RSA i liczby pierwsze

Co się właśnie stało?

Zwiększyłeś liczbę cyfr liczb pierwszych p i q. Mnożenie p·q pozostało błyskawiczne, ale próba odtworzenia p i q z samego n stała się nieporównywalnie trudniejsza — to właśnie ta asymetria chroni Twoje dane w internecie.

System RSA:

Ronald Rivest, Adi Shamir i Leonard Adleman opublikowali w 1978 r. system RSA — pierwszy praktyczny, powszechnie stosowany system kryptografii klucza publicznego. Klucz publiczny (do szyfrowania, może być jawny) zawiera iloczyn n = p × q dwóch tajnych, dużych liczb pierwszych; klucz prywatny (do odszyfrowania) wymaga znajomości p i q osobno.

Dlaczego to jest bezpieczne?

Ponieważ rozłożenie bardzo dużej liczby n z powrotem na czynniki pierwsze jest przy obecnej wiedzy matematycznej i mocy obliczeniowej praktycznie niewykonalne w rozsądnym czasie (dla liczb rzędu setek cyfr) — nawet znając n publicznie, atakujący nie jest w stanie w praktyce odtworzyć p i q. Stąd:

gdzie d to liczba cyfr p i q — mnożenie rośnie łagodnie (wielomianowo) z d, a faktoryzacja rośnie gwałtownie (sub-wykładniczo) z d.

Gdzie to spotykasz?

RSA jest dziś fundamentem szyfrowania w internecie — HTTPS (kłódka w przeglądarce), bankowość elektroniczna, podpisy cyfrowe. Za to osiągnięcie Rivest, Shamir i Adleman otrzymali w 2002 r. Nagrodę Turinga — najważniejsze wyróżnienie w informatyce, odpowiednik Nobla dla tej dziedziny.

Po co Ci to na maturze:

Liczby pierwsze i rozkład na czynniki pierwsze to standardowy temat matury z matematyki — RSA pokazuje, że ta „szkolna" matematyka ma bardzo realne zastosowanie: chroni każde logowanie i każdą transakcję online.

Zapamiętaj: mnożenie dużych liczb pierwszych jest szybkie, a faktoryzacja ich iloczynu — bardzo trudna. Ta asymetria to fundament bezpieczeństwa RSA i większości dzisiejszej komunikacji internetowej.