読者です 読者をやめる 読者になる 読者になる

ある意味攻撃

crypt

概要

Koichiro Noro and Kunikatsu Kobayashi. “Knapsack Cryptosystem on Elliptic Curves.” (ePrint 2009/091)を軽く読んだ.
書き直してみたら拡張ElGamal暗号の改悪になってしまった. したがってこの論文の価値が消滅した.
面倒くさいので正しい構成は元論文を当たってください.

研究会 講演論文 - 楕円曲線上のナップザック暗号を見るに2008/07にISEC研究会で発表済らしい.

元の暗号方式

パラメータ設定

G_1×G_2→G_T型の双線形写像を用いた群を考える.
それぞれ位数を素数qとしておく.
G_1の生成元をP, G_2の生成元をQとする.
G_Tの生成元はe(P,Q)である.

鍵生成
  1. G_1から元をランダムに選びそれをTとする.
  2. xをZ/qからランダムに選ぶ.
  3. yをy 2^{kl+1} < (q-1)を満たす整数からランダムに選ぶ.
  4. a_i = y 2^{i-1} (i=1,...,kl)とし, A_i = a_i Pを計算する.
  5. b_{ij} = e(P,Q)^{y j 2^{(i-1)k}}を i=1,...,lとj=1,...,2^{k-1}について計算し, f_i(\alpha)=(\alpha-1) \prod_{j=1}^{2^{r-1}} (\alpha-b_{ij})とする.
  6. 公開鍵は(P,yP,T,xT,A_1,...,A_{kl},)
  7. 秘密鍵は(x,y,a_1,...,a_{kl},f_1,...,f_l)
暗号化
  1. m_1,...,m_lをそれぞれkビットの数とする. で, M=\sum_{i=1}^{l} m_i 2^{i-1}としておく.
  2. C_{i1} = t_i T, C_{i2}=\sum_{j=1}^{k} m_{(i-1)k+j} A_{(i-1)k+j} + t_i x T とする
  3. C = M y Pとする.
  4. 暗号文は (C, C_{11}, C_{12}, ..., C_{l1}, C_{l2}).
復号

(省略)
f_i(α)を使って頑張っている.

書き直した暗号方式

C_{i2}の計算方法が無駄に重い. A_{i}をすべて公開する必要もなさそうだと考えると以下になる.

パラメータ設定

(省略)

鍵生成
  1. G_1から元をランダムに選びそれをTとする. (ElGamal暗号用.)
  2. xをZ/qからランダムに選ぶ. (ElGamal暗号用.)
  3. yをy 2^{kl+1} < (q-1)を満たす整数からランダムに選ぶ. (拡張部分用.)
  4. (省略.)
  5. 公開鍵は(P,yP,T,xT)
  6. 秘密鍵は(x,y)
暗号化
  1. m_1,...,m_lをそれぞれkビットの数とする.
  2. t_iをZ/qからランダムに選び, C_{i1} = t_i T, C_{i2}= m_i 2^{i-1} y P + t_i x T とする
  3. 暗号文は (C_{11}, C_{12}, ..., C_{l1}, C_{l2}).

これで(C_{i1}, C_{i2}) の部分が拡張ElGamal暗号になることが分かる.

復号
  1. C_{i1}とC_{i2}とxよりm_i 2^{i-1} y Pを計算する.
  2. m_i Pを計算する.
  3. kが小さいので2^{k}通り試せば, m_iが復元できる. これをl回繰り返す.

問題点

  • 復号について考えると, 論文中にあるような2^{k}以上回以上演算を行うメリットは無い. なんでこんなややこしくしているのかは俺は知らない.
  • 全部群G_1上で計算できるので, そもそもペアリング使う必要が無くなってしまう.
  • 暗号文に含まれるCの情報は全く必要ない.
  • 素数位数にしておけば, yの謎の条件も必要ない.
  • というわけでナップサックかと思ったら拡張ElGamalの改悪でしたとさ.