# WannaGame Cyber Knight 2024

## Warmup

- chall.py

from Crypto.Util.number import * 
from Crypto.Util.Padding import pad 
from flag import flag 
from gmpy2 import next_prime

message = b"The challenge's flag is: " + flag
assert len(message) % 3 == 0

part1 = message[ : len(message)//3]
part2 = message[len(message)//3 : 2*len(message)//3]
part3 = message[2*len(message)//3 : ]
sep = "#"*50

### part 1: Warm-up!!!
p1 = getPrime(512)
q1 = getPrime(512)
e1 = 11
n1 = p1 * q1
c1 = pow(bytes_to_long(part1), e1, n1)
print(f'{n1 = }')
print(f'{c1 = }')
print(sep)

### part 2: One more warm-up
p2 = getPrime(1024)
q2 = getPrime(1024)
n2 = p2*q2 
e2 = 17
print(f'{n2 = }')
print(f'Real: {pow(bytes_to_long(part2), e2, n2)}')
print(f'Fake: {pow(bytes_to_long(pad(part2, 16)), e2, n2)}')
print(sep)

### part 3: The last "warm-up"
p3,q3 = getPrime(1024), getPrime(1024)
n3 = p3 * q3
power1, power2 = getPrime(128), getPrime(128)
hint1 = pow((5*p3 + q3), power1, n3)
hint2 = pow((3*p3 - 6*q3), power2, n3)

e3 = next_prime(hint1 + hint2)
c3 = pow(bytes_to_long(part3), e3, n3)
print(f'{power1 = }')
print(f'{power2 = }')
print(f'{n3 = }')
print(f'{hint1 = }')
print(f'e3 = {e3}')
print(f'c3 = {c3}')

### Solution
- Ta thấy **FLAG** được chia làm 3 phần có độ dài bằng nhau và được encrypt theo những cách riêng.
- Trong lúc diễn ra giải mình đã decrypt part 2 đầu tiên
- Ta có thể thấy được phần **Real** là **FLAG** sau khi encrypt còn **FAKE** là `pad(FLAG)` sau khi decrypt
- Từ đây ta có thể bruteforce hết 16 trường hợp padding có thể và tìm **GCD** giữa 2 phương trình sẽ ra được (x - **FLAG**)
- Part 2:

from sage.all import *
from Crypto.Util.number import *
from Crypto.Util.Padding import pad

n2 = 19474122562778153703776906234103999694212644666605609184003798714902765132186442270466413951685774096672600567147343733732980015161843616032962680857426708013412213676449861264155297288378479051436442079937058938840721841860491557712477170366628773688474634289507561262017382779613838956398073685517438883550013563737919252844748012781298212795883037816078874734356565506037923530508679278288097627681354570158653097456586858900957218344882318145320067184688094419746980554117499065442646088691226289819440434740945671726394148366572739206464970977471727197412322136575227898097076974504287523260885786539573649783161
Real = 15636713266108700464255355282572617369877416762456096086219951374063737359559203674454786265210431923339051086905021926447634666321503985769492720281115251569517394409997291661224097948320454420612478527160246859233690225189444979403485318497052362506638619146425116246060495195223943704647051304805754627681254961634405541974848733951519522486396630609303328097791062133825888690738129275001884247653912942268589773666008633702027740289575546500039837328482189167641136880443555991865875325701485342918164649959219812272157959283006261464655737656031536878365520892164396734804695179528627342810772907739309174183304
Fake = 1901702486995025261538235880685531918771879286327896110111123890041702504494161154076737842357693655100992364579118174208323657012644698015659577716664514828814910889887457132697217080176306194565595589316187612945830703382031867854831608485926311704058671506309214522654866677161067649723883561755848469509892417562279714400249673848323509379109641015242793126408247724149712397397815568653344550396176143675147065423111733067480933601053636423334747702190300411842735906299712817499994397771633456847764374609445235276286713165285446045446123174200222508610983202190618557770618976371164659678708230871711252574428

def mygcd(f,g):
    while g != 0:
        r = g
        g = f % g
        f = r
    return f/f.lc()

P = PolynomialRing(Zmod(n2), 'x')   
x = P.gen()
p1 = x ** 17 - Real
test = b''
for i in range(16):
    padding = pad(test, 16)[i:]
    p2 = (2 ** ((16 - i) * 8) * x + bytes_to_long(padding)) ** 17 - Fake
    t = mygcd(p1, p2)
    if t.degree() == 1:
        print(long_to_bytes(int(-t[0]) % n2))
        break
    test += b'\x01'

_lA_15_h1hi__75f26f70b3fa1343153e

- Tiếp đến là part 1, sau khi decrypt xong part 2 ta biết được độ dài của từng thành phần là 33 ký tự và ta cũng biết được 25 ký tự đầu + thêm "W1{" là 28 ký tự. Giờ ta chỉ cần small_roots để tìm nốt phần còn lại.
- Part 1:

from sage.all import *
from Crypto.Util.number import *
from Crypto.Util.Padding import pad


n1 = 78100017093042237362585803611409807219210686771960485296694671535293298684240391999007937128416933959949645805107079926652343615109335481443408319617478348436412156203990196717356668119025919695447421356649708220217528303406969275048476878616591756855326600516077838718677582495646251901652030452534739980093
c1 = 21635094418936882229318713100837056867730099226953717083953338957077431886511252266065867668680214410547969294123420920750052299754539343424046939642019856856637610693840992502539517724666655388883948397275320947350529293996784254524553566619189584795444284261967162826834735297201762488824862476117397669601

message = b"The challenge's flag is: W1{\x00\x00\x00\x00\x00"
message = bytes_to_long(message)

P = PolynomialRing(Zmod(n1), 'x')   
x = P.gen()
f = (message + x) ** 11 - c1

FLAG = f.small_roots(X=2**50, beta=0.5, epsilon=0.015)
print(b"The challenge's flag is: W1{" + long_to_bytes(int(FLAG[0])))

The challenge's flag is: W1{A_p0r

- Đến với part cuối cùng, bạn có thể tham khảo Modular Binomials
- Giờ bạn chỉ cần bruteforce hết tất cả các hint2 phù hợp cho đến khi nào xuất hiện $p$ là được
- Part 3:

import math
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from gmpy2 import next_prime

power1 = 216515682056074917890546762360422775759
power2 = 181261651362416112447857910756974715253
n3 = 21359428772367567762465177652844235016399133661109374171468438854776561246101192389880378563002849491963133317822943728663659947135787662718455826488579139110050277672340965370240377096647337916266432987314270685198434379314123632571454622139263629066529934934145277818436942937601606973322506307539554768214679444922661752071123001107723044536675764939605450418550872933311130411355136155266638811137191949645399770280529254355150837851996371018266855150538183941848828564579160123399867316204489663532672172085306182442910667707542525506401104797512848908939121437800995819119455775357620426817733038470495147276793
hint1 = 21165771737478725950851391268640839742282738803460982495702522148737396455865260539601340347151173375617657055655041043517629027492240234235183580296831387302596600695810822254431016035932293471628759197250919622480691606652634091857970182748360357623125515085919940174799049558949629746381693045991973156293505919951290743073241929003963830080590083449251389368841868741731209817737242746289090221167945649864511277017186337822956848075038306043349755593388069666507069280026419826266727104285440789673438901905195589837692674191838634684368474851772930333812341283933491515890683850912453399208298386277684434445251
e3 = 37168304783168980393920173579379710993074140739837792931728618759911393587739974232300850198277091657299514225039110963445571485237776790392542202542871178828780578794970964528554601212794008256754381717435669983473010005148311575428821001052237868999060224515275873668669213982474419104490433570572105845650251833635244326980880559203371594232931397547585750248068741794286062945536039069446641110263273308725041343806223241749757368437839639116744539107461153105289738651458945715419945820612645097201055521095139028646379860663948813756288318543675883368961217287301785966051639519026541020372279840744062219039191
c3 = 1096068813757106861072993580055082418953963625562486119593706360815623910450146273178847639647973866883042811190136050041007753762866893600939527521717867763640548952449681014994092425911219237532793217675033536632826439864589482883751579581380877418411747043359264793736856167378058319757084322522347500331245555941134923517945671002893760566068668447306048296218747434127148067031352038287679665515172443331784546991573906825482519792803285599056922851777942853546318660474033734361350200902964188996923538488714615644961271863386265655804388494579456404108898159557142645993950324859997370434010675900211652602515
hint2 = 16002533045690254443068782310738871250791401936376810436026096611173997131874713692699509851125918281681857169384069919927942457745536556157358622246039791526183978099160142274123585176861714785125622520184750360992318398495677483570850818303877511375934709429355933493870164423524789358108740524580132689356745913683953583907638630199407764152341314098334360879226873052554853127798796323157550889095327658860530066789036903926800520362801333073394783514073083438782669371432525889153218716327204307527616619189943438808687186472110179071919843691902953035148876003368294450160955668114087621163981454466377784586475

while True:
    p = math.gcd((pow(3, (-power1 * power2), n3) * pow(hint2, power1, n3) - pow(5, (-power2 * power1), n3) * pow(hint1, power2, n3)) * (n3 - 6) % n3, n3)
    if p != 1:
        break
    
    hint2 += 1

p3 = p
p3 = 149980597760000270288020712564730421423970532153531109538283372659249090766781034501997790624701674901461522882220113357725378245572684453212159175961586586191733952945436353476578468558720453741235833653421187406171537615120165747876478240633282821626182454380149314563971827086993047558004886558019962996419
q3 = n3 // p3
assert p3 * q3 == n3

phi = (p3 - 1) * (q3 - 1)
d = pow(e3, -1, phi)
m = pow(c3, d, n3)
print(long_to_bytes(m))

a91411ae238_happy_hacking!!!!!!!}

- Kết hợp cả 3 part lại ta có được

W1{A_p0r_lA_15_h1hi__75f26f70b3fa1343153ea91411ae238_happy_hacking!!!!!!!}

## 435
- server.py

from Crypto.Cipher import AES 
from Crypto.Util import Counter
from Crypto.Util.number import long_to_bytes as ltb, bytes_to_long as btl
from Crypto.Util.Padding import pad, unpad
import os



GREEN = '\033[92m'
RED = '\033[91m'
YELLOW = '\033[33m'
NORM = '\033[0m'

BANNER = \
    f"""
    {YELLOW} 
 ___       __   ________  ________   ________   ________  ___       __     _____  ________      
|\  \     |\  \|\   __  \|\   ___  \|\   ___  \|\   __  \|\  \     |\  \  / __  \|\   ___  \    
\ \  \    \ \  \ \  \|\  \ \  \\\ \  \ \  \\\ \  \ \  \|\  \ \  \    \ \  \|\/_|\  \ \  \\\ \  \   
 \ \  \  __\ \  \ \   __  \ \  \\\ \  \ \  \\\ \  \ \   __  \ \  \  __\ \  \|/ \ \  \ \  \\\ \  \  
  \ \  \|\__\_\  \ \  \ \  \ \  \\\ \  \ \  \\\ \  \ \  \ \  \ \  \|\__\_\  \   \ \  \ \  \\\ \  \ 
   \ \____________\ \__\ \__\ \__\\\ \__\ \__\\\ \__\ \__\ \__\ \____________\   \ \__\ \__\\\ \__\\
    \|____________|\|__|\|__|\|__| \|__|\|__| \|__|\|__|\|__|\|____________|    \|__|\|__| \|__|

    {NORM}
Once upon a time, deep in the forest, there lies a great treasure but protected with a digital padlock. Rumor said that whoever could open the treasure would be rewarded with great riches. You, as a treasure hunter, decided to go on a trip to uncover this elusive prize. After facing countless obstacles and challenges, you finally reached the location of the treasure. Next to the treasure lies a truncated poem. You, as a master in cryptography also, will not give up easily right? Goodluck! ;)
    """



menu = \
f"""\
{NORM}
1. ECB_encrypt
2. CBC_decrypt
3. Crack Password
{"~"*100}
"""



class Riddle:
    def __init__(self, key, nonce):
        self.key = key
        self.nonce = nonce

    def GCM_encrypt(self, plaintext):
        """
        Return encryption of AES-GCM with provided plaintext
        """
        cipher_ = AES.new(self.key, AES.MODE_GCM, self.nonce)
        return cipher_.encrypt_and_digest(plaintext)

    def ECB_encrypt(self, plaintext):
        """
        Return encryption of AES-ECB with provided plaintext
        """
        cipher_ = AES.new(self.key, AES.MODE_ECB)
        return cipher_.encrypt(plaintext)

    def CBC_decrypt(self, iv, ciphertext):
        """
        Return decryption of AES-CBC with provided (ciphertext, iv)
        """
        cipher_ = AES.new(self.key, AES.MODE_CBC, iv)
        return cipher_.decrypt(ciphertext)



print(BANNER)

cipher = Riddle(key = os.urandom(16), nonce = os.urandom(12))


secret = os.urandom(256)
poem = \
pad(b"""\
The security code is simple, an intricate dance of numbers.
A shield against intruders, a fortress for slumbers.
Digits align in harmony, a secret melody they sing,
Guarding the treasures of a realm, where secrets take their wing : \
""", 16) + secret

print(secret.hex())


ciphertext, tag = cipher.GCM_encrypt(poem)

print(f"ct = '{ciphertext.hex()}'")
print(f"tag = '{tag.hex()}'")


while True:
    print(menu)
    option = int(input("Your choice > "))
    try:
        match option:
            case 1:
                m = bytes.fromhex(input("Please give me your message (in hex) > "))
                c = cipher.ECB_encrypt(m)
                print(c.hex())
            case 2:
                iv = bytes.fromhex(input("Please give me your iv (in hex) > "))
                c = bytes.fromhex(input("Please give me your ciphertext (in hex) > "))
                m = cipher.CBC_decrypt(iv, c)
                print(m.hex())
            case 3:
                key = bytes.fromhex(input("Give me your secret (in hex) > "))
                if key == secret:
                    FLAG = open('flag.txt', 'r').read()
                    print(f"{GREEN}Wow you did surprise me!! Here is your reward {FLAG}")
                    exit()
                else:
                    print("Ahh, try better next time :(")
                    exit()
            case _:
                print("No idea what you choose :(")
    except Exception as e: 
        print(f"{RED}An exception occurred: {str(e)}")

### Solution
- Bài này cho ta **ciphertext** và **tag** đã được encrypt qua AES GCM cũng với các chức năng **ECB_encrypt** và **CBC_decrypt**
- Ta biết phần encrypt của GCM hoặc động giống như Counter nên ta có thể đưa phần xor(ciphertext, plaintext) qua **CBC_decrypt** với IV = 0 để tìm lại được Counter
- Giờ ta chỉ cần cộng dần Counter lên rồi cho đi qua **ECB_encrypt** rồi lấy kết quả đó xor với ciphertext sẽ được xâu gốc

from Crypto.Cipher import AES 
from Crypto.Util import Counter
from Crypto.Util.number import *
from Crypto.Util.Padding import pad, unpad
import os
from pwn import *

# io = process(['python3', 'server.py'])
io = remote("45.122.249.68", 20024)

context.log_level = 'debug'

secret = os.urandom(256)
poem = \
pad(b"""\
The security code is simple, an intricate dance of numbers.
A shield against intruders, a fortress for slumbers.
Digits align in harmony, a secret melody they sing,
Guarding the treasures of a realm, where secrets take their wing : \
""", 16) + secret

io.recvuntil(b'ct = ')
ct = io.recvline().strip().decode()[1:-1]
ct = bytes.fromhex(ct)


test = xor(ct, poem)

io.sendafter(b'> ', b'2\n')
io.sendafter(b'> ', b"00" * 16 + b"\n")
io.sendafter(b'> ', test.hex().encode() + b'\n')

res = io.recvline().strip().decode()

res = res[:32]
counter = bytes_to_long(bytes.fromhex(res))

payload = b""
while len(payload) != len(ct):
    payload += long_to_bytes(counter)
    counter += 1

io.sendafter(b'> ', b'1\n')
io.sendafter(b'> ', payload.hex().encode() + b'\n')

res = io.recvline().strip().decode()
res = bytes.fromhex(res)

payload = xor(res, ct)[240:]
io.sendafter(b'> ', b'3\n')
io.sendafter(b'> ', payload.hex().encode() + b'\n')

io.interactive()

Wow you did surprise me!! Here is your reward W1{7hE_S3cRe7_L13s_4m0N9_M0De5_0f_0p3r4ti0n_cddde2b1d3eec22ffcd8c871faca7639}

## AESSS
- server.py

import os
import random
from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto.Hash import SHA256
from secret import FLAG

flag1 = FLAG[:len(FLAG)//3].encode()
flag2 = FLAG[len(FLAG)//3:2*len(FLAG)//3].encode()
flag3 = FLAG[2*len(FLAG)//3:].encode()

assert len(flag1) == len(flag2) == len(flag3) == 48

def pad(data, block_size):
    return data + (block_size - len(data) % block_size) * bytes([block_size - len(data) % block_size])


def challenge_part1(flag):
    key = os.urandom(16)
    iv = os.urandom(16)
    options = ['ecb', 'cbc', 'cfb', 'ofb', 'ctr']
    suboptions = ['data', 'flag']

    for _ in range(3):  # you only have 3 tries, stingy huh?
        [option, suboption, *more] = input('> ').split(' ')
        if option not in options:
            print('invalid option!')
            continue 
        if suboption not in suboptions:
            print('invalid suboption!')
            continue
        options.remove(option)

        if suboption == 'data':
            message = bytes.fromhex(more[0])
        else:
            message = flag

        if option == 'ecb':
            cipher = AES.new(key, AES.MODE_ECB)
        elif option == 'cbc':
            cipher = AES.new(key, AES.MODE_CBC, iv)
        elif option == 'cfb':
            cipher = AES.new(key, AES.MODE_CFB, iv, segment_size=128)
        elif option == 'ofb':
            cipher = AES.new(key, AES.MODE_OFB, iv)
        elif option == 'ctr':
            cipher = AES.new(key, AES.MODE_CTR,
                             counter=Counter.new(16, prefix=iv[:14]))

        ciphertext = cipher.encrypt(message)
        print(ciphertext.hex())
    else:
        print('No more options!')


def challenge_part2(flag):
    key = os.urandom(16)

    while True:
        try:
            options = input('> ').split(' ')
            if (options[0] == "encrypt_flag"):
                iv = os.urandom(16)
                cipher = AES.new(key, AES.MODE_GCM, iv)
                message = flag
                ciphertext= cipher.encrypt(message)
                print("Encrypted flag and tag, iv:", ciphertext.hex(), iv.hex())

            elif (options[0] == "encrypt_data"):
                iv = bytes.fromhex(options[1])
                cipher = AES.new(key, AES.MODE_GCM, iv)
                message = bytes.fromhex(input('input data:'))
                ciphertext= cipher.encrypt(message)
                print("Encrypted message and tag, iv:", ciphertext.hex(), iv.hex())
            else:
                print("Invalid option!")
        except Exception as e:
            print("An error occurred: ", e)
            break


def challenge_part3(flag):
    try:
        salt = os.urandom(2) # prevent rainbow table attack and ... brute force attack?
        password_file_path = os.path.join(os.path.dirname(__file__), "rockyou.txt") # rockyou.txt is a list of common passwords
        print(f"Looking for rockyou.txt at: {password_file_path}")

        if not os.path.isfile(password_file_path):
            print(f"Error: {password_file_path} not found")
            return

        with open(password_file_path, "rb") as file:
            passwords = file.readlines()[:100]

        password = random.choice(passwords).strip()
        key = SHA256.new(password + salt.hex().encode()).digest()[:16]
        cipher = AES.new(key, AES.MODE_ECB)
        ciphertext = cipher.encrypt(pad(password, 16))
        print("Encrypted password:", ciphertext.hex())

        input_password = input('input password:')
        if input_password.encode() == password:
            print("Correct password!")
            print("Good job! Here is your flag:", flag)
        else:
            print("Incorrect password!")

    except FileNotFoundError:
        print("rockyou.txt not found")
        return
    except Exception as e:
        print(f"An error occurred: {e}")
        return


def main():
    chall_option = input('challenge option:')
    if chall_option == '1':
        challenge_part1(flag1)
    elif chall_option == '2':
        challenge_part2(flag2)
    elif chall_option == '3':
        challenge_part3(flag3)
    else:
        print('Invalid option!')


if __name__ == '__main__':
    main()

### Solution
- Part 1:

import os
import random
from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto.Util.Padding import pad
from Crypto.Hash import SHA256
from pwn import *


io = remote("45.122.249.68", 20026)

context.log_level = "DEBUG"

io.sendlineafter(b"option:", b'1')
io.sendline(b"cfb data " + b"00" * 48)
enc1 = io.recvline().strip()[2:].decode()
print(enc1)
io.sendline(b"ofb flag")
enc2 = io.recvline().strip()[2:].decode()
print(enc2)
enc1 = bytes.fromhex(enc1)
enc2 = bytes.fromhex(enc2)
print(xor(enc1, enc2))

W1{AES_1s_w1d3ly_us3d_1n_r3al_w0rld_applic4t10ns

- Part 2:

import os
import random
from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto.Util.Padding import pad
from Crypto.Hash import SHA256
from pwn import *

io = remote("45.122.249.68", 20026)

context.log_level = "DEBUG"

io.sendlineafter(b"option:", b'2')
io.sendlineafter(b"> ", b"encrypt_flag")
io.recvuntil(b"iv: ")
enc1, iv = io.recvline().strip().decode().split(" ")
enc1 = bytes.fromhex(enc1)

io.sendlineafter(b"> ", b"encrypt_data" + b" " + iv.encode())
io.sendlineafter(b"input data:", b"00" * 48)
io.recvuntil(b"iv: ")
enc2, iv = io.recvline().strip().decode().split(" ")

enc2 = bytes.fromhex(enc2)
print(xor(enc1, enc2))

_4nd_1s_c0ns1d3r3d_t0_b3_0n3_0f_th3_m0st_s3cur3_

- Part 3:

import os
import random
from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto.Util.Padding import pad
from Crypto.Hash import SHA256
from pwn import *

io = remote("45.122.249.68", 20026)

context.log_level = "DEBUG"

io.sendlineafter(b"option:", b'3')
io.recvuntil(b"password: ")
enc = io.recvline().strip().decode()
print(enc)
with open("rockyou.txt", "rb") as file:
    passwords = file.readlines()[:100]

for password in passwords:
    password = password.strip()
    print(password)
    for bf1 in range(256):
        for bf2 in range(256):
            salt = bytes([bf1]) + bytes([bf2])
            key = SHA256.new(password + salt.hex().encode()).digest()[:16]
            cipher = AES.new(key, AES.MODE_ECB)
            ciphertext = cipher.encrypt(pad(password, 16))
            if ciphertext.hex() in enc or enc in ciphertext.hex():
                print("True")
                io.sendlineafter(b"input password:", password)
                io.interactive()

alg0r1thms_1n_pr4ct1c3_66e14a195cd4b2e9d5059ca1a

- Ghép cả 3 lại:

W1{AES_1s_w1d3ly_us3d_1n_r3al_w0rld_applic4t10ns_4nd_1s_c0ns1d3r3d_t0_b3_0n3_0f_th3_m0st_s3cur3_alg0r1thms_1n_pr4ct1c3_66e14a195cd4b2e9d5059ca1a

## Master of gacha
### Solution

from pwn import *
from sage.all import *
import random
import json
from Crypto.Util.number import *
from hashlib import sha256 

class Twister:
    N = 624
    M = 397
    A = 0x9908b0df

    def __init__(self):
        self.state = [[(1 << (32 * i + (31 - j))) for j in range(32)] for i in range(624)]
        self.index = 0

    @staticmethod
    def _xor(a, b):
        return [x ^ y for x, y in zip(a, b)]

    @staticmethod
    def _and(a, x):
        return [v if (x >> (31 - i)) & 1 else 0 for i, v in enumerate(a)]

    @staticmethod
    def _shiftr(a, x):
        return [0] * x + a[:-x]

    @staticmethod
    def _shiftl(a, x):
        return a[x:] + [0] * x

    def get32bits(self):
        if self.index >= self.N:
            for kk in range(self.N):
                y = self.state[kk][:1] + self.state[(kk + 1) % self.N][1:]
                z = [y[-1] if (self.A >> (31 - i)) & 1 else 0 for i in range(32)]
                self.state[kk] = self._xor(self.state[(kk + self.M) % self.N], self._shiftr(y, 1))
                self.state[kk] = self._xor(self.state[kk], z)
            self.index = 0

        y = self.state[self.index]
        y = self._xor(y, self._shiftr(y, 11))
        y = self._xor(y, self._and(self._shiftl(y, 7), 0x9d2c5680))
        y = self._xor(y, self._and(self._shiftl(y, 15), 0xefc60000))
        y = self._xor(y, self._shiftr(y, 18))
        self.index += 1

        return y

    def getrandbits(self, bit):
        return self.get32bits()[:bit]


class Solver:
    def __init__(self):
        self.equations = []
        self.outputs = []

    def insert(self, equation, output):
        for eq, o in zip(self.equations, self.outputs):
            lsb = eq & -eq
            if equation & lsb:
                equation ^= eq
                output ^= o

        if equation == 0:
            return

        lsb = equation & -equation
        for i in range(len(self.equations)):
            if self.equations[i] & lsb:
                self.equations[i] ^= equation
                self.outputs[i] ^= output

        self.equations.append(equation)
        self.outputs.append(output)

    def solve(self):
        num = 0
        for i, eq in enumerate(self.equations):
            if self.outputs[i]:
                # Assume every free variable is 0
                num |= eq & -eq

        state = [(num >> (32 * i)) & 0xFFFFFFFF for i in range(624)]
        return state

def get_random_bytes(num):
    x = os.urandom(num)
    y = random.randbytes(num)
    # print(x.hex(), y.hex())
    return x + y


def inv(n, q):
    return egcd(n, q)[0] % q


def egcd(a, b):
    s0, s1, t0, t1 = 1, 0, 0, 1
    while b > 0:
        q, r = divmod(a, b)
        a, b = b, r
        s0, s1, t0, t1 = s1, s0 - q * s1, t1, t0 - q * t1
        pass
    return s0, t0, a


def sqrt(n, q):
    assert n < q
    for i in range(1, q):
        if i * i % q == n:
            return (i, q - i)
        pass
    raise Exception("not found")

################### ECC Implement ###################

Coord = collections.namedtuple("Coord", ["x", "y"])


class EC(object):
    """System of Elliptic Curve"""
    def __init__(self, a, b, q, n):
        """elliptic curve as: (y**2 = x**3 + a * x + b) mod q
        - a, b: params of curve formula
        - q: prime number
        """
        assert 0 < a and a < q and 0 < b and b < q and q > 2
        assert (4 * (a ** 3) + 27 * (b ** 2))  % q != 0
        self.a = a
        self.b = b
        self.q = q
        self.zero = Coord(0, 0)
        self.order = n
        pass

    def is_valid(self, p):
        if p == self.zero: return True
        l = (p.y ** 2) % self.q
        r = ((p.x ** 3) + self.a * p.x + self.b) % self.q
        return l == r

    def at(self, x):
        assert x < self.q
        ysq = (x ** 3 + self.a * x + self.b) % self.q
        y, my = sqrt(ysq, self.q)
        return Coord(x, y), Coord(x, my)

    def neg(self, p):
        return Coord(p.x, -p.y % self.q)

    def add(self, p1, p2):
        if p1 == self.zero: return p2
        if p2 == self.zero: return p1
        if p1.x == p2.x and (p1.y != p2.y or p1.y == 0):
            return self.zero
        if p1.x == p2.x:
            l = (3 * p1.x * p1.x + self.a) * inv(2 * p1.y, self.q) % self.q
            pass
        else:
            l = (p2.y - p1.y) * inv(p2.x - p1.x, self.q) % self.q
            pass
        x = (l * l - p1.x - p2.x) % self.q
        y = (l * (p1.x - x) - p1.y) % self.q
        return Coord(x, y)

    def mul(self, p, n):
        r = self.zero
        m2 = p
        while 0 < n:
            if n & 1 == 1:
                r = self.add(r, m2)
                pass
            n, m2 = n >> 1, self.add(m2, m2)
            pass
        return r

    # def order(self, g):
    #     assert self.is_valid(g) and g != self.zero
    #     for i in range(1, self.q + 1):
    #         if self.mul(g, i) == self.zero:
    #             return i
    #         pass
    #     raise Exception("Invalid order")
    # pass

class DSA(object):
    def __init__(self, ec : EC, g : Coord):
        self.ec = ec
        self.g = g
        self.n = ec.order
        pass

    def gen(self, priv):
        assert 0 < priv and priv < self.n
        return self.ec.mul(self.g, priv)

    def sign(self, hashval, priv, r):
        assert 0 < r and r < self.n
        m = self.ec.mul(self.g, r)
        return (m.x, inv(r, self.n) * (hashval + m.x * priv) % self.n)
 
    def validate(self, hashval, sig, pub):
        assert self.ec.is_valid(pub)
        assert self.ec.mul(pub, self.n) == self.ec.zero
        w = inv(sig[1], self.n)
        u1, u2 = hashval * w % self.n, sig[0] * w % self.n
        p = self.ec.add(self.ec.mul(self.g, u1), self.ec.mul(pub, u2))
        return p.x % self.n == sig[0]
    pass

######### redo this after done code
P = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
A = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
curve_order = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
G = Coord(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, \
          0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
ec_object = EC(A, B, P, curve_order)
dsa_object = DSA(ec_object, G)

Ln = 256

num = 1500
bit = 24

twister = Twister()
output = []


# io = process(['python3', 'server.py'])
io = remote("45.122.249.68", 20025)
# Register
io.sendlineafter(b">> ", b"2")
io.sendlineafter(b"username: ", b"admin")
io.recvuntil(b"Account information:\n")
user = []
cookies = []
user.append(io.recvline().strip())
io.recvuntil(b"Cookie: ")
cookies.append(io.recvline().strip())

# login
io.sendlineafter(b">> ", b"1")
io.sendlineafter(b"information: ", user[0])
io.sendlineafter(b"cookie: ", cookies[0])

# Gacha
outputs = []
for i in range(num):
    print(i)
    io.sendlineafter(b">> ", b"4")
    io.sendlineafter(b"number: ", b"1")
    io.recvuntil(b"Lucky number is: ")
    res = io.recvline().strip()
    res = int(res)
    res = res & 0xffffff
    res = res.to_bytes(3, "little")
    outputs.append(int.from_bytes(res, "big"))

# io.interactive()
# outputs = [int.from_bytes(random.randbytes(3)[::-1], "big") for _ in range(num)]
equations = [twister.getrandbits(bit) for _ in range(num)]

solver = Solver()
for i in range(num):
    print(i)
    io.sendlineafter(b">>", b"3")
    for j in range(bit):
        solver.insert(equations[i][j], (outputs[i] >> (bit - 1 - j)) & 1)

state = solver.solve()
recovered_state = (3, tuple(state + [0]), None)
random.setstate(recovered_state)

for i in range(num):
    assert outputs[i] == random.getrandbits(bit)

n = 50
context.log_level = 'debug'

for i in range(n):
    # register
    io.sendlineafter(b">> ", b"2")
    io.sendlineafter(b"username: ", b"admin")
    user_id = get_random_bytes(8)
    io.recvuntil(b"Account information:\n")
    user.append(io.recvline().strip())
    io.recvuntil(b"Cookie: ")
    cookies.append((io.recvline().strip(), random.randbytes((curve_order).bit_length() // 16).hex()))


B = 2 ** 128

M = Matrix(QQ, n + 3, n + 3)
M[0, 0] = B
M[1, 1] = B
M[2, 2] = B / curve_order

for i in range(n):
    hashval = bytes_to_long(sha256(user[i + 1]).digest()[:Ln])
    r, s = cookies[i + 1][0].decode().split(".")
    k = int(cookies[i + 1][1], 16)
    r = int(r, 16)
    s = int(s, 16)
    M[0, i + 3] = inverse(s, curve_order) * inverse(2 ** 128, curve_order) * hashval % curve_order
    M[1, i + 3] = inverse(2 ** 128, curve_order) * (-k % curve_order) % curve_order
    M[2, i + 3] = inverse(s, curve_order) * inverse(2 ** 128, curve_order) * r % curve_order
    M[i + 3, i + 3] = curve_order

def register_account(username : str, isAdmin : bool, privkey: int):
    tmp = {"username" : username, "isAdmin" : isAdmin}

    user_id = get_random_bytes(8)
    tmp["userID"] = user_id.hex()


    while True:
        random_k = int.from_bytes(get_random_bytes((curve_order).bit_length() // 16), "big")
        if random_k < curve_order:
            break
    
    tmp_hash = bytes_to_long(sha256(json.dumps(tmp).encode()).digest()[:Ln])
    r, s = dsa_object.sign(tmp_hash, privkey, random_k)

    cookie = long_to_bytes(r).hex() + "." + long_to_bytes(s).hex()
    return tmp, cookie

M = M.LLL()
for i in M:
    if i[0] == B and i[1] == B:
        print(i[-1] * 2 ** 128 % curve_order + int(cookies[-1][1], 16))
        k = i[-1] * 2 ** 128 % curve_order + int(cookies[-1][1], 16)
        hashval = bytes_to_long(sha256(user[-1]).digest()[:Ln])
        r, s = cookies[-1][0].decode().split(".")
        r = int(r, 16)
        s = int(s, 16)
        d = (k * s - hashval) * inverse(r, curve_order) % curve_order
        print(d)
        payload1, payload2 = register_account("admin", True, d)
        print(payload1)
        io.sendlineafter(b">> ", b"1")
        io.sendlineafter(b"information: ", json.dumps(payload1).encode())
        io.sendlineafter(b"cookie: ", payload2)
        io.sendlineafter(b">> ", b"3")
        io.interactive()
        

W1{it_1s_n3v3r_saf3_t0_us3_n0n_secure_cryptogr4phic_r4nd0mizat!0n}