数论基础（续） 网络安全 推论：给定两个素数p,q,两个整数n,m,使得n=pq,0me,s则对于 任意整数k,下列关系成立：mk中(n)+1三mmod 证明：分两种情况： 1)m与n互素，则由欧拉定理得 m(n)三1modn mk()三1modn mkφ(n)+1≡m mod n 2) gcd(m,n)≠1，由于n=pq,则gcd(m,n)≠1意味着m要么是p的倍数， 要么是q的倍数，不妨设m=tp,其中t为一正整数。此时，gcd(m,q)=1, 否则m也是g的倍数，从而是pq的倍数，与m<n=pq矛盾。 由gcd(m,q)=1及欧拉定理得m(q)=1modq, [mk(q)](p)=1modq,mkΦ(m)≡1modq 因此存在一整数r,使得mk(n)=1+rq,两边同乘以m=tp,得mk(n)+1 =m+rtpq=m+rtn,即mkΦ(m)+1=8modn
18 数论基础（续） 推论：给定两个素数p, q , 两个整数 n, m ，使得n=pq, 0<m<n ； 则对于 任意整数k ，下列关系成立：m kф(n)+1 ≡ m mod n 证明：分两种情况： 1）m与n互素，则由欧拉定理得 mф(n) ≡1 mod n m kф(n) ≡1 mod n m kф(n)+1 ≡m mod n 2） gcd(m,n)1，由于n=pq，则gcd(m,n)1意味着m要么是p的倍数， 要么是q的倍数，不妨设m=tp，其中t为一正整数。此时，gcd(m,q)=1， 否则m也是q的倍数，从而是pq的倍数，与m<n=pq矛盾。 由gcd(m,q)=1及欧拉定理得mф(q) ≡1 mod q， [mkф(q)] ф(p)≡1 mod q， mkф(n) ≡1 mod q 因此存在一整数r，使得mkф(n) =1+rq，两边同乘以m=tp，得 mkф(n)+1 =m+rtpq=m+rtn，即m kф(n)+1 ≡m mod n
RSA算法操作过程 网络安全 NETWORK SECURITY 密钥产生 1.取两个大素数p9,P≠9，保密； p=7,9-17 2.计算n=pg,公开n n=119 3.计算欧拉函数中(n)=(p-1)(q-1)5 Φ(n)=96 4.选择整数e使得gcd(e中(n)》= 选择e=5 1<e<中(n) 5.计算d=e1mod(n) 5d=kx96+1 令k=4,得到 d=77 公开(en)=(5119) 将d保密，丢弃pq 19
19 • 密钥产生 1. 取两个大素数 p, q , pq, 保密; 2. 计算n=pq，公开n; 3. 计算欧拉函数ф(n) =(p-1)(q-1)； 4. 选择整数e,使得 gcd (e, ф(n))=1; 1<e<ф(n) 5.计算d = e -1 mod (n) 公开(e, n)=(5, 119) 将d 保密，丢弃p, q p=7,q=17 n=119 Ф（n）=96 选择e=5 5d=k×96＋1 令 k=4, 得到 d=77 RSA算法操作过程
RSA算法加密/解密过程 网络安全 NETWORK SECURITY 公开密钥：KU={e,n} {5,119} 秘密密钥：KR={d,n} {77,119} 加密过程 ·把待加密的内容分成k比特的分组， k≤log2n,并写成数字，设为M,则： C=Me mod n c=m5 mod 119 ·解密过程 M=Cd mod n m=c77 mod 119 20
20 • 公开密钥: KU={e, n} • 秘密密钥: KR={d, n} • 加密过程 ▪ 把待加密的内容分成k比特的分组， k≤ log2n，并写成数字，设为M，则： C= Me mod n • 解密过程 M = Cd mod n RSA 算法加密/解密过程 {5, 119} {77, 119} c=m5 mod 119 m=c77 mod 119