信息安全数学基础--算法应用与实践（第2版）/网络空间安全重点规划丛书

作者简介

深入浅出地阐述信息安全数学基础的理论与方法，强调理论在信息安全中的具体应用实例。

内容简介

第3章第3章同余式 第2章引入了同余的概念，本章介绍在模m情况下同余式的求解。首先介绍一次同余式的求解，再介绍一次同余式组的求解。 本章的重点是中国剩余定理及其在RSA中的应用，难点是模重复平方法。 3.13.1一次同余式3.1.1一次同余式的求解 定义3.1设m是一个正整数，f(x)为多项式且f(x)=anxn+…+a1x+a0其中ai是整数，则f(x)≡0 (mod m)称作模m同余式。若an0 (mod m)，则n叫作f(x)的次数，记为degf。此时叫作模m的n次同余式。 如果整数a使得f(a)≡0 (mod m)成立，则a叫作同余式的解。 事实上，满足x≡a (mod m)的所有整数都使得该同余式成立。因此，在讨论同余方程的解时，以一个剩余类作为一个解。在模m的完全剩余系中，使得同余式成立的剩余的个数叫作同余式的解数。 下面首先考虑一次同余式的求解。 定理3.1一次同余方程ax≡b (mod m)有解的充要条件是(a,m)|b，且当其有解时，其解数为(a,m)。 在证明之前，回顾定理1.8及其推论1.1，若同余方程有解，即b可以由a,m线性表出，于是(a,m)|b。 证明先证明必要性。设同余方程ax≡b (mod m)有解，解为x0，则存在整数k，使得ax0=km+b信息安全数学基础——算法、应用与实践（第2版）第3章同余式即 b=ax0-km由于(a,m)|a，(a,m)|m，因此(a,m)|ax0-km=b再证明充分性。 设a′=a(a,m)，m′=m(a,m)，b′=b(a,m)，易知，a′,m′,b′均为整数。 首先考虑同余方程a′x≡1 (mod m′)因为gcd(a′,m′)=1，可知a′存在模m′的乘法逆元x0（见定义2.3）。满足a′x0≡1 (mod m′)，且在模m′下,逆元是唯一的，即同余方程a′x≡1(mod m′)存在唯一解x≡x0 (mod m′)因此，易知同余方程a′x≡b′ (mod m′)也存在唯一解x≡x1≡x0b′(mod m′)下面证明这个解也是ax≡b (mod m)的特解。 不妨设x=k1m′+x0b′， k1∈Zax=ak1m′+ ax0b′=ak1m(a,m)+ax0b(a,m)= a′k1m+ a′x0b ≡a′x0b (mod m)由于a′x0≡1(mod m′)，不妨设 a′x0=k2m′+1，k2∈Za′x0b=(k2m′+1)b=k2m′b+b=k2m(a,m)b+b=k2mb′+b ≡b (mod m)最后，ax≡b (mod m)的全部解为x≡x1+tm(a,m) (mod m)t=0,1,…，(a,m)-1其原因是： 如果同时有同余式ax≡b (mod m)，ax1≡b (mod m)成立，两式相减得到a(x-x1)≡0 (mod m)这等价于x≡x1 modm(a,m)因此，x只要与x1关于m(a,m)同余，即为ax≡b (mod m)的解。■ 定理3.1的证明过程其实给出了一次同余式求解的过程。 定理3.2设m是一个正整数，a是满足(a,m)|b的整数，则一次同余式ax≡b (mod m)的全部解为x≡a(a,m)－1modm(a,m)b(a,m)+ tm(a,m) (mod m)t=0,1,…,(a,m)-1 ■定理3.2其实给出了一次同余式“根与系数的关系”。定理3.2是定理3.1的充分性证明过程的结果，图3.1给出了解的3个部分与定理3.1的对应关系。为便于记忆，这里将这3个部分简称为“模系收缩求逆元”“逆元扩大求特解”“t变模扩求全解”。“模系收缩”的目的是使得“系数a”和“模m”之间互素，从而可以求“系数a的逆元”。有了“逆元”之后就可以扩大“b′=b(a,m)”求出特解。最后再由特解求全解。 图3.1一次同余式“根与系数的关系”示意图 由定理3.2可以给出一个求解一次同余式的算法。 例3.1求解同余方程6x≡5 (mod 8)。 解答 (6,8)5，由定理3.1知，同余方程无解。 例3.2求解同余方程3x≡5 (mod 8)。 解答(3,8)|5，所以同余方程有解。 先解同余方程3x≡1 (mod 8)，此方程解唯一，易知其解为x≡3 (mod 8)，则同余方程3x≡5 (mod 8)也存在唯一解x≡3·5≡7 (mod 8)即为原方程的解。 例3.3求解同余方程6x≡2 (mod 8)。 解答先判断(6,8)|2，所以同余方程有解。 先解同余方程3x≡1 (mod 4)，此方程解唯一，易知其解为x≡3 (mod 4)取x1=3，则x=x1+82t=3+4t,(t=0,1) (mod 8)为原方程的解。原方程的所有解为x≡3 (mod 8) x≡3+4≡7 (mod 8) 例3.4求解同余方程6x≡4 (mod 8)。 解答先判断(6,8)|4，所以同余方程有解。 先解同余方程3x≡1 (mod 4)，此方程解唯一，易知其解为x≡3 (mod 4)同余方程3x≡2 (mod 4)也存在唯一解x≡x1≡2·3≡2 (mod 4)取x1=2，则x=x1+82t=2+4t(t=0,1) (mod 8)为原方程的解。原方程的所有解为x≡2 (mod 8) x≡6 (mod 8) 3.1.2一次同余式在仿射加密中的应用 仿射密码是一种古典密码，其算法设计时用到的数学基础是模运算和同余方程。上一章曾经介绍过移位密码，由于移位密码的密钥量太小，且移位密码在加密代换后字母的先后次序其实没有改变。仿射密码可以改进上述两个弱点。 定义明文空间P=Z26、密文空间C=Z26、密钥空间为K＝{（a,b）∈Z26·Z26：gcd(a,26)=1}对于x∈P,y∈C,k=(a,b)∈K定义加密函数ek(x)=ax+b mod 26定义解密函数dk(y)=a-1(y-b) mod 26例3.5利用仿射加密，a=3，b=5，模为26。 解答易知，加密函数为e(x)=3x+5 (mod 26)。 加密明文hello，其在Z26表示为7,4,11,11,14。 加密密文用Z26，表示为0,17,12,12,21，即密文为armmv。 思考3.1仿射密码中a是否有要求。 根据定理3.1，这里要求(a，26)=1；否则，加密函数就不是一个单射函数。 例如，当k=(6,1)时，(a,26)=(6,26)=2时，对x∈Z26，有6(x+13)+1=6x+1 mod 26于是x，x+13都是6x+1的明文。 思考3.2证明(a,26)=1时，仿射密码的解唯一。 证明设存在x1，x2∈Z26，使得ek(x)=ax1+b=ax2+b mod 26，于是ax1=ax2 mod 26，有26|a(x1-x2)，又因为(a,26)=1，所以26|(x1-x2)，由于x1，x2∈Z26，得到x1=x2。■ 思考3.3仿射密码的密钥空间大小，即密钥的数量有多少。 a的可能性为12，因为a∈Z26,gcd(a,26)=1，即a=φ(26)=φ(2·13)=φ(2)·φ(13)＝1·12＝12b∈Z26，b的可能性为26。 故整个密钥空间大小为12×26=312。 如果密钥空间太小，容易导致穷举所有可能的密钥，然后看能否解密密文的攻击。 另外，当a=1时，仿射密码就退化为移位密码。 3.23.2中国剩余定理在研究了一次同余式之后，下面考虑一次同余式组。 中国剩余定理（Chinese remainder theorem，CRT），又称孙子定理，最早见于公元5—6世纪，我国南北朝的一部经典数学著作《孙子算经》中的“物不知数”问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?” 这其实是求解一个一次同余方程式组，即x≡2 mod 3 x≡3 mod 5 x≡2 mod 7《孙子算经》中给出了解法，但这只是一个孤立的例子。南宋数学家秦九韶创立的“大衍求一术”一般性地解决了一次同余方程组的求解问题，中国古代这一成果统称为“孙子定理”，在外国文献中常被称为“中国剩余定理”。它可能是最著名的由中国人给出的算法。 在给出CRT算法之前，先给出一个逐步尝试（或局部调整）的算法体会一下，可以得到结果，但其时间效率不高。方法是： 在模3余2的数最小为5，不断增加3，保持模3余2，使其能够模5余3，刚好是5+3=8，然后在保持模2余3和模5余3的情况下，不断增加15（即不改变模3和模5的余数），使得模7余2，刚好是8+15=23。 在给出正式的算法之前，请先思考以下同余式组，即x≡2 mod 3 x≡2 mod 5 x≡2 mod 7容易知道，这个容易解决，即x≡2 (mod 105)，于是x=3·5·7K+2，K∈Z。 问题是，如果余数不再相等，则问题就有点麻烦了，再来看同余式组，即x≡2 mod 3 x≡3 mod 5 x≡4 mod 7设法从3K1+2，5K2+3，7K3+4（K1，K2，K3∈Z）中找到同一个数看上去是不容易的。也就是说，找到一个数同时满足这3个条件是不容易的。于是，能否换个思路，即能否把x“想象”成由3个部分组成。为便于对CRT求解过程的理解，下面专门给出一个特别的表述和解释。 写成3个部分的好处是： 每个部分的条件将“更容易”满足。 令x=A+B+C，若A，B，C满足以下条件，则为解。这里［a］m表示模m与a同余。A=［2］3，B=［0］3，C=［0］3 A=［0］5，B=［3］5，C=［0］5 A=［0］7，B=［0］7，C=［2］7看最左边一列，A为5·7的倍数，且模3余2，这样A就比较容易求解了。A可用以下方法计算。 A=(5·7)·(5·7)-1·2。因为这个表达式中有（5·7），因此是5和7的倍数。同时这个表达式模3余2。原因是： (5·7)=35。(5·7)-1表示(5·7)模3的逆元。35模3的逆元是2。两者相乘必然模3余1。因此，再乘以2后必然模3余2。即A=35·2·2=140模3余2，且为5和7的倍数。 同理，B为3·7的倍数，且模5余3，于是，可用以下方法计算： B=(3·7)·(3·7)-1·3，这里(3·7)-1表示(3·7)模5的逆元。3·7=21，21模5的逆元是1。因此，B=21·1·3=63。 同理，C为3·5的倍数，且模7余2，于是，可用以下方法计算： B=(3·5)·(3·5)-1·2，这里(3·5)-1表示(3·5)模7的逆元。3·5=15，15模7的逆元是1。因此，C=15·1·2=30。 于是x=A+B+C=140+63+30=233。又233 mod 105=23。因此，所有解为105K+23。 在程大位著的《算法统要》（1593年），用4句诗给出了上述解答过程的中几个关键数字： 三人同行古来稀，五数梅花廿一枝; 七子团圆正月半，除百零五便得之。 这几个关键的数字是： 与模3对应的是70（“古来稀”），即35·2；与模5对应的是21（“廿一枝”），即21·1；与模7对应的是15·1=15（“正月半”）。有了这三个关键数字，只要给出x模3，5，7的余数a1，a2，a3，即可以计算出结果x=a1·70+a2·21+a3·15 (mod 105)。结果除去105=3·5·7的倍数（“除百零五”）即可以得到答案。 一般地，如果m1，m2，m3是两两互素的正整数，对于同余方程组x≡a1 mod m1 x≡a2 mod m2 x≡a3 mod m3令m=∏3i=1mi，Mi = m/mi，则解为x≡∑3i=1Mi·Mi-1·ai (mod m)当然，上述解法可以推广到一般情况。 例3.6韩信点兵问题： 有兵一队，若列成五行纵队，则末行一人，若列成六行纵队，则末行五人；若列成七行纵队，则末行四人；若列成十一行纵队，则末行十人。求兵数。 解答转化为同余式组x≡1 mod 5 x≡5 mod 6 x≡4 mod 7 x≡10 mod 11应用CRT，m=5·6·7·11=2310M1=2310/5=462，M-11≡3 (mod 5) M2=2310/6=385，M-12≡1 (mod 6) M3=2310/7=330，M-13≡1 (mod 7) M4=2310/11=210，M-14≡1 (mod 11) x≡462·3·1+385·1·5+330·1·4+210·1·10 ≡6731≡2111 (mod 2310)下面给出CRT的严格证明。 定理3.3（中国剩余定理）设m1,m2,…，mk是k个两两互素的正整数，令 m=∏ki=1mi，Mi = m/mi(i=1,2，…，k)，则对任意的整数a1，a2，…，ak，同余式组x≡a1 mod m1 x≡a2 mod m2  x≡ak mod mk（3.1）有唯一解，即x≡∑ki=1Mi·Mi-1·ai (mod m) （3.2）其中：MiMi-1 ≡ 1 (mod mi)证明由于(mi,mj)=1，i ≠ j，即得(Mi，mi)=1，由定义2.3和定理2.8知，对每一个Mi，有一个M-1i存在，使得MiM-1i≡1 (mod mi)。另外，由于m=miMi，因此，mj|Mi，i ≠ j，故∑ki=1Mi·Mi-1·ai≡Mi·Mi-1·ai≡ai (mod mi)i=1,2,…，k即式（3.1）为式（3.2）的解。 若x1，x2是满足式（3.2）的任意两个整数，则x1≡x2(mod mi)（i=1,2,…，k），因为（mi,mj）=1，i≠j,于是x1≡x2(mod m)，故式（3.1）仅有解式（3.2）。■ 根据CRT，可以给出一个求解一次同余式组的算法。 " 本书包括初等数论、抽象代数、椭圆曲线论等方面的内容，该书选材合理、难度适中、层次分明、内容系统。书中以大量例题深入浅出地阐述信息安全数学基础各分支的基本概念、基本理论与基本方法。注重将抽象的理论与算法和实践相结合，并强调理论在信息安全特别是密码学中的具体应用实例。本书语言通俗易懂，容易自学。 本书可作为高等院校信息安全、网络空间安全、计算机科学与技术、密码学、通信工程、信息对抗、电子工程等领域的研究生和本科生相关课程的教科书，也可作为这些领域的教学、科研和工程技术人员的参考书。 "