本篇介绍RSA的常见攻击方式和题型

更新记录

2022-11-14

更新了几种常见的攻击方式

2022-11-20

整理了CopperSmith相关攻击

2022-12-28

把文章的所有数学公式改成mathjax格式，学习Rabin加密

低加密指数攻击

RSA中，如果e选取较小可以缩短加密时间（$e=2，e=3$），但是选取不当会造成安全问题。

e=2密文开平方

如果$e=2$时，即为对$m$进行平方，由于$c=pow(m,e,n)$，极有可能$m^e$后的数据甚至没有$n$大导致取余商为0，余数$c=m^e$，所以我们可以直接对c进行开平方求m。

python自带的开根号函数无法对特别大的数开方，我们可以使用gmpy2来对大整数开根号。

如果e=2

c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529

求m：

1
2
3
4
5
6
7
from Crypto.Util.number import *
import gmpy2

e=2
c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
print(long_to_bytes(gmpy2.iroot(c,2)[0]))
#b'flag1{Th1s_i5_wHat_You_ne3d_FirsT}'

Rabin算法

这个算法我们需要使用到二次剩余有关的性质及结论。

Rabin加密和RSA类似，属于非对称加密，Rabin加密中我们知道$e=2$，也知道$p,q$的值，也有$p\equiv q\equiv 3(\bmod 4)$，加密公式为$c=m^2\bmod n$，下面是解密原理：

根据$\phi(n)$我们可以知道它一定是个偶数，所以$e=2$对$\phi(n)$没有逆元，不能用正常的方法进行。

我们知道$c=m^2\bmod n$，$p,q$是$n$的因子，那么也有$c=m_p^2\bmod p,c=m_q^2\bmod q$，知道$c$是$p,q$的二次剩余，这里，我们用中国剩余定理就能求出唯一解$m \bmod n$。

我们首先计算出$m$，根据欧拉准则，我们可以知道$c^{\frac{p-1}2}\equiv 1\bmod p$，有$m_p^2\equiv 1\cdot c\equiv c^{\frac{p-1}2}\cdot c\equiv c^{\frac{p+1}2}\equiv (c^{\frac{p+1}4})^2\bmod p$，注意，Rabin算法里面默认满足$p\equiv q\equiv 3(\bmod 4)$，那么$m_p=±c^{\frac {p+1}4}\bmod p,m_q=±c^{\frac {q+1}4}\bmod q$

我们由于未知正负关系，所以将下面这四个式子两两组合，我们可以得到四个方程组能进行中国剩余定理求解，将四个解都计算出来（需要求$p,q$之间的逆元），其中之一就是我们需要的解：

若某题为：

1
2
3
4
5
e = 2  
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461  
p = 275127860351348928173285174381581152299  
q = 319576316814478949870590164193048041239
c = 45617141162985597041928941111553655146539175146765096976546144304138540198644

发现为Rabin加密，按照上面的分析，我们可以写出脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import gmpy2

e = 2  
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461  
p = 275127860351348928173285174381581152299  
q = 319576316814478949870590164193048041239
c = 45617141162985597041928941111553655146539175146765096976546144304138540198644
m=[]
mp=pow(c,(p+1)//4,p)
mq=pow(c,(q+1)//4,q)
qq=gmpy2.invert(p,q)
pp=gmpy2.invert(q,p)
m.append(long_to_bytes((mp*q*pp+mq*p*qq)%n))
m.append(long_to_bytes((mp*q*pp-mq*p*qq)%n))
m.append(long_to_bytes((-mp*q*pp+mq*p*qq)%n))
m.append(long_to_bytes((-mp*q*pp-mq*p*qq)%n))
for i in m:
    if b'flag' in i:
        print(i)#b'flag{R0bin_rsa_666666}'

e=3小明文攻击

和上面那种情况类似，明文过小，导致明文的e次方仍然小于n。（$m^e<n$)

1
2
3
n=0xad03794ef170d81aad370dccb7b92af7d174c10e0ae9ddc99b7dc5f93af6c65b51cc9c40941b002c7633caf8cd50e1b73aa942c8488d46c0032064306de388151814982b6d35b4e2a62dd647f527b31b4f826c36848dc52999574a8694460e1b59b4e96bda1341d3ba5f991f0000a56004d47681ecfd37a5e64bd198617f8dad
e=0x3
c=0x10652cdf6f422470ea251f77

依旧是直接开方：

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

n=0xad03794ef170d81aad370dccb7b92af7d174c10e0ae9ddc99b7dc5f93af6c65b51cc9c40941b002c7633caf8cd50e1b73aa942c8488d46c0032064306de388151814982b6d35b4e2a62dd647f527b31b4f826c36848dc52999574a8694460e1b59b4e96bda1341d3ba5f991f0000a56004d47681ecfd37a5e64bd198617f8dad
e=0x3
c=0x10652cdf6f422470ea251f77
print(long_to_bytes(gmpy2.iroot(c,3)[0]))
#b'flag'

如果$m^e<n$，明文略大，根据$c=pow(m,e,n)$，展开可以得到$m^e=kn+c$，我们可以考虑爆破$k$来求解$m$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
e = 0x3
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

from Crypto.Util.number import *
import gmpy2

k=0
while 1:
  m_e=c+k*n
  m=gmpy2.iroot(m_e,e)
  if m[1] == True:
    print(long_to_bytes(m[0]))
    break
  k+=1
#b'flag{25df8caf006ee5db94d48144c33b2c3b}'

由于gmpy2.iroot()函数返回值为一个数组为( mpz() , true/false )，我们可以在函数后使用[0]或者[1]来选择我们需要开方后的数据还是能否开方的判定。

pq相关

当$p,q$选取不当时进行攻击。

当$|p-q|$过大，接近于$n$，使得某个质因子很小，我们可以设为$p$，进行遍历爆破试除，得到$p,q$。

当$|p-q|$过小，使用费马因式分解：$n=x^2-y^2$，我们很容易知道$x$很大，$y$很小，我们可以从$\sqrt(n)$开始遍历，找到一个$x$使得$x^2-n$为完全平方数，进而因式分解求得$p,q$。

共模攻击

共模是指m相同，用两个公钥e1和e2加密得到两个私钥d1和d2和两个密文c1和c2

共模攻击是指在$m$不变的情况下，知道$n,e_1,e_2,c_1,c_2$，可以在不知道$d_1$和$d_2$的情况下直接求$m$。

原理：①$gcd(e_1,e_2)=1$

根据扩展欧几里得算法可以得到该式子的一组解$(s_1,s_2)$，假设$s_1$为正数，$s_2$为负数，得到整数$s_1,s_2$(一正一负)存在$e_1s_1+e_2s_2=1$(Ⅰ)

②$c_1≡m^{e_1} (\bmod n)$ $c_2≡m^{e_2} (\bmod n)$

③将上面两个式子代入(Ⅰ)式，得到：

$c_1^{s_1} c_2^{s_2} ≡ m (\bmod n)$（$m^1$ 1的代换）

因为$m<n$，所以$m\bmod n=m$

根据模运算性质：

$(ab)\bmod n=(a\bmod n*b\bmod n )\bmod n$

得到：$m = (c_1^{s_1}\bmod n * c_2^{s_2}\bmod n) \bmod n$

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2
#n1和n2相同
n1= 13275539468515927122668657418826962202430467408860484765898568663156503527396473586233806355289560759234484646820604878130245116609025833260834734249490247181739187091798406386899992249647283296098046635078998806241008947511489965043592342640904960118547695431908152475613663532406184101144164645776485026634520190801390504479902674438381031902988558383334546358843335032069110257941561153526273905221509504939058454345020402752203190691148266740216247933791900283468212865430165408235093857626104437061213452413564723765040442767798563232901124229044449065445046888956215682366228655047929453110805914555163635510419
e1= 2333
c1= 12839285960223495540837529365339640783021439899108155136321855396508597591195084834231690640732914408618285996134049202996422114737474822115945692760871458165554118169402663520900701296114704740122786806542520699905862239914946533647899715822828542560800418499031431014437887839597676472165537391472198221714363610491291038442463223575122912669355380941374075599322428985304893846875110708290551186273543362765115647684956793570841630280930991407077401574158296542671529832884549202417721050055128956160795181219321381962644469613816746657814407025821523489911167830470453075666809891234756979759785607614579837734082
n2= 13275539468515927122668657418826962202430467408860484765898568663156503527396473586233806355289560759234484646820604878130245116609025833260834734249490247181739187091798406386899992249647283296098046635078998806241008947511489965043592342640904960118547695431908152475613663532406184101144164645776485026634520190801390504479902674438381031902988558383334546358843335032069110257941561153526273905221509504939058454345020402752203190691148266740216247933791900283468212865430165408235093857626104437061213452413564723765040442767798563232901124229044449065445046888956215682366228655047929453110805914555163635510419
e2= 23333
c2= 3354756678232940495821979239801458007420410531822100812188898131516917749604851255269716527378343349516173106916414335163414268865824921119788877047553519631159949070051858008087712664995111487663781337726742683963116894637201549928831686056701870685405950856250977197910095810076403861881931015074416123490624856112462001350590171001296114611866177706693234039596982711256182797885834942186618425452535848339326240931859796433390218112045498069663580377366715346261942151557866185723732917427377138450852758541378023643134160677508933773941402646042004431292764888647202090679358894168736017515947373729257142729574

s,s1,s2=gmpy2.gcdext(e1,e2)
m=(pow(c1,s1,n1)*pow(c2,s2,n2))%n1#按照原理的推导得到的公式
print(long_to_bytes(m))#b'flag{6ed4c74e022cb18c8039e96de93aa9ce}'

模不互素

当存在多个模数$n$时，且当$gcd(n1,n2)≠1$时，两个模数不互素。

可以直接用欧几里得算法求出最大公约数得到对应的$p$或者$q$然后解密，非常简单：

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

c1=13441730251400128571977229593142940871751010505381260855224460287196727390469222939550812421347200196838438048024699666221486802399908899010207952343801594188343416907494217924604327790503225883835542346125225482039344759350277763837433379280096583341305389028869617683248799413979739363268033457687465648996420262716417241581724493354470106199821352349016588472136090169379061645169693166556944920857438600077175526576901256793011730088141894904144285313760021495889726682793012896005817269414998385027639644144616832444514530403073030074694777870828535446455324845772164336435571805941661828254282577755466733681550
c2=15328231330250081834477047740219278282593316362511100615004204622751171786670132245993887278491381235923056662500506998723614766703426463648408584443840596658345328131231183132509438413920351183948597928113589586382222764143163739012657735133379774771882801667737372560077053092559253594975541684842173939272386708330451380672084965747617626864956929312872056828498547489151622072278717218665029388764167372656315577727760793345119835363455506714130568979127981648251048378570854739086045308861851329670856571007215486559995487334672649387929289702393044489595651437697120416844240038737247851007260737699242433849924
n1=21824377738779468408827257784401291473510623951766563141467558666616122490580910590551791962182427311641502353346679610452829645848149848094627969354527652926697036837906234006527213506271197959772535054805941010860061487823884098869298300373932635288127822852298726035718315157544390927191969937871533140271655172776250090457934043984618296009621629200210952555157491449646254006516484772261881841377759561914782569350417091348181559115131387199775692882615684899521994039959458124354607871266998158582149478276930551057090238387496374521608281241581919370523817836840684035704981411384652048934515438607942152412681
n2=20092029528145992672654139890073213933238747749527468384088598597064157041275139759338939580495558132872000918949479506250951303058790519564498577759721056673790952159641958165024935517188228157952632089028204813818219749916767189828594940489791086812351615483375322705135798629782502006287366383693037549218957930440072994018927604211317945738204827472296517527130741396522181378192623474072177646653632335928008386592012648807016280337010353870037888161926332957003563238193945646462100660541744548842179623794874337825298666377443675103599615275110932815601056993385591682021400454266209586562090271432179596232569

p=gmpy2.gcd(n1,n2)
q1=n1//p
q2=n2//p
e=65537
d=gmpy2.invert(e,(p-1)*(q1-1))
m=pow(c1,d,n1)
print(long_to_bytes(m))

Roll按行加密

这种情况将密文拆分单独列出，我们需要将密文逐个破解获得flag。

例题：RSAROLL：

所给题目文件如下：

{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

在这一串数值中，最前面括起来的为$n$和$e$，后面的为拆分的$c$，我们可以设置一个数组遍历密文解密后组合：

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

n=920139713
e=19
c=[704796792,752211152,274704164,18414022,368270835,483295235,263072905,459788476,483295235,459788476,663551792,475206804,459788476,428313374,475206804,459788476,425392137,704796792,458265677,341524652,483295235,534149509,425392137,428313374,425392137,341524652,458265677,263072905,483295235,828509797,341524652,425392137,475206804,428313374,483295235,475206804,459788476,306220148]

phi=sympy.totient(n)
d=gmpy2.invert(e,int(phi))
flag=""
for i in c:
  m=long_to_bytes(pow(i,d,n))
  flag=flag+m.decode()#decode返回字符串
print(flag)

多素数RSA

如果n由多个素数因子相乘得到，此时：

$n=pqrs……$

$phi=(p-1)(q-1)(r-1)(s-1)……$

其他计算和一般的RSA几乎相同，且分解后素数值相差过小或者过大都会使得$n$更好分解，使用yafu可以直接分解得到多个素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2 
p=1249559655343546956371276497499 
q=1249559655343546956371276497489 
r=1249559655343546956371276497537 
s=1249559655343546956371276497423 
e=0x10001 
c=0x22fda6137013bac19754f78e8d9658498017f05a4b0814f2af97dc2c60fdc433d2949ea27b13337961ef3c4cf27452ad3c95 
n=p*q*r*s 
phi=(p-1)*(q-1)*(r-1)*(s-1) 
d=gmpy2.invert(e,phi) 
m=pow(c,d,n)
print(long_to_bytes(m))
#b'flag is:testflag'

但是，如果分解后得到的因数过多，导致在定义因数变量时过于繁琐，我们可以直接使用sympy模块：

phi=sympy.totient(n)

此函数在n便于分解的前提下可以直接分解$n$并求欧拉函数：

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

n = 706179551528927755973552706384396984481317254286311623624769899751819558939505945997955808655099027031705265588837771891194337168185947501511405516114316789503893959933022257186151153998659082999630884992772455511117927262369430907812434632575048530041321710852346187864765563420900774870186578367019792489105675914258590354238288703776693825560015115292267646952651167684102073917401094871598116344315029571542763276173097810446291806671655688989136095998847231743650883822652934830157399820589087316766825588604788059432668390768008074573747942247918780066903612446281491110881465924899154507579133581995992453624743
e = 12429651525304197013420279636711923981038125415166022519813412628507500580842180697305180388443706309048295378021377001474127573305660405451533036316536279
c = 489793409206127323003663138555459463734568805718348185967363875100820061051281866993789805632550567774469168536774422909001725853017677808173233286745121655492235683190912523018811907652176512184366843413364716154846998486548611626688519571323104191711209211363547146221376030907992798593852466452993901455418977825327230736672597253861620003629101553059002681884047091535001348201522250928398365221843609859032236259074731044818227022822220827819732951798250094840916333657668242504816809502947668786327917580504462518995597830910788447212750284065632411801331136555650318499485528208557551780877753450322260693177513

phi=sympy.totient(n)
d=gmpy2.invert(e,int(phi)) 
m=pow(c,d,n)
print(long_to_bytes(m))
#b'flag{952f8efea78b9db5455b091e45bb812d104bb6bf3bea123cc010ec42cb4cf123}'

在这个题里，$n$经过yafu分解能有接近100个因子，所以直接用公式才是最好的选择。

dp dq泄露

$dp=d\bmod (p-1)$

$dq=d\bmod (q-1)$

在RSA中，已知$dp，dq，p，q，c$，可以求$m$，大致推导流程如下：

$m ≡ c^d (\bmod n)$，先拆分这个式子：

$m_1=(c^d)\bmod p$⑤
$m_2=(c^d)\bmod q$⑥

用费马小定理得：$m_1=c^{d+a(p-1)}\bmod p=c^{dp} \bmod p$
同理由⑥得：$m_2=c^{d+b(q-1)}\bmod q=c^{dq}\bmod q$

同时，⑤可知$m_1+kp=c^d$⑦

代入⑥可得$kp≡m_2-m_1(\bmod q)$

由逆元定义，我们能得到：

$k≡p^{-1}(m2-m1)(\bmod q)$

代入⑦可得$c^d=m_1+p^{-1}((m_2-m_1)\bmod q)p$

根据以上推导可以写脚本：

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

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

n=p*q
pq=gmpy2.invert(p,q)
m1=pow(c,dp,p)
m2=pow(c,dq,q)
m=m1+pq*((m2-m1)%q)*p
print(long_to_bytes(m))

脚本倒数第二行有关$c^d=m$的问题：在$c^d=m_1+kp$中$m_1$是模$p$下的数，$k$是模$q$下的数，$kp<pq$，再加上$m_1<n$，取模$n$关系不大，所以$c^d=m$

dp泄露

在RSA中，若已知$dp、e、n、c$，则可计算出$p$，大致推导流程如下：

$dp=d\bmod (p-1)$

$dp≡d ( \bmod (p-1))$

$dpe≡de ( \bmod (p-1) )$

也就是$de=k(p-1)+dpe$ ①

在RSA中，$d*e≡1 (\bmod φ(n))$

也就是$de=1+k(p-1)(q-1)$ ②

把②代入①，得到$dpe=k_2(p-1)(q-1)-k_1(p-1)+1$

化简：$dpe=(k_2(q-1)-k_1)(p-1)+1$

由$dp=d\bmod (p-1)$可知，$dp\lt p-1$，所以$e\gt k_2(q-1)-k_1$（1的大小暂时忽略不计）

我们可以设 $k_2(q-1)-k_1=i$，遍历$i$（$e+1$种可能），求出 $p-1$ 得到$p$且能被$n$整除，进而求出$m$

对上式变形：$p-1=\frac{dpe-1}i$ 得$p=\frac{dpe-1}i+1$，先求$p$：

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

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for i in range(1,e):
    if (dp*e-1)%i==0 and n%(((dp*e-1)//i)+1)==0:#(dp*e-1)%i是p-1，寻找整数p-1且n能被p整除
        p=((dp*e-1)//i)+1
        q=n//p
        phi=(p-1)*(q-1)
        d=gmpy2.invert(e,phi)
        m=pow(c,d,n)
        print(long_to_bytes(m))
        break#跳出循环避免过多的运算
#b'flag{wow_leaking_dp_breaks_rsa?_98924743502}'

CopperSmith攻击

此攻击需要使用SageMath

前置知识

Coppersmith定理：

在一个e阶的mod n多项式f(x)中，如果有一个根小于$n^{\frac 1 e}$，就可以运用一个O(log n)的算法求出这些根。

sagemath：

​ 生成一个以x为符号的一元多项式环：
​ p.<x> = PolynomialRing(Zmod(n))

​ 定义求解的函数f，就是构造一个在模n或模n的因数为0条件下的方程：
​ 在已知p高位的攻击中：f = x + p_high（表示p的高位）

​ 多项式小值根求解及因子分解：
​ 引入X：表示求解根的上界

​ 引入β：求n因数下意义较少的根（p或q）（0<β≤1）

​ 规定：本题中，规定p或q≥n^β，大体可知β≠0.5，应该稍小一些，p,q二进制位数相同时一般只能取0.4。

x0 = f.small_roots(X=2^kbits, beta=0.4)（kbits为缺失的位数）

按位运算符：

按位运算符是把数字看作二进制来进行计算的。Python中的按位运算法则如下：

按位与 & 举例： 5&3 = 1 解释： 101 11 都为1的位仅为第一位1 ，故结果为 1

按位或 | 举例： 5|3 = 7 解释： 101 11 出现1的位是第一位第二位和第三位，故结果为 111

按位异或 ^ 举例： 5^3 = 6 解释： 101 11 对位相加(不进位)是 1 1 0，故结果为 110

按位反转 ~ 举例： ~5 = -6

解释： 将二进制数+1之后乘以-1，即~x = -(x+1)，-(101 + 1) = -110

按位反转仅能用在数字前面，不能出现在后面。

按位左移 << 举例： 5<<2 = 20 解释：101 向左移动2位得到 10100 ，即右面多出2位用0补

按位右移 >> 举例： 5>>2 = 1 解释：101 向右移动2位得到 1，即去掉右面的2位

已知p的高位

当p和q位数相同（如都为1024位）：

1
2
3
4
from Crypto.Util.number import getPrime
p = getPrime(1024)
q = getPrime(1024)
n = p * q

例题：

1
2
3
4
e = 0x10001
p>>128<<128 = 0xd1c520d9798f811e87f4ff406941958bab8fc24b19a32c3ad89b0b73258ed3541e9ca696fd98ce15255264c39ae8c6e8db5ee89993fa44459410d30a0a8af700ae3aee8a9a1d6094f8c757d3b79a8d1147e85be34fb260a970a52826c0a92b46cefb5dfaf2b5a31edf867f8d34d2222900000000000000000000000000000000
n = 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3
c = 0x1b2b4f9afed5fb5f9876757e959c183c2381ca73514b1918d2f123e386bebe9832835350f17ac439ac570c9b2738f924ef49afea02922981fad702012d69ea3a3c7d1fc8efc80e541ca2622d7741090b9ccd590906ac273ffcc66a7b8c0d48b7d62d6cd6dd4cd75747c55aac28f8be3249eb255d8750482ebf492692121ab4b27b275a0f69b15baef20bf812f3cbf581786128b51694331be76f80d6fb1314d8b280eaa16c767821b9c2ba05dfde5451feef22ac3cb3dfbc88bc1501765506f0c05045184292a75c475486b680f726f44ef8ddfe3c48f75bb03c8d44198ac70e6b7c885f53000654db22c8cee8eb4f65eaeea2da13887aaf53d8c254d2945691

p>>128<<128表示在p的二进制中的最后128位全部改成0，相当于未知低位。

先在sagemath里还原p：

1
2
3
4
5
6
7
#SageMath:先赋值n和所求的p
p_high = 0xd1c520d9798f811e87f4ff406941958bab8fc24b19a32c3ad89b0b73258ed3541e9ca696fd98ce15255264c39ae8c6e8db5ee89993fa44459410d30a0a8af700ae3aee8a9a1d6094f8c757d3b79a8d1147e85be34fb260a970a52826c0a92b46cefb5dfaf2b5a31edf867f8d34d2222900000000000000000000000000000000
n = 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3
p.<x>=PolynomialRing(Zmod(n))
f=x+p_high
x0=f.small_roots(X=2^128,beta=0.4)[0]#函数输出数组，[0]提取数
print(p_high+x0)

然后直接求m即可：

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

e = 0x10001
p_high = 0xd1c520d9798f811e87f4ff406941958bab8fc24b19a32c3ad89b0b73258ed3541e9ca696fd98ce15255264c39ae8c6e8db5ee89993fa44459410d30a0a8af700ae3aee8a9a1d6094f8c757d3b79a8d1147e85be34fb260a970a52826c0a92b46cefb5dfaf2b5a31edf867f8d34d2222900000000000000000000000000000000
n = 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3
c = 0x1b2b4f9afed5fb5f9876757e959c183c2381ca73514b1918d2f123e386bebe9832835350f17ac439ac570c9b2738f924ef49afea02922981fad702012d69ea3a3c7d1fc8efc80e541ca2622d7741090b9ccd590906ac273ffcc66a7b8c0d48b7d62d6cd6dd4cd75747c55aac28f8be3249eb255d8750482ebf492692121ab4b27b275a0f69b15baef20bf812f3cbf581786128b51694331be76f80d6fb1314d8b280eaa16c767821b9c2ba05dfde5451feef22ac3cb3dfbc88bc1501765506f0c05045184292a75c475486b680f726f44ef8ddfe3c48f75bb03c8d44198ac70e6b7c885f53000654db22c8cee8eb4f65eaeea2da13887aaf53d8c254d2945691

#sagemath
p=147305526294483975294006704928271118039370615054437206404408410848858740256154476278591035455064149531353089038270283281541411458250950936656537283482331598521457077465891874559349872035197398406708610440618635013091489698011474611145014167945729411970665381793142591665313979405475889978830728651549052207969

q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))#b'flag{Kn0wn_Hi9h_Bit5}'

已知m的高位

例题：

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

p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

m = bytes_to_long(long_to_bytes(randint(0,30))*208+flag)
assert(m.bit_length()==2044)
print((m>>315)<<315)
c = pow(m,3,n)
e=3
print(c)

#14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
#1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
#6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819

本题中通过print((m>>315)<<315)得知m的后315位未知，我们需要还原m的后315位求出真正的m。

我们照样可以使用sagemath进行计算：f 是构造一个在模n或模n的因数为0条件下的方程，由于c=pow(m,e,n)，得在模n条件下$m^3-c=0$，推得：

$f=m^e-c$

β：f公式中进行模$b$，有$b≥n^β$，由于本题是模的n，应该大于n的beta次方，所以beta取在范围内的值都可以。

根据p高位攻击的原理同理可得：

1
2
3
4
5
6
7
8
9
#sagemath
n=14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
m_high=1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
c=6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819
e=3
p.<x>=PolynomialRing(Zmod(n))
f=(m_high+x)^3-c
x0=f.small_roots(X=2^315,beta=0.4)
print(m_high+x0)

然后直接对m进行long_to_bytes就能得到最终flag：

1
2
3
from Crypto.Util.number import *
m=1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733393609593321367463114703873343853590413300366406780333184299791982772652326424221774382732443261
print(long_to_bytes(m))

已知m的低位

例题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from secret import flag
p = getPrime(512)
q = getPrime(512)
assert GCD(3, (p-1)*(q-1)) != 1
assert len(flag) == 40
assert flag.startswith(b'flag{')
assert flag.endswith(b'}')
n = p*q
m = bytes_to_long(flag[7:-1]+b'12345678900987654321')
e = 3
c = pow(m, e, n)

print("n =", n)
print("m =", m&((1<<350)-1))
print("c =", c)

'''
n = 78143938921360185614860462235112355256968995028076215097413461371745388165946555700961349927305255136527151965763804585057604387898421720879593387223895933656350645970498558271551701970896688207206809537892771605339961799334047604053282371439410751334173463317244016213693285842193635136764938802757014669091
m = 1906077032611187208365446696459387107800629785754941498024021333398862239730761050657886407994645536780849
c = 50130000135496687335562420162077023127865865388254124043997590968769445787929013990729805222613912997653046528125102370938788632651827553831996692788561639714991297669155839231144254658035090111092408296896778962224040765239997700906745359526477039359317216610131441370663885646599680838617778727787254679678
'''

print("m =", m&((1<<350)-1))根据m的输出结果可以得知m知道后350位，前面未知位数被抹除。

和m的高位攻击思路大体相同，题目所给了flag40的长度，取了[7:-3]共32位和”12345678900987654321”相加52位共416位长度（一个字节转二进制数为8位），减去350位得到未知的位数为66位，上限加一为67位。

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

n = 78143938921360185614860462235112355256968995028076215097413461371745388165946555700961349927305255136527151965763804585057604387898421720879593387223895933656350645970498558271551701970896688207206809537892771605339961799334047604053282371439410751334173463317244016213693285842193635136764938802757014669091
m_low = 1906077032611187208365446696459387107800629785754941498024021333398862239730761050657886407994645536780849
c = 50130000135496687335562420162077023127865865388254124043997590968769445787929013990729805222613912997653046528125102370938788632651827553831996692788561639714991297669155839231144254658035090111092408296896778962224040765239997700906745359526477039359317216610131441370663885646599680838617778727787254679678
e = 3

#sagemath
P.<x>=PolynomialRing(Zmod(n))
f=(m_low+x*(2**350))**e-c
f=f.monic()#低位攻击最好加上此函数
x0=f.small_roots(X=2**67,beta=1)[0]
print(long_to_bytes(int(m_low+x0*(2**350))))
#b'739a9a9e50c9a8a5ba83ae2a8e75947012345678900987654321'去掉后面加的数"12345678900987654321"即为所得flag

已知d的低位

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
import libnum


def getFullP(low_p, n):
    R. < x > = PolynomialRing(Zmod(n), implementation='NTL')
    p = x * 2 ^ bit + low_p
    root = (p - n).monic().small_roots(X=2 ^ 128, beta=0.4)
    if root:
        return p(root[0])
    return None


def phase4(low_d, n, c):
    maybe_p = []
    for k in range(1, 4):
        p = var('p')
        p0 = solve_mod([3 * p * low_d == p + k * (n * p - p ^ 2 - n + p)], 2 ^ bit)
        maybe_p += [int(x[0]) for x in p0]
    # print(maybe_p)

    for x in maybe_p:
        P = getFullP(x, n)
        if P: break

    P = int(P)
    Q = n // P

    assert P * Q == n
    print(P)
    print(Q)

    d = inverse_mod(3, (P - 1) * (Q - 1))
    print(d)
    print(libnum.n2s(int(power_mod(c, d, n))))


bit = 486
n = 99233273001596380809501393613886417854988989363311895592445631124571940638105064581031336422148895730117448547059137492090852484233539441265373247940823283633017582469362503632785297924194187912199716752955609363457416190782142095008241313065484612071705711161086869849047664563205898255359661312582650481473
e = 3
c = 175676150266403937224898870626869248307097859453341599800113943191154294552011908698393750389195590199207971365632903719917006078351629939912360175671032635640354766675409868021903917260597989036476083685690139071290022752606720020238530580507331902326179201548484337939338062870542095137303322195300197
d1 = 66155515334397587206334262409257611903325992908874597061630420749714627092070043054020890948099263820078299031372758328060568322822359627510248831960548842374360111368587702677016263988651746874367056185352095585037936034196599496577057035033718066207964292781685419156037246789689219471468151618592221802699

phase4(d1, n, c)