这题主要考察的是RSA
题目代码如下：
#!/usr/bin/env python2
from gmpy2 import next_prime, powmod
from random import randint, getrandbits
from hashlib import sha512, sha256
from os import urandom
introduction = """
.--. .-------------------------------.
| _| | |
| O O < Hey man, wanna mid some bit ? |
| | | | |
|| | / `-------------------------------'
|`-'|
`---'
Whoever says live is simple, is the one never actually live. :))
"""
def pad(num, length):
result = bin(num).lstrip('0b').strip('L')
result = result + '0' * (length - len(result))
return int(result, 2)
def xor(a, b):
return ''.join(chr(ord(i) ^ ord(j)) for i, j in zip(a, b))
def gen_key():
t1 = randint(768, 928)
t2 = 1024 - t1
if t1 > t2:
t1, t2 = t2, t1
assert t1 < t2
p2 = pad(getrandbits(1024 - t2) << t2, 1024)
p0 = pad(getrandbits(t1), t1)
q2 = pad(getrandbits(1024 - t2) << t2, 1024)
q0 = pad(getrandbits(t1), t1)
r = pad(getrandbits(t2 - t1) << t1, t2)
p = next_prime((p2 ^ r ^ p0))
q = next_prime((q2 ^ r ^ q0))
N = p * q
return N, t2 - t1, p0 - q0,p,q,
def proof_of_shit():
"""
This function has very special purpose
:)) Simply to screw you up
"""
raw = urandom(6)
print 'prefix = {}'.format(raw.encode('hex'))
challenge = raw_input('Challenge: ')
temp = sha256(raw + challenge).hexdigest()
if temp.startswith('25455'):
return True
else:
return False
if __name__ == "__main__":
try:
assert proof_of_shit() == True
N, delta, gamma = gen_key()
m = FLAG
c = powmod(m, 0x10001, N)
print introduction
print 'N = {}'.format(N)
print 'delta = {}'.format(delta)
print 'gamma = {}'.format(gamma)
print 'ciphertext = {}'.format(c)
except AssertionError:
print "Take your time and think of the inputs."
可以看到服务端会除了返回N和密文之外，还会返回delta和gamma两个非常奇怪的值
所以具体看他的p、q的生成算法
p = next_prime((p2 ^ r ^ p0))
q = next_prime((q2 ^ r ^ q0))
根据next_prime的性质，一般而言得到的p和next_prime的输入p2 ^ r ^ p0之间相差不超过10000,
由此可知结论1
| (p0-q0)-(p-q)&(2t1-1) | <10000
此外根据p2、q2和r的生成算法，有结论2
p和q的中间 1024-2×t1 位是相同的，较高的t1位不同，较低的t1位也不同
根据coppersmit 攻击，有结论3
如果我们能得到质因数p的足够数量的低比特位，可以对n=p×q进行分解
而由代码知t2=1024-t1 属于区间[768, 928]，满足结论3的攻击条件
因此我们只要能够根据结论1，结论2和给出的n，gamma，推导出p的低t2比特位，即可进行coppersmith攻击。
假设p的低t2比特位为x，gamma 和真实p，q低t1位的差为i,根据n，gamma计算x的方程如下：
g=gamma+i
r1=solve_mod([x * (x+g)==n0],2t1)
r2=solve_mod([x * (x+g)==n&(2t2-1)],2t2)
因此我们可以在一个合理的范围爆破i来求出x
需要说明的是，通过这种方法会求出多个满足等式的x
还需要把x代入coppersmith中，看是不是真的存在满足条件的p
具体sage脚本如下：
def partial_p(p0, kbits,pbits, n,offset=0):
#print "lower %d bits (of %d bits) is given" % (kbits, pbits)
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)
def compute(i):
g=gamma+i
var('xx')
n0=n&(2^t1-1)
r1=solve_mod([xx*(xx+g)==n0],2^t1)
r2=solve_mod([xx*(xx+g)==n&(2^t2-1)],2^t2)
if(len(r2)>0):
print i
for yy in r2:
result=partial_p(yy[0].lift(),t2,t2+t1,n,2)
if(result):
print result
n = 19787744055007771920075491868994595093008774777733094463267657045445491006226236122756176027670521293033971930544901550426019602751914449163021323306625597709926868006449807069771718137975569399401849816498362414538410746758435242648534889529758318238899434433000229062428208609293124251445336557626496221144799221046211625817903374716018476165360438767645671019540717239635125639502429065579038145981461938320723654297611786334692045444446931985658100226649855775288924797607205159552266184766109424149643788888036522548799788510471386824605128594324123755605356061187596278801235136397504966233996876612550128991993
delta = 608
gamma = 10356174804751816155721586247435033090295658846311470412894333
t2=(1024+delta)/2
t1=1024-t2
for i in range(-100,100):
compute(i)
for i in range(-500,-100):
compute(i)
for i in range(100,500):
compute(i)
for i in range(-1000,-500):
compute(i)
for i in range(500,1000):
compute(i)
for i in range(-1500,-1000):
compute(i)
for i in range(1000,1500):
compute(i)
for i in range(-2000,-1500):
compute(i)
for i in range(1500,2000):
compute(i)
最后根据分解出的p求出flag
>>> p=120636006277871411275371530087790065770134552887607039956902910661113789275639922696690508302593627744373797262608926169377237610359496446738472601322383943513077466708305240126154227404187298195677026542923410015128149399197711734201505801640198120678665925046049173946467463512174621999415403951225544839099
>>> q=164028507454307953998030584561374532729364541052939989108986085613755695456310053587570797100201540198211442715120682600140701077905210171298161735285877275283595109376452234736485541588980439459655220129066692701413940064735892881327113198833726660675511352354042700510883423696866994972583876907812196351707
>>> n=19787744055007771920075491868994595093008774777733094463267657045445491006226236122756176027670521293033971930544901550426019602751914449163021323306625597709926868006449807069771718137975569399401849816498362414538410746758435242648534889529758318238899434433000229062428208609293124251445336557626496221144799221046211625817903374716018476165360438767645671019540717239635125639502429065579038145981461938320723654297611786334692045444446931985658100226649855775288924797607205159552266184766109424149643788888036522548799788510471386824605128594324123755605356061187596278801235136397504966233996876612550128991993
>>> n==p*q
True
>>> f=(p-1)*(q-1)
>>> from libnum import *
>>> d=invmod(0x10001,f)
>>> cipher=10063064794864843312128550042856940325978411568147543113920034231240570289963573829350421824150738515370421890157251474391322062002314450945021754117310424572492269370708571470899634910437973313992828194830717962139782475599768731817262528197135385396676490833516836507954960687728249257889382361566995432480474003042400686070268597001143235114910699463880385869328802742259244425195913477126022427275517767473528864476008925769721936711219464549635822368655994152344558111678892454800804705969648049428383321047344672503044122691602273760755850221193346698969570690169363339213010957323861023611410002000863099686168
>>> n2s(pow(cipher,d,n))
'MeePwnCTF{It_is_the_time_to_move_to_Post_Quantum_Cryptography_DAGS}'
