XTR

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 $\mathbb {F} _{p}^{*}$ van een priemlichaam $\mathbb {F} _{p}$. 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.

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.
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 p² − p + 1 waarbij p ≡ 2 (mod 3). Omdat p² − p + 1 een deler is van p⁶ − 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 p² − p + 1 is. De orde van g deelt niet p^s − 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 (X³−1)/(X−1)=X²+X+1 een optimale normale basis vormen voor $\mathbb {F} _{p^{2}}$ over $\mathbb {F} _{p}$, met andere woorden $\mathbb {F} _{p^{2}}$ $\cong$ {x₁α + x₂α^p: x₁, x₂ ∈ $\mathbb {F} _{p}$}. Maar aangezien er ook αⁱ = α^{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α²; bijvoorbeeld het element 3 is voorgesteld als −3α−3α². Aan de hand van deze voorstelling kunnen de bijbehorende kosten voor de bewerkingen in $\mathbb {F} _{p^{2}}$ worden bepaald. Kies x₁α + x₂α² ∈ $\mathbb {F} _{p^{2}}$. Dit element kan op de volgende manier gekwadrateerd worden (x₁α + x₂α²)² = 2x₁x₂ + x₂²α + x₁²α² = −2x₁x₂α −2x₁x₂α² + x₂²α + x₁²α² = x₂(x₂ − 2x₁)α + x₁(x₁ − 2x₂)α² 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}$). De overige bewerkingen voor elementen uit $\mathbb {F} _{p^{2}}$ 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 $\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)).
De functie Tr(·) is een homomorfisme van $\mathbb {F} _{p^{6}}$ naar $\mathbb {F} _{p^{2}}$, die beide lichamen van karakteristiek p zijn:
Tr(h₁+h₂) = (h₁+h₂) + (h₁+h₂)^p2 + (h₁+h₂)^p4 = h₁ + h₂ + h₁^p2 + h₂^p2 + h₁^p4 +h ₂^p4 = Tr(h₁) + Tr(h₂).
Tr(c·h₁) = c·h₁ + c^p2·h₁^p2 + c^p4·h₁^p4 = c·h₁ + c·h₁^p2 + c·h₁^p4 = c·Tr(h₁),
met h₁, h₂ $\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

Binnen XTR zijn er verschillende methoden om sleutels te genereren, hoewel elke methode gebaseerd is op sporen van elementen van $\mathbb {F} _{p^{6}}$. 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:

1. Alice kiest een willekeurig geheel getal a in het interval [2,q − 3] en berekent
   S_a(Tr(g)) = (Tr(g^a−1),Tr(g^a),Tr(g^a+1)) ∈ $\mathbb {F} _{p^{2}}^{3}$,
   en stuurt Tr(g^a) ($\in \mathbb {F} _{p^{2}}$) naar Bob.
2. Bob ontvangt Tr(g^a), kiest een willekeurig geheel getal b in het interval [2,q − 3] en berekent
   S_b(Tr(g))=(Tr(g^b−1),Tr(g^b),Tr(g^b+1)) ∈ $\mathbb {F} _{p^{2}}^{3}$,
   en stuurt Tr(g^b) ($\in \mathbb {F} _{p^{2}}$) naar Alice.
3. Alice ontvangt Tr(g^b) en berekent
   S_a(Tr(g)^b) = (Tr(g^(a-1)b),Tr(g^ab),Tr(g^(a+1)b)) ∈ $\mathbb {F} _{p^{2}}^{3}$,
   en bepaalt K op basis van Tr(g^ab) ∈ $\mathbb {F} _{p^{2}}$.
4. Bob berekent
   S_b(Tr(g)^a) = (Tr(g^a(b−1)),Tr(g^ab),Tr(g^a(b+1))) ∈ $\mathbb {F} _{p^{2}}^{3}$,
   en bepaalt K op basis van Tr(g^ab) ∈ $\mathbb {F} _{p^{2}}$.

Voor het berekenen van de sporen, zoals bijvoorbeeld in S_a(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
S₀(Tr(g)) = (Tr(g)^p, 3, Tr(g));
S₁(Tr(g)) = (3, Tr(g), Tr(g)² − 2Tr(g)^p);
S₂(Tr(g)) = (Tr(g), Tr(g)² − 2Tr(g)^p, Tr(g)³ − 3Tr(g)^p+1 + 3^p) en
S₃ = (Tr(g)² − 2Tr(g)^p, Tr(g)³ − 3Tr(g)^p+1 + 3^p, 2Tr(g)^2p + Tr(g)⁴ − 4Tr(g)^p+2 + (3^p+1)Tr(g)).
We definiëren S_i '(Tr(g)) = S_2i+1(Tr(g)) en Tr(g)_n = Tr(gⁿ).
Laat $m=\sum _{j=0}^{r}m_{j}2^{j}$ en $m_{j}\in {0,1}.$
Ook is Tr(g)_2n = Tr(g²ⁿ) = Tr(gⁿ)² + 2Tr(gⁿ)^p,
Tr(g)_n+2 = Tr(gⁿ⁺²) = Tr(g) Tr(gⁿ⁺¹) − Tr(g)^p Tr(gⁿ) + Tr(gⁿ⁻¹),
Tr(g)_2n−1 = Tr(g^2n-1) = Tr(gⁿ⁻¹) Tr(gⁿ) − Tr(g)^p Tr(gⁿ)^p + Tr(gⁿ⁺¹)^p en
Tr(g)_2n+1 = Tr(g²ⁿ⁻¹) = Tr(gⁿ⁺¹) Tr(gⁿ) - Tr(g) Tr(gⁿ)^p + Tr(gⁿ⁻¹)^p.

Het algoritme loopt nu alle waarden van j na (voor j = r − 1, r − 2, ... , 0):

• Als m_j = 0, bereken dan

S_2k' (Tr(g)) = (Tr(g)_4k,Tr(g)_4k+1,Tr(g)_4k+2) aan de hand van
S_k' (Tr(g)) = (Tr(g)_2k,Tr(g)_2k+1,Tr(g)_2k+2).

• Als m_j = 1, bereken dan

S_2k+1' (Tr(g)) = (Tr(g)_4k+2,Tr(g)_4k+3,Tr(g)_4k+4) aan de hand van
S_2k' (Tr(g)) = (Tr(g)_2k,Tr(g)_2k+1,Tr(g)_2k+2).

• Vervang k := 2k+m_j, j := j−1.

Na alle iteraties is k = m en is de laatste uitkomst S_a(Tr(g)). Als a oneven was, bevat deze de gezochte waarde Tr(g^a). Als a even was, moet S_a+1(Tr(g)) berekend worden aan de hand van S_a(Tr(g)).

In 2001 hebben Lenstra en Stam aangetoond dat deze sporen, zoals Tr(g^a), 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 S_k (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 p² − 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 = r² − r + 1 een priemgetal is met Q bits.
2. Vind k ∈ $\mathbb {Z}$ zodanig dat p = r + kq = kr² + (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 r² − r + 1 als r² + 1 priemgetallen zijn én r² + 1 ≡ 2 (mod 3). Hieruit volgt dat r een even getal moet zijn. Wanneer we p = r² + 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 = r² − r + 1 = 4² - 4 + 1 = 13 hetgeen een priemgetal is evenals p = r² + 1 = 4² + 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 r₁ en r₂ van het polynoom X² − X + 1 mod q.
3. Vind k ∈ $\mathbb {Z}$ zodanig dat p = r_i + 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)² − −7 + 1 = 57 ≡ 0 (mod 19) en 8² − 8 + 1 = 57 ≡ 0 (mod 19). Hieruit volgt dat r₁ = −7 en r₂ = 8. Kies vervolgens k = 6 dan p = r₁ + 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), 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 p ≡ 2 (mod 3)) zodanig te kiezen zodat (p² - 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 p² − 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 p² − p + 1 = 11² - 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 ∈ $\mathbb {F} _{p^{6}}$ van orde q, waar q een deler is van p² − 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

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(γ^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 $\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 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 $\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 p² – p + 1 en dat g^q = 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)=14h_{1}+16h_{2}+2h_{3}+4h_{4}+6h_{5}+3h_{6}\in \mathbb {F} _{p};f_{2}(h)=14h_{1}+3h_{3}+2h_{4}+h_{5}+15h_{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(g^a) = $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(g^b) = $2\alpha +3\alpha ^{2}\in \mathbb {F} _{p^{2}}$ en stuurt dit naar Alice.
3. Alice ontvangt Tr(g^b) van Bob en berekent Tr(g^ab) = $3\alpha +2\alpha ^{2}\in \mathbb {F} _{p^{2}}$, hiermee kan zij de privésleutel K bepalen.
4. Bob ontvangt Tr(g^a) van Alice en berekent Tr(g^ab) = $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