Rating:
# Pragyan CTF 2019 "Help Rabin" writeup
This problem is solved by Laika and hi120ki.
## check problem
```
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.
```
and I get 3 files.
ciphertext.txt - encrypted data
publickey.pem - a publickey encoded as PEM
encrypt.py - main encryption code
## read publickey.pem
First, I check publickey.
I can get e and n value.
> まずは publickey.pem から e と n を取り出します。
```python
from Crypto.PublicKey import RSA
pubkey = RSA.importKey(open("publickey.pem").read())
e = pubkey.e
n = pubkey.n
print(e) # e = 1
print(n) # n = 68367741643352408657735068643514841659753216083862769094847066695306696933618090026602354837201210914348646470450259642887798188510482019698636160200778870456236361521880907328722252080005877088416283896813311117096542977573101128888124000494645965045855288082328139311932783360168599377647677632122110245577
```
## read encrypt.py
```python
from Crypto.Util.number import *
import random
# get next prime number
def nextPrime(prim):
if isPrime(prim):
return prim
else:
return nextPrime(prim+1)
p = getPrime(512)
q = nextPrime(p+1)
# p and q is generated as 3 (mod 4)
while p%4 != 3 or q%4 !=3:
# p is a random prime number
p = getPrime(512)
# q is generated by nextPrime function
q = nextPrime(p+1)
n = p*q
m = open('secret.txt').read()
# convert flag to long
m = bytes_to_long(m)
# e = 1
m = m**e
c = (m*m)%n
# convert encrypted data to bytes
c = long_to_bytes(c)
c = c.encode('hex')
# write encrypted data to text file
cipherfile = open('ciphertext.txt','w')
cipherfile.write(c)
```
q is generated by nextPrime function.
This means that p and q are similar values.
It is easy to get p and q value from n.
> q は nextPrime 関数から生成されています。
>
> nextPrime 関数は p をインクリメントしていき p の次に大きい素数を計算します。
>
> p と q の値が近いため、n のルート付近を総当たりで p と q を求めることができます。
## get value of p and q
First, I calculate approximation value from n^(1/2).
> まず n のルートの近似値を求めます。
```python
n = 68367741643352408657735068643514841659753216083862769094847066695306696933618090026602354837201210914348646470450259642887798188510482019698636160200778870456236361521880907328722252080005877088416283896813311117096542977573101128888124000494645965045855288082328139311932783360168599377647677632122110245577
appr = 8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
digit = 152
while digit > -1:
for i in range(11):
if ((appr + i * 10 ** digit)**2 - n) > 0:
appr = appr + (i-1) * 10 **digit
digit = digit - 1
print(appr)
break
# appr = 8268478798627496550868057067863302848395658194493470189583465530982345058367642548587735876643165276333944105562045538477589025350029252013031979923054810
```
Then, I try brute force attack to get p.
> そして p を総当たりで求めます。
```python
n= 68367741643352408657735068643514841659753216083862769094847066695306696933618090026602354837201210914348646470450259642887798188510482019698636160200778870456236361521880907328722252080005877088416283896813311117096542977573101128888124000494645965045855288082328139311932783360168599377647677632122110245577
appr = 8268478798627496550868057067863302848395658194493470189583465530982345058367642548587735876643165276333944105562045538477589025350029252013031979923054810
for i in range(1000):
if n % (appr + i) == 0:
print(appr + i)
# p = 8268478798627496550868057067863302848395658194493470189583465530982345058367642548587735876643165276333944105562045538477589025350029252013031979923054823
```
## decrypt
reverse ciphertext.txt
```python
from Crypto.Util.number import *
cipher = open('ciphertext.txt').read()
decoded = cipher.decode('hex')
c = bytes_to_long(decoded)
print(c)
# c = 55794223709813934192265135096073563545914401645083132264094031861211381439924290498765378643984142482022780941488967640941896234878298378029331869035026299883890239650523385184000895121634725249518610468891121286187697095281449541110528807147056849808508384046722319812216434329882704675650502328191347845959
```
Let's decrypt using this formula by secret key p and q.
<https://en.wikipedia.org/wiki/Rabin_cryptosystem#Computing_square_roots>
> 秘密鍵の p と q を使い復号します。
>
> 上記の wikipedia に掲載されている式から復号します。
```python
# this code is written by Laika
def ext_gcd(a: int, b: int):
c0, c1 = a, b
a0, a1 = 1, 0
b0, b1 = 0, 1
while c1 != 0:
q, m = divmod(c0, c1)
c0, c1 = c1, m
a0, a1 = a1, (a0 - q * a1)
b0, b1 = b1, (b0 - q * b1)
return a0, b0, c0
n = 68367741643352408657735068643514841659753216083862769094847066695306696933618090026602354837201210914348646470450259642887798188510482019698636160200778870456236361521880907328722252080005877088416283896813311117096542977573101128888124000494645965045855288082328139311932783360168599377647677632122110245577
p = 8268478798627496550868057067863302848395658194493470189583465530982345058367642548587735876643165276333944105562045538477589025350029252013031979923054823
q = n // p
c = 55794223709813934192265135096073563545914401645083132264094031861211381439924290498765378643984142482022780941488967640941896234878298378029331869035026299883890239650523385184000895121634725249518610468891121286187697095281449541110528807147056849808508384046722319812216434329882704675650502328191347845959
pe, qe = (p + 1) // 4, (q + 1) // 4
mp, mq = pow(c, pe, p), pow(c, qe, q)
yp, yq, _ = ext_gcd(p, q)
r1 = (yp * p * mq + yq * q * mp) % n
r2 = n - r1
s1 = (yp * p * mq - yq * q * mp) % n
s2 = n - s1
r1 = hex(r1) # :(
r2 = hex(r2) # :)
s1 = hex(s1) # :(
s2 = hex(s2) # :(
flag = ""
for a, b in zip(r2[2::2], r2[3::2]):
flag += chr(int(a + b, 16))
print(flag)
```
```
Hey Rabin, would you like to be the front end to my back end? Here is your flag: pctf{R4b1n_1s_th3_cut3st}
```
I get flag.
