맥엘리스 암호체계

암호학에서 맥엘리스 암호체계는 1978년 로버트 맥엘리스가 개발한 비대칭 암호 알고리즘이다.^[1] 그것은 암호화 과정에서 무작위화를 사용한 최초의 계획이었다. 이 알고리즘은 암호화 커뮤니티에서 그다지 수용된 적이 없지만, 쇼어의 알고리즘을 이용한 공격에 면역이 되고 더 일반적으로는 푸리에 샘플링을 사용하여 코셋 상태를 측정하는 것이 가능하기 때문에 "사후 수량 암호화"의 후보작이다.^[2]

알고리즘은 일반 선형 코드(NP-hard라고^[3] 알려져 있음)의 디코딩 경도에 기초한다. 개인 키에 대한 설명을 위해 효율적인 디코딩 알고리즘을 알고 $t{\displaystyle }$ ${\displaystyle t}$ 오류를$$ 수정할 수 있는 오류 수정 코드가 선택된다. 원래의 알고리즘은 바이너리 고파 코드(특성 2의 유한한 영역에 대한 속 0 곡선의 기하학적 고파 코드의 하위 필드 코드)를 사용한다. 이러한 코드는 패터슨에 의한 알고리즘 덕분에 효율적으로 해독될 수 있다.^[4] 공개 키는 선택한 코드를 일반 선형 코드로 위장하여 개인 키에서 파생된다. 이를 위해 코드의 제너레이터 $매트릭스{\displaystyle }$ G ${\displaystyle G}$이(가) 무작위로 선택된 두 개의 반전성 $매트릭스{\displaystyle }$ S ${\displaystyle S}$ 및 $P$ ${\displaystyle P}$에 의해 동요된다$$($$아래 참조).

이 암호 시스템의 변형들은 다른 종류의 코드를 사용하여 존재한다. 그들 중 대부분은 덜 안전하다는 것이 증명되었다; 그것들은 구조적인 해독에 의해 깨졌다.

고파 코드를 가진 맥엘리스는 지금까지 암호 분석에 저항해왔다. 알려진 가장 효과적인 공격은 정보 세트 디코딩 알고리즘을 사용한다. 2008년 논문은 공격과 해결책을 모두 설명한다.^[5] 또 다른 논문은 양자컴퓨팅의 경우 정보 집합 디코딩의 개선으로 키 사이즈가 4배 증가해야 한다는 것을 보여준다.^[6]

McEliece 암호 시스템은 예를 들어 RSA에 비해 몇 가지 장점이 있다. 암호화와 암호 해독이 더 빠르다.^[7] 오랫동안, McEliece는 서명을 만드는 데 사용될 수 없다고 생각되었다. 그러나 시그너처 체계는 맥엘리체 체계의 이중 변종인 니더레이터 체계에 기초하여 구성할 수 있다. McEliece의 주요 단점 중 하나는 개인 및 공용 키가 큰 매트릭스라는 것이다. 매개변수의 표준 선택 시 공개 키는 512 킬로비트 길이입니다.

구성표 정의

McEliece는 세 가지 알고리즘, 즉 공용 키와 개인 키를 생성하는 확률론적 키 생성 알고리즘, 확률론적 암호화 알고리즘, 그리고 결정론적 암호 해독 알고리즘으로 구성된다.

McEliece 배포의 모든 사용자는 공통 보안 매개 변수 집합($n{\displaystyle ,}$ ${\displaystyle k,}$ ${\displaystyle t}$ ${\displaystyle n,k,t})$을 공유한다$.$

키 생성

앨리스가 효율적인 디코딩 알고리즘을 알고 있는 일부 코드 제품군에서$$ 선형 $코드{\displaystyle }$ C$${\$displaystyle C}$를 $선택$하고, C$${\$displaystyle C}$을(를) 공개하지만 디코딩 알고리즘은 비밀로 유지하는 것이 원칙이다. 이러한 디코딩 알고리즘은 임의 발생기 매트릭스를 안다는 의미에서 $C{\displaystyle }$ ${\displaystyle C}$을(를$)$ 알고 있을 뿐만 아니라, 선택된 코드 $패밀리$에서 C$${\$displaystyle C}$을(를) 지정할 때 사용되는 파라미터를 알고 있어야 한다. 예를 들어, 이진 Goppa 코드의 경우, 이 정보는 Goppa 다항식 및 코드 로케이터가 될 것이다. 따라서 앨리스는 $C{\displaystyle }$ ${\displaystyle C}$의 적절한 난독화 발생기 행렬을 발행할 수 있다$.$

좀 더 구체적으로 말하면, 단계는 다음과 같다.

1. 앨리스는 일부 대규모 코드 제품군($예: 바이너리$ 고파 코드)에서 $t{\displaystyle }$ ${\displaystyle t}$ 오류를$$ 수정(효율적으로)할$$ 수 있는 바이너리$({\displaystyle n}$, ${\displaystyle k}$) ${\displaystyle C}$ -선형$$ 코드 $C{\displaystyle }$ ${\displaystyle C}$를 선택한다. 이 선택은 효율적인 디코딩 알고리즘 $A{\displaystyle }$ ${\displaystyle A}$을(를) 생성해야 한다$.$ 또한 $G{\displaystyle }$ ${\displaystyle G}$을 $C{\displaystyle }$ ${\displaystyle C}$의 생성기 매트릭스로 한다$$$.$ 모든 선형 코드는 제너레이터 매트릭스가 많지만, 이러한 코드 제품군에는 자연적인 선택이 있다. $이것$을 알면 $A$가$드러날$ 것이므로$$ 비밀로 해야 한다$.$
2. 앨리스는 무작위 $k{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle k}$ ${\displaystyle k\times k}$이(가) 2진수 비가수 행렬 $S{\displaystyle }$ ${\displaystyle S}$을(를) 선택한다$.$
3. 앨리스는 무작위 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle$ n$\times$ n$}$ 순열$$ 매트릭스 $P{\displaystyle }$ ${\displaystyle P}$를 선택한다$.$
4. 앨리스는 $k{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle k\times n}$ $행렬$ G${\displaystyle \stackrel{}{^}}$= S ${\displaystyle G}$ ${\displaystyle P}$ ${\displaystyle {\g}=$SGP$}$을$($를) 계산한다.
5. 앨리스의 ${\displaystyle \mathrm{공개}}$ 키는${\displaystyle }$(${\displaystyle G\hat{}}$ ,${\displaystyle }$t${\displaystyle }$) ${\displaystyle ({\hat$ {$G},$${\displaystyle t}$$)}$이고$,$ 개인 키는 $({\displaystyle S,}$ ${\displaystyle P,}$ A${\displaystyle )}$ ${\displaystyle (S,P,A)}$입니다$.$ $주의$할 점은 A ${\displaysty A}$을(를)를 $인코딩$하여 C ${\displaysty$ C$}$을 선택하는 데 사용되는 매개 변수로 저장할 수 있다는$$ 것이다$.$

메시지 암호화

밥이 공개 키가${\displaystyle }$( ${\displaystyle G\stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$, t${\displaystyle }$) ${\displaystyle({\hat {G},t$인 앨리스에게 다음과 같은 메시지 m을 보내려고 한다고 가정하자.

1. Bob은 메시지 $m{\displaystyle }$ ${\displaystyle m}$을(를) 길이 $k{\displaystyle }$ ${\displaystyle k}$의 이진 문자열로$$ 인코딩한다$.$
2. 밥은 벡터 $c{\displaystyle {}^{}}$ ${\displaystyle {\prime \mathrm{}}^{}}$= ${\displaystyle m}$ ${\displaystyle G\stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\$을$($를) 계산한다.
3. Bob은 정확히 $t{\displaystyle }$ ${\displaystyle t}$개$$(길이 $n{\displaystyle }$ ${\displaystyle n}$ 및$$ $중량{\displaystyle }$ t ${\displaystyle t}$의 벡터를 포함하는$$ $랜덤{\displaystyle }$ n ${\$$displaystyle z}$을(를) 생성한다$.$^[1]
4. ${\displaystyle 밥}$은 암호문을 $c{\displaystyle }$= ${\displaystyle {}^{}}$ = c ${\displaystyle {\prime \mathrm{}}^{}}$+ z ${\displaystyle c=c^{\prime }+z}$ 로 계산한다$.$

메시지 암호 해독

$c{\displaystyle }$ ${\displaystyle c}$을$($를) 받은 앨리스는 다음 단계를 수행하여 메시지를 해독한다.

1. 앨리스는 $P{\displaystyle }$ ${\displaystyle P}$의 역행($예{\displaystyle {}^{:}}$ ${\displaystyle {\mathrm{P}}^{}}$- 1 {\$displaystyle P^{-$1})$$을 계산한다.$$
2. 앨리스는 $c{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$= ${\displaystyle {\mathrm{c}}^{}}$ ${\displaystyle {}^{}}$- 1 ${\$를 계산한다$.$
3. 앨리스는 디코딩 알고리즘 $A{\displaystyle }$ ${\displaystyle A}$을(를) 사용하여$$ $c{\displaystyle \hat{}}$ ${\$에서 $m$^ ${\$까지 디코딩한다.
4. 앨리스는 $m{\displaystyle }$= ${\displaystyle m\stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\displaystyle S{}^{}}$- ${\displaystyle 1^{}}$ ${\$를 계산한다$.$

메시지 암호 해독 증명

Note that ${\displaystyle {\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}}$, and that ${\displaystyle P}$ is a permutation matrix, thus ${\displaystyle zP^{-1}}$ has weight ${\displaystyle t}$.

Gopa 코드 $G{\displaystyle }$ ${\displaystyle G}$은(는) $최대{\displaystyle }$ t ${\displaystyle t}$ 오류를$$ 수정할 수 있으며$$, m $S{\displaystyle }$ ${\displaystyle G}$ ${\displaystyle$ mSG$}$은(는) ${\displaystyle {\mathrm{P}}^{}}$- 1 ${\$에서 최대$$ $t{\displaystyle }$ ${\displaystystyt}$ 거리에 있다$$. 따라서 올바른 코드 $워드{\displaystyle \stackrel{}{}}$ m${\displaystyle \stackrel{}{}^}$ = ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle {\m}=mS}$을(를) 얻는다.

$S{\displaystyle }$ ${\displaystyle S}$의 역행과 곱하면 $m{\displaystyle }$ = ${\displaystyle m\stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\displaystyle S{}^{}}$- ${\displaystyle 1^{}}$= ${\displaystyle {\mathrm{m}}^{}}$ ${\displaystyle {}^{}}$- 1 ${\$ 즉 일반 문자 메시지가 된다$$${\displaystyle .}$

키 사이즈

McEliece는 원래 $n{\displaystyle }$= ${\displaystyle 1024,}$ k${\displaystyle }$= ${\displaystyle 524,}$ ${\displaystyle t}$ = ${\displaystyle 50}$ $displaystyle n=1024,k=524,t=50$^[1]의 보안 매개 변수 크기를 제안하여 공개 키 크기가 524*(1024-524) = 262,000비트를^{[clarification needed]} 나타냈다. Recent analysis suggests parameter sizes of ${\displaystyle n=2048,k=1751,t=27}$ for 80 bits of security when using standard algebraic decoding, or ${\displaystyle n=1632,k=1269,t=34}$ when using list decoding for the Goppa code, giving rise to public key sizes of 520,047 and 46각각 0,647비트.^[5] 양자 컴퓨터에 대한 복원력의 경우, goppa 코드가 $있는$ n${\displaystyle }$= ${\displaystyle 6960,}$ k${\displaystyle }$= ${\displaystyle 5413,}$ t${\displaystyle }$= ${\displaystyle 119}$ ${\displaystyle n=6960,k=5413,t=119}$의 크기가 제안되어 8,373,911비트의 공개 키 크기를 제공하였다.^[8] NIST 포스트 양자 표준화에 대한 그것의 3라운드 제출에서, 수준 5는 매개변수 세트 6688128, 6960119 및 8192128에 대해 주어진다. 매개변수는 $각각{\displaystyle }$$$ n${\displaystyle }$= ${\displaystyle 6688}$$,$ k${\displaystyle }$= ${\displaystyle \mathrm{128},}$ t${\displaystyle }$= ${\displaystyle 13}$ ${\$$displaystyle$ $n=668,k=128,t=13$ $n{\displaystyle }$= $,k=119,t=13,$ t$$= $13{\displaystyle }$$,$ n${\displaystyle }$= $k=128,t=13}$이다.

공격

공격은 공개 키$({\displaystyle G}$ ${\displaystyle \stackrel{}{^}}$, t$){\displaystyle({\hat{G},t)}$은 알고 있지만 개인 키는 모르는 적수로 구성되어 있으며, 일부 인터셉트된 암호 텍스트 $y{\displaystyle {}_{}^{}}$ F$$2n {\$displaysty$ y$\in\mathb {F} _{2$}^{n$}}}}}}$에서 일반 텍스트를 추론한다$.$ 그러한 시도는 실행될 수 없다.

맥엘리스를 위한 공격에는 크게 두 가지가 있다.

브루트 포스/구조화되지 않은 공격

공격자는${\displaystyle }$(${\displaystyle n}$, k${\displaystyle }$) {\$displaystyle$$(n,k)$ 코드$$ $C{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\$ {$G}$의 생성자 매트릭스인$$ $G{\displaystyle \hat{}}$ ${\displaystyle$ ${\c}$을(를) 알고 있으며, 이는$$ 조합적으로 $t{\displaystyle }$ ${\displaystyt}$ 오류를$$ 수정할 수 있다. 공격자는 $C{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\$이(가) 특정 패밀리에서 선택한 구조화된 코드의 난독화라는$$ 사실을 무시하고 대신 어떤 선형 코드로 해독하는 알고리즘을 사용할 수도 있다. 코드의 각 코드 워드, 증후군 디코딩 또는 정보 세트 디코딩과 같은 몇 가지 알고리즘이 존재한다.

그러나 일반 선형 코드의 디코딩은 NP-hard로 알려져 있으며,^[3] 위에서 언급한 모든 방법은 기하급수적인 실행시간을 가진다.

2008년 번스타인, 랜지, 피터스는^[5] 스턴에 의한 정보 집합 디코딩 방법을 사용하여 원래의 맥엘리스 암호 시스템에 대한 실제 공격을 기술했다.^[9] 맥엘리스가 당초 제시한 파라미터를 이용해 2비트^60.55 조작으로 공격을 진행할 수 있었다. 공격은 당황스러울 정도로 평행하기 때문에(노드 간 통신은 필요 없음) 적당한 컴퓨터 클러스터에서 수일 내에 수행될 수 있다.

구조적 공격

공격자는 대신 $C{\displaystyle }$ ${\displaystyle C}$의$$"구조"를 복구하여 효율적인 디코딩 $알고리즘{\displaystyle }$ A ${\displaystyle A}$ 또는$$ 다른 충분히 강력하고 효율적인 디코딩 알고리즘을 복구할 수 있다.

$C{\displaystyle }$ ${\displaystyle C}$을(를) 선택하는$$ 코드 패밀리는 공격자에게 이것이 가능한지 여부를 완전히 결정한다. 많은 코드 패밀리가 맥엘리체에게 제안되어 왔으며, 리드-솔로몬 코드처럼 효율적인 디코딩 알고리즘을 복구하는 공격이 발견되었다는 점에서 이들 대부분은 완전히 '파손'되었다.

원래 제안된 바이너리 고파 코드는 구조적 공격을 고안하려는 시도에 크게 저항해 온 몇 안 되는 제안 코드 패밀리 중 하나로 남아 있다.

수량 이후 암호화 후보

NTS-KEM과 결합한 이 알고리즘의 변형은 NIST 포스트 퀀텀 암호화 대회의 2차 라운드에서 입력되어 선택되었다.^[11]

참조

외부 링크

• Alfred J. Menezes; Scott A. Vanstone; A. J. Menezes; Paul C. van Oorschot (1996). "Chapter 8: Public-Key Encryption". Handbook of Applied Cryptography. CRC Press. ISBN 978-0-8493-8523-0.

• "Quantum Computers? Internet Security Code of the Future Cracked". Science Daily. Eindhoven University of Technology. 1 November 2008.

• "Classic McEliece". (NIST 포스트 퀀텀 암호 표준화 프로젝트 제출)