ぺんぎんさんのおうち

トリトリトリ

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

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


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

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

Enc(m) := me mod n

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

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


状況を整理する.

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

手順

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

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


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

s = Enc(k) = ke mod n
t = Enc(k2) =k2e mod n


次に s2 - t を計算する.

s2 - t = (ke)2 - k2e mod n
= k2e - k2e mod n
= 0 mod n


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

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

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

実際に計算してみる

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

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


k = 5

s = Enc(k) = 53 mod 143 = 125
t = Enc(k2) = 56 mod 143 = 38


s2 - t = 1252 - 38 = 15587
15587 % 143 = 0


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

GCD(0, 15587) = 15587


k = 6

s = Enc(k) = 63 mod 143 = 73
t = Enc(k2) = 66 mod 143 = 38


s2 - t = 732 - 38 = 5291
5291 % 143 = 0


GCDを計算.

GCD(15587, 5291) = 143


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


まとめ

なぜこの記事を書いたのか コレガワカラナイ

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