RSA MD4

[Gość]

Ale to i tak sciema, bo to jest klucz 140-bitowy, a takich "slabych" sie nie uzywa, wiec problem nadal pozostaje :P

To nie uzywa sie tu 128bitowych?

Ale gdzie tam.. taki to nawet zwykly PC by zlamal w sensownym czasie chyba.

Uzywa sie conajmniej 1024-bitowych, to jest nieporownywalnie wiekszy klucz od 140 bitow i podejrzewam, ze nawet przy polaczeniu w jednosc kilku a nawet kilkunastu tych superkomputerow nie daly by one rade tego zrobic w sensownym czasie.

Pozatym zostal juz zlamany klucz 576 bitowy, wiec te 140 to smiech na sali :) Łamali go za pomoca 100 kompow (nie wiem jakich) przez ok 3 miesiace. Trzeba wspomniec ze 1024 bitowy nie jest ~2 razy wiekszy od 576 tylko ok 2^450 razy wiekszy, chyba nie trzeba tlumaczyc jak duza to liczba? :]

[ParanoiK]

http://www.rsasecurity.com/rsalabs/node.asp?id=2093

 

Bawcie się ;]

[dzi]

Ale to i tak sciema, bo to jest klucz 140-bitowy, a takich "slabych" sie nie uzywa, wiec problem nadal pozostaje :P

To nie uzywa sie tu 128bitowych?

Ale gdzie tam.. taki to nawet zwykly PC by zlamal w sensownym czasie chyba.

Uzywa sie conajmniej 1024-bitowych, to jest nieporownywalnie wiekszy klucz od 140 bitow i podejrzewam, ze nawet przy polaczeniu w jednosc kilku a nawet kilkunastu tych superkomputerow nie daly by one rade tego zrobic w sensownym czasie.

Pozatym zostal juz zlamany klucz 576 bitowy, wiec te 140 to smiech na sali :) Łamali go za pomoca 100 kompow (nie wiem jakich) przez ok 3 miesiace. Trzeba wspomniec ze 1024 bitowy nie jest ~2 razy wiekszy od 576 tylko ok 2^450 razy wiekszy, chyba nie trzeba tlumaczyc jak duza to liczba? :]

Ah czyli RSA to ten co go pamietalem "ten z duzym kluczem", on byl jakis specjalny tam ale niewazne... Nie no jesli normalnie uzywa sie 1024 to jasne ze bieda ale wtedy nikt by nie robil tej proby wiec cos mi sie nie zgadza...

Inna sprawa ze skoro RSA sie uzywa to napewno jest bezpieczny, dlatego ja nie wnikam w te "proby lamania".

[Gość]

[...]ale wtedy nikt by nie robil tej proby wiec cos mi sie nie zgadza...

Jakiej proby? tej z lamaniem RSA-576 ? To bylo lamanie brute-force, jak wiesz trwalo 3 miechy, nastepny klucz 640 bit trwalby juz nieporownywalnie dluzej, ciezko mi strzelac, nie jestem bielgym matematykiem, ale na 100% w latach (i to raczej dziesiatkach/setkach niz mniej), przy zalozeniu tej samej mocy obliczeniowej, zobacz ile jeszcze jest krokow do 1024... na dzien dzisiejszy nie ma chyba jednostki czasu, w ktorej mozna by to zaprezentowac, zeby nie bylo zbyt duzo cyferek przez przecinkiem :>

Fakt, ze z roku na rok komputery sa coraz szybsze, ale bez przesady, chociaz gdyby zrobic projekt obliczen rozproszonych a'la Seti to kto wie, czy nie dalo by sie 1024 zlamac w mniej niz rok :)

[ParanoiK]

Polecam do poczytania:

http://www.signet.pl/archiwum/93.html

 

i kilkoma ciekawymi komentarzami do artykułu na linuxnews:

 

http://hedera.linuxnews.pl/_forum/00/_defa...long/1104.shtml

[Gość]

Przeczytalem wszystko i generalnie wynika z nich ze mam racje :)

[ParanoiK]

Pamiętam kiedyś na zajęciach bodajże z technik komputerowych liczyliśmy ile może zająć złamanie /obym nie skłamał - ale pewnie skłamię i tak/ kodu 4096 bitowego bez zastosowania algorytmów optymalizacyjnych i tego typu bajerów. Przy wykorzystatniu wszystkich komputerów świata i uwzględnieniu współczynnika moore'a wyszło jakieś 4 miliardy lat w przybliżeniu ;] Kto się podejmuje wyzwania? ;]

[piotrpo]

Akurat algorytmy na łąmanie RSA sa dostępne od wieków, takie sito Erastotenesa

Sito Eratostenesa to nie jest algorytm na lamanie RSA tylko na sprawdzanie liczb pierwszych, fakt, ze sie to akurat przydaje w RSA, ktore na liczbach pierwszych jest oparte, ale wlasnie sila RSA polega na tym, ze nie da sie w rozsadnym czasie rozlozyc duuzej liczby (bo takie sa klucze) na iloczyn 2 liczb pierwszych.

Cóż, powstał przed szyfrem RSA, ale się "doskonale" nadaje do odtwarzania kluczy prywatnych :D Ostatecznie musisz jedynie znaleźć jakiś dzielnik do klucza publicznego (konkretnie do znanej liczby pq). Problemem jest czas wykonania i pamięć, czytałem jakies śmieszne wyliczenie, że potrzebna była by macież dyskowa o wadze zbliżonej do naszej galaktyki, a mówimy cały czas o względnie słabych kluczach stosowanych publicznie, w przypadku których zawsze może ci się poszczęścić i trafisz na klucz półsłaby (taki w którym użyto liczby nie bedącej liczbą pierwszą). Dodatkowo w kryptograficznej paranoii nie zaleca się już stosowania MD-5 o MD-4 nie wspominając, teraz na topie są SHA-1/2

[piotrpo]

Uzywa sie conajmniej 1024-bitowych, to jest nieporownywalnie wiekszy klucz od 140 bitow

Z tymi kluczami to nie zupełnie tak :| Po prostu RSA wymaga dużo większego klucza niż algorytmy symetryczne (taki np. AES-128 jest na chwilę obecna nie łamalny) w przypadku RSA musisz sprawdzać jedynie do sqr(kucz), do tego jedynie liczby pierwsze, zawęża to dość znacznie przestrzeń możliwych kluczy. Do tego dochodzi jeszcze głupota niektórych użutkowników, korzystających z kopert RSA - DES, co z tego że nie złamiesz rsa, jeżeli czas łamania właściwej wiadomości jest kwestią godzin...

Generalnie, 256 bitów klucza symetrycznego (np. AES) oznacza, że wiadomości nie uda sie odszyfrować, zanim słońce nie stanie się supernową, ale 256 bitów w RSA to już czas bardzo realny.

[Gość]

Ale nie mowimy tutaj o RSA-256... taki klucz juz dawno przez RSA Security zostal uznany jako malo bezpieczny (czyt. niebezpieczny)

[piotrpo]

Dobra, mówimy to samo o tym samym, tylko się nie rozumiemy, wracając do pierwszego posta w tym wypadku jest to algorytm podpisu elektronicznego, wykorzystuje on "symetryczność" kluczy RSA czyli fakt, że jeżeli jesteśmy w stanie odczytac wiadomość za pomoca klucza publicznego (czyli odwrotnie) to została ona zaszyfrowana z użyciem klucza prywatnego. Po prostu RSA-MD4 oznacza, że został zrobiony hash z wiadomości za pomoca MD4 i zaszyfrowany kluczem prywatnym RSA autora. Za pomoca jego klucza publicznego jesteśmy w stanie to stwierdzić. Nie istnieje możliwość przekształcenia tego na cokolwiek innego.

[dzi]

[...]ale wtedy nikt by nie robil tej proby wiec cos mi sie nie zgadza...

Jakiej proby? tej z lamaniem RSA-576 ? To bylo lamanie brute-force, jak wiesz trwalo 3 miechy, nastepny klucz 640 bit trwalby juz nieporownywalnie dluzej, ciezko mi strzelac, nie jestem bielgym matematykiem, ale na 100% w latach (i to raczej dziesiatkach/setkach niz mniej), przy zalozeniu tej samej mocy obliczeniowej, zobacz ile jeszcze jest krokow do 1024... na dzien dzisiejszy nie ma chyba jednostki czasu, w ktorej mozna by to zaprezentowac, zeby nie bylo zbyt duzo cyferek przez przecinkiem :>

Fakt, ze z roku na rok komputery sa coraz szybsze, ale bez przesady, chociaz gdyby zrobic projekt obliczen rozproszonych a'la Seti to kto wie, czy nie dalo by sie 1024 zlamac w mniej niz rok :)

Chodzilo mi o to ze skoro stosuje sie 1024bit to chwalenie sie ze sie zlamalo 140bit jest smieszne i bezsensowne :) No ale poczytalem na stronie RSA i teraz czaje.

[Gość]

Otoz to... to jest "smieszne", nawet RSA-576 jest smieszne w porownaniu do 1024, wiec poki co nie ma sie co bac.

[piotrpo]

Tego typu działania nie są moim zdaniem śmieszne - pozwalają realnie ocenić bezpieczeństwo konkretnych algorytmów i kluczy. Ostatnio zresztą, AFIK został złamany klucz o długości 600 paru bitów. Do celów podpisu elektronicznego stosuje się klucze 1024-bitowe, bo takie są ograniczenia techniczne tzw. komponentów technicznych czyli modułów kryptograficznych. Wyliczanie "mocy klucza" też nie jest takie proste, do złamania klucza RSA nie trzeba sprawdzać 2^1024 przypadków, a jedynie ułamek tej liczby - takie przypadki które sa liczbami pierwszymi, mniejszymi od sqrt(2^1024). Innym przypadkiem jest DES i 3DES - klucze odpowiednio mają długość odpowiednio 56 i 168 bitów, czyli "intuicyjnie" 3DES jest 2^112 raza silniejszy, tym czasem faktycznie jego odporność wzrasta jakieś 2x (2^1). Oba z tego co wiem zostały złamane...

Jak chcesz ukryć korespodencję przed wścibskim adminem, to wystarczą najprostsze rozwiązania, ale jeżeli potrzebujesz bezwzględnego bezpieczeństwa, to pare rzeczy trzeba niestety wiedzieć. Jak ktoś chce się pobawić to niech zrobi sobie certyfikat poczty elektronicznej w www.certum.pl (free) równiez na tych stronach jest sporo informacji o zastosowaniach szyfrówm.

[Gość]

Tego typu działania nie są moim zdaniem śmieszne - pozwalają realnie ocenić bezpieczeństwo konkretnych algorytmów i kluczy.

No jasne, chodzilo mi o to, ze od informacji o zlamaniu RSA o takiej a takiej mocy daleko jeszcze do zlamania RSA-1024, nawet bardzo daleko, conajmniej przez kilka lat mozna go bezpiecznie uzywac.

Ostatnio zresztą, AFIK został złamany klucz o długości 600 paru bitów.

RSA-576 konkretniej