srdnlen CTF 2022 | Easy RSA

#srdnlen_CTF_2022

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long


def padding(text, n):
    for j in range(n % 2**8):
        text += b"poba"
    return bytes_to_long(text)


if __name__ == '__main__':
    f = open('flag.txt', 'r').read().encode()
    e = 13

    print("Can u break the best encryption tool of the world?")
    print()

    nums = []

    for i in range(15):
        x, y = getPrime(16), getPrime(16)
        print(f"x*y:{x * y}")
        k = int(input("Give me a number:"))
        if k < 2 ** 128 or k in nums or k % (x * y) == 0:
            print("Are u serious?")
            exit(1)
        r = int(input("Give me another number:"))
        if r < 2 ** 128 or r in nums:
            print("Are u serious?")
            exit(1)
        nums += [k, r]
        print()
        N = getPrime(512) * getPrime(512)
        CT = pow(padding(f, pow(k, r, x * y)), e, N)
        print(f"e:{e}")
        print(f"N:{N}")
        print(f"CT:{CT}")
        print()

RSAによる暗号化を15回までやってくれる。つなぎ直せば何回でもできるので15回に限定する必要はまったくないが…

クエリごとに、謎の式 の値によって平文のパディングの長さが決まる。は選ばせてくれるので、すべてのクエリでパディングの長さが同じになるようにを適当に探索するとすべてのクエリで同じ平文を暗号化することになるから、Hastad Broadcast Attackをやれば良い

from ptrlib import Socket, crt, hastads_broadcast_attack
from random import randrange


sock = Socket("nc easyrsa.challs.srdnlen.it 15005")


xy = int(sock.recvlineafter("x*y:"))
k = randrange(2, 2**256)
while True:
    r = randrange(2, 2**256)
    padsize = pow(k, r, xy) % 2**8
    if padsize * 32 < 200:
        break

sock.sendlineafter("Give me a number:", str(k))
sock.sendlineafter("Give me another number:", str(r))

N = int(sock.recvlineafter("N:"))
c = int(sock.recvlineafter("CT:"))

pairs = [(c, N)]

for _ in range(14):
    xy = int(sock.recvlineafter("x*y:"))
    k = randrange(2, 2**256)
    while True:
        r = randrange(2, 2**256)
        size = pow(k, r, xy) % 2**8
        if size == padsize:
            break

    sock.sendlineafter("Give me a number:", str(k))
    sock.sendlineafter("Give me another number:", str(r))

    N = int(sock.recvlineafter("N:"))
    c = int(sock.recvlineafter("CT:"))

    pairs.append((c, N))
m = hastads_broadcast_attack(13, pairs)
print(bytes.fromhex(hex(m)[2:]))