.: Rychlé menu: navigace .:. odkazy .:. kategorie .:. vyhledávání .:. archivy .:. autoři :.  

22.10.2004



Začínám trochou teorie, tak to bude o něco delší. Ale netřeba se bát, nebude to nijak náročné! Povíme si o tom, jak funguje takové šifrování...

Motto: Já vedu rozhovory, a ať si je každý odposlouchává, jak chce. Když si je člověk jistý, že nic nespáchal, může mu to být jedno...  — Jiří Kolář, prezident Policie ČR


Slíbil jsem seriál o šifrování spolu s praktickým návodem a ukázkami. Ale než se dostanu k těm ukázkám a k praxi, napíšu něco obecného o kryptografii. Vezmu to ale zkrátka — nechci suplovat odborná či populární pojednání (tedy o Enigmě se tu nic nového nedozvíte).

V současnosti je kryptografie obor úzce spojený s matematikou a používající podivné věty o běžných věcech, jako je třeba dělení, umocňování nebo prvočíslo. Těchto základů si nebudu všímat, natož abych je popisoval nebo nedejbůh vysvětloval. Pominu i historii šifrování a jen letmo se zmíním o pramáti šifer, o takzvané Caesarově šifře.

Caesarova šifra byla (z dnešního pohledu) velmi jednoduchá, ovšem nejspíš účinná — vzhledem k tomu, kdo byl Caesarův nepřítel. Její princip byl následující: Caesar napsal text, který chtěl zašifrovat, například: "Zabil jsem MCMLVII Galů, MDXLI Germánů a jednoho advokáta. Brutovi vyřiďte, že ho zapíchnu, až se vrátím!" a pak šel písmenko po písmenku a každé nahradil tím, které bylo o tři místa v abecedě dál. Takže místo A napsal D, místo B napsal E atd. až k Z, místo kterého napsal C... Zašifrovaná zpráva pak začínala slovy „Cdelo mvhp...” Takhle zašifrovanou zprávu odeslal Caesar do Říma, tam si ji přečetli senátoři a hned jim bylo všechno jasné: Caesar zase nasával! Ne, vážně — tam seděl někdo, kdo znal princip té šifry, a zprávu rozluštil.

Z tohoto stručného popisu je vidět, že pro šifrování jsou potřeba tři věci: Zpráva, kterou chci šifrovat, šifrovací klíč a dešifrovací klíč. U Caesarovy šifry byl šifrovací klíč ten výše zmíněný postup (+3) a dešifrovací klíč byl postup opačný. Důležité je, že dešifrovací klíč bylo možné velmi jednoduše zjistit z klíče šifrovacího a obráceně. Což není dnes příliš bezpečné... Tenkrát to ovšem stačilo.

Ve 20. století zažily šifry nebývalý rozvoj — podepsaly se na tom především dvě světové války a poválečný rozmach výpočetní techniky. V současnosti je snad nejpoužívanejším způsobem šifrování zpráv tzv. šifra s veřejným klíčem. Umožňuje hlavně dvě věci: Podepsat (autorizovat) zprávu a také to, že kdokoli může poslat určenému příjemci zašifrovanou zprávu, nečitelnou pro nikoho jiného.

Jak ta šifra funguje? Představte si trezor s dvěma zámky. Do každého zámku pasuje jiný klíč — jsou tedy dva klíče, nazvěme si je S a V. Trezor funguje tak, že jej zamknete jakým klíčem chcete, ovšem odemknout ho pak můžete jen tím druhým. Zamknete-li tedy trezor klíčem S, už ho tím samým klíčem neodemknete a musíte použít klíč V. A obráceně. Klíče S a V nejsou navíc zaměnitelné ani nejsou „zjistitelné”, to znamená že máte-li např. v ruce klíč V, nedokážete podle něj vytvořit protipól, tedy klíč S.

A teď to podstatné: Vy máte klíč S, u sebe, schovaný, tajný. Klíč V je veřejně přístupný, stejně tak jako trezor. Když vám někdo chce poslat zprávu, udělá to tak, že ji vloží do trezoru a trezor zamkne klíčem V. Jediný, kdo se teď ke zprávě dostane, je majitel klíče S — tedy vy. Kdokoli vám tedy může poslat veřejně (třeba mailem) zašifrovanou zprávu a k obsahu se dostanete jedině vy, nikdo jiný.

Stejný postup lze použít i pro ověření autora, laicky řečeno k „podepsání” zprávy. Vy napíšete zprávu, vložíte ji do trezoru a zamknete svým soukromým klíčem S. Teď se k té zprávě dostane čtenář pouze tehdy, když trezor odemkne klíčem V — a tím je zaručeno, že trezor byl zamčen vaším klíčem, jinými slovy že vy jste odesilatel.

Ve světě počítačů je tenhle princip použit v programu PGP a jeho klonech. (Na podobném principu pracuje i onen známý digitální podpis, [ironie] který tak rádi uznávají čeští úředníci [konec ironie].) V roli trezoru je tento program, klíče jsou malé soubory. Při prvním spuštění vám program vygeneruje dvojici klíčů, veřejný a soukromý. Veřejný vystavíte někde na Internetu, přidáte ho do patičky mailu, zkrátka ho nějak publikujete. Soukromý je jen pro vás a ten si musíte hlídat jako oko v hlavě! (Kvůli bezpečnosti je navíc chráněn heslem.)

Jak si takový program nainstalujete? Jak si vygenerujete šifrovací klíč? Jak s jeho pomocí zašifrujete zprávu? To napíšu příště — bude-li zájem... (Ale můžete se z pilnosti poohlédnout po internetu, návodů je dost. Hledejte klíčové slovo PGP, popř. GPG.)

Ještě dodám, že takovéhle praktiky občanů se státu samosebou nelíbí a státy hledají způsoby, jak číst svým poddaným i zašifrované zprávy. Špatné na tom je to, že každá šifra je prolomitelná. Dobré ale je to, že na prolomení jedné zprávy je potřeba tak velký výpočetní výkon a tolik času, že se to zkrátka nevyplatí.

A pokud byste chtěli vidět, jak vypadá takový veřejný klíč, podívejte se na můj veřejný PGP klíč.


Zadal Arthur Dent, 22.10.2004 10:05:53, 19 komentářů...,
TrackBack URL tohoto příspěvku je http://blog.maly.cz/tb.php/1154

Zpět na článek

HotLinks
Reakce na jiných stránkách (TrackBack)
WELL.DONE (c) Radek Hulán: Šifrování pro lamy - instalace GnuPG (GPG) na Windows
WELL.DONE (c) Radek Hulán: Šifrování pro lamy - Thunderbird s Enigmail a GnuPG
WELL.DONE (c) Radek Hulán: Šifrování pro lamy - instalace nejnovějšího GnuPG 1.4.0a
Zobrazit komentáře v chronologickém pořadí

Hezké... - Ladislav Thon (web)
(22.10.2004 10:30:21)

Hezké, nasávající Caesar je super {smile} Ale chybí mi zmínka o certifikačních autoritách. On takový pár klíčů si může vygenerovat kdekdo, ale jak zjistím, že patří skutečně tomu, o kom se tvrdí, že mu patří?
    

Re: Hezké... - Arthur Dent (web)
(22.10.2004 11:53:17)

Ano, k tomu se dostanu. Hnedle jak popíšu instalaci a použití, tak přijde řada na podepisování klíčů, certifikační autority a krátkou exkurzi do pružného přístupu Českého Úředníka(tm).
    


 - mao_boy (web)
(22.10.2004 13:00:54)

...<i>podivne věty o běžných věcech.</i>

- to je pěkně řečeno{big grin}))

Škoda jen, že ses o tom víc nerozepsal. Vůbec by to nemuselo být nudné a suchopárné. Naopak pojednání o malé Fermatově větě, faktorizaci velkých čísel, Mersennova prvočísla, testech prvočíselnosti (ARCLP apd.)...no nic, ale i tak je to fajn.

a propos: [www.mersenne.org/prime.htm] :

<i>On May 15, 2004, Josh Findley discovered the 41st known Mersenne Prime, 2^24036583-1. The number is nearly a million digits larger than our last find and is now the largest known prime number!</i>

ps: a znáte tenhle?

<b>How they prove that all odd integers higher than 2 are prime?<b>

Mathematician: 3 is a prime, 5 is a prime, 7 is a prime, and by induction - every odd integer higher than 2 is a prime.

Physicist: 3 is a prime, 5 is a prime, 7 is a prime, 9 is an experimental error, 11 is a prime,...

Engineer: 3 is a prime, 5 is a prime, 7 is a prime, 9 is a prime, 11 is a prime,...

Programmer: 3 is a prime, 5 is a prime, 7 is a prime, 7 is a prime, 7 is a prime,...

Salesperson: 3 is a prime, 5 is a prime, 7 is a prime, 9 -- we'll do for you the best we can,...

Computer Software Salesperson: 3 is prime, 5 is prime, 7 is prime, 9 will be prime in the next release,...

Biologist: 3 is a prime, 5 is a prime, 7 is a prime, 9 -- results have not arrived yet,...

Advertiser: 3 is a prime, 5 is a prime, 7 is a prime, 11 is a prime,...

Lawyer: 3 is a prime, 5 is a prime, 7 is a prime, 9 -- there is not enough evidence to prove that it is not a prime,...

Accountant: 3 is prime, 5 is prime, 7 is prime, 9 is prime, deducing 10% tax and 5% other obligations.

Statistician: Let's try several randomly chosen numbers: 17 is a prime, 23 is a prime, 11 is a prime...

Professor: 3 is prime, 5 is prime, 7 is prime, and the rest are left as an exercise for the student.

Computational linguist: 3 is an odd prime, 5 is an odd prime, 7 is an odd prime, 9 is a very odd prime,...

Psychologist: 3 is a prime, 5 is a prime, 7 is a prime, 9 is a prime but tries to suppress it,...
    

Re: - Arthur Dent (web)
(22.10.2004 13:39:39)

No, je s tím drobný problém.

Napíšu třeba, že "rozložit součin dvou malých prvočísel na tato prvočísla není příliš těžké, ale pro čísla mající třeba 500 míst je to těžko řešitelný úkol..." Ale taky abych napsal proč je to těžko řešitelný úkol, jaká jsou řešení atd. A měl bych popsat některé metody, např. Pollardovu ró-metodu... A obávám se, že tohle už bych nebyl schopen podat tak, aby to zajímalo víc lidí. Neříkám že to není zajímavé, ale - nedokázal bych to podat.

Pokud se toho chceš ujmout (nebo někdo jiný... nějaký matematik... Vlku, dívám se tvým směrem!{smile} ), budu rád a s chutí a s díky to tu zveřejním.

Spíš to ale nechám na poslední díl, jako "zajímavosti", a budu odkazovat na prameny...
    

Re: - ofr (web)
(22.10.2004 14:46:36)

začíná to dobře - keep crypting...
    


Re: popis - Vlk (web)
(23.10.2004 20:49:25)

Šiframa jsem se nikdy super moc nezajímal, takže snad něco v komentářích, ale jinak je můj styl "přehledný, jasný, ale strašně suchý" jak prohlásila naše paní profesorka ČJ na gymplu ...
    

Re: popis - Arthur Dent (web)
(23.10.2004 21:49:31)

Nemyslel jsem přímo šifry... Byl bys schopen vysvětlit, proč je rozklad velkých čísel na prvočísla o tolik těžší než rozklad menších? Jsi schopen vysvětlit, jak se kontroluje prvočíselnost? Dokázal bys vysvětlit, jak je to s těmi prvočísly "(2^p) - 1"?

A byl bys schopen vysvětlit mně, čistě soukromě, jaký je rozdíl mezi počítačovým operátorem "mod" (zbytek po dělení) a matematickým "modulo"? Jak jsem tak na to koukal, tak jsem zjistil, že "je to to samé, ale je to jiné", jak prohlásila naše paní profesorka matematiky. {smile}
    

Re: popis - Marian Kechlibar (web)
(24.10.2004 00:13:12)

Tak ses trefil do otazek, ktere delam uz dost dlouho {smile}
Rozdil mezi matematickym mod a pocitacovym mod v podstate ani neni. Oboje znamena ¨zbytek po deleni¨. S tim, ze matematici jsou zvykli povazovat za platne hodnoty mod r cisla 0 az r-1, zatimco pocitac ti obecne vyplivne hodnoty od -(r-1)/2 do (r-1)/2. To znaji matematici taky, ale rikaji tomu ¨least absolute value mod r¨.
Cisla 2^p-1 nejsou obecne prvocisla. Napriklad 2^11-1 = 2047 = 23*89. Jsou to vsak jedine vyrazy typu 2^n-1, ktere maji sanci prvocislem byt. Dukaz je trivialni, napis si n=mk a pouzij binomickou vetu na vyraz (2^m)^k-1 = (2^m)-1^k.
    

Re: popis - Arthur Dent (web)
(24.10.2004 10:35:16)

Fajn... A teď to vysvětli ostatním čtenářům {smile}

Není ta definice počítačového a matematického MOD přesně obráceně? V jazycích co znám je MOD definován jako zbytek po celočíselném dělení a počítá se takto:

a MOD b = (a - (INT (a/b) * b))

Jeho výsledek je tedy v intervalu <0;b-1>
    

Re: popis - Marian Kechlibar (web)
(24.10.2004 14:35:20)

Zdar,

no, hele, programuju faktorizaci kvadratickym sitem, a mel jsem prave opacne problemy: operator % mi vracel zaporne hodnoty "least absolute value", ac jsem chtel hodnoty 0..p-1. Naopak matematicka definice a = bq+r stanovi, ze 0<= r < q {smile}
    

Re: popis - Arthur Dent (web)
(24.10.2004 16:08:54)

Jazyk / překladač / vstupní hodnoty ?
    

Re: popis - Marian Kechlibar (web)
(25.10.2004 22:17:26)

C++ / GCC 3.3.1 / vstupní hodnoty typu signed int
    


Re: popis - ptr (web)
(25.10.2004 10:26:24)

čauky,
nevím, jestli jsem dobře pochopil Tvé tvrzení. Jestli ano, paxním nesouhlasím. Samozřejmě existují i jiná prvočísla než Mersen(n)ova (2 exp n - 1), ale u těchto čísel umíme lépe, rychleji a radostněji určit, zda dané číslo je nebo není prvočíslem. To je obecně dost velký problém, pokud to chceme dělat nějakým postupem (algoritmem) - třeba GNFS. Teď je ale velice IN mluvit o "zkratkách" v řešení tohohle problému (Shore-ův algoritmus a kvantová počitadla, Manindra apod.). No, to už jsem se dostal dál, než jsem chtěl: původní moje tvrzení je jednoduché: NENÍ PRAVDA, ŽE KAŽDÉ PRVOČÍSLO MUSÍ BÝT VE TVARU (2 exp N - 1).
    


Dobre ale stare stranky - DFly
(22.10.2004 16:17:09)

doporucuji kouknout na [www.krypta.cz/]
skoda jen ze za posledni dva roky uz neni moc aktualizovano
    


Skvělý - HUB (web)
(23.10.2004 14:55:05)

Super, těším se na pokračování
    


Šifrování na internetu - Martin - Techblog (web)
(23.10.2004 18:29:52)

Pokračování článku by bylo jistě zajímavé - té matiky bych se vážně nebál, zvlášť proto, že už před dlouhou dobou vyšel dokonalý seriál článků Šifrování na internetu od skvělého autora Hynka Hanke. Zdá se mi, že pokrývá tutéž oblast, jaké se chceš věnovat Ty.

Odkaz vede na poslední článek, kde jsou odkazy na všechny předcházející. Rozhodně stojí za přečtení.
[www.novinky.cz/archiv/Index/Internet/7623.html]

Takže se přimlouvám za něco méně populárního a více matematického. {smile}
    
HotLinks
Zpět na článek