首页 > 其他分享 >HITCON CTF 2022 SuperPrime

HITCON CTF 2022 SuperPrime

时间:2023-02-12 17:46:27浏览次数:58  
标签:10 48 SuperPrime CTF 2022 n1 n2 aligned 256

继续复现HITCON CTF 的赛题。争取近期全部复现完。

源码

chall.py

from Crypto.Util.number import getPrime, isPrime, bytes_to_long

def getSuperPrime(nbits):
    while True:
        p = getPrime(nbits)
        pp = bytes_to_long(str(p).encode())
        if isPrime(pp):
            return p, pp


p1, q1 = getSuperPrime(512)
p2, q2 = getSuperPrime(512)
p3, q3 = getSuperPrime(512)
p4, q4 = getSuperPrime(512)
p5, q5 = getSuperPrime(512)

n1 = p1 * q1
n2 = p2 * p3
n3 = q2 * q3
n4 = p4 * q5
n5 = p5 * q4

e = 65537
c = bytes_to_long(open("flag.txt", "rb").read().strip())
for n in sorted([n1, n2, n3, n4, n5]):
    c = pow(c, e, n)

print(f"{n1 = }")
print(f"{n2 = }")
print(f"{n3 = }")
print(f"{n4 = }")
print(f"{n5 = }")
print(f"{e = }")
print(f"{c = }")

思路

首先可以令

\[f(x)=bytes\_to\_long(str(x).encode()) \]

通过long_to_bytes源码,知道这这个函数就是把参数的每一个字节转成16进制然后拼起来。假设

\[\begin{aligned} x &= a_0 + a_1*10 + a_2*10^2 + \cdots \\ &= \sum_{i=0}^na_i*10^i \end{aligned} \]

那么

\[\begin{aligned} f(x) &= (a_0 + 48) + (a_1 + 48)<<8 + (a_2 + 48)<<16 + \cdots\\ &=(a_0 + 48) + (a_1 + 48)*2^{8} + (a_2+48)*2^{16}+\cdots\\ &=\sum_{i=0}^{n}(a_i+48)*256^{i} \end{aligned} \]

根据题目我们可以把题目分解成三个部分

# part 1
n1 = p1 * q1
# part 2
n2 = p2 * p3
n3 = q2 * q3
# part 3
n4 = p4 * q5
n5 = p5 * q4

Part 1

很容易知道\(f(x)\)是单调递增的,就可以用二分法搜索,时间复杂度为\(O(logN)\),最多查找512次,这个时间复杂度是非常低的。

def binary_search(n):
    L, R = 0, 2**512
    while L <= R:
        middle = (L+R) // 2
        v = middle*f(middle)
        if v > n:
            R = middle
        elif v < n:
            L = middle
        else:
            return middle

最后确实找了512次,只用了一秒不到。

Part 2

n2, n3的表达式得到

\[\begin{aligned} n_2 &= p_2*p_3 \\ &=(a_{01}+a_{11}*10+a_{21}*10^2+\cdots+)*(a_{02}+a_{12}*10+a_{22}*10^2+\cdots+) \end{aligned} \]

\[\begin{aligned} n_3&=q_2*q_3 \\ &= [(a_{01}+48) + (a_{11}+48)*256 + (a_{21}+48)*256^2+\cdots+]*[(a_{02}+48)+(a_{12}+48)*256+(a_{22}+48)*256^2+\cdots+] \end{aligned} \]

可以推出

\[\begin{aligned} n_2 &\equiv a_{01}*a_{02} \pmod{10} \\ n_2 &\equiv (a_{01} + a_{11}*10)*(a_{02}+a_{12}*10) \pmod{10^2} \\ &\vdots \\ n_2 &\equiv (a_{01} + \cdots+a_{n1}*10^n)*(a_{02} + \cdots+a_{n2}*10^n) \pmod{10^{n+1}} \end{aligned} \]

\[\begin{aligned} n_3 &\equiv (a_{01}+48)*(a_{02}+48) \pmod{256}\\ &\vdots\\ n_3&\equiv[(a_{01}+48)+\cdots+(a_{n1}+48)*256^n]*[(a_{02}+48)+\cdots+(a_{n2}+48)*256^n] \pmod{256^{n+1}} \end{aligned} \]

欸?是不是感觉似曾相识。很像BabySSS这道题的处理,不过这里有两个未知变量,但是对于每一个模10和256的幂,有两个方程,而且\(a_{i1}\)和\(a_{i2}\)的取值都在\([0, 9]\)
这个区间内,可以爆破。具体的方法使用到了Prune and Search搜索算法。

#Prune and Search
#official writeup from maple3142

def factor2(n1, n2):
    n1p = None

    def test_digits(ps, qs):
        nonlocal n1p
        if n1p is not None:
            return False
        p = sum([pi * 10**i for i, pi in enumerate(ps)])
        pp = sum([(48 + pi) * 256**i for i, pi in enumerate(ps)])
        q = sum([pi * 10**i for i, pi in enumerate(qs)])
        qq = sum([(48 + pi) * 256**i for i, pi in enumerate(qs)])
        if p != 0 and p != 1 and n1 % p == 0:
            n1p = p
            return False
        m1 = 10 ** len(ps)
        m2 = 256 ** len(qs)
        return (p * q) % m1 == n1 % m1 and (pp * qq) % m2 == n2 % m2

    def find_ij(ps, qs):
        for i in range(10):
            for j in range(10):
                if test_digits(ps + [i], qs + [j]):
                    yield i, j

    def search(ps, qs):
        for i, j in find_ij(ps, qs):
            search(ps + [i], qs + [j])

    search([], [])
    n2p = bytes_to_long(str(n1p).encode())
    assert n2 % n2p == 0
    return (n1p, n1 // n1p), (n2p, n2 // n2p)

Part 3

官方wp的解决方法是把\(n_4\)看成

\[\begin{aligned} n4&=p_4*f(p_5) \\ &=p_4*f(\frac{n_5}{f(p4)}) \end{aligned} \]

然后在\(p_4\)的长度不变的时候,\(n_4\)也是一个单调递增的,就可以用二分搜索分解。
offical writeup

def factor3(n1, n2):
    def try_factor(l, r): #二分搜索
        while l < r:
            m = (l + r) // 2
            if m > 1 and n1 % m == 0:
                return m
            if m * f(n2 // f(m)) < n1:
                l = m + 1
            else:
                r = m - 1

    for i in range(16):
        # brute force top 4 bits of p1
        # because len(str(p1)) must be constant to have monotonic property
        l = i << 508
        r = l + (1 << 508)
        if p1 := try_factor(l, r):
            return (p1, n1 // p1), (f(p1), n2 // f(p1))

最后所有的n都分解了,解5次rsa就可以了。

总结

这道题并没有考到很多密码学上的知识,而是一些非常有用的搜索算法,以及数学上的变换。通过这道题,学习了很多,包括Prune and Search还有对于时间复杂度的估算的应用。

标签:10,48,SuperPrime,CTF,2022,n1,n2,aligned,256
From: https://www.cnblogs.com/tr0uble/p/17114301.html

相关文章

  • HITCON CTF 2022 BabySSS
    周末抽时间看了一下HITCON的题,不愧是顶尖的比赛。由于水平比较菜,在比赛期间就做出来这么一道题(实际上就周六早上看了一下,下午赶ddl,周日打安洵杯)。maple3142师傅和lyc师傅......
  • HITCON CTF 2022 Secret
    源码prob.pyimportrandom,osfromCrypto.Util.numberimportgetPrime,bytes_to_longp=getPrime(1024)q=getPrime(1024)n=p*qflag=open('flag','rb'......
  • HSCSEC CTF 2023部分WP
    EZSSTI?name={{''.__class__.__mro__[-1].__subclasses__()}}查看所有子类fromrequestsimport*foriinrange(300):url="http://4dcc7f0f-0e07-49e1-b2c8-b9c......
  • .NET技术分享日活动20221022
    2022年10月22日下午,个人组织举办了山东地区的第六次.NET技术分享日活动。围绕.NET、低代码LowCode、云原生CloudNative、大数据、算法等方向进行创新技术的实践分享。......
  • Visual Studio 2019 与 Visual Studio 2022的下载方式
    相信大家目前百度或者其他搜索引擎搜索到的都是2022了,那么vs2019该如何安装呢?vs2019下载地址:https://visualstudio.microsoft.com/zh-hans/thank-you-downloading-visu......
  • CSP NOIP 游记 2022
    CSP2022.9.17初赛前一天,++rp。今年flag:搞到7级钩子。2022.9.18CSP2022J1ACACBBBCADDACABFFFFFBFTTCCBTTTFCBAABCDAABCCACSP2022S1感觉考完非常不好。B......
  • 我的2022——有点卷、没学习、还羊了
    夜幕下的北京,迎来全新的一年,屏幕前的我,又到了该做年终总结的时候了。MacBook的摄像头像Moss一样,注视着我,注视着红尘。在Moss的眼中,可能所有的悲欢离合都没有什么大不了,世间......
  • 新版国家标准GB/T 28181—2022将于2023年7月1日正式实施,与GB/T 28181—2016差别有哪些
    新版国家标准GB/T28181-2022《公共安全视频监控联网系统信息传输、交换、控制技术要求》已于2022年12月30日发布,将于2023年7月1日正式实施。与GB/T28181—2016相比,除结构调......
  • 2022年最全Elasticsearch面试题附答案解析大汇总
    2022年最全Elasticsearch面试题附答案解析大汇总全部面试题答案,更新日期:01月30日,直接下载吧!下载链接:高清500+份面试题资料及电子书,累计10000+页大厂面试题PDFElasti......
  • 最新2022年Elasticsearch面试题高级面试题及附答案解析
    最新2022年Elasticsearch面试题高级面试题及附答案解析全部面试题答案,更新日期:01月30日,直接下载吧!下载链接:高清500+份面试题资料及电子书,累计10000+页大厂面试题PDF......