本文參考https://findneo.github.io/180727rsa-attack/ 為對(duì)其知識(shí)進(jìn)行掌握筹淫，寫此文章來梳理和加深記憶
前言：理解基本概念，本文將每種攻擊方式實(shí)現(xiàn)方法提煉成了一個(gè)函數(shù)呢撞，便于理解原理也可以直接調(diào)用贸街。
基礎(chǔ)：
RSA概要：
在開始前可以通過 《RSA算法詳解》 這篇文章了解關(guān)于RSA的基礎(chǔ)知識(shí)，包括加解密方法狸相，算法原理和可行性證明等薛匪。（特詳細(xì)）
應(yīng)用流程：
1.選取兩個(gè)較大的互不相等的質(zhì)數(shù)p和q 計(jì)算n =pq。
2.計(jì)算phi =（p-1）（q-1）脓鹃。
3.選取任意的e逸尖，使得e滿足1<e<phi 且 gcd(e,phi) ==1 .
4.計(jì)算e關(guān)于phi的模逆元d，即d滿足（e*d）%phi ==1.
5.加解密：c=(m^e)%n ,m =(c^d)%n.其中m為明文，c為密文 （n,e）為公鑰娇跟，d為私鑰岩齿，要求0<=m<n.
求模逆可直接利用gmpy2庫。如import gmpy2 print gmpy2.invert(47,30)可求得47模30的逆為23苞俘。
擴(kuò)展歐幾里得算法基于歐幾里得算法盹沈，能夠求出使得 ax+by=gcd(a,b) 的一組x,y。
常見攻擊方式實(shí)踐
準(zhǔn)備工具
python gmpy2庫 libnum庫
yafu
RSATool2v17.exe
RSA解密
若已知私鑰d吃谣，則可以直接解密：m=pow(c,d,n).
若已知質(zhì)數(shù)p和q,則通過依次計(jì)算歐拉函數(shù)值phi乞封、私鑰d可解密。簡易實(shí)現(xiàn)如下：
phi = (p - 1) * (q - 1)
n = p * q
try:
d = gmpy2.invert(e, phi) #求e模phi的逆
return pow(c, d, n)
except Exception as e:
print "e and phi are not coprime!"
raise e
在選取加密指數(shù)e時(shí)要求phi岗憋，e互質(zhì)肃晚，也就是gcd(phi,e)==1 ，如果不滿足是無法直接解密的仔戈。
SCTF2018的Crypto - a number problem关串，題目是：x**33=1926041757553905692219721422025224638913707 mod 3436415358139016629092568198745009225773259 tell me the smallest answer of x
其中n=3436415358139016629092568198745009225773259 可以直接分解得到p,q，出phi=(p-1)*(q-1) 监徘，然后驚奇地發(fā)現(xiàn)gcd(phi,33)==3 晋修。這時(shí)如果對(duì)加密過程比較熟悉的話，就可以想到實(shí)際上公鑰e=11 凰盔，明文是m=x^3 飞蚓，應(yīng)該先求出m。然后再爆破x廊蜒。
圖片.png
使用yafu分解N
適用情況：p,q相差較大或較小時(shí)可快速分解趴拧。
使用方法：
yafu-x64.exe factor(233) ，yafu-x64.exe help模不互素gcd(N1,N2)!=1
多個(gè)模數(shù)n共用質(zhì)數(shù)山叮，則可以很容易利用歐幾里得算法求得他們的質(zhì)因數(shù)之一gcd(N1,N2) 著榴，然后這個(gè)最大公約數(shù)可用于分解模數(shù)分別得到對(duì)應(yīng)的p和q，即可進(jìn)行解密屁倔。實(shí)現(xiàn)參照本文歐幾里得算法 部分和RSA解密 部分脑又。
共模攻擊
適用情況：明文m、模數(shù)n相同锐借，公鑰指數(shù)e问麸、密文c不同，gcd(e1,e2)==1
對(duì)同一明文的多次加密使用相同的模數(shù)和不同的公鑰指數(shù)可能導(dǎo)致共模攻擊钞翔。簡單證明見代碼注釋严卖。
Python實(shí)現(xiàn)：
def common_modulus(n, e1, e2, c1, c2): """ ref: https://crypto.stackexchange.com/questions/16283/how-to-use-common-modulus-attack ∵gcd(e1,e2)==1,∴由擴(kuò)展歐幾里得算法，存在e1*s1+e2*s2==1 ∴m==m^1==m^(e1*s1+e2*s2)==((m^e1)^s1)*((m^e2)^s2)==(c1^s1)*(c2^s2) """ assert (libnum.gcd(e1, e2) == 1) _, s1, s2 = gmpy2.gcdext(e1, e2) # 若s1<0布轿，則c1^s1==(c1^-1)^(-s1)哮笆，其中c1^-1為c1模n的逆元来颤。 m = pow(c1, s1, n) if s1 > 0 else pow(gmpy2.invert(c1, n), -s1, n) m *= pow(c2, s2, n) if s2 > 0 else pow(gmpy2.invert(c2, n), -s2, n) return m % n例子：QCTF2018-XMan選拔賽 / Xman-RSA 【共模攻擊+模不互素】這道題利用了共模攻擊和模不互素。剛開始是一個(gè)字符替換稠肘，與本文無關(guān)福铅。encryption.encrypted文件被做了字符替換，根據(jù)語法確定替換表项阴，修復(fù)文件得到源文件如下滑黔。
from os import urandom
import base64
def bytes_to_num(b):
return int(b.encode('hex'), 16)
def num_to_bytes(n):
b = hex(n)[2:-1]
b = '0' + b if len(b) % 2 == 1 else b
return b.decode('hex')
def get_a_prime(l):
random_seed = urandom(l)
num = bytes_to_num(random_seed)
while True:
if is_prime(num):
break
num += 1
return num
def encrypt(s, e, n):
p = bytes_to_num(s)
p = pow(p, e, n)
return num_to_bytes(p).encode('hex')
def separate(n):
p = n % 4
t = (p * p) % 4
return t == 1
f = open('flag.txt', 'r')
flag = f.read()
msg1 = ""
msg2 = ""
for i in range(len(flag)):
if separate(i):
msg2 += flag[i]
else:
msg1 += flag[i]
p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1 * p2
n2 = p1 * p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)
e1 = 0x1001
e2 = 0x101
p4 = get_a_prime(128)
p5 = get_a_prime(128)
n3 = p4 * p5
c1 = num_to_bytes(pow(n1, e1, n3)).encode('hex')
c2 = num_to_bytes(pow(n1, e2, n3)).encode('hex')
print(c1)
print(c2)
print(base64.b64encode(num_to_bytes(n2)))
print(base64.b64encode(num_to_bytes(n3)))
n2，n3已知环揽，利用共模攻擊得到n1略荡，由gcd(n1,n2)==p1 分解n1，n2薯演，就可解密得到兩部分msg撞芍，拼接即可秧了。
# by https://findneo.github.io/
import base64
import libnum
import gmpy2
def fix_py():
# decode encryption.encrypted
s1 = 'abdefghijklmpqrtuvwxyz'
s2 = 'dmenwfoxgpyhirasbktclu'
f1 = open('encryption.encrypted')
with open('encryption.py', 'w') as f2:
for i in f1.readlines():
tmp = ''
for j in i:
tmp += s2[s1.index(j)] if j in s1 else j
f2.write(tmp)
# fix_py()
def common_modulus(n, e1, e2, c1, c2):
assert (libnum.gcd(e1, e2) == 1)
_, s1, s2 = gmpy2.gcdext(e1, e2)
m = pow(c1, s1, n) if s1 > 0 else pow(gmpy2.invert(c1, n), -s1, n)
m *= pow(c2, s2, n) if s2 > 0 else pow(gmpy2.invert(c2, n), -s2, n)
m %= n
return m
[n2, n3] = map(lambda x: int(base64.b64decode(x).encode('hex'), 16),
open('n2&n3').readlines())
[n1c1, n1c2] = map(lambda x: int(x, 16), open('n1.encrypted').readlines())
[msg1c1, msg2c2] = map(lambda x: int(x, 16), open('ciphertext').readlines())
# 通過共模攻擊得到n1
e1 = 0x1001
e2 = 0x101
n1 = common_modulus(n3, e1, e2, n1c1, n1c2)
# n1,n2有一個(gè)共有質(zhì)因數(shù)p1
# n1 += n3 # 存在n3比n1小的可能跨扮，并且確實(shí)如此;貌似主辦方中途改題，把n1改成小于n3了验毡。
p1 = gmpy2.gcd(n1, n2)
assert (p1 != 1)
p2 = n1 / p1
p3 = n2 / p1
e = 0x1001
d1 = gmpy2.invert(e, (p1 - 1) * (p2 - 1))
d2 = gmpy2.invert(e, (p1 - 1) * (p3 - 1))
msg1 = pow(msg1c1, d1, n1)
msg2 = pow(msg2c2, d2, n2)
msg1 = hex(msg1)[2:].decode('hex')
msg2 = hex(msg2)[2:].decode('hex')
print msg1, msg2
# XA{RP0I_0Itrsigi s.y
# MNCYT_55_neetnvmrap}
# XMAN{CRYPT0_I5_50_Interestingvim rsa.py}
小明文攻擊
適用情況：e較小衡创，一般為3。
公鑰e很小晶通，明文m也不大的話璃氢，于是m^e=k*n+m 中的的k值很小甚至為0，爆破k或直接開三次方即可狮辽。Python實(shí)現(xiàn)：
print time.asctime(), "Let's waiting..."
for k in xrange(200000000):
if gmpy2.iroot(c + n * k, e)[1] == 1:
print time.asctime(), "...done!"
return gmpy2.iroot(c + n * k, 3)[0]
例子：Extremely hard RSA
題目提供的n是4096位的一也，e=3。
n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e=3
res=0
c=int(open('extremelyhardRSA.rar/flag.enc','rb').read().encode('hex'),16)
print time.asctime()
for i in xrange(200000000):
if gmpy2.iroot(c+n*i,3)[1]==1:
res=gmpy2.iroot(c+n*i,3)[0]
print i,res
print libnum.n2s(res)
print time.asctime()
break
Rabin加密中的N可被分解
適用情況：e==2
Rabin加密是RSA的衍生算法喉脖，e==2是Rabin加密典型特征椰苟，可以百度或閱讀 https://en.wikipedia.org/wiki/Rabin_cryptosystem 以了解到詳細(xì)的說明，這里只關(guān)注解密方法树叽。一般先通過其他方法分解得到p舆蝴，q，然后解密题诵。
Python實(shí)現(xiàn)：
def rabin_decrypt(c, p, q, e=2):
n = p * q
mp = pow(c, (p + 1) / 4, p)
mq = pow(c, (q + 1) / 4, q)
yp = gmpy2.invert(p, q)
yq = gmpy2.invert(q, p)
r = (yp * p * mq + yq * q * mp) % n
rr = n - r
s = (yp * p * mq - yq * q * mp) % n
ss = n - s
return (r, rr, s, ss)
函數(shù)返回四個(gè)數(shù)洁仗，這其中只有一個(gè)是我們想要的明文，需要通過其他方式驗(yàn)證性锭，當(dāng)然CTF中顯然就是flag字眼了赠潦。
image
例子：Jarvis OJ hard RSA
解題腳本
import gmpy2,libnum
n=0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e=2
c=int(open('hardRSA.rar/flag.enc','rb').read().encode('hex'),16)
mp=pow(c,(p+1)/4,p)
mq=pow(c,(q+1)/4,q)
yp=gmpy2.invert(p,q)
yq=gmpy2.invert(q,p)
r=(yp*p*mq+yq*q*mp)%n
rr=n-r
s=(yp*p*mq-yq*q*mp)%n
ss=n-s
print libnum.n2s(r)
print libnum.n2s(rr)
print libnum.n2s(s)
print libnum.n2s(ss)
Wiener’s Attack
適用情況：e過大或過小。
工具：https://github.com/pablocelayes/rsa-wiener-attack
在e過大或過小的情況下草冈，可使用算法從e中快速推斷出d的值祭椰。詳細(xì)的算法原理可以閱讀：低解密指數(shù)攻擊 臭家。
import ContinuedFractions, Arithmetic
def wiener_hack(e, n):
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k, d) in convergents:
if k != 0 and (e * d - 1) % k == 0:
phi = (e * d - 1) // k
s = n - phi + 1
discr = s * s - 4 * n
if (discr >= 0):
t = Arithmetic.is_perfect_square(discr)
if t != -1 and (s + t) % 2 == 0:
print("Hacked!")
return d
return False
例子：2018強(qiáng)網(wǎng)杯nextrsa-Level2
n = 0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1L
e = 0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46fL
d = wiener_hack(e, n)
print d #42043
**私鑰文件修復(fù)
適用情況：提供破損的私鑰文件。 **
例子：Jarvis OJ-God Like RSA
參考 https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html 修復(fù)存儲(chǔ)私鑰的文件方淤，得到p和q钉赁。
**私鑰修復(fù)
Python 腳本：**
#-*- coding:utf-8 -*-
import re
import pickle
from itertools import product
from libnum import invmod, gcd
def solve_linear(a, b, mod):
if a & 1 == 0 or b & 1 == 0:
return None
return (b * invmod(a, mod)) & (mod - 1) # hack for mod = power of 2
def to_n(s):
s = re.sub(r"[^0-9a-f]", "", s)
return int(s, 16)
def msk(s):
cleaned = "".join(map(lambda x: x[-2:], s.split(":")))
return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)
def msk_ranges(s):
return [range(16) if c == " " else [int(c, 16)] for c in s]
def msk_mask(s):
return int("".join("0" if c == " " else "f" for c in s), 16)
def msk_val(s):
return int("".join("0" if c == " " else c for c in s), 16)
E = 65537
N = to_n("""00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
e8:6c:1d""")
p_ranges, pmask_msk, pmask_val = msk(""" 0: e: : : :c :c : : : :b : : : : :
:ab: e: 2: 8:c : : : 1:6 :6 : 6: f:d9: 0:
8 :5c:7 :06: : : :0 : 3:5 :4b: :6 : : :
2 : :6 : : : :2 :bc: c: :85:1 : 1:d : 3:
1:b4: : b: 1: 3: d:a : : :6e: 0:b :2 : :
:b : :9 :e : :82:8d: : :13: : : a: a:
: :4 : :c : f: : :7 :e :0a: : : b: 5:
: e:91:3 : :3c: 9: : 6: : :b5:7d: 1: :
: : :b :a1:99:6 :4 :3 :c :1a:02:4 : : 9:
9 :f : d:bd: :0 : : : :b3: : 4: :e9: 9:
: d: : :7 : :93: : e:dc: : 0: :e7: :
e : :2 : b: 2:5 : : : : : c:5f: : :e2:
: : 9: :2a: : e: : :2 : :9f: 7:3 : :
b : f:b : : 8: 7: : :f :6 :e :c : :3 : :
f7: 5: 8: 5: : : : : : 8: e: :03: c: :
33:76:e : 1:7 : c: : 0: :0b: : a: : 2: 9:
:c8:bf: : :06: 7:d5: :02: c:b :e2: 7:2 :
: """)
q_ranges, qmask_msk, qmask_val = msk(""" 0: f: :d0: 1:55: 4:31: : b:c4:8 : : e: d:
34: 3:f : : : : : 8:99:1 : : a:0 : :4 :
0 : :f : :a4:41:2 : :a : : 1: : a: c: :
: : 9: : : 2:f4: f: : : : :1 : 4:9 :
a : : :79:0 : : : : : 2: 8:b : :4 : 8:
:9b: 1: :d : :f :e4: :4 :c :e : :3 : :
7:2 : :d :8 :2 :7 : :d :67:fc:e : 0:f9: 7:
8 : : : :1 :2f: :51: : :2e:0a: e:3d: 6:
b : :dd: : 0:fb: :f4: : : :b4: 9:c : :
a: : : :d : : :6b: 2: :9b: a:60: :d6:
0:4f:16:d1: : :5 :fc: :f : :8 : : : :
1: 6:e1:9 : e:4 : 6: c: d:d :73: 3: : :7 :
:8 : 9: :3b:f : 2: : :f1: e: : :1e: :
8 : : : 6:0 : 4:99:e : : 5: : : 4: : :
: a:81:64: :7 :f : 9: d: :9 : : 7:93:f :
ac:8c: : 8: : 0: d: 8: :7 : :1d: :f : :
1 :a :6 :8 : :60: :b3: : : :89: : :14:
:5 """)
_, dmask_msk, dmask_val = msk(""" : : : f:8 :a5:d : 2: 0:b :7 : : 1: : 4:
1:0d: :3 : :6 : : : b: : : :e : : :
0e: 0:db: :1a:1c:c0: : e: : :99:bc:8 :a5:
7 :7 :7 : b: : : 8: 8: :7 :55: 2: : :f :
b2: : :b :f :4 : : 8: :b : : : : 0: :
0 : :6 :9 : : : : b: 4: : 0: a: 5:07:b :
9: c:9a: 9: : 7:9e: : b:60:f : : : :0 :
: 3:0 : : : : 1:b : : : b: 6:0 :f : :
: 2:18: 6: b:1 : : : : :d3:f3: :a : :
3: : : : : 3: d: 1: 2:7 : : d: : 2: d:
: : d:4 : :d : :6d: c:a :b6: : : : 1:
69: : 7: :89: :c :8 :61: d:25: 3:7 :1b: 4:
b : :8 :55: :49: 1:2 :3 : :1 :e9:a8: 3: :
9 : : 1:f8:d3: :e : :d : :9 :b6: : :71:
1 : :c1: : b: 1: : 6:e : :64: : :1a:c :
: b: :bf:c : : 0: : 8:a :4 : :26:a :5 :
6 : : : :eb: :e5: a: :3e:f9:10:0 : : :
6:0 : : 8: : 1:72: c:0 : f:5 : f:9c: 0: e:
7:b : : : : :d9: 4: : e:c :68: : : :
c: :3a: : :a0:ea: 3: 4: :72:a :d : 8: :
:0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
: :17:6 : : c: b: : f: :3 : 5:6 :3 :0e:
: 7:c :3e: 2: 9: 7: 6: f: e: f: 9: :f3: 9:
a :c1:6 : : 1:9 : :43: : f: 5: :0 :27: 4:
4 :a : :e9: : 8: 4:3 :8a: 6:16:d5:c : e: e:
:d : c:b :a8: : 7: : 9: :7 :7d: : : :
: : :4 :2 : : 3: 3: 6: : : :7b:0 : :
e: :0 : :a : : 5: : : : 5:1 :82:c :0d:
4 :2 :fd:36: 5:50:0 : : :d : f: 6: : :e :
0 : : :ce: :9e:8 : :0 :d :07:b3: : : :
0 :e4: : :68:b :c : : c:5 : : :3 : 7: 2:
c:e0: :5 : : :b4: :ef: 7: :1 :e : 0:f :
:6 : : : :e0:c :3 : : : 3: : d: : :
3: 3: c: a: :b : a:71: 3: 0:a : :4 :5d: :
0 :4 """)
_, dpmask_msk, dpmask_val = msk(""" : 3:2a: : d: : : : :0 :1 : f: : : 6:
1 :2 :1b:07: a:e :b :c5:58:7 : :e8: 7: 1: c:
: 1:b :a0: 4:0f:5 :67: :3 :7 :6 :f9: : c:
:79: 0:1 :65: :8 : :99: d:d : :2 :9 :0 :
e: :0 : : : : d: :d :7 :6 :a9: a:8b: b:
: : 7: a:37: : :7 :1 :6 : :c2: 7:6 :b :
e: : : : : : :b :3a:5 : : : : : :
: : :cd:8 : : d: :7 : 3: : f:e : c: :
: a: :c : f:c : 7:b :5 : : :2 :8 :8 :6 :
0a: a: : :3 :db: : 4:00: : d: :b : 5: :
20: 2: 5: :82: : 0: 6: :8a: :7 : : 8: :
4: 1: : : : 8:46: : : : : : 0:f :c8:
2 : : c:7 : : 1: : :2 : 0: 5: : : 1:9b:
6:9 : 0:74: :c : :e : : :cb:b :3 :3 : :
2: : :47: :2 : 0:5 : : : d: 6:83: : :
:c7: : :0b: : : c: :3 :8 : :9 :4 : 7:
5 :c0:fe: :f9: 1: :0 : e: 8:02: : f: :c :
55:61""")
_, dqmask_msk, dqmask_val = msk(""" :0b:7 :4 :0 : 0:6 : 7:7e: : 5: : 7: : a:
a :d : 0: 6: 4:86: : :8 : : : : :e :8f:
9: : : : 1: :2 : : 7: b:1 :5 : f: :8 :
:d :21: :e : d: :c9:e : b: : :1 : : :
:d :a2:b7: : : :f3: :42: :e : c: :f :
: 0:f :7 : 4: 5:34: :4 : c: : :8 :d : 8:
5 :af: 3:1d: 5:4 : :2 : :6 :c : 6:a :1 :5 :
a:9 : :d : : :0a:a1: :f :7 :9 :b : : :
f:2 :27: f: :0 :f6:4d: : : : : :5 : :
4:08: : 5: : 8: 5: : : :18: 4: 8:57: 2:
f: a: : :a8: f: c:f : e: 1:9 :c : 4:9 : :
: : : : : 1: :2 : :d1: : 6:e : d: :
: f:04:2 :8d: : 3: : :b : 8: :d6: : 2:
: : :6 : : f: : : 0:6 : :51: :48:19:
: : :69:4 : c: :c : : f: :f4:d : : f:
d:0 :0d:b :3 : 3:2 : : :6 : b:5 :2 : : c:
1:5a: f:f : : :7e:3e: :d :f :0 : d: c: 6:
1""")
def search(K, Kp, Kq, check_level, break_step):
max_step = 0
cands = [0]
for step in range(1, break_step + 1):
#print " ", step, "( max =", max_step, ")"
max_step = max(step, max_step)
mod = 1 << (4 * step)
mask = mod - 1
cands_next = []
for p, new_digit in product(cands, p_ranges[-step]):
pval = (new_digit << ((step - 1) * 4)) | p
if check_level >= 1:
qval = solve_linear(pval, N & mask, mod)
if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
continue
if check_level >= 2:
val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
if val is None or not check_val(val, mask, dmask_msk, dmask_val):
continue
if check_level >= 3:
val = solve_linear(E, 1 + Kp * (pval - 1), mod)
if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
continue
if check_level >= 4:
val = solve_linear(E, 1 + Kq * (qval - 1), mod)
if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
continue
if pval * qval == N:
print "Kq =", Kq
print "pwned"
print "p =", pval
print "q =", qval
p = pval
q = qval
d = invmod(E, (p - 1) * (q - 1))
coef = invmod(p, q)
from Crypto.PublicKey import RSA
print RSA.construct(map(long, (N, E, d, p, q, coef))).exportKey()
quit()
cands_next.append(pval)
if not cands_next:
return False
cands = cands_next
return True
def check_val(val, mask, mask_msk, mask_val):
test_mask = mask_msk & mask
test_val = mask_val & mask
return val & test_mask == test_val
# K = 4695
# Kp = 15700
# Kq = 5155
for K in range(1, E):
if K % 100 == 0:
print "checking", K
if search(K, 0, 0, check_level=2, break_step=20):
print "K =", K
break
for Kp in range(1, E):
if Kp % 1000 == 0:
print "checking", Kp
if search(K, Kp, 0, check_level=3, break_step=30):
print "Kp =", Kp
break
for Kq in range(1, E):
if Kq % 100 == 0:
print "checking", Kq
if search(K, Kp, Kq, check_level=4, break_step=9999):
print "Kq =", Kq
break
從缺失的私鑰中，我們可以分析出各部分?jǐn)?shù)據(jù)代表的數(shù)字携茂。
struct
{
BIGNUM *n; // public modulus
BIGNUM *e; // public exponent
BIGNUM *d; // private exponent
BIGNUM *p; // secret prime factor
BIGNUM *q; // secret prime factor
BIGNUM *dmp1; // d mod (p-1)
BIGNUM *dmq1; // d mod (q-1)
BIGNUM *iqmp; // q^-1 mod p
// ...
};
改動(dòng)原腳本中的各部分內(nèi)容即可恢復(fù)出私鑰你踩，大致算法為：
given a candidate for (p mod 16**(t - 1)), generate all possible candidates for (p mod 16**t) (check against mask for prime1)
calculate q = n * invmod(p, 16**t) (and check against mask for prime2)
calculate d = invmod(e, 16**t) * (1 + k * (N - p - q + 1)) (and check against mask for private exponent)
calculate d_p = invmod(e, 16**t) * (1 + k_p * (p - 1)) (and check against mask for exponent1)
calculate d_q = invmod(e, 16**t) * (1 + k_q * (q - 1)) (and check against mask for exponent2)
if any of checks failed - check next candidate
**LSB Oracle Attack
適用情況：可以選擇密文并泄露最低位。 **
在一次RSA加密中讳苦，明文為m带膜，模數(shù)為n，加密指數(shù)為e鸳谜，密文為c膝藕。我們可以構(gòu)造出c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n ， 因?yàn)閙的兩倍可能大于n咐扭，所以經(jīng)過解密得到的明文是 m'=(2*m)%n 芭挽。我們還能夠知道 m' 的最低位lsb 是1還是0。 因?yàn)閚是奇數(shù)蝗肪，而2*m 是偶數(shù)袜爪，所以如果lsb 是0，說明(2*m)%n 是偶數(shù)薛闪，沒有超過n辛馆，即m<n/2.0 ，反之則m>n/2.0 豁延。舉個(gè)例子就能明白2%3=2 是偶數(shù)昙篙，而4%3=1 是奇數(shù)焦蘑。以此類推俗慈，構(gòu)造密文c"=(4^e)*c)%n 使其解密后為m"=(4*m)%n ，判斷m" 的奇偶性可以知道m 和 n/4 的大小關(guān)系因痛。所以我們就有了一個(gè)二分算法胰苏，可以在對(duì)數(shù)時(shí)間內(nèi)將m的范圍逼近到一個(gè)足夠狹窄的空間硕蛹。
更多信息可參考：RSA Least-Significant-Bit Oracle Attack 和 RSA least significant bit oracle attack 。
Python實(shí)現(xiàn)：
def oracle():
return lsb == 'odd'
def partial(c, e, n):
k = n.bit_length()
decimal.getcontext().prec = k # for 'precise enough' floats
lo = decimal.Decimal(0)
hi = decimal.Decimal(n)
for i in range(k):
if not oracle(c):
hi = (lo + hi) / 2
else:
lo = (lo + hi) / 2
c = (c * pow(2, e, n)) % n
# print i, int(hi - lo)
return int(hi)
