演算プログラム、演算方法、および演算装置
【課題】ＲＳＡ暗号処理を、ＣＰＵの空き時間を可能な限り少なくなるよう非均等に分割し、短時間で完了させること。
【解決手段】演算装置１００は、検出部２０９にてＣＰＵの空き時間を検出する。そして算出部２１０にて、空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における乗算剰余演算処理の利用回数とに基づいて、空き時間内に処理可能なビット数を算出する。抽出部２１１にて、算出された処理可能なビット数に基づいて、対象データからビット列を抽出し、実行部２１２にて、抽出されたビット列を与えて、所定の部分演算処理を実行する。
【解決手段】演算装置１００は、検出部２０９にてＣＰＵの空き時間を検出する。そして算出部２１０にて、空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における乗算剰余演算処理の利用回数とに基づいて、空き時間内に処理可能なビット数を算出する。抽出部２１１にて、算出された処理可能なビット数に基づいて、対象データからビット列を抽出し、実行部２１２にて、抽出されたビット列を与えて、所定の部分演算処理を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理を実行する演算プログラム、演算方法、および演算装置に関する。
【背景技術】
【０００２】
携帯電話、車載器、ハードディスク装置などの組み込み機器が、搭載しているＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）は、ＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）に搭載しているＣＰＵに比べて、処理能力が低い。また、メモリ搭載量も低いのが一般的である。さらに、組み込み機器では、タスクが異常停止していないかを確認するために、一定時間ごとにＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）等の制御部に応答することでタスクの生存確認を行うことがある。応答先としては、装置内の制御部の他、ネットワーク経由による他の装置へ応答することもある。
【０００３】
一方、情報セキュリティ分野で使用されるＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）暗号処理は、演算負荷が大きく、処理能力の低い組み込み機器のＣＰＵでは、ＣＰＵを占有する時間が長くなり、ＣＰＵは、一定時間以内にＲＳＡ暗号処理を終了することができない可能性がある。一定時間以内に処理を終了できない場合、ＲＳＡ暗号処理を実行しているタスクは制御部に応答をすることができずに、制御部はタスクが異常停止していると誤認識をする結果となる。御認識を防ぐためには、ＲＳＡ暗号処理を途中で中断し、制御部に応答を行った後、ＲＳＡ暗号処理を再開することが必要となる。
【０００４】
前述した、ＲＳＡ暗号処理を分割する課題に関しては、ＲＳＡ暗号処理のほとんどを構成しているべき乗剰余演算処理を所定の部分乗算に分割して実行する技術が開示されている（たとえば、下記特許文献１を参照。）。また、べき乗剰余演算の高速化方法であるモンゴメリ乗算剰余演算処理において、複数回に分割して実行する技術が開示されている（たとえば、下記特許文献２を参照。）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００３−２９６２７号公報
【特許文献２】特開平８−１６９３２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来技術において、ＲＳＡ暗号処理を分割する際に、分割した各ＲＳＡ暗号分割処理が同一の長さになるような均等分割を行っていた。このため、ＣＰＵに空き時間が生じ、無駄な時間が存在しているという問題があった。
【０００７】
また、部分乗算を行う際に、事前の前処理として、ある一定範囲のべきに対し、べき乗剰余演算結果を格納する事前計算テーブルの生成処理を行い、事前計算テーブルを参照する場合がある。しかしながら、事前計算テーブルの大きさは常に固定サイズであり、固定の事前計算テーブルを参照したべき乗剰余演算処理を、ＣＰＵの空き時間内に行った場合、空き時間をすべて使いきれるとは限らず、空き時間が残る場合があるという問題があった。
【０００８】
本発明は、上述した従来技術による問題点を解消するため、ＣＰＵの空き時間にあわせてＲＳＡ暗号処理を非均等に分割し、処理効率の向上を図ることができる演算プログラム、演算方法、および演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、本演算プログラム、演算方法、および演算装置は、ＣＰＵの空き時間を検出し、空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における乗算剰余演算処理の利用回数とに基づいて、空き時間内に処理可能なビット数を算出し、算出された処理可能なビット数に基づいて、対象データからビット列を抽出し、抽出されたビット列を与えて、所定の部分演算処理を実行することを要件とする。
【発明の効果】
【００１０】
本演算プログラム、演算方法、および演算装置によれば、ＣＰＵの空き時間にあわせてＲＳＡ暗号処理を非均等に分割し、処理効率の向上を図ることができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１にかかる演算装置のハードウェア構成を示すブロック図である。
【図２】演算装置１００の機能的構成を示すブロック図である。
【図３】従来例と実施の形態１による実行状態を示す図である。
【図４】バイナリ法の概要説明を示す図である。
【図５】バイナリ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。
【図６】ウィンドウ法の概要説明を示す図である。
【図７】ウィンドウ法の処理時間を示す図である。
【図８】ウィンドウ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。
【図９】ウィンドウ法によるＲＳＡ暗号非均等分割処理を行った処理時間例を示す図である。
【図１０】ＲＳＡ暗号非均等分割処理を示すフローチャートである。
【図１１】実施の形態１にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【図１２】実施の形態２にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【図１３】実施の形態３にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【図１４】実施の形態４にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、本発明にかかる演算プログラム、演算方法、および演算装置の好適な実施の形態を詳細に説明する。
【００１３】
（実施の形態１）
（演算装置１００のハードウェア構成）
図１は、実施の形態１にかかる演算装置のハードウェア構成を示すブロック図である。図１において、演算装置１００は、ＣＰＵ１０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ Ｍｅｍｏｒｙ）１０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１０３と、磁気ディスクドライブ１０４と、磁気ディスク１０５と、光ディスクドライブ１０６と、光ディスク１０７と、ディスプレイ１０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）１０９と、キーボード１１０と、マウス１１１と、スキャナ１１２と、プリンタ１１３と、を備えている。また、各構成部はバス１１４によってそれぞれ接続されている。
【００１４】
ここで、ＣＰＵ１０１は、演算装置１００の全体の制御を司る。ＣＰＵ以外にも、リアルタイム処理を求められる組み込み機器で使用されるＤＳＰ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）であってもよい。
【００１５】
ＲＯＭ１０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１０３は、ＣＰＵ１０１のワークエリアとして使用される。磁気ディスクドライブ１０４は、ＣＰＵ１０１の制御にしたがって磁気ディスク１０５に対するデータのリード／ライトを制御する。磁気ディスク１０５は、磁気ディスクドライブ１０４の制御で書き込まれたデータを記憶する。また、演算装置１００の小型化を目的として、磁気ディスク１０５の代わりにＦｌａｓｈ ＲＯＭを使用してもよい。
【００１６】
光ディスクドライブ１０６は、ＣＰＵ１０１の制御にしたがって光ディスク１０７に対するデータのリード／ライトを制御する。光ディスク１０７は、光ディスクドライブ１０６の制御で書き込まれたデータを記憶したり、光ディスク１０７に記憶されたデータをコンピュータに読み取らせたりする。
【００１７】
ディスプレイ１０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００１８】
Ｉ／Ｆ１０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク１１５に接続され、このネットワーク１１５を介して他の装置に接続される。そして、Ｉ／Ｆ１０９は、ネットワーク１１５と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００１９】
キーボード１１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００２０】
スキャナ１１２は、画像を光学的に読み取り、演算装置１００内に画像データを取り込む。なお、スキャナ１１２は、ＯＣＲ（Ｏｐｔｉｃａｌ Ｃｈａｒａｃｔｅｒ Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ１１３は、画像データや文書データを印刷する。プリンタ１１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。なお、組み込み機器環境においては、磁気ディスクドライブ１０４、磁気ディスク１０５、光ディスクドライブ１０６、光ディスク１０７、ディスプレイ１０８、Ｉ／Ｆ１０９、キーボード１１０、マウス１１１、スキャナ１１２、プリンタ１１３、ネットワーク１１５の一部、またはすべてが存在しない構成であってもよい。
【００２１】
（演算装置１００の機能的構成）
次に、演算装置１００の機能的構成について説明する。図２は、演算装置１００の機能的構成を示すブロック図である。演算装置１００は、制御部２０１と、処理コントロール部２０２と、受信部２０３と、演算部２０４と、タイマー２０５と、空き時間計算部２０６と、リファレンス所要時間格納テーブル２０７と、処理時間取得部２０８と、を含む構成である。この制御部となる機能（制御部２０１〜処理時間取得部２０８）は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶装置に記憶されたプログラムをＣＰＵ１０１が実行することにより、その機能を実現する。または、Ｉ／Ｆ１０９を経由して他のＣＰＵが実行することにより、その機能を実現してもよい。
【００２２】
制御部２０１は、演算装置の制御を行うＯＳであり、演算部２０４を含む、すべてのタスクを実行するために、処理コントロール部２０２に処理を命令する機能を有する。具体的には、たとえば、制御部２０１は、処理コントロール部２０２がタスクＡを実行終了後に、タスクＢを実行するように処理コントロール部２０２に命令する。
【００２３】
処理コントロール部２０２は、制御部２０１からの命令にしたがって、タスクを実行する機能を有する。また、演算部２０４以外のタスクを実行後、ＯＳに応答を返すまでの空き時間を空き時間計算部２０６より取得する。具体的には、たとえば、ＯＳに応答を返す周期が３０［ｍｓｅｃ］（ミリ秒）の場合に、ＣＰＵ１０１が他のタスクを１０［ｍｓｅｃ］実行した場合、処理コントロール部２０２は空き時間として２０［ｍｓｅｃ］を取得する。なお、取得結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２４】
受信部２０３は、べき乗剰余演算処理が行われる被対象データを受信する機能を有する。具体的には、たとえば、暗号化を行う場合には、被対象データは平文であり、また、べき乗剰余演算処理の指数部分にあたる対象データとして、公開鍵の情報もあわせて受信する。なお、受信結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２５】
演算部２０４は、処理コントロール部２０２によって実行される機能の一つであり、ＲＳＡ暗号処理でのべき乗剰余演算処理を行う機能を有する。具体的には、たとえば、暗号文＝平文＾公開鍵（ｍｏｄＮ）というべき乗剰余演算処理を行うことで、平文から暗号文を生成する。また、平文＝暗号文＾暗号鍵（ｍｏｄＮ）というべき乗剰余演算処理を行うことで、暗号文から平文を生成する。演算部２０４の内部の詳細は後述する。なお、演算結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２６】
タイマー２０５は、ＣＰＵ１０１に対して一定間隔で割り込みを発生させる機能を有する。具体的には、たとえば、タイマー２０５により割り込みが発生した際に、制御部２０１で管理しているカウンタを増加することで、内部時刻を更新する。カウンタは、たとえば、ＣＰＵ１０１が保持しているレジスタに記憶される。
【００２７】
空き時間計算部２０６は、タイマー２０５の内部時刻から空き時間を計算する機能を有する。具体的には、たとえば、次にＯＳに応答を返す時刻から、現在時刻を引くことで、空き時間を求めることができる。なお、計算結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２８】
リファレンス所要時間格納テーブル２０７は、乗算剰余演算処理にかかる時間を事前に計算、もしくは計測し、格納しておく領域である。乗算剰余演算処理は、べき乗剰余演算処理の高速化方法であるモンゴメリ乗算剰余演算処理であってもよい。具体的には、たとえば、平文を暗号文にする場合、平文であるべき乗剰余演算処理の被対象データのビット長と、秘密鍵であるべき乗のビット長と、公開鍵であるモジュラスのビット長をインデックスとして、モンゴメリ乗算剰余演算処理にかかる時間を格納する。
【００２９】
また、処理方式がＣＲＴ（Ｃｈｉｎｅｓｅ Ｒｅｍａｉｎｄｅｒ Ｔｈｅｏｒｅｍ）もしくは非ＣＲＴかもインデックスに含めてもよい。リファレンス所要時間格納テーブル２０７は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。または、事前計測した結果をＲＯＭ１０２に保持しておいても良い。また、インデックスを持たず、１０２４ビットの乗算剰余演算処理の結果を保持しておき、利用時には暗黙的に１０２４ビットとして扱ってもよい。
【００３０】
処理時間取得部２０８は、べき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間を取得する機能を有する。具体的には、たとえば、演算装置１００は、リファレンス所要時間格納テーブル２０７から、べき乗剰余演算処理の被対象データのビット長と、べき乗のビット長と、モジュラスのビット長を指定することで、条件に当てはまる場合の処理時間を取得する。なお、取得結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００３１】
次に、実施の形態１にかかる演算部２０４の機能詳細について説明する。演算部２０４は、検出部２０９と、算出部２１０と、抽出部２１１と、実行部２１２と、設定部２１３と、テーブル生成部２１４と、テーブル取得部２１５で構成される。
【００３２】
検出部２０９は、べき乗剰余演算処理より優先度の高い処理を行うまでの空き時間を検出する機能を有する。具体的には、たとえば、他のタスクの処理が終わった時点で、次のＯＳに応答を返す時刻までの空き時間を、空き時間計算部２０６より検出する。なお、検出結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００３３】
算出部２１０は、乗算剰余演算処理に要する処理時間と、べき乗剰余演算処理の部分演算処理における乗算剰余演算処理の利用回数と、空き時間に基づいて、空き時間内で処理可能なビット数を算出する機能を有する。それぞれ、処理時間は処理時間取得部２０８から、空き時間は検出部２０９から検出する。部分演算処理とは、後述するバイナリ法、ウィンドウ法である。さらに、受信部２０３によって受信された対象データのビット列に基づいて、空き時間内で処理可能なビット数を算出してもよい。
【００３４】
部分演算処理でバイナリ法が実装されている場合、処理可能なビット数の算出式として、下記式（１）で算出してもよい。以下、この算出方式を「処理可能ビット数算出法１」と称する。実施の形態１では、処理可能ビット数算出法１を適用している。
【００３５】
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−１）／２）…（１）
【００３６】
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【００３７】
部分演算処理でウィンドウ法が実装されている場合、処理可能なビット数の算出式として、下記式（２）で算出してもよい。以下、この算出方式を「処理可能ビット数算出法２」と称する。後述する実施の形態２では、処理可能ビット数算出法２を適用している。
【００３８】
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−２＾ｎ）／（ｎ＋１））＊ｎ…（２）
【００３９】
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ法にて、１度に処理を行う対象のビット数を示す。以下、ウィンドウ幅とする。
【００４０】
部分演算処理でバイナリ法が実装されている場合、空き時間内に乗算剰余演算処理の利用可能な回数である演算利用可能回数を下記式（３）にて求める。そして、対象ビットの値に応じて演算を実行した回数を加算することにより、演算を実行した回数が演算利用可能回数になるまで対象ビットを順次読み出し、読み出した対象ビットの数を処理可能なビット数として、算出してもよい。具体的には、対象ビットが０ならば回数を１加算し、対象ビットが１ならば回数を２加算する。以下、この算出方式を「処理可能ビット数算出法３」と称する。後述する実施の形態３では、処理可能ビット数算出法３を適用している。
【００４１】
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−１）…（３）
【００４２】
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【００４３】
バイナリ法では、対象ビットが０である場合は乗算剰余演算処理を１回行い、１である場合は乗算剰余演算処理を２回行う。したがって、対象ビットの値に沿って乗算剰余演算処理を行う回数を計算することで、処理可能なビット数を算出できる。
【００４４】
部分演算処理でウィンドウ法が実装されている場合、空き時間内に乗算剰余演算処理の利用可能な回数である演算利用可能回数を下記式（４）にて求める。そして、ウィンドウ幅分のビット列が取り得るビットパターンに応じて演算を実行した回数を加算する。演算を実行した回数が演算利用可能回数になるまでビット列を順次読み出し、読み出したビット列を構成するビットの数を処理可能なビット数として、算出してもよい。具体的には、ビット列がすべて０ならば回数をウィンドウ幅分加算し、ビット列に１が含まれるならば回数をウィンドウ幅＋１分加算する。以下、この算出方式を「処理可能ビット数算出法４」と称する。後述する実施の形態４では、処理可能ビット数算出法４を適用している。
【００４５】
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−２＾ｎ）…（４）
【００４６】
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ幅を示す。
【００４７】
ウィンドウ法では、ｎビットのビット列がすべて０である場合は乗算剰余演算処理をｎ回行い、ビット列に１が含まれる場合は乗算剰余演算処理をｎ＋１回行う。したがって、ｎビットのビット列の値に沿って乗算剰余演算処理を行う回数を計算することで、処理可能なビット数を算出できる。
【００４８】
また、実施の形態２または４でのウィンドウ幅ｎについて、取り得るウィンドウ幅ごとに対して処理可能なビット数を算出し、後述する抽出部２１１にて、最長となるビット数を抽出し、後述する実行部２１２で実行してもよい。また、算出時に後述する設定部２１３にて設定されたテーブルの生成時間を含めて算出してもよい。
【００４９】
また、実施の形態１〜４を同時に複数持つ形態でもよい。具体的には、たとえば、実施の形態１であるバイナリ法と実施の形態２であるバイナリ法を同時に持ち、それぞれ処理可能なビット数を算出する。そして、処理可能なビット数が最大となる部分演算処理と処理可能なビット数を使用してもよい。
【００５０】
算出の具体例として、たとえば、実施の形態１にて、乗算剰余演算処理に要する処理時間が０．１［ｍｓｅｃ］、部分演算処理がバイナリ法、空き時間が２０［ｍｓｅｃ］の場合を考える。バイナリ法における乗算剰余演算処理の利用回数は１ビットに対して２回である。前述の条件では、後述する式１を使用することにより、Ｋｂ＝Ｆｌｏｏｒ（（２０／０．１−１）／２）により、空き時間内に９９ビット処理可能であることが算出できる。なお、算出結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５１】
抽出部２１１は、受信部２０３によって受信された対象データから算出部２１０によって算出されたビット数分のビット列を抽出する機能を有する。また、部分演算処理を開始する開始ビット位置を記憶装置から読み出し、対象データの開始ビット位置から、算出されたビット数分のビット列を抽出する。その後、次の算出時のために、開始ビット位置と算出されたビット数分に基づいて、新たな開始ビット位置を求め、開始ビット位置として記憶装置に格納してもよい。
【００５２】
具体的には、たとえば、算出部２１０によって９９ビット処理可能であるという算出結果を受けとったら、抽出部２１１は、対象データの先頭もしくは記憶装置に格納されている開始ビット位置から９９ビット分のビット列を抽出する。なお、算出結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５３】
実行部２１２は、抽出部２１１によって抽出されたビット列に対して、部分演算処理を実行する機能を有する。具体的には、たとえば、実施の形態１または３では、バイナリ法を実行する。また、実施の形態２または４では、ウィンドウ法を実行する。バイナリ法の概要説明は図４にて、ウィンドウ法の概要説明は図６にて後述する。
【００５４】
設定部２１３は、部分演算処理がウィンドウ法の場合に、ウィンドウ幅ごとに、後述するテーブル生成部２１４で生成するテーブルの作成時間を、処理時間取得部２０８を用いて設定する機能を有する。具体的には、たとえば、ウィンドウ幅が２ならば、テーブルの作成時間は、２＾２×（乗算剰余演算処理）と設定できる。なお、設定結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５５】
テーブル生成部２１４は、部分演算処理がウィンドウ法の場合に、事前に行う処理として、べき乗剰余演算処理が行われる被対象データをウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成する機能を有する。具体的には、たとえば、ウィンドウ幅が４ビットで、被対象データがＸ、モジュラスがＺの場合、Ｘ＾０（ｍｏｄＺ）、Ｘ＾１（ｍｏｄＺ）、・・・、Ｘ＾１５（ｍｏｄＺ）の値を求め、テーブルに格納する。なお、生成結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５６】
テーブル取得部２１５は、部分演算処理がウィンドウ法の場合に、テーブル生成部２１４によって生成されたテーブルから、ビットパターンに基づいて、被対象データをビットパターンにてべき乗剰余した値を取得する機能を有する。具体的には、たとえば、ウィンドウ幅が４ビットで、被対象データがＸ、モジュラスがＺの場合に、ウィンドウ内のビットパターンが９である場合は、テーブルに格納されているＸ＾９（ｍｏｄＺ）の値を取得する。なお、取得結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５７】
以上の機器、機能を使用して、演算装置１００はべき乗剰余演算処理を行う。次に、従来例と実施の形態１による実行状態を示す。
【００５８】
（実施の形態１の概要説明）
図３は、従来例と実施の形態１による実行状態を示す図である。前提条件として、１０［ｍｓｅｃ］ごとにＯＳに対して応答を返す。従来例での実行状態３０１では、別タスクを実行した後に、分割されたＲＳＡ暗号処理が行われている状態を示している。ＲＳＡ暗号処理を均等に分割する場合、一番空き時間が短い１０〜２０［ｍｓｅｃ］の区間にあわせるため、他の区間、たとえば、０〜１０［ｍｓｅｃ］の区間で空き時間３０３、２０〜３０［ｍｓｅｃ］の区間で空き時間３０４が発生してしまう。
【００５９】
実施の形態１では、ＲＳＡ暗号処理をそれぞれの空き時間を動的に計算して処理分割し、効率的にＣＰＵを利用する。実施の形態１での実行状態３０２では、ＲＳＡ暗号処理は、０〜１０［ｍｓｅｃ］の区間では部分演算処理３０５、１０〜２０［ｍｓｅｃ］の区間では部分演算処理３０６、２０〜３０［ｍｓｅｃ］の区間では部分演算処理３０７といった状態に非均等分割される。
【００６０】
図４は、バイナリ法の概要説明を示す図である。実施の形態１では、部分演算処理にバイナリ法が実装されている。バイナリ法はべき乗部分を２進数表現し、得られたビット列に対して１ビットごとにべき乗剰余演算処理を行う方法である。平文Ｘ、公開鍵ｄ、モジュラスＺ、があるときに、求める暗号文Ｙは、Ｙ＝Ｘ＾ｄ（ｍｏｄＺ）で表すことができる。
【００６１】
ここで、ｄ＝２１としてバイナリ法の具体例を示す。ｄ＝２１を２進数表記すると（１０１０１）となり、式４０１が得られる。式４０１において、符号４０２，４０３，４０５，４０６は２乗算をあらわし、符号４０４，４０７は乗算をあらわす。これら符号４０２〜４０７で示した乗算および２乗算は、ｄ＝２１の２進数表記（１０１０１）の各ビットに対応している。符号４０２の２乗算は２進数表記（１０１０１）の最上位から２番目のビットである０が対応している。以下、順に、符号４０３の２乗算と符号４０４の乗算は、最上位から３番目のビットである１が対応している。符号４０５の２乗算は、最上位から４番目のビットである０が対応している。符号４０６の２乗算と符号４０７の乗算は、最下位のビットである１が対応している。
【００６２】
したがって、ビット列先頭以外の対象ビットが０の場合には２乗算を行い、対象ビットが１の場合には２乗算を行った後に乗算を行うことにより、Ｘ＾２１を得ることができる。また、合同式の性質より、Ａ＊Ｂ（ｍｏｄＺ）＝（Ａ（ｍｏｄＺ））＊（Ｂ（ｍｏｄＺ））（ｍｏｄＺ）となるため、乗算剰余を行った結果同士をさらに乗算剰余することで、べき乗剰余と同じ結果を得ることができる。
【００６３】
図５は、バイナリ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。ＲＳＡ暗号非分割処理の実行状態５０１では１０［ｍｓｅｃ］の段階でＯＳに応答を返すことができない。従来例の実行状態５０２では、バイナリ法を、２乗算のところで分割した例である。タイマーを持たせることで、空き時間に応じてＲＳＡ暗号処理を割り当てている。
【００６４】
モンゴメリ乗算剰余を使用した従来例の実行状態５０３では、モンゴメリ乗算剰余を使用する際に必要な前処理が行われるため、０〜１０［ｍｓｅｃ］の区間では、ＲＳＡ暗号分割処理５０５が１０［ｍｓｅｃ］を超えてしまっている。同様に１０〜２０［ｍｓｅｃ］の区間では、ＲＳＡ暗号分割処理５０６が、２０〜３０［ｍｓｅｃ］の区間では、ＲＳＡ暗号分割処理５０７が、各区間を超過してしまっており、ＯＳに応答を返すことができない状態である。
【００６５】
実施の形態１での実行状態５０４では、モンゴメリ乗算剰余の前処理の時間を含んで処理可能なビット数を算出する。そのため、０〜１０［ｍｓｅｃ］、１０〜２０［ｍｓｅｃ］、２０〜３０［ｍｓｅｃ］、３０〜４０［ｍｓｅｃ］の各区間でＲＳＡ暗号分割処理が終了するように割り当てられている。空き時間内で処理可能なビットの算出式は式（１）となる。
【００６６】
（実施の形態２の概要説明）
図６は、ウィンドウ法の概要説明を示す図である。実施の形態２のハードウェアの構成は実施の形態１に示したものと等しく、機能的構成も同様であるが、部分演算処理はウィンドウ法が実装されている。また、算出部２１０も部分演算処理にあわせた機能となる。Ｙ＝Ｘ＾ｄ（ｍｏｄＺ）にて、ｄを２進数表記することで、ビット列６０１を得る。次に、所定のウィンドウ幅、図６ではｋビットごとにビット列を分割し、分割して得たｋビットのビット列に対してべき乗剰余演算処理を行う。ウィンドウｂm-1、ウィンドウｂm-2、・・・、ウィンドウｂ1、ウィンドウｂ0と分割し、分割して得た結果が式６０２である。
【００６７】
また、ｗ［０］＝Ｘ＾０（ｍｏｄＺ）、ｗ［１］＝Ｘ＾１（ｍｏｄＺ）、・・・、ｗ［２＾（ｋ−１）］＝Ｘ＾（２＾（ｋ−１））（ｍｏｄＺ）までを事前計算テーブルとして事前準備する。定義したｗ［］を使用すると、 ウィンドウｂm-1はｗ［１１１１］と置き換えられる。以下、同様に、ウィンドウｂm-2は、ｗ［０１１０］と置き換えられ、ｂ1は、ｗ［１００１］と置き換えられ、ｂ0は、ｗ［１１０１］と置き換えられる。置き換えた後、ウィンドウごとに２乗算をｋ回行い、さらにｗ［］との乗算を１回行うことを繰り返すことで、Ｙ＝Ｘ＾ｄ（ｍｏｄＺ）を求めることができる。
【００６８】
メモリが潤沢にある環境では、２３〜２５ビット程度のデータ量となる事前計算テーブルを事前計算にて準備しておき、べき乗剰余演算実行時にはこの事前計算テーブルを参照することで、高速な処理を実現できる。しかし、組み込み環境では、メモリ搭載量等の観点から事前計算テーブルを内部に保持し続けることができないため、実行の度にテーブル生成を行うことになり、オーバーヘッドがかかる。よって、一度に参照するビット幅が大きいテーブルを準備すれば、べき乗剰余演算の処理が高速に実行できる反面、事前計算テーブル生成の手間は大きくなる。
【００６９】
図７は、ウィンドウ法の処理時間を示す図である。ウィンドウ法は、処理の内容として、事前計算テーブルを生成する処理と、べき乗剰余演算処理を行う処理との２つに分かれる。図７は、それぞれのウィンドウ幅にあわせた、事前計算テーブルの生成にかかる処理時間と、べき乗剰余処理の処理時間とを表している。
【００７０】
たとえば、ウィンドウ幅が２ビットの場合は、テーブル生成には、２＾２×（乗算剰余演算処理）、べき乗剰余演算処理には、（ｂ＋ｂ／２）×（乗算剰余演算処理）の時間がかかることになる。ここで、ｂは対象データのビット長である。ウィンドウ幅がｎビットであれば、テーブル生成には、２＾ｎ×（乗算剰余演算処理）、べき乗剰余演算処理には、（ｂ＋ｂ／ｎ）×（乗算剰余演算処理）の時間がかかることになる。
【００７１】
図８は、ウィンドウ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。ウィンドウ幅を４ビット固定で行ったウィンドウ法の実行状態８０１では、１０〜２０［ｍｓｅｃ］の区間で空き時間８０３が、２０〜３０［ｍｓｅｃ］の区間で空き時間８０４が、それぞれ発生している。空き時間が発生する理由は、ウィンドウ法はバイナリ法よりも一度にまとめて処理を行うため、空きができることがあるためである。
【００７２】
次に、実施の形態２の実行状態８０２では、空き時間にあわせてウィンドウ幅を動的に変更させることで、空き時間を限りなく少なくなるように使用することができる。具体的には、０〜１０［ｍｓｅｃ］の区間では、ウィンドウ幅は４ビットである。同様に、１０〜２０［ｍｓｅｃ］の区間では、ウィンドウ幅は２ビット、２０〜３０［ｍｓｅｃ］の区間では、ウィンドウ幅は５ビット、３０〜４０［ｍｓｅｃ］の区間では、ウィンドウ幅は４ビットといったようにウィンドウ幅が可変となっている。空き時間内で処理可能なビットの算出式は式（２）となる。
【００７３】
図９は、ウィンドウ法によるＲＳＡ暗号非均等分割処理を行った処理時間例を示す図である。ＲＳＡ暗号処理の対象データのビット数を１０２４ビットとする。また、ＯＳに応答を返す間隔を３０［ｍｓｅｃ］とし、別タスク処理時間として、各最適実装法取得回数の各フィールドが対応する。たとえば、１度目は１２［ｍｓｅｃ］、２度目は１０［ｍｓｅｃ］となる。余り時間Ｔは、ＯＳに応答を返す間隔３０［ｍｓｅｃ］と別タスク処理時間の差となる。乗算剰余演算処理が行える回数ａは、余り時間Ｔと１回の乗算剰余演算処理に要する所要時間ｔの商である。
【００７４】
前述した前提条件にて、式（２）をウィンドウ幅１〜５ビットまで行い、最大のＫｂを最適実装法として取得する。たとえば、１度目の場合、Ｋｂ（１）としてウィンドウ幅１ビットの場合は８９ビット、同様に、Ｋｂ（２）は１１６ビット、Ｋｂ（３）は１２９ビット、Ｋｂ（４）は１２８ビット、Ｋｂ（５）は１２０ビットとなり、最大のＫｂはＫｂ（３）となる。したがって、未処理のビットは、１０２４ビットとＫｂ（３）で得た１２９の差となり、８９５ビットとなる。以下、２度目以降も同様の処理を行い、処理残りビットが７５１ビット、７２１ビット、・・・と繰り返す。９度目の時点で処理残りビットがなくなったため処理を終了する。
【００７５】
９度目の分割処理でＲＳＡ暗号処理が終わったため、ＲＳＡ処理に要した処理時間は別タスクの時間も含めると、２７０［ｍｓｅｃ］となる。もし、従来例で処理を行った場合、最も余り時間が短い、ＲＳＡ暗号分割処理の処理時間は５［ｍｓｅｃ］に設定することになる。ウィンドウ幅として４ビットを使用した場合、１度に２４ビット処理することができ、ＲＳＡ暗号処理ビットが１０２４ビットである場合、４３度目、１２９０［ｍｓｅｃ］で終了することになる。
【００７６】
（実施の形態１〜４の機能説明）
図１０は、ＲＳＡ暗号非均等分割処理を示すフローチャートである。図１０は実施の形態１〜４すべての形態で使用され、後述するステップＳ１００４と、ステップＳ１００８にてそれぞれの形態にて対応する処理が行われる。
【００７７】
演算装置１００は、別タスク実行後の空き時間を検出部２０９より検出し、Ｔに格納する（ステップＳ１００１）。続けて、乗算剰余演算処理の処理時間を処理時間取得部２０８により取得し、ｔに格納する（ステップＳ１００２）。演算装置１００は、Ｔとｔを用い、ａ＝Ｔ／ｔを計算し（ステップＳ１００３）、ａを引数として、最適実装法取得および処理可能ビット数算出処理を実行する（ステップＳ１００４）。具体的な処理内容は、それぞれの実施の形態、実施の形態１では図１１、実施の形態２では図１２、実施の形態３では図１３、実施の形態４では図１４にて後述する。
【００７８】
最適実装法と処理可能ビット数を取得できたら、演算装置１００は、今回が初回のＲＳＡ暗号処理であるのかを確認する（ステップＳ１００５）。初回である場合には（ステップＳ１００５：Ｙｅｓ）、受信部２０３によって受信された対象データを入力データとして取得する（ステップＳ１００６）。初回でなく、２回目以降の場合には（ステップＳ１００５：Ｎｏ）、記憶装置に格納してあったＲＳＡ暗号処理途中結果を取得する（ステップＳ１００７）。次に、取得した対象データに対して、算出した処理可能ビット数分、取得した最適実装法を実行する（ステップＳ１００８）。最適実装法は、実施の形態１または３ではバイナリ法を使用し、実施の形態２または４ではウィンドウ法を使用する。
【００７９】
処理可能ビット数分、最適実装法を行った後に、演算装置１００は、ＲＳＡ暗号処理が終了したかを確認する（ステップＳ１００９）。終了した場合には（ステップＳ１００９：Ｙｅｓ）、ＲＳＡ暗号処理結果を出力する（ステップＳ１０１０）。終了していなく、途中であった場合には（ステップＳ１００９：Ｎｏ）、ＲＳＡ暗号処理途中結果を記憶装置に格納する（ステップＳ１０１１）。
【００８０】
（実施の形態１の機能説明）
図１１は、実施の形態１にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法１のフローチャートが図１１となる。演算装置１００は、引数として渡されたａを用いて、Ｋｂ＝Ｆｌｏｏｒ（（ａ−１）／２）を算出する（ステップＳ１１０１）。ステップＳ１１０１で求めたＫｂが処理可能ビット数となり、最適実装法として、バイナリ法を出力し、処理可能ビット数として、Ｋｂを出力し（ステップＳ１１０２）、処理を終了する。
【００８１】
（実施の形態２の機能説明）
図１２は、実施の形態２にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法２のフローチャートが図１２となる。演算装置１００は、ｉを１に初期化する（ステップＳ１２０１）。後続するステップではｉをウィンドウ幅として使用する。
【００８２】
次に、演算装置１００は、引数として渡されたａを用いて、ａ−２＾ｉを算出し、０より大きいかを確認する（ステップＳ１２０２）。０より大きい場合には（ステップＳ１２０２：Ｙｅｓ）、Ｋｂ（ｉ）＝Ｆｌｏｏｒ（（ａ−２＾ｉ）／（ｉ＋１））＊ｉを算出する（ステップＳ１２０３）。算出されたＫｂ（ｉ）を保持し（ステップＳ１２０４）、次のウィンドウ幅で計算するために、ｉをインクリメントし（ステップＳ１２０５）、ステップＳ１２０２に移行する。
【００８３】
ａ−２＾ｉが０以下の場合は（ステップＳ１２０２：Ｎｏ）、演算装置１００は、保持したＫｂ（１）、・・・、Ｋｂ（ｉ）について、最大値をＫｂ＿ｍａｘに設定し、対応するウィンドウ幅の値をｉ＿ｍａｘに設定する（ステップＳ１２０６）。最後に最適実装法として、ウィンドウ幅をｉ＿ｍａｘとするウィンドウ法を出力し、処理可能ビット数として、Ｋｂ＿ｍａｘを出力し（ステップＳ１２０７）、処理を終了する。
【００８４】
また、変数ｉについて、演算装置１００が対応していないウィンドウ幅であった場合は、該当のウィンドウ幅での算出処理を行わず対応しているウィンドウ幅に対して処理を行ってもよい。同様に、ステップＳ１２０２にて、ａ−２＾ｉが０より大きい場合でも、演算装置１００のハードウェアの制約上、該当のウィンドウ幅以上でテーブルを生成できない場合には、ステップＳ１２０２：Ｎｏのルートに入ってもよい。
【００８５】
（実施の形態３の機能説明）
図１３は、実施の形態３にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法３のフローチャートが図１３となる。実施の形態３のハードウェアの構成は実施の形態１に示したものと等しく、機能的構成も同様であるが、算出部２１０にて、空き時間内に乗算剰余演算処理の利用可能な回数を算出する方法として処理可能ビット数算出法３を使用する。
【００８６】
演算装置１００は、引数として渡されたａを用いて、Ｆｌｏｏｒ（ａ−１）をａに設定する（ステップＳ１３０１）。乗算剰余演算処理の利用回数を示す変数ｍを用意し、０に初期化する（ステップＳ１３０２）。引き続き、ＲＳＡ暗号処理対象ビット列に、処理開始位置ｓを設定する（ステップＳ１３０３）。そして、ＲＳＡ暗号処理対象ビット列を指すポインタとして位置ｐを用意し、位置ｓと同位置に設定する（ステップＳ１３０４）。
【００８７】
演算装置１００は、位置ｐがＲＳＡ暗号処理対象ビット列の先頭かを確認する（ステップＳ１３０５）。先頭の場合は（ステップＳ１３０５：Ｙｅｓ）、ｍ＝ｍ＋１を行い（ステップＳ１３０６）、ｍ＞ａであるかを確認する（ステップＳ１３１０）。先頭でない場合は（ステップＳ１３０５：Ｎｏ）、続けて、位置ｐのビットの値が１かを確認する（ステップＳ１３０７）。１の場合は（ステップＳ１３０７：Ｙｅｓ）、ｍ＝ｍ＋２を行い（ステップＳ１３０９）、０の場合は（ステップＳ１３０７：Ｎｏ）、ｍ＝ｍ＋１を行い（ステップＳ１３０８）、ステップＳ１３１０に移行する。
【００８８】
演算装置１００は、ステップＳ１３１０にて、ｍ＞ａでない場合には（ステップＳ１３１０：Ｎｏ）、続けて、位置ｐがＲＳＡ暗号処理対象ビット列の末尾にあるかを確認する（ステップＳ１３１１）。末尾にない場合は（ステップＳ１３１１：Ｎｏ）、位置ｐを下位方向へ１つ移動し（ステップＳ１３１２）、ステップＳ１３０５に移行する。末尾であった場合には（ステップＳ１３１１：Ｙｅｓ）、ＲＳＡ暗号処理が終了したことを意味し、後述するステップＳ１３１４に移行する。
【００８９】
演算装置１００は、ステップＳ１３１０にて、ｍ＞ａである場合には（ステップＳ１３１０：Ｙｅｓ）、ｍが空き時間内に処理可能なビット数を超えたことを意味するため、位置ｐを上位方向へ１つ移動する（ステップＳ１３１３）。続けて、Ｋｂを位置ｓから位置ｐまでのビット数に設定し（ステップＳ１３１４）、最適実装法として、バイナリ法を出力し、処理可能ビット数として、Ｋｂを出力する（ステップＳ１３１５）。ステップＳ１３１１：Ｙｅｓのルートの場合は、最下位のビット列までＲＳＡ暗号処理が行えることを意味しているため、ステップＳ１３１３を行わず、ステップＳ１３１４を行う。
【００９０】
（実施の形態４の機能説明）
図１４は、実施の形態４にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法４のフローチャートが図１４となる。実施の形態４のハードウェアの構成は実施の形態２に示したものと等しく、機能的構成も同様であるが、算出部２１０にて、空き時間内に乗算剰余演算処理の利用可能な回数を算出する方法として処理可能ビット数算出法４を使用する。演算装置１００は、ｉを１に初期化する（ステップＳ１２０１）。後続するステップではｉをウィンドウ幅として使用する。
【００９１】
次に、演算装置１００は、引数として渡されたａを用いて、ａ−２＾ｉを算出し（ステップＳ１４０２）、ａ＞０かを確認する（ステップＳ１４０３）。ａ＞０であれば（ステップＳ１４０３：Ｙｅｓ）、乗算剰余演算処理の利用回数を示す変数ｍを用意し、０に初期化する（ステップＳ１４０４）。引き続き、ＲＳＡ暗号処理対象ビット列に、処理開始位置ｓを設定する（ステップＳ１４０５）。そして、ＲＳＡ暗号処理対象ビット列を指すポインタとして位置ｐを用意し、位置ｓと同位置に設定する（ステップＳ１４０６）。
【００９２】
位置ｐを設定後、演算装置１００は、位置ｐからｉ−１番目までのビットの値がすべて０かを確認する（ステップＳ１４０７）。０である場合は（ステップＳ１４０７：Ｙｅｓ）、ｍ＝ｍ＋ｉを行い（ステップＳ１４０９）、ｍ＞ａであるかを確認する（ステップＳ１４１０）。値が１であるビットが含まれる場合は（ステップＳ１４０７：Ｎｏ）、ｍ＝ｍ＋ｉ＋１を行い（ステップＳ１４０８）、ステップＳ１４１０に移行する。
【００９３】
演算装置１００は、ステップＳ１４１０にて、ｍ＞ａでない場合には（ステップＳ１４１０：Ｎｏ）、続けて、位置ｐがＲＳＡ暗号処理対象ビット列の末尾にあるかを確認する（ステップＳ１４１１）。末尾にない場合は（ステップＳ１４１１：Ｎｏ）、位置ｐを下位方向へｉ分移動し（ステップＳ１４１２）、ステップＳ１４０７に移行する。末尾であった場合には（ステップＳ１４１１：Ｙｅｓ）、ＲＳＡ暗号処理が終了したことを意味し、後述するステップＳ１４１４に移行する。
【００９４】
演算装置１００は、ステップＳ１４１０にて、ｍ＞ａである場合には（ステップＳ１４１０：Ｙｅｓ）、ｍが空き時間内に処理可能なビット数を超えたことを意味するため、位置ｐを上位方向へｉ分移動する（ステップＳ１４１３）。次に、Ｋｂ（ｉ）を位置ｓから位置ｐまでのビット数として保持し（ステップＳ１４１４）、ｉをインクリメントし（ステップＳ１４１５）、ステップＳ１４０２に移行する。
【００９５】
ステップＳ１４０３にて、ａが０以下の場合は（ステップＳ１４０３：Ｎｏ）、演算装置１００は、保持したＫｂ（１）、・・・、Ｋｂ（ｉ）について、最大値をＫｂ＿ｍａｘに設定し、対応するウィンドウ幅の値をｉ＿ｍａｘに設定する（ステップＳ１４１６）。最後に最適実装法として、ウィンドウ幅をｉ＿ｍａｘとするウィンドウ法を出力し、処理可能ビット数として、Ｋｂ＿ｍａｘを出力し（ステップＳ１４１７）、処理を終了する。
【００９６】
また、変数ｉについて、演算装置１００が対応していないウィンドウ幅であった場合は、該当のウィンドウ幅での算出処理を行わず対応しているウィンドウ幅に対して処理を行ってもよい。同様に、ステップＳ１４０３にて、ａが０より大きい場合でも、演算装置１００のハードウェアの制約上、該当のウィンドウ幅以上でテーブルを生成できない場合には、ステップＳ１４０３：Ｎｏのルートに入ってもよい。
【００９７】
以上説明したように、演算装置１００によれば、ＣＰＵの空き時間にあわせてべき乗剰余演算処理を非均等に分割することにより、１回のＲＳＡ暗号処理を短時間で完了することができる。
【００９８】
また、ビット列を抽出する場合、ビット列を順次抽出してもよい。これにより、べき乗剰余演算処理の対象データの先頭から末尾までを、複数の非均等に分割した処理に分けて処理することができる。また、上記実施の形態では先頭から末尾までを走査する方法を例示したが、逆に、末尾から先頭方向へ走査してもよい。
【００９９】
また、処理可能なビット数を算出する際に、部分演算処理がバイナリ法である場合、バイナリ法における乗算剰余演算処理の利用回数に基づいて、処理可能なビット数を算出してもよい。これにより、バイナリ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１００】
また、処理可能なビット数を算出する際に、部分演算処理がバイナリ法である場合、式（１）を使用してもよい。これにより、具体的にバイナリ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１０１】
また、処理可能なビット数を算出する際に、部分演算処理がバイナリ法である場合、式（３）より乗算剰余演算処理の利用可能な回数を求める。そして、対象データの対象ビットの値に応じて回数を減算し、回数が０になるまで対象ビットを順次読み出し、読み出した対象ビットの数を処理可能なビット数として算出してもよい。これにより、対象データのビット列に０が多く、バイナリ法にて、１ビットあたりに乗算剰余演算処理を１度だけ行うことが多い場合、より多くのビット数を算出可能として算出することができる。
【０１０２】
また、処理可能なビット数を算出する際に、部分演算処理がウィンドウ法である場合、ウィンドウ法における乗算剰余演算処理の利用回数に基づいて、処理可能なビット数を算出してもよい。これにより、ウィンドウ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１０３】
また、処理可能なビット数を算出する際に、部分演算処理がウィンドウ法である場合、式（２）を使用してもよい。これにより、具体的にウィンドウ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、空き時間にあったテーブルサイズを作成することができ、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１０４】
また、処理可能なビット数を算出する際に、部分演算処理がウィンドウ法である場合、式（４）より乗算剰余演算処理の利用可能な回数を求める。そして、対象データのウィンドウ幅分のビット列が取り得るビットパターンに応じて回数をウィンドウ幅分減算し、回数が０になるまでビット列を順次読み出し、読み出したビット列を構成するビットの数を処理可能なビット数として算出してもよい。これにより、対象データのビット列に０が多く、ウィンドウ法にて、対象ビット列あたりに乗算剰余演算処理をウィンドウ幅分だけ行うことが多い場合、より多くのビット数を算出可能として算出することができる。
【０１０５】
また、処理可能なビット数を算出する場合に部分演算処理がウィンドウ法である場合、取り得るウィンドウ幅ごとにビット数を算出し、算出されたビット数のうち最長となるビット数を抽出し、対象データからビット列を抽出し、ウィンドウ法を実行してもよい。これにより、ＣＰＵの空き時間の変化にあわせたウィンドウ幅を設定することができ、１回のＲＳＡ暗号処理を短時間で完了することができる。また、ＣＰＵの空き時間にあわせて非均等に分割した処理ごとに、毎回適切な大きさの事前計算テーブルを生成するため、処理効率を向上することができ、ＲＳＡ暗号処理を短時間で完了することができる。
【０１０６】
また、べき乗剰余演算処理を行う方式として、ＲＳＡ暗号処理を例にしたが、その他のべき乗剰余演算処理や曲線上の点のスカラー倍算を伴う処理、たとえば、楕円曲線暗号、ＥＰＯＣ（Ｅｆｆｉｃｉｅｎｔ Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｐｕｂｌｉｃ−ｋｅｙ ｅｎＣｒｙｐｔｉｏｎ）暗号、ラビン暗号、エルガマル暗号等でも、本実施の形態を利用することができる。
【０１０７】
なお、本実施の形態で説明した演算方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション、組み込み機器等のコンピュータで実行することにより実現することができる。本演算プログラムは、ＲＯＭ、不揮発性メモリ、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本演算プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１０８】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１０９】
（付記１）コンピュータを、
前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出手段、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段、
として機能させることを特徴とする演算プログラム。
【０１１０】
（付記２）前記抽出手段は、
前記対象データの先頭ビットから前記ビット数分のビット列を順次抽出することを特徴とする付記１に記載の演算プログラム。
【０１１１】
（付記３）前記算出手段は、
前記所定の部分演算処理がバイナリ法に関する部分演算処理である場合、前記空き時間と前記乗算剰余演算処理に要する処理時間と前記バイナリ法に関する部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能な前記バイナリ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記バイナリ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列を与えて前記バイナリ法に関する部分演算処理を実行することを特徴とする付記１または２に記載の演算プログラム。
【０１１２】
（付記４）前記算出手段は、
下記式（１）により前記処理可能なビット数を算出することを特徴とする付記３に記載の演算プログラム。
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−１）／２）…（１）
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【０１１３】
（付記５）前記算出手段は、
下記式（２）により前記空き時間内に前記乗算剰余演算処理の利用可能な回数である演算利用可能回数を求め、前記対象ビットの値に応じて演算を行った回数である演算実行回数を加算することにより、前記演算実行回数が前記演算利用可能回数になるまで対象ビットを順次読み出し、読み出した対象ビットの数を前記処理可能なビット数として算出することを特徴とする付記３に記載の演算プログラム。
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−１）…（２）
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【０１１４】
（付記６）前記コンピュータを、
前記所定の部分演算処理がウィンドウ法に関する部分演算処理である場合、前記べき乗剰余演算処理が行われる被対象データをウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成する生成手段、
前記生成手段によって生成されたテーブルから、前記ビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得する取得手段として機能させ、
前記算出手段は、
前記空き時間と前記乗算剰余演算処理に要する処理時間と前記ウィンドウ法に関する部分演算処理における前記乗算剰余演算処理の利用回数と前記生成手段によって生成されたテーブルの生成時間と前記ウィンドウ幅とに基づいて、前記空き時間内で処理可能な前記ウィンドウ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記ウィンドウ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする付記１または２に記載の演算プログラム。
【０１１５】
（付記７）前記算出手段は、
下記式（３）により前記処理可能なビット数を算出することを特徴とする付記６に記載の演算プログラム。
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−２＾ｎ）／（ｎ＋１））＊ｎ…（３）
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ幅を示す。
【０１１６】
（付記８）前記算出手段は、
下記式（４）により前記空き時間内に前記乗算剰余演算処理の利用可能な回数である演算利用可能回数を求め、前記ウィンドウ幅分のビット列が取り得るビットパターンに応じて演算を行った回数である演算実行回数をウィンドウ幅に基づいて加算することにより、前記演算実行回数が前記演算利用可能回数になるまで前記ビット列を順次読み出し、読み出したビット列を構成するビットの数を前記処理可能なビット数として算出することを特徴とする付記６に記載の演算プログラム。
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−２＾ｎ）…（４）
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ幅を示す。
【０１１７】
（付記９）前記算出手段は、
前記ウィンドウ幅ごとに前記ビット数を算出し、
前記抽出手段は、
前記算出手段によって算出されたウィンドウ幅ごとのビット数のうち、最長となるビット数を抽出し、
前記実行手段は、
前記抽出手段によって抽出された最長となるビット数に基づいて、前記ウィンドウ法に関する部分演算処理を実行することを特徴とする付記６〜８のいずれか１つに記載の演算プログラム。
【０１１８】
（付記１０）前記コンピュータを、
前記ウィンドウ幅ごとに、前記テーブルの生成時間を前記乗算剰余演算処理に要する処理時間に基づいて設定する設定手段として機能させ、
前記算出手段は、
前記ウィンドウ幅ごとに、前記設定手段によって設定された生成時間に基づいて前記ビット数を算出し、
前記抽出手段は、
前記ウィンドウ幅ごとに算出されたビット数のうち最長となるビット数分のビット列を抽出し、
前記生成手段は、
前記ビット数が最長となるウィンドウ幅に基づいて、前記被対象データを前記ウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成し、
前記取得手段は、
前記生成手段によって前記ビット数が最長となるウィンドウ幅に基づいて生成されたテーブルから、前記ウィンドウ幅のビット列のビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする付記９に記載の演算プログラム。
【０１１９】
（付記１１）検出手段と算出手段と抽出手段と実行手段とを備えるコンピュータが、
前記検出手段により、前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出工程と、
前記算出手段により、前記検出工程によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出工程と、
前記抽出手段により、前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出工程によって算出されたビット数分のビット列を抽出する抽出工程と、
前記実行手段により、前記抽出工程によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行工程と、
を実行することを特徴とする演算方法。
【０１２０】
（付記１２）一定時間ごとに返す応答までの空き時間を検出する検出手段と、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段と、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段と、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段と、
を備えることを特徴とする演算装置。
【符号の説明】
【０１２１】
１００ 演算装置
２０１ 制御部
２０２ 処理コントロール部
２０３ 受信部
２０４ 演算部
２０５ タイマー
２０６ 空き時間計算部
２０７ リファレンス所要時間格納テーブル
２０８ 処理時間取得部
２０９ 検出部
２１０ 算出部
２１１ 抽出部
２１２ 実行部
２１３ 設定部
２１４ テーブル生成部
２１５ テーブル取得部
【技術分野】
【０００１】
本発明は、演算処理を実行する演算プログラム、演算方法、および演算装置に関する。
【背景技術】
【０００２】
携帯電話、車載器、ハードディスク装置などの組み込み機器が、搭載しているＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）は、ＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）に搭載しているＣＰＵに比べて、処理能力が低い。また、メモリ搭載量も低いのが一般的である。さらに、組み込み機器では、タスクが異常停止していないかを確認するために、一定時間ごとにＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）等の制御部に応答することでタスクの生存確認を行うことがある。応答先としては、装置内の制御部の他、ネットワーク経由による他の装置へ応答することもある。
【０００３】
一方、情報セキュリティ分野で使用されるＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）暗号処理は、演算負荷が大きく、処理能力の低い組み込み機器のＣＰＵでは、ＣＰＵを占有する時間が長くなり、ＣＰＵは、一定時間以内にＲＳＡ暗号処理を終了することができない可能性がある。一定時間以内に処理を終了できない場合、ＲＳＡ暗号処理を実行しているタスクは制御部に応答をすることができずに、制御部はタスクが異常停止していると誤認識をする結果となる。御認識を防ぐためには、ＲＳＡ暗号処理を途中で中断し、制御部に応答を行った後、ＲＳＡ暗号処理を再開することが必要となる。
【０００４】
前述した、ＲＳＡ暗号処理を分割する課題に関しては、ＲＳＡ暗号処理のほとんどを構成しているべき乗剰余演算処理を所定の部分乗算に分割して実行する技術が開示されている（たとえば、下記特許文献１を参照。）。また、べき乗剰余演算の高速化方法であるモンゴメリ乗算剰余演算処理において、複数回に分割して実行する技術が開示されている（たとえば、下記特許文献２を参照。）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００３−２９６２７号公報
【特許文献２】特開平８−１６９３２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来技術において、ＲＳＡ暗号処理を分割する際に、分割した各ＲＳＡ暗号分割処理が同一の長さになるような均等分割を行っていた。このため、ＣＰＵに空き時間が生じ、無駄な時間が存在しているという問題があった。
【０００７】
また、部分乗算を行う際に、事前の前処理として、ある一定範囲のべきに対し、べき乗剰余演算結果を格納する事前計算テーブルの生成処理を行い、事前計算テーブルを参照する場合がある。しかしながら、事前計算テーブルの大きさは常に固定サイズであり、固定の事前計算テーブルを参照したべき乗剰余演算処理を、ＣＰＵの空き時間内に行った場合、空き時間をすべて使いきれるとは限らず、空き時間が残る場合があるという問題があった。
【０００８】
本発明は、上述した従来技術による問題点を解消するため、ＣＰＵの空き時間にあわせてＲＳＡ暗号処理を非均等に分割し、処理効率の向上を図ることができる演算プログラム、演算方法、および演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、本演算プログラム、演算方法、および演算装置は、ＣＰＵの空き時間を検出し、空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における乗算剰余演算処理の利用回数とに基づいて、空き時間内に処理可能なビット数を算出し、算出された処理可能なビット数に基づいて、対象データからビット列を抽出し、抽出されたビット列を与えて、所定の部分演算処理を実行することを要件とする。
【発明の効果】
【００１０】
本演算プログラム、演算方法、および演算装置によれば、ＣＰＵの空き時間にあわせてＲＳＡ暗号処理を非均等に分割し、処理効率の向上を図ることができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１にかかる演算装置のハードウェア構成を示すブロック図である。
【図２】演算装置１００の機能的構成を示すブロック図である。
【図３】従来例と実施の形態１による実行状態を示す図である。
【図４】バイナリ法の概要説明を示す図である。
【図５】バイナリ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。
【図６】ウィンドウ法の概要説明を示す図である。
【図７】ウィンドウ法の処理時間を示す図である。
【図８】ウィンドウ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。
【図９】ウィンドウ法によるＲＳＡ暗号非均等分割処理を行った処理時間例を示す図である。
【図１０】ＲＳＡ暗号非均等分割処理を示すフローチャートである。
【図１１】実施の形態１にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【図１２】実施の形態２にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【図１３】実施の形態３にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【図１４】実施の形態４にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、本発明にかかる演算プログラム、演算方法、および演算装置の好適な実施の形態を詳細に説明する。
【００１３】
（実施の形態１）
（演算装置１００のハードウェア構成）
図１は、実施の形態１にかかる演算装置のハードウェア構成を示すブロック図である。図１において、演算装置１００は、ＣＰＵ１０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ Ｍｅｍｏｒｙ）１０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１０３と、磁気ディスクドライブ１０４と、磁気ディスク１０５と、光ディスクドライブ１０６と、光ディスク１０７と、ディスプレイ１０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）１０９と、キーボード１１０と、マウス１１１と、スキャナ１１２と、プリンタ１１３と、を備えている。また、各構成部はバス１１４によってそれぞれ接続されている。
【００１４】
ここで、ＣＰＵ１０１は、演算装置１００の全体の制御を司る。ＣＰＵ以外にも、リアルタイム処理を求められる組み込み機器で使用されるＤＳＰ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）であってもよい。
【００１５】
ＲＯＭ１０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１０３は、ＣＰＵ１０１のワークエリアとして使用される。磁気ディスクドライブ１０４は、ＣＰＵ１０１の制御にしたがって磁気ディスク１０５に対するデータのリード／ライトを制御する。磁気ディスク１０５は、磁気ディスクドライブ１０４の制御で書き込まれたデータを記憶する。また、演算装置１００の小型化を目的として、磁気ディスク１０５の代わりにＦｌａｓｈ ＲＯＭを使用してもよい。
【００１６】
光ディスクドライブ１０６は、ＣＰＵ１０１の制御にしたがって光ディスク１０７に対するデータのリード／ライトを制御する。光ディスク１０７は、光ディスクドライブ１０６の制御で書き込まれたデータを記憶したり、光ディスク１０７に記憶されたデータをコンピュータに読み取らせたりする。
【００１７】
ディスプレイ１０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００１８】
Ｉ／Ｆ１０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク１１５に接続され、このネットワーク１１５を介して他の装置に接続される。そして、Ｉ／Ｆ１０９は、ネットワーク１１５と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００１９】
キーボード１１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００２０】
スキャナ１１２は、画像を光学的に読み取り、演算装置１００内に画像データを取り込む。なお、スキャナ１１２は、ＯＣＲ（Ｏｐｔｉｃａｌ Ｃｈａｒａｃｔｅｒ Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ１１３は、画像データや文書データを印刷する。プリンタ１１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。なお、組み込み機器環境においては、磁気ディスクドライブ１０４、磁気ディスク１０５、光ディスクドライブ１０６、光ディスク１０７、ディスプレイ１０８、Ｉ／Ｆ１０９、キーボード１１０、マウス１１１、スキャナ１１２、プリンタ１１３、ネットワーク１１５の一部、またはすべてが存在しない構成であってもよい。
【００２１】
（演算装置１００の機能的構成）
次に、演算装置１００の機能的構成について説明する。図２は、演算装置１００の機能的構成を示すブロック図である。演算装置１００は、制御部２０１と、処理コントロール部２０２と、受信部２０３と、演算部２０４と、タイマー２０５と、空き時間計算部２０６と、リファレンス所要時間格納テーブル２０７と、処理時間取得部２０８と、を含む構成である。この制御部となる機能（制御部２０１〜処理時間取得部２０８）は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶装置に記憶されたプログラムをＣＰＵ１０１が実行することにより、その機能を実現する。または、Ｉ／Ｆ１０９を経由して他のＣＰＵが実行することにより、その機能を実現してもよい。
【００２２】
制御部２０１は、演算装置の制御を行うＯＳであり、演算部２０４を含む、すべてのタスクを実行するために、処理コントロール部２０２に処理を命令する機能を有する。具体的には、たとえば、制御部２０１は、処理コントロール部２０２がタスクＡを実行終了後に、タスクＢを実行するように処理コントロール部２０２に命令する。
【００２３】
処理コントロール部２０２は、制御部２０１からの命令にしたがって、タスクを実行する機能を有する。また、演算部２０４以外のタスクを実行後、ＯＳに応答を返すまでの空き時間を空き時間計算部２０６より取得する。具体的には、たとえば、ＯＳに応答を返す周期が３０［ｍｓｅｃ］（ミリ秒）の場合に、ＣＰＵ１０１が他のタスクを１０［ｍｓｅｃ］実行した場合、処理コントロール部２０２は空き時間として２０［ｍｓｅｃ］を取得する。なお、取得結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２４】
受信部２０３は、べき乗剰余演算処理が行われる被対象データを受信する機能を有する。具体的には、たとえば、暗号化を行う場合には、被対象データは平文であり、また、べき乗剰余演算処理の指数部分にあたる対象データとして、公開鍵の情報もあわせて受信する。なお、受信結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２５】
演算部２０４は、処理コントロール部２０２によって実行される機能の一つであり、ＲＳＡ暗号処理でのべき乗剰余演算処理を行う機能を有する。具体的には、たとえば、暗号文＝平文＾公開鍵（ｍｏｄＮ）というべき乗剰余演算処理を行うことで、平文から暗号文を生成する。また、平文＝暗号文＾暗号鍵（ｍｏｄＮ）というべき乗剰余演算処理を行うことで、暗号文から平文を生成する。演算部２０４の内部の詳細は後述する。なお、演算結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２６】
タイマー２０５は、ＣＰＵ１０１に対して一定間隔で割り込みを発生させる機能を有する。具体的には、たとえば、タイマー２０５により割り込みが発生した際に、制御部２０１で管理しているカウンタを増加することで、内部時刻を更新する。カウンタは、たとえば、ＣＰＵ１０１が保持しているレジスタに記憶される。
【００２７】
空き時間計算部２０６は、タイマー２０５の内部時刻から空き時間を計算する機能を有する。具体的には、たとえば、次にＯＳに応答を返す時刻から、現在時刻を引くことで、空き時間を求めることができる。なお、計算結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００２８】
リファレンス所要時間格納テーブル２０７は、乗算剰余演算処理にかかる時間を事前に計算、もしくは計測し、格納しておく領域である。乗算剰余演算処理は、べき乗剰余演算処理の高速化方法であるモンゴメリ乗算剰余演算処理であってもよい。具体的には、たとえば、平文を暗号文にする場合、平文であるべき乗剰余演算処理の被対象データのビット長と、秘密鍵であるべき乗のビット長と、公開鍵であるモジュラスのビット長をインデックスとして、モンゴメリ乗算剰余演算処理にかかる時間を格納する。
【００２９】
また、処理方式がＣＲＴ（Ｃｈｉｎｅｓｅ Ｒｅｍａｉｎｄｅｒ Ｔｈｅｏｒｅｍ）もしくは非ＣＲＴかもインデックスに含めてもよい。リファレンス所要時間格納テーブル２０７は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。または、事前計測した結果をＲＯＭ１０２に保持しておいても良い。また、インデックスを持たず、１０２４ビットの乗算剰余演算処理の結果を保持しておき、利用時には暗黙的に１０２４ビットとして扱ってもよい。
【００３０】
処理時間取得部２０８は、べき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間を取得する機能を有する。具体的には、たとえば、演算装置１００は、リファレンス所要時間格納テーブル２０７から、べき乗剰余演算処理の被対象データのビット長と、べき乗のビット長と、モジュラスのビット長を指定することで、条件に当てはまる場合の処理時間を取得する。なお、取得結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００３１】
次に、実施の形態１にかかる演算部２０４の機能詳細について説明する。演算部２０４は、検出部２０９と、算出部２１０と、抽出部２１１と、実行部２１２と、設定部２１３と、テーブル生成部２１４と、テーブル取得部２１５で構成される。
【００３２】
検出部２０９は、べき乗剰余演算処理より優先度の高い処理を行うまでの空き時間を検出する機能を有する。具体的には、たとえば、他のタスクの処理が終わった時点で、次のＯＳに応答を返す時刻までの空き時間を、空き時間計算部２０６より検出する。なお、検出結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００３３】
算出部２１０は、乗算剰余演算処理に要する処理時間と、べき乗剰余演算処理の部分演算処理における乗算剰余演算処理の利用回数と、空き時間に基づいて、空き時間内で処理可能なビット数を算出する機能を有する。それぞれ、処理時間は処理時間取得部２０８から、空き時間は検出部２０９から検出する。部分演算処理とは、後述するバイナリ法、ウィンドウ法である。さらに、受信部２０３によって受信された対象データのビット列に基づいて、空き時間内で処理可能なビット数を算出してもよい。
【００３４】
部分演算処理でバイナリ法が実装されている場合、処理可能なビット数の算出式として、下記式（１）で算出してもよい。以下、この算出方式を「処理可能ビット数算出法１」と称する。実施の形態１では、処理可能ビット数算出法１を適用している。
【００３５】
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−１）／２）…（１）
【００３６】
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【００３７】
部分演算処理でウィンドウ法が実装されている場合、処理可能なビット数の算出式として、下記式（２）で算出してもよい。以下、この算出方式を「処理可能ビット数算出法２」と称する。後述する実施の形態２では、処理可能ビット数算出法２を適用している。
【００３８】
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−２＾ｎ）／（ｎ＋１））＊ｎ…（２）
【００３９】
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ法にて、１度に処理を行う対象のビット数を示す。以下、ウィンドウ幅とする。
【００４０】
部分演算処理でバイナリ法が実装されている場合、空き時間内に乗算剰余演算処理の利用可能な回数である演算利用可能回数を下記式（３）にて求める。そして、対象ビットの値に応じて演算を実行した回数を加算することにより、演算を実行した回数が演算利用可能回数になるまで対象ビットを順次読み出し、読み出した対象ビットの数を処理可能なビット数として、算出してもよい。具体的には、対象ビットが０ならば回数を１加算し、対象ビットが１ならば回数を２加算する。以下、この算出方式を「処理可能ビット数算出法３」と称する。後述する実施の形態３では、処理可能ビット数算出法３を適用している。
【００４１】
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−１）…（３）
【００４２】
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【００４３】
バイナリ法では、対象ビットが０である場合は乗算剰余演算処理を１回行い、１である場合は乗算剰余演算処理を２回行う。したがって、対象ビットの値に沿って乗算剰余演算処理を行う回数を計算することで、処理可能なビット数を算出できる。
【００４４】
部分演算処理でウィンドウ法が実装されている場合、空き時間内に乗算剰余演算処理の利用可能な回数である演算利用可能回数を下記式（４）にて求める。そして、ウィンドウ幅分のビット列が取り得るビットパターンに応じて演算を実行した回数を加算する。演算を実行した回数が演算利用可能回数になるまでビット列を順次読み出し、読み出したビット列を構成するビットの数を処理可能なビット数として、算出してもよい。具体的には、ビット列がすべて０ならば回数をウィンドウ幅分加算し、ビット列に１が含まれるならば回数をウィンドウ幅＋１分加算する。以下、この算出方式を「処理可能ビット数算出法４」と称する。後述する実施の形態４では、処理可能ビット数算出法４を適用している。
【００４５】
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−２＾ｎ）…（４）
【００４６】
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ幅を示す。
【００４７】
ウィンドウ法では、ｎビットのビット列がすべて０である場合は乗算剰余演算処理をｎ回行い、ビット列に１が含まれる場合は乗算剰余演算処理をｎ＋１回行う。したがって、ｎビットのビット列の値に沿って乗算剰余演算処理を行う回数を計算することで、処理可能なビット数を算出できる。
【００４８】
また、実施の形態２または４でのウィンドウ幅ｎについて、取り得るウィンドウ幅ごとに対して処理可能なビット数を算出し、後述する抽出部２１１にて、最長となるビット数を抽出し、後述する実行部２１２で実行してもよい。また、算出時に後述する設定部２１３にて設定されたテーブルの生成時間を含めて算出してもよい。
【００４９】
また、実施の形態１〜４を同時に複数持つ形態でもよい。具体的には、たとえば、実施の形態１であるバイナリ法と実施の形態２であるバイナリ法を同時に持ち、それぞれ処理可能なビット数を算出する。そして、処理可能なビット数が最大となる部分演算処理と処理可能なビット数を使用してもよい。
【００５０】
算出の具体例として、たとえば、実施の形態１にて、乗算剰余演算処理に要する処理時間が０．１［ｍｓｅｃ］、部分演算処理がバイナリ法、空き時間が２０［ｍｓｅｃ］の場合を考える。バイナリ法における乗算剰余演算処理の利用回数は１ビットに対して２回である。前述の条件では、後述する式１を使用することにより、Ｋｂ＝Ｆｌｏｏｒ（（２０／０．１−１）／２）により、空き時間内に９９ビット処理可能であることが算出できる。なお、算出結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５１】
抽出部２１１は、受信部２０３によって受信された対象データから算出部２１０によって算出されたビット数分のビット列を抽出する機能を有する。また、部分演算処理を開始する開始ビット位置を記憶装置から読み出し、対象データの開始ビット位置から、算出されたビット数分のビット列を抽出する。その後、次の算出時のために、開始ビット位置と算出されたビット数分に基づいて、新たな開始ビット位置を求め、開始ビット位置として記憶装置に格納してもよい。
【００５２】
具体的には、たとえば、算出部２１０によって９９ビット処理可能であるという算出結果を受けとったら、抽出部２１１は、対象データの先頭もしくは記憶装置に格納されている開始ビット位置から９９ビット分のビット列を抽出する。なお、算出結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５３】
実行部２１２は、抽出部２１１によって抽出されたビット列に対して、部分演算処理を実行する機能を有する。具体的には、たとえば、実施の形態１または３では、バイナリ法を実行する。また、実施の形態２または４では、ウィンドウ法を実行する。バイナリ法の概要説明は図４にて、ウィンドウ法の概要説明は図６にて後述する。
【００５４】
設定部２１３は、部分演算処理がウィンドウ法の場合に、ウィンドウ幅ごとに、後述するテーブル生成部２１４で生成するテーブルの作成時間を、処理時間取得部２０８を用いて設定する機能を有する。具体的には、たとえば、ウィンドウ幅が２ならば、テーブルの作成時間は、２＾２×（乗算剰余演算処理）と設定できる。なお、設定結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５５】
テーブル生成部２１４は、部分演算処理がウィンドウ法の場合に、事前に行う処理として、べき乗剰余演算処理が行われる被対象データをウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成する機能を有する。具体的には、たとえば、ウィンドウ幅が４ビットで、被対象データがＸ、モジュラスがＺの場合、Ｘ＾０（ｍｏｄＺ）、Ｘ＾１（ｍｏｄＺ）、・・・、Ｘ＾１５（ｍｏｄＺ）の値を求め、テーブルに格納する。なお、生成結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５６】
テーブル取得部２１５は、部分演算処理がウィンドウ法の場合に、テーブル生成部２１４によって生成されたテーブルから、ビットパターンに基づいて、被対象データをビットパターンにてべき乗剰余した値を取得する機能を有する。具体的には、たとえば、ウィンドウ幅が４ビットで、被対象データがＸ、モジュラスがＺの場合に、ウィンドウ内のビットパターンが９である場合は、テーブルに格納されているＸ＾９（ｍｏｄＺ）の値を取得する。なお、取得結果は、ＲＡＭ１０３、磁気ディスク１０５、光ディスク１０７などの記憶領域に記憶される。
【００５７】
以上の機器、機能を使用して、演算装置１００はべき乗剰余演算処理を行う。次に、従来例と実施の形態１による実行状態を示す。
【００５８】
（実施の形態１の概要説明）
図３は、従来例と実施の形態１による実行状態を示す図である。前提条件として、１０［ｍｓｅｃ］ごとにＯＳに対して応答を返す。従来例での実行状態３０１では、別タスクを実行した後に、分割されたＲＳＡ暗号処理が行われている状態を示している。ＲＳＡ暗号処理を均等に分割する場合、一番空き時間が短い１０〜２０［ｍｓｅｃ］の区間にあわせるため、他の区間、たとえば、０〜１０［ｍｓｅｃ］の区間で空き時間３０３、２０〜３０［ｍｓｅｃ］の区間で空き時間３０４が発生してしまう。
【００５９】
実施の形態１では、ＲＳＡ暗号処理をそれぞれの空き時間を動的に計算して処理分割し、効率的にＣＰＵを利用する。実施の形態１での実行状態３０２では、ＲＳＡ暗号処理は、０〜１０［ｍｓｅｃ］の区間では部分演算処理３０５、１０〜２０［ｍｓｅｃ］の区間では部分演算処理３０６、２０〜３０［ｍｓｅｃ］の区間では部分演算処理３０７といった状態に非均等分割される。
【００６０】
図４は、バイナリ法の概要説明を示す図である。実施の形態１では、部分演算処理にバイナリ法が実装されている。バイナリ法はべき乗部分を２進数表現し、得られたビット列に対して１ビットごとにべき乗剰余演算処理を行う方法である。平文Ｘ、公開鍵ｄ、モジュラスＺ、があるときに、求める暗号文Ｙは、Ｙ＝Ｘ＾ｄ（ｍｏｄＺ）で表すことができる。
【００６１】
ここで、ｄ＝２１としてバイナリ法の具体例を示す。ｄ＝２１を２進数表記すると（１０１０１）となり、式４０１が得られる。式４０１において、符号４０２，４０３，４０５，４０６は２乗算をあらわし、符号４０４，４０７は乗算をあらわす。これら符号４０２〜４０７で示した乗算および２乗算は、ｄ＝２１の２進数表記（１０１０１）の各ビットに対応している。符号４０２の２乗算は２進数表記（１０１０１）の最上位から２番目のビットである０が対応している。以下、順に、符号４０３の２乗算と符号４０４の乗算は、最上位から３番目のビットである１が対応している。符号４０５の２乗算は、最上位から４番目のビットである０が対応している。符号４０６の２乗算と符号４０７の乗算は、最下位のビットである１が対応している。
【００６２】
したがって、ビット列先頭以外の対象ビットが０の場合には２乗算を行い、対象ビットが１の場合には２乗算を行った後に乗算を行うことにより、Ｘ＾２１を得ることができる。また、合同式の性質より、Ａ＊Ｂ（ｍｏｄＺ）＝（Ａ（ｍｏｄＺ））＊（Ｂ（ｍｏｄＺ））（ｍｏｄＺ）となるため、乗算剰余を行った結果同士をさらに乗算剰余することで、べき乗剰余と同じ結果を得ることができる。
【００６３】
図５は、バイナリ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。ＲＳＡ暗号非分割処理の実行状態５０１では１０［ｍｓｅｃ］の段階でＯＳに応答を返すことができない。従来例の実行状態５０２では、バイナリ法を、２乗算のところで分割した例である。タイマーを持たせることで、空き時間に応じてＲＳＡ暗号処理を割り当てている。
【００６４】
モンゴメリ乗算剰余を使用した従来例の実行状態５０３では、モンゴメリ乗算剰余を使用する際に必要な前処理が行われるため、０〜１０［ｍｓｅｃ］の区間では、ＲＳＡ暗号分割処理５０５が１０［ｍｓｅｃ］を超えてしまっている。同様に１０〜２０［ｍｓｅｃ］の区間では、ＲＳＡ暗号分割処理５０６が、２０〜３０［ｍｓｅｃ］の区間では、ＲＳＡ暗号分割処理５０７が、各区間を超過してしまっており、ＯＳに応答を返すことができない状態である。
【００６５】
実施の形態１での実行状態５０４では、モンゴメリ乗算剰余の前処理の時間を含んで処理可能なビット数を算出する。そのため、０〜１０［ｍｓｅｃ］、１０〜２０［ｍｓｅｃ］、２０〜３０［ｍｓｅｃ］、３０〜４０［ｍｓｅｃ］の各区間でＲＳＡ暗号分割処理が終了するように割り当てられている。空き時間内で処理可能なビットの算出式は式（１）となる。
【００６６】
（実施の形態２の概要説明）
図６は、ウィンドウ法の概要説明を示す図である。実施の形態２のハードウェアの構成は実施の形態１に示したものと等しく、機能的構成も同様であるが、部分演算処理はウィンドウ法が実装されている。また、算出部２１０も部分演算処理にあわせた機能となる。Ｙ＝Ｘ＾ｄ（ｍｏｄＺ）にて、ｄを２進数表記することで、ビット列６０１を得る。次に、所定のウィンドウ幅、図６ではｋビットごとにビット列を分割し、分割して得たｋビットのビット列に対してべき乗剰余演算処理を行う。ウィンドウｂm-1、ウィンドウｂm-2、・・・、ウィンドウｂ1、ウィンドウｂ0と分割し、分割して得た結果が式６０２である。
【００６７】
また、ｗ［０］＝Ｘ＾０（ｍｏｄＺ）、ｗ［１］＝Ｘ＾１（ｍｏｄＺ）、・・・、ｗ［２＾（ｋ−１）］＝Ｘ＾（２＾（ｋ−１））（ｍｏｄＺ）までを事前計算テーブルとして事前準備する。定義したｗ［］を使用すると、 ウィンドウｂm-1はｗ［１１１１］と置き換えられる。以下、同様に、ウィンドウｂm-2は、ｗ［０１１０］と置き換えられ、ｂ1は、ｗ［１００１］と置き換えられ、ｂ0は、ｗ［１１０１］と置き換えられる。置き換えた後、ウィンドウごとに２乗算をｋ回行い、さらにｗ［］との乗算を１回行うことを繰り返すことで、Ｙ＝Ｘ＾ｄ（ｍｏｄＺ）を求めることができる。
【００６８】
メモリが潤沢にある環境では、２３〜２５ビット程度のデータ量となる事前計算テーブルを事前計算にて準備しておき、べき乗剰余演算実行時にはこの事前計算テーブルを参照することで、高速な処理を実現できる。しかし、組み込み環境では、メモリ搭載量等の観点から事前計算テーブルを内部に保持し続けることができないため、実行の度にテーブル生成を行うことになり、オーバーヘッドがかかる。よって、一度に参照するビット幅が大きいテーブルを準備すれば、べき乗剰余演算の処理が高速に実行できる反面、事前計算テーブル生成の手間は大きくなる。
【００６９】
図７は、ウィンドウ法の処理時間を示す図である。ウィンドウ法は、処理の内容として、事前計算テーブルを生成する処理と、べき乗剰余演算処理を行う処理との２つに分かれる。図７は、それぞれのウィンドウ幅にあわせた、事前計算テーブルの生成にかかる処理時間と、べき乗剰余処理の処理時間とを表している。
【００７０】
たとえば、ウィンドウ幅が２ビットの場合は、テーブル生成には、２＾２×（乗算剰余演算処理）、べき乗剰余演算処理には、（ｂ＋ｂ／２）×（乗算剰余演算処理）の時間がかかることになる。ここで、ｂは対象データのビット長である。ウィンドウ幅がｎビットであれば、テーブル生成には、２＾ｎ×（乗算剰余演算処理）、べき乗剰余演算処理には、（ｂ＋ｂ／ｎ）×（乗算剰余演算処理）の時間がかかることになる。
【００７１】
図８は、ウィンドウ法によるＲＳＡ暗号非均等分割処理による実行状態を示す図である。ウィンドウ幅を４ビット固定で行ったウィンドウ法の実行状態８０１では、１０〜２０［ｍｓｅｃ］の区間で空き時間８０３が、２０〜３０［ｍｓｅｃ］の区間で空き時間８０４が、それぞれ発生している。空き時間が発生する理由は、ウィンドウ法はバイナリ法よりも一度にまとめて処理を行うため、空きができることがあるためである。
【００７２】
次に、実施の形態２の実行状態８０２では、空き時間にあわせてウィンドウ幅を動的に変更させることで、空き時間を限りなく少なくなるように使用することができる。具体的には、０〜１０［ｍｓｅｃ］の区間では、ウィンドウ幅は４ビットである。同様に、１０〜２０［ｍｓｅｃ］の区間では、ウィンドウ幅は２ビット、２０〜３０［ｍｓｅｃ］の区間では、ウィンドウ幅は５ビット、３０〜４０［ｍｓｅｃ］の区間では、ウィンドウ幅は４ビットといったようにウィンドウ幅が可変となっている。空き時間内で処理可能なビットの算出式は式（２）となる。
【００７３】
図９は、ウィンドウ法によるＲＳＡ暗号非均等分割処理を行った処理時間例を示す図である。ＲＳＡ暗号処理の対象データのビット数を１０２４ビットとする。また、ＯＳに応答を返す間隔を３０［ｍｓｅｃ］とし、別タスク処理時間として、各最適実装法取得回数の各フィールドが対応する。たとえば、１度目は１２［ｍｓｅｃ］、２度目は１０［ｍｓｅｃ］となる。余り時間Ｔは、ＯＳに応答を返す間隔３０［ｍｓｅｃ］と別タスク処理時間の差となる。乗算剰余演算処理が行える回数ａは、余り時間Ｔと１回の乗算剰余演算処理に要する所要時間ｔの商である。
【００７４】
前述した前提条件にて、式（２）をウィンドウ幅１〜５ビットまで行い、最大のＫｂを最適実装法として取得する。たとえば、１度目の場合、Ｋｂ（１）としてウィンドウ幅１ビットの場合は８９ビット、同様に、Ｋｂ（２）は１１６ビット、Ｋｂ（３）は１２９ビット、Ｋｂ（４）は１２８ビット、Ｋｂ（５）は１２０ビットとなり、最大のＫｂはＫｂ（３）となる。したがって、未処理のビットは、１０２４ビットとＫｂ（３）で得た１２９の差となり、８９５ビットとなる。以下、２度目以降も同様の処理を行い、処理残りビットが７５１ビット、７２１ビット、・・・と繰り返す。９度目の時点で処理残りビットがなくなったため処理を終了する。
【００７５】
９度目の分割処理でＲＳＡ暗号処理が終わったため、ＲＳＡ処理に要した処理時間は別タスクの時間も含めると、２７０［ｍｓｅｃ］となる。もし、従来例で処理を行った場合、最も余り時間が短い、ＲＳＡ暗号分割処理の処理時間は５［ｍｓｅｃ］に設定することになる。ウィンドウ幅として４ビットを使用した場合、１度に２４ビット処理することができ、ＲＳＡ暗号処理ビットが１０２４ビットである場合、４３度目、１２９０［ｍｓｅｃ］で終了することになる。
【００７６】
（実施の形態１〜４の機能説明）
図１０は、ＲＳＡ暗号非均等分割処理を示すフローチャートである。図１０は実施の形態１〜４すべての形態で使用され、後述するステップＳ１００４と、ステップＳ１００８にてそれぞれの形態にて対応する処理が行われる。
【００７７】
演算装置１００は、別タスク実行後の空き時間を検出部２０９より検出し、Ｔに格納する（ステップＳ１００１）。続けて、乗算剰余演算処理の処理時間を処理時間取得部２０８により取得し、ｔに格納する（ステップＳ１００２）。演算装置１００は、Ｔとｔを用い、ａ＝Ｔ／ｔを計算し（ステップＳ１００３）、ａを引数として、最適実装法取得および処理可能ビット数算出処理を実行する（ステップＳ１００４）。具体的な処理内容は、それぞれの実施の形態、実施の形態１では図１１、実施の形態２では図１２、実施の形態３では図１３、実施の形態４では図１４にて後述する。
【００７８】
最適実装法と処理可能ビット数を取得できたら、演算装置１００は、今回が初回のＲＳＡ暗号処理であるのかを確認する（ステップＳ１００５）。初回である場合には（ステップＳ１００５：Ｙｅｓ）、受信部２０３によって受信された対象データを入力データとして取得する（ステップＳ１００６）。初回でなく、２回目以降の場合には（ステップＳ１００５：Ｎｏ）、記憶装置に格納してあったＲＳＡ暗号処理途中結果を取得する（ステップＳ１００７）。次に、取得した対象データに対して、算出した処理可能ビット数分、取得した最適実装法を実行する（ステップＳ１００８）。最適実装法は、実施の形態１または３ではバイナリ法を使用し、実施の形態２または４ではウィンドウ法を使用する。
【００７９】
処理可能ビット数分、最適実装法を行った後に、演算装置１００は、ＲＳＡ暗号処理が終了したかを確認する（ステップＳ１００９）。終了した場合には（ステップＳ１００９：Ｙｅｓ）、ＲＳＡ暗号処理結果を出力する（ステップＳ１０１０）。終了していなく、途中であった場合には（ステップＳ１００９：Ｎｏ）、ＲＳＡ暗号処理途中結果を記憶装置に格納する（ステップＳ１０１１）。
【００８０】
（実施の形態１の機能説明）
図１１は、実施の形態１にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法１のフローチャートが図１１となる。演算装置１００は、引数として渡されたａを用いて、Ｋｂ＝Ｆｌｏｏｒ（（ａ−１）／２）を算出する（ステップＳ１１０１）。ステップＳ１１０１で求めたＫｂが処理可能ビット数となり、最適実装法として、バイナリ法を出力し、処理可能ビット数として、Ｋｂを出力し（ステップＳ１１０２）、処理を終了する。
【００８１】
（実施の形態２の機能説明）
図１２は、実施の形態２にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法２のフローチャートが図１２となる。演算装置１００は、ｉを１に初期化する（ステップＳ１２０１）。後続するステップではｉをウィンドウ幅として使用する。
【００８２】
次に、演算装置１００は、引数として渡されたａを用いて、ａ−２＾ｉを算出し、０より大きいかを確認する（ステップＳ１２０２）。０より大きい場合には（ステップＳ１２０２：Ｙｅｓ）、Ｋｂ（ｉ）＝Ｆｌｏｏｒ（（ａ−２＾ｉ）／（ｉ＋１））＊ｉを算出する（ステップＳ１２０３）。算出されたＫｂ（ｉ）を保持し（ステップＳ１２０４）、次のウィンドウ幅で計算するために、ｉをインクリメントし（ステップＳ１２０５）、ステップＳ１２０２に移行する。
【００８３】
ａ−２＾ｉが０以下の場合は（ステップＳ１２０２：Ｎｏ）、演算装置１００は、保持したＫｂ（１）、・・・、Ｋｂ（ｉ）について、最大値をＫｂ＿ｍａｘに設定し、対応するウィンドウ幅の値をｉ＿ｍａｘに設定する（ステップＳ１２０６）。最後に最適実装法として、ウィンドウ幅をｉ＿ｍａｘとするウィンドウ法を出力し、処理可能ビット数として、Ｋｂ＿ｍａｘを出力し（ステップＳ１２０７）、処理を終了する。
【００８４】
また、変数ｉについて、演算装置１００が対応していないウィンドウ幅であった場合は、該当のウィンドウ幅での算出処理を行わず対応しているウィンドウ幅に対して処理を行ってもよい。同様に、ステップＳ１２０２にて、ａ−２＾ｉが０より大きい場合でも、演算装置１００のハードウェアの制約上、該当のウィンドウ幅以上でテーブルを生成できない場合には、ステップＳ１２０２：Ｎｏのルートに入ってもよい。
【００８５】
（実施の形態３の機能説明）
図１３は、実施の形態３にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法３のフローチャートが図１３となる。実施の形態３のハードウェアの構成は実施の形態１に示したものと等しく、機能的構成も同様であるが、算出部２１０にて、空き時間内に乗算剰余演算処理の利用可能な回数を算出する方法として処理可能ビット数算出法３を使用する。
【００８６】
演算装置１００は、引数として渡されたａを用いて、Ｆｌｏｏｒ（ａ−１）をａに設定する（ステップＳ１３０１）。乗算剰余演算処理の利用回数を示す変数ｍを用意し、０に初期化する（ステップＳ１３０２）。引き続き、ＲＳＡ暗号処理対象ビット列に、処理開始位置ｓを設定する（ステップＳ１３０３）。そして、ＲＳＡ暗号処理対象ビット列を指すポインタとして位置ｐを用意し、位置ｓと同位置に設定する（ステップＳ１３０４）。
【００８７】
演算装置１００は、位置ｐがＲＳＡ暗号処理対象ビット列の先頭かを確認する（ステップＳ１３０５）。先頭の場合は（ステップＳ１３０５：Ｙｅｓ）、ｍ＝ｍ＋１を行い（ステップＳ１３０６）、ｍ＞ａであるかを確認する（ステップＳ１３１０）。先頭でない場合は（ステップＳ１３０５：Ｎｏ）、続けて、位置ｐのビットの値が１かを確認する（ステップＳ１３０７）。１の場合は（ステップＳ１３０７：Ｙｅｓ）、ｍ＝ｍ＋２を行い（ステップＳ１３０９）、０の場合は（ステップＳ１３０７：Ｎｏ）、ｍ＝ｍ＋１を行い（ステップＳ１３０８）、ステップＳ１３１０に移行する。
【００８８】
演算装置１００は、ステップＳ１３１０にて、ｍ＞ａでない場合には（ステップＳ１３１０：Ｎｏ）、続けて、位置ｐがＲＳＡ暗号処理対象ビット列の末尾にあるかを確認する（ステップＳ１３１１）。末尾にない場合は（ステップＳ１３１１：Ｎｏ）、位置ｐを下位方向へ１つ移動し（ステップＳ１３１２）、ステップＳ１３０５に移行する。末尾であった場合には（ステップＳ１３１１：Ｙｅｓ）、ＲＳＡ暗号処理が終了したことを意味し、後述するステップＳ１３１４に移行する。
【００８９】
演算装置１００は、ステップＳ１３１０にて、ｍ＞ａである場合には（ステップＳ１３１０：Ｙｅｓ）、ｍが空き時間内に処理可能なビット数を超えたことを意味するため、位置ｐを上位方向へ１つ移動する（ステップＳ１３１３）。続けて、Ｋｂを位置ｓから位置ｐまでのビット数に設定し（ステップＳ１３１４）、最適実装法として、バイナリ法を出力し、処理可能ビット数として、Ｋｂを出力する（ステップＳ１３１５）。ステップＳ１３１１：Ｙｅｓのルートの場合は、最下位のビット列までＲＳＡ暗号処理が行えることを意味しているため、ステップＳ１３１３を行わず、ステップＳ１３１４を行う。
【００９０】
（実施の形態４の機能説明）
図１４は、実施の形態４にかかる最適実装法取得および処理可能ビット数算出処理を示すフローチャートである。処理可能ビット数算出法４のフローチャートが図１４となる。実施の形態４のハードウェアの構成は実施の形態２に示したものと等しく、機能的構成も同様であるが、算出部２１０にて、空き時間内に乗算剰余演算処理の利用可能な回数を算出する方法として処理可能ビット数算出法４を使用する。演算装置１００は、ｉを１に初期化する（ステップＳ１２０１）。後続するステップではｉをウィンドウ幅として使用する。
【００９１】
次に、演算装置１００は、引数として渡されたａを用いて、ａ−２＾ｉを算出し（ステップＳ１４０２）、ａ＞０かを確認する（ステップＳ１４０３）。ａ＞０であれば（ステップＳ１４０３：Ｙｅｓ）、乗算剰余演算処理の利用回数を示す変数ｍを用意し、０に初期化する（ステップＳ１４０４）。引き続き、ＲＳＡ暗号処理対象ビット列に、処理開始位置ｓを設定する（ステップＳ１４０５）。そして、ＲＳＡ暗号処理対象ビット列を指すポインタとして位置ｐを用意し、位置ｓと同位置に設定する（ステップＳ１４０６）。
【００９２】
位置ｐを設定後、演算装置１００は、位置ｐからｉ−１番目までのビットの値がすべて０かを確認する（ステップＳ１４０７）。０である場合は（ステップＳ１４０７：Ｙｅｓ）、ｍ＝ｍ＋ｉを行い（ステップＳ１４０９）、ｍ＞ａであるかを確認する（ステップＳ１４１０）。値が１であるビットが含まれる場合は（ステップＳ１４０７：Ｎｏ）、ｍ＝ｍ＋ｉ＋１を行い（ステップＳ１４０８）、ステップＳ１４１０に移行する。
【００９３】
演算装置１００は、ステップＳ１４１０にて、ｍ＞ａでない場合には（ステップＳ１４１０：Ｎｏ）、続けて、位置ｐがＲＳＡ暗号処理対象ビット列の末尾にあるかを確認する（ステップＳ１４１１）。末尾にない場合は（ステップＳ１４１１：Ｎｏ）、位置ｐを下位方向へｉ分移動し（ステップＳ１４１２）、ステップＳ１４０７に移行する。末尾であった場合には（ステップＳ１４１１：Ｙｅｓ）、ＲＳＡ暗号処理が終了したことを意味し、後述するステップＳ１４１４に移行する。
【００９４】
演算装置１００は、ステップＳ１４１０にて、ｍ＞ａである場合には（ステップＳ１４１０：Ｙｅｓ）、ｍが空き時間内に処理可能なビット数を超えたことを意味するため、位置ｐを上位方向へｉ分移動する（ステップＳ１４１３）。次に、Ｋｂ（ｉ）を位置ｓから位置ｐまでのビット数として保持し（ステップＳ１４１４）、ｉをインクリメントし（ステップＳ１４１５）、ステップＳ１４０２に移行する。
【００９５】
ステップＳ１４０３にて、ａが０以下の場合は（ステップＳ１４０３：Ｎｏ）、演算装置１００は、保持したＫｂ（１）、・・・、Ｋｂ（ｉ）について、最大値をＫｂ＿ｍａｘに設定し、対応するウィンドウ幅の値をｉ＿ｍａｘに設定する（ステップＳ１４１６）。最後に最適実装法として、ウィンドウ幅をｉ＿ｍａｘとするウィンドウ法を出力し、処理可能ビット数として、Ｋｂ＿ｍａｘを出力し（ステップＳ１４１７）、処理を終了する。
【００９６】
また、変数ｉについて、演算装置１００が対応していないウィンドウ幅であった場合は、該当のウィンドウ幅での算出処理を行わず対応しているウィンドウ幅に対して処理を行ってもよい。同様に、ステップＳ１４０３にて、ａが０より大きい場合でも、演算装置１００のハードウェアの制約上、該当のウィンドウ幅以上でテーブルを生成できない場合には、ステップＳ１４０３：Ｎｏのルートに入ってもよい。
【００９７】
以上説明したように、演算装置１００によれば、ＣＰＵの空き時間にあわせてべき乗剰余演算処理を非均等に分割することにより、１回のＲＳＡ暗号処理を短時間で完了することができる。
【００９８】
また、ビット列を抽出する場合、ビット列を順次抽出してもよい。これにより、べき乗剰余演算処理の対象データの先頭から末尾までを、複数の非均等に分割した処理に分けて処理することができる。また、上記実施の形態では先頭から末尾までを走査する方法を例示したが、逆に、末尾から先頭方向へ走査してもよい。
【００９９】
また、処理可能なビット数を算出する際に、部分演算処理がバイナリ法である場合、バイナリ法における乗算剰余演算処理の利用回数に基づいて、処理可能なビット数を算出してもよい。これにより、バイナリ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１００】
また、処理可能なビット数を算出する際に、部分演算処理がバイナリ法である場合、式（１）を使用してもよい。これにより、具体的にバイナリ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１０１】
また、処理可能なビット数を算出する際に、部分演算処理がバイナリ法である場合、式（３）より乗算剰余演算処理の利用可能な回数を求める。そして、対象データの対象ビットの値に応じて回数を減算し、回数が０になるまで対象ビットを順次読み出し、読み出した対象ビットの数を処理可能なビット数として算出してもよい。これにより、対象データのビット列に０が多く、バイナリ法にて、１ビットあたりに乗算剰余演算処理を１度だけ行うことが多い場合、より多くのビット数を算出可能として算出することができる。
【０１０２】
また、処理可能なビット数を算出する際に、部分演算処理がウィンドウ法である場合、ウィンドウ法における乗算剰余演算処理の利用回数に基づいて、処理可能なビット数を算出してもよい。これにより、ウィンドウ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１０３】
また、処理可能なビット数を算出する際に、部分演算処理がウィンドウ法である場合、式（２）を使用してもよい。これにより、具体的にウィンドウ法での処理可能なビット数を算出でき、ＣＰＵの空き時間を有効利用し、空き時間にあったテーブルサイズを作成することができ、１回のＲＳＡ暗号処理を短時間で完了することができる。
【０１０４】
また、処理可能なビット数を算出する際に、部分演算処理がウィンドウ法である場合、式（４）より乗算剰余演算処理の利用可能な回数を求める。そして、対象データのウィンドウ幅分のビット列が取り得るビットパターンに応じて回数をウィンドウ幅分減算し、回数が０になるまでビット列を順次読み出し、読み出したビット列を構成するビットの数を処理可能なビット数として算出してもよい。これにより、対象データのビット列に０が多く、ウィンドウ法にて、対象ビット列あたりに乗算剰余演算処理をウィンドウ幅分だけ行うことが多い場合、より多くのビット数を算出可能として算出することができる。
【０１０５】
また、処理可能なビット数を算出する場合に部分演算処理がウィンドウ法である場合、取り得るウィンドウ幅ごとにビット数を算出し、算出されたビット数のうち最長となるビット数を抽出し、対象データからビット列を抽出し、ウィンドウ法を実行してもよい。これにより、ＣＰＵの空き時間の変化にあわせたウィンドウ幅を設定することができ、１回のＲＳＡ暗号処理を短時間で完了することができる。また、ＣＰＵの空き時間にあわせて非均等に分割した処理ごとに、毎回適切な大きさの事前計算テーブルを生成するため、処理効率を向上することができ、ＲＳＡ暗号処理を短時間で完了することができる。
【０１０６】
また、べき乗剰余演算処理を行う方式として、ＲＳＡ暗号処理を例にしたが、その他のべき乗剰余演算処理や曲線上の点のスカラー倍算を伴う処理、たとえば、楕円曲線暗号、ＥＰＯＣ（Ｅｆｆｉｃｉｅｎｔ Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｐｕｂｌｉｃ−ｋｅｙ ｅｎＣｒｙｐｔｉｏｎ）暗号、ラビン暗号、エルガマル暗号等でも、本実施の形態を利用することができる。
【０１０７】
なお、本実施の形態で説明した演算方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション、組み込み機器等のコンピュータで実行することにより実現することができる。本演算プログラムは、ＲＯＭ、不揮発性メモリ、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本演算プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１０８】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１０９】
（付記１）コンピュータを、
前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出手段、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段、
として機能させることを特徴とする演算プログラム。
【０１１０】
（付記２）前記抽出手段は、
前記対象データの先頭ビットから前記ビット数分のビット列を順次抽出することを特徴とする付記１に記載の演算プログラム。
【０１１１】
（付記３）前記算出手段は、
前記所定の部分演算処理がバイナリ法に関する部分演算処理である場合、前記空き時間と前記乗算剰余演算処理に要する処理時間と前記バイナリ法に関する部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能な前記バイナリ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記バイナリ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列を与えて前記バイナリ法に関する部分演算処理を実行することを特徴とする付記１または２に記載の演算プログラム。
【０１１２】
（付記４）前記算出手段は、
下記式（１）により前記処理可能なビット数を算出することを特徴とする付記３に記載の演算プログラム。
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−１）／２）…（１）
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【０１１３】
（付記５）前記算出手段は、
下記式（２）により前記空き時間内に前記乗算剰余演算処理の利用可能な回数である演算利用可能回数を求め、前記対象ビットの値に応じて演算を行った回数である演算実行回数を加算することにより、前記演算実行回数が前記演算利用可能回数になるまで対象ビットを順次読み出し、読み出した対象ビットの数を前記処理可能なビット数として算出することを特徴とする付記３に記載の演算プログラム。
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−１）…（２）
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を示す。
【０１１４】
（付記６）前記コンピュータを、
前記所定の部分演算処理がウィンドウ法に関する部分演算処理である場合、前記べき乗剰余演算処理が行われる被対象データをウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成する生成手段、
前記生成手段によって生成されたテーブルから、前記ビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得する取得手段として機能させ、
前記算出手段は、
前記空き時間と前記乗算剰余演算処理に要する処理時間と前記ウィンドウ法に関する部分演算処理における前記乗算剰余演算処理の利用回数と前記生成手段によって生成されたテーブルの生成時間と前記ウィンドウ幅とに基づいて、前記空き時間内で処理可能な前記ウィンドウ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記ウィンドウ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする付記１または２に記載の演算プログラム。
【０１１５】
（付記７）前記算出手段は、
下記式（３）により前記処理可能なビット数を算出することを特徴とする付記６に記載の演算プログラム。
Ｋｂ＝Ｆｌｏｏｒ（（Ｔ／ｔ−２＾ｎ）／（ｎ＋１））＊ｎ…（３）
ただし、Ｋｂは処理可能なビット数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ幅を示す。
【０１１６】
（付記８）前記算出手段は、
下記式（４）により前記空き時間内に前記乗算剰余演算処理の利用可能な回数である演算利用可能回数を求め、前記ウィンドウ幅分のビット列が取り得るビットパターンに応じて演算を行った回数である演算実行回数をウィンドウ幅に基づいて加算することにより、前記演算実行回数が前記演算利用可能回数になるまで前記ビット列を順次読み出し、読み出したビット列を構成するビットの数を前記処理可能なビット数として算出することを特徴とする付記６に記載の演算プログラム。
ａ＝Ｆｌｏｏｒ（Ｔ／ｔ−２＾ｎ）…（４）
ただし、ａは演算利用可能回数を、Ｆｌｏｏｒ（）は床関数を、Ｔは空き時間を、ｔは乗算剰余演算処理に要する処理時間を、ｎはウィンドウ幅を示す。
【０１１７】
（付記９）前記算出手段は、
前記ウィンドウ幅ごとに前記ビット数を算出し、
前記抽出手段は、
前記算出手段によって算出されたウィンドウ幅ごとのビット数のうち、最長となるビット数を抽出し、
前記実行手段は、
前記抽出手段によって抽出された最長となるビット数に基づいて、前記ウィンドウ法に関する部分演算処理を実行することを特徴とする付記６〜８のいずれか１つに記載の演算プログラム。
【０１１８】
（付記１０）前記コンピュータを、
前記ウィンドウ幅ごとに、前記テーブルの生成時間を前記乗算剰余演算処理に要する処理時間に基づいて設定する設定手段として機能させ、
前記算出手段は、
前記ウィンドウ幅ごとに、前記設定手段によって設定された生成時間に基づいて前記ビット数を算出し、
前記抽出手段は、
前記ウィンドウ幅ごとに算出されたビット数のうち最長となるビット数分のビット列を抽出し、
前記生成手段は、
前記ビット数が最長となるウィンドウ幅に基づいて、前記被対象データを前記ウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成し、
前記取得手段は、
前記生成手段によって前記ビット数が最長となるウィンドウ幅に基づいて生成されたテーブルから、前記ウィンドウ幅のビット列のビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする付記９に記載の演算プログラム。
【０１１９】
（付記１１）検出手段と算出手段と抽出手段と実行手段とを備えるコンピュータが、
前記検出手段により、前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出工程と、
前記算出手段により、前記検出工程によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出工程と、
前記抽出手段により、前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出工程によって算出されたビット数分のビット列を抽出する抽出工程と、
前記実行手段により、前記抽出工程によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行工程と、
を実行することを特徴とする演算方法。
【０１２０】
（付記１２）一定時間ごとに返す応答までの空き時間を検出する検出手段と、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段と、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段と、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段と、
を備えることを特徴とする演算装置。
【符号の説明】
【０１２１】
１００ 演算装置
２０１ 制御部
２０２ 処理コントロール部
２０３ 受信部
２０４ 演算部
２０５ タイマー
２０６ 空き時間計算部
２０７ リファレンス所要時間格納テーブル
２０８ 処理時間取得部
２０９ 検出部
２１０ 算出部
２１１ 抽出部
２１２ 実行部
２１３ 設定部
２１４ テーブル生成部
２１５ テーブル取得部
【特許請求の範囲】
【請求項１】
コンピュータを、
前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出手段、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段、
として機能させることを特徴とする演算プログラム。
【請求項２】
前記抽出手段は、
前記対象データの先頭ビットから前記ビット数分のビット列を順次抽出することを特徴とする請求項１に記載の演算プログラム。
【請求項３】
前記算出手段は、
前記所定の部分演算処理がバイナリ法に関する部分演算処理である場合、前記空き時間と前記乗算剰余演算処理に要する処理時間と前記バイナリ法に関する部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能な前記バイナリ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記バイナリ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列を与えて前記バイナリ法に関する部分演算処理を実行することを特徴とする請求項１または２に記載の演算プログラム。
【請求項４】
前記コンピュータを、
前記所定の部分演算処理がウィンドウ法に関する部分演算処理である場合、前記べき乗剰余演算処理が行われる被対象データをウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成する生成手段、
前記生成手段によって生成されたテーブルから、前記ビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得する取得手段として機能させ、
前記算出手段は、
前記空き時間と前記乗算剰余演算処理に要する処理時間と前記ウィンドウ法に関する部分演算処理における前記乗算剰余演算処理の利用回数と前記生成手段によって生成されたテーブルの生成時間と前記ウィンドウ幅とに基づいて、前記空き時間内で処理可能な前記ウィンドウ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記ウィンドウ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする請求項１または２に記載の演算プログラム。
【請求項５】
前記算出手段は、
前記ウィンドウ幅ごとに前記ビット数を算出し、
前記抽出手段は、
前記算出手段によって算出されたウィンドウ幅ごとのビット数のうち、最長となるビット数を抽出し、
前記実行手段は、
前記抽出手段によって抽出された最長となるビット数に基づいて、前記ウィンドウ法に関する部分演算処理を実行することを特徴とする請求項４に記載の演算プログラム。
【請求項６】
前記コンピュータを、
前記ウィンドウ幅ごとに、前記テーブルの生成時間を前記乗算剰余演算処理に要する処理時間に基づいて設定する設定手段として機能させ、
前記算出手段は、
前記ウィンドウ幅ごとに、前記設定手段によって設定された生成時間に基づいて前記ビット数を算出し、
前記抽出手段は、
前記ウィンドウ幅ごとに算出されたビット数のうち最長となるビット数分のビット列を抽出し、
前記生成手段は、
前記ビット数が最長となるウィンドウ幅に基づいて、前記被対象データを前記ウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成し、
前記取得手段は、
前記生成手段によって前記ビット数が最長となるウィンドウ幅に基づいて生成されたテーブルから、前記ウィンドウ幅のビット列のビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする請求項５に記載の演算プログラム。
【請求項７】
検出手段と算出手段と抽出手段と実行手段とを備えるコンピュータが、
前記検出手段により、前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出工程と、
前記算出手段により、前記検出工程によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出工程と、
前記抽出手段により、前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出工程によって算出されたビット数分のビット列を抽出する抽出工程と、
前記実行手段により、前記抽出工程によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行工程と、
を実行することを特徴とする演算方法。
【請求項８】
一定時間ごとに返す応答までの空き時間を検出する検出手段と、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段と、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段と、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段と、
を備えることを特徴とする演算装置。
【請求項１】
コンピュータを、
前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出手段、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段、
として機能させることを特徴とする演算プログラム。
【請求項２】
前記抽出手段は、
前記対象データの先頭ビットから前記ビット数分のビット列を順次抽出することを特徴とする請求項１に記載の演算プログラム。
【請求項３】
前記算出手段は、
前記所定の部分演算処理がバイナリ法に関する部分演算処理である場合、前記空き時間と前記乗算剰余演算処理に要する処理時間と前記バイナリ法に関する部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能な前記バイナリ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記バイナリ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列を与えて前記バイナリ法に関する部分演算処理を実行することを特徴とする請求項１または２に記載の演算プログラム。
【請求項４】
前記コンピュータを、
前記所定の部分演算処理がウィンドウ法に関する部分演算処理である場合、前記べき乗剰余演算処理が行われる被対象データをウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成する生成手段、
前記生成手段によって生成されたテーブルから、前記ビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得する取得手段として機能させ、
前記算出手段は、
前記空き時間と前記乗算剰余演算処理に要する処理時間と前記ウィンドウ法に関する部分演算処理における前記乗算剰余演算処理の利用回数と前記生成手段によって生成されたテーブルの生成時間と前記ウィンドウ幅とに基づいて、前記空き時間内で処理可能な前記ウィンドウ法でのビット数を算出し、
前記抽出手段は、
前記対象データから前記算出手段によって算出された前記ウィンドウ法でのビット数分のビット列を抽出し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする請求項１または２に記載の演算プログラム。
【請求項５】
前記算出手段は、
前記ウィンドウ幅ごとに前記ビット数を算出し、
前記抽出手段は、
前記算出手段によって算出されたウィンドウ幅ごとのビット数のうち、最長となるビット数を抽出し、
前記実行手段は、
前記抽出手段によって抽出された最長となるビット数に基づいて、前記ウィンドウ法に関する部分演算処理を実行することを特徴とする請求項４に記載の演算プログラム。
【請求項６】
前記コンピュータを、
前記ウィンドウ幅ごとに、前記テーブルの生成時間を前記乗算剰余演算処理に要する処理時間に基づいて設定する設定手段として機能させ、
前記算出手段は、
前記ウィンドウ幅ごとに、前記設定手段によって設定された生成時間に基づいて前記ビット数を算出し、
前記抽出手段は、
前記ウィンドウ幅ごとに算出されたビット数のうち最長となるビット数分のビット列を抽出し、
前記生成手段は、
前記ビット数が最長となるウィンドウ幅に基づいて、前記被対象データを前記ウィンドウ幅のビット列が取り得るビットパターンごとにべき乗剰余した値を格納するテーブルを生成し、
前記取得手段は、
前記生成手段によって前記ビット数が最長となるウィンドウ幅に基づいて生成されたテーブルから、前記ウィンドウ幅のビット列のビットパターンに基づいて、前記被対象データをべき乗剰余した値を取得し、
前記実行手段は、
前記抽出手段によって抽出されたビット列と前記取得手段によって取得された前記被対象データをべき乗剰余した値とを与えて前記ウィンドウ法に関する部分演算処理を実行することを特徴とする請求項５に記載の演算プログラム。
【請求項７】
検出手段と算出手段と抽出手段と実行手段とを備えるコンピュータが、
前記検出手段により、前記コンピュータが一定時間ごとに返す応答までの空き時間を検出する検出工程と、
前記算出手段により、前記検出工程によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出工程と、
前記抽出手段により、前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出工程によって算出されたビット数分のビット列を抽出する抽出工程と、
前記実行手段により、前記抽出工程によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行工程と、
を実行することを特徴とする演算方法。
【請求項８】
一定時間ごとに返す応答までの空き時間を検出する検出手段と、
前記検出手段によって検出された空き時間とべき乗剰余演算処理を構成する乗算剰余演算処理に要する処理時間と所定の部分演算処理における前記乗算剰余演算処理の利用回数とに基づいて、前記空き時間内で処理可能なビット数を算出する算出手段と、
前記べき乗剰余演算処理の指数部分にあたる対象データから前記算出手段によって算出されたビット数分のビット列を抽出する抽出手段と、
前記抽出手段によって抽出されたビット列を与えて前記所定の部分演算処理を実行する実行手段と、
を備えることを特徴とする演算装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−７５６１１（Ｐ２０１１−７５６１１Ａ）
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願番号】特願２００９−２２３８８３（Ｐ２００９−２２３８８３）
【出願日】平成２１年９月２９日（２００９．９．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願日】平成２１年９月２９日（２００９．９．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]