NTRUEncrypt

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 december 2015; kontroller kräver 20 redigeringar .

NTRUEncrypt ( förkortning för Nth-degree TRUNcated polynomial ring eller Number Theorists aRe Us) är ett kryptografiskt system med offentlig nyckel som tidigare kallades NTRU .

NTRUEncrypt-kryptosystemet, baserat på ett gitterkryptosystem , skapades som ett alternativ till RSA och Elliptic Curve Cryptosystems (ECC) . Algoritmens stabilitet säkerställs av svårigheten att hitta den kortaste gittervektorn , som är mer motståndskraftig mot attacker utförda på kvantdatorer . Till skillnad från sina konkurrenter RSA , ECC , Elgamal , använder algoritmen operationer på ringen av trunkerade polynom med en grad som inte överstiger :

Ett sådant polynom kan också representeras av en vektor

Liksom alla unga algoritmer är NTRUEncrypt dåligt förstådd, även om den officiellt godkändes för användning i ekonomi av Accredited Standards Committee X9 . [ett]

Det finns en implementering av NTRUEncrypt med öppen källkod . [2]

Historik

NTRUEncrypt, ursprungligen kallad NTRU, uppfanns 1996 och introducerades för världen på CRYPTO- , RSA Conference , Eurocrypt . Anledningen som fungerade som början på utvecklingen av algoritmen 1994 var artikeln [3] , som talade om hur lätt det är att knäcka befintliga algoritmer på kvantdatorer, vilket, som tiden har visat, inte är långt borta [4] . Samma år kom matematikerna Jeffrey Hoffstein, Jill Pipher och Joseph H. Silverman, som utvecklade systemet tillsammans med grundaren av NTRU Cryptosystems, Inc. (senare omdöpt till SecurityInnovation), patenterade Daniel Lieman deras uppfinning. [5]

Ringar av trunkerade polynom

NTRU arbetar på polynom av högst grad

där koefficienterna  är heltal. När det gäller operationerna för addition och multiplikation modulo ett polynom , bildar sådana polynom en ring R , kallad ringen av trunkerade polynom , som är isomorf till kvotringen

NTRU använder den trunkerade polynomringen R tillsammans med modulo coprimtalen p och q för att reducera polynomens koefficienter .

Algoritmen använder också inversa polynom i ringen av trunkerade polynom. Det bör noteras att inte varje polynom har en invers, men om det finns ett inverst polynom är det lätt att beräkna det. [6] [7]

Följande alternativ kommer att väljas som exempel:

Parameterbeteckningar N q sid
Parametervärden elva 32 3

Public Key Generation

För att skicka ett meddelande från Alice till Bob behövs en offentlig och privat nyckel. Både Bob och Alice känner till den publika nyckeln, bara Bob känner till den privata nyckeln, som han använder för att generera den publika nyckeln. För att göra detta väljer Bob två "små" polynom f g från R . Polynomens "småhet" antyds i den meningen att den är liten med avseende på ett godtyckligt polynom modulo q : i ett godtyckligt polynom måste koefficienterna vara ungefär likformigt fördelade modulo q , medan de i ett litet polynom är mycket mindre än q . Polynomens litenhet bestäms med talen df och dg :

Anledningen till att polynomen väljs på detta sätt är att f förmodligen kommer att ha en invers, men g  definitivt inte ( g (1) = 0, och element noll har ingen invers).

Bob måste hålla dessa polynom hemliga. Därefter beräknar Bob de inversa polynomen och , det vill säga så att:

och .

Om f inte har ett inverst polynom, så väljer Bob ett annat polynom f .

Den hemliga nyckeln är ett par och den publika nyckeln h beräknas med formeln:

Exempel

Låt oss till exempel ta df =4 och dg =3. Sedan kan man som polynom välja

Därefter, för polynomet f , söks inversa polynom modulo p =3 och q =32:

Det sista steget är att beräkna den publika nyckeln h själv :

Kryptering

Nu när Alice har den offentliga nyckeln kan hon skicka det krypterade meddelandet till Bob. För att göra detta måste du representera meddelandet som ett polynom m med koefficienter modulo pvalda från intervallet (- p /2, p /2]. Det vill säga, m är ett "litet" polynom modulo q . Därefter måste Alice välj ett annat "litet" polynom r , som kallas "bländande", definierat av talet dr :

Med dessa polynom erhålls det krypterade meddelandet med formeln:

I det här fallet kommer alla som känner till (eller kan beräkna) det bländande polynomet r att kunna läsa meddelandet m .

Exempel

Antag att Alice vill skicka ett meddelande representerat som ett polynom

och valde ett "blindande" polynom för vilket dr = 3:

Då blir chiffertexten e redo att skickas till Bob:

Dekryptering

Nu, efter att ha mottagit det krypterade meddelandet e , kan Bob dekryptera det med sin privata nyckel. Först får han ett nytt mellanpolynom:

Om vi ​​skriver chiffertexten får vi kedjan:

och slutligen:

Efter att Bob har beräknat polynomet a modulo q, måste han välja dess koefficienter från intervallet (- q /2, q /2] och sedan beräkna polynomet b som erhålls från polynomet a genom reduktionsmodulo p:

sedan .

Nu, med hjälp av den andra halvan av den hemliga nyckeln och det resulterande polynomet b , kan Bob dekryptera meddelandet:

Det är lätt att se det

Det resulterande polynomet c är verkligen det ursprungliga meddelandet m .

Exempel : Bob fick ett krypterat meddelande e från Alice

Med den hemliga nyckeln f får Bob ett polynom a

med koefficienter som hör till intervallet (- q /2, q /2]. Därefter transformerar du polynom a till polynom b , vilket reducerar koefficienterna modulo p.

Det sista steget är att multiplicera polynomet b med den andra hälften av den privata nyckeln

Vilket är det ursprungliga meddelandet som Alice sände.

Motstånd mot attacker

Fullständig uppräkning

Den första av de möjliga attackerna är brute -force attacken . Här är flera varianter av uppräkning möjliga: antingen att sortera igenom alla , och kontrollera om koefficienterna för resultaten är små , som enligt idén borde ha varit små, eller att sortera igenom alla , även kontrollera om koefficienterna är små av resultatet . I praktiken är utrymmet mindre än utrymmet , därför bestäms hållbarheten av utrymmet . Och varaktigheten av ett individuellt meddelande bestäms av rymden .

Möte i mitten

Det finns en mer optimal variant av uppräkningsmöte i mitten föreslagen av Andrew Odlyzhko . Denna metod reducerar antalet alternativ till kvadratroten:

Säkerhet för den privata nyckeln = = ,

Och uthålligheten av ett enda meddelande = = .

En möte-i-mitt-attack byter ut den tid som behövs för beräkning mot det minne som behövs för att lagra tillfälliga resultat. Om vi ​​vill säkerställa systemets stabilitet måste vi alltså välja en storleksnyckel .

Attack med flera meddelanden

En ganska allvarlig attack mot ett enda meddelande, som kan undvikas genom att följa en enkel regel - skicka inte samma meddelande flera gånger. Kärnan i attacken är att hitta en del av koefficienterna för det bländande polynomet r . Och de återstående koefficienterna kan helt enkelt sorteras ut och därigenom läsa meddelandet. Eftersom samma krypterade meddelande med olika bländande polynom är , där i=1, … n. Du kan utvärdera ett uttryck som är exakt lika med . För ett tillräckligt stort antal sända meddelanden (säg för n = 4, 5, 6) är det möjligt att återställa, baserat på koefficienternas litenhet, det mesta av det bländande polynomet .

Gitterbaserad attack

Betrakta ett gitter som genereras av raderna i en 2 N × 2 N matris med determinant , bestående av fyra block med storleken N × N :

Eftersom den publika nyckeln är , så innehåller alltså detta gitter en vektor med storleken 2 N , som först innehåller koefficienterna för vektorn f , multiplicerad med koefficienten , sedan koefficienterna för vektorn g . Uppgiften att hitta en sådan vektor, för stora N och korrekt valda parametrar, anses svår att lösa.

Vald chiffertextattack

Den valda chiffertextattacken är den farligaste attacken. Det föreslogs av Éliane Jaulmes och Antoine Joux [8] 2000 vid CRYPTO-konferensen. Kärnan i denna attack är att välja ett sådant polynom a(x) så att . Samtidigt interagerar inte Eve med varken Bob eller Alice.

Om vi ​​tar chiffertexten , där , får vi ett polynom . Eftersom koefficienterna för polynomen f och g tar värdena "0", "1" och "-1", så kommer koefficienterna för polynomet a att tillhöra mängden {-2py , -py , 0, py, 2py}. Om py väljs så att , när man reducerar modulo för polynomet a(x), kommer endast koefficienter lika med -2py eller 2py att ges . Låt nu den i -te koefficienten vara lika med 2py , då kommer polynomet a(x) efter moduloreduktion att skrivas som:

,

och polynomet b(x) :

,

räkna slutligen ut:

.

Om vi ​​nu tar hänsyn till alla möjliga i , då istället för individuella , kan vi komponera ett polynom K och det dekrypterade meddelandet kommer att ha formen:

,

eller hemlig nyckel:

,

Sannolikheten att hitta nyckelkomponenter på detta sätt är cirka 0,1 ... 0,3 för en nyckel av storlek 100. För stora nycklar (~500) är denna sannolikhet mycket liten. Genom att använda denna metod tillräckligt många gånger kan du återställa nyckeln helt.

För att skydda mot denna typ av attack används den avancerade NTRU-FORST- krypteringsmetoden . För kryptering används ett bländande polynom , där H  är en kryptografiskt stark hashfunktion och R  är en slumpmässig uppsättning bitar . Efter att ha tagit emot meddelandet dekrypterar Bob det. Därefter krypterar Bob det nyligen dekrypterade meddelandet på samma sätt som Alice gjorde. Efter det jämför den den med den mottagna. Om meddelandena är identiska, accepterar Bob meddelandet, annars avvisar han det.

Hållbarhet och prestandaparametrar

Trots det faktum att det finns snabba algoritmer för att hitta det inversa polynomet, föreslog utvecklarna för kommersiell användning som en hemlig nyckel f att ta:

,

där F  är ett litet polynom. Den sålunda valda nyckeln har följande fördelar:

En av studierna arkiverad 6 oktober 2016 på Wayback Machine visade att NTRU är 4 storleksordningar snabbare än RSA och 3 storleksordningar snabbare än ECC .

Som nämnts tidigare föreslår utvecklarna, för att säkerställa algoritmens höga stabilitet, att endast använda de rekommenderade parametrarna som anges i tabellen:

Rekommenderade parametrar

Beteckning N q sid df dg dr Garanterad hållbarhet
NTRU167:3 167 128 3 61 tjugo arton Måttlig hållbarhet
NTRU251:3 251 128 3 femtio 24 16 Standard motståndsnivå
NTRU503:3 503 256 3 216 72 55 Den högsta nivån av hållbarhet
NTRU167:2 167 127 2 45 35 arton Måttlig hållbarhet
NTRU251:2 251 127 2 35 35 22 Standard motståndsnivå
NTRU503:2 503 253 2 155 100 65 Den högsta nivån av hållbarhet

Anteckningar

  1. Security Innovations NTRUEncrypt antagen som X9-standard för dataskydd . Hämtad 15 mars 2022. Arkiverad från originalet 13 augusti 2016.
  2. NTRUEncrypt och NTRUSign i Java . Hämtad 1 november 2011. Arkiverad från originalet 19 november 2011.
  3. Algoritmer för kvantberäkning: diskreta logaritmer och factoring (nedlänk) . Hämtad 30 oktober 2011. Arkiverad från originalet 18 juni 2010. 
  4. NIST demonstrerar "universell" programmerbar kvantprocessor . Hämtad 30 oktober 2011. Arkiverad från originalet 30 november 2011.
  5. NTRU Public Key Algorithms IP Assurance Statement för 802.15.3 . Hämtad 30 oktober 2011. Arkiverad från originalet 9 april 2016.
  6. JH Silverman, Nästan inverser och snabb NTRU-nyckelskapande Arkiverad 24 mars 2012 på Wayback Machine , NTRU Cryptosystems Technical Report #014.
  7. JH Silverman, Invertibility in Truncated Polynomial Rings Arkiverad 14 maj 2012 på Wayback Machine , NTRU Cryptosystems Technical Report #009.
  8. Jaulmes É., Joux A. En attack mot NTRU //Annual International Cryptology Conference. - Springer, Berlin, Heidelberg, 2000. - S. 20-35.

Länkar