情報処理装置、演算検証方法およびプログラム
【課題】より簡便な方法で故障利用攻撃の有無を判定することが可能な、情報処理装置、演算検証方法およびプログラムを提供すること。
【解決手段】本発明に係る情報処理装置に対して、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算部と、楕円曲線Ｅ上の点Ｐと、スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証部と、を設けた。
（Ｐ＋Ｑ）＋Ｇ＝Ｐ＋（Ｑ＋Ｇ） ・・・（式１）
【解決手段】本発明に係る情報処理装置に対して、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算部と、楕円曲線Ｅ上の点Ｐと、スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証部と、を設けた。
（Ｐ＋Ｑ）＋Ｇ＝Ｐ＋（Ｑ＋Ｇ） ・・・（式１）
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、演算検証方法およびプログラムに関する。
【背景技術】
【０００２】
楕円曲線暗号は、楕円曲線上における離散対数問題の困難性を利用した暗号方式であり、同じ安全性水準の下で、ＲＳＡ暗号に比べて短い鍵長で済むといった特徴を持つ。この楕円曲線暗号は、ＥＣＤＳＡ（Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｔｏｒｉｔｈｍ）署名による機器間認証など、様々な場面で利用されている暗号方式である。
【０００３】
楕円曲線暗号を用いて生成された秘密鍵を悪意のある第三者が不正に取得するための方法として、故障利用攻撃と呼ばれるものがある。この故障利用攻撃は、不正なシステムパラメータを与えたり、暗号処理中に故意に外部から故障（中間値を保持するレジスタの破壊等）を起こさせたりすることにより、悪意のある第三者が不正な計算結果を入手し、秘
密鍵を推定するという攻撃である。上述のような故障利用攻撃は、１９９７年にＢｏｎｅｈらによってＲＳＡ暗号に対する差分故障攻撃（Ｄｉｆｆｅｒｅｎｔｉａｌ ＦａｕｌｔＡｎａｌｙｓｉｓ ａｔｔａｃｋ：ＤＦＡ）として初めて提案され、２０００年にＢｉｅｈｌらによって、楕円曲線暗号へと拡張された。
【０００４】
ＤＦＡのような故障利用攻撃に対する対策としては、計算結果を出力する前に計算結果の正当性を検証し、不正な値であれば計算結果を出力しない、という方法をとる。シンプルな対策手法として、例えば、２度計算による検算がある。この方法は、同じ暗号処理を２度実施し、演算結果が同じでなければ演算結果を出力しない、という方法である。この方法は、全く同じ故障を連続して２度行うことは困難であることを想定している検証方法である。しかしながら、同じ演算を繰り返すため計算コストは対策なしの場合に比べ２倍になり、また、計算効率も好ましいものではないため、より効率的な故障検知方法が希求されている。
【０００５】
また、故障検知方法の別の例として、例えば以下に示す特許文献１では、演算により得られた点（Ｘ，Ｙ）に関し、楕円曲線を表す式の右辺および左辺を個別に計算し、左辺＝右辺が成立するか否かで故障利用攻撃の有無を判断する方法が記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２５２４３３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記特許文献１に記載の方法では、楕円曲線を表す式の右辺および左辺に該当する値をそれぞれ計算する機能と、得られた２種類の値を比較する機能と、を別途設ける必要がある。そのため、上記特許文献１に記載の方法をハードウェア実装する場合には、特別な処理部が必要となって回路規模が増加するという問題があり、上記特許文献１に記載の方法をソフトウェア的に処理する場合には、計算コストの増加が生じるという問題があった。
【０００８】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、より簡便な方法で故障利用攻撃の有無を判定することが可能な、情報処理装置、演算検証方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明のある観点によれば、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算部と、前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証部と、を備える情報処理装置が提供される。
【００１０】
（Ｐ＋Ｑ）＋Ｇ＝Ｐ＋（Ｑ＋Ｇ） ・・・（式１）
【００１１】
かかる構成によれば、スカラ倍演算部は、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算する。また、演算検証部は、楕円曲線Ｅ上の点Ｐと、スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、楕円曲線Ｅ上の任意の点Ｇと、を用いて、上記式１における等号が成立するか否かを検証する。
【００１２】
前記楕円曲線Ｅは、有限体Ｆｑ（ｑ＝ｐｍ，ｍ∈Ｎ，ｐ＞３）上で定義された楕円曲線ＥＡ：ｙ２＝ｘ３＋ａｘ＋ｂ（ａ，ｂ∈Ｆｑ）、または、標数２の有限体Ｆ２＾ｍ（ｍ∈Ｎ）上で定義された楕円曲線ＥＢ：ｙ２＋ｘｙ＝ｘ３＋ａ２ｘ２＋ａ６（ａ２，ａ６∈Ｆ２＾ｍ）であることが好ましい。
【００１３】
前記演算検証部は、前記式１における等号が成立しなかった場合、前記点Ｐが適式な値ではなかった、または、点Ｑに改ざんが加えられたと判断する。
【００１４】
前記情報処理装置は、自装置が秘匿すべき情報である秘匿情報を格納する記憶部を更に備え、前記楕円曲線Ｅ上の任意の点Ｇは、前記秘匿情報の一つとして前記記憶部に格納されることが好ましい。
【００１５】
前記記憶部には、自装置が保持する秘密鍵ｄが格納されており、前記スカラ倍演算部は、スカラ倍演算の係数ｓとして前記秘密鍵ｄを用いてもよい。
【００１６】
前記演算検証部は、前記点Ｐまたは前記点Ｑの代わりに、自装置が保持している公開鍵または信頼できる他の情報処理装置が保持している公開鍵を用いて、前記式１における等号が成立するか否かを検証してもよい。
【００１７】
また、上記課題を解決するために、本発明の別の観点によれば、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するステップと、前記楕円曲線Ｅ上の点Ｐと、算出された点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証するステップとを含む演算検証方法が提供される。
【００１８】
また、上記課題を解決するために、本発明の更に別の観点によれば、コンピュータに、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算機能と、前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算機能により算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証機能と、を実現させるためのプログラムが提供される。
【発明の効果】
【００１９】
以上説明したように本発明によれば、楕円曲線上の群の性質を利用することで、より簡便な方法で故障利用攻撃の有無を判定することが可能である。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施形態に係る情報処理装置の構成を説明するための説明図である。
【図２】同実施形態に係る演算検証方法を説明するための流れ図である。
【図３】本発明の実施形態に係る情報処理装置のハードウェア構成を説明するための説明図である。
【図４】スカラ倍演算のアルゴリズムの一例を説明するための説明図である。
【図５】小さい位数を使った攻撃について説明するための流れ図である。
【図６Ａ】スカラ倍演算中に故障を生じさせる攻撃について説明するための流れ図である。
【図６Ｂ】スカラ倍演算中に故障を生じさせる攻撃について説明するための流れ図である。
【発明を実施するための形態】
【００２１】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２２】
なお、説明は、以下の順序で行うものとする。
（１）楕円曲線について
（２）故障利用攻撃について
（３）第１の実施形態
（３−１）情報処理装置の構成について
（３−２）演算検証方法について
（４）本発明の実施形態に係る情報処理装置のハードウェア構成について
（５）まとめ
【００２３】
（楕円曲線について）
まず、本発明の実施形態に係る情報処理装置および演算検証方法について説明するに先立ち、本発明の実施形態で利用する楕円曲線について、詳細に説明する。
【００２４】
本発明の実施形態に係る情報処理装置および演算検証方法では、楕円曲線Ｅとして、以下の２つの楕円曲線を扱う。
【００２５】
（ｉ）有限体Ｆｑ（ｑ＝ｐｍ，ｍ∈Ｎ，ｐ＞３）上で定義された楕円曲線ＥＡ：ｙ２＝ｘ３＋ａｘ＋ｂ（ａ，ｂ∈Ｆｑ）
（ｉｉ）標数２の有限体（バイナリフィールド）Ｆ２＾ｍ（ｍ∈Ｎ）上で定義された楕円曲線ＥＢ：ｙ２＋ｘｙ＝ｘ３＋ａ２ｘ２＋ａ６（ａ２，ａ６∈Ｆ２＾ｍ）
【００２６】
以下、標数ｐ＞３の有限体上で定義された楕円曲線ＥＡを例にとって説明するが、標数２の有限体上で定義された楕円曲線ＥＢに関しても同様のことが成立する。
【００２７】
楕円曲線ＥＡ上の点の集合を、Ｅ（Ｆｑ）＝｛（ｘ，ｙ）∈Ｆｑ×Ｆｑ｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪｛Ｏ｝で表現する。ここで、Ｏは無限遠点であり、後述する加法におけるＥ（Ｆｑ）の単位元である。
【００２８】
また、Ｅ（Ｆｑ）の濃度を楕円曲線の位数と呼び、＃Ｅ（Ｆｑ）＝ｈ・ｒで表現する。ここで、ｒは、素数とする。ｈはｃｏｆａｃｔｏｒと呼ばれる係数であるが、本明細書では、ｈ＝１とする。また、楕円曲線上のランダムに選んだ点をベースポイントＧとすると、楕円曲線の位数は素位数を仮定しているため、Ｇの位数はｒとなる。
【００２９】
ここで、楕円曲線を表す式中の係数と、定義体の位数ｐと、ベースポイントの位数ｒと、ベースポイントＧは、楕円曲線を特定するための楕円曲線パラメータとなる。
【００３０】
次に、楕円曲線上に存在する２つの点の加法演算について説明する。
楕円曲線ＥＡでは、楕円曲線上に存在する点Ｐ１＝（ｘ１，ｙ１）、Ｐ２＝（ｘ２，ｙ２）に対する加法演算を、次のように定義する。ここで、Ｐ３＝（ｘ３，ｙ３）＝Ｐ１＋Ｐ２である。
【００３１】
【数１】
・・・（式１１）
・・・（式１２）
・・・（式１３）
【００３２】
このとき、Ｅ（Ｆｑ）は、以下の４つの群の性質を満足することが知られている。
【００３３】
１．閉法則：Ｐ＋Ｑ∈Ｅ（Ｆｑ） ｆｏｒ ａｌｌ Ｐ，Ｑ∈Ｅ（Ｆｑ）
２．単位元の存在：Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐ ｆｏｒ ａｌｌ Ｐ∈Ｅ（Ｆｑ）
３．逆元の存在：Ｐ＋（−Ｐ）＝（−Ｐ）＋Ｐ＝Ｏ ｆｏｒ ａｌｌ Ｐ∈Ｅ（Ｆｑ）
４．結合則：（Ｐ＋Ｑ）＋Ｒ＝Ｐ＋（Ｑ＋Ｒ） ｆｏｒ ａｌｌ Ｐ，Ｑ，Ｒ∈Ｅ（Ｆｑ）
【００３４】
また、点Ｐをスカラ（ｓｃａｌａｒ）倍（ｓ倍）した点をｓＰと表し、次のように定義する。すなわち、下式から明らかなように、点ｓＰは、点Ｐに対して、点Ｐをｓ−１回加えた結果得られた点として定義される。
【００３５】
【数２】
・・・（式１４）
【００３６】
このようなスカラ倍演算を実行するための計算アルゴリズムとして、例えば図４に示したような、Ｄｏｕｂｌｅ ａｎｄ Ａｄｄ Ｍｅｔｈｏｄがある。
【００３７】
同様に、楕円曲線ＥＢでは、楕円曲線上に存在する点Ｐ１＝（ｘ１，ｙ１）、Ｐ２＝（ｘ２，ｙ２）に対する加法演算を、次のように定義する。ここで、Ｐ３＝（ｘ３，ｙ３）＝Ｐ１＋Ｐ２である。ここで、Ｐ１≠Ｐ２の場合には、加法演算は、以下の式１５〜１７のように定義され、Ｐ１＝Ｐ２の場合には、加法演算は、以下の式１８〜２０のように定義される。
【００３８】
【数３】
・・・（式１５）
・・・（式１６）
・・・（式１７）
【００３９】
【数４】
・・・（式１８）
・・・（式１９）
・・・（式２０）
【００４０】
ここで、値Ｐおよび値ｓＰを与えられて、これら２つの値からｓを求める問題を、楕円曲線上の離散対数問題（Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ｐｒｏｂｌｅｍ：ＥＣＤＬＰ）という。このＥＣＤＬＰは、Ｐの位数が十分に大きければ解くことが非常に困難であり、この困難性が楕円曲線暗号の安全性の根拠となっている。
【００４１】
（故障利用攻撃について）
次に、図５〜図６Ｂを参照しながら、代表的な２種類の故障利用攻撃について、詳細に説明する。図５は、小さい位数を使った攻撃について説明するための流れ図である。また、図６Ａおよび図６Ｂは、スカラ倍演算中に故障を生じさせる攻撃について説明するための流れ図である。
【００４２】
Ｂｉｅｈｌらは、入力Ｐを秘密情報ｄ倍したｄＰの計算を行うスカラ倍演算に対して、故障を起こすタイミングによって、以下に示すような２通りの攻撃手法が存在することを提案している。故障を起こすタイミングは、スカラ倍演算を行う前、および、スカラ倍演算中の２通りである。
【００４３】
まず、スカラ倍演算を行う前に故障を生じさせる攻撃について説明する。
このスカラ倍演算を行う前に故障を生じさせる攻撃は、小さな位数による攻撃（Ｓｍａｌｌ Ｏｒｄｅｒ Ｐｏｉｎｔ Ａｔｔａｃｋ）と呼ばれている。この小さな位数による攻撃について、図５を参照しながら詳細に説明する。なお、以下の説明では、楕円曲線Ｅが、標数ｐ＞３の有限体上で定義された楕円曲線Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂである場合について説明する。
【００４４】
攻撃者は、スカラ倍演算を行う装置に対して、被演算点Ｐ∈Ｅ（Ｆｑ）に関する情報を入力し（ステップＳ１１）、この被演算点Ｐが、正しい楕円曲線Ｅ（すなわち、ｙ２＝ｘ３＋ａｘ＋ｂ）上の点であるか否かを装置に判定させる（ステップＳ１３）。
【００４５】
攻撃者は、被演算点Ｐが正しい楕円曲線Ｅ上の点であることを判定した直後に故障を生じさせ、点Ｐのｘ成分またはｙ成分の１ｂｉｔを反転させる（故障攻撃）。攻撃の結果１ｂｉｔが反転した点をＰ１とすると、この点Ｐ１は、楕円曲線Ｅ１：ｙ２＝ｘ３＋ａｘ＋ｂ１となり、スカラ倍演算を行う装置によるスカラ倍ｄＰ１の計算（ステップＳ１５）は、楕円曲線Ｅ１上で行われることとなる。なお、式１１〜式１３から明らかなように、楕円曲線上の点の加算や２倍算の公式には、楕円曲線を定義する係数ｂは出現しない。そのため、点Ｐ１に対するスカラ倍演算ｄＰ１は、正しく計算されることがわかる。
【００４６】
出力ｄＰ１を取得した攻撃者は、出力ｄＰ１のｘ座標およびｙ座標から楕円曲線Ｅ１を求め、位数＃Ｅ１を計算する（ステップＳ１７）。その後、攻撃者は、位数＃Ｅ１が、ある程度小さい因数ｒ１を持つか否かを判定する（ステップＳ１９）。
【００４７】
点Ｐ１∈Ｅ１のｘ成分またはｙ成分の何れか一方は、故障を生じさせる前の正しい値であるため、攻撃者は、ｘ成分またはｙ成分を楕円曲線Ｅ１に代入して、Ｐ１を復元することができる（ステップＳ２１）。続いて、攻撃者は、Ｐ１，ｄＰ１それぞれを（＃Ｅ１／ｒ１）倍し（ステップＳ２３）、位数ｒ１の部分群Ｅ１（Ｆｑ）［ｒ１］に写像する。次に、攻撃者は、算出した（＃Ｅ１／ｒ１）Ｐ１および（＃Ｅ１／ｒ１）ｄＰ１を用いて離散対数問題を解き、ｄ ｍｏｄ ｒ１を取得する（ステップＳ２５）。
【００４８】
続いて、攻撃者は、ｒ１とは異なる、ある程度小さい素数ｒｉを位数に持つ別の楕円曲線Ｅｉに対して、上述の手順を繰り返し行い、秘密情報ｄに関する部分情報ｄ ｍｏｄ ｒｉを、ｒ＜Πｒｉとなるまで集める（ステップＳ２７）。最後に。攻撃者は、ｄ ｍｏｄ ｒｉに対して中国人の剰余定理（Ｃｈｉｎｅｓｅ ｒｅｍａｉｎｄｅｒ ｔｈｅｏｒｅｍ）を適用し、秘密情報ｄを導出する（ステップＳ２９）。以上説明したように、攻撃者は、上述の手順に則った故障利用攻撃を用いることで、秘密情報ｄを取得できる可能性がある。
【００４９】
以上、スカラ倍演算を行う前に故障を生じさせる攻撃について説明した。
続いて、スカラ倍演算中に故障を生じさせる攻撃について、図６Ａおよび図６Ｂを参照しながら、詳細に説明する。
【００５０】
ここで、スカラ倍演算を実行する装置は、図４に示したＲｉｇｈｔ−Ｔｏ−Ｌｅｆｔ Ａｌｇｏｒｉｔｈｍを用いてスカラ倍演算を実行するものとする。
【００５１】
まず、攻撃者は、スカラ倍演算を実行する装置に対して被演算点Ｐを入力し（ステップＳ２１）、スカラ倍演算を実行する装置にスカラ倍演算を実行させて（ステップＳ２３）、正しいスカラ倍点Ｑ＝ｄＰを取得する。
【００５２】
次に、攻撃者は、パラメータｉを、ｌｏｇ２ｄを超えない最大の整数に設定した上で、ｄ＝０とする（ステップＳ２５）。続いて、攻撃者は、パラメータｋを、推定したいビット数ｍに設定する（ステップＳ２７）。
【００５３】
次に、攻撃者は、取得した正しいスカラ倍点Ｑを保持したまま、スカラ倍演算を実行する装置に対して、再度Ｐを被演算点として入力する（ステップＳ２９）。
【００５４】
スカラ倍演算を実行する装置は、入力された被演算点Ｐに基づいてスカラ倍の演算を実行するが（ステップＳ３１）、攻撃者は、あるタイミングで、スカラ倍演算の中間値を保持するレジスタに対して、故障（１ｂｉｔ反転）を生じさせる。図６Ａに示した例では、攻撃者は、ｉ−ｍ≦ｊ＜ｉを満たすｊステップ目に故障攻撃を実行し、スカラ倍演算を実行する装置に不正な演算結果Ｑ’を生成させる。攻撃者は、スカラ倍演算を実行する装置から出力された演算結果Ｑ’を保持する（ステップＳ３３）。
【００５５】
攻撃者は、秘密鍵の既知のビットから故障を起こした位置までの秘密鍵の一部（部分鍵ｘ）を推定し（ステップＳ３５）、以下の式９０１に基づいて、Ｑから故障が発生したｉステップ目の中間値Ｑｘｉまで逆算する（ステップＳ３７）。この逆算は、２ｍパターン分実行される。
【００５６】
【数５】
・・・（式９０１）
【００５７】
次に、攻撃者は、Ｑｘｉ−ｋの１ｂｉｔを反転させｘ倍した値であるＱｘ＊を算出する（ステップＳ３９）。ここで、ｘは、推定した部分鍵である。攻撃者は、算出したＱｘ＊と不正な結果Ｑ’とを比較する（ステップＳ４１）。Ｑ’とＱｘ＊とが等しくない場合には、攻撃者は、パラメータｋをｋ−１と設定し（ステップＳ４３）、再びＱｘ＊を算出する（ステップＳ３９）。このように、攻撃者は、中間値Ｑｘｉのどの１ｂｉｔが故障により反転したのかが分からないため、考えられるすべての故障パターンに対して、推定した秘密鍵を利用して不正な演算結果Ｑ’の候補Ｑｘ＊を計算する。
【００５８】
他方、Ｑ’とＱｘ＊とが一致した場合には、部分鍵ｘの推定が正しかったことになり、攻撃者は、パラメータｄを、ｄをｘで割り切った値（ｄ｜ｘ）に設定することで、パラメータｄの更新を行う（ステップＳ４５）。続いて、攻撃者は、パラメータｉをｉ−ｋと設定し（ステップＳ４７）、パラメータｉが０になったか否かを判定する（ステップＳ４９）。パラメータｉが０ではない場合には、攻撃者は、ステップＳ２７に戻って、次のｍｂｉｔについて、ステップＳ２７から再び処理を行う。パラメータｉが０になった場合には、秘密鍵の全体が復元できたことを意味するため、推定した秘密鍵の全体ｄを出力する（ステップＳ５１）。
【００５９】
例えば、秘密鍵ｄの上位４ｂｉｔを推定したい場合を考える。この場合、攻撃者は、スカラ倍演算を実行する装置がそれらのビットでスカラ倍演算を実行しているときに、ｆａｕｌｔ ｉｎｊｅｃｔｉｏｎ（故障攻撃）を行う。ここで、ｄのビット長を１６０ｂｉｔとすれば、ｆａｕｌｔ ｉｎｊｅｃｔｉｏｎしたステップｉは、１５６≦ｉ＜１６０となる。攻撃者は、１５６ステップ目に故障が発生したものと仮定して、１５６ステップ目の中間値Ｑ１５６を復元する。攻撃者は、考えられるすべての部分鍵候補ｘ∈｛０，１｝４に対して、Ｑｘｉ＝Ｑ−ｘ・２１５６Ｐを計算する。攻撃者は、すべてのＱｘ１５６に対して１ｂｉｔ反転を行い、それらの値をｘ倍したＱｘ＊を計算する。このＱｘ＊が得られた不正な結果Ｑ’と一致すれば、推定した部分鍵ｘと、ｆａｕｌｔ ｉｎｊｅｃｔｉｏｎが生じたステップｉ＝１５６と、反転したｂｉｔの位置とが正しかったことになる。また、不正な結果Ｑ’と一致するＱｘ＊がなければ、攻撃者は、ｉ＝１５７として、ｉ＝１５６の場合と同様にすべてのＱｘ１５７の１ｂｉｔ反転させたものを求め、処理を進めていく。このように、鍵推定は、中間値にｆａｕｌｔ ｉｎｊｅｃｔｉｏｎしたと考えられるブロック単位で行い、秘密鍵ｄ全体が復元できるまで、処理が繰り返される。
【００６０】
以上、スカラ倍演算中に故障を生じさせる攻撃について説明した。
このような故障利用攻撃が攻撃者によって実行されたか否かは、スカラ倍演算の出力である、べき倍点の正当性を検証することで検証することができ、検証結果に基づいて故障利用攻撃を防止することができる。なお、以上の説明では、標数ｐ＞３の有限体上で定義された楕円曲線ＥＡを例にとって説明を行ったが、標数２の有限体上で定義された楕円曲線ＥＢについても、同様な故障利用攻撃が攻撃者により行われる可能性がある。
【００６１】
以下で説明する本発明の実施形態に係る情報処理装置および演算検証方法では、上述のような故障利用攻撃の有無を、楕円曲線の種類にかかわらず容易に検証することが可能な方法である。以下に、本発明の実施形態に係る情報処理装置および演算検証方法について、詳細に説明する。
【００６２】
（第１の実施形態）
＜情報処理装置の構成について＞
続いて、本発明の第１の実施形態に係る情報処理装置について、詳細に説明する。図１は、本実施形態に係る情報処理装置の構成を説明するためのブロック図である。
【００６３】
本実施形態に係る情報処理装置１０は、例えば図１に示したように、暗号化処理部１０１と、復号処理部１０３と、楕円曲線演算部１０５と、記憶部１０７と、を主に備える。
【００６４】
暗号化処理部１０１は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、通信装置等により実現される。暗号化処理部１０１は、所定の有限体上で定義された楕円曲線Ｅを利用した暗合方式に基づいて、暗号化したい平文を暗号化し、暗号文とする。
【００６５】
より詳細には、暗号化処理部１０１は、平文を暗号文へと暗号化する暗号化処理に際して、楕円曲線演算部１０５に対して、楕円曲線Ｅを利用した楕円曲線演算処理を要請する。この楕円曲線演算の例として、楕円曲線Ｅ上の点の加法や、楕円曲線Ｅ上の点をスカラ倍するスカラ倍演算がある。
【００６６】
暗号化処理部１０１は、楕円曲線演算部１０５に楕円曲線演算を要請する際には、楕円曲線演算を実行する際に必要となる楕円曲線上の点や、演算に必要となる各種のパラメータ（例えば、スカラ倍演算における係数）などを、演算パラメータとして伝送する。また、暗号化処理部１０１は、楕円曲線演算部１０５から楕円曲線を利用した演算結果が伝送されると、演算結果を利用して、暗号化処理を継続する。
【００６７】
暗号化処理部１０１は、暗号化処理が終了すると、生成された暗号文を所定の装置へと送信する。
【００６８】
復号処理部１０３は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ、通信装置等により実現される。復号処理部１０３は、所定の有限体上で定義された楕円曲線Ｅを利用した暗合方式に基づいて、暗号文に対して復号処理を行い、平文にする。
【００６９】
より詳細には、復号処理部１０３は、暗号文を平文へと復号する復号処理に際して、楕円曲線演算部１０５に対して、楕円曲線Ｅを利用した楕円曲線演算処理を要請する。この楕円曲線演算の例として、楕円曲線Ｅ上の点の加法や、楕円曲線Ｅ上の点をスカラ倍するスカラ倍演算がある。
【００７０】
復号処理部１０３は、楕円曲線演算部１０５に楕円曲線演算を要請する際には、楕円曲線演算を実行する際に必要となる楕円曲線上の点や、演算に必要となる各種のパラメータ（例えば、スカラ倍演算における係数）などを、演算パラメータとして伝送する。また、復号処理部１０３は、楕円曲線演算部１０５から楕円曲線を利用した演算結果が伝送されると、演算結果を利用して、復号処理を継続する。
【００７１】
復号処理部１０３は、復号処理が終了すると、生成された平文を、情報処理装置１０に設けられたディスプレイ等の表示装置に表示する。
【００７２】
楕円曲線演算部１０５は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。楕円曲線演算部１０５は、所定の有限体上で定義された楕円曲線Ｅと、暗号化処理部１０１または復号処理部１０３から伝送された演算パラメータとに基づいて、楕円曲線を利用した演算処理を行う。この楕円曲線演算部１０５は、楕円曲線演算制御部１１１と、加法演算部１０３と、スカラ倍演算部１１５と、演算検証部１１７と、演算結果出力部１１９と、を更に備える。
【００７３】
楕円曲線演算制御部１１１は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。楕円曲線演算制御部１１１は、暗号化処理部１０１および復号処理部１０３から伝送された演算パラメータに基づいて、暗号化処理部１０１および復号処理部１０３から要請された楕円曲線演算の実行制御を行う。
【００７４】
より詳細には、楕円曲線演算制御部１１１は、暗号化処理部１０１および復号処理部１０３から伝送された演算パラメータを参照して、これらの処理部から要請された楕円曲線演算の種類を判別する。楕円曲線演算制御部１１１は、暗号化処理部１０１および復号処理部１０３から要請された楕円曲線演算の種類を特定すると、特定した楕円曲線演算の種類に応じて、後述する加法演算部１１３およびスカラ倍演算部１１５に、取得した演算パラメータを伝送する。また、楕円曲線演算制御部１１１は、特定した楕円曲線演算の種類を、後述する演算検証部１１７に伝送する。
【００７５】
加法演算部１１３は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。加法演算部１１３は、楕円曲線演算制御部１１１から伝送された演算パラメータに含まれる楕円曲線Ｅ上の点に関する情報に基づいて、被演算点である楕円曲線上の点の加法演算を行う。具体的には、加法演算部１１３は、演算に用いる楕円曲線Ｅの種類に応じて、上記式１１〜式１３または式１５〜式２０を用いて、被演算点の加法演算を行う。なお、加法演算部１１３は、加法演算処理に際して、記憶部１０７等に格納されている楕円曲線パラメータや、公開鍵、秘密鍵等を参照してもよい。
【００７６】
加法演算部１１３は、被演算点に関する加法演算の演算結果が得られると、加法演算処理が終了した旨を、楕円曲線演算制御部１１１に伝送する。また、加法演算部１１３は、被演算点に関する加法演算の演算結果（すなわち、加法演算の結果得られる楕円曲線Ｅ上の点に関する情報）を、後述する演算検証部１１７に伝送する。なお、加法演算部１１３は、演算結果を後述するスカラ倍演算部１１５に伝送し、演算結果を、スカラ倍演算部１１５におけるスカラ倍演算処理に用いても良い。
【００７７】
スカラ倍演算部１１５は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。スカラ倍演算部１１５は、楕円曲線演算制御部１１１から伝送された演算パラメータに含まれる楕円曲線Ｅ上の被演算点に関する情報と、スカラ倍演算の係数に関する情報と、に基づいて、被演算点に関するスカラ倍演算を実行する。すなわち、スカラ倍演算部１１５は、被演算点をＰ、スカラ倍演算の係数をｓ、スカラ倍演算結果（以下、べき倍点とも称する。）をＱとすると、Ｑ＝ｓ・Ｐを演算する処理部である。
【００７８】
スカラ倍演算部１１５は、被演算点に関するスカラ倍演算を、例えば図４に示したＤｏｕｂｌｅ ａｎｄ Ａｄｄ Ｍｅｔｈｏｄのような計算アルゴリズムを実行することで行う。また、スカラ倍演算部１１５が実行する計算アルゴリズムは、上記の例に限定されるわけではなく、他の任意の計算アルゴリズムを利用することが可能である。
【００７９】
なお、スカラ倍演算部１１５は、スカラ倍演算処理に際して、記憶部１０７等に格納されている楕円曲線パラメータや、公開鍵、秘密鍵等を参照してもよい。例えば、スカラ倍演算部１１５は、スカラ倍演算の係数ｓとして、自装置で秘匿している秘密鍵や、自装置で管理されている公開鍵を利用することができる。
【００８０】
スカラ倍演算部１１５は、被演算点に関するスカラ倍演算の演算結果が得られると、スカラ倍演算処理が終了した旨を、楕円曲線演算制御部１１１に伝送する。また、スカラ倍演算部１１５は、被演算点に関するスカラ倍演算の演算結果（すなわち、スカラ倍演算の結果得られる楕円曲線Ｅ上の点に関する情報）を、後述する演算検証部１１７に伝送する。なお、スカラ倍演算部１１５は、演算結果を加法演算部１１３に伝送し、演算結果を、加法演算部１１３における加法演算処理に用いても良い。
【００８１】
演算検証部１１７は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。演算検証部１１７は、スカラ倍演算部１１５がスカラ倍演算を実行した場合に、スカラ倍演算部１１５により実行されたスカラ倍演算処理の検証を行う。より詳細には、演算検証部１１７は、スカラ倍演算における被演算点Ｐと、スカラ倍演算の結果得られる楕円曲線Ｅ上の点（べき倍点）Ｑと、楕円曲線パラメータであるベースポイントＧと、に基づいて、以下の式１０１の等号が成立するか否かを検証する。
【００８２】
（Ｐ＋Ｑ）＋Ｒ＝Ｐ＋（Ｑ＋Ｒ） ・・・（式１０１）
【００８３】
具体的には、演算検証部１１７は、上記式１０１の左辺に示した加法演算処理と、上記式１０１の右辺に示した加法演算処理と、を、加法演算部１１３に要請する。演算検証部１１７は、加法演算部１１３から伝送された左辺の演算結果と、右辺の演算結果とが同一の値であるか（すなわち、楕円曲線Ｅ上の同一の点であるか否か）を判定することで、上記式１０１の等号が成立したか否かを検証する。
【００８４】
演算検証部１１７は、上記式１０１における等号が成立するか否かを検証することで、被演算点Ｐに対する検証と、スカラ倍演算結果であるべき倍点Ｑに対する検証の双方を行っている。
【００８５】
まず、べき倍点Ｑに関する検証について、より詳細に説明する。
スカラ倍演算部１１５がべき倍点Ｑの演算を実行している途中に故障攻撃を受け、スカラ倍の演算結果が不正な点Ｑ’に変更されたとすると、演算の結果得られるべき倍点Ｑ’は、正しい楕円曲線Ｅとは異なる楕円曲線Ｅ’上の点となる。すなわち、Ｑ∈Ｅ’（Ｆｑ）である。上記式１０１として表される群の結合法則は、同一楕円曲線上の３点Ｐ，Ｑ，Ｇ∈Ｅ（Ｆｑ）に対して成立する。そのため、演算検証部１１７は、式１０１における等号が成立した場合には、被演算点Ｐ、べき倍点ＱおよびベースポイントＧが、同一の楕円曲線Ｅ上の点であることが確認できる。逆に、式１０１における等号が成立しなかった場合には、べき倍点Ｑは、加法群Ｅ（Ｆｑ）とは異なる群に属している（すなわち、被演算点ＰおよびベースポイントＧとは異なる楕円曲線上の点である）ことを示している。そのため、演算検証部１１７は、スカラ倍演算中に、攻撃者から故障攻撃を受けたことを検出することができる。
【００８６】
次に、被演算点Ｐに関する検証について、より詳細に説明する。
スカラ倍演算部１１５がスカラ倍演算を実行する前に被演算点がＰ’∈Ｅ’（Ｆｑ）に修正された場合、得られるスカラ倍演算の演算結果は、Ｑ’∈Ｅ’（Ｆｑ）となり、ベースポイントＧ∈Ｅ（Ｆｑ）とは異なる群に属することとなる。そのため、攻撃者による攻撃や、情報処理装置１０の故障等により被演算点Ｐに変更が生じた場合には、演算検証部１１７は、被演算点Ｐが適式な値ではなかったことを検出することができる。
【００８７】
なお、上述のような検証では、被演算点Ｐまたはべき倍点Ｑのどちらが適式ではなかったのかは、明らかにすることができない。そのため、以下のような処理を行うことで、演算検証部１１７は、被演算点Ｐまたはべき倍点Ｑのどちらが不適だったのかを明確にすることができる。
【００８８】
例えば、被演算点Ｐのみを検証したい場合には、演算検証部１１７は、べき倍点Ｑの代わりに、自装置が管理している公開鍵、または、信頼できる他の情報処理装置の公開鍵を利用し、上記式１０１が成立するか否かを検証する。これらの公開鍵は、被演算点Ｐが存在している楕円曲線と同一の楕円曲線を用いて算出されたものであるため、被演算点Ｐと同一の群に属するものである。そのため、べき倍点Ｑの代わりにこれらの公開鍵を利用することで、被演算点Ｐのみの検証を行うことができる。なお、信頼できる他の情報処理装置の例として、公開鍵および秘密鍵からなる鍵ペアを生成する鍵生成センタが保持する情報処理装置や、第三者認証機関が保持する情報処理装置等を挙げることができる。
【００８９】
また、べき倍点Ｑのみを検証したい場合、演算検証部１１７は、被演算点Ｐのみの検証と同様に、被演算点Ｐの代わりに、自装置が管理している公開鍵、または、信頼できる他の情報処理装置の公開鍵を利用し、上記式１０１が成立するか否かを検証すればよい。
【００９０】
なお、スカラ倍演算部１１５は、ベースポイントＧのスカラ倍演算など、被演算点Ｐの指定を受けずにスカラ倍演算を実行する場合もある。この際、演算検証部１１７は、被演算点Ｐの代わりに、自装置が管理している公開鍵、または、信頼できる他の情報処理装置の公開鍵を利用し、上記式１０１が成立するか否かを検証すればよい。
【００９１】
以上説明したように、演算検証部１１７は、式１０１における等号が成立しなかった場合、被演算点Ｐが適式な値ではなかった、または、べき倍点Ｑに改ざんが加えられたと判断することができる。この演算結果の検証は、加法演算部１１５による４回の加法演算の結果に基づき、１回の楕円曲線上の点の比較を行うことで実施できる。そのため、本実施形態に係る情報処理装置では、楕円曲線上の群の性質を利用することで、より簡便な方法で故障利用攻撃の有無を判定することができる。
【００９２】
演算検証部１１７は、スカラ倍演算に関する検証結果が得られると、得られた検証結果を、後述する演算結果出力部１１９に伝送する。より詳細には、演算検証部１１７は、加法演算部１１３が実行した加法演算結果が伝送されると、伝送された加法演算結果を演算結果出力部１１９に伝送する。また、演算検証部１１７は、スカラ倍演算部１１５からスカラ倍演算結果が伝送されると、式１０１を用いた検証を行い、検証が成功した場合に、スカラ倍演算の演算結果とともに、得られた検証結果を、演算結果出力部１１９に伝送する。また、演算検証部１１７は、スカラ倍演算の検証が失敗した場合には、検証に失敗した旨のみを演算結果出力部１１９に伝送する。
【００９３】
演算結果出力部１１９は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。演算結果出力部１１９は、演算検証部１１７から伝送された演算結果および検証結果を、楕円曲線演算部１０５に楕円曲線演算処理を要請した処理部に対して出力する。
【００９４】
記憶部１０７は、情報処理装置１０が管理する秘密鍵および公開鍵と、楕円曲線パラメータとを格納する。また、記憶部１０７は、情報処理装置１０が、何らかの処理を行う際に保存する必要が生じた様々なパラメータや処理の途中経過等、または、各種のデータベース等を、適宜記憶することが可能である。この記憶部１０７は、本実施形態に係る情報処理装置１０が備える各処理部が、自由に読み書きを行うことが可能である。
【００９５】
以上説明したように、本実施形態に係る情報処理装置１０では、暗号処理中に故障攻撃を受けて中間値が変更された可能性がある場合に、スカラ倍演算の演算結果の正当性を、楕円曲線の種類を問わず容易に検証することができる。
【００９６】
以上、本実施形態に係る情報処理装置１０の機能の一例を示した。上記の各構成要素は、汎用的な部材や回路を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。また、各構成要素の機能を、ＣＰＵ等が全て行ってもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用する構成を変更することが可能である。
【００９７】
なお、上述のような本実施形態に係る情報処理装置の各機能を実現するためのコンピュータプログラムを作製し、パーソナルコンピュータ等に実装することが可能である。また、このようなコンピュータプログラムが格納された、コンピュータで読み取り可能な記録媒体も提供することができる。記録媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、フラッシュメモリなどである。また、上記のコンピュータプログラムは、記録媒体を用いずに、例えばネットワークを介して配信してもよい。
【００９８】
＜演算検証方法について＞
続いて、図２を参照しながら、本実施形態に係る演算検証方法について、詳細に説明する。図２は、本実施形態に係る演算検証方法について説明するための流れ図である。
【００９９】
情報処理装置１０の暗号化処理部１０１または復号処理部１０３は、それぞれの処理部が行う処理に際して、楕円曲線上の点のスカラ倍演算が必要となった際に、楕円曲線演算部１０５に対して、スカラ倍演算の実行を要請する。この際、暗号化処理部１０１および復号処理部１０３は、楕円曲線演算部１０５に対して、被演算点Ｐに関する情報およびスカラ倍演算の係数ｓに関する情報を含む演算パラメータを伝送する。
【０１００】
楕円曲線演算部１０５の楕円曲線演算制御部１１１は、暗号化処理部１０１または復号処理部１０３から伝送された演算パラメータを取得し（ステップＳ１０１）、要請のあった楕円曲線演算における被演算点Ｐと、スカラ倍演算の係数ｓと、を把握する。続いて、楕円曲線演算制御部１１１は、取得した被演算点Ｐおよびスカラ倍演算の係数ｓを、スカラ倍演算部１１５に伝送する。
【０１０１】
スカラ倍演算部１１５は、楕円曲線演算制御部１１１から伝送された演算パラメータに基づいて、スカラ倍演算Ｑ＝ｓ・Ｐを実行する（ステップＳ１０３）。スカラ倍演算部１１５は、スカラ倍演算処理が終了すると、スカラ倍演算処理が終了した旨を楕円曲線演算制御部１１１に通知するとともに、演算結果であるべき倍点Ｑに関する情報を、演算検証部１１７に伝送する。
【０１０２】
演算検証部１１７は、スカラ倍演算部１１５から演算結果が伝送されると、加法演算部１１３に、以下の２種類の加法演算の実行を要請する。
【０１０３】
Ｓ１＝（Ｐ＋Ｑ）＋Ｒ ・・・（式１０２）
Ｓ２＝Ｐ＋（Ｑ＋Ｒ） ・・・（式１０３）
【０１０４】
加法演算部１１３は、演算検証部１１７から上記Ｓ１およびＳ２で表される２種類の加法演算を要請されると、上記式１０２および式１０３に基づいて加法演算を実行し（ステップＳ１０５）、演算結果を演算検証部１１７に伝送する。
【０１０５】
演算検証部１１７は、加法演算部１１３から伝送された値Ｓ１およびＳ２に基づいて、Ｓ１＝Ｓ２が成立するか（すなわち、上記式１０１の等号が成立するか否か）を検証する（ステップＳ１０７）。
【０１０６】
演算検証部１１７は、Ｓ１＝Ｓ２が成立した場合には、べき倍点Ｑが適式に演算されたと判断し、スカラ倍演算の演算結果と検証結果とを、演算結果出力部１１９に伝送する。その後、演算結果および検証結果を取得した演算結果出力部１１９は、楕円曲線演算の実行を要請した処理部に対して、演算結果Ｑを出力する（ステップＳ１０９）。
【０１０７】
他方、Ｓ１＝Ｓ２が成立しなかった場合には、演算検証部１１７は、べき倍点Ｑが適式に演算されなかったと判断し、この判断結果を演算結果出力部１１９に伝送する。その後、検証結果を取得した演算結果出力部１１９は、楕円曲線演算の実行を要請した処理部に対して、べき倍点Ｑが適式に演算されなかった旨を表すエラーを出力する（ステップＳ１１１）。
【０１０８】
以上説明したように、本実施形態に係る演算検証方法は、式１０１の左辺における２回の加法演算と、式１０１の右辺における２回の加法演算と、１回の点の比較演算のみで、演算結果の検証を行うことができる。このため、本実施形態に係る演算検証方法では、ある値のべき乗を計算する等といった複雑な演算処理を行うことなく、スカラ倍演算の演算結果の正当性を、楕円曲線の種類を問わず容易に検証することができる。
【０１０９】
また、本実施形態に係る演算検証方法では、有限体における比較処理が不要であり、楕円曲線上の加算／比較処理をそのまま利用できる。そのため、本実施形態に係る演算検証方法をハードウェア的に実現する場合には、演算検証方法を実現するための回路規模を小さくすることが可能となる。また、本実施形態に係る演算検証方法では、被演算点Ｐおよびべき倍点Ｑの双方をあわせて検証することができるため、入力値および出力値の検証ステップを、従来の手法よりも簡略化することができる。その結果、本実施形態に係る演算検証方法をソフトウェア的に実現する場合に、計算コストを削減することができる。
【０１１０】
（ハードウェア構成について）
次に、図３を参照しながら、本発明の実施形態に係る情報処理装置１０のハードウェア構成について、詳細に説明する。図３は、本発明の実施形態に係る情報処理装置１０のハードウェア構成を説明するためのブロック図である。
【０１１１】
情報処理装置１０は、主に、ＣＰＵ９０１と、ＲＯＭ９０３と、ＲＡＭ９０５と、を備える。また、情報処理装置１０は、更に、ホストバス９０７と、ブリッジ９０９と、外部バス９１１と、インターフェース９１３と、入力装置９１５と、出力装置９１７と、ストレージ装置９１９と、ドライブ９２１と、接続ポート９２３と、通信装置９２５とを備える。
【０１１２】
ＣＰＵ９０１は、演算処理装置および制御装置として機能し、ＲＯＭ９０３、ＲＡＭ９０５、ストレージ装置９１９、またはリムーバブル記録媒体９２７に記録された各種プログラムに従って、情報処理装置１０内の動作全般またはその一部を制御する。ＲＯＭ９０３は、ＣＰＵ９０１が使用するプログラムや演算パラメータ等を記憶する。ＲＡＭ９０５は、ＣＰＵ９０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を一次記憶する。これらはＣＰＵバス等の内部バスにより構成されるホストバス９０７により相互に接続されている。
【０１１３】
ホストバス９０７は、ブリッジ９０９を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス９１１に接続されている。
【０１１４】
入力装置９１５は、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチおよびレバーなどユーザが操作する操作手段である。また、入力装置９１５は、例えば、赤外線やその他の電波を利用したリモートコントロール手段（いわゆる、リモコン）であってもよいし、情報処理装置１０の操作に対応した携帯電話やＰＤＡ等の外部接続機器９２９であってもよい。さらに、入力装置９１５は、例えば、上記の操作手段を用いてユーザにより入力された情報に基づいて入力信号を生成し、ＣＰＵ９０１に出力する入力制御回路などから構成されている。情報処理装置１０のユーザは、この入力装置９１５を操作することにより、情報処理装置１０に対して各種のデータを入力したり処理動作を指示したりすることができる。
【０１１５】
出力装置９１７は、取得した情報をユーザに対して視覚的または聴覚的に通知することが可能な装置で構成される。このような装置として、ＣＲＴディスプレイ装置、液晶ディスプレイ装置、プラズマディスプレイ装置、ＥＬディスプレイ装置およびランプなどの表示装置や、スピーカおよびヘッドホンなどの音声出力装置や、プリンタ装置、携帯電話、ファクシミリなどがある。出力装置９１７は、例えば、情報処理装置１０が行った各種処理により得られた結果を出力する。具体的には、表示装置は、情報処理装置１０が行った各種処理により得られた結果を、テキストまたはイメージで表示する。他方、音声出力装置は、再生された音声データや音響データ等からなるオーディオ信号をアナログ信号に変換して出力する。
【０１１６】
ストレージ装置９１９は、情報処理装置１０の記憶部の一例として構成されたデータ格納用の装置である。ストレージ装置９１９は、例えば、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等の磁気記憶部デバイス、半導体記憶デバイス、光記憶デバイス、または光磁気記憶デバイス等により構成される。このストレージ装置９１９は、ＣＰＵ９０１が実行するプログラムや各種データ、および外部から取得した音響信号データや画像信号データなどを格納する。
【０１１７】
ドライブ９２１は、記録媒体用リーダライタであり、情報処理装置１０に内蔵、あるいは外付けされる。ドライブ９２１は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体９２７に記録されている情報を読み出して、ＲＡＭ９０５に出力する。また、ドライブ９２１は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体９２７に記録を書き込むことも可能である。リムーバブル記録媒体９２７は、例えば、ＤＶＤメディア、ＨＤ−ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア等である。また、リムーバブル記録媒体９２７は、コンパクトフラッシュ（登録商標）（ＣｏｍｐａｃｔＦｌａｓｈ：ＣＦ）、メモリースティック、または、ＳＤメモリカード（Ｓｅｃｕｒｅ Ｄｉｇｉｔａｌ ｍｅｍｏｒｙ ｃａｒｄ）等であってもよい。また、リムーバブル記録媒体９２７は、例えば、非接触型ＩＣチップを搭載したＩＣカード（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ ｃａｒｄ）または電子機器等であってもよい。
【０１１８】
接続ポート９２３は、機器を情報処理装置１０に直接接続するためのポートである。接続ポート９２３の一例として、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）ポート、ｉ．Ｌｉｎｋ等のＩＥＥＥ１３９４ポート、ＳＣＳＩ（Ｓｍａｌｌ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍ Ｉｎｔｅｒｆａｃｅ）ポート等がある。接続ポート９２３の別の例として、ＲＳ−２３２Ｃポート、光オーディオ端子、ＨＤＭＩ（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ Ｍｕｌｔｉｍｅｄｉａ Ｉｎｔｅｒｆａｃｅ）ポート等がある。この接続ポート９２３に外部接続機器９２９を接続することで、情報処理装置１０は、外部接続機器９２９から直接各種のデータを取得したり、外部接続機器９２９に各種のデータを提供したりする。
【０１１９】
通信装置９２５は、例えば、通信網９３１に接続するための通信デバイス等で構成された通信インターフェースである。通信装置９２５は、例えば、有線または無線ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、Ｂｌｕｅｔｏｏｔｈ、またはＷＵＳＢ（Ｗｉｒｅｌｅｓｓ ＵＳＢ）用の通信カード等である。また、通信装置９２５は、光通信用のルータ、ＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ Ｄｉｇｉｔａｌ Ｓｕｂｓｃｒｉｂｅｒ Ｌｉｎｅ）用のルータ、または、各種通信用のモデム等であってもよい。この通信装置９２５は、例えば、インターネットや他の通信機器との間で、例えばＴＣＰ／ＩＰ等の所定のプロトコルに則して信号等を送受信することができる。また、通信装置９２５に接続される通信網９３１は、有線または無線によって接続されたネットワーク等により構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、ラジオ波通信または衛星通信等であってもよい。
【０１２０】
以上、本発明の実施形態に係る情報処理装置１０の機能を実現可能なハードウェア構成の一例を示した。上記の各構成要素は、汎用的な部材を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用するハードウェア構成を変更することが可能である。
【０１２１】
＜まとめ＞
以上説明したように、本発明の実施形態に係る情報処理装置および演算検証方法では、スカラ倍演算における被演算点Ｐと、スカラ倍演算の演算結果であるべき倍点Ｑと、楕円曲線のベースポイントＥとを利用して、簡便にスカラ倍演算の検証を行うことができる。
【０１２２】
より詳細には、本発明の実施形態に係る情報処理装置および演算検証方法では、４回の加法演算と、１回の点の比較演算のみで、演算結果の検証を行うことができる。このため、本発明の実施形態に係る情報処理装置および演算検証方法では、ある値のべき乗を計算する等といった複雑な演算処理を行うことなく、スカラ倍演算の演算結果の正当性を、楕円曲線の種類を問わず容易に検証することができる。
【０１２３】
また、本発明の実施形態に係る情報処理装置および演算検証方法では、有限体における比較処理が不要であり、楕円曲線上の加算／比較処理をそのまま利用できる。そのため、本発明の実施形態に係る演算検証方法をハードウェア的に実現する場合には、演算検証方法を実現するための回路規模を小さくすることが可能となる。また、本発明の実施形態に係る情報処理装置および演算検証方法をソフトウェア的に実現する場合には、計算コストを削減することができる。
【０１２４】
以上、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明はかかる例に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０１２５】
１０ 情報処理装置
１０１ 暗号化処理部
１０３ 復号処理部
１０５ 楕円曲線演算部
１０７ 記憶部
１１１ 楕円曲線演算制御部
１１３ 加法演算部
１１５ スカラ倍演算部
１１７ 演算検証部
１１９ 演算結果出力部
【技術分野】
【０００１】
本発明は、情報処理装置、演算検証方法およびプログラムに関する。
【背景技術】
【０００２】
楕円曲線暗号は、楕円曲線上における離散対数問題の困難性を利用した暗号方式であり、同じ安全性水準の下で、ＲＳＡ暗号に比べて短い鍵長で済むといった特徴を持つ。この楕円曲線暗号は、ＥＣＤＳＡ（Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｔｏｒｉｔｈｍ）署名による機器間認証など、様々な場面で利用されている暗号方式である。
【０００３】
楕円曲線暗号を用いて生成された秘密鍵を悪意のある第三者が不正に取得するための方法として、故障利用攻撃と呼ばれるものがある。この故障利用攻撃は、不正なシステムパラメータを与えたり、暗号処理中に故意に外部から故障（中間値を保持するレジスタの破壊等）を起こさせたりすることにより、悪意のある第三者が不正な計算結果を入手し、秘
密鍵を推定するという攻撃である。上述のような故障利用攻撃は、１９９７年にＢｏｎｅｈらによってＲＳＡ暗号に対する差分故障攻撃（Ｄｉｆｆｅｒｅｎｔｉａｌ ＦａｕｌｔＡｎａｌｙｓｉｓ ａｔｔａｃｋ：ＤＦＡ）として初めて提案され、２０００年にＢｉｅｈｌらによって、楕円曲線暗号へと拡張された。
【０００４】
ＤＦＡのような故障利用攻撃に対する対策としては、計算結果を出力する前に計算結果の正当性を検証し、不正な値であれば計算結果を出力しない、という方法をとる。シンプルな対策手法として、例えば、２度計算による検算がある。この方法は、同じ暗号処理を２度実施し、演算結果が同じでなければ演算結果を出力しない、という方法である。この方法は、全く同じ故障を連続して２度行うことは困難であることを想定している検証方法である。しかしながら、同じ演算を繰り返すため計算コストは対策なしの場合に比べ２倍になり、また、計算効率も好ましいものではないため、より効率的な故障検知方法が希求されている。
【０００５】
また、故障検知方法の別の例として、例えば以下に示す特許文献１では、演算により得られた点（Ｘ，Ｙ）に関し、楕円曲線を表す式の右辺および左辺を個別に計算し、左辺＝右辺が成立するか否かで故障利用攻撃の有無を判断する方法が記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２５２４３３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記特許文献１に記載の方法では、楕円曲線を表す式の右辺および左辺に該当する値をそれぞれ計算する機能と、得られた２種類の値を比較する機能と、を別途設ける必要がある。そのため、上記特許文献１に記載の方法をハードウェア実装する場合には、特別な処理部が必要となって回路規模が増加するという問題があり、上記特許文献１に記載の方法をソフトウェア的に処理する場合には、計算コストの増加が生じるという問題があった。
【０００８】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、より簡便な方法で故障利用攻撃の有無を判定することが可能な、情報処理装置、演算検証方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明のある観点によれば、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算部と、前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証部と、を備える情報処理装置が提供される。
【００１０】
（Ｐ＋Ｑ）＋Ｇ＝Ｐ＋（Ｑ＋Ｇ） ・・・（式１）
【００１１】
かかる構成によれば、スカラ倍演算部は、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算する。また、演算検証部は、楕円曲線Ｅ上の点Ｐと、スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、楕円曲線Ｅ上の任意の点Ｇと、を用いて、上記式１における等号が成立するか否かを検証する。
【００１２】
前記楕円曲線Ｅは、有限体Ｆｑ（ｑ＝ｐｍ，ｍ∈Ｎ，ｐ＞３）上で定義された楕円曲線ＥＡ：ｙ２＝ｘ３＋ａｘ＋ｂ（ａ，ｂ∈Ｆｑ）、または、標数２の有限体Ｆ２＾ｍ（ｍ∈Ｎ）上で定義された楕円曲線ＥＢ：ｙ２＋ｘｙ＝ｘ３＋ａ２ｘ２＋ａ６（ａ２，ａ６∈Ｆ２＾ｍ）であることが好ましい。
【００１３】
前記演算検証部は、前記式１における等号が成立しなかった場合、前記点Ｐが適式な値ではなかった、または、点Ｑに改ざんが加えられたと判断する。
【００１４】
前記情報処理装置は、自装置が秘匿すべき情報である秘匿情報を格納する記憶部を更に備え、前記楕円曲線Ｅ上の任意の点Ｇは、前記秘匿情報の一つとして前記記憶部に格納されることが好ましい。
【００１５】
前記記憶部には、自装置が保持する秘密鍵ｄが格納されており、前記スカラ倍演算部は、スカラ倍演算の係数ｓとして前記秘密鍵ｄを用いてもよい。
【００１６】
前記演算検証部は、前記点Ｐまたは前記点Ｑの代わりに、自装置が保持している公開鍵または信頼できる他の情報処理装置が保持している公開鍵を用いて、前記式１における等号が成立するか否かを検証してもよい。
【００１７】
また、上記課題を解決するために、本発明の別の観点によれば、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するステップと、前記楕円曲線Ｅ上の点Ｐと、算出された点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証するステップとを含む演算検証方法が提供される。
【００１８】
また、上記課題を解決するために、本発明の更に別の観点によれば、コンピュータに、所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算機能と、前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算機能により算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証機能と、を実現させるためのプログラムが提供される。
【発明の効果】
【００１９】
以上説明したように本発明によれば、楕円曲線上の群の性質を利用することで、より簡便な方法で故障利用攻撃の有無を判定することが可能である。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施形態に係る情報処理装置の構成を説明するための説明図である。
【図２】同実施形態に係る演算検証方法を説明するための流れ図である。
【図３】本発明の実施形態に係る情報処理装置のハードウェア構成を説明するための説明図である。
【図４】スカラ倍演算のアルゴリズムの一例を説明するための説明図である。
【図５】小さい位数を使った攻撃について説明するための流れ図である。
【図６Ａ】スカラ倍演算中に故障を生じさせる攻撃について説明するための流れ図である。
【図６Ｂ】スカラ倍演算中に故障を生じさせる攻撃について説明するための流れ図である。
【発明を実施するための形態】
【００２１】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２２】
なお、説明は、以下の順序で行うものとする。
（１）楕円曲線について
（２）故障利用攻撃について
（３）第１の実施形態
（３−１）情報処理装置の構成について
（３−２）演算検証方法について
（４）本発明の実施形態に係る情報処理装置のハードウェア構成について
（５）まとめ
【００２３】
（楕円曲線について）
まず、本発明の実施形態に係る情報処理装置および演算検証方法について説明するに先立ち、本発明の実施形態で利用する楕円曲線について、詳細に説明する。
【００２４】
本発明の実施形態に係る情報処理装置および演算検証方法では、楕円曲線Ｅとして、以下の２つの楕円曲線を扱う。
【００２５】
（ｉ）有限体Ｆｑ（ｑ＝ｐｍ，ｍ∈Ｎ，ｐ＞３）上で定義された楕円曲線ＥＡ：ｙ２＝ｘ３＋ａｘ＋ｂ（ａ，ｂ∈Ｆｑ）
（ｉｉ）標数２の有限体（バイナリフィールド）Ｆ２＾ｍ（ｍ∈Ｎ）上で定義された楕円曲線ＥＢ：ｙ２＋ｘｙ＝ｘ３＋ａ２ｘ２＋ａ６（ａ２，ａ６∈Ｆ２＾ｍ）
【００２６】
以下、標数ｐ＞３の有限体上で定義された楕円曲線ＥＡを例にとって説明するが、標数２の有限体上で定義された楕円曲線ＥＢに関しても同様のことが成立する。
【００２７】
楕円曲線ＥＡ上の点の集合を、Ｅ（Ｆｑ）＝｛（ｘ，ｙ）∈Ｆｑ×Ｆｑ｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪｛Ｏ｝で表現する。ここで、Ｏは無限遠点であり、後述する加法におけるＥ（Ｆｑ）の単位元である。
【００２８】
また、Ｅ（Ｆｑ）の濃度を楕円曲線の位数と呼び、＃Ｅ（Ｆｑ）＝ｈ・ｒで表現する。ここで、ｒは、素数とする。ｈはｃｏｆａｃｔｏｒと呼ばれる係数であるが、本明細書では、ｈ＝１とする。また、楕円曲線上のランダムに選んだ点をベースポイントＧとすると、楕円曲線の位数は素位数を仮定しているため、Ｇの位数はｒとなる。
【００２９】
ここで、楕円曲線を表す式中の係数と、定義体の位数ｐと、ベースポイントの位数ｒと、ベースポイントＧは、楕円曲線を特定するための楕円曲線パラメータとなる。
【００３０】
次に、楕円曲線上に存在する２つの点の加法演算について説明する。
楕円曲線ＥＡでは、楕円曲線上に存在する点Ｐ１＝（ｘ１，ｙ１）、Ｐ２＝（ｘ２，ｙ２）に対する加法演算を、次のように定義する。ここで、Ｐ３＝（ｘ３，ｙ３）＝Ｐ１＋Ｐ２である。
【００３１】
【数１】
・・・（式１１）
・・・（式１２）
・・・（式１３）
【００３２】
このとき、Ｅ（Ｆｑ）は、以下の４つの群の性質を満足することが知られている。
【００３３】
１．閉法則：Ｐ＋Ｑ∈Ｅ（Ｆｑ） ｆｏｒ ａｌｌ Ｐ，Ｑ∈Ｅ（Ｆｑ）
２．単位元の存在：Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐ ｆｏｒ ａｌｌ Ｐ∈Ｅ（Ｆｑ）
３．逆元の存在：Ｐ＋（−Ｐ）＝（−Ｐ）＋Ｐ＝Ｏ ｆｏｒ ａｌｌ Ｐ∈Ｅ（Ｆｑ）
４．結合則：（Ｐ＋Ｑ）＋Ｒ＝Ｐ＋（Ｑ＋Ｒ） ｆｏｒ ａｌｌ Ｐ，Ｑ，Ｒ∈Ｅ（Ｆｑ）
【００３４】
また、点Ｐをスカラ（ｓｃａｌａｒ）倍（ｓ倍）した点をｓＰと表し、次のように定義する。すなわち、下式から明らかなように、点ｓＰは、点Ｐに対して、点Ｐをｓ−１回加えた結果得られた点として定義される。
【００３５】
【数２】
・・・（式１４）
【００３６】
このようなスカラ倍演算を実行するための計算アルゴリズムとして、例えば図４に示したような、Ｄｏｕｂｌｅ ａｎｄ Ａｄｄ Ｍｅｔｈｏｄがある。
【００３７】
同様に、楕円曲線ＥＢでは、楕円曲線上に存在する点Ｐ１＝（ｘ１，ｙ１）、Ｐ２＝（ｘ２，ｙ２）に対する加法演算を、次のように定義する。ここで、Ｐ３＝（ｘ３，ｙ３）＝Ｐ１＋Ｐ２である。ここで、Ｐ１≠Ｐ２の場合には、加法演算は、以下の式１５〜１７のように定義され、Ｐ１＝Ｐ２の場合には、加法演算は、以下の式１８〜２０のように定義される。
【００３８】
【数３】
・・・（式１５）
・・・（式１６）
・・・（式１７）
【００３９】
【数４】
・・・（式１８）
・・・（式１９）
・・・（式２０）
【００４０】
ここで、値Ｐおよび値ｓＰを与えられて、これら２つの値からｓを求める問題を、楕円曲線上の離散対数問題（Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ｐｒｏｂｌｅｍ：ＥＣＤＬＰ）という。このＥＣＤＬＰは、Ｐの位数が十分に大きければ解くことが非常に困難であり、この困難性が楕円曲線暗号の安全性の根拠となっている。
【００４１】
（故障利用攻撃について）
次に、図５〜図６Ｂを参照しながら、代表的な２種類の故障利用攻撃について、詳細に説明する。図５は、小さい位数を使った攻撃について説明するための流れ図である。また、図６Ａおよび図６Ｂは、スカラ倍演算中に故障を生じさせる攻撃について説明するための流れ図である。
【００４２】
Ｂｉｅｈｌらは、入力Ｐを秘密情報ｄ倍したｄＰの計算を行うスカラ倍演算に対して、故障を起こすタイミングによって、以下に示すような２通りの攻撃手法が存在することを提案している。故障を起こすタイミングは、スカラ倍演算を行う前、および、スカラ倍演算中の２通りである。
【００４３】
まず、スカラ倍演算を行う前に故障を生じさせる攻撃について説明する。
このスカラ倍演算を行う前に故障を生じさせる攻撃は、小さな位数による攻撃（Ｓｍａｌｌ Ｏｒｄｅｒ Ｐｏｉｎｔ Ａｔｔａｃｋ）と呼ばれている。この小さな位数による攻撃について、図５を参照しながら詳細に説明する。なお、以下の説明では、楕円曲線Ｅが、標数ｐ＞３の有限体上で定義された楕円曲線Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂである場合について説明する。
【００４４】
攻撃者は、スカラ倍演算を行う装置に対して、被演算点Ｐ∈Ｅ（Ｆｑ）に関する情報を入力し（ステップＳ１１）、この被演算点Ｐが、正しい楕円曲線Ｅ（すなわち、ｙ２＝ｘ３＋ａｘ＋ｂ）上の点であるか否かを装置に判定させる（ステップＳ１３）。
【００４５】
攻撃者は、被演算点Ｐが正しい楕円曲線Ｅ上の点であることを判定した直後に故障を生じさせ、点Ｐのｘ成分またはｙ成分の１ｂｉｔを反転させる（故障攻撃）。攻撃の結果１ｂｉｔが反転した点をＰ１とすると、この点Ｐ１は、楕円曲線Ｅ１：ｙ２＝ｘ３＋ａｘ＋ｂ１となり、スカラ倍演算を行う装置によるスカラ倍ｄＰ１の計算（ステップＳ１５）は、楕円曲線Ｅ１上で行われることとなる。なお、式１１〜式１３から明らかなように、楕円曲線上の点の加算や２倍算の公式には、楕円曲線を定義する係数ｂは出現しない。そのため、点Ｐ１に対するスカラ倍演算ｄＰ１は、正しく計算されることがわかる。
【００４６】
出力ｄＰ１を取得した攻撃者は、出力ｄＰ１のｘ座標およびｙ座標から楕円曲線Ｅ１を求め、位数＃Ｅ１を計算する（ステップＳ１７）。その後、攻撃者は、位数＃Ｅ１が、ある程度小さい因数ｒ１を持つか否かを判定する（ステップＳ１９）。
【００４７】
点Ｐ１∈Ｅ１のｘ成分またはｙ成分の何れか一方は、故障を生じさせる前の正しい値であるため、攻撃者は、ｘ成分またはｙ成分を楕円曲線Ｅ１に代入して、Ｐ１を復元することができる（ステップＳ２１）。続いて、攻撃者は、Ｐ１，ｄＰ１それぞれを（＃Ｅ１／ｒ１）倍し（ステップＳ２３）、位数ｒ１の部分群Ｅ１（Ｆｑ）［ｒ１］に写像する。次に、攻撃者は、算出した（＃Ｅ１／ｒ１）Ｐ１および（＃Ｅ１／ｒ１）ｄＰ１を用いて離散対数問題を解き、ｄ ｍｏｄ ｒ１を取得する（ステップＳ２５）。
【００４８】
続いて、攻撃者は、ｒ１とは異なる、ある程度小さい素数ｒｉを位数に持つ別の楕円曲線Ｅｉに対して、上述の手順を繰り返し行い、秘密情報ｄに関する部分情報ｄ ｍｏｄ ｒｉを、ｒ＜Πｒｉとなるまで集める（ステップＳ２７）。最後に。攻撃者は、ｄ ｍｏｄ ｒｉに対して中国人の剰余定理（Ｃｈｉｎｅｓｅ ｒｅｍａｉｎｄｅｒ ｔｈｅｏｒｅｍ）を適用し、秘密情報ｄを導出する（ステップＳ２９）。以上説明したように、攻撃者は、上述の手順に則った故障利用攻撃を用いることで、秘密情報ｄを取得できる可能性がある。
【００４９】
以上、スカラ倍演算を行う前に故障を生じさせる攻撃について説明した。
続いて、スカラ倍演算中に故障を生じさせる攻撃について、図６Ａおよび図６Ｂを参照しながら、詳細に説明する。
【００５０】
ここで、スカラ倍演算を実行する装置は、図４に示したＲｉｇｈｔ−Ｔｏ−Ｌｅｆｔ Ａｌｇｏｒｉｔｈｍを用いてスカラ倍演算を実行するものとする。
【００５１】
まず、攻撃者は、スカラ倍演算を実行する装置に対して被演算点Ｐを入力し（ステップＳ２１）、スカラ倍演算を実行する装置にスカラ倍演算を実行させて（ステップＳ２３）、正しいスカラ倍点Ｑ＝ｄＰを取得する。
【００５２】
次に、攻撃者は、パラメータｉを、ｌｏｇ２ｄを超えない最大の整数に設定した上で、ｄ＝０とする（ステップＳ２５）。続いて、攻撃者は、パラメータｋを、推定したいビット数ｍに設定する（ステップＳ２７）。
【００５３】
次に、攻撃者は、取得した正しいスカラ倍点Ｑを保持したまま、スカラ倍演算を実行する装置に対して、再度Ｐを被演算点として入力する（ステップＳ２９）。
【００５４】
スカラ倍演算を実行する装置は、入力された被演算点Ｐに基づいてスカラ倍の演算を実行するが（ステップＳ３１）、攻撃者は、あるタイミングで、スカラ倍演算の中間値を保持するレジスタに対して、故障（１ｂｉｔ反転）を生じさせる。図６Ａに示した例では、攻撃者は、ｉ−ｍ≦ｊ＜ｉを満たすｊステップ目に故障攻撃を実行し、スカラ倍演算を実行する装置に不正な演算結果Ｑ’を生成させる。攻撃者は、スカラ倍演算を実行する装置から出力された演算結果Ｑ’を保持する（ステップＳ３３）。
【００５５】
攻撃者は、秘密鍵の既知のビットから故障を起こした位置までの秘密鍵の一部（部分鍵ｘ）を推定し（ステップＳ３５）、以下の式９０１に基づいて、Ｑから故障が発生したｉステップ目の中間値Ｑｘｉまで逆算する（ステップＳ３７）。この逆算は、２ｍパターン分実行される。
【００５６】
【数５】
・・・（式９０１）
【００５７】
次に、攻撃者は、Ｑｘｉ−ｋの１ｂｉｔを反転させｘ倍した値であるＱｘ＊を算出する（ステップＳ３９）。ここで、ｘは、推定した部分鍵である。攻撃者は、算出したＱｘ＊と不正な結果Ｑ’とを比較する（ステップＳ４１）。Ｑ’とＱｘ＊とが等しくない場合には、攻撃者は、パラメータｋをｋ−１と設定し（ステップＳ４３）、再びＱｘ＊を算出する（ステップＳ３９）。このように、攻撃者は、中間値Ｑｘｉのどの１ｂｉｔが故障により反転したのかが分からないため、考えられるすべての故障パターンに対して、推定した秘密鍵を利用して不正な演算結果Ｑ’の候補Ｑｘ＊を計算する。
【００５８】
他方、Ｑ’とＱｘ＊とが一致した場合には、部分鍵ｘの推定が正しかったことになり、攻撃者は、パラメータｄを、ｄをｘで割り切った値（ｄ｜ｘ）に設定することで、パラメータｄの更新を行う（ステップＳ４５）。続いて、攻撃者は、パラメータｉをｉ−ｋと設定し（ステップＳ４７）、パラメータｉが０になったか否かを判定する（ステップＳ４９）。パラメータｉが０ではない場合には、攻撃者は、ステップＳ２７に戻って、次のｍｂｉｔについて、ステップＳ２７から再び処理を行う。パラメータｉが０になった場合には、秘密鍵の全体が復元できたことを意味するため、推定した秘密鍵の全体ｄを出力する（ステップＳ５１）。
【００５９】
例えば、秘密鍵ｄの上位４ｂｉｔを推定したい場合を考える。この場合、攻撃者は、スカラ倍演算を実行する装置がそれらのビットでスカラ倍演算を実行しているときに、ｆａｕｌｔ ｉｎｊｅｃｔｉｏｎ（故障攻撃）を行う。ここで、ｄのビット長を１６０ｂｉｔとすれば、ｆａｕｌｔ ｉｎｊｅｃｔｉｏｎしたステップｉは、１５６≦ｉ＜１６０となる。攻撃者は、１５６ステップ目に故障が発生したものと仮定して、１５６ステップ目の中間値Ｑ１５６を復元する。攻撃者は、考えられるすべての部分鍵候補ｘ∈｛０，１｝４に対して、Ｑｘｉ＝Ｑ−ｘ・２１５６Ｐを計算する。攻撃者は、すべてのＱｘ１５６に対して１ｂｉｔ反転を行い、それらの値をｘ倍したＱｘ＊を計算する。このＱｘ＊が得られた不正な結果Ｑ’と一致すれば、推定した部分鍵ｘと、ｆａｕｌｔ ｉｎｊｅｃｔｉｏｎが生じたステップｉ＝１５６と、反転したｂｉｔの位置とが正しかったことになる。また、不正な結果Ｑ’と一致するＱｘ＊がなければ、攻撃者は、ｉ＝１５７として、ｉ＝１５６の場合と同様にすべてのＱｘ１５７の１ｂｉｔ反転させたものを求め、処理を進めていく。このように、鍵推定は、中間値にｆａｕｌｔ ｉｎｊｅｃｔｉｏｎしたと考えられるブロック単位で行い、秘密鍵ｄ全体が復元できるまで、処理が繰り返される。
【００６０】
以上、スカラ倍演算中に故障を生じさせる攻撃について説明した。
このような故障利用攻撃が攻撃者によって実行されたか否かは、スカラ倍演算の出力である、べき倍点の正当性を検証することで検証することができ、検証結果に基づいて故障利用攻撃を防止することができる。なお、以上の説明では、標数ｐ＞３の有限体上で定義された楕円曲線ＥＡを例にとって説明を行ったが、標数２の有限体上で定義された楕円曲線ＥＢについても、同様な故障利用攻撃が攻撃者により行われる可能性がある。
【００６１】
以下で説明する本発明の実施形態に係る情報処理装置および演算検証方法では、上述のような故障利用攻撃の有無を、楕円曲線の種類にかかわらず容易に検証することが可能な方法である。以下に、本発明の実施形態に係る情報処理装置および演算検証方法について、詳細に説明する。
【００６２】
（第１の実施形態）
＜情報処理装置の構成について＞
続いて、本発明の第１の実施形態に係る情報処理装置について、詳細に説明する。図１は、本実施形態に係る情報処理装置の構成を説明するためのブロック図である。
【００６３】
本実施形態に係る情報処理装置１０は、例えば図１に示したように、暗号化処理部１０１と、復号処理部１０３と、楕円曲線演算部１０５と、記憶部１０７と、を主に備える。
【００６４】
暗号化処理部１０１は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、通信装置等により実現される。暗号化処理部１０１は、所定の有限体上で定義された楕円曲線Ｅを利用した暗合方式に基づいて、暗号化したい平文を暗号化し、暗号文とする。
【００６５】
より詳細には、暗号化処理部１０１は、平文を暗号文へと暗号化する暗号化処理に際して、楕円曲線演算部１０５に対して、楕円曲線Ｅを利用した楕円曲線演算処理を要請する。この楕円曲線演算の例として、楕円曲線Ｅ上の点の加法や、楕円曲線Ｅ上の点をスカラ倍するスカラ倍演算がある。
【００６６】
暗号化処理部１０１は、楕円曲線演算部１０５に楕円曲線演算を要請する際には、楕円曲線演算を実行する際に必要となる楕円曲線上の点や、演算に必要となる各種のパラメータ（例えば、スカラ倍演算における係数）などを、演算パラメータとして伝送する。また、暗号化処理部１０１は、楕円曲線演算部１０５から楕円曲線を利用した演算結果が伝送されると、演算結果を利用して、暗号化処理を継続する。
【００６７】
暗号化処理部１０１は、暗号化処理が終了すると、生成された暗号文を所定の装置へと送信する。
【００６８】
復号処理部１０３は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ、通信装置等により実現される。復号処理部１０３は、所定の有限体上で定義された楕円曲線Ｅを利用した暗合方式に基づいて、暗号文に対して復号処理を行い、平文にする。
【００６９】
より詳細には、復号処理部１０３は、暗号文を平文へと復号する復号処理に際して、楕円曲線演算部１０５に対して、楕円曲線Ｅを利用した楕円曲線演算処理を要請する。この楕円曲線演算の例として、楕円曲線Ｅ上の点の加法や、楕円曲線Ｅ上の点をスカラ倍するスカラ倍演算がある。
【００７０】
復号処理部１０３は、楕円曲線演算部１０５に楕円曲線演算を要請する際には、楕円曲線演算を実行する際に必要となる楕円曲線上の点や、演算に必要となる各種のパラメータ（例えば、スカラ倍演算における係数）などを、演算パラメータとして伝送する。また、復号処理部１０３は、楕円曲線演算部１０５から楕円曲線を利用した演算結果が伝送されると、演算結果を利用して、復号処理を継続する。
【００７１】
復号処理部１０３は、復号処理が終了すると、生成された平文を、情報処理装置１０に設けられたディスプレイ等の表示装置に表示する。
【００７２】
楕円曲線演算部１０５は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。楕円曲線演算部１０５は、所定の有限体上で定義された楕円曲線Ｅと、暗号化処理部１０１または復号処理部１０３から伝送された演算パラメータとに基づいて、楕円曲線を利用した演算処理を行う。この楕円曲線演算部１０５は、楕円曲線演算制御部１１１と、加法演算部１０３と、スカラ倍演算部１１５と、演算検証部１１７と、演算結果出力部１１９と、を更に備える。
【００７３】
楕円曲線演算制御部１１１は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。楕円曲線演算制御部１１１は、暗号化処理部１０１および復号処理部１０３から伝送された演算パラメータに基づいて、暗号化処理部１０１および復号処理部１０３から要請された楕円曲線演算の実行制御を行う。
【００７４】
より詳細には、楕円曲線演算制御部１１１は、暗号化処理部１０１および復号処理部１０３から伝送された演算パラメータを参照して、これらの処理部から要請された楕円曲線演算の種類を判別する。楕円曲線演算制御部１１１は、暗号化処理部１０１および復号処理部１０３から要請された楕円曲線演算の種類を特定すると、特定した楕円曲線演算の種類に応じて、後述する加法演算部１１３およびスカラ倍演算部１１５に、取得した演算パラメータを伝送する。また、楕円曲線演算制御部１１１は、特定した楕円曲線演算の種類を、後述する演算検証部１１７に伝送する。
【００７５】
加法演算部１１３は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。加法演算部１１３は、楕円曲線演算制御部１１１から伝送された演算パラメータに含まれる楕円曲線Ｅ上の点に関する情報に基づいて、被演算点である楕円曲線上の点の加法演算を行う。具体的には、加法演算部１１３は、演算に用いる楕円曲線Ｅの種類に応じて、上記式１１〜式１３または式１５〜式２０を用いて、被演算点の加法演算を行う。なお、加法演算部１１３は、加法演算処理に際して、記憶部１０７等に格納されている楕円曲線パラメータや、公開鍵、秘密鍵等を参照してもよい。
【００７６】
加法演算部１１３は、被演算点に関する加法演算の演算結果が得られると、加法演算処理が終了した旨を、楕円曲線演算制御部１１１に伝送する。また、加法演算部１１３は、被演算点に関する加法演算の演算結果（すなわち、加法演算の結果得られる楕円曲線Ｅ上の点に関する情報）を、後述する演算検証部１１７に伝送する。なお、加法演算部１１３は、演算結果を後述するスカラ倍演算部１１５に伝送し、演算結果を、スカラ倍演算部１１５におけるスカラ倍演算処理に用いても良い。
【００７７】
スカラ倍演算部１１５は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。スカラ倍演算部１１５は、楕円曲線演算制御部１１１から伝送された演算パラメータに含まれる楕円曲線Ｅ上の被演算点に関する情報と、スカラ倍演算の係数に関する情報と、に基づいて、被演算点に関するスカラ倍演算を実行する。すなわち、スカラ倍演算部１１５は、被演算点をＰ、スカラ倍演算の係数をｓ、スカラ倍演算結果（以下、べき倍点とも称する。）をＱとすると、Ｑ＝ｓ・Ｐを演算する処理部である。
【００７８】
スカラ倍演算部１１５は、被演算点に関するスカラ倍演算を、例えば図４に示したＤｏｕｂｌｅ ａｎｄ Ａｄｄ Ｍｅｔｈｏｄのような計算アルゴリズムを実行することで行う。また、スカラ倍演算部１１５が実行する計算アルゴリズムは、上記の例に限定されるわけではなく、他の任意の計算アルゴリズムを利用することが可能である。
【００７９】
なお、スカラ倍演算部１１５は、スカラ倍演算処理に際して、記憶部１０７等に格納されている楕円曲線パラメータや、公開鍵、秘密鍵等を参照してもよい。例えば、スカラ倍演算部１１５は、スカラ倍演算の係数ｓとして、自装置で秘匿している秘密鍵や、自装置で管理されている公開鍵を利用することができる。
【００８０】
スカラ倍演算部１１５は、被演算点に関するスカラ倍演算の演算結果が得られると、スカラ倍演算処理が終了した旨を、楕円曲線演算制御部１１１に伝送する。また、スカラ倍演算部１１５は、被演算点に関するスカラ倍演算の演算結果（すなわち、スカラ倍演算の結果得られる楕円曲線Ｅ上の点に関する情報）を、後述する演算検証部１１７に伝送する。なお、スカラ倍演算部１１５は、演算結果を加法演算部１１３に伝送し、演算結果を、加法演算部１１３における加法演算処理に用いても良い。
【００８１】
演算検証部１１７は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。演算検証部１１７は、スカラ倍演算部１１５がスカラ倍演算を実行した場合に、スカラ倍演算部１１５により実行されたスカラ倍演算処理の検証を行う。より詳細には、演算検証部１１７は、スカラ倍演算における被演算点Ｐと、スカラ倍演算の結果得られる楕円曲線Ｅ上の点（べき倍点）Ｑと、楕円曲線パラメータであるベースポイントＧと、に基づいて、以下の式１０１の等号が成立するか否かを検証する。
【００８２】
（Ｐ＋Ｑ）＋Ｒ＝Ｐ＋（Ｑ＋Ｒ） ・・・（式１０１）
【００８３】
具体的には、演算検証部１１７は、上記式１０１の左辺に示した加法演算処理と、上記式１０１の右辺に示した加法演算処理と、を、加法演算部１１３に要請する。演算検証部１１７は、加法演算部１１３から伝送された左辺の演算結果と、右辺の演算結果とが同一の値であるか（すなわち、楕円曲線Ｅ上の同一の点であるか否か）を判定することで、上記式１０１の等号が成立したか否かを検証する。
【００８４】
演算検証部１１７は、上記式１０１における等号が成立するか否かを検証することで、被演算点Ｐに対する検証と、スカラ倍演算結果であるべき倍点Ｑに対する検証の双方を行っている。
【００８５】
まず、べき倍点Ｑに関する検証について、より詳細に説明する。
スカラ倍演算部１１５がべき倍点Ｑの演算を実行している途中に故障攻撃を受け、スカラ倍の演算結果が不正な点Ｑ’に変更されたとすると、演算の結果得られるべき倍点Ｑ’は、正しい楕円曲線Ｅとは異なる楕円曲線Ｅ’上の点となる。すなわち、Ｑ∈Ｅ’（Ｆｑ）である。上記式１０１として表される群の結合法則は、同一楕円曲線上の３点Ｐ，Ｑ，Ｇ∈Ｅ（Ｆｑ）に対して成立する。そのため、演算検証部１１７は、式１０１における等号が成立した場合には、被演算点Ｐ、べき倍点ＱおよびベースポイントＧが、同一の楕円曲線Ｅ上の点であることが確認できる。逆に、式１０１における等号が成立しなかった場合には、べき倍点Ｑは、加法群Ｅ（Ｆｑ）とは異なる群に属している（すなわち、被演算点ＰおよびベースポイントＧとは異なる楕円曲線上の点である）ことを示している。そのため、演算検証部１１７は、スカラ倍演算中に、攻撃者から故障攻撃を受けたことを検出することができる。
【００８６】
次に、被演算点Ｐに関する検証について、より詳細に説明する。
スカラ倍演算部１１５がスカラ倍演算を実行する前に被演算点がＰ’∈Ｅ’（Ｆｑ）に修正された場合、得られるスカラ倍演算の演算結果は、Ｑ’∈Ｅ’（Ｆｑ）となり、ベースポイントＧ∈Ｅ（Ｆｑ）とは異なる群に属することとなる。そのため、攻撃者による攻撃や、情報処理装置１０の故障等により被演算点Ｐに変更が生じた場合には、演算検証部１１７は、被演算点Ｐが適式な値ではなかったことを検出することができる。
【００８７】
なお、上述のような検証では、被演算点Ｐまたはべき倍点Ｑのどちらが適式ではなかったのかは、明らかにすることができない。そのため、以下のような処理を行うことで、演算検証部１１７は、被演算点Ｐまたはべき倍点Ｑのどちらが不適だったのかを明確にすることができる。
【００８８】
例えば、被演算点Ｐのみを検証したい場合には、演算検証部１１７は、べき倍点Ｑの代わりに、自装置が管理している公開鍵、または、信頼できる他の情報処理装置の公開鍵を利用し、上記式１０１が成立するか否かを検証する。これらの公開鍵は、被演算点Ｐが存在している楕円曲線と同一の楕円曲線を用いて算出されたものであるため、被演算点Ｐと同一の群に属するものである。そのため、べき倍点Ｑの代わりにこれらの公開鍵を利用することで、被演算点Ｐのみの検証を行うことができる。なお、信頼できる他の情報処理装置の例として、公開鍵および秘密鍵からなる鍵ペアを生成する鍵生成センタが保持する情報処理装置や、第三者認証機関が保持する情報処理装置等を挙げることができる。
【００８９】
また、べき倍点Ｑのみを検証したい場合、演算検証部１１７は、被演算点Ｐのみの検証と同様に、被演算点Ｐの代わりに、自装置が管理している公開鍵、または、信頼できる他の情報処理装置の公開鍵を利用し、上記式１０１が成立するか否かを検証すればよい。
【００９０】
なお、スカラ倍演算部１１５は、ベースポイントＧのスカラ倍演算など、被演算点Ｐの指定を受けずにスカラ倍演算を実行する場合もある。この際、演算検証部１１７は、被演算点Ｐの代わりに、自装置が管理している公開鍵、または、信頼できる他の情報処理装置の公開鍵を利用し、上記式１０１が成立するか否かを検証すればよい。
【００９１】
以上説明したように、演算検証部１１７は、式１０１における等号が成立しなかった場合、被演算点Ｐが適式な値ではなかった、または、べき倍点Ｑに改ざんが加えられたと判断することができる。この演算結果の検証は、加法演算部１１５による４回の加法演算の結果に基づき、１回の楕円曲線上の点の比較を行うことで実施できる。そのため、本実施形態に係る情報処理装置では、楕円曲線上の群の性質を利用することで、より簡便な方法で故障利用攻撃の有無を判定することができる。
【００９２】
演算検証部１１７は、スカラ倍演算に関する検証結果が得られると、得られた検証結果を、後述する演算結果出力部１１９に伝送する。より詳細には、演算検証部１１７は、加法演算部１１３が実行した加法演算結果が伝送されると、伝送された加法演算結果を演算結果出力部１１９に伝送する。また、演算検証部１１７は、スカラ倍演算部１１５からスカラ倍演算結果が伝送されると、式１０１を用いた検証を行い、検証が成功した場合に、スカラ倍演算の演算結果とともに、得られた検証結果を、演算結果出力部１１９に伝送する。また、演算検証部１１７は、スカラ倍演算の検証が失敗した場合には、検証に失敗した旨のみを演算結果出力部１１９に伝送する。
【００９３】
演算結果出力部１１９は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。演算結果出力部１１９は、演算検証部１１７から伝送された演算結果および検証結果を、楕円曲線演算部１０５に楕円曲線演算処理を要請した処理部に対して出力する。
【００９４】
記憶部１０７は、情報処理装置１０が管理する秘密鍵および公開鍵と、楕円曲線パラメータとを格納する。また、記憶部１０７は、情報処理装置１０が、何らかの処理を行う際に保存する必要が生じた様々なパラメータや処理の途中経過等、または、各種のデータベース等を、適宜記憶することが可能である。この記憶部１０７は、本実施形態に係る情報処理装置１０が備える各処理部が、自由に読み書きを行うことが可能である。
【００９５】
以上説明したように、本実施形態に係る情報処理装置１０では、暗号処理中に故障攻撃を受けて中間値が変更された可能性がある場合に、スカラ倍演算の演算結果の正当性を、楕円曲線の種類を問わず容易に検証することができる。
【００９６】
以上、本実施形態に係る情報処理装置１０の機能の一例を示した。上記の各構成要素は、汎用的な部材や回路を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。また、各構成要素の機能を、ＣＰＵ等が全て行ってもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用する構成を変更することが可能である。
【００９７】
なお、上述のような本実施形態に係る情報処理装置の各機能を実現するためのコンピュータプログラムを作製し、パーソナルコンピュータ等に実装することが可能である。また、このようなコンピュータプログラムが格納された、コンピュータで読み取り可能な記録媒体も提供することができる。記録媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、フラッシュメモリなどである。また、上記のコンピュータプログラムは、記録媒体を用いずに、例えばネットワークを介して配信してもよい。
【００９８】
＜演算検証方法について＞
続いて、図２を参照しながら、本実施形態に係る演算検証方法について、詳細に説明する。図２は、本実施形態に係る演算検証方法について説明するための流れ図である。
【００９９】
情報処理装置１０の暗号化処理部１０１または復号処理部１０３は、それぞれの処理部が行う処理に際して、楕円曲線上の点のスカラ倍演算が必要となった際に、楕円曲線演算部１０５に対して、スカラ倍演算の実行を要請する。この際、暗号化処理部１０１および復号処理部１０３は、楕円曲線演算部１０５に対して、被演算点Ｐに関する情報およびスカラ倍演算の係数ｓに関する情報を含む演算パラメータを伝送する。
【０１００】
楕円曲線演算部１０５の楕円曲線演算制御部１１１は、暗号化処理部１０１または復号処理部１０３から伝送された演算パラメータを取得し（ステップＳ１０１）、要請のあった楕円曲線演算における被演算点Ｐと、スカラ倍演算の係数ｓと、を把握する。続いて、楕円曲線演算制御部１１１は、取得した被演算点Ｐおよびスカラ倍演算の係数ｓを、スカラ倍演算部１１５に伝送する。
【０１０１】
スカラ倍演算部１１５は、楕円曲線演算制御部１１１から伝送された演算パラメータに基づいて、スカラ倍演算Ｑ＝ｓ・Ｐを実行する（ステップＳ１０３）。スカラ倍演算部１１５は、スカラ倍演算処理が終了すると、スカラ倍演算処理が終了した旨を楕円曲線演算制御部１１１に通知するとともに、演算結果であるべき倍点Ｑに関する情報を、演算検証部１１７に伝送する。
【０１０２】
演算検証部１１７は、スカラ倍演算部１１５から演算結果が伝送されると、加法演算部１１３に、以下の２種類の加法演算の実行を要請する。
【０１０３】
Ｓ１＝（Ｐ＋Ｑ）＋Ｒ ・・・（式１０２）
Ｓ２＝Ｐ＋（Ｑ＋Ｒ） ・・・（式１０３）
【０１０４】
加法演算部１１３は、演算検証部１１７から上記Ｓ１およびＳ２で表される２種類の加法演算を要請されると、上記式１０２および式１０３に基づいて加法演算を実行し（ステップＳ１０５）、演算結果を演算検証部１１７に伝送する。
【０１０５】
演算検証部１１７は、加法演算部１１３から伝送された値Ｓ１およびＳ２に基づいて、Ｓ１＝Ｓ２が成立するか（すなわち、上記式１０１の等号が成立するか否か）を検証する（ステップＳ１０７）。
【０１０６】
演算検証部１１７は、Ｓ１＝Ｓ２が成立した場合には、べき倍点Ｑが適式に演算されたと判断し、スカラ倍演算の演算結果と検証結果とを、演算結果出力部１１９に伝送する。その後、演算結果および検証結果を取得した演算結果出力部１１９は、楕円曲線演算の実行を要請した処理部に対して、演算結果Ｑを出力する（ステップＳ１０９）。
【０１０７】
他方、Ｓ１＝Ｓ２が成立しなかった場合には、演算検証部１１７は、べき倍点Ｑが適式に演算されなかったと判断し、この判断結果を演算結果出力部１１９に伝送する。その後、検証結果を取得した演算結果出力部１１９は、楕円曲線演算の実行を要請した処理部に対して、べき倍点Ｑが適式に演算されなかった旨を表すエラーを出力する（ステップＳ１１１）。
【０１０８】
以上説明したように、本実施形態に係る演算検証方法は、式１０１の左辺における２回の加法演算と、式１０１の右辺における２回の加法演算と、１回の点の比較演算のみで、演算結果の検証を行うことができる。このため、本実施形態に係る演算検証方法では、ある値のべき乗を計算する等といった複雑な演算処理を行うことなく、スカラ倍演算の演算結果の正当性を、楕円曲線の種類を問わず容易に検証することができる。
【０１０９】
また、本実施形態に係る演算検証方法では、有限体における比較処理が不要であり、楕円曲線上の加算／比較処理をそのまま利用できる。そのため、本実施形態に係る演算検証方法をハードウェア的に実現する場合には、演算検証方法を実現するための回路規模を小さくすることが可能となる。また、本実施形態に係る演算検証方法では、被演算点Ｐおよびべき倍点Ｑの双方をあわせて検証することができるため、入力値および出力値の検証ステップを、従来の手法よりも簡略化することができる。その結果、本実施形態に係る演算検証方法をソフトウェア的に実現する場合に、計算コストを削減することができる。
【０１１０】
（ハードウェア構成について）
次に、図３を参照しながら、本発明の実施形態に係る情報処理装置１０のハードウェア構成について、詳細に説明する。図３は、本発明の実施形態に係る情報処理装置１０のハードウェア構成を説明するためのブロック図である。
【０１１１】
情報処理装置１０は、主に、ＣＰＵ９０１と、ＲＯＭ９０３と、ＲＡＭ９０５と、を備える。また、情報処理装置１０は、更に、ホストバス９０７と、ブリッジ９０９と、外部バス９１１と、インターフェース９１３と、入力装置９１５と、出力装置９１７と、ストレージ装置９１９と、ドライブ９２１と、接続ポート９２３と、通信装置９２５とを備える。
【０１１２】
ＣＰＵ９０１は、演算処理装置および制御装置として機能し、ＲＯＭ９０３、ＲＡＭ９０５、ストレージ装置９１９、またはリムーバブル記録媒体９２７に記録された各種プログラムに従って、情報処理装置１０内の動作全般またはその一部を制御する。ＲＯＭ９０３は、ＣＰＵ９０１が使用するプログラムや演算パラメータ等を記憶する。ＲＡＭ９０５は、ＣＰＵ９０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を一次記憶する。これらはＣＰＵバス等の内部バスにより構成されるホストバス９０７により相互に接続されている。
【０１１３】
ホストバス９０７は、ブリッジ９０９を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス９１１に接続されている。
【０１１４】
入力装置９１５は、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチおよびレバーなどユーザが操作する操作手段である。また、入力装置９１５は、例えば、赤外線やその他の電波を利用したリモートコントロール手段（いわゆる、リモコン）であってもよいし、情報処理装置１０の操作に対応した携帯電話やＰＤＡ等の外部接続機器９２９であってもよい。さらに、入力装置９１５は、例えば、上記の操作手段を用いてユーザにより入力された情報に基づいて入力信号を生成し、ＣＰＵ９０１に出力する入力制御回路などから構成されている。情報処理装置１０のユーザは、この入力装置９１５を操作することにより、情報処理装置１０に対して各種のデータを入力したり処理動作を指示したりすることができる。
【０１１５】
出力装置９１７は、取得した情報をユーザに対して視覚的または聴覚的に通知することが可能な装置で構成される。このような装置として、ＣＲＴディスプレイ装置、液晶ディスプレイ装置、プラズマディスプレイ装置、ＥＬディスプレイ装置およびランプなどの表示装置や、スピーカおよびヘッドホンなどの音声出力装置や、プリンタ装置、携帯電話、ファクシミリなどがある。出力装置９１７は、例えば、情報処理装置１０が行った各種処理により得られた結果を出力する。具体的には、表示装置は、情報処理装置１０が行った各種処理により得られた結果を、テキストまたはイメージで表示する。他方、音声出力装置は、再生された音声データや音響データ等からなるオーディオ信号をアナログ信号に変換して出力する。
【０１１６】
ストレージ装置９１９は、情報処理装置１０の記憶部の一例として構成されたデータ格納用の装置である。ストレージ装置９１９は、例えば、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等の磁気記憶部デバイス、半導体記憶デバイス、光記憶デバイス、または光磁気記憶デバイス等により構成される。このストレージ装置９１９は、ＣＰＵ９０１が実行するプログラムや各種データ、および外部から取得した音響信号データや画像信号データなどを格納する。
【０１１７】
ドライブ９２１は、記録媒体用リーダライタであり、情報処理装置１０に内蔵、あるいは外付けされる。ドライブ９２１は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体９２７に記録されている情報を読み出して、ＲＡＭ９０５に出力する。また、ドライブ９２１は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体９２７に記録を書き込むことも可能である。リムーバブル記録媒体９２７は、例えば、ＤＶＤメディア、ＨＤ−ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア等である。また、リムーバブル記録媒体９２７は、コンパクトフラッシュ（登録商標）（ＣｏｍｐａｃｔＦｌａｓｈ：ＣＦ）、メモリースティック、または、ＳＤメモリカード（Ｓｅｃｕｒｅ Ｄｉｇｉｔａｌ ｍｅｍｏｒｙ ｃａｒｄ）等であってもよい。また、リムーバブル記録媒体９２７は、例えば、非接触型ＩＣチップを搭載したＩＣカード（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ ｃａｒｄ）または電子機器等であってもよい。
【０１１８】
接続ポート９２３は、機器を情報処理装置１０に直接接続するためのポートである。接続ポート９２３の一例として、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）ポート、ｉ．Ｌｉｎｋ等のＩＥＥＥ１３９４ポート、ＳＣＳＩ（Ｓｍａｌｌ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍ Ｉｎｔｅｒｆａｃｅ）ポート等がある。接続ポート９２３の別の例として、ＲＳ−２３２Ｃポート、光オーディオ端子、ＨＤＭＩ（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ Ｍｕｌｔｉｍｅｄｉａ Ｉｎｔｅｒｆａｃｅ）ポート等がある。この接続ポート９２３に外部接続機器９２９を接続することで、情報処理装置１０は、外部接続機器９２９から直接各種のデータを取得したり、外部接続機器９２９に各種のデータを提供したりする。
【０１１９】
通信装置９２５は、例えば、通信網９３１に接続するための通信デバイス等で構成された通信インターフェースである。通信装置９２５は、例えば、有線または無線ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、Ｂｌｕｅｔｏｏｔｈ、またはＷＵＳＢ（Ｗｉｒｅｌｅｓｓ ＵＳＢ）用の通信カード等である。また、通信装置９２５は、光通信用のルータ、ＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ Ｄｉｇｉｔａｌ Ｓｕｂｓｃｒｉｂｅｒ Ｌｉｎｅ）用のルータ、または、各種通信用のモデム等であってもよい。この通信装置９２５は、例えば、インターネットや他の通信機器との間で、例えばＴＣＰ／ＩＰ等の所定のプロトコルに則して信号等を送受信することができる。また、通信装置９２５に接続される通信網９３１は、有線または無線によって接続されたネットワーク等により構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、ラジオ波通信または衛星通信等であってもよい。
【０１２０】
以上、本発明の実施形態に係る情報処理装置１０の機能を実現可能なハードウェア構成の一例を示した。上記の各構成要素は、汎用的な部材を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用するハードウェア構成を変更することが可能である。
【０１２１】
＜まとめ＞
以上説明したように、本発明の実施形態に係る情報処理装置および演算検証方法では、スカラ倍演算における被演算点Ｐと、スカラ倍演算の演算結果であるべき倍点Ｑと、楕円曲線のベースポイントＥとを利用して、簡便にスカラ倍演算の検証を行うことができる。
【０１２２】
より詳細には、本発明の実施形態に係る情報処理装置および演算検証方法では、４回の加法演算と、１回の点の比較演算のみで、演算結果の検証を行うことができる。このため、本発明の実施形態に係る情報処理装置および演算検証方法では、ある値のべき乗を計算する等といった複雑な演算処理を行うことなく、スカラ倍演算の演算結果の正当性を、楕円曲線の種類を問わず容易に検証することができる。
【０１２３】
また、本発明の実施形態に係る情報処理装置および演算検証方法では、有限体における比較処理が不要であり、楕円曲線上の加算／比較処理をそのまま利用できる。そのため、本発明の実施形態に係る演算検証方法をハードウェア的に実現する場合には、演算検証方法を実現するための回路規模を小さくすることが可能となる。また、本発明の実施形態に係る情報処理装置および演算検証方法をソフトウェア的に実現する場合には、計算コストを削減することができる。
【０１２４】
以上、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明はかかる例に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０１２５】
１０ 情報処理装置
１０１ 暗号化処理部
１０３ 復号処理部
１０５ 楕円曲線演算部
１０７ 記憶部
１１１ 楕円曲線演算制御部
１１３ 加法演算部
１１５ スカラ倍演算部
１１７ 演算検証部
１１９ 演算結果出力部
【特許請求の範囲】
【請求項１】
所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算部と、
前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証部と、
を備える、情報処理装置。
（Ｐ＋Ｑ）＋Ｇ＝Ｐ＋（Ｑ＋Ｇ） ・・・（式１）
【請求項２】
前記楕円曲線Ｅは、
有限体Ｆｑ（ｑ＝ｐｍ，ｍ∈Ｎ，ｐ＞３）上で定義された楕円曲線ＥＡ：ｙ２＝ｘ３＋ａｘ＋ｂ（ａ，ｂ∈Ｆｑ）、または、
標数２の有限体Ｆ２＾ｍ（ｍ∈Ｎ）上で定義された楕円曲線ＥＢ：ｙ２＋ｘｙ＝ｘ３＋ａ２ｘ２＋ａ６（ａ２，ａ６∈Ｆ２＾ｍ）
である、請求項１に記載の情報処理装置。
【請求項３】
前記演算検証部は、前記式１における等号が成立しなかった場合、前記点Ｐが適式な値ではなかった、または、点Ｑに改ざんが加えられたと判断する、請求項２に記載の情報処理装置。
【請求項４】
前記情報処理装置は、自装置が秘匿すべき情報である秘匿情報を格納する記憶部を更に備え、
前記楕円曲線Ｅ上の任意の点Ｇは、前記秘匿情報の一つとして前記記憶部に格納される、請求項１に記載の情報処理装置。
【請求項５】
前記記憶部には、自装置が保持する秘密鍵ｄが格納されており、
前記スカラ倍演算部は、スカラ倍演算の係数ｓとして前記秘密鍵ｄを用いる、請求項１に記載の情報処理装置。
【請求項６】
前記演算検証部は、前記点Ｐまたは前記点Ｑの代わりに、自装置が保持している公開鍵または信頼できる他の情報処理装置が保持している公開鍵を用いて、前記式１における等号が成立するか否かを検証する、請求項１に記載の情報処理装置。
【請求項７】
所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するステップと、
前記楕円曲線Ｅ上の点Ｐと、算出された点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証するステップと
を含む、演算検証方法。
【請求項８】
コンピュータに、
所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算機能と、
前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算機能により算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証機能と、
を実現させるためのプログラム。
【請求項１】
所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算部と、
前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算部が算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証部と、
を備える、情報処理装置。
（Ｐ＋Ｑ）＋Ｇ＝Ｐ＋（Ｑ＋Ｇ） ・・・（式１）
【請求項２】
前記楕円曲線Ｅは、
有限体Ｆｑ（ｑ＝ｐｍ，ｍ∈Ｎ，ｐ＞３）上で定義された楕円曲線ＥＡ：ｙ２＝ｘ３＋ａｘ＋ｂ（ａ，ｂ∈Ｆｑ）、または、
標数２の有限体Ｆ２＾ｍ（ｍ∈Ｎ）上で定義された楕円曲線ＥＢ：ｙ２＋ｘｙ＝ｘ３＋ａ２ｘ２＋ａ６（ａ２，ａ６∈Ｆ２＾ｍ）
である、請求項１に記載の情報処理装置。
【請求項３】
前記演算検証部は、前記式１における等号が成立しなかった場合、前記点Ｐが適式な値ではなかった、または、点Ｑに改ざんが加えられたと判断する、請求項２に記載の情報処理装置。
【請求項４】
前記情報処理装置は、自装置が秘匿すべき情報である秘匿情報を格納する記憶部を更に備え、
前記楕円曲線Ｅ上の任意の点Ｇは、前記秘匿情報の一つとして前記記憶部に格納される、請求項１に記載の情報処理装置。
【請求項５】
前記記憶部には、自装置が保持する秘密鍵ｄが格納されており、
前記スカラ倍演算部は、スカラ倍演算の係数ｓとして前記秘密鍵ｄを用いる、請求項１に記載の情報処理装置。
【請求項６】
前記演算検証部は、前記点Ｐまたは前記点Ｑの代わりに、自装置が保持している公開鍵または信頼できる他の情報処理装置が保持している公開鍵を用いて、前記式１における等号が成立するか否かを検証する、請求項１に記載の情報処理装置。
【請求項７】
所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するステップと、
前記楕円曲線Ｅ上の点Ｐと、算出された点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証するステップと
を含む、演算検証方法。
【請求項８】
コンピュータに、
所定の定義体上で定義された楕円曲線Ｅ上の点Ｐに基づいて、点Ｐをスカラ倍した点Ｑ＝ｓ・Ｐを演算するスカラ倍演算機能と、
前記楕円曲線Ｅ上の点Ｐと、前記スカラ倍演算機能により算出した点Ｑ＝ｓ・Ｐと、前記楕円曲線Ｅ上の任意の点Ｇと、を用いて、以下の式１における等号が成立するか否かを検証する演算検証機能と、
を実現させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【公開番号】特開２０１０−２５８７０８（Ｐ２０１０−２５８７０８Ａ）
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願番号】特願２００９−１０５５８５（Ｐ２００９−１０５５８５）
【出願日】平成２１年４月２３日（２００９．４．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願日】平成２１年４月２３日（２００９．４．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]