Nervová kryptografie - Neural cryptography

Nervová kryptografie je pobočkou kryptografie věnovaný analýze aplikace stochastický zejména algoritmy umělá neuronová síť algoritmy, pro použití v šifrování a dešifrování.

Definice

Umělé neuronové sítě jsou dobře známé pro svou schopnost selektivně prozkoumat prostor řešení daného problému. Tato funkce nachází přirozené místo v oblasti aplikace dešifrování. Neuronové sítě zároveň nabízejí nový přístup k algoritmům šifrování útoků založeným na principu, že jakoukoli funkci lze reprodukovat neuronovou sítí, což je účinný osvědčený výpočetní nástroj, který lze použít k nalezení inverzní funkce jakéhokoli kryptografického algoritmus.

Myšlenky vzájemného učení, sebevzdělávání a stochastického chování neuronových sítí a podobných algoritmů lze použít pro různé aspekty kryptografie, například kryptografie veřejného klíče, řešení klíč distribuční problém pomocí vzájemné synchronizace neuronových sítí, hashování nebo generace pseudonáhodná čísla.

Další myšlenkou je schopnost neurální sítě oddělit prostor v nelineárních částech pomocí „zkreslení“. Poskytuje různé pravděpodobnosti aktivace neuronové sítě. To je velmi užitečné v případě kryptanalýzy.

K návrhu stejné oblasti výzkumu se používají dvě jména: Neuro-kryptografie a neurální kryptografie.

První práce, která je na toto téma známa, lze vysledovat v roce 1995 v diplomové práci v oboru IT.

Aplikace

V roce 1995 použil Sebastien Dourlens neuronové sítě k dešifrování DES umožněním sítím naučit se invertovat S-tabulky DES. Předpětí v DES studovalo pomocí diferenciální kryptoanalýzy od Adi Shamir je zvýrazněno. Experiment ukazuje, že lze najít přibližně 50% klíčových bitů, což umožňuje nalezení celého klíče v krátké době. Hardwarová aplikace s více mikrořadiči byla navržena kvůli snadné implementaci vícevrstvých neuronových sítí v hardwaru.
Jeden příklad protokolu veřejného klíče uvádí Khalil Shihab. Popisuje dešifrovací schéma a vytváření veřejného klíče, které jsou založeny na a zpětná propagace nervová síť. Schéma šifrování a proces vytváření soukromého klíče jsou založeny na booleovské algebře. Tato technika má výhodu malé časové a paměťové složitosti. Nevýhodou je vlastnost algoritmů zpětného šíření: z důvodu velkých tréninkových sad je fáze učení neuronové sítě velmi dlouhá. Proto je použití tohoto protokolu zatím pouze teoretické.

Protokol pro výměnu neurálních klíčů

Nejpoužívanější protokol pro výměnu klíčů mezi dvěma stranami A a B v praxi je Výměna klíčů Diffie – Hellman protokol. Výměna neurálních klíčů, která je založena na synchronizaci dvou stromových paritních strojů, by měla být bezpečnou náhradou za tuto metodu. Synchronizace těchto dvou strojů je podobná synchronizaci dvou chaotických oscilátorů v chaos komunikace.

Paritní stroj na stromy

Stromový paritní stroj

Paritní stroj stromů je speciální typ vícevrstvých dopředná neuronová síť.

Skládá se z jednoho výstupního neuronu, K. skryté neurony a K.×N vstupní neurony. Vstupy do sítě mají tři hodnoty:

${displaystyle x_ {ij} vlevo {-1,0, + 1 světlo}}$

Váhy mezi vstupem a skrytými neurony mají hodnoty:

${displaystyle w_ {ij} vlevo {-L, ..., 0, ..., + světlo}}$

Výstupní hodnota každého skrytého neuronu se vypočítá jako součet všech násobení vstupních neuronů a těchto vah:

${displaystyle sigma _ {i} = operatorname {sgn} (součet _ {j = 1} ^ {N} w_ {ij} x_ {ij})}$

Signum je jednoduchá funkce, která vrací −1,0 nebo 1:

${displaystyle operatorname {sgn} (x) = {egin {cases} -1 & {ext {if}} x <0, 0 & {ext {if}} x = 0, 1 & {ext {if}} x> 0 .end {případů}}}$

Pokud je skalární součin 0, je výstup skrytého neuronu mapován na -1, aby byla zajištěna binární výstupní hodnota. Výstup neuronové sítě se poté vypočítá jako násobení všech hodnot produkovaných skrytými prvky:

${displaystyle au = prod _ {i = 1} ^ {K} sigma _ {i}}$

Výstup stroje na paritu stromů je binární.

Protokol

Každá strana (A a B) používá svůj vlastní stromový paritní stroj. V těchto krocích je dosaženo synchronizace stromových paritních strojů

1. Inicializujte náhodné hodnoty hmotnosti
2. Proveďte tyto kroky, dokud nebude dosaženo úplné synchronizace
   1. Generujte náhodný vstupní vektor X
   2. Vypočítejte hodnoty skrytých neuronů
   3. Vypočítejte hodnotu výstupního neuronu
   4. Porovnejte hodnoty obou stromových paritních strojů
      1. Výstupy jsou stejné: přejděte na 2.1
      2. Výstupy jsou různé: jedno z vhodných pravidel učení se aplikuje na váhy

Po dosažení úplné synchronizace (váhy w_ij oba stromové paritní stroje jsou stejné), A a B mohou používat své váhy jako klíče.
Tato metoda je známá jako obousměrné učení.
Jedno z následujících pravidel učení^[1] lze použít pro synchronizaci:

• Hebbské pravidlo učení:

${displaystyle w_ {i} ^ {+} = g (w_ {i} + sigma _ {i} x_ {i} théta (sigma _ {i} au) théta (au ^ {A} au ^ {B})) }$

• Protib hebské pravidlo učení:

${displaystyle w_ {i} ^ {+} = g (w_ {i} -sigma _ {i} x_ {i} Theta (sigma _ {i} au) Theta (au ^ {A} au ^ {B})) }$

• Náhodná procházka:

${displaystyle w_ {i} ^ {+} = g (w_ {i} + x_ {i} Theta (sigma _ {i} au) Theta (au ^ {A} au ^ {B}))}$

Kde:

${displaystyle Theta (a, b) = 0}$ -li ${displaystyle aeq b}$ v opačném případě ${displaystyle Theta (a, b) = 1}$

A:

${displaystyle g (x)}$ je funkce který udržuje ${displaystyle w_ {i}}$ v dosahu ${displaystyle {-L, -L + 1, ..., 0, ..., L-1, L}}$

Útoky a bezpečnost tohoto protokolu

Při každém útoku se považuje, že útočník E může odposlouchávat zprávy mezi stranami A a B, ale nemá příležitost je změnit.

Hrubou silou

K zajištění útoku hrubou silou musí útočník vyzkoušet všechny možné klíče (všechny možné hodnoty vah wij). Podle K. skryté neurony, K.×N vstupní neurony a hranice vah L, to dává (2L + 1)^KN možnosti. Například konfigurace K. = 3, L = 3 a N = 100 nám dává 3 * 10²⁵³ klíčové možnosti, které znemožňují útok současným výkonem počítače.

Učení pomocí vlastního stromového paritního stroje

Jeden ze základních útoků může poskytnout útočník, který vlastní stejný stromový paritní stroj jako strany A a B. Chce synchronizovat svůj stromový paritní stroj s těmito dvěma stranami. V každém kroku jsou možné tři situace:

1. Výstup (A) ≠ Výstup (B): Žádná ze stran neaktualizuje své váhy.
2. Výstup (A) = Výstup (B) = Výstup (E): Všechny tři strany aktualizují váhy ve svých stromových paritních strojích.
3. Výstup (A) = Výstup (B) ≠ Výstup (E): Strany A a B aktualizovat své stromové paritní stroje, ale útočník to nemůže udělat. Kvůli této situaci je jeho učení pomalejší než synchronizace stran A a B.

Bylo prokázáno, že synchronizace dvou stran je rychlejší než učení útočníka. Lze jej zlepšit zvýšením synaptické hloubky L neurální sítě. To dává tomuto protokolu dostatečné zabezpečení a útočník může klíč zjistit jen s malou pravděpodobností.

Další útoky

U konvenčních kryptografických systémů můžeme zlepšit zabezpečení protokolu zvýšením délky klíče. V případě neurální kryptografie ji vylepšujeme zvětšením synaptické hloubky L neuronových sítí. Změna tohoto parametru exponenciálně zvyšuje náklady na úspěšný útok, zatímco úsilí pro uživatele roste polynomiálně. Proto narušení zabezpečení výměny neurálních klíčů patří do třídy složitosti NP.

Alexander Klimov, Anton Mityaguine a Adi Shamir říkají, že původní schéma neurální synchronizace lze prolomit nejméně třemi různými útoky - geometrickou analýzou, pravděpodobnostní analýzou a použitím genetických algoritmů. I když je tato konkrétní implementace nejistá, myšlenky chaotické synchronizace by mohly potenciálně vést k bezpečné implementaci.^[2]

Permutační paritní stroj

Parmiční permutační stroj je binární variantou parního stroje se stromy.^[3]

Skládá se z jedné vstupní vrstvy, jedné skryté vrstvy a jedné výstupní vrstvy. Počet neuronů ve výstupní vrstvě závisí na počtu skrytých jednotek K. Každý skrytý neuron má N binárních vstupních neuronů:

${displaystyle x_ {ij} vlevo {0,1ight}}$

Váhy mezi vstupem a skrytými neurony jsou také binární:

${displaystyle w_ {ij} vlevo {0,1ight}}$

Výstupní hodnota každého skrytého neuronu se vypočítá jako součet všech výlučných disjunkcí (výlučných nebo) vstupních neuronů a těchto vah:

${displaystyle sigma _ {i} = heta _ {N} (součet _ {j = 1} ^ {N} w_ {ij} oplus x_ {ij})}$

(⊕ znamená XOR).

Funkce ${displaystyle heta _ {N} (x)}$ je prahová funkce, která vrací 0 nebo 1:

${displaystyle heta _ {N} (x) = {egin {cases} 0 & {ext {if}} xleq N / 2, 1 & {ext {if}} x> N / 2.end {cases}}}$

Výstup neuronové sítě se dvěma nebo více skrytými neurony lze vypočítat jako exkluzivní nebo z hodnot vytvořených skrytými prvky:

${displaystyle au = igoplus _ {i = 1} ^ {K} sigma _ {i}}$

Jsou možné i další konfigurace výstupní vrstvy pro K> 2.^[3]

Tento stroj se ukázal být dostatečně robustní proti některým útokům^[4] mohl by být použit jako kryptografický prostředek, ale ukázalo se, že je zranitelný pravděpodobnostním útokem.^[5]

Zabezpečení proti kvantovým počítačům

A kvantový počítač je zařízení, které pro výpočet používá kvantové mechanismy. V tomto zařízení jsou data uložena jako qubits (kvantové binární číslice). To dává kvantovému počítači ve srovnání s běžným počítačem příležitost vyřešit v krátké době složité problémy, např. problém diskrétního logaritmu nebo faktorizace. Kvůli této vlastnosti jsou hledány algoritmy, které nejsou založeny na žádném z těchto problémů s teorií čísel.

Protokol pro výměnu neurálních klíčů není založen na žádné teorii čísel. Je založen na rozdílu mezi jednosměrnou a obousměrnou synchronizací neuronových sítí. Proto by něco jako protokol výměny neurálních klíčů mohlo vést k potenciálně rychlejším schémat výměny klíčů.^[2]

Viz také

• Nervová síť
• Stochastická neurální síť
• Shorův algoritmus

Reference

• Neuro-kryptografie 1995 - První definice neurokryptografie (AI Neural-Cryptography) použitá pro kryptoanalýzu DES od Sebastiena Dourlense, Francie.
• Neurální kryptografie - Popis jednoho druhu neurální kryptografie na internetu Univerzita ve Würzburgu, Německo.
• Kinzel, W .; Kanter, I. (2002). "Neurální kryptografie". Sborník příspěvků z 9. mezinárodní konference o zpracování neurálních informací. ICONIP '02. str. 1351–1354. arXiv:cond-mat / 0208453. doi:10.1109 / ICONIP.2002.1202841. - Jeden z předních článků, které zavádějí koncept používání synchronizovaných neuronových sítí k dosažení systému ověřování pomocí veřejného klíče.
• Li, Li-Hua; Lin, Luon-Chang; Hwang, Min-Shiang (listopad 2001). Msgstr "Schéma vzdáleného ověřování hesla pro architekturu více serverů pomocí neuronových sítí". Transakce IEEE na neuronových sítích. 12 (6): 1498–1504. doi:10.1109/72.963786. ISSN  1045-9227. PMID  18249979. - Možná praktická aplikace neurální kryptografie.
• Klimov, Alexander; Mityagin, Anton; Shamir, Adi (2002). „Analýza neurální kryptografie“ (PDF). Pokroky v kryptologii. ASIACRYPT 2002. LNCS. 2501. 288–298. doi:10.1007/3-540-36178-2_18. ISSN  0302-9743. Citováno 2017-11-15. - Analýza neurální kryptografie obecně a se zaměřením na slabost a možné útoky při použití synchronizovaných neuronových sítí.
• Neurální synchronizace a kryptografie - Andreas Ruttor. Disertační práce, Bayerische Julius-Maximilians-Universität Würzburg, 2006.
• Ruttor, Andreas; Kinzel, Wolfgang; Naeh, Rivka; Kanter, Ido (březen 2006). "Genetický útok na neurální kryptografii". Fyzický přehled E. 73 (3): 036121. arXiv:cond-mat / 0512022. Bibcode:2006PhRvE..73c6121R. doi:10.1103 / PhysRevE.73.036121. ISSN  1539-3755. PMID  16605612.
• Khalil Shihab (2006). „Backpropagation neurální síť pro zabezpečení počítačové sítě“ (PDF). Journal of Computer Science 2: 710–715. Archivovány od originál (PDF) dne 12.7.2007.