4. One-time Pad a lineární posouvací registry Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 10. října 2021 □ - = One-time Pad Posouvací registr Kryptoanalýza O čem to bude Použití systému Q One-time Pad Ä • Popis systému ™ ^ ^ • Použití systému P u 1 Fl Nyní budeme hovořit o následujícím perfektním systému: Předpokládejme, že abeceda Z je obvyklá 26-ti písmenná anglická abeceda a že tečky, mezery atd. jsou vypuštěny a že odesílaná zpráva M sestává z N písmen. Abychom zašifrovali zprávu, vygenerujeme náhodnou posloupnost o N písmenech z abecedy Z, přičemž výběr každého písmene je nezávislý a každé písmeno má pravděpodobnost 4, že bude vybráno. Fl Nyní budeme hovořit o následujícím perfektním systému: Předpokládejme, že abeceda Z je obvyklá 26-ti písmenná anglická abeceda a že tečky, mezery atd. jsou vypuštěny a že odesílaná zpráva M sestává z N písmen. Abychom zašifrovali zprávu, vygenerujeme náhodnou posloupnost o N písmenech z abecedy Z, přičemž výběr každého písmene je nezávislý a každé písmeno má pravděpodobnost ^, že bude vybráno. Tato náhodná posloupnost (Z|,..., ZN) bude klíč K a, abychom zašifrovali M = (x1,..., xN) pomocí K, budeme definovat C = e(M, K) jako y, = Xj e Z, mod 26, kde jako v obvyklém substitučním číslicovém systému jsme písmenům po řadě přiřadili číselnou hodnotu z množiny {0,... ,25}. One-time Pad Posouvací registr Kryptoanalýza Popis systému Použiti systému Tedy jako klíče vybereme rovněž všech 26™ posloupností délky A/; každou z těchto posloupností lze zvolit se stejnou pravděpodobností tj. H{K) = A/log26. Tedy jako klíče vybereme rovněž všech 26^ posloupností délky A/; každou z těchto posloupností lze zvolit se stejnou pravděpodobností ti. H{K) = A/log26. Protože klíč K = (Z1, Z2,..., ZN) je posloupnost náhodných písmen z 26-ti prvkové abecedy Z, je zřejmé, že existuje 26^ stejně pravděpodobných kryptogramu. Zároveň platí 1 P(K\C) = 26 N pro všechna K eK. Tedy jako klíče vybereme rovněž všech 26^ posloupností délky A/; každou z těchto posloupností lze zvolit se stejnou pravděpodobností ti. H{K) = A/log26. Protože klíč K = (Z1, Z2,..., ZN) je posloupnost náhodných písmen z 26-ti prvkové abecedy Z, je zřejmé, že existuje 26^ stejně pravděpodobných kryptogramu. Zároveň platí P(«\C) = ^ pro všechna K eK. Z kritéria 3 vidíme, že tento tzv. one-time pad systém (M, K, C je perfektní, neboť klíč je jednoznačně určen zprávou a kryptogramem, množina zpráv je je zároveň množinou klíčů, resp. kryptogramu, zejména tedy mají stejnou mohutnost. Tedy jako klíče vybereme rovněž všech 26^ posloupností délky A/; každou z těchto posloupností lze zvolit se stejnou pravděpodobností ti. H{K) = A/log26. Protože klíč K = (Z1, Z2,..., ZN) je posloupnost náhodných písmen z 26-ti prvkové abecedy Z, je zřejmé, že existuje 26^ stejně pravděpodobných kryptogramu. Zároveň platí P(«\C) = ^ pro všechna K eK. Z kritéria 3 vidíme, že tento tzv. one-time pad systém (M, K, C je perfektní, neboť klíč je jednoznačně určen zprávou a kryptogramem, množina zpráv je je zároveň množinou klíčů, resp. kryptogramu, zejména tedy mají stejnou mohutnost. One-time Pad pis sys Posouvací registr Kryptoanalýza Použití systému Tento šifrovací systém byl objeven v roce 1926 americkým inženýrem společnosti AT&T Gilbertem S. Vernamem (v dřívějších dobách byla písmena klíče napsána na listech trhacího bloku a jakmile bylo klíčové písmeno použito, byl odpovídající list vytrhnut a zničen). One-time Pad pis sys Posouvací registr Kryptoanalýza Použití systému Tento šifrovací systém byl objeven v roce 1926 americkým inženýrem společnosti AT&T Gilbertem S. Vernamem (v dřívějších dobách byla písmena klíče napsána na listech trhacího bloku a jakmile bylo klíčové písmeno použito, byl odpovídající list vytrhnut a zničen). Dnes se one-time pad neprovozuje s písmeny nýbrž s bity. Pak a,5 k, g {0,1} a kryptogram a-i ©k-ia2©k2 ... an©kn získáme pomocí binárního sčítání. Tento šifrovací systém byl objeven v roce 1926 americkým inženýrem společnosti AT&T Gilbertem S. Vernamem (v dřívějších dobách byla písmena klíče napsána na listech trhacího bloku a jakmile bylo klíčové písmeno použito, byl odpovídající list vytrhnut a zničen). Dnes se one-time pad neprovozuje s písmeny nýbrž s bity. Pak a,5 k, g {0,1} a kryptogram a-i ©k-ia2©k2 ... an©kn získáme pomocí binárního sčítání. Pro bezpečnost tohoto systému je podstatné, že všechny posloupnosti délky n se vyskytují s toutéž pravděpodobností. Jinak řečeno: Bity klíčového slova musí být voleny náhodně. One-time Pad Posouvací registr Kryptoanalýza Popis systému IV Použití systému Nejlépe si to představíme tím způsobem, že vrháme ideální minci. V praxi používáme fyzikální náhodný zdroj a tím automaticky vytvoříme bity. One-time Pad pis sys Posouvací registr Kryptoanalýza Použití systému Nejlépe si to představíme tím způsobem, že vrháme ideální minci. V praxi používáme fyzikální náhodný zdroj a tím automaticky vytvoříme bity. Za tuto formu perfektní bezpečnosti musíme - nikoliv neočekávaně - platit vysokou cenu. Pro tradiční one-time pad potřebujeme velké množství papíru, který musí být před útočníkem absolutně bezpečně ukryt. Proto se takovéto systémy používají jen zřídka. Nejlépe si to představíme tím způsobem, že vrháme ideální minci. V praxi používáme fyzikální náhodný zdroj a tím automaticky vytvoříme bity. Za tuto formu perfektní bezpečnosti musíme - nikoliv neočekávaně - platit vysokou cenu. Pro tradiční one-time pad potřebujeme velké množství papíru, který musí být před útočníkem absolutně bezpečně ukryt. Proto se takovéto systémy používají jen zřídka. V druhé světové válce se one-time pad používal anglickou dešifrovací skupinou, aby zprostředkovala zprávy premiérovi, které byly Němci zašifrovány pomocí Enigmy a které Angličané rozšifrovali. Tímto způsobem si spojenci zajistili, že Němci až do konce války nevěděli, že Enigma byla rozluštěna. One-time Pad Posouvací registr Kryptoanalýza Popis systému V Použití systému Jednou z dalších nevýhod tohoto systému je neexistence matematického způsobu generování nezávislých náhodných proměnných, které slouží jako klíč. One-time Pad pis sys Posouvací registr Kryptoanalýza Použití systému Jednou z dalších nevýhod tohoto systému je neexistence matematického způsobu generování nezávislých náhodných proměnných, které slouží jako klíč. Tedy je nutné použít pseudonáhodných posloupností generovaných jednou z mnoha standardních metod. One-time Pad pis sys Posouvací registr Kryptoanalýza Použití systému Jednou z dalších nevýhod tohoto systému je neexistence matematického způsobu generování nezávislých náhodných proměnných, které slouží jako klíč. Tedy je nutné použít pseudonáhodných posloupností generovaných jednou z mnoha standardních metod. Neexistuje pak žádná záruka, že takováto pseudonáhodné posloupnosti nám budou stejnou úroveň bezpečnosti. Jedná se o hluboký matematický problém. Jednou z dalších nevýhod tohoto systému je neexistence matematického způsobu generování nezávislých náhodných proměnných, které slouží jako klíč. Tedy je nutné použít pseudonáhodných posloupností generovaných jednou z mnoha standardních metod. Neexistuje pak žádná záruka, že takováto pseudonáhodné posloupnosti nám budou stejnou úroveň bezpečnosti. Jedná se o hluboký matematický problém. Proč se tento nepochybně perfektní systém používá jen velmi zřídka? Abychom byli schopni zodpovědět tuto otázku, představme si sebe v roli příjemce. One-time Pad Posouvací registr Kryptoanalýza Popis systému Použití systému Použití systému 1 Příjemce může přirozeně kryptogram pohodlně rozšifrovat: dešifrování je v podstatě stejný postup jako zašifrování (používáme-li bity, jedná se dokonce o přesně totéž). To ale může příjemce provést jen v případě, že má klíč. One-time Pad Posouvací registr Kryptoanalýza Popis systému Použití systému Použití systému 1 Příjemce může přirozeně kryptogram pohodlně rozšifrovat: dešifrování je v podstatě stejný postup jako zašifrování (používáme-li bity, jedná se dokonce o přesně totéž). To ale může příjemce provést jen v případě, že má klíč. Kde je vlastně problém? Problém spočívá v tom, že musíme přenést (doručit) dlouhý tajný klíč. One-time Pad Posouvací registr Kryptoanalýza „ , Popis systému Použiti systému Použití systému I Příjemce může přirozeně kryptogram pohodlně rozšifrovat: dešifrování je v podstatě stejný postup jako zašifrování (používáme-li bity, jedná se dokonce o přesně totéž). To ale může příjemce provést jen v případě, že má klíč. Kde je vlastně problém? Problém spočívá v tom, že musíme přenést (doručit) dlouhý tajný klíč. Kdybychom toto prováděli pomocí stejné cesty jako zprávu, je vzhledem k délce klíče šance přečtení klíče stejná jako při předání nezašifrovaného textu zprávy. One-time Pad Posouvací registr Kryptoanalýza „ , Popis systému Použiti systému Použití systému I Příjemce může přirozeně kryptogram pohodlně rozšifrovat: dešifrování je v podstatě stejný postup jako zašifrování (používáme-li bity, jedná se dokonce o přesně totéž). To ale může příjemce provést jen v případě, že má klíč. Kde je vlastně problém? Problém spočívá v tom, že musíme přenést (doručit) dlouhý tajný klíč. Kdybychom toto prováděli pomocí stejné cesty jako zprávu, je vzhledem k délce klíče šance přečtení klíče stejná jako při předání nezašifrovaného textu zprávy. Člověk by si mohl myslet, že u takovéhoto systému by mohl odesilatel zprávu nepříteli předat přímo do domu. One-time Pad Posouvací registr Kryptoanalýza Popis systému Použití systému Použití systému II To ale není zcela správné; totiž pro přenos klíče může odesilatel určit druh, způsob a dobu předání, což samozřejmě u přenosu zprávy neplatí. Jiný způsob přenosu klíče je použití kurýra. One-time Pad Posouvací registr Kryptoanalýza Popis systému Použití systému Použití systému II To ale není zcela správné; totiž pro přenos klíče může odesilatel určit druh, způsob a dobu předání, což samozřejmě u přenosu zprávy neplatí. Jiný způsob přenosu klíče je použití kurýra. Při přenosu klíče se nejedná pouze o teoretický problém, nýbrž o to, že obtížnost výměny klíče silně ovlivňuje nasazení šifrovacích systémů. One-time Pad Posouvací registr Kryptoanalýza „ , Popis systému Použiti systému Použití systému II To ale není zcela správné; totiž pro přenos klíče může odesilatel určit druh, způsob a dobu předání, což samozřejmě u přenosu zprávy neplatí. Jiný způsob přenosu klíče je použití kurýra. Při přenosu klíče se nejedná pouze o teoretický problém, nýbrž o to, že obtížnost výměny klíče silně ovlivňuje nasazení šifrovacích systémů. Důležitý postup pro vyřešení tohoto problému spočívá v tom, že namísto skutečně náhodných klíčových posloupností použijeme pouze pseudonáhodné posloupnosti. One-time Pad Posouvací registr Kryptoanalýza „ , Popis systému Použiti systému Použití systému II To ale není zcela správné; totiž pro přenos klíče může odesilatel určit druh, způsob a dobu předání, což samozřejmě u přenosu zprávy neplatí. Jiný způsob přenosu klíče je použití kurýra. Při přenosu klíče se nejedná pouze o teoretický problém, nýbrž o to, že obtížnost výměny klíče silně ovlivňuje nasazení šifrovacích systémů. Důležitý postup pro vyřešení tohoto problému spočívá v tom, že namísto skutečně náhodných klíčových posloupností použijeme pouze pseudonáhodné posloupnosti. Takováto posloupnost vypadá na první pohled jako skutečná náhodná posloupnost. One-time Pad Posouvací registr Kryptoanalýza Popis systému Použití systému Použití systému III A co je ještě důležitější: náhodnou posloupnost lze určit pomocí několika málo dat; tato data pak představují skutečný klíč. One-time Pad Posouvací registr Kryptoanalýza Popis systému Použití systému Použití systému III A co je ještě důležitější: náhodnou posloupnost lze určit pomocí několika málo dat; tato data pak představují skutečný klíč. Oba komunikující partneři pak mohou z těchto dat spočítat náhodné posloupnosti a zašifrovat zprávu resp. dešifrovat kryptogram. Problém přenosu klíče tak není zcela vyřešen, ale podstatně ulehčen. One-time Pad Posouvací registr Kryptoanalýza „ , Popis systému Použiti systému Použití systému III A co je ještě důležitější: náhodnou posloupnost lze určit pomocí několika málo dat; tato data pak představují skutečný klíč. Oba komunikující partneři pak mohou z těchto dat spočítat náhodné posloupnosti a zašifrovat zprávu resp. dešifrovat kryptogram. Problém přenosu klíče tak není zcela vyřešen, ale podstatně ulehčen. Samozřejmě musíme za tuto výhodu zaplatit: takovéto systémy neposkytují žádnou perfektní bezpečnost. Budeme tedy hledat kompromis mezi docílenou bezpečností a množinou tajně přenositelných dat. One-time Pad Posouvací registr Kryptoanalýza Primitivita 0 čem to wm ■ vytvořených lineárními A n .. p posouvacími registry w • Primitivní polynomy Q Posouvací registr £| Krvntnanal\/7a linpárnírh • Generování ^ ^ , . rpnQtr° • Vlastnosti posloupností One-time Pad Posouvací registr Generování I Kryptoanalýza Generování Vlastnosti Primitivita Posouvací registr je posloupnost v řadě za sebou následujících registrů, přičemž každý registr může obsahovat pouze číslici 1 (on) nebo 0 (off). Hodinový strojek reguluje chování systému, který pracuje v souladu s následujícími podmínkami: One-time Pad Posouvací registr Kryptoanalýza Primitivita Generování 1 Posouvací registr je posloupnost v řadě za sebou následujících registrů, přičemž každý registr může obsahovat pouze číslici 1 (on) nebo 0 (off). Hodinový strojek reguluje chování systému, který pracuje v souladu s následujícími podmínkami: Předpokládejme, že systém má m registrů R0,R^,...,fíA7?_1 a že Xj(t) označuje obsah registru fí, v čase t. Nechť je dále na začátku systém ve stavu One-time Pad Posouvací registr Generování I Kryptoanalýza Generování Vlastnosti Primitivita Posouvací registr je posloupnost v řadě za sebou následujících registrů, přičemž každý registr může obsahovat pouze číslici 1 (on) nebo 0 (off). Hodinový strojek reguluje chování systému, který pracuje v souladu s následujícími podmínkami: Předpokládejme, že systém má m registrů R0,R^,...,fíA7?_1 a že Xj(t) označuje obsah registru fí, v čase t. Nechť je dále na začátku systém ve stavu x(0) = (X|||_1 (0)? Xq(0)) One-time Pad Posouvací registr Generování I Kryptoanalýza Generování Vlastnosti Primitivita Posouvací registr je posloupnost v řadě za sebou následujících registrů, přičemž každý registr může obsahovat pouze číslici 1 (on) nebo 0 (off). Hodinový strojek reguluje chování systému, který pracuje v souladu s následujícími podmínkami: Předpokládejme, že systém má m registrů R0,R^,...,fíA7?_1 a že Xj(t) označuje obsah registru fí, v čase t. Nechť je dále na začátku systém ve stavu x(0) = (X|||_1 (0)? Xq(0)) Pokud X(ř) = (Xm.1(ř),...,Ab(ř))- označuje stav systému v době ř, stav v čase t + 1 je určen vztahV Xj{t + 1) = X/+1 (ř) (0 < / < m - 2), (2.1) Xin_1(ř+1) = ř(X(ř)), (2.2) kde ř je nějaká binární funkce m proměnnýplg., , fl ^ , , , , , t ^^cv One-time Pad Posouvací registr Generování II Kryptoanalýza Generování Vlastnosti Primitivita Pokud je f tvaru A77-1 f = Yl cm-iXi(t) = cmXo(t) e cm^{t) e • • • e ^xm_^t), i=0 mluvíme o lineárním posouvacím registru. One-time Pad Posouvací registr Kryptoanalýza Primitivita Generování II Pokud je f tvaru A77-1 f = Yl cm-iXi(t) = CmXo(t) © Cm^X^t) © • • • © CiX^iíř), /=0 mluvíme o lineárním posouvacím registru. Přitom chování systému je jednoznačně určeno O počátečním stavem X(0) a Q> množinou konstant c-i,..., cm. Budeme vždy předpokládat, že cm ^ 0; jinak bychom mohli pracovat bez registru R0. One-time Pad Posouvací registr Generování III Kryptoanalýza Generování Vlastnosti Primitivita Způsob, jakým lineární systém pracuje, je, že po obdržení signálu každý registr provede dvě věci: (i) Přenese svůj obsah do svého pravého souseda (registr R0 toto provést nemůže, jeho obsah se stane výstupním bitem Zt našeho stroje). (ii) Takové registry Rh pro které je c, = 1 přenesou svůj obsah do čítače, ten je sečte a výsledek přenese do registru Rm-^ ■ Rm-1 Rm-2 Rq output Z, XOR One-time Pad Posouvací registr Generování IV Kryptoanalýza Generování Vlastnosti Primitivita Jakmile je jednou nastaven počáteční vektor, lze posouvací registr považovat za zdroj nekonečné posloupnosti binárních číslic Xo(0),Xo(1),X0(2), One-time Pad Posouvací registr Generování IV Kryptoanalýza Generování Vlastnosti Primitivita Jakmile je jednou nastaven počáteční vektor, lze posouvací registr považovat za zdroj nekonečné posloupnosti binárních číslic Xo(0),X0(1),X0(2),.... Ačkoliv takto vytvořená posloupnost není náhodná, lze ukázat, že má jisté rysy nahodilosti. Navíc ji lze snadno a rychle generovat. Bohužel je však velmi nejistá. One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností I Nejprve uvažujme periodicitu. Nekonečná posloupnost (y, : 0 < / < oc) se nazývá periodická s periodou p, jestliže je p kladné přirozené číslo takové, že y/+p = y, pro všechna / a navíc je p nejmenší kladné přirozené číslo s touto vlastností. One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností I Nejprve uvažujme periodicitu. Nekonečná posloupnost (y, : 0 < / < oc) se nazývá periodická s periodou p, jestliže je p kladné přirozené číslo takové, že y/+p = y, pro všechna / a navíc je p nejmenší kladné přirozené číslo s touto vlastností. Má-li tedy posloupnost (y, : 0 < / < oo) periodu p, můžeme ji psát ve tvaru yo5/i 5/25 • • • 5/p-i j yo5/i 5/25 • • • >/p-i j • • • Jinak řečeno, posloupnost s periodou p je přesně posloupnost opakování konečného bloku délky p. One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností II Vraťme se nyní k posloupnosti určené lineárním posouvacím registrem: předpokládejme, že počáteční vektor X(0) není nulový vektor a že rovnice 2.1 a 2.2 lze přepsat ve tvaru X(ř+1)=CX(ř), (2.3) kde C je matice tvaru Cl c2 03 Cm— 1 Cm 1 0 0 0 0 0 ■ 1 ■ 0 ■ 0 ■ 0 ■ ■ ■ 0 ■ ■ 0 ■ ■ 0 ■ ■ ■ . 1 ■ ■ 0 One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností III Protože jsme předpokládali, že cm = 1 a protože det C = cm = 1, vidíme, že C je regulární matice. Iterováním rovnice 2.3 dostaneme X(ř) = CřX(0). One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností III Protože jsme předpokládali, že cm = 1 a protože det C = cm = 1, vidíme, že C je regulární matice. Iterováním rovnice 2.3 dostaneme X(ř) = CřX(0). Přitom platí Posloupnost vytvořená pomocí lineárního posouvacího registru je periodická a pokud je vytvořena z m registrů, je její maximální perioda 2m - 1. One-time Pad Posouvací registr Kryptoanalýza Generování Vlastnosti Primitivita Vlastnosti vytvořených posloupností IV Protože je C regulární, je i regulární matice C (/ = 0,1,...); přitom je X(0) nenulový vektor a existuje právě 2m - 1 nenulových vektorů délky m. One-time Pad Posouvací registr Kryptoanalýza Generování Vlastnosti Primitivita Vlastnosti vytvořených posloupností IV ^můkazVěty^^^^^^^^^^^^^^^ Protože je C regulární, je i regulární matice C (/ = 0,1,...); přitom je X(0) nenulový vektor a existuje právě 2m - 1 nenulových vektorů délky m. Je-li k = 2m - 1, pak jsou nenulové vektory délky m a tudíž nemohou být všechny různé: One-time Pad Posouvací registr Kryptoanalýza Generování Vlastnosti Primitivita Vlastnosti vytvořených posloupností IV Protože je C regulární, je i regulární matice C (/ = 0,1,...); přitom je X(0) nenulový vektor a existuje právě 2m - 1 nenulových vektorů délky m. Je-li k = 2m - 1, pak jsou X(0), CX(0l (^X(0),..., CkX(0) nenulové vektory délky m a tudíž nemohou být všechny různé: řekněme, že CsX(0) = Cs+řX(0), kde 0 < s < s + ř < 2m - 1. One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností V Důkaz Věty 2.1 - pokračování. Protože existuje C~s, máme X(ř) = CrX(0) = C-sCs+řX(0) = X(0) One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností V Důkaz Věty 2.1 - pokračování. Protože existuje C~s, máme X(ř) = CřX(0) = C-sCs+řX(0) = X(0). Tedy X(r + ř) = Cr+řX(0) = CrCřX(0) = CrX(ř) = CrX(0) = X(r) pro všechna r > 0, a CrX(0) je periodická s periodou nejvýše ř < 2m - 1. One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Vlastnosti vytvořených posloupností V Důkaz Věty 2.1 - pokračování. Protože existuje C~s, máme X(ř) = CrX(0) = C"sCs+rX(0) = X(0) Tedy X(r + ř) = Cr+rX(0) = CCrX(0) = CrX(ř) = CX(0) = X(r) pro všechna r > 0, a CřX(0) je periodická s periodou nejvýše t<2m-J\. Posloupnost vytvořená pomocí lineárního posouvacího registru je tedy periodická. I One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Primitivní polynomy I Definujme charakteristický polynom lineárního posouvacího registru jako polynom m Pm(x) = 1 + C'X'' /=1 s cm ž 0,c/ e {0,1}. One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Primitivní polynomy I Definujme charakteristický polynom lineárního posouvacího registru jako polynom m /=1 S Cm ŕ 0, Cf £{0,1}. Charakteristický polynom je primitivní, jestliže (a) nemá vlastní netriviální dělitele, (b) Pm(x) nedělí polynom xd + 1 pro všechna d < 2m - 1. One-time Pad Posouvací registr Kryptoanalýza Generování Primitivita _ Vlastnosti Primitivní polynomy II i?3 R2 Ri Ro XOR Lineární posouvací registr s charakteristickým polynomem 1 + X + X2 + X4. Následující tvrzení uvedeme bez důkazu. Posloupnost vytvořená pomocí lineárního posouvacího registru z nenulového vstupu má maximální periodu právě tehdy, je-li její charakteristický polynom primitivní Následující tvrzení uvedeme bez důkazu. Posloupnost vytvořená pomocí lineárního posouvacího registru z nenulového vstupu má maximální periodu právě tehdy je-li její charakteristický polynom primitivní Nalezení primitivních polynomů je netriviální úloha moderní algebry. Poznamenejme pouze, že primitivní polynomy existují pro každé n a že jsou tabelovány. One-time Pad Posouvací registr Kryptoanalýza O čem to bude Q Kryptoanalýza lineárních posouvacích registrů • Bloky a díry • Known-plaintext útok One-time Pad Blokv a ( Posouvací registr Kryptoanalýza Known-plaintext útok Můžeme tedy použít lineární posouvací registry k vytvoření pseudonáhodných posloupností pro kryptografické účely. To je laciné, lineární posouvací registry provádí výpočty velmi rychle - co můžeme ještě víc chtít? One-time Pad Blokv a ( Posouvací registr Kryptoanalýza Known-plaintext útok Můžeme tedy použít lineární posouvací registry k vytvoření pseudonáhodných posloupností pro kryptografické účely. To je laciné, lineární posouvací registry provádí výpočty velmi rychle - co můžeme ještě víc chtít? Nelze popřít, že posloupnosti vytvořené pomocí lineárních posouvacích registrů mají vynikající statistické vlastnosti; a to platí dokonce pro posloupnosti, které vzniknou z relativně krátkých lineárních posouvacích registrů. One-time Pad Blokv a ( Posouvací registr Kryptoanalýza Known-plaintext útok Můžeme tedy použít lineární posouvací registry k vytvoření pseudonáhodných posloupností pro kryptografické účely. To je laciné, lineární posouvací registry provádí výpočty velmi rychle - co můžeme ještě víc chtít? Nelze popřít, že posloupnosti vytvořené pomocí lineárních posouvacích registrů mají vynikající statistické vlastnosti; a to platí dokonce pro posloupnosti, které vzniknou z relativně krátkých lineárních posouvacích registrů. Ale z kryptologického pohledu mají tyto posloupnosti mimořádně pochybný charakter. To je důsledkem toho, že v případě known-plaintext útoku mu nejsou schopny odolat. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry II Known-plaintext útok Definujme blok délky t jako posloupnost tvaru 011... 10 obsahující právě t jedniček. Dírou délky t je posloupnost tvaru 100... 01 obsahující právě t nul. One-time Pad Blokv a ( Posouvací registr Kryptoanalýza Known-plaintext útok Definujme blok délky t jako posloupnost tvaru 011... 10 obsahující právě t jedniček. Dírou délky t je posloupnost tvaru 100... 01 obsahující právě t nul. Platí následující výsledek. Má-// lineární posouvací registr s m registry maximální periodu 2m - 1, mají pak výsledné posloupnosti délky 2m - 1 následující vlastnosti: One-time Pad Blokv a ( Posouvací registr Kryptoanalýza Known-plaintext útok Definujme blok délky t jako posloupnost tvaru 011... 10 obsahující právě t jedniček. Dírou délky t je posloupnost tvaru 100... 01 obsahující právě t nul. Platí následující výsledek. Má-// lineární posouvací registr s m registry maximální periodu 2m - 1, mají pak výsledné posloupnosti délky 2m - 1 následující vlastnosti: (a) obsahuje právě 2A7?_1 - 1 nul a2A7?_1 jedniček; One-time Pad Blokv a ( Posouvací registr Kryptoanalýza Known-plaintext útok Definujme blok délky t jako posloupnost tvaru 011... 10 obsahující právě t jedniček. Dírou délky t je posloupnost tvaru 100... 01 obsahující právě t nul. Platí následující výsledek. Věta 3.1 ■ Má-// lineární posouvací registr s m registry maximální periodu 2m - 1, mají pak výsledné posloupnosti délky 2m - 1 následující vlastnosti: (a) obsahuje právě 2A7?_1 - 1 nul a2A7?_1 jedniček; (b) obsahuje pro všechna t taková, ze 1 < t < m-2, 2m~t~2 bloků délky t a stejný počet děr délky t. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext utok (a): Stav lineárního posouvacího registru lze v každém okamžiku jednoznačně popsat přirozeným číslem z intervalu [1 ..2m - 1]: stačí vzít příslušnou část výstupní posloupnosti. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext utok (a): Stav lineárního posouvacího registru lze v každém okamžiku jednoznačně popsat přirozeným číslem z intervalu [1 ..2m - 1]: stačí vzít příslušnou část výstupní posloupnosti. Protože se všechna nenulová čísla z intervalu [1 ..2m - 1] musí vyskytnout jako stavy v cyklu maximální délky, výsledek okamžitě dostaneme výsledek (a) spočtením sudých a lichých čísel v této množině. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext utok (a) : Stav lineárního posouvacího registru lze v každém okamžiku jednoznačně popsat přirozeným číslem z intervalu [1 ..2m - 1]: stačí vzít příslušnou část výstupní posloupnosti. Protože se všechna nenulová čísla z intervalu [1 ..2m - 1] musí vyskytnout jako stavy v cyklu maximální délky, výsledek okamžitě dostaneme výsledek (a) spočtením sudých a lichých čísel v této množině. (b) : Abychom dokázali (b), poznamenejme, že běh typu 011... 10 obsahující právě t jedniček se může vyskytnout jako součást výstupu právě tehdy, když v nějaké části výpočtu je stav lineárního posouvacího registru 011 ... 10x-|X2 • • .xm_t_2, kdex, g {0,1}. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry IV Known-plaintext útok Důkaz Věty 3.1 - pokračování. Protože máme právě 2m~t~2 stavů tohoto tvaru a protože každý stav je realizován v nějakém okamžiku výpočtu vzhledem k tomu, že lineární posouvací registr má maximální periodu, výsledek (b) pro bloky platí. Zaměníme-li 0 a 1, dostáváme výsledek (b) pro díry. I One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok 1 Vraťme se nyní k dešifrování. Je-li M = M1M2 ... zpráva složená z binárních číslic, a je-li Z = Z1Z2... posloupnost vyprodukovaná lineárním posouvacím registrem, pak kryptogram C je posloupnost C = C-| C2 • • •, kde d = Mi + Z, (mod 2) (1 < / < 00). (3.1) One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok II Jsou-li tedy a C, známy, lze Z, získat triviálně jako Zj = Mi + Xj (mod 2) (1 < / < oo). (3.2) One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok II Jsou-li tedy M, a C, známy, lze Z, získat triviálně jako Z,- = Mi + Xj (mod 2) (1 < / < oo). (3.2) Uvažme nyní lineární posouvací registr s m registry a koeficienty Ci, cfe,..., cm. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok II Jsou-li tedy M, a C, známy, lze Z, získat triviálně jako Z, = Mi + Xj (mod 2) (1 < / < oo). (3.2) Uvažme nyní lineární posouvací registr s m registry a koeficienty Ci, cfe,..., cm. Jakmile zná nepřítel nějakých 2 m za sebou následujících členů Xj výsledné posloupnosti, je schopen najít tyto koeficienty C-|, C2, . . . , C/77. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok III Totiž odpovídající systém lineárních rovnic má tvar Zm+2 zm-\ *-m-2 Zm-\ zm Z2m- -3 Z2m- -4 Z2m- -5 Z2m- -2 Z2m- -3 Z2m- 4 Z2m- -1 Z2m- -2 Z2m- -3 z2 z3 z4 Zm z3 -m-2 zn Zm-i Cl Zm+J\ c2 Zm+2 c3 Zm+3 CA77-2 Z2m-2 Zim-\ Cm Z2m (3-3) One-time Pad Posouvací registr Kryptoanalýza Known-plaintext útok III Known-plaintext útok Totiž odpovídající systém lineárních rovnic má tvar zm-\ *-m-2 Zm-\ Z2m- -3 Z2m- -4 Z2m- -5 Z2m- -2 Z2m- -3 Z2m- 4 Z2m- -1 Z2m- -2 Z2m- -3 z2 Z4 Zm z3 -A77-2 Zm-i Cl CA77-2 C/77 Zm+2 Zm+3 Z2m-2 ^2/77—1 Z2m (3-3) To pak plně určuje šifrovací systém v případě, že matice na levé straně rovnice (3.3) je invertibilní a tudíž platí následující věta. One-time Pad Posouvací registr Known-plaintext útok IV Kryptoanalýza Bloky a díry Known-plaintext útok Je-li posloupnost bitů Z = Z1Z2 ... generována regulárním lineárním posouvacím registrem R délky m a neexistuje-li kratší lineární posouvací registr generující tuto posloupnost, pak je charakteristický polynom lineárního posouvacího registru R jednoznačně určen 2m za sebou jdoucími členy této posloupnosti. Je-li posloupnost bitů Z = Z1Z2 ... generována regulárním lineárním posouvacím registrem R délky m a neexistuje-li kratší lineární posouvací registr generující tuto posloupnost, pak je charakteristický polynom lineárního posouvacího registru R jednoznačně určen 2m za sebou jdoucími členy této posloupnosti. Důkaz. Stačí ověřit že matice A na levé straně rovnice (3.3) je invertibilní. Předpokládejme opak. Pak nutně její sloupce jsou lineárně závislé. Přitom sloupce nejsou nic jiného než stavy systému: X(0), X(1),..., X(a7? - 1), máme tedy lineární kombinaci ™-1 (3.4) One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok V Přitom koeficienty b\ e {0,1} nejsou všechny nulové. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok V Přitom koeficienty b\ e {0,1} nejsou všechny nulové. Položme k = max{i: b\ ^ 0}. Pak k < m - 1 a nutně (protože pracujeme mod 2) máme /c-1 5>/X(/) = X(/c). (3.5) One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok V Přitom koeficienty b\ e {0,1} nejsou všechny nulové. Položme k = max{i: b\ ^ 0}. Pak k < m - 1 a nutně (protože pracujeme mod 2) máme /c-1 5>/X(/) = X(/c). (3.5) /=o Buď nyní C matice lineárního posouvacího registru R. Pak pro každé t > 0 platí /c-1 /c-1 X(ř + k) = CřX(/c) = J] &/CřX(/) = W' + 0- (3-6) One-time Pad Posouvací registr Kryptoanalýza Known-plaintext útok Speciálně tedy pro ř > 1 platí /c-1 One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok VI Speciálně tedy pro ř > 1 platí /c-1 Zt+k = Y,biZt+i. (3.7) /=o Tudíž posloupnost Z = Z|Z2... je generována lineárním posouvacím registrem R' délky k (přičemž příslušný charakteristický polynom lineárního posouvacího registru R' má koeficienty b0,..., ). One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok VI Speciálně tedy pro ř > 1 platí /c-1 Zt+k = Y,biZt+i. (3.7) /=o Tudíž posloupnost Z = Z|Z2... je generována lineárním posouvacím registrem R' délky k (přičemž příslušný charakteristický polynom lineárního posouvacího registru R' má koeficienty b0,..., b^). To je ale spor s minimalitou m. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok VI Speciálně tedy pro ř > 1 platí /c-1 Zt+k = Y,biZt+i. (3.7) /=o Tudíž posloupnost Z = Z|Z2... je generována lineárním posouvacím registrem R' délky k (přičemž příslušný charakteristický polynom lineárního posouvacího registru R' má koeficienty b0,..., b^). To je ale spor s minimalitou m. Poznamenejme, že výše uvedené je překvapující výsledek. Totiž to znamená, že můžeme posloupnost více než milionu bitů (přesněji 1048575 = 220 - 1 bitů) rekonstruovat ze znalosti pouhých 40 výstupních bitů. One-time Pad Posouvací registr Known-plaintext útok VII Důsledek 3.3 Kryptoanalýza Bloky a díry Known-plaintext útok Užití posloupností vytvořených pomocí lineárního posouvacího registru není bezpečné proti known-plaintext útoku. One-time Pad Posouvací registr Known-plaintext útok VII Důsledek 3.3 Kryptoanalýza Bloky a díry Known-plaintext útok Užití posloupností vytvořených pomocí lineárního posouvacího registru není bezpečné proti known-plaintext útoku. Důkaz. Předpokládejme, že odesilatel Alice a příjemce Bob používají proudovou šifru, jejímž klíčem je výstup z lineárního posouvacího registru R délky m. Nechť útočník Eve zná část zdrojového textu o délce 2m, řekněme , M/+2, ..., Mi+2m-Pokud Eve zachytí odpovídající část šifrového textu C/+1, C/+2, ..., C/+2A77, pak samozřejmě zná i odpovídající část klíče Z/+1, ■ ■ ■ 5 Z/+2A77- One-time Pad Posouvací registr Known-plaintext útok VII Důsledek 3.3 Kryptoanalýza Bloky a díry Known-plaintext útok Užití posloupností vytvořených pomocí lineárního posouvacího registru není bezpečné proti known-plaintext útoku. Důkaz. Předpokládejme, že odesilatel Alice a příjemce Bob používají proudovou šifru, jejímž klíčem je výstup z lineárního posouvacího registru R délky m. Nechť útočník Eve zná část zdrojového textu o délce 2m, řekněme , M/+2, ..., Mi+2m-Pokud Eve zachytí odpovídající část šifrového textu C/+1, C/+2, ..., C/+2a7?, pak samozřejmě zná i odpovídající část klíče Z/+1, Z/+2, ..., Z/+2a7?. Dle předchozí věty je tedy Eve schopna určit koeficienty charakteristického polynomu lineárního posouvacího registru R, tj. zkonstruovat R. Může tedy, vezme-li za počáteční základ Z/+1, Z/+2, ..., Z/+2a7? vygenerovat všechny předchozí i následující členy klíče. Eve je tedy schopna dešifrovat zbytek zprávy. ,n>,== One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok VIII Chceme-li zachovat hezké vlastnosti lineárních registrů a zároveň zajistit větší stupeň bezpečnosti, použijeme v rovnici 2.2 nelineární funkci. Skutečně je tomu tak, že většina dnes používaných algoritmů je založena na nelineárních posouvacích registrech, ačkoliv bychom neměli zapomenout na DES případně Triple-DES. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok VIII Chceme-li zachovat hezké vlastnosti lineárních registrů a zároveň zajistit větší stupeň bezpečnosti, použijeme v rovnici 2.2 nelineární funkci. Skutečně je tomu tak, že většina dnes používaných algoritmů je založena na nelineárních posouvacích registrech, ačkoliv bychom neměli zapomenout na DES případně Triple-DES. Zvláště rafinovaná metoda je tzv. shrinking generátor. V tomto případě použijeme dva lineární posouvací registry, které pracují ve stejném taktu. Budeme se řídit předpisem, že použijeme právě ty výstupní bity druhého lineárního posouvacího registru, pro které je zároveň příslušná hodnota prvního lineárního posouvacího registru rovná 1. Položme si následující otázku: Lze rozumně měřit kryptologickou kvalitu posloupnosti nul a jedniček? Viděli jsme, že se k tomuto perioda sotva hodí. = One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok IX Proto se používá pojem lineární složitosti dané posloupnosti, jakožto nejkratší délka takového lineárního posouvacího registru, že daná posloupnost je vytvořena jakožto část výstupu tohoto lineárního posouvacího registru. Čím větší je lineární složitosti dané posloupnosti, tím lépe se tato posloupnost hodí pro kryptografické účely. Například metoda shrinking generator nám garantuje vysokou lineární složitost. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext utok Known-plaintext útok IX Proto se používá pojem lineární složitosti dané posloupnosti, jakožto nejkratší délka takového lineárního posouvacího registru, že daná posloupnost je vytvořena jakožto část výstupu tohoto lineárního posouvacího registru. Čím větší je lineární složitosti dané posloupnosti, tím lépe se tato posloupnost hodí pro kryptografické účely. Například metoda shrinking generátor nám garantuje vysokou lineární složitost. Udělejme si představu o náročnosti hádání klíče. Pravděpodobnost uhodnutí 64-bitového klíče je 1 /264, což je samozřejmě kladné číslo. Porovnejme si toto číslo s jinými velikostmi. One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok X Připomeňme, že 264 « 1,84-1019. Je tedy uhodnutí 64-bitového klíče stejně hodnotné, jakožto vybrání předem určeného prvku z množiny o 10 trilionech prvků, což je více než všech možných partnerských párů na zeměkouli (v současnosti nás je asi 6 • 109). One-time Pad Posouvací registr Kryptoanalýza Bloky a díry Known-plaintext útok Known-plaintext útok X Připomeňme, že 264 « 1,84-1019. Je tedy uhodnutí 64-bitového klíče stejně hodnotné, jakožto vybrání předem určeného prvku z množiny o 10 trilionech prvků, což je více než všech možných partnerských párů na zeměkouli (v současnosti nás je asi 6 • 109). Podobně počet všech 256-bitových klíčů lze odhadout jako 2256 « 1,15-1077, což je číslo větší než počet elementárních částic v našem vesmíru. Je tedy jasné, že útok hrubou silou nám bude k ničemu.