暗号計算機屋のブログ

なにか思いついたことを不定期に更新。

nhira型モンゴメリ乗算アルゴリズム

とりあえず

この証明だけは、まだ、役に立つかも。というところ。

はじめに

RSA暗号を高速化するためのアルゴリズムとしてモンゴメリ乗算が有名だが、その改良型がC.C.Yang(IEEE 1998)によって論文発表された。それをもとにDesign Wave MagagineのRSA暗号コンテスト(2008年)で実装されたものが記事になっていた。それをヒントに、この参考文献の14.36のモンゴメリ乗算を改良したnhira型モンゴメリ乗算のアルゴリズムを説明する。自身が作ったアルゴリズムだがC.C.Yangと同じかもしれない。C.C.Yangの論文を取り寄せる前に自身で証明できてしまったため、C.C.Yangの論文を読む必要がなくなった。

ちなみにDesign Wave Magagineはモンゴメリリダクションを使ったモンゴメリ乗算にC.C.Yangを導入した感じだが、これは乗算とリダクションを同時に行うモンゴメリ乗算にC.C.Yangを導入した感じだと思っている。

nhira型モンゴメリ乗算

 {
INPUT : integers　m  = (m_{n-1} … m_1 m_0)_b　,　x=(x_{n+1} x_n x_{n-1} … x_1 x_0)_b　,　\\
　　　　　　　　　y  = (y_{n+1} y_n y_{n-1} … y_1 y_0)_b \\
　　　　with　0　≦　x,y　≦　2m-1　,　R=b^{n+2}　with　gcd(m,b)=1　, \\
　　　　and　m'　=　-m^{-1}　mod　b \\
　\\
OUTPUT :　xyR^{-1}　mod　m. \\
　\\
1.　A←0.　 (Notation : A = (a_n a_{n-1} … a_1 a_0)_b　) \\
　\\
2.　For　i　from　0　to　(n+1)　do　the　following:　\\
　2-1.　u_i ← (a_0 + x_i y_0 )　m' 　mod　b. \\
　2-2.　A ← (A + x_i y + u_i m) / b. \\
　\\
3.　Return (A).　　0≦A≦2m-1
}

【解説】　

xの範囲は2m-1までなので {x_{n+1}}は必ず0。　わかりやすくするためb=2として説明する。 　Forループで0≦i≦n のとき0≦A＜3m-1 とした場合、次のAの値の範囲は、2.2の式から　(3m-2 + 2m-1 + m) / 2 = (6m-3) / 2 = 3m-1.5 以下なので0≦A <3m-1 の範囲になる。　Aの初期値は0なのでi=nのループ終了時のAは0≦A＜3m-1　となる。Forループでi=n+1 のとき0≦A＜3m-1なので、次のAの値の範囲は 2.2の式から(3m-2 + m ) / 2 = 2m-1 以下、すなわち0≦A≦2m-1

【解説２】(2017年2月26日 追加)

オリジナルの14.36に対してx,yがmを超える値となっていて正しい結果になる理由は、14.36は14.32のモンゴメリリダクションと同じ計算しかしていないということ。14.32で {a_i}を求めるタイミングまでにx×yを計算させて、最初からA=x×yであったのと同じ状態であればいい。14.32の定理でR= {b^{n}}をR= {b^{n+2}}とすればx,yが2m-1以下の範囲であれば正しい結果が得られる。

【参考文献】

Design Wave Magagineのコンテストの応募原稿にあった参考文献。(私は、読んでない) f:id:icf:20170225131209p:plain

(2017年2月27日 追加)

詳しく読んでないが、ここで説明するアルゴリズムを使って、やりたかったことが2008年のIEEEの論文になっていました。
↓↓↓これです↓↓↓

A New Modular Exponentiation Architecture for Efficient Design of RSA Cryptosystem - IEEE Journals & Magazine

(2018年2月25日 追加)

証明はだいぶ、省略して説明しているけど、問題ないはず。 こんな証明をした目的はOpenICF3と競合するアイディアを、自身で、潰してしまうこと。既出なら、これ以上、追う必要なし。