■　「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)＋１よりも小さいべき乗で再出現する）は kob. さんの (P-1)x(Q-1) ではなく LCM( (P-1),(Q-1) ) であるという指摘によって氷解しました。どうも有り難うございました。
　しかしながら、実際には (P-1)x(Q-1) と表現している文献、ＷＥＢが数多く存在しているのも事実です。初心者にとってはじめて目に触れるであろうそれらが、一日も早くはやく修正されるよう願っています。

と書かれていました。

ただし 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 */

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

前へ　次へ

メニューへ戻る