(57)【特許請求の範囲】
【請求項１】
法の値が偶数である剰余環上の逆元を求める逆元演算装置であって、
２５６ビット幅以上の４つの変数を記憶する多精度記憶手段と、
偶数である法Ｎ、及び逆元を求める被演算値Ａを受け取り、前記被演算値Ａが前記法Ｎ未満であるか否かを判定し、前記Ｎ未満である場合に、前記法Ｎと前記被演算値Ａを前記多精度記憶手段に格納する入力手段と、
前記多精度記憶手段に記憶された前記法Ｎの値を変数Ｍの値として設定し、前記Ｍを前記多精度記憶手段に格納し、前記多精度記憶手段に記憶された前記Ｍを最下位ビットが１となるように右へｔビットシフトする法分割手段と、
前記多精度記憶手段に記憶された前記被演算値Ａとシフト後の前記Ｍを用いて、前記Ｍを法とした剰余環上の前記被演算値Ａの逆元Ｘ１を演算によって算出し、前記Ｘ１を前記多精度記憶手段に格納する第１逆元演算手段と、
前記法分割手段から前記ｔの値を受け取り、前記多精度記憶手段に記憶された前記被演算値Ａを用いて、前記被演算値Ａの下位ｔビットの値を被演算値Ｂの値として設定し、２tを法とした剰余環上の前記被演算値Ｂの逆元Ｘ２を演算によって算出する第２逆元演算手段と、
前記第２逆元演算手段から演算された前記Ｘ２を受け取り、前記多精度記憶手段に記憶された前記Ｘ１を用いて、前記Ｎを法とした剰余環上の前記被演算値Ａの逆元を演算によって算出する合成演算手段を備えたことを特徴とする逆元演算装置。
【請求項２】
前記第１逆元演算手段は、前記被演算値Ａの逆元が存在しないと判断した場合に、前記合成演算手段にエラーを通知し、
前記合成演算手段は、前記第１逆元演算手段からエラーが通知された時、前記逆元Ｘを算出する演算を行わないことを特徴とする請求項１に記載の逆元演算装置。
【請求項３】
前記第１逆元演算手段は、前記Ｍを法とした剰余環上の前記被演算値Ａの逆元Ｘ１を、拡張バイナリユークリッド互除法を用いて演算することを特徴とする請求項１に記載の逆元演算装置。
【請求項４】
前記合成演算手段は、前記Ｎを法とした剰余環上の前記被演算値Ａの逆元Ｘを、中国人の剰余定理を用いて演算することを特徴とする請求項１に記載の逆元演算装置。
【請求項５】
前記入力手段は、前記被演算値Ａが前記法Ｎ以上である場合に、前記被演算値Ａを前記法Ｎで剰余演算することで、前記被演算値Ａを前記法Ｎ未満の正の整数に補正し、前記法Ｎと補正後の前記被演算値Ａを前記多精度記憶手段に格納することを特徴とする請求項１記載の逆元演算装置。
【請求項６】
法の値が偶数である剰余環上の逆元を求める逆元演算方法であって、
偶数である法Ｎ、及び逆元を求める被演算値Ａを受け取り、前記被演算値Ａが前記法Ｎ未満であるか否かを判定し、前記Ｎ未満である場合に、前記法Ｎと前記被演算値Ａを、２５６ビット幅以上の変数を記憶する多精度記憶部に格納する入力ステップと、
前記多精度記憶部に記憶された前記法Ｎの値を変数Ｍの値として設定し、前記Ｍを前記多精度記憶部に格納し、前記多精度記憶部に記憶された前記Ｍを最下位ビットが１となるように右へｔビットシフトする法分割ステップと、
前記多精度記憶部に記憶された前記被演算値Ａとシフト後の前記Ｍを用いて、前記Ｍを法とした剰余環上の前記被演算値Ａの逆元Ｘ１を演算によって算出し、前記Ｘ１を前記多精度記憶部に格納する第１逆元演算ステップと、
前記法分割ステップで演算された前記ｔの値を受け取り、前記多精度記憶部に記憶された前記被演算値Ａを用いて、前記被演算値Ａの下位ｔビットの値を被演算値Ｂの値として設定し、２tを法とした剰余環上の前記被演算値Ｂの逆元Ｘ２を演算によって算出する第２逆元演算ステップと、
前記第２逆元演算ステップで演算された前記Ｘ２を受け取り、前記多精度記憶部に記憶された前記Ｘ１を用いて、前記Ｎを法とした剰余環上の前記被演算値Ａの逆元Ｘを演算によって算出する合成演算ステップを備えたことを特徴とする逆元演算方法。
【請求項７】
前記第１逆元演算ステップは、前記被演算値Ａの逆元が存在しないと判断した場合に、エラーを出力し、
前記合成演算ステップは、前記第１逆元演算ステップからエラーが出力された時、前記逆元Ｘを算出する演算を行わないことを特徴とする請求項６に記載の逆元演算方法。
【請求項８】
前記第１逆元演算ステップは、前記Ｍを法とした剰余環上の前記被演算値Ａの逆元Ｘ１を、拡張バイナリユークリッド互除法を用いて演算することを特徴とする請求項６に記載の逆元演算方法。
【請求項９】
前記合成演算ステップは、前記Ｍを法とした剰余環上の前記被演算値Ａの逆元Ｘ１を、中国人の剰余定理を用いて演算することを特徴とする請求項６に記載の逆元演算方法。
【請求項１０】
前記入力ステップは、前記被演算値Ａが前記法Ｎ以上である場合に、前記被演算値Ａを前記法Ｎで剰余演算することで、前記被演算値Ａを前記法Ｎ未満の正の整数に補正し、前記法Ｎと補正後の前記被演算値Ａを、２５６ビット幅以上の変数を記憶する多精度記憶部に格納することを特徴とする請求項６に記載の逆元演算方法。
【請求項１１】
コンピュータに法の値が偶数である剰余環上の逆元を求めさせる逆元演算プログラムであって、
偶数である法Ｎ、及び逆元を求める被演算値Ａを受け取り、前記被演算値Ａが前記法Ｎ未満であるか否かを判定し、前記Ｎ未満である場合に、前記法Ｎと前記被演算値Ａを、２５６ビット幅以上の変数を記憶する多精度記憶部に格納する入力ステップと、
前記多精度記憶部に記憶された前記法Ｎの値を変数Ｍの値として設定し、前記Ｍを前記多精度記憶部に格納し、前記多精度記憶部に記憶された前記Ｍを最下位ビットが１となるように右へｔビットシフトする法分割ステップと、
前記多精度記憶部に記憶された前記被演算値Ａとシフト後の前記Ｍを用いて、前記Ｍを法とした剰余環上の前記被演算値Ａの逆元Ｘ１を演算によって算出し、前記Ｘ１を前記多精度記憶部に格納する第１逆元演算ステップと、
前記法分割ステップで演算された前記ｔの値を受け取り、前記多精度記憶部に記憶された前記被演算値Ａを用いて、前記被演算値Ａの下位ｔビットの値を被演算値Ｂの値として設定し、２tを法とした剰余環上の前記被演算値Ｂの逆元Ｘ２を演算によって算出する第２逆元演算ステップと、
前記第２逆元演算ステップで演算された前記Ｘ２を受け取り、前記多精度記憶部に記憶された前記Ｘ１を用いて、前記Ｎを法とした剰余環上の前記被演算値Ａの逆元Ｘを演算によって算出する合成演算ステップを備えたことを特徴とする逆元演算プログラム。
【請求項１２】
前記第１逆元演算ステップは、前記被演算値Ａの逆元が存在しないと判断した場合に、エラーを出力し、
前記合成演算ステップは、前記第１逆元演算ステップからエラーが出力された時、前記逆元Ｘを算出する演算を行わないことを特徴とする請求項１１に記載の逆元演算プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、法の値が偶数である剰余環において、逆元を演算する逆元演算装置及びその方法に関する。また、公開鍵アルゴリズムであるＲＳＡの鍵対を生成する、ＲＳＡ鍵生成装置、及びその方法に関する。
【０００２】
【従来の技術】
ＲＳＡ暗号の鍵対は、個々の機器にて生成することにより、より高い安全性が確保できる。これは、センターが鍵対を生成して機器に配布するといった方法に比べ、秘密鍵が機器から外にでないためである。特に、機器自身に高い安全性が必要とされる、ＩＣカードシステムにおいては、演算リソースが制限されているＩＣカード内での効率的なＲＳＡ暗号鍵対生成が必要となる。
【０００３】
通常、ＲＳＡ暗号鍵対生成方法は、次の手順で行う。
【０００４】
（１）  素数ｐ、ｑを生成する。ｎ＝ｐ×ｑとする。
【０００５】
（２）  １≦ｅ：奇数＜Ｌ＝ＬＣＭ（ｐ−１、ｑ−１）を決めて、ｅの逆元ｄを求める（ＬＣＭとは最小公倍数のことである）。
【０００６】
（３）  （ｎ、ｅ）を公開し、（ｐ、ｑ、ｄ）を秘密にする。
【０００７】
この手順のうち（２）のｅからｄの算出には、Ｌを法とする剰余環上の逆元演算が必要となる。
【０００８】
以下では、従来の逆元演算を説明し、演算リソースが限定されている機器にて逆元演算を実装することを前提に、
・内部変数が蓄積されるメモリ容量が少ない
・制御が簡易である
という観点より評価する。
【０００９】
剰余環上の逆元演算方法としては、ユークリッド互除法、レーマ法、バイナリユークリッド互除法などが知られている。例えば文献「暗号処理入門」（岡本栄司著、共立出版、１９９３）のｐ．８には、ユークリッド互除法のアルゴリズムが記載されている。この記載に基づき、ユークリッド互除法を用いて剰余環上の逆元を求めるアルゴリズムを説明する。
【００１０】
図１は前記文献に示されたアルゴリズムをフローチャートにしたもので、入力値Ａに対して、ｐを法とした剰余環上の逆元を求めるものである。
【００１１】
最初に入力ステップ１０１において、逆元演算を行う被演算数Ａ、及び剰余環の法の値ｐを入力する。次に内部変数初期化ステップ１０２において、Ｕ１、Ｕ２、Ｖ１、Ｖ２という４つの内部変数をそれぞれ初期化する。次にユークリッド互除法演算ステップ１０３において、内部変数Ｕ１、Ｕ２、Ｖ１、Ｖ２、の値を更新してゆく。更新した値について判定ステップ１０４において条件が成立しない限り、ユークリッド互除法演算ステップ１０３が繰り返される。判定ステップ１０４において条件が成立すると、ＧＣＤ確認ステップ１０５に進む。ＧＣＤとは最大公約数のことである。ＧＣＤ確認ステップ１０５では、ＧＣＤの値が１か否かを確認する。そして最後に出力ステップ１０６において値を出力する。ＧＣＤ確認ステップ１０５においてＧＣＤが１であると確認された時は、出力ステップ１０６において演算された逆元の値が出力される。また１でないと確認された時は、出力ステップ１０６においてエラーが出力される。
【００１２】
図２はユークリッド互除法ステップ１０３の詳細をフローチャートにしたものである。ここでは、さらに３つの内部変数Ｗ、Ｔ１、Ｔ２を用い、最初に初期化した変数Ｕ１、Ｕ２、Ｖ１、Ｖ２の値を更新してゆく。
【００１３】
この方法によって正しい値が出力されることは前記文献等に記されているためここでは省略する。この方法の特徴としては、内部変数の更新に多精度の除算を用いるということが挙げられる。また中間値を格納する内部変数として、７つの多精度の変数格納領域を必要とするということも挙げられる。単精度が３２ビットで、法の値が１０２４ビットのＲＳＡ暗号を考えると、この７つの多精度変数は、７×３２＝２２４ワードのワークメモリを必要とする。
【００１４】
次に別の従来例であるレーマ法について説明する。レーマ法は前記ユークリッドの互除法を改良した方法で、単精度の除算を用いることによって多精度乗算の回数を減らしたものである。例えば文献「ＨＡＮＤＢＯＯＫ  ｏｆ  ＡＰＰＬＩＥＤ  ＣＲＹＰＴＯＧＲＡＰＨＹ」（Ａｌｆｒｅｄ  Ｊ．Ｍｅｎｅｚｅｓ他、ＣＲＣ  Ｐｒｅｓｓ、１９９７）のｐ．６０７には、レーマ法のアルゴリズムが記載されている。但しここには剰余環上の逆元を求めるアルゴリズムではなく、ＧＣＤを求めるアルゴリズムとして記述してある。また同書のｐ．６７にはＧＣＤを求めるユークリッド互除法から、ＧＣＤが１の時の剰余環上の逆元を求める拡張方法が記述してある。従ってこの二つの記載に基づけばレーマ法を用いて剰余環上の逆元を求めるアルゴリズムが導き出せる。ここでは前記二つの記載方法に基づいたレーマ法のアルゴリズムを説明する。
【００１５】
図３はレーマ法のアルゴリズムをフローチャートにしたもので、入力値Ａに対して、ｐを法とした剰余環上の逆元を求めるものである。図１と比較すると分かる通り、内部変数を更新する部分を除くとユークリッド互除法と全く同じである。３０１がレーマ演算ステップで、ユークリッド互除法のユークリッド互除法演算ステップ１０３に相当する処理である。
【００１６】
図４は図３のレーマ演算ステップの詳細フローチャートである。図４においてアルファベット大文字で始まる変数は多精度の値を、アルファベット小文字で始まる変数は単精度の値を示している。ここで単精度とはレーマの演算を行う時に定める演算単位で、通常８、１６、３２、６４などの値が用いられる。
【００１７】
４０１は単精度変数初期化ステップで、ｕ、ｖ、ａ、ｂ、ｃ、ｄの６つの単精度変数を初期化している。ｕ、ｖはそれぞれＵ２の０でない最上位単精度値、及びＶ２の同位桁の単精度値が代入される。４０２は第１のレーマ演算判定ステップで、レーマ演算が継続できるか否かを判定する。継続できない場合には、それまでに計算されたａ〜ｄの値を用いて内部変数Ｕ１、Ｖ１、Ｕ２、Ｖ２の値の更新処理に移る。４０３は第２のレーマ演算判定ステップで、レーマ演算によりａ〜ｄの値が正しく計算できるか否かを判定する。演算が正しく計算できない場合には、ｑ、ｑ’の値が異なるため、第１のレーマ演算判定ステップと同様、それまでに計算されたａ〜ｄの値を用いて内部変数Ｕ１、Ｖ１、Ｕ２、Ｖ２の値の更新処理に移る。
【００１８】
４０４は単精度変数更新ステップで、ａ〜ｄの単精度変数を更新する。これらの変数は図１のユークリッド互除法における内部変数Ｗにあたり、複数の単精度変数を持つことにより複数の多精度乗算を一度に行うことが可能となっている。またこの単精度変数更新ステップが実行されると、第１のレーマ演算判定ステップ４０２に戻り、レーマ演算が継続可能な限り単精度変数更新ステップ４０４が繰り返される。４０５はまとめ演算判定ステップで、単精度変数ｂの値により多精度乗算のまとめ演算を行うか否かを判定する。4０６は第１の内部変数更新ステップで、これまでに計算されたａ〜ｄの単精度変数の値を用い、それぞれただ一度の乗算でＵ１、Ｕ２、Ｖ１、Ｖ２の４つの内部変数の値を更新する。４０７は第２の内部変数更新ステップで、第１の内部変数更新ステップが使えない時に通常のユークリッド互除法と同じ除算、乗算による内部変数の更新を行う。
【００１９】
この方法は単精度変数更新ステップ４０４を繰り返すことにより、４０６、４０７の多精度演算となる内部変数更新回数を減少させることができ、ユークリッド互除法に比べ実行速度が速くなるという特徴がある。しかし第１の内部変数更新ステップ４０６が使えない時に、第２の内部変数更新ステップ４０７を用いるため、多精度の除算を行わなくて済むようにはできない。またフローチャートを見ても分かるよう、多精度値から単精度値を取得するなど、非常に制御が複雑になる。さらにレーマ法の特徴としては、ユークリッド互除法と同様、中間値を格納する領域として、７つの多精度の内部変数を必要とするということが挙げられる。即ち、単精度が３２ビットで、法の値が１０２４ビットのＲＳＡ暗号では２２４ワードのワークメモリを必要とする。
【００２０】
また特願２００１−０９２４８１号公報によれば、多精度の除算を行わず、近似値を用いた改良レーマ法について記されている。しかしこの方法も通常のレーマ法と同様制御が複雑になることに変わりはない。また多精度の除算を行わない分、多精度内部変数の数が減少するが、それでも６つ必要となる。即ち、単精度が３２ビットで、法の値が１０２４ビットのＲＳＡ暗号では６×３２＝１９２ワードのワークメモリを必要とする。
【００２１】
次に別の従来例であるバイナリユークリッド互除法について説明する。前記ユークリッドの互除法では、ユークリッド互除法演算ステップ１０３において乗除算が必要であった。また前記レーマ法では、多精度値から単精度値を取得するなど複雑な制御が必要であった。バイナリユークリッド互除法は、これらのいずれも使用せず、加減算とシフト算のみで同じ効果を得るものである。加減算とシフト算はハードウェアの実装が容易な演算である。
【００２２】
例えば文献「ＨＡＮＤＢＯＯＫ  ｏｆ  ＡＰＰＬＩＥＤ  ＣＲＹＰＴＯＧＲＡＰＨＹ」（Ａｌｆｒｅｄ  Ｊ．Ｍｅｎｅｚｅｓ他、ＣＲＣ  Ｐｒｅｓｓ、１９９７）のｐ．６０８には、バイナリユークリッド互除法のアルゴリズムが記載されている。図５〜図７がバイナリユークリッド互除法を用い剰余環上の逆元を求めるアルゴリズムを、フローチャートにしたものである。これらの図を用いてバイナリユークリッド互除法を説明する。またバイナリユークリッド互除法は、前記ユークリッド互除法を改良したものであるため、そのフロー図である図１の各ステップとの対応も同時に説明する。
【００２３】
図５はバイナリユークリッド互除法の大きな流れを図にしたもので入力値Ａに対して、ｐを法とした剰余環上の逆元を求めるものである。但しここではｐを奇数と限定している。図１と比較すると分かる通り、内部変数を更新する部分を除くとユークリッド互除法と全く同じである。５０１がバイナリユークリッド互除法演算ステップで、ユークリッド互除法のユークリッド互除法演算ステップ１０３に相当する処理である。
【００２４】
図６はバイナリユークリッド互除法演算ステップの詳細フローチャートで、第１の内部変数更新停止判定ステップ６０１、第１の内部変数更新ステップ６０２、第２の内部変数更新停止判定ステップ６０３、第２の内部変数更新ステップ６０４、第３の内部変数更新ステップ６０５において、それぞれの内部変数を更新してゆく。これらのステップが、ユークリッド互除法における図２に対応する。
【００２５】
第１の内部変数更新停止判定ステップ６０１では、Ｖ２が偶数か奇数かを判定する。ここでＶ２が奇数と判定された時は、変数Ｖ１、Ｖ２の更新を停止し次の処理に移る。第１の内部変数更新ステップ６０２では、内部変数Ｖ１、Ｖ２を２で割る。Ｖ１については剰余体上において２で割る処理を行う。この２で割る処理がシフト演算で実現できるため、バイナリユークリッド互除法では乗除算を必要としない。
【００２６】
第２の内部変数更新停止判定ステップ６０３では、Ｕ２が偶数か奇数かを判定する。ここでＵ２が奇数と判定された時は、変数Ｕ１、Ｕ２の更新を停止し次の処理に移る。第２の内部変数更新ステップ６０４では、内部変数Ｕ１、Ｕ２を２で割る。但し第１の内部変数更新ステップ６０２と同様Ｕ１については剰余体上において２で割る処理を行う。
【００２７】
ここまでの内部変数更新処理において、Ｕ２、Ｖ２のどちらかは必ず奇数であり、Ｕ１、Ｕ２の更新、もしくは、Ｖ１、Ｖ２の更新のどちらかしか行われない。従って、これらの処理が図２の内部変数Ｗの演算（２０１）と内部変数Ｗの値を乗算する演算処理（２０２の一部）に対応する。
【００２８】
次に第３の内部変数更新ステップ６０５において、Ｕ１、Ｕ２、もしくはＶ１、Ｖ２の内部変数を更新する。この処理は図２の減算（２０２の一部）、及び内部変数Ｕ１、Ｕ２、Ｖ１、Ｖ２の更新処理（２０３、２０４）に対応する。
【００２９】
この方法は多精度の乗除算を行わなくて済むという特徴があるが、その分ユークリッド互除法に比べ実行速度が遅くなる。また、ここに示したフローチャートは、法の値を奇数と限定した時のものであるが、必要な内部変数が４つで良いという特徴がある。即ち、単精度が３２ビットで、法の値が１０２４ビットのＲＳＡ暗号の場合４×３２＝１２８ワードのワークメモリがあれば良い。
【００３０】
法の値が偶数の場合、図６の詳細フローチャート中、第１の内部変数更新ステップ６０２、第２の内部変数更新ステップ６０４、第３の内部変数更新ステップ６０５が異なってくる。図７は、法の値が偶数の時の、第１の内部変数更新停止判定ステップから第１の内部変数更新ステップにかけての詳細フロー図である。図で見ると分かるように、Ｖ３という新たな内部変数を用い、その値も内部変数として更新する形となる。第２の内部変数更新ステップ、第３の内部変数更新ステップの詳細フロー図は省略するが、同様にＵ３という新たな内部変数も必要となってくる。即ち法の値が偶数の時には、さらにＵ３、Ｖ３といった２つの内部変数の追加が必要になり、必要な多精度の内部変数の数は６つとなる。即ち、単精度が３２ビットで、法の値が１０２４ビットのＲＳＡ暗号の場合、１９２ワードのワークメモリを必要とする。
【００３１】
【発明が解決しようとする課題】
これらの従来の技術を見てみると、ＲＳＡ暗号の鍵対生成処理に必要となる逆元演算では、法の値が偶数の逆元演算を行わなければならず、少なくとも内部変数として多精度変数が６つ必要であった。これは、例えばＩＣカードのようにメモリ容量に制限がある環境での実装を困難にする要因であった。一方、法の値が奇数の時に逆元を求める方法として、多精度変数が４つでよい変数削減版拡張バイナリユークリッド互除法があった。しかしこの変数削減版拡張バイナリユークリッド互除法はＲＳＡ暗号の鍵対生成処理には使えないという課題があった。
【００３２】
そこで本発明はかかる問題点に鑑みてなされたものであり、法の値が偶数のときの逆元演算を、法の値が奇数の時の変数削減版拡張バイナリユークリッド互除法を利用して行うことを目的とする。即ち多精度の内部変数の数を４つにとどめながらＲＳＡ暗号の鍵対生成で使われる逆元演算を行うことを目的とする。多精度の内部変数は、ハードウェア回路を作成する際、通常メモリ領域として実装するため、少ないメモリ量でＲＳＡ暗号の鍵対生成を実行することも目的となる。
【００３３】
【課題を解決するための手段】
この課題を解決するために本発明に係る逆元演算装置は、法の値が偶数である剰余環上の逆元を求める逆元演算装置であって、２５６ビット幅以上の４つの変数を記憶する多精度記憶手段と、偶数である法Ｎ、及び逆元を求める被演算値Ａを受け取り、前記被演算値Ａが前記法Ｎ未満であるか否かを判定し、前記Ｎ未満である場合に、前記法Ｎと前記被演算値Ａを前記多精度記憶手段に格納する入力手段と、前記多精度記憶手段に記憶された前記法Ｎの値を変数Ｍの値として設定し、前記Ｍを前記多精度記憶手段に格納し、前記多精度記憶手段に記憶された前記Ｍを最下位ビットが１となるように右へｔビットシフトする法分割手段と、前記多精度記憶手段に記憶された前記被演算値Ａとシフト後の前記Ｍを用いて、前記Ｍを法とした剰余環上の前記被演算値Ａの逆元Ｘ１を演算によって算出し、前記Ｘ１を前記多精度記憶手段に格納する第１逆元演算手段と、前記法分割手段から前記ｔの値を受け取り、前記多精度記憶手段に記憶された前記被演算値Ａを用いて、前記被演算値Ａの下位ｔビットの値を被演算値Ｂの値として設定し、２tを法とした剰余環上の前記被演算値Ｂの逆元Ｘ２を演算によって算出する第２逆元演算手段と、前記第２逆元演算手段から演算された前記Ｘ２を受け取り、前記多精度記憶手段に記憶された前記Ｘ１を用いて、前記Ｎを法とした剰余環上の前記被演算値Ａの逆元を演算によって算出する合成演算手段を備えたことを特徴とする。
【００３４】
また、本発明に係る逆元演算装置は、法の値が偶数である剰余環上の逆元を求める逆元演算装置であって、前記特徴に加え、前記第１逆元演算手段は、前記被演算値Ａの逆元が存在しないと判断した場合に、前記合成演算手段にエラーを通知し、前記合成演算手段は、前記第１逆元演算手段からエラーが通知された時、前記逆元Ｘを算出する演算を行わないことを特徴とする。
【００３６】
【発明の実施の形態】
以下、本発明の実施の形態について、図面を用いて説明する。
【００３７】
（実施の形態１）
図８は、本発明における、入力値Ａに対して、偶数であるＮを法とした剰余環上の逆元を求める逆元演算方法の、大きな流れをフローチャートにしたものである。８０１は入力処理で、逆元演算対象となる値の入力を行う。８０２は法分割処理で、入力処理で入力された値のうち法の値を、以降の処理で使用できるように分割する。８０３は第１逆元演算処理で、法分割処理８０２で分割された一方の値を用い、第１の部分的な逆元を求める。８０４は第２逆元演算処理で、法分割処理８０２で分割された値のうち、第１逆元演算処理８０３で用いなかった値を用い、第２の部分的な逆元を用いる。なお、この実施の形態では第１逆元演算処理、第２逆元演算処理の順序で処理を行っているが、逆の順序で処理を行っても良い。またこの二つの処理は独立して実行できるため、同時に並列に処理を行っても良い。８０５は合成演算処理で、第１逆元演算処理８０３と第２逆元演算処理８０４で求められた二つの部分的な逆元を合成し、入力値に対する逆元を求める。８０６は出力処理で、求められた逆元を出力する。各処理の詳細を以降に説明する。
【００３８】
図９は、図８における入力処理８０１の詳細フローチャートである。９０１は値入力ステップで、逆元を求める剰余環の法の値としてＮを、逆元を求める被演算値としてＡを入力する。但しここではＡを奇数、Ｎを偶数とする。９０２は入力値検証ステップで、値入力ステップで入力された被演算値が法Ｎより小さい値であるかを検証する。９０３は入力値補正ステップで、入力値検証ステップ９０２で入力値Ａが法の値Ｎ以上であると判定された場合にのみ、剰余演算を行うことで被演算値をＮ未満に補正する。なお、この実施の形態では被演算値として入力される値が奇数であるという限定を行ったが、任意の値を被演算値として入力し、その値が偶数の場合には出力処理でエラー出力を行っても良い。
【００３９】
図１０は、図８における法分割処理８０２の詳細フローチャートである。１００１は分割値初期設定ステップで、変数ｔの値を０に、変数Ｍの値をＮに初期設定する。１００２は分割値更新ステップで、ｔの値を１増加させ、Ｍの値を右に１ビットシフトする。右へ１ビットシフトすることは、２で割ることと同じ処理である。ここで、入力された値Ｎは必ず偶数である。従って初期状態での値Ｍも必ず偶数となり、１００２の分割値更新ステップを最初に通る時、Ｍを１ビット右シフトする、即ち２で割ることは、必ず実行可能である。１００３は分割値更新終了判定ステップで、Ｍの最下位ビットを判定する。Ｍの最下位ビットが０の場合は、再び分割値更新ステップに戻る。分割値更新ステップ１００２と分割値更新終了判定ステップ１００３により、逆元を求める剰余環の法Ｎを、Ｎ＝Ｍ×２tとなるＭとｔに分割する処理が行われる。なお、この実施の形態では分割値のために新たな変数を用いたが、Ｎは以降の処理では使用しないため、Ｍの代わりにＮを用い、分割値更新ステップ１００２でＮの値を更新し、分割値更新終了判定ステップ１００３でＮの最下位ビットを判定するとしても良い。
【００４０】
図１１は、図８における第１逆元演算処理８０３の詳細フローチャートである。１１０１は第１被演算値補正ステップで、法分割処理８０２で求めた分割値のうちＭを用い、Ａ  ｍｏｄ  Ｍの値をＣに設定する。１１０２は第１部分逆元演算ステップで、Ｍを法とした剰余環上のＣの逆元を演算する。Ｍは奇数となるため、従来技術の拡張バイナリユークリッド互除法を用いることができるが、Ｍを法とした剰余集合は、体ではなく環であるため、逆元が存在しない場合がある。従って、逆元が存在しない時Ｘ１を０に、逆元が存在する時Ｘ１をその値（Ｃ(-1)  ｍｏｄ  Ｍ）に設定する。なお、この実施の形態では、第１部分逆元演算ステップ１１０２における逆元演算方法として、従来技術の拡張バイナリユークリッド互除法を用いたが、他の従来技術を用いても良い。またこの実施の形態では被演算値の補正値のために新たな変数を用いたが、Ａは下位ｔビットを除いて以降の処理では使用しない。従って下位ｔビットを保持しておけば、Ｃの代わりにＡを用い逆元の演算を行っても良い。
【００４１】
図１２は、図８における第２逆元演算処理８０４の詳細フローチャートである。１２０１は分割値判定ステップで、法分割処理８０２で求めた分割値のうちｔの値が８以下であるかどうかを確認する。８以下の場合、以降の処理が１バイト値の演算となるためである。１２０２は第２被演算値補正ステップで、Ａの下位ｔビットをＢに設定する。１２０３は第２部分逆元演算ステップで、分割値判定ステップ１２０１でｔの値が８以下の時、従来技術の拡張ユークリッド互除法を用いて、２tを法とした剰余環上のＢの逆元を演算しＸ２に設定する。１２０４は演算不能値設定ステップで、分割値判定ステップ１２０１でｔの値が８より大きい時、Ｘ２に０を設定する。なお、この実施の形態では、単精度を８ビット値として分割値判定ステップの判定条件を定めたが、使用する計算機の精度に合わせ判定条件の値を８以外の値（１６、３２など）にしても良い。また、使用する計算機が高速で多精度の演算処理が可能な時などに、分割値判定ステップ１２０１、演算不能値設定ステップ１２０４を行わず、常に第２被演算値補正ステップ１２０２、第２部分逆元演算ステップ１２０３を実行する構成としても良い。また、第２部分逆元演算ステップ１２０３における逆元演算方法として、従来技術の拡張ユークリッド互除法を用いたが、他の従来技術を用いても良い。
【００４２】
図１３は、図８における合成演算処理８０５の詳細フローチャートである。１３０１は合成判定ステップで、Ｘ１の値、及びＸ２の値が０以外の時次のステップを実行する。１３０２は中国人の剰余定理演算ステップで、これまでの処理で求めた値を、中国人の剰余定理に適用し、求める逆元を演算する。中国人の剰余定理は、例えば文献「暗号処理入門」（岡本栄司著、共立出版、１９９３）のｐ．１０に詳しく述べられている。具体的には、２tを法とした剰余環上のＭの逆元を求めＹ１とし、Ｘ２−Ｘ１に対し２tの剰余をＹ２とし、２tを法とした剰余環上のＹ１×Ｙ２の値とＭの積にＸ１を加算することで、入力値ＡのＮを法とした剰余環上の逆元Ｘを求める。
【００４３】
図１４は、図８における出力処理８０６の詳細フローチャートである。１４０１は第１エラー判定ステップで、Ｘ１が０かどうか判定する。１４０２は第１エラー出力ステップで、第１エラー判定ステップ１４０１でＸ１が０と判定された時、求める逆元が存在しない旨のエラーを出力する。１４０３は第２エラー判定ステップで、第１エラー判定ステップ１４０１でＸ１が０でないと判定された時、Ｘ２が０かどうか判定する。１４０４は第２エラー出力ステップで、第２エラー判定ステップ１４０３でＸ２が０と判定された時、２tの値が単精度を超えたため演算できない旨のエラーを出力する。１４０５は逆元出力ステップで、第２エラー出力ステップでＸ２が０でないと判定された時、合成演算処理８０５で計算されたＸの値を求める逆元として出力する。
【００４４】
図１５は、本発明における逆元演算装置の全体構成図である。１５０１は入力部で、図９のアルゴリズムに従って被演算値Ａと剰余環の法の値Ｎを入力する。被演算値Ａは、後述する第１逆元演算部と第２逆元演算部に送信する。法の値Ｎは、後述する法分割部に送信する。１５０２は法分割部で、図１０のアルゴリズムに従い、法ＮをＮ＝Ｍ×２t（Ｍは奇数）を満たすＭとｔに分割する。値Ｍは後述する第１逆元演算部に送信する。値ｔは後述する第２逆元演算部に送信する。
【００４５】
１５０３は第１逆元演算部で、図１１のアルゴリズムに従い、Ｘ１＝Ａ(-1)  ｍｏｄ  Ｍを満たすＸ１を求める。値Ｘ１は後述する合成演算部に送信する。１５０４は第２逆元演算部で、図１２のアルゴリズムに従い、Ｘ２＝Ａ(-1)  ｍｏｄ  ２tを満たすＸ２を求める。値Ｘ２は後述する合成演算部に送信する。
【００４６】
１５０５は合成演算部で、図１３のアルゴリズムに従い、法の値がＮである剰余環上のＡの逆元値Ｘを求める。値Ｘは後述する出力部に送信する。１５０６は出力部で求めた値Ｘを出力する。
【００４７】
なお、この実施の形態ではエラー処理に関する部分を省略したが、図９〜図１３のアルゴリズムによるエラー判定を入力部１５０１、第１逆元演算部１５０３、第２逆元演算部１５０４、合成演算部１５０５で行い、その結果をエラー情報として出力部１５０６に送信するとしても良い。そして出力部１５０６では送信されたエラー情報に従ってエラー値を出力するとしても良い。
【００４８】
図１８は、本発明における逆元演算方法で用いられる変数の数を、従来方法と合わせて表にしたものである。多精度変数は、例えば２５６ビット幅など、大きな領域を取る変数である、単精度変数は、例えば８ビット幅など、小さな領域を取る変数である。本発明による方法では第１の逆元演算処理では拡張バイナリユークリッド互除法を、第２の演算処理では拡張ユークリッド互除法を使用した場合の変数の数を表している。本発明による方法では中国人の剰余定理を使って最後に合成を行っているが、その時の変数は第１の逆元演算処理で一時的に使っていたものを再利用すれば良い。従って、全体として必要なのは拡張バイナリユークリッド互除法における多精度変数（４つ）と、拡張ユークリッド互除法における単精度変数（７つ）になる。
【００４９】
（実施の形態２）
図１６は、本発明におけるＲＳＡ鍵対生成方法の流れをフローチャートにしたものである。１６０１は素数取得処理で、従来技術を用い、異なる素数ｐ、ｑを取得する。１６０２は法演算処理で、素数取得処理１６０１で得られた素数を用い（ｐ−１）と（ｑ−１）の積を求め法の値Ｎとする。なお、この実施の形態では（ｐ−１）、（ｑ−１）の積を法Ｎの値としたが、（ｐ−１）、（ｑ−１）の最小公倍数を法Ｎと値としても良い。
【００５０】
１６０３は公開鍵取得処理で、従来技術を用い小さいビット数（８ビット程度）の奇数乱数を取得し値ｅとする。なお、この実施の形態では値ｅとして奇数乱数を取得したが、奇数値を入力する形としても良い。
【００５１】
１６０４は逆元演算処理で、実施の形態１を用い、偶数を法とした剰余環上の逆元を求める。
【００５２】
１６０５は繰り返し制御処理で、逆元演算処理１６０４の結果がエラーである時、公開鍵取得処理１６０３と逆元演算処理１６０４を再び行う。逆元演算処理１６０４の結果が正常の時、次の処理にすすむ。なお、この実施の形態では逆元演算処理の結果がエラーである時、公開鍵取得処理を行う形としたが、公開鍵取得処理の代わりに、素数取得処理と法演算処理を行う形としても良い。
【００５３】
１６０６は鍵対出力処理で、これまでの処理で得られた結果を元にＲＳＡ公開鍵、ＲＳＡ秘密鍵の値を計算し出力する。
【００５４】
図１７は、本発明におけるＲＳＡ鍵対生成装置の全体構成図である。１７０１は素数取得部で、従来技術を用い、異なる素数ｐ、ｑを取得する。素数ｐ、ｑは、後述する法演算部と鍵対出力部に送信する。１７０２は法演算部で、（ｐ−１）と（ｑ−１）の積を法Ｎの値とする。法Ｎは後述する逆元演算部に送信する。なお、この実施の形態では法Ｎの値を（ｐ−１）と（ｑ−１）の積としたが、この二つの値の最小公倍数としても良い。
【００５５】
１７０３は公開鍵取得部で、従来技術を用い小さいビット数（８ビット程度）の奇数乱数を取得し値ｅとする。値ｅは後述する逆元演算部と鍵対出力部に送信する。なお、この実施の形態では値ｅとして奇数乱数を取得したが、奇数値を入力する公開鍵入力部としても良い。
【００５６】
１７０４は逆元演算部で、偶数を法とした剰余環上の逆元ｄ＝ｅ(-1)  ｍｏｄＮを求める。この逆元演算部の詳細が、実施の形態１で説明したものになり、その構成図が図１５となる。
【００５７】
１７０５は繰り返し制御部で、逆元演算部の結果を受け、逆元演算部が正常出力を行った時、後述する鍵対出力部を動作させ、逆元演算部がエラー出力を行った時、公開鍵取得部と逆元演算部を再び動作させる。なお、この実施の形態では逆元演算部がエラー出力を行った時、公開鍵取得部と逆元演算部を再び動作させる形としたが、素数取得部と法演算部と逆元演算部を再び動作させる形としても良い。また逆元演算部がエラー出力を行った時、後述する鍵対出力部においてエラー出力を行うように制御しても良い。
【００５８】
１７０６は鍵対出力部で逆元演算部が正常出力を行った時、ＲＳＡ公開鍵の値として（ｅ、ｐ×ｑ）を、ＲＳＡ秘密鍵の値として（ｄ、ｐ、ｑ）を出力する。
【００５９】
（実施の形態３）
図１９は、本発明によるＲＳＡ鍵生成装置を組み込んだメッセージ送受信システム例である。（ａ）はメッセージにＲＳＡ署名を付加する場合である。１９０１はメッセージ送信装置で、メッセージをメッセージ受信装置に送信する。またこの装置はＲＳＡ署名を行うための機構を組み込んでいる。１９０２はメッセージ受信装置で、メッセージをメッセージ送信装置から受信する。またこの装置は、ＲＳＡ署名検証を行うための機構を組み込んでいる。１９０３はメッセージ送信装置に組み込まれたＲＳＡ署名装置で、メッセージからＲＳＡ署名を生成する。その際ＲＳＡ秘密鍵を必要とする。１９０４はＲＳＡ検証装置で、ＲＳＡ署名を検証する。その際メッセージ送信装置のＲＳＡ公開鍵を必要とする。１９０５は本発明によるＲＳＡ鍵生成装置で、ＲＳＡ公開鍵、秘密鍵のペアを生成し、ＲＳＡ署名装置にＲＳＡ秘密鍵を、ＲＳＡ検証装置にＲＳＡ公開鍵を提供する。
【００６０】
この構成により、メッセージ送信装置は、ＲＳＡ鍵生成を行い、メッセージにＲＳＡ署名を行うと共に、署名とＲＳＡ公開鍵をメッセージ受信装置に送信する。メッセージ装置は、受け取った情報からＲＳＡ署名検証を行うことでメッセージを復元し、送信者と送信されてきたメッセージを認証することができる。
【００６１】
（ｂ）はメッセージをＲＳＡ暗号化する場合である。１９０６はメッセージ送信装置で、メッセージをＲＳＡ暗号化してメッセージ受信装置に送信する。１９０７はメッセージ受信装置で、暗号化メッセージをメッセージ送信装置から受信し復号する。１９０８はメッセージ送信装置に組み込まれたＲＳＡ暗号装置で、メッセージをＲＳＡ暗号する。その際メッセージ受信装置のＲＳＡ公開鍵を必要とする。１９０９はＲＳＡ復号装置で、暗号メッセージをＲＳＡ復号する。その際ＲＳＡ秘密鍵を必要とする。１９１０は本発明によるＲＳＡ鍵生成装置で、ＲＳＡ公開鍵、秘密鍵のペアを生成し、ＲＳＡ暗号装置にＲＳＡ公開鍵を、ＲＳＡ復号装置にＲＳＡ秘密鍵を提供する。
【００６２】
この構成により、メッセージ送信装置は、受け取ったＲＳＡ公開鍵を用い、メッセージの暗号化を行い、暗号化メッセージをメッセージ受信装置に送信する。メッセージ装置は、ＲＳＡ鍵生成を行い、ＲＳＡ公開鍵をメッセージ送信装置に渡すと共に、受信した暗号化メッセージを復号することで秘匿通信を行うことができる。
【００６３】
【発明の効果】
以上のように本発明によれば、図１１〜図１３に示したように、逆元の演算を、法が奇数の時の拡張バイナリユークリッド互除法、単精度の拡張ユークリッド互除法、中国人の剰余定理の演算のみで行うことができる。また図１５に示したように、逆元演算装置を、上記３つの演算を行う手段を備えた構成とすることができる。従って、従来の方法と比較した変数の数が、図１８に示した表のようになり、ハードウェアに適した制御のみで、メモリ量を少なくした逆元演算装置となる。
【００６４】
また、図１６、１７に示したように、上記逆元演算方法を用いたＲＳＡ鍵生成方法とし、上記逆元演算装置によって構成されたＲＳＡ鍵生成装置とすることができる。従って、ハードウェアに適した制御のみで、メモリ量を少なくしたＲＳＡ鍵生成装置となる。
【図面の簡単な説明】
【図１】従来のユークリッド互除法による逆元演算処理のフローチャート
【図２】従来のユークリッド互除法のユークリッド互除法演算処理詳細フローチャート
【図３】従来のレーマ法による逆元演算処理の全体フローチャート
【図４】従来のレーマ法のレーマ演算処理詳細フローチャート
【図５】従来のバイナリユークリッド互除法による逆元演算処理の全体フローチャート
【図６】従来のバイナリユークリッド互除法のバイナリユークリッド互除法演算処理詳細フローチャート
【図７】従来のバイナリユークリッド互除法で入力された法の値が偶数の時の演算処理詳細フローチャート
【図８】本発明の実施の形態１による逆元演算処理の全体フローチャート
【図９】本発明の実施の形態１による入力処理詳細フローチャート
【図１０】本発明の実施の形態１による法分割処理詳細フローチャート
【図１１】本発明の実施の形態１による第１逆元演算処理詳細フローチャート
【図１２】本発明の実施の形態１による第２逆元演算処理詳細フローチャート
【図１３】本発明の実施の形態１による合成演算処理詳細フローチャート
【図１４】本発明の実施の形態１による出力処理詳細フローチャート
【図１５】本発明の実施の形態１による逆元演算装置の全体構成図
【図１６】本発明の実施の形態２によるＲＳＡ鍵対生成処理の全体フローチャート
【図１７】本発明の実施の形態２によるＲＳＡ鍵対生成装置の全体構成図
【図１８】本発明の実施の形態１と従来方法で使用する変数の数を表す比較図
【図１９】本発明の実施の形態３によるメッセージ送受信システムの全体構成図
【符号の説明】
１５０１  入力部
１５０２  法分割部
１５０３  第１逆元演算部
１５０４  第２逆元演算部
１５０５  合成演算部
１５０６  出力部
１７０１  素数取得部
１７０２  法演算部
１７０３  公開鍵取得部
１７０４  逆元演算部
１７０５  繰り返し制御部
１７０６  鍵対出力部
１９０１  メッセージ送信装置
１９０２  メッセージ受信装置
１９０３  ＲＳＡ署名装置
１９０４  ＲＳＡ検証装置
１９０５  ＲＳＡ鍵生成装置
１９０６  メッセージ送信装置
１９０７  メッセージ受信装置
１９０８  ＲＳＡ暗号装置
１９０９  ＲＳＡ復号装置
１９１０  ＲＳＡ鍵生成装置
【図１】
0004019762.tif 000002
【図２】
0004019762.tif 000003
【図３】
0004019762.tif 000004
【図４】
0004019762.tif 000005
【図５】
0004019762.tif 000006
【図６】
0004019762.tif 000007
【図７】
0004019762.tif 000008
【図８】
0004019762.tif 000009
【図９】
0004019762.tif 000010
【図１０】
0004019762.tif 000011
【図１１】
0004019762.tif 000012
【図１２】
0004019762.tif 000013
【図１３】
0004019762.tif 000014
【図１４】
0004019762.tif 000015
【図１５】
0004019762.tif 000016
【図１６】
0004019762.tif 000017
【図１７】
0004019762.tif 000018
【図１８】
0004019762.tif 000019
【図１９】
0004019762.tif 000020