2022羊城杯Crypto wp

比赛只有24h,记录一下做出来的几个题,后面太晚了实在干不动了。

EasyRsa

题目源码:

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

m = bytes_to_long(flag)
e = 65537
f = open("output.txt", "r")
a = f.readlines()
for i in a:
n = int(i)
c = pow(m, e, n)
m = c
print 'c = %s' % (m)
f.close()

output里面是一些n值,gcd一下可以发现全都有一个相同的公因子,那没啥好说的分解倒着解回来就完事儿了。

解题脚本:

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

c = 38127524839835864306737280818907796566475979451567460500065967565655632622992572530918601432256137666695102199970580936307755091109351218835095309766358063857260088937006810056236871014903809290530667071255731805071115169201705265663551734892827553733293929057918850738362888383312352624299108382366714432727
e = 65537
f = open("output.txt", "r")
ns = [ int(line) for line in f.readlines() if line.strip()]
'''
for i in range(len(ns)):
for j in range(i+1,len(ns)):
print(GCD(ns[i],ns[j]))
#7552850543392291177573335134779451826968284497191536051874894984844023350777357739533061306212635723884437778881981836095720474943879388731913801454095897
'''
p=7552850543392291177573335134779451826968284497191536051874894984844023350777357739533061306212635723884437778881981836095720474943879388731913801454095897
for n in ns[::-1]:
q=n//p
d=inverse(e,(p-1)*(q-1))
c=pow(c,d,n)
print(long_to_bytes(c))
#b'GWHT{gixkJl7SJTcpLOL9zqwo}'

LRSA

题目源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)

首先可以根据提供的值求出,然后我们观察到非常小,因此有: 又由于,因此有: 因此对进行连分数展开,即可找到某一逼近的分母为,从而求得值,接着带回原式可求得,然后解RSA即可。

解题脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import *
from gmpy2 import iroot

B=1023
PPQ=17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
PQQ=17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
t=44
c=4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
e=65537

def simplify_fraction(e,n,max_size):
assert e<n
simp_list=[]
for i in range(max_size):
if e==0:
break
t=n//e
simp_list.append(t)
(e,n)=(n-e*t,e)
return simp_list

def calc_convergent(simp):
convergent=[(0,0)]*len(simp)
for i in range(len(simp)):
a,b=1,simp[i]
for j in range(i):
a,b=b,simp[i-1-j]*b+a
convergent[i]=(a,b)
return convergent

PQ,b=iroot(PPQ*PQQ,3)
assert b
P=PPQ//PQ
Q=PQQ//PQ
simp=simplify_fraction(P,Q,1000)
convergent=calc_convergent(simp)
for a,b in convergent:
if isPrime(b+58) and b.bit_length()==1023:
p=b+58
q=(t-p*P+58*P)%Q
assert isPrime(q)
n=p*q
d=inverse(e,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))
#b'DASCTF{8f3djoj9wedj2_dkc903cwckckdk}'

Solomen's puzzle 1

题目源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# type: ignore

m = 257
F = Zmod(m)
alpha = F(223)
PR.<x> = PolynomialRing(F)
gx = (x - alpha ^ 0) * (x - alpha ^ 1) * (x - alpha ^ 2) * (x - alpha ^ 3)

def encode_block(message):
assert isinstance(message, list)

f = PR([0] * 4 + message)
px = f % gx
mx = f - px
c = [_ for _ in mx]
return c + (8 - len(c)) * [0]

def encode(byte_stream):

length = len(byte_stream)
if length % 4 != 0:
padding = (length // 4 + 1) * 4 - length
byte_stream += padding * b'\x00'
length += padding
code = b''
for i in range(0, length, 4):
block = byte_stream[i:i+4]
block_code = encode_block([each for each in block])
code += bytes(block_code)

return code


from secret import flag, p, q
from Crypto.Util.number import bytes_to_long, long_to_bytes
from random import randrange

n = p * q
e = 10632528934906371807995216845027219767890923967559690651733628659750564299493611010425615580946665632019547006685100876646048602773295571936276450835367591

cipher = bytes_to_long(flag) * e % n
code = encode(long_to_bytes(cipher))

code = [each for each in code]

for i in range(0, 256, 8):
index1 = randrange(4, 8)
value1 = randrange(0, 256)
index2 = randrange(4, 8)
value2 = randrange(0, 256)
code[i + index1] = value1
code[i + index2] = value2

print(n)
print(bytes(code))

从题目名也可以看出来,本题的考点是Reed-Solomon纠错编码,这是一种基于有限域内多项式运算的纠错码。具体原理可以参考wiki上的解释,看不懂英文的也可以去这篇文章上看看,讲的也很清楚。

在本题中,每个消息块消息长度为4,纠错码长度为4,组成8字节的编码。根据RS纠错码原理,长度为4的纠错码最多能纠正的错误为个。而本题也是在编码的消息部分随机产生了1~2字节的错误,因此纠错码是完全能够将错误全部纠正,得到正确的消息。

因此,本题主要考察的是如何根据编码进行纠错的问题。这一问题在以上的两份链接中也有相关的算法描述(其实是懒得贴公式)。先计算编码的syndrome值,然后根据syndrome值计算得到一个error locator向量,从而可以算出发生error的位置,最后代入到error locator多项式可以求出error value。

注意到编码中错误的个数是不确定的,我直接枚举了。

解题脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from Crypto.Util.number import *
from hashlib import md5

enc=b'\xb9$5.>\xff\xe3S\xc91\xb2\xeb\x1byR(\x12{\xc4\xbf\xa4wo|\xc5-;\xc9\xc9S[\xaeX\xad\xf0\xef@\x1c\x87]\x9a\xb9:\x8cu\xa5\xe3EA<"\xfd\x9a\xbfqB\x94\xc3R\x95\xd5\xbd\xd0\x10u\x10\xe3\xa5"S\xed\xd0\xf8\x02\xbf\x124A~1]\xceP\xdf\xf2Cr1\x93\xacw\x03\tQe\xcc2b\xbf\x0f\x92\xad\x19\x00\xab|\xf3\xc9\x9b&I%\xf5\x9b#\xf7\xa2\xcb\xb1\x0c\xee\xb56\xd5\xd2\xd5[?^\x9d\x8b\x93\xbe\x832\xee\xa9\xa5\x83$\xe9\xe5\x95\x01\xd6\x9f\xad\x1f\x90\xc3]aL\x10\x07{#4i^\xae\xdf|\x9f\x94\xf4\xaf\x06R\x86j&\xeb\x0b\x06\xcf\xb2\x8e\xb4\xb9s\x97[\xf1ip\x06\xf8\xfdFs\xf1`\xc6\x82\xd8\xce\xf6\x95{\xe3\x8cQ\xed\xef\xe9\xb9\'\x19\xdf^\xc8\x81\xde\x1fQ\x1e\x86\xda\xf8\xfd4M0#\xef\x8a\xe9\xe5\xfc\xe2\xe3\xe6\xd0e\xce\xe1\x0b\x9eM\x07\xc2Y\xf8B\xe1\xde\xfaP\xe9\x9d\xde\xc3\xe3C\xa5'
e = 10632528934906371807995216845027219767890923967559690651733628659750564299493611010425615580946665632019547006685100876646048602773295571936276450835367591
n = 94257413713770111563970534929325680923943690882102478219183863722026590313165304301118258536360712467357451726680293716779730218553691126214750969333228034756948476572806064756873382054384808713137658321644158757777088916851366208046581218865015163572359836440643828462291397248680038931998325006839692797347
m = 257
F = Zmod(m)
alpha = F(223)
PR.<x> = PolynomialRing(F)
gx = (x - alpha ^ 0) * (x - alpha ^ 1) * (x - alpha ^ 2) * (x - alpha ^ 3)

def get_syndromes(mx):
return [mx(alpha^i)for i in range(4)]

def get_locator(synd,v):
if v==2:
m=Matrix([[synd[0],synd[1]],[synd[1],synd[2]]])
vec=vector([-synd[2],-synd[3]])
return list(m^-1*vec)
else:
return F((-synd[1])*synd[0]^-1)

def get_pos(loc,v):
if v==2:
pos=[]
for i in range(8):
xx=alpha^(-i)
if F(1+loc[1]*xx+loc[0]*xx^2)==0:
pos.append(i)
return [ alpha^i for i in pos]
else:
res=F(-loc^-1)
return [F(res^-1)]

def get_err_val(synd,pos,v):
if v==2:
m=Matrix(F,[[pos[0]^0,pos[1]^0],[pos[0]^1,pos[1]^1]])
v=vector([synd[0],synd[1]])
return list(m^-1*v)
else:
return [F(synd[0])]

def decode_block(block):
mx=PR(list(block))
synd=get_syndromes(mx)
for v in [2,1]:
try:
locator=get_locator(synd,v)
pos=get_pos(locator,v)
arr=[alpha^i for i in range(8)]
err_idx=[ arr.index(t) for t in pos]
err_val=get_err_val(synd,pos,v)
err=[0]*8
for val,i in zip(err_val,err_idx):
err[i]=val
plain=mx-PR(err)
return bytes(list(plain))[4:8]
break

except Exception as e:
#print(e)
continue

def decode(enc):
plain=b''
for i in range(0,len(enc),8):
block=enc[i:i+8]
plain+=decode_block(block)
return plain

dec=decode(enc)
flag=bytes_to_long(dec)*inverse(e,n)%n
flag=long_to_bytes(flag)
print(flag)
flag='DASCTF{%s}'%md5(flag).hexdigest()
print(flag)
#b'DASCTF{What_a_funny_rsa_question_posted_by_Reed_and_Solomen_LOL_HHHHHH}'
#DASCTF{4e4fc02d88b0c8f66c924489e1bf58ea}

NovelSystem2

题目源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from Crypto.Util.number import *
from gmpy2 import *
from uuid import uuid4
from flag import flag

class NovelSystem:
def __init__(self, delta):
self.p = getPrime(delta >> 1)
self.q = getPrime(delta >> 1)
self.N = self.p * self.q

self.beta = 0.397
self.psi = (self.p ** 2 + self.p + 1) * (self.q ** 2 + self.q + 1)
self.e, self.d = self.generate_key(delta)
self.r = getPrime(delta % delta.bit_length())


def generate_key(self, delta):
delta = int(delta * self.beta)
d = getPrime(delta)
e = invert(d, self.psi)
return (e, d)

def print_pk(self):
print("pk:", (self.N, int(self.e), self.r))

def print_sk(self):
print("sk:", (self.N, self.p, self.q, self.e, self.d))

def add_(self, a, b):
m, n = a
k, l = b
if a[1] == 0:
a, b = b, a
m, n, k, l = k, l, m, n
if l == 0:
if n == 0:
return (m * k, m + k)
if (n + k) % self.N == 0:
if (m - n ** 2) % self.N == 0:
return (0, 0)
return ((m * k + self.r) * invert(m - n * n) % self.N, 0)
return ((m * k + self.r) * invert(n + k, self.N) % self.N, (m + n * k) * invert(n + k,self.N) % self.N)
if (m + k + n * l) % self.N != 0:
return ((m * k + (n + l) * self.r) * invert(m + k + n * l, self.N)%self.N,(n * k + m * l + self.r) * invert(m + k + n * l, self.N) % self.N)

if (n * k + m * l + self.r) % self.N == 0:
return (0, 0)
return ((m * k + (n + l) * self.r) * invert(n * k + m * l + self.r, self.N) % self.N, 0)

def mul_(self, a, n):
ans = (0, 0)
while n > 0:
if n & 1 == 1:
ans = self.add_(ans, a)
a = self.add_(a, a)
n //= 2
return ans

def encrypt(self, m):
return self.mul_(m, self.e)

def decrypt(self, c):
return self.mul_(c, self.d)

delta = 1024
enc = NovelSystem(delta)

m = bytes_to_long(flag[:len(flag) // 2]), bytes_to_long(flag[len(flag) // 2:])
c = enc.encrypt(m)
enc.print_pk()
print(c)
assert enc.decrypt(c) == m

这题是RSA的一种变种,其中的phi变成了

经过一番搜索发现,该系统是Murru and Saettone提出的一种新的类RSA加密系统。其方案原文链接在此。然而,这一RSA变体形式仍然可以被传统的Boneh and Durfee等攻击手法攻击。攻击方案在这篇论文中有详细的描述。文中分析到,只要满足,就可以利用 small inverse problem对进行多项式时间内分解。

本来尝试手动写一下攻击的实现,结果无意间找到原题了,原题是[pbCTF 2021]Yet Another RSA,连参数都没怎么改,好家伙!

解题脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
from Crypto.Util.number import *
from gmpy2 import invert

e=3569709831456961963983317856906282564247794656174883346551318455409781951821532194464316039706968856000098892463123452801581913760419867217744612993876726508565953876218527986879338419527071132882516845467078252901861510834762733680624403662683842157212966883670782784707420186939792539380416673702618954148609178781352393489552193742869735649479707631323667621294737562886946346783459713562739324444015141587968954791790724386091523034752910330271202144122827876441229219899077622471534860855412052877175120218922873300885113936346989198403927493848984768217738562507350427274074810257890679068944519650350540061773
N=69608791192421919283757675475568920773353852553984294535246714322217147926140334786382671447161809319059757926660104907264892471513691210713164936055575369238706600340586833164515933300246888063235136692968128246137215938114060492757345025435557818940819819146315427528432401269318798897677955790143951114837

P.<x, y> = PolynomialRing(ZZ)

m = 4
t = 2
X = int(N ^ 0.4)
Y = 3 * int(N ^ 0.5)

a = N + 1
b = N^2 - N + 1

f = x * (y^2 + a * y + b) + 1

gs = []

for k in range(m + 1):
for i in range(k, m + 1):
for j in range(2 * k, 2 * k + 2):
g = x^(i - k) * y^(j - 2 * k) * f^k * e^(m - k)
gs.append((i, j, k, g))
i = k
for j in range(2 * k + 2, 2 * k + t + 1):
g = x^(i - k) * y^(j - 2 * k) * f^k * e^(m - k)
gs.append((i, j, k, g))

gs.sort()

monomials = []
for tup in gs:
for v in tup[-1].monomials():
if v not in monomials:
monomials.append(v)

mat = [[0 for j in range(len(monomials))] for i in range(len(gs))]

for i, tup in enumerate(gs):
for j, mono in enumerate(monomials):
mat[i][j] = tup[-1].monomial_coefficient(mono) * mono(X, Y)

mat = Matrix(ZZ, mat)
mat = mat.LLL()

pols = []

for i in range(len(gs)):
f = sum(mat[i, k] * monomials[k] / monomials[k](X, Y) for k in range(len(monomials)))
pols.append(f)

found = False

for i in range(len(gs)):
for j in range(i + 1, len(gs)):
f1, f2 = pols[i], pols[j]

rr = f1.resultant(f2)
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
try:
PR.<q> = PolynomialRing(ZZ)
rr = rr(q, q)
soly = int(rr.roots()[0][0])
ss = f1(q, soly)
solx = int(ss.roots()[0][0])

print(i, j)
print(solx, soly)
assert f1(solx, soly) == 0
assert f2(solx, soly) == 0

found = True
except:
pass
if found:
break
if found:
break

b, c = soly, N
Dsqrt = int(sqrt(b^2 - 4*c))
p, q = (b + Dsqrt) // 2, (b - Dsqrt) // 2
assert p * q == N

phi = (p**2 + p + 1) * (q**2 + q + 1)
d = inverse(e, phi)

class NovelSystem:
def __init__(self, p, q, e, d):
self.p = p
self.q = q
self.N = self.p * self.q

self.beta = 0.397
self.psi = (self.p ** 2 + self.p + 1) * (self.q ** 2 + self.q + 1)
self.e, self.d = e, d
self.r = 3

def add_(self, a, b):
m, n = a
k, l = b
if a[1] == 0:
a, b = b, a
m, n, k, l = k, l, m, n
if l == 0:
if n == 0:
return (m * k, m + k)
if (n + k) % self.N == 0:
if (m - n ** 2) % self.N == 0:
return (0, 0)
return ((m * k + self.r) * invert(m - n * n) % self.N, 0)
return ((m * k + self.r) * invert(n + k, self.N) % self.N, (m + n * k) * invert(n + k,self.N) % self.N)
if (m + k + n * l) % self.N != 0:
return ((m * k + (n + l) * self.r) * invert(m + k + n * l, self.N)%self.N,(n * k + m * l + self.r) * invert(m + k + n * l, self.N) % self.N)

if (n * k + m * l + self.r) % self.N == 0:
return (0, 0)
return ((m * k + (n + l) * self.r) * invert(n * k + m * l + self.r, self.N) % self.N, 0)

def mul_(self, a, n):
ans = (0, 0)
while n > 0:
if n & 1 == 1:
ans = self.add_(ans, a)
a = self.add_(a, a)
n //= 2
return ans

def encrypt(self, m):
return self.mul_(m, self.e)

def decrypt(self, c):
return self.mul_(c, self.d)

c = (25277872308079622747549210576460613586229133947234593535200353386990766871354231190884983744062724190757790170095336476433339679661865115249940491581950905446714526508336734968117122923367321009658430492676221613955154012709104353264746945809594342072744903918483080444098810305069478604650812993367066108686, 23837611977059204694294310415628596206205358541193793076161113947121055317488611201828968875769165810136018932772918536959013421962176622562932517080185242296377551991015543007194938521921909070483342042300905806379510158998331097627686209024554054114596970966269941945120227200103961459438854583220408434182)
enc = NovelSystem(p,q,e,d)
m = enc.decrypt(c)
print(long_to_bytes(m[0]) + long_to_bytes(m[1]))
#b'DASCTF{a1a4a518320a469088c64aa4fbc22438}'
Author

zealot

Posted on

2022-09-04

Updated on

2022-09-04

Licensed under