XTR

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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.[1] 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[bewerken]

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 .[2] 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.[3]

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.[4]
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.[5]
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[bewerken]

XTR-supergroep en XTR-groep[bewerken]

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 p ≡ 2 (mod 3). 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 p ≡ 2 (mod 3) 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 - 2x22 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 ).[6] De overige bewerkingen voor elementen uit blijken ook veel goedkoper te zijn.

Sporen[bewerken]

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)).[7]
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[bewerken]

Binnen XTR zijn er verschillende methoden om sleutels te genereren, hoewel elke methode gebaseerd is op sporen van elementen van . Eén 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:[1]

  1. 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.
  2. 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.
  3. 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) ∈ .
  4. 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.[8] 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[bewerken]

Keuze van p en q[bewerken]

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

  1. Vind r ∈ zodanig dat q = r2 - r + 1 een priemgetal is met Q bits.
  2. 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 r2 + 1 ≡ 2 (mod 3). 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 p ≡ 1 (mod 4) 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 = 17 ≡ 1 (mod 4). 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

  1. Kies een priemgetal q ≡ 7 (mod 12) dat Q bits heeft.
  2. Vind de nulpunten r1 en r2 van het polynoom X2 - X + 1 mod q.
  3. 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 = 19 ≡ 7 (mod 12) dan geldt (-7)2 - -7 + 1 = 57 ≡ 0 (mod 19) en 82 - 8 + 1 = 57 ≡ 0 (mod 19). Hieruit volgt dat r1 = -7 en r2 = 8. Kies vervolgens k = 6 dan p = r1 + kq = - 7 + 6*19 = 107 ≡ 2 (mod 3). 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[9]), heeft het gebruik van een grote XTR-ondergroep geen negatieve gevolgen voor de snelheid van de cryptografische bewerkingen. In deze situatie wordt de meest optimale keuze verkregen door p (gegeven dat p ≡ 2 (mod 3)) 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

  1. Kies een priemgetal p ≡ 2 (mod 3) 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 = 11 ≡ 2 (mod 3) 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[bewerken]

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[bewerken]

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(γxy) = γ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[bewerken]

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

  1. Alice kiest een geheim getal a = 4 uit het interval [2,14], berekent Tr(ga) = en stuurt dit naar Bob.
  2. Bob kiest een geheim getal b = 5 uit het interval [2,14], berekent Tr(gb) = en stuurt dit naar Alice.
  3. Alice ontvangt Tr(gb) van Bob en berekent Tr(gab) = , hiermee kan zij de privésleutel K bepalen.
  4. 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.