楕円曲線暗号を用いた認証処理に対する故障利用攻撃を検知する認証用媒体
【課題】
楕円曲線暗号方式を用いたＩＣカード認証における故障利用攻撃の検知技術において、復号メッセージが楕円曲線の点であることを利用する従来技術では、多くの場合で当該攻撃を受けていることを検知できない。
【解決手段】
ＩＣカードにおいて、認証装置から入力された暗号文を秘密鍵で復号することで復号メッセージを得た後に、当該復号メッセージと前記暗号文との対応関係を、楕円曲線上の退化なペアリング関数を用いて検証することにより、故障利用攻撃の有無を検知する。
楕円曲線暗号方式を用いたＩＣカード認証における故障利用攻撃の検知技術において、復号メッセージが楕円曲線の点であることを利用する従来技術では、多くの場合で当該攻撃を受けていることを検知できない。
【解決手段】
ＩＣカードにおいて、認証装置から入力された暗号文を秘密鍵で復号することで復号メッセージを得た後に、当該復号メッセージと前記暗号文との対応関係を、楕円曲線上の退化なペアリング関数を用いて検証することにより、故障利用攻撃の有無を検知する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線暗号を用いた認証処理に対する故障利用攻撃を検知する認証用媒体に関する。
【背景技術】
【０００２】
ＩＣカード等の認証用媒体を用いた認証においては、一般に公開鍵暗号方式が用いられる。ＩＣカードには公開鍵暗号方式の秘密鍵及び暗号化（復号化）回路が実装されており、これにより暗号学的に安全性が保証された認証を行うことを可能としている。
【０００３】
ＩＣカード認証で通常用いられる公開鍵暗号方式として、楕円曲線暗号が知られている。楕円曲線暗号は、やはり公開鍵暗号方式の一つであるＲＳＡ暗号方式と比べ、より短い鍵長で同程度のセキュリティレベルを確保できるという特徴を持つ。例えば、鍵長１６０ビットの楕円曲線暗号と、鍵長１０２４ビットのＲＳＡ暗号のセキュリティレベルがほぼ同じであることが知られている。そのため、楕円曲線暗号は、メモリや処理パワーの少ないＩＣカード、携帯電話などの小型デバイスにおける実装に適している。
【０００４】
楕円曲線暗号の1つである楕円エルガマル（ＥｌＧａｍａｌ）暗号を利用したＩＣカード認証システムにおける認証処理の例を説明する。ｐを素数とし、有限体ＧＦ（ｐ）上の楕円曲線ＥにおけるベースポイントをＧとする（各記号の詳細については後述する）。ＩＣカードには、前記楕円曲線に基づく楕円曲線暗号の秘密鍵ｄが秘密に格納されている。また、認証装置には、前記楕円曲線暗号の公開鍵Ｙ＝[ｄ]Ｇが格納されている（ここで、記号[ ]はスカラー倍算を示す）。
【０００５】
図１１に基づき、認証装置がＩＣカード（正確には、ＩＣカードを保持するユーザ）を認証するための処理フローを説明する。認証装置は、ＩＣカードが入力されたことを検知する（ステップＳ７０１）。次に認証装置は、適当なメッセージＭを生成して記憶装置に格納するとともに、公開鍵を用いて前記メッセージＭを暗号化することで暗号文Ｃ＝（Ｃ１，Ｃ２）を生成する（ステップＳ７０２）。ここで、Ｃ１＝[ｒ]Ｇ、Ｃ２＝Ｍ＋[ｒ]Ｙである（ｒは適当に選んだ乱数）。そして認証装置は、生成した暗号文ＣをＩＣカードに送信する（ステップＳ７０３）。
【０００６】
次にＩＣカードは、前記暗号文Ｃを受信する（ステップＳ７０５）。ＩＣカードは、秘密鍵を用いてＣ１を復号することで、中間メッセージＫを得る（ステップＳ７０７）。具体的には、ＩＣカードはＫ＝[ｄ]Ｃ１を計算する。また、ＩＣカードは、Ｃ２を復号し、復号メッセージＭ’を得る（ステップＳ７０９）。具体的には、ＩＣカードはＭ’＝Ｃ２−Ｋを計算する。そして、ＩＣカードは、Ｍ’を認証装置に送信する（ステップＳ７１１）。
【０００７】
認証装置は、前記Ｍ’を受信する（ステップＳ７１３）。認証装置は、記憶装置から前記Ｍを読み出し、Ｍと前記受信したＭ’を比較する（ステップＳ７１５）。認証装置は、ＭとＭ’が一致した場合に「認証成功」と判定する（ステップＳ７１７）。一方、ＭとＭ’が一致しなかった場合には、認証装置は「認証失敗」と判定する（ステップＳ７１９）。この認証システムの安全性は、ＩＣカードが秘密鍵を有しない限り、ＩＣカードは手順３においてＣに基づいてＭ’＝ＭとなるＭ’を算出できないことに基づいている。
【０００８】
ＩＣカードにおいて秘密鍵は耐タンパに保持される為、外部から直接読み取られることは考えにくいが、これを間接的に推測する攻撃がいくつか存在する。そのような攻撃の１つに、故障利用攻撃がある。故障利用攻撃では、ＩＣカードが秘密鍵を用いて暗号化または復号化を行っている最中に、外部から供給電圧を急激に変化させる等の物理的変化を与えることにより、ＩＣカードの処理結果を意図的に誤らせる。攻撃者は、認証装置上でこの誤らせた処理結果を得ることで、所定の条件の下で、秘密鍵を推測することが可能となる。
【０００９】
すなわち、ステップＳ７０７およびＳ７０８において、ＩＣカードは、認証装置から受け取った暗号文Ｃから復号メッセージを計算するが、攻撃者はその際に高電圧などの物理的操作をＩＣカードに与える。このときＩＣカードが正当なもの（認証装置上の公開鍵に対応する秘密鍵を有するもの）であっても、復号メッセージは正しく計算されず（Ｍ’≠ＭとなるＭ’が算出される）、ＩＣカードは認証装置に対して正しくない結果を送信することになる。攻撃者は、その誤った出力を得て、当該出力を解析することで、ＩＣカード内に保持されている秘密鍵を推測できる。
【００１０】
上の例のように、ＩＣカード上の楕円曲線暗号を用いた認証システムにおいて故障利用攻撃を受けると、ＩＣカードの秘密鍵を攻撃者に特定される可能性がある。すなわち、故障利用攻撃は秘密鍵の漏洩に繋がるため、その対策が強く望まれている。
【００１１】
故障利用攻撃を検知するための従来技術として、ＩＣカードが故障利用攻撃を受けた場合に、その計算結果が楕円曲線暗号で利用する楕円曲線の点にならないことがある性質を利用する方式が知られている（例えば、特許文献１）。従来技術では、ＩＣカードに係る楕円曲線Ｅが方程式
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
で表されるとき、関数Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)を
Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6−(ｙ2＋ａ1ｘｙ＋ａ3ｙ)
と定める。ＩＣカードは、前記中間メッセージＫを求めた後、Ｋが楕円曲線Ｅの点であるかを判定する。ここで、Ｍ’ではなくＫの値を検証する理由は、攻撃者は秘密鍵ｄを推定したいのでＫ＝[ｄ]Ｃ１の計算時に故障利用攻撃を行うと考えられるためである。これに対し、Ｍ’＝Ｃ２−Ｋであり、すなわちＭ’の計算にｄは用いられないため、Ｍ’の計算時のみに故障利用攻撃を行っても意味がない。
【００１２】
ＩＣカードがＫが楕円曲線Ｅの点であるかを判定するためには、具体的には、前記Ｋを(ｘk，ｙk)と表すと、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)を計算すればよい。そして、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)＝０であればＫは楕円曲線の点であり、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)≠０であればＫは楕円曲線の点でないと判定できる。Ｋは本来は楕円曲線Ｅの点であるはずである（詳しくは後述するが、楕円曲線暗号では、元のメッセージ、暗号文、および復号メッセージはいずれも楕円曲線の点である）。そこで、Ｋが楕円曲線の点でないとき、ＩＣカードは、故障利用攻撃を受けたと判断することができる。
【特許文献１】特開2004-252433号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかし、従来技術は、ＩＣカードが故障利用攻撃を受けていることをそもそも検知できない場合が多数あるという課題がある。具体的には、特許文献１に係る従来技術は、故障利用攻撃を受けた計算結果がたまたま楕円曲線上の点になる場合には、攻撃を検知することができない。このような場合は、全暗号文の１／２が該当することが知られている。これは、ｘの値が与えられたときに、式Ｅを満たすｙを求める（すなわち、ｙに係る方程式Ｅが解ける）ことができる確率が１／２だからである。すなわち、従来技術では、２回に１回の割合で、故障利用攻撃の検知に失敗するという問題がある。
【００１４】
上記の問題は、従来技術が、中間メッセージＫのみを用いて故障利用攻撃の有無を判定していることに起因する。中間メッセージＫが満たすべき前記条件（楕円曲線上の点であること）を満たすＫは沢山ある（Ｋの種類数は、楕円曲線Ｅの点の数に等しい）。そのため、故障利用攻撃を受けて誤ったＫが算出されたとしても、当該誤ったＫが前記条件を満たしてしまう可能性も高いものとなる。
【課題を解決するための手段】
【００１５】
上記の課題を解決するために、本発明は、中間メッセージＫの検証を、Ｋの暗号文であるＣ１を用いて行うことを特徴とする。すなわち、暗号文Ｃ１と中間メッセージＫの間にある１対１の対応関係（中間メッセージＫは、確かに、暗号文Ｃ１を復号したものであるということ）を、復号化処理とは別のアプローチで把握することにより、前記課題を解決する。
【００１６】
これを実現するため、本発明は、楕円曲線上の退化なペアリングと呼ばれる関数を利用する。すなわち、退化なペアリングを用いて暗号文Ｃ１と中間メッセージＫとの対応関係を把握し、これにより故障利用攻撃を検出する。
【００１７】
楕円曲線上のペアリングｅとは、楕円曲線の２点に対してある値を出力し、かつ以下の２つの条件を満たす関数である（ここで、Ｐ１、Ｐ２、Ｐ３は楕円曲線の点とする）。
(１) ｅ(Ｐ１，Ｐ２＋Ｐ３)＝ｅ(Ｐ１，Ｐ２)・ｅ(Ｐ１，Ｐ３)
(２) ｅ(Ｐ１，Ｐ２)＝ｅ(Ｐ２，Ｐ１)
また、上記の２条件に加え、以下の条件を満たすｅを「退化なペアリング」と呼ぶ。
(３) ｅ(Ｐ１，Ｐ１)≠１
なお、楕円曲線上の退化なペアリングそのものは公知技術である。従来、退化なペアリングは、楕円曲線暗号に対する攻撃技術や、楕円曲線暗号そのものの内部処理において使用されている。
【００１８】
本発明に係るＩＣカードは、前記の退化なペアリングｅを用いて、故障利用攻撃の有無を検出する。これは、具体的には以下のように行う。ＩＣカードは、先述した暗号文Ｃ＝（Ｃ１，Ｃ２）の復号処理において、Ｃ１から中間メッセージＫを求めた後に、前記ベースポイントＧと当該Ｋとに基づきｅ１＝ｅ（Ｇ，Ｋ）を計算するとともに、前記公開鍵Ｙと当該Ｃ１とに基づきｅ２＝ｅ（Ｙ，Ｃ１）を計算する。ここで、ｅは退化なペアリング関数とする。そして、ＩＣカードは、ｅ１＝ｅ２が成り立つかを判定する。もしｅ１＝ｅ２であれば、ＩＣカードは、故障利用攻撃が行われなかったと判断する。反対に、ｅ１≠ｅ２であれば、ＩＣカードは、故障利用攻撃が行われたと判断する。
【発明の効果】
【００１９】
開示のＩＣカードによれば、従来技術よりも高い確率で故障利用攻撃を検知することが可能となるという効果を奏する。
【００２０】
故障利用攻撃が行われていない場合を考える。このとき、退化なペアリングの性質に基づき、前記ｅ１は、
ｅ１＝ｅ（Ｇ，Ｋ）＝ｅ（Ｇ，[ｄ]Ｃ１）＝ｅ（Ｇ，[ｄ−１]Ｃ１＋Ｃ１）
＝ｅ（Ｇ，[ｄ−１]Ｃ１）・ｅ（Ｇ，Ｃ１）
＝ｅ（Ｇ，[ｄ−２]Ｃ１＋Ｃ１）・ｅ（Ｇ，Ｃ１）
＝ｅ（Ｇ，[ｄ−２]Ｃ１）・ｅ（Ｇ，Ｃ１）2
と式変形できる。同様の式変形を繰り返すと、結局、関係式ｅ１＝ｅ（Ｇ，Ｃ１）dが導ける。また、前記ｅ２に対しても、同様にして、
ｅ２＝ｅ（Ｙ，Ｃ１）＝ｅ（[ｄ]Ｇ，Ｃ１）＝ｅ（Ｇ，Ｃ１）d
と式変形でき、結局、関係式ｅ２＝ｅ（Ｇ，Ｃ１）dが導ける。すなわち、もし故障利用攻撃が行われていなければ、必ず、ｅ１＝ｅ２が成立する。この対偶から、もしｅ１≠ｅ２であれば、１００％の確率で、故障利用攻撃が行われている。
【００２１】
反対に、故障利用攻撃が行われた場合を考える。このとき、Ｃ１から偶然にＫが算出される場合（ランダムな確率で発生するので、確率１／ｐで発生する）を除いて、Ｃ１からＫとは異なるＫ’が算出される。このとき、ｅ１＝ｅ（Ｇ，Ｋ’）≠ｅ（Ｇ，Ｃ１）dとなる。すなわち、もし故障利用攻撃が行われたならば、１−（１／ｐ）の確率で、ｅ１≠ｅ２が成立する。ここで、通常、ｐは非常に大きな素数であるので、１／ｐは無視できるほど小さい確率となる。したがって、もしｅ１＝ｅ２であれば、１００％に限りなく近い確率で、故障利用攻撃が行われていない。
【００２２】
すなわち、ｅ１＝ｅ２が成り立つか否かを判定することで、故障利用攻撃を高精度に検出できる。したがって、本願の方式によれば、ＩＣカード内においてほぼ１００％の割合で故障利用攻撃の有無を検出でき、故障利用攻撃による秘密鍵の漏洩を回避することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施の形態を図面を参照して説明する。なお、本発明は、楕円曲線暗号や楕円曲線上の退化なペアリングといった離散数学に基づいており、発明の理解が容易ではない側面がある。そこで、本発明の実施形態に係る説明においては、楕円曲線暗号や楕円曲線上の退化なペアリングを構成したという前提の下で、それらを用いて故障利用攻撃の検知を可能にした認証システムについて説明する。そして、前記楕円エルガマル暗号と楕円曲線上の退化なペアリング関数については、各実施形態に係る説明の後で、最後に説明する。
【００２４】
図１に、本発明の第１の実施形態に係る認証システムの機能ブロック図を示す。認証システムは、認証用媒体の一例であるＩＣカード１００と、認証装置３００とを備える。
【００２５】
ＩＣカード１００は、記憶部１０１、公開情報記憶部１０３、秘密鍵記憶部１０５、攻撃検知部１０７、復号化処理部１０９、通信部１１１、及び制御部１１３を備える。記憶部１０１は、種々の演算結果等を格納して記憶する。公開情報記憶部１０３は、ＰＫＩ（公開鍵基盤）の公開情報を格納して保持する。ここで公開情報は、公開鍵により身元が保証されるユーザの識別子、ユーザの公開鍵Ｙ、公開鍵暗号方式を少なくとも含む必要があり、例えばＸ．５０９で規定された公開鍵証明書を用いることができる。本実施例においては、公開鍵暗号として、楕円曲線暗号の１つである楕円エルガマル暗号を用いる。先述した公開鍵暗号方式には、公開鍵暗号として楕円エルガマル暗号を用いることに加え、その公開パラメータである有限体ＧＦ（ｐ）、ＧＦ（ｐ）上の楕円曲線Ｅ、およびベースポイントＧそれぞれを含む（各記号の詳細については後述する）。ここで、ｐは素数であり、ｐ＝２ ｍｏｄ ３を満たすとする。すなわち、Eは素数位数の楕円曲線である。なお、ＦＩＰＳ１８６−２を含む多くの楕円曲線暗号標準において、素数位数の楕円曲線暗号が採用されている。秘密鍵記憶部１０５は、前記公開鍵に対応する秘密鍵ｄを格納し、秘密に保持する。ここで、秘密鍵ｄと前記公開鍵Ｙの間には、Ｙ＝[ｄ]Ｇの関係が成り立っているものとする。攻撃検知部１０７は、故障利用攻撃の検知を行う。復号化処理部１０９は、暗号文を復号して復号メッセージを得る。通信部１１１は、認証装置３００とＩＣカード１００の間で暗号文や復号メッセージといったデータを送受する。制御部１１３は、故障利用攻撃検知部１０７、復号化処理部１０９、及び通信部１１１の制御を司る。
【００２６】
一方、認証装置３００は、記憶部３０１、公開情報記憶部３０３、乱数生成部３０５、認証処理部３０７、暗号化処理部３０９、通信部３１１、及び制御部３１３を備える。記憶部３０１は、種々の演算結果等を格納して記憶する。公開情報記憶部３０３は、ＰＫＩ（公開鍵基盤）の公開情報を格納して保持する。この公開情報は、ＩＣカード１００の公開情報記憶部１０３において記憶されるものと同等の情報である。乱数生成部３０５は、乱数を生成する。ここで生成する乱数は、数学的手法により生成される擬似乱数であっても良い。認証処理部３０７は、ユーザの認証処理を行う。暗号化処理部３０９は、メッセージを暗号化して暗号文を生成する。通信部３１１は、認証装置３００とＩＣカード１００の間で暗号文や復号メッセージといったデータを送受する。制御部３１３は、乱数生成部３０５、認証処理部３０７、暗号化処理部３０９、及び通信部３１１の制御を司る。
【００２７】
図２に基づき、第１の実施形態に係る認証システムの処理フローについて説明する。
【００２８】
まず、認証装置は、ＩＣカードが入力されたことを検知する（ステップＳ１）。次に認証装置３００の暗号化処理部３０９は、ＩＣカード１００に送信する暗号文を作成する（ステップＳ２）。これは以下のように行う。暗号化処理部３０９は、楕円曲線上の点であるメッセージＭを適当に選択し、記憶部３０１に格納する。次に、乱数生成部３０５は、乱数ｒを生成し、記憶部３０１に格納する。なお、前記メッセージＭについては、乱数生成部３０５が前記ｒとは別の乱数ｒ’を生成し、暗号化処理部３０９が前記ｒ’に基づいて生成することができる。次に、暗号化処理部３０９は、ベースポイントＧを公開情報記憶部３０３から読み出し、また前記ｒを記憶部３０１から読み出し、読み出したＧとｒとを用いて点[r]Ｇを計算し、計算結果を記憶部３０１上の変数Ｃ１に格納する。さらに、暗号化処理部３０９は、公開鍵Ｙを公開情報記憶部３０３から読み出し、また前記ｒとＭとを記憶部３０１から読み出し、読み出したＹ、Ｍ、およびｒを用いて点Ｍ＋[ｒ]Ｙを計算し、計算結果を記憶部３０１上の変数Ｃ２に格納する。Ｃ＝（Ｃ１，Ｃ２）を暗号文とする。
【００２９】
次に認証装置３００の通信部３１３は、ＩＣカード１００に対し、作成した暗号文Ｃ＝（Ｃ１，Ｃ２）を送信する（ステップＳ３）。ＩＣカード１００の通信部１１３は、送信された暗号文Ｃを受信し、記憶部１０１に格納する（ステップＳ５）。次にＩＣカードの復号化処理部１０９は、前記Ｃ１を記憶部１０１から読み出し、読み出したＣ１を復号する（ステップＳ７）。すなわち、復号化処理部１０９は、秘密鍵ｄを秘密鍵記憶部１０５から読み出し、読み出したｄを用いて点[ｄ]Ｃ１を計算し、計算結果を記憶部１０１上の変数Ｋに格納する。
【００３０】
次にＩＣカード１００の攻撃検知部１０７は、故障利用攻撃の有無を判定する（ステップＳ９）。判定の処理の詳細については後述する。次に攻撃検知部１０７は、ステップＳ９の判定結果に基づき、処理を分岐する（ステップＳ１１）。もし判定結果がＹＥＳ（攻撃を検知）の場合、ＩＣカードの制御部１１１は、必要に応じ所定の異常系処理を行う（ステップＳ１３）。すなわち、攻撃を検知したということは、ＩＣカードに故障利用攻撃が行われたことを意味する。そのため、認証の成否に意味が無くなり、またＩＣカードが復号メッセージを認証装置３００に出力すると、攻撃者がそれを盗聴してしまう。そこで、制御部１１１は、復号メッセージを認証装置３００に送信することはせず、管理者に通報したりエラーログを残すといった異常系処理を行う。そして、今回の認証処理は終了する。
【００３１】
一方、もしステップＳ９の判定結果がＮＯ（攻撃を検知せず）の場合、ＩＣカード１００の復号化処理部１０９は、メッセージＭ’を復号する（ステップＳ１５）。すなわち、復号化処理部１０９は、記憶部からＫとＣ２とを読み出し、読み出したＫとＣ２とにより点Ｃ２−Ｋを計算し、計算結果を記憶部１０１上の変数Ｍ’に格納する。
【００３２】
次に、ＩＣカード１００の通信部１１３は、認証装置３００に対し、復号したメッセージＭ’を送信する（ステップＳ１７）。認証装置３００の通信部３１１は、送信されたメッセージＭ’を受信し、記憶部３０１に格納する（ステップＳ１９）。最後に、認証装置３００の認証処理部３０７は、認証の成否を判定する（ステップＳ２１）。すなわち、認証処理部３０７は、認証装置３００の暗号化処理部３０９が選択して暗号化したメッセージＭと、ＩＣカードから受信したメッセージであるＭ’とをそれぞれ記憶部３０１から読み出し、比較する。そして、Ｍ＝Ｍ’の場合、認証処理部３０７は、「認証成功」と判定する（ステップＳ２３）。もし認証装置３００の公開情報記憶部３０３に格納された公開鍵ＹとＩＣカード１００の秘密鍵記憶部１０５に格納された秘密鍵ｄとの間に対応関係があれば、認証装置３００で暗号化したメッセージがＩＣカード１００で正しく復号されて元のメッセージに戻るはずであるため、Ｍ＝Ｍ’が成立するはずであるからである。反対に、Ｍ≠Ｍ’の場合、認証処理部３０７は、「認証失敗」と判定する（ステップＳ２５）。認証が成功でも失敗でも、認証装置の制御部３１１は、今回の認証処理を終了し、入力待ちとなる。
【００３３】
次に、図３に基づき、第１の実施形態に係るＩＣカードの攻撃検知部１０７が故障利用攻撃の有無を判定する処理（ステップＳ９）の詳細な処理フローについて説明する。攻撃検知部１０７は、前記ベースポイントＧ、前記暗号文Ｃ１を復号して得られたＫを記憶部１０１から読み出し、読み出したＧおよびＫを用いて、ｅ１＝ｅ(Ｇ，Ｋ) を算出する（ステップＳ１０１）。ここで、ｅは、後述する退化なペアリング関数である。ステップＳ１０１の処理の詳細については後述する。次に、攻撃検知部１０７は、公開鍵Ｙを公開情報記憶部１０３から読み出し、また前記暗号文Ｃ1を記憶部１０１から読み出し、読み出したＹおよびＣ１を用いて、ｅ２＝ｅ(Ｙ，Ｃ1)を算出する（ステップＳ１０２）。ステップ１０２の処理の詳細についても後述する。次に、攻撃検知部１０７は、ｅ１＝ｅ２が成立するか否かを確かめる（ステップＳ１０３）。もしｅ１＝ｅ２が成立する場合には、攻撃検知部１０７は故障利用攻撃を受けなかったと判定する（ステップＳ１０４）。また、もしｅ１＝ｅ２が成立しない場合には、攻撃検知部１０７は故障利用攻撃を受けたと判定する（ステップＳ１０５）。
【００３４】
次に、ステップＳ１０１でｅ１＝ｅ(Ｇ，Ｋ)を算出する処理、 および、ステップＳ１０２でｅ２＝ｅ(Ｙ，Ｃ1)を算出する処理の詳細を説明する。これら２つの処理は一部を除いてほとんど同じであるため、以下ではｅ１を算出する処理であるステップＳ１０１について詳細に述べ、ｅ２を算出する処理であるステップＳ１０２については、ステップＳ１０１と異なる点を中心に簡単に説明する。
【００３５】
図４の処理フローに基づき、ｅ１＝ｅ(Ｇ，Ｋ)を算出する処理（ステップＳ１０１）の詳細について説明する。まず攻撃検知部１０７は、公開情報記憶部１０３からベースポイントＧを読み出すと共に、記憶部１０１から前記算出したＫを読み出し、記憶部１０１上の変数Ｐ１にＧを、Ｐ２にＫを、それぞれ格納する（ステップＳ２０１）。ここで、Ｐ１、Ｐ２はそれぞれ平面上の点であり、（ｘ，ｙ）のような座標形式で表せるとする。そして攻撃検知部１０７は、ｅ(Ｐ１，Ｐ２)を算出する（ステップＳ２０２）。
【００３６】
ここで、図６の処理フローに基づき、ｅ(Ｐ１，Ｐ２)を算出する処理（ステップＳ２０２）の詳細について説明する。まず攻撃検知部１０７は、記憶部１０１からＰ２を読み出し、Φ（Ｐ２）を計算し、計算結果をＰ２に格納する（ステップＳ４０１）。なお、写像Φは、以下で定義される。
【００３７】
Φ：(ｘ，ｙ) → (ｗｘ，ｙ)
ここで、ｗは１の原始３乗根である。次に攻撃検知部１０７は、記憶部１０１上の変数ＳにＰ１を格納する（ステップＳ４０２）。そして攻撃検知部１０７は、関数ｆSを導出する（ステップＳ４０３）。
【００３８】
ここで、図７の処理フローに基づき、楕円曲線Ｅの点Ｓに対して、ｆSを算出する処理の詳細について説明する。まず攻撃検知部１０７は、前記有限体の位数ｐの２進展開を算出し、記憶部上の変数のｔ個組である（ｎt-1，．．．，ｎ0）2に格納する（ステップＳ５０１）。次に攻撃検知部１０７は、記憶部１０１上の変数ｉ、ｒにそれぞれ自然数ｔ−２、１を格納し、記憶部１０１上の変数ｆに関数１を格納し、さらに、記憶部１０１上の変数Ｖに前記楕円曲線Ｅの点であるＳを格納する（ステップＳ５０２）。
【００３９】
次に攻撃検知部１０７は、記憶部１０１上の変数ｉを読み出し、ｉ＜０であるかを判定する（ステップＳ５０３）。ｉ＜０でない場合（分岐のＮＯ）、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅの点Ｖを通り且つ楕円曲線Ｅに接する直線を求め、当該直線をｌr,r（ｘ，ｙ）＝０とする（ステップＳ５０４）。次に攻撃検知部１０７は、前記読み出したＶに基づき、点[２]Ｖを算出し、記憶部１０１上の変数Ｖに格納する（ステップＳ５０５）。また、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅ上のＶ及び無限遠点∞を通る直線を求め、当該直線をｖ2r｝（ｘ，ｙ）＝０とする（ステップＳ５０６）。そして、攻撃検知部１０７は、前記記憶部１０１に格納したｆを読み出し、前記求めた関数ｌr,r（ｘ，ｙ）およびｖ2r（ｘ，ｙ）とに基づき、関数ｆ2・ｌr,r（ｘ，ｙ）／ｖ2r（ｘ，ｙ）を算出し、当該算出した関数を記憶部１０１上の変数ｆに格納する（ステップＳ５０７）。また、攻撃検知部１０７は、前記読み出したｒの値に基づき２ｒを算出し、当該算出した値を記憶部１０１上の変数ｒに格納する（ステップＳ５０８）。
【００４０】
次に攻撃検知部１０７は、記憶部１０１上のｎiを読み出し、その値が１であるかを判定する（ステップＳ５０９）。ｎi＝１でない場合（分岐のＮＯ）、攻撃検知部は、後述するステップＳ５１５の処理を行う。一方、ｎi＝１である場合（分岐のＹＥＳ）、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅの点Ｖおよび前記点Ｓを通る直線を求め、当該直線をｌr,1（ｘ，ｙ）＝０とする（ステップＳ５１０）。次に攻撃検知部１０７は、前記読み出したＶおよびＳに基づき、点Ｖ＋Ｓを算出し、記憶部１０１上の変数Ｖに格納する（ステップＳ５１１）。また、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅ上のＶ及び無限遠点∞を通る直線を求め、当該直線をｖr+1（ｘ，ｙ）＝０とする（ステップＳ５１２）。そして、攻撃検知部１０７は、前記記憶部１０１に格納したｆを読み出し、前記求めた関数ｌr,1（ｘ，ｙ）およびｖr+1（ｘ，ｙ）とに基づき、関数ｆ・ｌr,1（ｘ，ｙ）／ｖr+1（ｘ，ｙ）を算出し、当該算出した関数を記憶部１０１上の変数ｆに格納する（ステップＳ５１３）。また、攻撃検知部１０７は、前記読み出したｒの値に基づきｒ＋１を算出し、当該算出した値を記憶部１０１上の変数ｒに格納する（ステップＳ５１４）。
【００４１】
攻撃検知部１０７は、記憶部１０１上のｉを読み出し、ｉ＋１を算出し、当該算出した値を記憶部１０１上の変数ｉに格納する（ステップＳ５１５）。そして、攻撃検知部１０７は、ステップＳ５０３に戻って処理を繰り返す。
【００４２】
一方、ステップＳ５０３の判定において、ｉ＜０である場合（分岐のＹＥＳ）、攻撃検知部１０７は、記憶部１０１からｆを読みだし、記憶部１０１上の変数ｆSに格納する（ステップＳ５１６）。以上により、所望の関数ｆSの導出が完了する。
【００４３】
図６の処理の説明に戻って、攻撃検知部１０７は、導出した関数ｆSを記憶部１０１上のｆP1に格納する（ステップＳ４０４）。また、攻撃検知部１０７は、記憶部１０１上の変数ＳにＰ２を格納する（ステップＳ４０５）。そして攻撃検知部１０７は、先述した図７の処理フローに基づき、再び関数ｆSを導出する（ステップＳ４０６）。そして、導出した関数ｆSを記憶部１０１上のｆP2に格納する（ステップＳ４０７）。
【００４４】
次に攻撃検知部１０７は、楕円曲線Ｅ上の２点を任意に選択し、それぞれ記憶部１０１上のＵ，Ｖに格納する（ステップＳ４０８）。そして攻撃検知部１０７は、Ｐ１，Ｐ２，Ｕ，Ｖをそれぞれ記憶部１０１から読み出して、平面上の２点Ｖ＋Ｐ１、および、Ｕ＋Ｐ２を計算し、これら２点が∞（無限遠点）でないかを判定する（ステップＳ４０９）。そして、Ｖ＋Ｐ１、Ｕ＋Ｐ２のいずれもが∞でない場合（分岐のＹＥＳ）、攻撃検知部１０７は、記憶部１０１から関数ｆP2及び関数ｆP2を読み出し、以下の式に基づいてｅ(Ｐ１，Ｐ２)を計算する（ステップＳ４１０）。
【００４５】
ｅ（Ｐ１， Ｐ２）＝ｆP1（Ｕ＋Ｐ２）／ｆP1（Ｕ）・ｆP2（Ｐ２）／ｆP2（Ｖ＋Ｐ２）
一方、ステップＳ４０９において、Ｖ＋Ｐ１、Ｕ＋Ｐ２のいずれかが∞である場合（分岐のＮＯ）、攻撃検知部１０７は、ステップＳ３０４の処理に戻って、Ｕ，Ｖを再選択する。
【００４６】
図４の処理の説明に戻って、攻撃検知部１０７は、算出したｅ（Ｐ１， Ｐ２）を記憶部１０１のｅ１に格納する（ステップＳ２０３）。これにより、ｅ１＝ｅ(Ｇ，Ｋ) を算出する処理は終了する。
【００４７】
次に、図５の処理フローに基づき、ｅ２＝ｅ(Ｙ，Ｃ1) を算出する処理（ステップＳ１０２）の詳細について説明する。まず攻撃検知部１０７は、公開情報記憶部１０３から公開鍵Ｙを読み出すと共に、記憶部１０１から前記暗号文Ｃ１を読み出し、記憶部１０１上の変数Ｐ１にＹを、Ｐ２にＣ１を、それぞれ格納する（ステップＳ３０１）。そして攻撃検知部１０７は、先述した図６の処理フローに基づき、ｅ(Ｐ１，Ｐ２)を算出する（ステップＳ３０２）。最後に、攻撃検知部１０７は、算出したｅ（Ｐ１， Ｐ２）を記憶部１０１のｅ２に格納する（ステップＳ３０３）。これにより、ｅ２＝ｅ(Ｙ，Ｃ１) を算出する処理は終了する。
【００４８】
以上のように、本発明の第１の実施形態に係る認証システムによれば、故障利用攻撃を高い確率で検知することが可能となる。すなわち、ｅ１＝ｅ２が成り立つか否かを判定することで、故障利用攻撃を高精度に検出できる。したがって、本願の方式によれば、ＩＣカード内においてほぼ１００％の割合で故障利用攻撃の有無を検出でき、故障利用攻撃による秘密鍵の漏洩を回避することができる。
【００４９】
以下では本発明の第２の実施形態について説明する。第２の実施形態は、第１の実施形態と多くの部分は同じであるが、ＩＣカードが故障利用攻撃の有無を判定する処理であるステップＳ９の詳細な処理フローが図３と異なる。具体的には、まず先述した従来の故障利用攻撃検知処理を行った後に、実施例１に記載の故障利用攻撃検知処理を行うものである。
【００５０】
図８に基づき、第２の実施形態に係るＩＣカードの攻撃検知部１０７が故障利用攻撃の有無を判定する処理（ステップＳ９）の処理フローについて説明する。楕円曲線Ｅが方程式
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
で表されるとき、関数Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)を
Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6−(ｙ2＋ａ1ｘｙ＋ａ3ｙ)
と定める。
【００５１】
まず攻撃検知部１０７は、ステップＳ７で算出したＫ＝（ｘk，ｙk）を記憶装置から読み出し、Ｋに基づき、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)を計算する（ステップＳ６０１）。そして攻撃検知部１０７は、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)＝０であるかを判定する（ステップＳ６０２）。Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)≠０であれば（分岐のＮＯ）、攻撃検知部１０７は故障利用攻撃を受けたと判定する（ステップＳ６０７）。Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)≠０であるならば、Ｋは楕円曲線Ｅの点ではなく、故障利用攻撃を受けたと判断できるためである。
【００５２】
一方、ステップＳ６０１で、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)＝０であれば（分岐のＹＥＳ）、攻撃検知部１０７は、前記ベースポイントＧ、前記暗号文Ｃ１を復号して得られたＫを記憶部１０１から読み出し、読み出したＧおよびＫを用いて、ｅ１＝ｅ(Ｇ，Ｋ) を算出する（ステップＳ６０３）。ここで、ｅは、退化なペアリング関数である。次に、攻撃検知部１０７は、公開鍵Ｙを公開情報記憶部１０３から読み出し、また前記暗号文Ｃ1を記憶部１０１から読み出し、読み出したＹおよびＣ１を用いて、ｅ２＝ｅ(Ｙ，Ｃ1)を算出する（ステップＳ６０４）。ここで、ステップ６０３、Ｓ６０４の処理の詳細は、それぞれ図４および図５の処理フローに従えばよい。次に、攻撃検知部１０７は、ｅ１＝ｅ２が成立するか否かを確かめる（ステップＳ６０５）。もしｅ１＝ｅ２が成立する場合には、攻撃検知部１０７は故障利用攻撃を受けなかったと判定する（ステップＳ６０６）。また、もしｅ１＝ｅ２が成立しない場合には、攻撃検知部１０７は故障利用攻撃を受けたと判定する（ステップＳ６０７）。
【００５３】
以上のように、第２の実施形態によれば、第１の実施形態と同じ作用・効果を奏する。すなわち、故障利用攻撃を高い確率で検知することが可能となる。さらに、第２の実施形態は、故障利用攻撃を検知できない場合も多いが処理性能に優れた従来の故障利用攻撃検知方法を前段で実施することにより、検知処理の処理時間の平均を約半分にすることができる。したがって、第２の実施形態によれば、第１の実施形態に比べて、検知の処理を高速化できるという特有の効果を奏する。
【００５４】
以上、第１〜２の実施形態による認証システムの構成を説明したが、本発明は上記実施形態に限るものではなく、その技術的思想の範囲内で種々の設計変更が可能である。例えば、上記の実施形態においては、楕円曲線暗号として楕円エルガマル暗号を用いたが、楕円ＲＳＡ暗号を含む他の楕円曲線暗号を用いても同様な故障利用検知は可能である。また、非退化なペアリングとしてヴェイユペアリングを用いたが、その代わりにテイトペアリング（Ｔａｔｅ Ｐａｒｉｎｇ）やこれらの変形を採用することもできる。また、ＩＣカード１００は、携帯用情報端末であれば良く、例えば携帯電話やＰＤＡ端末等であってもよい。
【００５５】
第１〜２の実施形態による認証システムに係るＩＣカード１００のハードウェア構成を図９に示す。図９のＩＣカード１００においては、Central Processing Unit（CPU）１１、Read only memory（ROM）１２、Random Access Memory（RAM）１３、不揮発性メモリ１４、および、入出力インタフェース１５がバス１７で接続されている。
【００５６】
CPU１１は後述するROM１２に格納されたプログラムやデータを読み込んで実行する。ROM１２は、上書きができない記憶装置であり、プログラムやデータが格納される。RAM１３は、CPU１１がワーク用の記憶装置として使用する。不揮発性メモリ１４は、電気的に書き込み可能な記憶装置であり、個人情報のようなICカード毎に異なるデータを格納する。入出力インタフェース１５は、後述するＩＣカードリーダとの間でデータの入出力を行う。
【００５７】
上記ハードウェア構成を、図１の機能ブロックと対応付けると以下のようになる。ＩＣカード１００の各処理部（攻撃検知部１０７、複号化処理部１０９、通信部１１１、及び制御部１１３）は、ＲＯＭ１２に格納される。公開情報記憶部１０３、及び秘密鍵記憶部１０５は不揮発メモリ１４により実現される。記憶部１０１はＲＡＭ１３により実現される。ＣＰＵ１１は、ＲＯＭ１２から各処理部を読み込んで実行する。このときＣＰＵ１１は、必要に応じて、不揮発性メモリ１４からデータを読み込み、ＲＡＭ１３に対しデータの読み書きを行う。
【００５８】
また、第１〜２の実施形態による認証システムに係る認証装置３００は、コンピュータ上で動作するプログラムによっても実現することができる。
【００５９】
本願発明に係るプログラムを実行するコンピュータである認証装置のハードウェア構成の例を図１０に示す。認証装置３００のハードウェア構成として、例えば、CPU３１、主記憶３２、補助記憶装置３３、出力インタフェース３４、入力インタフェース３５、ＩＣカードＲ／Ｗインタフェース３６がバス３７で接続されている。
【００６０】
CPU３１は後述する主記憶３２に格納されたプログラムを実行する。主記憶３２としては、通常はRAMが用いられ、後述する補助記憶装置３３から実行するプログラムや使用するデータを読み込んで一時的に格納する。補助記憶装置３３としては、通常はHard Disk Drive（HDD）が用いられ、プログラムやデータを格納してファイルとして保存する。なお、補助記憶装置３３としては、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の外部記憶媒体を用いることもできる。
【００６１】
出力インタフェース３４には出力装置の一つとして表示装置であるモニタ３８が接続される。プログラムの実行結果などがモニタに出力され表示される。入力インタフェース３５には入力装置としてキーボード３９やマウス４０が接続され、これら入力装置からデータが入力される。ＩＣカードＲ／Ｗインタフェース３６には、ＩＣカードリーダ／ライタ４１が接続され、ＩＣカードリーダ／ライタ４１にアクセスしたＩＣカードとデータの入出力を行う。
【００６２】
上記ハードウェア構成を、図１の機能ブロックと対応付けると以下のようになる。コンピュータを認証装置３００として機能させるためのプログラム（乱数生成部３０５、認証処理部３０７、暗号化処理部３０９、通信部３１１、及び制御部３１３）、及びデータ（記憶部３０１、公開情報記憶部３０３）を予め補助記憶装置１３に格納させておく。プログラムが起動されると、当該プログラムおよびデータはまず主記憶１２に読み込まれ、その後主記憶１２とCPU１１とが連携することでプログラムが実行される。プログラム実行中に記憶部３０１に格納される各種データは、通常は主記憶に書き込まれるが、必要に応じて補助記憶装置１３に退避させてもよい。
【００６３】
最後に、上記実施形態の前提となる技術である楕円エルガマル暗号、および、楕円曲線上の退化なペアリング関数について、数式を用いて詳細に説明する。
【００６４】
以下では、楕円エルガマル暗号について説明する。まず暗号方式の一方式である公開鍵暗号を説明し、次に公開鍵暗号の一方式である楕円曲線暗号を説明し、最後に楕円曲線暗号の一方式である楕円エルガマル暗号を説明する。
【００６５】
まず暗号方式の一方式である公開鍵暗号を説明する。暗号方式には、公開鍵暗号方式と共通鍵暗号方式とが含まれる。公開鍵暗号方式は、暗号化と復号化とで異なる鍵を用いる方式である。典型的な公開鍵暗号方式では、暗号化の為の鍵（公開鍵）はあらかじめ公開され、誰もが入手できるようになっている。受信者は、送信したい相手の公開鍵を用いて平文を暗号化して暗号文を作成し、その暗号文を受信者に送信する。暗号文を復号化するための鍵（秘密鍵）は受信者のみが知る秘密情報として保持され、受信者はこの秘密鍵を用いて暗号文を復号化することにより、平文を得る。
【００６６】
次に公開鍵暗号の一方式である楕円曲線暗号を説明する。楕円曲線暗号は公開鍵暗号方式に含まれる暗号方式の一つで、楕円曲線と呼ばれる代数曲線の点の間の演算規則を利用した暗号方式の総称である。ｐを素数、ｍを自然数とすると、要素数ｐmの有限体ＧＦ(ｐm)上の楕円曲線とは、方程式
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
を満たす点(ｘ，ｙ)の集合に、無限遠点とよばれる点∞を加えた集合のことをいう。無限遠点∞を０と表すこともある。ここで、定数ａ1、ａ2、ａ3、ａ4、および、ａ6、ならびに、変数ｘ、および、ｙは、有限体ＧＦ(ｐm)の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式(アファイン座標)で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現できない唯一の点である。このように、アファイン座標では無限遠点以外の点はＧＦ(ｐm)の２つの要素の組として表される。
【００６７】
楕円曲線Ｅ上の点の間には、以下のようにして点の加算と呼ばれる演算が定義できる。ＰをＧＦ(ｐm)上の楕円曲線Ｅ上の点とする。まず、Ｐの逆元−Ｐを以下のように定義する。
【００６８】
(１)Ｐ＝∞のとき、−Ｐ＝∞
(２)Ｐ≠∞のとき（Ｐ＝(ｘ、ｙ)とする）、−Ｐ＝(ｘ，−ｙ)
次に、Ｐ１，Ｐ２をＧＦ(ｐm)上の楕円曲線Ｅ上の２点とする。このとき、Ｐ１とＰ２の和Ｐ１＋Ｐ２を以下のように定義する。
【００６９】
(１)Ｐ１＝∞のとき、Ｐ１＋Ｐ２＝Ｐ２
(２)Ｐ２＝∞のとき、Ｐ１＋Ｐ２＝Ｐ１
(３)Ｐ１＝−Ｐ２のとき、Ｐ１＋Ｐ２＝∞
(４)上記以外のとき（Ｐ１＝(ｘ1，ｙ1)，Ｐ２＝(ｘ2，ｙ2)，Ｐ１＋Ｐ２＝(ｘ3，ｙ3)とする）、
ｘ3＝λ2＋ａ1λ−ａ2−ｘ1−ｘ2
ｙ3＝(ｘ1−ｘ2)λ−ｙ1−ａ1ｘ3−ａ3
ただし、
λ＝(ｙ2−ｙ1)／(ｘ2−ｘ1)・・・（Ｐ１≠Ｐ２のとき）
λ＝(３ｘ12＋２ａ2ｘ1＋ａ4−ａ1ｙ1)／(２ｙ1＋ａ1ｘ1＋ａ3)・・・（Ｐ１＝Ｐ２のとき）
なお、Ｐ１≠Ｐ２のときにＰ１＋Ｐ２を計算することを楕円加算という。また、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝[２]Ｐ１を計算することを楕円２倍算という。
【００７０】
楕円曲線とその上の点Ｐが与えられているとき、ある整数ｄに対して、点[ｄ]Ｐ＝Ｐ＋Ｐ＋・・・＋Ｐ(ｄ個の和)を計算することをスカラー倍算という。ここで、点Ｐをベースポイントと呼ぶ。スカラー倍算とは逆に、楕円曲線とその上の点Ｐとそのスカラー倍点[ｄ]Ｐが与えられているとき、整数（スカラー）ｄを求める問題を楕円曲線離散対数問題という。楕円曲線暗号の安全性は、スカラー倍算は容易に計算可能だが、楕円曲線離散対数問題を解くことは困難であるという事実に依存している。このため多くの楕円曲線暗号方式は、スカラーｄを秘密鍵、スカラー倍点[ｄ]Ｐを公開鍵の一部として使用することが多い。
【００７１】
次に、楕円曲線暗号の一方式である、楕円エルガマル暗号について説明する。有限体ＧＦ(ｐm )、その上の楕円曲線Ｅ、ベースポイントＰはあらかじめ定義されており、公開されているものとする。このとき、楕円エルガマル暗号における受信者の秘密鍵をｄとすると、公開鍵をＹ＝[ｄ]Ｐと定義できる。
【００７２】
受信者にメッセージＭを秘密裏に送りたい送信者は、受信者の公開鍵Ｙを用いて、以下の暗号化処理を行う。ここでメッセージＭは楕円曲線Ｅの点として表されているものとする。
（１）(疑似)乱数ｒを生成する。
（２）点[ｒ]Ｐを計算し、Ｃ１として保持する。
（３）点Ｍ＋[ｒ]Ｙを計算し、Ｃ２として保持する。
（４）Ｃ１とＣ２のペア(Ｃ１，Ｃ２)を暗号文として受信者に送る。
暗号文(Ｃ１，Ｃ２)を受け取った受信者は、自分の秘密鍵ｄを用いて、以下の復号化処理を行う。
（１）点[ｄ]Ｃ１を計算し、Ｋとして保持する。
（２）点Ｃ２−Ｋを計算し、復号化されたメッセージとする。
【００７３】
楕円エルガマル暗号の安全性について説明する。上の通信を傍受した攻撃者の目標は、平文を解読することである。まず攻撃者は公開鍵Ｙ(＝[ｄ]Ｐ)を入手できるが、ここから秘密鍵ｄを算出することは楕円曲線離散対数問題を解くことを意味するため、困難である。次に攻撃者は暗号文Ｃ＝（Ｃ１，Ｃ２）＝（［ｒ］Ｐ，Ｍ＋［ｒ］Ｙ）を入手（傍受）できる。Ｃ１とベースポイントＰから乱数ｒを算出することは楕円曲線離散対数問題を解くことを意味するため、困難である。従って攻撃者にとって乱数ｒは入手できないため、そのスカラー倍点［ｒ］Ｙ＝［ｒ］［ｄ］Ｐの算出も困難であり、Ｃ２から平文Ｍを入手することも困難である。このように、楕円曲線離散対数問題が困難であるという前提の下で、楕円エルガマル暗号の解読は困難であることが知られている。
【００７４】
以下では、楕円曲線上の退化なペアリング関数について説明する。楕円曲線上のペアリング関数は退化なものと非退化なものの２つに分けられ、退化なペアリング関数は非退化なペアリング関数を用いて構成することができる。そこで、まず非退化なペアリング関数の一実施例であるヴェイユペアリング（Ｗｅｉｌ Ｐａｒｉｎｇ）について説明し、次にヴェイユペアリングを用いて退化なペアリング関数を構成する方法を述べる。
【００７５】
Ｅを有限体ＧＦ(ｐm)上の楕円曲線とする。楕円曲線上のペアリングｅとは、楕円曲線の２点に対してある値を出力し、かつ以下の性質を満たす関数である。
【００７６】
(１) ｅ(Ｐ１，Ｐ２＋Ｐ３)＝ｅ(Ｐ１，Ｐ２)・ｅ(Ｐ１，Ｐ３)
(２) ｅ(Ｐ１，Ｐ２)＝ｅ(Ｐ２，Ｐ１)
そして、非退化なペアリングとは、上記の条件(１)，(２)に加えて、条件(３) ｅ(Ｐ１，Ｐ１)＝１を満たすものをいう。
【００７７】
非退化なペアリングの例として、ヴェイユペアリングが知られている。以下では、ヴェイユペアリングの説明をする。自然数ｎに対して、Ｅ［ｎ］を［ｎ］Ｐ＝∞を満たす楕円曲線Ｅの点Ｐの全体の集合とする。集合Ｅ［ｎ］の２点Ｐ１，Ｐ２に対するヴェイユペアリングｅ（Ｐ１，Ｐ２）を以下のように定める。
【００７８】
ｅ（Ｐ１， Ｐ２）＝ｆP1（Ｕ＋Ｐ２）／ｆP1（Ｕ）・ｆP2（Ｖ）／ｆP2（Ｖ＋Ｐ１）
ここで、ｆP1， ｆP2は、前記楕円曲線の点Ｐ１， Ｐ２からそれぞれ構成されるＥ上の関数である。また、例えばｆP1（Ｕ）とは、ｆP1にＥ上の点Ｕを代入した値を表す。なお、ｆP1， ｆP2の構成については後述する。また、点Ｕ， Ｖは、それぞれＵ＋Ｐ２及びＶ＋Ｐ１が無限遠点∞にならない楕円曲線Ｅ上の任意の点である。
【００７９】
次に、楕円曲線の点Ｐに対する、関数ｆPを導出するアルゴリズムを説明する。まず、方程式ｌi,j（ｘ，ｙ）＝０を以下のように定義する。
【００８０】
ｉ≠ｊのとき、楕円曲線Ｅ上の２点［ｉ］Ｐ及び［ｊ］Ｐを通る直線
ｉ＝ｊのとき、楕円曲線Ｅ上の点［ｉ］Ｐを通り楕円曲線Ｅに接する直線
また、方程式ｖi（ｘ，ｙ）＝０を、［ｉ］Ｐ及び無限遠点∞を通る直線と定義する。次に、関数ｇnを以下の漸化式で定義する。ただし、ｑは自然数である。
【００８１】
ｇ1＝１
ｇ2q＝ｌq,q（ｘ，ｙ）／ｖ2q（ｘ，ｙ）・ｇq2
ｇ2q+1＝ｌ2q,1（ｘ，ｙ）／ｖ2q+1（ｘ，ｙ）・ｇ2q
このとき、ｆP＝ｇpとなることが知られている。
【００８２】
次に、退化なペアリングについて説明する。退化なペアリングとは、非退化でないペアリングと定義され、一例として、以下のように構成できる。
【００８３】
ｐを素数とし、ｐ＝２ ｍｏｄ ３を満たすとする。有限体ＧＦ（ｐ)上の楕円曲線Ｅ’：ｙ2＝ｘ3＋１とする。ここで、先述のように楕円曲線は本来ＧＦ（ｐm）において定義可能であるが、ここではｍ＝１の場合に限定する点に注意する。ｗを１の原始３乗根とし、写像Φ：(ｘ，ｙ)−＞(ｗｘ，ｙ)とする。このとき、楕円曲線Ｅ’の点(ｘ，ｙ)に対してｆ(ｘ，ｙ)も楕円曲線Ｅ’の点となる。
【００８４】
以上により、楕円曲線の２点Ｐ１，Ｐ２に対して、以下の式により退化なペアリングｅ’を構成することができる。
【００８５】
ｅ’（Ｐ１，Ｐ２）＝ｅ（Ｐ１，Φ（Ｐ２））
ここで、ｅはヴェイユペアリングである。なお、退化なペアリングの構成に用いる写像Φはdistortion写像と呼ばれる。
【図面の簡単な説明】
【００８６】
【図１】本発明の第１の実施形態に係る認証システムの機能ブロック図である。
【図２】本発明の第１の実施形態に係る認証システムの全体の処理手順を示したフローチャートである。
【図３】本発明の第１の実施形態に係る認証システムの攻撃検知の処理手順を示したフローチャートである。
【図４】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｅ１の算出の処理手順を示したフローチャートである。
【図５】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｅ２の算出の処理手順を示したフローチャートである。
【図６】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｅ（Ｐ１，Ｐ２）の算出の処理手順を示したフローチャートである。
【図７】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｆSの算出の処理手順を示したフローチャートである。
【図８】本発明の第２の実施形態に係る認証システムの攻撃検知の処理手順を示したフローチャートである。
【図９】ＩＣカードのハードウェア構成を示した図である。
【図１０】コンピュータである認証装置のハードウェア構成を示した図である。
【図１１】従来の一般的な認証システムの全体の処理手順を示したフローチャートである。
【符号の説明】
【００８７】
１１ ＣＰＵ
１２ ＲＯＭ
１３ ＲＡＭ
１４ 不揮発性メモリ
１５ 入出力インタフェース
１７ バス
３１ ＣＰＵ
３２ 主記憶
３３ 補助記憶装置
３４ 出力インタフェース
３５ 入力インタフェース
３６ ＩＣカードＲ／Ｗインタフェース
３７ バス
３８ モニタ
３９ キーボード
４０ マウス
４１ ＩＣカードリーダ／ライタ
１００ ＩＣカード
１０１ 記憶部
１０３ 公開情報記憶部
１０５ 秘密鍵記憶部
１０７ 攻撃検知部
１０９ 復号化処理部
１１１ 制御部
１１３ 通信部
３００ 認証装置
３０１ 記憶部
３０３ 公開情報記憶部
３０５ 乱数生成部
３０７ 認証処理部
３０９ 暗号化処理部
３１１ 通信部
３１３ 制御部
【技術分野】
【０００１】
本発明は、楕円曲線暗号を用いた認証処理に対する故障利用攻撃を検知する認証用媒体に関する。
【背景技術】
【０００２】
ＩＣカード等の認証用媒体を用いた認証においては、一般に公開鍵暗号方式が用いられる。ＩＣカードには公開鍵暗号方式の秘密鍵及び暗号化（復号化）回路が実装されており、これにより暗号学的に安全性が保証された認証を行うことを可能としている。
【０００３】
ＩＣカード認証で通常用いられる公開鍵暗号方式として、楕円曲線暗号が知られている。楕円曲線暗号は、やはり公開鍵暗号方式の一つであるＲＳＡ暗号方式と比べ、より短い鍵長で同程度のセキュリティレベルを確保できるという特徴を持つ。例えば、鍵長１６０ビットの楕円曲線暗号と、鍵長１０２４ビットのＲＳＡ暗号のセキュリティレベルがほぼ同じであることが知られている。そのため、楕円曲線暗号は、メモリや処理パワーの少ないＩＣカード、携帯電話などの小型デバイスにおける実装に適している。
【０００４】
楕円曲線暗号の1つである楕円エルガマル（ＥｌＧａｍａｌ）暗号を利用したＩＣカード認証システムにおける認証処理の例を説明する。ｐを素数とし、有限体ＧＦ（ｐ）上の楕円曲線ＥにおけるベースポイントをＧとする（各記号の詳細については後述する）。ＩＣカードには、前記楕円曲線に基づく楕円曲線暗号の秘密鍵ｄが秘密に格納されている。また、認証装置には、前記楕円曲線暗号の公開鍵Ｙ＝[ｄ]Ｇが格納されている（ここで、記号[ ]はスカラー倍算を示す）。
【０００５】
図１１に基づき、認証装置がＩＣカード（正確には、ＩＣカードを保持するユーザ）を認証するための処理フローを説明する。認証装置は、ＩＣカードが入力されたことを検知する（ステップＳ７０１）。次に認証装置は、適当なメッセージＭを生成して記憶装置に格納するとともに、公開鍵を用いて前記メッセージＭを暗号化することで暗号文Ｃ＝（Ｃ１，Ｃ２）を生成する（ステップＳ７０２）。ここで、Ｃ１＝[ｒ]Ｇ、Ｃ２＝Ｍ＋[ｒ]Ｙである（ｒは適当に選んだ乱数）。そして認証装置は、生成した暗号文ＣをＩＣカードに送信する（ステップＳ７０３）。
【０００６】
次にＩＣカードは、前記暗号文Ｃを受信する（ステップＳ７０５）。ＩＣカードは、秘密鍵を用いてＣ１を復号することで、中間メッセージＫを得る（ステップＳ７０７）。具体的には、ＩＣカードはＫ＝[ｄ]Ｃ１を計算する。また、ＩＣカードは、Ｃ２を復号し、復号メッセージＭ’を得る（ステップＳ７０９）。具体的には、ＩＣカードはＭ’＝Ｃ２−Ｋを計算する。そして、ＩＣカードは、Ｍ’を認証装置に送信する（ステップＳ７１１）。
【０００７】
認証装置は、前記Ｍ’を受信する（ステップＳ７１３）。認証装置は、記憶装置から前記Ｍを読み出し、Ｍと前記受信したＭ’を比較する（ステップＳ７１５）。認証装置は、ＭとＭ’が一致した場合に「認証成功」と判定する（ステップＳ７１７）。一方、ＭとＭ’が一致しなかった場合には、認証装置は「認証失敗」と判定する（ステップＳ７１９）。この認証システムの安全性は、ＩＣカードが秘密鍵を有しない限り、ＩＣカードは手順３においてＣに基づいてＭ’＝ＭとなるＭ’を算出できないことに基づいている。
【０００８】
ＩＣカードにおいて秘密鍵は耐タンパに保持される為、外部から直接読み取られることは考えにくいが、これを間接的に推測する攻撃がいくつか存在する。そのような攻撃の１つに、故障利用攻撃がある。故障利用攻撃では、ＩＣカードが秘密鍵を用いて暗号化または復号化を行っている最中に、外部から供給電圧を急激に変化させる等の物理的変化を与えることにより、ＩＣカードの処理結果を意図的に誤らせる。攻撃者は、認証装置上でこの誤らせた処理結果を得ることで、所定の条件の下で、秘密鍵を推測することが可能となる。
【０００９】
すなわち、ステップＳ７０７およびＳ７０８において、ＩＣカードは、認証装置から受け取った暗号文Ｃから復号メッセージを計算するが、攻撃者はその際に高電圧などの物理的操作をＩＣカードに与える。このときＩＣカードが正当なもの（認証装置上の公開鍵に対応する秘密鍵を有するもの）であっても、復号メッセージは正しく計算されず（Ｍ’≠ＭとなるＭ’が算出される）、ＩＣカードは認証装置に対して正しくない結果を送信することになる。攻撃者は、その誤った出力を得て、当該出力を解析することで、ＩＣカード内に保持されている秘密鍵を推測できる。
【００１０】
上の例のように、ＩＣカード上の楕円曲線暗号を用いた認証システムにおいて故障利用攻撃を受けると、ＩＣカードの秘密鍵を攻撃者に特定される可能性がある。すなわち、故障利用攻撃は秘密鍵の漏洩に繋がるため、その対策が強く望まれている。
【００１１】
故障利用攻撃を検知するための従来技術として、ＩＣカードが故障利用攻撃を受けた場合に、その計算結果が楕円曲線暗号で利用する楕円曲線の点にならないことがある性質を利用する方式が知られている（例えば、特許文献１）。従来技術では、ＩＣカードに係る楕円曲線Ｅが方程式
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
で表されるとき、関数Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)を
Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6−(ｙ2＋ａ1ｘｙ＋ａ3ｙ)
と定める。ＩＣカードは、前記中間メッセージＫを求めた後、Ｋが楕円曲線Ｅの点であるかを判定する。ここで、Ｍ’ではなくＫの値を検証する理由は、攻撃者は秘密鍵ｄを推定したいのでＫ＝[ｄ]Ｃ１の計算時に故障利用攻撃を行うと考えられるためである。これに対し、Ｍ’＝Ｃ２−Ｋであり、すなわちＭ’の計算にｄは用いられないため、Ｍ’の計算時のみに故障利用攻撃を行っても意味がない。
【００１２】
ＩＣカードがＫが楕円曲線Ｅの点であるかを判定するためには、具体的には、前記Ｋを(ｘk，ｙk)と表すと、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)を計算すればよい。そして、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)＝０であればＫは楕円曲線の点であり、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)≠０であればＫは楕円曲線の点でないと判定できる。Ｋは本来は楕円曲線Ｅの点であるはずである（詳しくは後述するが、楕円曲線暗号では、元のメッセージ、暗号文、および復号メッセージはいずれも楕円曲線の点である）。そこで、Ｋが楕円曲線の点でないとき、ＩＣカードは、故障利用攻撃を受けたと判断することができる。
【特許文献１】特開2004-252433号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかし、従来技術は、ＩＣカードが故障利用攻撃を受けていることをそもそも検知できない場合が多数あるという課題がある。具体的には、特許文献１に係る従来技術は、故障利用攻撃を受けた計算結果がたまたま楕円曲線上の点になる場合には、攻撃を検知することができない。このような場合は、全暗号文の１／２が該当することが知られている。これは、ｘの値が与えられたときに、式Ｅを満たすｙを求める（すなわち、ｙに係る方程式Ｅが解ける）ことができる確率が１／２だからである。すなわち、従来技術では、２回に１回の割合で、故障利用攻撃の検知に失敗するという問題がある。
【００１４】
上記の問題は、従来技術が、中間メッセージＫのみを用いて故障利用攻撃の有無を判定していることに起因する。中間メッセージＫが満たすべき前記条件（楕円曲線上の点であること）を満たすＫは沢山ある（Ｋの種類数は、楕円曲線Ｅの点の数に等しい）。そのため、故障利用攻撃を受けて誤ったＫが算出されたとしても、当該誤ったＫが前記条件を満たしてしまう可能性も高いものとなる。
【課題を解決するための手段】
【００１５】
上記の課題を解決するために、本発明は、中間メッセージＫの検証を、Ｋの暗号文であるＣ１を用いて行うことを特徴とする。すなわち、暗号文Ｃ１と中間メッセージＫの間にある１対１の対応関係（中間メッセージＫは、確かに、暗号文Ｃ１を復号したものであるということ）を、復号化処理とは別のアプローチで把握することにより、前記課題を解決する。
【００１６】
これを実現するため、本発明は、楕円曲線上の退化なペアリングと呼ばれる関数を利用する。すなわち、退化なペアリングを用いて暗号文Ｃ１と中間メッセージＫとの対応関係を把握し、これにより故障利用攻撃を検出する。
【００１７】
楕円曲線上のペアリングｅとは、楕円曲線の２点に対してある値を出力し、かつ以下の２つの条件を満たす関数である（ここで、Ｐ１、Ｐ２、Ｐ３は楕円曲線の点とする）。
(１) ｅ(Ｐ１，Ｐ２＋Ｐ３)＝ｅ(Ｐ１，Ｐ２)・ｅ(Ｐ１，Ｐ３)
(２) ｅ(Ｐ１，Ｐ２)＝ｅ(Ｐ２，Ｐ１)
また、上記の２条件に加え、以下の条件を満たすｅを「退化なペアリング」と呼ぶ。
(３) ｅ(Ｐ１，Ｐ１)≠１
なお、楕円曲線上の退化なペアリングそのものは公知技術である。従来、退化なペアリングは、楕円曲線暗号に対する攻撃技術や、楕円曲線暗号そのものの内部処理において使用されている。
【００１８】
本発明に係るＩＣカードは、前記の退化なペアリングｅを用いて、故障利用攻撃の有無を検出する。これは、具体的には以下のように行う。ＩＣカードは、先述した暗号文Ｃ＝（Ｃ１，Ｃ２）の復号処理において、Ｃ１から中間メッセージＫを求めた後に、前記ベースポイントＧと当該Ｋとに基づきｅ１＝ｅ（Ｇ，Ｋ）を計算するとともに、前記公開鍵Ｙと当該Ｃ１とに基づきｅ２＝ｅ（Ｙ，Ｃ１）を計算する。ここで、ｅは退化なペアリング関数とする。そして、ＩＣカードは、ｅ１＝ｅ２が成り立つかを判定する。もしｅ１＝ｅ２であれば、ＩＣカードは、故障利用攻撃が行われなかったと判断する。反対に、ｅ１≠ｅ２であれば、ＩＣカードは、故障利用攻撃が行われたと判断する。
【発明の効果】
【００１９】
開示のＩＣカードによれば、従来技術よりも高い確率で故障利用攻撃を検知することが可能となるという効果を奏する。
【００２０】
故障利用攻撃が行われていない場合を考える。このとき、退化なペアリングの性質に基づき、前記ｅ１は、
ｅ１＝ｅ（Ｇ，Ｋ）＝ｅ（Ｇ，[ｄ]Ｃ１）＝ｅ（Ｇ，[ｄ−１]Ｃ１＋Ｃ１）
＝ｅ（Ｇ，[ｄ−１]Ｃ１）・ｅ（Ｇ，Ｃ１）
＝ｅ（Ｇ，[ｄ−２]Ｃ１＋Ｃ１）・ｅ（Ｇ，Ｃ１）
＝ｅ（Ｇ，[ｄ−２]Ｃ１）・ｅ（Ｇ，Ｃ１）2
と式変形できる。同様の式変形を繰り返すと、結局、関係式ｅ１＝ｅ（Ｇ，Ｃ１）dが導ける。また、前記ｅ２に対しても、同様にして、
ｅ２＝ｅ（Ｙ，Ｃ１）＝ｅ（[ｄ]Ｇ，Ｃ１）＝ｅ（Ｇ，Ｃ１）d
と式変形でき、結局、関係式ｅ２＝ｅ（Ｇ，Ｃ１）dが導ける。すなわち、もし故障利用攻撃が行われていなければ、必ず、ｅ１＝ｅ２が成立する。この対偶から、もしｅ１≠ｅ２であれば、１００％の確率で、故障利用攻撃が行われている。
【００２１】
反対に、故障利用攻撃が行われた場合を考える。このとき、Ｃ１から偶然にＫが算出される場合（ランダムな確率で発生するので、確率１／ｐで発生する）を除いて、Ｃ１からＫとは異なるＫ’が算出される。このとき、ｅ１＝ｅ（Ｇ，Ｋ’）≠ｅ（Ｇ，Ｃ１）dとなる。すなわち、もし故障利用攻撃が行われたならば、１−（１／ｐ）の確率で、ｅ１≠ｅ２が成立する。ここで、通常、ｐは非常に大きな素数であるので、１／ｐは無視できるほど小さい確率となる。したがって、もしｅ１＝ｅ２であれば、１００％に限りなく近い確率で、故障利用攻撃が行われていない。
【００２２】
すなわち、ｅ１＝ｅ２が成り立つか否かを判定することで、故障利用攻撃を高精度に検出できる。したがって、本願の方式によれば、ＩＣカード内においてほぼ１００％の割合で故障利用攻撃の有無を検出でき、故障利用攻撃による秘密鍵の漏洩を回避することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施の形態を図面を参照して説明する。なお、本発明は、楕円曲線暗号や楕円曲線上の退化なペアリングといった離散数学に基づいており、発明の理解が容易ではない側面がある。そこで、本発明の実施形態に係る説明においては、楕円曲線暗号や楕円曲線上の退化なペアリングを構成したという前提の下で、それらを用いて故障利用攻撃の検知を可能にした認証システムについて説明する。そして、前記楕円エルガマル暗号と楕円曲線上の退化なペアリング関数については、各実施形態に係る説明の後で、最後に説明する。
【００２４】
図１に、本発明の第１の実施形態に係る認証システムの機能ブロック図を示す。認証システムは、認証用媒体の一例であるＩＣカード１００と、認証装置３００とを備える。
【００２５】
ＩＣカード１００は、記憶部１０１、公開情報記憶部１０３、秘密鍵記憶部１０５、攻撃検知部１０７、復号化処理部１０９、通信部１１１、及び制御部１１３を備える。記憶部１０１は、種々の演算結果等を格納して記憶する。公開情報記憶部１０３は、ＰＫＩ（公開鍵基盤）の公開情報を格納して保持する。ここで公開情報は、公開鍵により身元が保証されるユーザの識別子、ユーザの公開鍵Ｙ、公開鍵暗号方式を少なくとも含む必要があり、例えばＸ．５０９で規定された公開鍵証明書を用いることができる。本実施例においては、公開鍵暗号として、楕円曲線暗号の１つである楕円エルガマル暗号を用いる。先述した公開鍵暗号方式には、公開鍵暗号として楕円エルガマル暗号を用いることに加え、その公開パラメータである有限体ＧＦ（ｐ）、ＧＦ（ｐ）上の楕円曲線Ｅ、およびベースポイントＧそれぞれを含む（各記号の詳細については後述する）。ここで、ｐは素数であり、ｐ＝２ ｍｏｄ ３を満たすとする。すなわち、Eは素数位数の楕円曲線である。なお、ＦＩＰＳ１８６−２を含む多くの楕円曲線暗号標準において、素数位数の楕円曲線暗号が採用されている。秘密鍵記憶部１０５は、前記公開鍵に対応する秘密鍵ｄを格納し、秘密に保持する。ここで、秘密鍵ｄと前記公開鍵Ｙの間には、Ｙ＝[ｄ]Ｇの関係が成り立っているものとする。攻撃検知部１０７は、故障利用攻撃の検知を行う。復号化処理部１０９は、暗号文を復号して復号メッセージを得る。通信部１１１は、認証装置３００とＩＣカード１００の間で暗号文や復号メッセージといったデータを送受する。制御部１１３は、故障利用攻撃検知部１０７、復号化処理部１０９、及び通信部１１１の制御を司る。
【００２６】
一方、認証装置３００は、記憶部３０１、公開情報記憶部３０３、乱数生成部３０５、認証処理部３０７、暗号化処理部３０９、通信部３１１、及び制御部３１３を備える。記憶部３０１は、種々の演算結果等を格納して記憶する。公開情報記憶部３０３は、ＰＫＩ（公開鍵基盤）の公開情報を格納して保持する。この公開情報は、ＩＣカード１００の公開情報記憶部１０３において記憶されるものと同等の情報である。乱数生成部３０５は、乱数を生成する。ここで生成する乱数は、数学的手法により生成される擬似乱数であっても良い。認証処理部３０７は、ユーザの認証処理を行う。暗号化処理部３０９は、メッセージを暗号化して暗号文を生成する。通信部３１１は、認証装置３００とＩＣカード１００の間で暗号文や復号メッセージといったデータを送受する。制御部３１３は、乱数生成部３０５、認証処理部３０７、暗号化処理部３０９、及び通信部３１１の制御を司る。
【００２７】
図２に基づき、第１の実施形態に係る認証システムの処理フローについて説明する。
【００２８】
まず、認証装置は、ＩＣカードが入力されたことを検知する（ステップＳ１）。次に認証装置３００の暗号化処理部３０９は、ＩＣカード１００に送信する暗号文を作成する（ステップＳ２）。これは以下のように行う。暗号化処理部３０９は、楕円曲線上の点であるメッセージＭを適当に選択し、記憶部３０１に格納する。次に、乱数生成部３０５は、乱数ｒを生成し、記憶部３０１に格納する。なお、前記メッセージＭについては、乱数生成部３０５が前記ｒとは別の乱数ｒ’を生成し、暗号化処理部３０９が前記ｒ’に基づいて生成することができる。次に、暗号化処理部３０９は、ベースポイントＧを公開情報記憶部３０３から読み出し、また前記ｒを記憶部３０１から読み出し、読み出したＧとｒとを用いて点[r]Ｇを計算し、計算結果を記憶部３０１上の変数Ｃ１に格納する。さらに、暗号化処理部３０９は、公開鍵Ｙを公開情報記憶部３０３から読み出し、また前記ｒとＭとを記憶部３０１から読み出し、読み出したＹ、Ｍ、およびｒを用いて点Ｍ＋[ｒ]Ｙを計算し、計算結果を記憶部３０１上の変数Ｃ２に格納する。Ｃ＝（Ｃ１，Ｃ２）を暗号文とする。
【００２９】
次に認証装置３００の通信部３１３は、ＩＣカード１００に対し、作成した暗号文Ｃ＝（Ｃ１，Ｃ２）を送信する（ステップＳ３）。ＩＣカード１００の通信部１１３は、送信された暗号文Ｃを受信し、記憶部１０１に格納する（ステップＳ５）。次にＩＣカードの復号化処理部１０９は、前記Ｃ１を記憶部１０１から読み出し、読み出したＣ１を復号する（ステップＳ７）。すなわち、復号化処理部１０９は、秘密鍵ｄを秘密鍵記憶部１０５から読み出し、読み出したｄを用いて点[ｄ]Ｃ１を計算し、計算結果を記憶部１０１上の変数Ｋに格納する。
【００３０】
次にＩＣカード１００の攻撃検知部１０７は、故障利用攻撃の有無を判定する（ステップＳ９）。判定の処理の詳細については後述する。次に攻撃検知部１０７は、ステップＳ９の判定結果に基づき、処理を分岐する（ステップＳ１１）。もし判定結果がＹＥＳ（攻撃を検知）の場合、ＩＣカードの制御部１１１は、必要に応じ所定の異常系処理を行う（ステップＳ１３）。すなわち、攻撃を検知したということは、ＩＣカードに故障利用攻撃が行われたことを意味する。そのため、認証の成否に意味が無くなり、またＩＣカードが復号メッセージを認証装置３００に出力すると、攻撃者がそれを盗聴してしまう。そこで、制御部１１１は、復号メッセージを認証装置３００に送信することはせず、管理者に通報したりエラーログを残すといった異常系処理を行う。そして、今回の認証処理は終了する。
【００３１】
一方、もしステップＳ９の判定結果がＮＯ（攻撃を検知せず）の場合、ＩＣカード１００の復号化処理部１０９は、メッセージＭ’を復号する（ステップＳ１５）。すなわち、復号化処理部１０９は、記憶部からＫとＣ２とを読み出し、読み出したＫとＣ２とにより点Ｃ２−Ｋを計算し、計算結果を記憶部１０１上の変数Ｍ’に格納する。
【００３２】
次に、ＩＣカード１００の通信部１１３は、認証装置３００に対し、復号したメッセージＭ’を送信する（ステップＳ１７）。認証装置３００の通信部３１１は、送信されたメッセージＭ’を受信し、記憶部３０１に格納する（ステップＳ１９）。最後に、認証装置３００の認証処理部３０７は、認証の成否を判定する（ステップＳ２１）。すなわち、認証処理部３０７は、認証装置３００の暗号化処理部３０９が選択して暗号化したメッセージＭと、ＩＣカードから受信したメッセージであるＭ’とをそれぞれ記憶部３０１から読み出し、比較する。そして、Ｍ＝Ｍ’の場合、認証処理部３０７は、「認証成功」と判定する（ステップＳ２３）。もし認証装置３００の公開情報記憶部３０３に格納された公開鍵ＹとＩＣカード１００の秘密鍵記憶部１０５に格納された秘密鍵ｄとの間に対応関係があれば、認証装置３００で暗号化したメッセージがＩＣカード１００で正しく復号されて元のメッセージに戻るはずであるため、Ｍ＝Ｍ’が成立するはずであるからである。反対に、Ｍ≠Ｍ’の場合、認証処理部３０７は、「認証失敗」と判定する（ステップＳ２５）。認証が成功でも失敗でも、認証装置の制御部３１１は、今回の認証処理を終了し、入力待ちとなる。
【００３３】
次に、図３に基づき、第１の実施形態に係るＩＣカードの攻撃検知部１０７が故障利用攻撃の有無を判定する処理（ステップＳ９）の詳細な処理フローについて説明する。攻撃検知部１０７は、前記ベースポイントＧ、前記暗号文Ｃ１を復号して得られたＫを記憶部１０１から読み出し、読み出したＧおよびＫを用いて、ｅ１＝ｅ(Ｇ，Ｋ) を算出する（ステップＳ１０１）。ここで、ｅは、後述する退化なペアリング関数である。ステップＳ１０１の処理の詳細については後述する。次に、攻撃検知部１０７は、公開鍵Ｙを公開情報記憶部１０３から読み出し、また前記暗号文Ｃ1を記憶部１０１から読み出し、読み出したＹおよびＣ１を用いて、ｅ２＝ｅ(Ｙ，Ｃ1)を算出する（ステップＳ１０２）。ステップ１０２の処理の詳細についても後述する。次に、攻撃検知部１０７は、ｅ１＝ｅ２が成立するか否かを確かめる（ステップＳ１０３）。もしｅ１＝ｅ２が成立する場合には、攻撃検知部１０７は故障利用攻撃を受けなかったと判定する（ステップＳ１０４）。また、もしｅ１＝ｅ２が成立しない場合には、攻撃検知部１０７は故障利用攻撃を受けたと判定する（ステップＳ１０５）。
【００３４】
次に、ステップＳ１０１でｅ１＝ｅ(Ｇ，Ｋ)を算出する処理、 および、ステップＳ１０２でｅ２＝ｅ(Ｙ，Ｃ1)を算出する処理の詳細を説明する。これら２つの処理は一部を除いてほとんど同じであるため、以下ではｅ１を算出する処理であるステップＳ１０１について詳細に述べ、ｅ２を算出する処理であるステップＳ１０２については、ステップＳ１０１と異なる点を中心に簡単に説明する。
【００３５】
図４の処理フローに基づき、ｅ１＝ｅ(Ｇ，Ｋ)を算出する処理（ステップＳ１０１）の詳細について説明する。まず攻撃検知部１０７は、公開情報記憶部１０３からベースポイントＧを読み出すと共に、記憶部１０１から前記算出したＫを読み出し、記憶部１０１上の変数Ｐ１にＧを、Ｐ２にＫを、それぞれ格納する（ステップＳ２０１）。ここで、Ｐ１、Ｐ２はそれぞれ平面上の点であり、（ｘ，ｙ）のような座標形式で表せるとする。そして攻撃検知部１０７は、ｅ(Ｐ１，Ｐ２)を算出する（ステップＳ２０２）。
【００３６】
ここで、図６の処理フローに基づき、ｅ(Ｐ１，Ｐ２)を算出する処理（ステップＳ２０２）の詳細について説明する。まず攻撃検知部１０７は、記憶部１０１からＰ２を読み出し、Φ（Ｐ２）を計算し、計算結果をＰ２に格納する（ステップＳ４０１）。なお、写像Φは、以下で定義される。
【００３７】
Φ：(ｘ，ｙ) → (ｗｘ，ｙ)
ここで、ｗは１の原始３乗根である。次に攻撃検知部１０７は、記憶部１０１上の変数ＳにＰ１を格納する（ステップＳ４０２）。そして攻撃検知部１０７は、関数ｆSを導出する（ステップＳ４０３）。
【００３８】
ここで、図７の処理フローに基づき、楕円曲線Ｅの点Ｓに対して、ｆSを算出する処理の詳細について説明する。まず攻撃検知部１０７は、前記有限体の位数ｐの２進展開を算出し、記憶部上の変数のｔ個組である（ｎt-1，．．．，ｎ0）2に格納する（ステップＳ５０１）。次に攻撃検知部１０７は、記憶部１０１上の変数ｉ、ｒにそれぞれ自然数ｔ−２、１を格納し、記憶部１０１上の変数ｆに関数１を格納し、さらに、記憶部１０１上の変数Ｖに前記楕円曲線Ｅの点であるＳを格納する（ステップＳ５０２）。
【００３９】
次に攻撃検知部１０７は、記憶部１０１上の変数ｉを読み出し、ｉ＜０であるかを判定する（ステップＳ５０３）。ｉ＜０でない場合（分岐のＮＯ）、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅの点Ｖを通り且つ楕円曲線Ｅに接する直線を求め、当該直線をｌr,r（ｘ，ｙ）＝０とする（ステップＳ５０４）。次に攻撃検知部１０７は、前記読み出したＶに基づき、点[２]Ｖを算出し、記憶部１０１上の変数Ｖに格納する（ステップＳ５０５）。また、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅ上のＶ及び無限遠点∞を通る直線を求め、当該直線をｖ2r｝（ｘ，ｙ）＝０とする（ステップＳ５０６）。そして、攻撃検知部１０７は、前記記憶部１０１に格納したｆを読み出し、前記求めた関数ｌr,r（ｘ，ｙ）およびｖ2r（ｘ，ｙ）とに基づき、関数ｆ2・ｌr,r（ｘ，ｙ）／ｖ2r（ｘ，ｙ）を算出し、当該算出した関数を記憶部１０１上の変数ｆに格納する（ステップＳ５０７）。また、攻撃検知部１０７は、前記読み出したｒの値に基づき２ｒを算出し、当該算出した値を記憶部１０１上の変数ｒに格納する（ステップＳ５０８）。
【００４０】
次に攻撃検知部１０７は、記憶部１０１上のｎiを読み出し、その値が１であるかを判定する（ステップＳ５０９）。ｎi＝１でない場合（分岐のＮＯ）、攻撃検知部は、後述するステップＳ５１５の処理を行う。一方、ｎi＝１である場合（分岐のＹＥＳ）、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅの点Ｖおよび前記点Ｓを通る直線を求め、当該直線をｌr,1（ｘ，ｙ）＝０とする（ステップＳ５１０）。次に攻撃検知部１０７は、前記読み出したＶおよびＳに基づき、点Ｖ＋Ｓを算出し、記憶部１０１上の変数Ｖに格納する（ステップＳ５１１）。また、攻撃検知部１０７は、記憶部１０１上の変数Ｖおよびｒを読み出し、楕円曲線Ｅ上のＶ及び無限遠点∞を通る直線を求め、当該直線をｖr+1（ｘ，ｙ）＝０とする（ステップＳ５１２）。そして、攻撃検知部１０７は、前記記憶部１０１に格納したｆを読み出し、前記求めた関数ｌr,1（ｘ，ｙ）およびｖr+1（ｘ，ｙ）とに基づき、関数ｆ・ｌr,1（ｘ，ｙ）／ｖr+1（ｘ，ｙ）を算出し、当該算出した関数を記憶部１０１上の変数ｆに格納する（ステップＳ５１３）。また、攻撃検知部１０７は、前記読み出したｒの値に基づきｒ＋１を算出し、当該算出した値を記憶部１０１上の変数ｒに格納する（ステップＳ５１４）。
【００４１】
攻撃検知部１０７は、記憶部１０１上のｉを読み出し、ｉ＋１を算出し、当該算出した値を記憶部１０１上の変数ｉに格納する（ステップＳ５１５）。そして、攻撃検知部１０７は、ステップＳ５０３に戻って処理を繰り返す。
【００４２】
一方、ステップＳ５０３の判定において、ｉ＜０である場合（分岐のＹＥＳ）、攻撃検知部１０７は、記憶部１０１からｆを読みだし、記憶部１０１上の変数ｆSに格納する（ステップＳ５１６）。以上により、所望の関数ｆSの導出が完了する。
【００４３】
図６の処理の説明に戻って、攻撃検知部１０７は、導出した関数ｆSを記憶部１０１上のｆP1に格納する（ステップＳ４０４）。また、攻撃検知部１０７は、記憶部１０１上の変数ＳにＰ２を格納する（ステップＳ４０５）。そして攻撃検知部１０７は、先述した図７の処理フローに基づき、再び関数ｆSを導出する（ステップＳ４０６）。そして、導出した関数ｆSを記憶部１０１上のｆP2に格納する（ステップＳ４０７）。
【００４４】
次に攻撃検知部１０７は、楕円曲線Ｅ上の２点を任意に選択し、それぞれ記憶部１０１上のＵ，Ｖに格納する（ステップＳ４０８）。そして攻撃検知部１０７は、Ｐ１，Ｐ２，Ｕ，Ｖをそれぞれ記憶部１０１から読み出して、平面上の２点Ｖ＋Ｐ１、および、Ｕ＋Ｐ２を計算し、これら２点が∞（無限遠点）でないかを判定する（ステップＳ４０９）。そして、Ｖ＋Ｐ１、Ｕ＋Ｐ２のいずれもが∞でない場合（分岐のＹＥＳ）、攻撃検知部１０７は、記憶部１０１から関数ｆP2及び関数ｆP2を読み出し、以下の式に基づいてｅ(Ｐ１，Ｐ２)を計算する（ステップＳ４１０）。
【００４５】
ｅ（Ｐ１， Ｐ２）＝ｆP1（Ｕ＋Ｐ２）／ｆP1（Ｕ）・ｆP2（Ｐ２）／ｆP2（Ｖ＋Ｐ２）
一方、ステップＳ４０９において、Ｖ＋Ｐ１、Ｕ＋Ｐ２のいずれかが∞である場合（分岐のＮＯ）、攻撃検知部１０７は、ステップＳ３０４の処理に戻って、Ｕ，Ｖを再選択する。
【００４６】
図４の処理の説明に戻って、攻撃検知部１０７は、算出したｅ（Ｐ１， Ｐ２）を記憶部１０１のｅ１に格納する（ステップＳ２０３）。これにより、ｅ１＝ｅ(Ｇ，Ｋ) を算出する処理は終了する。
【００４７】
次に、図５の処理フローに基づき、ｅ２＝ｅ(Ｙ，Ｃ1) を算出する処理（ステップＳ１０２）の詳細について説明する。まず攻撃検知部１０７は、公開情報記憶部１０３から公開鍵Ｙを読み出すと共に、記憶部１０１から前記暗号文Ｃ１を読み出し、記憶部１０１上の変数Ｐ１にＹを、Ｐ２にＣ１を、それぞれ格納する（ステップＳ３０１）。そして攻撃検知部１０７は、先述した図６の処理フローに基づき、ｅ(Ｐ１，Ｐ２)を算出する（ステップＳ３０２）。最後に、攻撃検知部１０７は、算出したｅ（Ｐ１， Ｐ２）を記憶部１０１のｅ２に格納する（ステップＳ３０３）。これにより、ｅ２＝ｅ(Ｙ，Ｃ１) を算出する処理は終了する。
【００４８】
以上のように、本発明の第１の実施形態に係る認証システムによれば、故障利用攻撃を高い確率で検知することが可能となる。すなわち、ｅ１＝ｅ２が成り立つか否かを判定することで、故障利用攻撃を高精度に検出できる。したがって、本願の方式によれば、ＩＣカード内においてほぼ１００％の割合で故障利用攻撃の有無を検出でき、故障利用攻撃による秘密鍵の漏洩を回避することができる。
【００４９】
以下では本発明の第２の実施形態について説明する。第２の実施形態は、第１の実施形態と多くの部分は同じであるが、ＩＣカードが故障利用攻撃の有無を判定する処理であるステップＳ９の詳細な処理フローが図３と異なる。具体的には、まず先述した従来の故障利用攻撃検知処理を行った後に、実施例１に記載の故障利用攻撃検知処理を行うものである。
【００５０】
図８に基づき、第２の実施形態に係るＩＣカードの攻撃検知部１０７が故障利用攻撃の有無を判定する処理（ステップＳ９）の処理フローについて説明する。楕円曲線Ｅが方程式
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
で表されるとき、関数Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)を
Ｉｓ＿ｏｎ＿ＥＣ(ｘ，ｙ)＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6−(ｙ2＋ａ1ｘｙ＋ａ3ｙ)
と定める。
【００５１】
まず攻撃検知部１０７は、ステップＳ７で算出したＫ＝（ｘk，ｙk）を記憶装置から読み出し、Ｋに基づき、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)を計算する（ステップＳ６０１）。そして攻撃検知部１０７は、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)＝０であるかを判定する（ステップＳ６０２）。Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)≠０であれば（分岐のＮＯ）、攻撃検知部１０７は故障利用攻撃を受けたと判定する（ステップＳ６０７）。Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)≠０であるならば、Ｋは楕円曲線Ｅの点ではなく、故障利用攻撃を受けたと判断できるためである。
【００５２】
一方、ステップＳ６０１で、Ｉｓ＿ｏｎ＿ＥＣ(ｘk，ｙk)＝０であれば（分岐のＹＥＳ）、攻撃検知部１０７は、前記ベースポイントＧ、前記暗号文Ｃ１を復号して得られたＫを記憶部１０１から読み出し、読み出したＧおよびＫを用いて、ｅ１＝ｅ(Ｇ，Ｋ) を算出する（ステップＳ６０３）。ここで、ｅは、退化なペアリング関数である。次に、攻撃検知部１０７は、公開鍵Ｙを公開情報記憶部１０３から読み出し、また前記暗号文Ｃ1を記憶部１０１から読み出し、読み出したＹおよびＣ１を用いて、ｅ２＝ｅ(Ｙ，Ｃ1)を算出する（ステップＳ６０４）。ここで、ステップ６０３、Ｓ６０４の処理の詳細は、それぞれ図４および図５の処理フローに従えばよい。次に、攻撃検知部１０７は、ｅ１＝ｅ２が成立するか否かを確かめる（ステップＳ６０５）。もしｅ１＝ｅ２が成立する場合には、攻撃検知部１０７は故障利用攻撃を受けなかったと判定する（ステップＳ６０６）。また、もしｅ１＝ｅ２が成立しない場合には、攻撃検知部１０７は故障利用攻撃を受けたと判定する（ステップＳ６０７）。
【００５３】
以上のように、第２の実施形態によれば、第１の実施形態と同じ作用・効果を奏する。すなわち、故障利用攻撃を高い確率で検知することが可能となる。さらに、第２の実施形態は、故障利用攻撃を検知できない場合も多いが処理性能に優れた従来の故障利用攻撃検知方法を前段で実施することにより、検知処理の処理時間の平均を約半分にすることができる。したがって、第２の実施形態によれば、第１の実施形態に比べて、検知の処理を高速化できるという特有の効果を奏する。
【００５４】
以上、第１〜２の実施形態による認証システムの構成を説明したが、本発明は上記実施形態に限るものではなく、その技術的思想の範囲内で種々の設計変更が可能である。例えば、上記の実施形態においては、楕円曲線暗号として楕円エルガマル暗号を用いたが、楕円ＲＳＡ暗号を含む他の楕円曲線暗号を用いても同様な故障利用検知は可能である。また、非退化なペアリングとしてヴェイユペアリングを用いたが、その代わりにテイトペアリング（Ｔａｔｅ Ｐａｒｉｎｇ）やこれらの変形を採用することもできる。また、ＩＣカード１００は、携帯用情報端末であれば良く、例えば携帯電話やＰＤＡ端末等であってもよい。
【００５５】
第１〜２の実施形態による認証システムに係るＩＣカード１００のハードウェア構成を図９に示す。図９のＩＣカード１００においては、Central Processing Unit（CPU）１１、Read only memory（ROM）１２、Random Access Memory（RAM）１３、不揮発性メモリ１４、および、入出力インタフェース１５がバス１７で接続されている。
【００５６】
CPU１１は後述するROM１２に格納されたプログラムやデータを読み込んで実行する。ROM１２は、上書きができない記憶装置であり、プログラムやデータが格納される。RAM１３は、CPU１１がワーク用の記憶装置として使用する。不揮発性メモリ１４は、電気的に書き込み可能な記憶装置であり、個人情報のようなICカード毎に異なるデータを格納する。入出力インタフェース１５は、後述するＩＣカードリーダとの間でデータの入出力を行う。
【００５７】
上記ハードウェア構成を、図１の機能ブロックと対応付けると以下のようになる。ＩＣカード１００の各処理部（攻撃検知部１０７、複号化処理部１０９、通信部１１１、及び制御部１１３）は、ＲＯＭ１２に格納される。公開情報記憶部１０３、及び秘密鍵記憶部１０５は不揮発メモリ１４により実現される。記憶部１０１はＲＡＭ１３により実現される。ＣＰＵ１１は、ＲＯＭ１２から各処理部を読み込んで実行する。このときＣＰＵ１１は、必要に応じて、不揮発性メモリ１４からデータを読み込み、ＲＡＭ１３に対しデータの読み書きを行う。
【００５８】
また、第１〜２の実施形態による認証システムに係る認証装置３００は、コンピュータ上で動作するプログラムによっても実現することができる。
【００５９】
本願発明に係るプログラムを実行するコンピュータである認証装置のハードウェア構成の例を図１０に示す。認証装置３００のハードウェア構成として、例えば、CPU３１、主記憶３２、補助記憶装置３３、出力インタフェース３４、入力インタフェース３５、ＩＣカードＲ／Ｗインタフェース３６がバス３７で接続されている。
【００６０】
CPU３１は後述する主記憶３２に格納されたプログラムを実行する。主記憶３２としては、通常はRAMが用いられ、後述する補助記憶装置３３から実行するプログラムや使用するデータを読み込んで一時的に格納する。補助記憶装置３３としては、通常はHard Disk Drive（HDD）が用いられ、プログラムやデータを格納してファイルとして保存する。なお、補助記憶装置３３としては、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の外部記憶媒体を用いることもできる。
【００６１】
出力インタフェース３４には出力装置の一つとして表示装置であるモニタ３８が接続される。プログラムの実行結果などがモニタに出力され表示される。入力インタフェース３５には入力装置としてキーボード３９やマウス４０が接続され、これら入力装置からデータが入力される。ＩＣカードＲ／Ｗインタフェース３６には、ＩＣカードリーダ／ライタ４１が接続され、ＩＣカードリーダ／ライタ４１にアクセスしたＩＣカードとデータの入出力を行う。
【００６２】
上記ハードウェア構成を、図１の機能ブロックと対応付けると以下のようになる。コンピュータを認証装置３００として機能させるためのプログラム（乱数生成部３０５、認証処理部３０７、暗号化処理部３０９、通信部３１１、及び制御部３１３）、及びデータ（記憶部３０１、公開情報記憶部３０３）を予め補助記憶装置１３に格納させておく。プログラムが起動されると、当該プログラムおよびデータはまず主記憶１２に読み込まれ、その後主記憶１２とCPU１１とが連携することでプログラムが実行される。プログラム実行中に記憶部３０１に格納される各種データは、通常は主記憶に書き込まれるが、必要に応じて補助記憶装置１３に退避させてもよい。
【００６３】
最後に、上記実施形態の前提となる技術である楕円エルガマル暗号、および、楕円曲線上の退化なペアリング関数について、数式を用いて詳細に説明する。
【００６４】
以下では、楕円エルガマル暗号について説明する。まず暗号方式の一方式である公開鍵暗号を説明し、次に公開鍵暗号の一方式である楕円曲線暗号を説明し、最後に楕円曲線暗号の一方式である楕円エルガマル暗号を説明する。
【００６５】
まず暗号方式の一方式である公開鍵暗号を説明する。暗号方式には、公開鍵暗号方式と共通鍵暗号方式とが含まれる。公開鍵暗号方式は、暗号化と復号化とで異なる鍵を用いる方式である。典型的な公開鍵暗号方式では、暗号化の為の鍵（公開鍵）はあらかじめ公開され、誰もが入手できるようになっている。受信者は、送信したい相手の公開鍵を用いて平文を暗号化して暗号文を作成し、その暗号文を受信者に送信する。暗号文を復号化するための鍵（秘密鍵）は受信者のみが知る秘密情報として保持され、受信者はこの秘密鍵を用いて暗号文を復号化することにより、平文を得る。
【００６６】
次に公開鍵暗号の一方式である楕円曲線暗号を説明する。楕円曲線暗号は公開鍵暗号方式に含まれる暗号方式の一つで、楕円曲線と呼ばれる代数曲線の点の間の演算規則を利用した暗号方式の総称である。ｐを素数、ｍを自然数とすると、要素数ｐmの有限体ＧＦ(ｐm)上の楕円曲線とは、方程式
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
を満たす点(ｘ，ｙ)の集合に、無限遠点とよばれる点∞を加えた集合のことをいう。無限遠点∞を０と表すこともある。ここで、定数ａ1、ａ2、ａ3、ａ4、および、ａ6、ならびに、変数ｘ、および、ｙは、有限体ＧＦ(ｐm)の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式(アファイン座標)で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現できない唯一の点である。このように、アファイン座標では無限遠点以外の点はＧＦ(ｐm)の２つの要素の組として表される。
【００６７】
楕円曲線Ｅ上の点の間には、以下のようにして点の加算と呼ばれる演算が定義できる。ＰをＧＦ(ｐm)上の楕円曲線Ｅ上の点とする。まず、Ｐの逆元−Ｐを以下のように定義する。
【００６８】
(１)Ｐ＝∞のとき、−Ｐ＝∞
(２)Ｐ≠∞のとき（Ｐ＝(ｘ、ｙ)とする）、−Ｐ＝(ｘ，−ｙ)
次に、Ｐ１，Ｐ２をＧＦ(ｐm)上の楕円曲線Ｅ上の２点とする。このとき、Ｐ１とＰ２の和Ｐ１＋Ｐ２を以下のように定義する。
【００６９】
(１)Ｐ１＝∞のとき、Ｐ１＋Ｐ２＝Ｐ２
(２)Ｐ２＝∞のとき、Ｐ１＋Ｐ２＝Ｐ１
(３)Ｐ１＝−Ｐ２のとき、Ｐ１＋Ｐ２＝∞
(４)上記以外のとき（Ｐ１＝(ｘ1，ｙ1)，Ｐ２＝(ｘ2，ｙ2)，Ｐ１＋Ｐ２＝(ｘ3，ｙ3)とする）、
ｘ3＝λ2＋ａ1λ−ａ2−ｘ1−ｘ2
ｙ3＝(ｘ1−ｘ2)λ−ｙ1−ａ1ｘ3−ａ3
ただし、
λ＝(ｙ2−ｙ1)／(ｘ2−ｘ1)・・・（Ｐ１≠Ｐ２のとき）
λ＝(３ｘ12＋２ａ2ｘ1＋ａ4−ａ1ｙ1)／(２ｙ1＋ａ1ｘ1＋ａ3)・・・（Ｐ１＝Ｐ２のとき）
なお、Ｐ１≠Ｐ２のときにＰ１＋Ｐ２を計算することを楕円加算という。また、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝[２]Ｐ１を計算することを楕円２倍算という。
【００７０】
楕円曲線とその上の点Ｐが与えられているとき、ある整数ｄに対して、点[ｄ]Ｐ＝Ｐ＋Ｐ＋・・・＋Ｐ(ｄ個の和)を計算することをスカラー倍算という。ここで、点Ｐをベースポイントと呼ぶ。スカラー倍算とは逆に、楕円曲線とその上の点Ｐとそのスカラー倍点[ｄ]Ｐが与えられているとき、整数（スカラー）ｄを求める問題を楕円曲線離散対数問題という。楕円曲線暗号の安全性は、スカラー倍算は容易に計算可能だが、楕円曲線離散対数問題を解くことは困難であるという事実に依存している。このため多くの楕円曲線暗号方式は、スカラーｄを秘密鍵、スカラー倍点[ｄ]Ｐを公開鍵の一部として使用することが多い。
【００７１】
次に、楕円曲線暗号の一方式である、楕円エルガマル暗号について説明する。有限体ＧＦ(ｐm )、その上の楕円曲線Ｅ、ベースポイントＰはあらかじめ定義されており、公開されているものとする。このとき、楕円エルガマル暗号における受信者の秘密鍵をｄとすると、公開鍵をＹ＝[ｄ]Ｐと定義できる。
【００７２】
受信者にメッセージＭを秘密裏に送りたい送信者は、受信者の公開鍵Ｙを用いて、以下の暗号化処理を行う。ここでメッセージＭは楕円曲線Ｅの点として表されているものとする。
（１）(疑似)乱数ｒを生成する。
（２）点[ｒ]Ｐを計算し、Ｃ１として保持する。
（３）点Ｍ＋[ｒ]Ｙを計算し、Ｃ２として保持する。
（４）Ｃ１とＣ２のペア(Ｃ１，Ｃ２)を暗号文として受信者に送る。
暗号文(Ｃ１，Ｃ２)を受け取った受信者は、自分の秘密鍵ｄを用いて、以下の復号化処理を行う。
（１）点[ｄ]Ｃ１を計算し、Ｋとして保持する。
（２）点Ｃ２−Ｋを計算し、復号化されたメッセージとする。
【００７３】
楕円エルガマル暗号の安全性について説明する。上の通信を傍受した攻撃者の目標は、平文を解読することである。まず攻撃者は公開鍵Ｙ(＝[ｄ]Ｐ)を入手できるが、ここから秘密鍵ｄを算出することは楕円曲線離散対数問題を解くことを意味するため、困難である。次に攻撃者は暗号文Ｃ＝（Ｃ１，Ｃ２）＝（［ｒ］Ｐ，Ｍ＋［ｒ］Ｙ）を入手（傍受）できる。Ｃ１とベースポイントＰから乱数ｒを算出することは楕円曲線離散対数問題を解くことを意味するため、困難である。従って攻撃者にとって乱数ｒは入手できないため、そのスカラー倍点［ｒ］Ｙ＝［ｒ］［ｄ］Ｐの算出も困難であり、Ｃ２から平文Ｍを入手することも困難である。このように、楕円曲線離散対数問題が困難であるという前提の下で、楕円エルガマル暗号の解読は困難であることが知られている。
【００７４】
以下では、楕円曲線上の退化なペアリング関数について説明する。楕円曲線上のペアリング関数は退化なものと非退化なものの２つに分けられ、退化なペアリング関数は非退化なペアリング関数を用いて構成することができる。そこで、まず非退化なペアリング関数の一実施例であるヴェイユペアリング（Ｗｅｉｌ Ｐａｒｉｎｇ）について説明し、次にヴェイユペアリングを用いて退化なペアリング関数を構成する方法を述べる。
【００７５】
Ｅを有限体ＧＦ(ｐm)上の楕円曲線とする。楕円曲線上のペアリングｅとは、楕円曲線の２点に対してある値を出力し、かつ以下の性質を満たす関数である。
【００７６】
(１) ｅ(Ｐ１，Ｐ２＋Ｐ３)＝ｅ(Ｐ１，Ｐ２)・ｅ(Ｐ１，Ｐ３)
(２) ｅ(Ｐ１，Ｐ２)＝ｅ(Ｐ２，Ｐ１)
そして、非退化なペアリングとは、上記の条件(１)，(２)に加えて、条件(３) ｅ(Ｐ１，Ｐ１)＝１を満たすものをいう。
【００７７】
非退化なペアリングの例として、ヴェイユペアリングが知られている。以下では、ヴェイユペアリングの説明をする。自然数ｎに対して、Ｅ［ｎ］を［ｎ］Ｐ＝∞を満たす楕円曲線Ｅの点Ｐの全体の集合とする。集合Ｅ［ｎ］の２点Ｐ１，Ｐ２に対するヴェイユペアリングｅ（Ｐ１，Ｐ２）を以下のように定める。
【００７８】
ｅ（Ｐ１， Ｐ２）＝ｆP1（Ｕ＋Ｐ２）／ｆP1（Ｕ）・ｆP2（Ｖ）／ｆP2（Ｖ＋Ｐ１）
ここで、ｆP1， ｆP2は、前記楕円曲線の点Ｐ１， Ｐ２からそれぞれ構成されるＥ上の関数である。また、例えばｆP1（Ｕ）とは、ｆP1にＥ上の点Ｕを代入した値を表す。なお、ｆP1， ｆP2の構成については後述する。また、点Ｕ， Ｖは、それぞれＵ＋Ｐ２及びＶ＋Ｐ１が無限遠点∞にならない楕円曲線Ｅ上の任意の点である。
【００７９】
次に、楕円曲線の点Ｐに対する、関数ｆPを導出するアルゴリズムを説明する。まず、方程式ｌi,j（ｘ，ｙ）＝０を以下のように定義する。
【００８０】
ｉ≠ｊのとき、楕円曲線Ｅ上の２点［ｉ］Ｐ及び［ｊ］Ｐを通る直線
ｉ＝ｊのとき、楕円曲線Ｅ上の点［ｉ］Ｐを通り楕円曲線Ｅに接する直線
また、方程式ｖi（ｘ，ｙ）＝０を、［ｉ］Ｐ及び無限遠点∞を通る直線と定義する。次に、関数ｇnを以下の漸化式で定義する。ただし、ｑは自然数である。
【００８１】
ｇ1＝１
ｇ2q＝ｌq,q（ｘ，ｙ）／ｖ2q（ｘ，ｙ）・ｇq2
ｇ2q+1＝ｌ2q,1（ｘ，ｙ）／ｖ2q+1（ｘ，ｙ）・ｇ2q
このとき、ｆP＝ｇpとなることが知られている。
【００８２】
次に、退化なペアリングについて説明する。退化なペアリングとは、非退化でないペアリングと定義され、一例として、以下のように構成できる。
【００８３】
ｐを素数とし、ｐ＝２ ｍｏｄ ３を満たすとする。有限体ＧＦ（ｐ)上の楕円曲線Ｅ’：ｙ2＝ｘ3＋１とする。ここで、先述のように楕円曲線は本来ＧＦ（ｐm）において定義可能であるが、ここではｍ＝１の場合に限定する点に注意する。ｗを１の原始３乗根とし、写像Φ：(ｘ，ｙ)−＞(ｗｘ，ｙ)とする。このとき、楕円曲線Ｅ’の点(ｘ，ｙ)に対してｆ(ｘ，ｙ)も楕円曲線Ｅ’の点となる。
【００８４】
以上により、楕円曲線の２点Ｐ１，Ｐ２に対して、以下の式により退化なペアリングｅ’を構成することができる。
【００８５】
ｅ’（Ｐ１，Ｐ２）＝ｅ（Ｐ１，Φ（Ｐ２））
ここで、ｅはヴェイユペアリングである。なお、退化なペアリングの構成に用いる写像Φはdistortion写像と呼ばれる。
【図面の簡単な説明】
【００８６】
【図１】本発明の第１の実施形態に係る認証システムの機能ブロック図である。
【図２】本発明の第１の実施形態に係る認証システムの全体の処理手順を示したフローチャートである。
【図３】本発明の第１の実施形態に係る認証システムの攻撃検知の処理手順を示したフローチャートである。
【図４】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｅ１の算出の処理手順を示したフローチャートである。
【図５】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｅ２の算出の処理手順を示したフローチャートである。
【図６】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｅ（Ｐ１，Ｐ２）の算出の処理手順を示したフローチャートである。
【図７】本発明の第１の実施形態に係る認証システムの攻撃検知処理における、ｆSの算出の処理手順を示したフローチャートである。
【図８】本発明の第２の実施形態に係る認証システムの攻撃検知の処理手順を示したフローチャートである。
【図９】ＩＣカードのハードウェア構成を示した図である。
【図１０】コンピュータである認証装置のハードウェア構成を示した図である。
【図１１】従来の一般的な認証システムの全体の処理手順を示したフローチャートである。
【符号の説明】
【００８７】
１１ ＣＰＵ
１２ ＲＯＭ
１３ ＲＡＭ
１４ 不揮発性メモリ
１５ 入出力インタフェース
１７ バス
３１ ＣＰＵ
３２ 主記憶
３３ 補助記憶装置
３４ 出力インタフェース
３５ 入力インタフェース
３６ ＩＣカードＲ／Ｗインタフェース
３７ バス
３８ モニタ
３９ キーボード
４０ マウス
４１ ＩＣカードリーダ／ライタ
１００ ＩＣカード
１０１ 記憶部
１０３ 公開情報記憶部
１０５ 秘密鍵記憶部
１０７ 攻撃検知部
１０９ 復号化処理部
１１１ 制御部
１１３ 通信部
３００ 認証装置
３０１ 記憶部
３０３ 公開情報記憶部
３０５ 乱数生成部
３０７ 認証処理部
３０９ 暗号化処理部
３１１ 通信部
３１３ 制御部
【特許請求の範囲】
【請求項１】
所定の楕円曲線に基づく楕円エルガマル暗号の秘密鍵ｄを秘密に格納した秘密鍵記憶部と、
前記楕円エルガマル暗号の公開鍵ＹとベースポイントＧとを格納した公開情報記憶部と、
前記楕円エルガマル暗号によって暗号化された暗号文Ｃ＝（Ｃ１，Ｃ２）の入力を受付ける入力部と、
当該暗号文Ｃを、記憶部に格納された秘密鍵ｄに基づき、Ｋ＝[ｄ]Ｃ１およびＭ’＝Ｃ２−Ｋを順に算出することで復号メッセージＭ’を生成する復号部と、当該復号メッセージＭ’を出力する出力部とを備える認証用媒体において、
退化なペアリングｅに基づき関係式ｅ（Ｇ，Ｋ）＝ｅ（Ｙ，Ｃ１）が成立するかを判定する判定部を、
さらに備え、
前記出力部は、前記関係式が成立する場合に、前記復号メッセージＭ’を出力する
ことを特徴とする認証用媒体。
【請求項２】
前記判定部は、前記復号部が算出したＫが前記所定の楕円曲線の点である場合に、前記関係式に基づく判定を行う、
ことを特徴とする請求項１に記載の認証用媒体。
【請求項１】
所定の楕円曲線に基づく楕円エルガマル暗号の秘密鍵ｄを秘密に格納した秘密鍵記憶部と、
前記楕円エルガマル暗号の公開鍵ＹとベースポイントＧとを格納した公開情報記憶部と、
前記楕円エルガマル暗号によって暗号化された暗号文Ｃ＝（Ｃ１，Ｃ２）の入力を受付ける入力部と、
当該暗号文Ｃを、記憶部に格納された秘密鍵ｄに基づき、Ｋ＝[ｄ]Ｃ１およびＭ’＝Ｃ２−Ｋを順に算出することで復号メッセージＭ’を生成する復号部と、当該復号メッセージＭ’を出力する出力部とを備える認証用媒体において、
退化なペアリングｅに基づき関係式ｅ（Ｇ，Ｋ）＝ｅ（Ｙ，Ｃ１）が成立するかを判定する判定部を、
さらに備え、
前記出力部は、前記関係式が成立する場合に、前記復号メッセージＭ’を出力する
ことを特徴とする認証用媒体。
【請求項２】
前記判定部は、前記復号部が算出したＫが前記所定の楕円曲線の点である場合に、前記関係式に基づく判定を行う、
ことを特徴とする請求項１に記載の認証用媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１０−２２６４０２（Ｐ２０１０−２２６４０２Ａ）
【公開日】平成２２年１０月７日（２０１０．１０．７）
【国際特許分類】
【出願番号】特願２００９−７１０９６（Ｐ２００９−７１０９６）
【出願日】平成２１年３月２４日（２００９．３．２４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２２年１０月７日（２０１０．１０．７）
【国際特許分類】
【出願日】平成２１年３月２４日（２００９．３．２４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]