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

  • 宿題の答え
    • 答えは否。暗号化に必要な暗号化指数 e と法 p は公開しなければならないが、 e と p-1 を拡張ユークリッドアルゴリズムに入力することによって復号化指数 d が高速に求められるので、 d を秘密鍵とすることができないから。

  • 授業内容
    • 命題
           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 を秘密鍵としてこれは公開鍵暗号になる。

    • 高速べき乗法（反復2乗法）
      • RSA暗号の計算に必要な xe % n の計算は、このままでは天文学的な時間とメモリを必要とする。 次のように2乗計算を巧みに用いることにより高速化しよう： 
        入力：x, e, n
出力：x ** e % n
y = 1
while e > 0:
    if e % 2 == 1:
        y = (y * x) % n
    x = (x * x) % n
    e /= 2
return y
    • 破られ易い鍵
      • 有名な素数を用いたもの
      • p, q がほとんど同じビット数のもの(フェルマ法, H28年度、田中の卒業論文)
      • p-1 が小さな素因数しか持たないもの(p-1法)
      • p+1 が小さな素因数しか持たないもの(p+1法, H27年度、寺本の卒業論文)
      • 有名な素数を用いたもの etc.

  • ツボ
    • RSA暗号の解読は、素因数分解と同程度に困難である。
    • 暗号設計に必須な xe % n の計算は、2乗を巧みに使って高速化できる。
    • RSA暗号と言えども、不用意に鍵を作ると危ない。

戻る