Problem 182 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 182 へ行く。
  • 1 (2008-02-28 (木) 21:28:48)

Problem 182 「RSA暗号」 †

RSA暗号は以下のアルゴリズムに基づいている:

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

さてあるeとmについてm&sup{e}; mod n=mとなることがある. 以下, m&sup{e}; mod n=mとなるmを公然の平文と呼ぶことにする.

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

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