21公钥密码学.ppt

第六章公钥密码学1 什么是公钥密码体制
公钥密码又称为双钥密码和非对称密码,是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的,见划时代的文献:
and , New Directrions in Cryptography, IEEE Transaction on Information Theory, -, Nov 1976, -654
单向陷门函数是满足下列条件的函数f:
(1)给定x,计算y=f(x)是容易的;
(2)给定y, 计算x使y=f(x)是困难的。
(所谓计算x=f-1(Y)困难是指计算上相当复杂,已无实际意义。)
(3)存在δ,已知δ时,对给定的任何y,若相应的x存在,则计算x使y=f(x)是容易的。
注:1*. 仅满足(1)、(2)两条的称为单向函数;第(3)条称为陷门性,δ称为陷门信息。
2*. 当用陷门函数f作为加密函数时,可将f公开,这相当于公开加密密钥。此时加密密钥便称为公开钥,记为Pk。 f函数的设计者将δ保密,用作解密密钥,此时δ称为秘密钥匙,记为Sk。由于加密函数时公开的,任何人都可以将信息x加密成y=f(x),然后送给函数的设计者(当然可以通过不安全信道传送);由于设计者拥有Sk,他自然可以解出x=f-1(y)。
3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。
-Hellman密钥交换算法
Diffie和Hellman在其里程碑意义的文章中,虽然给出了密码的思想,但是没有给出真正意义上的公钥密码实例,也既没能找出一个真正带陷门的单向函数。然而,他们给出单向函数的实例,并且基于此提出Diffie-Hellman密钥交换算法。这个算法是基于有限域中计算离散对数的困难性问题之上的:设F为有限域,g∈ F是F的乘法群F*=F\{0}=<g>。并且对任意正整数x,计算gx是容易的;但是已知g和y求x使y= gx,是计算上几乎不可能的。这已问题称为有限域F上的离散对数问题。公钥密码学种使用最广泛的有限域为素域FP.
对Diffie-Hellman密钥交换协议描述:Alice和Bob协商好一个大素数p,和大的整数g,1<g<p,g最好是FP中的本原元,即FP*=<g>。p和g无须保密,可为网络上的所有用户共享。
当Alice和Bob要进行保密通信时,他们可以按如下步骤来做:
(1)Alice送取大的随机数x,并计算
X=gx(mod P)
(2)Bob选取大的随机数x,并计算X = gx (mod P)
(3)Alice将X传送给Bob;Bob将X 传送给Alice。
(4)Alice计算K=(X )X(mod P);Bob计算K =(X) X (mod P),易见,K=K =g xx (mod P)。
由(4)知,Alice和Bob已获得了相同的秘密值K。双方以K作为加解密钥以传统对称密钥算法进行保密通信。
注:Diffie-Hellman密钥交换算法拥有美国和加拿大的专利。
3 RSA公钥算法
RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的(见Communitions of the ACM. . Feb. 1978, -126)该算法的数学基础是初等数论中的Euler(欧拉)定理,并建立在大整数因子的困难性之上。
将Z/(n)表示为 Zn,其中n=pq; p,q为素数且相异。若
Z*n{g∈ Zn|(g,n)=1},易见Z*n为(n)阶的乘法群,且有 g (n)1(mod n),而(n)=(p-1)(q-1).
RSA密码体制描述如下:
首先,明文空间P=密文空间C=Zn.(见P175).

选择p,q,p,q为互异素数,计算n=p*q, (n)=(p-1)(q-1), 选择整数e使((n),e)=1,1<e<(n)),计算d,使d=e-1(mod (n))),公钥Pk={e,n};私钥Sk={d,p,q}。
注意,当0<M<n时,M(n) =1(mod n)自然有:
MK(n)+1M(mod n), 而ed  1 (mod (n)),易见(Me)d  M(mod n)
(用e,n)明文:M<n 密文:C=Me(mod n).
(用d,p,q)
密文:C 明文:M=Cd(mod n)
注:1*, 加密和解密时一对逆运算。
2*, 对于0<M<n时,若(M,n) ≠ 1,则M为p或q的整数倍,假设M=cp,由(cp,q)=1 有 M(q)  1(mod q) M 