现代密码学概论（第2版）课件汇 潘森杉 5 RSA与公钥体制 -10 密码技术新应用

现代密码学概论7/29/202611:11AM1主讲人：潘森杉第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

d(dd)modn

if(d=1&x1&xn-1)returnTRUE

if(bi=1)thend(da)modn

if(d1)returnTRUE

elsereturnFALSE如果n不是素数，则返回FALSE的概率(即失败概率)小于0.5如返回TRUE，说明n不是素数。不满足an-1=amodn对于x2=1modn，除了1和n-1之外，还有别的解时间复杂度O((logn)3)，实际运行中，比Solovay-Strassen算法好定理Miller-Rabin算法对于合数问题是一个偏是的MonteCarlo算法。证:(反证)假设算法对素数n回答“n是合数”则am≠1modn算法中检测b的序列：am,a2m,…,由n为合数，n为素数，n-1=2km，由费马定理，是模n的1的平方根,对素数n仅两个模n的1的平方根±1modn从而类似的此时算法应回答“n是素数”，矛盾！RSA配置RSA配置RSA配置RSA配置文件加解密文件加解密RSA邮件加密RSA邮件加密RSA邮件加密RSA密码中的素数判定潘森杉计算机科学与通信工程学院，江苏大学密码学能说出公钥密码的优缺点认识和遵循密码方案参数设置规则能够使用Miller-Rabin判定大素数目录公钥密码的优缺点问题：为什么要用公钥密码来保护信息安全？目标：识别适用场景和意义公钥密码的优缺点

小艾小戴小蔡小鲍小张优点：1.安全密钥分发2.密钥管理开销小3.信息可验证私钥公钥公钥公钥公钥公开信道公开信道公开信道公开信道公开信道缺点：加解密速度比对称密码慢密钥长度较长公钥认证问题RSA核心应用场景

电子商务：HTTPS协议加密​应用方式：网站部署SSL/TLS证书，握手阶段用RSA交换会话密钥​实例：淘宝、京东等电商平台，用户输入的银行卡号、支付密码，通过RSA加密后传输，防止被窃取​关键价值：避免支付信息在传输中被篡改或泄露​数字签名：身份验证与防篡改​应用1：软件分发（如Windows系统、Adobe软件）​开发者用私钥对软件哈希值签名，用户用公钥验证——确认软件未被植入病毒​应用2：电子合同（如法大大、e签宝平台）​签约方用私钥签名，合同接收方用公钥验证——确保合同完整性、不可否认性​实例：企业远程签约劳动合同，通过RSA数字签名替代纸质盖章​VPN通信：企业远程安全访问​应用方式：企业搭建VPN时，用RSA加密VPN隧道内的数据​场景：员工居家办公访问公司内网（如财务系统、客户数据库）​实例：华为VPN、CiscoVPN设备，均集成RSA加密，防止内网数据被外部拦截​RSA算法的工作流程密钥生成加密解密玩具RSA算法加解密目标：能够演示如何配置并使用RSA算法加解密一串英文文本的过程

玩具RSA算法加解密(Python)#生成密钥对p=61q=53n=p*qphi_n=(p-1)*(q-1)e=17d=0while(d*e)%phi_n!=1:d+=1print(f"PublicKey(e,n):({e},{n})")print(f"PrivateKey(d,n):({d},{n})")#加密数据m=65#对应字母'A'c=(m**e)%nprint(f"EncryptedMessage:{c}")#解密数据decrypted_m=(c**d)%nprint(f"DecryptedMessage:{decrypted_m}")输出：PublicKey(e,n):(17,3233)PrivateKey(d,n):(2753,3233)EncryptedMessage:2790DecryptedMessage:65只有私钥(2753,3233)的拥有者才能解密方案建模——RSA算法的详细工作流程

RSA算法的安全性问题：密钥生成，即如何基于数学难题打造一把安全锁和对应的钥匙目标：认识到密码方案的参数设置对安全性的影响，并能够在遵循方案的设计准则下正确使用密码方案公钥n需要如何设置？#生成密钥对p=61q=53n=p*qphi_n=(p-1)*(q-1)e=17d=0while(d*e)%phi_n!=1:d+=1print(f"PublicKey(e,n):({e},{n})")print(f"PrivateKey(d,n):({d},{n})")问题：任何有p、q的人都能计算出私钥dRSA因子分解攻击2018AFCTF脆弱原因：

7983218175...43<623>

=

3133337

·

2547832606...39<617>步骤1）工具分解模数n得到p、q，例如2）通过欧拉定理、p、q求e的模逆元得到d3）解密并转换成字符串制作RSA锁壳n的设计图——素数问题：锁的安全级别需要设置多高才行？为什么？制作RSA锁壳的设计图——素数密钥n长度(bits)所需计算操作数(估算)破解所需时间(用现有硬件估算)1024~2⁸⁰已不再安全，已被专业机构淘汰2048

(当前标准)~2¹¹²即使用最强大的超级计算机，也需要数百万年3072~2¹²⁸比2048位安全级别高得多4096~2¹⁴⁴在可预见的未来（甚至量子计算机前）绝对安全指挥AI深挖专业知识：为什么n为2048时，破解RSA的计算操作约等于2¹¹²？动手任务1：请AI寻找大素数批判思考：如何判断AI没有忽悠你？打造“锁壳”：公开的模数n=p*q动手任务2：请AI计算大数乘法AI响应示例：(会输出一个更长的数字N)思考如何编程实现大数相乘拿到锁的人能恢复出设计图纸吗？为什么？核心原理：RSA的安全性基于一个数学事实：将两个大素数相乘很容易，但将其乘积分解还原为原来的两个素数极其困难。拓展：借助AI类比不同公钥密码方案的联系核心数学难题大整数质因数分解

n=p*q椭圆曲线离散对数问题(ECDLP)

Q=k*P格上最短向量问题(SVP)/差错学习(LWE)

b=A*s+e打造“锁”(公钥)公开乘积

n

和指数

e公开曲线点

P

和乘积点

Q=k*P公开矩阵

A

和结果向量

b=A*s+e打磨“钥匙”(私钥)保密质因数

p

和

q，或模逆元

d保密倍数

k保密秘密向量

s

和小误差

e“正向容易”计算大数乘法

p*q

很容易计算标量乘法

k*P

很容易计算矩阵乘法

A*s+e

很容易“逆向困难”从

n

分解出

p

和

q

极难从

P

和

Q

求出

k

极难从

A

和

b

求出

s

和

e

极难“陷门”作用知道

p

和

q

就能轻松计算

d知道

k

就能轻松完成解密运算知道

s

和

e

就能轻松纠正误差完成解密优势理解直观，应用广泛效率高：相同安全强度下，密钥比RSA短得多抗量子计算：被认为能抵抗量子计算机的攻击生成大素数的步骤制作RSA锁壳的设计图——素数素性判定方法平方差检验

检测合数的方法Fermat定理如果p是素数，那么对于任意整数a，有a^(p-1)≡1(modp)。思考：如何运用该定理检测合数？122≡22(mod35)，12≢±2(mod35)，35是一个合数，gcd(12-2,35)=5是35的一个非平凡因子例素性判定与因子分解的难度不一样复杂度为O(log(n))，比因子分解容易

例

定义Fermat定理素性判定的缺陷Fermat定理不能100%确定一个数是素数

最小的Fermat伪素数341，2^340mod  341=1但341=11×31。例Miller-Rabin素数判定步骤算法效率

概述概率性算法基于费马小定理和二次探测定理，通过多次随机测试来提高判定结果的准确性。030201分解

n−1随机选择基底a测试基底

a结果判定

Miller-Rabin素数判定测试

n=25

是否为素数误判原因算法中使用的a是随机的改进方法Miller-Rabin测试中的误判问题*增加测试的轮数*选择更大的随机数种子0102确定性算法AKS素性判定，多项式时间03定理：若a是随机选取的，则Miller-Rabin判定将合数当成素数的概率不超过1/4。AI类比不同素数测试的区别：

性能上的微小代价，换来了安全性的巨大提升特性费马素数测试米勒-拉宾素数测试理论基础费马小定理费马小定理+二次探测定理确定性概率性概率性错误类型合数被误判为素数（伪素数）合数被误判为素数（强伪素数）错误率（单次随机测试）较高。存在大量的卡迈克尔数，能通过所有基数的费马测试。极低。对任意合数，至少75%的基数会证明其是合数。实际错误率不可接受。无法可靠地排除卡迈克尔数。可接受。经过少量迭代（如5-10次），误判概率可忽略不计（如<1e-60）。计算步骤模幂运算：an−1 mod nan−1modn模幂运算+零到多次的平方模运算单次测试计算量略低略高（因为额外的平方检验步骤）实际性能差异差异极小。额外的平方检验在计算总量中占比很小，因为主要开销都在大数模幂运算上。安全性不安全，已被淘汰。无法有效检测出卡迈克尔数，攻击者可能利用此构造易分解的n。安全，行业标准。没有已知的类似卡迈克尔数的“漏洞”。主要缺陷卡迈克尔数（如561,1105,1729...）无已知重大缺陷

Miller-Rabin素数判定测试

n=561

是否为素数?费马测试仅在基数a是561的因子时才能成功RSA因子分解攻击

n=20499421483319837632829005665244953604816631094131482091599739242452461959670789327098587429656441009883765163931516947567316643569963621519243386576155541991650610105070387440479691299670503655019032377026089584152047162143622592606512093871068907193787013919967475201572411584456318069752118161110853731611597336602111728937901380008855876406951363681839727114631417566905375167058609392654378267988132283758536576123045237315624774544667706040426027925497245266590365080287798629911056879889563806490213919247917120199512548392006107613124668838850719777385822083736801474373012496703900585089950184532462833403107e=65537c=20032571908334556518706996350628353762857932090373933681400888944312785947661616694094701195862850761910097168558675875627215052773260832659893374127927598227236026530897152252167201800939030104214536327304912430809760264428512032937328302608592176040184547483423711571171744055968148657366655074788139832543212184924191715976191905198701170693941252097895416146372351355392205316913304672023350664554170422353392751177640905416228502429781714418077926868264124293539349931619123485098501005249806829896270239835682082818035333364506995823621010867979820662847712684534266471691343787498430152750115780889521627965005素数p和q的选择要求1长度足够大：当前标准要求p和q至少为1024位

（对应n为2048位）2|p-q|应该足够大，避免费马分解法攻击…自行设计密码方案的风险极大，请勿模仿专业人士调研：RSA的参数设置还有什么要求？小结能说出公钥密码的优缺点认识和遵循密码方案参数设置规则能够使用Miller-Rabin判定大素数谢谢您的观看THANKSRSA密码背后的原理及其应用潘森杉计算机科学与通信工程学院，江苏大学密码学明确欧拉定理的意义能够使用EEA求解私钥能够使用CRT加速解密能展示教科书RSA算法加解密过程能够辨析RSA背后的困难问题能够表述密码学基本安全模型的含义能够区分单向陷门置换与公钥加密方案能够运用标准RSA-OAEP加密目录欧拉定理在RSA中的意义目标：明确欧拉定理的贡献，能够使用EEA计算解密密钥方案建模——RSA算法的工作原理

欧拉φ函数RSA是单向陷门置换制作锁芯钥匙的设计图φ(n)欧拉函数φ(n)——连接公开与私密的桥梁原理：欧拉函数

φ(n)

表示小于n且与n互质的正整数的个数。对于一个由两个素数相乘得到的数

n=p*q，存在一个优美公式：φ(n)=(p-1)(q-1)。欧拉定理：如果整数a与n互质，则

a^φ(n)≡1(modn)。设计图φ(n)是算法的“心脏”，必须保密知识对比

欧拉φ函数为什么下述定理是正确的？

欧拉φ函数如何计算私钥d#生成密钥对p=61q=53n=p*qphi_n=(p-1)*(q-1)e=17d=0while(d*e)%phi_n!=1:d+=1print(f"PublicKey(e,n):({e},{n})")print(f"PrivateKey(d,n):({d},{n})")问题1：如果p、q很大，任何有p、q的人都能计算出私钥d？如何手工计算私钥d#生成密钥对p=61q=53n=p*qphi_n=(p-1)*(q-1)e=17d=0while(d*e)%phi_n!=1:d+=1print(f"PublicKey(e,n):({e},{n})")print(f"PrivateKey(d,n):({d},{n})")问题：任何有p、q的人都能计算出私钥d解题思路c≡c^(e*d)(modn)≡c^(kϕ(n)+1)(modn)，利用欧拉函数解ϕ(n)=(p-1)(q-1)利用EEA(扩展欧几里得算法)求私钥d，满足公式

e×d≡1(modϕ(n))

根据Bézout定理,一定存在整数d,k,使得d*e+kϕ(n)=1解一次同余方程：利用模逆元扩展欧几里得算法：求模逆元的主要方法它解决了什么问题？求解两个整数a和b的最大公约数。这是基础欧几里得算法（也称辗转相除法）的功能，扩展版自然也具备。寻找整数x和y，使得贝祖等式：ax+by=gcd(a,b)成立。求解线性同余方程：对于方程ax≡b(modm)，它可以转化为贝祖等式ax+my=b来求解。只有当gcd(a,m)能整除b时，方程才有解。计算模逆元本质上就是在求解贝祖等式！解一次同余方程：利用模逆元扩展欧几里得算法ax+by=gcd(a,b)就是贝祖等式，找到的整数解(x,y)称为贝祖系数。基本的欧几里得算法基于原理：gcd(a,b)=gcd(b,amodb)，不断递归直到余数为0。扩展欧几里得算法在每一步递归中，不仅计算最大公约数，还同时记录贝祖系数的变化。在基础的欧几里得算法（辗转相除法）中，可以通过不断地求商和余数来找到最大公约数。而在运用扩展欧几里得算法时，需要回溯一遍“拆”的过程，由1倒回到原系数，从而求得x和y。辗转相除法解一次同余方程：利用模逆元例题3：5x≡4(mod

13)d=gcd(5,13)=1，有唯一解。用扩展欧几里得算法求逆元：解5x+13y=1对13和5应用辗转相除法：13=5×2+3（余数是3）5=3×1+2（余数是2）3=2×1+1（余数是1）2=1×2+0（余数是0，结束）回溯求解系数：d=gcd（5，,13）=11=3-2×1代入（2=5-3×1），得1=3-(5-3×1)×1=3×2-5代入（3=13-5×2），得1=(13-5×2)×2-5整理得：1=-5×5+2×13对应可知：x=-5，y=2但x，y都应为正整数，故调整x=-5(mod13)=-5+13=8验证：5×8=40，40÷13=3余1，验证正确。所以5模13的逆元为8，接下来两边同乘逆元即可解：x≡8×4(mod13)≡6(mod13)。练习题求解2x≡3(mod5)求解4x≡6(mod10)求解12x≡9(mod15)系数2和模数5互质（gcd(2,5)=1），因此方程有唯一解观察可知：2×3=6≡1(mod5),2的逆元是3两边同乘逆元：x≡3×3(mod5)≡4(mod5)计算gcd(4,10)=2，且2整除6，因此方程有两个解两边同除d，得2x≡3(mod5)，正好是题目1，x≡4(mod5)模数为10，因此解为x≡4(mod10)和

x≡4+5=9(mod10)计算gcd(12,15)=3，且3整除9，因此方程有解，且有三个解两边同除d，得到

4x≡3(mod5)因为

4×4=16≡1(mod5)，所以逆元为4两边同乘逆元：x≡3×4(mod5)≡12(mod5)≡2(mod5)原模数为15，因此解为

x≡2(mod15)，

x≡2+5=7(mod15)，x≡2+10=12(mod15)由RSA密文、私钥恢复明文目标：能够演示RSA解密过程并优化习题：RSA算法中n=11413，e=7467，密文是5859，利用分解11413=101×113，求私钥。

习题：RSA算法中n=11413，e=7467，密文是5859，利用分解11413=101×113，求私钥。c≡c^(e*d)(modn)≡c^(kϕ(n)+1)(modn)，利用欧拉函数解ϕ(n)=(p-1)(q-1)利用EEA求私钥d，满足公式e×d≡1(modϕ(n))ϕ(n)=11200=7467×1+37337467=3733×2+11=7467-2*3733=7467-2*(11200-7467)=3*7467-2*11200

所以，d≡3(mod11200)，也就是d=3。根据Bézout定理,一定存在整数d,k,使得d*e+kϕ(n)=1习题：RSA算法中n=11413，e=7467，密文是5859，利用分解11413=101×113，求明文。c≡c^(e*d)(modn)≡c^(kϕ(n)+1)(modn)，利用欧拉函数解ϕ(n)利用EEA求私钥d，满足公式

d*e+kϕ(n)=1利用CRT化简m≡c^d(modn)为m≡a(modp),m≡b(modp)根据公式：m≡c^d(modn)。

将密文5859、私钥d=3和n=11413代入计算：

1415≡5859^3(mod11413)因为11413=101*113，5859=1(mod101)，5859≡96(mod113)=-17(mod113)5859^3≡1(mod101)，5859^3≡-289*17(mod113)≡-63*17(mod113)≡-3*(340+17)(mod113)≡-3*18(mod113)≡-54(mod113)≡59(mod113)根据中国剩余定理，我们需要找到一个数x，满足以下条件：x≡1(mod101)x≡59(mod113)习题：RSA算法中n=11413，e=7467，密文是5859，利用分解11413=101×113，求明文。c≡c^(e*d)(modn)≡c^(kϕ(n)+1)(modn)，利用欧拉函数解ϕ(n)利用EEA求私钥d，满足公式

e×d≡1(modϕ(n))利用CRT化简m≡c^d(modn)为m≡a(modp),m≡b(modp)利用EEA求p',q'，满足p*p'+q*q'=1计算m≡b*p*p'+a*q*q'(modn)x≡1(mod101)x≡59(mod113)113=101+12101=8*12+5

12=2*5+2

5=2*2+1因为1=5-2*2=5-2*(12-2*5)=5*5-2*12=5*(101-8*12)-2*12=5*101-42*12=5*101-42*(113-101)=47*101-42*113所以(113)^-1≡-42(mod101)≡59(mod101)，(101)^-1≡47(mod113)x≡1*113*59+59*101*47(mod11413)≡1415(mod11413)所以，明文为1415。q*q'≡1(modp)，p*p'≡1(modq)玩具RSA算法加解密(Python)#生成密钥对p=61q=53n=p*qphi_n=(p-1)*(q-1)e=17d=0while(d*e)%phi_n!=1:d+=1print(f"PublicKey(e,n):({e},{n})")print(f"PrivateKey(d,n):({d},{n})")#加密数据m=65#对应字母'A'c=(m**e)%nprint(f"EncryptedMessage:{c}")#解密数据decrypted_m=(c**d)%nprint(f"DecryptedMessage:{decrypted_m}")输出：PublicKey(e,n):(17,3233)PrivateKey(d,n):(2753,3233)EncryptedMessage:2790DecryptedMessage:65习题：如何快速求解密文2790对应的明文？大整数分解问题给定RSA公钥和密文，无法轻易求出明文，因模数n的两个素数不公开且分解大合数困难RSA问题RSA算法的安全基础不必分解模数n，也不必知道解密指数d，就能恢复出RSA对应的明文m，其被称为RSA问题。0102RSA算法挑战随着计算能力的提高，RSA算法的安全性受到挑战，建议使用至少2048比特的密钥长度来提高破解难度。03大整数分解问题和RSA问题哪个更难？RSA低加密指数攻击e=3,c=

3442467842482561323703237574537907554035337622762971103210557480050349359873041624336261782731509068910003360547049942482415036862904844600484976674423604861710166033558576921438068555951948966099658902606725292551952345193132973996288566246138708754810511646811362017769063041425115712305629748341207792305694590742066971202523405301561233341991037374101265623265332070787449332991792097090044761973705909217137119649091313457206589803479797894924402017273543719924849592070328396276760381501612934039653N=691316677109436623113422493782665795857921917893759942123087462879884062720557906429183155859597756890896192044003240821906332575292476160072039505771794531255542244123516929671277306361467074545720823735806308003091983427678300287709469582282466572230066580195227278214776280213722215953097747453437289734469454712426107967188109548966907237877840316009828476200388327329144783877033491238709954473809991152727333616022406517443130542713167206421787038596312975153165848625721911080561242646092299016802662913017071685740548699163836007474224715426587609549372289181977830092677128368806113131459831182390520942892670696447128631485606579943885812260640805756035377584155135770155915782120025116486061540105139339655722904721294629149025033066823599823964444620779259106176913478839370100891213072100063101232635183636552360952762838656307300621195248059253614745118852163569388418086291748805100175008658387803878200034840215506516715640621165661642177371863874586069524022258642915100615596032443145034847031564356671559179212705466145609698475546210994748949121359853094247990533075004393534565421776468785821261291309463205314057882016266066365636018084499158806717036972590848458891019171583268920180691221168453612029698510271RSA低加密指数攻击

RSA同模攻击(commonmodulusattack)结论1：无需大整数，也可能恢复RSA明文结论2：如果RSA被正确配置，RSA问题被认为和大整数分解问题一样困难如果没有设计图纸和钥匙，锁上的物品就安全了吗？

选择明文攻击是否不切实际？确定性加密

如果没有设计图纸和钥匙，锁上的物品就安全了吗？

高效的攻击者

概率性加密

选择明文攻击是否不切实际？1CPA-安全是密码方案的最低要求2CPA-安全需要概率性加密；确定性加密一定不是CPA-安全3攻击者有时是正义之士确定性加密

如果没有设计图纸和钥匙，锁上的物品就安全了吗？CCA(选择密文攻击)-安全

高效的攻击者

攻击者使用用户账号中间人攻击

如果攻击者能拿到多个锁上的物品，他对物品的安全性产生威胁吗？攻击者可以选择不同的“锁上物品”（密文）并尝试操作它们（如摇晃或敲击），以区分不同种类物品声音（即获取解密信息）。IND-CCA公钥密码的数学组件PKC的数学组件

——单向陷门置换

单向性陷门单向陷门置换的问题选择明文攻击RSA单向陷门置换是确定性算法，这意味着直接加密相同的明文，总是得到相同的密文。选择密文攻击攻击者可以选择密文c=E(m)⋅E(2)modn，然后请求解密c，解密结果将是m⋅2modn，攻击者可以通过除以2来推断出明文m。单向陷门置换的问题加密方案是一个系统：它不仅包含单向陷门函数，还包括了密钥管理、填充方案等。特性单向陷门置换加密方案本质一个基础的数学函数/原语一个完整的密码系统/协议核心功能提供单向性和陷门可逆性提供消息机密性确定性是，确定性的否，安全的方案必须是概率性的直接用途用作构建模块来创建加密、签名等方案直接用于加密数据输入/输出输入和输出通常是“无意义”的数字输入是明文，输出是密文安全性依赖依赖于某个数学难题不仅依赖于底层难题，还依赖于方案的设计例子RSA函数，Rabin函数RSA-OAEP,ElGamal加密单向陷门置换的问题RSA-OAEP概述RSA-OAEP(最佳非对称加密填充)填充过程生成填充字符串计算X=m'⊕G(r)；计算Y=r⊕H(X)；最终的填充字符串为P=X||Y。加密将填充后的字符串P作为明文，使用RSA公钥(e,n)进行加密，得到密文c=P^emodn。明文填充将明文m填充到一个固定长度的字符串m’。030201定理：当H、G为随机预言机时，如果RSA算法为单向陷门置换，那么RSA-OAEP是选择密文安全的。(研究)安全性小结明确欧拉定理的意义能够使用EEA求解私钥能够使用CRT加速解密能展示教科书RSA算法加解密过程能够辨析RSA背后的困难问题能够表述密码学基本安全模型的含义能够区分单向陷门置换与公钥加密方案能够运用标准RSA-OAEP加密谢谢您的观看THANKS现代密码学概论7/29/202611:11AM111主讲人：潘森杉第6讲离散对数与数字签名Merkle的背包(knapsack)问题0-1背包问题：给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程

S=∑aixi

的二进制向量X=(x1,…,xn)。这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长背包问题用于公钥密码学做法方法：明文为X，S为密文奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题公开密钥使用难解的背包问题私钥使用易解的背包问题易解的背包问题——超递增背包满足下列条件的背包 ai>∑aj(j=1,…,i-1)这样的背包也被称为简单背包求解从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包结果为{2,3,13,52}所以，密文70对应的明文为110101转换背包简单背包用作私钥如何产生相应的公钥——转换做法：选择一个整数m>∑ai(i=1,…,n)然后选择一个与m互素的整数w，然后

ai’=wai(modm)(i=1,…,n)这里的ai’是伪随机分布的这样得到的背包是非超递增背包基于背包问题的公钥密码系统

——MH公钥算法加密将明文分为长度为n的块X=(x1,…,xn)然后用公钥A’=(a1’,…,an’)，将明文变为密文S

S=E(X)=∑ai’xi解密先计算S’=w-1Smodm再求解简单背包问题S’=∑aixi背包密码系统的意义是第一个公钥密码系统有较好的理论价值在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷Diffie-Hellman密钥交换协议公钥用于密钥交换的一个显著的优点就是通信双方可以在无需安全信道的基础上进行密钥协商。Diffie和Hellman对Alice:对Bob:有限域Fp,p为素数，p-1的完全分解是知道的g为Fp*的生成元，[1,p)中每个元素都可以表示为gx(modp)注意到，这样双方计算得到的值是相同的。——为什么？例题的答案：执行Diffie-Hellman密钥交换协议应注意的问题共同的输入p应该是一个素数，或者素数的幂，满足p-1有足够大的因子p`，大于2160Alice和Bob应该验证ga和gb不等于1，这个验证将保证gab是Fpp`阶子群的一个元素。在通信结束后，应该立即删除a和b的值，这样将会拥有前向保密性质。共同输入g不必是Fp*的生成元,但应该是Fp*中一个高阶子群的生成元Diffie-Hellman密钥交换Alice和Bob确定两个大素数p和q，

这两个数不必保密，因此Alice和Bob可以用不安全信道确定这两个数。设p＝11，q＝72. Alice选择另一个大的随机数r₁，并计算：。设r₁＝3，则A＝73mod11＝23. Alice将A发送给Bob。4. Bob选择另一个大的随机数r₂，并计算：设r2＝6，则B＝76mod11＝45. Bob将B发送给Alice。6. Alice计算密钥：k₁＝43mod11＝97. Bob计算密钥:k2＝26mod11＝9中间人攻击

——处于A、B通信中间的主动攻击者能够利用协议的消息以达到成功的攻击中间人攻击图示类似的，Malice可以伪装成Bob，并同Alice协商另一个密钥gam，然后在两人之间转发“保密”通信。攻击存在的原因：没有进行消息源的认证服务。Diffie-Hellman密钥交换的攻击replay攻击中间人攻击图示ABK=rxyEABK=rxzEK=ryzDiffie-Hellman问题和离散对数问题原理：因为离散对数问题是困难的，所以DHC问题是单向的。ElGamal密码体制问题

离散对数

实例：乘法群(G,·)，一个n阶元素

∈G，∈<

>

问题：找到唯一整数a，1≤a≤n-1满足：

a=

整数a记为log

，称为

的离散对数。性质：求解离散对数(可能)是困难的，指数运算可以应用平方-乘算法有效计算，即：指数运算是单向函数。TaherElGamal密码体制

Zp*上的ElGamal公钥密码体制素数p，使得(Zp*,·)上的离散对数问题是难处理的，令∈Zp*是一个本原元令P=Zp*,C=Zp*×Zp*,定义K={(p,

,a,):

≡

a

(modp)}p,

,是公钥，a是私钥。对K=(p,

,a,),及一个(秘密)随机数k∈Zp-1,定义eK(x,k)=(y1,y2)其中：y1=

k

modpy2=x

k

modp对y1,y2∈Zp*，定义dK(y1,y2)=y2(y1a)

-1modp注：x通过乘以

k伪装，产生y2，

k也作为密文的一部分传送，Alice随机选k，Bob知道a，可从

k计算出

k(=

ak=(

k)a)，用y2除以

k去伪装，得到x.例：p=2579，

=2为Zp*本原元令a=765，=2756mod2579=949Alice:x=1299,随机选择k=853y1=2853mod2579y2=1299×949853mod2579=2396发送密文y=(y1，y2)=(435,2396)给BobBob收到密文y=(435,2396)

x=2396×(435765)-1mod2579=1299如果Oscar可计算a=log

，则ElGamal密码体制不安全。一般地，p至少取300位十进制数，p-1具有至少一个较大的素因子。离散对数问题的算法乘法群(G,·),

∈G，ord(

)=n，给定∈<

>,找出唯一的指数a=log

，使得a=

假定计算G中两元素乘积需常数（O(1)）时间通过O(n)时间和O(1)存储空间穷举搜索计算，2，…，直到发现=

a预计算所有可能的值i，并对(i,

i

)以第二个坐标排序列表。给定，对存储的列表执行一个二分查找，直到找到a使得a=

(需O(n)时间与计算的n个幂，O(nlogn)时间对n个元素排序，近似为O(n)，二分查找时间为O(logn)，忽略对数因子项，得：用O(1)时间，O(n)步预计算和O(n)存储空间)Shanks算法算法

SHANKS(G,n,,)m←[n1/2]+1forj←0tom-1

do

计算mj

对m个(j,

mj)关于第二个坐标排序，得到列表L1fori←0tom-1

do

计算-i对m个(i,

-i)关于第二个坐标排序，得到列表L2找(j,y)∈L1和(i,y)∈L2log

←(mj+i)modn由(j,y)∈L1和(i,y)∈L2，得

mj=y=

-i

mj+i=

log

=mj+i,0≤i,j≤m-1运行时间O(m)，存储空间O(m)，是一个时间-存储折中算法O(m)O(mlogm)O(m)O(m)O(mlogm)Pollard

离散对数算法划分G=S1∪S2∪S3,元素个数大致相同。定义f:<

>×Zn×Zn→<

>×Zn×Zn如果gcd(b2i-bi,n)=1,c=(ai-a2i)(b2i-bi)-1modn算法

Pollard

离散对数算法(G,n,,)proceduref(x,a,b)ifx∈S1

thenf←(x,a,(b+1)modn)

elseifx∈S2

thenf←(x2,2amodn,2bmodn)

elsef←(x,(a+1)modn,b)return(f)main定义划分G=S1∪S2∪S3(x,a,b)←f(1,0,0)(x’,a’,b’)←f(x,a,b)whilex≠x’

do(x,a,b)←f(x,a,b)(x’,a’,b’)←f(x’,a’,b’)(x’,a’,b’)←f(x’,a’,b’)ifgcd(b’-b,n)≠1

thenreturn(“failure”)

elsereturn(“(a-a’)(b’-b)-1modn”)gcd(b’-b,n)=d>1c(b’-b)≡a-a’(modn)有d个解，假如d不是很大，可直接算出d个解并检验哪个是正确的期望在O(n1/2)次迭代计算离散对数Pohlig-Hellman算法=a,a=log

，

的阶为n=∏pici,计算出每个i对应的amodpic，然后用CRT计算出amodnn≡0(modqc),n≠0(modqc+1),q素数，求x=amodqc

记x=a0+a1q+…+ac-1qc-1,a=x+sqc1.计算a0：

n/q=a0n/q计算r=n/q,r2,…,直到某个i≤q-1:ri=n/q,则a0=i2.c=1,则x=a0;c>1,确定a0，a1，…，ac-1记

0=，算法

Pohlig-Hellmen(G,n,,,q.c)j←0

j←whilej≤c-1

do←

找到满足=in/q的i

aj←i

j+1←j←j+1return(a0,a1,…,ac-1)算法计算复杂度为O(c·q1/2)指数演算法Zp*,因子基B={p1,p2,…,pb}计算这b个素数的离散对数；利用这些离散对数，计算所要求的离散对数。c稍大于b(如c=b+10),构造c个模p的同余方程：给定b个未知量log

pi的c个同余方程，希望存在模p-1下的唯一解，于是可得因子基元素的离散对数。随机取x,计算

xmodp，确定是否xmodp的所有因子在B中。利用LasVegas随机算法计算:选随机数s,1≤s≤p-1,计算r=

smodp试图在B上分解r，如果成功，得同余方程例：p=10007,=5为本原元，作为模p的离散对数的基取B={2,3,5,7},log55=1x=4063:54063mod10007=42=2×3×7

log52+log53+log57≡4063(mod10006)x=5136:55136mod10007=54=2×33

log52+3log53+log57≡5136(mod10006)x=9865:59865mod10007=189=33×7

3log53+log57≡9865(mod10006)log52=6578,log53=6109,log57=1301求log59451:

随机取s=77369541×57736mod10007=8400=24×3×52×7在B上完全分解log59451=4log52+log53+2log55+log57-7736mod10006=6057预计算O(e(1+O(1))(lnplnlnp)^1/2),计算O(e(1/2+O(1))(lnplnlnp)^1/2)公钥加密的实用性LOGO公钥加密的实用性LOGO公钥加密的实用性LOGOLOGO公钥加密的实用性LOGO公钥加密的实用性LOGORSA编码RSA解码数字签名数字签名的实用性纸质签名的缺点民间借贷纠纷案件：甲方说，这是张“借条”；乙方说，自己只在纸上留了个名字和电话号码，其余是对方写