blog

Matematyczna Luka w Algorytmach Szyfrujących

Krystian

Założyciel i szef serwisu eTrapez.

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

Mieszka koło Szczecina. Lubi spacery po lesie, plażowanie i piłkę nożną.


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

Jedna z wielu opinii o naszych Kursach...

Świetny kurs, zagadnienia wytłumaczone w bardzo przystępny sposób. Niech o jego jakości świadczy fakt, że po jednorazowym wysłuchaniu i zrobieniu wszystkich zadań zdałam statystykę, z której miałam już dwa razy warunek.

Ewelina

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 email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Twój komentarz będzie dostępny publicznie na naszej stronie razem z powyższym podpisem. Adres email nie będzie dostępny publicznie. Komentarz możesz zmienić, lub usunąć w każdej chwili. Dane osobowe zawarte w komentarzu i podpisie traktujemy zgodnie z naszą polityką 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