# RSA ATTACK
## Introduction
Mật mã RSA dựa trên số học modulo đơn giản. RSA có 2 key, Public Key là (n, e) và Private Key là (n, d).
Trong đó:
- n = p * q với p và q là các số nguyên tố
- Để chọn được e thích hợp thì trước hết ta phải tính φ(n) = (p-1) * (q-1)
- e là một số sao cho 1 < e < φ(n) và gcd(e, φ(n)) = 1, hay e và φ(n) sẽ không có ước số chung nào ngoài 1.
- d = inverse(e, φ(n)), hay d * e = k * φ(n) + 1
Giờ ta sẽ 1 plaintext m, để mã hóa m, ta sẽ tính toán c = pow(m, e, n), ta sẽ có được ciphertext.
Và để giải mã ciphertext c, ta sẽ phải có Private Key (n, d), m = pow(c, d, n), ta sẽ thu được plaintext cần tìm.
Thế nếu ta không có Private Key thì tìm plaintext làm sao nhỉ ??? Bây giờ ta sẽ tìm hiểu RSA Attack để tìm hiểu thêm về một số trường hợp có thể tấn công được loại mã hóa này.
## Factorizing the public key
Để có được Private Key để giải mã, ta cần phải có d, và để có d thì ta phải dựa vào cách tính d khi có φ(n) (d * e = k * φ(n) + 1), và để có φ(n) thì ta cần phải biết được p và q.
Nếu số n quá nhỏ (ít hơn 256 bits), ta sẽ factor được số n này. Thế nên nếu muốn tránh loại tấn công này, khuyến cáo nên dùng số n có 2048 bits trở nên.
## Common Modulus
### As an External Attacker
Bây giờ, Alice có 1 plaintext muốn gửi cho Bob và Cock, Bob và Cock sử dụng 2 Public Key khác nhau là (N, eb) và (N, ec). Eva là người tấn công, sẽ lấy được 2 ciphertext là Cb và Cc từ Eva khi gửi cho Bob và Cock. Thế giờ làm sao Eva có thể tìm lại được plaintext m của Alice.
Ta sẽ tính toán gcd(eb, ec), thường thì sẽ là 1. Sử dụng Extended Euclidean Algorithm, ta sẽ tìm được u và v thỏa mãn ``eb*u + ec*v = 1``.
```
Cb = m^eb mod n và Cc = m^ec mod n
Cb^u = m^(u * eb) mod n và Cc^v = m^(v * ec) mod n
---> Cb^u * Cc^v = m^(u * eb) * m^(v * ec) mod n = m^(u * eb + v * ec) mod n = m^1 mod n = m
```
Ví dụ: Ta có 1 message ``m = 600167100838453472459358035297984386711465500705
``
Ta có 2 khóa Public Key như sau
```
n = 19085995833312192524007220630153244389942263922006889142154298425751808612835625879164268530070480609
eb = 31
ec = 71
```
Từ đó ta sẽ thu được 2 ciphertext đó là
```
Cb = 7248000011746393608920764478555324889797098623177063575022710990560749986650254745111540462514063633
Cc = 11182172287733531215626356979925885819483390539286301041874693701292216053376480402307816910743778627
```
Ta sử dụng Extended Euclidean Algorithm sẽ tìm được 2 số u và v thỏa mãn ``eb * u + ec * v = 1``, ta tìm được ``u = -16`` và ``v = 7``
Ta thấy rằng u = -16 < 0 thế nên để có thể tính được Cb^u thì ta cần phải inverse(Cb,n) vì ``Cb^u mod n = Cb^[(-1)*(-u)] mod n = inverse(Cb,n)^(-u) mod n``
Giờ ta sẽ tính được ``m = (pow(inverse(Cb,n),-u,n)*pow(Cc,v,n)) mod n``
Giờ ta sẽ sử dụng python để giải quyết
```
from Crypto.Util.number import*
m = 600167100838453472459358035297984386711465500705
n = 19085995833312192524007220630153244389942263922006889142154298425751808612835625879164268530070480609
eb = 31
ec = 71
cb = 7248000011746393608920764478555324889797098623177063575022710990560749986650254745111540462514063633
cc = 11182172287733531215626356979925885819483390539286301041874693701292216053376480402307816910743778627
u = -16
v = 7
print(long_to_bytes((pow(inverse(cb,n),-u,n)*pow(cc,v,n))%n))
```
Message m = b'i love you so much !'
### Internal Attacker
Ta biết được khóa d phải dựa vào khóa e và φ(n). Trong trường hợp, bạn là nhân viên và được cấp bộ khóa (n,e,d) và có 1 ông sếp có bộ khóa (n, e_boss, d_boss). Chắc chắn là bạn sẽ biết được Public Key của boss rồi, giờ ta cần phải tìm được khóa d_boss của ổng. d_boss của ổng cũng sẽ dùng tới φ(n), thế nhưng ta không thể factor(n) được. Giờ ta sẽ tìm cách tấn công để tìm được khóa d_boss của ông ta.
Ta biết rằng ``k * φ(n) + 1 = d * e`` và ``k_boss * φ(n) + 1 = d_boss * e_boss``. Giờ ta sẽ cần tìm được k để tìm lại được φ(n) là bao nhiêu.
Ta thấy rằng ``k = (e*d - 1) / φ(n) > (e*d - 1) / n`` thế nên ta sẽ tính ``k = (e*d - 1) / n`` rồi cộng dần k lên rồi tính `` φ(n) = (e*d - 1)/k``. Nếu ``k*φ(n) == (e*d - 1)`` thì lúc đó ta sẽ tìm được φ(n).
Ví dụ như sau:
```
n = 13730129614804772880752289462783304761515939015020093221561636131237284843615057420238782770609522972779897464559870880621656031384890245461063527336575063520212170053984927001375709685496305697549444323762540974379841032836802437567934985405376229707618616476496280656706347867221251077231798652699138960795337971736737385768613807271829586487846817128045489170879950650371704605916087898243798748194979988358792610116890529133995964289953754892229284804853347124940125757859317160542053724461336937965356864205941364383726201201464704273080060575612938942759191475849545841070408774846327055098443851402443926907223
e = 65537
d = 12023526690621491987720747738813138281705925752033479867535039126109510878738907188380975357249357354331310487031074808272540111650063873495214869422972969017326039513072751965087711591319689340190429210752033035699428669538381810190600069386757819234172147309193250273418588132622714200732565672475949221035317015770404010091933464449805215046383253499225741965995314055140196259216185504885880375969486528172708580544458731168400724624074591153725513402527961730332556204152427575808471576393264405293657884074056992607573024433121976361451906626453906345264882561858456878706598474749674277815211319553881331985297
e_boss = 65537
```
Ta sẽ sử dụng code như sau:
```
from Crypto.Util.number import*
n = 1249110767794010895540410194153
e = 65537
d = 205119704640110252892051812353
e_boss = 3
k = (e*d - 1)//n
while True:
phi = (e*d - 1)//k
if phi*k == e*d - 1:
print("Found k:",k)
print("Found φ(n):", phi)
break
else:
k +=1
```
Ta có challenge thực chiến như sau
```
from Crypto.Util.number import*
p, q = getPrime(128), getPrime(128)
phi = (p-1)*(q-1)
print("p =", phi)
n = p*q
m = 600167100838453472459358035297984386711465500705
e = 65537
c = pow(m,e,n)
print("c =", c)
print("n =", n)
while True:
print("1. Nhap e cua ban")
print("2. Nhap khoa de gia ma")
inp = int(input())
if inp == 1:
ur_e = int(input("Nhap e: "))
print("Your private key: ")
print(inverse(ur_e,phi))
if inp == 2:
ur_d = int(input("Nhap d: "))
print("ur_p =", pow(c,ur_d,n))
```
Ta sẽ chọn e = 7, ta sẽ thu được khóa d với e = 7, từ đó ta có thể tìm được khóa d với e = 65537 vì m được mã hóa dựa vào e = 65537.
Từ đó ta tìm được ``φ(n) == 85639416467718659540681409319173517244166085303068104368992831187016124610080``, từ đó ta tìm được khóa d với e = 65537.
Nhập khóa d vào mục 2, ta sẽ thu được m cần tìm.
## Decipher oracle
Cách tấn công này hay còn gọi là Blinding attack.
Ví dụ như sau: Bạn có 1 tin nhắn m là "Send me $2 dollars" và nếu muốn đưa cho kế toán thì phải có chữ ký của boss, thế nhưng boss không ngu mà ký vào, thế nên ta cần phải lấy m' để đánh lừa boss ngu này, bằng cách như sau
Ta có ``c = pow(m,e,n)``, ta sẽ gửi ``c' = (pow(r, e, n)*c) % n ``, khi đó boss sẽ ký vào bằng khóa d của mình ``S = pow(c', d, n) = r*pow(c,d,n)``, khi đó ta chỉ cần lấy S//r là sẽ thu được m.
Đọc hơi khó hiểu đúng không, thử ví dụ này nha
```
from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes
f = open("flag.txt").read()
m = bytes_to_long(f.encode())
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 65537
c = pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)
d = pow(e, -1, (p-1)*(q-1))
c = int(input("Text to decrypt: "))
if c == m or b"KCSC{" in long_to_bytes(pow(c, d, n)):
print("No flag for you!")
exit(1)
print("m =", pow(c, d, n))
```
Ta sẽ được mã hóa của flag, public key. Giờ ta sẽ nhập 1 số để decrypt mà khi giải mã không được có ký tự của flag trong đó. Nghe có vẻ no hope, nhưng giờ ta chỉ cần gửi ``pow(r,e,n)*c`` thì sẽ thu được m' = m*r, sau đó sẽ thu được flag thui.
Mình sẽ lấy r bằng 2, sau đó lấy các khóa rùi làm như trên thui.
Giờ nhập số đó vào để decrypt rồi lấy ra chia cho 2.
Ta thu được flag rùi :heartpulse:
## Small public exponent
Nếu bạn có 1 quả n rất mạnh và lớn, thế nhưng chỉ lấy e = 3 thì cũng coi như là không mã hóa =)))
Ta có 1 plaintext m, so với n thì m rất nhỏ và m^3 cũng nhỏ hơn n, thế nên ``pow(m,3,n)`` cũng chính bằng m^3. Thế nên ta chỉ cần căn bậc 3 là sẽ thu được m thui.
## Hastad’s Broadcast Attack
Loại tấn công này cũng khá giống Small public exponent, thế nhưng message đã lớn hơn và gửi cho nhiều người với cùng 1 e.
Giả sử với e = 5, M = m^5, ta có được rằng
```
M ≡ C1[N1]
M ≡ C2[N2]
M ≡ C3[N3]
```
Giờ ta sẽ dùng [Thặng dư Trung Hoa](https://github.com/trananhnhatviet/CryptoHack/blob/main/Mathematics/04_Chinese_Remainder_Theorem.md) để tấn công nhaaa.
```
from gmpy2 import iroot
from Crypto.Util.number import*
e = 5
n1 = 95118357989037539883272168746004652872958890562445814301889866663072352421703264985997800660075311645555799745426868343365321502734736006248007902409628540578635925559742217480797487130202747020211452620743021097565113059392504472785227154824117231077844444672393221838192941390309312484066647007469668558141
n2 = 98364165919251246243846667323542318022804234833677924161175733253689581393607346667895298253718184273532268982060905629399628154981918712070241451494491161470827737146176316011843738943427121602324208773653180782732999422869439588198318422451697920640563880777385577064913983202033744281727004289781821019463
n3 = 68827940939353189613090392226898155021742772897822438483545021944215812146809318686510375724064888705296373853398955093076663323001380047857809774866390083434272781362447147441422207967577323769812896038816586757242130224524828935043187315579523412439309138816335569845470021720847405857361000537204746060031
c1 = 44643885876928229894339687791147483889081873683080948952473220411937240291600604967009102215608200081775074249286001453402825883292279665567678123214807611531941351394608697836776234093223777794346332632216833837995399934797886939033689918289531745909283564566484245521666625007898978941078860669318735325434
c2 = 44143117410059647762095913003262912479704737449712953561967268794930036228463178516548026385008346137693280641753063385660830541131352911139821249120800415441910930574199714264780097158205338261528246884217457601137849376649972995621085773416683024133527965327866632045455956019650455063878227433961529064296
c3 = 43758298724220182639918572113571637071082391732944709390663779379112331840911652803134604996621805027217904388017247167682937227278450493841176029741223145586984980660890778932371017310827918656251333087908084340461067839975909450067417000566279146533723691038158029229130115336369769056411536254398779305744
N = n1*n2*n3
N1 = n2*n3
N2 = n1*n3
N3 = n1*n2
u1 = inverse(N1,n1)
u2 = inverse(N2,n2)
u3 = inverse(N3,n3)
x = (N1*c1*u1 + N2*c2*u2+ N3*c3*u3) % N
print(long_to_bytes(iroot(x,5)[0]))
```
## Fermat’s attack
Nếu p và q đều có độ dài bit như nhau, và nếu chọn quá gần nhau, thì sẽ bị tấn công Fermat.
Thực chất, nếu p - q < n^(1/4) thì có thể sử dụng thuật toán Fermat Factoring để tìm lại được p và q.
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mi>n</mi>
<mo>=</mo>
<mi>p</mi>
<mi>q</mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mo stretchy="false">(</mo>
<mi>p</mi>
<mo>−</mo>
<mi>q</mi>
<mo stretchy="false">)</mo>
<mrow data-mjx-texclass="ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<msup>
<mo stretchy="false">)</mo>
<mn>2</mn>
</msup>
<mo>−</mo>
<mo stretchy="false">(</mo>
<mo stretchy="false">(</mo>
<mi>p</mi>
<mo>+</mo>
<mi>q</mi>
<mo stretchy="false">)</mo>
<mrow data-mjx-texclass="ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<msup>
<mo stretchy="false">)</mo>
<mn>2</mn>
</msup>
<mo>=</mo>
<msup>
<mi>x</mi>
<mn>2</mn>
</msup>
<mo>−</mo>
<msup>
<mi>y</mi>
<mn>2</mn>
</msup>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>−</mo>
<mi>y</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>+</mo>
<mi>y</mi>
<mo stretchy="false">)</mo>
</math>
Giờ để tìm lại được p và q thì ta có thể sử dụng thuật toán [Fermat Factoring](https://en.wikipedia.org/wiki/Fermat's_factorization_method) này.
Ngoài ra khi ta gặp những challenge RSA dạng tấn công này, ta có thể sử dụng tools factordb.com (có lúc hong được nha) hoặc có thể sử dụng các tools RSA trên github.
## Wiener’s attack
Bạn tham khảo trước tại [đây](https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2/)
Điều kiện để có thể sử dụng cách tấn công này là:
Chứng minh:
- Từ phương trình trên, ta có thể thấy được rằng ta không có φ(n), thế nên ta có thể thay φ(n) thành n để tính xấp xỉ của nó. ---> ``|e/n - k/d|``
- Ta có ``φ(n) = n - p - q + 1`` ---> ``|n - φ(n)| < p + q`` ``C4``
- Từ ``C4``, ta có ``|n - φ(n)| < 3√n`` ``C5``
- Từ đó ta được
- Và ta sẽ được
- Bây giờ ta sử dụng [Phân số liên tục](https://en.wikipedia.org/wiki/Continued_fraction), khai triển e/n để có các cặp k/d.
- Giờ có các k và d rồi, ta có thể tính được φ(n). Thử lại và cho tới khi nào đúng thì thui nhaaaa.
## Brute force attack on small secret CRT-Exponents
Ta có được rằng: ``dp = inverse(e, p-1)`` và ``dq = inverse(e, q-1)``. Nếu ta chọn khóa e không chuẩn, thì dp và dq có thể nhỏ đến mức có thể tấn công bruteforce.
Ta dùng dp đi haa, ta có: ``dp * e = 1 + k*(p-1)``, ta sẽ lấy 1 số r random sao cho ``gcd(r, p) = 1``. Ta thấy được rằng ``pow(r, e * dp, p) = pow(r, 1 + k * (p-1), p)`` tương đương với ``(r*pow(r, (p-1)^k, p))%p`` và theo Fermat’s little theorem thì ta sẽ thu được ``(r*pow(1, k, p))%p`` và bằng ``r % p``.
Thế nên, ta sẽ có được ``r - r^(e * dp) = k*p``, tương đương với ``(r%p - r%p)%p = 0%p``. Và tất nhiên rồi, ``gcd(n, r - r^(e * dp)) == p`` nếu output là số nguyên tố.
Ta có ví dụ như sau
```
import gmpy2
n = 81456722852928757238261542127151102587173197229707943752219811543156144375350699863083294551705799070878004194003070546338822440089905539549140825586980363561718569628995744214852601849629950615868613439865290355111413520845496729201667637139574520862615047519950667612227571310144108603794433291057865431359
e = 2446203909239906238862878052950988270795071430744877628420149012221572250593484910179302246981591737101667586509709578361904594855170615249056999067468389
# lấy đại r nha
r = 7516789928765
for dp in range(1000000):
f = gmpy2.gcd(r - pow(r, e*dp, n), n)
if f > 1:
print(dp,f)
break
```
Mình chạy bằng sage cho nhanh và có kết quả như sau
Check lại thui nàoo
## Fault attack on signatures
Đây sẽ là cách tấn công RSA CRT signing.
Ta thấy rằng, plaintext m, thay vì sign với n lun, thì đây sẽ sign với từng số nguyên tố, sau đó dùng CRT để đưa ra signature s cuối cùng với n.
Các khóa lần lượt là: ``dp = inverse(e,p)`` và ``dq = inverse(e,q)``.
Tiếp theo đó ta sẽ sign từng khóa với message ``sq = pow(m, dq, q)`` và ``sp = pow(m, dp, p)``.
Sau đó dùng CRT sẽ thu được signature cuối cùng.
Quá trình xác minh nếu như không có bất kỳ lỗi gì trong quá trình tính toán chữ ký qua sp và sq thì sẽ như sau:
Điều này có nghĩa là ``s^e - m`` sẽ là bội của cả p và q, tương đương ``gcd(pow(s, e, n) - m, n) == n``
Thế nhưng, khi chỉ cần 1 phần sign với p hoặc q bị lỗi 1 bit hoặc là nhiều bits, ta sẽ thấy ngay 1 điều nguy hiểm
Nếu ta bị lỗi với sp thì``s^e - m``sẽ chỉ chia hết cho q và ngược lại, thế nên chỉ cần``gcd(pow(s, e, n) - m, n)``ta sẽ thu được 1 trong 2 số nguyên tố.
Ta có ví dụ như sau
```
from Crypto.Util.number import*
from functools import reduce
import gmpy2
with open("flag.txt", "rb") as file:
flag = file.read()
print(flag)
p, q = getPrime(1024), getPrime(1024)
e = 65537
n = p*q
d = inverse(e,(p-1)*(q-1))
c = pow(bytes_to_long(flag), e, n)
print("n =",n)
print("e =",e)
print("c =",c)
def chinese_remainder(rests, modulus):
somme = 0
prod = reduce(lambda a, b: a * b, modulus)
for n_i, a_i in zip(modulus, rests):
p = prod // n_i
somme += a_i * gmpy2.invert(p, n_i) * p
return int(somme % prod)
def sign(m, fault = False):
dp = inverse(e,p-1)
dq = inverse(e,q-1)
sp = pow(m, dp, p)
sq = pow(m, dq, q)
if fault:
sq += 1
s = chinese_remainder([sp, sq], [p, q])
return s
while True:
m = int(input("Nhap m = "))
print(sign(m,True))
```
Ta chạy code thì thu được n và e (không hề biết p và q), ta sẽ lấy 1 message ngẫu nhiên và để mode fault là True, ta sẽ thu được 1 sign, giờ ta sẽ lấy sign đó mũ e và trừ đi cho m, lấy ước chung lớn nhất, ta sẽ thu được số nguyên tố.
## Parity Oracle
Giờ ta có 1 challenge như thế này:
```
from Crypto.Util.number import *
from os import urandom
flag = (395666745139103690621251672998591647401211535741)
p,q = getPrime(512),getPrime(512)
n = p*q
e = 0x10001
d = inverse(e,(p-1)*(q-1))
assert flag < n
ct = pow(flag, e, n)
print(f"{n = }")
print(f"{e = }")
print(f"{ct = }")
while True:
ct = int(input("> "))
pt = pow(ct, d, n)
out = ""
if pt == flag:
exit()
else:
if pt % 2 == 0:
print("Even")
else:
print("Odd")
```
Như Blinding Attack, ta sẽ gửi 1 ciphertext vào, thế nhưng đầu ra không phải là ký với Private Key mà chỉ có là bit 1 và 0 thì ta làm như thế nào ???
Giờ ta tìm hiểu các tấn công LSB.
Ta biết rằng, N luôn luôn là số lẻ vì được nhân bởi 2 số nguyên tố. Và 1 số a chẵn mod cho số lẻ b mà ra số lẻ thì a < b. Tương đương, nếu mod mà ra chẵn thì ``a > b``.
Tương đương như thế, ta sẽ gửi ct sao cho khi giải mã bằng khóa d sẽ bằng 2p. Khi đó, ta có 2 trường hợp:
- 2p < n thì modulo sẽ không hoạt động và sẽ trả về Even
- 2p > n thì modulo sẽ trả về là Odd
Ta biết rằng, khi p sẽ ∈ [0,n]. Thế nên, nếu ``2p > n`` --> ``p > n/2`` --> ``p ∈ [n/2, n]``. Còn nếu ``2p < n`` --> ``p ∈ [0, n/2]``. Thế ta sẽ gửi dần 2, 4, 8, 16, .... nha
Ta sẽ bo dần độ rộng của p dựa vào đường [link](https://crypto.stackexchange.com/questions/11053/rsa-least-significant-bit-oracle-attack) này.
Dựa vào đó, ta có source sau đây
```
from pwn import*
from binascii import*
from Crypto.Util.number import*
import base64
from Crypto.Util.number import*
def get_process():
return remote("localhost", 1337)
def oracle(x):
io.sendlineafter(b'> ', str(pow(x, e, n) * ct % n).encode())
return io.recvline()
io = get_process()
e = 65537
io.recvuntil(b'n = ')
n = int(io.recvuntil(b"\n").decode())
io.recvuntil(b'ct = ')
ct = int(io.recvuntil(b"\n").decode())
lb = 0
ub = n
k = 1
while True:
k *= 2
if oracle(k) == b"Even\n":
ub = ((ub + lb )//2)
else :
lb = ((ub+lb)//2)
if (ub - lb) < 65537:
print(int(ub),int(lb))
break
```
Ta thu được 2 số ``395666745139103690621251672998591647401211504165`` và ``395666745139103690621251672998591647401211539815`` khá gần với flag là ``395666745139103690621251672998591647401211535741``. Thế nên ta chỉ cần bruteforce trong khoảng đó là sẽ thu được flag nha.
***Tham khảo***
https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/
https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2/
https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-3/
https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-4/
# RSA CHALLENGE CRYPTOHACK
## STARTER
### RSA Starter 1
Chall này chỉ cần sử dụng sage, hoặc là dùng code python để lấy được đáp án thôi.
> 19906
### RSA Starter 2
Chall này cho ta hiểu được cách mã hóa của rsa thui.
> 301
### RSA Starter 3
Chall này nói về cách tính Φ(n) trong mã hóa rsa.
``Φ(n) = (p-1)*(q-1)``
> 882564595536224140639625987657529300394956519977044270821168
### RSA Starter 4
Chall hướng dẫn ta cách tính khóa d khi đã có phi và e.
> 121832886702415731577073962957377780195510499965398469843281
### RSA Starter 5
Chall này sẽ chỉ cho ta cách giải mã khi đã có Private Key và Public Key. Giờ ta chỉ cần ``pow(c,d,p*q)`` là sẽ giải mã được ciphertext.
> 13371337
### RSA Starter 6
Chall này sẽ chỉ cho ta cách sign message với private key thui. Ngoài ra sẽ phải sha256 flag trước khi signing.
```
from hashlib import sha256
from Crypto.Util.number import*
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
flag = b'crypto{Immut4ble_m3ssag1ng}'
flag = bytes_to_long(sha256(flag).digest())
c = pow(flag,d,N)
print(c)
```
> 13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475
## PRIMES PART 1
### Factoring
Chall này phải phân tích 1 số thành các nhân tử nguyên tố.
Đề cho ta 1 con số rất lớn là ``510143758735509025530880200653196460532653147``
Để giải được bài này, ta lên website http://factordb.com/, đây là 1 trang web giúp ta phân tích số thành các nhân tử nguyên tố
Nhập số vào và ta được 2 số là ``19704762736204164635843`` và ``25889363174021185185929``
Và số nhỏ hơn là ``19704762736204164635843``
> 19704762736204164635843
### Inferius Prime
Chall này khá giống với RSA Starter 5, chỉ decode plaintext thành bytes
Chall cho ta 1 file output.txt gồm:
```
n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373
```
Từ n, ta factor được
```
p = 752708788837165590355094155871
q = 986369682585281993933185289261
```
Tiếp theo ta tính phi ``phi = (p-1)*(q-1)``
Tìm private key ``d = inverse(e,phi)``
``Plaintext = pow (ct,d,n)``
Khi ta đã có được plaintext là 1 số nguyên lớn, ta decode nó sang byte ``decrypted = long_to_bytes(plaintext)``
Decrypted chính là flag cần tìm
```
from Crypto.Util.number import *
n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373
p = 752708788837165590355094155871
q = 986369682585281993933185289261
phi = (p-1)*(q-1)
d = inverse (e,phi)
pt = pow(ct, d, n)
pt = long_to_bytes(pt).decode()
print(pt)
```
> crypto{N33d_b1g_pR1m35}
### Monoprime
Chall này cho ta hiểu vì sao phải dùng 2 số nguyên tố p và q trong mật mã RSA
Ta có ``c = pow(p, e, n)``. Mà n lại chính là 1 số nguyên tố --> ``Φ(n) = (n-1)``
Đã có phi rồi thì ta chỉ cần tìm lại khóa d rồi lụm flag thui
```
from Crypto.Util.number import *
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
phi = n-1
d = inverse (e,phi)
pt = pow(ct, d, n)
pt = long_to_bytes(pt).decode()
print(pt)
```
> crypto{0n3_pr1m3_41n7_pr1m3_l0l}
### Square Eyes
Chall này cho ta hiểu về cách tấn công rsa khi ``n = p*q`` và ``p = q``.
Từ công thức này, ta có ``φ(n) = φ(p^2) = p*(p-1)``
Giờ có φ(n) rồi thì lụm flag thui nào
```
from Crypto.Util.number import *
from math import isqrt
N = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
c = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p = isqrt(N)
phi = (p)*(p-1)
d = inverse(e, phi)
plaintext = pow(c, d, N)
decrypted = long_to_bytes(plaintext).decode()
print(decrypted)
```
> crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}
### Manyprime
Chall này ta factor n thì thu được rất nhiều số nguyên tố.
Theo công thức: ``φ(n) = (p1-1)*(p2-1)*...*(pn-1)``
Giờ ta tính φ(n) rồi lụm flag thui
```
from Crypto.Util.number import inverse, long_to_bytes
N = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ciphertext = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
s='9282105380008121879<20> · 9303850685953812323<20> · 9389357739583927789<20> · 10336650220878499841<20> · 10638241655447339831<20> · 11282698189561966721<20> · 11328768673634243077<20> · 11403460639036243901<20> · 11473665579512371723<20> · 11492065299277279799<20> · 11530534813954192171<20> · 11665347949879312361<20> · 12132158321859677597<20> · 12834461276877415051<20> · 12955403765595949597<20> · 12973972336777979701<20> · 13099895578757581201<20> · 13572286589428162097<20> · 14100640260554622013<20> · 14178869592193599187<20> · 14278240802299816541<20> · 14523070016044624039<20> · 14963354250199553339<20> · 15364597561881860737<20> · 15669758663523555763<20> · 15824122791679574573<20> · 15998365463074268941<20> · 16656402470578844539<20> · 16898740504023346457<20> · 17138336856793050757<20> · 17174065872156629921<20> · 17281246625998849649'
lst=s.split('<20> · ')
factor_list=[]
for i in lst:
factor_list.append(int(i))
phi = 1
for prime in factor_list:
phi = phi * (int(prime) - 1)
d = inverse(e, phi)
plaintext = pow(ciphertext, d, N)
print(long_to_bytes(plaintext).decode())
```
> crypto{700_m4ny_5m4ll_f4c70r5}
## PUBLIC EXPONENT
### Salty
Source code của chall như sau:
```
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
e = 1
d = -1
while d == -1:
p = getPrime(512)
q = getPrime(512)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
n = p * q
flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
```
Ta thấy ``e = 1`` --> Nếu flag < n thì sau khi mã hóa, ct chính là flag do không bị ảnh hưởng.
Giờ ta chỉ cần decode ct ra byte là thu được flag thôi
> crypto{saltstack_fell_for_this!}
### Modulus Inutilis
Source code của chall như sau:
```
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
e = 3
d = -1
while d == -1:
p = getPrime(1024)
q = getPrime(1024)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
n = p * q
flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
```
Chall này thấy được e = 3, và số n rất chi là to lun, thế nên ``flag^3 < n`` thì mã hóa sẽ không ảnh hưởng tới flag. Giờ chỉ cần căn bậc 3 của ct là ta sẽ thu được flag thuiii
> crypto{N33d_m04R_p4dd1ng}
### Everything is Big
Chall này cho ta quả output rất chi là to lunn
```
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
Sau khi thấy output to như này, mình nghĩ ngay tới owiener attack.
Đoạn code sẽ như sau
```
import owiener
from Crypto.Util.number import long_to_bytes
N = int('0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d',16)
e = int('0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3',16)
c = int('0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474',16)
d = owiener.attack(e,N)
m = pow(c,d,N)
print(long_to_bytes(m).decode())
```
> crypto{s0m3th1ng5_c4n_b3_t00_b1g}
### Crossed Wires
```
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime
FLAG = b"crypto{????????????????????????????????????????????????}"
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)
my_key = (N, d)
friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]
cipher = bytes_to_long(FLAG)
for key in friend_keys:
cipher = pow(cipher, key[1], key[0])
print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")
```
Chall này sẽ mã hóa 6 lần, với 6 lần e khác nhau, thế nên ta cần phải bruteforce φ(n) để có thể tìm lại được khóa d tương ứng.
```
n,d = (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
e = 65537
k = (e*d - 1)//n
while True:
phi = (e*d - 1)//k
if phi*k == e*d - 1:
print("Found φ(n):", phi)
break
else:
k +=1
```
```
φ(n) = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280249307490374900729021320924716697863966277266625488626020771604596923670543560857724741855180400786259195735908618899535592322919617065525626834782656528352786625383923291590279348919015437292702452668873586799771898145386750557481851748649545280807708561842706253359025121644739401403945728547286791397492272
```
Giờ khóa d sẽ lần lượt là inverse(e,phi), làm ngược lại là được thoiooiii :v:
```
from Crypto.Util.number import*
n,d = (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
e = 65537
c = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
k = (e*d - 1)//n
while True:
phi = (e*d - 1)//k
if phi*k == e*d - 1:
print("Found φ(n):", phi)
break
else:
k +=1
friend_keys = [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
for key in friend_keys:
d_friend = inverse(key[1], phi)
c = pow(c,d_friend,key[0])
print(long_to_bytes(c).decode())
```
> crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}
### Everything is Still Big
Source code của chall như sau
```
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd
FLAG = b"crypto{?????????????????????????????????????}"
m = bytes_to_long(FLAG)
def get_huge_RSA():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
while True:
d = getrandbits(512)
if (3*d)**4 > N and gcd(d,phi) == 1:
e = inverse(d, phi)
break
return N,e
N, e = get_huge_RSA()
c = pow(m, e, N)
print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')
```
Ban đầu mình tưởng là dạng Wiener attack, mình thử thì vẫn được, nhưng sau khi tìm hiểu thì nó là dạng ``Boneh-Durfee Attack`` với ``d < N^0.292``. Bạn cũng có thể tham khảo tại [đây](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/boneh-durfee-attack).
Chall này bạn vẫn có thể factor N trên factordb được, hoặc cũng có thể tấn công Wiener được, nhưng mình sợ nếu gặp lại chall này nhưng mà thay số khác thì sẽ không có được, nên bạn nên tham khảo source code sau đây hoặc tại [link](https://raw.githubusercontent.com/mimoo/RSA-and-LLL-attacks/master/boneh_durfee.sage) này:
```
from __future__ import print_function
import time
############################################
# Config
##########################################
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
############################################
# Functions
##########################################
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1
print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print(a)
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
# end of our recursive function
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB
# we start by checking from the end
for ii in range(current, -1, -1):
# if it is unhelpful:
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# let's check if it affects other vectors
for jj in range(ii + 1, BB.dimensions()[0]):
# if another vector is affected:
# we increase the count
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# level:0
# if no other vectors end up affected
# we remove it
if affected_vectors == 0:
print("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# level:1
# if just one was affected we check
# if it is affecting someone else
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# if it is affecting even one vector
# we give up on this one
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# remove both it if no other vector was affected and
# this helpful vector is not helpful enough
# compared to our unhelpful one
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
print("* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# nothing happened
return BB
"""
Returns:
* 0,0 if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May
finds a solution if:
* d < N^delta
* |x| < e^delta
* |y| < e^0.5
whenever delta < 1 - sqrt(2)/2 ~ 0.292
"""
# substitution (Herrman and May)
PR.<u, x, y> = PolynomialRing(ZZ)
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()
UU = XX*YY + 1
# x-shifts
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()
# x-shifts list of monomials
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort()
# y-shifts (selected by Herrman and May)
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution
# y-shifts list of monomials
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)
# construct lattice B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
# Prototype to reduce the lattice
if helpful_only:
# automatically remove
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# reset dimension
nn = BB.dimensions()[0]
if nn == 0:
print("failure")
return 0,0
# check if vectors are helpful
if debug:
helpful_vectors(BB, modulus^mm)
# check if determinant is correctly bounded
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print("We do not have det < bound. Solutions might not be found.")
print("Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print("size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
# display the lattice basis
if debug:
matrix_overview(BB, modulus^mm)
# LLL
if debug:
print("optimizing basis of the lattice via LLL, this can take a long time")
BB = BB.LLL()
if debug:
print("LLL is done!")
# transform vector i & j -> polynomials 1 & 2
if debug:
print("looking for independent vectors in the lattice")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# for i and j, create the two polynomials
PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
# resultant
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print("no independant vectors could be found. This should very rarely happen...")
return 0, 0
rr = rr(q, q)
# solutions
soly = rr.roots()
if len(soly) == 0:
print("Your prediction (delta) is too small")
return 0, 0
soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
#
return solx, soly
def example():
############################################
# How To Use This Script
##########################################
#
# The problem to solve (edit the following values)
#
# the modulus
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
# the hypothesis on the private exponent (the theoretical maximum is 0.292)
delta = .18 # this means that d < N^delta
#
# Lattice (tweak those values)
#
# you should tweak this (after a first run), (e.g. increment it until a solution is found)
m = 4 # size of the lattice (bigger the better/slower)
# you need to be a lattice master to tweak these
t = int((1-2*delta) * m) # optimization from Herrmann and May
X = 2*floor(N^delta) # this _might_ be too much
Y = floor(N^(1/2)) # correct if p, q are ~ same size
#
# Don't touch anything below
#
# Problem put in equation
P.<x,y> = PolynomialRing(ZZ)
A = int((N+1)/2)
pol = 1 + x * (A + y)
#
# Find the solutions!
#
# Checking bounds
if debug:
print("=== checking values ===")
print("* delta:", delta)
print("* delta < 0.292", delta < 0.292)
print("* size of e:", int(log(e)/log(2)))
print("* size of N:", int(log(N)/log(2)))
print("* m:", m, ", t:", t)
# boneh_durfee
if debug:
print("=== running algorithm ===")
start_time = time.time()
solx, soly = boneh_durfee(pol, e, m, t, X, Y)
# found a solution?
if solx > 0:
print("=== solution found ===")
if False:
print("x:", solx)
print("y:", soly)
d = int(pol(solx, soly) / e)
print("private key found:", d)
else:
print("=== no solution was found ===")
if debug:
print(("=== %s seconds ===" % (time.time() - start_time)))
if __name__ == "__main__":
example()
```
> crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}
### Endless Emails
Source code của chall đây
```
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages
def RSA_encrypt(message):
m = bytes_to_long(message)
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 3
c = pow(m, e, N)
return N, e, c
for m in messages:
N, e, c = RSA_encrypt(m)
print(f"n = {N}")
print(f"e = {e}")
print(f"c = {c}")
```
Mình thấy có rất nhiều output gồm n, e, c. Mình thử dùng CRT với 3 bộ đầu tiên thì thấy không thu được gì, thế nên mình đã thử hết tất cả các trường hợp 3 bộ. Sau đó sẽ dùng CRT để xem cái nào căn bậc 3 sẽ trả về TRUE.
```
data = """
n = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
e = 3
c = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
e = 3
c = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
e = 3
c = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
e = 3
c = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
e = 3
c = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
e = 3
c = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
e = 3
c = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
"""
data = data.split("\n")
lst_n = []
lst_c = []
for i in data:
if "n" in i:
lst_n.append(int(i.replace("n = ","")))
if "c" in i:
lst_c.append(int(i.replace("c = ","")))
print(lst_c)
print(lst_n)
```
```
from sage.all import*
from itertools import combinations
lst_c = [6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225, 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172, 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153, 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577, 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805, 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749, 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144]
lst_n = [14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021, 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123, 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147, 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961, 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823, 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263, 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897]
choices = [(x, y) for x, y in zip(lst_c, lst_n)]
triples = list(combinations(choices, 3))
print(triples)
ans = []
for i in triples:
c = [x[0] for x in i]
n = [x[1] for x in i]
l = crt(c, n)
l = pow(l, 1/3)
if(l.is_integer()):
print(bytes.fromhex(hex(l)[2:]))
```
> crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}
## PRIMES PART 2
### Infinite Descent
Source code của chall sẽ như sau
```
import random
from Crypto.Util.number import bytes_to_long, isPrime
FLAG = b"crypto{???????????????????}"
def getPrimes(bitsize):
r = random.getrandbits(bitsize)
p, q = r, r
while not isPrime(p):
p += random.getrandbits(bitsize//4)
while not isPrime(q):
q += random.getrandbits(bitsize//8)
return p, q
m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
Ta thấy rằng, ban đầu p và q đều bằng r, thế nhưng nếu chưa là số nguyên tố thì p và q sẽ cộng thêm 1 số nhỏ hơn. Thế nên, p và q sẽ rất gần nhau.
Mình thử lấy thử 2 số p q thì sẽ thấy được
```
from gmpy2 import iroot
p = 2472821142620574019830186301893550269217348973615161682839123365686833286218185919375748583753835314573675041708248293197071862365303277003452257786419780575704976455189074575818952641950066572636488531007468343917336049549777576371227790588540886976946928067638611533089826599659226222811809718780151634661236042917475169461434815000805260920821783771376771298168412750315093762852176130992606156043143166330732747127246383040897710070406271294750339982844642505220750453075739089254063543852221083290521949188996908542257340501676666356123431729225686209081590038743715108230514746279388032476992037937034839823131
q = 2472821142620574019830186301893550269217348973615161682839123365686833286218185919375748583753835314573675041708248293197071862365303277003452257786419780575704976455189074575818952641950066572636488531007468343917336049549777576371227790588540886976946928067638611533089826599659226222811809718780151634661236042917475169461434815000805260920821783771376771298168412750315093762852176130992606156043143166330732747127246383040897710070406271294750339982844634159308964759610469302551028504388758969047272579699134196924099063326032649063096442708019230510714578264458605661791405520843295913192449859941582014158713
n = p*q
print(iroot(n,4)[0] > abs(p-q))
```
Ta thấy được ``p - q < n^(1/4)`` --> Ta sẽ tấn công Fermat nha.
Đọc hiểu thuật toán [Fermat](https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2/)
Sử dụng source code này để factor N nha
```
import sympy
from sympy.ntheory.primetest import is_square
def fermat(n):
a = int(sympy.sqrt(n)) # Fermat's Algorithm
b = (a*a) - n
while not is_square(b):
a += 1
b = (a*a) - n
else:
p = int(a - (sympy.sqrt(b)))
q = n//p
if p * q == n:
return p,q
else:
return "No Luck"
```
Giờ ta có p và q rồi thì sẽ làm như bình thường thui nha :v:
```
import sympy
from Crypto.Util.number import*
from sympy.ntheory.primetest import is_square
def fermat(n):
a = int(sympy.sqrt(n)) # Fermat's Algorithm
b = (a*a) - n
while not is_square(b):
a += 1
b = (a*a) - n
else:
p = int(a - (sympy.sqrt(b)))
q = n//p
if p * q == n:
return p,q
else:
return "No Luck"
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
p, q = (fermat(n))
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)).decode())
```
Ngoài ra giờ tools nào cũng chơi được dạng này nên vất vào tool cho nhanh.
> crypto{f3rm47_w45_4_g3n1u5}
### Marin's Secrets
Source code của chall như sau:
```
import random
from Crypto.Util.number import bytes_to_long, inverse
from secret import secrets, flag
def get_prime(secret):
prime = 1
for _ in range(secret):
prime = prime << 1
return prime - 1
random.shuffle(secrets)
m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
Ta thấy rằng, có 1 hàm get_prime lạ so với bình thường, mình phân tích hàm này nha.
```
p = 1
for i in range(10):
p = p << 1
print(p)
```
Output là 1024 = 2^10. Hóa ra là hàm này sẽ là trả về 1 số nguyên tố có dạng là ``2^n - 1``. Sau thời gian tra google thì mình tìm được quả [link](https://en.wikipedia.org/wiki/Mersenne_prime) này
Chall này ta sẽ bruteforce số lần chạy của vòng for, nếu thu được 2 số nhân với nhau bằng n thì sẽ trả về p và q.
```
from Crypto.Util.number import*
def find_prime(n):
p = 1
for i in range(3000):
p = p << 1
q = 1
for j in range(3000):
q = q << 1
if (p-1)*(q-1) == n:
return (p-1,q-1)
n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
e = 65537
p, q = find_prime(n)
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)).decode())
```
> crypto{Th3se_Pr1m3s_4r3_t00_r4r3}
### Fast Primes
```
import math
import random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse
from gmpy2 import is_prime
FLAG = b"crypto{????????????}"
primes = []
def sieve(maximum=10000):
# In general Sieve of Sundaram, produces primes smaller
# than (2*x + 2) for a number given number x. Since
# we want primes smaller than maximum, we reduce maximum to half
# This array is used to separate numbers of the form
# i+j+2ij from others where 1 <= i <= j
marked = [False]*(int(maximum/2)+1)
# Main logic of Sundaram. Mark all numbers which
# do not generate prime number by doing 2*i+1
for i in range(1, int((math.sqrt(maximum)-1)/2)+1):
for j in range(((i*(i+1)) << 1), (int(maximum/2)+1), (2*i+1)):
marked[j] = True
# Since 2 is a prime number
primes.append(2)
# Print other primes. Remaining primes are of the
# form 2*i + 1 such that marked[i] is false.
for i in range(1, int(maximum/2)):
if (marked[i] == False):
primes.append(2*i + 1)
def get_primorial(n):
result = 1
for i in range(n):
result = result * primes[i]
return result
def get_fast_prime():
M = get_primorial(40)
while True:
k = random.randint(2**28, 2**29-1)
a = random.randint(2**20, 2**62-1)
p = k * M + pow(e, a, M)
if is_prime(p):
return p
sieve()
e = 0x10001
m = bytes_to_long(FLAG)
p = get_fast_prime()
q = get_fast_prime()
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(FLAG)
assert cipher.decrypt(ciphertext) == FLAG
exported = key.publickey().export_key()
with open("key.pem", 'wb') as f:
f.write(exported)
with open('ciphertext.txt', 'w') as f:
f.write(ciphertext.hex())
```
Đây chính là dạng tấn công [ROCA](http://bitsdeep.com/posts/analysis-of-the-roca-vulnerability/) (Return of CopperSmith Attack). Bài này ta có thể dùng tool sẽ factor được N. Thế nhưng mình khuyên nghị nên dùng [yafu](https://sourceforge.net/projects/yafu/) vì nhiều bài factordb sẽ không sử dụng được.
Mình factor ra rồi dùng code sau để thu được flag.
```
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import long_to_bytes
from factordb.factordb import FactorDB
key = RSA.import_key(open("key.pem", "rb").read())
f = FactorDB(key.n)
f.connect()
factors = f.get_factor_list()
if factors:
p, q = factors
phi = (p - 1) * (q - 1)
d = pow(key.e, -1, phi)
key_decrypt = RSA.construct((key.n, key.e, d))
cipher = PKCS1_OAEP.new(key_decrypt)
hexc = 0x249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28
c = long_to_bytes(hexc)
m = cipher.decrypt(c)
print(m.decode('utf-8'))
```
> crypto{p00R_3570n14}
### Ron was Wrong, Whit is Right
Source code sẽ như sau
```
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
msg = "???"
with open('21.pem') as f:
key = RSA.importKey(f.read())
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(msg)
with open('21.ciphertext', 'w') as f:
f.write(ciphertext.hex())
```
Unzip output ra thì ta thấy rằng có rất nhiều public key, ý tưởng là mình sẽ thử tìm ước chung lớn nhất của 2 n xem có ra giá trị p nào không.
```
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import long_to_bytes
from factordb.factordb import FactorDB
from math import gcd
from Crypto.Util.number import*
all_pem = []
all_e = []
for i in range(1, 51):
path = "./keys_and_messages/" + str(i) + ".pem"
with open(path, "rb") as f:
pem_data = f.read()
all_pem.append(RSA.import_key(pem_data).n)
all_e.append(RSA.import_key(pem_data).e)
all_cipher = []
for i in range(1, 51):
path = "./keys_and_messages/" + str(i) + ".ciphertext"
with open(path, "r") as f:
ciphertext_data = (bytes.fromhex(f.read()))
all_cipher.append((ciphertext_data))
for i in range(len(all_cipher)):
for j in range(len(all_cipher)):
n_i, n_j = all_pem[i], all_pem[j]
if gcd(n_i,n_j) != 1 and n_i != n_j:
p = (gcd(n_i,n_j))
q = n_j // p
assert p*q == n_j
d = inverse(all_e[j], (p-1)*(q-1))
key = RSA.construct((n_j, all_e[j], d))
cipher = PKCS1_OAEP.new(key)
print(cipher.decrypt(all_cipher[j]))
```
> crypto{3ucl1d_w0uld_b3_pr0ud}
### RSA Backdoor Viability
Source code của chall như sau:
```
**import random
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
FLAG = b"crypto{????????????????????????????????}"
def get_complex_prime():
D = 427
while True:
s = random.randint(2 ** 1020, 2 ** 1021 - 1)
tmp = D * s ** 2 + 1
if tmp % 4 == 0 and isPrime((tmp // 4)):
return tmp // 4
m = bytes_to_long(FLAG)
p = get_complex_prime()
q = getPrime(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
Chall này mình chưa học tại vì dính tới đường cong eliptics, nhưng factordb thì ra được p và q =)))
Có p và q rùi thì tìm flag thui
```
from Crypto.Util.number import*
p = 20365029276121374486239093637518056591173153560816088704974934225137631026021006278728172263067093375127799517021642683026453941892085549596415559632837140072587743305574479218628388191587060262263170430315761890303990233871576860551166162110565575088243122411840875491614571931769789173216896527668318434571140231043841883246745997474500176671926153616168779152400306313362477888262997093036136582318881633235376026276416829652885223234411339116362732590314731391770942433625992710475394021675572575027445852371400736509772725581130537614203735350104770971283827769016324589620678432160581245381480093375303381611323
q = 34857423162121791604235470898471761566115159084585269586007822559458774716277164882510358869476293939176287610274899509786736824461740603618598549945273029479825290459062370424657446151623905653632181678065975472968242822859926902463043730644958467921837687772906975274812905594211460094944271575698004920372905721798856429806040099698831471709774099003441111568843449452407542799327467944685630258748028875103444760152587493543799185646692684032460858150960790495575921455423185709811342689185127936111993248778962219413451258545863084403721135633428491046474540472029592613134125767864006495572504245538373207974181
n = p*q
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
print(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),n)))
```
> crypto{I_want_to_Break_Square-free_4p-1}
Sign in with Wallet
Connect another wallet