JP2016009114A - データ処理装置及び復号処理方法 - Google Patents

Abstract

【課題】任意の公開鍵ｅに対して、べき乗剰余１回分の時間でフォルトアタック対策の検算を行う。
【解決手段】Ｙ＝Ｘ^ｄｍｏｄＮで表されるべき乗剰余演算において、ｄの２の補数をｄ’とし、ｎをｄのビット数とするとき、Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、Ｃ１＝Ｘ^ｄｍｏｄＮ及びＴ＝Ｘ^２＾^ｎｍｏｄＮを演算し、Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し、一致であればＣ１の値をＹとし、不一致であればエラーとする処理を行う。上記べき乗剰余演算はＲＳＡの復号処理を、中国人剰余定理を用いて行う場合のべき乗剰余演算に適用する。
【選択図】図１

Description

本発明は、公開鍵暗号の一つであるＲＳＡ（Rivest Shamir Adleman）の中国人剰余定理（ＣＲＴ：Chinese remainder theorem）に対するフォルトアタック（ＦＡ：Fault Attack）対策に関し、例えば、ＩＣカード、車載マイコンシステム、ＩＯＴ（Internet of Things）などに代表されるセキュリティ機能搭載製品及びセキュリティ機能搭載システムに適用して有効な技術に関する。

ＲＳＡでは復号処理を高速に行うため中国人剰余定理が用いられている。一方、ＲＳＡ等の暗号アルゴリズム実行中に鍵など秘密情報を暴き出す様々な攻撃手法が提案されている。その中で強力なものとして、フォルトアタックがある。この方法は計算実行中に何らかの方法で誤りを発生させ、この時の計算結果と正しく動作した時の計算結果から鍵情報を特定するものである。

＜ＲＳＡ＞
ＲＳＡとは、公開鍵をｅ、ｎとし、秘密鍵をｆとし、平文をＺとし、暗号文をＸとすると、次の計算式
Ｘ＝Ｚ^ｅｍｏｄＭ、
で暗号化する。また、次の式
Ｚ＝Ｘ^ｆｍｏｄＭ、
で復号する。

ここで秘密の素数をｐ，ｑとすると、次の関係
１＝ｅ×ｆｍｏｄ｛（ｐ−１）（ｑ−１）｝、
Ｍ＝ｐ×ｑ、
が成り立つ。

＜中国人剰余定理＞
上記復号の処理に中国人剰余定理を用いる場合には次の計算式
Ｄｐ＝ｆｍｏｄ（ｐ−１）、
Ｄｑ＝ｆｍｏｄ（ｑ−１）、
Ｘｐ＝Ｘ^Ｄｐｍｏｄｐ、
Ｘｑ＝Ｘ^Ｄｑｍｏｄｑ、
ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐ、
Ｚ＝ｗ×ｑ＋Ｘｑ、
によって平文Ｚを得ることができる。

＜フォルトアタック＞
フォルトアタックとは暗号処理実行中に、電源やクロックへのノイズ注入及び回路へのレーザ照射により、故障状態を引き起こした時に出力される値を正しい値と比較して鍵などの秘密情報を暴き出す攻撃手法である。

＜中国人剰余定理に対するフォルトアタック＞
中国人剰余定理に対するフォルトアタックでは、以下に示すようにＸｐ又はＸｑを求めるべき乗剰余演算の実行時に故障状態を引き起こす。例えば図６に例示するようにＸｐを求めるべき乗剰余演算の実行タイミングに合わせて故障状態を引き起こす。故障状態を引き起こして誤りを生じた演算結果Ｚ’と正しい演算結果Ｚから次の計算式
Ｚ−Ｚ’＝（ｗ−ｗ’）×ｑ、
ｑ＝ｇｃｄ｛ｐｑ、（ｗ−ｗ’）×ｑ｝＝ｇｃｄ（Ｍ，Ｚ−Ｚ’）、
で示すようにして、既知値のＭと出力値の差Ｚ−Ｚ’との最大公約数としてｑが求められる。ｑからｐ及びｆを求めることができるので、秘密鍵ｆが攻撃者に暴かれてしまうことになる。

＜フォルトアタック対策＞
消費電力のような物理情報を解析して秘密鍵ｆを不正に暴く攻撃手法への対策として例えば特許文献１に記載された技術がある。また、電力消費の解析や故障注入による攻撃に対する対策として特許文献２に記載された技術がある。しかしながら、何れも中国人剰余定理による復号アルゴリズムに着目したフォルトアタックへの対策は考慮されていない。本発明者は以下の対策について検討した。

第１の対策は、ＸｐとＸｑの計算をそれぞれ２回実施し、２回とも同じ値になることが確認できたらＺの値を出力する。すなわち、検算をして結果が合わなければ攻撃を受けたとみなし、Ｚの値を出力しない。この方法では、ＸｐとＸｑに係るべき乗剰余演算を４回行う必要がある。

第２の対策は、中国人剰余定理を用いて計算した結果Ｚを再度暗号化（Ｘ＝Ｚ^ｅｍｏｄＭ）し、入力Ｘと同じ値になることを確認できたらＺを出力し、そうでなければＺを出力しない。ｅ＝６５５３７がよく使われるので、この場合は再度の暗号化の計算時間は長くなく、その計算時間が実用に耐えないことはない。

特開２０１４−８１４２６号公報 特開２０１０−２７７０８５号公報

本発明者はフォルトアタック対策の上記第１の対策及び第２の対策について検討した。第１の対策では、ＸｐとＸｑに係るべき乗剰余演算を４回行う必要があり、無視し得ない程に計算時間が増大してしまう。第２の対策は暗号強度を高くするために任意値のｅを使用しようとする場合にｅの値が大きくなると、計算処理時間が長くなり過ぎて実用に耐えないことが想定される。

上記並びにその他の課題と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。

本願において開示される実施の形態のうち代表的なものの概要を簡単に説明すれば下記の通りである。

すなわち、Ｙ＝Ｘ^ｄｍｏｄＮで表されるべき乗剰余演算において、ｄの２の補数をｄ’とし、ｎをｄのビット数とするとき、Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、Ｃ１＝Ｘ^ｄｍｏｄＮ及びＴ＝Ｘ^２＾^ｎｍｏｄＮを演算し、Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し、一致であればＣ１の値をＹとし、不一致であればエラーとする処理を行う。上記べき乗剰余演算はＲＳＡの復号処理を、中国人剰余定理を用いて行う場合のべき乗剰余演算に適用する。本明細書中において上記「Ｘ^２＾^ｎ」におけるべき乗数「^２＾^ｎ」は「２^ｎ」を意味する。即ち、本明細書では便宜上記号＾をべき乗記号として用いることがある。

本願において開示される実施の形態のうち代表的なものによって得られる効果を簡単に説明すれば下記の通りである。

すなわち、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。

図１は公開鍵暗号の一つであるＲＳＡの中国人剰余定理に対するフォルトアタックに対抗するためのべき乗剰余演算を実行可能にする演算器２を備えたデータ処理装置における当該べき乗剰余演算の機能を論理記述によって例示した説明図である。 図２は図１の論理記述に対する具体的な演算処理を例示するフローチャートである。 図３は２進数標記でｄ＝１０１１１００１_２、ｎ＝８の場合について図２のステップＳ２乃至Ｓ９の処理例を示す説明図である。 図４はデータ処理装置の具体例としてプロセッサのプログラム処理で演算器の機能を実現する構成を示すブロック図である。 図５はデータ処理装置の別の具体例として専用ハードウェアで演算器の機能を実現する構成を示すブロック図である。 図６は国人剰余定理の処理においてＸｐ又はＸｑを求めるべき乗剰余演算の実行時に故障状態を引き起こすフォルトアタックについて例示する説明図である。 図７は通常のバイナリ法によるべき乗剰余演算の論理記述を例示する説明図である。 図８は図７の論理記述を実現するための演算処理フローを例示するフローチャートである。 図９は２進数標記でｄ＝１０１１１００１_２、ｎ＝８を一例とする場合について図７のべき乗剰余演算の論理記述の処理例を示す説明図である。

１．実施の形態の概要
先ず、本願において開示される実施の形態について概要を説明する。実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。

〔１〕＜フォルトアタックに対抗するべき乗剰余演算可能なデータ処理装置＞
データ処理装置（１）は中国人剰余定理を用いてＲＳＡの復号処理を行う演算器（２）を有する。前記演算器は、Ｙ＝Ｘ^ｄｍｏｄＮで表されるべき乗剰余演算において、ｄの２の補数をｄ’とし、ｎをｄのビット数として、Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、Ｃ１＝Ｘ^ｄｍｏｄＮ及びＴ＝Ｘ^２^^ｎｍｏｄＮを演算し（Ｓ２〜Ｓ９）、Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し（Ｓ１０，Ｓ１１）、一致であればＣ１の値をＹとし（Ｓ１２）、不一致であればエラーとする（Ｓ１３）処理を行う。

これによれば、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。したがって、注入された故障に応ずるべき乗剰余演算の誤った結果をそのまま用いた復号を阻むことができ、そのための演算処理時間の短縮に寄与することができる。換言すれば、フォルトアタックによる秘密鍵の不正な暴露を防止するための演算処理時間の短縮を実現する。

〔２〕＜フォルトアタック検出時のエラー応答＞
項１において、エラーとする処理はＣ１の値以外の値を返す処理である。

これによれば、中国人剰余定理による復号アルゴリズムに着目したフォルトアタック自体が無効化されることはもとより、不正アクセス者がそのことを認知できなくなる。

〔３〕＜プロセッサのプログラム処理で演算器の機能を実現＞
項１において、前記演算器は、ワークメモリ（４）と、前記ワークメモリを用いてプログラム処理を行うプロセッサ（３）と、前記プロセッサの動作プログラムを格納するプログラムメモリ（５）とを含む。

これによれば、演算器の機能実現に柔軟性を持たせることができる。

〔４〕＜専用ハードウェアで演算器の機能を実現＞
項１において、前記演算器は、プログラム処理を行うプロセッサ（１３）から発行された所定の演算コマンドに基づいてＹ＝Ｘ^ｄｍｏｄＮで表されるべき乗剰余演算の演算制御と演算を行うべき乗剰余演算回路である。

これによれば、演算器による復号処理の更なる高速化に資することができる。

〔５〕＜フォルトアタックに対抗するべき乗剰余演算方法＞
復号処理方法は、中国人剰余定理を用いてＲＳＡの復号をデータ処理によって行う方法であって、前記データ処理は２回のべき乗剰余演算を含。Ｙ＝Ｘ^ｄｍｏｄＮで表される夫々のべき乗剰余演算において、ｄの２の補数をｄ’とし、ｎをｄのビット数とし、Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、Ｃ１＝Ｘ^ｄｍｏｄＮ及びＴ＝Ｘ^２^^ｎｍｏｄＮを演算し（Ｓ２〜Ｓ９）、Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し（Ｓ１０，Ｓ１１）、一致であればＣ１の値をＹとし（Ｓ１２）、不一致であればエラーとする（Ｓ１３）処理を行う。

これによれば、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。したがって、注入された故障に応ずるべき乗剰余演算の誤った結果をそのまま用いた復号を阻むことができ、そのための演算処理時間の短縮に寄与することができる。換言すれば、フォルトアタックによる秘密鍵の不正な暴露を防止するための演算処理時間の短縮を実現する。

〔６〕＜フォルトアタック検出時のエラー応答＞
項５において、エラーとする処理はＣ１の値以外の値を返す処理である。

これによれば、中国人剰余定理による復号アルゴリズムに着目したフォルトアタック自体が無効化されることはもとより、不正アクセス者がそのことを認知できなくなる。

〔７〕＜フォルトアタックに対抗するべき乗剰余演算可能なデータ処理装置＞
データ処理装置（１）は、秘密鍵ｆ、ｐ及びｑを用いてＲＳＡ暗号による暗号文Ｘを平文Ｚに復号する演算器（２）を有する。前記演算器による演算処理は、ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄpｍｏｄｐを求める第１処理と、ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含む。前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、ｄの２の補数をｄ’とし、ｎをｄのビット数とするとき、Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、Ｃ１＝Ｘ^ｄｍｏｄＮ及びＴ＝Ｘ^２^^ｎｍｏｄＮを演算し（Ｓ２〜Ｓ９）、Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し（Ｓ１０，Ｓ１１）、一致であればＣ１の値をＹとし（Ｓ１２）、不一致であればエラーとする（Ｓ１３）処理、を含む。

これによれば、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。したがって、注入された故障に応ずるべき乗剰余演算の誤った結果をそのまま用いた復号を阻むことができ、そのための演算処理時間の短縮に寄与することができる。換言すれば、フォルトアタックによる秘密鍵の不正な暴露を防止するための演算処理時間の短縮を実現する。

〔８〕＜フォルトアタック検出時のエラー応答＞
項７において、エラーとする処理はＣ１の値以外の値を返す処理である。

これによれば、中国人剰余定理による復号アルゴリズムに着目したフォルトアタック自体が無効化されることはもとより、不正アクセス者がそのことを認知できなくなる。

〔９〕＜プロセッサのプログラム処理で演算器の機能を実現＞
項７において、前記演算器は、ワークメモリ（４）と、前記ワークメモリを用いてプログラム処理を行うプロセッサ（３）と、前記プロセッサの動作プログラムを格納するプログラムメモリ（５）とを含む。

これによれば、演算器の機能実現に柔軟性を持たせることができる。

〔１０〕＜専用ハードウェアで演算器の機能を実現＞
項７において、前記演算器は、プログラム処理を行うプロセッサ（１３）から発行された所定の演算コマンドに基づいて前記第１処理乃至第４処理の演算制御と演算を行うべき乗剰余演算回路である。

これによれば、演算器による復号処理の更なる高速化に資することができる。

〔１１〕＜フォルトアタックに対抗するべき乗剰余演算方法＞
復号処理方法は、データ処理装置に秘密鍵ｆ、ｐ及びｑと共にＲＳＡ暗号による暗号文Ｘを与えて平文Ｚに復号する方法であって、ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄpｍｏｄｐを求める第１処理と、ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含む。前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、ｄの２の補数をｄ’とし、ｎをｄのビット数とするとき、Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、Ｃ１＝Ｘ^ｄｍｏｄＮ及びＴ＝Ｘ^２^^ｎｍｏｄＮを演算し（Ｓ２〜Ｓ９）、Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し（Ｓ１０，Ｓ１１）、一致であればＣ１の値をＹとし（Ｓ１２）、不一致であればエラーとする（Ｓ１３）処理、を含む。

これによれば、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。したがって、注入された故障に応ずるべき乗剰余演算の誤った結果をそのまま用いた復号を阻むことができ、そのための演算処理時間の短縮に寄与することができる。換言すれば、フォルトアタックによる秘密鍵の不正な暴露を防止するための演算処理時間の短縮を実現する。

〔１２〕＜フォルトアタック検出時のエラー応答＞
項１１において、エラーとする処理はＣ１の値以外の値を返す処理である。

これによれば、中国人剰余定理による復号アルゴリズムに着目したフォルトアタック自体が無効化されることはもとより、不正アクセス者がそのことを認知できなくなる。

〔１３〕＜フォルトアタックに対抗するべき乗剰余演算可能なデータ処理装置＞
データ処理装置（１）は、秘密鍵ｆ、ｐ及びｑを用いてＲＳＡ暗号による暗号文Ｘを平文Ｚに復号する演算器（２）を有する。前記演算器による演算処理は、ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄpｍｏｄｐを求める第１処理と、ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含む。前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、
ＴレジスタにＸを初期設定する処理（Ｓ１）、
ｄのビットを順番に参照し、参照する度にＴレジスタの値の二乗に対してＮを法とする剰余でＴレジスタを書き換える処理（Ｓ５）、
参照したｄのビットが初めて１になるまでの間は、ｄのビットの参照の都度、Ｔレジスタの値でＣ０レジスタとＣ１レジスタを書き換える処理（Ｓ４）、
参照したｄのビットが一旦１になってからは、ｄのビットの１を参照する度にＣ１レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ１レジスタを書き換え（Ｓ８）、ｄのビットの０を参照する度にＣ０レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ０レジスタを書き換える処理（Ｓ７）、及び
ｄの全てのビットを参照したとき、Ｃ０レジスタの値とＣ１レジスタの値との積に対してＮを法とする剰余がＴレジスタの値に一致するか否かを判別し（Ｓ１０，Ｓ１１）、一致であればＣ１レジスタの値をＹとし（Ｓ１２）、不一致であればエラーとする（Ｓ１３）処理、を含む。

これによれば、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。したがって、注入された故障に応ずるべき乗剰余演算の誤った結果をそのまま用いた復号を阻むことができ、そのための演算処理時間の短縮に寄与することができる。換言すれば、フォルトアタックによる秘密鍵の不正な暴露を防止するための演算処理時間の短縮を実現する。

〔１４〕＜フォルトアタック検出時のエラー応答＞
項１３において、エラーとする処理はＣ１レジスタの値以外の値を返す処理である。

これによれば、中国人剰余定理による復号アルゴリズムに着目したフォルトアタック自体が無効化されることはもとより、不正アクセス者がそのことを認知できなくなる。

〔１５〕＜プロセッサのプログラム処理で演算器の機能を実現＞
項１３において、前記演算器（２）は、前記Ｔレジスタ、前記Ｃ０レジスタ及び前記Ｃ１レジスタとして利用可能にされると共に前記値ｄの格納領域にされるワークメモリ（４）と、前記ワークメモリを用いてプログラム処理を行うプロセッサ（３）と、前記プロセッサの動作プログラムを格納するプログラムメモリ（５）とを含む。

これによれば、演算器の機能実現に柔軟性を持たせることができる。

〔１６〕＜専用ハードウェアで演算器の機能を実現＞
項１３において、前記演算器は、所定の演算コマンドに基づいて演算を行うべき乗剰余演算回路であり、コマンドレジスタ（２０）、パラメータレジスタ（２２，２３）、制御回路（２１）及び演算回路（２４）を有する。前記コマンドレジスタはプログラム処理装置から前記所定の演算コマンドが書き込まれる。前記パラメータレジスタは前記Ｔレジスタ、前記Ｃ０レジスタ及び前記Ｃ１レジスタに割り当てられると共に、前記値ｄの設定領域を有する。前記制御回路は前記コマンドレジスタに書き込まれた所定の演算コマンド及び前記パラメータレジスタに設定された値ｄを参照することにより、前記Ｔレジスタ、前記Ｃ０レジスタ及び前記Ｃ１レジスタを用いて前記演算回路に前記第１処理乃至第４処理の演算を実行させる。

これによれば、演算器による復号処理の更なる高速化に資することができる。

〔１７〕＜フォルトアタックに対抗するべき乗剰余演算方法＞
復号処理方法は、データ処理装置に秘密鍵ｆ、ｐ及びｑと共にＲＳＡ暗号による暗号文Ｘを与えて平文Ｚに復号する方法であって、ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄpｍｏｄｐを求める第１処理と、ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含む。前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、
ＴレジスタにＸを初期設定する処理（Ｓ１）、
ｄのビットを順番に参照し、参照する度にＴレジスタの値の二乗に対してＮを法とする剰余でＴレジスタを書き換える処理（Ｓ５）、
参照したｄのビットが初めて１になるまでの間は、ｄのビットの参照の都度、Ｔレジスタの値でＣ０レジスタとＣ１レジスタを書き換える処理（Ｓ４）、
参照したｄのビットが一旦１になってからは、ｄのビットの１を参照する度にＣ１レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ１レジスタを書き換え（Ｓ８）、ｄのビットの０を参照する度にＣ０レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ０レジスタを書き換える（Ｓ７）処理、及び
ｄの全てのビットを参照したとき、Ｃ０レジスタの値とＣ１レジスタの値との積に対してＮを法とする剰余がＴレジスタの値に一致するか否かを判別し（Ｓ１０，Ｓ１１）、一致であればＣ１レジスタの値をＹとし（Ｓ１２）、不一致であればエラーとする（Ｓ１３）処理、を含む。

これによれば、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。したがって、注入された故障に応ずるべき乗剰余演算の誤った結果をそのまま用いた復号を阻むことができ、そのための演算処理時間の短縮に寄与することができる。換言すれば、フォルトアタックによる秘密鍵の不正な暴露を防止するための演算処理時間の短縮を実現する。

〔１８〕＜フォルトアタック検出時のエラー応答＞
項１７において、エラーとする処理はＣ１レジスタの値以外の値を返す処理である。

これによれば、中国人剰余定理による復号アルゴリズムに着目したフォルトアタック自体が無効化されることはもとより、不正アクセス者がそのことを認知できなくなる。

２．実施の形態の詳細
実施の形態について更に詳述する。

＜中国人剰余定理を用いてＲＳＡの復号処理を行う演算器＞
図１にはＩＣカード、車載マイコンシステム、ＩＯＴなどに代表されるセキュリティ機能搭載製品及びセキュリティ機能搭載システムに適用されるデータ処理装置１が例示される。このデータ処理装置は、公開鍵暗号の一つであるＲＳＡの中国人剰余定理に対するフォルトアタックに対抗するためのべき乗剰余演算を実行可能にする演算器２を備える。図１には演算器２においてそのようなべき乗剰余演算の機能が論理記述によって例示される。

ここで、ＲＳＡ、中国人剰余定理については前述した通りであり、以下の説明はそれを前提とする。データ処理装置１は前述したＲＳＡ及び中国人剰余定理を適用した所定のアルゴリズムに従って、暗号文Ｘを復号して平分Ｚを得る演算処理を行う。平文Ｚを暗号化して暗号文Ｘを得る演算処理がサポートされていても良いことは言うまでもない。

公開鍵をｅ、ｎとし、秘密鍵をｆとし、平文をＺとし、暗号文をＸとするとき、ＲＳＡにおける復号の演算処理は、次の演算式
Ｚ＝Ｘ^ｆｍｏｄＭ
によって実現される。ここで秘密の素数をｐ，ｑとすると、次の関係
１＝ｅ×ｆｍｏｄ｛（ｐ−１）（ｑ−１）｝、
Ｍ＝ｐ×ｑ、
が成り立つ。この関係を考慮して、上記復号の演算処理に中国人剰余定理を用いると、次の計算式
Ｄｐ＝ｆｍｏｄ（ｐ−１）、
Ｄｑ＝ｆｍｏｄ（ｑ−１）、
Ｘｐ＝Ｘ^Ｄｐｍｏｄｐ…第１処理、
Ｘｑ＝Ｘ^Ｄｑｍｏｄｑ…第２処理、
ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐ…第３処理、
Ｚ＝ｗ×ｑ＋Ｘｑ…第４処理、
によって平文Ｚを得ることができる。

図１の演算器２に示された論理記述は、上記第１処理又は第２処理に対して誤り注入によるフォルトアタックが行われたとき当該第１処理又は第２処理の演算結果を返さないようにするためのものである。図１の論理記述は、上記第１処理と第２処理の双方のべき乗剰余演算式を便宜的にＹ＝Ｘ^ｄｍｏｄＮとして図示してある。即ち、第１処理Ｘｐ＝Ｘ^Ｄｐｍｏｄｐの場合にはＸｐ＝Ｙ、Ｄｐ＝ｄ、ｐ＝Ｎとされる。第２処理Ｘｑ＝Ｘ^Ｄｑｍｏｄｑの場合にはＸｐ＝Ｙ，Ｄｑ＝ｄ，ｑ＝Ｎとされる。図１において記号＊は乗算を意味する。ｋ＝０〜ｎ−１はｎビット長を有するｄの下位側からのビット番号を意味する。

図１の演算器２に示された論理記述は、上記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、ｄの２の補数をｄ’とし、ｎをｄのビット数とするとき、Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、
Ｃ１＝Ｘ^ｄｍｏｄＮ、
Ｔ＝Ｘ^２^^ｎｍｏｄＮ、
を演算し、Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し、一致であればＣ１の値をＹとし、不一致であればエラーとする処理を意味するものである。以下この処理について具体的に説明する。

＜Ｙ＝Ｘ^ｄｍｏｄＮの演算処理方法＞
図２には図１の論理記述に対する具体的な演算処理フローが例示される。Ｙ＝Ｘ^ｄｍｏｄＮの演算処理を行うために、Ｔレジスタ、Ｃ０レジスタ、Ｃ１レジスタ、ｋレジスタ、ｄレジスタが用意される。図２の標記上、Ｔレジスタ、Ｃ０レジスタ、Ｃ１レジスタ、ｋレジスタ、ｄレジスタを単に記号←と共にＴ，Ｃ０，Ｃ１，ｋ，ｄとして簡略的に図示してある。ｋレジスタは、ｄレジスタにセットされた値ｄの下位側からのビット番号０〜ｎ−１の値と採る。Ｔレジスタ、Ｃ０レジスタ、Ｃ１レジスタには中間値Ｔ，Ｃ０，Ｃ１が一時的に保持される。

先ず、Ｎレジスタに値Ｎがセットされ、Ｔレジスタに暗号文Ｘが初期設定され、ｋレジスタに初期値０がセットされ、ｄレジスタに値ｄがセットされる（Ｓ１）。

次いで、ｋレジスタにセットされたビット番号の値ｄ[k]＝１が既に発生したか否かの判別が行われ（Ｓ２）、既に一度も発生指定なければ今回ｄ[k]＝０か否か（Ｓ３）、即ち今回初めてｄ[k]＝１が発生したか（Ｓ２＝Ｎｏ，Ｓ３＝Ｎｏ）、或いは今回までに未だｄ[k]＝１が発生していないか（Ｓ２＝Ｎｏ，Ｓ３＝Ｙｅｓ）、の判別が行われる。未だｄ[k]＝１が発生していなくても、また、初めてｄ[k]＝１が発生した場合にもレジスタＴをＴ＊ＴｍｏｄＮの演算結果で書き換えると共に、レジスタｋの値をｋ＋１に更新する（Ｓ５）。初めてｄ[k]＝１が発生した場合にはレジスタＣ０にそのときのＴの値を初期設定し、レジスタＣ１にそのときのＴの値を初期設定する（Ｓ４）。

ステップＳ２においてｋレジスタにセットされたビット番号の値ｄ[k]＝１が既に発生した後の場合には（Ｓ２＝Ｙｅｓ）、今回ｄ[k]＝０であれば（Ｓ６＝Ｙｅｓ）、レジスタＣ０をＣ０＊ＴｍｏｄＮの演算結果で書き換え（Ｓ７）、今回ｄ[k]＝１であれば（Ｓ６＝Ｎｏ）、レジスタＣ１をＣ１＊ＴｍｏｄＮの演算結果で書き換え（Ｓ８）。ステップＳ７，Ｓ８の次にステップＳ５の処理を行う。

ステップＳ５の次に、値ｄの各ビットの論理値判別が最上位ビットまで完了したか（ｋ＜ｎ−１）を判別し（Ｓ９）、最上位ビットの達するまで上記処理Ｓ２乃至Ｓ８を繰返す。

上記ステップＳ２乃至Ｓ８はべき乗剰余演算に対するバイナリ法による処理の変形として位置付けることが可能である。通常のバイナリ法では図７の論理記述及び図８の演算処理フローに例示されるように、ｄの各ビットの値が１の場合は中間値ＣとＴの双方を更新し、０の場合はＴの値だけを更新し、最後にＣに残った値が演算結果のＹとなる。２進数標記でｄ＝１０１１１００１_２、ｎ＝８を一例とすると、図９にはｋ＝０〜7の各ビットの値ｄ[ｋ]に応ずる中間値Ｃに係るべき乗、Ｔに係るべき乗が図示されており、例えばｋ＝４のとき（ｄ[ｋ］＝１）、中間値Ｃに係るべき乗はＸ^９＋Ｘ^１６＝Ｘ^２５になる。

通常のバイナリ法に対して図２のステップＳ２乃至Ｓ９の処理は、ｄの各ビットの値が１の場合は中間値Ｃ１とＴの双方を更新し、０の場合は中間値Ｃ０とＴの双方を更新する。前者はべき指数ｄに対するべき乗剰余演算Ｃ１＝Ｘ^ｄｍｏｄＮに対応され、後者はｄの２の補数ｄ’に対するべき乗剰余演算Ｃ０＝Ｘ^ｄ’ｍｏｄＮに対応される。特に、ｄのビットが最初に値１になる当該ビットに係る補数ｄ’のビットは値１になるので、当該ビットが最初に値１になったときは、ステップＳ４に示されるようにＣ１だけでなくＣ０にもレジスタＴの値がセットされるようになっている。

Ｓ２乃至Ｓ９の処理例として図９と同じく２進数標記でｄ＝１０１１１００１_２、ｎ＝８の場合について図３に示す。図３でも便宜上Ｃ０，Ｃ１，Ｔの夫々についてべき乗だけを図示しており、Ｔに係るべき乗値はｋが一つ進む毎にＸ^２倍される。Ｃ０に係るべき乗値は、ｄ[ｋ］＝１のときには直前値、ｄ[ｋ］＝０のときには直前のＣ０に係るべき乗値と直前のＴに係るべき乗値との積になる。Ｃ１に係るべき乗値は、ｄ[ｋ］＝０のときには直前値、ｄ[ｋ］＝１のときには直前のＣ１に係るべき乗値と直前のＴに係るべき乗値との積になる。ｄとｄ’は補数関係になっているから、ｋ毎にＣ０に係るべき乗値とＣ１に係るべき乗値との積はＴに係るべき乗値に等しくなる。

ｄの全てのビットを順次参照しながらステップＳ２乃至Ｓ９の処理を完了したとき、Ｃ０レジスタの値とＣ１レジスタの値との積に対してＮを法とする剰余でＣ０レジスタを書き換え（Ｓ１０），Ｃ０レジスタの値がＴレジスタの値に一致するか否かを判別する（Ｓ１１）。Ｙ＝Ｘ^ｄｍｏｄＮで表されるべき乗剰余演算の処理中にレーザ照射などによって積極的に誤りが注入されていなければ、ステップＳ１１の判別においてＣ０レジスタの値はＴレジスタの値に一致される。図３の例に従えば、Ｘ^７１×Ｘ^１８５＝Ｘ^２５６になる。

ステップＳ１１の判別が一致であればＹ＝Ｃ１を演算結果として出力する（Ｓ１２）。不一致の場合にはエラー処理を行う（Ｓ１３）。

このように、ｄの下位ビットから順番に演算し、初めてｄのビットが１になるとき、レジスタＣ０とＣ１にＴと同じ値を書き込み、ｄの各ビットが０の場合はレジスタ値Ｃ０とＴを更新し、１の場合はレジスタ値Ｃ１とＴを更新する。ｄ’をｄの２の補数とすると計算終了時にはＣ０＝Ｘ^ｄ’ｍｏｄＮ、Ｃ１＝Ｘ^ｄｍｏｄＮ、Ｔ＝Ｘ^２^^ｎｍｏｄＮとなり、Ｃ０×Ｃ１ｍｏｄＮ＝Ｘ^{（ｄ＋ｄ’）}ｍｏｄＮ＝Ｘ^２^^ｎｍｏｄＮ＝Ｔであるから、ＴとＣ０×Ｃ１ｍｏｄＮが同じ値になればＣ１を計算結果Ｙとして出力し、そうでなければ攻撃を受けたとみなしエラー処理を行う。エラー処理としてはＹを出力しないこと、或いはＣ１以外の任意の値を出力する処理とする。

この演算処理方法によれば、ＲＳＡの復号処理に適用する中国人剰余定理の処理においてべき乗剰余演算のタイミングで誤りが注入されたか否かを、暗号化に任意の公開鍵ｅが用いられている場合にも、検算だけのためのべき乗剰余演算や検算だけのための暗号化演算を追加することなく、復号のための本来のべき乗剰余演算を通じて検出することができる。したがって、注入された故障に応ずるべき乗剰余演算の誤った結果をそのまま用いた復号を阻むことができ、そのための演算処理時間の短縮に寄与することができる。換言すれば、任意の公開鍵ｅに対して、べき乗剰余１回分の時間でフォルトアタック対策の検算を行うことができ、フォルトアタックによる秘密鍵の不正な暴露を防止するための演算処理時間の短縮を実現する。

＜データ処理装置の具体例＞
図４にはデータ処理装置１の具体例が示される。図４に示されるデータ処理装置１はプロセッサのプログラム処理で演算器２の機能を実現する構成とされる。演算器２は、例えばワークメモリ４と、前記ワークメモリ４を用いてプログラム処理を行うプロセッサ３と、前記プロセッサ３の動作プログラムを格納するプログラムメモリ５とを含む。プロセッサ３は少なくとも中央処理装置を供え、プログラムメモリ５から順次フェッチした命令を解読して、中国人剰余定理を用いてＲＳＡの上述した復号処理の演算シーケンスの制御と演算処理を実行する。このとき、ワークメモリ４はＴレジスタ、Ｃ０レジスタ、Ｃ１レジスタ、Ｎレジスタ及びｄレジスタの記憶領域、並びにその他ワーク領域とされ、プロセッサ３がアクセスして利用する。データ処理装置１はその他に、外部インタフェース回路６やアクセラレータ７などを供える。プロセッサ３は中央処理装置のほかにキャッシュメモリ、アドレス変換バッファ、浮動小数点演算ユニットなど、その他の回路ユニットを供えてよいことは言うまでもない。

データ処理装置１はＣＭＯＳ集積回路製造技術などによって１個の半導体基板に単体ＬＳＩとして構成することが可能である。或いは、複数個の半導体チップから成るマルチチップの半導体集積回路モジュール、又は回路基板に複数個の半導体デバイスを実装してシステム構成することも可能である。また、演算器２も複数個の半導体デバイスによってマルチチップで構成することも可能である。

プロセッサ３のプログラム処理で演算器２の機能を実現することにより、演算器２の機能実現に柔軟性を持たせることができる。

図５にはデータ処理装置１の別の具体例が示される。図５に示されるデータ処理装置１は、専用ハードウェアで演算器２の機能を実現する構成とされる。演算器２は、所定の演算コマンドに基づいて演算を行うべき乗剰余演算回路を構成する。べき乗剰余演算回路を構成する演算器２は、コマンドレジスタ２０、パラメータレジスタ２２，２３、制御回路２１及び演算回路２４を有する。コマンドレジスタ２０はプログラム処理装置としてのプロセッサ１３から所定の演算コマンドが書き込まれる。プロセッサ１３はプログラムメモリ１５に格納されているプログラムをフェッチして実行する。前記パラメータレジスタ２３にはＴレジスタ、Ｃ０レジスタ、Ｃ１レジスタ、Ｎレジスタに割り当てられる。パラメータレジスタ２２は値ｄの設定領域とされる。演算回路２４は算術論理演算回路や乗算回路等を有する。制御回路２１は前記コマンドレジスタ２０に書き込まれた所定の演算コマンド及び前記パラメータレジスタ２２に設定された値ｄを参照することにより、Ｔレジスタ、Ｃ０レジスタ、Ｃ１レジスタ、Ｎレジスタを用いて、中国人剰余定理を用いてＲＳＡの上述した復号処理の演算処理を演算回路２４に実行させる。データ処理装置１はその他に、外部インタフェース回路１６やアクセラレータ１７などを供える。プロセッサ３は中央処理装置のほかにキャッシュメモリ、アドレス変換バッファ、浮動小数点演算ユニットなど、その他の回路ユニットを供えてよいことは言うまでもない。

図５のデータ処理装置１はＣＭＯＳ集積回路製造技術などによって１個の半導体基板に単体ＬＳＩとして構成することが可能である。べき乗剰余演算回路を構成する演算器２は一つのアクセラレータとみなすことも可能である。図５のデータ処理装置１は、複数個の半導体チップから成るマルチチップの半導体集積回路モジュール、又は回路基板に複数個の半導体デバイスを実装してシステム構成することも可能である。また、演算器２も複数個の半導体デバイスによってマルチチップで構成することも可能である。

これによれば、専用ハードウェア化された演算器２を用いることによって復号処理の更なる高速化に資することができる。

本発明は上記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。

例えば、ｄのビットの論理値を判定しながらべき乗剰余演算を行うバイナリ手法として右バイナリ法に基づいてこれを発展させる手法に限定されず、左バイナリ法に基づいてこれを発展させる手法にも応用することが可能であることは言うまでもない。

また、図２の処理フローは一例であり、その細部において適宜変形可能であることは言うまでもない。

１ データ処理装置
２ 演算器
３ プロセッサ
４ ワークメモリ
５ プログラムメモリ
１３ プロセッサ
１５ プログラムメモリ
１６ 外部インタフェース回路
１７ アクセラレータ
２０ コマンドレジスタ
２２，２３ パラメータレジスタ
２４ 演算回路

Claims (18)

1. 中国人剰余定理を用いてＲＳＡの復号処理を行う演算器を有し、
   前記演算器は、Ｙ＝Ｘ^ｄｍｏｄＮで表されるべき乗剰余演算において、
   ｄの２の補数をｄ’とし、ｎをｄのビット数として、
   Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、
   Ｃ１＝Ｘ^ｄｍｏｄＮ、及び
   Ｔ＝Ｘ^２＾^ｎｍｏｄＮを演算し（^２＾^ｎは２^ｎを意味する）、
   Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し、一致であればＣ１の値をＹとし、不一致であればエラーとする処理を行う、データ処理装置。
2. 請求項１において、エラーとする処理はＣ１の値以外の値を返す処理である、データ処理装置。
3. 請求項１において、前記演算器は、ワークメモリと、前記ワークメモリを用いてプログラム処理を行うプロセッサと、前記プロセッサの動作プログラムを格納するプログラムメモリとを含む、データ処理装置。
4. 請求項１において、前記演算器は、プログラム処理を行うプロセッサから発行された所定の演算コマンドに基づいてＹ＝Ｘ^ｄｍｏｄＮで表されるべき乗剰余演算の演算制御と演算を行うべき乗剰余演算回路である、データ処理装置。
5. 中国人剰余定理を用いてＲＳＡの復号をデータ処理によって行う復号処理方法であって、
   前記データ処理は２回のべき乗剰余演算を含み、
   Ｙ＝Ｘ^ｄｍｏｄＮで表される夫々のべき乗剰余演算において、
   ｄの２の補数をｄ’とし、ｎをｄのビット数とし、
   Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、
   Ｃ１＝Ｘ^ｄｍｏｄＮ、及び
   Ｔ＝Ｘ^２＾^ｎｍｏｄＮを演算し、
   Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し、一致であればＣ１の値をＹとし、不一致であればエラーとする処理を行う、復号処理方法。
6. 請求項５において、エラーとする処理はＣ１の値以外の値を返す処理である、復号処理方法。
7. 秘密鍵ｆ、ｐ及びｑを用いてＲＳＡ暗号による暗号文Ｘを平文Ｚに復号する演算器を有し、
   前記演算器による演算処理は、
   ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄｐｍｏｄｐを求める第１処理と、
   ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、
   Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、
   ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含み、
   前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、ｄの２の補数をｄ’とし、ｎをｄのビット数とするとき、
   Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、
   Ｃ１＝Ｘ^ｄｍｏｄＮ、及び
   Ｔ＝Ｘ^２＾^ｎｍｏｄＮを演算し、
   Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し、一致であればＣ１の値をＹとし、不一致であればエラーとする処理、を含むデータ処理装置。
8. 請求項７において、エラーとする処理はＣ１の値以外の値を返す処理である、データ処理装置。
9. 請求項７において、前記演算器は、ワークメモリと、前記ワークメモリを用いてプログラム処理を行うプロセッサと、前記プロセッサの動作プログラムを格納するプログラムメモリとを含む、データ処理装置。
10. 請求項７において、前記演算器は、プログラム処理を行うプロセッサから発行された所定の演算コマンドに基づいて前記第１処理乃至第４処理の演算制御と演算を行うべき乗剰余演算回路である、データ処理装置。
11. データ処理装置に秘密鍵ｆ、ｐ及びｑと共にＲＳＡ暗号による暗号文Ｘを与えて平文Ｚに復号する復号処理方法であって、
    ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄｐｍｏｄｐを求める第１処理と、
    ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、
    Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、
    ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含み、
    前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、ｄの２の補数をｄ’とし、ｎをｄのビット数とするとき、
    Ｃ０＝Ｘ^ｄ’ｍｏｄＮ、
    Ｃ１＝Ｘ^ｄｍｏｄＮ、及び
    Ｔ＝Ｘ^２＾^ｎｍｏｄＮを演算し、
    Ｃ０の値とＣ１の値との積に対してＮを法とする剰余がＴの値に一致するか否かを判別し、一致であればＣ１の値をＹとし、不一致であればエラーとする処理、を含む復号処理方法。
12. 請求項１１において、エラーとする処理はＣ１の値以外の値を返す処理である、復号処理方法。
13. 秘密鍵ｆ、ｐ及びｑを用いてＲＳＡ暗号による暗号文Ｘを平文Ｚに復号する演算器を有し、
    前記演算器による演算処理は、
    ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄｐｍｏｄｐを求める第１処理と、
    ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、
    Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、
    ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含み、
    前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、
    ＴレジスタにＸを初期設定する処理、
    ｄのビットを順番に参照し、参照する度にＴレジスタの値の二乗に対してＮを法とする剰余でＴレジスタを書き換える処理、
    参照したｄのビットが初めて１になるまでの間は、ｄのビットの参照の都度、Ｔレジスタの値でＣ０レジスタとＣ１レジスタを書き換える処理、
    参照したｄのビットが一旦１になってからは、ｄのビットの１を参照する度にＣ１レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ１レジスタを書き換え、ｄのビットの０を参照する度にＣ０レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ０レジスタを書き換える処理、及び
    ｄの全てのビットを参照したとき、Ｃ０レジスタの値とＣ１レジスタの値との積に対してＮを法とする剰余がＴレジスタの値に一致するか否かを判別し、一致であればＣ１レジスタの値をＹとし、不一致であればエラーとする処理、を含むデータ処理装置。
14. 請求項１３において、エラーとする処理はＣ１レジスタの値以外の値を返す処理である、データ処理装置。
15. 請求項１３において、前記演算器は、
    前記Ｔレジスタ、前記Ｃ０レジスタ及び前記Ｃ１レジスタとして利用可能にされると共に前記値ｄの格納領域にされるワークメモリと、
    前記ワークメモリを用いてプログラム処理を行うプロセッサと、
    前記プロセッサの動作プログラムを格納するプログラムメモリとを含む、データ処理装置。
16. 請求項１３において、前記演算器は、所定の演算コマンドに基づいて演算を行うべき乗剰余演算回路であり、コマンドレジスタ、パラメータレジスタ、制御回路及び演算回路を有し、
    前記コマンドレジスタはプログラム処理装置から前記所定の演算コマンドが書き込まれ、
    前記パラメータレジスタは前記Ｔレジスタ、前記Ｃ０レジスタ及び前記Ｃ１レジスタに割り当てられると共に、前記値ｄの設定領域を有し、
    前記制御回路は前記コマンドレジスタに書き込まれた所定の演算コマンド及び前記パラメータレジスタに設定された値ｄを参照することにより、前記Ｔレジスタ、前記Ｃ０レジスタ及び前記Ｃ１レジスタを用いて前記演算回路に前記第１処理乃至第４処理の演算を実行させる、データ処理装置。
17. データ処理装置に秘密鍵ｆ、ｐ及びｑと共にＲＳＡ暗号による暗号文Ｘを与えて平文Ｚに復号する復号処理方法であって、
    ｆをｐ−１で割った余りＤｐを用いてＸｐ＝Ｘ^Ｄｐｍｏｄｐを求める第１処理と、
    ｆをｑ−１で割った余りＤｑを用いてＸｑ＝Ｘ^Ｄｑｍｏｄｑを求める第２処理と、
    Ｘｐ−Ｘｑの値とｐを法とするｑの逆元ｑ^−１とを用いて、ｗ＝（Ｘｐ−Ｘｑ）×ｑ^−１ｍｏｄｐを求める第３処理と、
    ｗ×ｑ＋Ｘｐによって平文Ｚを求める第４処理とを含み、
    前記第１処理と第２処理の双方のべき乗剰余演算式をＹ＝Ｘ^ｄｍｏｄＮと表したとき、この式を実現する処理は、
    ＴレジスタにＸを初期設定する処理、
    ｄのビットを順番に参照し、参照する度にＴレジスタの値の二乗に対してＮを法とする剰余でＴレジスタを書き換える処理、
    参照したｄのビットが初めて１になるまでの間は、ｄのビットの参照の都度、Ｔレジスタの値でＣ０レジスタとＣ１レジスタを書き換える処理、
    参照したｄのビットが一旦１になってからは、ｄのビットの１を参照する度にＣ１レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ１レジスタを書き換え、ｄのビットの０を参照する度にＣ０レジスタの値とＴレジスタの値の積に対してＮを法とする剰余でＣ０レジスタを書き換える処理、及び
    ｄの全てのビットを参照したとき、Ｃ０レジスタの値とＣ１レジスタの値との積に対してＮを法とする剰余がＴレジスタの値に一致するか否かを判別し、一致であればＣ１レジスタの値をＹとし、不一致であればエラーとする処理、を含む復号処理方法。
18. 請求項１７において、エラーとする処理はＣ１レジスタの値以外の値を返す処理である、復号処理方法。

Images