나카체-스테인 배낭 암호체계

나카체-스테인 배낭 암호체계는 데이비드 나카체와 자크 스턴이 1997년 개발한 비정형 공개키 암호체계다.이 암호 체계는 결정론적이므로 의미론적으로 안전하지 않다.이 시스템은 현재까지 유지되고 있지만, 입증 가능한 보안도 부족하다.

시스템 개요

이 시스템은 배낭 문제의 한 종류에 기초하고 있다.구체적으로, 근본적인 문제는 다음과 같다$$: 정수 c,n,p 및 v₀,...,v_n, 벡터 $x{\displaystyle }$ ${\displaystyle \in \{0,}$ 1${\displaystyle {}^{}}$} ${\displaystyle n^{}}$ ${\$ x$\in \{0,1\}^{n}}}$

${\displaystyle c\equiv \prod _{i=0}^{nv_{i}^{x_{i}}\mod p}$

여기서의 생각은 v가_i 비교적 원초적이고 계수 p보다 훨씬 작을 때 이 문제는 쉽게 해결될 수 있다는 것이다.암호 해독이 가능한 것은 이 관찰이다.

키 생성

공용/개인 키 쌍을 생성하려면 다음과 같이 하십시오.

• 큰 소수 p를 골라라.
• 0에서 n까지의 i에 대해 양의 정수 n을 선택하고 p₀ = 2로 시작하는 p를_i ih prime으로 설정하십시오. = < ${\displaystyle \pd \pd _{$i=0}^{$n}p_{i$
• gcd(p-1,s) = 1과 같은 비밀 정수 s < p-1>을 선택한다.
• $v{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle p\text{exception 25:}}$ ${\displaystyle \text{exception 25:}}$ ${\displaystyle \sqrt[]{{}_{}}}$ ${\displaystyle \mathrm{mod}\text{exception 25:}}$ ${\displaystyle p}$ ${\displaystyle v_{i}={\sqrt[{s}]{p_{i}}\mod p}$을(를) 설정하십시오$.$

공용 키는 p,n,v₀,...,v_n 입니다. 개인 키는 s 입니다.

암호화

n비트 긴 메시지 m을 암호화하려면, 계산한다.

${\displaystyle c=\prod _{i=0}^{nv_{i}^{m_{i}\mod p}$

여기서 m은_i 메시지 m의 ith 비트다.

암호 해독

메시지 c의 암호를 해독하려면

${\displaystyle m=\sum _{i=0}^{n}{\frac {2^{p_{i}-1}\reft(\gcd(p_{i}},c^{s}\mod p)-1\right}}}$

이것은 분수령이 떨어지기 때문에 효과가 있다.

${\displaystyle {\frac {\gcd(p_{i},c^{s}\mod p)-1}{p_{i}-1}}$

p가_i c^s mod p를 나누는지에 따라 0 또는 1이다.

참고 항목

• 머클-헬만 배낭 암호체계
• 그레이엄-샤미르 배낭 암호체계

참조

• 원본 용지
• 최근의 대역폭 개선