# Techras

```
I'm having trouble determining when to discard a number versus when to reuse it in Techras. Any advice would be helpful!
```

Attachment:

```
#!/usr/bin/env python3

from Crypto.Util.number import *
from string import *
from flag import flag

def pad(flag):
    r = len(flag) % 8
    if r != 0:
        flag = flag[:-1] + (8 - r) * printable[:63][getRandomRange(0, 62)].encode() + flag[-1:]
    return flag

def genkey(nbit):
    p, q = [getPrime(nbit) for _ in ':)']
    n = p * q
    return n, (p, q)

def encrypt(msg, pubkey):
    msg = pad(msg)
    e = getPrime(32)
    m = bytes_to_long(msg)
    c = pow(m, e, pubkey)
    return str(c) + str(e)

nbit = 1024
pubkey, _ = genkey(nbit)

print(f'n = {pubkey}')
for _ in range(110):
    print(f'c = {encrypt(flag, pubkey)}')
```

The problem is, the randomness of `pad` is too low: only 63 possibilities. So two `pad` leads to the same `m`, which is encrypted using two `e`. It is prone to the attack describe in [https://crypto.stackexchange.com/questions/1614/rsa-cracking-the-same-message-is-sent-to-two-different-people-problem](<https://crypto.stackexchange.com/questions/1614/rsa-cracking-the-same-message-is-sent-to-two-different-people-problem>):

\\\[ c\_1 = m^{e\_1} \\bmod N \\\\ c\_2 = m^{e\_2} \\bmod N \\\\ e\_1a+e\_2b = 1 \\\\ m = c\_1^ac\_2^b \\bmod N \\\]

Steps:

1. Recover `c` and `e` from provided `output.txt`
2. Enumerate all pairs until we find the flag

```
from Cryptodome.Util.number import *

lines = open("output.txt", encoding="utf-8").readlines()
n = int(lines[0].split()[2])
c = [int(line.split()[2]) for line in lines[1:]]
print(n, len(c))

# find 32-bit prime suffixes
cs = []
es = []
for i in c:
    for j in range(1, 12):
        part = int(str(i)[-j:])
        if isPrime(part) and part.bit_length() == 32:
            cs.append(int(str(i)[:-j]))
            es.append(int(str(i)[-j:]))
print(cs, es)


# generated by google search
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return g, x, y


# find two c with the same padded message
for i in range(len(c)):
    for j in range(i):
        c1 = cs[i]
        e1 = es[i]
        c2 = cs[j]
        e2 = es[j]
        # if c1 = pow(m, e1, n), c2 = pow(m, e2, n)
        # find e1*a+e2*b = 1
        # m = pow(c1, a, n) * pow(c2, b, n) % n
        # https://crypto.stackexchange.com/questions/1614/rsa-cracking-the-same-message-is-sent-to-two-different-people-problem
        g, a, b = extended_gcd(e1, e2)
        if g == 1:
            m = pow(c1, a, n) * pow(c2, b, n) % n
            flag = long_to_bytes(m)
            if b"ASIS" in flag:
                print(flag)
```

Flag: `ASIS{d0nT___rEuS3___peXp!}`.