情報セキュリティ第10回

(1)

情報セキュリティ第10回

大久保誠也静岡県立大学経営情報学部

2/48

はじめに

 はじめに

 乱数

 情報処理演習の復習

 演習：乱数

3/48 3/63

これまでの話と今日の内容

 基礎技術：

秘密鍵暗号方式

暗号化

ブロック暗号とストリーム暗号

公開鍵暗号方式

暗号化と認証

ハッシュ値と一方向関数

乱数

 実際の実装：

RSA暗号の仕組み _4/48

乱数

乱数とは何か：サイコロの例

 次は、何の目が出るでしょうか？

 「鴨川の水、双六の賽，山法師は思うようにならない」

乱数の定義

 数列の中でも、過去の数列から、次の数が予想できないものを、乱数列という。

 つまり、x₁

, x

₂

, … , x

_tから次のx_t+1が予想できない。

 一般に言う

“

乱数

”

には種類ある。

 物理乱数：

物理的に生成した乱数。

サイコロも、ある種の物理乱数。

 疑似乱数：

計算機が生成した乱数。

厳密な乱数ではない。乱数のようなもの。

(2)

7/48

計算機と乱数：疑似乱数とは

 計算機は、基本的に「決まったことしかしない」もの。

 乱数のように「予想できないもの」を取り扱うことはできない。

 計算機で使用する乱数の多くは疑似乱数。

 疑似乱数は、計算機が内部で計算して「乱数っぽいもの」を生成したもの。

 疑似乱数は本当の意味での乱数にはなっていない。

 疑似乱数をどのように生成するか、いろいろな手法が検討・提案されている。

8/48

疑似乱数：多くの場合の例

 多くの疑似乱数は、種（seed）から、乱数列を生成する。

 今までの値を元に、何らかの処理を行い、乱数を生成。

単純な例

種 ^処理値1 ^処理値2 ^処理値3 …

乱数値1 乱数値2 乱数値3

処理処理処理

…

9/48

疑似乱数：実装例

 単純な生成方法では、次の値が予想できてしまう。

→ これでは、乱数としての意味をなさない。

 多くの実装例が存在する。

 線形合同法の種々のアルゴリズム



UNIXのrand関数

 メルセンヌ・ツイスタ



Blum Blum Shub

 セキュリティの分野では、疑似乱数の品質が暗号の強度に密接に関わってくるので、厳格に規定されている。

10/48

作り損なうとどうなるか

11/48

疑似乱数：線形合同法

 もっとも単純な疑似乱数生成方法。

 t 番目の乱数は、式

x_t

= A x

_t-1+ B （

mod M

）にしたがって決まる。

要するに、直前の値から次の値が定まる。

 乱数のアルゴリズムとしては、あまりよいものではなく、暗号には利用できない。



UNIXの古典的な rand() 関数で利用されていた方式。

12/48

疑似乱数：古典的な UNIX の場合



UNIX

では、

rand

関数により乱数を利用できる。



UNIX

で使用されていた古典的な

rand

関数

ちなみに、奇数と偶数が交互に出ます。

 現在では、さすがに改められていことが多いものの、

単純なので、あまり安全ではない。



OS

によって

rand

関数が利用する乱数生成アルゴリズムは異なります。

x = x*1103515245+12345 (mod 2

³¹

)

x = x*1103515245+12345 (mod 2

³¹

)

(3)

13/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より

14/48

物理乱数生成機

 計算機内部では決まったことしかできないため、外部に接続する物理乱数生成器も販売されている。

「物理乱数生成」で検索してみよう。

近頃だと、CPUに内蔵されている場合もある

 熱雑音やノイズ等を利用して、乱数を生成する。

15/48

乱数と再現性

 「再現性がある」とは

同じ乱数列を生成できるなら「再現性がある」。

線形合同法は種（seed）が同じなら、同じ乱数列。

疑似乱数は、ほとんど再現性がある。

物理乱数は再現性がない。

 「再現性がある」ことが重要な用途もある。

種処理

値1 処理

値2 処理

値3 …

処理処理処理

…

16/48

計算機と乱数：使用場面

 乱数は多くの場面で使用される。

シミュレーション：

モンテカルロ法等アンケートの無作為抽出

暗号：

秘密鍵暗号の秘密鍵の生成ストリーム暗号

ストリーム暗号

ブロック暗号とストリーム暗号

一度に暗号化する量で、分類される。

ブロック暗号：

ある程度の長さのブロック毎に区切り、その単位で暗号化。

処理速度的にこちらの方が優位であることが多い。

代表的な暗号：DES、AES

ストリーム暗号：

ビット毎等の細かい単位で暗号化。

その都度送るので、遅延が少ない。通信等で利用されることが多い。

代表的な暗号：RC4

(4)

19/48

暗号と乱数：ストリーム暗号 (1)



Alice

から

Bob

に平文pを暗号化して送りたい！

 ストリーム暗号の典型的なアイデア

 秘密鍵k として、種（

seed

）をお互いに持つ

 暗号化：

kを種とした疑似乱数を生成し、平文p とビット毎の 排他的論理和を計算することで、暗号文c を生成。

 復号：

k を種とした疑似乱数を生成し、暗号文c とビット毎の排他的論理和を計算することで、平文p を生成。

20/48

暗号と乱数：ストリーム暗号 (2)

 秘密鍵k として、種（

seed

）をお互いに持つ

 暗号化：

 復号：

平文：001011010011 kを種とした乱数列：011001011001 暗号文：010010001010 暗号文：010010001010 kを種とした乱数列：011001011001 平文：001011010011

21/48 hogehoge

Alice

Bob

② 送信

あｓｄふぁｓｄＪｌｋｊぇｗｋｆ

③ 乱数列と暗号文の排他的論理和を計算。

hogehoge

あｓｄふぁｓｄＪｌｋｊぇｗｋｆ

② 乱数列と平文の排他的論理和を計算。

暗号と乱数：ストリーム暗号(3)

① 種kを鍵として共有しておく

22/48

演習：乱数

23/48

本日の課題の概要

 今回は、



Excelでの乱数生成



Excelで組んでみる線形合同法



repl.it環境での

乱数生成関数rand()を利用した乱数列生成

線形合同法を用いた乱数列生成を行います。

24/48

Excel での乱数使用



Excelには、乱数値を生成する rand() 関数がありま

す。

 種を明示的に設定することはできません。

 以下のことをやってみましょう 1. 数個のセルに

rand() を書く。

2.

0～1の乱数値が生成されたことを確認する

3.

F9 を押すと、乱数値が

更新されることを確認する。

(5)

25/48

やってみる線形合同法 (1)

 以下をExcelでやってみる

種 ^処理値1 ^処理値2 ^処理値3 …

処理処理処理

…

1103515245倍して12345を足した結果を、

2

³²で割った余り

右に16ビットシフトして、下位16ビットを切り出す _26/48

やってみる線形合同法 (2)

1. 以下のように入力する

=MOD(1103515245*B1+12345,POWER(2,32))

=BITAND(BITRSHIFT(B2,16),32767)

27/48

やってみる線形合同法(3)

2. 下にコピーする

3. 種を変えると乱数列が変わることを確認してみる

28/48

やってみる線形合同法(4)

 図との対応関係

種

処理値1 値2 値3 … 乱数値1 乱数値2 乱数値3 …



srand()

：

乱数の種（

seed

）から乱数系列を設定する関数。



rand()

：

乱数値を生成する関数。

UNIX での乱数値の生成

srand(unsigned int seed) srand(unsigned int seed)

rand() rand()

種

処理値1 値2 値3 … srand(略) 1回目の

rand() 2回目の

rand() 3回目の

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());

} }

#include<stdio.h>

#include<stdlib.h>

int main(){

int i;

int seed = 10;

srand(seed);

for(i=0;i<10;i++){

} }

repl.it

でやる

(6)

31/48

使用例：解説

#include<stdio.h>

#include<stdlib.h>

int main(){

int i;

int seed = 10;

srand(seed);

for(i=0;i<10;i++){

} }

#include<stdio.h>

#include<stdlib.h>

int main(){

int i;

int seed = 10;

srand(seed);

for(i=0;i<10;i++){

} }

seedの設定

乱数の生成と表示

種処理

値1 値2 値3 …

乱数値1 乱数値2 乱数値3 …

srand(略) 1回目の

rand() 2回目の

rand() 3回目の

rand()

32/48

Excel との対応イメージ

srand(10)

rand()

33/48

補足説明(1)



x>>16 は何をしているのか？

>> は"ビットシフト"を行う演算です。

ローテイトではないので、外に押し出された部分は消滅します。

空いた部分には0が入ります。

0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 0

3ビットシフトの例

34/48

補足説明(2)



ExcelのBITANDは何をしているのか？

BITAND は"ビット毎の論理和"を行う演算です。

10進数の32767は、2進数だと111111111111111

（1が15個）です。

たとえば、変数xがあったとして

&32767

は、

x の下位15ビットのみを残す処理になります。

&00000000000000000111111111111111 01100100101011100101011110011011 00000000000000000101011110011011

35/48

他の乱数生成関数

 他にも、

drand48()

random()

等の関数が利用できる。

 インストールされていれば、メルセンヌ・ツイスタ等も利用できる。

36/48

課題の提出

 学籍番号7桁をseedとして、Excelでやってみたのと

repl.it上で乱数値を10個生成し、その結果を0010.odt

に貼り付け、経情グループウェアから提出しなさい

 グループ名は『R3_情報セキュリティ』です。

情報セキュリティ 第10回