kleinvieh_2

This Challenge was covered in nullcon CTF 2025, this is a writeup.

Before I start I liked this challenge because it's a nice coppersmith exercise, ensuring proper understanding of the technique.

Handouts

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
import math

# Utility functions
def chunks(l : list, n : int):
	"""Yield successive n-sized chunks from l."""
	for i in range(0, len(l), n):
		yield l[i:i + n]

# Encryption Methods

def encrypt1(message : bytes, key):
	return pow(bytes_to_long(message), key.e, key.n)

def encrypt2(message : bytes, key):
	r = 6882340053480090463606763880215995523230790077054797279541
	48955984833460337936950913921276804334830417982234720038650432
	72978049851415599561893741257560419681569060516183575560934138
	10921455481533129431196963983261449026392268314712005423371052
	82064399184931676924592908530791494346900227871404063095592748
	76429602825553057727865668046378265513942121930242289966766533
	92778247184219018318170431595521322520169452263706772780674245
	06514993298100924479619565269428391036310378044733517453768164
	25265593111120208943269707894718448626786594313865983615593934
	31347384089724269793291585060272806532093184794138952597743198
	48662706808171929571545923310500352950348748809789292920278241
	36201527896331548177702899734448017201096029400209857898946908
	92940225901348239139368695489071252944474774307390967674740264
	01347928008150737871869441842515706902681140123776591020038755
	23464218469985651732600457439392216291883939633654162021229687
	08326595761950104668967012490038085535608952398604541628467596
	35434691728716499056221797005696650174933343585361153344017021
	74782738919340566707333344356965956756224740628328245128415514
	97807379047609899109445504993166551283948992292847965847871986
	89342431338201610314893908441661953172106881929330452489260
	return pow(bytes_to_long(message) * r, key.e, key.n)

def encrypt3(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = message + b'\x00' * (bytelength - len(message))
	return pow(bytes_to_long(msg), key.e, key.n)

def encrypt4(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = message * (bytelength // len(message))
	return pow(bytes_to_long(msg), key.e, key.n)

def encrypt5(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = b'\x42' * (bytelength - len(message)) + message
	return pow(bytes_to_long(msg), key.e, key.n)

# Actual code
flag = open('flag.txt','r').read()
messages = [x for x in chunks(flag.encode(), len(flag) // 5 + 1)]

key = RSA.generate(4096, e = 3)
key_file = open('pubkey.pem','wb')
key_file.write(key.public_key().export_key())
key_file.close()

encryptors = [encrypt1,encrypt2,encrypt3,encrypt4,encrypt5]

for i in range(5):
	print(encryptors[i](messages[i], key))

220063927409019701680780388734859413263649938528559880958114989945319210396443096153070875125175228115415476201776095239222264863
521405777679638898956934268538900625825553438750301296652588113926908675649695287473044872094704614120486323959657990026640254596060659622526156708812669359650586620385290808935734592790788255073585330621151468871219769656595135843333814407503403584485725875093573131958504623569333490646639116961719078216840229603919536018487825851994866357917761987217050792416697381377048912395473353778387941958191907824408107449076068401916848269614839157102521989010679392116485801486351905021880108912590420172605418475794616003449288680484874497236175444664128438401914724753429360434711903099273327857734995750524336685921743399501618966233467673179877216701974657036419446491274854437281396070824372634560507303755215464570159167837973755757084277460889038540426254099700613477619367190997235567982845416706558020882785247647017658533190054489579620395565959077232929730085201031313238724372408560517067025821200011117585158799293570307490792480672057216647059928346781983773928742745961020992758462787355967282442061725370293489410415806016306004266400903317110818168429756442671778827765363252714782616931406456862197207387559816797319132734318242504254436838880072071853192476696183220292931118231156006566093505435792459195491243680582
270666484654665630744901461996006692323963839982688652821336211084979467239347411813160298980515940583603861222174521984995420008548684262439808167328926021870579303960012771121601180529687766238396064375729105115543248938593316359682370849163035376370382430086321848989469101241917690539277074390985259902303859203469942292526312785642432913613936993258827179590899881832319079212987637373648192635781867448864854757206430089991579140087742146982306295873762255307312524837239897502872553828380739799963200435212855355849421115331904398013024635259514540481471626803307520164323612306097337438109957993918779265436327033558060626053354750562352860044802675727693412211125966360236444057953485024215560142475510160722114624532935356913983972915673608523025209720167213909179022327299978019112977846926119199262414918029479523990318896183663433071251579236571042002734675157891234966022932698905198698241706452025453847010887618278823570050783989170662300961633292513523806788091889082274722372602239592372048577727269817482906420208931626412130427401917267155522492175168008656904232528370893411707370782832090829602128710489070166301148107529844470225377087526762510454613609000260941022095648201987928579356978933393880920171979201
653824340069025689137734254884130538700629136163559226740194794484993327658776187767570065320577134162743283784425272380809589160993088925874733196055173409287931015748252064633449072261545303183579447460502965342804624603405929157397131141984984644568357653302213965819415468460642952197339991556281367534783709497954301841184449070203282829556818406681886900718807834059676277878423047814575995317125009067646248518224341963179051812872833920966444865854397107596362642091691676816880789051432546280982801936460897107739053704289586862815777802365195344200436339914632247470287475059508482642321374344266084746769130713777040613388188063244264539412036380560226898399218628361640805872727932488302521211097971713325651815102241321497845489911517697687601337373561866169629605144418239966598946278151568343055898100847891792937851579379932984962575775149818916217268297467279875725571404166944999117855879952146915514369003878816227211205583465391314024099614444033724650197415698616726563650695337089763944873372957911180655004798934831152909017151923470147174567931032793367193038245769647005250292165097213630935925441110568790329108402080201984414111112552177466252777781418725448757243067372449888316330317213717511659267093522
358008688390962979576377899144327321078101097951911268175317488500603502519487932330612462905624620597194558963905078036617959827652774950608159539755872698070336695988156123259549872787213397592148258199055613243895883287122890753360508292871837174063088420693224462093920149982044282287843545879889673811146267351528090047294284591799007589644031290908451176760853222636619363811207185693725681140126798792027873548626157363148637874670590965485611082128311321694683523699469128409485949494113757646949983087406842230923148769118322570130431421259760535420603207584288801345366412235455743468488327636151425392848303200702882860489019370153190810988494600882544600108525238483037309140333051358221984674540701977879624246387893765464282113949391789532777484259814371861241414118348867987309273292578129887971446610687731851915056696448523460974558006120340055071716623978233935275849865817975522109696101884471525506261697387468489779620579480299246665603825623773259263912587161909414417437045900004826755951647391749631385635652448151832357232824962202646901774457696625192040117636828038808343932086478692164048901540300465526784540912169577834838256728624868904132298644241575543460006379361856217382572895303794378838795856964

-----BEGIN PUBLIC KEY-----
MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAq0qupn0dQPB2KBxkqKbH
qVdlQVInAL+PVtOIqiPfAKuomeiAPFqSxYnVszx8OX7esMulhF/JXERl17Glc7nr
1f4g5TqCRBdLjn7L5UFQfnTDgs0H0eEEXkDo6ujFrP7SCCjwm4u0YQUE14nIFDk2
eLNj7UHXNXvsTLhdJ6cahmMQ0UpcNLvJ2Utq+mPnxHQ4t8WfAe9LeMGSwyHvN6aW
33crJlWIA7q+USLxqQjfOVX2/nGMh/hUZiWkIWrUu5DrbN187s1UuFp/XMsgfTFM
gAFwe8yzwOS5NBc97H4hBechDSCIpUwYd07pkmPEon7V9sUuQasM84UqgzvSQBTF
vP8uKlzZpnoMIVFQJ1iPOUOsf6RYEhw2rgywIKgWILDUutcrBhMm/sZyYR1IqiYc
QBUaJ9jeCQ8pJk5GtTb2B/MDDlazW37iQmPopUGuaRAkWRVpSENC04/3pa57g0R3
jKffVevsNNOPcdVveZ9CNUJ36ckCHMkVjhtwTj3ChhCJkq0EJsmFZcSMe5dWtUEs
6tZm/OXkyCCIkJW2+9bv6fDxAuGtY6VKHKDYeFS1nfufA8fI7L022O++D9nkLnBX
bbi8dinhS9SfTS9GqR5mbEm5NvGT0bG74YbYO4Oy1GPThJOtMXVuNh1qevzDgKKF
PQlPTql78u4Zhw+T2ukQPGsCAQM=
-----END PUBLIC KEY-----

Analysis & Solver

So generally speaking, our plaintext is segmented into 5 different chunks, each chunk is encrypted using one of the encryptors sequentially, we're given the output of each chunk, and the public key used for encryption.

flag = open('flag.txt','r').read()
messages = [x for x in chunks(flag.encode(), len(flag) // 5 + 1)]

key = RSA.generate(4096, e = 3)

We know that e = 3 and N is 4096 bits long so 512 bytes.

encrypt1

This function encrypts the first chunk of the flag with the public key.

def encrypt1(message : bytes, key):
	return pow(bytes_to_long(message), key.e, key.n)

Now since N is so big and e is so small and the fact the length of each chunk of plaintext is only a fraction of the length of the flag, this makes me think that $pt^e < N$, we can try finding the cubic root.

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from gmpy2 import iroot
from sage.all import *

key = RSA.import_key(open('kleinvieh_2/pubkey.pem').read())


cts = list(map(int,open('kleinvieh_2/output').read().strip().split('\n')))

pts = b''

pt = iroot(cts[0],key.e)[0] 
pts += long_to_bytes(pt)

encrypt2

This function multiplies a big number r with the plaintext chunk then encrypts it with the public key.

def encrypt2(message : bytes, key):
	r = 688234005348009046360676388021599552323079007705479727954148955984833460337936950913921276804334830417982234720038650432729780498514155995618937412575604196815690605161835755609341381092145548153312943119696398326144902639226831471200542337105282064399184931676924592908530791494346900227871404063095592748764296028255530577278656680463782655139421219302422899667665339277824718421901831817043159552132252016945226370677278067424506514993298100924479619565269428391036310378044733517453768164252655931111202089432697078947184486267865943138659836155939343134738408972426979329158506027280653209318479413895259774319848662706808171929571545923310500352950348748809789292920278241362015278963315481777028997344480172010960294002098578989469089294022590134823913936869548907125294447477430739096767474026401347928008150737871869441842515706902681140123776591020038755234642184699856517326004574393922162918839396336541620212296870832659576195010466896701249003808553560895239860454162846759635434691728716499056221797005696650174933343585361153344017021747827389193405667073333443569659567562247406283282451284155149780737904760989910944550499316655128394899229284796584787198689342431338201610314893908441661953172106881929330452489260
	return pow(bytes_to_long(message) * r, key.e, key.n)

In this case, $(pt \times r)^3 > N$, this calls for coppersmith's method.

Coppersmith's Method

There is an advanced technique known as Coppersmith’s method which can sometimes recover small roots of univariate modular polynomial equations. The idea is that if the unknown $m$ (or in this case, $m \times r$ ) is small relative to $N^{\frac{1}{e}}$.

So, (with e=3, roughly if

$$m \times r < N^{\frac{1}{e}}$$

even after reduction), then one might set up a polynomial equation:

$$f(x) = (r\times m)^3 -c \equiv 0\pmod N$$

where 𝑐 is your ciphertext, 𝑟 is the known constant, and the unknown 𝑥 corresponds to the message 𝑚 (since during encryption $f(x) = x * e^{2 pi i \xi x}$$c = (m \times r)^3 \mod N$. The idea is that if the actual value 𝑚 is small enough relative to 𝑛 , then there exists an integer root $x_0$ of $f(x)$ (with $x_0 = m$) that can be recovered by Coppersmith’s method.

r = 688234005348009046360676388021599552323079007705479727954148955984833460337936950913921276804334830417982234720038650432729780498514155995618937412575604196815690605161835755609341381092145548153312943119696398326144902639226831471200542337105282064399184931676924592908530791494346900227871404063095592748764296028255530577278656680463782655139421219302422899667665339277824718421901831817043159552132252016945226370677278067424506514993298100924479619565269428391036310378044733517453768164252655931111202089432697078947184486267865943138659836155939343134738408972426979329158506027280653209318479413895259774319848662706808171929571545923310500352950348748809789292920278241362015278963315481777028997344480172010960294002098578989469089294022590134823913936869548907125294447477430739096767474026401347928008150737871869441842515706902681140123776591020038755234642184699856517326004574393922162918839396336541620212296870832659576195010466896701249003808553560895239860454162846759635434691728716499056221797005696650174933343585361153344017021747827389193405667073333443569659567562247406283282451284155149780737904760989910944550499316655128394899229284796584787198689342431338201610314893908441661953172106881929330452489260
c = cts[1]
n = key.n
R = r ** 3
PR = PolynomialRing(Zmod(n), 'x')
x = PR.gen()
f = PR(R * x ** 3 - c)
f = f.monic()
pt = int(f.small_roots(X = 2 ** 1024, beta = 0.5)[0])
pts += long_to_bytes(pt)

encrypt3

In this case the message is padded with null bytes for the 493 bytes (equalizing the padded plaintext bitlength with Ns bitlength)

def encrypt3(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = message + b'\x00' * (bytelength - len(message))
	return pow(bytes_to_long(msg), key.e, key.n)

what we did is M || "0x00" * 493 which is equivalent to a 493 bit shift to the left and can be represented like this: $c = (pt * 2^{(511 - 18) \times 8})^3 \mod N$, we can map this similarly to encrypt3 where r = 2 ** ((511 - 18) * 8) .

bytelength = int(math.floor(math.log2(key.n))) // 8
message_len = 18
c = cts[2]
n = key.n
R = (2 ** ((bytelength - message_len) * 8)) ** 3
PR = PolynomialRing(Zmod(n), 'x')
x = PR.gen()
f = PR(R * x ** 3 - c)
f = f.monic()
pt = int(f.small_roots(X=2 ** 1024, beta = 0.5)[0])
pts += long_to_bytes(pt)[:-1]

encrypt4

This function pads the message with copies of itself until its bitlength is as long or longer than the bitlength of N.

def encrypt4(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = message * (bytelength // len(message))
	return pow(bytes_to_long(msg), key.e, key.n)

Representing the Repeated Message as an Integer

given that the length of our message (L) = 18

Concatenating bytes is equivalent to “shifting” and adding. In our case, the integer corresponding to the repeated message is

$$msg = M \times S$$

where:

$$S = 256^{0 \times L} + 256^{1 \times L} + 256^{2 \times L} + ... + 256^{(k-1) \times L}$$

Since $256^L = 2^{8\times L}$ the sum S is a geometric series:

$$S = 1 + 256^{L} + 256^{2 L} + ... + 256^{(k-1) L}$$

Its closed‐form is

$$S = \frac {256^{kL} -1}{256^{L} -1}$$

We can represent $c = S^3 * M^3 \mod N$, now if we wanna get rid of that S factor, we can find $a = c \times S^{-3} = M^3 \mod N$

That way we could write our polynomial in the form:

$$f(x) = x^3 - a$$

c = cts[3]
n = key.n
r = pow(256, 18, n)
num = (pow(r, 28, n) - 1) % n
denom = (r - 1) % n
denom_inv = inverse_mod(denom, n)
S_mod_n = (num * denom_inv) % n
S_cubed = pow(S_mod_n, 3, n)
inv_S_cubed = inverse_mod(S_cubed, n)
a = (c * inv_S_cubed) % n
PR = PolynomialRing(Zmod(n), 'x', implementation='NTL')
x = PR.gen()
f = PR(x ** 3 - a)
pt = int(f.small_roots(X = 2 ** (2 ** 18), beta = 0.5)[0])
pts += long_to_bytes(pt)

encrypt5

This encryption pads "B" onto the most siginificant bits of the plaintext until its full bitlength has less than 144 bits difference from the bitlength of N

def encrypt5(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = b'\x42' * (bytelength - len(message)) + message
	return pow(bytes_to_long(msg), key.e, key.n)

$$k=bytelength−L.$$

so k = 511 - 18 = 493 bytes

Representing the Padded Message as an Integer:

Think of the padded message as a number in base 256. The left part is all the constant byte \x42, and the right part is the actual message. This number can be expressed as:

$$m=S\times256^L+M$$

where:

• M is the integer representation of the original 18-byte message.

• S represents the contribution of the repeated \x42 bytes.

  Since each \x42 corresponds to the number 0x42, and there are k=493 of them, concatenated in base 256, we have:

$$S = \text{0x42} \times (1 + 256^{0} + 256^{1} +256^{2} + ... + 256^{(k-1)})$$

Its closed-form is:

$$S = \text{0x42} \times \frac {256^{k} -1}{256 -1}$$

We can represent $c \equiv (S \times 256^{18} + M)^3 \pmod N$, let us set $A = S \times 256^{18}$, we can represent our polynomial

That way we could write our polynomial in the form:

$$f(x) = (x + A)^3 - c \mod N$$

and solve for 0.

c = cts[4]
n = key.n
num = (pow(256, 493 , n) - 1) % n
denom = 255 % n
denom_inv = inverse_mod(denom, n)
S = (0x42 * num * denom_inv) % n
A = (S * pow(256, 18, n)) % n
PR = PolynomialRing(Zmod(n), 'x', implementation='NTL')
x = PR.gen()
f = PR((x + A )**3 - c)
pt = int(f.small_roots(X=2**144, beta=1, epsilon = 0.05)[0])
pts += long_to_bytes(pt)
print(pts)

ENO{s0m3_0f_th35e_me1hod5_4ctua1ly_h4d_th3_sam3_1de3_th4t_i5_why_1t_i5_ju5t_1_ch4ll3nge}