My writeups for the Cryptography challenges of the 2023 Cryptoverse CTF!
Information
These are all the Crypto challenges I managed to solve. Here’s the link to my github repo that has the full solving scripts.
Challenges
Baby AES
Difficulty: easy
Description: Simple AES.
Code Analysis
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag
KEY_LEN = 2
BS = 16
key = pad(open("/dev/urandom","rb").read(KEY_LEN), BS)
iv = open("/dev/urandom","rb").read(BS)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(flag, 16))
print(f"iv = {iv.hex()}")
print(f"ct = {ct.hex()}")
# Output:
# iv = 1df49bc50bc2432bd336b4609f2104f7
# ct = a40c6502436e3a21dd63c1553e4816967a75dfc0c7b90328f00af93f0094ed62
Well well, the main issue here is that the key is 2 random bytes that are padded with Pycryptodome’s builtin padding function. We can easy bruteforce that. The minimum and maximum range for the key is 2^8,2^16.
Solution
We can try every integer in this range until the flag is found:
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad
KEY_LEN = 2
BS = 16
iv = bytes.fromhex('1df49bc50bc2432bd336b4609f2104f7')
ct = bytes.fromhex('a40c6502436e3a21dd63c1553e4816967a75dfc0c7b90328f00af93f0094ed62')
for i in range(2**8,2**16):
key = pad(long_to_bytes(i),BS)
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = cipher.decrypt(ct)
if b'cvctf' in pt:
print(unpad(pt,16).decode())
break
#cvctf{b4by_AES_s1mpL3}
Flag: cvctf{b4by_AES_s1mpL3}
LFSR Explorer
Difficulty: medium
Description:
Explorer instead of Destroyer.
Code Analysis
My most hateddddddd Cryptography stuff is anything related to bitwise changes 😭
from Crypto.Util.number import *
from secret import flag
assert flag.startswith("cvctf{")
assert flag.endswith("}")
flag = flag[6:-1].encode()
assert len(flag) == 8
def explore(state, mask):
curr = (state << 1) & 0xffffffff
i = state & mask & 0xffffffff
last = 0
while i != 0:
last ^= (i & 1)
i >>= 1
curr ^= last
return (curr, last)
states = [bytes_to_long(flag[4:]), bytes_to_long(flag[:4])]
mask = 0b10000100010010001000100000010101
output = []
for i in range(8):
tmp = 0
for j in range(8):
(states[i // 4], out) = explore(states[i // 4], mask)
tmp = (tmp << 1) ^ out
output.append(tmp)
with open("output.txt", "wb") as f:
f.write(bytes(output))
A few things to notice:
- the flag is split into two, and converted to a long integer
- the function explore iterates 32 times for each state, and then the ‘tmp’ ********is shifted left, and xored with the result.
First, we can recover the ‘out’ values, and each tmp value of the output. The recovered out values (which are either 1 or 0), when concatenate together and converted from binary to long integer, actually represents the last result of the explore(states[i//4],mask) function. So if we find this value, we can simply reverse until we get all the results for all states.
Solution
from Crypto.Util.number import *
mask = 0b10000100010010001000100000010101
def recover_all(output):
all_recs=[]
for val in output:
reced = [val]
for i in range(8):
val = val >> 1
reced.append(val)
reced.reverse()
all_recs.append(reced)
all_bs = []
for reced in all_recs:
bb =[]
for x in range(0,len(reced)-1):
if (reced[x]<<1)^0 == reced[x+1]:
bb.append(0)
else:
bb.append(1)
all_bs.append(bb)
return all_recs,all_bs
def explore(state, mask):
curr = (state << 1) & 0xffffffff
i = state & mask & 0xffffffff
last = 0
while i != 0:
last ^= (i & 1)
i >>= 1
curr ^= last
return (curr, last)
#trying everything cuz im lazy
def check_val(last,x):
good = 0
nextv = (last^1)>>1
nextv2 = (last^0)>>1
nextv3 = ((((last^0)>>1)|0xffffffff))+last>>1
nextv4 = ((((last^1)>>1)|0xffffffff))+last>>1
nextv5 = nextv3+1
nextv6 = nextv4+1
c1,v1 = explore(nextv,mask)
c2,v2 = explore(nextv2,mask)
c3,v3 = explore(nextv3,mask)
c4,v4 = explore(nextv4,mask)
c5,v5 = explore(nextv5,mask)
c6,v6 = explore(nextv6,mask)
if c1 == last:
return nextv
elif c2 == last:
return nextv2
elif c3 ==last:
return nextv3
elif c4==last:
return nextv4
elif c5==last:
return nextv5
elif c6==last:
return nextv6
else:
return None
def recover_states(flats,last,x):
flats = flat[x-32:x]
flats.reverse()
last = last
bs = []
for x in flats:
xv = check_val(last,x)
if xv:
last = xv
if not xv:
xv= check_val(last-1,x^1)+1
last = xv
bs.append(last)
return bs
output = [x for x in bytes.fromhex('D5E4B7C792248E32')]
recovered,out_vals=recover_all(output)
outs = [x for c in out_vals for x in c]
l1 = int('0b'+''.join([str(x) for x in outs[0:32]]),2)
l2 = int('0b'+''.join([str(x) for x in outs[32:]]),2)
states_1 = recover_states(outs,l1,32)
states_2 = recover_states(outs,l2,32+32)
flag_ = b'cvctf{'+long_to_bytes(states_2[-1])+long_to_bytes(states_1[-1])+b'}'
print(flag_.decode())
#cvctf{G@@d_j0b}
Flag: cvctf{G@@d_j0b}
Knapsack vs. Backpack
Difficulty: Medium
Description: Uh, would you rather call it a knapsack or a backpack?
Code Analysis
from Crypto.Util.number import *
from math import gcd
from secret import flag
import random
NBITS = 32
print("=== Knapsack vs. Backpack ===")
class Knapsack:
def __init__(self, nbits):
W, P = [], []
for _ in range(nbits):
W.append(random.randint(1, 10))
P.append(random.randint(1, 100))
self.W, self.P = W, P
def fill(self, nbits):
r = getRandomNBitInteger(nbits)
pt = [int(i) for i in bin(r)[2:].zfill(nbits)]
self.A = sum([x * y for x, y in zip(pt, self.W)])
self.B = sum([x * y for x, y in zip(pt, self.P)])
try:
for _ in range(10):
challenge1 = Knapsack(NBITS*4)
challenge1.fill(NBITS*4)
print(challenge1.W)
print(challenge1.P)
print(f"Knapsack Capacity: {challenge1.A}")
inp = list(map(int, input("Items: ").strip().split()))
for i in inp:
if i < 0 or i >= len(challenge1.W):
print("Nope.")
exit(1)
if len(inp) != len(set(inp)):
print("Nope.")
exit(1)
weight = sum([challenge1.W[i] for i in inp])
profit = sum([challenge1.P[i] for i in inp])
if weight <= challenge1.A and profit >= challenge1.B:
print("Correct!")
else:
print("Nope.")
exit(1)
except:
exit(1)
print(flag[:len(flag)//2])
class Backpack:
def __init__(self, nbits):
r = [42]
for _ in range(nbits - 1):
r.append(random.randint(2*r[-1], 4*r[-1]))
B = random.randint(3*r[-1] + 1, 4*r[-1])
A = random.randint(2*r[-1] + 1, B - 1)
while gcd(A, B) != 1:
A = random.randint(2*r[-1] + 1, B - 1)
self.M = [A * _ % B for _ in r]
def fill(self, inp):
return sum([x * y for x, y in zip(inp, self.M)])
try:
for _ in range(10):
challenge2 = Backpack(NBITS)
r = getRandomNBitInteger(NBITS)
pt = [int(i) for i in bin(r)[2:].zfill(NBITS)]
ct = challenge2.fill(pt)
print(challenge2.M)
print(f"In your Knapsack: {ct}")
inp = int(input("Secret: ").strip())
if inp == r:
print("Correct!")
else:
print("Nope.")
exit(1)
except:
exit(1)
print(flag[len(flag)//2:])
In order to get the full flag, there are two checks being performed. The first one, is the knapsack problem.
class Knapsack
At each loop, the class Knapsack is initialised. It has two parameters, that we will be tested on: W and P. They are both lists of random integers, 1 to 10 for W, and 1 to 100 for P. Then, a random integer of 128 bits is created, and its converted into a list of its binary representation (so zeros and ones). Then, each element in the list of random bits is multiplied by each element in list W, giving us value A. The same happens for list P, giving us value ****B. The server gives us both list W and P, and the value of A.
The test, is to send a list of unique indexes for both P and W (so one list for both). The server then calculates the sum of the indexed P list. If the sum is below A and above B we pass the test.
The challenge here is mostly that we need to find a list that works for both P and W, but also that we don’t know the value of B. If we get a single answer wrong, the server quits and we have to start over.
class Backpack
This is kind of the opposite of knapsack, where we have to find the multiplier. It seems hard, but if we look at how the multiplier is being generated, it’s pretty straightforward:
nbits = 32
r = [42]
for _ in range(nbits - 1):
r.append(random.randint(2*r[-1], 4*r[-1]))
So the r is actually a super increasing sequence. List A and B are calculated with the last value of r, but A is modified into the gcd of A and B is not equal to 1.
B = random.randint(3*r[-1] + 1, 4*r[-1])
A = random.randint(2*r[-1] + 1, B - 1)
while gcd(A, B) != 1:
A = random.randint(2*r[-1] + 1, B - 1)
Then, M, the list we are provided with is calculated by multiplying A with each element in r, mod B :
M = [A * _ % B for _ in r]
Finally, we are tested on the following:
M is calculated by the functions above, and then a new random integer of 32 bits is created. We are given the sum of all items in M * new_random_integer. Our job is to find the new_random_integer.
Solution
Step 1: Knapsack
I used sage’s built-in knapsack library to solve the Knapsack problem, and this code for the Backpack problem.
For W, I calculated the knapsack given max value A. Then, I iterated over each value in W, to find the corresponding index, and making sure it was a unique value (since the server checks that all indexes are unique).
I did the same for P, except I gave it a max value A**1.5. Normally, B should be around A*10, if we give this value to sage’s knapsack function, it will give us a much smaller array, resulting in less common indexes between P and W. The server only checks if the result is bigger than B, so giving a larger number still works.
from sage.numerical.knapsack import knapsack
from pwn import *
def solve_knapsack(invalues,maxvalue):
_,knapsacked = knapsack(invalues, max=maxvalue)
potentials = [(i,d) for i,d in enumerate(invalues)]
indexes = []
for val in knapsacked:
found_value = [x for x in potentials if x[1] == val][0]
if found_value not in indexes:
indexes.append(found_value[0])
del potentials[potentials.index(found_value)]
else:
pass
return indexes
def find_index(w,p,a):
indexes_w = solve_knapsack(w,a)
indexes_p = solve_knapsack(p,a**1.5)
commons = [x for x in indexes_p if x in indexes_w]
return str(commons)[1:-1].replace(', ',' ')
Step 2: Backpack
The Backpack problem can be solved using a low density attack. This is the code for the attack:
from math import ceil
from math import log2
from math import sqrt
from shared.lattice import shortest_vectors
def attack(a, s):
n = len(a)
d = n / log2(max(a))
N = ceil(1 / 2 * sqrt(n))
assert d < 0.9408, f"Density should be less than 0.9408 but was {d}."
L = matrix(QQ, n + 1, n + 1)
for i in range(n):
L[i, i] = 1
L[i, n] = N * a[i]
L[n] = [1 / 2] * n + [N * s]
for v in shortest_vectors(L):
s_ = 0
e = []
for i in range(n):
ei = 1 - (v[i] + 1 / 2)
if ei != 0 and ei != 1:
break
ei = int(ei)
s_ += ei * a[i]
e.append(ei)
if s_ == s:
return e
def solve_backpack(M,ct):
out = attack(M, ct)
resi = '0b'+''.join(str(x) for x in out)
return int(resi,2)
Step 3: Server Connection
The Backpack problem can be solved using a low density attack. This is the code for the attack:
host,port="67.205.179.135",int(7272)
conn=remote(host,port)
conn.recvline()
for i in range(10):
w=eval(conn.recvline().decode().strip())
p=eval(conn.recvline().decode().strip())
a= int(conn.recvline().decode().strip()[len('Knapsack Capacity: '):])
indexes=find_index(w,p,a)
conn.sendlineafter(b'Items: ',indexes)
res = conn.recvline()
print(res)
flag1 = conn.recvline()
print(flag1.decode().strip())
#cvctf{knap5ack_0/1_15_for_the_noob5_BUT_
for i in range(10):
M=eval(conn.recvline().decode().strip())
ct=int(conn.recvline().decode().strip()[len('In your Knapsack: '):])
rv = solve_backpack(M,ct)
conn.sendlineafter(b'Secret: ',str(rv))
res = conn.recvline()
print(res)
flag2 = conn.recvline()
print(flag2.decode().strip())
#backp@ck_M3rkl3_h3llm4n_15_for_the_pro5}
FLAG = flag1.decode().strip() + flag2.decode().strip()
print(FLAG)
#cvctf{knap5ack_0/1_15_for_the_noob5_BUT_backp@ck_M3rkl3_h3llm4n_15_for_the_pro5}
Flag: cvctf{knap5ack_0/1_15_for_the_noob5_BUT_backp@ck_M3rkl3_h3llm4n_15_for_the_pro5}
Fractional Flag
Difficulty: hard
Description: My Cryptosystem is not used for encryption, but to break the flag into fractions.
Code Analysis
fractional_flag.py
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from secret import flag
assert len(flag) == 99
assert flag.startswith(b"cvctf{") and flag.endswith(b"}")
class MyRSA:
def __init__(self, n = 2, nbits = 512):
self.p = getPrime(nbits)
self.q = getPrime(nbits)
self.N = self.p * self.q
self.d = getPrime(nbits//2 - 1)
self.my_phi = self.gen_phi(n)
self.e = inverse(self.d, self.my_phi)
def gen_phi(self, n):
return sum([self.p**i for i in range(n)]) * sum([self.q**i for i in range(n)])
def encrypt(self, m):
print("I am not going to encrypt anything...")
return m
def get_public(self):
print(f"N = {self.N}")
print(f"e = {self.e}\n")
def get_private(self):
# print(f"d = {self.d}")
return self.d
NPARTS = 3
fractions = [bytes_to_long(flag[len(flag)//NPARTS*i:len(flag)//NPARTS*(i+1)]) for i in range(NPARTS)]
print("[+] Here are my public keys:")
ns = [2, 3, 6]
rsas = [MyRSA(n) for n in ns]
private_exponents = [rsa.get_private() for rsa in rsas]
for rsa in rsas:
rsa.get_public()
print("[+] Here are my flag fractions:")
for i in range(NPARTS):
f = sum(fractions[j] * private_exponents[i]**(NPARTS-1-j) for j in range(NPARTS))
print(f"[!] Fraction {i+1}: {f}")
output.txt
[+] Here are my public keys:
N = 97612005002255328088089410975523983681740354800179039894937915732930244664586629120094932234362725524185511994009850035922533559839893979074939037832668549750255468381192887812469917667115839541015495242839376266431038121426628287675447989631207259597586333251571969522037989427555616133183042678577218636039
e = 76116130167787561359953887266200869082448529331107937460219287530308978477708991999616543343406382355689250048669403437942401267295685636067522489421767819007148067769751457394505797110602169754511939818788483430730012575308299189299157812591392734160576417069436538119185074252625496946207312639052459476691
N = 82898492840033848499679066573599199466262845944574446435099699953454086638324386416129279494828609729766998439132172194894188387716844097335523066318666261933348513791114624155336437054163128912934864480178839237943154511986161169068625070999701692457965233641625122455113801192492673037347038351956273261209
e = 4209437149177720414392052396995336370571472638739290885909782621676928212352728218779571626530884770305850882606520062302514835362331092897621059096111410844919671863579044484955054277159466422627065939698416080746679841734383574957303171143150437215717944527004524163060734647488552780385109395365103554265493136383680197786179491825415327877829363932241445886199163804911851983235568877189260370900147226881457732043676609664875472514523869518158935427849891304397052900751093562294098001282747462255107311383605819243052786444806092296448159814920695343700003324553167747140120222023780385726663202175975632841101
N = 74994178474501705271671940639744064973727732038326591115828216310018498822567967944888584927591599150655580137956560356301728244890598527629795727836492659456865084635190916504902969902122979161893704294891200235692036639700141954229504462610034653592940594511895628524050995435988759181763969824436031245313
e = 1489343297993123282242703585767862889532966168614466114229659752495521741344828171911376172581419167249138037648594483979411817592040147160238477726426615905245322859547191851844862266610905034585090032979459885344332508376146458008432418485138745167332564668471655885462387844870978937353124271354756749987557641173034038037138552554286596191926276854019397533360181392329678995160770713221738607291949604788483647158238145885370267789175042383720834228546234687195524802723091258548142868749009819341250311783811669486498714774091479332840123020791916467567722826634424992913028930995948675696110790085249624326162007313472329046629836566951986389110657545671708876118803228632059850860536273457909861781873059134865932188230401277356396602494704882757454481213539839098539947582560234411030973307998825870210215033177749651750411682404527804606701340350999128273688467096980925538961234964285918052638858734125375270072587641505250814286217419987349217586276836222849825473745401814287955844160842207855608228330415022147681694596413651097936005515497301045029721788331269208281455180641244748905469345705931987679143863830321305138722585532495234826613572876602582994268211475793765951624522296606385747914811802020368502982841323574845193182348705392733364068634167943152196883988138300398486795444947317920558342244022638552596544997423504070874736567161433560622253197613565603458736833008516912312579020461040855359316882678726669756450813443842584222951463074601799430267187315529031340358497011459213690622999701314023178557960651
[+] Here are my flag fractions:
[!] Fraction 1: 12885959655953139374785717692048211268233398655222955130228721746869891559409080848367142483157517829612928194235174347299097615553919212787225377729454255371358309685093996459461793296183459238094074717707949401000365552082820354011
[!] Fraction 2: 23144924364202496361036242964551729244108242071387074122924446048219898057065538815277890013860024253422666710259842325295228086904295846675276536535237894072110755426259617054492417613772645109337095876879440959135444974146373938103
[!] Fraction 3: 10216090816848970230135050433869173852319169856151418349231810820430643701522230150158652915588855848669985626642166987135416343716291162149831827545892183798838168834007800941773301995075510960084628367588300016798178754792796044603
Code Analysis
1. ‘Encryption’ Algorithm
This is quite an interesting challenge, because the encryption algorithm is not very RSA like.
Each fraction, N and E values are calculated like this:
fraction[i] = d[i]^2*x+d[i]*y+z
#where x,y,z = flag[0:33],flag[33:66],flag[66:] in long integer format
#max bit for each flag is 264
#where d[i] = getPrime(512//2 - 1) --> prime of 255 bits
N[i] = p[i]*q[i]
e[i] = inverse_mod(d[i],my_phi[i])
my_phi[i] = sum([p[i]**i for i in range(n)]) * sum([q[i]**i for i in range(n)])
#where n[i] = [2,3,6]
So essentially, the value of my_phi are:
#my_phi[0] = (p1+1)*(q1+1)
#my_phi[1] = (p2**2+p2+1)*(q2**2+q2+1)
#my_phi[2] == (p3**5+p3**4+p3**3+p3**2+p3+1)*(q3**5+q3**4+q3**3+q3**2+q3+1)
In RSA, the value of phi is supposed to be (p-1)*(q-1), and the private exponent d is the modular inverse of e and phi. The e that we are given is actually the private exponent, because if we replicate the function, the inverse of (e, my_phi) gives us d.
Replication & Tests
def replicate(n):
p = getPrime(512)
q = getPrime(512)
N = p * q
d = getPrime(512//2 - 1)
my_phi = sum([p**i for i in range(n)]) * sum([q**i for i in range(n)])
return p,q,N,d,my_phi
p1,q1,N1,d1,my_phi1 = replicate(2)
e1 = inverse(d1,my_phi1)
inverse(e1,my_phi1) == d1
Now, let’s use the values above to replicate the way the fractions are computed:
fake_flag = b'cvctf{this_is_a_fake_flag_for_testing_this_challenge_and_i_need_to_use_lots_of_words_to_make_it_99}'
NPARTS=3
x,y,z = [bytes_to_long(fake_flag[len(fake_flag)//NPARTS*i:len(fake_flag)//NPARTS*(i+1)]) for i in range(NPARTS)]
enc_1 = d1^2*x+d1*y+z
Now, to solve for the value of enc_1. Given that the value of my_phi is (p+1)*(q+1) and n = p*q, this is the same as N being my_phi, and my_phi being N. We can use a wiener lattice attack to solve the first equation:
from shared.lattice import shortest_vectors
def recover(N,e):
s = isqrt(N)
L = matrix(ZZ, [[e, s], [N, 0]])
for v in shortest_vectors(L):
d = v[1]//s
kval = (e * d - 1)//N
if kval !=0:
my_phi = (e * d - 1) // kval
if inverse(d,my_phi) == e:
return d, my_phi
d1,my_phi1 = recover(N1,e1)
(d1,my_phi1) == (d,my_phi)
enc_1 == d1^2*x+d1*y+z
Here, we could use coppersmith small roots, to solve for (partial) x. Since the known value of y and z is very small, this won’t work to recover their value. TBH this is useless but still wanted to give it a try.
def copper_attack(enc,d,phi_val,bt):
known_pt = bytes_to_long(b'cvctf{')
unknown_b = bytes_to_long(b'A')
unknown_c = bytes_to_long(b'}')
P.<a,b,c> = PolynomialRing(Zmod(phi_val))
bound = 2^bt
bt1 = bt-known_pt.bit_length()
bt2 = bt-unknown_b.bit_length()
bt3= bt-unknown_c.bit_length()-1
f = d^2*(known_pt*2^bt1 + a) + d*(unknown_b*2^bt2 +b) + (unknown_c*2^bt3+c) -enc
bounds = (bound, bound,bound)
sols = small_roots(f, bounds, m =4,d=3)
return sols[0]
sols = copper_attack(enc_1,d1,my_phi1,263)
sol_x=int(sols[0])) + bytes_to_long(b'cvctf{')*2^(263-bytes_to_long(b'cvctf{').bit_length())
diff=sol_x-fake_fractions[0]
#difference of 630
Anyways, this is besides the point because we are not limited to a single fraction. The more complicated part is for the next fractions. Again, reproducing it:
p2,q2,N2,d2,my_phi2 = replicate(3)
e2 = inverse(d2,my_phi2)
enc_2 = sum(fake_fractions[j] * d2**(NPARTS-1-j) for j in range(NPARTS))
recover(N2,e2)
#returns nothing
Unsurprisingly, the recover function doesn’t work! This is because the ‘phi’ value used for the calculation of e is much bigger than the N value (aka p*q). The wiener attack works by taking the square root of N, which won’t work for us. BUT, we can take the modulus and power it to the max value of n. So instead of using the lattice attack, we can use a modified wiener attack, and call for powering up the N value first. Note that this method works for the first value, by simply using 1 for the exponent:
def recover_squared(n,e,exp,bl):
N=n**exp
convergents = continued_fraction(ZZ(e) / ZZ(N)).convergents()
for c in convergents:
k = c.numerator()
d = c.denominator()
kval = (e * d - 1)//N
if kval !=0:
my_phi = (e * d - 1) // kval
if inverse(d,my_phi) == e:
if d.bit_length() == bl:
return d,my_phi
(d1,my_phi1) ==recover_squared(N1,e1,1,255)
(d2,my_phi2)==recover_squared(N2,e2,2,255)
#round3
p3,q3,N3,d3,my_phi3 = replicate(6)
e3 = inverse(d3,my_phi3)
enc_3 = sum(fake_fractions[j] * d3**(NPARTS-1-j) for j in range(NPARTS))
(d3,my_phi3)==recover_squared(N3,e3,5,255)
So we successfully found a way to get the d values. We don’t know enough bits of y and z to use the coppersmith attack, but, since we have three polynomials with three unkowns, we can use the groebner basis.
from shared import small_roots
R.<x,y,z> = PolynomialRing(ZZ, 3, order='lex')
#x,y,z = polygens(R,'x,y,z')
f1 = d1^2*x+d1*y+z - enc_1
f2 = d2^2*x+d2*y+z - enc_2
f3 = d3^2*x+d3*y+z - enc_3
f = f1.change_ring(ZZ)
pr = f.parent()
result = list(small_roots.find_roots_groebner(pr,[f1,f2,f3]))
pts = [long_to_bytes(v) for v in result[0].values()]
flag = b''.join(pts)
flag == fake_flag
print(flag.decode())
#cvctf{this_is_a_fake_flag_for_testing_this_challenge_and_i_need_to_use_lots_of_words_to_make_it_99}
Solution Script
Reproducing the above, but with the real values:
from Crypto.Util.number import long_to_bytes, inverse
def recover_squared(n,e,exp,bl):
N=n**exp
convergents = continued_fraction(ZZ(e) / ZZ(N)).convergents()
for c in convergents:
k = c.numerator()
d = c.denominator()
kval = (e * d - 1)//N
if kval !=0:
my_phi = (e * d - 1) // kval
if inverse(d,my_phi) == e:
if d.bit_length() == bl:
return d,my_phi
def solve_polynomials(rsas,encs):
enc_1,enc_2,enc_3=encs
d1,rsa_phi1 = recover_squared(rsas[0][0],rsas[0][1],1,255)
d2,rsa_phi2 = recover_squared(rsas[1][0],rsas[1][1],2,255)
d3,rsa_phi3 = recover_squared(rsas[2][0],rsas[2][1],5,255)
R.<x,y,z> = PolynomialRing(ZZ, 3, order='lex')
f1 = d1^2*x+d1*y+z -enc_1
f2 = d2^2*x+d2*y+z -enc_2
f3 = d3^2*x+d3*y+z -enc_3
f = f1.change_ring(ZZ)
pr = f.parent()
gens = pr.gens()
s = Sequence([f1,f2,f3], pr.change_ring(QQ, order="lex"))
G = s.groebner_basis()
roots=[]
for poly in G:
roots.append(poly.univariate_polynomial().roots()[0][0])
return b''.join([long_to_bytes(x) for x in roots])
with open('output.txt', 'r') as inf:
data = inf.read().splitlines()
enc = [int(x[16:]) for x in data if 'Fraction' in x]
flr = [int(x[4:]) for x in data[1:-4] if x != '']
rsas = [(flr[i],flr[i+1]) for i in range(0,len(flr),2)]
flag = solve_polynomials(rsas,enc)
print(flag.decode()
#cvctf{th15_fam1Ly_0f_RSA-like_crypt0syst3m_c4n_b3_4tt4ck3d_wh3n_E_15_cL053_t0_N^(n-1)_4nd_d<N^0.25}
