RSA共模攻击(包括原理)

RSA工作原理

RSA的工作原理，RSA涉及的几个参数
明文=>m 
密文=>c
模n，负责计算出两个质数p和q  p和q计算欧拉函数值Φ(n)欧拉函数Φ(n)=>Φ(n)=(p-1)*(q-1)
公钥参数e和私钥参数d，可由欧拉函数计算出  ed ≡ 1(mod Φ(n))
加密=> m^e≡c(mod n)
解密=> c^d ≡m(mod n)

模攻击
共模是指：就是明文m,相同。用两个公钥e1,e2加密得到两个私钥d1,d2 和两个密文c1,c2
共模攻击，即当m不变的情况下，知道n,e1,e2,c1,c2, 可以在不知道d1,d2的情况下，解出m
利用条件为=> gcd(e1,e2)=1

根据扩展欧几里得 算法得
可以得到该式子的一组解(s1,s2) 假设s1为正数，s2为负数
有整数s1,s2(一正一负)
存在e1s1+e2s2==1

加密过程
C=m^e mod n
C=pow(m,e,n)
解密过程
M=c^d mod n
M=pow(c,d,n)

m=(pow(c1,s1,n)pow(c2,s2,n))%n
=>(c1s1%nc2s2%n)%n=m

∵gcd(e1,e2)1,∴由扩展欧几里得算法，存在e1s1+e2s21
∴mm1==m(e1s1+e2s2)((me1)s1)((me2)s2)==(c1s1)(c2s2)

数学原理

这里我用三种数学原理来进行说明
第一种：

证明:m=(c1^s1)*(c2^s2)
带入 c1 = m^e1%n   c2 = m^e2%n  两个公式计算(c1^s1)*(c2^s2)%n=((m^e1%n)^s1*(m^e2%n)^s2)%n
=>(c1^s1)*(c2^s2)%n=((m^e1%n)^s1%n*(m^e2%n)^s2%n)%n    #(a*b)%n=(a%n*b%n)%n
=>(c1^s1)*(c2^s2)%n=((m^e1)^s1%n*(m^e2)^s2%n)%n    #a^b%n=((a%n)^b)%n     a=(m^e1)^s1   b=(m^e2)^s2
=>(c1^s1)*(c2^s2)%n=((m^e1)^s1*(m^e2)^s2)%n        #((a%p)*(b%p))%p=(a^b)%p
=>(c1^s1)*(c2^s2)%n=((m^(e1*^s1)*(m^(e2*^s2))%n    #幂的乘方，底数不变，指数想乘
=>(c1^s1)*(c2^s2)%n=((m^(e1*^s1+e2*^s2))%n
因为e1*s1+e2*s2=1得：(c1^s1)*(c2^s2)%n=(m^(1)%n(c1^s1)*(c2^s2)%n=m%n(c1^s1)*(c2^s2)=m    #根据等式性质

第二种：

因为gcd(e1,e2)=1
根据扩展欧几里得得到 e1*s1+e2*s2=1    s1,s2中一正一负，设s1为正，s2为负
c1 = m^e1%n   c2 = m^e2%n(c1^s1)*(c2^s2)%n=((m^e1%n)^s1*(m^e2%n)^s2)%n
=>(c1^s1)*(c2^s2)%n=((m^e1)^s1*(m^e2)^s2)%n       #(a*b)%n=(a%n*b%n)%n
=>(c1^s1)*(c2^s2)%n=(m^(e1^s1+e2^s2))%n              #同底数幂
=>(c1^s1)*(c2^s2)%n=(m^(1))%n    e1*s1+e2*s2=1=>(c1^s1)*(c2^s2)%n=m%n
=>(c1^s1)*(c2^s2)=m
可得m=(c1^s1)*(c2^s2)%n

第三种：

gcd(e1,e2)=1
e1*s1+e2*s2=1
m
=>m^1=>m(e1*s1+e2*s2)=>((m^e1)^s1*(m^e2)^s2)=>(c1^s1)*(c2^s2)根据模运算性质(a*b)%n=(a%n*b%n)%n
a^b%n=((a%n)^b)%n((a%p)*(b%p))%p=(a^b)%p

出题脚本：

import libnum
import gmpy2
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e1=2333
e2=23333
m="flag{6ed4c74e022cb18c8039e96de93aa9ce}"
m=libnum.s2n(m)
n=p*q
c1=pow(m,e1,n)
c2=pow(m,e2,n)print("n1=",n)print("e1=",e1)print("c1=",c1)print("n2=",n)print("e2=",e2)

解题脚本：

n1=13275539468515927122668657418826962202430467408860484765898568663156503527396473586233806355289560759234484646820604878130245116609025833260834734249490247181739187091798406386899992249647283296098046635078998806241008947511489965043592342640904960118547695431908152475613663532406184101144164645776485026634520190801390504479902674438381031902988558383334546358843335032069110257941561153526273905221509504939058454345020402752203190691148266740216247933791900283468212865430165408235093857626104437061213452413564723765040442767798563232901124229044449065445046888956215682366228655047929453110805914555163635510419
e1=2333
c1=12839285960223495540837529365339640783021439899108155136321855396508597591195084834231690640732914408618285996134049202996422114737474822115945692760871458165554118169402663520900701296114704740122786806542520699905862239914946533647899715822828542560800418499031431014437887839597676472165537391472198221714363610491291038442463223575122912669355380941374075599322428985304893846875110708290551186273543362765115647684956793570841630280930991407077401574158296542671529832884549202417721050055128956160795181219321381962644469613816746657814407025821523489911167830470453075666809891234756979759785607614579837734082
n2=13275539468515927122668657418826962202430467408860484765898568663156503527396473586233806355289560759234484646820604878130245116609025833260834734249490247181739187091798406386899992249647283296098046635078998806241008947511489965043592342640904960118547695431908152475613663532406184101144164645776485026634520190801390504479902674438381031902988558383334546358843335032069110257941561153526273905221509504939058454345020402752203190691148266740216247933791900283468212865430165408235093857626104437061213452413564723765040442767798563232901124229044449065445046888956215682366228655047929453110805914555163635510419
e2=23333
c2=3354756678232940495821979239801458007420410531822100812188898131516917749604851255269716527378343349516173106916414335163414268865824921119788877047553519631159949070051858008087712664995111487663781337726742683963116894637201549928831686056701870685405950856250977197910095810076403861881931015074416123490624856112462001350590171001296114611866177706693234039596982711256182797885834942186618425452535848339326240931859796433390218112045498069663580377366715346261942151557866185723732917427377138450852758541378023643134160677508933773941402646042004431292764888647202090679358894168736017515947373729257142729574import gmpy2
import libnum
s,s1,s2=gmpy2.gcdext(e1,e2)
m=(pow(c1,s1,n1)*pow(c2,s2,n2))%n1   => ∵m=(c1^s1)*(c2^s2)print(libnum.n2s(int(m)).decode())