fbpx
blog

Matematyczna Luka w Algorytmach Szyfrujących

Krystian Karczyński

Założyciel i szef serwisu eTrapez.

Magister matematyki Politechniki Poznańskiej. Korepetytor matematyki z wieloletnim stażem. Twórca pierwszych Kursów eTrapez, które zdobyły ogromną popularność wśród studentów w całej Polsce.

Mieszka w Szczecinie. Lubi spacery po lesie, plażowanie i kajaki.


Matematyczny ciąg 0 i 1 złamany napisem o bezpieczeństwie informacjiZła wiadomość, proszę Państwa, bezpieczeństwo internetowych transakcji handlowych i międzynarodowej komunikacji cyfrowej zagrożone.

Matematycy z ośrodków badawczych w Stanach Zjednoczonych i Szwajcarii odkryli istotny błąd w powszechnie stosowanych algorytmach do cyfrowych zabezpieczeń (zwanych “RSA”).

Większość takich algorytmów wykorzystuje wielkie i losowo generowane liczby pierwsze do tworzenia kluczy autoryzujących np. internetowe transakcje.

W swojej opublikowanej 14 lutego naukowej publikacji matematycy wykazali, że znacząca liczba tych właśnie liczb pierwszych nie jest wcale losowa, co stwarza olbrzymie zagrożenie dla opartych na nich kluczy.

Nie wnikali też w swojej pracy w przyczyny takiego stanu rzeczy (oczywiście z generowaniem “zupełnie”  losowych liczb jest zawsze problem).

Algorytm Euklidesa

Prof James P. Hughes wraz z kolegami użyli zwykłego, znanego nam z podstawówki (!) algorytmu Euklidesa do rozkładu liczb na czynniki. Wykazali, że 12720 na 6 400 000 przebadanych kluczy o długości 1024 bitów miało tą samą wielką liczbę pierwszą jako czynnik. Daje nam to 0.2%, a to o wiele ZA DUŻO na to, żeby mógł to być czysty przypadek.

Badania podważają wynalezioną w 1978 roku, a stosowaną publicznie od 2000 metodę szyfrowania zwaną RSA.

Można więc w uproszczeniu powiedzieć, że 99,8% światowych transakcji internetowych jest bezpiecznych i wydaje się, że to całkiem dużo, ale pomyślmy, że dokonuje się ich około pół miliona dziennie i widać skalę problemu.

Naukowcy byli zszokowani prostotą metod (przypominam, że chodzi o algorytm z podstawówki), które użyli do swoich odkryć. Ciężko im uwierzyć, że problem jest nowością dla “agencji i znanych z zainteresowania tego typu kwestiami stron”, jak żartobliwie piszą w swojej publikacji.

W kluczach RSA 2048-bitowych również pojawia się problem braku losowości, choć na mniejszą skalę.

Jednak występuje on tylko w algorytmach RSA, wynalezionych m.in. przez Rona Rivesta, a nie w innych algorytmach (dlatego matematycy zatytuowali swoją publikację “Ron był w błędzie, Whit ma rację”).

Więcej o sprawie znajdziecie w artykule, na którym głównie bazowałem:

Hidden flaw jeopardizes millions of online transactions (ang.)

A więcej technicznych szczegółów tutaj (ta instytucja razem z New York Timesem pierwsza zabiła na alarm):

Researchers Use EFF’s SSL Observatory To Discover Widespread Cryptographic Vulnerabilities (ang.)

No i oczywiście u źródła, czyli w samej publikacji matematyków:

Ron był w błędzie, Whit ma rację (ang.)

A więcej o szyfrowaniu algorytmem RSA w tej pracy w języku polskim:

Przełamywanie szyfru RSA

Bestsellery

Kurs Matura Rozszerzona (Formuła 2023 i 2015)

Szkoła Średnia / Autor: mgr inż. Anna Zalewska

59,00 

Kurs Prawdopodobieństwo

Studia / Autor: mgr Krystian Karczyński

39,00 

Kurs Mechanika - Statyka

Studia / Autor: mgr inż. Adam Kasprzak

39,00 

Kurs Macierze

Studia / Autor: mgr Krystian Karczyński

39,00 

Zobacz wszystkie Kursy eTrapez

Szukasz korepetycji z matematyki na poziomie studiów lub szkoły średniej? A może potrzebujesz kursu, który przygotuje Cię do matury?

Jesteśmy ekipą eTrapez. Uczymy matematyki w sposób jasny, prosty i bardzo dokładny - trafimy nawet do najbardziej opornego na wiedzę.

Stworzyliśmy tłumaczone zrozumiałym językiem Kursy video do pobrania na komputer, tablet czy telefon. Włączasz nagranie, oglądasz i słuchasz, jak na korepetycjach. O dowolnej porze dnia i nocy.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Twój komentarz będzie dostępny publicznie na naszej stronie razem z powyższym podpisem. Komentarz możesz zmienić, lub usunąć w każdej chwili. Administratorem danych osobowych podanych w tym formularzu jest eTrapez Usługi Edukacyjne E-Learning Krystian Karczyński. Zasady przetwarzania danych oraz Twoje uprawnienia z tym związane opisane są w Polityce Prywatności.


  1. Sebastian pisze:

    Można wiedzieć czy będzie kurs z matematyki dyskretnej? Pytam bo w tym semestrze mam ten przedmiot i czuje, że bez jakiegoś dobreg kursu (czyt. E-Trapeza) może być ciężko …

    1. Krystian Karczyński pisze:

      Dzień dobry

      Nie, w najbliższym czasie nie szykują się nowe Kursy…

  2. Iga pisze:

    panie Krystianie czy matematyka dyskretna została przez pana juz opracowana??? HELP

    1. Krystian Karczyński pisze:

      Nie, niestety nie mam do tego materiałów…

  3. Andrzej pisze:

    Ah szkoda, że nie będzie kursu z dyskretnej, ponieważ bardzo by się przydał w tym semestrze. Pozdrawiam

    1. Krystian Karczyński pisze:

      Pozdrawiam i powodzenia mimo wszystko!

  4. Olga pisze:

    A może jednak da się Pan namówić na matematykę dyskretną?

    1. Krystian Karczyński pisze:

      Dzięki, ale jeszcze nie w tym półroczu 🙂

    2. Piotr pisze:

      szkoda ze nie w tym półroczu, gdyż jest wielu potrzebujących

  5. marjan pisze:

    panie Krystianie, niech pan się pośpieszy z prawdopodobieństwem, mam w tym semestrze probablistykę, a kurs by pomógł 🙂

    1. Krystian Karczyński pisze:

      Dobra, zrobi się 🙂

  6. f pisze:

    Odchodząc od tematu, wiadomo już czy Statystyka będzie nastepnym tematem? Jeśli tak to kiedy można się spodziewać jego realizacji i ukonczenia? Nie ukrywam, iż mój popyt indywidualny na ten kurs właśnie wzrósł wraz z rozpoczęciem statystyki na II semestrze 😉

    1. Krystian Karczyński pisze:

      Niestety, jako następny powstanie Kurs Prawdopodobieństwa, a Statystyka będzie później. Nie sądzę, żebym zdążył ją zrobić w tym półroczu…

    2. f pisze:

      W sumie to dwa ściśle powiązane ze sobą tematy także może by je jakoś połączyć ? ;D

    3. Krystian Karczyński pisze:

      Myślałem o tym, ale za dużo materiału w jednym Kursie by wyszło. Niestety, wyjdą osobno.

    4. f pisze:

      Trudno, pozostaje liczyć, że jakimś cudem powstanie statystyka przed końcem semestru w postaci ewentualnego koła ratunkowego 😉 pozdrawiam