5 RSA与基础公钥体制

现代密码学概论7/29/202610:57AM1主讲人：潘森杉第5讲RSA与公钥体制(PKC)非对称密码体制概述早期密码（如凯撒密码）：依赖于对整个加密过程的保密对称密码学（如DES和AES）：遵循Kerchoffs原则，公开算法的细节来公开验证这些密码的安全性，加密和解密中都用到了秘密。公钥密码学：把明文空间M中有意义的消息均匀的分布到整个空间消息C中去，不必运用任何秘密便可以得到这样的随机分布。在公钥密码中，加密不用秘密钥，秘密钥仅在解密中使用。对称密码的缺点1AliceBobEve对称密码的缺点2AliceDavidClairBobZach

公钥密码的优点AliceDavidClairBobZach

PKC的安全性easyeasyhard公钥和私钥1973年，英国密码学家Cocks构造了第一例公钥密码系统，基于大数分解并且本质上与RSA相同，遗憾的是加密算法被保密起来，直到1997年12月，英国政府通信服务与电子安全工作组(CESG)才公布Cocks算法1974年，Merkle发现了一种通过非对称计算来实现密钥协商的机制，称为Merkle难题，Merkle难题第一次实现了单向陷门函数，意味着密钥协商协议中搭线窃听者和合法使用者之间计算复杂度的差别，但是Merkle难题不适用于现代密码学(计算复杂度的非对称介于n和n2之间)1975年，Diffie和Hellman实现了“不用任何秘密就能加密”，1976年提出了几个可能的单向陷门函数，但是非对称性不好，不能用于公钥加密公钥密码学的历史1公钥密码学的历史21976年，Diffie和Hellman提出了模指数运算函数，用来演示了一个Diffie-Hellman密钥交换协议，该协议目前仍在被广泛地应用并在不断地发展中76年Diffie和Hellman发表了“密码学的新方向”，奠定了公钥密码学的基础78年，RSA算法PKI公钥技术是二十世纪最伟大的思想之一改变了密钥分发的方式可以广泛用于数字签名和身份认证服务公钥密码的基本思想涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换加密与解密由不同的密钥完成 加密:X

Y:Y=EKU(X)

解密:Y

X:X=DKR(Y)=DKR(EKU(X))从加密密钥得到解密密钥在计算上是不可行的加密与解密的顺序没有限制(不是必须的)

X=DKR(EKU(X))=EKU(DKR(X))若X=Y且映射E:X

Y是满射的,则

成立

EKU(X)=EKU(DKR(EKU(X)))若X=Y且为有限集合(例如分组密码),则E:X

Y是满射的,从而

成立如何设计一个公钥算法公钥和私钥必须相关，而且从公钥到私钥不可推断必须要找到一个难题，从一个方向走是容易的，从另一个方向走是困难的如何把这个难题跟加解密结合起来单向陷门函数单向陷门函数，是一个单向函数，即*对任意的，容易计算，而*对几乎所有的，求逆困难。但是*如果知道陷门信息t，则对所有的，容易计算满足的计算复杂性算法的计算时间和存储空间分别称为时间复杂度和空间复杂度，定义为输入算法的数据长度n的函数f(n).f(n)常用与其相同数量级的一个简单函数表示.如f(n)=O(g(n)):存在常数C,N，当n>N时，f(n)≤C|g(n)|.一般地，若f(n)=a0+a1n+…+aknk,ak≠0,则f(n)=O(nk).若算法的时间复杂度为T=O(nk)，称算法为多项式时间的；若算法的时间复杂度T=O(kf(n)),其中k是常数，f(n)是多项式，称该算法是指数时间的。称一个算法是有效的，是指该算法可在多项式时间内完成，此时称算法属于多项式类P。称算法是无效的，指不能在多项式时间内完成；但是给定一个结果可以在多项式时间验证，此时称算法属于NP。对于一个问题，存在多项式时间的算法可以解决，称该问题是P问题，也称计算上可行的；否则，称NP问题，也称计算上不可行的。在NP类中，有一部分可以证明比其他问题困难，这部分称为NPC问题。x、y分别为k位、l位二进制表示的正整数，即k=[lbx]+1,l=[lby]+1，假定k≥lx+yO(k)x-yO(k)xyO(kl)[x/y]O(l(k-l))(O(kl)为一个弱估计)gcd(x,y)O(k3)

（算法5.1，迭代次数为O(k)，每次执行一次长除法需时间O(k2)，则计算复杂度O(k3)，实际上是O(k2))Zn中，n为k比特整数，0≤m1,m2≤n-1。正整数cm1+m2modnO(k)m1-m2modnO(k)m1m2modnO(k2)m1-1modnO(k3)(m1)cmodnO((logc)×k2)如：参数生成中第2、3、4步，O((logn)2)公钥算法应用：保密数论基础Fermat定理:p素数,a是整数且不能被p整除,则:ap-1

1modp

(证明略)Euler数

(n)定义为小于n且与n互素的正整数个数p是素数,

(p)=p-1若n的因子分解为n=

Piai,ai>0,Pi互不相同,则(n)=Piai(1-1/Pi)若gcd(m,n)=1,则

(mn)=

(m)

(n),特别地,若p

q且都是素数,

(pq)=(p-1)(q-1)习题计算Euler函数(60)的值数论基础(续)Euler定理:若a与n为互素的正整数,则

a(n)

1modn推论:若n=pq,p

q都是素数,k是任意整数,则

mk(p-1)(q-1)+1

mmodn,对任意0

m

n原根(primitiveroot)Euler定理表明,对两个互素的整数a,n, a(n)

1modn定义：

存在最小正整数m

(n)(m|

(n)),使得

am

1modn 若对某个a,m=

(n),则称a是n的一个原根对于素数p,若a是p的一个原根,则:

a,a2,…,ap-1

关于p两两不同余,从而构成了p的非0剩余类,即与{1,2,…,(p-1)}关于模p等价.RSARSA的安全性RSA的安全性PrimefactorizationofnisthetrapdoorforcomputingdEuler’sTheoremEuler'stotientfunction加密解密RSA安全性基于数学的攻击公钥:KU={e,n},私钥:KR={d,n},n=pq分解n=pq

(n)=(p-1)(q-1)

d=e-1mod

(n)不求出p,q,直接求(n)

d=e-1mod

(n)不求出(n),直接计算d结论已知的方法至少跟因子分解一样难度尚未发现多项式时间的因子分解算法因子分解的算法已经取得了长足进步措施:选择足够大的n(1024位以上),并且使得e,d之间相差不太大,也不太小教科书式安全的不安全性RSA的安全假设是否成立——中间相遇攻击更具破坏性质的主动攻击——可证明安全生日攻击和随机预言机公钥密码系统需要更强的安全性RSA密钥产生产生两个素数由于n=pq是公开的，所以，为了防止攻击者利用n获得p和q，必须选择足够大的素数p和q大素数产生算法选择e或者d，然后求出另一个大素数产生素数生成过程:

随机选择一个奇数n(如通过伪随机数发生器)

随机选择a,使a<n

进行素性测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到

如果通过了足够次数的测试,认为n是素数,否则转到

.素数理论:在N附近，每ln(N)个整数中有一个素数素性检测生成大的“随机素数”：先生成大的随机整数，然后检测其素性。2002年，Agrawal等证明存在素性检测的多项式时间确定性算法。实际中，主要使用随机多项式时间MonteCarlo算法（Solovay-Strassen算法、Miller-Rabin算法）：可能将一个合数n断言为素数，但是多次运行，错误概率可降到任何期望值以下。检测多少个才能找到一个:

表示≤N的素数个数，则从1～N中随机取一个数，为素数的概率≈1/lnN如：从512比特整数中取为素数概率≈1/ln(2512)≈1/355即给355个512比特数，其中一个会是素数，因此生成素数实际可行判定问题：yes或no的问题随机算法：使用随机数的算法(否则称为确定性算法)定义：对一个判定问题的随机算法：如果“是”回答总是正确的，但“否”回答也许是不正确的，称为偏是的MonteCarlo算法（类似可定义偏否的MonteCarlo算法）.

错误概率ɛ：算法对任何回答应该为“是”的实例至多以ɛ的概率给一个不正确的回答“否”。注：LasVegas算法也许不给出回答，一旦回答总是正确的。

MonteCarlo算法总给出回答，但回答也许是不正确的。问题

合数(Composites)

实例：一个正整数n≥2

问题：n是一个合数吗？Solovay-Strassen算法是对合数问题的一个偏是的MonteCarlo算法，具有1/2的错误概率。Solovay-Strassen算法算法

Solovay-Strassen(n)随机选择整数a，1≤a≤n-1x←ifx=0

thenreturn(“niscomposite”)y←a(n-1)/2(modn)ifx≡y(modn)

thenreturn(“nisprime”)

elsereturn(“niscomposite”)此算法为偏是的MonteCarlo算法，具有1/2的错误概率。O((logn)3)时间内求a(n-1)/2(modn)可在多项式时间内算出，至多O(logn)次模约化，每次需时间O((logn)2)，算法5.6复杂度为O((logn)3)假定已生成随机数n，用Solovay-Strassen算法检测完素性。如果运行算法m次，n为素数的概率为1-1/2ma=“一个特定的随机奇整数n是合数”，b=“算法连续回答了m次‘n是一个素数’”，则Pr[b|a]≤2-mN≤n≤2N，N～2N中奇素数约为2N/ln2N-N/lnN≈N/lnN≈n/lnnPr(a)≈1-2/lnn=1-(n/lnn)/(n/2)Pr(a|b)实际中可取m=50或100，错误概率非常小素性测试Miller-Rabin算法：用来测试一个整数是否是素数WITNESS(a,n)

设bkbk-1…b0是(n-1)的二进制表示

d

1

forikdownto0

doxd