FCSC 2025 Writeups

發表於 2025-04-28

分類於 CTF

FCSC (France Cybersecurity Challenge) 2025 是法國篩選選手去 ECSC 的一個 CTF 比賽，因為往年都覺得題目品質很不錯所以今年也來 Solo 玩玩看。主要都解了些 crypto 的題目，難度不低且都蠻好玩的。

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))

這題的 stream cipher 的 key 是個整數 $s$ ，而加密是隨機選和 $s$ 互直 $iv$ 後 $c = m \cdot iv \mod s$ 。

顯然透過已知的 plaintext/ciphertext 以及 iv 可用 gcd 求 $s$ ，之後就能解 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.")

這題用了 AES-OFB 結合 CRC32 做了一個 AEAD:

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

目標是要把 token 中的 json 做一些修改。

然而 OFB 類似 stream cipher，可以直接對 ciphertext xor 就能在 plaintext 上得到一樣的 xor，所以可以直接竄改 json。然後後面 crc 也會因為前面 json 改變而變化，不過這部分也只要把改變前後 crc 的差異 (xor) 也 xor 回去就好。

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!")

簡單來說要找到一組整數解符合:

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

首先因為 $a,b,c$ 都是整數，且 $159,485,487$ 兩兩互質，所以可令:

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

且 $k$ 為整數，因此就變成了:

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

由於 $313628 = 2^2 \cdot 7 \cdot 23 \cdot 487$ ，所以可再引入一個整數 $t$ 使得:

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

然後代回 $y$ 的那條得到:

3y^2 - y = 12142578462t^2

顯然這是一個 degree 2 diophantine equation，所以我這邊就用上了 alpertron 的 solver。得到的解是 recursive 的，所以有無限組解，不過因為題目有限制找到的解要小於 $10^{31337}$ ，可以額外篩一下，會發現只有唯一一組解夠小，因此 hash 就能拿到 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())

這題是個類似 Kyber 的 RLWE 題目，用的 ring $R=\mathbb{F}_{3329}[X]/(X^{256}-1)$ 。和一般的 RLWE 的一個不同點是在於 public 的 $A \in R^{2 \times 2}$ 是矩陣，因此很多其他的 $s,e$ 等等也都變成了向量。

這個題目最明顯的問題在於

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)

在 $\mathbb{Z}[X]$ 上不是個 irreducible polynomial，因此 key generation/encryption/decryption 中的所有等式都可以 mod $X^{256}-1$ 的任何一個 factor $f'$ 且成立。這樣可以導致要 LLL 的矩陣大小變小，所以可以找到 secret key $s$ mod $f'$ 的解，然後再 CRT 即可。

這部分和我之前解 d3bdd (or GLP420) 類似，不過差異在於這邊 $A$ 是矩陣且 $s$ 是向量。這會需要改一下構造 lattice 的部分，但這樣會總體的維度變高，這樣導致 LLL 找出的向量可能不是想要的 $s \mod f'$ 。實際上我也只能找到 $s \mod L$ ，其中 $L$ 是 $X^{256}-1$ 的其中幾個 low degree factors 的乘積。

幸好這題還有給一個 $C$ list，其中每個都加密了一個 $0$ or $1$ 的 bit，因此這樣就算只靠這個 partial key 也能在 $R'=\mathbb{F}_{3329}[X]/(L)$ 上解出 $C$ 的 bit。

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())

這題目標是找一個 m 中包含某個指定的動態字串 t，且 md5(m) 和 sha1(m) 都要以 fc5c25 結尾。包含字串的部分很好處理可以忽略不計，而後面的雙重 collision 部分如果直接找的所需次數期望是 $2^{24} \times 2^{24} = 2^{48}$ ，以題目說的 30 分鐘來說是有點難在個人電腦上達成。

我這邊的解法是先用我出過的 MagicHash 那題的方法，用 fastcoll 生成一堆 (超過 $2^{24}$ ) md5 collision，且這些 collision 可表示為一個 $\mathbb{F}_2^k$ 底下的 affine subspace 所以不用大量的儲存空間。

之後以 collision 做 prefix，中間接上指定的 t 字串，後面再做 $2^{24}$ 的爆搜使得 md5 suffix 是 fc5c25。這樣代表這個 collision space 的任何一個訊息加上 t 與 suffix 的 hash 都不會變，都是 fc5c25 結尾的。

最後拿從這個 space 中隨便 sample 些 message，看看誰的 sha1 suffix 正好是 fc5c25，得到的結果就是題目所求。這部分預期也只要 $2^{24}$ 步，這樣就把原本兩個 $2^{24}$ 的 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

這題給了一個 C 寫的 aes program & binary，它從 /dev/random 讀取隨機 key，然後從 stdin 讀取一個 block 的 plaintext，然後加密後輸出。另外有個 python 腳本會隨機生成一個 plaintext，用那個 aes program 隨機加密後把 ciphertext 給你。目標是要猜出 plaintext 才能拿到 flag。

顯然，如果題目只有這樣的話是無解的，所以 python 腳本那邊還有透過 qemu 的 libexeclog 讓你指定一個 address 去輸出某個 register 的值。因此這題就變成了一個 where & what to dump 的問題，然後之後還有有辦法從 dump 的值中解出 key or plaintext。

一個想法是直接去 dump round key，但這題 key expansion 還有很多的 aes operations 都沒有使用 loop，而是使用手動 loop unrolling 的寫法，且 binary 的編譯時開的是 -O0。由於 AES 128 只有 10 rounds，所以如果選擇 dump 的 address 選不好的話只能得到 10 or 11 個輸出，要去確定出 16 bytes 的 key 有點困難。

唯一一個有 loop 的 aes operation 是 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] ];
    }
}

因此如果 log 的地方放在這個 function 的 loop 裡面就能 dump $10 \times 4 = 40$ 次，能得到的資訊比較多。我這邊具體是讓它 log S[ t[i][(i + 3) % 4] ] 的值。具體的 address & register 要怎麼決定就靠自己的 reverse 能力的，反正 IDA 打開其實就能做到了。

下一步驟是找方法從這個 leak 的資訊中求 plaintext or key。由於 s 是 state，裡面算是 plaintext 以及 key 的混和，因此要直接求出任何一個都不太容易，還得需要結合已知的 ciphertext 去把可能的 plaintext/key 限制住才行。由於 AES 有 sbox 所以我自己沒什麼好辦法能處裡，所以只好請出了我們的好朋友: Z3 SAT Solver!

總之用 Z3 實作出來後然後用已知的值把它 constraint 起來，很神奇的就能 recover 出唯一的 key & 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)

這題是個 UOV (Unbalanced Oil and Vinegar) 的題目，給了 1600 組 message/signature pairs，沒有 public key，然後要做 signature forgery。

簡介 UOV 的話我不久前也有在 fairy-ring 這題介紹過，不過這邊需要更深入的了解才能處裡，所以我會用我的話完整的介紹一遍 UOV，再來說明解法。

UOV 簡介

UOV 做為一個 multivariate cryptosystem，它的難度仰賴於求解 multivariate polynomial system 的難度。因此 UOV 的 public key 是由多個 multivariate quadratic polynomials 所組成的一個 map $P(x)$ 。對 message $m$ 的 signature $s$ 符合 $P(s)=H(m)$ ，仰賴的是你很難在只知道 public key $P$ 的情況下去找 $H(m)$ 的 preimage $s$ 。

正式來說 UOV 在一個 field $K$ 上的 public key 是個 map $P(x): K^n \to K^m$ ，為 $m$ 條多項式

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

其中每條多項式 $f_i \in K[x_1,\cdots,x_n]$ ，且所有的 monomials 都是二次的，因此每個 $f_i$ 都能以二次型表示:

f_i(x) = x^T A_i x

所以我們也可以給整個 public key 定義對應的 polar form $P'(x,y)$ :

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

且 $P'(x,y)$ 是個 bilinear function。

而在 UOV 中要簽名需要有方法 invert $P$ ，而這在一般情況下是做不到的，所以需要 trapdoor。UOV 的 trapdoor 是一個 linear subspace $O \in K^n$ 叫 oil subspace，符合 $\forall o \in O, P(o)=0$ 。要簽名時先隨機選一個 $v \in K^n$ ，目標是找一個 $o \in O$ 使得 $P(v+o)=H(m)$ ，那麼可以得到:

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

注意到 $P(o)=0$ 可得 $P'(v,o)=H(m)-P(v)$ ，因此只要利用 $P'$ 是 linear 的性質就能解出需要的 $o$ ，所以有 signature $s=v+o$ 。

不過有個問題是 $O$ 這樣的 subspace 一般不一定會存在，所以 $O$ 是個從 keygen 時就要先設計好才能求出來的東西。keygen 時先生成一個隨機的 quadratic polynomial system $F(x) \in K[x_1,\cdots,x_n]^m$ ，其中的 $x_1,\cdots,x_m$ 叫 oil variable，剩下的 $x_{m+1},\cdots,x_n$ 叫 vinegar variable。

生成的 $F(x)$ 有個很重要的性質，就是它的多項式裡面都沒有 oil variable 與 oil variable 相乘得到的 monomial。

此時定義 $O'$ subspace:

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

因為 $F$ 中所有的 monomials 都有 vinegar variable，所以可得 $F(O')=0$ 。而這邊的 $O'$ 就是一個 oil subspace。不過顯然不能直接把 $F$ 直接當作 public key 公開，不然就太容易找出 $O'$ 了。因此還會再選一個隨機的 invertible linear transform $T: K^n \to K^n$ ，然後能得到 public key:

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

也就是 $T$ 代表是一個隨機的變數代換，而真正的 oil subspace $O=T^{-1}(O')$ 符合 $P(O)=0$ 。此時就不容易從 $P$ 中看出 oil subspace $O$ 是誰了，因為經過一個隨機變換之後就很難分出 oil variable 和 vinegar variable。

解法

回到題目本身，題目用了 $K=\mathbb{F}_{256}$ ，而 $n=60,m=24$ 。不過這題和一般 UOV 有個不同，就它的 secret_system (對應到 $F$ ) 是有一次項與常數項的，因此它的 public_system (對應到 $P$ ) 也會有一次項與常數項，所以我在這邊把 $P$ 重新定義為:

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

其中 $Q(x)$ 是二次項的部分， $L(x)$ 是一次項的部分， $C$ 是常數項。當然，不要把這邊的符號和上面介紹 UOV 的 $P$ 搞混。另外是 secret_cov 的矩陣則代表的是 $T$ 的 linear transform。

首先我們沒有 public key，所以會想看能不能從 signature/message pairs 中求出來。首先注意到 $P(s_i)=H(m_i)$ ，所以可以拿到很多的 relation。而 $P$ 的每個二次多項式 $f_i$ 都有 $\binom{n+1}{2}+n+1=1891$ 項，所以只要透過 linearization 加上超過 1891 組 pairs，理論上就能透過解 linear system 求出我們要的 public key $P$ 了。然而題目只給了 1600 pairs，因此能得到的解並非 unique 的，所以目前還沒辦法拿到 public key $P$ 。

這題還有個關鍵是在這段 code:

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)))

可見它在做簽名時所用的隨機 $v$ 是由 message 的 hash 決定的，因此我們知道 $v$ 是多少。所以自然會想說在 UOV 中若 $v$ 已知會造成什麼問題嗎? 對於這個問題我沒找到直接的答案，但我有看到一個類似的問題: Security Analysis of Reusing Vinegar Values in UOV Signature Scheme，討論了 UOV 中的 $v$ 如果在兩個不同的 signature 中 reuse 會導致什麼問題。

理解了它的攻擊方式後，我了解到 $v$ 如果被知道 (或是有些 linear relation 存在) 的話，那它能造成的影響和 ecdsa 中 $k$ 有問題是差不多大的，也就是能得到 private key $O$ 。

這邊要注意此處的 $v$ 是作為 $F$ (secret_system) 的輸入存在的，而不像前面簡介那邊作為 $P$ 的輸入存在!!!

簡單來說，我們知道 $v$ 與 signature 有這樣的關係: $s=T^{-1}[o | v]^T$ ，這部分從題目的 sign 函數最後那邊看了出來。定義 $\pi_v$ 做為一個只取後 $n-m$ 項 vinegar variable 的一個 projection operator，則有 $\pi_v(T(s))=v$ 。

假設定義 $\mathrm{vs}=[v_1,v_2,\cdots]$ , $\mathrm{ss}=[s_1,s_2,\cdots]$ ，我們可以找出一個 $x$ 使得 $\mathrm{vs} \cdot x=0$ (求 kernel)。此時可得:

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

也就是說 $T(\mathrm{ss} \cdot x)$ 是一個 $F$ domain 中 vinegar variable 全部為 0 的 vector，即:

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

這邊可以回憶一下這兩個定義:
$O'=\{x \in K^n | x_{m+1}=\cdots=x_n=0\}$
$O=T^{-1}(O')$

也就是說 $\mathrm{ss} \cdot x$ 是 private key $O$ 的一個 vector，如果能找到多個 $x$ 就能得到 $O$ 的整個 basis 了。

不過實際上帶入後會發現 $P(\mathrm{ss} \cdot x) \neq 0$ , why? 因為 $O'$ 能那樣定義的條件是在 $F$ 只有二次項時成立的，而這題的 $P$ 有一次項與常數項因此不成立。真正成立的等式應該是 $Q(\mathrm{ss} \cdot x) = 0$ ，其中 $Q$ (二次項的部分)可以很容易的從 $P$ 中分離出來。

這邊雖然還沒拿到 public key $P$ ，但還是可以 local 生一個自己知道 public key 的 instance 來測試

所以只要:

把各 message 對應的 $v_i$ 整理成 $\mathrm{vs}$ ，求 $x_i$ 使 $\mathrm{vs} \cdot x_i=0$
把各 signature 對應的 $s_i$ 整理成 $\mathrm{ss}$ ，則 $\mathrm{ss} \cdot x_i$ 就是 $O$ 的整個 basis，符合 $Q(O)=0$

就能得到 $O$ 了。

得到 $O$ 之後如果要 forge signature 我們還是會需要 public key，所以要還是要找個方法把 $P$ 求出來。我這邊延續前面說的 linearization 的方法，除了原本 1600 條等式以外我再 sample 一些隨機的 $o \in O$ ，把 $Q(o)=0$ 這部分作為等式加進去直到 rank 足夠為止。此時再去求解就能得到唯一的 $P$ 了，然後也能把 $Q,L,C$ 分離出來。

接下來是 signature forgery 的部分，也就是固定 $t$ 求 $s$ 使得 $P(s)=t$ 的方法。因為這邊有多 $L,C$ 的部分所以會有些不同。首先一樣是先選個 $v$ 作為 $P$ 的 input，找 $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}

因為有 $Q(o)=0, P(v)=Q(v)+L(v)+C$ ，所以整理得到:

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

而左側是整個 linear 的，所以一樣可以解出 $o$ ，因此可以做到任意的 signature forgery。然而這邊還有最後一個問題，就是這個題目要 forge 的 signature 時用的 $v$ 不是隨便選的。從題目我們知道 flag 內容是整個 signature 的 hex，所以這邊並不是任意的 signature 都能作為 flag，而只有透過原本相同 hash function 所生成的那個 $v$ 生成的 signature 才是 flag。

要做到這件事其實沒那麼 trivial，因為這邊的 $v$ 是 $F$ secret_system 的輸入，而不像 signature forgery 那邊一樣 $v$ 是 $P$ 的輸入。兩者間差了一個 $T$ ，也就是說這邊其實要以 $T^{-1}v$ 作為 public vinegar vector 去 forge 的 signature 才會試我們要的 flag!!!

一個可能的做法是想辦法透過 $P$ 與 $O$ ，想辦法分解 $P=F \cdot T$ ，不過這部分我自己是沒想到方法。我這邊用的一個關鍵是說 $P$ domain 的 $v$ ，就算換成任意的 $v'=v+o,o \in O$ 也不會對 signature $s$ 產生任何變化。(why? 我不知道==)

所以利用現成的 signature/message pairs 求 $x$ 使得 $\mathrm{vs} \cdot x = v$ ( $F$ domain 的 $v$ , hash 出來的輸出)，那麼可得:

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

此處 $\mathrm{os}$ 中的向量屬於 $O'$ ，因此 $T^{-1}(\mathrm{os} \cdot x) \in O$ ，也就是說 $\mathrm{ss} \cdot x$ 可以當作我們需要的那個 $T^{-1}v$ 來使用，因為它和真正的 $T^{-1}v$ 只差一個 $O$ 中的向量而已。所以取 $v=\mathrm{ss} \cdot x$ 做 signature forgery，得到的 signature 就是 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 簡介#

解法#