20210903-Blue Whale Freshers & 第六届中国海洋大学信息安全竞赛-CryptoSecPartWriteUp

Posted on Edited on In , Views: Symbols count in article: 57k Reading time ≈ 52 mins.

 

Blue Whale Freshers

CheckIn

aW9kantaaG9mcnBoX3dyX0Zsc2todVZzZGZoIX0=

base64$\rightarrow$Caesar 3

flag{Welcome_to_CipherSpace!}

baby_OTP

1
2
3
4
5
flag = 'flag{***********}'.strip('flag{').strip('}')
mask = 'It_is_Mask!'
cipher = ''.join([chr(ord(flag[i]) ^ ord(mask[i])) for i in range(len(flag))])
print(cipher.encode())
# b'1;-6B,\x12R\x12\x18X'

flag{xOr_1s_3asy}

baby_exGCD

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

flag = b'flag{********}'.strip(b'flag{').strip(b'}')
flag = bytes_to_long(flag)
p = 9250064974587738262998767
assert isPrime(p) and p > flag

for i in range(1, p):
    if (i * flag - 1) % p == 0:
        print(i)
        # 5141371231815721033613206
        exit()

flag{inverse_}

baby_quadratic-residue

1
2
3
4
5
6
7
from Crypto.Util.number import *

flag = b'flag{****}'.strip(b'flag{').strip(b'}')
flag = bytes_to_long(flag)
p = 10**11 + 3
assert isPrime(p) and flag < p
assert flag ** 2 % p == 45738244299
1
2
3
4
5
6
from Crypto.Util.number import *
from gmpy2 import *
p = 10**11 + 3
c = 45738244299
print(long_to_bytes(pow(c, (p + 1) // 4, p)))
print(long_to_bytes(p-pow(c, (p + 1) // 4, p)))

flag{ea5y}

baby_proof_of_work

1
2
3
4
5
6
from uuid import *
from hashlib import md5

flag = 'flag{' + str(uuid4()) + '}'
assert md5(flag.encode()).hexdigest() == '02195c68e0af460e431d8076aeda74d2'
assert flag[:-6] == 'flag{ba9951a2-c233-4555-b703-1337cdc'

UUID全称Universally Unique Identifier，通用唯一识别码，有点hash函数那味

16字节128位长的数字，通常以36字节的字符串表示，示例如下：

3F2504E0-4F89-11D3-9A0C-0305E82C3301

其中的字母是16进制表示，大小写无关

1
2
3
4
5
6
7
8
9
10
11
from hashlib import md5
from itertools import product
from string import hexdigits
space = hexdigits[:-6]+'-'
head = 'flag{ba9951a2-c233-4555-b703-1337cdc'
for i in product(space, repeat=5):
    tail = ''.join(i)
    flag = head + tail + '}'
    if md5(flag.encode()).hexdigest() == '02195c68e0af460e431d8076aeda74d2':
        print(flag)
        break

flag{ba9951a2-c233-4555-b703-1337cdcf4e3d}

baby_stream

1
2
3
4
5
6
7
8
9
flag = 'flag{************************************}'
key = '******'
cipher_set = []

for i in range(len(flag)):
    cipher_set.append(ord(flag[i]) ^ ord(key[i % len(key)]))
    
print(cipher_set)
# [39, 43, 14, 46, 61, 28, 53, 24, 6, 58, 25, 19, 45, 38, 8, 22, 48, 16, 51, 62, 48, 44, 39, 6, 56, 53, 6, 46, 46, 1, 30, 62, 0, 60, 25, 30, 47, 40, 24, 104, 103, 8]
1
2
3
4
5
6
7
8
9
10
11
12
# key
cipher_set = [39, 43, 14, 46, 61, 28, 53, 24, 6, 58, 25, 19, 45, 38, 8, 22, 48, 16, 51, 62, 48, 44, 39, 6, 56, 53, 6, 46, 46, 1, 30, 62, 0, 60, 25, 30, 47, 40, 24, 104, 103, 8]
flag = 'flag{'
key_parts = ''
for i in range(len(flag)):
    key_parts += chr(ord(flag[i]) ^ cipher_set[i])
# print(key_parts)
key = key_parts + 'u'
flag = ''
for i in range(len(cipher_set)):
    flag += chr(cipher_set[i] ^ ord(key[i % len(key)]))
print(flag)

flag{it_is_flag_very_easyright_you_know!!}

baby_gcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537

data = bytes_to_long(flag[:5])
flag = bytes_to_long(flag)
assert flag < n

print(n)
print(pow(flag, e, n))
print(pow(data, p, n))

'''
13363911977381658054715749670898309746795378579901910744548891514119930365598763675900066558885526891111578153852505468781338322217670232547796382694454636854667270681576447072504446292150761913091590029636528472343128844309564616107199650709984359476698570483265981944043392159470470399285710046127749035432951653658588305611925416558985714889031024015889163354845747839686029526924544667996738073746867634061472313832146768108912385319342837354867508476685733543811014072221007141421012887749322127577045821626420889053517061583804135616739747129097247525956401277280445776859357071596335365635129076760168060966607
10223697039967223267682181717488147275927367118413751107492765199808800173812525650250727485499667865861401513584367265156007990663044846919938201443790340452739587600478171647549035134701499317817566764471386396555838202312403465048654949983406474954598930748110503439437344393592595276155454781057276134145504380796903813247840224774545523607884159231845974898250966348829961146367007792068641912245512595560267823445320076403263562739363031632062342189801065044810262234549063628866927777175935167665086806182399437659557762115546086926046162171444133449925064332483160873278631920623056454541931283939092643363769
8407634300955121132761790421404876464439171066953178241717181127133987272675024893882593118056392128685766053032230696604294564590205211272173466649761038412652836039898073070956658795752143907494078331602633733508202164910668310281736798447342720590176784043217138366486935759740252492090711972604375828430662071251842986961821739442853955099030914125069036528452384768331862222815666911989108515279529962229787757202741446628933696420814510070543569524978792494846011056162739011324784470527582059752893749932914976314325653212342060502072125738929300327802791282926291615350754819628989468488062512660927247417470
'''

小费马忘了，多亏尚师傅提醒，白白耽搁好多时间

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from sage import gcd, inverse

n = 13363911977381658054715749670898309746795378579901910744548891514119930365598763675900066558885526891111578153852505468781338322217670232547796382694454636854667270681576447072504446292150761913091590029636528472343128844309564616107199650709984359476698570483265981944043392159470470399285710046127749035432951653658588305611925416558985714889031024015889163354845747839686029526924544667996738073746867634061472313832146768108912385319342837354867508476685733543811014072221007141421012887749322127577045821626420889053517061583804135616739747129097247525956401277280445776859357071596335365635129076760168060966607
c = 10223697039967223267682181717488147275927367118413751107492765199808800173812525650250727485499667865861401513584367265156007990663044846919938201443790340452739587600478171647549035134701499317817566764471386396555838202312403465048654949983406474954598930748110503439437344393592595276155454781057276134145504380796903813247840224774545523607884159231845974898250966348829961146367007792068641912245512595560267823445320076403263562739363031632062342189801065044810262234549063628866927777175935167665086806182399437659557762115546086926046162171444133449925064332483160873278631920623056454541931283939092643363769
e = 0x10001
_c = 8407634300955121132761790421404876464439171066953178241717181127133987272675024893882593118056392128685766053032230696604294564590205211272173466649761038412652836039898073070956658795752143907494078331602633733508202164910668310281736798447342720590176784043217138366486935759740252492090711972604375828430662071251842986961821739442853955099030914125069036528452384768331862222815666911989108515279529962229787757202741446628933696420814510070543569524978792494846011056162739011324784470527582059752893749932914976314325653212342060502072125738929300327802791282926291615350754819628989468488062512660927247417470
data = bytes_to_long(b'flag{')
p = gcd(_c-data, n)
assert n % p == 0
q = n // p
print(long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), n)))

flag{212333333333333333333333333333333333333333333333333333333333}

baby_RSA

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
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag # it means we hide the flag

class textbookRSA: 
    def __init__(self, p, q):
        self.p = p
        self.q = q
        self.N = self.p * self.q
        self.e = 65537
        self.d = invert(self.e, (self.p - 1) * (self.q - 1))

    def encrypt(self, m):
        assert m < self.N
        return powmod(m, self.e, self.N)
        
    def decrypt(self, c):
        return powmod(c, self.d, self.N)
        
    def vulnerability(self):
        return (self.p, self.q)
        

enc = textbookRSA(getPrime(512), getPrime(512))
c = enc.encrypt(bytes_to_long(flag))
vul = enc.vulnerability()
print(c)
print(vul)
'''
64701533343688372690654293712295773404129813784694237799153926736962621435068947287072687977347837010274295586096313263626594906283456719476000887723325924200788009114768670335038095853813713911223601130462041497767344698895750519413521122224460972816020538747290579261708064784859421449573347263967997160490
(9830899743055626691883675211456964737373662213776941723212592815656583592986430578241161039226354632749313979784000329125662593896949062022073761989419743, 11413016938938274789177683025211095871490834309326773658937859388628168661305423686103065519733651943178907824777739859479458155320334969216051745769010187)
'''

flag{welcome_to_crypto}

LCG

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
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

class LCG: 
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c
        self.seed = bytes_to_long(flag)
        self.state = self.seed
    def getstate(self):
        while 1:
            self.state = (a * self.state + b) % c
            yield self.state

a, b, c = getPrime(256), getPrime(256), getPrime(256)
prng = LCG(a, b, c)
random_states = []

for i in range(256):
    random_states.append(next(prng.getstate()))

print(random_states[-6:])

'''
[36525894934655222529534846431164486292811941872906741964139901975056461298468, 44760375502060853569502415785606266854123925363856190745249656424194532471837, 99435840430130187938928057751136501366281085823686937625866664159577574922185, 32218838886452625692584366771934359409743014626478611858398172896703555179084, 75894967689014169953442519719124136776429102657940075770201298059192401503113, 59195822914392909511892901455781443859673595142363513265120745050537984795930]
'''

LCG，同余式简单移位和变化；这里只知道最后6个状态，可以推出模数，然后推出乘数和增量

la佬的脚本，稍作修改

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
from functools import reduce
from math import gcd
from Crypto.Util.number import *
from gmpy2 import invert


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def crack_unknown_increment(states, m, a):
    b = (states[1] - states[0] * a) % m
    return m, a, b


def crack_unknown_multiplier(states, m):
    a = (states[2] - states[1]) * modinv(states[1] - states[0], m) % m
    return crack_unknown_increment(states, m, a)


def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2 * t0 - t1 * t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    m = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, m)


# N[i+1] = (A*N[i]+B) % M
# A,B,N均未知
sequence = [36525894934655222529534846431164486292811941872906741964139901975056461298468,
            44760375502060853569502415785606266854123925363856190745249656424194532471837,
            99435840430130187938928057751136501366281085823686937625866664159577574922185,
            32218838886452625692584366771934359409743014626478611858398172896703555179084,
            75894967689014169953442519719124136776429102657940075770201298059192401503113,
            59195822914392909511892901455781443859673595142363513265120745050537984795930]
modulus, multiplier, increment = crack_unknown_modulus(sequence)
t = sequence[-1]	
d = invert(multiplier, modulus)
for i in range(256):
    t = (((t - increment) % modulus) * d) % modulus
print(long_to_bytes(((t - increment) % modulus) * d))
for i in range(999999999):
    _t = t + i * modulus
    print(_t)
    flag = long_to_bytes(_t)
    if b'flag' in flag:
        print(flag, i)

为什么爆破了好久出不来，如果flag很大的话，那这样是很难出来的；因为我们求出来的这256伪随机数，是在模c下的，相当于我们知道的第一个状态，只是和flag同余的一个数，如果flag稍微大点，就要利用同余等式去枚举

怎么会这样

image-20210902103314795

暂时不会了，可能还有隐藏的套娃

flag{easyLcG!}

来自出题师傅的亲自教导

求出来的模数还有一个公因子3，由于当时是通过getPrime取得的，所以正确模数应该是个素数

多整除个3就出了

1
2
3
4
5
6
modulus = modulus // 3
t = sequence[-1]
d = invert(multiplier, modulus)
for i in range(256):
    t = (((t - increment) % modulus) * d) % modulus
print(long_to_bytes(t))

应该是这里的问题

image-20211014132539513

出来的可能是k*n

RSA2

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
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

def generate_prime(x):
    x += getPrime(200)
    while not isPrime(x):
        x += 1
    return x

class textbookRSA:
    def __init__(self, p):
        self.p = p
        self.q = generate_prime(p)
        self.N = self.p * self.q
        self.e = 65537
        self.d = invert(self.e, (self.p - 1) * (self.q - 1))

    def encrypt(self, m):
        assert m < self.N
        return powmod(m, self.e, self.N)
        
    def decrypt(self, c):
        return powmod(c, self.d, self.N)
        

enc = textbookRSA(getPrime(512))
c, N = enc.encrypt(bytes_to_long(flag)), enc.N

print(c)
print(N)
'''
40201544209443285599758189301888608601617874513443526548767757353443929151606722009781340637038714737084415903404819864837006813001196360676445857711384896521463808871500382419732201463547283765775164260612131076631479489522332895847086866318107250553614928244783290548532630896717593368294734888363949457545
114741910526756640742537765026673760290351576565995368541784885613800696330239577637413166195346207752006116626595608590117773931022872753795837847792402503651299975473904115705416410939337300159818820792886315026470035856630685448353338137360972444341989751746886768451631705313621681461055224875826857697751
'''

开方已知p高位，CopperSmith

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from gmpy2 import *

c = 40201544209443285599758189301888608601617874513443526548767757353443929151606722009781340637038714737084415903404819864837006813001196360676445857711384896521463808871500382419732201463547283765775164260612131076631479489522332895847086866318107250553614928244783290548532630896717593368294734888363949457545
n = 114741910526756640742537765026673760290351576565995368541784885613800696330239577637413166195346207752006116626595608590117773931022872753795837847792402503651299975473904115705416410939337300159818820792886315026470035856630685448353338137360972444341989751746886768451631705313621681461055224875826857697751
e = 0x10001
kbits = 202
p0 = int(iroot(n, 2)[0]) >> kbits << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = p0 + x
roots = f.small_roots(X=2^kbits, beta=0.4)
p = p0 + int(roots[0])
assert n % p == 0
q = n // p
print(long_to_bytes(pow(c, invert(e, (p-1)*(q-1)), n)))

flag{fermat_factorization_is_easy}

费马分解？确实

RSA3

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
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

flag = flag.strip(b'flag{').strip(b'}')

class textbookRSA:
    def __init__(self, p, q, e):
        self.p = p
        self.q = q
        self.N = self.p * self.q
        self.e = getPrime(23)
        self.d = invert(self.e, (self.p - 1) * (self.q - 1))

    def encrypt(self, m):
        assert m < self.N
        return pow(m, self.e, self.N)
        
    def decrypt(self, c):
        return pow(c, self.d, self.N)
        
    def vulnerability(self):
        vul = [pow(2, self.e, self.N), pow(4, self.e, self.N), pow(8, self.e, self.N)]
        return vul

enc = textbookRSA(getPrime(27), getPrime(27), getPrime(23))
c, vul = enc.encrypt(bytes_to_long(flag)), enc.vulnerability()

print(c)
print(vul)
'''
5661705370298896
[6716715946456033, 1533036361566453, 2286114319392486]
'''

Pollard’s kangaroo光滑数分解得到e，n也可以分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env sage
# -*- coding: utf-8 -*-

from Crypto.Util.number import *
from gmpy2 import *

c = 5661705370298896
vul = [6716715946456033, 1533036361566453, 2286114319392486]
n = gcd(vul[0]**2-vul[1], vul[0]**3-vul[2])
b = Mod(2, n)
vul0 = Mod(vul[0], n)
e = discrete_log_lambda(vul0, b, (getPrime(22), getPrime(24)))
p, q = factor(n)[0][0], factor(n)[1][0]
print(long_to_bytes(pow(c, invert(e, (p-1)*(q-1)), n)))

flag{345y_}

FuckPython-RSA1

nc 39.106.29.44 10106

比较简单，给一个nc，连上去，要python2，遍历256个字节；之后会得到RSA的公私钥和密文，解密就好

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
#!/usr/bin/env python2
# -*- coding: utf-8 -*-
# nc 39.106.29.44 10106
from itertools import product
from hashlib import md5
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from pwn import *

space = [chr(_) for _ in range(256)]
sh = remote('39.106.29.44', 10106)
context(log_level='debug')


def proof_of_work():
    # md5(XXX + '6a7943b6c92e79'.decode('hex')) == 0e503536b5304015ab9594ec2a5b68af
    proof = sh.recvline()
    tail = proof[11:25].decode('hex')
    HASH = proof[45:77]
    for i in product(space, repeat=3):
        head = ''.join(i)
        x = head + tail
        t = md5(x).hexdigest()
        if t == HASH:
            sh.sendline(head.encode('hex'))
            break


def pem2txt(s):
    with open('private.pem', 'w') as fp1:
        fp1.write(s)
    fp1.close()
    with open('private.pem', "r") as fp2:
        key = fp2.read()
        rsakey = RSA.importKey(key)
        # <_RSAobj @0x7f14f88bf410 n(2048),e,d,p,q,u,private>
        return rsakey.n, rsakey.d


proof_of_work()
sh.recvuntil(b'Your choice:')
# Crypto Challenge
sh.sendline(b'1')
pem = sh.recvuntil(b'-----END RSA PRIVATE KEY-----')[1:]
sh.recvuntil(b'flag2 ==> ')
c = int(sh.recvline().decode())
sh.recvuntil(b'''Input your flag:''')
n, d = pem2txt(pem)
flag = long_to_bytes(pow(c, d, n))
sh.sendline(flag)
sh.recv()

flag{RSA_private_k3y_WHITE_GIVE}

简单的数学0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy2 import *
from hashlib import md5
from secret import flag

assert md5(flag).hexdigest() == 'f9b24dfbe7d8abaab8b6a0188782eff5'

m = bytes_to_long(flag)
p = getPrime(512)
e = 1 << 20
c = pow(m, e, p)
print(c)

'''
3514205322103302728670602150841765811918844361962796570872272936440995516620485389724521788163049805962351733199966478659283631463151399360865675815083685
'''

附件更新

1
2
c = 8803822563647270623115855698498072941389567371514602911761887238000858306724820208054957805578533078861661091923759508072298768127983369027700000415655223
p = 12913561406317113183635547158985401377756429238562558559079682073564209000830793328430323950547190141901547099900430790186447107756095983956460182437021627

直接开平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from hashlib import md5
c = 8803822563647270623115855698498072941389567371514602911761887238000858306724820208054957805578533078861661091923759508072298768127983369027700000415655223
p = 12913561406317113183635547158985401377756429238562558559079682073564209000830793328430323950547190141901547099900430790186447107756095983956460182437021627
e = 0x100000
mi = []

for i in range(20):
    mi.append(pow(c, (p + 1) // 4, p))
    mi.append(p - pow(c, (p + 1) // 4, p))
    c = pow(c, (p + 1) // 4, p)

for i in mi:
    t = long_to_bytes(i)
    if md5(t).hexdigest() == 'f9b24dfbe7d8abaab8b6a0188782eff5':
        print(t)
        break

flag{easymathalgorithm}

简单的数学1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy2 import *
from functools import reduce
from secret import flag

factors = [2, 3, 5, 7, 9, 11, 13, 17]
power   = [17, 11, 8, 8, 6, 5, 5, 3]

m = 2
e = bytes_to_long(flag)

N = reduce(lambda x, y: x * y,[factors[i] ** power[i] for i in range(len(factors))]) + 1
assert isPrime(N) and e < N

c = pow(m, e, N)
print(c)

'''
1581213514613638887702604302628425969362759
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env sage
# -*- coding: utf-8 -*-

from Crypto.Util.number import *
from functools import reduce

factors = [2, 3, 5, 7, 9, 11, 13, 17]
power   = [17, 11, 8, 8, 6, 5, 5, 3]

m = 2
N = reduce(lambda x, y: x * y,[factors[i] ** power[i] for i in range(len(factors))]) + 1

c = 1581213514613638887702604302628425969362759
c = Mod(c, N)
m = Mod(m, N)
print(long_to_bytes(discrete_log(c, m)))

flag{you_got_ph}

困难一点点的数学0

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
from os import urandom
from gmpy2 import *
from random import *
from Crypto.Util.number import *
from secret import flag

assert flag[:4] == b'flag'

def pre(limit):
    primes = [2]
    while primes[-1] < limit:
        primes += [next_prime(primes[-1])]
    return primes

def gen(q):
    global primes
    
    e = 1
    n = 1
    q = next_prime(q)
    
    for i in range(10):
        n *= q ** primes[randint(0, 5)]
        q = next_prime(q)
    
    for i in range(5):
        e *= primes[randint(0, len(primes) - 1)] ** primes[randint(0, 5)]

    return (n, e)

primes = pre(100)
n, e = gen(2 ** 128)
len_ = n.bit_length()

m = bytes_to_long(flag + urandom((len_ >> 3) - len(flag)))
assert m < n

c = pow(m, e, n)

print(n)
print(c)
print(e)

'''
11994856154408832550226173326306706948322784186267813285424273727457277570449721708469377333295795450316798985747411428007939478275824993378444272641075595828905331211398917692117185101479077398613046411577116685482608874046448872880344276808220924860769086887940958633441714352583855540999548720044322998264846012161431636662433683276562625027092028130005970114647137832180580174041968866569822387764690463959881397320450667236461741620403395599935845735617477280364151807003271533625363666352062617204207977554178272479567385510394164676984094113453536958667301026374275130979677305822214444335545662001110540052205079456125870487695548122936396959457217914532553325619253546791069692985512699358985463221502502084675209516472887973080192751916784600603877788797705458888760552581342959043655183973152680603248917128462709597030509958883674860205970644241146476304149515438669191043736965162506814748737378119531830170603146515955648287154128232624377713379199023238511614078806426562021069638546292232028008642595243475950555611966843590609370802372713922810842109296634261927855897749685466429848085401683729949137325841031448197225286597985926477607730381020542179177937190267395728321154320663113144417493792344192501728192224067408526468047697092815734745508911899235305415196605573552817031582341240841963500082141599736527564221706520431869455796746093434293683100803464504347573705307339278622142604231243731290546424726300181230919587809100360017180646300141932273203009540779621343752276406327270280696985946756857577522536182716290889259854732662916401670054957144740292721681742707739784073111634648716873018489059318376430379543710047917376490266767875239644497833040110744093598044604501318749065110017000755265530585848590714646543215789831321305186253110749828658194624302871154167229533880360661192631336611540590753329799514109722282049242508985274973975569128167197103339329219857542511675333185438424100205435264185442625212957816223665085393904833681032006083319868956112013073947804141313761890184012761243094669629438534487954505709858329677691050279420667276012005715403824771026942764503867179041742712964566104284721980020875049780798089586557353746689141977077518535458410939575796862938638716615803650407786897854972763793186411099146552957299304020322056573695947636353479929828321017230745880492761198924142557387134524722498789054500072958840330107186959238787198423202007480930533185363864760876539962555722806312411851288978109934860380767506470800563090423502953911794718800665163227148855219153379250626032923411536090260611564327090513624773651630139865213054047971676969921132075382597029378871818496911936273603167169708274436918974731159618512856370147955309970639864283488998194291564522716718108808644500794139567941894324821270494322487330771480736023069465090696594967014241811185428807158275522064429448212412679526940639213423056138417455582473816078505889037913398303842261835933581251153905467725831957314379762137644348555546053964035105996510374509932329977348336229876173135652873412359763033310447686419768148309532098091688546115562450592460242975433396729597685387307
6351466082405672614085883295737944548919965310077599978190541984976106721260561511854691553565453868610374663116381728992690135579603964052096888436742489466374210302988977830209354260009636769071300547671488922280932487568494617872097079900945916095578623755388259234178268680612477377610914894710907496104362972636720911428089600646222586417255348258167381366988661303295347517753632411800607422746813905818666335896482669033027140915808983428842744482539062142710596639786508537317845758580996627882525064014450135034588736834794180287554486686075596972841883555087846775677701021701479352637748421102843822406248351476994277131337482690575095175009349909732516378330382964315421709620022837911961196685966020194554189215141758762297821318628808131301398323401698864010506849785816316875321330260285263314080063147494581040037600990836748077720670885523772728159627902311960453296092752330952130969249700776559562104117567236854526041303478039102747984668480082877982578911506991928425276445385557957750379045259124494960054574534424135407768648703579640630316936268243612044686186580389257001065198441757102217761322659630686894710273768219013265353821348563879078174064695595467864392947552655739896949699714908310000268044992892911329386425950830381092394869669909772028429264943114745575587790304248788515785473427021962255432027331143994772029825798100553275968616702208346511746136952846098000483881079268476334708733720366718979528049610330304650435684527462122705466063185641405473474636409990254433154961156119876528578589683787745161026307683732723150673756819990500536505419317277397641638885910418427679382912218056162106726030182041543254191389196695732924652812425467589000461451026805090543916784702340460053504268171601901665797607174213052404647848620139395976717777302984408101541424736063698589129484369980805581194717731469528976219054596456039278307705269184407577544084520370372269984748277291765285669123103849832742912650693589627527731652063314823281800811899078839130817382422516706798968876936676146422986085568876006217756879288536420625765537735876869140624480292479927568778211793082812927301155660252404197005435807632705417486828432680003527496336100268260013505692287715197974824293602702048074200039989010466046954319001764702167525159391165221097412507207070941040169607617565907669448292394080513719952028379907211892278587213063509785161727181094780834140425449087027374354210627478929892809387327800956442381416648762382930744745836860691652645272468710801480127383690670796702340344827232853798294566232977982518551989524593975440927239406568783391313258506866750608077495352966704970278327215482373252538685185523964815393905211818152851498336930972438448603569283564012724941434639295494863634240132261738242762708931234148319337032370483580480928554288281017282842715728356865227629594590080908396457555253561758256890799884600635571737440212394730433411857064284860111226945575837832906205884951631607279348335031910003072824224574236747404904434087096197641226369055991560801425685762426000158519701843480002622016573514879915173451468691465801627597331478760735200706227052
14338839073210349887787514275814499181389923069109753825994309046402251
'''

n可以完全分解的

求出phi之后发现和e是不互素的，按照一般的思路e去掉(e, phi)，求d解出第一层；第二层e剩下$7^{11}$，而且现在(e, phi)=e，直接开方就不行了，有限域也直接把我sage跑挂了

先记下第一层的

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
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from gmpy2 import *
from Crypto.Util.number import *
from fractions import Fraction


def pre(limit):
    _primes = [2]
    while _primes[-1] < limit:
        _primes += [next_prime(_primes[-1])]
    return _primes


n = 11994856154408832550226173326306706948322784186267813285424273727457277570449721708469377333295795450316798985747411428007939478275824993378444272641075595828905331211398917692117185101479077398613046411577116685482608874046448872880344276808220924860769086887940958633441714352583855540999548720044322998264846012161431636662433683276562625027092028130005970114647137832180580174041968866569822387764690463959881397320450667236461741620403395599935845735617477280364151807003271533625363666352062617204207977554178272479567385510394164676984094113453536958667301026374275130979677305822214444335545662001110540052205079456125870487695548122936396959457217914532553325619253546791069692985512699358985463221502502084675209516472887973080192751916784600603877788797705458888760552581342959043655183973152680603248917128462709597030509958883674860205970644241146476304149515438669191043736965162506814748737378119531830170603146515955648287154128232624377713379199023238511614078806426562021069638546292232028008642595243475950555611966843590609370802372713922810842109296634261927855897749685466429848085401683729949137325841031448197225286597985926477607730381020542179177937190267395728321154320663113144417493792344192501728192224067408526468047697092815734745508911899235305415196605573552817031582341240841963500082141599736527564221706520431869455796746093434293683100803464504347573705307339278622142604231243731290546424726300181230919587809100360017180646300141932273203009540779621343752276406327270280696985946756857577522536182716290889259854732662916401670054957144740292721681742707739784073111634648716873018489059318376430379543710047917376490266767875239644497833040110744093598044604501318749065110017000755265530585848590714646543215789831321305186253110749828658194624302871154167229533880360661192631336611540590753329799514109722282049242508985274973975569128167197103339329219857542511675333185438424100205435264185442625212957816223665085393904833681032006083319868956112013073947804141313761890184012761243094669629438534487954505709858329677691050279420667276012005715403824771026942764503867179041742712964566104284721980020875049780798089586557353746689141977077518535458410939575796862938638716615803650407786897854972763793186411099146552957299304020322056573695947636353479929828321017230745880492761198924142557387134524722498789054500072958840330107186959238787198423202007480930533185363864760876539962555722806312411851288978109934860380767506470800563090423502953911794718800665163227148855219153379250626032923411536090260611564327090513624773651630139865213054047971676969921132075382597029378871818496911936273603167169708274436918974731159618512856370147955309970639864283488998194291564522716718108808644500794139567941894324821270494322487330771480736023069465090696594967014241811185428807158275522064429448212412679526940639213423056138417455582473816078505889037913398303842261835933581251153905467725831957314379762137644348555546053964035105996510374509932329977348336229876173135652873412359763033310447686419768148309532098091688546115562450592460242975433396729597685387307
c = 6351466082405672614085883295737944548919965310077599978190541984976106721260561511854691553565453868610374663116381728992690135579603964052096888436742489466374210302988977830209354260009636769071300547671488922280932487568494617872097079900945916095578623755388259234178268680612477377610914894710907496104362972636720911428089600646222586417255348258167381366988661303295347517753632411800607422746813905818666335896482669033027140915808983428842744482539062142710596639786508537317845758580996627882525064014450135034588736834794180287554486686075596972841883555087846775677701021701479352637748421102843822406248351476994277131337482690575095175009349909732516378330382964315421709620022837911961196685966020194554189215141758762297821318628808131301398323401698864010506849785816316875321330260285263314080063147494581040037600990836748077720670885523772728159627902311960453296092752330952130969249700776559562104117567236854526041303478039102747984668480082877982578911506991928425276445385557957750379045259124494960054574534424135407768648703579640630316936268243612044686186580389257001065198441757102217761322659630686894710273768219013265353821348563879078174064695595467864392947552655739896949699714908310000268044992892911329386425950830381092394869669909772028429264943114745575587790304248788515785473427021962255432027331143994772029825798100553275968616702208346511746136952846098000483881079268476334708733720366718979528049610330304650435684527462122705466063185641405473474636409990254433154961156119876528578589683787745161026307683732723150673756819990500536505419317277397641638885910418427679382912218056162106726030182041543254191389196695732924652812425467589000461451026805090543916784702340460053504268171601901665797607174213052404647848620139395976717777302984408101541424736063698589129484369980805581194717731469528976219054596456039278307705269184407577544084520370372269984748277291765285669123103849832742912650693589627527731652063314823281800811899078839130817382422516706798968876936676146422986085568876006217756879288536420625765537735876869140624480292479927568778211793082812927301155660252404197005435807632705417486828432680003527496336100268260013505692287715197974824293602702048074200039989010466046954319001764702167525159391165221097412507207070941040169607617565907669448292394080513719952028379907211892278587213063509785161727181094780834140425449087027374354210627478929892809387327800956442381416648762382930744745836860691652645272468710801480127383690670796702340344827232853798294566232977982518551989524593975440927239406568783391313258506866750608077495352966704970278327215482373252538685185523964815393905211818152851498336930972438448603569283564012724941434639295494863634240132261738242762708931234148319337032370483580480928554288281017282842715728356865227629594590080908396457555253561758256890799884600635571737440212394730433411857064284860111226945575837832906205884951631607279348335031910003072824224574236747404904434087096197641226369055991560801425685762426000158519701843480002622016573514879915173451468691465801627597331478760735200706227052
e = 14338839073210349887787514275814499181389923069109753825994309046402251
primes = pre(100)
q = int(next_prime(2 ** 128))
phi = Fraction(int(n), int(1))
for i in range(10):
    phi *= Fraction(int(q - 1), int(q))
    q = int(next_prime(q))
assert phi.denominator == 1
phi = phi.numerator
e2 = 1
while gcd(e, phi) != 1:
    ex = gcd(e, phi)
    e = e // ex
    e2 *= ex
# step1
d1 = invert(e, phi)
m1 = pow(c, d1, n)

有点像CRT凑模数，但是这道题不行，因为由m = bytes_to_long(flag + urandom((len_ >> 3) - len(flag)))这句话可知，flag的位数和n是很接近的，所以几乎可以说不能把n中任何一个factor去掉

以下是n的完全分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# step2
e = 7 ** 11
c = m1
n_exponent = []
n_factor = []
nn = n
q = next_prime(2 ** 128)
for i in range(10):
    tot = 0
    # if gcd(q - 1, 7) != 1:
        # n_exponent.append(tot)
    # else:
    while gcd(nn, q) != 1:
        tot += 1
        nn = nn // q
    n_exponent.append(tot)
    n_factor.append(int(q))
    print('{0}^{1}'.format(q, tot), end='×')
    q = next_prime(q)
print(1)
# n = reduce(lambda x, y: x * y, [n_factor[i] ** n_exponent[i] for i in range(len(n_factor))])

340282366920938463463374607431768211507^2×340282366920938463463374607431768211537^13×340282366920938463463374607431768211621^13×340282366920938463463374607431768211729^11×340282366920938463463374607431768211841^7×340282366920938463463374607431768211877^7×340282366920938463463374607431768211919^11×340282366920938463463374607431768212029^2×340282366920938463463374607431768212081^2×340282366920938463463374607431768212213^13×1

$e|(p-1),e|(q-1)$

1
2
3
n = 11994856154408832550226173326306706948322784186267813285424273727457277570449721708469377333295795450316798985747411428007939478275824993378444272641075595828905331211398917692117185101479077398613046411577116685482608874046448872880344276808220924860769086887940958633441714352583855540999548720044322998264846012161431636662433683276562625027092028130005970114647137832180580174041968866569822387764690463959881397320450667236461741620403395599935845735617477280364151807003271533625363666352062617204207977554178272479567385510394164676984094113453536958667301026374275130979677305822214444335545662001110540052205079456125870487695548122936396959457217914532553325619253546791069692985512699358985463221502502084675209516472887973080192751916784600603877788797705458888760552581342959043655183973152680603248917128462709597030509958883674860205970644241146476304149515438669191043736965162506814748737378119531830170603146515955648287154128232624377713379199023238511614078806426562021069638546292232028008642595243475950555611966843590609370802372713922810842109296634261927855897749685466429848085401683729949137325841031448197225286597985926477607730381020542179177937190267395728321154320663113144417493792344192501728192224067408526468047697092815734745508911899235305415196605573552817031582341240841963500082141599736527564221706520431869455796746093434293683100803464504347573705307339278622142604231243731290546424726300181230919587809100360017180646300141932273203009540779621343752276406327270280696985946756857577522536182716290889259854732662916401670054957144740292721681742707739784073111634648716873018489059318376430379543710047917376490266767875239644497833040110744093598044604501318749065110017000755265530585848590714646543215789831321305186253110749828658194624302871154167229533880360661192631336611540590753329799514109722282049242508985274973975569128167197103339329219857542511675333185438424100205435264185442625212957816223665085393904833681032006083319868956112013073947804141313761890184012761243094669629438534487954505709858329677691050279420667276012005715403824771026942764503867179041742712964566104284721980020875049780798089586557353746689141977077518535458410939575796862938638716615803650407786897854972763793186411099146552957299304020322056573695947636353479929828321017230745880492761198924142557387134524722498789054500072958840330107186959238787198423202007480930533185363864760876539962555722806312411851288978109934860380767506470800563090423502953911794718800665163227148855219153379250626032923411536090260611564327090513624773651630139865213054047971676969921132075382597029378871818496911936273603167169708274436918974731159618512856370147955309970639864283488998194291564522716718108808644500794139567941894324821270494322487330771480736023069465090696594967014241811185428807158275522064429448212412679526940639213423056138417455582473816078505889037913398303842261835933581251153905467725831957314379762137644348555546053964035105996510374509932329977348336229876173135652873412359763033310447686419768148309532098091688546115562450592460242975433396729597685387307
c = 6351466082405672614085883295737944548919965310077599978190541984976106721260561511854691553565453868610374663116381728992690135579603964052096888436742489466374210302988977830209354260009636769071300547671488922280932487568494617872097079900945916095578623755388259234178268680612477377610914894710907496104362972636720911428089600646222586417255348258167381366988661303295347517753632411800607422746813905818666335896482669033027140915808983428842744482539062142710596639786508537317845758580996627882525064014450135034588736834794180287554486686075596972841883555087846775677701021701479352637748421102843822406248351476994277131337482690575095175009349909732516378330382964315421709620022837911961196685966020194554189215141758762297821318628808131301398323401698864010506849785816316875321330260285263314080063147494581040037600990836748077720670885523772728159627902311960453296092752330952130969249700776559562104117567236854526041303478039102747984668480082877982578911506991928425276445385557957750379045259124494960054574534424135407768648703579640630316936268243612044686186580389257001065198441757102217761322659630686894710273768219013265353821348563879078174064695595467864392947552655739896949699714908310000268044992892911329386425950830381092394869669909772028429264943114745575587790304248788515785473427021962255432027331143994772029825798100553275968616702208346511746136952846098000483881079268476334708733720366718979528049610330304650435684527462122705466063185641405473474636409990254433154961156119876528578589683787745161026307683732723150673756819990500536505419317277397641638885910418427679382912218056162106726030182041543254191389196695732924652812425467589000461451026805090543916784702340460053504268171601901665797607174213052404647848620139395976717777302984408101541424736063698589129484369980805581194717731469528976219054596456039278307705269184407577544084520370372269984748277291765285669123103849832742912650693589627527731652063314823281800811899078839130817382422516706798968876936676146422986085568876006217756879288536420625765537735876869140624480292479927568778211793082812927301155660252404197005435807632705417486828432680003527496336100268260013505692287715197974824293602702048074200039989010466046954319001764702167525159391165221097412507207070941040169607617565907669448292394080513719952028379907211892278587213063509785161727181094780834140425449087027374354210627478929892809387327800956442381416648762382930744745836860691652645272468710801480127383690670796702340344827232853798294566232977982518551989524593975440927239406568783391313258506866750608077495352966704970278327215482373252538685185523964815393905211818152851498336930972438448603569283564012724941434639295494863634240132261738242762708931234148319337032370483580480928554288281017282842715728356865227629594590080908396457555253561758256890799884600635571737440212394730433411857064284860111226945575837832906205884951631607279348335031910003072824224574236747404904434087096197641226369055991560801425685762426000158519701843480002622016573514879915173451468691465801627597331478760735200706227052
e = 14338839073210349887787514275814499181389923069109753825994309046402251

$n$由128位的连续素数的随机次幂相乘而得，$e$由小素数的随机次幂相乘而得，根据题目代码两者都能够被完全分解

分解出来把$e$的不互素因子去掉后，$e=7^{11}$，会发现$gcd(e,\ \varphi(n))=47$

有限域开方数应该会很慢，也不是$e|(p_i-1)$

从网上搜来的做法，参考https://paste.factorcode.org/paste?id=4236

先是根据拓展欧几里得算出$a,b,g$
$$
ae+b\varphi(n)=g\notag
$$
计算
$$
c_1\equiv c^a\ (mod\ n)\notag
$$
再遍历每一个因子幂后的结果，在模该因子下开49次方，最后再crt遍历一下结果

很神奇，之前一直是把$e$的公因子完整消掉，这里也提供了一种新的思路

image-20220523194913828

困难一点点的数学0_Revenge（not solve）

这道题在上一题的基础上，改了下pre和参数，没啥思路

第六届中国海洋大学信息安全竞赛

easyRSA

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
from Crypto.Util.number import *
from gmpy2 import *
from secret import *

assert flag.startswith(b'flag')

while 1:
    hint = getPrime(1024)
    b = getPrime(200)
    p = getPrime(512)
    q = hint * b * p + 2
    if isPrime(q):
        break

n = p * q
e = 64
m = bytes_to_long(flag)
c = pow(m, e, n)

print(n)
print(c)
print(hint)
'''
9057141637995599750120273501711128117576789048411357158233050845658505488383724832915968443730006384810721595601723748471745315354759415044859624198755098491311647992728384572103262800310263916249536898582100747311978019829291619921741682336800665277699122504431456051606407509905004993708771825443764723285750825546500765451509998514747599779552241055519485714649825416851221219747115910385536482995890893190128149999622905611239433481756073333147782531765685320972075370276543786386451560493093416152466142374684450770169257924330366774896526508005296520372463932722237001341584625279676089901419404816917142209281664709940400762785892142918132066900664643155176180059403739
6154079784140816887542685430803768415772730865151861643444097840023705832386679112482482248555761414705162328220586794375708796741624024822642170217210511028105715354610593613478964243640521028593911375212807872252055918567650066306345785341153202754138305812184867107836136289838379556395327458734454660336699800924390962557002402007091633450515772419925142945911576659151187043837460255245980821089671602664201100487652703989786977247616381447061677369391575649093177311422333653297000175353974295682284617873674552426804866371781198162476631361431011867016121352914491629749793369865802944046427625798032718230196065884706861662254100563745138198499719367503185424667724305
99336867941885596246249572957476249207783802547583614060828305903417094663626785107521682819540923350225137906529404247068926777322082579296175450572566483806852214547909169221325677351559413990125595962992773728902865500358652248335066478896252289023954431595375774635699658560226625953577281314982639316733
'''

这里一开始我以为是一条性质理解不了，关于整除的

由题目可知
$$
q=hint\times b\times p+2\notag
$$
那么我们容易得到
$$
n=p\times q=hint\times b\times p^2+2p\notag
$$
两边除以hint取整
$$
\lfloor n/hint\rfloor=b\times p^2+\lfloor 2p/hint\rfloor=b\times p^2+0\notag
$$
嗯对，这里不是很懂了，整数看习惯了，对于小数有点麻了，但是通过这个，之后求p和q就简单了

正确的理解应该是，这并不是一条所谓性质，随便搞了几个数字就知道不对；这里的解释只能说hint和p相差太大了吧，然后只能组成$n/hint$的小数部分，所以整数部分还是完全由$b\times p^2$决定的

一部分代码如下

1
2
3
4
5
6
7
8
9
e = 64
n = 9057141637995599750120273501711128117576789048411357158233050845658505488383724832915968443730006384810721595601723748471745315354759415044859624198755098491311647992728384572103262800310263916249536898582100747311978019829291619921741682336800665277699122504431456051606407509905004993708771825443764723285750825546500765451509998514747599779552241055519485714649825416851221219747115910385536482995890893190128149999622905611239433481756073333147782531765685320972075370276543786386451560493093416152466142374684450770169257924330366774896526508005296520372463932722237001341584625279676089901419404816917142209281664709940400762785892142918132066900664643155176180059403739
c = 6154079784140816887542685430803768415772730865151861643444097840023705832386679112482482248555761414705162328220586794375708796741624024822642170217210511028105715354610593613478964243640521028593911375212807872252055918567650066306345785341153202754138305812184867107836136289838379556395327458734454660336699800924390962557002402007091633450515772419925142945911576659151187043837460255245980821089671602664201100487652703989786977247616381447061677369391575649093177311422333653297000175353974295682284617873674552426804866371781198162476631361431011867016121352914491629749793369865802944046427625798032718230196065884706861662254100563745138198499719367503185424667724305
hint = 99336867941885596246249572957476249207783802547583614060828305903417094663626785107521682819540923350225137906529404247068926777322082579296175450572566483806852214547909169221325677351559413990125595962992773728902865500358652248335066478896252289023954431595375774635699658560226625953577281314982639316733

bp2 = n // hint
p = (n-hint*bp2) // 2
q = hint*bp2//p + 2
assert p*q == n

然后又是e是偶数的情况，不过显然没有前面遇到的那么容易和有现成的wp

Rabin

我的思路是多用了几个e=2的Rabin攻击，但感觉不对

借la师傅的脚本写了一下

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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import gmpy2
from Crypto.Util.number import *
import sys

n = 9057141637995599750120273501711128117576789048411357158233050845658505488383724832915968443730006384810721595601723748471745315354759415044859624198755098491311647992728384572103262800310263916249536898582100747311978019829291619921741682336800665277699122504431456051606407509905004993708771825443764723285750825546500765451509998514747599779552241055519485714649825416851221219747115910385536482995890893190128149999622905611239433481756073333147782531765685320972075370276543786386451560493093416152466142374684450770169257924330366774896526508005296520372463932722237001341584625279676089901419404816917142209281664709940400762785892142918132066900664643155176180059403739
c = 6154079784140816887542685430803768415772730865151861643444097840023705832386679112482482248555761414705162328220586794375708796741624024822642170217210511028105715354610593613478964243640521028593911375212807872252055918567650066306345785341153202754138305812184867107836136289838379556395327458734454660336699800924390962557002402007091633450515772419925142945911576659151187043837460255245980821089671602664201100487652703989786977247616381447061677369391575649093177311422333653297000175353974295682284617873674552426804866371781198162476631361431011867016121352914491629749793369865802944046427625798032718230196065884706861662254100563745138198499719367503185424667724305
hint = 99336867941885596246249572957476249207783802547583614060828305903417094663626785107521682819540923350225137906529404247068926777322082579296175450572566483806852214547909169221325677351559413990125595962992773728902865500358652248335066478896252289023954431595375774635699658560226625953577281314982639316733

bp2 = n // hint
p = (n-hint*bp2) // 2
q = hint*bp2//p + 2
assert p*q == n


def rabin_decrypt(C, P, Q, e=2):
    N = P * Q
    mp = pow(C, (p + 1) // 4, p)
    mq = pow(C, (q + 1) // 4, q)
    yp = gmpy2.invert(P, Q)
    yq = gmpy2.invert(Q, P)
    r = (yp * P * mq + yq * Q * mp) % N
    rr = N - r
    s = (yp * P * mq - yq * Q * mp) % N
    ss = N - s
    return r, rr, s, ss


x = 0
m32 = rabin_decrypt(c, p, q)
c16 = m32
for ct1 in c16:
    m16 = rabin_decrypt(ct1, p, q)
    c8 = m16
    for ct2 in c8:
        m8 = rabin_decrypt(ct2, p, q)
        c4 = m8
        for ct3 in c4:
            m4 = rabin_decrypt(ct3, p, q)
            c2 = m4
            for ct4 in c2:
                m2 = rabin_decrypt(ct4, p, q)
                c0 = m2
                for ct5 in c0:
                    m = rabin_decrypt(ct5, p, q)
                    for i in range(4):
                        print(long_to_bytes(m[i]))
                        x += 1
                        print(x)

有限域开方

问了Striving师傅，师傅给的思路：一是肯定了之前的思路（六次Rabin），二抛出一个新的概念“有限域开方”，并给了一个sage脚本，之前iscc的，改下数据

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
from Crypto.Util.number import  *

p = 9379687248080546498203772982837534815766954373570511486116083159981413417096645798856014966365034522452474187942388010149804818006063740815276649712799481
q = 965612327836309010640336991047433695556810179336511247528907945718618156107162848744574747053330490898357406242669343584421656178908998516241378530330570381491082968636749226112679273570797410328924840246087961289024973946055035418636926676076633496570175998461069029639169285927893363926033338135217150878112745316881927877175031909168645360203144573306218025903594105264560446428458045534270979754915646333544338288343648100774469601136673371680101712576187426590347035135361532767157406425958991578025201218590389525619
n = 9057141637995599750120273501711128117576789048411357158233050845658505488383724832915968443730006384810721595601723748471745315354759415044859624198755098491311647992728384572103262800310263916249536898582100747311978019829291619921741682336800665277699122504431456051606407509905004993708771825443764723285750825546500765451509998514747599779552241055519485714649825416851221219747115910385536482995890893190128149999622905611239433481756073333147782531765685320972075370276543786386451560493093416152466142374684450770169257924330366774896526508005296520372463932722237001341584625279676089901419404816917142209281664709940400762785892142918132066900664643155176180059403739
c = 6154079784140816887542685430803768415772730865151861643444097840023705832386679112482482248555761414705162328220586794375708796741624024822642170217210511028105715354610593613478964243640521028593911375212807872252055918567650066306345785341153202754138305812184867107836136289838379556395327458734454660336699800924390962557002402007091633450515772419925142945911576659151187043837460255245980821089671602664201100487652703989786977247616381447061677369391575649093177311422333653297000175353974295682284617873674552426804866371781198162476631361431011867016121352914491629749793369865802944046427625798032718230196065884706861662254100563745138198499719367503185424667724305
e= 16


R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()


R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()
m=[]
for i in res1:
    for j in res2:
        m.append(CRT(int(i[0]),int(j[0]),p,q))
e = 4

for C in m:
    R.<x> = Zmod(p)[]
    f = x ^ e - C
    f = f.monic()
    res1 = f.roots()


    R.<x> = Zmod(q)[]
    f = x ^e - C
    f = f.monic()
    res2 = f.roots()

    for i in res1:
        for j in res2:
            M=CRT(int(i[0]),int(j[0]),p,q)
            if long_to_bytes(M).startswith(b'flag'):
                print(long_to_bytes(M))

跑了十分钟终于出来了，好耶

easyRSA-75ae2c4a.png

Cipolla’s Algorithm $p,q\ \equiv1\ (mod\ 4)$

然后返回去复现Rabin的解法，经老师提醒Rabin一般是适用p和q同模4余3（这就是我直接用Rabin写脚本出来不的原因之一吧），但是不满足该条件的网上也有相应的解法

easyRSA-34686019.png

可以直接调sympy库

1
from sympy.ntheory.residue_ntheory import nthroot_modnthroot_mod(c, 2, n)

附上参考链接，https://xz.aliyun.com/t/5113

classical

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
p, q = getPrime(1024), getPrime(1024)
n = p * qe = 0x20002
m = bytes_to_long(flag)
c = pow(m, e, n)
print(n)
print(p^q)
print(c)
'''
14115093155264548284219850276976713894807135646407433952606241177170799620857407025703595509713850915829780548758828322672641152301034211705379026175072611331218908815311430949772272235565783721577000028261320417622996465873828778859895581557742322809089668839711806730037111219021594672886924179920040304097577013490236209729345268062386894230525646920709722753359165796352375582302187897324275077401465001693214034438313030500915688714866020374786738034712789705863769144687851817416283898692607558884892344860918856284384348045176373311592185711275374531053648357885260032561469921168991006893123688018793232724519
49718812286149241460257842584860093467814450098109752753313290896314226758583527714071510565085142777634579897580985904271580830999001072858071394478220167786258612467372600494251840440664134201847287229508941893691039239231768122659124710796291531043744564781384919249602079669571540916106577516894331515942
9953949741013869942547068198121837302318253723877106218866850569125612168124953507720549935440414456694849794070623435967826780140286915427474882462420987431026322506726433159619207457167288303630066313113554335142157973136384138957974141794821690882492289219381289736054817877583941375031278015108767863108668566479010711087436814686693513769053008124914798460553425393111487695972525254979562410234110752805380574182432866694020891030485921135474591933136062338390086730078396980498629461268411340424502744686773297853639711048789055056501585346987725433868282476192206326121122527472482411928363635793163788685739
'''

代码很简单，就把p和q异或了一下。初次拿到手没啥思路，问了下出题的师傅说是dfs。解法如下，先是需要推出以下两条结论

结论1：在任意进制下，m位的数乘以n位的数，其结果的位数$\in[m+n-1,m+n]$。

结论2：在任意进制下，k=m*n，则k的低x位等于m的低x位乘以n的低x位的低x位。

结论2的不严格证明如下

以十进制为例，两位数乘法$ab\times cd$可以写成$(10a+b)\times(10c+d)=100ac+10(ad+cb)+bd$，三位数乘法$eab\times fcb$可以写成

$(100e+10a+b)\times(100f+10c+d)=10000ef+1000(ec+af)+100(ac+ed+bf)+10(ad+cb)+bd$

其低两位仅有$10(ad+cb)+bd$决定。

很直接的想法，由低到高逐位爆破。已知异或的结果，每位只有两种情况，即异或结果为0，则pq对应位置不是00就是11，结果为1，不是01就是10。可以通过n来判断是哪种情况，但实际上应用结论2对于n的筛选能力有限，即存在前面一大串比特位都满足异或与结论2，但到下一位就不行了，需要有类似回滚的机制。而深度搜索的核心思想就是，当不能再继续向下访问时，依次退回到最近被访问的点。于是要解出本题就只需要解决下面两个问题

如何退回：用列表保存上一次的所有路径。

如何判断能否继续往下访问：在判断第b位时，如果当前p乘以q的低b位等于n的低b位，则能继续往下访问，否则不能。

手动模拟结果如下

dfs1

即

dfs2

每次最多有4种可能，然后通过判断机制，可以削去1/4或1/2或3/4，这使得时间复杂度不会呈指数级上升，程序能够正常运行。

最后0x20002显然是0x10001的两倍，用平方根公式和Cipolla’s algorithm求解二次同余方程。

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
from Crypto.Util.number import long_to_bytes
from exploit.rsa.CipollaAlgorithm import Cipolla_algorithm
from sage import crt
from gmpy2 import invert

n = 14115093155264548284219850276976713894807135646407433952606241177170799620857407025703595509713850915829780548758828322672641152301034211705379026175072611331218908815311430949772272235565783721577000028261320417622996465873828778859895581557742322809089668839711806730037111219021594672886924179920040304097577013490236209729345268062386894230525646920709722753359165796352375582302187897324275077401465001693214034438313030500915688714866020374786738034712789705863769144687851817416283898692607558884892344860918856284384348045176373311592185711275374531053648357885260032561469921168991006893123688018793232724519
x = 49718812286149241460257842584860093467814450098109752753313290896314226758583527714071510565085142777634579897580985904271580830999001072858071394478220167786258612467372600494251840440664134201847287229508941893691039239231768122659124710796291531043744564781384919249602079669571540916106577516894331515942

def YiBaSuo(p, q):
    e = 0x10001
    c = 9953949741013869942547068198121837302318253723877106218866850569125612168124953507720549935440414456694849794070623435967826780140286915427474882462420987431026322506726433159619207457167288303630066313113554335142157973136384138957974141794821690882492289219381289736054817877583941375031278015108767863108668566479010711087436814686693513769053008124914798460553425393111487695972525254979562410234110752805380574182432866694020891030485921135474591933136062338390086730078396980498629461268411340424502744686773297853639711048789055056501585346987725433868282476192206326121122527472482411928363635793163788685739
    d = invert(e, n - p - q + 1)
    c = pow(c, d, n)
    # e = 2
    assert p % 4 == 1
    assert q % 4 == 3
    q1 = pow(c, (q + 1) // 4, q)
    q2 = q - q1
    p1 = Cipolla_algorithm(p, c)
    p2 = p - p1

    print(long_to_bytes(crt([p1, q1], [p, q])))
    print(long_to_bytes(crt([p1, q2], [p, q])))
    print(long_to_bytes(crt([p2, q1], [p, q])))
    print(long_to_bytes(crt([p2, q2], [p, q])))

candidate = [(0, 0)]
for b in range(1024):
    criteria = (2 << b) - 1
    candidateForCandidate, candidate = candidate, []
    for p, q in candidateForCandidate:
        for i in range(2):
            for j in range(2):
                xx = p + (i << b)
                yy = q + (j << b)
                if (xx ^ yy) & criteria != x & criteria:
                    continue
                if n & criteria != xx * yy & criteria:
                    continue
                # 去掉诸如已经有(1,3)就不添加(3,1)的路径
                if (yy, xx) not in candidate and (xx, yy) not in candidate:
                    candidate.append((xx, yy))
for p, q in candidate:
    if p * q == n:
        YiBaSuo(p, q)
        break
# b'cne\x1f\xbbZc\xfb0"$\xcfR\xa8\xe1\t`FN\x1c\x1bd\xf9\xaa\x18\xe1\x81q\x1eRg\x10\x9b\x109\xcb:q\'\xdb\x9a`\xce\xdePjO%\x82\x17\xcf\r2\xa9\x02\x0e\x11-Gn$\xb3\\\x18\xd3M\xc4&.\xd6h t7\xe1\x9f\'\xa9\x1b<}\xce0\x9eM\xf4s\x80\xf7\x7f,\xb9_y\\I~\x07;}!:\xb9\xe6\xb5\xbb\xe2\x9fO\xdb\xfeO7\x13\x87\x16rQ\xcb\xf8\xa3\xe6\xae\x97\r"\xa6S\x9c\x84\x97\xbd\xaa\x9c?\x15\xd8\x1f\xbe\x7f\xdfR\xdb\x92\x16\xdb\xbd\xa0,r{\x14\x1fW\x04$\xe0\xd1^kb.\x07#\xe5\xe5c\x05\x13\xc2\xbe\x92\xa7\xd8\xafu\xb5\xef\xd7\xf9\xffI\xec\x95*^\xf6\xb7\xc6\xb8\xe1\xb5\xd6:\xc3 \x90w{\x86\x82\x02\xa6{S\x87en|\x9c\x84N\xce\xe4\xab\x92\xc0f\x0f\xce\xb75:\xab\x98\xc4\xba&\x94]A\xdc\xb5M\x06\xe0=H\n\xd0\xea*\x82s\xe1\xe0h\xa6~i\xef\x8c3\x8c\x1ak'
# b'o\xd0%\xbbk\xdf\x9b\xbb\xbb\xd3\x95\xe4op_8Y\x02x\x05\xc0\xe14T\xc81\xce\xad;\xb5\xba\xcc\x7f5+\x05\xe6\xfa\xa8-T\xac+\xaa\xf7\xf20\xb6\xc2 \x10\x07\xc1K=\x0cT\x12\xb1\n\xa6\xbe\xaf\xe1<\x95\x12f\xda+\xd4W\x87\x80c\xa2\xd9:\xaa\xfc\xf7z\x17\xc1ah2r\\\xa2RO\x1b\x19\x9a\xc8nr\x1d\xdb\xdb\xbf3\xb2}\xddh\xdf\x86\xfa\xb5\xfdn{\x96%\x11\\\xeb \xd2\xf9\x05\x07NA\x0f#\x1b\xa3tn\xa5 \xe9\x8c\xe5\t"\xa6\xb2mb\xb9y\xb5S\x08^H\x06\xb3_\xea\xdaL\xbd\xeb\xad*\xc0\xc6S\n\x96@\xbb\x9bL\xcf)\xbe\xce\xfb\xc1\xe9h\x19En\x01\x05\x94\xda{\x11\x0e[\tB\x1d\xd8\xe9\'\xed\x12\xbc)\x19\x1c\xd94\x1ae\x01\x18?\x9c\x85\xf1\t\xdfu\t\xfb\x84}^`AW\x0e\xb2U\x99u\x8a\xd7\x83\xf0b\x10>g\xaa\xb8\xcd\x91f\x05\xd8:\xe1\xa3bC\xef\xc0!*\xbcy\xe9+\x8c\xaa'
# b'flag{this_is_A_fake_flag_false_one}'
# b"\x0ca\xc0\x9b\xb0\x857\xc0\x8b\xb1q\x15\x1c\xc7~.\xf8\xbc)\xe9\xa5|:\xaa\xafPM<\x1dcS\xbb\xe4$\xf1:\xac\x89\x80Q\xbaK\\\xcc\xa7\x87\xe1\x91@\x08@\xfa\x8e\xa2:\xfeB\xe5i\x9c\x82\x0bS\xc8iGN@\xabUl7\x13H\x82\x03\xb1\x91\x8f\xc0y\xab\xe7#\x13s\xbe\xf1e#%\x95\xbb\xa0>~\xf0j\xe2^\xba\x84y\xcb\xc8!\x86@7\x1e\xb7\xae7h\x0f\x0e\x9f\x0b\x1f(/\x12VpA\x1eh\xcf\x7f\x1e\xdc\xb0\xfa\x84\xaaw\x0c\xe9d&\xd3\x1a\x87'b\xd9\x95h1\xd5\x8b\x9f@\x93\xd6'\xdd\x1aN\xbf^\x98K\xe6\xb0[X\x969\x0ck,'#\x12s\xb2)mt\x01\xbb\xa8EP\xb2\x17\xa3B\x89<#\x12\xed)\xf2+\xb1\x9d\x96W1s\xe9\xad\x90\xda.\tT\x85\x90\xa6%O\xf1\xbc\xf8Pr\xa0?\xe4\x0bh,E\x19Y\x06\x7f\x9c\xfcy\xe57\xf6\xaa\xc6\x9aMv\xcb\x90\xe7\xc2\xed{\x0f42M%\r\xd7\xbc"