Rabin 알고리즘

Rabin 알고리즘은 공개키 암호화 알고리즘 중 하나로, RSA 알고리즘과 비슷하게 작동합니다. 이 알고리즘은 Miller-Rabin 소수 판별 알고리즘을 사용하여 랜덤한 소수를 생성하고, 이를 이용하여 키를 생성합니다. 암호화는 평문을 제곱한 뒤, 소수로 나눈 나머지를 계산하여 수행하며, 복호화는 수학적 원리를 이용하여 암호문의 제곱근 중 4개의 가능한 해 중 올바른 해를 찾아내는 방식으로 수행됩니다. Rabin 알고리즘은 RSA 알고리즘보다 빠르게 작동하며, 해독 문제의 어려움 때문에 안전성이 높습니다.

 

(아래는 이해를 돕기 위한 간단한 예시로 작은 숫자를 활용해보았습니다)

공개키/개인키 생성 과정

1. 소수(p,q) 선택

Rabin 알고리즘은 RSA와 마찬가지로 1024비트 이상의 두 개의 서로 다른 소수 p와 q를 선택합니다. RSA 알고리즘과 다른 점은, 소수 p와 q는 4k+3 형태의 정수입니다.

p=7, q=11

2. n 값 계산

n은 두 소수(p,q)의 곱셈 n = p * q 으로 계산됩니다.

n=77

3. 공개키, 개인키 생성

n은 공개키, (p,q)는 개인키가 됩니다.

n=77, (p,q)=(7,11)

암호화 과정

1. 암호화하는 메세지를 ASCII 코드로 변환

암호화하기 위한 평문의 모든 글자를 ASCII 코드로 변환하여 각 글자를 1바이트로 변환합니다. 이후 바이트 단위로 암호화가 진행됩니다.

“pop”를 암호화하기 위해 ASCII 코드를 변환: p=112, o=111, p=112

2. 공개키로 암호화

공개키n를 이용하여, 암호화하고자 하는 메시지가 M일 때 다음 수식을 통해 암호화된 메세지 C를 얻을 수 있습니다.

공개키 n=77을 사용하면 다음과 같이 변환됩니다. 암호화된 문구 C(“ F
F ”)= 70 1 70

복호화 과정

1. 개인키로 복호화

개인키 (p,q)를 이용해 복호화를 합니다. 개인키 p와 q가 4k+3의 형태임을 이용해서 4개의 근을 도출합니다.

이후 CRT(Chinese Remainder Theorem)을 이용해서 복호화 된 값을 4개를 도출합니다

{P1,P2,P3,P4} 중 하나가 평문이 되며, 일반적으로 ASCII 코드에서 영문자 및 숫자와 일반적으로 사용되는 특수 문자를 범위로 지정하여 필터링을 하는 방식으로 올바르게 복호화된 평문을 확인하는 방법이 사용됩니다.

개인키 p=7,q=11 을 사용하면 다음과 같이 변환됩니다. 복화된 문구 P(“ pop ”)= 112 111 112