(57)【要約】  401は、105に保持される鍵dから201に保持される乱数2rを減算して得られる鍵d’を、302に格納する。演算開始時には、値「-C」と「-C2」がそれぞれ計算された上で、乗算テーブルメモリ205に値「C」と共に保持される。107は、第1演算サイクルでは、演算途中データレジスタ103に保持されている中間値108を選択し出力することにより乗算剰余演算回路104に2乗算を実行させる。107は、第2演算サイクルにおいては、鍵ビット値d’iと乱数ビット値r iの組合せに応じて、205に保持されている3値のうち1値を選択し出力することにより乗算剰余演算回路104に乗算を実行させる。これにより、演算時間が短く、回路規模が小さく、安全性が十分な暗号処理装置を実現できる。
2009118795.tif 000002
【特許請求の範囲】
【請求項１】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算ステップを繰返し実行することにより、    M = Cd mod Nで示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理方法であって、  乱数データと前記鍵データｄを入力し、前記鍵データdから前記乱数データｒを減算して鍵データd’を算出するステップと、  演算開始時に、前記入力データCに対して-C及び-C2を演算し、前記C,-C,及び-C2を記憶するステップと、  前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算ステップを実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記鍵データd’を構成する前記ビット値ｄiに対応するビット値d’iと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶したC,-C,-C2のうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する又は前記乗算剰余演算ステップをスキップすることにより、今回の繰返し演算の結果を得る繰返し演算ステップと、  を含むことを特徴とする暗号処理方法。
【請求項２】
前記繰返し演算ステップの第2演算サイクルにおいて、  前記ビット値d’i=0、前記ビット値r i=0のときに、前記乗算剰余演算ステップをスキップし、  前記ビット値d’i=0、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、  前記ビット値d’i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、  前記ビット値d’i=1、前記ビット値r i=1のときに、前記記憶した-C2の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する、  ことを特徴とする請求項１に記載の暗号処理方法。
【請求項３】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算ステップを繰返し実行することにより、    M = Cdmod Nで示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理方法であって、  演算開始時に、前記入力データCに対して-1及び-Cを演算し、前記-1,C,及び-Cを記憶するステップと、  前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算ステップを実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記ビット値ｄiと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶した-1,C,-Cのうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する又は前記乗算剰余演算ステップをスキップすることにより、今回の繰返し演算の結果を得る繰返し演算ステップと、  を含むことを特徴とする暗号処理方法。
【請求項４】
前記繰返し演算ステップの第2演算サイクルにおいて、  前記ビット値d’i=0、前記ビット値r i=0のときに、前記乗算剰余演算ステップをスキップし、  前記ビット値d’i=0、前記ビット値r i=1のときに、前記記憶した-1の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、  前記ビット値d’i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、  前記ビット値d’i=1、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する、  ことを特徴とする請求項3に記載の暗号処理方法。
【請求項５】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算機能を繰返し実行することにより、    M = Cdmod Nで示されるべき乗剰余演算を実行して暗号化又は復号化を行うコンピュータに、  乱数データと前記鍵データｄを入力し、前記鍵データdから前記乱数データｒを減算して鍵データd’を算出する機能と、  演算開始時に、前記入力データCに対して-C及び-C2を演算し、前記C,-C,及び-C2を記憶する機能と、  前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算機能を実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記鍵データd’を構成する前記ビット値ｄiに対応するビット値d’ iと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶したC,-C,-C2のうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行する又は前記乗算剰余演算機能をスキップすることにより、今回の繰返し演算の結果を得る繰返し演算機能と、  を実行させるためのプログラム。
【請求項６】
前記繰返し演算機能の第2演算サイクルにおいて、  前記ビット値d’i=0、前記ビット値r i=0のときに、前記乗算剰余演算機能をスキップし、  前記ビット値d’i=0、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行し、  前記ビット値d’i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行し、  前記ビット値d’i=1、前記ビット値r i=1のときに、前記記憶した-C2の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行する、  ことを特徴とする請求項５に記載のプログラム。
【請求項７】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算機能を繰返し実行することにより、    M = Cdmod Nで示されるべき乗剰余演算を実行して暗号化又は復号化を行うコンピュータに、  演算開始時に、前記入力データCに対して-1及び-Cを演算し、前記-1,C,及び-Cを記憶する機能と、  前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算機能を実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記ビット値ｄiと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶した-1,C,-Cのうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行する又は前記乗算剰余演算機能をスキップすることにより、今回の繰返し演算の結果を得る繰返し演算機能と、  を実行させるためのプログラム。
【請求項８】
前記繰返し演算機能の第2演算サイクルにおいて、  前記ビット値d’i=0、前記ビット値r i=0のときに、前記乗算剰余演算機能をスキップし、  前記ビット値d’i=0、前記ビット値r i=1のときに、前記記憶した-1の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行し、  前記ビット値d’i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行し、  前記ビット値d’i=1、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行する、  ことを特徴とする請求項７に記載のプログラム。
【請求項９】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算手段を繰返し動作させることにより、    M = Cdmod Nで示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理装置であって、  乱数データと前記鍵データｄを入力し、前記鍵データdから前記乱数データｒを減算して鍵データd’を算出する減算手段と、  演算開始時に、前記入力データCに対して-C及び-C2を演算し、前記C,-C,及び-C2を記憶する記憶手段と、  前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算手段を実行させ、前記第1演算サイクルに続く第2演算サイクルにおいて、前記鍵データd’を構成する前記ビット値ｄiに対応するビット値d’ iと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶したC,-C,-C2のうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させる又は前記乗算剰余演算手段の実行をスキップすることにより、今回の繰返し演算の結果を得る繰返し演算手段と、  を含むことを特徴とする暗号処理装置。
【請求項１０】
前記繰返し演算手段は、前記第2演算サイクルにおいて、  前記ビット値d’i=0、前記ビット値r i=0のときに、前記乗算剰余演算手段の実行をスキップさせ、  前記ビット値d’i=0、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させ、  前記ビット値d’i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させ、  前記ビット値d’i=1、前記ビット値r i=1のときに、前記記憶した-C2の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行させる、  ことを特徴とする請求項９に記載の暗号処理装置。
【請求項１１】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算手段を繰返し動作させることにより、    M = Cdmod Nで示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理装置であって、  演算開始時に、前記入力データCに対して-1及び-Cを演算し、前記-1,C,及び-Cを記憶する記憶手段と、  前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算手段を実行させ、前記第1演算サイクルに続く第2演算サイクルにおいて、前記ビット値ｄiと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶した-1,C,-Cのうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させる又は前記乗算剰余演算手段の実行をスキップさせることにより、今回の繰返し演算の結果を得る繰返し演算手段と、  を含むことを特徴とする暗号処理装置。
【請求項１２】
前記繰返し演算手段は、前記第2演算サイクルにおいて、  前記ビット値d’i=0、前記ビット値r i=0のときに、前記乗算剰余演算手段の実行をスキップさせ、  前記ビット値d’i=0、前記ビット値r i=1のときに、前記記憶した-1の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させ、  前記ビット値d’i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させ、  前記ビット値d’i=1、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させる、  ことを特徴とする請求項１１に記載の暗号処理装置。
【請求項１３】
請求項９乃至１２の何れか１項に記載の暗号処理装置を組み込んだ組込装置。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は暗号の分野に属するもので、暗号プロセッサ内部の秘密鍵をサイドチャネル攻撃と呼ばれる攻撃から防ぐための耐タンパ技術に関する。
【背景技術】
【０００２】  暗号方式は、共通鍵暗号方式と公開鍵暗号方式に大別される。共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(秘密鍵)を受信者のみの秘密情報とすることで安全性を保つ方式である。【０００３】  暗号の分野における技術の一つに、解読技術とよばれるものがある。解読技術とは秘密鍵等の秘密情報を暗号文等入手可能な情報から推定する技術のことであり、様々な手法が存在する。その中で最近注目されている技術に、サイドチャネル攻撃と呼ばれる手法がある。サイドチャネル攻撃とは、1998年にPaul Kocherによって考案された手法で、スマートカード等に搭載された暗号プロセッサに様々な入力データを与えた時の電力消費データやノイズ、処理時間等を収集・解析することにより、暗号プロセッサ内部の鍵情報を推定する手法である。サイドチャネル攻撃を用いれば、共通鍵暗号、公開鍵暗号共に暗号プロセッサから秘密鍵を推定できることが知られている。【０００４】  サイドチャネル攻撃には、処理時間を計測・解析するタイミング攻撃、消費電力を解析して攻撃する電力解析攻撃、ノイズを利用する電磁解析波攻撃などが存在する。特に電力解析攻撃と電磁波解析攻撃は、強力な解析・攻撃手段であり対策が求められている。電力解析攻撃と電磁波解析攻撃は測定する対象と測定方法は異なるが、基本的な解析方法や対策方法は同じである。そのため、本稿では二つを代表して電力解析攻撃をターゲットに記述する。【０００５】  電力解析攻撃には、単純電力解析(Single Power Analysis, 以下SPA), 電力差分解析(Differential Power Analysis, 以下DPA)の2種類が存在する。SPAは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行う方式、一方、DPAは多数の電力消費データの差分を解析することで秘密鍵の推定を行う方式である。【０００６】  DESやAESなどの共通鍵暗号方式に対して、SPA,DPAを用いた推定法については、下記非特許文献１(以下Kocher99) の文献にて述べられている。  RSA暗号、楕円曲線暗号などの公開鍵暗号に対してSPA,DPAを用いた鍵の推定法については、下記非特許文献２(以下Messerges99)や、下記非特許文献３(以下Coron99)などの文献にて述べられている。【０００７】  公開鍵暗号系の中で、現在標準として使用されているのは、RSA暗号である。RSA暗号の安全性は、素因数分解問題の困難性に基づくもので, R. Rivest, A. Shamir, L. Adlemanによって1977年に提案された暗号である。RSA暗号の基本アルゴリズムは次の通りである。【０００８】    C = Memod N      ・・・(1)    M = Cdmod N      ・・・(2)  ここで、Mは平文メッセージ、Cは暗号文、(e, N)は公開鍵、(d, N)は秘密鍵、mod NはNによる剰余を表す。【０００９】  RSA暗号ではM,C,e,d,N等に1024bit以上の非常に大きな整数を使用する。そのため、RSA暗号化装置は、乗算器や加算器などの単純な演算を組み合わせて実現しなければならない。特に、べき乗部分(指数部分)の処理は、指数の値に応じて繰り返し、乗算器や加算器などを制御する必要がある。この処理の代���的な方法がBinary法である。Binary法は、指数(例えばn-bitの秘密鍵d)を2進数表現し(d = dn-1dn-2…ｄ1d0)、例えば復号のべき乗演算を、次式に従って実行する。【００１０】    Cd = ((…((Cdn-1)2 * Cdn-2)2*… )2 * Cd1)2 * Cd0      ・・・(3)ここで、上式では、剰余演算は全ての項において実行されるので省略されている。そして、di = 0 の場合Cdi は１であるので、高速化のために計算をスキップすることがよくある。その場合、di=0 / 1によってCの乗算を実行したり実行しなかったりすることになる。RSAに対するサイドチャネル攻撃では、この特徴を利用する。たとえば、乗算を実行すると乗算器が動作するため消費電力が大きくなるが、動作しなければ総費電力は低いままである。そのため消費電力を測定すれば鍵dの0 / 1が計測できる。これがSPA(Simple Power Analysis)攻撃と呼ばれる。SPAの応用で、こういった特徴を複数の消費電力波形から統計的に導出するDPA(Differential Power Analysis)攻撃、消費電力の変わりに乗算器などからの電磁波ノイズを測定し攻撃に使用するEM(Electro-Magnetic)攻撃などが存在する。【００１１】  こういったRSAに対するサイドチャネル攻撃への対策としては、消費電力やノイズを撹乱するために、計算途中の値(中間値)や指数に乱数要素を加え、攻撃者が測定しても、鍵を導出できないようにするのが一般的である。特に、指数に乱数要素を加えると、鍵の同定が困難になることが知られている。【００１２】  指数に乱数要素を付加する対策の基本的な方式は、下記非特許文献４に記載のExponent Splitingと呼ばれる方式である。この方式は、秘密鍵dを乱数rを使って、    d = d’ + r      ・・・(4)として示されるように2つの項に分割し、次式の計算を実行することにより、乱数で秘密鍵dの解析を困難にしている。【００１３】    M = Cd’ * Cr mod N      ・・・(5)  また、下記非特許文献５(以下Ciet-Joye)では、これを改良して次式の分割式を導入される。【００１４】    d = d0 * r+ d1      ・・・(6)そして、次式を計算することにより、乱数で秘密鍵dの解析を困難にする方式が提案されている。【００１５】    M = (Cr)d0 * Cd1 mod N      ・・・(7)  さらに、Ciet-Joyeは、下記非特許文献６で公開されているShamir’s Tricと呼ばれる、複数のべき乗剰余演算の積を高速に計算する手法を用いることも提案している(以下Ciet-Joye + ST)。【００１６】  Shamir’s Trick は、例えば非常に大きな整数、  z = xa * yb       ・・・(8)を効率的に計算する手法である。一般的なBinary法を用いれはxaとybを別々に計算する必要があるため、次式に示されるように、xaの2倍の計算量を必要とする。【００１７】    xa = ((…((xan-1)2* xan-2)2 *… )2 * xa1)2* xa0    yb = ((…((ybn-1)2 * ybn-2)2*… )2 * yb1)2 * yb0    z = xa * yb                                                      ・・・(9)これに対して、Shamir’s Trickでは、あらかじめai, biで決定される4要素のテーブル、    T[ai, bi] ={1, x, y, xy}      ・・・(10)を作成しておき、次式が計算される。【００１８】    z = ((…((T[an-1,bn-1])2* T[an-2,bn-2])2 *… )2 * T[a1,b1])2* T[a0,b0]                                                      ・・・(11)これにより、xaの計算量とほぼ同じでzの計算が可能となる。【００１９】  スマートカード等にRSAを搭載する場合、回路面積が限られている上に、動作周波数が低いため、可能な限り小型・高速な実装が求められる。さらに、スマートカードはチップが直接カードに搭載され��非常に攻撃にさらされやすいデバイスであるため、サイドチャネル攻撃対策は必須である。【００２０】  図１は、例えば前述した(3)式の復号のべき乗剰余演算を実行する回路の構成例である。暗号化の演算回路も同様である（(1)式及び(2)式参照）。  乗算剰余演算回路104は、１回の乗算剰余演算を実行する回路である。乗算剰余演算回路104の実行サイクルは、第1演算サイクル及び第2演算サイクルの2サイクルで構成される。下記表１は、各演算サイクルにおける第2スイッチ107の制御を示した表である。【００２１】
【表１】
2009118795.tif 000003
第2スイッチ107は、第1演算サイクルにおいては、演算途中データレジスタ103に保持されている中間値108を選択し出力する。一方、第2スイッチ107は、第2演算サイクルにおいては、鍵レジスタ105に保持されている現在の演算サイクルに対応する鍵ビットｄiの値が0ならば、演算をスキップさせる値1を出力し、鍵ビットｄiの値が1ならば、乗数Cを出力する。
【００２２】  図１のべき乗剰余演算回路において、まず、入力レジスタ101は、(3)式の最も内側の項「Cdn-1」を入力するレジスタである。この値は、鍵の最上位ビット値「dn-1」が１ならば「C」であり、０ならば「1」である。【００２３】  この入力レジスタ101の値は、復号演算の開始時に、第1スイッチ102を介して演算途中データレジスタ103に保持される。第1スイッチ102は、演算の開始時のみ入力レジスタ101の出力を選択し出力し、それ以降は、乗算剰余演算回路104の出力を選択し出力する。【００２４】  そして、演算開始直後の第1演算サイクルにおいて、第2スイッチ107が中間値108を選択し出力することにより、乗算剰余演算回路104は、(3)式の「(Cdn-1)2」の2乗演算及びそれに対する剰余演算をまず実行する。【００２５】  続く、第2演算サイクルにおいて、第2スイッチ107が鍵ビットdn-2の値に応じて「1」又は「C」を出力、即ち「Cdn-2」の値を出力することにより、乗算剰余演算回路104は、(3)式の「(Cdn-1)2* Cdn-2」の乗算及びそれに対する剰余演算を実行する。なお、第2スイッチ107が「1」を出力した場合には乗算剰余演算回路104は、実際には乗算を実行する必要はなく、入力値をそのまま出力するように構成されている。【００２６】  それに続く、第1演算サイクルにおいては、再び第2スイッチ107が中間値108を選択し出力することにより、乗算剰余演算回路104が、再び2乗演算及びそれに対する剰余演算を実行し、第2演算サイクルにおいては、第2スイッチ107が鍵ビットdiの値に応じて「1」又は「C」を出力、即ち「Cdi」の値を出力することにより、乗算剰余演算回路104は、(3)式の「(Cdn-1)2* Cdn-2」の乗算及びそれに対する剰余演算を実行する。【００２７】  以上の第1演算サイクルと第2演算サイクルの演算ペア動作がn-1回繰返し実行されることにより、(3)式を計算することができる。  上述のべき乗剰余演算回路は、前述したように、鍵ビットdiの値に応じて乗算剰余演算回路104が動作したりしなかったりするため、電力解析攻撃等により鍵ビットを予測できてしまう。【００２８】  そこで、本発明に対する従来技術1として、Exponent Splittingを導入したRSAを考える。前記(5)式のExponent Splittingでは、dへの乱数要素追加は加減算を用いる。これはRSA演算リソースが流用できるため回路規模の増加はほとんどない。またRSA演算自体は、図１に示される通常のRSA回路を2回用いるだけであり、回路規模は増加しない。そのため、Exponent Splittingでは回路規模の増加はほとんどないと言える。しかし、RSA回路を2回用いる必要があり、RSA処理時間が対策無しの2倍必要となる。この処理時間の短縮が課題である。【００２９】  次に、本発明に対する従来技術2として、Ciet-Joyeの手法を搭載する場合を考える。この手法では、(7)式で使用される乱数要素d0とd1を (6)式から演算するために、鍵ｄを乱数ｒで除算するための割り算回路を必要とする。割り算回路は回路規模的には非常に大きい。従来技術2では、Cr, (Cr)d0, Cd1の三種類のべき乗剰余演算を行う必要があるが、rとd0のビット数は合計で元のdと同程度であることから、処理時間は対策無し（図1）の1.5倍程度となる。まとめると、回路規模的には割り算回路が増加し、処理時間が1.5倍必要となるため、Ciet-Joyeを実装する場合、回路規模と処理時間両方の削減が課題である。【００３０】  更に、本発明に対���る従来技術3として、Ciet-JoyeにSTを適用する(11)式の場合を考える。図２は、従来技術3に対応するべき乗剰余演算回路の構成例を示した図、下記表２は図２の第2スイッチ107の制御規則を示した表である。【００３１】
【表２】
2009118795.tif 000004
図２において、図１の場合と同じ番号が付された部分は、図１の場合と同じ機能を有する。
【００３２】  図２において、割り算回路202は、(6)式に基づいて、鍵レジスタ105に保持される鍵dを乱数レジスタ201に保持される乱数rで除算して得られる商d0と余りd1を、それぞれ商レジスタ203及び余りレジスタ204に格納する。【００３３】  また、従来技術3において、(7)式と(8)式の関係より、(10)式におけるaiとbiはd0iとd1iに対応し、(10)式のx、y、及びxyは、Cr、C、及びCr*C=Cr+1となる。この結果、従来技術3では、(10)式で示されるテーブル値に相当する各値、  T[d0i,d1i]={1,Cr,C,Cr+1}      ・・・(12)が、演算開始時にそれぞれ計算された上で、図２の乗数テーブルメモリ205に保持される。【００３４】  上記関係を前提とした上で、(11)式によって示される(7)式の演算は、(3)式の場合と同様に2乗算と乗算の繰返しで実現できる。従って、図１の場合と同様に、図２の回路において、第2スイッチ107は、第1演算サイクルにおいては、演算途中データレジスタ103に保持されている中間値108を選択し出力することにより乗算剰余演算回路104に2乗算を実行させ、第2演算サイクルにおいては、商レジスタ203に保持されている鍵の商ビット値d0iと余りレジスタ204に保持されている鍵の余りビット値d1iの値の組合せに応じて、(12)式又は表２に基づいて乗数テーブルメモリ205の値を選択し出力することにより乗算剰余演算回路104に乗算を実行させる。【００３５】  従来技術3では、乗数テーブルメモリ205に{C, Cr, Cr+1}の各値を計算してセットしなければならない。このロジックは複雑であるが、一度各値がセットされれば処理時間は、図１の攻撃対策無しの場合と同程度に削減できる。まとめると、回路規模的には割り算回路202の追加に加え、乗数テーブルメモリ205の切り替え機構が増加し、処理時間は攻撃対策無しの場合と同程度となる。このためCiet-Joye＋STを実装する場合、回路規模の削減が課題である。【００３６】  従来技術1〜3の方法の安全性は、RSAのソフトウェア(ファームウェア)で実装可能な程度に十分高い(160bit程度の安全性といわれる)。逆に言えば、これらの手法の安全性は、RSAをハードウェア実装するには十分過ぎるため、安全性をやや落としても小型高速な実装方法が望まれる。【００３７】  この解決策として、単純に従来技術1にSTを適用する場合を考える。この手法では、従来技術１における(5)式のRSA演算部分がテーブルの切替えで実行される。即ち、図３は、従来技術1+ST法に対応するべき乗剰余演算回路の構成例を示した図、下記表３は図３の第2スイッチ107の制御規則を示した表である。【００３８】
【表３】
2009118795.tif 000005
図３において、図１の場合と同じ番号が付された部分は、図１の場合と同じ機能を有する。
【００３９】  図３において、減算回路301は、(4)式に基づいて、鍵レジスタ105に保持される鍵dから乱数レジスタ201に保持される乱数rを減算して得られる鍵d’を、鍵レジスタ302に格納する。【００４０】  また、従来技術1+ST法において、(5)式と(8)式の関係より、(10)式におけるaiとbiはd’とｒに対応し、(10)式のx、y、及びxyは、C、C、及びC*C=C2となる。この結果、従来技術3では、(10)式で示されるテーブル値に相当する各値、  T[d’,ｒ]={1,C,C,C2}      ・・・(13)が、演算開始時にそれぞれ計算された上で、図３の乗数テーブルメモリ205に保持される。(12)式の第2項と第3項は、共に「C」であるため、実際に演算される値は「C2」の1値、記憶される値は「C」と「C2」の2値である。【００４１】  上記関係を前提とした上で、(11)式によって示される(5)式の演算は、(3)式の場合と同様に2乗算と乗算の繰返しで実現できる。従って、図１の場合と同様に、図３の回路において、第2スイッチ107は、第1演算サイクルにおいては、演算途中データレジスタ103に保持されている中間値108を選択し出力することにより乗算剰余演算回路104に2乗算を実行させ、第2演算サイクルにおいては、鍵レジスタ302に保持されている鍵ビット値d’iと乱数レジスタ201に保持されている乱数ビット値r iの組合せに応じて、(13)式又は表３に基づいて乗数テーブルメモリ205の値を選択し出力することにより乗算剰余演算回路104に乗算を実行させる。【００４２】  従来技術1+ST法では、乗数テーブルメモリ205には{C,C2}を持つだけなので、テーブルに値をセットするロジックは単純にできる。処理速度も、攻撃対策無しの場合と同程度で実現できる。しかし、この方法では、Exponent Splittingで追加された乱数要素がSTにより大半キャンセルされ、乱数性は指数部分/中間値部分で各1ビット分しか有効でない。従って、従来技術1+ST法は、有効な攻撃対策を有しないという問題点を有している。【００４３】  下記非特許文献は、以上の背景技術及び従来技術の説明において引用される公知例のリストである。【非特許文献１】Paul Kocher, Joshua Jaffe, and Benjamin Jun, “Differential Power Analysis,” in proceedings of Advances in Cryptology-CRYPTO’99, Lecture Notes in Computer Science vol. 1666, Springer-Verlag, 1999, pp. 388-397
【非特許文献２】Thomas S.Messerges, Ezzy A.Dabbish and Robert H.Sloan ”Power Analysis Attacks of Modular Exponentitiation in Smartcards”, Cryptographic Hardware and Embedded Systems(CHES’99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp.144-157
【非特許文献３】Jean-Sebastein Coron “Resistance against Differential Power Analysis for Elliptic Curve Crytosystems”, Cryptographic Hardware and Embedded Systems  (CHES’99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp.292-302, 1999
【非特許文献４】C.Clavier and M.Joye, "Universal Exponentiation Algorithm: A First Step towards Provable SPA-Resgistance", CHES'01, LNCS 2162, Springer-Verlag, 2001, 300-308, 2001
【非特許文献５】M. Ciet and M. Joye “(Virtually) Free randomization techniques for elliptic curve cryptography,” Information and Communications Security (ICICS 2003), LNCS2836, pp. 348--359, Springer-Verlag, 2003.
【非特許文献６】ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31 (1985) 469-472
【発明の開示】
【００４４】  本発明の課題は、前述した従来技術1＋ST法と同程度の回路規模、処理時間で、より安全性を向上することにある。  本発明は、RSA暗号の処理を行う暗号ハードウェアにおいて、電力解析攻撃(電磁波解析攻撃)による秘密鍵の推定が行われるのを防ぐための対策技術であり、本発明の技術を適用することで、効率的に電力解析攻撃(電磁波解析攻撃)を用いた秘密鍵の推定を困難にし、高い耐タンパ性をもつ暗号プロセッサを実現することができる。
【００４５】  本発明は、Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算ステップを繰返し実行することにより、    M = Cdmod Nで示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理方法、プログラム、装置、及びその装置を組み込んだ組込装置を前提とする。
【００４６】  本発明の第１の態様は、以下の構成を有する。  まず、乱数データと鍵データｄを入力し、鍵データdから乱数データｒを減算して鍵データd’を算出するステップが実行される。
【００４７】  次に、演算開始時に、入力データCに対して-C及び-C2を演算し、C,-C,及び-C2を記憶するステップが実行される。  そして、鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を第1の入力及び第2の入力として乗算剰余演算ステップを実行し、第1演算サイクルに続く第2演算サイクルにおいて、鍵データd’を構成するビット値ｄiに対応するビット値d’iと乱数データrを構成するビット値ｄiに対応するビット値r iの組合せに応じて、記憶したC,-C,-C2のうちの何れか１値を選択的に読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップを実行する又は乗算剰余演算ステップをスキップすることにより、今回の繰返し演算の結果を得る繰返し演算ステップが実行される。
【００４８】  ここで、繰返し演算ステップの第2演算サイクルにおいて、ビット値d’ i=0、ビット値r i=0のときに、乗算剰余演算ステップがスキップされ、ビット値d’i=0、ビット値r i=1のときに、記憶した-Cの値を読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップが実行され、ビット値d’i=1、ビット値r i=0のときに、記憶したCの値を読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップが実行され、ビット値d’i=1、ビット値r i=1のときに、記憶した-C2の値を読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップが実行される。
【００４９】  本発明の第２の態様は、以下の構成を有する。  まず、演算開始時に、入力データCに対して-1及び-Cを演算し、-1,C,及び-Cを記憶するステップが実行される。
【００５０】  次に、鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を第1の入力及び第2の入力として乗算剰余演算ステップを実行し、第1演算サイクルに続く第2演算サイクルにおいて、ビット値ｄiと乱数データrを構成するビット値ｄiに対応するビット値r iの組合せに応じて、記憶した-1,C,-Cのうちの何れか１値を選択的に読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップを実行する又は乗算剰余演算ステップをスキップすることにより、今回の繰返し演算の結果を得る繰返し演算ステップが実行される。
【００５１】  ここで、繰返し演算ステップの第2演算サイクルにおいて、ビット値d’ i=0、ビット値r i=0のときに、乗算剰余演算ステップがスキップされ、ビット値d’i=0、ビット値r i=1のときに、記憶した-1の値を読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップが実行され、ビット値d’i=1、ビット値r i=0のときに、記憶したCの値を読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップが実行され、ビット値d’i=1、ビット値r i=1のときに、記憶した-Cの値を読み出して第2の入力とし前回の繰返し演算の結果を第１の入力として乗算剰余演算ステップが実行される。
【図面の簡単な説明】
【００５２】
【図１】べき乗剰余回路の一般的構成例を示した図である。
【図２】従来技術2(Ciet-Joye + ST)の構成例を示した図である。
【図３】Exponent Splitting ＋ST法の構成例を示した図である。
【図４】第１の実施形態の構成例を示した図である。
【図５】第2の実施形態の構成例を示した図である。
【発明を実施するための最良の形態】
【００５３】  以下、図面を参照しながら、本発明を実施するための最良の形態を詳細に説明する。本発明の第１の実施形態  「背景技術」にて前述した従来技術1+ST法の安全性低下の原因の一つは、(5)式をSTの（８）式に単純に当てはめると、x=y=Cとなることである。そのため乗数テーブルメモリ205の記憶値が{C, C2}の乱数を含まない2値となり、取りうる値の範囲が限られてしまう。【００５４】  そこで、x!=y（「!=」は「=」の否定を表す）となるようにExponent Splittingの式を、マイナス値を利用して以下のように変形する。    d = d’ + 2r      ・・・(14)    M = Cd’ * (−C)2r mod N      ・・・(15)【００５５】  第１の実施形態において、(15)式と(8)式の関係より、(10)式におけるaiとbiはd’と２ｒに対応し、(10)式のx、y、及びxyは、C、-C、及びC*(-C)=-C2となる。この結果、第１の実施形態では、(10)式で示されるテーブル値に相当する各値、  T[d’,2ｒ]={1,C,-C,-C2}      ・・・(16)が、演算開始時にそれぞれ計算された上で、図４の乗数テーブルメモリ205に保持される。これより、乗数テーブルメモリ205に保持される値は{C, −C, −C2}の3値になり、乱数性は指数部分/中間値部分で各2ビット分に増加する。処理時間や回路規模、テーブル作成のロジックは従来技術1(Exponent Splitting)＋ST法と同等である。【００５６】  この構成では、乱数に偶数を用いることで、STに用いる−Cのマイナス値を自動的にキャンセルし、補正が不要であることも特徴である。  図４は、第１の実施形態に対応するべき乗剰余演算回路の構成例を示した図、下記表４は図４の第2スイッチ107の制御規則を示した表である。【００５７】
【表４】
2009118795.tif 000006
図４において、図１の場合と同じ番号が付された部分は、図１の場合と同じ機能を有する。
【００５８】  図４において、減算回路401は、(14)式に基づいて、鍵レジスタ105に保持される鍵dから乱数レジスタ201に保持される乱数2rを減算して得られる鍵d’を、鍵レジスタ302に格納する。【００５９】  演算開始時には、(16)式の値「-C」と「-C2」がそれぞれ計算された上で、乗数テーブルメモリ205に値「C」と共に保持される。  上記関係を前提とした上で、(11)式によって示される(15)式の演算は、(3)式の場合と同様に2乗算と乗算の繰返しで実現できる。従って、図１の場合と同様に、図４の回路において、第2スイッチ107は、第1演算サイクルにおいては、演算途中データレジスタ103に保持されている中間値108を選択し出力することにより乗算剰余演算回路104に2乗算を実行させ、第2演算サイクルにおいては、鍵レジスタ302に保持されている鍵ビット値d’iと乱数レジスタ201に保持されている乱数ビット値r iの組合せに応じて、(16)式又は表４に基づいて乗数テーブルメモリ205の値を選択し出力することにより乗算剰余演算回路104に乗算を実行させる。【００６０】  このように、第１の実施形態では、従来技術1よりも演算時間を短く、従来技術2よりも回路規模を小さく、Exponent Splitting＋ST法よりも安全性を高くすることができる。【００６１】本発明の第２の実施形態  上記第１の実施形態で説明したように、マイナス値を利用したST法を使えば、Exponent Splitting ＋ST法よりも安全性が高く、より演算時間リソース及び回路規模リソースの削減が可能となる。【００６２】  第１の実施形態では、ST法のx,yにCと−Cを用いたが、これをCと−1とすれば、より回路が単純化される。この構成では、dをExponent Splittingせずそのまま用いる。    M = Cd’ * (−1)2r mod N      ・・・(17)【００６３】  第2の実施形態において、(17)式と(8)式の関係より、(10)式におけるaiとbiはd’と２ｒに対応し、(10)式のx、y、及びxyは、C、-1、及びC*(-1)=-Cとなる。この結果、第2の実施形態では、(10)式で示されるテーブル値に相当する各値、  T[d’,2ｒ]={1,C,-1,-C}      ・・・(18)が、演算開始時にそれぞれ計算された上で、図４の乗数テーブルメモリ205に保持される。これより、乗数テーブルメモリ205に保持される値は{C,-1,-C}の3値になり、第１の実施形態の場合と同様に、乱数性は指数部分/中間値部分で各2ビット分になる。処理時間や回路規模、テーブル作成のロジックは従来技術1(Exponent Splitting)＋ST法と同等である。【００６４】  この構成では、乱数に偶数を用いることで、STに用いる−Cのマイナス値を自動的にキャンセルし、補正が不要であることも特徴である。  図５は、第２の実施形態に対応するべき乗剰余演算回路の構成例を示した図、下記表５は図５の第2スイッチ107の制御規則を示した表である。【００６５】
【表５】
2009118795.tif 000007
図５において、図１の場合と同じ番号が付された部分は、図１の場合と同じ機能を有する。
【００６６】  図５において、図４において必要であった減算回路401が不要であることが特徴である。  演算開始時には、(18)式の値「-C」のみが計算された上で、乗数テーブルメモリ205に値「C」「-1」と共に保持される。【００６７】  上記関係を前提とした上で、(11)式によって示される(17)式の演算は、(3)式の場合と同様に2乗算と乗算の繰返しで実現できる。従って、図１の場合と同様に、図５の回路において、第2スイッチ107は、第1演算サイクルにおいては、演算途中データレジスタ103に保持されている中間値108を選択し出力することにより乗算剰余演算回路104に2乗算を実行させ、第2演算サイクルにおいては、鍵レジスタ105に保持されている鍵ビット値diと乱数レジスタ201に保持されている乱数ビット値r iの組合せに応じて、(18)式又は表５に基づいて乗数テーブルメモリ205の値を選択し出力することにより乗算剰余演算回路104に乗算を実行させる。【００６８】  このように、第２の実施形態では、従来技術1よりも演算時間を短く、従来技術2よりも回路規模を更に小さく、Exponent Splitting＋ST法よりも安全性を高くすることができる。但し、乗数テーブルメモリ205からの入力値がCか-Cの何れかのみであるため(-1は第2演算サイクルに続く第1演算サイクルの中間値同士の演算でキャンセルされる)、中間値での乱数性はExponent Splitting+ST法と同等となる。【００６９】本発明の第１、第２の実施形態に対する補足  下記表６に各方式の比較を示す。【表６】
2009118795.tif 000008
この表より、第１及び第２の実施形態は、Exponent Splitting ＋ST法と回路規模、処理時間、テーブル作成ロジックは同等で、より高い乱数性(=安全性)を有することがわかる。
【００７０】  なお、(1)式及び(2)式の等価性より、第１及び第２の実施形態として実現されたべき乗剰余演算回路は、暗号化装置及び復号装置のどちらにも適用できることは自明である。  本発明の実施形態は、RSA暗号の耐タンパ技術を備えたスマートカードや車載機などの組込み機器として実現することができる。
【図１】
2009118795.tif 000009
【図２】
2009118795.tif 000010
【図３】
2009118795.tif 000011
【図４】
2009118795.tif 000012
【図５】
2009118795.tif 000013
【手続補正書】
【提出日】平成22年8月4日(2010.8.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算ステップを繰返し実行することにより、
M = Cd mod N
で示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理方法であって、
乱数データと前記鍵データｄを入力し、前記鍵データdから前記乱数データｒを減算して鍵データd’を算出するステップと、
演算開始時に、前記入力データCに対して-C及び-C2を演算し、前記C,-C,及び-C2を記憶するステップと、
前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算ステップを実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記鍵データd’を構成する前記ビット値ｄiに対応するビット値d’ iと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶したC,-C,-C2のうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する又は前記乗算剰余演算ステップをスキップすることにより、今回の繰返し演算の結果を得る繰返し演算ステップと、
を含むことを特徴とする暗号処理方法。
【請求項２】
前記繰返し演算ステップの第2演算サイクルにおいて、
前記ビット値d’ i=0、前記ビット値ri=0のときに、前記乗算剰余演算ステップをスキップし、
前記ビット値d’ i=0、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、
前記ビット値d’ i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、
前記ビット値d’ i=1、前記ビット値r i=1のときに、前記記憶した-C2の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する、
ことを特徴とする請求項１に記載の暗号処理方法。
【請求項３】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算ステップを繰返し実行することにより、
M = Cd mod N
で示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理方法であって、
演算開始時に、前記入力データCに対して-1及び-Cを演算し、前記-1,C,及び-Cを記憶するステップと、
前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算ステップを実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記ビット値ｄiと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶した-1,C,-Cのうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する又は前記乗算剰余演算ステップをスキップすることにより、今回の繰返し演算の結果を得る繰返し演算ステップと、
を含むことを特徴とする暗号処理方法。
【請求項４】
前記繰返し演算ステップの第2演算サイクルにおいて、
前記ビット値d’ i=0、前記ビット値r i=0のときに、前記乗算剰余演算ステップをスキップし、
前記ビット値d’ i=0、前記ビット値r i=1のときに、前記記憶した-1の値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、
前記ビット値d’ i=1、前記ビット値r i=0のときに、前記記憶したCの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行し、
前記ビット値d’ i=1、前記ビット値r i=1のときに、前記記憶した-Cの値を読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算ステップを実行する、
ことを特徴とする請求項3に記載の暗号処理方法。
【請求項５】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算機能を繰返し実行することにより、
M = Cd mod N
で示されるべき乗剰余演算を実行して暗号化又は復号化を行うコンピュータに、
乱数データと前記鍵データｄを入力し、前記鍵データdから前記乱数データｒを減算して鍵データd’を算出する機能と、
演算開始時に、前記入力データCに対して-C及び-C2を演算し、前記C,-C,及び-C2を記憶する機能と、
前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算機能を実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記鍵データd’を構成する前記ビット値ｄiに対応するビット値d’ iと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶したC,-C,-C2のうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行する又は前記乗算剰余演算機能をスキップすることにより、今回の繰返し演算の結果を得る繰返し演算機能と、
を実行させるためのプログラム。
【請求項６】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算機能を繰返し実行することにより、
M = Cd mod N
で示されるべき乗剰余演算を実行して暗号化又は復号化を行うコンピュータに、
演算開始時に、前記入力データCに対して-1及び-Cを演算し、前記-1,C,及び-Cを記憶する機能と、
前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算機能を実行し、前記第1演算サイクルに続く第2演算サイクルにおいて、前記ビット値ｄiと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶した-1,C,-Cのうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算機能を実行する又は前記乗算剰余演算機能をスキップすることにより、今回の繰返し演算の結果を得る繰返し演算機能と、
を実行させるためのプログラム。
【請求項７】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算手段を繰返し動作させることにより、
M = Cd mod N
で示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理装置であって、
乱数データと前記鍵データｄを入力し、前記鍵データdから前記乱数データｒを減算して鍵データd’を算出する減算手段と、
演算開始時に、前記入力データCに対して-C及び-C2を演算し、前記C,-C,及び-C2を記憶する記憶手段と、
前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算手段を実行させ、前記第1演算サイクルに続く第2演算サイクルにおいて、前記鍵データd’を構成する前記ビット値ｄiに対応するビット値d’ iと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶したC,-C,-C2のうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させる又は前記乗算剰余演算手段の実行をスキップすることにより、今回の繰返し演算の結果を得る繰返し演算手段と、
を含むことを特徴とする暗号処理装置。
【請求項８】
Cを入力データ、dを鍵データ、Mを出力データ、mod Nを法Nによる剰余演算として、第1の入力と第2の入力に対して乗算及び剰余演算を実行する乗算剰余演算手段を繰返し動作させることにより、
M = Cd mod N
で示されるべき乗剰余演算を実行して暗号化又は復号化を行う暗号処理装置であって、
演算開始時に、前記入力データCに対して-1及び-Cを演算し、前記-1,C,及び-Cを記憶する記憶手段と、
前記鍵データdを構成する各ビット値ｄi（0≦i≦n-1）に対応して上位ビットから順次繰り返して実行され、第1演算サイクルにおいて、前回の繰返し演算の結果を前記第1の入力及び前記第2の入力として前記乗算剰余演算手段を実行させ、前記第1演算サイクルに続く第2演算サイクルにおいて、前記ビット値ｄiと前記乱数データrを構成する前記ビット値ｄiに対応するビット値r iの組合せに応じて、前記記憶した-1,C,-Cのうちの何れか１値を選択的に読み出して前記第2の入力とし前記前回の繰返し演算の結果を前記第１の入力として前記乗算剰余演算手段を実行させる又は前記乗算剰余演算手段の実行をスキップさせることにより、今回の繰返し演算の結果を得る繰返し演算手段と、
を含むことを特徴とする暗号処理装置。
【国際調査報告】
2009118795.tif 000014
2009118795.tif 000015
2009118795.tif 000016
2009118795.tif 000017
2009118795.tif 000018
2009118795.tif 000019
2009118795.tif 000020
2009118795.tif 000021