Python3 – random/乱数

概要

randomモジュールには、疑似乱数を発生させる関数や、コレクションからランダムな要素を選んだり、コレクションをシャッフルしてくれる関数が用意されている。

疑似乱数/random()

random()関数は、0≤r<1の範囲の一様乱数を浮動小数点で返す。

一様乱数/uniform()

uniform(a, b)は、a≤r<bの範囲の一様乱数を浮動小数点で返す。

整数乱数/randint()

randint(a, b)はa≤r<bの範囲の乱数を整数で返す。

ランダム選択/choise()

choise(c)はコレクションcからランダムな要素を一つ選んで返す。

引数に文字列を指定すると、その中から任意の位置の文字を一つ返す。

シャッフル/shuffle()

shuffle(c)はコレクションの内容をシャッフルする。イミュータブルな文字列を指定するとTypeErrorになる。

 

Python3 – 参照?

概要

Pythonで関数の受け渡しが参照渡しとされているが、改めて変数とオブジェクトの関係を含めて確認してみた。

オブジェクトの参照に関する基本的な考え方は

  • 論理値や数値も含めて全てオブジェクト
  • 変数にはインスタンスのアドレスが格納され、参照される
  • ミュータブルなオブジェクトでリテラルが同じものは共通の1つのオブジェクト
  • イミュータブルなオブジェクトはリテラルが同じでも異なるオブジェクト

関数の引数の受け渡しは

  • 仮引数は、関数が呼び出されたときに呼び出し元の実引数が指しているアドレスを受け取る
  • 関数内での参照も上記の通りで、ミュータブルなオブジェクトが対象の場合は、関数内で内容を変更すると・・・

変数からオブジェクトへの参照

数値の場合

下記のコードをまず確認する。

ある数値を変数に代入すると、その変数には数値(オブジェクト)のアドレスがセットされる。その変数の内容(アドレス)を別の変数に代入すると、新しい変数も同じアドレスをさすようになる。

次に、同じ数値を指している変数の一つに別の数値を代入すると、その変数は新しい数値オブジェクトのアドレスを指すようになる。

以下のように、同じ値の数値は1つのオブジェクトのアドレスが共有される。

数値計算の場合も、結果が同じ値なら1のオブジェクトが共有される。

変数が絡む演算でも、結果が同じ値なら同じアドレスを指す。

浮動小数点の場合、精度上少しでも異なる値は違うオブジェクトになる。

文字列の場合

数値の場合と同じで、変数は文字列オブジェクトのアドレスを指す。

異なる内容の文字列は、異なるオブジェクトとなる。

同じ内容の文字列リテラルは、異なる位置で用いられても1つのオブジェクトとして共有される。

面白いことに、文字列リテラル同士の演算結果が同じなら、これも同じオブジェクトとして共有される。

同じオブジェクトを指していても、一方に演算を施すと新たなオブジェクトが生成されるため、異なるオブジェクトを指すようになる。

なお、リテラル同士の演算で結果が同じ場合はオブジェクトが共有されたが、変数が絡む場合は、内容が同じであっても異なるオブジェクトとなる。

リストの場合

リストの場合もオブジェクトへの参照が変数に保存される。

リストの要素を変更した場合、そのリストを指している全ての変数に変更結果が反映される。

注意点。リストの場合、リテラルが同じでも異なるオブジェクトが生成される。

オブジェクトが異なるため、片方の変更は他方に反映されない。

関数の引数の参照

数値の場合

関数の仮引数に実数値を渡す場合、関数内で引数の値を変更しても(参照するアドレスが変更されても)呼び出し元の実引数のアドレスは変わらず、その値も変更されない。

Cと同じ仕様で、関数実行時に実引数の値がコピーされて渡されているのではないか。

文字列の場合

文字列の場合も、関数内での変更は呼び出し元に影響を与えない。

リストの場合

リストを引数に渡した場合、関数内での変更が呼び出し元にも影響を与える。リストのようなミュータブルオブジェクトの場合、それに対する変更は元のオブジェクトに対する変更であり、イミュータブルなオブジェクトのように新しいオブジェクトが生成されるわけではないため。

 

Python3 – キーワードと予約語

キーワード

キーワードの一覧は以下の通り。

False, None, True, and, as, assert, async, await, break, class, continue, def, del, elif, else, except, finally, for, from, global, if, import, in, is, lambda, nonlocal, not, or, pass, raise, return, try, while, with, yield

組み込み関数

このうちabs以降の一覧は以下の通り。

abs, all, any, ascii, bin, bool, breakpoint, bytearray, bytes, callable, chr, classmethod, compile, complex, copyright, credits, delattr, dict, dir, divmod, enumerate, eval, exec, exit, filter, float, format, frozenset, getattr, globals, hasattr, hash, help, hex, id, input, int, isinstance, issubclass, iter, len, license, list, locals, map, max, memoryview, min, next, object, oct, open, ord, pow, print, property, quit, range, repr, reversed, round, set, setattr, slice, sorted, staticmethod, str, sum, super, tuple, type, vars, zip

 

公開鍵と秘密鍵

暗号化

暗号化の流れ

公開鍵(public key)と秘密鍵(secret/private key)を使った暗号化の流れは以下のとおり。

  1. 受信側が公開鍵と秘密鍵を準備し、公開鍵を公開
  2. 送信側は公開鍵を使って平文を暗号化し、受信側に送信
  3. 受信側は秘密鍵を使って暗号文を平文に復号(秘密鍵を持っている受信側しか複合できない)

この手順を、もう少し詳しく見ると以下のとおり。

  1. 受信側が、公開鍵として(p, n)、秘密鍵として(s, n)を準備し、公開鍵を公開する
  2. 送信側は、公開鍵を使って平文(plaintext)を暗号化し、暗号文(ciphertext)を生成、受信側に送信
    • T_c = T_p^p \mod n
  3. 受信側は、受け取った暗号文を秘密鍵を使って複合
    • T_p = T_c^s \mod n

公開鍵・秘密鍵の算出手順

素数の組の準備

まず、受信側で2つの素数q, rを準備する。例えばq=5, r=11とする。

素数の積nの計算

次に、q, rの積を計算し、その値をnとする。

(1)    \begin{equation*} n = qr \end{equation*}

例えばn=5 \times 11 = 55

計算準備

q-1, r-1の最小公倍数を計算しておく。

(2)    \begin{equation*} L = LCM(p-1, q-1) \end{equation*}

例えば、L = LCM(4, 10) = 20

公開鍵の計算

p, Lが互いに素であるようなpを選ぶ。ここで公開鍵は(p, n)となる。

(3)    \begin{equation*} p \; : \; GCM(p, L) = 1 \end{equation*}

例えば、p = 3とすると、公開鍵は(3, 55)

秘密鍵の計算

(4)    \begin{equation*} s \; : \; sp \mod L = 1 \end{equation*}

例えば、e = 7とすると、3 \times 7 \mod 20 = 1となり、秘密鍵は(7, 55)

簡略化した暗号化の例

鍵の準備

先の公開鍵・秘密鍵の算出で例示した値を使って、暗号化の流れを見てみる。

2つの素数の組p=5, q=11を準備し、n = pq = 5 \times 11 = 55を計算した。

さらにLCM(q-1, r-1)の値から、公開鍵(p, n)、秘密鍵(s, n)を以下の様に得た。

(5)    \begin{eqnarray*} (p, n) &=& (3, 55) \\ (s, n) &=& (7, 55) \end{eqnarray*}

暗号化

平文として数列12, 26, 33を考え、送信側で公開鍵を使って、この平文を暗号化する。

(6)    \begin{eqnarray*} 12 &\rightarrow& 12^p \mod n = 12^3 \mod 55 = 1728 \mod 55 = 23\\ 26 &\rightarrow& 26^p \mod n = 26^3 \mod 55 = 17576 \mod 55 = 31 \\ 33 &\rightarrow& 33^p \mod n = 33^3 \mod 55 = 35937 \mod 55 = 22 \end{eqnarray*}

復号

受信側は受け取った暗号文を、秘密鍵を使って複合する。

(7)    \begin{eqnarray*} 23 &\rightarrow& 23^s \mod n = 23^7 \mod 55 = 3404825447 \mod 55 = 12\\ 31 &\rightarrow& 31^s \mod n = 31^7 \mod 55 = 27512614111 \mod 55 =  26\\ 22 &\rightarrow& 22^s \mod n = 22^7 \mod 55 = 2494357888 \mod 55 = 33 \end{eqnarray*}

電子証明

電子証明の流れ

公開鍵と秘密鍵を使う順序を逆にすると、電子証明に仕える。その流れは以下のとおり。

  1. 発信側が公開鍵と秘密鍵を準備し、公開鍵を公開
  2. 発信側は秘密鍵を使って平文を暗号化し、受信側に送信
  3. 受信側は公開鍵を使って暗号文を平文に復号し、証明を確認(秘密鍵を持っている発信側しか公開鍵で正しい平文に復号可能な暗号文を生成できない)

簡略化した電子証明の例

暗号化の例と同じ公開鍵・秘密鍵を使って、電子証明の例を確認する。

証明書の暗号化

発信側で証明書の平文12, 26, 33を準備し、これを秘密鍵を使って暗号化。

(8)    \begin{eqnarray*} 12 &\rightarrow& 12^s \mod n = 12^7 \mod 55 = 35831808 \mod 55 = 23\\ 26 &\rightarrow& 26^s \mod n = 26^7 \mod 55 = 8031810176 \mod 55 = 16 \\ 33 &\rightarrow& 33^s \mod n = 33^7 \mod 55 = 42618442977 \mod 55 = 22 \end{eqnarray*}

受信側は、公開鍵を使って暗号文を復号し、平文を確認(秘密鍵で暗号化した文のみ、公開鍵で適正に複合できる)。

(9)    \begin{eqnarray*} 23 &\rightarrow& 23^p \mod n = 23^3 \mod 55 = 12167 \mod 55 = 12\\ 16 &\rightarrow& 16^p \mod n = 16^3 \mod 55 = 4096 \mod 55 = 26 \\ 22 &\rightarrow& 22^p \mod n = 22^3 \mod 55 = 10648 \mod 55 = 33 \end{eqnarray*}

 

ハッシュ

ハッシュ関数のことを考えてみようと、自分なりにトライしてみた。

簡単すぎる例
文字列の文字コードを足し込んでいくという単純な方法。

剰余を使った例
剰余を使った例。文字列が短い場合はある程度の長さに拡張して、キーとなる数で割った余りをハッシュとしている。

 

ハッシュ – 剰余を使った例

考え方

以下のように考える。

  • 文字列を文字コード化し、眺めのバッファーに先頭から収めていく
  • バッファーが余った場合は、終わりまで0x00で埋める
  • バッファー全体を一つの整数として、特定の値で割った余りを求める
  • 余りの下位で適当なバイト数の値を取り出し、ハッシュ値とする

コード全体

上記の考え方を、クラスに実装してみる。テスト用なので、引数やオーバーフローなどのチェックはしていない。

この実装例では、バッファーの長さを16バイト、ハッシュのバイト数は下位8バイトとし、余りを計算するための除数は実行時に引数として与えるようにしている。

実行結果

除数で変わる結果

これに適当な文字列と除数を与えてみる。

1文字だけ変えると、値が大きく変わり、なんとか使えそう。

簡単な文字列で除数を変えて試してみると、除数を「ややこしそうな値」にするとハッシュはばらつくが、除数の設定によっては入力文字列そのままの値が出たりする。

除数→ 0xfedcba98 0xffffffff
A 9ED40708 41000000
AA 24FECD68 41410000
AB B81E0A58 41420000
AC 4C608CB0 41430000
BA EB7C9820 42410000
BB 7FBF1A78 42420000
BC 14019CD0 42430000

除数の影響

被除数の値によって、なぜハッシュ値が単純になるのか。

たとえば10進数で以下の様な例を考える。

 \begin{array}{rcrcrcr} 0000 & = & 99 & \times & 0 & + & 0 \\ 0100 & = & 99 & \times & 10 & + & 10 \\ 0200 & = & 99 & \times & 20 & + & 20 \\ & \vdots \\ 9000 & = & 99 & \times & 90 & + & 90 \\ 9100 & = & 99 & \times & 91 & + & 91 \\ & \vdots \\ 9800 & = & 99 & \times & 98 & + & 98 \\ 9900 & = & 99 & \times & 100 & + & 0 \\ \end{array}

除数未満の値が余りに出ているが、上位桁のパターンがそのまま順番に現れており、先の2進数と同じ結果となっている。

そこで、より簡単な例を考えてみる。

以下の表は、左の列が被除数で、それらに対して最上段の除数で割ったときの余りを示している。被除数の1/2の桁の除数では、7あたりが最も結果がばらつき、その他の値では単純な余りの値が繰り返される。

 \begin{array}{r|ccccccccc} & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 10 & 1 & 2 & 3 & 4 & 0 & 2 & 1 & 0 & 0 \\ 20 & 2 & 4 & 6 & 2 & 0 & 0 & 2 & 0 & 0 \\ 30 & 3 & 6 & 2 & 0 & 0 & 2 & 0 & 0 & 0 \\ 40 & 4 & 0 & 5 & 4 & 0 & 0 & 1 & 0 & 0 \\ 50 & 5 & 2 & 1 & 2 & 0 & 2 & 2 & 0 & 0 \\ 60 & 6 & 4 & 4 & 0 & 0 & 0 & 0 & 0 & 0 \\ 70 & 7 & 6 & 0 & 4 & 0 & 2 & 1 & 0 & 0 \\ 80 & 8 & 0 & 3 & 2 & 0 & 0 & 2 & 0 & 0 \\ 90 & 0 & 2 & 6 & 0 & 0 & 2 & 0 & 0 & 0 \\ \end{array}

これを細分化すると、余りの値の繰り返しはより顕著であることがわかる。

 \begin{array}{r|ccccccccc} & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 0 & 0 \\ 3 & 3 & 3 & 3 & 3 & 3 & 3 & 0 & 1 & 0 \\ 4 & 4 & 4 & 4 & 4 & 4 & 0 & 1 & 0 & 0 \\ 5 & 5 & 5 & 5 & 5 & 0 & 1 & 2 & 1 & 0 \\ 6 & 6 & 6 & 6 & 0 & 1 & 2 & 0 & 0 & 0 \\ 7 & 7 & 7 & 0 & 1 & 2 & 3 & 1 & 1 & 0 \\ 8 & 8 & 0 & 1 & 2 & 3 & 0 & 2 & 0 & 0 \\ 9 & 0 & 1 & 2 & 3 & 4 & 1 & 0 & 1 & 0 \\ \end{array}

先のコードは、上記の例で言えば除数を9に設定した場合に、その結果がきれいにもとの値と同じとなることに相当する。

衝突状況のチェック

除数を変化させて、アルファベット大文字1~4文字の文字列でハッシュ値の衝突が出るか確認してみた。各文字数に対するバリエーションの数は以下の通り。

  • 1文字→26通り
  • 2文字→26*26=676通り
  • 3文字→26*26*26=17,576通り
  • 4文字→26*26*26*26=456,976通り
  • 合計、475,254通り

その結果は次の通り。

0xFEDCBA98
アルファベット1~4文字で衝突なし。

0xFEDCBA9
まだ衝突なし。

0xFEDCBA
衝突が多数発生。みな2つの文字列で衝突。たとえば
0071BB5E : [‘SZQA’, ‘ZRZW’]
003C0D52 : [‘SZQB’, ‘ZRZX’]
00065F46 : [‘SZQC’, ‘ZRZY’]
00CF8DF4 : [‘SZQD’, ‘ZRZZ’]
除数の10進値は16,702,650と文字列のバリエーションより大きいが、衝突が出始めた。

0xFFFFFFFF
意外にも衝突なし。

0xFFFFFFF
衝突が多数発生。これも2つの文字列で重複。たとえば
05A5CA5A : [‘JZZX’, ‘ZZZW’]
05A5DA5A : [‘JZZY’, ‘ZZZX’]
05A5EA5A : [‘JZZZ’, ‘ZZZY’]
除数の10進値は268,435,455とかなり大きいが、単純なパターンの値ほど衝突が起こりやすいのかもしれない。

コード詳細

コンストラクタ__init__()

  • インスタンス生成時にハッシュを生成する文字列を受け取り、空のバッファーを準備
  • バッファーの長さを16バイト、ハッシュ値の長さを8バイトに設定
  • 引数で与えられた文字列から1文字ずつ取り出し、文字コードを追加
  • バッファー長までの余った部分に0を追加

内部用メソッドget_nbytes()

文字コードを追加し終わったときのバッファー長を計算する処理を独立させたメソッド。

ハッシュ値計算get_hash()

  • バッファーの内容を整数として、引数で与えられた除数から剰余を計算する
  • 計算結果の下位バイトを取り出して、ハッシュ値として返す

文字列化メソッド__str()__

インスタンスの文字列化メソッド。

 

ハッシュ – 簡単すぎる例

ハッシュ関数のイメージを掴むために、簡単な例を考えてみる。

まず、任意の文字列が与えられたとき、文字列中の全ての文字コードを加えた値を返す関数を考える。

この関数を以下のような文字列で実行すると、1文字加えたり入れ替えただけで結果が違ってくるのがわかる。

長い文字列で試してみると、1文字入れ替えると値が変わってくるが、1文字分の足し込むコードが変わるだけなので、大きな変化は期待できない。

この方法で致命的なのは、同種の文字を順序違いで並べても結果が同じになる点。

このやり方は、あまりに単純すぎて使えない。

 

Python3 – 文字列とリストの相互変換

文字列からリストへの変換

リストから文字列への変換

リストから文字列に変換するときに、区切り文字を指定できる。

区切りは2文字以上でもok。

 

Python3 – 文字を順に取り出す

数字やアルファベットの文字を順に取り出して使いたい時、stringモジュールを使うと便利。