Spaurh의 느긋한 블로그



Asymmetric-key Cryptography Programming Tip

1. Trapdoor One way Function.

A one-way function은 두가지 조건을 만족한다.
a. f(x) = y. f(x)는 쉽게 계산가능
b. f'는 계산하기 어렵다. y가 주어졌을때, 산술적으로 x = f'(y)계산 불가능하다.

one-way는 한쪽방향으로만 계산이 쉽기 때문에 one-way function이라고 한다. 어렵다는 말은 컴퓨터로 쉽게 계산되기 어렵다는 말로 계산복잡도가 높다는 말이다.

A trapdoor One-way function은 세번째 조건을 가지고 있다.
c. y가 주어졌을때, trapdoor를 알고 있으면 y = f'(x)를 쉽게 계산할 수 있다.  trapdoor의 비밀키를 알고 있어야 풀기 쉬워진다.

RSA cryptosystem.

이 알고리즘은 1977년에 MIT의 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 개발되었기 때문에 이들의 이름을 따서 RSA 암호화라고 불린다.

RSA는 두 exponents e, d를 사용하고, e는 public d는 private키이다. P = plaintext, C = cypherText라고 할 때.
C = P^e mod n (n은 매우 큰 수이다.)
암호화, 복호화 모두 modular exponentiation을 사용한다. modular exponentiation은 다항식 계산에 사용하는 빠른 exponentiation 알고리즘을 이용한다. 그러나 modular logarithm은 modulus할만한 그렇다할 알고리즘이 존재하지 않는다. 때문에 암호화할때는 polynomial time으로(e = public) 연산가능하고, 복호화도 간단하게 할 수 있다. 그러나 중간에 가로챈 C를 복호화 하는 것은 무척 어렵다. 이를 식으로 나타내면.

암호화 : C = P^e mod n
복호화 : P = C^d mod n
가로챈 데이터를 복호화 : P = C^(1/e) mod n - modular logarithm (계산복잡도가 높다)

이는 암호화와 복호화는 trapdoor키를 아는 상태에서 암호화와 복호화를 one-way function으로 할 수 있지만, 가로챈 데이터를 복호화 하는 과정은 trapdoor키를 알지 못한 상황에서 하기가 무척 어렵다는 것이다.

Proof of RSA
If n = P * q, a < n and k 는 정수,  a^k*Φ(n)+1 ≡ a (mod n).

P1 = C^d mod n = (P^e mod n)^d mod n = P^ed mod n
ed = kΦ(n)+1                                                            //d and e are inverse modulo Φ(n)
P1 = P^ed mod n -> P1 = P^kΦ(n)+1 mod n
P1 = P^kΦ(n)+1 mod n = P mod n                                // Euler's theorem(second version)