# STARTER
---
## 1. RSA Starter 1
### Description:
- Find the solution to 101^17^ mod 22663
### Solution:
```python
print(pow(101, 17, 2263))
>>>19906
```
---
## 2. RSA Starter 2
### Description:
- "Encrypt" the number 12 using the exponent e = 65537 and the primes p = 17 and q = 23. What number do you get as the ciphertext?
### Solution:
```python
p = 17
q = 23
N = p*q
e = 65537
pt = 12
ct = pow(pt, e, N)
print(ct)
>>>301
```
---
## 3. RSA Starter 3
### Description:
- Given p, q, N = p*q. What is the totient of N?
### Solution:
```python
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
N = p*q
fn = (p-1)*(q-1)
print(fn)
>>>882564595536224140639625987657529300394956519977044270821168
```
---
## 4. RSA Starter 4
### Description:
- Given p, q, e. What is the private key d?
### Solution:
```python
from Crypto.Util.number import inverse
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
fn = (p-1)*(q-1)
e = 65537
d = inverse(e, fn) #d = pow(e, -1, fn)
print(d)
>>>121832886702415731577073962957377780195510499965398469843281
```
### Note:
- e and fn must be co-primes, if not you must try another way to find private key d. In some case you should find another (e, fn) and then do some mathematical works to solve the problem - The challenge named:
> Broken RSA (Mathematics) - 100 pts - (Apply Tonelli-Shanks algorithm)
---
## 5. RSA Starter 5
### Description:
- Decrypt the ciphertext, given public key where the modulus N can be factorized
### Solution:
```python
from Crypto.Util.number import inverse
N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
#Using http://www.factordb.com , we found the values of p and q
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
d = inverse(e, (p-1)*(q-1))
pt = pow(c, d, N)
print(pt)
>>>13371337
```
---
## 6. RSA Starter 6
### Description:
- Sign the flag ```crypto{Immut4ble_m3ssag1ng}``` using your private key and the SHA256 hash function.
- Private key:
```python
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
```
### Solution:
```python
from Crypto.Util.number import bytes_to_long
from Crypto.Hash import SHA256
N, d = ...
e = 65537
pt = b'crypto{Immut4ble_m3ssag1ng}'
# Calculate the hash of the message: H and sign it with private key S = pow(H, d, N)
H = SHA256.new(pt)
S = pow(bytes_to_long(H.digest()), d, N)
print(S)
>>>13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475
```
# PRIMES PART 1
## 7. Factoring
### Description:
- Factorise the 150-bit number `510143758735509025530880200653196460532653147` into its two constituent primes. Give the smaller one as your answer.
### Solution:
- Using http://www.factordb.com/, we found the values of p and q:
```python
p = 19704762736204164635843
q = 25889363174021185185929
>>>19704762736204164635843
```
---
## 8. Inferius Prime
### Description:
- Given `n`, `e`, `ct`, recover the flag.
### Solution:
```python
from Crypto.Util.number import inverse, long_to_bytes
n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373
# Using http://www.factordb.com/
p = 752708788837165590355094155871
q = 986369682585281993933185289261
d = inverse(e, (p-1)*(q-1))
pt = pow(ct, d, n)
print(long_to_bytes(pt))
>>>b'crypto{N33d_b1g_pR1m35}'
```
---
## 9. Monoprime
### Description:
- Why is everyone so obsessed with multiplying two primes for RSA. Why not just use one?
### Solution:
- With `n` being a prime, the totient of `n` should be `n-1` since it counts all the numbers that are co-prime with `n`
```python
from Crypto.Util.number import inverse, long_to_bytes
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
d = inverse(e, n-1)
pt = pow(ct, d, n)
print(long_to_bytes(pt))
>>>b'crypto{0n3_pr1m3_41n7_pr1m3_l0l}'
```
---
## 10. Square Eyes
### Description:
- Given `n`, `e`, `ct`, recover the flag.
### Solution:
- Using http://www.factordb.com/, we found that `n` is a square number computed by a prime.
- Giving `n` = `p^2` with `p` being a prime, the Euler's totient function works that:  Therefore, `fn = p*(p-1)`
- Code:
```python
from Crypto.Util.number import inverse, long_to_bytes
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
# Using http://www.factordb.com/
p = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
fn = p*(p-1)
d = inverse(e, fn)
pt = pow(ct, d, n)
print(long_to_bytes(pt))
>>>b'crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}'
```
### Note:
- Another way to solve this problem is to compute Euler's totient function using its original formula:  since `n` is special, `fn = n*(1 - 1/p)` (p is the only divisor of n)
such that: `fn = n - n/p`
such that: `fn = n - p`
---
## 11. Manyprime
### Description:
- Using one prime factor was definitely a bad idea so I'll try using over 30 instead.
### Solution:
- The difficulty is there are 30+ prime divisors of `n` so we will use sage to factorized `n` and compute its totient function: 
- Code:
```python
from Crypto.Util.number import inverse, long_to_bytes
from sage.all import *
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
'''
fn = 1
factors = ecm.factor(n)
for f in factors:
fn *= (f-1)
'''
fn = 580642391898843191487404652150193463439642600155214610402815446275117822457602964108279991178253399797937961990567828910318944376020941874995912942457183778540787232677949141800666918857974957805860863128934894322453334083108951829885566055541321469492863749601696156719452204625091396670183612468234453545730714411260422415053794985900973204357184470104831581957188055965458235216412636167147716884241110058234315146752181551500634472836779298794303330378218517375396697137335380548442818167481491481087606998467945980408909917714107491743183639877866494931448463312524563384587536906823474872320000000000000000
d = inverse(e, fn)
pt = pow(ct, d, n)
print(long_to_bytes(pt))
>>>b'crypto{700_m4ny_5m4ll_f4c70r5}'
```
# PUBLIC EXPONENT
---
## 12. Salty
### Description:
- Smallest exponent should be fastest, right?
- Challenge code:
```python
#!/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
```
- Challenge output:
```python
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
```
### Solution:
- Với `e = 1`, ta có thể thấy rằng `ct = m (mod n)`, tuy nhiên, `ct` rất nhỏ so với `n` nên có thể dễ dàng suy ra `ct = m`.
- Vì vậy, ta có code:
```python
from Crypto.Util.number import long_to_bytes
n, e, ct = ...
print(long_to_bytes(ct))
>>>b'crypto{saltstack_fell_for_this!}'
```
---
## 13. Modulus Inutilis
### Description:
- My primes should be more than large enough now!
- Challenge code:
```python
#!/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
```
- Challenge output:
```python
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
```
### Solution:
- Với `e = 3`, quan sát số kích thước của `n` và `ct`, ta có thể thấy phép mô-đun ở đây là vô nghĩa, hay nói cách khác `ct = m^3`.
- Vì vậy, ta có thể sử dụng code (code `sage` tương tự `python`) như sau:
```python
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
m = long_to_bytes(int(iroot(ct, 3)[0]))
>>>b'crypto{N33d_m04R_p4dd1ng}'
```
---
## 14. Everything is Big
### Description:
- We have a supercomputer at work, so I've made sure my encryption is secure by picking massive numbers!
- Challenge code:
```python
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long
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 = getPrime(256)
e = pow(d,-1,phi)
if e.bit_length() == N.bit_length():
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)}')
```
- Challenge output:
```python
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
### Solution:
- Với hai số `N`, `e` khủng bố như thế, ta có thể đoán được số `d` sẽ tương đối nhỏ, đây chính là điều kiện để sử dụng Weiner's attack
- Ta có code:
```python
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
from fractions import Fraction
def f2cf(nu, de):
'''
Fraction nu/de to continued fraction
'''
cf = []
while de:
qu = nu // de
cf.append(qu)
nu, de = de, nu - de*qu
return cf
def cf2f(cf):
'''
Continued fraction to fraction
'''
f = Fraction(0, 1)
for x in reversed(cf):
try:
f = 1 / (f+x)
except ZeroDivisionError:
return Fraction(0, 1)
return 1/f
def cf2cvg(cf):
'''
Continued faction to convergents
'''
for i in range(1,len(cf)+1):
yield cf2f(cf[:i])
def crack(e, n):
for cvg in cf2cvg(f2cf(e, n)):
k = cvg.numerator
if k == 0:
continue
d = cvg.denominator
phi = (e*d-1)//k
nb = n - phi + 1
squ = nb*nb-4*n
if squ < 0:
continue
root = int(iroot(squ, 2)[0])
if root*root == squ and not (nb+root)&1:
p = (nb+root)>>1
q = (nb-root)>>1
d = d
return p, q, d
return "FAIL"
N, e, c = ...
p, q, d = crack(e, N)
pt = long_to_bytes(pow(c, d, N))
print(pt)
>>>b'crypto{s0m3th1ng5_c4n_b3_t00_b1g}'
```
---
## 15. Crossed Wires
### Description:
- I asked my friends to encrypt our secret flag before sending it to me, but instead of using my key, they've all used their own! Can you help?
- Challenge code:
```python
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}")
```
- Challenge ouput:
```python
My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
```
### Solution:
- Từ mô tả của bài, ta dễ dàng thấy `ct` được tính: `ct = m^(e1*e2*e3*e4*e5) (mod N)`. Ta coi 5 tích `e1*e2*e3*e4*e5` kia là một số e duy nhất, từ đó giải bài toán.
- Rất may mắn, số `N` của chúng ta có thể factor bằng http://www.factordb.com/, ta có code:
```python
from Crypto.Util.number import long_to_bytes, inverse
N = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
pubexs = (
106979,
108533,
69557,
97117,
103231
)
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
p = 134460556242811604004061671529264401215233974442536870999694816691450423689575549530215841622090861571494882591368883283016107051686642467260643894947947473532769025695530343815260424314855023688439603651834585971233941772580950216838838690315383700689885536546289584980534945897919914730948196240662991266027
q = 161469718942256895682124261315253003309512855995894840701317251772156087404025170146631429756064534716206164807382734456438092732743677793224010769460318383691408352089793973150914149255603969984103815563896440419666191368964699279209687091969164697704779792586727943470780308857107052647197945528236341228473
assert p*q == N
fn = (p-1)*(q-1)
e = 1
for i in pubexs:
e *= i
d = inverse(e, fn)
pt = long_to_bytes(pow(ct, d, N))
print(pt)
>>>b'crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}'
```
### Note:
- Tuy nhiên, ta có một cách khác để giải bài toán này: **Common Modulus as Internal Attack**, code như sau:
```python
from Crypto.Util.number import long_to_bytes, inverse
def find_trapdoor(n, my_e, my_d, e):
k = (my_e*my_d - 1)//n
while True:
fn = (my_e*my_d - 1)//k
if(fn*k == my_e*my_d - 1):
return inverse(e, fn)
else: k += 1
N = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
my_e = 65537
my_d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
pubexs = (106979, 108533, 69557, 97117, 103231)
e = 1
for i in pubexs:
e *= i
d = find_trapdoor(N, my_e, my_d, e)
pt = long_to_bytes(pow(ct, d, N))
print(pt)
>>>b'crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}'
```
- Bên cạnh đó, có thể thực hiện factor `N` theo như hint của bài:
```python
from random import randint
from Crypto.Util.number import long_to_bytes, inverse, GCD
def factor(N, my_e, my_d):
k = my_e*my_d - 1
g = randint(2,N-1)
p = 0
while p == 0:
for i in range(6):
x = pow(g,k//2**i,N)
if (x > 1 and GCD(x-1,N) > 1):
return GCD(x-1,N), N//GCD(x-1,N)
g = randint(2,N-1)
N = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
my_e = 65537
my_d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
pubexs = (106979, 108533, 69557, 97117, 103231)
e = 1
for i in pubexs:
e *= i
p, q = factor(N, my_e, my_d)
assert p*q == N
fn = (p-1)*(q-1)
d = inverse(e, fn)
pt = long_to_bytes(pow(ct, d, N))
print(pt)
>>>b'crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}'
```
---
## 16. Everything is Still Big
### Description:
- Okay so I got a bit carefree with my last script, but this time I've protected myself while keeping everything really big. Nothing will stop me and my supercomputer now!
- Challenge code:
```python
#!/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)}')
```
### Solution:
- Bài cho `N` có thể factor nên ta sẽ không đề cập đến cách đó ở đây.
- Nếu nhìn vào source code của bài, dễ thấy Weiner's attack không thể dùng được. Tuy nhiên, theo nguồn đọc: https://www.ams.org/notices/199902/boneh.pdf, ta biết một cách tấn công khác đối với trường hợp `d` tương đối nhỏ (Copy code nhưng chưa hiểu bản chất nên mình chưa viết ở đây)
---
## 17. Endless Emails
### Description:
- Poor Johan has been answering emails all day and the students are all asking the same questions. Can you read his messages?
- Challenge code:
```python
#!/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}")
```
- Challenge output:
```python
ns = [14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021, 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123, 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147, 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961, 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823, 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263, 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897]
e = 3
cs = [6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
```
### Solution:
- Nhìn vào đề bài, ta biết được Johan cần gửi cùng một tin nhắn tới tất cả sinh viên, vì vậy công thức sẽ là: `c[i] = m[i]^e[i] (mod n[i])`. Ở đây có 7 cặp `(c, n)` tương ứng, chứng tỏ đây chính là Hastad Broadcast Attack (một dạng tương tự của CRT: Chinese Remainder Theorem)
- Ta sẽ chọn từng cặp `n` và `c` để giải bài, tuy nhiên source code cho thấy Johan mã hóa từng phần trong `message`, bên cạnh đó CRT yêu cầu ít nhất 3 phương trình nên ta sẽ chọn các bộ ba từ danh sách `(n, c, e)` đã cho để tìm ra `message` thực sự. Tổng số cách của ta sẽ là `7C3 = 35` cách
- Code (sử dụng sage để tiết kiệm thời gian viết lại hàm `crt`):
```python
from Crypto.Util.number import long_to_bytes
from itertools import combinations
from gmpy2 import iroot
cs = [6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225, 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172, 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153, 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577, 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805, 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749, 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144]
ns = [14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021, 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123, 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147, 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961, 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823, 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263, 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897]
e = 3
pairs = [(c, n) for c, n in zip(cs, ns)]
triples = list(combinations(pairs, e))
for i in triples:
c = [x[0] for x in i]
n = [x[1] for x in i]
l = crt(c, n)
l = int(iroot(l, e)[0])
flag = long_to_bytes(l)
if(b'crypto' in flag):
print(flag.decode())
break
'''
yes
---
Johan Hastad
Professor in Computer Science in the Theoretical Computer Science
Group at the School of Computer Science and Communication at KTH Royal Institute of Technology in Stockholm, Sweden.
crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}
'''
```
# PRIMES PART 2
## 18. Infinite Descent
### Description:
- Finding large primes is slow, so I've devised an optimisation.
- Challenge code:
```python
#!/usr/bin/env python3
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}")
```
- Challenge output:
```python
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
```
### Solution:
- Nếu thử chạy hàm `getPrimes` của `source code`, ta sẽ thấy được hai số `p` và `q` khá gần nhau. Đây cũng chính là dấu hiệu cho thấy ta có thể sử dụng Fermat's attack ở đây.
- Code:
```python
from Crypto.Util.number import long_to_bytes, inverse, isPrime
from sympy.ntheory.primetest import is_square
from sympy import sqrt
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
def fermat(n):
a = int(sqrt(n))
b = a*a - n
while not is_square(b):
a += 1
b = a*a - n
else:
p = int(a - sqrt(b))
q = n//p
if(p*q == n): return p, q
p, q = fermat(n)
assert p*q == n
d = inverse(e, (p-1)*(q-1))
flag = long_to_bytes(pow(c, d, n))
print(flag.decode())
>>>crypto{f3rm47_w45_4_g3n1u5}
```
---
## 19. Marin's Secrets
### Description:
- I've found a super fast way to generate primes from my secret list.
- Challenge code:
```python
#!/usr/bin/env python3
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}")
```
- Challenge output:
```python
n: 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e: 65537
c: 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
```
### Solution:
- Dựa vào `source code` tạo ra hai số `p` và `q`, có thể thấy rằng `p = 2**a - 1` và `q = 2**b - 1` với hai số `a` và `b` nguyên bất kì.
- Từ đó, ta có:
```
n = p*q = (2**a - 1)*(2**b - 1)
n-1 = 2**a * 2**b - (2**a + 2**b)
```
- Do đó, `n` chia hết cho 2, giả sử `b > a`, bằng một vòng loop ta có thể tìm được a:
```python
temp = n-1
a = 0
while temp%2 == 0:
temp //= 2
a += 1
```
- Tìm được `a`, ta có thể tìm được `p` và `q`, công việc factor đến đây đã hoàn thành.
- Code:
```python
from Crypto.Util.number import long_to_bytes, inverse
n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e = 65537
c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
tmp = n-1
a = 0
'''
p = 2**a - 1
q = 2**b - 1
'''
while tmp%2 == 0:
tmp //= 2
a += 1
p = 2**a - 1
q = n//p
assert p*q == n
d = inverse(e, (p-1)*(q-1))
flag = long_to_bytes(pow(c, d, n))
print(flag.decode())
>>>crypto{Th3se_Pr1m3s_4r3_t00_r4r3}
```
### Note:
- Có thể dùng http://www.factordb.com/ để factor `n`
---
## 20. Fast Primes
### Description:
- I need to produce millions of RSA keys quickly and the standard way just doesn't cut it. Here's yet another fast way to generate primes which has actually resisted years of review.
- Challenge code:
```python
#!/usr/bin/env python3
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())
```
- Challenge output:
```python
249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28
```
### Solution:
- Ta có hai cách cho bài
- Cách 1: Sử dụng http://www.factordb.com/ để tìm trapdoor `d` và từ đó recover lại `flag`
- Cách 2: Phân tích `p` và `q`
- Cách 2 là một cách tấn công theo hướng: https://jix.one/not-even-coppersmiths-attack/ **(UNDONE do chưa hiểu bản chất)**
---
## 21. Ron was Wrong, Whit is Right
### Description:
- Here's a bunch of RSA public keys I gathered from people on the net together with messages that they sent.
- As excerpt.py shows, everyone was using PKCS#1 OAEP to encrypt their own messages. It shouldn't be possible to decrypt them, but perhaps there are issues with some of the keys?
- Challenge code:
```python
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())
```
### Solution:
- Trước tiên, nhìn vào source code, ta biết được quy trình mã hóa như sau:
`Tạo key -> PKCS1.encrypt -> Viết vào file ct`
- Từ đó, ta cũng có quy trình giải mã theo các bước:
`Đọc file ct, đọc và khôi phục key -> PKCS1.decrypt`
- Ta đã có được giá trị của `n` và `e` dễ dàng bằng việc đọc file `21.pem`, để construct được `key` ta cần thêm `d`. May mắn là ta có thể tìm `d` bằng http://www.factordb.com/.
- Code:
```python
from Crypto.PublicKey.RSA import import_key, construct
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import inverse, long_to_bytes as ltb
key = open('21.pem', 'rb').read()
key = import_key(key)
n, e = key.n, key.e
ct = int(open('21.ciphertext', 'r').read(), 16)
p = 919031168254299342928662994540730760042229248845820491699169870943314884504551963184014786520812939038906152950817942941469675496074887272906954399256046690838233813273902630076899906873722574023918253104149453601408405078374008695616160025877687382663027910687942091698042309812910101246025081363544171351624307177908410700904833438480012985928358897861427063761678614898919524867442676631453135379994570031284289815099294504127712924001149921480778993635917803466637717023744788311275545126346774536416864472035644211758788016642401235014385037912224180351022196262011724157012443048941426178651665266181311662824205620324073087330858064769424755443807165558567191049013947419763315902476674266627953223373671797370373786249718677582213173537848582863398367624397247597103174897140005790273296171101569756006898658668311846034013183862374297777882433967015111727139360441681664840944403450472574336901043555319067050153928231938431298082827397506406624964952344826628463723499263165279281720105570577138817805451223334196017505528543229067732013216932022575286870744622250293712218581458417969597311485156075637589299870500738770767213366940656708757081771498126771190548298648709527029056697749965377697006723247968508680596118923
q = 991430390905926023965735525726256769345153760248048478891327804533279477721590201738061124861790305326884541900044434890157058142414306020739922709698601329762087825767461256626800629782378634339618941488765491437487541851308806651586976069659042714378353883168031522106709494592827914376213512564492771821921367377484213072867988877925314809325159382342584541006645302760204539354879391605736604946702073863673524002591877977949645618863730441482821840664748508050205004505250025193611888170440612737112479006348533153568103452396596042639466753099280111709882461562564978070397786887446291916733276692400981917025361391646188802038772976331121474570242334921390569285834250256522656433623912544555266998750630136756355560927237594975904642791712318215315246754105993145827690531584325461597482035600919501967088106457091199733024323755210212616553447076697617349235377466327471959683763796707566328536834402308887105044128592177681553611608618850780128709949316259039664054913946726480968288231015999572777436469163437066403964134928735809253108394078092917006632332098357725950865697047565284013456253933234017983509582245874130968218422573483012858388392588302838940565560162598810462310034964473576147200222580784694005333482381
d = inverse(e, (p-1)*(q-1))
key = construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
flag = cipher.decrypt(ltb(ct))
print(flag)
```
### Flag:
> crypto{3ucl1d_w0uld_b3_pr0ud}
### Note:
- Wow mình có đọc lời giải và thấy một bài khá thông minh khi gather tất cả các mô đun trong folder đã cho và tìm ước chung của chúng với `n`. Đó cũng là một cách để factor `n` hay.
- Code:
```python
from glob import glob
from math import gcd
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
moduli = [RSA.import_key(open(f_name, 'r').read()).n for f_name in glob("*.pem")]
vuln_key = RSA.import_key(open("21.pem", 'r').read())
n = vuln_key.n
e = vuln_key.e
p = max([gcd(n,m) for m in moduli if n!=m])
q = n // p
# Phần tiếp theo tương tự code của mình
```
---
## 22. RSA Backdoor Viability
### Description:
- It seems like my method to generate fast primes was not completely secure. I came up with a new approach to improve security, including a factorization backdoor in case I ever lose my private key. You'll definitely need some complex techniques to break this!
:::info
You may need to tweak the recursion limit (sys.setrecursionlimit(n) in Python) in your programming language to get your solution working.
:::
- Challenge code:
```python
#!/usr/bin/env python3
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}")
```
- Challenge output:
```python
n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
```
### Solution:
- Lại một bài nữa có thể dùng http://www.factordb.com/. Khá chán nên mình sẽ làm hai cách (nếu đủ khả năng).
#### Cách 1:
- Code:
```python
from Crypto.Util.number import inverse as I, long_to_bytes as L
n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
p = 20365029276121374486239093637518056591173153560816088704974934225137631026021006278728172263067093375127799517021642683026453941892085549596415559632837140072587743305574479218628388191587060262263170430315761890303990233871576860551166162110565575088243122411840875491614571931769789173216896527668318434571140231043841883246745997474500176671926153616168779152400306313362477888262997093036136582318881633235376026276416829652885223234411339116362732590314731391770942433625992710475394021675572575027445852371400736509772725581130537614203735350104770971283827769016324589620678432160581245381480093375303381611323
q = 34857423162121791604235470898471761566115159084585269586007822559458774716277164882510358869476293939176287610274899509786736824461740603618598549945273029479825290459062370424657446151623905653632181678065975472968242822859926902463043730644958467921837687772906975274812905594211460094944271575698004920372905721798856429806040099698831471709774099003441111568843449452407542799327467944685630258748028875103444760152587493543799185646692684032460858150960790495575921455423185709811342689185127936111993248778962219413451258545863084403721135633428491046474540472029592613134125767864006495572504245538373207974181
assert p*q == n
d = I(e, (p-1)*(q-1))
flag = L(pow(c, d, n)).decode()
print(flag)
```
#### Cách 2:
- Trước tiên nhìn vào công thức mà source code sử dụng, ta sẽ làm một phép thử để tính xem trong khoảng đã cho có bao nhiêu số thỏa mãn:
```python
D = 427
s = 2**1020
one = 0
zero = 0
for i in range(s, s+10000):
temp = (D*i**2 + 1)%4
if temp:
one += 1
else:
zero += 1
print(one, zero)
```
- Có thể thấy, số các số chia hết cho 4 luôn bằng số các số chia 4 dư 1 và bằng một nửa độ dịch chuyển. Vòng lặp trong source code bắt đầu với `2**1020` và kết thúc với `2**1021 - 1`, tổng là `2**2021 - 2**1020 - 1` số và khá lớn. Tuy nhiên nó không để làm gì đâu :penguin:.
- Bài toán thực sự ta cần tham khảo nằm ở [đây](https://www.scitepress.org/Papers/2019/77866/77866.pdf), nhưng mình chả hiểu gì cả nên cách 2 **FAIL** :crying_cat_face:
### Flag:
> crypto{I_want_to_Break_Square-free_4p-1}
---
# PADDING
## 23. Bespoke Padding
### Description:
- Been cooking up my own padding scheme, now my encrypted flag is different everytime!
- Connect at `socket.cryptohack.org 13386`
- Challenge code:
```python
#!/usr/bin/env python3
from utils import listener
from Crypto.Util.number import bytes_to_long, getPrime
import random
FLAG = b'crypto{???????????????????????????}'
class Challenge():
def __init__(self):
self.before_input = "Come back as much as you want! You'll never get my flag.\n"
self.p = getPrime(1024)
self.q = getPrime(1024)
self.N = self.p * self.q
self.e = 11
def pad(self, flag):
m = bytes_to_long(flag)
a = random.randint(2, self.N)
b = random.randint(2, self.N)
return (a, b), a*m+b
def encrypt(self, flag):
pad_var, pad_msg = self.pad(flag)
encrypted = (pow(pad_msg, self.e, self.N), self.N)
return pad_var, encrypted
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_flag':
pad_var, encrypted = self.encrypt(FLAG)
return {"encrypted_flag": encrypted[0], "modulus": encrypted[1], "padding": pad_var}
else:
return {"error": "Invalid option"}
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13386)
```
### Solution:
- Khi đọc về padding và RSA, ý tưởng nổi ra đầu tiên trong đầu mình là Coppersmith. Vậy thì có thể giải theo Coppersmith không, ta hãy phân tích source code một chút.
- Sau khi nc với server, ta nhận được `n`, `encrypted_flag`, `padding`. Phần `padding` này gồm hai số là `a` và `b`. Nếu đọc lại hàm `encrypt` sẽ biết `encrypted_flag` của ta không phải là `pow(m, e, n)` mà là `pow(a*m+b, e, n)`. Đây là dấu hiệu ta có thể sử dụng Coppersmith để tính m, nhưng không phải dạng Coppersmith Stereotyped Message vì phương trình không monic.
- Nói đúng hơn thì đây là một dạng của Coppersmith, tên là [Franklin–Reiter related-message attack](https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Franklin-Reiter_related-message_attack).
- Vì sage không cho sử dụng pwntools để nc với server nên ta sẽ chia thành hai giai đoạn là lấy output và giải.
- Code lấy output:
```python
from pwn import *
from json import *
def send(hsh):
return r.sendline(dumps(hsh).encode())
option = {
'option': 'get_flag'
}
r = connect('socket.cryptohack.org', 13386)
r.recv()
enc = []
padding = []
n = 0
e = 11
send(option)
get1 = loads(r.recvuntil('}'))
enc.append(get1['encrypted_flag'])
padding.append(get1['padding'])
send(option)
get2 = loads(r.recvuntil('}'))
enc.append(get2['encrypted_flag'])
padding2 = get2['padding']
padding.append(get2['padding'])
assert get1['modulus'] == get2['modulus']
n = get1['modulus']
print(f'{enc = }')
print(f'{padding = }')
print(f'{n = }')
print(f'{e = }')
```
- Ta cần gửi option hai lần vì điều kiện để áp dụng Franklin–Reiter related-message attack là phải cùng modulus `n`
- Code thực hiện thuật toán giải output (giả sử output như dưới):
```python
from Crypto.Util.number import long_to_bytes
enc = [7100471843638722289145167976606910159773138627423709595150798616816912608359586319306293257214081804010823296916273940791849973540111317677759409336871392368452501475423097005481973798772513132512108238910607226635988637953448918956558791314214147588373238958078150608219388374961536924967344309464270442318214989658627354998075057311939720175613834278397259987715228276202347028144867033469003848173009494204872529617410272037690826989674454532694289648440508753070511166587890116097675346856531360458183388798905732132355729884794843178592142055260682264344749466187293896166061696494864346905075145951040056156431, 1409748709950292874622277704193051118536706855123389331208988530884888555436254109679692049085268311429053834076971118583135611341883468934673085267942820066425649527174801697020835725274754643531146509498092617910493035467181903185821151745479788200950904368266164263860030134767872880687877738564114369722170823700449880902918643618815515584584512422873798284015144097351700927100292287659169848139113977881478760075225152849069522323005405533282746808568265798714820762139744558585479705078746190546772467653352371893182805560879813528837887710010117866032966437167674799907344414942300756008747447846856407166254]
padding = [[7226432484418709728502788814115475985223860639771383288383579996661038444889262247347504216810795524345086752669604938430595531947830098206386511591129632388647065386548004976885110696215986426323004441894549658902838274207209403179666843222996526829702897197026489506149144566534572700797958111637472106929103798226354995777678422558608863713553052501290053721884856547866457851648313000381246431406822883943413220484483703686905696960366876341494750598855825895409079800829125846498148551965510867854980265291785015327913884923861624261197538456030251948926204486973415916172742127769438122239608668266302380845729, 2564483966134092537639306264886796121451516245052897813034116134977116567103115472476025566366180795847141098004098515752587165412622055351935097070251783598349802608982232342602952603678514440736323725685622352768463636508519644455176706737367920123909225097915906371641673031258908771855713799834702349110295937948920226933268259595016527412025500067731001496462783995072771101781061171247889053981544152138063697746642761786896616251380156839797067976177924804956139571431004343396336877898407811590817767646640374623552004658758504670308372891945264219468642058825597252028577164390280803718754640673954133028398], [9049001627949003065365662285805417665907116914698241870571300266402570316920417093017483568397571317830531219268110298124431432362933722871313445496058132876178670409011632232725082383831930845135338858596388340852687314620222433210031672052655795317051383376392229715324480186743070915829878785644188925474541174821983150642996173715888854507776161643730328814109313846059413927235410357963847508485604772163706991515756105382153300227426926150319712221826108190812314682247333483647783556331271609249806636793325437332179721252448924538212588007268567338250346479245346636685313538974804491075019882070799487218918, 10597969989623979121122092539160116893902580153808358757149248643804900854144954536559297235459340366638145059609140336995392902422492142546234398884650371898563594728967706990611675146186512832475486340373271444570075914431262056400826615565686820908927755451228432997471755971170796224070873123993350122348890616073797525015954553120137163497808083102622312838363146041630066722843651747118883415739634473585330350080819678239500816088193039037377334189335668532244406944498783120654610807980166668347633047654114636124066585337198959279152537765512515723338149483471071383554196872372958648946403441942674048034073]]
n = 11416779452654399252749863040595828556008489215719804758281310703773063470473354493555693465727247199282711340023343259632634967801836384147898950691525505584451538754856400419340929720593835601187204170137351576988380832259703680571023466109554972858605106302667769239197997819727587849399487837970185751881192400251681932810203185938934548488366319424840632271125354507512173564269402303700777356800669186223932707883165550956089104301583299768756868601171465891237691635234504186470464963716410242787197588203713070761931591842549972123168850965817306755850399724333601720382742316904547945153594270150910697537693
e = 11
def gcd(a,b):
while b:
a, b = b, a % b
return a.monic()
P.<x> = PolynomialRing(Zmod(n))
p1 = (padding[0][0] * x + padding[0][1]) ^ e - enc[0]
p2 = (padding[1][0] * x + padding[1][1]) ^ e - enc[1]
m = -gcd(p1, p2).coefficients()[0]
flag = long_to_bytes(int(m)).decode()
print(flag)
```
### Flag:
> crypto{linear_padding_isnt_padding}
### Note:
- Code tham khảo ở [đây](https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Franklin-Reiter/exploit.sage).
---
## 24. Null or Never
### Description:
- Can custom padding save one from some of the mistakes we already covered?
- Challenge code:
```python
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
FLAG = b"crypto{???????????????????????????????????}"
def pad100(msg):
return msg + b'\x00' * (100 - len(msg))
key = RSA.generate(1024, e=3)
n, e = key.n, key.e
m = bytes_to_long(pad100(FLAG))
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
### Solution:
- Tiếp tục đến bài này, đọc source xong mình cũng chỉ nghĩ tới Coppersmith nhưng là [Stereotyped Message](https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Coppersmith/README.md).
- Với `e = 3`, có vẻ như bài áp dụng Coppersmith được thật. Tuy nhiên ta cần phân tích bản rõ, `m = flag + b'\x00' * (100 - len(flag))`, tức là m sẽ có 100 bytes. Nhưng bài khá chuối khi không cho ta biết độ dài của flag, bắt buộc ta phải đoán.
- Code (sage):
```python
from Crypto.Util.number import bytes_to_long, long_to_bytes
n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
for i in range(9, 93):
PR.<x> = PolynomialRing(Zmod(n))
flag = b'crypto{'
m = flag + (b'\x00' * i) + b'}' + (b'\x00' * (100 - len(flag) - i - 1))
m = bytes_to_long(m)
f = (m + (256**(100 - len(flag) - i))*x)**e - c
f = f.monic()
temp = f.small_roots(epsilon=1/30)
if temp != []:
middle = long_to_bytes(int(temp[0]))
flag = (flag + middle + b'}').decode()
print(flag)
break
else:
print('Not yet!!!')
```
- Ngồi đợi một chút flag sẽ ra :smiling_face_with_smiling_eyes_and_hand_covering_mouth:
### Flag:
> crypto{n0n_574nd4rd_p4d_c0n51d3r3d_h4rmful}
### Note:
- Code trên mình không in ra giá trị `i` nhưng theo solution thì với `i = 35` ta lụm được flag.
---
# SIGNATURES PART 1
## 25. Signing Server
### Description:
- My boss has so many emails he's set up a server to just sign everything automatically. He also stores encrypted messages to himself for easy access. I wonder what he's been saying.
- Connect at `socket.cryptohack.org 13374`
- Challenge code:
```python
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener
class Challenge():
def __init__(self):
self.before_input = "Welcome to my signing server. You can get_pubkey, get_secret, or sign.\n"
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_pubkey':
return {"N": hex(N), "e": hex(E) }
elif your_input['option'] == 'get_secret':
secret = bytes_to_long(SECRET_MESSAGE)
return {"secret": hex(pow(secret, E, N)) }
elif your_input['option'] == 'sign':
msg = int(your_input['msg'], 16)
return {"signature": hex(pow(msg, D, N)) }
else:
return {"error": "Invalid option"}
listener.start_server(port=13374)
```
### Solution:
- Sau khi nc với server, ta có thể lấy được `N`, `e`, `secret`, `signature`.
- Tuy nhiên, nếu đọc source code, ta thực sự không cần tính gì cả vì trong server đã có sẵn giá trị `d` rồi. Khi đó chỉ cần gửi ngược lại `secret` là ta lụm flag.
- Code:
```python
from pwn import *
from json import *
def send(hsh):
return r.sendline(dumps(hsh))
r = remote('socket.cryptohack.org', 13374)
r.recv()
option = {
'option': 'get_secret'
}
send(option)
msg = loads(r.recv())["secret"]
option = {
'option': 'sign',
'msg': msg
}
send(option)
get = loads(r.recv())
message = bytes.fromhex(get["signature"][2:])
print(message.decode())
```
### Flag:
> crypto{d0n7_516n_ju57_4ny7h1n6}
---
## 26. Let's Decrypt
### Description:
- If you can prove you own CryptoHack.org, then you get access to one of our secrets.
- Connect at `socket.cryptohack.org 13391`
- Challenge code:
```python
#!/usr/bin/env python3
import re
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener
from pkcos1 import emsa_pkcs1_v15
# from params import N, E, D
FLAG = "crypto{?????????????????????????????????}"
MSG = 'We are hyperreality and Jack and we own CryptoHack.org'
DIGEST = emsa_pkcs1_v15.encode(MSG.encode(), 256)
SIGNATURE = pow(bytes_to_long(DIGEST), D, N)
class Challenge():
def __init__(self):
self.before_input = "This server validates domain ownership with RSA signatures. Present your message and public key, and if the signature matches ours, you must own the domain.\n"
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_signature':
return {
"N": hex(N),
"e": hex(E),
"signature": hex(SIGNATURE)
}
elif your_input['option'] == 'verify':
msg = your_input['msg']
n = int(your_input['N'], 16)
e = int(your_input['e'], 16)
digest = emsa_pkcs1_v15.encode(msg.encode(), 256)
calculated_digest = pow(SIGNATURE, e, n)
if bytes_to_long(digest) == calculated_digest:
r = re.match(r'^I am Mallory.*own CryptoHack.org$', msg)
if r:
return {"msg": f"Congratulations, here's a secret: {FLAG}"}
else:
return {"msg": f"Ownership verified."}
else:
return {"error": "Invalid signature"}
else:
return {"error": "Invalid option"}
listener.start_server(port=13391)
```
### Solution:
- Sau khi đọc source code, mình nhận ra server sẽ nhả flag khi thỏa mãn điều kiện:
```python
digest = emsa_pkcs1_v15.encode(msg.encode(), 256)
calculated_digest = pow(SIGNATURE, e, n)
if bytes_to_long(digest) == calculated_digest:
r = re.match(r'^I am Mallory.*own CryptoHack.org$', msg)
if r:
return {"msg": f"Congratulations, here's a secret: {FLAG}"}
```
- Vì vậy, ta cần chọn `n`, `e`, `msg` phù hợp để gửi lên server.
- Ta đã biết được:
```python
MSG = 'We are hyperreality and Jack and we own CryptoHack.org'
DIGEST = emsa_pkcs1_v15.encode(MSG.encode(), 256) #m
SIGNATURE = pow(bytes_to_long(DIGEST), D, N) #s
```
- Viết dưới dạng toán, ta có:
```python
s ≡ m^D (mod N)
```
- Một trong các `msg` phù hợp là:
```python
msg = 'I am Mallory, I own CryptoHack.org'
--> left = emsa_pkcs1_v15.encode(msg.encode(), 256)
--> left = bytes_to_long(left)
```
- Công việc của ta là tìm `e` và `n` sao cho:
```python
left ≡ s^e (mod n)
```
- Để đơn giản hơn, ta chọn `e = 1`:
```python!
left ≡ s (mod n)
--> left = s - k*n
--> n = s - left #Viết thế này cho dễ vì s > left
```
- Tới đây, ta có thể chọn được ngay giá trị `k = 1` thỏa mãn. Lưu ý, ta nên thêm một dòng `assert` để đẳng thức chắc chắn đúng vì dấu ở trên là suy ra. Done :smile_cat:.
- Code:
```python
from pwn import *
from json import *
from Crypto.Util.number import bytes_to_long
from pkcs1 import emsa_pkcs1_v15
def send(hsh):
return r.sendline(dumps(hsh))
def convert(txt):
return int(txt, 16)
r = remote('socket.cryptohack.org', 13391)
print(r.recv())
option = {
'option': 'get_signature'
}
send(option)
get = loads(r.recv())
N, e, s = get["N"], get["e"], get["signature"]
N, e, s = convert(N), convert(e), convert(s)
msg = 'I am Mallory, I own CryptoHack.org'
left = emsa_pkcs1_v15.encode(msg.encode(), 256)
left = bytes_to_long(left)
e = 1
n = s - left
assert left%n == s%n
option = {
'option': 'verify',
'msg': msg,
'N': hex(n),
'e': hex(e),
}
send(option)
get = loads(r.recv())
flag = (get['msg'].split(':'))[1]
print(flag)
```
### Flag:
> crypto{dupl1c4t3_s1gn4tur3_k3y_s3l3ct10n}
### Note:
- Thực ra khi tính được giá trị `k*n = s - left` kia, ta có thể dựa vào số `n` để tìm ra số `n` thỏa mãn khác như `n//2` hoặc `n//5` hoặc `n//10` đều đúng vì `n%10 == 0`.
- Maybe ta có thể chọn các `e` lớn hơn nhưng mình giống [tlinh](https://www.youtube.com/watch?v=XPjRADqth1c).
---
## 27. Blinding Light
### Description:
- Here's my token signing and verification server. I'm not sure it's doing signing properly, but I've implemented some safeguards to ensure it won't hand out admin tokens to just anyone.
- Connect at `socket.cryptohack.org 13376`
- Challenge code:
```python
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener
FLAG = "crypto{?????????????????????????????}"
ADMIN_TOKEN = b"admin=True"
class Challenge():
def __init__(self):
self.before_input = "Watch out for the Blinding Light\n"
def challenge(self, your_input):
if 'option' not in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_pubkey':
return {"N": hex(N), "e": hex(E) }
elif your_input['option'] == 'sign':
msg_b = bytes.fromhex(your_input['msg'])
if ADMIN_TOKEN in msg_b:
return {"error": "You cannot sign an admin token"}
msg_i = bytes_to_long(msg_b)
return {"msg": your_input['msg'], "signature": hex(pow(msg_i, D, N)) }
elif your_input['option'] == 'verify':
msg_b = bytes.fromhex(your_input['msg'])
msg_i = bytes_to_long(msg_b)
signature = int(your_input['signature'], 16)
if msg_i < 0 or msg_i > N:
# prevent attack where user submits admin token plus or minus N
return {"error": "Invalid msg"}
verified = pow(signature, E, N)
if msg_i == verified:
if long_to_bytes(msg_i) == ADMIN_TOKEN:
return {"response": FLAG}
else:
return {"response": "Valid signature"}
else:
return {"response": "Invalid signature"}
else:
return {"error": "Invalid option"}
listener.start_server(port=13376)
```
### Solution:
- Bài này mình thấy còn dễ hơn bài trên :penguin: vì mình có trong tay thuật toán để giải. Đơn giản thôi vì nó là [Blinding Attack](https://en.wikipedia.org/wiki/Blind_signature).
- Thuật toán thực hiện giống hệt trong link trên nên mình sẽ không viết chi tiết ở đây nữa.
- [Bài đọc giải chi tiết, pass: KCSC](https://zupplearncrypto.wordpress.com/2024/01/10/twenty-years-of-attacks-on-the-rsa-cryptosystem/)
### Flag:
> crypto{d0n7_516n_ju57_4ny7h1n6}
### Note:
- Vì bài đã gần đạt length limit nên hai bài 28, 29 mình sẽ viết ở link dưới đây.
---
# [Two last challenges in RSA](https://hackmd.io/@Zupp/KCSC_Task1b)
Sign in with Wallet
Connect another wallet