改进的背包公钥密码系统：利用中国剩余定理增强安全性

本文档探讨了一个改进的背包公钥密码系统，发表于1992年的《清华大学学报(自然科学版)》第32卷第4期。这个密码系统由何敬民教授提出，是对早期背包公钥密码系统的创新。原始系统主要基于中国剩余定理（孙子定理）构建背包，但在新的设计中，作者引入了加法操作到背包分量上，这是以往背包密码系统未采用过的策略。这种改变增加了系统的复杂性和安全性，因为每个背包分量不仅依赖于模数，还包含了随机选取的秘密量。 在系统构造中，用户A首先会秘密选择h个两两互素的正整数mi, m2, ..., m_h。这些数对于除A之外的所有人都是隐藏的。接着，用户计算相应的商和余数，通过解决一系列同余方程，得到每个Mi相对于模mi的值M'i。由于mi和Mi互质，确保了每个同余方程有唯一解。 改进的关键在于引入随机参数，这有效地消除了原系统中由于背包分量之间的大公因数导致的安全隐患。尽管作者承认目前无法提供严格的数学证明，但通过对可能的破解方法进行了深入分析，得出结论，改进后的系统在抵抗攻击方面表现出足够的强度。 然而，如同当时许多公钥密码系统一样，包括Merkle-Hellman系统，该改进系统也面临被破解的风险，但作者的创新尝试为密码学领域带来了新的思考和挑战。这表明在密码设计中，不断寻求新的构造方法和理论融合是提高安全性的重要手段。