목록Cryptography (9)

암호(수학) 등.. 공부한 거 잊을거 같아서 만든 블로그

[Cryptograhpy] CRT를 이용한 빠른 RSA 복호화

CRT(Chinese Remainder Theorem)를 이용하면 RSA복호화를 기존 복호화 방식보다 빠르게 할 수 있다. CRT를 이용한 빠른 RSA 복호화 증명 CRT에 의하여 (1), (2)를 만족하는 m이 유일하게 존재. 아래의 식을 위 식의 k에 대입 양변에 q 곱하면 m2 이항 p > q 라고 하면 위 식을 이용하여 복호화 하면 기존 복호화 방법인 보다 빠르게 복호화가 가능하다. (사전에 필요한 값 대부분을 미리 계산하기 때문) 하지만 m1, m2를 아직모르기에 m1 와 m2를 구해보자. m1, m2 구하기 이므로 이다. 따라서 이고 위수(order)가 페르마 소정리에 의하여 p - 1이므로 이다. m2도 위와 같은 방법으로 하면 다음과 같다. 이제 m1과 m2를 알았으므로 위 방법을 사용하여..
Cryptography 2022. 10. 29. 22:43
이전 Prev 1 2 Next 다음