PragyanCTF 2019|Help Rabin - crypto-writeup-public

Rabin has received a text from someone special, but it's all in ciphertext and he is unable to make head or tail of it. He requested her for a little hint, and she sent him the encryption algorithm. He's still unable to decode the text. Not wanting to look dumb to her again, he needs your help in figuring out what she's written for him. So help him out.

ciphertext.txt, publickey.pem, encrypt.py が渡される。

from Crypto.Util.number import *
import random

def nextPrime(prim):
    if isPrime(prim):
        return prim
    else:
        return nextPrime(prim+1)

p = getPrime(512)
q = nextPrime(p+1)
while p%4 != 3 or q%4 !=3:
    p = getPrime(512)
    q = nextPrime(p+1)

n = p*q
m = open('secret.txt').read()
m = bytes_to_long(m)

m = m**e
c = (m*m)%n
c = long_to_bytes(c)
c = c.encode('hex')

cipherfile = open('ciphertext.txt','w')
cipherfile.write(c)

eが定義されてないんですが……。

Modulus:
    61:5b:e0:98:72:7a:e6:10:de:9c:10:48:19:f3:a1:
    f7:cc:5b:31:44:81:0b:38:d4:f4:d5:1b:be:11:d9:
    ca:20:f2:87:ee:d0:23:6b:ce:d1:fe:44:3a:33:5a:
    2f:33:c7:a8:ac:68:f0:9f:c5:f3:8b:fe:37:4a:92:
    07:d3:07:3d:40:2c:7a:65:a3:0b:60:f7:5b:10:e4:
    3a:29:67:30:aa:22:d3:25:27:f7:20:3e:c9:be:cc:
    6a:7a:0d:d7:0a:5c:e3:d1:d5:f2:a8:db:98:68:e8:
    a4:53:4e:ef:70:5f:2c:6a:83:26:c8:8a:53:6b:82:
    7c:88:bc:00:05:22:7a:c9
Exponent: 1 (0x1)

n = 615be098727ae610de9c104819f3a1f7cc5b3144810b38d4f4d51bbe11d9ca20f287eed0236bced1fe443a335a2f33c7a8ac68f09fc5f38bfe374a9207d3073d402c7a65a30b60f75b10e43a296730aa22d32527f7203ec9becc6a7a0dd70a5ce3d1d5f2a8db9868e8a4534eef705f2c6a8326c88a536b827c88bc0005227ac9

eは1らしい。わけわからんな。そのかわりに c = (m*m) % n があるってことだろうか。実質e=2なのでlow public exponent attackをやったけどだめだった。

というかこれはRSAじゃなくてRabin暗号っていうらしい。mをe乗してるのは謎だけどm *m としてるのは m(m + B) で B = 0ということか

まあpとqの値が近いのでNをfermat法で素因数分解すればp, qが求まるのであとはRabin暗号のソルバを見つけてくるだけ。

 from Crypto.Util.number import long_to_bytes
 
 
 def isqrt(n):
     x = n
     y = (x + n // x) // 2
     while y < x:
         x = y
         y = (x + n // x) // 2
     return x
 
 
 def fermat(n):
     x = isqrt(n) + 1
     y = isqrt(x * x - n)
 
     while True:
         w = x * x - n - y * y
         if w == 0:
             break
         elif w > 0:
             y += 1
         else:
             x += 1
     return x + y, x - y
 
 
 def egcd(a, b):
     if a == 0:
         return b, 0, 1
     else:
         gcd, y, x = egcd(b % a, a)
         return gcd, x - (b // a) * y, y
 
 
 n = 0x615BE098727AE610DE9C104819F3A1F7CC5B3144810B38D4F4D51BBE11D9CA20F287EED0236BCED1FE443A335A2F33C7A8AC68F09FC5F38BFE374A9207D3073D402C7A65A30B60F75B10E43A296730AA22D32527F7203EC9BECC6A7A0DD70A5CE3D1D5F2A8DB9868E8A4534EEF705F2C6A8326C88A536B827C88BC0005227AC9
 c = 0x4F741FE93DD7E383FF527CAA9A2F27D27FD74B53B62123837B74A2B024D0FBBE052F3B330CE5208BA989FC68E2F5235AC4E9DD9E091E7CB80C02745D9B2AAD10CAB9431590AE63117CE539EBF747B4BC81F2A293AEA52F0B1FEE746158DC45D0C8D60769A8A8E671FB049B52669A010A1CA6F5DE851D715BF1821D8771BBEB47
 p, q = fermat(n)
 
 r = pow(c, (p + 1) // 4, p)
 s = pow(c, (q + 1) // 4, q)
 
 gcd, c, d = egcd(p, q)
 x = (r * d * q + s * c * p) % n
 y = (r * d * q - s * c * p) % n
 plains = [x, n - x, y, n - y]
 
 for plain in plains:
     flag = long_to_bytes(plain)
     print(flag)