# Cryptohack

## RSA Starter 1 / Modular Exponentiation

### Đề bài

### Ý tưởng
- Như đề.

### Code

print(pow(101,17,22663))

## RSA Starter 2 / Public Keys

### Đề bài

### Ý tưởng
- Như đề.
### Code

print(pow(12, 65537, 17*23))

## RSA Starter 3 / Euler's Totient

### Đề bài

### Ý tưởng
- Sẽ được đề cập ở bài 5.

### Code

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi = (p - 1) * (q - 1)
print(phi)

## RSA Starter 4 / Private Keys

### Đề bài

### Ý tưởng
- Sẽ được đề cập ở bài 5.

### Code

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi)
print(d)

## RSA Starter 5 / RSA Decryption

### Đề bài

### Ý tưởng
- A muốn gửi cho B một đoạn tin nhắn `pt` nhưng lại lo ngại về tính bảo mật của nó. Vì thế A và B đã nghĩ ra một loại mật mã được gọi là RSA mà trong đó A sẽ giữ public key = `(n, e)` và B sẽ nhận được `ct` và giữ private key = `(n, d)`.
- Mã hóa:
$$
ct \equiv pt^e \ (mod \ n)
$$
- Ta sẽ tính d bằng:
$$
d \equiv e^{-1} \ (mod \ phi)
$$
- Với phi bằng:
$$
phi = (p-1)(q-1)
$$
Note: p,q là 2 số nguyên tố tạo lên n với $n = p*q$. Lý do họ chỉ dùng 2 số nguyên tố mà không dùng hơn bởi vì 2 lý do đơn giản là nó đã đủ bảo mật và nếu thêm vài số nguyên tố hơn nữa thì nó sẽ tốn nhiều thời gian và tài nguyên hơn trong quá trình giải mã (điều này không cần thiết).
- Giải mã:
$$
pt \equiv ct^d \ (mod \ n)
$$

### Code:

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
n = p*q
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi)

c = 77578995801157823671636298847186723593814843845525223303932

pt = pow(c, d, n)
print(pt)

## RSA Starter 6 / RSA Signatures

### Đề bài

### Ý tưởng
- Như ta đã biết thì hash là một hàm băm một chiều, và mấu chốt của signatures chính là double check thêm 1 lần RSA nữa với Hash(pt) để chắc rằng tin nhắn không bị thay đổi.

- Với tin nhắn RSA gốc, người A sẽ giữ (e0,n0), người B sẽ giữ (d0,n0).
- Và tin nhắn hash sẽ được tính bằng công thức:
$$
S \equiv Hash(pt)^{d1} \ (mod \ n1)
$$
- Giải mã tin nhắn hash bằng:
$$
Hash(pt) \equiv S^{e1} \ (mod \ n1)
$$
- Tức là người A sẽ giữ (d1,n1), người B sẽ giữ (e1,n1) để double check.

### Code

from hashlib import sha256
from Crypto.Util.number import bytes_to_long

pt = 'crypto{Immut4ble_m3ssag1ng}'

Hpt = sha256(pt.encode('utf-8')).hexdigest()
Hpt = bytes_to_long(bytes.fromhex(Hpt))

N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

print(pow(Hpt, d, N))

## Factoring

### Đề bài

### Ý tưởng
- Bài này ta chỉ việc sử dụng các tool để phân tích factor như factordb hoặc ECM của sage (sẽ được đề cập ở bài sau), để giải.

## Inferius Prime

### Đề bài
:::spoiler inferius.py

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 0x10001

# n will be 8 * (100 + 100) = 1600 bits strong (I think?) which is pretty good
p = getPrime(100)
q = getPrime(100)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

n = p * q

FLAG = b"crypto{???????????????}"
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

:::
:::spoiler output.txt
quá số lượng kí tự
:::
### Ý tưởng
- Bài này cho ta một số n có 200 bit, và đây là một số rất nhỏ và có thể dễ dàng bị bẻ khóa. Thời điểm hiện tại thì n sẽ rơi vào khoảng 2048 bit (p,q 1024 bit) là an toàn (có lẽ vậy).

### Code

from Crypto.Util.number import long_to_bytes

n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273

p =  848445505077945374527983649411
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
pt = long_to_bytes(pow(ct, d, n))
print(pt.decode())

## Monoprime

### Đề bài
:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Như cái tên của nó, bài này cho hẳn một số nguyên tố n, và đây cũng là vuln của bài này.

### Code

from Crypto.Util.number import long_to_bytes

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                               
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

phi = n - 1  
d = pow(e, -1, phi)
pt = long_to_bytes(pow(ct, d, n))
print(pt.decode())

## Square Eyes

### Đề bài
:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- n của bài này được tạo nên từ một số nguyên tố p, $n=p^2$. Vì thế để tính phi, công thức của nó sẽ hơi khác so với thông thường.
- Thông thường $phi = (p-1)(q-1)$ chỉ đúng khi p và q là 2 số nguyên tố cùng nhau. Nhưng bài này ta sẽ có một công thức tổng quát khác:
$$
phi = p^k - p^{k-1}
$$
Với k là số mũ của p khi tạo nên n.

### Code

from Crypto.Util.number import long_to_bytes
from math import isqrt

n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

p = isqrt(n)
phi = p*p - p 
d = pow(e, -1, phi)
pt = long_to_bytes(pow(ct, d, n))
print(pt.decode())

## Manyprime

### Đề bài
:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Bài này n được tạo nên từ rất nhiều số nguyên tố, và mình sử dụng ecm của sage để giải bài này theo [resources](https://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/ecm.html) mà cryptohack đề xuất. Mình cũng chưa hiểu quá sâu về cái này nên xin phép không nói thêm.

### Code

from Crypto.Util.number import long_to_bytes
from sage.all import *

n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

list = ecm.factor(Integer(n)) 
phi = 1
for i in list:
    phi *= (i - 1)
d = pow(e, -1, phi)
pt = long_to_bytes(pow(ct, d, n))
print(pt.decode())

## Salty

### Đề bài
:::spoiler salty.py

#!/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

:::
:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Như ta đã biết thì:
$$
ct = pt^e \ (mod \ n)
$$
Với công thức tổng quát theo số học module thì:
$$
pt = ct + i*n
$$
- Tuy nhiên, đây là RSA và trong đó ta phải thoả pt<n, và vì thế trong trường hợp này i =0, pt = ct

from Crypto.Util.number import long_to_bytes

ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

pt = long_to_bytes(ct)
print(pt.decode())

## Modulus Inutilis

### Đề bài
:::spoiler modulus_inutilis.py

#!/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

:::
:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Bài này ta có e = 3, nó là một số rất nhỏ nên ta chỉ việc tính căn bậc 3 là ra.

Note: Bài này mình dùng gmpy2 để đưa ra **độ chính xác cao nhất**, với `iroot(ct,e)` nó sẽ trả về một tuple với giá trị đầu là kết quả ta cần, giá trị sau sẽ là dạng true/false cho ta biết nó có phải kết quả chuẩn không (ai không hiểu thì tự test nha...).

### Code

from Crypto.Util.number import long_to_bytes
import gmpy2

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

pt = gmpy2.iroot(ct, e)[0]
pt = long_to_bytes(pt)
print(pt.decode())

## Endless Emails

### Đề bài
:::spoiler johan.py

#!/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}")

:::
:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Bài này giới thiệu cho ta cách tấn công `Hastad’s Broadcast Attack`, giải thích đơn giản thì ta có 1 tin nhắn m, và nhiều cặp (n, c). Với bài này trường hợp e = 3, thì ta cần ít nhất 3 cặp (n,c) để có thể giải ra m. Và giải bằng cách dùng crt.
- Bài này cho ta 7 cặp, nên ta sẽ pick 3 trong 7 cặp (n,c) để giải.

### Code

import re
from itertools import combinations
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
from sympy import integer_nthroot


n_list = [int(x) for x in re.findall(r'n\s*=\s*(\d+)', open('output.txt').read())]
c_list = [int(x) for x in re.findall(r'c\s*=\s*(\d+)', open('output.txt').read())]

for group in combinations(range(len(n_list)), 3):
    n_test = [n_list[i] for i in group]
    c_test = [c_list[i] for i in group]

    val = crt(n_test, c_test)[0]

    root, test = integer_nthroot(val, 3)
    
    if test:
        print(long_to_bytes(root))
        break
    else:
        continue

## Infinite Descent

### Đề bài
:::spoiler descent.py

#!/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}")

:::

:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Note: bài này hoàn toàn có thể dùng factordb để giải.
- Tuy nhiên khi tìm ra p, q thì mình nhận ra nó chỉ chênh lệch nhau rất ít giá trị, và đọc kĩ lại hint của đề thì nhận ra nó đang muốn ta giải theo `fermat attack`.
- Giải thích đơn giản thì ta fermat attack khi $∣p−q∣$ nhỏ. Lúc này ta sẽ có một setup như sau:
$$\begin{cases}
p + q = 2a \quad \\
p - q = 2b \quad
\end{cases}$$
Lúc này:
$$
n = (a+b)(a-b)=a^2-b^2
$$
=>
$$
b = \sqrt{(a^2 - n)}
$$
Vì b rất nhỏ nên có thể nói rằng $a^2 ≈ n$. Và những gì setup bên dưới chính là fermat attack.
[resources](https://viblo.asia/p/mat-ma-rsa-phan-4-r1QLx6EO4Aw)

### Code

from math import isqrt
from Crypto.Util.number import long_to_bytes

n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389

def fermat(n):
    a = isqrt(n)
    check = n - a * a
    b = isqrt(check)
    while b * b != check:
        a = a + 1
        check = a * a - n
        b = isqrt(check)
    p = a + b
    q = a - b
    return p, q

p, q = fermat(n)
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())

## Everything is Still Big

### Đề bài
:::spoiler sourcce.py

#!/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)}')

:::
::: spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Bài này ta sẽ sử dụng `Wiener's Attack`. Để giải thích đơn giản thì khi e là một số rất lớn ( lớn hơn rất nhiều 65537 mà ta hay dùng) thì ta hoàn toàn có thể nghĩ ngay tới cách tấn công này, cụ thể hơn là vì $d < \frac{1}{3} N^{\frac{1}{4}}$.
- Để set up thì trước hết ta có:
$$
ed \equiv 1 \ (mod \ phi)
$$
=>
$$
ed -k*phi = 1
$$
Chia 2 vế cho $d*phi$ ta được:
$$
\frac{e}{phi} - \frac{k}{d} = \frac{1}{d*phi}
$$
Và vì vế phải xấp xỉ 0 nên:
$$\frac{e}{N} \approx \frac{k}{d}$$
Lúc này ta sẽ tìm phân số hội tụ của nó để tìm k,d tiềm năng và tạo ra $phitest = \frac{ed-1}{k}$ để kiểm tra xem $x^2 - (N - phitest + 1)x + N = 0$ có 2 nghiệm nguyên p, q không.
[resources](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack)

### Code

import math
from Crypto.Util.number import long_to_bytes
import owiener

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

d = owiener.attack(e, N)
m = pow(c, d, N)
flag = long_to_bytes(m)
print(flag.decode())

- Note: mình không biết code, mình xài tool. #toibingu #toibingu #toibingu

## Crossed Wires

### Đề bài
:::spoiler source.py

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}")

:::
:::spoiler output.txt
quá số lượng kí tự
:::

### Ý tưởng
- Bài này chỉ đơn thuần là thực hiện RSA nhiều lần, cái khó ở đây là làm sao để ta có thể tìm được p, q để tính ra phi.
- Bài này đã giới thiệu cho ta một phương pháp để tìm p, q bằng cách tìm:
$$
x^2 \equiv 1 \ (mod \ n)
$$
Với $x \not= 1$ và $x \not= -1$ thì lúc này ta có GCD(x-1,n)=p. Để giải thích thì vì $x \not\equiv 1$ nên giá trị của GCD sẽ $\not= 0$ và với trường hợp còn lại thì sẽ $\not= n$.
- Ta triển khai thuật toán như sau:
- 1. Tính $k = d*e-1$
- 2. Chọn g bất kì từ (2->n-1), và t = k.
- 3. Cho s = t, x = pow(g, s, n)
- 5. Nếu x thỏa những dữ kiện mà mình đề cập ở trên thì lụm, không thì $s//=2$.
- 6. Nếu s%2 != 0 thì về lại bước 2.
[resources](https://di-mgt.com.au/rsa_factorize_n.html)

:::info
- Chứng minh:
Cốt lõi của bài này yêu cầu ta tìm GCD(x-1,n), và bản thân x có dạng là $g^t, g^{2t},g^{4t}...$. Và để lý giải điều đó thì ta có: $ed - 1 = k*\phi(n)$ mà e,d luôn là 2 số lẻ =>ed - 1 sẽ có dạng $2^r*t$. Mà theo định lý euler: $g^{\phi(n)} \equiv 1 \ (mod \ n)$ =>$g^{2^r*t} \equiv 1 \ (mod \ n)$ (y chang dạng của x ở trên). Và vì điều này cộng thêm với nghiệm x không tầm thường nữa thì ta sẽ tìm được p hoặc q.
:::

### Code

from Crypto.Util.number import long_to_bytes
from math import gcd
from random import randint

n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
e = 65537
key_list = [106979, 108533, 69557, 97117, 103231]
key_list = key_list[::-1]
c = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117

def find_p_q(n, e, d):
    k = d * e - 1
    t = k

    while True:
        g = randint(2, n - 1)
        s = t
        while s % 2 == 0:
            x = pow(g, s, n)
            if x != 1 and x != n - 1 and pow(x, 2, n) == 1:
                p = gcd(x - 1, n)
                q = n // p
                return p, q
            s //= 2
p, q = find_p_q(n, e, d)
phi = (p-1)*(q-1)

for key in key_list:
    d = pow(key, -1, phi)
    c = pow(c, d, n)
flag = long_to_bytes(c)
print(flag.decode())

# Dreamhack

## special_rsa_parameter

### Đề bài
`level 3`
:::spoiler special_rsa_parameter.py

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

e = 257
P = bytes_to_long(flag)

while True:
    p = getPrime(1024)
    if (p - 1) % e**2 != 0 and (p - 1) % e == 0:
        break

q = getPrime(1024)

n = p * q

C = pow(P, e, n)

assert (q - 1) % e != 0
assert (p - 1) % e == 0
assert (p - 1) % e**2 != 0

print(f"p = {p}")
print(f"q = {q}")
print(f"e = {e}")
print(f"n = {n}")
print(f"C = {C}")

:::
:::spoiler parameter.txt
output nằm trong code, phòng ngừa quá giới hạn kí tự...
:::

### Ý tưởng
- Vấn đề của bài này nằm ở việc $GCD(e,phi) \not= 1$. Hay nói thẳng ra là $GCD(e,p-1) = e$ và $GCD(e,q-1) = 1$.
- Trong lúc lân la trên mạng để tìm cách giải thì mình đọc được bài viết này ([resources](https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e)) và đó cũng chính là ý tưởng để giải ra bài này luôn.
- Tóm lại thì ta chỉ cần giải theo công thức sau đây:
$$
pt = ct^d * L^i \ (mod \ n)
$$
- Với $d = e^{-1} \ (mod \ \lambda/n)$
- $L = k^{\lambda/e} \ (mod \ n)$, ta chọn k bất kì sao cho $L \not= 1$
- $\lambda = \frac{(p-1)(q-1)}{GCD(p-1,q-1)}$
- i ta sẽ chạy vòng lặp từ (0->e)
Note: Mình không biết chứng minh tại sao công thức này đúng #toibingu #toibingu #toibingu.

### Code

from Crypto.Util.number import long_to_bytes
from math import gcd

p = 102917468046616568070479080437602349605790044856847368227989900438678598347252242912474630778930183524103498634272903762436029311481137741713080659077027483465896792512517855786714336938418831349151567425537183094315541122606131460802382497841037179253750742567612375678233281962828108691356598122015035462931
q = 155409405226203238058015527018600466439894178201393804291867914008619674289107580497614221099756010997177702316412488380301911465872315087011512265127913696978059566003514595719636467623534496220114055190116473471302619324855013682151351145662146108598413909004492093001297173273875378143449965795752096407249
e = 257
n = 15994342496511457631852165745889134659106113775792815345660283109468603940964892042894072452338973417508989267182581106246598435022873385443407040336706693823717245966048048753547976289148494787906459582665400524599910456936861809339918570553400623639334162939976766980991427000240636672326892016855733342336543332550988035515870213111437557851461183289944204759548833820909869065701576126243727856888072220248575585769081790850141026448275329427960153467083111068539569641547854318739805365356286162575492346400298725777857883327406673789140613479637379861625904116837931896101781221369655018622189149174730619186819
c = 9616384404213524657863670808981125526907268432622976664325249394851244870192789713737122799469499856887739253362805246859649606786263701308805488844336941066141053596437114630658542913559798796936296332917154444568198618992503828589914317105542317632873299732945292007245940129956165369995868033142331830348424499649247621627957887323716236781832428323377989036111392368810898382355775057357502240259332598797482858241354811610086476550911065698726091155648159869780115791767209206584503973202288411298660473001567148602289414544500536763463431773097574512189310225492456529147806648758189442259263483402853811323777

lambda_val = ((p-1)*(q-1)) // gcd(p-1, q-1)
lambda_divide_e = lambda_val // e  
d = pow(e, -1, lambda_divide_e)

k = 2
while True:
    L = pow(k, lambda_divide_e, n)
    if L != 1:
        break
    k += 1

a = pow(c, d, n)

for i in range(e):
    b = pow(L, i, n)       
    m = (a * b) % n
    
    msg = long_to_bytes(m)
    if b"BISC{" in msg:
        print(msg.decode())
        break

## Emoji RSA

### Đề bài
`level 4`
:::spoiler chal.py

from Crypto.Util.number import *
import random

EMOJIS = "🤣😅😇😍🤪🤑🤔🙄🥵🥶"
FLAG = open('flag', 'r').read()
MENU = """1. Encrypt your input
2. Change e
3. Encrypt the flag"""

def get_e(p, q):
    while True:
        t = random.randint(2 ** 16 + 1, 2 ** 18 + 1) | 1
        if GCD(t, (p - 1) * (q - 1)) == 1:
            return t

def emojify(emojis, s):
    return ''.join(emojis[int(ch)] for ch in str(s))

def main():
    emojis = list(EMOJIS)
    random.shuffle(emojis)

    p = getStrongPrime(512)
    q = getStrongPrime(512)
    n = p * q
    e = get_e(p, q)

    print(f"e: {e}")

    while True:
        print(MENU)
        inp = int(input('choice > ').strip())

        if inp == 1:
            inp = int(input('input > ').strip())
            print(emojify(emojis, pow(inp, e, n)))
        elif inp == 2:
            e = get_e(p, q)
            print(f"e: {e}")
        elif inp == 3:
            print(emojify(emojis, pow(bytes_to_long(FLAG.encode()), e, n)))

if __name__ == "__main__":
    main()

:::

### Ý tưởng
- Bài này chuyển mọi thứ thành emoji, khiến cho nó có chút dài và khó hơn một tí. Nhưng để làm thì không quá khó, ta sẽ chia thành 2 bước như sau:
- Bước 1: Tìm n
- Khi ta chọn phím 1, nó sẽ mã hóa cái input của ta. Và như ta đã biết, nó có một bảng mapping chứa 10 giá trị, tương ứng 0-9 để chuyển từ số thành emoji. Và khi ta nhập `input = 0`, ta sẽ biết được giá trị của 0 trong bảng mapping đó.Khi ta nhập `input = 1`, ta biết được giá trị của 1. Khi ta nhập `input = -1`, nó sẽ ứng với giá trị n-1. Và khi ta nhập `input = 2`, nó sẽ cho ra giá trị enc của input 2, tức là 2^e %n.
- Giờ ta sẽ tiến hành bruteforce, ta sẽ giả định một bảng mapping nào đó (có 8! trường hợp) và lấy thằng n-1 với 2^e %n để kiểm tra xem 2 phép tính đó có bị xung đột hay không. Nếu 2 phép tính đó không xung đột, tức là lúc này ta đã tìm ra được bản mapping đúng và n đúng.
- Bước 2: Tìm flag
- Lúc này ta đã tìm ra được n và bảng mapping, ta sẽ gọi 3 để tạo ra enc(msg) của thằng e1. Sau đó t gọi 2, rồi gọi 3 để tạo ra enc(msg) của thằng e2.
- Bài toán lúc này chính là `common module attack`, ta chỉ việc giải bằng egcd. (ai đi wco4 sẽ biết cách làm)

### Code

import sys
from itertools import permutations

e = 114187

emoji_0 = "😇"
emoji_1 ="😅"

all_emojis = "🤣😅😇😍🤪🤑🤔🙄🥵🥶"

n_minus_1_str = "😅🤣🤪😅🤣🤪🤑😇🤣🤑🤣🤔🤣🤑🤣🤪🥵🙄😇😅🙄🤣🤪🤪😅🤑😍😇🤔🥶🙄😇🙄🤔🤑🤑🥵🥶😅😇😅😇🥵🤣🤣😍😍🤔😅🙄🤪😇🤔🤑😇🤣🙄🙄🤔🤑🙄🤪🙄🥵🙄🥵😅🥶😇😅🤣😅🤪🤑🤔😅🥵🤑😇🥶😅🤑🤪🤔😅😅😍😇😇🥵🥶🥵🥵🤪😍😇🤣🤑🙄🤣😇😍😇🤑😅😅🙄🤑😇🤪🤑😇🥶🤔🥶🤪🙄😅🤣🤣😍😅🤣😅😅😍😍🤣🤪🤑🤪😅🤔🥶🤣🥶🤑😅🥵🤑🤑🙄😇🙄🥶😇🙄🥵🤔🤑😍🤑😅😅🥵😇🥶🤔🥶🥶🤪🤪🤣😅😅🙄🥵🤣🤪🤣🤣🤔😇🤪🥶😅🥶🥶🙄🤔🙄🥵🥵🤪🙄😍😅🥵😅🤣🤑😇🥶🤑🤔😅🤔🤣😇🥵😇🤣😍🤑🤣🤣😍🤔🙄🥶🤑🤪😇🥵🤪🥵🤔🙄🥶😍😇😅🥵😅🤔🙄😇🥶🥶🙄🤣🤪🤔🤪😍😍🤔😅🤣😍😇🥶🤣🥵😍🥶🤪🥶🤑🤔😅😇😇😍🥶🤑🥶😇🥶🥶🥵🥵😇🤪🤔🤔🤣🤑😍🤑😇🤣🤣🤪🤑😇🥶🤣🤪🤪🤣🥶🙄🤔🙄🥶🤪🤪🥵🤔😇😇🥵🤑🤣🙄🤪🤣🤑🤑😇🤪🙄🤑🤣🤪🙄🙄🙄"

enc_2_str = "🥶😍😍🙄🤪🤣🥶🥵😅🤑🙄😍🥵🥶🤔🥶😅😇🤑😍🥵🥵🤔🤑🤔🤑🤑🥵🤔🤪🤔😅🙄🤔😍🤑🤪🥶🥶😍🤑🤪😍🤔🤪😍🤣😍😅😇🙄🤑🤔🤔🤑🤔🥶😇🥶😍😇🙄😅😇🤔🥶😍🤣🤔😇🙄🤑😍🤔🤣😅🤔😇🥶😇🤑🤪🥵🥶🙄🤑🤑😅🥶🥶🤔😍🥵🤪😇😇😍🥶🙄😇🥵😅🥵😅🥶🥵🙄😍🤑🥶😅😅🥶🥶😅🥵😅😅🥶😅🤣😇🤑🤔😅😇🤑🤪😍🤪🤣🥵🤑🥶😅🤑🤑🥶🤣😅😇🙄🥶🤔🤔🥶🥵🤣😇🥶🤔🤣🙄🤪🤪🤑🥵🥵🤑😅🥵😅🤑🤔🤑🥶😅🤔😇😅😅😇🤪🥵🥵🙄😅😅🤔🤔🥵🥶🥵🤪😅🙄🥵😇🤪😇🥵🤑🥵🤔🥶🤔🤑🤪🥶🙄😅🤣😅🤣🤪🤑😇🤔😍😅🥵🥵🥵🤔🤔🤪🥶🥶🥶🤔🤔🤣🙄🙄🤔🥵🤑🤣🥵😅🤣🙄🥶😅🥶🤑😇🤑🤑🙄🥶🙄🥶😍🥶😇🥶🤣🥶🥵🤪🥵🙄🤑😇🤑🥵🤪😍😇🙄🤔🥵😅🤑😅🥵🤔😅🙄🤑🙄🥶🥵🤑🥶🥵🥵🥵🤑🥶🤪🙄😇😇😇😅🤪😇🤪😅😇😅🙄🤣🙄🤪🤪🥵🤪🥵🥶😍🤣🥵🙄😇🤣"

unknown_emojis = [c for c in all_emojis if c != emoji_0 and c!= emoji_1]
digits = "23456789"

for p in permutations(digits):
    mapping = {emoji_0: '0', emoji_1: '1'}
    for i, digit in enumerate(p):
        mapping[unknown_emojis[i]] = digit
    
    def decode(s):
        return int("".join([mapping[c] for c in s]))
        
    n = decode(n_minus_1_str) + 1
            
    calculate = pow(2, e, n)
            
    target = decode(enc_2_str)
            
    if calculate == target:
        print(mapping)
        print(n)
        break

Note: bước 1.

from Crypto.Util.number import long_to_bytes, inverse

mapping = {'😇': '0', '😅': '1', '🤣': '3', '😍': '2', '🤪': '5', '🤑': '8', '🤔': '4', '🙄': '6', '🥵': '7', '🥶': '9'}
n = 135135803834383576016355182049606488791010733224165048036648656767190131584178091854112007977520386302081168058094956133213112235851493981788606906748281170949955311673533405919964677562171380984143070328332469850757469201714609963545224132093729598410029890997705443828033580935539646955740078365388056835667
e1 = 114187
c1 = "🥵🤔🤑🥶😍🤑🤪🤑😇🤣🤑🙄🤔🤑🙄🤪😅🙄🤣🤣🤑🥶🤔🤑😍😍😅😇😍😇😍😍😇🥶🥶😇🤣😅😇😇🤑🤑🙄🤑🤔😇😇🙄🥵🙄🤣🤔😍😍😇🤪🤣🥶🥵🤣🤑😅🤔🥵🥵😍🥶🤑🤑🤪🙄😍🥶🥵🤔🙄😍🥶🥵🥵😇🤪🤔😍🤣🥵😇🥵🥵😇🤪🤑🙄🙄🥵🤔😅🤔🤪😅😅🙄🤔🙄🙄🤑😍🤣🤔🥵🤑😅🤔🤔🙄🙄🥵🤔🤑🤔🙄🥵🥶🤪🙄🤪🙄😇🤑🤣🥵😍😍🤔🤑🤔🤣🥵🙄😅🥶🤪😇🙄🥶🥶🤣🤔😅🙄🤔🤣🤪🤪🤪😍🤣😇🤪🤑😇🤣🥵🤣🥵😍🤣🤣🤑😇🥵🤔😅🤑🙄😅🥶😅😍🤣🙄🤣🤣🤣😅🤑🤑😅🤑😇🥵🤑🥶🥶😅🤪🙄🤑🙄🤣😅😅😇🙄🥶😇🥵🥵🤑🤑😅😇😇🤣🤪😍😍😍🤔🙄😍🤪🤣🥶🤪🤪🥶😍🤑🥶🙄😇😍🤔🤪🤑🤔😇🤔🤣😍😍🙄🥵🥶🤔🤑🙄😅🤣🤣😅🙄😅🤔🤑😍🥵😇🤪🥶🥶😇🥶🥵😍😅😇😅😇🤑🤑🤔🤪🤪🙄🥵🤑😇🤪🥵😅🙄🥶🤪😍🥶😇🙄🤑😇🙄🤪🤑🥶😇🤑🥶🤪🥶😅😅🙄😍😅😍🤔🙄"
e2 = 101111
c2 = "🤑🥵😍😍🤑🥶🤔🤔🙄😍🥶🤪😇🤔🙄🙄🥵🤣🤣😅😅😅😅🤔🤔🤑🥵🤔😅🤔🤣🥵😇🤑😅🥶😍🙄😇🥶😇🤑🤑🤣🤪🙄🥶🤑🙄🤪😍🤣🤪🥶🤣🤑🥵🤔🥶😅🥵😍😍🤔🤔🙄🤣😇🥶🥵😅😅🤪😇😇🥶🥶🥶😅😍🤣🙄🥶🤪🥶🤔🥶🥵😍🥵🥶😅😇🤑🙄😅🤑🙄😍🤣🤔🥵🤔🥶🤔🥵🤣🥵🥵😅🤔🤪🤔🤑🤪😅😍🤔🤔🥶😍🤔🤪😇😇🥵🥵🥵😅🤣😅🤪😇🤔😍🥶😅😍🤑😍🥶😇🤑🙄🥶🤣🥵🤔🥶🤪🙄🤣🤣🤣🙄😇😅😇🙄😇🤑🥶🤔🥵😇🤣🙄🤣🤔🙄🤪🥵🤑🤪🥵😍😇🤔🙄🥶🤪🥵🤔🥶🤔🤣😇😇😍🤑🤔🤔😇🥵🤣🤪😅🙄😅🥵😅😇🤑😅🤣🥶🙄😍🥶😍🥶🥶🤪😇😇🤪😇😍🤣🥵🤑🤑🤪🥶🥶🤣🙄😅🤔🥵🤪🙄😍🥵🤣😅🥵🙄🤪🤔🙄😅😇🤣😅😇😅🤔😍🙄😅😇🤑😇🤣😇😅🙄🤑🥵🥵😍🙄🙄🥵🙄🥶😍😇🥶🤑🤣🥵🥵🙄🥵🙄😍🤣🤔😅🥵😍🙄🤔😍😇😍🤣🤪😍🤪🙄😅🤔🥶😅😍😍😍🤔🤣🥶🤪🤔🤪🤑😅"

def decode(s, mapping):
    return int("".join([mapping[c] for c in s]))

c1 = decode(c1, mapping)
c2 = decode(c2, mapping)

#e1*16741 + e2*-18906 = 1
c1 = pow(c1,16741,n)
c2 = pow(c2,-18906,n)
m = (c1 * c2) % n
print(long_to_bytes(m).decode())

Note: bước 2.

# AlpacaHack Round 12

### Đề bài

:::spoiler chall.py

import os
from Crypto.Util.number import getPrime, bytes_to_long
 
e = 19
while True:
    p = getPrime(2048)
    q = getPrime(2048)
    if gcd((p - 1) * (q - 1), e) == 1:
        break
n = p * q
 
flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")
 
m = bytes_to_long((flag * 1337).encode())
c = pow(m, e, n)
 
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
'''
quá số lượng kí tự
'''

:::

### Ý tưởng
- Core của bài này nằm ở 2 dòng:

assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")

m = bytes_to_long((flag * 1337).encode())

- Mình đã thử test trong máy với đoạn code sau:

from Crypto.Util.number import bytes_to_long
flag = 'a'
print(bytes_to_long((flag).encode())) #97
print(bytes_to_long((flag * 2).encode())) #24929

- Ta được nhận xét là với len(flag) = 1, ta sẽ nhận được 2 số 97 và 24929. Và mối quan hệ của chúng lại liên quan đến bit, một chữ cái 'a' sẽ tốn 8 bit, và để ta nhân đôi 'a' lên thì chẳng khác gì ta phải dịch trái 8 lần hết. Để giải thích cụ thể thì ta có bảng dưới đây, với 'a' khi chuyển qua nhị phân sẽ là '01100001'

| Bit 15 | Bit 14 | Bit 13 | Bit 12 | Bit 11 | Bit 10 | Bit 9 | Bit 8 | Bit 7 | Bit 6 | Bit 5 | Bit 4 | Bit 3 | Bit 2 | Bit 1 | Bit 0 |
| ------ | ------ | ------ | ------ | ------ | ------ | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | --- |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
- Ở đây, từ bit 0-7 chính là cho chữ 'a' đầu tiên, và 8-15 là cho chữ 'a' thứ 2. Và khi ta chuyển từ mã nhị phân sang thập phân (đã học trong nmms) thì kết quả lúc này sẽ ra 24929. Và nếu ta chỉ tính đúng 8 bit đầu thì kết quả sẽ ra 97. Giờ ta có thể lập ra được một công thức như sau (áp dụng trong test nhỏ của mình):
$$F = flag*((2^8)^{k-1} +(2^8)^{k-2}+...+ 1)$$
- flag chính là flag gốc mà ta thực hiện phép nhân.
- k là số lần nhân.
- $2^8$ lúc này có thể gọi là hệ số nhân. Lý do nó chỉ có $2^8$ là vì len(flag)=1, tức là chỉ có 8 bit. Nhưng nếu len(flag) = 2, thì sẽ là $2^{16}$.
- Giờ ta sẽ quay lại bài toán gốc, vì len(flag) = 26 nên hệ số nhân sẽ bằng $2^{208}$. Và k = 1337. Tức là lúc này:
$$
m = flag*((2^{208})^{1336} +...+ 1)
$$
- Và ta có mã hóa RSA như sau:
$$
c \equiv m^e \pmod n
$$
=>
$$
c \equiv flag^e *((2^{208})^{1336} +...+ 1)^e \pmod n
$$
=>
$$
flag^e \equiv (((2^{208})^{1336} +...+ 1)^{-e} * c \ (mod \ n)
$$
Hết bài, ta có thể tìm ra flag từ đây.

### Code

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836
k = (pow(2**208, 1337) - 1) // (2**208 - 1)
F_e = c* pow(k**e,-1,n) % n
flag = iroot(F_e,e)[0]
print(long_to_bytes(int(flag)).decode())

# RAS - Wanna champion 2024

## Đề bài
:::spoiler

from Crypto.Util.number import *
#from secret import flag
import random
flag = b'W1{????????????????????????????????}'
#len(flag) = 36

class RAS(object):
    def __init__(self, p, q):
        self.p = p
        self.q = q
        self.n = (p**3 - p)*(q**3 - q) #p*(p**2 -1)*q*(q**2 -1)

    def generate_e(self):
        e = random.randint(self.p * self.q, (self.p * self.q)**2)
        return e

    def encrypt(self, pt):
        e = self.generate_e()
        assert pt < self.n
        c = pow(pt, e, self.n)
        return e, c

flag1, flag2, flag3 = bytes_to_long(flag[:len(flag)//3]), bytes_to_long(flag[len(flag)//3:2*len(flag)//3]), bytes_to_long(flag[2*len(flag)//3:])

# shuffle it
m1 = flag1*flag2*flag3
m2 = flag1 + flag2 + flag3
m3 = flag1 * flag2 + flag2 * flag3 + flag3 * flag1

nbit = 256
menu = '''
Welcome to my RAS
1. Send primes
2. Get encrypted flag
'''

b = False
print(menu)
while True:
    try:
        choose = input('> ')
        if choose == '1':
            primes = input(f"Send me two {nbit}-bit strong primes, separated by comma: ")
            try:
                p, q = map(int, primes.strip().split(','))
            except:
                raise Exception("Invalid input")

            if (isPrime(p) and isPrime(q) and
                p != q and
                p.bit_length() == q.bit_length() == nbit):
                b = True
                ras = RAS(p, q)
            else:
                print("Primes not strong enough!")
        elif choose == '2':
            if b:
                print(ras.encrypt(m1))
                print(ras.encrypt(m2))
                print(ras.encrypt(m3))
            else:
                raise Exception("You must send strong primes first!!!")
        else:
            raise Exception("Invalid choice!!!")

    except Exception as e:
        print(f"Error: {str(e)}")
        break

:::

## Ý tưởng
- Phân tích code: trước tiên thì chall cho ta nhập 2 số p, q và sẽ xuất ra encrypt m1, m2, m3 cũng như e1, e2, e3. Nhưng vấn đề lúc này của bài toán nằm ở việc N của nó khác với thông thường, hay cụ thể là p* (p ** 2 - 1) * q *(q ** 2 - 1).
- Và core idea của bài này để ta exploit đó là **crt**. Và vì độ dài của flag chỉ nằm trong p và q, nên thay vì xử lý trong trường N, ta sẽ chuyển thành xử lý trong trường p/q.
- Lúc này, phi = p-1 hoặc q-1. Tuy nhiên ta có thêm một vấn đề nhỏ đó là gcd(e,p-1) hoặc gcd(e,q-1) chưa chắc == 1. Vì thế ta cần phải spam connect để thu được nhiều testcase nhất và thực hiện crt với m = pow(c, d, p) hoặc pow(c, d, q). Và vì len(flag) mình chọn khá nhỏ nên chỉ cần 3 cặp crt là thỏa, đồng thời mình connect 6 lần vào server. Tức là ta sẽ có 12 cặp và ta chỉ cần 3 cặp.
- Cuối cùng giải phương trình bậc 3 là ra flag.

**- Tóm lại:**
- Bước 1: truy cập vào server nhiều lần để lấy c1, c2, c3 và e1, e2, e3.
- Bước 2: với từng cặp m, e. Ta thực hiện decrypt nó trong trường p hoặc q, và để decrypt được thì ta phải kiểm tra xem có tồn tại d trong trường hợp đó không (tức gcd(e, p-1) hoặc gcd(e, q-1) == 1).
- Bước 3: Giải crt để ra m1, m2, m3.
- Bước 4: Giải phương trình bậc 3.

## Code

from pwn import *
from Crypto.Util.number import getPrime, inverse, GCD, long_to_bytes
from sympy.ntheory.modular import crt
from sympy import symbols, solve
import itertools
import sys
import ast 

context.log_level = 'debug'

def get_data():
    collected_data = []
    
    r = process(['python3', '-u', 'chall.py'], level='error')
    
    for i in range(10): 
        r.recvuntil(b'> ') 
        r.sendline(b'1')

        p = getPrime(256)
        q = getPrime(256)
                
        r.recvuntil(b'separated by comma: ')
        payload = f"{p},{q}"
        r.sendline(payload.encode())

        r.recvuntil(b'> ') 
        r.sendline(b'2')

        cipher_list = []
        for _ in range(3):
            line = r.recvline().strip().decode()
            e_val, c_val = ast.literal_eval(line)
            cipher_list.append((e_val, c_val))
                
        collected_data.append((p, q, cipher_list))
        print(i)

    r.close()
    return collected_data

def decrypt(e, c, p_or_q):
    if GCD(e, p_or_q - 1) != 1:
        return None
    d = inverse(e, p_or_q - 1)
    return pow(c, d, p_or_q)

data = get_data()
    
residues_list = [[], [], []] 
moduli_list = [[], [], []]

for p, q, cipher_list  in data:
    for idx_msg in range(3):
        e, c = cipher_list[idx_msg]

        m_p = decrypt(e, c, p)
        if m_p is not None:
            residues_list[idx_msg].append(m_p)
            moduli_list[idx_msg].append(p)

        m_q = decrypt(e, c, q)
        if m_q is not None:
            residues_list[idx_msg].append(m_q)
            moduli_list[idx_msg].append(q)

vals = []
for i in range(3):
    val, _ = crt(moduli_list[i], residues_list[i])
    vals.append(val)

m1 = vals[0]      
m2 = vals[1]       
m3 = vals[2]  

x = symbols('x')
equation = x**3 - m2 * x**2 + m3 * x - m1
    
roots = solve(equation, x)
    
flag_parts = []
for r in roots:
    part = long_to_bytes(int(r))
    flag_parts.append(part)

for p in itertools.permutations(flag_parts):
    check = b'W1{????????????????????????????????}'
    flag = b''.join(p)
    if flag == check:
        print(flag.decode())
        break

# KMA_RAS
Trước khi vào bài thì em xin cảm ơn anh Đức rất nhiều vì hint <3
---

## Đề bài
:::spoiler chall.py

from Crypto.Util.number import *
from math import prod
import random

class RAS(object):
    def __init__(self, arr):
        self.n = prod(arr)*prod(arr)
        
    def generate_e(self):
        e = random.getrandbits(4048)
        return e
    
    def encrypt(self, pt):
        e = self.generate_e()
        assert self.n.bit_length() == 4048
        c = [pow(m, e, self.n) for m in pt]
        return  c
        
flag = b'KMACTF{???????????????????????????????}'
flag1, flag2, flag3 = bytes_to_long(flag[:len(flag)//3]), bytes_to_long(flag[len(flag)//3:2*len(flag)//3]), bytes_to_long(flag[2*len(flag)//3:])

# shuffle it
m1 = flag3
m2 = 65537*flag1**2 + flag3*flag2**2 

menu = '''
Welcome to my RAS stolen from tvd2004
1. Send primes
2. Get encrypted flag
'''

while True : 
    print(menu)
    choose = input('> ')
    if choose == '1':
        
        try:
            count = int(input(f"Not 1, not 2, you can choose number prime in RSA system : "))
        except :
            exit()
            
        arr = []
        for i in range(count) :
            p = int(input(f"Prime {i} : "))
            arr.append(p)
        
        ras =  RAS(arr)
        
    elif choose == '2':
        
        print("Here is ciphertext :")
        print(ras.encrypt([m1,m2]))
        
    else:
        raise Exception("Invalid choice!!!")

:::

## Ý tưởng
- Phân tích code: đề cho phép ta nhiều hơn 2 số chứ không chỉ dừng lại ở p, q. Và nó sẽ xuất ra c1, c2. Bài này khác bài trên ở việc nó không cho ta biết e.
- Dựa trên hint của anh Đức thì mình biết rằng bài này phải sử dụng `carmichael lambda function` và mình đã viết riêng cho nó một bài ở [đây](https://hackmd.io/@dkoazw/B1drWqASZe).
- Trước tiên, mình sẽ nhập vào 2 số **(khúc này không đúng lắm, xin hãy đọc danger ở cuối bài)**, số đầu tiên là thằng n1 với `lambda = 720720`, và n2 chỉ để đệm cho đủ bit đề yêu cầu.

from Crypto.Util.number import *
from sage.all import *
from math import isqrt

smooth = Integer(720720)
div = smooth.divisors()[::-1]
primes_div = [d+1 for d in div if (d+1).is_prime()]

n1 = Integer(1)
for p in primes_div[:]:  
    if n1.bit_length() + p.bit_length() <= 1012:
        n1 *= p
        primes_div.remove(p)
print(f"n1 = {n1}")

target_min_N_squared = 1 << 4047 
min_N = isqrt(target_min_N_squared)

min_n2 = min_N // n1 + 1

n2 = next_prime(min_n2)

print(f"n2 = {n2}")

N = n1 * n2
final_val = N * N
print(f"Check bit_length: {final_val.bit_length()}")

Note: có ăn cắp một phần code của anh Đức <(")
:::info
Lý do ta chọn 720720, vì đây là một số siêu hợp, tức nó có rất nhiều ước số, nên ta sẽ lọc được nhiều số p = i + 1 là một số nguyên tố. Tức là lúc này n1 = p1 * p2 * ... * pn thì khi ta tính lcm, nó sẽ là 720720.
:::
- Tuy nhiên vấn đề lúc này là gcd(lambda, e) có thể != 1. Và ở trên mình có làm 1 bài gặp trường hợp giống vậy, tuy nhiên bài ở trên ta biết e, nhưng bài dưới này thì không, vì thế ta phải tìm cách chứng minh gcd(lambda,e) == 1, nếu không thì thoát và connect lại bài khác. Và mình sẽ thực hiện chứng minh như sau:
- Theo định lý carmichael:
$$
a^{\lambda (n)} \equiv 1 \ (mod \ n)
$$
Thì với bài này, ta sẽ xử lý trong thằng n1, tức là lúc này:
$$
c^{\lambda (n)} \equiv 1 \ (mod \ n1)
$$
- Gọi g = gcd(lambda, e).
=>
$$
c^{\lambda (n)/g} \equiv m^{e*\lambda (n)/g} \ (mod \ n1)
$$
Ta có:
$$
e = g*k
$$
=>
$$
m^{e*\lambda (n1)/g} = m^{k*\lambda (n1)}
$$
Mà
$$
m^{k*\lambda (n)} \equiv 1 \ (mod \ n1)
$$
Từ đó ta có thể suy ra rằng:
$$
c^{\lambda (n)/g} \equiv 1 \ (mod \ n1)
$$
Vậy, ta sẽ thử thay g bằng các ước số của lambda(n), nếu g lớn nhất mà đồng dư với 1 chính là g = 1 thì gcd(lambda,e) == 1.
- Tiếp theo, ta sẽ giải bài toán trong trường lambda, lúc này ta sẽ tạo ra e_ = e % lambda, và vì thế ta sẽ bruteforce e_ từ (0, lambda -1). Nhìn lại output ở đầu, ta có thằng m1 = flag3, và vì thế ta sẽ tìm d bằng cách bruteforce e. Để biết đâu là d1 đúng thì ta có 2 điều kiện: 1 là tồn tại phép tính d1 = pow(e, -1, lambda), 2 là m1 = pow(c1, d, n1) phải printable.
- Khi tìm ra được d thì ta có thể tìm được m2.
- Khúc này thì mình hết cứt, không biết giải m2 <3.

## Script tạm

from Crypto.Util.number import *
from pwn import *
from sage.all import *
import math
    
smooth = Integer(720720)
div = smooth.divisors()[::-1]
primes_div = [d+1 for d in div if (d+1).is_prime()]

n1 = Integer(1)
for p in primes_div[:]:  
    if n1.bit_length() + p.bit_length() <= 1012:
        n1 *= p
        primes_div.remove(p)
print(f"n1 = {n1}")

target_min_N_squared = 1 << 4047 
min_N = isqrt(target_min_N_squared)

min_n2 = min_N // n1 + 1

n2 = next_prime(min_n2)

print(f"n2 = {n2}")

N = n1 * n2
final_val = N * N
print(f"Check bit_length: {final_val.bit_length()}")

io = process(["python3", "chall.py"])

io.recvuntil(b"> ")
io.sendline(b"1")

io.recvuntil(b"RSA system : ")
io.sendline(b"2")


io.recvuntil(b": ")
io.sendline(str(n1).encode())

io.recvuntil(b": ")
io.sendline(str(n2).encode())

io.recvuntil(b"> ")  
io.sendline(b"2")

io.recvuntil(b"Here is ciphertext :\n")
data = io.recvline().decode().strip()

c1, c2 = eval(data) 

print(f"c1 = {c1}")
print(f"c2 = {c2}")

io.close()

c1_ = c1 % n1
c2_ = c2 % n1

for i in div[::]:
    a = pow(c1_, 720720 // i, n1)
    if a == 1:
        g = i
        break
print(f"g = {g}")

if g == 1: 
    for e in range(g, 720720):
        if gcd(e, 720720) != g:
            continue

        h = e // g
        L = 720720 // g
        d = pow(h, -1, L)

        m1_try = pow(c1_, d, n1)
        m2_try = pow(c2_, d, n1)

        if all(chr(b) in string.printable for b in long_to_bytes(m1_try)):
            m1 = m1_try
            m2 = m2_try
            print(f"m1 = {m1}")
            print(f"m2 = {m2}")
            print(f"flag3 = {long_to_bytes(m1)}")
            break

:::danger
khi đang viết wu thì mình nhận ra không phải là ta nhập thẳng n1, n2 vào, mà chính xác phải là ta nhập các số nguyên tố p1, p2, p3, ...,pn và n2 vào. Với n1 = p1 * p2 * ... * pn. (Đây là sai sót của mình vì đã hiểu sai vấn đề nhưng mà lười sửa code quá <("))
:::