라빈 암호체계

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

1. 개요
2. 역사
3. 절차
4. 특징
5. 디지털 서명 알고리즘
- 5.1. 서명(Signing)
- 5.2. 서명 검증(Verifying a signature)
참조

1. 개요

라빈 암호체계는 1978년 마이클 O. 라빈에 의해 처음 발표된 트랩도어 함수를 기반으로 하는 공개 키 암호 시스템이다. 이 시스템은 소인수 분해 문제의 어려움에 기반하여 암호화와 디지털 서명에 사용되며, 키 생성, 암호화, 복호화의 세 가지 알고리즘으로 구성된다. 라빈 암호는 효율적인 암호화 속도를 가지지만, 복호화 과정에서 여러 개의 가능한 평문이 생성될 수 있으며, 선택 평문 공격 및 선택 암호문 공격에 취약하다는 특징이 있다. 또한, 전자 서명 알고리즘으로도 활용될 수 있으며, 서명 생성 및 검증 과정을 통해 메시지의 무결성을 보장한다.

더 읽어볼만한 페이지

암호학 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
암호학 - 암호화
암호화는 정보를 보호하기 위해 사용되는 기술로서, 단순한 문자 치환 방식에서 시작하여 현대에는 강력한 암호화 표준과 다양한 종류로 발전했으며, IT 시스템 전반에 적용되지만, 사이버 공격과 양자 컴퓨팅의 발전에 대한 대응이 필요한 기술이다.

라빈 암호체계
개요
종류	공개 키 암호 방식
기반	라빈 서명
세부 사항
보안	소인수 분해 문제의 어려움에 기반
취약점	선택적 평문 공격에 취약
비고	Rabin 암호체계는 소인수 분해가 어렵다는 가정에 기초한 공개 키 암호 방식이다.

2. 역사

마이클 O. 라빈은 1978년에 라빈 서명 방식의 일부로 라빈 트랩도어 함수를 처음 발표하였다.^[3]^[4]^[5] 라빈 서명 방식은 서명을 위조하는 것이 소인수 분해만큼 어렵다는 것을 증명할 수 있는 최초의 디지털 서명 방식이었다.

이 트랩도어 함수는 이후 교과서에서 공개 키 암호화 방식의 예로 재사용되었으며,^[6]^[7]^[1] 라빈이 암호화 방식으로 발표한 적은 없지만, 라빈 암호 시스템으로 알려지게 되었다.

3. 절차

라빈 암호체계는 키 생성, 암호화, 복호화의 세 단계로 이루어진다.

'''키 생성''': 공개 키와 개인 키를 생성한다. 공개 키는 모두에게 공개되고, 개인 키는 메시지 수신자만 알고 있다.
'''암호화''': 평문을 공개 키를 사용하여 암호문으로 변환한다.
'''복호화''': 암호문을 개인 키를 사용하여 원래의 평문으로 복원한다.

3. 1. 키 생성(Key generation)

앨리스는 매우 크며 서로 다른 두 소수 p와 q를 선택한다. 계산 편의를 위해 p ≡ q ≡ 3 (mod 4)를 만족하는 소수를 사용해도 좋다. (이러한 수를 블럼 수라고 한다.) n = pq를 계산하여 밥에게 공개한다. n은 공개 키, p와 q는 앨리스의 개인 키이다.^[1]

라빈 암호체계의 키 생성 과정은 다음과 같다.

단계	설명
1	서로 다른 두 개의 큰 소수 p와 q를 선택한다. 이때, p ≡ 3 (mod 4) 및 q ≡ 3 (mod 4)를 만족해야 한다.
2	n = pq를 계산한다.

여기서 n은 공개 키이고, (p, q) 쌍은 개인 키이다.^[2] p와 q를 블럼 수로 선택하면 복호화 처리가 간소화된다.^[3]

3. 2. 암호화(Encryption)

밥은 앨리스에게 보낼 평문 m을 선택한다. 이때 m은 1부터 n-1 사이의 값이다. 밥은 암호문

c = m^2 \pmod{n}

을 계산하여 앨리스에게 전송한다.^[1]

예시로,

p = 7

및

q = 11

을 사용하면

n=77

이 된다. 평문으로

m = 20

을 선택하면, 암호문은 다음과 같이 계산된다.

:

c = m^2 \bmod{n} = 400 \bmod{77} = 15

.

메시지 ''M''은 가역적인 매핑을 사용하여 숫자 ''m'' (

m < n

)으로 변환된 후,

c = m^2 \bmod{n}

을 계산하여 암호화할 수 있다. 이렇게 계산된 ''c''가 암호문이 된다.^[1]

평문을 ''x''라고 할 때, 암호화는 다음과 같이 수행될 수도 있다.

:

e(x) = x(x + B)\ \bmod \ n

3. 3. 복호화(Decryption)

앨리스는 암호문 ''c''와 개인 키 (''p'', ''q'')를 이용하여 평문 ''m''을 복원한다.

먼저, ''m_p'' = √''c'' (mod ''p''), ''m_q'' = √''c'' (mod ''q'')를 계산한다. 그리고 ''p'' * ''y_p'' + ''q'' * ''y_q'' = 1을 만족하는 ''y_p'', ''y_q''를 확장 유클리드 알고리즘을 이용해 찾는다.

중국인의 나머지 정리를 이용하여 다음 네 개의 근을 구한다.

''r''₁ = (''y_p'' * ''p'' * ''m_q'' + ''y_q'' * ''q'' * ''m_p'') mod ''n''
''r''₂ = ''n'' - ''r''₁
''r''₃ = (''y_p'' * ''p'' * ''m_q'' - ''y_q'' * ''q'' * ''m_p'') mod ''n''
''r''₄ = ''n'' - ''r''₃

이 네 개의 근 중 하나가 원래의 평문 ''m''이다.

만약

p \equiv q \equiv 3 \pmod{4}

이면, 아래 성질을 이용해 더 쉽게 풀 수 있다.

$m_p = c^((p+1)) \pmod{p}$
$m_q = c^((q+1)) \pmod{q}$
$(m_p)^2 \equiv c^((p+1)) \equiv c*c^((p-1))\equiv c*() \pmod{p}$ (는 르장드르 기호)
$c \equiv m^2 \pmod{pq} \Rightarrow c \equiv m^2 \pmod{p}$
$\therefore ()=1 \Rightarrow (m_p)^2 \equiv c \pmod{p}$

네 개의 값 중 어느 것이 올바른 평문인지 판별하기 위해, 평문에 중복성(redundancy)을 추가하거나 패딩 기법을 사용할 수 있다.^[1]

4. 특징

라빈 암호체계는 다음과 같은 특징을 가진다.

효율성: RSA에 비해 암호화 과정이 효율적이다. 라빈 암호는 제곱 연산만으로 암호화를 수행하지만, RSA는 세제곱 이상의 연산을 필요로 한다.^[1]
효과성: 암호화 함수가 4:1 함수이므로 복호화 과정에서 네 가지 서로 다른 결과가 나오며, 이 중 셋은 가짜 결과이다. 따라서 복호화 시 진짜 결과를 잘 추론해야 한다. 평문이 텍스트 메시지인 경우 추론이 어렵지 않지만, 숫자 값인 경우 모호성 제거 방식을 사용해야 한다.^[8] 이러한 단점을 보완하기 위해 암호문과 평문이 1:1 대응이 되도록 하는 알고리즘이 사용되기도 한다.
보안성: 소인수 분해 문제와 동치이므로, 소인수분해 일반 공식이 나오거나 동치성이 증명되기 전까지는 상당히 안전하다고 볼 수 있다. 그러나 선택 암호문 공격에 취약하며, 선택 평문 공격에 대해 구별 불가능성을 제공하지 않는다.^[1]

4. 1. 효율성(Efficiency)

암호화 과정은 RSA에 비해 효율적이다. 라빈 암호는 제곱 연산만으로 암호화를 수행하는 반면, RSA는 세제곱 이상의 연산을 필요로 한다.^[1] 복호화 과정의 효율성은 RSA와 비슷하다. 두 번의 모듈러 지수 연산과 중국인의 나머지 정리를 사용한다.^[1]

4. 2. 효과성(Effectiveness)

암호화 함수가 4:1 함수이므로, 복호화 과정에서 네 가지 서로 다른 결과가 나오고 이 중 셋은 가짜 결과이기 때문에, 복호화 과정에서 진짜 결과를 잘 추론해야 한다. 특히 숫자 값을 암호화한 경우 모호성 제거 스킴(disambiguation scheme)을 사용해야 한다.^[8] 이 단점을 개량해서 [암호문 1: 평문 1]을 유지하는 알고리즘이 쓰인다.

복호화는 올바른 결과 외에 세 개의 잘못된 결과를 생성하므로 올바른 결과를 추측해야 한다. 이는 라빈 암호체계의 주요 단점이며, 널리 실용화되지 못한 요인 중 하나이다.^[8]

평문이 텍스트 메시지를 나타내도록 의도된 경우 추측은 어렵지 않다. 그러나 평문이 숫자 값을 나타내도록 의도된 경우 이 문제는 일종의 모호성 제거 방식을 통해 해결해야 할 문제가 된다. 이 문제를 제거하기 위해 특수한 구조의 평문을 선택하거나 패딩을 추가할 수 있다. 역전의 모호성을 제거하는 방법은 Blum과 Williams에 의해 제안되었다. 사용되는 두 소수는 4 모듈로 3과 합동인 소수로 제한되고, 제곱의 영역은 이차 잔여 집합으로 제한된다. 이러한 제한은 제곱 함수를 트랩도어 순열로 만들어 모호성을 제거한다.^[8]

4. 3. 보안성(Security)

라빈 암호 알고리즘은 소인수 분해 문제와 동치이다. (이는 RSA 암호에서는 증명되지 않았다.) 따라서 소인수분해 일반 공식이 나오거나 동치성이 증명되기 전까지는 상당히 안전하다고 볼 수 있다.

하지만 라빈 암호 시스템은 선택 암호문 공격(chosen ciphertext attack)에 취약하다.^[1] 암호화 과정이 결정적이므로, 공격자는 암호문과 후보 메시지가 주어지면 후보 메시지를 암호화하여 주어진 암호문이 생성되는지를 쉽게 확인할 수 있다. 즉, 구별 불가능성을 선택 평문 공격에 대해 제공하지 않는다.

또한, 제작 시 quadratic residue modulo n을 사용하므로, 이와 관련된 공격이 가능하다.^[1]

라빈 암호 시스템은 선택 암호문 공격에 취약하며, 예를 들어 중복성을 추가하여 단일 근을 생성하는 방식으로 공격을 방해할 수 있지만, 이 경우 소인수 분해 문제와의 동등성 증명이 실패하여 안전성이 불확실해진다.^[1]

라빈 암호의 해독 문제는 소인수 분해 문제로 귀착시킬 수 있다. 어떤 평문 ''x1''에 대응하는 암호문 ''y1''이 주어졌을 때, 특정 방정식을 만족하는 ''x''를 구할 수 있다면, 높은 확률로 ''x1''과는 다른 값 ''x2''를 얻을 수 있고, 이를 통해 높은 확률로 소인수 p 또는 q를 구할 수 있다.^[1]

5. 디지털 서명 알고리즘

라빈 암호 체계는 전자 서명을 생성하고 검증하는 데 사용될 수 있다. 서명 생성에는 개인 키 $(p,q)$ 가, 서명 검증에는 공개 키 $n$ 이 필요하다.

5. 1. 서명(Signing)

메시지

m

은 개인 키

(p,q)

를 사용하여 다음과 같이 서명할 수 있다.

1. 임의의 값

u

를 생성한다.

2. 암호화 해시 함수

H

를 사용하여

c = H(m\mathbin\Vert u)

를 계산한다. 여기서 이중 막대 기호는 연결을 나타낸다.

c

는

n

보다 작은 정수여야 한다.

3. 개인 키

(p,q)

를 사용하여

c

의 제곱근을 찾는다. 그러면 일반적인 네 가지 결과

r_1, r_2, r_3, r_4

가 생성된다.

4. 각

r_i

를 제곱하면

c

가 생성될 것으로 예상할 수 있다. 그러나 이는

c

가

p

와

q

를 법으로 한 이차 잉여인 경우에만 참이다. 이 경우인지 확인하려면

r_1

을 제곱한다. 이렇게 해서

c

가 생성되지 않으면, 새로운 임의의

u

로 이 알고리즘을 반복한다. 적절한

c

를 찾기 전에 이 알고리즘을 반복해야 하는 예상 횟수는 4이다.

5.

c

의 제곱근

r_1

을 찾았으면, 서명은

(r_1,u)

이다.

5. 2. 서명 검증(Verifying a signature)

공개 키 ''n''을 사용하여 메시지 ''m''에 대한 서명 (''r'', ''u'')를 검증하는 방법은 다음과 같다.

1. ''c'' = H(''m'' || ''u'')를 계산한다.

2. ''r''′ = ''c''² mod ''n''을 계산한다.

3. ''r''′ ≡ ''r'' 이면 서명이 유효하고, 그렇지 않으면 위조된 것이다.

참조

_[1] 서적 Mathematics of Public Key Cryptography Cambridge University Press
_[2] 서적 Lecture Notes on Cryptography https://cseweb.ucsd.[...] 2008-07
_[3] 서적 Foundations of Secure Computation Academic Press
_[4] 간행물 Digitalized Signatures and Public Key Functions as Intractable as Factorization http://publications.[...] 1979-01
_[5] 학술회의 The Exact Security of Digital Signatures—How to Sign with RSA and Rabin Springer 1996-05
_[6] 서적 Cryptography: Theory and Practice Chapman & Hall/CRC 2006
_[7] 서적 Handbook of Applied Cryptography https://cacr.uwaterl[...] CRC Press 1996-10
_[8] 서적 Lecture Notes on Cryptography https://cseweb.ucsd.[...] 2008-07

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

문의하기 : help@durumis.com