谈到现代密码学，数论的影响起着决定性的作用。计算机算法的实现、密码算法的构造、软硬件的优化都离不开数论的理论支持。作为信息安全行业的工作者和学生，数论是我们无法回避的一座大山，是我们心中无法抚平的伤感。而中国剩余定理就是爱恨交织的部分。追寻信息安全的数学基础，欧几里得、欧拉、费马、伽罗瓦，都是来自西域的高山。只有中国剩余定理，这是有古书为证的中国特产。我得意地听着，发现我听不懂同样的话。感觉自己进化了两千多年……在研究中国余数定理之前，我们必须了解它对信息安全行业的应用价值。以公钥密码学为例。1976年，Diffie和Hellman提出的DH密钥协商协议开创了基于数学难题的公钥密码学的新纪元。公钥密码学设计的基本思想是：找到一个公认的数学问题，并在该问题的基础上构建密码算法。例如，DH密钥协商算法的有效性取决于计算离散对数的难度，使得在有限域中已知明文M很容易计算密文C，但已知C很难计算M。为了安全通信，Alice和Bob需要安全地交换一个密钥，所以他们分别选择自己的秘密a和b，g是双方已知的一个大质数的原根，计算Ca=g^a，Cb=g^b。得到对方的Ca和Cb后，两人分别计算Cab=Ca^b=Cb^a=g^ab。这样，爱丽丝和鲍勃就秘密完成了公钥的协商，以后的通信就可以加密了。计算g^a只是数学家手中的公式，但在实际运算中，g和a可能是1024或2048位二进制数，而我们现在的计算机CPU一次只能运算64位二进制——草稿纸上写不出来的数字乘法怎么算？没问题，中国剩余定理会帮助你。中国余数定理（Chineseremaindertheorem，CRT），又名孙子余数定理，初见于《孙子算经》卷2第28题“物不知数”：不知数事物的数量，三和三的数量是二。五五之数有三，七七之数有二。问几何？大意是这里有一堆不知道数量的东西。有的人以三***数还剩两个，有的人以五***数还剩三个，有的人以七**数还剩两个，请问这堆东西应该是多少？这个问题和民间传说“韩信点兵”很像。秦末，楚汉相争。有一次，韩信与楚王的大将李奉交战。一场苦战，楚军大败，退回大营。汉军也损失了四五百人，韩信整顿兵马，返回大本营。到了一个山坡上，有后军来报，说有楚军骑兵追来。只见远处尘土飞扬，杀声震天。汉军本就疲惫不堪，此时队伍中却是一片哗然。韩信的兵马到了坡顶，见敌军骑兵不足五百，急忙调集兵力迎敌。他命令士兵排成3人一排，还有2个士兵；又命众兵排成5人，又来3人。他命令士兵组成7个士兵，还有2个士兵。韩信立即向将士们宣布：我军有勇士1073人，敌方不足500人，我们居高临下，一定能战胜敌人。汉军士气大振。一时之间，旌旗摇曳，战鼓震天，汉军步步为营，楚军大乱。战罢不久，楚军大败而逃。故事中韩信的计兵法是中国剩余定理的实际应用。古人是如何描述余数定理的？《孙子算经》“东西不知道怎么数”的问题的其余解决方法在下面的文章《技巧说：从三数到三，如果还剩两个，就设一百和四十；数到七，如果还剩两个，就数到三十。把它们加起来是233，用210减去，就得到了。对于那些数到三和三的人，还剩一个的，设七十；还剩一的，设二十一；数七到七，还剩一的，设十五；一百零六以上的，减去一百零五得它。”“求一术”的起源被认为是中国数学史上最具创造性的成果之一，被称为中国余数定理。为了方便读者理解中国余数定理，将该定理记为遵循现有的数论知识[1]：设m1,m2,...,mk为k(k≥2)个大于1的成对素数正整数，b1,b2,...,bk∈Z，方程由一个变量中的k个联立同余方程组成的系统如下：我们以1275年中国古代数学家杨辉所著的《续古摘奇算法》中的一道题为例，详细解释中国余数定理的过程。剩下的数是一换二，二换五，三换七，四换九，原来的数。解：题意是中国剩余定理的历史发展演变。中国剩余定理如下图所示：图1中国剩余定理历史发展演化路线简图[2]中国剩余定理在现代密码学中的应用在RSA领域，RSA公钥密码体制仍然被认可和采纳。它是公认的安全性较好的密码体制，也是现阶段比较常用的密码体制。基于中国余数定理的单基数转换法（SRC）和混合基数转换法（MRC）可以快速实现RSA的解密，解密速度提高了约四倍，这对实现RSA非常重要RSA加密算法在软件和硬件[3]。中国余数定理还可以应用于轻量级密码设计、PKI认证体系、通信编码等，在信息安全领域占有非常重要的地位。多项式结语在同余群问题上，中国余数定理的研究在古代就遥遥领先于世界，可见中国人的数学能力是极其出众的。古人对数学的贡献是我们宝贵的财富。中国剩余定理在密码学中的应用只是其价值的部分体现。希望科研人员能够充分利用这些财富，创造更多更大的辉煌。参考文献[1]顾立泽，杨义贤．现代密码学教程[M]．北京邮电大学出版社出版。2009:53[2]邓振政．中国剩余定理的中外历史发展比较[D].四川师范大学，2017.[3]何宜超，刘建勤，陈维海．中国剩余定理在RSA解密中的应用[J]．河北科学院学报,2003,20(3):138-143.》原创稿件，转载请联系原作者]点此查看该作者更多好文
