FCSC 2025 Writeups

發表於 2025-04-28

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

FCSC (France Cybersecurity Challenge) 2025 is a CTF competition used by France to select players for ECSC. Because the quality of the problems in previous years was considered very good, I decided to play solo this year as well. I mainly solved some crypto problems, which were quite challenging and fun.

La quête de l'anneau

#!/usr/bin/env python3

import json
import os
from Crypto.Util.number import *
from Crypto.Random.random import randrange
from math import gcd

class Cipher:

	def __init__(self, size = 512):
		self.s = 2**size + randrange(2**size)
		self.bs = size // 8

	def encrypt(self, m, data = False):
		assert len(m) % self.bs == 0, f"Error: wrong length ({len(m)})"
		C = []
		for i in range(0, len(m), self.bs):
			iv = randrange(self.s)
			while gcd(iv,self.s) != 1:
				iv = randrange(self.s)
			b = int.from_bytes(m[i:i + self.bs],"big")
			if not data:
				C.append({
					"iv" : iv,
					"c" : (b * iv) % self.s,
				})
			else:
				C.append({
					"m" : b,
					"iv" : iv,
					"c" : (b * iv) % self.s,
				})

		return C

	def decrypt(self, c):
		r = b""
		for d in c:
			m = d["c"] * pow(d["iv"], -1, self.s) % self.s
			r += int.to_bytes(m, self.bs,"big")
		return r

if __name__ == "__main__":

	flag = open("flag.txt", "rb").read().strip()
	assert len(flag) == 64, "Error: wrong flag length."

	E = Cipher()

	m = os.urandom(64).hex()
	data = E.encrypt(m.encode(), data = True)

	C = E.encrypt(flag)
	assert flag == E.decrypt(C), "Error: decryption test failed."

	print(json.dumps({
		"data" : data,
		"C" : C
	}, indent = 4))

The key for this stream cipher is an integer $s$ , and encryption involves randomly selecting an $iv$ coprime to $s$ , then calculating $c = m \cdot iv \mod s$ .

Obviously, using the known plaintext/ciphertext and iv, we can find $s$ using gcd, and then decrypt the flag.

from sage.all import *
import json

with open("output.txt", "r") as f:
    j = json.load(f)
    data = j["data"]
    c0 = j["C"][0]

s = gcd([x["m"] * x["iv"] - x["c"] for x in data])

m = c0["c"] * pow(c0["iv"], -1, s) % s
print(m.to_bytes(100).strip(b"\x00"))
# FCSC{96fd29a6fc2301da363a4392cd4a9b9465d65b029a52913add2fd4001d}

CocoRiCo

import os
import json
from zlib import crc32 as le_mac
from Crypto.Cipher import AES

class CocoRiCo_Chiffrement_AEAD:
	def __init__(self, la_clef):
		self.la_clef = la_clef

	def le_chiffrement(self):
		return AES.new(self.la_clef, AES.MODE_OFB, iv = b"\x00" * 16)

	def chiffrer_integre(self, le_message):
		le_tag = int.to_bytes(le_mac(le_message), 4)
		return self.le_chiffrement().encrypt(le_message + le_tag)

	def dechiffrer(self, le_chiffre):
		x = self.le_chiffrement().decrypt(le_chiffre)
		le_message, t = x[:-4], x[-4:]
		le_tag = int.to_bytes(le_mac(le_message), 4)
		if le_tag == t:
			return le_message
		else:
			return b""

try:
	la_clef = os.urandom(32)
	E = CocoRiCo_Chiffrement_AEAD(la_clef)

	for _ in "FCSC":

		print("0. Quit")
		print("1. Login")
		print("2. Logout")
		print("3. TODO")
		choice = int(input(">>> "))

		if choice == 0:
			break

		elif choice == 1:

			new = input("Are you new ? (y/n) ")
			if new == "y":

				name = input("Name: ")
				if name == "toto":
					print("Toto is one of our admin! Do not try to outsmart the system!")
					exit(1)

				d = json.dumps({
					"name": name,
					"admin": False,
				}).encode()

				c = E.chiffrer_integre(d)
				print(f"Welcome {name}. Here is your token:")
				print(c.hex())

				logged = 1

				print("This challenge is still under active developement, please come back in a few weeks to try it out!")
				# TODO: Add vulnerable code here

			elif new == "n":

				token = bytes.fromhex(input("Token: "))
				x = E.dechiffrer(token)
				d = json.loads(x)
				if d["name"] == "toto" and d["admin"]:
					print("Congrats! Here is your flag:")
					print(open("flag.txt").read().strip())
				else:
					print(f"Weclome back {d['name']}!")

		elif choice == 2:
			logged = 0

		elif choice == 3:
			print("This challenge is still under active developement, please come back in a few weeks to try it out!")
			# TODO: Add another vuln here

except:
	print("Please check your inputs.")

This challenge uses AES-OFB combined with CRC32 to create an AEAD:

E_k(m)=\operatorname{AES-OFB}_k(m || \operatorname{crc}(m))

The goal is to modify the JSON within the token.

However, OFB is similar to a stream cipher; XORing the ciphertext directly results in the same XOR operation on the plaintext. Therefore, we can directly tamper with the JSON. The subsequent CRC will also change due to the modification of the JSON, but this can be handled by XORing the difference (XOR) between the original and modified CRCs back into the ciphertext.

import json
from zlib import crc32

from pwn import process, remote


def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])


# io = process(["python", "cocorico.py"])
io = remote("chall.fcsc.fr", 2150)
io.sendline(b"1")
io.sendline(b"y")
io.sendline(b"peko")
io.recvuntil(b"token:\n")
token = bytes.fromhex(io.recvlineS().strip())

orig_json = b'{"name": "peko", "admin": false}'
new_json = b'{"name": "toto", "admin": true }'
patch = xor(orig_json, new_json)
patch += xor(int.to_bytes(crc32(orig_json), 4), int.to_bytes(crc32(new_json), 4))

new_token = xor(token, patch)
io.sendline(b"1")
io.sendline(b"n")
io.sendline(new_token.hex().encode())
io.interactive()
# FCSC{56e8ee27c9039b13a2b896da9a95a266cadd9a6e06e6d1f140f3df6cbed6332c}

Problèmeuh

import sys
from hashlib import sha256
sys.set_int_max_str_digits(31337)
try:
    a, b, c, x, y = [ int(input(f"{x} = ")) for x in "abcxy" ]
    assert a > 0
    assert a == 487 * c
    assert 159 * a == 485 * b
    assert x ** 2 == a + b
    assert y * (3 * y - 1) == 2 * b
    h = sha256(str(a).encode()).hexdigest()
    print(f"FCSC{{{h}}}")
except:
    print("Nope!")

Simply put, we need to find a set of integer solutions that satisfy:

\begin{gathered} a > 0 \\ a = 487c \\ 159a = 485b \\ x^2 = a + b \\ y(3y - 1) = 2b \end{gathered}

First, since $a,b,c$ are all integers, and $159,485,487$ are pairwise coprime, we can set:

\begin{gathered} a = 485 \cdot 487 k \\ b = 487 \cdot 159 k \\ c = 485 k \end{gathered}

And $k$ is an integer, so it becomes:

\begin{gathered} x^2 = 313628k \\ 3y^2 - y = 154866k \end{gathered}

Since $313628 = 2^2 \cdot 7 \cdot 23 \cdot 487$ , we can introduce another integer $t$ such that:

\begin{gathered} x = 2 \cdot 7 \cdot 23 \cdot 487t \\ k = 7 \cdot 23 \cdot 487t^2 \end{gathered}

Then substitute back into the equation for $y$ to get:

3y^2 - y = 12142578462t^2

Clearly, this is a degree 2 Diophantine equation, so I used Alpertron's solver. The solutions obtained are recursive, meaning there are infinitely many solutions. However, the problem restricts the solution to be less than $10^{31337}$ . We can filter the solutions, and we find that only one solution is small enough. Therefore, hashing it gives the flag.

from sage.all import *
from hashlib import sha256

k, x, y = polygens(ZZ, ["k", "x", "y"])
a = 485 * 487 * k
b = 487 * 159 * k
c = 485 * k
f = x**2 - a - b
g = y * (3 * y - 1) - 2 * b
print(f)
print(g)

# x^2 = 313628*k = 2^2*7*23*487*k
# 3*y^2 - y = 154866*k

# x = 2*7*23*487*t
# k = 7*23*487*t^2

y, t = var("y t")
assume(y, "integer")
assume(t, "integer")
k = 7 * 23 * 487 * t**2
eq_new = 3 * y**2 - y == 154866 * k
print(eq_new)
# solve on https://www.alpertron.com.ar/QUAD.HTM

# solution set 1
P = -1044367725401670913368770806206355645862583128125839466135370989973399040239683155631954841643503043141463068663080447478306913405108832340878812443327122987475510822438988378566093716632789394745777535060243506246204856199921161910156256913906235018718600544390679175845674767570538535632148138127650352607259334670703570116509889501587858031309438346424055470372940138923784280073728086061967072783147866095947961038031740809373508129519564289241969009349201697080959230655586476914831337664261523174565899870468060823006346511403114524649745203919486401775624848288821256486642025577796974245321128359432163390007591946540718196389260856173189824995830971025686926741585539857160535919825086379117015737117323265861705240088529133358143684841353115997065720768120701584253547055324557834569078693423495023154345910910063874996456260262914600786438081349105719251434182149396495372823249792023069779416930770030817939588950714635453392636351333533114033630459022300486981923896832504227892127574998777766773929567517524233946575688049479393259668527432627319269119187393399543611055941374641608365712623099700702271839804118087241778435916777117989044604485625553898918357913583188619534035213972303104875388634934958394412961411045210926253231295697075259071821461090011864763188248245307298871946470946246485405498877952625076219879449111881356652709012695793640773263167614179740456526516734164215684716033088585890086274479034108110164833526730305761148543385067637837193917520179592247774430624713490705421576029480326309792239635710246403997325010965002703325268828349855216186677572852672737932040243039086452422633777293500750733402473270860974341861620071685955013606646408984286028054431841464525648666257952885606208881953530556756106037470432943097444571088319931152225451439010796142526119072564114960701645257225855229572517165549706082922334511829086958472908843531142025792262385036801499733168561351882531317829996518500726840070410381981573227452691514908257821062416346769207791671309612681663166525133882972656932501352024810206329429781494063170006956696350421588666589933837473290337169013853375703378405955372882681609666174616757980840962019864971128611911748073505833550196114658178111431516262539434063761518061246179133826757568466191942186170270257326524726784345666582333886961260881087988840728718481373793351462300223433649354968355314002593908111136809233683095335183589616210863781473802169282843813998499732882596408384494056015456697360836036758169558553442657849954042504101958344359120024913002096917094182605808387399273173141427458408369216541786993309136348130708652135808106321257738426118122908456855913693111981476978189303825348742111330353974989943689777682323036880503183331113307753352593919006449580452423189827717405271783228004016074092686329615338353513165881814286501249411681503179215398633977028202732387262789747936496207558242134826694899877824377071602892927615550721904650347516665585900258048076843422428601898283035289107801261509366056112445296291833647377863391962115367353710510011625856916343652677391001541778435466081952289022726543401813227247678250175794943273986038416046190718804439148020805642770196340355392275603204488836889756209950291878899481277603822485617244994678481003732552750686829267773816224018848436636386728536709557844576117899908125993375593337193272450337920987039640943147888222861026325612077288846163459680778288008511878405691610203461085279954860352560393555433656101306550807316344100383487967186493220950750966876753053665754702796245333638773091088623263991334373779113573271032589016691738351137395949107686429942117443302503363246819995901300359632904569798984452624872163152349319513786333308853295944712272889859389407764680868424225934033591688659627870034705426823882439541796170837572668056345353202186888752886102044289386501064962278497535316995790595601752603801308631683815224108668466365714575350366343932561654633557889479694957113983174935546481567607508930416217853669802041819989388038122714764517865238569193573156041430127069474735213387089952139258392084070219738531361605631971208833042641274368087364324758916872081662471940385985728037754443435202369919939860954658761673803731345925703661220099069495003858316266756695260625519135141988792625820814987471417879665549022990914453511819865794087052004861027282953342354628443101539175102137198467552898956546567313365568644195413467075546233501491630942325627100476633319401572892368087250875441255688529789810913165294811799623977476427601193024150704552694189240374816145137672458249710445315111996754757490747525440199189579295781129922052282873884219767802000686284708261160855357454286985870129445515666975378289123788130680710189591525092991530577128363032187801806068370383079593758376839841745093520908995143997776282527424443874789239170031626366914321087897676608450894233008128605921843098448973286564382756618573544790698548144828381638309883259756425384775259560586243077330374723388840131061096526949162512387046525195389845813107629178187185655167780886761023333410044594602020424682115469119270842065684966399144410421279851463713020860526092474867625616872201439424141573158916906413360616843484114749231132666017482896262311968806345594809928760708440733334114646548471380538000572062323463637329915950013061767413625699299368917642896641999038840953839459194165058515798828967180146288366585301971339492687960536835804154290786581568562285021140557563239820168808585213688516828420317233748252289804430736110277772172413473183383755950650868926769817030386151313119977349229134983066223827979462607831963967208809101484330947413558606721749124037600372044677573362825266650265151515521844111265403903546744195108825927850261845366682535987560818043781052967331801382241922644174161770780990405915781228274972253263293429158294460345032998220908522746885099921324151963697456843100600158254873172652127896144304740375407489496249952934597073537993428558769058248172711086390674071298071119627343558012008895870908194529132575756028719985692085302056276757838345675917610852289326316037341330080684087837980577916815225632668466574663707705114748952617228452142037740846022169337714977194537580873254276756818359335948985128718162330937290446866305604955324071693656007398791104819374385332274033494839035536193355508857698824558879703945920938072521650458897463746976317539764747337087451626923283339264575377496748129635567837219010309741361032904075131330801203864703574262706125847566659202325754512710228309943807075325450087161353116228739761135617570884711442954984367280906905324002937320975751937773432033621219426320418072508926136160850995658748270995975145807833433129652612254601125819086650386213092418480233849766221993337893068825622284422392862405221735259696847402294995598700018859032328146639342105849601875786982587573950504742287739433315021642663305257934776618228522516939213499028540303587743601055905243312852559713443369728180729842540259629552800200598537198554535970613196513551114944488058042665507926399776353911929753836021380042917432299802319399903702935316356523186834335606104738561602449890771632146410192045978749496029817788021868813954471431993705234508565863843386214179170691603617733207061939188102052420028404185082381678167062736263440976800322875505514380562246122288757699536796545708270334754393462837138040625385660105408116168210194135079158823243020250838304458366589248480633275374763658336966037967217131527827195243117870642013877305688495982879382035684542631352967233354150721736896078656143340936790540900182504975372972265710936797283775115977024793742300761144906384451302762429445858390762517912661464347804414067464558777723036394398408868475829665241495033257597659698844566511106660361413038683426466649570553212650882739305020982893033738344814685863962209654474119747566464407105677721194842135758757144619378449119454529028955202801170279296074442921206696001174997169004520624187151364450779270561729302549035804031523855803033933169474913992921273547193014048209810699603910595749905713702377137440738440644757152387656863166852193946529479458080459288960623221274493737882825511302124819026158723312252119694832606769436311573632387026216011394749010590611323943605570665258674640087729501475103525463621515694511050710226928685586356845910444653118798780876925636557304207322410457867205652123566153746320791277244117147271829853329986925136768961703955134912170980186186672582091975965889258872539880877613221175480590133946988590989110292064635208992773611256344474279877422565049086503741303952848353818062921906781504328109010806802529940013496923894439125165789631273166133503995625164858036123987156396110660101956428962317412104791949561335673750596885492472231963112060918679681994534207124590627853826632832731582424834921878964918635269901036179834742259257777244465025670082427120964786380985733090427743456993029526423618865948661773031355474030130197351293417192814141397597438021681353595666044142893533324211075045096529513245080419855403087383061228083219455078027572436087023366358834800906504996947071147002481691057100719445651438671004042299061249
Q = 16415669896999432386860905943686280324940796754304097014834369220232907194870242322230403395466921202572623379274597506756920983369629445663248380041753704562284161550040680375316457242460605900970143875285823019188204847402797749363173064853357161255402103155919226573821866714493265602393230087991790449883939417692100242658040419004844427410778807779486732049944967014214598999046791039305975095966226059776852439002101952045622445255353428479566098049628109838645731754808020971797987305692119040919439495318257745661296448531283285567914280267059698063966367445181514253910682714783055631879670228670141003661892448618382990101283218142791813176622534730478412232419852308563645069849519207222856663646599262300599245753206904239573751447078821700516086083855602091003378070576773377849167890854905021239935403080614949689726537253334303322740661048611123733764133640214579848791837947517160972999820567553983893910042030323782770747303316587458061296977838452539595033938261941136809791844112807217398478139643816764418486060403146843875766014450655039796239946816709474572470071131979246843585685487767554327930846382506866696466908574856437502866401603403032144812624969615320261239393776593206083924161399085621715313181462443392373678576315707460408634264489635873530005162888414140110564762918950731669373964055162639825249219731863138325848465833751129746646373415471458164711763747721489690255885132882129240290935290749780882842491482953419332275002168903218025584827089613615446741660832668007499880430028302578654882954094708077936406548861020737667020892125869704394603055475930328463356828300564922641519726944317896025181958145000434908658258394789164418756502045219181313486343095606811194895873965454794687686260693762211802672705133396950554550943169330074310766779916185661621451632233115673497352625572145638430801136743982864362025467192114581379597871521391496154205371046119090745005214500997503871148818097114090073012259933133434656858157632674144100020387474345646158326932629340437682711601213270073085178518172519378897329239099433454640382547662233913947264004531009530001886855335548915042461284848572941180504704649325218901114322779157795445690535967199285765518709488639906142080791737955365633101616961462051980583478241502155315147427601872521015134558280079382090416217299384821876288536163757794782503097269856587623323826356320024046910008165613209070934825578872026329866465131224752863382539488437296475197221263184716032043664618516196442913305789608874497996122229948347307082793322713457627448231422419646618317538080471260220471033027685158844414056704985829921531236714406111190145863985447615785613995726341957429463186124504584103907939412710070772787413644589407636442825912940343007328596255090630059177611819139532447217304007020381782620768502173120290713566821109641523282955045361087928922631755274521873320569836305022293164521305698810770195321904110744531833621243209897898156124760017959269143889488952768272792967527373115593885661964594234479895746568122999650748362051032670410717353559957538659409843438965915659366224619121272010654509596251312225018375461102315666374811135288435367547830399060930756718719962579713281869998774395188621827930913619879424171670094873695839328504599891924759309264244221891935787281871029218393933289253343227232407538600869613721907155714017775697260482718363654562193599753034763142476339275457804935231454823595488271598299540767737721643136549274237029864951291443043038746088057336445549764313492203822167720571247216720503779083619226712562369155438970489434493753055269668063131073057945968931476438125517509378463707201060836116730393244932731761993418754184219080579534031211866883079673793082566271237583764465971589208688188805618082022420947288092216719024227202885790457255179255370473997852175520593074352694128831822933624569874333069034070378054481857253136530077455127651598363611575659530034566846666884786638579324792941836128676291070103744913500459277347901346522671516410671069710843572588415703262677224986497678778126921657637133804107183880035229499297726613921626978945842520890113740605531387226875593127781482808042959356104030668543741297644137938045216147836595935644529362175784406573118150773459938622202668743165222043457392426296012275512694601557032716522102300942164143892986895514452009268588985857888296755649340806749025538427487349412567466288891951290216229126542590225579263006731878209413126090485885911034750350427918412366480785758945793685750986676340854790227903469766615810170468649855425875608903677915664716661179328127534034910534295928678291300931267292664606829533511534152388628733510401177956210181395504240091479999514344249805109286645846568735133154036519757480403310131673446887283391793621681038963030366766257483775475476391809980169777443730889396447267496999334286683455943920679284349679778179383070027901184685744157474642869604671574683616681748343772964678850037277032889974360177092674767093307173744675358764505061278665864990542405326576258839231470485324304128508195604605435131044523046950861707438577792407607409054861916643099312197148812453995129851452709944901390512504780157429807596546545990696123464314768818846686150105841284285482597691682963700924872199649404425654588216844733343049644479420371168955407897561407512895711935628566015940376005277689487856105210173820012616044810047461866209463645009185967234055019890445791678247965516252669806289451907614749112822853538076378816516116809743313290252470110873660647262354841657512846453888501506329058393845620760143612277687274608224253292136745977957019270650825936120833718777596701638648088129223709922852221039567624097619260781429742671278547064708486752902556353480807633059315378910382072286415206349614478467247810592427921232047568107162890117777749729316701356693050008206673481865384303745846773072630598782954353035323051182985149579290999374395193419418348316114665544136879262522824532646950348380667224528284609076033698149597116451387941340348204516771102712634019852786116102806081729342343328789891098486468920621005675705447906539614647734942415012597819766233862127520231496592445219233226382903112339755855496493705719162778769017747821940581264634596915623793674999116826850447126364730529844845807374049441117628601201806521857276485978826629235399610010923477997366854124995094649651948565561253606954720870794854471223256682660814050868758937305129677606486448605304077779916736404690290679790010524595862978552970065038572152827450783033325791826953717313035849660060269502919861633242643403431273094769760687054275400322245651420542829686018113518246831894096381439944073601386436130015153512047504646118140210601857000343315221154903409218726170663426654708441149554619046370628512786118675708791958457182318829535262450494672313361067724997532420356367357096051297596005756536388538668767540269040438508830609645556367472322289163181518442658133244382401877761126610429889883502593895285584496602105001862015745679773824426948838907219146011836182694217612917062864676942972877938811063310696958142680920186796695728183437144907150882251143852289256878864316307227677686696012854605127064848649247175810239142831564649265844335377309405324908369893037114833597618505666612061507567351628214729894671884208820080336953911810696072828085294842085590528905840815443561593272399101363156413359171890096452146637064288457828944721476186632556816071440446048595996917556852098301554605446275525871195787239404043117933067638313558301830440690119199057118847204289284910110667213781553713312677084907949835017852305047872200876120381245630965790984194886222843338259093176700708417290487261001847293514761955160283468523086144597662177674162387123214897999448458484305440727522405570708215443370653754939485809315763963120856527417811232331954860066410672607887239061994159019571778602436948958439740692440688276087184604653073803734398229517879039987457835667534256661928114036570640414190599096385084615310136514590410689519567144575135148480344793543040070871780085731642911859858747779196211915947659362229147096736143814866231592854724165583916316226115670034075412042058990702949622661797649983552158429261236025209880893664633599587081954673569064738334563195659388323177823448771671188803089286068643462961806382111414034062197214348886536076318866550439448364327752786724373445823837218521423279836375763496948872592680728599870093339898208121812499298712700471342721672965059230736621980642085641095858190858590784898043101594927394314508544316944982152903600226872967154212113563912510199996226236338450862810496156787224649200134328547885067972624594650411684812399988552225998566411989568532579039679658694777178968670857739027922595705062002917057983992550936549420321519737761541797614056637784678911230748654227680816246013094215236783652845074571381049592563102905266174217272871283709075169911559551709825749764576944142837957091053236999834771650191964230373888165035034886988124520251585411053916590166945509200681161757988254690250869659197111679098716373166548664792802245966472479662328588091056208565930748443518174424716224618309014314400
K = -2735944982833238731143484323947713387490132792384016169139061536705484532478373720371733899244486867095437229879099584459486830561604907610541396673625617427047360258340113395886076207076767650161690645880970503198034141233799624893862177475559526875900350525986537762303644452415544267065538347998631741647323236282016707109673403167474071235129801296581122008324161169035766499841131839884329182661037676629475406500350325340937074209225571413261016341604684973107621959134670161966331217615353173486573249219709624276882741421880547594652380044509949677327727907530252375651780452463842605313278371445023500610315408103063831683547203023798635529437089121746402038736642051427274178308253201203809443941099877050099874292201150706595625241179803616752681013975933681833896345096128896308194648475817503539989233846769158281621089542222383887123443508101853955627355606702429974798639657919526828833303427925663982318340338387297128457883886097909676882829639742089932505656376990189468298640685467869566413023273969460736414343400524473979294335741775839966039991136118245762078345188663207807264280914627925721321807730417811116077818095809406250477733600567172024135437494935886710206565629432201013987360233180936952552196910407232062279762719284576734772377414939312255000860481402356685094127153158455278228994009193773304208203288643856387641410972291854957774395569245243027451960624620248281709314188813688206715155881791630147140415247158903222045833694817203004264137848268935907790276805444667916646738338050429775813825682451346322734424810170122944503482020978284065767175912655054743892804716760820440253287824052982670863659690833405818109709732464860736459417007536530218914390515934468532482645660909132447947710115627035300445450855566158425758490528221679051794463319364276936908605372185945582892104262024273071800189457330477393670911198685763563266311920231916025700895174353181790834202416832917311858136349519015012168709988855572442809692938779024016670064579057607693054488771556739613785266868878345514196419695419896482888206516572242440063757943705652324544000755168255000314475889258152507076880808095490196750784108220869816852387129859632574281755994533214294253118248106651023680131956325894272183602826910341996763913040250359219191237933645420169189093046679897015069369549897470312714756027292965797083849544976097937220637726053337341151668027602201511822470929812004388311077521870792143897089914739549412532870210530786005340610769752699407152217631601479082999353704991391217847132220452242937908038570403274436386256346745210036745172171280859807402342784164304986921872785734351865024310664241269297602332621056992904910531020750764017317989902118345128797902274098234606073804318823390501221432709181771676529601969856588741202884001170063630436794750362186715118927803518273587213825840893514654820438625879086978886761639384170382194086884283135128365886984018457421972270207201649649692687460002993211523981581492128045465494587895519265647610327432372413315957761353833275124727008505445068452892259992923109901640573160985943227704103186878668442418266041885370836395910183719277729135189214739227924638399843488459453119993763285546978333129065864770304655152269979904028611682478949306554750766648654126551544040703648655964546978504869732322214875557204538734589766811602286984525952336295949543413786393942427032266625505793857079389879242967489205242470599248045266383256794622953607189424879039504977491881907173839791014676222740924960718915367303694620095207869453417296513936537785427061525906495081572415625509211611343855178842990994821912739687586251563077284533510139352788398874155455293665569792364036513429922338535311147179945632180427711872930627410995264868114698134269680337070157881348702786504037867147631742875863209228412332975362586765512392115688138637155604094979055511505678396342413642875522755012909187941933060601929276588339094474444480797773096554132156972688112715178350624152250076546224650224420445252735111844951807262098069283877112870831082946463021153609606188967351197313339204916549621102320271163157640420148352290100921897871145932187963580468007159892684005111423956882940689656340869357972765989274088227029297401095519691795576656437033778123860870340576232071049335379252115766926172119420350383490360690648831149252408668211431497642981382792608223467791504256404581224902094577714815325215036038187757098370929877167788646368235521015080980985172458391737986402061080130959824298947625164446056809131704650578294435968361744774975904312601483946319277452776863221354589005818422382654779715216821877882110767804922251922358731438122251733529659368363565917373348579999919057374967518214440974428122522192339419959580067218355278907814547231965603613506493838394461042913962579246065301663361629573955148232741211249499889047780575990653446547391613296363230511671316864114290692912440478267445262447269446958057295494113141672879505481662393362848779127848884528957445893127417510213110977498423734221096043139871911747554050688084699267434239188507420507825143617906429632067934568175810319440516552032858135408999188308575451657483565085417463359571634599424424331782687244052461469807781025017640214047580432948613827283487478699941567404275764702807455557174940746570061861492567982926901252149285322604761002656729334212948247976017535028970002102674135007910311034910607501530994539009169981740965279707994252708778301048241984602458185470475589679396469419352801623885548375411685145610107877059140276252141075648083584388176398974270126690602046281212434704042215356124329659503211775137656020138953129599450273108014688203951653808703506594604016269876796904957111879757844118081125483759392246801272176552563151730345381069201058269079744541301765404653538674594684527148352962958288219450226115508334701112246977564050624307795512105099797159058839220508530497524929881833229065865569903058052685777590689479877087137422107825058063444537421380768179338949691599519408564656890058034086128517118772336642131019350467680288223723888131648516414411486770167612617574651089935774622490402502099636627705643687920038582765407536538871063817185389959309249415617619860463128169624636990096877439099485937298945833186137808407854394121754974140967895674906852938100200301086976212747663137771539233268335153912999561142354165849108275324760926875601159120145132475745203876113776802341811459822884188279601081074767550679629986122734115048446631668420765977163092161677506428692137908463838887631971158952885505974943343378250486643605540440567238545515794960114509045900053707608570090471614336352253041138649016063573324012266897739355002525585341250774353023368433642833390552536859150568203121028443904442451406858259103174395104752131019779284798659742863719804922543741749112052226844620832922070059394559516008549599334292756064756444794590044840073084805101607592727912053714860530253073776355540730400312960187768404981647250432315880930749433684166977002624279962304071158139817869857668639363782369602152843810779490495479656468510551782826357113486697799449288030572857484525147041857308714876146477386051204612947782668809100854510808108207862635039857138594108210974055896218234220818061648839519138932936417611102010251261225271369121649111980701470013389492318635116012138014215807014265088150973469240593598878733183560526068893195315016075357772844048076304824120246031105426136011906741008099332819592808683050259100907712587645199297873234007186322177939718926383638406781686533176186474534048214151685111202296925618885446180817991639169642050841312033479353396874271827631830699147703807223043182196116784736215081210166974548919126992526713911420514357432943696279027064520535816333241409747384240121253734261784702573895108959156580968219293993853476087902968538721992476677735112101314539843665693169928629767072824826406623448740114712681197434108845633955733038252979839997909639277922376110321352339428440069031766516064180769218356085765068448253261190762522524746724132257173345145296680955273818643309791296532701985991276560371524516122690635811038598809120694263986052704352611672345902007009831783824937110299608330592026404876872670868313482277438933264513659112261510789722427199276564720529637241461945198133848214344773910493634397018569005677032869058147756012719811091739908060721292131120728907637306203086903879972729293916158145432113454766645015556649701353635416549785450078557120278827509871789436996773680940182643031809765130816340516932487899052418090719490830358817266704478827859035352260652085033332704372723075143801749359464537441533355721424647511328770765775068614135399998092037666427735331594755429839946609782462863161445142956504653765950843667152842997332091822758236720253289626923632935676106297446485205124775704613469374335515702539463942140845761896841598760517150877695702878811880618179194985259925284970958294096157357139659515175539499972461941698660705062314694172505814498020753375264235175652765027824251533446860292998042448375144943199518613183119395527758110798800374327745413277054764681842701427655124740586362404119370769718169052400
R = 66442853243535688708974162767204270786173493364644144736895435396985277842692080435545253357122768609269825212005794956421829400699974230610519694817129731242234265853750833583047896715482021698863391308362282895579502968172402863319779824422301284884435486310189009468995817264013543382555163773686493183192671057660306051348165074311226472646281725996411212668142288250700879217264107801363776209395959877623177650659697311879110648380476210284612236427598164545503319218053780132332850024348844889802827564321208779277177400977683985519183792611010232593247037210746340220027285068080140106069961431437556351189319458918006317623666934394237170409461530707384714443112878927728631593789085835559858052702791527318781657058778374283048240793946877732341613722120986622753260843009548111775431305372245492654564053239321179272562344640725916404161928553502588687740463775919738110106329394305388402044861584481873617495656440974771852814296298858678531477652962295040898620433632828054046124612342478138780304110005612598367478930566160634489717670273368216007192015600200642551670581288926387384635009151757423214915993436552831038541391852258297588118210457641308009031814993911464076452558765865834643394962215316285578080444270187599376948178827310907016866712942354660049332200545886415680931329625262468669227200319926683416378206432808919522391439702883113576598590188371035162187703640371787429152054027760183499285711158431332393074194139776209911112287599042500453318828790778810275185266301621177954834192412321647331280896507112338442675855291860346843640004143870288533404603487140921937247393181023897366537861114065185852176618200822584634168901900999200300723150185579127028804046601285890811881041181865974003110401904464736928205261129354216233389746203231126431592065505123393332619528909525113387859401763828685445695120144201045633132602874152710698683786985563851157336656396441359989107950559167456007191087274257791492428891642003867945483408486503323204397310235628006861857884699851409290582359549928752677751522062236470158775776003876314239521026228043324767336435082035576705884716319448679580686070957042909004796426988189221954035361192639143159414530917516795266056888031597985998177244540401456884611562791207665469919128362769901885429325584400528182671754467858556207118832265007314654909202573184501303546027785750534234595887588559820523777180934673027162478747759912716389111148946161229266727217486387738072412765370865055472759834613448737775293373138041540961142925316296737794493075417059281994867504963288141651077890857598382387696312378953486500410311318669208806793448329523763619547451556025900289215904650813299443306856019102204453460038381191411472048048208492087999869661408294965363893507014585780804859951569226775355443662489783994876222703176125110212451245031067913367052160488505259766208045071984554732110081238628076453136455409706165839062449095337318605009067558422056654456543341459663651566617895822023654830942694315396282717459287298186054986621427833583775336861074215816195840410435593144853427439524259846345842949210132036960872294248871166587581807809403432329615986436890374483888446386155374277402030269943290818189994067312471478611765660581576783661294494860945236323104165771871036704402002985150989460711953560816347622863184153844161934548873784328683296495512237491555567389953241907923500014611816144690368211543592875798779589441972195095694372773183607667762967037780784096773669440051793100672426777256314940067967395550045322613986686930075945153896786973096351629512842124406820294135240821389008421541332121066769022317147794853994272139236091870727574063625570159777334865583434723662711497468463083524431439743290071264272378234441795850343109608221629209121065998546008619934086628963318501150703957088070238465683620245399034033796106809048791342452583363590222487372252182954150564704021307274931252976621454379097614257835945523899624359562503092716331599397505961555030737576616077570457062329916623031359345796577454410036379989200192991651714759478540795332913721339373729789839799873102589645703515304952868026725135660086868680494888958215662455239549390063675748897995224546889021643992951752567851333440427425731070065228587694430644600026826559544964111120430074627031042685158816699042756876982126988213767883836774009792492464330936139008329004054168176140580799187079251503356093803492527244231704937709532936826819791955118142316842141393792773269246217664865831488013297803839411365175703795142782163622914467725767734871058726904550335388311630445146981122887080341853825536612885301102692549988923424768492663907553942457196371079244998810168975919387629788160650602215649245689240527346922426610139635324389539669540226121460063609418294512724386648758448582639570279467654481460446135395563860038169801589875938922045940221852125706704851331783705971479522743554743133748331311606534519839112302794687115867257575763736522665565689427206198672801626019344087395632838667362390772770776253348205386318927263058049229194131987098712988341543453124370989382713694739963333373616713730028471512349737371022637586209862380978396164277050330561737217383666210024975706400388227112482745650308782962466318440016668946823855726054217188474043360294377779281563149290150855667066734566325117949729497486333906585379034252785955490234788451226754203387152051328703063884800452945486851772629624732481569556536944193324322793113282670290395888790298796464275578109460549949955102568912666036864421259514949721237311956613099864846735260379283382665046631489974754609767768697044081890235342985841222578150607781037403559146562793905129897629653686934639027386754607146983360975489743863527530518135632254172437831850414029474191459711984126603371469413255345772090245546564434885838072489933582388675769290222402858246425555188387676672394982887975290154688313298619335502213032715782416744662183296984456276955968452856660171001364317841358383410162139248822267990912167845835733399976362175277173248571969860806541584307034694188168589774683842924505391935772771321670394200242802003637923788676284447411914987209723041568220146592483903658747610603165643161959096702929194690726050915259199481037702570926269235036124258701283578674190555389762709290967443711173812684753822747729265099232208515072061940944160613002886985885203620430716171728816171957663176069018311828240899971796124923181821988220263758648473842020776545077937063246540307879796312506826237015685893487412622701807385192093475165596022354612972035206638705950029356719326610755003483651192597126989173188900323109302137414356031325922582845008318996462074933818198912570897086878256337229145599687076250084289857555336690765634156558882324486916193142797392146041691657682919938748079179939600326924608910642433631316425988605262292792056855318878278125117145470625515589062967676962185189371348120652496154067225459336505127969746092143587454645177576870920220348486816761918009140549173944126490727429798697063172679487896902272892451743018367972849260177642089443489969987390414595766050744288132846191440602536753626781097535679138557079990427730070832724669584329876534451137468161879516502579071605299534645341846332407276202753494795573904781687718813800009523523735524631713603576730116583658872644202090746401851716763976616142727572281083703868502659679945809093472635064083220947003646122960853312462979818395110883458900940122737835118252503514740649785321244402951032853768584106107323893177797687525139679462534766603267561220673945690661655630464582171147897388878480921405639754742261590448955095638957144142432271287826202620012683848348461019060749311193004308801162815113598595422600901026923054063471392767151924285120215209913290209469869143724168436798309709426989195875500517411485222358257605209048298557706066207374285154986786271786026951771773661119045247909485631755891224052471559466317107239703424910224957647421836578952530102777630914179544965842583547396835970806364115089863431621712426958731558868906803185011523543477535186911141495064381986084827524600963705432615152710127776406383500575582656727971672537752292154301448560312881031442668057084964165031065586411710403996256332497399155877812082713322053728310936597193513704444801697818310968775841360022255639041634680066044789390087783062335547365152406539427447949100032313285511235083218604073934442191743325619061019689037979750003795659209070771308795646313689727793468868711964565598152260123345443343248575269917458217677124747742219044234779302880642940548959028668192256480913554035602276496392880865063069349140312776380711018875110793654005265802871189781145393537174435324116319033717810789064175622348904135078034043316328823242403806526998416482944363256860973264890227617061841207069039470792513698699506986840774519806097062636987137730095837745138125870202904458224475932425075488035877369031152474035140954784524163533743109967736163191731932769714343070793546650372031386868283126994611205568102835211174782604636830562079283603563766845376162410909668219629518662646081499238368554508048840442937654683537677934602758372823170744402691494378817600
S = -1044367725401670913368770806206355645862583128125839466135370989973399040239683155631954841643503043141463068663080447478306913405108832340878812443327122987475510822438988378566093716632789394745777535060243506246204856199921161910156256913906235018718600544390679175845674767570538535632148138127650352607259334670703570116509889501587858031309438346424055470372940138923784280073728086061967072783147866095947961038031740809373508129519564289241969009349201697080959230655586476914831337664261523174565899870468060823006346511403114524649745203919486401775624848288821256486642025577796974245321128359432163390007591946540718196389260856173189824995830971025686926741585539857160535919825086379117015737117323265861705240088529133358143684841353115997065720768120701584253547055324557834569078693423495023154345910910063874996456260262914600786438081349105719251434182149396495372823249792023069779416930770030817939588950714635453392636351333533114033630459022300486981923896832504227892127574998777766773929567517524233946575688049479393259668527432627319269119187393399543611055941374641608365712623099700702271839804118087241778435916777117989044604485625553898918357913583188619534035213972303104875388634934958394412961411045210926253231295697075259071821461090011864763188248245307298871946470946246485405498877952625076219879449111881356652709012695793640773263167614179740456526516734164215684716033088585890086274479034108110164833526730305761148543385067637837193917520179592247774430624713490705421576029480326309792239635710246403997325010965002703325268828349855216186677572852672737932040243039086452422633777293500750733402473270860974341861620071685955013606646408984286028054431841464525648666257952885606208881953530556756106037470432943097444571088319931152225451439010796142526119072564114960701645257225855229572517165549706082922334511829086958472908843531142025792262385036801499733168561351882531317829996518500726840070410381981573227452691514908257821062416346769207791671309612681663166525133882972656932501352024810206329429781494063170006956696350421588666589933837473290337169013853375703378405955372882681609666174616757980840962019864971128611911748073505833550196114658178111431516262539434063761518061246179133826757568466191942186170270257326524726784345666582333886961260881087988840728718481373793351462300223433649354968355314002593908111136809233683095335183589616210863781473802169282843813998499732882596408384494056015456697360836036758169558553442657849954042504101958344359120024913002096917094182605808387399273173141427458408369216541786993309136348130708652135808106321257738426118122908456855913693111981476978189303825348742111330353974989943689777682323036880503183331113307753352593919006449580452423189827717405271783228004016074092686329615338353513165881814286501249411681503179215398633977028202732387262789747936496207558242134826694899877824377071602892927615550721904650347516665585900258048076843422428601898283035289107801261509366056112445296291833647377863391962115367353710510011625856916343652677391001541778435466081952289022726543401813227247678250175794943273986038416046190718804439148020805642770196340355392275603204488836889756209950291878899481277603822485617244994678481003732552750686829267773816224018848436636386728536709557844576117899908125993375593337193272450337920987039640943147888222861026325612077288846163459680778288008511878405691610203461085279954860352560393555433656101306550807316344100383487967186493220950750966876753053665754702796245333638773091088623263991334373779113573271032589016691738351137395949107686429942117443302503363246819995901300359632904569798984452624872163152349319513786333308853295944712272889859389407764680868424225934033591688659627870034705426823882439541796170837572668056345353202186888752886102044289386501064962278497535316995790595601752603801308631683815224108668466365714575350366343932561654633557889479694957113983174935546481567607508930416217853669802041819989388038122714764517865238569193573156041430127069474735213387089952139258392084070219738531361605631971208833042641274368087364324758916872081662471940385985728037754443435202369919939860954658761673803731345925703661220099069495003858316266756695260625519135141988792625820814987471417879665549022990914453511819865794087052004861027282953342354628443101539175102137198467552898956546567313365568644195413467075546233501491630942325627100476633319401572892368087250875441255688529789810913165294811799623977476427601193024150704552694189240374816145137672458249710445315111996754757490747525440199189579295781129922052282873884219767802000686284708261160855357454286985870129445515666975378289123788130680710189591525092991530577128363032187801806068370383079593758376839841745093520908995143997776282527424443874789239170031626366914321087897676608450894233008128605921843098448973286564382756618573544790698548144828381638309883259756425384775259560586243077330374723388840131061096526949162512387046525195389845813107629178187185655167780886761023333410044594602020424682115469119270842065684966399144410421279851463713020860526092474867625616872201439424141573158916906413360616843484114749231132666017482896262311968806345594809928760708440733334114646548471380538000572062323463637329915950013061767413625699299368917642896641999038840953839459194165058515798828967180146288366585301971339492687960536835804154290786581568562285021140557563239820168808585213688516828420317233748252289804430736110277772172413473183383755950650868926769817030386151313119977349229134983066223827979462607831963967208809101484330947413558606721749124037600372044677573362825266650265151515521844111265403903546744195108825927850261845366682535987560818043781052967331801382241922644174161770780990405915781228274972253263293429158294460345032998220908522746885099921324151963697456843100600158254873172652127896144304740375407489496249952934597073537993428558769058248172711086390674071298071119627343558012008895870908194529132575756028719985692085302056276757838345675917610852289326316037341330080684087837980577916815225632668466574663707705114748952617228452142037740846022169337714977194537580873254276756818359335948985128718162330937290446866305604955324071693656007398791104819374385332274033494839035536193355508857698824558879703945920938072521650458897463746976317539764747337087451626923283339264575377496748129635567837219010309741361032904075131330801203864703574262706125847566659202325754512710228309943807075325450087161353116228739761135617570884711442954984367280906905324002937320975751937773432033621219426320418072508926136160850995658748270995975145807833433129652612254601125819086650386213092418480233849766221993337893068825622284422392862405221735259696847402294995598700018859032328146639342105849601875786982587573950504742287739433315021642663305257934776618228522516939213499028540303587743601055905243312852559713443369728180729842540259629552800200598537198554535970613196513551114944488058042665507926399776353911929753836021380042917432299802319399903702935316356523186834335606104738561602449890771632146410192045978749496029817788021868813954471431993705234508565863843386214179170691603617733207061939188102052420028404185082381678167062736263440976800322875505514380562246122288757699536796545708270334754393462837138040625385660105408116168210194135079158823243020250838304458366589248480633275374763658336966037967217131527827195243117870642013877305688495982879382035684542631352967233354150721736896078656143340936790540900182504975372972265710936797283775115977024793742300761144906384451302762429445858390762517912661464347804414067464558777723036394398408868475829665241495033257597659698844566511106660361413038683426466649570553212650882739305020982893033738344814685863962209654474119747566464407105677721194842135758757144619378449119454529028955202801170279296074442921206696001174997169004520624187151364450779270561729302549035804031523855803033933169474913992921273547193014048209810699603910595749905713702377137440738440644757152387656863166852193946529479458080459288960623221274493737882825511302124819026158723312252119694832606769436311573632387026216011394749010590611323943605570665258674640087729501475103525463621515694511050710226928685586356845910444653118798780876925636557304207322410457867205652123566153746320791277244117147271829853329986925136768961703955134912170980186186672582091975965889258872539880877613221175480590133946988590989110292064635208992773611256344474279877422565049086503741303952848353818062921906781504328109010806802529940013496923894439125165789631273166133503995625164858036123987156396110660101956428962317412104791949561335673750596885492472231963112060918679681994534207124590627853826632832731582424834921878964918635269901036179834742259257777244465025670082427120964786380985733090427743456993029526423618865948661773031355474030130197351293417192814141397597438021681353595666044142893533324211075045096529513245080419855403087383061228083219455078027572436087023366358834800906504996947071147002481691057100719445651438671004042299061249
L = 174061287566945152228128467701059274310430521354306577689228498328899840039947192605325806940583840523577178110513407913051152234184805390146468740554520497912585137073164729761015619438798232457629589176707251041034142699986860318359376152317705836453100090731779862640945794595089755938691356354608392101209889111783928352751648250264643005218239724404009245062156689820630713345621347676994512130524644349324660173005290134895584688253260714873661501558200282846826538442597746152471889610710253862427649978411343470501057751900519087441624200653247733629270808048136876081107004262966162374220188059905360565001265324423453032731543476028864970832638495170947821123597589976193422653304181063186169289519553877643617540014754855559690614140225519332844286794686783597375591175887426305761513115570582503859057651818343979166076043377152433464406346891517619875239030358232749228803874965337178296569488461671802989931491785772575565439391888922185672271743170383414496987316138750704648687929166462961128988261252920705657762614674913232209944754572104553211519864565566590601842656895773601394285437183283450378639967353014540296405986129519664840767414270925649819726318930531436589005868995383850812564772489159732402160235174201821042205215949512543178636910181668644127198041374217883145324411824374414234249812992104179369979908185313559442118168782632273462210527935696623409421086122360702614119338848097648347712413172351351694138921121717626858090564177939639532319586696598707962405104118915117570262671580054384965373272618374400666220835160833783887544804724975869364446262142112122988673373839847742070438962882250125122233745545143495723643603345280992502267774401497381004675738640244087608111042992147601034813658921759459351006245072157182907428514719988525370908573168466023754353178760685826783607542870975871595419527591617680487055751971514493078818140588523670965377064172800249955528093558647088552971666086416787806678401730330262204575448585818042970177069391128201298611884935446943861087522313828776155416892004135034388238296915677195001159449391736931444431655639578881722861502308895950563067659228813780268277695769459663473493669977495188101985291345584305591699352443029685238586043756572343960253010207696522304459594744365323697695045042887754121130724277763722314493543480181331473454786413562298891910383370572274892494725885667098984685189468205613849222530598269368477296912300361547140635666416622147099401397415676002576116226806006126361593092240442974992340417350326390726520004152167016152849030434301397899878862190237909734728202756964498884856058021784775355968017720209623071019687151409475985615518663579496364883970891457018555058995831657281629613720506146750530555185551292225432319834408263408737198304619567545297204667336012348781054935889725585527646969047750208235280250529869233105662838033788731210464957989416034593040355804449149979637396178600482154602591786984108391252777597650043008012807237071433649713839214851300210251561009352074216048638941229643898660352561225618418335270976152723942112898500256963072577680325381503787757233635537874613041695965823878997673069341031786467406524670134273795032723392565379267200748139481626034991715313149913546267303747602874165779746833955425458447804877962302704003141406106064454756118259640762686316651354332229265556198878741722986831173273490524648037143504387602012881474360576613463048001418646400948601700576847546659143392093398925905609350217758467886057350063914661197748870158458494479458842277625783799374222273128848514770543998555728963185595545172098169448623058522899324851281071657019573883750560541136665983550059938817428299830742104145360525391553252297722218142215990785378814976564901294113478070704322338931948109937978339117571137313739923632695139595444676057558867031148125481017007381564416844160379749589219499298432600292100633551438613969204018111411060952429225061057322093609105592981579949159518997195822591080261267918155069369642278300340303331564673020452460752977539761532262192673571687844912455868897848325356543065347345036623088560267605328534805507106879061347894054126486145346943745323397664288006292407239200394986656643492443126945633955224320950610203349844915833976386044459449210104253189190331465437636802497911902979944258170498485742251969977632347842000810171213825557059104740516923195850356199744592149826091094552227594774032568911179257705583581938490387604516746105553233595482061347875145906875948088298301818860882468633270662912737933532170691784092115698206729136024189612076374951740885851999459126248457920906699864929882630188320342047145647369961300333447714118043526809226242381164311688240919277829229714853964688446785031598587515498588429521393838697966967678061730513265626396139973624182253484832523999629380421237407312464873195005271061152386847982946101408482372168021434320307183074828881094063792769762257465116424690804730273051647209959404230795876593431040512888395787231473355176849421158193752064507754199231640968851271529697864275861296814460170555568340765767003404113685911519878473677614161066524068403546641910618836810087682079144604269478700239904023595526486151068893436140580685791538522111002913816043718661467724265801654793451406788889019107758078563423000095343720577272888319325002176961235604283216561486273816106999839806825639909865694176419299804827863357714727764216995223248781326756139300692381797763594760380836856759593873303361468097535614752804736719538958042048300738456018379628695402245530563959325108478154461636171731025218853329558204855830511037304663243767971993994534801516914055157902259767786958187339600062007446262227137544441710858585920307351877567317257790699184804321308376974227780422664593469673963508827888633563706987107362360295130165067652630204712495375543882238193049076724172166370151420457814183320220691993949576140516766693042478862108687982690717456729234581582708325489099512256332238093128176374695451847731779011883011853271223926335334815978484699088188762626004786664282014217009379459639724279319601808714887719339556888346780681306330096319469204272111411095777284617519124825436204742023672956807670361556285829532422930145542379459469726555991497521453027055156215074477717600825887345282276001233131850803229064222045672249139839256032225918142949804093146617324320156345420275076482910624496052923294124556181241937820547223210762562916124688272594639536501718290226838817345855221800200644117262377117687641261109867054292418785038051657301179220908347860225519371456626855936261814118573825830727880151150887333822886829291989628905338936869904386736345418154356026808499276458045165995857634638905521608768709100187636514441731035515403080038974961036998889648844804270380737065477067536955876616141233715832599783336476505388024439890350974933645964497097928991750790381289905552503607110550876322462769704753752823202249838090050597957266842650873885475426618907228288030121640423376604925466700099756199759089328435532752258519157414676340444251321066629392318654958972670230007152905383300386566650617155886059420531139055934350789760267074981795272024401698674329791582671636298003644802325745238665617539084760977307231035696528448600602955534510323198017008736671400697513730279694510456043906829466720479250919063427041020381459616589466090951378389125732243806189673437564276684234686028035032355846526470540503375139717409727764874746772212562460609722827672994536188587971199207186311773668979550948082663813230339280757105225494538892358453622816013109357223489465090150030417495895495377618489466213962519329504132290383460190817730741883793738240976398460419652110244057967402344577426462953839399066401478079304944206915838876266276616474094418517776726902173113904411108261758868775147123217503497148838956390802447643993701609079019957927744067850946286865807022626459524103229741519909088171492533800195046549345740486867782666862499528167420104031191894075129878426954883758172634005253975967172322194912485665486878924532169008034968449933985099291650952283729522906789740107459525397942810527808698991088246576346743214826770536879082289647137585217020803171026453885375353282472101128239385262272064504369335232458168431768553990600928444209779106681288250245850587577270252615751841785037821447597726140985074108853133130146154272759550701220401742977867608687261025624386798546207352857878638308888331154189461493617325855818695163364364445430348662660981543145423313479602203529246765022324498098498185048677439201498795601876057412379979570427508181083956883992141392303010486984463584054684835134467088323335582820649073187527631605212194355583999270860809672687331192732685110016992738160386235350798658260222612291766147582078705327185343486446613665755701187431771308971105472121930404139153646494153105878316839363305790376542962874077504278347071186827464396830955515071290576165504921070603144324776962171892579005021699558548902865469023566266239670280225599277674023815588887368512507516088252207513403309233847897176871347203242513004595406014503894393139133484417499491178524500413615176183453240941906445167340383176875

# solution set 2
P = -1044367725401670913368770806206355645862583128125839466135370989973399040239683155631954841643503043141463068663080447478306913405108832340878812443327122987475510822438988378566093716632789394745777535060243506246204856199921161910156256913906235018718600544390679175845674767570538535632148138127650352607259334670703570116509889501587858031309438346424055470372940138923784280073728086061967072783147866095947961038031740809373508129519564289241969009349201697080959230655586476914831337664261523174565899870468060823006346511403114524649745203919486401775624848288821256486642025577796974245321128359432163390007591946540718196389260856173189824995830971025686926741585539857160535919825086379117015737117323265861705240088529133358143684841353115997065720768120701584253547055324557834569078693423495023154345910910063874996456260262914600786438081349105719251434182149396495372823249792023069779416930770030817939588950714635453392636351333533114033630459022300486981923896832504227892127574998777766773929567517524233946575688049479393259668527432627319269119187393399543611055941374641608365712623099700702271839804118087241778435916777117989044604485625553898918357913583188619534035213972303104875388634934958394412961411045210926253231295697075259071821461090011864763188248245307298871946470946246485405498877952625076219879449111881356652709012695793640773263167614179740456526516734164215684716033088585890086274479034108110164833526730305761148543385067637837193917520179592247774430624713490705421576029480326309792239635710246403997325010965002703325268828349855216186677572852672737932040243039086452422633777293500750733402473270860974341861620071685955013606646408984286028054431841464525648666257952885606208881953530556756106037470432943097444571088319931152225451439010796142526119072564114960701645257225855229572517165549706082922334511829086958472908843531142025792262385036801499733168561351882531317829996518500726840070410381981573227452691514908257821062416346769207791671309612681663166525133882972656932501352024810206329429781494063170006956696350421588666589933837473290337169013853375703378405955372882681609666174616757980840962019864971128611911748073505833550196114658178111431516262539434063761518061246179133826757568466191942186170270257326524726784345666582333886961260881087988840728718481373793351462300223433649354968355314002593908111136809233683095335183589616210863781473802169282843813998499732882596408384494056015456697360836036758169558553442657849954042504101958344359120024913002096917094182605808387399273173141427458408369216541786993309136348130708652135808106321257738426118122908456855913693111981476978189303825348742111330353974989943689777682323036880503183331113307753352593919006449580452423189827717405271783228004016074092686329615338353513165881814286501249411681503179215398633977028202732387262789747936496207558242134826694899877824377071602892927615550721904650347516665585900258048076843422428601898283035289107801261509366056112445296291833647377863391962115367353710510011625856916343652677391001541778435466081952289022726543401813227247678250175794943273986038416046190718804439148020805642770196340355392275603204488836889756209950291878899481277603822485617244994678481003732552750686829267773816224018848436636386728536709557844576117899908125993375593337193272450337920987039640943147888222861026325612077288846163459680778288008511878405691610203461085279954860352560393555433656101306550807316344100383487967186493220950750966876753053665754702796245333638773091088623263991334373779113573271032589016691738351137395949107686429942117443302503363246819995901300359632904569798984452624872163152349319513786333308853295944712272889859389407764680868424225934033591688659627870034705426823882439541796170837572668056345353202186888752886102044289386501064962278497535316995790595601752603801308631683815224108668466365714575350366343932561654633557889479694957113983174935546481567607508930416217853669802041819989388038122714764517865238569193573156041430127069474735213387089952139258392084070219738531361605631971208833042641274368087364324758916872081662471940385985728037754443435202369919939860954658761673803731345925703661220099069495003858316266756695260625519135141988792625820814987471417879665549022990914453511819865794087052004861027282953342354628443101539175102137198467552898956546567313365568644195413467075546233501491630942325627100476633319401572892368087250875441255688529789810913165294811799623977476427601193024150704552694189240374816145137672458249710445315111996754757490747525440199189579295781129922052282873884219767802000686284708261160855357454286985870129445515666975378289123788130680710189591525092991530577128363032187801806068370383079593758376839841745093520908995143997776282527424443874789239170031626366914321087897676608450894233008128605921843098448973286564382756618573544790698548144828381638309883259756425384775259560586243077330374723388840131061096526949162512387046525195389845813107629178187185655167780886761023333410044594602020424682115469119270842065684966399144410421279851463713020860526092474867625616872201439424141573158916906413360616843484114749231132666017482896262311968806345594809928760708440733334114646548471380538000572062323463637329915950013061767413625699299368917642896641999038840953839459194165058515798828967180146288366585301971339492687960536835804154290786581568562285021140557563239820168808585213688516828420317233748252289804430736110277772172413473183383755950650868926769817030386151313119977349229134983066223827979462607831963967208809101484330947413558606721749124037600372044677573362825266650265151515521844111265403903546744195108825927850261845366682535987560818043781052967331801382241922644174161770780990405915781228274972253263293429158294460345032998220908522746885099921324151963697456843100600158254873172652127896144304740375407489496249952934597073537993428558769058248172711086390674071298071119627343558012008895870908194529132575756028719985692085302056276757838345675917610852289326316037341330080684087837980577916815225632668466574663707705114748952617228452142037740846022169337714977194537580873254276756818359335948985128718162330937290446866305604955324071693656007398791104819374385332274033494839035536193355508857698824558879703945920938072521650458897463746976317539764747337087451626923283339264575377496748129635567837219010309741361032904075131330801203864703574262706125847566659202325754512710228309943807075325450087161353116228739761135617570884711442954984367280906905324002937320975751937773432033621219426320418072508926136160850995658748270995975145807833433129652612254601125819086650386213092418480233849766221993337893068825622284422392862405221735259696847402294995598700018859032328146639342105849601875786982587573950504742287739433315021642663305257934776618228522516939213499028540303587743601055905243312852559713443369728180729842540259629552800200598537198554535970613196513551114944488058042665507926399776353911929753836021380042917432299802319399903702935316356523186834335606104738561602449890771632146410192045978749496029817788021868813954471431993705234508565863843386214179170691603617733207061939188102052420028404185082381678167062736263440976800322875505514380562246122288757699536796545708270334754393462837138040625385660105408116168210194135079158823243020250838304458366589248480633275374763658336966037967217131527827195243117870642013877305688495982879382035684542631352967233354150721736896078656143340936790540900182504975372972265710936797283775115977024793742300761144906384451302762429445858390762517912661464347804414067464558777723036394398408868475829665241495033257597659698844566511106660361413038683426466649570553212650882739305020982893033738344814685863962209654474119747566464407105677721194842135758757144619378449119454529028955202801170279296074442921206696001174997169004520624187151364450779270561729302549035804031523855803033933169474913992921273547193014048209810699603910595749905713702377137440738440644757152387656863166852193946529479458080459288960623221274493737882825511302124819026158723312252119694832606769436311573632387026216011394749010590611323943605570665258674640087729501475103525463621515694511050710226928685586356845910444653118798780876925636557304207322410457867205652123566153746320791277244117147271829853329986925136768961703955134912170980186186672582091975965889258872539880877613221175480590133946988590989110292064635208992773611256344474279877422565049086503741303952848353818062921906781504328109010806802529940013496923894439125165789631273166133503995625164858036123987156396110660101956428962317412104791949561335673750596885492472231963112060918679681994534207124590627853826632832731582424834921878964918635269901036179834742259257777244465025670082427120964786380985733090427743456993029526423618865948661773031355474030130197351293417192814141397597438021681353595666044142893533324211075045096529513245080419855403087383061228083219455078027572436087023366358834800906504996947071147002481691057100719445651438671004042299061249
Q = -16415669896999432386860905943686280324940796754304097014834369220232907194870242322230403395466921202572623379274597506756920983369629445663248380041753704562284161550040680375316457242460605900970143875285823019188204847402797749363173064853357161255402103155919226573821866714493265602393230087991790449883939417692100242658040419004844427410778807779486732049944967014214598999046791039305975095966226059776852439002101952045622445255353428479566098049628109838645731754808020971797987305692119040919439495318257745661296448531283285567914280267059698063966367445181514253910682714783055631879670228670141003661892448618382990101283218142791813176622534730478412232419852308563645069849519207222856663646599262300599245753206904239573751447078821700516086083855602091003378070576773377849167890854905021239935403080614949689726537253334303322740661048611123733764133640214579848791837947517160972999820567553983893910042030323782770747303316587458061296977838452539595033938261941136809791844112807217398478139643816764418486060403146843875766014450655039796239946816709474572470071131979246843585685487767554327930846382506866696466908574856437502866401603403032144812624969615320261239393776593206083924161399085621715313181462443392373678576315707460408634264489635873530005162888414140110564762918950731669373964055162639825249219731863138325848465833751129746646373415471458164711763747721489690255885132882129240290935290749780882842491482953419332275002168903218025584827089613615446741660832668007499880430028302578654882954094708077936406548861020737667020892125869704394603055475930328463356828300564922641519726944317896025181958145000434908658258394789164418756502045219181313486343095606811194895873965454794687686260693762211802672705133396950554550943169330074310766779916185661621451632233115673497352625572145638430801136743982864362025467192114581379597871521391496154205371046119090745005214500997503871148818097114090073012259933133434656858157632674144100020387474345646158326932629340437682711601213270073085178518172519378897329239099433454640382547662233913947264004531009530001886855335548915042461284848572941180504704649325218901114322779157795445690535967199285765518709488639906142080791737955365633101616961462051980583478241502155315147427601872521015134558280079382090416217299384821876288536163757794782503097269856587623323826356320024046910008165613209070934825578872026329866465131224752863382539488437296475197221263184716032043664618516196442913305789608874497996122229948347307082793322713457627448231422419646618317538080471260220471033027685158844414056704985829921531236714406111190145863985447615785613995726341957429463186124504584103907939412710070772787413644589407636442825912940343007328596255090630059177611819139532447217304007020381782620768502173120290713566821109641523282955045361087928922631755274521873320569836305022293164521305698810770195321904110744531833621243209897898156124760017959269143889488952768272792967527373115593885661964594234479895746568122999650748362051032670410717353559957538659409843438965915659366224619121272010654509596251312225018375461102315666374811135288435367547830399060930756718719962579713281869998774395188621827930913619879424171670094873695839328504599891924759309264244221891935787281871029218393933289253343227232407538600869613721907155714017775697260482718363654562193599753034763142476339275457804935231454823595488271598299540767737721643136549274237029864951291443043038746088057336445549764313492203822167720571247216720503779083619226712562369155438970489434493753055269668063131073057945968931476438125517509378463707201060836116730393244932731761993418754184219080579534031211866883079673793082566271237583764465971589208688188805618082022420947288092216719024227202885790457255179255370473997852175520593074352694128831822933624569874333069034070378054481857253136530077455127651598363611575659530034566846666884786638579324792941836128676291070103744913500459277347901346522671516410671069710843572588415703262677224986497678778126921657637133804107183880035229499297726613921626978945842520890113740605531387226875593127781482808042959356104030668543741297644137938045216147836595935644529362175784406573118150773459938622202668743165222043457392426296012275512694601557032716522102300942164143892986895514452009268588985857888296755649340806749025538427487349412567466288891951290216229126542590225579263006731878209413126090485885911034750350427918412366480785758945793685750986676340854790227903469766615810170468649855425875608903677915664716661179328127534034910534295928678291300931267292664606829533511534152388628733510401177956210181395504240091479999514344249805109286645846568735133154036519757480403310131673446887283391793621681038963030366766257483775475476391809980169777443730889396447267496999334286683455943920679284349679778179383070027901184685744157474642869604671574683616681748343772964678850037277032889974360177092674767093307173744675358764505061278665864990542405326576258839231470485324304128508195604605435131044523046950861707438577792407607409054861916643099312197148812453995129851452709944901390512504780157429807596546545990696123464314768818846686150105841284285482597691682963700924872199649404425654588216844733343049644479420371168955407897561407512895711935628566015940376005277689487856105210173820012616044810047461866209463645009185967234055019890445791678247965516252669806289451907614749112822853538076378816516116809743313290252470110873660647262354841657512846453888501506329058393845620760143612277687274608224253292136745977957019270650825936120833718777596701638648088129223709922852221039567624097619260781429742671278547064708486752902556353480807633059315378910382072286415206349614478467247810592427921232047568107162890117777749729316701356693050008206673481865384303745846773072630598782954353035323051182985149579290999374395193419418348316114665544136879262522824532646950348380667224528284609076033698149597116451387941340348204516771102712634019852786116102806081729342343328789891098486468920621005675705447906539614647734942415012597819766233862127520231496592445219233226382903112339755855496493705719162778769017747821940581264634596915623793674999116826850447126364730529844845807374049441117628601201806521857276485978826629235399610010923477997366854124995094649651948565561253606954720870794854471223256682660814050868758937305129677606486448605304077779916736404690290679790010524595862978552970065038572152827450783033325791826953717313035849660060269502919861633242643403431273094769760687054275400322245651420542829686018113518246831894096381439944073601386436130015153512047504646118140210601857000343315221154903409218726170663426654708441149554619046370628512786118675708791958457182318829535262450494672313361067724997532420356367357096051297596005756536388538668767540269040438508830609645556367472322289163181518442658133244382401877761126610429889883502593895285584496602105001862015745679773824426948838907219146011836182694217612917062864676942972877938811063310696958142680920186796695728183437144907150882251143852289256878864316307227677686696012854605127064848649247175810239142831564649265844335377309405324908369893037114833597618505666612061507567351628214729894671884208820080336953911810696072828085294842085590528905840815443561593272399101363156413359171890096452146637064288457828944721476186632556816071440446048595996917556852098301554605446275525871195787239404043117933067638313558301830440690119199057118847204289284910110667213781553713312677084907949835017852305047872200876120381245630965790984194886222843338259093176700708417290487261001847293514761955160283468523086144597662177674162387123214897999448458484305440727522405570708215443370653754939485809315763963120856527417811232331954860066410672607887239061994159019571778602436948958439740692440688276087184604653073803734398229517879039987457835667534256661928114036570640414190599096385084615310136514590410689519567144575135148480344793543040070871780085731642911859858747779196211915947659362229147096736143814866231592854724165583916316226115670034075412042058990702949622661797649983552158429261236025209880893664633599587081954673569064738334563195659388323177823448771671188803089286068643462961806382111414034062197214348886536076318866550439448364327752786724373445823837218521423279836375763496948872592680728599870093339898208121812499298712700471342721672965059230736621980642085641095858190858590784898043101594927394314508544316944982152903600226872967154212113563912510199996226236338450862810496156787224649200134328547885067972624594650411684812399988552225998566411989568532579039679658694777178968670857739027922595705062002917057983992550936549420321519737761541797614056637784678911230748654227680816246013094215236783652845074571381049592563102905266174217272871283709075169911559551709825749764576944142837957091053236999834771650191964230373888165035034886988124520251585411053916590166945509200681161757988254690250869659197111679098716373166548664792802245966472479662328588091056208565930748443518174424716224618309014314400
K = 2735944982833238731143484323947713387490132792384016169139061536705484532478373720371733899244486867095437229879099584459486830561604907610541396673625617427047360258340113395886076207076767650161690645880970503198034141233799624893862177475559526875900350525986537762303644452415544267065538347998631741647323236282016707109673403167474071235129801296581122008324161169035766499841131839884329182661037676629475406500350325340937074209225571413261016341604684973107621959134670161966331217615353173486573249219709624276882741421880547594652380044509949677327727907530252375651780452463842605313278371445023500610315408103063831683547203023798635529437089121746402038736642051427274178308253201203809443941099877050099874292201150706595625241179803616752681013975933681833896345096128896308194648475817503539989233846769158281621089542222383887123443508101853955627355606702429974798639657919526828833303427925663982318340338387297128457883886097909676882829639742089932505656376990189468298640685467869566413023273969460736414343400524473979294335741775839966039991136118245762078345188663207807264280914627925721321807730417811116077818095809406250477733600567172024135437494935886710206565629432201013987360233180936952552196910407232062279762719284576734772377414939312255000860481402356685094127153158455278228994009193773304208203288643856387641410972291854957774395569245243027451960624620248281709314188813688206715155881791630147140415247158903222045833694817203004264137848268935907790276805444667916646738338050429775813825682451346322734424810170122944503482020978284065767175912655054743892804716760820440253287824052982670863659690833405818109709732464860736459417007536530218914390515934468532482645660909132447947710115627035300445450855566158425758490528221679051794463319364276936908605372185945582892104262024273071800189457330477393670911198685763563266311920231916025700895174353181790834202416832917311858136349519015012168709988855572442809692938779024016670064579057607693054488771556739613785266868878345514196419695419896482888206516572242440063757943705652324544000755168255000314475889258152507076880808095490196750784108220869816852387129859632574281755994533214294253118248106651023680131956325894272183602826910341996763913040250359219191237933645420169189093046679897015069369549897470312714756027292965797083849544976097937220637726053337341151668027602201511822470929812004388311077521870792143897089914739549412532870210530786005340610769752699407152217631601479082999353704991391217847132220452242937908038570403274436386256346745210036745172171280859807402342784164304986921872785734351865024310664241269297602332621056992904910531020750764017317989902118345128797902274098234606073804318823390501221432709181771676529601969856588741202884001170063630436794750362186715118927803518273587213825840893514654820438625879086978886761639384170382194086884283135128365886984018457421972270207201649649692687460002993211523981581492128045465494587895519265647610327432372413315957761353833275124727008505445068452892259992923109901640573160985943227704103186878668442418266041885370836395910183719277729135189214739227924638399843488459453119993763285546978333129065864770304655152269979904028611682478949306554750766648654126551544040703648655964546978504869732322214875557204538734589766811602286984525952336295949543413786393942427032266625505793857079389879242967489205242470599248045266383256794622953607189424879039504977491881907173839791014676222740924960718915367303694620095207869453417296513936537785427061525906495081572415625509211611343855178842990994821912739687586251563077284533510139352788398874155455293665569792364036513429922338535311147179945632180427711872930627410995264868114698134269680337070157881348702786504037867147631742875863209228412332975362586765512392115688138637155604094979055511505678396342413642875522755012909187941933060601929276588339094474444480797773096554132156972688112715178350624152250076546224650224420445252735111844951807262098069283877112870831082946463021153609606188967351197313339204916549621102320271163157640420148352290100921897871145932187963580468007159892684005111423956882940689656340869357972765989274088227029297401095519691795576656437033778123860870340576232071049335379252115766926172119420350383490360690648831149252408668211431497642981382792608223467791504256404581224902094577714815325215036038187757098370929877167788646368235521015080980985172458391737986402061080130959824298947625164446056809131704650578294435968361744774975904312601483946319277452776863221354589005818422382654779715216821877882110767804922251922358731438122251733529659368363565917373348579999919057374967518214440974428122522192339419959580067218355278907814547231965603613506493838394461042913962579246065301663361629573955148232741211249499889047780575990653446547391613296363230511671316864114290692912440478267445262447269446958057295494113141672879505481662393362848779127848884528957445893127417510213110977498423734221096043139871911747554050688084699267434239188507420507825143617906429632067934568175810319440516552032858135408999188308575451657483565085417463359571634599424424331782687244052461469807781025017640214047580432948613827283487478699941567404275764702807455557174940746570061861492567982926901252149285322604761002656729334212948247976017535028970002102674135007910311034910607501530994539009169981740965279707994252708778301048241984602458185470475589679396469419352801623885548375411685145610107877059140276252141075648083584388176398974270126690602046281212434704042215356124329659503211775137656020138953129599450273108014688203951653808703506594604016269876796904957111879757844118081125483759392246801272176552563151730345381069201058269079744541301765404653538674594684527148352962958288219450226115508334701112246977564050624307795512105099797159058839220508530497524929881833229065865569903058052685777590689479877087137422107825058063444537421380768179338949691599519408564656890058034086128517118772336642131019350467680288223723888131648516414411486770167612617574651089935774622490402502099636627705643687920038582765407536538871063817185389959309249415617619860463128169624636990096877439099485937298945833186137808407854394121754974140967895674906852938100200301086976212747663137771539233268335153912999561142354165849108275324760926875601159120145132475745203876113776802341811459822884188279601081074767550679629986122734115048446631668420765977163092161677506428692137908463838887631971158952885505974943343378250486643605540440567238545515794960114509045900053707608570090471614336352253041138649016063573324012266897739355002525585341250774353023368433642833390552536859150568203121028443904442451406858259103174395104752131019779284798659742863719804922543741749112052226844620832922070059394559516008549599334292756064756444794590044840073084805101607592727912053714860530253073776355540730400312960187768404981647250432315880930749433684166977002624279962304071158139817869857668639363782369602152843810779490495479656468510551782826357113486697799449288030572857484525147041857308714876146477386051204612947782668809100854510808108207862635039857138594108210974055896218234220818061648839519138932936417611102010251261225271369121649111980701470013389492318635116012138014215807014265088150973469240593598878733183560526068893195315016075357772844048076304824120246031105426136011906741008099332819592808683050259100907712587645199297873234007186322177939718926383638406781686533176186474534048214151685111202296925618885446180817991639169642050841312033479353396874271827631830699147703807223043182196116784736215081210166974548919126992526713911420514357432943696279027064520535816333241409747384240121253734261784702573895108959156580968219293993853476087902968538721992476677735112101314539843665693169928629767072824826406623448740114712681197434108845633955733038252979839997909639277922376110321352339428440069031766516064180769218356085765068448253261190762522524746724132257173345145296680955273818643309791296532701985991276560371524516122690635811038598809120694263986052704352611672345902007009831783824937110299608330592026404876872670868313482277438933264513659112261510789722427199276564720529637241461945198133848214344773910493634397018569005677032869058147756012719811091739908060721292131120728907637306203086903879972729293916158145432113454766645015556649701353635416549785450078557120278827509871789436996773680940182643031809765130816340516932487899052418090719490830358817266704478827859035352260652085033332704372723075143801749359464537441533355721424647511328770765775068614135399998092037666427735331594755429839946609782462863161445142956504653765950843667152842997332091822758236720253289626923632935676106297446485205124775704613469374335515702539463942140845761896841598760517150877695702878811880618179194985259925284970958294096157357139659515175539499972461941698660705062314694172505814498020753375264235175652765027824251533446860292998042448375144943199518613183119395527758110798800374327745413277054764681842701427655124740586362404119370769718169052400
R = -66442853243535688708974162767204270786173493364644144736895435396985277842692080435545253357122768609269825212005794956421829400699974230610519694817129731242234265853750833583047896715482021698863391308362282895579502968172402863319779824422301284884435486310189009468995817264013543382555163773686493183192671057660306051348165074311226472646281725996411212668142288250700879217264107801363776209395959877623177650659697311879110648380476210284612236427598164545503319218053780132332850024348844889802827564321208779277177400977683985519183792611010232593247037210746340220027285068080140106069961431437556351189319458918006317623666934394237170409461530707384714443112878927728631593789085835559858052702791527318781657058778374283048240793946877732341613722120986622753260843009548111775431305372245492654564053239321179272562344640725916404161928553502588687740463775919738110106329394305388402044861584481873617495656440974771852814296298858678531477652962295040898620433632828054046124612342478138780304110005612598367478930566160634489717670273368216007192015600200642551670581288926387384635009151757423214915993436552831038541391852258297588118210457641308009031814993911464076452558765865834643394962215316285578080444270187599376948178827310907016866712942354660049332200545886415680931329625262468669227200319926683416378206432808919522391439702883113576598590188371035162187703640371787429152054027760183499285711158431332393074194139776209911112287599042500453318828790778810275185266301621177954834192412321647331280896507112338442675855291860346843640004143870288533404603487140921937247393181023897366537861114065185852176618200822584634168901900999200300723150185579127028804046601285890811881041181865974003110401904464736928205261129354216233389746203231126431592065505123393332619528909525113387859401763828685445695120144201045633132602874152710698683786985563851157336656396441359989107950559167456007191087274257791492428891642003867945483408486503323204397310235628006861857884699851409290582359549928752677751522062236470158775776003876314239521026228043324767336435082035576705884716319448679580686070957042909004796426988189221954035361192639143159414530917516795266056888031597985998177244540401456884611562791207665469919128362769901885429325584400528182671754467858556207118832265007314654909202573184501303546027785750534234595887588559820523777180934673027162478747759912716389111148946161229266727217486387738072412765370865055472759834613448737775293373138041540961142925316296737794493075417059281994867504963288141651077890857598382387696312378953486500410311318669208806793448329523763619547451556025900289215904650813299443306856019102204453460038381191411472048048208492087999869661408294965363893507014585780804859951569226775355443662489783994876222703176125110212451245031067913367052160488505259766208045071984554732110081238628076453136455409706165839062449095337318605009067558422056654456543341459663651566617895822023654830942694315396282717459287298186054986621427833583775336861074215816195840410435593144853427439524259846345842949210132036960872294248871166587581807809403432329615986436890374483888446386155374277402030269943290818189994067312471478611765660581576783661294494860945236323104165771871036704402002985150989460711953560816347622863184153844161934548873784328683296495512237491555567389953241907923500014611816144690368211543592875798779589441972195095694372773183607667762967037780784096773669440051793100672426777256314940067967395550045322613986686930075945153896786973096351629512842124406820294135240821389008421541332121066769022317147794853994272139236091870727574063625570159777334865583434723662711497468463083524431439743290071264272378234441795850343109608221629209121065998546008619934086628963318501150703957088070238465683620245399034033796106809048791342452583363590222487372252182954150564704021307274931252976621454379097614257835945523899624359562503092716331599397505961555030737576616077570457062329916623031359345796577454410036379989200192991651714759478540795332913721339373729789839799873102589645703515304952868026725135660086868680494888958215662455239549390063675748897995224546889021643992951752567851333440427425731070065228587694430644600026826559544964111120430074627031042685158816699042756876982126988213767883836774009792492464330936139008329004054168176140580799187079251503356093803492527244231704937709532936826819791955118142316842141393792773269246217664865831488013297803839411365175703795142782163622914467725767734871058726904550335388311630445146981122887080341853825536612885301102692549988923424768492663907553942457196371079244998810168975919387629788160650602215649245689240527346922426610139635324389539669540226121460063609418294512724386648758448582639570279467654481460446135395563860038169801589875938922045940221852125706704851331783705971479522743554743133748331311606534519839112302794687115867257575763736522665565689427206198672801626019344087395632838667362390772770776253348205386318927263058049229194131987098712988341543453124370989382713694739963333373616713730028471512349737371022637586209862380978396164277050330561737217383666210024975706400388227112482745650308782962466318440016668946823855726054217188474043360294377779281563149290150855667066734566325117949729497486333906585379034252785955490234788451226754203387152051328703063884800452945486851772629624732481569556536944193324322793113282670290395888790298796464275578109460549949955102568912666036864421259514949721237311956613099864846735260379283382665046631489974754609767768697044081890235342985841222578150607781037403559146562793905129897629653686934639027386754607146983360975489743863527530518135632254172437831850414029474191459711984126603371469413255345772090245546564434885838072489933582388675769290222402858246425555188387676672394982887975290154688313298619335502213032715782416744662183296984456276955968452856660171001364317841358383410162139248822267990912167845835733399976362175277173248571969860806541584307034694188168589774683842924505391935772771321670394200242802003637923788676284447411914987209723041568220146592483903658747610603165643161959096702929194690726050915259199481037702570926269235036124258701283578674190555389762709290967443711173812684753822747729265099232208515072061940944160613002886985885203620430716171728816171957663176069018311828240899971796124923181821988220263758648473842020776545077937063246540307879796312506826237015685893487412622701807385192093475165596022354612972035206638705950029356719326610755003483651192597126989173188900323109302137414356031325922582845008318996462074933818198912570897086878256337229145599687076250084289857555336690765634156558882324486916193142797392146041691657682919938748079179939600326924608910642433631316425988605262292792056855318878278125117145470625515589062967676962185189371348120652496154067225459336505127969746092143587454645177576870920220348486816761918009140549173944126490727429798697063172679487896902272892451743018367972849260177642089443489969987390414595766050744288132846191440602536753626781097535679138557079990427730070832724669584329876534451137468161879516502579071605299534645341846332407276202753494795573904781687718813800009523523735524631713603576730116583658872644202090746401851716763976616142727572281083703868502659679945809093472635064083220947003646122960853312462979818395110883458900940122737835118252503514740649785321244402951032853768584106107323893177797687525139679462534766603267561220673945690661655630464582171147897388878480921405639754742261590448955095638957144142432271287826202620012683848348461019060749311193004308801162815113598595422600901026923054063471392767151924285120215209913290209469869143724168436798309709426989195875500517411485222358257605209048298557706066207374285154986786271786026951771773661119045247909485631755891224052471559466317107239703424910224957647421836578952530102777630914179544965842583547396835970806364115089863431621712426958731558868906803185011523543477535186911141495064381986084827524600963705432615152710127776406383500575582656727971672537752292154301448560312881031442668057084964165031065586411710403996256332497399155877812082713322053728310936597193513704444801697818310968775841360022255639041634680066044789390087783062335547365152406539427447949100032313285511235083218604073934442191743325619061019689037979750003795659209070771308795646313689727793468868711964565598152260123345443343248575269917458217677124747742219044234779302880642940548959028668192256480913554035602276496392880865063069349140312776380711018875110793654005265802871189781145393537174435324116319033717810789064175622348904135078034043316328823242403806526998416482944363256860973264890227617061841207069039470792513698699506986840774519806097062636987137730095837745138125870202904458224475932425075488035877369031152474035140954784524163533743109967736163191731932769714343070793546650372031386868283126994611205568102835211174782604636830562079283603563766845376162410909668219629518662646081499238368554508048840442937654683537677934602758372823170744402691494378817600
S = -1044367725401670913368770806206355645862583128125839466135370989973399040239683155631954841643503043141463068663080447478306913405108832340878812443327122987475510822438988378566093716632789394745777535060243506246204856199921161910156256913906235018718600544390679175845674767570538535632148138127650352607259334670703570116509889501587858031309438346424055470372940138923784280073728086061967072783147866095947961038031740809373508129519564289241969009349201697080959230655586476914831337664261523174565899870468060823006346511403114524649745203919486401775624848288821256486642025577796974245321128359432163390007591946540718196389260856173189824995830971025686926741585539857160535919825086379117015737117323265861705240088529133358143684841353115997065720768120701584253547055324557834569078693423495023154345910910063874996456260262914600786438081349105719251434182149396495372823249792023069779416930770030817939588950714635453392636351333533114033630459022300486981923896832504227892127574998777766773929567517524233946575688049479393259668527432627319269119187393399543611055941374641608365712623099700702271839804118087241778435916777117989044604485625553898918357913583188619534035213972303104875388634934958394412961411045210926253231295697075259071821461090011864763188248245307298871946470946246485405498877952625076219879449111881356652709012695793640773263167614179740456526516734164215684716033088585890086274479034108110164833526730305761148543385067637837193917520179592247774430624713490705421576029480326309792239635710246403997325010965002703325268828349855216186677572852672737932040243039086452422633777293500750733402473270860974341861620071685955013606646408984286028054431841464525648666257952885606208881953530556756106037470432943097444571088319931152225451439010796142526119072564114960701645257225855229572517165549706082922334511829086958472908843531142025792262385036801499733168561351882531317829996518500726840070410381981573227452691514908257821062416346769207791671309612681663166525133882972656932501352024810206329429781494063170006956696350421588666589933837473290337169013853375703378405955372882681609666174616757980840962019864971128611911748073505833550196114658178111431516262539434063761518061246179133826757568466191942186170270257326524726784345666582333886961260881087988840728718481373793351462300223433649354968355314002593908111136809233683095335183589616210863781473802169282843813998499732882596408384494056015456697360836036758169558553442657849954042504101958344359120024913002096917094182605808387399273173141427458408369216541786993309136348130708652135808106321257738426118122908456855913693111981476978189303825348742111330353974989943689777682323036880503183331113307753352593919006449580452423189827717405271783228004016074092686329615338353513165881814286501249411681503179215398633977028202732387262789747936496207558242134826694899877824377071602892927615550721904650347516665585900258048076843422428601898283035289107801261509366056112445296291833647377863391962115367353710510011625856916343652677391001541778435466081952289022726543401813227247678250175794943273986038416046190718804439148020805642770196340355392275603204488836889756209950291878899481277603822485617244994678481003732552750686829267773816224018848436636386728536709557844576117899908125993375593337193272450337920987039640943147888222861026325612077288846163459680778288008511878405691610203461085279954860352560393555433656101306550807316344100383487967186493220950750966876753053665754702796245333638773091088623263991334373779113573271032589016691738351137395949107686429942117443302503363246819995901300359632904569798984452624872163152349319513786333308853295944712272889859389407764680868424225934033591688659627870034705426823882439541796170837572668056345353202186888752886102044289386501064962278497535316995790595601752603801308631683815224108668466365714575350366343932561654633557889479694957113983174935546481567607508930416217853669802041819989388038122714764517865238569193573156041430127069474735213387089952139258392084070219738531361605631971208833042641274368087364324758916872081662471940385985728037754443435202369919939860954658761673803731345925703661220099069495003858316266756695260625519135141988792625820814987471417879665549022990914453511819865794087052004861027282953342354628443101539175102137198467552898956546567313365568644195413467075546233501491630942325627100476633319401572892368087250875441255688529789810913165294811799623977476427601193024150704552694189240374816145137672458249710445315111996754757490747525440199189579295781129922052282873884219767802000686284708261160855357454286985870129445515666975378289123788130680710189591525092991530577128363032187801806068370383079593758376839841745093520908995143997776282527424443874789239170031626366914321087897676608450894233008128605921843098448973286564382756618573544790698548144828381638309883259756425384775259560586243077330374723388840131061096526949162512387046525195389845813107629178187185655167780886761023333410044594602020424682115469119270842065684966399144410421279851463713020860526092474867625616872201439424141573158916906413360616843484114749231132666017482896262311968806345594809928760708440733334114646548471380538000572062323463637329915950013061767413625699299368917642896641999038840953839459194165058515798828967180146288366585301971339492687960536835804154290786581568562285021140557563239820168808585213688516828420317233748252289804430736110277772172413473183383755950650868926769817030386151313119977349229134983066223827979462607831963967208809101484330947413558606721749124037600372044677573362825266650265151515521844111265403903546744195108825927850261845366682535987560818043781052967331801382241922644174161770780990405915781228274972253263293429158294460345032998220908522746885099921324151963697456843100600158254873172652127896144304740375407489496249952934597073537993428558769058248172711086390674071298071119627343558012008895870908194529132575756028719985692085302056276757838345675917610852289326316037341330080684087837980577916815225632668466574663707705114748952617228452142037740846022169337714977194537580873254276756818359335948985128718162330937290446866305604955324071693656007398791104819374385332274033494839035536193355508857698824558879703945920938072521650458897463746976317539764747337087451626923283339264575377496748129635567837219010309741361032904075131330801203864703574262706125847566659202325754512710228309943807075325450087161353116228739761135617570884711442954984367280906905324002937320975751937773432033621219426320418072508926136160850995658748270995975145807833433129652612254601125819086650386213092418480233849766221993337893068825622284422392862405221735259696847402294995598700018859032328146639342105849601875786982587573950504742287739433315021642663305257934776618228522516939213499028540303587743601055905243312852559713443369728180729842540259629552800200598537198554535970613196513551114944488058042665507926399776353911929753836021380042917432299802319399903702935316356523186834335606104738561602449890771632146410192045978749496029817788021868813954471431993705234508565863843386214179170691603617733207061939188102052420028404185082381678167062736263440976800322875505514380562246122288757699536796545708270334754393462837138040625385660105408116168210194135079158823243020250838304458366589248480633275374763658336966037967217131527827195243117870642013877305688495982879382035684542631352967233354150721736896078656143340936790540900182504975372972265710936797283775115977024793742300761144906384451302762429445858390762517912661464347804414067464558777723036394398408868475829665241495033257597659698844566511106660361413038683426466649570553212650882739305020982893033738344814685863962209654474119747566464407105677721194842135758757144619378449119454529028955202801170279296074442921206696001174997169004520624187151364450779270561729302549035804031523855803033933169474913992921273547193014048209810699603910595749905713702377137440738440644757152387656863166852193946529479458080459288960623221274493737882825511302124819026158723312252119694832606769436311573632387026216011394749010590611323943605570665258674640087729501475103525463621515694511050710226928685586356845910444653118798780876925636557304207322410457867205652123566153746320791277244117147271829853329986925136768961703955134912170980186186672582091975965889258872539880877613221175480590133946988590989110292064635208992773611256344474279877422565049086503741303952848353818062921906781504328109010806802529940013496923894439125165789631273166133503995625164858036123987156396110660101956428962317412104791949561335673750596885492472231963112060918679681994534207124590627853826632832731582424834921878964918635269901036179834742259257777244465025670082427120964786380985733090427743456993029526423618865948661773031355474030130197351293417192814141397597438021681353595666044142893533324211075045096529513245080419855403087383061228083219455078027572436087023366358834800906504996947071147002481691057100719445651438671004042299061249
L = 174061287566945152228128467701059274310430521354306577689228498328899840039947192605325806940583840523577178110513407913051152234184805390146468740554520497912585137073164729761015619438798232457629589176707251041034142699986860318359376152317705836453100090731779862640945794595089755938691356354608392101209889111783928352751648250264643005218239724404009245062156689820630713345621347676994512130524644349324660173005290134895584688253260714873661501558200282846826538442597746152471889610710253862427649978411343470501057751900519087441624200653247733629270808048136876081107004262966162374220188059905360565001265324423453032731543476028864970832638495170947821123597589976193422653304181063186169289519553877643617540014754855559690614140225519332844286794686783597375591175887426305761513115570582503859057651818343979166076043377152433464406346891517619875239030358232749228803874965337178296569488461671802989931491785772575565439391888922185672271743170383414496987316138750704648687929166462961128988261252920705657762614674913232209944754572104553211519864565566590601842656895773601394285437183283450378639967353014540296405986129519664840767414270925649819726318930531436589005868995383850812564772489159732402160235174201821042205215949512543178636910181668644127198041374217883145324411824374414234249812992104179369979908185313559442118168782632273462210527935696623409421086122360702614119338848097648347712413172351351694138921121717626858090564177939639532319586696598707962405104118915117570262671580054384965373272618374400666220835160833783887544804724975869364446262142112122988673373839847742070438962882250125122233745545143495723643603345280992502267774401497381004675738640244087608111042992147601034813658921759459351006245072157182907428514719988525370908573168466023754353178760685826783607542870975871595419527591617680487055751971514493078818140588523670965377064172800249955528093558647088552971666086416787806678401730330262204575448585818042970177069391128201298611884935446943861087522313828776155416892004135034388238296915677195001159449391736931444431655639578881722861502308895950563067659228813780268277695769459663473493669977495188101985291345584305591699352443029685238586043756572343960253010207696522304459594744365323697695045042887754121130724277763722314493543480181331473454786413562298891910383370572274892494725885667098984685189468205613849222530598269368477296912300361547140635666416622147099401397415676002576116226806006126361593092240442974992340417350326390726520004152167016152849030434301397899878862190237909734728202756964498884856058021784775355968017720209623071019687151409475985615518663579496364883970891457018555058995831657281629613720506146750530555185551292225432319834408263408737198304619567545297204667336012348781054935889725585527646969047750208235280250529869233105662838033788731210464957989416034593040355804449149979637396178600482154602591786984108391252777597650043008012807237071433649713839214851300210251561009352074216048638941229643898660352561225618418335270976152723942112898500256963072577680325381503787757233635537874613041695965823878997673069341031786467406524670134273795032723392565379267200748139481626034991715313149913546267303747602874165779746833955425458447804877962302704003141406106064454756118259640762686316651354332229265556198878741722986831173273490524648037143504387602012881474360576613463048001418646400948601700576847546659143392093398925905609350217758467886057350063914661197748870158458494479458842277625783799374222273128848514770543998555728963185595545172098169448623058522899324851281071657019573883750560541136665983550059938817428299830742104145360525391553252297722218142215990785378814976564901294113478070704322338931948109937978339117571137313739923632695139595444676057558867031148125481017007381564416844160379749589219499298432600292100633551438613969204018111411060952429225061057322093609105592981579949159518997195822591080261267918155069369642278300340303331564673020452460752977539761532262192673571687844912455868897848325356543065347345036623088560267605328534805507106879061347894054126486145346943745323397664288006292407239200394986656643492443126945633955224320950610203349844915833976386044459449210104253189190331465437636802497911902979944258170498485742251969977632347842000810171213825557059104740516923195850356199744592149826091094552227594774032568911179257705583581938490387604516746105553233595482061347875145906875948088298301818860882468633270662912737933532170691784092115698206729136024189612076374951740885851999459126248457920906699864929882630188320342047145647369961300333447714118043526809226242381164311688240919277829229714853964688446785031598587515498588429521393838697966967678061730513265626396139973624182253484832523999629380421237407312464873195005271061152386847982946101408482372168021434320307183074828881094063792769762257465116424690804730273051647209959404230795876593431040512888395787231473355176849421158193752064507754199231640968851271529697864275861296814460170555568340765767003404113685911519878473677614161066524068403546641910618836810087682079144604269478700239904023595526486151068893436140580685791538522111002913816043718661467724265801654793451406788889019107758078563423000095343720577272888319325002176961235604283216561486273816106999839806825639909865694176419299804827863357714727764216995223248781326756139300692381797763594760380836856759593873303361468097535614752804736719538958042048300738456018379628695402245530563959325108478154461636171731025218853329558204855830511037304663243767971993994534801516914055157902259767786958187339600062007446262227137544441710858585920307351877567317257790699184804321308376974227780422664593469673963508827888633563706987107362360295130165067652630204712495375543882238193049076724172166370151420457814183320220691993949576140516766693042478862108687982690717456729234581582708325489099512256332238093128176374695451847731779011883011853271223926335334815978484699088188762626004786664282014217009379459639724279319601808714887719339556888346780681306330096319469204272111411095777284617519124825436204742023672956807670361556285829532422930145542379459469726555991497521453027055156215074477717600825887345282276001233131850803229064222045672249139839256032225918142949804093146617324320156345420275076482910624496052923294124556181241937820547223210762562916124688272594639536501718290226838817345855221800200644117262377117687641261109867054292418785038051657301179220908347860225519371456626855936261814118573825830727880151150887333822886829291989628905338936869904386736345418154356026808499276458045165995857634638905521608768709100187636514441731035515403080038974961036998889648844804270380737065477067536955876616141233715832599783336476505388024439890350974933645964497097928991750790381289905552503607110550876322462769704753752823202249838090050597957266842650873885475426618907228288030121640423376604925466700099756199759089328435532752258519157414676340444251321066629392318654958972670230007152905383300386566650617155886059420531139055934350789760267074981795272024401698674329791582671636298003644802325745238665617539084760977307231035696528448600602955534510323198017008736671400697513730279694510456043906829466720479250919063427041020381459616589466090951378389125732243806189673437564276684234686028035032355846526470540503375139717409727764874746772212562460609722827672994536188587971199207186311773668979550948082663813230339280757105225494538892358453622816013109357223489465090150030417495895495377618489466213962519329504132290383460190817730741883793738240976398460419652110244057967402344577426462953839399066401478079304944206915838876266276616474094418517776726902173113904411108261758868775147123217503497148838956390802447643993701609079019957927744067850946286865807022626459524103229741519909088171492533800195046549345740486867782666862499528167420104031191894075129878426954883758172634005253975967172322194912485665486878924532169008034968449933985099291650952283729522906789740107459525397942810527808698991088246576346743214826770536879082289647137585217020803171026453885375353282472101128239385262272064504369335232458168431768553990600928444209779106681288250245850587577270252615751841785037821447597726140985074108853133130146154272759550701220401742977867608687261025624386798546207352857878638308888331154189461493617325855818695163364364445430348662660981543145423313479602203529246765022324498098498185048677439201498795601876057412379979570427508181083956883992141392303010486984463584054684835134467088323335582820649073187527631605212194355583999270860809672687331192732685110016992738160386235350798658260222612291766147582078705327185343486446613665755701187431771308971105472121930404139153646494153105878316839363305790376542962874077504278347071186827464396830955515071290576165504921070603144324776962171892579005021699558548902865469023566266239670280225599277674023815588887368512507516088252207513403309233847897176871347203242513004595406014503894393139133484417499491178524500413615176183453240941906445167340383176875


t, y = 0, 0  # base solution
for _ in range(5):
    t, y = P * t + Q * y + K, R * t + S * y + L  # recursive
    assert -12142578462 * t**2 + 3 * y**2 - y == 0
    if t > 0:
        x = 2 * 7 * 23 * 487 * t
        k = 7 * 23 * 487 * t**2
        print(x**2 == 313628 * k, 3 * y**2 - y == 154866 * k)
        a = 485 * 487 * k
        b = 487 * 159 * k
        c = 485 * k
        assert a > 0
        assert a == 487 * c
        assert 159 * a == 485 * b
        assert x**2 == a + b
        assert y * (3 * y - 1) == 2 * b
        if len(str(a)) < 31337:
            h = sha256(str(a).encode()).hexdigest()
            print(f"FCSC{{{h}}}")
# FCSC{b313c611e23a09e5479b10793705fb40a7a32dbcbd8c4bc2b1a33e42c4579cae}

Kzber

import os
import json
import zlib
import base64
import pickle
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all import *

class Kzber:
    def __init__(self, q = 3329, d = 256, k = 2, B = 2):
        self.q = q
        self.d = d
        self.k = k
        self.B = B
        Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
        R, X = Zq.quotient_ring(Y**d - 1, 'X').objgen()
        self.R = R
        self.X = X
        self._keygen()

    def _sample_short_poly(self):
        coeffs = [randint(-self.B, self.B) for i in range(self.d)]
        return self.R(coeffs)

    def _sample_short_vector(self):
        return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()

    def _keygen(self):
        A = random_matrix(self.R, 2, 2)
        s  = self._sample_short_vector()
        e1 = self._sample_short_vector()
        t = A * s + e1
        self.sk = s
        self.pk = (A, t)

    def encrypt(self, m):
        A, t = self.pk
        r  = self._sample_short_vector()
        e2 = self._sample_short_vector()
        e3 = self._sample_short_poly()
        u = r.transpose() * A + e2.transpose()
        v = r.transpose() * t + e3 + (int(round(self.q/2)) * self.R(m))
        return u, v
    
    def decrypt(self, c):
        u, v = c
        w = (v - u * self.sk)[0, 0]
        coeffs = list(w)
        coeffs = [int(wi) if int(wi) < self.q//2 else int(wi) - self.q for wi in coeffs]
        return [0 if abs(wi) <= self.q//4 else 1 for wi in coeffs]

PKE = Kzber()
A, t = PKE.pk
sk = randint(0, 2 ** 128)
C = [ PKE.encrypt(int(m)) for m in f"{sk:0128b}" ]

flag = open("flag.txt", "rb").read()
iv = os.urandom(16)
E = AES.new(int.to_bytes(sk, 16), AES.MODE_CBC, iv = iv)
enc = E.encrypt(pad(flag, 16))

print(base64.b64encode(zlib.compress(pickle.dumps({
    "A": A,
    "t": t,
    "C": C,
    "flag" : {
        "iv": iv,
        "enc": enc,
    },
    "sk": sk,
    "s": PKE.sk
}))).decode())

This is an RLWE problem similar to Kyber, using the ring $R=\mathbb{F}_{3329}[X]/(X^{256}-1)$ . One difference from standard RLWE is that the public $A \in R^{2 \times 2}$ is a matrix, and consequently, many other elements like $s,e$ , etc., also become vectors.

The most obvious issue with this problem is that

X^{256} - 1 = (X - 1) \cdot (X + 1) \cdot (X^{2} + 1) \cdot (X^{4} + 1) \cdot (X^{8} + 1) \cdot (X^{16} + 1) \cdot (X^{32} + 1) \cdot (X^{64} + 1) \cdot (X^{128} + 1)

is not an irreducible polynomial over $\mathbb{Z}[X]$ . Therefore, all equations in key generation, encryption, and decryption hold true modulo any factor $f'$ of $X^{256}-1$ . This allows reducing the size of the matrix for LLL, enabling us to find the solution for the secret key $s$ modulo $f'$ , and then use CRT to combine the results.

This part is similar to how I solved d3bdd (or GLP420) before, but the difference here is that $A$ is a matrix and $s$ is a vector. This requires modifying the lattice construction, but it increases the overall dimension, which might cause LLL to find a vector that is not the desired $s \mod f'$ . In practice, I could only find $s \mod L$ , where $L$ is the product of several low-degree factors of $X^{256}-1$ .

Fortunately, the challenge also provides a list $C$ , where each element encrypts a bit ( $0$ or $1$ ). Therefore, even with only this partial key, we can recover the bits of $C$ over $R'=\mathbb{F}_{3329}[X]/(L)$ .

from sage.all import *
import os
import json
import zlib
import base64
import pickle
import itertools
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from lll_cvp import flatter
from time import time

q = 3329
d = 256
k = 2
B = 2
Zq, Y = PolynomialRing(GF(q), "Y").objgen()
R, X = Zq.quotient_ring(Y**d - 1, "X").objgen()

with open("output.txt") as f:
    data = pickle.loads(zlib.decompress(base64.b64decode(f.read())))


def solve(poly, a1, a2, a3, a4, b1, b2):
    # solve for a1*s1+a2*s2+e1=b1 (mod poly)
    # solve for a3*s1+a4*s2+e2=b2 (mod poly)
    # where s and e are small
    global mat, mat2
    n = poly.degree()
    print(f"Try solving with deg(poly) = {n}")
    t0 = time()
    main_block1 = matrix([vector(a1 * Y**i % poly) for i in range(n)])
    main_block2 = matrix([vector(a2 * Y**i % poly) for i in range(n)])
    main_block3 = matrix([vector(a3 * Y**i % poly) for i in range(n)])
    main_block4 = matrix([vector(a4 * Y**i % poly) for i in range(n)])
    approx = 256 // n  # approximation for the average of target vector
    mat = block_matrix(
        ZZ,
        [
            [1, 0, -main_block1, -main_block3, 0],
            [0, 1, -main_block2, -main_block4, 0],
            [0, 0, q, 0, 0],
            [0, 0, 0, q, 0],
            [
                # kannan embedding
                0,
                0,
                matrix(vector(b1 % poly)),
                matrix(vector(b2 % poly)),
                matrix([[approx]]),
            ],
        ],
    )
    print(f"Lattice size = {mat.dimensions()}")
    mat2 = flatter(mat)
    print(f"{mat.nrows()}x{mat.ncols()} lattice reduced in {time() - t0}")
    for ret in mat2:
        if ret[-1] < 0:
            ret = -ret
        if ret[-1] == approx:
            print(ret)
            return Zq(list(ret[:n])), Zq(list(ret[n : 2 * n]))


fs = [f for f, _ in factor(polygen(ZZ, "Y") ** 256 - 1)]

A = data["A"]
t = data["t"]

a1, a2, a3, a4 = [x.lift() for x in A.list()]
b1, b2 = [x.lift() for x in t.list()]
# s1, s2 = [x.lift() for x in data["s"].list()]

s1ar = []
s2ar = []
mods = []
for ff in fs[3:6]:
    f = ff.change_ring(GF(q))
    s1x, s2x = solve(f, a1, a2, a3, a4, b1, b2)
    s1ar.append(s1x)
    s2ar.append(s2x)
    mods.append(f)
    # assert s1x == s1 % f and s2x == s2 % f

s1r = crt(s1ar, mods)
s2r = crt(s2ar, mods)
L = lcm(mods)


sk = 0
for i, (u, v) in enumerate(data["C"]):
    ul = matrix(*u.dimensions(), [x.lift() % L for x in u.list()])
    vl = matrix(*v.dimensions(), [x.lift() % L for x in v.list()])
    wl = (vl - ul * matrix.column([s1r, s2r]))[0, 0] % L
    w = ZZ(wl.constant_coefficient())
    w = w if w < q // 2 else w - q
    b = 0 if abs(w) <= q // 4 else 1
    print(i, b)
    sk = (sk << 1) | b

E = AES.new(int.to_bytes(sk, 16), AES.MODE_CBC, iv=data["flag"]["iv"])
flag = E.decrypt(data["flag"]["enc"])
print(flag)
# FCSC{9fa12c00603e0399fb84939704f7eea5626c715318578b5793b5da240b151984}

Fun with Hash

#!/usr/bin/env python3

from hashlib import md5, sha1, sha256
from datetime import datetime

print("Try to login on my super safe computer! Be fast, you have at most 30 minutes.")

now = str(datetime.now())
print(now)

try:
	m = bytes.fromhex(input())
except:
	print("Access denied!")
	exit(1)

t = sha256(now.encode()).hexdigest()
if t.encode() not in m:
	print("Access denied!")
	exit(1)

if not md5(m).hexdigest().endswith("fc5c25"):
	print("Access denied!")
	exit(1)

if not sha1(m).hexdigest().endswith("fc5c25"):
	print("Access denied!")
	exit(1)

print("Welcome! Here is your flag:")
print(open("flag.txt").read())

The goal of this challenge is to find a message m that contains a specific dynamic string t, and both md5(m) and sha1(m) must end with fc5c25. The requirement of containing the string is easy to handle and can be ignored for now. The double collision part, if searched directly, has an expected complexity of $2^{24} \times 2^{24} = 2^{48}$ , which is difficult to achieve on a personal computer within the 30-minute time limit mentioned in the problem.

My approach here is to first use the method from my previous challenge MagicHash. I use `` to generate a large number (more than $2^{24}$ ) of MD5 collisions. These collisions can be represented as an affine subspace over $\mathbb{F}_2^k$ , thus avoiding the need for large storage space.

Then, using a collision block as a prefix, append the specified string t, and perform a brute-force search of complexity $2^{24}$ for a suffix such that the resulting MD5 ends with fc5c25. This means that for any message within this collision space, appending t and the found suffix will result in the same hash ending with fc5c25.

Finally, randomly sample messages from this space and check whose SHA1 hash ends with fc5c25. The resulting message is the solution. This part is expected to take only $2^{24}$ steps. This effectively changes the cost from multiplying the two $2^{24}$ complexities to adding them, significantly reducing the attack cost.

import multiprocessing as mp
import os
import pickle
import subprocess
from base64 import b64encode
from datetime import datetime
from hashlib import md5, sha1, sha256
from pathlib import Path
from tempfile import TemporaryDirectory
from zlib import crc32

from pwn import remote
from pwnlib.util.iters import mbruteforce
from tqdm import trange


def fastcoll(
    prefix=b"", *, fastcool_bin=os.path.expanduser("~/workspace/fastcoll/fastcoll")
):
    with TemporaryDirectory() as dir:
        with open(dir + "/prefix", "wb") as f:
            f.write(prefix)
        subprocess.run(
            [
                fastcool_bin,
                "-p",
                "prefix",
                "-o",
                "out1",
                "-o",
                "out2",
            ],
            cwd=dir,
            stdout=subprocess.DEVNULL,
            check=True,
        )
        with open(dir + "/out1", "rb") as f:
            m1 = f.read()
        with open(dir + "/out2", "rb") as f:
            m2 = f.read()
    return m1[len(prefix) :], m2[len(prefix) :]


def get_collision_pairs(n: int):
    collisions = Path(__file__).parent / f"collisions_{n}.pkl"
    if collisions.exists():
        with collisions.open("rb") as f:
            return pickle.load(f)
    pairs = []
    prev = b""
    for _ in trange(n):
        ma, mb = fastcoll(prev)
        pairs.append((ma, mb))
        prev += ma
    with collisions.open("wb") as f:
        pickle.dump(pairs, f)
    return pairs


io = remote("chall.fcsc.fr", 2152)
io.recvuntil(b"minutes.\n")
now = io.recvlineS().strip()


n = 32
pairs = get_collision_pairs(n)

target_suffix = b"\xfc\x5c\x25"
msg_include = sha256(now.encode()).hexdigest().encode()


def xor(a, b):
    n = len(a)
    return (int.from_bytes(a, "big") ^ int.from_bytes(b, "big")).to_bytes(n, "big")


base = b"".join([ma for ma, _ in pairs])
deltas = []
for i in range(n):
    dt = b"".join(
        [
            b"\x00" * len(ma) if j != i else xor(ma, mb)
            for j, (ma, mb) in enumerate(pairs)
        ]
    )
    deltas.append(dt)
    assert md5(xor(base, dt)).digest() == md5(base).digest()


addition_suffix = mbruteforce(
    lambda m: md5(base + msg_include + m.encode()).digest().endswith(target_suffix),
    alphabet="0123456789",
    method="fixed",
    length=16,
).encode()
suffix = msg_include + addition_suffix
assert md5(base + suffix).digest().endswith(target_suffix)
assert md5(xor(base, deltas[0]) + suffix).digest().endswith(target_suffix)
print("suffix", suffix)


def brute(result, found):
    import random

    r = random.Random()

    b = base
    cnt = 0
    while True:
        b = xor(b, r.choice(deltas))
        cnt += 1
        if sha1(b + suffix).digest().endswith(target_suffix):
            if found.is_set():
                break
            result.put(b + suffix)
            found.set()
            break
        if cnt % 100000 == 0:
            print("brute forcing", cnt)
            if found.is_set():
                break


nproc = 8
found = mp.Event()
result = mp.Queue()
procs = [
    mp.Process(
        target=brute,
        args=(
            result,
            found,
        ),
    )
    for _ in range(nproc)
]
for p in procs:
    p.start()
print("burte forcing")
result = result.get()
print("found", result)

assert sha256(now.encode()).hexdigest().encode() in result
assert md5(result).digest().endswith(target_suffix)
assert sha1(result).digest().endswith(target_suffix)

io.sendline(result.hex())
io.interactive()
# FCSC{1070be6d782e61137ea9685d224375293ab88c39f0439a2f200b1acee5cd5bb3}

AES Distrace

This challenge provides an AES program written in C and its binary. It reads a random key from /dev/random, reads a block of plaintext from stdin, encrypts it, and outputs the result. Additionally, a Python script randomly generates a plaintext, encrypts it using the AES program with a random key, and gives you the ciphertext. The goal is to guess the plaintext to get the flag.

Obviously, if this were the entire problem, it would be unsolvable. However, the Python script also uses QEMU's `` to allow you to specify an address and dump the value of a specific register at that point. Therefore, the challenge becomes a "where & what to dump" problem, followed by figuring out how to recover the key or plaintext from the dumped values.

One idea is to directly dump the round keys. However, in this challenge, the key expansion and many AES operations do not use loops; instead, they are implemented using manual loop unrolling, and the binary is compiled with -O0. Since AES-128 has only 10 rounds, if the chosen dump address is not optimal, we might only get 10 or 11 outputs, making it difficult to determine the 16-byte key.

The only AES operation with a loop is subbytes + shiftrows:

void
SubBytes_ShiftRows(uint8_t s[4][4])
{
    uint8_t t[4][4];
    for (int i = 0; i < 4; ++i) {
        t[i][0] = s[i][0];
        t[i][1] = s[i][1];
        t[i][2] = s[i][2];
        t[i][3] = s[i][3];
    }
    for (int i = 0; i < 4; ++i) {
        s[i][0] = S[ t[i][(i + 0) % 4] ];
        s[i][1] = S[ t[i][(i + 1) % 4] ];
        s[i][2] = S[ t[i][(i + 2) % 4] ];
        s[i][3] = S[ t[i][(i + 3) % 4] ];
    }
}

Therefore, if the logging point is placed inside the loop of this function, we can dump $10 \times 4 = 40$ times, providing more information. Specifically, I chose to log the value of S[ t[i][(i + 3) % 4] ]. Determining the exact address and register requires reverse engineering skills, but it's achievable by opening the binary in IDA.

The next step is to find a way to recover the plaintext or key from this leaked information. Since s is the state, which is a mix of plaintext and key material, directly recovering either is difficult. We need to combine this information with the known ciphertext to constrain the possible plaintexts/keys. Because AES involves S-boxes, I couldn't find a good manual method, so I turned to our good friend: the Z3 SMT Solver!

In summary, after implementing the AES process in Z3 and adding constraints based on the known values (leaked data and ciphertext), it miraculously recovers the unique key and plaintext:

from z3 import *
from Crypto.Cipher import AES
from pwn import process, remote

# ------------------------------------
# Z3-compatible AES Start
# ------------------------------------

# fmt: off
RCON = [
    0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1b, 0x36
]
SBOX = [
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
    0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
    0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
    0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
    0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
    0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
    0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
    0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
    0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
    0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
    0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
    0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
    0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
    0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
    0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
    0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
    0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
]
MUL2 = [
    0x00, 0x02, 0x04, 0x06, 0x08, 0x0a, 0x0c, 0x0e,
    0x10, 0x12, 0x14, 0x16, 0x18, 0x1a, 0x1c, 0x1e,
    0x20, 0x22, 0x24, 0x26, 0x28, 0x2a, 0x2c, 0x2e,
    0x30, 0x32, 0x34, 0x36, 0x38, 0x3a, 0x3c, 0x3e,
    0x40, 0x42, 0x44, 0x46, 0x48, 0x4a, 0x4c, 0x4e,
    0x50, 0x52, 0x54, 0x56, 0x58, 0x5a, 0x5c, 0x5e,
    0x60, 0x62, 0x64, 0x66, 0x68, 0x6a, 0x6c, 0x6e,
    0x70, 0x72, 0x74, 0x76, 0x78, 0x7a, 0x7c, 0x7e,
    0x80, 0x82, 0x84, 0x86, 0x88, 0x8a, 0x8c, 0x8e,
    0x90, 0x92, 0x94, 0x96, 0x98, 0x9a, 0x9c, 0x9e,
    0xa0, 0xa2, 0xa4, 0xa6, 0xa8, 0xaa, 0xac, 0xae,
    0xb0, 0xb2, 0xb4, 0xb6, 0xb8, 0xba, 0xbc, 0xbe,
    0xc0, 0xc2, 0xc4, 0xc6, 0xc8, 0xca, 0xcc, 0xce,
    0xd0, 0xd2, 0xd4, 0xd6, 0xd8, 0xda, 0xdc, 0xde,
    0xe0, 0xe2, 0xe4, 0xe6, 0xe8, 0xea, 0xec, 0xee,
    0xf0, 0xf2, 0xf4, 0xf6, 0xf8, 0xfa, 0xfc, 0xfe,
    0x1b, 0x19, 0x1f, 0x1d, 0x13, 0x11, 0x17, 0x15,
    0x0b, 0x09, 0x0f, 0x0d, 0x03, 0x01, 0x07, 0x05,
    0x3b, 0x39, 0x3f, 0x3d, 0x33, 0x31, 0x37, 0x35,
    0x2b, 0x29, 0x2f, 0x2d, 0x23, 0x21, 0x27, 0x25,
    0x5b, 0x59, 0x5f, 0x5d, 0x53, 0x51, 0x57, 0x55,
    0x4b, 0x49, 0x4f, 0x4d, 0x43, 0x41, 0x47, 0x45,
    0x7b, 0x79, 0x7f, 0x7d, 0x73, 0x71, 0x77, 0x75,
    0x6b, 0x69, 0x6f, 0x6d, 0x63, 0x61, 0x67, 0x65,
    0x9b, 0x99, 0x9f, 0x9d, 0x93, 0x91, 0x97, 0x95,
    0x8b, 0x89, 0x8f, 0x8d, 0x83, 0x81, 0x87, 0x85,
    0xbb, 0xb9, 0xbf, 0xbd, 0xb3, 0xb1, 0xb7, 0xb5,
    0xab, 0xa9, 0xaf, 0xad, 0xa3, 0xa1, 0xa7, 0xa5,
    0xdb, 0xd9, 0xdf, 0xdd, 0xd3, 0xd1, 0xd7, 0xd5,
    0xcb, 0xc9, 0xcf, 0xcd, 0xc3, 0xc1, 0xc7, 0xc5,
    0xfb, 0xf9, 0xff, 0xfd, 0xf3, 0xf1, 0xf7, 0xf5,
    0xeb, 0xe9, 0xef, 0xed, 0xe3, 0xe1, 0xe7, 0xe5
]
AES_POLY = 0x11b
# fmt: on


def new_state():
    return [[0] * 4 for _ in range(4)]


def default_sbox(x):
    return SBOX[x]


def default_mul2(x):
    return MUL2[x]


def z3_mul2(x):
    return (x << 1) ^ (AES_POLY & -LShR(x, 7))


def key_expansion(key, *, sbox=default_sbox):
    rk = [new_state() for _ in range(11)]

    for j in range(4):
        rk[0][0][j] = key[4 * j + 0]
        rk[0][1][j] = key[4 * j + 1]
        rk[0][2][j] = key[4 * j + 2]
        rk[0][3][j] = key[4 * j + 3]

    for i in range(1, 11):
        rk[i][0][0] = rk[i - 1][0][0] ^ sbox(rk[i - 1][1][3]) ^ RCON[i]
        rk[i][1][0] = rk[i - 1][1][0] ^ sbox(rk[i - 1][2][3])
        rk[i][2][0] = rk[i - 1][2][0] ^ sbox(rk[i - 1][3][3])
        rk[i][3][0] = rk[i - 1][3][0] ^ sbox(rk[i - 1][0][3])
        rk[i][0][1] = rk[i - 1][0][1] ^ rk[i][0][0]
        rk[i][1][1] = rk[i - 1][1][1] ^ rk[i][1][0]
        rk[i][2][1] = rk[i - 1][2][1] ^ rk[i][2][0]
        rk[i][3][1] = rk[i - 1][3][1] ^ rk[i][3][0]
        rk[i][0][2] = rk[i - 1][0][2] ^ rk[i][0][1]
        rk[i][1][2] = rk[i - 1][1][2] ^ rk[i][1][1]
        rk[i][2][2] = rk[i - 1][2][2] ^ rk[i][2][1]
        rk[i][3][2] = rk[i - 1][3][2] ^ rk[i][3][1]
        rk[i][0][3] = rk[i - 1][0][3] ^ rk[i][0][2]
        rk[i][1][3] = rk[i - 1][1][3] ^ rk[i][1][2]
        rk[i][2][3] = rk[i - 1][2][3] ^ rk[i][2][2]
        rk[i][3][3] = rk[i - 1][3][3] ^ rk[i][3][2]

    return rk


def add_round_key(r, state, rk):
    for i in range(4):
        for j in range(4):
            state[i][j] ^= rk[r][i][j]


def subbytes_shiftrows(s, *, sbox=default_sbox):
    t = new_state()
    for i in range(4):
        t[i][0] = s[i][0]
        t[i][1] = s[i][1]
        t[i][2] = s[i][2]
        t[i][3] = s[i][3]
    for i in range(4):
        s[i][0] = sbox(t[i][(i + 0) % 4])
        s[i][1] = sbox(t[i][(i + 1) % 4])
        s[i][2] = sbox(t[i][(i + 2) % 4])
        s[i][3] = sbox(t[i][(i + 3) % 4])
        # this is the leak
        global_leak.append(s[i][3])


def MC_one(state, i, *, mul2=default_mul2):
    la, lb, lc, ld = state
    a = la[i]
    b = lb[i]
    c = lc[i]
    d = ld[i]
    aa = mul2(a) ^ mul2(b) ^ (b) ^ (c) ^ (d)
    bb = (a) ^ mul2(b) ^ mul2(c) ^ (c) ^ (d)
    cc = (a) ^ (b) ^ mul2(c) ^ mul2(d) ^ (d)
    dd = mul2(a) ^ (a) ^ (b) ^ (c) ^ mul2(d)
    la[i] = aa
    lb[i] = bb
    lc[i] = cc
    ld[i] = dd


def mix_columns(s, *, mul2=default_mul2):
    MC_one(s, 0, mul2=mul2)
    MC_one(s, 1, mul2=mul2)
    MC_one(s, 2, mul2=mul2)
    MC_one(s, 3, mul2=mul2)


def AES128(rk, state, *, sbox=default_sbox, mul2=default_mul2):
    add_round_key(0, state, rk)
    for i in range(1, 10):
        subbytes_shiftrows(state, sbox=sbox)
        mix_columns(state, mul2=mul2)
        add_round_key(i, state, rk)
    subbytes_shiftrows(state, sbox=sbox)
    add_round_key(10, state, rk)


def list_to_state(b):
    state = new_state()
    for i in range(4):
        for j in range(4):
            state[i][j] = b[4 * j + i]
    return state


def state_to_list(state):
    b = [0] * 16
    for i in range(4):
        for j in range(4):
            b[4 * j + i] = state[i][j]
    return b


# ------------------------------------
# Z3-compatible AES End
# ------------------------------------


def get_test_instance():
    import random
    import string

    def randomString(length=16):
        return "".join(
            random.choice(string.ascii_letters + string.digits) for _ in range(length)
        )

    key = os.urandom(16)
    pt = randomString(16).encode()

    rk = key_expansion(key)
    state = list_to_state(pt)

    global global_leak
    global_leak = leak = []
    AES128(rk, state)
    ct = bytes(state_to_list(state))
    assert ct == AES.new(key, AES.MODE_ECB).encrypt(pt), "implementation error"
    return key, pt, leak, ct


def connect():
    # io = process(["python", "local.py"])
    io = remote("chall.fcsc.fr", 2151)
    # leak at the last assignment of SubBytes_ShiftRows
    # printf abcdabcdabcdabcd | qemu-x86_64 -plugin ./libexeclog.so,afilter=0x401c24,reg=rax -d plugin ./aes-distrace
    io.sendlineafter(b"Address:  ", b"0x401c24")
    io.sendlineafter(b"Register: ", b"rax")
    leak = []
    for _ in range(40):
        leak.append(int(io.recvlineS().split("-> ")[1], 16))
    print(f"{leak = }")
    ct = bytes.fromhex(io.recvlineS().strip())
    print(f"{ct = }")
    return io, leak, ct


def solve(leak, ct):
    sol = Solver()
    sbox = Function("sbox", BitVecSort(8), BitVecSort(8))
    for x in range(256):
        sol.add(sbox(x) == default_sbox(x))

    sym_key = [BitVec(f"key_{i}", 8) for i in range(16)]
    sym_rk = key_expansion(sym_key, sbox=sbox)
    sym_pt = [BitVec(f"pt_{i}", 8) for i in range(16)]
    sym_state = list_to_state(sym_pt)

    global global_leak
    global_leak = sym_leak = []
    AES128(sym_rk, sym_state, sbox=sbox, mul2=z3_mul2)
    sym_ct = state_to_list(sym_state)

    for x, y in zip(sym_ct, ct):
        sol.add(x == y)

    assert len(leak) == len(sym_leak)
    for x, y in zip(sym_leak, leak):
        sol.add(x == y)

    print("Solving...")
    assert sol.check() == sat, "wtf"
    model = sol.model()
    key = bytes([model.eval(k).as_long() for k in sym_key])
    pt = AES.new(key, AES.MODE_ECB).decrypt(ct)
    return key, pt


def sanity_check():
    key, pt, leak, ct = get_test_instance()
    rec_key, rec_pt = solve(leak, ct)
    assert key == rec_key and pt == rec_pt, "failed"
    print("Success!")


io, leak, ct = connect()
key, pt = solve(leak, ct)
print(f"{key = }")
print(f"{pt = }")
io.sendline(pt)
print(io.recvallS().strip())
# FCSC{1bb5671d7de5ebe5d7ac8b8358419e3c1305c86944bed477d52a15c0e7}

Ça tourne au vinaigre

from Crypto.Hash import SHAKE256
import os
import json

class UOV:
    n = 60
    m = 24
    F = GF(256)
    Fxi = PolynomialRing(F, [f"x{i}" for i in range(n)])
    xi = list(Fxi._first_ngens(n))
    v = n - m

    def __init__(self):
        set_random_seed(int.from_bytes(os.urandom(32)))
        self.keygen()

    def bytes_to_vec(self, b):
        return vector(self.F, [self.F.from_integer(k) for k in b])

    def vec_to_bytes(self, vec):
        return bytes([k.to_integer() for k in vec])

    def generate_secret_system(self):
        self.secret_system = []
        for _ in range(self.m):
            curr_pol = self.F.random_element()
            for i in range(self.n):
                curr_pol += self.F.random_element() * self.xi[i]
                for j in range(max(self.v, i), self.n):
                    curr_pol += self.F.random_element() * self.xi[i] * self.xi[j]
            self.secret_system.append(curr_pol)

    def generate_secret_change_of_variable(self):
        cov_space = MatrixSpace(self.F, self.n, self.n)
        self.secret_cov = cov_space.random_element()
        while self.secret_cov.determinant() == 0:
            self.secret_cov = cov_space.random_element()

    def generate_public_key_from_secrets(self):
        new_variables = list(self.secret_cov * vector(self.Fxi, self.xi))
        self.public_system = []
        for secret_pol in self.secret_system:
            self.public_system.append(secret_pol(new_variables))

    def keygen(self):
        self.generate_secret_system()
        self.generate_secret_change_of_variable()
        self.generate_public_key_from_secrets()
        return self.secret_cov, self.public_system

    def sign(self, message):
        shake = SHAKE256.new()
        shake.update(message)
        # Target values
        hash_values = self.bytes_to_vec(shake.read(self.m))
        # Vinegar values
        v_values = list(self.bytes_to_vec(shake.read(self.v)))

        mat = []
        constant_vec = []
        # Fix vinegar values and deduce a linear system in the oil variables
        for secret_pol in self.secret_system:
            new_secret_pol = secret_pol(self.xi[:self.m] + v_values)
            mat.append([new_secret_pol.coefficient({self.xi[i]: 1}) for i in range(self.m)])
            constant_vec.append(new_secret_pol.constant_coefficient())
        mat = Matrix(self.F,mat)

        # Deterministic signature fails if the matrix is not invertible
        if not mat.is_invertible():
            return 0

        constant_vec = vector(self.F, constant_vec)
        # Constant part of the linear system
        output_vec = constant_vec + hash_values
        # Oil values can be deduced with linear system solving
        o_values = mat.inverse() * output_vec
        # Oil and vinegar values are aggregated
        ov_values = vector(self.F, list(o_values) + v_values)
        # They are transformed to the public coordinates
        x_values = self.secret_cov.inverse() * ov_values

        return self.vec_to_bytes(x_values)

    def verify(self, message, signature):
        try:
            shake = SHAKE256.new()
            shake.update(message)

            # Target values
            hash_values = self.bytes_to_vec(shake.read(self.m))
            # x-values contained in the signature
            x_values = self.bytes_to_vec(signature)

            # The x-values contained in the signature should solve the polynomial system
            # The target values correspond to the hash of the message
            a = True
            for public_pol, h in zip(self.public_system, hash_values):
                a = a & (public_pol(x_values) == h)
            return a
        except:
            return 0

if __name__ == "__main__":

    Vinaigrette = UOV()

    data = {}
    while len(data) < 1600:
        message = os.urandom(16)
        signature = Vinaigrette.sign(message)
        if signature == 0:
            continue
        data[message.hex()] = signature.hex()

    print(json.dumps(data, indent = 4))

    flag_signature = Vinaigrette.sign(b"Un mauvais vinaigre fait une mauvaise vinaigrette!")
    flag = f"FCSC{{{flag_signature.hex()}}}"
    with open("flag.txt", "w") as f:
        f.write(flag)

This is an Unbalanced Oil and Vinegar (UOV) challenge. We are given 1600 message/signature pairs, no public key, and the goal is to perform a signature forgery.

I recently introduced UOV in the writeup for the fairy-ring challenge. However, this problem requires a deeper understanding, so I will provide a complete introduction to UOV in my own words before explaining the solution.

UOV Introduction

As a multivariate cryptosystem, UOV's security relies on the difficulty of solving systems of multivariate polynomial equations. Therefore, the UOV public key consists of a map $P(x)$ composed of multiple multivariate quadratic polynomials. A signature $s$ for a message $m$ satisfies $P(s)=H(m)$ . The security relies on the difficulty of finding a preimage $s$ for $H(m)$ when only the public key $P$ is known.

Formally, the public key of UOV over a field $K$ is a map $P(x): K^n \to K^m$ , consisting of $m$ polynomials:

P(x)=(f_1(x), f_2(x), \cdots, f_m(x))

where each polynomial $f_i \in K[x_1,\cdots,x_n]$ , and all monomials are quadratic. Thus, each $f_i$ can be represented in quadratic form:

f_i(x) = x^T A_i x

So we can also define the corresponding polar form $P'(x,y)$ for the entire public key:

P'(x,y)=P(x+y)-P(x)-P(y)=x^T(A+A^T)y

And $P'(x,y)$ is a bilinear function.

In UOV, signing requires a method to invert $P$ . Since this is generally infeasible, a trapdoor is needed. The UOV trapdoor is a linear subspace $O \in K^n$ called the oil subspace, satisfying $\forall o \in O, P(o)=0$ . To sign, one first randomly chooses a $v \in K^n$ , then aims to find an $o \in O$ such that $P(v+o)=H(m)$ . This leads to:

P(v+o)=P'(v,o)+P(v)+P(o)=H(m)

Noting that $P(o)=0$ , we get $P'(v,o)=H(m)-P(v)$ . Since $P'$ is linear, we can solve for the required $o$ , yielding the signature $s=v+o$ .

However, a problem is that such a subspace $O$ does not generally exist. Therefore, $O$ must be designed during key generation. Key generation starts by creating a random quadratic polynomial system $F(x) \in K[x_1,\cdots,x_n]^m$ , where $x_1,\cdots,x_m$ are called oil variables, and the remaining $x_{m+1},\cdots,x_n$ are called vinegar variables.

The generated $F(x)$ has a crucial property: none of its polynomials contain monomials formed by multiplying two oil variables.

At this point, define the subspace $O'$ :

O'=\{x \in K^n | x_{m+1}=\cdots=x_n=0\}

Since all monomials in $F$ involve at least one vinegar variable, we have $F(O')=0$ . Here, $O'$ serves as an oil subspace. However, $F$ cannot be directly published as the public key, as $O'$ would be too easy to find. Therefore, a random invertible linear transformation $T: K^n \to K^n$ is chosen, and the public key is derived as:

P(x)=F \cdot T=F(T(x))

That is, $T$ represents a random change of variables, and the true oil subspace $O=T^{-1}(O')$ satisfies $P(O)=0$ . Now, it is difficult to identify the oil subspace $O$ from $P$ , because the random transformation makes it hard to distinguish between oil and vinegar variables.

Solution

Returning to the challenge, it uses $K=\mathbb{F}_{256}$ , with $n=60,m=24$ . However, this challenge differs from standard UOV in that its secret_system (corresponding to $F$ ) includes linear and constant terms. Consequently, its public_system (corresponding to $P$ ) also has linear and constant terms. Therefore, I redefine $P$ here as:

P(x)=Q(x)+L(x)+C

where $Q(x)$ is the quadratic part, $L(x)$ is the linear part, and $C$ is the constant term. Be careful not to confuse the notation here with the $P$ used in the UOV introduction above. Additionally, the secret_cov matrix represents the linear transformation $T$ .

First, since we don't have the public key, we consider whether we can recover it from the message/signature pairs. Note that $P(s_i)=H(m_i)$ , providing many relations. Each quadratic polynomial $f_i$ in $P$ has $\binom{n+1}{2}+n+1=1891$ terms. Therefore, using linearization with more than 1891 pairs, we could theoretically solve a linear system to find the public key $P$ . However, the challenge only provides 1600 pairs, which means the solution is not unique, and we cannot yet obtain the public key $P$ .

Another crucial part of this challenge is in this code snippet:

def sign(self, message):
    shake = SHAKE256.new()
    shake.update(message)
    # Target values
    hash_values = self.bytes_to_vec(shake.read(self.m))
    # Vinegar values
    v_values = list(self.bytes_to_vec(shake.read(self.v)))

It shows that the random $v$ used during signing is determined by the hash of the message. Thus, we know the value of $v$ . This naturally leads to the question: what problems arise in UOV if $v$ is known? I couldn't find a direct answer to this, but I found a related paper: Security Analysis of Reusing Vinegar Values in UOV Signature Scheme, which discusses the issues caused by reusing $v$ in two different signatures in UOV.

After understanding its attack method, I realized that if $v$ is known (or if some linear relations exist), the impact is comparable to having issues with $k$ in ECDSA, meaning we can recover the private key $O$ .

Note that here $v$ exists as input to $F$ (secret_system), unlike in the introduction where it was input to $P$ !!!

Simply put, we know the relationship between $v$ and the signature is $s=T^{-1}[o | v]^T$ , which can be seen from the end of the sign function in the code. Define $\pi_v$ as a projection operator that takes only the last $n-m$ vinegar variables. Then we have $\pi_v(T(s))=v$ .

Suppose we define $\mathrm{vs}=[v_1,v_2,\cdots]$ , $\mathrm{ss}=[s_1,s_2,\cdots]$ . We can find an $x$ such that $\mathrm{vs} \cdot x=0$ (find the kernel). Then we get:

\pi_v(T(\mathrm{ss} \cdot x))=\mathrm{vs} \cdot x = 0

This means $T(\mathrm{ss} \cdot x)$ is a vector in the $F$ domain where all vinegar variables are zero, i.e.:

T(\mathrm{ss} \cdot x) \in O' \rightarrow \mathrm{ss} \cdot x \in O

Recall these two definitions:
$O'=\{x \in K^n | x_{m+1}=\cdots=x_n=0\}$
$O=T^{-1}(O')$

This means $\mathrm{ss} \cdot x$ is a vector in the private key subspace $O$ . If we can find multiple such $x$ , we can obtain the entire basis for $O$ .

However, upon substitution, we find that $P(\mathrm{ss} \cdot x) \neq 0$ . Why? Because the condition for defining $O'$ that way holds only when $F$ has only quadratic terms. In this challenge, $P$ has linear and constant terms, so this condition does not hold. The equation that actually holds is $Q(\mathrm{ss} \cdot x) = 0$ , where $Q$ (the quadratic part) can be easily separated from $P$ .

Although we haven't obtained the public key $P$ yet, we can still create a local instance with a known public key for testing.

So, we just need to:

Collect the $v_i$ corresponding to each message into $\mathrm{vs}$ , and find $x_i$ such that $\mathrm{vs} \cdot x_i=0$ .
Collect the $s_i$ corresponding to each signature into $\mathrm{ss}$ . Then $\mathrm{ss} \cdot x_i$ forms the entire basis for $O$ , satisfying $Q(O)=0$ .

This allows us to obtain $O$ .

After obtaining $O$ , we still need the public key to forge signatures, so we need to find a way to determine $P$ . I continue with the linearization method mentioned earlier. In addition to the original 1600 equations, I sample some random $o \in O$ and add the equations $Q(o)=0$ until the rank is sufficient. Solving this system then yields the unique $P$ , from which we can also separate $Q,L,C$ .

Next is the signature forgery part, which involves finding $s$ for a fixed $t$ such that $P(s)=t$ . Since there are additional $L,C$ terms here, the process is slightly different. First, choose a $v$ as input to $P$ and try to find $P(v+o)=t$ :

\begin{aligned} P(v+o) &=Q(v+o)+L(v+o)+C \\ &=Q'(v,o)+Q(v)+Q(o)+L(v)+L(o)+C \\ &=t \end{aligned}

Since we have $Q(o)=0, P(v)=Q(v)+L(v)+C$ , rearranging gives:

Q'(v,o)+L(o)=t-P(v)

The left side is entirely linear, so we can solve for $o$ , enabling arbitrary signature forgery. However, there's one final issue: the $v$ used for the signature forgery required by the challenge is not arbitrary. We know from the problem description that the flag content is the hex representation of the entire signature. This means not just any signature will work as the flag; only the signature generated using the specific $v$ produced by the original hash function will be the correct flag.

Achieving this is not trivial because here $v$ is the input to the $F$ secret_system, unlike in the general signature forgery process where $v$ is the input to $P$ . They differ by the transformation $T$ . This means we actually need to use $T^{-1}v$ as the public vinegar vector to forge the signature that will be our flag!!!

One possible approach is to try to decompose $P=F \cdot T$ using $P$ and $O$ , but I couldn't figure out how to do this myself. A key insight I used here is that for a $v$ in the $P$ domain, replacing it with any $v'=v+o,o \in O$ does not change the resulting signature $s$ . (Why? I don't know ==)

Therefore, using the existing signature/message pairs, find $x$ such that $\mathrm{vs} \cdot x = v$ (where $v$ is the target vinegar vector in the $F$ domain, the output from the hash function). Then we have:

\mathrm{ss} \cdot x = T^{-1} (\mathrm{os} + \mathrm{vs}) \cdot x = T^{-1}v + T^{-1}(\mathrm{os} \cdot x)

Here, the vectors in $\mathrm{os}$ belong to $O'$ , so $T^{-1}(\mathrm{os} \cdot x) \in O$ . This means $\mathrm{ss} \cdot x$ can be used as the required $T^{-1}v$ , because it differs from the true $T^{-1}v$ only by a vector in $O$ . Therefore, taking $v=\mathrm{ss} \cdot x$ for signature forgery yields the signature that is the flag.

from sage.all import *
from Crypto.Hash import SHAKE256
import json


n = 60
m = 24
F = GF(256)
Fxi = PolynomialRing(F, [f"x{i}" for i in range(n)])
xi = list(Fxi._first_ngens(n))
v = n - m


def bytes_to_vec(b):
    return vector(F, [F.from_integer(k) for k in b])


def vec_to_bytes(vec):
    return bytes([k.to_integer() for k in vec])


def convert_signature_pair(message, signature):
    shake = SHAKE256.new()
    shake.update(message)
    hash_values = bytes_to_vec(shake.read(m))
    x_values = bytes_to_vec(signature)
    v_values = bytes_to_vec(shake.read(v))
    return x_values, hash_values, v_values


with open("output.txt") as f:
    data = json.load(f)
    sigpairs = [
        convert_signature_pair(bytes.fromhex(message), bytes.fromhex(signature))
        for message, signature in data.items()
    ]


# since we know the vinegar part used to sign the message
# which is approximate the same case as vinegar reused
# so the method of "Security Analysis of Reusing Vinegar Values in UOV Signature Scheme" applies
# https://www.researchgate.net/publication/381204113_Security_Analysis_of_Reusing_Vinegar_Values_in_UOV_Signature_Scheme
# basically there a linear transform T that T*s=[o | v], and the uov map is P(x)=F(T(x)) for some quadratic map F
# so if we find a linear relations of vs that vs*x=0
# then vinergar_part(T*ss*x)=vinergar_part(vs*x)=0
# and the secret linear subspace in the secret system is O'={v | v in F^n and vinegar_part(v)=0}
# so T^-1(O')=O is the linear subspace in the public system
# by definition, T*ss*x is in O', so ss*x is in O

SM, HM, VM = [matrix(x) for x in zip(*sigpairs)]
vlk = VM.left_kernel_matrix()
O_basis = vlk * SM
# O_basis is the kernel of the quadratic part of the public key
# does not include the affine part
O = span(O_basis)

# let's recover the public key by linearization
quad_terms = binomial(n + 1, 2) + n + 1


def to_quad(v):
    ret = [1]
    ret.extend(list(v))
    for i in range(n):
        for j in range(i, n):
            ret.append(v[i] * v[j])
    assert len(ret) == quad_terms
    return vector(ret)


lhs = []
rhs = []
for x, y, _ in sigpairs:
    lhs.append(to_quad(x))
    rhs.append(y)
# since the challenge only gives 1600 samples, which is less then quad_terms, the solution is not unique
# so we also need to use our recovered O to ensure its uniqueness, quad(O) = 0
while len(lhs) < quad_terms + 10:
    t = to_quad(O.random_element())
    t[: 1 + n] = [0] * (1 + n)  # set the constant and linear term to zero
    lhs.append(t)
    rhs.append([0] * m)
lhs = matrix(F, lhs)
rhs = matrix(F, rhs)
assert lhs.rank() == quad_terms, "rank not enough, can't find unique solution"
pub_mat = lhs.solve_right(rhs).T  # equivalent to the public key


def pub(x):
    # pub(x) = quad(x) + lin(x) + const
    return pub_mat * to_quad(x)


# let split pub(x) into quadratic, linear and constant part
quad_mat = pub_mat[:, 1 + n :]
lin_mat = pub_mat[:, 1 : 1 + n]
const = vector(pub_mat[:, 0])


def lin(x):
    return lin_mat * x


def quad(x):
    return quad_mat * to_quad(x)[1 + n :]


x = random_vector(F, n)
assert pub(x) == quad(x) + lin(x) + const, "wtf"
# verify O is indeed the kernel of the quadratic part
assert quad(O.random_element()) == 0


def quad_polar(x, y):
    return quad(x + y) - quad(x) - quad(y)


target_msg = b"Un mauvais vinaigre fait une mauvaise vinaigrette!"
shake = SHAKE256.new()
shake.update(target_msg)
target_hash = bytes_to_vec(shake.read(m))
tv_raw = bytes_to_vec(shake.read(v))


# FOR ANYONE WHO READS THIS CODE
# PLEASE SKIP THIS PART FIRST UNTIL YOU UNDERSTAND THE SIGNATURE FORGERY PART
# THIS PART ONLY MATTERS FOR THE DETERMINISTIC SIGNATURE USED IN THE CHALLENGE

# the correct target_v should be
# target_v = uov.secret_cov.inverse() * vector(F, [0] * m + list(tv_raw))
# which is the correct "vinegar" in the public system
# because in the original signing algorithm tv_raw is substituted into the secret system
# and we are now trying to solve it in the public system, so a inverse transformation is needed
# also, due to how uov works, the target_v and add any vector in O
# target_v += O.random_element() also result in the same signature

# but we don't know the secret transformation matrix
# denote uov.secret_cov.inverse() = A
# from the signature equation we know A * (v + o) = S where A*o is in O
# if you use the existing signatures to find x such that vs*x=V' (V' target vinegar)
# then ss*x = A*vs*x + A*os*x = A*V' + A*os*x
# the A*V' is the target_v we want, and the ss*x - A*V' = A*os*x is also in O
# this means the target_v below is also different from the original target_v by a vector in O
# so the signature is still the same!!!

# END OF THE PART YOU SHOULD SKIP

target_v = VM.solve_left(tv_raw) * SM


# signature forgery:
# now I want to find x that pub(x)=target_hash
# pub(x+v)=quad(x+v)+lin(x+v)+const=t
#         =quad(x)+quad_polar(v,x)+quad(v)+lin(x)+lin(v)+const
# if we only sample x from O, which satisfy quad(O)=0
# then quad_polar(v,x)+lin(x)=t-quad(v)-lin(v)-const=t-pub(v)
# so we only need to find x in O such that quad_polar(v,x)+lin(x)=t-pub(v)
# and quad_polar(v,x)+lin(x) is linear in x, just solve it

lhs = []
rhs = []
for _ in range(n + 10):
    ov = O.random_element()
    lhs.append(ov)
    rhs.append(quad_polar(target_v, ov) + lin(ov))
sol = matrix(rhs).solve_left(target_hash - pub(target_v)) * matrix(lhs)
sig = sol + target_v
assert pub(sig) == target_hash, "wtf"
print(f"FCSC{{{vec_to_bytes(sig).hex()}}}")
# FCSC{ae0ab14d8d586f9dc94efa6b3a82a69960ecd9517b8d0254ec34f52cffec24326030234e3640544ed4e1279548793f253d341fb13c6ef5f001705bd2}

La quête de l'anneau#

CocoRiCo#

Problèmeuh#

Kzber#

Fun with Hash#

AES Distrace#

Ça tourne au vinaigre#

UOV Introduction#

Solution#