JP3315087B2 - 逆元計算装置及びそのプログラム記録媒体 - Google Patents
逆元計算装置及びそのプログラム記録媒体Info
- Publication number
- JP3315087B2 JP3315087B2 JP01078899A JP1078899A JP3315087B2 JP 3315087 B2 JP3315087 B2 JP 3315087B2 JP 01078899 A JP01078899 A JP 01078899A JP 1078899 A JP1078899 A JP 1078899A JP 3315087 B2 JP3315087 B2 JP 3315087B2
- Authority
- JP
- Japan
- Prior art keywords
- storage means
- stored
- updating
- storage
- storing
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Landscapes
- Complex Calculations (AREA)
Description
【０００１】
【発明の属する技術分野】この発明は、符号理論や情報
セキュリティ技術に用いられる整数の剰余環の逆元計算
装置及びそのプログラム記録媒体に関するものである。
セキュリティ技術に用いられる整数の剰余環の逆元計算
装置及びそのプログラム記録媒体に関するものである。
【０００２】
【従来の技術】データを秘匿するためには暗号化技術が
有効である。暗号化の方法は共通鍵暗号と公開鍵暗号が
ある。共通鍵暗号では、暗号化側と復号化側で同一の鍵
を用い、この鍵は秘密に管理されている。一方、公開鍵
暗号では暗号化鍵と復号化鍵は異なっており、暗号化鍵
は公開しても、復号化鍵は現実的な時間内に求まらない
と広く信じられている。
有効である。暗号化の方法は共通鍵暗号と公開鍵暗号が
ある。共通鍵暗号では、暗号化側と復号化側で同一の鍵
を用い、この鍵は秘密に管理されている。一方、公開鍵
暗号では暗号化鍵と復号化鍵は異なっており、暗号化鍵
は公開しても、復号化鍵は現実的な時間内に求まらない
と広く信じられている。
【０００３】公開鍵暗号の方式として代表的なＲＳＡ暗
号の構成は、例えば「岡本、太田共編：“暗号・ゼロ知
識証明・数論，”共立出版，１９９５」（以下、文献Ｏ
Ｏと略す）のｐ．２２０に示されている。ＲＳＡ暗号は
Ｎを自然数としてＺ／ＮＺ上の冪乗演算、いわゆる冪乗
剰余演算を必要とする。この冪乗剰余演算を高速に実行
するためには、文献ＯＯのｐｐ．１７９−１８１に紹介
されているＭｏｎｔｇｏｍｅｒｙ法が有効である。Ｍｏ
ｎｔｇｏｍｅｒｙ法を実行するためにはｍを自然数とし
てｍｏｄ２m での逆元演算を必要とする。
号の構成は、例えば「岡本、太田共編：“暗号・ゼロ知
識証明・数論，”共立出版，１９９５」（以下、文献Ｏ
Ｏと略す）のｐ．２２０に示されている。ＲＳＡ暗号は
Ｎを自然数としてＺ／ＮＺ上の冪乗演算、いわゆる冪乗
剰余演算を必要とする。この冪乗剰余演算を高速に実行
するためには、文献ＯＯのｐｐ．１７９−１８１に紹介
されているＭｏｎｔｇｏｍｅｒｙ法が有効である。Ｍｏ
ｎｔｇｏｍｅｒｙ法を実行するためにはｍを自然数とし
てｍｏｄ２m での逆元演算を必要とする。
【０００４】一般的にｍｏｄＮでの逆元演算を実行する
ためには、文献ＯＯのｐｐ．１２０−１２１にある拡張
Ｅｕｃｌｉｄの互除法を使うことができるが、ここでは
法が２m という特別な形であるので、Ｈｅｎｓｅｌ ｌ
ｉｆｔｉｎｇ（多項式の根をｍｏｄ ｂm からｍｏｄ
ｂm+1 に持ち上げる自然な方法）を用い効率的に求める
ことができる。さらに、逆元計算をソフトウェアで実行
する場合には近年のＣＰＵにおいてワード乗算は比較的
高速であるのでｍがワード長程度の場合Ｈｅｎｓｅｌ
ｌｉｆｔｉｎｇの２次版であるＺａｓｓｅｎｈａｕｓの
方法（文献「Ｈ．Ｚａｓｓｅｎｈａｕｓ：“Ｏｎ Ｈｅ
ｎｓｅｌ Ｆａｃｔｏｒｉｚａｔｉｏｎ，Ｉ，”Ｊｏｕ
ｒｎａｌ ｏｆ ｎｕｍｂｅｒ ｔｈｅｏｒｙ，ｖｏ
ｌ．１，ｐｐ．２９１−３１１，１９６９」）が有効で
ある。
ためには、文献ＯＯのｐｐ．１２０−１２１にある拡張
Ｅｕｃｌｉｄの互除法を使うことができるが、ここでは
法が２m という特別な形であるので、Ｈｅｎｓｅｌ ｌ
ｉｆｔｉｎｇ（多項式の根をｍｏｄ ｂm からｍｏｄ
ｂm+1 に持ち上げる自然な方法）を用い効率的に求める
ことができる。さらに、逆元計算をソフトウェアで実行
する場合には近年のＣＰＵにおいてワード乗算は比較的
高速であるのでｍがワード長程度の場合Ｈｅｎｓｅｌ
ｌｉｆｔｉｎｇの２次版であるＺａｓｓｅｎｈａｕｓの
方法（文献「Ｈ．Ｚａｓｓｅｎｈａｕｓ：“Ｏｎ Ｈｅ
ｎｓｅｌ Ｆａｃｔｏｒｉｚａｔｉｏｎ，Ｉ，”Ｊｏｕ
ｒｎａｌ ｏｆ ｎｕｍｂｅｒ ｔｈｅｏｒｙ，ｖｏ
ｌ．１，ｐｐ．２９１−３１１，１９６９」）が有効で
ある。
【０００５】Ｚａｓｓｅｎｈａｕｓの方法は入力をｘ、
出力をｙ、補助変数をａとｂとおき、［ｘ］をガウス記
号（ｘを越えない最大の整数）とすると、ｍ＝２n （ｎ
≧１）の場合は以下の通りである。また、ビット位置は
最下位を０とおき、ｘ、ｙ、ａ、ｂのビット長はｍとす
る。 Ｓｔｅｐ１：ｘを入力する。
出力をｙ、補助変数をａとｂとおき、［ｘ］をガウス記
号（ｘを越えない最大の整数）とすると、ｍ＝２n （ｎ
≧１）の場合は以下の通りである。また、ビット位置は
最下位を０とおき、ｘ、ｙ、ａ、ｂのビット長はｍとす
る。 Ｓｔｅｐ１：ｘを入力する。
【０００６】Ｓｔｅｐ２：初期値としてｙ：＝１、ｂ：
＝［ｘ／２］とする。 Ｓｔｅｐ３：ｉ＝０，１，…，ｎ−１について以下を繰
り返す。 １．ａを（ｙ×（２＾（２i ）−（ｂの下位２i ビッ
ト）））の下位２i ビットとする。ただし、ｐ＾ｑはｐ
のｑ乗を表わす。 ２．ｙの２i ビット目から２i+1 −１ビット目にａの下
位２i ビットをはめ込む。
＝［ｘ／２］とする。 Ｓｔｅｐ３：ｉ＝０，１，…，ｎ−１について以下を繰
り返す。 １．ａを（ｙ×（２＾（２i ）−（ｂの下位２i ビッ
ト）））の下位２i ビットとする。ただし、ｐ＾ｑはｐ
のｑ乗を表わす。 ２．ｙの２i ビット目から２i+1 −１ビット目にａの下
位２i ビットをはめ込む。
【０００７】３．ｂにｘａ＋ｂの２i ビット目から２n
−２i −１ビット目を代入する。 Ｓｔｅｐ４：ｙを出力する。 この場合のビット処理は、ｉの状態変化に対する出力ｙ
を格納したレジスタの内容を２進数で表わすと図３に示
すようになる。「１」は常に１、「．」は求まったビッ
ト、「？」は未知のビットである。ここでｉ＝１の結果
からｉ＝２の結果を作るところを見ると、新たに４〜７
ビット目が求まっている。この４〜７ビット目にデータ
を配置することを「はめ込む」と表現している。
−２i −１ビット目を代入する。 Ｓｔｅｐ４：ｙを出力する。 この場合のビット処理は、ｉの状態変化に対する出力ｙ
を格納したレジスタの内容を２進数で表わすと図３に示
すようになる。「１」は常に１、「．」は求まったビッ
ト、「？」は未知のビットである。ここでｉ＝１の結果
からｉ＝２の結果を作るところを見ると、新たに４〜７
ビット目が求まっている。この４〜７ビット目にデータ
を配置することを「はめ込む」と表現している。
【０００８】
【発明が解決しようとする課題】上記Ｚａｓｓｅｎｈａ
ｕｓの方法は、下位２i ビットの取出し、はめ込みなど
ビット単位の処理が多く、ソフトウェアで実装する場合
にはマスク処理が多くなり効率があまりよくない。この
発明では、このマスク処理を削減することを目的とす
る。
ｕｓの方法は、下位２i ビットの取出し、はめ込みなど
ビット単位の処理が多く、ソフトウェアで実装する場合
にはマスク処理が多くなり効率があまりよくない。この
発明では、このマスク処理を削減することを目的とす
る。
【０００９】
【課題を解決するための手段】上記Ｚａｓｓｅｎｈａｕ
ｓの方法において、Ｓｔｅｐ３の２．で、ａをｙにはめ
込む際にそのまま、はめ込むのではなく、この発明では
加算ではめ込む（足し込む）。このようにすると、Ｓｔ
ｅｐ３の１．でマスクせずとも符号を反転させれば結果
が正しくなる性質を利用する。
ｓの方法において、Ｓｔｅｐ３の２．で、ａをｙにはめ
込む際にそのまま、はめ込むのではなく、この発明では
加算ではめ込む（足し込む）。このようにすると、Ｓｔ
ｅｐ３の１．でマスクせずとも符号を反転させれば結果
が正しくなる性質を利用する。
【００１０】つまり入力ｘのｍｏｄｍでの逆元ｙを求め
たもので、ａ、ｂを補助変数とし、ｍ＝２n （ｎ≧１）
であり、ｘ、ｙ、ａ、ｂのビット長はｍであって、この
発明によれば、ｘを入力し、記憶手段に記憶し、初期処
理として、ｘを読み出し、［ｘ／２］を演算し、この結
果をｂとして記憶手段に記憶し、ｂの最下位ビットをａ
として記憶手段に記憶し、ａ、ｘ、ｂを読み出し、
［（ａｘ＋ｂ）／２］を演算し、その結果によりｂを更
新し、ｘを読み出し、その下位２ビットをｙとして記憶
手段に記憶する。
たもので、ａ、ｂを補助変数とし、ｍ＝２n （ｎ≧１）
であり、ｘ、ｙ、ａ、ｂのビット長はｍであって、この
発明によれば、ｘを入力し、記憶手段に記憶し、初期処
理として、ｘを読み出し、［ｘ／２］を演算し、この結
果をｂとして記憶手段に記憶し、ｂの最下位ビットをａ
として記憶手段に記憶し、ａ、ｘ、ｂを読み出し、
［（ａｘ＋ｂ）／２］を演算し、その結果によりｂを更
新し、ｘを読み出し、その下位２ビットをｙとして記憶
手段に記憶する。
【００１１】次にｉ＝１，２，…，ｎ−１に対して、
ｂ、ｙを読み出して−ｂｙを演算し、その結果で記憶手
段内のａを更新し、またｂ、ａ、ｘを読み出して［（ｂ
＋ａｘ）／（２＾（２i ））］を演算し、その結果で記
憶手段内のｂを更新し、ｙ、ａを読み出し、ｙ＋ａ×２
＾（２i ）を演算し、その結果で記憶手段内のｙを更新
する。ただしｐ＾ｑはｐのｑ乗を表わす。
ｂ、ｙを読み出して−ｂｙを演算し、その結果で記憶手
段内のａを更新し、またｂ、ａ、ｘを読み出して［（ｂ
＋ａｘ）／（２＾（２i ））］を演算し、その結果で記
憶手段内のｂを更新し、ｙ、ａを読み出し、ｙ＋ａ×２
＾（２i ）を演算し、その結果で記憶手段内のｙを更新
する。ただしｐ＾ｑはｐのｑ乗を表わす。
【００１２】次にｙを読み出して逆元演算結果として出
力する。
力する。
【００１３】
【発明の実施の形態】以下ではこの発明の実施例につい
て説明する。図１は処理手順を示す。入力をｘ、出力を
ｙ、補助変数をａとｂとおき、［ｘ］をガウス記号（ｘ
を越えない最大の整数）とし、ｍ＝２n （ｎ≧１）の場
合は以下の通りである。ここでｘ、ｙ、ａ、ｂのビット
長はｍとする。
て説明する。図１は処理手順を示す。入力をｘ、出力を
ｙ、補助変数をａとｂとおき、［ｘ］をガウス記号（ｘ
を越えない最大の整数）とし、ｍ＝２n （ｎ≧１）の場
合は以下の通りである。ここでｘ、ｙ、ａ、ｂのビット
長はｍとする。
【００１４】Ｓｔｅｐ１：ｘを入力する（Ｓ１）。 Ｓｔｅｐ２：初期処理として以下の計算を行なう。 １．ｂ：＝［ｘ／２］ ２．ａ：＝ｂの最下位ビット（Ｓ２） ３．ｂ：＝［（ａｘ＋ｂ）／２］ ４．ｙ：＝ｘの下位２ビット（Ｓ３） ５．ｉ：＝１（Ｓ４） Ｓｔｅｐ３：ｉ＝１，２，…，ｎ−１に対し以下を繰り
返す。
返す。
【００１５】 １．ａ：＝−ｂｙ ２．ｂ：＝［（ｂ＋ａｘ）／（２＾（２i ））］ ３．ｙ：＝ｙ＋ａ×２＾（２i ）（Ｓ５） ４．ｉ：＝ｉ＋１（Ｓ６） Ｓｔｅｐ４：ｙを出力する。
【００１６】・Ｓｔｅｐ２において、１，２，３はこの
順序で実行する。４と５は任意のタイミングで実行して
よい。 ・Ｓｔｅｐ３において、１→２→３の順に実行しても、
１→３→２の順に実行してもよいが、最近の計算機では
データ依存性から１→２→３の順で実行するのがよい。
また、ｉ＝ｎ−１のときは、ｂは不要なので２を実行し
なくてよい。さらに４は任意のタイミングで実行してよ
い。
順序で実行する。４と５は任意のタイミングで実行して
よい。 ・Ｓｔｅｐ３において、１→２→３の順に実行しても、
１→３→２の順に実行してもよいが、最近の計算機では
データ依存性から１→２→３の順で実行するのがよい。
また、ｉ＝ｎ−１のときは、ｂは不要なので２を実行し
なくてよい。さらに４は任意のタイミングで実行してよ
い。
【００１７】・アルゴリズムのループを予め展開してお
いてもよい（展開数は逆元対象のビット数のｌｏｇのオ
ーダでしか効いてこない）。ループ展開することによ
り、ｉに依存する定数を事前に計算しておき、より高速
に逆元を求めることができる。 ・２の冪での割算、かけ算は、通常のプロセッサではシ
フト演算を使うとより高速に計算できる。
いてもよい（展開数は逆元対象のビット数のｌｏｇのオ
ーダでしか効いてこない）。ループ展開することによ
り、ｉに依存する定数を事前に計算しておき、より高速
に逆元を求めることができる。 ・２の冪での割算、かけ算は、通常のプロセッサではシ
フト演算を使うとより高速に計算できる。
【００１８】図２にこの発明の装置の機能構成を示す。
入力手段１１によりｘが記憶装置１２のｘ格納領域１３
に格納され、演算装置１０内のｂ初期化第１手段１４に
よりｘが記憶装置１２から読み出され、［ｘ／２］が演
算され、その演算結果がｂとして記憶装置１２のｂ格納
領域１５に格納される。
入力手段１１によりｘが記憶装置１２のｘ格納領域１３
に格納され、演算装置１０内のｂ初期化第１手段１４に
よりｘが記憶装置１２から読み出され、［ｘ／２］が演
算され、その演算結果がｂとして記憶装置１２のｂ格納
領域１５に格納される。
【００１９】ａ初期化手段１６により記憶装置１２から
ｂが読み出され、その最下位ビットがａとして記憶装置
１２のａ格納領域１７に記憶される。ｂ初期化第２手段
１８により、記憶装置１２からａ、ｘ、ｂが読み出さ
れ、［（ａｘ＋ｂ）／２］が演算され、その演算結果が
ｂとしてｂ格納領域１５の記憶内容が更新される。ｙ初
期化手段１９により記憶装置１２からｘが読み出され、
その下位２ビットがｙとして記憶装置１２のｙ格納領域
２１に格納される。ｉ初期化手段２２により記憶装置１
２のｉ格納領域２３にｉとして１がセットされる。
ｂが読み出され、その最下位ビットがａとして記憶装置
１２のａ格納領域１７に記憶される。ｂ初期化第２手段
１８により、記憶装置１２からａ、ｘ、ｂが読み出さ
れ、［（ａｘ＋ｂ）／２］が演算され、その演算結果が
ｂとしてｂ格納領域１５の記憶内容が更新される。ｙ初
期化手段１９により記憶装置１２からｘが読み出され、
その下位２ビットがｙとして記憶装置１２のｙ格納領域
２１に格納される。ｉ初期化手段２２により記憶装置１
２のｉ格納領域２３にｉとして１がセットされる。
【００２０】ａ更新手段２４により記憶装置１２から
ｂ、ｙが読み出され、−ｂｙが演算され、その演算結果
によりａ格納領域１７に記憶されているａが更新され
る。ｂ更新手段２５により記憶装置１２からａ、ｂ、
ｘ、ｉが読み出され、［（ｂ＋ａｘ）／２＾（２i ）］
が演算され、その演算結果によりｂ格納領域１５に記憶
されているｂが更新される。
ｂ、ｙが読み出され、−ｂｙが演算され、その演算結果
によりａ格納領域１７に記憶されているａが更新され
る。ｂ更新手段２５により記憶装置１２からａ、ｂ、
ｘ、ｉが読み出され、［（ｂ＋ａｘ）／２＾（２i ）］
が演算され、その演算結果によりｂ格納領域１５に記憶
されているｂが更新される。
【００２１】ｙ更新手段２６により記憶装置１２から
ａ、ｙ、ｉが読み出され、ｙ＋ａ×２＾（２i ）が演算
され、その演算結果により、ｙ格納領域２１に格納され
ているｙが更新される。ｉ更新手段２７により記憶装置
１２からｉが読み出され、ｉ＋１が演算され、その演算
結果によりｉ格納領域２３に格納されているｉが更新さ
れる。
ａ、ｙ、ｉが読み出され、ｙ＋ａ×２＾（２i ）が演算
され、その演算結果により、ｙ格納領域２１に格納され
ているｙが更新される。ｉ更新手段２７により記憶装置
１２からｉが読み出され、ｉ＋１が演算され、その演算
結果によりｉ格納領域２３に格納されているｉが更新さ
れる。
【００２２】制御手段２８により記憶装置１２からｉ、
ｎが読み出され、ｉ＝ｎになるまでａ更新手段２４、ｂ
更新手段２５、ｙ更新手段２６、ｉ更新手段２７が順次
動作させられ、ｉ＝ｎになると出力手段２９により、記
憶装置１２からｙが読み出され、外部へ出力される。こ
の発明の装置はその各機能を、コンピュータによりプロ
グラムを解析実行させることにより、行わせることもで
きる。
ｎが読み出され、ｉ＝ｎになるまでａ更新手段２４、ｂ
更新手段２５、ｙ更新手段２６、ｉ更新手段２７が順次
動作させられ、ｉ＝ｎになると出力手段２９により、記
憶装置１２からｙが読み出され、外部へ出力される。こ
の発明の装置はその各機能を、コンピュータによりプロ
グラムを解析実行させることにより、行わせることもで
きる。
【００２３】
【発明の効果】この発明によれば、Ｓｔｅｐ３の１、
２、３から理解されるようにビットはめ込み処理がなく
なり、それだけＺａｓｓｅｎｈａｕｓの方法をソフトウ
ェアで実装する上で問題となったビット処理が軽減さ
れ、ｍｏｄ２m で高速に逆元が計算できるようになっ
た。
２、３から理解されるようにビットはめ込み処理がなく
なり、それだけＺａｓｓｅｎｈａｕｓの方法をソフトウ
ェアで実装する上で問題となったビット処理が軽減さ
れ、ｍｏｄ２m で高速に逆元が計算できるようになっ
た。
【００２４】・汎用のワークステーション上でｎ＝５
（すなわち３２ビット）の場合に“Ｚａｓｓｅｎｈａｕ
ｓの方法”及びこの発明の逆元演算方法をＣ言語で実装
して処理速度を比較した。入力ｘは乱数を発生させて決
定し、繰り返し実行することでＯＳのオーバーヘッドを
除去して比較したところ、この発明の逆元演算方法は
“Ｚａｓｓｅｎｈａｕｓの方法”に比べて１０％以上高
速に逆元を計算できることを確認した。
（すなわち３２ビット）の場合に“Ｚａｓｓｅｎｈａｕ
ｓの方法”及びこの発明の逆元演算方法をＣ言語で実装
して処理速度を比較した。入力ｘは乱数を発生させて決
定し、繰り返し実行することでＯＳのオーバーヘッドを
除去して比較したところ、この発明の逆元演算方法は
“Ｚａｓｓｅｎｈａｕｓの方法”に比べて１０％以上高
速に逆元を計算できることを確認した。
【図１】この発明の実施例の処理手順を示す流れ図。
【図２】この発明の実施例の機能構成を示すブロック
図。
図。
【図３】Ｚａｓｓｅｎｈａｕｓの方法のビット処理の例
を示す図。
を示す図。
フロントページの続き (56)参考文献 特開 平10−207689（ＪＰ，Ａ) ＧＦ（２ｍ）における逆元の高速算法 について，電子情報通信学会技術研究報 告，1987年 ７月18日，Ｖｏｌ．87，Ｎ ｏ．120，ＩＴ87−24 有限体ＧＦ（２ｍ）の逆元の効率的再 帰アルゴリズム，昭和63年電子情報通信 学会春季全国大会講演論文集，1988年 ３月15日，１−299 素数べきを法とする逆元計算アルゴリ ズム，1997年暗号と情報セキュリティ・ シンポジウム講演論文集，1997年 １月 29日，14Ａ (58)調査した分野(Int.Cl.7，ＤＢ名) G09C 1/00 650 G06F 7/72 ＪＩＣＳＴファイル（ＪＯＩＳ)
Claims (2)
- 【請求項１】 入力されたｘを記憶手段に記憶する入力
手段と、 整数ｎ、ｉ（ｎは１以上）および２n ビットの整数ｘ、
ｙ、ａ、ｂを記憶する記憶手段と、 記憶手段に記憶されたｘを用いて［ｘ／２］（ただし
［ｘ］はｘを越えない最大の整数）を演算し、演算結果
をｂとして記憶手段に記憶するｂ初期化第１手段と、 記憶手段に記憶されたｂの最下位ビットをａとして記憶
手段に記憶するａ初期化手段と、 記憶手段に記憶されたａ、ｘ、ｂを用いて［（ａｘ＋
ｂ）／２］を演算し、その演算結果により、記憶手段に
記憶されたｂを更新するｂ初期化第２手段と、 記憶手段に記憶されたｘの下位２ビットを取得してｙと
して記憶手段に記憶するｙ初期化手段と、 記憶手段に記憶されたｉを１にセットするｉ初期化手段
と、 記憶手段に記憶されたｂ、ｙを用いて−ｂｙを演算し、
その演算結果により、記憶手段に記憶されたａを更新す
るａ更新手段と、 記憶手段に記憶されたａ、ｂ、ｘ、ｉを用いて［（ｂ＋
ａｘ）／（２＾（２i））］を演算し、その演算結果に
より、記憶手段に記憶されたｂを更新するｂ更新手段と
（但しｐ＾ｑはｐのｑ乗を表わす）、 記憶手段に記憶されたａ、ｙ、ｉを用いてｙ＋ａ×２＾
（２i ）を演算し、その演算結果により、記憶手段に記
憶されたｙを更新するｙ更新手段と、 記憶手段に記憶されたｉをｉ＋１に更新するｉ更新手段
と、 記憶手段に記憶されたｉ、ｎを読み出し、ｉ＝ｎになる
まで上記ａ更新手段、 上記ｂ更新手段、上記ｙ更新手段、上記ｉ更新手段を順
次動作させる制御手段と、 記憶手段に記憶されたｙを出力する出力手段と、 を有することを特徴とする逆元演算装置。 - 【請求項２】 入力された２n ビットの整数（ｎは１以
上の整数）ｘを記憶手段に記憶する処理と、 記憶手段のｘを読み出し、［ｘ／２］（ただし［ｘ］は
ｘを越えない最大の整数）を演算し、その演算結果を２
n ビットの整数ｂとして記憶手段に記憶する処理と、 記憶手段のｂを読み出し、ｂの最下位ビットを２n ビッ
トの整数ａとして記憶手段に記憶する処理と、 記憶手段のａ、ｘ、ｂを読み出し、［（ａｘ＋ｂ）／
２］を演算し、その演算結果をｂとして記憶手段に記憶
する処理と、 記憶手段のｘを読み出し、ｘの下位２ビットを取得して
２n ビットの整数ｙとして記憶する処理と、 整数ｉを、ｌに初期化して記憶手段に記憶する処理と、 記憶手段からｂ及びｙを読み出し、−ｂｙを演算し、そ
の演算結果により記憶手段に記憶されているａを更新す
るａ更新処理と、 記憶手段からａ、ｂ、ｘ、ｉを読み出し、［（ｂ＋ａ
ｘ）／（２＾（２i ））］を演算し、その演算結果によ
り記憶手段に記憶されているｂを更新するｂ更新処理と
（ただしｐ＾ｑはｐのｑ乗を表わす）、 記憶手段からａ、ｙ、ｉを読み出し、ｙ＋ａ×２＾（２
i ）を演算し、その演算結果により、記憶手段に記憶さ
れているｙを更新するｙ更新処理と、 記憶手段からｉを読み出し、ｉをｉ＋１に更新するｉ更
新処理と、 記憶手段からｉ、ｎを読み出し、ｉ＝ｎになるまで、上
記ａ更新処理、上記ｂ更新処理、上記ｙ更新処理、上記
ｉ更新処理を順次繰返し動作させる処理と、 記憶手段のｙを読み出して出力する処理と、 を逆元演算装置のコンピュータに実行させるプログラム
を記録した記録媒体。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01078899A JP3315087B2 (ja) | 1999-01-19 | 1999-01-19 | 逆元計算装置及びそのプログラム記録媒体 |
| US09/487,597 US6578061B1 (en) | 1999-01-19 | 2000-01-19 | Method and apparatus for data permutation/division and recording medium with data permutation/division program recorded thereon |
| US10/419,241 US6850960B2 (en) | 1999-01-19 | 2003-04-21 | Inverse calculation apparatus and recording medium having stored thereon a program for executing inverse calculation |
| US10/419,244 US6859818B2 (en) | 1999-01-19 | 2003-04-21 | Method and apparatus for permuting input data and recording medium having stored thereon a program for executing permutation |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01078899A JP3315087B2 (ja) | 1999-01-19 | 1999-01-19 | 逆元計算装置及びそのプログラム記録媒体 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000206881A JP2000206881A (ja) | 2000-07-28 |
| JP3315087B2 true JP3315087B2 (ja) | 2002-08-19 |
Family
ID=11760091
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP01078899A Expired - Lifetime JP3315087B2 (ja) | 1999-01-19 | 1999-01-19 | 逆元計算装置及びそのプログラム記録媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3315087B2 (ja) |
-
1999
- 1999-01-19 JP JP01078899A patent/JP3315087B2/ja not_active Expired - Lifetime
Non-Patent Citations (3)
| Title |
|---|
| ＧＦ（２ｍ）における逆元の高速算法について，電子情報通信学会技術研究報告，１９８７年 ７月１８日，Ｖｏｌ．８７，Ｎｏ．１２０，ＩＴ８７−２４ |
| 有限体ＧＦ（２ｍ）の逆元の効率的再帰アルゴリズム，昭和６３年電子情報通信学会春季全国大会講演論文集，１９８８年 ３月１５日，１−２９９ |
| 素数べきを法とする逆元計算アルゴリズム，１９９７年暗号と情報セキュリティ・シンポジウム講演論文集，１９９７年 １月２９日，１４Ａ |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2000206881A (ja) | 2000-07-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Comba | Exponentiation cryptosystems on the IBM PC | |
| US6859818B2 (en) | Method and apparatus for permuting input data and recording medium having stored thereon a program for executing permutation | |
| EP0917047B1 (en) | Apparatus for modular inversion for information security | |
| JP2008293034A (ja) | タイミング攻撃を阻止する標準化されたモジュラべき乗を計算することにより復号メカニズムを実行する方法と装置 | |
| CN113141255B (zh) | 用于在处理设备、对应的处理设备和计算机程序产品中对数据执行密码运算的方法 | |
| WO2010048719A1 (en) | Method and apparatus for modulus reduction | |
| US12524578B2 (en) | Processor architecture and related techniques | |
| CN111385092B (zh) | 使用信息盲化的密码装置及其密码处理方法 | |
| CN108418687B (zh) | 一种适合sm2算法的快速模约减方法和介质 | |
| JP3315087B2 (ja) | 逆元計算装置及びそのプログラム記録媒体 | |
| Kim et al. | High-speed division architecture for GF (2 m) | |
| Bernstein | Optimizing linear maps modulo 2 | |
| CN118713820A (zh) | 一种基于比特切片的aes高阶掩码s盒快速实现方法 | |
| CN111339546B (zh) | 用于生成数据标签的方法、电子设备及计算机存储介质 | |
| Kuramoto et al. | Improved Constant-Time Modular Inversion | |
| Jin et al. | Short-iteration constant-time GCD and modular inversion | |
| Dutta et al. | Polynomial Inversion Algorithms in Constant Time for Post-Quantum Cryptography | |
| Ilkhom et al. | A novel approach to integer factorization: a paradigm in cryptography | |
| KR100194769B1 (ko) | 메모리를 사용하여 유한체상에서 역원을 구하는 방법 | |
| Inoue et al. | A faster variant of cgl hash function via efficient backtracking checks | |
| KR100377185B1 (ko) | 암호시스템의 연산속도 개선 방법 | |
| Cao et al. | EHNP strikes back: analyzing SM2 implementations | |
| JP2004102071A (ja) | 多項式剰余系演算装置、方法及びプログラム | |
| JP3110110B2 (ja) | 暗号復号装置 | |
| US20040081317A1 (en) | Encryption circuit achieving higher operation speed |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090607 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090607 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100607 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100607 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110607 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120607 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130607 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140607 Year of fee payment: 12 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| EXPY | Cancellation because of completion of term |