title: XTR
text: 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. 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 . 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.
  
  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.  
  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.
  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 ). 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)).
  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 bijvoorbeeld 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.
  
  Voor sommige toepassingen van XTR is het vereist om te verifiëren of een bepaald element in de XTR-ondergroep zit. Dit wordt gedaan om eventuele aanvallen op deze ondergroep (subgroup attacks in het Engels) te voorkomen. In dit geval blijkt het handig te zijn om de grootte Q van de XTR-ondergroep ongeveer gelijk te kiezen aan de grootte P van de XTR-supergroep. Bovendien, door gebruik te maken van 'korte machten' (bijvoorbeeld ter grootte van 170 bits), heeft het gebruik van een grote XTR-ondergroep geen negatieve gevolgen voor de snelheid van de cryptografische bewerkingen. In deze situatie wordt de optimale keuze verkregen door p (gegeven dat ) zodanig te kiezen zodat (p2 - p + 1) / 3 een priemgetal is (gelijk aan q). Het volgende algoritme geeft geschikte priemgetallen p en q voor dergelijke toepassingen:
  
  Algoritme III
   Kies een priemgetal  bestaande uit P bits totdat p2 − p + 1 de gedaante q×s heeft waar q een priemgetal is en s klein is.
  
  We geven nu een voorbeeld voor P = Q = 2. Kies p =  dan geldt er p2 − p + 1 = 112 - 11 + 1 = 111 = 3 × 37. Uit het feit dat 11 en 37 priemgetallen zijn volgt er dat we een geschikt tweetal gegenereerd hebben, namelijk p = 11 en q = 37.
  
  Keuze van ondergroep
  Voordat een privé sleutel gegenereerd kan worden, moet er ook een geschikte Tr(g) gevonden worden voor een element g ∈  van orde q, waar q een deler is van p2 − p + 1 en groter is dan 3. Een rechttoe-rechtaanaanpak om  Tr(g) te vinden is het gebruiken van een irreducibele derdegraadsveelterm over  om  te representeren, ook kan een irreducibele zesdegraadsveelterm over  gekozen worden. Vervolgens wordt er een element h ∈  gekozen totdat h(p6−1)/q ≠ 1. Noem dit element g en bereken Tr(g). De achterliggende gedachte van deze methode is redelijk simpel maar om het daadwerkelijk toe te passen in de praktijk blijkt de efficiëntie niet voldoende te zijn. Een snellere manier die ook nog eens makkelijker is toe te passen wordt beschreven in  [6] .
  
  Beveiliging
  
  Bij een juiste keuze van p en q is de XTR-beveiliging gelijkwaardig aan de Diffie-Hellman-beveiliging in de multiplicatieve groep . 
  Deze beveiliging berust op het Diffie-Hellman-probleem om γxy uit te rekenen als γx en γy gegeven zijn. Een efficiënt algoritme dat dit probleem oplost zou het XTR-, DH-protocol en vele andere cryptosystemen onveilig maken. Het wordt echter als zeer onwaarschijnlijk gezien dat dit algoritme gevonden wordt. 
  Het Diffie-Hellman-probleem wordt geschreven als DH(γx,γy) = γxy. Twee andere gerelateerde problemen zijn het Diffie-Hellman-Beslissingsprobleem: gegeven a,b,c ∈ <γ> bepaal of c = DH(a,b) en de discrete logaritme: gegeven a = γx ∈ <γ>, vind x = DL(a). Hoewel er geen bewijs voor is worden deze drie problemen als even moeilijk verondersteld.
  De gelijkwaardigheid van deze drie problemen in  en de XTR-varianten hiervan in de XTR-groep <g> wordt bewezen in [6] .
  Om het DL-probleem in de XTR-groep <g> van orde q op te lossen zijn er twee manieren: men kan de multiplicatieve groep  aanvallen of men kan de ondergroep <g> aanvallen. Voor de eerste aanval kan het best de getallenlichamenzeef gebruikt worden. Omdat <g> niet ingebed kan worden in de multiplicatieve groep van een echt deellichaam  van  voor s=1,2,3, is de verwachte looptijd van dit algoritme:  met 
  Voor de tweede aanval kan het best de Pollards rho-algoritme gekozen worden, dit leidt tot  berekeningen in <g>. 
  Als p en q beide uit 170 bits bestaan, dan is de discrete logaritme in de XTR-groep moeilijker dan het factoriseren van een RSA modulus van 6 * 170 = 1020 bits. 
  Verder is nog authenticatie nodig om een man-in-the-middle-aanval te voorkomen. Iemand kan twee veilige lijnen openen met Alice en Bob, zich voordoende als Alice richting Bob, en als Bob richting Alice. Zo kan hij alle berichten ontcijferen en vercijferd doorsturen na het gelezen of opgeslagen te hebben.  
  Dit probleem kan verholpen worden met een password-authenticated key agreement.
  
  Voorbeeld
  Stel dat Alice en Bob beiden toegang hebben tot de openbare XTR-sleutelgegevens p, q en Tr(g) en een geheime sleutel K willen vormen. In dit voorbeeld zullen ze dat doen met behulp van de XTR-DH-sleutelovereenkomst. De priemgetallen p en q zijn hier té klein gekozen om een veilige privésleutel te kunnen vormen.
  
   Openbare XTR-sleutelgegevens  
  Er zal een voortbrenger g van de XTR-groep en een  geconstrueerd worden ter verduidelijking. Dit is niet nodig bij het implementeren van een XTR-protocol. Het irreducibele zesdegraadspolynoom hieronder is willekeurig. De priemgetallen p, q en de voortbrenger g zijn zo gekozen dat q een deler is van p2 – p + 1 en dat gq = 1 :  
  p = 17
  q = 13
  
   Vorming privésleutel K 
   Alice kiest een geheim getal a = 4 uit het interval [2,14], berekent Tr(ga) =  en stuurt dit naar Bob. 
   Bob kiest een geheim getal b = 5 uit het interval [2,14], berekent Tr(gb) =   en stuurt dit naar Alice.
   Alice ontvangt Tr(gb)  van Bob en berekent Tr(gab) =  , hiermee kan zij de privésleutel K bepalen.
   Bob ontvangt Tr(ga) van Alice en berekent Tr(gab) = ,  hiermee kan hij de privésleutel K bepalen.
  Alice en Bob hebben nu een privésleutel waarmee ze kunnen communiceren. Om veilig te communiceren moeten p en q ter grootte van 170 bits gekozen worden en is authenticatie nodig. 
   
  
  Algoritme
  Cryptografie