を参照していく。
10. 現代社会を支えるアルゴリズム
日常生活を支えるアルゴリズムを紹介する。具体的には通信経路の暗号化とデータの圧縮を扱う。
10.1 ハッシュ関数
適当な入力値に対してハッシュ値を返す関数をハッシュ関数という。の組み込み関数である
関数は正の整数を入力するとそれをそのままハッシュ値として返す。これに対して出力値から入力の予測がほぼ不可能なハッシュ関数を暗号学的ハッシュ関数という。
import hashlib import pickle # ハッシュ値を返してみる print(hashlib.md5(pickle.dumps(1)).hexdigest()) print(hashlib.md5(pickle.dumps(2)).hexdigest())
10.1.1 パスワードの保存
このような暗号学的ハッシュ関数を用いる理由は何だろうか。たとえばユーザがあるサービスに会員登録してパスワードを登録したとき、サイトの運営者はパスワードを暗号学的ハッシュ関数によって変換してデータベースに保存すべきである。これは暗号的ハッシュ関数の返り値は出力値から入力の予測がほぼ不可能だからである。こうすればユーザが実際にどのようなパスワードを用いているかは不明であり、万が一サーバが不正アクセスされてパスワード情報が流出しても平文のパスワードが第三者に渡る心配がなくなる。理論的には、異なる入力データに同じハッシュ値が割当たるハッシュ値の衝突が起こる可能性があるものの、実際にはまず起こらない。
10.1.2 ビットコインと暗号学的ハッシュ関数
暗号学的ハッシュ関数が具体的に利用されている状況を議論しよう。
一般的な銀行口座を介した取引では、データが改竄されていないことを銀行が保障する。これに対してビットコインの場合はブロックチェーンで支えられている。ブロックチェーンではブロックを連結するのに、暗号学的ハッシュ関数の出力値を求めている。しかもと呼ばれる小さい余計なデータを追加することで算出されるハッシュ値の先頭が
で埋まるように調整し、入力データが改竄されるとハッシュ値が大きく変化することを容易に検知しやすくしている。
を変えながら目的のハッシュ値が求められるまで計算を続けることをマイニングという。
import hashlib def block_to_hash(block_data, nonce): # 関数の引数xにnonceを連結し、sha256(規格名)を用いてハッシュ値を計算する input_str = str(block_data) + str(nonce) h = hashlib.sha256(input_str.encode('UTF-8')).hexdigest() # 先頭から0がいくつ並んでいるかを数える cnt = 0 for v in h: if v=='0': cnt += 1 else: break return h, cnt my_block = 'prev_block_tx0_tx1_tx2' c = 1 while True: hash_val, cnt = block_to_hash(my_block, c) if cnt == 5: print('{}回目の計算で成功しました'.format(c)) print(hash_val) break c += 1
10.2 公開鍵暗号
公開鍵暗号は、暗号の鍵の一部を公開するにもかかわらず通信を暗号化できる仕組みである。さらに現在使われている公開鍵暗号の仕組みは本人であることの証明にも使える。
10.2.1 暗号の種類
暗号化した場合、暗号化された文字を伝えられた側がそれを解読すべく、復号の鍵が必要になる。暗号化と復号化とで同じ鍵を用いるとき、その鍵は共通鍵暗号ないし秘密鍵暗号と呼ばれる。インターネットは基本的に不特定多数の参加者がいるため、秘密のカギを全員で共有するのはほぼ不可能である。そこで公開鍵暗号を併用する。公開鍵暗号は誰にでも公開してよい一方で、秘密鍵は誰にも教えてはならない。
10.2.2 RSA暗号
現在広く使われている公開鍵暗号は暗号である。大きな数の素因数分解に時間が掛かることを利用した方法である。
暗号では公開鍵を用いて暗号化したデータは秘密鍵では復号化できず、秘密鍵を使ったときのみ元に戻すことができる。秘密鍵を持っている相手にだけ、他の誰にも知られたくない情報を送ることができる。
秘密鍵を使って暗号化されたデータは公開鍵を使えば誰でも復号化できる。公開鍵は一般に公開しているため、署名に相当する。秘密鍵を知っているのは自分自身のみであるため、その人が公開している鍵で復号化できるデータは、その人が暗号化したことが保障される。
これらを使うことで通信経路の暗号化と接続しているサイトの真偽検証が一度に実現できる。
10.2.3 RSA暗号の数学的な背景
の小定理を拡張した
関数を、互いに素な
に対して
を満たすような関数だとする。が素数ならば
である。
暗号はこれを活用する。素数
を用いて自然数
と書けるとする。
次に
を満たすようなを用意する。そして
を公開する。このとき
は誰にも知られてはならない。
は
と互いな素である必要がある一方でどのみち公開するために、2進数表現したときに
を用いる数が少なく計算が高速になることもあり、
などが用いられる。
を決めるには
を満たすようなを決めればよい。
を暗号化して送信したいメッセージだとする。通信相手が公開している
を用いて
を
で割った余りを計算すると暗号となる。これを
とすれば、
が得られる。で
は共に素数だから、
であり、
を得る。
10.2.4 RSA暗号の実装
##################### ### RSA暗号の実装 ### ##################### p = pow(2, 89) - 1 # 素数だと知られている q = pow(2, 107) - 1 # 素数だと知られている print(p) print(q) n = p * q # 公開鍵暗号の1つ print(n) r = 65537 # もう1つの公開鍵暗号 def find_s(phi_pq, r): k = 1 while True: y = 1 + k * phi_pq s,d = divmod(y, r) if d ==0: return k, s k += 1 k, s = find_s((p-1)*(q-1), r) s ### テスト msg = ord('猫') print(msg) secret_msg = pow(msg, r, n) print(secret_msg) decoded_msg = pow(secret_msg, s, n) chr(decoded_msg)
10.2.5 公開鍵暗号基盤
公開鍵暗号と暗号学的ハッシュ関数を組み合わせると、デジタル署名を作ることができる。
データ送信者はまずデータのハッシュ値を計算し、自らの秘密鍵を用いて暗号化した上で、データと暗号化されたデータを送信する。受信者はデータを取り出し、同じアルゴリズムでハッシュ値を計算する。一方でデータ送信者の公開鍵を用いて一緒についてきた暗号を復号化する。送信者の送ってきた暗号化されたデータ（＝ハッシュ値）と、受信者が送信者から得たデータのハッシュ値が一致するかを判定することで送信者が想定していた当人なのかを判断する。
秘密鍵と公開鍵のペアが全くの第三者に所有されているとセキュリティに懸念が生じる。そこで認証局を設置する。認証局を信頼できる第三者として、自らの公開鍵に認証局のデジタル署名を付けてもらう。これを証明書と呼ぶ。こうした仕組みを公開鍵基盤として整備されている。
10.3 データ圧縮の技術
10.3.1 データ圧縮の基本
データの圧縮には、可逆圧縮と非可逆圧縮の2つがある。後者は圧縮率が高い一方で完全な復元ができない。
データ圧縮の基本的なアイディアは、データのうち、同じ文字が連続しているときにその文字1文字とそれが連続する数に変換することである。ただし一般に同じ文字が連続することは珍しいため、同じ文字が連続するように変換処理する。その方法の1つにブロックソートがある。
10.3.2 ブロックソート
ブロックソートは-
変換とも呼ばれる。
| (1) | まず文字列の先頭から順番に1文字ずつ末尾に移動する。これを元の文字列が出現する1つ手前まで繰り返す。 | |
| (2) | 完成した文字列をソートする。これによりソートした後の文字列とソートした後に元の文字列が何番目に来たかの2つの情報を記録しておく。ただしソートの順番が決まらない場合、元の順序を保持する。 |
これを復元することも可能である。
################################ ### ブロックソートとその復元 ### ################################ def block_sort_encode(val): res = [] res.append(val) # 元のデータを追加してあるため、forの回数を1回減らす for i in range(len(val)-1): # 1つ前を持ってくる temp = res[-1] # 先頭の文字を末尾に移動する res.append(temp[1:] + temp[0]) res.sort() # 元のデータがどこへ行ったか探す idx = res.index(val) # 末尾の文字をすべて集めたものが結果になる encoded_str = [v[-1] for v in res] return ''.join(encoded_str), idx input_str = '明日の会合は午後が良いですが、良い天気だとお昼ご飯の後で眠くなってしまうため、午後は午後でも遅い時間が良いです。' bsorted_str = block_sort_encode(input_str) bsorted_str ### デコード def block_sort_decode(val, idx): # ソートした場合に各文字がどこへ行くかを格納する char_last_idx = [] for i, v in enumerate(val): char_last_idx.append((v, i)) # 文字でソートする。同じ文字の場合は、元の順序を保持する char_last_idx.sort() # すべて0で初期化 last_to_front_idx = [0] * len(char_last_idx) for i,v in enumerate(char_last_idx): # 末尾にあった文字が先頭へ行ったときに何処へ行ったのか last_to_front_idx[v[1]] = i res = val[idx] # 最初は元のデータのあった場所から i = last_to_front_idx[idx] while i != idx: res += val[i] # 次に行く場所へ添字を更新 i = last_to_front_idx[i] # 逆順にして返す return res[::-1] block_sort_decode(*bsorted_str)
