Infinity Castle

Catégorie: medium-easy

Points: 131

Résolutions: 32

First blood! 🩸

Énoncé

Can you break our new schema and decrypt the mixed encrypted message without having the public key and shared secret?!

#!/usr/bin/env python3

from Crypto.Util.number import *
from os import urandom

class TaylorSeries():

	def __init__(self, order):
		self.order = order
		
	def coefficient(self, n):
		i = 0
		coef = 1
		while i < n:
			i += 1
			coef *= (coef * (1/2-i+1)) / i
		return coef

	def find(self, center):
		sum = 0
		center -= 1
		i = 0
		while i < self.order:
			sum += (center**(1/2-i) * self.coefficient(i))
			i += 1
		return sum

def xor(cip, key):
	repeation = 1 + (len(cip) // len(key))
	key = key * repeation
	key = key[:len(cip)]
	
	msg = bytes([c ^ k for c, k in zip(cip, key)])
	return msg

# If you run these 3 functions (diamond, triage, summarize) with big numbers, they will never end
# You need to optimize them first

def diamond(num):
	output = 0
	for i in range(num):
		output += i*2 + 1
	return output

def triage(num):
	output = 0
	index = 0
	for i in range(num):
		output += (i+index)*6 + 1
		index += i
	return output

def summarize(b):
	order = getRandomRange(1000, 2000)
	t = TaylorSeries(order)
	output = 0
	
	i = 2
	while i < b:
		b1 = t.find(i)
		b2 = t.find(i+1)
		output += (b1+b2) / 2
		i += 1
	return output

KEY_SIZE = 2048
p, q = [getPrime(KEY_SIZE) for _ in '01']

e, n = 0x10001, p*q

f = open ('./message.txt', 'rb')
message = f.read()
f.close()
msg_length = len(message)
padded_msg = message + urandom(len(long_to_bytes(n)) - msg_length)
padded_msg_length = len(padded_msg)

xor_key = long_to_bytes(int(summarize(n)))[:padded_msg_length]
assert(len(xor_key) == 512)

enc0 = xor(padded_msg, xor_key)
assert(bytes_to_long(enc0) < n)

c0 =  abs(diamond(p) - diamond(q))
c1 =  triage(p)
c1 += 3*n*(p+q)
c1 += triage(q)

m = bytes_to_long(enc0)
enc1 = pow(m, e, n)

print(f"c0 = {c0}")
print(f"c1 = {c1}")
print(f"enc = {enc1}")

avec les données:

c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045

Analyse des fonctions diamond et triage

Nous sommes prévenus que les fonctions fournies dans le code ne sont «pas optimisées».

Par exemple la fonction diamond(n) calcule:

\[\sum_{i=0}^n 2i+1 = n^2\]

De même la fonction triage(n) calcule la somme d’une fonction de degré 2 (à chaque itération index == i*(i-1)/2) et on sait que dans ce cas, elle doit être égale à un polynôme de degré 3.

Les premières valeurs donnent la réponse immédiatement:

In [1]: [triage(n) for n in range(10)]
Out[1]: [0, 1, 8, 27, 64, 125, 216, 343, 512, 729]

In [2]: all([triage(n) == n**3 for n in range(1000)])
Out[2]: True

On peut alors retrouver p et q:

c0 =  abs(diamond(p) - diamond(q))
c1 =  triage(p)
c1 += 3*n*(p+q)
c1 += triage(q)

grâce aux identités:

c0 = (p-q)*(p+q)
c1 = (p+q)**3

En effet c1 donne la somme p+q par racine cubique, et obtient p-q = c0/(p+q).

Grâce aux valeurs de p et q, on peut inverser l’encodage RSA et obtenir enc0.

Analyse de TaylorSeries

Comme son nom l’indique cette fonction décrit le calcul d’une formule de Taylor dont les coefficients sont de la forme:

\[a_n = \prod_{i=1}^n \frac{1/2 - i + 1}{i}\]

soit:

\[f(x) = 1 + \frac 1 2 x + \frac 1 2 \big( \frac {-1} 2 \big) \frac{1}{2!} x^2 + ...\]

On reconnaît la série de Taylor de la fonction racine carrée. Vérifions empiriquement:

In [9]: [ts.find(x)**2 for x in range(2, 10)]
Out[9]: 
[2.0607879850956023,
0461572205234684,
034363357385889,
0271310008269765,
022359724979985,
018997922516909,
016507694540005,
014591266875902]

La fonction summarize effectue alors la somme de 2 à b de (f(i) + f(i+1)) / 2 : on reconnaît un calcul d’intégrale par la méthode des trapèzes.

On en déduit que summarize(n) est environ n**1.5 / 1.5 à quelques unités près.

Solution

from sage.all import Integer

p_plus_q = c1.nth_root(3)
p_minus_q = c0 // p_plus_q

p = (p_plus_q + p_minus_q) // 2
q = (p_plus_q - p_minus_q) // 2
n = p*q
d = pow(65537, -1, (p-1)*(q-1))
enc0 = int(pow(enc, d, n)).to_bytes(512, "big")

integral = (Integer(n**3).isqrt() * 2) // 3 - 1
key = int(integral).to_bytes(2048, "big").lstrip(b"\0")[:512]

print(bytes(a^^b for a,b in zip(enc0, key)))

# Never heard of using taylor series and integral beside RSA?!
# But there are always ways to make things complicated
# CCTF{Mix1ng_c4lcUluS_w17h_Numb3r_The0Rry_S33ms_s7r0ng_cRyp70_Sch3m4!!}
# We compute integrals with just measuring the area with a little fraction, forget about tough works!
# Good luck with the rest of CryptoCTF2022