몽고메리 곱셈 계산기

하드웨어에서 나눗셈이 곱셈보다 열 배 넘게 느리기 때문입니다. RSA 하나를 계산하려면 모듈러 곱셈을 수천 번 되풀이해야 하는데, 그때마다 나눗셈을 하면 그 비용이 전부를 좌우합니다. 몽고메리 방식은 나눗셈을 2ᵏ로만 하도록 바꾸는데, 2의 거듭제곱으로 나누는 것은 시프트라 사실상 공짜입니다.

n′을 그렇게 되도록 골랐기 때문입니다. m = T·n′ mod R이고 n′ = −n⁻¹ mod R이므로 T + m·n ≡ T + T·n′·n ≡ T − T ≡ 0 (mod R)입니다. 한 줄이면 끝나는 이야기인데, 이 한 줄이 나눗셈을 시프트로 바꿉니다.

(T + m·n)/R이 n보다 작다는 보장이 없고 2n보다 작다는 것까지만 보장되기 때문입니다. 그래서 n 이상이면 한 번 빼면 됩니다. 다만 이 분기가 «뺐는가 안 뺐는가»를 실행시간으로 흘려 부채널 공격의 빌미가 되기도 해서, 실제 암호 구현은 늘 빼되 결과를 상수시간으로 고르는 식으로 처리합니다.

아닙니다. 오히려 손해입니다. 값을 몽고메리 표현 ā = a·R mod n으로 바꿔 넣고 나중에 되돌리는 비용이 있어서, 곱셈 한 번을 위해 REDC를 세 번이나 하게 됩니다. 거듭제곱처럼 같은 모듈로 수백·수천 번 곱할 때라야 진입·이탈 비용이 묻히고 이깁니다 — RSA가 딱 그 경우입니다.

R = 2ᵏ와 서로소여야 n⁻¹ mod R이 존재하기 때문입니다. n이 짝수면 n과 R이 2를 공약수로 가져 역원이 없고, n′을 만들 수 없으므로 방법 자체가 성립하지 않습니다. 암호에서 쓰는 모듈러스는 큰 소수이거나 소수의 곱이라 언제나 홀수여서 실제로는 걸림돌이 되지 않습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.