RSA 共素数攻击

原理

RSA 的公钥模数 N = p * q，其安全性建立在分解大数 N 的困难性上。如果两个不同的设备、用户或应用生成了各自的模数 N_1 和 N_2，但碰巧使用了同一个素数作为因子

  • N_1 = p × q_1

  • N_1 = p × q_1

那么，攻击者只要计算一次最大公约数就能立即得到公共因子 p，进而求出 q_1 和 q_2，两个模数同时被攻破

实战案例

rsa（共素数攻击）

题目源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime,bytes_to_long

flag=open("flag","rb").read()

p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)

p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n

输出里一共有四个重要值

1
2
3
4
5
6
7
8
第一组：
c1, n1

额外输出：
pow(294, e, n1)

第二组：
c2, n2

两组 RSA 生成过程

1
2
3
4
5
6
7
8
9
10
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = bytes_to_long(flag)
c = pow(m, e, n)

p = getPrime(1024)
n = p * q
m = bytes_to_long("BJD"*32)
c = pow(m,e,n)

两个模数共用了同一个素数 q

1
2
3
n_1 = p_1 * q

n_2 = p_2 * q

那么直接计算 gcd(n_1, n_2) 就能得到 q

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
33
34
35
36
37
38
39
40
41
42
43
44
45
#!/usr/bin/env python3
from math import gcd
from Crypto.Util.number import long_to_bytes

e = 52361

c1 = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120

n1 = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037

hint_value = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018

c2 = 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721

n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047


# 如果没有 hint，可以用这个值爆破 e
assert pow(294, e, n1) == hint_value

# 两个模数共用了 q
q = gcd(n1, n2)

print("[+] gcd(n1, n2) =", q)
print("[+] q bit length =", q.bit_length())

assert q != 1
assert n1 % q == 0
assert n2 % q == 0

p1 = n1 // q

phi1 = (p1 - 1) * (q - 1)

# 检查 e 和 phi(n) 互素
assert gcd(e, phi1) == 1

# Python 3.8+ 可直接 pow(e, -1, phi1)
d = pow(e, -1, phi1)

m = pow(c1, d, n1)

flag = long_to_bytes(m)

print("[+] flag =", flag)

强网先锋-辅助（共素数攻击）

题目中的关键代码，它只重新生成了 p，但是没有重新生成 q

1
2
p = getPrime(1024)
n = p * q
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from math import gcd

def long_to_bytes(n):
    return n.to_bytes((n.bit_length() + 7) // 8, "big")

def bytes_to_long(b):
    return int.from_bytes(b, "big")


c1 = 2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597

n1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727

c2 = 3829060039572042737496679186881067950328956133163629908872348108160129550437697677150599483923925798224328175594483217938833520220087230303470138525970468915511111320396185482564783975435346354440035776909781158407636044986403819840648379609630039348895415045723208843631191252142600667607807479954194447237061080618370787672720344741413537975922184859333432197766580150534457001196765621678659952108010596273244230812327182786329760844037149719587269632133595149294067490955644893402708720284179715002149224068928828656515326446881791228638008572889331511945042911372915003805505412099102954073299010951896955362470

n2 = 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979

e = 65537

# 1. 计算公共因子
q = gcd(n1, n2)

print("[+] gcd(n1, n2) =", q)
print("[+] q bit length =", q.bit_length())

assert q != 1
assert n1 % q == 0
assert n2 % q == 0

# 2. 分解 n1
p1 = n1 // q

print("[+] p1 bit length =", p1.bit_length())

# 3. 计算 phi
phi1 = (p1 - 1) * (q - 1)

assert gcd(e, phi1) == 1

# 4. 求私钥 d
d = pow(e, -1, phi1)

# 5. 解密
m = pow(c1, d, n1)

flag = long_to_bytes(m)

print("[+] flag =", flag)

# 6. 顺手验证第二组已知明文
known_m = bytes_to_long(b"1" * 32)
assert pow(known_m, e, n2) == c2
print("[+] known plaintext check passed")