SuSeC CTF | Blue Shop

問題のソースコードは提供されていない

• 接続する度に N = pq を生成する

• がもらえる

• 好きな回数だけ RabinCryptosystem の復号ができる

コードの一部だけもらえる

import gmpy

# Rabin Crypt
def gen_modulus(nbit):
    while True:
        p, q = getPrime(nbit), getPrime(nbit)
        if (p % 4) * (q % 4) == 9:
            n = p * q
            return n

# Rabin Encryption
def blue_shop(r, n):
    assert gmpy.gcd(r, n) == 1
    return pow(r, 2, n)


# RSA Encryption (?)
def encrypt(m, n):
    m = bytes_to_long(m)
    return pow(m, 0x10001, n)

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

# p = 11553046883467845118400143030661629735110573266821438299904023918065786121464573761771932209733272865928633200215275308104230716404138397306709790504824379
# n = 116739186388840587483368825147809754748757035098012577043638879022960264657944943977786757563378525459238652595371068453947915684686699403715167655027827323697827650548386646627401118691801723128804956620842758976964235568375525295135304221675680678967991592055975382427901529787835019567536883719123188143297
# assert n % p == 0
# q = n // p
# e = 65537
# phi = (p-1)*(q-1)
# d = inverse(e, phi)
# 
# c = 101192663964297569655774624679193235076105231674494641541927180319930006349621107704941122239087264335025964012572341203191655743630556688758107166603754766037376499747909526664189106665021622814648143616475761524075640966717326586983612923912424471426222105053269779629600884302408905126556224941360525688597
# m = pow(c,d,n)
# print(long_to_bytes(m))

def blue_shop(r, n):
    assert GCD(r, n) == 1
    return pow(r, 2, n)

sock = Socket("66.172.27.57", 1337)
sock.sendline("P")
sock.recvuntil("n = ")
n = int(sock.recvline().decode())
sock.sendline("F")
sock.recvuntil("n) = ")
c = int(sock.recvline().decode())
e = 65537

while True:
    while True:
        x = getRandomRange(0, n)
        if x * x >= n:
            break
    sock.sendline("G")
    sock.recvuntil(":")
    sock.sendline(str(blue_shop(x,n)))
    sock.recvuntil("shop(")
    r1 = int(sock.recvuntil(",").decode()[:-1])
    if r1 != x:
        if r1 > x:
            x,r1 = r1,x
        p = GCD(x - r1, n)
        if p != 1 and p != n:
            break
q = n // p
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c,d,n)
print(long_to_bytes(m))