(57)【特許請求の範囲】
【請求項１】
公開鍵暗号において，秘密指数dと, 公開鍵nと, 暗号文cとから，平文mを復号する，公開鍵暗号における復号装置であって，
前記暗号文cをランダム化された暗号文tに変換する処理部と，
ランダム化された暗号文tをランダム化された平文uに変換する処理部と，
ランダム化された平文uを平文mに変換する処理部と，
べき剰余計算部と，を有し，
前記ランダム化された暗号文tに変換する処理部は，
乱数rを生成する処理部と，
前記乱数rと前記乱数rより導出された整数sを用いてランダム化された暗号文tに変換する処理部とを含み，
前記ランダム化された平文uに変換する処理部は，
前記秘密指数dより導出された値を用いてランダム化された平文uを計算する処理部を含み，
前記平文mに変換する処理部は，
ランダム化された平文uに前記整数sを乗ずる処理部を含む
ことを特徴とする公開鍵暗号における復号装置。
【請求項２】
請求項１記載の公開鍵暗号における復号装置であって，さらに，
モジュラー乗算部を備え，
前記乱数rより導出された前記整数ｓとして，前記べき剰余計算部により計算されるre-1を用い，
前記ランダム化された暗号文tに変換する処理部は，前記モジュラー乗算部を用いて，srを前記暗号文cに乗ずる処理部を含む
ことを特徴とする公開鍵暗号における復号装置。
【請求項３】
請求項１または２に記載の公開鍵暗号における復号装置であって，さらに，
前記ランダム化された平文uを計算する処理部は，
前記べき剰余計算部を用いて，前記秘密指数dより導出された値としてd-1を用い，前記ランダム化された暗号文tのd-1乗を計算する処理部を含む
ことを特徴とする公開鍵暗号における復号装置。
【請求項４】
請求項１記載の公開鍵暗号における復号装置であって，さらに，
モジュラー乗算部を備え，
前記暗号文tに変換する処理部は，
前記モジュラー乗算部を用いて，前記乱数rより導出された値としてr2を用い，r2を前記暗号文cに乗ずる処理部を含む
ことを特徴とする公開鍵暗号における復号装置。
【請求項５】
請求項１記載の公開鍵暗号における復号装置であって，さらに，
前記公開鍵nは，p mod 4 = q mod 4 = 3となる素因数p,qを含み，
前記ランダム化された平文uを計算する処理部は，
前記べき剰余計算部を用いて前記秘密指数dから(p-3)/4および(q-3)/4を導出する処理部と，
ランダム化された暗号文tの(p-3)/4乗を計算する処理部と，
ランダム化された暗号文tの(q-3)/4乗を計算する処理部と，を含む
ことを特徴とする公開鍵暗号における復号装置。
【請求項６】
請求項４に記載の公開鍵暗号における復号装置であって，さらに，
前記平文mに変換する処理部における前記整数sとして前記r2を用いる
ことを特徴とする公開鍵暗号における復号装置。
【請求項７】
公開鍵暗号を用いた電子署名において，秘密指数dと, 公開鍵nと, データcとから，署名データmを生成する，公開鍵暗号を用いた署名作成装置であって，
前記データcをランダム化されたデータtに変換する処理部と，
ランダム化されたデータtをランダム化された署名uに変換する処理部と，
ランダム化された署名uを署名mに変換する処理部と，を有し，
前記ランダム化されたデータtに変換する処理部は，
乱数rを生成する処理部と，
前記乱数rと前記乱数rより導出された整数sを用いてランダム化されたデータtに変換する処理部とを含み，
前記ランダム化された署名uに変換する処理部は，
前記秘密指数dより導出された値を用いてランダム化された署名uを計算する処理部を含み，
前記署名mに変換する処理部は，
ランダム化された署名uに前記整数sを乗ずる処理部を含む
ことを特徴とする公開鍵暗号を用いた署名作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はセキュリティ技術に係り、特にべき乗剰余算を用いたデータ処理方法に関する。
【背景技術】
【０００２】
ＲＳＡ暗号はRivest, Shamir, Adleman により提案された公開鍵暗号である。公開鍵暗号には、公開鍵と呼ばれる一般に公開してよい情報と、秘密鍵と呼ばれる秘匿しなければならない秘密情報がある。与えられたデータの暗号化や署名の検証には公開鍵を用い、与えられたデータの復号化や署名の作成には秘密鍵を用いる。
【０００３】
ＲＳＡ暗号における秘密鍵は、大きな素数p,qおよび整数d、公開鍵は、整数n,eである。これらの数値の間には、
n=pq                        （式1）
ed=1 mod Phi(n)            （式2）
という関係が成り立っている。ただし、Phi(n)はオイラー関数であり、整数nと互いに素な正整数の個数を表す。n=pqの場合は、
Phi(n) = (p-1)(q-1)        （式3）
となる。式1、式2より、任意の整数zに対して、
zed = z mod n               （式4）
という関係が成り立つ。この性質を利用することにより、暗号化・復号化等を達成することができる。すなわち、暗号化や署名の検証においては、
xe mod n                    （式5）
が計算され、復号化や署名の作成においては、
yd mod n                    （式6）
が計算される。ここでx,yは、入力データを表す整数である。この計算はべき乗剰余算と呼ばれる。
【０００４】
一般に、処理速度の向上のために、eの値は小さくとる。通常用いられる値は
e=65537  (=216+1)          （式7）
である。
【０００５】
また、ＲＳＡ暗号の高速化手法として中国人剰余定理（以下、ＣＲＴという）が知られている。一方、ＲＳＡ暗号を性能向上させた様々な公開鍵暗号が提案されている。非特許文献４〜７に記載されている、Multi-prime RSA, Multi-exponent RSA, Rabin cryptosystem, HIME(R)等がその例である。これらの暗号系へもＣＲＴは適用可能である。
【０００６】
ＲＳＡ暗号等を暗号装置として実装した場合、暗号処理に要する計算時間や電力消費量、電磁波等が観測可能である。それらの情報をもとに暗号装置内部に格納されている秘密鍵等の秘密情報を暴く方法が提案されている。この方法はサイドチャネル攻撃と呼ばれている。サイドチャネル攻撃は非特許文献１に記載されている。
【０００７】
ＣＲＴを用いたＲＳＡ暗号へのサイドチャネル攻撃が非特許文献２に記載されている。この攻撃は、Novakの攻撃と呼ばれている。この攻撃は、上記Multi-prime RSA, Multi-exponent RSA, Rabin cryptosystem, HIME(R)等の公開鍵暗号へも拡張可能である。
【０００８】
一方、サイドチャネル攻撃を防ぐ手法として、逆元演算を用いる方法が非特許文献３に記載されている。しかしながら、逆元演算は多くの計算量を必要とする計算である。そのため、この方法はサイドチャネル攻撃を防ぐことはできるが、多くの計算時間を必要とする。また、逆元演算をあらかじめ計算し、その値をメモリに格納しておくこともできるが、その場合は多くのメモリを使用する。
【０００９】
【非特許文献１】P.C. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis,” in the proceedings of CRYPTO 1999, Lecture Note in Computer Science 1666, Springer-Verlag, pp.388-397, (1999).
【００１０】
【非特許文献２】R. Novak, “SPA-Based Adaptive Chosen-Ciphertext Attack on RSA Implementation,” in the proceedings of 2002 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2002), Lecture Note in Computer Science 2274, Springer-Verlag, pp.252-262, (2002).
【非特許文献３】P.C. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,” in the proceedings of CRYPTO 1996, Lecture Note in Computer Science 1109, Springer-Verlag, pp.104-113, (1996).
【非特許文献４】Public-Key Cryptography Standards, PKCS # 1,Amendment 1: Multi-Prime RSA, RSA Laboratories, (2000)
【非特許文献５】T. Takagi, “Fast RSA-type cryptosystem modulo pkq”, in the proceedings of  CRYPTO 1998, Lecture Note in Computer Science 1462, Springer-Verlag, pp.318-326, (1998).
【非特許文献６】D. Boneh, “Simplified OAEP for the RSA and RabinFunctions,” in the proceedings of CRYPTO 2001, Lecture Note in Computer Science 2139, pp.275-291, (2001).
【非特許文献７】M. Nishioka, H. Satoh, and K. Sakurai, ”Design and Analysis of Fast Provably Secure Public-Key Cryptosystems Based on a Modular Squaring,” in the proceedings of The 4th International Conference on Information Security and Cryptology (ICISC 2001), Lecture Note in Computer Science 2288, pp.81-102, (2001).
【発明の開示】
【発明が解決しようとする課題】
【００１１】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証のために暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも高速性やメモリ使用量などがある。特に、スマートカード（ICカードともいう）等においては利用可能なリソースは少なく、限られたリソース内で暗号処理を最適化する必要がある。
【００１２】
上記技術は、サイドチャネル攻撃を防ぐ方法としては有効であるが、高速性やメモリ使用量に関しては考慮されていない。
【課題を解決するための手段】
【００１３】
本発明は、サイドチャネル攻撃を防ぐことのできる、かつ高速性やメモリ使用量に優れるべき乗剰余計算方法を提供する。
【００１４】
本発明は、公開鍵暗号において、秘密指数d, 公開鍵n, 暗号文cから、平文mを復号する復号方法であって、上記暗号文cをランダム化された暗号文tに変換するステップと、ランダム化された暗号文tをランダム化された平文uに変換するステップと、ランダム化された平文uを平文mに変換するステップと、を有するものであって、上記ランダム化された暗号文tに変換するステップは、乱数rを生成するステップと、上記乱数ｒと上記乱数rより導出された整数sを用いてランダム化された暗号文tに変換するステップとを含み、上記ランダム化された平文uに変換するステップは、上記秘密指数dより導出された値を用いてランダム化された平文uを計算するステップを含み、上記平文mに変換するステップは、ランダム化された平文uに上記整数sを乗ずるステップとを含むことを特徴とする。
【００１５】
本発明は、また、上記乱数rより導出された前記整数ｓとして、re-1を用い、上記暗号文tに変換するステップは、srを暗号文cに乗ずるステップを含む用に構成しても良い。
【００１６】
本発明は、また、上記ランダム化された平文uに変換するステップにおける上記秘密指数dより導出された値としてd-1を用い、上記ランダム化された平文uに変換するステップは、ランダム化された暗号文tのd-1乗を計算するステップを含むように構成してもよい。
【００１７】
本発明は、また、上記暗号文tに変換するステップにおける上記乱数rより導出された値として、r4を用い、上記暗号文tに変換するステップは、r4を暗号文cに乗ずるステップを含むように構成してもよい。
【００１８】
本発明は、また、上記公開鍵nは、
p mod 4 = q mod 4 = 3となる素因数p,qを含み、上記ランダム化された平文uに変換するステップにおける上記秘密指数dより導出された値として
(p-3)/4および(q-3)/4を用い、上記ランダム化された平文uに変換するステップは、ランダム化された暗号文tの
(p-3)/4乗を計算するステップと、ランダム化された暗号文tの
(q-3)/4乗を計算するステップと、を含むように構成してもよい。
【００１９】
本発明は、また、上記平文mに変換するステップにおける整数sとしてr2を用いるように構成してもよい。
【００２０】
本発明は、また、公開鍵暗号を用いた電子署名において、秘密指数d, 公開鍵n, データcから、署名データmを生成する署名作成方法であって、上記データcをランダム化されたデータtに変換するステップと、ランダム化されたデータtをランダム化された署名uに変換するステップと、ランダム化された署名uを署名mに変換するステップと、を有するように構成してもよい。
【００２１】
本発明は、また、上記ランダム化されたデータtに変換するステップは、乱数rを生成するステップと、上記乱数rと上記乱数rより導出された整数sを用いてランダム化されたデータtに変換するステップとを含み、上記ランダム化された署名uに変換するステップは、上記秘密指数dより導出された値を用いてランダム化された署名uを計算するステップを含み、上記署名mに変換するステップは、ランダム化された署名uに上記整数sを乗ずるステップとを含むように構成してもよい。
【００２２】
以上のように、本発明のべき乗剰余計算方法によれば、入力された暗号文はランダム化された暗号文に変換され、ランダム化された平文から平文への変換の際に逆元計算を行なう必要はないため、サイドチャネル攻撃を防ぐことのできる、かつ高速性やメモリ使用量に優れるべき乗剰余計算方法が利用可能になる。
【発明の効果】
【００２３】
本発明によれば、逆元演算を用いることなく、サイドチャネル攻撃に対して安全で、かつ高速性やメモリ使用量に優れる、公開鍵暗号技術における復号または署名作成処理が可能となる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の実施例を図面により説明する。
【００２５】
図１はネットワークによって接続された本発明によるべき乗剰余算の計算法を適用したコンピュータＡ101、コンピュータＢ121がネットワーク142により接続されたシステム構成を示すものである。
【００２６】
図1の暗号通信システムにおけるコンピュータＡ101でデータの暗号化を行なうには、c=me mod nを計算して出力し、コンピュータＢ121で暗号文の復号化を行なうには、cd mod nを計算して出力すればよい。ここでmは暗号化するデータを示す整数、e, nはそれぞれ公開鍵を示す整数、cはデータmに対する暗号文を示す整数、dは秘密鍵を示す整数である。
【００２７】
ネットワーク142には、暗号文cのみ送信され、データmを復元するためには、cd mod nを計算する必要がある。ところが、秘密鍵dはネットワーク142には送信されないため、秘密鍵を保持しているものだけが、データmを復元できることになる。
【００２８】
図１において、コンピュータＡ101は、ＣＰＵ113やコプロセッサ114などの演算装置、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置、コンピュータ外部とのデータ入出力を行なう入出力インタフェース110を装備しており、外部にはコンピュータＡをユーザが操作するためのディスプレイ108、キーボード109、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００２９】
更にコンピュータＡ101は、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置によって、記憶部102を実現し、ＣＰＵ113やコプロセッサ114などの演算装置が、記憶部102に格納されたプログラムを実行することにより、データ処理部112を実現する。
【００３０】
データ処理部112は、本実施形態においては、暗号化処理部112として入力されたデータの暗号化を行なう。
【００３１】
コンピュータＢ121はコンピュータＡ101と同様のハードウェア構成を備える。
【００３２】
更にコンピュータＢ121は、ＲＡＭ123、ＲＯＭ126や外部記憶装置127などの記憶装置によって、記憶部122を実現し、ＣＰＵ133やコプロセッサ134などの演算装置が、記憶部122に格納されたプログラムを実行することにより、データ処理部132を実現する。
【００３３】
データ処理部132は、本実施形態においては、復号化処理部132として機能し、暗号化されたデータである暗号文の復号化を行なう。
【００３４】
なお、上記各プログラムは、予め、上記コンピュータ内の記憶部に格納されていてもよいし、必要なときに、入出力インタフェースと上記コンピュータが利用可能な媒体を介して、他の装置から上記記憶部に導入されてもよい。媒体とは、例えば、入出力インタフェースに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【００３５】
次に、図1のコンピュータＡ101が、入力されたデータを暗号化する場合の動作について説明する。データはディジタルデータであればよく、テキスト、画像、音などの種類は問わない。
【００３６】
暗号化処理部112は、入出力インタフェース110を介して、平文データを受け取ると、入力された平文データのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように平文データを区切る。以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。
【００３７】
次に、暗号化処理部112は、データのビット列によって表される数値mに対して、
べき乗剰余c=me mod nを計算し、暗号化されたデータcを得る。コンピュータＡ101は暗号化処理部112で暗号化された1つ以上の部分データから暗号化された出力データを組み立てる。コンピュータＡ101は暗号化されたデータ141を入出力インタフェース110より出力し、ネットワーク142を介してコンピュータＢ121へ転送する。
【００３８】
次に、コンピュータＢ121が、暗号化されたデータ141を復号化する場合の動作について説明する。
【００３９】
復号化処理部132は、入出力インタフェース130を介して、暗号化されたデータが入力されると、入力された暗号化されたデータのビット長があらかじめ定めたビット長か否かを判断する。あらかじめ定めたビット長よりも長い場合は、あらかじめ定めたビット長となるように暗号化されたデータを区切る。以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。
【００４０】
次に、復号化処理部132は、データのビット列により表される数値cに対して、
べき乗剰余m'=cd mod nを計算し、暗号化される前の部分データmに相当するm'を得る。コンピュータＢ121は、復号化処理部132で復号化された部分データから平文データを組み立て、入出力インタフェース130を介して、ディスプレイ128などから出力する。
【００４１】
次に、コンピュータＢ121が、復号化処理を行う場合の、データ処理部132の処理を詳細に説明する。
【実施例１】
【００４２】
第1実施例では、復号化処理部132として、図2で示されるデータ処理部132の機能ブロックを用いる。データ処理部132は、モジュラー乗算部201、乱数生成部202、汎用べき乗剰余計算部203、定数204からなる。
【００４３】
復号化処理部132が所定のビット長に区切られている暗号文cから、秘密鍵dを用いて、暗号化される前の部分データである平文mを計算する第1の計算方法を、図3を用いて説明する。
【００４４】
復号化処理部132は暗号文cを受け取る。乱数生成部202は、乱数rを生成する（301）。汎用べき乗剰余計算部203は、
re-1 mod nを計算し、sに格納する（302）。モジュラー乗算部201は、
src mod nを計算し、tに格納する（303）。この計算は、モジュラー乗算部201がs, rからsr mod nを計算し、その後 
(sr) c mod nを計算することにより達成できる。汎用べき乗剰余計算部203は、
td-1 modを計算し、uに格納する（304）。モジュラー乗算部201は、
us mod nを計算し、vに格納する（305）。モジュラー乗算部201は、
vc mod nを計算し、m'に格納する。復号化処理部132は、m'を暗号化される前の部分データである平文mとして出力する。平分mから平分データが組み立てられる。
【００４５】
次に中国人剰余定理を用いて汎用べき乗剰余算を高速化する場合の処理について、図4、図5を用いて説明する。この場合、汎用べき乗剰余計算部203はＣＲＴ計算部203として働く。
【００４６】
ＣＲＴ計算部203は、モジュラー乗算部401、モジュラー加減算部402、モジュラー剰余乗算部403、べき乗剰余計算部404、加減乗算部405、定数406からなる。ＣＲＴ計算部203は、整数tと整数dから、整数p,qを用いて、
td mod nを計算する。ここでp,qはnを割りきる素数である。
【００４７】
ＣＲＴ計算部203は、整数tと整数dを受け取る。モジュラー剰余計算部403は、
d mod p-1, d mod q-1 を計算し、dp, dqにそれぞれ格納する（501）。モジュラー剰余計算部403は
t mod p, t mod q を計算し、tp, tqにそれぞれ格納する（502）。べき乗剰余計算部404は、tp dp mod p, tq dq mod qを計算し、それぞれmp, mqに格納する（503）。モジュラー乗算部401およびモジュラー加減算部402は、
(mq-mp)pInv mod qを計算し、hに格納する（504）。この計算は、モジュラー加減算部402が
mq-mp mod qを計算し、モジュラー乗算部401が、その結果にpInvを乗ずる
（すなわち (mq-mp)pInv mod q）ことにより達成できる。加減乗算部405は、mp+phを計算し、mpqに格納する（505）。この計算は、加減乗算部405がphを計算し、その結果にmpを加える（すなわち mp+(ph)）ことにより達成できる。ただし、pInvは、
pInv = p-1 mod q           （式8）
をみたす整数である。pInvは定数406としてＣＲＴ計算部203に格納されている。ＣＲＴ計算部203は、mpqを
td mod nとして出力する（506）。
【００４８】
復号化処理部132の行なう処理により出力されるm'はm'=mとなる。この理由は次の通りである。
m' = vc = usc = td-1sc 
= (src)d-1sc = (rec)d-1re-1c
= cdred-e+e-1 = cd mod n            （式9）
ここで、e,d の定義より、red-1 = 1が成り立つ。cはmを暗号化したものであるので、
cd = m mod n                          （式10）
が成り立つ。したがって、m'=mとなる。
【００４９】
上記の計算方法では、剰余乗算等の演算は用いるが、逆元演算は用いない。したがって、非特許文献３の手法と比べて、高速な計算が可能である。また、eを式7により定めた場合、直接cd mod nを計算する方法と比べると、計算量増加は剰余乗算20回分である。一般に、1024ビットの汎用べき乗剰余算を行なった場合、1500回程度の剰余乗算を必要とするため、上記計算方法の計算量増加は、この値と比べて比較的小さいと言える。
【００５０】
また、上記の計算方法では逆元演算を用いないため、逆元演算をあらかじめ計算し、その値をメモリに格納する、ということを行なう必要がない。そのため、メモリ使用量が少なくてすむ。
【００５１】
また、上記の計算方法は、サイドチャネル攻撃に対する防御に関しても有効である。この理由は次の通りである。上記の計算方法で秘密鍵を用いるのはステップ503のみである。ステップ503の入力である整数tは、入力されたデータcと、ステップ501で生成された乱数rのe乗との乗算結果である。したがって、攻撃者は整数tの値を予測することはできない。Novakの攻撃は、汎用べき乗剰余算に入力される値が攻撃者にとって既知であることを利用しているので、攻撃者はNovakの攻撃を行なうことができない。
【００５２】
以上の通り、上記の計算方法は、サイドチャネル攻撃に有用な情報を与えないため、サイドチャネル攻撃に対して耐性がある。また、逆元演算を用いないため、高速な計算が可能であり、さらに、逆元演算の結果をあらかじめメモリに格納する必要もないため、メモリ使用量も少なくてすむ。
【００５３】
なお、上記の計算方法は、multi-prime RSA や multi-exponent RSA に対しても適用できる。この場合においても、サイドチャネル攻撃に耐性を有し、さらに、逆元演算を用いないため、高速計算可能かつ小メモリとなる。
【００５４】
まず、multi-prime RSA の場合について説明する。
【００５５】
非特許文献４に開示されているように、multi-prime RSAにおける秘密鍵は、大きな素数p,q,rおよび整数d、公開鍵は、整数n,eである。これらの数値の間には、
n = pqr                    （式11）
ed = mod Phi(n)          （式12）
という関係が成り立っている。ここでは、大きな素数を３つとしたが、４つやそれ以上でもよい。式12のnの場合、
Phi(n) = (p-1)(q-1)(r-1)        （式13）
となる。multi-prime RSAにおいても、式4が成立し、そのため、暗号化や署名の検証においては式5が計算され、復号化や署名の作成においては式6が計算される。従って復号化処理を行なう場合、第1の計算方法を用いることにより、サイドチャネル攻撃に耐性を有し、さらに、逆元演算を用いないため、高速計算可能かつ小メモリとなる。
【００５６】
次に中国人剰余定理を用いて汎用べき乗剰余算を高速化する場合の処理について、図4、図6を用いて説明する。この場合、汎用べき乗剰余計算部203はＣＲＴ計算部203として働く。
【００５７】
ＣＲＴ計算部203は、整数tと整数dから、整数p,q,rを用いて、td mod n を計算する。ここで、p,q,rはnを割りきる素数である。
【００５８】
ＣＲＴ計算部203は、整数tと整数dを受け取る。モジュラー剰余計算部403は、
d mod p-1, d mod q-1, d mod r-1 を計算し、dp, dq, dr にそれぞれ格納する（601）。モジュラー剰余計算部403は 
t mod p, t mod q, t mod r を計算し、tp, tq, trにそれぞれ格納する（602）。べき乗剰余計算部404は、
tp dp mod p, tq dq mod q, tr dr mod r を計算し、それぞれ mp, mq, mr に格納する（603）。モジュラー乗算部401およびモジュラー加減算部402は、
(mq-mp)pInv mod q を計算し、hに格納する（604）。この計算は、モジュラー加減算部402が
mq-mp mod q を計算し、モジュラー乗算部401が、その結果にpInvを乗ずる
（すなわち (mq-mp)pInv mod q）ことにより達成できる。ただし、pInvは、式*をみたす整数である。加減乗算部405は、mp+phを計算し、mpqに格納する（605）。この計算は、加減乗算部405がphを計算し、その結果にmpを加える（すなわち mp+(ph)）ことにより達成できる。モジュラー乗算部401およびモジュラー加減算部402は、
(mr-mpq)pqInv mod r を計算し、hに格納する（606）。この計算は、モジュラー加減算部402が
mr-mpq mod r を計算し、モジュラー乗算部401が、その結果にpqInvを乗ずる
（すなわち (mr-mpq)pqInv mod r）ことにより達成できる。ただし、pqInvは、
pqInv = (pq)-1 mod r           （式14）
をみたす整数である。pqInvは定数406として、ＣＲＴ計算部203に格納されている。加減乗算部405は、mpq+pqhを計算し、mpqr に格納する（607）。この計算は、加減乗算部405がpqを計算し、その結果にhを乗じ、さらにその結果にmpqを加える（すなわち mpq+((pq)h)）ことにより達成できる。ＣＲＴ計算部203は、mpqr を 
td mod n として出力する（608）。
【００５９】
次に、multi-exponent RSA の場合について説明する。
【００６０】
非特許文献５に開示されているように、multi-exponent RSAにおける秘密鍵は、大きな素数p,qおよび整数d、公開鍵は、整数n,eである。これらの数値の間には、
n = p2q                    （式15）
ed = mod Phi(n)        （式16）
という関係が成り立っている。ここでは、べき指数を2としたが、3やそれ以上でもよい。式16のnの場合、
Phi(n) = p(p-1)(q-1)          （式17）
となる。multi-exponent RSAにおいても、式4が成立し、そのため、暗号化や署名の検証においては式5が計算され、復号化や署名の作成においては式6が計算される。従って復号化処理を行なう場合、第1の計算方法を用いることにより、サイドチャネル攻撃に耐性を有し、さらに、逆元演算を用いないため、高速計算可能かつ小メモリとなる。
【００６１】
次に中国人剰余定理を用いて汎用べき乗剰余算を高速化する場合の処理について、図4、図7を用いて説明する。この場合、汎用べき乗剰余計算部203はＣＲＴ計算部203として働く。
【００６２】
ＣＲＴ計算部203は、整数tと整数dから、整数p,qを用いて、td mod n を計算する。ここで、p,qはnを割りきる素数であり、さらにnはp2でも割りきれる。
【００６３】
ＣＲＴ計算部203は、整数tと整数dを受け取る。モジュラー剰余計算部403は、
d mod p-1, d mod q-1 を計算し、dp, dq にそれぞれ格納する（701）。モジュラー剰余計算部403は 
t mod p, t mod q を計算し、tp, tq にそれぞれ格納する（702）。べき乗剰余計算部404は、
tp dp-1 mod pを計算し、kに格納する（703）。モジュラー剰余計算部403は、
tp k mod p を計算し、mp に格納する。べき乗剰余計算部404は、
tq dq mod q を計算し、mq に格納する（704）。べき乗剰余計算部404、モジュラー加減算部402、およびモジュラー剰余計算部403は、
c - mp e mod p2 を計算し、gに格納する。モジュラー乗算部401は、
g k eInv mod p2 を計算し、bに格納する。加減乗算部405は、mq +b を計算し、mp2 に格納する（705）。これらの計算は、べき乗剰余計算部404が
mp e mod p2 を計算し、モジュラー剰余計算部403が
c mod p2 を計算し、モジュラー加減算部402がそれらの差分をとる（すなわち 
(c mod p2)  (mp e) mod p2）ことによりgが計算できる。モジュラー乗算部401がg k mod p2 を計算し、その結果にeInv を乗ずる
（すなわち (gk)eInv mod p2）ことによりbが計算できる。その後、加減乗算部405が mq +b を計算することにより、達成できる。ただし、eInvは、
eInv = (e)-1 mod p           （式18）
をみたす整数である。eInvは定数406としてＣＲＴ計算部203に格納されている。モジュラー乗算部401およびモジュラー加減算部402は、
(mq-mp2)p2Inv mod q を計算し、hに格納する（706）。この計算は、モジュラー加減算部402が
mq-mp2 mod q を計算し、モジュラー乗算部401が、その結果にp2Invを乗ずる
（すなわち (mq-mp2)p2Inv mod q）ことにより達成できる。ただし、p2Invは、
p2Inv = (p2)-1 mod r           （式19）
をみたす整数である。p2Invは定数406としてＣＲＴ計算部203に格納されている。加減乗算部405は、mp2+p2hを計算し、mp2qに格納する（707）。この計算は、加減乗算部405が(p2)hを計算し、その結果にmp2を加える（すなわち mp+((p2)h)）ことにより達成できる。ＣＲＴ計算部203は、mp2q を 
td mod n として出力する（708）。
【実施例２】
【００６４】
第2実施例では、Rabin暗号の場合について説明する。
【００６５】
非特許文献６に開示されているように、Rabin暗号における秘密鍵は、大きな素数p,q、公開鍵は、整数n,eである。Rabin暗号の場合は特に
e=2                          （式20）
である。また素数p,qは、
p mod 4 = q mod 4 = 3      （式21）
をみたすように選ばれる。これらの数値の間には、
n = pq                          （式22）
という関係が成り立っている。Rabin暗号の場合、暗号化や署名の検証においては、xの平方
y = x2 mod n                    （式23）
を計算し、復号化や署名の作成においては、式23をみたすxを計算する。そのため、Rabin暗号では、式23をみたす整数が4つ存在し、そのうち適切なものを選択することとなる。
【００６６】
第2実施例では、復号化処理部132として、図8で示されるデータ処理部132の機能ブロックを用いる。データ処理部132は、モジュラー乗算部801、乱数生成部802、汎用べき乗剰余計算部803、定数804、モジュラー加減算部805、加減乗算部806からなる。
【００６７】
復号化処理部132が所定のビット長に区切られている暗号文cから、秘密鍵を用いて、平文mを計算する第2の計算方法を、図9を用いて説明する。
【００６８】
復号化処理部132は暗号文cを受け取る。乱数生成部802は、乱数rを生成する（901）。モジュラー乗算部801は、
r2 mod nを計算し、sに格納する（902）。モジュラー乗算部801は、
s2c mod nを計算し、tに格納する（903）。この計算は、モジュラー乗算部801がsから
s2 mod nを計算し、その後 
(s2) c mod nを計算することにより達成できる。汎用べき乗剰余計算部803は、 
t(p-3)/4 mod p, t(q-3)/4 mod q を計算し、それぞれup, uq格納する（904）。モジュラー乗算部801およびモジュラー加減算部805は、
(uq-up)pInv mod q を計算し、h1に格納する。加減乗算部806は、
up+ph1を計算し、w1に格納する（905）。これらの計算は、モジュラー加減算部805が
uq-up mod q を計算し、モジュラー乗算部801が、その結果にpInvを乗ずる
（すなわち (uq-up)pInv mod q）ことによりh1が計算できる。その後、加減乗算部806がph1を計算し、その結果にupを加える
（すなわち up+(ph1)）ことにより、達成できる。ただし、pInvは、式8をみたす整数である。モジュラー乗算部801およびモジュラー加減算部805は、
(uq+up)pInv mod q を計算し、h2に格納する。加減乗算部806は、
-up+ph2を計算し、w2に格納する（906）。これらの計算は、モジュラー加減算部805が
uq+up mod q を計算し、モジュラー乗算部801が、その結果にpInvを乗ずる
（すなわち (uq+up)pInv mod q）ことによりh2が計算できる。その後、加減乗算部806がph2を計算し、その結果からupを減ずる（すなわち -up+(ph2)）ことにより、達成できる。加減乗算部806は、
n-w1, m-w2 を計算し、それぞれw3, w4 に格納する（907）。モジュラー乗算部801は、
w1 cs mod n, w2 cs mod n, w3 cs mod n, w4 cs mod nを計算し、それぞれm1, m2, m3, m4 に格納する（908）。これらの計算は、モジュラー乗算部801が cs mod n を計算し、その結果にそれぞれw1, w2, w3, w4 を乗ずることにより達成できる。復号化処理部132は、m1, m2, m3, m4 を平文mの候補として出力する（909）。
【００６９】
復号化処理部132の行なう処理により出力されるm1, m2, m3, m4は
m1 2 = m2 2 = m3 2 = m4 2 = c mod n  （式24）
をみたす。この理由は次の通りである。まず、upに関して次の式が成立する。
【００７０】
up 2 = (t(p-3)/4)2 
= (s2 c)(p-3)/2 = sp-3 mp-3 mod p  （式25）
ここで、pは素数であるので、任意の整数zに対して、
zp = z mod p  （式26）
が成り立つことに注意すると、
up 2 = s-2 m-2 mod p  （式27）
が成り立つ。同様に、
uq 2 = s-2 m-2 mod q  （式28）
も成り立つ。他方、w1に関して次の式が成立する。
【００７１】
w1 2 = up 2 mod p  （式29）
w1 2 = (up +p(uq-up)pInv)2 mod q  （式30）
pInvは式*をみたすので、
w1 2 = uq 2 mod q  （式31）
が成り立つ。式22、式27、式28、式29、式31を考慮すると、
m1 2 = w1 2 c2 s2 mod n
= c mod n    （式32）
が成り立つ。m2, m3, m4に対しても、同様にして示すことができる。
【００７２】
上記の計算方法では、剰余乗算等の演算は用いるが、逆元演算は用いない。したがって、非特許文献３の手法と比べて、高速な計算が可能である。また、e=2であるため、通常のRabin暗号の計算手法と比べると、計算量増加は剰余乗算5回分である。一般に、1024ビットの汎用べき乗剰余算を行なった場合、1500回程度の剰余乗算を必要とするため、上記計算方法の計算量増加は、この値と比べて比較的小さいと言える。
【００７３】
また、上記の計算方法では逆元演算を用いないため、逆元演算をあらかじめ計算し、その値をメモリに格納する、ということを行なう必要がない。そのため、メモリ使用量が少なくてすむ。
【００７４】
また、上記の計算方法は、サイドチャネル攻撃に対する防御に関しても有効である。この理由は次の通りである。上記の計算方法で秘密鍵が初めて用いられるのはステップ904であり、その後の演算は、ステップ904の演算結果を用いる。ステップ904の入力である整数tは、入力されたデータcと、ステップ901で生成された乱数rの4乗との乗算結果である。したがって、攻撃者は整数tの値を予測することはできない。Novakの攻撃は、汎用べき乗剰余算に入力される値が攻撃者にとって既知であることを利用しているので、攻撃者はNovakの攻撃を行なうことができない。
【００７５】
以上の通り、上記の計算方法は、サイドチャネル攻撃に有用な情報を与えないため、サイドチャネル攻撃に対して耐性がある。また、逆元演算を用いないため、高速な計算が可能であり、さらに、逆元演算の結果をあらかじめメモリに格納する必要もないため、メモリ使用量も少なくてすむ。
【００７６】
なお、ステップ906で -up を p-up におきかえて実行してもよい。そうすると、負の整数を扱うことなく実行できるため、プログラムを簡略化できる。
【実施例３】
【００７７】
第3実施例では、HIME(R)の場合について説明する。  非特許文献７に開示されているように、HIME(R)における秘密鍵は、大きな素数p,q、公開鍵は、整数n,eである。HIME(R)の場合は、Rabin暗号と同様に、eは式20をみたすように選ばれる。また素数p,qについても、式21をみたすように選ばれる。これらの数値の間には、
n = p2q                      （式33）
という関係が成り立っている。HIME(R)の場合、暗号化や署名の検証においては、xの平方
y = x2 mod n                  （式34）
を計算し、復号化や署名の作成においては、式34をみたすxを計算する。そのため、HIME(R)では、式34をみたす整数が4つ存在し、そのうち適切なものを選択することとなる。
【００７８】
第3実施例では、復号化処理部132として、図8で示されるデータ処理部132の機能ブロックを用いる。
【００７９】
復号化処理部132が所定のビット長に区切られている暗号文cから、秘密鍵を用いて、平文mを計算する第3の計算方法を、図10を用いて説明する。
【００８０】
復号化処理部132は暗号文cを受け取る。乱数生成部802は、乱数rを生成する（1001）。モジュラー乗算部801は、
r2 mod nを計算し、sに格納する（1002）。モジュラー乗算部801は、
s2c mod nを計算し、tに格納する（1003）。この計算は、モジュラー乗算部801がsから
s2 mod nを計算し、その後 
(s2) c mod nを計算することにより達成できる。汎用べき乗剰余計算部803は、 
t(p-3)/4 mod p, t(q-3)/4 mod q を計算し、それぞれup, uq格納する（1004）。モジュラー乗算部801は、
up t mod p を計算し、kに格納する（1005）。モジュラー乗算部801およびモジュラー加減算部805は、
(uq-up)pInv mod q を計算し、h1に格納する。加減乗算部806は、
up+ph1を計算し、upq,1に格納する（1006）。これらの計算は、モジュラー加減算部805がuq-up mod q を計算し、モジュラー乗算部801が、その結果にpInvを乗ずる
（すなわち (uq-up)pInv mod q）ことによりh1が計算できる。その後、加減乗算部806がph1を計算し、その結果にupを加える
（すなわち up+(ph1)）ことにより、達成できる。ただし、pInvは、式8をみたす整数である。モジュラー乗算部801およびモジュラー加減算部805は、
t upq,1 2 mod n を計算し、g1に格納する。モジュラー乗算部801は、
g1 k (2Inv) mod n を計算し、b1に格納する。モジュラー加減乗算部805は、
upq,1+b1を計算し、u1に格納する（1007）。これらの計算は、モジュラー乗算部801が 
upq,1 2 mod n を計算し、モジュラー加減算部805が、tからその結果を減ずる
（すなわち t  (upq,1 2) mod n）ことにより、g1が計算できる。その後、モジュラー乗算部801が、
k (2Inv) mod n を計算し、その結果にg1を乗ずる
（すなわち g1 (k (2Inv)) mod n）ことにより、b1が計算できる。その後、加減乗算部806が、
upq,1 +b1 を計算することにより、達成できる。ただし、2Invは、
2Inv = 2-1 mod p           （式35）
をみたす整数である。モジュラー乗算部801およびモジュラー加減算部805は、
(uq+up)pInv mod q を計算し、h2に格納する。加減乗算部806は、
p-up+ph2を計算し、upq,2に格納する（1008）。これらの計算は、モジュラー加減算部805が
uq+up mod q を計算し、モジュラー乗算部801が、その結果にpInvを乗ずる
（すなわち (uq+up)pInv mod q）ことによりh2が計算できる。その後、加減乗算部806がph2を計算し、その結果にpを加え、upを減ずる
（すなわち p-up+(ph2)）ことにより、達成できる。
【００８１】
モジュラー乗算部801およびモジュラー加減算部805は、
t upq,2 2 mod n を計算し、g2に格納する。モジュラー乗算部801は、
g2 k (2Inv) mod n を計算し、b2に格納する。モジュラー加減乗算部805は、
upq,2+b2を計算し、u2に格納する（1009）。これらの計算は、モジュラー乗算部801が 
upq,2 2 mod n を計算し、モジュラー加減算部805が、tからその結果を減ずる
（すなわち t  (upq,2 2) mod n）ことにより、g2が計算できる。その後、モジュラー乗算部801が、
k (2Inv) mod n を計算し、その結果にg2を乗ずる
（すなわち g2 (k (2Inv)) mod n）ことにより、b2が計算できる。その後、加減乗算部806が、
upq,2 +b2 を計算することにより、達成できる。ただし、2Invは、式35をみたす整数である。加減乗算部806は、
n-u1, m-u2 を計算し、それぞれu3, u4 に格納する（1010）。モジュラー乗算部801は、
u1 cs mod n, u2 cs mod n, u3 cs mod n, u4 cs mod nを計算し、それぞれm1, m2, m3, m4 に格納する（1011）。これらの計算は、モジュラー乗算部801が cs mod n を計算し、その結果にそれぞれu1, u2, u3, u4 を乗ずることにより達成できる。復号化処理部132は、m1, m2, m3, m4 を平文mの候補として出力する（1012）。
【００８２】
復号化処理部132の行なう処理により出力されるm1, m2, m3, m4は
m1 2 = m2 2 = m3 2 = m4 2 = c mod n  （式36）
をみたす。この理由は次の通りである。まず、upに関して次の式が成立する。
【００８３】
up 2 = (t(p-3)/4)2 
= (s2 c)(p-3)/2 = sp-3 mp-3 mod p  （式37）
ここで、pは素数であるので、任意の整数zに対して、
zp = z mod p    （式38）
が成り立つことに注意すると、
up 2 = s-2 m-2 mod p  （式39）
が成り立つ。同様に、
uq 2 = s-2 m-2 mod q  （式40）
も成り立つ。式39、式40を用いると、
upq,1 2 = s-2 m-2 mod p  （式41）
upq,1 2 = s-2 m-2 mod q  （式42）
を示すことができ、したがって、
upq,1 2 = s-2 m-2 mod pq  （式43）
が成り立つ。u = (sm)-1 mod n, u = upq,1 + b と表すと、
t = u2 = upq,1 2 + 2upq,1 b mod n  （式44）
となる。そのため、
b = (t  upq,1 2)((2 upq,1)-1 mod p) mod n  （式45）
となる。
【００８４】
k = up 1 mod p  （式46）
であることに注意すれば、b = b1 が成り立つ。したがって、
m1 = (sm)-1 cs = m mod n  （式47）
となる。m2, m3, m4 についても同様に示すことができる。
【００８５】
上記の計算方法では、剰余乗算等の演算は用いるが、逆元演算は用いない。したがって、非特許文献３の手法と比べて、高速な計算が可能である。また、e=2であるため、通常のHIME(R)の計算手法と比べると、計算量増加は剰余乗算5回分である。一般に、1024ビットの汎用べき乗剰余算を行なった場合、1500回程度の剰余乗算を必要とするため、上記計算方法の計算量増加は、この値と比べて比較的小さいと言える。
【００８６】
また、上記の計算方法では逆元演算を用いないため、逆元演算をあらかじめ計算し、その値をメモリに格納する、ということを行なう必要がない。そのため、メモリ使用量が少なくてすむ。
【００８７】
また、上記の計算方法は、サイドチャネル攻撃に対する防御に関しても有効である。この理由は次の通りである。上記の計算方法で秘密鍵が初めて用いられるのはステップ1004であり、その後の演算は、ステップ1004の演算結果を用いる。ステップ1004の入力である整数tは、入力されたデータcと、ステップ1001で生成された乱数rの4乗との乗算結果である。したがって、攻撃者は整数tの値を予測することはできない。Novakの攻撃は、汎用べき乗剰余算に入力される値が攻撃者にとって既知であることを利用しているので、攻撃者はNovakの攻撃を行なうことができない。
【００８８】
以上の通り、上記の計算方法は、サイドチャネル攻撃に有用な情報を与えないため、サイドチャネル攻撃に対して耐性がある。また、逆元演算を用いないため、高速な計算が可能であり、さらに、逆元演算の結果をあらかじめメモリに格納する必要もないため、メモリ使用量も少なくてすむ。
【００８９】
なお、ステップ906で -up を p-up におきかえて実行してもよい。そうすると、負の整数を扱うことなく実行できるため、プログラムを簡略化できる。
【００９０】
以上、コンピュータＢ121が、暗号化されたデータ141を復号化する場合のデータ処理部132の動作を説明したが、コンピュータＡ101が入力データを暗号化する場合も同様である。
【００９１】
また、本発明は、署名作成方法をしても用いることができる。その場合には、暗号文cは、署名対象データcとして扱い、署名生成の際には、
m = cd mod n          （式48）
を計算し、mをデータcに対する署名として出力すればよい。
【００９２】
また、上記実施形態におけるコンピュータは、スマートカードや携帯電話、情報家電であってもよい。またその際、必要なデータはオンラインで上記コンピュータ内に入力され、べき乗剰余計算を行なってもよい
また、上記各実施形態におけるデータ処理部、ＣＲＴ計算部は、専用のハードウェアを用いて行なってもよい。モジュラー乗算部、モジュラー加減算部、乱数生成部、汎用べき乗剰余計算部、モジュラー剰余計算部、加減乗算部をコプロセッサまたはそれ以外の専用ハードウェアで実現してもよい。
【図面の簡単な説明】
【００９３】
【図１】実施形態におけるシステム構成図である。
【図２】第1実施例の実施形態におけるデータ処理部の構成図である。
【図３】第1実施例における復号化処理を示すフローチャート図である。
【図４】第１実施例の実施形態におけるＣＲＴ計算部の構成図である。
【図５】第１実施例におけるＣＲＴ計算部の行なう計算方法を示すフローチャート図である。
【図６】第1実施例におけるＣＲＴ計算部の行なう計算方法を示すフローチャート図である。
【図７】第1実施例におけるＣＲＴ計算部の行なう計算方法を示すフローチャート図である。
【図８】第２、第３実施例の実施形態におけるデータ処理部の構成図である。
【図９】第２実施例における復号化処理を示すフローチャートである。
【図１０】第３実施例における復号化処理を示すフローチャートである。
【符号の説明】
【００９４】
101、121：コンピュータ、102、122：記憶部、112、132：データ処理部、104、124、204、406、804：定数、105、125：秘密情報、110、130：入出力インターフェース、108、128：ディスプレイ、109、129：キーボード、142：ネットワーク、141、143：データ、201、401、801：モジュラー乗算部、202、802：乱数生成部、203、803：汎用べき乗剰余計算部、402、805：モジュラー加減算部、403：モジュラー剰余計算部、404：べき乗剰余計算部、405、806：加減乗算部。
【図１】
0004626148.tif 000002
【図２】
0004626148.tif 000003
【図３】
0004626148.tif 000004
【図４】
0004626148.tif 000005
【図５】
0004626148.tif 000006
【図６】
0004626148.tif 000007
【図７】
0004626148.tif 000008
【図８】
0004626148.tif 000009
【図９】
0004626148.tif 000010
【図１０】
0004626148.tif 000011