説明

剰余乗算処理装置

【課題】剰余乗算器を用い、剰余乗算器が処理可能なビット長を越えるデータの剰余乗算を処理する剰余乗算処理装置を提供する。
【解決手段】剰余乗算処理装置において、剰余乗算器113が処理できるビット長にあわせ、剰余乗算の対象データを分解する。剰余乗算器113の出力結果を用いて作成した、剰余乗算の計算に必要なデータを記憶装置123へ格納する。記憶領域の利用量が最小となるよう、一時データを逐次的に特定の記憶領域へ蓄積する。記憶領域へ蓄積された一時データを合わせ、剰余乗算器113が処理できるビット長を越えた剰余乗算の解を作成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、セキュリティ技術に用いられる剰余乗算処理装置に関し、特にICカード、PDA、TPM等の小型端末から、ストレージ装置やサーバ装置等の大型機器まで、各装置が搭載する暗号機器上の実装技術に関する。
【背景技術】
【0002】
<高速な剰余乗算の必要性>
RSA暗号などの公開鍵暗号では、重い計算処理である、べき乗の剰余乗算を計算する必要がある。そのため、高性能なCPUを搭載できないICカードや、処理が集中するストレージ装置やサーバ装置では、剰余乗算を処理するハードウェア(以降、剰余乗算器と呼ぶ)を用い、処理の重いべき乗の剰余乗算を高速にハードウェアで処理する。特に、古典的な剰余乗算やモンゴメリ乗算は、効率的な計算手法であり、多くの剰余乗算器がそれらの計算手法を採用している。
【0003】
<RSA暗号の復号化>
2048ビット等の、ビット長の長いRSA暗号を高速に処理するため、剰余乗算の演算処理を分割し、高速に剰余乗算を計算する手段が知られている。この手法で秘密鍵の情報を必要とする手法は古くから知られており、RSA暗号の復号化(または署名生成)処理にて利用できる。
【0004】
<RSA暗号の暗号化>
秘密鍵の情報を用いずに、剰余乗算の演算処理を分割する手法も研究されている。RSA暗号の暗号化(または署名検証)処理では、復号化(または署名生成)処理とは異なり、秘密の情報を用いる必要がない。暗号化(または署名検証)処理にも対応でき、剰余乗算器が処理できるビット長を越えた剰余乗算を、剰余乗算器を用い、高速に計算する研究が報告されている。従来の研究報告では、剰余乗算器が古典的な剰余乗算を実装する場合(非特許文献1と非特許文献2)と、モンゴメリ乗算を実装する場合(非特許文献3)に大別できる。
【非特許文献1】W. Fischer, J.−P. Seifert: “Increasing the bitlength of crypto−coprocessors” CHES2002, vol. 2523 of Lecture Notes in Computer Science, Springer−Verlag, pp. 71−−81 (2003).
【非特許文献2】Benoit Chevallier−Mames, Marc Joye, and Pascal Paillier: “Faster Double−Size Modular Multiplication From Euclidean Multipliers” CHES2003, vol. 2779 of Lecture Notes in Computer Science, Springer−Verlag, pp. 214−227 (2003).
【非特許文献3】Masayuki Yoshino, Katsuyuki Okeya, and Camille Vuillaume. Unbridlethe Bit−Length of a Crypto−Coprocessor with Montgomery Multiplication.In Preproceedings of SAC2006 pp. 184−198(2006)
【発明の開示】
【発明が解決しようとする課題】
【0005】
非特許文献1、非特許文献2、非特許文献3に紹介された従来技術による実現手法には、以下の課題がある。
【0006】
課題1:計算に必要な記憶容量が多い。
【0007】
課題1は、非特許文献1、非特許文献2、非特許文献3に共通の課題である。
【0008】
剰余乗算またはべき乗の剰余乗算を高速に実現するため、計算過程で一時的なデータを格納する記憶領域が必要である。しかし、この記憶領域は、一般に、高速アクセスを可能とする、高価で容量が限られた記憶領域を用いる。前記の文献いずれにおいても、利用する記憶容量の最適化が検討されておらず、十分な容量の記憶領域を持たない暗号機器または演算に利用できる記憶領域が限定された暗号機器では、従来の実現手法が利用できない。
【0009】
課題2:剰余乗算器が古典的な剰余乗算を実装する場合、剰余乗算器が処理できるビット長の2倍の剰余乗算を実行できない。
【0010】
非特許文献1、非特許文献2では、剰余乗算器が古典的な剰余乗算を実装する場合を主対象に、剰余乗算器が処理できるビット長の2倍の剰余乗算を実現する手法を紹介している。紹介される手法では、正の整数をwとすると、最大wビットのビット長の剰余乗算を処理できる剰余乗算器を用い、2wビットの剰余乗算を実行する際には、wビットのデータ同士を加算または減算した結果を、剰余乗算器に入力する必要がある。しかし、演算後のデータのビット長はw+α(αは正の整数)であり、剰余乗算器の処理できる最大ビット長wを越えてしまうため、剰余乗算器を利用できなくなってしまう。
【0011】
課題3:剰余乗算器がモンゴメリ乗算を実装する場合、剰余乗算器が処理できるビット長の2倍の剰余乗算を実行するには、大きな計算量を要する補正処理が必要である。
【0012】
非特許文献3では、剰余乗算器がモンゴメリ乗算を実装する場合を主対象に、剰余乗算器が処理できるビット長の2倍の剰余乗算を実現する手法を紹介する。紹介される手法では、データの加算または減算した結果が剰余乗算器に入力できるビット長(wとする)を越えるとき、wビットのデータの加算または減算により、剰余乗算器に入力できるようデータのビット長を減らし、剰余乗算器が出力するデータに対し、再びwビットのデータの加算または減算を行って、wを越えたビット長のデータの計算結果を得ている。そのため、wビットの加算または減算に係る計算処理が必要であり、全体の処理が遅くなってしまう。
【0013】
本発明の目的は、上記の課題を克服し、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越えるデータの剰余乗算を処理する剰余乗算処理装置を提供することにある。
【0014】
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【0015】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。
【0016】
すなわち、代表的なものの概要は、剰余乗算処理装置が計算過程で作成するデータを格納する記憶領域を指定する出力指示部を備えたものである。
【発明の効果】
【0017】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【0018】
すなわち、代表的なものによって得られる効果は、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算が処理できる。
【発明を実施するための最良の形態】
【0019】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態において、同一の部材には原則として同一の符号を付け、繰り返しの説明は省略する。
【0020】
<本発明の概要>
本発明では、剰余乗算を用いた剰余乗算を行う剰余乗算器において、剰余乗算器が許容できる剰余乗算のビット長を越える剰余乗算を実施する。
【0021】
また、本発明では、対象とするディジタル化されたデータをメッセージと呼ぶ。本発明では、剰余乗算器が処理できるよう、入力された剰余乗算の対象となるメッセージを分解し、剰余乗算器に適した形式にメッセージを変換する。
【0022】
さらに、変換されたメッセージを、剰余乗算器に入力できるサイズに合わせて変換した後、メモリ等の記憶領域に出力する。剰余乗算器はメッセージを記憶領域から読み出し、剰余乗算を実行する。得られた剰余乗算の剰余から、剰余乗算の種類に基づく、剰余乗算の商と剰余を求める。
【0023】
剰余乗算の商とは、剰余乗算に関するある定義した式を満たすメッセージを指し、剰余乗算の剰余とは、剰余乗算器が実装する剰余乗算が出力するメッセージを指す。剰余乗算器のビット長を越えた剰余乗算を計算するため、剰余乗算器を用いて、剰余乗算の商と剰余の複数回の計算が必要であるが、全ての剰余と商を個別に保存しておく必要は無い。
【0024】
そこで、メッセージを格納する適当な記憶領域を用意し、計算中に、用意した記憶領域に逐次的に剰余乗算の商と剰余の情報を蓄積する。蓄積した記憶領域内の情報を合成すると、最終的に剰余乗算器の処理できるビット長を越えた剰余乗算の解となるメッセージが得られる。
【0025】
(実施の形態1)
<剰余乗算処理装置を適用した通信システムの全体構成>
図1により、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムの全体構成について説明する。なお、図1に示す通信システムの全体構成は、後述する実施の形態2、5においても基本的に共通である。図1は本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【0026】
図1において、通信システムは、ネットワーク151によってコンピュータA101とコンピュータB102が接続されている。
【0027】
コンピュータA101は、コンピュータ外部とのメッセージ入出力を行なう入出力インタフェース111、メッセージの変換処理(暗号処理も含む)を担当する処理装置121を装備する。処理装置121は、さらにメッセージの演算処理を担当する演算装置122と、メッセージを格納する記憶装置123に分けられる。
【0028】
例えば、記憶装置123に格納されたプログラムを演算装置122が実行し、剰余乗算処理装置が含まれる処理装置121を実現する。演算装置122はCPU112や剰余乗算器113などの演算装置122から構成され、記憶装置123は揮発性のメモリであるRAM131、RAM141、不揮発性のメモリであるEEPROM132、ROM133から構成される。
【0029】
CPU112は、記憶装置123に対しメッセージの読みだし、書き込み等が処理できる。例えば、ROM133にプログラム、EEPROM132にプログラムに入力するメッセージ、RAM131またはRAM141にプログラムの実行中に必要なメッセージを格納し、CPU112はプログラムとメッセージを読み出し、プログラムの実行中にメッセージの書き込み等を実行する。
【0030】
剰余乗算器113は、処理できるメッセージの最大のビット長が定められた、剰余乗算を実行する計算装置またはプログラムであり、RAM141に格納されたメッセージのみにアクセスできる。剰余乗算器113は、RAM141の固定領域に格納されたメッセージを、剰余乗算の乗数、被乗数、法とみなし、実装する剰余乗算(モンゴメリ乗算、古典的な剰余乗算など)に基づき、剰余乗算の演算結果(剰余)をRAM141に出力する。
【0031】
実施の形態1と後述する実施の形態5では剰余乗算器113がモンゴメリ乗算を実装する場合を、後述する実施の形態2では剰余乗算器113が古典的な剰余乗算を実装する場合を想定する。
【0032】
どのメッセージが剰余乗算の乗数、被乗数、法に該当するかを剰余乗算器113が判別できるよう、RAM141内の記憶領域はラベル付けされており、乗数を入力する記憶領域をXA、被乗数を入力する記憶領域をXB、法を入力する記憶領域をXN、剰余乗算器113が計算過程で利用する記憶領域をXW、計算結果を出力する記憶領域をXRと呼ぶ。
【0033】
従って、剰余乗算器113はXAに入力されたメッセージを乗数、XBに入力されたメッセージを被乗数、XNに入力されたメッセージを法とみなし、剰余乗算の演算結果(剰余)をXRに出力する。これらのラベル付けは固定でも、可変でも良く、また、各ラベルが指定する記憶領域が重なっていて(例えば、XRとXAが指す記憶領域が同一である、など)もよい。
【0034】
なお、剰余乗算器113は、最大w+h(wは正の整数、hは0以上w未満の整数)ビットのメッセージに対する剰余乗算を処理できるとする。
【0035】
コンピュータA101内のプログラムは、予め、コンピュータA101内の記憶装置123に格納されていても良く、必要な際に入出力インタフェース111を介して接続するコンピュータ、または当該コンピュータが利用可能な物理媒体を介して上記記憶装置123に導入されてもよい。物理媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体(すなわちネットワークまたはネットワークを伝搬する搬送波やディジタル信号)を指す。
【0036】
なお、図1示す構成において、コンピュータA101は、外部への入出力用に、キーボードやモニターと接続していてもよい。また、コンピュータA101内の演算装置122の構成に、乗算を実行する乗算器を加えても良く、乗算器を剰余乗算器の代わりとして用いても良い。
【0037】
コンピュータB102は、コンピュータA101と同様の、入出力インタフェース111、処理装置121から構成される。
【0038】
<全体処理>
次に、図2により、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置121が行う全体処理について説明する。図2は本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図であり、本発明の実施の形態1に係る剰余乗算処理装置の演算処理の対象はメッセージとして取り扱われている。メッセージは、ディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。なお、図2に示すシーケンス図は、後述する各実施の形態においても共通である。
【0039】
データ処理部115は、入出力インタフェース111あるいは記憶装置123を介してメッセージが入力されると(S201)、入力されたメッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるようにメッセージを区切る。また、短い場合には、パディング処理により、メッセージを予め定めたビット長となるように設定する。以下、所定のビット長として2wビットに区切られている部分メッセージ(これ以降、部分メッセージをメッセージと呼ぶ)について説明する。ただし、wは正の整数とする。
【0040】
データ処理部115は、メッセージを2倍剰余乗算部116に出力する(S202)。
【0041】
2倍剰余乗算部116では、まず、入力されたメッセージを剰余乗算器113が実装する剰余乗算(モンゴメリ乗算、古典的な剰余乗算など)に適した形式に変換し、剰余乗算器113を用い、2wビットの剰余を計算する。2倍剰余乗算部116は、剰余乗算器113が実装する剰余乗算に適した形式からメッセージをデータ処理部115へ入力時の整数表現に変換し、データ処理部115へ出力する(S203)。
【0042】
データ処理部115では、2wビットのメッセージを、入出力インタフェース111または記憶装置123へ出力する(S204)。
【0043】
なお、データ処理部115と2倍剰余乗算部116のメッセージの受け渡しは、記憶装置123へのメッセージの書き込みと読み出し、またはネットワーク151を用いる。
【0044】
<2倍剰余乗算部の機能ブロック>
次に、図3により、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の2倍剰余乗算部116の構成について説明する。図3は本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の2倍剰余乗算部の構成を示す機能ブロック図である。なお、図3に示す機能ブロック図は、後述する各実施の形態においても共通である。
【0045】
図3において、2倍剰余乗算部116は、表現処理部301、入出力処理部302、剰余処理部303、共通部304からなる。表現処理部301は、分割部311、合成部312からなる。入出力処理部302は、入力部321、補正部322、出力指示部323、蓄積部324からなる。剰余処理部303は、剰余乗算器取扱部331、商演算部332、移動部333、法変更部334、乗数変更部335からなる。共通部304は、加減乗算部341、剰余計算部342、条件判定部343からなる。
【0046】
表現処理部301、入出力処理部302、剰余処理部303については、それぞれ後述する各実施の形態毎に説明することとし、ここでは共通部304について説明する。共通部304は、表現処理部301、入出力処理部302、剰余処理部303から呼び出せる共通の機能の集合である。
【0047】
加減乗算部341は、加算、減算、乗算などの基本演算機能を有する。加減乗算部341は、記憶装置123に格納された、指定された二つのメッセージを入力としてみなし、加算実行時には二つのメッセージの値を加算した値をもつメッセージを作成し、減算実行時には一番目のメッセージの値から二番目のメッセージを減算した値をもつメッセージを作成し、乗算実行時には二つのメッセージの積の値をもつメッセージを作成し、指定された記憶装置123の記憶領域へ作成したメッセージを出力する。
【0048】
剰余計算部342は、記憶装置123に格納された、指定された二つのメッセージを入力としてみなし、一番目のメッセージの値を二番目のメッセージの値で割った時の剰余の値をもつメッセージを作成し、指定された記憶装置123の記憶領域へ作成したメッセージを出力する。条件判定部343は、メッセージの値がある条件を満たすか否かを判定し、その判定結果をメッセージの出力元の機能ブロックへ出力する。
【0049】
なお、蓄積部324と共通部304にて第1の処理部を構成し、剰余処理部303と共通部304にて第2の処理部を構成し、分割部311と共通部304にて第3の処理部を構成し、補正部322と共通部304にて第4の処理部を構成する。
【0050】
以下では、各実施の形態において、コンピュータA101の2倍剰余乗算部116の処理の詳細を中心に説明する。
【0051】
<実施の形態1の概要>
本実施の形態では、剰余乗算器113がモンゴメリ乗算を実装する場合、2倍剰余乗算部116が、2wビットからなるメッセージを対象に、モンゴメリ乗算に基づく剰余乗算を計算する第1の計算方法について説明する。ただし、wは正の整数とする。
【0052】
<2倍剰余乗算部の処理の概要>
次に、図4により、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の2倍剰余乗算部116の処理について説明する。図4は本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の2倍剰余乗算部の処理を示すシーケンス図であり、2倍剰余乗算部116の機能ブロックである表現処理部301、入出力処理部302、剰余処理部303のメッセージの受け渡しの様子を示している。
【0053】
まず、表現処理部301へメッセージが入力される(S401)。表現処理部301は、入力したメッセージから、モンゴメリ乗算の計算用に変換したメッセージ(以降、モンゴメリ乗算用のメッセージと呼ぶ)を作成し、入出力処理部302へ出力する(S402)。入出力処理部302は、適当なメッセージまたは定数を選択し(詳細な処理内容は後述)、剰余処理部303へ出力する。
【0054】
剰余処理部303は、後述する(式1)によって定義されたモンゴメリ乗算の商と剰余を計算し、入出力処理部302へ出力する。入出力処理部302と剰余処理部303は、上記のメッセージの交換処理を複数回繰り返す(S403、S404)。入出力処理部302は、複数個のモンゴメリ乗算用の商と剰余を合成したメッセージを、表現処理部301へ出力する(S451)。表現処理部301は、モンゴメリ乗算用の商と剰余を合成したメッセージをデータ処理部115へ出力する(S452)。
【0055】
なお、表現処理部301、入出力処理部302、剰余処理部303のメッセージの受け渡しには、記憶装置123へのメッセージの書き込みと読み出しを用い、メッセージの受け渡しを実施する。ただし、ネットワーク151を用い、メッセージの受け渡しを実施しても良い。
【0056】
<表現処理部の処理>
次に、コンピュータA101内の表現処理部301の行う分割処理と合成処理について説明する。
【0057】
まず、表現処理部301の行う分割処理について説明する。表現処理部301は、メッセージをモンゴメリ乗算の計算に適した形式であるモンゴメリ乗算用のメッセージに変換する機能を有する。ただし、モンゴメリ乗算の計算に適した形式とは、2wビットの整数Xを上位側wビットの整数xと下位側wビットの整数xで表すように、変換した(式1)を満たす整数表現を指す。
【0058】
X=x+x …(式1)
ただし、0≦X<22wかつ0≦x、x<2である。
【0059】
まず、表現処理部301内の分割部311は、2wビットのメッセージA、メッセージB、メッセージNを記憶装置123から読み込む(S401)。次に、分割部311は2wビットのメッセージA、2wビットのメッセージB、2wビットのメッセージNを上位wビットと下位wビットに分け、(式1)を満たすよう、メッセージAからメッセージaとメッセージa、メッセージBからメッセージbとメッセージb、メッセージNからメッセージnとメッセージnを作成する。従って、以下の式が成り立つ。
【0060】
N=n+n
A=a+a
B=b+b
分割部311は、記憶装置123にメッセージnとメッセージn、メッセージa、メッセージa、メッセージb、メッセージbを出力する(S402)。
【0061】
表現処理部301の行う合成処理について説明する。表現処理部301内の合成部312は、入出力処理部302が格納したメッセージqsとメッセージrsを用い、(rs+qs)の値を保持するメッセージCを作成する機能を有する。
【0062】
まず、表現処理部301内の合成部312は、メッセージqとメッセージrを記憶装置123から読み込む(S451)。次に、メッセージqsとメッセージrsを用い、(rs+qs)の値を保持するメッセージCを作成する。従って、メッセージC、メッセージrs、メッセージqsには以下の式が成り立つ。
【0063】
C=rs+qs
合成部312は、共通部304における条件判定部343を用い、メッセージCが条件式0≦C<Nを満たすかを判定する。条件式を満たさない場合は、共通部304における剰余計算部342を用い、以下の式を満たすメッセージCを作成する。
【0064】
C=(rs+qs)mod N
ただし、0≦C<N<22wである。合成部312は、メッセージCを記憶装置123へ出力する(S452)。
【0065】
なお、表現処理部301の分割部311は、複数の分割処理の手法を有する。メッセージNから、上位wビットのメッセージnと下位wビットのメッセージnに分割すると、剰余乗算の法になるメッセージnが小さくなりすぎ、補正処理が増え、結果的に計算処理が増加することがある。この計算処理を減らすため、次式に基づき、メッセージnの代わりに(2−n)の値を持つメッセージn’を作成し、剰余乗算の法として用いる。
【0066】
N=(n+1)2−(2−n
=n’+n’
ただし、n’=n+1かつn’=−(2−n)である。
【0067】
<入出力処理部の処理>
次に、図5〜図8により、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部302の処理について説明する。図5〜図8は本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【0068】
MUは、剰余処理部303を表し、剰余処理部303に入力するメッセージの組はMUの右辺の括弧内に、剰余処理部303から出力するメッセージの組は左辺の括弧内に表す。
【0069】
入出力処理部302と剰余処理部303のメッセージの受け渡しには、記憶装置123を用いる。メッセージの格納領域として、RAM141においてラベル付けされたXA、XB、XN、XRと、他の記憶領域(例えばRAM131)においてラベル付けされたYQ、YR、YT(メッセージの格納用に領域を定義)を用いる。
【0070】
なお、入出力処理部302と剰余処理部303におけるメッセージ交換の際の記憶装置123の利用方法の詳細については、図10と図11を用いて後述する。
【0071】
<入出力処理>
入力部321は、メッセージaをXAに、メッセージbをXBに、メッセージnをXNに格納する。出力指示部323は、剰余処理部303へ出力する商を指すメッセージqをXBに、剰余rを指すメッセージrをYTに格納するよう指示する(S501)。
【0072】
入力部321は、メッセージnをXAに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq2をXAに、剰余を指すメッセージr2をYRに格納するよう指示する(S502)。
【0073】
蓄積部324は、XAに格納されたメッセージq2とYTに格納されたメッセージrを加減乗算部341に入力し、(r−q)の値を持つメッセージtをYQに格納する(S503)。
【0074】
入力部321は、メッセージaをXAに、メッセージbをXBに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq3をXAに、剰余を指すメッセージr3をYTに格納するよう指示する(S504)。
【0075】
蓄積部324は、YQに格納されたメッセージtとXAに格納されたメッセージqを加減乗算部341に入力し、(t−q)の値を持つメッセージtをYQに格納するよう指示する。さらに、蓄積部324は、YRに格納されたメッセージr2とYTに格納されたメッセージrを加減乗算部341に入力し、(r+r)の値を持つメッセージrをYRに格納する(S505)。
【0076】
入力部321は、加減乗算部341に対してメッセージを交換し、(a+a)の値を持つメッセージ(a+a)をXAに、(b+b)の値を持つメッセージ(b+b)をXBに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq4をXAに、剰余を指すメッセージr4をYTに格納するよう指示する(S506)。
【0077】
蓄積部324は、YQに格納されたメッセージtとXAに格納されたメッセージqを加減乗算部341に入力し、(t+q)の値を持つメッセージtをXBに格納する。さらに、蓄積部324は、YTに格納されたメッセージrとXAに格納されたメッセージqを加減乗算部341に入力し、(r+q)の値を持つメッセージtをYTに格納する。さらに、蓄積部324は、XBに格納されたメッセージtとYRに格納されたメッセージrとYTに格納されたメッセージtを加減乗算部341に入力し、(−t+t−r)の値を持つメッセージqをYQに格納する(S507)。
【0078】
入力部321は、定数1をXBに、メッセージnをXNに格納する。出力指示部323は、剰余処理部303へ、商を指すメッセージq5をXBに、剰余を指すメッセージr5をYTに格納するよう指示する(S508)。
【0079】
蓄積部324は、YQに格納されたメッセージqとYTに格納されたメッセージrを加減乗算部341に入力し、(q+r)の値を持つメッセージqをYQに格納する(S509)。
【0080】
入力部321は、メッセージnをXAに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq6をXAに、剰余を指すメッセージr6をYTに格納するよう指示する(S510)。
【0081】
蓄積部324は、XAに格納されたメッセージqとYQに格納されたメッセージqを加減乗算部341に入力し、(q−q)の値を持つメッセージqをYQに格納する。さらに、蓄積部324は、YTに格納されたメッセージrとYRに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージrをYRに格納する(S511)。
【0082】
<乗数と被乗数の補正処理>
補正部322は、剰余処理部303が適切に処理できるよう、メッセージの値を変更する機能を有する。例えば、剰余処理部303がメッセージxに対し、0≦x<2の値域を条件とする場合の、補正部322が関わる剰余乗算の計算処理を示すフローチャートを図6に示す。図6は、図5で示したフローチャートの各ステップに加え、補正部322の補正処理が加わる。
【0083】
以降では、図6の補正部322の補正処理に関連するステップのみを説明する。
【0084】
補正部322は、下記の式を用い、0≦q<2を満たすよう、qとrの値を変更する。
【0085】
←q+i2
←r−in
ただし、iは小さな整数である。また、qの値を変更する必要がない場合、i=0が成り立ち、S501aの処理は不要である(S501a)。
【0086】
補正部322は、下記の式を用い、0≦a+a、b+b<2を満たすよう、値を変更する。
【0087】
←a+a+i2
←b+b+j2
ただし、i、jは小さな整数である。また、a+a、b+bの値を変更する必要がない場合、i=0、j=0が成り立つ(S505a)。
【0088】
入力部321は、メッセージtをXAに、メッセージtをXBに、定数1をXNに格納する。出力指示部323は、剰余処理部303から商を指すメッセージqをXAに、剰余を指すメッセージrをYTに格納するよう指示する(S506a)。ただし、S505aでi=0かつj=0が成り立つ場合、S506aの代わりにS506を実行しても良い。
【0089】
補正部322は、YTに格納されたメッセージrとXAに格納されたメッセージtとXBに格納されたメッセージtを加減乗算部341に入力し、(r+it+jt)の値を持つメッセージrとしてYTに格納する(S506b)。
【0090】
補正部322は、下記の式を用い、0≦t<2を満たすよう、tの値を変更する。
【0091】
←t+i2
ただし、iは小さな整数である。また、tの値を変更する必要がない場合、i=0が成り立ち、S507aの処理は不要である(S507a)。
【0092】
補正部322は、YTに格納されたメッセージrとメッセージiを加減乗算部341に入力し、(r+i)の値を持つメッセージrとしてYTに格納する(S508a)。
【0093】
補正部322は、下記の式を用い、0≦q<2を満たすよう、qとrの値を変更する。
【0094】
←q+i2
←r−in
ただし、iは小さな整数である。また、qの値を変更する必要がない場合、i=0が成り立ち、S508bの処理は不要である(S508b)。
【0095】
<入出力処理その2>
図5の入出力処理部302の剰余乗算の計算処理を示すフローチャートにおいて、S502、S504、S506、S510において、XNに定数1を設定した。しかし、XNに設定する数は定数1である必要性はなく、どのような値の整数もXNに設定できる。
【0096】
図7は、S502、S504、S506、S510において、定数2−1を用いた場合の入出力処理部302の剰余乗算の計算処理を示すフローチャートである。以下では、図7が示すフローチャートについて、図5が示すフローチャートと異なる点のみ、説明する。
【0097】
入力部321は、メッセージnをXAに、定数2−1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq2をXAに、剰余を指すメッセージr2をYRに格納するよう指示する(S502c)。
【0098】
補正部322は、XAに格納されたメッセージq2を加減乗算部341に入力し、(−q)の値を持つメッセージqをXAに格納する。また、補正部322は、YRに格納されたメッセージr2とXAに格納されたメッセージqを加減乗算部341に入力し、(r−q)の値を持つメッセージrをYRに格納する(S502d)。
【0099】
入力部321は、メッセージaをXAに、メッセージbをXBに、定数2−1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq3をXAに、剰余を指すメッセージr3をYTに格納するよう指示する(S504c)。
【0100】
補正部322は、XAに格納されたメッセージqを加減乗算部341に入力し、(−q)の値を持つメッセージqをXAに格納する。また、補正部322は、YTに格納されたメッセージrとXAに格納されたメッセージqを加減乗算部341に入力し、(r−q)の値を持つメッセージrをYTに格納する(S504d)。
【0101】
入力部321は、加減乗算部341に対してメッセージを交換し、(a+a)の値を持つメッセージ(a+a)をXAに、(b+b)の値を持つメッセージ(b+b)をXBに、定数2−1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq4をXAに、剰余を指すメッセージr4をYTに格納するよう指示する(S506c)。
【0102】
補正部322は、XAに格納されたメッセージqを加減乗算部341に入力し、(−q)の値を持つメッセージqをXAに格納する。また、補正部322は、YTに格納されたメッセージrとXAに格納されたメッセージqを加減乗算部341に入力し、(r−q)の値を持つメッセージrをYTに格納する(S506d)。
【0103】
入力部321は、メッセージnをXAに、定数2−1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq6をXAに、剰余を指すメッセージr6をYTに格納するよう指示する(S510c)。
【0104】
補正部322は、XAに格納されたメッセージqを加減乗算部341に入力し、(−q)の値を持つメッセージqをXAに格納する。また、補正部322は、YTに格納されたメッセージrとXAに格納されたメッセージqを加減乗算部341に入力し、(r−q)の値を持つメッセージrをYTに格納する(S510d)。
【0105】
<入出力処理その3>
図5の入出力処理部302の剰余乗算の計算処理を示すフローチャートにおいて、S501、S508において、XNに定数nを設定した。図8は、S501、S508において、定数2−nを用いた場合の入出力処理部302の剰余乗算の計算処理を示すフローチャートである。以下では、図8が示すフローチャートについて、図5が示すフローチャートと異なる点のみを説明する。
【0106】
入力部321は、メッセージaをXAに、メッセージbをXBに、2−nの値を持つメッセージをXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージqをXBに、剰余rを指すメッセージrをYTに格納するよう指示する(S501e)。
【0107】
入力部321は、n+1の値を持つメッセージをXAに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq2をXAに、剰余を指すメッセージr2をYRに格納するよう指示する(S502e)。
【0108】
入力部321は、XAに格納されたメッセージq2とYTに格納されたメッセージrを加減乗算部341に入力し、(r+q)の値を持つメッセージtをYQに格納する(S503e)。
【0109】
蓄積部324は、YQに格納されたメッセージtとXAに格納されたメッセージqを加減乗算部341に入力し、(t−q)の値を持つメッセージtをYQに格納する。さらに、蓄積部324は、YRに格納されたメッセージr2とYTに格納されたメッセージrを加減乗算部341に入力し、(−r+r)の値を持つメッセージrをYRに格納する(S505e)。
【0110】
入力部321は、定数1をXBに、(2−n)の値を持つメッセージをXNに格納する。出力指示部323は、剰余処理部303から商を指すメッセージq5をXBに、剰余を指すメッセージr5をYTに格納するよう指示する(S508e)。
【0111】
入力部321は、(n+1)の値を持つメッセージをXAに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq6をXAに、剰余を指すメッセージr6をYTに格納するよう指示する(S510e)。
【0112】
入力部321は、YTに格納されたメッセージrとYRに格納されたメッセージrを加減乗算部341に入力し、(r+r)の値を持つメッセージrをYRに格納する。さらに、入力部321は、XAに格納されたメッセージqとYQに格納されたメッセージqを加減乗算部341に入力し、(q+q)の値を持つメッセージqをYQに格納する(S511e)。
【0113】
<平方算への展開>
なお、入出力処理部302の剰余乗算に関する処理は、メッセージAとメッセージBの値が等しい場合、即ち平方算の場合も含む。また、上記の2wビットの剰余乗算を繰り返し実行すると、2wビットのべき乗の剰余乗算が実現できる。
【0114】
<剰余処理部の処理>
次に、図9により、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部303の処理について説明する。図9は本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートであり、剰余処理部303におけるモンゴメリ乗算の商qと剰余rの計算処理について示している。
【0115】
乗数変更部335は、剰余乗算を実行する前に、下記の式を用い、XAに設定されたメッセージx、XBに設定されたメッセージy、XNに設定されたメッセージzが0≦x、y<zを満たすよう、メッセージxとメッセージyの値を変更する(S1001)。
【0116】
x←x−iz
y←y−jz
ただし、iとjは整数である。また、xとyの値を変更する必要がない場合、i=j=0が成り立ち、S1001と後述するS1014の処理は不要である。
【0117】
剰余乗算器取扱部331は、入力部321が、XA、XB、XNに設定したメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。例えば、XAにメッセージxを、XBにメッセージyを、XNにメッセージzを設定した場合、以下の式で定義されるモンゴメリ乗算の剰余rをXRに出力する。
【0118】
r←xy2−wmod z
ただし、xは乗数、yは被乗数、zは法である。次に、移動部333は、出力指示部323が指示したメッセージの格納領域へ、メッセージrを移動する(S1002)。
【0119】
法変更部334は、XNに設定したメッセージの値を変更する。例えば、法変更部334は、条件判定部343を用い、XNに設定したメッセージzの値が条件式(z<2w−1+2w−2)を満たすかを判定する(S1003)。条件を満たせばS1004へ、満たさなければS1005へと進む。法変更部334は、加減乗算部341を用い、XNに設定したメッセージzの値を変更する。z+2w−2の値を持つメッセージz’を作成する(S1004)、またはz−2w−2の値を持つメッセージz’を作成する(S1005)。
【0120】
剰余乗算器取扱部331は、XA、XB、XNに設定されたメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。XAにメッセージxを、XBにメッセージyを、XNにメッセージz’を設定した場合、以下の式で定義されるモンゴメリ乗算の剰余r’をXRに出力する。
【0121】
r’←xy2−wmod z’
ただし、xは乗数、yは被乗数、z’は法である。(S1006)。
【0122】
商演算部332は、条件判定部343を用い、XNに設定したメッセージzの値から判別式を用い、メッセージβの値を設定する。条件式(z<2w−1+2w−2)を満たせばS1008へ、満たさなければS1009へと進む(S1007)。商演算部332は、メッセージβの値を1(S1008)または(−1)とする(S1009)。
【0123】
商演算部332は、加減乗算部341と剰余計算部342を用い、以下の式を満たすメッセージαを計算する(S1010)。
【0124】
α← xyz2−4β(r−r’)z3 (mod 2)
商演算部332は、条件判定部343を用い、メッセージαの値が条件式(α>2)を満たすかを判定する。条件を満たせばS1012へ、満たさなければS1013へと進む(S1011)。
【0125】
商演算部332は、加減乗算部341を用い、α−2の値をもつメッセージαを作成する(S1012)。
【0126】
商演算部332は、加減乗算部341と剰余計算部342を用い、以下の式を満たすメッセージqを計算し、出力指示部323が指示したメッセージの格納領域へ、メッセージqを出力する(S1013)。
【0127】
q← αz’+4β(r−r’)
このとき、メッセージqは、モンゴメリ乗算の商qであり、以下の式を満たす。
【0128】
xy=qz+r2
ただし、xは乗数、yは被乗数、rはモンゴメリ乗算の剰余、zは法である。
【0129】
乗数変更部335は、加減乗算部341を用い、以下の式を満たすメッセージqを計算し、メッセージqが格納されていた領域に、再びメッセージqを格納する(S1014)。
【0130】
q←q+ix+jy−ijz
なお、剰余乗算器113のビット長の制限によっては、図9に示すフローチャートを簡略化して、モンゴメリ乗算の商qと剰余rを計算してもよい。
【0131】
<乗算器(剰余乗算器ではなく)を用いる場合>
剰余乗算器113が乗算を実行できる場合、または剰余乗算器113以外に、演算装置として乗算を実行する乗算器が実装されている場合、剰余処理部303は、乗算を利用し、モンゴメリ乗算の商qとモンゴメリ乗算の剰余rを求めても良い。この計算方法は、XNに定数を設定する、S502、S504、S506、S510などで利用できる。剰余乗算器取扱部331は、乗数xと被乗数y用いて、以下の式を満たす積cを計算する。
【0132】
c←xy
剰余処理部303は、cの下位wビットをモンゴメリ乗算の商、それ以外の上位ビットをモンゴメリ乗算の剰余とみなす。
【0133】
<入出力処理部と剰余処理部の構成>
入出力処理部302と剰余処理部303は、メッセージの交換に記憶装置123を用いる。
【0134】
次に、図10および図11により、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムの記憶装置123へのメッセージの格納順序について説明する。図10および図11は、本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【0135】
図10および図11は、行と列をもつ表から構成される。最も左の列は、図5で示したフローチャートの各ステップと対応を取り、他の列は、メッセージを格納する記憶領域であるXR、XA、XB、XN、YQ、YR、YTを意味する。各行には記憶領域内に格納されるメッセージを表し、「任意」は、格納されているメッセージはどのような値でもかまわない。
【0136】
また、上行から下行に順々に処理が実行され、「―」は以前の処理にて格納されたメッセージを格納し続ける状態を指す。また、y、zは定数を表すメッセージであり、例えば図5が示すフローチャートでは、y=1、z=1であり、図7が示すフローチャートでは、y=1、z=2−1である。
【0137】
S501の第1行目では、XAにメッセージa、XBにメッセージb、XNにメッセージnが格納される。他の記憶領域であるXR、YQ、YR、YTに格納するメッセージは任意でよい。S501の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。他の記憶領域に格納するメッセージに変更はない。
【0138】
S501の第3行目では、YTにもメッセージrが格納される。S501の第4行目では、メッセージnの値を変更したメッセージn’がXNに格納される。S501の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S501の第6行目では、XBにモンゴメリ乗算の商であるメッセージqが格納される。
【0139】
S502の第1行目では、XAにメッセージn、XNにメッセージzが格納される。他の記憶領域であるXR、XB、YQ、YR、YTに格納するメッセージは任意でよい。S502の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。他の記憶領域に格納するメッセージに変更はない。
【0140】
S502の第3行目では、YRにもメッセージrが格納される。S502の第4行目では、メッセージzの値を変更したメッセージz’がXNに格納される。S502の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S502の第6行目では、XAにモンゴメリ乗算の商であるメッセージqが格納される。
【0141】
S503では、(r−q)の値をもつメッセージtがYQに格納される。
【0142】
S504の第1行目では、XAにメッセージa、XBにメッセージb、XNにメッセージzが格納される。S504の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。S504の第3行目では、YTにもメッセージrが格納される。
【0143】
S504の第4行目では、メッセージzの値を変更したメッセージz’がXNに格納される。S504の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S504の第6行目では、XAにモンゴメリ乗算の商であるメッセージqが格納される。
【0144】
S505の第1行目では、(t−q)の値をもつメッセージtがYQに格納される。S505の第2行目では、(r+r)の値をもつメッセージrがYRに格納される。
【0145】
S506の第1行目では、(a+a)の値を持つメッセージがXAに、(b+b)の値を持つメッセージがXBに、メッセージzがXNに格納される。S506の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。
【0146】
S506の第3行目では、YTにもメッセージrが格納される。S506の第4行目では、メッセージzの値を変更したメッセージz’がXNに格納される。S506の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S506の第6行目では、XAにモンゴメリ乗算の商であるメッセージqが格納される。
【0147】
S507の第1行目では、(t+q)の値をもつメッセージtがXBに格納される。S507の第2行目では、(q+r)の値をもつメッセージtがYTに格納される。S507の第3行目では、(‐t+t−r)の値を持つメッセージqがYQに格納される。
【0148】
S508の第1行目では、XAにメッセージy、XNにメッセージnが格納される。S508の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。S508の第3行目では、YTにもメッセージrが格納される。S508の第4行目では、メッセージnの値を変更したメッセージn’がXNに格納される。S508の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S508の第6行目では、XBにモンゴメリ乗算の商であるメッセージqが格納される。
【0149】
S509では、(q+r)の値をもつメッセージqがYQに格納される。
【0150】
S510の第1行目では、XAにメッセージn、XNにメッセージzが格納される。S510の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。S510の第3行目では、YTにもメッセージrが格納される。
【0151】
S510の第4行目では、メッセージzの値を変更したメッセージz’がXNに格納される。S510の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S510の第6行目では、XAにモンゴメリ乗算の商であるメッセージqが格納される。
【0152】
S511の第1行目では、(q−q)の値をもつメッセージqがYQに格納される。S511の第2行目では、(r‐r)の値をもつメッセージrがYRに格納される。
【0153】
<応用例>
実施の形態1では、剰余乗算器113がモンゴメリ乗算を実装し、2倍剰余乗算部116が、2wビットからなるメッセージを対象に、モンゴメリ乗算に基づく剰余乗算を計算する計算方法について説明した。実施の形態1に基づくモンゴメリ乗算を繰り返し用いる、または対象の2wビットからなるメッセージの値を変更すると、古典的な剰余乗算と同じ値をもつ剰余乗算の剰余が得られる。
【0154】
以上のように実施の形態1では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【0155】
(実施の形態2)
<実施の形態2の概要>
本実施の形態では、剰余乗算器113が古典的な剰余乗算を実装する場合、2倍剰余乗算部116が、2wビットからなるメッセージを対象に、古典的な剰余乗算に基づく剰余乗算を計算する第2の計算方法について説明する。
【0156】
<2倍剰余乗算部の処理の概要>
図12より、本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の2倍剰余乗算部116の処理について説明する。図12は本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の2倍剰余乗算部の処理を示すシーケンス図であり、2倍剰余乗算部116の機能ブロックである表現処理部301、入出力処理部302、剰余処理部303のメッセージの受け渡しの様子を示す。実施の形態2に係る剰余乗算処理装置を適用した通信システムの構成は実施の形態1と同様である。
【0157】
まず、表現処理部301へメッセージが入力される(S1101)。表現処理部301は、入力したメッセージを元に、古典的な剰余乗算の計算用に変換したメッセージ(以降、古典的な剰余乗算用のメッセージと呼ぶ)を作成し、入出力処理部302がアクセスできるメモリ領域へ出力する(S1102)。入出力処理部302は、メモリ領域から、古典的な剰余乗算用のメッセージを入力し、適当なメッセージ、または定数を選択し、剰余処理部303がアクセスできるメモリへ出力する。
【0158】
剰余処理部303は、メモリ領域から、古典的な剰余乗算用のメッセージおよび定数を用い、(式1)によって定義された古典的な剰余乗算の商と剰余を計算し、入出力処理部302がアクセスできるメモリ領域へ出力する。入出力処理部302、剰余処理部303は、上記の処理を複数回繰り返す(S1103、S1104)。入出力処理部302は、入力された複数個の古典的な剰余乗算用の商と剰余を合成したメッセージを、表現処理部301がアクセスできるメモリ領域へ出力する(S1151)。表現処理部301は、メモリ領域から、古典的な剰余乗算用の商と剰余を合成したメッセージを、データ処理部115へ出力する(S1152)。
【0159】
<表現処理部の処理>
本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の表現処理部301の行う分割処理と合成処理について説明する。
【0160】
まず、表現処理部301の行う分割処理について説明する。表現処理部301は、メッセージを古典的な剰余乗算の計算に適した形式である古典的な剰余乗算用のメッセージに変換する機能を有する。ただし、古典的な剰余乗算の計算に適した形式とは、2wビットの整数Xを上位側wビットの整数xと下位側wビットの整数xで表すように、変換した(式2)を満たす整数表現を指す。
【0161】
X=x+x …(式2)
ただし、0≦X<22wかつ0≦x、x<2である。
【0162】
まず、表現処理部301がもつ分割部311は2wビットのメッセージA、2wビットのメッセージB、2wビットのメッセージNを記憶装置123から読み込む(S1101)。次に、分割部311は、各メッセージを上位wビットと下位wビットに分け、(式2)を満たすよう、メッセージAからメッセージaとメッセージa、メッセージBからメッセージbとメッセージb、メッセージNからメッセージnとメッセージnを作成する。従って、以下の式が成り立つ。
【0163】
N=n+n
A=a+a
B=b+b
分割部311は、RAM131などの記憶装置123にメッセージnとメッセージn、メッセージa、メッセージa、メッセージb、メッセージbを出力する(S1102)。
【0164】
次に、表現処理部301の行う合成処理について説明する。表現処理部301内の合成部312は、入出力処理部302が格納したメッセージqsとメッセージrsを用い、(rs+qs)の値を保持するメッセージCを作成する機能を有する。
【0165】
まず、表現処理部301内の合成部312は、記憶装置123から、メッセージqとメッセージrを読み込む(S1151)。次に、(q+r)の値を持つメッセージCを作成する。従って、メッセージC、メッセージrs、メッセージqsには以下の式が成り立つ。
【0166】
C=rs+qs
合成部312は、共通部304における条件判定部343を用い、メッセージCが条件式0≦C<Nを満たすかを判定する。条件式を満たさない場合は、共通部304における剰余計算部342を用い、以下の式を満たすメッセージCを作成する。
【0167】
C=(rs+qs)mod N
ただし、0≦C<N<22wである。合成部312は、メッセージCを記憶装置123へ出力する(S1152)。
【0168】
なお、表現処理部301の分割部311は、複数の分割処理の手法を有する。例えば、分割部311は、剰余乗算器113あるいは剰余処理部303が処理できるメッセージのビット長に応じ、自由にメッセージNから作成するメッセージnとメッセージnを変更する。wビットのメッセージNの値をi倍し、iNの値を持つメッセージの下位wビットと上位側の残りのビットに分けて、次式を満たす、メッセージn’とメッセージn’を作成する。
【0169】
iN=n’2+n
<入出力処理>
次に、図13〜図15により、本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部302の処理について説明する。図13〜図15は本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【0170】
実施の形態1で用いた図5と同様、MUは、剰余処理部303を表し、剰余処理部303に入力するメッセージの組はMUの右辺の括弧内に、剰余処理部303から出力するメッセージの組は左辺の括弧内に表す。
【0171】
また、実施の形態1と同様に、入出力処理部302と剰余処理部303のメッセージの受け渡しには、記憶装置123またはネットワーク151を用いる。メッセージの格納領域として、RAM141におけるXA、XB、XN、XRと、他の記憶領域(例えばRAM131)におけるYQ、YR、YT(メッセージの格納用に領域を定義)を用いる。
【0172】
入力部321は、メッセージaをXAに、メッセージbをXBに、メッセージnをXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージqをXBに、剰余rを指すメッセージrをYTに格納するよう指示する(S1201)。
【0173】
入力部321は、メッセージnをXAに、定数2をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq2をXAに、剰余を指すメッセージr2をYRに格納するよう指示する(S1202)。
【0174】
入力部321は、XAに格納されたメッセージq2とYTに格納されたメッセージrを加減乗算部341に入力し、(r−q)の値を持つメッセージtをYQに格納する(S1203)。
【0175】
入力部321は、メッセージaをXAに、メッセージbをXBに、定数2をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq3をXAに、剰余を指すメッセージr3をYTに格納するよう指示する(S1204)。
【0176】
入力部321は、YQに格納されたメッセージtとXAに格納されたメッセージqを加減乗算部341に入力し、(t−q)の値を持つメッセージtをYQに格納する。さらに、入力部321は、YRに格納されたメッセージr2とYTに格納されたメッセージrを加減乗算部341に入力し、(r+r)の値を持つメッセージrをYRに格納する(S1205)。
【0177】
入力部321は、加減乗算部341に対してメッセージを交換し、(a+a)の値を持つメッセージ(a+a)をXAに、(b+b)の値を持つメッセージ(b+b)をXBに、定数2をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq4をXAに、剰余を指すメッセージr4をYTに格納するよう指示する(S1206)。
【0178】
入力部321は、YQに格納されたメッセージtとXAに格納されたメッセージqを加減乗算部341に入力し、(t+q)の値を持つメッセージtをXBに格納する。さらに、入力部321は、YTに格納されたメッセージrとXAに格納されたメッセージqを加減乗算部341に入力し、(r+q)の値を持つメッセージtをYTに格納する。さらに、入力部321は、XBに格納されたメッセージtとYTに格納されたメッセージtとYRに格納されたメッセージrを加減乗算部341に入力し、(−t+t−r)の値を持つメッセージqをYQに格納する(S1207)。
【0179】
入力部321は、定数1をXBに、メッセージnをXNに格納する。出力指示部323は、剰余処理部303から商を指すメッセージq5をXBに、剰余を指すメッセージr5をYTに格納するよう指示する(S1208)。
【0180】
入力部321は、YTに格納されたメッセージrとYQに格納されたメッセージqを加減乗算部341に入力し、(q+r)の値を持つメッセージqをYQに格納する(S1209)。
【0181】
入力部321は、メッセージnをXAに、定数2をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq6をXAに、剰余を指すメッセージr6をYTに格納するよう指示する(S1210)。
【0182】
入力部321は、XAに格納されたメッセージqとYQに格納されたメッセージqを加減乗算部341に入力し、(q−q)の値を持つメッセージqをYQに格納する。さらに、入力部321は、YTに格納されたメッセージrとYRに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージrをYRに格納する(S1211)。
【0183】
<入出力処理:法の変更>
図13の入出力処理部302の剰余乗算の計算処理を示すフローチャートにおいて、r、r、r、q、q、qを計算する際、XNにメッセージnまたは定数2を設定した。しかし、乗数と被乗数の値が法よりも大きくなる場合があるため、法の値を大きくするよう、他の値をもつメッセージを法として、設定しても良い。これには、予め、または必要時に、分割部311が表現処理部301の分割処理において、剰余乗算器113あるいは剰余処理部303が処理できるメッセージのビット長に応じ、wビットのメッセージNの値をi倍またはj倍し、iNまたはjNの値を持つメッセージの下位wビットと上位側の残りのビットに分けて、メッセージn’とメッセージn’、メッセージn’’とメッセージn’’を作成すればよい。
【0184】
iN=n’2+n
jN=n’’2+n’’
図14は、r、r、r、q、q、qの計算に、別の値のメッセージまたは定数を法として用いた場合の入出力処理部302の剰余乗算の計算処理を示すフローチャートである。以下では、図13が示すフローチャートと異なる点のみを説明する。
【0185】
入力部321は、メッセージaをXAに、メッセージbをXBに、メッセージn’をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージqをXBに、剰余rを指すメッセージrをYTに格納するよう指示する(S1201c)。
【0186】
入力部321は、メッセージn’をXAに、定数2をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq2をXAに、剰余を指すメッセージr2をYRに格納するよう指示する(S1202c)。
【0187】
入力部321は、加減乗算部341に対してメッセージを交換し、(a+a)の値を持つメッセージ(a+a)をXAに、(b+b)の値を持つメッセージ(b+b)をXBに、定数2w+1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq4をXAに、剰余を指すメッセージr4をYTに格納するよう指示する(S1206c)。
【0188】
入力部321は、XAに格納されたメッセージrとYTに格納されたメッセージqからメッセージr’、メッセージq’を計算し、それぞれXA、YTに格納する(S1206d)。
【0189】
入力部321は、定数2をXBに、メッセージn’’をXNに格納する。出力指示部323は、剰余処理部303から商を指すメッセージq5をXBに、剰余を指すメッセージr5をYTに格納するよう指示する(S1208c)。
【0190】
入力部321は、メッセージn’’をXAに、定数2をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq6をXAに、剰余を指すメッセージr6をYTに格納するよう指示する(S1210c)。
【0191】
<補正処理>
補正部322は、剰余処理部303が適切に処理できるよう、メッセージの値を変更する機能を有する。例として、剰余処理部303がメッセージxに対し、0≦x<2の値域を条件とする場合の、入出力処理部302の剰余乗算の計算処理を示すフローチャートを図15に示す。図15は、図13で示したフローチャートの各ステップに加え、補正部322の補正処理が加わる。
【0192】
以降では、図15の補正部322の補正処理に関連するステップのみを説明する。
【0193】
補正部322は、下記の式を用い、0≦a+a、b+b<2を満たすよう、値を変更する。
【0194】
←a+a+i2
←b+b+j2
ただし、i、jは小さな整数である。また、a+a、b+bの値を変更する必要がない場合、i=0、j=0が成り立つ(S1205a)。
【0195】
入力部321は、メッセージtをXAに、メッセージtをXBに、定数2をXNに格納する。出力指示部323は、剰余処理部303から商を指すメッセージqをXAに、剰余を指すメッセージrをYTに格納するよう指示する(S1206a)。ただし、S1205aでi=0かつj=0が成り立つ場合、S1206aの代わりにS1206を実行しても良い。
【0196】
補正部322は、YTに格納されたメッセージrとXAに格納されたメッセージtとXBに格納されたメッセージtを加減乗算部341に入力し、(r+it+jt+ij2)の値を持つメッセージqとしてYTに格納する(S1206b)。
【0197】
補正部322は、下記の式を用い、0≦t<2を満たすよう、tの値を変更する。
【0198】
←t+i2
ただし、iは小さな整数である。また、tの値を変更する必要がない場合、i=0が成り立ち、S1207aの処理は不要である(S1207a)。
【0199】
補正部322は、YTに格納されたメッセージrとi2の値を持つメッセージを加減乗算部341に入力し、q+iの値を持つメッセージqとしてYTに格納する(S1208a)。
【0200】
補正部322は、下記の式を用い、0≦q<2を満たすよう、qの値を変更する。
【0201】
←q+i2
ただし、iは小さな整数である。また、qの値を変更する必要がない場合、i=0が成り立ち、S1208aの処理は不要である(S1209a)。
【0202】
補正部322は、XAに格納されたメッセージqとinの値を持つメッセージを加減乗算部341に入力し、q+inの値を持つメッセージqとしてXAに格納する(S1210a)。
【0203】
<剰余処理部の処理>
次に、図16により、本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部303の処理について説明する。図16は本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【0204】
乗数変更部335は、剰余乗算を実行する前に、下記の式を用い、XAに設定されたメッセージx、XBに設定されたメッセージy、XNに設定されたメッセージzが0≦x、y<zを満たすよう、メッセージxとメッセージyの値を変更する(S1601)。
【0205】
x←x−iz
y←y−jz
ただし、iとjは整数である。また、xとyの値を変更する必要がない場合、i=j=0が成り立ち、S1601と後述するS1606の処理は不要である。
【0206】
剰余乗算器取扱部331は、入出力処理部302が、XA、XB、XNに設定したメッセージに基づき、古典的な剰余乗算による剰余乗算の剰余を計算する。例えば、XAにメッセージxを、XBにメッセージyを、XNにメッセージzを設定した場合、古典的な剰余乗算の剰余rは以下の式で定義される。
【0207】
r←xy mod z
ただし、xは乗数、yは被乗数、zは法である。
【0208】
次に、移動部333は、出力指示部323が指示したメッセージの格納領域へ、メッセージrを移動する(S1602)。
【0209】
法変更部334は、XNに設定したメッセージの値を変更する。例えば、XNにメッセージzを設定する場合、以下の式で定義されるメッセージz’をXNに出力する。(S1603)。
【0210】
z’←z+1
ただし、加算に代えて減算により、即ち以下の式に従い、メッセージz’を計算しても良い。
【0211】
z’←z−1
剰余乗算器取扱部331は、XA、XB、XNに設定されたメッセージに基づき、古典的な剰余乗算による剰余乗算の剰余を計算する。XAにメッセージxを、XBにメッセージyを、XNにメッセージz’を設定した場合、以下の式で定義される古典的な剰余乗算の剰余r’をXRに出力する。
【0212】
r’←xy mod z’
ただし、xは乗数、yは被乗数、z’は法である。(S1604)。
【0213】
商演算部332は、以下の式を満たす古典的な剰余乗算の商qを計算し、出力指示部323が指示したメッセージの格納領域へ、古典的な剰余乗算の商qを出力する。
【0214】
xy=qz+r
ただし、xは乗数、yは被乗数、rは古典的な剰余乗算の剰余、zは法である。
【0215】
商演算部332は、加減乗算部341を用い、(r−r’)の値を持つメッセージqを作成する(S1605)。
【0216】
商演算部332は、条件判定部343を用い、メッセージqの値が負であるか(q<0を満たすか)判定する。メッセージqの値が負であればS1607へ進み、非負であればS1608へと進む(S1606)。
【0217】
商演算部332は、加減乗算部341を用い、(q+z+1)の値を持つメッセージqを作成する(S1607)。
【0218】
乗数変更部335は、下記の式に従い、メッセージqの値を変更する(S1608)。
【0219】
q←q+jx+iy−ijz
<乗算器を利用できる場合>
なお、剰余処理部303が、剰余乗算器113以外に、乗算器を利用できる場合、この乗算器を利用して、商qと剰余rを求めても良い。この計算方法は、XNに定数を設定する、S1202、S1204、S1206、S1210などで利用できる。
【0220】
補正部322の働きは、剰余乗算器113を利用する計算方法と同様である。剰余乗算器取扱部331は、乗数xと被乗数y用いて、以下の式を満たす積cを計算し、下位wビットを剰余とする。
【0221】
xy=c
次に、商演算部332は、残りの上位側のビットを商とみなす。
【0222】
<入出力処理部と剰余処理部の構成>
入出力処理部302と剰余処理部303は、メッセージの交換に記憶装置123を用いる。実施の形態1では、図10と図11を用い、記憶装置123へのメッセージの格納順序を示した。実施の形態2における、記憶装置123へのメッセージの格納順序は、実施の形態1と同様であり、各処理の対応関係が示せる。即ち、実施の形態2におけるS1201は、実施の形態1における、図10が示すS501に対応する。同様に、S1202はS502、S1203はS503、S1204はS504、S1205はS505、S1206はS506、S1207はS507、S1208はS508、S1209はS509、S1210はS510、S1211はS511に対応する。また、定数を表すメッセージyとメッセージzは、y=1、z=2である。
【0223】
<応用例:XAに剰余を出力する剰余乗算器>
実施の形態1、実施の形態2では、XAに入力されたメッセージを乗数、XBに入力されたメッセージを被乗数、XNに入力されたメッセージを法とみなし、演算結果(剰余)はXRに出力する剰余乗算器113を仮定した。この仮定とは異なり、剰余乗算器113が演算結果をXRではなく、XAに出力(即ち、XRとXAは同一のメッセージの格納領域を指す)する場合も、実施の形態1または実施の形態2と同様に、XA、XB、XN、YQ、YR、YTのみの記憶領域を用いて、本技術を適用できる。
【0224】
以上のように実施の形態2では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【0225】
(実施の形態3)
<剰余乗算処理装置を適用した通信システムの全体構成>
図17により、本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムの全体構成について説明する。なお、図17に示す通信システムの全体構成は、後述する実施の形態4においても基本的に共通である。図17は本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【0226】
図17において、図1における構成図との違い(即ち、実施の形態1、実施の形態2との違い)は、記憶装置123と剰余乗算器113の構成にある。
【0227】
図1の構成図では、剰余乗算器113からメッセージの読み出し、書き込み等ができる記憶装置123はRAM141のみであったが、図17の構成図では、全ての記憶装置123が剰余乗算器113からアクセスできる(従って、図1では区別されていたRAM131とRAM141の差分が無くなったため、図17ではRAMはRAM131に統一した)。
【0228】
本実施の形態における剰余乗算器113は、剰余乗算を実行する計算装置またはプログラムであり、記憶装置123の各メモリ上のメッセージの読み出し、または書き込み処理ができる。剰余乗算器113は、記憶装置123に格納されたメッセージの記憶領域によらず、自由に記憶装置123内のメッセージを剰余乗算の乗数、被乗数、法に設定でき、実装する剰余乗算の種類(モンゴメリ乗算または古典的な剰余乗算)に基づき、演算結果(剰余)を記憶装置123のいずれの記憶領域にも出力できる。
【0229】
本実施の形態では、便宜上、XN、XQ、XR、XT、YA0、YA1、YB0、YB1、YN0、YN1を、メッセージを格納する記憶領域とした。なお、YQ、YR、YTは、図17の揮発性メモリ131に配置してもよいし、他のメモリ領域に配置しても良い。
【0230】
また、剰余乗算器113が演算中に利用する記憶領域は上記の記憶装置123には含まない。剰余乗算器113が計算する剰余乗算は、最大w+h(wは正の整数、hは0以上w未満の整数)ビットのメッセージを対象とする。
【0231】
<実施の形態3の概要>
本実施の形態では、剰余乗算器113がモンゴメリ乗算を実装する場合、2倍剰余乗算部116が、2wビットからなるメッセージを対象に、モンゴメリ乗算に基づく剰余乗算を計算する第3の計算方法について説明する。ただし、wは正の整数とする。
【0232】
<2倍剰余乗算部の処理の概要>
本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の2倍剰余乗算部116の処理は、実施の形態1(図4のシーケンス図を参照)と同様である。
【0233】
<表現処理部の処理>
本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の表現処理部301の行う分割処理と合成処理について説明する。
【0234】
まず、表現処理部301の行う分割処理について説明する。表現処理部301は、メッセージをモンゴメリ乗算の計算に適した形式であるモンゴメリ乗算用のメッセージに変換する機能を有する。ただし、モンゴメリ乗算の計算に適した形式とは、2wビットの整数Xを上位側wビットの整数xと下位側wビットの整数xで表すように、変換した(式1)を満たす整数表現を指す。
【0235】
X=x+x …(式1)
ただし、0≦X<22wかつ0≦x、x<2である。
【0236】
まず、表現処理部301内の分割部311は記憶装置123から2wビットのメッセージA、2wビットのメッセージB、2wビットのメッセージNを読み込む(S401)。次に、分割部311は、各メッセージを上位wビットと下位wビットに分け、(式1)を満たすよう、メッセージAからメッセージaとメッセージa、メッセージBからメッセージbとメッセージb、メッセージNからメッセージnとメッセージnを作成する。従って、以下の式が成り立つ。
【0237】
N=n+n
A=a+a
B=b+b
分割部311は、メモリ領域のYN1にメッセージnを、YN0にメッセージnを、YA1にメッセージa、YA0にメッセージa、YB1にメッセージb、YB0にメッセージbを出力する(S402)。
【0238】
次に、表現処理部301の行う合成処理について説明する。表現処理部301内の合成部312は、入出力処理部302がメモリ領域のXQに格納したメッセージqsとXRに格納したメッセージrsを用い、(rs+qs)の値を保持するメッセージCを作成する機能を有する。
【0239】
まず、表現処理部301内の合成部312は、メッセージqとメッセージrを記憶装置123から読み込む(S451)。次に、メッセージqとメッセージrを用い、(r+q)の値を保持するメッセージCを作成する。従って、メッセージC、メッセージrs、メッセージqsには以下の式が成り立つ。
【0240】
C=rs+qs
合成部312は、共通部304における条件判定部343を用い、メッセージCが条件式0≦C<Nを満たすかを判定する。条件式を満たさない場合は、共通部304における剰余計算部342を用い、以下の式を満たすメッセージCを作成する。
【0241】
C=(rs+qs)mod N
ただし、0≦C<N<22wである。
【0242】
合成部312は、メッセージCを記憶装置123へ出力する(S452)。
【0243】
<入出力処理部の処理>
次に、図18により、本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部302の処理について説明する。図18は本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【0244】
MUは、入出力処理部302と連携する、剰余処理部303を表し、MUの入力変数は右辺の括弧内に、出力変数は左辺に表す。入出力処理部302は、各メッセージを格納するメモリ領域である、YA0、YA1、YB0、YB1、YN0、YN1、XQ、XR、XN、XTを用いる。
【0245】
入出力処理部302は、入力したモンゴメリ乗算用のメッセージを用い、剰余処理部303へモンゴメリ乗算用のメッセージを出力する機能を有する。また、剰余処理部303へ、出力するメッセージを適切にメモリ領域に格納し、2wビットのモンゴメリ乗算に基づく剰余乗算の剰余を計算する機能を有する。
【0246】
<入出力処理>
入力部321は、メッセージaを格納するYA1を乗数、メッセージbを格納するYB1を被乗数、メッセージnを格納するYN1を法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXRに、剰余rを指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(a=q+r)で表される(S1801)。
【0247】
入力部321は、メッセージnを格納するYN0を乗数、メッセージqを格納するXRを被乗数、定数1をXNに格納後、XNを法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージq2をXRに、剰余を指すメッセージr2をXQに出力するよう指示する。各メッセージの関係は、式(q=q+r)で表される(S1802)。
【0248】
蓄積部324は、XRに格納されたメッセージq2とXTに格納されたメッセージrを加減乗算部341に入力し、(r−q)の値を持つメッセージ(r−q)をXRに格納する(S1803)。
【0249】
入力部321は、定数1を格納後にXTを乗数、メッセージ(r−q)を格納するXRを被乗数、メッセージnを格納するYN1を法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXRに、剰余を指すメッセージrをXNに出力するよう指示する。各メッセージの関係は、式(r−q=q+r)で表される(S1804)。
【0250】
蓄積部324は、XNに格納されたメッセージrとXQに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージqsをXQに格納する(S1805)。
【0251】
入力部321は、メッセージaを格納するYA1を乗数、メッセージbを格納するYB0を被乗数、定数1を格納後、XNを法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXNに、剰余を指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(a=q+r)で表される(S1806)。
【0252】
蓄積部324は、XRに格納されたメッセージqsとXTに格納されたメッセージr4を加減乗算部341に入力し、(qs+r)の値を持つメッセージqsをXQに格納する。蓄積部324は、XNに格納されたメッセージqとXRに格納されたメッセージqを加減乗算部341に入力し、(q+q)の値を持つメッセージrsをXRに格納する(S1807)。
【0253】
入力部321は、メッセージaを格納するYA0を乗数、メッセージbを格納するYB1を被乗数、メッセージnを格納すYN1を法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXNに、剰余を指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(a=q+r)で表される(S1808)。
【0254】
蓄積部324は、XQに格納されたメッセージqsとXTに格納されたメッセージrを加減乗算部341に入力し、(qs+r)の値を持つメッセージqsをXQに格納する。蓄積部324は、XNに格納されたメッセージqとXRに格納されたメッセージrsを加減乗算部341に入力し、(rs+q)の値を持つメッセージrsをXRに格納する(S1809)。
【0255】
入力部321は、メッセージnを格納するYN0を乗数、メッセージrsを格納するXRを被乗数、定数1をXNに格納後、XNを法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXNに、剰余を指すメッセージrをXTに格納するよう指示する。各メッセージの関係は、式(ns=q+r)で表される(S1810)。
【0256】
蓄積部324は、XQに格納されたメッセージqsとXNに格納されたメッセージqを加減乗算部341に入力し、(qs−q)の値を持つメッセージqsをXQに格納する(S1811)。
【0257】
入力部321は、メッセージaを格納するYA0を乗数、メッセージbを格納するYB0を被乗数、定数1をXNに格納後、XNを法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXNに、剰余を指すメッセージrをXTに格納するよう指示する。各メッセージの関係は、式(a=q7+r7)で表される(S1812)。
【0258】
蓄積部324は、XQに格納されたメッセージqsとXNに格納されたメッセージqを加減乗算部341に入力し、(qs+q)の値を持つメッセージqsをXQに格納する。蓄積部324は、XRに格納されたメッセージrとXTに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージrsをXRに格納する(S1813)。
【0259】
<補正部の処理>
本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の補正部322の処理は、実施の形態1と同様である。
【0260】
<剰余処理部の処理>
本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の剰余処理部303の処理は、実施の形態1と同様である。
【0261】
<入出力処理部と剰余処理部の構成>
入出力処理部302と剰余処理部303は、メッセージの交換に記憶装置123を用いる。
【0262】
次に、図19により、本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムの記憶装置123へのメッセージの格納状態について説明する。図19は、本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【0263】
図19は、行と列をもつ表から構成される。最も左の列は、図18で示したフローチャートの各ステップであり、他の列は、メッセージを格納する記憶領域であるXN、XQ、XR、XT、YA1、YA0、YB1、YB0、YN1、YN0を意味する。各行には記憶領域内に格納されるメッセージを表し、「任意」は、格納されているメッセージはどのような値でもかまわない。また、左の行が示すステップを実行後の、メッセージを各列に示す。ただし、「―」は以前の処理にて格納されたメッセージを格納し続ける状態を指す。また、定数を表すメッセージzは、z=1である。
【0264】
以上のように実施の形態3では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【0265】
(実施の形態4)
<実施の形態4の概要>
実施の形態4では、剰余乗算器113が古典的な乗算を実装する場合、2倍剰余乗算部116が、2wビットからなるメッセージを対象に、古典的な剰余乗算に基づく剰余乗算を計算する第4の計算方法について説明する。実施の形態3との違いは、剰余乗算器113が実装する剰余乗算の種類である。
【0266】
<2倍剰余乗算部の処理の概要>
本発明の実施の形態4に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の2倍剰余乗算部116の処理は、実施の形態2(図12のシーケンス図を参照)と同様である。
【0267】
<表現処理部の処理>
本発明の実施の形態4に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の表現処理部301の行う分割処理と合成処理について説明する。
【0268】
まず、表現処理部301の行う分割処理について説明する。表現処理部301は、メッセージを古典的な剰余乗算の計算に適した形式である古典的な剰余乗算用のメッセージに変換する機能を有する。ただし、古典的な剰余乗算の計算に適した形式とは、2wビットの整数Xを上位側wビットの整数xと下位側wビットの整数xで表すように、変換した(式1)を満たす整数表現を指す。
【0269】
X=x+x …(式1)
ただし、0≦X<22wかつ0≦x、x<2である。
【0270】
まず、表現処理部301がもつ分割部311に2wビットのメッセージA、2wビットのメッセージB、2wビットのメッセージNを記憶装置123から読み込む(S1101)。次に、分割部311は、各メッセージを上位wビットと下位wビットに分け、(式1)を満たすよう、メッセージAからメッセージaとメッセージa、メッセージBからメッセージbとメッセージb、メッセージNからメッセージnとメッセージnを作成する。従って、以下の式が成り立つ。
【0271】
N=n+n
A=a+a
B=b+b
分割部311は、メモリ領域のYN1にメッセージnを、YN0にメッセージnを、YA1にメッセージa、YA0にメッセージa、YB1にメッセージb、YB0にメッセージbを出力する(S1102)。
【0272】
なお、表現処理部301の行う分割処理では、別の方法でメッセージを作成しても良い。例えば、分割部311は、剰余乗算器113あるいは剰余処理部303が処理できるメッセージのビット長に応じ、自由にメッセージNから作成するメッセージを変更する。wビットのメッセージNの値をi倍し、iNの値を持つメッセージの下位wビットと上位側の残りのビットに分けて、メッセージn’とメッセージn’を作成してもよい。
【0273】
iN=n’2+n
次に、表現処理部301の行う合成処理について説明する。表現処理部301内の合成部312は、入出力処理部302がメモリ領域XQに格納したメッセージqとXRに格納したメッセージrを用い、(r+q)の値を保持するメッセージCを作成する機能を有する。
【0274】
まず、表現処理部301内の合成部312は、記憶装置123から、メッセージqsとメッセージrsを読み込む(S1151)。次に、(q+r)の値を持つメッセージCを作成する。従って、メッセージC、メッセージrs、メッセージqsには以下の式が成り立つ。
【0275】
C=rs+qs
合成部312は、共通部304における条件判定部343を用い、メッセージCが条件式0≦C<Nを満たすかを判定する。条件式を満たさない場合は、共通部304における剰余計算部342を用い、以下の式を満たすメッセージCを作成する。
【0276】
C=(rs+qs)mod N
ただし、0≦C<N<22wである。
【0277】
合成部312は、メッセージCを記憶装置123へ出力する(S1152)。
【0278】
<入出力処理部の処理>
次に、図20により、本発明の実施の形態4に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部302の処理について説明する。図20は本発明の実施の形態4に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【0279】
MUは、入出力処理部302と連携する、剰余処理部303を表し、MUの入力変数は右辺の括弧内に、出力変数は左辺に表す。入出力処理部302は、各メッセージを格納するメモリ領域である、YA0、YA1、YB0、YB1、YN0、YN1、XQ、XR、XN、XTを用いる。
【0280】
入出力処理部302は、入力した古典的な剰余乗算用のメッセージを用い、剰余処理部303へ古典的な剰余乗算用のメッセージを出力する機能を有する。また、剰余処理部303へ、出力するメッセージを適切にメモリ領域に格納し、2wビットの古典的な剰余乗算に基づく剰余乗算の剰余を計算する機能を有する。
【0281】
<入出力処理>
入力部321は、メッセージaを格納するYA1を乗数、メッセージbを格納するYB1を被乗数、メッセージnを格納するYN1を法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXRに、剰余rを指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(a=q+r)で表される(S1901)。
【0282】
入力部321は、メッセージnを格納するYN0、メッセージqを格納するXR、定数2をXNに格納後、XNを法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージq2をXRに、剰余を指すメッセージr2をXQに出力するよう指示する。各メッセージの関係は、式(q=q+r)で表される(S1902)。
【0283】
蓄積部324は、XRに格納されたメッセージq2とXTに格納されたメッセージrを加減乗算部341に入力し、(r−q)の値を持つメッセージ(r−q)をXRに出力する(S1903)。
【0284】
入力部321は、定数2をXTに格納後、XTを乗数、メッセージ(r−q)を格納するXRを被乗数、メッセージnを格納するYN1を法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXRに、剰余を指すメッセージrをXNに出力するよう指示する。各メッセージの関係は、式(2(r−q)=q+r)で表される(S1904)。
【0285】
蓄積部324は、XNに格納されたメッセージrとXQに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージqsをXQに出力する(S1905)。
【0286】
入力部321は、メッセージaを格納するYA1を乗数、メッセージbを格納するYB0を被乗数、メッセージnを格納するXNを法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXNに、剰余を指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(a=q+r)で表される(S1906)。
【0287】
蓄積部324は、XRに格納されたメッセージqsとXTに格納されたメッセージr4を加減乗算部341に入力し、(qs+r)の値を持つメッセージqsをXQに出力する。蓄積部324は、XNに格納されたメッセージqとXRに格納されたメッセージqを加減乗算部341に入力し、(q+q)の値を持つメッセージrsをXRに出力する(S1907)。
【0288】
入力部321は、メッセージaを格納するYA0を乗数、メッセージbを格納するYB1を被乗数、メッセージnを格納するYN1を法として設定する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージqをXNに、剰余を指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(a=q+r)で表される(S1908)。
【0289】
蓄積部324は、XQに格納されたメッセージqsとXTに格納されたメッセージrを加減乗算部341に入力し、(qs+r)の値を持つメッセージqsをXQに出力する。蓄積部324は、XNに格納されたメッセージqとXRに格納されたメッセージrsを加減乗算部341に入力し、(rs+q)の値を持つメッセージrsをXRに出力する(S1909)。
【0290】
入力部321は、メッセージnを格納するYN0を乗数、メッセージrsを格納するXRを被乗数、定数2をXNに格納後、XNを法として設定する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージqをXNに、剰余を指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(ns=q+r)で表される(S1910)。
【0291】
蓄積部324は、XQに格納されたメッセージqsとXNに格納されたメッセージqを加減乗算部341に入力し、(qs−q)の値を持つメッセージqsをXQに出力する(S1911)。
【0292】
入力部321は、メッセージaを格納するYA0を乗数、メッセージbを格納するYB0を被乗数、定数2をXNに格納後、XNを法として設定する。出力指示部323は、剰余処理部303へ、商を指すメッセージqをXNに、剰余を指すメッセージrをXTに出力するよう指示する。各メッセージの関係は、式(a=q7+r7)で表される(S1912)。
【0293】
入力部321は、XQに格納されたメッセージqsとXNに格納されたメッセージqを加減乗算部341に入力し、(qs+q)の値を持つメッセージqsをXQに出力する。入力部321は、XRに格納されたメッセージrとXTに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージrsをXRに出力する(S1913)。
【0294】
<補正部の処理>
本発明の実施の形態4に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の補正部322の処理は、実施の形態2と同様である。
【0295】
<剰余処理部の処理>
本発明の実施の形態4に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の剰余処理部303の処理は、実施の形態2と同様である。
【0296】
<入出力処理部と剰余処理部の構成>
入出力処理部302と剰余処理部303は、メッセージの交換に記憶装置123を用いる。実施の形態3では、図19を用い、記憶装置123へのメッセージの格納状態を示した。実施の形態4における、記憶装置123へのメッセージの格納順序は、実施の形態3と同様であり、各処理の対応関係が示せる。即ち、実施の形態3におけるS1801は、実施の形態4におけるS1901に対応する。同様に、S1802はS1902、S1803はS1903、S1804はS1904、S1805はS1905、S1806はS1906、S1807はS1907、S1808はS1908、S1809はS1909、S1810はS1910、S1811はS1911、S1812はS1912、S1813はS1913に対応する。また、定数を表すメッセージzは、z=2である。
【0297】
<応用例>
実施の形態3、実施の形態4で述べた技術は、剰余乗算器113が記憶装置123における全てのメモリへのアクセスができることを仮定した。この仮定とは異なり、剰余乗算器113がいくつかのメモリへアクセスできない場合も、実施の形態3または実施の形態4と同様に、YA0、YA1、YB0、YB1、YN0、YN1、XQ、XR、XN、XTのみの記憶領域を用いて、本技術を適用できる。
【0298】
以上のように実施の形態4では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【0299】
(実施の形態5)
<実施の形態5の概要>
実施の形態1〜4で説明した技術によれば、剰余乗算器113がモンゴメリ乗算を実装する場合には、剰余乗算器113の2倍のビット長のモンゴメリ乗算の計算を、剰余乗算器113が古典的な剰余乗算を実装する場合は、剰余乗算器113の2倍のビット長の古典的な剰余乗算を計算が実現できる。実施の形態5では、本技術により、剰余乗算器113の種類とは異なる、剰余乗算器113のビット長の2倍の剰余乗算の実現方法を示す。
【0300】
モンゴメリ乗算を応用した、高速な剰余乗算が2分剰余乗算として知られている。この剰余乗算では、以下の式によって、剰余Rを求める。
【0301】
R=XY(αM)(−1)mod N
ここで、XとYは2nビット以下のメッセージ、Mはモンゴメリ定数であり、αはαwが整数かつ条件式(0<α<1)を満たすような小数である。例えば、wが偶数とのとき、αの値として0.5が取れる。
【0302】
この2分剰余乗算は、モンゴメリ定数の値を変更したモンゴメリ乗算とみなせる。本実施の形態5では、モンゴメリ乗算を剰余乗算器113が実装する場合に、αを0.5とする、剰余乗算器113の2倍のビット長のモンゴメリ乗算(2分剰余乗算)の実現方法を示す。
【0303】
<2倍剰余乗算部の処理の概要>
図21より、本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の2倍剰余乗算部116の処理について説明する。図21は本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の2倍剰余乗算部の処理を示すシーケンス図であり、2倍剰余乗算部116の機能ブロックである表現処理部301、入出力処理部302、剰余処理部303のメッセージの受け渡しの様子を示している。実施の形態5に係る剰余乗算処理装置を適用した通信システムの構成は実施の形態1と同様である。
【0304】
まず、表現処理部301へメッセージが入力される(S2101)。表現処理部301は、入力したメッセージから、剰余乗算器113が実装するモンゴメリ乗算に適するよう、モンゴメリ乗算の計算用に変換したメッセージ(以降、モンゴメリ乗算用のメッセージと呼ぶ)を作成し、入出力処理部302へ出力する(S2102)。
【0305】
入出力処理部302は、適当なメッセージまたは定数を選択し(詳細な処理内容は後述)、剰余処理部303へ出力する(S2103)。剰余処理部303は、モンゴメリ乗算の剰余を計算し、入出力処理部302へ出力する(S2104)。
【0306】
入出力処理部302は、適当なメッセージまたは定数を選択し(詳細な処理内容は後述)、剰余処理部303へ出力する(S2105)。剰余処理部303は、古典的な剰余乗算の商と剰余を計算し、入出力処理部302へ出力する(S2106)。入出力処理部302は、適当なメッセージまたは定数を選択し(詳細な処理内容は後述)、剰余処理部303へ出力する(S2107)。
【0307】
剰余処理部303は、モンゴメリ乗算の商と剰余を計算し、入出力処理部302へ出力する(S2108)。以降、入出力処理部302と剰余処理部303は、上記のメッセージの交換処理を複数回繰り返し、入出力処理部302は、複数個の古典的な剰余乗算の商と剰余と、モンゴメリ乗算用の商と剰余を合成したメッセージを合成したメッセージを、表現処理部301へ出力する(S2151)。
【0308】
表現処理部301は、合成したメッセージをデータ処理部115へ出力する(S2152)。なお、表現処理部301、入出力処理部302、剰余処理部303のメッセージの受け渡しには、記憶装置123へのメッセージの書き込みと読み出しを用い、メッセージの受け渡しを実施する。ただし、ネットワーク151を用い、メッセージの受け渡しを実施しても良い。
【0309】
<表現処理部の処理の概要>
本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の表現処理部301の処理は、実施の形態1と同様である。
【0310】
ただし、実施の形態5で示す手法では、剰余乗算の法であるメッセージNを分割したメッセージnとメッセージnの双方を法として用いる。従って、モンゴメリ乗算の条件である奇数の法を作成するよう、次式に基づき、メッセージnの代わりに、(n+1)の値を持つメッセージn’を作成し、剰余乗算の法として用いても良い。この変換は、以下の式に基づいており、
N=(n+1)2−(2−n
=n+n
(n+1)の値を持つメッセージn’を用いる場合、メッセージnの代わりに−(2−n)の値を持つメッセージn’を用いる。
【0311】
<入出力処理部の処理の概要>
次に、図22により、本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部302の処理について説明する。図22は本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【0312】
MUとMUは、それぞれ剰余処理部303を表す。入力するメッセージの組はそれぞれ、MUまたはMUの右辺の括弧内に、剰余処理部303から出力するメッセージは左辺の括弧内に表す。なお、MU、MUの説明は後述する。
【0313】
入出力処理部302と剰余処理部303のメッセージの受け渡しには、記憶装置123を用いる。メッセージの格納領域として、RAM141におけるXA、XB、XN、XRと、他の記憶領域(例えばRAM131)におけるYQ、YR、YT(メッセージの格納用に領域を定義)を用いる。
【0314】
なお、入出力処理部302と剰余処理部303におけるメッセージ交換の際の記憶装置123の利用方法の詳細については、図24と図25を用いて後述する。
【0315】
<入出力処理>
入力部321は、メッセージaをYQに、メッセージbをXBに、メッセージnをXNに格納する。出力指示部323は、剰余処理部303へ出力する商を指すメッセージqをXBに、剰余rを指すメッセージrをYTに格納するよう指示する(S2201)。
【0316】
入力部321は、メッセージnをXAに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq2をYQに、剰余を指すメッセージr2をYRに格納するよう指示する(S2202)。
【0317】
蓄積部324は、YRに格納されたメッセージr2とYTに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージrをYRに格納する(S2203)。
【0318】
入力部321は、メッセージaをXAに、メッセージbをXBに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq3をXBに、剰余を指すメッセージr3をYTに格納するよう指示する(S2204)。
【0319】
蓄積部324は、YRに格納されたメッセージrとYTに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージrをYRに格納するよう指示する(S2205)。
【0320】
入力部321は、加減乗算部341に対してメッセージを交換し、定数(2−1)をXAに、(q+q)の値を持つメッセージ(q+q)をXBに、メッセージnをXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージq4をXBに、剰余を指すメッセージr4をYQに格納するよう指示する(S2206)。
【0321】
入力部321は、メッセージnをXAに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、商を指すメッセージq5をXBに、剰余を指すメッセージr5をYTに格納するよう指示する(S2207)。
【0322】
蓄積部324は、YRに格納されたメッセージrとYQに格納されたメッセージrを加減乗算部341に入力し、(r+r)の値を持つメッセージqをYQに格納する。ついで、蓄積部324は、YRに格納されたメッセージqとXBに格納されたメッセージqを加減乗算部341に入力し、(q−q)の値を持つメッセージqをYQに格納する。さらに、蓄積部324は、YTに格納されたメッセージrとYRに格納されたメッセージrを加減乗算部341に入力し、(r−r)の値を持つメッセージrをYRに格納する(S2208)。
【0323】
入力部321は、加減乗算部341に対してメッセージを交換し、(a+a)の値を持つメッセージ(a+a)をXAに、(b+b)の値を持つメッセージ(b+b)をXBに、定数1をXNに格納する。出力指示部323は、剰余処理部303へ、出力する商を指すメッセージqをXAに、剰余を指すメッセージrをYTに格納するよう指示する(S2209)。
【0324】
蓄積部324は、XAに格納されたメッセージqとYQに格納されたメッセージqを加減乗算部341に入力し、(q+q)の値を持つメッセージqをYQに格納する。さらに、蓄積部324は、YTに格納されたメッセージrとYRに格納されたメッセージrを加減乗算部341に入力し、(r+r)の値を持つメッセージrをYRに格納する(S2210)。
【0325】
<補正部の処理>
本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の補正部322の処理は、実施の形態1(図4のシーケンス図を参照)と同様である。
【0326】
<剰余処理部の処理>
次に、図23により、本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部303の処理について説明する。図23は本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【0327】
本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA101内の剰余処理部303の処理は、2種類の異なる処理手続きMU、MUを有する。
【0328】
MUは、実施の形態1における剰余処理部303の処理手続き(図9のフローチャートを参照)と同様であり、入力されたメッセージを乗数、被乗数、法とみなし、モンゴメリ乗算における剰余乗算の商と剰余を計算する。
【0329】
MUは、入力されたメッセージを乗数、被乗数、法とみなし、古典的な剰余乗算における剰余乗算の商と剰余を計算する。実施の形態2における剰余処理部303の処理と同様であるが、実施の形態5では仮定する剰余乗算器113(剰余乗算の種類)が異なるため、図23に示すように、MUは実施の形態2と異なる処理手続きである。
【0330】
次に、MUの処理手続きを説明する。
【0331】
乗数変更部335は、剰余乗算を実行する前に、下記の式を用い、XBに設定されたメッセージy、XNに設定されたメッセージzが0≦y<zを満たすよう、メッセージyの値を変更する(S2301)。
【0332】
y←y−jz
ただし、jは整数である。また、xとyの値を変更する必要がない場合、i=j=0が成り立ち、S2301と後述するS2313の処理は不要である。
【0333】
剰余乗算器取扱部331は、入力部321が、XA、XB、XNに設定したメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。XAにメッセージx、XBにメッセージy、XNにメッセージzを設定した場合、以下の式で定義されるモンゴメリ乗算の剰余y’をXRに出力する。
【0334】
y’←xy2−wmod z
ただし、xは乗数、yは被乗数、zは法である。次に、移動部333は、メッセージy’をXAへ移動する(S2302)。
【0335】
剰余乗算器取扱部331は、XA、XB、XNに設定したメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。XAにメッセージx、XBにメッセージy’、XNにメッセージzが設定してあるので、以下の式で定義されるモンゴメリ乗算の剰余rをXRに出力する。
【0336】
r←xy’2−wmod z
ただし、xは乗数、y’は被乗数、zは法である。次に、移動部333は、出力格納部が指示したメッセージの格納領域へ、メッセージrを移動する(S2303)。
【0337】
法変更部334は、加減乗算部341を用い、XNに設定したメッセージzの値を変更し、z+2の値を持つメッセージz’を作成し、XNに格納する(S2304)。
【0338】
剰余乗算器取扱部331は、XA、XB、XNに設定されたメッセージに基づき、モンゴメリ乗算による剰余乗算の剰余を計算する。XAにメッセージxを、XBにメッセージyを、XNにメッセージz’を設定した場合、以下の式で定義されるモンゴメリ乗算の剰余r’をXRに出力する。
【0339】
r’←xy’2−wmod z’
ただし、xは乗数、yは被乗数、z’は法である(S2305)。
【0340】
商演算部332は、条件判定部343を用い、r−r’が偶数であればS2309へ、奇数であればS2308へと進む(S2306)。商演算部332は、条件判定部343を用い、条件式(r’≦r)を満たせばS2311へ、満たさなければS2310へと進む。商演算部332は、メッセージδの値を1と設定する(S2308)。または、商演算部332は、メッセージδの値を0と設定する(S2311)。または、商演算部332は、メッセージδの値を2と設定する(S2310)。
【0341】
商演算部332は、加減乗算部341と剰余計算部342を用い、以下の式を満たすメッセージqを計算する(S2312)。
【0342】
q← (r−r’+δz’)/2
商演算部332は、加減乗算部341と剰余計算部342を用い、以下の式を満たすメッセージqを計算し、出力指示部323が指示したメッセージの格納領域へ、メッセージqを出力する(S2313)。
【0343】
q← q+jx
<入出力処理部と剰余処理部の構成>
次に、図24および図25により、本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムの記憶装置123へのメッセージの格納順序について説明する。図24および図25は、本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【0344】
図24および図25は、行と列をもつ表から構成される。最も左の列は、図22および図23で示したフローチャートの各ステップと対応を取り、他の列は、メッセージを格納する記憶領域であるXR、XA、XB、XN、YQ、YR、YTを意味する。
【0345】
各行には記憶領域内に格納されるメッセージを表し、「任意」は、格納されているメッセージはどのような値でもかまわない。また、上行から下行に順々に処理が実行され、「―」は以前の処理にて格納されたメッセージを格納し続ける状態を指す。また、y、zは定数を表すメッセージであり、例えば、図24および図25では、定数xは式(22w mod n)の値を持ち(即ち、y=22wmod nが成り立つ)、定数yはy=2−1、定数zはz=1である。
【0346】
S2201の第1行目では、YQにメッセージa、XBにメッセージb、XNにメッセージnが格納される。S2201の第2行目では、XAに定数xが格納される。S2201の第3行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。
【0347】
S2201の第4行目では、XBにメッセージrが格納される。S2201の第5行目では、XAにメッセージaが格納される。S2201の第6行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。
【0348】
S2201の第7行目では、YTにもメッセージrが格納される。S2201の第8行目では、メッセージnの値を変更したメッセージn’がXNに格納される。S2201の第9行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S2201の第10行目では、XBに古典的な剰余乗算の商であるメッセージqが格納される。
【0349】
S2202の第1行目では、XAにメッセージn、XNにメッセージzが格納される。S2202の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。他の記憶領域に格納するメッセージに変更はない。
【0350】
S2202の第3行目では、YRにもメッセージrが格納される。S2202の第4行目では、メッセージzの値を変更したメッセージz’がXNに格納される。S2202の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S2202の第6行目では、XBにモンゴメリ乗算の商であるメッセージqが格納される。
【0351】
S2203では、(r−r)の値をもつメッセージrがYRに格納される。
【0352】
S2204の第1行目では、XAにメッセージa、XBにメッセージb、XNにメッセージzが格納される。S2204の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。S2204の第3行目では、YTにもメッセージrが格納される。S2204の第4行目では、メッセージzの値を変更したメッセージz’がXNに格納される。
【0353】
S2204の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S2204の第6行目では、XAにモンゴメリ乗算の商であるメッセージqが格納される。
【0354】
S2205では、(r−r)の値をもつメッセージrがYRに格納される。
【0355】
S2206の第1行目では、XAに定数y、XBに(q+q)の値をもつメッセージ(q+q)が、XNにメッセージnが格納される。S2206の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。S2206の第3行目では、YQにもメッセージrが格納される。S2206の第4行目では、メッセージnの値を変更したメッセージn’がXNに格納される。
【0356】
S2206の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S2206の第6行目では、XBにモンゴメリ乗算の商であるメッセージqが格納される。
【0357】
S2207の第1行目では、XAにメッセージn、XNに定数zが格納される。S2207の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。S2207の第3行目では、YTにもメッセージrが格納される。S2207の第4行目では、定数zの値を変更した定数z’がXNに格納される。
【0358】
S2207の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S2207の第6行目では、XBにモンゴメリ乗算の商であるメッセージqが格納される。
【0359】
S2208の第1行目では、(−r−r+q)の値をもつメッセージqがYQに格納される。S2208の第2行目では、(−r+r)の値を持つメッセージrがYRに格納される。
【0360】
S2209の第1行目では、(a+a)の値を持つメッセージがXAに、(b+b)の値を持つメッセージがXBに、定数zがXNに格納される。S2209の第2行目では、XRにモンゴメリ乗算の剰余であるメッセージrが格納される。S2209の第3行目では、YTにもメッセージrが格納される。S2209の第4行目では、定数zの値を変更した定数z’がXNに格納される。
【0361】
S2209の第5行目では、XRにモンゴメリ乗算の剰余であるメッセージr’が格納される。S2209の第6行目では、XAにモンゴメリ乗算の商であるメッセージqが格納される。
【0362】
S2210の第1行目では、(q+q)の値をもつメッセージqがYQに格納される。S2210の第2行目では、(r+r)の値をもつメッセージrがYRに格納される。
【0363】
<応用例>
実施の形態5では、剰余乗算器113の種類とは異なる、剰余乗算器113の2倍のビット長の剰余乗算の実現方法の一例として、剰余乗算器113がモンゴメリ乗算を実装する場合に、剰余乗算器113のビット長の2倍の2倍剰余乗算の実現方法を示した。本技術の他の利用例として、例えば、剰余乗算器113がモンゴメリ乗算を実装する場合に、剰余乗算器113のビット長の2倍の古典的な剰余乗算が実現できる。
【0364】
また、剰余乗算器113が古典的な剰余乗算を実装する場合にも、剰余乗算器113のビット長の2倍のモンゴメリ乗算、または2分割剰余乗算を実現できる。
【0365】
また、実施の形態5では、実施の形態1と同様の構成の通信システム(図1を参照)を用いた。他に本技術が適用できる通信システムの構成として、例えば、実施の形態3と同様の通信システムがある。
【0366】
また、RSAの署名検証や暗号化処理などでは、剰余乗算器113がモンゴメリ乗算を実装する場合、事前計算として、モンゴメリ定数の自乗を必要とする場合がある。実施の形態5で説明した本技術を用いると、この事前計算の計算処理が軽く、または不要になるように、他の剰余乗算への変更が可能であり、計算の高速化にも貢献できる。
【0367】
また、実施の形態1、2、5では、剰余乗算器113が利用する記憶領域は重複しないように、即ち、XR、XA、XB、XNが異なる記憶領域を指すように説明した。しかし、これらの記憶領域が同一の領域を指しても、容易に本技術は実現可能である。
【0368】
以上のように実施の形態5では、メモリ等の記憶装置の使用量を最小に抑えつつ、剰余乗算器を用い、剰余乗算器が処理可能なビット長を越える剰余乗算を処理することが可能である。
【0369】
(実施の形態6)
実施の形態1〜5で述べた技術は、RSA暗号、ElGamal暗号やDSA暗号、さらに楕円暗号、乱数生成など、剰余乗算を利用する全ての処理に適用できる。本技術により実現できる暗号技術の例として、RSA暗号におけるメッセージの暗号化処理について説明する。
【0370】
図26により、本発明の実施の形態6に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置121が行う全体処理について説明する。図26は本発明の実施の形態6に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図である。
【0371】
データ処理部115は、入出力インタフェース111あるいは記憶装置123を介して公開鍵とメッセージが入力されると(S2601)、入力されたメッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるようにメッセージを区切る。また、短い場合には、パディング処理により、メッセージを予め定めたビット長となるように設定する。以下、所定のビット長として2wビットに区切られている部分メッセージ(これ以降、部分メッセージをメッセージと呼ぶ)について説明する。ただし、wは正の整数とする。
【0372】
データ処理部115は、メッセージを2倍剰余乗算部116に出力する(S2602)。
【0373】
2倍剰余乗算部116では、まず、入力されたメッセージを剰余乗算器113が実装する剰余乗算(モンゴメリ乗算または古典的な剰余乗算)に適した形式に変換し、剰余乗算器113を用い、2wビットの剰余を計算する。2倍剰余乗算部116は、剰余乗算器113が実装する剰余乗算に適した形式からメッセージをデータ処理部115へ入力時の整数表現に変換し、データ処理部115へ出力する(S2603)。
【0374】
S2602とS2603により、2wビットのメッセージに対し、2wビットの剰余乗算が1回計算された。RSA暗号の暗号化処理では、べき乗の剰余乗算が要求されるため、2wビットの剰余乗算を複数繰り返せばよい。繰り返しの剰余乗算の処理が終了すると、データ処理部115では、べき乗の剰余乗算を計算した2wビットのメッセージを、入出力インタフェース111または記憶装置123へ出力する(S2604)。
【0375】
なお、データ処理部115と2倍剰余乗算部116のメッセージの受け渡しには、記憶装置123へのメッセージの書き込みと読み出し、またはネットワーク151を用い、メッセージの受け渡しを実施する。
【0376】
なお、2倍剰余乗算部116の処理内容、仮定するシステム環境は、他の実施の形態と共通である。
【0377】
RSA暗号における暗号化処理の他に、復号化処理、ディジタル署名の生成、ディジタル署名の検証処理に本技術が適用できる。特に、ディジタル署名の生成と検証を用いると、暗号技術による認証手段が提供できる。
【0378】
<応用例>
各実施の形態では、剰余乗算器113のビット長のk(0<k≦2)倍の剰余乗算の演算方法を示したが、本技術を再帰的に利用し、ビット長のk’(>2)倍化にも対応できる。例として、本技術の再帰的な利用により、剰余乗算器113の最大ビット長の4倍化が可能である。
【0379】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【0380】
本発明は、セキュリティ技術に用いられる剰余乗算処理装置に関し、特に、サーバ、ストレージ、ICカード等に搭載される暗号機器への実装に適用可能である。
【図面の簡単な説明】
【0381】
【図1】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【図2】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図である。
【図3】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の2倍剰余乗算部の構成を示す機能ブロック図である。
【図4】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の2倍剰余乗算部の処理を示すシーケンス図である。
【図5】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図6】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図7】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図8】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図9】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【図10】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図11】本発明の実施の形態1に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図12】本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の2倍剰余乗算部の処理を示すシーケンス図である。
【図13】本本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図14】本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図15】本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図16】本発明の実施の形態2に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【図17】本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムの全体構成を示す構成図である。
【図18】本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図19】本発明の実施の形態3に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図20】本発明の実施の形態4に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図21】本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の2倍剰余乗算部の処理を示すシーケンス図である。
【図22】本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の入出力処理部の計算処理を示すフローチャートである。
【図23】本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の剰余処理部の計算処理を示すフローチャートである。
【図24】本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図25】本発明の実施の形態5に係る剰余乗算処理装置を適用した通信システムのコンピュータA内の入出力部と剰余処理部との処理における記憶装置への格納メッセージを示す図である。
【図26】本発明の実施の形態6に係る剰余乗算処理装置を適用した通信システムのコンピュータ内の処理装置が行うメッセージの受け渡しの様子を示したシーケンス図である。
【符号の説明】
【0382】
101…コンピュータA、102…コンピュータB、111…入出力インタフェース、112…CPU、113…剰余乗算器、115…データ処理部、116…2倍剰余乗算部、121…処理装置、122…演算装置、123…記憶装置、131…RAM(揮発性メモリ1)、132…EEPROM(不揮発性メモリ)、133…ROM(不揮発性メモリ)、141…RAM(揮発性メモリ2)、151…ネットワーク、301…表現処理部、302…入出力処理部、303…剰余処理部、304…共通部、311…分割部、312…合成部、321…入力部、322…補正部、323…出力指示部、324…蓄積部、331…剰余乗算器取扱部、332…商演算部、333…移動部、334…法変更部、335…乗数変更部、341…加減乗算部、342…剰余計算、342…剰余計算部、343…条件判定部。

【特許請求の範囲】
【請求項1】
剰余乗算を計算する剰余乗算器と、データを格納する記憶領域をもつ記憶装置を有し、前記剰余乗算器が処理できるビット長を越えた剰余乗算を計算する剰余乗算処理装置であって、
前記剰余乗算処理装置が計算過程で作成するデータを格納する前記記憶領域を指定する出力指示部を備えたことを特徴とする剰余乗算処理装置。
【請求項2】
請求項1記載の剰余乗算処理装置において、
前記剰余乗算処理装置が計算過程で作成するデータを指定された前記記憶領域へ格納する移動部を備えたことを特徴とする剰余乗算処理装置。
【請求項3】
請求項2記載の剰余乗算処理装置において、
前記剰余乗算処理装置の計算過程で格納されたデータから情報を前記記憶領域へ蓄積する第1の処理部を備えたことを特徴とする剰余乗算処理装置。
【請求項4】
請求項3記載の剰余乗算処理装置において、
前記剰余乗算器の入力に前記記憶領域が格納するデータの記憶領域を指定する入力部を備えたことを特徴とする剰余乗算処理装置。
【請求項5】
請求項4記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類に応じて、前記剰余乗算器がモンゴメリ乗算を実装する場合には、前記剰余乗算器が処理できるビット長を越えたモンゴメリ乗算を計算し、前記剰余乗算器が古典的な剰余乗算を実装する場合には、前記剰余乗算器が処理できるビット長を越えた古典的な剰余乗算を計算する2倍剰余乗算部を備えたことを特徴とする剰余乗算処理装置。
【請求項6】
請求項4記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類とは異なる、前記剰余乗算器が処理できるビット長を越えた剰余乗算を計算する2倍剰余乗算部を備えたことを特徴とする剰余乗算処理装置。
【請求項7】
請求項6記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類とは異なる、剰余乗算の商を計算する第2の処理部を備えることを特徴とする剰余乗算処理装置。
【請求項8】
請求項5または7記載の剰余乗算処理装置において、
前記剰余乗算器が実装する剰余乗算の種類にあわせ、前記剰余乗算器が処理できるビット長を越えたデータを、前記剰余乗算器が処理できるビット長以下にデータの形式を変更する第3の処理部を備えたことを特徴とする剰余乗算処理装置。
【請求項9】
請求項8記載の剰余乗算処理装置において、
前記剰余乗算処理装置が計算過程で作成するデータのビット長を、前記剰余乗算器が処理できるデータのビット長以下に調整する第4の処理部を備えたことを特徴とする剰余乗算処理装置。
【請求項10】
請求項5または6記載の剰余乗算処理装置において、
前記2倍剰余乗算部により、前記剰余乗算器が処理できるビット長を越えた剰余乗算を計算し、その計算結果に基づいて、暗号技術に基づく認証処理またはデータ暗号化処理を行うことを特徴とする剰余乗算処理装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate


【公開番号】特開2011−7820(P2011−7820A)
【公開日】平成23年1月13日(2011.1.13)
【国際特許分類】
【出願番号】特願2007−238715(P2007−238715)
【出願日】平成19年9月14日(2007.9.14)
【出願人】(000005108)株式会社日立製作所 (27,607)
【Fターム(参考)】