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

2022.4.13，开个新坑

2023.1.19，20 题完结

# 0x13 unknown easysvp 1.19

附件

from random import randrange
from Crypto.Util.number import *
from gmpy2 import *
from flag import flag


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

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

e = 196611
t = getPrime(1024)
while True:
    p = getPrime(512)
    q = getPrime(512)
    if p > (t//2)**(0.5) or q > (t//2)**(0.5) or q < (t//4)**(0.5):
        continue
    if gcd(p,t)==1 and gcd(p,q)==1:
        break

n = p*q
a = inverse(p,t)
b = a*q % t

x = randrange(1, (t//2)**(0.5))
c1 = pow(bytes_to_long(m1), e, n)
c2 = (x*b+bytes_to_long(m2)) % t

print('n:', n)
print('t:', t)
print('b:', b)
print('c1:', c1)
print('c2:', c2)
'''
n: 65923160983714159174054470515573655706226330836484887232047084356206551027110611733852661357129720187920709446876218553615531690351151400345537469812811754017254876997964169603223262682390304358781343907306701677293241401311458582376923692545390056409390040815766533450665171898894960981350098449471585835983
t: 156735006421025159162464822189709647625666833755415833041315380970290330967501247763901201324107388364754932161997024416664716046695306206076067986718008348395105538562568685715810261941446669628131228936345994680854906523779208112907313194284266511667655498806866506447714590977347633499249461638469397646143
b: 102828034489985130292237328415914374036194592912123145515988805200145853584202889332537743985786669465808768348444018770207326799609832768446997902851310627183128143736647178489337894207754483450029034766480012064411339544711254824382201113260666700562674152083497595259510709102443621597274104424732970983346
c1: 53919877044806667590191317976457216703097157378893548902917302837026217993556841959874040719754382894805766098772727554793887109758342211929068651122821912401228458881370271005861714431415278512010429891161410017074563692738062898727179931757587022730420443768861148908495675732837105452751476067158477074416
c2: 93209672266652558201721906871222852586159974489807496213149282485691823460173568938838492468817777256382818737811311622582977800840264981574839834478715137925028333166737702156942511501971498573467635899900227942924329380167513249979806622469774326486417222407610460860379054991133760924378877816208820000726
'''

缝合怪题，前半部分是模不互素，后半部分的格基规约问题。

模不互素没啥说的，常规思路打就行

from Crypto.Util.number import *
import gmpy2
e = 196611
n = 65923160983714159174054470515573655706226330836484887232047084356206551027110611733852661357129720187920709446876218553615531690351151400345537469812811754017254876997964169603223262682390304358781343907306701677293241401311458582376923692545390056409390040815766533450665171898894960981350098449471585835983
t = 156735006421025159162464822189709647625666833755415833041315380970290330967501247763901201324107388364754932161997024416664716046695306206076067986718008348395105538562568685715810261941446669628131228936345994680854906523779208112907313194284266511667655498806866506447714590977347633499249461638469397646143
b = 102828034489985130292237328415914374036194592912123145515988805200145853584202889332537743985786669465808768348444018770207326799609832768446997902851310627183128143736647178489337894207754483450029034766480012064411339544711254824382201113260666700562674152083497595259510709102443621597274104424732970983346
c1 = 53919877044806667590191317976457216703097157378893548902917302837026217993556841959874040719754382894805766098772727554793887109758342211929068651122821912401228458881370271005861714431415278512010429891161410017074563692738062898727179931757587022730420443768861148908495675732837105452751476067158477074416
c2 = 93209672266652558201721906871222852586159974489807496213149282485691823460173568938838492468817777256382818737811311622582977800840264981574839834478715137925028333166737702156942511501971498573467635899900227942924329380167513249979806622469774326486417222407610460860379054991133760924378877816208820000726
PR.<a> = PolynomialRing(Zmod(t))
f = a ** 2 * n - b
root = f.roots()
print(root)
#[(116231959510358160812755793831584335959100766156535932861226868172580463216816375971999356944597603556117791659485819216769100213826425384473081766229007741782651362591487751335698862068456452058850711298569225829628888753311404538439325209285849892423108708117681509739698109141926240416541118397102587818568, 1), (40503046910666998349709028358125311666566067598879900180088512797709867750684871791901844379509784808637140502511205199895615832868880821602986220489000606612454175971080934380111399872990217569280517637776768851226017770467803574467987984998416619244546790689184996708016481835421393082708343241366809827575, 1)]

a 是质数，所以后面那个是 a，之后用 a 分解 n。发现 e 和 phi 公约数是 3，比较小，用 sage 的 roots 函数就可以解

a = 40503046910666998349709028358125311666566067598879900180088512797709867750684871791901844379509784808637140502511205199895615832868880821602986220489000606612454175971080934380111399872990217569280517637776768851226017770467803574467987984998416619244546790689184996708016481835421393082708343241366809827575
p = gmpy2.invert(a,t)
q = n // p
phi = (p - 1) * (q - 1)

d = gmpy2.invert(e // 3,phi)
c = pow(c1,d,n)
flag1 = b''
R.<x> = Zmod(p)[]
f = x ^ 3 - c
f = f.monic()
res1 = f.roots()
 
R.<x> = Zmod(q)[]
f = x ^3 - c
f = f.monic()
res2 = f.roots()
for i in res1:
    for j in res2:
        ai = [int(i[0]),int(j[0])]
        mi = [p,q]
        flag = CRT_list(ai,mi)
        flag = long_to_bytes(flag)
        if b'flag' in flag:
            flag1 = flag
            break
print(flag1)
#b'flag{9ad0f091075c06'

后面的格基规约需要注意以下数据量的大小。注意题目中给出的 p 和 q 的大小

$p \leq \sqrt{\frac{t}{2}}$ $\sqrt{\frac{t}{4}}\leq q \leq \sqrt{\frac{t}{2}}$

然后根据加密 flag 的等式

c2 = (x*b+bytes_to_long(m2)) % t

$c_2+kt=xb+m_2$

需要注意一下各个量的位数，具体列表如下

c2	k	t	x	b	m2
1024	512	1024	512	1024	151

可以造格子如下

$\begin{bmatrix} x&k&1 \end{bmatrix} \begin{bmatrix} b&0&0\\t&1&0\\c&0&2^{512} \end{bmatrix} \begin{bmatrix} m_2&k&2^{512} \end{bmatrix}$

格子的最后一位需要凑平，具体有一个 Hermite 定理可以计算一下界。

简单来说 LLL 算法会返回当前格中欧几里得范数最小的一组向量，如果最后填 1，我们预期得到的结果为 $[m_2 \quad k \quad 1]$ ，但是这样的结果并不是最小的结果，所以在格的最末尾填上 $2^{512}$ 或者更大的数，才能将该向量作为格中最小的结果给格基规约出来。

mat = [
    [b,0,0],
    [t,1,0],
    [c2,0,2 ** 512]
]
mat = matrix(ZZ,mat)
print(mat.LLL())
flag2 = abs(int(mat.LLL()[-1][0]))
flag2 = long_to_bytes(flag2)
#b'7589e989433efffd76}'

# 0x12 2021 第五空间 ecc 1.10

附件

print 'Try to solve the 3 ECC'

from secret import flag
from Crypto.Util.number import *
assert(flag[:5]=='flag{')
flag = flag[5:-1]
num1 = bytes_to_long(flag[:7])
num2 = bytes_to_long(flag[7:14])
num3 = bytes_to_long(flag[14:])

def ECC1(num):
	p = 146808027458411567
	A = 46056180
	B = 2316783294673
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

def ECC2(num):
	p = 1256438680873352167711863680253958927079458741172412327087203
	#import random
	#A = random.randrange(389718923781273978681723687163812)
	#B = random.randrange(816378675675716537126387613131232121431231)
	A = 377999945830334462584412960368612
	B = 604811648267717218711247799143415167229480
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q
	factors, exponents = zip(*factor(E.order()))
	primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
	print primes
	dlogs = []
	for fac in primes:
		t = int(int(P.order()) / int(fac))
		dlog = discrete_log(t*Q,t*P,operation="+")
		dlogs += [dlog]
		print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
	print num
	print crt(dlogs,primes)



def ECC3(num):
	p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
	A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
	B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

ECC1(num1)
print '=============='
ECC2(num2)
print '=============='
ECC3(num3)

out

Try to solve the 3 ECC
Elliptic Curve defined by y^2 = x^3 + 46056180*x + 2316783294673 over Finite Field of size 146808027458411567
P: (119851377153561800 : 50725039619018388 : 1)
Q: (22306318711744209 : 111808951703508717 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 377999945830334462584412960368612*x + 604811648267717218711247799143415167229480 over Finite Field of size 1256438680873352167711863680253958927079458741172412327087203
P: (550637390822762334900354060650869238926454800955557622817950 : 700751312208881169841494663466728684704743091638451132521079 : 1)
Q: (1152079922659509908913443110457333432642379532625238229329830 : 819973744403969324837069647827669815566569448190043645544592 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
P: (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 : 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610 : 1)
Q: (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 : 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537 : 1)

决定恶补一下 ECC，寒假在家里也没什么事情做。

题目中三段数据都是求 $Q=\text{num} \times P$ 中的 num，三部分对应了三种不同的情况，依次说明。

第一部分可以看出数据很小，椭圆曲线的数学困难问题就是基于离散对数问题的求解，数据很小直接用 sage 梭就行

#part1
p = 146808027458411567
a = 46056180
b = 2316783294673
E = EllipticCurve(GF(p),[a,b])
P = E(119851377153561800,50725039619018388)
Q = E(22306318711744209,111808951703508717)
flag1 = P.discrete_log(Q)
# print(long_to_bytes(flag1))

第二部分数据变大了，但是阶部分光滑。求出阶看分解可以看出只有最后一个阶是很大的，运用前面几个数的分解就可以将答案求出。算法思想与 hellman 一致

#part2
p = 1256438680873352167711863680253958927079458741172412327087203
a = 377999945830334462584412960368612
b = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[a,b])
P = E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q = E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)

E_order = E.order()
factors, exponents = zip(*factor(E_order))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
# print(primes)
dlogs = []
# print(P.order())

for fac in primes:
    t = int(E_order) // int(fac)
    dlog = discrete_log(t * Q,t * P,operation="+")
    dlogs.append(dlog)
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog))
flag2 = crt(dlogs,primes)
# print(long_to_bytes(flag2))

第三部分曲线的阶和模数 $p$ 相等，使用 smartAttack 方法求解，原理不懂，记个板子。参考 https://wstein.org/edu/2010/414/projects/novotney.pdf

#part3
p = 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a = 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b = 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
E = EllipticCurve(GF(p),[a,b])
P = E(10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861,8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q = E(964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927,5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

flag3 = SmartAttack(P,Q,p)

# 0x11 2023realworld 体验赛 1.9

附件

#!/usr/bin/env python3
from random import randrange
from Crypto.Cipher import AES

p = 193387944202565886198256260591909756041

i = lambda x: pow(x, p-2, p)

def add(A, B):
    (u, v), (w, x) = A, B
    assert u != w or v == x
    if u == w: m = (3*u*w + 4*u + 1) * i(v+x)
    else: m = (x-v) * i(w-u)
    y = m*m - u - w - 2
    z = m*(u-y) - v
    return y % p, z % p

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

x = randrange(p)
aes = AES.new(x.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16))
flag = open('flag.txt').read().strip()
cipher = aes.encrypt(flag.ljust((len(flag)+15)//16*16).encode())
print(*mul(x, (4, 10)), cipher.hex(), file=open('flag.enc', 'w'))
#65639504587209705872811542111125696405 125330437930804525313353306745824609665 b3669dc657cef9dc17db4de5287cd1a1e8a48184ed9746f4c52d3b9f8186ec046d6fb1b8ed1b45111c35b546204b68e0

贴个原题链接 https://github.com/p4-team/ctf/tree/master/2018-12-08-hxp/crypto_curve12833227

首先根据 add 函数

def add(A, B):
    (u, v), (w, x) = A, B
    assert u != w or v == x
    if u == w: m = (3*u*w + 4*u + 1) * i(v+x)
    else: m = (x-v) * i(w-u)
    y = m*m - u - w - 2
    z = m*(u-y) - v
    return y % p, z % p

其中 if u == w: m = (3*u*w + 4*u + 1) * i(v+x) ，函数 i 为求逆元，通过对此判别式积分可以推算出曲线方程为 $y^2=x^3+2x^2+x+C$ ，又因为点 (4,10) 在曲线上，可以得出 $C=0$ ，则曲线方程为 $y^2=x^3+2x^2+x$ 。其存在奇点 $(-1,0)$ 。

参考本篇文章 https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp 可以求出 x，exp 如下

#sage
p = 193387944202565886198256260591909756041
# P.<x> = GF(p)[]
PR.<x> = PolynomialRing(Zmod(p))
f = x ** 3 + 2 * x ** 2 + x
P = (4,10)
Q = (65639504587209705872811542111125696405,125330437930804525313353306745824609665)
# root = f.roots()
# print(root)
#Singular point (-1,0)
k = 193387944202565886198256260591909756040
ff = f.subs(x = x - 1)
print(ff.factor())
#(x + 193387944202565886198256260591909756040) * x^2
PP = (P[0] - 193387944202565886198256260591909756040,P[1])
QQ = (Q[0] - 193387944202565886198256260591909756040,Q[1])
t = GF(p)(193387944202565886198256260591909756040).square_root()

u = (PP[1] + t * PP[0]) / (PP[1] - t * PP[0]) % p
v = (QQ[1] + t * QQ[0]) / (QQ[1] - t * QQ[0]) % p
x = v.log(u)
#x = 4470735776084208177429085432176719338

结果发现用这个 x 无法求出 flag，说明还要算上阶，最后得到 flag

#sage
x = 4470735776084208177429085432176719338
print(x)
kk=u.multiplicative_order()
enc = bytes.fromhex('b3669dc657cef9dc17db4de5287cd1a1e8a48184ed9746f4c52d3b9f8186ec046d6fb1b8ed1b45111c35b546204b68e0')
while True:
    x += kk
    if x > p:
        break
    aes = AES.new(long_to_bytes(x),AES.MODE_CBC,bytes(16))
    flag = aes.decrypt(enc)
    print(flag)
b'rwctf{Singular_Elliptic_Curve_is_easy_to_break} '

# 0x10 2022 年江西省大学生信息安全技术大赛初赛 easylattice2 12.30

附件

from Crypto.Util.number import *
FLAG = b'DASCTF{xxx}'
FLAG = FLAG[7:-1]
q = 2^256

t = 40

x = bytes_to_long(FLAG)

A = []
B = []
for i in range(t):
    alpha = ZZ(Zmod(q).random_element())
    A.append(alpha)
    B.append((alpha*x % q)>>(256-8))

print(A)
print(B)

'''
[84545605098919357883342049785700230040968693996530839945990653400855504906802, 64318627050238621913856342658149309111953371364362248466973076501370171739866, 44833833707095656654503484256000993796921007419233493881691012114619868094560, 73232050050978729749876385355125922365994635840614577909712939078465889486927, 49705754343680217825731689069247222931464457288368278401756955216063821460713, 7773716507069077286176384328311704695943346186956011585647833650872546985704, 35367871748426097942891975752985612532178159522392487799137847162793844297259, 62764829622761591382777789741125592700340145715067712695838863315679297865421, 46935977121421979257863144003719821155118122728798766585021557461458554711048, 42939177889039484362479588720740991357365976148437177435101168045290359758410, 97121564005524888337068660871158366982592875907457306709790495639937090537232, 76886701253807415588943538291675931582703667239932988501427868196293288708454, 26135505377348779821008049265473415821466025876911023611852970773014088341697, 110995849442144940870427048133899156608419550927266942442877901533603266505363, 5044203606638773879637402874988459469968364471257924922588754307799172436111, 2665604848469247498374079779039877909487959491708401136315883984900023830087, 106082111880140350563516845222048616300919360816856986713701434503153473598272, 87595120997346701153771844173354962363505990024749960032323522802170210856998, 30735469834005371392098522683460862628728000563099737246414787689161654170005, 74359883667893599589405273462303347696610905658857136168118529986363407255898, 20204197780205297843081711648226294480448019326273455617021195999857044167942, 63096262783751516980983192186356065149841431907259395141910451383433704709184, 12152056244753544826439613524228624069728455796264166814352560273933151913592, 114889255822548504838278221664465176494052041487922417522436000874970493661674, 12697645037989154507748939749910714768436117428576511237333427290637745232352, 75299588851358924593106633315972752823613401831656849845776220971408926864757, 66252398829865053651294427099510477412334399373429337393371739360897428551080, 96532198311446483093375170979824934072692435507945852599941894677854324762234, 6139286263397899992951419178195053475916568135172144122694657112490581510300, 34376460022522877744382639064317171686750419881002499940120807593906622629919, 96501742323730881521910813296284942340349016330837155159335201986513386546858, 77138784030740465724716203856139754018741545301925742743136359127104441232992, 57759435811750287940649147535145228583155499038537697675728235258033065901677, 27297361883253038600939612200992657560439960674763420079462172997044428666986, 23401758127641977798857113971736125468419263857787075540336458711365758576497, 68532606512738331105309350681916480349485076493586056552769624280354609427017, 71959573997311126544920410961743015991934367773498267843192433783459395347384, 86568022924301252995070743709076133954812487027394051823868169701714096819788, 65483599135089201771470413647566590147384718070198959226794224092625758570289, 2353939170592029768060112909867989273389149830947499985690619642365711664985]
[231, 134, 184, 26, 1, 252, 141, 254, 219, 145, 192, 30, 211, 114, 242, 175, 180, 134, 76, 238, 3, 108, 164, 227, 220, 212, 197, 226, 147, 252, 241, 249, 89, 26, 98, 232, 213, 192, 145, 36]
'''

一眼 HNP 问题，关于 HNP 问题春哥知乎里基于 dsa 的 HNP 问题写得很详细很透彻，这里算是一个运用，还有 Tover 佬的写的也很全面（膜拜 ing）。

详细原理不能说完全懂，大概的做法是知道了。

首先题目的意思是有以下多组式子 $A_ix \equiv B_i \bmod q$ ， $x$ 是要求的 flag，给了全部的 $A_i$ ，但是每个 $B_i$ 只给了前 8 位，所以有 $a_ix \equiv 2^{248}b_i + B_i\bmod q$ ，方便区分就，小写变量均为已知，大写变量均为未知。

这里直接说做法。

首先要先通过运算把 $x$ 给消去，即由 $a_ix \equiv 2^{248}b_i + B_i\bmod q$ 和 $a_0x \equiv 2^{248}b_0 + B_0\bmod q$ 得到

$B_i=2^{248}(b_0a_ia_0^{-1}-b_i)+B_0a_ia_0^{-1} - l_iq$

和春哥的做法一样，目的是让较小的 $B_i$ 系数为 1，所以这样构造。也不一定要选第 0 组，要选择方便求逆元的。本题就应该选择第 3 组。之后令 $D_i=2^{248}(b_0a_ia_0^{-1}-b_i)$ ， $E_i=a_ia_0^{-1}$ ，有等式 $B_i=D_i+E_iB_0-l_iq$ 于是可以构造格如下

$\begin{bmatrix} l_1&l_2&l_3&\dots&B_0&1 \end{bmatrix} \begin{bmatrix} -q& & & &\\ &-q& & &\\ & &-q& &\\ E_1&E_2&E_3&1& &\\ D_1&D_2&D_3& &2^{247} \end{bmatrix} \begin{bmatrix} B_1&B_2&B_3&\dots&B_0&2^{247} \end{bmatrix}$

推荐使用 BKZ 算法，准确率更高。且 BKZ 算法格基规约后第一行通常都是最短向量。

得到 $B_0$ 之后正常求逆即可得到 x 的值，完整 exp 如下

import gmpy2
from Crypto.Util.number import *
A = [84545605098919357883342049785700230040968693996530839945990653400855504906802, 64318627050238621913856342658149309111953371364362248466973076501370171739866, 44833833707095656654503484256000993796921007419233493881691012114619868094560, 73232050050978729749876385355125922365994635840614577909712939078465889486927, 49705754343680217825731689069247222931464457288368278401756955216063821460713, 7773716507069077286176384328311704695943346186956011585647833650872546985704, 35367871748426097942891975752985612532178159522392487799137847162793844297259, 62764829622761591382777789741125592700340145715067712695838863315679297865421, 46935977121421979257863144003719821155118122728798766585021557461458554711048, 42939177889039484362479588720740991357365976148437177435101168045290359758410, 97121564005524888337068660871158366982592875907457306709790495639937090537232, 76886701253807415588943538291675931582703667239932988501427868196293288708454, 26135505377348779821008049265473415821466025876911023611852970773014088341697, 110995849442144940870427048133899156608419550927266942442877901533603266505363, 5044203606638773879637402874988459469968364471257924922588754307799172436111, 2665604848469247498374079779039877909487959491708401136315883984900023830087, 106082111880140350563516845222048616300919360816856986713701434503153473598272, 87595120997346701153771844173354962363505990024749960032323522802170210856998, 30735469834005371392098522683460862628728000563099737246414787689161654170005, 74359883667893599589405273462303347696610905658857136168118529986363407255898, 20204197780205297843081711648226294480448019326273455617021195999857044167942, 63096262783751516980983192186356065149841431907259395141910451383433704709184, 12152056244753544826439613524228624069728455796264166814352560273933151913592, 114889255822548504838278221664465176494052041487922417522436000874970493661674, 12697645037989154507748939749910714768436117428576511237333427290637745232352, 75299588851358924593106633315972752823613401831656849845776220971408926864757, 66252398829865053651294427099510477412334399373429337393371739360897428551080, 96532198311446483093375170979824934072692435507945852599941894677854324762234, 6139286263397899992951419178195053475916568135172144122694657112490581510300, 34376460022522877744382639064317171686750419881002499940120807593906622629919, 96501742323730881521910813296284942340349016330837155159335201986513386546858, 77138784030740465724716203856139754018741545301925742743136359127104441232992, 57759435811750287940649147535145228583155499038537697675728235258033065901677, 27297361883253038600939612200992657560439960674763420079462172997044428666986, 23401758127641977798857113971736125468419263857787075540336458711365758576497, 68532606512738331105309350681916480349485076493586056552769624280354609427017, 71959573997311126544920410961743015991934367773498267843192433783459395347384, 86568022924301252995070743709076133954812487027394051823868169701714096819788, 65483599135089201771470413647566590147384718070198959226794224092625758570289, 2353939170592029768060112909867989273389149830947499985690619642365711664985]
B = [231, 134, 184, 26, 1, 252, 141, 254, 219, 145, 192, 30, 211, 114, 242, 175, 180, 134, 76, 238, 3, 108, 164, 227, 220, 212, 197, 226, 147, 252, 241, 249, 89, 26, 98, 232, 213, 192, 145, 36]
cc = 3
q = 2 ** 256
t = 40
D = []
E = []
for i in range(0,t):
    if i == cc:
        continue
    else:
        tmp1 = (B[cc] * A[i] * gmpy2.invert(A[cc],q) - B[i]) * 2 ** 248 % q
        tmp2 = A[i] * gmpy2.invert(A[cc],q) % q
        D.append(tmp1)
        E.append(tmp2)
mat = [[0 for _ in range(41)] for _ in range(41)]
print(len(D))
for i in range(0,t - 1):
    mat[i][i] = -q
    mat[39][i] = E[i]
    mat[40][i] = D[i]
mat[39][39] = 1
mat[40][40] = 2 ** 247
mat = matrix(ZZ,mat)
# print(mat.BKZ())
ans = abs(mat.BKZ()[0][-2])
bcc = B[cc] * 2 ** 248 + ans
x = bcc * gmpy2.invert(A[cc],q) % q
print(long_to_bytes(x))

# 0x0F 2022geek Crypto1957 11.10

附件

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

key = bytes_to_long(flag) 
f = open('message.txt','r').read().split('\n')
cipher = open('cipher.txt','w') 
for i in f: 
    i = bytes_to_long(i.encode()) 
    c = i ^ key 
    cipher.write(hex(c)[2:]+'\n') 
cipher.close()

经典 mtp，参考 https://www.ruanx.net/many-time-pad/

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False


def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)


dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('cipher.txt', 'r').readlines()]
print(c)
msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

# know(1, 6, 'p')
# know(4, 1, 'o')
# know(11,10,'i')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

# 0x0E 2022 ISCTF ezzzzzzzzzzzzzzzzzlattice 11.2

附件

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

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(340)
e = getPrime(27)
useful = getPrime(1024)
c = (inverse(e, q) * useful + pow(m, e, q)) % p
with open('output','w+') as f:
    f.write(f'p = {p}\nq = {q}\nc = {c}\nuseful = {useful}')

经典格子题，有等式如下 $c=t\times u+s \bmod p$ ，其中定义 t 为 e 的逆元，s 定义为 $m^e \bmod q$ 。

观察位数，c u p 都是 1024 位，q s 是 340 位，从某位神深邃的思想中，学到了一些做题快餐：小的放结果，已知的放矩阵。结果的大小得差不太多，由于位数的原因，得构造一个三维的格子。

跟据等式 $c+kp-tu=s$ 可知

$\begin{bmatrix} -t&k&1 \end{bmatrix} \begin{bmatrix} u&0&0\\p&1&0\\c&0&1 \end{bmatrix} \begin{bmatrix} s&-k&1 \end{bmatrix}$

可以得到 s 的值，得到了 s 之后其他量也就很快能出来了。

需要注意的是模数 q 只有 340 位，考虑到 flag 的大小可能超过 340 位，进行一个小范围的爆破

import gmpy2
from Crypto.Util.number import *
p = 157528135408677299394292236808407130951620182277485861264162367221003923311026835340974796733969066338128486003687892984888625395846811728890576334899010454107820204146796395164875654422020481368009883567020291526109447619934985261676396363315066221941991907441551816700543054518214048084585510572273143302929
q = 1442705299941797183684818615170726432069333234814734331406043466619811163894111214168224392907643854069
c = 133435253885105904681139014309955886539710389070811311502821772509611736349656307170673935962481372815353262899448626430304691786429011183960239913678295381009683495881961582566729076446859372293063364241805786413804485568317533502444560563638886447542766320382309683259017825708340404274999458766205770820533
u = 120769987044261474693385398937509234270805384830942774998331036756015602254500864686090818859805146371437761470282545762646846799062287962879226076629580866415238728781778876557024691706000280566550610727659583989813062963375313642707997246101611714406510716765838248871330574233154650330128833595352286430109
mat = [
    [u,0,0],
    [p,1,0],
    [c,0,1]
]
mat = matrix(ZZ,mat)
s = int(mat.LLL()[0][0])
t = (c - s) * gmpy2.invert(u,p) % p
e = gmpy2.invert(t,q)
d = gmpy2.invert(e,q - 1)
m = pow(s,d,q)
assert c == (inverse(e, q) * u + pow(m, e, q)) % p
for i in range(100):
    ans = m + i * q
    flag = long_to_bytes(ans)
    if b'ISCTF' in flag:
        print(flag)

# 0x0D 2022 0xGame week4 oracle 10.22

附件

import socketserver
from Crypto.Util.number import *
import os
import signal
import string
from random import *
from secret import _flag

banner = r"""                               
  ____        _          ___                 _      
 | __ ) _   _| |_ ___   / _ \ _ __ __ _  ___| | ___ 
 |  _ \| | | | __/ _ \ | | | | '__/ _` |/ __| |/ _ \
 | |_) | |_| | ||  __/ | |_| | | | (_| | (__| |  __/
 |____/ \__, |\__\___|  \___/|_|  \__,_|\___|_|\___|
        |___/                                       

"""
menu = r"""
MENU:
1.GetKey
2.Encrypt
3.Decrypt
4.Quit
"""


def GenerateRSAKey():
    n, phi = 1, 1
    for i in range(4):
        while True:
            p = getPrime(1000)
            if isPrime(p):
                break
        n *= p
        phi *= (p - 1)
    e = getPrime(randint(20, 24))
    d = inverse(e, phi)
    return n, e, d


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 9182
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def printf(self, msg, newline=True):
        if newline:
            msg += "\n"
        self.request.sendall(msg.encode())

    def scanf(self, prompt='> '):
        self.printf(prompt, newline=False)
        return self._recvall()

    def handle(self):
        signal.alarm(1200)
        self.printf(banner)
        n, e, d = GenerateRSAKey()
        flag = _flag
        flag = bytes_to_long(os.urandom(390) + b"          " + flag.encode() + b"          " + os.urandom(30))
        for ___ in range(1607087):
            self.printf(menu)
            try:
                op = int(self.scanf())
                if op == 1:
                    self.printf(f"n={n}")
                    self.printf(f"e={e}")
                    self.printf(f"c={pow(flag, e, n)}")
                elif op == 2:
                    m = int(self.scanf("Enter your plaintext in decimal format >"))
                    c = pow(m, e, n)
                    msg = long_to_bytes(c).hex()[-2:]
                    self.printf(f"The last byte of your Ciphertext is: {msg}")
                elif op == 3:
                    c = int(self.scanf("Enter your ciphertext in decimal format >"))
                    m = pow(c, d, n)
                    msg = long_to_bytes(m).hex()[-2:]
                    self.printf(f"The last byte of your Plaintext is: {msg}")
                else:
                    break
            except:
                self.printf("Wrong Input")
                break
        self.printf("Quitting...")


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10003
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print("Server at 0.0.0.0 port " + str(PORT))
    server.serve_forever()

详细参考 RSA LSB Oracle 攻击原理分析，大概介绍一下题目。

一个 RSA 系统，首先给出初始的公钥 (n,e) 及公钥加密信息之后得到的密文 c，之后与系统交互，构造密文 c 与靶机交互，给出密钥解密后明文 m 的最后一字节 (可以理解成最后 256 位)。也可以构造明文 m 与靶机交互，给出明文加密后密文 c 的最后一字节 (用处不大，毕竟这个环节本地都能运算)。

参考了资料之后，应该这样理解这个密码系统。

首先将明文 m 转化成 256 进制，即 $m=256^{n}{a_n} + 256^{n-1}{a_{n-1}} + 256^{n-2}{a_{n-2}} + \dots +256^{2}{a_2} + 256^{1}{a_1} + 256^{0}{a_0}$ ，问题转化求所有的 a。

尝试构造密文 $cc = 256^{-ei} \times c \bmod n$ ，得到的明文就有一定的规律

密文 $cc=c \bmod n$ ，明文 $mm={a_0} \bmod 256$

密文 $cc = 256^{-e}c \bmod n$ ，明文 $mm={a_1} + (256^{-1}{a_0} \bmod n) \bmod 256$

密文 $cc=256^{-2e}c \bmod n$ ，明文 $mm={a_2} + (256^{-1}{a_1}+256^{-2}{a_0} \bmod n) \bmod 256$

...

至此， ${a_0},{a_1},{a_2}\dots$ 可以依次全部计算出。

完整 wp 为

import gmpy2
from pwn import *
from Crypto.Util.number import *
def getinit():
    r.recvuntil(b'> ')
    r.send(b'1')
    r.recvuntil(b'n=')
    n = int(r.recvline()[:-1].decode())
    r.recvuntil(b'e=')
    e = int(r.recvline()[:-1].decode())
    r.recvuntil(b'c=')
    c = int(r.recvline()[:-1].decode())
    return n,e,c

def getm(c):
    r.recvuntil(b'> ')
    r.send(b'3')
    r.recvuntil(b"Enter your ciphertext in decimal format >")
    r.send(str(c).encode())
    r.recvuntil(b'The last byte of your Plaintext is: ')
    m = int(r.recvline()[:-1].decode(),16)
    return m

r = remote('124.223.224.73',10003)
n,e,c = getinit()
Mod = 256
inv = gmpy2.invert(Mod,n)
cnt = 0
flag = 0
pad = 0
ans = 0
while True:
    cc = pow(inv,e * cnt,n) * c % n
    mm = getm(cc)
    ans = (mm - (inv * pad) % n) % Mod
    pad = pad * inv + ans
    flag += ans * Mod ** cnt
    cnt += 1
    print(cnt,long_to_bytes(flag))
    if b'0xGame' in long_to_bytes(flag):
        print(long_to_bytes(flag))
        break
r.interactive()

# 0x0C 2022 强国杯北部 babysecret 10.20

附件

from Crypto.Util.number import *
# from secret import flag
flag = b'flag{*****}'
p = getPrime(512)
q = getPrime(512)
while q > p: 
    q = getPrime(512)
a = getPrime(1023)
b = getPrime(1023)
e = 65537
n = p * q
r = p - q
t = (a * pow(r,3,n) + b * r + 1) % n
q_high = q >> 300
c = pow(bytes_to_long(flag),e,n)

print("n = {}".format(n))
print("e = {}".format(e))
print("a = {}".format(a))
print("b = {}".format(b))
print("t = {}".format(t))
print("q_high = {}".format(q_high))
print("c = {}".format(c))
print(p)
print(q)

这题实际上考察 cop 的使用，最开始的思路是把 q 还原，毕竟 q 给了高位，然后尝试用式子 $t \equiv ar ^ {3} + br + 1 \bmod n$ 梭 q 的低位，但是最后出来的式子为 $tq \equiv -aq^{4} - bq^{2} + q \bmod n$ ，到这一步不能再约去 q 了，因为 q 与 n 互为质因数，不存在逆元，最简只能是 4 次，而未知数为 300 位左右，四次方之后超出了 n 的范围，所以 cop 是出不来的。

看了题解之后发现，t 的多项式内他没有进行同乘 q 的操作，这样也就没有扩大次数。直接用 q 的高位算出 r 的高位，再代入 cop 得解。其中

r = p - q
rr = n // (q_high * 2 ** 300) - (q_high * 2 ** 300)
print(bin(r))
print(bin(rr))

本地生成一组数据可以看出，模拟的 rr 中只有末位 300 位左右的结果是不一样的，前面 200 多位结果是与真实值相同的，且没有扩大未知数的次方

exp 如下

from Crypto.Util.number import *
import gmpy2
n = 118088182400914872425507968305001164877208606657359236256953881915206277084877253319397356024962095850764800309318427035601324751558659744194849519524768634089878781543795243844210935970526496301486149610251619204865266958793387724445198146924553969795907722472468946829250329488057262816583502807822047775749
e = 65537
a = 89550668608326948747166067438829922823887013755318531189964699343980590520537880532984839411681664094386478706293102571338952459853162555403593475801893006583685834858174847392363091151867265947345240856071768997776673534676668988013380416401922279287936776316984917630501973335231159056002526848423043741739
b = 74736873984456627360375165191987470664126749405775465193769364774937103162073685392907101869079202748656338724470334837227618563620904690556042686593201928845784888493510324333317558940643204638015713789725349483078890281349489771681063469660086262184331856737942824520401011011367209215669180904463091704793
t = 55298221876719248720462722179593967045120179680181438454697067031826253837624893816677443873366419002676868473736730359161158982104951679819748784973352864934703454256788638969088766978407029001891853043007408744014019161425106707841280190111967859927296650163135281286639261786835931577107901630806430604953
q_high = 4873455269440533882208474100574590898238440656351420611293551205
c = 72083095376657291976415139371103988590583687265551728324585228973734111764075986640135709899922822926656873211820340541735802658976140345336179744983481132768179022018280627646669824902791379704259415594071797631422474951050783918408844716193804627942306938224043576608092708196941811171855265283550843594808
PR.<x> = PolynomialRing(Zmod(n))
rr = n // (q_high * 2 ** 300) - (q_high * 2 ** 300)
r = (rr // (2 ** 310)) * 2 ** 310 + x
f = a * r ** 3 + b * r + 1 - t
f = f.monic()
root = f.small_roots(X=2^310,epsilon = 0.04)
print(root)
r = int((rr // (2 ** 310)) * 2 ** 310 + root[0])
delta = r ** 2 + 4 * n
# print(gmpy2.iroot(delta,2))
q = (-r + gmpy2.iroot(delta,2)[0]) // 2
assert n % q == 0
p = n // q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))

# 0x0B 2022 羊城杯 LRSA 10.17

附件

import gmpy2
from pwn import *
from hashlib import sha256
import string
from Crypto.Util.number import *
from random import *


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

m=bytes_to_long(flag)

def getPQ(p,q):
    P=getPrime(2048)
    Q=getPrime(2048)
    t=(p*P-58*P+q)%Q
    assert (isPrime(Q))
    return P,Q,t

B=getRandomNBitInteger(11)
p=getPrime(B)
q=getPrime(B)
n=p*q
e=65537
c=pow(m,e,n)
P,Q,t=getPQ(p,q)

print("B=",B)
print("P*P*Q=",P*P*Q)
print("P*Q*Q=",P*Q*Q)
print("t=",t)
print("c=",c)

P 和 Q 都很容易得到，关键在构成 t 的同余中 $t \equiv (p - 58) \times P + q \bmod Q$ ，其中 t 为 44，即 $44-q = (p-58)P+kQ$ ，其中 P 和 Q 已知，由此可构造格

$\begin{bmatrix}p-58&k\end{bmatrix}\begin{bmatrix}P&1\\Q&0\end{bmatrix}\begin{bmatrix}44-q&p-58\end{bmatrix}$

格基规约之后可以得到 q 和 p，完整 wp 为

from Crypto.Util.number import *
import gmpy2
B = 1023
pp1 = 17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
pp2 = 17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
t = 44
c = 4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
e = 0x10001
pq = gmpy2.gcd(pp1,pp2)
P = pp1 // pq
Q = pp2 // pq
assert P * P * Q == pp1
mat = matrix(ZZ,[[P,1],[Q,0]]).LLL()
q = int(abs(mat[0][0]) + 44)
p = int(abs(mat[0][1]) + 58)
n = p * q
assert isPrime(p) == True
assert isPrime(q) == True
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))

# 0x0A 2022BUUCTF * CBCTF LittleRSA 10.17

附件

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
phi = (p-1)*(q-1)
e = 65537
n = p * q
c = pow(m, e, n)

s = getPrime(300)
N = getPrime(2048)
g = p * inverse(s,N)**2 % (N**2)
print(N)
print(g)
print(n)
print(c)

'''
19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
'''

已知 $g = p \times s^{-2} \bmod N^{2}$ ，写成等式就是 $s^{2}g = p + k N^{2}$ 。观察位数，s 有 300 位，g 有 4093 位，p 有 512 位，N 有 2048 位。其中 g，N 已知。

预期解是用格子做的，首先放出非预期解

构造 $s^{2}q \equiv n g^{-1} \bmod N$ ，同余式右边全为已知量。且 N 值过大，同余式左边不发生取模，为真实值，之后再 gcd 即可的得到 q 的值。

from Crypto.Util.number import *
import gmpy2
e = 0x10001
N = 19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
g = 101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
n = 90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
c = 51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
tmp = n * gmpy2.invert(g,N) % N
q = gmpy2.gcd(tmp,n)
p = n // q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

格子的做法是，构造等式 $s^{2}g=p+kN$ ，其中 g，N 为已知值构造格

$\begin{bmatrix}s^{2}&k\end{bmatrix}\begin{bmatrix}g&1\\N&0\end{bmatrix}\begin{bmatrix}p&s^{2}\end{bmatrix}$

之后格基规约即可得到 $p$ 和 $s^2$ ，exp 如下

from Crypto.Util.number import *
import gmpy2
e = 0x10001
N = 19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
g = 101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
n = 90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
c = 51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
mat = matrix(ZZ,[[g,1],[N,0]]).LLL()
print(mat)
p = abs(mat[0][0])
assert n % p == 0
q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
m = int(pow(c,d,n))
print(long_to_bytes(m))

# 0x09 2022WMCTF ECC 9.16

附件

flag bits: 606
e = 0x10001
n = 61262574892917665379101848600282751252633178779864648655116434051615964747592676204833262666589440081296571836666022795166255640192795587508845265816642144669301520989571990670507103278098950563219296310830719975959589061794360407053224254135937766317251283933110936269282950512402428088733821277056712795259
c = 16002162436420434728223131316901476099110904029045408221515087977802746863468505266500673611412375885221860212238712311981079623398373906773247773552766200431323537510699147642358473715224124662007742017000810447999989426207919068340364725395075614636875116086496704959130761547095168937180751237132642548997
G = (3364552845709696244757995625685399274809023621531082895612949981433844727622567352338990765970534554565693355095508508160162961299445890209860508127449468 : 4874111773041360858453223185020051270111929505293131058858547656851279111764112235653823943997681930204977283843433850957234770591933663960666437259499093 : 1)
3G = (8240596254289477251157504980772167439041663401504657696787046343848644902166655624353107697436635678388969190302189718026343959470011854412337179727187240 : 4413479999185843948404442728411950785256136111461847698098967018173326770728464491960875264034301169184074110521039566669441716138955932362724194843596479 : 1)

题目提示了是 ECC 问题，给的点 G 和 3G 应该是椭圆曲线上的点。椭圆曲线上的点满足关系式 $y^2 \equiv x^3+ax+b \bmod p$ ，其中加法规则如下。

椭圆曲线上已知两个点 $(x_1,y_1)(x_2,y_2)$ ，可以利用公式算出第三点。

${x_3} = s^2-{x_1}-{x_2}$

${y_3}=s({x_1}-{x_3})-{y_1}$

有限域的椭圆曲线要求 $4a^3+27b^2 \not =0$

当两点不同时， $s=({y_2}-{y_1})/({x_2}-{x_1})$ 。当两个点相同时， $s=({3x^2+a})/({2y})$ 。

本题首先利用三倍点的关系求出 a 的值

再利用关系式 $G+G=3G-G$ 求出 $kp$ ，值得注意的是，若 $G$ 为 $(x1,y1)$ ，则 $-G$ 为 $(x1,-y1)$ ，仅有 y 的值为负

两种关系式表达出的 ${x_2}$ 分别为 ${x_2}=((3{x_1}^2+a)/(2{y_1}))^2-2{x_1}$ 和 ${x_2}=(({y_3}+{y_1})/({x_3}-{x_1}))^{2}-({x_3}+{x_1})$ ，联立得到的值为 $kp$ ，之后与 n 求公约数可得解

from Crypto.Util.number import *
import gmpy2
e = 0x10001
n = 61262574892917665379101848600282751252633178779864648655116434051615964747592676204833262666589440081296571836666022795166255640192795587508845265816642144669301520989571990670507103278098950563219296310830719975959589061794360407053224254135937766317251283933110936269282950512402428088733821277056712795259
c = 16002162436420434728223131316901476099110904029045408221515087977802746863468505266500673611412375885221860212238712311981079623398373906773247773552766200431323537510699147642358473715224124662007742017000810447999989426207919068340364725395075614636875116086496704959130761547095168937180751237132642548997
x0,y0 = (3364552845709696244757995625685399274809023621531082895612949981433844727622567352338990765970534554565693355095508508160162961299445890209860508127449468,4874111773041360858453223185020051270111929505293131058858547656851279111764112235653823943997681930204977283843433850957234770591933663960666437259499093)
x3,y3 = (8240596254289477251157504980772167439041663401504657696787046343848644902166655624353107697436635678388969190302189718026343959470011854412337179727187240,4413479999185843948404442728411950785256136111461847698098967018173326770728464491960875264034301169184074110521039566669441716138955932362724194843596479)

a = (y3 ** 2 - y1 ** 2 - (x3 ** 3 - x1 ** 3))/(x3 - x1)
# print(a)
tmp = (x3 - x1) ** 2 * ((3 * x1 ** 2 + a) ** 2 - 8 * x1 * y1 ** 2) - (4 * y1 ** 2 * ((y3 + y1) ** 2 - (x3 + x1) * (x3 - x1) ** 2))
p = int(gcd(tmp,n))
a %= p
b = (y1 ** 2 - x1 ** 3 - a * x1) % p
q = int(n // p)
d = gmpy2.invert(e,(p - 1) * (q - 1))
m = int(pow(c,d,n))
piece_bits = 202
flag = (a << (2 * piece_bits)) + (b << piece_bits) + m
print(b'wmctf{'+long_to_bytes(flag)+b'}')

# 0x08 2022TeamItalyCTF lazy-platform 9.8

附件

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import random
import signal
import os

TIMEOUT = 300
FLAG = os.environ.get("FLAG", "flag{test}").encode()
def getrandbytes(n: int) -> bytes:
    return random.getrandbits(n * 8).to_bytes(n, "little")


def handle():
    print("Welcome to Lazy platform! If you want to decrypt some messages, you can't do that here, you'll have to do it on your own")

    while True:
        print("Choose one of the following options")
        print("[1] Encrypt")
        print("[2] Decrypt")
        print("[3] Get encrypted flag")
        print("[4] Exit")
        option = input("> ")

        if option == "1":
            message = input("Enter a message to encrypt: ")
            key = getrandbytes(32)
            iv = getrandbytes(16)
            ciphertext = AES.new(key, AES.MODE_CBC, iv).encrypt(
                pad(message.encode(), AES.block_size))
            print("Ciphertext:", ciphertext.hex())
            print("Key:", key.hex())
            print("IV:", iv.hex())
        elif option == "2":
            print("I can't do that at the moment, I'm cooking a pizza")
        elif option == "3":
            key = getrandbytes(32)
            iv = getrandbytes(16)
            ciphertext = AES.new(key, AES.MODE_CBC, iv).encrypt(
                pad(FLAG, AES.block_size))
            print("Ciphertext:", ciphertext.hex())
        elif option == "4":
            print("Bye bye!\n")
            break
        else:
            print("Invalid option")
        print()


if __name__ == "__main__":
    signal.alarm(TIMEOUT)
    handle()

程序的逻辑很简单，一个交互题，其中就两个选项有用，其中一个加密自己给出的明文，另一个给你 flag 的密文，通过 aes 加密，值得注意的是，可以无限次交互，限定了时间应该只是确保你是用程序去实现交互的。

当选择加密自己的明文时，题目会把加密用的 key 和 iv 给你，也就是说可以获得很多组 key 和 iv，明文随便选就好。注意一下函数 getrandbytes

1 2	def getrandbytes(n: int) -> bytes: return random.getrandbits(n * 8).to_bytes(n, "little")

由于 to_bytes() 函数取的是 little，所以得到的 bytes 和原来相比是相反的，测试代码为

random.seed(16)
num = random.getrandbits(16 * 8)
# tmp = long_to_bytes(num)#b'H\xf1e\xd5{\x00\xc7\xf4x\x1e\xf8o\\\x8c\xc1\xab'
# tmp = num.to_bytes(16,'big')#b'H\xf1e\xd5{\x00\xc7\xf4x\x1e\xf8o\\\x8c\xc1\xab'
# tmp = num.to_bytes(16,'little')#b'\xab\xc1\x8c\\o\xf8\x1ex\xf4\xc7\x00{\xd5e\xf1H'
print(tmp)

可以看到在 little 的作用下，得到的 bytes 顺序是相反的。

再一个就是 getrandbits 的原理。mt19937 是 32 位比特为一组，如果是生成 64 位的数据，就是先生成 32 位在低位，再生成 32 位在高位。如果是生成 48 位的数据，就是先生成 32 位在低位之后，再生成一个 32 位数据，取前面 16 位作为 48 位数据的高位。

num = [......]
rc = RandCrack()
[rc.submit(i) for i in num]
# print(hex(rc.predict_getrandbits(64))[2:])#18a3217abb50885a
print(hex(rc.predict_getrandbits(48))[2:])#18a3bb50885a

所以这题直接就拿 52 组 key 和 iv，把 mt19937 需要的 624 个 32 位数据填满，之后拿 flag 的 key 和 iv，这一组是可以预测出结果的，完整 exp 为

import random

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from pwn import *
from randcrack import RandCrack

def getrandbytes(n: int) -> bytes:
    return random.getrandbits(n * 8).to_bytes(n, "little")
r = remote('lazy-platform.challs.teamitaly.eu',15004)
num = []
for _ in range(52):
    r.recvuntil(b'> ')
    r.sendline(b'1')
    r.recvuntil(b'Enter a message to encrypt: ')
    r.sendline(b'flag')
    r.recvuntil(b'Key: ')
    key = bytes.fromhex(r.recvline()[:-1].decode())[::-1].hex()
    r.recvuntil(b'IV: ')
    iv = bytes.fromhex(r.recvline()[:-1].decode())[::-1].hex()#倒序
    print(key,iv)
    tmp_key = [int(key[i - 8:i],16) for i in range(len(key),0,-8)]
    tmp_iv = [int(iv[i - 8:i],16) for i in range(len(iv),0,-8)]#倒着填进去
    num = num + tmp_key + tmp_iv
print(num)
r.recvuntil(b'> ')
r.sendline(b'3')
r.recvuntil(b'Ciphertext: ')
enc = bytes.fromhex(r.recvline()[:-1].decode())
print(enc)
rc = RandCrack()
[rc.submit(i) for i in num]
key = rc.predict_getrandbits(32 * 8).to_bytes(32, "little")
iv = rc.predict_getrandbits(16 * 8).to_bytes(16,"little")
aes = AES.new(key,AES.MODE_CBC,iv)
flag = aes.decrypt(enc)
print(flag)

# 0x07 2022ångstromCTF log log log 6.11

附件

from secrets import randbits
from flag import flag

flagbits = len(flag) * 8
flag = int(flag.hex(),16)

q = 127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043
p = q * 2^1024 + 1

assert p in Primes()

nbits = p.nbits()-1

e = randbits(nbits-flagbits)
e <<= flagbits
e |= flag

K = GF(p)
g = K.multiplicative_generator()
a = g^e

print(hex(p))
print(g)
print(hex(a))
print(flagbits)

离散对数问题，也称作 DLP 问题，很明显 flag 在指数位置上。

尝试使用 pohlig-hellman 结合大步小步算法。仔细观察可以发现 p-1 的因子是由一个大因子 q 和 1024 个小因子 2 相乘而成。如果结合所有因子考虑，由于大因子 q 的存在，运算会十分缓慢，尝试舍去大因子 q 计算 flag。

exp 是一个计算离散对数问题的板子

from gmpy2 import invert
from Crypto.Util.number import *
def baby_step_giant_step(step, modulo, ct, pt):
    known_small_powers = {1: 0}
    prev = 1
    for i in range(1, step):
        curr = (prev * pt) % modulo
        known_small_powers[curr] = i
        prev = curr
    subtractor = inverse_mod(power_mod(pt, step, modulo), modulo)
    x = ct
    i = 0
    while x not in known_small_powers:
        i += 1
        x = (x * subtractor) % modulo
    return step * i + known_small_powers[x]

def pohlig_hellman(g, c, s, n, factors):
    res = [0] * len(factors)
    modulus = []
    for i, (q, e) in enumerate(factors):
        for j in range(e):
            gi = power_mod(g, s // q, n)
            ci = power_mod(c * power_mod(inverse_mod(g, n), res[i], n),s // q**(j + 1), n)
            dlogi = baby_step_giant_step(isqrt(q), n, ci, gi)
            res[i] += dlogi * (q**j)
        res[i] = res[i] % (q**e)
        modulus.append(q**e)
        print("[+] dlog modulo {0} == {1}".format(q**e, res[i]))
        print(long_to_bytes(res[i]))
        exit()
    print("\n[*] res = ", res)
    print("[*] modulus = ", modulus)
    dlog = CRT(res, modulus)
    print("\n[+] dlog modulo {0} == {1}".format(prod(modulus), dlog))
    return dlog
    
def find_order(g, s, ff):
    for p, e in ff:
        while s % p == 0 and power_mod(g, s // p, n) == 1:
            s //= p
        if not power_mod(g, s, n) == 1:
            s *= p
    return s

g = 3
s = 0xb4ec8caf1c16a20c421f4f78f3c10be621bc3f9b2401b1ecd6a6b536c9df70bdbf024d4d4b236cbfcb202b702c511aded6141d98202524709a75a13e02f17f2143cd01f2867ca1c4b9744a59d9e7acd0280deb5c256250fb849d96e1e294ad3cf787a08c782ec52594ef5fcf133cd15488521bfaedf485f37990f5bd95d5796b0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
n = 0xb4ec8caf1c16a20c421f4f78f3c10be621bc3f9b2401b1ecd6a6b536c9df70bdbf024d4d4b236cbfcb202b702c511aded6141d98202524709a75a13e02f17f2143cd01f2867ca1c4b9744a59d9e7acd0280deb5c256250fb849d96e1e294ad3cf787a08c782ec52594ef5fcf133cd15488521bfaedf485f37990f5bd95d5796b0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
ff = [
    (2, 1024),
  (127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043,1)
]
for p, e in ff:
    assert power_mod(g, s // p, n) != 1
assert power_mod(g, s, n) == 1
c = 0xaf99914e5fb222c655367eeae3965f67d8c8b3a0b3c76c56983dd40d5ec45f5bcde78f7a817dce9e49bdbb361e96177f95e5de65a4aa9fd7eafec1142ff2a58cab5a755b23da8aede2d5f77a60eff7fb26aec32a9b6adec4fe4d5e70204897947eb441cc883e4f83141a531026e8a1eb76ee4bff40a8596106306fdd8ffec9d03a9a54eb3905645b12500daeabdb4e44adcfcecc5532348c47c41e9a27b65e71f8bc7cbdabf25cd0f11836696f8137cd98088bd244c56cdc2917efbd1ac9b6664f0518c5e612d4acdb81265652296e4471d894a0bd415b5af74b9b75d358b922f6b088bc5e81d914ae27737b0ef8b6ac2c9ad8998bd02c1ed90200ad6fff4a37
dlog = pohlig_hellman(g, c, s, n, ff)

# 0x06 2022ctfshowdsb TooYoungRSA 5.21

虽然但是，春哥的题还是得尊重一下的，附件

from nevergonnagiveyouup import n, e
import secrets
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

if __name__ == "__main__":
    with open("flag.txt", "rb") as f:
        flag = f.read().strip()

    k = secrets.randbelow(n)
    print(f"ck = {pow(k, e, n)}")
    key = sha256(str(k).encode()).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    print(f"ct = {cipher.encrypt(pad(flag, AES.block_size)).hex()}")
    
    while True:
        nevergonnaletyoudown = int(input("I just wanna tell you how i'm feeling... "))
        assert nevergonnaletyoudown >= 0
        print(f"gotta make you understand: {pow(nevergonnaletyoudown, e, n)}")

给出 $ck=k^{e} \bmod n$ ，以及用 $k$ 加密之后得到的 aes 密文 $ct$ ，求得 $k$ 之后可以还原明文。靶机交互是可以重复输入 $m$ 然后得到公钥加密之后的密文，本题的特色就是未知公钥 (n,e)，尝试输入之后发现得到的密文特别小，也就是说 n 可以直接分解，只要求得 n 即可。

尝试输入 2 的次方，即得到

$c1 = 2^{e} \bmod n = 2^{e} - k1 \times n$

$c2 = 4^{e} \bmod n = 4^{e} - k2 \times n$

$c3 = 16^{e} \bmod n = 16^{e} - k3 \times n$

$c4 = 256^{e} \bmod n = 256^{e} - k4 \times n$

可以得到如下关系

$c1^{2}-c2 = \_k1 \times n$

$c2^{2} - c3 = \_k2 \times n$

$c3^{2} - c4 = \_k3 \times n$

即可 gcd 求得 n

c1 = 124723985017203401196518421017251357832
c2 = 167060963656030161398510115791819709693
c3 = 67147460534536520913187316098564482078
c4 = 30405433154955336047389937748228753910

tmp1 = pow(c1,2) - c2
tmp2 = pow(c2,2) - c3
tmp3 = pow(c3,2) - c4

n = reduce(gmpy2.gcd,[tmp1,tmp2,tmp3])
print(n)
#197090442394747169360754978303092915071

n 可以轻松分解，求得 n 之后还需求 e，e 作为指数，除了爆破就是离散对数解法 discrete_log (sage 中的比 sympy 更强大)。求得 e 之后本题也就解完了。

# 0x05 2022TJCTF Morph-master 5.18

参考 wp，附件

#!/usr/local/bin/python -u

from Crypto.Util.number import *

N = 1024
p = getPrime(N)
q = getPrime(N)
assert GCD(p * q, (p - 1) * (q - 1)) == 1

n = p * q
s = n ** 2
λ = (p - 1) * (q - 1) // GCD(p - 1, q - 1)
g = getRandomRange(1, s)
L = lambda x : (x - 1) // n
μ = pow(L(pow(g, λ, s)), -1, n)

def encrypt(m):
    r = getRandomRange(1, n)
    c = (pow(g, m, s) * pow(r, n, s)) % (s)
    return c

def decrypt(c):
    m = (L(pow(c, λ, s)) * μ) % n
    return m

print(f"public key (n, g) = ({n}, ?)")
print(f"E(4) = {encrypt(4)}")
print()
print("Encrypt 'Please give me the flag' for your flag:")
c = int(input())
m = decrypt(c)

if long_to_bytes(m) == b"Please give me the flag":
    print("Okay!")
    with open("flag.txt") as f:
        print(f.read())
else:
    print("Hmm... not quite.")

第一次接触同态加密的签名题，这个 Paillier 密码系统 wiki 里面也介绍的很详细。来看加同态加密的加法和乘法

$D(E({m_1},{r_1}) \times E({m_2},{r_2}) \bmod {n^2})={m_1} + {m_2} \bmod n$

$D(E({m_1},{r_1}) \times g^{m_2} \bmod {n^2})={m_1} + {m_2} \bmod n$

$D(E({m_1},{r_1})^{m_2} \bmod {n^2})={m_1}{m_2} \bmod n$

$D(E({m},{r})^{k} \bmod {n^2})={k}{m} \bmod n$

回到本题，题目给的条件有 E (4) 和 n 已经待签名的值 m，需要构造一个 ans 满足 $D(ans)=m \bmod n$ ，由于 g 未知，不能通过加法构造，又因为待签名值 m 为奇数，只能构造 $D(E(4,r)^{-\frac{n-m}{4}} \bmod {n^2}))=m \bmod n$ ，且需满足 n-m%4==0，如果取不到合适的数据就接着取

from Crypto.Util.number import *
import gmpy2
from pwn import *
context(log_level = 'debug')
while True:
    r = remote('tjc.tf',31996)
    r.recvuntil(b'public key (n, g) = (')
    line = r.recvline()[:-1].decode()
    n = int(line[:line.find(',')])
    r.recvuntil(b'E(4) = ')
    e4 = int(r.recvline()[:-1].decode())
    m = bytes_to_long(b'Please give me the flag')
    if (n - m) % 4 == 0:
        ans = pow(e4,-(n - m) // 4,pow(n,2))
        r.recvuntil(b'Encrypt \'Please give me the flag\' for your flag:')
        r.sendline(str(ans).encode())
        r.interactive()
    else:
        continue

# 0x04 2022crew The HUGE e 5.16

附件

from Crypto.Util.number import getPrime, bytes_to_long, inverse, isPrime
from secret import flag

m = bytes_to_long(flag)

def getSpecialPrime():
    a = 2
    for i in range(40):
        a*=getPrime(20)
    while True:
        b = getPrime(20)
        if isPrime(a*b+1):
            return a*b+1


p = getSpecialPrime()
e1 = getPrime(128)
e2 = getPrime(128)
e3 = getPrime(128)

e = pow(e1,pow(e2,e3))
c = pow(m,e,p)

assert pow(c,inverse(e,p-1),p) == m

print(f'p = {p}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
print(f'e3 = {e3}')
print(f'c = {c}')

做题的式子也很简单 $c \equiv m^{e1^{e2^{e3}}} \pmod p$ ，

对欧拉定理的灵活使用，欧拉定理如下：** 若 $n,a$ 为正整数，且 gcd (n,a)==1，则有 $a^{\varphi(n)}\equiv 1 \pmod n$ 。** 灵活运用一下则有 $a^{m \% \varphi(p)} \equiv a^{m} \pmod p$ 。

所以有e1^{e2^{e3}} \equiv e1^{e2^{e3} \% \varphi(p-1)} \pmod

$m^{e1^{e2^{e3}}} \equiv m^{e1^{e2^{e3}\% \varphi(p-1)}} \times m^{k(p-1)} \pmod p$

$m^{e1^{e2^{e3}}} \equiv m^{e1^{e2^{e3}\% \varphi(p-1)}\% \varphi(p)} \pmod p$

思路清晰，这个 huge e 可以在 mod p 中求出一个等效的，其中求 $\varphi(p-1)$ 根据欧拉函数的性质求就行，直接贴 exp 了

from Crypto.Util.number import *
import gmpy2
import primefac
p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
e1 = 219560036291700924162367491740680392841
e2 = 325829142086458078752836113369745585569
e3 = 237262361171684477270779152881433264701
c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613
phi = 1
for i in primefac.primefac(p - 1):
    phi *= i - 1
e2_e3 = pow(e2,e3,phi)
e = pow(e1,e2_e3,p - 1)
d = gmpy2.invert(e,p - 1)
m = pow(c,d,p)
print(long_to_bytes(m))

# 0x03 2022pwnhub ezrsa 4.24

周末 pwnhub 暴打了，题目质量挺不错，复现一下，附件

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

p = getPrime(1024)
q = getPrime(512)
e = 0x10001
n = p * q
E = EllipticCurve(Zmod(n), [p+q, p^2+(q-1)//2])

def gen_point():
    while 1:
        pad_m = flag + os.urandom(20)
        m = bytes_to_long(pad_m)
        x = Integer(m)
        Ep = E.change_ring(GF(p))
        Eq = E.change_ring(GF(q))
        try:
            y = crt([Integer(Ep.lift_x(x)[1]), Integer(Eq.lift_x(x)[1])], [p, q])
            return (x, y)
        except:
            pass

m_point = E(gen_point())
cipher_point = e * m_point
print(f'cipher_point = {cipher_point.xy()}')
print(f'n = {n}')
# cipher_point = (338555080220637081961629108201515088631648910827927160728143665306856840891283037339677849661861227903908933145477264046446986150577658634798201036502060805774599658207669111688439996110692201008037849119605962378316457201998475046620515963725786423440494993922281942396227626532022005579340476627086260000576524772862121364339849726687865874619472513654142054490221489754144358483093331358263771080584662872680106076787261957704707055652825959314984924849600101, 936859805496385391559236776246883920797971062581544240268575675825570737296851006237870839271568976317212531276234406232945021531066674291887782791534409966305833225084692612867437424551505174720475931132798839349207246806850341280754752239303350596733681932273450149927797735966407187594725231158980098119489003450563623494155562513634618466910170109518754662675054081897025489520391417883488720972781393802142478712026232107041683271177224983497203599032383279)
# n = 988000511804778695813521569460767024014375863209856154754147082419975777208656083311740358048468580712106204105426217752071608551112269505247365548210006567296850568411531004204795967810292432041395592133501302461324005142940183488044983348152371980166614840414803124031222965874472013554869981954785271467321919039144942853506143787908194930700818770224752026306092706366253640515130802157497666497193713819097381223915943111321812676982912146706199692543488639

果然是题目做少了，这题给了一个加密之后的点，给了公钥 n,e，第一步考虑的就是能不能把 n 分解出来。当时做题的时候没注意，除了给了 p 和 q 的位数，还可以通过代入加密点的方法再得到一组关系从而求解出 q，就可以把 n 给分解出。椭圆曲线可变换为 $2x^{3}-2y^{2} +2xq + q-1\equiv 0 \pmod p$

之后 cop 可以得到 q 的结果

from Crypto.Util.number import *
import gmpy2
x,y = (338555080220637081961629108201515088631648910827927160728143665306856840891283037339677849661861227903908933145477264046446986150577658634798201036502060805774599658207669111688439996110692201008037849119605962378316457201998475046620515963725786423440494993922281942396227626532022005579340476627086260000576524772862121364339849726687865874619472513654142054490221489754144358483093331358263771080584662872680106076787261957704707055652825959314984924849600101, 936859805496385391559236776246883920797971062581544240268575675825570737296851006237870839271568976317212531276234406232945021531066674291887782791534409966305833225084692612867437424551505174720475931132798839349207246806850341280754752239303350596733681932273450149927797735966407187594725231158980098119489003450563623494155562513634618466910170109518754662675054081897025489520391417883488720972781393802142478712026232107041683271177224983497203599032383279)
n = 988000511804778695813521569460767024014375863209856154754147082419975777208656083311740358048468580712106204105426217752071608551112269505247365548210006567296850568411531004204795967810292432041395592133501302461324005142940183488044983348152371980166614840414803124031222965874472013554869981954785271467321919039144942853506143787908194930700818770224752026306092706366253640515130802157497666497193713819097381223915943111321812676982912146706199692543488639
e = 0x10001
PR.<q> = PolynomialRing(Zmod(n))
f = 2 * pow(x,3) - 2 * pow(y,2) + 2 * x * q + q - 1
f = f.monic()
root = f.small_roots(X=2^512,beta=0.4)
print(root)

之后再回过头来看生成加密点的原理，之前看 crt 的过程，不明白为什么他要分别 mod p 再 mod q，现在知道是如果不经过这样一个换环的操作，是没有办法得到点的，在 mod n 的情况，n 不是质数，无法代入求点无法开根，所以得先将 n 给分解了，然后在换环 q，在 GF (q) 中求出 e 的逆元 d，之后就得到原始点了，完整 wp

from Crypto.Util.number import *
import gmpy2
x,y = (338555080220637081961629108201515088631648910827927160728143665306856840891283037339677849661861227903908933145477264046446986150577658634798201036502060805774599658207669111688439996110692201008037849119605962378316457201998475046620515963725786423440494993922281942396227626532022005579340476627086260000576524772862121364339849726687865874619472513654142054490221489754144358483093331358263771080584662872680106076787261957704707055652825959314984924849600101, 936859805496385391559236776246883920797971062581544240268575675825570737296851006237870839271568976317212531276234406232945021531066674291887782791534409966305833225084692612867437424551505174720475931132798839349207246806850341280754752239303350596733681932273450149927797735966407187594725231158980098119489003450563623494155562513634618466910170109518754662675054081897025489520391417883488720972781393802142478712026232107041683271177224983497203599032383279)
n = 988000511804778695813521569460767024014375863209856154754147082419975777208656083311740358048468580712106204105426217752071608551112269505247365548210006567296850568411531004204795967810292432041395592133501302461324005142940183488044983348152371980166614840414803124031222965874472013554869981954785271467321919039144942853506143787908194930700818770224752026306092706366253640515130802157497666497193713819097381223915943111321812676982912146706199692543488639
e = 0x10001
# PR.<q> = PolynomialRing(Zmod(n))
# f = 2 * pow(x,3) - 2 * pow(y,2) + 2 * x * q + q - 1
# f = f.monic()
# root = f.small_roots(X=2^512,beta=0.4)
# print(root)
# q = int(root[0])
q = 6855192886546913083681222574678665050135391949965285975146135828115325275541631426684624286108989012385528786352923283164197836807561259652090408171411517
p = n // q
E = EllipticCurve(Zmod(n), [p+q, p^2+(q-1)//2])
Eq = E.change_ring(GF(q))
d = gmpy2.invert(e,Eq.order())
c_point = Eq(x,y)
m_point = c_point * d
flag = m_point.xy()[0]
print(long_to_bytes(flag))

# 0x02 two_old_man 4.21

附件

from Crypto.Util.number import getPrime, bytes_to_long
from gmpy2 import next_prime
from os import urandom
p = getPrime(512)
q = next_prime(p)
f = open('flag.txt', 'rb')
flag = bytes_to_long(f.read() + urandom(80))
f.close()
n = p * q
noise = 1
for i in range(1, p):
    noise = (noise * i) % n
e = 65537
m = noise * flag % n
c = pow(m, e, n)
f = open('cipher.txt', 'w')
f.write(f'n = {n}\n')
f.write(f'c = {c}\n')
f.close()
n = 85300075344029411815824595503988243445862905766678219075505308650733618833670564881852727486124268400610986787128098448019033364495139613324970241727110931819892696714818851281415775513570277910383275087114654129682377412912019832281317957560043184535419626656895668221654944747681971549122289940681069900407
c = 9573652589542765552302771253681350397003834739308979745013100413124314842798363931809688570564520116621700487372591176287735200842509675988724251662626729985842786542792501720096155870937426730816107184806453412679852267311433564241907769415712680798333238722253896962273334726781549003053182286964079196169

一眼看到阶乘，肯定得用威尔逊定理解，威尔逊定理简单普及一下：当且仅当 p 为素数时满足 $(p-1)! =-1\pmod p$

p 和 q 很靠近，能直接分解出，m 也能求出，现在就有式子 $m\equiv (p-1)! \times flag\pmod n$

考虑到 p<q，且 p 和 q 的值已知，考虑求出 (p-1)! 在 mod q 的环境下的值，然后中国剩余定理可求得 x 有 $(p-1)!\equiv x \pmod n$

数学推理如下

$(q-1)!\equiv -1 \pmod q$

$(p-1)! \times p \times \dots \times (q-1) \equiv -1 \pmod q$

$(p-1)!\equiv (p\times \dots \times (q-2))^{-1} \pmod q$

然后可以把 (p-1)! mod n 求出，就可以求得 flag 了

from Crypto.Util.number import *
import gmpy2
import sympy
import os
from functools import reduce

def union(x1, x2):
    a1, m1 = x1
    a2, m2 = x2
    d = gmpy2.gcd(m1, m2)
    assert (a2 - a1) % d == 0
    p1,p2 = m1 // d,m2 // d
    _,l1,l2 = gmpy2.gcdext(p1,p2)
    k = -((a1 - a2) // d) * l1
    lcm = gmpy2.lcm(m1,m2)
    ans = (a1 + k * m1) % lcm
    return ans,lcm

def excrt(ai,mi):
    tmp = zip(ai,mi)
    return reduce(union, tmp)
n = 85300075344029411815824595503988243445862905766678219075505308650733618833670564881852727486124268400610986787128098448019033364495139613324970241727110931819892696714818851281415775513570277910383275087114654129682377412912019832281317957560043184535419626656895668221654944747681971549122289940681069900407
c = 9573652589542765552302771253681350397003834739308979745013100413124314842798363931809688570564520116621700487372591176287735200842509675988724251662626729985842786542792501720096155870937426730816107184806453412679852267311433564241907769415712680798333238722253896962273334726781549003053182286964079196169
e = 65537
q = gmpy2.iroot(n,2)[0]
q = sympy.nextprime(q)
p = n // q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(m)
ass = 1
for i in range(p,q - 1):
    ass = ass * i % q
tmp = gmpy2.invert(ass,q)
ai = [tmp,-1]
mi = [q,p]
ans = excrt(ai,mi)[0]
print(ans)
flag = m * gmpy2.invert(ans,n) % n
print(long_to_bytes(flag))

CRT 还是很好用的呜呜呜

# 0x01 2022*CTF ezRSA 4.20

附件

from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from flag import flag

p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537

m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)

print(hex(n))
#0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

print(hex(c))
#0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

给了 n,e,c 及公钥 n 的生成形式，仔细观察 p 与 q 的生成方式

p 和 q 的高 124 位是相同的，中间 600 位 q 和 p 互相取反，最后 300 被混淆。看到最后 300 被混淆很容易想到用 cop 求出最后的 300 位，高 124 位直接对 n 开方取前 124 位就得到了。问题就在中间的 600 位如何利用取反关系求得。

$p=hight128+x+l1\quad q=hight128+y+l2$ ，其中 + 表示拼接会直观一些，hight128 表示可求出的 128 位，l1 和 l2 表示最后被混淆的 300 位，中间 600 位 x 与 y 满足关系式 $x+y=2^{600}-1$ 。所以我们尝试改变 p 和 q 的值，p 相应减少多少，q 就相应增大多少 (仅中间 600 位)

$\_n=\_p\times\_q=(a-x)\times(b+x)=ab+x(a-b)-x^2$

我们先分别赋值 p 和 q 为极大极小值，由于最后 300 位不知道，p 和 q 赋的极大值默认最后 300 位为 0，中间求出来的数不能准确得求出 600 位，求出来的 p 会比实际值更小一些。

from Crypto.Util.number import *
import gmpy2
n = 29229445599118483001701466306458274418313207587536209963238059476868917454504410032112597117546615733598387274665904107870896556998881063494600049216084775281584147609749667294182462818941181246561319625259137178286553974862986352158857172427903588054746932151579636584132759169528954347728678147797597780996214188968831836400285920685337294608990778009074569367505456248478822993714411937836237079928768898433354626698856023139709607246825672149802133458391862603953992754636020632951723690379324712160511376119409228990756977864084382454893999090811914709514495628598844102290648843131526073812299407141152746828211
e = 65537
c = 27262929902030666496793680198378375783118765007240773797447297373974049739280501484190475741272400002678990305397801039585302141612980217637827689855495194137917731223794004541444801329963350663757702880339071040394112003443782577628934852778346806832338683188416557851657662851936237381508536575784367362155948842050537160648323422133865019281159422760012328176817578911979109809017343487277094564311771567762098406452929665999529576409514599383724142729549969108272634307034039737849698091566761416686112727060743246758998947423163006255390922762318010959938510994940492040924944342464117140526367088683519638709681

hight_124 = gmpy2.iroot(n,2)[0]
hight_124 >>= 900
print(hight_124)
p = ((hight_124 << 900) ^ (1<<900)-1) ^ ((1<<300)-1)
q = (hight_124 << 900)

至于具体求的方法，则是利用异或的特性不断尝试，可以理解为是 p 向 q 传递一个定值，传递之后 p 与 q 的乘积会相应得更大些，如果传递之后大于给出的 n，则是传递的定值大了，在二进制的角度来看题目就会更好理解

for i in range(899,299,-1):
    tmp = 1 << i
    tmp_p = p ^ tmp
    tmp_q = q ^ tmp
    if tmp_p * tmp_q < n:
        p,q = tmp_p,tmp_q
print(p)

这样出来的 p 有误差，最后部分位数是无法准确求出的，具体不知道是哪一位，我们可以用 cop 一起求出

from Crypto.Util.number import *
import gmpy2
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
e = 65537
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
hight_124 = gmpy2.iroot(n,2)[0]
hight_124 >>= 900
print(hight_124)
# p = ((hight_124 << 900) ^ (1<<900)-1) ^ ((1<<300)-1)
# q = (hight_124 << 900)
# for i in range(899,299,-1):
#     tmp = 1 << i
#     tmp_p = p ^ tmp
#     tmp_q = q ^ tmp
#     if tmp_p * tmp_q < n:
#         p,q = tmp_p,tmp_q
p = 170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371344767976558822028720769455584351917209508431456012727131938700513852456800512509515671651181190792109543581556171983224752308224
for i in range(300,600):
    h_p = p >> i
    PR.<x> = PolynomialRing(Zmod(n))
    f = (h_p << i) + x
    root = f.small_roots(X=2^i,beta=0.4)
    if len(root) > 0:
        p = int((h_p << i) + root[0])#这里要转化为int，我也不知道为啥
        print(p,i)
        break
q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

# 0x00 2022NISA xor 4.13

附件

import os
import base64
from Crypto.Util import number, strxor
#from flag import flag

flag='xxxxxxxxxxxxxxxxxx'


def gen_key():
    return [os.urandom(16) for _ in range(8)]

def rnd(b: bytes, k: bytes):
    l = b[:16]
    r = b[16:]
    _r = l
    _l = strxor.strxor(strxor.strxor(r, k), l)
    return _l + _r

def enc(b: bytes, ks):
    c = b
    for i in range(8):
        c = rnd(c, ks[i])
    return c

if __name__ == '__main__':
    a = os.urandom(32)
    ks = gen_key()
    enc_a = enc(a, ks)
    enc_flag = enc(flag.encode(), ks)
    print(base64.b64encode(a).decode())
    print(base64.b64encode(enc_a).decode())
    print(base64.b64encode(enc_flag).decode())

#i03yXzXWe4QTiwJHlUZo6iqEdDkwJVviSOQ7CM3vJmM=
#4EnYOhbivTMP5r4VYLA8cwJBFTXIeeKAoNf/3ctgLLA=
#+qyVMEei1eN3YbV/z2kjcaCKngWc2pW2/e7HwpXKaj0=

这题是经典的 Feistel 密码系统，因为给了一组明文与密文，也给了 flag 的密文，只要找到多次轮换加密之后的关系即可。本题倒比较清晰，加密的密钥 ks 不需要知道，画一个表清晰地展示下 (其中 ks 的值我用数字表示，省略了异或符号)

序号	L	R
1	L R 1	L
2	R 1 2	L R 1
3	L 2 3	R 1 2
4	L R 1 3 4	L 2 3
...	...	...
8	R 1 2 4 5 7 8	L R 1 3 4 6 7

推到后面其实发现，后面具体是 ks 的哪一个值我不用管，我只需要知道明文在密文中对应的关系即可 (下表格中省略了一系列的 key)

序号	L	R
1	L R	L
2	R	L R
3*	L	R
4	L R	L
...	...	...
8	R key1	L R key2

如果只考虑明文在密文中的状态，从第三行可见，已经产生了循环，该题中给出了一组明文及轮换 8 次加密之后的密文，求 key 的思路就很清晰了

$msg1=L\quad msg2=R$

$enc1=R \oplus key1 \quad enc2=L\oplus R \oplus key2$

其中 msg 和 enc 都是已知量，先求出对应的 key，即有

$key1=msg2\oplus enc1 \quad key2=enc2\oplus msg1 \oplus msg2$

key 出来了这题也就出来了

from Crypto.Util import strxor
import os
import base64
from pwn import xor

a = base64.b64decode('i03yXzXWe4QTiwJHlUZo6iqEdDkwJVviSOQ7CM3vJmM=')
enc_a = base64.b64decode('4EnYOhbivTMP5r4VYLA8cwJBFTXIeeKAoNf/3ctgLLA=')
enc_flag = base64.b64decode('+qyVMEei1eN3YbV/z2kjcaCKngWc2pW2/e7HwpXKaj0=')
assert len(a) == 32
msg1,msg2 = a[:16],a[16:]
enc1,enc2 = enc_a[:16],enc_a[16:]
key1 = xor(msg2,enc1)
key2 = xor(enc2,msg1,msg2)
enc1,enc2 = enc_flag[:16],enc_flag[16:]
msg2 = xor(enc1,key1)
msg1 = xor(enc2,msg2,key2)
print(msg1 + msg2)

学习 crypto