> For the complete documentation index, see [llms.txt](https://kos0ng.gitbook.io/ctfs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kos0ng.gitbook.io/ctfs/write-up/2023/lakectf-quals/cryptography.md).

# Cryptography

<table><thead><tr><th width="347">Challenge</th><th>Link</th></tr></thead><tbody><tr><td>KeySharer (50 pts)</td><td><a href="#keysharer-50-pts">Here</a></td></tr><tr><td>Random RSA (50 pts)</td><td><a href="#random-rsa-50-pts">Here</a></td></tr><tr><td>Vigenere-CBC (50 pts)</td><td><a href="#vigenere-cbc-50-pts">Here</a></td></tr><tr><td>Choices (460 pts)</td><td><a href="#choices-460-pts">Here</a></td></tr></tbody></table>

## KeySharer (50 pts)

### Description

### Solution

## Random RSA (50 pts)

### Description

RSA is really simple, there can't be any mistakes, right?

### Solution

Given code below

```python
#!/usr/bin/env -S python3 -u
import os
from Crypto.Util.number import isPrime, bytes_to_long
import random

def getPrime(n_bits, verbose=False):
    while True:
        a = random.getrandbits(n_bits)
        if isPrime(a):
            return a
        elif verbose:
            print(f"Sadly, {a} was not prime")

p = getPrime(1024, verbose=True)
q = getPrime(1024)

flag = os.getenv("flag","EPFL{fake_flag}").encode()
n = p * q
e = 65537
print(f"Ciphertext: {pow(bytes_to_long(flag), e, n)}")
```

getPrime function generate random number using random.getrandbits and if random number is prime it will be returned from the function. random.getrandbits is not secure random generator, we can predict next value if we have 624 \* 32 bits number generated by getrandbits. So in this case, because we know random number generated from getrandbits we can regenerate the p and q and decrypt the ciphertext. Since randcrack need 32 bits value so we submit each value received from the server in 32 bit format. Here is my solve script

```python
from pwn import *
from randcrack import RandCrack
import os
from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytes

def getPrime(n_bits):
    while True:
        a = rc.predict_randrange(0, (2**1024)-1)
        if isPrime(a):
            return a

def submit_crack(tmp):
	while tmp > 0:
		try:
			rc.submit(tmp % (1 << 32))
			tmp = tmp >> 32
		except Exception as e:
			break
		
r = remote("chall.polygl0ts.ch", 9022)
rc = RandCrack()

tmp = int(r.recvline().strip().decode().split("Sadly, ")[-1].split(" was not prime")[0])
while tmp > 0:
	if(tmp.bit_length() <= 512):
		rc.submit(tmp % (1 << 32))
	tmp = tmp >> 32

for i in range(19):
	tmp = int(r.recvline().strip().decode().split("Sadly, ")[-1].split(" was not prime")[0])
	submit_crack(tmp)

tmp = r.recvline().strip().decode()
while "Ciphertext: " not in tmp:
	tmp = r.recvline().strip().decode()

ct = int(tmp.split(" ")[-1])
p = getPrime(1024)
q = getPrime(1024)
e = 65537
n = p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)

print(long_to_bytes(pow(ct, d, n)))
```

<figure><img src="/files/GwUzRzcZgCLdVHVV9Eqp" alt=""><figcaption></figcaption></figure>

Flag : EPFL{w0w\_s0\_much\_r4nd000o0oo0om}

## Vigenere-CBC (50 pts)

### Description

### Solution

## Choices (460 pts)

### Description

### Solution