Klucz RSA 4096 bitów niby złamany, ale nie ma powodów do niepokoju
(źródło: takacsi75)
Badacze ogłosili, że ku swojemu zaskoczeniu złamali właśnie klucz RSA o długości 4096 bitów, należący do jednego z najważniejszych programistów jądra Linuks. Jest to jednak – z wielu powodów – bardziej ciekawostka, niż powód do zmartwienia.
Autorzy projektu „Phuctor: The RSA Super Collider.” właśnie poinformowali, że stworzony przez nich system odkrył fatalny błąd w kluczu PGP Hansa Petera Anvina, programisty znanego ze stworzenia wielu funkcji jądra Linuks. Przyczyny powstanie błędu są nieznane, ale jego skutkiem jest trywialna możliwość złamania bezpieczeństwa klucza. Nie wszystko jednak w tej sprawie jest jasne.
Liczba pierwsza podzielna przez 77 (i 3)
Zanim rzucicie się do pisania komentarzy o treści „tytuł pierwszego akapitu zawiera błąd logiczny” przeczytajcie wyjaśnienie. Siłę algorytmu RSA zapewnia matematyka. Jego podstawowa konstrukcja opiera się na tzw. problemie faktoryzacji iloczynów liczb pierwszych. O ile łatwo jest pomnożyć przez siebie dwie liczby pierwsze, takie jak np. 65537 i 65539, o tyle ustalenie, wynikiem jakiego mnożenia jest liczba 4295229443 zajmuje znacząco więcej czasu. Można próbować dzielić 4295229443 przez wszystkie kolejne liczby, jednak to bardzo pracochłonne zajęcie. Można także skorzystać z algorytmu sita kwadratowego (dla liczb krótszych niż 150 cyfr dziesiętnych) lub algorytmu GNFS (dla liczb większych niż 100 cyfr dziesiętnych), jednak dla liczb dłuższych niż ok. 232 liczby dziesiętne (768 bitów) te ataki stają się całkowicie nieprzydatne – czas ich trwania rośnie wykładniczo wraz z długością atakowanej liczby.
Jak zatem udał się atak na klucz o długości 4096 bitów? Badacze nie wierzyli temu, co zobaczyli. Okazuje się, że w badanym kluczu jedna z liczb pierwszych, składających się na iloczyn, była zaskakująco mała – i do tego nie była liczbą pierwszą. Algorytm badaczy odkrył, że dla tego klucza iloczyn jest podzielny przez liczbę 231 (która sama jest podzielna przez 3 i 77).
817023023960376946633975507110154649249407598806798730414849884461776172171921668594148071323527016137506405823108520062504849249423700259406905313281403901410082762097159560221463048924336192384026777502177262731045200322200149773127502888545234973139480887644585192600631058962876114156934248895171959246969597637127280010272143593885240940877456234662196130491400738438731832514335353824697930453078426722191105157568392826870043655708008545411143367763836566011740499383456592129662585004880376777597714978023542434421914201119537685489173509942329090631662014650033142642110914360849421856179611226450806562235534802516081595259914768497444702718749402330070488028751073730349460752771915484847399385631524708487646079936572410398967582895983187640798072309362094727654167628620105981459021548290415800096769214437425690934372015628796027498219902441288189398386359846661623243493534897411417685435424010451956954083531228374002591372549525280610594684910812811287436481207089763125424247793044043309737269468709710679872269272855389945385386467765509880648929743498214329578288874987193768439353382305260108425688024147656806932474058888992099083804597481699305852902662863062054067183925164590726103552998367994727700722491707 `mod` 231 = 0Oznacza to, ze dla tego konkretnego klucza publicznego można bez problemu obliczyć wartości potrzebne do wygenerowania klucza prywatnego. Klucz zatem jest złamany, ale trzeba jeszcze odpowiedzieć na kilka zaj… errr bardzo ważnych pytań.
Losowy obrazek z kluczami (źródło: bohman)
To tak można generować klucze?
Czy generatory kluczy PGP/GPG powinny dopuszczać do takich sytuacji, że jedna z liczb pierwszych jest śmiesznie mała? I do tego nie jest liczbą pierwszą? Odpowiedź brzmi oczywiście: NIE. Nie wiemy, jak ten klucz został wygenerowany. Możliwe scenariusze to:
- wyjątkowo słaby generator liczb pseudolosowych/losowych
- niski poziom entropii zasilającej generator
- fatalna implementacja generowania kluczy, która nie potrafi wykryć takich przypadków i ich odrzucić
- celowe działanie wroga (tylna furtka)
- celowe działanie trolla (o tym za chwilę).
Tak czy inaczej, pojawienie się takich wartości w kluczu RSA nie powinno mieć miejsca. Sam algorytm RSA nie jest tym odkryciem zagrożony – jedyne ryzyko wiąże się z tym, że być może tak błędnie wygenerowanych kluczy jest gdzieś więcej. Już wcześniejsze badania wykazywały, że źle wygenerowanych klucz nie brakuje w sieci.
Troll miesiąca?
Wiadomość o odkryciu szybko obiegła tę część internetu, gdzie nikt nie śpi bo pilnuje swoich kluczy i wzbudziła zrozumiałe obawy i wątpliwości ekspertów. Eksperci przystąpili zatem do własnych eksperymentów i ustalili, że:
- klucz ten jest jednym z pod-kluczy klucza głównego Hansa Petera Anvina,
- z trzech pod-kluczy akurat ten jeden nie jest przez niego podpisany,
- nie we wszystkich źródłach, z których klucz Anvina można pobrać, klucz ten wygląda identycznie.
gpg --verbose --keyserver hkp://hkps.pool.sks-keyservers.net --recv-key 0xbda06085493bace4
gpg: requesting key 0xBDA06085493BACE4 from hkp server hkps.pool.sks-keyservers.net
gpg: armor header: Version: SKS 1.1.5
gpg: armor header: Comment: Hostname: keyserver.witopia.net
gpg: pub 4096R/0xBDA06085493BACE4 2011-09-22 H. Peter Anvin <[email protected]>
gpg: key 0xBDA06085493BACE4: invalid subkey binding
gpg: key 0xBDA06085493BACE4: skipped subkey
gpg: key 0xBDA06085493BACE4: "H. Peter Anvin (hpa) <[email protected]>" not changed
gpg: Total number processed: 1
gpg: unchanged: 1Wygląda zatem na to, że mamy raczej do czynienia z prawie udanym atakiem na system dystrybucji kluczy niż z atakiem na algorytm RSA. Autorzy badania utrzymują, że klucz do testu pobrali z publicznego, zaufanego źródła. Jak zatem tam się znalazł? Czekamy na aktualizacje. Na razie śpijcie spokojnie, Wasze klucze są nie do złamania (przynajmniej oficjalnie). Polecamy także wątek na Hacker News.
NSA pewnie crackuje takie klucze od dawna :) Oczywiście niekoniecznie bruteforce.
Czy dla 2048 albo 4096 bitowych kluczy nie można raz wygenerować wszystkich możliwych wyników mnożenia by móc łamać potem wszystkie klucze?
Można, tylko nie wiem czy starczy dysków w Amazonie.
Właśnie na ilości kombinacji opiera się bezpieczeństwo szyfrowania.
Dla porównania:
klucz 4096 bitowy zajmuje 512 bajtów czyli 2^9 bajtów
Dysk o pojemności 1TB (2^40 B) zmieści takich kluczy 2^31 czyli jakieś 2mld
A teraz pomyśl ile trzeba takich dysków by zmieścić wszystkie kombinacje mnożeń dla 4096 bitowych kluczy.
2^4096 / 2^31 = 2^4065 dysków 1TB – nawet gdyby taki dysk miał wielkość 1 atomu to taka ilosć dysków wypełniłaby spokojnie cały wszechświat, nie mówiąc o tym ile czasu zajełyby obliczenia.
Jeśli ktoś chce łamać RSA, niech lepiej kombinuje nad algorytmami szybkiej faktoryzacji lub sposobami wykradania kluczy.
Klucz 2^4096 bitowy może zajmować kilka bajtów, nikt nie każe zapamiętywać binarny zapis klucza, zapis wartości może być symboliczny np. 2^4096-2^1234 – proszę mamy 13 bajtów.
A niech nawet zajmuje 0.0000001 bita to i tak w praktyce wiele nie zmienia. Pomysł jest praktyczny tylko dla stosunkowo małych ilości kombinacji np ilość danych w internecie szacowana jest na pare exabajtów czy tam zetabajtów a to tylko 2^60B – 2^70B. A poza tym nie każdą liczbę tak zapiszesz (niektóre tak zapisywane będą dłuższe, a inne krótsze). Ale fakt że da się taką bazę zoptymalizować i uzyskać setki,tysiące czy nawet miliony razy mniejszą ilość danych, ale to w praktyce wiele nie zmienia przy tak dużej ilości kombinacji. Ta metoda jest nieopłacalna, bo nawet banalnego do złamania klucza 128 bitowego byś tą metodą nie złamał (no może byś i złamał ale nie było by to opłacalne), choć odpowiednimi metodami udało się złamać klucz o długości ponad 700 bitów.
Popełniacie błąd logiczny. Zapisanie wszystkich wyników nie było by dla nikogo problemem (kompresja danych, ktoś coś?) i w cale nie potrzeba było by ogromnych ilości miejsca (zwłaszcza, że akurat przy RSA np. ciągi słownikowe mogły by mieć niemalże nieograniczoną długość – w zastosowaniu do jednego wyniku oczywiście). Problemem jest to, że przy dzisiejszej technologii OPERACJE generowania wyników i ich zapisu trwały by niemalże nieskończenie długo ;) Co więcej, nie potrzebujemy nawet zapisywać tych wyników, bo wszystkie z nich są już znane – żaden komputer nie ma najmniejszych problemów z podaniem wyniku mnożenia prawie dwóch, dowolnych liczb, o dowolnym rozmiarze (o ile tylko wam wystarczy pamięci aby przedstawić jeden wynik) i operacja taka w cale nie będzie trwała jakoś niesamowicie długo, co również wykorzystuje RSA w swoim algorytmie. Jeżeli ktoś znajdzie sposób na szybkie obliczanie WSZYSTKICH wyników (z niemal nieskończonego zbioru), wtedy i tylko wtedy złamie RSA (i tutaj pojawiają się komputery kwantowe, ale nie te, które obecnie się testuje, posiadające 2-3 kubity, tylko te, które posiadają setki milionów kubitów na jednym rdzeniu procesora – moc obliczeniowa takiego procesora robiła by RSA czy AESa niemalże w czasie rzeczywistym ;) ).
@jozek – chciałem tylko wykopkowi zobrazować o jak dużej ilości danych mówimy i wykazać że jego metoda jest „mało praktyczna”.
Algorytmy kompresji raczej się nie sprawdzą bo:
a) musisz mieć co kompresować (potrzebny czas na wygenerowanie)
b) jaki algorytm kompresji pozwoliłby spakować tak dużą ilość danych, a jednocześnie pozwoliłby na dostanie się w krótkim czasie do konkretnych danych.
„Co więcej, nie potrzebujemy nawet zapisywać tych wyników, bo wszystkie z nich są już znane” – no właśnie nie znamy mając tylko klucz publiczny. W rozwiązaniu o którym rozmawiamy chodziło o to by stworzyć coś w rodzaju tablicy indeksowanej kluczami publicznymi, a elementami tablicy są czynniki pierwsze podanej liczby.
Nie wiem jak wypada komuter kwantowy vs AES, ale co do RSA to się zgadza. Poza tym AES nie jest algorytmem konkurencyjnym do RSA, bo to alg symetryczny. Z tego co wiem to komputery kwantowe nie są lepsze we wszystkim od zwykłych komputerów, więc pewnie da się stworzyć algorytm szyfrowania odporny na ataki kwantowe jak alg NTRU. I z tego co wyczytałem na wikipedii to nie testują 2-3 kubitów:
„W 2011 roku udało się stworzyć układ złożony z 10 miliardów kubitów, a 2 lata później powiodło się utrzymanie 10 miliardów kubitów w stanie splątanym przez 39 minut.” ;D
@nikt
„a) musisz mieć co kompresować (potrzebny czas na wygenerowanie)”
– tak, ale ja już mówiłem o teoretycznym posiadaniu wyników ;)
„b) jaki algorytm kompresji pozwoliłby spakować tak dużą ilość danych, a jednocześnie pozwoliłby na dostanie się w krótkim czasie do konkretnych danych.”
– samo LZW dało by bardzo dobre efekty ;)
„W rozwiązaniu o którym rozmawiamy chodziło o to by stworzyć coś w rodzaju tablicy indeksowanej kluczami publicznymi, a elementami tablicy są czynniki pierwsze podanej liczby.”
– gdzie się niby pomyliłem? Jestem człowiekiem myślącym do przodu, dla mnie „wynik” to już skończona operacja wszystkich założonych/koniecznych przebiegów.
„no właśnie nie znamy mając tylko klucz publiczny.”
– przyjmijmy że posiadamy pewien zbiór skończony, o niepoliczalnej ilości elementów (taki paradoks). Jesteśmy z niego wstanie wyciągnąć jeden dowolny wynik (składową kilku operacji), ale nie jesteśmy wstanie podać wszystkich wyników. Chcesz powiedzieć, że nie znasz wszystkich wyników? ;) Matematyka dyskretna stwierdza jasno – jeżeli znasz sposób na otrzymanie wyniku, znasz wszystkie wyniki, ale nie koniecznie możesz wszystkie przedstawić. Przy mnożeniu liczb, znasz wszystkie możliwe składowe i możesz wyciągnąć dowolny, pojedynczy wynik operacji (dla kogoś było by problemem pomnożenie 7^100 x 7^100? Odpowiedź jest prosta – google robi to w 0.02 sec ;) , ale wypisanie wszystkich wyników mnożenia 7^100 x 7^n+1 n=1 jest już bardzo problematyczne).
Czasem się mogę wypowiadać z sposób „mało polski”, sorry :P
@jozek – tak mnożenie jest bardzo proste problem w tym że mamy wynik i chcemy poznać czynniki pierwsze.
Potęgowanie też:
7^100 x 7^100=(((((((7^2*7)^2)^2)^2*7)^2)^2)^2 – i można nawet na kartce przeliczyć ;D
Omawiany sposób polega na tym że robimy tablicę zawierające wszystkie kombinacje mieszczące się w n-bitowym kluczu i umieszczamy w odpowiednim miejscu tablicy np:
7*11=15 => 7 i 11 umieszczamy w komórce o indeksie 77.
7*12=18 => 7 i 12 umieszczamy w komórce o indeksie 84.
7*13=21 => 7 i 13 umieszczamy w komórce o indeksie 91.
Po wypełnieniu tak tablicy możemy z łatwością łamać dowolny klucz RSA o tej długości, lub krótszy po prostu dając klucz jako indeks tablicy tzn dla równania A*B=C mając tylko C możemy tablica[C].A i tablica[C].B
I tu jest problem z wielkością takiej tablicy.
@nikt
Mam dziwne wrażenie, że ty w ogóle nie czytasz bądź nie rozumiesz tego, co napisałem ;)
Ale wytłumaczę Ci – w przykładzie z twojego ostatniego komentarza, liczysz sobie mnożenie liczb pierwszych i zapisujesz do tablicy – bardzo fajnie. W innych słowach, liczysz mnożenie dwóch liczb z nieograniczonego zbioru i zapisujesz wynik (nie ma znaczenia gdzie). Dokładnie to, co napisałem w moich dwóch poprzednich komentarzach. Wasz problem logiczny, przy którym was usiłuje poprawić, polega na tym, że problemem nie jest ZAPISANIE i PRZECHOWYWANIE tych wyników, tylko że czas wykonania operacji MNOŻENIA dwóch liczb oraz ich ZAPISU/PRZEDSTAWIENIA dąży do nieskończoności i to jest faktyczny problem (i to nie ważne co liczycie, czy mnożenie, faktoryzacje liczb, potęgi, czy samo generowanie kluczy publicznych i ich odpowiadających kluczy prywatnych). Obecnie procesory posiadają KILKASET milionów tranzystorów (bitów), może nawet i miliardów, wykonanie dla nich mnożeń dwóch dowolnych liczb nie jest JAKIMKOLWIEK problemem, co oznacza, że możesz sprawdzić sobie wynik mnożenia dwóch, dowolnych liczb (liczb, mieszczących się na milionach bitów), w ułamki sekund. Problem jest taki, że obecna technologia jest synchroniczna i sekwencyjna – procesor w jednej chwili może wykonywać tylko JEDNĄ operację (o ile nie jest wielowątkowy/wielordzeniowy). Załóżmy, że bierzemy pod uwagę NAJPROSTSZY możliwy model pracy procesora przy mnożeniu dwóch liczb – 1. pobranie liczb z pamięci 2. wykonanie operacji 3. przesłanie danych do pamięci (prezentacja wyniku, bez jego zapisu). W tym modelu pomijamy wszelką komunikację z pozostałymi podzespołami, pomijamy odczyty rejestrów, odczyt pamięci cache itd. W momencie, w którym mnożysz TYLKO dwie liczby, operacja taka trwa… no bardzo szybko :) Ale w momencie, w którym szukasz WSZYSTKICH wyników operacji dla nieograniczonego zbioru liczb, szybkość wykonania An+1 x Bn+1 n=1 rośnie… w zastraszającym tempie dążąc do nieskończoności :) Tutaj idealnym przykładem jest działanie CERNu. Oni produkują 35 petabajtów każdego roku, nikt nie ma problemu z zapisem takich ogromnych ilości danych (inną sprawą jest znalezienie najwygodniejszego i najbardziej optymalnego nośnika), problemem jest to, że gdyby pozwalały na to obecne procesory, pamięci, czujniki itd. produkowali by 700 petabajtów każdego roku ;) Niestety, nie pozwala na to po prostu prędkość obliczeniowa, którą dysponują. Załóżmy, że łamiesz bruteforcem jakieś hasło – nie ważne ile tych kombinacji jest, sprawdzanie ich trwa ze stałą prędkością (w konkretnym czasie), jednak czas wykonania operacji jest w pełni zależny od ilości cyfr (kombinacji) składających się na dane hasło. Dlatego, łamanie hasła 4 znakowego z tablicy posiadającej 64 elementy trwa 3 minuty, ale 8 znakowego z tablicy posiadającej 64 elementy 12 godzin (przykład, wszystko zależy od procesora) – a wszystko to dlatego, że procesor wykonuję konkretny cykl operacji i wykonanie jednego cyklu ma swój przebieg czasowy. Nic nie stoi jednak na przeszkodzie, żeby sprawdzić jeden, konkretny wynik np. omgzeco1. To jest właśnie prawdziwe piękno problemów obliczeniowych – wszystko trwa zbyt długo, by się chciało komukolwiek mimo, że wszystko już znamy :) To dlatego technologia kwantowa tak bardzo ludzi pociąga, bo dzięki superpozycjom można wykonywać nie konkretnie jedną, ale wiele (milionów? ;) ) operacji w tym samym czasie. I nie czytaj pierdół na wikipedii, nie ma jeszcze ŻADNEGO komputera kwantowego, są komputery, które działają na pewnych zależnościach kwantowych (przykładowo na wyżarzaniu kwantowym), ale nikomu nie udało się jeszcze stworzyć i utrzymać prawdziwej superpozycji na tyle, by stworzyć działający komputer. Rekord utrzymania prawdziwej superpozycji, przy pomocy ciekłego azotu, to coś koło 9 sekund, w 9 sekund nawet helloworda nie napiszesz i nie skompilujesz :P
@jozek – to nie jest błąd logiczny tylko mówimy o jednym z problemów, ale oczywiście istnieje drugi co najmniej równie poważny czyli czas/wydajność.
35PB czyli 35*2^50B to może nie problem, ale tablica 2^4096 elementowa już porządnie zapycha miejsce na dysku ;)
Tak w ogóle to procesor nie musi mieć wielu rdzeni/wątków by wykonywać obliczenia równolegle, przecież w potokach kolejne instukcje zaczynają się zanim poprzednie się skończą, a w niektórych architekturach późniejsza instrukcja może skończyć się wcześniej niż poprzednia (na ia64 była chyba nawet instrukcja (2 średniki na końcu instrukcji assemblera) by powiadomić kompilator że te instrukcje można zrównoleglić). Do tego chyba istnieją jakieś instrukcje operujące na wektorach (przemnożenie wszystkich elementów kilku elementowej tablicy na raz). Oczywiście takie optymalizacje nie rozwiązują całkowicie powyższego problemu. Na komputerach kwantowych się nie znam, ale gdyby komuś udało się stworzyć nawet jakiś względnie prosty, to nie koniecznie musielibyśmy się o tym dowiedzieć od razu ;)
`Klucz 2^4096 bitowy może zajmować kilka bajtów` – a nieprawda. Tzn. jeden klucz może zajmować mniej bajtów, ale – zgodnie z pigeonhole principle – jeśli wygenerujesz wszystkie możliwe klucze (a taki jest cel) to będą zajmować CO NAJMNIEJ 2^4096 bita na klucz (podstawy kompresji danych się kłaniają).
Chyba coś namieszałeś. Wtedy przykładowo kodowanie Huffmana nie miało by żadnego sensu, bo długość bitów przedstawiających konkretne, różne wartości była by nie zmieniona, a o to przecież w Huffmanie chodzi ;) Ogólnie wiem o co chcesz powiedzieć, tylko źle się do tego zabrałeś. http://pl.wikipedia.org/wiki/Zasada_szufladkowa_Dirichleta
wystarczy komputer kwantowy i kilka sekund;)
„2^4096 / 2^31 = 2^4065 dysków 1TB – nawet gdyby taki dysk miał wielkość 1 atomu to taka ilość dysków wypełniłaby spokojnie cały wszechświat, nie mówiąc o tym ile czasu zajęłyby obliczenia.”
W powyższej wypowiedzi przecenia pan wszechświat i to o spooooro rzędów wielkości:
Liczba fundamentalnych cząstek w obserwowalnym wszechświecie estymowania jest na między 10^80 a 10^85 czyli liczba z 81 lub 86 cyframi. Oczywiście liczba atomów jest od tego mniejsza, nawet jeśli przyjąć, ze są to same atomy wodoru, czyli w stanie normalnym to elektron, neutron i proton (czyli elektron i 6 kwarków na 1 atom). Wtedy jednak pomijamy neutrina, fotony, i całą resztę cząstek elementarnych, a zliczamy tylko elektrony i kwarki górne i dolne. Ale to i tak nie powinno być przedmiotem porównania, bo mamy lepszą liczbę: Skupmy się na objętościach Plancka. Tych w obserwowalnym wszechświecie jest 4×10^185 – to liczba o 186 cyfrach. (W atomie wodoru mieści się 1,6×10^73 objętości Plancka. Liczba uśredniona, bo zależnie od konfiguracji objętość atomu wodoru może być trochę inna.)
Mimo to ta liczba o 186 cyfrach jest niczym w porównaniu z liczbą dysków jaką pan wyliczył, czyli 2^4065 – ta liczba ma 1224 cyfry; ( a 2^4096 ma 1234 cyfry).
Liczba z 1224 cyframi w porównaniu do liczby mającej 186 cyfr jest o 1039 rzędów wielkości większa. Ignorując tą czwórkę w liczbie 4×10^185, która i tak niewiele tu zmienia, gdy mamy tak znaczą różnicę rzędów wielkości to: liczba objętości Plancka w obserwowalnym wszechświecie jest o 1039 rzędów wielkości mniejsza niż wymagana liczba dysków do przechowania wyników mnożeń dla 4096 bitowych kluczy bez kompresji. Czyli nawet jeśli dysk był by nie wielkości atomu wodoru, ale wielkości objętości Plancka, to dana liczba dysków (2^2065) wypełniła by z grubsza 10^1038 obserwowalnych wszechświatów. Czyli liczbę o tysiąc trzydziestu dziewięciu cyfrach. Inaczej mówiąc 10^939 zbiorów w których każdy z tych zbiorów zawierał by googol wszechświatów, czyli jedynkę ze stoma zerami wszechświatów każdy o rozpiętości 93 miliardów lat świetlnych.) Tak dla zobrazowania.
Co więcej, nawet jeśli stosować by kompresję to i tak nawet przy 1000 krotnej kompresji, w wyniku której potrzeba by tysiąc razy mniej dysków, zyskujemy wtedy tylko 3 rzędy wielkości, i z różnicy 1039 rzędów wielkości zrobi się różnica 1036 rzędów, także to niewiele zmienia w ogólnym rozrachunku.
Jeśli jest jakaś pomyłka w tych zgrubnych obliczeniach i porównaniach, to dajcie znać.
Pannie Salander udało się załamać RSA za pomocą krzywej eliptycznej, pff
Czy komuś udało złamać klucz RSA 4096 i odszyfrować pliki?
Landauer’s principle!
Ja od początku tego roku używam już klucza o długości 8192 bity. Nie powiem jednak, żeby to było szybkie i bezproblemowe korzystanie.
Czy dobrze pamiętam że trzeba sobie zrekompilować GPG żeby móc taki wygenerować?
Dobrze pan pamięta. Ale nie to jest najgorsze. O wiele więcej jest problemów z kompatybilnością oprogramowania z kluczem takiej długości.
„trzeba sobie zrekompilować GPG”
W zasadzie tak:
https://lists.gnupg.org/pipermail/gnupg-users/2015-January/052149.html
a przy wersji 1.14 na pewno:
https://deekayen.net/large-gpg-keys
Gorsza sprawa, że taka długość klucza może przekładać się na różne jeszcze nieznane błędy, co może zmniejszać bezpieczeństwo. Ale to może być hoax :)
https://wiki.gnupg.org/LargeKeys
„Klucz zatem jest złamany, ale trzeba jeszcze odpowiedzieć na kilka zaj… errr bardzo ważnych pytań” – nikt? Naprawdę? Oj hakiery, klasyków nie oglądacie? :)
@Adam nie rób mi tak, do cholery. Zaplułem monitor.
Cicho, królu sedesów ;p
( chciałeś to masz :D )
Mała nieścisłość w artykule Panowie, ale aby wygenerować klucz RSA, wcale nie potrzebujemy liczb pierwszych, bo wystarczy para liczb względnie pierwszych, której reprezentacja bitowa jest odpowiedniej czyt. aktualnie uważanej za bezpieczną”długości” (patrz Funkcja Carmicheala λ(n)).
Czyli par takich jak 1001101 i 11 lub 100001 i 111 tudziez 10101 i 1011?
DSA. Ktoś? Gdzieś?
To wszystko było celowe.
Po co w ogole pisac do jakiejs losowej Julki? To jest wlasnie blad pierworodny kutzy, na ktorym przejechali sie eksperci z polskich marketow, czyli myslenie, ze komputerek zastapi podstawowa wartosc w relacjach miedzyludzkich, jaka jest zaufanie. A tego niestety nie da sie zdobyc bez nawiazania uprzednich stosunkow w swiecie rzeczywistym.
„(…) 231 (która sama jest podzielna przez 3 i 77).”
Dzielnikami liczby 231 są:
1, 3, 7, 11, 21, 33, 77, 231
z czego:
3, 7, 11
są liczbami pierwszymi.
Przepraszam, obejrzałem niedawno wykłada Tomasza Millera odnośnie hipotezy Riemanna i tam właśnie pojawiło się wykorzystanie liczb pierwszych w kryptografii.
Od razu mówię, że matematykę lubię, ale średnio ją zgłębiam, ale nie wydaje mi się (na mój chłopski rozum) by zdanie pojawiające się w wielu przypadkach (artykułach, wykładach):
przez siebie dwie liczby pierwsze, takie jak np. 65537 i 65539, o tyle ustalenie, wynikiem jakiego mnożenia jest liczba 4295229443 zajmuje znacząco więcej czasu. Można próbować dzielić 4295229443
Nie wydaje się to w ogóle skomplikowane dla zwykłego laika, który jest słaby z matematyki, więc nie rozumiem w jaki sposób znając wynik nie można ustalić iloczynu liczb pierwszych. Czy może mi ktoś pomóc wyjaśnić w czym jest problem?:)
Trochę odkop, ale spróbuję odpowiedzieć na pytanie. W ogólnym przypadku rozkład na czynniki pierwsze (faktoryzacja) nie jest problemem trudnym. Jeśli weźmiemy losową liczbę, to jest duża szansa, że posiada ona małe czynniki rozkładu. Wiadomo, że co 2 liczba dzieli się przez 2, co 3 przez 3, itd. Weźmy sobie jakąś losową liczbę z generatora liczb losowych, np. 628938602. Jej rozkład na czynniki pierwsze jest następujący: 2×29×31×499×701. Jak widać faktoryzacja tej liczby nawet z wykorzystaniem kalkulatora i kartki sprawdzając po kolei liczby pierwsze nie potrwałaby bardzo długo, przy wykorzystaniu komputera zajęłoby to ułamki sekund.
Jednak bezpieczeństwo kryptografii opartej na problemie faktoryzacji (np. RSA) wykorzystuje liczbę będącą iloczynem dwóch dużych liczb pierwszych, której faktoryzacja jest już problemem trudnym obliczeniowo. Przykładowo mamy iloczyn dwóch liczb 2048 bitowych, co daje nam liczbę o długości 4096 bitów. I teraz aby znaleźć dzielniki tej liczby algorytmem trywialnym należałoby sprawdzić wszystkie liczby pierwsze od 2 do 2^2048. Już samo wyznaczanie dużych liczb pierwszych, które chcemy sprawdzić jest problemem. Oczywiście istnieją algorytmy takie jak sito kwadratowe czy GNFS, które nieco przyspieszają faktoryzację, jednak nadal mają one złożoność podwykładniczą. Przykładowo faktoryzacja liczby 640 bitowej algorytmem GNFS trwała 5 miesięcy. Obecnie RSA-4096 jest uważane za bezpieczne rozwiązanie. Namieszać w faktoryzacji prawdopodobnie będą mogły dopiero komputery kwantowe, które powinny znacząco skrócić ten czas.