XTR is een algoritme binnen de cryptografie dat gebruikt wordt voor het verzenden van de sleutel voor symmetrische cryptografie met hulp van asymmetrische cryptografie. XTR staat voor 'ECSTR' wat een afkorting is voor Efficient And Compact Subgroup Trace Representation. Het is een methode die gebruikmaakt van het spoor om machten van elementen uit een ondergroep van een eindig lichaam weer te geven en te berekenen. XTR is gebaseerd op het Diffie-Hellman-sleuteluitwisselingsprotocol en heeft als voordelen dat de parameter- en sleutelselectie sneller verloopt dan bij RSA, de grootte van de sleutels klein is (kleiner dan bij RSA) en dat de veiligheid gebaseerd is op de discrete logaritme in cyclische groepen.An overview of the XTR public key system De voordelen, samen met het feit dat het makkelijk te programmeren is, maken XTR een geschikt asymmetrische cryptografie dat toepassingen heeft binnen een groot aantal gebieden, van smartcards tot webservers.
Geschiedenis In 1976 publiceerden Whitfield Diffie en Martin Hellman een artikel over het door hen ontwikkeld Diffie-Hellman-sleuteluitwisselingsprotocol over een multiplicatieve groep van een priemlichaam .New Directions in Cryptography Dit systeem geeft partijen de mogelijkheid een gemeenschappelijke sleutel te vormen over een openbare lijn. De beveiliging berust op het feit dat de operator ‘machtsverheffen’ relatief snel is toe te passen en niet (snel) te herleiden met een logaritme (dus te kraken). T. Elgamal suggereerde in 1985 dat uitbreidingslichamen in plaats van een priemlichaam gebruikt konden worden, maar dit leidde niet direct tot snellere of beter beveiligde algoritmen.A Public Key Cryptosystem and a Signature scheme Based on Discrete Logarithms
In 1991 publiceerde Claus P. Schnorr een variant van het Diffie-Hellman-systeem die veel sneller was door een voortbrenger g zo te kiezen dat een kleine ondergroep van gegenereerd wordt.C.P.Schnorr, Efficient signature generation by smart cards, Journal of Cryptology, 4 (1991), 161-174 Andries Brouwer en collega’s lieten in 1999 voor het eerst zien hoe uitbreidingslichamen in combinatie met ondergroepen gebruikt konden worden om het aantal over te zenden bits met een factor 3 te verkleinen.Doing more with fewer bits In 2000 wisten Arjen Lenstra en Eric Verheul dit systeem sneller te maken door het gebruik van de operator spoor. Hun systeem werd XTR.
Werking XTR-supergroep en XTR-groep Veel protocollen binnen de cryptografie zijn gebaseerd op een voortbrenger van de multiplicatieve groep van een eindig lichaam. De Duitse wiskunde Claus P. Schnorr introduceerde het idee om deze voortbrenger te vervangen door de voortbrenger van een relatief kleine ondergroep van orde q, waar q een voldoende groot priemgetal is. Dit idee wordt toegepast in XTR op de volgende manier: Stel dat g een element is van orde q, met q een priemgetal en q > 6, en stel dat q een deler is van p2 − p + 1 waarbij . Omdat p2 − p + 1 een deler is van p6 − 1, de orde van , deelt q ook de orde van de groep . Dit betekent dat g een ondergroep van van orde q genereert. Deze ondergroep wordt de XTR-(onder)groep genoemd terwijl de XTR-supergroep de deelgroep van orde p2 − p + 1 is. De orde van g deelt niet ps − 1 voor s=1,2,3, waaruit volgt dat de ondergroep gegenereerd door g niet kan worden ingebed in de multiplicatieve groep van een echt deellichaam van . Het grote voordeel van XTR is dat machten van het element g voorgesteld kunnen worden aan de hand van slechts één element uit het deellichaam . Het berekenen van deze machten is heel efficiënt aangezien alle bewerkingen in het lichaam plaatsvinden in plaats van . Op deze manier is het construeren van overbodig. Er is slechts een constructie van nodig. Verder moet er ook worden opgemerkt dat een voorstelling van 6log p bits gebruikt terwijl het representeren van slechts 2log p bits kost.
Uit volgt dat p mod 3 de groep genereert zodat de nulpunten α en αp van het polynoom (X3−1)/(X−1)=X2+X+1 een optimale normale basis vormen voor over , met andere woorden {x1α + x2αp: x1, x2 ∈ }. Maar aangezien er ook αi = αi mod 3 geldt, wordt de uiteindelijk voorstelling . In deze representatie wordt een element t uit voorgesteld als −tα-tα2; bijvoorbeeld het element 3 is voorgesteld als −3α−3α2. Aan de hand van deze voorstelling kunnen de bijbehorende kosten voor de bewerkingen in worden bepaald. Kies x1α + x2α2 ∈ . Dit element kan op de volgende manier gekwadrateerd worden (x1α + x2α2)2 = 2x1x2 + x22α + x12α2 = −2x1x2α −2x1x2α2 + x22α + x12α2 = x2(x2 − 2x1)α + x1(x1 − 2x2)α2 waaruit volgt dat kwadrateren slechts twee vermenigvuldigingen vergt in . Hierbij is er aangenomen dat optellen (en dus ook aftrekken) in geen kosten vereist. Er blijkt dat het kwadrateren van een element uit 14.4 vermenigvuldigingen vergt in (hierbij neemt men aan dat kwadrateren in 80% van de tijd kost van een vermenigvuldiging in ).The XTR public key system De overige bewerkingen voor elementen uit blijken ook veel goedkoper te zijn.
Sporen Binnen elk cryptografisch systeem is het maken van sleutels een cruciaal onderdeel. Bij XTR zijn de sleutels gebaseerd op sporen van de elementen uit <g>, de ondergroep voortgebracht door g. Stel dat h een element is van . Dan is h geconjugeerd aan de elementen h, h p2 en h p4 over . De som van deze elementen is gedefinieerd als het spoor van element h, ofwel Tr(h) = h + h p 2 + h p 4 (want Tr(h) p 2 = Tr(h)).S. Lang, Algebra, Graduate Texts in Mathematics. 211. Berlin, New York: Springer-Verlag, 2002 De functie Tr(·) is een homomorfisme van naar , die beide lichamen van karakteristiek p zijn: Tr(h1+h2) = (h1+h2) + (h1+h2)p2 + (h1+h2)p4 = h1 + h2 + h1p2 + h2p2 + h1p4 +h 2p4 = Tr(h1) + Tr(h2). Tr(c·h1) = c·h1 + cp2·h1p2 + cp4·h1p4 = c·h1 + c·h1p2 + c·h1p4 = c·Tr(h1), met h1, h2 en c . Hierdoor is optelling en scalaire vermenigvuldiging eenvoudig binnen . Er is echter geen eenvoudige vermenigvuldiging mogelijk, want in principe geldt: . Het voordeel van het voorstellen van elementen aan de hand van hun sporen is dat alles (elementen en bewerkingen) in plaatsvindt, waardoor het aantal bits met een factor drie gereduceerd wordt. Echter kunnen elementen niet meer onderscheiden worden van hun geconjugeerden (over ).
Sleutels Binnen XTR zijn er verschillende methoden om sleutels te genereren, hoewel elke methode gebaseerd is op sporen van elementen van . Een van de manieren is de XTR-DH-sleutelovereenkomst. Hierbij zijn p, q en Tr(g) openbare sleutelgegevens. Stel dat Alice en Bob een privésleutel K willen maken, dan moeten ze de volgende stappen volgen: Alice kiest een willekeurig geheel getal a in het interval [2,q − 3] en berekent Sa(Tr(g)) = (Tr(ga−1),Tr(ga),Tr(ga+1)) ∈ , en stuurt Tr(ga) () naar Bob. Bob ontvangt Tr(ga), kiest een willekeurig geheel getal b in het interval [2,q − 3] en berekent Sb(Tr(g))=(Tr(gb−1),Tr(gb),Tr(gb+1)) ∈ , en stuurt Tr(gb) () naar Alice. Alice ontvangt Tr(gb) en berekent Sa(Tr(g)b) = (Tr(g(a-1)b),Tr(gab),Tr(g(a+1)b)) ∈ , en bepaalt K op basis van Tr(gab) ∈ . Bob berekent Sb(Tr(g)a) = (Tr(ga(b−1)),Tr(gab),Tr(ga(b+1))) ∈ , en bepaalt K op basis van Tr(gab) ∈ .
Voor het berekenen van de sporen, zoals in Sa(Tr(g)), wordt een algoritme gebruikt. De beginwaarden die hiervoor gebruikt worden zijn als volgt: gegeven a en Tr(g). Als a even is, vervang a := a − 1. Laat a = 2m − 1 en laat k = 1. Bereken S0(Tr(g)) = (Tr(g)p, 3, Tr(g)); S1(Tr(g)) = (3, Tr(g), Tr(g)2 − 2Tr(g)p); S2(Tr(g)) = (Tr(g), Tr(g)2 − 2Tr(g)p, Tr(g)3 − 3Tr(g)p+1 + 3p) en S3 = (Tr(g)2 − 2Tr(g)p, Tr(g)3 − 3Tr(g)p+1 + 3p, 2Tr(g)2p + Tr(g)4 − 4Tr(g)p+2 + (3p+1)Tr(g)). We definiëren Si '(Tr(g)) = S2i+1(Tr(g)) en Tr(g)n = Tr(gn). Laat en Ook is Tr(g)2n = Tr(g2n) = Tr(gn)2 + 2Tr(gn)p, Tr(g)n+2 = Tr(gn+2) = Tr(g) Tr(gn+1) − Tr(g)p Tr(gn) + Tr(gn−1), Tr(g)2n−1 = Tr(g2n-1) = Tr(gn−1) Tr(gn) − Tr(g)p Tr(gn)p + Tr(gn+1)p en Tr(g)2n+1 = Tr(g2n−1) = Tr(gn+1) Tr(gn) - Tr(g) Tr(gn)p + Tr(gn−1)p.
Het algoritme loopt nu alle waarden van j na (voor j = r − 1, r − 2, ... , 0): Als mj = 0, bereken dan S2k' (Tr(g)) = (Tr(g)4k,Tr(g)4k+1,Tr(g)4k+2) aan de hand van Sk' (Tr(g)) = (Tr(g)2k,Tr(g)2k+1,Tr(g)2k+2). Als mj = 1, bereken dan S2k+1' (Tr(g)) = (Tr(g)4k+2,Tr(g)4k+3,Tr(g)4k+4) aan de hand van S2k' (Tr(g)) = (Tr(g)2k,Tr(g)2k+1,Tr(g)2k+2). Vervang k := 2k+mj, j := j−1.
Na alle iteraties is k = m en is de laatste uitkomst Sa(Tr(g)). Als a oneven was, bevat deze de gezochte waarde Tr(ga). Als a even was, moet Sa+1(Tr(g)) berekend worden aan de hand van Sa(Tr(g)).
In 2001 hebben Lenstra en Stam aangetoond dat deze sporen, zoals Tr(ga), sneller berekend kunnen worden. Deze methode gebruikt een aantal nieuwe berekeningen van machten van sporen, zoals Tr(g)3n, heeft niet alle opvolgende waarden van Sk (k=0,...,3) nodig en vereist daardoor minder berekeningen.
Het toekennen van waarden aan de parameters Keuze van p en q Uit het bovenstaande volgt dat de priemgetallen p en q zodanig gekozen moeten zodat q een deler is van p2 − p + 1. Bovendien moeten de op deze manier verkregen lichamen en ondergroepen groot genoeg zijn om bescherming te bieden tegen mogelijke aanvallen. Om gebruik te kunnen maken van de snelle bewerkingen in moet het priemgetal p van de vorm 2 (mod 3) zijn. Priemgetallen van de vorm 1 (mod 3) garanderen niet dezelfde snelheid. Veronderstel dat P en Q corresponderen met het aantal bits van de priemgetallen p en q respectievelijk. Het priemgetal p moet zodanig gekozen worden zodat het lichaam niet efficiënt aangevallen kan worden door gebruik te maken van de getallenlichamenzeef. Verder moet de keuze van q ervoor zorgen dat de ondergroep van orde q niet efficiënt kan worden aangevallen met het Pollards rho-algoritme. Om hetzelfde veiligheidsniveau te bereiken als dat van RSA met 1024 bits, moet 6P ongeveer 1024 bits hebben waaruit volgt dat P ≈ 170. Het wordt niet aangeraden om Q veel kleiner dan P te kiezen. De keuze Q ≈ 160 wordt daarom als acceptabel beschouwd. In principe mag p ook een priemgetal tot een bepaalde niet-triviale macht zijn. Echter wordt het kiezen van geschikte p en q in het algemeen op deze manier een stuk lastiger. Hier volgt een algoritme dat gebruikt kan worden om een q en een 'mooie' p te vinden:
Algoritme I Vind r ∈ zodanig dat q = r2 − r + 1 een priemgetal is met Q bits. Vind k ∈ zodanig dat p = r + kq = kr2 + (1 − k)r + k een priemgetal is met P bits én van de vorm 2 (mod3).
Algoritme I is heel snel en kan gebruikt worden om priemgetallen p te vinden die voldoen aan een tweedegraadsveelterm met kleine coëfficiënten. Zulke p leiden tot snelle bewerkingen in . In het bijzonder kan de beperking k = 1 worden beschouwd. Merk op dat er in dit geval een r wordt gevraagd zodanig dat zowel r2 − r + 1 als r2 + 1 priemgetallen zijn én . Hieruit volgt dat r een even getal moet zijn. Wanneer we p = r2 + 1 modulo 4 bekijken, zien we dat de restterm van een even getal in het kwadraat gelijk is aan 0 modulo 4, waaruit we concluderen dat p de 'mooie' gedaante heeft. We zien dat het in het geval k = 1 redelijk makkelijk is om een voorbeeld te vinden. Kies bijvoorbeeld r = 4. Dan geldt er q = r2 − r + 1 = 42 - 4 + 1 = 13 hetgeen een priemgetal is evenals p = r2 + 1 = 42 + 1 = . Vanwege de mooie vorm van p heeft dit algoritme als nadeel dat het misschien het toepassen van de getallenlichamenzeef vergemakkelijkt. Een andere methode om p en q te genereren die dit nadeel niet heeft en ongeveer even snel is het volgende algoritme:
Algoritme II Kies een priemgetal dat Q bits heeft. Vind de nulpunten r1 en r2 van het polynoom X2 − X + 1 mod q. Vind k ∈ zodanig dat p = ri + kq voor i = 1 of 2 een priemgetal is van de vorm 2 (mod 3) bestaande uit P bits.
Hier volgt een voorbeeld met Q = 2 en P = 3: Kies q = dan geldt (−7)2 − −7 + 1 = en 82 − 8 + 1 = . Hieruit volgt dat r1 = −7 en r2 = 8. Kies vervolgens k = 6 dan p = r1 + kq = −7 + 6×19 = . Aangezien zowel 19 als 107 priemgetallen zijn, hebben we op deze manier de combinatie q = 19 en p = 107 gegenereerd.