[수학] 수학을 이용한 암호(RSA&동형암호)

수의 성질을 이용한 암호(RSA&동형암호)

정보를 보호하는 암호는 숫자와 밀접한 관계로 수의 성질을 이용한 경우가 많다. 오늘날 금융이나 빅데이터 같은 분야에서 쓰이는 암호도 마찬가지이다. 대표적인 예시로 RSA와 동형암호가 있다.

 

• RSA vs 동형암호
   RSA는 큰 숫자일수록 소인수 분해하기 어렵다는 점을 적용한 암호 기술이다. RSA 덕분에 전자상거래의 기술적, 보안적 기반이 마련되었다. 그런데 1993년 피터 쇼어가 양자 컴퓨터를 이용하여 매우 큰 숫자를 일정 시간 안에 소인수 분해하는 방법을 발표하였다. 양자컴퓨터가 발명되면 안정성이 무너진다는 우려가 생기기 시작했다.
   이에 대한 해결책이 동형암호이다. 동형암호는 수학적 난제를 이용하여 정보를 처리하는 암호 기술로 양자컴퓨터가 뚫을 수 없다. 또한 이전의 암호 기술은 정보를 처리하기 위해 복호화 과정을 거치는데 동형암호는 암호화된 상태에서 정보를 처리하기 때문에 해킹의 위험성이 낮다. 이는 빅데이터와 개인정보를 활용하는 기술적, 보안적 밑거름이 될 것이다.

  	RSA	동형암호
  수학 원리	큰 수의 소인수 분해	P-NP 난제
  안정성	양자컴퓨터에 취약함	양자컴퓨터에서도 안정적임
  활용	전자상거래 등	빅데이터 등

 

 

• RSA의 원리

A가 B에게 정보를 암호화하여 전달하려는 상황이다. (출처: Iconscut.com)

1. B가 A에게 줄 공개키를 만든다.
   공개키는 n과 e로 이루어져 있다.
   n = p × q이고 e는 n보다 작은 임의의 숫자이다. (단, p와 q는 소수)
2. B의 개인키를 만든다.
   개인키는 n과 d로 이루어져 있다.
   d는 {(p-1)(q-1) ×k+1} / e이다. (단, k는 임의의 수)
   
   
3. B가 공개키를 공개하여 A가 볼 수 있게 한다.
   
   
4.  A는 공개키를 이용하여 정보를 암호화한다.
   원래 정보를 M을 암호화된 정보 m으로 바꾸는 것이다. >>> m = (M^e) mod (n)
   a mod b = c는 a를 b로 나눈 나머지가 c라는 뜻이다.
   수식으로 표현하면 m = M^e -(n×k) (단, k는 임의의 자연수)
   
   
5. A가 암호화된 정보 m을 공개하여 B가 볼 수 있게 한다.
   
   
6. B가 개인키로 암호화된 정보를 복호화한다.
   m = M^e mod n은 '페르마의 소정리'에 의해서 M = m^d mod n과 같다.
   B는 개인키(n과 d) 값을 알기 때문에 원래 정보인 M 값을 알아낼 수 있다.
   
   
7. 총정리
   p와 q를 알아내면 개인키를 알아내어 정보를 복호화할 수 있다.
   그러나 n을 소인수 분해해야 하고 이는 시간이 매우 오래 걸려 불가능에 가깝다.
   암호화된 정보 m을 이용하여 원래 정보 M을 알아내려는 시도가 있을 수 있다.
   그러나 m = M^e-(n×k)에서 M과 k를 모르기 때문에 불가능하다.
   (1개의 방정식에 미지수가 2개 있으면 해가 무수히 많다.)
   * 해킹을 시도하더라도 해커는 공개키(n, d)와 암호화된 정보 m밖에 모르므로 해킹할 수 없다.
   (더 자세한 원리는 https://www.youtube.com/watch?v=kGUlfVpIfaQ를 참고하세요.)

반응형

• 동형암호의 원리

A가 B에게 암호화된 정보를 주면 B가 정보를 처리하고 복호화하는 상황이다. (출처: Iconscut.com)

1. A가 가진 정보들을 암호화한다.
   - 숫자 10과 15를 가지고 있다.
   A와 B만 알고 있는 비밀키 12345를 이용한다.
   10은 10+(12345×a)
   15는 15+(12345×b)로 암호화한다.
   단, a와 b는 임의의 작은 자연수
   
   
2. B에게 전송한다.
   
   
3. B가 암호화된 정보를 처리한다.
   - 두 정보를 덧셈한다고 가정한다.
   10+(12345×a)+15+(12345×b)이다.
   정리하면 25+12345(a+b)이다.
   비밀키인 12345를 이용해서 25로 복호화한다.
   
   
4. 총정리
   - 12345를 모르면 복호화하기가 불가능하다. (P-NP난제)
   - 정보를 복호화하지 않고 연산하더라도 결과값이 같다.
   - 이러한 원리에 근사연산, 기계학습 등을 더해 상용화 연구 중이다.
   P-NP 설명 더보기

 일정 시간(다항시간) 내에 답을 구할 수 있는 문제를 P문제라 한다. 문제의 답에 대해 검산할 수 있지만, 일정 시간 내에 답을 구할 수 없는 문제를 NP문제라고 한다. 'P문제이면 NP문제이다'는 성립하지만 'NP문제이면 P문제이다'는 아직 증명되지 않았다. 즉, 어려운 문제(NP문제를) 쉬운 문제(P문제)로 변환하는 방법은 아직 밝혀지지 않은 것이다.
위의 동형암호에 적용해 보면 문제는 25+12345(a+b)라는 숫자에서 25를 알아내는 것이다. 이때, 12345라는 비밀키를 알면 25라는 숫자를 일정 시간 내에 구할 수 있다. (검산 가능) 그러나 비밀키를 모르는 채로 숫자 25를 알아내는 것은 불가능하다. (어려운 문제) 어려운 문제를 쉬운 문제로 변환할 수 없으므로 비밀키를 모른다면 정보를 복호화할 수 없는 것이다.