## 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 challengeis 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 plaintextusing RSA. Key lengths are pretty long, so we cannot easily factorize `n` using normal approach - instead we have to relyon 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**19tq = 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 baseitself. 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 ciphertextgives flag.
###PL version
W zadaniu dostajemy zaszyfrowany tekst, generator kluczy napisany w Pythonie, oraz klucz publiczny wygenerowany przezniego - zadanie sprowadzało się zatem do odkodowania tekstu bez znajomości klucza prywatnego. Przestudiowanieskryptu pozwala nam stwierdzić, że użyto algorytmu RSA ze sporą wartością `p` i `q` - standardowe metody faktoryzacjizatem 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**19tq = 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 cyfryznają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 dwiemaniewiadomymi. Rozwiązując kwadratowe równanie, otrzymujemy `tp` i `tq`, dzięki którym poznajemy `p` i `q`, którez kolei pozwalają nam na odczytanie odkodowanej wiadomości z flagą.