文档介绍：第九章 公钥密码学
精选
*
对称密码体制的缺陷：
精选
*
{M,C,K，EK，DK}，且满足如下的条件：
；
ø(N) = 1 mod N
for all x not divisible by p or q, ie gcd(x,ø(N))=1
where ø(N)=(p-1)(q-1)
但在 RSA 中，e & d 是特殊选择的
ie =1 mod ø(N) =1+Rø(N)
hence have: M = Cd = = M1+Rø(N) = M1.(Mø(N))R = M1.(1)R = M1 mod N
精选
*
8。RSA举例
例子：
1. 选素数p=47和q＝71，得n=3337,
(n)=46×70＝3220；
2. 选择e=79，求得私钥d=e -1 1019(mod 3220〕。
3. 公开n=3337和e=79.
4. 现要发送明文688，计算：
68879(mod 3337)=1570
，用私钥d＝1019进展解密：
15701019〔mod 3337)=688
精选
*
9。RSA 平安性
RSA 平安性基于计算 ø(N)的困难性
要求分解模N
精选
*
10. RSA的实现问题
需要计算模 300 digits (or 1024+ bits) 的乘法
计算机不能直接处理这么大的数
〔计算速度很慢〕
需要考虑其它技术，加速RSA的实现
精选
*
11. RSA – 的快速实现
加密很快，指数小
解密比较慢，指数较大
利用中国剩余定理CRT，
CRT 对RSA解密算法生成两个解密方程 〔利用M = Cd mod R 〕
即: M1 = M mod p = (C mod p)d mod (p-1)
M2 = M mod q = (C mod q)d mod (q-1)
解方程 M = M1 mod p
M = M2 mod q
具有唯一解〔利用CRT 〕：
:M = [((M2 +q - M1)u mod q] p + M1
其中 mod q = 1
精选
*
：如果P是素数，且a小于p,如果至少存在一个x∈ [1，p-1]满足x2≡a(modp)，那么我们称a是模p的二次剩余〔quadratic residue〕。
：设p是一奇素数，对任何a≧0,我们定义勒让德符号〔Legendre symbol〕L(a,p)为
0 如果a ≡ 0(modp)
L(a,p)= 1 如果a是模p的二次剩余
-1 如果a是p的非二次剩余
〔欧拉准那么〕：设p是素数，那么x是模p的二次剩余当且仅当
x(P-1)/2 ≡ 1(modp)
精选
*
：假设p是素数，那么L(a,p) ≡ a(P-1)/2(modp)
：雅可比符号〔Jacobi symbol〕,记作J(a,n),是勒让德符号的一般化表示，它定义在任意正整数a和奇整数n上。设n的素数因子分解式为pe1……pek,那么
J(a，n)=L(a，p1)e1 …L(a，p)ek
精选
*
对一个奇整数n的Solovay-strassen素性测试
1. 选择一随机整数a，满足a∈ [1,n-1]
(a,n)=a(n-1)/2modn 那么
答复“n是素数〞
否那么 答复“n是合数〞
精选
*
-Hellman 密钥分配方案
公钥密码问世
Diffie & Hellman in 1976:
密钥交换的实际方法
公钥方案概念的提出
W Diffie, M E Hellman, "New directions in Cryptography", IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976
James Ellis (UK CESG) 在案970年曾提出此概念
精选
*
12。El Gamal 公钥加密方案
Diffie-Hellman key distribution scheme 的变形
能够用于平安交换密钥
published in 1985 by ElGamal:
T. El