RSA模数相关攻击

p q 选取不当

适用情况:
当 $p$ 和 $q$ 选取不当时,例如 $q$ 选取了 $p$ 的 $t$ 倍的后几个素数,甚至 $q$ 就是 $p$ 的后几个素数,可以在较短时间内分解 $n$。

原理

不妨设:
$q = tp + k$
那么:
$n = pq = p(tp + k) = tp^2 + pk$
即:
$tp^2 + kp - n = 0$
则:
$p = \frac{-k + \sqrt{k^2 + 4tn}}{2t}$
由于 $p$ 是整数,所以 $\sqrt{k^2 + 4tn}$ 是整数,即 $k^2 + 4tn$ 开方后是整数。
寻找到符合条件的 $k$,那么:
$p = \frac{-k + \sqrt{k^2 + 4tn}}{2t}$
$q = tp + k$
如果 $pq = n$,那么已成功分解。否则继续寻找 $k$。

代码

大数精确开方需要用到 gmpy2 库中的 iroot

1
2
3
4
5
6
7
8
9
10
11
12
def factor():
n_4t = n*4*t
for k in range(100000):
delta = k**2 + n_4t
if gmpy2.iroot(delta, 2)[1]:
print 'k =', k
p = (-k + gmpy2.iroot(delta, 2)[0]) / (2*t)
q = t*p + k
if p*q == n:
print 'p =', p
print 'q =', q
return p, q

例子

2018柏鹭杯:simple RSA
题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from flag import flag
from Crypto.Util.number import *
import random
def next_prime(n):
num = n + 1
while True:
if isPrime(num):
return num
num += 1
p = random.randint(1<<3071,1<<3072)
p = next_prime(p)
q = next_prime(p*10)

N = p*q
e = 65537
c = pow(bytes_to_long(flag),e,N)
print N#247157208312655169175097941364280738161257111976460225724719907081110265510517450181419502794457206227461600647913804553439171851865273449559295717229024951735351965745325255241561391509015823198303928588939850683031392486366218841593013566932215141428061199015117025898704736991786081007198271335363347647516874679013119543722851148642512142186199102168074461255284546705588056994149297326331376082141145137980534967406372164077378650248545875219877244489040506317293082270408705203779841533080244655519849164084793887915122847280359452339072498784918027724621588636245527176960457003310429876627882173282069366037431766179722648353575718417895929519296072344510519198593252963273537190447967056699273665756186541135880261688073100218736960343554003491651502334045257343825793705434779809139021362473746587814528428007114308414633338220797896397738142172067161950968365434368211510967904096253326804711795198906393597153228365711080786247894858858419136771806150038968465644512536135428099037524022644906606239281576512245480765249280626544900781649017542649977530381598608436485399917576052247750573936190833224008929770080605906041913084656134359260509037195783858871830359437278131656343708211575987756873026171223324073191307367943843353573378426157170935012284820053625264544030714057464690450568057598110227083895395913850243271935830358181622027323185508807486853971929523201869477689585619024238113916052252320578711256593537267591407960305853736136636628575478996733430026632486500743561965770413140633948002705696925426367918545515713035754606128166993229587155817506068035187995926746472892280477401942441831391756895131543049750847590716935278314226902082626392655666615086297442052602217416486188297831289978272258543231414975069191549588547253936829655332588805672513945883351937495650167502066292697223592894483418517613405613285519159
print c#152721025887735064764471379084548069204525956728140596238274397757947415316727016281416993518884790524343567541799262176820909148208728616947040227306302164641933331109468512979068186962047716308015535717796123080303496277784765187481185086876434873226524784636408104495312136956587251145463229424950634548624036265557622592089071331292811066840281494102799063634204855779210798330603868025111521826209601342683209160845433746624786171189961029265101816540639855230011618388675527443511618729301028631422873421421991470450059414988968787693753741941765791793672069240992955177930884210118700416564364129283739917229225845073750451244070534919112957275948312337882004219145847493047815403283126471638320784008475284616178697542301935170768573588093196019976675846311280356987370969400610196847990069257614148181804915868273001764028563852238142447411811579695265293746037324400494199877368049162903819737962946786971556872009326814914717430484711885484790156341127433550909206551293806568904858726942820132521566970376839336895645431303013575622422180179687172859250687080526393904583834607514619581478966664406178290247731116920836372943133394640322159512633671870473674514938423231596849301615200001553851411828993918474534316510609878376462094608058640335426907349648369552864820322464995077358198844334320833893207364879282292959161203675080110629771237503657412087961891443054530286088807186134851425688726147108076040204500951624929585070273336203814962656253259257806100191430918121713005141607192112560560371475173081441671613602480052062955279287813475764285469835557663176529059039540417149792518941598550609678298901186032272305421028365295602810159191055078633881059737011784127699357480578433240110432805495328517379885306237631225477566136721077348329866885731002878563684349453668924250445128775992616650275173644658245397235667490402628

由题目可知,p 是一个 3000 多位的素数,q 是 10 倍 p 的下一个素数。
直接可由上方法分解 n:

1
2
3
k = 1171
p = 4971490805710648894784063900603982138103528416416093113682856149525895474391965093292856360186270533203485404384261736770807923420477678768335595268260058770929420214670794184479653642688593773001265441972139034999789321709099375988424776953616924996952770970955016095518058970453801153351600603001621188113472370286189729979231943525793160692844078376540082324198649179890017101800683049489232021392715915700831833371902425005874555370189042455321691195416425399507551235346773377429357933240695935997956969841660473107352934178051894901298644110556291216221039424250078546978571086275993790666829060240691673857284132895978717935677825502362997789971900863003499701755174512295162461514926135376073693593713246781021035797102243028802222257489266812730745381990847604727619717567202686948267842932198278066304365500430012440700948799107940169074390644763691400614036677335457180241108468029814414775113509028739480597728319
q = 49714908057106488947840639006039821381035284164160931136828561495258954743919650932928563601862705332034854043842617367708079234204776787683355952682600587709294202146707941844796536426885937730012654419721390349997893217090993759884247769536169249969527709709550160955180589704538011533516006030016211881134723702861897299792319435257931606928440783765400823241986491798900171018006830494892320213927159157008318333719024250058745553701890424553216911954164253995075512353467733774293579332406959359979569698416604731073529341780518949012986441105562912162210394242500785469785710862759937906668290602406916738572841328959787179356778255023629977899719008630034997017551745122951624615149261353760736935937132467810210357971022430288022222574892668127307453819908476047276197175672026869482678429321982780663043655004300124407009487991079401690743906447636914006140366773354571802411084680298144147751135090287394805977284361

得到flag:
ISEC{simp13_crypt0}


模不互素

适用情况:
当存在两个公钥的 $n$ 不互素时,显然可以直接对这两个数求最大公因数,直接获得 $p$ 和 $q$。

代码

1
2
3
4
5
6
7
8
9
def factor():
p = gmpy2.gcd(n1, n2)
q1 = n1 / p
q2 = n2 / p
assert p*q1 == n1
assert p*q2 == n2
print 'p =', p
print 'q1 =', q1
print 'q2 =', q2

例子

SCTF:RSA2
pcap 包中含有 n 和 e 的消息。其中有两个 n:

1
2
n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943

发现模数不互素:

1
print gmpy2.gcd(n1, n2)

1
122281872221091773923842091258531471948886120336284482555605167683829690073110898673260712865021244633908982705290201598907538975692920305239961645109897081011524485706755794882283892011824006117276162119331970728229108731696164377808170099285659797066904706924125871571157672409051718751812724929680249712137

那么可以直接由上述方法解密,得到flag:
sH1R3_PRlME_1N_rsA_iS_4ulnEra5le


多因子

适用情况:
$n$ 是由两个以上的素数相乘得到,会有些特殊。

原理

如果选取两个以上的素数,记为 $p_1, p_2, p_3…$,它们相乘得到 $n$,那么:
$\varphi (n) = (p_1 - 1)(p_2 - 1)(p_3 - 1)…$
公钥、私钥、加解密都与一般 RSA 相同。
选取多因子,虽然会减少生成密钥的时间,但同样也更容易被破解。

例子

2018picoctf:Super Safe RSA 3
每次 nc 连接可以获得不同的 cne
例如一次连接中:

1
2
3
c: 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n: 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e: 65537

首先用 yafu 经过多次分解直到所有因子都为素数,可以得到 32 个素数因子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2209835647
3279221983
2203115203
3083863231
2624125561
4051923611
3870883097
3919135769
3746033843
2349626557
2911452569
2280078727
3772965367
2486744167
3816147749
2613884417
2657517431
2808514571
3516405091
3393739981
2965911017
2282964227
2794765357
2162896789
4177000211
2804308609
2549752151
2206071653
2336473199
2647948099
3656705023
2574736709

然后就可以直接求解:

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
import gmpy2

c = 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n = 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e = 65537
factors = [2209835647, 3279221983, 2203115203, 3083863231, 2624125561, 4051923611, 3870883097, 3919135769, 3746033843, 2349626557, 2911452569, 2280078727, 3772965367, 2486744167, 3816147749, 2613884417, 2657517431, 2808514571, 3516405091, 3393739981, 2965911017, 2282964227, 2794765357, 2162896789, 4177000211, 2804308609, 2549752151, 2206071653, 2336473199, 2647948099, 3656705023, 2574736709]
phi = 1
for x in factors:
phi *= (x-1)
d = gmpy2.invert(e, phi)
print long_to_bytes(pow(c, d, n))

得到flag:
picoCTF{p_&_q_n0_r_$_t!!_5146060}


共模攻击

适用情况:
当两个用户使用相同的模数、不同的私钥,加密同一明文消息时,即存在共模攻击。

原理

两用户私钥不同而模数相同,则两用户公钥必定不同。
设两用户的公钥分别为 $e_1$ 和 $e_2$,由于选取的 $e$ 与 $\varphi (n)$ 互质,因此 $e_1$ 和 $e_2$ 互质。明文为 $m$,密文分别为:
$c_1 = m^{e_1} \bmod n$
$c_2 = m^{e_2} \bmod n$

当攻击者截获 $c_1$ 和 $c_2$ 后,就可以恢复出明文。
用扩展欧几里得算法可求出 $re_1 + se_2 = 1 \bmod n$ 的两个整数 $r$ 和 $s$,由此可得:
$\begin{align}
c_{1}^{r}c_{2}^{s} &= m^{re_1}m^{se_2}\bmod n \\
&= m^{(re_1+se_2)} \bmod n \\
&= (m\bmod n)^{(re_1+se_2)} \bmod n\\
&= (m\bmod n)^{1 \bmod n} \bmod n\\
&= m \bmod n
\end{align}$

代码

1
2
3
4
5
6
7
8
9
10
11
def get_m():
gcd, r, s = gmpy2.gcdext(e1, e2)
assert gmpy2.gcd(e1, e2) == 1
if r < 0:
r = -r
c1 = gmpy2.invert(c1, n)
if s < 0:
s = -s
c2 = gmpy2.invert(c2, n)
m = pow(c1, r, n) * pow(c2, s, n) % n
print 'm =', m

例子

XMan 一期夏令营课堂练习

1
2
3
4
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}
message1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

可以发现两个公钥模数 $n$ 相同,由上述方法可以得到 $m$:

1
m = 1021089710312311910410111011910111610410511010710511610511511211111511510598108101125

直接 long_to_bytes 得到的都是乱码,这里应该不是通常的将明文逐个字符转 16 进制 ascii 码再字符串相加最后转 10 进制。通过观察应该是每两个或三个数字是 10 进制的 ascii 码。所以:

1
2
3
4
5
6
7
8
9
10
11
i = 0
flag = ""
m = str(m)
while i < len(m):
if m[i] == '1':
flag += chr(int(m[i: i+3]))
i += 3
else:
flag += chr(int(m[i: i+2]))
i += 2
print flag

得到 flag:
flag{whenwethinkitispossible}