アルゴリズム論特論（塩田）　2015年度教材

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

授業内容
- RSA 暗号の設計
- RSA 暗号には使ってはいけない危険な鍵がある
サンプルプログラム
- 関数定義部 crypto.py （以下のプログラムで import ）
- Fermat 法 FermatMethod.py
- Newton 法 NewtonMethod.py
- p-1 法 p-1Method.py / 実行例
- p+1 法 p+1Method.py / 実行例
ツボ
- 設計者・正規ユーザの行う計算は高速
  - 素数生成 O(log⁴)
  - 暗号化指数、復号化指数の生成 O(log²)
  - 暗号化、復号化 O(log³)
- 公開鍵のみから復号化指数を求める計算量は膨大
  - 素因数分解問題と同等
  - 不注意な鍵生成によって復号化指数が高速に計算できることもある
宿題

RSA暗号の公開鍵 n, e をおおよそ 1024 ビット程度で作成し、塩田宛に送信せよ。（次の宿題で塩田からの暗号文を復号してもらいますので、復号化鍵を失くさないように。）

ただし素数生成に自信の無い諸君は、以下のリンクから p, q を格納したテキストファイルをダウンロードして用いて良い。

学籍番号末尾 31 32 34 35 36 37 38 39 40 42

メールはここから。