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

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

2の補数

2019-07-28 / tau / コメントする

簡単なケース

正の数の表現

桁数が固定された2進数の加算を考える。たとえば4桁(4 bits)の場合に1ずつ加える。

$\begin{array}{cc} 0000 + 0001 = 0001 & (1)\\ 0001 + 0001 = 0010 & (2)\\ 0010 + 0001 = 0011 & (3)\\ 0011 + 0001 = 0100 & (4)\\ 0100 + 0001 = 0101 & (5)\\ 0101 + 0001 = 0110 & (6)\\ 0110 + 0001 = 0111 & (7) \end{array}$

負の数の表現

一方、-1は0から1を引いた値として計算される。最初の計算だけ、上位桁から1を借りてこられるとして、以下の様な計算になる。

$\begin{array}{cc} 0000 - 0001 = 1111 & (-1)\\ 1111 - 0001 = 1110 & (-2)\\ 1110 - 0001 = 1101 & (-3)\\ 1101 - 0001 = 1100 & (-4)\\ 1100 - 0001 = 1011 & (-5)\\ 1011 - 0001 = 1010 & (-6)\\ 1010 - 0001 = 1001 & (-7)\\ 1001 - 0001 = 1000 & (-8) \end{array}$

上の足し算の結果と下の引き算の結果をを見ると、以下のことがわかる。

正の数(0～7)と負の数(-8～-1)の合計15個で、4ビットの全てのパターンが網羅されている
正の数の最上位ビットは0、負の数の最上位ビットは1

引き算と補数の足し算

たとえば上の例で、正の数と負の数を加えてみる。

$\begin{array}{cl} 0101 + 1110 = 0011 & (5-2=3) \\ 0011 + 1001 = 1100 & (3-7=-4) \\ 1111 + 1100 = 1011 & (-1-4=-5) \end{array}$

2の補数を計算したときに0からその数を減じているので、当然の結果ではある。いずれにしても、負数を2の補数で表現することで、減算を加算で代えることができる。

2の補数を得る方法

2の補数を得るのに、いちいち0から引かなくても、以下の方法で可能。

整数のビットパターンを反転
1を加える

4ビットの例では以下のとおり。

$\begin{array}{cc} 0001 \rightarrow 1110 \rightarrow 1111 & (-1)\\ 0010 \rightarrow1101 \rightarrow 1110 & (-2)\\ 0011 \rightarrow1100 \rightarrow 1101 & (-3)\\ 0100 \rightarrow1011 \rightarrow 1100 & (-4)\\ 0101 \rightarrow1010 \rightarrow 1011 & (-5)\\ 0110 \rightarrow1001 \rightarrow 1010 & (-6)\\ 0111 \rightarrow1000 \rightarrow 1001 & (-7)\\ 1000 \rightarrow0111 \rightarrow 1000 & (-8)\\ \end{array}$

すなわち、固定長の整数の場合、ビット反転と加算機能があれば、減算を実現できる。

典型的なビット数の整数範囲

8ビット

byte型でよく見る値。

$\begin{array}{lllr} 0111\:1111 = &2^7 - 1 &=& 127 \\ 1000\:0000 = &-2^7 &=& -128 \end{array}$

16ビット

short型でよく見る値。

$\begin{array}{lllr} 0111\:1111\:1111\:1111 = &2^{15} - 1 &= &32767 \\ 1000\:0000\:0000\:0000 = &-2^{15} &= &-32768 \end{array}$

32ビット

一般的なint型で絶対値が約21億。

$\begin{array}{llr} 2^{31} - 1 &=& ‭2,147,483,647 \\ -2^{31} &=& -‭2,147,483,648‬ \end{array}$

64ビット

long型、絶対値が約920京（！）

$\begin{array}{llr} 2^{63} - 1 &=& ‭9,223,372,036,854,775,807 \\ -2^{63} &=& -‭9,223,372,036,854,775,808‬ \end{array}$

Python3 – 数値と文字列の相互変換

2019-07-28 / tau / コメントする

数値から文字列への変換

10進数(str関数)

str関数で引数の数値を文字列化。

整数の場合、桁数が多くてもそのまま文字列化される。

>>> str(1234)
'1234'
>>> str(12345678901234567890)
'12345678901234567890'

>>> str(1234)

'1234'

>>> str(12345678901234567890)

'12345678901234567890'

実数の場合は有効数値で丸められる。

>>> str(123.45678901234567890)
'123.45678901234568'

1 2	>>> str(123.45678901234567890) '123.45678901234568'

浮動小数点で与えると、桁数が収まる範囲で固定少数表示の文字列になる。

>>> str(1e3)
'1000.0'
>>> str(1e15)
'1000000000000000.0'
>>> str(1e16)
'1e+16'

>>> str(1e3)

'1000.0'

>>> str(1e15)

'1000000000000000.0'

>>> str(1e16)

'1e+16'

2進数、8進数、16進数

組み込み関数を使う方法

bin、oct、hex関数を使った場合、プレフィックス’0b’、’0o’、’0x’がついた文字列になる。

>>> bin(31)
'0b11111'
>>> oct(4095)
'0o7777'
>>> hex(65535)
'0xffff'

>>> bin(31)

'0b11111'

>>> oct(4095)

'0o7777'

>>> hex(65535)

'0xffff'

format関数を使う方法

format関数の第2引数に基数に対応した文字を指定する。

>>> format(255, 'b')
'11111111'
>>> format(255, 'o')
'377'
>>> format(255, 'x')
'ff'
>>> format(255, 'X')
'FF'

>>> format(255, 'b')

'11111111'

>>> format(255, 'o')

'377'

>>> format(255, 'x')

'ff'

>>> format(255, 'X')

'FF'

第2引数で、桁数を指定して空いた上位桁を0で埋めることができる。

>>> format(15, '08b')
'00001111'
>>> format(15, '04o')
'0017'
>>> format(15, '02x')
'0f'

>>> format(15, '08b')

'00001111'

>>> format(15, '04o')

'0017'

>>> format(15, '02x')

'0f'

書式文字列を使う方法

書式文字列と％演算子を使っても、数値を文字列化できるが、2進数には対応していない。

>>> '%#o' % 255, '%o' % 255
('0o377', '377')
>>> '%#x' % 255, '%x' % 255
('0xff', 'ff')
>>> '%#X' % 255, '%X' % 255
('0XFF', 'FF')

>>> '%#o' % 255, '%o' % 255

('0o377', '377')

>>> '%#x' % 255, '%x' % 255

('0xff', 'ff')

>>> '%#X' % 255, '%X' % 255

('0XFF', 'FF')

文字列から数値への変換

10進数

整数(int関数)

int関数は整数の文字列を数値化するが、実数形式の文字列を与えるとエラーになる。

>>> int('1234')
1234
>>> int('1.')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: '1.'

>>> int('1234')

1234

>>> int('1.')

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ValueError: invalid literal for int() with base 10: '1.'

実数(float関数)

float関数は実数の文字列を数値化する。固定小数点/浮動小数点のどちらの表現でもかまわない。

>>> float('1234')
1234.0
>>> float('1.234')
1.234
>>> float('1e15')
1000000000000000.0
>>> float('1e16')
1e+16

>>> float('1234')

1234.0

>>> float('1.234')

1.234

>>> float('1e15')

1000000000000000.0

>>> float('1e16')

1e+16

2進数、8進数、16進数

int関数の第2引数で基数を指定する。

>>> int('1111', 2)
15
>>> int('7777', 8)
4095
>>> int('FFFF', 16)
65535

>>> int('1111', 2)

>>> int('7777', 8)

4095

>>> int('FFFF', 16)

65535

第2引数には2～36まで指定可能で、0～9とA～Zまで使った36進法まで変換可能。

>>> int('1000', 1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: int() base must be >= 2 and <= 36
>>> int('1000', 3)
27
>>> int('GGGG', 17)
83520
>>> int('ZZZZ', 36)
1679615

>>> int('1000', 1)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ValueError: int() base must be >= 2 and <= 36

>>> int('1000', 3)

>>> int('GGGG', 17)

83520

>>> int('ZZZZ', 36)

1679615

‘0b’、’0o’、’0x’のプレフィックスを付けた文字列を変換するときは、第2引数を0にする。この場合、10進数も変換可能。

>>> int('0x1111', 0)
4369
>>> int('0x7777', 0)
30583
>>> int('0xFFFF', 0)
65535
>>> int('9999', 0)
9999

>>> int('0x1111', 0)

4369

>>> int('0x7777', 0)

30583

>>> int('0xFFFF', 0)

65535

>>> int('9999', 0)

9999

Python3 – 数値

2019-07-27 / tau / コメントする

int型

整数型はintで表される。

>>> print(type(1), 1)
<class 'int'> 1

1 2	>>> print(type(1), 1) <class 'int'> 1

桁数が多くなってもint型として扱われる。

>>> print(type(1000000000000000000000000000000), 1000000000000000000000000000000)
<class 'int'> 1000000000000000000000000000000

1 2	>>> print(type(1000000000000000000000000000000), 1000000000000000000000000000000) <class 'int'> 1000000000000000000000000000000

int型のチェック

>>> print(type(1)==int)
True

1 2	>>> print(type(1)==int) True

float型

数値リテラルに小数点を付けるとfloat型として扱われる。float型はCやFORTRANの倍精度の精度。

>>> print(type(1.), 1.)
<class 'float'> 1.0

1 2	>>> print(type(1.), 1.) <class 'float'> 1.0

‘/’による除算の結果は常にfloat型になる。

>>> print(type(6/3), 6/3)
<class 'float'> 2.0

1 2	>>> print(type(6/3), 6/3) <class 'float'> 2.0

‘//’による除算では商が整数化される(整数除算と剰余を参照)。

>>> print(type(8//3), 8//3)
<class 'int'> 2

1 2	>>> print(type(8//3), 8//3) <class 'int'> 2

キーワード

組み込み関数

暗号化

暗号化の流れ

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

素数の組の準備

素数の積nの計算

計算準備

公開鍵の計算

秘密鍵の計算

簡略化した暗号化の例

鍵の準備

暗号化

復号

電子証明

電子証明の流れ

簡略化した電子証明の例

証明書の暗号化

考え方

コード全体

実行結果

除数で変わる結果

除数の影響

衝突状況のチェック

コード詳細

コンストラクタ__init__()

内部用メソッドget_nbytes()

ハッシュ値計算get_hash()

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

簡単なケース

正の数の表現

負の数の表現

引き算と補数の足し算

2の補数を得る方法

典型的なビット数の整数範囲

8ビット

16ビット

32ビット

64ビット

数値から文字列への変換

10進数(str関数)

2進数、8進数、16進数

組み込み関数を使う方法

format関数を使う方法

書式文字列を使う方法

文字列から数値への変換

10進数

整数(int関数)

実数(float関数)

2進数、8進数、16進数

int型

float型

コンストラクタinit()

文字列化メソッドstr()