(57)【要約】【課題】  モンゴメリ（Montgomery）演算での積和演算での多倍長の減算処理の実行回数を削減し、トータルの演算サイクル数を削減する構成を提供する。【解決手段】  モンプロ演算プロセスにおける中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせを判別し、該判別データに基づいて、モンプロ演算式における値ｕの算出式を変更して実行する構成とするとともに、ｕの算出において多倍長の減算処理を不要とした式に基づく処理の実行確率を高めた。ｕ＜Ｒが示される場合のみならず、ｕ＞Ｎであることが示される場合においても、モンプロ（MonPro）演算における減算処理を省略することが可能となり、演算の高速化が実現される。【選択図】  図８
2005031472.tif 000002
【特許請求の範囲】
【請求項１】
メッセージ文をＭ，暗号文をＣ、公開鍵をｅ、秘密鍵をｄ、剰余数をＮとし、
暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ
復号化：Ｍ＝Ｃｄ ｍｏｄ Ｎ
により暗号化・復号化を行うＲＳＡ暗号においてモンゴメリ法を適用し、ＲをＮより大きい２のべき乗値、Ｎ'＝−Ｎ−１ｍｏｄＲとして、下記演算式［演算式Ａ］［演算式１］に従ったモンプロ演算を実行する演算処理方法であり、
［演算式Ａ］
ＭｏｎＰｒｏ（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*
ｍ＝ｔ×Ｎ' mod Ｒ
［演算式１］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
if  Carry＝１ then return ｕ−Ｎ
else  return  ｕ
上記モンプロ演算における中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせを判別し、該判別データに基づいて、上記式における値ｕの算出式を変更して実行することを特徴とする演算処理方法。
【請求項２】
前記演算処理方法において、
前記［演算式Ａ］中のｔ，ｍの上位ビットの組み合わせを判別し、該判別データに基づいてｕ＞Ｎであると判定される場合に、
モンプロ演算のｕの算出を、下記［演算式２］
［演算式２］
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
に従って実行し、
ｕ＜Ｒであると判定される場合に、
モンプロ演算のｕの算出を、下記［演算式３］
［演算式３］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
に従って実行することを特徴とする請求項１に記載の演算処理方法。
【請求項３】
ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（１，１）であるとき、
ｕ＜Ｒであると判定し、モンプロ演算のｕの算出を、前記［演算式３］に従って実行し、
ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（０，０）であるとき、
ｕ＞Ｎであると判定し、モンプロ演算のｕの算出を、前記［演算式２］に従って実行することを特徴とする請求項２に記載の演算処理方法。
【請求項４】
前記演算処理方法は、
ｔ，ｍの最上位ビットまたは上位複数ビットの組み合わせに基づいて、ｕ＞Ｎであると判定されるか、ｕ＜Ｒであると判定されるか、いずれとも判定できないかを判断し、
ｕ＞Ｎであると判定される場合には、モンプロ演算のｕの算出を、前記［演算式２］に従って実行し、
ｕ＜Ｒであると判定される場合には、モンプロ演算のｕの算出を、前記［演算式３］に従って実行し、
いずれとも判定できない場合には、モンプロ演算を、前記［演算式１］に従って実行することを特徴とする請求項２に記載の演算処理方法。
【請求項５】
メッセージ文をＭ，暗号文をＣ、公開鍵をｅ、秘密鍵をｄ、剰余数をＮとし、
暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ
復号化：Ｍ＝Ｃｄ ｍｏｄ Ｎ
により暗号化・復号化を行うＲＳＡ暗号において、モンゴメリ法を適用し、ＲをＮより大きい２のべき乗値、Ｎ'＝−Ｎ−１ｍｏｄＲとして、下記演算式［演算式Ａ］［演算式１］に従ったモンプロ演算を実行する演算処理装置であり、
［演算式Ａ］  ＭｏｎＰｒｏ（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*
ｍ＝ｔ×Ｎ' mod Ｒ
［演算式１］  ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
if  Carry＝１ then return ｕ−Ｎ
else  return  ｕ
前記［演算式１］における値ｕの算出処理を実行する乗算器および加算器を有するとともに、前記乗算器の一方のデータ入力段に反転器およびセレクタを設けた演算部と、
前記モンプロ演算における中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせに基づいて、前記乗算器の一方の入力データを反転データまたは非反転データとして選択入力するように演算部に制御信号を出力する制御部と、
を有することを特徴とする演算処理装置。
【請求項６】
前記演算部は、さらに、
前記反転器およびセレクタ間に桁上げ（Ｃａｒｒｙ）信号による＋１処理を実行する加算器を有し、
前記制御部は、前記乗算器入力が共に最下位ワードである場合に、前記加算器による桁上げ（Ｃａｒｒｙ）を実行し、該桁上げ処理後のデータを前記乗算器に入力するように前記演算部の制御を実行する構成を有することを特徴とする請求項５に記載の演算処理装置。
【請求項７】
前記演算部はさらに、
前記乗算器と加算器の間に反転・非反転制御回路を有し、
前記モンプロ演算における中間値として取得されるｔ，ｍの値を構成する上位ビットの組合せに基づいて、
前記乗算器の出力データを反転データまたは非反転データとして前記加算器の一方へ選択入力するように演算部に制御信号を出力する制御部と、
を有することを特徴とする請求項５に記載の演算処理装置。
【請求項８】
前記制御部は、
前記［演算式Ａ］中のｔ，ｍの上位ビットの組み合わせを判別し、該判別データに基づいてｕ＞Ｎであると判定される場合に、
モンプロ演算のｕの算出を、下記［演算式２］
［演算式２］
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
に従って実行するように前記演算部を制御し、
ｕ＜Ｒであると判定される場合に、
モンプロ演算のｕの算出を、下記［演算式３］
［演算式３］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
に従って実行するように、前記演算部の制御を実行する構成であることを特徴とする請求項５乃至７いずれかに記載の演算処理装置。
【請求項９】
前記制御部は、
ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（１，１）であるとき、
ｕ＜Ｒであると判定し、モンプロ演算のｕの算出を、前記［演算式３］に従って実行するように前記演算部を制御し、
ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（０，０）であるとき、
ｕ＞Ｎであると判定し、モンプロ演算のｕの算出を、前記［演算式２］に従って実行するように前記演算部の制御を実行する構成であることを特徴とする請求項８に記載の演算処理装置。
【請求項１０】
前記制御部は、
ｔ，ｍの最上位ビットまたは上位複数ビットの組み合わせに基づいて、ｕ＞Ｎであると判定されるか、ｕ＜Ｒであると判定されるか、いずれとも判定できないかを判定し、
ｕ＞Ｎであると判定される場合には、モンプロ演算のｕの算出を、前記［演算式２］に従って実行するように前記演算部を制御し、
ｕ＜Ｒであると判定される場合には、モンプロ演算のｕの算出を、前記［演算式３］に従って実行するように前記演算部を制御し、
いずれでもない場合には、モンプロ演算を、前記［演算式１］に従って実行するように前記演算部を制御する構成であることを特徴とする請求項９に記載の演算処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理演算の高速化手法に関する。特に、多倍長のべき剰余演算にモンゴメリ法を適用した演算における演算サイクル数を削減して演算の高速化を実現する演算処理方法、および演算処理装置に関する。
【背景技術】
【０００２】
データ記憶、データ通信などの際の情報漏えいを防止する技術として、データの暗号化がある。暗号化方式には、大別して共通鍵方式、公開鍵方式がある。共通鍵方式は、対称暗号方式ともよばれ、発信者、受信者の双方で共通の鍵を保有する。共通鍵方式の代表的な方法として、ＤＥＳ（Data Encryption Standard）がある。ＤＥＳアルゴリズムの特徴は、暗号化と復号化とをほぼ同じアルゴリズムで実行可能なことである。
【０００３】
この共通鍵暗号に対して、発信者と受信者の鍵を異なるものとした構成が公開鍵方式または非対称暗号方式である。公開鍵暗号方式では、暗号化、復号化に共通の鍵を用いる共通鍵暗号方式と異なり、秘密に保つ必要のある秘密鍵は、特定の１人が持てばよいため鍵の管理において有利である。ただし、公開鍵暗号方式は共通鍵暗号方式に比較してデータ処理速度が遅く、一般には、共通鍵暗号の秘密鍵の配送、ディジタル署名等のデータ量の少ない対象に多く用いられている。公開鍵暗号方式の代表的なものにはＲＳＡ（Rivest-Shamir-Adleman）暗号がある。これは非常に大きな２つの素数（例えば１５０桁）の積を用いるものであり、大きな２つの素数（例えば１５０桁）の積の素因数分解する処理の困難さを利用している。
【０００４】
公開鍵暗号方式では、不特定多数に公開鍵を使用可能とする構成であり、配布する公開鍵が正当なものであるか否かを証明する証明書、いわゆる公開鍵証明書を使用する方法が多く用いられている。例えば、利用者Ａが公開鍵、秘密鍵のペアを生成して、生成した公開鍵を認証局に対して送付して公開鍵証明書を認証局から入手する。利用者Ａは公開鍵証明書を一般に公開する。不特定のユーザは公開鍵証明書から所定の手続きを経て公開鍵を入手して文書等を暗号化して利用者Ａに送付する。利用者Ａは秘密鍵を用いて暗号化文書等を復号する、等のシステムである。また、利用者Ａは、秘密鍵を用いて文書等に署名を付け、不特定のユーザが公開鍵証明書から所定の手続きを経て公開鍵を入手して、その署名の検証を行なうシステムである。
【０００５】
公開鍵証明書は、公開鍵暗号方式における認証局あるいは発行局（ＣＡ：Certificate AuthorityまたはＩＡ：Issuer Authority）が発行する証明書であり、ユーザが自己のＩＤ、公開鍵等を認証局に提出することにより、認証局側が認証局のＩＤや有効期限等の情報を付加し、さらに認証局による署名を付加して作成される証明書である。
【０００６】
上述のＲＳＡ暗号では、メッセージ文を"Ｍ"，暗号文を"Ｃ"、公開鍵を"ｅ"、秘密鍵を"ｄ"、剰余数を"Ｎ"としたとき、
暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ
復号化：Ｍ＝Ｃｄ ｍｏｄ Ｎ
により暗号化・復号化をおこなう。この演算は、例えば１０２４［ｂｉｔ］のＲＳＡ暗号の暗号化の場合、公開鍵をｅ＝Σｉ＝０１０２３ｅｉ・２ｉとした場合、暗号化は以下の手順で行なわれる。
Ｃ＝１
ｆｏｒｉ＝１０２３ ｔｏ ０
Ｃ：＝Ｃ×Ｃ ｍｏｄ Ｎ
ｉｆ ｅｉ＝１ then Ｃ：＝Ｃ×Ｍ ｍｏｄ Ｎ
ｎｅｘｔ ｉ
なお、上記暗号化演算フローで、［：＝］は、右辺の演算結果を左辺の変数に代入する事を表す。
【０００７】
このような暗号化演算を実行する暗号処理モジュールとしては、ＩＣ等の演算処理装置が用いられる。ＩＣは半導体によって構成され、暗号演算の実行時には、演算処理シーケンスに従った電気的な処理を行うことになる。従って、このような半導体モジュールにおいて暗号処理が実行される際の電力消費を解析することで、暗号処理手順が解析されてしまうという恐れがある。暗号解読攻撃としては、処理時間を解析することにより秘密情報を推定するタイムアタック［Ｔｉｍｉｎｇ  ａｔｔａｃｋ（ＴＡ）］、暗号処理時の消費電力の観測により秘密情報を推定するシンプルパワー解析［Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ（ＳＰＡ）］、さらに、大量のデータに対する暗号処理における消費電力を測定し、それらの測定データを統計的に解析することにより秘密情報を推定する差分電力解析［Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ（ＤＰＡ）］等がある。
【０００８】
これらの攻撃に対する耐性を高めるために、暗号処理演算シーケンス中にダミー演算を挿入し、解析困難性を高める手法が知られている。例えば、上述のＲＳＡ暗号化において、ダミー演算を挿入した演算手順は、以下の様になる。
Ｃ＝１
ｆｏｒ ｉ＝１０２３ ｔｏ ０
Ｃ：＝Ｃ×Ｃ ｍｏｄ Ｎ
Ｄ：＝Ｃ×Ｍ ｍｏｄ Ｎ
ｉｆ ｅｉ＝１ then Ｃ：＝Ｄ
ｎｅｘｔ ｉ
【０００９】
上記式において、ｅｉ＝０のときの［Ｄ:＝Ｃ×Ｍ  mod Ｎ］の演算がダミーの演算処理である。この演算は、例えばビット長が１０２４bitと大きな数値であるため、剰余演算に時間がかかるという問題がある。
【００１０】
ＲＳＡ暗号方式では、鍵長の長いこと、演算速度が遅いという問題がある。ＲＳＡ暗号の演算時間を短縮する方法の１つとしてモンゴメリ（Montgomery）法が使われる。このモンゴメリ法は、Ｎによる剰余演算の代わりに、Ｎより大きい２のべき乗値での剰余演算を行なう。２のべき乗値による剰余演算は、演算処理装置においてはビットシフト処理として実現可能であり、演算サイクル数は大幅に削減される。
【００１１】
モンゴメリ（Montgomery）法を用いた１０２４ｂｉｔのＲＳＡ暗号の演算では、
Ｒ＝２１０２４、Ｎ'＝−Ｎ−１ ｍｏｄ Ｒとしたとき、
タイムアタック（Ｔｉｍｅ  Ａｔｔａｃｋ）対策を施した演算フローは、以下のようになる。
ｘ＊：＝Ｒ ｍｏｄ Ｎ
Ｍ＊：＝Ｍ×Ｒ ｍｏｄ Ｎ
ｆｏｒ  ｉ＝１０２３ ｔｏ ０
ｘ＊：＝MonPro（ｘ＊，ｘ＊）
ｙ＊：＝MonPro（Ｍ＊，ｘ＊）
ｉｆ  ｅｉ＝１ then ｘ＊：＝ｙ＊
ｎｅｘｔ  ｉ
Ｃ：＝MonPro（１，ｘ＊）
【００１２】
ここで、モンプロ（MonPro）演算、すなわち、MonPro（ａ＊，ｂ＊）は、下記の演算処理である。
【００１３】
MonPro（ａ＊，ｂ＊）：
ｔ＝ａ＊×ｂ＊
ｍ＝ｔ×Ｎ' ｍｏｄ Ｒ
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
ｉｆ  ｕ≧Ｎ then return ｕ−Ｎ
else return ｕ
【００１４】
乗算器のビット幅をω［ｂｉｔ］、データのワード数をＤＬ（＝１０２４／ω）、ｒ＝２ω、演算の途中で出てくる中間値"ｔ"をｔ＝Σi=0DL-１ｔｉ・２ω・ｉ、パラメータ"Ｎ'"をＮ'＝Σi=0DL-１Ｎ'ｉ・２ω・ｉとした時、モンプロ（MonPro）演算、すなわち、MonPro（ａ＊，ｂ＊）は、下記の演算処理としても示される。
MonPro（ａ＊，ｂ＊）：
ｔ＝ａ＊×ｂ＊＝Σi=02×DL-１ｔｉ・２ω・ｉ
ｆｏｒ ｉ＝０ ｔｏ ＤＬ−１
ｍ＝ｔ０×Ｎ'０ ｍｏｄ ｒ
ｔ：＝（ｔ＋ｍ×Ｎ）／ｒ
ｎｅｘｔ  ｉ
ｉｆ    ｔ≧Ｎ then return ｔ−Ｎ
else  return ｔ
となる。
【００１５】
このモンプロ（MonPro）演算において、
ｉｆ  ｔ≧Ｎ then ｔ：＝ｔ−Ｎ
の処理のために、"ｔ"と"Ｎ"の大小関係を取得することが求められ、以下の様な補足演算を実行することが必要となる。
Ｔｅｍｐ  ＝ｔ−Ｎ
ｉｆ  Ｔｅｍｐ≧０  then return Ｔｅｍｐ
else  return ｔ
【００１６】
このように、モンゴメリ（Montgomery）演算を行なう場合に実行されるモンプロ（MonPro）演算では、演算結果"ｔ"と剰余数"Ｎ"の大小判定のための補足演算として、最後に多倍長の減算処理を行なうことが必要となる。１回の多倍長減算のサイクル数は、剰余数のビット幅が１０２４[bit]で加算器のビット幅が３２bitの場合、最低でも１０２４／３２＝３２サイクル[cycle]必要となる。
【００１７】
タイムアタック（Time Attack）のためのダミー演算を含む演算フローでは、各ループで２回の上記したモンプロ（MonPro）演算を行なうことが必要となるため、暗号化・復号化の度に２×１０２４＝２０４８回の多倍長減算が必要となり、３２×２０４８＝約６５K cycleの、演算サイクル数・演算時間が増加することになる。
【００１８】
モンゴメリ（Montgomery）法を用いた演算の場合、演算ループの途中であれば、演算の途中結果"ｘ*"，" ｙ*"が剰余数"Ｎ"より大きくても、パラメータ"Ｒ"より小さければ最終的な演算結果に影響を与えないことが特許文献１に示されている。なお、パラメータ"Ｒ"は、Ｒ＝２１０２４で示される。
【００１９】
特許文献１は、モンゴメリ（Montgomery）法を用いた演算の場合、演算ループの途中であれば、演算の途中結果"ｘ*"，" ｙ*"が剰余数"Ｎ"より大きくても、パラメータ"Ｒ"より小さければ最終的な演算結果に影響を与えないことを数学的に示している。すなわち、モンプロ（MonPro）演算のフローにおいて、中間値ｔと剰余数Ｎとの比較、すなわち、
ｉｆ  ｔ≧Ｎ then  return  ｔ−Ｎ
ではなく、中間値ｔとパラメータＲとの比較、すなわち、
ｉｆ  ｔ≧Ｒ then  return  ｔ−Ｎ
を行なう手法を開示している。
【００２０】
この手法を適用する場合、直前の積和演算でのキャリーの有無でｔとＲの大小関係が得られるため、大小比較のための引算は不要で、したがって、ｔ＜Ｒが成立する場合は、一切の多倍長減算は必要なくなり、ある程度演算サイクル数・演算時間を短縮することができる。
【００２１】
しかし、上記手法を適用した場合においても、ｔ＜Ｒが成立しない場合、すなわちｔ≧Ｒの場合には、多倍長の減算が必要となり、これらの多倍長減算による演算サイクル数・演算時間の増加という問題を解決するものには至っていない。
【特許文献１】特開平９−２７４５６０
【発明の開示】
【発明が解決しようとする課題】
【００２２】
本発明は、上記、問題点に鑑みてなされたものであり、モンゴメリ（Montgomery）法を用いた暗号処理演算において、演算サイクル数・演算時間を短縮した演算処理方法、および演算処理装置を提供するものである。
【００２３】
本発明は、特に、モンゴメリ（Montgomery）法を用いた暗号処理におけるモンプロ（MonPro）演算における多倍長減算の実行回数を削減することにより演算サイクル数を削減し、演算時間短縮を実現する演算処理方法、および演算処理装置を提供するものである。
【課題を解決するための手段】
【００２４】
本発明の第１の側面は、
メッセージ文をＭ，暗号文をＣ、公開鍵をｅ、秘密鍵をｄ、剰余数をＮとし、
暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ
復号化：Ｍ＝Ｃｄ ｍｏｄ Ｎ
により暗号化・復号化を行うＲＳＡ暗号においてモンゴメリ法を適用し、Ｒを２のべき乗、Ｎ'＝−Ｎ−１ｍｏｄＲとして、下記演算式［演算式Ａ］［演算式１］に従ったモンプロ演算を実行する演算処理方法であり、
［演算式Ａ］
ＭｏｎＰｒｏ（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*
ｍ＝ｔ×Ｎ' mod Ｒ
［演算式１］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
if  Carry＝１ then return ｕ−Ｎ
else  return  ｕ
上記モンプロ演算における中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせを判別し、該判別データに基づいて、上記式における値ｕの算出式を変更して実行することを特徴とする演算処理方法にある。
【００２５】
さらに、前記演算処理方法の一実施態様において、前記［演算式Ａ］中のｔ，ｍの上位ビットの組み合わせを判別し、該判別データに基づいてｕ＞Ｎであると判定される場合に、モンプロ演算のｕの算出を、下記［演算式２］
［演算式２］
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
に従って実行し、
ｕ＜Ｒであると判定される場合に、
モンプロ演算を、下記［演算式３］
［演算式３］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
に従って実行することを特徴とする。
【００２６】
さらに、前記演算処理方法の一実施態様において、ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（１，１）であるときｕ＜Ｒであると判定し、モンプロ演算のｕの算出を、前記［演算式３］に従って実行し、ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（０，０）であるとき、ｕ＞Ｎであると判定し、モンプロ演算を、前記［演算式２］に従って実行することを特徴とする。
【００２７】
さらに、前記演算処理方法の一実施態様において、前記演算処理方法は、ｔ，ｍの最上位ビットまたは上位複数ビットの組み合わせに基づいて、ｕ＞Ｎであると判定されるか、ｕ＜Ｒであると判定されるか、いずれとも判定できないかを判定し、ｕ＞Ｎであると判定される場合には、モンプロ演算のｕの算出を、前記［演算式２］に従って実行し、ｕ＜Ｒあると判定される場合には、モンプロ演算のｕの算出を、前記［演算式３］に従って実行し、いずれとも判定できない場合には、モンプロ演算のｕの算出を、前記［演算式１］に従って実行することを特徴とする。
【００２８】
さらに、本発明の第２の側面は、
メッセージ文をＭ，暗号文をＣ、公開鍵をｅ、秘密鍵をｄ、剰余数をＮとし、
暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ
復号化：Ｍ＝Ｃｄ ｍｏｄ Ｎ
により暗号化・復号化を行うＲＳＡ暗号において、モンゴメリ法を適用し、ＲをＮより大きい２のべき乗値、Ｎ'＝−Ｎ−１ｍｏｄＲとして、下記演算式［演算式Ａ］［演算式１］に従ったモンプロ演算を実行する演算処理装置であり、
［演算式Ａ］
ＭｏｎＰｒｏ（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*
ｍ＝ｔ×Ｎ' mod Ｒ
［演算式１］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
if  Carry＝１ then return ｕ−Ｎ
else  return  ｕ
前記［演算式１］における値ｕの算出処理を実行する乗算器および加算器を有するとともに、前記乗算器の一方のデータ入力段に反転器およびセレクタを設けた演算部と、
前記モンプロ演算における中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせに基づいて、前記乗算器の一方の入力データを反転データまたは非反転データとして選択入力するように演算部に制御信号を出力する制御部と、
を有することを特徴とする演算処理装置にある。
【００２９】
さらに、前記演算処理装置の一実施態様において、前記演算部は、さらに、前記反転器およびセレクタ間に桁上げ（Ｃａｒｒｙ）信号による＋１処理を実行する加算器を有し、前記制御部は、前記乗算器入力が共に最下位ワードである場合に、前記加算器による桁上げ（Ｃａｒｒｙ）を実行し、該桁上げ処理後のデータを前記乗算器に入力するように前記演算部の制御を実行する構成を有することを特徴とする。
【００３０】
さらに、前記乗算器と加算器の間に反転・非反転制御回路を有し、前記モンプロ演算における中間値として取得されるｔ，ｍの値を構成する上位ビットの組合せに基づいて、前記乗算器の出力データを反転データまたは非反転データとして前記加算器の一方へ選択入力するように演算部に制御信号を出力する制御部と、
を有することを特徴とする演算処理装置にある。
【００３１】
さらに、前記演算処理装置の一実施態様において、前記制御部は、前記［演算式Ａ］中のｔ，ｍの上位ビットの組み合わせを判別し、該判別データに基づいてｕ＞Ｎであると判定される場合に、モンプロ演算を、下記［演算式２］
［演算式２］
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
に従って実行するように前記演算部を制御し、
ｕ＜Ｒであると判定される場合に、
モンプロ演算を、下記［演算式３］
［演算式３］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
に従って実行するように、前記演算部の制御を実行する構成であることを特徴とする。
【００３２】
さらに、前記演算処理装置の一実施態様において、前記制御部は、ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（１，１）であるとき、ｕ＜Ｒであると判定し、モンプロ演算のｕの算出を、前記［演算式３］に従って実行するように前記演算部を制御し、ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（０，０）であるとき、ｕ＞Ｎであると判定し、モンプロ演算のｕの算出を、前記［演算式２］に従って実行するように前記演算部の制御を実行する構成であることを特徴とする。
【００３３】
さらに、前記演算処理装置の一実施態様において、前記制御部は、ｔ，ｍの最上位ビットまたは上位複数ビットの組み合わせに基づいて、ｕ＞Ｎであると判定されるか、ｕ＜Ｒであると判定されるか、いずれとも判定できないかを判定し、ｕ＞Ｎである場合には、モンプロ演算のｕの算出を、前記［演算式２］に従って実行するように前記演算部を制御し、ｕ＜Ｒである場合には、モンプロ演算のｕの算出を、前記［演算式３］に従って実行するように前記演算部を制御し、いずれとも判定できない場合には、モンプロ演算のｕの算出を、前記［演算式１］に従って実行するように前記演算部を制御する構成であることを特徴とする。
【発明の効果】
【００３４】
本発明の構成によれば、モンプロ演算プロセスにおける中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせを判別し、該判別データに基づいて、モンプロ演算式における値ｕの算出式を変更して実行する構成とするとともに、ｕの算出において多倍長の減算処理を不要とした式に基づく処理の実行確率を高めたので、モンゴメリ（Montgomery）演算での積和演算での多倍長の減算処理の実行回数が削減され、トータルの演算サイクル数の削減が実現される。
【００３５】
本発明の構成によれば、ｕ＜Ｒの場合のみならず、ｕ＞Ｎであることが示される場合においても、モンプロ（MonPro）演算における減算処理を省略することが可能となり、演算の高速化が実現される。
【発明を実施するための最良の形態】
【００３６】
以下、本発明の演算処理方法、および演算処理装置について詳細に説明する。
【００３７】
説明は、以下の項目に分けて行う。
１．本発明の演算シーケンス
２．具体的な演算プロセス例
３．本発明の演算処理および装置と従来構成との比較
【００３８】
［１．本発明の演算シーケンス］
まず、本発明の演算処理装置、および演算処理方法において適用する運算シーケンスについて説明する。本発明は、ＲＳＡ暗号の演算時間の短縮手法として知られているモンゴメリ（Ｍｏｎｔｇｏｍｅｒｙ）法において実行するモンプロ（MonPro）演算において実行される多倍長減算の実行回数を削減することにより演算サイクル数を削減し、演算時間短縮を実現したものである。
【００３９】
従来技術の欄においても説明したように、モンゴメリ（Montgomery）法を用いた１０２４ｂｉｔのＲＳＡ暗号の演算は、Ｒ＝２１０２４、Ｎ'＝−Ｎ−１ ｍｏｄ Ｒとしたとき、タイムアタック（Ｔｉｍｅ  Ａｔｔａｃｋ）対策を施した演算フローは、以下のようになる。
ｘ＊：＝Ｒ ｍｏｄ Ｎ
Ｍ＊：＝Ｍ×Ｒ ｍｏｄ Ｎ
ｆｏｒ  ｉ＝１０２３ ｔｏ ０
ｘ＊：＝MonPro（ｘ＊，ｘ＊）
ｙ＊：＝MonPro（Ｍ＊，ｘ＊）
ｉｆ  ｅｉ＝１ then ｘ＊：＝ｙ＊
ｎｅｘｔ  ｉ
Ｃ：＝MonPro（１，ｘ＊）
【００４０】
ここで、モンプロ（MonPro）演算、すなわち、MonPro（ａ＊，ｂ＊）は、下記の演算処理として実行される。
【００４１】
MonPro（ａ＊，ｂ＊）：
ｔ＝ａ＊×ｂ＊
ｍ＝ｔ×Ｎ' ｍｏｄ Ｒ
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
ｉｆ  ｕ≧Ｎ then return ｕ−Ｎ
else return ｕ
【００４２】
ここで、乗算器のビット幅をω［ｂｉｔ］、データのワード数をＤＬ（＝１０２４／ω）、ｒ＝２ω、演算の途中で出てくる中間値"ｔ"をｔ＝Σi=02×DL-1ｔｉ・２ω・ｉ、パラメータ"Ｎ'"をＮ'＝Σi=0DL-1Ｎ'ｉ・２ω・ｉとした時、
MonPro（ａ＊，ｂ＊）：
ｔ＝ａ＊×ｂ＊
ｆｏｒ ｉ＝０ ｔｏ ＤＬ−１
ｍ＝ｔ０×Ｎ'０ ｍｏｄ ｒ
ｔ：＝（ｔ＋ｍ×Ｎ）／ｒ
ｎｅｘｔ  ｉ
ｉｆ    ｔ≧Ｎ then return ｔ−Ｎ
else    return ｔ
とも表わされる。
【００４３】
このモンプロ（MonPro）演算において、
ｉｆ  ｔ≧Ｎ then ｔ：＝ｔ−Ｎ
の演算プロセスでは、"ｔ"と"Ｎ"の大小関係の取得のために、以下の様な補足演算が必要となり、実行される。
Ｔｅｍｐ  ＝ｔ−Ｎ
ｉｆ  Ｔｅｍｐ≧０  then return Ｔｅｍｐ
else  return ｔ
【００４４】
このように、モンゴメリ（Montgomery）演算を行なう場合に実行されるモンプロ（MonPro）演算では、演算結果"ｔ"と剰余数"Ｎ"の大小判定のための補足演算として、最後に多倍長の減算を行なうことが必要となる。１回の多倍長減算のサイクル数は、剰余数のビット幅が１０２４[bit]で加算器のビット幅ωが３２bitの場合、最低でも１０２４／３２＝３２サイクル[cycle]必要となる。
【００４５】
本発明の演算シーケンスでは、上述のモンプロ（MonPro）演算における多倍長減算処理の実行回数を削減するものである。
【００４６】
本発明の演算シーケンスについて説明する。従来技術の欄で説明したように、モンゴメリ（Montgomery）法を用いた演算の場合、演算ループの途中であれば、演算の途中結果"ｘ*"，" ｙ*"が剰余数"Ｎ"より大きくても、パラメータ"Ｒ"より小さければ最終的な演算結果に影響を与えないことが証明されている（特開平９−２７４５６０）。すなわち、モンプロ（MonPro）演算のフローにおける補足演算において、中間値ｔと剰余数Ｎとの比較を、
ｉｆ  ｔ≧Ｎ then  return  ｔ−Ｎ
ではなく、
中間値ｔとパラメータＲとの比較、すなわち、
ｉｆ  ｔ≧Ｒ then  return  ｔ−Ｎ
と設定して行なう手法が有効であることが示されている。
【００４７】
この手法を適用すると、モンゴメリ（Montgomery）演算として実行されるモンプロ（MonPro）演算は、下記のシーケンスに従って実行されることになる。
MonPro（ａ＊，ｂ＊）：
ｔ＝ａ＊×ｂ＊
ｍ＝ｔ×Ｎ' ｍｏｄ Ｒ
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
Ｔｅｍｐ＝ｕ−Ｎ
ｉｆ  ｕ≧Ｒ then return Ｔｅｍｐ（＝ｕ−Ｎ）
else  return  ｕ
【００４８】
本発明においては、さらに、上記モンプロ（MonPro）演算における中間値である下記の２値、すなわち、
ｔ＝ａ＊×ｂ＊と、
ｍ＝ｔ×Ｎ' ｍｏｄ Ｒ
これらｔ，ｍの上位ビット（ＭＳＢ〜数ビット）の値を調べ、ｔ，ｍの上位ビットの組合せに基づいて、以下に示す演算：［演算式１］〜［演算式３］のうちの１つを選択して実行する。この処理により、多倍長減算の実行回数を削減する。
【００４９】
［演算式１］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
if Carry=1 then return ｕ−Ｎ
［演算式２］
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
［演算式３］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
【００５０】
以下、上記［演算式１］〜［演算式３］のいずれかを選択して実行する本発明の演算処理について説明する。
【００５１】
上述したように、モンゴメリ（Montgomery）演算には、以下の演算式で示されるモンプロ演算が含まれる。
MonPro（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*              ・・・・・（数式１）
ｍ＝ｔ×Ｎ' mod Ｒ          ・・・（数式２）
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ         ・・（数式３）
if  Carry＝１ then return ｕ−Ｎ
else  return  ｕ    ・・（数式４）
【００５２】
ここで、ＲＳＡ暗号のビット数は、剰余数"Ｎ"のビット数"Ｌ"[bit] で規定されるが、これをワード数（１ワード＝ωビット）で表したものをＤＬ（＝Ｌ／ω）とするとき、Ｒ＝２ω・DL と設定する。そして、（数式１）で計算される"ｔ"は、ａ*（＜Ｎ）とｂ*（＜Ｎ）の積であるため、そのビット長は２×ω×ＤＬとなる。この時"ｔ"は、
ｔ＝ｔH×２ω・DL ＋ｔL＝ｔH×Ｒ＋ｔL・・・（数式５）
と表わせる。ｔHはｔのＲ以上のビット、ｔLはｔのＲ未満のビットである。
【００５３】
このとき、ｕとＮの比較において、
Temp1＝ｕ−Ｎ＝（ｔ＋ｍ×Ｎ）／Ｒ−Ｎ
＝（ｔH×Ｒ＋ｔL−（Ｒ−ｍ）×Ｎ）／Ｒ
＝ｔH＋ｔL／Ｒ−（Ｒ−ｍ）×Ｎ／Ｒ・・・（数式６）
となる。
【００５４】
また、ｕとＲの比較において、
Temp2＝ｕ−Ｒ＝（ｔ＋ｍ×Ｎ）／Ｒ−Ｒ
＝（ｔH×Ｒ＋ｔL＋ｍ×Ｎ）／Ｒ−Ｒ
＝ｍ×Ｎ／Ｒ−（Ｒ−ｔH−ｔL／Ｒ）・・・（数式７）
となる。
【００５５】
これらの式で、０≦ｔL＜Ｒであるため、０≦ｔL／Ｒ＜１である。従って、（数式６）のＴｅｍｐ１、と（数式７）のＴｅｍｐ２の式において、以下の関係式が成り立つ。
【００５６】
Temp1＝ｕ−Ｎ≧ｔH−（Ｒ−ｍ）×Ｎ／Ｒ・・（数式８）
Temp2＝ｕ−Ｒ＜ｍ×Ｎ／Ｒ−（Ｒ−ｔH−１）・・（数式９）
【００５７】
これらの式で、剰余数"Ｎ"の最上位ビット（ＭＳＢ）は"１"であるため、0.5＜Ｎ／Ｒ＜１である。（数式８）で、"ｔＨ"と"Ｒ−ｍ"の関係に基づき、
Ｔｅｍｐ１＞０
が示せる場合、ｕ＞Ｎであるため、（数式３）の"ｕ"の計算式の代わりに"ｕ−Ｎ"の計算を実行し、それを"ｕ"とすれば（数式４）の判定及び多倍長の減算を行なう必要がなくなる。
【００５８】
この場合、すなわち、"ｔＨ"と"Ｒ−ｍ"の関係に基づき、Temp1＞０が示され、ｕ＞Ｎであると判定される場合は、前述の
［演算式２］
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
を適用してモンプロ（MonPro）演算を実行する。
すなわち、モンプロ（MonPro）演算は、以下の処理となる。
MonPro（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*      ・・・・・・・・・・（数式１０）
ｍ＝ｔ×Ｎ' mod Ｒ    ・・・・・・・（数式１１）
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ  ・・（数式１２）
【００５９】
この場合、ｕはＮ以下となっているため、減算処理は不要である。（数式１２）は、"ｔ"から、"ｍ"の２の補数を取った値と"Ｎ"の乗算値を引き、その結果を"Ｒ"で割る（ビットシフト）事により演算結果を得る事ができる。この場合、"ｍ"の２の補数計算は、ビット反転と"１"の加算で実現できる。具体的な演算方法については後述する。
【００６０】
次に、Ｔｅｍｐ２を示す上記（数式９）で、"ｍ" と"Ｒ−ｔH−１"の関係に基づいて、
Ｔｅｍｐ２＝ｕ−Ｒ＜０、
すなわち、
ｕ＜Ｒ
であることが示される場合は、前述の
［演算式３］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
を適用してモンプロ（MonPro）演算を実行する。
すなわち、モンプロ（MonPro）演算は、以下の処理となる。
MonPro（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*  ・・・・・・・・（数式１３）
ｍ＝ｔ×Ｎ' mod Ｒ  ・・・・（数式１４）
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ ・・・（数式１５）
【００６１】
この場合、ｕはＲ以下となっている。ｕはＮ以上の場合もあるが、Ｒ以下であるため、この後に減算処理を行なわないで、この演算結果を次のモンプロ（MonPro）演算に用いても不具合は生じないため省略することができる。このことは、従来技術の欄で説明したように、特開平９−２７４５６０に示されている。
【００６２】
特開平９−２７４５６０においては、ｕ＜Ｒの場合においてのみ、モンプロ（MonPro）演算における減算処理、すなわち、
Ｔｅｍｐ＝ｕ−Ｎ
ｉｆ  ｕ≧Ｒ then return Ｔｅｍｐ（＝ｕ−Ｎ）
else  return  ｕ
を省略するものであったが、本発明の構成においては、"ｔＨ"と"Ｒ−ｍ"の関係に基づき、
Ｔｅｍｐ１＝ｕ−Ｎ＞０、すなわち、ｕ＞Ｎであることが示される場合においても、上記モンプロ（MonPro）演算における減算処理を省略することが可能となる。
【００６３】
本発明のモンプロ（MonPro）演算の実行シーケンスについて、図１を参照して説明する。ステップＳ１０１において、
ｔ＝ａ*×ｂ*＝ｔH×Ｒ＋ｔL
ｍ＝ｔ×Ｎ'  mod  Ｒ
としてそれぞれの値を算出する。上述した説明における（数式１）、（数式２）に相当する。
【００６４】
ステップＳ１０２において、演算プロセスにおける中間値に基づくｔＨ"と"Ｒ−ｍ"の上位ビットの比較に基づき、ｕ＞Ｎが成立するか否かを判定する。ｕ＞Ｎと判定される場合は、ステップＳ１０４において［演算式２］の演算、すなわち、
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
を実行する。
この演算処理においては、ｕ，Ｎの大小判定のための補足演算としての多倍長減算は不要となる。
【００６５】
ステップＳ１０２において、ｕ＞Ｎと判定されない場合は、ステップＳ１０３に進み、"ｍ" と"Ｒ−ｔH−１"の上位ビットの比較に基づいて、ｕ＜Ｒが成立するか否かを判定する。
【００６６】
ｕ＜Ｒが成立する場合は、ステップＳ１０５において［演算式３］の演算、すなわち、
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
を実行する。
この演算処理においては、ｕ，Ｎの大小判定のための補足演算としての多倍長減算は不要となる。
【００６７】
ステップＳ１０３において、ｕ＜Ｒと判定されない場合は、ステップＳ１０６に進み、［演算式１］の演算、すなわち、
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
Temp＝ｕ−Ｎ
if  Carry＝１ then return ｕ−Ｎ
else  return  ｕ
を実行する。
この［演算式１］の演算処理においてのみ、ｕ，Ｎの大小判定のための補足演算としての多倍長減算を実行することになる。
【００６８】
このように、本発明においては、ｕ＞Ｎと判定される場合、および、ｕ＜Ｒと判定される場合、いずれの場合においても、モンプロ（MonPro）演算における減算処理を省略することが可能となり、演算サイクル数が削減され、処理の高速化が実現される。
【００６９】
［２．具体的な演算プロセス例］
次に、本発明の演算処理の具体的な処理例について説明する。上述したように、本発明の演算シーケンスにおいては、モンプロ（MonPro）演算における中間値である下記の２値、すなわち、
ｔ＝ａ＊×ｂ＊と、
ｍ＝ｔ×Ｎ' ｍｏｄ Ｒ
これらｔ，ｍの上位ビット（ＭＳＢ〜数ビット）の値を調べ、ｔ，ｍの上位ビットの組合せに基づいて、前述の［演算式１］〜［演算式３］のうちの１つを選択して実行する。ｔ，ｍの上位ビットの組合せに基づいて、ｕ＞Ｎと判定される場合は［演算式２］が適用可能であり、ｕ＜Ｒであると判定される場合には、［演算式３］が適用可能であり、いずれの場合にも減算処理を省略することが可能となる。
【００７０】
以下、"ｔ"と"ｍ"の上位ビットの組合せに基づいて、［演算式１］〜［演算式３］を選択して実行する処理の具体例について説明する。以下、
（ａ）．"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせに基づく処理
（ｂ）．"ｔ"と"ｍ"の上位２ビットの組み合わせに基づく処理
（ｃ）．"ｔ"と"ｍ"の上位３ビットの組み合わせに基づく処理
の各処理例について説明する。
【００７１】
（ａ）"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせに基づく処理
【００７２】
"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせは、図２に示すように、ｔ＝０，１、ｍ＝０，１の２通り×２通りの組み合わせであり、全部で４通りの組み合わせがある。図２に示すように、"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせが（０，０）であれば、ｕ＜Ｒと判定され、（１，１）であれば、ｕ＞Ｎと判定され、これらの組み合わせの場合には、前述の［演算式２］または［演算式３］の適用が可能となり、減算処理を省略することができる。図中［？］の示された組み合わせ、すなわち、"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせが（０，１）または（１，０）の場合には、ｕ＜Ｒが成立する事もｕ＞Ｎが成立する事も示せないため、前述の［演算式１］を適用した処理、すなわち減算処理を伴う演算を実行することになる。
【００７３】
以下、"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の各組み合わせにおいて、ｕ＜Ｒまたはｕ＞Ｎが成立することが示される組み合わせ、または成立することが示されない組み合わせについて説明する。
【００７４】
前述したように、ＲＳＡ暗号のビット数は、剰余数"Ｎ"のビット数"Ｌ"[bit] で規定されるが、これをワード数（１ワード＝ωビット）で表したものをＬＤ（＝Ｌ／ω）とするとき、Ｒ＝２ω・DL と定義できる。そして、（数式１）で計算される"ｔ"は、ａ*（＜Ｎ）とｂ*（＜Ｎ）の積であるため、そのビット長は２×ω×ＤＬとなる。この時"ｔ"は、
ｔ＝ｔH×２ω・DL ＋ｔL＝ｔH×Ｒ＋ｔL
と表わせる。
ｔHはｔのＲ以上のビット、ｔLはｔのＲ未満のビットである。
【００７５】
ｔの最上位ビットが１である場合とは、ｔH＞２ω・DL −１である場合であり、ｔの最上位ビットが０である場合とは、ｔH＜２ω・DL −１である場合となる。同様に、ｍの最上位ビットが１である場合とは、ｍ＞２ω・DL −１である場合であり、ｍの最上位ビットが０である場合とは、ｍ＜２ω・DL −１である場合となる。以下、ｔ，ｍの最上位ビットの組み合わせが、（１，１）、（１，０）、（０，１）、（０，０）の場合に、ｕ＜Ｒまたはｕ＞Ｎが成立するか否かについて説明する。
【００７６】
（ａ−１）"ｔ"のＭＳＢ＝１"ｍ"のＭＳＢ＝１
この場合は、ｔH＞２ω・DL −１，ｍ＞２ω・DL −１の場合に相当する。
この場合、
Ｒ−ｍ ＜２ω・DL −２ω・DL −１＝２ω・DL −１
であり、
なおかつ、Ｎ／Ｒ＜１であるため、
ｔH ＞ （Ｒ−ｍ）×Ｎ／Ｒとなる。
この場合、（数式８）より、
ｕ＞Ｎとなる。
【００７７】
このように、"ｔ"のＭＳＢ＝１"ｍ"のＭＳＢ＝１の場合、ｕ＞Ｎが成立し、前述の［演算式２］の演算を実行可能であり、減算処理の省略が可能となる。
【００７８】
（ａ−２）"ｔ"のＭＳＢ＝１"ｍ"のＭＳＢ＝０
この場合は、ｔH ＞２ω・DL−１，ｍ ＜２ω・DL−１の場合に相当する。
この場合、
Ｒ−ｍ ＞２ω・DL −２ω・DL −１＝２ω・DL −１
であり、"ｔH "も"Ｒ−ｍ"も両方２ω・DL−１より大きい。
この場合、（数式８）より、"ｔH "と"ｍ"の最上位ビットだけではｕとＮの大小関係は判定できない。
また、
Ｒ−ｔH ＜２ω・DL −２ω・DL −１＝２ω・DL −１
であり、"ｍ"も"Ｒ−ｔH"も両方２ω・DL−１より小さい。この場合、（数式９）より、"ｔH "と"ｍ"の最上位ビットだけではｕとＲの大小関係は判定できない。
【００７９】
この場合、前述した［演算式１］で演算を実行することが必要となり、（数式３）の演算結果でキャリー（Carry）が発生した場合のみＮの減算処理を行なう。
【００８０】
（ａ−３）"ｔ"のＭＳＢ＝０"ｍ"のＭＳＢ＝１
この場合は、ｔH ＜２ω・DL−１，ｍ ＞２ω・DL−１の場合に相当する。
この場合、
Ｒ−ｍ ＜２ω・DL −２ω・DL −１＝２ω・DL −１
であり、"ｔH "も"Ｒ−ｍ"も両方２ω・DL−１より小さい。この場合、（数式８）より、"ｔH "と"ｍ"の最上位ビットだけではｕとＮの大小関係は判定できない。
また、
Ｒ−ｔH ＞２ω・DL −２ω・DL −１＝２ω・DL −１
であり、"ｍ"も"Ｒ−ｔH"も両方２ω・DL−１より大きい。この場合、（数式９）より、"ｔH "と"ｍ"の最上位ビットだけではｕとＲの大小関係は判定できない。
【００８１】
この場合、前述した［演算式１］で演算を実行することが必要となり、（数式３）の演算結果でキャリー（Carry）が発生した場合のみＮの減算処理を行なう。
【００８２】
（ａ−４）"ｔ"のＭＳＢ＝０"ｍ"のＭＳＢ＝０
この場合は、ｔH ＜２ω・DL−１，ｍ ＜２ω・DL−１  の場合に相当する。
この場合、
Ｒ−ｔH ＞２ω・DL −２ω・DL −１＝２ω・DL −１
であり、"ｍ "は２ω・DL−１以下で、Ｎ／Ｒ＜１より"ｍ×Ｎ／Ｒ"は２ω・DL−１以下である。一方、"Ｒ−ｔH "は２ω・DL −１以上であるため、（数式９）式より、
ｕ＜Ｒ
となる。
【００８３】
このように、"ｔ"のＭＳＢ＝０"ｍ"のＭＳＢ＝０の場合、ｕ＜Ｒが成立し、前述の［演算式３］の演算を実行可能であり、減算処理の省略が可能となる。
【００８４】
以上、説明した、"ｔH"と "ｍ"の最上位１ビットに着目したときの、"ｕ"と "Ｎ" または"Ｒ"との大小関係を示したのが、図２である。
【００８５】
図２に示すように、"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせが（０，０）であれば、ｕ＜Ｒが示され、（１，１）であれば、ｕ＞Ｎが示され、これらの組み合わせの場合には、前述の［演算式２］または［演算式３］の適用が可能となり、減算処理を省略することができる。図中［？］の示された組み合わせ、すなわち、"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせが（０，１）または（１，０）の場合には、ｕ＜Ｒまたはｕ＞Ｎであることが示されず、前述の［演算式１］を適用した処理、すなわちキャリーが発生した場合にＮの減算処理を伴う演算を実行することになる。
【００８６】
（ｂ）"ｔ"と"ｍ"の上位２ビットの組み合わせに基づく処理
【００８７】
"ｔ"と"ｍ"の上位２ビットの組み合わせは、図３に示すように、ｔ＝００〜１１、ｍ＝００〜１１の４通り×４通りの組み合わせであり、全部で１６通りの組み合わせがある。図３に示すように、"ｔ"と"ｍ"の上位２ビットの組み合わせが（ｔ，ｍ）＝（００，００）、（００，０１）、（００，１０）、（０１，００）、（０１，０１）、（１０，００）であれば、ｕ＜Ｒが示され、（ｔ，ｍ）＝（０１，１１）、（１０，１０）、（１０，１１）、（１１，０１）、（１１，１０）、（１１，１１）、であれば、ｕ＞Ｎが示され、これらの組み合わせの場合には、前述の［演算式２］または［演算式３］の適用が可能となり、減算処理を省略することができる。図中［？］の示された組み合わせ、すなわち、（ｔ，ｍ）＝（００，１１）、（０１，１０）、（１０，０１）、（１１，００）の場合には、ｕ＜Ｒまたはｕ＞Ｎであることが示されず、前述の［演算式１］を適用した処理、すなわち必要に応じて減算処理を伴う演算を実行することになる。
【００８８】
以下、"ｔ"と"ｍ"の上位２ビットの各組み合わせにおいて、ｕ＜Ｒまたはｕ＞Ｎが成立することが示される組み合わせ、または成立することが示されない組み合わせについて説明する。
【００８９】
なお、前述の（ａ）"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）の組み合わせに基づく処理において、ｔ，ｍのＭＳＢが両者とも０の場合は、ｕ＜Ｒが成立し、両者とも１の場合は、ｕ＞Ｎが成立することが証明されているので、これらの場合以外の組み合わせについて説明する。図３における太線枠で示す８パターンについて説明する。
【００９０】
（ｂ−１）ｔの上位２ビット＝１１、ｍの上位２ビット＝０１
この場合は、２ω・DL ＞ｔH ＞３×２ω・DL−2，２ω・DL−2＜ｍ＜２ω・DL−１の場合に相当する。
この場合、
３×２ω・DL-2 ＞Ｒ−ｍ ＞２ω・DL-1
であり、
なおかつ、Ｎ／Ｒ＜１であるため、（Ｒ−ｍ）×Ｎ／Ｒは３×２ω・DL-2 以下である。一方、ｔH は３×２ω・DL-2 以上であるため、（数式８）より、
ｕ＞Ｎ
となる。
【００９１】
このように、ｔの上位２ビット＝１１、ｍの上位２ビット＝０１の場合、ｕ＞Ｎが成立し、前述の［演算式２］の演算を実行可能であり、減算処理の省略が可能となる。
【００９２】
（ｂ−２）ｔの上位２ビット＝１１、ｍの上位２ビット＝００
この場合は、２ω・DL ＞ｔH ＞３×２ω・DL−2，０＜ｍ＜２ω・DL−2  の場合に相当する。
この場合、
２ω・DL ＞Ｒ−ｍ ＞３×２ω・DL-2
である。
この場合、"ｕ"と"Ｎ"の大小関係の判定はできない。また、０ ＜Ｒ−ｔH ＜２ω・DL-2である。この場合、"ｕ"と"Ｒ"の大小関係の判定はできない。
【００９３】
この場合、前述した［演算式１］で演算を実行することが必要となり、（数式３）の演算結果でキャリー（Carry）が発生した場合のみＮの減算処理を行なう。
【００９４】
（ｂ−３）ｔの上位２ビット＝１０、ｍの上位２ビット＝０１
この場合は、３×２ω・DL−2＞ｔH ＞２ω・DL−1，２ω・DL−2＜ｍ＜２ω・DL−１  の場合に相当する。
この場合、
３×２ω・DL-2 ＞Ｒ−ｍ ＞２ω・DL-1
である。
この場合、"ｕ"と"Ｎ"の大小関係の判定はできない。また、
２ω・DL-2 ＜Ｒ−ｔH ＜２ω・DL-1
である。この場合、"ｕ"と"Ｒ"の大小関係の判定はできない。
【００９５】
この場合、前述した［演算式１］で演算を実行することが必要となり、（数式３）の演算結果でキャリー（Carry）が発生した場合のみＮの減算処理を行なう。
【００９６】
（ｂ−４）ｔの上位２ビット＝１０、ｍの上位２ビット＝００
この場合は、３×２ω・DL−2＞ｔH ＞２ω・DL−1，０＜ｍ＜２ω・DL−2  の場合に相当する。
Ｎ／Ｒ＜１であるため、ｍ×Ｎ／Ｒは２ω・DL-2 以下である。
一方、２ω・DL-2 ＜Ｒ−ｔH ＜２ω・DL-1であるため、Ｒ−ｔH は２ω・DL-2 以上である。このため、（数式９）より、
ｕ＜Ｒとなる。
【００９７】
この場合は、ｕ＜Ｒが成立し、前述の［演算式３］の演算を実行可能であり、減算処理の省略が可能となる。
【００９８】
（ｂ−５）ｔの上位２ビット＝０１、ｍの上位２ビット＝１１
この場合は、２ω・DL-2 ＜ｔH ＜２ω・DL−1，２ω・DL＞ｍ＞３×２ω・DL−2  の場合に相当する。
この場合、
０ ＜Ｒ−ｍ ＜２ω・DL-2
である。
Ｎ／Ｒ＜１であるため、（Ｒ−ｍ）×Ｎ／Ｒは２ω・DL-2 以下である。一方、ｔH は２ω・DL-2 以上であるため、（数式８）より、
ｕ＞Ｎとなる。
【００９９】
この場合、ｕ＞Ｎが成立し、前述の［演算式２］の演算を実行可能であり、減算処理の省略が可能となる。
【０１００】
（ｂ−６）ｔの上位２ビット＝０１、ｍの上位２ビット＝１０
この場合は、２ω・DL-2 ＜ｔH ＜２ω・DL−1，３×２ω・DL-2＞ｍ＞２ω・DL−1  の場合に相当する。
この場合、
２ω・DL-2 ＜Ｒ−ｍ ＜２ω・DL-1
である。
この場合、"ｕ"と"Ｎ"の大小関係の判定はできない。また、
３×２ω・DL-2＞Ｒ−ｔH ＞２ω・DL-1
である。この場合、"ｕ"と"Ｒ"の大小関係の判定はできない。
【０１０１】
この場合、前述した［演算式１］で演算を実行することが必要となり、（数式３）の演算結果でキャリー（Carry）が発生した場合のみＮの減算処理を行なう。
【０１０２】
（ｂ−７）ｔの上位２ビット＝００、ｍの上位２ビット＝１１
この場合は、０ ＜ｔH ＜２ω・DL−2，２ω・DL＞ｍ＞３×２ω・DL−2  の場合に相当する。
この場合、
０ ＜Ｒ−ｍ ＜２ω・DL-2
である。
この場合、"ｕ"と"Ｎ"の大小関係の判定はできない。また、
２ω・DL ＞Ｒ−ｔH ＞３×２ω・DL-2
である。この場合、"ｕ"と"Ｒ"の大小関係の判定はできない。
【０１０３】
この場合、前述した［演算式１］で演算を実行することが必要となり、（数式３）の演算結果でキャリー（Carry）が発生した場合のみＮの減算処理を行なう。
【０１０４】
（ｂ−８）ｔの上位２ビット＝００、ｍの上位２ビット＝１０
この場合は、０ ＜ｔH ＜２ω・DL−2，３×２ω・DL-2＞ｍ＞２ω・DL−1  の場合に相当する。
Ｎ／Ｒ＜１であるため、ｍ×Ｎ／Ｒは３×２ω・DL-2 以下である。一方、
２ω・DL ＞Ｒ−ｔH ＞３×２ω・DL-2
であるため、Ｒ−ｔH は３×２ω・DL-2 以上である。このため、（数式９）より
ｕ＜Ｒ
となる。
【０１０５】
この場合は、ｕ＜Ｒが成立し、前述の［演算式３］の演算を実行可能であり、減算処理の省略が可能となる。
【０１０６】
以上、説明した、"ｔH"と "ｍ"の上位２ビットに着目したときの、"ｕ"と "Ｎ" または"Ｒ"との大小関係を示したのが、図３である。
【０１０７】
図３に示すように、"ｔ"と"ｍ"の上位２ビットの組み合わせパターン１６通り中、６通りにおいてｕ＜Ｒが示され、他の６通りにおいてｕ＞Ｎが示され、これら１２通りの組み合わせの場合には、前述の［演算式２］または［演算式３］の適用が可能となり、減算処理を省略することができる。図中［？］の示された４通りの組み合わせのみが、ｕ＜Ｒまたはｕ＞Ｎであることが証明されず、前述の［演算式１］を適用した処理、すなわちキャリーが発生した場合にＮの減算処理を伴う演算を実行することになる。
【０１０８】
"ｔ"と"ｍ"の最上位ビット（ＭＳＢ）のみを検討した場合は、４通り中、２通り、すなわち、５０％の組み合わせにおいて、［演算式２］または［演算式３］の適用が可能となり、減算処理を省略することができるという結果であったが、"ｔ"と"ｍ"の上位２ビットを検討した場合は、１６通り中、１２通り、すなわち、７５％の組み合わせにおいて、［演算式２］または［演算式３］の適用が可能となり、減算処理を省略することができるという結果を得ることができる。
【０１０９】
"ｔ"と"ｍ"の上位３ビットに着目し、組み合わせデータ毎に、ｕ＜Ｒまたはｕ＞Ｎが成立するか否かを示した図が図４である。図４に示すように、ｔ＝０００〜１１１、ｍ＝０００〜１１１の８通り×８通りの組み合わせであり、全部で６４通りの組み合わせがある。図４に示すように、"ｔ"と"ｍ"の上位３ビットに着目した場合は、６４通り中、５６通り、すなわち、８７．５％の組み合わせにおいて、［演算式２］または［演算式３］の適用が可能となり、減算処理を省略することができるという結果を得ることができる。
【０１１０】
このように、本発明においては、モンプロ（MonPro）演算における中間値として算出される"ｔ"と"ｍ"の上位ビットの組み合わせに基づいてｕ＞Ｎであるか、または、ｕ＜Ｒであることが示される場合に、減算処理を伴う［演算式１］を実行することなく、［演算式２］または［演算式３］を適用した演算を実行する構成としたので、演算サイクルが削減され、処理の高速化が実現される。
【０１１１】
なお、上述した例では、モンプロ（MonPro）演算における中間値として算出される"ｔ"と"ｍ"の最上位〜３ビットの組み合わせについて説明したが、さらに、上位４ビット以上の多ビット情報を検出し、それらの検出ビットに基づいて、実行演算式を決定する構成としてもよい。着目する最上位ビット数を増やすほど、"ｕ"と "Ｎ" または"Ｒ"との大小関係が特定できない組合せの比率が減少し、積和演算後の Carry 発生時に、多倍長減算を実行する回数が減少する。
【０１１２】
［３．本発明の演算処理および装置と従来構成との比較］
次に、本発明の演算処理および装置について、従来構成との比較に基づいて、説明する。いわゆる、従来からの改良モンゴメリ（Montgomery）法は、通常のモンゴメリ（Montgomery）法が、剰余及び除算を２DL・ωで実行するのに対し、演算器のビット幅である２ωで行なうことで、演算サイクル数を削減した演算手法である。従来の改良モンゴメリ（Montgomery）法に基づく演算フローを以下に示す。
【０１１３】
MonPro（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*  ・・・・・・・・・・・・（数式１６）
for i ＝ 0 to DL−１
m＝ｔ0×Ｎ0' mod ｒ  ・・・・・・（数式１７）
ｔ:＝（ｔ＋ｍ×Ｎ）／ｒ  ・・・・（数式１８）
next i
if  Carry＝１  then  return  ｔ−Ｎ
else  return  ｔ  ・・（数式１９）
【０１１４】
このフローで、
DL ：剰余数"Ｎ"のワード数
ｒ ：演算器の幅をω[bit]とした時、ｒ＝２ω
t0：演算の中間値"ｔ"をｔ＝Σi=0DL-1ｔi・２ω・i とした時の、０ワード目の値
Ｎ0'：パラメータ"Ｎ'"をＮ'＝Σi=0DL-1Ｎ'i・２ω・i とした時の、０ワード目の値を表わす。このフローでは、ループの最後の演算でキャリー（Carry）が発生した場合、ループの演算結果"ｔ"から剰余数"Ｎ"を引いたものを演算結果としている。
【０１１５】
これに対して本発明に係る改良モンゴメリ（Montgomery）法において、演算フローは以下のようになる。
MonPro（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*  ・・・・・・・・・・・・（数式２０）
for i ＝ 0 to DL−２
m＝ｔ0×Ｎ0' mod ｒ  ・・・・・・（数式２１）
ｔ:＝（ｔ＋ｍ×Ｎ）／ｒ  ・・・・（数式２２）
next i
ｍ＝ｔ0×Ｎ0' mod ｒ  ・・・・・・・・（数式２３）
（ｍとｔの上位ビットから、（ｔ＋ｍ×Ｎ）／ｒ＞Ｎと判断できる場合）
ｕ＝（ｔ−（ｒ−ｍ）×Ｎ）／ｒ  ・・・（数式２４）
（ｍとｔの上位ビットから、（ｔ＋ｍ×Ｎ）／ｒ＜Ｒと判断できる場合）
ｕ＝（ｔ＋ｍ×Ｎ）／ｒ  ・・・・・・・（数式２５）
（ｍとｔの上位ビットから、上記どちらの判断もできない場合）
ｕ＝（ｔ＋ｍ×Ｎ）／ｒ  ・・・・・・・（数式２６）
if Carry＝１  then  return  ｕ−Ｎ
else  return  ｕ  ・・・（数式２７）
【０１１６】
上述の演算フローにおいて、(数式２４)の演算は、"ｍ"の２の補数と"Ｎ"の乗算値を"ｔ"から引き、その結果を１ワードずらす処理により行なう。実際の演算方法は後述する。
【０１１７】
上述した本発明の改良モンゴメリ（Montgomery）法を実行する演算処理装置の構成例を図５に示す。
【０１１８】
図５に示すように、演算処理装置は、制御部１０１、演算部１０２、メモリ入出力制御部１０３、および第１〜第４メモリ１１１〜１１４を有する。制御部１０１は演算部１０２に対して様々な制御信号、例えば桁上げに伴う処理を実行させるための制御信号、前述の［演算式１］〜［演算式３］を選択的に実行させるための制御信号などを出力する。
【０１１９】
演算部１０２には、メモリ入出力制御部１０３を介して第１〜第４メモリ１１１〜１１４から演算処理対象データが入力される。第１〜第４メモリ１１１〜１１４には、乗数・被乗数・被加算値、演算結果等がそれぞれ格納される。この例では、各メモリからの入力データは３２ビット構成であり、各メモリに対するデータ指定用アドレスは１０ビットデータとした例を示している。
【０１２０】
この構成で、多倍長の積和演算を行なう演算フローとしては、下記の（１）、（２）の２種類ある。
【０１２１】
（１）例えば乗数の１ワードに着目し、被乗数との多倍長乗算を行ない、それと平行して被加算値をメモリから読出して乗算結果と加算を行ない、結果をメモリに格納する。次に、乗数のワードを１ワード上位の値として被乗数との多倍長乗算を行ない、それと平行して被加算値をメモリから読出して乗算結果と加算を行ない、結果をメモリに格納する。これを、乗数のワードが最上位ワードになるまで繰り返す。
【０１２２】
（２）乗算結果の桁数が同じになる乗数、被乗数の組合せでの乗算を行なう。この乗算の前に、乗算結果と同じ桁となる被加算値をメモリから読出して、加算器にセットして、乗算結果と加算をしていく。それと平行して乗算結果と同じ桁となる被加算値をメモリから読出して加算し、その後下位ワードをメモリに格納し、上位ワードを加算器の下位ワードに移し、乗算結果の桁数が1ワード上となる乗算を行なう。これを、乗数、被乗数が共に最上位になるまで繰り返す。
【０１２３】
上記（１）の演算方法では、同じサイクルで同一メモリから演算の途中結果を読出して乗算結果と加算してその結果をメモリに書込む必要があり、高速なメモリが必要となる。一方、（２）の多倍長乗算手法は、このような高速メモリは必ずしも必要とはならない。
【０１２４】
（２）の多倍長乗算手法を実現する多倍長積和演算の演算部の構成および演算処理について、図６〜図９を参照して説明する。
【０１２５】
上述した本発明の演算、すなわち、モンプロ（MonPro）演算における中間値として算出される"ｔ"と"ｍ"の上位ビットの組み合わせに基づいてｕ＞Ｎであるか、または、ｕ＜Ｒであることが示される場合に、減算処理を伴う［演算式１］を実行することなく、［演算式２］または［演算式３］を適用した演算を実行する演算処理装置構成、および処理について、従来型の演算処理装置構成と処理と対比しながら説明する。
【０１２６】
まず、図６および図７を参照して多倍長の積和演算、
ｕ＝ｔ＋ｍ×Ｎ
の演算処理について説明する。
【０１２７】
演算処理装置の外部から演算命令が発行され、演算処理装置に入力されると、制御部からの制御により、乗数・被乗数・被加算値の格納されているメモリをアクセスし、必要なデータを演算部にセットすると共に、演算結果をメモリに格納する。
【０１２８】
この例では、乗数及び被乗数（ｍ，Ｎ）は４ワード構成であり、図６に示す［データ１］、［データ２］として設定され、被加算値（ｔ）は８ワードであり、図６に示す［データ３］として設定される。演算結果が［データ４］となる。
【０１２９】
まず、被加算値（ｔ）の構成ワードｔ0，ｔ1，ｔ2 が［データ３］としてセレクタ２１４を介して加算器２１５にセットされ、乗数及び被乗数（ｍ，Ｎ）の構成ワードｍ0とＮ0が［データ１］、［データ２］として、ラッチ２１１を介して乗算器２１２にセットされ、乗算が開始される。
【０１３０】
乗算器２１２における乗算結果"ｍＮ00L"，"ｍＮ00H"は、ラッチ２１３を介して加算器２１５に入力されて、ｔ0，ｔ1と加算され、キャリーが発生した場合は、ｔ2が＋１される。この演算結果の各ワードをｕ0，ｕ1，ｕ2 とすると、各ワードｕ0，ｕ1，ｕ2 は、ラッチ２１６を介して加算器２１５から出力され、ワードｕ0は、演算結果としてメモリに出力される。また、ワードｕ1とｕ2 は１ワードずつ下位側にシフトしてセレクタ２１４を介して加算器２１５の下位２ワードにセットされると共に、加算器２１５の最上位にｔ3がセットされる。
【０１３１】
一方、乗算器２１２には、ラッチ２１１を介してｍ1とＮ0がセットされて乗算が実行され、乗算結果"ｍＮ10L"，"ｍＮ10H"はｕ1，ｕ2 と加算される。この加算でキャリーが発生した場合、ｔ3が＋１される。この演算結果をｕ1'，ｕ2'，ｕ3'とした場合、これらは加算器２１５の一方にセットされ、乗算器２１２には ｍ0 と Ｎ1 がセットされて乗算が実行され、乗算結果"ｍＮ01L"，"ｍＮ01H"はｕ1'，ｕ2'と加算される。この加算でキャリーが発生した場合、ｕ3'が＋１される。
【０１３２】
この演算結果をｕ1''，ｕ2''，ｕ3''とした場合、u1''はメモリに出力され、ｕ2''とｕ3 ''は１ワードずつ下位側にシフトして加算器２１５の下位２ワードにセットされると共に、加算器２１５の最上位にｔ4 がセットされる。そして、乗算器２１２にはｍ2 と Ｎ0 がセットされて次の桁の積和演算が実行される。
【０１３３】
以下、同様に図７に示す演算フローに従って多倍長の積和演算が実行され、最終的にキャリーを含めて９ワードの演算結果［Carry〜ｕ０］が得られるが、モンゴメリ（Montgomery）演算では下位４ワードは"０"となるため、有効な値は下位５ワード目より上位の値である。そして、この演算結果が剰余数"Ｎ"より大きければ、"Ｎ"を引いた値を演算結果とする。また、このモンゴメリ（Montgomery）演算がルーブ（Loop）の途中であれば、キャリー（Carry）が発生した場合のみ"Ｎ"を引いて演算結果とし、これを次のモンゴメリ（Montgomery）演算に用いる。
【０１３４】
一方、本発明の演算処理、すなわち、モンプロ（MonPro）演算における中間値として算出される"ｔ"と"ｍ"の上位ビットの組み合わせに基づいてｕ＞Ｎであるか、または、ｕ＜Ｒであることが示される場合に、減算処理を伴う［演算式１］を実行することなく、［演算式２］または［演算式３］を適用した演算を実行する演算処理装置構成、および処理について、図８、図９を参照して説明する。
【０１３５】
本発明の演算処理を実現するための演算部（図８）には、図６に示す従来の積和演算器にない追加構成として、反転器３１１、加算器３１２、セレクタ３１３、反転・非反転回路３１４を持つ。このうち、３１１〜３１３の回路は、乗算器２１２の一方の入力、すなわち入力信号［データ１］の入力部に設けられている。
【０１３６】
すなわち、本発明の演算処理装置は、乗算器２１２の一方の入力が、入力信号［データ１］と、その値の反転信号とを選択して入力する構成を採り、［データ１］に入力される多倍長データで最下位のワードが［データ１］にセットされた時のみ、加算器２１４のキャリー（Carry）入力［"Cry1"］が"１"に制御される。
【０１３７】
乗算器２１２における乗算結果を加算器２１５に入力するとき、乗算結果とその反転信号を選択して入力する構成を採り、反転信号を選択した場合、多倍長演算の最初の時のみ、加算器２１５のキャリー（Carry）入力［"Cry2"］が"１"に制御される。これらの構成が付加されている点が図６に示す従来の積和演算器と異なる点である。
【０１３８】
この図８に示す演算器でモンゴメリ（Montgomery）演算を行なう場合、乗数及び被乗数、すなわち、［データ１］、［データ２］に対応する"ｍ"と"ｔ"の上位ビットの組合せで積和演算結果"ｕ"が"ｕ＞Ｎ"と判定されない場合、［データ１］はそのまま乗算器に入力され、乗算結果は反転する事無くそのまま加算器に入力され、通常の積和演算と同じように演算される。
【０１３９】
一方、"ｍ"と"ｔ"の上位ビットの組合せで積和演算結果"ｕ"が"ｕ＞Ｎ"と判定される場合、［データ１］は反転され、［データ１］が最下位ワードの場合は反転データに＋１した値が、それ以外の場合は反転データが乗算器に入力される。乗算結果は反転して加算器に入力され、乗算器入力が共に最下位ワードの場合のみ加算器のキャリー（Carry）入力［"Cry2"］が"１"に固定され、それ以外の場合には"０"に固定され、
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
が実行される。
【０１４０】
演算結果"ｕ"は"Ｎ"以下となっているため、その後の多倍長の減算は不要となる。この時の演算フローを図９に示す。この演算フローにおいて、ｍ'は以下の式で表される
ｍ'＝Σi=03 ｍi'・２ω・ｉ ＝Ｒ−Σi=03 ｍi・２ω・ｉ
【０１４１】
改良 Montgomery 演算を用いる場合、"ｍ"と"ｔ"の上位ビットの組合せで積和演算結果"ｕ"が"ｕ＞Ｎ"と判定されない場合、［データ１］はそのまま乗算器に入力され、乗算結果は反転すること無くそのまま加算器に入力され、通常の積和演算と同じように演算される。
【０１４２】
一方、"ｍ"と"ｔ"の上位ビットの組合せで積和演算結果"ｕ"が"ｕ＞Ｎ"と判定される場合、［データ１］は反転され、"ｍ"は１ワードであるため反転データに＋１した値が乗算器の一方に入力される。乗算結果は反転して加算器に入力され、乗算器入力が共に最下位ワードの場合のみ加算器のキャリー（Carry）入力［"Cry2"］が"１"に固定され、それ以外の場合には"０"に固定され、
ｕ＝（ｔ−（ｒ−ｍ）×Ｎ）／ｒ
が実行される。
【０１４３】
演算結果"ｕ"は"Ｎ"以下であるため、その後の多倍長の減算は不要となる。
【０１４４】
以上、説明したように、本発明の演算処理構成によれば、モンゴメリ（Montgomery）演算での積和演算で、その後の多倍長の減算を実行する回数を削減し、暗号演算のトータルの演算サイクル数を削減することができる。
【０１４５】
なお、図８に示す演算部に対して、データ１の反転データを入力するか、非反転データを入力するか、さらに桁上げを実行するか否かの制御信号は、図５に示す制御部１０１から演算部１０２に対して出力される。
【０１４６】
すなわち、本発明の演算処理装置は、メッセージ文をＭ，暗号文をＣ、公開鍵をｅ、秘密鍵をｄ、剰余数をＮとし、暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ、復号化：Ｍ＝Ｃｄ ｍｏｄ Ｎにより暗号化・復号化を行うＲＳＡ暗号において、モンゴメリ法を適用し、ＲをＮより大きい２のべき乗値、Ｎ'＝−Ｎ−１ｍｏｄＲとして、下記演算式［演算式１］
ＭｏｎＰｒｏ（ａ*，ｂ*）：
ｔ＝ａ*×ｂ*
ｍ＝ｔ×Ｎ' mod Ｒ
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
if  Carry＝１ then return ｕ−Ｎ
else  return  ｕ
に従ったモンプロ演算を実行する演算処理装置であり、モンプロ演算プロセスにおける中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせに基づいて、制御部１０１から制御信号を演算部１０２に出力し、演算部１０２は、制御信号に従って、前述の［演算式１］〜［演算式３］のいずれかの演算処理を選択的に実行する構成である。
【０１４７】
演算部１０２は、図８に示すように、上記［演算式１］における値ｕの算出処理を実行する乗算器２１２および加算器２１５を有するとともに、乗算器２１２の一方のデータ入力段に反転器３１１および、加算器３１２、セレクタ３１３及び反転・非反転回路３１４を設けた構成である。制御部１０１は、モンプロ演算プロセスにおける中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせに基づいて、乗算器２１２の一方の入力データを反転データまたは非反転データとして選択入力するように演算部１０２に制御信号を出力する。
【０１４８】
さらに、制御部１０１は、データ１の入力が最下位ワードである場合に、加算器３１２による桁上げ（Ｃａｒｒｙ）を実行し、該桁上げ処理後のデータを乗算器２１２に入力するように演算部１０２の制御を実行する。
【０１４９】
また、制御部１０１は、前記［演算式１］中のｔ，ｍの上位ビットの組み合わせを判別し、判別データに基づいてＴｅｍｐ１＝ｕ−Ｎ＞０であると判定される場合に、下記［演算式２］
ｕ＝（ｔ−（Ｒ−ｍ）×Ｎ）／Ｒ
に従って実行するように演算部１０２を制御し、
Ｔｅｍｐ２＝ｕ−Ｒ＜０であると判定される場合に、
下記［演算式３］
ｕ＝（ｔ＋ｍ×Ｎ）／Ｒ
に従って実行するように、演算部１０２の制御を実行する。
【０１５０】
例えば、制御部１０１は、ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（１，１）であるとき、Ｔｅｍｐ２＝ｕ−Ｒ＜０であると判定し、前記［演算式３］に従って実行するように演算部１０２を制御し、ｔ，ｍの最上位ビットの組み合わせが、（ｔ，ｍ）＝（０，０）であるとき、Ｔｅｍｐ１＝ｕ−Ｎ＞０であると判定し、前記［演算式２］に従って実行するように演算部１０２の制御を実行する。
【０１５１】
また、制御部１０１は、ｔ，ｍの最上位ビットまたは上位複数ビットの組み合わせに基づいて、Ｔｅｍｐ１＝ｕ−Ｎ＞０であるか、Ｔｅｍｐ２＝ｕ−Ｒ＜０であるか、いずれでもないかを判定し、Ｔｅｍｐ１＝ｕ−Ｎ＞０である場合には、モンプロ演算を、前記［演算式２］に従って実行するように演算部１０２を制御し、Ｔｅｍｐ２＝ｕ−Ｒ＜０である場合には、モンプロ演算を、前記［演算式３］に従って実行するように演算部１０２を制御し、いずれでもない場合には、モンプロ演算を、前記［演算式１］に従って実行するように演算部１０２を制御する。
【０１５２】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【産業上の利用可能性】
【０１５３】
以上、説明したように、本発明の構成によれば、モンプロ演算プロセスにおける中間値として取得されるｔ，ｍの値を構成する上位ビットの組み合わせを判別し、該判別データに基づいて、モンプロ演算式における値ｕの算出式を変更して実行する構成とするとともに、ｕの算出において多倍長の減算処理を不要とした式に基づく処理の実行確率を高めたので、モンゴメリ（Montgomery）演算での積和演算での多倍長の減算処理の実行回数が削減され、トータルの演算サイクル数の削減が実現され、高速処理の要請される暗号処理デバイスにおいて適用可能である。
【０１５４】
本発明の構成によれば、Ｔｅｍｐ２＝ｕ−Ｒ＜０の場合のみならず、Ｔｅｍｐ１＝ｕ−Ｎ＞０、すなわち、ｕ＞Ｎであることが示される場合においても、モンプロ（MonPro）演算における減算処理を省略することが可能となり、演算の高速化が実現され高速処理の要請される暗号処理デバイスにおいて適用可能である。
【図面の簡単な説明】
【０１５５】
【図１】本発明の演算処理装置において実行するモンプロ演算処理シーケンスを説明するフロー図である。
【図２】モンプロ演算における中間値ｔ，ｍの最上位ビットの各組み合わせにおいてｕ＜Ｒまたはｕ＞Ｎの得られる組み合わせを示す図である。
【図３】モンプロ演算における中間値ｔ，ｍの上位２ビットの各組み合わせにおいてｕ＜Ｒまたはｕ＞Ｎの得られる組み合わせを示す図である。
【図４】モンプロ演算における中間値ｔ，ｍの上位３ビットの各組み合わせにおいてｕ＜Ｒまたはｕ＞Ｎの得られる組み合わせを示す図である。
【図５】モンゴメリ法を実行可能な積和演算処理を実行する演算処理装置構成を示す図である。
【図６】モンゴメリ法を実行可能な積和演算処理を実行する演算処理装置における演算部構成を示す図である。
【図７】図６に示す演算部を用いて実行する積和演算処理シーケンスについて説明する図である。
【図８】モンゴメリ法を実行可能な積和演算処理を実行し、中間値ｔ，ｍの上位ビットの各組み合わせに基づく効率的な演算を実行可能とした演算処理装置における演算部構成を示す図である。
【図９】図８に示す演算部を用いて実行する積和演算処理シーケンスについて説明する図である。
【符号の説明】
【０１５６】
１０１  制御部
１０２  演算部
１０３  メモリ入出力制御部
１１１〜１１４  メモリ
２１１  ラッチ
２１２  乗算器
２１３  ラッチ
２１４  セレクタ
２１５  加算器
２１６  ラッチ
３１１  反転器
３１２  加算器
３１３  セレクタ
３１４  反転・非反転回路
【図１】
2005031472.tif 000003
【図２】
2005031472.tif 000004
【図３】
2005031472.tif 000005
【図４】
2005031472.tif 000006
【図５】
2005031472.tif 000007
【図６】
2005031472.tif 000008
【図７】
2005031472.tif 000009
【図８】
2005031472.tif 000010
【図９】
2005031472.tif 000011