计算系统与网络安全 Computer System and Network Security

计算系统与网络安全 Computer System and Network Security
电子科技大学计算机科学与工程学院 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

最大公约数的欧几里得算法（续） 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 = (  1) = 108 – 4  108 =5*108 – 4*132 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ê1) ϕ(p2ê2)… ϕ(pmêm) 下证：ϕ(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ê1) ϕ(p2ê2)… ϕ(pmêm) =(p1ê1 – p1^(e1-1))(p2ê2-p2^(e2-1)…(pmêm-pm^(em-1)) =p1ê1p2ê2…pmêm(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. 例如：求 (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

中国剩余定理《孙子算经》中记载着一道世界闻名的“孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”
孙子问题等同于下面这样一个问题：已知 x=2mod3，x=3mod5且x=2mod7，求整数x。 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   91   77  12 (mod ) =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

模的幂运算优势：模的幂运算可快速完成，并且不需要太大内存计算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 = （1234 = ( )2） 21234 = 286  559 367 49 4 ≡ 481 (mod 789) 优势：模的幂运算可快速完成，并且不需要太大内存 2019/2/25

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

模的幂运算（续）重复平方-乘算法 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

整数的次数（续）整数次数的有效计算方法（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 ≡ ≡2 33 ≡ ≡4 35 ≡ ≡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

本原根有关定理（续）定理（原根的计算）：
（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 ≡ ≡2 33 ≡ ≡4 35 ≡ ≡1 上述六个数刚好是模数m的一组缩系。（1）证明：按照指数的定义： ab=g^(ind(ab)) a＝gînd(a) b=gînd(b) g^(ind(ab))=g^(g^(ab))=g^(gâ+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înd(a) b=gînd(b) g^(ind(ab))=g^(g^(ab))=g^(gâ+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înd(a) b=gînd(b)
g^(ind(ab))=g^(g^(ab))=g^(gâ+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înd(a) b=gînd(b) g^(ind(ab))=g^(g^(ab))=g^(gâ+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)

离散对数困难问题基于离散对数困难性假设，EIGamal提出了EIgamal公钥密码体制。（1）证明：按照指数的定义：
ab=g^(ind(ab)) a＝gînd(a) b=gînd(b) g^(ind(ab))=g^(g^(ab))=g^(gâ+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)

模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 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) ≡ ≡ (mod11) 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

有限域 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

计算系统与网络安全 Computer System and Network Security

Similar presentations

Presentation on theme: "计算系统与网络安全 Computer System and Network Security"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

计算系统与网络安全 Computer System and Network Security

Similar presentations

Presentation on theme: "计算系统与网络安全 Computer System and Network Security"— Presentation transcript:

Similar presentations

About project

反馈