NTRUEncrypt - NTRUEncrypt

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (duben 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The NTRUEncrypt kryptosystém veřejného klíče, také známý jako NTRU šifrovací algoritmus, je na mřížce alternativa k RSA a ECC a je založen na nejkratší vektorový problém v mřížce (o které není známo, že by byla rozbitná pomocí kvantové počítače ).

Spoléhá se na předpokládanou obtížnost factoring určité polynomy ve zkráceném stavu polynomiální kruh do kvocientu dvou polynomů, které mají velmi malé koeficienty. Prolomení kryptosystému silně souvisí, i když není ekvivalentní, s algoritmickým problémem mřížková redukce v některých mříže. K zmaření některých publikovaných útoků je nutný pečlivý výběr parametrů.

Protože šifrování i dešifrování používají pouze jednoduché polynomiální násobení, jsou tyto operace ve srovnání s jinými asymetrickými šifrovacími schématy, jako je RSA, velmi rychlé. ElGamal a kryptografie eliptické křivky. NTRUEncrypt však dosud neprošel srovnatelným množstvím kryptografické analýzy v nasazené formě.

Příbuzný algoritmus je NTRUSign digitální podpis algoritmus.

Operace NTRU jsou konkrétně založeny na objektech ve zkráceném polynomiálním kruhu ${ displaystyle R = mathbb {Z} [X] / (X ^ {N} -1)}$ s konvolučním násobením a všechny polynomy v kruhu mají celé číslo koeficienty a stupeň nanejvýš N-1:

${ displaystyle { textbf {a}} = a_ {0} + a_ {1} X + a_ {2} X ^ {2} + cdots + a_ {N-2} X ^ {N-2} + a_ {N-1} X ^ {N-1}}$

NTRU je ve skutečnosti parametrizovaná rodina kryptosystémů; každý systém je specifikován třemi celočíselnými parametry (N, str, q), které představují maximální stupeň ${ displaystyle N-1}$ pro všechny polynomy ve zkráceném kruhu R, malý modul, respektive velký modul, kde se předpokládá, že N je primární, q je vždy větší než str, a str a q jsou coprime; a čtyři sady polynomů ${ displaystyle { mathcal {L}} _ {f}, { mathcal {L}} _ {g}, { mathcal {L}} _ {m}}$ a ${ displaystyle { mathcal {L}} _ {r}}$ (polynomická část soukromého klíče, polynom pro generování veřejného klíče, zprávy a oslepující hodnoty), maximálně všech stupňů ${ displaystyle N-1}$.

Dějiny

Kryptosystém veřejného klíče NTRUEncrypt je relativně nový kryptosystém. První verzi systému, který se jednoduše nazýval NTRU, vyvinuli kolem roku 1996 tři matematici (Jeffrey Hoffstein, Jill Pipher, a Joseph H. Silverman ). V roce 1996 tito matematici společně s Daniel Lieman založili společnost NTRU Cryptosystems, Inc. a dostali patent^[1] (nyní vypršela platnost) na kryptosystému.

Během posledních deseti let lidé pracovali na zdokonalování kryptosystému. Od první prezentace kryptosystému byly provedeny některé změny, které zlepšily jak výkon systému, tak jeho bezpečnost. Většina vylepšení výkonu byla zaměřena na zrychlení procesu. Do roku 2005 lze nalézt literaturu, která popisuje selhání dešifrování NTRUEncrypt. Pokud jde o zabezpečení, od první verze NTRUEncrypt byly zavedeny nové parametry, které se zdají být bezpečné pro všechny aktuálně známé útoky a přiměřené zvýšení výpočetního výkonu.

Nyní je systém plně akceptován podle standardů IEEE P1363 podle specifikací pro kryptografii veřejného klíče založenou na mřížce (IEEE P1363.1 Z důvodu rychlosti kryptosystému veřejného klíče NTRUEncrypt (viz http://bench.cr.yp.to pro srovnávací výsledky) a jeho nízké využití paměti (viz níže )^{[pochybný – diskutovat]}, lze jej použít v aplikacích, jako jsou mobilní zařízení a Čipové karty V dubnu 2011 byl NTRUEncrypt přijat jako standard X9,98 pro použití v odvětví finančních služeb.^[2]

Generování veřejného klíče

Odeslání tajné zprávy od Alice Bobovi vyžaduje vygenerování veřejného a soukromého klíče. Veřejný klíč zná Alice i Bob a soukromý klíč zná pouze Bob. Pro vygenerování dvojice klíčů dva polynomy F a G, s mírou maximálně ${ displaystyle N-1}$ a s koeficienty v {-1,0,1} jsou povinné. Mohou být považovány za reprezentace zbytkových tříd polynomů modulo ${ displaystyle X ^ {N} -1}$ v R. Polynom ${ displaystyle { textbf {f}} v L_ {f}}$ musí splňovat další požadavek, že inverze modulo q a modulo str (počítáno pomocí Euklidovský algoritmus ) existují, což znamená, že ${ displaystyle { textbf {f}} cdot { textbf {f}} _ {p} = 1 { pmod {p}}}$ a ${ displaystyle { textbf {f}} cdot { textbf {f}} _ {q} = 1 { pmod {q}}}$ musí držet. Takže když je vyvolený F není invertibilní, Bob se musí vrátit a zkusit jiný F.

Oba F a ${ displaystyle mathbf {f} _ {p}}$ (a ${ displaystyle g}$) jsou Bobův soukromý klíč. Veřejný klíč h je generováno počítáním množství

${ displaystyle { textbf {h}} = p { textbf {f}} _ {q} cdot { textbf {g}} { pmod {q}}.}$

Příklad: V tomto příkladu jsou parametry (N, str, q) bude mít hodnoty N = 11, str = 3 a q = 32 a tedy polynomy F a G jsou stupně nanejvýš 10. Parametry systému (N, str, q) jsou známy všem. Polynomy jsou vybrány náhodně, takže předpokládejme, že jsou reprezentovány

${ displaystyle { textbf {f}} = - 1 + X + X ^ {2} -X ^ {4} + X ^ {6} + X ^ {9} -X ^ {10}}$

${ displaystyle { textbf {g}} = - 1 + X ^ {2} + X ^ {3} + X ^ {5} -X ^ {8} -X ^ {10}}$

Pomocí euklidovského algoritmu inverzní k F modulo str a modulo qse vypočítá

${ displaystyle { textbf {f}} _ {p} = 1 + 2X + 2X ^ {3} + 2X ^ {4} + X ^ {5} + 2X ^ {7} + X ^ {8} + 2X ^ {9} { pmod {3}}}$

${ displaystyle { textbf {f}} _ {q} = 5 + 9X + 6X ^ {2} + 16X ^ {3} + 4X ^ {4} + 15X ^ {5} + 16X ^ {6} + 22X ^ {7} + 20X ^ {8} + 18X ^ {9} + 30X ^ {10} { pmod {32}}}$

Což vytváří veřejný klíč h (známé Alice i Bobovi) výpočet produktu

${ displaystyle { textbf {h}} = p { textbf {f}} _ {q} cdot { textbf {g}} { pmod {32}} = 8-7X-10X ^ {2} - 12X ^ {3} + 12X ^ {4} -8X ^ {5} + 15X ^ {6} -13X ^ {7} + 12X ^ {8} -13X ^ {9} + 16X ^ {10} { pmod {32}}}$

Šifrování

Alice, která chce Bobovi poslat tajnou zprávu, vloží svou zprávu ve formě polynomu m s koeficienty v ${ displaystyle [-p / 2, p / 2]}$ . V moderních aplikacích šifrování lze polynomial zprávy přeložit v binární nebo ternární reprezentaci. Po vytvoření polynomu zprávy Alice náhodně vybere polynom r s malými koeficienty (neomezenými na množinu {-1,0,1}), to znamená zakrýt zprávu.

S Bobovým veřejným klíčem h zašifrovanou zprávu E je počítáno:

${ displaystyle { textbf {e}} = { textbf {r}} cdot { textbf {h}} + { textbf {m}} { pmod {q}}}$

Tento šifrovací text skrývá Aliciny zprávy a lze jej bezpečně odeslat Bobovi.

Příklad: Předpokládejme, že Alice chce poslat zprávu, kterou lze zapsat jako polynom

${ displaystyle { textbf {m}} = - 1 + X ^ {3} -X ^ {4} -X ^ {8} + X ^ {9} + X ^ {10}}$

a že náhodně zvolená „oslepující hodnota“ může být vyjádřena jako

${ displaystyle { textbf {r}} = - 1 + X ^ {2} + X ^ {3} + X ^ {4} -X ^ {5} -X ^ {7}}$

Šifrový text E , která představuje její zašifrovanou zprávu Bobovi, bude vypadat

${ displaystyle { textbf {e}} = { textbf {r}} cdot { textbf {h}} + { textbf {m}} { pmod {32}} = 14 + 11X + 26X ^ { 2} + 24X ^ {3} + 14X ^ {4} + 16X ^ {5} + 30X ^ {6} + 7X ^ {7} + 25X ^ {8} + 6X ^ {9} + 19X ^ {10} { pmod {32}}}$

Dešifrování

Někdo ví r mohl vypočítat zprávu m hodnocením E - rh; tak r nesmí být Alice odhalena. Kromě veřejně dostupných informací zná Bob i svůj vlastní soukromý klíč. Zde je, jak může získat m: Nejprve znásobí zašifrovanou zprávu E a část jeho soukromého klíče F

${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {q}}}$

Přepsáním polynomů tato rovnice ve skutečnosti představuje následující výpočet:

${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {q}}}$

${ displaystyle { textbf {a}} = { textbf {f}} cdot ({ textbf {r}} cdot { textbf {h}} + { textbf {m}}) { pmod { q}}}$

${ displaystyle { textbf {a}} = { textbf {f}} cdot ({ textbf {r}} cdot p { textbf {f}} _ {q} cdot { textbf {g} } + { textbf {m}}) { pmod {q}}}$

${ displaystyle { textbf {a}} = p { textbf {r}} cdot { textbf {g}} + { textbf {f}} cdot { textbf {m}} { pmod {q }}}$

Místo výběru koeficientů A mezi 0 a q - 1 jsou vybrány v intervalu [-q/2, q/ 2], aby se zabránilo tomu, že původní zpráva nemusí být správně obnovena, protože Alice zvolí souřadnice své zprávy m v intervalu [-str/2, str/ 2]. To znamená, že všechny koeficienty ${ displaystyle p { textbf {r}} cdot { textbf {g}} + { textbf {f}} cdot { textbf {m}}}$ již leží v intervalu [-q/2, q/ 2] protože polynomy r, G, F a m a připravit str všichni mají ve srovnání s malými koeficienty q. To znamená, že všechny koeficienty zůstanou během redukce modulo beze změny q a že původní zpráva může být správně obnovena.

Dalším krokem bude výpočet A modulo str:

${ displaystyle { textbf {b}} = { textbf {a}} { pmod {p}} = { textbf {f}} cdot { textbf {m}} { pmod {p}}}$

protože ${ displaystyle p { textbf {r}} cdot { textbf {g}} { pmod {p}} = 0}$.

Vědět b Bob může použít druhou část svého soukromého klíče ${ displaystyle left ({ textbf {f}} _ {p} right)}$ obnovit Alicinu zprávu vynásobením b a ${ displaystyle { textbf {f}} _ {p}}$

${ displaystyle { textbf {c}} = { textbf {f}} _ {p} cdot { textbf {b}} = { textbf {f}} _ {p} cdot { textbf {f }} cdot { textbf {m}} { pmod {p}}}$

${ displaystyle { textbf {c}} = { textbf {m}} { pmod {p}}}$

protože vlastnost ${ displaystyle { textbf {f}} cdot { textbf {f}} _ {p} = 1 { pmod {p}}}$ bylo požadováno pro ${ displaystyle { textbf {f}} _ {p}}$.

Příklad: Šifrovaná zpráva E od Alice k Bobovi se vynásobí polynomem F

${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {32}} = 3-7X-10X ^ {2} -11X ^ {3} + 10X ^ {4} + 7X ^ {5} + 6X ^ {6} + 7X ^ {7} + 5X ^ {8} -3X ^ {9} -7X ^ {10} { pmod {32}}, }$

kde Bob používá interval [-q/2, q/ 2] místo intervalu [0, q - 1] pro koeficienty polynomu A aby se zabránilo správnému obnovení původní zprávy.

Snížení koeficientů A mod str výsledky v

${ displaystyle { textbf {b}} = { textbf {a}} { pmod {3}} = - XX ^ {2} + X ^ {3} + X ^ {4} + X ^ {5} + X ^ {7} -X ^ {8} -X ^ {10} { pmod {3}}}$

což se rovná ${ displaystyle { textbf {b}} = { textbf {f}} cdot { textbf {m}} { pmod {3}}}$.

V posledním kroku se výsledek znásobí ${ displaystyle { textbf {f}} _ {p}}$ z Bobova soukromého klíče a skončí s původní zprávou m

${ displaystyle { textbf {c}} = { textbf {f}} _ {p} cdot { textbf {b}} = { textbf {f}} _ {p} cdot { textbf {f }} cdot { textbf {m}} { pmod {3}} = { textbf {m}} { pmod {3}}}$

${ displaystyle { textbf {c}} = - 1 + X ^ {3} -X ^ {4} -X ^ {8} + X ^ {9} + X ^ {10}}$

Což je skutečně původní zpráva, kterou Alice poslala Bobovi!

Útoky

Od návrhu NTRU bylo zavedeno několik útoků na kryptosystém veřejného klíče NTRUEncrypt. Většina útoků je zaměřena na úplné přerušení hledání tajného klíče F místo pouhého obnovení zprávy m.Li F je známo, že má velmi málo nenulových koeficientů, které může Eva úspěšně připojit útok hrubou silou vyzkoušením všech hodnot pro F. Když chce Eva vědět, jestli F„Je tajný klíč, jednoduše spočítá ${ displaystyle { textbf {f}} ^ {'} cdot { textbf {h}} { pmod {q}}}$. Pokud má malé koeficienty, může to být tajný klíč Fa Eva může vyzkoušet, jestli F„Je tajný klíč, který jej používá k dešifrování zprávy, kterou si sama zašifrovala. Eva si také mohla vyzkoušet hodnoty G a vyzkoušet, zda ${ displaystyle { textbf {g}} ^ {'} cdot { textbf {h}} ^ {- 1} { pmod {q}}}$má malé hodnoty.

Je možné namontovat a útok typu „setkat se uprostřed“ což je silnější. Může zkrátit čas hledání druhou odmocninou. Útok je založen na vlastnosti, která ${ displaystyle { textbf {f}} cdot { textbf {h}} = p { textbf {g}} { pmod {q}}}$.

Eva chce najít ${ displaystyle { textbf {f}} _ {1}}$ a ${ displaystyle { textbf {f}} _ {2}}$ takhle ${ displaystyle { textbf {f}} = { textbf {f}} _ {1} + { textbf {f}} _ {2}}$ drží a takové, že mají majetek

${ displaystyle left ({ textbf {f}} _ {1} + { textbf {f}} _ {2} right) cdot { textbf {h}} = { textbf {g}} { pmod {q}}}$

${ displaystyle { textbf {f}} _ {1} cdot { textbf {h}} = { textbf {g}} - { textbf {f}} _ {2} cdot { textbf {h }} { pmod {q}}}$

Li F má d něčí a N-d nula, pak Eva vytvoří vše možné ${ displaystyle { textbf {f}} _ {1}}$ a ${ displaystyle { textbf {f}} _ {2}}$ ve kterém mají oba délku ${ displaystyle { frac {1} {2}} N}$ (např. ${ displaystyle { textbf {f}} _ {1}}$ pokrývá ${ displaystyle { frac {1} {2}} N}$ nejnižší koeficienty F a ${ displaystyle { textbf {f}} _ {2}}$ nejvyšší) s d/ 2 jedna. Pak vypočítá ${ displaystyle { textbf {f}} _ {1} cdot { textbf {h}} { pmod {q}}}$ pro všechny ${ displaystyle { textbf {f}} _ {1}}$ a objednává je do košů na základě prvních k souřadnic. Poté vše spočítá ${ displaystyle - { textbf {f}} _ {2} cdot { textbf {h}} { pmod {q}}}$ a objednává je do košů nejen na základě prvních k souřadnic, ale také na základě toho, co se stane, když k prvním k souřadnicím přidáte 1. Pak zkontrolujete koše, které obsahují obě ${ displaystyle { textbf {f}} _ {1}}$ a ${ displaystyle { textbf {f}} _ {2}}$ a uvidíme, jestli ten majetek ${ displaystyle { textbf {f}} _ {1} cdot { textbf {h}} = { textbf {g}} - { textbf {f}} _ {2} cdot { textbf { h}} { pmod {q}}}$ drží.

Mřížkový redukční útok je jednou z nejznámějších a nejpraktičtějších metod prolomení NTRUEncrypt. Svým způsobem to lze přirovnat k faktorizaci modulu v RSA. Nejpoužívanějším algoritmem pro útok na redukci mřížky je Algoritmus Lenstra-Lenstra-Lovász Protože veřejný klíč h obsahuje obojí F a G lze je zkusit získat od h. Je však příliš těžké najít tajný klíč, když jsou zvoleny dostatečně zabezpečené parametry NTRUEncrypt. Útok na snížení mřížky se ztěžuje, pokud se rozměr mřížky zvětší a nejkratší vektor se prodlouží.

The zvolený útok šifrovaného textu je také metoda, která využívá tajný klíč F a výsledkem je totální zlom. Při tomto útoku se Eva pokusí získat svou vlastní zprávu z šifrovacího textu, a tím se pokusí získat tajný klíč. Při tomto útoku nemá Eva s Bobem žádnou interakci.

Jak to funguje:

První Eva vytvoří šifrovací text ${ displaystyle { textbf {e}} = c { textbf {h}} + c}$ takhle ${ displaystyle c = 0 { pmod {p}}, c <{ frac {q} {2}}}$ a ${ displaystyle 2c> { frac {q} {2}}}$ Když Eva zapíše kroky k dešifrování e (aniž by skutečně počítala hodnoty, protože nezná f), najde ${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {q}}}$:

${ displaystyle { textbf {a}} = { textbf {f}} vlevo (c { textbf {h}} + c vpravo) { pmod {q}}}$

${ displaystyle { textbf {a}} = c { textbf {g}} + c { textbf {f}} { pmod {q}}}$

${ displaystyle { textbf {a}} = c { textbf {g}} + c { textbf {f}} - qK}$

Ve kterém ${ displaystyle K = součet k_ {i} x ^ {i}}$ takhle

${ displaystyle k_ {i} = { begin {cases} 1 qquad { text {if the}} i ^ {th} { text {koeficient of}} { textbf {f}} { text {and}} { textbf {g}} { text {is}} 1 - 1 qquad { text {pokud}} i ^ {th} { text {koeficient of}} { textbf {f}} { text {and}} { textbf {g}} { text {is}} -1 0 qquad { text {Jinak}} end {cases}}}$

Příklad:

${ displaystyle { textbf {f}} = - 1 + X + X ^ {2} -X ^ {4} + X ^ {6} + X ^ {9} -X ^ {10}}$

${ displaystyle { textbf {g}} = - 1 + X ^ {2} + X ^ {3} + X ^ {5} -X ^ {8} -X ^ {10}}$

Pak K. se stává ${ displaystyle K = -1 + X ^ {2} -X ^ {10}}$.

Snižování koeficientů polynomů A mod str skutečně snižuje koeficienty ${ displaystyle c { textbf {g}} + c { textbf {f}} - qK { pmod {p}}}$. Po násobení s ${ displaystyle { textbf {f}} _ {p}}$, Eva najde:

${ displaystyle { textbf {m}} = c { textbf {f}} _ {p} cdot { textbf {g}} + c { textbf {f}} _ {p} cdot { textbf {f}} - q { textbf {f}} _ {p} cdot K { pmod {p}}}$

${ displaystyle { textbf {m}} = c { textbf {h}} + c-q { textbf {f}} _ {p} cdot K { pmod {p}}}$

Protože c bylo vybráno jako násobek str, m lze psát jako

${ displaystyle { textbf {m}} = - q { textbf {f}} _ {p} cdot K { pmod {p}}}$

Což znamená, že ${ displaystyle { textbf {f}} = - qK cdot { textbf {m}} ^ {- 1} { pmod {p}}}$.

Teď když F a G mít několik koeficientů, které jsou stejné za stejných faktorů, K. má několik nenulových koeficientů a je tak malý. Vyzkoušením různých hodnot K. útočník se může vzpamatovat F.

Šifrováním a dešifrováním zprávy podle NTRUEncrypt může útočník zkontrolovat, zda je funkce F je správný tajný klíč nebo ne.

Vylepšení zabezpečení a výkonu

Pomocí nejnovějších navrhovaných parametrů (viz níže ) kryptosystém veřejného klíče NTRUEncrypt je bezpečný pro většinu útoků. Mezi výkonem a zabezpečením však stále dochází k potížím. Je těžké vylepšit zabezpečení bez zpomalení rychlosti a naopak.

Jedním ze způsobů, jak urychlit proces bez poškození účinnosti algoritmu, je provést některé změny v tajném klíči FNejprve postavte F takhle ${ displaystyle { textbf {f}} = 1 + p { textbf {F}}}$, ve kterém F je malý polynom (tj. koeficienty {-1,0, 1}). Konstruováním F tudy, F je invertible mod str. Ve skutečnosti ${ displaystyle { textbf {f}} ^ {- 1} = 1 { pmod {p}}}$, což znamená, že Bob nemusí skutečně počítat inverzní funkci a že Bob nemusí provádět druhý krok dešifrování. Proto budování F tímto způsobem ušetříte spoustu času, ale neovlivní to bezpečnost NTRUEncrypt, protože je jen snazší najít ${ displaystyle { textbf {f}} _ {p}}$ ale F je stále těžké obnovit. V tomto případě F má koeficienty odlišné od -1, 0 nebo 1, kvůli násobení str. Ale protože Bob se vynásobí str vygenerovat veřejný klíč h, a později redukuje ciphertext modulo str, nebude to mít vliv na metodu šifrování.

Druhý, F lze psát jako součin více polynomů, takže polynomy mají mnoho nulových koeficientů. Tímto způsobem je třeba provést méně výpočtů.

Ve většině komerčních aplikací NTRUEncrypt je parametr N= 251 je použito. Abychom se vyhnuli příhradovým útokům, útokům hrubou silou a útokům uprostřed cesty, F a G by měl mít asi 72 nenulových koeficientů.

Podle nejnovějšího výzkumu ^[3] následující parametry jsou považovány za bezpečné:

Tabulka 1: Parametry

Reference

• Jaulmes, E. a Joux, A. Vybraný šifrovací útok proti NTRU. Poznámky k přednášce z informatiky; Vol 1880. Proceedings of the 20. Annual International Cryptology Conference on Advances in Cryptography. 20–35, 2000.
• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: kruhový veřejný klíčový kryptosystém. In Algorithmic Number Theory (ANTS III), Portland, OR, červen 1998, J. P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.
• Howgrave-Graham, N., Silverman, J.H. & Whyte, W., Setkejte se uprostřed útoku na soukromý klíč NTRU.
• J. Hoffstein, J. Silverman. Optimalizace pro NTRU. Objeví se kryptografie veřejného klíče a teorie výpočetních čísel (Varšava, 11. – 15. Září 2000), DeGruyter.
• A. C. Atici, L. Batina, J. Fan a I. Verbauwhede. Nízkonákladové implementace NTRU pro všudypřítomné zabezpečení.

externí odkazy

• Technické webové stránky NTRU
• Domovská stránka IEEE P1363
• Bezpečnostní inovace (získaná NTRU Cryptosystems, Inc.)
• Implementace licence BSD s otevřeným zdrojovým kódem NTRUEncrypt
• Licence Open Source GPL v2 pro NTRUEncrypt
• strongSwan Open Source IPsec řešení využívající výměnu klíčů založenou na NTRUEncrypt
• - Integrovaná knihovna SSL / TLS nabízející šifrovací sady využívající NTRU (wolfSSL)