# Introduction
### Finding flags
Ở bài đầu giúp ta làm quen với format của flag, chỉ cần nộp flag trên đề bài là được
#### Flag: `crypto{y0ur_f1rst_fl4g}`

### Great Snakes
Ở bài này giúp ta biết về python và chạy code python được cho sẽ ra flag
#### Flag: `crypto{z3n_0f_pyth0n}`

### Network Attacks
Ở bài này giới thiệu chúng ta module **pwntools**, hỗ trợ chúng ta trong các challenge phải kết nối với server
Challenge cho ta code mẫu, chỉ cần thay đổi thành **buy:flag** thì server sẽ trả về flag

from pwn import * # pip install pwntools
import json

HOST = "socket.cryptohack.org"
PORT = 11112

r = remote(HOST, PORT)


def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)


print(r.readline())
print(r.readline())
print(r.readline())
print(r.readline())

request = {
    "buy": "flag"
}
json_send(request)

response = json_recv()

print(response)

#### Flag: `crypto{sh0pp1ng_f0r_fl4g5}`

# General
## Encoding
### ASCII
Dãy số được cho trong bài là thứ tự của các kí tự trong mã ASCII, ta có thể dùng đoạn code sau để chuyển đổi

Flag = [99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]
print("".join(chr(o) for o in Flag))


#### Flag: `crypto{ASCII_pr1nt4bl3}`

### Hex
Đoạn mã trong bài cho là mã hex, ta có thể sử dụng hàm **bytes.fromhex()** trong python để chuyển sang dạng byte sau đó dùng hàm **decode** để chuyển thành mã UTF-8

flag = '63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d'
print(bytes.fromhex(flag).decode())

#### Flag: `crypto{You_will_be_working_with_hex_strings_a_lot}`

### Base64
Đoạn mã được cho trong bài là mã hex, theo yêu cầu đề bài ta sẽ chuyển mã hex đó sang bytes sau đó mã hóa nó thành mã base64 , ta có thể **import module base64** và sử dụng hàm **base64.b64encode()** để encode đoạn mã

from base64 import b64encode

flag = bytes.fromhex('72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf')
print(flag)
print(b64encode(flag).decode())


#### Flag: `crypto/Base+64+Encoding+is+Web+Safe/`

### Encoding Challenge
Challenge cho file 13377.py là file chứa đoạn code thực thi của **"socket.cryptohack.org 13377"**

from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener # this is cryptohack's server-side module and not part of python
import base64
import codecs
import random

FLAG = "crypto{????????????????????}"
ENCODINGS = [
    "base64",
    "hex",
    "rot13",
    "bigint",
    "utf-8",
]
with open('/usr/share/dict/words') as f:
    WORDS = [line.strip().replace("'", "") for line in f.readlines()]


class Challenge():
    def __init__(self):
        self.challenge_words = ""
        self.stage = 0

    def create_level(self):
        self.stage += 1
        self.challenge_words = "_".join(random.choices(WORDS, k=3))
        encoding = random.choice(ENCODINGS)

        if encoding == "base64":
            encoded = base64.b64encode(self.challenge_words.encode()).decode() # wow so encode
        elif encoding == "hex":
            encoded = self.challenge_words.encode().hex()
        elif encoding == "rot13":
            encoded = codecs.encode(self.challenge_words, 'rot_13')
        elif encoding == "bigint":
            encoded = hex(bytes_to_long(self.challenge_words.encode()))
        elif encoding == "utf-8":
            encoded = [ord(b) for b in self.challenge_words]

        return {"type": encoding, "encoded": encoded}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, your_input):
        if self.stage == 0:
            return self.create_level()
        elif self.stage == 100:
            self.exit = True
            return {"flag": FLAG}

        if self.challenge_words == your_input["decoded"]:
            return self.create_level()

        return {"error": "Decoding fail"}


listener.start_server(port=13377)

Đoạn code trên cho chúng ta biết, khi kết nối tới socket thì nó sẽ gửi lại một đoạn mã ở dạng **base64, rot13, bigint** hoặc **utf-8**. Nhiệm vụ của chúng ta là phải giải mã nó và gửi lại cho server.

Làm như vậy cho tới khi vượt qua *100 levels*. Đây là đoạn code để solve challenge.

import json
import codecs
from Cryptodome.Util.number import * 

r = remote('socket.cryptohack.org', 13377, level = 'debug')

def json_recv():
    line = r.recvline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)



for i in range(100):
    received = json_recv()

    print("Received type: ")
    print(received["type"])
    print("Received encoded value: ")
    print(received["encoded"])

    decoded = None

    if received["type"] == "base64":
                decoded = base64.b64decode(received["encoded"]).decode() # wow so encode
    elif received["type"] == "hex":
                decoded =  bytes.fromhex(received["encoded"]).decode()
    elif received["type"] == "rot13":
                decoded = codecs.decode(received["encoded"], 'rot_13')
    elif received["type"] == "bigint":
                decoded = bytes.fromhex(received["encoded"][2:]).decode()
    elif received["type"] == "utf-8":
                decoded = "".join(chr(b) for b in received["encoded"])


    to_send = {
        "decoded": decoded
    }
    json_send(to_send)

json_recv()

#### Flag: `crypto{3nc0d3_d3c0d3_3nc0d3}`

## XOR
### XOR Starter
Bài trên cho ta biết về phép xor trong máy tính. Nhiệm vụ ở đây là ta sẽ xor từng kí tự trong chữ **"label"** với số 13.

from pwnlib.util.fiddling import xor

flag = b'label'
print(xor(flag, 13).decode())


#### Flag: `crypto{aloha}`

### XOR Properties
Bài trên cho ta biết về tính chất của phép xor, nếu có **KEY1 ^ KEY2 ^ KEY3 = KEY4**, thì **KEY4 ^ KEY3 = KEY1 ^ KEY2**. Nghĩa là khi hai KEY giống nhau xor với nhau thì chúng sẽ bằng 0.

Theo đề bài ta sẽ thấy, FLAG = FLAG ^ KEY1 ^ KEY2 ^ KEY3 ^ KEY1 ^ KEY2 ^ KEY3

from pwnlib.util.fiddling import xor

KEY1 = bytes.fromhex('a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313')
KEY23 = bytes.fromhex('c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1')
flag = bytes.fromhex('04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf')


print(xor(flag, KEY1, KEY23).decode())

#### Flag: `crypto{x0r_i5_ass0c1at1v3}`

### Favourite byte
Tác giả xor mã hex ở trên với 1 byte, suy ra ta chỉ cần bruteforce từ số 0 tới 255, để tìm được flag

from pwn import *

flag = bytes.fromhex('73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d')
for i in range(256): 
    real = xor(flag,i).decode()
    if real.find("crypto") != -1:
        print(i, ': ',real)
        break

#### Flag: `crypto{0x10_15_my_f4v0ur173_by7e}`

### You either know, XOR you don't
Với gợi ý của bài là xor với format của flag là **crypto{**

from pwn import *
flag = bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104')
key = xor(flag, "crypto{")
print(key)

Ta có đoán key là **myXORkey**
Tiếp theo ta xor mã với key

from pwn import *
flag = bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104')
key = xor(flag, "myXORkey")
print(key)

#### Flag: `crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}`
## Mathematics
### Greatest Common divisor
Ta dùng hàm **gcd** trong thư viện **math** của python

>>> import math
>>> math.gcd(66528, 52920)
1512

### Extended gcd
Ta sử dụng thuật toán **extended Euclidean**.

def gcdExtended(a, b): 
    if a == 0 : 
        return b,0,1   
    gcd,x1,y1 = gcdExtended(b%a, a) 
    x = y1 - (b//a) * x1 
    y = x1 
    return gcd,x,y 
a, b = 26513, 32321
g, x, y = gcdExtended(a, b) 
print("gcd(", a , "," , b, ") = ", g) 

gcd( 26513 , 32321 ) = 1
### Modular Arithmetic 1
- Ta cần tìm số dư khi chia 11 cho 6, 8146798528947 và 17

>>> min(11 % 6, 8146798528947 % 17)
4

### Modular Arithmetic 2

- Ta áp dụng định lý [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem).

`a^(p-1) ≡ 1 mod p <=> a^(p-1) % p = 1`

273246787654^65536 % 65537 =
273246787654^(65537-1) % 65537 = 1

### Modular Inverting

- Ta áp dụng định lý [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem).

`a^(p-1) ≡ 1 mod p <=> a^(p-1) % p = 1`

a^(p-1) ≡ 1 mod p
a^(p-1) * a^(-1) ≡ a^(-1) mod p
a^(p-2) * a * a^(-1) ≡ a^(-1) mod p
a^(p-2) ≡ a^(-1) mod p 
<=> 
a^(p-2) % p = a^(-1) 

- Ta chú ý là **a^(-1) là nghịch đảo modular của a**.

3 * d ≡ 1 mod 13
<=> 3^(13-2) % 13 = d 

- Ta có thể sử dụng hàm pow() để tính phép tính trên.

>>> pow(3, 13-2, 13)
9

## DATA FORMATS
### Privacy-Enhanced Mail?

- Ta mở file challenge ta thấy PEM-formatted RSA key


- Ta có thể dùng thư viện của Crypto để lấy private key d.

from Crypto.PublicKey import RSA

f = open('privacy_enhanced_mail.pem','r')
key = RSA.importKey(f.read())
print(key.d)

#### 15682700288056331364787171045819973654991149949197959929860861228180021707316851924456205543665565810892674190059831330231436970914474774562714945620519144389785158908994181951348846017432506464163564960993784254153395406799101314760033445065193429592512349952020982932218524462341002102063435489318813316464511621736943938440710470694912336237680219746204595128959161800595216366237538296447335375818871952520026993102148328897083547184286493241191505953601668858941129790966909236941127851370202421135897091086763569884760099112291072056970636380417349019579768748054760104838790424708988260443926906673795975104689

### CERTainly not

from Crypto.PublicKey import RSA

with open('2048b-rsa-example-cert.der','rb') as f:
    key = RSA.import_key(f.read())
print(key.n)

#### 22825373692019530804306212864609512775374171823993708516509897631547513634635856375624003737068034549047677999310941837454378829351398302382629658264078775456838626207507725494030600516872852306191255492926495965536379271875310457319107936020730050476235278671528265817571433919561175665096171189758406136453987966255236963782666066962654678464950075923060327358691356632908606498231755963567382339010985222623205586923466405809217426670333410014429905146941652293366212903733630083016398810887356019977409467374742266276267137547021576874204809506045914964491063393800499167416471949021995447722415959979785959569497

### SSH Keys


from Crypto.PublicKey import RSA
f = open('bruce_rsa.pem', 'r')
pubkey = RSA.import_key(f.read())
print(pubkey.n)

### Transparency


> Đọc tệp PEM có tên “transparency.pem” chứa khóa công khai.
> Nhập khóa và trích xuất khóa công khai.
> Khóa công khai sau đó được xuất dưới định dạng DER.
> Tính toán mã băm SHA-256 từ khóa công khai được mã hóa DER.
> Cuối cùng, in ra SHA-256 của khóa công khai.

import hashlib
from Crypto.PublicKey import RSA

pem = open('transparency.pem', 'r').read()
key = RSA.importKey(pem).public_key()

der = key.exportKey(format='DER')
sha256 = hashlib.sha256(der)
sha256_fingerprint = sha256.hexdigest()

print(f"Public Key SHA256: {sha256_fingerprint}")

#### Public Key SHA256: 29ab37df0a4e4d252f0cf12ad854bede59038fdd9cd652cbc5c222edd26d77d2

# Mathematics

## MODULAR MATH

### Quadratic Residues

Đề bài yêu cầu trong các số thuộc mảng ints, tìm **căn bậc hai theo mô tả của đề**, lấy số nhỏ nhất.

p = 29
ints = [14, 6, 11]

for a in range(29):
  a2 = pow(a,2,29)
  if a2 in ints:
    print(a2,a)

#### 6 8
#### 6 21

### Legendre Symbol

Ở bài này yêu cầu **tìm căn bậc hai theo mô tả của để**, lấy số nhỏ nhất. Tương tự như bài Quadratic Residues, nhưng với **các số rất lớn**

Cách ở bài trước không thể áp dụng được ở bài này, tuy nhiên, ta có thể áp dụng ***Legendre***


[Quadratic reciprocity](https://en.wikipedia.org/wiki/Quadratic_reciprocity)
- 

[Legendre symbol](https://en.wikipedia.org/wiki/Legendre_symbol)
- 

Dựa vào công thức trên, ta có thể tính được dù với số rất lớn

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

quadr_res = []
for n in ints:
    if pow(n, (p-1)//2, p) == 1:
        quadr_res.append(n)

print(pow(quadr_res[0], (p + 1) // 4, p))

### Modular Square Root

Ở challenge này chúng ta sẽ dùng thuật toán ***Tonelli-Shanks*** để thực hiện yêu cầu

def legendre_symbol(a, p):
    """
    Legendre symbol: Determines if 'a' is a quadratic residue modulo an odd prime 'p'.
    [^1^][5](http://en.wikipedia.org/wiki/Legendre_symbol)
    """
    ls = pow(a, (p - 1) // 2, p)
    if ls == p - 1:
        return -1
    return ls

def prime_mod_sqrt(a, p):

    a %= p

    # Simple cases
    if a == 0:
        return [0]
    if p == 2:
        return [a]

    # Check solution existence for odd prime
    if legendre_symbol(a, p) != 1:
        return []

    # Simple case for p ≡ 3 (mod 4)
    if p % 4 == 3:
        x = pow(a, (p + 1) // 4, p)
        return [x, p - x]

    # Factor p-1 as q * 2^s (with Q odd)
    q, s = p - 1, 0
    while q % 2 == 0:
        s += 1
        q //= 2

    # Select a z which is a quadratic non-residue modulo p
    z = 1
    while legendre_symbol(z, p) != -1:
        z += 1

    c = pow(z, q, p)

    # Search for a solution
    x = pow(a, (q + 1) // 2, p)
    t = pow(a, q, p)
    m = s

    while t != 1:
        # Find the lowest i such that t^(2^i) = 1
        i, e = 0, 2
        for i in range(1, m):
            if pow(t, e, p) == 1:
                break
            e *= 2

        # Update next value to iterate
        b = pow(c, 2**(m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i

    return [x, p - x]

if __name__ == "__main__":
    a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768

    p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

    solutions = prime_mod_sqrt(a, p)
    print(f"Solutions for x^2 ≡ {a} (mod {p}): {solutions}")

### Chinese Remainder Theorem

**Yêu cầu của đề**

[Định lý số dư Trung Hoa – Chinese Remainder Theorem](https://drx.home.blog/2018/07/25/dinh-ly-so-du-trung-hoa/)
Dựa vào trang trên, ta rút ra công thức để tính

def gcdExtended(a, b):
    global x, y
 
    if (a == 0):
        x = 0
        y = 1
        return b
 
    gcd = gcdExtended(b % a, a)
    x1 = x
    y1 = y
 
    x = y1 - (b // a) * x1
    y = x1
 
    return gcd
 
 
def modInverse(A, M):
 
    g = gcdExtended(A, M)
    if (g != 1):
        print("Inverse doesn't exist")
 
    else:
 
        res = (x % M + M) % M
        return res


M = 5 * 11 * 17
p1 = 5
p2 = 11
p3 = 17
a1 = 2
a2 = 3
a3 = 5
M1 = 11 * 17
M2 = 5 * 17
M3 = 5 * 11

y1 = modInverse(M1,p1)
y2 = modInverse(M2,p2)
y3 = modInverse(M3,p3)

flag = (a1*y1*M1 + a2*y2*M2 + a3*y3*M3) % M
print(flag)

## LATTICES

### Vectors


import numpy as np
v = np.asarray([2,6,3])
w = np.asarray([1,0,0])
u = (7,7,2)
# print(v@w)
#3*(2*v - w)*2
k = 3*(2*v - w)*2
#k * u
re = np.matmul(k,u) # nhân vô hướng vector
print(re)

### Size and Basis

from math import sqrt
def dot_product(v1,v2):
    return sum(a*b for a,b in zip(v1,v2))
def vector_norm(v):
    return sqrt(dot_product(v,v))
v = (4, 6, 2, 5)
print(vector_norm(v))

### Gram Schmidt

from math import sqrt
# Hàm nhân vector
def dot_product(v1, v2):
    return sum(a*b for a, b in zip(v1, v2)) # tương đương với a in v1 * b in v2

# Hàm tính norm ~ 2
def vector_norm(v):
    return sqrt(dot_product(v, v))

vectors = [[4, 1, 3, -1], [2, 1, -3, 4], [1, 0, -2, 7], [6, 2, 9, -5]]
# Gram smith
def gram_smith(vectors):
    u = []
    for i in range(len(vectors)):
        ui = vectors[i]
        for j in range(i):
            muj = dot_product(vectors[i], u[j]) / vector_norm(u[j])**2
            ui = [ui[k] - muj * u[j][k] for k in range(len(ui))]
        u.append(ui)
    return u

flag = round(gram_smith(vectors)[3][1],5)
print(flag)

### What's a Lattice?

import numpy as np
v1=[6, 2, -3]
v2=[5, 1, 4]
v3=[2, 7, 1]

numpy_array=np.asarray([v1,v2,v3])
det = np.linalg.det(numpy_array)
print(f"Volume: {abs(det)}")

### Gaussian Reduction

import numpy as np
from math import sqrt
def dot_product(v1, v2):
    return sum(a*b for a, b in zip(v1, v2)) # tương đương với a in v1 * b in v2
def vector_norm(v):
    return sqrt(dot_product(v, v))

v = [846835985, 9834798552]
u = [87502093, 123094980]


def gauss_reduction(v1, v2):
    while True:
        if vector_norm(v2) < vector_norm(v1):
            v1, v2 = v2, v1 # swap step
        m = round( dot_product(v1,v2) / dot_product(v1,v1) )
        if m == 0:
            return (v1, v2)
        k = [m * x for x in v1]
        v2 = [x1 - x2 for x1,x2 in zip(v2,k)] # reduction step

basis = gauss_reduction(v,u)

flag = dot_product(basis[0],basis[1])

print(flag)

### Find the Lattice

from Crypto.Util.number import getPrime, inverse, long_to_bytes
import random
import math
from math import sqrt

FLAG = b'crypto{?????????????????????}'





def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)


def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e


def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m


def dot_product(v1, v2):
    return sum(a*b for a, b in zip(v1, v2)) # tương đương với a in v1 * b in v2
def vector_norm(v):
    return sqrt(dot_product(v, v))

# Tìm cơ sở có n2-norm nhỏ
def gauss_reduction(v1, v2):
    while True:
        if vector_norm(v2) < vector_norm(v1):
            v1, v2 = v2, v1 #đổi chỗ
        m = round( dot_product(v1,v2) / dot_product(v1,v1) )
        if m == 0:
            return (v1, v2)
        k = [m * x for x in v1]
        v2 = [x1 - x2 for x1,x2 in zip(v2,k)] # Bước giảm


public, private = gen_key()
q, h = 7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257, 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800

# fh = g[q]

v1 = [1,h]
v2 = [0,q]
basis = gauss_reduction(v1,v2)


# Suy ra
f, g = basis[0][0], basis[0][1] # có thể vector còn lại
e = 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523

flag = long_to_bytes(decrypt(q,h,f,g,e))

print(flag)

# RSA
## STARTER
### RSA Starter 1
Ở bài này giới thiệu tới hàm **pow()** trong python, nó có thể vừa thực hiện phép mũ một số lên vừa mod nó cho một số khác. Việc này có lợi cho mã hóa, vì dễ thực thi theo một chiều, còn để tìm chiều ngược lại thì rất khó.

Ta sẽ thực hiện câu lệnh sau để tìm solution
`print(pow(101, 17, 22663))`
#### Solution: `19906`

### RSA Starter 2
Bài này cho ta biết một **public key** bao gồm những gì, nó sẽ là một cặp số **(N, e)** với e là số mũ (thường là 65537) và N là số được nhân bởi 2 số nguyên tố bất kì.

Ta giải bài này với câu lệnh sau:

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

#### Solution: `301`

### RSA Starter 3
Ở bài này cho ta biết được về phi hàm Euler, nếu một số là số nguyên tố thì 
Đề bài cho `N = p * q`, với p và q là hai số nguyên tố, ta có thể tính phi hàm của N như sau
#### Solution: `882564595536224140639625987657529300394956519977044270821168`

### RSA Starter 4
Bài này cho ta biết về private key và công thức của nó là `d = e^(-1) mod N`với d là private key

from Cryptodome.Util.number import inverse
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
N = (p-1)*(q-1)
d = inverse(e, N)
print(d)

#### Solution: `121832886702415731577073962957377780195510499965398469843281`

### RSA Starter 5
Bài này ta sẽ decrypt để tìm số ban đầu, sử dụng private key ở bài trước, sau đó ta sử dụng công thức `c^d mod N` để decrypt

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
d = 121832886702415731577073962957377780195510499965398469843281
c = 77578995801157823671636298847186723593814843845525223303932

base = pow(c, d, N)
print(base)

#### Solution: `13371337`

### RSA Starter 6
Bài này giúp ta biết cách mà bạn chúng ta biết được đây là tin nhắn từ chúng ta, và bài yêu cầu mã hóa xâu `crypto{Immut4ble_m3ssag1ng}` với private được cho trong file `private.key`

from hashlib import sha256
from Cryptodome.Util.number import bytes_to_long, long_to_bytes
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

flag = "crypto{Immut4ble_m3ssag1ng}"
sh = sha256(flag.encode()).digest()
c = pow(bytes_to_long(sh), d, N)
print(c)

#### Solution: `13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475`

## PRIMES PART 1
### Factoring
Bài này yêu cầu ta tìm hai số nguyên tố đã tạo nên số `N = 510143758735509025530880200653196460532653147 ` và nhập số nhỏ hơn vào chỗ submit
Ta có thể sử dụng trang web [factordb](http://www.factordb.com) để tìm hai số đó
#### Solution: `19704762736204164635843`

### Inferius Prime

Ở bài này ta sẽ được cho đoạn code python, trong đó có và output.txt bao gồm ciphertext và số N, đọc đoạn code dưới đây ta có thể biết được cách decrypt

#!/usr/bin/env python3

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

e = 3

# n will be 8 * (100 + 100) = 1600 bits strong which is pretty good
while True:
    p = getPrime(100)
    q = getPrime(100)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    if d != -1 and GCD(e, phi) == 1:
        break

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

Đoạn code decrypt, với p và q có thể tìm được bằng trang web ở challenge trước

from Cryptodome.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

n = 742449129124467073921545687640895127535705902454369756401331
ct = 39207274348578481322317340648475596807303160111338236677373
e = 3

p = 752708788837165590355094155871
q = 986369682585281993933185289261

phi = (p-1)*(q-1)
d = inverse(e, phi)

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)

print(decrypted)

#### Flag: `crypto{N33d_b1g_pR1m35}`

### Monoprime30
Bài này giúp ta tìm hiểu thêm tại sao không nên chỉ dùng một số nguyên tố để tạo khóa, vì như vậy sẽ rất dễ tìm số nguyên tố đó và tin tặc có thể dễ dàng giải mã
Code giải mã từ output đề cho

from Cryptodome.Util.number import inverse, long_to_bytes
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

phi = (n-1)
d = inverse(e, phi)

decrypted = long_to_bytes(pow(ct, d, n))
print(decrypted)

#### Flag: `crypto{0n3_pr1m3_41n7_pr1m3_l0l}`

### Square Eyes
Từ công thức hình dưới đây ta có thể tìm phi hàm euler từ output của đề bài, với **n = p*p** và p là một số nguyên tố
Đây là code, với p ta có thể tìm từ trang web factordb

from Cryptodome.Util.number import long_to_bytes, inverse
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

p = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107

phi = p*(p-1)
d = inverse(e, phi)

decrypted = long_to_bytes(pow(ct, d, n))
print(decrypted)

#### Flag: `crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}`

### Manyprime
Bài này có cách làm như bài trước, ta có thể dùng trang web factordb hoặc sử dụng thư viện factordb trong python

from Cryptodome.Util.number import long_to_bytes, inverse
from factordb.factordb import FactorDB
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

phi = 1
f = FactorDB(n)
f.connect()
lprime = f.get_factor_list()

for i in lprime:
    phi *=  i-1
d = inverse(e, phi)

decrypted =long_to_bytes(pow(ct, d, n))
print(decrypted)

#### Flag: `crypto{700_m4ny_5m4ll_f4c70r5}`

## Public exponent
Bài này cho ta một số mũ nhỏ là e = 1, ta thực hiện tính toán như những bài trước và được flag

from Cryptodome.Util.number import long_to_bytes, inverse
from factordb.factordb import FactorDB

n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

phi = (n-1)
d = inverse(e, phi)

decrypted = long_to_bytes(pow(ct, d, n))

print(decrypted)

#### Flag: `crypto{saltstack_fell_for_this!}`

### Modulus Inutilis
Ở bài này ta có thể thấy được số để mod lớn hơn ciphertext rất nhiều, nên về cơ bản ta chỉ cần thực hiện căn ba ciphertext là được flag
Code gốc của bài:

#!/usr/bin/env python3

from Cryptodome.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

Code để decrypt

from Cryptodome.Util.number import long_to_bytes, inverse
from factordb.factordb import FactorDB
from sympy import cbrt

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

print(long_to_bytes(cbrt(ct)))

#### Flag: `crypto{N33d_m04R_p4dd1ng}`

### Everything is Big
Ở bài này các giá trị như số mod N, số e và ciphertext quá lớn nên ta có thể sử dụng thuật toán **Wiener's attack từ sagemath**
Code dùng để chạy trên sagemath

from Crypto.Util.number import long_to_bytes
def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None

N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474

d = wiener(e, N)
m = pow(c, d, N)
print(long_to_bytes(m))

#### Flag: `crypto{s0m3th1ng5_c4n_b3_t00_b1g}`

### Crossed Wires
Từ công thức ở hình dưới ta có suy ra được số mod của những người bạn, và với mũ e từ những người bạn thì ta chỉ cần nghịch đảo tích của chúng và mod với số vừa tìm được

from Cryptodome.Util.number import inverse, long_to_bytes
c = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117

n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771

e = 65537
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097

fk = [106979, 108533, 69557, 97117, 103231]
ed1 = e*d-1
k = inverse(106979 * 108533 * 69557 * 97117 * 103231, ed1)
m = pow(c, k, n)
print(long_to_bytes(m))

#### Flag: `crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}`

### Everything is Still Big
Ở bài này ta sẽ sử dụng thuật toán **Boneh_Durfee attack** từ sagemath để tìm private key. Đây là link [code](https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage) tìm được (sẽ phải thay số N và số e trong code), code này sẽ được chạy trên sagemath
Đây là code sau khi tìm được private key

from Cryptodome.Util.number import long_to_bytes
d = 4405001203086303853525638270840706181413309101774712363141310824943602913458674670435988275467396881342752245170076677567586495166847569659096584522419007
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b

decrypted = pow(c, d, N)
print(long_to_bytes(decrypted))

#### Flag: `crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}`

### Endless Emails
Ở bài này ta sẽ dùng thuật toán **Hastad's Broadcast Attack**

#!/usr/bin/python3
from sympy.ntheory.modular import crt
from itertools import combinations
from gmpy2 import iroot

N =[14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021, 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123, 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147, 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961, 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823, 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263, 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897]
e = 3
C = [6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225, 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172, 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153, 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577, 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805, 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749, 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144]
for i in list(combinations([i for i in range(7)],3)):
        n1, n2, n3 = N[i[0]], N[i[1]], N[i[2]]
        c1, c2, c3 = C[i[0]], C[i[1]], C[i[2]]
        m = bytes.fromhex(hex(iroot(crt((n1,n2,n3),(c1,c2,c3))[0],3)[0])[2:])
        if b'crypto' in m:
                print(m.decode())
                break

#### Flag: `crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}`