superprime [HITCON 2022]

First Post:

Last Update:

Word Count:
1.3k

Read Time:
7 min

superprime [HITCON2022]

Analyze

先上题

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 = }")

output.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
n1 = 132240475872174910020944408159013384770525986234801028624784519134365862704105251340824787510945183963356820885920367304711310957365047441178683686926111455575911962257698539064559510444855775549001648292058855493337857073693460061212792795075263084221929517773754699732129582794061997056827998985829666251060653380798686353779510948629280009197715644814616657550158740378670095210797455828266323922570838468050733341304227070902756780052159113811360169205531739117518635829837403006788948761106892086004133969899267757339921

n2 = 95063555614573541810575593850289506856925979977609991181205616159125089261546784721154599484613262518469706157215924537125160406418217535531993036958388330505871763176297570429533467696205928686731756713059807727405313286020007347211892135226632724359291407913539632339885950358476265995466145680878334722001

n3 = 59077122528757446350604269162079270359932342538938986760275099248290981958441838384256597839386787448447136083450980256330743221155636885358548541847176342745397373638152767362253944731433134474562146358334422503033973244936835557423934491676324297243326613498319086748647812745223753746779568080090592100960499863677438403657325762852705171109382084916335379889394829715777901290096314487661584614712488781379507151355301063123233880909931925363322846957197537676660047824476129446066149857051131731840540157488590899311381370266592295206055792990886734933291304077440476730373491475852882163732120626849448728573574411786320772125534383707413572678316508826450778346723441956945169297689138799298561759843280317867927205551400065163199599457

n4 = 24589423756497058585126900932611669798817346035509889383925628660158156567930038333401661451846451875869437263666365776498658699865323180836374906288949824205543130261556051807217164348291174483234810669420041361857307271050079366739157441129916338485838528114129985080841445467007786565727910355311119650431197742495274527401569906785121880408809802492383216836691265423297722021017515667257863302820657924121913047547741420413553737917632809270380269758313556777803344394624408862183672919570479289614998783678080936272369083

n5 = 185885020243714550225131939334004568560534422416697599024696590344782893162219788079305752632863387855011040772104676488940707663157284194641170875157382507202789029285286466326803699701161968587945867047101502048926016515139728368809523009828247173096909917611001113266938209226483162533302629909322412013492978440863258135181226831155024690292336026753678424906151360739424148666951389956182136072508650529271179749569637083537783283360860102371562796635391549934474381821125255176073752645643893294533330184238070085333427

e = 65537

c = 44836759088389215801662306050375432910426695023654894661152471598197009644316944364461563733708795401026569460109604554622161444073404474265330567406370705019579756826106816505952084633979876247266812002057927154389274998399825703196810049647324831928277737068842860115202258059693760003397831075633707611377854322143735834890385706873765241863615950449707047454133596389612468366465634011925228326638487664313491916754929381088396403448356901628825906815317934440495749705736715790281606858736722493438754469493049523175471903946974639097168758949520143915621139415847104585816466890751841858540120267543411140490236193353524030168152197407408753865346510476692347085048554088639428645948051171829012753631844379643600528027854258899402371612

Phase 1

首先观察一下函数getSuperPrime(nbits)，其首先生成一个nbits位的素数p，将其转换为字符串后用函数bytes_to_long()再次转换，循环直到结果为素数pp为止，返回值为p，pp，查看一下bytes_to_long()的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def bytes_to_long(s):
    """Convert a byte string to a long integer (big endian).

    In Python 3.2+, use the native method instead::

        >>> int.from_bytes(s, 'big')

    For instance::

        >>> int.from_bytes(b'\x00P', 'big')
        80

    This is (essentially) the inverse of :func:`long_to_bytes`.
    """
    acc = 0

    unpack = struct.unpack

    # Up to Python 2.7.4, struct.unpack can't work with bytearrays nor
    # memoryviews
    if sys.version_info[0:3] < (2, 7, 4):
        if isinstance(s, bytearray):
            s = bytes(s)
        elif isinstance(s, memoryview):
            s = s.tobytes()

    length = len(s)
    if length % 4:
        extra = (4 - length % 4)
        s = b'\x00' * extra + s
        length = length + extra
    for i in range(0, length, 4):
        acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
    return acc

整个函数就是把参数的每一个字节转成16进制然后拼起来，显然，p越大，pp也越大，那么我们便可以对进行二分规约

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#Phrase 1
def l2b2l(p):
    trans=str(p).encode()
    return(bytes_to_long(trans))

def break1(n):
    l=0
    r=2**512
    v=0
    while(l<=r):
        m=(l+r)//2
        v=m*l2b2l(m)
        if(v<n):
            l=m
        elif(v>n):
            r=m
        else:
            return m,n//m

Phase 2

对和进行分析：

所以可以对每一位进行爆破

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#Phase 2
#Prune and Search
#official writeup from maple3142

def break2(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)

Phase 3

第三部分很简单，可以直接参照第一部分，只是这里有一些小变化，，仍然进行二分规约

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#Phase3
def break3(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 * l2b2l(n2 // l2b2l(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), (l2b2l(p1), n2 // l2b2l(p1))

所有的p和q都知道了，直接进行RSA解密即可得到flag

EXP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
from Crypto.Util.number import *
from gmpy2 import *

#Phase 1
def l2b2l(p):
    trans=str(p).encode()
    return(bytes_to_long(trans))

def break1(n):
    l=0
    r=2**512
    v=0
    while(l<=r):
        m=(l+r)//2
        v=m*l2b2l(m)
        if(v<n):
            l=m
        elif(v>n):
            r=m
        else:
            return m,n//m

#Phase 2
#Prune and Search
#official writeup from maple3142

def break2(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)

#Phase3
def break3(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 * l2b2l(n2 // l2b2l(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), (l2b2l(p1), n2 // l2b2l(p1))

#break
with open("output.txt") as f:
    exec(f.read())

p1,q1=break1(n1)
(p2,p3),(q2,q3)=break2(n2,n3)
(p4,q5),(p5,q4)=break3(n4,n5)

phi1=(p1-1)*(q1-1)
phi2=(p2-1)*(p3-1)
phi3=(q2-1)*(q3-1)
phi4=(p4-1)*(q5-1)
phi5=(p5-1)*(q4-1)

d1=invert(e,phi1)
d2=invert(e,phi2)
d3=invert(e,phi3)
d4=invert(e,phi4)
d5=invert(e,phi5)

c=pow(c,d3,n3)
c=pow(c,d4,n4)
c=pow(c,d5,n5)
c=pow(c,d1,n1)
c=pow(c,d2,n2)

print(long_to_bytes(c))
reward
Alipay
Wechat
≡