RSA(持续更新🫡)

基本原理

RSA 中加、解密：

加密\(c = m^e\quad mod\quad n\)

解密\(m = c^d\quad mod\quad n\)

接下来证明一下解密过程，先引入欧拉定理。

欧拉定理

对于互为质数的 m、n 两个数，有\(m^{\phi(n)} = 1\quad mod\quad n\)，其中\(\phi(n)\)表示小于 n 的质数的个数。

解密原理

通过\(c = m^e\quad mod\quad n\)与欧拉定理\(m^{\phi(n)} = 1\quad mod\quad n\)，我们便可进行推导。

对欧拉定理进行变形，得到\(m^{k\phi(n)+1} = m\quad mod\quad n\)

因为我们已经知道\(c = m^e\quad mod\quad n\)，所以寻找一个 d，使得\(ed = k\phi(n)+1\),则可以得到\(m^{ed}=m\quad mod \quad n\)

则得到了\(c^d =m\quad mod\quad n\)

共模攻击

所谓共模，就是 n 相同，会对应多组 c，e。

例：给定 n、c1、c2、e1、e2

m = c1e1 mod n

m = c2e2 mod n

扩展欧几里得算法

给定两个整数 a、b，必定存在 x、y，使得 gcd(a,b)=ax+by

运用该算法推导过程

m = m % n

m = ms1e1+s2e2 % n

m = (me1s1 * me2s2)% n

m = (me1s1 % n) * (me2s2 % n) % n

m = (c1s1 % n) * (c2s2 % n) % n

EXP

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import long_to_bytes
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

r,s1,s2=gmpy2.gcdext(e1,e2)
m=(pow(c1,s1,n) * pow(c2,s2,n)) %n
print(long_to_bytes(m))
#flag{49d91077a1abcb14f1a9d546c80be9ef}

Wiener's Attack

适用于已知 N、e，且 e 过大或过小。

Wiener 表示如果\(d<\frac{1}{3}n^{\frac{1}{4}}\),那么一种基于连分数的攻击就可危及 RSA 安全。

那么什么是连分数以及如何利用呢？

连分数

当 \(a_0, a_1, a_2, \dots, a_n\) 都是正整数时，一个连分数可以表示为： \[x\;=\;a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}}\]

例如我们可以求解\(\pi\)的近似值 \[\pi = 3 + \cfrac{1}{7 + \cfrac{1^2}{15 + \cfrac{2^2}{1 + \cfrac{3^2}{1 + \cfrac{4^2}{2 + \cdots}}}}}\] 其中每一项可以用如下公式计算：

\[ a_k = \begin{cases} a_0, & k=0 \\ \lfloor b_k \rfloor, & k > 0 \end{cases}\\ \]

\[ b_k = \begin{cases} a_0, & k=0 \\ \dfrac{1}{b_{k-1} - \lfloor b_{k-1} \rfloor}, & k > 0 \end{cases} \]

在这个例子中，\(a_0 = 3\)，并且按照上述公式递归计算 \(a_k\) 和 \(b_k\) 直到达到一定精度为止，就可以得到一个近似值 \(\pi \approx 3.14159265\)。

至此也就明白了连分数的作用，常用于无理数的逼近。

当然，也可以逼近一个任意数，得到最接近精确值的近似值。

Legendre's theorem

\[\left | \frac{e}{N}-\frac{k}{d} \right |\leq \frac{1}{2d^2}\] 当满足这一点时，\(\frac{k}{d}\)就是\(\frac{e}{N}\)的连分数收敛。

攻击 RSA 原理

\[\phi(n)=(p-1)(q-1)\]

\[\because p,q很大,\therefore \phi(n) \approx N\] \[ed - 1=k\phi(n)\] 同除 \(d\phi(n)\) 得 \[\frac{e}{\phi(n)}-\frac{k}{d}=\frac{1}{d\phi(n)}\] \[\therefore \frac{e}{N}-\frac{k}{d}=\frac{1}{d\phi(n)}\]

到这里发现，等式右边的\(\frac{1}{d\phi(n)}\)很小，因此\(\frac{k}{d}\)就是一个对于已知量\(\frac{e}{N}\)的一个连分数逼近。

因此可以通过将\(\frac{e}{N}\)的连分数展开，依次计算每一个渐进分数。Wiener 证明了可以精准覆盖\(\frac{k}{d}\)。

exp

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
import gmpy2
def transform(x,y):       #使用辗转相处将分数 x/y 转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res

def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:      #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回


#求解每个渐进分数
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res

def get_pq(a,b,c):      #由p+q和pq的值通过维达定理来求解p和q
    par=gmpy2.isqrt(b*b-4*a*c)   #由上述可得，开根号一定是整数，因为有解
    x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
    return x1,x2

def wienerAttack(e,n):
    for (d,k) in sub_fraction(e,n):  #用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k==0:                     #可能会出现连分数的第一个为0的情况，排除
            continue
        if (e*d-1)%k!=0:             #ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue

        phi=(e*d-1)//k               #这个结果就是 φ(n)
        px,qy=get_pq(1,n-phi+1,n)
        if px*qy==n:
            p,q=abs(int(px)),abs(int(qy))     #可能会得到两个负数，负负得正未尝不会出现
            d=gmpy2.invert(e,(p-1)*(q-1))     #求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
            return d
    print("该方法不适用")


e = 14058695417015334071588010346586749790539913287499707802938898719199384604316115908373997739604466972535533733290829894940306314501336291780396644520926473
n = 33608051123287760315508423639768587307044110783252538766412788814888567164438282747809126528707329215122915093543085008547092423658991866313471837522758159
d=wienerAttack(e,n)
print("d=",d)

Extending Wiener's Attack

扩展维纳攻击是为了扩展到\(n\)个加密指数\(e_i\),且\(d_i\)都较小的情况。 由\(e*d-k*\lambda(N)=1\)得

\[d_ige_i-k_iN=g+k_is\]

记为维纳等式\(W_i\)。

利用 Guo 的方法可得到关系式: \[k_id_je_j-k_jd_ie_i=k_i-k_j\]

记为郭等式\(G_{i,j}\)。注意到两种等式的右侧都非常小。

参考论文和 wiki 中的做法，后续的思路是使用这两个式子的不同关系去构造格，进而格基约化求得\(\phi(N)\)来实现\(N\)的分解。

两个小解密指数

三个小解密指数

低加密指数攻击 e=3

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 *

def dec(c, e, n):
    k = 0
    while True:
        mm = c + n*k
        result, flag = gmpy2.iroot(mm, e)
        if True == flag:
            return result
        k += 1
n= 14067473525623615859223663589118945198091192669401088734569589535726733244095067264729942915265175903139441309376381225701454902095234966599914234681888481774607095853830772571665038109641511499155604914228117882196188074964226780922239011682486198651997912713999544628177959592818928976240251790858062449396082494272361535640237914373270152455829541596341184902017633404494979208958080467979235974182507427501682492000572071306960595992848840147393057648929439822116261337091431441205378542080755128597543738922210525692259529009107645032171097155449558362749512243918901171631681472217935131865121871798425854707759
e= 3
c= 2217344750798294937344050117513831761010547351781457575945714176628679412650463329423466955026804439931765627111856888102133234836914006818023839994342283023142702993182665344445325734299047409223354338948863171846780674244925724334091153701697864918695050507247415283070309

m=dec(c,e,n)
print(long_to_bytes(m))

低加密指数广播攻击

特点是 e 小，有多组 n，对应了多组 c

me = c1 mod n1

me = c2 mod n2

me = c3 mod n3

中国剩余定理(CRT)

定理内容如下

针对上述方程组，若 n1、n2、n3 互质，对于任意的 c1、c2、c3，方程组都有解 m。

使用条件是 m^e < n1、n2、n3。通解推导如下：

设\(N=n_1 \times n_2 \times n_3, N_1=N/n_1, N_2=N/n_2, N_3=N/n_3\)

设\(t_i=N_i^{-1}\),这里表示\(t_i\)是\(N_i\)在模\(n_i\)的逆元。

有了以上几个数，我们可以给出通解形式：

\[m=c_1t_1N_1+c_2t_2N_2+c_3t_3N_3+kN=kN+\sum_{i=1}^3c_it_iN_i\]

在模 N 后，只剩唯一解\(m=\sum_{i=1}^3c_it_iN_i\)

EXP

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
import gmpy2
from sympy.ntheory.modular import crt
from Crypto.Util.number import long_to_bytes
e = 3
n1 = '331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004'
c1 = '310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243'

n2 = '302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114'
c2 = '112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344'

n3 = '332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323'
c3 = '10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242'
c1=int(c1,5)
n1=int(n1,5)
c2=int(c2,5)
n2=int(n2,5)
c3=int(c3,5)
n3=int(n3,5)
e=3
n=[n1,n2,n3]
c=[c1,c2,c3]
resultant,mod= crt(n, c)
# 有现成的库函数可以调用
print(gmpy2.iroot(resultant, e))
m=259362307225540148883586283191025214233097658309244310540770399135748418469298031742173624766441014006294782333
print(long_to_bytes(m))
#noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}

dp、dq 相关

给定 dp、dq 类型

dp ≡ d mod (p-1)

dq ≡ d mod (q-1)

m ≡ cd mod n

m = cd + k * n

m = cd +k _ p _ q

对上式两端同时对 p、q 分别取余，得：（中国剩余定理）

m1 ≡ cd mod p

m2 ≡ cd mod q

同理，可得到 cd = m1 +k * p

代入到 m2 ≡ cd mod q 中：

m2 ≡ (m1 + k * p)mod q ，两端减去 m1 得

m2 - m1 ≡ k * p mod q ，两端乘 p 的逆元得

(m2 - m1)p-1 ≡ k mod q

将 k 代入到 cd = m1 +k * p 中得：

cd = m1 + ((m2 - m1)p-1 mod q) * p

m=cd mod n

得到

m ≡ (((m2 - m1) _ p-1 mod q) _ p + m1) mod n

接下来就是求解 m1，m2

m1 ≡ cdp+k(p-1) mod p

m2 ≡ cdq+k(q-1) mod q

根据费马小定理

若 p 是素数，则 a(p-1) ≡ 1 mod p

因此 m1 ≡ cdp mod p，m2 ≡ cdq mod q

最终可求得 m

EXP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import long_to_bytes
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
m1=pow(c,dp,p)
m2=pow(c,dq,q)
n=p*q
p0=gmpy2.invert(p,q)
m=(((m2-m1)*p0 % q)* p +m1)%n
print(long_to_bytes(m))
#noxCTF{W31c0m3_70_Ch1n470wn}

只给定 dp

dp ≡ d mod (p-1)

ed ≡ 1 mod (p-1) * (q-1)

ed = 1 + k2(p-1)(q-1)

对 1 式两端同乘 e，得

e * dp ≡ ed mod (p-1)

e * dp = k1(p-1) + ed

代入 ed 得

e * dp = k1(p-1) + 1 + k2(p-1)(q-1)

由于两个未知数略显麻烦，发现公因子(p-1)，等式两边同时取余 p-1，即可消掉 n

e * dp ≡ 1 mod (p-1)

e * dp =k(p-1) + 1

得到这个式子后，其实真正意义上的未知数只有我们要求的 p，但是还存在一个 k。

针对 k，我们判断一下他的范围，看看能否采用爆破的方式。

k = (e * dp - 1)/(p-1)

因为 dp < p-1

所以 k < e

通过遍历 k 然后找到(e * dp - 1)可以整除 k 的情况即可。

(跑了一下发现限制条件还不够)

因此再加一个 n 能否整除 p 即可。

EXP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
from Crypto.Util.number import long_to_bytes
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
# p = 13468634736343473907717969603434376212206335187555458742257940406618189481177835992217885676243155145465521141546915941147336786447889325606555333350540003
# q = 18432009829596386103558375461387837845170621179295293289126504231317130550979989727125205467379713835047300158256398009229511746203459540859429194971855371
for k in range(1,e):
    if (e*dp-1)%k == 0:
        p=(e*dp-1)//k + 1
        if n%p == 0:
            print(p)
            break
q=n//p
phi= (p-1)*(q-1)
d= gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
#flag{wow_leaking_dp_breaks_rsa?_98924743502}

DLP

magic(hitcon2021)

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
import os
from Crypto.Util.number import *
from hashlib import *
magic=b'e0204eeaf14d72ab90e1f7ac69559dd182'
LEN = 17
magic = os.urandom(LEN)
print("Magic:", magic.hex())
print('Coud you use it to do encryption as hash?')

magic_num = bytes_to_long(magic)
try:
    N = int(input('N:>'))
    e = int(input('E:>'))
    data = long_to_bytes(int(input('data:>'), 16))
    if N >> (248) == magic_num:
        data2 = sha384(data).digest()
        num1 = bytes_to_long(data)
        num2 = bytes_to_long(data2)
        if pow(num1, e, N) == num2:
            print(os.getenv('FLAG'))
        else:
            print('try harder!!!')
    else:
        print('try harder!')
except Exception as e:
   print('invalid')

EXP

rabin

适用于 RSA 中 e=2 的情况

pqpq(seccon2022)

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
from Crypto.Util.number import *
from Crypto.Random import *
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537

assert n.bit_length() // 8 - len(flag) > 0
padding = get_random_bytes(n.bit_length() // 8 - len(flag))
m = bytes_to_long(padding + flag)

assert m < n

c1p = pow(p, e, n)
c1q = pow(q, e, n)
cm = pow(m, e, n)
c1 = (c1p - c1q) % n
c2 = pow(p - q, e, n)

print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")
# e = 131074
# n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
# c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
# c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
# cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866


大致思路

根据题目，可先通过计算 c1、c2 表达式，合并找出公因子，即可求出 p、q，从而 r 也可求得。 发现 e=65537 * 2，因此是无逆元存在的，索性就将 e 拆分为 65537 与 2，e2=2 时便可通过 Rabin 算法解密。

求 p、q、r

\(c2 = (p - q)^e \mod n \\\) 左右同乘 r \(c2 * r = rp^e + rq^e + X*pqr = rp^e + rq^e \mod n\\\) \(c2 = p^e + q^e \mod n\\\) 同理得到\(c1 = p^e - q^e \mod n \\\) 从而求得 p、q \(p=gcd(c1+c2,n)\\\)

\(q=gcd(c1-c2,n)\\\)

求解 m^2

\(\phi(n)=(p-1)*(q-1)*(r-1)\\\) 通过 e1(e/2)和\(\phi(n)\)求出 d，得到\(cm^d=m^{2*e1*d}=m^2 \mod n\)

Rabin 解密

接下来就是传统 Rabin 解密，找了两种脚本，exp 中的sqrtPrime(n,p)和Tonelli_Shanks(n,p)任选其一即可，都是基于二次剩余定理所实现的解密算法

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import gmpy2
from Crypto.Util.number import *
import random
from itertools import product
def sqrtPrime(n, p):
    q = p - 1
    m = 0
    while q & 1 == 0:
        q >>= 1
        m += 1

    z = 1
    while pow(z, (p - 1) >> 1, p) == 1:
        z = random.randint(1, p - 1)

    c = pow(z, q, p)
    t = pow(n, q, p)
    r = pow(n, (q + 1) >> 1, p)
    if t == 0:
        return 0
    m -= 2
    while t != 1:
        while pow(t, 2**m, p) == 1:
            c = c * c % p
            m -= 1
        r = r * c % p
        c = c * c % p
        t = t * c % p
        m -= 1
    return r

def Legendre(n,p): # 这里用勒让德符号来表示判断二次（非）剩余的过程
    return pow(n,(p - 1) // 2,p)
def Tonelli_Shanks(n,p):
    assert Legendre(n,p) == 1
    if p % 4 == 3:
        print("1")
        return pow(n,(p + 1) // 4,p)
    q = p - 1
    s = 0
    while q % 2 == 0:
        q = q // 2
        s += 1
    for z in range(2,p):
        if Legendre(z,p) == p - 1:
            c = pow(z,q,p)
            break
    r = pow(n,(q + 1) // 2,p)
    t = pow(n,q,p)
    m = s
    if t % p == 1:
        return r
    else:
        i = 0
        while t % p != 1: # 外层循环的判断条件
            temp = pow(t,2**(i+1),p) # 这里写作i+1是为了确保之后内层循环用到i值是与这里的i+1的值是相等的
            i += 1
            if temp % p == 1: # 内层循环的判断条件
                b = pow(c,2**(m - i - 1),p)
                r = r * b % p
                c = b * b % p
                t = t * c % p
                m = i
                i = 0 # 注意每次内层循环结束后i值要更新为0
        return r

e = 131074
e = 65537*2
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866
p = GCD(c1+c2,n)
q = GCD(c1-c2,n)
r = n//(p*q)
phi=(p-1)*(q-1)*(r-1)
d0=gmpy2.invert(65537,phi)
m2=pow(cm,d0,n)
cp=m2%p
cq=m2%q
cr=m2%r
mp=sqrtPrime(cp,p)
mq=sqrtPrime(cq,q)
mr=sqrtPrime(cr,r)

mp=Tonelli_Shanks(cp,p)
mq=Tonelli_Shanks(cq,q)
mr=Tonelli_Shanks(cr,r)

for mp1,mq1,mr1 in product([mp,p-mp],[mq,q-mq],[mr,r-mr]):
    x=[mp1,mq1,mr1]
    y=[p,q,r]
    print(long_to_bytes(crt(y,x)[0]))

#SECCON{being_able_to_s0lve_this_1s_great!}

e 与 phi 不互素

GCD(p-1,e)!=1 GCD(q-1,e)!=1

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
import libnum
from Crypto.Util.number import *
import itertools
n = 3326716005321175474866311915397401254111950808705576293932345690533263108414883877530294339294274914837424580618375346509555627578734883357652996005817766370804842161603027636393776079113035745495508839749006773483720698066943577445977551268093247748313691392265332970992500440422951173889419377779135952537088733
c = 2709336316075650177079376244796188132561250459751152184677022745551914544884517324887652368450635995644019212878543745475885906864265559139379903049221765159852922264140740839538366147411533242116915892792672736321879694956051586399594206293685750573633107354109784921229088063124404073840557026747056910514218246
p = 11104262127139631006017377403513327506789883414594983803879501935187577746510780983414313264114974863256190649020310407750155332724309172387489473534782137699
q=n//p
e=196608
enc=c
N=p*q


def get_oneroot(p, e):
    while True:
        Zp = Zmod(p)
        g = Zp.random_element()
        g = g^((p-1) // e)
        for mult in divisors(e):
            if (mult != e):
                g2 = g^mult
                if (g2 == 1):
                    break
        else:
            return g

def decrypt(p, c, e):
    w = gcd(e, p-1)
    e1, p1 = e // w, (p-1) // w
    d = inverse_mod(e1, p1)
    c1 = pow(c, d, p)
    g, a, b = xgcd(p1, w)
    g = get_oneroot(p, w)
    m = pow(c1, b, p)
    return [ZZ(m * g^i) for i in range(w)]

mp_list = decrypt(p, enc, e)
print('Find root p OK')
mq_list = decrypt(q, enc, e)
print('Find root q OK')
for mp, mq in itertools.product(mp_list, mq_list):
    m = crt([mp, mq], [p, q])
    msg = long_to_bytes(int(m))
    if (b'flag' in msg):
        print(msg)

m^GCD < n

求出\(d*t\)后，对\(m\)开\(t\)次方根。

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
import gmpy2
from Crypto.Util.number import *
import random
flag=b'flag{dsajhkdhsajkdh}'
m=bytes_to_long(flag)
while 1:
    e = random.getrandbits(128)
    p=getPrime(1024)
    q=getPrime(1024)
    n=p*q
    phi_n=(p-1)*(q-1)
    t=gmpy2.gcd(e,phi_n)
    if  gmpy2.invert(e // t, phi_n) and t!=1 and m^t < n:
        break
c=pow(m,e,n)

# decrypt
phi=(p-1)*(q-1)
t=GCD(e,phi)
n=p*q
d=gmpy2.invert(e//t,phi)
m0=pow(c,d,n)
m=gmpy2.iroot(m0,t)
print(long_to_bytes(m[0]))

m^GCD > n

\[t=GCD(e,phi)\] \[d=inverse(e//t,phi)\] \[c=pow(c,d,n)\] 使用 CRT 进行有限域开根 \[x^t\;=c\;mod\;p\] \[x^t\;=c\;mod\;q\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def decrypt(p, q, e, c):
    R.< x > = Zmod(p)[]
    f = x ^ e - c
    f = f.monic()
    res1 = f.roots()

    R.< x > = Zmod(q)[]
    f = x ^ e - c
    f = f.monic()
    res2 = f.roots()

    for i in res1:
        for j in res2:
            m = CRT(int(i[0]), int(j[0]), p, q)
            flag = long_to_bytes(m)
            if b'flag' in flag:
                print(flag)
                print(bytes_to_long(flag))

AMM

适用于\(e\)可整除\(\phi\)的情况

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#Sage
import random
import time
from Crypto.Util.number import *
# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp


e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q
c=10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print(mps, mqs)


def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    if bytes.fromhex(h).startswith(b'flag'):
        print(bytes.fromhex(h))
        return True
    else:
        return False


# About 16 mins to run 0x1337^2 == 24196561 times CRT
start = time.time()
print('Start CRT...')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
    print(time.time() - start)

end = time.time()
print("Finished in {} seconds.".format(end - start))

已知 p^q 和 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
def get_pq(n, x):
    a = [0]
    b = [0]
    maskx = 1
    maskn = 2
    for i in range(1024):
        xbit = (x & maskx) >> i
        nbit = n % maskn
        t_a = []
        t_b = []
        for j in range(len(a)):
            for aa in range(2):
                for bb in range(2):
                    if aa ^ bb == xbit:
                        tmp2 = n % maskn
                        tmp1 = (aa * maskn // 2 + a[j]) * (bb * maskn // 2 + b[j]) % maskn
                        if tmp1 == tmp2:
                            t_a.append(aa * maskn // 2 + a[j])
                            t_b.append(bb * maskn // 2 + b[j])
        maskx *= 2
        maskn *= 2
        a = t_a
        b = t_b
    for a1, b1 in zip(a, b):
        if a1 * b1 == n1:
            return a1, b1

明文相关攻击

1
2
3
assert flag == b"dasctf{" + secret + b"}"
print(rsaencrypt(bytes_to_long(secret)))
print(rsaencrypt(bytes_to_long(flag)))

适用于

$$ C_1=M^e ; mod; n \

C_2=(aM+b)^e ; mod ; n $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x*256+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

for i in range(5,200):
    sl = i*8
    diff = bytes_to_long(b"dasctf{")*2^(sl+8) + bytes_to_long(b"}")
    #print(long_to_bytes(diff))
    v = related_message_attack(C1, C2, diff, e, n)
    v = long_to_bytes(int(v))
    if all(0x20<=k<=0x7f for k in v):
        print(v)
CTF
RSA(持续更新🫡)
https://sch01ar.github.io/2023/04/20/RSA/
作者
Roo1e
发布于
2023年4月20日
许可协议