[RedpwnCTF] Binary (RSA LSB Oracle Attack)

010000100110100101101110011000010111001001111001 Binary Written by: Tux 0100100100100000011001100110111101110101011011100110010000100000011101000110100001101001011100110010000001110111011001010110100101110010011001000010000001110011011001010111001001110110011010010110001101100101001011100010111000101110 I found this weird service... nc chall2.2019.redpwn.net 5001 Hint: 010010010111001100100000011010010111010000100000011001010111011001100101011011100010000001101111011100100010000001101111011001000110010000111111 Is it even or odd?

아는 분이 RSA 문제 소개시켜주어서... 잠깐 풀어보았는데

롸업은 나중에 쓰고 일단 익스코드 나중에 쓰일거같아서 저장하려고 ㅎㅎ...

설명은 나중에 올려야지

RSA LSB Oracle Attack 기법을 사용해서 풀 수 있다.

import decimal
from pwn import *
from Crypto.Util.number import long_to_bytes
 
conn = remote("chall2.2019.redpwn.net", 5001)
 
def decode_binary(ut):
    msg = conn.recvuntil(ut)[:-1]
    msg = int(msg,2)
    msg = long_to_bytes(msg)
    result = conn.recvline()
    return msg, result
 
print(decode_binary("\n")[0])
print(decode_binary("\n")[0])
 
msg, result = decode_binary(":")
N, e = result.strip()[1:-1].split(",")
N=int(N,2)
e=int(e,2)
 
print(msg + " : " + str(N) + ", " + str(e))
 
conn.recvline()
 
msg, result = decode_binary(":")
enc = int(result,2)
print(msg + " : " + str(enc))
 
 
k = N.bit_length()
decimal.getcontext().prec = k
lower = decimal.Decimal(0)
upper = decimal.Decimal(N)
 
 
p2 = pow(2, e, N)
lower = decimal.Decimal(0)
upper = decimal.Decimal(N)
p = p2
 
for i in xrange(k):
    mid = (lower + upper) / 2
    conn.readuntil('> ')
    conn.sendline(bin(enc * p % N)[2:])
    cur = int(conn.readline().strip())
    if cur == 0:
        upper = mid
    else:
        lower = mid
    p = p * p2 % N
    print(int(upper))
print long_to_bytes(int(upper))
conn.interactive()