Author
ka
Website: kaosfield
Twitter: ka
GitHub: kaosf
ka
2019-10-19
Copyright (C) 2019 ka
https://kaosf.github.io/20191019-osc-slide
Repository: kaosf/20191019-osc-slide - GitHub
このスライドはオープンソースとして公開されています
誤字脱字，その他ミスの修正などはPull Requestとして随時受け付けています
また手元で自分のペースで読み返したりなどはご自由にどうぞ
以下のQRコードでスライドが見えます
アルファベットを決まった数だけずらす
+3ずらすなら…
平文: HELLO -(暗号化)→ 暗号文: KHOOR
暗号化が+3ずらすのであれば復号は-3ずらせばOK
暗号文: JRRGEBH -(復号)→ 平文: GOODBYE
この場合 +3 というのが鍵になる
暗号化も復号も同じ鍵を使うので共通鍵暗号という
最初に鍵を誰にも知られず共有しておかなければならない
盗聴者に鍵を知られると通信内容がバレてしまう
公開鍵で暗号化をするとその鍵では復号出来ないが秘密鍵を使うと復号出来るという性質を持つ暗号
イメージとしては誰でも鍵をかけられる錠前とそれを開けることが出来る鍵
錠前が公開鍵でそれを開ける鍵が秘密鍵のようなイメージ
シーザー暗号のような暗号は実は人力でも簡単に解読出来てしまう
暗号文に平文の性質(例えばアルファベットならeがよく出現するなど)が残ってしまう
良い暗号文は平文の性質が一切残らないものである
暗号文をただそれだけ眺めていてもそれはノイズと見分けがつかない
現在使われている暗号はその辺りは既に完璧である
実は暗号技術はオープンソースと切っても切れない関係にある
暗号化の方法を秘匿にする方法がかつてはとられていましたが現代の暗号というのは
暗号化する方法は誰もが知っているが復号は現実的に不可能である
ということが世界中の人によって確認されていることが重要
それが本当に強い暗号である
敢えて言うなら暗号化の方法を隠さなければならない時点で何かが弱い疑いがある
ここから易しめで行きます
小数や分数を考えない余り付きの割り算を覚えていますか？
\(7 \div 3 = 2 \cdots 1\)
\(13 \div 5 = 2 \cdots 3\)
\(30 \div 8 = 3 \cdots 6\)
7を3で割ると2余り1…のようなもの
小学校でやって中学校で少し忘れて高校以降また多項式になって考えたりするあれです
この「割る数」と「余り」にだけ着目した数学があります
モジュロ演算または剰余演算と呼びます
例えば…
\(7 \div 3 = 2 \cdots 1\)
\(10 \div 3 = 3 \cdots 1\)
\(13 \div 3 = 4 \cdots 1\)
このとき，7と10と13は3で割った余りが全て1です
ここで「7も10も13も3で割った余りが等しいから等しいとみなそう」と考えます
以下のように表記します
\(7 \equiv 1 \pmod{3}\)
\(10 \equiv 1 \pmod{3}\)
\(13 \equiv 1 \pmod{3}\)
\(7 \equiv 10 \equiv 13 \equiv 1 \pmod{3}\)
紛らわしいかも知れませんが誤解の心配がなければ通常の \(=\) で書くこともあります
\(7 = 1 \pmod{3}\)
このスライドでは \(=\) で書きます
\(7 = 1 \pmod{3}\)
これを日本語で「3を法とすると7と1は等しい」と言います
単純に「7と1は等しい」と言う言葉に条件を付け加えるニュアンスです
モジュロ演算では四則演算は可能でしょうか？
答えは
足し算と引き算と掛け算は可能，割り算も場合によっては可能
\(7 + 10 = 1 + 1 = 2 \pmod{3}\)
\(7 + 10 = 17 = 3 * 5 + 2 = 2 \pmod{3}\)
\(10 - 7 = 1 - 1 = 0 \pmod{3}\)
\(10 - 7 = 3 = 0 \pmod{3}\)
\(7 * 10 = 1 * 1 = 1 \pmod{3}\)
\(7 * 10 = 70 = 3 * 23 + 1 = 1 \pmod{3}\)
3で割った余りしか考えない世界なので実質出てくる数値は 0, 1, 2 だけです
…と言ってもそれで計算が何もかも簡単になるわけじゃないです
と言うよりそれで難しくなってしまうある計算を利用して暗号を作ります
それはまた後ほど
\(\pmod{3}\) の 3 と 互いに素 な数であれば割り算が可能です
例1
\(10 = 40 = 1 \pmod{3}\)
\(10 \div 5 = 2 \pmod{3}\)
\(40 \div 5 = 8 = 2 \pmod{3}\)
例2
\(24 = 34 = 4 \pmod{5}\)
\(24 \div 2 = 12 = 2 \pmod{5}\)
\(34 \div 2 = 17 = 2 \pmod{5}\)
ですが今回ここは詳しくは省略します
ですがですが 互いに素 という概念は重要なので後で説明します
\(14 = 8 \pmod{6}\)
\(14 \div 2 = 7 = 1 \pmod{6}\)
\(8 \div 2 = 4 \pmod{6}\)
1と4が6を法とする世界で同じ？？？そんなことはない
割り算はいつでも出来るわけではない ということです
モジュロ演算ではないよく知っている計算の世界では割り算とは即ち逆数の掛け算のことでした
逆数とは何だったでしょう？
簡単に言うと \(x\) の逆数は \(\frac{1}{x}\) でした
しかし本質的には 掛け算すると1になる数 のことを逆数と言います
モジュロ演算の世界でもこれを考えることが出来るでしょうか？
今は分数や小数を考えていません
なので \(2\) の逆数は？と聞かれても \(\frac{1}{2}\) ではなく…
\(2\) に掛け算するとモジュロ演算の世界で \(1\) になる数は何か？と考えます
\(2 * 0 = 0 \pmod{3}\) ダメ
\(2 * 1 = 2 \pmod{3}\) ダメ
\(2 * 2 = 4 = 1 \pmod{3}\) OK
なので 3 を法とすると 2 の逆数は 2 です…不思議ですがそうなんです
指数を覚えていますか？
\(2^{3} = 2 * 2 * 2 = 8\)
\(4^{2} = 4 * 4 = 16\)
右肩についている数の分だけ掛け算をする計算です
指数計算には指数法則という性質があります
\(2^{2} * 2^{3} = 2 * 2 * 2 * 2 * 2 = 2^{5} = 2^{2 + 3}\)
\(3^{3} * 3^{1} = 3 * 3 * 3 * 3 = 3^{4} = 3^{3 + 1}\)
掛け算の計算を足し算に置き換えて考えることが出来ます
詳しくは説明しません
\(2^{3} * 2^{1} = 2^{4} \pmod{3}\)
掛け算が出来るんだから指数の計算も指数法則も同じですよね？
\(2^{3} * 2^{1} = 8 * 2 = 2 * 2 = 4 = 1 \pmod{3}\)
\(2^{4} = 16 = 1 \pmod{3}\)
高校生以上の人は指数計算には 0 乗とか負数乗とか果ては実数乗まで存在していることを知ってるかもしれません
(複素数乗も知ってたら偉い)
だから成り立たない場合もあるのでは？と思ったかもしれませんが今モジュロ演算の世界では足し算の場合しか考えません
なので大丈夫
ちなみに一応ですが 0 乗はOKです
\(2^{2} * 2^{0} = 2^{2} \pmod{3}\)
\(a = b \pmod{p}\) とは \(a\) と \(b\) は \(p\) を法として等しいという意味
言い換えると \(a\) と \(b\) は \(p\) で割り算した余りが等しい
\(a = b \pmod{p} \Longrightarrow a + c = b + c \pmod{p}\)
\(a = b \pmod{p} \Longrightarrow a * c = b * c \pmod{p}\)
\(a = b \pmod{p} \Longrightarrow a^{c} = b^{c} \pmod{p}\)
モジュラ逆数というものが考えられ \(p\) を法とする世界で \(a\) のモジュラ逆数が \(b\) であるなら \(a * b = 1 \pmod{p}\) となる
急に難しそうな数学用語が出てきました…
ですが今回に限って言えば例としては単純なもので…
\(2^{3}\) と \(2^{2}\) の 掛け算 を先程考えました
ですがこれの計算は実質
\(2^{3 + 2}\)
つまり足し算を考えることだと言いました
\(3 + 2\) という計算の結果と \(8 * 4\) という計算の結果はお互いに対応しています
\[3 + 2 = 5 \longleftrightarrow 2^{3} * 2^{2} = 2^{5}\]
変数に置き換えて話を広げると
\[x + y = z \longleftrightarrow 2^{x} * 2^{y} = 2^{z}\]
これは指数法則そのものですが…
左側の足し算の世界と右側の掛け算の世界は一対一に対応しているのです
片方を計算するともう片方の計算もしたことになります
語弊はありますがこういう性質のことを同型といいます
誤解を恐れず簡単に言うと同型よりもゆるいものが準同型です
この辺りをガチで考えるととてもしんどいので今日は放っておきましょう
別に問題ありませんしそもそもここから先話がどんどんフワっとしていきます
なのですみませんがここから先は変数がバンバン出てきます
ですが実際にやっている計算は全て今まで説明したものだけです
ではサクサク進んでいきましょう
暗号化というのは平文となる数値を別の数値(暗号文)に置き換えること
平文 \(m\) を暗号化する操作を \(Enc(m)\) とする
暗号化ということは平文がノイズのように変わってしまう
そのノイズのようなもの同士でも計算を行うと
平文で計算したものを暗号化したのと同じ結果になる性質をもつ暗号が存在する
平文を足したものを \(m_1 + m_2\) を暗号化 \(Enc(m_1 + m_2)\)
個別に暗号化したものを掛け算 \(Enc(m_1) * Enc(m_2)\)
\[Enc(m_1) * Enc(m_2) = Enc(m_1 + m_2)\]
これが満たされて欲しい
Pailler暗号という暗号が存在する
Paillierの読み方は「ペイエ」
参考: Paillier暗号
Paillier暗号では
\[Enc(m_1) * Enc(m_2) = Enc(m_1 + m_2)\]
となる
暗号化したものを掛け算すると平文を足し算して暗号化したものと等しい
ちなみにこのように暗号化したまま行う計算のことを秘密計算という
匿名性を完全に維持して電子投票が可能になる
「電子投票」と「インターネット投票」は別の話なので混同注意
電子投票というのは紙と鉛筆と投票箱でやる投票を電子化しようというだけのもの
インターネット投票は更にその先でそれをインターネットを使って何処からでも出来るようにしようというもの
例えば投票の強制という問題がある
投票が解禁される瞬間にどこかに監禁や軟禁をされ
ある特定の候補者へ投票をするところを確認されるまで解放されない
というような状況
例えば きのこの山, たけのこの里, アルフォート のどれを買うかを9人で投票して決めるとする
ここで
という操作を考える
もしも投票結果が \(214\) になっていたなら…
\(214 = 2 * 100 + 1 * 10 + 4 * 1\)
であるはずなので
であったはずである
もし99人で投票する場合は
とすれば良い
集計結果が
自分が何に投票したかは 0, 1, 10 or 100 で表現されるがこれを暗号化したい
そして暗号化されたまま合算されて復号されるとうれしい
ここで加法準同型暗号の出番である
平文と暗号文を \(m\), \(C\) とする
2つの異なる素数 \(p, q\) の積が \(n\) でありそれを公開鍵をする
\[g = (1 + \alpha n) * \beta^n\] \[C = g^m \pmod{n^2}\]
\(\alpha\), \(\beta\) は準同型の性質を崩さないように調整できる定数
\(g\) は \(n\) と \(\alpha\), \(\beta\) から計算出来る公開鍵や公開情報とだけ認識してくれればOK
(もうちょっと言っておくと \(g\) は巡回群の生成元 generator です)
ただしこれでは同じ平文(投票先)からは常に同じ暗号文が生成されてしまう
そこで
\[C = g^m * r^n \pmod{n^2}\]
とする
ここで \(r\) は \(n\) と互いに素となる整数値から選ばれる乱数である
乱数を使って暗号化しても一意に復号が出来る(カーマイケルの定理より)
2つの数が互いに素とは何か？
互いに素というのは 最大公約数が1になる という意味です
公約数というのは2つの数に共通する約数のことです
約数というのは割り切ることの出来る数のことです
例えば…
10 の約数は 1, 2, 5, 10
15 の約数は 1, 3, 5, 15
共通する約数は 1 と 5 です
なので最大公約数は 5 になり 10 と 15 は互いに素ではありません
15 と 28 の場合
15 の約数は 1, 3, 5, 15
28 の約数は 1, 2, 4, 7, 14, 28
共通する約数，公約数は… 1 しかありません
最大の公約数が 1 です
なので 15 と 28 は互いに素です
復号するための秘密鍵 \(\lambda\) は以下の通り
\[\lambda = \operatorname{lcm}(p-1, q-1)\]
\(\operatorname{lcm}(x, y)\) というのは \(x\) と \(y\) の最小公倍数という意味です
最大公約数のある意味正反対のモノです
以下のように復号する
\[C^\lambda = 1 + \alpha \lambda mn \pmod{n^2}\]
\[g^\lambda = 1 + \alpha \lambda n \pmod{n^2}\]
(↑これは二項定理を展開してみると証明出来ます)
\[L(x) = \frac{x - 1}{n}\]
\[\frac{L(C^\lambda)}{L(g^\lambda)} = \frac{\alpha\lambda m}{\alpha\lambda} = m\]
ただしこれはモジュロ演算の割り算なのでモジュラ逆数を見つけて掛け算する操作になるので注意
\[L(C^\lambda) * (L(g^\lambda))^{-1} = m\]
\[C_1 = g^{m_1} * r_1^n \pmod{n^2}\] \[C_2 = g^{m_2} * r_2^n \pmod{n^2}\]
\[C_1 * C_2 = g^{m_1 + m_2} * (r_1 r_2)^n \pmod{n^2}\]
これを復号すると
\[m_1 + m_2\]
が得られることになる
暗号化したまま足し算が出来ることは分かったが，そもそも
\[C = g^{m} * r^{n} \pmod{n^2}\]
これは本当に暗号になっているのか？
だって掛け算してるだけでは…？
モジュロ演算であることが重要です
掛け算を何回も何回もやっているだけの計算ですが実はその都度 \(n^2\) で割った余りを考えているので
\(1\) から \(n^2 - 1\) の範囲を何周もします
するとその計算結果は最早規則が無いように見えます
ここでモジュロ演算になると難しくなる計算があると言ったのを思い出して欲しいのですが…
実は \(g^m = c \pmod{n^2}\) の計算，左辺を計算して右辺を求めることは簡単なのですが…
逆に右辺 \(c\) だけを与えられた時に「これは \(g\) を何乗したものですか？」というのが簡単には求まらないのです
これを 離散対数問題 と言います
しかし \(n\) を素因数分解した \(p\) \(q\) を知っていると先程紹介した復号方法で \(m\) を計算することは出来ます
そしてこれは聞いたことのある人も居ると思いますが大きな2つの素数の積を素因数分解することはこれまた簡単には出来ないのです
まだ説明をしていないままの箇所をまとめて説明
以下は全てライブラリで提供されています
ユークリッドの互除法というアルゴリズムで可能
\(\operatorname{lcm}(x, y) = (x * y) / \gcd(x, y)\)
\(\gcd(x, y)\) は最大公約数
拡張ユークリッドの互除法で可能
この話をする
相手に情報を与えずに(※相手が得る知識はゼロ)自分が持っている情報が正しいことを証明する方法
参考: ゼロ知識証明
今回は自分の票を明かすことは無く，しかし自分は有効な票を暗号化してあることを示したい
暗号文だけを使ってその平文が正当でない場合にそれを確率 1/2 で見破れる計算が存在するとする
言い換えると 1/2 の確率でデタラメでも正解になってしまう問題が存在するとする
投票先が正当な場合には 100% 正解できる問題である
その問題を大量に(ほぼ無数に)作り出せる(予め答えを全部計算しておくなんてことは出来ない)とする
この問題を10連続で正解出来るかどうかを確認する
正当でない場合にその人が偶然全て正解出来てしまう確率は 1/1024 であるし20連続なら更にとんでもなく低い確率になる
数学のくせになんか曖昧な気がする…これはアリなのか？
アリです
よく考えて欲しいのですがそもそも何であっても確率を0にすることは出来ません
暗号には必ず鍵が存在します
その鍵を偶然見つけられる確率というのは決して0にはならないのです
粘土をランダムにこねた場合にそれが何かの錠前の鍵になってしまっている確率は0ではないのです
でもそんな確率は0だと思って生きてても問題ないのと同じです
Paillier暗号はやってることは掛け算ばかり…だが？
デモ展示に使っていたアプリケーションのリポジトリです
Herokuのアカウントを持っていれば Deploy to Heroku ボタンで一発デプロイ出来ます