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

# kleinvieh\_2

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

## Handouts

```python
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.

```python
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.

```python
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.

```python
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.

```python
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.

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

```python
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)` .

```python
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.

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

<figure><img src="https://427275427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FHsQs1QxfvG7fIv03WKVZ%2Fuploads%2FEiPaKAmlNi1EpWKcCFTv%2Fimage.png?alt=media&#x26;token=d835f752-03f5-4aca-9e71-2bb9666f25a7" alt=""><figcaption></figcaption></figure>

#### 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
$$

```python
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

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

<figure><img src="https://427275427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FHsQs1QxfvG7fIv03WKVZ%2Fuploads%2FaSE0Nfp7uQONEdV0dwYY%2Fimage.png?alt=media&#x26;token=55c9431f-d428-4145-8a44-893c36eb12fa" alt=""><figcaption></figcaption></figure>

$$
k=bytelength−L.
$$

so k = 511 - 18 = 493 bytes&#x20;

**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.

```python
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}
```
