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 het 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 \mathbb F_p^* van een priemlichaam \mathbb F_p.[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 \mathbb F_{p^n} in plaats van een priemlichaam \mathbb F_p 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 \mathbb F_p^* 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 \mathbb F_{p^6}^*, deelt q ook de orde van de groep \mathbb F_{p^6}^*. Dit betekent dat g een ondergroep van \mathbb F_{p^6}^* 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 \mathbb F_{p^6}. 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 \mathbb F_{p^2}. Het berekenen van deze machten is heel efficiënt aangezien alle bewerkingen in het lichaam \mathbb F_{p^2} plaatsvinden in plaats van \mathbb F_{p^6}. Op deze manier is het construeren van \mathbb F_{p^6} overbodig. Er is slechts een constructie van \mathbb F_{p^2} nodig . Verder moet er ook worden opgemerkt dat een voorstelling van \mathbb F_{p^6} 6log p bits gebruikt terwijl het representeren van \mathbb F_{p^2} slechts 2log p bits kost.
Uit p ≡ 2 (mod 3) volgt dat p mod 3 de groep \mathbb F_3^* genereert zodat de nulpunten α en αp van het polynoom (X3-1)/(X-1)=X2+X+1 een optimale normale basis vormen voor \mathbb F_{p^2} over \mathbb F_p, met andere woorden \mathbb F_{p^2} \cong {x1α + x2αp: x1, x2\mathbb F_p}. Maar aangezien er ook αi = αi mod 3 geldt, wordt de uiteindelijk voorstelling

\mathbb F_{p^2}\cong \{x_1\alpha+x_2\alpha^2: \alpha^2+\alpha+1=0 \text{ en } x_1,x_2  \in \mathbb F_p\} .

In deze representatie wordt een element t uit \mathbb F_{p} 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 \mathbb F_{p^2} worden bepaald. Kies x1α + x2α2\mathbb F_{p^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 \mathbb F_p. Hierbij is er aangenomen dat optellen (en dus ook aftrekken) in \mathbb F_p geen kosten vereist. Er blijkt dat het kwadrateren van een element uit \mathbb F_{p^6} 14.4 vermenigvuldigingen vergt in \mathbb F_p (hierbij neemt men aan dat kwadrateren in \mathbb F_p 80% van de tijd kost van een vermenigvuldiging in \mathbb F_p).[6] De overige bewerkingen voor elementen uit \mathbb F_{p^2} 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  \mathbb F_{p^6} . Dan is h geconjugeerd aan de elementen h, h p2 en h p4 over  \mathbb F_{p^2} . De som van deze elementen is gedefinieerd als het spoor van element h, ofwel Tr(h) = h + h p 2 + h p 4  \in \mathbb F_{p^2} (want Tr(h) p 2 = Tr(h)).[7]
De functie Tr(·) is een homomorfisme van  \mathbb F_{p^6} naar  \mathbb F_{p^2} , welke 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 \in \mathbb F_{p^6} en c  \in \mathbb F_{p^2} .
Hierdoor is optelling en scalaire vermenigvuldiging eenvoudig binnen  \mathbb F_{p^2} . Er is echter geen eenvoudige vermenigvuldiging mogelijk, want in principe geldt:  Tr(h_1 \cdot h_2) \neq Tr(h_1) \cdot Tr(h_2). Het voordeel van het voorstellen van elementen aan de hand van hun sporen is dat alles (elementen en bewerkingen) in \mathbb F_{p^2} plaatsvindt, waardoor het aantal bits met een factor drie gereduceerd wordt. Echter kunnen elementen niet meer onderscheiden worden van hun geconjugeerden (over \mathbb F_{p^2} ).

Sleutels[bewerken]

Binnen XTR zijn er verschillende methoden om sleutels te genereren, hoewel elke methode gebaseerd is op sporen van elementen van  \mathbb F_{p^6} . 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)) ∈ \mathbb F_{p^2} ^3,
    en stuurt Tr(ga) ( \in \mathbb F_{p^2}) 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)) ∈ \mathbb F_{p^2} ^3,
    en stuurt Tr(gb) ( \in \mathbb F_{p^2}) 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)) ∈ \mathbb F_{p^2} ^3,
    en bepaalt K op basis van Tr(gab) ∈ \mathbb F_{p^2}.
  4. Bob berekent
    Sb(Tr(g)a) = (Tr(ga(b-1)),Tr(gab),Tr(ga(b+1))) ∈ \mathbb F_{p^2} ^3,
    en bepaalt K op basis van Tr(gab) ∈ \mathbb F_{p^2}.

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  m= \sum_{j=0}^{r} m_j 2^j en  m_j \in {0,1}.
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 \mathbb F_{p^2} 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 \mathbb F_{p^6} 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 ∈ \mathbb{Z} zodanig dat q = r2 - r + 1 een priemgetal is met Q bits.
  2. Vind k ∈ \mathbb{Z} 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 \mathbb F_p. 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 ∈ \mathbb{Z} 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\mathbb F_{p^6} 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 \mathbb F_{p^2} om \mathbb F_{p^6} te representeren, ook kan een irreducibele zesdegraadsveelterm over \mathbb F_{p} gekozen worden. Vervolgens wordt er een element h\mathbb F_{p^6} 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 \mathbb F_{p^6}^*.
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 het discreet 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 \mathbb F_{p^6}^* 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 \mathbb F_{p^6}^* 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 \mathbb F_{p^s} van \mathbb F_{p^6} voor s=1,2,3, is de verwachte looptijd van dit algoritme: L [ p^6 , 0.333 , 1.923 ] met  L[n,v,u] =  \exp((u+o(1))(\ln(n))^v(\ln(\ln(n)))^{1-v})
Voor de tweede aanval kan het best de Pollards rho-algoritme gekozen worden, dit leidt tot O(\sqrt{q}) berekeningen in <g>.
Als p en q beide uit 170 bits bestaan, dan is het discreet 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 \mathbb F_{p^6} 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   \in \mathbb F_{p^6 }:
p = 17
q = 13

\mathbb F_{p^6}\cong \{y_1 +y_2\beta+y_3\beta^2+y_4\beta^3+y_5\beta^4+y_6\beta^5: 12+ 2\beta+8\beta^2+13\beta^3+\beta^4+11\beta^5+6 \beta^6=0 \text{ en } y_i \in \mathbb F_{p}\}

\mathbb F_{p^2}\cong \{x_1 \alpha+x_2\alpha^2: \alpha^2+ \alpha+1=0 \text{ en } x_1,x_2  \in \mathbb F_p\}

Tr(h) = f_1(h) \alpha + f_2(h) \alpha^2 \in \mathbb F_{p^2} \text{ met } \alpha = 14 +12 \beta + 14 \beta^2 + 4 \beta^3 + 16 \beta^4 + 12 \beta^5 ; \alpha^2 = -1 - \alpha

f_1(h) = 14 h_1 + 16 h_2 + 2 h_3 + 4 h_4 + 6 h_5 + 3 h_6 \in \mathbb F_{p}; f_2(h) = 14 h_1 + 3 h_3 + 2 h_4 + h_5 + 15 h_6 \in \mathbb F_{p}

g = 9+2 \beta +10 \beta ^2 + 8 \beta ^3 + 9 \beta ^4 + 10 \beta ^5 \in \mathbb F_{p^6 }

<g> =\{g^i:1\leq i \leq q\} \subset \mathbb F_{p^6}  \text{  (de XTR-groep)}

 Tr(g) = 5 \alpha + 8 \alpha^2 \in \mathbb F_{p^2}

Vorming privésleutel K

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

Bronnen, noten en/of referenties
  1. a b An overview of the XTR public key system
  2. New Directions in Cryptography
  3. A Public Key Cryptosystem and a Signature scheme Based on Discrete Logarithms
  4. C.P.Schnorr, Efficient signature generation by smart cards, Journal of Cryptology, 4 (1991), 161-174
  5. Doing more with fewer bits
  6. The XTR public key system
  7. S. Lang, Algebra, Graduate Texts in Mathematics. 211. Berlin, New York: Springer-Verlag, 2002
  8. Speeding up XTR
  9. P.C. van Oorschot, M.J. Wiener, "On Diffie-Hellman key agreement with short exponents", Proceedings of Eurocrypt '96, LNCS 1070, Springer-Verlag 1996, 332-343