博士

ロボ子、今日のITニュースはRSA暗号の鍵生成に関するものじゃ。

ロボ子

RSA暗号ですね。公開鍵と秘密鍵を使う暗号方式でしたでしょうか。

博士

そうじゃ！RSAの公開鍵は、指数 *e* と *n* = *p* *q* のペア(*e*, *n*)で構成されるんじゃよ。*p* と *q* は大きな素数じゃ。

ロボ子

なるほど。初期のRSA論文では、秘密鍵 *d* を選択して、*e* *d* ≡ 1 mod φ(*n*) を計算していたと。

博士

そうそう。今は *e* を選んで *d* を計算するのが一般的で、*e* はほぼ常に65537じゃな。

ロボ子

φ(*n*) はオイラーのトーティエント関数で、φ(*n*) = (*p* − 1)(*q* − 1) で計算されるんですよね。

博士

その通り！RSA暗号の安全性は、*p* と *q* を知らない限り、φ(*n*) を計算するのが難しいという仮定に基づいているんじゃ。

ロボ子

秘密鍵 *d* の計算方法が、当初の *e* *d* ≡ 1 mod φ(*n*) から、*e* *d* ≡ 1 mod λ(*n*) に変わったというのは、どういうことでしょうか？

博士

λ(*n*) はカーマイケルのトーティエント関数じゃ。フェルマーの小定理のオイラーによる一般化におけるφ(*n*)を置き換えることができる最小の数として定義されていて、λ(*n*)はφ(*n*)を割り切るんじゃ。

ロボ子

カーマイケルのトーティエント関数を使うと、秘密鍵が小さくなって、復号が速くなるんですね。

博士

*n* = *p* *q* の場合、λ(*n*) = lcm((*p* − 1), (*q* − 1)) = (*p* − 1)(*q* − 1) / gcd((*p* − 1), (*q* − 1)) となるんじゃ。

ロボ子

λ(*n*) は φ(*n*) よりも gcd((*p* − 1), (*q* − 1)) の分だけ小さいんですね。少なくとも、この因子は2以上だと。

博士

そうじゃ。でも実験によると、gcd((*p* − 1), (*q* − 1)) は通常2か4で、カーマイケルのトーティエント関数を使っても効率の向上はわずかなんじゃ。

ロボ子

なるほど。ガーナーのアルゴリズムを使う方が、効率が向上するんですね。

博士

そういうことじゃ！RSA暗号も奥が深いじゃろう？

ロボ子

はい、勉強になりました！

博士

ところでロボ子、RSA暗号の「RSA」って何の略か知ってるか？

ロボ子

えっと…発明者の名前ですよね？

博士

正解！じゃあ、ロボ子が暗号を発明したら、なんて名前にする？

ロボ子

そうですね…「ロボ子暗号」…ですかね？

博士

ダサっ！私なら「ハカセクリプト」にするぞ！