This Year’s Crypto CTF was very exciting, I got just enough time to solve 2 challenges and 2 challenges partially. Congrats for the teams that solved all the challenges. This was my first real time CTF attempt on a specific category.
Suction (Easy)
The following source code and the corresponding output is given to us
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def keygen(nbit, r):
while True:
p, q = [getPrime(nbit) for _ in '__']
e, n = getPrime(16), p * q
phi = (p - 1) * (q - 1)
if GCD(e, phi) == 1:
N = bin(n)[2:-r]
E = bin(e)[2:-r]
# print(-r)
PKEY = N + E
pkey = (n, e)
return PKEY, pkey
def encrypt(msg, pkey, r):
m = bytes_to_long(msg)
n, e = pkey
c = pow(m, e, n)
print('c:', c)
C = bin(c)[2:-r]
return C
r, nbit = 8, 128
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')
PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761
It picks two random 128 bit primes and forms our modulus then raises it to the power e, a prime of bit length 16. Usually 128 bit primes are small enough to be factored in a manageable time.
The hard part in this challenge is to find the actual N, E and C values used as the output truncates the last byte from each of the integers. This however is not a major issue and for the most part we can quickly find the actual values used. You can separate PKEY and ENC into its components with
#!/usr/bin/env python3
N_E = bin(PKEY)[2:]
_C = bin(ENC)[2:]
_E = N_E[-8:]
_N = N_E[:-8]
Then we can brute force and append all possible 3*256 values into a list to further narrow down. Firstly for N, we can check the first 2^20 or so numbers for common divisor with each of the possible N since we know both factors have a bit length of 128, this narrows it down to just nine N values, we can manually factor each of the possible ones and find an N with two 128 bit primes.
p = 188473222069998143349386719941755726311
q = 292926085409388790329114797826820624883
We can calculate $\phi$ value from these two factors, now all that’s left is to find our E to inverse. After brute forcing for E, we can further narrow it down by checking if it is a 16 bit prime. Then find $d$ such that $$de = 1 \mod \phi$$ Now we can simply brute force each of the possible 256 ciphertext values by $$ c^d \mod n$$ We can write a simple ASCII checker to filter any non ASCII bytes after converting from an integer to bytes.
FLAG: CCTF{6oRYGy&Dc$G2ZS}
Resuction (Medium)
We are given the following source code and the corresponding output
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
from decimal import *
def keygen(nbit, r):
while True:
p, q = [getPrime(nbit) for _ in '__']
d, n = getPrime(64), p * q
phi = (p - 1) * (q - 1)
if GCD(d, phi) == 1:
e = inverse(d, phi)
N = bin(n)[2:-r]
E = bin(e)[2:-r]
PKEY = N + E
pkey = (n, e)
return PKEY, pkey
def encrypt(msg, pkey, r):
m = bytes_to_long(msg)
n, e = pkey
c = pow(m, e, n)
C = bin(c)[2:-r]
return C
r, nbit = 8, 1024
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')
PKEY = 14192646310719975031517528381795548241077678859071194396837281472399230674325587198691913743313024193030641258581477544395982020385534616950314446352119543012689979705497443206671093873748633162188213109347667494028713308821945628880987033909436936504594085029207071182583896573425433818693447573712242776054326253393149643818428222532313129014785625379928796322492111783102063504659053965652092334907431265629283336869752591405010801363428649651892548988084920295512198406822149854508798413366425646089176325412867633899847841343293434518769693835679828109184625256833518392375615524221729773443578746961887429674099018040291053535429314874943299587513900900515776980848746070077651676814430155460898107362207677739452859298842563030631706907437662807884529549746843462830493900480079096937402325307522965877069080418178692616875205678928420840955518031258855869218152431304423803589723140983606576549207164114711076498723237274262054605174412193097533550076687418481230734706280737017543741247718967059747548710091320650704988384742281590019869955579949961574733610565593105027342454880292474482792325237942870408329807427182014062811782475262070063065860763705715879581562335668163076088547827008755841277828137570366416095778
enc = 93313196155732054514477836642637636744872135106456047659057794344503071105783322399713135615723000054324693644981340568454628360027598469597864407205974007198804288563284521413279406211756674451582156555173212403946908121125010635246043311803494356106191509999360722019559999844621905376368824621365540442906142224342650371557766313381899279520110833822291649001754956653102495882094754863493058001964760438040783400782352466943990226083197340594364084294954324101604417550048379969516185353765224920719355485680872367930581872987972421836853197205534334204586713387469939986387582911728909524428102693874671302382
This may look almost identical to the Suction challenge, however we are working with 1024 bit primes which are quite hard to factorize like before. The other major difference is that we are choosing a 64 bit prime for $d$ then finding it’s inverse to encrypt. There are two major attacks against choosing a small $d$ Wiener’s attack and Boneh-Durfee Although Boneh-Durfee is an extension of Wiener’s attack, Wiener’s attack is more simple to implement and our $d$ easily satisfies its requirement. The only other difficulty is brute forcing $N$ and $E$ and $C$, like before since we know the factors of $N$ has 1024 digits we can do a naive check for divisibility with small numbers to narrow down $N$, I was able to narrow it down to just 6 possible ones, then from there running over all possible $E$ and parallelizing our attack we can factor $N$.
p = 165057747190263284822060070867326404037226426769214461653453077347642660157038079939800175423376926190278742477747265143003662594094338527240051087411682630746699434893569121815945138770655880775127567084882226276395011876712312835431878615781804989285062397026979540636501309686456639319755442794081237335613
q = 174371810769321904879771281457264126835536885769795883249689917534917724369418768788724295833034211032483643000304760729751539874477879712047563093622220226046317887445404441674034749799537927102249473198079484568936482286828850749395726000380023524546597995716458255074061858150920326214596269436009922505467
Now as before after finding $d$ we can brute force $c$ by checking if any of them is ASCII after decryption.
FLAG: CCTF{aIr_pr3s5urE_d!Ff3rEn7i4L_8eTw3eN_ArEa5!}
The following are my attempts to solve challenges that I was only able to do partially during the competition and finished at a later time.
Bertrand (Medium)
This is a fun challenge, and the best part is that it does not require any previous mathematical knowledge. We are given an
image file enc.png, and the code that seems to do some complicated operation to encrypt, the first thing I did is to
figure out what the functions sox and spin does, this seems to be an operation that takes close to 20 seconds to compute on my machine.
Since we know the length of key and start of the flag we can start working with a local key and flag which is known, we can
get the n variable imported from the secret by reading the image size of enc.png and get that n = 256.
#!/usr/bin/env python3
import sys
import math
import functools
from PIL import Image
from random import randint
import string
from secret import flag, key, n
def pad(s, l):
while len(s) < l:
s += string.printable[randint(0, 61)]
return s
def sox(n, d):
x, y, t = 0, 0, d
for s in range(n - 1):
u = 1 & t // 2
v = 1 & t ^ u
x, y = spin(2**s, x, y, u, v)
x += 2**s * u
y += 2**s * v
t = t // 4
return x, y
def spin(n, x, y, u, v):
if v == 0:
if u == 1:
x = n - 1 - x
y = n - 1 - y
x, y = y, x
return x, y
def encrypt(msg, key, n):
_msg = pad(msg, n ** 2)
_msg, _key = [ord(_) for _ in _msg], [ord(_) for _ in key]
img = Image.new('RGBA', (n, n), 'darkblue')
pix = img.load()
for _ in range(len(key)):
w = len(_key)
h = n**2 // w + 1
arr = [[_msg[w*x + y] if w*x + y < n**2 else None for x in range(h)] for y in range(w)]
_conf = sorted([(_key[i], i) for i in range(w)])
_marshal = [arr[_conf[i][1]] for i in range(w)]
_msg = functools.reduce(lambda a, r: a + _marshal[r], range(w), [])
_msg = list(filter(lambda x: x is not None, _msg))
_msg = [(_msg[_] + _key[_ % w]) % 256 for _ in range(n**2)]
for d in range(n**2):
x, y = sox(n, d)
pix[x,y] = (_msg[d], _msg[d], _msg[d])
keysum = sum(_key) if w > 0 else 0
orient = keysum % 4
img = img.rotate(90*orient)
return img
assert len(key) == 3
img = encrypt(flag, key, n)
img.save('enc.png')
Because n is fixed
we can figure out what the parameter d does to the function, because there are only $2^{16}$ elements we can form a lookup
table corresponding to the d, I also serialized the list for significantly faster lookups and removed the 20 seconds of processing entirely, if we convert the 2d $(x, y)$ to 1d array coordinate
we can see that it is just some permutation of $ {0, 1, …, 65535} $, we can easily make an inverse lookup table and
treat the sox function as a black box which does some invertible operation.
for d in range(n**2):
x, y = sox(n, d)
sox_lookup[y * n + x] = d
inv_lookup[d] = y * n + x
The final operation the encryption does is to rotate the image, I started with a simple function that rotates the image
and performs inverse lookup to undo the sox operation
def get_unsox(orient):
n = 256
msg_unsoxed = [-1 for _ in range(n**2)]
with Image.open("enc.png") as img:
img = img.rotate(orient)
pix = img.load()
for d in range(n**2):
h = inv_lookup[d]
x, y = h % n, h // n
r, g, b, _ = pix[x, y]
if r == g and g == b:
msg_unsoxed[d] = r
else:
raise Exception('Something went wrong')
return msg_unsoxed
The most complicated part of the encryption seems to be the loop that iterates over the length of key
and does some sort of mixing operation if you are familiar with AES. Before the first step
it pads the message until it gets 65536 elements and at each iteration of key length it maps
into an array with 3 rows (it will add empty value if the wrapping goes over the total number of elements, but for the most part this is not relevant)
which is just the 3-by-h transposition of the 2d array.
Then the loop rearranges the rows based on the numeric ASCII value after sorting from smallest to the largest, followed
by flattening the 2d list to a 1d list, then after getting rid of the empty values after over wrapping, it simply adds the numeric
value of key (unsorted) to our message. It does these operations in a loop, length of key times updating our _msg list each time.
The key idea is to realize that mixing the 2d array simply based on a key length of 3 leaves only 6 possible choices for the mixing operation. I wrote a simple function to track the position the loop will end up on given a starting position and array indices. I also added in feature so that the function will return the key index that gets added with message on each iteration
def track_scrambling(conf, _msg):
idxs = []
w = 3
for dd in range(w):
h = n**2 // w + 1
arr = []
for y in range(3):
row = []
for x in range(h):
if w*x + y < n ** 2:
if _msg[w*x + y] == 1:
row.append(1)
else:
row.append(-1)
else:
row.append(None)
arr.append(row)
_marshal = [arr[conf[i]] for i in range(w)]
_msg = functools.reduce(lambda a, r: a + _marshal[r], range(w), [])
_msg = list(filter(lambda x: x is not None, _msg))
for i, x in enumerate(_msg):
if x == 1:
idxs.append(i % 3)
assert(len(idxs) == 3)
for i,x in enumerate(_msg):
if x == 1:
return i, idxs
There are certainly faster and more optimal ways to do this, but this was very easy to implement and understand and is more
than adequately efficient for our use case. If we fix an array index conf, and since we know the flag starts with CCTF{
we can calculate the ending positions of the first 5 characters and create an equation solver with 3 unknowns $k_0, k_1, k_2$,
and 5 equations and try to solve for each of the possible 4 orientations $90\degree, 180\degree, 270\degree, 0\degree$ and 6 possible
indices $[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]$, if we get a solution we can try that corresponding key value
def FindKey():
msg_start = [ord(c) for c in 'CCTF{']
solutions = []
unknowns = var('x y z')
for o in range(4):
unsoxed = get_unsox(o*90)
for i, j, k in all_choices(3):
eqs = []
for pos in range(len(msg_start)):
msg = [0] * pos + [1] + [0] * (n**2 - pos - 1)
_C0, kidxs = track_scrambling([i, j, k], msg)
kidxs.sort()
# print(kidxs)
eqs.append(unknowns[kidxs[0]] + unknowns[kidxs[1]] + unknowns[kidxs[2]] + msg_start[pos] == unsoxed[_C0])
print(f'[+] Trying to solve equation to for {90*o}° at position')
s = solve_mod(eqs, 256)
if len(s) < 1:
continue
for possible in s:
k0, k1, k2 = possible
key = chr(k0) + chr(k1) + chr(k2)
print(f'[+] Found possible key: {key}')
yield possible
Now if we loop over all the keys this function finds and try to decrypt it by subtracting the keys ASCII value at each iteration we can print any number of characters from the encrypted message
NUM_CHARS = 50
for _key in FindKey():
flag = b''
unsoxed = get_unsox(int(90*lift(-sum(_key) % 4)))
conf = sorted([(_key[i], i) for i in range(3)])
conf = [i for _, i in conf]
for pos in range(NUM_CHARS):
msg = [0] * pos + [1] + [0] * (n**2 - pos - 1)
moved, kidxs = track_scrambling(conf, msg)
kidxs.sort()
c = unsoxed[moved]
m = (c - _key[kidxs[0]] - _key[kidxs[1]] - _key[kidxs[2]]) % 256
flag += bytes([m])
print(f'[+] Found flag: {flag}')
break
Because I wrote this in sagemath I had to lift the number from $\mod 4$ to the integers, otherwise it creates a very
subtle and hard to find bug.
FLAG: CCTF{3nCrypTioN_8Y_c0lUmn4R_7rAnSp05it!On!}
ASIv1 (rated Medium but really easy)
We are given the following script and this output.txt file. This is a very easy challenge, you simply solve the matrix equation and reconstruct the number given the coefficients of Euclidean algorithm.
from Crypto.Util.number import *
from flag import flag
def base(n, l):
D = []
while n > 0:
n, r = divmod(n, l)
D.append(r)
return ''.join(str(d) for d in reversed(D)) or '0'
def asiv_prng(seed):
l = len(seed)
_seed = base(bytes_to_long(seed), 3)
_seed = [int(_) for _ in _seed]
_l = len(_seed)
R = [[getRandomRange(0, 3) for _ in range(_l)] for _ in range(_l**2)]
S = []
for r in R:
s = 0
for _ in range(_l):
s += (r[_] * _seed[_]) % 3
# s += getRandomRange(0, 3)
s %= 3
S.append(s)
return R, S
seed = flag.lstrip(b'CCTF{').rstrip(b'}')
R, S = asiv_prng(seed)
f = open('output.txt', 'w')
f.write(f'R = {R}\nS = {S}')
f.close()
The solve script is
from Crypto.Util.number import *
import json
from sage.all import *
def unbase(r_s):
n_s = [0]
for r in r_s:
r = int(r)
n_s.append(n_s[-1]*3 + r)
return n_s[-1]
with open('output.txt', 'r') as fp:
R = fp.readline()
R = R[R.find('= ')+2:]
R = json.loads(R)
S = fp.readline()
S = S[S.find('= ')+2:]
S = json.loads(S)
M = matrix(GF(3), 110**2, 110, R)
v = vector(GF(3), S)
seed = list(M.solve_right(v))
flag = b'CCTF{' + long_to_bytes(unbase(seed)) + b'}'
print(flag)
FLAG: CCTF{3Xpl0i7eD_bY_AtT4ck3r!}
Risk (Medium)
#!/usr/bin/env python3
from Crypto.Util.number import *
from secret import m, flag
def genPrime(m, nbit):
assert m >= 2
while True:
a = getRandomNBitInteger(nbit // m)
r = getRandomNBitInteger(m ** 2 - m + 2)
p = a ** m + r
if isPrime(p):
return (p, r)
def genkey(m, nbit):
p, r = genPrime(m, nbit // 2)
q, s = genPrime(m, nbit // 2)
n = p * q
e = r * s
return (e, n)
def encrypt(msg, pkey):
e, n = pkey
m = bytes_to_long(msg)
c = pow(m, e, n)
return c
pkey = genkey(m, 2048)
enc = encrypt(flag, pkey)
print(f'pkey = {pkey}')
print(f'enc = {enc}')
pkey = (150953688, 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983)
enc = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883
The first order of business is to find the secret value of m, since r*s directly involves that, we can factor the small public exponent given and combine factors so that both r and s have the same bit length after which we can recover that $m = 4$, so at the end the bit length of both prime are actually 256, we can try to factorize this
and get
p = 24854995563762799317055160315647073592768859410925406616067526817964296709994775588158311030813096922905657553370793515214591086698010302872311633588541111630338981703494212247996116660819640489213219705595382514374022123356637290058228183400682431815794876393612877273757515867990847040787313812864434536969
q = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675938807
However, if we try to find the inverse of $e \mod \phi$, we hit a roadblock straightaway because $\gcd(e, \phi) = 10728$, this means that $e$ does not have a multiplicative inverse modulo $\phi$, and so we cannot just take the ciphertext to some power and expect to get back the plaintext. However, since we know the prime factorization we can with relative ease find nth roots of some power in $F_p$ and $F_q$ separately and use the Chinese remainder theorem to find the root modulo n. Because $\gcd(e, q-1) = 6$ and $\gcd(e, p-1) = 10728$, by Bezout’s identity we can find $m^6 \mod q$ and $m^{10728} \mod p$. This will significantly optimize the running time of our square roots, since most of the brute force only happens when taking the roots in $F_p$. For ease with showing progress and simplicity I factored 10728 into $149*72$ and found the roots separately. In sage, you can do the following to find arbitrary roots in $F_p$
P.<x> = PolynomialRing(Zmod(p))
f = x**149 - m_pow_10728
Now what’s left is to use Chinese remainder theorem to reassemble the $m \mod n$ and check if the decrypted message starts with ‘CCTF’
FLAG: CCTF{S!mP1E_A7t4cK_0n_SpEc1aL-5trucTur3D_RSA_pR1me5!}
Vinefruit (Hard)
#!/usr/bin/env python3
import sys
import random
import binascii
from flag import flag
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 vinefruit(msg, mod, flag = 0):
P = [16777619, 1099511628211, 309485009821345068724781371]
O = [2166136261, 14695981039346656037, 144066263297769815596495629667062367629]
assert mod in [0, 1, 2]
p, o, m = P[mod], O[mod], 2 ** (2 << (4 + mod))
vine = o
for b in msg:
if flag == 1:
vine = (vine + b) % (2 ** 128)
else:
vine = vine ^ b
vine = (vine * p) % m
return vine
def main():
border = "|"
pr(border*72)
pr(border, " Hi all, I have designed a gorgeous cryptography hash function in ", border)
pr(border, " order to secure the world! Your mission is to find collision for ", border)
pr(border, " this function with specific conditions. ", border)
pr(border*72)
step = 19
while True:
pr("| Options: \n|\t[S]ubmit collision \n|\t[Q]uit")
ans = sc().decode().lower().strip()
if ans == 's':
S = []
for level in range(step):
mod = random.randint(0, 2)
pr(border, f'Submit two different string such that vinefruit(m1, {mod}, 1) = vinefruit(m2, {mod}, 1)')
pr(border, f'You are at level: {level + 1}')
if level == step - 1 and len(S) == step - 1:
die(border, f'Congrats, you got the flag: {flag}')
try:
pr(border, f'Please send first byte string: ')
s1 = sc()[:-1]
pr(border, f'Please send second byte string: ')
s2 = sc()[:-1]
s1, s2 = binascii.unhexlify(s1), binascii.unhexlify(s2)
except:
pr(border, 'You should send valid hex strings.')
break
if len(s1) == len(s2) == 35 - level and s1 != s2:
if vinefruit(s1, mod, 1) == vinefruit(s2, mod, 1):
if vinefruit(s1, mod, 1) not in S:
S.append(vinefruit(s1, mod, 1))
pr(border, 'gj, try the next level :)')
else:
break
else:
break
else:
die(border, 'Kidding me?! Try again and be smart!! Bye!!!')
elif ans == 'q':
die(border, 'Quitting...')
else:
die(border, 'You should select valid choice!')
if __name__ == '__main__':
main()
The objective of this challenge is to find collisions against 17 separate outputs on a rolling hash where the moduli are $2^{32}, 2^{64}, 2^{128}$. This took me a while to solve, and I think I learned a lot from this challenge in particular. The way I solved it (and from the looks of it others as well), is to rephrase the problem in-terms of lattices and use the powerful LLL algorithm to find vectors with the smallest lengths, because this challenge was significantly harder, I cannot go full in-depth into my solution. Rolling hashes are mathematically very easy to rephrase, our goal is to find two distinct $(a_1, …, a_n), (b_1, …, b_n)$ such that $$ (a_n + s)p^n + a_{n-1}p^{n-1} + … + a_1p \mod 2^{i} = (b_n + s)p^n + … + b_1p $$ where $p, s$ are the corresponding values from the list $P, O$ in the function, note that all the $a_i, b_i \in \{0, 255\}$, we can further rephrase it as finding $$ c_np^n + … + c_1p \mod 2^{i} = 0 $$ Where, $ c_i \in \{-255, 255\} $ since the smallest length the challenge asks is 17, we can find one set of $c_1, … c_{17}$ and send the same bytes at each of the corresponding positions of the two data we are finding collisions. This is the part where I skip the heart of the problem and use LLL to find the vector $v = (-64, 5, 73, 35, -53, 19, -10, -78, -44, 48, 61, -1, -80, 26, -22, 72, -31)$ to find collisions in $\mod 2^{128}$ by
for i in range(17):
s = 125
msg1.append(s)
msg2.append(s+v[i])
print(f'{vinefruit(msg1, _m)} ==? {vinefruit(msg2, _m)}')
# 87878065646535226217207999987159837038 ==? 87878065646535226217207999987159837038
Similarly, you can find the vectors corresponding to the other moduli $$ \begin{align*} v_{32} &= (-1, 1, -1, -1, 0, 1, 1, 0, 0, 0, 2, 1, -1, 1, 0, 0, -1) \newline v_{64} &= (2, -4, 0, 2, -1, 5, -8, -1, -1, -3, 5, -5, -2, -7, -4, 1, -3) \end{align*} $$
One can check these values by constructing two different hashes similar to the snippet before. When I was writing it, the remote servers were not available, so I have not posted the flag here.
Slowsum (Tough)
Although this challenge was in the tough section, it seems to be a psychological trick, and it didn’t seem that hard to me when I later solved it.
#!/usr/bin/env sage
import sys
from itertools import product
from flag import flag
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 slowsum(p, n):
g = 0
perms = list(product([0, 1], repeat = n))
for _prm in perms:
g += p(_prm)
return g
def h4sh(p, q):
coeffs = p.coefficients()
return pow(sum(coeffs), (q - 1) // 2 - sum(coeffs), q)
def main():
border = "|"
pr(border*72)
pr(border, "Hi all, I have created a basic and rudimentary version of a sumcheck", border)
pr(border, "protocol. Your task is to generate a false statement and persuade ", border)
pr(border, "verifier of its validity. ", border)
pr(border*72)
q = 2**61 - 1 # Mersenne prime
F = GF(q)
while True:
pr("| Options: \n|\t[C]laim the statement \n|\t[D]etermine parameters and polynomial \n|\t[Q]uit")
ans = sc().decode().lower().strip()
if ans == 'd':
pr(border, f'Please first send the number of variable and the degree of your desired polynomial:')
_ans = sc()
try:
_n, _d = [int(_) for _ in _ans.split(b',')]
if (_n * _d) // q < 5e-17 and _n >= 5 and _d >= 3:
R = PolynomialRing(F, _n, 'x')
x = R.gens()
else:
raise Exception()
except:
die(border, 'The parameters are not consistent! Try again!!')
pr(border, f'Now, please send the {_n}-variable polynomial as p: ')
_p = sc().strip().decode()
try:
_p = R(_p)
p = _p
_deg = _p.degree(std_grading=True)
if _deg != _d:
raise Exception()
except:
die(border, 'The polynomial is not valid or does not hold true in the given situations!')
g = slowsum(_p, _n)
elif ans == 'c':
pr(border, 'Please send the g: ')
_g = sc()
try:
_g = int(_g)
if _g == g:
die(border, 'Kidding me?! Bye :P')
except:
die(border, 'Some exception occurred! Bye!!')
_P, _H = [], []
for i in range(_n):
pr(border, f'Please send the (p_{i}, h4sh(p_{i}, q)): ')
pr(border, f'Note that the variable of p_{i} should be x. ')
_ph = sc().strip()
try:
_p, _h = [_.decode() for _ in _ph.split(b',')]
_R = PolynomialRing(F, 'x')
_p, _h = _R(_p), F(_h)
if _p.degree() > _d:
raise Exception()
_P.append(_p)
_H.append(_h)
except:
die(border, 'Some exception occurred! Bye!!')
j = 0
for i in range(_n):
if i == 0:
if _P[i](0) + _P[i](1) != _g or h4sh(_P[i], q) != _H[i]:
break
else:
if _P[i](0) + _P[i](1) != _P[i-1](_H[i-1]) or h4sh(_P[i], q) != _H[i]:
break
j += 1
if j < _n or p(_H) != _P[_n-1](_H[_n-1]):
die(border, 'Oops, verifier believes that the polynomial is not valid! Bye!!')
die(border, f'Congrats, here the flag: {flag}')
elif ans == 'q':
die(border, 'Quitting...')
else:
die(border, 'You should select valid choice!')
if __name__ == '__main__':
main()
The objective is to first give the server two numbers $n, d$ where $n$ is the number of variables and $d$ is the degree of multinomial, the minimum values are 5 and 3 correspondingly, after we give the server our polynomial $P$ it does “slowsum” which basically takes the sum of evaluations after substituting 0 or 1 to all $n$ variables through all possible combinations. Then it asks a value “g” not equal to the output of slowsum and for $n$ different polynomials $P_1, … P_n$ in one variable as well as it’s corresponding h4sh $H_1, … H_n$. It then checks that sum of evaluations at 0 and 1 such that $$ P_0(0) + P_0(1) = g \newline P_i(0) + P_i(1) = P_{i-1}(H_{i-1}) $$ for $i > 1$ and $$ P(H_1, …, H_n) = P_{n}(H_n) $$ all these operations seems complicated and unmanageable to understand, but if we pick random values for most of them and try to reverse the remaining variables, we can solve it with relative ease. Firstly, we fix $n = 5, d = 3$ and pick some random $g$ in $F_{2^{61} - 1}$
F = GF(2^61 - 1)
def satisfying_eq(s, d):
coeffs = []
for i in range(d):
coeffs.append(F.random_element())
return [(s - sum(coeffs)) / 2] + coeffs
def from_coeffs(coeffs, d):
_R = PolynomialRing(F, 'x')
_p = '0 '
for e in range(d+1):
_p += f'+ {coeffs[e]}*x^{e} '
return _R(_p)
for i in range(n):
if i == 0:
coeffs = satisfying_eq(g, d)
_hmm = g
else:
coeffs = satisfying_eq(_ps[i-1](h4sh(_ps[i-1])), d)
_hmm = h4sh(_ps[i-1])
_ps.append(from_coeffs(coeffs, d))
_hs.append(h4sh(_ps[i]))
print('Polynomials: P_1, ..., P_5: ', _ps)
print('Hashes: H_1, ..., H_5: ', _hs)
This will find the $n$ single variable polynomials satisfying our requirement. To find the multinomial that satisfies our requirement, we can simply just restrict it to single variable and pick
R = PolynomialRing(F, n, 'x')
_p = f'x0^{d} - {_hs[0]^d} + {_ps[-1](_hs[-1])}'
P = R(_p)
This forces $P(H_1, …, H_n) = P_{n}(H_n)$ are required.