머클-헬만 배낭 암호체계

더 머클-헬먼 배낭 암호 시스템은 초기 공개키 암호체계 중 하나이다.1978년 랄프 머클과 마틴 헬먼에 의해 출판되었다.다항식 시간 공격은 1984년에 Adi Shamir에 의해 출판되었다.그 결과, 암호체계는 현재 불안정한 것으로 간주되고 있다.^{[1]: 465 [2]: 190}

역사

공개키 암호화의 개념은 1976년 휘트필드 디피와 마틴 헬먼에 의해 도입되었다.^[3]당시 그들은 어떤 비밀 "트랩도어" 정보 없이는 계산하기 어려운 함수인 "트랩도어 함수"의 일반적인 개념만을 제안했지만, 아직 그러한 함수의 실질적인 예를 찾지 못하고 있었다.그 후 1977년 RSA, 1978년 Merkle-Hellman과 같은 몇 년 동안 다른 연구자들에 의해 구체적인 공개키 암호 시스템이 제안되었다.^[4]

설명

Merkle-Hellman은 공개키 암호체계로, 암호화를 위한 공개키와 암호 해독을 위한 비공개키라는 두 개의 키가 사용된다.그것은 서브셋 합계 문제(캡삭 문제의 특별한 경우)에 근거한다.^[5]문제는 다음과 같다: 정수 $A{\displaystyle }$ ${\displaystyle A}$과 정수 c ${\displaystyle c}$의 집합이 주어진$$$경우{\displaystyle }$ c$${\$displaystyle c}$에 $해당$하는 A ${\displaystyle A}$의 하위 집합을 찾으십시오$.$ 일반적으로 이 문제는 NP-완전한 것으로 알려져 있다.그러나 $A{\displaystyle }$ ${\displaystyle A}$이(가) 증가하여 집합의 각 요소가 집합의 모든 숫자의 합보다 작을 경우 문제는 "쉬운"이며 단순한 탐욕 알고리즘으로 다항식 시간에 해결할 수 있다.

인 머클-헬먼, 메시지 암호를 해독하려면 겉보기에는 "힘든" 배낭 문제를 해결해야 해.개인 키에는 숫자 $W{\displaystyle }$ ${\displaystyle W}$의 증가 목록이 포함되어 있으며$,$ 공용 키에는 $실제로{\displaystyle }$ W ${\displaystyle W}$의 "disguided" 버전인 숫자 $B{\displaystyle }$ ${\displaystyle B}$의 증가되지 않는 목록이 포함되어 있다$.$ 개인 키에는 하드 변환에 사용할 수 있는 일부 "rapdoor" 정보도 포함되어 있다.$B{\displaystyle }$ ${\displaystyle B}$을(를) 사용한 배낭 문제에서$$ W ${\displaystyle W}$을(를$)$ 사용한 손쉬운 배낭 문제.

RSA와 같은 다른 공개 키 암호 시스템과 달리, Merkle-Hellman의 두 키는 서로 교환할 수 없으므로 개인 키를 암호화에 사용할 수 없다.따라서 Merkle-Hellman은 Samir가 서명에 사용할 수 있는 변종을 발표했음에도 불구하고 암호화 서명에 의한 인증에 직접 사용할 수 있는 것은 아니다.^[6]

키 생성

1. 블록 크기 $n{\displaystyle }$ ${\displaystyle n}$을 선택하십시오$.$ 이 키로 $최대{\displaystyle }$ n {\$displaystyle$ n$}비트$ 길이의$$ 정수를 암호화할 수 있다.

2. $n{\displaystyle }$ ${\displaystyle n}$ 양의 정수의 랜덤하게 증가된 시퀀스 선택

${\displaystyle W=(w_{1},w_{2},\dots ,w_{n}}}}$

은 > i= - 1 ${\$ 1 < ${\displaystystyle 1<k\$c\$leqn$ .

3. 무작위 정수 $q{\displaystyle }$ ${\displaystyle q}$을(를) 다음과 같이$$ 선택한다.

${\displaystyle q>\sum _{i=1}^{n}w_{i}}}}$

4. ${\displaystyle gcd(r}$ ,${\displaystyle q}$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle \gcd(r,q)=1}($$즉{\displaystyle }$, r ${\displaystyle r}$ 및 $q{\displaystyle }$ ${\displaystyle q}$이(가) 같은 값인 임의$$ $정수{\displaystyle }$ r ${\displaysty$ r}을 선택하십시오$.$

5. 순서 계산

${\displaystyle B=(b_{1},b_{2},\dots ,b_{n}}}}$

여기서 $b{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle r}$ ${\displaystyle {}_{}}$ ${\displaystyle mod}$ ${\displaystyle q}$ ${\$

공개 키는 $B{\displaystyle }$ ${\displaystyle B}$이고 개인 키는${\displaystyle }$(${\displaystyle W}$, ${\displaystyle q}$, r${\displaystyle }$) ${\displaystyle (W,q,r)}$ 입니다$.$

암호화

$m{\displaystyle {}_{}}$ ${\displaystyle m}$을(를) ${\displaystyle {n\mathrm{}}_{}}$ ${\displaystyle n}$ -bit$$ m ${\displaystyle {1m\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {}_{}{m}_{}}${\$displaystyle m_{1}m_{$2}\$dots$m_${n$로 구성되며 ${\displaystyle {m\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$이 가장$$ 높은 순서 비트로 한다.$m{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$이(가) 0이 아닌 $각{\displaystyle {}_{}}$ ${\displaystyle b_{}}$ i$${\$displaystyle$ b_{i$}$를 선택하고 함께 추가하십시오.동등하게 계산한다.

${\displaystyle c}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle i_{}}$ b ${\displaystyle i_{}}$ ${\$

$암호문$은 c ${\displaystyle c}$ 입니다$.$

암호 해독

암호문 $c{\displaystyle }$ ${\displaystyle c}$을$($를) 해독하려면 $c{\displaystyle }$ ${\displaystyle$c}을$($를) 합한 B {\$displaystyle$ c$}$의 서브셋을 찾아야 한다$.$ 우리는 $문제$를 $W{\displaystyle }$$$${\displaystyle W$}의$$ 서브셋을 찾는 것의 하나로 변환함으로써 이 문제는 다항식 시간 내에 해결될 수 있다$.$

1. 확장유클리드 알고리즘을 사용하여$$ $r{\displaystyle }$ ${\displaystyle r}$ modulo$$ $q{\displaystyle }$ ${\displaystyle q}$의 모듈 반전을 계산한다.$r{\displaystyle }$ ${\displaystyle r}$이(가) $q{\displaystyle }$ ${\displaystyle q}$과(와) 동일하므로 역이 존재할 것이다$.$

${\displaystyle r':=r^{-1}{\pmod{q}}$

$r{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 계산은 메시지와 무관하며$$, 개인 키가 생성되었을 때 한 번만 할 수 있다.

2. 계산하다

${\displaystyle c':=cr'{\bmod{q}}$

3. 아래에 설명된 간단한 탐욕 알고리즘에 의해 증가 $시퀀스{\displaystyle }$ W ${\displaystyle W}$을(를$)$ $사용$하여 c${\displaystyle {}^{}}$′$${\$displaystyle c'}$에 대한 부분집합 문제를 해결하십시오.Let ${\displaystyle X=(x_{1},x_{2},\dots ,x_{k})}$ be the resulting list of indexes of the elements of ${\displaystyle W}$ which sum to ${\displaystyle c'}$. (That is, ${\displaystyle c'=\sum _{i=1}^{k}w_{x_{i}}}$.)

4. ${\displaystyle {메시지}_{}}$ m ${\$ 비트$$ 위치에 각각 1개, 기타 모든 비트 위치에 0개씩 메시지$$ $m{\displaystyle }$ {\$displaystyle m}$을(를) 생성하십시오.

${\displaystyle m=\sum _{i=1}^{k}2^{n-x_{i}}}$

부분합계 문제 해결

이 단순한 탐욕 알고리즘은 다항식 시간에서 $c{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을$($를) 합한 증가$$ $시퀀스{\displaystyle }$ W ${\displaystyle W}$의 하위 집합을 찾는다.

1. $X{\displaystyle }$ ${\displaystyle X}$을(를) 빈 목록으로$$ 초기화하십시오.

2. $W{\displaystyle {}^{}}$${\$ $W$$}$에서 c ${\displaystyle {say}_{}}$ ${\$ c$'}$보다 작거나 같은 가장$$ 큰 요소를 $찾으십시오{\displaystyle {}_{}}$$.$$$w j {\displaystyle w_${j}$라고 말하십시오$.$

3. 빼기: $c{\displaystyle {}^{}}$′ ${\displaystyle :={}^{}}$′${\displaystyle }$- ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$ c$':=c'-w_{j$

4. $목록{\displaystyle }$ $X$에 j ${\$$displaystyle j$$}$을(를$)$ 추가하십시오$.$

5. $c{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$이(가) 0보다 크면 2단계로 돌아가십시오.

예

키 생성

다음과 같은 8개 값의 무작위적으로 증가된 시퀀스를 만들어 8비트 숫자를 암호화하는 키를 만드십시오.

${\displaystyle W=(2,7,11,21,42,89,180,354)}$

합계가 706이므로 $q{\displaystyle }$ ${\displaystyle q}$에 대해 더 큰 값을 선택하십시오$.$

${\displaystyle q}$= ${\displaystyle 881}$ ${\displaystyle q=881$

$q{\displaystyle }$ ${\displaystyle q}$에 복사하려면 r ${\displaystyle$ r$}$을(를) 선택하십시오$.$

${\displaystyle r}$= ${\displaystyle 588}$ ${\displaystyle r=588$

$W{\displaystyle }$ ${\displaystyle W}$의 각 요소에 $r{\displaystyle }$ ${\displaystyle r}$ modulo$$ $q{\displaystyle }$ ${\displaystyle q}$을(를) 곱하여$$ 공용 $키{\displaystyle }$ B ${\displaystyle B}$을(를) 생성하십시오$.$

${\displaystyle {\begin{aligned}&(2*588){\bmod {8}}81=295\\&(7*588){\bmod {8}}81=592\\&(11*588){\bmod {8}}81=301\\&(21*588){\bmod {8}}81=14\\&(42*588){\bmod {8}}81=28\\&(89*588){\bmod {8}}81=353\\&(180*588){\bmod {8}}81=120\\&(354*588){\bmod {8}}81=236\end{aligned}}}$

그러므로 $B{\displaystyle }$=${\displaystyle }$(${\displaystyle 295,}$ ${\displaystyle 592}$, ${\displaystyle 301}$, ${\displaystyle 14,}$ ${\displaystyle 28,}$ ${\displaystyle 353}$, ${\displaystyle 120,}$ ${\displaystyle 236}$) ${\displaystyle B=(295,592,301,14,28,353,120,236$

암호화

8비트 메시지를 $m{\displaystyle }$= ${\displaystyle 97}$= ${\displaystyle {01100001\mathrm{}}_{}}$ 2 ${\$ 각 비트에 $B{\displaystyle }$ ${\displaystyle B}$의 해당 숫자를 곱하고 결과를$$ 추가한다.

0 * 295 + 1 * 592 + 1 * 301 + 0 * 14 + 0 * 28 + 0 * 353 + 0 * 120 + 1 * 236     = 1129

암호 텍스트 $c{\displaystyle }$ ${\displaystyle c}$은(는) 1129이다.

암호 해독

1129의 암호를 해독하려면 먼저 확장 유클리드 알고리즘을 $사용$하여 r ${\displaystyle r}$md$$ $q{\displaystyle }${\$displaystyle q}$의 모듈 반전을 찾으십시오$.$

${\displaystyle r^{}}$ ${\displaystyle {\prime }^{}}$= ${\displaystyle {\mathrm{r}}^{}}$- 1 ${\displaystyle mod}$ ${\displaystyle q}$= ${\displaystyle {588}^{}}$- 1 ${\displaystyle mod}$ 8 ${\displaystyle 81}$= ${\displaystyle 442}$ ${\displaystyle r'=r^{-1}{\bmod {q}=588^{-1}{\bmod {8}81=442$ .

계산 $c{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$= c ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle mod}$ ${\displaystyle q}$= ${\displaystyle 1129}$ ${\displaystyle \ast }$ ${\displaystyle 442}$ ${\displaystyle mod}$ 8 ${\displaystyle 81}$= ${\displaystyle 372}$ ${\displaystyle c'=cr'{\bmod {q}=1129*442{\bmod {8}81=372$ .

탐욕스러운 알고리즘을 사용하여 ${\displaystyle {372}_{}}$를$$w i {\displaystyle $w_{i}$ 값의$$ 합으로 분해하십시오.

${\displaystyle {\begin{aligned}c'&=372\\&w_{8}=354\leq 372\\c'&=372-354=18\\&w_{3}=11\leq 18\\c'&=18-11=7\\&w_{2}=7\leq 7\\c'&=7-7=0\end{aligned}}}$

따라서 ${\displaystyle 372}$= ${\displaystyle 354}$+ ${\displaystyle 11}$+ ${\displaystyle 7}$= ${\displaystyle {w\mathrm{}}_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$+ w ${\displaystyle {3\mathrm{}}_{}}$+ w 2 {\$displaystyle 372=354+11+7=w_{8}+w_{$3}+$w_{2$ 색인 $목록$은 X${\displaystyle }$=${\displaystyle }$(${\displaystyle 8}$, ${\displaystyle 3}$, $){\displaysty X=(8,3$, 2, 2$)}$로 계산할 수 있다$.$

${\displaystyle m}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle 2^{}}$ ${\displaystyle \underset{}{\overset{}{}}{\mathrm{}}^{}}$ -${\displaystyle {{}_{}}^{}}$ i${\displaystyle {{}_{}}^{}}$= 2 ${\displaystyle 8^{}}$- ${\displaystyle {8\mathrm{}}^{}}$- ${\displaystyle 3^{}}$+ ${\displaystyle {\mathrm{}}^{}}$ + ${\displaystyle {2\mathrm{}}^{}}$- ${\displaystyle 2^{}}$= ${\displaystyle 1}$+ ${\displaystyle 32}$+ ${\displaystyle 64}$ = ${\displaystyle$ m$=\sum _{i=1}^{3}2^{n-x_}}}=2^{8-8-8-8}+3}=1+32+64$97.

암호해석

이 구간은 확장이 필요하다.덧셈으로 도움받을 수 있다(2020년 9월)

1984년에 Adi Shamir는 개인 키를 사용하지 않고도 다항식 시간에 암호화된 메시지를 해독할 수 있는 Merkle-Hellman 암호 시스템에 대한 공격을 발표했다.^[7] The attack analyzes the public key ${\displaystyle B=(b_{1},b_{2},\dots ,b_{n})}$ and searches for a pair of numbers ${\displaystyle u}$ and ${\displaystyle c}$ such that ${\displaystyle (ub_{i}{\bmod {m}})}$ is a superincreasing sequence.공격에 의해 발견된${\displaystyle }$(${\displaystyle u}$, ${\displaystyle m}$) ${\displaystyle (u,m)}$ 쌍은$$ 개인 키의$$ $({\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$, ${\displaystyle q}$) ${\displaystyle (r',q)}$과 같지 않을 수 있지만, 이 쌍과 $마찬가지$로 B$${\$displaystyle B}$을(으)를 사용하는 하드 배낭 문제를 초증가 시퀀스를 사용하는 쉬운 문제로$$ 변환하는 데 사용할 수 있다.그 공격은 오직 공개 키에서만 작동한다. 암호화된 메시지에 대한 접근은 필요하지 않다.

참조