(57)【要約】【課題】Ｘｐ−Ｘｑの符号を利用したサイドチャネルアタックに対する有効な防御方法を提供する。【解決手段】半導体装置（３）は、中国人剰余定理を用いたアルゴリズムによってＲＳＡ暗号による暗号文Ｘを復号する。秘密鍵ｄ、ｐ、ｑに対して、Ｄｐ＝ｄｍｏｄ（ｐ−１）、Ｄｑ＝ｄｍｏｄ（ｑ−１）、Ｘｐ＝ＸDpｍｏｄｐ、Ｘｑ＝ＸDqｍｏｄｑとしたとき、半導体装置（３）には、Ｘｐ−Ｘｑを格納する第１のレジスタ（ＲＥ１）と、Ｘｐ−Ｘｑ＋ｐを格納する第２のレジスタ（ＲＥ２）とが設けられる。演算器（１０）は、Ｘｐ−Ｘｑの符号が正の場合に第１のレジスタ（ＲＥ１）に格納されている値を用いて平文Ｙを求め、Ｘｐ−Ｘｑの符号が負の場合に第２のレジスタ（ＲＥ２）に格納されている値を用いて平文Ｙを求める。【選択図】図５
2014081426.tif 000002
【特許請求の範囲】
【請求項１】
半導体装置であって、
第１〜第３のレジスタと、
セレクタと、
秘密鍵ｄ、ｐおよびｑを用いてＲＳＡ暗号による暗号文Ｘを復号する演算器とを備え、
前記演算器は、
ｄをｐ−１で割った余りＤｐを用いて、Ｘｐ＝ＸDpｍｏｄｐを求め、
ｄをｑ−１で割った余りＤｑを用いて、Ｘｑ＝ＸDqｍｏｄｑを求め、
Ｘｐ−Ｘｑの演算結果を前記第１のレジスタに格納し、Ｘｐ−Ｘｑ＋ｐの演算結果を前記第２のレジスタに格納するように構成されており、
前記セレクタは、Ｘｐ−Ｘｑの符号が正または０の場合に前記第１のレジスタに格納されている値を前記第３のレジスタに転送し、Ｘｐ−Ｘｑの符号が負の場合に前記第２のレジスタに格納されている値を前記第３のレジスタに転送するように構成されており、
前記演算器は、さらに、
前記第３のレジスタに格納されている値Ａとｐを法とするｑの逆元ｑ-1とを用いて、ｗ＝Ａ×ｑ-1ｍｏｄｐを求め、
平文Ｙ＝ｗ×ｑ＋Ｘｑを求めるように構成されている、半導体装置。
【請求項２】
半導体装置であって、
第１〜第３のレジスタと、
セレクタと、
第１の値または第２の値を有する切替信号を発生する信号発生器と、
秘密鍵ｄ、ｐおよびｑを用いてＲＳＡ暗号による暗号文Ｘを復号する演算器とを備え、
前記演算器は、
ｄをｐ−１で割った余りＤｐを用いて、Ｘｐ＝ＸDpｍｏｄｐを求め、
ｄをｑ−１で割った余りＤｑを用いて、Ｘｑ＝ＸDqｍｏｄｑを求め、
前記切替信号が前記第１の値の場合、Ｘｐ−Ｘｑの演算結果を前記第１のレジスタに格納し、Ｘｐ−Ｘｑ＋ｐの演算結果を前記第２のレジスタに格納し、
前記切替信号が前記第２の値の場合、Ｘｐ−Ｘｑの演算結果を前記第２のレジスタに格納し、Ｘｐ−Ｘｑ＋ｐの演算結果を前記第１のレジスタに格納するように構成されており、
前記セレクタは、
前記切替信号が前記第１の値の場合、Ｘｐ−Ｘｑの符号が正または０のときに前記第１のレジスタに格納されている値を前記第３のレジスタに転送し、Ｘｐ−Ｘｑの符号が負のときに前記第２のレジスタに格納されている値を前記第３のレジスタに転送し、
前記切替信号が前記第２の値の場合、Ｘｐ−Ｘｑの符号が正または０のときに前記第２のレジスタに格納されている値を前記第３のレジスタに転送し、Ｘｐ−Ｘｑの符号が負のときに前記第１のレジスタに格納されている値を前記第３のレジスタに転送するように構成されており、
前記演算器は、さらに、
前記第３のレジスタに格納されている値Ａとｐを法とするｑの逆元ｑ-1とを用いて、ｗ＝Ａ×ｑ-1ｍｏｄｐを求め、
平文Ｙ＝ｗ×ｑ＋Ｘｑを求めるように構成されている、半導体装置。
【請求項３】
秘密鍵ｄ、ｐおよびｑを用いてＲＳＡ暗号による暗号文Ｘを復号する演算器によって実行される暗号処理方法であって、
ｄをｐ−１で割った余りをＤｐとし、ｐより大きい２のべき乗数をＲとしたとき、前記演算器が、Ｘｐ＝ＸDpｍｏｄｐで表わされるＸｐのモンゴメリ変換である、
Ｍ（Ｘｐ）＝ＸDp×Ｒｍｏｄｐを求めるステップと、
ｄをｑ−１で割った余りＤｑとしたとき、前記演算器が、Ｘｑ＝ＸDqｍｏｄｑで表わされるＸｑのモンゴメリ変換であるＭ（Ｘｑ）＝（ＸDqｍｏｄｑ）×Ｒｍｏｄｐを求めるステップと、
前記演算器が、ｐを法とするｑの逆元ｑ-1のモンゴメリ変換である、
Ｍ（ｑ-1）＝ｑ-1×Ｒｍｏｄｐを求めるステップと、
ｐを法とするＲの逆元をＲ-1としたとき、前記演算器が、Ｍ（Ｘｐ）−Ｍ（Ｘｑ）とＭ（ｑ-1）とのモンゴメリ乗算剰余である、
Ｍ（ｗ）＝（Ｍ（Ｘｐ）−Ｍ（Ｘｑ））×Ｍ（ｑ-1）×Ｒ-1ｍｏｄｐを求めるステップと、
前記演算器が、Ｍ（ｗ）のモンゴメリ逆変換であるｗ＝Ｍ（ｗ）×Ｒ-1ｍｏｄｐを求めるステップと、
前記演算器が、平文Ｙ＝ｗ×ｑ＋Ｘｑを求めるステップとを備えた暗号処理方法。
【請求項４】
前記Ｍ（Ｘｐ）を求めるステップは、モンゴメリ乗算剰余演算の繰り返しによって実行される、請求項３に記載の暗号処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号処理を行なう半導体装置および暗号処理方法に関し、たとえば、ＲＳＡ暗号のサイドチャネルアタックに対する防御に好適のために用いられるものである。
【背景技術】
【０００２】
暗号方式は、暗号および復号ともに同じ鍵を使う共通鍵方式と、暗号と復号とで異なる鍵を使う公開鍵方式に大別される。公開鍵暗号方式では、暗号化鍵が公開にされ、復号化鍵が秘密にされる。
【０００３】
公開鍵暗号方式のうちで最もよく使われるものがＲＳＡ暗号である。ＲＳＡ暗号では、大きな素数ｐ，ｑの積Ｎ（すなわち、Ｎ＝ｐ×ｑ）を計算することは容易であるが、Ｎから素因数ｐ，ｑを見出すことが困難な点を利用している。具体的には、
１＝ｅ×ｄｍｏｄ（ｐ−１）（ｑ−１）      …(1)
を満たすｅ，ｄを用いて、平文Ｙから、
Ｘ＝ＹeｍｏｄＮ      …(2)
によって暗号文Ｘが計算される。上式（２）のｅ、Ｎが公開鍵として公開される。復号化では、暗号文Ｘから、
Ｙ＝ＸdｍｏｄＮ      …(3)
によって平文Ｙが計算される。ｄ、ｐ、ｑが秘密鍵である。
【０００４】
復号時の計算量の軽減のために中国人剰余定理（ＣＲＴ：Chinese  Remainder  Theorem）を用いたアルゴリズムがよく利用される。ＣＲＴを用いた場合、以下の式（４）〜（９）に従って、暗号文Ｘから平文Ｙが計算される。計算量は約１／４に軽減される。
【０００５】
Ｄｐ＝ｄｍｏｄ（ｐ−１）      …(4)
Ｄｑ＝ｄｍｏｄ（ｑ−１）      …(5)
Ｘｐ＝ＸDpｍｏｄｐ      …(6)
Ｘｑ＝ＸDqｍｏｄｑ      …(7)
ｗ＝（Ｘｐ−Ｘｑ）×ｑ-1ｍｏｄｐ      …(8)
Ｙ＝ｗ×ｑ＋Ｘｑ      …(9)
ただし、上式（８）において、ｑ-1は、ｐを法とするｑの逆元である（すなわち、１≡ｑ×ｑ-1（ｍｏｄｐ））。
【０００６】
ＲＳＡ暗号は、暗号方式自体は安全性の高いものであるが、実装方式が脆弱であると悪意ある攻撃者に秘密鍵が盗まれてしまう場合がある。一般に、暗号装置が暗号処理する際に生じる消費電力、電磁波、または処理時間といった物理情報を解析することで暗号鍵を取得する攻撃法をサイドチャネルアタックと称する。サイドチャネルアタックの代表例が電力解析攻撃である。
【０００７】
電力解析攻撃では、単一の消費電流波形の特徴を解析する単純電力解析（ＳＰＡ：Single  Power  Analysis）と、多数の電力消費データの差分を解析する差分電力解析（ＤＰＡ：Differential  Power  Analysis）とが知られている。これらの攻撃法は、上記のＣＲＴを用いたＲＳＡ暗号の復号アルゴリズムに対しても適用可能であり、有効な防御法が必要とされている。
【０００８】
たとえば、特開２００２−２６１７５３号公報（特許文献１）は、ＳＰＡに対する防御方法を開示している。特開２０１０−１６６４６３号公報（特許文献２）は、べき乗剰余演算の消費電力を繰り返し観察することによってｐ、ｑの値を推定するＤＰＡに対する防御方法を開示している。特開２００６−２１７１９３号公報（特許文献３）は、上式（９）におけるｗ×ｑの演算における消費電力を繰り返し観察することによってｑの値を推定するＤＰＡに対する防御方法を開示している。
【０００９】
他の電力解析攻撃法として、Ｎｏｖａｋは、上式（８）におけるＸｐ−Ｘｑの符号によって消費電流波形に違いが生じることを利用してｐの値を推定する攻撃法を開示している（Roman  Novak,  "SPA-Based  Adaptive  Chosen-Ciphertext  Attack  on  RSA  Implementation",  Lecture  Notes  in  Computer  Science,  Vol.  2274,  Springer-Verlag,  2002,  p.252-262（非特許文献１）参照）。具体的にＮｏｖａｋの文献によれば、Ｙの値がｐの倍数のとき、Ｘｐ−Ｘｑの符号が正から負に変化することが示される。ここで、通常の実装では、Ｘｐ−Ｘｑの演算においてＸｐ−Ｘｑの値が負になれば、Ｘｐ−Ｘｑ＋ｐの演算が行なわれるので、消費電流波形を観察することによってＸｐ−Ｘｑが正から負に変化するタイミングを検知できる。この結果、ｐの値の推定が可能になる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００２−２６１７５３号公報
【特許文献２】特開２０１０−１６６４６３号公報
【特許文献３】特開２００６−２１７１９３号公報
【非特許文献】
【００１１】
【非特許文献１】Roman  Novak,  "SPA-Based  Adaptive  Chosen-Ciphertext  Attack  on  RSA  Implementation",  Lecture  Notes  in  Computer  Science,  Vol.  2274,  Springer-Verlag,  2002,  p.252-262
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記のＮｏｖａｋの文献に記載されたサイドチャネルアタックに対する有効な防御方法はこれまで明らかになっていない。その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１３】
一実施の形態による半導体装置は、中国人剰余定理を用いたアルゴリズムによってＲＳＡ暗号による暗号文Ｘを復号する。秘密鍵ｄ、ｐ、ｑに対して、Ｄｐ＝ｄｍｏｄ（ｐ−１）、Ｄｑ＝ｄｍｏｄ（ｑ−１）、Ｘｐ＝ＸDpｍｏｄｐ、Ｘｑ＝ＸDqｍｏｄｑとしたとき、半導体装置には、Ｘｐ−Ｘｑを格納する第１のレジスタと、Ｘｐ−Ｘｑ＋ｐを格納する第２のレジスタとが設けられる。演算器は、Ｘｐ−Ｘｑの符号が正の場合に第１のレジスタに格納されている値を用いて平文Ｙを求め、Ｘｐ−Ｘｑの符号が負の場合に第２のレジスタに格納されている値を用いて平文Ｙを求める。
【発明の効果】
【００１４】
上記の一実施の形態によれば、上記のＮｏｖａｋの文献に記載されたサイドチャネルアタックに対して有効に防御できる。
【図面の簡単な説明】
【００１５】
【図１】各実施の形態で防御の対象としているサイドチャネルアタックの手順を示すフローチャートである。
【図２】平文Ｙの値とＸｐ−Ｘｑの符号との関係を示す図である。
【図３】ＲＳＡ暗号の復号処理の際の消費電流波形の一例を示す図である。
【図４】実施の形態１による半導体装置の構成を示すブロック図である。
【図５】図４のコプロセッサの構成を示すブロック図である。
【図６】図５のコプロセッサによるＲＳＡ暗号の復号手順を示すフローチャートである。
【図７】実施の形態２によるコプロセッサの構成を示すブロック図である。
【図８】図７のコプロセッサによるＲＳＡ暗号の復号手順を示すフローチャートである。
【図９】実施の形態３によるコプロセッサの構成を示すブロック図である。
【図１０】実施の形態３によるＲＳＡ暗号の復号手順を示すフローチャートである。
【発明を実施するための形態】
【００１６】
＜サイドチャネルアタックについて＞
まず、以下の各実施の形態で防御の対象としているサイドチャネルアタックについて説明する。
【００１７】
図１は、各実施の形態で防御の対象としているサイドチャネルアタックの手順を示すフローチャートである。図１を参照して、攻撃者は、まず任意に決定した平文Ｙに対して、公開鍵ｅおよびＮを用いて暗号文Ｘを作成する（ステップＳ１００、Ｓ１０５）。具体的には、前述の式（２）で表わされるＸを求める。
【００１８】
次に攻撃者は、作成した暗号文Ｘを暗号処理チップに受信させ、暗号文Ｘの復号時の消費電流を測定する（ステップＳ１１０）。以上のステップを、Ｙを連続的に変化させながら繰り返す。Ｙと消費電流波形との関係を表わすデータが十分に得られたら（ステップＳ１１５でＮＯ）、攻撃者は、以下で説明する消費電流波形のタイミング解析を行なう（ステップＳ１２０）。なお、ステップＳ１１０において消費電流に代えてチップから放射される電磁波を測定し、ステップＳ１２０で電磁波の波形を解析するようにしても構わない。
【００１９】
前述のＮｏｖａｋの文献によれば、平文Ｙの値を引数とする関数ｄｉｆｆ（Ｙ）が定義される。ｄｉｆｆ（Ｙ）の値は、前述の式（８）におけるＸｐ−Ｘｑの符号に応じて変化する。すなわち、
ｄｉｆｆ（Ｙ）＝０  ただし、Ｘｐ−Ｘｑ≧０      …(10A)
ｄｉｆｆ（Ｙ）＝１  ただし、Ｘｐ−Ｘｑ＜０      …(10B)
と定義される。Ｎｏｖａｋは、ｄｉｆｆ（Ｃ−１）＝０かつｄｉｆｆ（Ｃ）＝１となるＣの値がｐの倍数になること、すなわち、Ｘｐ−Ｘｑの値が正から負に切替わるときＹの値がｐの倍数になることを指摘している。
【００２０】
図２は、平文Ｙの値とＸｐ−Ｘｑの符号との関係を示す図である。図２に示すように、Ｘｐ−Ｘｑが正から負に切替わるときのＹの値がｐの倍数になる。
【００２１】
従来の実装では、ｄｉｆｆ（Ｙ）＝１の場合すなわちＸｐ−Ｘｑ＜０の場合、Ｘｐ−Ｘｑの値を正にするためにｐを加算することによりＸｐ−Ｘｑ＋ｐが計算される。そうすると、ｄｉｆｆ（Ｙ）＝０の場合とｄｉｆｆ（Ｙ）＝１の場合とで処理内容が異なるので、消費電流波形が変化する。
【００２２】
図３は、ＲＳＡ暗号の復号処理の際の消費電流波形の一例を示す図である。図３（Ａ）のグラフがｄｉｆｆ（Ｙ）＝１の場合すなわちＸｐ−Ｘｑ＜０の場合を示し、図３（Ｂ）のグラフがｄｉｆｆ（Ｙ）＝０の場合すなわちＸｐ−Ｘｑ≧０の場合を示す。
【００２３】
図３（Ａ）の場合と図３（Ｂ）の場合とで符号ＡＰ１で示した区間は消費電流波形が同じであるので、暗号処理チップは同一の処理を行なっている。しかしながら、処理が行なわれるタイミングは異なり、図３（Ａ）の場合のほうが遅れている。この理由は、図３（Ａ）の場合はＸｐ−Ｘｑ＜０であるので、Ｘｐ−Ｘｑの値を正にするためにｐを加算する処理が、符号ＡＰ１で示した区間より前で行なわれているからである。
【００２４】
したがって、同一の消費電流波形が観測されるタイミングに着目すれば、ｄｉｆｆ（Ｙ）が０であるか１であるかを判別することができる。そして、Ｙを連続的に変化させたときに消費電流波形からｄｉｆｆ（Ｙ）が０から１に変化したときのＹの値を特定することによって、ｐの値を推定することができる。
【００２５】
以下の各実施の形態では、上記のサイドチャネルアタックに対する防御手段が実装された半導体装置および暗号処理方法について図面を参照して詳しく説明する。なお、同一または相当する部分には同一の参照符号を付して、その説明を繰返さない場合がある。
【００２６】
＜実施の形態１＞
［半導体装置の全体構成］
図４は、実施の形態１による半導体装置の構成を示すブロック図である。図４を参照して、半導体装置（暗号処理チップ）１は、チップ全体を制御するＣＰＵ（Central  Processing  Unit）２と、暗号処理（暗号化および復号）を行なうコプロセッサ３と、入出力回路４と、メモリ（ＲＡＭ（Random  Access  Memory）およびＲＯＭ（Read  Only  Memory））５とを含む。暗号文および平文は、入出力回路４を介してチップに入出力される。ＲＯＭは、フラッシュメモリなどのＥＥＰＲＯＭ（Electrically  Erasable  Programmable  Read-Only  Memory）によって構成してもよい。各機能ブロックは、バス６を介して相互に接続される。
【００２７】
［暗号処理用のコプロセッサの構成］
図５は、図４のコプロセッサの構成を示すブロック図である。図５を参照して、コプロセッサ３は、ＲＳＡ暗号処理のための演算を行なう演算器１０と、レジスタ群１１とを含む。レジスタ群１１は、暗号文、平文、暗号鍵、および計算の中途段階の値などを格納する。演算器１０には、各機能ブロック間の信号の制御を行なうコントローラも設けられている。
【００２８】
コプロセッサ３は、さらに、前述のＮｏｖａｋの文献に記載されたサイドアタック攻撃を防御するために設けられたデータ処理部２０を含む。データ処理部２０は、レジスタＲＥ１〜ＲＥ３と、セレクタ２１とを含む。
【００２９】
レジスタＲＥ１は、演算器１０によって計算されたＸｐ−Ｘｑ（＝Ｂ１）を格納する。ただし、ＸｐおよびＸｑは前述の式（６）、（７）（次式（１６）、（１７））で表わされる値である。
【００３０】
レジスタＲＥ２は、演算器１０によって計算されたＸｐ−Ｘｑ＋ｐ（＝Ｂ１＋ｐ＝Ｂ２）を格納する。
【００３１】
セレクタ２１は、レジスタＲＥ１の最上位ビットの値（サインフラグ）すなわちＢ１の符号に応じて、Ｂ１の符号が正または０のとき（すなわち、サインフラグが０のとき）、レジスタＲＥ１を自動的に選択する。これにより、レジスタＲＥ１に格納されているＢ１がレジスタＲＥ３に転送される。セレクタ２１は、Ｂ１の符号が負のとき（すなわち、サインフラグが１のとき）、レジスタＲＥ２を自動的に選択する。これにより、レジスタＲＥ２に格納されているＢ２がレジスタＲＥ３に転送される。Ｂ１またはＢ２の転送後のレジスタＲＥ３の値をＡとする。演算器１０は、レジスタＲＥ３の値Ａに基づいて、平文Ｙを求める。
【００３２】
［コプロセッサの復号時の動作］
図６は、図５のコプロセッサによるＲＳＡ暗号の復号手順を示すフローチャートである。
【００３３】
図５、図６を参照して、まず、図４の入出力回路４を介して、暗号文Ｘがレジスタ１２に入力される（ステップＳ２００）。暗号文Ｘは、公開鍵ｅ、Ｎを用いて平文Ｙを、
Ｘ＝ＹeｍｏｄＮ      …(11)
に従って暗号化したものである。ただし、素数ｐ、ｑを用いて、
Ｎ＝ｐ×ｑ      …(12)
１＝ｅ×ｄｍｏｄ（ｐ−１）（ｑ−１）      …(13)
の関係が成り立つ。公開鍵ｅ、Ｎおよび秘密鍵ｄ、ｐ、ｑは図１のメモリ５に格納されており、暗号処理時にレジスタ群１１に転送される。
【００３４】
次に、演算器１０は、秘密鍵ｄをｐ−１で割った余りＤｐ、およびｄをｑ−１で割った余りＤｑを求める（ステップＳ２０５）。すなわち、演算器１０は、
Ｄｐ＝ｄｍｏｄ（ｐ−１）      …(14)
Ｄｑ＝ｄｍｏｄ（ｑ−１）      …(15)
で表わされるＤｐ、Ｄｑを求める。式（１４）、式（１５）で表わされるＤｐ、Ｄｑは、予め計算して図１のメモリ５に格納しておき、暗号処理時に読み出されるようにしてもよい。
【００３５】
次に、演算器１０は、
Ｘｐ＝ＸDpｍｏｄｐ      …(16)
Ｘｑ＝ＸDqｍｏｄｑ      …(17)
で表わされるＸｐ、Ｘｑを求め、演算結果をレジスタ１３，１４にそれぞれ格納する（ステップＳ２１０，Ｓ２１５）。式（１６）および（１７）のべき乗剰余演算は、公知のモンゴメリ乗算剰余アルゴリズムを繰り返し用いることによって、除算を実質的に行なわずに、乗算、加算およびシフト演算のみで実行することができる。
【００３６】
次に、演算器１０は、ＸｐからＸｑを減じた値Ｂ１、すなわち、
Ｂ１＝Ｘｐ−Ｘｑ      …(18)
で表わされるＢ１を求めて、求めたＢ１をレジスタＲＥ１に格納する（ステップＳ２２０）。さらに、演算器１０は、Ｂ１にｐを加算した値Ｂ２、すなわち、
Ｂ２＝Ｂ１＋ｐ      …(19)
で表わされるＢ２を求めて、求めたＢ２をレジスタＲＥ２に格納する(ステップＳ２２５）。
【００３７】
次に、レジスタＲＥ１またはＲＥ２からレジスタＲＥ３へのデータ転送を実施する（ステップＳ２３５，Ｓ２４０）。セレクタ２１は、レジスタＲＥ１のサインフラグが０のとき（すなわち、Ｂ１≧０のとき、ステップＳ２３０でＹＥＳ）、レジスタＲＥ１を自動的に選択する。これにより、レジスタＲＥ１からレジスタＲＥ３へデータＢ１が転送される（ステップＳ２３５）。セレクタ２１は、レジスタＲＥ１のサインフラグが１のとき（すなわち、Ｂ１＜０のとき、ステップＳ２３０でＮＯ）、レジスタＲＥ２を自動的に選択する。これにより、レジスタＲＥ２からレジスタＲＥ３にデータＢ２が転送される（ステップＳ２４０）。
【００３８】
次に、演算器１０は、レジスタＲＥ３に格納されている値Ａ（Ｂ１またはＢ２が転送されたもの）を用いて、
ｗ＝Ａ×ｑ-1ｍｏｄｐ      …(20)
に従ってｗを求める（ステップＳ２４５）。ただし、ｑ-1は、ｐを法とするｑの逆元である。さらに、演算器１０は、
Ｙ＝ｗ×ｑ＋Ｘｑ      …(21)
に従って、平文Ｙを求める（ステップＳ２５０）。
【００３９】
［実施の形態１の効果］
図６のステップＳ２３５およびＳ２４０の実行時において、図５のセレクタ２１は、レジスタＲＥ１のサインフラグの値（Ｂ１の符号）に応じて、自動的にレジスタＲＥ１に格納されたＢ１およびレジスタＲＥ２に格納されたＢ２のいずれかを選択する。これにより、Ｂ１を用いてステップＳ２４５の計算を実行する場合と、Ｂ２を用いてステップＳ２４５の計算を実行する場合とで時間差がなくなる。この結果、消費電流波形を解析しても、Ｘｐ−Ｘｑの符号を特定することが困難になる。さらに、レジスタＲＥ３のハミング重みは、Ｘｐ−Ｘｑの符号（関数ｄｉｆｆ（Ｙ）の値）によって極端に変化しない。以上により、Ｘｐ−Ｘｑの符号を利用して秘密鍵ｐが暴かれる可能性が低くなる。
【００４０】
＜実施の形態２＞
図５に示した実施の形態１のコプロセッサ３では、レジスタＲＥ１からレジスタＲＥ３までの配線インピーダンスと、レジスタＲＥ２からレジスタＲＥ３までの配線インピーダンスとに差があれば、消費電流の大きさが異なる。この消費電流の差を利用してＸｐ−Ｘｑの符号を推定することにより、秘密鍵ｐが暴かれる可能性がある。実施の形態２は、この点を防御可能な実装手段について開示する。
【００４１】
［コプロセッサの構成］
図７は、実施の形態２によるコプロセッサの構成を示すブロック図である。コプロセッサ３Ａは、コプロセッサ３に代えて図４の半導体装置１に搭載される。
【００４２】
図７を参照して、データ処理部２０Ａは、レジスタＲＥ４、切替信号発生器２２、セレクタ２３、およびＥＸ−ＯＲ（排他的論理和：Exclusive  OR）ゲート２４をさらに含む点で図５のデータ処理部２０と異なる。
【００４３】
レジスタＲＥ４は、演算器１０がＸｐ−Ｘｑの演算を行なった際のサインフラグを格納する。
【００４４】
切替信号発生器２２は、“０”または“１”の値を有する切替信号を発生する。切替信号発生器２２は、たとえば、線形帰還シフトレジスタ（ＬＦＳＲ：Linear  Feedback  Shift  Register）を含む。線形帰還シフトレジスタの初期値には、半導体装置１に設けられタイマ７の下位ビットが用いられる。切替信号発生器２２は、線形帰還シフトレジスタのいずれかのビットの値または全ビットの排他的論理和（２入力の排他的論理和をカスケード接続したもの）を切替信号として出力する。より簡単な構成では、切替信号発生器２２は、タイマの下位ビットの排他的論理和を切替信号として出力するように構成されていてもよい。切替信号発生器２２は、ＲＳＡ暗号の復号処理を実行する度に起動をかけて、新たな切替信号を出力するように制御される。これによって、切替信号の値はランダムになる。
【００４５】
演算器１０は、Ｘｐ−Ｘｑ（＝Ｂ１）およびＸｐ−Ｘｑ＋ｐ（＝Ｂ１＋ｐ＝Ｂ２）の演算を行なう。セレクタ２３は、切替信号の値が“０”のとき、演算器１０がＸｐ−Ｘｑの演算を行なう際にレジスタＲＥ１を選択し、演算器１０がＸｐ−Ｘｑ＋ｐの演算を行なう際にレジスタＲＥ２を選択する。これによって、切替信号の値が“０”のとき、演算器１０によるＸｐ−Ｘｑ（＝Ｂ１）の演算結果がレジスタＲＥ１に転送され、Ｘｐ−Ｘｑ＋ｐ（＝Ｂ１＋ｐ＝Ｂ２）の演算結果がレジスタＲＥ２に転送される。セレクタ２３は、切替信号の値が“１”のとき、演算器１０がＸｐ−Ｘｑの演算を行なう際にレジスタＲＥ２を選択し、演算器１０がＸｐ−Ｘｑ＋ｐの演算を行なう際にレジスタＲＥ１を選択する。これによって、切替信号の値が“１”のとき、演算器１０によるＸｐ−Ｘｑ（＝Ｂ１）の演算結果がレジスタＲＥ２に転送され、Ｘｐ−Ｘｑ＋ｐ（＝Ｂ１＋ｐ＝Ｂ２）の演算結果がレジスタＲＥ１に転送される。以上により、切替信号の値に応じてＢ１，Ｂ２を格納するレジスタが切替わる。
【００４６】
ＥＸ−ＯＲゲート２４は、レジスタＲＥ４に格納されているサインフラグと切替信号との排他的論理和演算の結果を出力する。セレクタ２１は、ＥＸ−ＯＲゲート２４の出力が“０”の場合に、レジスタＲＥ１を選択する。これにより、レジスタＲＥ１に格納されているデータがレジスタＲＥ３に転送される。セレクタ２１は、ＥＸ−ＯＲゲート２４の出力が“１”の場合に、レジスタＲＥ２を選択する。これにより、レジスタＲＥ２に格納されているデータがレジスタＲＥ３に転送される。
【００４７】
上記の構成によれば、切替信号が“０”の場合には、実施の形態１の場合と同様に、Ｂ１，Ｂ２がレジスタＲＥ１，ＲＥ２にそれぞれ格納される。Ｂ１≧０のとき、レジスタＲＥ１に格納されているＢ１がレジスタＲＥ３に転送され、Ｂ１＜０のとき、レジスタＲＥ２に格納されているＢ２がレジスタＲＥ３に転送される。
【００４８】
切替信号が“１”の場合には、実施の形態１の場合とは逆に、Ｂ１，Ｂ２がレジスタＲＥ２，ＲＥ１にそれぞれ格納される。Ｂ１≧０のとき、レジスタＲＥ２に格納されているＢ１がレジスタＲＥ３に転送され、Ｂ１＜０のとき、レジスタＲＥ１に格納されているＢ２がレジスタＲＥ３に転送される。
【００４９】
図７のその他の点は図５の場合と同じであるので同一または相当する部分には同一の参照符号を付して説明を繰り返さない。
【００５０】
［コプロセッサの動作］
図８は、図７のコプロセッサによるＲＳＡ暗号の復号手順を示すフローチャートである。以下では、図６のフローチャートと異なる点について主として説明し、図６と同じステップにはついては同一の参照符号を付して説明を繰り返さない場合がある。
【００５１】
図８のフローチャートは、ステップＳ２１５とステップＳ２２０との間にステップＳ２１７が追加されている点で、図６のフローチャートと異なる。ステップＳ２１７は、図７の切替信号発生器２２から出力される切替信号の値が“０”であるか否かによって処理を切替えるために設けられている。切替信号の値が“０”の場合（ステップＳ２１７でＹＥＳ）、図６の場合と同様にステップＳ２２０〜Ｓ２４０が実行される。切替信号の値が“１”の場合（ステップＳ２１７でＮＯ）、ステップＳ２２０〜Ｓ２４０に代えてステップＳ２２０Ａ〜Ｓ２４０Ａが実行される。
【００５２】
図７、図８を参照して、演算器１０が、暗号文Ｘを用いてＸｐ，Ｘｑを演算して、レジスタ１３，１４にそれぞれ格納するステップＳ２１０，Ｓ２１５までは、図６の場合と同じである。
【００５３】
次に演算器１０は、ＸｐからＸｑを減じた値Ｂ１を求める。セレクタ２３は、切替信号の値が“０”の場合、レジスタＲＥ１を選択する。これにより、求めたＢ１がレジスタＲＥ１に格納される（ステップＳ２２０）。セレクタ２３は、切替信号の値が“１”の場合、レジスタＲＥ２を選択する。これにより、求めたＢ１がレジスタＲＥ２に格納される（ステップＳ２２０Ａ）。
【００５４】
さらに、演算器１０は、Ｂ１にｐを加算した値Ｂ２を求める。セレクタ２３は、切替信号の値が“０”の場合、レジスタＲＥ２を選択する。これにより、求めたＢ２がレジスタＲＥ２に格納される（ステップＳ２２５）。セレクタ２３は、切替信号の値が“１”の場合、レジスタＲＥ１を選択する。これにより、求めたＢ２がレジスタＲＥ１に格納される（ステップＳ２２５Ａ）。
【００５５】
次に、セレクタ２１は、切替信号の値が“０”かつＢ１≧０の場合（すなわち、ＥＸ−ＯＲゲート２４の出力が“０”の場合）、レジスタＲＥ１を自動的に選択する。これにより、レジスタＲＥ１に格納されているＢ１がレジスタＲＥ３に転送される（ステップＳ２３５）。セレクタ２１は、切替信号の値が“０”かつＢ１＜０（すなわち、ＥＸ−ＯＲゲート２４の出力が“１”の場合）、レジスタＲＥ２を自動的に選択する。これにより、レジスタＲＥ２に格納されているＢ２がレジスタＲＥ３に転送される（ステップＳ２４０）。
【００５６】
一方、セレクタ２１は、切替信号の値が“１”かつＢ１≧０の場合（すなわち、ＥＸ−ＯＲゲート２４の出力が“１”の場合）、レジスタＲＥ２を自動的に選択する。これにより、レジスタＲＥ２に格納されているＢ１がレジスタＲＥ３に転送される（ステップＳ２３５Ａ）。セレクタ２１は、切替信号の値が“１”かつＢ１＜０の場合（すなわち、ＥＸ−ＯＲゲート２４の出力が“０”の場合）、レジスタＲＥ１を自動的に選択する。これにより、レジスタＲＥ１に格納されているＢ２がレジスタＲＥ３に転送される（ステップＳ２４０Ａ）。
【００５７】
その後、演算器１０は、レジスタＲＥ３に格納されている値Ａ（Ｂ１またはＢ２が転送されたもの）を用いて、前述の式（２０）に従ってｗを求め（ステップＳ２４５）、さらに前述の式（２１）に従って平文Ｙを求める（ステップＳ２５０）。
【００５８】
［実施の形態２の効果］
実施の形態２では、Ｘｐ−Ｘｑ（＝Ｂ１）の演算結果とＸｐ−Ｘｑ＋ｐ（＝Ｂ２）の演算結果をレジスタＲＥ１，ＲＥ２に格納する前に、切替信号発生器２２が起動し、０または１の値を有する切替信号を発生する。切替信号の値は、切替信号発生器２２の起動の度に０または１にランダムに変化する。Ｂ１およびＢ２が格納されるレジスタは、切替信号の値に応じて切替えられる。これによって、セレクタ２１がＢ１の符号に応じてＢ１，Ｂ２を選択する際の消費電力の大きさが一意に決まらなくなるので、サイドチャネルアタックによってＢ１，Ｂ２のどちらが選択されたかを特定することを困難になる。
【００５９】
＜実施の形態３＞
実施の形態３は、Ｘｐ，Ｘｑの値をモンゴメリ変換することによって、モンゴメリ変換後のＸｐ−Ｘｑの正負と秘密鍵ｐとの間に対応関係が生じないようにしたものである。以下では、まず、モンゴメリ変換およびモンゴメリ乗算剰余について簡単に説明する。
【００６０】
［モンゴメリ変換およびモンゴメリ乗算剰余について］
ｐを法とするＳのモンゴメリ変換Ｍ（Ｓ）は、ｐより大きい２のべき乗数Ｒを用いて、
Ｍ（Ｓ）＝Ｓ×Ｒｍｏｄｐ      …(22)
で表わされる。通常、ｐのビット数をｎとすると、Ｒ＝２nで与えられる。ｐとＲは互いに素である必要がある。Ｍ（Ｓ）のモンゴメリ逆変換は、Ｒの逆元をＲ-1として、
Ｓ＝Ｍ（Ｓ）×Ｒ-1ｍｏｄｐ      …(23)
で与えられる。
【００６１】
ＳとＴのモンゴメリ乗算剰余Ｓ＊Ｔは、
Ｓ＊Ｔ＝Ｓ×Ｔ×Ｒ-1ｍｏｄｐ      …(24)
で定義される。モンゴメリ乗算剰余は、次のアルゴリズムを用いて計算できる。
【００６２】
（Ｓ１）ｐ×ｐ’≡−１ｍｏｄＲを満たすｐ’を求める。
（Ｓ２）Ｓ×ＴｍｏｄＲの演算結果をｍに代入する。
【００６３】
（Ｓ３）ｍ×ｐ’ｍｏｄＲの演算結果をｍに代入する。
（Ｓ４）Ｓ×Ｔ＋ｍ×ｐをＲで割った値をｋに代入する。
【００６４】
（Ｓ５）ｋ＞Ｎであれば、ｋ−Ｎをｋに代入する。
（Ｓ６）ｋを出力する。
【００６５】
上記のアルゴリズムにおいて、ステップＳ１のｐ’は、たとえば、拡張されたユークリッド互除法によって予め計算しておく。ステップＳ１〜Ｓ４において、Ｒは２のべき乗数であるので、ｍｏｄＲおよびＲでの除算は、ビットをシフトするだけで計算できる。したがって、モンゴメリ乗算剰余演算は、乗算、加算およびシフト演算のみで実行することができる。
【００６６】
実施の形態１の式（１６）のべき乗剰余演算はモンゴメリ乗算剰余を用いて計算することができる。たとえば、Ｘ3ｍｏｄｐの計算では、まず、Ｘをモンゴメリ変換してＭ（Ｘ）を求める。次に、Ｍ（Ｘ）3＝Ｍ（Ｘ)＊Ｍ（Ｘ）＊Ｍ（Ｘ）を計算する。最後にＭ（Ｘ）3のモンゴメリ逆変換すなわちＭ（Ｘ）3＊１を計算すれば、Ｘ3ｍｏｄｐが得られる。
【００６７】
［コプロセッサの構成］
図９は、実施の形態３によるコプロセッサの構成を示すブロック図である。コプロセッサ３Ｂは、コプロセッサ３に代えて図４の半導体装置１に搭載される。
【００６８】
図９を参照して、コプロセッサ３Ｂは、ＲＳＡ暗号処理のための演算を行なう演算器１０と、レジスタ群１１とを含む。レジスタ群１１は、暗号文、平文、暗号鍵、および計算の中途段階の値などを格納する。演算器１０には、各機能ブロック間の信号の制御を行なうコントローラも設けられている。
【００６９】
［コプロセッサの動作］
図１０は、実施の形態３によるＲＳＡ暗号の復号手順を示すフローチャートである。以下のモンゴメリ変換で用いられるＲは、ｐよりも大きい２のべき乗数である。前述の式（１１）の公開鍵Ｎを２０４８ビットとし、素数ｐ、ｑを１０２４ビットとするとき、たとえばＲ＝２1024とする。
【００７０】
図９、図１０を参照して、まず、図４の入出力回路４を介して、暗号文Ｘがレジスタ１２に入力される（ステップＳ３００）。暗号文Ｘは、公開鍵ｅ、Ｎを用いて平文Ｙを暗号化したものであり、前述の式（１１）〜（１３）の関係が成り立つ。
【００７１】
次に、演算器１０は、秘密鍵ｄをｐ−１で割った余りＤｐ、およびｄをｑ−１で割った余りＤｑを求める（ステップＳ３０５）。Ｄｐ、Ｄｑは、予め計算して図１のメモリ５に格納しておき、暗号処理時に読み出されるようにしてもよい。
【００７２】
次に、演算器１０は、前述の式（１６）で表わされるＸｐのモンゴメリ変換Ｍ（Ｘｐ）を算出する（ステップＳ３１０）。すなわち、演算器１０は、
Ｍ（Ｘｐ）＝ＸDp×Ｒｍｏｄｐ      …(25)
で表わされるＭ（Ｘｐ）を求める。上式（２５）のＭ（Ｘｐ）は、Ｘのモンゴメリ変換をＭ（Ｘ）としたとき、Ｍ（Ｘ）についてのモンゴメリ乗算剰余演算の繰り返しによって求めることができる。
【００７３】
さらに、演算器１０は、前述の式（１７）で表わされるＸｑのモンゴメリ変換Ｍ（Ｘｑ）を算出する（ステップＳ３１５）。すなわち、演算器１０は、
Ｍ（Ｘｑ）＝（ＸDqｍｏｄｑ）×Ｒｍｏｄp      …(26)
で表わされるＭ（Ｘｑ）を求める。
【００７４】
次に、演算器１０は、ｐを法とするｑの逆元ｑ-1のモンゴメリ変換Ｍ（ｑ-1）を計算する（ステップＳ３２０）。すなわち、演算器１０は、
Ｍ（ｑ-1）＝ｑ-1×Ｒｍｏｄｐ      …(27)
で表わされるＭ（ｑ-1）を求める。
【００７５】
次に、演算器１０は、Ｍ（Ｘｐ）−Ｍ（Ｘｑ）とＭ（ｑ-1）とのモンゴメリ乗算剰余Ｍ（ｗ）を計算する（ステップＳ３２５）。すなわち、演算器１０は、
Ｍ（ｗ）＝（Ｍ（Ｘｐ）−Ｍ（Ｘｑ））×Ｍ（ｑ-1）×Ｒ-1ｍｏｄｐ      …(28)
で表わされるＭ（ｗ）を求める。
【００７６】
次に、演算器１０は、Ｍ（ｗ）をモンゴメリ逆変換することによってｗを計算する（ステップＳ３３０）。すなわち、演算器１０は、
ｗ＝Ｍ（ｗ）×Ｒ-1ｍｏｄｐ      …(29)
で表わされるｗを求める。
【００７７】
次に、演算器１０は、前述の式（２１）に従って平文Ｙを求める。
［実施の形態３の効果］
ここで、モンゴメリ変換後のｄｉｆｆ関数を下記のように定義する。
ｄｉｆｆ（Ｙ）＝０  ただし、Ｍ（Ｘｐ）−Ｍ（Ｘｑ）≧０      …(30A)
ｄｉｆｆ（Ｙ）＝１  ただし、Ｍ（Ｘｐ）−Ｍ（Ｘｑ）＜０      …(30B)
上記の方法によって、暗号文Ｘから平文Ｙを求めると、Ｙの値がｐの倍数であっても、ｄｉｆｆ（Ｙ−１）＝０かつｄｉｆｆ（Ｙ）＝１になるとは限らない。すなわち、モンゴメリ変換後のＸｐ−Ｘｑの正負と秘密鍵ｐとの間に対応関係が生じないようにできるので、サイドチャネルアタックでｄｉｆｆ関数の値を特定することによる秘密鍵ｐへの攻撃が成功する可能性を低くすることができる。
【００７８】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は上記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【符号の説明】
【００７９】
１  半導体装置、２  ＣＰＵ、３，３Ａ，３Ｂ  コプロセッサ、４  入出力回路、５  メモリ、６  バス、７  タイマ、１０  演算器、１１  レジスタ群、１２〜１４，ＲＥ１〜ＲＥ４  レジスタ、２０，２０Ａ  データ処理部、２１，２３  セレクタ、２２  切替信号発生器、２４  ＥＸ−ＯＲゲート。
【図１】
2014081426.tif 000003
【図２】
2014081426.tif 000004
【図３】
2014081426.tif 000005
【図４】
2014081426.tif 000006
【図５】
2014081426.tif 000007
【図６】
2014081426.tif 000008
【図７】
2014081426.tif 000009
【図８】
2014081426.tif 000010
【図９】
2014081426.tif 000011
【図１０】
2014081426.tif 000012