RSA暗号の解説に出てくる数値の逆数のmod

アルゴリズム
スポンサーリンク

RSA暗号に紹介には、必ず次のような式がでてきます。

これ
inv_1
今日は、この式について解説します。
といっても・・・すみません。言い訳になりますが、
数学科出身ではなく、間違ったこというかもしれません。
それをふまえていただいて・・・解説させていただきます。

まず、m = (p – 1)(q – 1) とすると、式は次のようになります。
inv_2
さて、この式、意味が分かりますでしょうか。
ここで、mod mというのは、mで割った余りとなります。
つまり、式通りの意味を考えると x-1 =(1/x) を計算して、
m で割った余りが y となります。

しかし、よく考えてください。
言い忘れていましたが、x, y, m とも整数なのです。
x が整数の時点で、 x-1 =(1/x) という式を計算すると、
小数点付きの数値となり、小数点付きの数値に対して、
整数 m で割る?というよく分からないことが起きます。

じつは、これは逆数とはいってもモジュラ逆数と呼ばれるものなのです。
つまり、(1/x)みたいなことをしてはいけないのです。たぶん?

さて、モジュラ逆数となると、
上記のこれまでの式は一体どういう意味なのか。
実は、次のような意味になります。
inv_3
x と y を掛け算して、m で割った後の余りが 1 となります。

つまり、これまでの式は、
上記の計算結果を満たすような y を求める式なのです。

例題と行きましょう。
x = 3, m = 10 としたときの y は一体いくつでしょうか。
inv_4
これの y を求めてみましょう。

・・・

求める過程は、モジュラ逆数の紹介にある
拡張ユークリッド互除法最大公約数など、
いくつか値を求める必要がありまして、
ここでは省略します。

そして、答えを求めると y = 7 が導かれます。

実際に計算してみると・・・
inv_5
余りが 1 となり、ぴったりとなります。

なお、Java などでは、
この y の値を BigInteger の modInverse メソッドで計算することが可能です。

	public static void main(String[] args) {
		System.out.println(new BigInteger("3").modInverse(new BigInteger("10")));
	}

コメント

タイトルとURLをコピーしました