srdnlen CTF 2022 | fancy e

#srdnlen_CTF_2022

#!/usr/bin/env python3

import os
import random
import string

from Crypto.Util.number import getPrime, bytes_to_long


def flag_padding(flag):
    s = string.ascii_lowercase + string.ascii_uppercase + string.digits
    for i in range(random.randint(5, 10)):
        flag = random.choice(s) + flag + random.choice(s)
    return flag


def fancy_e(b, x, y):
    rand1 = random.randint(1, 5)
    rand2 = random.randint(1, 5)
    rand3 = random.randint(1, 5)

    op1 = random.choice([-1, 1])
    op2 = random.choice([-1, 1])
    op3 = random.choice([-1, 1])

    e = b + (op1 * rand1)
    f = x * y + op2 * rand2 * y + op3 * rand3 * x + 1
    k = rand1 + rand2 + rand3

    new_e = (e * f * k + 1) | 1

    assert pow(new_e, -1, (x - 1) * (y - 1))

    return new_e


flag = os.environ.get("FLAG", "srdnlen{template}")
flag = flag_padding(flag)
base = int(open('base.txt', 'r').read())
assert 300 < base < 10000

disclaimer = "Tired of using e = 65537? Would you prefer a more stylish and original e to encrypt your message?\n" \
             "Try my new software then! It is free, secure and sooooo cool\n" \
             "Everybody will envy your fancy e\n" \
             "You can have a look to up to 1000 flags encrypted with my beautiful e and " \
             "choose the one you like the most\n" \
             "How many do you want to see?"

print(disclaimer)
number = int(input("> "))
if number < 1 or number > 1000:
    print("I said up to 1000! Pay for more")
    exit(1)
print()

i = 0
while i < number:
    p = getPrime(256)
    q = getPrime(256)
    n = p * q
    try:
        e = fancy_e(base, p, q)
        ct = pow(bytes_to_long(flag.encode()), e, n)
        print("Ciphertext"+str(i)+"= " + str(ct))
        print("e"+str(i)+"=          " + str(e))
        print("Modulus"+str(i)+"=    " + str(n))
        print()
        i += 1

    except:
        continue

exit(0)

RSAだが、の計算方法が特殊でかつ、1000回までクエリできる。

はと小さい乱数で決まる。だいたい（は乱数）と近似できることに着目して性質を見ると、何回もクエリして出てきた最小のを3で割ったあたりの値がに近いことに気がついた。

あとは乱数を全探索するとの計算式にが使われているので二次方程式が立って解ける

import random
from Crypto.Util.number import getPrime
from itertools import product
from tqdm import tqdm
from sympy.solvers import solve
from sympy import symbols
from ptrlib import Socket

sock = Socket("nc fancye.challs.srdnlen.it 15007")
# sock = Socket("nc localhost 9999")
sock.sendlineafter("> ", "400")

bs = []
for i in tqdm(range(400)):
    c = int(sock.recvlineafter("Ciphertext"+str(i)+"= "))
    e = int(sock.recvlineafter("e"+str(i)+"=          "))
    n = int(sock.recvlineafter("Modulus"+str(i)+"=    "))

    if i == 0:
        print(n)
        print(e)
        print(c)
        N = n
        f_e = e
        ct = c
    bs.append(e // n)

sock.close()

bs = list(sorted(bs))
b_guess = bs[0] // 3

x, y = symbols("x, y", integer=True)


xs = list(product([1, 2, 3, 4, 5], repeat=3))
for (r1, r2, r3) in tqdm(xs):
    for b in [b_guess + diff for diff in range(-5, 5)]:
        for (o1, o2, o3) in product([-1, 1], repeat=3):
            e = b + (o1 * r1)
            f = N + o2 * r2 * y + o3 * r3 * x + 1
            k = r1 + r2 + r3

            e1 = e * f * k + 1
            e2 = e * f * k + 2

            s = solve([e1 - f_e, N - x*y]) or solve([e2 - f_e, N - x*y])


            if s:
                p, q = abs(int(s[0][x])), abs(int(s[0][y]))
                assert p*q == N
                d = pow(f_e, -1, (p-1)*(q-1))
                m = pow(ct, d, N)
                print(N, f_e, ct, p, q, m)