RSAにおける暗号化オラクルを使ったなにか

おなじみのRSA暗号について.
今回はRSAでも特に暗号化オラクルに焦点を当てる. 単体で記事にするようなトピックでもないが面白いと思ったので.

暗号化オラクルとは簡単にいうとユーザが自分の好きな平文を暗号化して(平文を送ると暗号文が返ってくる)遊ぶことができるものである. (選択平文攻撃)

RSAではExponentのeとModulusのnを公開鍵として平文mを以下のように暗号化する.

Enc(m) := m^e mod n

復号についてはこの記事では取り扱わない.

(e, n)は公開鍵で, 読んで字のごとく公開されているのでみんなが知ってる値なのだが, これらが隠されている場合でも暗号化オラクルが利用できればModulusは特定が可能である.

状況を整理する.

• 公開鍵(e, n)はわからない
• 暗号化オラクルが使える(好きな平文mに対応する暗号文cが得られる)

手順

簡単な手順を先に置いておく.

1. 適当な値 k を準備する.
2. 暗号化オラクルを使って s = Enc(k), t = Enc(k²) を得る.
3. s² - t を計算し, N = GCD(N, s²-t) でNを更新する. (Nの初期値は0)
4. 1に戻る.

s, t それぞれの処理を追ってみる.

s = Enc(k) = k^e mod n
t = Enc(k²) =k^2e mod n

次に s² - t を計算する.

s² - t = (k^e)² - k^2e mod n
= k^2e - k^2e mod n
= 0 mod n

s² - t が n で割り切れる数字になっていることがわかる.

kを変えて処理を繰り返すと約数にnを持つs² - t がいくつか得られ, これらは共通の約数nを持っているのでGCDを取れば最終的にnが特定できる.

たまに共通の約数が2*nだったり5*nだったりするので5, 6回繰り返すと大抵nが出てくる.

実際に計算してみる

大きな値だと面倒なので比較的小さな p=11, q=13 で計算する.

(e, n) = (3, 143) で, 先に説明したようにこれは公開されていない公開鍵である.

k = 5

s = Enc(k) = 5³ mod 143 = 125
t = Enc(k²) = 5⁶ mod 143 = 38

s² - t = 125² - 38 = 15587
15587 % 143 = 0

nの候補の更新としてGCDを取る.

GCD(0, 15587) = 15587

k = 6

s = Enc(k) = 6³ mod 143 = 73
t = Enc(k²) = 6⁶ mod 143 = 38

s² - t = 73² - 38 = 5291
5291 % 143 = 0

GCDを計算.

GCD(15587, 5291) = 143

今回は偶然この時点でnが特定できているが, 念の為あと3, 4回は繰り返したほうが良い.

まとめ

なぜこの記事を書いたのか ｺﾚｶﾞﾜｶﾗﾅｲ

現実的ではないだろうがExponentの特定も考えたい(future works).
Pohlig–Hellman algorithmを使うのも難しそうだ.

公開鍵暗号 (一般)ElGamal暗号の勉強

公開鍵暗号の1つであるElGamal暗号について.
ElGamal暗号 - Wikipedia

一般ElGamal暗号については後述する. 詳しく知りたい人は 暗号技術のすべて を買おう. 余談だが私はほしい物リストに入れてたら誰かが買ってくれた. 誰なのかは未だわからない.

Key Generation

セキュリティパラメータをk [bits]とする.

• k [bits] の素数p を選択する
• Z_pから元を2つ選びg, xとし h = g^x mod p を計算する

公開鍵 : (g, h, p)
秘密鍵 : x

Encrypt

平文mを受け取る暗号化関数は以下のように定義される.
Z_pから元を1つ選択しrとする.

Enc(m) := (c1, c2) = (g^r mod p , m*h^r mod p)

(c1, c2) を暗号文とする.

Decrypt

暗号文c1, c2を受け取る復号関数は以下のように定義される.

Dec(c1, c2) := c2 * (c1^x)^-1 mod p

Dec(c1, c2) = m になることを確認しよう.

まずはc1から

c1^x = g^rx

次にc2

c2 = m * h^r
= m * (g^x)^r
= m * g^rx

最後に

c2 * (c1^x)^-1 mod p
= m * g^rx * (g^rx)^-1 mod p
= m

平文が復号できた.

乗法準同型

ElGamal暗号は乗法準同型を持っていて, 平文mを暗号化した(c1, c2)のc2をt倍して復号すると平文mをt倍したものが得られる.

たとえば3倍する場合だと次のようになる.

c1, c2 = Enc(m)
Dec(c1, 3 * c2) = 3 * m

確認しよう.
c2をt倍して復号する. c2' = t*c2

Dec(c1, c2') = c2' * (c1^x)^-1 mod p
= c2' * (c1^x)^-1 mod p
= t * m * g^rx * (g^rx)^-1 mod p
= t * m mod p

復号オラクルが使用できる場合, 選択暗号文攻撃に弱い.

一応検証コードを置いておく.

test_elgamal

実は選択暗号文攻撃以外にも, 鍵生成を失敗すると攻撃者に暗号文を解読されてしまう可能性がある. 次の説でElGamal暗号の安全性について話をする.
Wikipediaではちゃんとセキュリティを考慮した鍵生成の解説がなされている.

安全性

結論を先に言うと, ElGamal暗号で重要なのは素数pの選択である.

Z_*pの位数は p-1 であり, Z_*pの元gが作る部分群の位数は p-1 以下になるのだが, ラグランジュの定理により, gによる部分群の位数は p-1 を割り切る数字となる.

p-1 は偶数なので, 位数が2である群と (p-1)/2 が位数の部分群が少なくとも存在する.
他にも約数を持つ場合, gによる部分群の位数が小さくなる.

また, φ(p) = p-1 が複数の小さな素数の積で表すことができるとき, Pohlig–Hellman algorithmによって解読が簡単化される. Pohlig–Hellman algorithm - Wikipedia

これを回避するために, 最初の素数選択では安全な素数(safe prime)を使うことが推奨されている.

safe primeとはある素数pに対して, 2p + 1 も素数である時の2p + 1のことである.
たとえば, 3は素数であり 2*3 + 1 = 7も素数なので7はsafe primeといえる.
言い換えると (p-1)/2 が素数であるp.

q = 2*p + 1; (p ,q はそれぞれ素数) としてElGamal暗号を考える.

このとき

φ(q) = 2*p + 1 - 1 = 2*p

であり, φ(q)の約数は2と大きな素数pに限定される.

φ(q)が2*pではPohlig–Hellman algorithmは効果を発揮できないため弱点を克服できた.

次は部分群の位数が素数になるようにしよう.
pが素数のとき g^x ≡ 1 (mod p) の最小のxがp-1であればgは原始元となる. 原始元とはもとの群と部分群の位数が同じになるような元である(素体を扱っているので原始元と呼んでいる. 生成元でもよい).

|{g, g², g³, ..., 1}| = p-1
のとき g は原始元

適当な原始元を選択し, 次のような式を考える.

α = g^(q-1)/p mod q

q = 2*p + 1 であれば

α = g^{(2p + 1 -1)/p} mod q
α = g² mod q

Z_*qの原始元gを2乗したαを使って部分群を生成すると位数が素数になる.
これはαのp乗が1になれば確認できる.

α^p = (g^(q-1)/p)^p mod q
α^p = g^q-1 mod q
= 1

Z_*qの原始元gによって作られる部分群の位数はq-1になるが, g²によって作られる部分群の位数はpでありこれは素数である.

まとめ

一般ElGamalに関する記述が見当たらない. 安全性のあたりから曖昧な記憶を頼りに書いてしまったのでまたちゃんと勉強して書き直す.

公開鍵暗号 Paillier暗号の勉強

Pascal Paillierが提案した加法準同型をもつPaillier暗号について.

元論文を読んだのでまとめてみる.
が, 基本的な内容に関してはelliptic-shiho先生の記事を読むことで理解できる.
elliptic-shiho.hatenablog.com

カーマイケルの定理

Paillier暗号ではカーマイケルの定理が登場する.
これはオイラーの定理とよく似ていて, nを法として以下の式で表される. (ただしaとnは互いに素)

a^λ(n) ≡ 1 (mod n)

λ(n)はカーマイケルのλ関数であり, こちらもオイラーのφ関数と似ている.
φ関数を使うと

a^φ(n) ≡ 1 (mod n)

aをx乗して1と合同になる値(x)を得ることができるが, このxが最小とは限らない(aによって作られる部分群の位数がφ(n)ではないことを意味している).

λ関数はφ関数をより厳密にしたもので, 最小のxを得ることができる.

RSAではよくオイラーが登場する(個人の見解)が, カーマイケルを使って解説している場合もあるので覚えておくと良い.

少し脱線

RSAにおいてp, qは大きな素数であり, λ, φの入力をn(=p*q)として

φ(n) = (p-1)*(q-1)
λ(n) = LCM(p-1, q-1)

このように得られる. LCMとGCDの関係をx, yを使って表し.

LCM(x, y) * GCD(x, y) = x * y

x, y をそれぞれp-1, q-1とすれば

LCM(p-1, q-1) = (p-1)*(q-1) / GCD(p-1, q-1)
= φ(n) / GCD(p-1, q-1)

p, qが大きな素数であるということはGCD(p-1, q-1)は最小でも2になる.

λ(n) <= φ(n) / 2

λ(n)がφ(n)よりも小さいことが示せた.

話を戻す

Paillier暗号では法をn²としてカーマイケルの定理を使用しているので, a^x ≡ 1 (mod n²) を満たすxはλ(n)ではなく以下のようになる.

a^nλ(n) ≡ 1 (mod n²)

これを示すには

λ(n²) = nλ(n)

であることが言えればよい.

λ(n²) = λ(p² * q²)
= LCM(λ(p²), λ(q²))
= LCM(p^2-1(p-1), q^2-1(q-1))
= LCM(p(p-1), q(q-1))

ここでp, qは互いに素な大きな素数であり, LCMの計算に関与しないため外に出せる.

LCM(p(p-1), q(q-1))
= pq * LCM(p-1, q-1)
= n * λ(n)

これで示せた.

ちなみにオイラーの定理でも同様に法をn²として

a^nφ(n) ≡ 1 (mod n²)

これを示すには

φ(n²) = nφ(n)

であればよく, こちらも愚直に計算すると

φ(n²) = φ(p² * q²)
= (p² - p¹) * (q² - q¹)
= p(p-1) * q(q-1)
= pq * (p-1)(q-1)
= n * φ(n)

となるので正しい.

次の節からPaiiler暗号の鍵生成から暗号化/復号の話をする.

Key Generation

2つの大きな素数p, qを選び, n = p*q とする.
Z_nの元を1つ選びこれをkとし, g = (k*n + 1) mod n² とする.

公開鍵 : (n, g)
秘密鍵 : (p, q)

Encrypt

Z_n²の元を1つ選び r とする. このrは暗号化のたびに変わる.
平文mの暗号化は以下のように定義される.

Enc(m) := g^m * rⁿ mod n²

※平文空間はZ_nだが, 暗号文空間はZ_n²である.

Decrypt

復号は以下のように定義される.

Dec(c) := L(c^λ mod n²) * L(g^λ mod n²)^-1 mod n

ここで

L(u) = (u-1)/n
λ = LCM(p-1, q-1)

λはλ(n)の略記である.

再掲 : ※平文空間はZ_n, 暗号文空間はZ_n²
-> 暗号化では mod n² が, 復号では mod n になっている.

では Dec(c) = m になることを確認していこう.

c^λ = (g^m * rⁿ)^λ mod n²
= g^mλ * r^nλ mod n²
= g^mλ mod n²
= (1 + kn)^mλ mod n²

r^nλ mod n² はカーマイケルの定理により1である.

(1 + kn)^mλ mod n² は二項定理を使って展開し, mod n² であることに注意すると n² を因数に持つ項が綺麗に消えるので

(1 + kn)^mλ mod n² = 1 + mλkn

が得られる.

これをL関数に適用し, L(g^λ mod n²)も同じように計算する.

L(c^λ mod n²) = L(1 + mkλn mod n²)
= ((1 + mkλn) - 1) / n
= mkλ

L(g^λ mod n²) = L((1 + kn)^λ mod n²)
= L(1 + kλn mod n²)
= ((1 + kλn) - 1) / n
= kλ

最後に

L(c^λ mod n²) * L(g^λ mod n²)^-1 mod n
= mkλ * (kλ)^-1 mod n
= m

これで平文が復号できた.

検証コード

以上を踏まえて検証.
最後に加法準同型であることを確認している.

test_paillier

まとめ

(暗号化, 復号の部分はやっぱり先生の記事読むのが手っ取り早いんだよなぁ)

個人的にPaiilier暗号で好きなのは平文が1であっても暗号文が1にならない点.
plain RSAでは平文をe乗するので平文が1ならどうあがいても暗号文が1になってしまうが, Paiilerでは(1+kn)を平文乗するので平文が1でも暗号文が1になるとは限らない.

参考文献

公開鍵暗号 - Paillier暗号 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです

• Public-Key Cryptosystems Based on Composite Degree Residuosity Classes https://link.springer.com/chapter/10.1007/3-540-48910-X_16

• カーマイケルのλ関数
  Carmichael function - Wikipedia

AES-ECBに対する攻撃を考える

ブロック暗号で使われるECBモードについて(AESに限った話ではないけれど). 

暗号利用モード - Wikipedia

Wikipediaでも言及されているが, 平文ブロックが同じであれば暗号ブロックも同じになるという弱点がある. 今回はその弱点を突いた攻撃について考える.

例として適当な平文Pを与える. 1ブロックを16 [bytes]とする.

P1 : HOGEHOGE | PIYOPIYO

P2 : PIYOPIYO | HOGEHOGE

P3 : HOGEHOGE | PIYOPIYO

これらを暗号化した暗号文Cのブロックは

P1 -> C1

P2 -> C2

P3 -> C3

となるが, このときC1 = C3 として得られる.

暗号化(復号)の際に1つ前のブロックに依存しておらず, 各ブロックが独立している. これを利用すると

平文P = P1 | P2 | P3 | P4 に対応する

暗号文C = C1 | C2 | C3 | C4

のブロックを部分的に入れ替えて(改ざんされて)も復号自体は成功するため中間者攻撃される可能性がある.

たとえば暗号文が

C1 | C3 | C2 | C4 

C4 | C3 | C2 | C1  

のように並び替えられていても受信側は改ざんされていたかどうかわからない(復号したものが文章として正しいかどうかでわかるかもしれないが).

また, 同じ平文ブロックが同じ暗号文ブロックとして出てくるという性質を利用すると

平文P = [ユーザーの入力 + SECRET] 

という状況下であれば選択平文攻撃によってSECRETを特定することができる.

CTFではこのSECRETがフラグになっていたりするが, 実際に運用されているサービスにおいてはCookieだったり機密情報だったり, まさしくSECRETなものに置き換えて言えることなので注意. 

要するにECBモードは使わないようにしようという話. (HMACで改ざん検知はできるためこの表現は誇張し過ぎかもしれない.)  

手を動かす

ではSECRETを特定していこう.

先に方法を説明しておくと1文字ずつブルートフォースである.

SECRETのnバイト目をSn { S1, S2, ...} と表す. 

1ブロックは16バイトで, 満たない部分はパディングが行われるが今回は考慮しなくてよいので記述を省略する.

繰り返しになるが平文

P1 = | a a a a a a a a | a a a a a a a a |

P2 = | a a a a a a a a | a a a a a a a a |

P3 = | S1 S2 S3 ... | <- ここは暗号化の際にくっつけられる

に対応する暗号ブロックC1とC2は等しい. ただし1バイトでも異なる場合は全く違う暗号ブロックが生成される(これについてはAESの実装を参照)

この時の入力は'a' * 32 だが, これを 'a' * 31 にしてみると

P1 = | a a a a a a a a | a a a a a a a a |

P2 = | a a a a a a a a | a a a a a a a S1 |

P3 = | S2 S3 ...

 P1とP2の最後の1バイトだけが異なる状況が作れた.

このときの暗号ブロックC1, C2は

S1 = a であれば C1 = C2 である.

すこし変える.

P1 = 'a' * 15 + [a-zA-Z0-9]

P2 = 'a' * 15 

これはつまり

P1 = | a a a a a a a a | a a a a a a a [a-zA-Z0-9] |

P2 = | a a a a a a a a | a a a a a a a S1 |

P3 = | S2 S3 ...

ふぁっ, なんだこれは.

[a-zA-Z0-9] の総当たりで C1 = C2 となる文字が見つかれば S1 が特定できるではないか. たまげたなぁ.

S1が特定できれば次はS2をやっていく.

基本的にはS1と同じである.

P1 = | a a a a a a a a | a a a a a a S1 [a-zA-Z] |

P2 = | a a a a a a a a | a a a a a a S1 S2 |

P3 = | S3 ...

 1バイトずらして P2 の末尾に S2 がくるようにした. あとは総当たりで C1 = C2 となる文字を探せば良い.

あとは同様に1バイトずつ特定していけばSECRETが判明する.

バイト数が多くなってくると, どのブロックとどのブロックが同じかを考えるのは面倒なので 16 [bytes]に区切って重複なしの集合位数の変化で検知すればよさそう.

以下, 検証コード.

今回はSECRETが見ればわかるが, 実行するとちゃんと総当たりで特定していることがわかる.

gist.github.com

近況

ykm11.hatenablog.com

四国支部の学会に参加した.

あまり規模の大きいものではないが発表を済ませたので卒業要件が1つクリア.

あとは単位を修得するだけ. 頑張ろうな.

そして夏休みももうすぐ終わり, 明々後日から後期が始まる. 

来月末にはprocon29もあるがまぁ適当に.