| Dobrý den. V současnosti je bezpčečnost na internetu na prvním místě. Pokud se posílají citlivé údaje z klienta na server (nebo opačně), je vhodné, aby tato komunikace byla šifrována.
V případě, že se např. přihlašuji do své e-mailové schrinky, je mé heslo (které píšu do formuláře) následně zašifrováno a převedeno na HASH, který doputuje po síti až ne server, kde je porovnán s hashem, který je na serveru uložený.
Nj. pokud je ale hashovací funkce normální matematická funkce a je známa (předpokládám, že zdrojové kody MD5 a pod. jsou dosutpné). jak je možné , že nelze (resp. je to obtížné) ze získaného (odchyceného) hashe zpětně heslo zjistit a to velmi rychle se 100 % jistotou úspěchu...?
Vím, že to nejde, ale není mi už tak jasné proč. Přeci pokud mám např. funkci y=2x + 5 a já vím, že y = 10 (y..reprezentuje hash), tak jsem snad vždy schopen vypočítat to "x" (tedy heslo).
Takže moje otázka je, jak vypadá taková hashovací funkce z pohledu matematika a proč není tak jednoduché k ní vypočítat "funkci inverzní", která by okamžitě převáděla hash na heslo?
Dik za odpoveďi....
(odpovědět) | | Anonymous | 195.39.54.125/unknown | 18.2.2010 13:44 |
|
|
|
|
| Znáte třeba problém batohu?
Matematicky se jedná o problém výběru z množiny celých čísel její podmnožiny tak, aby součet prvků této podmnožiny byl roven nějaké předem zvolené konstantě. (analogicky: naskládat do batohu různě těžká zavazadla tak, aby vážil přesně třeba 50kg)
Pokud vám někdo sestaví onu chtěnou podmnožinu, snadno a hlavně rychle ověříte, jestli splňuje zadané kritérium (sečtete prvky a porovnáte s konstantou).
Sestavení této podmnožiny je ovšem horší, zatím se neví o lepším způsobu (až na pár víceméně bezvýznamných detailů), než vyzkoušet všechny podmnožiny.
Hashovací funkce jsou postavené na podobném principu - snadno pro nějaký řetězec X a hashovací funkci h() zjistíte hodnotu h(X), kterou porovnáte s uloženým hashem (analogie v sečtení prvků a porovnání s konstantou). Opačný proces je ovšem výpočetně náročnější (ale ne nemožný).
"...a proč není tak jednoduché k ní vypočítat "funkci inverzní", která by okamžitě převáděla hash na heslo?" - to jsou docela hluboké problémy teorie složitosti :-)
(odpovědět) | | mr.Crow. | 213.211.34.* | 18.2.2010 16:33 |
|
|
|
| Možná, že přemýšlíte, jak se dostat k peněžnám transakcím prováděných na internetu :) K tomu můžu přiložit snad jen odkaz na Riemannovu hypotézu [link] :) Zatím se uvažuje o tom, že spadá mezi problémy NP úplných úloh (tzv. neřešitelné problémy tisíciletí), na jejichž řešitele čeká hodně tučná odměna :)
(odpovědět) | | Duck | 194.212.102.* | 18.2.2010 17:23 |
|
|
|
| NP úplné problémy jsou takové, které jsou na nedeterministickém turingáči řešitelné v polynomiálním čase ("jsou ověřitelné" v pol. čase), ovšem těžko říct, jestli i na deterministickém (tedy jestli jsou i řešitelné v pol. čase). Jestli ano nebo ne, je jeden z tzv. problémů milénia, mezi které patří i Riemannova hypotéza.
Kladná odpověď na jednu z hypotéz (Riemannovu nebo P=NP) by možná znamenala nějaký podstatně rychlejší algoritmus pro faktorizaci.
Tohle píšu, protože si nejsem jistý, jestli v tom máš pořádek :-)
(odpovědět) | | mr.Crow. | 213.211.34.* | 18.2.2010 18:17 |
|
|
|
| Špatně jsem se vyjádřil a plně souhlasím s tím, co jsi napsal :) Díky za upřesnění :)
(odpovědět) | | Duck | 194.212.102.* | 18.2.2010 22:25 |
|
|
|
| Mozna ze to co napisu je kravina, ale neni jednoduchy priklad funkce ke ktere se obtizne hleda inverzni pouhe posunuti v posuvnem registru?
y = (x << (x - (x % 2))) / x ** 10
Z hlavy me nenapada jak k tomu najit inverzi.
(odpovědět) | | Bystroushaak_ | 147.230.164.* | 18.2.2010 20:33 |
|
|
|
| mas pravdu, k funkcii prakticky sa rovnajucej y=f(x)=0 pre vsetky x>1 je skutocne nemozne najst povodny vstup :)
(odpovědět) | | stopa27 | 85.216.196.* | 18.2.2010 22:26 |
|
|
|
| Nj, chybka, zkousel jsem to na "A" - "z" - tzn 65 - 122.
(odpovědět) | | Bystroushaak_ | 147.230.164.* | 18.2.2010 23:13 |
|
|
|
| Anonymous - michas hrusky s jabkama a pokladas spatne formulovane otazky
V současnosti je bezpčečnost na internetu na prvním místě.
Neni ...
Pokud se posílají citlivé údaje z klienta na server (nebo opačně), je vhodné, aby tato komunikace byla šifrována.
Ano, prinejmensim ...
V případě, že se např. přihlašuji do své e-mailové schrinky, je mé heslo (které píšu do formuláře) následně zašifrováno a převedeno na HASH, který doputuje po síti až ne server, kde je porovnán s hashem, který je na serveru uložený.
TAK TAKHLE NE! V takovem pripade nema smysl nejaky hash vubec pouzivat. Autentizacni token nemuzes jen tak poslat. Musis pouze prokazat, ze ho znas. K tomu jsou ruzne protokoly (asymetr., zero knowlige, chalenge response, ...)
Nj. pokud je ale hashovací funkce normální matematická funkce a je známa (předpokládám, že zdrojové kody MD5 a pod. jsou dosutpné). jak je možné , že nelze (resp. je to obtížné) ze získaného (odchyceného) hashe zpětně heslo zjistit a to velmi rychle se 100 % jistotou úspěchu...?
Otazkou je, cemu rikas matematicka funkce. Rozhodne nemusi byt spojita a prosta. Jsou ruzne druhy hashovacich funkci s ruzny pouzitim. MD5, stejne jako MD2 nebo MD4 je popsana ve svem RFC.
Vím, že to nejde, ale není mi už tak jasné proč. Přeci pokud mám např. funkci y=2x + 5 a já vím, že y = 10 (y..reprezentuje hash), tak jsem snad vždy schopen vypočítat to "x" (tedy heslo).
Takže moje otázka je, jak vypadá taková hashovací funkce z pohledu matematika a proč není tak jednoduché k ní vypočítat "funkci inverzní", která by okamžitě převáděla hash na heslo?
Nebudu rozebirat vlastnosti ruznych typu hashovacich funkci, to by vydalo na jeden nebo i vice clanku. Jen lehce napadnu tvrzeni, ze k hashovaci funkci neni mozne spocitat funkci inverzni. Pro vybranou vstupni mnozinu to neni zas tak slozite - hledej pojem rainbow tables, resp. puvodni clanek od Martina Hellmana.
Ty tezke problemy lze vysvetlit i jinak, velice zjednodusene. Predstav si rubikovu kostku nebo treba puzzle. U takoveho hlavolamu je jednoduche rozhodnout, ze je spravne poskladany, ale samotne slozeni jednoduche rozhodne neni. Skladani muzes urychlit tim, ze ten samy hlavolam v te same konfiguraci budete resit dva a kazdy z vas si vybere jen polovinu moznych cest. Muzete to resit ctyri, kazdy se cvrtinou cest ...
Timto zpusobem vymenis potrebny cas pro reseni za vice prostoru potrebneho k reseni.
Kdyby te to vice zajimalo, tak shanej materialy na tema vypocetni slozitost, vycislitenost a NP-uplnost
(odpovědět) | | drd | 85.160.7.222/127.0.0.* | 19.2.2010 11:51 |
|
|
|
| Anonymous: predstav si treba logicke operatory, jako je OR (XOR, NOR, ...).
Vem z retezce, ktery chces zahashovat postupne bity po dvou a aplikuj na ne OR. Dostanes nejaky vysledek, ze ktereho uz ale nikdy nedostanes puvodni retezec. Pokud to takhle aplikujes vickrat, pravdepodobnost ziskani toho puvodni se dal snizuje.
Napriklad:
1101 0010
(1 || 1) = 1
(0 || 1) = 1
(0 || 0) = 0
(1 || 0) = 1
Vysledek mas 1101. Jak z nej ale zjistis, ten puvodni retezec? Nijak. Dokazes jen vypocitat mnozinu vsech puvodnich retezcu, ktera tento vysledek dava (10010010, 01100001, ...).
Tehle funkci muzes samozrejme pouzit vic a jinych, ruzne je kombinovat, v pripade ze nemas dostatek znaku tak je doplnovat, ruzne otacet atd.
----------
public static void main(String args[]){
throw new UnsupportedOperationException("Not implemented!");
}
(odpovědět) | |
|
|
| [link]
Vlastimil Klíma : Hašovací funkce, principy, příklady, kolize, přednáška na ČVÚT, Cryptofest, 2005
když už tu máme takové pěkné vzdělávací vlákno.
(odpovědět) | | mr.Crow. | 213.211.34.* | 19.2.2010 13:22 |
|
|
|
