現代暗号 読書メモ
https://gyazo.com/855561707c78e15b2875f0bbde8002c4
第1章 現代暗号の全体像 (2020/07/09)
- スイカは2001年
用語
$ \rm{gmsb}(x): 半分より小さい ? 0 : 1
e.g. pが3のとき$ x = 1 \Rightarrow 0、$ x = 1 or 2 \Rightarrow 1
negligible: 無視できる
ストリーム暗号: 1ビット単位で暗号化を行う
バーナム暗号
ブロック暗号: 一定の長さごとに暗号化を行う
DES
第2章 数学的準備 (2020/07/09)
- 素体 $ \mathbb{Z}_p は逆数ある(拡大体 $ GF(p^l)も)
Legendre記号
Carmichael関数
有限体(2020/07/11)
有限体 = ガロア体 $ GF(q) = $ F_q
拡大体もあるよ
uniform: Turing計算量
non-uniform: 回路
所属問題, 探索問題
co-NP: L in NP, bar L
co-: 命題の否定 に属する言語
確率を考慮した言語クラス(乱択アルゴリズム)
- RP: OK -> P < cons`, NG -> P = 0
- BPP: OK -> P < const, NG -> P < const
- ZPP: RP && co-RP e,g, { 素数 }
- IP: ???
- PSPACE: テープの長さが多項式
- IP = PSPACE
- AM: const回質問で判定
https://gyazo.com/05f095e7334b7cd710930d9e82cfedda
第3章 疑似乱数(p62-80) 2020/07/12
- 線形複雑度
- 線形だと予測できてしまう -> 非線形変換
- r^N が (L, N, e)-PLR性: seed: z^L, r^Nのe個と真乱数のe個が区別つかない
3.3.1 一方向性関数(強い)
$ Pr[ A(f(x)) \in f^{-1}(f(x)) \lt \epsilon (|x|)]
任意のビット幅に拡張できるんで疑似乱数を1ビット拡張できればいい
第4章 秘密鍵暗号の情報理論に基づく安全性 2020/07/14
def 4.1: 攻撃者目線(h-epsよりH()がでかい)と復号者目線(epsより間違わない)
h = H(M) のとき 暗号(E. D) は完全秘匿
無記憶性: 過去の結果からなにもわからない -> H(M^n) = nH(M).
バーナム暗号
https://gyazo.com/5a88198522553b0dfda8c90af526b8fb
第5章 ストリーム暗号とブロック暗号の使用モード
ストリーム暗号: ビットごとに暗号化と復号化を行う暗号(バーナム暗号等)
出力フィードバック(OFB): ブロック暗号器の出力をレジスタに保存しまた使う
暗号文フィードバック(CFB): 暗号文を使う
暗号文ブロック連鎖(CBC): ブロック暗号で前のを使うので毎回変わる
(P96)
第6章 秘密鍵ブロック暗号 2020/07/15
[選択]?[暗号文|平文]攻撃
DES
m: 64bit, c: 64bit, key: 56 + 8(parity)bit
同じ変換2回でもとに戻る: involution
FEALもinvolutionな手法
線形解読法
MISTY
第7章 公開鍵暗号
適応的選択暗号文攻撃: CCA、一番怖い
暗号文で平文に意図的な変更を加えられない: 頑強性(non-malleable)
秘匿性
完全解読: わかっちゃう
部分解読: もれる, どのような部分解読も出来ない時 -> 強秘匿
RSA暗号
$ pk: d = \frac{1}{e} mod\ \lambda(n), \lambda(n = pq) = LCM(p - 1, q - 1)
$ sk: e, n
$ Enc(e, n): c = m^e % n
$ Dec(d, n): m = c^d % n
Rabin暗号（1979）
逆数暗号
素因数分解ができてしまうと秘密鍵計算できてしまう
ElGamal暗号(1982)
prime p, $ \mathbb{Z}_p^{*} での原始元(a^i == 1なa) g.
$ x \in_{U} \mathbb{Z}_{p-1}, $ y = g^x \rm{mod}\ p
$ sk: x
$ pk: y, g, p
Enc: $ (c_1, c_2), c_1 = g^r\ \rm{mod}\ p, c_2 = y^r m\ \rm{mod}\ p
Dec: $ (c_2/c_1)^x\ \rm{mod}\ p
位数がわかってしまうと計算できてしまう -> 離散対数問題
楕円曲線
楕円 ElGamal暗号
有限体上の計算を楕円曲線上の加法に対応
x^r |-> rx
確率暗号
def 7.5 強秘匿(semantically secure)
情報もれない <=> 区別するヒントがない
どんなアルゴリズム A でもどちらの暗号文か判定不能($ < \epsilon(n))な暗号
(P148)
第8章 ゼロ知識証明 2020/07/16
ゼロ知識 + 対話証明
def 8.1 対話証明
証明者 P: 計算能力に制限のないTM, 検証者 V: 多項式時間制限のTMのとき言語Lに対する対話証明
完全性: Pr[(P, V) が x 受理] > 2/3 で正しく判定
健全性: x \nin L な x を < 1/3 で間違える
多項式回繰り返すことで確実になる = 1
PとVの対話をTM M でシミュレーション
多項式時間でシミュレート => ゼロ知識証明
- 完全識別不可能性: T, M ∞計算でわかる proof by 確率変数が全て同じ
- 統計的識別不可能性: T ∞, M: poly でわかる
- 計算量識別不可能性: T, M: poly
def 8.8 ブラックボックスゼロ知識性
e.g. グラフが同型か置換の結果を聞いて判定
$ View_{(P, V)}(x, y) 対話でVが知れる確率変数(??)の族
$ M^{V^{*}}(x) 対話再現マシンの
対話再現マシン DTMが作れない -> 識別可能 -> 確率変数が違うことが分かる
マシンは自力で作る
第9章 相手認証 2020/07/18
デジタル署名 < 電子署名
人を証明
- パスワードとか
UNIXパスワード方式
ソルト(乱数)を付加 -> 長くすると状態数多く
ワンタイムパスワード式
秘密鍵暗号方式
秘密の鍵を事前に共有
公開鍵方式
SHA-256: 256bitのハッシュ値
Feige-Fiat-Shamir認証(素因数分解が難しいので)
第10章 メッセージ認証
秘密鍵認証に基づく
電子データの正当性を保証するのがメッセージ認証とディジタル署名
なりすまし攻撃の成功確率 $ P_I \leq \frac{|M|}{|C|}, 改ざん攻撃の成功確率 $ P_S \leq \frac{|M| - 1}{|C| - 1}
第11章 ディジタル署名 2020/07/19
署名できるのは秘密鍵をもつひとのみ。
署名を検証するひとは公開鍵で復号できるかを検証する。
安全性
レベルが3つある
一般的偽造不可
選択的偽造不可
存在的偽造不可
一方向性関数が存在 <=> 安全なディジタル署名
- RSA署名
[$ d = \frac{1}{e}\ \rm{mod}\ \lambda(n)
署名:$ s := h(m)^d\ \rm{mod}\ n
検証: $ h(m) == s^e\ \rm{mod}\ n
素因数分解が難し
- ESIGN署名
- ElGamal署名
離散対数問題に基づく
- DSA署名 extends ElGamal署名
- Fiay-Shamir署名
- Schnorr 署名
離散対数問題を楕円曲線上でやると 楕円XXX署名となり安全性が等価
ブラインド署名
Aが自分の文書の内容を署名者Bに秘密にしつつ署名できる方式
第12章 ハッシュ関数(2020/07/19)
汎用一方向性ハッシュ関数 (universal one-way hash function)
$ \rm{(hard \ to \ find \ y)}\quad h(x) = h(y)
衝突困難ハッシュ関数 (collision intractable hash function)
$ \rm{(hard \ to \ find \ x, \ y)} \quad h(x) = h(y)
SHA
in: $ |m| < 2^{64}な $ m
out: 160bit
第13章 鍵配送 2020/07/20
- 秘密鍵: Kerberos(鍵配送サーバー)などが有名
- 公開鍵: Diffie-Hellman鍵配送や公開鍵簿、IDに基づく方法
Kerberos
Diffie-Hellman鍵配送(1976)
離散対数問題が難しい
1. (A -> B) Z_p, x乱数, a = g^x mod p, a to B
2. (B -> A) b = g^y mod p, b to A
3. (A) k_A = b^x mod p, k_A を 共通鍵
4. (B) k_B = a^y mod p, k_B
5. k_A == (g^y)^x == (g^x)^y == k_B より鍵を共有できたことに
第14章 秘密分散法
(k, n) - しきい値法: n個のうちk個あつめて復元(極小アクセス集合)
第15章 暗号プロトコル 2020/07/21
マルチパーティプロトコル: 複数人によるプロトコル
紛失通信
検証可能秘密分散(VSS)と紛失通信(OT)
AからBに送る時 $ \frac{1}{2} で紛失するがAは知ることが出来ない
1. (A): n = pq(p, q: prime), n -> B
2. (B): x \in_U Z_n, y := x^2\ \mod\ n, y -> A
3. (A): z := {ランダムな x | y == x^2 \mod n }, mをRabin暗号でcに, (z, c) -> B
4. (B): GCD(n, x-z) == p or q => 素因数分解でき mを入手 otherwize 情報を得られない (得られる確率1/2)
(1987) 公開鍵暗号が存在 => 任意の関数でマルチパーティプロトコルが存在する
- t人(< 1/3)の不審者を許す方式
秘匿計算
第16章 電子投票
- 高次剰余利用方式: 1bitじゃないと処理量大幅増加
- Mixnet利用方式
- ブラインド署名利用方式
第17章 電子契約
- 基本的な概念として段階的秘密交換プロトコル
- 送達確認電子メール
- 1 out of 2 紛失通信
- 一方向性関数に基づく方式
第18章 電子現金
- 電子財布
- オンライン検証型電子現金方式(iTunesカード)
第19章 情報理論に基づく暗号理論
盗聴通信路
符号化定理
in: X --(通信路)-> Y
相互情報量 I(X; Y) = H(Y) - H(Y | X)
通信路容量: C = max_p I(X; Y)
第20章 量子暗号
- 偏光させると確率で分岐するのでわかりません
参考: 暗号技術入門(2015)にはあるやつ
- PGP
- SSL/TLS
- 仮想通貨