アルゴリズム論特論（塩田）　2014年度教材　第8回

  • 前回の復習

  • 授業内容
    • 暗号用語
    • 法べき乗暗号
      • p : 素数
      • e, d : gcd(e, p-1) = 1, ed ≡ 1 mod (p-1) を満たすべき指数
      を用いて次のように設計：
      • 平文集合 P = 暗号文集合 C = {0, 1, ..., p-1}
      • 暗号化関数 E(x) = xe % p
      • 復号化関数 D(y) = yd % p

  • ツボ
    • 設計原理はフェルマの小定理
    • 鍵 p, e, d がおおよそ n 程度の数であるとき、鍵生成の計算量は O(log4 n)
    • 暗号化・復号化の計算量は O(log3 n)
    • これは公開鍵暗号にはならない（暗号化鍵 p, e から d が計算できる）

戻る