crypto的挨打之路（一） | T5uppari = 蒟蒻的入土史

学 pwn 有点学不明白了，先来 crypto 放松一下。

2022.3.9 一不小心放松成主方向了，每 20 题换一篇写

一些收藏：
CyberChef 解决多重加密的
维吉尼亚密码爆破维吉尼亚密码爆破密钥
quipqiup 快速自动密码解算器

~~因为不会置顶只有改时间的屑 4.11~~

# 0x14 2022Securinets CTF Quals 2022 AES-2 4.11

该坑的最后一题（21.9.12-22.4.11）

这题着实是让人眼前一亮，附件

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os, sys, hashlib, random

FLAG = b"Securinets{REDACTED}"

key, iv1, iv2 = [os.urandom(16) for _ in range(3)]

def xor(a, b):
	return bytes(i ^ j for i, j in zip(a, b))

def get_token(msg, iv1, iv2):
	if len(msg) % 16 != 0:
		msg = pad(msg, 16)
	aes = AES.new(key, AES.MODE_ECB)
	blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]
	enc = b""
	tmp1 = iv1
	tmp2 = iv2
	for block in blocks:
		tmp = aes.encrypt(xor(block, tmp1))
		_tmp = aes.encrypt(xor(tmp, tmp2))
		enc += _tmp
		tmp1 = _tmp
		tmp2 = tmp
	return enc

def proof(msg):
	res = b"\x00"*16
	for i in range(0, len(msg), 16):
		res = xor(res, msg[i:i+16])
	return hashlib.sha256(res).digest()


if __name__ == "__main__":
	alice_username = os.urandom(32)
	alice_token = get_token(alice_username, iv1, iv2)
	print(f"Alice's creds : {alice_username.hex()} -> {alice_token.hex()}\n")

	while True:
		try:
			username = bytes.fromhex(input("Username : "))
			token = get_token(username, iv1, iv2)
			print(f"Your creds : {username.hex()} -> {token.hex()}")

			if proof(token) == proof(alice_token):
				if token == alice_token:
					print(f"You are not Alice!")
					sys.exit()
				else:
					print(f"Hey Alice! Here is your flag {FLAG}")
					sys.exit()	
			else:
				print("Try again!\n")
		except Exception as e:
			print(e)
			print("Invalid input.\n")

作图描述一下这个过程

msg 是 username，enc 是 get_token 之后的结果。msg 由自己控制，得到的 enc 会给出。目的是需要构造一个 msg 使两次 AES 加密之后得到的 enc 能满足 proof 之后是一样的。而 proof 读源码一看就能理解就是所有 enc 分块再异或。如果直接输入原有 Alice 的 msg，得到的 token 是和 alice_token 一样无法满足条件，目的是 proof 之后一样但是本身不等于。

相当于就是构造一个假的 token 能过 proof。deebato👴太强了，思路是 dbt👴的，因为每次试错会给回显，再一个就是，如果能控制得到 enc3 和 enc4 满足 enc3^enc4=0，也能过 proof。所以问题就在如何构造 msg3 和 msg4。先把变量写进图中

由于 AES 的 key 和 iv1、iv2 是未知的不可控，msg 是自个输入的，要控制让 enc3 和 enc4 相等，就是有

$(msg2\oplus enc1)^{AES}\oplus (msg3\oplus enc2)^{AES} == (msg3\oplus enc2)^{AES} \oplus (msg4 \oplus enc3)^{AES}$

其中 msg3 和 msg4 是可控的，msg1、msg2、enc1、enc2 已知。

显而易见只要满足 $msg4=enc1\oplus enc3\oplus msg2$ 等式即可成立，exp 如下 (其中我令 $msg3=enc2 \oplus enc1\oplus msg2$ ，其实大可不必)

from pwn import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
import hashlib
from functools import reduce
def hex_xor(s1,s2):
    bytes_s1 = bytes.fromhex(s1)
    bytes_s2 = bytes.fromhex(s2)
    return xor(bytes_s1,bytes_s2).hex()
# context(log_level = 'debug')
r = remote('20.233.7.174',4870)
r.recvuntil(b'Alice\'s creds : ')
line = r.recvline()[:-1].decode()
msg = [line[:32],line[32:64]]
enc = [line[-64:-32],line[-32:]]
alice_user = line[:64]
print(line)
print(msg)
print(enc)
tmp = reduce(hex_xor,[msg[1],enc[0],enc[1]])
alice_user += tmp
r.recvuntil(b'Username :')
r.sendline(alice_user.encode())
r.recvuntil(b'Your creds : ')
line = r.recvline()[:-1].decode()
msg.append(line[64:96])
enc.append(line[-32:])
tmp = reduce(hex_xor,[enc[0],enc[2],msg[1]])
alice_user += tmp
r.recvuntil(b'Username :')
r.sendline(alice_user.encode())
r.recvuntil(b'Hey Alice!')
print(r.recvline())
r.interactive()

# 0x13 2022Securinets CTF Quals 2022 escrime 4.11

咕咕了好久了，附件

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

FLAG = b"Securinets{REDACTED}"

def genPrime(prime):
    while True:
        a = getPrime(256)
        p = 2*prime*a + 1
        if isPrime(p):
            break
    while True:
        b = getPrime(256)
        q = 2*prime*b + 1
        if isPrime(q):
            break
    return p, q

prime = getStrongPrime(512)
p1, q1 = genPrime(prime)
p2, q2 = genPrime(prime)
assert p1 != p2 != q1 != q2

n1 = p1*q1
n2 = p2*q2
e = 65537

m1 = bytes_to_long(FLAG[:len(FLAG)//2])
m2 = bytes_to_long(FLAG[len(FLAG)//2:])

c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)

print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"e = {e}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

最开始以为是 rho 生成的，后面发现不是，反应过来之后这题已经被别人交了呜呜呜，我只配做大佬们出过的题。

代码很简短很容易看懂，公钥生成的原理如下

$p=2 \times prime \times a + 1$

$q = 2 \times prime \times b + 1$

其中 prime 为 512 位的强素数，ab 均为 256 位素数。这题考察数论变换，主要要注意不同数据的大小。我开始在想他为什么一定要把 flag 分成两部分，后面发现是非分成两段不可，因为他得给两组 n 才能出结果。

数学变换式如下：

$n = p \times q = (2 \times prime \times a + 1)(2 \times prime \times b + 1)$

$n = 4 \times prime^{2} \times ab + 2\times prime \times (a + b) + 1$

所以可以粗略地得出

$n-1=2 \times prime \times(prime \times ab + a + b)$

但是注意，直接 gmpy2.gcd (n1-1,n2-1) 得到的不是 2*prime，因为另一个因数中间有加号，可能存在一些小因子，将 gcd 得到的结果拿去 yafu 分解，得到的 512 位的素数才是我们要求的 prime。

得到 prime 之后再回过头来看 n，我们分解 n 的目的其实就是为了求 n 的欧拉函数 $\phi(n)$ 进而求到私钥，所以求出 p 和 q 的值不是目的，目的是求出 $\phi(n)$ 。然后来康康 $\phi(n)$ 的表达式

$\phi(n)=(p-1)\times(q-1)=4\times prime^{2}\times ab$

所以要求出 $a\times b$ 才能求得 $\phi(n)$ ，再回过头去看看 n 的生成规律能不能得到新的思路。

$n-1=(4 \times prime^{2} \times ab) + 2\times prime \times (a + b)$

其中第一项 $4\times primes^{2} \times ab$ 为 1536 位，第二项 $2 \times prime \times (a+b)$ 为 768 位，其中 $prime^{2}$ 为 1024 位

可以看出前一项是比后一项大很多的，由此可以得出我们整除 $prime^{2}$ 之后，第二项就被消去了，之后我们再乘回 $prime^{2}$ 得到的就是 $\phi(n)$

1	phi = (n - 1) // prime // prime * pow(prime,2)

求出私钥了这题也就结束了，所以对数据的大小要有一定的敏感度

from Crypto.Util.number import *
import gmpy2
n1 = 5285941989924581490741575774796326221790301948671605967204654261159288826022690654909746856601734294076351436205238123432817696904524845143908229601315593896823359605609172777227518764838488130850768836467030938547486936412484230693105639039311878853055295612388722273133638524917106191321503530749409311343663516633298043891444321772817485480644504762143353706512690041092791539952154332856635651319630479019844011333570438615137628705917690349203588170944935681
n2 = 5512656145670579765357132887430527554149315293720001536465226567777071834432904027590899542293511871806792894769506962601330354553170015126601443256295513753986998761021594415121386822360537570074896704547101502955980189351257681515387379761554807684880212096397524725819607628411147885452294832392886405475830663300445429053365129797792206619514994944481130684176571005780217091773969415001961227566026934419626425934895777818074251010427154279687683891897394401
e = 65537
c1 = 3792561290017712418676552700903779226679678307521013229152018077539055935181708693237786486418411190513573593312739874489485768872374239333562352570689090751306553033406629945001093355613620844532659507519582518955178617942044813600181673015763469247380587771641089223066734168709065596269187564842646397647564064090886856491267151338586218098150720579275673440512159074650632829004798635425409766385176472514086448897744502264325566940224093583630788193949908215
c2 = 3222093169881176821995152873609430742364413196826316856495679228145853706169389758246323802005549827444022148276365869623395771621464376723299960525487777645386674088866891887984766934440527885549168365996216682223515034398685244541695223412679979637178695229351272286453267599205874775267533781360269542834699741976380260822746797186755978820611721151719635986648586937891954519919600047846994285652165076540057377973800029963140392459328016771048953153246246886
prime = gmpy2.gcd(n1 - 1,n2 - 1)
print(prime)
# print(getPrime(512))
prime = 12397002878565866184412236037259205021945058505472864688501145731895119789392433217522880454989374040698621943547773164450323280239641723319936790061247301
phi1 = (n1 - 1) // prime // prime * pow(prime,2)
phi2 = (n2 - 1) // prime // prime * pow(prime,2)
d1 = gmpy2.invert(e,phi1)
d2 = gmpy2.invert(e,phi2)
m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
print(long_to_bytes(m1) + long_to_bytes(m2))
#Securinets{G3n3r4t1ng_pr1m3s_1n_4_sp3c1f1c_f0rm_4lm0st_4lw4ys_3nds_b4dly}

这题难度不算大，但是哥哥们交太快了呜呜

# 0x12 2022hgame week2 The Password Plus Pro Max Ultra 2.10

附件

from functools import reduce
from operator import xor
from random import sample
from re import findall
from libnum import s2n
from secret import flag
from solve import decrypt

def move(n, k):
    s = bin(n)[2:].zfill(64)
    k &= 63
    return int(s[k:] + s[:k], 2)

def encrypt(x, ks):
    return xor(x, reduce(xor, map(lambda k: move(x, k), ks)))

xs = list(map(s2n, findall(r".{1,8}", flag)))
for i in range(len(xs)):
    ks = sample(range(1, 64), (i + 1) * 2)
    y = encrypt(xs[i], ks)
    assert xs[i] == decrypt(y, ks)
    print(y, sorted(ks))

刚拿到手上寻思是算法题，但是注意这里的 move 函数其实就是 <<<，循环左移，并且定了一个界就是二进制的后 64 位。这题没出，能够做出来的思路有很多，可以把他当作 64 个未知数当方程运算。但是题解的思路更为巧妙，参考题解写出了我的理解。

首先可以将一次加密这样理解：

y 为密文，x 为明文，p 和 q 是移动的位数 (假设只有两次)，他们之间满足如下关系：

$y=x\oplus(x>>>p)\oplus(x>>>q)$

然后做两次变形得到：

$y>>>p=(x>>>p)\oplus(x>>>2p)\oplus(x>>>(p+q))$

$y>>>q=(x>>>q)\oplus(x>>>(p+q))\oplus(x>>>2q)$

三式异或得到：

$y\oplus(y>>>p)\oplus(y>>>q)=x\oplus(x>>>2p)\oplus(x>>>2q)$

如果将右边的式子再做变形再异或可以得到：

$y\oplus(y>>>2p)\oplus(y>>>2q)=x\oplus(x>>>3p)\oplus(x>>>3q)$

故得到加密的本质其实是：

$x \to x\oplus(x>>>kp)\oplus(\cdots)$

因为 move 定了一个界，所以明文只要加密 64k 次就还是明文。得到的 y 是已经经过一次加密之后的密文，只要再加密 63 次就可以得到明文。

exp：

from operator import xor
from Crypto.Util.number import *
from functools import reduce
def encrypt(x, ks):
    return xor(x, reduce(xor, map(lambda k: move(x, k), ks)))

def move(n, k):
    s = bin(n)[2:].zfill(64)
    k &= 63#取二进制的后8位
    return int(s[k:] + s[:k], 2)

def decrypt(y,ks):
    tmp = y
    for _ in range(63):
        tmp = encrypt(tmp,ks)
    return long_to_bytes(tmp)

y = [2656224875120172108,1261711348908201279, 18219282869614004824,15279054981769814589,7966355346882200701,5641592208539483808,1502927090219059154,3996223120734273799,18295033054788808618,18126228466291248047,9413762634844369954,8964324149921197550,6962485320551449848]
ks = [[8, 35],[19, 29, 30, 45], [6, 16, 18, 21, 44, 55], [10, 26, 30, 46, 51, 54, 58, 63],[5, 13, 25, 29, 37, 39, 43, 52, 53, 59],[1, 26, 31, 39, 40, 41, 43, 45, 49, 52, 54, 62],[8, 12, 19, 20, 30, 32, 34, 40, 41, 45, 46, 49, 55, 58],[2, 3, 5, 6, 8, 10, 15, 19, 26, 27, 33, 40, 42, 47, 52, 61], [1, 16, 17, 27, 28, 30, 32, 36, 37, 38, 39, 48, 49, 51, 55, 57, 59, 62], [5, 11, 12, 20, 22, 23, 25, 27, 31, 32, 33, 37, 44, 45, 49, 52, 53, 59, 61, 62],[2, 7, 10, 12, 18, 19, 20, 22, 26, 29, 33, 34, 38, 40, 41, 45, 46, 51, 54, 56, 57, 60],[3, 4, 5, 9, 12, 13, 18, 19, 21, 23, 24, 25, 30, 33, 34, 35, 37, 39, 43, 44, 46, 49, 50, 53],[1, 3, 6, 7, 10, 11, 13, 14, 23, 27, 32, 33, 35, 37, 39, 41, 46, 48, 49, 50, 51, 53, 54, 56, 58, 62]]
flag = b''
for i in range(len(y)):
    flag += decrypt(y[i],ks[i])
print(flag)
#hgame{XOr|RoR&rOl|Is+vERY#coMmon*BiTwisE$OPeraTiOn*IT@is%oFten,ENCOUntErED*in.syMMeTRic?encryPtION}

被题目暴打了呜呜呜，想学一下当作 64 位未知数的解法。

# 0x11 2020 羊城杯 Invitations 1.17

附件

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
import gmpy2
import random

def pad(s,i):
    return i * pow(3,s.bit_length()) + s**2

def gen_N():
    return getPrime(512) * getPrime(512)


assert len(flag) == 54
invite = bytes_to_long(flag)

e_list = [random.choice([3,5,7]) for i in range(14)]
N_list = [gen_N() for i in range(14)]

with open('./invitations','w') as f:
    for i in range(14):
        invis = pow(pad(invite,i+1),e_list[i],N_list[i])
        f.write('Invitation%d: %d \n'%(i+1,invis))

    f.write('Wait a minute! \n')

    for i in range(14):
        f.write('[e%d,N%d]: [%d,%d]\n'%(i+1,i+1,e_list[i],N_list[i]))

易求得：s.bit_length ()=431

$invis = (i \times 3^{431} + flag^{2})^{e} \pmod N$

其中只有 flag 是未知量，题目给了很多组解。选取 e=3 的几组解

$cs=(Bs + flag)^{3} \pmod N$

其中，Bs= $i \times 3^{431}$ ，cs=invis。

exp 来自 striving 佬的博客。

cs = [129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823, 8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214, 25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080, 9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346]
Ns = [146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391, 65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029, 126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901, 75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471]
B = [130732040222851824313696449987153029924371122238848027365037357297776778759867316566762151412818918312428287717025992710824535681461390797938699373612526042317415057049122693829277442013233093340157044859841, 348618773927604864836523866632408079798322992636928072973432952794071410026312844178032403767517115499808767245402647228865428483897042127836531662966736112846440152130993850211406512035288248907085452959576, 435773467409506081045654833290510099747903740796160091216791190992589262532891055222540504709396394374760959056753309036081785604871302659795664578708420141058050190163742312764258140044110311133856816199470, 479350814150456689150220316619561109722694114875776100338470310091848188786180160744794555180336033812237054962428639939689964165358432925775231036579262155163855209180116544040683954048521342247242497819417]
e = 3
PR.<x> = PolynomialRing(ZZ)
Fs = []
for i in range(len(cs)):
    f =  (x + B[i])**e - cs[i]
#     ff = f.change_ring(Zmod(Ns[i]))
#     ff = ff.monic()
    
    Fs.append(f)
print(Fs)
F = crt(Fs, Ns)#需在ZZ环中运行
print(F)
M = reduce( lambda x, y: x * y, Ns )

FF = F.change_ring(Zmod(M))

m = FF.small_roots(X=2^862,beta=1)[0]
print(m)

得到的 m 开个二次方再 long_to_bytes 就是 flag 了。

# 0x10 ctfshow 摆烂杯 easypeasy 1.10

附件

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

p = getPrime(1024)
q = getPrime(1024)
n = p * q
print(f'n = {n}')

l = len(flag)
assert(l == 86)
m = bytes_to_long(b'\x00' * (l - 1) + flag + b'\x00' * (l - 2))
e = 3
c = pow(m, e, n)
print(f'c = {c}')

# n = 23570098360097260908266914080954003513706885568390448463720576188146956287111601604870247233822682630020002051748117520481402155749832096007629686239669192722978473890311246293580246256300691145653885805730865515297134808702766299205253761028235483781919393575836334910012714628455073300114978717047912395404034141622115001451888302617428376998024080880564792294546406688814397757714979980790018933407614160131827023349206138480523080173634617167828920519758917549492886733519381497665596997617399404664611446202014908853898043742964782757859701755202188366852773164911994663079171498909577012208742001609095258401847
# c = 7802816471025387606454709075933309958303134972861203739854774032383575355964299097074709350633475519273512630813578801152996777689686451397201513854823239337669091889776200179028891111154423623765139235199507280104544068425347533121731521700106757148551520759776111224072064131087547685154285120156917449926992033491342535410929828988598182819897435365878832122138552492908774845437576910276499625679469289655841639181182040186931130789588869657335253479416209378458303531995734157105918063227453396477282662136225029972745246845372963076381252679409317314514131852117346576265346926741908194011319430767975281696400

给了 n、c、e，而且 e=3，乍一看是一个单纯的低指数加密爆破，但是注意一下 flag 转成大数之后的 m 被扩大了很多，前后都被加了很多的 \x00，前面的 \x00 对大数不造成什么影响，重点是研究后面的 84 个 \x00。用 python 实验再加上自己的理解得出结论：flag 后面每加一个 \x00 都是给大数增大 256 倍。
所以可以得到 $m = flag \times 256^{84}$
结合正常的 RSA 流程可得到：
$c=flag^{e} \times 256^{252} \pmod n$
之前这里卡了半天，在宋师父的指点下，一个简单的数论问题
$c \times (256^{252})^{-1} \equiv flag^{e} \pmod n$
把数字化小了之后就是正常的低指数爆破问题了。
贴一个完整的 exp:

from Crypto.Util.number import *
import gmpy2

n = 23570098360097260908266914080954003513706885568390448463720576188146956287111601604870247233822682630020002051748117520481402155749832096007629686239669192722978473890311246293580246256300691145653885805730865515297134808702766299205253761028235483781919393575836334910012714628455073300114978717047912395404034141622115001451888302617428376998024080880564792294546406688814397757714979980790018933407614160131827023349206138480523080173634617167828920519758917549492886733519381497665596997617399404664611446202014908853898043742964782757859701755202188366852773164911994663079171498909577012208742001609095258401847
c = 7802816471025387606454709075933309958303134972861203739854774032383575355964299097074709350633475519273512630813578801152996777689686451397201513854823239337669091889776200179028891111154423623765139235199507280104544068425347533121731521700106757148551520759776111224072064131087547685154285120156917449926992033491342535410929828988598182819897435365878832122138552492908774845437576910276499625679469289655841639181182040186931130789588869657335253479416209378458303531995734157105918063227453396477282662136225029972745246845372963076381252679409317314514131852117346576265346926741908194011319430767975281696400
e = 3
l = 86
flag = b'\xff' + b'\x00' * 85
key = gmpy2.invert(pow(256,252),n)
_c = c * key % n
print(_c)
print(pow(256,252))
k = 0
while True:
    num = _c + k * n
    if gmpy2.iroot(num,3)[1] == True:
        print(long_to_bytes(gmpy2.iroot(num,3)[0]))
        break
    k += 1

# 0x0F 2022 长安战役 math 1.10

附件

pinvq = 0x63367a2b947c21d5051144d2d40572e366e19e3539a3074a433a92161465543157854669134c03642a12d304d2d9036e6458fe4c850c772c19c4eb3f567902b3
qinvp = 0x79388eb6c541fffefc9cfb083f3662655651502d81ccc00ecde17a75f316bc97a8d888286f21b1235bde1f35efe13f8b3edb739c8f28e6e6043cb29569aa0e7b
c = 0x5a1e001edd22964dd501eac6071091027db7665e5355426e1fa0c6360accbc013c7a36da88797de1960a6e9f1cf9ad9b8fd837b76fea7e11eac30a898c7a8b6d8c8989db07c2d80b14487a167c0064442e1fb9fd657a519cac5651457d64223baa30d8b7689d22f5f3795659ba50fb808b1863b344d8a8753b60bb4188b5e386
e = 0x10005
d = 0xae285803302de933cfc181bd4b9ab2ae09d1991509cb165aa1650bef78a8b23548bb17175f10cddffcde1a1cf36417cc080a622a1f8c64deb6d16667851942375670c50c5a32796545784f0bbcfdf2c0629a3d4f8e1a8a683f2aa63971f8e126c2ef75e08f56d16e1ec492cf9d26e730eae4d1a3fecbbb5db81e74d5195f49f1

先贴一个原题链接，膜 la 佬

给了 5 个值，c、e、d、 $q^{-1} \pmod p$ 、 $p^{-1} \pmod q$ 。

其实条件多给了一个，也无伤大雅只是多给条件可能有点误导。

首先因为 $e \times d \equiv 1 \pmod {\varphi(n)}$ ，可推得 $e \times d = k \times \varphi(n) + 1$ 。

比较比特位可得 k 与 e 比特位相同，可以通过爆破的方式求得 k 和 $\varphi(n)$ 。

e = 0x10005
d = 0xae285803302de933cfc181bd4b9ab2ae09d1991509cb165aa1650bef78a8b23548bb17175f10cddffcde1a1cf36417cc080a622a1f8c64deb6d16667851942375670c50c5a32796545784f0bbcfdf2c0629a3d4f8e1a8a683f2aa63971f8e126c2ef75e08f56d16e1ec492cf9d26e730eae4d1a3fecbbb5db81e74d5195f49f1
for k in range(100000):
	if((e * d - 1) % (100000 - k) == 0):
		print(100000 - k)
		break
k = 60701
phi = (e * d - 1) // k
print(phi)

$\varphi(n) \equiv -(q-1) \pmod p$

令 $cf = q^{-1} \pmod p$

$cf \times \varphi(n) \pmod p = cf -cf\times q \pmod p = cf - 1 \pmod p$

故 $(cf \times \varphi(n) - cf + 1) | p$

令 $x=cf \times \varphi(n) - cf + 1$
根据费马小定理 $\quad r^{p-1} \equiv 1 \pmod p$

$r^{\varphi(n)} \equiv 1 \pmod p$

$r^{\varphi(n)}\pmod p = r^{\varphi(n)} \pmod x \pmod p \equiv 1$

所以最终得到 $\quad r^{\varphi(n)}=1+k \times p$

任意意取若干个 r，算出若干个 $r^{\varphi(n)}-1$ 再求公约数就得到了 p, 后面就是正常的 RSA 解密流程了。

exp

from Crypto.Util.number import *
import gmpy2
import libnum
from functools import *
pinvq = 0x63367a2b947c21d5051144d2d40572e366e19e3539a3074a433a92161465543157854669134c03642a12d304d2d9036e6458fe4c850c772c19c4eb3f567902b3
qinvp = 0x79388eb6c541fffefc9cfb083f3662655651502d81ccc00ecde17a75f316bc97a8d888286f21b1235bde1f35efe13f8b3edb739c8f28e6e6043cb29569aa0e7b
c = 0x5a1e001edd22964dd501eac6071091027db7665e5355426e1fa0c6360accbc013c7a36da88797de1960a6e9f1cf9ad9b8fd837b76fea7e11eac30a898c7a8b6d8c8989db07c2d80b14487a167c0064442e1fb9fd657a519cac5651457d64223baa30d8b7689d22f5f3795659ba50fb808b1863b344d8a8753b60bb4188b5e386
e = 0x10005
d = 0xae285803302de933cfc181bd4b9ab2ae09d1991509cb165aa1650bef78a8b23548bb17175f10cddffcde1a1cf36417cc080a622a1f8c64deb6d16667851942375670c50c5a32796545784f0bbcfdf2c0629a3d4f8e1a8a683f2aa63971f8e126c2ef75e08f56d16e1ec492cf9d26e730eae4d1a3fecbbb5db81e74d5195f49f1
print(d)
for k in range(100000):
	if((e * d - 1) % (100000 - k) == 0):
		print(100000 - k)
		break
# print(e)
k = 60701
phi = (e * d - 1) // k
print(phi)

x = 1 + qinvp * phi - qinvp

tmp1 = pow(2,phi,x) - 1
tmp2 = pow(3,phi,x) - 1
tmp3 = pow(5,phi,x) - 1
p = reduce(gmpy2.gcd,[tmp1,tmp2,tmp3])
q = gmpy2.invert(qinvp,p)
n = p * q
m = pow(c,d,n)
print(long_to_bytes(m))

# 0x0E 2021 赣网杯 leak 12.29

附件

from Crypto.Util.number import *
from random import randint, getrandbits
from sympy import nextprime
from secret import flag, secreteBitNum

hint = bytes_to_long((f'secreteBitNum = {secreteBitNum}').encode())
tmp_e = 65537
tmp_p = getPrime(int(512))
tmp_q = getPrime(int(512))
tmp_N = tmp_p * tmp_q
print(f'tmp_N = {tmp_N}')
print(pow(hint, tmp_e, tmp_N))
print(tmp_p >> 180)

target_bits = int(256)
prime = getPrime(target_bits)
s = randint(prime>>10, prime)
r = getrandbits(secreteBitNum)
t = (r*(s^2 + 2*s)) % prime
gifts = [3, 2]
ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
leak1 = s >> (target_bits - ks[0])
leak2 = t >> (target_bits - ks[1])

p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
q = getPrime(p.bit_length())
N = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, N)

print(f'prime = {prime}')
print(f'c = {c}')
print(f'N = {N}')
print(f'leak1 = {leak1}')
print(f'leak2 = {leak2}')


"""
tmp_N = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
N = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
leak1 = 4392924728395269190263639346144303703257730516994610750658
leak2 = 838456777370923849008096179359487752850229097203212
"""

分析题目逻辑可以看出题目分为两个部分，一个是求 hint，一个是求 flag。

求 hint 的部分还是比较显而易见的。也是一组 RSA 加密，题目给了高位的 p，一元 cop 直接梭。

#sage
p4 = 4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
n = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
pbits = 512
kbits = 180
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = p4 + x
root = f.small_roots(X=2^kbits, beta=0.4)
p = p4+root[0]
print(p)

得到 hint 为

1	secreteBitNum = 26

第二部分就是三个变量 s,t,r，三者之间的关系有一个式子给出了

1	t = (r(s^2 + 2s)) % prime

由此可以构造一个三元的多项式，用三元 cop 的板子一把梭

#sage
import itertools
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

hs = 4392924728395269190263639346144303703257730516994610750658
ht = 838456777370923849008096179359487752850229097203212
n = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037

P.<s0,t0,r> = PolynomialRing(Zmod(prime))
s = (hs << 64) + s0
t = (ht << 86) + t0
f = r * (s ^ 2 + 2 * s) - t
bounds = (1 << 64,1 << 86,1 << 26)
roots = small_roots(f,bounds,m=3)[0]
print(roots)
#(2837580634489900859, 63360403616040741532234070, 29943235)

这样就得到了 s,t,r 三个变量，这题也就做完了。

最后贴一个完整的 exp

from Crypto.Util.number import *
import gmpy2
from math import floor
from random import randint, getrandbits
from sympy import nextprime
tmp_e = 65537
tmp_n = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
tmp_hp = 4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
tmp_c = 40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
tmp_p = 7474218428506439131024561238447007658574698902527126414652353026654065729675401366440504060759323896095490193371294094265057254763085596066166150006638181
tmp_q = tmp_n // tmp_p
tmp_phi = (tmp_p - 1) * (tmp_q - 1)
tmp_d = gmpy2.invert(tmp_e,tmp_phi)
hint = pow(tmp_c,tmp_d,tmp_n)
print(long_to_bytes(hint))
prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
n = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
hs = 4392924728395269190263639346144303703257730516994610750658
ht = 838456777370923849008096179359487752850229097203212
secreteBitNum = 26
gifts = [3, 2]
target_bits = int(256)
ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
print(ks)
r = getrandbits(secreteBitNum)
print(r)
print(r.bit_length())

s0,t0,r = 2837580634489900859, 63360403616040741532234070, 29943235
s = (hs << 64) + s0
t = (ht << 86) + t0
p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
print(p)
q = n // p
phi = (p - 1) * (q - 1)
e = 65537
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

# 0x0D 2021 西湖论剑 unknown_dsa 12.23

附件

from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from Crypto.Hash import SHA1
from gmpy2 import invert, powmod
import random
from secret import flag, m1, m2, ul, vl, wl


def encrypt():
    key = DSA.generate(int(1024))
    q = key.q
    p = key.p
    g = key.g
    x1 = bytes_to_long(flag[:len(flag) // 2])
    x2 = bytes_to_long(flag[len(flag) // 2:])
    assert x1 < q and x2 < q
    t = powmod(g, p * q - (p + q), p * q)
    hm1 = bytes_to_long(SHA1.new(m1).digest())
    hm2 = bytes_to_long(SHA1.new(m2).digest())
    k = random.randint(1, q - 1)
    r1 = powmod(g, k, p) % q
    s1 = (hm1 + x1 * r1) * invert(k, q) % q
    s2 = (hm2 + x1 * r1) * invert(k, q) % q
    r2 = powmod(g, x1, p) % q
    s3 = (hm1 + x2 * r2) * invert(k, q) % q
    print(p * q, (p - 1) // q, t, sep=', ')
    print(r1, s1, s2, sep=', ')
    print(r2, s3, sep=', ')


def main():
    for i in range(len(ul)):
        assert ul[i] ** 2 - wl[i] * vl[i] ** 2 == 1
    e = 7
    cl1 = [int(powmod(bytes_to_long(m1), e, x)) for x in ul]
    cl2 = [int(powmod(bytes_to_long(m2), e, y)) for y in vl]
    print(wl, cl1, cl2, sep=', ')

    encrypt()


if __name__ == '__main__':
    main()

'''
[3912956711, 4013184893, 3260747771], [2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704, 21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961, 301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424], [148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144, 1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256, 10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]
85198615386075607567070020969981777827671873654631200472078241980737834438897900146248840279191139156416537108399682874370629888207334506237040017838313558911275073904148451540255705818477581182866269413018263079858680221647341680762989080418039972704759003343616652475438155806858735982352930771244880990190318526933267455248913782297991685041187565140859, 106239950213206316301683907545763916336055243955706210944736472425965200103461421781804731678430116333702099777855279469137219165293725500887590280355973107580745212368937514070059991848948031718253804694621821734957604838125210951711527151265000736896607029198, 60132176395922896902518845244051065417143507550519860211077965501783315971109433544482411208238485135554065241864956361676878220342500208011089383751225437417049893725546176799417188875972677293680033005399883113531193705353404892141811493415079755456185858889801456386910892239869732805273879281094613329645326287205736614546311143635580051444446576104548
498841194617327650445431051685964174399227739376, 376599166921876118994132185660203151983500670896, 187705159843973102963593151204361139335048329243
620827881415493136309071302986914844220776856282, 674735360250004315267988424435741132047607535029
'''

这题要运用的东西还是很多的，佩尔方程求解，扩展 CRT，最后 DSA 的原理就当数论题做了。

从 main 进去先解一个佩尔方程。佩尔方程的基本形式为

$x^{2}-ny^{2}=1$
其中 n 为正整数，基本解法是通过对 $\sqrt {n} $ 的连分数展开求出

具体参照 wiki 百科的佩尔方程

这里用 sage 的连分数攻击得到每个 ul、vl

#sage
ul = []
vl = []
wl = [3912956711, 4013184893, 3260747771]
for n in wl:
    cf = continued_fraction(sqrt(n))
    for i in range(10000):#无理数的连分数是无限的，规定一个循环次数也就是定一个界
        fz = cf.numerator(i)
        fm = cf.denominator(i)
        if fz ** 2 - n * fm ** 2 == 1:
            ul.append(fz)
            vl.append(fm)
            break
print(ul)
print(vl)

顺着题目的思路，得到了 ul、vl，cl1、cl2 题目已经给出，通过这些已知量求 m1 和 m2。m1 和 m2 的加密方式是一样的，每个 m 给了 3 组数据，很容易想到 CRT (中国剩余定理)，但是常规 CRT 不能解决解决模数不互质情况的模线性同余方程组。具体参照 ruanx 大佬的 blog

最后放了个板子我也就直接用了～

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


def uni(P, Q):
    r1, m1 = P
    r2, m2 = Q
    d = gmpy2.gcd(m1, m2)
    assert (r2 - r1) % d == 0
    l1, l2 = exgcd(m1 // d, m2 // d)
    return (r1 + (r2 - r1) // d * l1 * m1) % gmpy2.lcm(m1, m2), gmpy2.lcm(m1, m2)

def CRT(eq):
    return reduce(uni, eq)
e = 7
m1,mod1 = CRT(zip(cl1,ul))#得到通解的形式是m1 + i * mod1
m2,mod2 = CRT(zip(cl2,vl))
print(m1)
m1 = long_to_bytes(gmpy2.iroot(m1,e)[0])
m2 = long_to_bytes(gmpy2.iroot(m2,e)[0])
print(m1)
print(m2)
#b'Hello, this is the first message.'
#b'YES!! that is the second message.'

得到了 m1 和 m2。也就得到了 hm1、hm2。最后来分析一下关于 flag 的加密。
$s1 \equiv (hm1 + x1 \times r1) \times k^{-1} \pmod q$
$s2 \equiv (hm2 + x1 \times r1) \times k^{-1} \pmod q$

题目也给了 $p \times q$ 和 $\frac{p - 1}{q}$ ，解个方程出 pq，复现的时候试了试 factorb 也能出。得到 q 之后就解 k，两个式子相减，需注意的是这里的加减乘除都是在模意义下的。

_m = hm1 - hm2#是负数
_s = s1 - s2
k = gmpy2.mul(_m,gmpy2.invert(_s,q)) % q
print(k)
x1 = (gmpy2.mul(s1,k) - hm1) * gmpy2.invert(r1,q) % q
x2 = (gmpy2.mul(s3,k) - hm1) * gmpy2.invert(r2,q) % q
print(long_to_bytes(x1) + long_to_bytes(x2))
#b'DASCTF{f11bad18f529750fe52c56eed85d001b}'

# 总结

高中老师就教过说数学是一门工具学科，ctf 的密码学题目中大部分也都是偏向于应用。通俗一点讲就是，我知道了变量 a、b，题目要求 c，我知道 python 或者 sage 或者是其他哪个工具可以通过已知量求出 c，来，但是原理我其实不能讲的很清楚。

很直观的体现就是 python 里面的 gmpy2，sympy 等这些包或者是 sage 里面的函数，很难说去理解里面每个函数的原理代码实现，知道的更多就是应用。

当然定理的原理还是要弄清楚，比如说这题的 excrt，这样题目魔改之后也能得心应手。

# 0x0C 小省赛简单 aes 12.5

附件

#!/usr/bin/python3

from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto.Util.number import *
import os

KEY = os.urandom(16)

def encrypt(plaintext):
    cipher = AES.new(KEY, AES.MODE_CTR, counter=Counter.new(128))
    ciphertext = cipher.encrypt(plaintext).hex()
    return ciphertext

message = b"Don't be afraid to fail. It's not the end of the world and in many ways it's the first step toward learning something better and getting better at it."

print(encrypt(message))
print(hex(bytes_to_long(message)))

with open('flag.txt', 'rb') as f:
    flag = f.read().strip()
print(encrypt(flag))
#e453a54c22660a191c8d41f9a7e1709ea615bef755eb5b82bc99f58703bfca088e2d26f44dc84d54e0127a6586b45b94371a3f2f858ffd95bb0b0cfe941ace3272e8cb5ce1da10e8a7a38fa0f58ac0af688693cdcba10c4ea5ed94f01ba3c3676a96bdc5d3ecf926364a446aca8b958c0760a68eaca395b1514295b18f21444f72239f3828b22e4c11e8608fa69cc721db003fedcee0
#c650aa0c2d7459195e8915e8a7b12d8ab71facf70db5059aace5b49041af9406c96f36f94d95

代码很短也很容易看懂，先把给出的 message 用 AES 的 CTR 模式加密给出结果，再给出加密之后的 flag，需要逆推回原来的 flag。先来看看 CTR 模式的加密解密。

我们可以用给出的 message 的明文密文形式求出计数器加密之后的字节，再用这些来和 flag 的密文进行异或得到的就是 flag，思路还是很简单的，直接贴 exp 了。

from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util import Counter

def xor(a,b):
    ans = ''
    for i in range(0,min(len(a),len(b))):
        num1 = eval('0x' + a[i])
        num2 = eval('0x' + b[i])
        ans += hex(num1 ^ num2)[2:]
    return ans

message = b"Don't be afraid to fail. It's not the end of the world and in many ways it's the first step toward learning something better and getting better at it."
c = 'e453a54c22660a191c8d41f9a7e1709ea615bef755eb5b82bc99f58703bfca088e2d26f44dc84d54e0127a6586b45b94371a3f2f858ffd95bb0b0cfe941ace3272e8cb5ce1da10e8a7a38fa0f58ac0af688693cdcba10c4ea5ed94f01ba3c3676a96bdc5d3ecf926364a446aca8b958c0760a68eaca395b1514295b18f21444f72239f3828b22e4c11e8608fa69cc721db003fedcee0'
eflag = 'c650aa0c2d7459195e8915e8a7b12d8ab71facf70db5059aace5b49041af9406c96f36f94d95'
hexmessage = hex(bytes_to_long(message))[2:]
print(hexmessage)
key = xor(c,hexmessage)
key = key[:76]
flag = xor(key,eflag)
flag = long_to_bytes(eval('0x' + flag))
print(flag)

# 0x0B 2020ACTF 新生赛 crypto-aes 12.5

附件

from Cryptodome.Cipher import AES
import os
import gmpy2
from flag import FLAG
from Cryptodome.Util.number import *

def main():
    key=os.urandom(2)*16
    iv=os.urandom(16)
    print(bytes_to_long(key)^bytes_to_long(iv))
    aes=AES.new(key,AES.MODE_CBC,iv)
    enc_flag = aes.encrypt(FLAG)
    print(enc_flag)
if __name__=="__main__":
    main()

代码很好懂，key 是两个 bytes*16，初始向量 iv 是随机 16 个 bytes。可以看出 key 是比 iv 长一倍的，题目给了 key^iv 的值，前面一半就可以推出 key，推出 key 再推出 iv，这题就做完了。

tmp = 91144196586662942563895769614300232343026691029427747065707381728622849079757
print(hex(tmp))
#0xc981c981c981c981c981c981c981c9814eed98e380b1356763849930c850b9cd
显而易见可推出
key = b'\xc9\x81' * 16

然后再异或得到 iv，贴一个完整的 exp

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

def xor(a,b):
    ans = ''
    for i in range(0,min(len(a),len(b))):
        num1 = eval('0x' + a[i])
        num2 = eval('0x' + b[i])
        ans += hex(num1 ^ num2)[2:]
    return ans

tmp = 91144196586662942563895769614300232343026691029427747065707381728622849079757
print(hex(tmp))
key = b'\xc9\x81' * 16
#iv = xor(key,hex(tmp)[2:])
iv = b'\x87\x6c\x51\x62\x49\x30\xfc\xe6\xaa\x05\x50\xb1\x01\xd1\x70\x4c'
enc_flag = b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'
# print(key)
# print(iv)
aes = AES.new(key,AES.MODE_CBC,iv)
flag = aes.decrypt(enc_flag)
print(flag)

# 0x0A 2021swpu_nssctf 新生赛 crypto3 11.29

附件

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

flag  = '******************'

p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))

n = p*q

flag1 = pow(m1,p,n)
flag2 = pow(m1,q,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))

#flag1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
#flag2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
#n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

flag1、flag2 作为两个加密后的密文，这题就是纯纯的数学题，最后运用 sage 的 PolynomialRing (Zmod (n)) 求解。

$c1=m^{p} \bmod n$
$c2=m^{q} \bmod n$

$c1 \bmod p=m^{p} \bmod p$
$c2 \bmod q=m^{q} \bmod p$

根据费马小定理

$a^{p-1} \equiv 1\pmod p$ p 为素数
也可以写成
$a^{p} \equiv a\pmod p$

可得

$c1 \bmod p=m^{p} \bmod p=m \bmod p $即$ c1 \equiv m \pmod p$
同理 $c2 \equiv m \pmod q$

写成等式就是

$c1=m+k_1×p$
$c2=m+k_2×q$

经过等式变换可得

$m^{2}-m×(c1+c2)+c1×c2=k_1\times k_2\times n \equiv 0 \pmod n$

演算至此，可用 sage 解同余方程，该同余式中仅有 m 为未知值

#sage
c1= 17893542812755845772427795161304049467610774531005620109503081344099161906017295486868699578946474114607624347167976713200068059018517606363517478396368430072890681401898145302336139240273132723451063402106360810413024642916851746118524166947301681245568333254648265529408446609050354235727237078987509705857
c2= 95580409405085606847879727622943874726633827220524165744517624606566789614499137069562997931972825651309707390763700301965277040876322904891716953565845966918293178547100704981251056401939781365264616997055296773593435626490578886752446381493929807909671245959154990639046333135728431707979143972145708806954
n= 140457323583824160338989317689698102738341061967768153879646505422358544720607476140977064053629005764551339082120337223672330979298373653766782620973454095507484118565884885623328751648660379894592063436924903894986994746394508539721459355200184089470977772075720319482839923856979166319700474349042326898971

PR.<x> = PolynomialRing(Zmod(n))
f = x^2 - (c1 + c2) * x + c1 * c2#同余方程 右边为0
x0 = f.small_roots(X = 2^400,beta = 0.4)#X为方程中X的大概值
print(x0)#得到的结果即为m的值

最后将得到的 m 直接 long_to_bytes 就好了。

# 0x09 2021 安洵杯 cry3 11.28

附件

from Crypto.Util.number import *
import os

flag = b'D0g3{}'
m = bytes_to_long(flag)

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

hint = bytes_to_long(os.urandom(256))

m1 = m | hint
m2 = m & hint

c = pow(m1, e, n)

with open('output.txt','a') as f:
    f.write(str([n,c,m2,hint]))
    f.close()

仔细观察，给了 m2 和 hint，m1 是 m 和 hint 做或 | 运算，m2 是 m 和 hint 做与 | 运算。值得注意的是 c 是由 m1 加密得到的，最终我们要求的是 m。这题的难点就是看出这是一个 coppersmith 攻击。看一下位数。

1 2	print(hint.bit_length())#2047 print(m2.bit_length())#383

可以看出 hint 是比 m2 长很多的，所以可以推出 m 的长度为 383，383 位的 m 和 2047 位的 hint 做或 | 运算，得到的 m1 也是 2047 位的，可以理解为是 hint 的后 383 位被 m 混淆得到了 m1。

这样想思路就简单了，可以理解为是给出 m 高位的 coppersmith 攻击，Stereotyped messages 攻击。所以这里直接将 hint 理解为是高位的 m1，直接舍弃后面被混淆的 383 位，先做一个处理是

1	m_high = hint >> 383 << 383

再就是跑 sage

#sage
e = 
b = #高位m
n = 
c = 
kbits = #低位m的位数
PR.<x> = PolynomialRing(Zmod(n))
f = (x + b)^e-c
x0 = f.small_roots(X=2^kbits, beta=1)[0]
print(int(x0))
#得到的结果x0是低位m

这样可以得到低位的 m1，也就是知道了后面 383 位的 m1，这样已知 m1、m2、hint，就可以把 383 位的 m 每一位给试出来。完整脚本如下。

from Crypto.Util.number import *
import gmpy2
n = 13002904520196087913175026378157676218772224961198751789793139372975952998874109513709715017379230449514880674554473551508221946249854541352973100832075633211148140972925579736088058214014993082226530875284219933922497736077346225464349174819075866774069797318066487496627589111652333814065053663974480486379799102403118744672956634588445292675676671957278976483815342400168310432107890845293789670795394151784569722676109573685451673961309951157399183944789163591809561790491021872748674809148737825709985578568373545210653290368264452963080533949168735319775945818152681754882108865201849467932032981615400210529003
c = 8560367979088389639093355670052955344968008917787780010833158290316540154791612927595480968370338549837249823871244436946889198677945456273317343886485741297260557172704718731809632734567349815338988169177983222118718585249696953103962537942023413748690596354436063345873831550109098151014332237310265412976776977183110431262893144552042116871747127301026195142320678244525719655551498368460837394436842924713450715998795899172774573341189660227254331656916960984157772527015479797004423165812493802730996272276613362505737536007284308929288293814697988968407777480072409184261544708820877153825470988634588666018802
m2 = 9869907877594701353175281930839281485694004896356038595955883788511764488228640164047958227861871572990960024485992
hint = 9989639419782222444529129951526723618831672627603783728728767345257941311870269471651907118545783408295856954214259681421943807855554571179619485975143945972545328763519931371552573980829950864711586524281634114102102055299443001677757487698347910133933036008103313525651192020921231290560979831996376634906893793239834172305304964022881699764957699708192080739949462316844091240219351646138447816969994625883377800662643645172691649337353080140418336425506119542396319376821324619330083174008060351210307698279022584862990749963452589922185709026197210591472680780996507882639014068600165049839680108974873361895144
# print(hint.bit_length())
# print(m2.bit_length())
m_part = hint >> 383 << 383
print(hex(m_part))
#sage得到的m1_low
m1_low = 13420866878657192881981508918368509601760484822510871697454710042290632315733970543259862148639047993224391010676733
m1 = m_part + m1_low
print(m1_low.bit_length())
print(m1.bit_length())
_m1 = bin(m1_low)[2:]
_m2 = bin(m2)[2:]
_hint = bin(hint)[-383:]
m = ''
for i in range(383):
    if 1 | int(_hint[i]) == int(_m1[i]) and 1 & int(_hint[i]) == int(_m2[i]):
        m += '1'
    else:
        m += '0'
print(m)
print(long_to_bytes(int(m,2)))

# 0x08 2020 羊城杯 gmc 11.24

附件

from Crypto.Util.number import getPrime,bytes_to_long,getRandomNBitInteger
from secret import flag
from gmpy2 import gcd


def gmc(a, p):
    if pow(a, (p-1)//2, p) == 1:
        return 1
    else:
        return -1


def gen_key():
    [gp,gq] = [getPrime(512) for i in range(2)]
    gN = gp * gq
    return gN, gq, gp


def gen_x(gq,gp):
    while True:
        x = getRandomNBitInteger(512)
        if gmc(x,gp) ^ gmc(x,gq) == -2:
            return x


def gen_y(gN):
    gy_list = []
    while len(gy_list) != F_LEN:
        ty = getRandomNBitInteger(768)
        if gcd(ty,gN) == 1:
            gy_list.append(ty)
    return gy_list


if __name__ == '__main__':

    flag = bin(bytes_to_long(flag))[2:]
    F_LEN = len(flag)
    N, q, p = gen_key()
    x = gen_x(q, p)
    y_list = gen_y(N)
    ciphertext = []

    for i in range(F_LEN):
        tc = pow(y_list[i],2) * pow(x,int(flag[i])) % N
        ciphertext.append(tc)

    with open('./output.txt','w') as f:
        f.write(str(N) + '\n')
        for i in range(F_LEN):
            f.write(str(ciphertext[i]) + '\n')

通过 gmc 中的欧拉判别式中判断出来说这题考二次同余，思路清晰，仍旧是判断 tc 是否是 n 的二次剩余，直接贴 exp

from Crypto.Util.number import *
import gmpy2
ans = ''
with open('output.txt','r') as f:
    n = int(f.readline())
    for i in f:
        if gmpy2.jacobi(int(i),n) == 1:
            ans += '0'
        else:
            ans += '1'
print(long_to_bytes(int(ans,2)))

# 0x07 2021Geekchallenge step_by_step 11.24

二次同余，附件

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import gmpy2 as gp
import random
from flag import flag
flag = bytes_to_long(flag)
p = getPrime(100)
q = getPrime(100)
n = p * q
clist = []
for i in bin(flag)[2:]:
    while True:
        x = random.randint(1, n)
        if gp.gcd(x, n) == 1:
            c = (pow(3, int(i) + x * 2, n) * x**2) % n
            clist.append(c)
            break
print(n)

print(clist)
'''
1254676922968308054473282588201432441748387886551758353389559
clist...

'''

整个加密算法核心无疑是 c

$c=3^{i+2x} × x^{2} \pmod n$ (i 为 0 或 1)

此题仅需判断 c 是否是 n 的二次剩余，用雅可比符号就好了。

关于雅可比符号，它其实是勒让德符号的推广，具体的求法不展开细说网上的教程挺多的。求雅可比符号也可以用 gmpy2 里的库求。这里最核心就是判断，具体如下

若 i=0， $c=(3^{x}×x)^{2}\pmod n$ 。即 c 为二次剩余，雅可比符号为 1
若 i=1， $c=3^{1+2x} × x^{2} \pmod n$ 。2x+1 为奇数，c 为非二次剩余，雅可比符号为 0

知道了这个之后这题思路就很清晰了，直接上 exp

from Crypto.Util.number import *
import gmpy2
n = 1254676922968308054473282588201432441748387886551758353389559
c = [112490766735794793494258589897687977797993914062877995369853, 423825989606899409733986824741778284626898537704684650054048, 1239912440099782777043012567198356769914426423982980091061342, 1078272043845620437375344423460688188703277391763226546180151, 159286594418951337823608883690981934876156746053051292254402, 189434397083734065502133592439774066008070864031834709620441, 264105932521685455831442874483122006851812174082486446496525, 252479590298382195780257510632414277760400686563367629394825, 34602153293813328946647556336715300088648653636913843351330, 808692976248223555967993480457680585654329233137701900525232, 836623390705731389723338030121423143060093415003999783847569, 1218829648463542488706300570862499177531816513847669694517865, 571795296699927140597629733281737316938588378300113684751321, 324408602401500017634991400429058861929441907523133040616718, 652309276856121062936275131393396513436481452168222192943617, 135368324264829776566203256490111602190045577103623626459391, 677807894471260530035795635544578014296111908610448488780236, 1135708831589387209825610411788217272141435421502826225558333, 196882176169680492388044653063809988445336200851553236565493, 1130705847039352086713022625138307016610235729598245321418537, 974627899979016730650505688458957247745733629797568884460037, 948987355716018600108888773982169186615279073844787201014331, 364200727831752453880724784142441918092136276002472196567297, 811786724825671349602848333002825903390189436235744947667153, 248544601758659627780643527412918707686666534454807514221527, 1078860601713092925823762998344218082511712606733279204236487, 634851505432770176888905188832078431577879067601938324607512, 232972021265122845242665536151391828176473610240017058444456, 1080796896535347345799923528377657622102130648424673730618155, 622059452832122796944248249707923610120342427983134655552340, 837257289852652447556360719449396492271622453092839975184158, 626327369687614106133688347844033161113612134573404258486630, 1233019194503373412608053469954621323121044455057773900406773, 912564467902216938034173803480737819092198560216579817988291, 408076399689155479697691914877522087726703540593136498587215, 1118745562641959211267518507476218888452509349041078337285098, 1103228775032586830415033772993541541820163005491285279882940, 680899077364553221002722115625274809744677788062477442312086, 355349436487753936000721704075588637048102593449252106813298, 5254361838244723184679801326407268664182654715017847086461, 480145671282471097574354032682584083826945502763658946101104, 249136810947175342894562520096603076879372702701088690594445, 175216547555975039599856545426098941943382367602172941744494, 436310864447848960706296122266108102033486860525693191197797, 342620466614509535208918527767209905005823047382938223113086, 369848992268737575958936185907214270590887322936419642815242, 278575045025661827978388874494219837629182438978526195181637, 1189171180780533071473125545247289861677955100195126109964590, 256190182678715266654387215899616014762531664768736561586327, 719160215933023695898776016718481385742508618676368640641809, 147033122794177086112261858085593706727904275426698884436011, 247466503394960387825735598976068779045757078494832316444804, 787155643450160361724955357286670519256662665704845721250609, 112101120505278148126370035869523081506090979629681063614381, 890009544685851814191758439205974159586245412054287515881584, 1168625756997945588141764967298286550498540363325170551587334, 946031342434770434479581499217378781992921204179509449159996, 759124753621557368233069144948668001126536400499520990700641, 930584421635842804698880452391670787414151645249729141739148, 140981825203074314092967178062754008486703246602401550271041, 880126454149733441805446179826584472107299085899567279467558, 510129631452465708304688340114214360026947205003705062663759, 857274757020001316639221394675820731579775247610619594760511, 444486969413575687285961819261097401974268741167841964919716, 645830958128126799221416466698967430939726760487764050203821, 128864469762235652994228226148325614187747349331618451490354, 732913002124581119538173953534485652651112140400076340646452, 1245672039639609341331477592944058028011275464117654972595670, 1160765030758624190775369713232721901616189349905945190302338, 745734132091942990384796294800038299023052878196943617322617, 34973161572808799782240527358912894045293050940490682156733, 507586651070816931641904112686082840821460472219390068396982, 359195216122538975934588740641220005777478961423841727365432, 60506687352654743312206686911057762445232526009857863834444, 402036521271253699065227780662896890228371046068283711170220, 465427226677337673103293964961886503610313835775181975449721, 925246962888172144515172444374190859841851825972285013006527, 542176614893876361668218387162168517498644799220587472896002, 852215132196560596695876248813488364201491362280912035912061, 945548964927065532651141821562204387565145712002346337639711, 736943822066388892909878515650831955490636214039062998720510, 766357526983761241394182000478355475617711906398422036954152, 77156525593382594092608158744099524034892127423492520631820, 562562817542804973601572838378263130638457829485887327130286, 768093992370198202822524520006977816845162154854939167515517, 1099957424762490943973557935337350760135180754563993547358098, 698816668614997174913438496891169625976027534942525487303513, 417641699919584202170293946436276552973997395211792288687960, 1006229610175567855209117721408416419896921240126676949824724, 4206431689326446028142220658552064336105749936096602165359, 893846509909828693967573302731018066461118006150050253703744, 878425189026235350891203121924637130803808920422558040493294, 730047416245095988472212050949689633327186823542036387345181, 648095719945750715387983948406690533087473721929975873848169, 213513454359755001454814601053555627585345770061082141021326, 350001050012957205656929492039628823072469208940960439158263, 1016858635000037892730835311903706149371704230428070443107320, 1040987439471207869975679257301693610464700899302787643642354, 1194690615352550474729309715449838057220521596135246725909553, 508165053077110820797186371383859674371399129952105597675096, 266494438294281492504556232035584920066331725618646155019547, 28469482072427012244441092412738741355431846649166066368980, 790175775999108776289865518368056397969387298334297622465909, 590581138260907253939363764832940322585129285968275409510634, 221909012579985462013325803334419731308959816500415305934495, 1063780559219791515938747204569742799329237935871594345400252, 977747525495509380693721486866821791065499754056415279744653, 346306061371595730004513789139807509540063462412619321003626, 456103179467597859705969406860196938169100856240100927540401, 969300078509189631808517876996065933181606409375207150288464, 1029806631220370012120597683927351131622576733031694535189521, 344896431603140401163996810922500893279239069499717183710501, 430000423804197030568046280589772094106128395099434235915031, 700179843567016021775399107572964843751703290591400960796112, 961227906080189143689698720420426659986080298413605666115640, 607209606799750473714271393200060455739097869884727178692312, 106958847163040842225140399905505511449479709017540851084532, 953369942103273809257762268859167463617831445026988544378658, 428269440686506672744282327102546440435442014650795927162711, 56621803434665963032193024056111306570802155743250152849716, 800707635631355839166448276143596444307614901816577459076131, 1032256515703247765067950588859299047987257001987777631061065, 813725055801254665600156259482200403981770576173968929131487, 940024839745068011043019236327963504645352520797347949823455, 1065005324140908547287467504568283884363143527586278243210801, 1087828777506290663525994551834233065465427418753806182842291, 668387132001968449612224853010931354244797738682007519611989, 563185246196177998134932666270526715161378776103340983046580, 148292872313931508344196679476720973752571125303712466045656, 413889563851226543249984374872220761253120628252088546262699, 853542105910386365929770611480736086723126396438880650918917, 59730458840715910492468261806200793684923819793480597554146, 792260492800286127199649276659137441324248689470594987965190, 753608630500639136668081531883097047491651258191552267413126, 33514911499472634865669915075769163328171019557849259474018, 634963859228206842307837566519244534650818456901841184879977, 219354096455968590219445072777282329948785844491217770978344, 1123377226439583158729762969668999276741275445803396272436031, 357765295513680388973981712560200525235334734759663454993805, 385868499980630535766019957877752149506518574529845752144666, 138578212294299392480319417966870656714476525885983752756188, 1110526796192425688386237355263892073046060477008920073455044, 244699783645221387947312903861559688207612147588246639081699, 583209905862562678600202085212425597809036630416117298854978, 1207854793808762194414317661151529169444903662139065050090746, 1127506983223466275821900811940356395242309493951089427884032, 526185119576631048584313761548704536031634598332129570964689, 266882032196696984660521486449809902101615921156569537960109, 1188118705564450461919200724390473040524626320052324478509883, 682831747455078454647149830819696088960233603851250102828667, 669419928942561433130809268138650695825596612075801278942980, 1077750630919867687880983437504767304166615787212813240073843, 486023540111308483450127320955599047045479654684477043315645, 409429366346146233850088863324915025465847596238000661872172, 779883595226131237594759409249289551033410304517183865388408, 1155872225708857920911178110668279174877878422508206228579940, 411063490066038942009369947241345843238439795078686488373864, 1243453053541946030699872676712518536022061850799945414120045, 871711034820169700581685353768658469631429266493677466057997, 601920686459160120670719526703980120744719013393032353678765, 329932100141177850249406090412821976994089707958551194468769, 558327299751202100333335353826111016492585371503632197870640, 113444032302978611299580451314055133491399096282744687816086, 152525914892717139057165748051966776217223953242540511499945, 965404850400527912039904270871065001313018148780552532312669, 313557099445185696402013375071955475516203519824979749629786, 952254159335810337756614972813240144837526566801182319987154]
ans = ''
for i in c:
    if gmpy2.jacobi(i,n) == 1:
        ans += '0'
    else:
        ans += '1'
print(long_to_bytes(int(ans,2)))

这题被秒成签到了。

贴个附件

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

m1 = bytes_to_long(flag[:len(flag) // 2])
m2 = bytes_to_long(flag[len(flag) // 2:])

def gen(pbits, qbits):
    p1, q1 = getPrime(pbits), getPrime(qbits)
    n1 = p1**4*q1
    q2 = getPrime(qbits)
    bound = p1 // (8*q1*q2) + 1
    p2 = random.randrange(p1, p1 + bound)
    while not isPrime(p2):
        p2 = random.randrange(p1, p1 + bound)
    n2 = p2**4*q2
    return (n1, n2), (p1, q1), (p2, q2)

e = 0x10001
pbits = int(360)
qbits = int(128)
pk, sk1, sk2 = gen(pbits, qbits)
c1 = pow(m1, e, pk[0])
c2 = pow(m2, e, pk[1])
print(f'pk = {pk}')
print(f'c1, c2 = {c1, c2}')

"""
pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
"""

$\frac{N1}{N2}$ 的连分数展开是对 $\frac{q1}{q2}$ 的一个逼近

参考前题，直接贴 exp:

from Crypto.Util.number import *
import gmpy2
def continuedFra(x,y):
    cf = []
    while y != 0:
        cf.append(x // y)
        x,y = y,x % y
    return cf

def exp(x,y):
    cf = continuedFra(x,y)
    fz = [cf[0],cf[0] * cf[1] + 1]
    fm = [1,cf[1]]
    for i in range(2,len(cf)):
        z = fz[i - 1] * cf[i] + fz[i - 2]
        m = fm[i - 1] * cf[i] + fm[i - 2]
        fz.append(z)
        fm.append(m)
    return fz,fm

e = 0x10001
c1 = 361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438
c2 = 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394
n1 = 1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233
n2 = 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989
_q1,_q2 = exp(n1,n2)
for i in range(2,len(_q1)):
    q1,q2 = _q1[i],_q2[i]
    if n1 % q1 == 0 and n2 % q2 == 0 and n1 != q1 and n2 != q2:
        print(q1,q2)
q1 = 181856133933383097933223133658050179553
q2 = 196443958511498599913330690975430421229
p1 = gmpy2.iroot(n1 // q1,4)[0]
p2 = gmpy2.iroot(n2 // q2,4)[0]
phi1 = p1 ** 3 * (p1 - 1) * (q1 - 1)
phi2 = p2 ** 3 * (p2 - 1) * (q2 - 1)
d1 = gmpy2.invert(e,phi1)
d2 = gmpy2.invert(e,phi2)
m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
print(long_to_bytes(m1) + long_to_bytes(m2))

# 0x05 2020 羊城杯 RRRRRRRSA 11.23

打完西湖论剑之后一直被学校的课题牵着，其实也是之前的债。

连分数，先贴一个附件图

import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{************}'

flag1 = flag[:19].encode()
flag2 = flag[19:].encode()
assert(len(flag) == 38)

P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)

Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)

N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2

E1 = getPrime(1024)
E2 = sympy.nextprime(E1)

m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)

c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)


output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()

这里需要用一个定理

若 $x \in R+$ ，那么在 x 的连分数展开逼近式中，若有 $|x-\frac{b}{c}|<\frac{1}{2c^{2}}$ , 其中 gcd (b,c)==1，则可以认为 $\frac{b}{c}$ 是 x 连分数展开式中的一项。

p1 与 p2 之间，q1 与 q2 之间相差的值都非常的小，e 非常的大，flag 的两段加密是算法的一样的。n 与平常的不同，此题的 n 是
$n=p^{2}×q$
我们可以构造式子
$q1×N2-q2×N1=q1×q2×(p2^{2}-p1^{2})$
最后经过化简推导可以得到
$|\frac{N1}{N2}-\frac{q1}{q2}|=\frac{q1×q2×(p2^{2}-p1^{2})}{p2^{2}×q2^{2}}$
至此，需要证明
$\frac{q1×q2×(p2^{2}-p1^{2})}{p2^{2}×q2^{2}}<\frac{1}{2q2^{2}}$ 映射到公式中就是 (c=q2)

证明过程省略，结论就可知
$\frac{N1}{N2}$ 的连分数展开式中一项为 $\frac{q1}{q2}$
连分数的展开式计算有递推公式

连分数 $\frac{p_k}{q_k}$ 的展开式满足递推关系
$p_{k}=a_{k}p_{k-1}+p_{k-2}$
$q_{k}=a_{k}q_{k-1}+q_{k-2}$
$a_{k}$ 为该项连分数展开的值

于是可以通过连分数展开求出 q1,q2 的值，完整 exp 如下

from Crypto.Util.number import *
import gmpy2
n1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
e1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
n2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
e2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393

def continuedfra(x,y):#得到连分数的展开式
    ans = []
    while(y != 0):
        ans.append(x // y)
        x,y = y ,x % y
    return ans
    
def exp(x,y):
    cf = continuedfra(x,y)
    fz = [cf[0],cf[0] * cf[1] + 1]
    fm = [1,cf[1]]
    for i in range(2,len(cf)):
        z = cf[i] * fz[i - 1] + fz[i - 2]
        m = cf[i] * fm[i - 1] + fm[i - 2]
        fz.append(z)
        fm.append(m)

    return fz,fm

#print(exp(415,93))
_q1,_q2 = exp(n1,n2)
for i in range(2,len(_q1)):
    if n1 % _q1[i] == 0 and n2 % _q2[i] == 0 and n1 != _q1[i] and n2 != _q2[i]:
        q1,q2 = _q1[i],_q2[i]
        print(q1,q2)
        break
q1 = 11628371843051760370952910026406764366191062991235308941262037248377376991693250742343307155422036713746576338866595433599862614339347536916226536644210947
q2 = 11628371843051760370952910026406764366191062991235308941262037248377376991693250742343307155422036713746576338866595433599862614339347536916226536644211929
p1 = gmpy2.iroot(n1 // q1,2)[0]
p2 = gmpy2.iroot(n2 // q2,2)[0]
phi1 = p1 * (p1 - 1) * (q1 - 1)
phi2 = p2 * (p2 - 1) * (q2 - 1)
d1 = gmpy2.invert(e1,phi1)
d2 = gmpy2.invert(e2,phi2)
m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
print(long_to_bytes(m1) + long_to_bytes(m2))

# 0x04 省赛 crypto2 10.26

附件：

from Crypto.Util.number import *
from secret import flag, NBIT, MIDDLE
assert MIDDLE < 4096

def rsarsa(nbit):
    while True:
        p = getPrime(nbit)
        middle = (2**nbit - 3) ^ p
        q = middle + MIDDLE
        if isPrime(q):
            return p,q

p,q = rsarsa(NBIT)
e = 0x10001
n = p * q 
m = bytes_to_long(flag)
c = pow(m,e,n)

print('n =', n)
print('c =', c)


'''
n = 692224041388945379000542945310902880889100544298206558809223921382304144887565486168738878540375370962131523216110266003450063038852597901973959069961409252090233088923246072020448653242413438525803983280986587695098100053523677324314279892099704680639276122605007782194993832619487191722743054531524695485466578897531910673635843617334895918839728199336965513679879931120369894252383320216068550188557341291620047417322944706390751843111508918089789408109422357563835039746241760245490926252447703597477533668752930171198897054058982716965576506579176144003183647342789557878319494827627831312013617439863026665812607443
c = 307197727308287745314426467002903248074969761558679046606456172330293223597622415661766314599586983706525802752702590834171088229466177584813058269117390420554764305566689318459776899180134066369190626054796865325243251558047293127988662783785017198221284274732844911397443405439812227924713443788235973809737857889544240278704700770780579167766105940360383012181564955578959555701526997721449721679761556310570137638766549920135248234070586743609456381815893734230223940645912347773433002389063138902856398043379520285872239709077175291162768996775352120726794354655215827681853155145863834324898022202315574453344333550
'''

这题当时线下没打出来，我太菜了呜呜呜。赛后在受点拨之后终于打出来了。
这题的核心代码就是 p 和 q 的取值

def rsarsa(nbit):
    while True:
        p = getPrime(nbit)
        middle = (2**nbit - 3) ^ p
        q = middle + MIDDLE
        if isPrime(q):
            return p,q

结合上一个记录的例题，发现了端倪，有一个等式很关键
$p+middle=2^{nbits}+1或2^{nbits}-3$
两个答案之间才相差 4，又由于有 MIDDLE 的存在，所以可以得到一个更关键的等式
$p+q=2^{nbits}+MIDDLE$
做到这这题基本上可以算是做出来了，n 的位数是 2063 (n.bit_length ())，估摸着 p 的位数在 1033 左右，取 p 和 q 的关键代码如下

nbit = 1033
while True:
    for MIDDLE in range(4100):
        tmp = MIDDLE + pow(2,nbit) + 1
        _tmp = gmpy2.iroot(tmp * tmp - 4 * n,2)[0]
        #print(_tmp)
        p = (tmp + _tmp) // 2
        q = (tmp - _tmp) // 2
        if p * q == n:
            print(p,q)
    nbit += 1

这样可以把 p 和 q 的值求出来，最后完整 exp 如下

from Crypto.Util.number import *
import sympy
import gmpy2
n = 692224041388945379000542945310902880889100544298206558809223921382304144887565486168738878540375370962131523216110266003450063038852597901973959069961409252090233088923246072020448653242413438525803983280986587695098100053523677324314279892099704680639276122605007782194993832619487191722743054531524695485466578897531910673635843617334895918839728199336965513679879931120369894252383320216068550188557341291620047417322944706390751843111508918089789408109422357563835039746241760245490926252447703597477533668752930171198897054058982716965576506579176144003183647342789557878319494827627831312013617439863026665812607443
c = 307197727308287745314426467002903248074969761558679046606456172330293223597622415661766314599586983706525802752702590834171088229466177584813058269117390420554764305566689318459776899180134066369190626054796865325243251558047293127988662783785017198221284274732844911397443405439812227924713443788235973809737857889544240278704700770780579167766105940360383012181564955578959555701526997721449721679761556310570137638766549920135248234070586743609456381815893734230223940645912347773433002389063138902856398043379520285872239709077175291162768996775352120726794354655215827681853155145863834324898022202315574453344333550
e = 0x10001
nbit = 1033
'''while True:
    for MIDDLE in range(4100):
        tmp = MIDDLE + pow(2,nbit) + 1
        _tmp = gmpy2.iroot(tmp * tmp - 4 * n,2)[0]
        #print(_tmp)
        p = (tmp + _tmp) // 2
        q = (tmp - _tmp) // 2
        if p * q == n:
            print(p,q)
    nbit += 1'''
p = 83779430298667510005030233140133481557110011860444148119338405921926228260533780776148652029157919380426250379194849091713116366415687948044381119153358182529766538707906804669498361969372946520124225189026692780636946602267126307798394572549518588479133844354106171812548366397662316259990312379415967213934437
q = 8262458206283064470710192628264584804130409461401948404657795630832901751882712347798088359914739062387247927299304307408183995217293362671956765334052569151650622725624323791968374466465053669035753282440830173008186547092214687516248940047384956948501617116402012886304623522839298488085390061351635544321239
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

去线下被风信子的师傅打烂了，争取下次不被打得那么惨。

# 0x03 roXen 10.25

附件：

#!/usr/bin/env python

from Crypto.Util.number import *
from secret import exp, flag, nbit

assert exp & (exp + 1) == 0

def adlit(x):
    l = len(bin(x)[2:])
    return (2 ** l - 1) ^ x

nbit = 1024
l = [1023,1024,1025]
def genadlit(nbit):
    while True:
        p = getPrime(nbit)
        q = adlit(p) + 31337
        if isPrime(q):
            return p, q

p, q = genadlit(nbit)
e, n = exp, p * q

c = pow(bytes_to_long(flag), e, n)

print 'n =', hex(n)
print 'c =', hex(c)
#n = 0x3ff77ad8783e006b6a2c9857f2f13a9d896297558e7c986c491e30c1a920512a0bad9f07c5569cf998fc35a3071de9d8b0f5ada4f8767b828e35044abce5dcf88f80d1c0a0b682605cce776a184e1bcb8118790fff92dc519d24f998a9c04faf43c434bef6c0fa39a3db7452dc07ccfced9271799f37d91d56b5f21c51651d6a9a41ee5a8af17a2f945fac2b1a0ea98bc70ef0f3e37371c9c7b6f90d3d811212fc80e0abcd5bbefe0c6edb3ca6845ded90677ccd8ff4de2c747b37265fc1250ba9aa89b4fd2bdfb4b4b72a7ff5b5ee67e81fd25027b6cb49db610ec60a05016e125ce0848f2c32bff33eed415a6d227262b338b0d1f3803d83977341c0d3638fL
#c = 0x2672cade2272f3024fd2d1984ea1b8e54809977e7a8c70a07e2560f39e6fcce0e292426e28df51492dec67d000d640f3e5b4c6c447845e70d1432a3c816a33da6a276b0baabd0111279c9f267a90333625425b1d73f1cdc254ded2ad54955914824fc99e65b3dea3e365cfb1dce6e025986b2485b6c13ca0ee73c2433cf0ca0265afe42cbf647b5c721a6e51514220bab8fcb9cff570a6922bceb12e9d61115357afe1705bda3c3f0b647ba37711c560b75841135198cc076d0a52c74f9802760c1f881887cc3e50b7e0ff36f0d9fa1bfc66dff717f032c066b555e315cb07e3df13774eaa70b18ea1bb3ea0fd1227d4bac84be2660552d3885c79815baef661L

这题和省赛线下那道题很类似，这题理解起来倒不难。细看这个 adlit 函数，和 $2^l$ -1 异或，不就是取反吗。然后可以得到这个式子
$p+adlit(p)=2^{nbit}-1$
然后题目又给了条件：
$q=adlit(p)+31337$
联立一下可以求出 p 和 q

import sympy
p = sympy.Symbol('p')
q = sympy.Symbol('q')
f1 = pow(2,1024) - 1 + 31337 - (p + q)
f2 = n - p * q
result = sympy.solve([f1,f2],[p,q])
print(result)
#我是懒狗别骂了

然后是 e，题目给了一个条件 assert exp & (exp + 1) == 0，仅能确定
$e=2^k-1$
不过这也够了，贴一个 exp

from Crypto.Util.number import *
import gmpy2
import sympy
n = 8075050082948443349212340895390914595911667800472259304754411169066015177591933999426560842475863558771524178567197246061634705069273801684590339376649250275207876158732481939003115606742710400986721591279999826858150876137968993463656776832026731671417714759299940616065017786507499266738676453484280827236651674321383863812748279151357153518973782147856930772203682878762471730337625339948570784785485324346140610598746611747268908435220575244445870697107881309658419479841845001923938819243466739611923893747979395011225704679540471165704211172427337362271759859075915131503186516103524664973440454762264198865807
c = 4853661856538137406464034645906094152913630881745619406489837142176663842103161345726810796014324314815721708473241794990602572186090153630178109119000213575671689095484555801915325918814943882491883912939695163112247489821713563958885663470619257776668644302133854563122818923079903345131503071641985122522971974296790978299728014731290028116679328055229119298349730647468258800098306200875957662303051682669135862889528217767209821797678213735216907093405968738909692976414606843097568371074804700587363228896629583675336567001789346679322477777578268489982160639014959437742274169277165123841304006603130339784289
#print(n)
#print(c)
p = sympy.Symbol('p')
q = sympy.Symbol('q')
f1 = pow(2,1024) - 1 + 31337 - (p + q)
f2 = n - p * q
result = sympy.solve([f1,f2],[p,q])
print(result)

tmp1 = pow(2,1024) - 1 + 31337
tmp2 = gmpy2.sqrt(tmp1 * tmp1 - 4 * n)
#p = (tmp1 + tmp2) // 2
#q = (tmp1 - tmp2) // 2
p = 87834916545113015336000964296144306577174555879027549345134855850783246277838709952680829156347468418886211490335525241607253688425417142115840218894244902812798763051744684655923207165455737209507609386779708842318917975391900956941587572141475884466544826179681669143055208345737430546444402480246313669813
q = 91934396941118575436929554782758166784623142015203107928295225306949429527662253180027648166060067602233902389535868116051536080388999480377007211745229221564969130373120800620379012435790356909945473565305296926519232706950561924532325538399351352696805684504904629096892037592742285758390953849377910498739
phi = (p - 1) * (q - 1)
k = 1
while True:
    k += 1
    e = 2 ** k - 1
    gcd = gmpy2.gcd(e, phi)
    e2 = e // gcd
    d = gmpy2.invert(e2, phi//gcd)
    m = pow(c, d, n)
    p, judge = gmpy2.iroot(m, gcd)
    plaintext = long_to_bytes(p)
    if b'CTF' in plaintext and judge:
        print(plaintext)
        break

# 0x02 Geek Challenge 2021 Superposition_under_the_starry_sky 10.16

附件：

from Crypto.Util.number import bytes_to_long, getPrime
from flag import flag
a = getPrime(400)
b = getPrime(400)
n = getPrime(400)
flag = bytes_to_long(flag)
seed = flag
result = []
for i in range(3):
    seed = (seed * a + b) % n
    result.append(seed)
print(result)
print(n)
"""
[1633086272556604467630727869278140040711140555507257984778706962389364338237377391272504059109316040445365656669071569236, 1206389051656797336925675372412697477889689141174380289961348552709531162180853687116202278892215286522581909284859193494, 664238088423928246579566483655935746695807924062694495126404306361290788561253706421181510449476188038387172722467882193]
2482696698513566590184292572066254640333143735400366745928208268241117181592178071999744746850718587310205478604372055081

"""

宋师父跟我说是 lcg 算法，然后取模运算里有一句很关键的话是，模意义下的除法都是求逆元。公式自己都推的七七八八了，直接除法改逆元就出了，exp：

from Crypto.Util.number import *
import gmpy2
n = 2482696698513566590184292572066254640333143735400366745928208268241117181592178071999744746850718587310205478604372055081
result1 = 1633086272556604467630727869278140040711140555507257984778706962389364338237377391272504059109316040445365656669071569236
result2 = 1206389051656797336925675372412697477889689141174380289961348552709531162180853687116202278892215286522581909284859193494
result3 = 664238088423928246579566483655935746695807924062694495126404306361290788561253706421181510449476188038387172722467882193

tmp1 = result2 - result1
tmp2 = result3 - result2
a = tmp2 * gmpy2.invert(tmp1,n) % n
b = (result2 - a * result1) % n
print(a)
print(b)
flag = (result1 - b) * gmpy2.invert(a,n) % n
print(long_to_bytes(flag))

# 0x01 GKCTF2021 RRRRsa 点击下载

附件如下：

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

flag = b'xxxxxxxxxxxxx'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)
print('c={}'.format(c))

p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = 65537
assert gcd(e1,(p1-1)*(q1-1)) == 1
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(2020 * p1 + q1, 202020, n1)
hint2 = pow(2021 * p1 + 212121, q1, n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))

p2 = getPrime(512)
q2 = getPrime(512)
n2 = p2*q2
e2 = 65537
assert gcd(e1,(p2-1)*(q2-1)) == 1
c2 = pow(q,e2,n2)
hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))
print('hint4={}'.format(hint4))

#c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
#n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
#c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
#hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
#hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
#n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
#c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
#hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
#hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

这题算是考察对模运算的理解和灵活运用，其中用到了费马小定理和二项式定理。用 RSA 对公钥中的 p、q 分别加密。数学运算过程如下图

如果是 mod q，那等式相减的目的就是将等式中的 p 相减消去，相减之后只剩下 q 和系数，可以用 gcd 求出公约数。注意相减的式子要先 mod n 缩小数的大小，这样并不会改变运算结果。最终 exp 如下：

from Crypto.Util.number import *
import gmpy2
c = 13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758

hint1 = 23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2 = 52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n1 = 75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1 = 68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
e = 65537
tmp2 = pow(hint2 - 212121,202020,n1) * pow(2020,202020)
tmp1 = hint1 * pow(2021,202020)
q1 = gmpy2.gcd(tmp2 - tmp1,n1)
print(q1)
p1 = n1 // q1
phi1 = (p1 - 1) * (q1 - 1)
d1 = gmpy2.invert(e,phi1)
p = pow(c1,d1,n1)

n2 = 114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
c2 = 67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
hint3 = 25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4 = 104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

tmp3 = pow(hint3,212121,n2) * pow(2021,202020 * 212121,n2)
tmp4 = pow(hint4,202020,n2) * pow(2020,202020 * 212121,n2)
q2 = gmpy2.gcd(tmp4 - tmp3,n2)
p2 = n2 // q2
phi2 = (p2 - 1) * (q2 - 1)
d2 = gmpy2.invert(e,phi2)
q = pow(c2,d2,n2)
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
n = p * q
m = pow(c,d,n)
print(long_to_bytes(m))

学习 crypto