# CRYPTO HACK - RSA
## I. Starter
### Modular Exponentiation
Khi làm việc với RSA, ta làm việc mời các phép toán mudular. Đồng thời, với RSA chỉ có thể giải mã nếu có những thông tin thích hợp.

Flag: 19906
### Public Key
Public key hay Public info là N và e với N thường là p*q (p and q are primes).

Flag: 301
### Euler's Totient
N nếu có thể bị phân tích thành các phần tử nguyên tố, ta có thể tính phi(N) để giải mã Ciphertext:

Flag: 882564595536224140639625987657529300394956519977044270821168
### Private key
nghiệm d được hiểu là 1 private key giúp giải mã cipher 1 cách dễ dàng thay vì phân tích thừa số nguyên tố N khi N rất lớn. Ta có: d*e mod phi(n) = 1.

Đề bắt tìm d khi biết e, q, p.

Flag:121832886702415731577073962957377780195510499965398469843281
### RSA Decryption
Dùng flag chal trước làm d để giải RSA:

Flag: 13371337

### RSA Signature
RSA signing được hiểu như 1 bước tạo 1 bản tham chiếu, được sử dụng để kiểm tra xem plaintext là chính chủ không. Cụ thể nó được tính bằng: S = H(m)^(d1) mod N1. Với d1 và N1 là các khóa riêng của người gửi, khi người nhận sử dụng public key của người gửi với chữ ký Sign = S: s = S^e1 mod N1 mà s == H(m) thì nghĩa là xác định người gửi ko đổi.

Đề bài bắt ta Sign flag:

from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
m = b'crypto{Immut4ble_m3ssag1ng}'
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
m = bytes_to_long(sha256((m)).digest())
print(pow(m,d,N))

Flag: 13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475
## II. Primes Part 1
### Factoring
Tag này nhấn mạnh việc phải tạo 1 số N đủ lớn để việc tìm các phần tử nguyên tố trở nên đủ khó khăn.

Task của đề là phân tích 1 N không quá lớn, có thể tìm flag bằng factorint trong sympy:

from sympy import factorint
n = 510143758735509025530880200653196460532653147 
print(factorint(n))

Flag: 19704762736204164635843
### Inferus Prime
Bài đưa ta không 1 chút thông tin gì để tìm private key vì vậy việc ta có thể làm là đưa N vào 1 hàm fatorint để tìm q và p cho q và p chưa quá lớn.

Ta nhận được p, q = {1160939713152385063689030212503, 8484455050779453745279836494111}

Từ đó ta dễ dàng giải mã flag:

from Crypto.Util.number import long_to_bytes
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
p = 1160939713152385063689030212503
q = 848445505077945374527983649411 
d = pow(e,-1,(p-1)*(q-1))
print(long_to_bytes(pow(ct,d,n)))

Flag: crypto{N33d_b1g_pR1m35
### Monoprime
Task muốn ta decrypt m trong khi n là số nguyên tố, từ đó ta có thể tính phi(n) khá dễ. Sau đó, tìm d và cuối cùng là giải mã:

from sympy import sqrt_mod
from Crypto.Util.number import long_to_bytes

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

d = pow(e,-1,n-1)
m = pow(ct, d, n)
print(long_to_bytes(m))

flag: crypto{0n3_pr1m3_41n7_pr1m3_l0l}
### Square Eyes
N trong đề bài được tính là bình phương của p, Ta lấy căn n được p, giải phi tìm d. Cuối cùng là giải mã cipher:

from sympy import sqrt_mod, sqrt, isprime
from Crypto.Util.number import long_to_bytes

n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

p = int(sqrt(n))
phi = p*(p - 1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(ct, d, n)))

Flag: crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}
### Manyprime
N bài cho được tạo nên từ 30 số nguyên tố. Bằng cách sử dụng thuật toán phân tích thừa số nguyên tố 'ecm' trong Sage, ta có thể dễ dàng lấy được 30 số nguyên tố đó.

Sage:

sage: n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593
....: 6744855557922349009694020190556017816620445159992100326982759816313766511173186773687428676871801400487156271606417711180403725
....: 7357547933083009298980073010557370055771714625186058880250931053479231074889850439496626381995996327350911979103752550442260663
....: 4640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163
....: 147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
sage: factors = n.factor(algorithm = 'ecm')
  print(factors)

Khi đã có được các thừa số nguyên tố, ta tiến hành giải mã như bình thường:

phi = 1
for i in primes: 
    phi *= i - 1
d = pow(e, -1, phi) 
print(long_to_bytes(pow(ct,d,n)))

Flag: crypto{700_m4ny_5m4ll_f4c70r5}

## III.Public Exponent
### Salty
e = 1, lúc này ta dễ dàng tính được ct chính là m

Flag: crypto{saltstack_fell_for_this!}
### Modulus Inutilis
e = 3 trong khi N trong bài cho lại quá lớn, vì vậy ta tính được flag thật ra chính là căn 3 của ct:

from Crypto.Util.number import * 
from sympy import root
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
flag = root(ct, 3)
print(long_to_bytes(flag))

Flag: crypto{N33d_m04R_p4dd1ng}
### Everything is big
Task giao cho ta 1 public key với E và N siêu to khổng lồ, nhưng đề bài lại cho ta manh mối quan trọng là d có kích thước rất nhỏ so với N ( d = 2^256 < 2^511). Manh mối này để ta sử dụng thuật toán OWIENER, và thuật toán này được triển khai như sau.
- Trước tiên, 1 thuật toán RSA hợp lý, ta có công thức:
$e.d = 1 + k.\phi(n)$
<=>$\frac{e}{\phi(n)} = \frac{1}{d.\phi(n)} + \frac{k}{d}$
Lúc này, vì d rất nhỏ so với N (d <= $n^\frac{1}{4})$, e có số bit bằng n và chúng rất lớn, ta suy ra được:
$\frac{e}{n} \approx \frac{k}{d}$

- Thuật toán tấn công OWIENER được phát biểu như sau, ta phân tích $\frac{e}{n}$ thành liên phân số(Ta chỉ phân tích được nếu tử và mẫu nguyên tức nó hữu tỉ). Sau đó, ta tìm các phân số tiệm cận dạng $\frac{k}{d}$ tức là những giá trị xấp xỉ cho liên phân số, sao cho ta có d thỏa mãn đề bài.

** Cách kiểm tra d:
Với các giá trị (d, k) tìm được, ta tiến hành kiểm tra như sau:
------
- Ta tính giá trị của nghi ngờ của $phi(n)$ = $\frac{e.d - 1}{k}$, công thức được rút ta từ khải triển modular tính khóa riêng: $e.d = 1 + k.\phi(n)$ ( Nếu k = 0 thì ta sẽ bỏ qua và kiếm tra cặp tiếp theo)
- Ta đặt giá trị 't' là tổng 'p + q' = N - $\phi(n)$ + 1. Ta nhận xét 'p' và 'q' là nghiệm của phương trình: $x^2 - t.x + N$, lý do:
p + q = t
p . q = N
- Giải nghiệm q và p, nếu p . q = N thì ta lấy d.

from math import isqrt
from Crypto.Util.number import long_to_bytes
def lien_phan_so(tu, mau): 
    display = []
    while mau: 
        a = tu // mau 
        display.append(a) 
        temp = tu
        tu = mau 
        mau = temp - a*mau
    return display

def phan_so_tiem_can(display): 
    tiem_can = []
    for i in range(len(display)): 
        tu, mau = 0 , 1
        for j in reversed(display[:i+1]):
            tu,mau = j*tu + mau, tu
        tiem_can.append((tu,mau))
    return tiem_can

def chinh_phuong(a):
    if a < 0: 
        return False
    sqt = isqrt(a)
    return sqt**2 == a
    
def OWIENER(e, N): 
    lienphanso = lien_phan_so(e, N)
    tiemcan = phan_so_tiem_can(lienphanso)

    for (k, d) in tiemcan:
        if k == 0: 
            continue 
        if (e * d - 1) % k != 0:
            continue 
        phi = (e * d - 1) // k
        t = N - phi + 1

        delta = (t**2) - 4 * N
        if chinh_phuong(delta) == False and delta < 0: 
            continue
        p = (t + (isqrt(delta))) // 2
        q = (t - (isqrt(delta))) // 2 
        if q*p == N: 
            return d 
    return 0 

N = int(0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d)
e = int(0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3)
c = int(0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474)

d = int(OWIENER(e, N))
flag = pow(c, d, N)
print(long_to_bytes(flag))

Flag: crypto{s0m3th1ng5_c4n_b3_t00_b1g}
### Crossed Wires
Task này muốn ta phân tích N thành p,q khi biết d, e, N. Task cũng đề cập đến thuật toán để tính điều này, đây là bản raw:

Ta code theo thuật toán:

def computation_given_d(d, e, N,): 
    k = d * e - 1
    p, q = 0, 0
    while p == 0: 
        g = randrange(2,N)
        t = k 
        while t % 2 == 0: 
            x = pow(g,t,N)
            t = t // 2
            if x > 1 and gcd(x - 1, N) > 1: 
                p = gcd(x - 1, N)
                q = N // p
    return p, q

p, q = computation_given_d(d, e, N)
phi = int((q - 1) * (p - 1))
for (n, e) in reversed(friends_keys): 
    d = pow(e, -1 , phi)
    c = pow(c,d,n)
print(long_to_bytes(c))

Flag: crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}
### Everything is still big
Trong source của đề bài có cho điều kiện $d > \frac{1}{3}.N^{\frac{1}{4}}$, với d có 512 bit. Khá hoảng vì lúc này d vượt quá điều kiện của Wiener attack rồi, nhưng khi thử đưa vào thuật toán tấn công Wiener thì vẫn ra flag bthg, wtf.

Có lẻ d = 512 bit thì d chỉ lớn hơn điều kiện Wiener 1 chút:

from math import isqrt
from Crypto.Util.number import long_to_bytes
def lien_phan_so(tu, mau): 
    display = []
    while mau: 
        a = tu // mau 
        display.append(a) 
        temp = tu
        tu = mau 
        mau = temp - a*mau
    return display

def phan_so_tiem_can(display): 
    tiem_can = []
    for i in range(len(display)): 
        tu, mau = 0 , 1
        for j in reversed(display[:i+1]):
            tu,mau = j*tu + mau, tu
        tiem_can.append((tu,mau))
    return tiem_can

def chinh_phuong(a):
    if a < 0: 
        return False
    sqt = isqrt(a)
    return sqt**2 == a
    
def OWIENER(e, N): 
    lienphanso = lien_phan_so(e, N)
    tiemcan = phan_so_tiem_can(lienphanso)

    for (k, d) in tiemcan:
        if k == 0: 
            continue 
        if (e * d - 1) % k != 0:
            continue 
        phi = (e * d - 1) // k
        t = N - phi + 1

        delta = (t**2) - 4 * N
        if chinh_phuong(delta) == False and delta < 0: 
            continue
        p = (t + (isqrt(delta))) // 2
        q = (t - (isqrt(delta))) // 2 
        if q*p == N: 
            return d 
    return 0 

N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5

d = int(OWIENER(e, N))
flag = pow(c, d, N)
print(long_to_bytes(flag))

Flag: crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}
### Endless Emails
Đề bài cho ta ouput gồm các cặp (n,c) tương ứng và e nhỏ = 3. Vì đề bài nói rằng các các c thực chất là cùng 1 m được mã hóa khác nhau bởi các n, và e = 3, Ta nghĩ đến cách tấn công CRT:

from math import prod
from Crypto.Util.number import long_to_bytes, GCD
import gmpy2
def CRT(c,n):
    res = 0 
    Ni = prod(n)
    for i in range(len(n)): 
        ni = Ni // n[i]
        Mi = pow(ni,-1,n[i])
        res += c[i]*Mi*ni
    return (res % Ni)


n = [14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021,20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123,19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147,12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
,17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823,25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263,19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897]
e = 3 
c = [6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225,5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172,5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153,1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577,8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805,23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749,15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144]
for i in range(len(n)):
    for j in range(i+ 1, len(n)):
        for g in range(j+ 1,len(n)):
            m = CRT([c[i], c[j], c[g]], [n[i], n[j], n[g]])
            m = gmpy2.iroot(m, 3)[0]
            print(long_to_bytes(m))

Flag: crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}
## IV. Primes part 2
### Infinite Descent
Đọc đề bài ta thấy rằng p và q được tạo ra bằng cách:
- Khi p là số đầu tiên được lấy random số 2048 bit, nếu không tìm được p nguyên tố thì ta giảm đi 4 lần
- q còn giảm mạnh hơn p tận 8 lần trong khi để lấy được p thì khả năng cao việc giảm bit đã diễn ra rất nhiều lần

=> Ta đoán được rằng việc factor N trở nên khả thi:

from Crypto.Util.number import long_to_bytes, GCD
from sympy import factorint
#factorint(n)
p,q = 19579267410474709598749314750954211170621862561006233612440352022286786882372619130071639824109783540564512429081674132336811972404563957025465034025781206466631730784516337210291334356396471732168742739790464109881039219452504456611589154349427303832789968502204300316585544080003423669120186095188478480761108168299370326928127888786819392372477069515318179751702985809024210164243409544692708684215042226932081052831028570060308963093217622183111643335692361019897449265402290540025790581589980867847884281862216603571536255382298035337865885153328169634178323279004749915197270120323340416965014136429743252761521,19579267410474709598749314750954211170621862561006233612440352022286786882372619130071639824109783540564512429081674132336811972404563957025465034025781206466631730784516337210291334356396471732168742739790464109881039219452504456611589154349427303832789968502204300316585544080003423669120186095188478480761108168299370326928127888786819392372477069515318179751702985809024210164243409544692708684215042226932081052831028570060308963093217622183111643335692362635203582868526178838018946986792656819885261069890315500550802303622551029821058459163702751893798676443415681144429096989664473705850619792495553724950931
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
d = pow(e, -1, (p-1)*(q - 1))
print(long_to_bytes(pow(c,d,n)))

Flag: crypto{f3rm47_w45_4_g3n1u5}
### Marin's Secret
Cách tạo ra số nguyên tố bài này khá dị, khi q và p được tạo ra bằng cách lũy thừa bậc i rồi - 1. Nắm được điều này, ta chỉ cần chia dần N cho ($2^{i} - 1$) là ta dễ dàng tìm được flag rồi:

from Crypto.Util.number import long_to_bytes, GCD
for i in range (1, 10**5): 
    if n % (2**i - 1) == 0: 
        print(2**i - 1)
p = 1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007
q = 446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351
d = pow(e,-1,(p - 1)*(q - 1))
print(long_to_bytes(pow(c,d,n)))

Flag: crypto{Th3se_Pr1m3s_4r3_t00_r4r3}
### Fast primes
ROCA
### Ron was wrong, whit is right:
Phần giới thiệu của task này hướng chúng ta đến việc tìm ra 1 common element trong số các public key ta có. Áp dụng điều này, ta có thể dễ dàng tìm ra thành phần p của 1 N nào đó, việc còn lại là thử giải cặp (PEM, CIPHER) tương ứng để xem có flag trong đó không, rất may là có:

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import GCD

n, e, c = [], [], []

for i in range(1, 51):
    key = RSA.importKey(open(f"{i}.pem", 'r').read())
    cipher = open(f"{i}.ciphertext", 'r').read()
    n.append(key.n) 
    c.append(cipher)
    e.append(key.e)
p = 0 
index = 0 
for i in range(len(n)):
    for j in range(i+1,len(n)):
        cur = GCD(n[i],n[j])
        if cur != 1 and cur not in n:
            p,index = cur, i
q = n[index] // p 
d = pow(e[index],-1, (p-1)*(q -1))
key = RSA.construct((n[index],e[index],d))
cipher = PKCS1_OAEP.new(key)
flag = cipher.decrypt(bytes.fromhex(c[index]))
print(flag)

Flag: crypto{3ucl1d_w0uld_b3_pr0ud}
## V. Padding
### Bespoke padding
Đề bài muốn ta giải mã M được padding bằng cách : $a.M + b$

Ta thấy rằng N, e là đơn vị không hề thay đổi, ta được:
- $c1 = (a1.M + b1)^{e} \mod N$
- $c2 = (a2.M + b2)^{e} \mod N$

Thấy được điều này, ta nghĩ đến việc sử dụng Franklin Reiter attack, tìm được 1 đa thức bậc thấp có M là nghiệm duy nhất:
- $x + m = 0 \mod N$
=> $M = -m \mod N$

Cho rằng M bé hơn N, ta lấy luôn M sẽ là n - m, thật may mắn đây lại là giá trị đúng.

Sage:

from Crypto.Util.number import long_to_bytes
n =  27510406426346462690824472192271460310205190843329056640981719792315101786518175968596866399034362800555005000817112912706257087893858993279500191370807416811604795194116595411179476585992078596161268861377892890617260143160249300195518436543954407903034034097357341737032667245195205791903342037375075205362881451091621704140622012283359335368450981787953579705308382221819153926126455671449941798488642683157797137997444242606556204456185203495524062550522113910941654903042002266054012843095488165422580242486794439243469716922319990119982078622636600792309104272579780627331455739900280630019232168599459951762057
c1 = 9974911473370462656704557793008784631009602091844216158054897093801988632185485955005775963924192214923453327278506411527957629206469661616231631436847933022403464898922361776866200724549086546082334115904501616286287097030136866480251365061596603060377583400301762291162263773253525409504134056630249375820369869687193648099456773999303982561365628438853060345278433129665666044288177806608789113879907673440153216188879668966298486926475927275182479532472357236742864945630174925619882308952837489826301847272510463482166566117194864129508767827713930768211225548678866767120831182894412567845511147146265152974490
pad1 = [13549575189552614941566017865234409835989315434248065049391016171960739000367139391387383645497959963413473939277924416662651478132880345515035101756676128504426196791820547256930705135627218682743373318293143123836372986583388068767097774376299735815071967942664764898143917156680008800502318573016379941837796303891253304998371412326681354750474438291906452198407527737207670224495648073593890502593923172680832059870587972966548896038398365091343135301432016383606548725473852887226028181380236593742317703567544481502204241595276079262109049423902302986059517392461876219001388425499204851510139518057910631004833, 13716844224580273810498655209883364840636066501446121866761892258078068022121197661391858814218792706578392072723580966236179290998464168596757218715133320668757499809689211910469919295072237156049689755336097889011647653755303018756960981471659695991578822149048224860735618703731560173542779295676364625136080374500318617510230834924768695565249552397529064149832779205980337951993520259560455348485997928563164345541804436697874588615326888254300431525319533926060531807310936138741233838487928627177793340370985144364753140328291036893272762887590545606402626662975064002109086550325569447804813663161493536923216]
c2 = 26183580344360263692526095393699889533266413579090387448657272342352467425348661212472574920811342210576025051760075905491463297110531126831635357880267168520717147061988284704824455308262732965638539542593267762144694861033342695057424995718399314983621702381084524055293042355601921312236685372814683852766797832402708470370922610212071510899493707631166489320747420432662565291270245323775294554710050170666925732822068422700203235527358850227025310700275790761521140265839427048412464734085153660527223787090446620407692003547928213019124599014052290759225573135566359039966978150597859278782624352598266586673149
pad2 = [1938358953321486454798637280677468811971474611570133317516000185919408523454744721501017016549565259459916901267522237363254679261082667209396862365639080043267885811573712134332675658283299876594337760752327193277605211582042198483662253291267850784239813546390009318263473521312138853810527982351556213139853033421306968268622471597733222453106268313147694942227587101213542022211064815083291096835233064325997145804928500455348824490079214405068471817112121859049158900900888797599978709610932125013188765049126803108725460976774634722085413489276540243883479769161283607455227361928092518677682448323605325386261, 3868722605584282747198494518685983824432035362548588859605511350023331847437716369525584482893415326850236960998648337170276222686764488259632647619371189296655719122539558996434918760208706862214309036156817911711656624396230092801793304937664171449904136755789405473747573902522422907090707535078437913691257237108064925864900708316432915153858896390349436010430442079277162671492422313456476188815723698796695823750019264577956908883981426013673557601014146721260754407991113817544852473091216861906572879181673975745053784810364682788405610635958728150862051612828966530608650450705725088577578568178197931642703]
e = 11
R.<x> = PolynomialRing(Zmod(n))
pt1 = (pad1[0]*x + pad1[1])^e - c1
pt2 = (pad2[0]*x + pad2[1])^e - c2

while pt2 != 0:
    pt1, pt2 = pt2 , pt1 % pt2

gcdpt = pt1 / pt1.lc()
print(gcdpt)


flag = n - 27510406426346462690824472192271460310205190843329056640981719792315101786518175968596866399034362800555005000817112912706257087893858993279500191370807416811604795194116595411179476585992078596161268861377892890617260143160249300195518436543954407903034034097357341737032667245195205791903342037375075205362881451091621704140622012283359335368450981787953579705308382221819153926126455671449941798488642683157797137997444242606556204456185203495524062550522113910941654903042002266054012843095488165422580242486794439243469716922319235460158373341699174107615560727422048837442457776574972414208351338943616606335756
print(long_to_bytes((flag)))

Flag: crypto{linear_padding_isnt_padding}
### Null or Never
Cách Padding của câu này thực chất là dịch M sang trái 1 số $a = (100 - len(FLAG))$bytes, hay nói cách khác M được nhân thêm $a = 256^{(100 - len(FLAG))}$.

Hiểu được điều này, ta chỉ cần nhân C với nghịch đảo $a \mod N$. Sau đó chia dư kết quả cho N và + thêm $k.N$ (k ta sẽ bruteforce), dò căn bậc 3 của từng kết quả ứng với từng k để tìm được M ban đầu:

from Crypto.Util.number import long_to_bytes 
from gmpy2 import iroot

n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
FLAG = b"crypto{???????????????????????????????????}"

pad = 256**(100 -len(FLAG))
pad_enc = pow(pad,e,n)
pad_inv = pow(pad_enc,-1,n)
for k in range(10**5): 
    m = iroot(c*pad_inv % n + k*n, 3)[0]
    m = long_to_bytes(m)
    if b'crypto' in m:
        print(m)
        break

Flag: crypto{n0n_574nd4rd_p4d_c0n51d3r3d_h4rmful}
## VI. Signatures Part 1
### Signing Sever
Ta biết rằng:
$Sig = m^{d} \mod N$

Vậy để lấy được flag, ta đơn giản lấy C, sau đó đưa C vào Sign là xong:

from Crypto.Util.number import long_to_bytes
sig = 0x544f444f3a206175646974207369676e696e672073657276657220746f206d616b6520737572652074686174206d6564646c696e67206861636b657220646f65736e27742067657420686f6c64206f66206d792073656372657420666c61673a2063727970746f7b64306e375f3531366e5f6a7535375f346e793768316e367d
N = 0xac75f79fce92e1da50ca29668757467e2af8809f2474477e6635367bef04ea476e303bbfffc98b190d47fa17e5588925121f5a973f1078ce20741c13859af0f7542ebf8fcd5c1bad29b08eeada9aba6a7e40bffe61bc9f8f3e2e3b9fba18ea5ffe31c8316567aa989f763726b05e2533eb8750fb17af065040bf3662a700bdc54b75dbfce7624dded6b3ffe3a710ddb2183b45cba06f4858389e147ac907b26bfa752190bcfdc3eed9b1589bd034d4dbf8d53a5a83d74032ee2349b779c5ea9b98f0791c875bdeff5022254ddfe5d4b0e1f9bb606fd725e5b77484964c00a10dea4ab4dac4c1afe79777ed8ff9cdc635daced77b94713cc5d2e99f25e8fa3187
e = 65537 
c = 0x36616f25259cd2f073ce920144b1054d891fcd20cf243c4fc0bac556b5d7240fe92d8a19db7cfcee183c64f29585226521189b3d1c8be02d79ee754856cf1efae8a136cb02e045edd3f44b704a759f756574db89571b4b2fc3e52258ff15224e93072360afd7cea95d81029bc59f400dc1492597b958b8183c87a07a909b7ab407d44e5f65875e8b94585bbc60662a022e0c5edb18a28746ead4b8f8247cb80012d53a04ffa720cb10de0927f21a1334a49f5dae246d659672f8ff27703a52412dc9291f4ea50edd0d53a61cd8032336b3e416496bf2c424154018d2793c2d778c83fc245d8fabad2053d3e77767ba0feb3c094887e5424efbf5c5f02f618ec5
sig = int(sig)
print(long_to_bytes(sig))

Flag: crypto{d0n7_516n_ju57_4ny7h1n6}
### Let's Decrypt
Lỗ hổng lớn của đề bài là thuật toán check chữ kí bằng e và N do người dùng nhập, bằng cách đưa vào e và N hợp lệ, ta lấy m = 'I am Mallory own CryptoHack.org' để đưa và thuật toán để lấy flag.
Sau khi kết nối đến sever, chọn "get_secret ta nhận được chữ kí, N và e":
Lúc này ta chỉ cần đổi signature thành fakemsg: "I am Mallory own CryptoHack.org" cho giống với tham chiếu đề bài dùng để xác minh. Cùng với đó chọn:
$Nfake = Signature^{1} - H(fakemsg)$, e = 1 rồi đưa vào sever "verify" là đã dễ dàng bypass được rồi:

from pwn import *
import json

r = remote("socket.cryptohack.org", 13391)

welcome = r.recvline(timeout=5)
print(welcome.decode().strip())

data_send = {
    "option": "verify",
    "msg": "I am Mallory own CryptoHack.org",
    "N": "0x55c031eebc642cd1e44199e10937ee8b9e93c0c2d10a18b7b53a207fb1ddd4e6c2e08368a1943187bb1efe0378567340a0851710c426f609aa79d3b5bb3f8efe7f531cfdb54a9fba9e77e3ca2adcecdc299ebf601bd8926dd6ed4e7e71f96ef61cc041159eb0584ff4ce9f0d9e5cb49a91ba15226740f378340e40805aff2e20e275b783aa43a0ac670ec1af2d4e834acceda189add6ed7daf64ed8f9f9718f030c8a7d64afee7cf33beef5f790611eaef40e7c978e2355f3039a6df4f38113ce83ed669a733ce6a93e1fb04fdd6c28815beb6b62f886a47150fbdd44638894fec51825c3c78656da094299025ed6982f6b75febf6d1fa35f812ec7399225cc0",
    "e": "0x1"  
}

r.sendline(json.dumps(data_send))
response = r.recvline(timeout=5)
print(response.decode().strip())

Flag: crypto{dupl1c4t3_s1gn4tur3_k3y_s3l3ct10n}
### Blinding Light
Đọc article và code của đề bài hiểu luôn ta cần dùng phương pháp Blinding Attack để lấy chữ ký lên 'admin = True'.

Đề giải rất đơn giản, ta gọi sever lấy N và e. Sau đó tính $M' = r^{e}.M \mod N$ để tạo "cừu" nhử sever ký lên nó. Sau đó ta có:
$Sig' = (M.r^{e})^{d} \mod N$
=> $Sig \equiv Sig'.r^{-1} \equiv M^{d} \mod N$

Ta thành công có được chữ ký, việc bây giờ chỉ là đưa nó lên sever lấy flag thôi.

from Crypto.Util.number import bytes_to_long
N = int(0x954e1412ba207b8a246ea515e81425aeb5471cf5062b6497b2c76312ccf150498779ca540464b09fe573df68b0cfdcac124ba799b8546b45b49eaae9fadd630d1b5562a9993c6a3da72d5222e24aa6e1f9c663bfd07f31f0cdef87a54f2fbf7151afc3fd329bd16692dcfa6794c3d94d00fb2e11b49557a491be3e510f0c3e22163487df65e54d68f43a3ecea44e48dc929f2d321c6bfdb2c6c233c704e0618041ace0be91f637f423e6161b36a1fe0f04445ee1f48dc5960659706bbcb97c1667c5f17d0f2395dad348a88f3efb7fa06f99f7963749679eb697cd178fce6f65cfee5b6c9c36096c96f5b5532a6a3b44127afe27f10015dd71a644d455f800d5)
e = int(0x10001)
r = 2
inv_r = pow(r,-1,N)
cuu = bytes_to_long(b"admin=True")
cuu = (cuu * r**e) % N
print(hex(cuu))
sig_ = 0x6d65dcfe8f09ae022186b63b2665f4457d710a80dd1b01fe52d064af2461f8f848d81a59c48905b156a7ffc6a92ec43a94c3f18ef3e28b34fea35b1ab3454d20927731c238505529f5f00a345c02215f144f8c47467e9053255edf8a995264817f37a8cd1a6e48d94587a53c72028ce0fe025bc720b8a64ab0dc818f7dbe2bbc12b6e22cc150539f2496ab6b9de2f4cf41db2f6db4f5f3a031954fa7d83a8cffbcf2866f8cd85736f8a2c60c8778cd260beb597235d1c20094fbf321c23de11e7963fbaf5265c35d6247811f9826733ced0f7406dafea90300a1e37c188188d40b6c6b25e33e41d34b2cfc013b28ea5213db4f20bbb0cbb113d4eb054e8e630e
sig = int(sig_) * inv_r % N
print(hex(sig))

Interact:

from pwn import *
import json

r = remote("socket.cryptohack.org", 13376)

welcome = r.recvline(timeout=5)
print(welcome.decode().strip())

data_send = {
    "option": "verify",
    "msg" : "61646d696e3d54727565", #admin = True
    "signature" : "36b2ee7f4784d70110c35b1d9332fa22beb885406e8d80ff296832579230fc7c246c0d2ce24482d8ab53ffe35497621d4a61f8c779f1459a7f51ad8d59a2a690493b98e11c282a94faf8051a2e0110af8a27c623a33f482992af6fc54ca93240bf9bd4668d37246ca2c3d29e390146707f012de3905c5325586e40c7bedf15de095b711660a829cf924b55b5cef17a67a0ed97b6da7af9d018caa7d3ec1d467fde794337c66c2b9b7c51630643bc669305f5acb91ae8e1004a7df990e11ef08f3cb1fdd7a932e1aeb123c08fcc13399e7687ba036d7f54818050f1be0c40c46a05b63592f19f20e9a5967e009d94752909eda7905dd865d889ea7582a7473187"
}
r.sendline(json.dumps(data_send))
response = r.recvline(timeout=5)
print(response.decode().strip())

Flag: crypto{m4ll34b1l17y_c4n_b3_d4n63r0u5}
## Signatures Part 2
### Vote for Pedro
Khi nhìn vào code của đề bài: Sever check 'vote' bằng cách cắt byte '\00' và chọn byte cuối cùng xem có phải là b'VOTE FOR PEDRO' hay không, ta nhận ra ta cần biến đổi: b'VOTE FOR PEDRO' bằng cách thêm các bytes vào bên trái của nó và bytes gần nhất là: b'\00'.

Ta biết rằng, khi thêm byte vào bên trái, tức giá trị số học của nó bị thay đổi như sau:
$NewBytesStr = NewByte . 256^{k} + x$
- NewByte = giá trị byte thêm vào
- x = giá trị chuỗi byte cũ
- k = số byte của byte cũ

Hiểu được điều này,ta cần tìm biến send sao cho khi mũ 3 nó trong Modular N thỏa mãn đề bài, ta có:
$send^{3} = k.256^{15} + vote$
=> $send^{3} \equiv vote \mod 256^{15}$
Lúc này ta cần tìm căn 3 của send trong Modular $256^{15}$. Ta tìm send đơn giản bằng sage:
Sage:

from Crypto.Util.number import bytes_to_long, long_to_bytes
vote = bytes_to_long(b'\00' + b'VOTE FOR PEDRO')

R = Zmod(256**15)
send = R(vote).nth_root(3)
print(hex(int(send))

Lúc này, ta gửi send vào sever để nhận flag thôi:

from pwn import *
import json

r = remote("socket.cryptohack.org", 13375)

welcome = r.recvline(timeout=5)
print(welcome.decode().strip())

data_send = {
    "option": "vote",
    "vote" : "0xa4c46bfb65e7eccc4e76a1ce2afc6f"
}
r.sendline(json.dumps(data_send))
response = r.recvline(timeout=5)
print(response.decode().strip())

Flag: crypto{y0ur_v0t3_i5_my_v0t3}
### Let's Decrypt Again!
Ý tưởng thô sơ của task là ta cần tìm ra 3 'msg' sao cho với mỗi msg là fullfill được 1 challenge của đề bài và sever sẽ nhả cho ta 1 share.
- Các 'msg' với mỗi send sau khi sever xử lý thỏa mãn 1 trong: 
là ta ăn được 1 secret, đủ 3 secrets thì xor chúng với nhau ta sẽ được flag.

Ta nhận ra rằng đề bài bắt ta phải thêm 'suffix' vào cuối mỗi msg ta gửi, điều này ngăn cản cách tiếp cận bài Let's Decrypt trước đây khi ta đơn giản chỉ cần chọn e = 1 và tự tin tính N.

Lúc này mục tiêu của ta là tìm các e và N sao cho: $Sig^{ei} = mi \mod N$, sử dụng thuật toán Pohlig Hellman, ta dễ dàng tính được N và các cặp {ei, mi}.

Pohlig Hellman:
- Theo đề bài thì ta cần tìm ei, N sao cho:
$Sig^{ei} = sendi \mod N$, tức ứng với mỗi ei là sendi.
- Nói cách khác, ta tính: $\log{sig}{(sendi)} = ei \mod N$.
- Nếu $\phi(N)$ smooth, tức có thể thế phân tích thành hàng loạt các phần tử primes nhỏ
$\phi(n) = p^{g1}.p^{g2}...p^{gr}$
- ei vì không có ước với các số prime nên nó có thể viết thành: $ei \equiv e(r) \mod p^{gr} => ei = k.p^{gr} + e(r)$ , nên với mỗi 1 thành phần phân tích nguyên tố của $\phi(n)$, ta thấy ei thỏa mãn:
$ei \equiv e(1) \mod p^{g1}$
$ei \equiv e(2) \mod p^{g2}$
...
$ei \equiv e(r) \mod p^{gr}$
- Các $e(r)$ là 1 nghiệm của $sig^{er} \equiv sendi \mod p^{gr}$. Sage sẽ tính các nghiệm này trong quá trình sử dụng Pohlig Hellman.
- Bằng đính lý phần dư trung hoa, khi $\phi(n)$ có thể phân tích smooth, Sage giải đủ các e(r) thì tính được ei ứng với các sendi dễ dàng.
- Trong Sage, nếu ta có thể tạo được N có cấu trúc 'smooth', khi giải mũ ei trong Sage thì Sage sẽ tự động sử dụng thuật toán này.

Các bước giải:
- Đầu tiên , ta cần tạo N smooth = $p^{2}$ bằng cách chạy vòng lặp, tạo p chính là tích của các số nguyên tố tăng dần cho đến khi p + 1 là 1 số nguyên tố và > N để đảm bảo N hợp lệ để đưa vào sever. Sau đó, ta cần chắc chắn rằng Signature là phần tử sinh của Zn nếu không sẽ không tồn tại ei.
- Tiếp theo, ta chỉ cần đưa N vào sever để lấy suffix, đưa suffix vào từng message ta muốn gửi vào sever để lấy secret.
- Tính ei trong trường Zmod(N) ứng với từng message, sau đó gửi chúng lên sever cùng với index ứng với từng secret để lấy secret.
- Sau khi có 3 secret, XOR chúng lại với nhau để lấy flag.

from sage.all import *
from Pwn4Sage import remote
from pkcs1 import emsa_pkcs1_v15
import json

r = remote('socket.cryptohack.org', 13394)
r.recvuntil(b"This server validates statements we make for you. Present your messages and public key, and if the signature matches ours, you must undoubtably be us. Just do it multiple times to make sure...\n")

BIT_LENGTH = 768

def get_prime(n, sig):
    p = 1 
    nextprime = 2 
    while True: 
        p = p*nextprime
        nextprime = next_prime(nextprime)
        if is_prime(p + 1) and (p + 1) > n: 
            if Zmod(p+1)(sig).is_primitive_root():
                return (p + 1)
            else: 
                continue
def option_claim(send, ei, idx):
    data_send = {
        "option" : "claim",
        "msg" : send.decode(),
        "e" : hex(ei)[2:],
        "index" : idx
    }
    sending = json.dumps(data_send).encode() 
    r.sendline(sending)
    data = json.loads(r.recvline().strip())
    return data
def set_pub(N):
    r.sendline(json.dumps({"option": "set_pubkey", "pubkey": hex(N)[2:]}).encode())
    data = json.loads(r.recvline().strip())
    return data['suffix'] 
def xor(a, b):
    assert len(a) == len(b)
    return bytes(x ^^ y for x, y in zip(a, b))


#get_pubkey 
r.sendline(b'{"option" : "get_signature"}')
data = json.loads(r.recvline().strip())
n = int(data['N'], 16)
e = int(data['E'], 16)
sig = int(data['signature'], 16)

msg = [b"This is a test message for a fake signature.", b"My name is duong and I own CryptoHack.org",b"Please send all my money to 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy"]

p = get_prime(n, sig)
N = p**2 
suffix = set_pub(N)
send = []
for i in msg:
    i += suffix.encode()
    send.append(i) 

digest = [] 
for i in send: 
    i = emsa_pkcs1_v15.encode(i, BIT_LENGTH // 8)
    digest.append(i)

secret = []
R = Zmod(N)

for idx, d in enumerate(digest): 
    ei = R(int.from_bytes(d, 'big')).log(R(sig))
    claim = option_claim(send[idx], ei, idx)
    secret.append(bytes.fromhex(claim['secret']))

r.close() 
sec1 = secret[0]
sec2 = xor(sec1, secret[1])
flag = xor(sec2, secret[2])
print(flag)

Flag: crypto{let's_decrypt_w4s_t0o_ez_do_1t_ag41n} ớ