初回はガイダンスだったので、2回目から記録をとっていく。

第2回

概要

本講義全体では、主に公開鍵暗号理論の数学的な側面について進めていくことになる。が、公開鍵が何者かわからずに理論を学んでも仕方がない、ということでそれに先立ち、公開鍵暗号が出てくるまでの歴史と公開鍵暗号が使用される場面、さらに公開鍵の問題点を説明する、という感じの流れ。

公開鍵が出てくるまでの歴史

公開鍵は、共通鍵を安全に配送するために考え出された暗号である。 つまり、公開鍵が出てくるまでの鍵はすべて共通鍵暗号方式であり、送信者と受信者で同じ鍵を共有する必要がある。

シーザー暗号

ローマの軍人、ユリウス・シーザーが考え出した暗号。平文のアルファベットをアルファベット順でn文字シフトさせる。送信者と受信者でシフトする文字数n(鍵)を共有する必要がある。 問題点としては、鍵の数が25しかないので破るのが簡単ということ。

換字暗号

シーザー暗号を一般化したものとして、生み出された暗号。シーザー暗号では鍵に対して全ての文字をnシフトしていた。一方、この暗号は,文字1文字に対して暗号文を一対一に写像する。可能な鍵の種類はpermutation(25)になる。 問題点としては、平文と暗号文の対が流出すると鍵が破られること、また、同じ鍵でやり取りを続けていると規則性が見つかってしまうことがある。

バーナム暗号

発明されたのは、1918年。このころは電信がすでに発達していた。つまり、「ビット」という概念が存在した。 ビット列で生成された平文と同じ長さの鍵を用意する。平文と鍵のビット同士の排他的論理和をとることで暗号文が生成される。復号には同じ鍵を用いて、暗号文と鍵の排他的論理和をとる。

自分は、このバーナム暗号が現代の共通鍵暗号方式でも使われいてると思っていたが、どうやら違うようです。後ほど共通鍵のセクションで説明する鍵が現代では使われているみたい。授業ではバーナム暗号が使われない理由として、共通鍵を共有するのが難しいと言っていたが、それは全部の共通鍵に共通することじゃないか？と思った。なぜ現代でバーナム暗号が共通鍵に使われないかは調べてみる価値があるかもしれない。

その他、古典的な暗号技術

エニグマ暗号器、ローレンツ暗号器の二つが説明されていたが、原理についてはそこまで説明していなかった。

現代の暗号技術

共通鍵暗号

今まで説明してきたのも全部共通鍵暗号だが、現代ではさらに強力な共通鍵暗号が考案されているらしい。 1977年にDESという共通鍵暗号が考案され、さらに2001年にAESというさらに強力な暗号が考案された。

公開鍵暗号

ここまで共通鍵をずっと説明してきたが,共通鍵を使った暗号系の問題に「どのように安全に共通鍵を2者間で共有するか」がある。これを鍵配送問題という。 鍵配送問題を解決するために発明されたのが「公開鍵暗号方式」である。さらに、公開鍵暗号方式の特徴を活かして認証や署名をすることもできる。

じつは、公開鍵にも問題点はあるが、それを解決する手段として、公開鍵を使った署名が行われる（デジタル証明書）。後ほど説明する。

公開鍵暗号方式では、秘密鍵と公開鍵という二つの鍵をペアで生成する。 公開鍵で暗号化された暗号文は、秘密鍵でしか復号できない。この逆も存在し、秘密鍵で暗号化された暗号文は公開鍵でしか復号できない。この特徴を用いることで2者間で安全に情報のやり取りができるようになる。

公開鍵暗号方式ではRSA暗号が使われる。「非常に大きな2つの素数の積の素因数分解が原理上不可能である」性質を用いているため、鍵の長さが非常に長いのが特徴で、現在、RSA暗号の安全性を担保する為には2048bitの鍵が必要となっている。 原理的には、すべての通信を公開鍵暗号で行うことも可能だが、暗号、復号のコストが大きいため、共通鍵を公開鍵暗号方式で交換した後は、共通鍵で暗号通信をするのが一般的である。

認証と署名についても説明したいと思う。 認証とは、「公開鍵のペアである秘密鍵が本物であるか」を証明するための仕組み。原理は簡単で、送信者は元文を公開鍵で暗号化し、暗号文を受信者に送る。受信者が秘密鍵で復号してそれを送信者に送り返す。元文と秘密鍵で復号されて送られてきた文が同じであれば受信者がもっている秘密鍵が本物であることが証明できる。つまり、送信相手が安全ということが保証される。

署名とは、「送られてきたデータが改ざんされていないこと」を証明するための仕組み。AがBになにか情報を送りたいときに署名をつかう例で説明する。 まず、AとBの両者で共通のハッシュ関数を用意する。Aはハッシュ関数に送信したい情報を入れてハッシュ値をえる。そのハッシュ値を秘密鍵で暗号化する。Aは暗号化されたハッシュ値と平文をBに送る。Bは、1)送られてきた平文を公開されているハッシュ関数にかけてハッシュ値を得る。さらに,2)Aから送られてきた暗号化されたハッシュ値を公開鍵を使って復号する。この二つの値が一致すれば、Aが送ってきた文書に改ざんがないことが証明できる。 （同時に、認証もできている気がするのだが）

公開鍵暗号方式を用いて共通鍵を交換し、その共通鍵を使って通信をすれば安全なように思える。しかし、AさんとBさんの間にXという攻撃者が入る、man in the middle attackというものがある。これは、

AがBに自ら公開鍵を渡して公開鍵暗号による通信を行うとすると、XはAがBに送った公開鍵を取得し、Bには代わりに自分の公開鍵をAのものと偽って送信する。Bは（Aのものと思い込んでいる）Xの公開鍵で暗号化したデータをAに送信する(が実際はXがBの情報を不正に入手することになる)。

という攻撃手法。

つまり、公開鍵暗号方式では、「一般公開されているように見える公開鍵が、目的としている人の公開鍵である保証がない」という問題点が存在する。

この問題を解決するために、「公開鍵暗号基盤(Publick Key Infrastructure)」が整備された。 具体的には、「公開鍵が本人のものであることを証明する機関」を設けた。この機関を認証局(CA)という。

例えとして、Aが自分の公開鍵の正当性を保証する流れを考える。 Aは公開鍵が本物であることを証明するために、CA認証局に自分の公開鍵を渡す。CAは、Aから渡された公開鍵が、Aの秘密鍵のペアであることを上で説明した認証等の技術を使って確認する。その後、CAはCAが持っている秘密鍵を用いてAの公開鍵をハッシュ化し、さらに暗号化する（署名）。この、ハッシュ化されて、暗号化された公開鍵がデジタル証明書である。技術的には「認証局の秘密鍵・公開鍵を用いた署名」を使っている。

ここでBがAの公開鍵が本当にBのものであるかを確認したいときには、Aのデジタル証明書をCAの公開鍵で復号する。復号された公開鍵のハッシュ値とAが本物であると宣言する公開鍵のハッシュ値が一致すれば、その公開鍵は本当にAのものであることが証明される。

なお、上で説明しているハッシュ値を計算するための「ハッシュ関数」は公開されているものである。つまり、署名がどのようなハッシュ関数を用いて生成されたかは公開されている。規格化されているということ。 例えば、SHA-1は公開されているハッシュアルゴリズムで20バイトのハッシュ値を生成する。ソースコードはここで見られる。他には、sha-256というのもある。これは、256ビットのハッシュ値を生成する。

ちなみに、ssl化されているサイトはurlの左に鍵マークがついている。この鍵マークをクリックすると、デジタル証明書に関する情報が得られる。このサイトのデジタル証明書を例に説明していく(非常に見づらいですが。 デジタル証明書

認証局は,Let’s Encryptであることがわかる。 技術的に大事なところは、Fingerprintsのところ。これは、ハッシュ化された公開鍵ですね。SHA-256 Fingerprintは、2048bitの公開鍵を256bitにハッシュ化した時のハッシュ値。SHA-1 Fingerprintは20バイトのハッシュ値。20バイト=160ビット=40hex。 SHA-1 fingerprintを見ると、確かに40文字ある。

さらに写真は割愛するが、detaileタブで「Certificate Signature Value」が見られるが、これは認証局によって生成された、デジタル署名である。内容はこんな感じ

AD B9 37 B3 F6 A5 BC B9 E8 98 8B 83 05 76 59 E6
8E 57 E5 4C E8 7B 25 7B 01 D0 A1 85 A5 06 C5 26
DD C9 FD 0E 9B 79 1E 8A 5F 42 F5 F0 8D BC 32 02
F0 DC 44 55 FF EB 2A 1B D0 62 D5 8A 6C 31 E3 09
FE C9 B6 1A 1A E5 6F 52 8B B0 91 51 EB 4D D3 64
07 48 18 B0 A8 30 99 5E 5C 7C 8B 53 F6 38 67 F8
D1 26 FC 86 A0 A0 A4 43 45 25 49 55 B0 CD 23 C2
CE CF 78 78 AB FF 1E 16 50 AC 87 44 37 10 49 B5
59 AC 11 F4 69 4E 17 05 5C C9 29 59 38 B7 A0 A8
AB B9 D6 54 0B C1 02 8B A6 42 4E 17 70 3E 89 F6
13 E5 BF C2 9C E7 23 DA 68 FB 15 EC BC C9 4B 73
6B 42 6C 41 56 E4 D9 20 94 52 AE F1 E0 BF DB B5
19 08 9D 54 1A DB E6 EF 7B 01 B2 1C 57 8C 1E BA
51 39 7C EC 0D 75 0C 61 C2 CF B1 16 61 E1 0F C7
B0 49 2A 53 10 A1 5E D5 24 A5 0A 24 9F 75 7D 10
3B 92 4F 84 77 2E DB 34 EF 2A 02 B4 98 D6 62 DB

161616 = (2**4)3 = 212 = 4096bit。 これが署名。この署名をLet’s Encryptの公開鍵で復号すると、SHA-1ハッシュが出てくるはず。

参考サイト

1

2

3

4

学んだことをOpenSSLで試してみる

OpenSSLのことをまとめてくれているいいサイトがある。これを参考にOpenSSLをいろいろといじってみる。

sha256を使ってみる

このサイト でsha256のハッシュ関数の原理が説明されています。 ちなみに、

openssl sha256 file.txt

を入力するとハッシュ値が出てきます。ちなみに、sha256ってのは、256bitのハッシュを生成しますよって意味の256.

SHA-256とは、任意の長さの原文から固定長の特徴的な値を算出するハッシュ関数（要約関数）の一つ。 どんな長さの原文からも256ビットのハッシュ値を算出することができる。

そして、当たり前だけど、sha256ハッシュは、規格化されているというか、どのsha256も当たり前だけど同じアルゴリズムを使ってハッシュ値を計算している。これはすごいっちゃすごいよね。実際にうちのラズパイクラスタで同じファイルをopensslを使ってハッシュ化した結果がこちらです。

hoge@slave1:/cluster_common $ openssl sha256 kami_from_1.txt
SHA256(kami_from_1.txt)= 5760122a32c3926f8b09e3f76971884f26a7b68fca7c8616b08e8548e26ec4ed

hoge@mastar:/cluster_common $ openssl sha256 kami_from_1.txt
SHA256(kami_from_1.txt)= 5760122a32c3926f8b09e3f76971884f26a7b68fca7c8616b08e8548e26ec4ed

完全一致してるね。面白い。よくソフトウェアにハッシュ値が含まれていることがあるよね。何のためかというと、ハッシュ値を使ってファイルの内容が正しいかどうかをチェックするのが目的。改ざんされていないか、ウイルスに完成んしていないかとかね。 いわゆるチェックサムも同じだと思う。

base64とは

エンコード方法である。64文字の英数字のみを用いてマルチバイト文字やバイナリデータを扱うためのエンコード方式。なるほど。Base64変換手順は以下の通り

  1. 元データを6ビットずつに分割する。（6ビットに満たない分は後ろに0を追加して6ビットにする）
  1. 各6ビットの値を変換表を使って4文字ずつ変換する。
  2. 4文字に足りない分は = 記号を後ろに追加する。

文章の最後が=になっているの多いけど、あれには理由があったということだよね。

これは暗号化、というより単なる写像だね。BASE64()という関数によってデータがエンコードされるって思えばいいかな。

opensslを使った単純な暗号化。

openssl enc -aes-256-cbc -e -in plain.txt -out encrypted.txt

パスワードの入力を求められて、 ぼくのクレジットカード番号を暗号化したらこうなった

Salted__ x!�R')��t
�L������3Z)�{#���e�t�+

openssl enc -aes-256-cbc -d -in encrypted.txt -out plain.txt

で復号したらこうなった。

5555-5555-4560-0721

ref1

第3回

概要

公開鍵暗号理論を数学的に説明するにあたり基礎となる数学を学んでいくことになる。その第一回として、 群(group)について学んだ。

そもそも代数とは

集合上の演算を扱う分野である。 演算を一般化したのが次の式

X×X |-> X

群とは

群とは、「集合と、その集合に対する演算が以下の三つの公理を満たしている者である」

  1. 1: 結合法則が成り立つ
  2. 2: 単位元を持つ
  3. 3: 逆元を持つ

また、1,2,3のどこまでを満たすかによって、その集合と演算には名前が付く 1のみを満たしている場合：半群(semigroup) 1,2を満たしている場合：monoid

さらに、上記1,2,3を満たし、演算が可換であるとき、その群は「アーベル群」になる。

群の例

加法整数群(整数の集合と足し算)

  1. 1: a + (b + c) = (a + b) + c
  2. 2: a + 0 = 0 + a. 単位元:0
  3. 3-3 = 0: aの逆元：-a

よって、群となる。さらに、足し算は可換である。よってアーベル群

乗法整数軍(0を除く)

  1. 1: 満たす
  2. 2: a1 = 1a
  3. 3: a*(1/a) = 1

よって、アーベル群

正則な行列の積

  1. 1: 満たす
  2. 2: AE = EA = A
  3. 3: AAinv = AinvA = E よって、群である。（可換ではない）

bidirectional map(全単射)

まずは、全単射の定義から 単射(injection)：入力が違かったら出力が違う 全射(surjection)：出力元で入力元の写像になっていないものが存在しない。（あまりものが存在しない) この二つを満たすとき、関数（写像）は全単射となる。

写像の例(入力と出力の集合はどちらもR)

  1. 1: f(x) = x**2 単射ですらない。なぜなら、f(-1) = f(1)

  2. 2: f(x) = exp(x) 単射ではあるが全射ではない。なぜなら、exp(x) = -4 を満たすxが存在しないため。

  3. 3: f(x) = x 全単射

話を戻す。

全単射である関数(集合)の合成(演算)は群である。 なぜなら,

  1. 1: f*(gh) = (fg)*h やればわかる
  2. 2: 単位元を持つ。　単位元　f(x) = x
  3. 3: 逆元を持つ。　逆元：逆関数。

自然数の足し算

  1. 1: 結合法則は成り立つ
  2. 単位元を持たない。なぜなら、自然数は0を含まないから。 よって、群ではない。

楕円曲線群

まったく意味が分からない説明だったけど、どうやら楕円曲線上の足し算というのも群らしい。おれにはわからない。 で、加法楕円曲線群の上で成立している暗号が、有名な「楕円曲線暗号」。 楕円曲線暗号のすごいところは、RSA暗号と同等の安全性をRSA暗号よりも短いかぎの長さで実現できるということ。 楕円曲線暗号がわかったら、いいですね、この授業を通して。

第4、5回

授業に出ていなかったので内容はスライドをまとめたものになる。

  1. 環、体の話ですね。 基本的には、群の性質を満たす代数系の中に環があって、さらに特定の性質を満たすものを体と呼ぶ、みたいな感じですね。

環の定義

  1. 集合Rとその上の二つの二項演算（加法、乗法）出会って、以下の条件を満たすもののこと。
  2. 加法に関して、アーベル群である
  3. 乗法に関して、モノイドである。
  4. 分配法則が成り立つ

commuttive = 可換な

かなり基礎的な代数をやっているね。群艦隊の定義だね。

11/24(第6，7回)

Introducrtion to Public key cryptography

まあこの辺から興味ありますね。

diffie-hellman key exchange

事前の秘密の共有無しに、盗聴の可能性のある通信路を使って、暗号鍵の共有を可能にする、公開鍵暗号方式の暗号プロトコルである。この鍵は、共通鍵暗号の鍵として使用可能である。

原理についてはwikipediaを見てください。

二つの重要な仮定。

  1. Discrete Logarithm Assumption aka(DL assumptoin) 離散対数。

離散対数問題とは、ある計算の結果から簡単に逆算ができないような数学上の問題の一つで、整数のべき乗を素数で割った余りを求める計算を用いるもの。公開鍵暗号やデジタル署名（電子署名）のアルゴリズムの基礎として応用されている。 ある素数qについて、q未満の自然数gおよびxを選択し、gのx乗をqで割った余りmを算出する。このとき、q、g、xからmは容易に算出できる一方、g、q、mが分かっても、このような関係を満たすxを求める効率的な方法は見つかっていない。

  1. Diffie-Hellman Assumption aka (DH assumption)

cyclic group: 巡回群

DH鍵の生成と暗号化、復号化をopensslでやってみる！！

暗号の課題をやらないといけない。

  1. 環Z/nZの単数群 G = (Z/nZ)*上でのRSA暗号方式、という文章を理解するところから始まりますね。これが結構出てくるのでここを理解する所から始まりますね。

12/22

ZERO知識証明の位置づけ