from gmpy2 import *
import libnum
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
e1 = 17
e2 = 65537
s = gcdext(e1, e2)
s1 = s[1]
s2 = -s[2]
c1 = libnum.s2n(open("./veryhardRSA/flag.enc1", 'rb').read())
c2 = libnum.s2n(open("./veryhardRSA/flag.enc2", 'rb').read())
c2 = invert(c2, n)
m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n
print libnum.n2s(m)
原理
引子
假設(shè)有一家公司COMPANY，在員工通信系統(tǒng)中用RSA加密消息健芭。COMPANY首先生成了兩個(gè)大質(zhì)數(shù)P,Q县钥，取得PQ乘積N。并且以N為模數(shù)慈迈，生成多對(duì)不同的公鑰及其相應(yīng)的私鑰若贮。COMPANY將所有公鑰公開。而不同的員工獲得自己的私鑰痒留，比如谴麦，員工A獲得了私鑰d1.員工B獲得了私鑰d2.
現(xiàn)在，COMPANY將一條相同的消息伸头，同時(shí)經(jīng)過所有公鑰加密细移，發(fā)送給所有員工。
此時(shí)熊锭，就可能出現(xiàn)共模攻擊弧轧。
共模攻擊
也稱同模攻擊，英文原名是 Common Modulus Attack 碗殷。
同模攻擊利用的大前提就是精绎，RSA體系在生成密鑰的過程中使用了相同的模數(shù)n。
我們依然以上面的案例展開锌妻。
假設(shè)COMPANY用所有公鑰加密了同一條信息M代乃，也就是
c1 = m^e1%n
c2 = m^e2%n
此時(shí)員工A擁有密鑰d1他可以通過
m = c1^d1%n
解密得到消息m
同時(shí)員工B擁有密鑰d2
他可以通過
m = c2^d2%n
解密得到消息m
如果，此時(shí)有一個(gè)攻擊者仿粹，同時(shí)監(jiān)聽了A和B接收到的密文c1,c2搁吓，因?yàn)槟?shù)不變，以及所有公鑰都是公開的吭历，那么利用同模攻擊堕仔，他就可以在不知道d1，d2的情況下解密得到消息m晌区。
又到了高數(shù)時(shí)間~
這里就是要論證摩骨，當(dāng)n不變的情況下，知道n,e1,e2,c1,c2 可以在不知道d1,d2的情況下朗若，解出m恼五。
首先假設(shè)，e1哭懈，e2互質(zhì)
即
gcd(e1,e2)=1
此時(shí)則有
e1*s1+e2*s2 = 1
式中灾馒，s1、s2皆為整數(shù)遣总，但是一正一負(fù)睬罗。
通過擴(kuò)展歐幾里德算法轨功，我們可以得到該式子的一組解（s1,s2），假設(shè)s1為正數(shù),s2為負(fù)數(shù).
因?yàn)?/p>
c1 = m^e1%n
c2 = m^e2%n
所以
(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n
根據(jù)模運(yùn)算性質(zhì)傅物，可以化簡(jiǎn)為
(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
也就是證明了命題：當(dāng)n不變的情況下，知道n,e1,e2,c1,c2 可以在不知道d1,d2情況下琉预，解出m董饰。
這里還有一個(gè)小問題，順帶說明下圆米。
我們知道解出來s2是為負(fù)數(shù)卒暂。
而在數(shù)論模運(yùn)算中，要求一個(gè)數(shù)的負(fù)數(shù)次冪娄帖，與常規(guī)方法并不一樣也祠。
比如此處要求c2的s2次冪，就要先計(jì)算c2的模反元素c2r近速，然后求c2r的-s2次冪诈嘿。
案例
n = 1022117
p = 1013
q = 1009
#936
fn = (p-1)*(q-1)
e = 17
d = 180017
m = int("h1".encode("hex"),16)
c1 = m**e%n
e1 = 5
d1 = 816077
c2 = m**e1%n
print n
print e
print e1
print c1
print c2
假設(shè)模數(shù)n固定為1022117，并且產(chǎn)生了（e,d）,(e1,d1)兩個(gè)密鑰對(duì)削葱。
并且打印出m加密后的密文c1,c2.
求通過e,e1,c1,c2解出m來奖亚。
以下是一個(gè)可供利用的腳本
#coding=utf-8
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def main():
n = int(raw_input("input n:"))
c1 = int(raw_input("input c1:"))
c2 = int(raw_input("input c2:"))
e1 = int(raw_input("input e1:"))
e2 = int(raw_input("input e2:"))
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1<0:
s1 = - s1
c1 = modinv(c1, n)
elif s2<0:
s2 = - s2
c2 = modinv(c2, n)
m = (c1**s1)*(c2**s2)%n
print m
if __name__ == '__main__':
main()
