XTR (algoritme)

XTR (forkortelse for ECSTR - "Efficient and Compact Subgroup Trace Representation") er en offentlig nøglekrypteringsalgoritme baseret på beregningskompleksiteten af det diskrete logaritmeproblem . Fordelene ved denne algoritme frem for andre, der bruger denne idé, er højere hastighed og mindre nøglestørrelse.

Denne algoritme bruger en generator af en relativt lille undergruppe af orden ( er enkel) af undergruppen . Med det korrekte valg af har den diskrete logaritme i gruppen genereret af , den samme beregningsmæssige kompleksitet som i . XTR bruger aritmetik i stedet for , hvilket giver den samme sikkerhed, men med mindre beregnings- og dataoverførselsomkostninger. $g$ $q$ $q$ $GF(p^{6})^{*}$ $q$ $g$ $GF(p^{6})^{*}$ $GF(p^{2})$ $GF(p^{6})$

Teoretisk grundlag for XTR

Algoritmen arbejder i et begrænset felt . Overvej en gruppe af orden , og dens undergruppe af orden q , hvor p er et primtal , således at et andet tilstrækkeligt stort primtal q er en divisor af . En gruppe af orden q kaldes en XTR-undergruppe. Denne cykliske gruppe er en undergruppe og har en generator g . $GF(p^{6})$ $p^{2}-p+1$ $p^{2}-p+1$ $\langle g\rangle$ $GF(p^{6})^{*}$

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

Lad p være et primtal, således at p ≡ 2 mod 3 og p 2 - p + 1 er deleligt med et tilstrækkeligt stort primtal q . Da p 2 ≡ 1 mod 3 , genererer p . Således er det cirkulære polynomium irreducerbart i . Derfor danner rødderne og et optimalt normalgrundlag over og $(\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 er omkostningerne ved aritmetiske operationer som følger:

Beregning af x p kræver ikke multiplikation
Beregningen af x 2 kræver to gange ind $GF(p)$
Beregningen af xy kræver tre gange ind $GF(p)$
Beregning af xz-yzskræver fire gange i .: [1] $GF(p)$

Brug af fodspor i $GF(p^{2})$

De konjugerede elementer af i er: sig selv og , og deres sum er sporet . $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}}.

Udover:

{\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}}

Overvej generatoren af en XTR-gruppe af orden , hvor er et primtal. Da er en undergruppe af ordensgruppen , så . Udover, $g$ $q$ $q$ $\langle g\rangle$ $p^{2}-p+1$ $q\mid p^{2}-p+1$

p^{2}=p-1

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

På denne måde

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

Bemærk også, at konjugatet til elementet er , dvs. har en norm lig med 1. Nøgletræk ved XTR er, at det minimale polynomium i $g$ $en$ $g$ $g$ $GF(p^{2})$

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

forenklet til

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

Med andre ord er de konjugerede elementer, som rødderne af det minimale polynomium i , fuldstændig bestemt af sporet . Lignende ræsonnement gælder for enhver grad : $g$ $GF(p^{2})$ $g$ $g$

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

— dette polynomium er defineret som følger . $Tr(g^{n})$

Ideen med algoritmen er at erstatte med , altså beregne med i stedet for med. Men for at metoden skal være effektiv, en måde at hurtigt få ud af det tilgængelige . $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)$

Hurtig beregningsalgoritme ifølge [2] $Tr(g^{n})$ $Tr(g)$

Definition: For hver definerer vi: $c$ $GF(p^{2})$

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

Definition: Lad være rødderne i , og . Angiv: ${\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}.

Egenskaber og : $c_n$ $F(c,X)$

${\displaystyle c=c_{1))$
${\displaystyle c_{-n}=c_{np}=c_{n}^{p))$
$c_{n}\in GF(p^{2})$ til $n\in \mathbb {Z}$
${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{uv}+c_{u-2v))$ til $u,v\in \mathbb {Z}$
Enten har alle en rækkefølge, der er en divisor af og , eller også er alle i feltet . Især - er irreducerbar, hvis og kun hvis dens rødder har en orden, der er en divisor af og . ${\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)$ bringe på banen hvis og kun hvis $GF(p^{2})$ $c_{p+1}\in GF(p)$

Udtalelse: Lad . ${\displaystyle c,\!\ c_{n-1},c_{n},c_{n+1))$

Beregningen kræver to produktoperationer på marken . ${\displaystyle c_{2n}=c_{n}^{2}-2c_{n}^{p))$ $GF(p)$
Beregningen kræver fire produktoperationer på marken . ${\displaystyle c_{n+2}=c_{n+1}\cdot cc^{p}\cdot c_{n}+c_{n-1))$ $GF(p)$
Beregningen kræver fire produktoperationer på marken . ${\displaystyle c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p))$ $GF(p)$
Beregningen kræver fire produktoperationer på marken . ${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p))$ $GF(p)$

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

Algoritme til beregning af givet og $S_{n}(c)$ $n$ $c$

Når algoritmen anvendes til og , så bruges egenskab 2 til at opnå det endelige resultat $n<0$ $-n$ $c$
Kl , . $n=0$ $S_{0}(c)\!\ =(c^{p},3,c)$
Kl , . $n=1$ $S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})$
For bruger vi udtrykkene for og til at finde og hhv . $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)$
For at beregne introducerer vi $n>2$ $S_{n}(c)$

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

og hvis ikke ulige og hvis lige. Lad os indstille og finde ved hjælp af Statement, og . Lad i fremtiden,

{\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))

hvor og . For at gøre følgende i rækkefølge:

m_{j}\in {0,1}

m_{r}=1

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

Hvornår bruger vi til at finde . $m_{j}=0$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k}(c)$
Hvornår bruger vi til at finde . $m_{j}=1$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k+1}(c)$
Lad os erstatte med . $k$ ${\displaystyle 2k+m_{j))$

I slutningen af gentagelserne, og . Hvis n er lige, skal du bruge til at finde . $k=m$ $S_{\bar {m}}(c)={\bar {S}}_{m}(c)$ $S_{\bar {m}}(c)$ ${\bar {S}}_{m+1}(c)$

Valg af muligheder

Valg af felt og undergruppestørrelse

For at drage fordel af repræsentationen af gruppeelementer i form af deres spor og sikre tilstrækkelig datasikkerhed, er det nødvendigt at finde enkle og , hvor er karakteristikken for feltet , og , og er størrelsen af undergruppen og divisor . Angiv som og størrelserne og i bits. For at opnå det sikkerhedsniveau, som for eksempel RSA med en nøglelængde på 1024 bit giver, skal du vælge sådan, at , det vil sige a kan være omkring 160. Den første algoritme, der giver dig mulighed for at beregne sådanne primtal og er Algoritme EN. $s$ $q$ $s$ $GF(p^{6})$ $p\equiv 2\ {\text{mod}}\ 3$ $q$ $p^{2}-p+1$ $P$ $Q$ $s$ $q$ $P$ $6P>1024$ $P\ca. 170$ $Q$ $s$ $q$

Algoritme A

Lad os finde sådan, at tallet er et primtal af længde i bit. $r\in \mathbb {Z}$ $q=r^{2}-r+1$ $Q$
Lad os finde sådan, at tallet er et primtal af længdebit, såvel som . $k\in\mathbb{Z}$ $p=r+k\cdot q$ $P$ $p\equiv 2\ {\text{mod}}\ 3$

Korrekthed af algoritme A: Det er kun nødvendigt at verificere det , da alle de resterende egenskaber naturligvis er opfyldt på grund af de særlige forhold ved valget af og .

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

s

q

Det er let at se det 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

Algoritme A er meget hurtig, men kan være usikker, da den er sårbar over for et talfeltsigteangreb .

Den langsommere algoritme B er skånet for denne mangel.

Algoritme B

Lad os vælge et primtal af længde i bit, sådan at . $q$ $Q$ $q\equiv 7\ {\text{mod}}\ 12$
Lad os finde rødderne og . $r_{1}$ $r_{2}$ $X^{2}-X+1\ {\text{mod}}\ q$
Lad os finde sådan, at , er et simpelt -bit tal og på samme tid for $k\in\mathbb{Z}$ $p=r_{i}+k\cdot q$ $s$ $P$ $p\equiv 2\ {\text{mod}}\ 3$ $i\in \{1,2\}$

Korrekthed af algoritme B: Så snart vi vælger , er betingelsen (Siden og ) automatisk opfyldt. Det følger af denne udtalelse og den kvadratiske lov om gensidighed , at rødderne eksisterer .

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

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

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

3\midt 12

r_{1}

r_{2}

For at kontrollere det , overvej igen for og bemærk, at . Derfor , og er rødder , og derfor .

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

Undergruppevalg

I det foregående afsnit fandt vi størrelserne af både det endelige felt og den multiplikative undergruppe i . Nu skal vi finde en undergruppe i for nogle sådan, at . Det er dog ikke nødvendigt at søge efter et eksplicit element , det er nok at finde et element sådan for elementet af orden . Men givet kan XTR-gruppegeneratoren findes ved at finde roden til . For at finde dette , overveje ejendom 5 . Når man har fundet en sådan , bør man tjekke, om den virkelig er i orden , men først skal man vælge c\in GF(p²), sådan at F(c,\ X) er irreducerbar. Den enkleste tilgang er at vælge tilfældigt. $s$ $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)$

Udsagn: For en tilfældigt valgt er sandsynligheden for, at - er irreducerbar, større end 1/3. $c\in GF(p^{2})$ $F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]$

Grundlæggende søgealgoritme : $Tr(g)$

Lad os vælge en tilfældig . $c\in GF(p^{2})\backslash GF(p)$
Hvis - vi giver, vil vi vende tilbage til det første trin. $F(c,\ X)$
Lad os bruge søgealgoritmen . Lad os finde . $S_{n}(c)$ ${\displaystyle d=c_{(p^{2}-p+1)/q))$
Hvis rækkefølgen ikke er lig med , vender vi tilbage til det første trin. $d$ $q$
Lad . $Tr(g)=d$

Denne algoritme beregner feltelementets ækvivalent for en eller anden rækkefølge . [en] $GF(p^{2})$ $Tr(g)$ $g\in GF(p^{6})$ $q$

Eksempler

Diffie-Hellman Protocol

Antag, at Alice og Bob har en offentlig XTR-nøgle og ønsker at generere en delt privat nøgle . $\left(p,q,Tr(g)\right)$ $K$

Alice vælger et tilfældigt tal , så , beregner det og sender det til 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 modtager fra Alice, vælger en tilfældig sådan, at , beregner og sender til Alice. $Tr(g^{a})$ $b\in \mathbb {Z}$ $1<b<q-2$ $S_{b}(Tr(g))=\venstre(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 modtager fra Bob, beregner og modtager - den private nøgle . $Tr(g^{b})$ $S_{a}(Tr(g^{b}))=\venstre(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å samme måde beregner og henter Bob den private nøgle . $S_{b}(Tr(g^{a}))=\venstre(Tr(g^{a(b-1)}),Tr(g^{ab}),Tr(g^{a (b+1)})\right)\i GF(p^{2})^{3}$ $Tr(g^{ab})\in GF(p^{2})$ $K$

Ordning af ElGamal

Antag, at Alice har en del af den offentlige XTR-nøgle: . Alice vælger et hemmeligt heltal og beregner og udgiver . Givet Alices offentlige nøgle kan Bob kryptere meddelelsen, der er bestemt til Alice ved hjælp af følgende algoritme: $(p,q,Tr(g))$ $k$ $Tr(g^{k})$ $\left(p,q,Tr(g),Tr(g^{k})\right)$ $M$

Bob vælger en tilfældig og beregner . $b\in \mathbb {Z}$ $1<b<q-2$ $S_{b}(Tr(g))=\venstre(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right) \i GF(p^{2})^{3}$
Bob regner så ud . $S_{b}(Tr(g^{k}))=\venstre(Tr(g^{(b-1)k}),Tr(g^{bk}),Tr(g^{( b+1)k})\right)\i GF(p^{2})^{3}$
Bob definerer en symmetrisk nøgle baseret på . $K$ $Tr(g^{bk})\in GF(p^{2})$
Bob krypterer beskeden med nøglen og modtager den krypterede besked . $M$ $K$ $E$
Bob sender et par til Alice. $(Tr(g^{b}),\ E)$

Efter at have modtaget et par , dekrypterer Alice det som følger: $(Tr(g^{b}),\ E)$

Alice beregner . $S_{k}(Tr(g^{b}))=\venstre(Tr(g^{b(k-1)}),Tr(g^{bk}),Tr(g^{b (k+1)})\right)\i GF(p^{2})^{3}$
Alice definerer en symmetrisk nøgle baseret på . $K$ $Tr(g^{bk})\in GF(p^{2})$
Ved at vide, at meddelelseskrypteringsalgoritmen er symmetrisk, dekrypterer Alice med nøglen og modtager den originale meddelelse . $K$ $E$ $M$

Dermed sendes beskeden.

Noter

↑ 1 2 Lenstra, Arjen K.; Verheul, Eric R. En oversigt over XTR offentlige nøglesystem (indef.) . Arkiveret fra originalen den 15. april 2006.
↑ Lenstra, Arjen K.; Verheul, Eric R. XTR offentlige nøglesystem (ubestemt) .

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort