(57)【要約】【課題】公開鍵暗号方式の暗号化処理における安全性を高める。【解決手段】群に含まれる元を入力する元入力部（10）と、元入力部から入力された元、および、群に対応した単位元を保持する記憶部（11）と、記憶部から元および単位元を取得し、該取得した各元を初期値とするループ処理により第１の演算および第２の演算を行う演算部（12）と、予め設定された個数のビットで特定の整数値を表すビット列を入力するビット列入力部（13）と、ビット列の全てのビットを各ビット毎に参照し、当該ビットが示す値に予め関連付けられた第１および第２の演算のうちのいずれかの実行を当該ビットの値に応じて演算部に指示する演算制御部（14）とを備える。【選択図】        図１
2004198566.tif 000002
【特許請求の範囲】
【請求項１】
群に含まれる元を入力する元入力部と、
前記元入力部から入力された元および前記群に対応した単位元を保持する記憶部と、
前記記憶部から前記元および前記単位元を取得し、該取得した各元を初期値とするループ処理により第１の演算および第２の演算を行う演算部と、
予め設定されたビット数で特定の整数値を表すビット列を入力するビット列入力部と、
前記入力されたビット列の全てのビットを各ビット毎に参照し、当該ビットが示す値に予め関連付けられた前記第１および第２の演算のうちのいずれかの実行を当該ビットの値に応じて前記演算部に指示する演算制御部とを備えることを特徴とする演算処理装置。
【請求項２】
前記群は、有限体上に定義された楕円曲線上の点からなる加法群である請求項１記載の演算処理装置。
【請求項３】
前記ビット列は、整数ｋを表し、
前記演算制御部は、前記参照したビットが第１の値を示すとき、前記単位元を初期値とする変数Ｓおよび前記元を初期値とする変数Ｔについての前記第１の演算となるＴ＝Ｓ＋ＴおよびＳ＝２Ｓの実行を前記演算部に指示し、また、前記参照したビットが第２の値を示すとき、前記第２の演算となるＳ＝Ｓ＋ＴおよびＴ＝２Ｔの実行を前記演算部に指示し、
前記演算部は、前記指示に基づいて、スカラ値を前記整数ｋとする前記元のスカラ倍の値を求める請求項２記載の演算処理装置。
【請求項４】
前記第１の値および第２の値はそれぞれ０および１であり、前記単位元の値は０である請求項３記載の演算処理装置。
【請求項５】
前記演算制御部は、前記第１または第２の演算を前記演算部に実行させるべく、前記変数Ｓおよび変数Ｔをそれぞれｔ［０］およびｔ［１］とし且つ各ビットが示す値をｋｉとした、ｔ［１−ｋｉ］＝ｔ［０］＋ｔ［１］およびｔ［ｋｉ］＝２ｔ［ｋｉ］の演算を行うよう指示する請求項４記載の演算処理装置。
【請求項６】
前記記憶部は、前記変数ｔ［０］およびｔ［１］の各値を一時的に格納する第１の記憶領域および第２の記憶領域を有し、
前記演算部は、前記演算を実行するとき、前記第１および第２の各記憶領域から変数ｔ［０］およびｔ［１］を取得し、当該演算の結果を、対応する前記第１または第２の記憶領域へ供給する請求項５記載の演算処理装置。
【請求項７】
前記群は、整数を法とする剰余環からなる乗法群である請求項１記載の演算処理装置。
【請求項８】
前記ビット列は、整数ｋを表し、
前記演算制御部は、前記参照したビットが第１の値を示すとき、前記単位元を初期値とする変数Ｓおよび前記元を初期値とする変数Ｔについての前記第１の演算となるＴ＝ＳＴおよびＳ＝Ｓ２の実行を前記演算部に指示し、また、前記参照したビットが第２の値を示すとき、前記第２の演算となるＳ＝ＳＴおよびＴ＝Ｔ２の実行を前記演算部に指示し、
前記演算部は、べき数を前記整数ｋとする前記元のべき乗の値を求めるべく、前記指示に基づいて、ｐを正の整数とする法ｐの剰余乗算を行う請求項７記載の演算処理装置。
【請求項９】
前記第１の値および第２の値はそれぞれ０および１であり、前記単位元の値は１である請求項８記載の演算処理装置。
【請求項１０】
前記演算制御部は、前記第１または第２の演算を前記演算部に実行させるべく、前記変数Ｓおよび変数Ｔをそれぞれｔ［０］およびｔ［１］とし且つ各ビットが示す値をｋｉとした、ｔ［１−ｋｉ］＝ｔ［０］＊ｔ［１］およびｔ［ｋｉ］＝ｔ［ｋｉ］２の演算を行うよう指示する請求項９記載の演算処理装置。
【請求項１１】
前記記憶部は、前記変数ｔ［０］およびｔ［１］の各値を一時的に格納する第１の記憶領域および第２の記憶領域を有し、
前記演算部は、前記演算を実行するとき、前記第１および第２の各記憶領域から変数ｔ［０］およびｔ［１］を取得し、当該演算の結果を、対応する前記第１または第２の記憶領域へ供給する請求項１０記載の演算処理装置。
【請求項１２】
前記ビット列は、所定の情報の暗号化および該暗号化された暗号化情報の復号化のための鍵情報を示す請求項２記載の演算処理装置。
【請求項１３】
前記暗号化および復号化は電子署名に関する処理である請求項１２記載の演算処理装置。
【請求項１４】
前記暗号化および復号化は、送信側で情報を暗号化して送信し、該送信された情報を受信した受信側で当該情報を解読すべく復号化する秘密通信に関する処理である請求項１２記載の演算処理装置。
【請求項１５】
前記乗法群は暗号化すべき情報または復号化すべき情報であり、前記ビット列は当該暗号化または復号化のための鍵情報を示す請求項７記載の演算処理装置。
【請求項１６】
前記暗号化および復号化は電子署名に関する処理である請求項１５記載の演算処理装置。
【請求項１７】
前記暗号化および復号化は、送信側で情報を暗号化して送信し、該送信された情報を受信した受信側で当該情報を解読すべく復号化する秘密通信に関する処理である請求項１５記載の演算処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線暗号方式あるいはＲＳＡ（Rivest−Shamir−Adleman）暗号方式のような公開鍵暗号方式に沿った演算処理を行う演算処理装置に関する。
【０００２】
【従来の技術】
従来、公開鍵暗号方式を用いた電子署名機能を果たすＩＣカードのＬＳＩに対し、電力解析と称される手法により第三者が鍵情報を推測することが知られている。この電力解析では、暗号化処理または復号化処理の際に、鍵情報の「０」または「１」に応じて行う演算での電流値に着目し、各電流値が当該２値間で異なることを利用して鍵情報が推測される。
【０００３】
このような鍵情報の推測を困難にするために、前記２値間の電流値の差異を低減する手法が提案されている。例えば、後述する非特許文献１では、楕円曲線暗号方式で用いられる、楕円曲線上の加法群におけるスカラ倍計算に対する対策が開示されている。図１３は、当該文献に沿ったアルゴリズムを示す。このアルゴリズムに沿った演算では、鍵情報が示す整数値を２進表示したときの各ビットとなるビットｋｉを、ｋｔ−１からｋ０までループ処理により順次参照し、当該参照ビットの値が「０」および「１」のいずれであっても、その参照毎に加算および２倍算の演算を１回ずつ実行する。これにより、ビットｋｉが示す値に係わらず、各ループ処理毎に同等の電流が検知されることから、鍵情報を推測することは困難となる。
【０００４】
【非特許文献１】
Julio Lopezand Ricardo Dahab, "Fast multiplication on elliptic curves over GF(2 m ) without precomputation", CHES '99, LNCS1717, 1999, 316−327
【０００５】
【発明が解決しようとする課題】
ところで、一般的に鍵情報の値はデバイス毎に異なる値が設定され、デバイス内では、鍵情報を２進表示したものが所定のビット長で表現される。この所定のビット長を鍵長とし、鍵長を例えば８ビットとする場合、実質的な鍵部分が「１１」、すなわち鍵情報が示す整数値が「３」であるデバイスでは、鍵情報が「００００００１１」と表現され、鍵部分が「１０１」である他のデバイスでは鍵情報は「０００００１０１」と表現される。
【０００６】
しかしながら、図１３に示す前記文献のアルゴリズムでは、鍵情報のビット列ｋについて、その先頭ビットｋｔ−１の値が「ｋｔ−１＝１」と定義されていることから、当該ビット列ｋ自体が鍵部分を示すことが明らかとなる。すなわち、従来は、例えば鍵情報の「０００００１０１」においては、その鍵部分である「１０１」が前記ビット列ｋに該当する。そして、ビット列ｋの先頭の「１」が参照ビットとなったとき、加算および２倍算のループ処理が開始される。
【０００７】
このことから、ビット列ｋのｋｔ−２からｋ０間に行われるループ処理の回数を外部から検知することにより、鍵部分のビット長が推測できると考えられる。これによりビット長が確定すると、２進表示である鍵部分の割り出しが容易になり、デバイスにおける安全性の確保が困難となるという不都合があった。
【０００８】
本発明は、前記した課題に鑑みてなされたものであり、公開鍵暗号方式を用いたデバイスの安全性を高めることができる演算処理装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明に係る演算処理装置は、群に含まれる元を入力する元入力部と、前記元入力部から入力された元および前記群に対応した単位元を保持する記憶部と、前記記憶部から前記元および前記単位元を取得し、該取得した各元を初期値とするループ処理により第１の演算および第２の演算を行う演算部と、予め設定されたビット数で特定の整数値を表すビット列を入力するビット列入力部と、前記入力されたビット列の全てのビットを各ビット毎に参照し、当該ビットが示す値に予め関連付けられた前記第１および第２の演算のうちのいずれかの実行を当該ビットの値に応じて前記演算部に指示する演算制御部とを備える。
【００１０】
また、本発明に係る演算処理装置に関する前記群は、有限体上に定義された楕円曲線上の点からなる加法群とすることができる。
【００１１】
前記群を加法群とする前記演算処理装置において、前記ビット列が整数ｋを表す場合、前記演算制御部は、前記参照したビットが第１の値を示すとき、前記単位元を初期値とする変数Ｓおよび前記元を初期値とする変数Ｔについての前記第１の演算となるＴ＝Ｓ＋ＴおよびＳ＝２Ｓの実行を前記演算部に指示し、また、前記参照したビットが第２の値を示すとき、前記第２の演算となるＳ＝Ｓ＋ＴおよびＴ＝２Ｔの実行を前記演算部に指示し、前記演算部は、前記指示に基づいて、スカラ値を前記整数ｋとする前記元のスカラ倍の値を求めることができる。
【００１２】
前記第１の値および第２の値はそれぞれ０および１であり、前記単位元の値は０とすることができる。
【００１３】
その場合、前記演算制御部は、前記第１または第２の演算を前記演算部に実行させるべく、前記変数Ｓおよび変数Ｔをそれぞれｔ［０］およびｔ［１］とし且つ各ビットが示す値をｋｉとした、ｔ［１−ｋｉ］＝ｔ［０］＋ｔ［１］およびｔ［ｋｉ］＝２ｔ［ｋｉ］の演算を行うよう指示することができる。
【００１４】
前記記憶部に、前記変数ｔ［０］およびｔ［１］の各値を一時的に格納する第１の記憶領域および第２の記憶領域を設けることができる。その場合、前記演算部は、前記演算を実行するとき、前記第１および第２の各記憶領域から変数ｔ［０］およびｔ［１］を取得し、当該演算の結果を、対応する前記第１または第２の記憶領域へ供給することができる。
【００１５】
本発明に係る演算処理装置に関する前記群は、整数を法とする剰余環からなる乗法群とすることができる。
【００１６】
また、前記群を乗法群とする前記演算処理装置において、前記ビット列が整数ｋを表す場合、前記演算制御部は、前記参照したビットが第１の値を示すとき、前記単位元を初期値とする変数Ｓおよび前記元を初期値とする変数Ｔについての前記第１の演算となるＴ＝ＳＴおよびＳ＝Ｓ２の実行を前記演算部に指示し、また、前記参照したビットが第２の値を示すとき、前記第２の演算となるＳ＝ＳＴおよびＴ＝Ｔ２の実行を前記演算部に指示し、前記演算部は、べき数を前記整数ｋとする前記元のべき乗の値を求めるべく、前記指示に基づいて、ｐを正の整数とする法ｐの剰余乗算を行うことができる。
【００１７】
前記第１の値および第２の値はそれぞれ０および１であり、前記単位元の値は１とすることができる。
【００１８】
その場合、前記演算制御部は、前記第１または第２の演算を前記演算部に実行させるべく、前記変数Ｓおよび変数Ｔをそれぞれｔ［０］およびｔ［１］とし且つ各ビットが示す値をｋｉとした、ｔ［１−ｋｉ］＝ｔ［０］＊ｔ［１］およびｔ［ｋｉ］＝ｔ［ｋｉ］２の演算を行うよう指示することができる。
【００１９】
前記記憶部に、前記変数ｔ［０］およびｔ［１］の各値を一時的に格納する第１の記憶領域および第２の記憶領域を設けることができる。その場合、前記演算部は、前記演算を実行するとき、前記第１および第２の各記憶領域から変数ｔ［０］およびｔ［１］を取得し、当該演算の結果を、対応する前記第１または第２の記憶領域へ供給する。
【００２０】
本発明に係る演算処理装置に関する前記加法群は、前記ビット列に、所定の情報の暗号化および該暗号化された暗号化情報の復号化のための鍵情報を適用することができる。その場合、当該演算処理装置を、電子署名に関する処理を行う装置として用いることができる。また、前記演算処理装置を、電子署名の処理に限らず、例えば、送信側で情報を暗号化して送信し、該送信された情報を受信した受信側で当該情報を解読すべく復号化する、いわゆる秘密通信に関する処理に利用することができる。
【００２１】
本発明に係る演算処理装置に関する前記乗法群として、暗号化すべき情報である平文情報または復号化すべき情報である暗号化情報を適用することができ、前記ビット列として、当該暗号化または復号化のための鍵情報を適用することができる。その場合、当該演算処理装置を、電子署名に関する処理を行う装置として用いることができる。また、前記演算処理装置を、電子署名の処理に限らず、例えば、送信側で情報を暗号化して送信し、該送信された情報を受信した受信側で当該情報を解読すべく復号化する、いわゆる秘密通信に関する処理に利用することができる。
【００２２】
【発明の実施の形態】
以下、本発明の実施の形態を具体例を用いて説明する。
〈具体例１〉
図１は、本発明に係る演算処理装置の具体例１の構成を示すブロック図である。
具体例１の演算処理装置１０１は、電子署名の機能を果たすＩＣカードのＬＳＩに搭載され、当該ＬＳＩが楕円曲線暗号方式のような公開鍵暗号方式による暗号化処理および復号化処理を実行するための楕円曲線演算を行う。演算処理装置１０１は、有限体上に定義された楕円曲線上の点を示す元Ｇからなる加法群を用い、任意の整数であるスカラ値ｋを鍵情報として元Ｇのスカラ倍演算（ｋＧ）を行い、その演算結果を出力する。前記ＬＳＩでは、例えば暗号化処理においては、前記演算結果を利用して平文の暗号化が行われる。
【００２３】
演算処理装置１０１は、図１に示すように、加法群の元Ｇを入力する元入力部である加法元入力部１０と、該加法元入力部からの元Ｇおよび後述する単位元「０」を保持する記憶部１１とを備える。記憶部１１には、元Ｇを初期値とする変数Ｔを保持する記憶領域１１ａ、および、単位元「０」を初期値とする変数Ｓを保持する記憶領域１１ｂが設けられている。
【００２４】
演算処理装置１０１は、さらに、記憶部１１から変数Ｓおよび変数Ｔに関する後述する楕円曲線演算を行う楕円曲線演算部１２と、前記スカラ値をビット数ｎで表すビット列ｋを入力するビット列入力部となるスカラ値入力部１３と、該スカラ値入力部からのビット列を構成する全てのビットについて各ビット値を判別し、該判別した値に対し予め関連付けられている後述する第１の演算および第２の演算を楕円曲線演算部１２に指示する演算制御部１４と、この演算制御部１４の最終的な演算結果を出力する出力部１５とを備える。
【００２５】
スカラ値入力部１３は、予め設定されたｎ個のビットｋｉ（ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０）からなるビット列ｋ、すなわち鍵長がｎビットである鍵情報を示すビット列ｋを演算制御部１４へ入力する。ビット列ｋは、予めユーザによりスカラ値入力部１３に設定される。このビット列ｋには、従来の鍵情報と同様に、ｍビット（ｍ＜ｎ）の鍵部分が含まれており、鍵部分は、従来と同様に、暗号化情報の復号処理のために予め保持されている正規の復号鍵に関連して値が設定され、その値は機密性を高めるためにデバイス毎に異なるように設定される。そして、例えば、ある複数のＩＣカードに共通に設定される鍵長をｎ＝１９２ビットとした場合、各カードの鍵部分のビット長は、鍵部分が示す値に応じて、ｍ＝１８０ビットあるいはｍ＝１９０ビットなど、カード毎に異なるビット長となりうる。
【００２６】
演算制御部１４は、ビット列ｋの全てのビットｋｉのビット値を判別する毎に、図９に示すアルゴリズムに沿った楕円曲線演算を楕円曲線演算部１２に指示する。この楕円曲線演算により、楕円曲線演算部１２では、有限体上に定義された楕円曲線上の点Ｇのスカラ倍である「ｋＧ」が算出される。図示のアルゴリズムにおいて、「Ｓ＋Ｔ」は前記した楕円曲線上での加算を示し、「２Ｓ」は当該楕円曲線上での２倍算を示す。このアルゴリズムによれば、変数Ｓの初期値として、加法の単位元である「０」が設定されていることから、ビットｋｉが鍵部分の先頭ビットを示すまでの演算処理においては、複数回のループ処理が行われても変数Ｓおよび変数Ｔの値を初期値から他の値に推移させることはない。
【００２７】
演算処理装置１０１の動作を図２に示すフローチャートに沿って説明する。
スカラ値入力部１３には、鍵情報となるスカラ値ｋ、すなわちｎ個のビットｋｉ（ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０）からなるビット列ｋが入力され、また、記憶部１１には、予め、変数Ｔの初期値である元Ｇが加法元入力部１０から記憶領域１１ａに入力され、変数Ｓの初期値である単位元「０」が記憶領域１１ｂに入力される（ステップＳ１）。
【００２８】
演算制御部１４は、スカラ値入力部１３から入力されたビット列ｋについて、その先頭ビットｋｎ−１から最終ビットｋ０まで順次検知すると共に（ステップＳ２：ＮＯ）、各ビットｋｉが示す値を順次判別する(ステップＳ３)。前記判別の結果、ビットｋｉのビット値が「０」である場合、演算制御部１４は、第１の演算となる「Ｔ＝Ｓ＋Ｔ」および「Ｓ＝２Ｓ」の演算を行うよう楕円曲線演算部１２に指示し（ステップＳ４）、また、ビットｋｉのビット値が「１」である場合、第２の演算となる「Ｓ＝Ｓ＋Ｔ」および「Ｔ＝２Ｔ」の演算を行うよう指示する（ステップＳ５）。このような演算指示を、ループ処理により、ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０の順に行う（ステップＳ６）。
【００２９】
楕円曲線演算部１２は、演算制御部１４からの演算指示に基づいて、記憶部１１の変数Ｓおよび変数Ｔに関する演算を順次行い、それらの結果を、各変数に対応する記憶領域１１ａおよび記憶領域１１ｂに供給する。そして、ビット列ｋの全てのビットｋｉについての演算が完了したとき（ステップＳ２：ＹＥＳ）、出力部１５は、スカラ倍演算「ｋＧ」により記憶領域１１ｂに格納されている最終的な演算結果を出力する（ステップＳ７）。これを以って、演算処理装置１０１の演算処理が完了する。
【００３０】
具体例１の演算処理装置１０１によれば、楕円曲線暗号方式の暗号化処理および復号化処理の際、鍵情報となるビット列ｋの全てのビットｋｉ（ｉ＝ｎ−１、ｎ−２、・・・、１、０）を参照し、その中に含まれる鍵部分のビット長：ｍに依存しないｎ回のループ処理を行う。従って、たとえ電力解析によりループ処理の合計回数：ｎが検知されても、鍵部分に対する処理回数：ｍは検出されないことから、当該鍵部分のビット長：ｍの推測を防止することができる。これにより、楕円曲線暗号方式を利用したデバイスの安全性を高めることが可能となる。
【００３１】
〈具体例２〉
図３は、本発明に係る演算処理装置の具体例２の構成を示すブロック図である。
具体例２の演算処理装置１０２は、電子署名の機能を果たすＩＣカードのＬＳＩに搭載され、ＲＳＡ（Rivest−Shamir−Adleman）暗号方式のような、べき乗剰余演算を用いた公開鍵暗号方式の暗号化処理および復号化処理を行う。本具体例の演算処理装置１０２は、例えば暗号化処理においては、平文を示す乗法群に含まれる元ｇに対して、指数値ｋを鍵情報とし正の整数ｐを法とする、べき乗剰余演算（ｇｋ  ｍｏｄ  ｐ）を行い、その演算結果を暗号化情報として出力する。
【００３２】
演算処理装置１０２は、図３に示すように、乗法群の元ｇを入力する乗法元入力部２０と、該乗法元入力部からの元ｇおよび後述する単位元「１」を保持する記憶部２１とを備える。記憶部２１には、元ｇを初期値とする変数Ｔを保持する記憶領域２１ａ、および、単位元「１」を初期値とする変数Ｓを保持する記憶領域２１ｂが設けられている。
【００３３】
演算処理装置１０２は、さらに、記憶部２１の変数Ｓおよび変数Ｔに関する後述する剰余乗算演算を行う剰余乗算演算部２２と、前記指数値をビット数ｎで表すビット列ｋを入力するビット列入力部となる指数入力部２３と、ビット列ｋを構成する各ビットｋｉ（ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０）について各ビット値を判別し、該判別した値に対し予め関連付けられている後述する第１の演算および第２の演算を剰余乗算演算部２２に指示する演算制御部２４と、この演算制御部２４の最終的な演算結果を暗号化情報または復号化情報として出力する出力部２５とを備える。指数入力部２３が入力するビット列ｋは、鍵情報となる指数値がｎビットで２進表示されたものであり、すなわちビット列ｋは鍵長がｎビットである鍵情報を示す。
【００３４】
演算制御部２４は、ビット列ｋの全てのビットｋｉのビット値を判別する毎に、図１０に示すアルゴリズムに沿った剰余乗算演算を剰余乗算演算部２２に指示する。剰余乗算演算部２２は、前記指示に基づき、ビットｋｉの参照毎に得られるＳおよびＴの値を用いて、正の整数ｐを法とする「ＳＴ  ｍｏｄ  ｐ」および「Ｓ２（Ｔ２）  ｍｏｄ  ｐ」を演算し、最終的に「ｇｋ  ｍｏｄ  ｐ」の値を導出する。
【００３５】
また、当該アルゴリズムによれば、変数Ｓの初期値として、乗法の単位元である「１」が設定されていることから、ビットｋｉが実質的な鍵部分の先頭ビットを示すまでの演算処理においては、具体例１の楕円曲線演算部１２における演算と同様に、複数回のループ処理が行われても変数Ｓおよび変数Ｔの値を初期値から他の値に推移させることはない。
【００３６】
演算処理装置１０２の動作を図４に示すフローチャートに沿って説明する。ここでは、演算処理装置１０２が暗号化処理を行う例を示す。
指数入力部２３には、鍵情報である指数値ｋ、すなわちｎ個のビットｋｉ（ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０）からなるビット列ｋが入力され、また、記憶部２１には、予め、変数Ｔの初期値である元ｇが乗法元入力部２０から記憶領域２１ａに入力され、変数Ｓの初期値である単位元「１」が記憶領域２１ｂに入力される（ステップＳ１１）。
【００３７】
演算制御部２４は、指数入力部２３から入力されたビット列ｋについて、その先頭ビットｋｎ−１から最終ビットｋ０まで順次検知すると共に（ステップＳ１２：ＮＯ）、各ビットｋｉが示す値を順次判別する(ステップＳ１３)。前記判別の結果、ビットｋｉのビット値が「０」である場合、演算制御部２４は、第１の演算となる「Ｔ＝Ｓ＊Ｔ」および「Ｓ＝Ｓ２」の演算を行うよう剰余乗算演算部２２に指示し（ステップＳ１４）、また、ビットｋｉのビット値が「１」である場合、第２の演算となる「Ｓ＝Ｓ＊Ｔ」および「Ｔ＝Ｔ２」の演算を行うよう指示する（ステップＳ１５）。このような演算指示を、ループ処理により、ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０の順に行う（ステップＳ１６）。
【００３８】
剰余乗算演算部２２は、演算制御部２４からの演算指示に基づいて、記憶部２１の変数Ｓおよび変数Ｔに関する演算を順次行い、それらの結果を、当該各変数に対応する記憶領域２１ａおよび記憶領域２１ｂに供給する。そして、ビット列ｋの全てのビットｋｉについての演算が完了したとき（ステップＳ１２：ＹＥＳ）、出力部２５は、べき乗剰余演算「ｇｋ  ｍｏｄ  ｐ」により記憶領域２１ｂに格納されている最終的な演算結果を暗号化情報として出力し、演算処理を終了する（ステップＳ１７）。
【００３９】
具体例２の演算処理装置１０２によれば、べき乗剰余演算を用いた暗号化処理および復号化処理を行う際、前記した具体例１の演算処理装置１０１と同様に、鍵情報となるビット列ｋの全てのビットｋｉ（ｉ＝ｎ−１、ｎ−２、・・・、１、０）を参照し、その中に含まれる鍵部分のビット長：ｍに依存しないｎ回のループ処理を行う。従って、たとえループ処理の合計回数：ｎが検知されても、その中に含まれる鍵部分に対する処理回数：ｍは検出されないことから、当該鍵部分のビット長：ｍの推測を防止することができる。これにより、ＲＳＡ暗号方式を利用したデバイスの安全性を高めることが可能となる。
【００４０】
〈具体例３〉
図５は、本発明に係る演算処理装置の具体例３の構成を示すブロック図である。
具体例３の演算処理装置１０３は、具体例１の演算処理装置１０１と同様に楕円曲線暗号方式の暗号化処理および復号化処理に用いられ、具体例１の楕円曲線演算部１２と同様な機能を果たす楕円曲線演算部３２が、演算制御部３４の指示に基づいて楕円曲線演算を行う。
【００４１】
本具体例の演算処理装置１０３における記憶部３１の記憶領域３１ａおよび記憶領域３１ｂのそれぞれにはインデックスが付与されており、記憶領域３１ａにｔ［１］、記憶領域３１ｂにｔ［０］が与えられている。演算制御部３４は、これらのインデックスを用いて、後述する第１の演算および第２の演算を行うべく、図１１に示すアルゴリズムに沿った演算を行うよう楕円曲線演算部３２に指示する。
【００４２】
演算処理装置１０３の動作を図６に示すフローチャートに沿って説明する。
スカラ値入力部３３には、鍵情報となるスカラ値ｋ、すなわちｎ個のビットｋｉ（ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０）からなるビット列ｋが入力され、また、記憶部３１には、予め、インデックスｔ［１］の初期値である元Ｇが加法元入力部３０から記憶領域３１ａに入力され、インデックスｔ［０］の初期値である単位元「０」が記憶領域３１ｂに入力される（ステップＳ２１）。
【００４３】
演算制御部３４は、スカラ値入力部３３から入力されたビット列ｋについて、その先頭ビットｋｎ−１から最終ビットｋ０まで順次検知し（ステップＳ２２：ＮＯ）、検知した各ビット毎に「ｔ［１−ｋｉ］＝ｔ［０］＋ｔ［１］」および「ｔ［ｋｉ］＝２ｔ［ｋｉ］」の演算を行うよう楕円曲線演算部３２に指示する（ステップＳ２３）。このステップＳ２３において、ビットｋｉ＝０の場合に指示する演算が第１の演算であり、ビットｋｉ＝１の場合の演算が第２の演算である。このような演算指示を、ループ処理により、ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０の順に行う（ステップＳ２４）。
【００４４】
楕円曲線演算部３２は、演算制御部３４からの前記した演算指示に基づいて、インデックスｔ［１］およびｔ［０］に関する演算を順次行う。そして、ビット列ｋの全てのビットｋｉについての演算が完了したとき（ステップＳ２２：ＹＥＳ）、出力部３５は、スカラ倍演算「ｋＧ」により記憶領域３１ｂのインデックスｔ［０］に格納されている最終的な演算結果を出力する（ステップＳ２５）。これを以って、演算処理装置１０３の演算処理が完了する。
【００４５】
具体例３の演算処理装置１０３によれば、具体例１の演算処理装置１０１による効果と同様な効果を得ることができ、さらに、楕円曲線演算を行うためのアルゴリズムにインデックスを用いることから、ビットｋｉが示す値に対応した条件分岐処理を行うことなくループ処理を実行することができる。これにより、デバイスの暗号処理における安全性を強化することができる。
【００４６】
〈具体例４〉
図７は、本発明に係る演算処理装置の具体例４の構成を示すブロック図である。
具体例４の演算処理装置１０４は、具体例２の演算処理装置１０２と同様にＲＳＡ暗号方式の暗号化処理および復号化処理に用いられ、具体例２の剰余乗算演算部２２と同様な機能を果たす剰余乗算演算部４２が、演算制御部３４の指示に基づいて剰余乗算演算を行う。
【００４７】
演算処理装置１０４における記憶部４１の記憶領域４１ａおよび記憶領域４１ｂのそれぞれには、前記した具体例３の記憶部３１と同様にインデックスが付与されており、記憶領域４１ａにはｔ［１］、記憶領域４１ｂにはｔ［０］が与えられている。演算制御部４４は、これらのインデックスを用いて後述する第１の演算および第２の演算を行うべく、図１２に示すアルゴリズムに沿った演算を行うよう剰余乗算演算部４２に指示する。
【００４８】
具体例４の演算処理装置１０４の動作を図８に示すフローチャートに沿って説明する。ここでは、演算処理装置１０４が暗号化処理を行う例を示す。
指数入力部４３には、鍵情報である指数値ｋ、すなわちｎ個のビットｋｉ（ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０）からなるビット列ｋが入力され、また、記憶部４１には、予め、インデックスｔ［１］の初期値である元ｇが乗法元入力部４０から記憶領域４１ａに入力され、インデックスｔ［０］の初期値である単位元「１」が記憶領域４１ｂに入力される（ステップＳ３１）。
【００４９】
演算制御部４４は、指数入力部４３から入力されたビット列ｋについて、その先頭ビットｋｎ−１から最終ビットｋ０まで順次検知し（ステップＳ３２：ＮＯ）、検知した各ビット毎に「ｔ［１−ｋｉ］＝ｔ［０］＊ｔ［１］」および「ｔ［ｋｉ］＝ｔ［ｋｉ］２」の演算を行うよう剰余乗算演算部４２に指示する（ステップＳ３３）。このステップＳ３３において、ビットｋｉ＝０の場合に指示する演算が第１の演算であり、ビットｋｉ＝１の場合の演算が第２の演算である。このような演算指示を、ループ処理により、ｋｎ−１、ｋｎ−２、・・・、ｋ１、ｋ０の順に行う（ステップＳ３４）。
【００５０】
剰余乗算演算部４２は、演算制御部４４からの前記した演算指示に基づいて、インデックスｔ［１］およびｔ［０］に関する剰余乗算演算を順次行う。そして、ビット列ｋの全てのビットｋｉについての演算が完了したとき（ステップＳ３２：ＹＥＳ）、出力部４５は、べき乗剰余演算「ｇｋ  ｍｏｄ  ｐ」により記憶領域４１ｂのインデックスｔ［０］に格納されている最終的な演算結果を暗号化情報として出力し、演算処理を終了する（ステップＳ３５）。
【００５１】
具体例４の演算処理装置１０４によれば、具体例２の演算処理装置１０２による効果と同様な効果を得ることができ、さらに、剰余乗算演算を行うためのアルゴリズムにインデックスを用いることから、具体例３の演算処理装置１０３と同様に、ビットｋｉが示す値に対応した条件分岐処理を行うことなくループ処理を実行することができる。これにより、デバイスの暗号処理における安全性を強化することができる。
【００５２】
前記した各具体例では、本発明に係る演算処理装置が、電子署名の機能を果たすＩＣカードのＬＳＩに適用された例を示したが、本発明の適用範囲はこれに限定されず、例えば、送信側で情報を暗号化して送信した後、受信側で当該情報を復号化して利用する、いわゆる秘密通信である暗号通信の際の暗号処理に用いることができる。
【００５３】
【発明の効果】
本発明に係る演算処理装置によれば、公開鍵暗号方式の暗号処理の際に、いずれのデバイスに対しても、ビット列の全てのビットを参照して演算のループ処理を行うことから、たとえ電力解析によりループ処理の合計回数が検知されても、当該ビット列に含まれる実質的な鍵部分のビット長が推測されることを防止できる。これにより、公開鍵暗号方式を利用したデバイスの安全性を高めることが可能となる。
【図面の簡単な説明】
【図１】本発明に係る演算処理装置の具体例１の構成を示すブロック図である。
【図２】具体例１の演算処理装置の動作を説明するためのフローチャートである。
【図３】本発明に係る演算処理装置の具体例２の構成を示すブロック図である。
【図４】具体例２の演算処理装置の動作を説明するためのフローチャートである。
【図５】本発明に係る演算処理装置の具体例３の構成を示すブロック図である。
【図６】具体例３の演算処理装置の動作を説明するためのフローチャートである。
【図７】本発明に係る演算処理装置の具体例４の構成を示すブロック図である。
【図８】具体例４の演算処理装置の動作を説明するためのフローチャートである。
【図９】具体例１の演算処理装置のアルゴリズムを説明するための説明図である。
【図１０】具体例２の演算処理装置のアルゴリズムを説明するための説明図である。
【図１１】具体例３の演算処理装置のアルゴリズムを説明するための説明図である。
【図１２】具体例４の演算処理装置のアルゴリズムを説明するための説明図である。
【図１３】従来の演算処理装置のアルゴリズムを説明するための説明図である。
【符号の説明】
１０１  演算処理装置
１０  加法元入力部
１１  記憶部
１１ａ、１１ｂ  記憶領域
１２  楕円曲線演算部
１３  スカラ値入力部
１４  演算制御部
１５  出力部
【図１】
2004198566.tif 000003
【図２】
2004198566.tif 000004
【図３】
2004198566.tif 000005
【図４】
2004198566.tif 000006
【図５】
2004198566.tif 000007
【図６】
2004198566.tif 000008
【図７】
2004198566.tif 000009
【図８】
2004198566.tif 000010
【図９】
2004198566.tif 000011
【図１０】
2004198566.tif 000012
【図１１】
2004198566.tif 000013
【図１２】
2004198566.tif 000014
【図１３】
2004198566.tif 000015