Rabin Signature

Intro

Rabin 서명(Rabin Signature)은 1979년에 Michael O. Rabin이 제안한 Rabin 암호(Rabin cryptosystem)를 서명 목적으로 응용한 알고리즘입니다. 이 서명 방식은 비대칭키 암호학(공개키 암호학)에서 사용되며, RSA 서명 알고리즘과 유사하면서도 수학적으로는 다른 구조적 특징을 보입니다.

Rabin 암호는 의사 난수 생성, 메시지 암호화, 서명 알고리즘 등 다양한 분야에서 연구되어 왔습니다. Rabin의 원 논문에서는 “Rabin 알고리즘은 RSA와 마찬가지로 큰 소수들의 곱을 모듈러로 사용하는 단방향 함수를 기반으로 하되, 그 안전성에 대한 증명이 조금 더 ‘간단하면서도 강력한’ 성질을 보인다”고 주장합니다. 실제로 Rabin 서명은 오직 Integer Factorization Problem에 기반하여 안전성이 귀결된다는 점에서 이론적으로 튼튼한 근거를 가지고 있습니다.

아래에서는 Rabin 서명이 무엇인지, 어떤 원리로 동작하는지, 그리고 구현상의 세부 사항 및 주의점, 다른 서명 알고리즘과 비교했을 때의 장단점 등을 단계별로 살펴봅니다.

History

Rabin 암호의 기원

• 1978년 Rivest, Shamir, Adleman이 RSA 공개키 암호를 제안한 이후, 수학적으로 큰 수의 인수분해가 어려운 점을 기반으로 한 다양한 암호 알고리즘들이 등장하였습니다.
• 1979년 Michael O. Rabin은 RSA와 비슷하게 소인수분해 문제에 근거한 알고리즘을 제안합니다. Rabin 암호는 메시지 mmm에 대해 m2mod  nm^2 \mod nm2modn으로 암호화하는 구조를 갖습니다.
• Rabin 암호의 독특한 점은 복호화 시 하나의 암호문에 대해 최대 4개의 가능한 평문 후보가 나오기 때문에, 이를 처리하는 메커니즘이 필요합니다.

서명 알고리즘으로의 발전

• Rabin 암호가 알려진 뒤, ‘Rabin 서명(Rabin Signature)’ 알고리즘이 자연스럽게 관심을 끌었습니다. 한편, RSA 서명에 비해 Rabin 서명이 덜 보급된 이유 중 하나는 구현의 복잡성, 그리고 서명값이 단순 제곱(혹은 변형)에 기반하여 여러 후보가 나오기 때문에 생기는 특수한 문제들과 같은 실용적인 이유가 꼽힙니다.
• 그럼에도 Rabin 서명의 안전성은 오직 정수 인수분해 난이도에만 의존하기 때문에, 이론적 관심은 꾸준히 이어지고 있습니다.

수학적 배경

인수분해 문제

• Rabin 서명을 포함한 많은 공개키 암호는 큰 수의 인수분해가 어려움을 근간으로 합니다.
• 일반적으로 소수 ppp와 qqq를 이용하여 n=p×qn = p \times qn=p×q로 구성하면, nnn의 인수분해는 수백~수천 비트 수준의 p,qp, qp,q를 사용했을 때 매우 어렵다고 알려져 있습니다.
• Rabin 서명에서는 이 nnn을 공개키로, p,qp, qp,q를 비밀키로 사용합니다.

모듈러 제곱

• Rabin 서명의 기본 연산은 제곱 연산입니다. 단순화하면, 서명 생성 시 메시지나 해시 값 등을 특정 함수로 변환한 후, 그 결과에 대한 ‘루트’를 찾는 과정이 포함됩니다.
• 수학적으로 x2≡y(modn)x^2 \equiv y \pmod{n}x2≡y(modn)를 만족하는 xxx를 찾는 문제(즉 “제곱근” 문제)는 nnn이 소인수분해되지 않은 상태에서 어렵습니다. 그러나 nnn을 인수분해할 수 있다면(즉 비밀키를 가진 자라면) 이 문제는 쉽게 해결될 수 있습니다.

메시지 해싱과 패딩

• Rabin 서명에서도 메시지를 바로 서명하는 것이 아니라, 일반적으로 암호학적 해시 함수(예: SHA-256, SHA-3 등)를 이용하여 메시지를 짧은 해시값으로 만든 다음, 그 해시값(혹은 패딩된 해시값)에 대해 서명을 취합니다.
• 해시 함수는 원본 메시지를 임의의 길이에서 고정된 길이로 압축해 주며, 일반적으로 역상 저항성을 가집니다.
• Rabin 서명에서는 메시지 해시를 H(m)H(m)H(m)라 하고, 서명 연산 시 이 해시에 특정 패딩 방식을 적용한 뒤 제곱근을 찾는 과정을 거칩니다.

Rabin 서명의 동작 방식

Rabin 서명은 핵심적으로 아래와 같은 과정을 거칩니다. 이때, 메시지를 단순화하여 설명하며, 실제 구현에서는 해시 함수와 추가 패딩(혹은 파라미터)을 적용합니다.

Key Generation

1. 두 소수 p,qp, qp,q 선택

   • 큰 소수 p,qp, qp,q (예: 각 1024비트씩, 총 2048비트 모듈러 등)를 무작위로 선택합니다.
   • p,qp, qp,q는 서로 다른 소수여야 하며, 보통 p≡q≡3(mod4)p \equiv q \equiv 3 \pmod{4}p≡q≡3(mod4)와 같은 형태로 선택하는 게 일반적입니다.
     • 이는 서명 및 복호화(루트 찾기) 과정에서 2개의 해만 생성되도록 관리하기 위함입니다.
     • 사실상 p≡q≡3(mod4)p \equiv q \equiv 3 \pmod{4}p≡q≡3(mod4)이면, 복원 시 한 후보(예: 양수 루트)만을 선택하는 명확한 규칙이 가능하게 됩니다.

2. n=p×qn = p \times qn=p×q 계산

   • 공개키: nnn
   • 개인키(비밀키): p,qp, qp,q

3. 추가 파라미터 설정(옵션)

   • Rabin 서명은 복호 과정(제곱근 구하기)에서 4가지 후보가 나올 수 있습니다. 이를 명확히 하나로 결정하기 위한 추가 정보(예: salt, 선택 비트, 인코딩 규칙) 등이 필요한 경우가 있습니다.
   • 일반적으로 블룸-골드워서(BGW) 패딩이나 다른 메시지 임베딩 방식을 이용하여, 서명 값에 대해 충돌이 일어나지 않도록 합니다.

Signing

1. 메시지 해시 H(m)H(m)H(m) 계산

   • 원본 메시지 mmm에 대하여, 암호학적 해시 함수 HHH를 적용해 h=H(m)h = H(m)h=H(m)을 구합니다.
   • 필요하다면 hhh에 다시 패딩 등 추가 데이터를 포함해 h~\tilde{h}h~와 같은 확장 버전을 형성하기도 합니다.

2. 서명 목적의 “제곱근” 계산

   • Rabin 서명에서 서명값 sss는 h≡s2(modn)\tilde{h} \equiv s^2 \pmod{n}h≡s2(modn)을 만족하도록 하는 sss를 찾는 과정에 의해 결정됩니다.
   • 하지만, 모듈로 nnn의 제곱근은 p, q의 소인수를 아는 사람만이 쉽게 계산할 수 있습니다.
   • 구체적으로,
     • hp=hmod  p\tilde{h}_p = \tilde{h} \mod php​=hmodp
     • hq=hmod  q\tilde{h}_q = \tilde{h} \mod qhq​=hmodq
     • 각각의 소수에 대해 sp2≡hp(modp)s_p^2 \equiv \tilde{h}_p \pmod{p}sp2​≡hp​(modp), sq2≡hq(modq)s_q^2 \equiv \tilde{h}_q \pmod{q}sq2​≡hq​(modq)를 만족하는 해 sp,sqs_p, s_qsp​,sq​를 찾고,
     • 중국인의 나머지 정리(CRT, Chinese Remainder Theorem)를 사용하여 sps_psp​와 sqs_qsq​를 nnn에서의 고유 솔루션 sss로 결합합니다.
   • 만약 p,q≡3(mod4)p, q \equiv 3 \pmod{4}p,q≡3(mod4) 형태로 선택되었다면, hp\tilde{h}_php​가 주어졌을 때 sp≡hpp+14mod  p s_p \equiv \tilde{h}_p^{\frac{p+1}{4}} \mod psp​≡hp4p+1​​modp 방식으로 쉽게 제곱근을 구할 수 있습니다.

3. 유일한 서명값(혹은 대표값) 결정

   • 이론적으로 CRT 적용 시 4개의 후보 ±sp,±sq\pm s_p, \pm s_q±sp​,±sq​ 조합이 나타날 수 있으나, 그중 하나를 선택하는 규칙(예: 가장 작은 양의 정수)을 통해 서명값을 단일하게 결정합니다.

4. 서명 결과 출력

   • 최종 서명값 sss를 송신측(서명자)이 메시지와 함께 전송합니다.

Verification

1. 메시지 해시 H(m)H(m)H(m) 재계산

   • 검증자는 메시지를 받아 동일한 해시 함수 HHH를 적용하여 h=H(m)h = H(m)h=H(m)을 얻습니다.
   • 패딩이 적용된 경우, 메시지에 포함된 패딩 정보를 복원하거나 별도의 방식을 통해 h~\tilde{h}h~를 재구성합니다.

2. 서명값을 이용해 제곱 연산 수행

   • 검증자는 서명값 sss에 대해 s2mod  ns^2 \mod ns2modn을 계산하여, 그 결과가 h~\tilde{h}h~와 일치하는지 확인합니다.
   • 만약 h≡s2(modn)\tilde{h} \equiv s^2 \pmod{n}h≡s2(modn)이 성립한다면, 서명은 유효합니다.
   • 성립하지 않는다면 위조이거나 변조된 것으로 판정됩니다.

Rabin 서명의 장점과 단점

장점

1. 단일한 수학적 가정(인수분해 문제)에만 의존

   • RSA와 달리 “eee” 혹은 “ddd” 등의 추가 지수 가정이 필요 없습니다.
   • Rabin 서명의 안전성은 오직 정수 인수분해 문제의 난이도에 근거합니다. 이론적으로 깔끔한 안전성 근거를 가짐.

2. 상대적으로 단순한 구조

   • 실제 구현은 메시지를 변환(해시+패딩)한 뒤 모듈러 제곱근 연산을 수행하는 방식으로, RSA 서명과 큰 틀에서 다르지 않습니다.
   • 서명 검증도 제곱 연산 한 번이면 충분하므로, 계산 비용은 비교적 적을 수 있습니다(지수 연산 대신 제곱 연산).

3. 서명 검증이 매우 간단

   • ‘서명값을 제곱 → 모듈러 연산 → 해시와 비교’로 끝나므로, 검증 측면에서 연산이 경량화될 수 있습니다.

단점

1. 4가지 해(±값) 문제

   • 모듈로 nnn에서의 제곱근은 최대 4가지가 존재합니다.
   • 이를 처리하기 위해 CRT와 ‘대표값’을 정하는 규칙이 필요합니다. 실제 구현 시 복잡성을 증가시키는 원인이 됩니다.

2. 패딩/임베딩 방식의 복잡성

   • Rabin 서명을 안전하게 적용하기 위해서는 적절한 패딩 스킴이 필요합니다.
   • 예를 들어 블룸-골드워서(Bloom–Goldwasser) 패딩, 혹은 ISO/IEC 표준에 명시된 별도의 패딩 알고리즘 등을 적용해야 합니다.
   • 올바르지 않은 패딩은 메시지-서명 쌍에 대한 공격 벡터를 만들 수도 있습니다.

3. 널리 쓰이지 않음

   • RSA, ECDSA, EdDSA 등에 비해 산업 표준으로 채택된 사례가 적습니다.
   • 따라서 실제 구현 라이브러리나 문서화, 최적화 코드, 하드웨어 가속 지원 등이 부족한 편입니다.

4. 키 길이와 안전성

   • Rabin 서명도 RSA처럼 큰 모듈러 nnn을 사용해야 안전합니다.
   • 대략 RSA와 유사하게 2048비트 이상(현대 보안 기준)은 권장되며, 3072, 4096 등 더 큰 키 길이가 요구될 수도 있습니다.

Rabin Signature vs. RSA

Rabin 서명과 RSA 서명은 모두 소인수분해 문제를 기반으로 하지만, 수학적 처리 과정에서 약간의 차이가 있습니다.

1. 수학적 원리

   • RSA: s≡hd(modn)s \equiv h^d \pmod{n}s≡hd(modn) (여기서 ddd는 개인키)
   • Rabin: s2≡h(modn)s^2 \equiv h \pmod{n}s2≡h(modn) (소인수분해를 통해 제곱근을 구함)

2. 복잡도

   • 서명 연산에서 RSA는 거듭제곱(지수 연산), Rabin은 제곱근을 찾아야 합니다.
   • 대체로 RSA는 모듈러 거듭제곱을, Rabin은 CRT 기반의 두 소수에 대한 루트 합성 과정을 수행하므로, 어느 쪽이 더 효율적인지는 구현에 따라 달라질 수 있습니다.

3. 안전성 근거

   • RSA는 일반적으로 “RSA 문제”(ce≡mmod  nc^e \equiv m \mod nce≡mmodn에서 mmm을 찾기 어렵다는 것)에 근거하지만, 최종적으로는 정수 인수분해, e-th root 문제 등 복합적인 수학적 문제에 의존합니다.
   • Rabin은 조금 더 직접적으로 정수 인수분해 문제에 귀결되므로, 안전성 증명이 간결하다고 평가됩니다.

4. 표준/채택도

   • RSA는 수많은 국제 표준, 산업 표준에 채택되어 폭넓게 쓰이며, 하드웨어 가속도 지원됩니다.
   • Rabin은 학술적으로는 RSA와 어깨를 나란히 하지만, 실제 산업적으로는 덜 채택되었습니다.