쇼어 알고리즘

쇼어의 소인수 분해 알고리즘으로 이전의 암호문제를 해결할 수 있습니다. 

 

RSA 알고리즘이 현대 암호학의 기반을 이뤄어냈다고 과언이 아닐 텐데 이에 대한 암호를 해결할 수 있는 알고리즘이 양자알고리즘을 통해 나오고 있습니다. 

 

쇼어 알고리즘을 정리하면 다음과 같습니다. 

 

 

 

예시로 91을 소인수 분해하는 과정을 쇼어 알고리즘 방식으로 풀어봅시다.

 

 

91=?x?

 

어떠한 연산값을 먼저 추정해야 하는데 여기서 a=3이라고 정의해 봅시다. 

 

f(x) = a^x mod N

 

으로 정의하면 f(x)=3^x mod 91이 만들어집니다. 

 

이를 한번 계산해 보면 

 

3^1 mod 91=3

3^2 mod 91=9

3^3 mod 91=27

3^4 mod 91=81

3^5 mod 91=63

3^6 mod 91=9 ( 패턴 반복 시작)

3^7 mod 91=27

 

여기서 주기가 r=6이라는 것을 확인 합니다. 

 

이제 공식에 이 내용을 적용해 봅시다. 

 

 

 

a=3과 r=6을 대비하면 

 

 

 

 13과 7이라는 결과를 얻어냅니다. 

 

91=13 x 7입니다. 

 

이를 RSA 방법으로 한번 진행해 보면 쇼어 알고리즘이 상당히 빠른 속도로 문제를 해결하는지 확인할 수 있습니다. 

 

쇼어 알고리즘의 특징을 주기 규칙을 발견해서 바로 결과를 나타내며, RSA는 소인수 분해를 통해 다 나눠본 후 결과를 찾는 방법입니다. 

 

 

RSA 방법

 

두 개의 소수 p,q 를 선택해 봅시다. N을 공개해도 p,q를 알수 없고, 개인키 d를 알 수 없다는 전제입니다.

 

p=7, q= 13

 

입니다. N=p x q , N=91 입니다. 

 

공개키 (N,e) 와 개인키 (N,d)로 구분하여 e와 d는 역원 관계로 정의합니다. 

 

 

 

 

 

따라서 공개키는 (91,5) 개인키는 (91,29)

 

M=10이라고 하면 

 

암호화 C=10^5 mod 91=82

복호화 M=82^29 mod 91 =10

 

 

이렇게 연산을 할 수 있습니다. 

 

 

https://www.apple-economy.com/news/articleView.html?idxno=71062

‘RSA암호알고리즘’과 ‘쇼어 알고리즘’의 싸움 - 애플경제

 

 

 

https://horizon.kias.re.kr/14195/

양자 알고리즘: 소인수 분해 알고리즘

 

 

https://sean9892.tistory.com/45

쇼어 알고리즘 바닥부터 설명하기 (Shor's Algorithm explained from scratch)