RSA算法能正确加解密的前提之一，是作为加密钥的需要与互素。为什么此条件要严格满足呢？如果不满足会有什么问题？特殊情形下的RSA又该如何求解？
1 RSA with gcd(e,phi)=1
1.1 RSA算法回顾
令是两个位数相近的大素数的乘积。取两个整数，满足,其中。即为公钥，即为私钥。
加密的操作是：，解密的操作则是。
1.2 RSA加密原理
由欧拉定理：
可得
存在逆元的充要条件
证明：是的充要条件
充分性：
由,由裴蜀定理：存在整数，使得
上式可化为，得证
必要性：
假设x是a对于b的乘法逆元，则有 , 即是方程 的一个整数解。 但是形如$
ax + by gcd(a,b)gcd(a,b)=1$时，a才有对于b的乘法逆元。
因此，在RSA算法中，对任意，存在的充要条件是：
2 RSA with gcd(e,phi)≠1
2.1 题目
1
2
3
4
5
6
7
8
9
10
| p4=146068806215073497344459876631371603884129554507314987227041386431864296983800292232765852493230146632246223391161616274352995602128509562953556195654254929572680238155614318159006433172894208760309766144817665852858474274746295434459658946786114485553768622540321693696983334739989582184316792317376817587284066141025953893816735983622448994863347051427279673308801466174898201800602688359956097373676655607179834345973775227535147398518523539179261883968140504230643073698857288314127486345168652339309386405706576632120711116391426300160476076254612138216623537070845645803721685414583459545099925250474009703135469241079408739336592005949980987466671054020054633554508243871664072158338203090563533576053886607251476483441992750608537110739543678599105838456537686029895264928334606913181627024815548789841726411333636163152202116487198575625907392074866811580053962217284776220330628233642351622897902940633662074194963147661868086182955886918339487179905557899816215131118989868243555958033477834658657082003718410617182774845820310639577794302769424451100567749840744304334325501306470124397022077759031911677326433654909824518845224227308515695216456907499080502091628962571645468099748573164070147303131348996440422701533681
q1 = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
p=gp.iroot(p4,4)[0]
n1=p*q1
n2=p*q2
e1 = 15218928658178
e2 = 381791429275130
c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
|
2.2 分析
本题实质就是解同余方程组：
本题难点在于用于加密的。因此，攻击的思想就是找到使得。
由gcd(e1,(p-1)*(q1-1))=14可得，于是原方程组可化为：
由RSA解密思想，这里令，则有
理论上，接下来的步骤十分明确：M可以通过中国剩余定理求解，但在求解过程中报错：不存在逆元。
所以需要更换一下思路。由同余式的性质，方程还可以写作： 其中，②④式的模数为质数，对两式做中国剩余定理，即可求出，令其为。
对于求，可以使用类似的方法。考虑到，等式可化为 由，求解同样可以由RSA的解密思想，求出7模的逆元，然后就能求解出，再对其开平方，就是正确的了。
2.3 求解
1
2
3
4
5
6
7
8
9
10
| d1=gp.invert(e1//14,(p-1)*(q1-1))
d2=gp.invert(e2//14,(p-1)*(q2-1))
c=[gp.powmod(c1,d1,q1),gp.powmod(c2,d2,q2)]
n=[q1,q2]
m14=CRT(c,n)
d=gp.invert(7,(q1-1)*(q2-1))
m2=gp.powmod(m14,d,q1*q2)
m=gp.iroot(m2,2)[0]
print(long_to_bytes(m))
|
2.4 攻击思想总结
对于不满足e与phi互素的RSA，考虑对同余式做进一步变换，使e中的一个因数（最直接的做法是）与phi互素，分多部求解。