PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 182 / RSA暗号

RSA暗号は以下のアルゴリズムにもとづいている。

  • 鍵生成
    • 二つの異なる素数 p と q を生成する
    • n=pq とし,φ=(p-1)(q-1) (=φ(n)) とする
    • 1< e< φ の範囲で gcd(e, φ)=1 となる整数eを決定する
  • 暗号化
    • 平文を [0, n-1] 中の整数 m とする。平文は以下の方法で [0, n-1] 中の整数に暗号化される
    • c=m^e mod n とし, c を暗号文とする
  • 復号
    • 暗号文を c とし以下の操作を行う
    • ed=1 mod φ となる d を計算する。m=c^d mod n が元の平文となる

ある e と m について m^e mod n=m となることがある。以下,m^e mod n=m となる m を公然の平文と呼ぶ。

公開鍵の一部 e を選ぶときには, 公然の平文が多くならないことが重要である。たとえば p = 19, q = 37 とする。このとき n = 19 x 37 = 703 であり,φ = 18 x 36 = 648 である。e = 181 とすると gcd(181, 648) = 1 であるが,すべての平文 m (0≤m≤n-1) が公然の平文となってしまう。e をどのように選んでも,必ずいくつかは公然の平文が存在する。

p = 1009, q = 3643 とする。このとき,公然の平文の個数が最小となるすべての e の総和を求めよ。
1< e< φ(1009, 3643) かつ gcd(e, φ)=1 とする。

本家:Problem 182 - Project Euler
日本語訳:Problem 187 - PukiWiki


公然の平文の個数は次の式で与えられます。証明は結構長いので省略しますが,「rsa unconcealed」などでググるとみつかります。

 \left\{1+gcd(e-1,\, p-1)\right\}  \left\{1+gcd(e-1,\, q-1)\right\}

各数の奇偶を考えると,この個数が最小になるのは次のような e を選んだときです。

 gcd(e-1,\, p-1)=gcd(e-1,\, q-1)=2