picoCTF - EVEN RSA CAN BE BROKEN???

W tym poście opiszę sposób rozwiązania zadania EVEN RSA CAN BE BROKEN z sekcji Cryptography picoCTF. 

Zadanie jak zawsze polega na odczytaniu flagi. 

Do zadania dołączono kod programu w Pythonie, który wygląda następująco:

1. from sys import exit
2. from Crypto.Util.number import bytes_to_long, inverse
3. from setup import get_primes
4.  
5. e = 65537
6.  
7. def gen_key(k):
8.     """
9.    Generates RSA key with k bits
10.    """
11.     p,q = get_primes(k//2)
12.     N = p*q
13.     d = inverse(e, (p-1)*(q-1))
14.  
15.     return ((N,e), d)
16.  
17. def encrypt(pubkey, m):
18.     N,e = pubkey
19.     return pow(bytes_to_long(m.encode('utf-8')), e, N)
20.  
21. def main(flag):
22.     pubkey, _privkey = gen_key(1024)
23.     encrypted = encrypt(pubkey, flag)
24.     return (pubkey[0], encrypted)
25.  
26. if __name__ == "__main__":
27.     flag = open('flag.txt', 'r').read()
28.     flag = flag.strip()
29.     N, cypher  = main(flag)
30.     print("N:", N)
31.     print("e:", e)
32.     print("cyphertext:", cypher)
33.     exit()

Na samym początku, po deklaracji potrzebnych bibliotek mamy zdefiniowaną wartość e. Oznacza ona wartość eksponenta publicznego dla RSA. Najczęściej jest to liczba całkowita dodatnia. Wprowadzona liczba 65537, jest najczęściej stosowaną wartością, dla większości implementacji. 

Wartość 65537 jest często stosowana ponieważ jest liczbą pierwszą, ma mało jedynek dla zapisu binarnego (10000000000000001), co przyśpiesza obliczenia. Dzięki dostatecznie dużej wartości zapewnia odpowiedni poziom bezpieczeństwa. 

Następna jest funkcja odpowiedzialna za generowanie kluczy. Na samym początku losowane są dwie liczby pierwsze p oraz q o długości k/2. Dalej obliczany jest N czyli tzw. moduł RSA. Po nim następuje obliczenie Następnie następuje obliczenie funkcji Eulera:

φ(n)=(p-1)(q-1)

Który jest wykorzystywany do obliczenia d, czyli odwrotności modularnej czyli e dzielone przed funkcje Eulera. 

Po uruchomieniu tego programu otrzymuje następujący wynik działania:

1. N: 22321130498067817633914018534979291148516929113331749263752822928968742441808984572395615385890948558208946804442522443015782843622882350503183464582229078
2. e: 65537
3. cyphertext: 7429146572356614276991625770288474207334266336657246449826510284146138168542796284195883914974571879854693673736977402030651149358945018430121241138148897

Teraz należy rozłożyć otrzymane N. Korzystam ze strony factordb.com. Po wklejeniu do niej N otrzymuję następującą informację:

Z tego wynika, że liczba ma 155 cyfr dziesiętnych. Standardowo, gdy wykorzystywane jest 1024 bitowe N to otrzymujemy około 310 cyfr. Więc to N jest krótsze od klasycznego RSA. 

Faktoryzacja pokazała, że N nie jest iloczynem dwóch dużych liczb pierwszych nieparzystych. Jedną z tych liczb jest 2 (czyli najmniejsza liczba pierwsza), druga to duża liczba pierwsza składająca się z 155 cyfr. 

Powoduje to uproszczenie funkcji Eulera do postaci:

φ(n)=(2-1)(q-1)=(q-1)

Status FF oznacza, że liczba została w pełni rozłożona na czynniki pierwsze. 

 

Teraz wystarczy przygotować program w Python, który odwróci operacje:

1. def long_to_bytes(n):
2.     return n.to_bytes((n.bit_length() + 7) // 8, 'big')
3.  
4. N = 22321130498067817633914018534979291148516929113331749263752822928968742441808984572395615385890948558208946804442522443015782843622882350503183464582229078
5. e = 65537
6. c = 7429146572356614276991625770288474207334266336657246449826510284146138168542796284195883914974571879854693673736977402030651149358945018430121241138148897
7.  
8. q = N // 2
9.  
10. phi = (2 - 1) * (q - 1)
11. d = pow(e, -1, phi)
12.  
13. m = pow(c, d, N)
14. print(long_to_bytes(m).decode())

Wynik działania programu:

1. picoCTF{<flaga>}
2. ** Process exited - Return Code: 0 **

Można to też napisać w C. Należy dołączyć bibliotekę gmp,h w celu obsługi typów GMP do przechowywania dużych liczb. 

1. #include <stdio.h>
2. #include <gmp.h>
3. #include <stdint.h>
4. #include <stdlib.h>
5. #include <string.h>
6.  
7. int main() {
8.     //zmienne dla dużych liczb
9.     mpz_t N, e, c, p, q, phi, d, m;
10.     mpz_inits(N, e, c, p, q, phi, d, m, NULL);
11.  
12.     // Inicjalizacja liczb z tekstu dziesietnego
13.     mpz_set_str(N, "22321130498067817633914018534979291148516929113331749263752822928968742441808984572395615385890948558208946804442522443015782843622882350503183464582229078", 10);
14.     mpz_set_str(e, "65537", 10);
15.     mpz_set_str(c, "7429146572356614276991625770288474207334266336657246449826510284146138168542796284195883914974571879854693673736977402030651149358945018430121241138148897", 10);
16.  
17.     //p jako 2 bo wyszło z wyliczeń na stronie
18.     mpz_set_ui(p, 1);
19.    
20.     //q = N / 2
21.     mpz_fdiv_q_ui(q, N, 2);
22.  
23.     //q = q - 1
24.     mpz_sub_ui(q, q, 1);
25.    
26.     // phi = (2-1)*(q-1)
27.     mpz_mul(phi, p, q);      
28.  
29.     //d = e^-1 mod phi
30.     if (mpz_invert(d, e, phi) == 0) {
31.         printf("ERROR\n");
32.         return 1;
33.     }
34.  
35.     //m = c^d mod N
36.     mpz_powm(m, c, d, N);
37.    
38.     size_t count;
39.     char *str = mpz_export(NULL, &count, 1, 1, 1, 0, m);
40.     printf("Flag: %.*s\n", (int)count, str);
41.  
42.     free(str);
43.     mpz_clears(N, e, c, p, q, phi, d, m, NULL);
44.     return 0;
45. }

Otrzymany wynik pokrywa się z tym wygenerowanym z pierwszego programu.