RSA

• 가장 유명한 비대칭 알고리즘
  
• 매우 큰 수의 인수분해가 어렵다는 사실을 기반으로 한다.

RSA 계산을 들어가기 이전에 RSA 계산을 하기 위한 함수들을 알고 가자.

오일러 파이 함수

예-2)
RSA에서 많이 사용한다.
N이 두 소수 P와 Q의 곱일 때

 

유클리드 알고리즘

• 두 숫자의 최대공약수(GCD)를 매우 빨리 찾는다.
• 방법 : 두 수중 큰 수를 작은 수로 나눈 후 나머지를 취한다. 다시 세 수중 작은 수 2개를 취한다. 반복. 나머지가 0이 되기 바로 전의 나머지가 원래 두 수의 최대공약수(GCD)이다.
• 

 

 

확장 유클리드 알고리즘

• 
• 유클리드 알고리즘을 거꾸로 써가면서 진행하면 된다.

 

 

RSA 공개키, 비밀키 구하기

이 조건을 만족시키는 D를 찾기 위해서, 확장 유클리드 알고리즘을 사용한다.

확장 유클리드 알고리즘 형태로 변환하면,

예) 만약 , P=11, Q=13이라면,

GCD(x,120)=1 이 되는 값은 7253

D=-43 , S=2599.

여기서의 S값은 RSA계산시 그냥 수이기 때문에 변형이 가능하고, 따라서 S값이 변형 함에 따라서 D는 mod 120의 연산형태를 띄게 된다. 120-43 = 77 가 가능하다.

RSA에서는 N과 E의 값을 공개키, D를 개인키로 하고 P,Q를 버린다.

RSA 암호화, 복호화

메시지 M이 N보다 크면, N보다 작은 단위로 쪼개야 한다. Mod N연산이기 때문이다.

 

 

RSA의 핵심 수식

RSA의 핵심 수식은 "오일러의 정리"에 기반한다.

이 연산은 mod N연산임으로, 다음 식도 참이 됨

양변에 M을 곱한다.


위의 등식이 RSA의 핵심 수식이다.

이 식은 기본적으로 M을 그대로 출력하지만, 두 부분으로 나누면 암호화/복호화에 쓰일 수 있다.

 

 

RSA 문제점

문제는 D를 얼마나 길게 비밀로 유지 할 수 있는가? 이다.

즉, RSA의 키 크기는 인수분해를 하는 것이 충분히 오래 걸려야 한다.

 

 

RSA 문제점 2 , 피터 쇼어의 양자 인수분해 알고리즘

쇼어 알고리즘을 사용하면 크기가 N인 수를 소인수분해할 때 O(log3N)의 시간과 O(logN)의 저장공간이 필요하다.
원본 위치 <http://ko.wikipedia.org/wiki/%EC%87%BC%EC%96%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98>

따라서, 확실히 큰 수의 인수분해를 할 만큼 양자 컴퓨터가 개발된다면, RSA는 쉽게 깰 수 있다.

피터 쇼어의 양자 인수분해 알고리즘 순서 : 인수분해할 숫자를 N이라 하자. 그리고 N보다 작은 숫자 A를 고른다. 이 A는 N과 서로소이다. 그런데 RSA에 쓰이는 N은 항상 두 소수의 곱이고, 이는 곧, N과 서로소가 아닌 수는 N을 이루는 두 소수밖에 없으므로 A를 고르는 일은 매우 쉽다. 그 후

증명 :

예제 :

출처 : 개정판 해킹 공격의 예술 (에이콘 출판사) 책을 읽고 정리한 내용입니다.