0%

2024-强网杯-wp-crypto

今年最后一个大比赛!题目质量总体来说没有让人失望,seal是真的一点都不了解,有机会的话学一学来复现下。

EasyRSA

题目描述:

1
easy的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
#encoding:utf-8
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2

class RSAEncryptor:
def __init__(self):
self.g = self.a = self.b = 0
self.e = 65537
self.factorGen()
self.product()

def factorGen(self):
while True:
self.g = getPrime(500)
while not gmpy2.is_prime(2*self.g*self.a+1):
self.a = random.randint(2**523, 2**524)
while not gmpy2.is_prime(2*self.g*self.b+1):
self.b = random.randint(2**523, 2**524)
self.h = 2*self.g*self.a*self.b+self.a+self.b
if gmpy2.is_prime(self.h):
self.N = 2*self.h*self.g+1
print(len(bin(self.N)))
return

def encrypt(self, msg):
return gmpy2.powmod(msg, self.e, self.N)


def product(self):
with open('/flag', 'rb') as f:
self.flag = f.read()
self.enc = self.encrypt(self.flag)
self.show()
print(f'enc={self.enc}')

def show(self):
print(f"N={self.N}")
print(f"e={self.e}")
print(f"g={self.g}")


RSAEncryptor()

题目的RSA由如下素数组成:

其中$g \approx n^{0.244}$。

这显然是个已知g的Common Prime RSA攻击,找到板子:

Common Prime RSA 笔记 | 独奏の小屋 (hasegawaazusa.github.io)

其中bsgs那一行可能是sage版本问题会报错,搜下sage文档的bsgs参数然后照着改掉就好。

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
N=18609249586511447022929188601029606630816796460795187470065452150283160549624372398383148374249992521068549349516037511009027303530058706112191091689108542770802393390942693648814845389265858611340109158309645284100825624911741650444467173946569096983438455034895955228543351436008546035535031019474847660151534447157873386841134028651786166708821300066332734338450150803713659027324704224480646285707278634645234095122804559045312923819794776928194098487972764363649361713512731460059740929840789043447155551107435766468071813945331313861835289050624825980714650042186547867057986370794200778277570803957071502251887
e=65537
g=2157382166227048008151606160068683153029902706798753603550075684775242674106840467207794609506075603345430902709796320595040305496549488048759451499003
enc=1706676139782916859705617140716929473350550599143215409850324617375385155893376548401557158261122335220199922229225746433590875391358929714141838314015655361989993985070285957305126847445442699828095001203266978036575956723172054402632901673504599481917025056824986547174258708944098866240451432510310007060414500907941107101001004474036283249456230343043785187819423163986135104740039129111213967847515011092231384245986891933365405336421413444499204268699546739391271911481490278065027465465222639265899471823742196086481403499948301061349936225773314002398442541447810628796808530412232638250097430811300924120316
gamma = 500/(1024*2)
cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ^ (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y, y ^ u, (2**(cbits-1), 2**(cbits+1)), operation='*')
#(a, b, bounds, operation='*', identity=None, inverse=None, op=None)
ab = u - c
apb = v + 2 * g * c
P.<x> = ZZ[]
f = x ^ 2 - apb * x + ab
a = f.roots()
if a:
a, b = a[0][0], a[1][0]
p = 2 * g * a + 1
q = 2 * g * b + 1
assert p * q == N

from Crypto.Util.number import *
print(long_to_bytes(int(pow(enc,inverse(e,(p-1)*(q-1)),N))))


#flag{a4fc2d54-0ab3-492a-a82b-762705d83cff}



apbq

题目描述:

1
I obtained several sets of ap + bq through channel measurement. Can you solve it?

题目:

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
from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys

class RSA():
def __init__(self, privatekey, publickey):
self.p, self.q, self.d = privatekey
self.n, self.e = publickey

def encrypt(self, plaintext):
if isinstance(plaintext, bytes):
plaintext = bytes_to_long(plaintext)
ciphertext = pow(plaintext, self.e, self.n)
return ciphertext

def decrypt(self, ciphertext):
if isinstance(ciphertext, bytes):
ciphertext = bytes_to_long(ciphertext)
plaintext = pow(ciphertext, self.d, self.n)
return plaintext

def get_keypair(nbits, e = 65537):
p = getPrime(nbits//2)
q = getPrime(nbits//2)
n = p * q
d = inverse(e, n - p - q + 1)
return (p, q, d), (n, e)

if __name__ == '__main__':
pt = './output.txt'
fout = open(pt, 'w')
sys.stdout = fout

block_size = ceil(len(flag)/3)
flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
e = 65537

print(f'[+] Welcome to my apbq game')
# stage 1
print(f'┃ stage 1: p + q')
prikey1, pubkey1 = get_keypair(1024)
RSA1 = RSA(prikey1, pubkey1)
enc1 = RSA1.encrypt(flag[0])
print(f'┃ hints = {prikey1[0] + prikey1[1]}')
print(f'┃ public key = {pubkey1}')
print(f'┃ enc1 = {enc1}')
print(f'----------------------')

# stage 2
print(f'┃ stage 2: ai*p + bi*q')
prikey2, pubkey2 = get_keypair(1024)
RSA2 = RSA(prikey2, pubkey2)
enc2 = RSA2.encrypt(flag[1])
kbits = 180
a = [getRandomNBitInteger(kbits) for i in range(100)]
b = [getRandomNBitInteger(kbits) for i in range(100)]
c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
print(f'┃ hints = {c}')
print(f'┃ public key = {pubkey2}')
print(f'┃ enc2 = {enc2}')
print(f'----------------------')

# stage 3
print(f'┃ stage 3: a*p + q, p + bq')
prikey3, pubkey3 = get_keypair(1024)
RSA3 = RSA(prikey3, pubkey3)
enc3 = RSA2.encrypt(flag[2])
kbits = 512
a = getRandomNBitInteger(kbits)
b = getRandomNBitInteger(kbits)
c1 = a*prikey3[0] + prikey3[1]
c2 = prikey3[0] + b*prikey3[1]
print(f'┃ hints = {c1, c2}')
print(f'┃ public key = {pubkey3}')
print(f'┃ enc3 = {enc3}')

题目分成三部分,均需要根据已知数据得到p,q。

part1

给出额外信息:

这个没啥好说的,联立消元解方程。

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

#stage1
hint1 = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
n1, e1 = (89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589, 65537)
enc1 = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247

PR.<p,q> = PolynomialRing(ZZ)
f1 = p*q - n1
f2 = p+q - hint1
res = f1.sylvester_matrix(f2,q).det().univariate_polynomial().roots(multiplicities=False)
p1 = res[0]
q1 = res[1]

print(long_to_bytes(int(pow(enc1, inverse(e1,(p1-1)*(q1-1)), n1))))

#flag{yOu_can_

part2

给出额外信息:

总共有100组数据,其中p,q都是512bit的,而ai,bi则显得比较小,仅有180bit。

直接规约

由于有180bit这样的小量存在,这就自然让人想到造格,为了使目标向量较短,所以当然要消去p、q才行。因此固定前两组数据,将3-100组数据和前两组数据分别做两次消元,就可以得到一个只含a1,a2,ai,b1,b2,bi的等式如下:

提出共有的系数a1,也就是:

显然作为系数的$a_jb_k \pm a_kb_j$只有360bit左右,是个小量,因此将所有数据放入格中就可以把他们规约出来。

之后的问题是如何由规约出的这些和差来求出所有a、b来,这一部分可以参考maple的做法,大致思路是把这三个等式做groebner_basis,由于等式不够,所以肯定不能得到a、b的值,但是却可以得到a、b的线性等式,因此可以再做一次LLL后gcd解决:

DownUnderCTF 2023 Writeups | 廢文集中區 (maple3142.net)

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
#stage2
from re import findall
from subprocess import check_output
from itertools import *

def flatter(M):
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

hint2 =
n2, e2 = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
enc2 = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244

h = hint2
nums = 98
L = Matrix(ZZ, 1+nums*2, 1+nums*3)
for i in range(1+nums*2):
L[i,i] = 1
for i in range(nums):
L[0,1+nums*2+i] = h[i+2]
L[2*i+1,1+nums*2+i] = h[0]
L[2*i+2,1+nums*2+i] = h[1]
L[:,-nums:] *= 2^512
L = flatter(L)



v,t,u = L[0,0],L[0,1],L[0,2]
a1s, a2s, a3s, b1s, b2s, b3s = QQ["a1,a2,a3,b1,b2,b3"].gens()
for sign in product((-1, 1), repeat=3):
I = ideal(
[
a3s * b2s - a2s * b3s + sign[0] * t,
a3s * b1s - a1s * b3s + sign[1] * u,
a2s * b1s - a1s * b2s + sign[2] * v,
]
)
if I.dimension() != -1:
print(sign)
print("dim", I.dimension())

def step2(f):
# this f is in the form of k1*a1+k2*a2+k3*a3==0
# for some reason, k1*b1+k2*b2+k3*b3==0 also holds
# use LLL to find it
print("=" * 40)
print(f)
L = matrix(f.coefficients()).T.augment(matrix.identity(3))
L[:, 0] *= n2
L = L.LLL()
print(L[0])
print(L[1])
v1 = L[0]
v2 = L[1]
xs = []
for c1, c2 in product((-2, -1, 0, 1, 2), repeat=2):
v = c1 * v1 + c2 * v2
_, x1, x2, x3 = v
if all([0 <= x <= 2**180 for x in (x1, x2, x3)]):
xs.append((x1, x2, x3))
# we don't know which one is correct pair of (a1, a2, a3) and (b1, b2, b3)
# just try all combinations
for g1, g2 in combinations(xs, 2):
a1r, a2r, a3r = g1
b1r, b2r, b3r = g2
q = gcd(a2r * h[0] - a1r * h[1], n2)
if 1 < q < n2:
p = n2 // q
e = 0x10001
d = inverse_mod(e, (p - 1) * (q - 1))
m = pow(enc2, d, n2)
flag = int(m).to_bytes(1024, "big").strip(b"\x00")
print(p,flag)
exit()

step2(I.groebner_basis()[1])

#s0lve_the_@pb
正交格

赛后听群友讨论,发现这个题用正交格的确更加简单,因为hint中的一个值其实就是:

我们有一百组等式,因此可以拼起来得到:

接下来就是正交格的常规操作,找到矩阵$M$使得:

那么有:

而$AB$比较短,因此预期可以对$M$的右核做LLL找到$AB$,从而做GCD恢复p、q。

实际上找到的是B和与B约减过的A

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
from Crypto.Util.number import *

hint2 =
n, e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
c = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244


######################################################################################### recover A,B using orthogonal Lattice
L = block_matrix(ZZ,[
[1,Matrix(ZZ,hint2).T],
])
L = L.LLL()

M = []
for i in L:
if(i[-1] == 0):
M.append(i[:-1])
M = Matrix(ZZ,M)

Ker = M.right_kernel().basis()
Ker = Matrix(ZZ, Ker)
AB = Ker.LLL()

B = list(map(abs, AB[1]))
A = [i+j for i,j in zip(AB[0], B)]


######################################################################################### recover p,q
p = GCD(n, hint2[0]*B[1]-hint2[1]*B[0])
q = n // p
print(long_to_bytes(int(pow(c, inverse(e,(p-1)*(q-1)), n))))


#s0lve_the_@pb

part3

给出额外信息:

其中a,b和p,q均为512bit的数字。

两个式子显然可以构造出一个模n下的等式:

展开之后可以发现,p、q的乘积又被消掉了,所以整个式子其实是线性的:

这个等式中,两个未知量p、q仅有模数n的一半bit而已,很接近LLL可以规约出来的范围,小范围爆破一下:

然后LLL就可以找到p、q了。

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

#stage3
hint3 = (68510878638370415044742935889020774276546916983689799210290582093686515377232591362560941306242501220803210859757512468762736941602749345887425082831572206675493389611203432014126644550502117937044804472954180498370676609819898980996282130652627551615825721459553747074503843556784456297882411861526590080037, 117882651978564762717266768251008799169262849451887398128580060795377656792158234083843539818050019451797822782621312362313232759168181582387488893534974006037142066091872636582259199644094998729866484138566711846974126209431468102938252566414322631620261045488855395390985797791782549179665864885691057222752)
n3,e3 = (94789409892878223843496496113047481402435455468813255092840207010463661854593919772268992045955100688692872116996741724352837555794276141314552518390800907711192442516993891316013640874154318671978150702691578926912235318405120588096104222702992868492960182477857526176600665556671704106974346372234964363581, 65537)
enc3 = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
c1,c2 = hint3

brute = 2
for i in range(2^brute):
for j in range(2^brute):
L = Matrix(ZZ, [
[1,0,0,2^brute*c1],
[0,1,0,2^brute*c2],
[0,0,2^(512-brute),c1*i+c2*j-c1*c2],
[0,0,0,n3]
])
L[:,-1:] *= n3
res = L.LLL()[0]

p = 2^brute*abs(res[0])+i
if(n3 % p == 0):
print(p)

但是,素数明明分解掉了,为什么求不出明文?然后仔细看源代码发现有乌龙:

1
2
RSA3 = RSA(prikey3, pubkey3)
enc3 = RSA2.encrypt(flag[2])

第三部分还是用第二部分的密钥加密的,所以其实不做第三部分也行。



21_steps

题目描述:

1
weight it in 21 steps!

题目:

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
import re
import random
from secrets import flag
print(f'Can you weight a 128 bits number in 21 steps')
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'

command = input().strip()
assert command[-1] == ';'
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])

step = 21
for i in command[:-1].split(';'):
t = i.translate(str.maketrans('', '', '=AB0123456789'))
if t in ['>>', '<<', '+', '-', '&', '^']:
step -= 1
elif t in ['*', '/', '%']:
step -= 3
if step < 0:exit()

success = 0
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
for _ in range(100):
A = random.randrange(0, 2**128)
wa = w(A)
B = 0
try : exec("global A; global B;" + command)
except : exit()
if A == wa:
success += 1

if success == 100:
print(flag)

整个题目任务就是:

  • 输入不超过21条如下格式的指令:

    如果是乘除或者模的话,一条更比三条强

  • 用这些指令计算出一个128bit以内数字的汉明重量

搜一下hamming weight algorithm之类的关键词,可以找到:

algorithm - Calculating Hamming Weight in O(1) - Stack Overflow

这是32bit的版本,改成128bit之后再转指令就行。

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
46
47
48
49
50
51
52
from Crypto.Util.number import *
from pwn import *


def popcountRE(A):
B = 0
B = A >> 1
B = B & 113427455640312821154458202477256070485
A = A - B
#x -= (x >> 1) & 0x55555555555555555555555555555555
B = A >> 2
B = B & 68056473384187692692674921486353642291
A = A & 68056473384187692692674921486353642291
A = A + B
#x = (x & 0x33333333333333333333333333333333) + ((x >> 2) & 0x33333333333333333333333333333333)
B = A >> 4
A = A + B
A = A & 20016609818878733144904388672456953615
#x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
A = A * 1334440654591915542993625911497130241
A = A & 340282366920938463463374607431768211455
A = A >> 120
#return ((x * 0x01010101010101010101010101010101) & 0xffffffffffffffffffffffffffffffff) >> 120
return A

instructions=[
"B=A>>1",
"B=B&113427455640312821154458202477256070485",
"A=A-B",
"B=A>>2",
"B=B&68056473384187692692674921486353642291",
"A=A&68056473384187692692674921486353642291",
"A=A+B",
"B=A>>4",
"A=A+B",
"A=A&20016609818878733144904388672456953615",
"A=A*1334440654591915542993625911497130241",
"A=A&340282366920938463463374607431768211455",
"A=A>>120",
]

msg=";".join(instructions) + ";"
command=msg

sh = remote("47.94.195.201", 38958)
sh.recvuntil(b'Can you weight a 128 bits number in 21 steps')
sh.sendline(command.encode())
print(sh.recvline())
print(sh.recvline())


#flag{you_can_weight_it_in_21_steps!}



traditional_game

题目描述:

1
Since you've made it here, let's now play a Traditional Game from 1997.

题目:

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
from Crypto.Util.number import getPrime,bytes_to_long
from secret import secret,flag
import random
import time
import os
import signal

def _handle_timeout(signum, frame):
raise TimeoutError('function timeout')

timeout = 300
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

random.seed(secret + str(int(time.time())).encode())

class RSA:
def __init__(self):
self.p = getPrime(512)
self.q = getPrime(512)
self.e = getPrime(128)
self.n = self.p * self.q
self.phi = (self.p - 1) * (self.q - 1)
self.d = pow(self.e, -1, self.phi)

def get_public_key(self):
return (self.n, self.e)

def get_private_key(self, blind_bit=None, unknown_bit=None):
if blind_bit is not None and unknown_bit is not None:
blind = getPrime(blind_bit)
d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
return (d_, blind)
else:
return (self.d, 0)

def encrypt(self, m):
if type(m) == bytes:
m = bytes_to_long(m)
elif type(m) == str:
m = bytes_to_long(m.encode())
return pow(m, self.e, self.n)

def game(self,m0,m1,b):
return self.encrypt([m0,m1][b])


rsa = RSA()
token = os.urandom(66)

print( "[+] Welcome to the game!")
print(f"[+] rsa public key: {rsa.get_public_key()}")

coins = 100
price = 100
while coins > 0:
print("=================================")
b = random.randint(0,1)
c = rsa.game(
b'bit 0:' + os.urandom(114),
b'bit 1:' + os.urandom(114),
b)
print("[+] c:",c)
guessb = int(input("[-] b:"))
coins -= 1
if guessb == b:
price -= 1
print("[+] correct!")
else:
print("[+] wrong!")

if price != 0:
print("[-] game over!")
exit()

blind_bit = 40
unknown_bit = 365

d_,blind = rsa.get_private_key(blind_bit, unknown_bit)

print( "[+] Now, you have permission to access the privkey!")
print(f"[+] privkey is: ({d_},{blind}).")
print(f"[+] encrypt token is: {rsa.encrypt(bytes_to_long(token))}")

guess_token = bytes.fromhex(input("[-] guess token:"))
if guess_token == token:
print("[+] correct token, here is your flag:",flag)
else:
print("[-] wrong token")

题目分为两个部分,第一个部分是要连续猜对100次硬币,第二部分是要解一个leak了d部分数据的RSA。

part1

第一部分主要代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
coins = 100
price = 100
while coins > 0:
print("=================================")
b = random.randint(0,1)
c = rsa.game(
b'bit 0:' + os.urandom(114),
b'bit 1:' + os.urandom(114),
b)
print("[+] c:",c)
guessb = int(input("[-] b:"))
coins -= 1
if guessb == b:
price -= 1
print("[+] correct!")
else:
print("[+] wrong!")

if price != 0:
print("[-] game over!")
exit()

每一轮的硬币值是randint(0,1)产生的,而random初始种子的设定是:

1
random.seed(secret + str(int(time.time())).encode())

虽然和时间有关,但是可以看到在前面还附加了一个秘密值secret,这是我们不知道的,因此不能通过本地时间来预测b的值。

然而,由于时间戳做了int处理,因此如果在同一秒内连接上靶机的话,随机数种子就会完全相同。所以做法也很简单,同时开两个靶机,一个随便发数据,去拿到所有的b,另一个把这些正确的b发过去就好了。

从c判断出b我觉得应该不太可行

part2

第二部分要解一个按如下方式泄露私钥d部分数据的RSA:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class RSA:
def __init__(self):
self.p = getPrime(512)
self.q = getPrime(512)
self.e = getPrime(128)
self.n = self.p * self.q
self.phi = (self.p - 1) * (self.q - 1)
self.d = pow(self.e, -1, self.phi)

def get_public_key(self):
return (self.n, self.e)

def get_private_key(self, blind_bit=None, unknown_bit=None):
if blind_bit is not None and unknown_bit is not None:
blind = getPrime(blind_bit)
d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
return (d_, blind)
else:
return (self.d, 0)

我们会有d_和blind,记blind为$B$,从这两个数据我们可以把d表示成如下形式:

其中dm是未知的,为365bit左右。

dh和dl可以用d_通过如下方式计算出来:

1
2
dh = (d_ >> unknown_bit) // blind
dl = d_ % blind

注意到e是128bit,我们又有d的近似高位,因此我们可以用:

测试一下可以发现这样近似的k和准确的k仅仅差1。

而为了利用上d的已知信息,仍然老规矩利用下面的等式:

将已知的d部分数据和n代入:

移项整理一下得到:

那么就有:

这是一个线性等式,而且模数M比起dm,p+q这两个未知量来说显得相当大,因此可以考虑造格LLL求解,这一部分测试代码如下:

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
from Crypto.Util.number import *

################################################################################# gen data
p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
blind_bit = 40
unknown_bit = 365
if blind_bit is not None and unknown_bit is not None:
blind = getPrime(blind_bit)
d_ = ((int(d >> unknown_bit) // blind * blind) << unknown_bit) + int(d % blind)


################################################################################# get k,dh,dl
k = (e*d_ - 1) // n + 1
dh = (d_ >> unknown_bit) // blind
dl = d_ % blind


################################################################################# LLL
M = e*(2^unknown_bit*blind*dh+dl) - k*(n+1) - 1
K = 2^(513-unknown_bit)
L = matrix(ZZ,[
[K,0,e*blind],
[0,1,k],
[0,0,M]
])
L[:,-1:] *= M
L = L.LLL()
L[:,:1] /= K

for i in L:
print(i)

然而会发现,我们预期的向量似乎并不在LLL之后的向量中:

而出现在第一行的是仅有128bit左右的向量,第二行虽然数量级与目标向量相近,但是与我们的目标向量有较大的误差。记第二行向量为:

那么p+q和实际y的差值大约有405bit,刚好是unknownbit+blindbit=365+40。

此时我们可以得到第一个信息,由于误差是405bit左右,那么由第二行向量可以获得p+q的100出头的高位。

那么低位呢?此时需要想一下LLL之后的第一行究竟是什么,为什么会有一个更短的向量在目标向量之前,回顾一下造格的等式:

可以发现由于系数比起我们想要的根来说更小,所以下面这种形式当然也是解:

LLL之后的第一行正是这样的向量:

而第二行的误差就来自于与这个短向量进行约减,也就是说LLL得到的第二行其实应该是:

因此我们有:

因此我们可以拿到p+q模eB下的值,此时我们等价于拥有了p+q的高低位,转化成已知p的高低位copper即可。

这个高低位并不是二进制位,而是模eB意义下的,这个转化也很简单,有兴趣的师傅还可以看一看我出的这个题目:

[tangcuxiaojkuai]easy_copper2 | NSSCTF

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
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
from Crypto.Util.number import *
from tqdm import *


################################################################################# data
n, e = 85326799303014496026064371730108772674311332235197622668632563161991602151711567135121280447576711444698674128128361298108919951648223986067215747231280671858955299505770967232491254103263536714363392698361887554304255293991522369123049450389169430042203506125207632731477059899911948136482137033584148217327, 254105853966712863308295955275449077351
d_, blind = 21378651607895524021279554589638483737491146093477974150650211288463988209605132503571807152155799637952833578907915487652394101057156932695702372344185513500134378667094923442647974423915643213700386663283702204046537471425141802799603607927835879677131664511051343930330150649244588933823965535065854996174,1033378191583
c = 53742732129028328063112055299975805421399396945032126712022723372351554830940247890238890674346304685771599765645061449905866414886468887177488826724343823941484173305683401484367061591100780027467534437239106132736115748345075082986831034406103970493456683245813494600511020286115561513979129441895596164513


################################################################################# get k,dh,dl
blind_bit = 40
unknown_bit = 365
k = (e*d_ - 1) // n + 1
dh = (d_ >> unknown_bit) // blind
dl = d_ % blind


################################################################################# LLL
M = e*(2^unknown_bit*blind*dh+dl) - k*(n+1) - 1
K = 2^(513-unknown_bit)
L = matrix(ZZ,[
[K,0,e*blind],
[0,1,k],
[0,0,M]
])
L[:,-1:] *= M
L = L.LLL()
L[:,:1] /= K
pqh = L[1][1] // (e*blind) * (e*blind)
pql = L[1][1] % (e*blind)


################################################################################# copper
############################################### get ph
PR.<x> = PolynomialRing(RealField(1000))
f = x*(pqh-x) - n
ph = int(f.roots()[0][0]) // (e*blind) * (e*blind)
############################################### get pl
R.<x> = PolynomialRing(Zmod(e))
fe = x*(pql-x) - n
rese = fe.roots()

R.<x> = PolynomialRing(Zmod(blind))
fb = x*(pql-x) - n
resb = fb.roots()

for i in rese:
for j in tqdm(resb):
nlist = [e,blind]
clist = [int(i[0]),int(j[0])]
pl = int(crt(clist,nlist))

############################################### get p
PR.<x> = PolynomialRing(Zmod(n))
f = ph + e*blind*x + pl
f = f.monic()
res = f.small_roots(X=2^(512-105-167+3), beta=0.499, epsilon=0.02)
if(res != []):
p = int(ph + e*blind*res[0] + pl)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(int(pow(c, d, n))).hex())
assert n % p == 0
break


#0a00d817e70c0e83bcabd4d38d88a7e08c5427eeaa68e289741dca172597e73b2713ca3f88f8c5205a2cc136cad8bbb6f82d8b35e2efd23cad8cfed470db99e77a81
#flag{eeeeeeeeeeeeeeeeeeeeezzzz_game_will_be_over}



electronic_game

题目描述:

1
After finishing traditional cigarettes, let's try vaping some electronic cigarettes.

题目:

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
from sage.all import *
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from base64 import b64encode
from random import *
from secret import flag
import signal

def _handle_timeout(signum, frame):
raise TimeoutError('function timeout')

timeout = 66
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

def qary_trans_to_int(x, q):
return sum([int(x[i]) * q**i for i in range(len(x))])

def encode(f, q):
try:
return b64encode(long_to_bytes(qary_trans_to_int(f.polynomial().coefficients(sparse = False), q)))
except:
return b64encode(long_to_bytes(qary_trans_to_int(f.coefficients(sparse = False), q)))

def generate_irreducible_polynomial(R, n):
while True:
f = R.random_element(degree=n)
while f.degree() != n:
f = R.random_element(degree=n)
if f.is_irreducible():
return f

def generate_sparse_irreducible_polynomial(R, n):
x = R.gen()
while True:
g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
if (x**n + g + 1).is_irreducible():
return x**n + g + 1

def random_polynomial(R, n, beta):
return sum(randrange(-beta, beta) * R.gen()**i for i in range(randint(0, n))) + R.gen()**n

q = 333337
n = 128
beta = 333
chance = 111
polyns = beta//chance
bound = 106
R = PolynomialRing(GF(q),'x')

F = generate_irreducible_polynomial(R,n).monic()

k1 = GF(q**n, name = 'a', modulus = generate_sparse_irreducible_polynomial(R,n).monic())
k2 = GF(q**n, name = 'b', modulus = F)

phi = FiniteFieldHomomorphism_generic(Hom(k1, k2))

print("F:", encode(F,q).decode())

win_count = 0
for _ in range(chance):
opt = randint(0, 1)
if opt:
As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)]
else:
As = [k2.random_element() for i in range(polyns)]

for i in range(polyns):
print(f"As[{i}]: {encode(As[i],q).decode()}")

opt_guess = input("Guess the option[0/1]: ")
if int(opt_guess) != opt:
print("Wrong guess!")
else:
win_count += 1
print("Correct guess!")

if win_count >= bound:
print("You are so smart! Here is your flag:")
print(flag)
else:
print("No flag for you!")

题目是一个多项式的decision,他会先生成两个模q下度为128的不可约多项式$G,F$,然后用他们作为模多项式构造出128次的有限扩域:

在这里G是一个系数均为1、0、-1且除了x^128外度不超过65的多项式,而F则是完全随机的多项式。

然后生成一个有限域之间的同态:

不给出G,但给出我们F,之后进入如下decision:

  • 如果当前opt为1,则生成三个:

    其中Ai是k1上的系数不超过beta,且高次项有一些0的多项式(因为是randint(0, n)

  • 如果当前opt为0,则生成三个k2上的随机多项式

我们需要在111次里成功106次,从而拿到flag。

偷鸡x1

第一反应当然是偷鸡!很明显能感觉到,opt为1的时候涉及同态计算,计算量会比opt为0要大不少,因此测一下本地时间会发现确实有区别:

1
2
3
4
5
6
7
8
T1 = time.time()
As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)]
T2 = time.time()
As = [k2.random_element() for i in range(polyns)]
T3 = time.time()

print(T2-T1)
print(T3-T2)
1
2
0.005532741546630859
0.0006456375122070312

然而实际测试发现,与靶机交互的时候这种差别完全是看不出来的,只能作罢。

坐在靶机上打也许能行

同态的矩阵表示

那么就老实一点想其他办法,能显著感受到的区别在于:opt为1的时候,其模多项式G和随机多项式Ai的系数都比较小(尤其是G),而商环下的多项式乘法是可以转化成矩阵的,因此第一个想法是能不能转化成一个正交格问题来做区分。

首先需要理解同态的具体过程。对于k1中多项式A到k2的同态,其步骤为:

  • 将k1的不可约多项式$G$放到k2中求根,得到core

  • 在k2中计算:

    此时就有:

而如果把多项式看作由系数组成的向量,那么这个过程就是:

其中C就是在k2中代入core到多项式的矩阵。

测试过程

这一部分要用代码测试一下,首先是:

1
2
phi = FiniteFieldHomomorphism_generic(Hom(k1, k2)) 
print(phi)

直接打印phi的话就可以看到G的不可约多项式在F中的求根结果,如下是一个示例:

1
2
3
4
Ring morphism:
From: Finite Field in a of size 333337^128
To: Finite Field in b of size 333337^128
Defn: a |--> 73459*b^127 + 45965*b^126 + 154611*b^125 + 228072*b^124 + 222553*b^123 + 293345*b^122 + 296462*b^121 + 325636*b^120 + 110826*b^119 + 325665*b^118 + 275677*b^117 + 97527*b^116 + 274255*b^115 + 225271*b^114 + 97921*b^113 + 81246*b^112 + 328017*b^111 + 269156*b^110 + 193081*b^109 + 312527*b^108 + 189230*b^107 + 150907*b^106 + 30731*b^105 + 125825*b^104 + 31844*b^103 + 327717*b^102 + 1433*b^101 + 190323*b^100 + 897*b^99 + 63791*b^98 + 280126*b^97 + 297186*b^96 + 135758*b^95 + 56307*b^94 + 171871*b^93 + 148171*b^92 + 153362*b^91 + 232503*b^90 + 95473*b^89 + 250132*b^88 + 232460*b^87 + 109887*b^86 + 32836*b^85 + 130012*b^84 + 322154*b^83 + 215014*b^82 + 77906*b^81 + 272936*b^80 + 200528*b^79 + 190313*b^78 + 282062*b^77 + 177772*b^76 + 68233*b^75 + 110862*b^74 + 301957*b^73 + 240838*b^72 + 273201*b^71 + 130583*b^70 + 30294*b^69 + 125390*b^68 + 131116*b^67 + 296750*b^66 + 66239*b^65 + 122663*b^64 + 66040*b^63 + 327828*b^62 + 72383*b^61 + 278100*b^60 + 51545*b^59 + 110734*b^58 + 306201*b^57 + 209521*b^56 + 292167*b^55 + 211179*b^54 + 49583*b^53 + 66788*b^52 + 177292*b^51 + 290824*b^50 + 242571*b^49 + 201457*b^48 + 234932*b^47 + 127565*b^46 + 60668*b^45 + 252324*b^44 + 124866*b^43 + 211782*b^42 + 306845*b^41 + 60190*b^40 + 34820*b^39 + 200959*b^38 + 139847*b^37 + 295175*b^36 + 41736*b^35 + 187566*b^34 + 185605*b^33 + 275307*b^32 + 200245*b^31 + 227416*b^30 + 100274*b^29 + 281802*b^28 + 89121*b^27 + 223111*b^26 + 50072*b^25 + 112360*b^24 + 126574*b^23 + 47014*b^22 + 15719*b^21 + 206201*b^20 + 79590*b^19 + 224184*b^18 + 152022*b^17 + 260161*b^16 + 273909*b^15 + 241370*b^14 + 108763*b^13 + 250304*b^12 + 102586*b^11 + 65473*b^10 + 224710*b^9 + 165509*b^8 + 143187*b^7 + 328267*b^6 + 238494*b^5 + 322023*b^4 + 95192*b^3 + 305212*b^2 + 78695*b + 320671

改一改变量名,固定一组F、G进行观察:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
F = x^128 + 148280*x^127 + 125296*x^126 + 303967*x^125 + 82692*x^124 + 148324*x^123 + 297200*x^122 + 19852*x^121 + 61039*x^120 + 257505*x^119 + 249895*x^118 + 308497*x^117 + 279156*x^116 + 14767*x^115 + 247088*x^114 + 295630*x^113 + 282010*x^112 + 216734*x^111 + 106241*x^110 + 221465*x^109 + 257885*x^108 + 209863*x^107 + 169559*x^106 + 46083*x^105 + 313025*x^104 + 279179*x^103 + 282980*x^102 + 301293*x^101 + 303914*x^100 + 279971*x^99 + 48418*x^98 + 132348*x^97 + 34804*x^96 + 175616*x^95 + 99277*x^94 + 251209*x^93 + 271846*x^92 + 246439*x^91 + 119459*x^90 + 247587*x^89 + 161063*x^88 + 199742*x^87 + 84803*x^86 + 203535*x^85 + 72656*x^84 + 131490*x^83 + 133892*x^82 + 100587*x^81 + 228110*x^80 + 122509*x^79 + 35010*x^78 + 206327*x^77 + 44620*x^76 + 296935*x^75 + 181274*x^74 + 176313*x^73 + 57085*x^72 + 108158*x^71 + 107810*x^70 + 206948*x^69 + 178184*x^68 + 210102*x^67 + 204244*x^66 + 176239*x^65 + 273323*x^64 + 93382*x^63 + 293018*x^62 + 116418*x^61 + 121990*x^60 + 7698*x^59 + 17397*x^58 + 269648*x^57 + 109790*x^56 + 44374*x^55 + 302391*x^54 + 266167*x^53 + 244403*x^52 + 185576*x^51 + 289374*x^50 + 300327*x^49 + 331430*x^48 + 180450*x^47 + 71904*x^46 + 196869*x^45 + 277619*x^44 + 176135*x^43 + 161273*x^42 + 214612*x^41 + 214480*x^40 + 160252*x^39 + 188335*x^38 + 94120*x^37 + 212575*x^36 + 116820*x^35 + 239270*x^34 + 122340*x^33 + 294503*x^32 + 292932*x^31 + 332717*x^30 + 106872*x^29 + 126922*x^28 + 179567*x^27 + 235901*x^26 + 83800*x^25 + 24144*x^24 + 187639*x^23 + 308050*x^22 + 223365*x^21 + 29187*x^20 + 278083*x^19 + 6529*x^18 + 55605*x^17 + 33840*x^16 + 61834*x^15 + 164019*x^14 + 42485*x^13 + 57332*x^12 + 190124*x^11 + 195118*x^10 + 94061*x^9 + 263431*x^8 + 115313*x^7 + 136480*x^6 + 315639*x^5 + 120028*x^4 + 143444*x^3 + 140329*x^2 + 75249*x + 73094
G = x^128 + x^39 + 333336*x^37 + 333336*x^36 + 333336*x^35 + 333336*x^34 + x^33 + x^30 + x^27 + 333336*x^26 + x^25 + 333336*x^24 + x^22 + x^21 + x^20 + x^19 + x^17 + 333336*x^16 + 333336*x^15 + 333336*x^14 + x^13 + x^12 + 333336*x^10 + 333336*x^9 + x^8 + x^7 + 333336*x^5 + 333336*x^4 + 333336*x^3 + 333336*x + 1

k1 = GF(q^n, name = 'a', modulus = G)
k2 = GF(q^n, name = 'b', modulus = F)
a, b = k1.gen(), k2.gen()

phi = FiniteFieldHomomorphism_generic(Hom(k1, k2))
#print(phi)

core = 73459*b^127 + 45965*b^126 + 154611*b^125 + 228072*b^124 + 222553*b^123 + 293345*b^122 + 296462*b^121 + 325636*b^120 + 110826*b^119 + 325665*b^118 + 275677*b^117 + 97527*b^116 + 274255*b^115 + 225271*b^114 + 97921*b^113 + 81246*b^112 + 328017*b^111 + 269156*b^110 + 193081*b^109 + 312527*b^108 + 189230*b^107 + 150907*b^106 + 30731*b^105 + 125825*b^104 + 31844*b^103 + 327717*b^102 + 1433*b^101 + 190323*b^100 + 897*b^99 + 63791*b^98 + 280126*b^97 + 297186*b^96 + 135758*b^95 + 56307*b^94 + 171871*b^93 + 148171*b^92 + 153362*b^91 + 232503*b^90 + 95473*b^89 + 250132*b^88 + 232460*b^87 + 109887*b^86 + 32836*b^85 + 130012*b^84 + 322154*b^83 + 215014*b^82 + 77906*b^81 + 272936*b^80 + 200528*b^79 + 190313*b^78 + 282062*b^77 + 177772*b^76 + 68233*b^75 + 110862*b^74 + 301957*b^73 + 240838*b^72 + 273201*b^71 + 130583*b^70 + 30294*b^69 + 125390*b^68 + 131116*b^67 + 296750*b^66 + 66239*b^65 + 122663*b^64 + 66040*b^63 + 327828*b^62 + 72383*b^61 + 278100*b^60 + 51545*b^59 + 110734*b^58 + 306201*b^57 + 209521*b^56 + 292167*b^55 + 211179*b^54 + 49583*b^53 + 66788*b^52 + 177292*b^51 + 290824*b^50 + 242571*b^49 + 201457*b^48 + 234932*b^47 + 127565*b^46 + 60668*b^45 + 252324*b^44 + 124866*b^43 + 211782*b^42 + 306845*b^41 + 60190*b^40 + 34820*b^39 + 200959*b^38 + 139847*b^37 + 295175*b^36 + 41736*b^35 + 187566*b^34 + 185605*b^33 + 275307*b^32 + 200245*b^31 + 227416*b^30 + 100274*b^29 + 281802*b^28 + 89121*b^27 + 223111*b^26 + 50072*b^25 + 112360*b^24 + 126574*b^23 + 47014*b^22 + 15719*b^21 + 206201*b^20 + 79590*b^19 + 224184*b^18 + 152022*b^17 + 260161*b^16 + 273909*b^15 + 241370*b^14 + 108763*b^13 + 250304*b^12 + 102586*b^11 + 65473*b^10 + 224710*b^9 + 165509*b^8 + 143187*b^7 + 328267*b^6 + 238494*b^5 + 322023*b^4 + 95192*b^3 + 305212*b^2 + 78695*b + 320671

f = random_polynomial(R, n, beta)
print(phi(f))
print(sum(list(f)[i]*core^i for i in range(n+1)))

结果为:

1
2
90651*b^127 + 48921*b^126 + 317095*b^125 + 7873*b^124 + 274789*b^123 + 160062*b^122 + 207308*b^121 + 237019*b^120 + 204263*b^119 + 267380*b^118 + 114003*b^117 + 149239*b^116 + 58126*b^115 + 55786*b^114 + 286352*b^113 + 305047*b^112 + 117630*b^111 + 266050*b^110 + 180452*b^109 + 272098*b^108 + 28949*b^107 + 197679*b^106 + 203360*b^105 + 226493*b^104 + 75252*b^103 + 265873*b^102 + 225485*b^101 + 59931*b^100 + 60212*b^99 + 289428*b^98 + 83485*b^97 + 295707*b^96 + 176312*b^95 + 4467*b^94 + 206451*b^93 + 258643*b^92 + 201874*b^91 + 281183*b^90 + 11864*b^89 + 104831*b^88 + 279072*b^87 + 6542*b^86 + 289955*b^85 + 95606*b^84 + 283515*b^83 + 37343*b^82 + 137199*b^81 + 157867*b^80 + 68322*b^79 + 264266*b^78 + 78000*b^77 + 39760*b^76 + 111509*b^75 + 2120*b^74 + 293613*b^73 + 45674*b^72 + 220453*b^71 + 119761*b^70 + 207557*b^69 + 67778*b^68 + 18979*b^67 + 204342*b^66 + 126067*b^65 + 320210*b^64 + 295529*b^63 + 330547*b^62 + 30523*b^61 + 49342*b^60 + 210441*b^59 + 293588*b^58 + 13751*b^57 + 162848*b^56 + 26422*b^55 + 216110*b^54 + 20437*b^53 + 329478*b^52 + 191422*b^51 + 127252*b^50 + 330040*b^49 + 222976*b^48 + 42022*b^47 + 27741*b^46 + 211697*b^45 + 180466*b^44 + 110159*b^43 + 150589*b^42 + 201801*b^41 + 298657*b^40 + 166987*b^39 + 261619*b^38 + 324182*b^37 + 330271*b^36 + 316021*b^35 + 32823*b^34 + 202060*b^33 + 101009*b^32 + 4313*b^31 + 312481*b^30 + 84293*b^29 + 111074*b^28 + 199076*b^27 + 186666*b^26 + 182304*b^25 + 13949*b^24 + 93027*b^23 + 224149*b^22 + 264084*b^21 + 300936*b^20 + 126654*b^19 + 20076*b^18 + 217563*b^17 + 293567*b^16 + 107585*b^15 + 142407*b^14 + 245*b^13 + 141130*b^12 + 161996*b^11 + 99645*b^10 + 235644*b^9 + 30653*b^8 + 142590*b^7 + 186706*b^6 + 72897*b^5 + 33019*b^4 + 284283*b^3 + 251073*b^2 + 283266*b + 291242
90651*b^127 + 48921*b^126 + 317095*b^125 + 7873*b^124 + 274789*b^123 + 160062*b^122 + 207308*b^121 + 237019*b^120 + 204263*b^119 + 267380*b^118 + 114003*b^117 + 149239*b^116 + 58126*b^115 + 55786*b^114 + 286352*b^113 + 305047*b^112 + 117630*b^111 + 266050*b^110 + 180452*b^109 + 272098*b^108 + 28949*b^107 + 197679*b^106 + 203360*b^105 + 226493*b^104 + 75252*b^103 + 265873*b^102 + 225485*b^101 + 59931*b^100 + 60212*b^99 + 289428*b^98 + 83485*b^97 + 295707*b^96 + 176312*b^95 + 4467*b^94 + 206451*b^93 + 258643*b^92 + 201874*b^91 + 281183*b^90 + 11864*b^89 + 104831*b^88 + 279072*b^87 + 6542*b^86 + 289955*b^85 + 95606*b^84 + 283515*b^83 + 37343*b^82 + 137199*b^81 + 157867*b^80 + 68322*b^79 + 264266*b^78 + 78000*b^77 + 39760*b^76 + 111509*b^75 + 2120*b^74 + 293613*b^73 + 45674*b^72 + 220453*b^71 + 119761*b^70 + 207557*b^69 + 67778*b^68 + 18979*b^67 + 204342*b^66 + 126067*b^65 + 320210*b^64 + 295529*b^63 + 330547*b^62 + 30523*b^61 + 49342*b^60 + 210441*b^59 + 293588*b^58 + 13751*b^57 + 162848*b^56 + 26422*b^55 + 216110*b^54 + 20437*b^53 + 329478*b^52 + 191422*b^51 + 127252*b^50 + 330040*b^49 + 222976*b^48 + 42022*b^47 + 27741*b^46 + 211697*b^45 + 180466*b^44 + 110159*b^43 + 150589*b^42 + 201801*b^41 + 298657*b^40 + 166987*b^39 + 261619*b^38 + 324182*b^37 + 330271*b^36 + 316021*b^35 + 32823*b^34 + 202060*b^33 + 101009*b^32 + 4313*b^31 + 312481*b^30 + 84293*b^29 + 111074*b^28 + 199076*b^27 + 186666*b^26 + 182304*b^25 + 13949*b^24 + 93027*b^23 + 224149*b^22 + 264084*b^21 + 300936*b^20 + 126654*b^19 + 20076*b^18 + 217563*b^17 + 293567*b^16 + 107585*b^15 + 142407*b^14 + 245*b^13 + 141130*b^12 + 161996*b^11 + 99645*b^10 + 235644*b^9 + 30653*b^8 + 142590*b^7 + 186706*b^6 + 72897*b^5 + 33019*b^4 + 284283*b^3 + 251073*b^2 + 283266*b + 291242

输出值相等,符合我们的预期,接下来就是转成矩阵形式:

1
2
3
4
C = matrix([(core**i).list() for i in range(n+1)])
print(phi(f).list())
f = vector(GF(q), f.list())
print(f*C)

输出值依然相等,因此我们已经找到了同态正确的矩阵表示方法,此外,由于core是G在k2中的根,因此我们还有:

验证一下:

1
2
3
C = matrix([(core**i).list() for i in range(n+1)])
g = vector(GF(q), G.list())
print(g*C)

输出为:

1
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

也符合我们的预期。

正交格

此时问题转化为,已知以下关系式:

我们知道的信息有:

  • $\textbf{as}$的值
  • $\textbf{a}$和$\textbf{g}$都比较小,尤其是$\textbf{g}$仅由1、0、-1组成,小中小

因此似乎是个HSSP类型的正交格问题。

然而试了好一会儿,发现核的方向似乎不太对,而且格的维数略大,所以最后也没有搞定这个思路。

偷鸡x2

然而,在上面的分析中可以知道,由于我们有k2的不可约多项式$F$,那么一旦我们有了k1的不可约多项式$G$,我们自然就有了矩阵$C$,那么通过解下面的矩阵方程,我们就可以得到$\textbf{a}$来:

而$\textbf{a}$的系数是不超过beta的,因此就可以做出判断了。

为什么可以得到$G$呢?注意到他的生成过程为:

1
2
3
4
5
6
def generate_sparse_irreducible_polynomial(R, n): 
x = R.gen()
while True:
g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
if (x**n + g + 1).is_irreducible():
return x**n + g + 1

可以发现,除了最后必须会有的x^128以外,剩下的最高次数是由randint(1, n//2 + 1)决定的!而这显然有一定机会赌到较小的度,比如10以内。

而且在一次完整的交互过程中,$G$是不会变的,那么我们可以将所有度在10以内的不可约多项式$G$提前算好,然后在连接上靶机得到$F$之后,计算出所有对应的$C$。那么如果当前的$G$正好度在10以内,我们就可以成功解矩阵方程做出decision。由于有66s的timeout,所以$G$少取一些,减少$C$的计算量。

接下来就是拼脸而已,实际上我跑了几次就跑出来了。

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
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
from sage.all import *
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from base64 import *
from pwn import *
import itertools, tqdm


def qary_trans_to_int(x, q):
return sum([int(x[i]) * q**i for i in range(len(x))])

def int_trans_to_qary_trans(x, q):
arr = []
while(x):
arr.append(x % q)
x //= q
return arr

def encode(f, q):
try:
return b64encode(long_to_bytes(qary_trans_to_int(f.polynomial().coefficients(sparse = False), q)))
except:
return b64encode(long_to_bytes(qary_trans_to_int(f.coefficients(sparse = False), q)))

def generate_irreducible_polynomial(R, n):
while True:
f = R.random_element(degree=n)
while f.degree() != n:
f = R.random_element(degree=n)
if f.is_irreducible():
return f

def generate_sparse_irreducible_polynomial(R, n):
x = R.gen()
while True:
g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
if (x**n + g + 1).is_irreducible():
return x**n + g + 1


q = 333337
n = 128
beta = 333
chance = 111
polyns = beta//chance
bound = 106
R, (x, ) = PolynomialRing(GF(q), 'x').objgens()

try:
Gs = #预计算过的列表
Gs = Gs[:100]
except:
Gs = list()
for l in range(10):
for g in tqdm.tqdm(itertools.product([-1, 0, 1], repeat=l+1)):
g = sum(g[i]*x**i for i in range(l+1))
g = x**n + g + 1
if g.is_irreducible():
Gs.append(g)
print(f"{Gs = }")

while True:
sh = remote("47.94.151.65", 32787)
sh.recvuntil(b"F:")
res = sh.recvline().strip().decode()
F = int_trans_to_qary_trans(bytes_to_long(b64decode(res)), q)
assert encode(R(F), q) == res.encode()
F = R(F)
k2, (b, ) = GF(q**n, name = 'b', modulus = F).objgens()

Cs = list()
for G in tqdm.tqdm(Gs):
k1, (a, ) = GF(q**n, name = 'a', modulus = G).objgens()
phi = FiniteFieldHomomorphism_generic(Hom(k1, k2))
core = phi(a)
C = matrix(GF(q), [(core**i).list() for i in range(n)])
Cs.append(C)

def decision(As, C):
As = matrix(GF(q), [A.list() for A in As])
try:
fs = C.solve_left(As)
cnt = sum([f.list().count(0) for f in fs])
return int(cnt > 20)
except:
return 0

nowC = None
cnt = 0
for i in tqdm.trange(111):
As = []
sh.recvuntil(b"As[0]: ")
As.append(R(int_trans_to_qary_trans(bytes_to_long(b64decode(sh.recvline().strip().decode())), q)))
sh.recvuntil(b"As[1]: ")
As.append(R(int_trans_to_qary_trans(bytes_to_long(b64decode(sh.recvline().strip().decode())), q)))
sh.recvuntil(b"As[2]: ")
As.append(R(int_trans_to_qary_trans(bytes_to_long(b64decode(sh.recvline().strip().decode())), q)))

###################################################################### Decision here
opt = 0
if nowC:
opt = decision(As, nowC)
else:
for C in Cs:
opt = decision(As, C)
if opt:
nowC = C
break

###################################################################### Decision here
sh.recvuntil(b"Guess the option[0/1]: ")
sh.sendline(str(opt).encode())
res = sh.recvline()
# print(opt, res)
if b'Wrong' in res:
cnt += 1
if cnt > 5:
sh.close()
print("not this time")
break
else:
print(sh.recvline())
print(sh.recvline())
sh.interactive()


#flag{ju5t_4_d3c1si0n4l_ff1_g4m3}

偷鸡x3

刚刚那个方法至少需要理解同态的矩阵表示,然而,仔细想想,既然已经有了$G$,真的需要这样绕一圈解矩阵方程吗?实际上这样就可以了XD:

1
2
3
4
5
6
7
8
9
k1 = GF(q**n, name = 'a', modulus = G)
k2 = GF(q**n, name = 'b', modulus = F)
phi = FiniteFieldHomomorphism_generic(Hom(k1, k2))
phi1 = phi^(-1)

A = random_polynomial(k1,n,beta)
phiA = phi(A)
A_ = phi1(phiA)
assert A == A_

域中元素的迹

看了下春哥他们的wp,发现说用元素的迹可以做出区分,就像下面这样:

1
2
3
4
As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)] 
print([min(i.trace(), q-i.trace()) for i in As])
As = [k2.random_element() for i in range(polyns)]
print([min(i.trace(), q-i.trace()) for i in As])
1
2
[2688, 1280, 7424]
[119765, 87415, 89479]

可以看出opt为1的时候,元素的迹与q会很接近(因为元素的迹有正有负,这相当于说元素的迹比较小),因此可以区分出来。

并不是每组都这么明显,比如下面这组:

1
2
[24320, 40832, 10624]
[11763, 5615, 6528]

所以每次给出三组数据是降低错误率,并且有五次容错

那么这就引出两个问题:

  • 什么是域中元素的迹?
  • 为什么opt为1的时候,元素的迹会比较小?
概念

因为我完全不知道域中元素的迹是什么,因此还是得先搜索一下,发现可以参考下面这篇:

有限域的结构(3): 迹, 范数与基 - 知乎 (zhihu.com)

直截了当的,文中给出了这样的定义:

image-20241104104555030

测试一下发现的确是这样,而且最终trace的值会落在基域$F_q$内:

1
2
3
a = random_polynomial(k1,n,beta)
print(sum([a^(q^i) for i in range(128)]))
print(a.trace())
1
2
1690
1690

接着往下看,可以看见一个等价定义:

image-20241104105258770

也就是说一个元素的迹实际上是他的极小多项式的所有根的和,而把极小多项式按照全部根做因式分解后对比系数可以发现,迹其实就是极小多项式的次高项系数的负数值。

依然测试一下:

1
2
3
a = random_polynomial(k1,n,beta)
g = a.minimal_polynomial()
print(-g.coefficients()[-2] % q == a.trace())
1
True

结果是正确的。

推论1

有了上面的基础理论,现在回顾题目。

显然,对于opt=0的情况,三个元素都是k2中随机的,迹自然也不会有什么特殊性质,因此我们主要关注opt=1。由于迹仅跟元素的极小多项式有关,因此我们要关注元素的极小多项式。

我们记没有经过同态的当前元素为$\alpha$,极小多项式的意义在于,由他生成的主理想可以得到所有系数来自基域$F_p$的以$\alpha$为根的多项式,自然有:

那么同态之后就有:

可以推得,对于$\forall f \in J,J = (g(x))$,有:

这说明$g(x)$生成的主理想也能得到所有以$\phi(\alpha)$为根的多项式,因此同态前后极小多项式是相等的,测试一下:

1
2
a = random_polynomial(k1,n,beta)
print(phi(a).minimal_polynomial() == a.minimal_polynomial())
1
True

的确符合预期。

抽代说实话有点忘了,不严谨甚至错误的地方欢迎指出

这说明什么呢?由于极小多项式一样,而迹只和极小多项式有关,那么对于这个题目来说就得到了一个重要结论:同态前后元素的迹是相等的

推论2

因此现在我们只需要关注同态前元素的迹有什么性质,我们知道同态前的元素$\alpha$满足:

  • 本身系数比较小
  • 所在扩域的模多项式系数也比较小

然而我的确没想明白为什么满足这两个条件,$\alpha$的迹就会也显得比较小,不过不管是脑子里冥冥之中的直觉还是实际测试出来都的确是这样。因此我们不妨脸皮厚一点,认为我们得到了第二个结论:random_polynomial(k1,n,beta)生成的元素$\alpha$的迹比较小。

所以结合上述两个推论就可以用迹的大小来对元素究竟是opt为1还是opt为0做出判断。



ECRandom_game

题目描述:

1
easy密码游戏

题目:

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
from flag import M, q, a, b, select
import hashlib
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
import sys
import ecdsa
from Crypto.Util.Padding import pad, unpad
from ecdsa.ellipticcurve import CurveFp,Point
from math import ceil
import os
import random
import string

flag = b'qwb{kLeMjJw_HBPtoHsVhnnxZdvtGjomivNDUI_vMRhZHrfKlCZ6HlGAeXRV_gQ8i117nGhzEMr0Zk_YTl1wftSskpX4JLnryE9Mhl96cPTWorGCl_R6nD33bcx1AYflag_leak}'
assert len(flag) == 136

BANNER = '''
GGGGG OOOOO DDDDD DDDDD GGGGG AAA MM MM EEEEEEE
GG OO OO DD D DD D GG AAAAA MMM MMM EE
GG GGG OO OO DD D DD D GG GGG A A MM MM MM EEEEE
GG GG OO OO DD D DD D GG GG AAAAA MM MM EE
GGGGGGG OOOOO DDDDD DDDDD GGGGGGG A A MM MM EEEEEEE
'''

NNN = []
def die(*args):
pr(*args)
quit()

def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()

def sc():
return sys.stdin.buffer.readline()

def Rng(k):
ran = random.getrandbits(k)
NNN.append(ran)
return ran


def ADD(num):
NUM = 0
for i in range(num):
NUM += Rng(32)
return NUM

def secure_choice(sequence):
if not sequence:
return None
randbelow = 0
for i, x in enumerate(sequence):
randbelow += 1
if os.urandom(1)[0] < (1 << 8) * randbelow // len(sequence):
return x

def xDBLADD(P, Q, PQ, q, a, b):
(X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
return (X4, Z4), (X5, Z5)

def xMUL(P, k, q, a, b):
Q, R = (1, 0), P
for i in reversed(range(k.bit_length() + 1)):
if k >> i & 1:
R, Q = Q, R
Q, R = xDBLADD(Q, R, P, q, a, b)
if k >> i & 1:
R, Q = Q, R
return Q

def shout(x, d, q, a, b):
P = (x,1)
Q = xMUL(P, d, q, a, b)
return Q[0] * pow(Q[1], -1, q) % q

def generate_random_string(length):
characters = string.ascii_letters + string.digits
random_string = ''.join(secure_choice(characters) for i in range(length))
return random_string

class ECCDu():
def __init__(self,curve,G):
self.state = getRandomNBitInteger(512)
self.Curve = curve
self.g = G

self.num = Rng(32)
d = 65537
self.Q = self.num*self.g
self.P = d * self.Q

def ingetkey(self):
t = int((self.state * self.Q).x())
self.updade()
return t%(2**250)

def updade(self):
self.state = int((self.state * self.P).x())

def Random_key(self, n:int):
out = 0
number = ceil(n/250)
for i in range(number):
out = (out<<250) + self.ingetkey()
return out % (2**n)

def proof_of_work():
random.seed(os.urandom(8))
proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
_hexdigest = sha256(proof.encode()).hexdigest()
pr(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
pr('Give me XXXX: ')
x = sc().rstrip(b'\n')
if len(x) != 4 or sha256(x + proof[4:].encode()).hexdigest() != _hexdigest:
return False
return True

def main():
pr(BANNER)
pr('WELCOME TO THIS SIMPLE GAME!!!')
ASSERT = proof_of_work()
if not ASSERT:
die("Not right proof of work")

pr('Now we will start our formal GAME!!!')
pr('===== First 1💪: =====')
pr('Enter an integer as the parameter p for Curve: y^2 = x^3+12x+17 (mod p) and 250<p.bit_length()')
p1 = int(sc())
if not 250<=p1.bit_length():
die('Wrong length!')
curve = CurveFp(p1, 12, 17,1)
pr(curve)
pr('Please Enter a random_point G:')
G_t = sc().split(b' ')
Gx,Gy = int(G_t[0]),int(G_t[1])
if not curve.contains_point(Gx,Gy):
die('This point is outside the curve')
G = Point(curve,Gx,Gy)

for i in range(500):
ECDU = ECCDu(curve,G)
m = 'My secret is a random saying of phrase,As below :' + generate_random_string(119)
Number = ECDU.Random_key(1344)
c = Number^bytes_to_long(m.encode())
pr(f'c = {c}')
pr(f'P = {int(ECDU.P.x()), int(ECDU.P.y())}')
pr(f'Q = {int(ECDU.Q.x()), int(ECDU.Q.y())}')

pr('Enter m:')
m_en = sc().rstrip(b'\n')
if m_en != m.encode():
die('This is not the right m,Please try again')
else:
pr('Right m!!!')
pr('Bingo!')
new_state,new_state1 = ADD(136),ADD(50)

random.seed(new_state)

pr('===== Second 2💪: =====')
curve1 = CurveFp(q,a,b,1)
pr(f'{int(curve1.p()),int(curve1.a()),int(curve1.b())}')

pr("Enter a number that does not exceed 1500")
number = int(sc())

pr(f'You only have {number} chances to try')
success = 0
for i in range(number):
Gx = secure_choice(select)
R = Rng(25)
pr('Gx = ',Gx)
pr('Px = ',shout(Gx, R, q, a, b))
R_n = int(sc().rstrip(b'\n'))
if R_n != R:
pr(f'Wrong number!!!,Here is your right number {R}')
else:
pr('GGood!')
success += 1

if int(success)/int(number) <= 0.262:
die('Please Try more...')

random.seed(new_state)
iv_num = ADD(2000)

iv = hashlib.sha256(str(iv_num).encode()).digest()[:16]
key = hashlib.sha256(str(new_state1).encode()).digest()[:16]
Aes = AES.new(key,AES.MODE_CBC, iv)
C = Aes.encrypt(pad(flag,16))

key_n, iv_n = int(sc()), int(sc())
iv1 = hashlib.sha256(str(iv_n).encode()).digest()[:16]
key1 = hashlib.sha256(str(key_n).encode()).digest()[:16]
Aes_verify = AES.new(key1,AES.MODE_CBC, iv1)
C_verify = unpad(Aes_verify.decrypt(C),16)

if C_verify == flag:
pr('Congratulations🎇🎇🎇!!!!')
pr('Here is your flag😊:', M)
else:
pr('Maybe you could get the right flag!')

if __name__ == '__main__':
main()

这个题表面上是ECC,实际上是MT19937的大满套。

part1

第一部分基于一个Dual EC的伪随机数生成器,其原理可以参考:

密码学后门系列Ⅰ: Dual EC | tl2cents blog (tanglee.top)

总之,我们既然有他的后门d,而且每次msg固定了高位,因此可以获得stage从而往后预测随机数,所以通过500次不是问题。

而这五百次中,每一次都会涉及一个MT19937的随机数ki,他是getrandbits(32)生成的,我们需要求出他来进行后续的随机数预测,具体来说它满足:

而他们所在的曲线的素数p是我们提供的,因此爆破一下p,找一个光滑小因子乘积超过32bit的曲线就可以快速求解dlp得到ki了。

在通过这五百轮之后他会生成:

1
new_state,new_state1 = ADD(136),ADD(50)

这里ADD的意思就是接下来136个getrandbits(32)和50个getrandbits(32)的求和结果。

我们只有500个随机数,做不到准确预测后续所有的随机数,然而由于MT的twist只和三个状态有关,也就是:

因此我们虽然预测不了newstate,但是预测newstate1是完全没有问题的,因为所有与他有关的位置都在前500个已知的随机数中。而且做法更加简单,只需要往predictor里塞了前500个正确数据之后,再塞124个垃圾数据凑够624个,之后进行预测就行了。

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
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
from Crypto.Util.number import *
from pwn import *

####################################################################################################### part1 Dual EC
def proof(sh):
import string, tqdm, hashlib, itertools

sh.recvuntil(b'sha256(XXXX+')
suffix = sh.recv(16)
sh.recvuntil(b') == ')
pre = sh.recvline().strip().decode()[:-1]
for prefix in tqdm.tqdm(itertools.product(string.ascii_letters + string.digits, repeat=4)):
prefix = ''.join(prefix).encode()
if hashlib.sha256(prefix+suffix).hexdigest() == pre:
sh.sendlineafter(b'Give me XXXX: ', prefix)
break
return

def func1():
global out1
def part1(P, Q, c):
d = 65537
known = b'My secret is a random saying of phrase,As below :' + b'\x00'*119
m = bytes_to_long(known) ^^ c
prefix = bytes_to_long(long_to_bytes(m, len(known))[:len(known)-119])<<(119*8)
number = ceil(1344/250)
outs = [(prefix>>(i*250)) % 2**250 for i in range(number)][::-1]
# ls0, s1, hs2, ...
t1 = outs[1]
ht2 = outs[2]
for k in range(2**10):
s1 = ZZ(t1 + k*2**250)
try:
sQ = E.lift_x(s1)
s2 = int((d*sQ).xy()[0])
t2 = int((s2*Q).xy()[0]) % 2**250
if ((t2|ht2) == t2) and ((t2&ht2) == ht2):
break
except Exception as e:
continue
else:
raise Exception("not this time")
state = s2
outs = outs[:2]
for i in range(number-2):
t = int((state*Q).xy()[0])
state = int((state*P).xy()[0])
outs.append(t % 2**250)
out = 0
for t in outs:
out = (out<<250) + (t)
m = long_to_bytes(out ^^ c)
return m

p = 76837912973221323002483668912067151296065917149894557283725838853584131795679
E = EllipticCurve(GF(p), [12, 17])
n = 76837912973221323002483668912067151296162675561982794479768589266782793320165
Gx, Gy = (50815842720719088866452690975886010078415234799217383820996108469852859980668, 21844377630643101592426006459110255155148432904632255524120741447151662349886)
rrr = 3689513 * 6432902579 * 999652676767686311 * 815669308181510359025276279
G = E(Gx, Gy)

from tqdm import trange
sh.sendlineafter(b'Enter an integer as the parameter p for Curve: y^2 = x^3+12x+17 (mod p) and 250<p.bit_length()', str(p).encode())
sh.sendlineafter(b'Please Enter a random_point G:', f"{Gx} {Gy}".encode())
for _ in trange(500):
sh.recvuntil(b'c = ')
c = int(sh.recvline())
sh.recvuntil(b'P = ')
P = E(eval(sh.recvline()))
sh.recvuntil(b'Q = ')
Q = E(eval(sh.recvline()))
m = part1(P, Q, c)
out1.append(int((rrr*Q).log(rrr*G)))
sh.sendlineafter(b'Enter m:\n', m)
return

sh = remote(*"47.93.99.173 26698".split())
proof(sh)
out1 = []
func1()

part2

第二部分开始时,会先用new_state设置随机数种子,而第三部分会同样设置这个随机数种子去生成所需数据,因此我们接下来的任务就是求出这个设置了种子后的state。

而这一部分基于一个看上去很奇怪的曲线,每一次我们需要在这个曲线上解决25bit的ECDLP问题,从而拿到足够的随机数去恢复输出state。而这个曲线点加和倍乘操作是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def xDBLADD(P, Q, PQ, q, a, b):
(X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
return (X4, Z4), (X5, Z5)

def xMUL(P, k, q, a, b):
Q, R = (1, 0), P
for i in reversed(range(k.bit_length() + 1)):
if k >> i & 1:
R, Q = Q, R
Q, R = xDBLADD(Q, R, P, q, a, b)
if k >> i & 1:
R, Q = Q, R
return Q

def shout(x, d, q, a, b):
P = (x,1)
Q = xMUL(P, d, q, a, b)
return Q[0] * pow(Q[1], -1, q) % q

这个部分看了让人害怕,但实际上测试下会发下,这实际上就是很普通的椭圆曲线而已:

而shout的操作实际上就是对横坐标为x的点乘d倍,并返回这个倍点横坐标而已,所以这个ECDLP部分实际是很简单的。

再细看一下会发现他似乎根本没检查请求次数是不是真的小于1500,所以不用ECDLP会显著加快速度,直接要足够的数据之后(比如1300组),再往后预测直到超过0.262的成功率就可以了。

所以这一部分实际上是一个已知多个连续的getrandbits(25),怎么向后预测随机数,并推理初始state的问题。这个实际上可以用建矩阵的方法来解,但是正好试用一下maple的新板子,发现速度会快上很多:

maple3142/gf2bv: Solving linear systems over GF(2) by manipulating bitvectors (github.com)

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
46
47
48
49
50
51
52
53
54
#sh.recvuntil(b': =====')
#print(sh.recvline())
#print(sh.recvline())
#print(sh.recvline())

####################################################################################################### part2 MT 25
import random
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import *

def mt19937(bs, out):
lin = LinearSystem([32] * 624)
mt = lin.gens()

rng = MT19937(mt)
zeros = [rng.getrandbits(bs) ^^ int(o) for o in out] + [mt[0] ^^ int(0x80000000)]
sol = lin.solve_one(zeros)

rng = MT19937(sol)
pyrand = rng.to_python_random()
return pyrand

################################################################################## test
if(0):
nums = 1300
random.seed(int(3142))
out = [random.getrandbits(25) for i in range(nums)]
RNG = mt19937(25, out)
STATE = RNG.getstate()[1][:-1]
temp = [RNG.getrandbits(25) for i in range(nums)] #iter

for i in range(1000):
assert RNG.getrandbits(25) == random.getrandbits(25)

################################################################################## use
if(1):
sh.recvuntil(b"Enter a number that does not exceed 1500")
nums = 1300
sh.sendline(b"2000")
print(sh.recvline())

out2 = []
for i in trange(nums):
sh.sendline(b"1")
sh.recvuntil(b"Wrong number!!!,Here is your right number ")
out2.append(int(sh.recvline().strip().decode()))
RNG = mt19937(25, out2)
temp = [RNG.getrandbits(25) for i in range(nums)] #iter
for i in trange(2000-nums):
sh.sendline(str(RNG.getrandbits(25)).encode())
sh.recvuntil(b'GGood!')

RNG1 = mt19937(25, out2)

part3

有了state和state1之后,这一部分就是纯粹把预测的随机数回传给靶机。

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
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from mt19937predictor import MT19937Predictor

flag = b'qwb{kLeMjJw_HBPtoHsVhnnxZdvtGjomivNDUI_vMRhZHrfKlCZ6HlGAeXRV_gQ8i117nGhzEMr0Zk_YTl1wftSskpX4JLnryE9Mhl96cPTWorGCl_R6nD33bcx1AYflag_leak}'

iv_num = 0
for i in range(2000):
iv_num += RNG1.getrandbits(32)


predictor1 = MT19937Predictor()
for i in range(500):
predictor1.setrandbits(out1[i], 32)
for i in range(124):
predictor1.setrandbits(0, 32)
for i in range(136-124):
predictor1.getrandbits(32)

key = 0
for i in range(50):
key += predictor1.getrandbits(32)

print(key)
print(iv_num)
sh.sendline(str(key).encode())
sh.sendline(str(iv_num).encode())

print(sh.recvline())
print(sh.recvline())
print(sh.recvline())


#qwb{hdasdh_sdah_sdadhd_vnvm_2323rerwegfds}



homomor_game

题目描述:

1
It seems that you enjoy this homomorphic game…Don’t you?

题目:

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
144
145
146
147
148
149
150
151
152
153
154
155
import tenseal.sealapi as sealapi
from random import randint
import base64

g = 5
poly_modulus_degree = 8192
plain_modulus = 163841

def gen_keys():
parms = sealapi.EncryptionParameters(sealapi.SCHEME_TYPE.BFV)
parms.set_poly_modulus_degree(poly_modulus_degree)
parms.set_plain_modulus(plain_modulus)
coeff = sealapi.CoeffModulus.BFVDefault(poly_modulus_degree, sealapi.SEC_LEVEL_TYPE.TC128)
parms.set_coeff_modulus(coeff)

ctx = sealapi.SEALContext(parms, True, sealapi.SEC_LEVEL_TYPE.TC128)

keygen = sealapi.KeyGenerator(ctx)
public_key = sealapi.PublicKey()
keygen.create_public_key(public_key)
secret_key = keygen.secret_key()

parms.save("app/parms")
public_key.save("app/public_key")
secret_key.save("app/secret_key")

def load():
parms = sealapi.EncryptionParameters(sealapi.SCHEME_TYPE.BFV)
parms.load("app/parms")

ctx = sealapi.SEALContext(parms, True, sealapi.SEC_LEVEL_TYPE.TC128)

public_key = sealapi.PublicKey()
public_key.load(ctx, "app/public_key")

secret_key = sealapi.SecretKey()
secret_key.load(ctx, "app/secret_key")
return ctx, public_key, secret_key

def gen_galois_keys(ctx, secret_key, elt):
keygen = sealapi.KeyGenerator(ctx, secret_key)
galois_keys = sealapi.GaloisKeys()
keygen.create_galois_keys(elt, galois_keys)
galois_keys.save("app/galois_key")
return galois_keys

def gen_polynomial(a):
return '1x^' + str(a)

def f(a, b):
return (pow(g, a-b, plain_modulus) + pow(g, b-a, plain_modulus) + pow(g, 3*a-b, plain_modulus) + pow(g, a-3*b, plain_modulus))%plain_modulus

def check_result(ctx, decryptor, a, b, pos):
plaintext = sealapi.Plaintext()
ciphertext = sealapi.Ciphertext(ctx)
ciphertext.load(ctx, "app/computation")
decryptor.decrypt(ciphertext, plaintext)
print(plaintext[pos])
print(f(a,b))
print("Done!")
assert plaintext[pos] == f(a, b)

def send(filepath):
f = open(filepath, "rb")
data = base64.b64encode(f.read()).decode()
f.close()
print(data)

def recv(filepath):
try:
data = base64.b64decode(input())
except:
print("Invalid Base64!")
exit(0)

f = open(filepath, "wb")
f.write(data)
f.close()

def main():
ctx, public_key, secret_key = load()
encryptor = sealapi.Encryptor(ctx, public_key)
decryptor = sealapi.Decryptor(ctx, secret_key)

a, b = [randint(1, poly_modulus_degree - 1) for _ in range(2)]
poly_a, poly_b = gen_polynomial(a), gen_polynomial(b)

plaintext_a, plaintext_b = sealapi.Plaintext(poly_a), sealapi.Plaintext(poly_b)
ciphertext_a, ciphertext_b = [sealapi.Ciphertext() for _ in range(2)]
encryptor.encrypt(plaintext_a, ciphertext_a)
encryptor.encrypt(plaintext_b, ciphertext_b)
ciphertext_a.save("app/ciphertext_a")
ciphertext_b.save("app/ciphertext_b")
galois_used = 0

while True:
try:
choice = int(input("Give Me Your Choice:"))
except:
print("Invalid choice!")
exit(0)

if choice == 0:
print("Here Is Ciphertext_a:")
send("app/ciphertext_a")
print("Here Is Ciphertext_b:")
send("app/ciphertext_b")

elif choice == 1:
if galois_used == 1:
print("No More!")
exit(0)
try:
elt = int(input("Please give me your choice:"))
except:
print("Invalid input!")
exit(0)

try:
galois_key = gen_galois_keys(ctx, secret_key, [elt])
except:
print("Invalid galois!")
exit(0)

print("Here is your galois key:")
send("app/galois_key")
galois_used = 1

elif choice == 2:
try:
pos = int(input("Give Me Your Position:"))
assert pos in range(poly_modulus_degree)
except:
print("Invalid position!")
exit(0)

print("Give Me Your Computation")
recv("app/computation")

try:
check_result(ctx, decryptor, a, b, pos)
except:
print("Incorret Answer!")
exit(0)

flag = open("app/flag", "rb")
print(flag.read())
flag.close()

else:
print("Invalid choice!")
break

# gen_keys()
main()

预备知识

要完成这个题目首先需要了解点bfv,这里可以参考:

FHE全同态加密算法学习-BFV | tl2cents blog (tanglee.top)

R3CTF 2024 Crypto Writeup - Tanglee’s Blog

核心在于运算的同态性,把bfv的加密解密分别看作是一个map:

最基本的,那么对于同态加$\oplus$和同态乘$\otimes$有:

对于本题还需要用的高斯自同构运算$\theta$,它也具有:

所有运算都在一个商环下完成,对于本题来说商环是:

其中$q = 163841, n = 8192$。

具体的同态运算细节可以参考上述博客

题目内容

在有一个大概了解的基础上,来看一看题目需要完成些什么。

  • 首先,题目预生成了一组公私钥,并且把公钥发放给了我们

  • 连接靶机后,靶机会生成两个随机的明文多项式$x^a , x^b$,并将这两个多项式用bfv加密,得到对应密文$C_a,C_b$

  • 之后进入不限次数但限时300s的交互,有如下几种选项:

    • 输入0,可以获得$C_a,C_b$

    • 输入1,可以指定一个galois key,并且整个交互中只能指定一次

      galois key的作用是对多项式计算高斯自同构,如果galois key为i,那么可以用它计算:

    • 输入2,可以发送一系列同态计算,靶机会应用我们的同态计算并解密得到明文多项式,如果我们能够使该明文多项式的一个确定位置的系数为:

      就可以获得flag

由于bfv具有同态性,因此我们的任务实际可以看作是通过同态加、同态乘、高斯自同构等同态运算,将$x^a,x^b$这两个多项式组合出一个含有如下单项的多项式:

并且我们需要知道i才行,这个过程里a、b都是未知的。

同态运算

这一部分主要展示下用每种同态运算能构造些什么出来。

具体调用方式可以参考:

微软同态加密库SEAL算子功能汇总_微软seal 基于什么协议-CSDN博客

我们有$x^a,x^b$的密文$C_a,C_b$,用三种运算分别可以构造出能解密出如下明文的密文:

  • 同态加:

    这里还包含了数乘

  • 同态乘:

    并且两个密文也可以相乘,所以总的来说一般结构是:

    这里在实际操作的时候会发现,由于同态乘会将二元组的密文扩展为三元组的密文,在这之后要进行高斯自同构的话,需要重线性化回二元组的密文才行。但是这需要一个重线性化的密钥,而题目没有给出,所以在同态乘之后就不能用高斯自同构了,只能在同态乘之前用

  • 高斯自同构:

解题

回顾题目,我们的任务是通过同态加、同态乘、高斯自同构等同态运算,将$x^a,x^b$这两个多项式组合出一个含有如下单项的多项式:

但是最大的问题在于我们根本没有a和b的具体值,所以我怎么都想不出来如何构造出这种形式。

最后请教了@peigong才明白,我们可以从构造如下的一个和式多项式入手:

如果把这个明文多项式与$C_a$做同态乘,那么解密会得到:

那么其中含有单项:

而由于在环$R_q$下有:

所以$p(x)$的常数项就是:

再取一个负号,我们就成功的在明文多项式的常数项构造了一个$g^a$。

而我们的目的是构造出$g^{a-b}$,这只需要我们构造出一个能解密出$x^{a-b}$这一单项的密文,然后与上面的和式$f(x)$相乘即可。

为此我们需要利用galois key,由于在$R_q$下有:

所以也有:

那么将i取为n-1,我们就可以实现指数上的取负操作。

此时要注意系数也同时取了个负,要取回来才行

此时我们就可以按如下步骤获取一个解密后常数项为$g^{a-b}$的密文:

  • 对$C_b$应用$\theta_{n-1}$,此时解密得到$-x^{-b}$
  • 对该密文取负,此时解密得到$x^{-b}$
  • 与$C_a$进行同态乘,此时解密得到$x^{a-b}$
  • 构造和式$f(x) = \sum_{i=0}^{n-1}g^ix^{n-i}$
  • 将密文与$f(x)$相乘,此时常数项是$-g^{a-b}$
  • 取负,解密后常数项就是$g^{a-b}$

既然能构造出这样的$g^{a-b}$,那么如法炮制也就可以得到$g^{b-a} , g^{3a-b} , g^{a-3b}$这几个常数项,之后同态加起来解密就能得到我们需要的常数项$g^{a-b} + g^{b-a} + g^{3a-b} + g^{a-3b}$,从而拿到flag了。

事实上同态运算有时候密文系数的正负号还是会反,这是因为galois key对$x^b$来说是这样应用的:

所以实际上系数需不需要取反取决于b的奇偶性,而这个我们并不知道,我的处理方法就反复多连几次靶机就行了。

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
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
import tenseal.sealapi as sealapi
import base64
from pwn import *

context.log_level = "critical"

############################################################################################ prepare data and tools
g = 5
n = 8192
p = 163841

def load():
parms = sealapi.EncryptionParameters(sealapi.SCHEME_TYPE.BFV)
parms.load("app/parms")

ctx = sealapi.SEALContext(parms, True, sealapi.SEC_LEVEL_TYPE.TC128)

public_key = sealapi.PublicKey()
public_key.load(ctx, "app/public_key")

return ctx, public_key

def gen_polynomial(a):
poly = hex(a[0])[2:]
for i in range(1, len(a)):
poly = hex(a[i])[2:] + 'x^' + str(i) + ' + ' + poly
return poly

ctx, public_key = load()
encryptor = sealapi.Encryptor(ctx, public_key)


for i in range(20):
############################################################################################ ciphera, cipherb
sh = remote("node6.anna.nssctf.cn", 24711)
sh.recvuntil(b"Give Me Your Choice:")
sh.sendline(b"0")
sh.recvuntil(b"Here Is Ciphertext_a:")
sh.recvline()
ciphertexta = base64.b64decode(sh.recvline().strip())
f = open("app/ciphertext_a", "wb")
f.write(ciphertexta)
f.close()
sh.recvuntil(b"Here Is Ciphertext_b:")
sh.recvline()
ciphertextb = base64.b64decode(sh.recvline().strip())
f = open("app/ciphertext_b", "wb")
f.write(ciphertextb)
f.close()
ciphertext_a = sealapi.Ciphertext(ctx)
ciphertext_a.load(ctx, "app/ciphertext_a")
ciphertext_b = sealapi.Ciphertext(ctx)
ciphertext_b.load(ctx, "app/ciphertext_b")


############################################################################################ galois key
sh.recvuntil(b"Give Me Your Choice:")
sh.sendline(b"1")
elt = n-1
sh.sendline(str(elt).encode())
sh.recvuntil(b"Here is your galois key:")
sh.recvline()
galoiskey = base64.b64decode(sh.recvline().strip())
f = open("app/galois_key", "wb")
f.write(galoiskey)
f.close()
galois_keys = sealapi.GaloisKeys()
galois_keys.load(ctx, "app/galois_key")


############################################################################################ calculate
evaluator = sealapi.Evaluator(ctx)
ciphertext = sealapi.Ciphertext(ctx)
if(0): #samples
evaluator.sub_inplace(ciphertext, ciphertext_b)
evaluator.multiply_plain_inplace(ciphertext, sealapi.Plaintext(hex(5)[2:]))
evaluator.apply_galois_inplace(ciphertext, elt, galois_keys)
evaluator.multiply_inplace(ciphertext, ciphertext_a)

Y1,Y2,Y3,Y4 = 1,1,1,1
############################ g^(a-b)
if(Y1):
ciphertext11 = sealapi.Ciphertext(ctx)
ciphertext12 = sealapi.Ciphertext(ctx)
evaluator.add_inplace(ciphertext11, ciphertext_a)
evaluator.add_inplace(ciphertext12, ciphertext_b)
evaluator.apply_galois_inplace(ciphertext12, elt, galois_keys)
evaluator.negate_inplace(ciphertext12)
evaluator.multiply_inplace(ciphertext11, ciphertext12)
poly = sealapi.Plaintext(gen_polynomial([pow(g, n-i, p) % p for i in range(n)]))
evaluator.multiply_plain_inplace(ciphertext11, poly)
evaluator.negate_inplace(ciphertext11)
evaluator.add_inplace(ciphertext, ciphertext11)

############################ g^(b-a)
if(Y2):
ciphertext11 = sealapi.Ciphertext(ctx)
ciphertext12 = sealapi.Ciphertext(ctx)
evaluator.add_inplace(ciphertext11, ciphertext_b)
evaluator.add_inplace(ciphertext12, ciphertext_a)
evaluator.apply_galois_inplace(ciphertext12, elt, galois_keys)
evaluator.negate_inplace(ciphertext12)
evaluator.multiply_inplace(ciphertext11, ciphertext12)
poly = sealapi.Plaintext(gen_polynomial([pow(g, n-i, p) % p for i in range(n)]))
evaluator.multiply_plain_inplace(ciphertext11, poly)
evaluator.negate_inplace(ciphertext11)
evaluator.add_inplace(ciphertext, ciphertext11)

############################ g^(3a-b)
if(Y3):
ciphertext11 = sealapi.Ciphertext(ctx)
ciphertext12 = sealapi.Ciphertext(ctx)
evaluator.add_inplace(ciphertext11, ciphertext_a)
evaluator.multiply_inplace(ciphertext11, ciphertext_a)
evaluator.multiply_inplace(ciphertext11, ciphertext_a)

evaluator.add_inplace(ciphertext12, ciphertext_b)
evaluator.apply_galois_inplace(ciphertext12, elt, galois_keys)
evaluator.negate_inplace(ciphertext12)

evaluator.multiply_inplace(ciphertext11, ciphertext12)
poly = sealapi.Plaintext(gen_polynomial([pow(g, n-i, p) % p for i in range(n)]))
evaluator.multiply_plain_inplace(ciphertext11, poly)
evaluator.negate_inplace(ciphertext11)
evaluator.add_inplace(ciphertext, ciphertext11)

############################ g^(a-3b)
if(Y4):
ciphertext11 = sealapi.Ciphertext(ctx)
ciphertext12 = sealapi.Ciphertext(ctx)
ciphertext13 = sealapi.Ciphertext(ctx)
evaluator.add_inplace(ciphertext11, ciphertext_a)

evaluator.add_inplace(ciphertext12, ciphertext_b)
evaluator.apply_galois_inplace(ciphertext12, elt, galois_keys)
evaluator.negate_inplace(ciphertext12)
evaluator.add_inplace(ciphertext13, ciphertext12)
evaluator.multiply_inplace(ciphertext13, ciphertext12)
evaluator.multiply_inplace(ciphertext13, ciphertext12)

evaluator.multiply_inplace(ciphertext11, ciphertext13)
poly = sealapi.Plaintext(gen_polynomial([pow(g, n-i, p) % p for i in range(n)]))
evaluator.multiply_plain_inplace(ciphertext11, poly)
evaluator.negate_inplace(ciphertext11)
evaluator.add_inplace(ciphertext, ciphertext11)



ciphertext.save("app/computation")

f = open("app/computation", "rb")
msg = base64.b64encode(f.read()).decode()
f.close()


############################################################################################ check
sh.recvuntil(b"Give Me Your Choice:")
sh.sendline(b"2")
sh.recvuntil(b"Give Me Your Position:")
sh.sendline(b"0")
sh.recvuntil(b"Give Me Your Computation")
sh.sendline(msg.encode())
sh.recvline()

res = sh.recvline().strip().decode()
if("Incorret" not in res):
print(res)
break

sh.close()


#NSSCTF{3a66ac20-ef09-4941-9c0d-35db2abb80af}