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]
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]
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 |
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:
ExempelLå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 :
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 .
ExempelAntag 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:
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.
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 .
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 .
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 .
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.
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.
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:
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 |
Public key kryptosystem | |||||||||
---|---|---|---|---|---|---|---|---|---|
Algoritmer |
| ||||||||
Teori |
| ||||||||
Standarder |
| ||||||||
Ämnen |
|