書記が数学やるだけ#895 RSA暗号の高速化

RSA暗号の計算を高速化する手法について例を挙げる。

問題

説明

モンゴメリ乗算（Montgomery multiplication）とは、特に時間のかかる除算を実質的に行うことなく、乗算・加算・減算・シフト演算のみで整数の積の剰余を効率的に求めることのできるアルゴリズムである。暗号理論の分野では、数百ビットを超える法による冪剰余演算が重要な役割を果たし、このような冪剰余演算にモンゴメリ乗算が利用されている。

さらに、中国剰余定理を用いて冪剰余演算の指数計算を分割することで、RSA暗号などの計算を高速化することが可能である。

Garner アルゴリズムを用いて中国剰余定理に基づく計算を逐次実施することにより、さらに効率化を図ることができる。

解答

直接法では、c^dmodN を計算する必要があり、法 N=55 のもとでは 27 回の繰り返し二乗法が必要である。大きな RSA では指数 d が 2048 ビット規模であるため、計算は非常に重い。

一方、CRT 法では法を p=5,q=11 に分割し、それぞれの指数をd_p =3,d_q =7 と小さくする。計算は「2 つの小さい法」で行われるため、理論上約 4 倍の高速化が得られる。

また，通常のCRTは

$$x≡∑r_i M_i M_{I−1}\ (modM) ,\ M=∏mi$$

という形を使うが、各 Mi  が大きくなるので中間計算が巨大になりやすい。

Garner法では

$$x=a_1 +a_2 m_1 +a_3 m_1 m_2 +⋯$$

の形で 逐次的に小さい法の中で計算し、最後に組み立てることで，大きな数の積を直接扱わずに済む。

モンゴメリ乗算によって通常の計算と同じ結果が得られることは、以下の補題から示される。

実際の計算例を以下に示す。

本記事のもくじはこちら：