MeepwnCTF18-BITBITBIT

这题主要考察的是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)&(2^t1-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],2^t1)
r2=solve_mod([x * (x+g)==n&(2^t2-1)],2^t2)

因此我们可以在一个合理的范围爆破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}'