《大学安全工程之密码学2第二章 密码学的数学基础》由会员分享，可在线阅读，更多相关《大学安全工程之密码学2第二章 密码学的数学基础（91页珍藏版）》请在金锄头文库上搜索。
1、1 第二章密码学的数学基础 数论 素数 模运算 代数结构 安全性基础 信息论 复杂性理论 2 为何讲素数？ 为何讲数？ 加（解）密：数字变换 信息：离散事件 例：A(0),B(1),Z(25) 为何讲素数？ 素数是数的基础 3 整除 定义：记为 例： 性质： ,mab =ba ?83 ,255,183 , 62 ?proof cybxacaba baabba cacbba = 4 素数与合数 定义：整数p是一个素数，如果它只能被+p, -p,+1,-1整除 例：2,3,5,7,11,13,17,101, 全体素数的集合记为P 定义：如果整数n不是素数，则它是一个合 数 例：4,9,187,90
2、0, 5 Theorem:(Fundamental Theorem of Arithmetic) nN n= p1e1p2e2pkek ( or piPpei) where epis the exponent of the prime factor p Note: the result of factorization is unique Example: 84=2237 数的因子分解 6 素数 Theorem: There are infinitely many primes Proof: (by contradiction) Assume , build a number N is The
3、re N is a new prime. max P 1. max21 +=PPPN 7 最大公因子 Definition: the greatest common divisor (GCD) is the number c Properties: Definition: if gcd(a,b)=1,then a and b are relatively prime (coprime) max),gcd(bdaddbac= brqbarbaproof babba nndndndnd kk = = 0mod: )mod,gcd(),gcd( ),.,gcd(,., 121 8 Finding G
4、CD Theorem: Example: Complexity = i ba i b i i a i i ii ii pbapbpa ),min( ),gcd( 637*3),gcd( 11*7*5*33465 7*3*2882 2 3 22 = = = ba b a )()( )(no conT bandathefactoringNeed = 9 Euclidean Algorithm: Example GCD(1970,1066) 1970=1*1066+904 gcd(1066,904) 1066=1*904+162 gcd(904,162) 904=5*162+94 gcd(162,9
5、4) 162=1*94+68 gcd(94,68) 94=1*68+26 gcd(68,26) 68=2*26+16 gcd(26,16) 26=1*16+10 gcd(16,10) 16=1*10+6 gcd(10,6) 10=1*6+4 gcd(6,4) 6=1*4+2 gcd(4,2) 4=2*2+0 gcd(2,0) 10 Euclidean Algorithm ),gcd(:3 00 . :2 ,:1 1 1 112 3221 2110 10 barstep randruntil rrqr rrqr rrqr step brarstep n nn nnnn = = += += +=
6、= 11 Euclidean Algorithm: Proof 111 1 2110 10 1 1131 21 ),gcd(),gcd(),gcd( ),gcd(. ),gcd(),gcd( ),gcd(),gcd( ),gcd( . 0 = = nnn n n nnnn nnn rbarbabar rba rbarqrba rbaandrba bar brandarrr rrr 12 Modular Arithmetic Why modular arithmetic? 011000100 Plaintext: 2n 110100111 Ciphertext: 2n +: addition :
7、 multiplication Problems: 1. the set of plaintext (and ciphertext) finite 2. how to define +,-,x,/ operations in finite 13 Modular Arithmetic (模运算) Definition: a mod n (modulo operator) is the remainder when a is divided by n. a mod n is r 等价于 a=qn+r (0rn) 1 20 n2n3nqna(q+1)n n r 14 Congruence Modul
8、o n (模n同余) Definition: Integers a and b are congruence modulo n - if a mod n= b mod n - Denoted as a b mod n - Example: 100 34 mod 11(1mod 11) - a b mod n a=b+kn)(ban 15 Congruence Properties(同余性质) Propertie1: Example: Propertie2: )(mod )(mod dba ndnba )(mod )(mod )(mod)(mod ndbca ndbca ndcnba + 9mo
9、d.10.10 ,.9mod110, 9mod110 001 2 aaaaaa m m m += 16 Congruence Relation（同余关系） 同余关系是一个等价关系 自反性 对称性 传递性 等价关系划分 cacbba abba aa 17 例：整数模（模剩余类） -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 : 7 Z 模剩余类 Z
10、7=0, 1, 2, , 6 18 Modular Arithmetic（模运算） We can define the modular arithmetic in the set of integers: Zn=0, 1, 2, , n-1 Under normal arithmetic (+, ) (a mod n) + (b mod n) mod n = (a+b) mod n Proof: Let a=q1n+r1, b=q2n+r2 (a+b) mod n = (q1n+r1+q2n+r2) mod n = (r1+r2) mod n (a mod n) (b mod n) mod n
11、 = (ab) mod n (+, ) (-,) ? 19 模运算：举例 (Z8=0, 1, 2, , 7, +) What? 20 模运算：举例 (Z8=0, 1, 2, , 7, ) 不包含Z8中所有的元 素 21 模运算说明 Additive Inverse Always Exists (a+(-a) = 0 mod n -a = n-a if (a+b) (a+c) mod n then b c mod n (-a)+a+b) (-a)+a+c) mod n Multiplicative Inverse NOT Always Exists Example: 6 in Z8 When?
12、22 模运算中的乘法逆 Definition: a-1mod n is the multiplicative inverse of a1,2,n-1 when ax1 mod n Theorem: If and only if gcd(a,n)=1, then the a-1 mod n exists Lemma: If gcd(a,n)=1, then ai aj mod n for all 0ijn (i j) Proof: assume ai aj mod n n|a(i-j) n|i-j i-j=0 23 乘法逆定理 Proof: gcd(a,n)=1 a1,n-1 mod n is
13、the permutation of 1,n-1 So there exists only an i that ai 1 mod n Therefore i is a-1mod n Suppose a-1exists, call it x ax 1 (mod n) and ax + yn = 1 for some integer y gcd(a, n)=1 (gcd(a,n)|ax+yn gcd(a,n)|1) 24 如何找到 a-1mod n ？ 在 1,n-1 中寻找,直到找到一个 a-1,使得 aa-1 1 (mod n) T(n)=O(n) 计算 a-1= a (n)-1 mod n
14、寻找(n) 分解 n T(n)=O(na) 用 Extended Euclidean Algorithm T(n)=O(logan) 25 Euclidean Algorithm: Example GCD(1970,1066) 1970=1*1066+904 gcd(1066,904) 1066=1*904+162 gcd(904,162) 904=5*162+94 gcd(162,94) 162=1*94+68 gcd(94,68) 94=1*68+26 gcd(68,26) 68=2*26+16 gcd(26,16) 26=1*16+10 gcd(16,10) 16=1*10+6 gcd(10,6) 10=1*6+4 gcd(6,4) 6=1*4+2 gcd(4,2) 4=2*2+0 gcd(2,0) 26 求a-1mod n gcd(n,a) n=aq1+r1 r1=n-aq1=
