Enigma詳細解説 part2 - Somewhat Homomorphic Encryptionを手計算でやってみた
みなさんこんにちは。カナゴールドです。今日は、Enigmaの雰囲気は分かったけど、具体的にどんな理論を使ってるのかちゃんと理解したいんや!という勉強熱心な人向けの記事で、最低限中学校までの数学の知識が必要になります。
そんなわけで、Somewhat Homomorphic Encryptionの雰囲気を理解するために、手計算でやってみちゃおうぜ?という企画です。
まず、前提知識の共有として、あらゆる計算はANDとXORがあれば表現できます。知らない人は適宜ググってください。
二つの1ビットの数字(0か1をとる)m1とm2があった時、
AND
(m1, m2)=(0, 0)→0
(m1, m2)=(0, 1)→0
(m1, m2)=(1, 0)→0
(m1, m2)=(1, 1)→1
XOR
(m1, m2)=(0, 0)→0
(m1, m2)=(0, 1)→1
(m1, m2)=(1, 0)→1
(m1, m2)=(1, 1)→0
と書け、ANDは掛け算で、ORは足し算に相当します。
やりたいことは、m1、m2を暗号化したものをc1、c2とした時に、それらを掛け算、足し算した結果を復号した時に得られる数字が、上の対応表と一致することになります。
というわけで、SHEを使って暗号化してみましょう。
c1= q1*p + 2*r1 + m1
c2= q2*p + 2*r2 + m2
ここで、q1とq2はランダムな大きい数字で、r1とr2はランダムな小さな数字で、これらは一回限りのものです。pがいわゆる秘密鍵で、ランダムな大きな数字になります。
これを復号するステップは、まず最初にpで割った余りを求めて、次に2で割った余りを求めることになります。
とりあえずc1をpで割った余りを求めると、式を見ての通り、2*r1+m1になりますね。しかし聡明な読者は、2*r1+m1もpで割れる可能性があるのでは?と思うかもしれませんが、最初の設定では、r1は小さな数字としており、m1に至っては0か1なので、pを十分大きな値としている限りは絶対割り切れませんね。そして次に2で割った余りを求めると、見ての通りm1になります。
やったー!復号できたー!ということになります。q1とr1の値について知らなくてもpだけで復号できましたね。
ここまでで自明ですが、一応c1+c2を計算すると、
c1+c2=p*(q1+q2)+2*(r1+r2)+(m1+m2)
なので、pよりも2*(r1+r2)+(m1+m2)が小さい限りは、復号した結果は、m1+m2になりますね。正確には、m1とm2がどちらも1の時は、和が2になって最後の2で割るプロセスで割り切れるので、結果としては0が帰ってきます。よって、XOR対応表と同じ結果になりますね。
さて、今度は掛け算をやってみましょう。
c1*c2=(q1*p + 2*r1 + m1)*(q2*p + 2*r2+ m2)
=p*q1*(q2*p + 2*r2+ m2) +2*r1*(q2*p + 2*r2+ m2)+m1*(q2*p + 2*r2+ m2)
=p*[q1*(q2*p + 2*r2+ m2)+2*r1*q2+q2*m1]+2*[2*r1*r2+r1*m2+r2*m1]+m1*m2
となるので、2*r1*r2+r1*m2+r2*m1がpよりも小さければ、復号した結果はm1*m2になり、上のAND対応表と一致することがわかりますね。
ここで、復号できるためには、p>2*(2*r1*r2+r1*m2+r2*m1)でなければならないことがわかりましたが、右辺を見ると、r1*r2が出てきてることがわかります。r1とr2は小さい数字としましたが、さすがに掛け算を何度もやっていくと、結構なスピードで大きくなっていくことがわかります。これが、「SHEでは掛け算の回数が限られる」ことの理由になります。
ここまででお分かりになりましたでしょうか?記号ばかりでよくイメージがわかないという人も多いかと思うので、実際に数字を代入しながら見てみましょう。
秘密の情報をm1=1、m2=1としますか。秘密鍵は大きいランダムな数字にする必要があるので、p=99でいいや。99って結構大きいよね?q1とq2も大きな数字ということで、q1=20、q2=21にしましょう。r1とr2は小さい数字だから、r1=2、r2=3でいいや。
それではまず足し算から。
c1=20*99+2*2+1=1985
c2=21*99+2*3+1=2086
になりました。もともと1だったのに、結構大きな数字になりましたね。しかもどっちも違う数字に。では足してみましょう。
c1+c2=1985+2086=4071
です。復号するために秘密鍵99で割ります。
4071÷99=41 あまり 12
です。このあまりを2で割ると、
12÷2=6 あまり 0
なので、復号した結果は0になりました。
やった!求めていた数字になってる!
というわけで、確かに、秘密鍵で復号できましたね!
では次に、同じ設定で掛け算行ってみましょう。
c1*c2=1985*2086=4140710
です。結構大きいですね。復号するので99で割って、
4140710÷99=41825 あまり 35
です。あまり35を2で割ると、1余るので、確かにAND対応表と同じになった!すげー!!!
というわけで、調子に乗ってもう一回c1を掛けてみちゃいましょう。
c1*c2*c1=4140710*1985=8219309350
になります。かなり大きくなりました。復号すると、
8219309350÷99=83023326 あまり76
なので、あまり76を2で割ると、あまりは0です、、、??!!
おかしい。1に対してAND演算をいくらやっても1のはずなのに、0になりました。何が起こった??!!
というわけで数式展開してみましょう。
c1*c2*c1={p*[q1*(q2*p + 2*r2+ m2)+2*r1*q2+q2*m1]+2*[2*r1*r2+r1*m2+r2*m1]+m1*m2}*( q1*p + 2*r1 + m1)
=p*[(長いので略)]+2*[4*r1*r2+2*r1*m2+2*r2*m1+m1*m2*r1+2*r1*r2*m1+r1*m2*m1+r2*m1*m1]+m1*m2*m1
となるので、2で括ったところを計算してみると、
4*r1*r2+2*r1*m2+2*r2*m1+m1*m2*r1+2*r1*r2*m1+r1*m2*m1+r2*m1*m1=4*2*3+2*2+2*3+2+2*2*3+2+3=24+4+6+2+12+2+3=53
なので、
c1*c2*c1=p*[(長いので略)]+2*53+m1*m2*m1
となります。おや?これをp=99で割ってみると、、、
c1*c2*c1=99*[(長いので略)]+106+m1*m2*m1
=99*[(長いので略)+1]+7+m1*m2*m1
なので、あまりは7+m1*m2*m1となります。
これを2で割ると、m1*m2*m1=1なので、あまりは0!!!
というわけで、r1とr2がpより小さくても、掛け算を繰り返していくとダメになってしまうことがわかりましたね!そして、掛け算可能な回数を増やそうとしたら、pを大きな数にしてあげることが必要になるのは一目瞭然ですね。
はい。これはSHEでは掛け算の回数が制限され、掛け算可能な回数と計算負荷がトレードオフな関係にあることがわかりました。
今日から君もSHEマスターだ!!!