Rating:

## High-speed RSA Keygen (Crypto, 150p)

See the attached files.

Download RSA-Keygen.tar.gz

###ENG
[PL](#pl-version)

We were given a ciphertext, a key generator written in Python and a public key generated by that script - so the challenge
is to decrypt the ciphertext using only the public key.
Looking at the script, we can notice that it generates two random prime numbers `p` and `q` and then encrypts plaintext
using RSA. Key lengths are pretty long, so we cannot easily factorize `n` using normal approach - instead we have to rely
on weaknesses in generation algorithm.
The interesting part of script (there were also primality checks and other things, but
they are not important for this writeup):
```
kq = randrange(1, 2**12) + 2**12 + 2**13 + 2**14 + 2**15 + 2**16 + 2**17 + 2**18 + 2**19
tq = randrange(1, 2**399)
q = kq * pi * 2**400 + tq
```
`pi` - calculated earlier - is a product of first 443 primes.
Algorithm for `p` is the same. Let's see how `n=p*q` looks like:

`n=p*q=`

`=(kp * pi * 2**400 + tp)*(kq * pi * 2**400 + tq)=`

`=kp*kq*pi^2*2^800 + kp*pi*2^400*tq + kq*pi*2^400*tp + tp*tq=`

`=(pi*2^400)^2 * kp*kq + (pi*2^400) * (kq*tp+kp*tq) + tp*tq`

This looks similar to number written in base `pi*2^400`. We still need to check whether "digits" are smaller than base
itself. As `pi` is around `2^600`, base is close to `2^1000`. The biggest digit is the last one - `tp*tq`, which is
smaller than `2^800`, so everything is good.

As we know, representation of any number in any base is unique - therefore we can recover those digits from `n` alone.
Let's call those digits `A`, `B` and `C`. We have:

`A=kp*kq`, `B=kp*tq+kq*tp`, `C=tp*tq`

Since `kp` and `kq` have only small number of possible values (2^12), we can easily brute force the generated ones.
It turns out there was only one possibility. Knowing `kp` and `kq`, we are left with two equations and two unknowns.
Solving quadratic equation, we get `tp` and `tq`, which we later use to recover `p` and `q`. Decoding the ciphertext
gives flag.

###PL version

W zadaniu dostajemy zaszyfrowany tekst, generator kluczy napisany w Pythonie, oraz klucz publiczny wygenerowany przez
niego - zadanie sprowadzało się zatem do odkodowania tekstu bez znajomości klucza prywatnego. Przestudiowanie
skryptu pozwala nam stwierdzić, że użyto algorytmu RSA ze sporą wartością `p` i `q` - standardowe metody faktoryzacji
zatem odpadają. Pozostaje wykorzystanie podatności w kodzie generującym klucze.

Najważniejsza część skryptu (pomijając sprawdzanie pierwszości itp.):
```
kq = randrange(1, 2**12) + 2**12 + 2**13 + 2**14 + 2**15 + 2**16 + 2**17 + 2**18 + 2**19
tq = randrange(1, 2**399)
q = kq * pi * 2**400 + tq
```
`pi` - obliczone wcześniej - to iloczyn pierwszych 443 liczb pierwszych.
`p` jest obliczane analogicznie. Zobaczmy, jak zatem wygląda `n`:

`n=p*q=`

`=(kp * pi * 2**400 + tp)*(kq * pi * 2**400 + tq)=`

`=kp*kq*pi^2*2^800 + kp*pi*2^400*tq + kq*pi*2^400*tp + tp*tq=`

`=(pi*2^400)^2 * kp*kq + (pi*2^400) * (kq*tp+kp*tq) + tp*tq`

Równanie wygląda podobnie do zapisu liczby w systemie o podstawie `pi*2^400`. Sprawdźmy jeszcze, czy "cyfry" tej
reprezentacji są mniejsze od podstawy - jak sprawdziliśmy, `pi` jest równe około `2^600`, zatem podstawa to około
`2^1000`. Z kolei największa "cyfra" to `tp`*`tq`, które jest mniejsze niż `2^800`. Wszystko się więc zgadza.

Jak wiadomo, reprezentacja dowolnej liczby w dowolnym systemie liczbowym jest unikatowa - można zatem wyciągnąć te cyfry
znając jedynie `n`. Nazwijmy te cyfry `A`, `B` i `C`. Mamy:

`A=kp*kq`, `B=kp*tq+kq*tp`, `C=tp*tq`

Ponieważ `kp` i `kq` mają niewielką liczbę możliwych wartości (2^12), łatwo możemy wybrutować te prawdziwe. Okazuje się,
że jest tylko jedna para liczb spełniająca pierwsze równanie. Znając `kp` i `kq`, zostają nam dwa równania z dwiema
niewiadomymi. Rozwiązując kwadratowe równanie, otrzymujemy `tp` i `tq`, dzięki którym poznajemy `p` i `q`, które
z kolei pozwalają nam na odczytanie odkodowanej wiadomości z flagą.

Original writeup (https://github.com/p4-team/ctf/tree/master/2016-02-05-sharif/crypto_150_keygen).