Skrytka jest zagadkowa, a położenie pojemnika jest owiane tajemnicą. Nie znajduje się on na współrzędnych początkowych, a w regulaminowej odległości od nich. By poznać koordynaty skrytki, należy odszyfrować tajną wiadomość i wpisać ją do checkera.
Informacje ogólne
Algorytm RSA jest jednym z pierwszych asymetrycznych algorytmów kryptograficznych. Oznacza to mniej więcej tyle, że w oparciu o publicznie dostępny klucz, każdy użytkownik może swoją wiadomość zaszyfrować, ale tylko posiadacz klucza tajnego może wiadomość odszyfrować.
Takie algorytmy opierają się na funkcjach, które dają się stosunkowo łatwo wyliczyć, ale niekoniecznie łatwo odwrócić (w sensie numerycznym: operacji komputerowych na wielkich liczbach). Przykłady takich funkcji to mnożenie czy potęgowanie modulo. Działania do nich odwrotne, czyli rozkład na czynniki pierwsze czy logarytmowanie dyskretne to już inny poziom trudności. Poniżej znajdziesz opis działania algorytmu - może Ci się przydać, jeżeli chcesz znaleźć pojemnik finałowy!
Co ciekawe i ważne, algorytm RSA nie jest jedynie ciekawostką historyczną którą na ćwiczeniach odtwarzają studenci matematyki, ale znajduje swoje zastosowania w praktyce przesyłania zaszyfrowanych danych. Zarówno przykład jak i zadanie bazują na małych liczbach i zapewne złamanie szyfru nie byłoby trudne. Oczywiście im większe liczby i im lepsze dodatkowe zabezpieczenia, tym bardziej szyfrowanie RSA jest bezpieczne. Biorąc liczby p i q (o nich więcej niżej) mające setki cyfr, a także dzieląc wiadomość na większe pakiety znaków (uniemożliwiające analizę częstości wystąpień popularnych sekwencji znaków), można utrudnić życie osobie mającej niecne plany. Co więcej, długie ciągi znaków często szyfrowane są w inny sposób, a algorytmem RSA szyfruje się... sposób szyfrowania. Bezpieczniej zamykać drzwi na dwa zamki, niż na jeden.
Największym zagrożeniem przyszłości dla algorytmu RSA są opracowanie szybkich metod faktoryzacji liczb oraz skonstruowanie komputera kwantowego. Już teraz złamanie szyfru nie jest tak trudne jak kilkadziesiąt lat temu, a dzięki powszechności zastosowań, zebranie i analiza certyfikatów bezpieczeństwa przestaje stanowić problem. Szacuje się, że 1 na 172 certyfikaty w dobie Internet of things jest zagrożonych ze względu na współdzielenie danych.
Algorytm RSA wziął swoją nazwę od inicjałów nazwisk jego twórców: Rona Rivesta, Adiego Shamira i Leonarda Adlemana.
(wróć do spisu)
Przydatne pojęcia matematyczne
Do zrozumienia algorytmu RSA potrzebne jest sięgnięcie po arytmetykę zegarową bądź... w języku lekcji z podstawówki: liczenie reszty z dzielenia. Ile wynosi reszta z dzielenia 50 przez 11?
50 = 4 x 11 + 6,
a zatem odpowiedzią na nasze pytanie jest 6. W zapisie matematycznym, resztę z dzielenia 50 przez 11 notujemy jako
50 mod 11 = 6.
Chociaż dla człowieka policzenie reszty z dzielenia dużych liczb może sprawić trudność, szczególnie gdy dysponuje jedynie kartką i długopisem, komputery radzą sobie z tymi działaniami bardzo dobrze. O tym więcej trochę niżej.
Użyteczna jest znajomość pojęcia liczb względnie pierwszych. O dwóch liczbach powiemy, że są względnie pierwsze, jeżeli nie mają wspólnych dzielników w rozkładzie na iloczyn liczb pierwszych. Na przykład, liczby 21 i 40 są względnie pierwsze, gdyż dzielniki 21 to 3 i 7, a dzielniki pierwsze 40 to 2 i 5. Z kolei liczby 21 i 49 nie są względnie pierwsze, gdyż mają wspólny dzielnik - 7.
Kolejnym ważnym działaniem, jest potęgowanie modularne. Jest to nic więcej niż policzenie reszty z dzielenia rezultatu potęgowania. Popatrzmy:
43 mod 11 = 64 mod 11 = 9.
Proste, prawda? Przy potęgowaniu modularnym "na piechotę" przydatne jest poszukiwanie zależności pomiędzy liczbami, np.
762 mod 12 = 4931 mod 12 = 131 mod 12 = 1.
Spróbuj teraz na własną rękę znaleźć resztę z dzielenia 3017180 przez 57. Możesz musieć poszukać odpowiedniego narzędzia. Rebus w galerii może Ci pomóc trafić na jedno z nich.
(wróć do spisu)
RSA krok po kroku - szyfrowanie
Pierwszym krokiem algorytmu jest wybór dwóch liczb pierwszych, nazwijmy je p i q. Dla potrzeb przykładu ustalmy, że p=5, a q=11. W kolejnym kroku obliczamy dwie wielkości - iloczyn liczb pierwszych (oznaczany przez N)
N = p x q
oraz jego tocjent (wartość funkcji Eulera), która w tym specjalnym przypadku przybiera postać
ɸ(N) = (p-1) x (q-1).
W naszym przypadku N=55 i ɸ(N)=40.
Następnie, wybieramy dowolną liczbę J, względnie pierwszą z ɸ(N). U nas ɸ(N)=23 x 5, więc możemy wziąć J=7. Liczba N oraz liczba J stanowią dane jawne, publiczne, konieczne do zaszyfrowania wiadomości. Przed nami ostatni wybór - znalezienie liczby T takiej, że
J x T = 1 mod ɸ(N),
bądź innymi słowy
T = J-1 mod ɸ(N).
Liczba ta jest tajna i wiadoma jedynie osobie upoważnionej do odszyfrowania wiadomości. W naszym przypadku taką liczbę prosto znaleźć, jest nią T=23.
Załóżmy teraz, że chcemy zaszyfrować słowo ANDERS, dzieląc je na pojedyńcze litery. Pierwszym krokiem jest zamiana liter na liczby wg ustalonej konwencji - przyjmijmy A-1, ..., Z-26, spacja-27.
A N D E R S
1 14 4 5 18 19
Dalej, każdą z liczb podnosimy do potęgi J, zatem w naszym przykładzie mamy
17 147 47 57 187 197
1 105413504 16384 78125 612220032 893871739
Ostatnie działanie matematyczne to obliczenie reszt z dzielenia powyższych liczb przez N. Tym samym otrzymujemy
1 9 49 25 17 24
Zatem, wysyłamy do odbiorcy zaszyfrowane dane w postaci
010949251724
(wróć do spisu)
RSA krok po kroku - odszyfrowywanie
Otrzymaliśmy od naszego znajomego komunikat treści
010949251724
Dysponujemy ponadto kluczem tajnym, w którego skład wchodzą liczby N=55 oraz T=23. Najpierw dzielimy komunikat na bloki długości odpowiadającej długością liczbie N, w naszym przypadku są one dwucyfrowe:
01 09 49 25 17 24
Następnie, każdą z otrzymanych liczb podnosimy do potęgi T:
123 923 4923 2523 1723 2423
1 387420489 1628413597910449 3814697265625 118587876497 2641807540224
Całkiem spore liczby, wyobraźmy sobie teraz że wyjściowe liczby nie są jedno- i dwucyfrowe, ale mają ich ponad 150... Po chwili refleksji, ostatnie działanie matematyczne - obliczamy reszty z dzielenia powyższych liczb przez N. Dostajemy:
1 14 4 5 18 19
Pod liczby podstawiamy litery zgodnie z ustaloną konwencją i odczytujemy nadany komunikat:
ANDERS
(wróć do spisu)
Zagadka
A teraz Twoje zadanie:
05235008070304213253003810028611474
Powyższy ciąg cyfr to zaszyfrowany ciąg znaków. By uzyskać współrzędne, musisz odszyfrować tajną wiadomość i sprawdzić swój wynik w poniższym checkerze. Jeżeli hasło będzie poprawne, checker poda Ci współrzędne skrytki.
Dobra wiadomość jest taka, że nie musisz łamać kodu. Spójrz na współrzędne początkowe. Tysięczne części minut współrzędnych początkowych są liczbami pierwszymi użytymi do zakodowania wiadomości, co powinno pomóc w rozpoczęciu zadania.
Użyty do szyfrowania klucz jawny to 7285. Lektura listingu powinna pomóc w znalezieniu klucza tajnego.
Otrzymane w rezultacie dekodowania liczby należy przełożyć na litery. Konwersja następuję poprzez zmiany systemu liczbowego z dziesiętnego na system o podstawie 37, którego cyfry do cyfry naturalne od 0 do 9, litery alfabetu angielskiego od A do Z i kropka:
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ.
Nie przejmuj się, jeżeli otrzymywane znaki nie będą miały sensu. Bezpieczniej drzwi zamykać na dwa zamki niż na jeden.
Na znalazców czeka plastikowy pojemnik objętości 20 ml, w którym znajduje się logbook, drewniak na wymianę oraz (w zakrętce) certyfikaty dla pierwszych trzech znalazców.
(wróć do spisu)
Materiały źródłowe
- Buchanan B., RSA Gradually Leaves The Stage After More Than 40 Years As A Leader — And It’s Its Friend (TLS) That Is Pushing It Off, dostęp online 23.11.2022 na blogu autora (ASecuritySite) na portalu Medium
- Crane C., How Secure is RSA in an Increasingly Connected World?, "HashedOut by The SSL Store", dostęp online 12.11.2021 na portalu The SSL Store
- Żak T., Labirynty matematyki: RSA, Politechnika Wrocławska, dostęp online 23.11.2022 na portalu PWr.
(wróć do spisu)