Involved Knowledge
- RSA
- Adjacent Element
Description
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}