5-2RSA密码原理及其应用

RSA密码背后的原理及其应用潘森杉计算机科学与通信工程学院，江苏大学密码学明确欧拉定理的意义能够使用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的数学组件

——单向陷门置换

单向性陷门单向陷门置换的问题选择