Hric - Příklad na zápočet - potřebuju poradit...
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Hric - Příklad na zápočet - potřebuju poradit...
povinnosti k zápočtu z algoritmů u Hrice si plním výpočtem 9 z jeho příkladů a jeden z nich zní :
"Předpokládejte že v RSA se prvočísla p a q liší od odmocniny z n (jejich součinu) nanejvýš o jeden bit, tedy jsou téměř stejně velká. Kolik rozkladů hrubou silou musím vyzkoušet?"
já to buď nechápu a nebo je odpověď skutečně to, že stačí jeden - odmocninu z n znám a když si určím nejbližší vyšší, resp. nebližnší nižší prvočíslo, tak to musí ten správný rozklad...
ale přijde mi, že je to nějaký moc jednoduchý, takže asi něco přehlížím/nechápu zadání...
"Předpokládejte že v RSA se prvočísla p a q liší od odmocniny z n (jejich součinu) nanejvýš o jeden bit, tedy jsou téměř stejně velká. Kolik rozkladů hrubou silou musím vyzkoušet?"
já to buď nechápu a nebo je odpověď skutečně to, že stačí jeden - odmocninu z n znám a když si určím nejbližší vyšší, resp. nebližnší nižší prvočíslo, tak to musí ten správný rozklad...
ale přijde mi, že je to nějaký moc jednoduchý, takže asi něco přehlížím/nechápu zadání...
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
No do vzdalenosti +- 1 bit se ale tech prvocisel urcite vejde vic, ne? A nejde i o to testovani prvocisel?
Plug 'n' Pray.
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
Nebylo by nejjednoduší udělat si dva cykly od 1 do log_2(sqrt(n)) a zkouset prehazovat 1 bit pro jedno cislo (1 cyklus) a druhy bit pro druhe cislo (2. cyklus) a pak to pronasobit a testovat to? Slozitost je log_2(n)^2 * (nasobeni cisel + test prvociselnosti)Ellrohir píše:...
Osiris
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
2Tuetschek : řekl bych, že o to nejde - určování prvočíselnosti je snad u RSA až sekundární problém, ne? (resp. dá se snad předpokládat, že když už někdo bude chtít zkošuet brutal attack, tak bude schopen určit efektivně prvočíselnost zkoušených možností)...spíš to bude v tom, jak říkáš, že do +/- 1 bit se jich vejde víc než právě dvě...teď ale jak teda určit závislost mezi hodnotou odmocniny z n a počtu prvočísel lišících se o +/- jeden bit, což bude zjevně odpověď na tuto otázku? já sem asi po čtyřech hodinách s algoritmy úplně blbej
2Osiris : asi trochu nechápu nicméně určitě vím, že mě je jedno, co by bylo jednodušší...já mám zodpovědět otázku, kolik je potřeba zkusit možností při brute force (ale když člověk ví, že rozdíl prvočísel je max 1 bit od odmocniny ze součinu)
2Osiris : asi trochu nechápu nicméně určitě vím, že mě je jedno, co by bylo jednodušší...já mám zodpovědět otázku, kolik je potřeba zkusit možností při brute force (ale když člověk ví, že rozdíl prvočísel je max 1 bit od odmocniny ze součinu)
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
Těch prvočísel bude fakt hodně, protože tenhle tvůj problém je ekvivalentní s tím, najít všechna prvočísla od sqrt(n)/2 do 2*sqrt(n) (nebo nějaká takováhle konstanta), což je pravděpodobně ekvivalentní vyřešit faktorizaci obecného n.Ellrohir píše:...
Jinak ten můj algoritmus potřebuje vygenerovat log_2(n) čísel, což už je rozumné. Třeba pro n dlouhé 2048 bitů bude potřebovat zkusit cca 2048 čísel.
Osiris
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
to je hezký a díky za to, jenomže jak znovu říkám - nejde o to, upravit metodu tak, aby fungovala co nejefektivněji...jde o to analyzovat a říct, jak bude fungovat ta neefektivní
pakliže je pravda to, co předpokládáš - že to je ekvivalentní faktorizaci obecného n - pak je to, co jsem chtěl slyšet
pakliže je pravda to, co předpokládáš - že to je ekvivalentní faktorizaci obecného n - pak je to, co jsem chtěl slyšet
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
Pod větou Kolik rozkladů hrubou silou musím vyzkoušet bych si představil, kolik MINIMÁLNĚ. To taky můžeš říct, že hledání Hamiltonovské kružnice na kružnicích je O(n!), i když je to triviální.Ellrohir píše:to je hezký a díky za to, jenomže jak znovu říkám - nejde o to, upravit metodu tak, aby fungovala co nejefektivněji...jde o to analyzovat a říct, jak bude fungovat ta neefektivní
pakliže je pravda to, co předpokládáš - že to je ekvivalentní faktorizaci obecného n - pak je to, co jsem chtěl slyšet
Osiris
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
no nevim nevím...mě prostě přijde, že v tomhle případě opravdu není účelem vylepšit "hackovací algoritmus" a že "hrubou silou" se opravdu myslí "hloupé" zkoušení všech možných prvočísel...to je jako, kdyby byla otázka na hashování a na počet nutně vyzkoušitelných možností při "slovníkovém útoku" - a já místo hledání závislosti počtu možností na délce slova a výběru znaků začal chytračit, jak útočníka vylepšit, aby jich nemusel projít tolik...to by podlě me stála otázka "navrhněte lepší heuristiku pro útok na RSA šifru", kdybych chtěl, abych vylepšoval základní "hloupý" algoritmus...
a klidně si to napíšu do zdůvodnění řešení, že jsem to zadání prostě pochopil takhle...můj problém ale je, že se mi nedaří tu závislost počtu možností na n (potažmo odmocnině z n) najít
a klidně si to napíšu do zdůvodnění řešení, že jsem to zadání prostě pochopil takhle...můj problém ale je, že se mi nedaří tu závislost počtu možností na n (potažmo odmocnině z n) najít
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
Jenže ten příměr je špatný. Tady je to zadání osekané. To je, jako kdybych ti dal prolomit hash slovníkovým útokem s tím, že bych ti řekl, že se jedná o měsíce a dny v týdnu (celkem 19 možností). Šel bys na to tak, že bys zkoušel všechny možné kombinace písmen a slov? Asi ne. Hrubou silou zde znamená prostě vyzkoušet všech 19 možností.Ellrohir píše:no nevim nevím...mě prostě přijde, že v tomhle případě opravdu není účelem vylepšit "hackovací algoritmus" a že "hrubou silou" se opravdu myslí "hloupé" zkoušení všech možných prvočísel...to je jako, kdyby byla otázka na hashování a na počet nutně vyzkoušitelných možností při "slovníkovém útoku" - a já místo hledání závislosti počtu možností na délce slova a výběru znaků začal chytračit, jak útočníka vylepšit, aby jich nemusel projít tolik...to by podlě me stála otázka "navrhněte lepší heuristiku pro útok na RSA šifru", kdybych chtěl, abych vylepšoval základní "hloupý" algoritmus...
a klidně si to napíšu do zdůvodnění řešení, že jsem to zadání prostě pochopil takhle...můj problém ale je, že se mi nedaří tu závislost počtu možností na n (potažmo odmocnině z n) najít
Btw. víš, co je to vůbec heuristika? Tohle není heuristika, to co jsem napsal. Ten můj algoritmus je korektní a DETERMINISTICKÝ a vždy najde rozklad n na zmíněná p a q hodně rychle - samozřejmě za té zmíněné podmínky o 1 bitu.
Osiris
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
Osiris: myslim, ze mas pravdu, s tim konceptem ... ze Hricovi fakt jde o to, kolik MUSIM vyzkouset, tj. minimalni pocet ... protoze jinak bych si mohl vymyslet libovolne hodne velke cislo a nejaky algoritmus by se uz vzdycky nasel ... ale ten tvuj algoritmus jsem z toho taky nepobral. Co je "prehazovat bit"?
Plug 'n' Pray.
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.Tuetschek píše:Osiris: myslim, ze mas pravdu, s tim konceptem ... ze Hricovi fakt jde o to, kolik MUSIM vyzkouset, tj. minimalni pocet ... protoze jinak bych si mohl vymyslet libovolne hodne velke cislo a nejaky algoritmus by se uz vzdycky nasel ... ale ten tvuj algoritmus jsem z toho taky nepobral. Co je "prehazovat bit"?
Osiris
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
Aha ... ja jsem to ale pochopil tak, ze p a q se lisi od sqrt(n) max. o 1 bit svou delkou ... tohle si myslim, ze neco takoveho nema moc sanci nastat .Osiris píše:Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.
Plug 'n' Pray.
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Hric - Příklad na zápočet - potřebuju poradit...
No to je sporné, dá se to pochopit oběma způsoby. Když mě někdo řekne, že číslo a se liší od čísla b nanejvýš o 1 bit, rozhodně bych si to představil tak, že stačí někde znegovat bit a z čísla a dostanu b. Tohle je akademický příklad, takže se asi moc nehledí jestli to reálně může nastat.Tuetschek píše:Aha ... ja jsem to ale pochopil tak, ze p a q se lisi od sqrt(n) max. o 1 bit svou delkou ... tohle si myslim, ze neco takoveho nema moc sanci nastat .Osiris píše:Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.
Osiris
Re: Hric - Příklad na zápočet - potřebuju poradit...
riesim teraz tuto istu ulohu.. riesenie mi dost pomohlo.. ale keby sa jednalo o to ze sa meni postupne kazdy bit, tak by tam bolo podla mna.. p a q sa lisia od sqrt(n) najviac "v" jednom bite..
Re: Hric - Příklad na zápočet - potřebuju poradit...
mohol by mi niekto pomoct s 2 ulohami? nie som si isty co tam napisat.. uz len tieto mi chybaju a dost by mi to pomohlo
Popište (pseudopolynomiální) algoritmus pro rešení souctu podmnožiny
Vysvetlete, proc tyto algoritmy nelze považovat za polynomiální.
Heuristika najbližšieho bodu
Na zaciatku vytvoríme cyklus z jednoho lub. bodu.
V jednotlivých krokoch postupne hladáme vrchol u, ktorý
nie je v cykle a je najbližšie k cyklu, k nejakému vrcholu
v. Rozšírime cyklus pridaním u za v a opakujeme, kým
v cykle nie sú všetky vrcholy. Ukážte, že táto heuristika
vracia cyklus, ktorý je najviac dvaktát dlhší než optimálna
cesta (pri platnosti trojuholnikovej nerovnosti).
Navrhnite zlepšenie k popísanej heuristike.
Popište (pseudopolynomiální) algoritmus pro rešení souctu podmnožiny
Vysvetlete, proc tyto algoritmy nelze považovat za polynomiální.
Heuristika najbližšieho bodu
Na zaciatku vytvoríme cyklus z jednoho lub. bodu.
V jednotlivých krokoch postupne hladáme vrchol u, ktorý
nie je v cykle a je najbližšie k cyklu, k nejakému vrcholu
v. Rozšírime cyklus pridaním u za v a opakujeme, kým
v cykle nie sú všetky vrcholy. Ukážte, že táto heuristika
vracia cyklus, ktorý je najviac dvaktát dlhší než optimálna
cesta (pri platnosti trojuholnikovej nerovnosti).
Navrhnite zlepšenie k popísanej heuristike.