计算系统与网络安全 Computer System and Network Security 电子科技大学 计算机科学与工程学院 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

数论基础 子夏曰：“贤贤易色；事父母，能竭其力；事君，能致其身；与朋友交，言而有信。虽日未学，吾必谓之学矣。” 人际关系：父子；君臣；朋友；夫妻 贤贤易色4种不同的解释：一、以尊重贤人的心取代喜好美色的心；二、要像喜好美色一样地尊重贤人；三、要以恭敬的神色态度与贤人相处；四、丈夫与妻子相处时，要尊敬她的贤德胜过喜好她的美貌。 事父母能竭其力：侍奉父母则要尽心尽力。 事君能致其身：侍奉君主能尽忠职守。 与朋友交言而有信：和朋友交往要诚实信用。 虽曰未学：这样的人如果还自谦没学过什么东西。 吾必谓之学矣：我还是认为他算是有学过的人了。 父子关系；事君指君臣关系；与朋友交指朋友关系；这三者皆为人际关系，而贤贤易色的第四种解释，丈夫与妻子相处，则为夫妇关系，亦属人际关系。所以小弟以为此种解法较为合宜。 2019/2/25

整除定义及性质 1.定义： 2.整除的基本性质( N —整数集) 设整数a和b,且a ≠ 0，如果存在整数k使得b=ak， 那么就说a整除a（或b能被a整除），记作a|b，或者说b是a的倍数。 举例：3|15,-15|60 2.整除的基本性质( N —整数集) (1) a(a≠0),  a|0,a|a (同理b  N,1|b) (2) b|a, cb|ca (3) a|b, b|c  a|c.（传递性） (4) a|b, a|c  a|(xb+yc) (x,yN) (5) b|a 且a≠0 |b|≤|a| (6) cb|ca, b|a 证明（3）： b=ak1 c=ak2 xb+yc=sak1+tak2=a(xk1+ytk2) 2019/2/25

带余数除法 带余数除法： 如果a，b是两个整数，其中b>0，则存在两个整数q和r，使得a＝bq＋r（0≤r＜b）成立，且q和r是唯一的。 证明： （1）作一个整数序列 （2）反证法 证明 （1）： 对于整数序列 …, -3b, -2b, -b, 0, b, 2b, 3b ,… a比在上述某两项之间，即存在一个整数q使得： qb≤a<(q+1)b 令a-qb=r则证明完成。 （2）假设存在另外一对q1，r1满足a＝bq1＋r1 则： bq＋r＝bq1＋r1 所以：b(q-q1)=r1-r | b(q-q1)|=|r1-r| 因为r和r1都小于b，因此|r1-r|<b 如果q≠q1，则| b(q-q1)|>b 矛盾 2019/2/25

带余数除法 定义（非负最小剩余） 非负最小剩余的性质： a＝bq＋r（0≤r＜b）中r叫做非负最小剩余，常记做<a>b=r（在不致引起混淆的情况下，b常常省略） 非负最小剩余的性质： （1）<a1 + a2> = < <a1> + <a2> > （2）<a1 - a2> = < <a1> - <a2> > （3）<a1 a2> = < <a1> <a2> > 证明: a1=bq1+<a1>, a2=bq2+<a2> 由于<a1>+<a2>=是一个整数，因此由最小剩余的定义可知： <a1>+<a2>=bq3 +<<a1> +<a2>> 所以： a1+a2=b(q1+q2)+<a1>+<a2> =b(q1+q2+q3++<<a1>+<a2>> <a1+a2>=<<a1>+<a2>> 2019/2/25

素数定义及素数个数定理 1.定义： 合数（4，6，8，9，12等） 一个大于1的整数p，只能被1或者是它本身整除,而不能被其他整数整除，则称整数为素数(prime number)，否则就叫做合数(composite)。 eg 素数（2，3，5，7，11，13等） 合数（4，6，8，9，12等） 2019/2/25

素数补充定理 2.补充定理(1)：设a是任一大于1的整数，则a的除1外的最小正因子q是素数，并且当a是合数时： 定理： （1）假定q不是素数，由定义，q除1和它本身以外还有一个正因素q1，因而1<q1<q，但是由于q|a，所以q1|a，这与q是a的最小正因子矛盾，因此q一定是素数 （2）当a是合数时，则a＝a1q，且q≤a1，故a＝a1q≥qq=q^2,所以且q≤sqrt（a） 2019/2/25

素数补充定理（续） 2.补充定理(2)：若p是一个素数，a是任一整数，则有p|a或(p,a)=1 证明： 设p和a的最大公因素为（p，a），则有（p，a）|p 由于p是素数，因此（p，a）＝1或（p，a）＝p。而由（p，a）＝p，可得p|a 2019/2/25

素数补充定理（续） 2.补充定理： p为素数，且p|ab,那么p|a或p|b。 更一般地，如果ab…z能够被素数p整除，那么a,b,…,z中的某个数必能被p整除。 定理的证明采用数学归纳法 2019/2/25

素数个数定理及证明 3.素数个数定理（1）： 素数的个数是无限的 证明：反证法 假设正整数个数是有限的，设为p1,p2,…..,pk 令：p1p2…pk+1=N (N>1) 则N有一个素数p，且p≠pi（i=1,2,…,k). 故p是上述k个素数外的另外一个素数。 因此与假设矛盾。 原因： （1）N（N>1）的除1外的最小正因数q是一个素数 （2）如果q=pi，（i＝1,2,…,k), 且q|N，因此q|(N- p1p2,…..pk)，所以q|1，与q是素数矛盾。 2019/2/25

素数定义及素数个数定理 3.素数个数定理（2）： eg:可以估算100位素数的个数： 设(x)是小于x的素数个数，则 (x) ≈ x / lnx, 即x→∝时，比值(x) /(x / lnx) →1 eg:可以估算100位素数的个数： (10100) - (1099) ≈ 10100/(ln10100) – 1099/(ln1099) ≈3.9 * 1097. 2019/2/25

整数的唯一分解定理 1.整数的唯一分解定理定理（算术基本定理）: 设n∈Z, 有分解式, n = ±p1e1p2e2...pmem,其中p1, p2,…, pm∈Z+是互不相同的素数, e1,e2,…,em∈Z+, 并且数对(p1, e1), (p2, e2),…,(pm, em)由n唯一确定（即如果不考虑顺序，n的分解是唯一的）. 定理 （1）采用数学归纳法证明存在性 （2） eg: 504=23327, 1125 = 3253 2019/2/25

最大公约数定义及求法 1.定义 2. 求最大公约数的两种方法： 两个整数a,b的最大公约数，就是能同时整除a和b的最大正整数,记为gcd(a,b)， 或(a,b). eg: gcd(5,7) = 1， gcd(24,60) = 12， 2. 求最大公约数的两种方法： (1)因数分解： eg:1728 = 2632,4536 = 23347, gcd(1728, 4536) = 2332=72. 2019/2/25

最大公约数的欧几里得算法 (2)欧几里得(Euclid)算法 设a, bN, a>b>0, 用以下方法可求出 gcd(a,b). 定理：a＝bq＋c，其中q四整数，则(a,b)=(b,c) 证明： 因为(a,b)|a，(a,b)|b，所以(a,b)|c（理由： C|A,C|B,则C|MA+MB, 在本定理中注意c＝a－bq，因为(a,b)|a-bq，所以(a,b)|c） 因为(a,b)|b,(a,b)|c,所以（a,b)是b和c的公因素，因此(a,b)<=(b,c) 同理：（a,b)>=(b,c) 所以(a,b)=(b,c) gcd(a,b)=Rn的证明： (Rn-2,Rn-1)=(Rn-1,Rn)=(Rn-1,Rn)=(a,b) 2019/2/25

最大公约数的欧几里得算法（续） Euclid算法实例：求 gcd(132, 108). 2019/2/25

最大公约数的欧几里得算法（续） 欧几里得算法（例1） 求：gcd（1180，482） gcd（1180，482）＝2 2019/2/25

最大公约数的欧几里得算法（续） 欧几里得算法（例2）：求gcd(12345,1111) 2019/2/25

最大公约数的欧几里得算法（续） 欧几里得算法抽象 规律：余数－除数－被除数－忽略 2019/2/25

最大公约数的欧几里得算法（续） 欧几里得算法实现 2019/2/25

扩展的欧几里得算法 3.定理 设a, b∈Z+, 则存在m, n∈Z使得gcd(a,b)=ma+nb. 证明：根据Euclid算法 a=bq1+r1 b=r1q2+r2 r1=r2q3+r3 , …… rn-2 = rn-1qn+rn gcd(a,b)= r n = rn-2 - rn-1qn =…… = ma+nb 特别a, b为素数时gcd(a,b)=1，存在 ma+nb=1. 上述求 rn = ma+nb的方法叫做扩展的Euclid算法 利用该方法我们可以求ax+by=d的解,这里d= (a,b) 2019/2/25

扩展的欧几里得算法（续） 欧几里得算法的结果 扩展的欧几里得算法的结果 计算出了gcd(a,b); 但是并没有计算出两个数m，n来，使得： ma+nb=gcd(a,b) 扩展的欧几里得算法的结果 计算出了gcd(a,b); 计算出两个数m，n来，使得： ma+nb=gcd(a,b) 2019/2/25

扩展的欧几里得算法（续） 利用该方法我们可以求密码学方程ax+by=d的解,这里d= (a,b) 例如: 求132x+108y = 12的解 解： 12=gcd(132,108) 12 = 108-424 = 108-4 (132-108  1) = 108 – 4  132 +4 108 =5*108 – 4*132 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

同余 1.定义 2.定理 a≡b (mod m)  m|(a-b). 设a,b∈Z, m∈Z+, 如果a和b被m除所得余数相同，则称a和b关于模数m同余，记为a≡b (mod m). 2.定理 设a,b∈Z, m∈Z+, 则 a≡b (mod m)  m|(a-b). 证明： 必要性:设a≡b (mod m), a=mp+r, b=mq+r, 0≤r<m  a-b=m(p-q), m|(a-b). 充分性:设m|(a-b), a=mp+r, b=mq+s, 0≤r, s<m  a-b=m(p-q)+(r-s)  m|(r-s) 0≤|r-s|<m, ∴ r=s,  a≡b (mod m). 证毕 2019/2/25

同余及模运算性质 3.同余的性质 4.模运算的性质 设a,b∈Z, m∈Z+ (1) 自反性：a∈Z  a≡a (mod m). (2) 对称性：a≡b (mod m)  b≡a (mod m). (3) 传递性：a≡b，b≡c (mod m)  a≡c (mod m). 4.模运算的性质 设m∈Z+, a≡b (mod m), x≡y (mod m), 则有 (1) a+x≡b+y (mod m) （加法） (2) a-x ≡b-y (mod m) （减法） (3) ax ≡ by (mod m) （乘法） （1）的证明：a＝b+mt,x=y+ms a+x=b+mt+y+ms =(b+y)+m(t+s) a+x|b+y(mod m) 2019/2/25

模运算的除法运算及其性质 4.模运算的性质 例： （4）除法：相对复杂 如果：12x＝24，那么：3x＝8 如果：12x＝24（mod3），那么：3x＝8（mod3）？？？ 定理：设整数a，b，c，n（n≠0），gcd(a，n)＝1，如果ab＝ac（mod n），则b＝c（mod n）。 例： 求解2x＋7＝3（mod 17） 解：2x＝3－7 → 2x＝－4 x＝－2 x＝15（mod 17） （1）的证明：a＝b+mt,x=y+ms a+x=b+mt+y+ms =(b+y)+m(t+s) a+x|b+y(mod m) 计算成立的原因：gcd（2，17）＝1 2019/2/25

模运算的除法运算及其性质（续） 4.模运算的性质 （4）除法： 例： 求解5x＋6＝13（mod 11） 解：5x＝13－6 所以： 5x＝7（mod 11）→ 5x＝40（mod 11） x＝8（mod 11） （1）的证明：a＝b+mt,x=y+ms a+x=b+mt+y+ms =(b+y)+m(t+s) a+x|b+y(mod m) 计算成立的原因：gcd（5，11）＝1 2019/2/25

乘法逆元 5.模m的乘法逆元 则称y是x的模m乘法逆元, 记为: y=x-1 eg： 2  3≡1 (mod 5) 定义：设m∈Z+, x, y∈Z, 如果xy≡1 (mod m), 则称y是x的模m乘法逆元, 记为: y=x-1 eg： 2  3≡1 (mod 5) ∴ 3是2的模5乘法逆元, 2是3的模5乘法逆元. 2  8≡1 (mod 5) ∴ 8是2的模5乘法逆元. 注意：模m乘法逆元不唯一！ 但是，如果求一个与模数互素的数的乘法逆元，则是唯一的。 2019/2/25

扩展欧几里德算法与乘法逆元 欧几里德算法与乘法逆元 如果算法gcd（a，b）输出rm＝1，则b有乘法逆元 如果求出了ma+nb=1中的整数m，n，则可以求出b（mod a）的乘法逆元。 欧几里得算法没有给出b的乘法逆元b－1 如何求b－1 ？ 扩展的欧几里德算法 2019/2/25

扩展欧几里德算法与乘法逆元（续） 2019/2/25

扩展欧几里德算法与乘法逆元（续） 例：求28mod75的乘法逆元(a=75,b=28) i ri qi si ti 1 2 3 4 19 9 1 2 3 4 19 9 -1 -2 -8 75=2X28+19 28=1X19+9 19=2X9+1 9=9X1+0 2019/2/25

扩展欧几里德算法 2019/2/25

剩余类和完全剩余系 定义（剩余类） 设m是一个给定的正整数，Cr（r＝0，1，2，……,m－1）表示所有形如qm＋r的整数组成的集合，其中q＝0，±1， ±2，…，则C0，C1，…Cm-1叫做模数m的剩余类。 例如：m＝3 C0＝3q C1＝3q＋1 C2＝3q＋2 2019/2/25

剩余类和完全剩余系（续） 定理：设m>0， C1，…Cm-1是模数m的剩余类，则有： （1）每一个整数恰好包含在某一个类Cj中（0≤j≤m-1） （2）两个整数x和y属于同一个类的充要条件是x≡y（mod m） 证明： （1）由于a＝qm＋r，因此a恰好包含在Cr中。 （2）充分条件： 设a和b都包含在Cr中，则有： a＝q1m＋r，b＝q2m＋r。因此： a－b＝(q1－q2)m（即m|a-b） 必要条件： 反之， 如果m|a-b，a和b模m同余，因此属于同一个Cr（原因：a和b模m同余的充要条件是m|a－b) （2）充分条件： 设a和b都包含在Cr中，则有： a＝q1m＋r，b＝q2m＋r。因此： a－b＝(q1－q2)m（即m|a-b） 必要条件：反之， 如果m|a-b，a和b模m同余，因此属于同一个Cr（原因：a和b模m同余的充要条件是m|a－b) 2019/2/25

剩余类和完全剩余系（续） 定义（完全剩余系）： 在模数m的剩余类 C1，…Cm-1中各取一数aj（j=0，1，…，m-1），此m个数a0，a1，…，am-1称为模数m的一组完全剩余系。 例如：m＝3 C0＝｛0，3，6，9，…｝ C1＝｛1，4，7，10，…｝ C2 ＝｛2，5，8，11，…｝ 则a0＝0，a1＝1，a2＝2就是模m的一组完全剩余系。 2019/2/25

剩余类和完全剩余系（续） 定理（完全剩余系）： m个整数组成模数m的一组完全剩余系的充要条件是两两对模数m不同余。 定义（非负最小完全剩余系） 由0， 1，2，…，m-1组成的剩余系称为模数m的非负最小完全剩余系。 2019/2/25

剩余类和完全剩余系（续） 定理（完全剩余系）： 设（k, m）＝1，a0，a1，…，am-1是模数m的一组完全剩余系，则： ka0， ka1，…，kam-1也是模数m的一组完全剩余系。 证明： 如果kai＝kaj（mod m），则m| k(ai-aj)，又(k,m)=1,所以m|(ai-aj)，与条件矛盾。 2019/2/25

剩余类和完全剩余系（续） （1）剩余类可能包含多个集合（ 即：模数m的剩余类是多个集合） （2）完全剩余系专指一个集合 如果一个模数m的剩余类里面的数与m互素，就称之为与模数m互素的剩余类。 例如：m＝3 C1＝｛1，4，7，10，…｝ C2 ＝｛2，5，8，11，…｝ 都是模m互素的剩余类。 证明： 如果kai＝kaj（mod m），则m| k(ai-aj)，又(k,m)=1,所以m|(ai-aj)，与条件矛盾。 2019/2/25

剩余类和完全剩余系（续） 定义（缩系） 在与模数m互素的全部剩余类中，各取一个数所组成的集合叫做模数m的一组缩系。 例如：m＝3 C1＝｛1，4，7，10，…｝ C2 ＝｛2，5，8，11，…｝ 是模m互素的剩余类，而C＝ ｛4，5｝是模数m的一组缩系。 证明： 如果kai＝kaj（mod m），则m| k(ai-aj)，又(k,m)=1,所以m|(ai-aj)，与条件矛盾。 问题：缩系含有多少个数？ 2019/2/25

费马小定理和欧拉定理 1.定义（欧拉函数） 欧拉函数的求法： 欧拉函数ϕ(n)是一个定义在正整数上的函数， ϕ(n) 的值等于序列0，1，2，…，n－1中与n互素的数的个数。 欧拉函数的求法： （1）如果n是素数，则ϕ(n)=n-1 （2）n＝pq，其中p，q为素数，则ϕ(n)=(p-1)(q-1) （3） 证明：ϕ(n) = ϕ(p1^e1) ϕ(p2^e2)… ϕ(pm^em) 下证：ϕ(p^) = p^ - p^( -1) ϕ(p^)等于从p减去在1,2,… p^中与p不互素的数的个数，因为p是素数，故ϕ(p^)等于从p^减去在1,2,… p^中被p整除的数的个数。而在 1,2,… p,p+1,…,2p,…,p^(-1)p 中，p的倍数共有p^(-1)个，所以ϕ(p) = p^ - p^(-1) ϕ(n) = ϕ(p1^e1) ϕ(p2^e2)… ϕ(pm^em) =(p1^e1 – p1^(e1-1))(p2^e2-p2^(e2-1)…(pm^em-pm^(em-1)) =p1^e1p2^e2…pm^em(1-1/p1)(1-1/p2)…(1-1/pm) =n (1-1/p1)(1-1/p2)…(1-1/pm) 2019/2/25

费马小定理和欧拉定理（续） 定理（缩系中数的个数） 例如： m＝3， ϕ(m)＝2，因而C＝ ｛1，2｝含有两个数。 定理（缩系） 模数m的缩系含有ϕ(n)个数。 例如： m＝3， ϕ(m)＝2，因而C＝ ｛1，2｝含有两个数。 定理（缩系） 若a1，a2，…，a ϕ(m)是ϕ(m)个与m互素的整数，则a1，a2，…，aϕ(m)是模数m的一组缩系的充要条件是它们两两对模数m不同余。 2019/2/25

费马小定理和欧拉定理（续） 定理：若（a，m）＝1，x通过模数m的缩系，则ax也通过模数m的缩系。 证明： 当x通过模数m的缩系，则ax通过ϕ(m)个整数，由于（a，m）=1，（x，m）=1，因此（ax，m）=1。 若ax1≡ax2（mod m），可知x1≡x2（mod m），与假设x通过模数m的缩系矛盾，故ax通过模数m的缩系。 2019/2/25

费马小定理和欧拉定理（续） (2)欧拉定理 eg: 求7803的后三位数字 设m>1，如果gcd(a, n) = 1,则:aϕ(n) ≡ 1mod n. eg: 求7803的后三位数字 解： 7803（mod 1000）的结果 ϕ(1000) = 1000(1-1/2)(1-1/5) = 400， 有7803 ≡ (7400)273 ≡ 343 (mod 1000) 证明： 设r1，r2，…rϕ（n）是模数m的一组缩系，则由定理3，ar1，ar2，…，arϕ（n）也是模数m的缩系。因此： （ar1）（ar2）…arϕ（m）＝r1r2…rϕ（m）（mod m），即： a^ϕ（m）r1r2…rϕ（m）= r1r2…rϕ（m）(mod m) 由于： （ri，m）＝1，i＝1，2，…， ϕ（m） 所以： （r1r2…r ϕ（m））＝1 因此： a^ϕ（m）＝1（mod m） 2019/2/25

费马小定理和欧拉定理（续） 推论（ Fermat小定理）: 例如： 求 253 (mod 11) = ? p素数,a是整数且不能被p整除,则:a p-1 ≡ 1 mod p. 例如： 求 253 (mod 11) = ? 由Fermat小定理: 210 = 1024 ≡ 1 (mod 11) 253 = (210)523 ≡ 1523 ≡8 (mod 11) 证明（1）： 证明: 考虑集合s1 = {1,2,…,p-1},对每个数乘以a,得到集合s2 = {a (modp),2a(modp),…,(p-1)a(modp)}, s2中的元素两两不同且都在1与p-1之间,因此两个集合相同,于是:(p-1)! =1  2  …  (p-1) ≡[a(modp) 2a(modp)  … (p-1)a(modp)] mod p ≡[a  2a …  (p-1)a] mod p ≡[ap-1  (p-1)!] mod p 注意到(p-1)!与p互素,两边消去(p-1)!，得 a p-1 ≡ 1 mod p 证明（2）： 因而p是素数，所以p的欧拉数为p－1，带入欧拉定理即得。 2019/2/25

费马小定理和欧拉定理的应用 （2）但2n-1 模n 不等于 1,那么n不可能为素数 （1）通常情况下，如果2n-1 ≡ 1 (mod n),n为素数,然而,也有例外: 561 = 3 11 17是合数,但2560 ≡ 1 (mod 561)。因此，如果2n-1 ≡ 1 (mod n),那么n可能为素数。 （2）但2n-1 模n 不等于 1,那么n不可能为素数 这为我们提供一种寻找素数的方法，给定一个n, 计算2n-1 模n 是否等于 1，如果不等于1， n为非素数，如果等于1，还需用更复杂的方法来判断是否为素数，比如： (1)索洛维-斯特拉森(Solovay-Strassen)素性检测算法 (2)米勒-罗宾(Miller-Rabin)素性检测算法 (3) AKS算法 2019/2/25

欧拉定理的应用 eg: 计算243210 （mod 101） 解： （1）由费尔马定理2100（mod 1001）＝1（mod 101） 2019/2/25

一次同余式 7.一次同余式 eg : (1)定义: 设m∈Z+, a, b∈Z, a≠0, 我们把 ax+b≡0 (mod m) 称为模数m的一次同余式. 如果x0∈Z满足: ax0+b≡0 (mod m) 则称x≡x0 (mod m)是同余式的解. eg : 同余式2x+1 ≡0 (mod 3) 有解x0=1. 同余式2x+1 ≡0 (mod 4) 无解. 同余式2x+1 ≡0 (mod 5) 有解x0=2. 2019/2/25

一次同余式（续） 定理1: (2)一次同余式的解 设m∈Z+, a, b∈Z, a≠0, (a, m)=1, 则同余式 ax≡b (mod m)恰有一个解x≡ba ϕ(m)-1 (mod m). eg:同余式2x+1≡0 (mod 5) 有解: x0=(-1)×2 ϕ(5)-1 ≡4×23 ≡32≡2 (mod 5) 证明： 因为1，2，…，m组成一组模数m的完全剩余系，（a，m）＝1，因此a，2a，3a，…，ma也组成模数m的一组完全剩余系，故其中恰有一个数设为aj，适合aj=b（mod m），x＝j（mod m）就是其唯一解。 2019/2/25

一次同余式的解 定理2: 设m∈Z+, a, b∈Z, a≠0, (a, m)=d, 则同余式ax≡b(mod m) 有解的充要条件是d|b. 在d|b的条件下, 同余式有d个解. eg: 同余式2x ≡3 (mod 4)无解⇐d=(2,4)=2ł3. 同余式2x ≡4 (mod 6) d=(2,6)=2|4 有2个解: x=2, 5. 证明： （1）如果方程有解，则由d|a,d|m，推出d|b。ax＝b＋mq，b＝ax－mq＝d（n1－n2q）＝dn，因此d|b。 （2）如果d|b，则因（a/d，m/d）＝1，因此同余式（a/d）x＝（b/d）（mod m/d）有一组解，即方程有一组解。 （3）如果有整数c满足方程ax=b(mod m),则c也适合方程（a/d）x＝（b/d）（mod m/d） 反之，如c适合（a/d）x＝（b/d）（mod m/d），则也适合ax=b(mod m)。 设t适合（a/d）x＝（b/d）（mod m/d），则（a/d）x＝（b/d）（mod m/d）有唯一解x＝t（mod m/d），即全体整数t+k(m/d)(k=0,1,2,….)对模数m来说，恰可选出d个互不同余的整数，因此有d个解。 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

中国剩余定理 《孙子算经》中记载着一道世界闻名的“孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 孙子问题等同于下面这样一个问题： 已知 x=2mod3，x=3mod5且x=2mod7，求整数x。 2019/2/25

中国剩余定理（续） 2019/2/25

中国剩余定理（续） 2019/2/25

中国剩余定理（续） 2019/2/25

中国剩余定理（续） 中国剩余定理(孙子: Sun Ze, 公元前450年,孙子定理)： 设自然数m1,m2,…mr两两互素，并记M=m1m2…mr，则同余方程组: x ≡ b1(mod m1) x ≡ b2(mod m2) ....... x ≡ br(mod mr) 有唯一解： x ≡ b1*M1*y1+b2*M2*y2+…+br*Mr*yr (mod M) Mi = M/mi ,yi = Mi-1 (mod mi) (1 i r) 2019/2/25

中国剩余定理解同余方程组 例如:求以下同余方程组的解： x ≡5 mod 7 x ≡3 mod 11 x ≡10 mod 13 解： r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10; 模M = m1 m2  m3 = 1001, M1 =M/ m1 = m2  m3 = 143, M2 =91, M3 =77. y1 = M1-1(mod m1) = 143-1(mod 7) = 5, y2=4, y3=12. 解为: x = b1  M1  y1 + b2  M2  y2 + b3  M3  y3 (mod M) = 5  143  5 + 3  91  4 + 10  77  12 (mod 1001) =13907 (mod 1001) = 894 验证: x = 894 = 127 7+5 = 5 (mod 7) 2019/2/25

中国剩余定理（续） 中国剩余定理： 其中： m=miMi Mi’Mi=1 (mod m) 除数 余数 最小公倍数 衍数 乘率 各总 答数 b1 m=m1m2…mk M1 M1’ M1M1’b1 X=∑MiMi’bi (mod m) m2 b2 M2 M2’ M2M2’b2 …… mk bk Mk Mk’ MkMk’bk 其中： m=miMi Mi’Mi=1 (mod m) 2019/2/25

中国剩余定理（续） 2019/2/25

中国剩余定理求解同余方程组 例如（孙子算经）解法：表格法 除数 余数 最小公倍数 衍数 乘率 各总 答数 3 2 3x5x7=105 5x7 M1’=2 35x2x2 140＋63＋30＝233 5 7x3 M2’=1 21x1x3 7 3x5 M3’=1 15x1x2 2019/2/25

中国剩余定理（续） 2019/2/25

中国剩余定理（续） 2019/2/25

中国剩余定理（续） 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

模的幂运算 优势： 模的幂运算可快速完成，并且不需要太大内存 计算Xa ( mod n) ,其中 x, a, n ∈Z+ Eg:计算21234 (mod 789) 一种有效的方法： 24 ≡ 16 28 ≡ 256 216 ≡ 2562 ≡ 49 232 ≡ 492 ≡ 34 264 ≡ 342 ≡ 367 2128 ≡ 3672 ≡ 559 2256 ≡ 5592 ≡ 37 2512 ≡ 372 ≡ 580 21024 ≡ 5802 ≡ 286 1234 = 1024+128+64+16+2 （1234 = (10011010010)2） 21234 = 286  559 367 49 4 ≡ 481 (mod 789) 优势： 模的幂运算可快速完成，并且不需要太大内存 2019/2/25

模的幂运算（续） 但是，上述计算过程并不适合于计算机程序实现。为此，可以采用“重复平方-乘”运算来进行指数模运算。 2019/2/25

模的幂运算（续） 重复平方-乘算法 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

整数的次数 由欧拉定理知道：如果(a, m)＝1，m>1，则aϕ(n) ≡1(mod m) aγ ≡1(mod m) 定义（整数的次数）： 若(a, m)＝1，m>1，则使得同余式 aγ ≡1(mod m) 成立的最小正整数γ叫做a对模m的次数。 2019/2/25

整数的次数（续） 定理：设a对模数m的次数为l，an≡1（mod m），则l|n。 证明： 如果结论不成立，则必有两个整数q和r，使得： n＝ql＋r（0<r<l） 而1≡ an ≡a(ql＋r) ≡ aqlar ≡ ar (mod m)，因此与l的定义相违背。 推论的证明： 因为a^ϕ(m）＝1（mod m），因此l|ϕ(m) 推论：设a对模数m的次数为l，则l|ϕ(m)。 2019/2/25

整数的次数（续） 整数次数的计算： 因为l|ϕ(m)，因此可以通过计算以下对模数m的值求出。 例如：m＝7，a＝2 Φ(m)＝6＝2×3 22（mod 7）＝4 23（mod 7）＝1 因此a对模数m的次数为3。 推论的证明： 因为a^ϕ(m）＝1（mod m），因此l|ϕ(m) 2019/2/25

整数的次数（续） 整数次数的有效计算方法（1）： 推论的证明： 因为a^ϕ(m）＝1（mod m），因此l|ϕ(m) 2019/2/25

整数的次数（续） 整数次数的有效计算方法（1）： 推论的证明： 因为a^ϕ(m）＝1（mod m），因此l|ϕ(m) 2019/2/25

整数的次数（续） 整数次数的有效计算方法（2）： 推论的证明： 因为a^ϕ(m）＝1（mod m），因此l|ϕ(m) 2019/2/25

整数的次数（续） 定理：设a对模数m的次数为l，1,a, a2,…，al-1≡对模数m两两不同余。 证明： 如果结论不成立，则有某对j，k（0≤j<k≤l-1，使得： aj ≡ ak（mod m） 因此： ak-j≡ 1（mod m） 而1<k-j<l-1，因此与l的定义相违背。 2019/2/25

本原根定义 定义（原根） 设整数m>0,(g,m)=1, 如果整数g对m的次数为ϕ(m) ，则g叫做m的一个本原根（或原根）. eg: 3是模7的本原根 因为3 ϕ(7) ≡ 36 ≡1(mod 7) 一般说来，当p为素数时，模p本原根是一个数，它的幂构成模p的同余类，且存在ϕ(p-1) 个模p的本原根。 例如： 3是模7的本原根，3(mod7)的幂运算： 31 ≡3 32 ≡2 33 ≡6 34 ≡4 35 ≡5 36 ≡1 2019/2/25

本原根定义（续） 例如：m＝7，a＝2 Φ(m)＝6＝2×3 22（mod 7）＝4 23（mod 7）＝1 因此： 所以： 2不是7的本元根。 推论的证明： 因为a^ϕ(m）＝1（mod m），因此l|ϕ(m) 2019/2/25

本原根判断 定理（原根） 设整数m>0,(g,m)=1,则g是m的一个原根的充要条件是： g，g2，…gϕ(m)组成模数m的一组缩系。 2019/2/25

本原根有关定理 2.定理： 设对素数p而言，如果g是一个本原根 (1)如果n是整数，那么gn ≡1(mod p)当且仅当 n≡0(mod p-1) (2)如果j和k都是整数，那么gj ≡ gk当且仅当j ≡k(mod p-1) 2019/2/25

本原根有关定理（续） 问题：是否所有的正整数都有原根？ 例如：m＝12 Φ(m)＝6＝2×3，与m互素的正整数包括5，7，11。 52（mod 12）＝1 因此，5对12的次数是2 72（mod 12）＝1 因此7对模数m的次数为2 112（mod 12）＝1 因此11对模数m的次数为2 因此m＝12没有原根。 2019/2/25

本原根有关定理（续） 定理（整数存在原根的必要条件）： 设m>1，若m有原根，则m必为下列诸数之一：2，4，pl，2pl（l≥1，p为奇素数）。 定理（整数存在原根的充分条件）： 设m＝2，4，pl，2pl（l≥1，p为奇素数）时，则m有原根。 定理（整数原根个数）： 设m有一个原根g，则m恰有ϕ(ϕ(m))个对模数m不同余的原根，这些原根由以下集合给出： 2019/2/25

本原根有关定理（续） 2019/2/25

本原根有关定理（续） 原根的判断： 一般来说，判断g是否时一个素数m的原根时，不需要逐一计算g1，g2，…，gϕ(m)，而仅需要计算gt(modm），其中t|ϕ(m)。 2019/2/25

本原根有关定理（续） 2019/2/25

本原根有关定理（续） 定理（原根的计算）： （1）若g是模数m的一个原根，则g对模数m的次数是ϕ（m），但0<ϕ(m)/qi<ϕ(m)(i=1,2,…,s)，故等式成立。 （2）如果等式成立，设g对模数m的次数是f，假定f<ϕ(m)，因此f|ϕ(m)，所以ϕ（m）/f是大于1的整数，故有某个素因素qi|(ϕ(m)/f)，即ϕ(m)/f=qiu，于是ϕ(m)/qi=fu， g^（ϕ(m)/qi)=g^fu=1(mod m)。矛盾，故f＝ϕ（m），g是m的一个原根。 2019/2/25

本原根有关定理（续） 2019/2/25

本原根有关定理（续） 2019/2/25

本原根有关定理（续） 定理（原根的计算）： （1）若g是模数m的一个原根，则g对模数m的次数是ϕ（m），但0<ϕ(m)/qi<ϕ(m)(i=1,2,…,s)，故等式成立。 （2）如果等式成立，设g对模数m的次数是f，假定f<ϕ(m)，因此f|ϕ(m)，所以ϕ（m）/f是大于1的整数，故有某个素因素qi|(ϕ(m)/f)，即ϕ(m)/f=qiu，于是ϕ(m)/qi=fu， g^（ϕ(m)/qi)=g^fu=1(mod m)。矛盾，故f＝ϕ（m），g是m的一个原根。 2019/2/25

本原根有关定理（续） 一个计算原根的算法： （1）若g是模数m的一个原根，则g对模数m的次数是ϕ（m），但0<ϕ(m)/qi<ϕ(m)(i=1,2,…,s)，故等式成立。 （2）如果等式成立，设g对模数m的次数是f，假定f<ϕ(m)，因此f|ϕ(m)，所以ϕ（m）/f是大于1的整数，故有某个素因素qi|(ϕ(m)/f)，即ϕ(m)/f=qiu，于是ϕ(m)/qi=fu， g^（ϕ(m)/qi)=g^fu=1(mod m)。矛盾，故f＝ϕ（m），g是m的一个原根。 2019/2/25

本原根有关定理（续） （1）若g是模数m的一个原根，则g对模数m的次数是ϕ（m），但0<ϕ(m)/qi<ϕ(m)(i=1,2,…,s)，故等式成立。 （2）如果等式成立，设g对模数m的次数是f，假定f<ϕ(m)，因此f|ϕ(m)，所以ϕ（m）/f是大于1的整数，故有某个素因素qi|(ϕ(m)/f)，即ϕ(m)/f=qiu，于是ϕ(m)/qi=fu， g^（ϕ(m)/qi)=g^fu=1(mod m)。矛盾，故f＝ϕ（m），g是m的一个原根。 2019/2/25

本原根有关定理（续） （1）若g是模数m的一个原根，则g对模数m的次数是ϕ（m），但0<ϕ(m)/qi<ϕ(m)(i=1,2,…,s)，故等式成立。 （2）如果等式成立，设g对模数m的次数是f，假定f<ϕ(m)，因此f|ϕ(m)，所以ϕ（m）/f是大于1的整数，故有某个素因素qi|(ϕ(m)/f)，即ϕ(m)/f=qiu，于是ϕ(m)/qi=fu， g^（ϕ(m)/qi)=g^fu=1(mod m)。矛盾，故f＝ϕ（m），g是m的一个原根。 2019/2/25

指数 如果整数m>0有一个元根g，g，g2，…gϕ(m)(或数1,g，g，g2，…gϕ(m)-1）组成模数m的一组缩系。 例如， 3是模7的本原根，因此： 31 ≡3 32 ≡2 33 ≡6 34 ≡4 35 ≡5 36 ≡1 上述六个数刚好是模数m的一组缩系。 （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） 定义：任一整数n，（n，m）＝1，必有唯一的整数k（0≤k< ϕ（m）），满足： n≡gk（mod m） 其中k叫做n对模数m的指数，记做k＝indgn（简记为ind n） (指数也叫做离散对数)。 （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） 指数的性质：设g是m的原根，如果(a,m)＝(b,m)＝1： （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

指数（续） （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

离散对数困难问题 基于离散对数困难性假设，EIGamal提出了EIgamal公钥密码体制。 （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

离散对数困难问题（续） （1）证明： 按照指数的定义： ab=g^(ind(ab)) a＝g^ind(a) b=g^ind(b) g^(ind(ab))=g^(g^(ab))=g^(g^a+g^b) =g^(ind(a)+ind(b)) Ind(a,b)=ind(a)+ind(b)(mod ϕ（m））， 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

模n逆矩阵 定理：一个平方矩阵是模n可逆的当且仅当 它的行列式和n是互素的. 证明：假设M平方矩阵在模n下有逆矩阵N,则 MN ≡ I(mod n) det(MN) ≡ det(M)det(N) ≡ det(I) ≡1 (mod n) 因为 det(M)可逆 (det(M),n)=1 Eg:2 2矩阵,通常的求逆为： a b -1 d -b = 1/(ad-bc) c d -c a 2019/2/25

模n逆矩阵（续） 1 2 假如要求 (mod11)的逆 3 4 因为ad-bc = -2,需求-2 (mod11)的逆，因为5 (-2) ≡1 (mod11) 1 2 4 -2 4 -2 9 1 ≡ 1/(-2) ≡5 ≡ (mod11) 3 4 -3 1 -3 1 7 5 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

模n平方根 定义(二次剩余） 设n是一个大于1的正整数， a∈Z, a ≠0 (mod n). 如果同余方程 x2≡a (mod n) 有一个解1≤x≤n-1, 则称a是模数n的二次剩余，而x称之为a模n的平方根。 如果上述方程无解，则a称之为模数n的非二次剩余。 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

模n平方根（续） 2019/2/25

第2章 信息安全数学基础（数论） 本原根 模的幂运算 中国剩余定理 同余 基本概念 有限域 模n平方根 模n逆矩阵 2019/2/25

有限域 2019/2/25

有限域（续） 2019/2/25

多项式 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

多项式（续） 2019/2/25

有限域 p=2,z2=｛0,1｝ ,不可约多项式m(x) = 1+x2+x3 , 多项式F[x] = Z2[x] eg:GF（23）域的构造： p=2,z2=｛0,1｝ ,不可约多项式m(x) = 1+x2+x3 , 多项式F[x] = Z2[x] GF（23） = Z2[x]/< 1+x2+x3> = ｛0，1， x,x+1,x2,x2+1,x2+x,x2+x+1｝ 2019/2/25

教材与参考书 教材： 李毅超 曹跃，网络与系统攻击技术 电子科大出版社 2007 周世杰 陈伟 钟婷，网络与系统防御技术 电子科大出版社 2007 参考书 阙喜戎 等 编著，信息安全原理及应用，清华大学出版社 Christopher M.King, Curitis E.Dalton, T. Ertem Osmanoglu（常晓波等译）. 安全体系结构的设计、部署与操作，清华大学出版社，2003(Christopher M.King, et al, Security Architecture, design, deployment & Operations ) William Stallings，密码编码学与网络安全－原理与实践（第四版），电子工业出版社 蔡皖东，网络与信息安全，西北工业大学出版社，2004 李建平，小波分析与信息处理---理论、应用及软件实现，1997年第一版，2001年第二版，2003年第二版修订版。 张世永，网络安全原理与应用，科学出版社，2003 杨义先等，信息安全理论与技术，邮电出版社 2019/2/25

课外阅读资料 Mao Wenbo， Modern Cryptography: Theory and Practice ， 电子工业出版社，2004 2019/2/25

Any Question? Q&A 2019/2/25