Klucz publiczny i podpis elektroniczny

🎯 Po co Ci to?

Wszystkie szyfry tego działu — od Cezara po Vigenère'a — mają wspólną piętę achillesową, o której jeszcze nie rozmawialiśmy: obie strony muszą wcześniej uzgodnić tajny klucz. Jak? Spotkać się? Wysłać kluczem… zaszyfrowanym czym? Przez stulecia odpowiedzią byli kurierzy z teczkami. A teraz spójrz na swój telefon: łączysz się z bankiem, którego nigdy nie widziałeś, przez sieć, którą podsłuchać może każdy — i w ułamku sekundy macie wspólny sekret. W latach 70. XX wieku garstka ludzi wpadła na pomysł tak przewrotny, że początkowo uznano go za niemożliwy: klucz szyfrujący można ogłosić światu. Ta jednostka domyka dział — i spina go z liczbami pierwszymi z działu 4.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • wyjaśnić różnicę między kryptografią symetryczną a asymetryczną (metafora kłódki);
  • opisać, na czym opiera się bezpieczeństwo klucza publicznego (funkcje jednokierunkowe);
  • wyjaśnić, czym jest podpis elektroniczny i co gwarantuje (z haszem w roli głównej).

🔁 Przypomnij sobie

Z 4.4: mnożenie łatwe, rozkład na czynniki beznadziejny; z 4.6: wielkie potęgi mod liczy się błyskawicznie; z 5.6: hasz to odcisk dokumentu.

📘 Wyjaśnienie

Symetria i jej granice. Wszystkie dotychczasowe szyfry są symetryczne: ten sam klucz zamyka i otwiera. Symetria wymusza wcześniejsze uzgodnienie sekretu — a z $n$ rozmówcami potrzebujesz $n$ różnych kluczy (i każdy nowy kontakt to nowy problem kurierski). Internet z miliardami par rozmówców byłby na symetrii nie do zbudowania.

Pomysł: kłódka. Wyobraź sobie, że zamiast klucza rozdajesz światu… otwarte kłódki. Każdy może włożyć wiadomość do skrzynki i zatrzasnąć Twoją kłódkę — zamknąć potrafi każdy. Ale otworzyć — tylko Ty, bo kluczyk nigdy nie opuścił Twojej kieszeni. To jest kryptografia asymetryczna: para kluczy zamiast jednego.

📐 DEFINICJA — kryptografia klucza publicznego: system z parą matematycznie powiązanych kluczy: publicznym (jawnym — służy do szyfrowania) i prywatnym (tajnym — służy do deszyfrowania). Wiadomości zaszyfrowanej kluczem publicznym nie da się praktycznie odszyfrować bez prywatnego.

Po ludzku: kłódka dla wszystkich, kluczyk dla jednego. Czym NIE jest: magią bez założeń. Całość stoi na tym, że pewnych operacji matematycznych nie umiemy odwracać w rozsądnym czasie — to bezpieczeństwo obliczeniowe, nie absolutne.

Skąd asymetria? Z matematyki, którą już znasz. Potrzebna jest operacja łatwa w jedną stronę i beznadziejna w drugą — funkcja jednokierunkowa. Kandydatkę poznałeś w 4.4: pomnożyć dwie wielkie liczby pierwsze — mikrosekundy; z iloczynu odzyskać czynniki — epoki geologiczne. W najsłynniejszym systemie (RSA, od nazwisk Rivest–Shamir–Adleman, 1977) klucz publiczny zawiera właśnie taki iloczyn $n = p \cdot q$; kto zna czynniki (właściciel!), umie odszyfrowywać, kto zna tylko iloczyn — musiałby go rozłożyć. Szyfrowanie i deszyfrowanie to potęgowanie modulo $n$ na wielkich liczbach — dokładnie ta operacja, którą w 4.6 nauczyłeś się liczyć w 60 krokach zamiast $10^{600}$. Nie prowadzimy tu pełnego rachunku RSA (wykracza poza program) — ale zauważ z satysfakcją: wszystkie klocki masz w rękach: pierwszość (4.1), Euklides (4.2), rozkład-jako-mur (4.4), szybka potęga (4.6). Kryptografia to dział 4 w mundurze.

Podpis elektroniczny: asymetria na odwrót. Para kluczy ma drugą, mniej oczywistą supermoc. Zauważ symetrię ról: skoro klucz prywatny „odwraca" publiczny, to działa też w drugą stronę — coś przekształconego kluczem prywatnym może sprawdzić każdy, używając klucza publicznego. A przekształcić mógł tylko właściciel. To jest podpis:

  1. Liczysz hasz dokumentu (5.6 — odcisk, krótki i związany z każdym bitem treści).
  2. Hasz przekształcasz swoim kluczem prywatnym — to jest podpis, dołączany do dokumentu.
  3. Weryfikujący: liczy hasz dokumentu sam, „odwraca" Twój podpis Twoim kluczem publicznym i porównuje. Zgodność oznacza: podpisał posiadacz klucza prywatnego (autentyczność), i to dokładnie ten dokument — zmiana jednego bitu zmienia hasz (integralność). Bonus prawny: podpisu nie da się później wyprzeć (niezaprzeczalność), bo nikt inny nie mógł go złożyć.

Zwróć uwagę na rozdział ról w duecie z poprzedniej jednostki: hasz gwarantuje „to ten dokument", podpis — „to ta osoba". Dziura z 💭 w 5.6 (napastnik podmienia plik i opublikowany hasz) właśnie się zamknęła: hasza podrobisz, podpisu — nie.

A skąd wiadomo, czyj jest klucz publiczny? Pytanie za sto punktów — bo napastnik może ogłosić własny klucz „w imieniu banku". Odpowiedź praktyczna: klucze publiczne też są podpisywane — przez urzędy certyfikacji, którym Twoja przeglądarka ufa fabrycznie (łańcuch zaufania). Kłódka przy adresie oznacza: „klucz tego serwera jest podpisany przez kogoś z listy zaufanych". System nie jest doskonały (urzędy bywały kompromitowane), ale skalowalny — i to on trzyma dziś handel, bankowość i pocztę świata. Więcej o praktyce — w dziale 16.

💭 Pomyśl: Chcesz wysłać koleżance poufny list tak, by (a) tylko ona go odczytała, (b) miała pewność, że to od Ciebie. Które klucze — czyje i które z pary — biorą udział w każdym z tych celów?

Sprawdź odpowiedź

(a) Poufność: szyfrujesz jej kluczem publicznym (tylko jej prywatny otworzy). (b) Autentyczność: podpisujesz swoim kluczem prywatnym (jej weryfikacja — Twoim publicznym). W praktyce robi się jedno i drugie: podpisz, potem zaszyfruj. Cztery klucze, dwie pary, zero kurierów — i proszę zauważyć, że pomyliłeś się w tym ćwiczeniu albo nie: mylenie „czyj klucz do czego" to najczęstszy błąd na sprawdzianach z tego tematu, więc odpowiedź warto umieć wyrecytować obudzonym o trzeciej w nocy.

🤯 Ciekawostka

Historia lubi ironię: RSA wynaleziono w 1977 roku publicznie — ale identyczny system opracował już w 1973 Clifford Cocks z brytyjskiego wywiadu GCHQ. Utajniono go tak skutecznie, że nawet wynalazca nie mógł się pochwalić — świat dowiedział się dopiero w 1997. A dziś nad RSA wisi nowe pytanie: wystarczająco duży komputer kwantowy rozkładałby liczby szybko (algorytm Shora), więc kryptografia właśnie przeprowadza się na nowe funkcje jednokierunkowe, odporne — jak sądzimy — także na kwanty. Wyścig łamaczy i konstruktorów, który zaczął Al-Kindi, nie skończy się nigdy; zmieniają się tylko dekoracje.

🛠️ Teraz Ty

Bez komputera (zabawkowe RSA — liczby śmiesznie małe, żeby dało się ręcznie): weź $p = 3$, $q = 11$, więc $n = 33$; kluczem publicznym niech będzie wykładnik 3 (szyfrowanie: $c = w^3 \bmod 33$), prywatnym — wykładnik 7 (deszyfrowanie: $w = c^7 \bmod 33$). Zaszyfruj wiadomość $w = 4$ i odszyfruj wynik (szybkie potęgowanie mod z 4.6 w wersji ręcznej!). Sprawdź też, że kolejność potęg nie gra roli: $(4^7)^3 \bmod 33 = 4$ — to podstawa podpisu.

📐 Definicje tej lekcji

  • Kryptografia symetryczna / asymetryczna — jeden wspólny tajny klucz / para: publiczny (jawny) + prywatny (tajny).
  • Funkcja jednokierunkowa — łatwa do policzenia, praktycznie nieodwracalna; np. mnożenie wielkich pierwszych vs rozkład.
  • Podpis elektroniczny — hasz dokumentu przekształcony kluczem prywatnym; weryfikowalny publicznym; daje autentyczność, integralność, niezaprzeczalność.

📌 Najważniejsze w pigułce

  • Asymetria rozwiązuje problem kuriera: kłódka jawna, kluczyk prywatny — sekret nigdy nie podróżuje.
  • Bezpieczeństwo = twardość matematycznego muru (rozkład na czynniki), nie tajność metody; klocki muru poznałeś w dziale 4.
  • Podpis = hasz + klucz prywatny; certyfikaty podpisują same klucze — tak powstaje łańcuch zaufania z kłódką w pasku adresu.

🎒 Zadania

  1. Uzupełnij tabelkę „kto czym co robi": wysyłanie poufne, odbieranie poufne, podpisywanie, weryfikacja podpisu — dla każdej operacji wskaż klucz (czyj + publiczny/prywatny).
Wskazówka i odpowiedź

Wysyłasz poufnie: publiczny odbiorcy. Odbierasz poufne: swój prywatny. Podpisujesz: swój prywatny. Weryfikujesz cudzy podpis: publiczny nadawcy. Zasada porządkująca: prywatnego używa się tylko do rzeczy, które ma umieć zrobić wyłącznie właściciel (odczytać adresowane do niego; poświadczyć sobą); wszystko, co „może każdy", chodzi na kluczach publicznych.

  1. Bank ostrzega: „nigdy nie podamy Ci przez telefon kodu z SMS-a". Przeanalizuj przez pojęcia tej jednostki, czego w rozmowie telefonicznej z „konsultantem" brakuje — i czego NIE rozwiązuje nawet najlepsza kryptografia.
Wskazówka i odpowiedź

Telefon nie daje uwierzytelnienia rozmówcy: głos „konsultanta" to samozwańczy klucz publiczny bez certyfikatu — nikt go nie podpisał. Kryptografia zabezpiecza kanały i tożsamości maszyn; człowiek przekonany socjotechnicznie odda kod sam, najpiękniej zaszyfrowanym kanałem. Najsłabszym ogniwem systemu nie jest matematyka — dział 16 poświęci temu całą jednostkę o socjotechnice.

  1. Umowa podpisana elektronicznie ma zmieniony jeden przecinek (po podpisaniu). Opisz krok po kroku, jak weryfikacja to wykryje — i wyjaśnij, która własność hasza (5.6) jest tu kluczowa.
Wskazówka i odpowiedź

Weryfikujący liczy hasz otrzymanego dokumentu → „odwraca" podpis kluczem publicznym, dostając hasz dokumentu pierwotnego → porównuje: różne, bo zmiana choćby bitu zmienia odcisk. Kluczowa własność: wrażliwość hasza na każdą zmianę wejścia (tzw. efekt lawinowy) plus praktyczna niemożność znalezienia innego dokumentu o tym samym haszu (odporność na kolizje) — bez niej fałszerz podmieniłby treść „pod istniejący podpis". Odcisk i podpis pracują w parze; osobno każde jest do obejścia.

🔍 Sprawdź, czy umiesz

  • Opowiedzieć metaforę kłódki i wskazać, gdzie w niej mieszka funkcja jednokierunkowa.
  • Rozpisać podpis elektroniczny na trzy kroki i trzy gwarancje.
  • Wyjaśnić, po co istnieją certyfikaty i co oznacza kłódka w przeglądarce.

Ucz się tej jednostki z asystentem