BambooFox 2019 | Oracle

#RSA #LSBLeakAttack

#!/usr/bin/env python3
from Crypto.Util.number import *

with open("flag", "rb") as f:
    flag = int.from_bytes(f.read(), "big")


def genkeys():
    e = 65537
    while True:
        p, q = getPrime(512), getPrime(512)
        n, phi = p * q, (p - 1) * (q - 1)
        if GCD(e, phi) == 1:
            d = inverse(e, phi)
            return n, e, d


def menu():
    print("1) Info")
    print("2) Decrypt")
    print("3) Exit")


def main():
    n, e, d = genkeys()

    while True:
        menu()
        option = input("> ")
        if option == "1":
            c = pow(flag, e, n)
            print(f"c = {c}")
            print(f"n = {n}")
        elif option == "2":
            c = int(input("c = "))
            m = pow(c, d, n)
            print(f"m = {m % 3}")
        else:
            return

main()

誰が見ても LSBLeakAttack。ただしmod3。mod 3のときも同様にやりたいので考える。考えるとに対しては、ならばになっているはず、と気がつく。気がつくのでこれでoracleがわかるし解ける。

from ptrlib import *
from Crypto.Util.number import long_to_bytes

e = 65537

sock = Socket("34.82.101.212", 20001)

sock.recvuntil("> ")
sock.sendline("1")
sock.recvuntil("c = ")
c = int(sock.recvline().strip())
sock.recvuntil("n = ")
n = int(sock.recvline().strip())

sock.recvuntil("> ")
sock.sendline(b"2")
sock.recvuntil("c = ")
sock.sendline(str(c).encode())
sock.recvuntil("m = ")
last = int(sock.recvline().strip())


def oracle(c):
    global last
    sock.recvuntil("> ")
    sock.sendline(b"2")
    sock.recvuntil("c = ")
    sock.sendline(str(c).encode())
    sock.recvuntil("m = ")
    m = int(sock.recvline().strip())
    if m != (last * 2) % 3:
        ret = 1
    else:
        ret = 0
    last = m
    return ret


m = lsb_leak_attack(oracle, n, e, c)
print(long_to_bytes(m))