抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

2024 CISCN x 长城杯铁人三项 初赛 WriteUp

crypto比赛

发布于：2024年12月21日

次浏览

rasnd

加密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
import os

FLAG = os.getenv("FLAG").encode()
flag1 = FLAG[:15]
flag2 = FLAG[15:]

def crypto1():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q-0x114
    hint2=x2*p+y2*q-0x514
    c = pow(bytes_to_long(flag1), e, n)
    print(n)
    print(c)
    print(hint1)
    print(hint2)


def crypto2():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    hint = pow(514*p - 114*q, n - p - q, n)
    c = pow(bytes_to_long(flag2),e,n)
    print(n)
    print(c)
    print(hint)
print("==================================================================")
crypto1()
print("==================================================================")
crypto2()
print("==================================================================")

分为两层加密，第一层的话，根据两个hint的等式，直接消掉一个p或者q就行了，然后我们可以得到如下的等式

image-20241215180416983

能满足$$know * p \equiv 0\ (mod\ n)$$​，显然就是know和q有倍数关系，所以这边我们直接gcd找他们的因子就可以了

其实到这边得到这个等式之后，有挺多种方法可以做的，除了直接gcd，用solve_mod函数来做也是可以，但是因为这个在爆破，用solve_mod函数太慢了，roots应该也是一样的

当然也有使用费马小定理之后，去计算gcd(pow(2, know, n)，n)，但是这样实测也非常慢，应该是涉及了幂运算，导致爆破的速度也不理想

exp1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse, isPrime
from gmpy2 import iroot, gcd
from tqdm import trange


n1 = 17310686908778728745449354559802941946997896756243856912832576760675562312077799396599231948126385952057312169901033809840639023433489015009822009587919976821459705568133889486358608412949817482914129347583368378773163903299203660972995618294109645144315334549701096983597019368003407750914501919000206577708655243967346282848018490107046949100610467865379900940374382317941626281607014987898420673393221076557550350714383448163376148090492425725769527732209270580359317981591251860111578196496836532090641023922542177760203697279375290470122370953265605033699999237696530837166987965402030511008570227499053858415589
c1 = 16801136688776848905189583066124184181605235613468826025167164990737203785577153779968144287425030876115693615695973552178669507372756662517872836873532372873104381298512676540506180939064702446251055916192839182254160651955152472382129412375165846355186810314277540458462737775658540820351366159791897062706319738582175663161673641264485895479047085644955134173053399210772453274437437650558491343071054681468917598948947849339755507701652954057387144107636550466906541207089179622538211596281963615007936184150772982401572039877033189118382151964903168743863988864938773395153618109854626801894827551132349825934048
hint1 = 2477996433220738043622133780345574935136056477634270387691415040860651816313698350481105379393606643792493933030252187985540480193826844575786917504563212615591947336827131036061865020453648292790252977476741824597421573128221147373241709525069458483831823196234210561124714908044630499381066408414577413328176041616410349558032896455987496268
hint2 = 3137475932416527139286634960823544631965548664103993358517488315320409377390611754271852553601794986938848132860809744270918113110601431725955064776295841568126005906161924413611266529442263492723531092767851370933688086426874790580454813935496647372763389302737474208961448740153404073860193314600613913409394507452478113751942840536864875073701069386553808604224372149844554572364248242010448859521005078087076922560295908636574339399105701048880829362161183847


for x1 in trange(1, 2 ^ 11):
    for x2 in range(1, 2 ^ 11):
        know = (hint1 * x2 - hint2 * x1) + 0x114 * x2 - 0x514 * x1
        if gcd(know, n1) != 1:
            q = int(gcd(know, n1)) % n1
            e = 65537
            p = n1 // q
            phi = (p - 1) * (q - 1)
            d1 = inverse(e, phi)
            print(long_to_bytes(int(pow(c1, d1, n1))))  #b'flag{299dc9da-d8a0-'

对于第二层加密的话，直接解一个二元一次方程就可以了（利用到欧拉定理）

image-20241215180701724

exp2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse, isPrime
from gmpy2 import iroot, gcd


n2 = 17852379230831263077492443645517524782877703753693408080027712402383930619845734003191922568470099156757227518418841934348678705692807610487502903475066212024016026772695709874654434071759886847144987627824309040318953055819128137532342600218127375922396169571417060075251837131440789009020281380594551495034506456568639317302650233612183779579388683143456858997880819263732249622210137939698730563046214821230634103313220529125021058999182014757244533018469768194481448634804668491520969148003100428422906592828506579812678209726723490155171972379460695868749876659068978259534378528342458577249471485939878071066781
c2 =6457124454630977279083318517136056048994981657102713798861789132946960924788454240045022016749103040038582397266779376922458258879511238711863439172573992672269944281196228832026042788514833807851569807895848773612307107332200937270911202540034907126676830220795450294815846685344274249632796298518652045091113814607892734554835452797267462127322858988899801977668506314249485852001119727739173290541474856419753187538834950880723377243590331445468284278069552329365325402280743189571012755120987340894641050440177292175527281744110219913880353494263914566043077027966527392323264935214909513300432715625591998932278
hint2 = 7022928469215188794896159363114216103264137878166634936619665468565860894410179602925380205654804344175484822946774664548850198574273507877356676945333658983326465614140366844687501782669688509290255495687946212664207595107103278265123751844101029087286192458571447776880684457682304092209759498024170110943489459735345987232782942337036666190988352534111964443352600615267949091000136931756580923914824359453466918676964147705663433852995198096337163404473487073140676231970342261180171821824455950519091774102747410457593553416780633424458115273755507656388667082208435890865202586317510023135252865190973648070447


p = (inverse(hint2, n2) + iroot(int(inverse(hint2, n2) ^ 2 + 4 * 514 * 114 * n2), 2)[0]) // (2 * 514)
q = n2 // p
phi = (p - 1) * (q - 1)
e = 0x10001
d2 = inverse(e, phi)
print(long_to_bytes(int(pow(c2, d2, n2))))  #b'4250-9e12-63032352c599}'

fffffhash

今年的CISCN就有格做法的了

加密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import os
from Crypto.Util.number import *
def giaogiao(hex_string):
	base_num = 0x6c62272e07bb014262b821756295c58d
	x = 0x0000000001000000000000000000013b
	MOD = 2**128
	for i in hex_string:
		base_num = (base_num * x) & (MOD - 1) 
		base_num ^= i
	return base_num


giao=201431453607244229943761366749810895688

print("1geiwoligiaogiao")
hex_string = int(input(),16)
s = long_to_bytes(hex_string)

if giaogiao(s) == giao:
	print(os.getenv('FLAG'))
else:
	print("error")

思路很简单，去年是用中间相遇攻击打的，不过那个极限应该在7位左右，这次位数都不知道了，很明显用格打才行，然后爆破一手位数就可以了

以s的长度是4为例（就是把异或看做是加法，用w来代表所对应的误差

image-20241221154646466

造个得先拿等式，本地测试一下，构造出来的等式应该是类似这样的

1
2
3
4
5
6
7
8
b0, b1, b2, w0, w1, w2, w3, x = var('b0, b1, b2, w0, w1, w2, w3, x'.replace(',', ''))
bb3 = b2 * x + w2
bb2 = b1 * x + w1
bb1 = b0 * x + w0
b4 = b3 * x + w3


b4.subs(b3 = bb3).subs(b2 = bb2).subs(b1 = bb1).expand()
1
b0*x^4 + w0*x^3 + w1*x^2 + w2*x + w3

根据等式我们很明显可以构造出如下的格

image-20241221154842130

然后规约得到的w0，w1，w2，w3就是误差，满足

image-20241221163454708

由此类推即可得到s3，s2，s1，s0

exp：

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


b0 = 0x6c62272e07bb014262b821756295c58d
x = 0x0000000001000000000000000000013b
giao=201431453607244229943761366749810895688
MOD = 2**128


for num in trange(1, 50):  #num为可能的明文长度
    B = [giao]
    tmp, S = [], []
    for i in range(num - 1, -1, -1):
        tmp.append(x ^ i)
    tmp.append(b0 * x ^ num - giao)   
    L = block_matrix([[identity_matrix(num + 1), Matrix(ZZ, num + 1, 1, tmp)], 
                  [Matrix(ZZ, 1, num + 1), MOD]]) 
    Q = diagonal_matrix(ZZ, [1] * num + [128] + [2 ^ 128])
    L = L * Q
    res = L.BKZ()
    for j in res:
        if abs(j[-2]) == 128 and j[-1] == 0:
            if j[-2] == 128:
                my = j[:-2:]
                for w in range(len(my) - 1, -1, -1):
                    tmp_b = (B[-1] - my[w]) * inverse(x, MOD) % MOD
                    B.append(tmp_b)
                    S.append(((tmp_b * x) ^^ B[-2]) % MOD)  #这个注意还是要限制在模的意义下，比赛那时候就是忘记了导致格一直打不出来
                if all(0 <= w <= 256 for w in S):
                    print(bytes(S[::-1]).hex())
                    # sys.exit()
            elif j[-2] == -128:
                my = [-lll for lll in j[:-2:]]
                for w in range(len(my) - 1, -1, -1):
                    tmp_b = (B[-1] - my[w]) * inverse(x, MOD) % MOD
                    B.append(tmp_b)
                    S.append(((tmp_b * x) ^^ B[-2]) % MOD)  #这个注意还是要限制在模的意义下，比赛那时候就是忘记了导致格一直打不出来
                if all(0 <= w <= 256 for w in S):
                    print(bytes(S[::-1]).hex())
                    # sys.exit()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
020101081b04390001051a020a3d0f0f
1df2006d2e3362153d001f53102a7c2a0a591516
f7d210031a28123358f217313d0f1d070d043a2215
df3beb01fd05000d1f09147c051c6f0000090aed273d00
070e092f101f387d22071b040308766d3901030d3f091d03
fc1d0c00030202030d020b0c06191e3908121a03fb03181c041e090d0d
010f0500020704011603017f0c191e02080b0d023c0d3f0a18130b060204
f406021c0405040937031f0e7f0d1a0f020e0b0400070104010e05070e020502
fffe020f06030a05020f023a010f3c3b010f020a04067d0d0f021f040c0202070002
01030104001efb070e03050f043e027c0f1c0b3d02011b02017600020400050607040f
030406041e043d1d05011b060c07070a1f060d3c070e000f060c0f130e043c0102020d0f
01070107000d0201040507040e06010d0b070303001c0200000301010f041c0e0a3f3c02060202
030603070004040a003d030203000207011e0704fd00021c0600060005010302060707070101040d
fe0703010507021f01020d0401030203001d070e0f060f3d000f0e0103061b031f07010203013d06020e
000d0e000e0d0c0e1d01030e013e037d061e02060e02000102020207033c03001d010703050404fc073e000f
01001f000d0700003c0000001f0f07011e060101030101000602010106071c0305000e010dfc040d0100060401
010d030301030e1c06050b0700001f063f0300021e02000e0f06010100010300020200050f010207040202030f00
ff010701020003010302070005010e000102000c0a030500030000020103010007020006050a0005011c0505010c040003

其中070e092f101f387d22071b040308766d3901030d3f091d03为我们所要求的

lwewl

这题后面再更，当时比赛差点打出来了（看那个5解，真的很着急），一个lwe和一个rlwe，有段时间没碰密码太生疏了，忘了挺多，思维都迟钝了。

更新于：2024年12月21日

评论

评论区