Kryptosystém McEliece - McEliece cryptosystem

v kryptografie, Kryptosystém McEliece je asymetrické šifrování algoritmus vyvinutý v roce 1978 uživatelem Robert McEliece.^[1] Bylo to první takové schéma, které se používalo randomizace v procesu šifrování. Algoritmus v kryptografické komunitě nikdy nebyl příliš akceptován, ale je kandidátem na „postkvantová kryptografie ", protože je imunní vůči útokům pomocí Shorův algoritmus a - obecněji - měření stavů cosetu pomocí Fourierova vzorkování.^[2]

Algoritmus je založen na tvrdosti dekódování generál lineární kód (o kterém je známo, že je NP-tvrdé^[3]). Popis soukromého klíče, an kód pro opravu chyb je vybrán, pro který je známý efektivní dekódovací algoritmus a který je schopen opravit ${ displaystyle t}$ chyby. Původní algoritmus používá binární kódy Goppa (podpole kódy geometrické Kódy Goppa křivky rodu 0 nad konečnými poli charakteristiky 2); tyto kódy lze efektivně dekódovat díky algoritmu podle Pattersona.^[4] Veřejný klíč je odvozen od soukromého klíče maskováním vybraného kódu jako obecného lineárního kódu. K tomu je kód matice generátoru ${ displaystyle G}$ je narušen dvěma náhodně vybranými invertibilními maticemi ${ displaystyle S}$ a ${ displaystyle P}$ (viz. níže).

Varianty tohoto kryptosystému existují a používají různé typy kódů. U většiny z nich se ukázalo, že jsou méně bezpečné; byli rozbiti strukturální dekódování.

Společnost McEliece s kódy Goppa dosud odolávala dešifrování. Nejúčinnější útoky známé použití dekódování sady informací algoritmy. Dokument z roku 2008 popisuje útok i opravu.^[5] Další práce ukazuje, že pro kvantové výpočty musí být velikosti klíčů zvětšeny čtyřikrát kvůli vylepšení dekódování informační sady.^[6]

Kryptosystém McEliece má některé výhody oproti například RSA. Šifrování a dešifrování jsou rychlejší.^[7] Po dlouhou dobu se předpokládalo, že McEliece nelze použít k výrobě podpisy. Podpisové schéma však může být vytvořeno na základě Niederreiter schéma, duální varianta schématu McEliece. Jednou z hlavních nevýhod McEliece je, že soukromý a veřejný klíč jsou velké matice. Pro standardní výběr parametrů je veřejný klíč dlouhý 512 kilobitů.

Definice schématu

McEliece se skládá ze tří algoritmů: pravděpodobnostní algoritmus generování klíčů, který vytváří veřejný a soukromý klíč, pravděpodobnostní šifrování algoritmus a deterministický dešifrovací algoritmus.

Všichni uživatelé v nasazení McEliece sdílejí sadu běžných parametrů zabezpečení: ${ displaystyle n, k, t}$ .

Generování klíčů

Princip je ten, že Alice zvolí lineární kód ${ displaystyle C}$ z nějaké rodiny kódů, pro které zná efektivní dekódovací algoritmus, a to ${ displaystyle C}$ veřejně známé, ale dekódovací algoritmus udržujte v tajnosti Takový dekódovací algoritmus vyžaduje nejen znalost ${ displaystyle C}$ , ve smyslu znát libovolnou matici generátoru, ale vyžaduje znalost znalosti parametrů použitých při zadávání ${ displaystyle C}$ ve vybrané rodině kódů. Například pro binární kódy Goppa by touto informací byl polynom Goppa a vyhledávače kódů. Proto může Alice publikovat vhodně popletenou matici generátoru ${ displaystyle C}$ veřejně.

Kroky jsou konkrétněji následující:

Alice vybere binární soubor ${ displaystyle (n, k)}$ -lineární kód ${ displaystyle C}$ schopný (efektivně) korigovat ${ displaystyle t}$ chyby z některé velké skupiny kódů, např. binární kódy Goppa. Tato volba by měla vést k efektivnímu dekódovacímu algoritmu ${ displaystyle A}$ . Nechť také ${ displaystyle G}$ být libovolná generátorová matice pro ${ displaystyle C}$ . Jakýkoli lineární kód má mnoho generátorových matic, ale pro tuto rodinu kódů je často přirozená volba. Vědět to odhalí ${ displaystyle A}$ takže by to mělo být tajné.
Alice vybere náhodně ${ displaystyle k krát k}$ binární ne-singulární matice ${ displaystyle S}$ .
Alice vybere náhodně ${ displaystyle n krát n}$ permutační matice ${ displaystyle P}$ .
Alice počítá ${ displaystyle k krát n}$ matice ${ displaystyle { hat {G}} = SGP}$ .
Alicin veřejný klíč je ${ displaystyle ({ hat {G}}, t)}$ ; její soukromý klíč je ${ displaystyle (S, P, A)}$ . Všimněte si, že ${ displaystyle A}$ lze zakódovat a uložit jako parametry použité pro výběr ${ displaystyle C}$ .

Šifrování zpráv

Předpokládejme, že si Bob přeje poslat zprávu m Alici, jejíž veřejný klíč je ${ displaystyle ({ hat {G}}, t)}$ :

Bob zakóduje zprávu ${ displaystyle m}$ jako binární řetězec délky ${ displaystyle k}$ .
Bob vypočítá vektor ${ displaystyle c ^ { prime} = m { hat {G}}}$ .
Bob generuje náhodný ${ displaystyle n}$ -bitový vektor ${ displaystyle z}$ obsahující přesně ${ displaystyle t}$ ty (vektor délky ${ displaystyle n}$ a hmotnost ${ displaystyle t}$ )^[1]
Bob počítá šifrovací text jako ${ displaystyle c = c ^ { prime} + z}$ .

Dešifrování zprávy

Po obdržení ${ displaystyle c}$ , Alice k dešifrování zprávy provede následující kroky:

Alice počítá inverzní funkci ${ displaystyle P}$ (tj. ${ displaystyle P ^ {- 1}}$ ).
Alice počítá ${ displaystyle { hat {c}} = cP ^ {- 1}}$ .
Alice používá dekódovací algoritmus ${ displaystyle A}$ dekódovat ${ displaystyle { hat {c}}}$ na ${ displaystyle { hat {m}}}$ .
Alice počítá ${ displaystyle m = { hat {m}} S ^ {- 1}}$ .

Doklad o dešifrování zprávy

Všimněte si, že ${ displaystyle { hat {c}} = cP ^ {- 1} = m { hat {G}} P ^ {- 1} + zP ^ {- 1} = mSG + zP ^ {- 1}}$ , a to ${ displaystyle P}$ je tedy permutační matice ${ displaystyle zP ^ {- 1}}$ má váhu ${ displaystyle t}$ .

Kód Goppa ${ displaystyle G}$ lze opravit až ${ displaystyle t}$ chyby a slovo ${ displaystyle mSG}$ je nanejvýš na dálku ${ displaystyle t}$ z ${ displaystyle cP ^ {- 1}}$ . Proto správné kódové slovo ${ displaystyle { hat {m}} = mS}$ je získáno.

Násobení inverzní funkcí z ${ displaystyle S}$ dává ${ displaystyle m = { hat {m}} S ^ {- 1} = mSS ^ {- 1}}$ , což je prostá textová zpráva.

Klíčové velikosti

McEliece původně navrhoval velikosti bezpečnostních parametrů ${ displaystyle n = 1024, k = 524, t = 50}$ ,^[1] což má za následek velikost veřejného klíče 524 * (1024–524) = 262 000 bitů^{[je zapotřebí objasnění ]}. Nedávná analýza navrhuje velikosti parametrů ${ displaystyle n = 2048, k = 1751, t = 27}$ pro 80 kousky zabezpečení při použití standardního algebraického dekódování nebo ${ displaystyle n = 1632, k = 1269, t = 34}$ při použití dekódování seznamu pro kód Goppa, což vede k velikosti veřejného klíče 520 047 a 460 647 bitů.^[5] Pro odolnost vůči kvantovým počítačům, velikosti ${ displaystyle n = 6960, k = 5413, t = 119}$ s kódem Goppa byly navrženy, což dalo velikost veřejného klíče 8 373 911 bitů.^[8]

Útoky

Útok se skládá z protivníka, který zná veřejný klíč ${ displaystyle ({ hat {G}}, t)}$ ale ne soukromý klíč, odvodit holý text z nějakého zachyceného šifrovacího textu ${ displaystyle y in mathbb {F} _ {2} ^ {n}}$ . Takové pokusy by neměly být možné.

McEliece má dvě hlavní větve útoků:

Hrubá síla / nestrukturované útoky

Útočník to ví ${ displaystyle { hat {G}}}$ což je matice generátoru ${ displaystyle (n, k)}$ kód ${ displaystyle { hat {C}}}$ který je kombinatoricky schopen opravit ${ displaystyle t}$ chyby. Útočník může tuto skutečnost ignorovat ${ displaystyle { hat {C}}}$ je ve skutečnosti zmatek strukturovaného kódu vybraného z konkrétní rodiny a místo toho stačí použít algoritmus pro dekódování libovolným lineárním kódem. Existuje několik takových algoritmů, například procházení každým kódovým slovem kódu, dekódování syndromu nebo dekódování sady informací.

Dekódování obecného lineárního kódu je však známo NP-tvrdé,^[3] a všechny výše uvedené metody mají exponenciální dobu běhu.

V roce 2008 Bernstein, Lange a Peters^[5] popsal praktický útok na původní kryptosystém McEliece pomocí metody Stern Information Set Decoding.^[9]Za použití parametrů původně navržených McEliecem by útok mohl být proveden za 2^60.55 bitové operace. Protože útok je trapně paralelní (komunikace mezi uzly není nutná), lze ji provádět za několik dní na skromných počítačových klastrech.

Strukturální útoky

Útočník se místo toho může pokusit obnovit „strukturu“ serveru ${ displaystyle C}$ , čímž se obnoví efektivní dekódovací algoritmus ${ displaystyle A}$ nebo jiný dostatečně silný a efektivní dekódovací algoritmus.

Rodina kódů, ze kterých ${ displaystyle C}$ je zcela vybráno, určuje, zda je to pro útočníka možné. Pro McEliece bylo navrženo mnoho rodin kódů a většina z nich byla zcela „rozbitá“ v tom smyslu, že byly nalezeny útoky, které obnoví účinný dekódovací algoritmus, jako například Kódy Reed-Solomon.

Původně navrhované binární kódy Goppa zůstávají jednou z mála navrhovaných skupin kódů, které do značné míry odolávaly pokusům o vytvoření strukturálních útoků.

Reference

^ ^A ^b ^C McEliece, Robert J. (1978). „Kryptosystém veřejného klíče založený na teorii algebraického kódování“ (PDF). Zpráva o pokroku DSN. 44: 114–116. Bibcode:1978DSNPR..44..114M.
^ Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). Kryptosystémy McEliece a Niederreiter, které odolávají kvantovým Fourierovým vzorkovacím útokům. Pokroky v kryptologii - CRYPTO 2011. Přednášky v informatice. 6841. Heidelberg: Springer. str. 761–779. doi:10.1007/978-3-642-22792-9_43. ISBN 978-3-642-22791-2. PAN 2874885.
^ ^A ^b Berlekamp, Elwyn R .; McEliece, Robert J .; Van Tilborg, Henk C.A. (1978). "O vrozené neodolatelnosti určitých problémů s kódováním". Transakce IEEE na teorii informací. IT-24 (3): 384–386. doi:10.1109 / TIT.1978.1055873. PAN 0495180.
^ N. J. Patterson (1975). "Algebraické dekódování kódů Goppa". Transakce IEEE na teorii informací. IT-21 (2): 203–207. doi:10.1109 / TIT.1975.1055350.
^ ^A ^b ^C Bernstein, Daniel J .; Lange, Tanja; Peters, Christiane (8. srpna 2008). Útok a obrana kryptosystému McEliece. Proc. 2. mezinárodní workshop o postkvantové kryptografii. Přednášky z informatiky. 5299. 31–46. CiteSeerX 10.1.1.139.3548. doi:10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6.
^ Bernstein, Daniel J. (2010). Sendrier, Nicolas (ed.). Grover vs. McEliece (PDF). Postkvantová kryptografie 2010. Přednášky v informatice. 6061. Berlín: Springer. str. 73–80. doi:10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5. PAN 2776312.
^ „eBATS: ECRYPT Benchmarking asymetrických systémů“. bench.cr.yp.to. 25. srpna 2018. Citováno 1. května 2020.
^ Daniel Augot; et al. (7. září 2015). „Počáteční doporučení dlouhodobě bezpečných postkvantových systémů“ (PDF). PQCRYPTO: Postkvantová kryptografie pro dlouhodobé zabezpečení.
^ Jacques Stern (1989). Metoda pro hledání kódových slov malé váhy. Teorie kódování a aplikace. Přednášky z informatiky. 388. Springer Verlag. 106–113. doi:10.1007 / BFb0019850. ISBN 978-3-540-51643-9.

externí odkazy

Alfred J. Menezes; Scott A. Vanstone; A. J. Menezes; Paul C. van Oorschot (1996). „Kapitola 8: Šifrování pomocí veřejného klíče“. Příručka aplikované kryptografie. CRC Press. ISBN 978-0-8493-8523-0.

„Kvantové počítače? Praskl internetový bezpečnostní kód budoucnosti“. Věda denně. Eindhoven University of Technology. 1. listopadu 2008.

„Classic McEliece“. (Podání NIST Standardizace post-kvantové kryptografie Projekt)

[McEliece-1] A ^b ^C McEliece, Robert J. (1978). „Kryptosystém veřejného klíče založený na teorii algebraického kódování“ (PDF). Zpráva o pokroku DSN. 44: 114–116. Bibcode:1978DSNPR..44..114M.

[quantum-fourier-2] Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). Kryptosystémy McEliece a Niederreiter, které odolávají kvantovým Fourierovým vzorkovacím útokům. Pokroky v kryptologii - CRYPTO 2011. Přednášky v informatice. 6841. Heidelberg: Springer. str. 761–779. doi:10.1007/978-3-642-22792-9_43. ISBN 978-3-642-22791-2. PAN 2874885.

[intractability-3] A ^b Berlekamp, Elwyn R .; McEliece, Robert J .; Van Tilborg, Henk C.A. (1978). "O vrozené neodolatelnosti určitých problémů s kódováním". Transakce IEEE na teorii informací. IT-24 (3): 384–386. doi:10.1109 / TIT.1978.1055873. PAN 0495180.

[Patterson-4] N. J. Patterson (1975). "Algebraické dekódování kódů Goppa". Transakce IEEE na teorii informací. IT-21 (2): 203–207. doi:10.1109 / TIT.1975.1055350.

[fix-5] A ^b ^C Bernstein, Daniel J .; Lange, Tanja; Peters, Christiane (8. srpna 2008). Útok a obrana kryptosystému McEliece. Proc. 2. mezinárodní workshop o postkvantové kryptografii. Přednášky z informatiky. 5299. 31–46. CiteSeerX 10.1.1.139.3548. doi:10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6.

[6] Bernstein, Daniel J. (2010). Sendrier, Nicolas (ed.). Grover vs. McEliece (PDF). Postkvantová kryptografie 2010. Přednášky v informatice. 6061. Berlín: Springer. str. 73–80. doi:10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5. PAN 2776312.

[7] „eBATS: ECRYPT Benchmarking asymetrických systémů“. bench.cr.yp.to. 25. srpna 2018. Citováno 1. května 2020.

[PQcrypto-initial-8] Daniel Augot; et al. (7. září 2015). „Počáteční doporučení dlouhodobě bezpečných postkvantových systémů“ (PDF). PQCRYPTO: Postkvantová kryptografie pro dlouhodobé zabezpečení.

[9] Jacques Stern (1989). Metoda pro hledání kódových slov malé váhy. Teorie kódování a aplikace. Přednášky z informatiky. 388. Springer Verlag. 106–113. doi:10.1007 / BFb0019850. ISBN 978-3-540-51643-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]