[RABIN] in Public-key cryptosystem

수식 입력이 번거로워서 수식 표현이 좀 매끄럽지 못합니다.

특히 주의해서 보실 것: 예를 들어 a의 역원인 경우, a역 이라 표현했습니다.

키 생성

public key: n이고, private key: (p, q)이다.

서로다른 두 소수 p, q (4k+ 3 형태)를 선택한 뒤,

n을 얻는다: n = p * q

 

 

암호화

c ≡ m^2 mod n

 

복호화

 

먼저,
c1 ≡ c mod p,
c2 ≡ c mod q를 계산한다.

 

이를 이용하여,
a1 and a2 ≡ +- c1^(p+1  /  4) mod p,
b1 and b2 ≡ +- c2^(q+1  /  4) mod q를 계산한다.

 

여기서, a1 또는 a2, 그리고 b1 또는 b2 중 하나씩 고르는 경우의 수는 2*2 = 4가지이므로,

m = p * (p역 mod q) * b + q * (q역 mod p) * a 의 경우의 수 역시 4가지이다.

 

최종적으로, 실제 m은 이 중 1개이다. 

안전성 

 

 

A1, A2: Algorithm 1, 2

  A2는 RABIN 암호를 무조건 풀어낼 수 있는 놈이다.

  (실제로 그런 알고리즘이 뭔지 안다는 게 아니라, 단지 그저! 안전성 증명을 위한 전제로서 만들어낸 것 뿐입니다)    

 

1단계. "Rabin 암호를 풀 수 있으면, 인수분해 문제가 풀린다"(Rabin easy -> 인수분해 easy)가 참임을 증명 

 

위가 참임을 증명하기 위해, "전건을 참으로 전제"한 상태에서 후건의 참 여부를 확인할 것이다.

여기서 "전건을 참으로 전제"한다는 것은 즉 "Rabin 암호를 무조건 풀어낼 수 있는 방법이 있다고 전제"하는 것이며,

이는 그림 상에서 "A2 for RABIN"으로 나타나있다. 

 

우리의 목적은 "이 A2를 활용한다면 A1도 풀릴 수 있는가?"를 확인하는 것이다.  

인수분해 하고자 하는 수 n을 A1의 입력으로 넣고, 
A1 안에서는 y를 랜덤으로 골라, c ≡ y^2 mod n을 계산한다.
이 c를 A2에 입력으로 넣으면, 애초에 A2은 무조건 Rabin 암호를 풀 수 있다고 전제했던 녀석이므로, x를 출력할 수 있다 (able).

이 x값이 만약 +-y mod n가 아니라면 (이것은 단지 trivial한 경우이므로 배제하는 것이다) ,
gcd(x-y, n), gcd(x+y, n)을 계산해봐서, 

이 결과가 만약 "1 초과 n 미만"이면 p와 q를 찾은 것 (즉 n의 인수를 찾은 것, 즉 인수분해 문제를 푼 것)이고, 
그렇지 않다면, 처음부터 다른 y값으로 다시 시도한다.

위 방법으로 인수분해 문제가 풀리므로, 

"Rabin easy -> 인수분해 easy"는 참으로 증명되었다.

 
2단계. 위의 대우인 "인수분해 문제가 어렵다면, Rabin 암호도 어렵다(안전하다)"(인수분해 hard -> Rabin hard) 역시 참이다.

 

3단계. 위에서 전건(인수분해 hard)은 참이므로, 따라서 후건(Rabin hard)이 참이다.

이로써, RABIN 암호의 안전성은 증명되었다.