babyRSA GWCTF 2019

Involved Knowledge

• RSA
• Adjacent Element

Description

encrypt.py

import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '/n')
output.write('m1=' + str(m1) + '/n')
output.write('m2=' + str(m2) + '/n')
output.close()

secret

N = 6365851495945747469090301601826908662229092…

m1 = 900099743414522432169869380283712…

m2 = 487443985757405173426628188375657117604235507…

Analyze

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

这里将flag分为了长度相等的两半，每段长度为19

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

通过这部分我们可以得到p和q相邻，因为q是p的下一个质数

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

将两部分flag转成数值

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

c1为F1与F2的和

c2为F1与F2的立方和

并且保证c2<N

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

/(c1^e ≡ m1 (mod N)/)

/(c2^e ≡ m2 (mod N)/)

也就是我们得到的m1与m2

以上就是题目加密的一个思路，涵盖的知识点是RSA，且p与q相邻

我们逆着题目加密的过程进行解密

• 首先通过m1 , m2得到c1 , c2

/(m1^d ≡ c1 (mod N)/)

/(m2^d ≡ c2(mod N)/)

即pow(m1 , d , N) pow(m2 , d , N)

接着我们可以通过z3来对F1F2进行求解

/(F1 + F2 = c1/)

/(F_1^3 + F_2^3 = c2/)

得到F1F2后，就相当于得到flag的两部分了

GWHT{f709e0e2cfe7e530ca8972959a1033b2}