《第四章公钥密码体制》.ppt

4.1公钥密码体制的基本原理 公钥密码体制 公钥密码学解决的基本问题 密钥交换 对称密码进行密钥交换的要求： 已经共享一个密钥 利用密钥分配中心 数字签名 与传统的签名比较 公钥密码学 是密码学一次伟大的革命 使用两个密钥：公钥、私钥 六个组成部分： 明文、密文；公钥、私钥； 加密、解密算法 仅根据密码算法和加密密钥来确定解密密钥在计算上不可行 加解密的非对称性 是对对称密码的重要补充 4.2 RSA算法 数论知识简介 定义3 模运算 同余：如果a和b都是整数，而m是一个固定的正整数，则当m能够整除a-b时，称a,b对模m同余，记为 a?b(mod m),如果a除m的余数为r,则r称为a模m的剩余，记作 a mod m.如a mod m=b mod m，表示(a-b)mod m=0； 定义:z m={0,1,2,3,……m-1}, 为模m剩余集, 其中m为整数. 数论知识简介 模运算： 9＋9＝6 mod 12 9×9＝9 mod 12 9－10＝11 mod 12 模运算的性质： [(a mod m) +(b mod m)]mod m=(a + b) mod m； - - ； * * ； 例：152 mod 12 =(3*3) mod 12=9 数论知识简介 a,x,n都为整数 定义4 若a?x mod m =1，则称a与x在乘法运算下关于模m互为逆元。如2和3关于模5互为逆元。 若a和m互素，则a在模m下有逆元。故z m*中每个元素关于模m都有逆元。用Euclid算法求乘法逆元 。 z m*定义为z m 中与m互素的数的集合. Euler函数：φ(n)=与n互素的、小于n的正整数的个数，即z m*中元素的个数。例： φ(3)= φ(4) = φ(6) =2，φ(5)=4，φ(7) =6， φ(12)=6 若n是素数，则φ(n)=n-1 若n=p*q，p、q是不同素数，则φ(n)=(p-1)*(q-1) 例： φ(21)= φ(3*7)=2*6=12 RSA算法 由MIT的 Rivest, Shamir Adleman 在 1977 提出 最著名的且被广泛应用的公钥加密体制 明文、密文是0到n-1之间的整数，通常n的大小为1024位或309位十进制数 RSA算法描述 加密： y=xe mod N, where 0≤xN 解密： x=yd mod N 公钥为（e，N）， 私钥为（d，N） 必须满足以下条件： xed = x mod N 计算xe和yd是比较容易的 由e和n确定d是不可行的 RSA 密钥产生过程 随机选择两个大素数 p, q (必威体育官网网址) 计算 N=p.q（n公开） 注意 ?(N)=(p-1)(q-1) （?(N) 必威体育官网网址） 随机选择 e使得1e?(N),且gcd(e,?(N))=1 解下列方程求出 d e.d=1 mod ?(N) 且 0≤d≤N 公布公钥: KU={e,N} 保存私钥: KR={d,p,q} RSA Example Select primes: p=17 q=11 Compute n = pq =17×11=187 Compute ?(n)=(p–1)(q-1)=16×10=160 Select e : gcd(e,160)=1; choose e=7 Determine d: de=1 mod 160 and d 160 Value is d=23 since 23×7=161= 10×160+1 Publish public key KU={7,187} Keep secret private key KR={23,17,11} RSA Example cont sample RSA encryption/decryption is: given message M = 88 (注意 88187) encryption: C = 887 mod 187 = 11 decryption: M = 1123 mod 187 = 88 注意： 对任意整数k, Xe (mod n)≡（X+kn）e (mod n),所以每一个明文X,X+n,X+2n, …,X+mn将产生同样的密文。 若限定X在集合{1,2,…,n-1}之内时，明文与密文就是一对一了。 解密过程的证明 因为 Euler 定理的一个推论: Mk?(n)＋1 =