(57)【要約】【課題】  モンゴメリ積和剰余演算で用いるパラメータである必要下位ビット数が多いＮＤ値を高速に演算が可能な演算回路装置を提供する。【解決手段】  ＮＤ値生成部１１は、変数Ｓｕｍの下位ｋビットの値と、正の奇数値Ｎの下位ｋビットの値を参照して、ＮＤ値の必要下位ビットの値を、１クロックサイクルで下位よりｋビットごとに生成し、積和演算部１２は、生成したＮＤ値のｋビットの値と必要下位ビットの正の奇数値Ｎの積に、変数Ｓｕｍを加算する演算を行い、Ｓｕｍ値保持部１３は、積和演算部１２の演算結果をｋビット右シフトした値をＮＤ値生成部１１において次のクロックサイクルで用いる変数Ｓｕｍとして更新し、保持する。【選択図】  図１
2005208498.tif 000002
【特許請求の範囲】
【請求項１】
整数Ｎと、前記整数Ｎと互いに素であって前記整数Ｎより大きな基数ＲによるＲ×Ｒ-1−Ｎ×ＮＤ＝１の関係を満たす、モンゴメリ積和剰余演算で用いるパラメータであるＮＤ値の、必要下位ビットを求める演算回路装置において、
変数Ｓｕｍの下位ｋビットの値と、前記整数Ｎの下位ｋビットの値を参照して、前記ＮＤ値の必要下位ビットの値を、１クロックサイクルで下位よりｋビットごとに生成するＮＤ値生成部と、
生成した前記ＮＤ値のｋビットの値と前記必要下位ビットの前記整数Ｎの積に、前記変数Ｓｕｍを加算する演算を行う積和演算部と、
前記積和演算部の演算結果をｋビット右シフトした値を前記ＮＤ値生成部において次のクロックサイクルで用いる前記変数Ｓｕｍとして更新し、保持するＳｕｍ値保持部と、
を有することを特徴とする演算回路装置。
【請求項２】
前記積和演算部は、Ｂｏｏｔｈアルゴリズムにより部分積を生成する部分積生成部を有し、前記ＮＤ値生成部は、１クロックサイクル前の演算で生成した１ビット下位のＮＤ値をさらに参照して補正することにより前記ＮＤ値を生成することを特徴とする請求項１記載の演算回路装置。
【請求項３】
前記積和演算部は、複数に分割して構成された桁上げ加算器を有することを特徴とする請求項１記載の演算回路装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は積和演算回路を用いた演算回路装置に関し、特に整数Ｎと、整数Ｎと互いに素であって整数Ｎより大きな基数ＲからＲ×Ｒ-1−Ｎ×ＮＤ＝１の関係を満たす、モンゴメリ積和剰余演算で用いるパラメータであるＮＤ値の、必要下位ビットを求める演算回路装置に関する。
【背景技術】
【０００２】
近年、電子商取引（Ｅコマース）などのようにネットワーク上で金銭授受を行う市場が広まり、クレジットカード番号や個人情報などの重要な情報を、ネットワークを介して送受信するような機会が急速に増大している。
【０００３】
このような重要な情報がネットワーク上に流れている間に、悪意ある第３者により情報が盗聴や改ざんされることを防止するため、情報の暗号化技術は欠かせないものとなっている。
【０００４】
暗号化技術の中の１つに公開鍵方式が知られている。
公開鍵方式は、公開鍵と秘密鍵の一対の鍵を用意しておき、送信者が受信者の公開鍵で暗号化し、受信者は受信者しか知りえない秘密鍵で復号化する。例えば、ネットワーク上で商品を購入する場合に、顧客は業者から公開鍵を送ってもらい、これによってクレジットカード番号などの情報を暗号化して送信する。業者は秘密鍵によって受信した情報を復号化する。公開鍵を広く公開することによって、不特定多数の者との通信の秘密が簡単に確保できる。
【０００５】
このような公開鍵方式として、ＲＳＡ（Rivest Shamir Adleman）方式がある。ＲＳＡ方式は、乗算剰余演算を用い、ある数を何回も乗算して整数ｎで割った余りを計算することはコンピュータにとって簡単であるが、その逆の演算で、大きな整数ｎの素因数分解は困難である性質を利用した暗号化方式である。
【０００６】
しかしながら、ＲＳＡ方式における乗算剰余演算の計算量は、ＤＥＳ（Data Encryption Standard）などの対称暗号方式に比較すると多くなるので、高速に計算できるアルゴリズムが求められている。その手法の１つにモンゴメリ積和剰余演算法がある。
【０００７】
モンゴメリ積和剰余演算法は、整数Ｎと、整数Ｎと互いに素であって整数Ｎより大きな基数Ｒに対し、０≦Ｔ≦Ｒ×Ｎである入力値ＴからＴ×Ｒ-1ｍｏｄＮ（Ｔ×Ｒ-1を整数Ｎで割った剰余を示す）を整数Ｎを法とした既約値で求める演算方式である。整数Ｎの値が非常に大きな場合に、整数Ｎの剰余値を求めるのに適した方法である（非特許文献１参照）。
【０００８】
この演算法を実施するに当たって、Ｒ×Ｒ-1−Ｎ×ＮＤ＝１の条件を満たすパラメータであるＮＤ値を求める必要がある（Ｒ-1は整数Ｎを法とする基数Ｒの乗算逆元を示す）。
このＮＤ値は基数Ｒと整数Ｎに対し、除算を繰り返して演算するユークリッドアルゴリズムを適用することで、全ての値を求めることが一般に知られている。
【０００９】
しかし、モンゴメリ積和剰余演算の入力値として使用する場合には、多倍長データであるＮＤ値の全ての値を求める必要はなく、限定された下位ビット（以下必要下位ビットと呼ぶ）のみを算出すればよいことが一般に知られている。
【００１０】
必要下位ビット（例えば３２ビット）のＮＤ値を求める場合にはＮ×ＮＤの必要下位ビットが全て１になる（必要下位ビットが３２ビットならば０ｘｆｆｆｆｆｆｆｆ）性質を利用して、以下で示すようなＮＤ値を演算するアルゴリズムが紹介されている（例えば非特許文献２参照）。
【００１１】
図７は、従来のＮＤ値を算出するアルゴリズムを示す図である。
ここで、表記中のｓはＮＤ値の必要下位ビット数である。また、変数の次の［］内の数字は変数の下位からのビット位置を示している。例えば、Ｓｕｍ［０］は変数Ｓｕｍの最下位ビットである。またＮＤ［ｉ］はＮＤ値の最下位からｉ＋１番目のビットとなる。
【００１２】
まず、変数Ｓｕｍを初期化（Ｓｕｍ：＝０）して、ｉ＝０からｓ−１まで以下の演算を繰り返す。すなわち、Ｓｕｍ［０］が０の場合にはＮＤ［ｉ］に１を代入し（ＮＤ［ｉ］：＝１）、変数Ｓｕｍに整数Ｎ（ただし必要下位ビット長分。以下同様）を加算し１ビット右シフト（アルゴリズム上では＞＞１と表記している）して変数Ｓｕｍを更新する。それ以外の場合には、ＮＤ［ｉ］に０を代入して変数Ｓｕｍは１ビット右シフトさせて更新する。
【００１３】
図８は、ＮＤ値を算出する従来の演算回路の構成を示す図である。
従来のＮＤ値を算出する演算回路８００は、図７で示したアルゴリズムを実施する回路であり、変数Ｓｕｍに応じて整数Ｎの加算の必要の有無を選択するマルチプレクサ８０１と、選択された値と変数Ｓｕｍとの加算を行う２項加算器８０２と、変数Ｓｕｍを格納するＳｕｍレジスタ８０３と、インバータ８０４と、ＮＤ値を格納するＮＤレジスタ８０５とからなる。
【００１４】
変数Ｓｕｍを保持するＳｕｍレジスタ８０３の初期値は０である。マルチプレクサ８０１は変数Ｓｕｍに整数Ｎの加算の必要の有無を変数Ｓｕｍの最下位ビットであるＳｕｍ［０］で判断する。加算の必要がある場合、すなわち“Ｓｕｍ［０］＝＝０”の場合には、Ｎ値が選択され、２項加算器８０２に出力され、それ以外の場合には、０選択され２項加算器８０２に出力される。２項加算器８０２では、選択された値と、Ｓｕｍレジスタ８０３に格納された変数Ｓｕｍとの加算を行い、結果を１ビット右シフトしてＳｕｍレジスタ８０３に再格納する。また、Ｓｕｍ［０］のインバータ８０４による反転値がＮＤ値の最下位ビットとしてＮＤレジスタ８０５に保持される。ＮＤレジスタ８０５はシフトレジスタであり、求められた値が順に右へシフトしていき、ループの終了時点で最終結果がＮＤレジスタに格納される。
【００１５】
なお、求めたいＮＤ値の必要下位ビット数が大きい場合には、加算演算器の桁上げ遅延時間が動作速度を遅らせる原因となってしまうので、この場合には、加算演算器にＣＳＡ（キャリー・セーブ・アダー）を用いることができる。キャリー出力をＳｕｍ値の出力とは別に、キャリーレジスタに保持しておき、整数Ｎ、変数Ｓｕｍ、キャリーをＣＳＡを用いて加算演算することによりＮＤ値を求めることができる。
【非特許文献１】P. L. Montgomery: "Modular Multiplication without Trial Division" , Mathematics of Computation , Vol. 44, No. 170, pp. 519-521 (1985)
【非特許文献２】C. K. Koc. "High-Speed RSA Implementation", Technical Report TR 201, RSA Laboratories, Version 2.0, November, pp. 48-49 (1994)
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかし、ＮＤ値を上記の演算アルゴリズムを用いて実施する従来の演算回路方式は、処理クロック数がＮＤ値の必要下位ビット数分必要となる。モンゴメリ積和剰余演算回路においては、必要下位ビット数が５１２ビットなどと大きいＮＤ値が使用される場合もあり、そのような場合には、処理クロック数が５１２クロック必要になり、演算時間が長くなってしまうという問題があった。
【００１７】
本発明はこのような点に鑑みてなされたものであり、モンゴメリ積和剰余演算で用いるパラメータである必要下位ビット数が多いＮＤ値を高速に演算が可能な演算回路装置を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明では上記問題を解決するために、図１に示すように、整数Ｎと、整数Ｎと互いに素であって整数Ｎより大きな基数ＲによるＲ×Ｒ-1−Ｎ×ＮＤ＝１の関係を満たす、モンゴメリ積和剰余演算で用いるパラメータであるＮＤ値の、必要下位ビットを求める演算回路装置１０において、変数Ｓｕｍの下位ｋビット（図ではｋ＝２ビットの場合について示している。以下同様）の値と、整数Ｎの下位ｋビットの値を参照して、ＮＤ値の必要下位ビットの値を、１クロックサイクルで下位よりｋビットごとに生成するＮＤ値生成部１１と、生成したＮＤ値のｋビットの値と必要下位ビットの整数Ｎの積に、変数Ｓｕｍを加算する演算を行う積和演算部１２と、積和演算部１２の演算結果をｋビット右シフトした値をＮＤ値生成部１１において次のクロックサイクルで用いる変数Ｓｕｍとして更新し、保持するＳｕｍ値保持部１３と、を有することを特徴とする演算回路装置１０が提供される。
【００１９】
上記の構成によれば、ＮＤ値生成部１１は、変数Ｓｕｍの下位ｋビットの値と、整数Ｎの下位ｋビットの値を参照して、ＮＤ値の必要下位ビットの値を、１クロックサイクルで下位よりｋビットごとに生成し、積和演算部１２は、生成したＮＤ値のｋビットの値と必要下位ビットの整数Ｎの積に、変数Ｓｕｍを加算する演算を行い、Ｓｕｍ値保持部１３は、積和演算部１２の演算結果をｋビット右シフトした値をＮＤ値生成部１１において次のクロックサイクルで用いる変数Ｓｕｍとして更新し、保持する。
【発明の効果】
【００２０】
本発明は、ＮＤ値を１クロックサイクルでｋビットずつ生成するようにしたので、ＮＤ値の算出に必要な処理クロックサイクル数を減らすことができ、ビット数の多いＮＤ値を高速に求めることができる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施の形態を図面を参照して詳細に説明する。
図１は、本発明の実施の形態の演算回路装置の原理を説明する概略図である。
なお、以下では、基数Ｒを２のべき乗数、整数Ｎを奇数値として説明を行う。
【００２２】
本発明の実施の形態の演算回路装置１０は、２のべき乗数Ｒと正の奇数値ＮによるＲ×Ｒ-1−Ｎ×ＮＤ＝１の関係を満たす、モンゴメリ積和剰余演算で用いるパラメータであるＮＤ値の必要下位ビットを、１クロックサイクルでｋビットずつ（図１では簡単のため２ビットずつ）求める装置である。
【００２３】
演算回路装置１０は、ＮＤ値を生成するＮＤ値生成部１１と、積和演算処理を行う積和演算部１２と、積和演算の演算結果を２ビット右シフトした値である変数Ｓｕｍを保持するＳｕｍ値保持部１３を有する。また、生成したＮＤ値を格納するＮＤ値格納部１４を有している。
【００２４】
ＮＤ値生成部１１は、変数Ｓｕｍの下位２ビットの値と、正の奇数値Ｎの下位２ビットの値を参照して、ＮＤ値の必要下位ビットの値を、１クロックサイクルで下位より２ビットごとに生成する。
【００２５】
積和演算部１２は、生成したＮＤ値の２ビットの値と正の奇数値Ｎ（ただし、必要下位ビット長分。以下同様）の積に、変数Ｓｕｍを加算する演算を行う。
Ｓｕｍ値保持部１３は、積和演算部１２の演算結果を２ビット右シフトした値を、ＮＤ値生成部１１において次のクロックサイクルで用いる変数Ｓｕｍとして更新し保持する。
【００２６】
ＮＤ値格納部１４は、ＮＤ値生成部１１において、１クロックサイクルで得られる２ビット分のＮＤ値を順に右へ２ビットシフトさせて格納する。
図２は、積和演算部の構成図である。
【００２７】
積和演算部１２は、部分積生成部１２ａと、複数項加算器部１２ｂと、最終桁上げ加算器部１２ｃとを有している。
部分積生成部１２ａは、Ｎ×ＮＤ（ＮＤ［ｉ］，ＮＤ［ｉ＋１］）の部分積を生成する。この部分積生成部１２ａには、ＮＤ［ｉ＋１］，ＮＤ［ｉ］に、１クロックサイクル前の演算で生成した１ビット下位のＮＤ値であるＮＤ［ｉ−１］を加えた３ビットごとに部分積を生成するＢｏｏｔｈアルゴリズムを用いることができる（詳細は後述する）。
【００２８】
複数項加算器部１２ｂは、部分積生成部１２ａで生成した値と、変数Ｓｕｍとの加算を行う。この複数項加算器部１２ｂは、例えば、Wallace Tree構造が用いられる。
最終桁上げ加算器部１２ｃは、複数項加算器部１２ｂの出力である桁上げ遅延がない２項を入力して、最終桁上げ加算を行う。
【００２９】
図３は、最終桁上げ加算器を複数に分割した場合の積和演算回路の構成図である。
図２と同じ構成要素については、同一符号とし、説明を省略する。
最終桁上げ加算器部１２ｃを複数ビットごとに加算器１２ｃ−１、１２ｃ−２、１２ｃ−３のように分割すれば、加算時に桁上げ時間が短縮されて、動作クロック周波数をあげることが可能となる。
【００３０】
この際、加算器１２ｃ−１、１２ｃ−２、１２ｃ−３で生じるキャリーＣｏｕｔは、別途レジスタに保持しておき、次のサイクルの加算時にキャリー入力Ｃｉｎとして与えられる（詳細は後述する）。
【００３１】
なお、部分積生成部１２ａにおいてＢｏｏｔｈアルゴリズムを用いた一般的な積和演算では、図３のようなキャリー分割加算を行うと上位側に符号補正が必要となってしまうが、本発明の実施の形態の演算回路装置１０によれば、処理サイクルが進行するにつれて、上位側から演算して求めなければならない値が２ビットずつ減っていくので、上位側の符号補正は不要になる。
【００３２】
次に本発明の実施の形態の演算回路装置の動作を説明する。
図４は、本発明の実施の形態の演算回路装置の動作を表現したアルゴリズムである。
ここで、表記中のｓはＮＤ値の必要下位ビット数である。また、変数の次の［］内の数字は変数の下位からのビット位置を示している。例えば、Ｓｕｍ［０］は変数Ｓｕｍの最下位ビットである。またＮＤ［ｉ］はＮＤ値の最下位からｉ＋１番目のビットとなる。
【００３３】
演算回路装置１０において、正の奇数値Ｎが入力されると、Ｓｕｍ値保持部１３及びＮＤ値格納部１４の、変数Ｓｕｍ及びＮＤ値が初期化される（Ｓｕｍ：＝０、ＮＤ：＝０）。なお、ここでは、正の奇数値Ｎの最下位ビットは常に１であり、Ｎ［０］＝１として扱うため図４で示すアルゴリズムには表記していない。
【００３４】
その後、ｉ＝０からｓ−１までｆｏｒ文によるループ内で示される以下の演算を繰り返す。
ＮＤ値生成部１１は、変数Ｓｕｍの下位２ビットの値と、正の奇数値Ｎの下位２ビットの値を参照して、ＮＤ値を下位より１クロックサイクルで２ビットずつ生成する。必要下位ビットのＮＤ値を求める場合には、Ｎ×ＮＤの演算結果の必要下位ビットがすべて１になる性質を利用して、図４のループ内の“ｉｆ”または“ｅｌｓｅ  ｉｆ”の行に示されるようにして、２ビットのＮＤ値を生成する。
【００３５】
例えば、（Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“０００”の場合は、（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）として“１１”が生成される。また、（Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“００１”の場合は、（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）として、“０１”が生成される。このように、（Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“０００”から（Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“１１１”まで、計８つの条件に応じて、８つのデコード結果が得られる。
【００３６】
その後、積和演算部１２は、ＮＤ値生成部１１にて生成された２ビットの（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）と、正の奇数値Ｎ、変数Ｓｕｍを入力して、Ｓｕｍ＋Ｎ×（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）の演算を行う。
【００３７】
積和演算部１２の演算結果は、Ｓｕｍ値保持部１３にて、２ビット右シフトされ（アルゴリズム上では＞＞２と表記されている）、新たな変数Ｓｕｍとして更新される。
以上の処理が１クロックサイクルで行われる。
【００３８】
次のクロックサイクルでは、ｉに＋２して（アルゴリズム上ではｓｔｅｐ２と表記されている）、上記と同様の処理をｉ＝ｓ−１となるまで繰り返す。
一方、図４のアルゴリズム上では省略したが、ＮＤ値格納部１４には、ＮＤ値生成部１１にて生成された２ビットの（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）が順次２ビット右シフトされ格納される。
【００３９】
上記のようにして、ループの終了時に、ＮＤ値格納部１４には、必要下位ビット分、すなわちｓビットのＮＤ値が格納される。
このように、本発明の実施の形態の演算回路装置１０によれば、１クロックサイクルでＮＤ値を２ビットずつ求めることができるので、ループ回数をｓの半分にすることができ、演算処理に必要なクロックサイクル数をｓ／２とすることができる。
【００４０】
例えば、従来、必要下位ビットが５１２ビットのＮＤ値を求める場合、クロックサイクル数が５１２回必要であったが、本発明の実施の形態によれば、その半分の２５６回で済む。
【００４１】
また、上記では、ＮＤ値を２ビットずつ求める場合について説明したが、それ以上、例えば、４ビットまたは８ビットずつ求めるようにしてもよい。その場合、ＮＤ値生成部１１は、下位４ビットまたは８ビットの変数Ｓｕｍ、正の奇数値Ｎを参照して、ＮＤ値を４ビットずつ求める。また、積和演算部１２は、生成したＮＤ値の４ビットまたは８ビットの値と、正の奇数値Ｎの積に、変数Ｓｕｍを加算する演算を行う。Ｓｕｍ値保持部１３は、積和演算部１２の演算結果を、４ビットまたは８ビット右シフトして新たな変数Ｓｕｍとして更新する。ＮＤ値格納部１４も、４ビットまたは８ビットずつ右シフトして、ＮＤ値生成部１１で４ビットまたは８ビットずつ生成したＮＤ値を格納する。
【００４２】
次に、積和演算部１２に、一般的に知られている２の補数を使って乗算を行うＢｏｏｔｈアルゴリズム（以下では２次Ｂｏｏｔｈアルゴリズム）を用いたときの本発明の実施の形態の動作を説明する。
【００４３】
図５は、積和演算部にＢｏｏｔｈアルゴリズムを用いたときの本発明の実施の形態の演算回路装置の動作を表現したアルゴリズムである。
なお、ここでは、図４で示したｆｏｒ文によるループ内のみを図示している。
【００４４】
ループ内の、前半はＮＤ値生成部１１にてＮＤ値の下位２ビットを決める処理であり、後半が積和演算部１２にてＮＤ値からＢｏｏｔｈアルゴリズムにしたがって積和演算処理を行う部分である。Ｂｏｏｔｈアルゴリズムを用いる場合には、前のサイクルで求めたＮＤ値を使用して加算結果の補正を行う必要が発生する。この値は、ＮＤ値格納部１４に格納した値を使用することができる。
【００４５】
前半部分では、“ｉｆ”または“ｅｌｓｅ  ｉｆ”の行に示されるように、前サイクルで求めたＮＤ値の上位側のビットＮＤ［ｉ−１］と、変数Ｓｕｍの下位２ビットの値と、正の奇数値Ｎの下位２ビットの値を参照して、ＮＤ値を下位より１クロックサイクルで２ビットずつ生成する。
【００４６】
例えば、（ＮＤ［ｉ−１］、Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“００００”の場合は、（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）として“１１”が生成される。また、（ＮＤ［ｉ−１］、Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“１０００”の場合は、（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）として、“１０”が生成される。このように、（ＮＤ［ｉ−１］、Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“００００”から（ＮＤ［ｉ−１］、Ｓｕｍ［１］、Ｓｕｍ［０］、Ｎ［１］）が“１１１１”まで、計１６の条件に応じて、１６の結果が得られる。
【００４７】
その後、積和演算部１２は、ＮＤ値生成部１１にて生成された２ビットの（ＮＤ［ｉ＋１］、ＮＤ［ｉ］）と、正の奇数値Ｎ、変数Ｓｕｍ及びＮＤ［ｉ−１］を入力して、Ｂｏｏｔｈのアルゴリズムによる積和処理を行う。
【００４８】
Ｎ×ＮＤを計算するために、２次Ｂｏｏｔｈアルゴリズムでは、ＮＤ値をＮＤ［ｉ＋１］、ＮＤ［ｉ］と、前サイクルで求めたＮＤ値の上位ビットＮＤ［ｉ−１］の３ビットごとに部分積を生成する。その３ビットと部分積の値は、（ＮＤ［ｉ＋１］、ＮＤ［ｉ］、ＮＤ［ｉ−１］）が“０００”または“１１１”のときは部分積は“Ｎ×０”、“００１”または“０１０”のときは“Ｎ×１”、“０１１”のときは“Ｎ×２”、“１００”のときは“Ｎ×−２”、“１０１”または“１１０”のときは“Ｎ×−１”となる。
【００４９】
これを、アルゴリズム上では、図５の後半の“ｉｆ”または“ｅｌｓｅ  ｉｆ”の行に示している。ＮＤ［ｉ＋１］、ＮＤ［ｉ］、ＮＤ［ｉ−１］の３ビットの値に応じて、変数Ｓｕｍに加算するＮ×ＮＤ（３ビット）を決定する。なお、図５で、“Ｎ＜＜１”は、１ビット左シフトであり、“Ｎ×２”に相当する。また、“！Ｎ”は、Ｎについて２の補数を取る処理を示し“Ｎ×−１”に相当する。
【００５０】
このような２次Ｂｏｏｔｈアルゴリズムによれば、実質２ビットまとめて部分積を求められるので、部分積項を半分に減らすことができる。
積和演算部１２の演算結果は、Ｓｕｍ値保持部１３にて、２ビット右シフトされ（アルゴリズム上では＞＞２と表記されている）、新たな変数Ｓｕｍとして更新される。
【００５１】
次に、本発明の実施の形態の演算回路装置の具体的な回路構成を説明する。
図６は、本発明の実施の形態の演算回路装置の具体的な回路構成を示す図である。
ここでは、演算するＮＤ値の必要下位ビット数を３２ビット、１サイクルでの処理ビット数を４ビットとした場合について示している。
【００５２】
演算回路装置１００は、ＮＤ値生成デコーダ１１０と、積和演算部１２０、レジスタ部１３０と、ＮＤレジスタ１４０とから構成される。
ＮＤ値生成デコーダ１１０は、図１のＮＤ値生成部１１に対応しており、図５の前半で示したようなアルゴリズムを４ビットに拡張することによりＮＤ値を生成する。すなわち変数Ｓｕｍの下位４ビットと、正の奇数値Ｎの下位４ビット（Ｎ［０］は１なので、実際には３ビット）と、１クロックサイクル前の演算で生成した１ビット下位のＮＤ値であるＮＤ［ｉ−１］を参照して、４ビットのＮＤ値を生成する。
【００５３】
積和演算部１２０は、２次Ｂｏｏｔｈアルゴリズムにより部分積を生成する機能を有し、最終桁上げ加算器を分割した構成である。２次Ｂｏｏｔｈデコーダ１２１と、２つのＢｏｏｔｈセレクタ１２２、１２３と、３項加算器１２４と、７つの２項加算器１２５−１、１２５−２、１２５−３、…、１２５−７とから構成されている。２項加算器１２５−４、１２５−５、１２５−６については図示を省略している。
【００５４】
２次Ｂｏｏｔｈデコーダ１２１は、ＮＤ値生成デコーダ１１０にて生成されたＮＤ値４ビットと、ＮＤレジスタ１４０に格納された１クロックサイクル前の演算で生成した１ビット下位のＮＤ値であるＮ［ｉ−１］から、Ｂｏｏｔｈセレクタ１２２、１２３に制御信号を出力している。
【００５５】
Ｂｏｏｔｈセレクタ１２２、１２３は、制御信号に基づき、Ｎの２倍、１倍、０倍、−１倍、−２倍の値を出力する。ここでの制御信号は、図５の後半に示したようになる。
ここで、正の奇数値Ｎは奇数値であることから、２の補数を求めるに際しての最下位ビットへの１の加算は不要となる。また上位側の符号補正もＮＤ値の下位ビットのみを求めるので不要となる。
【００５６】
３項加算器１２４は、Ｂｏｏｔｈセレクタ１２２、１２３の出力２項と、変数Ｓｕｍの計３項を加算し、２項の出力とする。
７つの２項加算器１２５−１、１２５−２、１２５−３、…、１２５−７は、３項加算器１２４から出力された２項の最終桁上げ加算を行う。最上位の４ビットの２項加算器１２５−７は、キャリーの影響を無視できるため、キャリー出力が存在していない。
【００５７】
レジスタ部１３０は、図１のＳｕｍ値保持部１３に対応しており、各４ビットの７つのＳｕｍレジスタ１３１−１、１３１−２、１３１−３、…、１３１−７を有している。更に、レジスタ部１３０は、積和演算部１２０の２項加算器１２５−１〜１２５−６のキャリーＣ０、Ｃ１、Ｃ２、…、Ｃ５を格納する各１ビットのキャリー保持レジスタ１３２−１、１３２−２、１３２−３、…、１３２−６を有している。キャリー保持レジスタ１３２−４、１３２−５、１３２−６及びそれに格納されるキャリーＣ３、Ｃ４、Ｃ５については図示を省略している。キャリー保持レジスタ１３２−１〜１３２−６に格納されたキャリーＣ０〜Ｃ５は、２項加算器１２５−１〜１２５−６での次のサイクルでの加算に使用される。
【００５８】
ＮＤレジスタ１４０は、図１のＮＤ値格納部１４に対応しており、ＮＤ値生成部１１で生成されたＮＤ値を、順次４ビットごと右シフトして格納する。
次に、図６の演算回路装置１００の動作を簡単に説明する。
【００５９】
演算回路装置１００において、正の奇数値Ｎが入力され、各レジスタが初期化される。
その後、ＮＤ値生成デコーダ１１０によって、変数Ｓｕｍの下位４ビットと、正の奇数値Ｎの下位４ビットと、１クロックサイクル前の演算で生成した１ビット下位のＮＤ値であるＮＤ［ｉ−１］を参照して、４ビットのＮＤ値を生成する。２次Ｂｏｏｔｈデコーダ１２１は、ＮＤ値生成デコーダ１１０にて生成されたＮＤ値４ビットと、Ｎ［ｉ−１］から、Ｂｏｏｔｈセレクタ１２２、１２３に制御信号を出力している。Ｂｏｏｔｈセレクタ１２２、１２３は、制御信号に基づき、Ｎの２倍、１倍、０倍、−１倍、−２倍の値を出力する。Ｂｏｏｔｈセレクタ１２２、１２３の出力２項は、３項加算器１２４に入力され、変数Ｓｕｍの計３項とで加算が行われ、２項の出力となる。その後、３項加算器１２４から出力された２項の最終桁上げ加算が７つの２項加算器１２５−１、１２５−２、１２５−３、…、１２５−７で行なわれる。
【００６０】
加算結果は右４ビットシフトされてＳｕｍレジスタ１３１−１、１３１−２、１３１−３、…、１３１−７に再格納される。
ＮＤ値生成デコーダ１１０から出力されたＮＤ値の４ビットは、ＮＤレジスタ１４０に保持され、都度右４ビットシフトされる。
【００６１】
以上のサイクルを８回繰り返すことで、３２ビットＮＤ値を求めることができる。
なお、上記では２次Ｂｏｏｔｈデコーダ１２１と、ＮＤ値生成デコーダ１１０を別々に設けたが、これを１つのブロックとして統合してしまえば、図５の前半のＮＤ値生成と、Ｂｏｏｔｈアルゴリズムの処理を共通化でき、処理速度が向上する。
【００６２】
また、上記では、ＮＤ値を３２ビット、１サイクルのシフト量を４ビット、２次Ｂｏｏｔｈアルゴリズム、３項加算器を用いて説明したが、高次Ｂｏｏｔｈアルゴリズムを用いる方式や、３項加算器の加算項数を適宜に変更すれば、１サイクルのシフト量は任意に変更可能である。
【００６３】
また、上記では、基数Ｒを２のべき乗数、整数Ｎを奇数値として説明を行ったが、これに限定されず、整数Ｎと基数Ｒの関係が、互いに素であって基数Ｒが整数Ｎより大きければよい。
【産業上の利用可能性】
【００６４】
本発明は、例えば、公開鍵暗号方式の一つであるＲＳＡ方式においてモンゴメリ積和剰余演算を適用した、暗号化回路または復号化回路が搭載されたＩＤカードなどに適用される。
【図面の簡単な説明】
【００６５】
【図１】本発明の実施の形態の演算回路装置の原理を説明する概略図である。
【図２】積和演算部の構成図である。
【図３】最終桁上げ加算器を複数に分割した場合の積和演算回路の構成図である。
【図４】本発明の実施の形態の演算回路装置の動作を表現したアルゴリズムである。
【図５】積和演算部にＢｏｏｔｈアルゴリズムを用いたときの本発明の実施の形態の演算回路装置の動作を表現したアルゴリズムである。
【図６】本発明の実施の形態の演算回路装置の具体的な回路構成を示す図である。
【図７】従来のＮＤ値を算出するアルゴリズムを示す図である。
【図８】ＮＤ値を算出する従来の演算回路の構成を示す図である。
【符号の説明】
【００６６】
１０  演算回路装置
１１  ＮＤ値生成部
１２  積和演算部
１３  Ｓｕｍ値保持部
１４  ＮＤ値格納部
【図１】
2005208498.tif 000003
【図２】
2005208498.tif 000004
【図３】
2005208498.tif 000005
【図４】
2005208498.tif 000006
【図５】
2005208498.tif 000007
【図６】
2005208498.tif 000008
【図７】
2005208498.tif 000009
【図８】
2005208498.tif 000010