XTR (algoritm)

XTR (förkortning för ECSTR - "Efficient and Compact Subgroup Trace Representation") är en krypteringsalgoritm för offentlig nyckel som är baserad på beräkningskomplexiteten hos det diskreta logaritmproblemet . Fördelarna med denna algoritm jämfört med andra som använder denna idé är högre hastighet och mindre nyckelstorlek.

Denna algoritm använder en generator av en relativt liten undergrupp av ordning ( är enkel) av undergruppen . Med rätt val av har den diskreta logaritmen i gruppen som genereras av , samma beräkningskomplexitet som i . XTR använder aritmetik istället för , vilket ger samma säkerhet, men med mindre beräknings- och dataöverföringskostnader. $g$ $q$ $q$ $GF(p^{6})^{*}$ $q$ $g$ $GF(p^{6})^{*}$ $GF(p^{2})$ $GF(p^{6})$

Teoretisk grund för XTR

Algoritmen fungerar i ett ändligt fält . Betrakta en grupp av ordning , och dess undergrupp av ordning q , där p är ett primtal , så att ett annat tillräckligt stort primtal q är en divisor av . En grupp av ordningen q kallas en XTR-undergrupp. Denna cykliska grupp är en undergrupp och har en generator g . $GF(p^{6})$ $p^{2}-p+1$ $p^{2}-p+1$ $\langle g\rangle$ $GF(p^{6})^{*}$

Aritmetiska operationer i $GF(p^{2})$

Låt p vara ett primtal så att p ≡ 2 mod 3 och p 2 - p + 1 är delbart med ett tillräckligt stort primtal q . Eftersom p 2 ≡ 1 mod 3 genererar p . _ Således är det cirkulära polynomet irreducible i . Därför rötterna och bildar en optimal normal grund över och $(\mathbb {Z} /3\mathbb {Z} )^{*}$ $\Phi _{3}(x)=x^{2}+x+1$ $GF(p)$ $\alfa$ $\alpha ^{p}$ $GF(p^{2})$ $GF(p)$

GF(p^{2})\cong \{x_{1}\alpha +x_{2}\alpha ^{p}:x_{1},x_{2}\in GF(p)\} .

Givet p ≡ 2 mod 3 :

GF(p^{2})\cong \{y_{1}\alpha +y_{2}\alpha ^{2}:\alpha ^{2}+\alpha +1=0,y_{1 },y_{2}\i GF(p)\}.

Således är kostnaden för aritmetiska operationer som följer:

Att beräkna x p kräver inte multiplikation
Beräkningen av x 2 kräver två multiplikationer in $GF(p)$
Beräkningen av xy kräver tre multiplikationer in $GF(p)$
Beräknar xz-yzsidkräver fyra multiplikationer i .: [1] $GF(p)$

Användning av fotspår i $GF(p^{2})$

De konjugerade elementen i i är: sig själv och , och deras summa är spåret . $h\in GF(p^{6})$ $GF(p^{2})$ $h,h^{p^{2}}$ $h^{p^{4))$ $h$

Tr(h)=h+h^{p^{2}}+h^{p^{4}}.

Förutom:

{\begin{aligned}Tr(h)^{p^{2}}&=h^{p^{2}}+h^{p^{4}}+h^{p^{6 }}\\&=h+h^{p^{2}}+h^{p^{4}}\\&=Tr(h)\end{aligned}}

Betrakta generatorn av en XTR-grupp av ordning , där är ett primtal. Eftersom är en undergrupp till gruppen av ordning , alltså . Förutom, $g$ $q$ $q$ $\langle g\rangle$ $p^{2}-p+1$ $q\mid p^{2}-p+1$

p^{2}=p-1

och

p^{4}=(p-1)^{2}=p^{2}-2p+1=-p

På det här sättet,

{\begin{aligned}Tr(g)&=g+g^{p^{2}}+g^{p^{4}}\\&=g+g^{p-1}+ g^{-p}.\end{aligned}}

Observera också att konjugatet till elementet är , det vill säga har en norm lika med 1. Nyckelegenskapen för XTR är att det minimala polynomet i $g$ $ett$ $g$ $g$ $GF(p^{2})$

(xg)\!\ (xg^{p-1})(xg^{-p})

förenklat till

x^{3}-Tr(g)\!\ x^{2}+Tr(g)^{p}x-1

Med andra ord, de konjugerade elementen, som rötterna till det minimala polynomet i , bestäms helt av spåret . Liknande resonemang gäller för vilken grad som helst : $g$ $GF(p^{2})$ $g$ $g$

x^{3}-Tr(g^{n})\!\ x^{2}+Tr(g^{n})^{p}x-1

— detta polynom definieras enligt följande . $Tr(g^{n})$

Tanken med algoritmen är att ersätta med , det vill säga beräkna med istället för med. Men för att metoden ska vara effektiv, ett sätt att snabbt få ut från det tillgängliga . $g^{n}\in GF(p^{6})$ $Tr(g^{n})\in GF(p^{2})$ $Tr(g^{n})$ $Tr(g)$ $g^{n}$ $g$ $Tr(g^{n})$ $Tr(g)$

Snabb beräkningsalgoritm enligt [2] $Tr(g^{n})$ $Tr(g)$

Definition: För varje definierar vi: $c$ $GF(p^{2})$

F(c,X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X].

Definition: Låt vara rötterna i , och . Beteckna: ${\displaystyle h_{0},\!\ h_{1},h_{2))$ $F(c,X)$ $GF(p^{6})$ $n\in {\mathbb {Z}}$

c_{n}=h_{0}^{n}+h_{1}^{n}+h_{2}^{n}.

Egenskaper och : $c_n$ $F(c,X)$

${\displaystyle c=c_{1))$
${\displaystyle c_{-n}=c_{np}=c_{n}^{p))$
$c_{n}\in GF(p^{2})$ för $n\in \mathbb {Z}$
${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{uv}+c_{u-2v))$ för $u,v\in \mathbb {Z}$
Antingen har alla en ordning som är en divisor av och eller så är alla i fältet . I synnerhet är - irreducerbar om och endast om dess rötter har en ordning som är en divisor av och . ${\displaystyle h_{j))$ $p^{2}-p+1$ $>3$ ${\displaystyle h_{j))$ $GF(p^{2})$ $F(c,X)$ $p^{2}-p+1$ $>3$
$F(c,X)$ ta med till fältet om och bara om $GF(p^{2})$ $c_{p+1}\in GF(p)$

Uttalande: Låt . ${\displaystyle c,\!\ c_{n-1},c_{n},c_{n+1))$

Beräkningen kräver två produktoperationer på fältet . ${\displaystyle c_{2n}=c_{n}^{2}-2c_{n}^{p))$ $GF(p)$
Beräkningen kräver fyra produktoperationer på fältet . ${\displaystyle c_{n+2}=c_{n+1}\cdot cc^{p}\cdot c_{n}+c_{n-1))$ $GF(p)$
Beräkningen kräver fyra produktoperationer på fältet . ${\displaystyle c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p))$ $GF(p)$
Beräkningen kräver fyra produktoperationer på fältet . ${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p))$ $GF(p)$

Definition: Låt . ${\displaystyle S_{n}(c)=(c_{n-1},c_{n},c_{n+1})\in GF(p^{2})^{3))$

Algoritm för beräkning av given och $S_{n}(c)$ $n$ $c$

När algoritmen används för och används egenskap 2 för att erhålla det slutliga resultatet $n<0$ $-n$ $c$
Vid , . $n=0$ $S_{0}(c)\!\ =(c^{p},3,c)$
Vid , . $n=1$ $S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})$
För använder vi uttrycken för och för att hitta respektive . $n=2$ ${\displaystyle c_{n+2}=c_{n+1}\cdot cc^{p}\cdot c_{n}+c_{n-1))$ $S_{1}(c)$ $c_{3}$ $S_{2}(c)$
För att beräkna introducerar vi $n>2$ $S_{n}(c)$

{\bar {S}}_{i}(c)=S_{2i+1}(c)

och om inte udda och om jämnt. Låt oss ställa in och hitta med hjälp av Statement och . Låt i framtiden,

{\bar {m}}=n

n

{\bar {m}}=n-1

{\bar {m}}=2m+1,k=1

{\bar {S}}_{k}(c)=S_{3}(c)

S_{2}(c)

{\displaystyle m=\sum _{j=0}^{r}m_{j}2^{j))

var och . För att göra följande i följd:

m_{j}\in {0,1}

m_{r}=1

j=r-1,r-2,...,0

När använder vi för att hitta . $m_{j}=0$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k}(c)$
När använder vi för att hitta . $m_{j}=1$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k+1}(c)$
Låt oss ersätta med . $k$ ${\displaystyle 2k+m_{j))$

I slutet av iterationerna , och . Om n är jämnt, använd för att hitta . $k=m$ $S_{\bar {m}}(c)={\bar {S}}_{m}(c)$ $S_{\bar {m}}(c)$ ${\bar {S}}_{m+1}(c)$

Val av alternativ

Val av fält och undergruppsstorlek

För att dra fördel av representationen av gruppelement i form av deras spår och säkerställa tillräcklig datasäkerhet, är det nödvändigt att hitta enkla och , där är kännetecknet för fältet , och , och är storleken på undergruppen och divisor . Ange som och storlekarna och i bitar. För att uppnå den säkerhetsnivå som till exempel RSA med en nyckellängd på 1024 bitar ger måste du välja sådan att , det vill säga a kan vara cirka 160. Den första algoritmen som låter dig beräkna sådana primtal och är Algoritm A. $sid$ $q$ $sid$ $GF(p^{6})$ $p\equiv 2\ {\text{mod}}\ 3$ $q$ $p^{2}-p+1$ $P$ $F$ $sid$ $q$ $P$ $6P>1024$ $P\approx 170$ $F$ $sid$ $q$

Algoritm A

Låt oss hitta sådana att talet är ett primtal av längden i bitar. $r\in \mathbb {Z}$ $q=r^{2}-r+1$ $F$
Låt oss hitta sådana att talet är ett primtal av längdbitar, liksom . $k\in\mathbb{Z}$ $p=r+k\cdot q$ $P$ $p\equiv 2\ {\text{mod}}\ 3$

Korrekthet av Algoritm A: Det är bara nödvändigt att verifiera det , eftersom alla återstående egenskaper uppenbarligen är uppfyllda på grund av detaljerna i valet av och .

q\mid p^{2}-p+1

sid

q

Det är lätt att se att , betyder .

p^{2}-p+1=r^{2}+2rkq+k^{2}q^{2}-r-kq+1=r^{2}-r+1+q( 2rk+k^{2}qk)=q(1+2rk+k^{2}qk)

q\mid p^{2}-p+1

Algoritm A är mycket snabb, men kan vara osäker, eftersom den är sårbar för en sifferfältsattack .

Den långsammare algoritmen B är skonad från denna brist.

Algoritm B

Låt oss välja ett primtal för längden i bitar, så att . $q$ $F$ $q\equiv 7\ {\text{mod}}\ 12$
Låt oss hitta rötterna och . $r_{1}$ $r_{2}$ $X^{2}-X+1\ {\text{mod}}\ q$
Låt oss hitta sådant att , är ett enkelt -bittal och samtidigt för $k\in\mathbb{Z}$ $p=r_{i}+k\cdot q$ $sid$ $P$ $p\equiv 2\ {\text{mod}}\ 3$ $i\in \{1,2\}$

Korrekthet av algoritm B: Så snart vi väljer är villkoret (Sedan och ) automatiskt uppfyllt. Det följer av detta uttalande och den kvadratiska lagen om ömsesidighet att rötterna finns .

q\equiv 7\ {\text{mod}}\ 12

q\equiv 1\ {\text{mod}}\ 3

7\equiv 1\ {\text{mod}}\ 3

3\mid 12

r_{1}

r_{2}

För att kontrollera att , överväg igen för och notera att . Därför och är rötter och därför .

q\mid p^{2}-p+1

p^{2}-p+1

r_{i}\in \{1,2\}

p^{2}-p+1=r_{i}^{2}+2r_{i}kq+k^{2}q^{2}-r_{i}-kq+1=r_{ i}^{2}-r_{i}+1+q(2rk+k^{2}qk)=q(2rk+k^{2}qk)

r_{1}

r_{2}

X^{2}-X+1

q\mid p^{2}-p+1

Val av undergrupp

I föregående avsnitt hittade vi storlekarna på både det sista fältet och den multiplikativa undergruppen i . Nu måste vi hitta en undergrupp för några sådana som . Det är dock inte nödvändigt att söka efter ett explicit element , det räcker att hitta ett element så att för elementet ordning . Men givet kan XTR-gruppgeneratorn hittas genom att hitta roten till . För att hitta detta , överväg egenskap 5 . Efter att ha hittat en sådan bör man kontrollera om den verkligen är i sin ordning , men först måste man välja c\in GF(p²), så att F(c,\ X) är irreducerbar. Det enklaste sättet är att välja slumpmässigt. $sid$ $q$ $GF(p^{6})$ $GF(p^{6})^{*}$ $\langle g\rangle$ $GF\!\ (p^{6})^{*}$ $g\in GF(p^{6})$ $\mid \!\!\langle g\rangle \!\!\mid =q$ $g\in GF(p^{6})$ $c\in GF(p^{2})$ $c=Tr(g)$ $g\in GF(p^{6})$ $q$ $Tr(g)$ $g$ $F(Tr(g),\ X)$ $c$ $F(c,\ X)$ $c$ $q$ $c\in GF(p^{2})\backslash GF(p)$

Påstående: För en slumpmässigt vald är sannolikheten att - är irreducerbar större än 1/3. $c\in GF(p^{2})$ $F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]$

Grundläggande sökalgoritm : $Tr(g)$

Låt oss välja en slumpmässig . $c\in GF(p^{2})\backslash GF(p)$
Om - vi ger, kommer vi tillbaka till det första steget. $F(c,\ X)$
Låt oss använda sökalgoritmen . Låt oss hitta . $S_{n}(c)$ ${\displaystyle d=c_{(p^{2}-p+1)/q))$
Om ordningen inte är lika med , återgår vi till det första steget. $d$ $q$
Låt . $Tr(g)=d$

Denna algoritm beräknar fältelementets ekvivalent för någon ordning . [ett] $GF(p^{2})$ $Tr(g)$ $g\in GF(p^{6})$ $q$

Exempel

Diffie-Hellman Protocol

Anta att Alice och Bob har en offentlig XTR-nyckel och vill generera en delad privat nyckel . $\left(p,q,Tr(g)\right)$ $K$

Alice väljer ett slumpmässigt tal så att , beräknar det och skickar det till Bob. $a\in \mathbb {Z}$ $1<a<q-2$ $S_{a}(Tr(g))=\left(Tr(g^{a-1}),Tr(g^{a}),Tr(g^{a+1})\right) \i GF(p^{2})^{3}$ $Tr(g^{a})\in GF(p^{2})$
Bob tar emot från Alice, väljer en slumpmässig sådan att , beräknar och skickar till Alice. $Tr(g^{a})$ $b\in \mathbb {Z}$ $1<b<q-2$ $S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right) \i GF(p^{2})^{3}$ $Tr(g^{b})\in GF(p^{2})$
Alice tar emot från Bob, beräknar och tar emot - den privata nyckeln . $Tr(g^{b})$ $S_{a}(Tr(g^{b}))=\left(Tr(g^{(a-1)b}),Tr(g^{ab}),Tr(g^{( a+1)b})\right)\i GF(p^{2})^{3}$ $Tr(g^{ab})\in GF(p^{2})$ $K$
På samma sätt beräknar och erhåller Bob den privata nyckeln . $S_{b}(Tr(g^{a}))=\left(Tr(g^{a(b-1)}),Tr(g^{ab}),Tr(g^{a (b+1)})\höger)\i GF(p^{2})^{3}$ $Tr(g^{ab})\in GF(p^{2})$ $K$

Schema för ElGamal

Anta att Alice har en del av den publika XTR-nyckeln: . Alice väljer ett hemligt heltal och beräknar och publicerar . Med tanke på Alices publika nyckel kan Bob kryptera meddelandet som är avsett för Alice med hjälp av följande algoritm: $(p,q,Tr(g))$ $k$ $Tr(g^{k})$ $\left(p,q,Tr(g),Tr(g^{k})\right)$ $M$

Bob väljer en slumpmässig och beräknar . $b\in \mathbb {Z}$ $1<b<q-2$ $S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right) \i GF(p^{2})^{3}$
Bob räknar sedan ut . $S_{b}(Tr(g^{k}))=\left(Tr(g^{(b-1)k}),Tr(g^{bk}),Tr(g^{( b+1)k})\höger)\i GF(p^{2})^{3}$
Bob definierar en symmetrisk nyckel baserat på . $K$ $Tr(g^{bk})\in GF(p^{2})$
Bob krypterar meddelandet med nyckeln och tar emot det krypterade meddelandet . $M$ $K$ $E$
Bob skickar ett par till Alice. $(Tr(g^{b}),\ E)$

Efter att ha fått ett par , dekrypterar Alice det enligt följande: $(Tr(g^{b}),\ E)$

Alice räknar ut . $S_{k}(Tr(g^{b}))=\left(Tr(g^{b(k-1)}),Tr(g^{bk}),Tr(g^{b (k+1)})\höger)\i GF(p^{2})^{3}$
Alice definierar en symmetrisk nyckel baserad på . $K$ $Tr(g^{bk})\in GF(p^{2})$
Eftersom Alice vet att meddelandekrypteringsalgoritmen är symmetrisk, dekrypterar Alice med nyckeln och tar emot det ursprungliga meddelandet . $K$ $E$ $M$

Sålunda sänds meddelandet.

Anteckningar

↑ 1 2 Lenstra, Arjen K.; Verheul, Eric R. En översikt av XTR:s publika nyckelsystem (indef.) . Arkiverad från originalet den 15 april 2006.
↑ Lenstra, Arjen K.; Verheul, Eric R. XTR:s publika nyckelsystem (obestämd) .

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort