공개키(비대칭) 암호와 RSA 에 대하여

 

* 대칭키 사용의 한계

1. 대칭키 분배 문제

어떻게 상대에게 키를 비밀리에 전달하는가

 

2. 대칭키 수에 대한 문제

사용자가 n 명이라면, 각 사용자는 n-1 개의 키가 필요, 총 n(n+1)/2개의 키가 필요하게 됨

 

3. 사용자간 부인 방지 불가

한 사용자가 대칭키 사용을 부인하는 것을 방지할 수 없음

 

 

 

공개키(비대칭키)

각 사용자는 공개키(public key, K+)와 개인키(private key, K-)두 종류의 키를 생성

공개키는 누구나 알 수 있으나 개인키는 비밀로 함

 

 

 

활용

1. 암호화

Alice(송신자)는 메시지 암호화 시 Bob의 공개키로 암호화 함

Bob(수신자)은 Alice가 보낸 암호문을 복호화 할 때 자신의 개인키로 복호화 함

 

2. 전자서명

Alice는 자신의 개인키로 암호화 함

Bob은 Alice의 공개키로 복호화하여 Alice의 서명을 증명함

 

3. 대칭키 교환

 

 

 

 

Trap door on-way function

한 방향으로는 계산이 쉬우나 반대방향으로는 계산이 어려움

 

[ex]One-way function f(x)

• y = f(x) is is easy
• x = f^-1(y) is infeasible

 

 

 

One-way function의 종류

1. Factoring integers (소인수 분해) : RSA

2. Discrete Logarithm(이산로그) : Diffie-Hellman, Elgamal, DSA

3. Elliptic curve(타원곡선, generalized discrete logarithm) : ECDH, ECDSA

 

 

 

---

RSA?

1977년 Rivest, Shamir, Adleman에 의해 발표된 공개키 방식 암호로 지금까지 널리 사용되고 있음

 

 

 

Factoring Integers (정수의 소인수 분해)

• p와 q는 아주 큰 소수(prime number)
• N = pq 계산은 매움 쉬움
• 하지만 N에서 아주 큰 p, q 를 찾는 것은 매우 어려움

 

 

암호화와 복호화

1. 키 생성

공개키는 n, e 개인키는 n, d 라는 두 정수로 이루어짐

 

n 구하기

임의의 두 소수 p, q를 정하고 n = p * q를 함

 

e 구하기 (공개키에 이용)

Φ(n) = (p-1)(q-1) 로 Φ(n) 을 구함

e는 (1 < e < Φ(n) ) 이면서 Φ(n) 과 서로소인 수로 정해줌

 

d 구하기 (개인키에 사용)

(e * d) mod Φ(n) = 1 를 만족하는 d를 구함

 

 

2. 암호화(Encryption)

메시지 원문을 (M), 암호화된 메시지를 (C) 라고 할 때 아래 식으로 암호화 함

 

 

3. 복호화(Decryption)

 

 

권장사항

• n의 비트 수는 적어도 1024비트가 되어야 함
• 두 개의 소수 p, q는 적어도 512 비트가 되어야 함
• p, q 는 같지 않으며, 거의 같은 크기의 소수이어야 함
• p-1, q-1은 큰 소인수를 각각 가져야 함
• p-1, q-1의 최대공약수는 작은 수이어야 함

 

 

 

 

예제

• M = 8 이라 가정

 

1. 두 개의 소수 p, q 선택 (p = 11, q = 3)

 

2. n = p*q = 33

 

3. Φ(n) = (p-1)*(q-1) = 20

 

4. e = 3 (e = Φ(n)과 서로소)

 

5. d = 7 (e*d = 1 mod 20)

 

6.

암호화 | C = M^e mod 33 = 8^3 = 512 = 17 mod 33 , C = 17

복호화 | M = C^d mod 33 = 17^7 = 410,338,673 = 12,434,505 * 33 + 8 = 8 mod 33

∴ M = 8

 

 

 

 

 

정리

현재 가장 널리 사용되는 공개키 암호 방식으로 주요 응용은 전자 서명과 대칭키 교환

안전성은 1) 대수 소인수분해의 어려움 2)나머지 연산의 역연산의 어려움으로 보장됨 

(현재 컴퓨팅 환경에서는 1024비트는 소인수 분해 할 수 없기 때문, 다만 보안을 위해 2048비트-3076비트 사용 권장됨)

 

 

 

 

 

 

 

 

 

출처

 

https://www.crocus.co.kr/1203

 

RSA 암호 알고리즘

 

https://yjshin.tistory.com/entry/%EC%95%94%ED%98%B8%ED%95%99-%EB%B9%84%EB%8C%80%EC%B9%AD%ED%82%A4-%EC%95%94%ED%98%B8-RSA-%EC%95%94%ED%98%B8%EC%8B%9C%EC%8A%A4%ED%85%9C

[암호학] 비대칭키 암호 - RSA (공개키 암호시스템)

 

이산수학, 

https://www.youtube.com/watch?v=Xh8hTEz09AA&list=PLW8wOTYOluvFmqr01lKXKku_4zjn2RqKH&index=16 

https://www.youtube.com/watch?v=7Pokl4jSmY8&list=PLW8wOTYOluvFmqr01lKXKku_4zjn2RqKH&index=15