Kriptográfia, 04 előadás (október 22.)

Ma a helyzet a többi titkosítást, de kapcsolódó kriptográfiai titkos kulcs. Néha pontosan, néha streaming.

Mi rejtjelfolyam? Ha egy tömbrejtjelezésnél működik a nagy mennyiségű információt, és titkosítja az egész blokk, a rejtjelfolyam működik bit. Nagyon ritkán működik bájt.

Rejtjelfolyam egy titkosító fejlesztése Vernon, amit kitalált, 1917-ben, eljövetele előtt a kriptográfia, mint tudomány. A különlegessége ennek a titkosító - mintegy bizonyítani tudja, hogy ez teljesen stabil, bizonyos feltételek mellett.

Úgy működik, - van egy patak a nyílt szöveg és a kulcs patak, patakok adunk bitenkénti modulo két és kap rejtjelfolyam.

Bebizonyosodott az ember, mint Claude Shannon, aki először kezdett tanulni a kódokat és matematizálására minden ezt az elméletet. És azt bizonyította, hogy ha Vernon titkosító kulcsot használjuk, egyenlő hosszúságú a nyílt szöveg és a kulcs _absolyutno_ véletlenszerűen kiválasztott, és a kulcsot csak egyszer használatos, akkor teljesen stabil.

De ez csak egy modell, mint egy Turing-gép.

De semmi sem teljesen véletlen valós rendszerekben. Ha úgy dönt, a kulcs hosszával megegyező a nyílt szöveg még mindig lehetséges, hogy nehéz választani egy teljesen véletlenszerű.

És azt szeretném, hogy a determinisztikus algoritmus, amely előállítja a kulcs tartományban.

Felmerül a kérdés, hogy mit tegyünk? Hogyan tudjuk módosítani a kódot Vernon, hogy kapnánk gyakorlati kriptográfiai rendszerek között.

Bármilyen klasszikus rejtjelfolyam preddstavlyaet saját kulcs patak. Ezután a kulcsot patak áll modulo kettő az egyszerű szöveges és rejtjelezett kapunk.

A legfontosabb elem - a funkció, amit vyrayuatyvaet kulcs tartományban. Ő attól függ, bizonyos kulcs, amely bemenet.

Van egy doboz, hogy a kulcs a billentyűt, az általa előállított egy kicsit. Ezek a bitek használ, mint a tartományban.

Rejtjelfolyam termel csak tartománynál, nem bonyolult műveletek tiszta szöveget, a blokk titkosításokat nem.

A patak titkosításokat van egy kis hátránya - önmagában nem véd a szándékos torzításokat. Patak ciphers hogy csak titoktartás. Ugyanebben blokk módban van mód, hogy támogassa elleni védelem torzítás.

léptetőregiszter visszacsatolással. Kidolgozása az új bit függvényében n korábban. Nagyon gyakran használják a hagyományos lineáris függvény. ISTO elméletileg használható lineáris. De szinte mindig egyenes.

Shift regiszterek, amelyek visszacsatolás lineáris függvény az úgynevezett lineáris visszacsatolt eltolási regiszter.

Ha beszélünk általában a shift regisztert. Bármilyen lineárisan visszacsatolt shiftregiszter lehet állítani nemcsak koeefitsenty lineáris függvény, hanem egy többtagú.

Következő fokozat polinom hosszával megegyező léptető regiszter.

Miután a shift regiszter vyrayuatyvaet nekünk egy kulcsot tartományban, előfordulhat, hogy mivel a végesség mi regiszter, a sorozat periodikus.

Mi van, ha a szekvencia ismétlődik a kis bárok? Akkor mi a legfontosabb lenne nagyon rossz, akkor egy nem véletlenszerű sorrendben.

Szeretnénk egy shift regiszter az időszak ez a szekvencia maximális. És akkor felmerül a kérdés - hogyan lehet róla, hogy az időszak volt a legnagyobb? Mivel voobze meghatározni ezt az időszakot léptető regiszter?

Chtobf válaszoljon a kérdésre, ami a legnagyobb, viszont a státusz regiszter. Abból, amit időskálán kezd ismétli önmagát? Amikor bejutni sotoyanii már esett. A maximális időszak a sorrend lehet, mi? 2 ^ (Llength regiszterben) - 1.

Nézzünk egy példát s0 * s1 + s2. A karakterisztikus polinomja 1 + x 2 + x 3, 000 -> 000

Abban az esetben nemlineáris ristra időszakban egy kicsit kiszámítható.

De abban az esetben lineáris van spekuláció - annak érdekében, hogy legfeljebb a karakterisztikus polinom irreducibilis kell felett gf2.

Tény, neprivoimosti polinomok elég.

Szükséges, hogy a polinom primitív volt.

Igazoljuk, hogy 1 + x + x ^ 4 lesz egy maximális időtartam.

Nos ez primtivny polinom?

Először meg kell adni a definíció - adja polinomfok. Az, hogy a polinom - van minimalneo száma n, hogy mnogchlen x ^ n - 1 osztható F (x).

Mi nem megy a dzsungelbe a véges testek, de van ebben a sorrendben - igen fontos jellemzője.

A polinom nevezzük primitív, Elsi annak érdekében egyenlő 2 ^ n - 1.

Ez lehet bizonyítani, hogy minden irreducibilis polinom osztja a polinom.

a + b mod p a * b mod p

És akkor is, ha nincs gyökere ezen a területen.

Polinom úgynevezett primitív, ha ez az alfa is kifejeződik az összes sejtben elemei a területen.

Ha veszel egy polinom, ami nem primitív, nem minden sorakoznak a láncban.

Vette Shift Register zababahali lábujj és edinichki vett primtivny polinom, tette a működési szabályokat.

Belátható, hogy a szekvencia kialakult egy léptetőregiszter szinte véletlenszerűen.

Ha az előírtnál n = 256, akkor az időszak lesz 2 ^ 256. Azaz, a nyilvántartás pi kis hosszúságú kaphat egy random szekvencia hossza irreális. De itt van egy fogás.

Polinom, sőt, a kulcs.

Minden jó lenne, ha a két eloveka nincs elkényeztetett, és nem jön ki adlgoritm, ami egy kis darab posledovtelnosti helyreállítása a nyilvántartásban. Nevük Berlekamp és Messi.

Ő egy klasszikus, használják sok helyen.

Bemutató az algoritmus Berlekamp Massey.

Végül elérkeztünk a mókára.

Az ötletet, hogy regisztrál a visszajelzést nem sikerült. Mit kell tenni? Hogyan élnek?

Mi a probléma a mi esetünkben? Majdnem minden esetben lineáris. Meg kell bevezetni a nem-linearitás.

Hagyja fdelaem szűrőt. Nem adjuk a nagyon skála, és néhány nemlineáris függvénye tartományban. Egy másik ötlet -, hogy használjon más típusú non-linearitás

Van egy kedvenc sort shift regiszter, de nem gamma vybrasiyvaetsya balról a sejt, és egyfajta nemlineáris függvény az állam. Azaz, egy állami sostonie folytassa lineárisan, de a különböző tekintettel a nemlineáris függvény az állam. Van egy fejlődésének ezt az elképzelést.

Van egy nemlineáris függvénye változók en. És az egyes változók által készített külön léptető regiszter.

Belátható, hogy az első változat csökken a második.

Tehát, amikor én csak egy esetben, a sorozat szinte véletlenül. Engedélyezett a szűrőn. Ki mondta, hogy a szekvencia véletlen?

Mi lehet a legnagyobb távolság?

max = ρ (f, A) Tekintsük Molosh Hadamard transzformáció - bővülését alapján ortogonális függvények.

Maximális távolság 2 n - 2 (n / 2), ha n páros. Funkció, amely elérte a maximumot, az úgynevezett hajlított funkciókat.

Tehát azt találtuk, hogy a függvény kell egy hajlított funkciót, egyensúlyban kell lennie, sőt, hogy tökéletesen kiegyensúlyozott.

Nézzük helyettesítheti a funkciója a változók állandó. Ha egy új funkció méltánytalan, akkor indítson támadást helyettesítve a változó kívánt nulla, és próbál húzni összefüggéseket.

Például, ha egy szűrő funkció, például x * y \ xor x * z \ xor z. z = 1 =>! xy

f (x, y, z) = z valószínűséggel 3/4. És ugyanez verotyanostyu ICSU.

Ez azt jelenti, hogy csak akkor megy át az értékeket Xs. És van egy kitalálni detektor - verotyanost 3/4 mérkőzést. Akkor is vissza tudja állítani a nyilvántartásban részt. Akkor visszaállítani ötvözi y.

Még az úgynevezett korellyatsionnymi támadást. A komplexitás nagyon erősen esik. Ha a teljesítmény voltak regiszterek H1 H2 H3, a teljes keresés 2 (n 1 + n 2 + n 3). akkor nem lesz túlzás 2 n 1 + n 2 2 + n 2 3

Bad ciphers lehet psomtret bejelentkezik a https: \\ mail.ru

Ha a króm, azt mutatja, a zár, és ott a leírás azt mondja, hogy a kapcsolat védett rc4 128. rejtjel rc4 streaming, egonedavno lomanuli seyas és az nem biztonságos.