RSA-Paillier暗号

Paillier暗号の暗号化にRSA暗号の公開鍵を使ったものを，RSA-Paillier暗号（RSAP暗号）といいます．

Paillier暗号についてよくわからない場合はこちらへ

RSA暗号の公開鍵 (N, e) と乱数 R から暗号文を
C = R^e (1 + N)^M mod N^2
と生成します．

これだけで終了です．

えっ，復号はできるの？平文が累乗になっているし．

はい，復号できます．
しかし，少し面倒な手順が必要になります．

まずは，暗号文 C と秘密鍵 d から
R = C^d mod N
と乱数を復元します．

この乱数を暗号化の式
C = R^e (1 + MN) mod N^2
に入れて平文Mについて解くだけです．ね，簡単でしょ？

R = C^d mod N^2 じゃなくて mod N でしょうか？

さっきの暗号化の式から
(R^e (1 + MN) mod N^2)^d mod N
と変形できます．

そうすると，内側が mod N^2 になっていますが，mod Nでどうせ N の倍数の部分は消えてしまうので関係ありません．
1だけ残るので R^ed mod N だけになります．

RSA暗号の定義から
ed mod (p - 1)(q - 1) = 1 （p，qは素数）
なので
R^ed mod N = R
です．

mod N^2 と mod N を組み合わせるところがみそです．



インターネット家庭教師Netty

Paillier暗号

Paillier暗号（パイリヤあんごう）はPascal Paillierが提案した公開鍵暗号方式の一つです．また準同型暗号（その1，その2）でもあります．
この暗号化方式は，暗号文を掛け算すると，平文の足し算に対しての暗号文を作れるという変わった方式です．

pとqを素数とし， N = p × q とします．

Paillier暗号は次の性質
(1 + N)^M mod N^2 = 1 + MN mod N^2
という性質を使っています．

これは簡単に証明できます．

二項定理を使うと
(1 + N)^M = 1 + MN + M(M - 1) N^2 / 2 + …
と計算できるので，mod N^2 をとると N^2 以上の累乗の部分はすべて0になります．

よって，上の式が成り立つことが確認できます．

通常は上の式のまま暗号化の式で使うことはありません．
乱数を掛け算して，平文のデータをマスクして暗号文として使います．

乱数でマスクした暗号文を
C = R(1 + N)^M mod N^2
とします．
そうすると，平文M1，M2に対する暗号文は
C1 = R1(1 + N)^(M1) mod N^2
C2 = R2(1 + N)^(M2) mod N^2
と表すことができます．

C1 と C2 を掛け算すると
C1 × C2 mod N^2
 = R1 × R2 (1 + N)^(M1) × (1 + N)^(M2) mod N^2
 = R1 × R2 (1 + N)^(M1 + M2) mod N^2
となり，これは平文 M1 + M2 に対する暗号文ということになります．

乱数でマスクしてあるので選択平文攻撃に対して識別できないという意味で安全（IND-CPA安全）になります．

しかし，暗号文を掛け算すると平文の足し算に対する暗号文が作れてしまうので，頑強性（NM-CCA安全性）および選択暗号文攻撃に対して識別できない安全性（IND-CCA安全性）は満たしません．

インターネット家庭教師Netty

Triple Encryption

Mihir Ballare，Phillip Rogaway著の「Code-Based Game-Playing Proofs and Triple Encryption」から，今度はTriple Encryption（三重暗号化）に触れていきます．

三重に暗号化したら安全になるの？

いいえ，無条件に1回暗号化よりも安全になるとは言えません．

まずは，2回暗号化する場合を考えていきましょう．
暗号化関数をEとします．
暗号化の鍵をK1，K2とします．
平文Mを2回暗号化した式は E(K1, E(K2, M)) と表すことができます．

ここで，別の鍵K3で暗号化すると E(K3, M) となります．

全ての平文Mに対して
E(K3, M) = E(K1, E(K2, M))
となるような鍵K3が見つかってしまったら，ダメです．
このとき，暗号化関数Eは合成演算子に関して群をなしていると言います．
2回暗号化が1回暗号化と同等になってしまいます．
時間がかかるだけで安全性は向上していません．

K3が見つからなければ，安全性は向上します．

3回暗号化のときも同様に
E(K4, M) = E(K1, E(K2, E(K3, M)))
となるようなK4が見つからなければ暗号化の回数を増やすごとに安全性が向上していきます．

AES暗号が開発されるまで標準として用いられていたDESは，暗号化の回数を増やすことで安全性を向上させることができます．
DESを3段重ねたTriple-DESは現在では推奨されていませんが，細々と使われています．

Triple Encryptionの安全性解析はTriple-DESのために考えられた概念であるといえます．

次回からはTriple Encryptionについて私のわかる範囲内で説明していきます．

~約8,000名の受講生と80社以上の導入実績~
現役エンジニアのオンライン家庭教師CodeCamp

参考文献

Mihir Bellare, Phillip Rogaway: The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. EUROCRYPT 2006: 409-426

Code-based game-playing proof その2

Gameを使った証明方法として，必須事項であるのが「Fundamental Lemma」（無理やり訳すと，基本的補題）！
「Bad」というフラグがGameの同じところで立てられるときに次のような確率の式が成り立ちます．

補題 Aを敵だとする．Game G，Game Hの同じところで「bad」が起きるとする．
このとき
Adv(A(G), A(H)) ≦ Pr[A(G) sets bad]
である．
また，Game G，Game H，Game Iの同じところで「bad」が起きるとする．
このとき
Adv(A(G), A(H)) ≦ Pr[A(I) sets bad]
である．

そもそも「bad」って何でしょうか？

実は，「bad」にこだわる必要はありません．名前はなんでもよいです．
例えば，「collision」とか「distinct」とか「forgery」とかでもよいです．
運悪く衝突ペアが見つかってしまったり，敵が認証暗号化方式を識別できたり，あるいは偽造ができてしまったりすることがあります．
設計者側から見て悪いことが起きるから，「bad」ということでしょう（これは私の考えです．Bellareさんの意図はわかりませんが）．

この補題がどうやって成り立つのかざっくりと見てみましょう．

Cというのをランダムコインの集合，つまり全部の起きうるものを集めたまとまりとしましょう．
CGというのをGame Gで1を出力するランダムコインの集合，つまりGame Gで起きうるものをすべて集めたまとまりだとします．
CHというのも同様にGame Hで1を出力するランダムコインの集合とします．

Game GとGame Hの識別利得は，それぞれで1を出力する確率の差で表されるので
Adv(A(G), A(H)) = (CGの要素数 - CHの要素数) / Cの要素数
と表すことができます．
CG(bad)をGame Gで「bad」を立てるランダムコインの集合，CH(bad)をGame Hで「bad」を立てるランダムコインの集合とします．
じゃあ，CG(good)はCGからCG(bad)の分を引いたものになります．CH(good)も同様です．

そうすると，この識別利得は
Adv(A(G), A(H)) = (CG(good)の要素数 + CG(bad)の要素数 - CH(good)の要素数 - CH(bad)の要素数) / Cの要素数
と表すことができます．
goodというのは運悪いことが起きなかったということなので，敵からの見え方はGame GかあるいはGame Hかどうかは完全にわかりません．
よって，CG(good)の要素数 = CH(good)の要素数 ということになります．

最終的に
Adv(A(G), A(H)) = (CG(bad)の要素数 - CH(bad)の要素数) / Cの要素数 ≦ (CG(bad)の要素数) / Cの要素数
となります．
最後の項はGame Gで「bad」を立てる確率です．

「bad」を立てた後の動作がGame G，Game H，Game Iで全く一緒だったら（敵からの見え方が一緒だったら）
CG(bad)の要素数 = CH(bad)の要素数 = CI(bad)の要素数
となって，補題の下側の式が成り立ちます．

これは厳密な証明ではありません．
Mihir Bellare，Phillip Rogaway著の「Code-Based Game-Playing Proofs and the Security of Triple Encryption」（Cryptography ePrint Archive）に詳しく載っています．

~約8,000名の受講生と80社以上の導入実績~
現役エンジニアのオンライン家庭教師CodeCamp

参考文献

Mihir Bellare, Phillip Rogaway: The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. EUROCRYPT 2006: 409-426

準同型暗号 その2

先ほどの記事では準同型について大まかに話しました．

準同型暗号は公開鍵暗号の概念です．
例えば，RSA暗号やElGamal暗号は準同型の性質をもっています．

RSA暗号の場合は，公開鍵はpk = (N, e)です．
平文M1に対する暗号文は
C1 = (M1)^e mod N
で，平文M2に対する暗号文は
C2 = (M2)^e mod N
と表すことができます．
これらを掛け算すると
C = C1 × C2 mod N = (M1)^e(M2)^e mod N = (M1 × M2)^e mod N
となり，これは平文 M1 × M2 に対する暗号文ということになります．

また，ElGamal暗号も同様で，公開鍵が pk = (p, g, y) より
平文M1に対する暗号文は
C1 = (g^(r1), M1 × y^(r1)) mod p
で，平文M2に対する暗号文は
C2 = (g^(r2), M2 × y^(r2)) mod p
と表すことができます．
これらをそれぞれの成分で掛け算すると
C = (g^(r1) × g^(r2), M1 × M2 × y^(r1) × y^(r2)) mod p
= (g^(r1 + r2), M1 × M2 × y^(r1 + r2)) mod p
となり，これは平文 M1 × M2 に対する暗号文ということになります．

暗号文を演算することで別の平文に対する暗号文を作れるということです．

この性質は電子マネーとか電子投票に用いられています．
もちろんこれだけで使うことはできないので（認証の機能がないから），実際の利用ではメッセージ認証方式やディジタル署名方式も使われます．

しかしながら，ハッシュ関数に使ってはいけません．
すでにあるハッシュ値から，別のメッセージに対するハッシュ値が作れてしまうからです（メッセージのハッシュ値をハッシュ関数に通さずに作れる）．