Python3 – random/乱数

2019-08-18 / tau / コメントする

概要

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

なお、numpy.randomモジュールにも便利な乱数生成関数が準備されている。

乱数系列/seed()

random.seed()関数は、引数を指定して乱数系列を固定する。

import random

random.seed(0)

for n in range(5):
    print(random.random())

# 0.8444218515250481
# 0.7579544029403025
# 0.420571580830845
# 0.25891675029296335
# 0.5112747213686085
# 何度繰り返しても同じ値になる

import random

random.seed(0)

for n in range(5):

print(random.random())

# 0.8444218515250481

# 0.7579544029403025

# 0.420571580830845

# 0.25891675029296335

# 0.5112747213686085

# 何度繰り返しても同じ値になる

疑似乱数/random()

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

import random

for n in range(0, 5):
    print(random.random())

# 0.18356662737924279
# 0.2535975770454991
# 0.07112643912586292
# 0.9296944359969844
# 0.16323733244990823

import random

for n in range(0, 5):

print(random.random())

# 0.18356662737924279

# 0.2535975770454991

# 0.07112643912586292

# 0.9296944359969844

# 0.16323733244990823

一様乱数/uniform()

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

import random

for n in range(0, 5):
    print(random.uniform(1, 5))

# 3.6379958781920916
# 3.380738588720399
# 1.2535708428173264
# 4.802360086175415
# 2.7348909239420416

import random

for n in range(0, 5):

print(random.uniform(1, 5))

# 3.6379958781920916

# 3.380738588720399

# 1.2535708428173264

# 4.802360086175415

# 2.7348909239420416

整数乱数/randint(), randrange()

randint(a, b)はa≤r≤bの範囲の乱数を整数で返す。第2引数のbも生成されることに注意。

randrange(start, end, step)はstart≤r<stopの範囲でstep間隔の乱数を整数で返す。第2引数のstopは生成されないことに注意。stepを省略した場合は1となる。

import random

for n in range(20):
    print(random.randint(0, 2), end=" ")

for n in range(20):
    print(random.randrange(0, 6, 2), end=" ")

# 0 2 2 1 1 2 1 1 1 1 1 2 2 1 0 0 2 1 2 1
# 2 2 4 4 2 0 4 0 2 4 2 2 2 0 4 2 4 4 2 0

import random

for n in range(20):

print(random.randint(0, 2), end=" ")

for n in range(20):

print(random.randrange(0, 6, 2), end=" ")

# 0 2 2 1 1 2 1 1 1 1 1 2 2 1 0 0 2 1 2 1

# 2 2 4 4 2 0 4 0 2 4 2 2 2 0 4 2 4 4 2 0

ランダム選択/choise()

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

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']
for n in range(0, 5):
    print(random.choice(cities))

# Kobe
# Nagoya
# Yokohama
# Sapporo
# Yokohama

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']

for n in range(0, 5):

print(random.choice(cities))

# Kobe

# Nagoya

# Yokohama

# Sapporo

# Yokohama

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

import random

a_string = 'ABCDEFG'
for n in range(0, 5):
    print(random.choice(a_string))

# D
# C
# E
# D
# B

import random

a_string = 'ABCDEFG'

for n in range(0, 5):

print(random.choice(a_string))

# D

# C

# E

# D

# B

シャッフル/shuffle()

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

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']
random.shuffle(cities)
print(cities)

# ['Nagoya', 'Kobe', 'Fukuoka', 'Osaka', 'Yokohama', 'Sapporo']

import random

cities = ['Yokohama', 'Osaka', 'Nagoya','Sapporo', 'Fukuoka', 'Kobe']

random.shuffle(cities)

print(cities)

# ['Nagoya', 'Kobe', 'Fukuoka', 'Osaka', 'Yokohama', 'Sapporo']

Python3 – オブジェクトへの参照

2019-08-18 / tau / コメントする

概要

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

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

論理値や数値も含めて全てオブジェクト
変数にはインスタンスのアドレスが格納され、参照される
数値や文字列などイミュータブルなオブジェクトの場合、リテラルの表現が同じものは共通の1つのインスタンスとなる
リストなどミュータブルなオブジェクトは、インスタンスの内容が変更されても参照先は変わらない(逆に言えば、参照先が変わらないのに内容が変更されている可能性がある)

関数の引数の受け渡しは

仮引数は、関数が呼び出し時には元のオブジェクトへの参照を指しているが、イミュータブルオブジェクトが変更された場合は参照先が変わり、呼び出し元の引数に影響を与えない
引数の参照先がミュータブルオブジェクトの場合、インスタンスの内容が変更されても参照先は変わらず、呼び出し元の内容も変更される

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

数値の場合

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

a = 1
b = a
c = b

print('a={}, b={}, c={}'.format(a, b, c))
print('$a={}, $b={}, $c={}'.format(id(a), id(b), id(c)))

# a=1, b=1, c=1
# $a=1943168176, $b=1943168176, $c=1943168176
# 3つの変数の値は等しく、参照番地は同じ

a = 1

b = a

c = b

print('a={}, b={}, c={}'.format(a, b, c))

print('$a={}, $b={}, $c={}'.format(id(a), id(b), id(c)))

# a=1, b=1, c=1

# $a=1943168176, $b=1943168176, $c=1943168176

# 3つの変数の値は等しく、参照番地は同じ

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

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

b = 2

# a=1, b=2, c=1
# $a=1943168176, $b=1943168192, $c=1943168176
# bに新しい値をセットすると、参照番地も変わる
# a, cの値、参照番地は変化しない

b = 2

# a=1, b=2, c=1

# $a=1943168176, $b=1943168192, $c=1943168176

# bに新しい値をセットすると、参照番地も変わる

# a, cの値、参照番地は変化しない

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

c = 2

# a=1, b=2, c=2
# $a=1943168176, $b=1943168192, $c=1943168192
# cにbと同じ値をセットすると、値・参照番地とも同じになる

c = 2

# a=1, b=2, c=2

# $a=1943168176, $b=1943168192, $c=1943168192

# cにbと同じ値をセットすると、値・参照番地とも同じになる

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

a = 3 * 4
b = 2 * 6

# a=12, b=12
# $a=1943168352, $b=1943168352
a# 計算過程に関わらず、計算結果が同じなら同じ番地を参照

a = 3 * 4

b = 2 * 6

# a=12, b=12

# $a=1943168352, $b=1943168352

a# 計算過程に関わらず、計算結果が同じなら同じ番地を参照

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

x = 3
a = x * 4
b = 2 * 2 * x

# a=12, b=12
# $a=1943168352, $b=1943168352
# 変数が絡む場合でも計算結果が同じならオブジェクトも同じ

x = 3

a = x * 4

b = 2 * 2 * x

# a=12, b=12

# $a=1943168352, $b=1943168352

# 変数が絡む場合でも計算結果が同じならオブジェクトも同じ

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

a = 1.0 / 3
b = 10 / 3 - 3

# a=0.3333333333333333, b=0.3333333333333335
# $a=62840080, $b=62839984
# 浮動小数点の場合、必ずしも予想した同じ値とならない場合がある

a = 1.0 / 3

b = 10 / 3 - 3

# a=0.3333333333333333, b=0.3333333333333335

# $a=62840080, $b=62839984

# 浮動小数点の場合、必ずしも予想した同じ値とならない場合がある

文字列の場合

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

a = 'AA'
b = a

# a=AA, b=AA
# $a=67099680, $b=67099680
# 同じ文字列オブジェクトを参照

a = 'AA'

b = a

# a=AA, b=AA

# $a=67099680, $b=67099680

# 同じ文字列オブジェクトを参照

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

b = 'AB'

# a=AA, b=AB
# $a=67099680, $b=67099776
# 新たな文字列は新たなオブジェクトとして生成され参照される

b = 'AB'

# a=AA, b=AB

# $a=67099680, $b=67099776

# 新たな文字列は新たなオブジェクトとして生成され参照される

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

a = 'AB'

# a=AB, b=AB
# $a=67099776, $b=67099776
# 同じ内容の文字リテラルは同じオブジェクトとして参照される

a = 'AB'

# a=AB, b=AB

# $a=67099776, $b=67099776

# 同じ内容の文字リテラルは同じオブジェクトとして参照される

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

b = 'A' + 'B'

# a=AB, b=AB
# $a=67099776, $b=67099776
# 文字列リテラルの演算結果が同じ内容なら同一のオブジェクト

b = 'A' + 'B'

# a=AB, b=AB

# $a=67099776, $b=67099776

# 文字列リテラルの演算結果が同じ内容なら同一のオブジェクト

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

a += 'C'

# a=ABC, b=AB
# $a=67172064, $b=67099776
# 文字列に変更があると新たな別のオブジェクトになる

a += 'C'

# a=ABC, b=AB

# $a=67172064, $b=67099776

# 文字列に変更があると新たな別のオブジェクトになる

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

x = 'A'
a = x + 'B'
b = x + 'B'

# a=AB, b=AB
# $a=67172608, $b=67172064
# 結果が同じでもリテラルのみでない演算の場合は異なるオブジェクト

x = 'A'

a = x + 'B'

b = x + 'B'

# a=AB, b=AB

# $a=67172608, $b=67172064

# 結果が同じでもリテラルのみでない演算の場合は異なるオブジェクト

リストの場合

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

a = [0, 1, 2]
b = a

# a=[0, 1, 2], b=[0, 1, 2]
# $a=66799096, $b=66799096
# 同じリストを参照

a = [0, 1, 2]

b = a

# a=[0, 1, 2], b=[0, 1, 2]

# $a=66799096, $b=66799096

# 同じリストを参照

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

a[0] = 1

# a=[1, 1, 2], b=[1, 1, 2]
# $a=66799096, $b=66799096
# 同じリストを参照しているので変更結果も参照先に反映

a[0] = 1

# a=[1, 1, 2], b=[1, 1, 2]

# $a=66799096, $b=66799096

# 同じリストを参照しているので変更結果も参照先に反映

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

a = [0, 1, 2]
b = [0, 1, 2]

# a=[0, 1, 2], b=[0, 1, 2]
# $a=67159624, $b=67158704
# リストの場合、同じリテラル表現でも異なるオブジェクトになる

a = [0, 1, 2]

b = [0, 1, 2]

# a=[0, 1, 2], b=[0, 1, 2]

# $a=67159624, $b=67158704

# リストの場合、同じリテラル表現でも異なるオブジェクトになる

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

a[0] = 1

# a=[1, 1, 2], b=[0, 1, 2]
# $a=67159624, $b=67158704
# リストの内容を変化させても参照番地は変わらない
# 異なるオブジェクトのため、変更は波及しない

a[0] = 1

# a=[1, 1, 2], b=[0, 1, 2]

# $a=67159624, $b=67158704

# リストの内容を変化させても参照番地は変わらない

# 異なるオブジェクトのため、変更は波及しない

関数の引数の参照

数値の場合

関数の引数に数値を渡す場合の流れは以下の通り。

仮引数は引数と同じオブジェクトを指す
関数内で引数が変更されると、新たなオブジェクトを指すようになる
その結果、仮引数に渡した変数は変更されない

def func_num(arg):
    print('arg_before={}, id={}'.format(arg, id(arg)))
    arg +=1
    print('arg_after={}, id={}'.format(arg, id(arg)))
    return arg

var = 1
print('variable={}, id={}'.format(var, id(var)))
result = func_num(var)

print('result={}, id={}'.format(result, id(result)))
print('variable={}, id={}'.format(var, id(var)))

# variable=1, id=1943037104
# arg_before=1, id=1943037104
# arg_after=2, id=1943037120
# result=2, id=1943037120
# variable=1, id=1943037104
# 引数は、数値への参照で渡される
# 関数内で異なる値にセットされると引数の参照番地が変わる
# しかし、その結果は呼び出し元の実引数に影響しない

def func_num(arg):

print('arg_before={}, id={}'.format(arg, id(arg)))

arg +=1

print('arg_after={}, id={}'.format(arg, id(arg)))

return arg

var = 1

print('variable={}, id={}'.format(var, id(var)))

result = func_num(var)

print('result={}, id={}'.format(result, id(result)))

print('variable={}, id={}'.format(var, id(var)))

# variable=1, id=1943037104

# arg_before=1, id=1943037104

# arg_after=2, id=1943037120

# result=2, id=1943037120

# variable=1, id=1943037104

# 引数は、数値への参照で渡される

# 関数内で異なる値にセットされると引数の参照番地が変わる

# しかし、その結果は呼び出し元の実引数に影響しない

文字列の場合

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

def func_str(arg):
    print('arg_before={}, id={}'.format(arg, id(arg)))
    arg += 'X'
    print('arg_after={}, id={}'.format(arg, id(arg)))
    return arg

var = 'ABC'
print('variable={}, id={}'.format(var, id(var)))
result = func_str(var)

print('result={}, id={}'.format(result, id(result)))
print('variable={}, id={}'.format(var, id(var)))

# variable=ABC, id=72144960
# arg_before=ABC, id=72144960
# arg_after=ABCX, id=72220064
# result=ABCX, id=72220064
# variable=ABC, id=72144960
# 数値の場合と同じで、引数は参照渡しだが呼び出し元の変数は変更されない

def func_str(arg):

print('arg_before={}, id={}'.format(arg, id(arg)))

arg += 'X'

print('arg_after={}, id={}'.format(arg, id(arg)))

return arg

var = 'ABC'

print('variable={}, id={}'.format(var, id(var)))

result = func_str(var)

print('result={}, id={}'.format(result, id(result)))

print('variable={}, id={}'.format(var, id(var)))

# variable=ABC, id=72144960

# arg_before=ABC, id=72144960

# arg_after=ABCX, id=72220064

# result=ABCX, id=72220064

# variable=ABC, id=72144960

# 数値の場合と同じで、引数は参照渡しだが呼び出し元の変数は変更されない

リストの場合

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

元のインスタンスに影響を波及させたくない場合はコピー、ディープコピーを使う。

def func_list(arg):
    print('arg_before={}, id={}'.format(arg, id(arg)))
    arg.append(0)
    print('arg_after={}, id={}'.format(arg, id(arg)))
    return arg
var = [3, 2, 1]
print('variable={}, id={}'.format(var, id(var)))
result = func_list(var)

print('result={}, id={}'.format(result, id(result)))
print('variable={}, id={}'.format(var, id(var)))

# variable=[3, 2, 1], id=71845368
# arg_before=[3, 2, 1], id=71845368
# arg_after=[3, 2, 1, 0], id=71845368
# result=[3, 2, 1, 0], id=71845368
# variable=[3, 2, 1, 0], id=71845368
# リストの場合は内容が変化しても参照は変更されないので
# 呼び出し元の変数が影響を受ける

def func_list(arg):

print('arg_before={}, id={}'.format(arg, id(arg)))

arg.append(0)

print('arg_after={}, id={}'.format(arg, id(arg)))

return arg

var = [3, 2, 1]

print('variable={}, id={}'.format(var, id(var)))

result = func_list(var)

print('result={}, id={}'.format(result, id(result)))

print('variable={}, id={}'.format(var, id(var)))

# variable=[3, 2, 1], id=71845368

# arg_before=[3, 2, 1], id=71845368

# arg_after=[3, 2, 1, 0], id=71845368

# result=[3, 2, 1, 0], id=71845368

# variable=[3, 2, 1, 0], id=71845368

# リストの場合は内容が変化しても参照は変更されないので

# 呼び出し元の変数が影響を受ける

Python3 – キーワードと予約語

2019-08-17 / tau / コメントする

キーワード

>>> import keyword
>>> for s in keyword.kwlist: print(s)
...
False
None
True
and
as
.....
with
yield

>>> import keyword

>>> for s in keyword.kwlist: print(s)

...

False

None

True

and

.....

with

yield

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

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

組み込み関数

>>> for s in dir(__builtins__): print(s)
...
ArithmeticError
AssertionError
......
_
__build_class__
__debug__
.....
abs
all
.....
vars
zip

>>> for s in dir(__builtins__): print(s)

...

ArithmeticError

AssertionError

......

__build_class__

__debug__

.....

abs

all

.....

vars

zip

このうち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

公開鍵と秘密鍵

2019-08-15 / tau / コメントする

暗号化

暗号化の流れ

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

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

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

受信側が、公開鍵として $(p, n)$ 、秘密鍵として $(s, n)$ を準備し、公開鍵を公開する
送信側は、公開鍵を使って平文(plaintext)を暗号化し、暗号文(ciphertext)を生成、受信側に送信
- $T_c = T_p^p \mod n$
受信側は、受け取った暗号文を秘密鍵を使って複合
- $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*}$

電子証明

電子証明の流れ

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

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

簡略化した電子証明の例

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

証明書の暗号化

発信側で証明書の平文 $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*}$

ハッシュ

2019-08-15 / tau / コメントする

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

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

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

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

2019-08-15 / tau / コメントする

考え方

以下のように考える。

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

コード全体

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

class Hash1():
    """簡単なハッシュを生成するクラス"""

    def __init__(self, st):
        """
        コンストラクター
        引数
        - st：ハッシュ生成対象文字列
        内容
        - 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定
        - 文字列の各文字の文字コードをバッファーの背等から格納

        """
        self.buf = 0
        self.buf_length = 16  # バッファーは16バイト
        self.hash_length = 8  # ハッシュ値は8バイト

        # 文字列中の文字のコードをバッファーに加えていく
        for c in st:
            self.buf <<= 8
            self.buf += ord(c)

        # 文字コードを埋めた後のバッファーのバイト数
        nbytes = self.get_nbytes()

        # バッファーの残り領域を0で埋める
        for n in range(0, self.buf_length - nbytes):
            self.buf = (self.buf << 8) + 0x00

    def __str__(self):
        """インスタンスの文字列化メソッド"""
        return format(self.buf, '0x')

    def get_hash(self, mod_key):
        """
        ハッシュを生成するメソッド
        引数
        - 剰余計算の被除数
        内容
        - バッファーの内容を整数とみなして剰余を計算
        戻り値
        - 16進表示の文字列によるハッシュ値(バイト数を調整)
        """
        hash_value = (self.buf % mod_key)
        return format(hash_value, '0'+str(self.hash_length)+'X')

    def get_nbytes(self):
        """現在のバッファーのバイト数を返すメソッド"""
        bf = self.buf
        nbytes = 0
        while bf != 0:
            nbytes += 1
            bf >>= 8
        return nbytes

class Hash1():

"""簡単なハッシュを生成するクラス"""

def __init__(self, st):

"""

コンストラクター

引数

- st：ハッシュ生成対象文字列

内容

- 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定

- 文字列の各文字の文字コードをバッファーの背等から格納

"""

self.buf = 0

self.buf_length = 16 # バッファーは16バイト

self.hash_length = 8 # ハッシュ値は8バイト

# 文字列中の文字のコードをバッファーに加えていく

for c in st:

self.buf <<= 8

self.buf += ord(c)

# 文字コードを埋めた後のバッファーのバイト数

nbytes = self.get_nbytes()

# バッファーの残り領域を0で埋める

for n in range(0, self.buf_length - nbytes):

self.buf = (self.buf << 8) + 0x00

def __str__(self):

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

return format(self.buf, '0x')

def get_hash(self, mod_key):

"""

ハッシュを生成するメソッド

引数

- 剰余計算の被除数

内容

- バッファーの内容を整数とみなして剰余を計算

戻り値

- 16進表示の文字列によるハッシュ値(バイト数を調整)

"""

hash_value = (self.buf % mod_key)

return format(hash_value, '0'+str(self.hash_length)+'X')

def get_nbytes(self):

"""現在のバッファーのバイト数を返すメソッド"""

bf = self.buf

nbytes = 0

while bf != 0:

nbytes += 1

bf >>= 8

return nbytes

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

実行結果

除数で変わる結果

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

h = Hash1("My fair lady")
print(h)
print(h.get_hash(0xfedcba98))

# 4d792066616972206c61647900000000
# 723C2FC8

h = Hash1("My fair lady")

print(h)

print(h.get_hash(0xfedcba98))

# 4d792066616972206c61647900000000

# 723C2FC8

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

h = Hash1("my fair lady")
print(h)
print(h.get_hash(0xfedcba98))

# 6d792066616972206c61647900000000
# 5E674DF0

h = Hash1("my fair lady")

print(h)

print(h.get_hash(0xfedcba98))

# 6d792066616972206c61647900000000

# 5E674DF0

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

除数→	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に設定した場合に、その結果がきれいにもとの値と同じとなることに相当する。

衝突状況のチェック

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

１文字→26通り
２文字→26*26=676通り
３文字→26*26*26=17,576通り
４文字→26*26*26*26=456,976通り
合計、475,254通り

import string

.....

hash_dict = {}

al = string.ascii_uppercase
modkey = 0xffffffff

for c1 in al:
    h1 = Hash1(c1).get_hash(modkey)
    if not(h1 in hash_dict): hash_dict[h1] = []
    hash_dict[h1].append(c1)
    for c2 in al:
        s2 = c1 + c2
        h2 = Hash1(s2).get_hash(modkey)
        if not(h2 in hash_dict): hash_dict[h2] = []
        hash_dict[h2].append(s2)
        for c3 in al:
            s3 = c1 + c2 + c3
            h3 = Hash1(s3).get_hash(modkey)
            if not(h3 in hash_dict): hash_dict[h3] = []
            hash_dict[h3].append(s3)
            for c4 in al:
                s4 = c1 + c2 + c3 + c4
                h4 = Hash1(s4).get_hash(modkey)
                if not(h4 in hash_dict): hash_dict[h4] = []
                hash_dict[h4].append(s4)

for itm in list(hash_dict.items()):
    if len(itm[1]) > 1:
        print('{} : {}'.format(itm[0], itm[1]))

import string

.....

hash_dict = {}

al = string.ascii_uppercase

modkey = 0xffffffff

for c1 in al:

h1 = Hash1(c1).get_hash(modkey)

if not(h1 in hash_dict): hash_dict[h1] = []

hash_dict[h1].append(c1)

for c2 in al:

s2 = c1 + c2

h2 = Hash1(s2).get_hash(modkey)

if not(h2 in hash_dict): hash_dict[h2] = []

hash_dict[h2].append(s2)

for c3 in al:

s3 = c1 + c2 + c3

h3 = Hash1(s3).get_hash(modkey)

if not(h3 in hash_dict): hash_dict[h3] = []

hash_dict[h3].append(s3)

for c4 in al:

s4 = c1 + c2 + c3 + c4

h4 = Hash1(s4).get_hash(modkey)

if not(h4 in hash_dict): hash_dict[h4] = []

hash_dict[h4].append(s4)

for itm in list(hash_dict.items()):

if len(itm[1]) > 1:

print('{} : {}'.format(itm[0], itm[1]))

その結果は次の通り。

0xFEDCBA98
アルファベット１～４文字で衝突なし。

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を追加

    def __init__(self, st):
        """
        コンストラクター
        引数
        - st：ハッシュ生成対象文字列
        内容
        - 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定
        - 文字列の各文字の文字コードをバッファーの背等から格納

        """
        self.buf = 0
        self.buf_length = 16  # バッファーは16バイト
        self.hash_length = 8  # ハッシュ値は8バイト

        # 文字列中の文字のコードをバッファーに加えていく
        for c in st:
            self.buf <<= 8
            self.buf += ord(c)

        # 文字コードを埋めた後のバッファーのバイト数
        nbytes = self.get_nbytes()

        # バッファーの残り領域を0で埋める
        for n in range(0, self.buf_length - nbytes):
            self.buf = (self.buf << 8) + 0x00

def __init__(self, st):

"""

コンストラクター

引数

- st：ハッシュ生成対象文字列

内容

- 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定

- 文字列の各文字の文字コードをバッファーの背等から格納

"""

self.buf = 0

self.buf_length = 16 # バッファーは16バイト

self.hash_length = 8 # ハッシュ値は8バイト

# 文字列中の文字のコードをバッファーに加えていく

for c in st:

self.buf <<= 8

self.buf += ord(c)

# 文字コードを埋めた後のバッファーのバイト数

nbytes = self.get_nbytes()

# バッファーの残り領域を0で埋める

for n in range(0, self.buf_length - nbytes):

self.buf = (self.buf << 8) + 0x00

内部用メソッドget_nbytes()

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

    def get_nbytes(self):
        """現在のバッファーのバイト数を返すメソッド"""
        bf = self.buf
        nbytes = 0
        while bf != 0:
            nbytes += 1
            bf >>= 8
        return nbytes

def get_nbytes(self):

"""現在のバッファーのバイト数を返すメソッド"""

bf = self.buf

nbytes = 0

while bf != 0:

nbytes += 1

bf >>= 8

return nbytes

ハッシュ値計算get_hash()

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

    def get_hash(self, mod_key):
        """
        ハッシュを生成するメソッド
        引数
        - 剰余計算の被除数
        内容
        - バッファーの内容を整数とみなして剰余を計算
        戻り値
        - 16進表示の文字列によるハッシュ値(バイト数を調整)
        """
        hash_value = (self.buf % mod_key)
        return format(hash_value, '0'+str(self.hash_length)+'X')

def get_hash(self, mod_key):

"""

ハッシュを生成するメソッド

引数

- 剰余計算の被除数

内容

- バッファーの内容を整数とみなして剰余を計算

戻り値

- 16進表示の文字列によるハッシュ値(バイト数を調整)

"""

hash_value = (self.buf % mod_key)

return format(hash_value, '0'+str(self.hash_length)+'X')

文字列化メソッドstr()

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

    def __str__(self):
        """インスタンスの文字列化メソッド"""
        return format(self.buf, '0x')

def __str__(self):

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

return format(self.buf, '0x')

ハッシュ – 簡単すぎる例

2019-08-15 / tau / コメントする

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

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

# hash_0.py
# 任意の文字列のhashを返す関数。
# 文字列中の文字コードを単純に足し込んでいく
def make_hash(str):
    buffer = 0
    char_list = list(str)

    # すべての文字のコードを加える
    for c in char_list:
        buffer += ord(c)

    # 加えた結果を16進文字列にして返す
    return(format(buffer, 'X'))

# hash_0.py

# 任意の文字列のhashを返す関数。

# 文字列中の文字コードを単純に足し込んでいく

def make_hash(str):

buffer = 0

char_list = list(str)

# すべての文字のコードを加える

for c in char_list:

buffer += ord(c)

# 加えた結果を16進文字列にして返す

return(format(buffer, 'X'))

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

print(make_hash("America"))  # 2B2
print(make_hash("American")) # 320
print(make_hash("america"))  # 2D2

print(make_hash("America")) # 2B2

print(make_hash("American")) # 320

print(make_hash("america")) # 2D2

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

print(make_hash("The rain in Spain stays mainly in the plain.")) # FB5
print(make_hash("The rain in spain stays mainly in the plain.")) # FD5

1 2	print(make_hash("The rain in Spain stays mainly in the plain.")) # FB5 print(make_hash("The rain in spain stays mainly in the plain.")) # FD5

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

print(make_hash("AB")) # 83
print(make_hash("BA")) # 83

1 2	print(make_hash("AB")) # 83 print(make_hash("BA")) # 83

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

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

2019-08-12 / tau / コメントする

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

s = 'string'
lst = list(s)
print(lst) # ['s', 't', 'r', 'i', 'n', 'g']

s = 'string'

lst = list(s)

print(lst) # ['s', 't', 'r', 'i', 'n', 'g']

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

lst = ['s', 't', 'r', 'i', 'n', 'g']
print("".join(lst)) # string

1 2	lst = ['s', 't', 'r', 'i', 'n', 'g'] print("".join(lst)) # string

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

lst = ['s', 't', 'r', 'i', 'n', 'g']
print("-".join(lst)) # s-t-r-i-n-g

1 2	lst = ['s', 't', 'r', 'i', 'n', 'g'] print("-".join(lst)) # s-t-r-i-n-g

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

lst = ['s', 't', 'r', 'i', 'n', 'g']
print(", ".join(lst)) # s, t, r, i, n, g

1 2	lst = ['s', 't', 'r', 'i', 'n', 'g'] print(", ".join(lst)) # s, t, r, i, n, g

Python3 – 文字を順に取り出す

2019-08-11 / tau / コメントする

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

import string

print(string.digits)
print(string.octdigits)
print(string.hexdigits)
print(string.ascii_uppercase)
print(string.ascii_lowercase)
print(string.ascii_letters)
print(string.punctuation)

# 0123456789
# 01234567
# 0123456789abcdefABCDEF
# ABCDEFGHIJKLMNOPQRSTUVWXYZ
# abcdefghijklmnopqrstuvwxyz
# abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
# !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

import string

print(string.digits)

print(string.octdigits)

print(string.hexdigits)

print(string.ascii_uppercase)

print(string.ascii_lowercase)

print(string.ascii_letters)

print(string.punctuation)

# 0123456789

# 01234567

# 0123456789abcdefABCDEF

# ABCDEFGHIJKLMNOPQRSTUVWXYZ

# abcdefghijklmnopqrstuvwxyz

# abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

# !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

概要

乱数系列/seed()

疑似乱数/random()

一様乱数/uniform()

整数乱数/randint(), randrange()

ランダム選択/choise()

シャッフル/shuffle()

概要

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

数値の場合

文字列の場合

リストの場合

関数の引数の参照

数値の場合

文字列の場合

リストの場合

キーワード

組み込み関数

暗号化

暗号化の流れ

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

素数の組の準備

素数の積nの計算

計算準備

公開鍵の計算

秘密鍵の計算

簡略化した暗号化の例

鍵の準備

暗号化

復号

電子証明

電子証明の流れ

簡略化した電子証明の例

証明書の暗号化

考え方

コード全体

実行結果

除数で変わる結果

除数の影響

衝突状況のチェック

コード詳細

コンストラクタ__init__()

内部用メソッドget_nbytes()

ハッシュ値計算get_hash()

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

コンストラクタinit()

文字列化メソッドstr()