■ 「mod (p-1)×(q-1)」or「mod LCM (p-1,q-1)」?

 2000年7月4日に献本としてもらった雑誌(私の作ったソフトが収録されています)を眺めていると「RSA実地体験 Ver.1.01」(1998/5/14付)と言うのを見つけました。興味があったので解凍(展開?)して readme.txt を眺めていると

謝辞
 V1.00 における疑問点(φ(N)+1よりも小さいべき乗で再出現する)は kob. さんの (P-1)x(Q-1) ではなく LCM( (P-1),(Q-1) ) であるという指摘によって氷解しました。どうも有り難うございました。
 しかしながら、実際には (P-1)x(Q-1) と表現している文献、WEBが数多く存在しているのも事実です。初心者にとってはじめて目に触れるであろうそれらが、一日も早くはやく修正されるよう願っています。

と書かれていました。

ただし readme.txt を読むと,この方は「LCM (p-1,q-1)」と「φ(N)」を混同していると思われます。通常 φ(N) とはオイラー関数のことなので φ(N)=φ(p×q)=φ(p)×φ(q)=(p-1)×(q-1) です。ここで LCM は Least Common Multiple,最小公倍数のことです。この文書が正しいのであれば私も間違えている一人です。少し調べる必要があるようです。

 そこで「RSA セキュリティ社の Web ページ(日本語と英語両方)」や「結城浩さんが書かれた C MAGAZINE の記事」,「PGP 暗号メールと電子署名」(Simson Garfinkel 著,山本和彦 訳)を読んでみましたがすべて mod (p-1)×(q-1) と書かれていました。総元締めの RSA セキュリティ社でさえ mod (p-1)×(q-1) と書かれているので,多くの人がそう信じるのも無理はないと思います(2000年当時の話です)。

※ 2008年1月に再度確認したところRSA社の文献でも LCM (p-1,q-1) が使われていました。参考 URL ftp://ftp.rsasecurity.com/pub/rsalabs/rsa_algorithm/rsa-oaep_spec.pdf の5ページ

 しかし確かに mod LCM (p-1,q-1) と書かれている文献があるのも事実でした。(例えば,「符号と暗号の数理」,共立出版,藤原・神保著,ISBN4-320-02661-6)

 そこで PGP ではどのように実装されているのだろうと思い,ソースコードをダウンロードすることにしました。PGP 6.5 あたりのコードは見つからなかったので,一番新しそうな PGP 6.0.2 のソースコード をダウンロードしました。
\pgp602i-win-src\libs\pgpcdk\priv\keys\pubkey\pgpRSAKey.c の 1516行目から

	/* Find the product, n = lcm(p-1,q-1) = c * d */
	if (bnMul(&sec->s.n, &sec->s.q, &sec->s.d) < 0)
		goto bnerror;

	/* Find the inverse of the exponent mod n */
	i = bnInv(&sec->s.d, &sec->s.e, &sec->s.n);
	if (i < 0)
		goto bnerror;
	pgpAssert(!i);	/* We should NOT get an error here */
と書かれています。つまり PGP でも LCM (p-1,q-1) が使用されています。

どうやら 「mod LCM (p-1,q-1)」を使うべき ようです。

前へ 次へ

メニューへ戻る