[BambooFox CTF] oracle

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

rsa 문제이다.

c의 원하는 값을 넣어서 나오는 m(mod 3)을 알 수 있다. rsa의 준동형사상 성질을 이용하자.

c 대신 c*(1/3)^e를 넣는다면 (1/3)m이 나오는 것을 통해 m을 삼진수로 표현하였을 때 한 비트씩 알아낼 수 있다.

Exploit Code

from pwn import *
from Crypto.Util.number import *

p = remote('bamboofox.cs.nctu.edu.tw', 25001)
p.sendlineafter('> ', '1')
p.recvuntil('c = ')
c = int(p.recvline())
p.recvuntil('n = ')
n = int(p.recvline())

e = 65537

i = 0
b = 0
m = 0
while True:
    value = c * pow(inverse(3, n), i*e, n) % n
    p.sendlineafter('> ', '2')
    p.sendlineafter('c = ', str(value))
    p.recvuntil('m = ')
    a = (int(p.recvline()[:-1]) - b) % 3
    b = (b+a)*inverse(3,n) % n
    m = m+pow(3, i)*a
    print long_to_bytes(m)
    i += 1

Capture the Flag

---