매켈리스 암호체계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
3. 키 크기
4. 공격 방법
- 4.1. 구조적 공격
- 4.2. 비구조적 공격 (총망라 공격)
5. 양자 내성 암호 후보
참조

1. 개요

매켈리스 암호체계는 확률적 알고리즘을 기반으로 하는 공개 키 암호 시스템이다. 이 암호는 키 생성, 암호화, 복호화의 세 가지 알고리즘으로 구성된다. 키 생성 시에는 효율적인 복호화 알고리즘이 알려진 선형 코드를 선택하고, 암호화 과정에서는 메시지를 공개 키를 사용하여 암호문으로 변환하며, 복호화는 개인 키를 사용하여 암호문을 원래 메시지로 되돌린다. 매켈리스 암호는 양자 컴퓨터의 공격에도 안전한 것으로 평가되어 NIST의 양자 내성 암호화 경쟁에 후보로 제출되었다.

더 읽어볼만한 페이지

양자 후 암호 - 쇼어 알고리즘
쇼어 알고리즘은 소인수분해 및 이산 로그 문제를 해결하는 양자 알고리즘으로, 양자 위상 추정 알고리즘과 연분수 알고리즘을 활용하며, 공개 키 암호화 방식을 깨뜨릴 수 있다.
양자 후 암호 - IEEE P1363
IEEE P1363은 격자 기반, 비밀번호 기반, ID 기반 방식을 포함한 다양한 공개 키 암호화 알고리즘 표준을 정의하며, 키 합의, 서명, 암호화 방식을 제시하여 보안 시스템 설계 및 구현에 널리 사용된다.
암호 알고리즘 - 이진 코드
이진 코드는 0과 1을 사용하여 정보를 표현하는 시스템으로, 고대 중국의 주역에서 기원하며, 컴퓨터 과학, 통신 등 다양한 분야에서 활용된다.
암호 알고리즘 - 메시지 인증 코드
메시지 인증 코드(MAC)는 메시지 무결성을 보장하기 위해 사용되는 암호화 기법으로, 송신자와 수신자가 동일한 키를 공유하여 MAC 생성, 확인 과정을 거친다.

매켈리스 암호체계
개요
종류	공개 키 암호 방식
고안자	로버트 맥엘리스
발표	1978년
기반	오류 수정 부호
보안 근거	무작위 선형 부호의 해독은 NP-완전 문제임
양자 컴퓨터 공격에 대한 저항성	있음 (양자 내성 암호)
대체 암호	니더라이터 암호 방식
상세 정보
특징	암호화 및 복호화 속도가 빠르지만, 키 크기가 매우 큼
장점	양자 컴퓨터 공격에 안전함 암호화 속도가 빠름
단점	큰 키 크기 구조적 암호 방식으로 변환하기 어려움
안전성
최적화된 공격	정보 집합 디코딩
구현체
라이브러리	PQClean Open Quantum Safe (OQS)

2. 알고리즘

매켈리스 암호체계는 세 가지 알고리즘으로 구성된다. 공개 키와 개인 키를 생성하는 확률론적 알고리즘인 키 생성 알고리즘, 확률적 암호화를 수행하는 암호화 알고리즘, 그리고 결정론적 알고리즘인 복호화 알고리즘이다.

매켈리스 암호체계를 사용하는 모든 사용자는 공통 보안 매개변수 $n, k, t$ 를 공유하며, 일반적으로 $n=1024, t=38, k=644$ 정도의 값이 안전하다고 권장된다.

2. 1. 키 생성

매켈리스 암호체계의 키 생성 알고리즘은 확률론적 알고리즘이다. 키 생성에는 보안 매개변수

n, t, k

가 사용되며, 일반적으로

n=1024, t=38, k=644

정도의 값이 안전하다고 권장된다.

키 생성의 기본 원리는 효율적인 복호화 알고리즘

A

가 알려진 선형 부호

C

를 선택하는 것에서 시작한다. 이 코드

C

자체는 공개될 수 있지만, 그것의 효율적인 복호화 알고리즘

A

는 비밀로 유지되어야 한다. 복호화 알고리즘

A

를 사용하기 위해서는 단순히

C

의 생성 행렬

G

를 아는 것만으로는 부족하며,

C

를 특정 코드 집합(예: 이진 고파 부호)에서 선택할 때 사용된 특정 매개변수(예: 고파 다항식, 코드 로케이터)를 알아야 한다. 따라서 키 생성자는 원래의 생성 행렬

G

를 난독화하여 만든 새로운 행렬

{\hat G}

를 공개한다.

구체적인 키 생성 단계는 다음과 같다.

# 오류

t

개를 효율적으로 수정할 수 있는

(n, k)

-선형 부호

C

를 (예: 이진 고파 부호와 같이 큰 코드 집합에서) 선택한다. 이 선택 과정에서 효율적인 복호화 알고리즘

A

와

C

의 생성 행렬

G

가 결정된다.

G

와

A

는 비밀로 유지한다.

# 임의의

k \times k

이진 가역 행렬

S

를 선택한다.

# 임의의

n \times n

치환 행렬

P

를 선택한다.

#

k \times n

행렬

{\hat G} = SGP

를 계산한다.

# 공개 키는

({\hat G}, t)

이고, 개인 키는

(S, P, A)

이다. 개인 키의

A

부분은

C

를 선택할 때 사용된 매개변수 형태로 저장될 수 있다.

2. 2. 암호화

밥이 메시지

m

을 앨리스에게 보내고 싶어한다고 하자. 앨리스의 공개키, 즉 암호화를 위한 키가

({\hat G},t)

라면, 밥은 다음과 같이

m

을 암호화한다.

# 밥은 메시지

m

을 길이

k

의 비트열로 표현한다.

# 밥은 벡터

c^{\prime} = m{\hat G}

를 계산한다.

# 밥은

n

비트 벡터이며, 정확히

t

개의 요소가 1(나머지는 0)인 벡터

z

를 무작위로 생성한다. (즉, 벡터

z

의 길이는

n

이고 가중치는

t

이다.)^[14]

# 밥은 암호문으로

c = c^{\prime} + z

를 계산한다.

2. 3. 복호화

복호화 알고리즘은 결정론적 알고리즘이다. 암호문

c

를 수신한 경우, 앨리스는 다음과 같이 복호화하여 원본 메시지를 얻는다.

# 앨리스는

P

의 역행렬

P^{-1}

을 계산한다.

# 앨리스는

{\hat c} = cP^{-1}

를 계산한다.

# 앨리스는 복호화 알고리즘

A

를 사용하여

{\hat c}

를 복호화하고, 복호화 결과

{\hat m}

을 얻는다.

# 앨리스는

m = {\hat m}S^{-1}

를 계산한다.

m

이 원본 메시지이다.

2. 4. 복호화의 정당성

암호화 및 복호화 절차에 따라,

{\hat c} = cP^{-1} = m{\hat G}P^{-1} + zP^{-1} = mSG + zP^{-1}

가 성립한다. 여기서

P

는 순열 행렬이므로

zP^{-1}

는 가중치가

t

인 벡터이다.

고파 부호 '''

G

'''는 최대

t

개의 오류를 정정할 수 있으며, 벡터

mSG

와

cP^{-1}

사이의 거리는 최대

t

이다. 따라서, 복호화 알고리즘을 통해 올바른 부호어

{\hat m} = mS

를 얻을 수 있다.

마지막으로 '''

S

'''의 역행렬을 곱하면

m = {\hat m}S^{-1}= mSS^{-1}

가 되어 원본 평문 메시지를 복구할 수 있다.

3. 키 크기

행렬 $S$ 에서 자유로운 선택이 가능하기 때문에, 마지막 $k$ 열이 항등 행렬 ${\hat G} = ({\tilde G}|I)$ 에 해당하는 "체계적 형식"으로 ${\hat G}$ 를 표현하는 것이 일반적이다. 이렇게 하면 공개 키 크기가 $(n-k) \times k$ 비트로 줄어든다.^[8]^[9]

매켈리스는 원래 $n=1024, k=524, t=50$ 의 보안 매개변수 크기를 제안했으며,^[1] 결과적으로 공개 키 크기는 524 × (1024 − 524) = 262,000 비트가 된다.^[14]

최근 분석에 따르면 표준 대수적 복호를 사용할 때 80 비트 보안을 위해 $n=2048, k=1751, t=27$ 의 매개변수 크기 (공개 키 크기 520,047 비트), 또는 고파 부호를 위한 리스트 복호를 사용할 때 $n=1632, k=1269, t=34$ 의 매개변수 크기 (공개 키 크기 460,647 비트)가 제안되었다.^[5]^[18]

양자 컴퓨터에 대한 내성을 갖추기 위해, 고파 부호를 사용하여 $n=6960, k=5413, t=119$ 의 크기가 제안되었으며, 이때 공개 키 크기는 8,373,911 비트이다.^[10]^[21] NIST의 양자 내성 암호 표준화 공모(Post-Quantum Cryptography standardization) 3라운드에서는 최고 보안 수준(Level 5)을 위해 다음 매개변수 집합들이 제출되었다: $n=6688, k=128, t= 13$ , $n= 6960, k = 119, t = 13$ , $n=8192, k =128, t = 13$ .

4. 공격 방법

공격은 공개 키 $({\hat G}, t)$ 는 알지만 개인 키는 모르는 적대자가 가로챈 암호문 $y \in \mathbb{F}_2^n$ 으로부터 평문을 추론하는 것으로 구성된다. 이러한 시도는 실행 불가능해야 한다.

매켈리스 암호 체계에 대한 공격은 크게 두 가지로 나뉜다.

4. 1. 구조적 공격

구조적 공격은 암호문 생성에 사용된 부호

C

의 구조를 복원하여, 이를 통해 원래의 효율적인 복호 알고리즘

A

나 다른 효과적인 복호화 방법을 찾아내려는 시도를 말한다.

이러한 공격의 성공 가능성은

C

를 어떤 부호족(code family)에서 선택했는지에 따라 크게 달라진다. 매켈리스 암호체계를 위해 여러 부호족이 제안되었지만, 리드-솔로몬 부호와 같이 상당수는 효율적인 복호 알고리즘을 찾아내는 공격 방법이 발견되어 더 이상 안전하지 않은 것으로 여겨진다.

반면, 매켈리스가 처음 제안했던 이진 고파 부호(binary Goppa code)는 이러한 구조적 공격 시도에 대해 현재까지 안전성을 유지하고 있는 대표적인 부호족 중 하나이다.

4. 2. 비구조적 공격 (총망라 공격)

공격자는 공개된 생성 행렬

\hat G

를 알고 있으며, 이 행렬이

t

개의 오류를 수정할 수 있는

(n,k)

코드

\hat C

를 생성한다는 것을 안다. 공격자는

\hat C

가 특정 구조를 가진 코드를 난독화한 것이라는 사실을 무시하고, 임의의 선형 코드를 해독하는 알고리즘을 사용한다. 이것이 비구조적 공격 또는 총망라 공격에 해당한다.

이러한 공격에 사용될 수 있는 알고리즘으로는 코드의 모든 코드 단어를 확인하는 방법, 증후군 해독, 정보 집합 해독 등이 있다. 그러나 일반적인 선형 코드를 해독하는 것은 NP-난해 문제로 알려져 있으며,^[3]^[16] 앞서 언급된 모든 방법은 지수적인 실행 시간을 필요로 한다.

2008년, 다니엘 번스타인, 랑에(Lange), 페터스(Peters)는 스턴(Stern)의 정보 집합 해독 방법을 이용하여^[11]^[22] 원래의 매켈리스 암호체계에 대한 실제적인 공격 방법을 발표했다.^[5]^[18] 매켈리스가 처음 제안했던 매개변수를 사용했을 때, 이 공격은 2^60.55 비트 연산만으로 수행될 수 있었다. 이 공격은 완전히 병렬화할 수 있으므로(각 계산 노드 간 통신 불필요), 적당한 규모의 컴퓨터 클러스터를 사용하면 며칠 안에 완료될 수 있다.

5. 양자 내성 암호 후보

매켈리스 암호체계의 변형 알고리즘은 NTS-KEM^[12]과 결합되어 NIST의 양자 내성 암호 표준화 공모 3차 라운드 후보로 선정되었다.^[13]

참조

_[1] 간행물 A Public-Key Cryptosystem Based on Algebraic Coding Theory https://ipnpr.jpl.na[...]
_[2] 간행물 McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks Springer
_[3] 간행물 On the Inherent Intractability of Certain Coding Problems https://authors.libr[...]
_[4] 간행물 The algebraic decoding of Goppa codes
_[5] 서적 Post-Quantum Cryptography https://eprint.iacr.[...] 2008-08-08
_[6] 간행물 Grover vs. McEliece https://cr.yp.to/cod[...] Springer
_[7] 웹사이트 eBATS: ECRYPT Benchmarking of Asymmetric Systems https://bench.cr.yp.[...] 2018-08-25
_[8] 웹사이트 Classic McEliece: conservative code-based cryptography: cryptosystem specification https://classic.mcel[...] 2022-10-23
_[9] Youtube Code-based cryptography III - Goppa codes: definition and usage https://www.youtube.[...] 2021-02-23
_[10] 웹사이트 Initial recommendations of long-term secure post-quantum systems https://pqcrypto.eu.[...] 2015-09-07
_[11] 서적 Coding Theory and Applications Springer Verlag
_[12] 웹사이트 NTS-KEM https://nts-kem.io/ 2017-12-29
_[13] 간행물 Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process https://nvlpubs.nist[...]
_[14] 간행물 A Public-Key Cryptosystem Based On Algebraic Coding Theory https://ipnpr.jpl.na[...]
_[15] 간행물 McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks Springer
_[16] 간행물 On the Inherent Intractability of Certain Coding Problems
_[17] 간행물 The algebraic decoding of Goppa codes
_[18] 서적 Attacking and defending the McEliece cryptosystem https://eprint.iacr.[...] 2008-08-08
_[19] 간행물 Grover vs. McEliece https://cr.yp.to/cod[...] Springer
_[20] 웹사이트 eBATS: ECRYPT Benchmarking of Asymmetric Systems https://bench.cr.yp.[...] 2018-08-25
_[21] 웹사이트 Initial recommendations of long-term secure post-quantum systems https://pqcrypto.eu.[...] 2015-09-07
_[22] 서적 A method for finding codewords of small weight Springer Verlag

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com