XTR

암호학에서 XTR은 공개키 암호화를 위한 알고리즘이다.XTR은 Efficient and Compact Subgroup Trace Presentation의 약자인 'ECSTR'을 의미한다.유한 장의 승법군 하위군의 원소를 나타내는 방법이다.이를 위해 ${\displaystyle \mathrm{GF}({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle GF(p^{2})}$에 대한 추적을 사용하여$$ ${\displaystyle \mathrm{GF}({}^{}}$ ${\displaystyle {6\mathrm{}}^{}{}^{}}$) ${\displaystyle {\ast }^{}}$ ${\$의 하위 그룹 요소를 나타낸다$.$

보안 관점에서 XTR은 유한 분야의 전체 승수 그룹에서 이산 로그 관련 문제를 해결하는 어려움에 의존한다.한정된 분야의 전체 승수 그룹의 생성기를 기반으로 하는 많은 암호 프로토콜과는 달리, XTR은 오른쪽 $choic$과 함께 ${\displaystyle \mathrm{GF}}$(${\displaystyle {p\mathrm{}}^{}}$ $6$)$∗{\$ $q}$의 일부$$ 소수 부분군 g ${\displaystyle$ q}의$$ 생성기 $g{\displaystyle }$ ${\displaystyle$$q$$\}$을 사용한다.e of ${\displaystyle q}$, computing Discrete Logarithms in the group, generated by ${\displaystyle g}$, is, in general, as hard as it is in ${\displaystyle GF(p^{6})^{*}}$ and thus cryptographic applications of XTR use ${\displaystyle GF(p^{2})}$ arithmetics while achieving full $$${\displaystyle G}$ ${\displaystyle F}$( ${\displaystyle {p\mathrm{}}^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle GF(p^{6})}$ 보안으로$$ 보안에 영향을 주지 않으면서 통신 및 계산 오버헤드 모두에서 상당한 비용 절감 효과를 얻음XTR의 다른 장점으로는 빠른 키 생성, 작은 키 크기 및 속도 등이 있다.

XTR의 기본 원리

XTR은 일반적으로 XTR supergroup이라 불리는 부분군의 XTR supergroup 또는 just XTR 그룹으로, ${\displaystyle {p\mathrm{}}^{}}$ 6 ${\$ 원소가$$$$ 있는 $유한장{\displaystyle }$ $GF(p^{$})의 승법집단을 사용한다.XTR 슈퍼 그룹은 p ${\displaystyle {2\mathrm{}}^{}}$ -${\displaystyle {}^{}}$p${\displaystyle }$+ 1 ${\displaystyle \mathrm{순서}}$ p - ${\displaystyle p}$ + 1 ${\$$displaystyle$ p$^{2}-$$p+1}$이며$,$ 여기서 p는 충분히 큰 prime$q$가 ${\displaystyle {p\mathrm{}}^{}}$ ${\displaystyle 2}$ -${\displaystyle }$p + $1$을 나누는 프라임$$$q$이다${\displaystyle {}^{}}$XTR 하위 그룹은 이제 q를 주문했으며, 제너레이터 g와 함께$$ 주기 ${\displaystyle \mathrm{그룹}}$인$$G ${\displaystyle F}$${\displaystyle (}$${\displaystyle {p\mathrm{}}^{}}$ 6${\displaystyle {}^{}{}^{}}$) $∗ {\displaystyle GF$$(p^{6$$}}^{*}}}}}$의 하위 그룹으로서$,$The following three paragraphs will describe how elements of the XTR supergroup can be represented using an element of ${\displaystyle GF(p^{2})}$ instead of an element of ${\displaystyle GF(p^{6})}$ and how arithmetic operations take place in ${\displaystyle GF(p^{2})}$ instead of in $G{\displaystyle }$ ${\displaystyle F}$( ${\displaystyle {}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$) ${\displaystyle GF(p^{6})}$.

$G{\displaystyle }$ ${\displaystyle F({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle GF(p^{2})}$의 산술 연산

p가장 많은 사람은 피와 p2-p2모드 3≡과 같아야+13우리는 그 p(Z/3Z)∗{\displaystyle(\mathbb{Z}/3\mathbb{Z})^{*}를 생성하}참조하십시오 p2 ≡ 1모드이고 따라서 세번째 원주 등분 다항식 Φ 3())이후)는 충분히 큰 소인수 quaque다 x2+x+1{\displaystyle \Phi_{3}())=x^{2}+x+1}irreduci 것입니다.가물가물e over ${\displaystyle GF(p)}$. It follows that the roots ${\displaystyle \alpha }$ and ${\displaystyle \alpha ^{p}}$ form an optimal normal basis for ${\displaystyle GF(p^{2})}$ over ${\displaystyle GF(p)}$ and

${\displaystyle GF(p^{2})\cong \{x_{1}\알파 +x_{2}\알파 ^{p}:x_{1},x_{2}\in GF(p)\}.}$

p ≡ 2 mod 3을 고려하면 우리는 지수 modulo 3을 줄일 수 있다.

${\displaystyle GF(p^{2})\cong \{y_{1}\알파 +y_{2}\알파 ^{2}:\알파 ^{2}+\알파 ^{1=0,y_{1},y_{2}\in GF(p)\}}$

산술 연산의 비용은 이제 "XTR 공개 키 시스템의 개요"^[1]에서 Lema 2.21이라는 라벨을 붙인 다음 Lemma에 제시되어 있다.

보조정리

• x^p 컴퓨팅은 곱셈을 사용하지 않고 수행된다.
• 컴퓨팅 x는² $G{\displaystyle }$ ${\displaystyle F}$( ${\displaystyle p}$) ${\displaystyle GF(p)}$의 두 배수를 사용한다.
• xy 컴퓨팅은 $G{\displaystyle }$ ${\displaystyle F}$( ${\displaystyle p}$) ${\displaystyle GF(p)}$의 세 배수를 사용한다.
• xz-yz^p 연산에는 ${\displaystyle \mathrm{GF}(p}$) ${\displaystyle GF(p)}$의 네 가지 배수가 사용된다$.$

$G{\displaystyle }$ ${\displaystyle F({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle GF(p^{2})$에 대한 추적

The trace in XTR is always considered over ${\displaystyle GF(p^{2})}$. In other words, the conjugates of ${\displaystyle h\in GF(p^{6})}$ over ${\displaystyle GF(p^{2})}$ are ${\displaystyle h,h^{p^{2}}}$ and ${\displaystyle h^{p^{4}}}$$$ $h{\displaystyle }$ ${\displaystyle h}$의 흔적이 이들의 총합이다$$.

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

이후$$ $T{\displaystyle }$ ${\displaystyle r}$(${\displaystyle h}$ ) ${\displaystyle \in }$ ${\displaystyle G}$ ${\displaystyle F}$( ${\displaystyle {p\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle Tr(h)\in GF(p^{2})$에 주목하십시오.

${\displaystyle{\begin}{p^{p^{2}}~{p^{p^{2}}+h^{p^{4}}+h^{p^{6}\\&=h+h^{p^{2}}+h^{p^{p^{4}}}}}\&=Tr(h)\end{liged}}}}}}}}}}}}}}}}}}$

Consider now the generator ${\displaystyle g}$ of the XTR subgroup of a prime order ${\displaystyle q}$. Remember that ${\displaystyle \langle g\rangle }$ is a subgroup of the XTR supergroup of order ${\displaystyle p^{2}-p+1}$, so ${\displaystyle q\mid p^{2}-p+1}$.다음 섹션에서는 $p{\displaystyle }$ ${\displaystyle p}$ $및{\displaystyle }$ q$${\$displaystyle q$을(를) 선택하는 방법을 볼 수 있지만, 현재로서는 > 3 ${\displaystyle$ $q>3$을(를$)$ 가정하면 충분하다. modulo $p{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$- ${\displaystyle p}$+ ${\displaystyle 1}$ ${\displaystylease$ $p$$^{2}+1}$에 대한 $추적$을 계산하려면

${\displaystyle p^{}}$ ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle p}$- ${\displaystyle 1}$ ${\displaystyle p^{2}=p-1}$ 및

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

따라서

${\displaystyle {\begin{aigned}Tr(g)&=g+g^{p^{2}}+g^{p^{p^{4}\\&=g+g^{p-1}+g^{-p}.\end{정렬}}}$

$g{\displaystyle }$ ${\displaystyle g}$의 $결합상품$은 1 ${\displaystyle$ 1$\},$ 즉 $g{\displaystyle }$ ${\displaystyle g}$이(가) 표준 1을 갖는$$ 것과 같다$$.

XTR의 중요한 관찰 내용은 $G{\displaystyle }$ ${\displaystyle F({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle GF(p^{2})$에 대한 g ${\displaystyle g}$의 최소 다항식이라는 것이다.

${\displaystyle (x-g)\!\ (x-g^{p-1})(x-g^{-p})}$

로 단순화하다.

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

T ${\displaystyle r}$( ${\displaystyle g}$) ${\displaystyle Tr(g)}$에 의해 완전히 결정된다$.$ 따라서 G $F{\displaystyle }$ (${\displaystyle p}$ ${\displaystyle {2\mathrm{}}^{}}$ )${\displaystyle g}$에 $대한{\displaystyle }$ g ${\displaystyle$ g$}$의 최소 다항식의 뿌리로서$$$g{\displaystyle }$ ${\displaysty g}$의 추적에 의해 완전히 결정된다$.$$g{\displaystyle }$ ${\displaystyle g}$의 모든 동력에 대해서도 동일함$:$ ${\displaystyle g^{}}$ ${\$ g$^{n}$의 접합자는 다항식의 뿌리임$$

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

그리고 이 다항식은 $T{\displaystyle }$ ${\displaystyle r}$( g ${\displaystyle n^{}}$) ${\displaystyle Tr(g^{n})}$에 의해 완전히 결정된다$.$

트레이스를 사용하는 이면의 아이디어는 암호 프로토콜(예: Diffie–)에서 g $n{\displaystyle {}^{}n}$ G F${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$) ${\displaystyle$ g$^{n}\in GF(p^{6})$를 대체하는 것이다.$GF(p^{2})$에서 T $r{\displaystyle ({}^{}{n}^{}}$ )${\displaystyle }$∈ ${\displaystyle G}$F(${\displaystyle {p\mathrm{}}^{}}$2 ) $\displaystyle Tr(g^{n})\\$displaystyle Tr(g^{n})\에 의한 헬만 키 교환으로 표현 크기가$$ 3 감소하는 계수를 얻었다.그러나 이는 $T{\displaystyle }$ ${\displaystyle r}$(${\displaystyle g}$ n${\displaystyle {}^{}}$) ${\displaystyle Tr(g$$^{n})}$을(를$)$ 얻을 수 있는 빠른 방법이 있는 경우에만 유용하다$.$The next paragraph gives an algorithm for the efficient computation of ${\displaystyle Tr(g^{n})}$. In addition, computing ${\displaystyle Tr(g^{n})}$ given ${\displaystyle Tr(g)}$ turns out to be quicker than computing ${\displaystyle g^{n}}$ given ${\displaystyle g}$$$.^[1]

$T$ ${\displaystyle r}$( ${\displaystyle g^{}}$ n${\displaystyle {}^{}}$) ${\displaystyle Tr($${\displaystyle g}$$^{n})$ ${\displaystyle Tr(g)}$의 빠른 계산 알고리즘

A. 렌스트라와 E.Verheul은 XTR 공개 키 시스템이라는 제목의 논문에서 이 알고리즘을 제공했다.^[2]알고리즘과 여기에 제시된 알고리즘 자체에 필요한 모든 정의와 레마(lemmas)는 이 문서에서 가져온 것이다.

${\displaystyle \mathrm{GF}({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$)$${\$displaystyle GF(p^{$2})에서 c에 $대한$정의 정의$$ 정의

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

Definition Let ${\displaystyle h_{0},\!\ h_{1},h_{2}}$ denote the, not necessarily distinct, roots of ${\displaystyle F(c,X)}$ in ${\displaystyle GF(p^{6})}$ and let ${\displaystyle n}$ be in ${\displaystyle \mathbb {Z} }$. Define

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

$c{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$ 및$$ $F{\displaystyle (c}$, X${\displaystyle }$) ${\displaystyle F(c,X)}$의 속성

1. ${\displaystyle c=c_{1}.$
2. ${\displaystyle c_{-n}=c_{np}=c_{n}^{p}}}$
3. ${\displaystyle c_{n}\in GF(p^{2}){\text{{}}{}}}}}}}{}n\in \in \mathb {Z}}$
4. ${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{u-v}+c_{u-2v}{\text{}{}}{}}}}}}{}u,v\in \mathb {Z}}}}}}$
5. 해석)모든 hj{\displaystyle h_{j}}하 p2− p+1{\displaystyle p^{2}-p+1}과 을 나누고, 3{\displaystyle>3}또는 모든 hj{\displaystyle h_{j}}GF(p2){GF(p^{2})\displaystyle}에. 특히, 만일 F(c, X){F(c,X)\displaystyle} 할 수 있다.그 roots는 ${\displaystyle {diving\mathrm{}}^{}}$ ${\displaystyle p{}^{}}$2 - p${\displaystyle }$+ ${\displaystyle 1}$(\$displaystyle p^{2$}-$p+1}$및 >3 (\$displaystyle$ >$3}$을(를) 주문한다
6. ${\displaystyle }$${\displaystyle F_{}}$${\displaystyle (c}$ ${\displaystyle ,}$ ${\displaystyle X}$) ${\displaystyle F$${\displaystyle {}^{}}$$c,$${\displaystyle {X\mathrm{}}^{}}$$)}$은(는) C${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle G}$ ${\displaystyle F(p}$) ${\displaystyle C_{p+$1$}\in$ $GF(p)$에 ${\displaystyle \mathrm{대해}}$ 축소 가능함$$

Lemma Let $c{\displaystyle }$, c ${\displaystyle n_{}}$- ${\displaystyle 1_{}}$,${\displaystyle {}_{}}$c ${\displaystyle n_{}}$ ${\displaystyle {\mathrm{c}}_{}}$+ ${\displaystyle 1_{}}$ ${\$ c$,\\\c_{n-1}c_{n},c_{n+1}$가 주어지도록$$ 한다.

1. 컴퓨팅 $c{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{2n}}_{}}$= ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle 2_{}^{}}$- 2 ${\displaystyle c_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$은(는) ${\displaystyle \mathrm{GF}(p}$) ${\displaystyle GF(p)}$에서 두 곱을 취한다$$$.$
2. ${\displaystyle {\mathrm{컴퓨팅}}_{}}$ $c{\displaystyle {}_{}}$ ${\displaystyle n_{}}$+ 2${\displaystyle {}_{}}$= ${\displaystyle c_{}}$+ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ c -${\displaystyle }$c ${\displaystyle p^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle c_{}}$ + c ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ c + ${\displaystyle {\mathrm{n}}_{}}$- 1 ${\$$cdot$ $c_{n}+c_{n-1}$는 $GF(p)$로 4 곱한다$$$.$
3. Computing ${\displaystyle c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p}}$ takes four multiplication in ${\displaystyle GF(p)}$.
4. Computing ${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p}}$ takes four multiplication in ${\displaystyle GF(p)}$.

${\displaystyle \mathrm{Definition}}$ Let S${\displaystyle {}_{}{n}_{}}$( c${\displaystyle }$)${\displaystyle }$= ( ${\displaystyle c_{}{}_{}}$ -${\displaystyle 1_{}}$, c ${\displaystyle n_{}}$ ${\displaystyle {\mathrm{c}}_{}}$ ${\displaystyle {}_{}}$+ 1${\displaystyle {}_{}}$) ${\displaystyle \in }$ ${\displaystyle G}$ ${\displaystyle F}$( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}{}^{}}$) ${\displaystyle {3\mathrm{}}^{}}$ ${\$

$n{\displaystyle }$ ${\displaystyle n}$ 및$$ $c{\displaystyle }$ ${\displaystyle c}$에 지정된 $S{\displaystyle {}_{}}$ ${\displaystyle n_{}}$(${\displaystyle c}$ ${\displaystyle )}$ ${\displaystyle S_{n}(c)}$ 계산 알고리즘 1

• < ${\displaystyle n<0}$인 경우 이 알고리즘을$$${\displaystyle \mathrm{-n}}$ ${\displaystyle -n}$ $및$ c ${\displaystyle c}$에 적용하고 결과 값에 속성 2를 적용한다.
• $n{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle n=0$이면 $S{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}c}$ ${\displaystyle )}$=${\displaystyle }$(${\displaystyle \mathrm{c}{}^{}}$, 3${\displaystyle }$, c${\displaystyle }$) ${\displaystyle S_{0}(c)\\ =(c^{p},3,c)}$.
• $n{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle n=1}$이면$$${\displaystyle S}$ 1${\displaystyle {}_{}}$( ${\displaystyle {c\mathrm{}}_{}}$)${\displaystyle }$= ( 3, c${\displaystyle ,2{}^{}}$- ${\displaystyle 2}$ ${\displaystyle p^{}}$ )${\displaystyle S_{1}(c)\\\$ = $(3,c,c^{2-c^{p$ .
• If ${\displaystyle n=2}$, use the computation of ${\displaystyle c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}}$ and ${\displaystyle S_{1}(c)}$ to find ${\displaystyle c_{3}}$ and thereby ${\displaystyle S_{2}(c)}$$$.
• > ${\displaystyle n>2$}이가) $S{\displaystyle {}_{}}$ ${\displaystyle n_{}}$(${\displaystyle c}$ ${\displaystyle )}$ ${\displaystyle S_{n}(c)}$을(를) 계산하는 경우

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

및 $m{\displaystyle \stackrel{\text{'}}{}}$= ${\displaystyle n}$이 홀수인 경우$$ n ${\displaystyle {\m}=n$${\displaystyle \},}$ m${\displaystyle \stackrel{}{}}$= ${\displaystyle \mathrm{n}}$- 1 ${\displaystyle {\m}=n-1},$ 그렇지$$ 않은 경우.Let $m{\displaystyle \stackrel{}{}}$=${\displaystyle \mathrm{2m}}$+ 1,${\displaystyle }$k${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle {\m}=2m+1,k=1}$및 계산$$ S(${\displaystyle {}_{}{\stackrel{}{)=}}_{}{3\mathrm{}}_{}c}$ $){\displaystyle {\S}_{k}(c)=$위의 ${\displaystyle {리마사}_{}}$와 ${\displaystyle \mathrm{S2}{}_{}}$(c${\displaystyle }$)를$$ $사용하는 S_{3$}(c$)}$ ${\displaystyle S_{2}(c)}$. 더 멀리 두십시오.

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

$m{\displaystyle {}_{}}$ ${\displaystyle j_{}}$${\displaystyle \mathrm{r}}$ ${\displaystyle 0\mathrm{},}$ ${\displaystyle 1}$ ${\$} $및{\displaystyle {}_{}}$ m$$${\displaystyle {}_{}}$= ${\displaystyle 1}$ ${\displaystyle m_{r}=1}.$$j{\displaystyle }$= r${\displaystyle }$- 1,${\displaystyle }$r${\displaystyle }$- ${\displaystyle 2}$,${\displaystyle }$.${\displaystyle }$. . . . ${\displaystyle 0}${\$displaystyle j=r-1,r-2,$ ...,$0}$을 연속으로 사용하여 다음을 수행하십시오.

• $m{\displaystyle {}_{}}$ ${\displaystyle j_{}}$= ${\displaystyle 0}$ ${\displaystyle m_{j}=0$인 경우 $S$의${\displaystyle {\stackrel{}{}k}_{}}$ (${\displaystyle c}$ )${\displaystyle {\s}_{k}(c)$를 사용하여$$ $S$의${\displaystyle {\stackrel{}{}}_{\mathrm{2k}}c}$) ${\displaystyle {\s}_{2k}(c)$를 계산하십시오$.$
• $m{\displaystyle {}_{}}$ ${\displaystyle j_{}}$= ${\displaystyle 1}$ ${\displaystyle m_{j}=1}$인 경우$,$ $S$의${\displaystyle {\stackrel{}{}k}_{}}$($){\displaystyle {\s}_{k}(c)$를 사용하여$$ $S$의${\displaystyle {\stackrel{}{}}_{\mathrm{2k}}}$+ $){\displaystyle {\s}_{2k+1}(c)$을 계산하십시오$.$
• $k{\displaystyle }$ ${\displaystyle k}$을(를) ${\displaystyle \mathrm{2k}}$+ m ${\displaystyle j_{}}$ ${\$로 교체하십시오$.$

When these iterations finish, ${\displaystyle k=m}$ and ${\displaystyle S_{\bar {m}}(c)={\bar {S}}_{m}(c)}$. If n is even use ${\displaystyle S_{\bar {m}}(c)}$ to compute ${\displaystyle {\bar {S}}_{m+1}(c)}$.

파라미터 선택

한정된 필드 및 부분군 크기 선택

위에서 설명한 요소들의 표현을 추적하고 충분한 보안을 확보하기 위해 아래에서 논의될 p{\$displaystyle p}$와 $q{\displaystyle }$ ${\displaystyle q}$를 찾아야 하며, $여기$서 p ${\displaystyle p}$은 ${\displaystyle \mathrm{필드}}$ G F${\displaystyle }$( ${\displaystyle {페이지\mathrm{}}^{}}$ 6${\displaystyle {}^{}}$)의 특성을 나타낸다$.$$p{\displaystyle }$ ${\displaystyle \equiv }$ ${\displaystyle 2}$ ${\displaystyle \text{mod}}$ $[\displaystyle p\equiv$ 2$\\\text{mod}\$ 3$}$을(를$)$ 사용하는$$ ${\$$displaystyle q}$은(는$)$ p $2{\displaystyle {}^{}}$ -${\displaystyle {}^{}p}$+ ${\displaystyle 1}$을(를$)$ 나누는$$ 부분군 $크기$ 입니다$.$

$P{\displaystyle }$ ${\$$displaystyle P$$}$과 $Q{\displaystyle }$ ${\$$displaystyle Q}$의 크기를 비트로$$ 표시한다$.$1024비트 RSA에 필적하는 보안을 얻으려면 약 $1024년경$ $6P(P$)를 선택해야 한다. 즉, $P{\displaystyle 170}$ 170$(P\style$ P\ 약 $170)$ 및$$ $Q{\displaystyle }$ ${\displaysty Q}$는 약 160이 될 수 있다$$.

이러한 프리타임 $p{\displaystyle }$ {\$displaystyle p}$ 및$$$q{\displaystyle }$ ${\displaystyle q}$을(를) 계산하기 위한 첫 번째 쉬운 알고리즘은$$ 다음 알고리즘 A:

알고리즘 A

1. $q{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$- ${\displaystyle r}$+ ${\displaystyle 1}$ ${\displaystyle q=r^{2}-r+1$}이$($가) $Q{\displaystyle }$ ${\displaystyle Q}$ -bit$$ prime인 $r{\displaystyle }$r ${\displaystyle Z\mathbb{}}$ ${\displaystyle$ r$\in$ {$Z}$을(를$)$ 찾으십시오.
2. $p{\displaystyle }$= ${\displaystyle r}$+ ${\displaystyle k}$ ${\displaystyle \cdot }$$q${\$displaystyle p=r+k\cdot$q$$}이$($$가$) p ${\displaystyle \equiv }$ ${\displaystyle 2}$ 3 {\displaystyle $p\equiv 2\\\text{mod}}$ 3$}$인 P ${\$$displaystystyle$ $P}$ -b$$ p} -bit prime}을$($으) 찾으십시오$.$

알고리즘 A의 정확성:

It remains to check that ${\displaystyle q\mid p^{2}-p+1}$ because all the other necessary properties are obviously satisfied per definition of ${\displaystyle p}$ and ${\displaystyle q}$. We easily see that ${\displaystyle p^2-p+1=r^2+2rkq+k^2{q}^2-r-kq+1=r^2-r+1+q(2r}$${\displaystyle p^{2}-p+1=r^{2}+2rkq+k^{2}q^{2}-r-kq+1=r^{2}-r+1+q(2rk+k^{2}q-k)=q(1+2rk+k^{2}q-k)}$ which implies that ${\displaystyle q\mid p^{2}-p+1}$.

알고리즘 A는 매우 빠르고 계수가 작은 도 2 다항식을 만족시키는$$ primes $p{\displaystyle }$ ${\displaystyle p}$을(를) 찾는 데 사용할 수 있다.이러한 $p{\displaystyle }$ ${\displaystyle p}$은(는) ${\displaystyle \mathrm{GF}(p}$) ${\displaystyle GF(p)}$의 빠른 산술 연산을 유도한다$.$ 특히 $k{\displaystyle }$ ${\displaystyle$ $k$$}$ 검색이 ${\displaystyle \mathrm{k}}$= 1 ${\$$displaystyle$ k$=$$1}$로 제한되는$$ 경우 $r{\displaystyle {}^{}}$ - ${\displaystyle 2{}^{}}$- r${\displaystyle }$+ ${\displaystyle \text{1}}$과 ${\displaystyle {r\mathrm{}}^{}}$+$$을 $모두$ 찾는$$ $것$을 의미한다.$r^{2}-r+1{\text${\text${}$및$}}$${\displaystyle \mathrm{r}}$$^{2}+1$}{}$r^{2}+1\equiv$ 2${\text{}}}$이$($가) 프라임 $^{\displaystyp p}$이(가) 이러한 멋진 형태를 갖도록$$ 한다$$.이 경우 $r{\displaystyle }$ ${\displaystyle r}$은(는) 짝수여야 하며$$ r ${\displaystyle \equiv }$ ${\displaystyle 1}$ ${\displaystyle \text{mod}}$ ${\displaystyle 4\mathrm{}}$ ${\displaystyle r\equiv 1{\text{mod} }}$이어야 한다는 점에 유의하십시오$.$

반면에 그러한 $p{\displaystyle }$ ${\displaystyle p}$은(는) 숫자 필드 체의 이산 로그 변종(Intertain Logarithm)으로 공격을 쉽게 할 수 있기 때문에 보안 관점에서 바람직하지 않을$$ 수 있다.

다음의 알고리즘 B는 이러한 단점을 가지고 있지 않지만, 그 경우에 있어서 A 알고리즘이 가지고 있는 빠른 $산술모듈$로 p ${\displaystyle p}$ 알고리즘도$$ 가지고 있지 않다.

알고리즘 B

1. ${\displaystyle \mathrm{Q}}$ ${\displaystyle Q}$ -bit$$ prime $q{\displaystyle }$ ${\displaystyle q}$을(를) 선택하여$$ $q{\displaystyle }$ ${\displaystyle \equiv }$ 7 ${\displaystyle \text{mod}}$ ${\displaystyle 12\mathrm{}}$ ${\displaysty q\equiv$ 7$\{\text}\12$ .
2. $X{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$- ${\displaystyle X}$+ ${\displaystyle 1}$ $q$ {\displaystyle $r_{1$}, R $2{\displaystyle {}_{}}$ ${\$$displaystyle$ $r_{2$$}}-displaystyle$ X^{2}-X$+1\\\text{mod}\ q}$의 루트$$ ${\displaystyle {r\mathrm{}}_{}}$ 1${\\$ r_{{1}}}을$$ 찾으십시오$.$
3. Find a ${\displaystyle k\in \mathbb {Z} }$ such that ${\displaystyle p=r_{i}+k\cdot q}$ is a ${\displaystyle P}$-bit prime with ${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$ for ${\displaystyle i\in \{1,2\}}$

알고리즘 B의 정확성:

q ${\displaystyle \equiv }$ 7 ${\displaystyle \text{mod}}$ ${\displaystyle 12\mathrm{}}$ ${\displaystyle q\equiv 7\{\text}\$$12}$을(를) 선택했으므로 $$q${\displaystyle }$${\displaystyle \mathrm{}}$ ${\displaystyle \equiv }$ ${\displaystyle 1}$ ${\displaystyle \text{md}}$ ${\displaystyle 3\mathrm{}}$ ${\displaysty q$$\equiv 1$$\\\\\text{mod}$및$$ 3 ${\displaystyle \mid }$ ${\displaystyle 12}$ ${\displaystystyledyledyledayste$ 3$\}을 즉시$ 따라간다.$$그것과 이차적 상호주의로부터 우리는 r ${\displaystyle {1\mathrm{}}_{}}$ ${\$}와$$ $r{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}개가 존재한다고$$ 추론할 수 있다.

To check that ${\displaystyle q\mid p^{2}-p+1}$ we consider again ${\displaystyle p^{2}-p+1}$ for ${\displaystyle r_{i}\in \{1,2\}}$ and get that ${\displaystyle 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+}$${\displaystyle 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}q-k)=q(2rk+k^{2}q-k)}$, since ${\displaystyle r_{1}}$ and ${\displaystyle r_{2}}$ are roots of ${\displaystyle X^{2}-X+1}$ and hence ${\displaystyle q\mid p^2-p+1}$${\$displaystyle$$q\$displaystyle q\mid p^{2}-p+1}.$

부분군 선택

In the last paragraph we have chosen the sizes ${\displaystyle p}$ and ${\displaystyle q}$ of the finite field ${\displaystyle GF(p^{6})}$ and the multiplicative subgroup of ${\displaystyle GF(p^{6})^{*}}$, now we have to find a subgroup ${\displaystyle \langle g\rangle }$$$ ${\displaystyle \mathrm{일부}}$ $G{\displaystyle }$${\displaystyle }$${\displaystyle \in }$ G ${\displaystyle F}$(${\displaystyle {p\mathrm{}}^{}}$ ${\displaystyle {6\mathrm{}}^{}{}^{}}$) ${\displaystyle {\ast }^{}}$ ${\$$$$\{{\displaystyle \mathrm{GF}}$ (${\displaystyle p}$$^{6}}}}$에 대해$$ ${\displaystyle$ $g\$$mid \\}!$$\langle g\angle \!\!$$\mid =q}$.

However, we do not need to find an explicit ${\displaystyle g\in GF(p^{6})}$, it suffices to find an element ${\displaystyle c\in GF(p^{2})}$ such that ${\displaystyle c=Tr(g)}$ for an element ${\displaystyle g\in GF(p^{6})}$ of order ${\display$$style$${\displaystyle q}$$\}.$ 그러나 $T{\displaystyle }$ r${\displaystyle }$( ${\displaystyle g}$) ${\displaystyle Tr(g)}$이$($가) 주어진 경우 위에서 $정의$한 F ( T r${\displaystyle }$(${\displaystyle g}$)${\displaystyle }$, ${\displaystyle \text{X}}$)$$${\displaystyle$$$F$(Tr(g),\ X)$의 루트를 결정하여 XTR(sub) 그룹의$$ $g{\displaystyle }$ {\displaystystyle g}을 찾을 수 있다.To find such a ${\displaystyle c}$ we can take a look at property 5 of ${\displaystyle F(c,\ X)}$ here stating that the roots of ${\displaystyle F(c,\ X)}$ have an order dividing ${\displaystyle p^{2}-p+1}$ if and only if ${\displaystyle F(c,\ X)}$ is irreducible. 그러한 $c{\displaystyle }$ ${\$$displaystyle$ $c}$을(를) 찾은 후 실제로$$$$$q{\displaystyle }$ ${\$$displaystyle$ $q$${\displaystyle {}^{}}$이(가) 순서인지 확인할 필요가 있지만, 먼저 $F{\displaystyle (c}$ ${\displaystyle ,}$ $)$가 풀릴$$ 수 없도록$$${\displaystyle }$c$c{\displaystyle }$ $($$p$$^{2})$를 선택하는 방법에 초점을 맞춘다.

초기 접근방식은 $다음{\displaystyle }$ 보조정리기로 정당화되는 c ${\displaystyle \in }$ ${\displaystyle G}$ ${\displaystyle F}$(${\displaystyle {p\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle \mathrm{\setminus }}$ G ${\displaystyle F}$(${\displaystyle p}$ ${\displaystyle )}$ ${\displaystyle c\in GF(p^{2})\백슬래시 GF(p)}$를 무작위로$$ 선택하는 것이다.

보조정리: For a randomly selected ${\displaystyle c\in GF(p^{2})}$ the probability that ${\displaystyle F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]}$ is irreducible is about one third.

이제 적합한 $T{\displaystyle }$ ${\displaystyle r}$( g${\displaystyle }$) ${\displaystyle Tr(g)}$을(를) 찾기 위한 기본 알고리즘은 다음과$$ 같다.

알고리즘 개요

1. 임의 $c{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle G}$ ${\displaystyle F}$ (${\displaystyle }$p ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle \mathrm{\setminus }}$ ${\displaystyle G}$ ${\displaystyle F}$( ${\displaystyle p}$ )${\displaystyle }${ G F ( ) ${\displaystyle c\in GF(p^{2})\백슬래시 GF(p)}$를 선택하십시오$.$
2. $F{\displaystyle (c}$, ${\displaystyle \text{X}}$) ${\displaystyle F(c,\ X)}$이(가) 축소 가능한 경우 1단계로 돌아가십시오.
3. 알고리즘 1을 사용하여 $d{\displaystyle }$= ${\displaystyle {}_{({p\mathrm{}}^{}}}$ 2${\displaystyle {{}^{}}_{}}$- ${\displaystyle p_{}}$+ ${\displaystyle 1_{}}$)${\displaystyle {}_{}}$/ ${\displaystyle q_{}}$ ${\$을(를) 계산하십시오$.$
4. $d{\displaystyle }$ ${\displaystyle d}$이(가) 순서 $q{\displaystyle }$ ${\displaystyle q}$이$($가) 아닌$$ 경우 1단계로 돌아가십시오.
5. $Let{\displaystyle }$ T ${\displaystyle r}$( ${\displaystyle g}$)${\displaystyle }$= ${\displaystyle d}$ ${\displaystyle Tr(g)=d$

이 알고리즘이 $q{\displaystyle }$ ${\displaystyle q}$의 $일부$ G${\displaystyle }$∈ ${\displaystyle G}$ F${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$) ${\displaystyle Tr($$g$)}에 $대해$ T ${\displaystyle r}$ (${\displaystyle }$g${\displaystyle }$) ${\displaystyle$ Tr(g$)}$과 같은 $GF$${\displaystyle }$($p^{6})$의 요소를 실제로 계산하는 것으로 나타났다$.$

알고리즘, 정확성, 런타임 및 Lemma 증명에 대한 자세한 내용은 의 "XTR 공개 키 시스템의 개요"에서 확인할 수 있다.^[1]

암호 체계

이 절에서는 원소의 흔적을 이용한 위의 개념이 암호학에 어떻게 적용될 수 있는지 설명한다.일반적으로 XTR은 (하위 그룹) 이산 로그 문제에 의존하는 모든 암호 시스템에서 사용될 수 있다.XTR의 두 가지 중요한 애플리케이션은 Diffie이다.Hellman 키 계약과 ElGamal 암호화.디피부터 시작하자.헬먼

XTR-DH 키 계약

Alice와 Bob 모두 XTR 공개 키 데이터${\displaystyle (p}$ ,${\displaystyle q}$, ${\displaystyle T}$r ( ${\displaystyle g}$) ${\$에 액세스할 수 있으며 공유 비밀 키 $K{\displaystyle }$ ${\displaystyty K}$에 동의하려고 한다$.$ 다음 XTR 버전을 사용하여 이 작업을 수행할 수 있다.Hellman 키 교환:

1. Alice picks ${\displaystyle a\in \mathbb {Z} }$ randomly with ${\displaystyle 1<a<q-2}$, computes with Algorithm 1 ${\displaystyle S_{a}(Tr(g))$$=\left(Tr(g^{a-1}),Tr(g^{a}),Tr(g^{a+1})\right)\in GF(p^{2})^{3}}$ and sends ${\displaystyle Tr(g^{a})\in GF(p^{2})}$ to Bob.
2. 밥은 앨리스한테서, 임의의 b에 ∈ Z{\displaystyleb\in \mathbb{Z}선택하는}1<>와 q − 2{1<, b<, q-2\displaystyle}, Sb(Tr(g)))(Tr(gb− 1), Tr(gb), Tr(gb+1)를 계산하기 위해)알고리즘 1적용된다 ∈ GF(p2Tr(를 입수){Tr(g^{})\displaystyle}b<>를 받는다. =3{)$디스플레이 스타일 S_{b}(Tr(g))$$=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}}$ and sends ${\displaystyle Tr(g^{b})\in GF(p^{2})}$ to Alice.
3. Alice receives ${\displaystyle Tr(g^{b})}$ from Bob, computes with Algorithm 1 ${\displaystyle S_{a}(Tr(g^{b}))$$=\좌측(Tr(g^{(a-1)b}),Tr(g^{ab}),Tr(g^{(a+1)b}}$$\right)\in GF(p^{2}}^{3}}}$에 있는 ${\displaystyle \mathrm{GF}}$(g a ) ${\displaystyle {}^{}}$ G${\displaystyle {}^{}{F}^{}({p\mathrm{}}^{}}$ ${\displaystyle 2{}^{}}$)${\displaystyle Tr(g^{ab})\in GF(p^{2})$에 기반하여$$ $K{\displaystyle }$ ${\\displaysty K}$를 결정한다$.$
4. Bob은 알고리즘 1을 ${\displaystyle S_{}}$ $b{\displaystyle {}_{}T}$ r${\displaystyle }$( g${\displaystyle a^{}}$ )${\displaystyle }$=${\displaystyle }$( T${\displaystyle r^{}}$ ( g${\displaystyle {}^{}}$a (${\displaystyle b^{}}$ -${\displaystyle {}^{}{1}^{})),}$ ${\displaystyle T}$r ( ${\displaystyle {}^{}{a}^{}}$) , ${\displaystyle T}$ r${\displaystyle }$( ${\displaystyle g^{}}$ a${\displaystyle {}^{}}$( ${\displaystyle {\mathrm{b}}^{}}$+ 1${\displaystyle {}^{}}$)${\displaystyle }$) 계산에 유사하게 적용한다. ${\displaystyle \in }$ ${\displaystyle G}$ ${\displaystyle F}$( ${\displaystyle {}^{}{}^{}{2\mathrm{}}^{}}$ ) ${\displaystyle {3\mathrm{}}^{}}$ ${\$$=\left(Tr(g^{a(b-1)}),Tr(g^{ab}),Tr(g^{a(b+1)})\right)\in GF(p^{2})^{3}}$ and also determines ${\displaystyle K}$ based on ${\displaystyle Tr(g^{ab})\in GF(p^{2})}$.

XTR ElGamal 암호화

ElGamal 암호화의 경우, 이제 Alice가 XTR 공개 키 데이터$, q$ , ${\displaystyle T}$ ${\displaystyle r}$($$)${\displaystyle$$k$ 계산된 $T{\displaystyle }$ ${\displaystyle r}$( g k${\displaystyle {}^{}}$) ${\$$displaystyle$ $k{\displaystyle }$}, 계산된 T r (${\displaystyle {}^{}}$ ${\displaystyle k^{}}$ ){$displaystyTr(g^{k})$의 소유자라고$$ 가정하고$$ 있다.앨리스의 XTR 공개 키 데이터$({\displaystyle p}$, ${\displaystyle q}$, ${\displaystyle T}$ r${\displaystyle }$(${\displaystyle }$g )${\displaystyle }$, ${\displaystyle T}$ ${\displaystyle r}$( ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$)${\$(Tr$(g^{k}\rig)}})$를 감안할 때$,$ Bob은 다음과 같은 XTR 버전의 엘가말 암호화를 사용하여 앨리스용 메시지 ${\displaystytype$ M}을 암호화할 수 있다$.$

1. Bob selects randomly a ${\displaystyle b\in \mathbb {Z} }$ with ${\displaystyle 1<b<q-2}$ and computes with Algorithm 1 ${\displaystyle S_{b}(Tr(g))$$=\\좌측(G^{b-1}),Tr(g^{b}),Tr(g^{b+1}}\우측)\in GF($p^{$2})^{3$
2. 다음으로 Bob은 알고리즘 1을 $S{\displaystyle {}_{}}$ ${\displaystyle b_{}T}$ r${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle T^{}}$ r${\displaystyle }$(${\displaystyle {\mathrm{g}}^{}}$- 1${\displaystyle {}^{}}$) ${\displaystyle k^{}}$)${\displaystyle }$, ${\displaystyle T}$ ${\displaystyle r}$( ${\displaystyle {}^{}}$ ${\displaystyle b^{}}$ ${\displaystyle k^{}}$)${\displaystyle }$, ${\displaystyle T}$ ${\displaystyle r}$ ( g b k ) , T ${\displaystyle r}$( g (${\displaystyle {\mathrm{b}}^{}}$+ ${\displaystyle 1^{}}$)${\displaystyle {}^{}}$)${\displaystyle \in }$ G ${\displaystyle F}$( p ${\displaystyle {2\mathrm{}}^{}{}^{}}$) 3 ${\$ S_${b}(Tr(g^{k)})$에 적용한다.$=\\좌측(G^{(b-1)k}),Tr(g^{bk}),Tr(g^{(b+1)k}\우측)\in GF(p^{2}^{3$
3. Bob은 $(p^{2})$에서 $T{\displaystyle }$ r${\displaystyle ({}^{}}$ ${\displaystyle b^{}}$ k${\displaystyle {}^{}}$) ${\displaystyle \in }$ G ${\displaystyle F({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle Tr(g^{bk})\$in $GF$(p^{2})에 기반하여$$ 대칭 암호화 키 $K{\displaystyle }${\$displaysty K}$를 결정한다$.$
4. Bob은 $자신$의 메시지 $M{\displaystyle }$ ${\displaystyle$M}을(를) 암호화하기 위해$$ 키 $K{\displaystyle }${\$displaystyle$ $K}$과(와) 대칭 암호화 방법에 합의하여 E$$${\displaystyle$ E$}$을(를) 사용한다$.$
5. 밥은 앨리스에게${\displaystyle }$(${\displaystyle \text{T}}$ ${\displaystyle r}$( ${\displaystyle g^{}}$ b${\displaystyle {}^{}}$)${\displaystyle }$, E${\displaystyle }$) ${\displaystyle (Tr(g^{b}),\ E)}$을 보낸다.

$($${\displaystyle T}$ ${\displaystyle r}$( ${\displaystyle g^{}}$ b${\displaystyle {}^{}}$)${\displaystyle }$, ${\displaystyle \text{E}}$) ${\displaystyle (Tr(g^{b}),\ E)}$을 받은 앨리스는 다음과 같은 방법으로 메시지를 해독한다.

1. 앨리스는 $S{\displaystyle {}_{}}$ ${\displaystyle k_{}}$( ${\displaystyle T}$ ${\displaystyle r}$( g ${\displaystyle b^{}}$)${\displaystyle }$=${\displaystyle }$( T ${\displaystyle r}$( ${\displaystyle g^{}}$ ${\displaystyle {}^{}}$( k${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$)${\displaystyle }$, T ${\displaystyle r}$( ${\displaystyle {}^{}}$ ${\displaystyle b^{}}$ k${\displaystyle {}^{}}$)${\displaystyle }$, T r ( ${\displaystyle {}^{}}$ b ${\displaystyle k^{}}$ ) , ${\displaystyle T}$ ${\displaystyle r}$( g b${\displaystyle {}^{}}$+ ${\displaystyle 1^{}}$)${\displaystyle \in }$ ${\displaystyle G}$ F${\displaystyle }$( ${\displaystyle {p\mathrm{}}^{}}$ 2${\displaystyle {}^{}{}^{}}$) 3 ${\$를 계산한다.$=\\좌측(G^{b(k-1)}),Tr(g^{bk}),Tr(g^{b(k+1)}\우측)\in GF(p^{2}^{3$
2. 앨리스는 $GF(p^{$2})에서 T $r{\displaystyle ({}^{}}$ ${\displaystyle b^{}}$ ${\displaystyle k^{}}$) ${\displaystyle \in }$ G ${\displaystyle F({p\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle Tr(g^{bk})\$in GF(p^{$2})$를 기준으로 대칭 $키{\displaystyle }$ K ${\displaystystyle K}$를 결정한다$.$
3. 앨리스는 키 $K{\displaystyle }$ ${\displaystyle K$$}$과(와) 합의된 대칭 $암호화$ 방법을 사용하여$$E {\$displaystyle$ E}을(를) 해독하고$$원본 메시지 $M{\displaystyle }$ ${\displaystyle M}$을(를) 생성한다$.$

여기서 설명한 암호화 체계는 ElGamal 암호화의 일반적인 하이브리드 버전을 기반으로 하며, $여기$서 암호키 K ${\displaystyle K}$를 비대칭 공개 키 시스템에 의해 얻은 다음$$ 앨리스와 밥이 동의한 대칭 키 암호화 방법으로 암호화한다.

In the more traditional ElGamal encryption the message is restricted to the key space, which would here be ${\displaystyle GF(p^{2})}$, because ${\displaystyle Tr(g)\in GF(p^{2})\ \forall p\in GF(p^{6})^{*}}$. The encryption in this case is the multiplication of t키 공간 $G{\displaystyle }$ ${\displaystyle F({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle GF(p^{2})$에서 되돌릴 수 없는 작업인 키를 가진 메시지$.$

Concretely this means if Bob wants to encrypt a message ${\displaystyle M\!\ '}$, first he has to convert it into an element ${\displaystyle M}$ of ${\displaystyle GF(p^{2})}$ and then compute the encrypted message ${\displaystyle E}$ as ${\displaystyle E=K\cdot M$$\in GF(p^{2})}$. Upon receipt of the encrypted message ${\displaystyle E}$ Alice can recover the original message ${\displaystyle M}$ by computing ${\displaystyle M=E\cdot K^{-1}}$, where ${\displaystyle K^{-1}}$ is the inverse of ${\displaystyle K}$ in ${\display$$스타일 GF(p^{2})$.

보안

위에서 설명한 XTR 암호화 체계의 보안 속성에 대해 뭐라고 말하려면 먼저 XTR 그룹의 보안을 확인하는 것이 중요하며, 이는 그곳에서 이산 로그 문제를 해결하는 것이 얼마나 어려운가를 의미한다.그런 다음 다음 파트에서는 XTR 그룹의 이산 로그 문제와 이산 로그 문제의 XTR 버전 사이의 동등성을 요소의 트레이스만 사용하여 기술한다.

일반 $G{\displaystyle }$ ${\displaystyle F({}^{}}$ ${\displaystyle t^{}}$) ${\$의 이산 로그

이제 $⟨{\displaystyle }$ ${\displaystyle \gamma }$ {\$displaystyle \langle$ \langle $\gamma$ $\$$rangele}}$을(를$)$ Ω {\$displaystyle \$omega}의 다중 순서 그룹으로$$ 합시다.$$Diffie–의 보안.$⟨{\displaystyle }$ ${\displaystyle \gamma }$ ${\displaystyle ⟩}$ ${\displaystyle \langle \gamma \rangle }$의 Hellman 프로토콜은 Diffie–에 의존한다$$.Hellman (DH) problem of computing ${\displaystyle \gamma ^{xy}{\text{ given }}\gamma ,\gamma ^{x}{\text{ and }}\gamma ^{y}}$. We write ${\displaystyle DH(\gamma ^{x},\ \gamma ^{y})=\gamma ^{xy}}$.DH 문제와 관련된 다른 두 가지 문제가 있다.첫 번째는 디피-헬먼 결정 만약 c=DH{\displaystyle c=DH(a,b)}(a, b)을 결정하기 위해서 문제(DHD)된, b, c∈ ⟨γ ⟩{\displaystyle a,b,c\in \langle \gamma \rangle}, 다른 하나는 이산 로그(DL)문제에 찾xxDL(를){\displaystyle x=DL(를)}에 주어진 a=γ)∈⟨ γ ⟩과 0≤)<>.;ω$\displaystyle a=\cHB ^{x}\in \langle \langle {\text{{}}, }0\leq$ x$<\omega$

DL 문제는 적어도 DH 문제만큼 어려우며 일반적으로 $⟨{\displaystyle }$ ${\displaystyle \gamma }$ { ${ \$ {\$displaystyle$ \$langle \gamma \angle$}의 DL 문제가 다루기 어려운 경우$$ 나머지 두 가지 문제도 다루기 어렵다고 가정한다.

$\Omega {\displaystyle }$ ${\displaystyle \omega}$의 primary factorization을 고려할 때, Pohlig–로 인해 프라임 순서와 함께 $⟨{\displaystyle }$ ${\displaystyle \gamma }$ γ ${\displaystyle \backslash }$ $\$$$\$langle$ $\angle }$의 모든 하위 그룹에서 DL 문제로 축소할$$ 수 있다$$.헬만 알고리즘.따라서 $\Omega {\displaystyle }$ ${\displaystyle \omega}$은(는) 안전하게 프라임으로 가정할 수 있다$$.

부분군 $⟨{\displaystyle }$ ${\displaystyle \gamma }$ {\$displaystyle \langle$\langle \$gamma \rangle$$$$}$의 경우, 승수 그룹 ${\displaystyle \mathrm{GF}{{}^{}}^{}}$ ${\displaystyle {t^{}}^{}}$)${\displaystyle {}^{}}$$\omega {\displaystyle }$ ${\$의 프라임 순서 Ω ${\\\\\\\\\displaystydisplaysty$}일부 $t{\displaystyle }$ ${\displaystyle t}$에 $대해{\displaystyle }$ ${\displaystyle G}$ F${\displaystyle (p)}$ ${\displaystyle GF(p$$^{t$$})}$의 확장 필드 ${\displaystyle \mathrm{GF}}$({*}) 중$$ $^{}}},$ 이제 시스템을 공격하는 두 가지 방법이 있다$.$사람은 전체 승수 그룹에 초점을 맞출 수도 있고 하위 그룹에 초점을 맞출 수도 있다.To attack the multiplicative group the best known method is the Discrete Logarithm variant of the Number Field Sieve or alternatively in the subgroup one can use one of several methods that take ${\displaystyle {\mathcal {O}}({\sqrt {\omega }})}$ operations in ${\displaystyle \langle \gamma \rangle }$, such as Pol라드의 rho 방식

For both approaches the difficulty of the DL problem in ${\displaystyle \langle \gamma \rangle }$ depends on the size of the minimal surrounding subfield of ${\displaystyle \langle \gamma \rangle }$ and on the size of its prime order ${\displaystyle \omega }$. If ${\displaystyle GF\left(p^{t}\r$$ight)}$ itself is the minimal surrounding subfield of ${\displaystyle \langle \gamma \rangle }$ and ${\displaystyle \omega }$ is sufficiently large, then the DL problem in ${\displaystyle \langle \gamma \rangle }$ is as hard as the general DL problem in ${\displaystyle GF\left(p^{t}\right)}$.

The XTR parameters are now chosen in such a way that ${\displaystyle p}$ is not small, ${\displaystyle q}$ is sufficiently large and ${\displaystyle \langle g\rangle }$ cannot be embedded in a true subfield of ${\displaystyle GF(p^{6})}$, since ${\displaystyle q\mid p^{2}-p+$$1}$ 및$$ $p{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ -${\displaystyle {}^{}\mathrm{p}}$+ ${\displaystyle 1}$ ${\displaystyle$ p$^{2}-p+1$}은$($는)${\displaystyle f}$ G F(${\displaystyle {p\mathrm{}}^{}}$ 6${\displaystyle {}^{}{}^{}}$)${\displaystyle \ast ={}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$- ${\displaystyle 1}$ ${\displaysty \mid \!$의 구분자임$$$GF(p^{6})^{*}\!\mid =p^{6}-1}$, but it does not divide ${\displaystyle p^{s}-1{\text{ for }}s\in \{1,2,3\}}$ and thus ${\displaystyle \langle g\rangle }$ cannot be a subgroup of ${\displaystyle GF\!\ (p^{s})$$^*}{{*}$ $s{\displaystyle \{1}$, ${\displaystyle 2}$,${\displaystyle 3}$ ${\displaystyle \}}$ ${\displaystyle s\in \{1,2,3\}}$에 대해$$$.$ XTR 그룹의 DL 문제는 ${\displaystyle \mathrm{GF}}$(${\displaystyle {}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$) ${\displaystyle GF(p^{6})$의 DL 문제만큼 단단하다고 가정할 수 있다$.$

XTR의 보안

이산 로그에 기반한 암호화 프로토콜은 타원 곡선 지점의 그룹이나 XTR 그룹과 같은 유한 분야의 승수 그룹의 하위 그룹과 같은 여러 가지 종류의 하위 그룹을 사용할 수 있다.XTR 버전의 Diffie-에서 살펴본 바와 같이.Hellman 및 ElGamal 암호화 프로토콜은 XTR 그룹의 요소를 트레이스를 사용하여 대체한다.이는 이러한 암호화 체계의 XTR 버전의 보안이 더 이상 원래의 DH, DHD 또는 DL 문제에 기초하지 않는다는 것을 의미한다.따라서 이러한 문제의 XTR 버전은 정의되어야 하며 우리는 그것들이 원래의 문제와 동등하다는 것을 알게 될 것이다.

정의:

• We define the XTR-DH problem as the problem of computing ${\displaystyle Tr(g^{xy})}$ given ${\displaystyle Tr(g^{x})}$ and ${\displaystyle Tr(g^{y})}$ and we write ${\displaystyle XDH(g^{x},\ g^{y})=g^{xy}}$.
• $XTR-DHD$ 문제는 ${\displaystyle \mathrm{XD}}$ H${\displaystyle }$( a ,${\displaystyle b}$)${\displaystyle }$= $a{\displaystyle }$, ${\displaystyle b}$, ${\displaystyle c}$ , c ${\displaystyle \in }$ ${\displaystyle T}$ $r$($$ ${\displaystyle g}$⟩${\displaystyle }$)$$${\displaystyle$ $XDH(a$$,b)=$$c}$의 여부를$$ 결정하는$문제다.$
• Given ${\displaystyle a\in Tr(\langle g\rangle )}$, the XTR-DL problem is to find ${\displaystyle x=XDL(a)}$, i.e. ${\displaystyle 0\leq x<q}$ such that ${\displaystyle a=Tr(g^{x})}$.
• We say that problem ${\displaystyle {\mathcal {A}}}$ is (a,b)-equivalent to problem ${\displaystyle {\mathcal {B}}}$, if any instance of problem ${\displaystyle {\mathcal {A}}}$ (or ${\displaystyle {\mathcal {B}}}$) can be solved by at most a (or b) calls to an algorithm solving problem ${$$\displaystyle {\mathcal{B}($$또는{\displaystyle \mathcal{}}$ A ${\$ $$.

이러한 문제의 XTR 버전을 도입한 후 다음 정리는 XTR과 사실상 동등한 XTR 문제 사이의 연관성을 알려주는 중요한 결과물이다.이는 위에서 볼 수 있듯이, 보안에 영향을 주지 않으면서 일반적인 표현보다 3배 빠른 추적을 가진 요소들의 XTR 표현이라는 것을 의미한다.

정리 다음과 같은 동등성은 유지된다.

i. XTR-DL 문제는 (1,1)- $⟨{\displaystyle }$ ${\displaystyle g}$\ ${\displaystyle \langle g\angle }$의 DL 문제와 동일하다$.$

ii. XTR-DH 문제는 (1,2)- $⟨{\displaystyle }$ ${\displaystyle g}$\ ${\displaystyle \langle g\angle }$의 DH 문제와 동일하다$.$

iii. XTR-DHD 문제는 (3,2)- $-{\displaystyle }$ ${\displaystyle g}$⟩ ${\displaystyle \langle g\angle }$의 DHD 문제와 동일하다$.$

즉, XTR-DL, XTR-DH 또는 XTR-DHD 중 하나를 불가해한 확률로 해결하는 알고리즘을 해당 비-XTR 문제 DL, DH 또는 DHD를 불가해한 알고리즘으로 변환할 수 있으며 그 반대의 경우도 마찬가지다.In particular part ii. implies that determining the small XTR-DH key (being an element of ${\displaystyle GF(p^{2})}$) is as hard as determining the whole DH key (being an element of ${\displaystyle GF(p^{6})}$ ) in the representation group ${\displaystyle \langle g\rangle }$.

참조