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