Multi-prime RSAの計算方法＆実際に計算する

投稿日：2022/02/28 更新日:2022/02/28

RSA暗号との違い

まずRSA暗号を知らない人は以下の記事を読んでみてください！

$N$ の値が2つの素数からではなく、3つ以上の素数からなります。

\begin{aligned} RSA : N &= p\times q\\ Multi-prime\ RSA: N &= p_1^{k_1} \times p_2^{k_2} \times ...\times p_n^{k_n} \end{aligned}

鍵の生成の前にオイラー関数について知っておく必要があります。
本題ではないので簡単に説明します。
オイラー関数とは以下のことです

\varphi(n) = nと互いに素である1以上n未満の自然数の個数

$\varphi(10)$ を考えてみましょう！
10と互いに素な自然数は{1, 3, 7, 9}の4つです。したがって、 $\varphi(10) = 4$ となります。

鍵の作成はRSAとほとんど同じです。

いくつかの素数 $p, q, r ...$ を選び $N$ を作ります

N=p^{k_1} \times q^{k_2} \times r^{k_3}...

$\varphi(N)$ を計算します。
もしも、 $N=p \times q \times r...$ のような一乗の素数だけで構成されいると以下のような簡単な式で計算できます。

\varphi(N) = (p-1)(q-1)(r-1)...

$E$ は以下の条件式を満たす者です

1 < E < \varphi(N)\\ \gcd(E, \varphi(N))=1

$1<E<\varphi(N)$ の中で $\varphi(N)$ と互いに素な数ということです！

$D$ は以下の条件式を満たすものです。

1 < D < \varphi(N)\\ E\times D \equiv 1 \mod\varphi(N)

$E\times D$ の値を $\varphi(N)$ で割った余りが1ということですね！

このようにして得られた $E$ と $N$ が公開鍵、 $D$ と $N$ が秘密鍵です！

今回は $p=3, q=5, r=7$ でいきます！

\begin{aligned} N&=3\times 5 \times 7\\ &= 105 \end{aligned}

今回はすべて1乗なので簡単に計算できます!

\begin{aligned} \varphi(105) &= (3-1)(5-1)(7-1)\\ &= 48 \end{aligned}

$1 < E < 48$ の中で48と互いに素（ $\gcd(E, 48)=1$ ）の数を探します。
$E = 5, 7, 11...$ と複数の候補が見つかります。どれを選んでも良いですが、今回は $E=5$ とします！

$1 < D < 48$ の中で $5E \equiv 1 \mod 48$ となる $D$ を探します。
$D = 29$ の時に条件を満たします！

得られた $E = 5, N = 105$ が公開鍵、そして $D = 29, N=105$ が秘密鍵です。

今回は「32」を暗号化してみましょう！

公開鍵は $E = 5, N = 105$ ですので以下の式で暗号化できます

\begin{aligned} 暗号文 &= 32^{5}\mod 105\\ &= 33554432 \mod 105\\ &= 2 \end{aligned}

得られた「2」が暗号文です！

$D = 29, N=105$ の秘密鍵で先ほどの暗号「2」を復号しましょう！

\begin{aligned} 平文&=2^{29}\mod 105\\ &= 536870912 \mod 105\\ &= 32 \end{aligned}

先ほど暗号化した「32」が得られています！
正しく復号化できました！

今回はMulti-prime RSAについて学びました。ほどんどRSA暗号と同じということが分かったと思います！

Hinek, M. Jason. "On the security of multi-prime RSA." Journal of Mathematical Cryptology 2.2 (2008): 117-147.