wk13 - crypto

Theme: RSA attack, pseudo-random number generation: LSFR

RSA 1 (100)

Solve

This is a small-exponent RSA attack, as the public-key exponent e = 5, which is really small. The encryption formula in RSA is c = m^e mod n. When e is really small, m^e is also small. When m^e is smaller than n, then m^e mod n simply reduces to m^e. The equation simplifies to c = m^e, which means m can be calculated by taking the e-th root of c.

Since c is so large, we need to rely on Python's gmpy2 to calculate the 5th root of c. After getting m, we cast it into an integer. This integer, when viewed in hex, represents the original message's string, character by character. The most-significant byte represents the ASCII value of the first character in the string. We will rely on Python's libnum to handle the conversion because m is too big.

Script

import gmpy2
from libnum import *
n = 533605186777306193639508819403689854723168800416077570877556814561974510650703933663552187967375851050646208128209568481683355229899167319112490973880299837120480018922986799636227477834771362913279292487850421999350777708001020329795709138334610780730597034260153640234480722366154979291024335986198570593451145386096041441694142303029951422457927053482922346932059407588856162775465207822285341789134878903971960839160948713769933790271069617086233644676520577331376568114692462625908315402532488462606571660357054531551286020401012508969452459284862627743043345321322925499920088688010914314443609388063914697750619842677930595246081958644122784948962984865394846362143230320583771665384591443721852392466330803543470550877599287392221654219595175889497614399302890343580420367364874038398080995808471132855542861664243296681960132955542020152839237160011164613078369333074195496802962856580473719775240389129028230147531833572933406563330750479771719014642826021391325452781708286449850887680856359748290195973831842764130014972291220789121217726533156605699949176771067317787613639174247701763343887308493679345260109576954599452655522660349242730700233496465587203398595170125932170987424508237647032302254684786567416411326169
c = 732466032403203463374878220140059105091651520977480015886219080123117189578708190919121654951682498149506672860608479885524740049575872017474671777421674377373429605767981432727119392556710499513482246717540914707181450967175025879049618458016661818671901159528808525779690169558386717353946747527285065825894006369625446593132198572253701519060895642563024420339887430552270587095668123446780708158342136739722982418780290340903335556259510360452596819062050805330143163954781773797707204334359165792123048164936391973508948725609734174349
e = 5
# m = c ^ (1/e) assuming m^e < n (here it is the case; e is very small (=5))

secret_msg, is_exact = gmpy2.iroot(c, e)
print(f"The {e}-th root is: {secret_msg}")
print(f"Is the root exact? {'Yes' if is_exact else 'No'}")
print("Flag: ", n2s(int(secret_msg))) # convert number to packed string
# Output: Flag:  b'flag{n0_f4ct0r1ng_r3qu1r3d!_9cd6a1b5e826ceb9}'

Flag

flag{n0_f4ct0r1ng_r3qu1r3d!_9cd6a1b5e826ceb9}

Linear (200)

Theme: LSFR

Given

• lsfr.py source code to encrypt the flag

• Galois field of emojis

• encrypted flag

Initial Observations

• LSFR is seeded with a random number

• Randomly generated bits are used to generate Galois emoji field

• Then proceed to further generate random bits used as keys to encrypt the flag

Solve

The goal is to first solve for the seed. With the seed, we can then generate all random bits in order, and use them to decrypt the flag.

Let's trace the Python code to understand what happens. A random number (entropy from server's system). Within the function for Galois field, we see that it's printed row by row. For every emoji, it first generates a random bit to determine whether to source emoji from animal or field array. Then, it generates 3 more random bits to form an integer used to index into the emoji array. This means for a single emoji, a total of 4 random bits are used. From LSFR's algorithm, for a N-bit seed, the first N "random" bits generated are just the seed, in reverse.

Looking at LSFR's constructor, we see that the seed has 32 bits. Since the seed is 32 bits, and each emoji uses 4 random bits, the first 8 emojis reveal the seed bits in reverse. We'll work those out: ![[Captura de pantalla 2024-12-16 a las 22.25.50.png]] Organise these bits into an array: [0,1,0,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1] If we read these bits backwards as a single number, that is our seed!

We'll write a Python script to process the seed, print out the Galois field again (both to verify that our seed is correct and to use up those first 400 bits), XOR each byte in the encrypted flag with the randomly generated bytes from LFSR and get the flag:

# include funcs and class from original lfsr.py code (snipped)

# calculate seed
seed_reverse = [0,1,0,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1]
seed_reverse = seed_reverse[:-8]
print(f"Length of seed in bits: {len(seed_reverse)}")
seed_correct_order = seed_reverse[::-1]
seed = 0
for bit in seed_correct_order:
seed = seed << 1 | bit
print(f"Seed: {seed}")

# verify that seed is correct by printing a Galois field and cmp with actual Galois
rng = LFSR(seed)
# rng.get_int(400) <-- can do this instead of draw_field(rng)
print("Here's a happy little Galois field:")
draw_field(rng)
# Verified!

# prepare encrypted bytes
encrypted_str = "a70ad66da9ffea23c57b36a3700130aa5821ba213ff2ef42054ce3c89c958fbef10aa413118cd0a8d5951100806960d329"
encrypted_bytes = [int(encrypted_str[i:i+2], 16) for i in range(0, len(encrypted_str), 2)]
# print(encrypted_bytes)

# now use the random bits for real as keys
# decrypt byte
decrypted_bytes = [byte ^ rng.get_byte() for byte in encrypted_bytes]
decrypted_bytes = [chr(byte) for byte in decrypted_bytes]
flag = "".join(decrypted_bytes)
print(flag)

Flag

flag{v3ry_ps3ud0_not_so_r4nd0m!_3f7a64d057eaca24}