Preco je tazke prelomit sifru RSA ?

07.03.2008 16:43 | blackhole

Cielom tohto clanku je zoznamit citatela so zakladnymi principmi sifry RSA. Tento text neobsahuje ziadne matematicke dokazy. Co sa tyka matematiky, tak k pochopeniu clanku si vystacite s ucivom zakladnej skoly:-) Clanok pisem hlavne pre ludi, ktori sice poznaju vseobecny princip asymetrickeho sifrovania a aku ulohu zohrava verejny/sukromny kluc, ale nedostali sa hlbsie k fungovaniu sifry RSA. Ak algoritmus RSA dobre poznate, stale si tento clanok mozete precitat a do komentarov citatelov upozornit na chyby/nepresnosti.

Najprv vysvetlim zopar pojmov, s ktorymi budem neskor pracovat.

Eulerova totient funkcia.
Mozno to znie strasne, ale ide o celkom jednoduchu vec. Totient funkciu budem dalej znacit Phi. Na "vstupe" dostane prirodzene cislo n a vrati pocet cisel, ktore su mensie alebo rovne n a zaroven nemaju s cislom n ziadneho spolocneho delitela okrem cisla 1. Napriklad Phi(24) = 8 (odpovedajuce 8 cisel su: 1,5,7,11,13,17,19,23).
Tato totient funkcia ma niekolko jednoduchych vlastnosti, ktore sa vyuzivaju prave pri sifrovani RSA.
1. Ak je p prvocislo, potom Phi(p) = p - 1.
2. Ak cisla p,q nemaju spolocneho delitela okrem 1, potom Phi(p * q) = Phi(p) * Phi(q). (Priklad Phi(5*8) = Phi(5) * Phi(8) = 4 * 4 = 16. S cislom 40 su nesudelitelne tieto cisla: 1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39)

Dalej si vysvetlime zaklady modularnej aritmetiky.
Z bezneho zivota sme zvyknuti na fakt, ze cisiel je nekonecne vela. Ale ukazuje sa, ze niekedy je celkom vyhodne si predstavit, ze cisel mame iba konecny pocet. Samozrejme iba samotne cisla by nam boli na nic. Tak sa na nich definuju rozne operacie (plus, krat). Tieto operacie sa urcia tak, aby platili niektore zakladne vlastnosti, na ktore sme zvyknuti z matematiky zakladnej skoly. Uvediem konkretny priklad. Majme mnozinu cisel (0,1,2,3,4,5,6). Dalej si k nim definujme operacie plus a krat. pricom a plus b = a + b (mod 7). To "mod 7" znamena, ze delime cislom 7 a vysledkom je zvysok. Teda napr. 3 + 4 = 0 (mod 7), pretoze 3 + 4 = 7 & 7 dava po deleni 7 zvysok 0. Obdobne nadefinujeme na nasej mnozine cisel operaciu krat modulo n. a krat b = a * b (mod n). Kedze uz mame zavedene nasobenie modulo n, mozme si zaviest umocnovanie modulo n. V mnozine realnych cisel sme zvyknuti napriklad na to, ze ku kazdemu cislu existuje opacne. Napriklad k 7 je opacne cislo -7. Ale na nasej mnozine cisel mozme tiez najst k lubovolnemu cislu opacne. Pomozeme si faktom, ze sucet cisla n a (-n) je 0. Povedzme ze v nasej mnozine cisel hladame cislo opacne k 4. To je 3. Pretoze 4 + 3 = 0 (mod 7). Dalej sme zvyknuti z realnych cisel na operaciu deleno. Kedze uz vieme nasobit, staci nam, ak ku kazdemu cislu dokazeme najst jeho prevratenu hodnotu. Cize k cislu a hladame cislo b, aby platilo a krat b = 1 (mod 7). Cislu b potom hovorime, ze je multiplikativny inverz cisla a. (A naopak a je multiplikativny inverz cisla b). Lahko ku kazdemu cislu z nasej mnoziny (okrem 0, samozrejme:-) najdeme inverz, napr k cislu 5 je inverzne vzhladom na nasobenie cislo 3, pretoze 5 krat 3 = 1 (mod 7) Nasa mnozina ma celkom peknu vlastnost - ku kazdemu cislu okrem 0 dokazeme najst cislo inverzne. To ale nemusi platit o vsetkych takto "umelo" vytvorenych mnozinach cisel.

Teraz si konecne mozme napisat vzorcek, na ktorom je postaveny cely algoritmus RSA.
Nech n je prirodzene cislo, m je z mnoziny {0..n - 1} a dalej nech plati, ze e * d = 1 (mod Phi(n)).
Potom: m^(e*d) = m (mod n)

Zaujima Vas, ako sa da tento vzorcek pouzit na sifrovanie a nasledne desifrovanie? Jednoducho. Povedzme, ze mame spravu m reprezentovanu cislom. (Urcite si dokazete predstavit nejaky sposob, ako textovu spravu skonvertovat na cislo a naopak) Takze mame tajnu spravu m. Ak ju chceme zasifrovat, jednoducho ju umocnime na cislo e. Na to, aby sme spravu desifrovali, iba vysledok umocnime na d. Podla hore uvedeneho vzorceka dostaneme naspat cislo m - povodna sprava.

Popiseme si to este raz v terminologii asymetrickeho sifrovania. Alica chce odoslat spravu m Bobovi. Pred tym ju samozrejme musi zasifrovat Bobovym verejnym klucom. Bobov verejny kluc je dvojica (e, n). Alica teda spocita e-tu mocninu spravy m. Vypocet samozrejme robi modulo n. Bob prijme zasifrovanu spravu. Bobov sukromny kluc tvori dvojica (d, n). Zasifrovanu spravu umocni na d (mod n) a dostane povodnu spravu.

A preco je tazke prelomit RSA, alebo znamena RSA Really Stupid Algorithm?
Pozrime sa, co ma k dispozicii utocnik. Predpokladajme, ze sa mu podarilo zachytit zasifrovanu spravu, teda vysledok m^e. Takisto ma utocnik Bobov verejny kluc, cize pozna hodnotu cisla n a sifrovaci exponent e. Jedina vec, ktora mu chyba, je desifrovaci exponent d. Utocnik samozrejme vie, ako RSA funguje a preto vie, ze medzi e,d plati vztah: e * d = 1 (mod Phi(n))
Takze utocnik si jednoducho vypocita najprv Totient funkciu cisla n Phi(n). A potom jednoducho (napr. pomocou rozsireneho euklidovho algoritmu) najde multiplikativny inverz cisla e. A dostane hladany desifrovaci exponent d.

A kde je hacik?
Cela bezpecnost algoritmu RSA je zalozena na predpoklade, ze utocnik nedokaze zistit hodnotu Phi(n), a to napriek tomu, ze pozna n. To, aby to utocnik nedokazal zistit, sa dosahuje tak, ze za n sa vezme velmi velke cislo. To znamena, ze utocnik by musel skontrolovat vsetky cisla od 0 po n - 1, zistit, ktore z nich maju s cislom n najvacieho spolocneho delitela 1 a spocitat ich pocet. Tak by dostal Phi(n) a uz by mu nic nebranilo v uspesnom desifrovani:-)

Aj vy ste si vsimli, ze tu nieco nesedi?
Z toho co som napisal v predchadzajucom odstavci sa moze zdat, ze s bezpecnostou RSA je vsetko v najlepsiom poriadku. Ale stale to ma maly nedostatok. Nikde som nenapisal, ako Bob dokaze vygenerovat dvojicu (sukromny kluc, verejny kluc).
Ked si totiz Bob zvoli dostatocne velke cislo n, ma skoro taky isty problem, ako nas utocnik. Totiz musi najst dvojicu cisel (e,d) tak, aby platilo e * d = 1 (mod Phi(n)). Cize musi najprv zistit hodnotu Phi(n). A ak to dokaze Bob, preco to nedokaze nas utocnik? Tu si pomozeme na zaciatku clanku uvedenou vlastnostou Totient funkcie, a to Phi(a * b) = Phi(a) * Phi(b) (Cisla a,b musia byt nesudelitelne). Takze Bob si nevyberie za cislo n len tak hociktore velke cislo, ale najprv si vyberie 2 prvocisla p,q. Kedze p,q su prvocisla, dokaze hned urcit, ze Phi(p) = p - 1, Phi(q) = q - 1. (Tato vlastnost je tiez uvedena na zaciatku clanku) A ako cislo n si Bob zvoli sucin prvocisel p * q. A samozrejme dostane, ze Phi(n) = Phi(p * q) = Phi(p) * Phi(q) = (p - 1)*(q - 1). Takze teraz Bob pozna Phi(n). Zvoli si cislo e, take aby najvaci spolocny delitel cisel e, Phi(n) bol 1. (To mu zaruci ze bude k nemu existovat multiplikativny inverz). Dalej si Bob pomocou rozsireneho euklidovho algoritmu spocita multiplikativny inverz k cislu e, ako vysledok dostane d. A teraz uz Bob ma verejny kluc (e, n) a sukromny kluc (d, n) a Bob moze veselo sifrovat :-)

Zhrnutie na zaver:
Generovanie paru klucov:
1. Bob si vytvori 2 velke prvocisla p,q.
2. Bob si spocita n = p * q.
3. Bob si spocita Phi(n) = (p - 1)*(q - 1)
4. Bob si vyberie 1 < e < Phi(n) tak aby cislo e nemalo s Phi(n) ziadneho spolocneho delitela
5. Bob si spocita d pomocou rozsireneho euklidovho algoritmu ako multiplikativny inverz k e. (e * d = 1 (mod Phi(n))
6. Bob ma verejny kluc (e,n) a sukromny kluc (d, n)

Sifrovanie:
C(m) = m^e (mod n)

Desifrovanie D(c) = c^d (mod n)

Takze preco je tazke rozlusknut RSA?
Utocnik stoji pred problemom z cisla n spocitat Phi(n). Ale pretoze utocnik pozna fungovanie algoritmu RSA, vie ze cislo n bolo vytvorene ako sucin 2 velkych prvocisel. Ak sa mu tie prvocisla podari najst, moze si spocitat Phi(n) a pomocou neho desifrovaci exponent d (Spocita si to rovnakym sposobom akym Bob generoval svoj par klucov)

A ako to suvisi s digitalnym podpisom?
Povedzme, ze Bob chce poslat Alici spravu m, ale chce aby mala Alica istotu, ze sprava pochadza od neho. Bob si vygeneruje verejny kluc (n, e) a sukromny kluc (n, d). (Kde e je "sifrovaci" exponent a d "desifrovaci"). Bob vytvori podpisanu spravu S = m^d (mod n) a tuto spravu posle Alici. Pretoze uz vieme, ze plati m^(e*d) = m (mod n), staci, ak si Alica zisti Bobov verejny kluc (e, n) a spocita povodnu spravu m = S^e (mod n).
Alica teda vie, ze povodna sprava bola umocnena sukromnym klucom, ktory odpoveda Bobovmu verejnemu klucu a teda sa moze domnievat, ze spravu napisal skutocne Bob a tato sprava nebola po ceste zmenena.

    • Re: Preco je tazke prelomit sifru RSA ? 07.03.2008 | 20:04
      Avatar blackhole   Návštevník

      Pekny clanok, vyborne vysvetlene pre kazdeho. Budem rad, ak sa podobne kvalitne clanky budu objavovat na BH castejsie.

      ____________________________________________________________
      Ked niecim nie som takmer uplne presvedceny, nepisem to. Vzdy uvadzajte vecne a najdolezitejsie argumenty, inak ma nepresvedcite. Ked sa mylim, opravte ma; rad sa poucim.

    • Re: Preco je tazke prelomit sifru RSA ? 07.03.2008 | 21:57
      Avatar blackhole_karci   Používateľ

      Super clanok, vzdy rad privitam nejake dalsie info o cryptovani :)
      +1

      EDIT: Uplna blbost, ale ked pises ze si ludia vystacia s ucivom zakladnej skoly, tak ucia sa na zakladke mnoziny? ;)
      ______________
      if it moves, compile it! [:. Gentoo rulz .:]

      ______________ if it moves, compile it! [:. Gentoo rulz .:]
      • Re: Preco je tazke prelomit sifru RSA ? 07.03.2008 | 23:11
        Avatar blackhole   Návštevník

        Yoo suhlasim... uplne easy math to opat nie je :), ale skladam poctu, skutocne kvalitny clanok ;)

    • Re: Preco je tazke prelomit sifru RSA ? 07.03.2008 | 23:23
      Avatar blackhole_matej   Používateľ

      Imho velmi chaoticky napisane, bez upravy. Kebyze neviem, ako to funguje, z tohoto to urcite nepochopim.

      Co sa tyka matematiky, tak k pochopeniu clanku si vystacite s ucivom zakladnej skoly:-)
      Eulerova funkcia a pocitanie v konecnych poliach? To asi nie...

      • Re: Preco je tazke prelomit sifru RSA ? 08.03.2008 | 11:02
        Avatar blackhole   Návštevník

        Ja si myslim, ze to je napisane dost dobre.
        Pre mna najlepsi clanok minimalne za posledny mesiac, diki.
        ==
        Správnemu programátorovi stačí pivo a google.

      • Re: Preco je tazke prelomit sifru RSA ? 15.05.2009 | 13:47
        Avatar ehmo   Používateľ

        matej, ale no tak. ked uz chces rypat, tak zacni najskor u seba.

        blackhole je uzavreta komunita prevazne ludi, ktori uz vedia urobit 1+1 dokonca aj 4*4 a mozno aj o nieco viac. nejde o sme.sk, azet, alebo iny bordel site, kde chodi kazdy debil a tak by si sam mohol predpokladat, ze citatelia tohoto portalu budu mat aku-taku predstavu o tom, co sa v clanku bude pisat. preto aj zvelicenie autora o matematike zakladnej skoly moze byt povazovane za urcitu humornu vlozku.

        samotny clanok je napisany v skutku vyborne. napriek tomu, ze som sa o rsa dlhsie sam zaujimal, nikdy som sa na to nepozeral tak, ako autor, resp. nikdy som to tak jednoducho nedostal a urcite by som to tak nevedel ani spatne podat. autor (som lenivy zistovat kto to pisal) ma viditelne nadanie na podavanie podobnej problematiky ludskym jazykom a ja by som bol velmi rad, keby nam tu predostrel aj ine matematicke zahady dnesnej cryptologie, aj napriklad jednoduche hashovacie funkcie (ako md5, sha1, atd.) [ja som napriklad donedavna veril, ze md5 nad 32 znakov uz nie je "decryptnutelna" pretoze neobsahuje zdroj informacie, ale vraj to tak nie je]

        keby sa clanok upravil do mozno trosku jasnejsej formy, viac by sa vytvorili odseky a kde tu vymenili slovicka, mohol by to byt extremne vhodny clanok pre wikipediu, kde by mohol pomoct pochopit RSA mnohym slovakom i cechom.

        suhlasim s pXom, jeden z najlepsich clankov poslednej doby.
        ------------------------------
        http://blog.synopsi.com

        ------------------------------ http://blog.synopsi.com
        • Re: Preco je tazke prelomit sifru RSA ? 15.05.2009 | 18:59
          Avatar burbaky   Používateľ

          Máš nízke nároky. Ten článok bol celý zle.

          MB

    • Re: Preco je tazke prelomit sifru RSA ? 08.03.2008 | 01:55
      Avatar ehmo   Používateľ

      velmi pekny clanocek, mozno trosicka chaoticky rozdeleny, ale pre pochopenie to podla mna celkom staci. mas urcite u mna +

      pre tych, co maju radi vizualne ukazky tu mam jedno peknucke video
      ------------------------------
      http://blog.synopsi.com

      ------------------------------ http://blog.synopsi.com
    • Re: Preco je tazke prelomit sifru RSA ? 08.03.2008 | 18:10
      Avatar blackhole   Návštevník

      Clonok sice pekny, ale mozno by sa hodilo niekedy napisat, ze preco to funguje:-) A volil by som menej bulvarny nadpis (kedze v clanku sa odpoved nenachadza).

      • Re: Preco je tazke prelomit sifru RSA ? 08.03.2008 | 18:30
        Avatar blackhole   Návštevník

        Precitaj si clanok este raz a postupne, nepreskakuj riadky. Potom tam najdes aj odpoved na nadpis, aj preco to funguje.
        ____________________________________________________________
        Ked niecim nie som takmer uplne presvedceny, nepisem to. Vzdy uvadzajte vecne a najdolezitejsie argumenty, inak ma nepresvedcite. Ked sa mylim, opravte ma; rad sa poucim.

        • Re: Preco je tazke prelomit sifru RSA ? 08.03.2008 | 19:38
          Avatar blackhole   Návštevník

          Neviem, ale od clanku s napisom preco je tazke prelomit sifru RSA by som ocakaval lepsiu odpoved, ako to, ze Eulerovu funkciu nevieme efektivne vypocitat, alebo to, ze nevieme efektivne faktorizovat . Ocakaval by som odpoved, preco je ju tazke vypocitat a preco je tazke faktorizovat. Proste od clanku "preco je tazke prelomit sifru RSA" som cakal ine. Lepsi nadpis by bol napriklad: "Ako funguje RSA?"

          Dalej, preco to funguje tam napisane nie je. Vzorcek tam nie je dokazany a ani tam nie je naznaceny dokaz a ani pokus o vysvetlenie, preco to tak je. Je tam len napisane, ze nejake vztahy platia.

          Tymto nechcem kritizovat clanok, vobec nie je zly, ale iba povedat co mi tam chybalo.

          • Re: Preco je tazke prelomit sifru RSA ? 08.03.2008 | 22:04
            Avatar vektor   Používateľ

            Ten vzorcek sa dokazuje malou Fermatovou vetou, a na dokaz tej potrebujes vediet napriklad to, co je to grupa invertibilnych prvkov monoidu Z_n. Si si isty, ze ten dokaz patri na tento portal?...

            _________________________ There is some SERIOUS sh*t going on right now!
            • Re: Preco je tazke prelomit sifru RSA ? 08.03.2008 | 22:28
              Avatar blackhole   Návštevník

              Ten dokaz nie je taky dlhy a tazky, aby sem nemusel ist. Nemusis vediet co je to grupa invertibilnych prvkov monoidu Z_n( pozri napriklad http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem ).

              A podla mna dokaz urcite patri na tento portal, teda ak chces tomu rozumiet, tak sa aj oplati vediet preco. Ako, netvrdim ze v tomto clanku musel byt cely dokaz, ale aspon nejake zdovodnenie. Nemam rad, ked niekto poskytne napriklad vzorec, a nepovie k nemu nic viac. Ak je dokaz nahodou strasna tyc, tak aspon ze je to tyc a linka na clanok, kde ten dokaz je ak je to mozne.

              Ale uz sa pokusim vyhnut debate k tomuto clanku, nemam v umysle na neho kydat ako to teraz urcite vyzera, je celkom pekny:-)

      • Re: Preco je tazke prelomit sifru RSA ? 07.04.2008 | 13:28
        Avatar blackhole   Návštevník

        myslim ze autor chcel len nadhot a priblizne ukazat ako to funguje.

        Na detailny popis by to chcelo serial aspon 15tich clankov z ktorych asi 10 by boli zaklad Diskretnej matematiky pripadne aj matematickej logiky aby vobec sme mohli hovorit o tom preco toto sifrovanie a algorytmus funguje a kde su jeho slabe stranky a preco.

        Takze nemozes velmi chciet presnu odpoved so vsetkym ako to funguje v jednom clanku.

    • Re: Preco je tazke prelomit sifru RSA ? 28.03.2008 | 12:21
      Avatar burbaky   Používateľ

      Článok nevysvetľuje, prečo a či vôbec je ťažké prelomiť RSA. Aj by som sa divil. Pretože to vraj nevie na tejto planéte nikto. Aspoň sa tým teda dodnes nikto nepochválil. Možno to jedného dňa príde, ale moja radosť bola tentokrát priskorá.

      Najprv k diskusiám, či vôbec fungovanie RSA ide vysvetliť pomocou matematiky základnej/strednej školy. Samozrejme to ide. "Vypadne to" z Malej Fermatovej vety a Čínskej vety o zvyškoch. Tie sa dajú poohýbať tak, že to pochopí aj (vhodne!) náhodne zvolený gymnazista. Dá sa to celé hravo udržať v elementárnej teórii čísel a netreba šermovať pojmami ako "monoid", "grupa" alebo "konečné pole" (Toto bolo obzvlášť vtipné. Tesne vedľa!) "Zdola" sa k fungovaniu RSA cestička vyšliapať dá aj stredoškoláckymi topánočkami. Ale takýto dobrodruh neuvidí to, čo vidí, kto sa díva "zhora" a "RSA" dostane zdarma ako triviálny dôsledok krásnej, v princípe jednoduchej no masám na míle vzdialenej matematickej teórie.

      K "lámaniu" RSA. Prečo si autor myslí, že na "zlomenie" RSA potrebujem vypočítať d? Mňa nezaujíma nejaké d ale m. Preto RSA zlomím, ak viem počítať e-te odmocniny modulo n. Nepotrebujem d ani phi(n). Na "zlomenie" RSA možno stačí "menej" námahy. Ja neviem. Možno. Takmer nikto nevie. Trošičku zavádza tvrdenie, že je to ekvivalentné rozkladu na prvočísla. Znalosť phi(n) síce so znalosťou p a q ekvivalentná je ale až takto veľa nám možno netreba.

      Napokon, nikto netuší, aký je rozklad čísel na prvočísla vlastne ťažký. Existuje iba "taký pocit", že ľahké to asi nebude. Všelijakí bystrí ľudia si desiatky rokov lámu nad tým hlavy a "takmer nikde" sa nedostali. Súčasný stav poznatkov preto ako-tak môže podložiť našu vieru v bezpečnosť RSA. Ale je to iba viera. V prípade niektorých kvalifikovanejšia viera, ale stále viera...

    • Re: Preco je tazke prelomit sifru RSA ? 09.03.2008 | 00:13
      Avatar burbaky   Používateľ

      Ale prečo nie, môže byť. Princíp šifry ako takej v princípe (s ohľadom na publikum) vysvetlený. Akurát analýza bezpečnosti kríva. Ale tá bude asi krívať vždy a každému.

      Ešte priateľské varovanie ostatným čitateľom. Nesnažte sa to, čo ste (v tomto či inom) článku čítali, nikde v reálnom svete "takto" implementovať. Bude to takmer určite zle. Toto vyzerá na príjemný a nežný úvod do principiálnych myšlienok "tamtých vecí". V naozajstnom svete je (najmä no nielen) implementácia oveľa oveľa zložitejšia.

    • Re: Preco je tazke prelomit sifru RSA ? 09.03.2008 | 13:58
      Avatar blackhole   Návštevník

      Pekny clanok, akurat sa najblizsie skus viac pohrat s rozdelenim textu, aby to bolo prehladnejsie.

    • Re: Preco je tazke prelomit sifru RSA ? 09.03.2008 | 15:37
      Avatar blackhole   Návštevník

      Pekny clanok. Ja som sa podrobnejsie o RSA dozvedel az teraz a celkom tomu rozumiem, takze fajn.

    • Re: Preco je tazke prelomit sifru RSA ? 15.05.2009 | 00:26
      Avatar blackhole   Návštevník

      njn, velmi dobry clanok, len tak dalej ;)
      ----------------------------------------------------
      I want more life !

    • Re: Preco je tazke prelomit sifru RSA ? 11.06.2009 | 08:39
      Avatar blackhole   Návštevník

      Dobrý článok, teraz už aspoň trošku chápem princípu RSA..:-)

    • Re: Preco je tazke prelomit sifru RSA ? 12.07.2009 | 21:23
      Avatar blackhole   Návštevník

      Super clanok! Diki.
      Vzdy som tuzil vediet ako funguje RSA ale myslel som ze je to moc tazke - ale zvladol som v pohode.
      Z nudy som si spravil aj algoritmus na sifrovanie / desifrovanie aj rozsireny euklidov algoritmus - viem nie je to ono tak ma "nezabijajte" pracuje to iba s malymi cislami - bezproblemove rozsifrovanie :)
      Pre tych ktori sa nudia ako som sa nudil ja prikladam spravu zasifrovanu klucom 97 5311 (zasifrovany kazdy znak samotatne, des. sustava; pouzite pretypovanie na char) - mozete skusit prelomit :D
      636 2261 572 881 1667 1789 1667 4197 1955 3192 2958 2958 2958 1629 4072 4689 5197 1955 4689 1040 1955 286 4689 3037 286 2261 2995 190 4689 3037 3440 2261 2995 3409 572 1789 286 881 1667 881 2995 286 4689 3037 3440 2261 1667 286 572 286 190 572 4689 1789 1667 190 3037 4689 286 4689 3037 286 2995 3452 3192 1955 1040 1667 3900 1629 417 572 286 4197 1955 4197 286 101 3409 5212 190 3452 3409 3037 2522 1040 1667 881 3037 1955 101 286 1040 572 5197 3037 4689 286 1955 1237 3192 572 3037 1789 286 1040 572 286 572 3452 2261 1955 4689 1667 286 2269 572 2261 881 3037 1040 3900 1443 102 493 4264 572 881 1789 572 4689 3900 4689 2531 286 572 286 572 2531 2995 286 5197 2261 1955 3452 3192 1955 881 286 1667 3409 1955 3452 286 1443 629 5150 286 4689 2995 1789 3409 1955 3452 3900 1629 1023 2995 286 4689 5197 2261 572 3409 5212 286 1040 572 5197 3037 4689 286 4689 1667 2531 2261 2995 3192 1040 5212 286 2531 1789 1667 1574 286 4108 4689 881 572 1574 3037 286 3452 1295 286 572 1789 1955 2810 2995 286 881 1955 1040 881 2995 286 881 1955 4617 881 3900 1629 629 286 5197 2995 190 3452 2261 572 3409 2995 3192 1629 3354 3354 4242 5150 4510 803 286 1063 1295 1629
      Ano viem ze to bude lahke cisla su moc male, ale na zabavu staci... tak prijemne lamanie! :D
      --------------------------------------
      Rozdiel medzi vírusmi a windowsami je v tom že vírusy sú malé, úsporné a na rozdiel od windowsov aj niečo robia...

      • Re: Preco je tazke prelomit sifru RSA ? 12.07.2009 | 21:39
        Avatar vektor   Používateľ

        Kedze si zasifroval kazdy znak samostatne, nie je to ziadna RSA, ale obycajna substitucia, ktora sa da trivialne prelomit frekvencnou analyzou, najma pri dlhsom texte. Teda nie ze by sa mi to teraz chcelo, ale da sa to:)

        http://en.wikipedia.org/wiki/Substitution_cipher

        _________________________
        There is some SERIOUS sh*t going on right now!

        _________________________ There is some SERIOUS sh*t going on right now!
        • Re: Preco je tazke prelomit sifru RSA ? 13.07.2009 | 00:06
          Avatar burbaky   Používateľ

          Prečo by to nebolo RSA? Nerozumiem. Nie je náhodou každá (deterministická) šifra substitúciou, hoci s "trošku väčšou" abecedou?

          Kľúč je 2337. Zvyšok strata času. Ako bol i pôvodný článok...

          • Re: Preco je tazke prelomit sifru RSA ? 13.07.2009 | 00:21
            Avatar blackhole   Návštevník

            Blbe je, ze tu ta abeceda "trosku vacsia" nieje...
            ==
            Things are rarely just crazy enough to work, but they're frequently just crazy enough to fail hilariously.

            • Re: Preco je tazke prelomit sifru RSA ? 13.07.2009 | 08:34
              Avatar blackhole   Návštevník

              Ouha! To som si neuvedomil - klasicku substtituciu poznam velmi dobre :D no nevadi aspon haluz a to s tym e-1 musim kuknut :) ale aspon sme sa zabavili...
              --------------------------------------
              Rozdiel medzi vírusmi a windowsami je v tom že vírusy sú malé, úsporné a na rozdiel od windowsov aj niečo robia...

      • Re: Preco je tazke prelomit sifru RSA ? 13.07.2009 | 01:02
        Avatar blackhole   Návštevník

        Presne ako vravi vektor je to substitucia. Este horsie ale je, ze viem public kluc, mne teraz staci si zasifrovat vsetky znaky abecedy (to ma nezabije ani v najmensom - nejakych 64 znakov) a ziskam presne substitucnu tabulku.
        Takze sa netreba spoliehat na frekvencnu analyzu.

        Viem, ze si spravu chcel napisat len ako zaujimavost, ale pritom si niekto mohol mysliet, ze to je uplne vporiadku a ze asymetricke sifrovanie skutocne prebieha takto. A clovek by si myslel, ze kedze je to asymetricke, je to superbezpecne...

        Jo, a mas chyvu v implementacii toho tvojho sifrovania, v skutocnosti to umocnujes e-1 krat.
        A mail ti pisat nejdem.
        ==
        Things are rarely just crazy enough to work, but they're frequently just crazy enough to fail hilariously.