PBCTF 2020 Writeups

December 7, 2020

crypto writeup

PBCTF 2020 Writeups

Crypto

I have participated in PBCTF 2020 as a member of zer0pts and We won the CTF 🥳

Queensarah2

challenge.py

#!/usr/bin/env python3

from string import ascii_lowercase
from itertools import product
from random import SystemRandom
from math import ceil, log
from secretstuff import FLAG

random = SystemRandom()
ALPHABET = ascii_lowercase + "_"
assert all(char in ALPHABET for char in FLAG)

bigrams = [''.join(bigram) for bigram in product(ALPHABET, repeat=2)]
random.shuffle(bigrams)

S_box = {}
for i in range(len(ALPHABET)):
    for j in range(len(ALPHABET)):
        S_box[ALPHABET[i]+ALPHABET[j]] = bigrams[i*len(ALPHABET) + j]
        # map bigrams -> random.shuffle(bigrams)
assert len(set(S_box.keys())) == 27*27

def encrypt(message):
    if len(message) % 2:
        message += "_"

    message = list(message)
    rounds = int(2 * ceil(log(len(message), 2))) # The most secure amount of rounds

    for round in range(rounds):
        # Encrypt
        for i in range(0, len(message), 2):
            message[i:i+2] = S_box[''.join(message[i:i+2])]

        # Shuffle, but not in the final round
        if round < (rounds-1):
            message = [message[i] for i in range(len(message)) if i%2 == 0] + [message[i] for i in range(len(message)) if i%2 == 1]

    return ''.join(message)


if __name__ == "__main__":
    print("This is a restricted service! Decrypt this password to proceed:")
    print({encrypt(FLAG)})

    for _ in range(1500):
        question = input("> ").strip()
        assert 0 < len(question) <= 10000

        if not question:
            print("Bye.")
            break

        elif question == FLAG:
            print(f"You got it. The flag is pbctf{{{FLAG}}} ")
            break

        else:
            print("That's not quite right. Your password encrypts to this:")
            print(encrypt(question))

Challenge implements an encryption function and gives us the flag encrypted with it at the start of the connection. We can request the server for the encryption of plaintexts for 1500 times.

encryption function is substitution followed by permutation for n rounds.n depends on the plaintext length.

We know the permutation used and knowledge of the substitution box would suffice to write a decryption routine, eventually get the flag :)

Let S represent the substitution which basically maps a bigram to bigram and is bijective.

Because of the permutation used in the encryption function, encryption of a bigram ($i$) is equal to $S(S(i))$.

Let’s consider an small $S$ to understand how we can use this information ($i$, $S(S(i))$) to recover $S$.

S = {0: 1, 1: 2, 2: 3, 3: 0, 4: 5, 5: 4, 6: 6, 7: 8, 8: 9, 9: 7}

if we consider $S$ as Permutation Group then mapping $i$ to $S(S(i))$ is $S^{2}$

$$S = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9 \\ 1&2&3&0&5&4&6&8&9&7 \end{pmatrix} = (0\ 1\ 2\ 3)(4\ 5)(6)(7\ 8\ 9)$$

and

$$S^{2} = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9 \\ 2&3&0&1&4&5&6&9&7&8 \end{pmatrix} = (0\ 2)(1\ 3)(4)(5)(6)(7\ 9\ 8)$$

consider a cycle with odd length from $S$ : $(7\ 8\ 9)$

$$S(S(7)) = 9,\ \ S(S(9)) = 8,\ \ S(S(8)) = 7$$

The resulting elements form a cycle of $S^{2}$ : $(7\ 9\ 8)$

Now, considering a cycle of even length : $(0\ 1\ 2\ 3)$

$$S(S(0)) = 2,\ \ S(S(2)) = 0,\ \ S(S(1)) = 3,\ \ S(S(3)) = 1$$

similarly, resulting elements form cycles of $S^{2}$: $(0\ 2)$, $(1\ 3)$

It’s quite easy to observe that

Every even length cycle in $S$ will break into 2 equal size cycles in $S^{2}$.
Every even length cycle in $S^{2}$ is part of bigger cycle(double it’s length) in $S$
Every odd length cycle in $S$ will have a cycle with the same length and same elements but with different order in $S^{2}$

After extracting $S^{2}$ from server, we can use above rules to recover most part of the $S$.
A little bruteforce is needed for combining cycles
consider above example, combining $(0\ 2),\ \ (1\ 3)$ could result in $(0\ 1\ 2\ 3)$ or $(0\ 3\ 2\ 1)$

after calculating $S$, it’s straightforward to decrypt the flag ciphertext.

FLAG :: pbctf{slide_attack_still_relevant_for_home_rolled_crypto_systems}

#!/usr/bin/env python3
import ast

from string import ascii_lowercase
from itertools import product
from math import ceil, log

def construct_cycles(sbox):
	# construct cyclic representation of sbox permutation
	bigrams = list(sbox.keys())
	cycles = []
	while len(bigrams) > 0:
		current = []
		i = bigrams[0]
		while i not in current:
			current.append(i)
			i = sbox[i]
			bigrams.remove(i)
		cycles.append(current)
	return cycles

def construct_single_cycle(double_cycle):
	""" 
	ex:
	double_cycle - (1 3 5 7 2 4 6)
	single_cycle - (1 2 3 4 5 6 7)
	"""
	assert len(double_cycle) % 2 == 1

	single_cycle = [None] * len(double_cycle)
	i = 0
	j = 0
	while None in single_cycle:
		single_cycle[i] = double_cycle[j]
		i = (i + 2) % len(double_cycle)
		j = (j + 1)
	return single_cycle

def combine_double_cycles(c1, c2):
	"""
	join 2 double cycles 
	ex: 
	double_cycle_1 = (1 3 5)
	double_cycle_2 = (2 4 6)
	
	res -->	(1 2 3 4 5 6)
	"""
	single_cycle = [None] * (len(c1)*2)
	assert len(c1) == len(c2)
	j = 0
	for i in range(0, len(single_cycle), 2):
		single_cycle[i] = c1[j]
		single_cycle[i + 1] = c2[j]
		j += 1
	return single_cycle

def construct_sbox(cycles):
	"""
	convert cyclic representation of a permutation to 
	a mapping
	"""
	sbox = {}
	for cur in cycles:
		# print(cur)
		for i in range(len(cur)):
			sbox[cur[i]] = cur[(i + 1) % len(cur)]
	return sbox

def encrypt(S_box, message):
    if len(message) % 2:
        message += "_"
    message = list(message)
    rounds = int(2 * ceil(log(len(message), 2))) # The most secure amount of rounds
    for round in range(rounds):
        # Encrypt
        for i in range(0, len(message), 2):
            message[i:i+2] = S_box[''.join(message[i:i+2])]

        # Shuffle, but not in the final round
        if round < (rounds-1):
            message = [message[i] for i in range(len(message)) if i%2 == 0] + [message[i] for i in range(len(message)) if i%2 == 1]

    return ''.join(message)

def decrypt(S_box, ct):
    S_box = reverse_sbox(S_box)
    ct = list(ct)
    rounds = int(2 * ceil(log(len(ct), 2)))
    for round in range(rounds):
        for i in range(0, len(ct), 2):
            ct[i:i+2] = S_box[''.join(ct[i:i+2])]
        if round < (rounds-1):
            nct = [None] * len(ct)
            for i in range(len(ct) // 2):
            	nct[i*2] = ct[i]
            	nct[i*2 + 1] = ct[i + (len(ct)//2)]
            ct = nct
    return ''.join(ct)

def reverse_sbox(sbox):
	rev_sbox = {}
	for i in sbox:
		rev_sbox[sbox[i]] = i
	return rev_sbox

def check_sbox(sbox, pt_ct):
	for pt in pt_ct:
		cti = encrypt(sbox, pt)
		if not cti == pt_ct[pt]:
			return False
	return True

"""
Note: the below part of the program contains hardcoded values
calculated using the data collected.
I haven't wrote a general version(yet)
"""

with open("tmp_output", "r") as f:
	data = f.read()

data = ast.literal_eval(data)

# data collected from the server
flag_ct, double_sbox, tmp_cts = data

flag_ct = flag_ct.strip()[2:-2]

tmp_pts = ["a" * 8, "b" * 8, "c" * 8]

# to validate generated sboxs
pt_ct_pairs = {}
for pt, ct in zip(tmp_pts, tmp_cts):
	pt_ct_pairs[pt] = ct

# convert double sbox (S_box[S_box[i]]) to cyclic representation
cycles = construct_cycles(double_sbox)

print("cycle lengths = ", [len(i) for i in cycles])

cycle_lengths = [len(i) for i in cycles]
# known_encs = []

# single_cycles contain cycles of odd length in original S_box
single_cycles = []
remaining_cycles = []
for cycle in cycles:
	if cycle_lengths.count(len(cycle)) == 1:
		single_cycles.append(construct_single_cycle(cycle))
	else:
		remaining_cycles.append(cycle)

print("remaining_cycle_lengths = ", [len(i) for i in remaining_cycles])

cycles_258 = [i for i in remaining_cycles if len(i) == 258]
cycles_6 = [i for i in remaining_cycles if len(i) == 6]
cycles_1 = [i for i in remaining_cycles if len(i) == 1]

possible_flags = []

for i1 in range(258):
	t1_single_cycles = single_cycles[::]
	s_c258 = combine_double_cycles(cycles_258[0], cycles_258[1][i1:] + cycles_258[1][:i1])
	t1_single_cycles.append(s_c258)
	for i2 in range(6):	
		s_c6 = combine_double_cycles(cycles_6[0], cycles_6[1][i2:] + cycles_6[1][:i2])
		t2_single_cycles = t1_single_cycles + [s_c6]
		
		combs = [(0, 1, 2), (1, 2, 0), (0, 2, 1)]
		# bruteforce cycles one of size 2 and another of 1 
		for comb in combs:
			final_single_cycles = [combine_double_cycles(cycles_1[comb[0]], cycles_1[comb[1]])]
			final_single_cycles += t2_single_cycles
			final_single_cycles += [cycles_1[comb[2]]]
			t_sbox = construct_sbox(final_single_cycles)
			if check_sbox(t_sbox, pt_ct_pairs):
				print("decrypted_flag =", decrypt(t_sbox, flag_ct))
				possible_flags.append(decrypt(t_sbox, flag_ct))
		# check for cycles of size 1 each 
		final_single_cycles = [bigram for bigram in cycles_1]
		final_single_cycles += t2_single_cycles
		t_sbox = construct_sbox(final_single_cycles)
		if check_sbox(t_sbox, pt_ct_pairs):
			print("decrypted_flag = ", decrypt(t_sbox, flag_ct))
			possible_flags.append(decrypt(t_sbox, flag_ct))

print("possible flags\n")
for flag in possible_flags:
	print("pbctf{{{}}}".format(flag))

"""
cycle lengths =  [81, 258, 258, 117, 6, 6, 1, 1, 1]
remaining_cycle_lengths =  [258, 258, 6, 6, 1, 1, 1]
decrypted_flag = slide_attack_stihclcelevant_for_home_rolled_crypto_systems
decrypted_flag = slide_attack_stiptqcgnqbeot_for_home_rolled_crypto_systems
decrypted_flag = slide_attack_stillineaxozqt_for_home_rolled_crypto_systems
decrypted_flag =  slide_attack_still_relevant_for_home_rolled_crypto_systems
possible flags

pbctf{slide_attack_stihclcelevant_for_home_rolled_crypto_systems}
pbctf{slide_attack_stiptqcgnqbeot_for_home_rolled_crypto_systems}
pbctf{slide_attack_stillineaxozqt_for_home_rolled_crypto_systems}
pbctf{slide_attack_still_relevant_for_home_rolled_crypto_systems}
"""

# FLAG :: pbctf{slide_attack_still_relevant_for_home_rolled_crypto_systems}

LeaK

challenge.py

#!/usr/bin/env python3

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Private_key
import hashlib
import random

g = SECP256k1.generator
order = int(SECP256k1.order)
secret = random.randrange(2, order - 1)
pubkey = Public_key(g, g * secret)
privkey = Private_key(pubkey, secret)

arr = []
for i in range():
    h = random.randrange(2, order - 1)
    k = random.randrange(2, order - 1)
    sig = privkey.sign(h, k)
    print(k)
    lea_k = int("0x" + "{:064x}".format(k)[10:-10], 16)
    arr.append((h, lea_k, int(sig.r), int(sig.s)))

sha256 = hashlib.sha256()
sha256.update(str(secret).encode())
key = sha256.digest()

aes = AES.new(key, mode=AES.MODE_ECB)
print(aes.encrypt(pad(flag, 16)).hex())

This is a classic(kind of) challenge based on leaked nonces of ecdsa. We were given 30 signatures along with the consecutive middle bits of the corresponding nonce used in signing process.

Similar to most challenges based on leaked nonces, this could be solved by finding paper discussing this problem and implementing algorthim given in that. It’s quite easy to find such paper.
paper “A Tale of Three Signatures: Practical Attack of ECDSA with wNAF” (link) worked for me.
Though linking solution code would suffice, I’m gonna take a chance and try to explain my take on the solution.for that I will pretend like I haven’t read the paper for a moment.

Let $q$ be a prime number and $\ \alpha, k, r, s, h\ \in \ \mathbb{Z}/q\mathbb{Z}$.

ECDSA signature is calculated as

$$s = k^{-1}(h + r\alpha)\ \ \ \ (mod\ q)$$

where $(r, s)$ is the signature, $k$ is the nonce, $h$ is hash of the message and $\alpha$ is the private exponent.

$$r\alpha = sk - h\ \ \ \ (mod\ q)$$

let

$$k = d_{1} + a + bd_{2} \tag{eq 1}$$

implies

$$r\alpha = s(d_{1} + a + bd_{2}) - h\ \ \ \ \ (mod\ q)$$ $$r\alpha - sd_{1} - sbd_{2} - (sa - h) = 0\ \ \ \ \ (mod\ q)$$

Let Equation $E_{i}$ be

$$r_{i}\alpha - s_{i}d_{i1} - s_{i}b_{i}d_{i2} - (s_{i}a_{i} - h_{i}) = 0\ \ \ \ \ (mod\ q)$$

let $u$ be the number of signatures avaliable

for $2\leq i \leq u$ consider $r_{1}E_{i} - r_{i}E_{1}$

$$-r_{1}s_{i}d_{i1} - r_{1}s_{i}b_{i}d_{i2} - r_{1}(s_{i}a_{i} - h_{i}) + r_{i}s_{1}d_{11} + r_{i}s_{1}b_{1}d_{12} + r_{i}(s_{1}a_{1} - h_{i}) = 0\ \ \ \ \ (mod\ q)$$ $$r_{i}s_{1}d_{11} + r_{i}s_{1}b_{1}d_{12} + (-r_{1}s_{i})d_{i1} + (-r_{1}s_{i}b_{i})d_{i2} - (r_{1}(s_{i}a_{i} - h_{i}) - r_{i}(s_{1}a_{1} - h_{i})) = 0\ \ \ \ \ (mod\ q)$$

for $2\leq i \leq u$ let $\tau_{i1} = r_{i}s_{1},\ \tau_{i2} = r_{i}s_{1}b_{1},\ \sigma_{i1} = -r_{1}s_{i},\ \sigma_{i2} = -r_{1}s_{i}b_{i},\ \gamma = r_{1}(s_{i}a_{i} - h_{i}) - r_{i}(s_{1}a_{1} - h_{i})$

Above equation can be written as

$$\tau_{i1}d_{11} + \tau_{i2}d_{12} + \sigma_{i1}d_{i1} + \sigma_{i1}d_{i2} - \gamma_{i} = 0\ \ \ \ \ (mod\ q),\ \ \ 2\leq i \leq u \tag{eq 2}$$

for this challenge $q, \alpha, k, s, h, r$ are of size 256 bits each and total of $u = 30$ signatures are given.
for each signature middle(40-256) bits of k are given.

$$k = d_{i1} + 2^{40}leak_{i} + 2^{256-40}d_{i2}$$

we don’t know the values of $d_{i1}, d_{i2}$, knowing them would allow us to calculate $k$ and ultimately calculate secret exponent $\alpha$.
let $\mu_{ij}$ be the bit length of $d_{ij}$ and $m = \max_{ij}\mu_{ij}$, In our case $\mu_{ij} = 40$ and $m = 40$
with each signature, $a_{i} = 2^{40}leak_{i}, b_{i} = 2^{256-40}$ we could derive equations of form $(eq\ 2)$

$$\tau_{i1}d_{11} + \tau_{i2}d_{12} + \sigma_{i1}d_{i1} + \sigma_{i1}d_{i2} - \gamma_{i} = 0\ \ \ \ \ (mod\ q),\ \ \ 2\leq i \leq u$$ $$\tau_{i1}d_{11} + \tau_{i2}d_{12} + \sigma_{i1}d_{i1} + \sigma_{i1}d_{i2} - \gamma_{i} - t_{i}q = 0\ \ \ \ \ \ \ \ \ \ \ \ \ 2\leq i \leq u$$

Now, we have collection of equations with “small” unknowns result in “small” value (not just small but $0$).LLL works great with this type of linear equations.
so, we have to construct a Basis $B$ and hope that LLL(treat this as a black box) finds a short vector in the lattice generated by $B$ which contains information about unknowns.

It’s upto to us to construct such Basis $B$ which contains a short vector and statisfies certain bounds so that LLL could find it.

Every vector in a lattice is linear combination of basis vectors which we represent as row vectors in matrix $B$.
So, let’s try to build a matrix $A$ using the equations so that linear combinations of row vectors will result in rhs of them. (linear combination of row vectors is nothing but left multiplication of $A$ i.e $xA$)

$$\tau_{i1}d_{11} + \tau_{i2}d_{12} + \sigma_{i1}d_{i1} + \sigma_{i1}d_{i2} - \gamma_{i} - t_{i}q = 0\ \ \ \ \ \ \ \ \ \ \ \ \ 2\leq i \leq u$$

each equation corresponds to a column in $A$ and we want $x\ in\ xA$ to have unknows as entries.

– each coefficient of $q$ $(-t_{i})$ are different. so, a $q$ goes into a new row for each equation
– coefficient of $\tau_{i1}$ are all $d_{11}$. $\tau_{i1}, 2\leq i\leq u$ go into same row
– similarly $\tau_{i2}, 2\leq i\leq u$ go into same row
– coefficient of $\sigma_{i1}$ and $\sigma_{i2}$ are different.so, each go into a new row

$A$ would be

$$A = \begin{bmatrix} q&0&\cdots&0 \\ 0&q&\cdots&0 \\ & &\ddots& \\ 0&0&\cdots&q \\ \tau_{21}&\tau_{31}&\cdots&\tau_{u1} \\ \tau_{22}&\tau_{32}&\cdots&\tau_{u2} \\ \sigma_{21}&0&\cdots&0 \\ \sigma_{22}&0&\cdots&0 \\ 0&\sigma_{31}&\cdots&0 \\ 0&\sigma_{32}&\cdots&0 \\ & &\ddots& \\ 0&0&\cdots&\sigma_{u1} \\ 0&0&\cdots&\sigma_{u2} \\ \gamma_{2}&\gamma_{3}&\cdots&\gamma_{u} \end{bmatrix}$$

and $x = \begin{pmatrix}t_{2}&t_{3}&\cdots&t_{u}&d_{11}&d_{12}&d_{21}&\cdots&d_{u1}&d_{u2}&-1\end{pmatrix}$, $xA = 0$
LLL would find us a short vector given a basis and we know unknows($d_{ij}$) are small.it’s logical to consider a vector with entries $d_{ij}$ as a short vector.
$x$ contains $d_{ij}$.so, we can add more columns to $A$ with non zero diagonal entries $(c_{ij})$

$$A = \begin{bmatrix} q&\cdots&0&0 \\ &\ddots& \\ 0&\cdots&q&0 \\ \tau_{21}&\cdots&\tau_{u1}&c_{11} \\ \tau_{22}&\cdots&\tau_{u2}& &c_{12} \\ \sigma_{21}&\cdots&0& & &c_{21} \\ \sigma_{22}&\cdots&0& & & &c_{22} \\ &\ddots&0& & & & &\ddots \\ 0&\cdots&\sigma_{u1}& & & & & &c_{u1} \\ 0&\cdots&\sigma_{u2}& & & & & & &c_{u1} \\ \gamma_{2}&\cdots&\gamma_{u} \end{bmatrix}$$

$xA = (0,\ \cdots,\ 0,\ c_{11}d_{11},\ c_{12}d_{12},\ \cdots,\ c_{u1}d_{u1},\ c_{u2}d_{u2})$ is definitely a short vector.
Now, consider the following basis $B$ obtained by applying few changes to matrix $A$.(I will explain the reasons behind this changes later in the post)

$$B = \begin{bmatrix} 2^{m}q&\cdots&0&0 \\ &\ddots& \\ 0&\cdots&2^{m}q&0 \\ 2^{m}\tau_{21}&\cdots&2^{m}\tau_{u1}&2^{m-\mu_{11}}\\ 2^{m}\tau_{22}&\cdots&2^{m}\tau_{u2}& &2^{m-\mu_{12}} \\ 2^{m}\sigma_{21}&\cdots&0& & &2^{m-\mu_{21}} \\ 2^{m}\sigma_{22}&\cdots&0& & & &2^{m-\mu_{22}} \\ &\ddots&0& & & & &\ddots \\ 0&\cdots&2^{m}\sigma_{u1}& & & & & &2^{m-\mu_{u1}} \\ 0&\cdots&2^{m}\sigma_{u2}& & & & & & &2^{m-\mu_{u2}} \\ 2^{m}\gamma_{2}&\cdots&2^{m}\gamma_{u}&2^{m-1}&2^{m-1}&\cdots& & & &2^{m-1}&2^{m-1} \end{bmatrix}$$

let $v = \begin{pmatrix}t_{2}&t_{3}&\cdots&t_{u}&d_{11}&d_{12}&d_{21}&\cdots&d_{u1}&d_{u2}&-1\end{pmatrix}$ $w = vB = (0,\ \cdots,\ 0,\ d_{11}2^{m-\mu_{11}} - 2^{m-1},\ d_{12}2^{m-\mu_{12}} - 2^{m-1},\ \cdots,\ d_{u1}2^{m-\mu_{u1}} - 2^{m-1},\ d_{u2}2^{m-\mu_{u2}} - 2^{m-1}, -2^{m-1})$ as $w = vB$, $w \in \mathcal{L}$ and $\forall\ y\ \in w\ \ \lvert y \rvert \leq 2^{m-1}$. so, $w$ is a short vector and LLL will find it.

Final solution for this challenge is:

calculate $\tau_{ij}, \sigma_{ij}, \gamma_{ij}$ from the signatures
construct basis $B$ and apply reduction algorithm(LLL) on it
find our target vector in the reduced basis and extract a $d_{i1},\ d_{i2}$ pair
calculate secret key using extracted values and decrypt the flag.easy peasy :wink:

FLAG :: pbctf{!!!_https://eprint.iacr.org/2019/023.pdf_$$$}

Reasons(I believe) for why we did few things the way we did

we have calculated $r_{1}E_{i} - r_{i}E_{1}$, instead of directly using $E_{i}$ to reduce the Lattice dimension for faster basis reduction
we have added an extra column at the end to the matrix $A$ cause $A$ is not really a basis because of redundancies as $A$ has $n+1$ vectors of degree $n$. And entry of that column could be used to identify the target vector in the reduced basis.
we used $c_{ij} = 2^{m-\mu_{ij}}$. $\ \ c_{ij}$ could be any nonzero value.remember that $\mu_{ij}$ is the bitlength of $d_{ij}$ and $m = \max_{ij}\mu_{ij}$. In our target short vector we have terms $c_{ij}d_{ij}$. with $c_{ij} = 2^{m-\mu_{ij}}$, $c_{ij}d_{ij} = 2^{m-\mu_{ij}}d_{ij}$ and $d_{ij}$ are of bitlength $\mu_{ij}$, therefore $2^{m-\mu_{ij}}d_{ij} \approx 2^{m}$ as a result all the terms in our target vector will have same size.
we changed entries of the last row to $2^{m-1}$ when they could have been $0$.the reason for this is, our target vector is linear combinations of row vectors of B and for our target vector, linear combination of all rows except the last will have entries of size $2^{m}$ and last row vector is subtracted from that to obtain the target vector. if last row entries are $0$ then target vector entries would be $0 < w_{i} < 2^{m}$, if they are $2^{m-1}$ then $-2^{m-1} < w_{i} < 2^{m-1}$ and this helps us cause LLL reduction algorithm uses Euclidean norm to decide size of the vectors and Euclidean norm doesn’t change based on the sign(uses squares of them). so, our target vector is much shorter with respect to LLL.
Above, I said that $c_{ij} = 2^{m-\mu_{ij}}$ to make entries of the target vector to have same size but why $2^{m}$? why not let’s say $\delta$ less than $2^{m}$.suppose we want to use $\delta$ instead of $2^{m}$ then we could set $c_{ij} = \delta/\mu_{ij}$ and last row entries to $\delta/2$ to achieve the same i.e entries of our target vector will be of same size and range is also converted to $-\delta/2 < w_{i} < \delta/2$. but now few of the entries will be Rational numbers. so, the lattice is now on Rational numbers and to avoid that i.e in order to ensure that all the entries are integer values. $\delta$ is set to $1$ and entire basis $B$ is scaled with $2^{m}$

Oof, This is the longest writeup I’ve written.if you find any mistake or didn’t understand anything, feel free to DM me @S3v3ru5_

if you want to learn more about this type of challenges. keywords “Hidden Number problem”, “Extended Hidden Number problem”, “Biased nonce”, “leaked nonce” should help you while searching.

def parse_output():
	import ast
	with open("output") as f:
		data = f.read().strip()
	return ast.literal_eval(data)

def gen_tau_sigma(sigs, modulus):
	K = 2**40
	li = 2
	u = 30
	h1, leak1, r1, s1 = sigs[0]
	vals = []

	# (τ1,i)*d11 + (τ2,i)*d12 + (σi,1)*di1 + (σi,1)*di2 - γi = 0 mod q
	for i in range(1, len(sigs)):
		hi, leaki, ri, si = sigs[i]

		# γi = r1(siki − H(mi)) − ri(s1k1 − H(m1)) mod q
		gamma_i = r1*(si*leaki*K - hi) - ri*(s1*leak1*K - h1)
		gamma_i = gamma_i % modulus

		# τ1,i = r1si
		# τ2,i = s1ri(2^(256 - 40))
		taus = []
		taus.append((ri*s1) % modulus)
		taus.append((ri*s1*(2**(256 - 40))) % modulus)

		# σi,1 = -r1*si
		# σi,2 = -r1*si*(2^(256 - 40))
		sigmas = []
		sigmas.append((-r1*si) % modulus)
		sigmas.append((-r1*si*(2**(256 - 40))) % modulus)

		vals.append((taus, sigmas, gamma_i))

	return vals

def construct_B(vals, modulus):
	u = 30
	li = 2
	mu_ij = 40
	m_ = 40
	q = modulus
	T = 60
	pow_2_m = 2**m_
	inc_factor = 1 # Δ

	B = matrix.zero(ZZ, T + u)

	# fill diagonal
	tmp = (2**m_) * q
	for i in range(u - 1):
		B[i, i] = tmp * inc_factor
	for i in range(u - 1, B.nrows() - 1):
		B[i, i] = 1
	B[-1, -1] = 2**(m_ - 1)

	# fill taus (τ)
	row_ind = u - 1
	for tau_ind in range(u - 1):
		tau = vals[tau_ind][0]
		for i in range(li):
			B[row_ind + i, tau_ind] = tau[i] * pow_2_m * inc_factor

	# fill sigmas (σ)
	row_ind = row_ind + li
	for col_ind in range(u - 1):
		sigma = vals[col_ind][1]
		for i in range(li):
			B[row_ind + i, col_ind] = sigma[i] * pow_2_m * inc_factor
		row_ind += li
	
	assert (row_ind == B.nrows() - 1), f"{row_ind}, {B.nrows()}"
	
	# fill gamma vals (γ)
	for col_ind in range(u-1):
		B[row_ind, col_ind] = vals[col_ind][2] * pow_2_m * inc_factor
	tmp = 2**(m_ - 1)
	for col_ind in range(u - 1, B.ncols()):
		B[row_ind, col_ind] = tmp
	return B

def check_dis(vals, dis, modulus):
	# check given dis are correct or not 
	# by checking if they are zeros to the
	# generated equations
	# i.e (τ1,i)*d11 + (τ2,i)*d12 + (σi,1)*di1 + (σi,1)*di2 - γi = 0 mod q 
	u = 30
	d11 = dis[0][0]
	d12 = dis[0][1]
	checks = []
	for i in range(u - 1):
		taus, sigmas, gamma_i = vals[i]
		di1, di2 = dis[i + 1]
		res = taus[0]*d11 + taus[1] * d12
		res = res + sigmas[0]*di1 + sigmas[1]*di2
		res = res - gamma_i
		checks.append((res % modulus) == 0)
	return checks

def calc_priv(sigs, dis, modulus):
	# calculate private keys using dis
	# ki = di1 + leak*2^40 + di2*2^(256-40)
	# si*ki = hi + ri*private_key
	# private_key = (siki - hi)/ri
	privs = []
	u = 30
	for i in range(u):
		di1, di2 = dis[i]
		hi, leaki, ri, si = sigs[i]
		ki = di1 + leaki*(2**40) + di2*(2**(256 - 40))

		alpha = (ki*si - hi) % modulus
		alpha = alpha * inverse_mod(ri, modulus)
		alpha = alpha % modulus
		privs.append(alpha)
	assert len(set(privs)) == 1
	return privs[0]

def decrypt(secret):
	import hashlib
	from Crypto.Cipher import AES
	sha256 = hashlib.sha256()
	sha256.update(str(secret).encode())
	key = sha256.digest()
	aes = AES.new(key, mode=AES.MODE_ECB)
	ct = bytes.fromhex("8d47217b47714708b39befc5bef252e621d3c10fdb1d8d6168c62c4f7b981c185b44a907c9db378b1bfd3b984262ad157ead801493286eb877e7c774978c3f4d")
	return aes.decrypt(ct)

sigs = parse_output()
u = 30
li = 2
mu_ij = 40
m_ = 40

q = 115792089237316195423570985008687907852837564279074904382605163141518161494337
T = 60
modulus = q
vals = gen_tau_sigma(sigs, q)
B = construct_B(vals, q)

M = B.LLL()

ww = M[0]
vv = B.solve_left(ww)

if vv[-1] == 1:
	vv = vv*-1

dis = list(map(Integer, vv[u - 1: -1]))
dis = [(dis[i], dis[i+1]) for i in range(0, len(dis), 2)]
assert all(check_dis(vals, dis, modulus)), "Busted"

secret_key = calc_priv(sigs, dis, modulus)

flag = decrypt(secret_key)
print("flag =", flag[:-flag[-1]].decode())

"""
flag = pbctf{!!!_https://eprint.iacr.org/2019/023.pdf_$$$}

References:
[1] Gabrielle De Micheli, Rémi Piau, Cécile Pierrot  A Tale of Three Signatures: Practical Attack of ECDSA with wNAF
https://link.springer.com/chapter/10.1007/978-3-030-51938-4_18
"""

Special gift and it’s revenge

challenge.py

#!/usr/bin/env python3

from Crypto.Util.number import getStrongPrime, inverse, bytes_to_long, GCD as gcd
from Crypto.Random.random import randint
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q
phi = (p - 1) * (q - 1)

# Hehe, boi
while True:
    d = randint(int(N ** 0.399), int(N ** 0.4))
    if gcd(d, phi) == 1:
        break

e = inverse(d, phi)

# Here's a special gift. Big.
gift = d >> 120

enc = pow(bytes_to_long(flag), e, N)

print("N =", N)
print("e =", e)
print("gift =", gift)
print("enc =", enc)

RSA key is generated and msb bits of the private exponent($d$) are given along with the public key$(N, e)$.
for Special Gift challenge $d \approx N^{0.4}$ and for Special Gift revenge $d \approx N^{0.6}$.
I have implemented algorithms given in paper “Partial Key Exposure Attacks on RSA up to Full Size Exponents”(link). Algorithm described in section 4.1.1 works for the Special Gift challenge and Algorithm described in section 4.1.2 works for the Special Gift Revenge challenge. There are few things I don’t understand completely in these algorithm so I’m not gonna try to explain this algorithm as I did for LeaK.
solve.sage

def find_z0(pol, f1, f2):
	"""
	find root z0
	given (x0, y0, z0) is roots of pol, f1, f2
	and f1, f2 are not multiples of pol
	on the assumption that 
	resultant computations of polynomials yield non-zero polynomials 
	"""
	x, y, z = pol.parent().gens()

	PZ = PolynomialRing(IntegerRing(), "zn")
	zn = PZ.gen()

	r1 = f1.resultant(pol, x)
	r2 = f2.resultant(pol, x)
	r3 = r1.resultant(r2, y)
	
	check = r3 - r3.constant_coefficient()
	if check == 0:
		return False, None
	
	final_pol = r3.subs(z = zn)
	
	if type(final_pol) == type(Integer()):
		return False, None
	
	z_roots = list(map(lambda t: t[0], final_pol.roots()))
	
	if len(z_roots) == 0:
		return False, None
	if len(z_roots) == 1 and z_roots[0] == 0:
		return False, None
	
	return True, z_roots

def root_z0(HH, pol):
	"""
	from the reduced polynomials find f1, f2 such that
	f1(x0, y0, z0) = f2(x0, y0, z0) == 0, 
	f1 % pol != 0, f2 % pol != 0
	and find root z0
	"""
	D = {}
	for i in HH:
		if HH[i] % pol != 0:
			D[i] = HH[i]
	if len(D.keys()) == 0:
		print("All are multpliers of pol")
		return []
	res = []
	poss = list(D.keys())
	if 0 in poss:
		poss.remove(0)
	for i, j in Combinations(poss, 2):
		found, root = find_z0(pol, D[i], D[j])
		if found:
			# res.extend(root)
			return root[0]
	# return list(set(res))


def get_monomials(pols):
	# return all unique monomials part of polynomials in pols 
	x, y, z = pols[0].parent().gens()
	monomials_tmp = []
	monomials = []

	deg_x = deg_y = deg_z = 0
	for t_poly in pols:
		monomials_tmp += t_poly.monomials()
		deg_x = max(deg_x, t_poly.degree(x))
		deg_y = max(deg_y, t_poly.degree(y))
		deg_z = max(deg_z, t_poly.degree(z))
	monomials_tmp = sorted(set(monomials_tmp))

	monomials = []
	for k in range(deg_z + 1):
		for j in range(deg_y + 1):
			for i in range(deg_x + 1):
				mono = x^i * y^j * z^k
				if mono in monomials_tmp:
					monomials += [x^i * y^j * z^k]
	return monomials

def ernst_trivariate(pol, XU, YU, ZU, WW, mm, tt):
	"""
	Finds small roots to the trivariate equations of form
	f(x, y, z) = a0 + a1*x + a2*y + a3*y*z
	
	tt = τ*mm
	x0 < X, y0 < Y, z0 < Z and

	X^(1+3τ) * Y^(2+3τ) * Z(1+3τ+3τ^2) ≤ W^(1+3τ)

	References:
	 [1] Matthias Ernst, Ellen Jochemsz, Alexander May, Benne de Weger. "Partial Key Exposure Attacks on RSA up to Full Size Exponents"
	 	 https://link.springer.com/chapter/10.1007/11426639_22
	"""
	PR = pol.parent()
	x, y, z = PR.gens()

	RR = (XU * YU)^mm * ZU^(mm + tt) * WW

	# make constant term 1 modulo RR
	# res-> f_ = 1 + a*x + b*y + c*y*z
	f_ = pol
	a0 = f_.constant_coefficient()
	if a0 != 0:
		assert gcd(a0, RR) == 1, "gcd(a0, RR) != 1"
		F = Zmod(RR)
		PK = PolynomialRing(F, 'xs, ys, zs')
		PR = pol.parent()
		f_ = PR(PK(f_) * F(a0)^-1)

	# construct shift polynomials (cf.[1] p.7)
	g_shft_pols = set()
	for i in range(mm + 1):
		for j in range(mm - i + 1):
			for k in range(j + 1):
				tmp_pol = x^i * y^j * z^k
				tmp_pol *= f_
				tmp_pol *= XU^(mm - i) * YU^(mm - j) * ZU^(mm + tt - k)
				g_shft_pols.add(tmp_pol)

	h_shift_pols = set()
	for i in range(mm + 1):
		for j in range(mm - i + 1):
			for k in range(j + 1, j + tt + 1):
				tmp_pol = x^i * y^j * z^k
				tmp_pol *= f_
				tmp_pol *= XU^(mm - i) * YU^(mm - j) * ZU^(mm + tt - k)
				h_shift_pols.add(tmp_pol)

	g_dash_pols = set()
	for i in range(mm + 1 + 1):
		j = mm + 1 - i
		for k in range(j + 1):
			g_dash_pols.add(RR * x^i * y^j * z^k)

	h_dash_pols = set()
	for i in range(mm + 1 + 1):
		j = mm + 1 - i
		for k in range(j + 1, j + tt + 1):
			h_dash_pols.add(RR * x^i * y^j * z^k)

	# calculate all monomials
	G = list(g_shft_pols) + list(h_shift_pols) + list(g_dash_pols) + list(h_dash_pols)	
	monomials = get_monomials(G)

	monomials_2 = get_monomials(list(g_dash_pols) + list(h_dash_pols))

	# order monomials such that g_shift_pols and h_shift_pols
	# will be the top rows of the basis
	final_monomials = []
	for mono in monomials:
		if mono not in monomials_2:
			final_monomials += [mono]
	final_monomials = final_monomials + monomials_2

	monomials = final_monomials

	assert len(monomials) == len(G)

	dims = len(monomials)
	
	# calculate coefficient vectors gijk(xX, yY, zZ) and ...
	coefficient_vecs = []
	for i in range(dims):
		tmp_pol = G[i]
		pol_coeffs = []
		for monomial in monomials:
			pol_coeffs.append(
				tmp_pol.monomial_coefficient(monomial) * monomial(XU, YU, ZU)
				)
		coefficient_vecs.append(pol_coeffs)

	# order coefficient vectors such that 
	# diagonal entries of g and h are equal to
	# (X*Y)^m * Z^(m + t)
	ordered_vecs = [0 for _ in range(dims)]
	for i in range(len(coefficient_vecs)):
		j = 0
		while coefficient_vecs[i][j] == 0:
			j += 1
		ordered_vecs[j] = coefficient_vecs[i]

	M = Matrix(IntegerRing(), ordered_vecs)
	B = M.LLL()

	# construct polynomials using reduced basis
	H = [(i, 0) for i in range(dims)]
	H = dict(H)
	for i in range(dims):
		for j in range(dims):
			assert B[i, j] % monomials[j](XU, YU, ZU) == 0
			H[i] += PR((monomials[j] * B[i, j]) / monomials[j](XU, YU, ZU))
	return H

def ernst_trivariate_2nd_case(pol, XU, YU, ZU, WW, mm, tt):
	"""
	Finds small roots to the trivariate equations of form
	f(x, y, z) = a0 + a1*x + a2*y + a3*y*z + a4*d*z
	
	tt = τ*mm
	x0 < X, y0 < Y, z0 < Z and

	X^(2+3τ) * Y^(3+6τ+6τ^2) * Z(3+3τ) ≤ W^(2+3τ)

	References:
	 [1] Matthias Ernst, Ellen Jochemsz, Alexander May, Benne de Weger. "Partial Key Exposure Attacks on RSA up to Full Size Exponents"
	 	 https://link.springer.com/chapter/10.1007/11426639_22
	"""
	PR = pol.parent()
	x, y, z = PR.gens()

	RR = XU^mm * YU^(mm + tt) * ZU^mm * WW

	# make constant term 1 modulo RR
	# res-> f_ = 1 + a*x + b*y + c*y*z + d*z
	f_ = pol
	a0 = f_.constant_coefficient()
	if a0 != 0:
		assert gcd(a0, RR) == 1, "gcd(a0, RR) != 1"
		F = Zmod(RR)
		PK = PolynomialRing(F, 'xs, ys, zs')
		PR = pol.parent()
		f_ = PR(PK(f_) * F(a0)^-1)

	# construct shift polynomials (cf.[1] p.9)
	g_shft_pols = set()
	for i in range(mm + 1):
		for j in range(mm - i + 1):
			for k in range(mm - i + 1):
				tmp_pol = x^i * y^j * z^k
				tmp_pol *= f_
				tmp_pol *= XU^(mm - i) * YU^(mm + tt - j) * ZU^(mm - k)
				g_shft_pols.add(tmp_pol)

	h_shift_pols = set()
	for i in range(mm + 1):
		for j in range(mm - i + 1, mm - i + tt + 1):
			for k in range(mm - i + 1):
				tmp_pol = x^i * y^j * z^k
				tmp_pol *= f_
				tmp_pol *= XU^(mm - i) * YU^(mm + tt - j) * ZU^(mm - k)
				h_shift_pols.add(tmp_pol)

	g_dash_pols = set()
	for i in range(mm + 1 + 1):
		for j in range(mm + tt + 1 - i + 1):
			k = mm + 1 - i
			g_dash_pols.add(RR * x^i * y^j * z^k)

	h_dash_pols = set()
	for i in range(mm + 1):
		j = mm + tt + 1 - i
		for k in range(mm - i + 1):
			h_dash_pols.add(RR * x^i * y^j * z^k)

	# diagonal_entry = XU^mm * YU^(mm + tt) * ZU^mm

	# calculate all monomials
	G = list(g_shft_pols) + list(h_shift_pols) + list(g_dash_pols) + list(h_dash_pols)
	
	monomials = get_monomials(G)

	monomials_2 = get_monomials(list(g_dash_pols) + list(h_dash_pols))

	# order monomials such that g_shift_pols and h_shift_pols
	# will be the top rows of the basis
	final_monomials = []
	for mono in monomials:
		if mono not in monomials_2:
			final_monomials += [mono]
	final_monomials = final_monomials + monomials_2

	monomials = final_monomials

	assert len(monomials) == len(G)

	dims = len(monomials)

	# calculate coefficient vectors gijk(xX, yY, zZ) and ...
	coefficient_vecs = []
	for i in range(dims):
		tmp_pol = G[i]
		pol_coeffs = []
		for monomial in monomials:
			pol_coeffs.append(
				tmp_pol.monomial_coefficient(monomial) * monomial(XU, YU, ZU)
				)
		coefficient_vecs.append(pol_coeffs)

	# order coefficient vectors such that 
	# diagonal entries of g and h are equal to 
	# X^m * Y^(m+t) * Z^m
	ordered_vecs = [0 for _ in range(dims)]
	for i in range(len(coefficient_vecs)):
		j = 0
		while coefficient_vecs[i][j] == 0:
			j += 1
		ordered_vecs[j] = coefficient_vecs[i]

	M = Matrix(IntegerRing(), ordered_vecs)
	B = M.LLL()
	
	# construct polynomials using reduced basis
	H = [(i, 0) for i in range(dims)]
	H = dict(H)
	for i in range(dims):
		for j in range(dims):
			assert B[i, j] % monomials[j](XU, YU, ZU) == 0
			H[i] += PR((monomials[j] * B[i, j]) / monomials[j](XU, YU, ZU))
	return H


if 1:
	# pbctf 2020 Crypto Special gift
	print("pbctf 2020 Crypto Special gift\n")
	N = 124588792854585991543122421017579759242707321792822503200983206042530513248160179498235727796077646122690756838184806567078369714502863053151565317001149999657802192888347495811627518984421857644550440227092744651891241056244522365071057538408743656419815042273198915328775318113249292516318084091006804073157
	e = 109882604549059925698337132134274221192629463500162142191698591870337535769029028534472608748886487359428031919436640522967282998054300836913823872240009473529848093066417214204419524969532809574214972094458725753812433268395365056339836734440559680393774144424319015013231971239186514285386946953708656025167
	gift = 870326170979229749948990285479428244545993216619118847039141213397137332130507928675398

	R = (e*gift*(2**120)) - 1

	delta = 120/1024
	beta = 0.4
	tau = (1/2) - delta
	mm = 2
	tt = 1

	XU = floor(N**delta)
	YU = floor(N**beta)
	ZU = floor(3*(N**(1/2)))

	while gcd(R, XU) != 1:
		XU += 1
	while gcd(R, YU) != 1:
		YU += 1
	while gcd(R, ZU) != 1:
		ZU += 1

	WW = max((e*XU, N*YU, YU*ZU, R))

	RR = (XU * YU)^mm * ZU^(mm + tt) * WW

	cond = int(XU^(1+3*tau) * YU^(2+3*tau) * ZU^(1 + 3*tau + 3*tau^2)) < int(WW^(1 + 3*tau))
	print("W >= NY", WW >= N*YU)
	print("Good =", cond)

	PR = PolynomialRing(IntegerRing(), "x, y, z")
	x, y, z = PR.gens()
	
	# (x0, y0, z0) = (d0, k, p + q - 1)
	pol = e*x - N*y + y*z + R

	a0 = pol.constant_coefficient()

	assert gcd(a0, RR) == 1, "gcd(a0, RR) != 1"

	HH = ernst_trivariate(pol, XU, YU, ZU, WW, mm=mm, tt = tt)

	z0 = root_z0(HH, pol)

	phi_N = N - z0
	d = inverse_mod(e, phi_N)

	enc = 67594553703442235599059635874603827578172490479401786646993398183588852399713973330711427103837471337354320292107030571309136139408387709045820388737058807570181494946004078391176620443144203444539824749021559446977491340748598503240780118417968040337516983519810680009697701876451548797213677765172108334420
	m = int(pow(enc, d, N))
	from Crypto.Util.number import long_to_bytes
	flag = long_to_bytes(m)
	print("\nSpecial Gift = ", flag.decode(), end="\n\n")

if 1:
	# pbctf 2020 Crypto Special gift revenge
	print("pbctf 2020 Crypto Special gift revenge\n")
	N = 123463519828344660835965296108959625188149729700517379543746606603601816029557213728343115758280318474617032830851553509268562367217512005079977122560679743955588214135519642513042848616372204042776892196887455692479457740367547908255044784496969010537283159300508751036032559594474145098337531029291955103059
	e = 85803665824396212221464259773478155183477895540333642019501498374139506738444521180470104195883386495607712971252463223185914391456070458788554837326327618859712794129800329295751565279950274474800740076285111503780662397876663144946831503522281710586712396810593754749589799811545251575782431569881989690861
	gift = 46710143823773072238724337855139753113453277386728402328859555407710009799097841900723288768522450009531777773692804519189753306306645410280934372812

	d_ = gift * (2**120)
	k_ = (e*d_ - 1) // N

	R = e*d_ - 1 - k_ * N

	beta = 0.6
	delta = 120 / 1024
	gamma = max(delta, beta - 1/2)
	tau = ((1/2) - delta - gamma)/(2*gamma)

	mm = 2
	tt = 1

	XU = floor(N^delta)
	YU = floor(4*N^gamma)
	ZU = floor(3*N^(1/2))

	while gcd(R, XU) != 1:
		XU += 1
	while gcd(R, YU) != 1:
		YU += 1
	while gcd(R, ZU) != 1:
		ZU += 1

	WW = max((e*XU, N*YU, YU*ZU, k_*ZU, R))

	RR = XU^mm * YU^(mm + tt) * ZU^mm * WW

	cond_lhs = XU^(2 + 3*tau) * YU^(3 + 6*tau + 3*tau^2) * ZU^(3 + 3*tau)
	cond_rhs = WW^(2+3*tau)

	print("W >= NY", WW >= N*YU)
	print("Good =", int(cond_lhs) < int(cond_rhs))

	PR = PolynomialRing(IntegerRing(), 'x, y, z')
	x, y, z = PR.gens()


	# (x0, y0, z0) = (d0, k0, p + q - 1)
	pol = e*x - N*y + y*z + k_ * z + R

	a0 = pol.constant_coefficient()
	assert gcd(a0, RR) == 1, "Error: gcd(a0, RR) != 1"

	HH = ernst_trivariate_2nd_case(pol, XU, YU, ZU, WW, mm, tt)
	z0 = root_z0(HH, pol)
	phi_N = N - z0
	d = inverse_mod(e, phi_N)

	enc = 106121451638162677594573310940827829041097305506084523508481527070289767121202640647932427882853090304492662258820333412210185673459181060321182621778215705296467924514370932937109363645133019461501960295399876223216991409548390823510949085131028770701612550221001043472702499511394058569487248345808385915190
	m = int(pow(enc, d, N))
	from Crypto.Util.number import long_to_bytes
	flag = long_to_bytes(m)
	print("\nSpecial Gift Revenge = ", flag.decode(), end="\n\n")

"""
pbctf 2020 Crypto Special gift

W >= NY True
Good = True

Special Gift =  pbctf{I_used_http://souravsengupta.com/publications/2010_indocrypt_2.pdf.How_about_you?}

pbctf 2020 Crypto Special gift revenge

W >= NY True
Good = True

Special Gift Revenge =  pbctf{thank_you_rkm0959,_for_finding_unintended_solution}

"""

# References for implementation
"""
[1] https://github.com/elliptic-shiho/crypto_misc/blob/master/small_root/jochemsz_may.sage
[2] https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
"""