利用者:Roget/HIME(R)

HIME(R)とは、大きな数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。日立製作所が提案した。

概要

特殊な法を利用したRabin暗号方式の一種である。パディングにはOAEPを用いている。

Rabin暗号では法として$N=pq$を利用していたが、HIME(R)では法として$N=p^{d}q$を利用する。 また、復号化の際に中国式剰余定理を用いない点も特徴である。

用語については、暗号の用語、暗号理論の用語を参照のこと。

暗号方式

$\lambda$ をセキュリティ・パラメータとする。

鍵生成

• 法を4の下で3と等しい$\lambda$ビットの素数$p,q$を選ぶ。
• $d>1$となる整数$d$を選ぶ。
• $N=p^{d}q$を計算する。

また、パディング用に以下のパラメータ生成を行う。

• $k=|N|$とする。
• $n=k-k_{0}-k_{1}-1$, $2k_{0}<k$となる正整数$k_{0},k_{1},n$を選ぶ。
• ハッシュ関数$G:\{0,1\}^{k_{0}}\to \{0,1\}^{k-k_{0}-1}$と$H:\{0,1\}^{k-k_{0}-1}\to \{0,1\}^{k_{0}}$を選ぶ。

秘密鍵を素因数$(p,q)$とし、公開鍵を$(N,k,k_{0},k_{1},G,H)$とする。

暗号化

• $\{0,1\}^{n}$の元$m$を平文とする。
• 乱数$r$を$\{0,1\}^{k_{0}}$からランダムに選ぶ。
• パディング: OAEPを用いる。
  • $X=(m||0^{k_{1}})\oplus G(r))$を計算する。
  • $Y=r\oplus H(X)$を計算する。
  • $M=X||Y$とする。
• $c=M^{2}{\bmod {N}}$を暗号文とする。

復号

受け取った暗号文を$c\in \mathbb {Z} _{N}$とする。

• 暗号文$c$が$\mathbb {Z} _{N}$上で平方剰余かどうか確かめる。そうでなければ拒否。
  • 具体的には$c^{(p-1)/2}\equiv 1{\pmod {p}}$と$c^{(q-1)/2}\equiv 1{\pmod {q}}$を確かめる。
• $\gamma _{1},\dots ,\gamma _{d}$の計算。
  • $\gamma _{0}=\pm {\sqrt {y}}{\bmod {p}}$, $\Gamma _{0}=\gamma _{0}$,
  • $(\pm {\sqrt {y}}-\gamma _{0})/p{\bmod {q}}$, $\Gamma _{1}=\gamma _{0}+\gamma _{1}p$を計算し,
  • $i\geq 2$について, $\gamma _{i}=((y-\Gamma _{i-1}^{2}{\bmod {p^{i}q}})/p^{i-1}q)\cdot (2\gamma _{0})^{-1}{\bmod {p}}$, $\Gamma _{i}=\Gamma _{i-1}+\gamma _{i}p^{i-1}q$を計算する.
• $M=\gamma _{0}+\gamma _{1}p+\sum _{i=2}^{d}\gamma _{i}p^{i-1}q$を計算する。
  • 注: $\gamma _{0},\gamma _{1}$がそれぞれ2通りの値を取るので, 4つのMがありうる。
• 各$M_{i}$についてOAEPの逆パディングを適用し, 正しく$m$を復元できたものを平文とする。

実装上の注意

• 仕様ではハッシュ関数GおよびHの実装例が記されている。
• 復号精度の向上のために$M$の符号とヤコビ記号を送っても良い。この場合でも安全性証明に影響は無い。

参考文献

• (株) 日立製作所: HIME(R) 暗号 暗号技術仕様書 http://www.hitachi.co.jp/rd/yrl/crypto/hime/HIME_R_specJ.pdf

関連項目

• 暗号
• 暗号理論
• RSA
• 素因数分解