[数据结构与算法] 【20210903 Blue-Whale2021 Freshers&第六届中国海洋大学信息安全竞赛】Crypto方向WP

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【20210903 Blue-Whale2021 Freshers&第六届中国海洋大学信息安全竞赛】Crypto方向WP -> 正文阅读

[数据结构与算法]【20210903 Blue-Whale2021 Freshers&第六届中国海洋大学信息安全竞赛】Crypto方向WP

芜湖，不是吧，不会有人鸽了两三个月才来复现结果误闯人家新生赛了吧

yyd萌新

文章目录

CheckIn

aW9kantaaG9mcnBoX3dyX0Zsc2todVZzZGZoIX0=

base64 $\rightarrow$ Caesar 3

flag{Welcome_to_CipherSpace!}

baby_OTP

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

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

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

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

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进制表示，大小写无关

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

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]

# 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

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
'''

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

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)))

sage是我自己上密码学课自己写的库，想要实现一些sage里常用的函数

flag{212333333333333333333333333333333333333333333333333333333333}

不过话说离散对数在 $Z^*_n$ 下简单是真的吗

baby_RSA

#!/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（unsolved）

#!/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佬的脚本，方便日后行动

稍作修改

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稍微大点，就要利用同余等式去枚举

怎么会有这么不要脸的东西

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

RSA2

#!/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一把梭

#!/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}

emmmm费马分解，打扰了

RSA3

#!/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]
'''

选择明文攻击（bushi）先获得n， Pollard’s kangaroo光滑的袋鼠（bushi）得到e，n好可以分解

#!/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开着，好评

emmmmm总感觉哪里不对

nc 39.106.29.44 10106

好在题目是正确的

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

第一次因为窗口的原因，显示少了，解出来的flag不对，所以我都用脚本实现最后send过去。然后发现是wt的窗口显示少了，不过好在这道题用到的理论储备并没有出大问题

#!/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}

FuckPython-RSA2（unsolved）

端口给的和FuckPython-RSA1是一样的，不知道要干嘛，用FuckPython-RSA1的flag提交也不对

简单的数学0

#!/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
'''

不是RSA已知c，p，e的题型，p不知道

虽然确实有个oracle检验我们的flag是否是正确的，但是不知道p我没什么思路

第二天附件更新，给了p，我就说哈哈哈

c = 8803822563647270623115855698498072941389567371514602911761887238000858306724820208054957805578533078861661091923759508072298768127983369027700000415655223
p = 12913561406317113183635547158985401377756429238562558559079682073564209000830793328430323950547190141901547099900430790186447107756095983956460182437021627

直接用平方根了

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

#!/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
'''

#!/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（unsolved）

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的随机数不知道，但是可以用欧拉函数的通式绕过，配上Python的Fraction库，行家啊（其实n可以完全分解的）

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

先记下第一层的

#!/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的完全分解吧，也暂时不知道从何下手

# 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

好了，做完发现才没有上次的题目，结果误闯别人萌新赛了，密码题还是挺有实在的，只是希望他们不要打我

easyRSA

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

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

一部分代码如下

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师傅的脚本写了一下

#!/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师傅，师傅给的思路如下：
一是ta肯定了我之前的思路（六次Rabin），二抛出一个新的概念“有限域开方”，并给了一个sage脚本，之前iscc的，改下数据

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))

虽然跑了十分钟吧，但终归是出来了，好耶

flag{congratss_to_uooo}

Rabin $p,q\ \equiv1\ (mod\ 4)$

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

下面就是重点了，关于平方根算法的

简单来说一句话

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

深入了解还是去看论文吧，虽然这个链接https://xz.aliyun.com/t/5113上有现成的脚本

classical（unsolved）

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

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x20002
m = bytes_to_long(flag)
c = pow(m, e, n)

print(n)
print(p^q)
print(c)

'''
14115093155264548284219850276976713894807135646407433952606241177170799620857407025703595509713850915829780548758828322672641152301034211705379026175072611331218908815311430949772272235565783721577000028261320417622996465873828778859895581557742322809089668839711806730037111219021594672886924179920040304097577013490236209729345268062386894230525646920709722753359165796352375582302187897324275077401465001693214034438313030500915688714866020374786738034712789705863769144687851817416283898692607558884892344860918856284384348045176373311592185711275374531053648357885260032561469921168991006893123688018793232724519
49718812286149241460257842584860093467814450098109752753313290896314226758583527714071510565085142777634579897580985904271580830999001072858071394478220167786258612467372600494251840440664134201847287229508941893691039239231768122659124710796291531043744564781384919249602079669571540916106577516894331515942
9953949741013869942547068198121837302318253723877106218866850569125612168124953507720549935440414456694849794070623435967826780140286915427474882462420987431026322506726433159619207457167288303630066313113554335142157973136384138957974141794821690882492289219381289736054817877583941375031278015108767863108668566479010711087436814686693513769053008124914798460553425393111487695972525254979562410234110752805380574182432866694020891030485921135474591933136062338390086730078396980498629461268411340424502744686773297853639711048789055056501585346987725433868282476192206326121122527472482411928363635793163788685739
'''