情報セキュリティ第 06 回 大久保誠也 静岡県立大学経営情報学部 はじめに はじめに 乱数 情報演習の復習 演習 : 乱数 2/48 これまでの話と今日の内容 基礎技術 : 秘密鍵暗号方式 暗号化 ブロック暗号とストリーム暗号 公開鍵暗号方式 暗号化と認証 ハッシュ値と一方向関数 乱数 実際の実装 : 乱数 RSA 暗号の仕組み 3/48 3/63 4/48 乱数とは何か : サイコロの例 次は 何の目が出るでしょうか? 鴨川の水 双六の賽, 山法師は思うようにならない 乱数の定義 数列の中でも 過去の数列から 次の数が予想できないものを 乱数列という つまり x 1, x 2,, x t から次の x t+1 が予想できない 一般に言う 乱数 には 2 種類ある 物理乱数 : 物理的に生成した乱数 サイコロも ある種の物理乱数 疑似乱数 : 計算機が生成した乱数 厳密な乱数ではない 乱数のようなもの ( 太平記より ) 5/48 6/48
計算機と乱数 : 疑似乱数とは 計算機は 基本的に 決まったことしかしない もの 乱数のように 予想できないもの を取り扱うことはできない 計算機で使用する乱数の多くは疑似乱数 疑似乱数は 計算機が内部で計算して 乱数っぽいもの を生成したもの 疑似乱数は本当の意味での乱数にはなっていない 疑似乱数をどのように生成するか いろいろな手法が検討 提案されている 疑似乱数 : 多くの場合の例 多くの疑似乱数は 種 (seed) から 乱数列を生成する 今までの値を元に 何らかのを行い 乱数を生成 単純な例 種 値 1 値 2 値 3 乱数値 1 乱数値 2 乱数値 3 7/48 8/48 疑似乱数 : 実装例 単純な生成方法では 次の値が予想できてしまう これでは 乱数としての意味をなさない 多くの実装例が存在する 線形合同法の種々のアルゴリズム UNIX の rand 関数 メルセンヌ ツイスタ Blum Blum Shub セキュリティの分野では 疑似乱数の品質が暗号の強度に密接に関わってくるので 厳格に規定されている 作り損なうとどうなるか 9/48 10/48 疑似乱数 : 線形合同法 もっとも単純な疑似乱数生成方法 t 番目の乱数は 式 x t = Ax t-1 + B (mod M) にしたがって決まる 要するに 直前の値から次の値が定まる 乱数のアルゴリズムとしては あまりよいものではなく 暗号には利用できない UNIXの古典的な 関数で利用されていた方式 疑似乱数 : 古典的な UNIX の場合 UNIX では rand 関数により乱数を利用できる UNIX で使用されていた古典的な rand 関数 x = x*1103515245+12345 (mod 2 31 31 ) ちなみに 奇数と偶数が交互に出ます 現在では さすがに改められていことが多いものの 単純なので あまり安全ではない OS によって rand 関数が利用する乱数生成アルゴリズムは異なります 11/48 12/48
疑似乱数 : 今の FreeBSD の場合 FreeBSD 8.0 の /lib/libc/stdlib/random.c より int32_t hi, lo; if (x == 0) x = 123459876; hi = x / 127773; lo = x % 127773; x = 16807 * lo - 2836 * hi; if (x < 0) x += 0x7fffffff; return (x); 13/48 物理乱数生成機 計算機内部では決まったことしかできないため 外部に接続する物理乱数生成器も販売されている 物理乱数生成 で検索してみよう 熱雑音やノイズ等を利用して 乱数を生成する 14/48 乱数と再現性 再現性がある とは 同じ乱数列を生成できるなら 再現性がある 線形合同法は種 (seed) が同じなら 同じ乱数列 種 値 1 疑似乱数は ほとんど再現性がある 物理乱数は再現性がない 再現性がある ことが重要な用途もある 値 2 値 3 乱数値 1 乱数値 2 乱数値 3 15/48 計算機と乱数 : 使用場面 乱数は多くの場面で使用される シミュレーション : モンテカルロ法等アンケートの無作為抽出 暗号 : 秘密鍵暗号の秘密鍵の生成ストリーム暗号 16/48 ストリーム暗号 17/48 ブロック暗号とストリーム暗号 一度に暗号化する量で 分類される ブロック暗号 : ある程度の長さのブロック毎に区切り その単位で暗号化 速度的にこちらの方が優位であることが多い 代表的な暗号 :DES AES ストリーム暗号 : ビット毎等の細かい単位で暗号化 その都度送るので 遅延が少ない 通信等で利用されることが多い 代表的な暗号 :RC4 18/48
暗号と乱数 : ストリーム暗号 (1) Alice から Bob に平文 p を暗号化して送りたい! ストリーム暗号の典型的なアイデア 秘密鍵 k として 種 (seed) をお互いに持つ 暗号化 : k を種とした疑似乱数を生成し 平文 p とビット毎の排他的論理和を計算することで 暗号文 c を生成 復号 : k を種とした疑似乱数を生成し 暗号文 c とビット毎の排他的論理和を計算することで 平文 p を生成 暗号と乱数 : ストリーム暗号 (2) 秘密鍵 k として 種 (seed) をお互いに持つ 暗号化 : 復号 : 平文 :001011010011 k を種とした乱数列 :011001011001 暗号文 :010010001010 暗号文 :010010001010 k を種とした乱数列 :011001011001 平文 :001011010011 19/48 20/48 暗号と乱数 : ストリーム暗号 (3) 1 種 k を鍵 2 乱数列と平文の排他的論理和を計算 hogehoge として共有しておく 2 送信 3 乱数列と暗号文の排他的論理和を計算 Bob hogehoge あsdふぁ sd Jlkj ぇ wkf 情報演習の復習 あsdふぁ sd Jlkj ぇ wkf Alice 21/48 22/48 復習の内容 リモートへの接続とteraterm teratermの使い方 シェル 基本的なコマンド emacsの使い方 コンパイルとgccの使い方 計算機と機械語 計算機言語とコンパイラ 23/48 リモートへの接続 windows EDxxxx teraterm UNIX smax リモートとやり取りするターミナルソフトウェア キーボードからの入力を送り UNIX の応答を表示する 24/48
シェル UNIXでコマンドを入力したりするところ smaxのデフォルトは sh ( ボーンシェル ) シェルの種類によって 操作方法が異なります 今日は tcsh を使ってみましょう シェルで と入力 %/> tcsh 他にも 代表的なシェルとして bash や zsh とかがあります 25/48 tcsh の便利な機能 ファイル名 ディレクトリ名の補完 ファイル名やディレクトリ名は 途中まで入力した状態で タブを押すと補完できます 候補が複数ある場合 候補の一覧が出てきます コマンドのヒストリ 上を押すと 過去に入力したコマンドが出てきます history コマンドで過去に入力したコマンドの一覧がでます 26/48 alias の利用 alias 機能を使うと コマンドに別名をつけることができます %/> alias [ 別名 ] [ コマンド ] ためしに 以下のコマンドを実行してみましょう %/> alias dir ls -Fs dir により ls Fs が実行できるようになります ls Fs の F はディレクトリ名末尾に / をつけるオプション s はファイルの容量を表示するオプション 27/48 基本的なコマンド ls: ファイルの一覧の取得 (list) mkdir: ディレクトリの作成 (make directory) cd: カレントディレクトリの変更 (change directory) rm: ファイルの削除 (remove ) rmdir: ディレクトリの削除 (remove directory) mv: ファイルの移動 (move) 28/48 emacs UNIX でよく利用されるエディタ 起動方法 : %/> emacs ファイル名 ファイル名を打たないと *scratch* が開きます *scratch* に直にテキストや C のプログラムを書かない 29/48 emacs の基本的なコマンド (1) C-x C-f : ファイルのオープン C-x C-s : ファイルの上書き保存 C-x C-w : ファイルを名前をつけて保存 C-x C-c : emacs の終了 C-[space]: 選択の開始 C-w : 選択範囲からのカット C-y : ペースト C-k : 行末まで削除 30/48
emacs の基本的なコマンド (2) C-a : カーソルを行頭に移動 C-e : カーソルを行末に移動 C-g : キャンセル C-_ : アンドゥ 計算機とは 計算機は ざっくりと言って CPUとメモリ 入出力装置からなる 計算機 入出力装置 CPU メモリ 31/48 外部とデータをやりとりする データをする データを保存する ビットとバイト 日常 人は 値 ( 数 ) は10 進数で 文字は文字として使用している 一方 計算機の内部では すべてのデータは 0,1 で管理されている 0,1 しか取り扱うことができない! また 計算機は メモリにデータを蓄えている 単位は bit 1bit 0 もしくは 1 のどちらかを保存 byte 1byte 1bit が 8 つ集まっている 昔のプログラミング 人間は 曰く " 人間語 " を話す 計算機は 2 進数しか理解できない! 昔は 人間が計算機に合わせて 2 進数を話していた 0000 0001 0002 0003 0004 計算機 了解 理解した 10001001 01101010 10111010 11011011 こういうをやりたいなぁ 人 上級言語 人間は 2 進数を会話するようにできていない! 人間が計算機に指示しやすく つまり プログラミングしやすくしたものが 上級言語 0000 0001 0002 0003 0004 計算機 了解 理解した 10001001 01101010 10111010 11011011 変換 こういうをやりたいなぁ printf() get() put() while() 人 gcc Gnu Compiler Collection Cコンパイラの実行ファイル名でもある Cのソースファイル sample.c gcc sample.c 実行ファイル a.out
本日の課題の概要 演習 : 乱数 今回は UNIX でも演習を行いますので smax にログインしてください 今回は Excel での乱数生成 UNIX 環境での 乱数生成関数 を利用した乱数列生成 線形合同法を用いた乱数列生成を行います 37/48 38/48 Excel での乱数使用 Excel には 乱数値を生成する 関数があります 種を明示的に設定することはできません 以下のことをやってみましょう 1. 数個のセルに を書く 2. 0~1 の乱数値が生成されたことを確認する 3. F9 を押すと 乱数値が更新されることを確認する UNIX での乱数値の生成 s : 乱数の種 (seed) から乱数系列を設定する関数 srand(unsigned int seed) : 乱数値を生成する関数 srand( 略 ) 1 回目の 2 回目の 3 回目の 種 値 1 値 2 値 3 39/48 乱数値 1 乱数値 2 乱数値 3 40/48 使用例 : 使用例 : 解説 #include<stdio.h> #include<stdlib.h> int main(){ int i; i; int seed = 10; コンパイルは gcc sample02.c として行う #include<stdio.h> #include<stdlib.h> srand( 略 ) 種 int main(){ int i; i; int seed = 10; seedの設定 1 回目の 2 回目の 3 回目の 値 1 値 2 値 3 乱数値 1 乱数値 2 乱数値 3 srand(seed); for(i=0;i<10;i++){ printf("%d n",); 41/48 srand(seed); for(i=0;i<10;i++){ printf("%d n",); 乱数の生成と表示 42/48
疑似乱数の式 : 線形合同法 #include<stdio.h> #include<stdlib.h> コンパイルは gcc sample03.c int main(){ int i; として行う i; int seed=10, A=1103515245,C=12345; long x; x; x=seed; for(i=0;i<10;i++){ x=a*x+c; printf("%d n",(int)(x>>16)&32767); 43/48 プログラムの説明 #include<stdio.h> #include<stdlib.h> int main(){ 各種の値の設定 int i; i; int seed=10, A=1103515245,C=12345; long x; x; 種を初期値にする x=seed; for(i=0;i<10;i++){ xをa 倍してCを足した x=a*x+c; ものを xの新しい値に printf("%d n",(int)(x>>16)&32767); xを16bit 右シフトしたものの下位 15bitを乱数値として出力 44/48 補足説明 (1) 補足説明 (2) x>>16 は何をしているのか? >> は " ビットシフト " を行う演算です ローテイトではないので 外に押し出された部分は消滅します 空いた部分には 0 が入ります 3 ビットシフトの例 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1 45/48 &32767は何をしているのか? & は " ビット毎の論理和 " を行う演算です 10 進数の32767は 2 進数だと111111111111111 (1が15 個 ) です たとえば 変数 xがあったとして &32767 は x の下位 15ビットのみを残すになります 01100100101011100101011110011011 &00000000000000000111111111111111 00000000000000000101011110011011 46/48 他の乱数生成関数 他にも drand48() random() 等の関数が利用できる インストールされていれば メルセンヌ ツイスタ等も利用できる 課題の提出 学籍番号 7 桁を seed として乱数値を 10 個生成し その結果を MS-Word もしくはテキストファイルに貼り付け 経情グループウェアから提出しなさい MS-Excel sample02.c sample03.c のそれぞれについて行うこと ファイル名は学籍番号の末尾に f をつけたものとする グループ名は H26_ 情報セキュリティ です 47/48 48/48