(57)【要約】      （修正有）【課題】ｎビットモンゴメリ乗算剰余を用いたｎビットの整数倍のビット数のモンゴメリ乗算剰余の算出に要する演算時間を短縮する演算処理方法を提供する。【解決手段】ＣＰＵと、ＣＰＵの命令によりｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算を切り換えて行う演算器と、メモリと、を備えた演算処理装置において、ｎビットの整数倍のビット数のモンゴメリ乗算剰余を算出する演算処理方法は、ＣＰＵが、メモリから読み出したプログラムに基づき、ｎビットモンゴメリ乗算剰余、又はｎビット乗算のどちらか一方の演算方法を選択するステップＳ１０３と、ＣＰＵが、選択した演算方法による演算を演算器に実行させるステップＳ１０４、又はＳ１０５と、を有する。【選択図】図３
2020140120.tif 000002
【特許請求の範囲】
【請求項１】
ＣＰＵと、
前記ＣＰＵの命令によりｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算を切り換えて行う演算器と、
メモリと、
を備えた演算処理装置において、ｎビットの整数倍のビット数のモンゴメリ乗算剰余を算出する演算処理方法であって、
前記ＣＰＵが、前記メモリから読み出したプログラムに基づき、ｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算から演算方法を選択する第１ステップと、
前記ＣＰＵが、選択した前記演算方法による演算を前記演算器に実行させる第２ステップと、
を有する、
演算処理方法。
【請求項２】
請求項１に記載の演算処理方法において、
前記第１ステップでは、前記ＣＰＵは、ｎビットモンゴメリ乗算剰余の算出を含むマルチ演算を実行するとき、ｎビットモンゴメリ乗算剰余の算出を前記演算方法として選択し、乗算を実行するとき、ｎビット乗算を前記演算方法として選択する、
演算処理方法。
【請求項３】
請求項１に記載の演算処理方法において、
前記演算器は、ｎビットモンゴメリ乗算剰余の算出、ｎビット乗算、及び加減算を切り換えて行い、
第１ステップでは、前記ＣＰＵが、前記メモリから読み出したプログラムに基づき、ｎビットモンゴメリ乗算剰余の算出、ｎビット乗算、及び加減算から前記演算方法を選択する、
演算処理方法。
【請求項４】
請求項１に記載の演算処理方法において、
前記演算器は、ｎビットモンゴメリ乗算剰余の算出を行う第１演算器と、ｎビット乗算を行う第２演算器と、が独立して設けられており、
前記ＣＰＵは、前記第１ステップにおいてｎビットモンゴメリ乗算剰余の算出を選択した場合、前記第２ステップにおいて前記第１演算器による演算を実行させ、前記第１ステップにおいてｎビット乗算を選択した場合、前記第２ステップにおいて前記第２演算器による演算を実行させる、
演算処理方法。
【請求項５】
請求項４に記載の演算処理方法において、
前記ＣＰＵは、前記第１ステップにおいてｎビットモンゴメリ乗算剰余の算出及びｎビット乗算を選択した場合、前記第２ステップにおいて前記第１演算器による演算と前記第２演算器による演算とを並行して実行させる、
演算処理方法。
【請求項６】
請求項１に記載の演算処理方法において、
前記ＣＰＵは、２ｎビット又は３ｎビットモンゴメリ乗算剰余を算出する、
演算処理方法。
【請求項７】
ＣＰＵと、
前記ＣＰＵの命令によりｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算を切り換えて行う演算器と、
メモリと、
を備え、
前記ＣＰＵは、前記メモリから読み出したプログラムに基づき、ｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算を選択して前記演算器に実行させ、ｎビットの整数倍のビット数のモンゴメリ乗算剰余を算出する、
演算処理装置。
【請求項８】
請求項７に記載の演算処理装置において、
前記ＣＰＵは、ｎビットモンゴメリ乗算剰余の算出を含むマルチ演算を実行するとき、ｎビットモンゴメリ乗算剰余の算出を選択して前記演算器に実行させ、乗算を実行するとき、ｎビット乗算を選択して前記演算器に実行させる、
演算処理装置。
【請求項９】
請求項７に記載の演算処理装置において、
前記演算器は、前記ＣＰＵの命令によりｎビットモンゴメリ乗算剰余の算出、ｎビット乗算、及び加減算を切り換えて行う、
演算処理装置。
【請求項１０】
請求項７に記載の演算処理装置において、
前記演算器は、ｎビットモンゴメリ乗算剰余の算出を行う第１演算器と、ｎビット乗算を行う第２演算器と、が独立して設けられている、
演算処理装置。
【請求項１１】
請求項１０に記載の演算処理装置において、
前記ＣＰＵは、前記第１演算器におけるｎビットモンゴメリ乗算剰余の算出と、前記第２演算器におけるｎビット乗算とを並行して実行させる、
演算処理装置。
【請求項１２】
請求項７に記載の演算処理装置において、
前記ＣＰＵは、２ｎビット又は３ｎビットモンゴメリ乗算剰余を算出する、
演算処理装置。
【請求項１３】
ＣＰＵと、
前記ＣＰＵの命令によりｎビット乗算を切り換えて行う演算器と、
メモリと、
を備え、
前記ＣＰＵは、前記メモリから読み出したプログラムに基づき、ｎビット乗算を選択して前記演算器に実行させ、ｎビットの整数倍のビット数のモンゴメリ乗算剰余を算出し、
前記ＣＰＵは、複数回の乗算を含むマルチ演算を実行するとき、及び１回のみの乗算を実行するときのいずれにおいても、ｎビット乗算を選択して前記演算器に実行させる、
演算処理装置。
【請求項１４】
請求項１３に記載の演算処理装置において、
前記ＣＰＵは、２ｎビット又は３ｎビットモンゴメリ乗算剰余を算出する、
演算処理装置。
【請求項１５】
請求項７に記載の演算処理装置を備えた、
半導体装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理方法、演算処理装置、及び半導体装置に関する。
【背景技術】
【０００２】
暗号処理分野では、乗算剰余の算出処理が行われる。例えば、非特許文献１〜３には、モンゴメリ乗算剰余について開示されている。非特許文献１には、モンゴメリ乗算剰余の基本的な内容が開示されている。非特許文献１によれば、モンゴメリ乗算剰余の算出には、数回の乗算とシフト演算とが組み合わされる旨記載されている。モンゴメリ乗算剰余は、除算を必要とせず、他の乗算剰余アルゴリズムと比べて極めて高速で実行することが可能である。このため、モンゴメリ乗算剰余は、暗号処理分野において広く利用されている。
【０００３】
非特許文献２〜３には、ｎビットモンゴメリ乗算剰余を用いて、２ｎビットモンゴメリ乗算剰余を算出する方法が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Montgomery, Peter L. "Modular multiplication without trial division." Mathematics of computation 44.170 (1985): 519-521.
【非特許文献２】Yoshino, Masayuki, Katsuyuki Okeya, and Camille Vuillaume. "Montgomery multiplication with twice the bit-length of multipliers." IEICE transactions on fundamentals of electronics, communications and computer sciences 91.1 (2008): 203-210.
【非特許文献３】Yoshino, Masayuki, Katsuyuki Okeya, and Camille Vuillaume. "Recursive Double-Size Modular Multiplications from Euclidean and Montgomery Multipliers." IEICE transactions on fundamentals of electronics, communications and computer sciences 93.1 (2010): 180-187.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、従来の暗号処理における、ｎビットモンゴメリ乗算剰余を用いた２ｎビットモンゴメリ乗算剰余の算出方法について説明する。図１６は、暗号処理を行う従来の演算処理装置の構成の一例を示す図である。演算処理装置１００１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０、演算器１０２０、メモリ３０を備えている。ＣＰＵ１０は、メモリ３０に保持されたプログラムを読み出し、プログラムに基づく命令を演算器１０２０に送信する。また、ＣＰＵ１０は、演算器１０２０における演算に必要なデータを、メモリ３０から読み出し演算器１０２０に送信する。
【０００６】
演算器１０２０は、ＣＰＵ１０から受信した命令及びデータに基づき、モンゴメリ乗算剰余算出の演算等を含むマルチ演算（ＭｕｌｔＭｏｎＤｉｖ）を行う。
【０００７】
メモリ３０は、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等を備え、ＣＰＵ１０で実行するプログラムや、ＣＰＵ１０や演算器１０２０における演算結果、演算処理装置１００１の設定情報等のデータを保持する。
【０００８】
図１７は、従来の暗号処理における２ｎビットモンゴメリ乗算剰余の算出に係るアルゴリズムを示す図である。図１８は、マルチ演算のアルゴリズムを示す図である。図１９は、図１７のアルゴリズムに対応するフロー図である。図１７、図１９に示すように、２ｎビットモンゴメリ乗算剰余の算出には、それぞれの入力値に対し、６回のマルチ演算（Ｓｔｅｐ１〜Ｓｔｅｐ６）が順次実行される。そして、各Ｓｔｅｐにおける演算結果を用いて、２ｎビットモンゴメリ乗算剰余が出力値（Ｏｕｔｐｕｔ）として算出される。なお、図１９における各ステップを示す符号は、後述する図３等と対応している。
【０００９】
図１８に示すように、それぞれのマルチ演算（ＭｕｌｔＭｏｎＤｉｖ）では、例えば「ｘ」、「ｙ」、「ｗ」を入力とし、「ｑ」、「ｒ」が出力される。図１８に示すように、それぞれのマルチ演算では、１行目及び４行目において、ｎビットモンゴメリ乗算剰余の算出（ＭｕｌｔＭｏｎ）が行われる。すなわち、２ｎビットモンゴメリ乗算（２ｎビットモンゴメリ乗算剰余）の算出には、１２回のｎビットモンゴメリ乗算剰余の算出を行う必要がある。
【００１０】
図２０は、ｎビットモンゴメリ乗算剰余の算出に係る演算量と、ｎビット乗算に係る演算量とを比較する図である。図２０に示すように、ｎビットモンゴメリ乗算剰余の算出に要する演算量は、ｎビット乗算に要する演算量よりも多く、ｎビットモンゴメリ乗算剰余の算出には、ｎビット乗算の１．５倍以上の演算時間が必要となる。そうすると、２ｎビットモンゴメリ乗算剰余の算出には、ｎビット乗算の１８倍以上の演算時間が必要となる。
【００１１】
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１２】
本明細書には、複数の実施の形態の演算処理方法等が記載されているが、一実施の形態の演算処理方法を述べると、次の通りである。演算処理方法は、ＣＰＵと、ＣＰＵの命令によりｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算を切り換えて行う演算器と、メモリと、を備えた演算処理装置において、ｎビットの整数倍のビット数のモンゴメリ乗算剰余を算出する演算処理方法である。演算処理方法は、ＣＰＵが、メモリから読み出したプログラムに基づき、ｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算から演算方法を選択する第１ステップと、ＣＰＵが、選択した演算方法による演算を演算器に実行させる第２ステップと、を有する。
【発明の効果】
【００１３】
一実施の形態によれば、ｎビットモンゴメリ乗算剰余を用いたｎビットの整数倍のビット数のモンゴメリ乗算剰余の算出に要する演算時間を短縮することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の実施の形態１に係る演算処理装置の構成の一例を示す図である。
【図２】図２は、本発明の実施の形態１に係る２ｎビットモンゴメリ乗算剰余算出のアルゴリズムを例示する図である。
【図３】図３は、図２のアルゴリズムに対応するフロー図である。
【図４】図４は、本発明の実施の形態１の変形例に係る２ｎビットモンゴメリ乗算剰余算出のアルゴリズムを例示する図である。
【図５】図５は、図４のアルゴリズムに対応するフロー図である。
【図６】図６は、本発明の実施の形態２に係る演算処理装置の構成の一例を示す図である。
【図７】図７は、本発明の実施の形態３に係る３ｎビットモンゴメリ乗算剰余算出のアルゴリズムを例示する図である。
【図８】図８は、図７のアルゴリズムに対応するフロー図である。
【図９】図９は、本発明の実施の形態４に係る演算処理装置の構成の一例を示す図である。
【図１０】図１０は、本発明の実施の形態４におけるマルチ演算とｎビット乗算とを並列実行させる手順の一例を示す図である。
【図１１】図１１は、本発明の実施の形態４におけるマルチ演算とｎビット乗算とを並列実行させる手順の他の例を示す図である。
【図１２】図１２は、本発明の実施の形態５に係る演算処理装置の構成の一例を示す図である。
【図１３】図１３は、本発明の実施の形態５に係るマルチ演算のアルゴリズムを例示する図である。
【図１４】図１４は、図１３のアルゴリズムに対応するフロー図である。
【図１５】図１５は、図１３のアルゴリズムに対応するフロー図である。
【図１６】図１６は、暗号処理を行う従来の演算処理装置の構成の一例を示す図である。
【図１７】図１７は、従来の暗号処理における２ｎビットモンゴメリ乗算剰余の算出に係るアルゴリズムを示す図である。
【図１８】図１８は、マルチ演算のアルゴリズムを示す図である。
【図１９】図１９は、図１７のアルゴリズムに対応するフロー図である。
【図２０】図２０は、ｎビットモンゴメリ乗算剰余の算出に係る演算量と、ｎビット乗算に係る演算量とを比較する図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するためのすべての図において、同一部分には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００１６】
（実施の形態１）
本実施の形態では、ｎビットモンゴメリ乗算剰余の算出を含むマルチ演算（ＭｕｌｔＭｏｎＤｉｖ）と、ｎビット乗算とを、ＣＰＵが適宜選択することにより、２ｎビットモンゴメリ乗算剰余の算出が行われる。
【００１７】
＜演算処理装置の構成＞
図１は、本発明の実施の形態１に係る演算処理装置の構成の一例を示す図である。図１は図１６に類似しており、演算器１０２０が演算器２０に置き換えられている点が異なる。演算器２０は、ＣＰＵ１０の命令により、ｎビットモンゴメリ乗算剰余の算出（ＭｕｌｔＭｏｎ）と、ｎビット乗算とを切り換えて実行する。
【００１８】
図２は、本発明の実施の形態１に係る２ｎビットモンゴメリ乗算剰余算出のアルゴリズムを例示する図である。本実施の形態における２ｎビットモンゴメリ乗算剰余算出には、図２に示すＳｔｅｐ１〜Ｓｔｅｐ６等の演算処理が実行される。図２に示すように、Ｓｔｅｐ１、Ｓｔｅｐ２、Ｓｔｅｐ４、Ｓｔｅｐ６ではｎビット乗算が実行され、Ｓｔｅｐ３、Ｓｔｅｐ５ではｎビットモンゴメリ乗算剰余の算出や加減算を含むマルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。
【００１９】
具体的に説明すると、図２のアルゴリズムでは、Ａ＝ａ１ｍ＋ａ０、Ｂ＝ｂ１ｍ＋ｂ０、Ｎ＝ｎ１ｍ＋ｎ０を入力として、２ｎビットの各値｛ｒ０、ｑ０｝、｛ｒ１、ｑ１｝、（ｑ２、ｒ２）、｛ｒ３、ｑ３｝、（ｑ４、ｒ４）、｛ｒ５、ｑ５｝が算出される。なお、ｍ：＝２ｎ、Ｍ：＝ｍ２＝２２ｎである。ａ１、ｂ１、ｎ１は各値（Ａ、Ｂ、Ｎ）における上位ビット（ｎビット）、ａ０、ｂ０、ｎ０は各値（Ａ、Ｂ、Ｎ）における下位ビット（ｎビット）を示している。また、ｒは算出された各値の上位ビット（ｎビット）であり、ｑは算出された各値の下位ビット（ｎビット）を示している。
【００２０】
Ｓｔｅｐ１では、［ａ１、ｂ１］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ０、ｑ０｝が算出される。Ｓｔｅｐ２では、［ａ１＋ａ０、ｂ１＋ｂ０］を入力として、これらの乗算が算出される。これにより、２ｎビットの値｛ｒ１、ｑ１｝が算出される。Ｓｔｅｐ３では、［ａ０、ｂ０、ｎ０］を入力として、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。これにより、２ｎビットの値（ｑ２、ｒ２）が算出される。
【００２１】
Ｓｔｅｐ４では、［ｑ２、ｎ１］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ３、ｑ３｝が算出される。Ｓｔｅｐ５では、［−ｑ０＋ｑ１＋ｒ２−ｑ３、１、ｎ０］を入力として、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。これにより、２ｎビットの値（ｑ４、ｒ４）が算出される。Ｓｔｅｐ６では、［ｑ４、ｎ１］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ５、ｑ５｝が算出される。
【００２２】
そして、これらの演算結果を用いて、以下の式（１）により、２ｎビットモンゴメリ乗算剰余が出力値として算出される。
【００２３】
Ａ＊Ｂ＊Ｍ−１（ｍｏｄ Ｎ）＝（ｒ０＋ｒ３−ｒ５）ｍ＋（ｑ０−ｒ０＋ｒ１−ｒ２＋ｑ３−ｒ３＋ｒ４−ｑ５）    ・・・（１）
＜演算処理方法＞
図３は、図２のアルゴリズムに対応するフロー図である。図３のフロー図は、ステップＳ１０１〜Ｓ１０８を含む。ステップＳ１０１では、ＣＰＵ１０は、メモリ３０に対してカウント値の初期化を実行し、カウント値を「１」に設定する。ここで、カウント値とは、図２のアルゴリズムにおける処理の進捗状況を識別する値である。詳しくは後述するが、各Ｓｔｅｐの処理が完了するごとに、カウント値が更新される。例えば、カウント値が「４」に設定されていれば、図２における処理がＳｔｅｐ３まで完了していることが示される。
【００２４】
ステップＳ１０２では、図２の各Ｓｔｅｐに対応する入力値の準備が行われる。ＣＰＵ１０は、メモリ３０から読み出したプログラムに基づき、各Ｓｔｅｐの入力値を作成する。例えば、Ｓｔｅｐ１であれば、ＣＰＵ１０は、入力値［ａ１、ｂ１］を作成する。また、Ｓｔｅｐ２、５では、ＣＰＵ１０は、加減算を行って入力値を作成する。
【００２５】
ステップＳ１０３では、カウント値に応じて、演算方法が選択される。具体的に述べると、カウント値が「３、５」の場合（Ｙｅｓ）、ＣＰＵ１０は、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）、すなわちｎビットモンゴメリ乗算剰余の算出を選択し、ステップＳ１０４の処理が実行される。一方、カウント値がそれ以外の値である場合（Ｎｏ）、ＣＰＵ１０は、乗算を選択し、ステップＳ１０５の処理が実行される。
【００２６】
ＣＰＵ１０は、ステップＳ１０２で作成した入力値を送信するとともに、選択した演算方法を実行するため、演算器２０に演算方法を命令する。
【００２７】
例えば、Ｓｔｅｐ１では、カウント値が「１」に設定されているので、ＣＰＵ１０は、乗算を選択する。そして、ＣＰＵ１０は、入力値［ａ１、ｂ１］を送信し、演算器２０に乗算を行うよう命令する。
【００２８】
ステップＳ１０５では、演算器２０は、ＣＰＵ１０からの命令に従い、受信した入力値を用いた乗算を行う。例えば、Ｓｔｅｐ１では、演算器２０は、入力値［ａ１、ｂ１］を用いたｎビット乗算を行い、２ｎビットの値｛ｒ０、ｑ０｝を算出する。算出された値は、メモリ３０に保持される。
【００２９】
ステップＳ１０４では、演算器２０におけるｎビットモンゴメリ乗算剰余の算出や、ＣＰＵ１０による加減算等の処理が実行される。ステップＳ１０４は、図３に示すように、ステップＳ１０４ａ〜Ｓ１０４ｃを有する。
【００３０】
ステップＳ１０４ａでは、図１８の１行目に対応するｎビットモンゴメリ乗算剰余の算出が行われる。ＣＰＵ１０は、読み出したプログラムに基づき、演算器２０に対し、ｎビットモンゴメリ乗算剰余の算出を行うよう命令し、図１８に示す入力値［ｘ、ｙ、ｗ］を送信する。入力値は、図２のＳｔｅｐ３では［ａ０、ｂ０、ｎ０］であり、Ｓｔｅｐ５では［−ｑ０＋ｑ１＋ｒ２−ｑ３、１、ｎ０］である。ＣＰＵ１０の命令に基づき、演算器２０は、入力された値を用いてｎビットモンゴメリ乗算剰余の算出を行い、出力値の上位ビットの値ｒを算出する。ここで算出された値ｒは、メモリ３０に保持される。
【００３１】
ステップＳ１０４ｂでは、図１８の４行目に対応するｎビットモンゴメリ乗算剰余の算出が行われる。なお、ステップＳ１０４ｂの入力となる図１８の２〜３行目の演算は、例えばＣＰＵ１０において実行される。ＣＰＵ１０は、プログラムに基づき、演算器２０に対し、ｎビットモンゴメリ乗算剰余の算出を行うよう命令し、図１８の２〜３行目に対応する値等を入力値として送信する。演算器２０は、入力された値を用いてｎビットモンゴメリ乗算剰余の算出を行い、出力値の下位ビットの算出用の値ｒ’を算出する。
【００３２】
そして、ステップＳ１０４ｃにおいて、ＣＰＵ１０は、図１８の６〜８行目に対応する加算等の各演算を行い、出力値の下位ビットの値ｑを算出する。そして、ＣＰＵ１０は、出力値として２ｎビットの値（ｑ、ｒ）を作成する。算出された値は、メモリ３０に保持される。
【００３３】
例えば、Ｓｔｅｐ３において、ＣＰＵ１０は、演算器２０に対し入力値［ａ０、ｂ０、ｎ０］に基づくｎビットモンゴメリ乗算剰余の算出を２回実行させ、加算等の演算を行って２ｎビットの値（ｑ２、ｒ２）を算出する。また、Ｓｔｅｐ５において、ＣＰＵ１０は、演算器２０に対し入力値［−ｑ０＋ｑ１＋ｒ２−ｑ３、１、ｎ０］に基づくｎビットモンゴメリ乗算剰余の算出を２回実行させ、加算等の演算を行って２ｎビットの値（ｑ４、ｒ４）を算出する。
【００３４】
ステップＳ１０６では、カウント値が「６」であるかどうかが判定される。ＣＰＵ１０は、カウント値が「６」でないと判定した場合（Ｎｏ）、ステップＳ１０７において、カウント値を「＋１」加算する処理を行う。例えば、Ｓｔｅｐ１の処理が行われた場合、ＣＰＵ１０は、カウント値を１＋１＝２に更新し、更新したカウント値をメモリ３０に保持させる。そして、ステップＳ１０２に戻り、Ｓｔｅｐ２以降の処理が続いて実行される。
【００３５】
一方、ステップＳ１０６において、ＣＰＵ１０は、カウント値が「６」であると判定した場合（Ｙｅｓ）、Ｓｔｅｐ１〜Ｓｔｅｐ６の処理がすべて完了したと判断し、ステップＳ１０８の処理が実行される。ステップＳ１０８では、ＣＰＵ１０は、Ｓｔｅｐ１〜Ｓｔｅｐ６における演算結果を用いて出力値を算出する。ＣＰＵ１０は、メモリ３０に保持された各演算結果の値を読み出し、式（１）に示す２ｎビットモンゴメリ乗算剰余を出力値として算出する。算出された出力値は、メモリ３０に保持されてもよいし、外部に送信されてもよい。
【００３６】
＜本実施の形態による主な効果＞
本実施の形態によれば、ＣＰＵ１０は、メモリ３０から読み出したプログラムに基づき、ｎビットモンゴメリ乗算剰余の算出、又はｎビット乗算を選択して演算器に実行させる。
【００３７】
この構成によれば、演算時間が長いｎビットモンゴメリ乗算剰余を含むマルチ演算の回数を削減し、演算時間が短い乗算が用いられるので、ｎビットモンゴメリ乗算剰余を用いた２ｎビットモンゴメリ乗算剰余の算出に係る演算時間を短縮することが可能となる。
【００３８】
削減される演算時間は、ｎビット乗算とｎビットモンゴメリ乗算剰余における演算時間の差によって決まる。具体的に述べると、ｎビット乗算に対してｎビットモンゴメリ乗算剰余の演算時間が遅いほど効果が大きくなる。ｎビットモンゴメリ乗算剰余がｎビット乗算に対してｋ倍の時間が掛かるとした場合、２ｎビットモンゴメリ乗算剰余の演算時間は、次の通りとなる。ｋ＝３の場合、本実施の形態における演算時間は、従来の約４４．４％となる。ｋ＝２の場合、本実施の形態における演算時間は、従来の約５０％となる。ｋ＝１．５の場合、本実施の形態における演算時間は、従来の約５５．６％となる。ｋ＝１の場合、本実施の形態における演算時間は、従来の約６６．７％となる。このように、ｎビットモンゴメリ乗算剰余の演算時間がｎビット乗算の演算時間より長くなると、２ｎビットモンゴメリ乗算剰余の演算時間の削減効果はより大きくなる。
【００３９】
［変形例］
２ｎビットモンゴメリ乗算剰余の算出は、図２以外のアルゴリズムでも可能である。そこで、ここでは、図２以外のアルゴリズムを変形例として例示する。図４は、本発明の実施の形態１の変形例に係る２ｎビットモンゴメリ乗算剰余算出のアルゴリズムを例示する図である。図４のＳｔｅｐ１〜Ｓｒｅｐ５は、図２と同じであるが、図４のＳｔｅｐ６がマルチ演算に置き換えられている。図５は、図４のアルゴリズムに対応するフロー図である。
【００４０】
図４のＳｔｅｐ６では、［ｑ４、ｎ１、ｍ−１］を入力として、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。これにより、２ｎビットの値（ｑ５、ｒ５）が算出される。出力値である２ｎビット乗算剰余は、すでに述べた式（１）を用いて算出される。
【００４１】
図５は、図３に対し、ステップＳ１０３の処理内容のみが異なる。図４に示すように、Ｓｔｅｐ６においてもマルチ演算が実行される。このため、ステップＳ１０３では、カウント値が「３、５、６」の場合（Ｙｅｓ）、ＣＰＵ１０は、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）を選択し、ステップＳ１０４の処理が実行される。一方、カウント値がそれ以外の値「１、２、４」である場合（Ｎｏ）、ＣＰＵ１０は、乗算を選択し、ステップＳ１０５の処理が実行される。
【００４２】
本変形例においても、従来の演算方法に比べて２ｎビットモンゴメリ乗算剰余の演算時間を削減することが可能である。
【００４３】
（実施の形態２）
次に、実施の形態２について説明する。なお、以下では、すでに述べた内容と重複する箇所については、原則として説明を省略する。
【００４４】
図６は、本発明の実施の形態２に係る演算処理装置の構成の一例を示す図である。図６に示す演算処理装置１０１は、図１の演算器２０が演算器１２０に置き換えられている。演算器１２０は、ＣＰＵ１０から送信される命令に基づき、ｎビットモンゴメリ乗算剰余の算出、ｎビット乗算、及び加減算を切り換えて実行する。
【００４５】
演算器１２０は、例えば図３のステップＳ１０８における出力値の算出を加減算により行う。このように、演算器１２０は、ＣＰＵ１０が行っていた演算を代わりに実行することができる。また、演算器１２０は、出力値の算出以外にも、加減算による入力値の算出をＣＰＵ１０に代わり行ってもよい。
【００４６】
具体的に述べると、図２のＳｔｅｐ２において、ＣＰＵ１０は、入力値の算出に必要な値［ａ１、ａ０、ｂ１、ｂ０］を演算器１２０に送信し、演算器１２０に入力値［ａ１＋ａ０、ｂ１＋ｂ０］を算出させてもよい。そして、演算器１２０は、自身が算出した入力値を用いてｎビット乗算を実行することができる。
【００４７】
図２、図３におけるその他の場合においても、演算器１２０は、ＣＰＵ１０に代わり加減算を実行することが可能となる。
【００４８】
本実施の形態によれば、演算器１２０は、ＣＰＵ１０の命令によりｎビットモンゴメリ乗算剰余の算出、ｎビット乗算、及び加減算を切り換えて行う。この構成によれば、ＣＰＵ１０の負荷が軽減され演算処理装置１０１における処理が高速化される。また、演算結果を、ＣＰＵ１０に読み出す必要がなくなるので、２ｎビットモンゴメリ乗算剰余の演算時間がより短縮される。
【００４９】
（実施の形態３）
次に、実施の形態３について説明する。従来手法を用いることにより、２ｎ、４ｎ、８ｎビット等のモンゴメリ乗算剰余の算出は可能ではあるが、３ｎビットモンゴメリ乗算剰余の算出には、一旦、４ｎビットモンゴメリ乗算剰余の算出を行う必要がある。しかし、この方法では、ｎビットモンゴメリ乗算剰余の算出回数が増え、演算時間が長くなるとともに、４ｎビットのメモリ領域が必要となる。そこで、本実施の形態では、ｎビットモンゴメリ乗算剰余やｎビット乗算を用いた３ｎビットモンゴメリ乗算剰余の算出方法について説明する。
【００５０】
図７は、本発明の実施の形態３に係る３ｎビットモンゴメリ乗算剰余算出のアルゴリズムを例示する図である。本実施の形態における３ｎビットモンゴメリ乗算剰余算出には、図７のＳｔｅｐ１〜Ｓｔｅｐ１４等の演算処理が実行される。図７に示すように、Ｓｔｅｐ１〜２、Ｓｔｅｐ４〜８、Ｓｔｅｐ１０〜１１、Ｓｔｅｐ１３〜１４ではｎビット乗算が実行され、Ｓｔｅｐ３、Ｓｔｅｐ９、Ｓｔｅｐ１２ではｎビットモンゴメリ乗算剰余の算出や加減算を含むマルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。このように、本実施の形態では、Ｓｔｅｐ数を増やすことにより、３ｎビット乗算剰余が直接算出される。
【００５１】
具体的に述べると、図７のアルゴリズムでは、Ａ＝ａ２ｍ２＋ａ１ｍ＋ａ０、Ｂ＝ｂ２ｍ２＋ｂ１ｍ＋ｂ０、Ｎ＝ｎ２ｍ２＋ｎ１ｍ＋ｎ０を入力として、２ｎビットの各値｛ｒ０、ｑ０｝〜｛ｒ１、ｑ１｝、（ｑ２、ｒ２）、｛ｒ３、ｑ３｝〜｛ｒ７、ｑ７｝、（ｑ８、ｒ８）、｛ｒ９、ｑ９｝〜｛ｒ１０、ｑ１０｝、（ｑ１１、ｒ１１）、｛ｒ１２、ｑ１２｝〜｛ｒ１３、ｑ１３｝が算出される。なお、ｍ：＝２ｎ、Ｍ：＝ｍ３＝２３ｎである。
【００５２】
Ｓｔｅｐ１では、［ａ２、ｂ２］を入力とし、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ０、ｑ０｝が算出される。Ｓｔｅｐ２では、［ａ１、ｂ１］を入力とし、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ１、ｑ１｝が算出される。Ｓｔｅｐ３では、［ａ０、ｂ０、ｎ０］を入力として、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。これにより、２ｎビットの値（ｑ２、ｒ２）が算出される。
【００５３】
Ｓｔｅｐ４では、［ａ２＋ａ１、ｂ２＋ｂ１］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ３、ｑ３｝が算出される。Ｓｔｅｐ５では、［ａ２＋ａ０、ｂ２＋ｂｏ］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ４、ｑ４｝が算出される。Ｓｔｅｐ６では、［ａ１＋ａ０、ｂ１＋ｂ０］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ５、ｑ５｝が算出される。
【００５４】
Ｓｔｅｐ７では、［ｑ２、ｎ２］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ６、ｑ６｝が算出される。Ｓｔｅｐ８では、［ｑ２、ｎ１］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ７、ｑ７｝が算出される。Ｓｔｅｐ９では、［−ｑ１＋ｒ２＋ｑ５−ｑ７、１、ｎ０］を入力として、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。これにより、２ｎビットの値（ｑ８、ｒ８）が算出される。
【００５５】
Ｓｔｅｐ１０では、［ｑ８、ｎ２］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ９、ｑ９｝が算出される。Ｓｔｅｐ１１では、［ｑ８、ｎ１］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ１０、ｑ１０｝が算出される。Ｓｔｅｐ１２では、［−ｑ０＋ｑ１−ｒ１−ｒ２＋ｑ４＋ｒ５−ｑ６＋ｑ７−ｒ７＋ｒ８−ｑ１０、１、ｎ０］を入力として、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）が実行される。これにより、２ｎビットの値（ｑ１１、ｒ１１）が算出される。
【００５６】
Ｓｔｅｐ１３では、［ｑ１１、ｎ２］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ１２、ｑ１２｝が算出される。Ｓｔｅｐ１４では、［ｑ１１、ｎ１］を入力として、これらの乗算が実行される。これにより、２ｎビットの値｛ｒ１３、ｑ１３｝が算出される。
【００５７】
そして、これらの演算結果を用いて、以下の式（２）により、３ｎビットモンゴメリ乗算剰余が出力値として算出される。
【００５８】
Ａ＊Ｂ＊Ｍ−１（ｍｏｄ Ｎ）＝（ｒ０＋ｒ６−ｒ１２）ｍ２＋（ｑ０−ｒ０−ｒ１＋ｒ３＋ｑ６＋ｒ６＋ｒ７−ｒ９−ｑ１２−ｒ１３）ｍ＋（−ｑ０−ｒ０−ｑ１＋ｒ１−ｒ２＋ｑ３＋ｒ４＋ｑ６−ｒ６＋ｑ７＋ｒ７−ｑ９−ｒ１０＋ｒ１１−ｑ１３）    ・・・（２）
図８は、図７のアルゴリズムに対応するフロー図である。図７は、図３に対し、ステップＳ１０３、Ｓ１０６の処理内容が異なる。図７に示すように、本実施の形態では、Ｓｔｅｐ３、９、１２においてマルチ演算が実行される。このため、図８のステップＳ１０３では、カウント値が「３、９、１２」の場合（Ｙｅｓ）、ＣＰＵ１０は、マルチ演算（ＭｕｌｔＭｏｎＤｉｖ）を選択し、ステップＳ１０４の処理が実行される。一方、カウント値がそれ以外の値「１〜２、４〜８、１０〜１１、１３〜１４」である場合（Ｎｏ）、ＣＰＵ１０は、乗算を選択し、ステップＳ１０５の処理が実行される。
【００５９】
ステップＳ１０６では、カウント値が「１４」であるかどうかが判定される。ＣＰＵ１０が、カウント値が「１４」でないと判定した場合（Ｎｏ）、ステップＳ１０７の処理が実行される。これに対し、ＣＰＵ１０が、カウント値が「１４」であると判定した場合（Ｙｅｓ）、ステップＳ１０８の処理が実行される。
【００６０】
本実施の形態によれば、演算器２０において、ｎビットモンゴメリ乗算剰余の算出と、ｎビット乗算とを適宜切り換えて実行することにより、３ｎビットモンゴメリ乗算剰余の算出が行われる。２ｎビットモンゴメリ乗算剰余の算出に比べてステップ数が増えているが、ｎビットモンゴメリ乗算剰余の算出の回数が６回に抑えられており、３ｎビットモンゴメリ乗算剰余の算出に要する演算時間を短縮させることが可能となる。また、４ｎビットモンゴメリ乗算剰余の算出を行うことなく、３ｎビットモンゴメリ乗算剰余を直接算出することが可能となるので、３ｎビット以上のメモリ領域を用意する必要がなくなり、メモリを有効に利用することが可能となる。
【００６１】
本実施の形態では、３ｎビットモンゴメリ乗算剰余の算出方法について説明したが、ステップ数を増やすことにより、さらにビット数の大きいｎビットの整数倍のビット数のモンゴメリ乗算剰余も短時間で算出可能である。
【００６２】
（実施の形態４）
次に、実施の形態４について説明する。本実施の形態では、ｎビットモンゴメリ乗算剰余を行う演算器（第１演算器）と、ｎビット乗算を行う演算器（第２演算器）とがそれぞれ独立して設けられている。図９は、本発明の実施の形態４に係る演算処理装置の構成の一例を示す図である。図９に示す演算処理装置２０１は、図１の演算器２０が演算器２２１、２２２に置き換えられている。演算器２２１は、ＣＰＵ１０の命令に基づきｎビットモンゴメリ乗算剰余の算出を実行する。演算器２２２は、ＣＰＵ１０の命令に基づき、ｎビット乗算を実行する。
【００６３】
本実施の形態に係る演算処理装置２０１は、演算器２２１によるｎビットモンゴメリ乗算剰余の算出を含むマルチ演算と、演算器２２２によるｎビット乗算とを並列に実行することが可能である。図１０は、本発明の実施の形態４におけるマルチ演算とｎビット乗算とを並列実行させる手順の一例を示す図である。図１０には、図２のアルゴリズムを例にした並列実行手順が示されている。
【００６４】
図２のアルゴリズムについて検討する。Ｓｔｅｐ３のマルチ演算は、入力値（Ｉｎｐｕｔ）のみを用いて実行可能である。したがって、Ｓｔｅｐ１のｎビット乗算と、Ｓｔｅｐ３のマルチ演算とを並列実行可能である。また、Ｓｔｅｐ３の実行中、Ｓｔｅｐ１に続いてＳｔｅｐ２のｎビット乗算を並行実行することが可能である。
【００６５】
一方、Ｓｔｅｐ４のｎビット乗算には、Ｓｔｅｐ３の演算結果「ｑ２」が必要となるので、Ｓｔｅｐ３の処理が完了するまで、Ｓｔｅｐ４を実行することはできない。また、Ｓｔｅｐ５のマルチ演算には、Ｓｔｅｐ４の演算結果「ｑ３」が必要となるので、Ｓｔｅｐ４の処理が完了するまで、Ｓｔｅｐ５を実行することができない。また、Ｓｔｅｐ６のｎビット乗算には、Ｓｔｅｐ５の演算結果「ｑ４」が必要となるので、Ｓｔｅｐ５の処理が完了するまで、Ｓｔｅｐ６を実行することができない。
【００６６】
したがって、図２のアルゴリズムに対し、演算処理装置２０１では、Ｓｔｅｐ１及びＳｔｅｐ３、Ｓｔｅｐ２及びＳｔｅｐ３がそれぞれ並行実行可能である。
【００６７】
図１１は、本発明の実施の形態４におけるマルチ演算とｎビット乗算とを並列実行させる手順の他の例を示す図である。図１１は、図７のアルゴリズムを例にした並列実行手順が示されている。図１１に示すように、Ｓｔｅｐ３のマルチ演算時には、Ｓｔｅｐ２、６、８のｎビット乗算が順次並列実行可能である。Ｓｔｅｐ９のマルチ演算時には、Ｓｔｅｐ１、５、７のｎビット乗算が順次並列実行可能である。
【００６８】
一部でｎビット乗算の順序が入れ換わっているが、これは、各Ｓｔｅｐにおいて必要な値が得られるタイミング等を考慮したためである。例えば、Ｓｔｅｐ１で得られる値「ｑ０」は、Ｓｔｅｐ１２のマルチ演算まで使用されない。このため、Ｓｔｅｐ１は、必ずしも最初に実行される必要はない。一方、Ｓｔｅｐ９のマルチ演算は、Ｓｔｅｐ８の演算結果「ｑ７」が必要なので、Ｓｔｅｐ３と並行して実行されることが望ましい。そうすれば、Ｓｔｅｐ３とＳｔｅｐ９とを連続して実行可能となる。その他のＳｔｅｐについても、ここで述べた事情により適宜実行順序が決定される。
【００６９】
本実施の形態によれば、演算器２２１によるｎビットモンゴメリ乗算剰余の算出を含むマルチ演算と、演算器２２２によるｎビット乗算とを並列に実行することが可能であるので、２ｎビットや３ｎビット等のモンゴメリ乗算剰余の算出に要する演算時間がより短縮される。
【００７０】
（実施の形態５）
次に、実施の形態５について説明する。本実施の形態では、マルチ演算をｎビット乗算及び加減算により実行する場合について説明する。図１２は、本発明の実施の形態５に係る演算処理装置の構成の一例を示す図である。図１２に示す演算処理装置３０１は、図１の演算器２０が演算器３２０に置き換えられている。演算器３２０は、ＣＰＵ１０の命令に基づきｎビット乗算を実行する。すなわち、本実施の形態では、演算器においてｎビットモンゴメリ乗算剰余の算出が直接行われることはない。
【００７１】
図１３は、本発明の実施の形態５に係るマルチ演算のアルゴリズムを例示する図である。図１３のマルチ演算では、「ａ、ｂ、ｎ、ｍ、ｓ」が入力され、「ｑ、ｒ」が出力される。なお、ｓはｎ−１（ｍｏｄ ｍ）で規定される値であり、マルチ演算の実行前に、ＣＰＵ１０等で事前に算出しておく。
【００７２】
Ｓｔｅｐ１では、［ａ、ｂ］を入力として、これらの乗算が実行され、値｛ｃ１、ｃ０｝が算出される。なお、ｂ＝１の場合、｛ｃ１、ｃ０｝＝ａである。Ｓｔｅｐ２では、［ｃ０、ｓ］を入力としてこれらの乗算等を行い、値「ｑ」が算出される。Ｓｔｅｐ３では、［ｑ、ｎ］を入力とする乗算等や、［ｃ０、ｃ１］を入力とする加減算等が実行される。
【００７３】
図１４及び図１５は、図１３のアルゴリズムに対応するフロー図である。図１４は、２ｎビットモンゴメリ乗算剰余の算出に係るフロー図であり、図３と対応している。図１５は、３ｎビットモンゴメリ乗算剰余の算出に係るフロー図であり、図８と対応している。
【００７４】
図１４及び図１５では、図３のステップＳ１０４がステップＳ３０４に置き換えられている。ステップＳ３０４は、ステップＳ３０４ａ〜Ｓ３０４ｅを含んでいる。ステップＳ３０４ａでは、入力値「ｂ」が１であるどうかが判断される。ＣＰＵ１０が、ｂ≠１と判断すると（Ｎｏ）、ステップＳ３０４ｂの処理が実行される。一方、ステップＳ３０４ａにおいて、ＣＰＵ１０がｂ＝１と判断すると（Ｙｅｓ）、ステップＳ３０４ｃの処理が実行される。
【００７５】
ステップＳ３０４ｂでは、図１３のＳｔｅｐ１の処理が実行される。ＣＰＵ１０は値「ａ、ｂ」を演算器３２０に送信し、乗算を行うよう命令する。演算器３２０は、ＣＰＵ１０の命令に従い、［ａ、ｂ］を入力とする乗算（ａ＊ｂ）を実行する。算出された値｛ｃ１、ｃ０｝は、例えばメモリ３０に保持される。
【００７６】
ステップＳ３０４ｃでは、図１３のＳｔｅｐ２の処理が実行される。ＣＰＵ１０は値［ｃ０、ｓ］を演算器３２０に送信し、乗算を行うよう命令する。演算器３２０は、ＣＰＵ１０の命令に従い、［ｃ０、ｓ］を入力とする乗算（ｃ０＊ｓ）を実行する。算出された値「ｑ」は、例えばメモリ３０に保持される。
【００７７】
ステップＳ３０４ｄ〜Ｓ３０４ｅでは、図１３のＳｔｅｐ２の処理が実行される。ステップＳ３０４ｄにおいて、ＣＰＵ１０は、値［ｑ、ｎ］を演算器３２０に送信し、乗算を行うよう命令する。演算器３２０は、ＣＰＵ１０の命令に従い、［ｑ、ｎ］を入力とする乗算（ｑ＊ｎ）を実行する。算出された値「ｑ＊ｎ」は、例えばメモリ３０に保持される。
【００７８】
ステップＳ３０４ｅにおいて、ＣＰＵ１０は、ステップＳ３０４で算出された値「ｑ＊ｎ」、及び値［ｃ０、ｃ１］を用いて値「ｒ」を算出する。算出された値「ｒ」は、例えばメモリ３０に保持される。このように、マルチ演算により値（ｑ、ｒ）が算出される。このように、乗算及び加減算を含むステップＳ３０４のマルチ演算により算出された値は、ｎビットモンゴメリ乗算剰余の算出及び加算を含むＳ１０４のマルチ演算により算出された値と同一である。
【００７９】
図１４及び図１５のマルチ演算では、２回のｎビットモンゴメリ乗算剰余の算出が、３回の乗算に変更されている。したがって、２ｎビットモンゴメリ乗算剰余の算出では、マルチ演算で６（３×２）回の乗算が実行される。また、３ｎビットモンゴメリ乗算剰余の算出では、マルチ演算で９（３×３）回の乗算が実行される。また、ｂの値に応じて、マルチ演算における乗算回数は削減される。
【００８０】
本実施の形態によれば、乗算及び加減算によりマルチ演算が実行される。この構成によれば、ｎビット乗算剰余の算出を行わなくてもよいので、２ｎビットや３ｎビット等のモンゴメリ乗算剰余の算出に要する演算時間がさらに短縮される。
【００８１】
これまで説明した各実施の形態に係る演算処理装置は、例えば、セキュリティ機能が要求されるネットワーク機器、自動車、産業機器等に搭載される。また、演算処理装置は、その他の機能を含めた半導体装置として構成されてもよい。
【００８２】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【符号の説明】
【００８３】
１、１０１、２０１、３０１…演算処理装置、１０…ＣＰＵ、２０、１２０、２２１、２２２、３２０…演算器、３０…メモリ
【図１】
2020140120.tif 000003
【図２】
2020140120.tif 000004
【図３】
2020140120.tif 000005
【図４】
2020140120.tif 000006
【図５】
2020140120.tif 000007
【図６】
2020140120.tif 000008
【図７】
2020140120.tif 000009
【図８】
2020140120.tif 000010
【図９】
2020140120.tif 000011
【図１０】
2020140120.tif 000012
【図１１】
2020140120.tif 000013
【図１２】
2020140120.tif 000014
【図１３】
2020140120.tif 000015
【図１４】
2020140120.tif 000016
【図１５】
2020140120.tif 000017
【図１６】
2020140120.tif 000018
【図１７】
2020140120.tif 000019
【図１８】
2020140120.tif 000020
【図１９】
2020140120.tif 000021
【図２０】
2020140120.tif 000022