Public-Key Cryptography (공개키 알고리즘)

RSA 관련 문제를 풀이하던 중 공개키 알고리즘에 대해 자세히 알아보고 싶어 정리했습니다.

 

---

RSA 암호

RSA 암호는 공개키 암호시스템의 하나로, 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘으로 알려져 있다.

RSA 암호체계의 안정성은 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 두고 있다.

결국 큰 수의 소인수분해를 빠르게 할 수 있는 알고리즘이 발견되면 이 암호체계는 가치가 떨어진다는 것이다.

 

RSA는 두 개의 키를 사용한다.

공개키 : 모두에게 알려져 있으며 메시지를 암호화하는데 쓰인다.

개인키 : 개인키를 가진 자만이 암호화된 메시지를 복호화할때 쓰인다.

 

대칭키 알고리즘과의 차이는 누구나 어떤 메시지를 암호화할 수 있지만 그것을 해독하여 열람할 수 있는 사람은

개인키를 가진 사람만이 복호화할 수 있다는 점에서 차이가 있다.

또한 RSA 암호는 대칭키인 DES나 AES보다 속도가 느리므로 메시지 암호화에는 쓰이지 않고

주로 키를 암호화하는데 쓰인다.

---

키의 생성

공개키와 개인키를 제작하는 과정은 다음과 같다.

 

출처 : https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8

공개키 : < N, e >

개인키 : < N, d >

 

B가 A에게 메시지를 전달하기 위해서는 A의 공개키가 필요하다.

A는 위의 방법을 통해 공개키와 개인키를 제작하고 B에게 공개키를 공개한다.

B는 이 공개키를 사용하여 자신의 메시지를 암호화하게 된다.

 

여기서 p와 q를 알게된다면 d와 e의 계산이 가능하기 때문에 보안에 신경을 써야한다.

 

---

RSA 암호화

C : 암호문, M : 평문, e : 공개키, n : 소수의 곱 (n=pq)

 

암호문 C의 길이는 n의 길이에 따라 결정되므로 n 이상의 평문을 암호화할 수 없다.

mod 연산으로 인해 결과값의 범위는 0~n-1까지이기 때문이다.

 

합동(≡)은 도형에서 완전히 겹쳐지는 관계를 뜻하지만 여기서는 나머지가 서로 같은 두 정수 사이의 관계를 뜻한다.

5 ≡ 8 mod 3은 5를 3으로 나누었을 때 나머지가 2이고 8도 3으로 나누었을 때 나머지가 2이므로

5와 8은 mod 3에 대해 합동 관계에 있는 것이다.

---

RSA 복호화

M : 평문, C : 암호문, d : 개인키, n : 소수의 곱

 

RSA 암호화와 복호화가 가능한 이유를 증명하면 아래와 같다.

 

gcd(M,n) = 1인 경우 : 오일러 정리에 의해 성립함을 알 수 있다.

gcd(M,n) ≠ 1인 경우: M<n이므로 M은 p의 배수이거나 q의 배수이다.

p의 배수라고 가정하면

위의 식이 성립한다.

그러므로

이 성립한다.

---

RSA 문제

 

두 개의 서로 다른 소수 p와 q의 곱인 양의 정수 n, gcd(e,Φ(n))=1인 양의정수 e, 양의 정수 c가 주어졌을 때

 

인 m을 찾는 문제를 RSA 문제라 한다.

이 문제는 n을 인수분해 할 수 있으면 쉽게 다음과 같이 해결할 수 있다.

 

1. Φ(n) = (p-1)(q-1) 을 계산한다.

2. ed ≡ 1 (mod Φ(n))인 d를찾는다. (확장된 유클리드 알고리즘을 이용)

3. 다음 식을 이용하여 m을 계산한다.

---

위와같은 문제도 단순히 식 대입만으로 정답을 찾을 수 있다.

다만 지수가 너무 크므로 모듈러 거듭제곱법을 활용하면 좋다.

 

sh1r0hacker.tistory.com/51?category=898569

RSA Starter 1

sh1r0hacker.tistory.com/60?category=898569

RSA Starter 2