现在密码学第11讲公钥密码

第5章

公钥密码主要内容

公钥密码体制的产生公钥密码体制的基本原理

RSA公钥密码体制其它公钥密码算法安全服务保密性验证（鉴别）完整性不可抵赖性（不可否认性）访问控制可用性

传统密码体制在应用中的缺陷密钥管理的麻烦在拥有大量用户的通信网络，若想让两两用户都能进行保密通信，即要求(1)任意一对用户共享一个会话密钥，需要通过保密信道进行密钥交换。(2)不同的用户对共享的会话密钥不相同对于分配中心，N个用户则需要分配N2/2个会话密钥，大量的数据存储和分配是一件很麻烦的事，在计算机网络环境下显的尤为突出。传统密码体制在应用中的缺陷密钥难以传输不能提供法律证据缺乏自动检测密钥泄密的能力公钥密码体制(Publickeysystem)公钥密码学与其他密码学完全不同：公钥算法基于数学函数而不是基于替换和置换使用两个独立的密钥公钥密码学的提出是为了解决两个问题：密钥的分配数字签名1976年Diffie和Hellman首次公开提出了公钥密码学的概念，被认为是一个惊人的成就。公钥密码体制的原理公钥体制(Publickeysystem)(Diffie和Hellman,1976)

每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。密钥持有量大大减少提供了对称密码技术无法或很难提供的服务：如与哈希函数联合运用可生成数字签名，可证明的安全伪随机数发生器的构造，零知识证明等

公钥密码体制有4个组成部分明文：算法的输入，它们是可读信息或数据，用M表示；密文：算法的输出。依赖于明文和密钥，对给定的消息，不同的密钥产生密文不同。用E表示；公钥和私钥：算法的输入。这对密钥中一个用于加密，为Ke，此密钥公开；一个用于解密，为Kd，此密钥保密。加密算法执行的变换依赖于密钥；加密、解密算法公钥密码体制下的秘密通信保证机密性

MEKbeE(M,Kbe)DKbdMKbe：Bob的公钥Kbd

：Bob的私钥保证真实性

Kad：Alice的私钥Kae

：Alice的公钥MEKadE(M,Kad)DKaeM既保证机密性又保证真实性

Kad：Alice的私钥Kae

：Alice的公钥MEKbeE(C1,Kbe)DKbdMEKadC1=E(M,Kad)C1DKaeKbe：Bob的公钥Kbd

：Bob的私钥公钥密码应满足的要求通讯双方A和B容易通过计算产生出一对密钥（公开密钥K1，私钥密钥K2）。在知道公开密钥K1和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：C=Ek1（M）接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：M=Dk2（C）=Dk2[Ek1（M）]除A和B以外的其他人即使知道公钥k1，要确定私钥K2在计算上也是不可行的。除A和B以外的其他人即使知道公钥k1和密文C，要想恢复原来的明文C在计算上也是不可行的单向陷门函数这些要求最终可以归结到设计一个单项陷门函数。单向函数：一个单向函数是满足下列条件的函数：它将一个定义域映射到值域，使得每个函数值有一个唯一的原像，同时还要满足下列条件：函数值计算很容易，而逆计算是不可行的。单项陷门函数：所谓单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在另外的方向上要计算是不可行的。有了附加的信息，函数的逆就可以在多项式时间内计算出来。一个实用的公开密钥密码系统的建立和发展依赖于找到一个单向陷门函数。对公钥密码体制的攻击攻击公开密钥密码系统的方法有如下几种：穷举法–对此防范措施应为：使用长的密钥。但是由于公钥算法依赖于单向陷门函数，计算函数的复杂性与密钥的长度的关系可能会增长得更快。因而密钥大小必须足够大，以保证安全性，但是又要足够小以便加密解密使用。根据公钥计算私钥–在数学上证明，对任何公钥算法，这种分析可能成功。因而对任何公钥算法，对这种攻击方法都需要测试

。常用加密算法:RSA算法

RSAAlgorithm概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman[Rivest等1978,1979]发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。算法原理RSA算法使用了乘方运算。要求：明文M经过加密得到密文C：C=Memodn

密文C经过解密得到明文M：

Cd

modn=(Memodn)dmodn=Medmodn=M即：必须存在e，d，n，使Medmodn=M成立如何确定e,d,n确定n：独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值(n)=(p－1)(q－1)确定e：随机选一整数e，1<

e<(n)，gcd((n),e)=1确定d：根据ed=1

mod(n)在模(n)下，计算d这样确定的e,d,n是否能使Medmodn=M成立呢？因为ed=1

mod(n)即ed=k(n)+1

所以：Med=Mk(n)+1如果M和n互素，即gcd(M,n)=1那么，根据欧拉定理(如果gcd(a,n)=1，则

aФ(n)

≡1modn)：有：M(n)≡1modn所以：Med≡Mk(n)+1≡M[M(n)]kmod

n

≡M[1]kmodn

≡Mmodn如果M和n不互素，即gcd(M,n)≠1，即M和n有大于1的公约数。因为n=pq，而p、q都是素数，不可再分解，所以M一定包含了p或q为因子。又因为M<n，所以M不可能既是p的倍数又是q的倍数。不妨设M是p的倍数，M=cp。由于M不是q的倍数，所以gcd(M,q)=1，则M(q)≡1modq，所以：[M(q)](p)≡1modq即M(n)≡1modq，即M(n)=1+kqM(n)=1+kq两边同乘以M=cp，则：M(n)+1=M+kqcp=M+kcn把kc看作一个常数，则：M(n)+1=M+tn即：M(n)+1≡Mmodn，即M(n)≡1modn因为ed=1mod(n)，所以：Med≡Mk(n)+1≡

M[M(n)]kmodn

≡M[1]kmodn

≡Mmodn综上,这样的e，d，n可以实现加密C=Memodn和解密M=Cdmodn密钥以n，e为公钥。秘密钥为d。(p,q不再需要，可以销毁。)RSA算法在计算上的可行性加密和解密无论是加密还是解密都需要计算某个整数的模n整数次幂，即C=Memodn、M=Cdmodn。但不需要先求出整数的幂再对n取模，而可利用模运算的性质：

(amodn)*(bmodn)=(a*b)modn对于Memodn，可先求出M1modn，M2modn，M4modn……，再求MemodnRSA算法在计算上的可行性产生密钥由于n是公开的，为了避免攻击者用穷举法求出p和q（根据n=pq），应该从足够大的集合中选取p和q，即p和q必须是大素数。目前还没有有效的方法可以产生任意大素数，通常使用的方法是：随机挑选一个期望大小的奇数，然后测试它是否是素数，若不是，则挑选下一个随机数直至检测到素数为止。RSA算法在计算上的可行性确定d和e有了p和q，可计算出(n)=(p－1)(q－1)根据gcd((n),e)=1来选择e，这一步计算量也不大，因为两个随机数互素的概率约为0.6有了e，再计算d=e-1mod(n)，这里用的是扩展的Euclid算法。选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确定满足d·e=1mod96且小于96的d，因为77×5=385=4×96+1，所以d为77。因此公开钥为{5，119}，秘密钥为{77，119}。设明文m=19，则由加密过程得密文为C=195mod119≡2476099mod119=66解密为6677mod119=19RSA的安全性RSA的安全性是基于分解大整数的困难性假定如果分解n=p×q，则立即获得(n)=(p－1)(q－1)，从而能够确定e的模(n)乘法逆dn的长度应该介于1024bit到2048bit之间由n直接求(n)等价于分解nRSA-129的故事

鹗鸟（ossifrage），又名髭兀鹰（lammergeier），是阿尔卑斯山上一种稀有的肉食秃鹰。它的翅膀展开将近十米宽。鸟名的字面含义是“碎骨”。顾名思义，其习性令人毛骨悚然。MirtinGardner在1977年“ScientificAmerican”的专栏文章中介绍了RSA码。为了显示这一技术的威力，RSA公司的研究人员用一个129位的数N和一个4位数e对这个关于秃鹰的消息作了编码。Gardner刊登了那个密文，同时给出了N和e。RSA公司还悬赏100美元，奖给第一个破译这密码的人。96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154一批松散组成的因子分解迷，大约有六百多人，分布在二十几个国家。他们经过八个月的努力最后于1994年4月为RSA-129找到了64位数和65位数两个素数因子。114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541=3490529510847650949147849619903898133417764638493387843990820577*32769132993266709549961988190834461413177642967992942539798288533“Themagicwordsaresqueamishossifrage”来自两个方面的威胁人类计算能力的不断提高分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分