RSA暗号のべき乗剰余計算

IT Ruby

RSA暗号

RSA暗号では、a^b mod c という演算が使われる。

暗号化及び復号化の手順は次のようになる。

  • 素数p, q （自分で決める）
  • n = p * q
  • n' = (p - 1) * (q - 1)
  • n' と互いに素な数 e (自分で決める)
  • e * d mod n' = 1 となる d （ 1 < d < n' の範囲では唯一）

を決めて、n と e を公開鍵とする。 そして平文 M に対し、M^e mod n (=C) で暗号化する。復号は、C^d mod n (=M) で行う。

参考）
RSA暗号の仕組みと安全性・具体例 | 高校数学の美しい物語

RSA暗号で「ふっかつのじゅもん」を作る(1) - Pashango’s Blog

べき剰余計算

e や d が大きな数になると、M^e や C^d を計算することは困難となる。しかし最終的に剰余を求めるのであれば、分割して計算することができる。

参考）
大きな数の累乗の余りを計算する方法|0からわかる、暗号(RSA)の仕組み|独極

上記ページ（の次のページ）には手作業で計算する例が載っている。ruby などのプログラミング言語のライブラリでもこのような剰余機能が組み込まれている。；

> (109861231 ** 69345235) % 572309893
warning: in a**b, b may be too big

> 109861231.pow(69345235, 572309893)
=> 75

[Ruby] (巨大な整数でも) 冪剰余を求める #Ruby - Qiita

計算サイト

以下のサイトでは入力した値で RSAを計算することができる。

RSA暗号

ここで

RSA 暗号の解読（1文字） | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

にあった

p q e E(暗号文)
23917 23929 8731 109861231

を入れてみるが

となり暗号Ｃが正しく作られない。

正しくは以下となるはず
irb(main):038:0> (75**e) % n
=> 109861231

このサイトのソースを見ると pmod関数が以下のように定義されている。

/*べきのmod計算*/

function pmod(m,e,n)
{
var i, j,aa,xx
j=1;
aa=e;
xx=m;
i=0;
while (aa!=0)
    {
    if ((aa%2)==1)
        {
        j=(j*xx)%n;
        }
    aa=Math.floor(aa/2);
    xx=(xx*xx)%n;
    i++;
    }
return(j);
}
  • 奇数なら a^(n+1) を a^n × a に分割して指数部を偶数にする。
  • n が偶数である an について、m = 2 * n として
    a^n = a^(2*m) = a^2 * a^m
  • としているがここで j を含めてない。

これ合ってるんだろうか？