[Muokattu: 27.9.2013]

NTRU-algoritmi (3-B) [ < Epäsymmetrisiä ... < Kryptoalgoritmi... ]

Julkisen avaimen systeemejä kehitellään kaiken aikaa. Yksi uusista on algoritmeista on NTRU. Se on noin vuodelta 1996 eli 20 vuotta myöhempi kuin ensimmäiset PK-systeemit. Rakenne poikkeaa monista aiemmista, ja se esitellään tarkemmin Matemaattisen kryptologian kurssilla. Koska uutta primitiiviä pidetään turvallisena, se kannattaa mainita myös tässä.

Laskenta tapahtuu erikseen modulo p ja q enintään tiettyä astetta N-1 olevilla polynomeilla, joiden kertoimet ovat kokonaislukuja. Parametrien p, q ja N esimerkkiarvoja ovat: N=167, 263 tai 503; p = 2 tai 3; q = 64, 127, 128, 253 tai 256. Nyt siis moduulit p ja q ovat pieniä eikä niitä kerrota keskenään. Niistä edellytetään vain, että syt(p,q)=1 ja q on paljon isompi kuin p.

Turvallisuus perustuu modulosekoituksen lisäksi vaikeuteen löytää lyhyitä vektoreita hilasta. Hila tarkoittaa tässä pistejoukkoa, joka muodostuu vektoriavaruuteen, kun jotkin kantavektorit summataan kaikilla mahdollisilla kokonaislukukertoimilla. Hyviä algoritmeja tähän on, mutta ei tarpeeksi hyviä. Parhaat aiheuttivat selkäreppu- eli knapsack-salausjärjestelmien ”tuhon” 1980-luvulla. Myös NTRUssa pitää valita parametrit oikein, jotta hyökkäys olisi vaikea.

Julkinen avain on NTRU:ssa kahden polynomin tulo (kertoimet modulo q). Yksityinen avain on toinen näistä polynomeista ja sillä pitää olla käänteispolynomi sekä modulo p että modulo q. Toista tulon tekijää ei tarvita!

Salaus on nopeaa. Siinä valitaan satunnainen polynomi, tehdään polynomikertolasku ja redusoidaan modulo q. Myös purku on nopea, mutta se vaatii huolellisuutta ja voi joissain tapauksissa epäonnistua. Siinä tehdään ensin polynomikertolasku modulo q, säädetään kertoimia sopivalle välille (-q/2 .. +q/2), ja sitten polynomikertolasku modulo p.

Edellä luonnostellun NTRU-salauksen ohella on olemassa myös NTRU-allekirjoitus, mutta se on varsin etäistä sukua tälle algoritmille.

NTRUEncrypt on standardoitu (2008) ja patentoitu, mutta siitä on olemassa myös avoimen koodin Java-toteutus. Lisätietoja saa myös NTRU-sivustolta . Leuvenin yliopistossa tehdyt tutkimukset (2010) osoittavat NTRUn GPU-toteutusten olevan merkittävästi nopeampia kuin vastaavan tason turvallisuuden tarjoavat RSA tai elliptisten käyrien kryptosysteemit.