(57)【要約】【課題】剰余演算を行って暗号アルゴリズムを処理する暗号処理回路において、ＦＰＧＡの機能拡張に適応した回路構成及び処理方式を採ることで、より少ない回路リソースでの高速動作を可能とし、さらに、回路の汎用性を高めることを目的とする。【解決手段】被乗数をＡ、乗数をＢ、法をＭ、中間値をＱとし、Ａ及びＢの乗算結果とＭ及びＱの乗算結果と中間結果Ｓとの加算結果に基づいて、モンゴメリ乗算による剰余演算を行うモンゴメリ乗算回路２０１において、演算回路Ａ３０１及び演算回路Ｄ６０１は、所定の動作周波数ｃｌｋ１ｘの２倍の動作周波数ｃｌｋ２ｘにて、Ａ及びＢの乗算処理とＭ及びＱの乗算処理とを行う。演算回路Ｂ４０１及び演算回路Ｃ５０１は、ｃｌｋ１ｘにて、上記２つの乗算処理の結果とＳとの加算処理を行う。演算回路Ｃ５０１は、その加算処理の結果に基づいて、モンゴメリ乗算による剰余演算を行う。【選択図】図２
2008176136.tif 000002
【特許請求の範囲】
【請求項１】
被乗数をＡ、乗数をＢ、法をＭ、中間値をＱとし、Ａ及びＢの乗算結果とＭ及びＱの乗算結果と中間結果Ｓとの加算結果に基づいて、モンゴメリ乗算による剰余演算を行う剰余演算装置において、
所定の動作周波数の２倍の動作周波数にて、Ａ及びＢの乗算処理とＭ及びＱの乗算処理とを乗算器で行い、それぞれの乗算結果を出力する多倍長乗算部と、
前記所定の動作周波数にて、前記多倍長乗算部により出力された２つの乗算結果とＳとの加算処理を加算器で行い、当該加算結果を出力する多倍長加算部と、
前記多倍長加算部により出力された加算結果に基づいて、モンゴメリ乗算による剰余演算を行う剰余演算部とを備えることを特徴とする剰余演算装置。
【請求項２】
前記多倍長乗算部は、前記２倍の動作周波数の各サイクルにて、所定のビット長の乗算処理を行い、
前記多倍長加算部は、前記所定の動作周波数の各サイクルにて、前記所定のビット長の２倍の長さの加算処理を行うことを特徴とする請求項１に記載の剰余演算装置。
【請求項３】
前記剰余演算装置は、前記２倍の動作周波数にて、多倍長データの乗算処理を行う多倍長乗算回路を予め具備するＦＰＧＡ（Ｆｉｅｌｄ・Ｐｒｏｇｒａｍｍａｂｌｅ・Ｇａｔｅ・Ａｒｒａｙ）により実装され、
前記多倍長乗算部は、前記多倍長乗算回路により乗算処理を行うことを特徴とする請求項１に記載の剰余演算装置。
【請求項４】
前記剰余演算装置は、
Ｂのビット長をｋビット×ｎ、遅延パラメータをｄとし、
Ｂ＝｛Ｂｎ＋ｄ，・・・，Ｂ１，Ｂ０｝、Ｂｎ＋ｄ，・・・，Ｂｎの各々の値を０とし、
Ｑ＝｛Ｑｎ＋ｄ＋１，・・・，Ｑ１，Ｑ０，Ｑ−１，・・・，Ｑ−ｄ｝、Ｑ０，Ｑ−１，・・・，Ｑ−ｄの各々の値を０とし、
Ｍ’’’＝（Ｍ’’＋１）／２ｋ（ｄ＋１）、Ｍ’’＝Ｍ’（ｍｏｄ（２ｋ（ｄ＋１）））Ｍ、（−ＭＭ’）ｍｏｄ（２ｋ（ｄ＋１））＝１とし、
Ｓ＝｛Ｓｎ＋ｄ＋１，・・・，Ｓ１，Ｓ０｝、Ｓ０の各々の値を０とし、
２ｋｎＲ−１ｍｏｄ（Ｍ）＝１とし、
Ａ及びＢの乗算結果Ｐ＝｛Ｐｎ＋ｄ，・・・，Ｐ１，Ｐ０｝とし、
Ｍ及びＱの乗算結果Ｕ＝｛Ｕｎ＋ｄ，・・・，Ｕ１，Ｕ０｝とし、
Ｐ及びＵの加算結果Ｖ＝｛Ｖｎ＋ｄ，・・・，Ｖ１，Ｖ０｝とし、
カウンタｉを０からｎ＋ｄまで１ずつインクリメントしてｎ＋ｄ＋１回の処理を繰り返すループ処理を行い、
前記多倍長乗算部は、前記２倍の動作周波数にて、各回の処理で、ＡとＢｉとの乗算処理を行い、当該乗算結果Ｐｉを出力するとともに、各回の処理で、Ｍ’’’とＱｉ−ｄとの乗算処理を行い、当該乗算結果Ｕｉを出力し、
前記多倍長加算部は、前記所定の動作周波数にて、各回の処理で、前記多倍長乗算部により出力されたＰｉとＵｉとの加算処理を行い、当該加算結果Ｖｉを出力した後、初回の処理では、Ｖ０とＳ０との加算処理を行い、当該加算結果をＳ１として出力し、２回目以降の処理では、Ｖｉと前回の処理で出力したＳｉとの加算処理を行い、当該加算結果をＳｉ＋１として出力し、
前記剰余演算装置は、さらに、
各回の処理で、Ｖｉの最初のｋビットとＳｉの２番目のｋビットとの加算処理を加算器で行い、当該加算結果をＱｉ＋１として出力する中間値導出部を備え、
前記多倍長乗算部は、各回の処理で、前記中間値導出部により前回の処理で出力されたＱｉを遅延させたＱｉ−ｄを用いて、Ｍ’’’とＱｉ−ｄとの乗算処理を行い、
前記剰余演算部は、ｎ＋ｄ＋１回目の処理の後、前記多倍長加算部により出力されたＳｎ＋ｄ＋１とＳｎ＋ｄからＳｎ＋１までの各々の２番目のｋビットとを連結し、当該ビット列をＳｎ＋ｄ＋２≡ＡＢＲ−１ｍｏｄ（Ｍ）として剰余演算を行うことを特徴とする請求項１に記載の剰余演算装置。
【請求項５】
前記多倍長乗算部は、各回の処理で、Ｍ’’’の最初のｋビットとＱｉ−ｄとの乗算処理を行った後、当該乗算結果とＰｉの最初のｋビットとの加算処理を加算器で行い、当該加算結果をＶｉの最初のｋビットとして出力し、
前記中間値導出部は、各回の処理で、前記多倍長乗算部により出力されたＶｉの最初のｋビットを用いて、Ｖｉの最初のｋビットとＳｉの２番目のｋビットとの加算処理を行うことを特徴とする請求項４に記載の剰余演算装置。
【請求項６】
前記多倍長加算部は、各回の処理で、ＶｉとＳｉとの加算処理を行った後、Ｓｉ＋１を可変シフトレジスタに格納し、前記可変シフトレジスタからＳｉ＋１を出力するタイミングを調整することを特徴とする請求項４に記載の剰余演算装置。
【請求項７】
被乗数をＡ、乗数をＢ、法をＭ、中間値をＱとし、Ａ及びＢの乗算結果とＭ及びＱの乗算結果と中間結果Ｓとの加算結果に基づいて、モンゴメリ乗算による剰余演算を行う剰余演算方法において、
所定の動作周波数の２倍の動作周波数にて、Ａ及びＢの乗算処理とＭ及びＱの乗算処理とを行い、それぞれの乗算結果を出力する多倍長乗算ステップと、
前記所定の動作周波数にて、前記多倍長乗算ステップで出力された２つの乗算結果とＳとの加算処理を行い、当該加算結果を出力する多倍長加算ステップと、
前記多倍長加算ステップで出力された加算結果に基づいて、モンゴメリ乗算による剰余演算を行う剰余演算ステップとを備えることを特徴とする剰余演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、剰余演算装置及び剰余演算方法に関するものである。本発明は、特に、剰余演算装置における多倍長演算器及びその制御方式（処理方式）に関するものである。
【背景技術】
【０００２】
現在、電子商取引やネットワーク通信などではＲＳＡ（登録商標）（Ｒｉｖｅｓｔ・Ｓｈａｍｉｒ・Ａｄｌｅｍａｎ）公開鍵暗号方式（以下、「ＲＳＡ暗号」という）が利用されている。ＲＳＡ暗号では、べき乗剰余演算の処理を必要とする。一般に、ＲＳＡ暗号で用いられるべき乗剰余演算は、演算対象となるデータが５１２ビットや１０２４ビットなどの大きなサイズを持つため、非常に長い処理時間がかかることが知られている。
【０００３】
べき乗剰余演算をハードウェア上で効率的に行う計算法として、Ｐ．Ｌ．Ｍｏｎｔｏｇｏｍｅｒｙにより提案されたモンゴメリ乗算と呼ばれるアルゴリズムが一般に知られている。このモンゴメリ乗算では、剰余演算で必要な除算処理をビットシフトで置き換えることができる。非特許文献１では、回路がレイテンシを持つ場合においても、効率よくモンゴメリ乗算を計算するアルゴリズムが開示されている。以下に非特許文献１に記載されているモンゴメリ乗算のアルゴリズムについて説明する。
【０００４】
【数１】
2008176136.tif 000003
【０００５】
上記モンゴメリ乗算のハードウェアによる従来方式として、非特許文献１では、４−２加算器による構成例が開示されている。また、非特許文献２ではＦＰＧＡ（Ｆｉｅｌｄ・Ｐｒｏｇｒａｍｍａｂｌｅ・Ｇａｔｅ・Ａｒｒａｙ）のＲＡＭ（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）と加算器で構成される演算器を基本構成単位としたシストリックアレイ（Ｓｙｓｔｏｌｉｃ・Ａｒｒａｙ）の構成が示されている。非特許文献３ではＦＰＧＡの組み込み乗算器を用いたシストリックアレイの構成が示されている。ＦＰＧＡとしては、例えば非特許文献４に示されるようなものがある。
【非特許文献１】Ｈ．Ｏｒｕｐ、“Ｓｉｍｐｌｉｆｙｉｎｇ  Ｑｕｏｔｉｅｎｔ  Ｄｅｔｅｒｍｉｎａｔｉｏｎ  ｉｎ  Ｈｉｇｈ−Ｒａｄｉｘ  Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ”、Ｐｒｏｃ．  ｏｆ  ｔｈｅ  １２ｔｈ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｒｉｔｈｍｅｔｉｃ、１９９５年
【非特許文献２】Ｔ．Ｂｌｕｍ、Ｃ．Ｐａａｒ、“Ｈｉｇｈ−Ｒａｄｉｘ  Ｍｏｎｔｇｏｍｅｒｙ  Ｍｏｄｕｌａｒ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ｏｎ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｈａｒｄｗａｒｅ”、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ、Ｖｏｌ．５０、Ｎｏ．７、ｐｐ．７５９−７６４、２００１年７月
【非特許文献３】Ｓ．Ｈ．Ｔａｎｇ、Ｋ．Ｓ．Ｔｓｕｉ、Ｐ．Ｈ．Ｗ．Ｌｅｏｎｇ、“Ｍｏｄｕｌａｒ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ｕｓｉｎｇ  Ｐａｒａｌｌｅｌ  Ｍｕｌｔｉｐｌｉｅｒｓ”、Ｐｒｏｃｅｅｄｉｎｇｓ．２００３  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｔｅｃｈｎｏｌｏｇｙ（ＦＰＴ）、ｐｐ．５２−５９、２００３年１２月
【非特許文献４】Ｘｉｌｉｎｘ，Ｉｎｃ．、「Ｖｉｒｔｅｘ−４  ユーザーガイド」、２００５年９月１２日、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｄｉｒｅｃｔ．ｘｉｌｉｎｘ．ｃｏｍ／ｂｖｄｏｃｓ／ｕｓｅｒｇｕｉｄｅｓ／ｊ＿ｕｇ０７０．ｐｄｆ＞
【発明の開示】
【発明が解決しようとする課題】
【０００６】
近年のＦＰＧＡでは様々な機能拡張が行われている。例えば、一般的なものでは、多倍長データの乗算処理を高速で行うための専用回路が予め実装されているため、これらを利用して乗算処理を効率的に行うデバイスを容易に実現することができる。また、例えば、非特許文献４のＦＰＧＡのように、音声や画像などの処理で一般に広く利用されているＤＳＰ（Ｄｉｇｉｔａｌ・Ｓｉｇｎａｌ・Ｐｒｏｃｅｓｓｏｒ）の基本要素が複数組み込まれるようになったものもある。前述したようなモンゴメリ乗算のハードウェアによる従来方式は、このようなＦＰＧＡの機能拡張を想定して構成されていないため、機能拡張されたＦＰＧＡに従来方式を単純に実装しても、ＦＰＧＡが持つ機能を十分に引き出すことができないという課題があった。
【０００７】
本発明は、剰余演算を行って暗号アルゴリズムを処理する暗号処理回路において、ＦＰＧＡの機能拡張に適応した回路構成及び処理方式を採ることで、より少ない回路リソースでの高速動作を可能とし、さらに、回路の汎用性を高めることを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一の態様に係る剰余演算装置は、
被乗数をＡ、乗数をＢ、法をＭ、中間値をＱとし、Ａ及びＢの乗算結果とＭ及びＱの乗算結果と中間結果Ｓとの加算結果に基づいて、モンゴメリ乗算による剰余演算を行う剰余演算装置において、
所定の動作周波数の２倍の動作周波数にて、Ａ及びＢの乗算処理とＭ及びＱの乗算処理とを乗算器で行い、それぞれの乗算結果を出力する多倍長乗算部と、
前記所定の動作周波数にて、前記多倍長乗算部により出力された２つの乗算結果とＳとの加算処理を加算器で行い、当該加算結果を出力する多倍長加算部と、
前記多倍長加算部により出力された加算結果に基づいて、モンゴメリ乗算による剰余演算を行う剰余演算部とを備えることを特徴とする。
【発明の効果】
【０００９】
本発明の一の態様によれば、被乗数をＡ、乗数をＢ、法をＭ、中間値をＱとし、Ａ及びＢの乗算結果とＭ及びＱの乗算結果と中間結果Ｓとの加算結果に基づいて、モンゴメリ乗算による剰余演算を行う剰余演算装置において、多倍長乗算部が、所定の動作周波数の２倍の動作周波数にて、Ａ及びＢの乗算処理とＭ及びＱの乗算処理とを乗算器で行い、それぞれの乗算結果を出力し、多倍長加算部が、前記所定の動作周波数にて、前記多倍長乗算部により出力された２つの乗算結果とＳとの加算処理を加算器で行い、当該加算結果を出力し、剰余演算部が、前記多倍長加算部により出力された加算結果に基づいて、モンゴメリ乗算による剰余演算を行うことにより、剰余演算を行って暗号アルゴリズムを処理する暗号処理回路において、より少ない回路リソースでの高速動作が可能となり、さらに、回路の汎用性が向上する。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施の形態について、図を用いて説明する。
【００１１】
実施の形態１．
本実施の形態に係る暗号処理回路は、剰余演算を行って暗号アルゴリズムを処理するために、特に、ＦＰＧＡのリソースを有効活用することにより、処理の高速化と回路の小型化を実現するものである。
【００１２】
図１は、本実施の形態に係る暗号処理回路を用いたデバイスの一例として、ＦＰＧＡを用いたセキュリティチップ１０１の構成を示すブロック図である。セキュリティチップ１０１は、例えば、携帯電話、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ・Ｃｉｒｃｕｉｔ）カード、ＩＣカードリーダライタといった小型端末やネットワークルータなどの通信機器に組み込まれ、通信データの暗号処理のために用いられる。
【００１３】
図１において、セキュリティチップ１０１は、ＣＰＵ１０２（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）、内部メモリ１０３、外部インタフェース１０４、暗号処理回路用メモリ１０５を備え、これらはバス１０６で接続されている。また、セキュリティチップ１０１は、本実施の形態に係る暗号処理回路として、モンゴメリ乗算回路２０１を備える。
【００１４】
ＣＰＵ１０２は、モンゴメリ乗算回路２０１に対する入出力の制御、内部メモリ１０３のデータの読み書き、外部インタフェース１０４を介した外部装置との通信などを行うプログラムを実行するプロセッサ（処理装置）である。内部メモリ１０３は、ＣＰＵ１０２の作業領域として利用されるＲＡＭ（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、各種プログラムや設定パラメータなどを格納するＲＯＭ（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）からなり、ＦＰＧＡが持つ機能の１つである組み込みメモリで実装することが想定される。外部インタフェース１０４は、シリアル通信やＬＡＮ（ローカルエリアネットワーク）などの各種インタフェースであり、セキュリティチップ１０１に対して、モンゴメリ乗算回路２０１で処理するデータの入出力を行う。暗号処理回路用メモリ１０５は、モンゴメリ乗算回路２０１とバス１０６間のインタフェースとして用いられる。
【００１５】
モンゴメリ乗算回路２０１は、剰余演算装置の一例である。モンゴメリ乗算回路２０１は、モンゴメリ乗算を利用した暗号処理に、ＦＰＧＡが持つ機能や特性を活用することで、従来方式より効率的な演算を可能とするものである。以下、モンゴメリ乗算回路２０１の詳細について説明する。
【００１６】
まず、モンゴメリ乗算回路２０１に実装されるアルゴリズムを以下に示す。下記アルゴリズムは、非特許文献１に記載のモンゴメリ乗算のアルゴリズムをＦＰＧＡが持つ機能や特性を考慮して改良したものである。
【００１７】
【数２】
2008176136.tif 000004
【００１８】
【数３】
2008176136.tif 000005
【００１９】
【数４】
2008176136.tif 000006
【００２０】
上記アルゴリズムの擬似コードにおいて、“｜”はビット連結を意味する。また、ｃａｒｒｙ＿ｋはｋビット、ｃａｒｒｙ＿１は１ビットの中間値を意味する。また、変数ｐ［ｉ］［ｊ］、ｕ［ｉ］［ｊ］、ｖ［ｉ］［ｊ］、ｓ［ｉ］［ｊ］はそれぞれｋビットとし、初期値は０とする。
【００２１】
上記擬似コードの特徴は、乗算処理をｋビットごとの２つの乗算処理、多倍長乗算処理（１）、多倍長乗算処理（２）に分割している点と、加算処理を２ｋビットごとの２つの加算処理、多倍長加算処理（１）、多倍長加算処理（２）に分割している点である。また、他の特徴として、多倍長乗算処理（２）ではｊ＝０の場合のみ処理を変更することで、ｑ導出処理を高速に行うことが挙げられる。これらの理由及び詳細については後述する。
【００２２】
図２は、モンゴメリ乗算回路２０１の構成を示すブロック図である。図２に示したモンゴメリ乗算回路２０１全体で、前述した擬似コード全体が処理される。
【００２３】
図２において、モンゴメリ乗算回路２０１は、演算回路Ａ３０１、演算回路Ｂ４０１、演算回路Ｃ５０１、演算回路Ｄ６０１の４種類の演算回路を備える。演算回路Ａ３０１、演算回路Ｄ６０１は、多倍長乗算部の一例であり、擬似コードの多倍長乗算処理（１）及び多倍長乗算処理（２）を行う演算回路である。また、演算回路Ｂ４０１、演算回路Ｃ５０１は、多倍長乗算部の一例であり、順に、擬似コードの多倍長加算処理（１）、多倍長加算処理（２）を行う演算回路である。モンゴメリ乗算回路２０１全体の構成及び動作について説明する前に、まず、それぞれの種類の演算回路について説明する。
【００２４】
図３は、演算回路Ａ３０１の構成の一例を示すブロック図である。
【００２５】
図３に示した演算回路Ａ３０１は、前述した擬似コードの多倍長乗算処理（１）及び多倍長乗算処理（２）におけるループ処理のうち、ｊ＝０からｊ＝（２ｔ−１）までの処理を行うものである。この演算回路Ａ３０１の処理は以下の擬似コード（以下、「擬似コードＡ」という）で表せる。
【００２６】
【数５】
2008176136.tif 000007
【００２７】
ここで、擬似コードＡと演算回路Ａ３０１の各部との対応について説明する。
【００２８】
まず、入力ポート３０２から、擬似コードＡのａ［ｊ］及びａ［ｊ＋１］、もしくは、ｍ［ｊ］及びｍ［ｊ＋１］が同時に入力される。そのため、入力ポート３０２は、２ｋビットのバス幅を持つ。また、入力ポート３０３からは、擬似コードＡのｂ［ｉ］が入力される。また、入力ポート３０４からは、擬似コードＡのｑ［ｉ−ｄ］が入力される。入力ポート３０２，３０３，３０４から入力されたデータは、それぞれ入力レジスタ３０９，３１０，３１１，３１２に格納される。
【００２９】
入力レジスタ３０９，３１０に格納されたデータがａ［ｊ］とａ［ｊ＋１］の場合、そのどちらか一方がマルチプレクサ３０６で選択され、中間レジスタ３１３に格納される。同様に、入力レジスタ３０９，３１０に格納されたデータがｍ［ｊ］とｍ［ｊ＋１］の場合、そのどちらか一方がマルチプレクサ３０６で選択され、中間レジスタ３１３に格納される。また、入力レジスタ３１１，３１２に格納されたｂ［ｉ］及びｑ［ｉ−ｄ］は、マルチプレクサ３０７で選択され、中間レジスタ３１４に格納される。中間レジスタ３１４のデータは、出力ポート３１９に出力される。
【００３０】
中間レジスタ３１３と中間レジスタ３１４に格納されたデータは、乗算器３１６で乗算処理され、その結果が中間レジスタ３１５に格納される。ここで、中間レジスタ３１５はｋビット×ｋビットの乗算結果を格納するため、２ｋビットのレジスタとなる。中間レジスタ３１５に格納されたデータは、入力ポート３０５から与えられ入力レジスタ３０８に格納されたデータ、もしくは、出力レジスタ３２２に格納されたデータの上位ｋビットと加算器３１７で加算処理され、その結果が出力レジスタ３２２に格納される。ここで、入力レジスタ３０８に格納されたデータと出力レジスタ３２２に格納されたデータの上位ｋビットの選択はマルチプレクサ３１８で行われる。出力レジスタ３２２は、２ｋビットのレジスタであり、上位ｋビットはマルチプレクサ３１８の入力と出力ポート３２０に接続され、下位ｋビットは出力ポート３２１に接続されている。
【００３１】
続けて、演算回路Ａ３０１の詳細な動作について説明する。ここで、図３の点線外における動作クロックをｃｌｋ１ｘとし、点線内の動作クロックをｃｌｋ２ｘと表記する。ｃｌｋ２ｘはｃｌｋ１ｘの２倍の動作周波数であるものとする。図３の点線内は、ＦＰＧＡであるセキュリティチップ１０１に予め設けられている多倍長乗算回路３２３である。前述したように、ＦＰＧＡは、このような乗算処理のための専用回路を具備している。そして、ＦＰＧＡの特性の１つとして、このような専用回路は一般的に高い周波数で動作することができる。
【００３２】
最初に、入力ポート３０２から、ｃｌｋ１ｘを基準としてａ［１］｜ａ［０］が入力される。以降、ｃｌｋ１ｘを基準としてａ［２ｔ−１］｜ａ［２ｔ−２］まで毎サイクル、入力ポート３０２からデータが連続して入力される。以下では、この処理を入力処理ａと呼ぶことにする。続けて、入力ポート３０２から、ａ［２ｔ−１］｜ａ［２ｔ−２］が入力されたサイクルの次のサイクルでｍ［１］｜ｍ［０］が入力される。以降、ｃｌｋ１ｘを基準としてｍ［２ｔ−１］｜ｍ［２ｔ−２］まで毎サイクル、入力ポート３０２からデータが連続して入力される。以下では、この入力処理ａの終了後の処理を入力処理ｍと呼ぶことにする。入力処理ｍの終了後は再び入力処理ａ、入力処理ｍが繰り返し実行される。そして、この一連の処理は、所定の回数（ｉ＝０からｉ＝ｎ＋ｄまで）繰り返し実行される。
【００３３】
上記の入力処理ａ及び入力処理ｍに同期しながら、ｃｌｋ１ｘを基準として入力ポート３０３からはｂ［ｉ］が、入力ポート３０４からはｑ［ｉ−ｄ］が入力される。
【００３４】
マルチプレクサ３０６は、ｃｌｋ２ｘを基準として入力レジスタ３０９と入力レジスタ３１０に格納されたデータを交互に選択する。マルチプレクサ３０７は、入力レジスタ３０９と入力レジスタ３１０に入力処理ａのデータが格納されている場合には、入力レジスタ３１１に格納されたデータであるｂ［ｉ］を選択する。一方、入力レジスタ３０９と入力レジスタ３１０に入力処理ｍのデータが格納されている場合には、入力レジスタ３１２に格納されたデータであるｑ［ｉ−ｄ］を選択する。つまり、中間レジスタ３１３にａ［ｊ］あるいはａ［ｊ＋１］が格納されている場合は、中間レジスタ３１４にｂ［ｉ］が格納され、中間レジスタ３１３にｍ［ｊ］あるいはｍ［ｊ＋１］が格納されている場合は、中間レジスタ３１４にｑ［ｉ−ｄ］が格納される。
【００３５】
これにより、乗算器３１６では、入力処理ａに対応してｂ［ｉ］・ａ［ｊ］（“・”は乗算処理を表すが、省略する場合がある）が処理され、入力処理ｍに対応してｑ［ｉ−ｄ］・ｍ［ｊ］が処理される。処理結果は、中間レジスタ３１５に格納される。
【００３６】
次に、中間レジスタ３１５にｂ［ｉ］・ａ［０］が格納されている場合、入力レジスタ３０８の値は０にセットされ、マルチプレクサ３１８で入力レジスタ３０８の値が選択されて、加算器３１７がｂ［ｉ］・ａ［０］＋０の処理を実行する。それ以降は、マルチプレクサ３１８で出力レジスタ３２２の上位ｋビットの値が選択されて、加算器３１７がｂ［ｉ］・ａ［ｊ］＋ｃａｒｒｙ＿ｋの処理を実行する。一方、中間レジスタ３１５にｑ［ｉ−ｄ］・ｍ［０］が格納されている場合、入力レジスタ３０８の値はｐ［ｉ］［０］にセットされ、マルチプレクサ３１８で入力レジスタ３０８の値が選択されて、加算器３１７がｑ［ｉ−ｄ］・ｍ［０］＋ｐ［ｉ］［０］の処理を実行する。それ以降は、マルチプレクサ３１８で出力レジスタ３２２の上位ｋビットの値が選択されて、加算器３１７がｑ［ｉ−ｄ］・ｍ［ｊ］＋ｃａｒｒｙ＿ｋの処理を実行する。
【００３７】
以上の処理により、出力ポート３２１には、入力処理ａに対応してｐ［ｉ］［０］からｐ［ｉ］［２ｔ−１］が出力され、入力処理ｍに対応してｖ［ｉ］［０］及びｕ［ｉ］［１］からｕ［ｉ］［２ｔ−１］が出力される。また、出力ポート３２０には、出力ポート３２１に対応したｃａｒｒｙ＿ｋが出力される。出力ポート３２０，３２１には、ｃｌｋ２ｘを基準としてサイクルごとに各データが出力される。
【００３８】
このように、演算回路Ａ３０１では、入力ポート３０２，３０３へのデータの入力がｃｌｋ１ｘを基準とするのに対して、乗算処理や加算処理自体はｃｌｋ２ｘを基準とする。本実施の形態では、このような構成により、入力ポート３０２，３０３に接続される外部回路を、ｃｌｋ１ｘを基準として構成することができ、なおかつ乗算処理や加算処理自体はｃｌｋ２ｘを基準として処理できる。このように、本実施の形態では、外部回路を低い動作周波数で構成できるため、タイミング制約が緩くなり外部回路の設計条件を緩めることができる。
【００３９】
様々な機能拡張が施された近年のＦＰＧＡでは、図３に示した多倍長乗算回路３２３のような乗算処理や加算処理の専用回路がハードマクロとして組み込まれている。一般にこのような専用回路は、高い動作周波数で動作させることができる。一方で、専用回路以外の部分に関してＦＰＧＡの回路を専用回路と同等の動作周波数で動作させることを前提とした場合、タイミング制約が厳しくなるため、複雑な回路を実装することは難しい。本実施の形態は、全体の性能を低下させずに、専用回路部分のみを高い動作周波数で動作させ、それ以外の部分を低い動作周波数で動作させることができるため、効率的な処理が実現できる。
【００４０】
図４は、前述したアルゴリズムの擬似コードのｑ導出処理を行う演算回路の構成の一例を示すブロック図である。
【００４１】
図４に示した演算回路のうち、演算回路Ａ３０１を除いたものは、中間値導出部の一例である。この演算回路において、入力ポート２０５からは、ｓ［ｉ］［１］が入力される。そして、入力レジスタ２０２は、ｃｌｋ１ｘに同期してｓ［ｉ］［１］を取り込む。中間レジスタ２０３は、図３に示した演算回路Ａ３０１の出力ポート３２１からｖ［ｉ］［０］が出力されたタイミングでデータを取り込む。その結果、中間レジスタ２０３にｖ［ｉ］［０］が格納される。加算器２０４は、ｖ［ｉ］［０］＋ｓ［ｉ］［１］の処理を行い、その結果としてｑ［ｉ＋１］を出力する。加算器２０４は、演算回路Ａ３０１の入力ポート３０４に接続されており、入力レジスタ３１２が所定のタイミングで入力ポート３０４からｑ［ｉ＋１］を取り込む。図示していないが、加算器２０４と演算回路Ａ３０１の入力ポート３０４の間にはバッファが設けられており、このバッファが加算器２０４から出力されるｑ［ｉ＋１］に遅延ｄを加えることで、上記タイミングが調整される。その結果、図３に示したように、演算回路Ａ３０１の入力ポート３０４からはｑ［ｉ−ｄ］が入力されることになる。また、演算回路Ａ３０１の出力ポート３２１は、入力ポート３０５を介して入力レジスタ３０８と接続されており、入力レジスタ３０８が出力ポート３２１からｐ［ｉ］［０］が出力されたタイミングで入力ポート３０５からデータを取り込む。その結果、入力レジスタ３０８にｐ［ｉ］［０］が格納される。
【００４２】
上記擬似コードの多倍長乗算処理（２）でｊ＝０の場合のみｖ［ｉ］［０］を算出するように処理するのは、図４に示した演算回路で行う処理を多倍長加算処理（１）の結果を待たずして開始できるからである。これにより、ｑ［ｉ＋１］の導出を高速に行うことができる。ｑ［ｉ＋１］の導出が高速であれば、繰り返し処理である入力処理ａ及び入力処理ｍを連続して行うことができる。逆に、ｑ［ｉ＋１］の導出が遅いと、入力処理ｍを実行しても、乗算対象であるｑ［ｉ＋１］が入力されるまで乗算処理を開始することができず、以降の処理を連続して行うことができなくなってしまう。
【００４３】
図５は、演算回路Ｂ４０１の構成の一例を示すブロック図である。
【００４４】
図５に示した演算回路Ｂ４０１は、前述したアルゴリズムの擬似コードの多倍長加算処理（１）におけるループ処理のうち、ｊ＝０からｊ＝ｔ−１までの処理を行うものである。
【００４５】
図３に示した演算回路Ａ３０１が２ｔ回のループ処理を行うのに対して、図５に示した演算回路Ｂ４０１はｔ回のループ処理を行うことに注意されたい。演算回路Ｂ４０１は、ｃｌｋ１ｘを基準として動作する。このため、演算回路Ｂ４０１は、大部分の回路がｃｌｋ２ｘで動作する演算回路Ａ３０１の半分のループ回数を処理することとなる。
【００４６】
入力ポート４０２は、演算回路Ａ３０１の出力ポート３２１に接続されている。出力ポート３２１から出力されるデータのうち、演算回路Ａ３０１でのループ処理におけるｊの値が偶数のときの出力は、中間レジスタ４０４に格納される。同じくｊの値が奇数のときの出力は、中間レジスタ４０６に格納される。中間レジスタ４０５は、中間レジスタ４０４の出力を格納する。このとき、中間レジスタ４０４と中間レジスタ４０５，４０６は、互いに逆のエッジで動作するレジスタであるとする。つまり、中間レジスタ４０４がｃｌｋ１ｘの立ち上がりで動作するレジスタであるとすれば、中間レジスタ４０５，４０６はｃｌｋ１ｘの立ち下がりで動作するレジスタとなる。このような構成により、中間レジスタ４０５，４０６からは同一のタイミングで、隣り合う中間値を連結した値であるｐ［ｉ］［ｊ＋１］｜ｐ［ｉ］［ｊ］あるいはｕ［ｉ］［ｊ＋１］｜ｕ［ｉ］［ｊ］が出力されることになる。例えば、中間レジスタ４０５がｐ［ｉ］［０］を出力するタイミングでは、中間レジスタ４０６はｐ［ｉ］［１］を出力し、中間レジスタ４０５がｐ［ｉ］［２］を出力するタイミングでは、中間レジスタ４０６はｐ［ｉ］［３］を出力する。また、中間レジスタ４０５がｕ［ｉ］［２］を出力するタイミングでは、中間レジスタ４０６はｕ［ｉ］［３］を出力する。ただし、前述したように、上記擬似コードの多倍長乗算処理（２）ではｊ＝０の場合のみｖ［ｉ］［０］を算出する処理を行う関係上、中間レジスタ４０５がｖ［ｉ］［０］を出力するタイミングでは、中間レジスタ４０６はｕ［ｉ］［１］を出力することに注意されたい。
【００４７】
中間レジスタ４０５，４０６がｐ［ｉ］［ｊ］｜ｐ［ｉ］［ｊ＋１］を出力する場合、ＡＮＤゲート４０７，４０８の出力が０になるようにマスク処理が行われる。よって、加算器４１０，４１１の出力は、ｐ［ｉ］［ｊ］｜ｐ［ｉ］［ｊ＋１］となる。加算器４１０，４１１がｐ［ｉ］［ｊ］｜ｐ［ｉ］［ｊ＋１］を出力するとき、可変シフトレジスタ４１２，４１３は、加算器４１０，４１１の出力を取り込む。その結果、可変シフトレジスタ４１２，４１３にｐ［ｉ］［ｊ］｜ｐ［ｉ］［ｊ＋１］が格納される。次に、中間レジスタ４０５，４０６がｕ［ｉ］［ｊ］｜ｕ［ｉ］［ｊ＋１］を出力する場合、可変シフトレジスタ４１２，４１３は、格納されているｐ［ｉ］［ｊ］｜ｐ［ｉ］［ｊ＋１］を出力する。このとき、ＡＮＤゲート４０７，４０８ではマスク処理が行われず、可変シフトレジスタ４１２，４１３の出力が、ＡＮＤゲート４０７，４０８を介して加算器４１０，４１１に入力される。そして、加算器４１０，４１１は、ｐ［ｉ］［１］＋ｕ［ｉ］［１］あるいは（ｐ［ｉ］［ｊ＋１］｜ｐ［ｉ］［ｊ］）＋（ｕ［ｉ］［ｊ＋１］｜ｕ［ｉ］［ｊ］）＋ｃａｒｒｙ＿１の処理を行う。ここで、ｃａｒｒｙ＿１は出力レジスタ４１６の値である。ｐ［ｉ］［１］＋ｕ［ｉ］［１］の処理が実行される場合は、入力ポート４０３から０が入力され、マルチプレクサ４０９で入力ポート４０３からの０が選択されて加算器４１０に入力される。それ以外の場合は、マルチプレクサ４０９で出力レジスタ４１６の値が選択されて加算器４１０に入力される。加算器４１０，４１１による加算処理の結果であるｖ［ｉ］［ｊ］、ｖ［ｉ］［ｊ＋１］、及び、加算処理時に発生するキャリー値であるｃａｒｒｙ＿１は、それぞれ出力レジスタ４１４〜４１６に格納され、出力ポート４１７〜４１９に出力される。
【００４８】
ここで、可変シフトレジスタ４１２，４１３は、レイテンシが変更可能なシフトレジスタであり、ｔの値によってレイテンシが定められる。例えば、ｔ＝０の場合はレイテンシを１とし、ｔ＝１の場合はレイテンシを２とする。このように、可変シフトレジスタ４１２，４１３は、ｔ＋１のレイテンシを持つように設定する。なお、可変シフトレジスタ４１２，４１３は、ＦＰＧＡが持つ機能の１つであり、ＦＰＧＡ上でこのような機能を実現することは容易である。
【００４９】
図６は、演算回路Ｃ５０１の構成の一例を示すブロック図である。
【００５０】
図６に示した演算回路Ｃ５０１は、前述したアルゴリズムの擬似コードの多倍長加算処理（２）におけるループ処理のうち、ｊ＝０からｊ＝ｔ−１までの処理を行うものである。
【００５１】
図３に示した演算回路Ａ３０１が２ｔ回のループ処理を行うのに対して、図６に示した演算回路Ｃ５０１はｔ回のループ処理を行うことに注意されたい。演算回路Ｃ５０１はｃｌｋ１ｘを基準として動作する。このため、演算回路Ｃ５０１は、大部分の回路がｃｌｋ２ｘで動作する演算回路Ａ３０１の半分のループ回数を処理することとなる。
【００５２】
入力ポート５０２は、図５に示した演算回路Ｂ４０１の出力ポート４１７に接続されている。また、入力ポート５０３は、演算回路Ｂ４０１の出力ポート４１８に接続されている。入力ポート５０２，５０３から入力されるｖ［ｉ］［ｊ＋１］｜ｖ［ｉ］［ｊ］は、可変シフトレジスタ５１２及び可変シフトレジスタ５１３の出力、あるいは、入力ポート５０４から入力されるデータと加算器５１０，５１１で加算処理される。この加算処理は上記擬似コードの（ｖ［ｉ］［ｊ＋１］｜ｖ［ｉ］［ｊ］）＋（ｓ［ｉ］［ｊ＋２］｜ｓ［ｉ］［ｊ＋１］）＋ｃａｒｒｙ＿１の処理に対応する。加算器５１０，５１１は、加算結果ｓ［ｉ＋１］［ｊ］、ｓ［ｉ＋１］［ｊ＋１］、及び、加算処理時に発生するキャリー値であるｃａｒｒｙ＿１を出力する。出力されたデータは、それぞれ出力レジスタ５１４〜５１６に格納される。また、ｓ［ｉ＋１］［ｊ］、ｓ［ｉ＋１］［ｊ＋１］については可変シフトレジスタ５１２，５１３にも格納される。ｉ＝０の処理では、ｓ［ｉ］［０］、・・・、ｓ［ｉ］［ｔ］であるため、加算処理は（ｖ［０］［ｊ＋１］｜ｖ［０］［ｊ］）＋０となる必要がある。そのため、この処理は、ＡＮＤゲート５０６，５０７の出力が０となるようにＡＮＤゲート５０６，５０７が制御され、入力ポート５０５から０が入力され、マルチプレクサ５０８で入力ポート５０５からの０が選択されて加算器５１０に入力される。
【００５３】
次に、加算処理の詳細について述べる。
【００５４】
前述したように、可変シフトレジスタ５１２，５１３には、ｓ［ｉ＋１］［ｊ］、ｓ［ｉ＋１］［ｊ＋１］が格納される。ｔ＝１の場合、ｉ＝０の処理後は、ｓ［１］［０］が可変シフトレジスタ５１２に格納され、ｓ［１］［１］が可変シフトレジスタ５１３に格納される。ｉ＝１の処理時には、加算器５１０への入力としてｓ［１］［１］が必要となり、加算器５１１への入力としてｓ［１］［２］が必要となる。このとき、ｓ［１］［１］は可変シフトレジスタ５１３に格納されているので、ＡＮＤゲート５０６を経由して加算器５１０に入力されるのに対し、ｓ［１］［２］は入力ポート５０４から入力されるものとする。ｓ［１］［１］及びｓ［１］［２］に対する加算処理時に発生するキャリー値は、出力レジスタ５１６に格納された後、出力ポート５１９に出力される。ｉ＝２以降の処理も同様に行われる。
【００５５】
ｔ＝２の場合、ｉ＝０の処理後は、ｓ［１］［０］、ｓ［１］［２］が可変シフトレジスタ５１２に格納され、ｓ［１］［１］、ｓ［１］［３］が可変シフトレジスタ５１３に格納される。ｉ＝１の処理時には、加算器５１０への入力としてｓ［１］［１］、ｓ［１］［３］が必要となり、加算器５１１への入力としてｓ［１］［２］、ｓ［１］［４］が必要となる。このとき、ｔ＝１の場合と同様に、加算器５１０での処理に必要なデータは可変シフトレジスタ５１３に格納されているので、ＡＮＤゲート５０６を経由して加算器５１０に入力される。加算器５１１での処理に必要なデータのうち、ｓ［１］［２］は可変シフトレジスタ５１２に格納されているので、マルチプレクサ５０９及びＡＮＤゲート５０７を経由して加算器５１１に入力されるのに対し、ｓ［１］［４］は入力ポート５０４から入力されるものとする。ｓ［１］［１］及びｓ［１］［２］に対する加算処理時に発生するキャリー値は、出力レジスタ５１６に格納された後、次のｓ［１］［３］及びｓ［１］［４］に対する加算処理に必要なｃａｒｒｙ＿１の値としてマルチプレクサ５０８を経由して加算器５１０に入力される。ｓ［１］［３］及びｓ［１］［４］に対する加算処理時に発生するキャリー値は、出力レジスタ５１６に格納された後、出力ポート５１９に出力される。ｉ＝２以降の処理も同様に行われる。
【００５６】
ｔ＝３以上の場合も、ｔ＝２の場合と同様に、可変シフトレジスタ５１２，５１３に格納済みのｓの値は、前述したように、ＡＮＤゲート５０６を経由して加算器５１０に入力され、加算器５１０は入力されたｓの値を用いて加算処理を行う。そして、可変シフトレジスタ５１２，５１３に格納されていないｓの値は、前述したように、入力ポート５０４から入力され、加算器５１０は入力されたｓの値を用いて加算処理を行う。
【００５７】
次に、図４に示した演算回路と図６に示した演算回路Ｃ５０１の入出力関係について述べる。
【００５８】
図６に示した演算回路Ｃ５０１の出力ポート５１８は図４に示した演算回路の入力ポート２０５に接続する。これによりｑ導出処理、即ち、ｖ［ｉ］［０］＋ｓ［ｉ］［１］の処理に必要なｓ［ｉ］［１］の値を出力ポート５１８に出力されたタイミングで入力レジスタ２０２に格納し、加算器２０４で加算処理することでｑ［ｉ＋１］を導出することができる。
【００５９】
図７は、演算回路Ｄ６０１の構成の一例を示すブロック図である。
【００６０】
図７に示した演算回路Ｄ６０１は、前述したアルゴリズムの擬似コードの多倍長乗算処理（１）及び多倍長乗算処理（２）におけるループ処理のうち、ｊ＝２ｔからｊ＝（４ｔ−１）までの処理を行うものである。ここで、ｔは正の整数（ｔ≠０）とする。この演算回路Ｄ６０１の処理は以下の擬似コード（以下、「擬似コードＤ」という）で表せる。
【００６１】
【数６】
2008176136.tif 000008
【００６２】
ここで、擬似コードＤにおける右辺のｃａｒｒｙ＿ｋは、それぞれ図３に示した演算回路Ａ３０１によるｊ＝２ｔ−１のときの処理で発生したキャリー値であるものとする。以下、擬似コードＤと演算回路Ｄ６０１の各部との対応について説明する。
【００６３】
まず、入力ポート６０２から、擬似コードＤのａ［ｊ］及びａ［ｊ＋１］、もしくは、ｍ［ｊ］及びｍ［ｊ＋１］が同時に入力される。そのため、入力ポート６０２は、２ｋビットのバス幅を持つ。また、入力ポート６０３からは、擬似コードＤのｂ［ｉ］及びｑ［ｉ−ｄ］が入力される。入力ポート６０３は、中間レジスタ６０８，６０９を経由して、乗算器６１４と出力ポート６１６に接続されている。つまり、入力ポート６０３から入力されたデータは、レイテンシを２として乗算器６１４で乗算処理されるとともに、出力ポート６１６に出力される。
【００６４】
入力ポート６０２，６０３では、データを入力する処理が、図３に示した演算回路Ａ３０１と同様に行われる。つまり、入力処理ａと入力処理ｍが、ｃｌｋ２ｘを基準として２ｔサイクルごとに交互に行われる。
【００６５】
マルチプレクサ６１１は、ｃｌｋ２ｘを基準として入力レジスタ６０５と入力レジスタ６０６に格納されたデータを交互に選択する。中間レジスタ６０７には、マルチプレクサ６１１で選択されたデータが格納される。中間レジスタ６０７に入力処理ａのデータが格納されている場合、そのデータと同じタイミングで中間レジスタ６０９からｂ［ｉ］が乗算器６１４に入力される。一方、中間レジスタ６０７に入力処理ｍのデータが格納されている場合、そのデータと同じタイミングで中間レジスタ６０９からｑ［ｉ−ｄ］が乗算器６１４に入力される。
【００６６】
これにより、乗算器６１４では、入力処理ａに対応してｂ［ｉ］・ａ［ｊ］が処理され、入力処理ｍに対応してｑ［ｉ−ｄ］・ｍ［ｊ］が処理される。処理結果は、中間レジスタ６１０に格納される。
【００６７】
次に、加算器６１５では、中間レジスタ６１０に格納された乗算器６１４による乗算処理の結果とｃａｒｒｙ＿ｋとの加算処理を行う。ｊ＝２ｔの場合のみ、ｃａｒｒｙ＿ｋの値として入力ポート６０４から入力される値がマルチプレクサ６１２で選択されて加算器６１５で用いられる。それ以外の場合は、図３に示した演算回路Ａ３０１と同様に、１サイクル前の加算処理で発生したキャリー値がマルチプレクサ６１２で選択されて加算器６１５で用いられる。
【００６８】
以上の処理により、出力ポート６１８には、入力処理ａに対応してｐ［ｉ］［２ｔ］からｐ［ｉ］［４ｔ−１］が出力され、入力処理ｍに対応してｕ［ｉ］［２ｔ］からｕ［ｉ］［４ｔ−１］が出力される。また、出力ポート６１７には、出力ポート６１８に対応したｃａｒｒｙ＿ｋが出力される。出力ポート６１７，６１８には、ｃｌｋ２ｘを基準としてサイクルごとに各データが出力される。
【００６９】
図２に示したように、ｊ＝２ｔからｊ＝（４ｔ−１）までの多倍長加算処理（１）におけるループ処理の回路は、図５に示した演算回路Ｂ４０１と同一の回路を図７に示した演算回路Ｄ６０１に接続して構成する。また、ｊ＝２ｔからｊ＝（４ｔ−１）までの多倍長加算処理（２）におけるループ処理の回路は、さらに、そこに図６に示した演算回路Ｃ５０１と同一の回路を接続して構成する。
【００７０】
さらに、ｊ＝４ｔ以降の処理も２ｔごとに図７に示した演算回路Ｄ６０１、図５に示した演算回路Ｂ４０１、図６に示した演算回路Ｃ５０１を所定の回数分用意して構成する。
【００７１】
図２において、モンゴメリ乗算回路２０１の回路構成のうち、演算回路Ａ３０１及び演算回路Ｄ６０１の大部分（図３の多倍長乗算回路３２３、図７の多倍長乗算回路６１９）と演算回路Ａ３０１の出力を格納する中間レジスタ２０３は、ｃｌｋ２ｘを基準として処理を行い、それ以外の回路は、ｃｌｘ１ｘを基準として処理を行う。そのため、モンゴメリ乗算回路２０１全体における入出力はｃｌｋ１ｘを基準として行われる。これにより、外部回路は低い動作周波数で構成できるため、タイミング制約が緩くなり外部回路の設計条件を緩めることができる。例えば、ＦＰＧＡに組み込まれているメモリに対する読み出し、書き込み処理を外部回路に利用できる。また、演算回路Ａ３０１及び演算回路Ｄ６０１に、近年のＦＰＧＡに機能拡張として組み込まれている乗算処理及び加算処理の専用回路を用いることにより、専用回路が動作可能な高い動作周波数をそのまま活用した処理が可能となり、高速で効率のよい処理が実現できる。
【００７２】
次に、図２に示したモンゴメリ乗算回路２０１全体の動作について説明する。
【００７３】
まず、演算回路Ａ３０１が、図３を用いて説明した処理を開始する。演算回路Ａ３０１がｉ＝０における入力処理ａを完了した後、つまり、処理開始からｃｌｋ２ｘを基準として２ｔサイクル後（ｃｌｋ１ｘを基準とした場合はｔサイクル後）、演算回路Ａ３０１に接続されている演算回路Ｄ６０１が入力処理ａを開始する。同様に、ｃｌｋ２ｘを基準として２ｔサイクルごとに、順次隣の演算回路Ｄ６０１が入力処理ａを開始する。以降、前述したアルゴリズムの擬似コード全体の処理が完了するまで各演算回路が処理を行う。演算結果は、図２の一番左側の演算回路Ｃ５０１により、ｓ［ｎ＋ｄ＋１］［１］｜ｓ［ｎ＋ｄ＋１］［０］からｓ［ｎ＋ｄ＋１］［２ｔ−１］｜ｓ［ｎ＋ｄ＋１］［２ｔ−２］まで順次２ｋビットずつが、ｃｌｋ１ｘを基準としてｔサイクル間出力される。この出力後、続けて右隣の演算回路Ｃ５０１により、ｓ［ｎ＋ｄ＋１］［２ｔ＋１］｜ｓ［ｎ＋ｄ＋１］［２ｔ］からｓ［ｎ＋ｄ＋１］［４ｔ−１］｜ｓ［ｎ＋ｄ＋１］［４ｔ−２］まで順次２ｋビットずつが、ｃｌｋ１ｘを基準としてｔサイクル間出力される。以降、順次隣の演算回路Ｃ５０１により、演算結果が、ｃｌｋ１ｘを基準としてｔサイクル間出力される。また、演算結果として必要なｓ［ｎ＋ｄ］［１］、・・・、ｓ［ｎ＋１］［１］は一番左側の演算回路Ｃ５０１により出力される。
【００７４】
図８は、モンゴメリ乗算回路２０１の動作（剰余演算方法）を示すフローチャートである。
【００７５】
ここで、前述したアルゴリズムの擬似コードにおいて、
被乗数Ａ＝｛Ａｎ＋ｄ，・・・，Ａ１，Ａ０｝（Ａｎ＋ｄ，・・・，Ａｎの各々の値は０）、
乗数Ｂ＝｛Ｂｎ＋ｄ，・・・，Ｂ１，Ｂ０｝（Ｂｎ＋ｄ，・・・，Ｂｎの各々の値を０）、
Ｍ’’’＝＝｛Ｍ０，Ｍ１，・・・，Ｍｎ＋ｄ｝、
中間値Ｑ＝｛Ｑｎ＋ｄ＋１，・・・，Ｑ１，Ｑ０，Ｑ−１，・・・，Ｑ−ｄ｝、
中間結果Ｓ＝｛Ｓｎ＋ｄ＋１，・・・，Ｓ１，Ｓ０｝、
Ａ及びＢの乗算結果Ｐ＝｛Ｐｎ＋ｄ，・・・，Ｐ１，Ｐ０｝、
Ｍ及びＱの乗算結果Ｕ＝｛Ｕｎ＋ｄ，・・・，Ｕ１，Ｕ０｝、
Ｐ及びＵの加算結果Ｖ＝｛Ｖｎ＋ｄ，・・・，Ｖ１，Ｖ０｝とする。
【００７６】
モンゴメリ乗算回路２０１（剰余演算装置）は、Ｓ０の値を０に設定し、例えばメモリに格納しておく（ステップＳ１０１）。また、モンゴメリ乗算回路２０１は、Ｑ０，Ｑ−１，・・・，Ｑ−ｄの各々の値を０に設定し、例えばメモリに格納しておく（ステップＳ１０２）。
【００７７】
モンゴメリ乗算回路２０１は、カウンタｉを０に設定してループ処理を開始する（ステップＳ１０３）。
【００７８】
演算回路Ａ３０１及び演算回路Ｄ６０１（多倍長乗算部）は、所定の動作周波数ｃｌｋ１ｘの２倍の動作周波数ｃｌｋ２ｘにて、ｉ回目の処理で、ＡとＢｉとの乗算処理を乗算器３１６，６１４で行い、その乗算結果Ｐｉを出力する（ステップＳ１０４：多倍長乗算ステップの一部）。また、演算回路Ａ３０１及び演算回路Ｄ６０１は、２倍の動作周波数ｃｌｋ２ｘにて、ｉ回目の処理で、Ｍ’’’とＱｉ−ｄとの乗算処理を乗算器３１６，６１４で行い、その乗算結果Ｕｉを出力する（ステップＳ１０５：多倍長乗算ステップの一部）。このステップＳ１０５において、演算回路Ａ３０１及び演算回路Ｄ６０１は、後述するように、ｉ−１回目の処理のステップＳ１０８で出力されるＱｉを遅延させたＱｉ−ｄを用いて、Ｍ’’’とＱｉ−ｄとの乗算処理を行う。本実施の形態では、ステップＳ１０５において、演算回路Ａ３０１は、ｉ回目の処理で、Ｍ’’’の最初のｋビットとＱｉ−ｄとの乗算処理を行った後、その乗算結果とステップＳ１０４で出力したＰｉの最初のｋビットとの加算処理を加算器３１７で行い、その加算結果をＶｉの最初のｋビットとして出力する。
【００７９】
演算回路Ｂ４０１（多倍長加算部）は、所定の動作周波数ｃｌｋ１ｘにて、ｉ回目の処理で、ステップＳ１０４で出力されたＰｉとステップＳ１０５で出力されたＵｉとの加算処理を加算器４１０，４１１で行い、その加算結果Ｖｉを出力する（ステップＳ１０６：多倍長加算ステップの一部）。その後、演算回路Ｃ５０１（多倍長加算部）は、１回目の処理では、ステップＳ１０６で出力されたＶ０とステップＳ１０１でメモリに格納されたＳ０との加算処理を加算器５１０，５１１で行い、その加算結果をＳ１として出力する。また、演算回路Ｃ５０１は、２回目以降のｉ回目の処理では、ステップＳ１０６で出力されたＶｉとｉ−１回目の処理で出力したＳｉとの加算処理を加算器５１０，５１１で行い、その加算結果をＳｉ＋１として出力する（ステップＳ１０７：多倍長加算ステップの一部）。本実施の形態では、ステップＳ１０７において、演算回路Ｃ５０１は、ｉ回目の処理で、ＶｉとＳｉとの加算処理を行った後、Ｓｉ＋１を可変シフトレジスタ５１２，５１３に格納し、ｔの大きさに合わせてタイミングを調整した上で、可変シフトレジスタ５１２，５１３からＳｉ＋１を出力する。
【００８０】
図４に示した演算回路（中間値導出部）は、ｉ回目の処理で、ステップＳ１０５で出力されたＶｉの最初のｋビットとステップＳ１０７で出力されたＳｉの２番目のｋビットとの加算処理を加算器２０４で行い、その加算結果をＱｉ＋１として出力する（ステップＳ１０８：中間値導出ステップ）。ここで、図４に示した演算回路は、ステップＳ１０６で出力されたＶｉを用いて、Ｖｉの最初のｋビットとＳｉの２番目のｋビットとの加算処理を行ってもよい。この場合、ステップＳ１０５において、演算回路Ａ３０１はＶｉの最初のｋビットを演算しなくてもよい。
【００８１】
モンゴメリ乗算回路２０１は、カウンタｉがｎ＋ｄになるまで、ｉを１ずつインクリメントし、上記処理をｎ＋ｄ＋１回繰り返す（ステップＳ１０９）。
【００８２】
演算回路Ｃ５０１（剰余演算部）は、ループ処理が終了した後、直前（即ち、ｎ＋ｄ＋１回の処理）のステップＳ１０７で出力されたＳｎ＋ｄ＋１とそれより前のｄ回の処理（時間的に逆の順でいえば、ｎ＋ｄ回目からｎ＋１回目まで）のステップＳ１０７で出力されたＳｎ＋ｄからＳｎ＋１までの各々の２番目のｋビットとを連結する。そして、連結されたビット列をＳｎ＋ｄ＋２≡ＡＢＲ−１ｍｏｄ（Ｍ）とし、これを利用してモンゴメリ乗算による剰余演算を行う（ステップＳ１１０：剰余演算ステップ）。
【００８３】
以上のように、本実施の形態に係る剰余演算装置は、多倍長乗算処理と多倍長加算処理を分離し、多倍長乗算処理は多倍長加算処理の２倍の動作周波数で実行されることを特徴とする。
【００８４】
前記剰余演算装置は、多倍長加算処理において、各サイクルあたりに処理するビット長が多倍長乗算処理の２倍の長さであることを特徴とする。
【００８５】
前記剰余演算装置は、多倍長乗算処理は図３及び図７に示した回路構成を持つことを特徴とする。
【００８６】
前記剰余演算装置は、多倍長加算処理は図５及び図６に示した回路構成を持つことを特徴とする。
【００８７】
前記剰余演算装置は、多倍長加算処理のうち、最初のｋビットの処理のみ多倍長乗算処理用の回路で行い、多倍長乗算処理で必要な中間値の導出を高速化することを特徴とする。
【００８８】
前記剰余演算装置は、多倍長加算処理用の回路において、多倍長加算処理の結果を可変シフトレジスタに格納し、格納した値を多倍長加算処理に必要なタイミングで可変シフトレジスタから出力することで、任意のループ回数に対応することを特徴とする。つまり、本実施の形態に係る剰余演算装置では、入力データのビット長に合わせてループ回数を調整することが可能である。
【図面の簡単な説明】
【００８９】
【図１】ＦＰＧＡを用いたセキュリティチップの構成を示すブロック図である。
【図２】モンゴメリ乗算回路の構成を示すブロック図である。
【図３】多倍長乗算処理（１）及び多倍長乗算処理（２）を行う演算回路Ａの構成の一例を示すブロック図である。
【図４】ｑ導出処理を行う演算回路の構成の一例を示すブロック図である。
【図５】多倍長加算処理（１）を行う演算回路Ｂの構成の一例を示すブロック図である。
【図６】多倍長加算処理（２）を行う演算回路Ｃの構成の一例を示すブロック図である。
【図７】多倍長乗算処理（１）及び多倍長乗算処理（２）を行う演算回路Ｄの構成の一例を示すブロック図である。
【図８】モンゴメリ乗算回路の動作を示すフローチャートである。
【符号の説明】
【００９０】
１０１  セキュリティチップ、１０２  ＣＰＵ、１０３  内部メモリ、１０４  外部インタフェース、１０５  暗号処理回路用メモリ、２０１  モンゴメリ乗算回路、２０２  入力レジスタ、２０３  中間レジスタ、２０４  加算器、２０５  入力ポート、３０１  演算回路Ａ、３０２，３０３，３０４，３０５  入力ポート、３０６，３０７  マルチプレクサ、３０８，３０９，３１０，３１１，３１２  入力レジスタ、３１３，３１４，３１５  中間レジスタ、３１６  乗算器、３１７  加算器、３１８  マルチプレクサ、３１９，３２０，３２１  出力ポート、３２２  出力レジスタ、３２３  多倍長乗算回路、４０１  演算回路Ｂ、４０２，４０３  入力ポート、４０４，４０５，４０６  中間レジスタ、４０７，４０８  ＡＮＤゲート、４０９  マルチプレクサ、４１０，４１１  加算器、４１２，４１３  可変シフトレジスタ、４１４，４１５，４１６  出力レジスタ、４１７，４１８  出力ポート、５０１  演算回路Ｃ、５０２，５０３，５０４，５０５  入力ポート、５０６，５０７  ＡＮＤゲート、５０８，５０９  マルチプレクサ、５１０，５１１  加算器、５１２，５１３  可変シフトレジスタ、５１４，５１５，５１６  出力レジスタ、５１７，５１８，５１９，５２０  出力ポート、６０１  演算回路Ｄ、６０２，６０３，６０４  入力ポート、６０５，６０６  入力レジスタ、６０７，６０８，６０９，６１０  中間レジスタ、６１１，６１２  マルチプレクサ、６１３  出力レジスタ、６１４  乗算器、６１５  加算器、６１６，６１７，６１８  出力ポート、６１９  多倍長乗算回路。
【図１】
2008176136.tif 000009
【図２】
2008176136.tif 000010
【図３】
2008176136.tif 000011
【図４】
2008176136.tif 000012
【図５】
2008176136.tif 000013
【図６】
2008176136.tif 000014
【図７】
2008176136.tif 000015
【図８】
2008176136.tif 000016