XTR (algoritmus)

XTR (zkratka pro ECSTR - "Efficient and Compact Subgroup Trace Representation") je šifrovací algoritmus veřejného klíče založený na výpočetní složitosti problému diskrétního logaritmu . Výhody tohoto algoritmu oproti ostatním využívajícím tuto myšlenku jsou vyšší rychlost a menší velikost klíče.

Tento algoritmus využívá generátor relativně malé podskupiny řádu ( je jednoduchý) podskupiny . Při správné volbě , má diskrétní logaritmus ve skupině generované , stejnou výpočetní složitost jako v . XTR používá aritmetiku místo , poskytuje stejné zabezpečení, ale s menší režií na výpočty a přenos dat. $G$ $q$ $q$ $GF(p^{6})^{*}$ $q$ $G$ $GF(p^{6})^{*}$ $GF(p^{2})$ $GF(p^{6})$

Teoretický základ XTR

Algoritmus pracuje v konečném poli . Uvažujme skupinu řádu a jeho podgrupu řádu q , kde p je prvočíslo , takže další dostatečně velké prvočíslo q je dělitelem . Skupina řádu q se nazývá XTR-podskupina. Tato cyklická skupina je podskupinou a má generátor g . $GF(p^{6})$ $p^{2}-p+1$ $p^{2}-p+1$ $\langle g\rangle$ $GF(p^{6})^{*}$

Aritmetické operace v $GF(p^{2})$

Nechť p je prvočíslo takové, že p ≡ 2 mod 3 a p 2 - p + 1 je dělitelné dostatečně velkým prvočíslem q . Protože p 2 ≡ 1 mod 3 , p generuje . Kruhový polynom je tedy v . Proto kořeny a tvoří optimální normální základ přes a $(\mathbb {Z} /3\mathbb {Z} )^{*}$ $\Phi _{3}(x)=x^{2}+x+1$ $GF(p)$ $\alpha$ $\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)\} .

Dané p ≡ 2 mod 3 :

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

Náklady na aritmetické operace jsou tedy následující:

Výpočet x p nevyžaduje násobení
Výpočet x 2 vyžaduje dvě násobení in $GF(p)$
Výpočet xy vyžaduje tři násobení v $GF(p)$
Výpočet xz-yzpvyžaduje čtyři násobení v .: [1] $GF(p)$

Použití stop v $GF(p^{2})$

Konjugované prvky in jsou: sebe a , a jejich součet je stopa . $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}}.

Kromě:

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

Uvažujme generátor XTR-skupiny řádu , kde je prvočíslo. Protože je podskupinou skupiny řádu , pak . Kromě, $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

Takto,

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

Všimněte si také, že konjugát k prvku je , to znamená, že má normu rovnou 1. Klíčovým rysem XTR je, že minimální polynom v $G$ $jeden$ $G$ $G$ $GF(p^{2})$

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

zjednodušené na

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

Jinými slovy, konjugované prvky, jako kořeny minimálního polynomu v , jsou zcela určeny stopou . Podobné úvahy platí pro jakýkoli stupeň : $G$ $GF(p^{2})$ $G$ $G$

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

— tento polynom je definován následovně . $Tr(g^{n})$

Myšlenkou algoritmu je nahradit za , to znamená vypočítat podle namísto podle. Aby však byla metoda efektivní, způsob, jak rychle získat z dostupných . $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)$

Rychlý výpočetní algoritmus podle [2] $Tr(g^{n})$ $Tr(g)$

Definice: Pro každý definujeme: $C$ $GF(p^{2})$

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

Definice: Nechť jsou kořeny v , a . Označit: ${\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}.

Vlastnosti a : $c_n$ $F(c,X)$

${\displaystyle c=c_{1))$
${\displaystyle c_{-n}=c_{np}=c_{n}^{p))$
$c_{n}\in GF(p^{2})$ pro $n\in \mathbb {Z}$
${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{uv}+c_{u-2v))$ pro $u,v\in \mathbb {Z}$
Buď mají všechny řád, který je dělitelem a , nebo jsou všechny v poli . Zejména - je neredukovatelné tehdy a pouze tehdy, když jeho kořeny mají řád, který je dělitelem a . ${\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)$ přinést do pole tehdy a jen tehdy $GF(p^{2})$ $c_{p+1}\in GF(p)$

Prohlášení: Nechte . ${\displaystyle c,\!\ c_{n-1},c_{n},c_{n+1))$

Výpočet vyžaduje dvě operace produktu na poli . ${\displaystyle c_{2n}=c_{n}^{2}-2c_{n}^{p))$ $GF(p)$
Výpočet vyžaduje čtyři operace produktu na poli . ${\displaystyle c_{n+2}=c_{n+1}\cdot cc^{p}\cdot c_{n}+c_{n-1))$ $GF(p)$
Výpočet vyžaduje čtyři operace produktu na poli . ${\displaystyle c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p))$ $GF(p)$
Výpočet vyžaduje čtyři operace produktu na poli . ${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p))$ $GF(p)$

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

Algoritmus pro výpočet daných a $S_{n}(c)$ $n$ $C$

Když je algoritmus aplikován na a , pak se k získání konečného výsledku použije vlastnost 2 $n<0$ $-n$ $C$
V , . $n=0$ $S_{0}(c)\!\ =(c^{p},3,c)$
V , . $n=1$ $S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})$
Pro , používáme výrazy pro a k nalezení , 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)$
Pro , pro výpočet , zavádíme $n>2$ $S_{n}(c)$

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

a není-li liché a pokud sudé. Pojďme nastavit a najít pomocí Statement a . Ať v budoucnu

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

kde a . Postupně postupujte takto :

m_{j}\in {0,1}

m_{r}=1

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

Kdy , používáme k nalezení . $m_{j}=0$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k}(c)$
Kdy , používáme k nalezení . $m_{j}=1$ ${\bar {S}}_{k}(c)$ ${\bar {S}}_{2k+1}(c)$
Nahradíme . _ $k$ ${\displaystyle 2k+m_{j))$

Na konci iterací jsou , a . Pokud je n sudé, použijte k nalezení . $k=m$ $S_{\bar {m}}(c)={\bar {S}}_{m}(c)$ $S_{\bar {m}}(c)$ ${\bar {S}}_{m+1}(c)$

Výběr možností

Volba velikosti pole a podskupiny

Pro využití reprezentace prvků skupiny v podobě jejich tras a zajištění dostatečné bezpečnosti dat je nutné najít jednoduché a , kde je charakteristika pole , a , a je velikost podskupiny a dělitele . Označte jako a velikosti a v bitech. Chcete-li dosáhnout úrovně zabezpečení, kterou poskytuje například RSA s délkou klíče 1024 bitů, musíte zvolit takovou , že , tedy a může být přibližně 160. První algoritmus, který umožňuje vypočítat taková prvočísla a je Algoritmus 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\cca 170$ $Q$ $p$ $q$

Algoritmus A

Pojďme najít takové, že číslo je prvočíslo délky v bitech. $r\in \mathbb {Z}$ $q=r^{2}-r+1$ $Q$
Pojďme najít takové, že číslo je prvočíslo bitů délky, stejně jako . $k\in\mathbb{Z}$ $p=r+k\cdot q$ $P$ $p\equiv 2\ {\text{mod}}\ 3$

Správnost algoritmu A: Je třeba pouze ověřit , že vzhledem ke specifikům výběru a jsou zjevně splněny všechny zbývající vlastnosti .

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

p

q

Je snadné to vidět , znamená .

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

Algoritmus A je velmi rychlý, ale může být nejistý, protože je zranitelný vůči útokům typu field sieve .

Pomalejší Algoritmus B je tohoto nedostatku ušetřen.

Algoritmus B

Zvolme prvočíslo délky v bitech, takové, že . $q$ $Q$ $q\equiv 7\ {\text{mod}}\ 12$
Pojďme najít kořeny a . $r_{1}$ $r_{2}$ $X^{2}-X+1\ {\text{mod}}\ q$
Najdeme takové, že , je jednoduché -bitové číslo a zároveň for $k\in\mathbb{Z}$ $p=r_{i}+k\cdot q$ $p$ $P$ $p\equiv 2\ {\text{mod}}\ 3$ $i\in \{1,2\}$

Správnost algoritmu B: Jakmile zvolíme , je automaticky splněna podmínka (Od a ). Z tohoto tvrzení a kvadratického zákona reciprocity vyplývá, že kořeny existují .

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}

Chcete-li zkontrolovat, že , zvažte znovu pro a poznamenejte si, že . Proto , a jsou kořeny , a tedy .

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

Výběr podskupiny

V předchozí části jsme našli velikosti jak konečného pole , tak multiplikativní podskupiny v . Nyní musíme najít podskupinu pro některé takové, že . Není však nutné hledat explicitní prvek , stačí najít prvek takový, že pro prvek objednávky . Ale vzhledem k tomu , generátor skupiny XTR lze nalézt nalezením kořene . Chcete-li to zjistit , zvažte vlastnost 5 . Po nalezení takového je třeba zkontrolovat, zda je skutečně v pořádku , ale nejprve je třeba zvolit c\in GF(p²), takže F(c,\ X) je ireducibilní. Nejjednodušší způsob je vybrat náhodně. $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})\obrácené lomítko GF(p)$

Tvrzení: U náhodně vybraného je pravděpodobnost, že - je neredukovatelné, větší než 1/3. $c\in GF(p^{2})$ $F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]$

Základní vyhledávací algoritmus : $Tr(g)$

Vyberme si náhodný . $c\in GF(p^{2})\obrácené lomítko GF(p)$
Pokud – dáme, vrátíme se k prvnímu kroku. $F(c,\ X)$
Použijme vyhledávací algoritmus . Pojďme najít . $S_{n}(c)$ ${\displaystyle d=c_{(p^{2}-p+1)/q))$
Pokud má pořadí není rovno , vrátíme se k prvnímu kroku. $d$ $q$
Nechte _ $Tr(g)=d$

Tento algoritmus vypočítává ekvivalent prvku pole pro určitý řád . [jeden] $GF(p^{2})$ $Tr(g)$ $g\in GF(p^{6})$ $q$

Příklady

Protokol Diffie-Hellman

Předpokládejme , že Alice a Bob mají veřejný klíč XTR a chtějí vygenerovat sdílený soukromý klíč . $\left(p,q,Tr(g)\right)$ $K$

Alice vybere náhodné číslo takové, že , vypočítá je a pošle Bobovi. $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) \in GF(p^{2})^{3}$ $Tr(g^{a})\in GF(p^{2})$
Bob obdrží od Alice, vybere náhodný takový, že , vypočítá a pošle Alici. $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) \in GF(p^{2})^{3}$ $Tr(g^{b})\in GF(p^{2})$
Alice přijímá od Boba, vypočítává a přijímá - soukromý klíč . $Tr(g^{b})$ $S_{a}(Tr(g^{b}))=\left(Tr(g^{(a-1)b}),Tr(g^{ab}),Tr(g^{( a+1)b})\vpravo)\in GF(p^{2})^{3}$ $Tr(g^{ab})\in GF(p^{2})$ $K$
Stejným způsobem Bob vypočítá a získá soukromý klíč . $S_{b}(Tr(g^{a}))=\left(Tr(g^{a(b-1)}),Tr(g^{ab}),Tr(g^{a (b+1)})\vpravo)\in GF(p^{2})^{3}$ $Tr(g^{ab})\in GF(p^{2})$ $K$

Schéma ElGamal

Předpokládejme, že Alice má část veřejného klíče XTR: . Alice vybere tajné celé číslo a spočítá a publikuje . Díky Alicinu veřejnému klíči může Bob zašifrovat zprávu určenou pro Alici pomocí následujícího algoritmu: $(p,q,Tr(g))$ $k$ $Tr(g^{k})$ $\left(p,q,Tr(g),Tr(g^{k})\right)$ $M$

Bob si vybere náhodný a počítá . $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) \in GF(p^{2})^{3}$
Bob pak počítá . $S_{b}(Tr(g^{k}))=\left(Tr(g^{(b-1)k}),Tr(g^{bk}),Tr(g^{( b+1)k})\vpravo)\in GF(p^{2})^{3}$
Bob definuje symetrický klíč založený na . $K$ $Tr(g^{bk})\in GF(p^{2})$
Bob zašifruje zprávu pomocí klíče a přijme zašifrovanou zprávu . $M$ $K$ $E$
Bob posílá pár k Alici. $(Tr(g^{b}),\ E)$

Po obdržení páru jej Alice dešifruje takto: $(Tr(g^{b}),\ E)$

Alice počítá . $S_{k}(Tr(g^{b}))=\left(Tr(g^{b(k-1)}),Tr(g^{bk}),Tr(g^{b (k+1)})\vpravo)\in GF(p^{2})^{3}$
Alice definuje symetrický klíč založený na . $K$ $Tr(g^{bk})\in GF(p^{2})$
S vědomím, že algoritmus šifrování zprávy je symetrický, Alice dešifruje pomocí klíče , přičemž obdrží původní zprávu . $K$ $E$ $M$

Tím je zpráva přenášena.

Poznámky

↑ 1 2 Lenstra, Arjen K.; Verheul, Eric R. Přehled systému veřejného klíče XTR (indef.) . Archivováno z originálu 15. dubna 2006.
↑ Lenstra, Arjen K.; Verheul, Eric R. Systém veřejného klíče XTR (neurčitý) .

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta