Tankolas atveres!

[Vajk Fekete]

a brute force/nem brute force modszereket ugy szoktak megkulonboztetni, 
hogy a tores ido/szemitas igenye hogyan aranyos a kulcs hosszaval (a 
lehetseges kulcsok szamaval).

altalaban a brute force az egyenesen aranyos a kulcsok szamaval, a 
kulcsok szama meg exponencialisan a kulcshosszal, igy konnyu olyan 
kulcshosszot valasztani, hogy a brute force nagyon sokaig tartson . 
raadasul a kodolas eroforrasigenye is no a kulcshosszal, a probalgatas 
idoigenye meg gyorsabban no. az mas kerdes, hogy adott kulcshossz 
tegnapi gepen a brute force modszerrel elegnek tunt (varhatoan 2000 ev 
probalgatas), a mai gep meg 100-szor gyorsabb, es veszek szazat belole, 
es egy par honap alatt megvan. de ezt nem tortek meg, csak kellene a 
kulcshosszot novelni. sajna a rendszereink elegge hardkodoltak ahhoz, 
hogy a kulcshossz noveles ugyanakkora atalakitas mint az algoritmus csereje.

adott titkositasi algoritmust akkor szoktak megtortnek tekinteni, ha 
talalnak olyan egyszerusitest, modszert, algoritmust, amivel a kulcs 
megtalalasanak eroforrasigenye sokkal lassabban no mint linearis a 
kulcsok szamaval. pl az RSA algorimus lenyege, hogy ha van egy nehany 
szaz jegyu szamod, ami ket primszam szorzata, akkor a minden primszamot 
kiprobalok hogy osztoja-e modszernel nagysagrendileg hatekonyabb modszer 
jelenleg nem ismert a ket primszam meghatarozasara. ez a probalgatas nem 
is a lehetseges kulcsokat probalja vegig, megis probalgatas, es mivel a 
hasznalt primszamok hossza aranyos a kulcshosszal a probalgatas hossza 
is aranyos lesz. ezert ez brute-formce modszer. ha a matematikusok 
talalnanak egy modszert, amivel a szorzat sokkal egyszerubben 
felbonthato, es eroforrasigenye (futasi ideje) nem a x a (jegyek szama) 
hatvanyon, hanem mondjuk (jegyek szama) a negyediken, akkor hiaba 
noveled a jegyek szamat a ketszeresere, feltorni csak 16szor tart tovabb.

bocs a szofosasert.

vajk

pyxys1 wrote:
> Szia Auth Gábor,
> 
> Monday, August 25, 2003, 1:04:39 PM, you wrote:
> 
> AG> Halihó!
> 
> AG> 2003. augusztus 25. 12.53 dátummal pyxys1 ezt írta:
> 
>>>lásd rsa feltörése. iszonyú pénz, idő, csak azért, hogy bizonyított
>>>legyen, hogy elméletileg fejthető.
>>
> AG>   Nem mindegy, hogy elméletileg törik, vagy brutal-force után. Az RSA-t 
> AG> tudtommal brutal-force tudták törni, úgy meg nem elméletileg van törve, 
> AG> hanem gyakorlatilag. Elméleti törés azt jelenti, hogy pár (bonyolultabb) 
> AG> számolás után előáll a jó kulcs, nem pedig az, hogy minden kulcsot 
> AG> megpróbálnuk és egyszer az egyik jó lesz... :)
> 
> a kriptorendszer jóságát az mutatja, hogy menni ideig képes
> ellenállni a töréseknek. mivel ezidáig egyettlen egy kripto rendszer
> van, ami elméletileg sem törhető, ezért az elméleti és gyakorlati
> törés... hogyan értelmezed?
> a pár "bonyolultabb" számolás, lehet a teljes kipróbálás is, hiszen a
> végén meg van a kulcs, amivel utána minden üzenet törhető a következő
> kulcs változtatásig.
> 
>