(57)【特許請求の範囲】
【請求項１】
被乗数Ａの下位ｍビット（ｍは２以上の整数）の値と乗数Ｂを用いて暫定剰余ｕに部分積{Σ(Ａj*Ｂ) *２j  (j=0,,,m-1)} を加算する加算回路に、法Ｎを加算及び１ビットシフトする処理回路をｍ段継続接続し、前記処理回路における処理結果を帰還値ｖとして一時レジスタに格納し、その格納した値を新たな暫定剰余ｕとして前記加算回路に送る乗算剰余演算器において、
前記暫定剰余ｕの下位ｍビットのシフトを行い、
前記処理を繰り返し行うことにより被乗数Ａと乗数Ｂとのモンゴメリ積を計算し、
前記処理回路の１ビットシフトを禁止することにより乗数Ｂの倍数を計算することができることを特徴とする乗算剰余演算器。
【請求項２】
請求項１の乗算剰余演算器において、前記処理回路で法Ｎの減算及び１ビットシフト禁止を行うことにより前記帰還値ｖ及び暫定剰余ｕのビット数をｋ（ｋは正の整数）ビット値に戻し、当該ｋビット値を用いて繰り返しモンゴメリ積を計算することができることを特徴とする乗算剰余演算器。
【請求項３】
複数のレジスタとマルチプレクサを有し、請求項２の乗算剰余演算器で計算されたモンゴメリ積を繰り返し前記レジスタに格納し、メッセージＭのｅ乗の剰余を計算することを特徴とする乗算剰余演算器。
【請求項４】
前記計算されたモンゴメリ積は帰還値ｖであり、この帰還値ｖは前記マルチプレクサを介して新たな被乗数Ａ若しくは乗数Ｂとされることを特徴とする請求項３に記載の乗算剰余演算器。
【請求項５】
被乗数Ａの下位ｍビット（ｍは２以上の整数）の値と乗数Ｂを用いて暫定剰余ｕに部分積{Σ(Ａj*Ｂ) *２j  (j=0,,,m-1)}を加算する加算回路を有し、前記暫定剰余ｕに法Ｎの倍数{Σ(sj*Ｎ) *２j  (j=0,,,m-1)}を加算し、かつ、 ｍビットシフトする処理回路での処理結果を帰還値ｖとして一時レジスタに格納し、その格納した値を新たな暫定剰余ｕとして前記加算回路に送る乗算剰余演算器において、
前記処理を繰り返し行うことにより被乗数Ａと乗数Ｂとのモンゴメリ積を計算し、前記処理回路のｍビットシフトを禁止することにより乗数Ｂ及び法Ｎの倍数を計算することができることを特徴とする乗算剰余演算器。
【請求項６】
請求項５の乗算剰余演算器において、
前記処理回路で法Ｎの減算及びｍビットシフト禁止を行うことにより前記帰還値ｖ及び暫定剰余ｕのビット数をｋ（ｋは正の整数）ビット値に戻し、当該ｋビット値を用いて繰り返しモンゴメリ積を計算することができることを特徴とする乗算剰余演算器。
【請求項７】
複数のレジスタとマルチプレクサを有し、請求項６の乗算剰余演算器で計算されたモンゴメリ積を繰り返し前記レジスタに格納し、メッセージＭのｅ乗の剰余を計算することを特徴とする乗算剰余演算器。
【請求項８】
前記計算されたモンゴメリ積は帰還値ｖであり、この帰還値ｖは前記マルチプレクサを介して新たな被乗数Ａ若しくは乗数Ｂとされることを特徴とする請求項３に記載の乗算剰余演算器。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は、モンゴメリ空間における乗算剰余演算を高速に行うことができる回路に関するものである。
【０００２】
【従来の技術】
近年ＩＣカードや携帯端末等の普及に伴い本人の認証等を短時間で行う必要性が高まっている。例えば、オンライン・ショッピングに使われる携帯端末では、顧客を待たせないために短時間の内に当該認証を行わなければならない。この認証等においては個人情報の保護のために、通常データを暗号化することが行われる。その暗号としてよく用いられるのがＲＳＡ暗号や楕円曲線暗号であるが、その計算には乗算剰余演算が多用されている。そこで、乗算剰余演算を高速で行う必要性がある。
単純な乗算剰余演算では、例えば１０２４ビットのＲＳＡ暗号を採用したとき、その１０２４ビットデータの乗算ではその積に対し２倍の２０４８ビットのレジスタが必要とされ、かつ、１０２４ビットデータによる割り算が必要である。しかし、割り算に対する計算の負荷は高く、前記短時間での暗号処理を困難にしている。
【０００３】
モンゴメリ(Peter L. Montgomery)法は、乗算剰余演算において前記割り算を用いないで乗算剰余演算を行うことができる方法として著名である。モンゴメリ法では、２つの数値Ａ及びＢの積を法Ｎのもとでその剰余を計算する場合、即ち
Ａ*Ｂ  (mod Ｎ)   (数式１)
を求める場合に、直接的に計算するのではなく、法Ｎの剰余空間での積を計算することにより、その乗算剰余を求める。
さて、大きな数値Ｒが法Ｎと素である場合に（gcd(Ｎ,Ｒ) ＝１)、前記剰余空間として数値Ｒを用いた法Ｎの剰余空間（以下、モンゴメリ空間という。）を考える。数式１での数値Ａ及びＢは、このモンゴメリ空間ではＡ'＝ＡＲ(modＮ)及び Ｂ'＝ＢＲ(modＮ)として取り扱われる。また、モンゴメリ空間での積Mont(Ａ'Ｂ'）は
Mont(Ａ'，Ｂ')＝Ａ'*Ｂ'*Ｒ-1  (mod Ｎ)    (数式２)
で定義される。但し、Ｒ-1は数値Ｒの法Ｎにおける逆数である。数式２の与える結果は当然モンゴメリ空間での値であるので、数式１と異なり、
Ａ*Ｂ*Ｒ  (mod Ｎ)    (数式３)
という形になる。そこでモンゴメリ空間で乗算剰余を求めた後は、通常Ｒ-1を乗じる後処理が必要になる。
【０００４】
ここで、ＲＳＡ暗号を前提にメッセージＭを暗号化することを考えてみよう。メッセージＭは平文を２進表現した巨大な数値である。暗号化は、Ｃ＝Ｍe (modＮ)という指数計算により行われる。この計算はモンゴメリ空間での乗算剰余演算を繰り返すことで容易に計算することができる。段落番号００１７に記載された式Ａ１ないしＡ６はこの乗算剰余演算を表している。これらの式において、式Ａ１及び式Ａ２はモンゴメリ空間を利用するための前処理である。このうち式Ａ２はメッセージＭをモンゴメリ空間での数値Ｍ'に変換する。 Ｍ'＝Ｍ*Ｒ  (modＮ)である。式Ａ３乃至Ａ５のＦＯＲ文は、 モンゴメリ空間でＭ'のe乗(modＮ)を計算している。その結果はＭ'e＝Ｍe *Ｒ  (modＮ)であり、最終的な結果Ｃを求めるために式Ａ６の後処理が必要になる。なお、式Ａ４は指数ｅの２進表現により暗号文を形作っている部分である。また、式Ａ５はそれ自身の２乗を作って、指数を２の倍数だけ増加させる機能を有する。
式Ａ１乃至Ａ６までの間、モンゴメリ空間での積Montだけが使われたので、メッセージＭの暗号化に際し何ら直接的に割り算が使われなかったことに注意したい。このようにモンゴメリ法はＲＳＡ暗号等を高速に計算するのに有効な手法である。
【０００５】
次に、モンゴメリ法でどのようにして巧妙に割り算を回避しているかを説明する。前記数式２において、数値Ａ及びＢがｋビットで構成される２進数として表現され、かつ、Ｒ＝２kとした場合は、シフトレジスタや加算器を用いて前記乗算剰余演算を計算することができる。この時数式２は以下のように表現できる。
Mont(ＡＢ)＝２-k*{Σ(Ａj*Ｂ) *２j  (j=0,,,k-1)}  (mod Ｎ)  (数式４)
数式４では、ｊ番目の部分積(Ａj *Ｂ) *２jを累加して積Montを計算しているが、その際因子２-kをシフタを利用して実現する。
ｕ＝０                           （Ｂ１）
for(j=0;j<k;j++){              （Ｂ２）
ｕ＝ｕ＋Ａj *Ｂ                   （Ｂ３）
if(u0==1) ｕ＝ｕ＋Ｎ          （Ｂ４）
ｕ＝ｕ/２ }                      （Ｂ５）
上述の式は２進加算とシフトにより前記数式４を計算する方法（以下、２進加算シフト法と呼ぶ。）を示したものである。この方法はＲＳＡ暗号等で用いられる法Ｎは通常奇数であるという事実に基礎を置いている。式Ｂ１は計算での暫定値ｕが初期値０であることを示す。式Ｂ２乃至式Ｂ５はfor文であって、添え字ｊが０からｋ−１まで１づつ増加して繰り返される。式Ｂ３は項Ａj *Ｂを暫定値ｕに繰り込むことを示し、これは前記数式４の項別の加算に対応する。式Ｂ４は暫定値ｕに法Ｎを加算するか否かを決めている。暫定値ｕに法Ｎ及びその倍数を加算してもその剰余は変化しないことに注意したい。暫定値ｕのＬＳＢであるu0が１の場合、法Ｎを加算する。法Ｎは奇数であるので、加算の結果暫定値ｕのＬＳＢであるu0は０になる。暫定値ｕのＬＳＢであるu0が０の場合は、法Ｎの前記加算は行わない。この結果、暫定値ｕのＬＳＢであるu0が常に０(ｕが２の倍数であることを示す)のまま項別加算が進むことになる。式Ｂ５は暫定値を２で割っているが、暫定値ｕが２の倍数なのでこれは１ビットシフトで実現できる。なお、前記シフト因子２-1は、暫定値ｕの計算が終了した時点ではその因子は２-kになる。このように２進加算シフト法では、式Ｂ２乃至式Ｂ５の操作を繰り返すことで数式４を求めることができる。
式Ｂ４における暫定値ｕのＬＳＢであるu0'は、式Ｂ４の判定の前に、即ち式Ｂ３の段階で論理的に求めることができる。
u0'＝ u0＠(Ａj *Ｂ0)   (数式５)
ここで、右辺のu0は式Ｂ３の暫定値ｕの最下位ビットであり、 Ｂ0は２進表示した数値Ｂの最下位ビットである。数式５の意味するところは、暫定値ｕのＬＳＢであるu0'（式Ｂ４のu0）を０にする論理式である。但し、演算子＠はＥＯＲ論理を意味する。
以上の計算から明らかなように、モンゴメリ法では加算とシフトだけでモンゴメリ空間での積Montを計算することができた。
【０００６】
なお、加算とシフトによる計算を行う回路については、本出願人が２００２年３月１８日に出願している下記特許出願がある。
【０００７】
【特許文献１】
特願２００２−７６４１３
【０００８】
以上説明したように２進シフト加算法は、暫定値ｕの最下位ビット  ｕ０を０にするために比較的単純な処理で済ませることができるが、１ビット毎の処理で能率が悪い。
そこで、並列演算処理などを用いて処理速度を上げようとする例として下記特許文献がある。
【０００９】
【特許文献２】
特開２００２−７１１２号公報
【００１０】
【発明が解決しようとする課題】
ＩＣカードや携帯端末等の取り扱う情報は年々増加しており、認証等に用いられる暗号についても計算時間の短縮化の要請は大きい。乗算剰余演算を高速に実行するため、上述のような並列演算処理を採用すると、同一の回路を複数必要とするために回路規模が大きくなってしまう。
【００１１】
【課題を解決するための手段】
本発明では、モンゴメリ法による乗算剰余演算を高速に実行させるために複数ビットを同時処理する方法を採用する。即ち、本発明では暫定値ｕの下位の複数ビットをそれぞれ０とし、その複数ビット分だけ右シフトする方式を採用する。その結果、モンゴメリ法による乗算剰余演算をほぼ当該複数倍に高速化することができる。
【００１２】
【発明の実施の形態】
本発明による第一の実施例では、モンゴメリ法による乗算剰余演算を２ビット同時処理する方法を開示する。本実施例による乗算剰余演算で２ビットを同時処理するときは、部分積の大きさがＢより大きくなる場合があること、及び法Ｎの加算を２段に亘って行わなければならなくなる他、法Ｎを加算するか否かの判定処理が複雑化する。
最初に数式４を２ビット毎の部分積に構成し直す。
0003576155.tif 000002
但し、ｋは偶数と仮定
数式６で、部分積は(２Ａ2j+1＋Ａ2j)*Ｂとなる。モンゴメリ法による乗算剰余演算を２ビット同時処理するためには、この部分積を累加した暫定値ｕの下位２ビットが常に０(ｕが４の倍数であることを示す)のまま項別加算を進める必要がある。項(２Ａ2j+1＋Ａ2j)は数値Ａが２進数で表示されたとき、３乃至０の値を取り得る。それ故部分積は３Ｂ乃至０の値を持ち、暫定値ｕに加算される。  暫定値ｕのＬＳＢ(u0とする)とその一つ上のビット(u1とする)は法Ｎを加算するか否かの基準になる。ベクトル(u1,u0)と表示したとき、これが (0,0)となるように法Ｎを加算し若しくはシフトするのがモンゴメリ法による乗算剰余演算のやり方である。これは図４の式Ｂ４を拡張した方式でもあるが、２ビット同時処理を行うことにしたために、シフト処理が複雑化することになった。
従来法の１ビット右シフトは暫定値ｕのＬＳＢを０にしたために可能になった。本実施例においても、前記ベクトルを(0,0)にできたときは２ビット右シフトすることができる。しかし、最初のビットu0を０にするために法Ｎを加算するのに伴いキャリが発生し、次のビットu1を０にするために当該キャリを考慮しなければならなくなる。
【００１３】
ｕ＝０                                  （Ｃ１）
for(j=0;j<k/2-1;j++){                （Ｃ２）
ｕ＝ｕ＋(２Ａ2j+1＋Ａ2j)*Ｂ        （Ｃ３）
if(u0==1) ｕ＝ｕ＋Ｎ                （Ｃ４）
ｕ＝ｕ/２                            （Ｃ５）
if(u0==1) ｕ＝ｕ＋Ｎ                （Ｃ６）
ｕ＝ｕ/２ }                          （Ｃ７）
上述の式は、本発明による第一の実施例における積Montの計算方法である。式Ｃ１は計算での暫定値ｕが初期値０であることを示す。式Ｃ２乃至式Ｃ７はfor文であって、添え字ｊが０からｋ/2−１まで１づつ増加して繰り返される。但し、ｋは偶数と仮定されている。この添え字ｊのステップは１クロックに対応し、ここでは１クロックで２項分の処理が行われる。
式Ｃ３は部分積は(２Ａ2j+1＋Ａ2j)*Ｂを暫定値ｕに繰り込むことを示し、これは前記数式４の項別の加算に対応する。式Ｃ４は暫定値ｕに法Ｎを加算するか否かを決める。暫定値ｕに法Ｎ及びその倍数を加算してもその剰余は変化しないことに注意したい。暫定値ｕのＬＳＢであるu0が１の場合、法Ｎを加算する。法Ｎは通常奇数であるので、加算の結果暫定値ｕのＬＳＢであるu0は０になる。暫定値ｕのＬＳＢであるu0が０の場合は、法Ｎの前記加算は行わない。この結果、暫定値ｕのＬＳＢであるu0が常に０(ｕが２の倍数であることを示す)のまま式Ｃ５へ処理が移ることになる。
式Ｃ４における暫定値ｕのＬＳＢであるu0は、式Ｃ４の判定の前に、即ち式Ｃ３の段階で論理的に求めることができる。
論理を明快にするために、式Ｃ３の右辺において、改めて
Ｂ＝２Ｂ1＋Ｂ0  及び  ｕ＝２u1＋ u0
とおくと、式Ｃ３は
ｕ＝４Ａ2j+1*Ｂ1＋２(u1＋ Ａ2j*Ｂ1＋ Ａ2j+1*Ｂ0)＋(u0＋ Ａ2j*Ｂ0)  (数式７)
と表現できる。この数式７の第１項は暫定値ｕの一つ上の桁のビットu2を与えるので無視できる。この第３項は左辺の新たなu0（以下u0'と表示する）を決定する。第３項の加算は次の論理式と等価である。
u0'＝ u0＠(Ａ2j*Ｂ0)   (数式８)
数式８の論理式は、暫定値ｕのＬＳＢであるu0を０にするために法Ｎを加算するか否かを決定する。このu0'は式Ｃ４のＬＳＢであるu0に対応する。但し、演算子＠はＥＯＲ論理を意味する。
式Ｃ５は暫定値を２で割る。これは１ビット右シフトで実現でき、結線の変更で対処できる。その際前記項別加算において何ら暫定値ｕの表示及びその桁数を変更しないことに注意したい。このシフトの結果、暫定値ｕのＬＳＢはビットu0'から一つ上の桁のビットu1'へ移行する。
式Ｃ６は暫定値ｕのＬＳＢを再び０にするために設けられており、その方法は暫定値ｕに法Ｎを加算することにより行われる。どのような場合にビットu1'が１になるかの論理式は、前記キャリの考慮により多少複雑になる。上記数式７の右辺第２項と、法Ｎを加算する場合には必ずキャリが発生することを考慮すると、式Ｃ５における暫定値ｕの新たな暫定値ｕは、上記シフトの結果
ｕ＝ u1＋ Ａ2j*Ｂ1＋ Ａ2j+1*Ｂ0＋(N1＋１）u0'   (数式９)
と表現できる。但し、N1は法Ｎの第２ビットである。
これを論理式に置き換えるとき、上記数式９の右辺のＬＳＢに着目し、かつ、キャリを無視すると、
u1'＝ u1＠Ａ2j*Ｂ1＠Ａ2j+1*Ｂ0＠N1_u0'   (数式１０)
と表現できる。 このu1'は式Ｃ６のＬＳＢであるu0に対応する。但し、N1_はN1の否定論理であり、演算子＠はＥＯＲ論理を意味する。
【００１４】
次に本発明の第一の実施例による積Montを計算する回路構成図を、図１に示す。この回路構成図は、式C1からC7に示した積Montの計算方法をほぼそのまま実現している。部分積を計算するために、レジスタ１０１に置かれた数値Ｂの他に、予めレジスタ１０３に数値３Ｂを置いてある。レジスタ１０２に置かれた数値２Ｂは前記レジスタ１０１に置かれた数値Ｂを結線で１ビットシフトすることで間に合わせることができる。数値３Ｂは乗算剰余演算の初期に予め計算しておかなければならない。図５は、モンゴメリ積Montを計算する際の計算手順を示している。積Montの計算の前に、数値３Ｂの計算という前処理が必要である。数式４によるモンゴメリ積Montの計算の後には、後処理として桁合わせが行われる。これについては、本発明の第二の実施例の方で解説する。
図２は、前記数値３Ｂの計算を行うときの計算表の一例を示す図表である。初期値として、２ビット右シフトレジスタ１０４を  (A2j+1,A2j)＝（0,1）のようにセットしておき、かつ、その際一時レジスタＴＰ１１４をリセットしておく。そこで、暫定値uは０になり、マルチプレクサ１０５からの出力値Ｂが加算器１０６の入力となる。また、法Ｎの加算を行うか否か決定するＡＮＤゲート（１０９、１１１は、制御信号が（u1'，u0'）＝（0,0）であるので、その加算は行われない。更に、１ビット右シフタ１１０、１１３は、制御信号が  (s1,s0)＝（1,1）であるので、そのシフトは行われない。そこで、加算器１０６、１０７、１１２による加算後の帰還値ｖは値Ｂになる。１クロック後、前記帰還値ｖは一時レジスタＴＰ１１４にセットされ、新たな暫定値uはＢになる。次に、前記１クロック後に２ビット右シフトレジスタ１０４を  (A2j+1,A2j)＝（1,0）のようにセットする。制御信号（u1'，u0'）及び制御信号(s1,s0)の値は同じままなので、新たなマルチプレクサ１０５からの出力値２Ｂと前記暫定値uの値Ｂの加算から、加算後の帰還値ｖは値３Ｂになる。帰還値ｖは次のクロックでレジスタ１０３に格納され、モンゴメリ積Montの計算の準備が整う。なお、一時レジスタＴＰ１１４を再びリセットして、暫定値uを事前に０にしておく。
次に、図１を用いてモンゴメリ積Montの計算方法を開示する。数値Ａを格納するレジスタ１０４は２ビット右シフトレジスタであり、１クロック毎に、即ち図２の式Ｃ２の添え字ｊ毎に、２ビット右シフトする。その結果、数値Ａの下位２ビットがＡ2j+1Ａ2j(j=0,,,k/2-1)という形で取り出される。マルチプレクサ１０５は数値Ａの前記下位２ビットに基づき、レジスタ１０１、１０２、１０３か０の何れかを選択する。選択された値は(２Ａ2j+1＋Ａ2j)*Ｂであって、その値は３Ｂ乃至０の何れかになる。加算器１０６は暫定値ｕと前記マルチプレクサ１０５の出力値とを加算する（これは上述の式Ｃ３に対応する）。
【００１５】
暫定値ｕのＬＳＢを０にするための処理回路１１５は、当該暫定値ｕにレジスタ１０８に格納された法Ｎを加算する処理を行う。法Ｎを加算するか否かの決定は数式８の変数ｕ０’が行うが、数式８の構成から、変数ｕ０’を加算器１０６での加算の開始直後に確定することができる。加算器１０７においては、ｕ０’が１の場合にだけ法Ｎが暫定値ｕに加算される（これは上述の式Ｃ４に対応する）。加算の結果暫定値ｕのＬＳＢが０になり、１ビット右シフタ１１０により１ビット右シフトすることができる（制御信号ｓ０は値０である。）。この結果、１ビット右シフタ１１０は新たな暫定値ｕを与える（これは上述の式Ｃ５に対応する）。
暫定値ｕのＬＳＢを０にするための処理回路１１６は、当該暫定値ｕにレジスタ１０８に格納された法Ｎを加算する処理を行う。法Ｎを加算するか否かの決定は数式９の変数ｕ１’が行うが、数式１０の構成から、変数ｕ１’を加算器１０７での加算の開始直後に確定することができる。加算器１１２においては、ｕ１’が１の場合にだけ法Ｎが暫定値ｕに加算される（これは上述の式Ｃ６に対応する）。加算の結果暫定値ｕのＬＳＢが０になり、１ビット右シフタ１１３により１ビット右シフトすることができる（これは上述の式Ｃ７に対応する）。この結果、１ビット右シフタ１１３は当該暫定値ｕを出力し（制御信号ｓ１は値０である。）、その値は次のクロックの際に新たな暫定値ｕとして一時レジスタＴＰ１１４に格納される。
図１の回路がｋ／２個のクロックを終了すると、１ビット右シフタ１１３の出力は数式６の積Ｍｏｎｔを与える。モンゴメリ積Ｍｏｎｔの計算において、本発明の第一の実施例では回路量でみると処理回路が一段分増加するが、２ビット毎の処理を行うことができたので計算速度は倍になった。予め数値３Ｂを計算しておく不利はあるが、乗算剰余演算を高速で行う要請に応えるものである。
【００１６】
図１の回路は、計算の説明のために回路の詳細については省略してあるが、実際には多ビットの加算器１０６、１０７、１１２、ＡＮＤゲート１０９、１１１、及び１ビット右シフタ１１０、１１３を使用している。そこで図３を用いて、制御回路１１６の構成例について説明しておく。
図３は、制御回路１１６の１ビット分（第ｊビット）の回路１２１を示している。その中心にあるのは全加算器ＦＡ１２２で、暫定値ｕの１ビットｕｊと法Ｎの１ビットＮｊと前段からのキャリＣｊ−１との加算を行い、加算値Ｑｊと次段へのキャリＣｊを生成する。法Ｎの１ビットＮｊとの加算を行うか否かは制御信号ｕ１’の値に依存しており、ＡＮＤゲート１２４で制御される。加算値Ｑｊはそのまま出力になるのではなく、次段の加算値Ｑｊ＋１との選択がマルチプレクサ１２３において行われる。マルチプレクサ１２３の制御信号ｓ１はその値０のときは次段の加算値Ｑｊ＋１が選択されるので、これは１ビット右シフトを選択したことになる。制御信号ｓ１は、その値１のときは加算値Ｑｊが選択されるから、結局、シフト禁止信号としての意味を有する。
１ビット分の回路に、帰還値ｖの第ｊビットｖｊが含まれているのは、主に配線を考慮したことに基づく。多ビットの配線を引き回すことはＬＳＩのチップサイズを増大させるので、これを行わないための工夫である。
【００１７】
次に本発明の第二の実施例について説明する。本発明の第二の実施例は、下記のメッセージＭのｅ乗の計算(Ｃ＝Ｍe)に関係する。
Ｔ１＝Ｒ                                （Ａ１）
Ｔ２＝Mont(Ｍ,Ｒ2)                 （Ａ２）
for(j=0;j<k;j++){                      （Ａ３）
if(ej==1) Ｔ１＝Mont(Ｔ２,Ｔ１)    （Ａ４）
Ｔ２＝Mont(Ｔ２,Ｔ２) }              （Ａ５）
Ｃ＝Mont(Ｔ１,１)                      （Ａ６）
上の計算でも明らかなように、モンゴメリ積Montはその引数（Ｔ１若しくはＴ２）を繰り返し使っている。そこで、新たなレジスタ（Ｔ１及びＴ２）を設けて計算の実質的な高速化を計る方法を考えることができる。
図４は、本発明の第二の実施例によるメッセージＭのe乗の計算をする回路構成図である。基本的には、本発明の第一の実施例である図１の回路に、Ｔ１レジスタ６１７、Ｔ２レジスタ６１８、マルチプレクサ６１９、及びマルチプレクサ６２０を追加した構成を有する。 Ｔ１レジスタ６１７のセットにはラッチ信号set1が、 Ｔ２レジスタ６１８のセットにはラッチ信号set2が、それぞれ使われる。マルチプレクサ６１９の選択は選択信号sel1が、マルチプレクサ６２０の選択は選択信号sel2が、それぞれ使われる。処理回路６１５及び６１６は、それぞれ図１の処理回路１１５及び１１６に対応するので、処理回路６１６の１ビット右シフタ６１３の累加された出力は数式６の積Montを与える。それ故、図３のメッセージＭのｅ乗の計算に際しては、特にＦＯＲ文内部の式Ａ４と式Ａ５の計算において、前記Ｔ１レジスタ６１７及びＴ２レジスタ６１８へのデータのセットが頻繁に行われる。
0003576155.tif 000003
上記の式は、メッセージＭのe乗の計算をする方法であって、ｅの値にかかわらず計算時間の均一化を図るところが上述した式Ａ１乃至Ａ６に開示した方法と異なる。即ち、上記の式Ｄ１乃至Ｄ５及びＤ８はそれぞれ上述した式Ａ１乃至Ａ５及びＡ６に対応する。異なる点は、if文の条件が合致しなかった場合にelse文である式Ｄ６及びＤ７が挿入されているところである。この両式は、if文が実行されてもelse文実行されてもその計算時間が変わらないように構成されている。計算時間の均一化を図る目的は、情報の漏洩の防止である。仮に前記図３の方法により構成された暗号が信号線を介して伝送されたとして、その信号線から漏れるノイズの周期性から鍵情報ｅに関するデータを取得する技術がある。これを幾分でも防ぐために、上記計算方法が採用されている。本発明の第二の実施例は、上述した式Ｄ１〜Ｄ８のようにレジスタ（Ｔ１及びＴ２）を頻繁に入れ替える計算において、効率の良い回路構成になっている。
【００１８】
本発明の第二の実施例では、取り扱うデータのビット長に大きな配慮を行う必要がある。データのビット長はレジスタの大きさに直接関係する。図６の加算器６０６と処理回路（６１５、６１６）と暫定値ｕで構成されるループからも明らかなように、暫定値ｕの最大値ｕmax、乗数Ｂ、及び法Ｎの間には
ｕmax≦｛(max(0,B,2B,3B)＋ｕ＋Ｎ)/２＋Ｎ｝/２    (数式１１)
の関係がが成立する。
数式２でＲ＝２1024とした場合は、数式１１において３ＢはＭＰＸ６０５の最大値で1024+2bit、Ｎは法で1024bitである。
また、ｕ＜Ｒ、Ｂ＜Ｒ、Ｎ＜Ｒの関係から、数式１１より
ｕ＜Ｎ＋Ｒ          （数式１２）
の関係が成立する。
従って、そのビット長につき整合するためには  ｕは暫定値で1024+1bitでならなければならない。暫定値ｕは1024+1bitであっても、何ら問題はない。数式１１において、数式１２により暫定値ｕが１ビット増えても、再び数式１２の関係が維持されるからである。しかし、次のモンゴメリ積Montの計算においては、このままでは帰還値ｖが1024+1bitになってしまい、レジスタＴ１若しくはＴ２(1024bit)と整合が取れないという問題が生じる。
図５はモンゴメリ積Montの計算手順を示す概念図である。図５に示したモンゴメリ積Montの計算手順において、後処理を追加した理由はこの点にある。この問題を回路的に解決するために、図４の処理回路６１６は図１の処理回路１１６とは異なる構成を採用した。図６の処理回路６１６の加減算器６１２がそれで、制御信号sel4により法Ｎを暫定値ｕから差し引く事ができるようにしてある。この結果、暫定値ｕに対し  ｕ＜Ｒの関係を維持でき、次のモンゴメリ積Montの計算に支障が出ない。
【００１９】
図６は、モンゴメリ積Montの計算におけるレジスタの桁合わせを示す図表である。以下、この図６を参照しつつ、詳しい後処理の内容について説明する。一応のモンゴメリ積Montの計算が終了した後、このままではレジスタＴ１若しくはＴ２に帰還値ｖを格納できない場合がある。それは帰還値ｖのＭＳＢが１の場合で、帰還値ｖの値がＲを越えていることを意味する。そこでこの場合は帰還値ｖから法Ｎを差し引く処理を行う。モンゴメリ積Montの計算後で初期値でv(MSB)が１の場合には、後処理を開始する。１クロック後前記帰還値ｖは一時レジスタＴＰ６１４に格納され、暫定値ｕになる。この時２ビット右シフトレジスタ６０４を  (A2j+1,A2j)＝（0,0）のようにセットしておくと、加算器６０６において乗数の加算は行われず暫定値ｕがそのまま処理回路６１５に入力される。１ビット右シフタ６１０、６１３は制御信号が  (s1,s0)＝（1,1）のようにセットされているので、そのシフトは禁止されている。処理回路６１６では前記暫定値ｕから法Ｎを差し引く計算が行われる。制御信号sel4が値１になると、加減算器６１２で減算が選択される。その減算は入力キャリ値１を伴う２の補数演算である。この演算の結果、２クロック後暫定値ｕは  ｕ＜Ｒの関係を維持でき、レジスタＴ１若しくはＴ２への格納が可能になる。
本発明の第一の実施例における図１の制御回路１１６は、本発明の第二の実施例において減算が可能な図４の制御回路６１６に置き換えられている。その減算の方法は、入力キャリ値１を伴う２の補数演算である。図７は、制御回路６１６の１ビット分（第ｊビット）の回路６３１の構成を示すものである。その中心にあるのは全加算器ＦＡ６３２で、暫定値ｕの１ビットｕｊと法Ｎの１ビットＮｊと前段からのキャリＣｊ-1との加算を行い、加算値Ｑｊと次段へのキャリＣｊを生成する。法Ｎの１ビットＮｊとの加算を行うか否かは制御信号u1'の値に依存しており、ＡＮＤゲート６３４で制御される。加算値Ｑｊはそのまま出力になるのではなく、次段の加算値Ｑｊ+1との選択がマルチプレクサ６３３において行われる。マルチプレクサ６３３の制御信号s1はその値１のときは次段の加算値Ｑｊ+1が選択されるので、これは１ビット右シフトを選択したことになる。制御信号s1は、その値０のときは加算値Ｑｊが選択される。
図７に記載した回路と図3に記載した回路との違いは、新たなＥＯＲゲート６３５とそれを制御する信号sel4の追加にある。 制御信号sel4は、その値が１の時は減算をその値が０の時は加算を選択する。ＡＮＤゲート６３４の出力は直接全加算器ＦＡ６３２に入力されるのではなく、このＥＯＲゲート６３５を介して行われる。これは、前記２の補数演算を実行するために法Ｎのビット反転出力を作ることにある。入力キャリ値１を伴う当該反転出力の加算は数値(―Ｎ)の加算を意味する。
【００２０】
次に、本発明の第三の実施例について説明する。図８は、本発明の第三の実施例を示す回路構成図である。第三の実施例は、第一及び第二の実施例を更に効率化した回路構成を有する。本発明の第三の実施例が第二の実施例と異なる主要な点は、第二の実施例では図４の如く処理回路が２段（６１５及び６１６）であったのに対し、第三の実施例では処理回路が１段（８１５）であり、その結果回路量の削減と消費電力の削減を実現できること、及び、第二の実施例では法Ｎの加算だけを行うのに対し、第三の実施例では３Ｎ乃至０の加算を行う点にある。また、処理回路８１５の構成内容も異なる。即ち、処理回路８１５は加算器８０７と２ビット右シフタ８０８で構成されており、ＡＮＤゲートは使われていない。その理由は、本発明の第三の実施例は、暫定値ｕの下位２ビットを同時に０にする方式を採用したからである。第三の実施例で３Ｎ乃至０の加算を行う理由もここにある。
どのような場合に３Ｎ乃至０の何れかを選択するかは、マルチプレクサ８２４の選択信号sel3の選択の仕方による。いま、選択信号sel3のＬＳＢをs0、一つ上のビットをs1として、
sel3=2s1+s0と表示することにする。このとき加算器８０７に加算される値は  sel3*Ｎと表示できる。すると、加算後の暫定値ｕ'は
ｕ'＝ｕ＋(２Ａ2j+1＋Ａ2j)*(２Ｂ1＋Ｂ0)＋(2s1+s0)*(２Ｎ1＋Ｎ0)  (数式１３)
で与えられる。これを整理すると、
0003576155.tif 000004
となる。
【００２１】
さて数式１４で、第１項はｕ'の第３ビット目以上を決めるのでここでは無視できる。第３項はｕ'のＬＳＢを決定する。第３項が０となるようにs0を決めるので、Ｎが奇数であることを考慮し、
s0＝ u0＠Ａ2j*Ｂ0  (数式１５)
と求めることができる。このs0を用いて、数式１４の第２項を０にすることを考えると、第１項を０にした際キャリが発生していることを考慮し、
s1= u1＠Ａ2j*Ｂ1＠Ａ2j+1*Ｂ0＠N1_s0  (数式１６)
と求めることができる。なお、数式１５の変数s0及び数式１６の変数s1は、それ等の数式の構成から、加算器８０６での加算の開始直後に確定することができる。
第二の実施例との差異を明らかにするために、図８の制御回路８１５の１ビット分（第ｊビット）の回路例を図９に示した。この回路の特徴は、法Ｎの替わりに３Ｎ乃至０の値が制御信号sel3により選択されるので図７のＡＮＤゲート６３４に相当するものが不要になったこと、及び、２ビット右シフトを達成するためにマルチプレクサ６３３は制御信号s5により加算値Ｑｊ若しくはＱｊ+2の何れかが選択されること、にある。
３Ｎの計算は基本的には前記３Ｂの計算と同様である。図１０は、この３Ｎの計算表を示す図表である。３Ｎの計算が３Ｂの計算と異なる点は加算値の選択のために制御信号sel3を用いていること、及び、制御信号s3により２ビット右シフトを行わない選択をしていること、である。
モンゴメリ積Montの計算におけるレジスタの桁合わせ（後処理）は、この場合にも必要になる。図１１はモンゴメリ積Montの計算におけるレジスタの桁合わせを示す図表である。図１１を参照するとどのようにして桁合わせを行うかの方法が理解できる。暫定値ｖのＭＳＢが１の場合に後処理が必要とされ、制御信号sel3を法Ｎを選択するように定め、制御信号sel5を加減算器８０７が減算を選択するように定め、かつ、２ビット右シフトを行わないように制御信号s3を定める。これにより、暫定値ｖの桁をＴ１若しくはＴ２の桁と一致させることができる。
【００２２】
本発明の第三の実施例において、求められた選択信号sel3＝(s1,s0)を使って加算器８０７で暫定値ｕと選択された値sel3*Ｎを加算すると、加算後の当該暫定値ｕは既に下位２ビットが０になっているので、２ビット右シフタ８０８でシフトした後でもその乗算剰余は何ら変わらず、累加とシフトのみでモンゴメリ積Montを計算することができた。また、本発明の第二の実施例と同様に、式A1乃至A6若しくは式D1乃至D6のメッセージＭのe乗の計算に際し、新たなレジスタ（Ｔ１及びＴ２）を設けたことから当該計算の実質的な高速化を計ることができた。なお、予め３Ｂを計算しておく前処理の他に、新たに予め３Ｎを計算しておく前処理の負担が生じている。
【００２３】
本発明の第一の実施例は更に一般的に拡張することができる。被乗数Ａの下位ｍビット（ｍは２以上の整数）の値と乗数Ｂを用いて暫定剰余ｕに部分積{Σ(Ａj*Ｂ) *２j  (j=0,,,m-1)}を加算する回路において、法Ｎを加算及び１ビットシフトする処理回路をｍ段継続接続することにより前記暫定剰余ｕの下位ｍビットを０にし、その後前記暫定剰余ｕの下位ｍビットの右シフトを行い、上記処理を繰り返し行うことにより被乗数Ａと乗数Ｂとのモンゴメリ積（数式４）を計算する方法である。この方法においては前処理として乗数Ｂの倍数を必要とするが、２j倍の値に対しては結線の変更によるシフトを用い、その他の値に対しては前処理として計算しておかなければならない。
本発明による第二の実施例を拡張する場合には、メッセージＭのｅ乗の計算(Ｃ＝Ｍe)において新たなレジスタ（Ｔ１及びＴ２）を設けたが、これらのレジスタと暫定値ｕとの桁合わせを行う後処理も複数ビット分行わなければならない。
また、本発明の第三の実施例も更に一般的に拡張することができる。被乗数Ａの下位ｍビット（ｍは２以上の整数）の値と乗数Ｂを用いて暫定剰余ｕに部分積{Σ(Ａj*Ｂ) *２j  (j=0,,,m-1)}を加算する回路において、法Ｎの倍数{Σ(sj*Ｎ) *２j  (j=0,,,m-1)}を加算することにより前記暫定剰余ｕの下位ｍビットを０にし、その後前記暫定剰余ｕの下位ｍビットの右シフトを行い、上記処理を繰り返し行うことにより被乗数Ａと乗数Ｂとのモンゴメリ積（数式４）を計算する方法である。この方法においても前処理として法Ｎの倍数を必要とするが、２j倍の値には結線の変更によるシフトを用い、その他の値は前処理により計算しておかなければならない。
【００２４】
【発明の効果】
本発明による第一の実施例によれば、モンゴメリ積Montを計算するに際し従来の２進シフト加算法は１ビット毎の処理で能率が悪かったことから、第一の実施例において複数ビットを同時処理する方法を新たに提案した。その結果、モンゴメリ積Montの計算を従来法のおよそ複数倍に高速化することができ、かつ、モンゴメリ法のメリットを享受することができた。本発明による第二の実施例によれば、メッセージＭのｅ乗の計算(Ｃ＝Ｍe)において、新たなレジスタ（Ｔ１及びＴ２）を設けて当該計算の実質的な高速化を計る方法を考えることができた。本発明による第三の実施例によれば、更に、法Ｎの複数倍の値を加算することにより処理回路の段数を減じて前記第二の実施例よりも回路量と消費電力の削減を達成することができた。また、第一の実施例と同様に、モンゴメリ積Montの計算を従来法のおよそ複数倍に高速化することができ、かつ、モンゴメリ法のメリットを享受することができた。
【図面の簡単な説明】
【図１】本発明の第一の実施例による積Ｍｏｎｔを計算する回路構成図である。
【図２】数値３Ｂの計算を行うときの計算を示す図表である。
【図３】本発明の第一の実施例の制御回路の１ビット分の回路図である。
【図４】本発明の第二の実施例によるメッセージＭのｅ乗の計算をする回路構成図である。
【図５】モンゴメリ積Ｍｏｎｔを計算する際の計算手順を示した図である。
【図６】モンゴメリ積Ｍｏｎｔを計算する際の後処理の内容を示した図である。
【図７】図６の制御回路の１ビット分の回路図である。
【図８】本発明の第三の実施例によるメッセージＭのｅ乗の計算をする回路構成図である。
【図９】図８の制御回路の１ビット分の回路図である。
【図１０】数値３Ｎの計算を示す図表である。
【図１１】モンゴメリ積Ｍｏｎｔを計算する際の後処理の内容を示した図である。
【符号の説明】
１０１、１０２、１０３  レジスタ
１０４                  ２ビット右シフトレジスタ
１０５                  マルチプレクサ
１０６、１０７、１１２  加算器
１１０、１１３          １ビット右シフタ
１０９、１１１          ＡＮＤゲート
１０８、１１４          レジスタ
１１５、１１６          処理回路
６０１、６０２、６０３  レジスタ
６０４                  ２ビット右シフトレジスタ
６０８、６１４、６１７、６１８  レジスタ
６０６                  加算器
６１５、６１６          処理回路
６０５、６１９、６２０  マルチプレクサ
８０１、８０２、８０３  レジスタ
８０４                  ２ビット右シフトレジスタ
８０６、８０７          加算器
８０５、８１９、８２０、８２４  レジスタ
８０８                  ２ビット右シフタ
８１４、８１７、８１８  レジスタ
８１５                  処理回路
８２１、８２２、８２３  レジスタ
１２１、６３１、８３１  制御回路１１６の１ビット分の回路
１２２、６３２、８３２  全加算器ＦＡ
１２３、６３３、８３３  マルチプレクサ
１２４、６３４          ＡＮＤゲート
６３５                  ＥＯＲゲート
【図１】
0003576155.tif 000005
【図２】
0003576155.tif 000006
【図３】
0003576155.tif 000007
【図４】
0003576155.tif 000008
【図５】
0003576155.tif 000009
【図６】
0003576155.tif 000010
【図７】
0003576155.tif 000011
【図８】
0003576155.tif 000012
【図９】
0003576155.tif 000013
【図１０】
0003576155.tif 000014
【図１１】
0003576155.tif 000015