第章公钥密码体制

第2.3章公钥密码体制公钥密码学RSA算法传统密码体制的不足对称密码体制的问题加密能力与解密能力是捆绑在一起的密钥更换、传递和交换需要可靠信道如有n用户，则需要C=n(n-1)/2个密钥，n=1000时，C(1000,2)≈500000，管理困难无法满足不相识的人之间通信的保密要求不能实现数字签名公钥密码学解决的基本问题密钥交换对称密码进行密钥交换的要求：已经共享一个密钥利用密钥分配中心数字签名如果密码编码学要获得广泛的应用，不仅用在军事场合而且用于商业或私人目的，那么电子报文和文件就需要一种与书面材料中使用的签名等效的认证手段。也就是说，我们能不能设计一种方法可以让参与各方都信服地确认一个数字报文是由某个人发送的？这是一个比鉴别更高一些的要求公钥密码学公钥密码学是密码学一次伟大的革命1976年，Diffie和Hellman在“密码学新方向”一文中提出使用两个密钥：公密钥、私密钥加解密的非对称性利用数论的方法是对对称密码的重要补充(/)公钥密码体制重要特点仅根据密码算法和加密密钥来确定解密密钥在计算上不可行。两个密钥中的任何一个都可用来加密，另一个用来解密。六个组成部分：明文、密文；公钥、私钥；加密、解密算法(/)对公钥密码的要求1.B产生一对密钥(公钥KUb，私钥KRb)在计算上是容易的。2.已知公钥和要加密的消息m，发送方A产生相应的密文在计算上是容易的：c=EKUb(m)3.接收方B使用其私钥对接收的密文解密以恢复明文在计算上是容易的：m=DKRb(c)=DKRb

[EKUb(m)]4.已知公钥KUb时，攻击者要确定私钥KRb在计算上是不可行的。5.已知公钥KUb和密文c，攻击者要恢复明文m在计算上是不可行的。6.加密和解密函数的顺序可以交换顺序：m=EKUb

[DKRb(m)]=DKUb

[EKRb(m)]单向函数单向函数将一个定义域映射到一个值域，使得每个函数值有一个惟一的原像；函数值计算很容易，而逆计算是不可行的

y=f(x) 容易

x=f-1(y) 不容易例子打碎/拼接平方/开方乘法/分解单向陷门函数对公钥密码的要求，相当于寻找一个单向陷门函数除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在另外的方向上要计算是不可行的。有了附加信息，函数的逆就可以在多项式时间内计算出来。即：

y=fk(x)容易，如果知道了k和x

x=fk-1(y)容易，如果知道了k和y

x=fk-1(y)不可行，如果知道y而不知道k例子魔方的置乱/恢复 如果有口诀，就能很快恢复公钥密码体制(/)公钥密码体制的加密功能A向B发消息XB的公钥为KUb,私钥为KRb加密Y=EKUb(X)解密X=DKRb(Y)(/)公钥密码体制的加密功能(/)公钥密码体制的认证A向B发送消息XA的公钥为KUa，私钥为KRa“加密”：Y=EKRa(X)（数字签名）“解密”：X=DKUa(Y)注意：不能保证消息的保密性(/)公钥密码体制的认证(/)具有保密与认证的公钥体制(/)对称密钥和公钥密钥(/)关于公钥密码的几种误解公钥密码比传统密码安全？公钥密码是通用方法，所以传统密码已经过时？公钥密码实现密钥分配非常简单？(/)公钥密码体制的应用加密/解密：发送方用接收方的公开密钥加密报文数字签名：发送方用它自己的私有密钥“签署”报文。签署功能是通过对于报文，或者作为报文的一个函数的一小块数据应用密码算法完成的密钥交换：两方合作以便交换会话密钥。这有几种可能的方法，其中涉及到一方或两方的私有密钥RSA算法简介RSA是基于Diffie和Hellman所提出的单向陷门函数的定义而给出的第一个公钥密码的实际实现RSA算法的名字以发明者的名字命名：RonRivest，AdiShamir和LeonardAdlemanRSA算法于1977年12月申请专利(U.S.Patent4,405,829)，2000年9月到期明文、密文是0到n-1之间的整数，通常n的大小为1024位或309位十进制数RSA的安全性一直未能得到理论上的证明，它经历了各种攻击，至今未被完全攻破国际上一些标准化组织ISO、ITU、SWIFT等均已接受RSA体制作为标准。在Internet中所采用的PGP(PrettyGoodPrivacy)中也将RSA作为传送会话密钥和数字签名的标准算法RSA算法描述加密：c=memodn,其中0≤m<n解密：m=cdmodn =(memodn)dmodn =(me)dmodn公钥为(e,n)，私钥为(d,n)必须满足以下条件：med

≡mmodn计算me和cd是比较容易的由e和n确定d是不可行的(/)为什么RSA可以加解密(/)因为Euler定理的一个推论，对于给定素数p和q，整数n和m，k，其中n=p

×

q，0<m<n，则下列等式成立：mk·ø(n)＋1≡mmodnRSA中:n=p

×

qø(n)=(p-1)(q-1)选择e&d

使得e·d≡1mod

ø(n)因此存在k使得e·d=1+k·ø(n)因此

cd=(me)d=m1+k.ø(N)≡mmodn

相关参数(n)：指小于n并且与n互素的正整数的个数 [参考书第8.2.2章Euler函数]对于素数p有：(p)=p-1

如：(37)=36对于n=pq，p，q均为素数，有(pq)=(p-1)(q-1)

(21)=(3–1)×(7–1)=2×6=12gcd(a,b)=1[参考书第4.3章Euclid算法]a,b

最大公因子为1，也即a,b互素a

≡b

modn[参考书第4.2章模运算](amodn)=(bmodn)，则称a，b对于模n同余，记为a

≡b

modn如73≡4mod23 21≡-9mod10RSA密钥的产生(/)随机选择两个大素数p,q

计算n=p×q注意ø(n)=(p-1)(q-1)

选择e使得1<e<ø(n),且gcd(e,ø(n))=1解下列方程求出de

×

d≡1modø(n)且0≤d≤n

公布公钥：KU={e,n}保存私钥：KR={d,n}销毁：p,qRSA的使用(/)发送方要加密明文m:获得接收方的公钥KU={e,n}计算:c=memodn,where0≤m<n接收方解密密文c:

使用自己的私钥KR={d,n}计算:m=cdmodn

注意：m必须比n小模幂运算模幂运算是RSA中的主要运算[(amodn)×(bmodn)]modn=(a×b)modn利用中间结果对n取模，实现高效算法对于RSA的模运算mamodn

假设a二进制表示为bibi-1…b0，则模运算可变化如下：RSA实例(/)选择两个素数:p=17和q=11计算n=pq=17×11=187机算ø(n)=(p–1)(q-1)=16×10=160选择e，使其与ø(n)互素且小于ø(n)。在此选择e=7确定d：de≡1mod160并且d<ø(n)。

因为23×7=161=10×160+1，符合要求。所以选择d=23。公布公钥KU={7,187}保护私钥KR={23,17,11}RSA实例对于明文信息m=88(88<187)加密：C=887

mod187 =[(884

mod187)×(882

mod187)×(881

mod187)]mod187 =(88×77×132)

mod187=11 881

mod187=88 882

mod187=(88×88)mod187=77 884

mod187=[(882

mod187)×(882

mod187)]mod187 =(77×77)mod187=132解密：M=1123

mod187=88

(/)问题1p=3，q=11，n=33，(n)=20，d=77e=1mod20，e=3加解密如下明文：(/)问题2c=10,e=5,n=35,m能够求出吗？如果：e=31,n=3599,d=?你看出什么问题了吗解答c=10,e=5,n=35,m能够求出吗？n=35=5×7=>p=5,q=7=>(n)=(5-1)(7-1)=24e=5,可以找到d=5

m=cdmodn=105mod35=5

RSA密钥生成必须做确定两个大素数：p,q

p,q

都应该在1075，10100之间选择e或者d，并计算d或者e素数测试是重要的算法[参考书p1778.3素数测试]由e求d要使用到扩展Euclid算法[参考书p97EXTENDEDEUCLID](/)RSA