(57)【特許請求の範囲】
【請求項１】
メモリに記録された数値データを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理により更新しながら逆元演算を実行する暗号処理装置において、
前記逆元演算により数値データを更新するための一連の演算処理の少なくとも１つの演算処理の前または後に、当該演算処理の結果を更新しない擬似演算処理を少なくとも１つ付加的に実行する冗長処理手段を設けたことを特徴とする、
暗号処理装置。
【請求項２】
前記擬似演算は、前記メモリに記録された数値データを前記擬似演算処理の入力データとし、更新しない複数種類の演算処理のいずれかにより生じる物理量の変化パタンを、前記更新を伴う複数種類の演算処理のいずれかにより生じる物理量の変化と同じにすることを特徴とする、
請求項１記載の暗号処理装置。
【請求項３】
前記冗長処理手段は、
２つの前記数値データの大小を判別する大小判別手段と、
前記２つの数値データのそれぞれが奇数か偶数かを判別する奇数・偶数判別手段とを備え、前記大小判別手段による判別結果及び前記奇数・偶数判別手段による判別結果の組み合わせが所定の条件を満たすときに前記擬似演算処理の実行を開始するものであって、
前記所定の条件とは、前記装置外部から認知可能な物理量の変化パタンが所定のパタンになるような条件であることを特徴とする、
請求項２記載の暗号処理装置。
【請求項４】
メモリに記録された数値データを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理によって更新しながら逆元演算を実行する暗号処理方法であって、
前記逆元演算により数値データを更新するための一連の演算処理の少なくとも１つの演算処理の前または後に、当該演算処理の結果を更新しない擬似演算処理を少なくとも１つ付加的に実行することを特徴とする、
暗号処理方法。
【請求項５】
メモリを有するコンピュータを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理により更新しながら逆元演算を実行する暗号処理装置として動作させるためのコンピュータプログラムであって、
前記コンピュータを、
前記メモリに記録された数値データを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理により更新しながら実行し、前記逆元演算により数値データを更新するための一連の演算処理の少なくとも１つの演算処理の前または後に、当該演算処理の結果を更新しない擬似演算処理を少なくとも１つ付加的に実行する冗長処理手段として機能させる、
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理の際のセキュリティ技術に関し、特にサイドチャネル攻撃により秘密情報が漏洩することを防止する暗号処理技術に関する。
【背景技術】
【０００２】
ＩＣカードのように高度なセキュリティ性が要求される暗号モジュールは、所要の処理を実行するときの消費電力や電磁波のような物理量の変化パタン（以下、「サイドチャネル情報」という。）の解析により、秘密鍵が漏洩する（以下、「サイドチャネル攻撃」という。）ことが知られている。
そのため、サイドチャネル攻撃への対処が重要になってくる。例えば、ＲＳＡ（ISO/IEC 18033-2などで標準化）やＤＳＡ（FIPS PUB 186-2で規定）のようなデジタル署名アルゴリズムを実装する際には、鍵生成処理や署名生成処理などにおいて、べき乗剰余演算（Modular exponentiation）が行われるが、このべき乗剰余演算処理の過程から、サイドチャネル攻撃によって秘密鍵が漏洩する可能性があることが知られている。
【０００３】
べき乗剰余演算は、「t=g^k mod p」で表され、「ｇ」をｋ乗した結果を「ｐ」で除算したときの剰余を算出する演算である。べき乗剰余演算の処理過程からサイドチャネル攻撃による秘密鍵の漏洩を防止する方法として、擬似演算処理（以下、擬似乗算の処理を「ダミー乗算処理」、擬似減算の処理を「ダミー減算処理」、これらの処理を区別する必要のない場合は「ダミー演算処理」と称する。）を行う方法、「ｇ」のスクランブル（BlindingやDuplicate Method）、「ｐ」の変換、べき数「ｋ」のスクランブル、エンコードなどが知られている。
【０００４】
ダミー演算処理、例えばダミー乗算処理を用いる方法は、べき乗剰余演算の途中に本来は不要な乗算処理を実行して、べき乗剰余演算の実行過程を観察することで得られるサイドチャネル情報を、対策を施さない場合の処理のときと異なるものとすることで、べき数ｋの漏洩を防止する。
特許文献１は、このようなダミー乗算を用いてサイドチャネル攻撃による秘密鍵の漏洩を防止する例である。
【特許文献１】特開２００７−３１６４９１号公報
【０００５】
「ｇ」のスクランブルには、べき乗剰余演算を２つの演算処理に分けて実行する方式（Duplicate Method）がある。この方式は、「g=g1*g2 mod p」となるランダムに定めた２つベースg1、g2について、それぞれ「t1=g1^k mod p」と「t2=g2^k mod p」とを求め、最後に「t=t1*t2 mod p」とする。
【０００６】
「ｐ」の変換とは、「p'=R*p」として、「t'=g^k mod p'」を求めた後に、「t=t' mod p」とする手法である。Ｒは乱数である。また、「ｋ」のスクランブルは，乱数Ｒによって、「k'=k+R(p-1)」として，「t=g^k' mod p」とする手法である。
【０００７】
このように、べき乗剰余演算に対するサイドチャネル攻撃への対策は、従来から多々講じられてきた。これは、べき乗剰余演算をよく知られたバイナリ法などで実装するとその実行過程を物理的に観察することで得られるサイドチャネル情報からダイレクトにべき数ｋを得ることができると知られていて、さらに、良く知られたＲＳＡやＤＳＡなどにおいては、べき数が得られることは、秘密鍵そのものが得られることと等価である。そのために、従来から、べき乗剰余演算に対するサイドチャネル攻撃への対策は、非常に重要であった。
【０００８】
その一方で、ＲＳＡ鍵生成処理やＤＳＡ署名生成処理で実行される逆元演算については、実行過程から得られるサイドチャネル情報と秘密情報との関係が不明であったために、これまでは処理速度や実装面積などについての工夫しか施されておらず、秘密情報の漏洩防止の議論がなされていなかった。しかし、最近、発明者らの研究によって、逆元演算の入力データが漏洩することがわかった。
【０００９】
逆元演算は、数値データａ，ｂ（ａとｂとは互いに素）を入力データとし、数値データｖを出力データとして、「v=1/a mod b」で表すことができる。拡張２進ＧＣＤ法による逆元演算は、主に、加減算処理とシフト処理（例えば「２」による除算）や「２」による乗算）との組み合わせで行われる。
以下、説明の便宜上、入力データｂを奇数とする。
【００１０】
まず、入力データである数値データａ，ｂの初期値をａ0，ｂ0とする。数値データａ,ｂの少なくとも一方が偶数であれば偶数である方の数値データにシフト処理（２による除算）を行って数値データａ,ｂを更新する。数値データａ,ｂの両方が奇数ならば、大きい数値データから小さい数値データを減算して大きい数値データを更新する。その際、初期値である下記の２行２列の行列データＧと、初期値０である数値データｇに数値データａ，ｂに行った更新に対応する演算を行う。
【００１１】
【数１】
0005214317.tif 000002
なお、説明の便宜上、上記の行列を[1,0;0,1]と表現する。例えば、行列[a；b]は下記のような２行１列の行列である。
【００１２】
【数２】
0005214317.tif 000003
【００１３】
数値データの更新は、次のように行う。但し、ａ，ｂ，ｇは、数値データａ，ｂ，ｇ、Ｇは行列データＧである（以下、本明細書において同じ）。
ａをシフトする場合は、G=[1,0;0,2]*Gとg=g+1、
ｂをシフトする場合は、G=[2,0;0,1]*Gとg=g+1、
ａ＝ａ−ｂを行う場合は、G=[1,-1;0,1]*G、
ｂ＝ｂ−ａを行う場合は、G=[1,0;-1,1]*G。
これにより、ａ，ｂ，Ｇ，ｇとの間には、下記の関係が保たれる。
「a*2^g=G[1,1]*a0+G[1,2]*b0」
「b*2^g=G[2,1]*a0+G[2,2]*b0」
この２つの式は、行列表現すると、下記のようになる。
[a;b]*2^g=G*[a0;b0]。
【００１４】
このようなシフト処理と減算処理との組み合わせを数値データｂが「０」になるまで続ける。そのとき、ａはａ0とｂ0の最大公約数である「１」となる。その後、出力データｖの初期値としてＧ[1,1]を設定しておき、このｖをｇ回「２」除算し、「２」で割り切れない場合には数値データｂの初期値であるｂ0を加算する。
このようにして求めた出力データｖが、「1/a mod b」となる値である。
【００１５】
逆元２進ＧＣＤ法の主たる演算である減算処理とシフト処理とでは、処理の中味が異なるため，この違いが処理時間あるいは消費電力など何かしらの物理量の変化パターンの違いとなって観察できる場合がある。図７ａは消費電力の時間変化を表したグラフで、処理時間は同じだが消費電力が異なる場合の例である。減算処理時の消費電力がシフト処理時の消費電力よりも大きいために、消費電力の変化パタンから、減算処理とシフト処理とを区別することができ、サイドチャネル情報が得られる。このサイドチャネル情報に所定の変換アルゴリズムを適用すれば、数値データａなどの逆元の入力データを得ることができる。そして、べき乗剰余演算のべき数ｋと同様に、ＲＳＡの鍵生成処理やＤＳＡの署名生成処理において逆元演算の入力データが得られることは秘密鍵そのものが得られることと等価である。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、上記の問題に鑑み、逆元演算を実行する際に表れるサイドチャネル情報から秘密情報が漏洩されることを防止する新規な暗号処理技術を提供することを、その課題とするものである。
【課題を解決するための手段】
【００１７】
本発明は、上記の課題を解決するために、暗号処理装置、暗号処理方法及びコンピュータプログラムを提供する。
本発明の暗号処理装置は、メモリに記録された数値データを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理により更新しながら逆元演算を実行する暗号処理装置において、前記逆元演算により数値データを更新するための一連の演算処理の少なくとも１つの演算処理の前または後に、当該演算処理の結果を更新しない擬似演算処理を少なくとも１つ付加的に実行する冗長処理手段を設けたことを特徴とする。
この暗号処理装置では、逆元演算の実行過程で、冗長処理が付加的に実行されるので通常処理により得られる物理量の変化パタンとは異なる変化パタンが生じる。サイドチャネル情報から秘密情報を得ようとする者は、この変化パタンからサイドチャネル情報を得ることになるが、サイドチャネル情報に冗長処理による情報が含まれるため、物理量の変化パタンを観測するだけでは秘密情報を得ることができなくなる。
【００１８】
また、ダミー演算処理は、数値データを更新しないので、逆元演算の最終処理結果に影響を与えることなく、つまり、最終処理結果を有効なものとしつつ、実行過程で生じる物理量の変化を通常処理時と異なるパタンに変容させることができる。更新しない複数種類の演算処理のいずれかにより生じる物理量の変化パタンを、通常処理時の物理量の変化と同じにすれば、ダミー演算処理による変化パタンか、通常処理による変化パタンかの区別がつかなくなるため、変化パタンから秘密情報が漏洩する可能性をより低くすることができる。
【００１９】
第１の態様での冗長処理手段は、また、２つの前記数値データの大小を判別する大小判別手段と、前記２つの数値データのそれぞれが奇数か偶数かを判別する奇数・偶数判別手段とを備え、前記大小判別手段による判別結果及び前記奇数・偶数判別手段による判別結果の組み合わせが所定の条件を満たすときに前記ダミー演算処理の実行を開始するものであって、前記所定の条件とは、前記装置外部から認知可能な物理量の変化パタンが所定のパタンになるような条件であるように構成することができる。これにより、ダミー演算処理が付加的に実行されるタイミングを適切に定めることができる。
【００２２】
本発明の暗号処理方法は、メモリに記録された数値データを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理によって更新しながら逆元演算を実行する装置が行う暗号処理方法であって、前記逆元演算により数値データを更新するための一連の演算処理の少なくとも１つの演算処理の前または後に、当該演算処理の結果を更新しないダミー演算処理を少なくとも１つ付加的に実行することを特徴とする。
【００２３】
本発明のコンピュータプログラムは、メモリを有するコンピュータを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理により更新しながら逆元演算を実行する暗号処理装置として動作させるためのコンピュータプログラムであって、前記コンピュータを、前記メモリに記録された数値データを、装置外部から認知可能な物理量の変化パタンが互いに異なる複数種類の演算処理により更新しながら実行し、前記逆元演算により数値データを更新するための一連の演算処理の少なくとも１つの演算処理の前または後に、当該演算処理の結果を更新しない擬似演算処理を少なくとも１つ付加的に実行する冗長処理手段として機能させる、コンピュータプログラムである。
【発明の効果】
【００２４】
本発明によれば、冗長処理を付加的に実行しつつ逆元演算による最終実行結果を有効なものとすることで、逆元演算の実行過程で生じる物理量の変化パタンが、冗長処理が存在しない場合の処理（以下、冗長処理が存在する場合と区別するために「通常処理」と称する場合がある。）と異なるパタンに変容するので、この変化パタンが外部に認知されても、逆元演算がどのように行われたかを解析することができなくなるという特有の効果が得られる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明を、高セキュリティ性のＩＣカードなどの暗号モジュールに適用した場合の実施の形態例を、図面を参照して説明する。
図１は、この実施形態による暗号モジュールのハードウェア構成図である。この暗号モジュール１は、ＣＰＵ（Central Processing Unit）１０と、Ｉ／Ｏインタフェース２０と、ＣＰＵ１０で実行される各種プログラムを格納するプログラムメモリ３１及びプログラムの実行時に用いられるデータが格納されるデータメモリ３２を含むメモリ３０とをハードウエア資源として含み、Ｉ／Ｏインタフェース２０を介して、図示しない外部装置と通信できるように構成される。暗号モジュール１は，外部装置との間で通信して，ＲＳＡやＤＳＡなどのデジタル署名アルゴリズムで使用するパラメータやメッセージを受信し，処理結果を送信する。
【００２６】
暗号モジュール１は、上記のハードウエア資源とプログラムメモリ３１に格納された本発明のコンピュータプログラムとの協働により、特徴的な暗号処理を行うための種々の機能を実現する。図２は、このようにして実現される暗号モジュール１の機能ブロック図である。暗号モジュール１は、べき乗剰余演算部１１、逆元演算部１２、素数生成部１３、乱数生成部１４、ＲＳＡ鍵生成部１５、ＤＳＡ署名生成部１６、及び記憶部１７の機能を実現する。
【００２７】
べき乗剰余演算部１１は、「t=g^k mod p」で表されるべき乗剰余演算処理を行う。べき乗剰余演算部１１は、従来と同様のサイドチャネル攻撃に対する対策が施されており、ダミー乗算、「ｇ」のスクランブル、「ｐ」の変換、「ｋ」のスクランブル、エンコードなどを行う。
【００２８】
逆元演算部１２は、「v=1/k mod p」で表される逆元演算を行う。逆元演算部１２は、判別部１２１、加減算処理部１２２、シフト処理部１２３、スクランブル部１２４、及び制御部１２５の機能ブロックを有する。
判別部１２１は、数値データの大小判別、数値データを「２」で除算したときの剰余の大小判別及び当該剰余による数値データの偶数、奇数の判別、数値データの符号の判別など、特徴的な逆元演算を実行する上で必要となる各種の判別を行う。判別部１２１は、この判別結果を制御部１２５に送る。
【００２９】
加減算処理部１２２は、数値データの加算処理及び減算処理を行う。シフト処理部１２３は、数値データを「２」で除算及び乗算（シフト処理）する。スクランブル部１２４は、乱数生成部１４で生成された乱数を用いて数値データのスクランブルを行う。制御部１２５は、判別部１２１の判別結果に応じて加減算処理部１２２及びシフト処理部１２３に加減算処理及びシフト処理を実行させる。制御部１２５は、判別結果により、減算処理のときは、どの数値データからどの数値データを減算するかを指示し、加算処理のときはどの数値データを用いた加算であるかを指示し、シフト処理のときは、どの数値データのシフト処理を行うかを指示する。
【００３０】
逆元演算部１２は、上記の機能ブロックにより、逆元演算のサイドチャネル攻撃に対する種々の対策を実現する。例えば、判別部１２１、加減算処理部１２２、シフト処理部１２３、及び制御部１２５によるダミー演算処理（第１の対策）、スクランブル部１２５による数値データのスクランブルとその逆の手順による逆スクランブル（第２の対策）、及び、判別部１２１、加減算処理部１２２、シフト処理部１２３、及び制御部１２５による演算過程における大小判別のランダムなエラー又はノイズの混入とそのリカバリ（第３の対策）、の３つの対策を実現する。
逆元演算部１２では、これら３つの対策の少なくとも１つにより（好適には、３つを組み合わせて）、サイドチャネル情報による秘密情報の漏洩を効果的に防止する。これらの詳細については、後述する。
【００３１】
素数生成部１３は、ＲＳＡ鍵生成処理のときに用いる素数を生成し、乱数生成部１４は、ＤＳＡ署名処理のときに用いる乱数を生成する。
【００３２】
ＲＳＡ鍵生成部１５は、べき乗剰余演算部１１、逆元演算部１２、及び素数生成部１３を用いてＲＳＡ鍵を生成する。このＲＳＡ鍵の生成処理は、例えば図３の処理手順で行われる。まず、パラメータとして「ｅ」及び素数ｐ、ｑのサイズを、Ｉ／Ｏインタフェース２０を介して外部装置から取得する（ステップＳ１００）。「ｅ」は、システムの固定値の場合が多い。代表的な例として「e=2^16+1」である。
次に、パラメータとして取得したサイズを満たす素数ｐ、ｑを、素数生成部１３で生成する（ステップＳ１１０）。素数ｐ、ｑは、「gcd(e,p-1)=1」、「gcd(e,q-1)」を満たす。これらを用いて逆元演算部１２で、「d=1/e mod lcm(p-1,q-1))」を行い、「ｄ」を求める（ステップＳ１２０）。また、素数ｐ、ｑの積ｎを算出する。これにより、公開鍵（ｅ，ｎ）、秘密鍵（ｄ,ｐ,ｑ）が得られる（ステップＳ１３０）。
【００３３】
ＤＳＡ署名生成部１６は、べき乗剰余演算部１１、逆元演算部１２、及び乱数生成部１４によりＤＳＡ署名処理を行う。ＤＳＡ署名生成処理は、例えば図４の処理手順で行われる。まず、メッセージＭをＩ／Ｏインタフェース２０を介して外部装置から取得する（ステップＳ２００）。また、署名生成鍵（秘密鍵）ｘを取得する。公開パラメータを（ｇ,ｐ,ｑ）とする。次に、べき数ｋを乱数発生部１４で生成する（ステップＳ２１０）。べき数ｋは（０＜ｋ＜ｑ）の範囲にある乱数である。次に、べき乗剰余演算部１１でべき乗剰余演算「(g^k mod p) mod q」を行い、署名データの一つである「ｒ」を求める（ステップＳ２２０）。次に、べき数ｋの逆元ｋ’を逆元演算部１２で算出する「k'=1/k mod p)」（ステップＳ２３０）。次に署名ｓを求める。署名ｓは、「s=k'・(SHA1(M)+xr) mod q」により求められる（ステップＳ２４０）。以上の手順により、署名データ（ｒ,ｓ）を得る（ステップＳ２５０）。
【００３４】
記憶部１７は、暗号モジュール１で実行する各種処理に用いる数値データ、メッセージ、パラメータなどを格納するメモリである。特に、この実施形態では、逆元演算部１２により行われる逆元演算で更新の対象となる数値データ、逆元演算の実行過程で生成される一時データを格納する。
【００３５】
ＲＳＡ鍵生成部１５で行うＲＳＡ鍵生成処理及びＤＳＡ署名生成部１６で行うＤＳＡ署名生成処理は、いずれも逆元演算をその処理内容に含む。逆元演算では、上記の通り、サイドチャネル攻撃に対する第１〜第３の対策を施す。以下の説明では、逆元演算を拡張２進ＧＣＤ法により実行する場合を例として、第１〜第３の対策について説明する。
【００３６】
＜第１の対策＞
第１の対策としては、加減算処理部１２２による減算処理を、逆元演算に必要な通常処理の他にダミー演算処理、例えばダミー減算処理として周期的に行うことで、シフト処理部１２３によるシフト処理の連続実行回数を固定して行う。
ダミー減算処理も通常処理（ダミーでない通常の（減算）処理）と同じ処理内容なので、物理量の一例となる消費電力の変化パタンは同じである。判別部１２１が、数値データの大小判別結果及び数値データの偶数、奇数判別を行い、この判別結果により制御部１２５が加減算処理部１２２による減算処理とシフト処理部１２３によるシフト処理とを行うが、シフト処理を連続して決まった回数行わせた後に通常処理又はダミー減算処理を必ず行う。
通常処理もダミー減算処理も同じ消費電力となるので、サイドチャネル情報では、どちらの処理なのかは区別できない。そのために、サイドチャネル情報からの秘密鍵情報の漏洩を防止できる。例えば、シフト処理の連続実行回数を１回に固定して、シフト処理が終了する度に通常処理又はダミー減算処理を行う。
そのための最も安易な方法は、シフト処理が連続する場合には、連続するシフト処理の間に毎回ダミー減算処理を入れることである。
【００３７】
以下のアルゴリズムでは、シフト処理と、通常処理又はダミー減算処理とを交互に実行できる。図５は、このアルゴリズムのフローチャートである。これにより、通常処理又はダミー減算処理と、シフト処理とが交互に行われ、結果として、シフト処理の連続実行回数は１回に固定される。このアルゴリズムにおいて数値データａは、べき乗剰余演算のべき数ｋと同様に、漏洩すると秘密鍵の暴露につながる情報である。また、アルゴリズム中の「t=a-b」、「t=b-a」、及び「t=v+b0」がダミー減算処理である。
【００３８】
INPUT:(a,b), OUTPUT: v,
begin
b0=b; G=[1,0;0,1]; g=0;
while(b>0){
if(a>b){
if(a%2<b%2){  t=a-b; T=[1,-1;0,1]*G; }
else{         a=a-b; G=[1,-1;0,1]*G; }
if(a%2==0){   a=a/2; G=[1,0;0,2]*G; g=g+1; }else
if(b%2==0){   b=b/2; G=[2,0;0,1]*G; g=g+1; }
}else{
if(b%2<a%2){  t=b-a; T=[1,0;-1,1]*G; }
else{         b=b-a; G=[1,0;-1,1]*G; }
if(a%2==0){   a=a/2; G=[1,0;0,2]*G; g=g+1; }else
if(b%2==0){   b=b/2; G=[2,0;0,1]*G; g=g+1; }
}
}
v=G[1,1];
while(g>0){
if(v%2!=0){ v=v+b0; }else{ t=v+b0; } v=v/2; g=g-1;
}
return(v);
end;
【００３９】
「/」は除算、「%」は剰余算である。「[]」は配列又は行列で、「[i11,i12; i21,i22]」ならば２行２列の行列を表す。「Y[i,j]」は行列Ｙのｉ行ｊ列目の要素を表す。大文字と小文字は別変数である。
【００４０】
１つ目の「while」ループ（以下、「第１ループ」という。）の開始時の数値データａ,ｂの値の状態、具体的には、数値データａ,ｂの大小、数値データａ,ｂのそれぞれが偶数か奇数かによって８個のルートに分岐する。このアルゴリズムであれば、どのルートであっても、加減算処理部１２２による減算処理とシフト処理部１２３によるシフト処理とが１回ずつ実行される。
【００４１】
a>b,   a%2=0, b%2=0 → a=a-b, a=a/2
a>b,   a%2=0, b%2=1 → t=a-b, a=a/2（ダミー減算処理）
a>b,   a%2=1, b%2=0 → a=a-b, b=b/2
a>b,   a%2=1, b%2=1 → a=a-b, a=a/2
a<=b,  a%2=0, b%2=0 → b=b-a, a=a/2
a<=b,  a%2=0, b%2=1 → b=b-a, a=a/2
a<=b,  a%2=1, b%2=0 → t=b-a, b=b/2（ダミー減算処理）
a<=b,  a%2=1, b%2=1 → b=b-a, b=b/2
【００４２】
判別部１２１が、数値データａが数値データｂよりも大きく且つ数値データａを「２」で除算したときの剰余（a%2）が「０」（数値データａが偶数）、剰余（b%2）が「１」（数値データｂが奇数）であると判別したとき、あるいは数値データｂが数値データａ以上で数値データｂを２で除算したときの剰余（b%2）が「０」（数値データｂが偶数）、剰余（a%2）が「１」（数値データａが奇数）であると判別したときに、制御部１２５は、ダミー減算処理を実行する。すなわち、ダミー減算処理が実行されるのは、３つの条件がそろった場合（ (a>b) ＆ (a%2=0) ＆ (b%2=1) ）などのときである。
ダミー減算処理では、数値データａ,ｂは更新されず、一時データｔとして記憶部１７に格納される。一時データｔは逆元演算の通常処理には関与しないために、ダミー減算処理が通常処理の処理結果に影響を与えることはない。この場合、制御部１２５は、本発明のダミー演算処理手段の機能を有する。
【００４３】
このようなダミー演算処理（上記例では、ダミー減算処理）により、逆元演算の結果を有効にしつつ秘密情報の漏洩につながるサイドチャネル情報を外部で認知できなくする。また、通常処理の途中にダミー演算処理を実行するので、毎回ダミー演算処理を挿入するよりも効率がよい。例えば、ａ＝１０、ｂ＝２３の場合は、第１ループが以下のような処理になる。この例では、最後から２番目にダミー減算処理が開始される。また、減算処理とシフト処理とが交互に行われるために、シフト処理の回数から秘密鍵が漏洩することはない。
【００４４】
処理            ; 処理後の値
b=b-a，a=a/2    ; a=5, b=13
b=b-a，b=b/2    ; a=5, b=4
a=a-b，b=b/2    ; a=1, b=2
t=b-a，b=b/2    ; a=1, b=1（ダミー減算処理）
b=b-a，b=b/2    ; a=1, b=0
【００４５】
図７ｂは、このような第１の対策により得られる消費電力の変化パタン（時間と共に変化するパタン）の例示図である。図７ａに表す通常処理による消費電力の変化パタンは、サイドチャネル情報として有用である。しかし、図７ｂでは、減算処理とシフト処理とが交互に行われ、また、ダミー減算処理と通常処理による減算処理との区別がつかないので、サイドチャネル情報として用いることが困難になる。
【００４６】
＜第２の対策＞
第２の対策としては、数値データａ,ｂを乱数などを用いてスクランブルし、逆元演算による数値データの最終更新前に逆スクランブルすることにより復元することにより、実際に逆元演算で処理される値をわかりづらくする。例えば、スクランブル部１２４が乱数生成部１４から乱数Ｒ１とＲ２とを取得して、数値データａを「a'=a+R１＊b」として変換し、数値データｂを「ｂ’＝ｂ＊Ｒ２」と変換する。ここで、Ｒ２は奇数で、「ｇｃｄ（ａ’，Ｒ２）＝１」である乱数を使用する。
これにより剰余演算の性質から、「v' = 1/a' mod b'」とすると、「v' mod b= 1/(a+R*b) mod b=1/a mod b」となる。
最終更新前に逆スクランブルとして、「v=v'mod b」を行うことにより、正しい逆元演算処理結果を求めて出力する。
但し、Ｒ２＝１にすれば最後の逆スクランブルは不要にできる。
【００４７】
このように、実際に逆元演算で更新される数値データをスクランブル／逆スクランブルすることで、公開情報との関係を切断でき、サイドチャネル情報から秘密情報を求めることができなくなる。この対策は、数値データａ,ｂに関する情報を利用した攻撃を阻止できる。第三者がサイドチャネル情報のみから数値データａ,ｂを復元することが困難になる。
【００４８】
＜第３の対策＞
第３の対策としては、加減算処理部１２２による加減算処理の内容（数値データａを更新するか、数値データｂを更新するか）を、ランダムに変更して行うことで、サイドチャネル情報に“不規則な要素”を含ませる。また、逆元演算による数値データの更新では、数値データa,bの条件と、その条件に対して正しい演算結果が得られる演算の組み合わせを複数用意し、ランダムに得られた不規則な要素にもとづいて、前記組み合わせを選択して演算することにより、有効な逆元演算の結果を得る。これによって数値データａ,ｂの値の更新が不規則になり、観察したサイドチャネル情報から数値データａ,ｂを復元することが困難になる。
【００４９】
以下のアルゴリズムは、「a=a-b」と「b=b-a」の処理分岐を乱数によって反転させる例である。図６は、このアルゴリズムのフローチャートである。この処理分岐は、判別部１２１による数値データａ,ｂの偶数、奇数判別、数値データａ,ｂの絶対値の差と乱数の乗算結果の正負判別、及び数値データａ,ｂの乗算結果の正負判別により決まる。乱数部分が「random(100)-50)」であるので、この乱数は負の値をとり得る。乱数は、例えば乱数発生部１４から取得する。
【００５０】
INPUT:(a,b), OUTPUT: v,
begin
b0=b; G=[1,0;0,1]; g=0; s=0; 
while(abs(b)>0){
if(a%2==0){       a=a/2; G=[1,0;0,2]*G; g=g+1; }else
if(b%2==0){       b=b/2; G=[2,0;0,1]*G; g=g+1; }else
if((abs(a)-abs(b))*(random(100)-50))>0){
if(a*b>0){    a=a-b; G=[1,-1;0,1]*G; }
else{         a=a+b; G=[1,+1;0,1]*G; }
}else{
if(a*b>0){    b=b-a; G=[1,0;-1,1]*G; }
else{         b=b+a; G=[1,0;+1,1]*G; }
} 
}
if(a>0){ v=G[1,1]; }else{ v=-G[1,1]; }
while(g>0){
if(v%2!=0){ v=v+b0; }else{ t=v+b0; } v=v/2; g=g-1;
}
return(v) ;
end;
【００５１】
数値データａ,ｂの符号が同じ場合には、max(|a|,|b|)>|a-b|が成立するため、「a=a-b」あるいは「b=b-a」という処理を行っても、max(|a|,|b|)は増加することはない。
|a|>|b|のときに「a=a-b」を行えば、max(|a|,|b|)は減少し、|a|>|b|のときに「b=b-a」を行えば、max(|a|,|b|)は不変である（|a|<|b|のときはその逆になる）。また、数値データａ,ｂの符号が異なる場合には、max(|a|,|b|) > |a+b|が成立するため、「a=a+b」あるいは「b=b+a」という処理を行っても、max(|a|,|b|)は増加することはない。|a|>|b|のときに「a=a+b」を行えば、max(|a|,|b|)は減少し、|a|>|b|のときに「b=b+a」を行えば、max(|a|,|b|)は不変である。
よって圧倒的な確率で、max(|a|,|b|)は「０」に近づき、第１ループは収束する。例えば、「a=11、b=23」の場合は、第１ループは、以下のように収束する。
処理     ; 処理後の値
b=b-a    ; a=11, b=12
b=b/2    ; a=11, b=6
b=b/2    ; a=11, b=3
b=b-a    ; a=11, b=-8
b=b/2    ; a=11, b=-4
b=b/2    ; a=11, b=-2
b=b/2    ; a=11, b=-1
a=a+b    ; a=10, b=-1
a=a/2    ; a=5, b=-1
b=b+a    ; a=5, b=4
b=b/2    ; a=5, b=2
b=b/2    ; a=5, b=1
a=a-b    ; a=4, b=1
a=a/2    ; a=2, b=1
a=a/2    ; a=1, b=1
b=b-a    ; a=1, b=0
このように、制御部１２５は、本発明のリカバリ手段の機能を有する。
【００５２】
また、「a=a-b」、「a=a+b」、「b=b-a」、「b=b+a」の４パターンにあわせてＧの処理も用意する。すなわち、次のような処理を行う。
「a=a-b」の場合は、G=[1,-1;0,１]*G、
「a=a+b」の場合は、G=[1,+1;0,1]*G、
「b=b-a」の場合は、G=[1,0;-1,1]*G、
「b=b+a」の場合は、G=[1,0;+1,1]*G。
これにより、第１ループで不規則な要素を発生させても、ａ，ｂ，Ｇの相互関係は正しく保持されるため、正しく逆元演算することができる。
【００５３】
図７ｃは、このような第３の対策により得られる消費電力の時間変化の例示図である。図７ｃでは、発生させた不規則な要素によってサイドチャネル情報が図７ａとは異なる形になっている。また、「a=a-b」、「a=a+b」、「b=b-a」、「b=b+a」の４パターンは、加算か減算かという違いであり、加算も減算もどちらも消費電力はほとんど同一であるので、エラー又はノイズによって４パターンのどの処理を行ったかのを見分けることはできない。そのために、観察したサイドチャネル情報から数値データａ,ｂを復元することが困難になる。
【００５４】
このように、本実施形態による暗号モジュール１では、逆元演算に対するサイドチャネル攻撃への対策を種々講じることができる。逆元演算のサイドチャネル情報としては、図７ａのような減算処理時とシフト処理時との消費電力の相違に基づくものがある。しかし、第１、第３の対策を施した逆元演算により得られるサイドチャネル情報は、ダミー演算処理である減算処理や処理分岐の判断を、乱数によりランダムに間違わせることで、分岐先を変えることで、図７ｂ、図７ｃのように単調なもの、あるいはノイズを含むものとなり、そのままではサイドチャネル情報としては無用なものにする。そのため、悪意の第三者がＲＳＡ鍵生成やＤＳＡ署名生成などのデジタル署名アルゴリズムで行われる逆元演算からサイドチャネル情報を取得して、秘密情報を得ることが著しく困難になる。これにより秘密情報が漏洩しにくくなり、セキュリティ性が格段に向上する。
【図面の簡単な説明】
【００５５】
【図１】本発明を適用した暗号モジュールのハードウェア構成図。
【図２】本実施形態による暗号モジュールの機能ブロック図。
【図３】ＲＳＡ鍵生成処理の処理手順図。
【図４】ＤＳＡ署名生成処理の処理手順図。
【図５】第１の対策のフローチャート。
【図６】第３の対策のフローチャート。
【図７ａ】消費電力の変化パタン（時間変化）の例示図。
【図７ｂ】消費電力の変化パタン（時間変化）の例示図。
【図７ｃ】消費電力の変化パタン（時間変化）の例示図。
【符号の説明】
【００５６】
１…暗号モジュール、１０…ＣＰＵ、２０…Ｉ／Ｏインタフェース、３０…メモリ、３１…プログラムメモリ、３２…データメモリ、１１…べき乗剰余演算部、１２…逆元演算部、１２１…判別部、１２２…加減算処理部、１２３…シフト処理部、１２４…スクランブル部、１２５…制御部、１３…素数生成部、１４…乱数生成部、１５…ＲＳＡ鍵生成部、１６…ＤＳＡ署名生成部、１７…記憶部。
【図１】
0005214317.tif 000004
【図２】
0005214317.tif 000005
【図３】
0005214317.tif 000006
【図４】
0005214317.tif 000007
【図５】
0005214317.tif 000008
【図６】
0005214317.tif 000009
【図７ａ】
0005214317.tif 000010
【図７ｂ】
0005214317.tif 000011
【図７ｃ】
0005214317.tif 000012