XTR (algoritm)

XTR (prescurtare de la ECSTR - „Efficient and Compact Subgroup Trace Representation”) este un algoritm de criptare cu cheie publică bazat pe complexitatea de calcul a problemei logaritmului discret . Avantajele acestui algoritm față de alții care folosesc această idee sunt viteza mai mare și dimensiunea mai mică a tastei.

Acest algoritm folosește un generator al unui subgrup relativ mic de ordin ( este simplu) al subgrupului . Cu alegerea corectă a , logaritmul discret din grupul generat de , are aceeași complexitate de calcul ca și în . XTR folosește aritmetica în loc de , oferind aceeași securitate, dar cu mai puține cheltuieli de calcul și transfer de date. $g$ $q$ $q$ $GF(p^{6})^{*}$ $q$ $g$ $GF(p^{6})^{*}$ $GF(p^{2})$ $GF(p^{6})$

Baza teoretică a XTR

Algoritmul funcționează într-un câmp finit . Considerăm un grup de ordin și subgrupul său de ordin q , unde p este un număr prim , astfel încât un alt număr prim suficient de mare q este un divizor al lui . Un grup de ordinul q se numește subgrup XTR. Acest grup ciclic este un subgrup și are un generator g . $GF(p^{6})$ $p^{2}-p+1$ $p^{2}-p+1$ $\langle g\rangle$ $GF(p^{6})^{*}$

Operații aritmetice în $GF(p^{2})$

Fie p un număr prim astfel încât p ≡ 2 mod 3 și p 2 - p + 1 este divizibil cu un prim suficient de mare q . Deoarece p 2 ≡ 1 mod 3 , p generează . Astfel, polinomul circular este ireductibil în . Prin urmare, rădăcinile și formează o bază normală optimă peste și $(\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)\} .

Dat p ≡ 2 mod 3 :

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

Astfel, costul operațiilor aritmetice este după cum urmează:

Calcularea x p nu necesită înmulțire
Calculul lui x 2 necesită două înmulțiri în $GF(p)$
Calculul lui xy necesită trei înmulțiri în $GF(p)$
Calcularea xz-yzpnecesită patru înmulțiri în .: [1] $GF(p)$

Utilizarea amprentelor în $GF(p^{2})$

Elementele conjugate ale lui în sunt: sine și , iar suma lor este urma . $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}}.

In afara de asta:

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

Luați în considerare generatorul unui grup XTR de ordin , unde este un număr prim. Deoarece este un subgrup al grupului de ordine , atunci . In afara de asta, $g$ $q$ $q$ $\langle g\rangle$ $p^{2}-p+1$ $q\mid p^{2}-p+1$

p^{2}=p-1

și

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

În acest fel,

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

Rețineți, de asemenea, că conjugatul cu elementul este , adică are o normă egală cu 1. Caracteristica cheie a XTR este că polinomul minim din $g$ $unu$ $g$ $g$ $GF(p^{2})$

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

simplificat la

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

Cu alte cuvinte, elementele conjugate , ca rădăcinile polinomului minim în , sunt complet determinate de urma . Raționament similar este valabil pentru orice grad : $g$ $GF(p^{2})$ $g$ $g$

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

— acest polinom este definit după cum urmează . $Tr(g^{n})$

Ideea algoritmului este să înlocuiască cu , adică să se calculeze cu în loc de cu. Cu toate acestea, pentru ca metoda să fie eficientă, o modalitate de a obține rapid din disponibilul . $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)$

Algoritm de calcul rapid conform [2] $Tr(g^{n})$ $Tr(g)$

Definiție: Pentru fiecare definim: $c$ $GF(p^{2})$

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

Definiție: Fie rădăcinile în , și . Denota: $h_{0},\!\ h_{1},h_{2}$ $F(c,X)$ $GF(p^{6})$ $n\în {\mathbb {Z}}$

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

Proprietăți și : $c_n$ $F(c,X)$

$c=c_{1)$
$c_{-n}=c_{np}=c_{n}^{p)$
$c_{n}\in GF(p^{2})$ pentru $n\in \mathbb {Z}$
${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{uv}+c_{u-2v))$ pentru $u,v\in \mathbb {Z}$
Fie toate au un ordin care este un divizor al lui și , fie toate sunt în câmp . În special, - este ireductibil dacă și numai dacă rădăcinile sale au un ordin care este un divizor al lui și . $h_{j)$ $p^{2}-p+1$ $>3$ $h_{j)$ $GF(p^{2})$ $F(c,X)$ $p^{2}-p+1$ $>3$
$F(c,X)$ aduce pe teren dacă și numai dacă $GF(p^{2})$ $c_{p+1}\in GF(p)$

Afirmație: Să . ${\displaystyle c,\!\ c_{n-1},c_{n},c_{n+1))$

Calculul necesită două operațiuni de produs pe teren . ${\displaystyle c_{2n}=c_{n}^{2}-2c_{n}^{p))$ $GF(p)$
Calculul necesită patru operațiuni de produs pe teren . ${\displaystyle c_{n+2}=c_{n+1}\cdot cc^{p}\cdot c_{n}+c_{n-1))$ $GF(p)$
Calculul necesită patru operațiuni de produs pe teren . $c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p)$ $GF(p)$
Calculul necesită patru operațiuni de produs pe teren . ${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p))$ $GF(p)$

Definiție: Fie . $S_{n}(c)=(c_{n-1},c_{n},c_{n+1})\in GF(p^{2})^{3)$

Algoritm pentru calculul dat și $S_{n}(c)$ $n$ $c$

Când se aplică algoritmul pentru și , atunci proprietatea 2 este utilizată pentru a obține rezultatul final $n<0$ $-n$ $c$
La , . $n=0$ $S_{0}(c)\!\ =(c^{p},3,c)$
La , . $n=1$ $S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})$
Pentru , folosim expresiile pentru și pentru a găsi și, respectiv, . $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)$
Pentru , pentru a calcula , introducem $n>2$ $S_{n}(c)$

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

iar dacă nu impar și dacă par. Să setăm și să găsim folosind Statement și . Să, în viitor,

{\bar {m}}=n

n

{\bar {m}}=n-1

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

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

S_{2}(c)

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

unde si . Pentru a face următoarele în secvență:

m_{j}\in {0,1}

m_{r}=1

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

Când , obișnuim să găsim . $m_{j}=0$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k}(c)$
Când , obișnuim să găsim . $m_{j}=1$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k+1}(c)$
Să înlocuim cu . $k$ $2k+m_{j)$

La sfârșitul iterațiilor , și . Dacă n este par, folosiți pentru a găsi . $k=m$ $S_{\bar {m}}(c)={\bar {S}}_{m}(c)$ $S_{\bar {m}}(c)$ ${\bar {S}}_{m+1}(c)$

Alegerea opțiunilor

Alegerea câmpului și a mărimii subgrupului

Pentru a profita de reprezentarea elementelor grupului sub forma urmelor lor și pentru a asigura o securitate suficientă a datelor, este necesar să găsiți simplu și , unde este caracteristica câmpului , și , și este dimensiunea subgrupului și divizorului . Notați ca și dimensiunile și în biți. Pentru a atinge nivelul de securitate pe care îl oferă, de exemplu, RSA cu o lungime a cheii de 1024 de biți, trebuie să alegeți astfel încât , adică a poate fi de aproximativ 160. Primul algoritm care vă permite să calculați astfel de prime și este algoritmul A. $p$ $q$ $p$ $GF(p^{6})$ $p\equiv 2\ {\text{mod}}\ 3$ $q$ $p^{2}-p+1$ $P$ $Q$ $p$ $q$ $P$ $6P>1024$ $P\aproximativ 170$ $Q$ $p$ $q$

Algoritmul A

Să găsim astfel încât numărul să fie un număr prim de lungime în biți. $r\in \mathbb {Z}$ $q=r^{2}-r+1$ $Q$
Să găsim astfel încât numărul să fie un număr prim de biți de lungime , precum și . $k\in\mathbb{Z}$ $p=r+k\cdot q$ $P$ $p\equiv 2\ {\text{mod}}\ 3$

Corectitudinea algoritmului A: Este necesar doar să verificăm că , deoarece toate proprietățile rămase sunt în mod evident satisfăcute datorită specificului alegerii și .

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

p

q

Este ușor de văzut că înseamnă .

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

Algoritmul A este foarte rapid, dar poate fi nesigur, deoarece este vulnerabil la un atac cu sită de câmp numeric .

Algoritmul B mai lent este ferit de acest neajuns.

Algoritmul B

Să alegem un număr prim de lungime în biți, astfel încât . $q$ $Q$ $q\equiv 7\ {\text{mod}}\ 12$
Să găsim rădăcinile și . $r_{1}$ $r_{2}$ $X^{2}-X+1\ {\text{mod}}\ q$
Să găsim astfel încât , este un număr simplu de biți și, în același timp, pentru $k\in\mathbb{Z}$ $p=r_{i}+k\cdot q$ $p$ $P$ $p\equiv 2\ {\text{mod}}\ 3$ $i\in \{1,2\}$

Corectitudinea algoritmului B: De îndată ce alegem , condiția (Deoarece și ) este îndeplinită automat. Din această afirmație și din legea pătratică a reciprocității rezultă că rădăcinile există .

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}

Pentru a verifica acest lucru , luați în considerare din nou pentru și rețineți că . Prin urmare , și sunt rădăcini și, prin urmare, .

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

Selectarea subgrupului

În secțiunea anterioară, am găsit dimensiunile atât ale câmpului final, cât și ale subgrupului multiplicativ în . Acum trebuie să găsim un subgrup pentru unii astfel încât . Cu toate acestea, nu este necesar să căutați un element explicit , este suficient să găsiți un element astfel încât pentru elementul de ordine . Dar dat fiind, generatorul de grup XTR poate fi găsit prin găsirea rădăcinii lui . Pentru a găsi aceasta , luați în considerare proprietatea 5 . După ce am găsit astfel de , ar trebui să verificați dacă este într-adevăr de ordine , dar mai întâi trebuie să alegeți c\in GF(p²), astfel încât F(c,\ X) să fie ireductibil. Cea mai simplă abordare este să alegeți la întâmplare. $p$ $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)$

Afirmație: Pentru una aleasă aleatoriu , probabilitatea ca - să fie ireductibil este mai mare de 1/3. $c\in GF(p^{2})$ $F(c,\X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]$

Algoritm de căutare de bază : $Tr(g)$

Să alegem unul la întâmplare . $c\in GF(p^{2})\backslash GF(p)$
Dacă – dăm, vom reveni la primul pas. $F(c,\X)$
Să folosim algoritmul de căutare . Să găsim . $S_{n}(c)$ $d=c_{(p^{2}-p+1)/q)$
Dacă ordinea nu este egală cu , revenim la primul pas. $d$ $q$
Lasă . $Tr(g)=d$

Acest algoritm calculează echivalentul elementului de câmp pentru o anumită ordine . [unu] $GF(p^{2})$ $Tr(g)$ $g\in GF(p^{6})$ $q$

Exemple

Protocolul Diffie-Hellman

Să presupunem că Alice și Bob au o cheie publică XTR și doresc să genereze o cheie privată partajată . $\stanga(p,q,Tr(g)\dreapta)$ $K$

Alice alege un număr aleatoriu astfel încât , îl calculează și îl trimite lui 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})\dreapta) \in GF(p^{2})^{3}$ $Tr(g^{a})\in GF(p^{2})$
Bob primește de la Alice, alege o aleatorie astfel încât , calculează și trimite lui 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})\dreapta) \in GF(p^{2})^{3}$ $Tr(g^{b})\in GF(p^{2})$
Alice primește de la Bob, calculează și primește - cheia privată . $Tr(g^{b})$ $S_{a}(Tr(g^{b}))=\left(Tr(g^{(a-1)b}),Tr(g^{ab}),Tr(g^{( a+1)b})\dreapta)\în GF(p^{2})^{3}$ $Tr(g^{ab})\in GF(p^{2})$ $K$
În același mod, Bob calculează și obține cheia privată . $S_{b}(Tr(g^{a}))=\left(Tr(g^{a(b-1)}),Tr(g^{ab}),Tr(g^{a (b+1)})\dreapta)\în GF(p^{2})^{3}$ $Tr(g^{ab})\in GF(p^{2})$ $K$

Schema lui ElGamal

Să presupunem că Alice are o parte din cheia publică XTR: . Alice alege un întreg secret și calculează și publică . Având în vedere cheia publică a lui Alice , Bob poate cripta mesajul destinat lui Alice utilizând următorul algoritm: $(p,q,Tr(g))$ $k$ $Tr(g^{k})$ $\stanga(p,q,Tr(g),Tr(g^{k})\dreapta)$ $M$

Bob alege unul aleator și calculează . $b\in \mathbb {Z}$ $1<b<q-2$ $S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\dreapta) \in GF(p^{2})^{3}$
Bob calculează apoi . $S_{b}(Tr(g^{k}))=\left(Tr(g^{(b-1)k}),Tr(g^{bk}),Tr(g^{( b+1)k})\dreapta)\în GF(p^{2})^{3}$
Bob definește o cheie simetrică pe baza . $K$ $Tr(g^{bk})\in GF(p^{2})$
Bob criptează mesajul cu cheia , primind mesajul criptat . $M$ $K$ $E$
Bob îi trimite un cuplu lui Alice. $(Tr(g^{b}),\E)$

După ce a primit o pereche , Alice o decriptează după cum urmează: $(Tr(g^{b}),\E)$

calculează Alice . $S_{k}(Tr(g^{b}))=\left(Tr(g^{b(k-1)}),Tr(g^{bk}),Tr(g^{b (k+1)})\dreapta)\în GF(p^{2})^{3}$
Alice definește o cheie simetrică bazată pe . $K$ $Tr(g^{bk})\in GF(p^{2})$
Știind că algoritmul de criptare a mesajelor este simetric, Alice decriptează cu cheia , primind mesajul original . $K$ $E$ $M$

Astfel, mesajul este transmis.

Note

↑ 1 2 Lenstra, Arjen K.; Verheul, Eric R. O prezentare generală a sistemului de chei publice XTR (indef.) . Arhivat din original pe 15 aprilie 2006.
↑ Lenstra, Arjen K.; Verheul, Eric R. Sistemul de cheie publică XTR (nedefinită) .

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP