높은 잔류성 문제

암호학에서 대부분의 공개 키 암호 체계는 난치성이 있다고 여겨지는 문제들에 기초한다.높은 잔류성 문제(n th-residity 문제라고도^[1] 함)는 그러한 문제 중 하나이다.이 문제는 정수 인자화보다 풀기 쉬우므로 이 문제가 풀기 어렵다는 가정은 정수 인자화가 어렵다는 가정보다 강하다.

수학적 배경

n이 정수일 경우, 정수 modulo n은 링을 형성한다.p와 q가 소수인 n=pq를 말한다면, 중국의 나머지 정리는 우리에게 다음과 같이 말해준다.

${\displaystyle \mathb {Z} /n\mathb {Z} \simeq \mathb {Z} /p\mathb {Z} \timeb \mathb {Z} \timeb {Z} \mathb {Z} \q\mathb {Z}}}}$

모든 링의 단위 그룹이 그룹을 형성하며, $Z{\displaystyle \mathbb{}/n\mathbb{}}$ Z ${\$의 단위 그룹은 전통적으로${\displaystyle }$(${\displaystyle Z\mathbb{}/n}$ ${\displaystyle Z\mathbb{}){}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$로 표시된다$.$

위와 같은 이형성으로부터 우리는

${\displaystyle(\mathb {Z} /n\mathb {Z} )^{*}\simeq(\mathb {Z} /p\mathb {Z}}^{*}번(\mathb {Z} /q\mathb {Z} )^{*}}}$

집단의 이형화로서p와 q는 primary로 가정하였으므로, 그룹$({\displaystyle Z\mathbb{}/p}$ ${\displaystyle Z\mathbb{}{}^{}}$) $∗{\$과 $({\displaystyle Z\mathbb{}/q}$ ${\displaystyle Z\mathbb{}{}^{}}$) ${\displaystyle {\ast }^{}}$ ${\$ ){{Z$}^{*$는 각각 p-1과 q-1의 순환이다.d가 p-1의 divisor인 경우$,{\displaystyle }$ (${\displaystyle Z\mathbb{}}$/ ${\displaystyle p{}^{}Z\mathbb{}}$ ) ${\displaystyle {\ast }^{}}$ ${\$(\$mathb {Z} /p\mathb {Z} )^{*}}$의 d번째 검정력 집합이 d의 하위 그룹을 형성한다$$.If gcd(d,q-1) = 1, then every element in ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$ is a dth power, so the set of dth powers in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ is also a subgroup of index d.In general, if gcd(d,q-1) = g, then there are (q-1)/(g) dth powers in ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$, so the set of dth powers in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ has index dg.이것은 d=2일 때 가장 흔히 나타나며, 우리는 2차 잔류물의 부분군을 고려하고 있는데$,{\displaystyle }$ (${\displaystyle Z\mathbb{}/n\mathbb{}}$ Z${\displaystyle {}^{}}$) ${\displaystyle {\ast }^{}}$ ${\$의 원소의 정확히 4분의 1이 2차 잔류물(n은 여기서와 같이 정확히 2회의 산물인 경우)인$$ 것으로 잘 알려져 있다.

중요한 점은 p-1${\displaystyle (}$또는 q-1)의 divisor d에 대해 dth powers 집합이${\displaystyle }$(${\displaystyle Z\mathbb{}{}^{}}$/${\displaystyle {}^{}}$n Z )의 하위 그룹을 형성한다는 것이다${\displaystyle {}^{}}$ ${\displaystyle(\mathb {Z}/n$ /n$\mathb {Z} )^{*}}}$

문제명세서

p와 q를 알 수 없는 정수 n = pq, d와 같은 정수 d와 정수 x < n을 나눈다면 x가 d번째 전력(동등 d번째 잔류물) modulo n인지를 판단할 수 없다.

p와 q가 알려진 경우, x가 d번째 잔류물 모듈로 n인지 쉽게 판단할 수 있다는 점에 유의하십시오.

${\displaystyle x^{(p-1)/d}\equiv 1{\pmod{p}}}$

d=2일 때 이것을 2차 잔류성 문제라고 한다.

적용들

베날로 암호체계와 나카체-스테인 암호체계의 의미적 보안은 이 문제의 난해성에 달려 있다.

참조