(57)【要約】【課題】モンゴメリ乗算に基づく剰余演算器を用い、剰余演算器が処理可能なビット長を超えるデータの剰余演算を処理することができる剰余演算処理装置を提供する。【解決手段】剰余演算処理装置において、剰余演算の対象となるデータを分解し、それぞれモンゴメリ乗算に適した形式に変換する。さらに、各データを剰余演算器１１５に入力できるサイズになるよう変換した後、繰り返し剰余演算器１１５のモンゴメリ乗算を実行する。得られた剰余から、元のビット長のモンゴメリ乗算の剰余を復元する。【選択図】図４
2007212701.tif 000002
【特許請求の範囲】
【請求項１】
モンゴメリ乗算による剰余演算を行う剰余演算器を有し、前記剰余演算器が処理できないビット長を持つデータの剰余演算を計算する剰余演算処理装置であって、
前記剰余演算器を用いて、モンゴメリ乗算の商と剰余を計算する第１の処理部を備えたことを特徴とする剰余演算処理装置。
【請求項２】
請求項１記載の剰余演算処理装置において、
前記第１の処理部へ計算するデータを与え、前記第１の処理部が計算したモンゴメリ乗算の前記商と前記剰余を用いて、前記剰余演算器が処理できないビット長を持つデータの剰余演算を計算する第２の処理部を備えたことを特徴とする剰余演算処理装置。
【請求項３】
請求項２記載の剰余演算処理装置において、
前記剰余演算処理装置に入力されたデータの形式を前記モンゴメリ乗算に適した形式に変換する第３の処理部を備えたことを特徴とする剰余演算処理装置。
【請求項４】
請求項３記載の剰余演算処理装置において、
前記第２の処理部による剰余演算の剰余を前記モンゴメリ乗算に適した形式から、前記入力されたデータの形式に逆変換する第４の処理部を備えたことを特徴とする剰余演算処理装置。
【請求項５】
請求項１記載の剰余演算処理装置において、
前記第１の処理部が計算するモンゴメリ乗算の前記商と前記剰余とは、データＸとデータＹとデータＮとモンゴメリ乗算に用いるモンゴメリ定数Ｍを用いた
ＸＹ＝ＱＮ＋ＲＭ
の式を満たすデータＱとデータＲがそれぞれモンゴメリ乗算の商と剰余であることを特徴とする剰余演算処理装置。
【請求項６】
請求項５記載の剰余演算処理装置において、
前記第１の処理部が行う処理は、
前記剰余演算器の最大ビット長以下になるように、前記データＸと前記データＹを変更し、前記剰余演算器を用いて、前記データＸと前記データＹの剰余演算の剰余から、前記モンゴメリ乗算の商Ｑと剰余Ｒを計算する処理であることを特徴とする剰余演算処理装置。
【請求項７】
請求項３または４記載の剰余演算処理装置において、
前記第３の処理部が行う処理は、
前記剰余演算処理装置に入力されたデータＡに対し、前記モンゴメリ乗算用のモンゴメリ定数Ｍと整数Ｚを用いた
Ａ＝Ａ1Ｚ＋Ａ0Ｍ
の式を満たすデータＡ1とデータＡ0を計算する処理であることを特徴とする剰余演算処理装置。
【請求項８】
請求項７記載の剰余演算処理装置において、
前記第４の処理部が行う処理は、
前記モンゴメリ乗算に適した形式へ変換された前記データＡ1と前記データＡ0と前記モンゴメリ乗算に用いるモンゴメリ定数Ｍと整数Ｚを用いた
Ａ1'２n＋Ａ0'＝Ａ1Ｚ＋Ａ0Ｍ
の式を満たすデータＡ1'とデータＡ0'を計算する処理であることを特徴とする剰余演算処理装置。
【請求項９】
請求項２記載の剰余演算処理装置において、
前記第２の処理部により、前記剰余演算器が処理できないビット長を持つデータのべき乗の剰余演算を計算するために、前記剰余演算器が処理できないビット長を持つデータのべき乗の剰余演算を繰り返すように指示を与える第５の処理部を備えたことを特徴とする剰余演算処理装置。
【請求項１０】
請求項９記載の剰余演算処理装置において、
前記モンゴメリ乗算の前記商と前記剰余が一定のビット長以内になるように、前記モンゴメリ乗算の前記商と前記剰余を変換する第６の処理部を備えたことを特徴とする剰余演算処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に用いられる剰余演算処理装置に関し、特に、サーバ、スマートカード等に搭載される暗号機器上への、実装技術に関する。
【背景技術】
【０００２】
＜ＲＳＡ暗号の基本＞
１９７８年に考案された世界で最初の公開鍵暗号であるＲＳＡ暗号は、暗号化用の鍵と復号化用の鍵が異なり、暗号化用の鍵（公開鍵）を公開することができるという性質を持つ。ＲＳＡ暗号では、平文Ｌを暗号文Ｃに変換するため、べき乗剰余演算Ｃ＝Ｌe ｍｏｄ Ｋを実行する。ただし、ｅとＫは，暗号化用の公開鍵である。ＲＳＡ暗号では、復号化は、べき指数をｅから復号化用の鍵（秘密鍵）ｄの値に変更するだけである。公開鍵である法Ｋや秘密鍵ｄは、安全性の観点から１，０２４ビット以上が利用されることが多い。
【０００３】
＜高速な剰余演算の必要性＞
ＲＳＡ暗号などの公開鍵暗号では、処理時間が掛かるべき乗の剰余演算が必要となる。そのため、高性能なＣＰＵを搭載できないＩＣカードや管理が集中するサーバ装置では、剰余演算をハードウェアとして実装した剰余演算器を用い、実行時間を短縮することが多い。特に、非特許文献１に記載されるモンゴメリ乗算は、多くのハードウェアに実装される、高速な剰余演算の処理手法であることが知られている。また剰余演算の高速化手法として、モンゴメリ乗算を応用した手法（以降、二分剰余演算と呼ぶ）が、非特許文献４に記載されている。
【０００４】
＜ＲＳＡ暗号の復号化＞
ＲＳＡ暗号を高速に処理するため、演算処理を分割する手法を応用し、剰余演算器のビット数を超える剰余演算を高速に実行する手段が知られている。この手法の多くは、演算処理の分割に秘密鍵の情報が必要となるため、ＲＳＡ暗号の復号化（または署名生成）処理にて利用することができる。
【０００５】
＜ＲＳＡ暗号の暗号化＞
ＲＳＡ暗号の暗号化（または署名検証）処理において、復号化処理と同様、剰余演算器のビット数を超える剰余演算を高速に実行する研究が、非特許文献２と非特許文献３に記載されている。正の整数ｎをビット長とする剰余演算器を用い、最大２倍（２ｎ）をビット長とする剰余演算を実行することが可能となるため、ｎビットの剰余演算器を用い、最大２ｎビットの鍵長を持つＲＳＡ暗号の暗号化処理をすることができる。
【非特許文献１】Ａ．Ｍｅｎｅｚｅｓ，  Ｐ．ｖａｎ  Ｏｏｒｓｃｈｏｔ，  Ｓ．Ｖａｎｓｔｏｎｅ，  Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｐｐ．５９９−ｐｐ．６０３  （１９９７）．
【非特許文献２】Ｗ．  Ｆｉｓｃｈｅｒ，  Ｊ．−Ｐ．  Ｓｅｉｆｅｒｔ：  “Ｉｎｃｒｅａｓｉｎｇ  ｔｈｅ  ｂｉｔｌｅｎｇｔｈ  ｏｆ  ｃｒｙｐｔｏ−ｃｏｐｒｏｃｅｓｓｏｒｓ”  ＣＨＥＳ２００２，  ｖｏｌ．  ２５２３  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．  ７１−−８１  （２００３）．
【非特許文献３】Ｂｅｎｏｉｔ  Ｃｈｅｖａｌｌｉｅｒ−Ｍａｍｅｓ，  Ｍａｒｃ  Ｊｏｙｅ，  ａｎｄ  Ｐａｓｃａｌ  Ｐａｉｌｌｉｅｒ：  “Ｆａｓｔｅｒ  Ｄｏｕｂｌｅ−Ｓｉｚｅ  Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  Ｆｒｏｍ  Ｅｕｃｌｉｄｅａｎ  Ｍｕｌｔｉｐｌｉｅｒｓ”  ＣＨＥＳ２００３，  ｖｏｌ．  ２７７９  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．  ２１４−２２７  （２００３）．
【非特許文献４】Ｍ．  Ｋａｉｈａｒａ，  Ｎ．Ｔａｋａｇｉ：  “Ｂｉｐａｒｔｉｔｅ  Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ”  ＣＨＥＳ２００５，  ｖｏｌ．  ３６５９  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．  ２０１−２１０  （２００５）．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
剰余演算、特にべき乗の剰余演算を計算する場合には、高速に処理できるモンゴメリ乗算を剰余演算器にハードウェア実装し、剰余演算を処理する場合が多い。しかし、非特許文献２、非特許文献３に紹介されている手法には、以下の課題がある。
【０００７】
課題１：モンゴメリ乗算の利用条件を想定していない。
【０００８】
モンゴメリ乗算に基づく剰余演算は、剰余演算の法とモンゴメリ定数が互いに素でなければならない、という条件がある。非特許文献２、非特許文献３に紹介されている手法では、この条件を満たさない場合が生じるため、モンゴメリ乗算を実装した剰余演算器を利用することができない。
【０００９】
課題２：剰余演算器のビット長の２倍の剰余演算が処理できることを保証していない。
【００１０】
非特許文献２、非特許文献３によれば、剰余演算器の２倍のビット数（２ｎビット）の剰余演算を実行するため、ｎビットのデータを加算または減算した結果を、剰余演算器に入力する必要がある。しかし、加算または減算後に得られるデータは、ビット数がｎを越えてしまう場合があるため、剰余演算器はｎ＋α（αは正の整数）ビットの剰余演算を処理しなければならない。これは即ち、非特許文献２、非特許文献３に紹介されている手法が、剰余演算器のビット長の２倍の剰余演算を処理することができないことを示す。
【００１１】
課題３：剰余演算に入力する法の値によっては、剰余演算器が正しく剰余演算を実行することができない。
【００１２】
非特許文献２、非特許文献３によれば、最大２ｎビットの剰余演算を実行するため、剰余演算器に法となるデータの上位（ｎ＋１）ビットから２ｎビットの値を設定することを必要としている。従って、法となるデータのビット数がｎビット以下の場合には、剰余演算器に設定する法の値が存在しない（あるいは、０である）ため、剰余演算器が正しく剰余演算を実行することができない。
【００１３】
課題４：剰余演算器の剰余演算のビット長を２倍化するために必要な情報を、モンゴメリ乗算を用いた剰余演算では取得することが困難である。
【００１４】
非特許文献１に紹介されているモンゴメリ乗算は、時間の掛かる剰余演算を、コンピュータが得意とする乗算で処理しようと試みた手法である。通常の剰余演算では、対象となる２つの数の積から法を減算していき、剰余を積の下位側に保存するのに対し、モンゴメリ乗算では、積に法を加算していき、剰余を積の上位側に保存している。一般の剰余演算では、剰余は２数の積の下位側に保存されているため、法の最下位ビットを反転させた２つの剰余の差分から、容易に商を求めることができる。非特許文献２、非特許文献３では、通常の剰余演算に基づく剰余演算器のビット長の最大２倍の剰余演算を実現するため、剰余演算の剰余だけでなく、商を求めることにより、ビット長を最大２倍化するために必要な情報を収集している。しかし、モンゴメリ乗算では商そのものの定義がされていないため、モンゴメリ乗算を用いた場合には商に関する情報を集めることが困難である。
【００１５】
上記の課題を克服し、本発明の目的は、モンゴメリ乗算に基づく剰余演算器を用い、剰余演算器が処理可能なビット長を超えるデータの剰余演算を処理することができる剰余演算処理装置を提供することにある。
【課題を解決するための手段】
【００１６】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。
【００１７】
本発明による剰余演算処理装置は、モンゴメリ乗算による剰余演算を行う剰余演算器を有し、剰余演算器が処理できないビット長を持つデータの剰余演算を計算する剰余演算処理装置であって、剰余演算器を用いて、モンゴメリ乗算の商と剰余を計算する第１の処理部を備えたものである。
【００１８】
また、本発明による剰余演算処理装置は、第１の処理部へ計算するデータを与え、第１の処理部が計算したモンゴメリ乗算の商と剰余を用いて、剰余演算器が処理できないビット長を持つデータの剰余演算を計算する第２の処理部を備えたものである。
【００１９】
また、本発明による剰余演算処理装置は、剰余演算処理装置に入力されたデータの形式をモンゴメリ乗算に適した形式に変換する第３の処理部を備えたものである。
【００２０】
また、本発明による剰余演算処理装置は、第２の処理部による剰余演算の剰余をモンゴメリ乗算に適した形式から、入力されたデータの形式に逆変換する第４の処理部を備えたものである。
【００２１】
また、本発明による剰余演算処理装置は、第２の処理部により、剰余演算器が処理できないビット長を持つデータのべき乗の剰余演算を計算するために、剰余演算器が処理できないビット長を持つデータのべき乗の剰余演算を繰り返すように指示を与える第５の処理部を備えたものである。
【００２２】
また、本発明による剰余演算処理装置は、モンゴメリ乗算の商と剰余が一定のビット長以内になるように、モンゴメリ乗算の商と剰余を変換する第６の処理部を備えたものである。
【００２３】
具体的には、本発明では、モンゴメリ乗算を用いた剰余演算を行う剰余演算器において、剰余演算器が許容できる剰余演算のビット長を超える剰余演算を実施している。本発明では、対象とするディジタル化されたデータをメッセージと呼ぶ。
【００２４】
本発明では、入力された剰余演算の対象となるメッセージを分解し、モンゴメリ乗算に適した形式に変換する。モンゴメリ乗算に適した形式に変換されたメッセージを、さらに、剰余演算器に入力できるサイズになるように変換した後、剰余演算器に入力する。剰余演算器にて剰余演算を繰り返し実行し、得られた剰余演算の剰余から、モンゴメリ乗算の形式に基づき、モンゴメリ乗算の剰余と商を求める。モンゴメリ乗算の剰余とは、剰余演算器に入力する前のビット長を持つメッセージに対する、モンゴメリ乗算の剰余である。また、モンゴメリ乗算の商とは、モンゴメリ乗算に関する各メッセージで定義した式を満たすパラメータを指す。複数のモンゴメリ乗算の剰余と商から、入力されたメッセージの剰余を求めることができる。求めた剰余は、剰余演算器の持つ剰余演算の形式から、元のメッセージの形式に戻す。
【発明の効果】
【００２５】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【００２６】
本発明によれば、モンゴメリ乗算に基づく剰余演算器を用い、剰余演算器が処理可能なビット長を超えるデータの剰余演算を処理することができる。
【発明を実施するための最良の形態】
【００２７】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００２８】
（実施の形態１）
＜剰余演算処理装置を適用した通信システムの全体構成＞
図１により、本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムの全体構成について説明する。なお、図１に示す通信システムの全体構成は、以下の各実施の形態で基本的に共通である。図１は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムの全体構成を示す構成図である。
【００２９】
図１において、通信システムは、ネットワーク１４２によってコンピュータＡ１０１およびコンピュータＢ１２１が接続されている。
【００３０】
コンピュータＡ１０１は、ＣＰＵ１１４や剰余演算器１１５などの演算装置、ＲＡＭ１０３、ＥＥＰＲＯＭ１０６、ＲＯＭ１０７や外部記憶装置１０８などの記憶装置、コンピュータ外部とのデータ入出力を行なう入出力インタフェース１１１を装備しており、外部にはコンピュータＡ１０１をユーザが操作するためのディスプレイ１０９、キーボード１１０、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００３１】
更に、コンピュータＡ１０１は、ＲＡＭ１０３、ＲＯＭ１０７、ＥＥＰＲＯＭ１０６や外部記憶装置１０８などの記憶装置によって、記憶部１０２を実現し、ＣＰＵ１１４や剰余演算器１１５などの演算装置が、記憶部１０２に格納されたプログラムを実行することにより、処理部１１２を実現する。
【００３２】
例えば、記憶部１０２を構成するＥＥＰＲＯＭ１０６ないしはＲＯＭ１０７に、プログラムやスマートカードごとに異なる情報を格納し、ＲＡＭ１０３には処理部１１２の行う計算の中間データを格納する。
【００３３】
剰余演算器１１５は剰余演算を実行する計算装置または計算プログラムであり、乗算の対象となる２つのメッセージ、法となるメッセージ、さらに剰余演算用の定数を入力として受け付け、剰余演算の剰余を出力するインタフェースを持つ。また、剰余演算器１１５は、最大ｎ＋ｈ（ｎは正の整数、ｈは０以上ｎ未満の整数）ビットのメッセージを対象に、剰余演算を実行することができる。
【００３４】
コンピュータＢ１２１は、コンピュータＡ１０１と同様に、演算装置、記憶装置、入出力インタフェース１３１を備えており、ＣＰＵ１３４がプログラムを実行することにより、処理部１３２を実現する。
【００３５】
なお、図１に示す構成において、コンピュータＡ１０１内、コンピュータＢ１２１内の各プログラムは、予め、コンピュータＡ１０１内、コンピュータＢ１２１内の記憶部１０２、１２２に格納されていても良いし、必要なときに、入出力インタフェース１１１、１３１を介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部１０２、１２２に導入されてもよい。媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波やディジタル信号）を指す。
【００３６】
また、コンピュータＢ１２１内の処理部の動作は、コンピュータＡ１０１と同様であり、以下の説明においては、コンピュータＡ１０１内の処理部の動作として説明する。
【００３７】
＜コンピュータ内の処理部が行う剰余演算処理＞
次に、図２により、本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の処理部が行う剰余演算処理について説明する。図２は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の処理部が行う情報の受け渡しの様子を示したシーケンス図である。
【００３８】
図２において、剰余演算の処理対象は、メッセージとして取り扱われている。メッセージは、ディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
【００３９】
なお、図２に示すシーケンス図は、以下の各実施の形態で基本的に共通である。
【００４０】
データ処理部１１３は、入出力インタフェース１１１を介して、メッセージが入力されると（Ｓ２０１）、入力されたメッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるようにメッセージを区切る。以下、所定のビット長として２ｎビットに区切られている部分メッセージ（これ以降、単に部分メッセージをメッセージと呼ぶ）について説明する。ただし、各実施の形態において、ｎは正の整数である。
【００４１】
データ処理部１１３は、メッセージおよび、べき乗数をモンゴメリ乗算利用部１１６に出力する（Ｓ２０２）。
【００４２】
モンゴメリ乗算利用部１１６では、まず、入力されたメッセージを剰余演算器の持つ剰余演算に適した形式に変換する。次に、変換したメッセージから、剰余演算器１１５が入力として受け取れるサイズ分のメッセージを剰余演算器１１５へ出力する（Ｓ２０３）。図２のシーケンス図では、ｎビットのサイズ分のメッセージだけを剰余演算器１１５に出力している。
【００４３】
剰余演算器では、入力されたメッセージの剰余を求め、剰余をモンゴメリ乗算利用部１１６に出力する（Ｓ２０４）。
【００４４】
モンゴメリ乗算利用部１１６と剰余演算器１１５では、Ｓ２０３からＳ２０４の処理を複数回繰り返す。モンゴメリ乗算利用部１１６は、出力された剰余を元に、２ｎビットからなる剰余を計算する。モンゴメリ乗算利用部１１６では、剰余演算器の持つ剰余演算に適した形式から元の整数表現にメッセージを変換し、データ処理部１１３へ出力する（Ｓ２０５）。
【００４５】
データ処理部１１３では、入力されたメッセージを元に、出力メッセージを求め、入出力インタフェース１１１へ出力、またはＲＡＭ１０３、ＲＯＭ１０７、ＥＥＰＲＯＭ１０６などへ格納する（Ｓ２０６）。
【００４６】
なお、各モジュール間のデータの受け渡しには、データを直接転送する以外にも、記憶部１０２にデータを書き込み、転送先モジュールが記憶部１０２にアクセスし、データを読み出してもよい。
【００４７】
以下、コンピュータＡ１０１のモンゴメリ乗算利用部１１６の処理について、詳細に説明する。
【００４８】
＜モンゴメリ乗算利用部の処理の概要＞
まず、本実施の形態では、モンゴメリ乗算利用部１１６が、２ｎビットからなるメッセージを対象に、モンゴメリ乗算に基づく剰余演算を計算する第１の計算方法について説明する。
【００４９】
＜モンゴメリ乗算利用部の機能ブロック＞
図３により、本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内のモンゴメリ乗算利用部の構成について説明する。図３は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内のモンゴメリ乗算利用部１１６の構成を示す機能ブロック図である。
【００５０】
モンゴメリ乗算利用部１１６では、剰余演算器１１５とｎビットのメッセージを交換し、２ｎビットのメッセージのモンゴメリ乗算に基づく剰余演算の剰余を求める機能を持つ。
【００５１】
図３において、モンゴメリ乗算利用部１１６は、表現処理部３０１、入出力処理部３０２、剰余処理部３０３からなる。
【００５２】
表現処理部３０１は、表現変換部３１１、逆変換部３１２、補正部３１３、出力部３１４、加算部３１５、減算部３１６、合成部３１７からなる。
【００５３】
入出力処理部３０２は、入力設定部３２１、合成部３２２、補正部３２３、出力部３２４、加算部３２５、減算部３２６、繰返判定部３２７、条件判定部３２８からなる。
【００５４】
剰余処理部３０３は、剰余演算器取扱部３３１、商演算部３３２、剰余演算部３３３、出力部３３４、加算部３３５、減算部３３６、条件判定部３３７、ｍｏｄ算部３３８、乗算部３３９からなる。
【００５５】
次に、各機能部の基本的な働きとインタフェースを説明する。
【００５６】
表現変換部３１１、逆変換部３１２、補正部３１３のインタフェース、働きについては、それぞれ実施例毎に説明する。実施例１では、図５、図６、図１４のフローチャートを用いて説明する。
【００５７】
出力部３１４は、入力されたメッセージを、データ処理部１１３または入出力処理部３０２へ出力する。
【００５８】
加算部３１５は、二つのメッセージを入力として受け付け、二つのメッセージの値を加算した値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００５９】
減算部３１６は、二つのメッセージを入力として受け付け、一番目のメッセージの値から二番目のメッセージを減算した値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００６０】
合成部３１７は、二つのメッセージを入力として受け付け、ある式に基づいてメッセージを合成し、メッセージの出力元の機能部へ合成したメッセージを出力する。
【００６１】
入力設定部３２１のインタフェース、働きについては、実施例毎に説明する。実施例１では、図８、図９、図１２、図１３のフローチャートを用いて説明する。
【００６２】
合成部３２２は、入力されたメッセージをある式に基づいて合成し、出力部３２４へ合成したメッセージを出力する。
【００６３】
補正部３２３のインタフェース、働きについては、図１４のフローチャートを用いて後述する。
【００６４】
出力部３２４は、入力されたメッセージを、表現処理部３０１または剰余処理部３０３へ出力する。
【００６５】
加算部３２５は、二つのメッセージを入力として受け付け、二つのメッセージの値を加算した値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００６６】
減算部３２６は、二つのメッセージを入力として受け付け、一番目のメッセージの値から二番目のメッセージを減算した値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００６７】
繰返判定部３２７と条件判定部３２８のインタフェース、働きについては、実施例毎に説明する。実施例１では、図７のフローチャート図を用いて説明する。
【００６８】
剰余演算器取扱部３３１、商演算部３３２、剰余演算部３３３のインタフェース、働きについては、実施例毎に説明する。実施例１では、図１０と図１１のフローチャートを用いて説明する。
【００６９】
出力部３３４は、入力されたメッセージを、入出力処理部３０２へ出力する。
【００７０】
加算部３３５は、二つのメッセージを入力として受け付け、二つのメッセージの値を加算した値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００７１】
減算部３３６は、二つのメッセージを入力として受け付け、一番目のメッセージの値から二番目のメッセージを減算した値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００７２】
条件判定部３３７はのインタフェース、働きについては、実施例毎に説明する。実施例１では、図１１のフローチャートを用いて、説明する。
【００７３】
ｍｏｄ算部３３８は、二つのメッセージを入力として受け付け、一番目のメッセージの値を二番目のメッセージの値で割った時の剰余の値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００７４】
乗算部３３９は、二つのメッセージを入力として受け付け、二つのメッセージの値の積の値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【００７５】
なお、剰余処理部３０３の、剰余演算器取扱部３３１、商演算部３３２、剰余演算部３３３、加算部３３５、減算部３３６、条件判定部３３７、ｍｏｄ算部３３８、乗算部３３９で、第１の処理部を構成している。
【００７６】
また、入出力処理部３０２の、入力設定部３２１、合成部３２２、加算部３２５、減算部３２６で、第２の処理部を構成し、入出力処理部３０２の、繰返判定部３２７、条件判定部３２８で、第５の処理部を構成し、入出力処理部３０２の、補正部３２３、加算部３２５、減算部３２６で、第６の処理部を構成している。
【００７７】
また、表現処理部３０１の、表現変換部３１１、加算部３１５、減算部３１６で、第３の処理部を構成し、表現処理部３０１の、逆変換部３１２、加算部３１５、減算部３１６、合成部３１７で、第４の処理部を構成している。
【００７８】
＜モンゴメリ乗算利用部と剰余演算器の処理＞
次に、図４により、本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内のモンゴメリ乗算利用部と剰余演算器の処理について説明する。図４は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内のモンゴメリ乗算利用部と剰余演算器の処理を示すシーケンス図であり、モンゴメリ乗算利用部１１６の機能ブロックである表現処理部３０１、入出力処理部３０２、剰余処理部３０３と、剰余演算器１１５のメッセージの受け渡しの様子を示している。
【００７９】
まず、表現処理部３０１へメッセージおよび、べき乗数が入力される（Ｓ４０１）。
【００８０】
表現処理部３０１は、入力したメッセージを元に、モンゴメリ乗算用に変換したメッセージ（以降、モンゴメリ乗算用のメッセージと呼ぶ）を作成し、モンゴメリ乗算用のメッセージを作成する際に用いた定数とべき乗数と共に、入出力処理部３０２へ出力する（Ｓ４０２）。
【００８１】
入出力処理部３０２は、入力したモンゴメリ乗算用のメッセージと定数から、適当なメッセージを選択し、出力する（Ｓ４０３）。
【００８２】
剰余処理部３０３は、入力したモンゴメリ乗算用のメッセージまたは定数が、剰余演算器１１５が入力として受け取れるサイズになるよう、値を変更し、剰余演算器１１５へ出力する（Ｓ４０４）。
【００８３】
剰余演算器１１５は、入力したメッセージを用い、モンゴメリ乗算に基づく剰余演算を実行し、計算結果を剰余１として出力する。剰余処理部３０３は、剰余演算器１１５から出力された剰余１を入力する（Ｓ４０５）。剰余演算器１１５の剰余演算の法の設定値の変更要求、または新たな法であるメッセージを出力する（Ｓ４０６）。剰余演算器１１５は、剰余演算の法の値を更新した後に、モンゴメリ乗算に基づく剰余演算を実行し、計算結果を剰余２として出力する。剰余処理部３０３は、剰余演算器１１５から出力された剰余２を入力する（Ｓ４０７）。剰余処理部３０３は、剰余１と剰余２を用い、後述する（式２）によって定義されたモンゴメリ乗算の商と剰余を計算し、入出力処理部３０２へ出力する。（Ｓ４０８）
入出力処理部３０２、剰余処理部３０３、剰余演算器１１５は、ステップＳ４０３からステップＳ４０８の連続した処理を複数回繰り返す。入出力処理部３０２は、入力された複数個のモンゴメリ乗算用の商と剰余を合成し、べき乗数を用いてステップＳ４０３へ戻るか、ステップＳ４５１へ進むかを判定する。
【００８４】
入出力処理部３０２は表現処理部３０１へモンゴメリ乗算用の商と剰余を合成したメッセージを出力する（Ｓ４５１）。表現処理部３０１は、入力されたモンゴメリ乗算用の商と剰余を合成したメッセージを、ステップＳ４０１で入力したメッセージと同じ形式に変換し、データ処理部１１３へ出力する（Ｓ４５２）。
【００８５】
＜表現処理部の処理＞
次に、図５および図６により、本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理について説明する。図５および図６は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【００８６】
表現処理部３０１は、メッセージをモンゴメリ乗算に適した形式であるモンゴメリ乗算用のメッセージに変換、またはモンゴメリ乗算用のメッセージから逆変換し、出力する機能を持つ。
【００８７】
モンゴメリ乗算に適した形式とは、詳細な説明は後述するモンゴメリ乗算の商と剰余を求めるための次の（式２）の剰余とモンゴメリ定数の積の部分に着目し、メッセージが同様の部分を持つように、変換した形式を指す。
【００８８】
ＸＹ＝ＱＮ＋ＲＭ        …（式２）
例えば、２ｎビットのメッセージＮから変換されたモンゴメリ乗算用のメッセージＮ1とメッセージＮ0は、次の（式３）を満たす。
【００８９】
Ｎ=Ｎ1Ｚ＋Ｎ0Ｍ        …（式３）
ここで、Ｍはモンゴメリ定数、Ｚは２n−ｋ（ｋは正の奇数）である。モンゴメリ乗算用のメッセージＮ0とモンゴメリ定数Ｍの積の部分が、（式２）の剰余とモンゴメリ定数の積の部分に相当する。モンゴメリ乗算の法は、モンゴメリ定数Ｍと互いに素でなければならない、という条件がある。後に剰余演算器１１５にモンゴメリ乗算の法として設定するＮ1は、Ｚを奇数に設定することにより、モンゴメリ定数Ｍと互いに素になる。また、（式３）は、（式２）と類似した形式であるが、（式３）はより計算が容易になるよう、Ｚを設定できるという側面を持つ。例えば、モンゴメリ定数Ｍの値が２nとなる際には、Ｚ＝２n−１と設定することにより、メッセージＮからメッセージＮ1とメッセージＮ0を求める式、かつ逆にメッセージＮを求める式を容易に導出することができる。以降では、ｋ＝１（即ち、Ｚ＝２n−１）の場合を説明するが、ｋが他の値を取るときも同様の手法で実施することができる。
【００９０】
図５のフローチャートは、表現処理部３０１が２ｎビットのメッセージを、モンゴメリ乗算用のメッセージに変換するまでの処理手続きを示す。
【００９１】
まず、表現処理部３０１がもつ表現変換部３１１に２ｎビットのメッセージＡ、２ｎビットのメッセージＢ、２ｎビットのメッセージＮとべき乗数Ｅが入力される（Ｓ５０１）。
【００９２】
表現変換部３１１は、各メッセージを上位ｎビットと下位ｎビットに分け、メッセージＡからメッセージＡ'１とメッセージＡ'0、メッセージＢからメッセージＢ'1とメッセージＢ'0、メッセージＮからメッセージＮ'1とメッセージＮ'0を作成し、ステップＳ５０３へと進む（Ｓ５０２）。ただし、ステップＳ５０２にて、２ｎビットに満たないメッセージが入力された場合、表現変換部３１１は、メッセージの最上位ビットから０をパディングしていき、メッセージを２ｎビットからなるメッセージとみなす。
【００９３】
表現変換部３１１は、（式３）を満たすように、メッセージＮ1、メッセージＮ0、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0を作成する。例えば、以下の式を満たすようにメッセージＮ1、メッセージＮ0、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0を作成すると、（式３）を満たすことができる。
【００９４】
Ｎ1＝ａ２n−Ｎ'0
Ａ1＝ｂ２n−Ａ'0
Ｂ1＝ｃ２n−Ｂ'0
Ｎ0＝Ｎ'1−Ｎ1＋ａ
Ａ0＝Ａ'1−Ａ1＋ｂ
Ｂ0＝Ｂ'1−Ｂ1＋ｃ
ただし、ａ、ｂ、ｃは正の整数である。例えば、ａ＝１、ｂ＝１、ｃ＝１と設定する。
【００９５】
例えば、表現変換部３１１は、次のように計算する。表現変換部３１１は、加算部３１５、減算部３１６に対しメッセージを交換することにより、（ａ２ｎ−Ｎ'0）の値をメッセージＮ1に格納する。これは、加算部３１５に対し定数２ｎをやりとりし、減算部３１６に対し加算部が出力した値を持つメッセージとメッセージＮ'0を出力することにより、ａ２n−Ｎ'0の値を持つメッセージＮ1を取得することができる。表現変換部３１１は、加算部３１５、減算部３１６に対しメッセージを交換することにより、（Ｎ'1−Ｎ1＋ａ）の値をメッセージＮ0に格納する。例えば、減算部３１６に、定数２nをａ倍した値をもつメッセージとメッセージＮ'0を出力し、減算部３１６が出力した値（ａ２n−Ｎ'0）の値をメッセージＮ1に格納する。表現変換部３１１は、減算部３１６に、メッセージＮ'1とメッセージＮ1を出力し、減算部３１６が出力した値（Ｎ'1−Ｎ1）を持つメッセージと定数ａを加算部３１５に出力し、加算部３１５が出力した（Ｎ'1−Ｎ1＋ａ）の値をメッセージＮ0に格納する。メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0もメッセージＮ1とメッセージＮ0と同様に作成する（Ｓ５０３）。
【００９６】
表現出力部３１１は、出力部３１４にメッセージＮ1とメッセージＮ0、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0、定数Ｚを出力する。出力部３１４は、入力されたメッセージＮ1、メッセージＮ0、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0、定数であるメッセージＺを出力する（Ｓ５１０）。
【００９７】
次に、逆変換部３１２が、モンゴメリ乗算用のメッセージを逆変換し、出力するまでの手続きを図６のフローチャートを用いて示す。
【００９８】
まず、逆変換部３１２に、メッセージＱ、メッセージＲが入力される（Ｓ５５１）。
【００９９】
逆変換部３１２は、定数２nとメッセージＱを減算部３１６に出力する。減算部３１６では、定数２nからメッセージＱの値を減算した値を出力する。逆変換部３１２は、出力された値（２n−Ｑ）を入力として受け取り、メッセージＡ0に格納する。従って、メッセージＡ0、定数２n、メッセージＱは以下の関係式を満たす。
【０１００】
Ａ0＝２n−Ｑ
逆変換部３１２は、加算部３１５、減算部３１６とメッセージを交換し、（Ｑ＋Ｒ−１）の値をメッセージＡ1に格納する。例えば、逆変換部３１２は、メッセージＱとメッセージＲを加算部３１５に出力する。加算部３１５では、メッセージＱの値にメッセージＲの値を加算した値を出力する。逆変換部３１２は、入力として受け取った値を、メッセージ（Ｑ＋Ｒ）として、定数１と共に減算部３１６へ出力する。減算部３１６では、メッセージ（Ｑ＋Ｒ）の値から１を減算した値を出力する。逆変換部３１２は、出力された値（Ｑ＋Ｒ−１）を入力として受け取り、メッセージＡ1に格納する。従って、メッセージＡ1、メッセージＱ、メッセージＲ、定数１は以下の関係式を満たす（Ｓ５５２）。
【０１０１】
Ａ1＝Ｑ＋Ｒ−１
逆変換部３１２は、合成部３１７にメッセージＡ1とメッセージＡ0を出力する。合成部３１７は、メッセージＡ1とメッセージＡ0を用い、（Ａ1２n＋Ａ0）の値を作成し、出力する。逆変換部３１２は、出力された（Ａ1２n＋Ａ0）の値をメッセージＣに格納する。（Ｓ５５３）。
【０１０２】
逆変換部３１２は、出力部３１４にメッセージＣを出力する。出力部３１４は、入力されたメッセージＣを出力する（Ｓ５５４）。
【０１０３】
＜入出力処理部の処理＞
次に、図７〜図９により、本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の処理について説明する。図７〜図９は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う処理を示すフローチャートである。
【０１０４】
入出力処理部３０２は、２ｎビットのモンゴメリ乗算に基づく剰余演算を実行するため、剰余処理部３０３へモンゴメリ乗算用のメッセージを出力する機能を持つ。また、剰余処理部３０３から出力されたメッセージを入力として受け取り、２ｎビットのモンゴメリ乗算に基づく剰余演算の剰余を計算し、出力する機能を有する。
【０１０５】
図７は、モンゴメリ乗算に基づくべき乗の剰余演算を計算する場合の入出力処理部３０２の処理手続きを示したフローチャートである。図７にある、ステップＳ５７４の処理手続きの詳細は図８に示し、ステップＳ５７７の処理手続きの詳細は図９に示す。
【０１０６】
まず、入出力処理部３０２内の繰返判定部３２７にメッセージＮ1、メッセージＮ0、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0、べき乗定数Ｅ、メッセージＺが入力される（Ｓ５７１）。
【０１０７】
繰返判定部３２７は、メッセージＡ1、メッセージＡ0をそれぞれメッセージＢ1、メッセージＢ0に格納する（Ｓ５７２）。
【０１０８】
繰返判定部３２７は、べき乗数Ｅの値から、べき乗の剰余演算が必要かを判定する。必要ならばステップＳ５７４へ進み、不必要ならばステップＳ５７９へ進む。判定方法の例としては、０の値を持つ変数ｉを用意し、繰返判定部がステップＳ５７３に来る毎に、判断する変数iを変更し、変数iの値がべき乗数Ｅの値と等しくなかったら必要と判断してステップＳ５７４へ進み、変数iの値がべき乗数Ｅの値と等しかったら必要と判断してステップＳ５７９へ進む方法がある（Ｓ５７３）。
【０１０９】
繰返判定部３２７は、入出力設定部３２１に、メッセージＡ1、メッセージＡ0、メッセージＮ1、メッセージＮ0、メッセージＺを出力する（Ｓ５７４）。
【０１１０】
入力設定部３２１はステップＳ６０１からステップＳ６０９の処理（後述）を行い、メッセージＱtotal、メッセージＲtotalを出力する。繰返判定部３２７は、出力されたメッセージＱtotal、メッセージＲtotalをそれぞれメッセージＡ1、メッセージＡ0に格納する（Ｓ５７５）。
【０１１１】
条件判定部３２８は、べき乗数Ｅの値から、ステップＳ５７７におけるＡ×Ｂの剰余演算が必要かを判定する。必要ならばステップＳ５７７へ進み、不必要ならばステップＳ５７３へ進む。判定方法の例としては、べき乗数Ｅのビット数を値として持つ変数ｊを用意し、繰返判定部３２７がステップＳ５７６に来る毎に、判断する変数ｊを２分して行き、べき乗数Ｅを２進数に展開したとき、べき乗数Ｅの（ｊ−１）番目の値が１と等しかったら必要と判断してステップＳ５７７へ進み、０と等しかったら不必要と判断してステップＳ５７３へ進む、という方法がある（Ｓ５７６）。
【０１１２】
繰返判定部３２７は、入出力設定部３２１に、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0、メッセージＮ1、メッセージＮ0、メッセージＺを出力する（Ｓ５７７）。
【０１１３】
入力設定部３２１はステップＳ６５１からステップＳ６６０の処理（後述）を行い、メッセージＱtotal、メッセージＲtotalを出力する。繰返判定部３２７は、出力されたメッセメッセージＲtotalを、それぞれメッセージＡ1、メッセージＡ0に格納する（Ｓ５７８）。
【０１１４】
繰返判定部３２７は、メッセージＡ１とメッセージＡ0を出力部３２４に出力する。出力部３２４は、受け取ったメッセージＡ1、メッセージＡ0を出力する（Ｓ５７９）。
【０１１５】
図８は、メッセージＮを法とするメッセージＡの二乗のモンゴメリ乗算を計算する場合の、入出力処理部３０２の処理を示したフローチャートである。図８を用い、入出力処理部３０２が剰余処理部３０３にメッセージを出力し、剰余処理部３０３にて出力されたモンゴメリ乗算の商と剰余を用いて、２ｎビットのモンゴメリ乗算の剰余を計算する処理手順を説明する。
【０１１６】
入力設定部３２１は、剰余処理部３０３とのメッセージの入出力（（Ｓ６０２）から（Ｓ６０７）まで）を繰り返す。剰余処理部３０３は、３つのメッセージを入力として受け取り、２つのメッセージを出力する。なお、図８では剰余処理部３０３へのメッセージの入出力を、関数ＧＥＴＱＲを用いて表す。
【０１１７】
まず、入力設定部３２１にメッセージＡ1、メッセージＮ1、メッセージＡ0、メッセージＮ0、メッセージＺが入力される（Ｓ６０１）。
【０１１８】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージＺ、メッセージＮ1を出力し、剰余処理部３０３が出力したモンゴメリ乗算の商と剰余をメッセージＱ1、メッセージＲ1に格納する（Ｓ６０２）。
【０１１９】
ステップＳ６０３からステップＳ６０７の処理手続きは、ステップＳ６０２に従う。
【０１２０】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＱ1、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ2、メッセージＲ2に格納する（Ｓ６０３）。
【０１２１】
入力設定部３２１は、加算部、減算部に対してメッセージを交換し、（２Ａ0＋Ｒ1−Ｑ2）の値を持つメッセージ（２Ａ0＋Ｒ1−Ｑ2）を得る。
【０１２２】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージ（２Ａ0＋Ｒ1−Ｑ2）、メッセージＮ1を出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ3、メッセージＲ3に格納する（Ｓ６０４）。
【０１２３】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＱ3、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ4、メッセージＲ4に格納する（Ｓ６０５）。
【０１２４】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージＲ2、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ5、メッセージＲ5に格納する（Ｓ６０６）。
【０１２５】
入力設定部３２１は、剰余処理部３０３にメッセージＡ0、メッセージＡ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の形式に基づく商と剰余をメッセージＱ6、メッセージＲ6に格納する（Ｓ６０７）。
【０１２６】
入力設定部３２１は、合成部３２２に、メッセージＲ3、メッセージＲ4、メッセージＲ5、メッセージＲ6、メッセージＱ4、メッセージＱ5、メッセージＱ6を出力する。合成部３２２は、以下の式を満たすＱtotalとＲtotalを計算する（Ｓ６０８）。
【０１２７】
Ｑtotal＝Ｒ3−Ｑ4−Ｑ5＋Ｑ6
Ｒtotal＝Ｒ6−Ｒ5−Ｒ4
例えば、合成部３２２は次のように計算する。合成部３２２は、メッセージＲ3とメッセージＱ4を減算部３２６へ出力する。減算部３２６は、メッセージＲ3からメッセージＱ4の値を減算し、その値をメッセージとして出力する。減算部３２６は、出力されたメッセージ（Ｒ3−Ｑ4）を入力として受け取り、メッセージＱ5と共に、減算部３２６へ出力する。減算部３２６は、メッセージ（Ｒ3−Ｑ4）からメッセージＱ5の値を減算し、その値をメッセージとして出力する。減算部３２６は、出力されたメッセージ（Ｒ3−Ｑ4−Ｑ5）を入力として受け取り、メッセージＱ6と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ3−Ｑ4−Ｑ5＋Ｑ6）からメッセージＱ6の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ3−Ｑ4−Ｑ5＋Ｑ6）を入力として受け取り、メッセージＱtotalに格納する。従って、メッセージＱtotal、メッセージＲ3、メッセージＱ4、メッセージＱ5、メッセージＱ6は以下の関係式を満たす。
【０１２８】
Ｑtotal＝Ｒ3−Ｑ4−Ｑ5＋Ｑ6
合成部３２２は、メッセージＲ6とメッセージＲ5を減算部３２６へ出力する。減算部３２６は、メッセージＲ6からメッセージＲ5の値を減算し、出力する。減算部３２６は、出力されたメッセージ（Ｒ6−Ｒ5）を入力として受け取り、メッセージＲ6と共に、減算部３２６へ出力する。減算部３２６は、メッセージ（Ｒ6−Ｒ5）からメッセージＲ4の値を減算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ6−Ｒ5−Ｒ4）を入力として受け取り、メッセージＲtotalに格納する。従って、メッセージＲtotal、メッセージＲ4、メッセージＲ5、メッセージＲ6は以下の関係式を満たす。
【０１２９】
Ｒtotal＝Ｒ6−Ｒ5−Ｒ4
合成部３２２は、出力部３２４にメッセージＱtotalとメッセージＲｔotalを出力する。出力部３２４は、入力されたメッセージＱtotalとメッセージＲｔotalを出力する（Ｓ６０９）。
【０１３０】
図９は、メッセージＮを法とするメッセージＡとメッセージＢのモンゴメリ乗算を計算する場合の、入出力処理部３０２の処理を示したフローチャートである。図９を用い、入出力処理部３０２が剰余処理部３０３にメッセージを出力し、剰余処理部３０３にて出力されたモンゴメリ乗算の商と剰余を用いて、２ｎビットのモンゴメリ乗算の剰余を計算する処理手順を説明する。
【０１３１】
入力設定部３２１は、剰余処理部３０３とメッセージの入出力（（Ｓ６５２）から（Ｓ６５８）まで）を繰り返す。
【０１３２】
まず、入力設定部３２１にメッセージＡ1、メッセージＢ1、メッセージＮ1、メッセージＡ0、メッセージＢ0、メッセージＮ0、メッセージＺが入力される（Ｓ６５１）。
【０１３３】
入力設定部３２１は、剰余処理部３０３にメッセージＢ1、メッセージＺ、メッセージＮ1を出力する。剰余処理部３０３が入力されたメッセージＢ1、メッセージＺ、メッセージＮ1をもとに、計算し、出力したモンゴメリ乗算の商と剰余を、入力設定部３２１はメッセージＱ1、メッセージＲ1に格納する（Ｓ６５２）。
【０１３４】
ステップＳ６５３からステップＳ６５８も、ステップＳ６５２と同様の処理を繰り返す。
【０１３５】
入力設定部３２１は、剰余処理部３０３にメッセージＱ1、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ2、メッセージＲ2に格納する（Ｓ６５３）。
【０１３６】
入力設定部３２１は、加算部、減算部に対してメッセージを交換し、（Ｂ0＋Ｒ1−Ｑ2）の値を持つメッセージ（Ｂ0＋Ｒ1−Ｑ2）を得る。
【０１３７】
入力設定部３２１は、剰余処理部３０３にメッセージＡ1、メッセージ（Ｂ0＋Ｒ1−Ｑ2）、メッセージＮ1を出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ3、メッセージＲ3に格納する（Ｓ６５４）。
【０１３８】
入力設定部３２１は、剰余処理部３０３にメッセージＡ0、メッセージＢ1、メッセージＮ1を出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ4、メッセージＲ4に格納する（Ｓ６５５）。
【０１３９】
入力設定部３２１は、加算部に対してメッセージを交換し、（Ｑ3＋Ｑ4）の値を持つメッセージ（Ｑ3＋Ｑ4）を得る。
【０１４０】
入力設定部３２１は、剰余処理部３０３にメッセージ（Ｑ3＋Ｑ4）、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ5、メッセージＲ5に格納する（Ｓ６５６）。
【０１４１】
入力設定部３２１は、剰余処理部３０３にメッセージＡ1、メッセージＲ2、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ6、メッセージＲ6に格納する（Ｓ６５７）。
【０１４２】
入力設定部３２１は、剰余処理部３０３にメッセージＡ0、メッセージＢ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ7、メッセージＲ7に格納する（Ｓ６５８）。
【０１４３】
入力設定部３２１は、合成部３２２に、メッセージＲ3、メッセージＲ4、メッセージＲ5、メッセージＲ6、メッセージＱ4、メッセージＱ5、メッセージＱ6を出力する。合成部３２２は、以下の式を満たすメッセージＱtotalとメッセージＲtotalを計算する（Ｓ６５９）。
【０１４４】
Ｑtotal＝Ｒ3＋Ｒ4−Ｑ5−Ｑ6＋Ｑ7
Ｒtotal＝Ｒ7−Ｒ6−Ｒ5
例えば、合成部３２２は、次の様にメッセージＱtotalとメッセージＲtotalを計算することができる。合成部３２２は、メッセージＲ3とメッセージＲ4を加算部３２５へ出力する。加算部３２５では、メッセージＲ3からメッセージＲ4の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ3＋Ｒ4）を入力として受け取り、メッセージＱ5とともに減算部３２６へ出力する。減算部３２６は、メッセージ（Ｒ3＋Ｒ4）からメッセージＱ5の値を減算し、その値をメッセージとして出力する。減算部３２６は、出力されたメッセージ（Ｒ3＋Ｒ4−Ｑ5）を入力として受け取り、メッセージＱ6と共に、減算部３２６へ出力する。減算部３２６は、メッセージ（Ｒ3＋Ｒ4−Ｑ5）からメッセージＱ6の値を減算し、その値をメッセージとして出力する。減算部３２６は、出力されたメッセージ（Ｒ3＋Ｒ4−Ｑ5−Ｑ6）を入力として受け取り、メッセージＱ7と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ3＋Ｒ4−Ｑ5−Ｑ6）からメッセージＱ7の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ3＋Ｒ4−Ｑ5−Ｑ6＋Ｑ7）を入力として受け取り、メッセージＱtotalに格納する。従って、メッセージＱtotal、メッセージＲ3、メッセージＲ4、メッセージＱ5、メッセージＱ6、メッセージＱ7は以下の関係式を満たす。
【０１４５】
Ｑtotal＝Ｒ3＋Ｒ4−Ｑ5−Ｑ6＋Ｑ7
合成部３２２は、メッセージＲ7とメッセージＲ6を減算部３２６へ出力する。減算部３２６は、メッセージＲ7からメッセージＲ6の値を減算し、その値をメッセージとして出力する。減算部３２６は、出力されたメッセージ（Ｒ7−Ｒ6）を入力として受け取り、メッセージＲ5と共に、減算部３２６へ出力する。減算部３２６は、メッセージ（Ｒ7−Ｒ6）からメッセージＲ5の値を減算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ7−Ｒ6−Ｒ5）を入力として受け取り、メッセージＲtotalに格納する。従って、メッセージＲtotal、メッセージＲ5、メッセージＲ6、メッセージＲ7は以下の関係式を満たす（Ｓ６５９）。
【０１４６】
Ｒtotal＝Ｒ7−Ｒ6−Ｒ5
合成部３２２は、出力部３２４にメッセージＱtotalとメッセージＲｔotalを出力する。出力部３２４は、受け取ったメッセージＱtotalとメッセージＲtotalを出力する（Ｓ６６０）。
【０１４７】
＜剰余処理部の処理＞
次に、図１０および図１１により、本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理について説明する。図１０および図１１は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理を示すフローチャートである。
【０１４８】
まず、モンゴメリ乗算を用いて計算される剰余Ｒ0は、次の式を満たす。
【０１４９】
Ｒ0＝ＸＹＭ(-1)ｍｏｄ Ｎ        …（式１）
ただし、ＸとＹは任意のメッセージであり、Ｍはモンゴメリ定数、Ｎは法となる任意のメッセージを指す。一般に、モンゴメリ定数Ｍは計算を容易にするため、Ｍ＝２nと値を設定されることが多い。
【０１５０】
剰余処理部３０３は、入力されたメッセージと剰余演算器１１５から入力された剰余を用い、モンゴメリ乗算の商と剰余を求める機能を持つ。ここで、モンゴメリ乗算の商と剰余とは、次の式を満たすＱとＲを指す。
【０１５１】
ＸＹ＝ＱＮ＋ＲＭ        …（式２）
（式２）は、（式１）を変形し、求めることができる。（式２）では、（式１）の左辺のモンゴメリ定数Ｍが剰余Ｒの乗数となり、法Ｎに対する被乗数を商Ｑとしている。剰余を求める方法として利用されてきたモンゴメリ乗算に対し、商を用いて定義した式が（式２）である。
【０１５２】
図１０は、剰余処理部３０３のモンゴメリ乗算の商と剰余を求める処理手続きを示したフローチャートである。ただし、剰余演算器１１５が処理できるメッセージの最大のビット数は、入力されるメッセージのビット数以上である。図１０では、剰余演算器１１５へのメッセージの入出力を、３つのメッセージを入力として受け取り、１つのメッセージを出力する関数ＭＯＮＴＧを用いて表す。なお、剰余演算器１１５に入力できるメッセージの最大ビット長が入力されるメッセージのビット数以下の場合は、図１１のフローチャートを用いて説明する。
【０１５３】
まず、図１０は剰余処理部３０３にメッセージＸ、メッセージＹ、メッセージＮが入力される場合を説明する。メッセージＸ、メッセージＹ、メッセージＮは入出力処理部３０２から入力される適当なメッセージを指す。ただし、メッセージＮは剰余演算の法となるメッセージである（Ｓ７０１）。
【０１５４】
剰余演算器取扱部３３１は、剰余演算器１１５にメッセージＸ、メッセージＹ、メッセージＮを設定し、剰余演算器１１５が実行するモンゴメリ乗算により、ＸＹＭ(-1)ｍｏｄ Ｎの値を持つメッセージＲを得る（Ｓ７０２）。
【０１５５】
次に、剰余演算器取扱部３３１は、法であるメッセージＮの値をＮから（Ｎ＋２ｎ）に変更し、ＸＹＭ(-1)ｍｏｄ （Ｎ＋２ｎ）の値を持つメッセージＲ'を得る。例えば、剰余演算器取扱部３３１は、メッセージＮと定数２nを加算部３３５へ出力し、加算部３３５が出力した値に、剰余演算器１１５を用いて、ＸＹＭ(-1)ｍｏｄ（Ｎ＋２n）の値を持つメッセージＲ'を得る。剰余演算器取扱部３３１は、メッセージＲ'を取得後、メッセージＮと定数２nを減算部３３６へ出力し、減算部３３６が出力した値をメッセージＮとして保存することにより、メッセージＮの値を元に戻す（Ｓ７０３）。
【０１５６】
剰余演算器取扱部はメッセージＸ、メッセージＹ、メッセージＮ、メッセージＲ、メッセージＲ'を出力し、商演算部３３２にそれらのメッセージが入力される。商演算部３３２は、ｍｏｄ算部３３８、乗算部３３９に対して、メッセージＮ、メッセージＲ、定数２2を交換し、ＲＮ(-1)ｍｏｄ ２2の計算結果をメッセージＴ１に格納する（Ｓ７０４）。
【０１５７】
商演算部３３２は、加算部３３５、ｍｏｄ算部３３８、乗算部３３９に対して、定数２n、メッセージＮ、メッセージＲ'、定数２2を交換し、Ｒ'(Ｎ＋２n)(-1) ｍｏｄ ２2の計算結果をメッセージＴ２に格納する（Ｓ７０５）。
【０１５８】
商演算部３３２は、ｍｏｄ算部３３８、乗算部３３９に対して、メッセージＸ、メッセージＹ、定数２2を交換し、ＸＹｍｏｄ ２2の計算結果をメッセージＴ３に格納する（Ｓ７０６）。
【０１５９】
商演算部３３２は、加算部３３５、減算部３３６、ｍｏｄ算部３３８に対して、メッセージＴ１、メッセージＴ２、メッセージＴ３、定数２2を交換し、（−Ｔ１＋Ｔ２＋Ｔ３）ｍｏｄ ２2の結果をメッセージＴに格納する（Ｓ７０７）。
【０１６０】
商演算部３３２は、条件式（Ｔ＞２）が成立するかどうかを判定する（Ｓ７０８）。条件が成立する場合はステップＳ７０９へ行き、条件が成立しない場合はステップＳ７１０へ行く。商演算部３３２は、減算部３３６へメッセージＴと定数２2を出力し、（Ｔ−２2）の値をメッセージＴに格納する（Ｓ７０９）。
【０１６１】
商演算部３３２は、加算部３３５、減算部３３６、乗算部３３９に対して、メッセージＴ、メッセージＮ、定数２ｎ、メッセージＲ、メッセージＲ'を交換し、Ｔ（Ｎ＋２n）＋Ｒ−Ｒ'の結果をメッセージＱに格納する（Ｓ７１０）。
【０１６２】
商演算部３３２は、剰余演算部３３３へメッセージＲを出力する。剰余演算部３３３は、メッセージＲを出力部３３４へ出力する。商演算部３３２は、出力部３３４へメッセージＱを出力する。出力部３３４は、メッセージＱ、メッセージＲを、モンゴメリ乗算の商Ｑと剰余Ｒとして、入出力処理部３０２へ出力する（Ｓ７１１）。
【０１６３】
図１１のフローチャートは、剰余演算器１１５に入力できるメッセージの最大のビット数がｎに限定された場合の、剰余処理部３０３の処理を示す。なお、図１１では剰余演算器１１５へのメッセージの入出力を、図１０と同様に関数ＭＯＮＴＧを用いて表す。
【０１６４】
剰余処理部３０３にメッセージＸ、メッセージＹ、メッセージＮが入力される（Ｓ８０１）。
【０１６５】
剰余処理部３０３は、条件判定部３３７に、メッセージＸ、メッセージＹを出力する。
条件判定部３３７は、受け取ったメッセージＸ、メッセージＹが条件式（０≦Ｘ、Ｙ＜２n）を満たすかを判定する。条件を満たす場合はステップＳ８０４へ行き、条件を満たさない場合はステップＳ８０３へ行く（Ｓ８０２）。
【０１６６】
条件判定部３３７は、メッセージＸが条件式（Ｘ＜０）を満たす場合には、加算部３３５にメッセージＸとメッセージＳを出力する。加算部３３５は、メッセージＸからメッセージＳの値を加算し、出力したメッセージを、条件判定部がメッセージＸに格納する。メッセージＸが条件式（Ｘ≧２n）を満たす場合には、条件判定部３３７は、メッセージＸとメッセージＳを減算部３３６へ出力し、減算部３３６が出力した値をメッセージＸに格納する。条件判定部３３７は、整数ｘiの初期値を０とし、加算部３３５とメッセージを交換するたびにｘiを１ずつ減算、減算部３３６とメッセージを交換するたびにｘiを１ずつ加算する。条件判定部３３７は、メッセージＹと、整数ｙjに対してそれぞれメッセージＸと整数ｘiと同様の処理を行う。なお、メッセージＳは条件式（｜Ｓ｜≦２n）を満たす整数であり、Ｓ＝２nと設定するとＸ、Ｙが条件式（０≦Ｘ、Ｙ＜２n)を満たすｘi、ｙjが一意に定まる（Ｓ８０３）。
【０１６７】
条件判定部３３７は、メッセージＸ、メッセージＹ、整数ｘi、整数ｙjを剰余演算器取扱部３３１に出力する。剰余演算器取扱部３３１は、剰余演算器１１５にメッセージＸ、メッセージＹ、メッセージＮを設定し、剰余演算器１１５が実行するモンゴメリ乗算により、ＸＹＭ(-1)ｍｏｄ Ｎの値を持つメッセージＲを得る（Ｓ８０４）。
【０１６８】
次に、剰余演算器取扱部３３１はＳ８０４と同様の処理を行い、ＸＹＭ(-1)ｍｏｄ（Ｎ＋２(n-2)）またはＸＹＭ(-1)ｍｏｄ（Ｎ−２(n-2)）の計算結果をもつメッセージＲ'を得る。例えば、剰余演算器１１５のメッセージＮの最上位から２番目（最下位を０番目としたとき、最下位から（ｎ−２）番目）のビットを反転させ、剰余演算器１１５を用いて、同様にメッセージＲ'を計算する。剰余の計算後、剰余演算器１１５に設定されたメッセージＮの値を元に戻す（Ｓ８０５）。
【０１６９】
剰余演算器取扱部３３１は、条件判定部３３７へメッセージＮを出力する。条件判定部３３７は、メッセージＮの最上位から２番目（最下位を０番目としたとき、最下位から（ｎ−２）番目）のビットが１であるかを判定し、条件が成立する場合はステップＳ８０８へ、条件が成立しない場合はステップＳ８１１へ行く（Ｓ８０７）。
【０１７０】
剰余演算器取扱部３３１は、メッセージＸ、メッセージＹ、メッセージＮ、メッセージＲ、メッセージＲ'を商演算部３３２に出力し、商演算部３３２はそれらのメッセージを入力として受け付ける。
【０１７１】
商演算部３３２は、減算部３３６、ｍｏｄ算部３３８、乗算部３３９に対して、メッセージＮ、メッセージＲ、メッセージＲ'、定数２2、定数２(n-2)を交換し、ＲＮ(-1)ｍｏｄ ２2の結果をメッセージＴ１に、Ｒ'（Ｎ−２(n-2))(-1) ｍｏｄ ２2の結果をメッセージＴ２に格納する（Ｓ８０８）。
【０１７２】
商演算部３３２は、ｍｏｄ算部３３８、減算部３３６、乗算部３３９に対し、メッセージＴ１、メッセージＴ２、定数４、定数２4を交換し、４（Ｔ１−Ｔ２）ｍｏｄ ２4の結果をメッセージＴに格納する（Ｓ８０９）。
【０１７３】
商演算部３３２は、減算部３３６、ｍｏｄ算部３３８、乗算部３３９に対し、メッセージＸ、メッセージＹ、メッセージＮ、定数２４、定数２n-2を交換し、ＸＹ（Ｎ(-1)−（Ｎ−２(n-2))(-1)）ｍｏｄ ２4の結果をメッセージＴに格納する（Ｓ８１０）。
【０１７４】
商演算部３３２は、ｍｏｄ算部３３８、乗算部３３９に対して、メッセージＮ、メッセージＲ、メッセージＲ'、定数２2、定数２(n-2)を交換し、ＲＮ(-1)ｍｏｄ ２2の結果をメッセージＴ１に、Ｒ'（Ｎ＋２(n-2))(-1)ｍｏｄ ２2の結果をメッセージＴ２に格納する（Ｓ８１１）。
【０１７５】
商演算部３３２は、減算部３３６、ｍｏｄ算部３３８、乗算部３３９に対し、メッセージＴ１、メッセージＴ２、定数４、定数２4を交換し、４（Ｔ２−Ｔ１）ｍｏｄ ２4の結果をメッセージＴに格納する（Ｓ８１２）。
【０１７６】
商演算部３３２は、加算部３３５、ｍｏｄ算部３３８、乗算部３３９に対し、メッセージＸ、メッセージＹ、メッセージＮ、定数２４、定数２(n-2)を交換し、ＸＹ（Ｎ(-1)−（Ｎ＋２(n-2))(-1)）ｍｏｄ ２4の結果をメッセージＴに格納する（Ｓ８１３）。
【０１７７】
商演算部３３２は、加算部３３５、ｍｏｄ算部３３８とメッセージＴ、メッセージＴ３、定数２4を交換し、（Ｔ＋Ｔ３）ｍｏｄ ２4の結果をメッセージＴに格納する（Ｓ８１４）。
【０１７８】
商演算部３３２は、条件式（Ｔ＞２3）が成立するかどうかを判定する（Ｓ８１５）。条件が成立する場合はステップＳ８１６へ行き、条件が成立しない場合はステップＳ８１７へ行く。ステップＳ８１６では、商演算部３３２は、減算部３３６へメッセージＴと定数２4を出力し、Ｔ−２4をメッセージＴに格納する（Ｓ８１６）。
【０１７９】
商演算部３３２は、条件判定部３３７へメッセージＮを出力する。条件判定部３３７は、メッセージＮの最上位から２番目のビットが１であるかを判定し、条件が成立する場合はステップＳ８１８へ、条件が成立しない場合はステップＳ８１９へ行く（Ｓ８１７）。
【０１８０】
商演算部３３２は、加算部３３５、減算部３３６、乗算部３３９とメッセージを交換し、Ｔ（Ｎ−２(n-2)）＋４（Ｒ'−Ｒ）の結果をメッセージＱに格納する（Ｓ８１８）。
【０１８１】
商演算部３３２は、加算部３３５、減算部３３６、乗算部３３９とメッセージを交換し、Ｔ（Ｎ＋２(n-2)）＋４（Ｒ−Ｒ'）の結果をメッセージＱに格納する（Ｓ８１９）。
【０１８２】
商演算部３３２は、メッセージＲ、メッセージＸ、メッセージＹ、整数ｘi、整数ｙj、メッセージＳを剰余演算部３３３に出力する。剰余演算部３３３は、加算部３３５、減算部３３６、乗算部３３９にメッセージＲ、メッセージＳ、メッセージＸ、メッセージＹ、整数ｘi、整数ｙjを交換し、Ｒ＋ｘiＹ＋ｙjＸ＋ｘiｙjＳの結果をメッセージＲに格納する（Ｓ８２０）。
【０１８３】
剰余演算部３３３は、メッセージＲを出力部３３４に出力する。商演算部３３２は、メッセージＱを出力部３３４に出力する。出力部３３４は、受け取ったメッセージＱとメッセージＲを、モンゴメリ乗算の商Ｑと剰余Ｒとして、入出力処理部３０２へ出力する（Ｓ８２１）。
【０１８４】
＜応用例＞
本実施の形態で述べた技術をＲＳＡ暗号に用いる場合、暗号化（または署名検証）処理、復号化（または署名生成）処理など、剰余演算を必要とする全ての処理に適用することができる。また、ＥｌＧａｍａｌ暗号やＤＳＡ暗号、さらに楕円暗号、乱数生成など、剰余演算を利用する全ての処理に適用することができる。
【０１８５】
本実施の形態では、剰余演算器のビット長のｋ（０＜ｋ≦２）倍の剰余演算を演算できることを示したが、本実施の形態で述べた本技術を、再帰的に利用することにより、ビット長のｋ（＞２）倍化にも対応することができる。例として、ビット長を４倍化する場合の基本的な仕組みを説明する。まず、本実施の形態を適用することにより、剰余演算器１１５のビット長の２倍の剰余演算を実現する装置を実現する。次に、その装置を、剰余演算器１１５として利用する。他のデータ処理部１１３、モンゴメリ乗算利用部１１６内の各処理は、処理するデータのビット数が２倍になる。そして、本実施の形態の図２のシーケンス図の処理に従い、剰余演算器のビット長の４倍の剰余演算を処理することができる。
【０１８６】
本実施の形態は、剰余演算器１１５がハードウェアとして実装されている場合を対象としたが、剰余演算器１１５がソフトウェアとして実装されている場合にも、同様に本技術を適用することができる。
【０１８７】
＜実装上の工夫＞
本実施の形態の技術では、ビット長をｋ（０＜ｋ）倍化する過程で、（式２）にて定義したモンゴメリ乗算の商を計算している。しかし、モンゴメリ乗算の商は、法となるメッセージの値が小さい場合に、その絶対値が大きくなりすぎてしまうことがある。絶対値が大きくなりすぎると、オーバーフローや計算量の増加などの問題を引き起こすことがあるため、法にはある程度の大きな値を設定することがのぞましい。
【０１８８】
そこで、図５、図１２および図１３により、法の値を修正し、ある一定の大きさを持つように修正する方法について説明する。図１２および図１３は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部３０２の行うメッセージＮ１の値を変更した場合の、剰余処理部３０３との入出力処理を示すフローチャートである。
【０１８９】
図５のステップＳ５０３において、モンゴメリ乗算の法となるメッセージＮ1を計算した後、以下に示すステップＳ５０４からステップＳ５０６の処理を挿入することにより、メッセージＮ1を変更することができる。
【０１９０】
表現変換部３１１は、メッセージＮ1が条件式（Ｎ1≧２(n-1））を満たすかを判定する（Ｓ５０４）。条件が成立する場合は、ステップＳ５１０へと行く。条件が成立しない場合は、定数２nとメッセージＮ1を減算部３１６へ出力する（Ｓ５０５）。減算部３１６は、定数２nからメッセージＮ1を減算し、（２n−Ｎ1）の値をもつメッセージを出力する。表現変換部３１１は、受け取ったメッセージをメッセージＮ1に格納し（Ｓ５０６）、ステップＳ５１０へと行く。
【０１９１】
上記ステップＳ５０４からステップＳ５０６の処理を挿入することにより、メッセージＮ1は常に、条件式（Ｎ1≧２(n-1)）を満たし、一定の大きさを持った値が法として設定できる。
【０１９２】
表現処理部３０１の処理に、上記ステップＳ５０４からステップＳ５０６の処理を挿入した場合、入出力処理部３０２が行う処理も、いくつかの処理を挿入する必要がある。
【０１９３】
図１２および図１３は、入出力処理部３０２内の入力設定部３２１の処理手続きを示すフローチャートである。
【０１９４】
図１２は、メッセージＮ1を変更した際のメッセージＡの二乗のモンゴメリ乗算を計算する場合、図１３はメッセージＮ1を変更した際のメッセージＡとメッセージＢへのモンゴメリ乗算を計算する場合である。図１２は図８にステップＳ９０３、ステップＳ９０６の処理を追加し、図１３は図９にステップＳ９５３、ステップＳ９５６、ステップＳ９５８の処理を追加している。追加した処理のみを説明する。
【０１９５】
ステップＳ９０３において、入力設定部３２１は、定数０とメッセージＱ1を減算部３１６へ出力する。減算部３１６は、定数０からメッセージＱ1を減算し、その値をメッセージとして出力する。入力設定部３２１は、出力された値をメッセージＱ1に格納する。さらに、入力設定部３２１は、メッセージＲ1とメッセージＱ1を減算部３１６へ出力する。減算部３１６は、メッセージＲ1からメッセージＱ1を減算し、その値をメッセージとして出力する。入力設定部３２１は、出力された値をメッセージＲ1に格納する（Ｓ９０３）。
【０１９６】
ステップＳ９０６において、入力設定部３２１は、定数０とメッセージＱ3を減算部３１６へ出力する。減算部３１６は、定数０からメッセージＱ3を減算し、その値をメッセージとして出力する。入力設定部３２１は、出力された値をメッセージＱ3に格納する。さらに、入力設定部３２１は、メッセージＲ3とメッセージＱ3を減算部３１６へ出力する。減算部３１６は、メッセージＲ3からメッセージＱ3を減算し、その値をメッセージとして出力する。入力設定部３２１は、出力された値をメッセージＲ3に格納する（Ｓ９０６）。
【０１９７】
ステップＳ９５３の処理は、ステップＳ９０３と同様である（Ｓ９５３）。
【０１９８】
ステップＳ９５６の処理は、ステップＳ９０６と同様である（Ｓ９５６）。
【０１９９】
ステップＳ９５８において、入力設定部３２１は、定数０とメッセージＱ4を減算部３１６へ出力する。減算部３１６は、定数０からメッセージＱ4を減算し、その値をメッセージとして出力する。入力設定部３２１は、出力された値をメッセージＱ4に格納する。さらに、入力設定部３２１は、メッセージＲ4とメッセージＱ4を減算部３１６へ出力する。減算部３１６は、メッセージＲ4からメッセージＱ4を減算し、その値をメッセージとして出力する。入力設定部３２１は、出力された値をメッセージＲ4に格納する（Ｓ９５８）。
【０２００】
＜モンゴメリ乗算の商と剰余の補正＞
図２のシーケンス図において、ステップＳ２０２でモンゴメリ乗算利用部１１６がメッセージを受け取ってから、ステップＳ２０５でモンゴメリ乗算利用部１１６がメッセージを出力するまでの、モンゴメリ乗算利用部１１６と剰余演算器１１５が関わる一連の処理を繰り返すことにより、メッセージのべき乗の剰余演算を実行することができる。しかし、メッセージのべき乗の剰余演算を繰り返し実行すると、取り扱うメッセージのサイズが次第に大きくなってしまい、オーバーフローや計算量の増加などの問題を引き起こすことがある。
【０２０１】
図１４により、モンゴメリ乗算利用部１１６が、条件式（−Ｓ＜Ｑ，Ｒ＜Ｓ）を満たすように、モンゴメリ乗算の商Ｑと剰余Ｒを変換する方法について説明する。図１４は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行うモンゴメリ乗算の商と剰余を変換する処理を示すフローチャートである。
【０２０２】
なお、図１４の処理は、図３のモンゴメリ乗算利用部１１６の機能ブロックのうち、入出力処理部３０２の補正部３２３が担当する。
【０２０３】
図１４において、モンゴメリ乗算利用部１１６の補正部３２３へ、モンゴメリ乗算の商Ｑと剰余Ｒ、メッセージＮ１、メッセージＮ０、メッセージＺ、モンゴメリ定数Ｍが入力される（Ｓ１００１）。
【０２０４】
補正部３２３は、条件としてＲの絶対値がＳを越えるか（｜Ｒ｜＞Ｓを満たすか）どうか判定する。補正部３２３は条件を満たせばステップＳ１００３へ行き、条件が成立しない場合はステップＳ１０１１へ行く（Ｓ１００２）。
【０２０５】
補正部３２３は、条件（Ｒ＜−Ｓ）が成立するかどうかを判定する。補正部３２３は条件を満たせばステップＳ１００４へ行き、条件が成立しない場合はステップＳ１００５へ行く（Ｓ１００３）。
【０２０６】
補正部３２３は、加算部３２５へモンゴメリ乗算の剰余Ｒ、メッセージＺを出力し、加算部３２５から出力された（Ｒ＋Ｚ）の値をモンゴメリ乗算の剰余Ｒに格納する。また、補正部３２３は、減算部３２６へモンゴメリ乗算の商Ｑ、モンゴメリ定数Ｍを出力し、減算部３２６から出力された（Ｑ−Ｍ）の値をモンゴメリ乗算の商Ｑに格納する（Ｓ１００４）。
【０２０７】
補正部３２３は、減算部３２６へモンゴメリ乗算の剰余Ｒ、メッセージＺを出力し、減算部３２６から出力された（Ｒ−Ｚ）の値をモンゴメリ乗算の剰余Ｒに格納する。また、補正部３２３は、加算部３２５へモンゴメリ乗算の商Ｑ、モンゴメリ定数Ｍを出力し、加算部３２５から出力された（Ｑ＋Ｍ）の値をモンゴメリ乗算の商Ｑに格納する（Ｓ１００５）。
【０２０８】
補正部３２３は、条件としてＱの絶対値がＳを越えるか（｜Ｑ｜＞Ｓを満たすか）どうか判定する（Ｓ１０１１）。条件が成立する場合、ステップＳ１０１２へ行き、条件が成立しない場合はステップＳ１０２１へ行く。ステップＳ１０１２では、補正部３２３は条件式（Ｑ＜−Ｓ）を満たすかどうか判定する。条件が成立する場合はステップＳ１０１３へ行き、成立しない場合は、ステップＳ１０１６へ行く。
【０２０９】
前述の実装上の工夫において、ステップＳ５０３とステップＳ５１０の間に、ステップＳ５０４からステップＳ５０６の処理を挿入することにより、Ｎ1の値が変更され、一定数より大きくなる（Ｎ1≧２(n-1)）ことを示した。ステップ１０１３では、これらの処理を挿入した場合でも、Ｎ1の値が変更されていない場合はステップＳ１０１４へ、変更された場合にはステップＳ１０１５へと進む。（Ｓ１０１３）
補正部３２３は、加算部３２５と減算部３２６に対して、モンゴメリ乗算の剰余Ｒ、メッセージＮ0、メッセージＺを交換し、（Ｒ＋Ｎ0−Ｚ）の値をモンゴメリ乗算の剰余Ｒに格納する。補正部３２３は、加算部３２５に対し、モンゴメリ乗算の商Ｑ、メッセージＮ１、メッセージＭを交換し、（Ｑ＋Ｎ1＋Ｍ）の値をモンゴメリ乗算の商Ｑに格納する（Ｓ１０１４）。
【０２１０】
補正部３２３は、加算部３２５と減算部３２６に対して、モンゴメリ乗算の剰余Ｒ、メッセージＮ0、メッセージＺを交換し、（Ｒ＋Ｎ0−Ｚ）の値をモンゴメリ乗算の剰余Ｒに格納する。補正部３２３は、加算部３２５と減算部３２６に対して、モンゴメリ乗算の商Ｑ、メッセージＮ1、定数２n、メッセージＭを交換し、（Ｑ−Ｎ1＋２n＋Ｍ）の値をモンゴメリ乗算の商Ｑに格納する（Ｓ１０１５）。
【０２１１】
補正部３２３は、ステップＳ１０１６にて、ステップＳ１０１３と同じ条件判定を行い、Ｎ1の値が変更されていない場合はステップＳ１０１７へ、変更された場合はステップＳ１０１８へと進む（Ｓ１０１６）。
【０２１２】
補正部３２３は、加算部３２５と減算部３２６に対して、モンゴメリ乗算の剰余Ｒ、メッセージＮ0、メッセージＺを交換し、（Ｒ−Ｎ0＋Ｚ）の値をモンゴメリ乗算の剰余Ｒに格納する。補正部３２３は、減算部３２６に対して、モンゴメリ乗算の商Ｑ、メッセージＮ1、メッセージＭを交換し、（Ｑ−Ｎ1−Ｍ）の値をモンゴメリ乗算の商Ｑに格納する（Ｓ１０１７）。
【０２１３】
補正部３２３は、加算部３２５と減算部３２６に対して、モンゴメリ乗算の剰余Ｒ、メッセージＮ0、メッセージＺを交換し、（Ｒ−Ｎ0＋Ｚ）の値をモンゴメリ乗算の剰余Ｒに格納する。補正部３２３は、加算部３２５と減算部３２６に対して、モンゴメリ乗算の商Ｑ、メッセージＮ1、定数２n、メッセージＭを交換し、（Ｑ＋Ｎ1−２n−Ｍ）の値をモンゴメリ乗算の商Ｑに格納する（Ｓ１０１８）。
【０２１４】
補正部３２３は、ステップＳ１０２１にて、条件（｜Ｒ｜＜Ｓ）が満たされるかどうか判定する。条件が成立しない場合は、ステップＳ１００３へ行く。条件が成立する場合はステップＳ１０２２へ行く。
【０２１５】
補正部３２３は、ステップＳ１０２２にて、モンゴメリ乗算の商Ｑと剰余Ｒを出力部３２４へ出力する。出力部３２３は、モンゴメリ乗算の商Ｑと剰余Ｒを出力する（Ｓ１０２２）。
【０２１６】
＜Ａ1とＡ0の補正＞
図１５により、図２に示すシーケンス図のステップＳ２０５で出力されるメッセージが、法として設定されたメッセージよりも小さな値を持つよう、表現処理部３０１がメッセージＡ1とメッセージＡ0を変換する方法について説明する。なお、この処理は、図３のモンゴメリ乗算利用部１１６の機能ブロックのうち、表現処理部３０１の補正部３１３が担当する。図１５は本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行うモンゴメリ乗算の商と剰余を変換する処理を示すフローチャートである。この処理は、図６に示すステップＳ５５２とステップＳ５５３の間に挿入すればよい。
【０２１７】
まず、補正部３１３は、メッセージＡ1、メッセージＡ0、メッセージＮ'1、メッセージＮ'0を入力として受け取る（Ｓ１１０１）。補正部３１３は、条件式（｜Ａ1｜＞２n）が満たされるかを判定する（Ｓ１１０２）。条件が満たされればステップＳ１１０３へ行き、満たされなければステップＳ１１１１へ行く。補正部３１３は、条件式（Ａ1＜０）が満たされるかを判定する（Ｓ１１０３）。条件が成立する場合は、ステップＳ１１０４へ、条件が成立しない場合は、ステップＳ１１０５へ行く。
【０２１８】
補正部３１３は、加算部３１５に、メッセージＡ1とメッセージＮ'1を出力し、（Ａ1＋Ｎ'1）の値をメッセージＡ1に格納する。補正部３１３は、加算部３１５に、メッセージＡ0とメッセージＮ'0を出力し、（Ａ0＋Ｎ'0）の値をメッセージＡ0に格納する（Ｓ１１０４）。
【０２１９】
補正部３１３は、減算部３１６に、メッセージＡ1とメッセージＮ'1を出力し、（Ａ1−Ｎ'1）の値をメッセージＡ1に格納する。補正部３１３は、減算部３１６に、メッセージＡ0とメッセージＮ'0を出力し、（Ａ0−Ｎ'0）の値をメッセージＡ0に格納する（Ｓ１１０５）。
【０２２０】
補正部３１３は、条件式（｜Ａ0｜＞２n）が満たされるかを判定する（Ｓ１１１１）。条件式が満たされればステップＳ１１１２へ行き、満たされなければステップＳ１１１５へ行く。補正部３１３は、条件式（Ａ0＜０）が満たされるかを判定する（Ｓ１１１２）。条件が成立する場合は、ステップＳ１１１３へ行き、条件が成立しない場合は、ステップＳ１１１４へ行く。
【０２２１】
補正部３１３は、減算部３１６に、メッセージＡ1と定数１を出力し、（Ａ1−１）の値をメッセージＡ1に格納する。補正部３１３は、加算部３１５に、メッセージＡ0と定数２nを出力し、（Ａ0＋２n）の値をメッセージＡ0に格納する（Ｓ１１１３）。
【０２２２】
補正部３１３は、加算部３１５に、メッセージＡ1と定数１を出力し、（Ａ1＋１）の値をメッセージＡ1に格納する。補正部３１３は、減算部３１６に、メッセージＡ0と定数２nを出力し、（Ａ0−２n）の値をメッセージＡ0に格納する。（Ｓ１１１４）。
【０２２３】
補正部３１３はメッセージＡ１、メッセージＡ0を出力する（Ｓ１１１５）。
【０２２４】
以上のように、本実施の形態では、モンゴメリ乗算に基づく剰余演算器を用い、剰余演算器が処理可能なビット長を超えるデータの剰余演算を処理することが可能である。
【０２２５】
（実施の形態２）
実施の形態２では、２の拡大体を用いたモンゴメリ乗算に基づく剰余演算のビット長を増幅させる方法および装置について説明する。実施の形態１と実施の形態２の違いは、加減乗除の四則演算が定義される集合が有限体から、２の拡大体に変更されたことである。
【０２２６】
＜モンゴメリ乗算利用部の機能ブロック＞
実施の形態２では、実施の形態１と共通する部分の説明は省き、コンピュータＡ１０１のモンゴメリ乗算利用部１１６の処理を説明する。
【０２２７】
モンゴメリ乗算利用部１１６は、実施の形態１と同様に、モンゴメリ乗算を用い、２ｎビットのメッセージの剰余またはべき乗の剰余を求める機能を持つ。本実施の形態では、図３で示されるモンゴメリ乗算利用部１１６の機能ブロックのうち、減算部３１６、減算部３２６、減算部３３６の機能ブロックは用いない。
【０２２８】
従って、剰余処理部３０３の、剰余演算器取扱部３３１、商演算部３３２、剰余演算部３３３、加算部３３５、条件判定部３３７、ｍｏｄ算部３３８、乗算部３３９で、第１の処理部を構成している。
【０２２９】
また、入出力処理部３０２の、入力設定部３２１、合成部３２２、加算部３２５で、第２の処理部を構成し、入出力処理部３０２の、繰返判定部３２７、条件判定部３２８で、第５の処理部を構成し、入出力処理部３０２の、補正部３２３、加算部３２５で、第６の処理部を構成している。
【０２３０】
また、表現処理部３０１の、表現変換部３１１、加算部３１５で、第３の処理部を構成し、表現処理部３０１の、逆変換部３１２、加算部３１５、合成部３１７で、第４の処理部を構成している。
【０２３１】
＜表現処理部の処理＞
図１６と図１７により、本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理について説明する。図１６および図１７は本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【０２３２】
表現処理部３０１は、実施の形態１と同様、メッセージをモンゴメリ乗算用のメッセージに変換し、またはモンゴメリ乗算用のメッセージから逆変換し、出力する機能を持つ。
【０２３３】
２ｎビットのメッセージＮと、ｎビットのモンゴメリ乗算用のメッセージＮ1とメッセージＮ0の間には、次式が成り立つ。
【０２３４】
Ｎ＝Ｎ1Ｚ＋Ｎ0Ｍ        …（式３）
ただし、Ｍは剰余演算器１１５に設定するモンゴメリ定数、Ｚは最大ｎ次元の任意の多項式である。Ｚを変更することにより、剰余演算器１１５に法として設定するＮ1を変更することができる。例えば、Ｎ1の最下位ビットが常に1になるように、または、Ｎ1が既約多項式になるように、または、Ｎ1とＮ0が最大（ｎ−１）次元になるようにＺの値を設定することができる。
【０２３５】
例として、モンゴメリ定数Ｍの値がｘnである際の、Ｚ＝ｘ(n-1)＋１の場合の、Ｎ1とＮ0を求める手続きを、図１６のフローチャートを用いて説明する。図１６のフローチャートは、表現変換部３１１が最大（２ｎ−１）次元のメッセージＮから、モンゴメリ乗算用のメッセージＮ1とＮ0を作成するまでの処理手続きを示す。
【０２３６】
表現変換部３１１に２ｎビットの多項式からなるメッセージＮが入力される（Ｓ１２０１）。ここで、メッセージＮは、次式からなる（２ｎ−１）次の多項式とする。
【０２３７】
Ｎ＝ｎ2n-1ｘ2n-1＋ｎ2n-2ｘ2n-2＋・・・＋ｎ1ｘ＋ｎ0
この時、以下の（ｎ−１）次の多項式からなるメッセージＮ1とメッセージＮ0を求める。
【０２３８】
Ｎ1＝ｓn-1ｘn-1＋ｓn-2ｘn-2＋・・・＋ｓ1ｘ＋ｓ0
Ｎ0＝ｔn-1ｘn-1＋ｔn-2ｘn-2+・・・＋ｔ1ｘ＋ｔ0
表現変換部３１１は、ｎ0からｎn-2の値をそれぞれｓ0からｓn-2に格納する（Ｓ１２０２）。
【０２３９】
表現変換部３１１は、加算部３２５にｓ0とｎn-1を出力し、加算部３２５がｓ0とｎn-1を加算した結果を、ｓn-1に格納する（Ｓ１２０３）。
【０２４０】
表現変換部３１１は、加算部３２５にｎnからｎ2n-2、ｓ1からｓn-1の値をそれぞれ加算部３２５に出力し、加算した結果をｔ1からｔn-2に格納する（Ｓ１２０４）。
【０２４１】
表現変換部３１１は、ｎ2n-1の値をｔn-1に格納する（Ｓ１２０５）。
【０２４２】
表現変換部３１１は、出力部３１４にメッセージＮ1とメッセージＮ0を出力する。出力部３１４は、受け取ったメッセージＮ1とメッセージＮ0を出力する（Ｓ１２０６）。
【０２４３】
同様の手続きで、表現変換部３１１は、メッセージＡから、モンゴメリ乗算用のメッセージメッセージＡ1とＡ0、メッセージＢから、モンゴメリ乗算用のメッセージＢ1とＢ0を作成し、出力部３１４がそれらのモンゴメリ乗算用のメッセージＡ1、Ａ0、Ｂ1、Ｂ0を出力する。
【０２４４】
なお、図１６では、モンゴメリ定数Ｍの値がｘn、Ｚはｘ(n-1)＋１の場合の手続き示したが、ＭとＺに他の多項式を設定するときも、同様の手続きでモンゴメリ乗算用のメッセージを作成することができる。
【０２４５】
図１７のフローチャートは、モンゴメリ定数Ｍの値がｘn、Ｚはｘ(n-1)＋１の場合に、モンゴメリ乗算の商Ｑと剰余Ｒから２ｎビットのメッセージＣを作成し、出力するまでの処理手続きを示す。
【０２４６】
逆変換部３１２に、モンゴメリ乗算の商Ｑと剰余Ｒが入力される（Ｓ１２５１）。ここで、モンゴメリ乗算のＱと剰余Ｒは、それぞれ次式からなる（ｎ−１）次の多項式とする。
【０２４７】
Ｑ＝ｑn-1ｘn-1 ＋ｑn-2ｘn-2 ＋・・・＋ｑ1ｘ＋ｑ0
Ｒ＝ｒn-1ｘn-1 ＋ｒn-2ｘn-2 ＋・・・＋ｒ1ｘ＋ｒ0
まず、以下の（ｎ−１）次の多項式からなるメッセージＡ1とメッセージＡ0を求める。
【０２４８】
Ａ1＝ａn-1ｘn-1＋ａn-2ｘn-2＋・・・＋ａ1ｘ＋ａ0
Ａ0＝ｂn-1ｘn-1＋ｂn-2ｘn-2＋・・・＋ｂ1ｘ＋ｂ0
逆変換部３１２は、ｒ0からｒn-2の値をａ0からａn-2にそれぞれ格納する（Ｓ１２５２）。
【０２４９】
逆変換部３１２は、加算部３１５にａ0とｒn-1を出力し、加算部３１５がａ0とｒn-1を加算した結果を、ａn-1に格納する（Ｓ１２５３）。
【０２５０】
逆変換部３１２は、加算部３１５にｑ0からｑn-2、ａ1からａn-1の値をそれぞれ加算部３１５に出力し、加算した結果をｂ1からｂn-2に格納する（Ｓ１２５４）。
【０２５１】
逆変換部３１２は、ｑn-1の値をｂn-1に格納する（Ｓ１２５５）。
【０２５２】
逆変換部３１２は、合成部３１７にメッセージＡ1とメッセージＡ0を出力する。合成部３１７は、以下の式を満たすメッセージＣを作成する（Ｓ１２５６）。
【０２５３】
Ｃ＝Σi=0(n-1)ａiｘ(i+n)＋Σi=0(n-1)ｂiｘi
合成部３１７は、メッセージＣを逆変換部３１２に出力する。逆変換部３１２は、受け取ったメッセージＣを出力部３１４に出力する。出力部３１４は、メッセージＣを出力する（Ｓ１２５７）。
【０２５４】
＜入出力処理部の処理＞
図１８および図１９により、本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う剰余処理部との入出力処理について説明する。図１８および図１９は本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う剰余処理部との入出力処理を示すフローチャートである。
【０２５５】
入出力処理部３０２は、剰余処理部３０３へ入力するモンゴメリ乗算用のメッセージを出力する機能を持ち、剰余処理部３０３から出力されたメッセージを入力として受け取り、最大（２ｎ−１）次元のモンゴメリ乗算に基づく剰余演算の剰余を計算し、出力する機能を有する。
【０２５６】
入出力処理部３０２のべき乗に関する処理手順は、実施の形態１の図７とほぼ同様である。相異点は、ステップＳ５７４におけるＡ2の剰余演算の処理が、図１８のフローチャートに記したステップＳ１３０１からステップＳ１３０９の処理手続きになること、ステップＳ５７７におけるＡ×Ｂの剰余演算の処理が、図１９のフローチャートに記したステップＳ１３５１からステップＳ１３６０になることである。
【０２５７】
図１８および図１９では、剰余処理部３０３へのメッセージの入出力を、３つのメッセージを入力として受け取り、２つのメッセージを出力する関数ＧＥＴＱＲとして表す。
【０２５８】
図１８は、メッセージＮを法とするメッセージＡの二乗のモンゴメリ乗算を計算する場合の、入力設定部３２１の処理を示したフローチャートである。入力設定部３２１が剰余処理部３０３にメッセージを出力し、剰余処理部３０３にて出力されたモンゴメリ乗算の商と剰余を用いて、２ｎビットのモンゴメリ乗算の剰余を計算する処理手順を説明する。
【０２５９】
まず、入力設定部３２１にメッセージＡ1、メッセージＮ1、メッセージＡ0、メッセージＮ0、メッセージＺが入力される（Ｓ１３０１）。
【０２６０】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージＺ、メッセージＮ1を出力する。剰余処理部３０３が、入力されたメッセージＡ1、メッセージＺ、メッセージＮ1をもとに計算し、出力したモンゴメリ乗算の商と剰余を、入力設定部３２１はメッセージＱ1、メッセージＲ1に格納する（Ｓ１３０２）。
【０２６１】
ステップＳ１３０３からステップＳ１３０７の処理手順は、ステップＳ１３０２と同様に進める。
【０２６２】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＱ1、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ2、メッセージＲ2に格納する（Ｓ１３０３）。
【０２６３】
入力設定部３２１は、加算部３２５に対してメッセージを交換し、（２Ａ0＋Ｒ1＋Ｑ2）の値を持つメッセージ（２Ａ0＋Ｒ1＋Ｑ2）を得る。
【０２６４】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージ（２Ａ0＋Ｒ1＋Ｑ2）、メッセージＮ1を出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ3、メッセージＲ3に格納する（Ｓ１３０４）。
【０２６５】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＱ3、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ4、メッセージＲ4に格納する（Ｓ１３０５）。
【０２６６】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージＲ2、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の商と剰余をメッセージＱ5、メッセージＲ5に格納する（Ｓ１３０６）。
【０２６７】
入力設定部３２１は、剰余処理部３０３にメッセージＡ0、メッセージＡ0、メッセージＺを出力し、剰余処理部３０３から出力されたモンゴメリ乗算の形式に基づく商と剰余をメッセージＱ6、メッセージＲ6に格納する（Ｓ１３０７）。
【０２６８】
入力設定部３２１は、合成部３２２に、メッセージＲ3、メッセージＲ4、メッセージＲ5、メッセージＲ6、メッセージＱ4、メッセージＱ5、メッセージＱ6を出力する。合成部３２２は、以下の式を満たすＱtotalとＲtotalを計算する（Ｓ１３０８）。
【０２６９】
Ｑtotal＝Ｒ3＋Ｑ4＋Ｑ5＋Ｑ6
Ｒtotal＝Ｒ6＋Ｒ5＋Ｒ4
例えば、合成部３２２は、次のように計算する。合成部３２２は、メッセージＲ3とメッセージＱ4を加算部３２５へ出力する。加算部３２５は、メッセージＲ3にメッセージＱ4の値を加算し、その値をメッセージとして出力する。加算部３２５は、出力されたメッセージ（Ｒ3＋Ｑ4）を入力として受け取り、メッセージＱ5と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ3＋Ｑ4）にメッセージＱ5の値を加算し、その値をメッセージとして出力する。加算部３２５は、出力されたメッセージ（Ｒ3＋Ｑ4＋Ｑ5）を入力として受け取り、メッセージＱ6と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ3＋Ｑ4＋Ｑ5＋Ｑ6）にメッセージＱ6の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ3＋Ｑ4＋Ｑ5＋Ｑ6）を入力として受け取り、メッセージＱtotalに格納する。従って、メッセージＱtotal、メッセージＲ3、メッセージＱ4、メッセージＱ5、メッセージＱ6は以下の関係式を満たす。
【０２７０】
Ｑtotal＝Ｒ3＋Ｑ4＋Ｑ5＋Ｑ6
合成部３２２は、メッセージＲ6とメッセージＲ5を加算部３２５へ出力する。加算部３２５は、メッセージＲ6にメッセージＲ5の値を加算し、その値をメッセージとして出力する。加算部３２５は、出力されたメッセージ（Ｒ6 ＋Ｒ5）を入力として受け取り、メッセージＲ6と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ6＋Ｒ5）にメッセージＲ4の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ6＋Ｒ5＋Ｒ4）を入力として受け取り、メッセージＲtotalに格納する。
【０２７１】
従って、メッセージＲtotal、メッセージＲ4、メッセージＲ5、メッセージＲ6は以下の関係式を満たす。
【０２７２】
Ｒtotal＝Ｒ6＋Ｒ５＋Ｒ４
合成部３２２は、出力部３２４にメッセージＱtotalとメッセージＲtotalを出力する。出力部３２４は、入力されたメッセージＱtotalとメッセージＲtotalを出力する（Ｓ１３０９）。
【０２７３】
図１９は、メッセージＮを法とするメッセージＡとメッセージＢのモンゴメリ乗算を計算する場合の、入出力処理部３０２の処理を示したフローチャートである。入出力処理部３０２が剰余処理部３０３にメッセージを出力し、剰余処理部３０３にて出力されたモンゴメリ乗算の商と剰余を用いて、２ｎビットのモンゴメリ乗算の剰余を計算する処理手順を説明する。
【０２７４】
まず、入力設定部３２１にメッセージＡ1、メッセージＢ1、メッセージＮ1、メッセージＡ0、メッセージＢ0、メッセージＮ0、メッセージＺが入力される（Ｓ１３５１）。
【０２７５】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＢ1、メッセージＺ、メッセージＮ1を出力する。剰余処理部３０３が入力されたメッセージＢ1、メッセージＺ、メッセージＮ1をもとに、計算し、出力したモンゴメリ乗算の商と剰余を、入力設定部３２１はメッセージＱ1、メッセージＲ1に格納する（Ｓ１３５２）。
【０２７６】
ステップＳ１３５３からステップＳ１３５８の処理手続きは、ステップＳ１３５２と同様である。
【０２７７】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＱ1、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３が出力したモンゴメリ乗算の商と剰余をメッセージＱ2、メッセージＲ2に格納する（Ｓ１３５３）。
【０２７８】
入力設定部３２１は、加算部３２５に対してメッセージを交換し、（Ｂ0＋Ｒ1＋Ｑ2）の値を持つメッセージ（Ｂ0＋Ｒ1＋Ｑ2）を得る。
【０２７９】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージ（Ｂ0＋Ｒ1＋Ｑ2）、メッセージＮ1を出力し、剰余処理部３０３が出力したモンゴメリ乗算の商と剰余をメッセージＱ3、メッセージＲ3に格納する（Ｓ１３５４）。
【０２８０】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ0、メッセージＢ1、メッセージＮ1を出力し、剰余処理部３０３が出力したモンゴメリ乗算の商と剰余をメッセージＱ4、メッセージＲ4に格納する（Ｓ１３５５）。
【０２８１】
入力設定部３２１は、加算部３２５に対してメッセージを交換し、（Ｑ3＋Ｑ4）の値を持つメッセージ（Ｑ3＋Ｑ4）を得る。
【０２８２】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージ（Ｑ3＋Ｑ4）、メッセージＮ0、メッセージＺを出力し、剰余処理部３０３が出力したモンゴメリ乗算の商と剰余をメッセージＱ5、メッセージＲ5に格納する（Ｓ１３５６）。
【０２８３】
入力設定部３２１は、モンゴメリ乗算利用部１１６にメッセージＡ1、メッセージＲ2、メッセージＺを出力し、剰余処理部３０３が出力したモンゴメリ乗算の商と剰余をメッセージＱ6、メッセージＲ6に格納する（Ｓ１３５７）。
【０２８４】
入力設定部３２１は、剰余処理部３０３にメッセージＡ0、メッセージＢ0、メッセージＺを出力し、剰余処理部３０３が出力したモンゴメリ乗算の商と剰余をメッセージＱ7、メッセージＲ7に格納する（Ｓ１３５８）。
【０２８５】
入力設定部３２１は、合成部３２２に、メッセージＲ3、メッセージＲ4、メッセージＲ5、メッセージＲ6、メッセージＲ7、メッセージＱ5、メッセージＱ6、メッセージＱ7を出力する。合成部３２２は、以下の式を満たすＱtotalとＲtotalを計算する（Ｓ１３５９）。
【０２８６】
Ｑtotal＝Ｒ3＋Ｒ4＋Ｑ5＋Ｑ6＋Ｑ7
Ｒtotal＝Ｒ7＋Ｒ6＋Ｒ5
例えば、合成部３２２は、次のように計算する。合成部３２２は、メッセージＲ3とメッセージＲ4を加算部３２５へ出力する。加算部３２５では、メッセージＲ3からメッセージＲ4の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ3＋Ｒ4）を入力として受け取り、メッセージＱ5とともに加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ3＋Ｒ4）にメッセージＱ5の値を加算し、その値をメッセージとして出力する。加算部３２５は、出力されたメッセージ（Ｒ3＋Ｒ4＋Ｑ5）を入力として受け取り、メッセージＱ6と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ3＋Ｒ4＋Ｑ5）にメッセージＱ6の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ3＋Ｒ4＋Ｑ5＋Ｑ6）を入力として受け取り、メッセージＱ7と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ3＋Ｒ4＋Ｑ5＋Ｑ6）からメッセージＱ7の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ3＋Ｒ4＋Ｑ5＋Ｑ6＋Ｑ7）を入力として受け取り、メッセージＱtotalに格納する。従って、メッセージＱtotal、メッセージＲ3、メッセージＲ4、メッセージＱ5、メッセージＱ6、メッセージＱ7は以下の関係式を満たす。
【０２８７】
Ｑtotal＝Ｒ3＋Ｒ4＋Ｑ5＋Ｑ6＋Ｑ7
合成部３２２は、メッセージＲ7とメッセージＲ6を加算部３２５へ出力する。加算部３２５は、メッセージＲ7にメッセージＲ6の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ7＋Ｒ6）を入力として受け取り、メッセージＲ5と共に、加算部３２５へ出力する。加算部３２５は、メッセージ（Ｒ7＋Ｒ6）にメッセージＲ5の値を加算し、その値をメッセージとして出力する。合成部３２２は、出力されたメッセージ（Ｒ7＋Ｒ6＋Ｒ5）を入力として受け取り、メッセージＲtotalに格納する。従って、メッセージＲtotal、メッセージＲ5、メッセージＲ6、メッセージＲ7は以下の関係式を満たす。
【０２８８】
Ｒtotal＝Ｒ7＋Ｒ6＋Ｒ5
合成部３２２は、出力部３２４にメッセージＱtotalとメッセージＲｔotalを出力する。出力部３２４は、受け取ったメッセージＱtotalとメッセージＲtotalを出力する（Ｓ１３６０）。
【０２８９】
＜剰余処理部の処理＞
図２０により、本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理について説明する。図２０は本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理を示すフローチャートである。
【０２９０】
図２０に、剰余演算器１１５に入力できるメッセージの最大の次元数が（ｎ−１）である場合の、剰余処理部３０３がモンゴメリ乗算の商と剰余を求める処理手続きを示す。なお、図２０では、剰余演算器１１５を、３つのメッセージを入力として受け取り、１つのメッセージを出力する関数ＭＯＮＴＧとして表す。
【０２９１】
まず、剰余処理部３０３に最大（ｎ−１）次元からなるメッセージＸ、メッセージＹ、メッセージＮが入力される（Ｓ１４０１）。
【０２９２】
剰余演算器取扱部３３１は、剰余演算器１１５にメッセージＸ、メッセージＹ、メッセージＮを設定し、剰余演算器が実行するモンゴメリ乗算により、ＸＹＭ(-1)ｍｏｄ Ｎの値を持つメッセージＲを得る（Ｓ１４０２）。
【０２９３】
次に、剰余演算器取扱部３３１は剰余演算器１１５のメッセージＮの最上位から２番目（最下位から（ｎ−２）番目）のビットを変更し、Ｓ１４０２と同様の処理を行う。例えば、剰余演算器取扱部３３１は、メッセージＮの最上位から２番目のビットを反転させ、剰余演算器１１５を用いて、ＸＹＭ(-1)ｍｏｄ（Ｎ＋ｘ(ｎ-2)）の値をもつにメッセージＲ'を計算する。ただし、剰余の計算後、剰余演算器１１５に設定されたメッセージＮの値を元に戻す（Ｓ１４０３）。
剰余演算器取扱部３３１は、メッセージＸ、メッセージＹ、メッセージＮ、メッセージＲ、メッセージＲ'を商演算部３３２に出力し、商演算部３３２はそれらのメッセージを受け取る。
【０２９４】
商演算部３３２は、加算部３３５、ｍｏｄ算部３３８、乗算部３３９に対して、メッセージＸ、メッセージＹ、メッセージＮを交換し、ＲＮ(-1)ｍｏｄ ｘ2の結果をメッセージＴ１に、Ｒ'（Ｎ＋ｘ(n-2))(-1)ｍｏｄ ｘ2の結果をメッセージＴ２に格納する（Ｓ１４０４）。
【０２９５】
商演算部３３２は、加算部３３５、乗算部３３９に対してメッセージを交換し、次の式を満たすＴを得る。
【０２９６】
Ｔ＝ｘ2（Ｔ１＋Ｔ２)
例えば、メッセージＴは次のように計算する。商演算部３３２は、メッセージＴ１、メッセージＴ２を加算部３３５に出力する。加算部３３５では、メッセージＴ１にメッセージＴ２を加算した値を出力する。商演算部３３２は、メッセージＴに加算部から出力された値を格納し、メッセージＴと定数ｘ2を乗算部３３９に出力する。乗算部３３９では、メッセージＴの値にｘ2の積を取った値をメッセージとして出力する。商演算部３３２は、メッセージＴに出力されたメッセージの値を格納する（Ｓ１４０５）。
【０２９７】
商演算部３３２は、加算部３３５、ｍｏｄ算部３３８にメッセージＸ、メッセージＹ、メッセージＮを出力することにより、以下の式を満たす値をメッセージＴ３に格納する（Ｓ１４０６）。
【０２９８】
Ｔ３＝ＸＹ（（Ｎ＋ｘ(n-2))(-1) ｍｏｄ) ｘ4
商演算部３３２は、加算部３３５にメッセージＴ、メッセージＴ３を出力することにより、（Ｔ＋Ｔ３）の値をメッセージＴに格納する（Ｓ１４０７）。
【０２９９】
商演算部３３２は、メッセージＴ、メッセージＮ、メッセージＲ、メッセージＲ'を加算部３３５に出力することにより、ｘ2Ｔ（Ｎ＋ｘ(n-2)）＋ｘ2（Ｒ'＋Ｒ）の値をメッセージＱに格納する（Ｓ１４０８）。
【０３００】
剰余演算部３３３は、メッセージＲを出力部３３４に出力する。商演算部３３２は、メッセージＱを出力部３３４に出力する。出力部３３４は、メッセージＱ、メッセージＲを入出力処理部３０２へ出力する（Ｓ１４０９）。
【０３０１】
ステップＳ１４０１からステップＳ１４０９では、図２０のフローチャートを用い、剰余演算器１１５に入力できるメッセージの最大の次元数が（ｎ−１）である場合に、剰余処理部３０３がモンゴメリ乗算の商と剰余を求める処理手続きを示した。同様の処理により、剰余演算器１１５に入力できるメッセージの最大の次元数が（ｎ−１）で無い場合にも、モンゴメリ乗算の商と剰余を得ることができる。
【０３０２】
＜応用例＞
本実施の形態では、２の拡大体を用いたモンゴメリ乗算に基づく剰余演算のビット長のｋ（０＜ｋ≦２）倍化させる装置を説明した。本技術はＡＥＳ暗号の暗号化処理または復号化処理など、２の拡大体に基づく剰余演算を必要とする全ての処理に適用することができる。
【０３０３】
本実施の形態の技術を再帰的に利用することにより、実施の形態１と同様、剰余演算器のビット長をｋ（＞２）倍化した剰余演算を実現することができる。
【０３０４】
本実施の形態は、実施の形態１と同様、ハードウェア実装されている剰余演算器だけでなく、ソフトウェア実装されている剰余演算器にも、適用することができる。
【０３０５】
（実施の形態３）
モンゴメリ乗算を応用した、高速な剰余演算（以降、二分剰余演算と呼ぶ）が非特許文献４に提案されている。この剰余演算で求める剰余Ｒαは、以下の式を満たす。
【０３０６】
Ｒα＝ＸＹ（αＭ）(-1)ｍｏｄ Ｎ        …（式４）
ここで、ＸとＹは２ｎビット以下のメッセージ、Ｍはモンゴメリ定数であり、αはαｎが整数かつ条件式（０＜α＜１）を満たす小数である。例えば、αの値を０.５に設定することができる。
【０３０７】
二分剰余演算は、モンゴメリ定数の値を変更したモンゴメリ乗算とみなせる。従って、二分剰余演算が剰余演算器に実装されている場合にも、実施の形態１、実施の形態２と同様に、剰余演算を実行することができる。実施の形態３では、二分剰余演算に基づく剰余演算の第３の計算方法を説明する。
【０３０８】
＜モンゴメリ乗算利用部の機能ブロック＞
図３により、コンピュータＡ１０１のモンゴメリ乗算利用部１１６の処理について、詳細に説明する。
【０３０９】
モンゴメリ乗算利用部１１６では、実施形態１と同様、剰余演算器１１５を用い、モンゴメリ乗算の商と剰余を求め、２ｎビットからなるメッセージの剰余を求める機能を持つ。本実施の形態では、図３で示されるモンゴメリ乗算利用部１１６の機能ブロックの表現処理部３０１に乗算部３１８、除算部３１９を加え、剰余処理部３０３に除算部３４０を加える。
【０３１０】
乗算部３１８は、二つのメッセージを入力として受け付け、二つのメッセージの値の積の値をもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【０３１１】
除算部３１９と除算部３４０は、二つのメッセージを入力として受け付け、一番目のメッセージの値を二番目のメッセージの値で除算し、その剰余を値としてもつメッセージを作成し、メッセージの出力元の機能部へ作成したメッセージを出力する。
【０３１２】
従って、剰余処理部３０３の、剰余演算器取扱部３３１、商演算部３３２、剰余演算部３３３、加算部３３５、減算部３３６、条件判定部３３７、ｍｏｄ算部３３８、乗算部３３９、除算部３４０で、第１の処理部を構成している。
【０３１３】
また、入出力処理部３０２の、入力設定部３２１、合成部３２２、加算部３２５、減算部３２６で、第２の処理部を構成し、入出力処理部３０２の、繰返判定部３２７、条件判定部３２８で、第５の処理部を構成し、入出力処理部３０２の、補正部３２３、加算部３２５、減算部３２６で、第６の処理部を構成している。
【０３１４】
また、表現処理部３０１の、表現変換部３１１、加算部３１５、減算部３１６、乗算部３１８、除算部３１９で、第３の処理部を構成し、表現処理部３０１の、逆変換部３１２、加算部３１５、減算部３１６、合成部３１７、乗算部３１８、除算部３１９で、第４の処理部を構成している。
【０３１５】
＜表現処理部の処理＞
次に、図２１および図２２により、本発明の実施の形態３に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理について説明する。図２１および図２２は本発明の実施の形態３に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【０３１６】
表現処理部３０１は、メッセージを二分剰余演算用のメッセージに変換、または逆変換し、出力する機能を持つ。
【０３１７】
例えば、２ｎビットのメッセージＮを変換する場合は、ｎビットの二分剰余演算用のメッセージＮ1とメッセージＮ0は、メッセージＮと次の式を満たす。
【０３１８】
Ｎ＝Ｎ1Ｚ＋Ｎ0Ｍα        …（式５）
ただし、二分剰余演算用の定数Ｍαは定数αとモンゴメリ定数Ｍの積であり、式、Ｍα＝αＭを満たす。Ｚは２n−ｋ（ｋは正の奇数）である。実施の形態１と同様に、Ｚを奇数に設定することにより、Ｎ1は定数Ｍαと互いに素になる。
【０３１９】
以降では、ｋ＝１（即ち、Ｚ＝２n−１）の場合を説明する。実施の形態１と同様、ｋが他の値を取る時も同様の手法で実施することができる。
【０３２０】
図２１は、表現変換部３１１が、二分剰余演算用のメッセージを出力するまでの処理手続きを示す。ステップＳ５０１、ステップＳ５０２、ステップＳ５１０は、実施の形態１に用いた図５のフローチャートと同じ処理であるので、説明は省く。異なる処理を行う図２１のステップＳ１５０３を説明する。
【０３２１】
ステップＳ１５０３において、表現変換部３１１は、（式５）を満たすように、メッセージＮ1、メッセージＮ0、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0を作成する。例えば、以下の式を満たすようにメッセージＮ1、メッセージＮ0、メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0を作成すると、（式５）を満たすことができる。
【０３２２】
Ｎ1＝２an−Ｎ'0
Ａ1＝２bn−Ａ'0
Ｂ1＝２cn−Ｂ'0
Ｎ0＝（Ｎ'1＋Ｎ'0）２(1-α)n＋（１−２n）２(a-α)n
Ａ0＝（Ａ'1＋Ａ'0）２(1-α)n＋（１−２n）２(b-α)n
Ｂ0＝（Ｂ'1＋ Ｂ'0 ）２(1-α)n＋（１−２n）２(c-α)n
ただし、ａ、ｂ、ｃの値はα以上である。例えば、a＝α、ｂ＝１、ｃ＝αと設定することができる。
【０３２３】
表現変換部３１１は、次のように計算することができる。表現変換部３１１は、加算部３１５、減算部３１６、乗算部３１８に対しメッセージを交換することにより、２an−Ｎ'0の値をメッセージＮ0'に格納することができる。表現変換部３１１は、加算部３１５、減算部３１６、乗算部３１８、除算部３１９に対しメッセージを交換することにより、（Ｎ'1＋Ｎ'0）２(1-α)n＋（１−２n）２(a-α)nの値をメッセージＮ0に格納する。メッセージＡ1、メッセージＡ0、メッセージＢ1、メッセージＢ0もメッセージＮ1とメッセージＮ0と同様に作成する（Ｓ１５０３）。
【０３２４】
なお、ステップＳ１５０３では特定の計算方法を示したが、（式５）を満たすメッセージを計算できる方法であれば、どのような方法でもかまわない。
【０３２５】
次に、逆変換部３１２が、二分剰余演算用のメッセージを、そのビット列に基づいて、２進数で表されるビット列（コンピュータ内の通常の表現形式）に変換し、出力するまでの処理手続きを、図２２のフローチャートを用いて説明する。
【０３２６】
図２２は、逆変換部３１２が、二分剰余演算用のメッセージを出力するまでの処理手続きを示す。ステップＳ５５１、ステップＳ５５３、ステップＳ５５４は、実施の形態１に用いた図６のフローチャートと同じ処理であるので、説明は省く。異なる処理を行う図２２のステップＳ１５５２を説明する。
【０３２７】
ステップＳ１５５２において、逆変換部３１２は、以下の式を満たすように、メッセージＡ0、メッセージＡ1を作成する（Ｓ１５５２）。
【０３２８】
Ａ1２n＋Ａ0＝ＱＺ＋ＲＭα        …（式６）
例えば、以下の式を満たすようにメッセージＡ0、メッセージＡ1を作成すると、（式６）を満たすことができる。
【０３２９】
Ａ0＝２bn−Ｑ
Ａ1＝Ｑ−２(b-1)n＋Ｒ２(α-1)n
逆変換部３１２は、逆変換部３１２は、加算部３１５、減算部３１６、乗算部３１８、除算部３１９に対しメッセージを交換することにより、２bn−Ｑの値をもつメッセージＡ0を、Ｑ−２(b-1)n＋Ｒ２(α-1)nの値をもつメッセージＡ1を得ることができる。
【０３３０】
＜入出力処理部の処理＞
入出力処理部３０２の処理は、実施の形態１と同様である。
【０３３１】
＜剰余処理部の処理＞
次に、図２３により、本発明の実施の形態３に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理について説明する。図２３は本発明の実施の形態３に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理を示すフローチャートである。
【０３３２】
剰余処理部３０３は、入力されたメッセージを用い、二分剰余演算の商と剰余を求める機能を持つ。
【０３３３】
剰余処理部３０３は、入力されたメッセージと剰余演算器１１５から入力された剰余を用い、二分剰余演算の商と剰余を求める機能を持つ。ここで、二分剰余演算の商と剰余とは、次の式を満たすＱとＲを指す。
【０３３４】
ＸＹ＝ＱＮ＋ＲＭα        …（式７）
（式７）は、（式４）を変形し、求めることができる。（式７）では、（式４）の左辺の二分剰余演算用の定数Ｍαが剰余Ｒの乗数となり、法Ｎに対する被乗数を商Ｑとしている。二分剰余演算に対し、商を用いて定義した式が（式７）である。
【０３３５】
図２３のフローチャートを用い、剰余演算器１１５が処理できるメッセージの最大のビット数がｎの場合の、処理手続きを示す。剰余演算器１１５へのメッセージの入出力は関数ＭＯＮＴＧを用いて表す。
【０３３６】
ステップＳ１６０１、ステップＳ１６０２、ステップＳ１６０３の各処理は、それぞれ実施の形態１の図１１に示すステップＳ８０１、ステップＳ８０２、ステップＳ８０３と同様である。
【０３３７】
剰余演算器取扱部３３１は、剰余演算器１１５にメッセージＸ、メッセージＹ、メッセージＮを設定し、剰余演算器１１５が実行する二分剰余演算により、ＸＹＭα(-1)ｍｏｄ Ｎの値を持つメッセージＲを得る（Ｓ１６０４）。
【０３３８】
次に、剰余演算器取扱部３３１は、法であるメッセージＮの値をＮから（Ｎ＋２αｎ）または（Ｎ−２αｎ）に変更し、Ｓ７０２と同様の処理を行う。例えば、剰余演算器取扱部３３１は剰余演算器１１５のメッセージＮのαｎ番目（最下位を０番目とし、最下位から数えてαｎ番目）のビットを反転させ、剰余演算器１１５を用いて、同様にメッセージＲ'を計算する。剰余演算器１１５に設定されたメッセージＮの値を元に戻す（Ｓ１６０５）。
【０３３９】
条件判定部３３７は、メッセージＮのαｎ番目のビットが１であるかを判定し、条件が成立する場合はステップＳ１６０８へ、条件が成立しない場合はステップＳ１６１０へ行く（Ｓ１６０７）。
【０３４０】
商演算部３３２は、減算部３３６、ｍｏｄ算部３３８、乗算部３３９に対して、メッセージＮ、メッセージＲ、メッセージＲ'、定数２αn、定数２2+(1-α)nを交換し、ＲＮ(-1)ｍｏｄ ２2+(1-α)n の結果をメッセージＴ１に、Ｒ'（Ｎ−２(αn))(-1)ｍｏｄ ２2+(1-α)nの結果をメッセージＴ２に格納する（Ｓ１６０８）。
【０３４１】
商演算部３３２は、ｍｏｄ算部３３８、減算部３３６に対して、メッセージＴ２、メッセージＴ１、定数２2+(1-α)nを交換し、（Ｔ１−Ｔ２）ｍｏｄ ２2+(1-α)nの結果をメッセージＴに格納する（Ｓ１６０９）。
【０３４２】
商演算部３３２は、ｍｏｄ算部３３８、減算部３３６、乗算部３３９、除算部３４０に対して、メッセージＸ、メッセージＹ、メッセージＮ、定数２αn、定数２2+(1-α)nを交換し、ＸＹ（（Ｎ(-1)−（Ｎ−２αn)(-1)）/２αn）ｍｏｄ ２2+(1-α)nの結果をメッセージＴ３に格納する（Ｓ１６１０）。
【０３４３】
ステップＳ１６１１にて、商演算部３３２は、加算部３３５、ｍｏｄ算部３３８、乗算部３３９に対して、メッセージＮ、メッセージＲ、メッセージＲ'、定数２αn、定数２2+(1-α)nを交換し、ＲＮ(-1)ｍｏｄ ２2+(1-α)n の結果をメッセージＴ１に、Ｒ'（Ｎ＋２(αn))(-1)ｍｏｄ ２2+(1-α)nの結果をメッセージＴ２に格納する（Ｓ１６１１）。
【０３４４】
商演算部３３２は、減算部３３６、ｍｏｄ算部３３８に対して、メッセージＴ１、メッセージＴ２、定数２(1-α)nを交換し、（Ｔ２−Ｔ１）ｍｏｄ ２(1-α)nの結果をメッセージＴに格納する（Ｓ１６１２）。
【０３４５】
商演算部３３２は、加算部３３５、減算部３３６、ｍｏｄ算部３３８、乗算部３３９、除算部３４０に対して、メッセージＸ、メッセージＹ、メッセージＮ、定数２αn、定数２2+(1-α)nを交換し、ＸＹ（（Ｎ(-1)−（Ｎ＋２αn)(-1)）／２αn）ｍｏｄ ２2+(1-α)nの結果をメッセージＴ３に格納する（Ｓ１６１３）。
【０３４６】
商演算部３３２は、加算部３２５、ｍｏｄ算部３３８に対してメッセージＴ、メッセージＴ３、定数２2+(1-α)nを交換し、（Ｔ＋Ｔ３）ｍｏｄ ２2+(1-α)nの結果をメッセージＴに格納する（Ｓ１６１４）。
【０３４７】
商演算部３３２は、条件式（Ｔ＞２1+(1-α)n）が成立するかどうかを判定する（Ｓ１６１５）。条件が成立する場合はステップＳ１６１６へ行き、条件が成立しない場合はステップＳ１６１７へ行く。ステップＳ１６１６では、商演算部３３２は、減算部３３６へメッセージＴと定数２2+(1-α)nを出力し、Ｔ−２2+(1-α)nの値をメッセージＴに格納する（Ｓ１６１６）。
【０３４８】
商演算部３３２は、条件判定部へメッセージＮを出力する。条件判定部３３７は、メッセージＮのαｎ番目のビットが１であるかを判定し、条件が成立する場合はステップＳ１６１８へ、条件が成立しない場合はステップＳ１６１９へ行く（Ｓ１６１７）。
【０３４９】
商演算部３３２は、加算部３３５、減算部３３６、乗算部３３９とメッセージを交換し、Ｔ（Ｎ−２αn）＋Ｒ'−Ｒの結果をメッセージＱに格納する（Ｓ１６１８）。
【０３５０】
商演算部３３２は、加算部３３５、減算部３３６、乗算部３３９とメッセージを交換し、Ｔ（Ｎ＋２αn）＋Ｒ−Ｒ'の結果をメッセージＱに格納する（Ｓ１６１９）。
【０３５１】
商演算部３３２は、メッセージＲ、メッセージＸ、メッセージＹ、整数ｘi、整数ｙj、メッセージＳを剰余演算部３３３に出力する。剰余演算部３３３は、加算部３３５、減算部３３６、乗算部３３９にメッセージＲ、メッセージＳ、メッセージＸ、メッセージＹ、整数ｘi、整数ｙjを交換し、Ｒ＋ｘiＹ＋ｙjＸ＋ｘiｙjＳの結果をメッセージＲに格納する（Ｓ１６２０）。
【０３５２】
剰余演算部３３３は、メッセージＲを出力部３３４に出力する。商演算部３３２は、メッセージＱを出力部３３４に出力する。出力部３３４は、受け取ったメッセージＱとメッセージＲを、モンゴメリ乗算の商Ｑと剰余Ｒとして、入出力処理部３０２へ出力する（Ｓ１６２１）。
【０３５３】
＜実装上の工夫＞
本実施の形態においても、二分剰余演算の商の絶対値が大きくなりすぎる問題が発生することがある。しかし、実施の形態１の図１４に示した処理手順と同様に、二分剰余演算の商の絶対値が小さくなるよう、変換することができる。実施の形態１の図１４に示すステップＳ１００４、ステップＳ１００５、ステップＳ１０１４、ステップＳ１０１５、ステップＳ１０１７、ステップＳ１０１８で扱うモンゴメリ定数Ｍを、定数Ｍαに変換すればよい。
【０３５４】
＜応用例＞
本実施の形態で述べた技術は、実施の形態１と同様、ＲＳＡ暗号や、ＥｌＧａｍａｌ暗号やＤＳＡ暗号、さらに楕円暗号、乱数生成など、剰余演算を必要とする全ての処理に適用することができる。
【０３５５】
本実施の形態では、二分剰余演算を用いた剰余演算器のビット長のｋ（０＜ｋ≦２）倍の剰余演算を演算できることを示したが、実施の形態１と同様、本実施形態で述べた技術を再帰的に利用することにより、ビット長のｋ（＞２）倍化にも対応することができる。
【０３５６】
本実施の形態は、ハードウェア実装されている剰余演算機を対象に、剰余演算が処理できることを示したが、剰余演算器がソフトウェア実装されている場合にも、本技術を適用することができる。
【０３５７】
本実施の形態で述べた技術は、実施の形態２と同様、２の拡大体に基づく、二分剰余演算を用いた剰余演算器にも利用することができる。ＡＥＳ暗号など、２の拡大体に基づく剰余演算に本技術を適用することができる。さらに、本実施の形態で述べた技術を、２の拡大体に基づく二分剰余演算を用いた剰余演算器に適用する場合、実施の形態２と同様、本実施の形態の技術を再帰的に利用することにより、ビット長のｋ（＞２）倍化に対応することができる。
【０３５８】
二分剰余演算は、通常の剰余演算とモンゴメリ乗算を組み合わせた剰余演算である。通常の剰余演算とモンゴメリ乗算に基づく複数の剰余演算器がハードウェア実装またはソフトウェア実装されている場合にも、本実施の形態で述べた技術を適用することができる。
【０３５９】
さらに、二分剰余演算に基づく異なるαの値を持つ複数の剰余演算器がハードウェア実装またはソフトウェア実装されている場合にも、本実施の形態で述べた技術を適用することができる。
【産業上の利用可能性】
【０３６０】
本発明は、セキュリティ技術に用いられる剰余演算処理装置に関し、特に、サーバ、スマートカード等に搭載される暗号機器への実装に適用可能である。
【図面の簡単な説明】
【０３６１】
【図１】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムの全体構成を示す構成図である。
【図２】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の処理部が行う情報の受け渡しの様子を示したシーケンス図である。
【図３】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内のモンゴメリ乗算利用部１１６の構成を示す機能ブロック図である。
【図４】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内のモンゴメリ乗算利用部と剰余演算器の処理を示すシーケンス図である。
【図５】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【図６】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【図７】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う剰余処理部との入出力処理を示すフローチャートである。
【図８】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う剰余処理部との入出力処理を示すフローチャートである。
【図９】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う剰余処理部との入出力処理を示すフローチャートである。
【図１０】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理を示すフローチャートである。
【図１１】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理を示すフローチャートである。
【図１２】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行うメッセージＮ１の値を変更した場合の、剰余処理部との入出力処理を示すフローチャートである。
【図１３】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行うメッセージＮ１の値を変更した場合の、剰余処理部との入出力処理を示すフローチャートである。
【図１４】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行うモンゴメリ乗算の商と剰余を変換する処理を示すフローチャートである。
【図１５】本発明の実施の形態１に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行うモンゴメリ乗算の商と剰余を変換する処理を示すフローチャートである。
【図１６】本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【図１７】本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【図１８】本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う剰余処理部との入出力処理を示すフローチャートである。
【図１９】本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の入出力処理部の行う剰余処理部との入出力処理を示すフローチャートである。
【図２０】本発明の実施の形態２に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理を示すフローチャートである。
【図２１】本発明の実施の形態３に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【図２２】本発明の実施の形態３に係る剰余演算処理装置を適用した通信システムのコンピュータ内の表現処理部の行う整数表現の変換処理を示すフローチャートである。
【図２３】本発明の実施の形態３に係る剰余演算処理装置を適用した通信システムのコンピュータ内の剰余処理部の処理を示すフローチャートである。
【符号の説明】
【０３６２】
１０１…コンピュータＡ、１０２…記憶部、１０３…ＲＡＭ、１０６…ＥＥＰＲＯＭ、１０７…ＲＡＭ、１０８…外部記憶装置、１０９…ディスプレイ、１１０…キーボード、１１１…入出力インタフェース、１１２…処理部、１１３…データ処理部、１１４…ＣＰＵ、１１５…剰余演算器、１１６…モンゴメリ乗算利用部、１２１…コンピュータＢ、１２２…記憶部、１２３…ＲＡＭ、１２６…ＥＥＰＲＯＭ、１２７…ＲＡＭ、１２８…外部記憶装置、１２９…ディスプレイ、１３０…キーボード、１３１…入出力インタフェース、１３２…処理部、１３３…データ処理部、１３４…ＣＰＵ、１３５…剰余演算器、１３６…モンゴメリ乗算利用部、１４２…ネットワーク、３０１…表現処理部、３０２…入出力処理部、３０３…剰余処理部、３１１…表現出力部、３１１…表現変換部、３１２…逆変換部、３１３…補正部、３１４…出力部、３１５…加算部、３１６…減算部、３１７…合成部、３１８…乗算部、３１９…除算部、３２６…減算部、３２１…入力設定部、３２２…合成部、３２３…出力部、３２３…補正部、３２４…出力部、３２５…加算部、３２６…減算部、３２７…繰返判定部、３２８…条件判定部、３３１…剰余演算器取扱部、３３２…商演算部、３３３…剰余演算部、３３４…出力部、３３５…加算部、３３６…減算部、３３７…条件判定部、３３８…ｍｏｄ算部、３３９…乗算部、３４０…除算部。
【図１】
2007212701.tif 000003
【図２】
2007212701.tif 000004
【図３】
2007212701.tif 000005
【図４】
2007212701.tif 000006
【図５】
2007212701.tif 000007
【図６】
2007212701.tif 000008
【図７】
2007212701.tif 000009
【図８】
2007212701.tif 000010
【図９】
2007212701.tif 000011
【図１０】
2007212701.tif 000012
【図１１】
2007212701.tif 000013
【図１２】
2007212701.tif 000014
【図１３】
2007212701.tif 000015
【図１４】
2007212701.tif 000016
【図１５】
2007212701.tif 000017
【図１６】
2007212701.tif 000018
【図１７】
2007212701.tif 000019
【図１８】
2007212701.tif 000020
【図１９】
2007212701.tif 000021
【図２０】
2007212701.tif 000022
【図２１】
2007212701.tif 000023
【図２２】
2007212701.tif 000024
【図２３】
2007212701.tif 000025