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

  • 授業内容
    • 宿題の答え
      • 暗号化関数を公開すると、p と e を公開することになる。
      • e と p-1 を入力として拡張ユークリッドアルゴリズムを実行することにより復号化指数 d が高速に計算できる。
      • 従って前回の暗号は公開鍵暗号にはなり得ない。

    • RSA 暗号の設計
      • 命題
             p, q : 異なる素数
             n = p×q
             m : p-1 と q-1 の公倍数(公倍数なら何でも良い)
             e, d : ed ≡ 1 ( mod m ) を満たす自然数
        ならば、任意の整数 x に対して
             xed ≡ x ( mod n )

      • RSA暗号 E : P → C, D : C → P とは：
        • 平文集合　 P = {0, 1, ..., n-1}
        • 暗号文集合 C = {0, 1, ..., n-1}
        • 暗号化関数 E(x) = xe % n
        • 復号化関数 D(y) = yd % n

      • 命題
        n と e を知っている者にとって、次のことは計算量的に同値：
        • n の素因数 p, q を知ること
        • p-1 と q-1 の公倍数 m をひとつ知ること
        • 復号化指数 d を知ること

      • n, e を公開鍵、p, q, m, d を秘密鍵としてこれは公開鍵暗号になる。

    • 破られ易い鍵
      • 有名な素数を用いたもの
      • p, q がほとんど同じビット数のもの(フェルマ法)
      • p-1 が小さな素因数しか持たないもの(p-1法)
      • p+1 が小さな素因数しか持たないもの(p+1法)
      • p-1 と q-1 の最大公約数が大きいもの etc.

    • サンプルプログラム
  • ツボ
    • 設計者・正規ユーザの行う計算は高速
      • 素数生成 O(log4)
      • 暗号化指数、復号化指数の生成 O(log2)
      • 暗号化、復号化 O(log3)

    • 公開鍵のみから復号化指数を求める計算量は膨大
      • 素因数分解問題と同等
      • 不注意な鍵生成によって復号化指数が高速に計算できることもある

  • 宿題
    • RSA暗号の鍵 p, q, n, e, d を、n が 1024 ビット程度になるように生成し、 公開鍵 n, e を塩田に送信せよ。秘密鍵は各自保管しておくこと。
    • メールは ここ から。

戻る