长城杯baby_rsa题解

Source

from Crypto.Util.number import *
from secret import flag, v1, v2, m1, m2


def enc_1(val):
    p, q = pow(v1, (m1+1))-pow((v1+1), m1), pow(v2, (m2+1))-pow((v2+1), m2)
    assert isPrime(p) and isPrime(q) and (
        p*q).bit_length() == 2048 and q < p < q << 3
    return pow(val, 0x10001, p*q)


def enc_2(val):
    assert val.bit_length() < 512
    while True:
        fac = [getPrime(512) for i in range(3)]
        if isPrime(((fac[0]+fac[1]+fac[2]) << 1) - 1):
            n = fac[0]*fac[1]*fac[2]*(((fac[0]+fac[1]+fac[2]) << 1) - 1)
            break
    c = pow(val, 0x10001, n)
    return (c, n, ((fac[0]+fac[1]+fac[2]) << 1) - 1)


if __name__ == "__main__":
    assert flag[:5] == b'flag{'
    plain1 = bytes_to_long(flag[:21])
    plain2 = bytes_to_long(flag[21:])
    print(enc_1(plain1))
    print(enc_2(plain2))

'''
15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311
(40625981017250262945230548450738951725566520252163410124565622126754739693681271649127104109038164852787767296403697462475459670540845822150397639923013223102912674748402427501588018866490878394678482061561521253365550029075565507988232729032055298992792712574569704846075514624824654127691743944112075703814043622599530496100713378696761879982542679917631570451072107893348792817321652593471794974227183476732980623835483991067080345184978482191342430627490398516912714451984152960348899589532751919272583098764118161056078536781341750142553197082925070730178092561314400518151019955104989790911460357848366016263083, 43001726046955078981344016981790445980199072066019323382068244142888931539602812318023095256474939697257802646150348546779647545152288158607555239302887689137645748628421247685225463346118081238718049701320726295435376733215681415774255258419418661466010403928591242961434178730846537471236142683517399109466429776377360118355173431016107543977241358064093102741819626163467139833352454094472229349598479358367203452452606833796483111892076343745958394932132199442718048720633556310467019222434693785423996656306612262714609076119634814783438111843773649519101169326072793596027594057988365133037041133566146897868269, 39796272592331896400626784951713239526857273168732133046667572399622660330587881579319314094557011554851873068389016629085963086136116425352535902598378739)
'''

简要分析

题目代码如上，题目分为两部分，一部分是构造两个有固定形式的p和q，加密flag的前半段，第二部分是构造一个内部结构已知的n，并提示flag的大小在512bit以内。

第一部分

一般这种告诉我们p和q有固定形式的，这种p和q在数轴上分布是比较稀疏的，给出的几个约束条件进一步在较小的范围内确定p和q即可。

我先是进行了一个不太好的尝试：

我根据

assert isPrime(p) and isPrime(q) and (p*q).bit_length() == 2048 and q < p < q << 3

写出了如下的代码：

p=[]
q=[]
for i in range(10000):
    for j in range(200):
         m=pow(i, (j+1))-pow((i+1), j)
         m_2=m**2
         l=len(bin(m_2))
         if(l>=2050 and l<=2053 and isPrime(m)):
              p.append(m)
              print(i, j)
for i in range(10000):
    for j in range(200):
         m=pow(i, (j+1))-pow((i+1), j)
         m_2=m**2
         l=len(bin(m_2))
         if(l>=2047 and l<=2050 and isPrime(m)):
              q.append(m)
              print(i, j)
c=15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311
for i in p:
    for j in q:
        if(len(bin(i*j))== 2050 and j < i and i < j<<3):
            d=inverse(0x10001,(i-1)*(j-1))
            m=long_to_bytes(pow(c,d,i*j))
            if(b"flag{" in m):
                print(m)

以上代码中，我采用生成数平方的区间去找这些稀疏分布的数，然后再在这些数解密的结果中搜寻“flag{”的字串，最终得到前半段flag。

这里我用的方法虽然没什么问题，但是在开始不知道 i 和 j 的范围的情况下进行大范围盲猜的情况下，很可能会让程序运行很久，这种情况下，建议使用tqdm库，来生成一个进度条，比较类似于我们平常调试程序时候用的中间输出，但是可视化了，比较舒服。

改进后：

from Crypto.Util.number import *
from tqdm import tqdm
p=[]
q=[]
for i in tqdm(range(10000)):
    for j in range(200):
         m=pow(i, (j+1))-pow((i+1), j)
         m_2=m**2
         l=len(bin(m_2))
         if(l>=2050 and l<=2053 and isPrime(m)):
              p.append(m)
              print(i, j)
for i in tqdm(range(10000)):
    for j in range(200):
         m=pow(i, (j+1))-pow((i+1), j)
         m_2=m**2
         l=len(bin(m_2))
         if(l>=2047 and l<=2050 and isPrime(m)):
              q.append(m)
              print(i, j)
c=15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311
for i in p:
    for j in q:
        if(len(bin(i*j))== 2050 and j < i and i < j<<3):
            d=inverse(0x10001,(i-1)*(j-1))
            m=long_to_bytes(pow(c,d,i*j))
            if(b"flag{" in m):
                print(m)

是不是瞬间感觉很舒服，缓解了自己秃头的压力。

得到前半段flag{8102c552-3d78-4a

第二部分

第二部分我做的时候就感觉很奇怪，这个代码产生的

$((fac[0]+fac[1]+fac[2]) << 1) - 1$

不得是个素数吗？我再瞧瞧生成的算法，确认了自己的想法：

while True:
        fac = [getPrime(512) for i in range(3)]
        if isPrime(((fac[0]+fac[1]+fac[2]) << 1) - 1):
            n = fac[0]*fac[1]*fac[2]*(((fac[0]+fac[1]+fac[2]) << 1) - 1)
            break

这段代码无疑就是在说，找三个素数，得到这个串，如果这一串是素数就生成一个 n 并结束循环，如果不是素数，就再生成三个新素数，再算这一串，直到它为素数为止。

按这逻辑，这一串怎么说都得是素数吧，但是它偏偏可以分解！！这就让我当时卡住了。

这道题本身倒是不难，题目提示了flag的后半段小于512个bit，我们很容易通过yafu得到那一串本该是素数的数的分解

而这个数的大于512bit，同时又是n的因子，我们知道flag的后半段是小于512bit的，那么其实模它就可以得到最终答案了。

import gmpy2
from Crypto.Util.number import *


def main():
    _n = 39796272592331896400626784951713239526857273168732133046667572399622660330587881579319314094557011554851873068389016629085963086136116425352535902598378739
    e = 0x10001
    c = 40625981017250262945230548450738951725566520252163410124565622126754739693681271649127104109038164852787767296403697462475459670540845822150397639923013223102912674748402427501588018866490878394678482061561521253365550029075565507988232729032055298992792712574569704846075514624824654127691743944112075703814043622599530496100713378696761879982542679917631570451072107893348792817321652593471794974227183476732980623835483991067080345184978482191342430627490398516912714451984152960348899589532751919272583098764118161056078536781341750142553197082925070730178092561314400518151019955104989790911460357848366016263083
    phi_n = (191 - 1) * (193 - 1) * (627383 - 1) * (1720754738477317127758682285465031939891059835873975157555031327070111123628789833299433549669619325160679719355338187877758311485785197492710491 - 1)
    d = gmpy2.invert(e, phi_n)
    m = pow(c % _n, d, _n)
    print(long_to_bytes(m))


if __name__ == '__main__':
    main()