(57)【特許請求の範囲】
【請求項１】
入力座標点及び入力スカラー値を受け、前記入力座標点のスカラー倍算値を得るスカラー倍算装置であって、
２つの入力値の加算演算を実行する加算演算部と、
１つの入力値の２倍算演算を実行する２倍算演算部と、
前記入力スカラー値あるいは前記入力スカラー値を変換して得られる変換スカラー値を演算用スカラー値とし、前記演算用スカラー値と前記入力座標点とを演算対象として、スカラー倍算処理を行い前記スカラー倍算値を得るスカラー倍演算機構とを備え、
前記演算用スカラー値は複数の桁部を有し、前記複数の桁部はそれぞれ少なくとも１ビットの情報量を有し、
前記スカラー倍算処理は、前記複数の桁部に対応して実行され各々が桁部演算結果を得る複数の桁部演算処理を含み、前記複数の桁部演算処理の実行により、隣接する桁部間で上位から下位に桁部演算結果を伝搬しつつ、最上位から最下位にかけて桁部単位に桁部演算結果を順次得て、最下位の桁部より得られる桁部演算結果を前記スカラー倍算値とし、
前記複数の桁部演算処理はそれぞれ、前記加算演算部及び前記２倍算演算部を用いて実行され、桁部の値が“０”の場合はゼロ演算処理を実行して桁部演算結果を取得し、“０”以外の場合は前記ゼロ演算処理と異なる演算内容の非ゼロ演算処理を実行して桁部演算結果を取得し、
前記ゼロ演算処理及び前記非ゼロ演算処理を共に、２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、前記第２の加算処理の演算結果を桁部演算結果としたことを特徴とする、
スカラー倍算装置。
【請求項２】
請求項１記載のスカラー倍算装置であって、
前記演算用スカラー値は前記入力スカラー値であり、前記複数の桁部はそれぞれ１ビットの情報量を有し、
前記２倍算処理は前記２倍算演算部を１回用いて１回倍算値を得る処理を含む、
スカラー倍算装置。
【請求項３】
請求項１記載のスカラー倍算装置であって、
前記演算用スカラー値は前記変換スカラー値であり、前記複数の桁部はそれぞれＭ（Ｍ≧２）ビットの情報量を有し、
前記スカラー倍算処理は、
前記入力スカラー値を前記変換スカラー値に変換するスカラー値変換処理と、
前記入力座標点に基づき、前記入力座標点を整数倍して得られる整数倍座標点を複数種有する倍数テーブルを作成するテーブル作成処理と、
前記スカラー値変換処理及び前記テーブル作成処理の実行後に、前記複数の桁部演算処理を実行するスカラー倍算本処理とを含み、
前記２倍算処理は前記２倍算演算部をＭ回繰り返し用いてＭ回倍算値を得る処理を含み、
前記第１の加算処理は前記非ゼロ演算処理の実行時に前記倍数テーブルを用いて行われる、
スカラー倍算装置。
【請求項４】
請求項１記載のスカラー倍算装置であって、
前記演算用スカラー値は前記変換スカラー値であり、前記複数の桁部はそれぞれ正負を含む１ビットの情報量を有し
前記スカラー倍算処理は、
前記入力スカラー値を前記変換スカラー値に変換するスカラー値変換処理と、
前記スカラー値変換処理の実行後に、前記複数の桁部演算処理を実行するスカラー倍算本処理とを含み、
前記２倍算処理は前記２倍算演算部を１回用いて１回倍算値を得る処理を含み、
前記非ゼロ演算処理は、前記桁部の値が正の場合に実行される第１の非ゼロ演算処理と
前記桁部の値が負の場合に実行される第２の非ゼロ演算処理とを含み、前記第１及び第２の非ゼロ演算処理は共に前記２倍算処理、前記第１の加算処理、及び前記第２の加算処理の順で行い、前記第２の加算処理の演算結果を桁部演算結果としている、
スカラー倍算装置。
【請求項５】
請求項１記載のスカラー倍算装置であって、
前記演算用スカラー値は前記変換スカラー値であり、前記複数の桁部はそれぞれＭ（Ｍ≧２）ビット以下のＫ（Ｋ＝１〜Ｍのいずれか）ビットの情報量を有し、
前記スカラー倍算処理は、
前記入力スカラー値を前記変換スカラー値に変換するスカラー値変換処理と、
前記入力座標点に基づき、前記入力座標点を偶数倍して偶数倍座標点を複数種有する倍数テーブルを作成するテーブル作成処理と、
前記スカラー値変換処理及び前記テーブル作成処理の実行後に、前記複数の桁部演算処理を実行するスカラー倍算本処理とを含み、
前記２倍算処理は前記２倍算演算部をＭ回繰り返し用いて１回倍算値〜Ｍ回倍算値を得た後、Ｋ回倍算値を選択する処理を含み、
前記非ゼロ演算処理は、前記桁部の値が正の場合に実行される第１の非ゼロ演算処理と
前記桁部の値が負の場合に実行される第２の非ゼロ演算処理とを含み、前記第１及び第２の非ゼロ演算処理は共に前記２倍算処理、前記第１の加算処理、及び前記第２の加算処理の順で行い、前記第２の加算処理の演算結果を桁部演算結果としている、
スカラー倍算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、入力座標点をスカラー倍算してスカラー倍算値を得るスカラー倍算装置に関する。
【背景技術】
【０００２】
楕円曲線暗号の主演算であるスカラー倍算処理は、有理点Ｐとスカラー（倍数）値ｄの乗算を行うことで、スカラー倍算値ｄＰ（スカラー倍数点）を求める演算処理である。楕円曲線暗号はスカラー倍算値ｄＰからスカラー値ｄを求めるのは困難なこと(楕円曲線上の離散対数問題(ECDLP))を安全性の根拠としている。
【０００３】
楕円曲線上の有理点の演算は、無限遠点を零元とする加群を成す。一般的に直線を用いた加算、２倍算の２種類が定義される。これらの演算は、スカラー（倍数）値ｄをバイナリ法などの加算鎖アルゴリズムによってビット展開し、各ビットの値によって加算、２倍算を行うことで、スカラー倍算処理を実現している。しかし、処理時間はスカラー値ｄに依存して変化（タイミングリークが発生）するため、スカラー値ｄが漏洩するという問題がある。タイミングリークの回避策としては、スカラー値ｄのビット値が“０”の場合でもダミー演算を行うことが考えられるが、非特許文献１によってフォルト挿入によるセーフエラー攻撃によってダミー演算からスカラー値ｄの漏洩の可能性が指摘されている。また特許文献１〜特許文献６において様々なサイドチャネル攻撃対策が提案されているが、各種入力データ（スカラー値ｄ、有理点Ｐ）を写像や変換を行う必要があるため、主演算であるスカラー倍算処理以外に用いる演算器や制御機構が必要なため実装コストが高くなる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４７８３０６１号公報
【特許文献２】特許第４２８４３２０号公報
【特許文献３】特許第４６６８９３１号公報
【特許文献４】特許第５２３３４７３号公報
【特許文献５】特許第５４８８７１８号公報
【特許文献６】特許第５５７３９６４号公報
【非特許文献】
【０００５】
【非特許文献１】菅原 健、鈴木 大輔,『楕円群演算において無限遠点が特別扱いされることを利用したECDSAのセーフエラー攻撃』(SCIS2015)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述したように、ダミー演算によるタイミングリーク回避策を施した従来のスカラー倍算装置は、フォルト挿入によるセーフエラー攻撃に弱いという問題点があった。また、サイドチャネル攻撃対策にスカラー倍算処理以外の種々の演算処理を余分に実行するようにしたスカラー倍算装置は実装コストが高くなるという問題点があった。
【０００７】
この発明は上記問題点を解決するためになされたもので、サイドチャネル攻撃に強く、セキュリティー性が高いスカラー倍演算処理を実行するスカラー倍算装置を比較的簡単な構成で得ることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る請求項１記載のスカラー倍算装置は、入力座標点及び入力スカラー値を受け、前記入力座標点のスカラー倍算値を得るスカラー倍算装置であって、２つの入力値の加算演算を実行する加算演算部と、１つの入力値の２倍算演算を実行する２倍算演算部と、前記入力スカラー値あるいは前記入力スカラー値を変換して得られる変換スカラー値を演算用スカラー値とし、前記演算用スカラー値と前記入力座標点とを演算対象として、スカラー倍算処理を行い前記スカラー倍算値を得るスカラー倍演算機構とを備え、前記演算用スカラー値は複数の桁部を有し、前記複数の桁部はそれぞれ少なくとも１ビットの情報量を有し、前記スカラー倍算処理は、前記複数の桁部に対応して実行され各々が桁部演算結果を得る複数の桁部演算処理を含み、前記複数の桁部演算処理の実行により、隣接する桁部間で上位から下位に桁部演算結果を伝搬しつつ、最上位から最下位にかけて桁部単位に桁部演算結果を順次得て、最下位の桁部より得られる桁部演算結果を前記スカラー倍算値とし、前記複数の桁部演算処理はそれぞれ、前記加算演算部及び前記２倍算演算部を用いて実行され、桁部の値が“０”の場合はゼロ演算処理を実行して桁部演算結果を取得し、“０”以外の場合は前記ゼロ演算処理と異なる演算内容の非ゼロ演算処理を実行して桁部演算結果を取得し、前記ゼロ演算処理及び前記非ゼロ演算処理を共に、２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、前記第２の加算処理の演算結果を桁部演算結果としたことを特徴としている。
【発明の効果】
【０００９】
請求項１記載の本願発明におけるスカラー倍算装置は、上記特徴を有することにより、ゼロ演算処理及び非ゼロ演算処理間で共通の演算処理（２倍算処理、第１及び第２の加算処理）の実行後にはじめて桁部演算結果を得ている。このため、演算用スカラー値の桁部の値が“０”か非“０”かによって演算処理時間の変化が生じない。したがって、ゼロ演算処理及び非ゼロ演算処理間における演算処理時の差異に基づくタイミングリークを確実に回避することができる。
【００１０】
さらに、ゼロ演算処理及び非ゼロ演算処理間で実行される２倍算処理、第１及び第２の加算処理は全て桁部演算結果を得るために必要な演算処理であり、演算結果が利用されないダミー演算処理ではない。したがって、ダミー演算処理に対するセーフエラー攻撃が実行されることもない。
【００１１】
加えて、スカラー倍算処理以外のサイドチャネル攻撃用の演算処理を特に施していないため、比較的簡単な構成で実現できる。
【００１２】
その結果、タイミングリークの検知及びセーフエラー攻撃を含むサイドチャネル攻撃に強く、セキュリティー性が高いスカラー倍算処理を実行するスカラー倍算装置を得ることができる。
【図面の簡単な説明】
【００１３】
【図１】本願発明のスカラー倍算装置のスカラー倍算アルゴリズムの概要を示す説明図である。
【図２】実施の形態１（〜４）のスカラー倍算装置の構成を示すブロック図である。
【図３】実施の形態１のスカラー倍算アルゴリズムを模式的に示す説明図である。
【図４】実施の形態１のスカラー倍算アルゴリズムの実行例を模式的に示す説明図である。
【図５】Window法における変換アルゴリズムを模式的に示す説明図である。
【図６】Window法における従来の事前計算アルゴリズムを模式的に示す説明図である。
【図７】Window法における従来の本計算アルゴリズムを模式的に示す説明図である。
【図８】実施の形態２の事前計算アルゴリズムを模式的に示す説明図である。
【図９】実施の形態２の本計算アルゴリズムを模式的に示す説明図である。
【図１０】実施の形態２の本計算アルゴリズムの実行例を模式的に示す説明図である。
【図１１】ＮＡＦ法における変換アルゴリズムを模式的に示す説明図である。
【図１２】ＮＡＦ法における従来の本計算アルゴリズムを模式的に示す説明図である。
【図１３】実施の形態３の本計算アルゴリズムを模式的に示す説明図である。
【図１４】実施の形態３の本計算アルゴリズムの実行例を模式的に示す説明図である。
【図１５】ｗＮＡＦ法における従来の変換アルゴリズムを模式的に示す説明図である。
【図１６】ｗＮＡＦ法における従来の事前計算アルゴリズムを模式的に示す説明図である。
【図１７】ｗＮＡＦ法における従来の本計算アルゴリズムを模式的に示す説明図である。
【図１８】実施の形態４の変換アルゴリズムを模式的に示す説明図である。
【図１９】実施の形態４の事前計算アルゴリズムを模式的に示す説明図である。
【図２０】実施の形態４の本計算アルゴリズムを模式的に示す説明図である。
【図２１】実施の形態４の本計算アルゴリズムの実行例を模式的に示す説明図（その１）である。
【図２２】実施の形態４の本計算アルゴリズムの実行例を模式的に示す説明図（その２）である。
【図２３】楕円曲線を示す説明図である。
【図２４】従来のバイナリ法のアルゴリズムを示す説明図である。
【図２５】ダミー演算処理を実行する、従来のバイナリ法のアルゴリズムを示す説明図である。
【発明を実施するための形態】
【００１４】
＜発明の原理＞
（楕円曲線暗号について）
公開鍵暗号としてはＲＳＡ暗号が普及しているが、近年、同じ安全性をより短い鍵長で実現できる楕円曲線暗号の普及が進んできており、デジタル家電の認証や、著作権保護に採用されている。楕円曲線暗号のもう一つ特筆すべき点は、楕円曲線上のペアリングと呼ばれる双線形写像を用いたペアリング暗号へ拡張できることである。ペアリングを利用した暗号プロトコルの研究が盛んになっており、そのような暗号としては、ＩＤベース暗号、タイムリリース暗号、属性ベース暗号、検索可能暗号、関数型暗号などがある。
【００１５】
（楕円曲線の定義）
図２３は楕円曲線を示す説明図である。本明細書では、Weierstrass標準形Ｅ：｛ｙ２＝ｘ３＋aｘ＋ｂ｝で与えられる標数ｐ＞３の有限体Ｆｐ上の楕円曲線の場合について記述する。楕円曲線Ｅに含まれる任意の２点Ｐ，Ｑ∈Ｅ対して、｛Ｐ＋Ｑ｝と表記される第３の点が、図２３のようなＰとＱとを通る直線Ｌを使って幾何学的に定義され、この演算｛＋｝によってＥは群を成す。
【００１６】
（楕円曲線上の有理点の加法（直線による定義））
楕円曲線の重要な性質は、Ｐ，Ｑ∈Ｅ（Ｆ）に対して第３の点｛Ｐ＋Ｑ｝∈Ｅ（Ｆ）が幾何学的に定義でき、無限遠点Ｏを零元とする加群を成すことである。Ｆが有限体Ｆｐの時は、Ｅ（Ｆｐ）は有限群となり、その位数を＃Ｅ（Ｆｐ）と表記する。
【００１７】
この幾何学的な加法は点の座標を用いて記述することができる。Ｐ＝（ｘ１，ｙ１）、Ｑ＝（ｘ２，ｙ２）とすると、Ｐ＋Ｑ＝（ｘ３，ｙ３）は以下の式(1)〜式(3)で与えられる。
【００１８】
【数１】
0006457911.tif 000002
【００１９】
【数２】
0006457911.tif 000003
【００２０】
【数３】
0006457911.tif 000004
【００２１】
式(2)の公式は、Ｐ≠Ｑ場合は加算、Ｐ＝Ｑの場合は２倍算と呼ばれる。以降、アルゴリズムを表す擬似言語の図中では、加算をＥＣＡＤＤ（Ｐ，Ｑ）、２倍算をＥＣＤＢＬ（Ｐ）という関数形式で表す。
【００２２】
（スカラー倍算処理）
上述した加法の繰り返しにより、楕円曲線上の有理点と整数に対してスカラー倍数値ｄＰは、スカラー値ｄ個の和となる｛ｄＰ＝Ｐ＋Ｐ＋…＋Ｐ｝が定義される。
【００２３】
このような演算をスカラー倍算と呼び、楕円曲線暗号はスカラー倍算値ｄＰからＰを求めることは困難なこと(楕円曲線上の離散対数問題(ECDLP))を安全性の根拠としている。
【００２４】
実際にスカラー倍算値ｄＰを求めるには、加算鎖アルゴリズムを用いることが一般的である。
【００２５】
図２４は代表的な加算鎖アルゴリズムである、従来のLeft to Rightバイナリ法のアルゴリズムを示す説明図である。なお、図２４で示すスカラー倍算アルゴリズムＡＲ５１において、１：，２：，…７：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ７と呼ぶ。
【００２６】
図２４に示すスカラー倍算アルゴリズムＡＲ５１は、スカラー値ｄはｓビットの２進数｛ｄｓ−１，ｄｓ−２，…，ｄ１，ｄ０｝で表される。すなわち、スカラー値ｄは各々が１ビットの情報量を有するｓ個の桁部により表される。
【００２７】
そして、スカラー値ｄに対し、最上位桁（ｓ−１）から、最下位桁０にかけて、ステップＳＴ３の２倍算関数ＥＣＤＢＬ（Ｑ）後に、各桁部の値ｄｉ（ｉ＝（ｓ−１）〜０のいずれか）が“１”であるか否か（“０”であるか否か）に基づき、ステップＳＴ４の加算関数ＥＣＡＤＤ（Ｐ，Ｑ）の実行の有無が分けられる桁部演算処理を実行し、最終的に最下位桁０のｄ０の桁部演算処理によって得られる値Ｑ（桁部演算結果）が、スカラー倍算値ｄＰとして得られる。
【００２８】
このように、Left to Rightバイナリ法は、スカラー値ｄを２進数表記にしたときの各桁部（ビット）の値ｄｉによってステップＳＴ４の加算処理を行うかどうかが分岐するという特徴がある。
【００２９】
（課題）
楕円曲線の演算は、一般的に楕円曲線上の点を通る直線により、有理点の加算、及び２倍算という加法が定義され、Left to Rightバイナリ法等の加算鎖アルゴリズムによって、加算（ＥＣＡＤＤ（Ｐ，Ｑ））及び２倍算（ＥＣＤＢＬ（Ｑ））に展開することによってスカラー倍算処理を実現している。
【００３０】
しかし、バイナリ法のアルゴリズムは秘密鍵となるスカラー（倍数）値ｄの各ビット値ｄｉに依存して処理時間が変化するタイミングリークが発生するため、スカラー値ｄが漏洩する恐れがある。
【００３１】
図２５はダミー演算処理を挿入した、従来のLeft to Rightバイナリ法のアルゴリズムを示す説明図である。なお、図２５で示すスカラー倍算アルゴリズムＡＲ５２において、１：，２：，…８：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ８と呼ぶ。
【００３２】
図２５のスカラー倍算アルゴリズムＡＲ５２に示すように、一般的な対策としては、ステップＳＴ５で示すダミー演算（加算関数ＥＣＡＤＤ（Ｑ，Ｐ））を挿入してスカラー値ｄのビット値ｄｉに関わらず、処理時間を一定にしている。
【００３３】
このステップＳＴ５のダミー演算により得られた変数Ｄは、演算後破棄される。ダミー演算を挿入することにより、スカラー値ｄのビット値ｄｉの“０”，“１”（ゼロであるか、非ゼロであるか）に依存せず処理時間が同じになるためタイミングリークを回避することができる。
【００３４】
しかし、このようなダミー演算がある場合、非特許文献１に開示されたように、フォルト挿入により中間結果が無限遠点Ｏに入った時に限り、誤りが伝播しないことを利用してスカラー倍数値を推定するセーフエラー攻撃に弱いという問題点があった。
【００３５】
以下、セーフエラー攻撃例を説明する。スカラー倍算アルゴリズムＡＲ５２のステップＳＴ４またはステップＳＴ５で、｛Ｑ＋Ｐ→Ｏ｝となるようなフォルトを挿入する（例えば、Ｑ＝−Ｐとする）。
【００３６】
すると、次に実行される（仮にｉ＝ｎ−１とする）ステップＳＴ３で、２Ｑ→Ｏとなる場合は、ｄｎ＝１、そうでない場合はｄｎ＝０と推定することができる。以下、この点を詳述する。
【００３７】
ステップＳＴ４で｛Ｑ＋Ｐ→Ｏ｝となるようにフォルトを挿入すると、次に実行されるステップＳＴ３で“０”の倍算時に無限遠点Ｏであることが判明し例外処理が実行されることにより、ｄｎ＝１であったと予測できる。
【００３８】
一方、ステップ５で｛Ｑ＋Ｐ→Ｏ｝となるようにフォルトを挿入しても、Ｄ（ダミー演算結果）は破棄されるため、次に実行されるステップＳＴ３で“０”の倍算時に無限遠点Ｏとならず例外処理が実行されないことにより、ｄｎ＝０であったと予測できる。
【００３９】
このように、ダミー演算を挿入して、ｄｉ＝“０”，“１”に関わらず、加算関数ＥＣＡＤＤ（Ｐ，Ｑ）を実行するようにしても、フォルト挿入によるセーフエラー攻撃によりスカラー値ｄが漏洩する問題を回避することができない課題がある。
【００４０】
以下の実施の形態１〜実施の形態４で述べる本願発明のスカラー倍算装置は、フォルト挿入によるセーフエラー攻撃によりスカラー値ｄが漏洩する問題を回避するという、課題の解決を図る装置である。
【００４１】
（発明の概要）
本願発明のスカラー倍算装置では、スカラー（倍数）値ｄに依存したタイミングリークの回避、及び無限遠点Ｏが特別扱いされることを利用したセーフエラー攻撃への対策として、加法公式の組み合わせによって処理時間をスカラー値のビット値に依存せず一定にしたまま、Left to Rightバイナリ法（以下、単に「バイナリ法」と略記する場合あり）に代表されるスカラー倍算アルゴリズムが成立する演算の組み合わせを提案する。
【００４２】
図１は本願発明のスカラー倍算装置のスカラー倍算アルゴリズムの概要を示す説明図である。スカラー値ｄはそれぞれが１ビットの情報量を有する複数の桁部により構成されている。
【００４３】
図２４及び図２５で示したスカラー倍算アルゴリズムＡＲ５１及びＡＲ５２で示すように、バイナリ法では、スカラー値ｄの桁部のビット値ｄｉが“１”の場合、｛Ｑ←２Ｑ＋Ｐ｝の演算式１による桁部演算処理（非ゼロ演算処理）を行い、スカラー値ｄの桁部のビット値ｄｉが“０”の場合、｛Ｑ←２Ｑ｝の演算式２による桁部演算処理（ゼロ演算処理）を行って、それぞれ桁部演算結果を得る必要がある。
【００４４】
このように、バイナリ法に代表されるスカラー倍算アルゴリズムは、桁部の値が“０”の場合に実行するゼロ演算処理と、“１”の場合（“０”以外の場合）に実行する非ゼロ演算処理とは演算処理内容が異なっている。
【００４５】
そこで、本願発明は、スカラー値ｄの桁部のビット値ｄｉが“１”の場合、図１(a)に示すように、ステップＳＰ１１〜ＳＰ１３を実行することにより、｛Ｑ←２Ｑ＋Ｐ｝の演算式１を実現している。ステップＳＰ１１は２倍算処理であり、ステップＳＰ１２及びＳＰ１３は加算処理（第１及び第２の加算処理）である。
【００４６】
一方、スカラー値ｄの桁部のビット値ｄｉが“０”の場合、図１(b)に示すように、ステップＳＰ０１〜ＳＰ０３を実行することにより、｛Ｑ←２Ｑ｝の演算式２を実現している。ステップＳＰ０１は２倍算処理であり、ステップＳＰ０２及びＳＰ０３は加算処理（第１及び第２の加算処理）である。なお、ステップＳＰ０３及びステップＳＰ１３も｛Ｂ←（−Ｐ）｝とした加算処理に含まれる。
【００４７】
このように、ゼロ演算処理（ステップＳＰ０１〜ＳＰ０３）及び非ゼロ演算処理（ステップＳＰ１１〜ＳＰ１３）を共に、倍算器を用いた２倍算処理（ＳＰ０１，ＳＰ１１）、主として加算演算部５を用いた第１の加算処理（ＳＰ０２，ＳＰ１２）、及び主として加算演算部５を用いた第２の加算処理（ＳＰ０３，ＳＰ１３）の順で行い、第２の加算処理の演算結果（ステップＳＰ０３及びＳＰ１３で得られたＱ）を最終的に得られる桁部演算結果としている。
【００４８】
ここで、ステップＳＰ１２及びＳＰ１３並びにステップＳＰ０２及びＳＰ０３においてと、「Ｑ＝Ａ」または「Ｑ＝Ｂ」となった場合は加算処理の代わりに例外的に２倍算処理を行う。実行するアルゴリズムが変動するため、タイミングリークが発生すると考えられるが、スカラー値ｄの桁部の値に起因するものではないため、スカラー値ｄの漏洩には影響しない。また、ステップＳＰ０１〜ＳＰ０３の処理は冗長ではあるが、上記演算式２を成立させるために必要な演算処理のみにより構成されているため、無限遠点Ｏを利用したフォルト挿入によるセーフエラー攻撃の影響も受けない。
【００４９】
以上の説明したように、図１で示したゼロ演算処理（ステップＳＰ０１〜ＳＰ０３）及び非ゼロ演算処理（ステップＳＰ１１〜ＳＰ１３）を採用した本願発明のスカラー倍算装置は、秘密鍵であるスカラー（倍数）値ｄに対する２種類のサイドチャネル攻撃（「タイミングリークによるスカラー値の漏洩」と「フォルト挿入によるセーフエラー攻撃」）を防ぐことができる。
【００５０】
＜実施の形態１＞
図２は実施の形態１のスカラー倍算装置の構成を示すブロック図である。同図に示すように、スカラー倍算装置は、スカラー倍算用演算部１、変換スカラー値生成部３、加算演算部５、２倍算演算部６及び記憶部８を主要構成要素として有している。
【００５１】
加算演算部（ＥＣＡＤＤ演算部）５は直線による加法に基づく加算演算を実行すべく、加算シーケンサ、有限体加算器、有限体減算器及び有限体乗算器（以下、これらを総称して「有限体演算器」と略記する場合あり）、並びに上述した有限体演算器の選択部等を含んで構成されており、２つの入力値（Ｉ１，Ｉ２）の加算演算を実行して加算演算結果（Ｉ１＋Ｉ２）を得る。
【００５２】
２倍算演算部（ＥＣＡＤＤ演算部）６は、直線による加法に基づく２倍算演算を実行すべく、２倍算シーケンサ、有限体加算器、有限体減算器及び有限体乗算器並びに上述した有限体演算器の選択部等を含んで構成されており、１つの入力値（Ｉ）の２倍算演算を実行して２倍算演算結果（２Ｉ）を得る。
【００５３】
スカラー倍算用演算部１は内部の演算部選択機能により、加算演算部５及び２倍算演算部６を選択的に使用して、楕円曲線加法アルゴリズムにおける演算内容の切り替えを行う。
【００５４】
変換スカラー値生成部３はスカラー倍算用演算部１よりスカラー値ｄを受け、スカラー値ｄに対しスカラー値変換処理を行い、変換スカラー値ｂ，変換スカラー値ａ等の変換スカラー値をスカラー倍算用演算部１に出力する。なお、実施の形態１では選択値生成部３を利用することなく、スカラー値ｄをそのまま演算対象としている。
【００５５】
スカラー倍算用演算部１は、入力座標点Ｐ（ｘ，ｙ）及びスカラー値ｄを受け、さらに後述するスカラー倍算アルゴリズムＡＲ１に沿って有限体の計算を行うスカラー倍算処理を実行して、スカラー倍算値（スカラー倍数点）を得る。スカラー倍算用演算部１はスカラー倍算アルゴリズムＡＲ１の実行時において２倍算処理及び加算処理を行う場合、演算部選択機能により、加算演算部５あるいは２倍算演算部６を選択的に使用して、加算演算部５あるいは２倍算演算部６より得られる演算結果情報を記憶部８に出力させる。そして、スカラー倍算用演算部１は当該演算結果情報を記憶部８から取得する。
【００５６】
記憶部８は、上述した加算演算部５あるいは２倍算演算部６からの演算結果情報以外に、入力座標点Ｐ、スカラー値ｄ、及び変換スカラー値ｂ，ａ、並びに後述する倍数テーブル及び桁部演算結果（Ｑ，Ａ）等のスカラー倍算処理に必要な種々の情報をさらに格納する。
【００５７】
実施の形態１では、上述したスカラー倍算用演算部１のみにより、スカラー値ｄを演算用スカラー値とし、演算用スカラー値と入力座標点Ｐとを演算対象として、スカラー倍演算処理を行いスカラー倍算値ｄＰを得るスカラー倍演算機構が構成される。
【００５８】
図３は実施の形態１のスカラー倍算装置が実行するスカラー倍算アルゴリズムＡＲ１を模式的に示す説明図である。なお、図３で示すスカラー倍算アルゴリズムＡＲ１において、１：，２：，…９：は実行ステップ位置を示す。以下、実行ステップ位置をステップＳＴ１〜ＳＴ９と呼ぶ。
【００５９】
なお、図３において、ステップＳＴ３の２倍算関数ＥＣＤＢＬ（Ｑ）はＱの２倍算処理を行うこと示している。したがって、ステップＳＴ３は、具体的には、スカラー倍算用演算部１は演算部選択機能により、２倍算関数ＥＣＤＢＬ（Ｑ）を演算入力情報として２倍算演算部６に１つの入力値Ｑ（演算入力情報）を与え、２倍算演算部６より得られるＱの２倍算演算結果２Ｑが演算結果情報として記憶部８に格納され、記憶部８に格納された２倍算演算結果２Ｑをスカラー倍算用演算部１が取得する。
【００６０】
また、図３において、ステップＳＴ４〜ＳＴ６の加算関数ＥＣＡＤＤ（Ｑ，Ａ（Ｂ））は２つの入力値ＱとＡ（Ｂ）との加算処理を行うことを示している。したがって、ステップＳＴ４，ＳＴ５（ＳＴ６）は、具体的には、スカラー倍算用演算部１は演算部選択機能により、加算関数ＥＣＡＤＤ（Ｑ，Ａ）（あるいはＥＣＡＤＤ（Ｑ，Ｂ））に基づく２つの入力値Ｑ及びＡ（Ｂ）（演算入力情報）を加算演算部５に与え、加算演算部５により得られるＱとＡとの加算演算結果（Ｑ＋Ａ）あるいはＱとＢとの加算演算結果（Ｑ＋Ｂ）が演算結果情報として記憶部８に格納される。そして、記憶部８に格納された加算演算結果（Ａ＋Ｂ）あるいは（Ｑ＋Ｂ）をスカラー倍算用演算部１が取得する。
【００６１】
ただし、加算関数ＥＣＡＤＤ（Ｑ，Ａ（Ｂ））おいてＱ＝ＡあるいはＱ＝Ｂの場合、演算部選択機能は例外的に、２倍算演算部６に一つの入力値Ｑを与え、倍算演算部６より得られるＱの２倍算演算結果２Ｑが演算結果情報となる。
【００６２】
図３に示すように、スカラー倍算アルゴリズムＡＲ１では、ステップＳＴ３で図１のステップＳＰ１１（あるいはステップＳＰ０１）を実行し、ステップＳＴ４で図１のステップＳＰ１２、ステップＳＴ５で図１のステップＳＰ０２を実行し、ステップＳＴ６で図１のステップＳＰ１３（あるいはステップＳＰ０３）を実行するようにしている。
【００６３】
図４は実施の形態１のスカラー倍算装置によるスカラー倍算アルゴリズムＡＲ１の実行例を模式的に示す説明図である。以下、スカラー倍算用演算部１が実行するスカラー倍算アルゴリズムＡＲ１の概要を、図３及び図４を参照して説明する。
【００６４】
(1)スカラー倍算装置に入力座標点Ｐとスカラー値ｄを入力し、入力座標点Ｐをスカラー倍算用演算部１に取り込むとともに、必要に応じて記憶部８に格納する（図３のInput：…に相当）。
【００６５】
(2)上記処理(1)の際、Left to Rightバイナリ法のアルゴリズムで計算を行うため、スカラー値ｄに関しｓ個の桁部がそれぞれ１ビット情報を有する表記とする。
【００６６】
したがって、図３に示すように、スカラー値ｄ＝｛ｄｓ−１，ｄｓ−２，…，ｄ１，ｄ０｝２で表される。例えば、図４(a)に示すように、ｓ＝１２とした、スカラー値ｄ“１０１００１１１１０１１”２（＝（２６８３）１０）の値を有する、ｄ１１〜ｄ０がスカラー倍算用演算部１内に取り込まれ、必要に応じて記憶部８に格納される。
【００６７】
(3)１つ上位の桁部における桁部演算結果Ｑ（初期値は無限遠点Ｏ）の２倍算値（２倍点）２Ｑを計算し、記憶部８に格納する（図３のステップＳＴ３に相当）。
【００６８】
例えば、ＭＳＢ（最上位（ｓ−１））の桁部の値ｄ１１に対する演算処理Ｐ１では、桁部演算結果Ｑの初期値は無限遠点Ｏであるため、２倍算関数ＥＣＤＢＬ（Ｑ）の演算結果も無限遠点Ｏとなり、ステップＳＴ３が実行されない場合と実質的に同じになる（図４では図示せず）。
【００６９】
また、ＭＳＢ−１（＝ｓ−２）の桁部の値ｄ１０に対する演算処理Ｐ２（１行目）では、１つ上位の桁部の演算処理Ｐ１の桁部演算結果ＱがＰであったため、Ｐの２倍算値２Ｐ（＝Ｐ×２）が得られる。
【００７０】
(4)ｄｉ（ｉ＝（ｓ−１）〜０のいずれか）が“１”の場合、Ａ＝２Ｐとして加算処理（Ｑ＋Ａ）（第１の加算処理）を実行し（ステップＳＴ４に相当）、ｄｉが“０”の場合、Ａ＝Ｐとして加算処理（Ｑ＋Ａ）（第１の加算処理）を実行する（図３のステップＳＴ５に相当）。
【００７１】
例えば、ｄ９（＝“１”）に対して行う演算処理Ｐ３（２行目）では、Ｑ（＝４Ｐ）＋２Ｐの加算処理が実行され、ｄ８（＝“０”）に対して行う演算処理Ｐ４（２行目）では、Ｑ（＝１０Ｐ）＋Ｐの加算処理が実行される。
【００７２】
(5)Ｂ＝−Ｐとして加算処理（第２の加算処理）を実行して、ｉ桁の桁部（ｄｉ）の桁部演算結果Ｑを得る（ステップＳＴ６に相当）。
【００７３】
例えば、ｄ９（＝“１”）に対して行う演算処理Ｐ３（３行目）では、Ｑ（＝６Ｐ）＋（−Ｐ）の加算処理が実行される。
【００７４】
(6)桁数ｉを“１”繰り下げた後（ステップＳＴ７に相当）、上記処理(3)〜(5)を繰り返す。
【００７５】
そして、スカラー倍算用演算部１は、最終的にｉ＝０のとき、ｄ０に対する演算処理Ｐ１２の第２の加算処理（処理(5)）によって得られるＬＳＢ（最下位“０”）の桁部の桁部演算結果Ｑ＝２６８３Ｐが、スカラー倍算値ｄＰとなる。
【００７６】
このように、演算処理Ｐ１〜Ｐ１２のうち、最初の演算処理Ｐ１を除いて、ｄｉの値の“０”，“１”に関わらず、２倍算処理（図３のステップＳＴ３）→第１の加算処理（図３のステップＳＴ４あるいはＳＴ５）→第２の加算処理（図３のステップＳＴ６）の順番で１１回実行するため、ダミー演算を行うことなく処理時間を一定にすることができる。
【００７７】
（効果等）
上述したように、実施の形態１のスカラー倍算装置において、スカラー倍算用演算部１によって行うスカラー倍演算処理は、スカラー値ｄを構成する複数の桁部に対応して実行され、各々が桁部演算結果を得る複数の桁部演算処理（図４(b)の演算処理Ｐ１〜Ｐ１２に相当）を含んでいる。そして、複数の桁部演算処理の実行により、隣接する桁部間で上位から下位に桁部演算結果Ｑを記憶部８を介して伝搬しつつ、最上位（ｎ−１）から最下位（０）にかけて桁部単位に桁部演算結果Ｑを順次得て、最下位の桁部に対応する桁部演算処理（図４(b)の演算処理Ｐ１２に相当）より得られる桁部演算結果Ｑをスカラー倍算値ｄＰとして取得している。
【００７８】
上述した複数の桁部演算処理はそれぞれ、加算演算部５及び２倍算演算部６を用いて実行され、桁部のｄｉが“０”の場合はゼロ演算処理（図２のステップＳＰ０１〜ＳＰ０３）を実行して桁部演算結果Ｑを取得し、“１”の場合（“０”以外の場合）は上記ゼロ演算処理と異なる演算内容の非ゼロ演算処理（図２のステップＳＰ１１〜ＳＰ１３）を実行して桁部演算結果Ｑを取得している。
【００７９】
そして、実施の形態１のスカラー倍算装置は、上記ゼロ演算処理及び上記非ゼロ演算処理を共に、２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、第２の加算処理の演算結果を桁部演算結果としたことを特徴としている。
【００８０】
実施の形態１のスカラー倍算装置は、上記特徴を有することにより、ゼロ演算処理及び非ゼロ演算処理間で共通の演算処理（２倍算処理、第１及び第２の加算処理）の実行後にはじめて桁部演算結果を得ているため、スカラー値ｄ（演算用スカラー値）の桁部の値が“０”か非“０”かによって演算処理時間の変化が生じない。したがって、ゼロ演算処理及び非ゼロ演算処理間における演算処理時の差異に基づくタイミングリークを確実に回避することができる。
【００８１】
さらに、実施の形態１において、ゼロ演算処理及び非ゼロ演算処理間で実行される２倍算処理、第１及び第２の加算処理は全て桁部演算結果Ｑを得るために必要な演算処理であり、演算結果が利用されないダミー演算処理ではない。したがって、ダミー演算処理に対するセーフエラー攻撃が実行されることもない。
【００８２】
加えて、スカラー倍算処理以外のサイドチャネル攻撃用の演算処理を特に必要としていないため、実施の形態１のスカラー倍算装置を比較的簡単な構成で実現できる。
【００８３】
その結果、タイミングリークの検知及びセーフエラー攻撃を含むサイドチャネル攻撃に強く、セキュリティー性が高いスカラー倍演算処理を実行する実施の形態１のスカラー倍算装置を比較的簡単な構成で得ることができる。
【００８４】
なお、実施の形態１のスカラー倍算装置は、外部より入力されるスカラー値ｄ（入力スカラー値）を、スカラー倍算用演算部１がスカラー倍算処理を行うための演算対象となる演算用スカラー値として用いている。したがって、演算用スカラー値（スカラー値ｄ）を構成する複数の桁部はそれぞれ１ビットの情報量を有している。また、図１のステップＳＰ０１あるいはステップＳＰ１１として実行する２倍算処理は２倍算演算部６を１回用いて１回倍算値を得る処理となる。
【００８５】
このように、実施の形態１のスカラー倍算装置は、スカラー値ｄ（入力スカラー値）をそのまま演算用スカラー値として用いるバイナリ法を採用したスカラー倍演算処理をセキュリティー性を高めて実行することができる効果を奏する。
【００８６】
＜実施の形態２＞
実施の形態２は、Window法を採用したスカラー倍算装置である。Window法とは、スカラー倍数値をＭビットのウィンドウ形式に変換して得られる変換スカラー値を演算用スカラー値としてスカラー倍算処理を行う加算鎖アルゴリズムの一種である。Window法は楕円曲線演算をバイナリ法より高速に行うことができる利点を奏している。
【００８７】
（Window法の概要）
Window法のアルゴリズムにおけるスカラー倍算処理は、「Window変換」（スカラー値変換処理）、「事前計算」（テーブル作成処理）、及び「本計算」（スカラー倍算本処理）の３つの処理に分類される。
【００８８】
図５はWindow法におけるスカラー値変換処理の（Window）変換アルゴリズムＡＲ６１を模式的に示す説明図である。なお、図５で示す変換アルゴリズムＡＲ６１において、１：，２：，…１２：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１２と呼ぶ。
【００８９】
図５のステップＳＴ３において、ｃ［ｗ−１：０］は変数ｃにおける最下位ｗビットを意味する。
【００９０】
図５で示す変換アルゴリズムＡＲ６１を実行することにより、スカラー値ｄから、各々がＭビット（＝ｗ≧２）の情報量の複数の桁部を有する変換スカラー値ｂを得ることができる。
【００９１】
例えば、スカラー値ｄが“１０１００１１１１０１１”２（＝（２６８３）であり、Ｍ＝ｗ＝４の場合、スカラー値変換処理を実行することにより、スカラー値ｄを４ビット単位にWindow変換して、変換スカラー値ｂ（データｂ２＝“１０１０”、データｂ１＝“０１１１”）、データｂ０＝“１０１１”）を得ることができる。すなわち、変換スカラー値ｂは、データｂ２〜データｂ０を有する３つの桁部から構成される。
【００９２】
図６はWindow法における従来のテーブル作成処理である事前計算アルゴリズムＡＲ６２を模式的に示す説明図である。なお、図６で示す事前計算アルゴリズムＡＲ６２において、１：，２：，…５：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ５と呼ぶ。
【００９３】
図６で示す事前計算アルゴリズムＡＲ６２を実行することにより、入力座標点Ｐを整数倍して得られる整数倍座標点を複数種計算し、｛テーブルＴ１〜Ｔβ｝として記憶部８内に格納される。
【００９４】
図７はWindow法における従来のスカラー倍算本処理である本計算アルゴリズムＡＲ６３を模式的に示す説明図である。なお、図７で示す本計算アルゴリズムＡＲ６３において、１：，２：，…１１：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１１と呼ぶ。
【００９５】
このように、変換アルゴリズムＡＲ６１、事前計算アルゴリズムＡＲ６２及び本計算アルゴリズムＡＲ６３からなるスカラー倍算処理を実行するのが従来のWindow法である。
【００９６】
図７に示すように、従来のスカラー倍算本処理では、変換スカラー値ｂの桁部の値ｂｉが非“０”の場合はステップＳＴ７及びＳＴ８が実行され、値ｂｉが“０”の場合はステップＳＴ７及びＳＴ８が実行されない。
【００９７】
したがって、従来のWindow法に対するサイドチャネル攻撃については、桁部の値（Window値）であるｂｉが“０”と非“０”の場合で処理が分岐しているため、タイミングリークを完全に隠蔽することができない問題点があった。
【００９８】
（構成）
上記問題点の解決を図りつつ、Window法を採用したのが実施の形態２のスカラー倍算装置である。
【００９９】
装置構成は図２で示した実施の形態１と同様であるが、変換スカラー値生成部３が上述したスカラー値変換処理を行い、スカラー値ｄから変換スカラー値ｂを得る点、スカラー倍算用演算部１が変換スカラー値ｂを演算用スカラー値として、後述するテーブル作成処理及びスカラー倍算本処理を行う点が大きく異なる。
【０１００】
そして、実施の形態２において、スカラー倍算用演算部１及び変換スカラー値生成部３により、変換スカラー値ｂを演算用スカラー値とし、演算用スカラー値と入力座標点Ｐとを演算対象として、スカラー倍演算処理を行いスカラー倍算値ｄＰを得るスカラー倍演算機構が構成される。
【０１０１】
変換スカラー値生成部３はスカラー値ｄを受け、スカラー値ｄに基づき、変換アルゴリズムＡＲ１１（図５で示した変換アルゴリズムＡＲ６１と同じ）によるスカラー値変換処理を実行して変換スカラー値ｂを取得し、取得した変換スカラー値ｂをスカラー倍算用演算部１に出力する。
【０１０２】
スカラー倍算用演算部１は、後述するテーブル作成処理を実行して入力座標点Ｐを整数倍して得られる整数倍座標点を複数種有する倍数テーブルを作成して記憶部８に格納する。
【０１０３】
そして、スカラー倍算用演算部１は、変換スカラー値生成部３から変換スカラー値ｂを受け、変換スカラー値ｂ及び入力座標点Ｐを演算対象として後述するスカラー倍算本処理を実行してスカラー倍算値ｄＰを得る。なお、変換スカラー値ｂ及び入力座標点Ｐは必要に応じて記憶部８に格納される。
【０１０４】
（アルゴリズム）
図８はWindow法における実施の形態２のテーブル作成処理である事前計算アルゴリズムＡＲ１２を模式的に示す説明図である。なお、図８で示す事前計算アルゴリズムＡＲ１２において、１：，２：，…５：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ５と呼ぶ。
【０１０５】
図８で示す事前計算アルゴリズムＡＲ１２を実行することにより、入力座標点Ｐを整数倍して得られる整数倍座標点を複数個計算し、倍数テーブル｛Ｔ２〜Ｔβ｝として記憶部８内に格納される。
【０１０６】
図９はWindow法における実施の形態２のスカラー倍算本処理である本計算アルゴリズムＡＲ１３を模式的に示す説明図である。なお、図９で示す本計算アルゴリズムＡＲ１３において、１：，２：，…１３：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１３と呼ぶ。
【０１０７】
図１０は実施の形態２のスカラー倍算装置による本計算アルゴリズムＡＲ１３の実行例を模式的に示す説明図である。以下、スカラー倍算用演算部１が実行する本計算アルゴリズムＡＲ１３の概要を、図９及び図１０を参照して説明する。なお、図１０で示す例では、Window幅Ｍである各桁部のビット数を４ビットとしている。
【０１０８】
(1)スカラー倍算装置に入力座標点Ｐとスカラー値ｄ（入力スカラー値）を入力し、入座標点Ｐをスカラー倍算用演算部１に取り込むとともに、必要に応じて記憶部８に格納する。一方、変換スカラー値生成部３は変換アルゴリズムＡＲ１１を採用したスカラー値変換処理を実行することにより、スカラー値ｄを変換スカラー値ｂに変換し、変換スカラー値ｂをスカラー倍算用演算部１に出力する（図９のInput：…に相当）。
【０１０９】
(2)上記処理(1)の際、Window法のアルゴリズムで計算を行うため、変換スカラー値ｂに関しｎ個の桁部がそれぞれ４ビット（Ｍビット）情報を有する表記とする。
【０１１０】
図９に示すように、変換スカラー値ｂ＝｛ｂｎ−１，…，ｂ０｝で表される。例えば、図１０(a)に示すように、ｎ＝３とした、変換スカラー値ｂ（データｂ２＝１０、データｂ１＝７、データｂ０＝１１）の値を有する、ｂ２〜ｂ０となる。
【０１１１】
(3)１つ上位の桁部における桁部演算結果Ａ（初期値“無限遠点Ｏ”）の２ｗ倍点（ｗ回倍算値）である２ｗＡを計算し、記憶部８に格納する（図９のステップＳＴ２〜ＳＴ４に相当）。
【０１１２】
例えば、ＭＳＢ（最上位（ｎ−１））の桁部の値ｂ２に対する演算処理Ｐ１では、桁部演算結果Ａの初期値は無限遠点Ｏであるため、２倍算関数ＥＣＤＢＬ（Ａ）の演算結果も無限遠点Ｏとなり、ステップＳＴ２〜ＳＴ４が実行されない場合と実質的に同じになる（図１０では図示せず）。
【０１１３】
また、ＭＳＢ−１（＝ｎ−２）の桁部の値ｂ１に対する演算処理Ｐ２（１〜４行目）では、１つ上位の桁部の演算処理Ｐ１の桁部演算結果Ａが１０Ｐであったため、Ｐの２倍算を４（＝Ｍ＝ｗ）回繰り返して行う４回倍算値である倍算値１６０Ｐ（＝１０Ｐ×２×２×２×２）が得られる。
【０１１４】
(4)ｂｉ（ｉ＝（ｎ−１）〜０のいずれか）が非“０”の場合、Ｂ＝ｅＰとして決定した（図９のステップＳＴ５及びＳＴ６に相当）後、加算処理（Ａ＋Ｂ）（第１の加算処理）を実行する（図９のステップＳＴ１０に相当）。
【０１１５】
なお、ｅはｂｉの値により選択される入力座標点Ｐの倍数値を意味し、ｅ＝（ｂｉ＋１）となる。すなわち、ｂｉが非“０”の場合、事前計算アルゴリズムＡＲ１２に沿ったテーブル作成処理によって得られた倍数テーブル｛テーブルＴ２〜Ｔβ｝のうち、Ｔｂｉ−１に合致する値が選択される。このように、第１の加算処理は非ゼロ演算処理の実行時に倍数テーブルを用いて行われる。
【０１１６】
例えば、ｂ１（＝“７”）に対して行う演算処理Ｐ２（５行目）では、ｅ＝ｂ１＋１＝８となり、Ａ（＝１６０Ｐ）＋８Ｐの加算処理が実行される。
【０１１７】
一方、ｂｉが“０”の場合、Ｂ＝Ｐとして決定した（図９のステップＳＴ７及びＳＴ８に相当）後、加算処理（Ａ＋Ｂ）（第１の加算処理）を実行する（図９のステップＳＴ１０に相当）。
【０１１８】
(5)−Ｐを用いた加算処理（第２の加算処理）を実行して、ｉ桁の桁部（ｂｉ）の桁部演算結果Ａを得る（図９のステップＳＴ１１に相当）。
【０１１９】
例えば、ｂ１に対して行う演算処理Ｐ２（６行目）では、Ａ（＝１６８Ｐ）＋（−Ｐ）の加算処理が実行される。
【０１２０】
(6)桁数ｉを“１”繰り下げた後（ステップＳＴ１及びＳＴ１２に相当）、上記処理(3)〜(5)を繰り返す。
【０１２１】
そして、スカラー倍算用演算部１は、最終的にｉ＝０のとき、ｂ０に対する演算処理Ｐ３の第２の加算処理（処理(5)）によって得られるＬＳＢ（最下位“０”）桁部の桁部演算結果Ａ＝２６８３Ｐを、スカラー倍算値ｄＰとして出力する（図９のステップＳＴ１３に相当）。
【０１２２】
このように、実施の形態２のスカラー倍算装置は、スカラー倍算処理として、変換アルゴリズムＡＲ１１を採用したスカラー値変換処理、事前計算アルゴリズムＡＲ１２を採用したテーブル作成処理及び本計算アルゴリズムＡＲ１３を採用したスカラー倍算本処理を実行している。
【０１２３】
したがって、図１０(b)に示すように、演算処理Ｐ１〜Ｐ３のうち、最初の演算処理Ｐ１を除いて、ｂｉの値の“０”，非“０”に関わらず、Ｍ（＝ｗ）回繰り返して行う２倍算処理（図９のステップＳＴ２〜ＳＴ４）→第１の加算処理（図９のステップＳＴ５、ＳＴ６及びＳＴ１０、あるいはＳＴ７、ＳＴ８及びＳＴ１０）→第２の加算処理（図９のステップＳＴ１１）の順番で２回実行するため、ダミー演算を行うことなく処理時間を一定にすることができる。
【０１２４】
（効果等）
このように、実施の形態２のスカラー倍算装置において、スカラー倍算用演算部１によって行うスカラー倍演算処理は、変換スカラー値ｂを構成する複数の桁部に対応して実行され、各々が桁部演算結果を得る複数の桁部演算処理（図１０(b)の演算処理Ｐ１〜Ｐ３に相当）を含んでいる。そして、複数の桁部演算処理の実行により、隣接する桁部間で上位から下位に桁部演算結果Ａを記憶部８を介して伝搬しつつ、最上位（ｎ−１）から最下位（０）にかけて桁部単位に桁部演算結果Ａを順次得て、最下位の桁部に対応する桁部演算処理（図１０(b)の演算処理Ｐ３に相当）より得られる桁部演算結果Ａをスカラー倍算値ｄＰとして取得する。
【０１２５】
上述した複数の桁部演算処理はそれぞれ、加算演算部５及び２倍算演算部６を用いて実行され、桁部のｂｉが“０”の場合にゼロ演算処理（図９のステップＳＴ８を固有の実行とする処理）を実行して桁部演算結果Ａを取得し、非“０”の場合は上記ゼロ演算処理と異なる演算内容の非ゼロ演算処理（図９のステップＳＴ６を固有の実行とする処理）を実行して桁部演算結果Ａを取得している。
【０１２６】
そして、実施の形態２のスカラー倍算装置は、実施の形態１と同様、上記ゼロ演算処理及び上記非ゼロ演算処理を共に、（Ｍ（＝ｗ）回繰り返して行う）２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、第２の加算処理の演算結果を桁部演算結果としたことを特徴としている。
【０１２７】
実施の形態２のスカラー倍算装置は、上記特徴を有することにより、実施の形態１と同様、ゼロ演算処理及び非ゼロ演算処理間における演算処理時の差異に基づくタイミングリークを確実に回避することができる。
【０１２８】
さらに、実施の形態２において、ゼロ演算処理及び非ゼロ演算処理間で実行されるＭ（＝ｗ）回繰り返して行う２倍算処理、第１及び第２の加算処理は全て桁部演算結果Ａを得るために必要な演算処理であり、演算結果が利用されないダミー演算処理ではない。したがって、ダミー演算処理に対するセーフエラー攻撃が実行されることもない。
【０１２９】
加えて、スカラー倍算処理以外のサイドチャネル攻撃用の演算処理を特に必要としていないため、実施の形態２のスカラー倍算装置を比較的簡単な構成で実現できる。
【０１３０】
その結果、サイドチャネル攻撃に強く、セキュリティー性が高いスカラー倍演算処理を実行する実施の形態２のスカラー倍算装置を得ることができる。
【０１３１】
なお、実施の形態２のスカラー倍算装置は、外部より入力されるスカラー値ｄ（入力スカラー値）がスカラー値変換処理によって変換された変換スカラー値ｂをスカラー倍算処理の演算対象となる演算用スカラー値として用いている。したがって、演算用スカラー値（変換スカラー値ｂ）を構成する複数の桁部はそれぞれＭ（＝ｗ）ビットの情報量を有している。また、図９のステップステップＳＴ２〜ＳＴ４として実行する、２倍算処理は２倍算演算部６をＭ回用いてＭ回倍算値を得る処理となる。
【０１３２】
また、第１の加算処理は、非ゼロ演算処理の実行時にテーブル作成処理によって作成された倍数テーブル｛Ｔ２〜Ｔβ｝を用いて行っている。
【０１３３】
このように、実施の形態２のスカラー倍算装置は、変換スカラー値ｂを演算用スカラー値として用いるWindow法を採用したスカラー倍演算処理をセキュリティー性を高めて実行することができる効果を奏する。
【０１３４】
さらに、実施の形態２のスカラー倍算装置は、バイナリ法を採用した実施の形態１に比べて加算処理回数を少なくして処理速度を高めることができる効果も奏する。
【０１３５】
＜実施の形態３＞
実施の形態３は、ＮＡＦ法を採用したスカラー倍算装置である。ＮＡＦ法とはスカラー値ｄをＮＡＦ（符号付の非隣接形式）に変換して得られる変換スカラー値を演算用スカラー値としてスカラー倍算処理を行うアルゴリズムの一種である。ＮＡＦ法は加算鎖の計算をバイナリ法より高速に行える可能性が高い利点を奏している。
【０１３６】
（ＮＡＦ法の概要）
ＮＡＦ法のアルゴリズムにおけるスカラー倍算処理は、「ＮＡＦ変換」（スカラー値変換処理）、及び「本計算」（スカラー倍算本処理）の２つの処理に分類される。
【０１３７】
図１１はＮＡＦ法におけるスカラー値変換処理の（ＮＡＦ）変換アルゴリズムＡＲ７１を模式的に示す説明図である。なお、図１１で示す変換アルゴリズムＡＲ７１において、１：，２：，…１６：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１６と呼ぶ。
【０１３８】
図１１のステップＳＴ３においてｃ［０］は変数ｃの最下位ビットを示し、ステップＳＴ４においてｃ［１：０］は変数ｃにおける最下位２ビットを意味する。
【０１３９】
図１１で示す変換アルゴリズムＡＲ７１を実行することにより、スカラー値ｄから、各々が１ビットの情報量の複数の桁部を有する変換スカラー値ａを得ることができる。ただし、変換スカラー値ａを構成する複数の桁部の値ａｉは正負の情報を含んでいる。値ａｉの正負決定処理は、図１１のステップＳＴ４〜ＳＴ７の処理で行われる。
【０１４０】
例えば、スカラー値ｄが“１０１００１１１１０１１”２（＝（２６８３））の場合、変換アルゴリズムＡＲ７１を採用したスカラー値変換処理を実行することにより、スカラー値ｄを１ビット単位にＮＡＦ変換して、変換スカラー値ａ＝“１０１０１００００（−１）０（−１）”を得ることができる。すなわち、変換スカラー値ａは、データａ１１〜データａ０を有する１２個の桁部から構成される。
【０１４１】
図１２はＮＡＦ法における従来のスカラー倍算本処理である本計算アルゴリズムＡＲ７３を模式的に示す説明図である。なお、図１２で示す本計算アルゴリズムＡＲ７３において、１：，２：，…１０：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１０と呼ぶ。
【０１４２】
このように、変換アルゴリズムＡＲ７１、及び本計算アルゴリズムＡＲ７３からなるスカラー倍算処理を実行するのが従来のＮＡＦ法である。
【０１４３】
図１２に示すように、従来のスカラー倍算本処理では、変換スカラー値ａの桁部の値ａｉが非“０”の場合はステップＳＴ５あるいはステップＳＴ７を実行している。すなわち、ａｉ＝“１”の場合はステップＳＴ５が実行され、ａｉ＝“−１”の場合はステップＳＴ７が実行される。このように、ＮＡＦ法では、非ゼロ演算処理として互いに異なる２つの非ゼロ演算処理（第１及び第２の非ゼロ演算処理）を有している。
【０１４４】
一方、値ａｉが“０”の場合はステップＳＴ５及びＳＴ７は共に実行されない。
【０１４５】
したがって、従来のＮＡＦ法に対するサイドチャネル攻撃については、桁部の値であるａｉが“０”と非“０”の場合で処理が分岐しているため、タイミングリークを完全に隠蔽することができない問題点があった。
【０１４６】
（構成）
上記問題点の解決を図りつつ、ＮＡＦ法を採用したのが実施の形態３のスカラー倍算装置である。
【０１４７】
装置構成は図２で示した実施の形態１と同様であるが、変換スカラー値生成部３が上述したスカラー値変換処理を行い、スカラー値ｄから変換スカラー値ａを得る点、スカラー倍算用演算部１が変換スカラー値ａを演算用スカラー値として、後述するスカラー倍算本処理を行う点が大きく異なる。
【０１４８】
そして、実施の形態３において、スカラー倍算用演算部１及び変換スカラー値生成部３により、変換スカラー値ａを演算用スカラー値とし、演算用スカラー値と入力座標点Ｐとを演算対象として、スカラー倍演算処理を行いスカラー倍算値ｄＰを得るスカラー倍演算機構が構成される。
【０１４９】
変換スカラー値生成部３はスカラー値ｄを受け、スカラー値ｄに基づき、変換アルゴリズムＡＲ２１（図１１で示した変換アルゴリズムＡＲ７１と同じ）によるスカラー値変換処理を実行して変換スカラー値ａを取得し、変換スカラー値ａをスカラー倍算用演算部１に出力する。
【０１５０】
そして、スカラー倍算用演算部１は、変換スカラー値生成部３から取得した変換スカラー値ａに基づき、変換スカラー値ａ及び入力座標点Ｐを演算対象として後述するスカラー倍算本処理を実行してスカラー倍算値ｄＰを得る。なお、変換スカラー値ａ及び入力座標点Ｐは必要に応じて記憶部８に格納される。
【０１５１】
（アルゴリズム）
図１３はＮＡＦ法における実施の形態３のスカラー倍算本処理である本計算アルゴリズムＡＲ２３を模式的に示す説明図である。なお、図１３で示す本計算アルゴリズムＡＲ２３において、１：，２：，…１４：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１４と呼ぶ。
【０１５２】
図１４は実施の形態３のスカラー倍算装置による本計算アルゴリズムＡＲ２３の実行例を模式的に示す説明図である。以下、スカラー倍算用演算部１が実行する本計算アルゴリズムＡＲ２３の概要を、図１３及び図１４を参照して説明する。
【０１５３】
(1)スカラー倍算装置に入力座標点Ｐとスカラー値ｄ（入力スカラー値）を入力し、入座標点Ｐをスカラー倍算用演算部１内に取り込むとともに、必要に応じて記憶部８格納する。一方、変換スカラー値生成部３は変換アルゴリズムＡＲ２１を採用したスカラー値変換処理を実行することにより、スカラー値ｄを変換スカラー値ａに変換し、変換スカラー値ａをスカラー倍算用演算部１に出力する（図１３のInput：…に相当）。
【０１５４】
(2)上記処理(1)の際、ＮＡＦ法のアルゴリズムで計算を行うため、変換スカラー値ａに関しｎ個の桁部がそれぞれ正負を含む１ビット情報を有する表記とする。
【０１５５】
図１３に示すように、変換スカラー値ａ＝｛ａｎ−１，…，ａ０｝で表される。例えば、図１４(a)に示すように、ｎ＝１２とした、変換スカラー値ａ＝“１０１０１００００（−１）０（−１）”の値を有する、ａ１１〜ａ０がスカラー倍算用演算部１に出力される。
【０１５６】
(3)１つ上位の桁部における桁部演算結果Ａ（初期値“０”）の２倍算点である２Ａを計算し、記憶部８に格納する（図１３のステップＳＴ３に相当）。
【０１５７】
例えば、ＭＳＢ（最上位（ｎ−１））の桁部の値ａ１１に対する演算処理Ｐ１では、桁部演算結果Ａの初期値は無限遠点Ｏ”であるため、２倍算関数ＥＣＤＢＬ（Ａ）の演算結果も無限遠点Ｏとなり、ステップＳＴ３が実行されない場合と実質的に同じになる（図１４では図示せず）。
【０１５８】
また、ＭＳＢ−１（＝ｎ−２）の桁部の値ａ１０に対する演算処理Ｐ２（１行目）では、１つ上位の桁部の演算処理Ｐ１の桁部演算結果ＡがＰであったため、Ｐの２倍算を行って倍算値２Ｐ（＝Ｐ×２）が得られる。
【０１５９】
(4)ａｉ（ｉ＝（ｎ−１）〜０のいずれか）が非“０”で正の場合は｛Ｂ＝２Ｐ，Ｃ＝−Ｐ｝に設定し（図１３のステップＳＴ５）、非“０”で負の場合は｛Ｂ＝−２Ｐ，Ｃ＝Ｐ｝に設定した（図１３のステップＳＴ７）後、加算処理（Ａ＋Ｂ）（第１の加算処理）を実行する（図１３のステップＳＴ１１に相当）。さらに、その後、加算処理（Ａ＋Ｃ）（第２の加算処理）を実行する（図１３のステップＳＴ１２に相当）。
【０１６０】
例えば、ａ９（＝“１”）に対して行う演算処理Ｐ３（２行目）では、第１の加算処理として、Ａ（＝４Ｐ）＋Ｂ（＝２Ｐ）の加算処理が実行され、演算処理Ｐ３（３行目）では、第２の加算処理として、Ａ（＝６Ｐ）＋Ｂ（＝−Ｐ）の加算処理が実行される。
【０１６１】
また、ａ２（＝“−１”）に対して行う演算処理Ｐ１０（２行目）では、第１の加算処理として、Ａ（＝６７２Ｐ）＋Ｂ（＝−２Ｐ）の加算処理が実行され、演算処理Ｐ１０（３行目）では、第２の加算処理として、Ａ（＝６７０Ｐ）＋Ｂ（＝Ｐ）の加算処理が実行される。
【０１６２】
一方、ａｉが“０”の場合、｛Ｂ＝Ｐ，Ｃ＝−Ｐ｝に設定した（図１３のステップＳＴ９）後、加算処理（Ａ＋Ｂ）（第１の加算処理）を実行し（図１３のステップＳＴ１１に相当）、さらに、その後、加算処理（Ａ＋Ｃ）（第２の加算処理）を実行する（図１３のステップＳＴ１２に相当）。
【０１６３】
例えば、ａ１０（＝“０”）に対して行う演算処理Ｐ２（２行目）では、第１の加算処理として、Ａ（＝２Ｐ）＋Ｂ（＝Ｐ）の加算処理が実行され、演算処理Ｐ２（３行目）では、第２の加算処理として、Ａ（＝３Ｐ）＋Ｂ（＝−Ｐ）の加算処理が実行される。
【０１６４】
上述した第２の加算処理（図１３のステップＳＴ１１に相当）を実行した後、ｉ桁の桁部（ａｉ）の桁部演算結果Ａを得ることができる。桁部演算結果Ａは適宜記憶部８に格納される。
【０１６５】
(5)桁数ｉを“１”繰り下げた後（ステップＳＴ２及びＳＴ１３に相当）、上記処理(3)〜(4)を繰り返す。
【０１６６】
そして、スカラー倍算用演算部１は、最終的にｉ＝０のとき、ａ０に対する演算処理Ｐ１２の第２の加算処理（処理(4)）によって得られるＬＳＢ（最下位“０”）桁部の桁部演算結果Ａ＝２６８３Ｐを、スカラー倍算値ｄＰとして出力する（図１３のステップＳＴ１４に相当）。
【０１６７】
このように、実施の形態３のスカラー倍算装置は、スカラー倍算処理として、変換アルゴリズムＡＲ２１を採用したスカラー値変換処理、及び本計算アルゴリズムＡＲ２３を採用したスカラー倍算本処理を実行している。
【０１６８】
したがって、演算処理Ｐ１〜Ｐ１２のうち、最初の演算処理Ｐ１を除いて、ａｉの値の“０”，非“０”（正，負）に関わらず、２倍算処理（図１３のステップＳＴ３）→第１の加算処理（図１３のステップＳＴ５及びＳＴ１１、ＳＴ７及びＳＴ１１あるいはＳＴ９及びＳＴ１１）→第２の加算処理（図１３のステップＳＴ５及びＳＴ１２、ＳＴ７及びＳＴ１２あるいはＳＴ９及びＳＴ１２）の順番で１１回実行するため、ダミー演算を行うことなく処理時間を一定にすることができる。
【０１６９】
（効果等）
このように、実施の形態３のスカラー倍算装置において、スカラー倍算用演算部１によって行うスカラー倍演算処理は、変換スカラー値ａを構成する複数の桁部に対応して実行され、各々が桁部演算結果を得る複数の桁部演算処理（図１４(b)の演算処理Ｐ１〜Ｐ１２に相当）を含んでいる。そして、複数の桁部演算処理の実行により、隣接する桁部間で上位から下位に桁部演算結果Ａを記憶部８を介して伝搬しつつ、最上位（ｎ−１）から最下位（０）にかけて桁部単位に桁部演算結果Ａを順次得て、最下位の桁部に対応する桁部演算処理（図１４(b)の演算処理Ｐ１２に相当）より得られる桁部演算結果Ａをスカラー倍算値ｄＰとして取得する。
【０１７０】
上述した複数の桁部演算処理はそれぞれ、加算演算部５及び２倍算演算部６を用いて実行され、スカラー倍算用演算部１は、桁部のａｉが“０”の場合にゼロ演算処理（図１３のステップＳＴ９を固有の実行とする処理）を実行して桁部演算結果Ａを取得し、非“０”の場合は上記ゼロ演算処理と異なる演算内容の非ゼロ演算処理（図１３のステップＳＴ５あるいはＳＴ７を固有の実行とする処理）を実行して桁部演算結果Ａを取得している。
【０１７１】
そして、実施の形態３のスカラー倍算装置は、実施の形態１と同様、上記ゼロ演算処理及び上記非ゼロ演算処理を共に、２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、第２の加算処理の演算結果を桁部演算結果としたことを特徴としている。
【０１７２】
さらに、実施の形態３のスカラー倍算装置は、非ゼロ演算処理として桁部の値ａｉが正の場合に実行される第１の非ゼロ演算処理（図１３のステップＳＴ３，ＳＴ５、ＳＴ１１及びＳＴ１２に相当）と、桁部の値ａｉが負の場合に実行される第２の非ゼロ演算処理（図１３のステップＳＴ３，ＳＴ７，ＳＴ１１及びＳＴ１２に相当）とを含んでいる。
【０１７３】
そして、実施の形態３のスカラー倍算装置は、上述した第１の非ゼロ演算処理及び第２の非ゼロ演算処理を共に、２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、第２の加算処理の演算結果を桁部演算結果としている。このため、第１の非ゼロ演算処理及び第２の非ゼロ演算処理間においても、演算処理時の差異に基づくタイミングリークはなく、ダミー演算処理を含まない。
【０１７４】
実施の形態３のスカラー倍算装置は、上記特徴を有することにより、実施の形態１及び実施の形態２と同様、ゼロ演算処理及び非ゼロ演算処理間における演算処理時の差異に基づくタイミングリークを確実に回避することができる。
【０１７５】
さらに、実施の形態３において、ゼロ演算処理及び非ゼロ演算処理（第１及び第２の非ゼロ演算処理を含む）間で実行される２倍算処理、第１及び第２の加算処理は全て桁部演算結果Ａを得るために必要な演算処理であり、演算結果が利用されないダミー演算処理ではない。したがって、ダミー演算処理に対するセーフエラー攻撃が実行されることもない。
【０１７６】
加えて、スカラー倍算処理以外のサイドチャネル攻撃用の演算処理を特に必要としていないため、実施の形態３のスカラー倍算装置を比較的簡単な構成で実現できる。
【０１７７】
その結果、サイドチャネル攻撃に強く、セキュリティー性が高いスカラー倍演算処理を実行する実施の形態３のスカラー倍算装置を得ることができる。
【０１７８】
なお、実施の形態３のスカラー倍算装置は、外部より入力されるスカラー値ｄ（入力スカラー値）がスカラー値変換処理によって変換された変換スカラー値ａをスカラー倍算処理の演算用スカラー値として用いている。したがって、演算用スカラー値（変換スカラー値ａ）を構成する複数の桁部はそれぞれ正負の情報を含む１ビットの情報量を有している。また、図１のステップＳＰ０１あるいはステップＳＰ１１として実行する２倍算処理は２倍算演算部６を１回用いて１回倍算値を得る処理となる。
【０１７９】
このように、実施の形態３のスカラー倍算装置は、変換スカラー値ａを演算用スカラー値として用いるＮＡＦ法を採用したスカラー倍演算処理をセキュリティー性を高めて実行することができる効果を奏する。
【０１８０】
＜実施の形態４＞
実施の形態４は、ｗ（Window）ＮＡＦ法を採用したスカラー倍算装置である。ｗＮＡＦ法とはスカラー値ｄをｗＮＡＦ（符号付ウィンドウ形式）に変換して計算を行うアルゴリズムである。ｗＮＡＦ法は加算鎖の計算をバイナリ法より高速に行える可能性が高い利点を奏している。
【０１８１】
（ｗＮＡＦ法の概要）
ｗＮＡＦ法のアルゴリズムにおけるスカラー倍算処理は、「ｗＮＡＦ変換」（スカラー値変換処理）、「事前計算」（テーブル作成処理）、及び「本計算」（スカラー倍算本処理）の３つの処理に分類される。
【０１８２】
図１５はｗＮＡＦ法における従来のスカラー値変換処理の（ｗＮＡＦ）変換アルゴリズムＡＲ８１を模式的に示す説明図である。なお、図１５で示す変換アルゴリズムＡＲ８１において、１：，２：，…１６：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１６と呼ぶ。
【０１８３】
図１５のステップＳＴ３においてｃ［０］は変数ｃの最下位ビットを示し、ステップＳＴ４においてｃ［ｗ：０］は変数ｃにおける最下位（ｗ＋１）ビットを意味する。
【０１８４】
図１５で示す変換アルゴリズムＡＲ８１を実行することにより、スカラー値ｄから、各々がＭ（＝ｗ＋１）ビット以下のＫビットの情報量の複数の桁部を有する変換スカラー値ｂを得ることができる。ただし、変換スカラー値ｂを構成する複数の桁部の値ｂｉは正負の情報を含んでいる。値ｂｉの正負決定処理は、図１５のステップＳＴ４〜ＳＴ７の処理で行われる。
【０１８５】
例えば、スカラー値ｄが“１０１００１１１１０１１”２（＝（２６８３））の場合、変換アルゴリズムＡＲ８１を採用したスカラー値変換処理を実行することにより、スカラー値ｄを１ビット単位にｗＮＡＦ変換して、変換スカラー値ｂ（＝１０００５００００００（−５））を得ることができる。すなわち、変換スカラー値ｂは、データｂ１１〜データｂ０を有する１２個の桁部から構成される。
【０１８６】
図１６はｗＮＡＦ法における従来のテーブル作成処理である事前計算アルゴリズムＡＲ８２を模式的に示す説明図である。なお、図１６で示す事前計算アルゴリズムＡＲ８２において、１：，２：，…５：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ５と呼ぶ。
【０１８７】
図１６で示す事前計算アルゴリズムＡＲ８２を実行することにより、入力座標点Ｐを奇数倍して得られる奇数倍座標点を複数個計算し、｛テーブルＴ１〜Ｔβ｝として記憶部８内に格納される。
【０１８８】
図１７はｗＮＡＦ法における従来のスカラー倍算本処理である本計算アルゴリズムＡＲ８３を模式的に示す説明図である。なお、図１７で示す本計算アルゴリズムＡＲ８３において、１：，２：，…１０：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１０と呼ぶ。
【０１８９】
このように、変換アルゴリズムＡＲ８１、事前計算アルゴリズムＡＲ８２及び本計算アルゴリズムＡＲ８３からなるスカラー倍算処理を実行するのが従来のｗＮＡＦ法である。
【０１９０】
図１７に示すように、ｗＮＡＦ法を採用した従来のスカラー倍算本処理では、変換スカラー値ｂの桁部の値ｂｉが非“０”の場合はステップＳＴ５あるいはステップＳＴ７が実行される。すなわち、ｂｉが正の場合はステップＳＴ５が実行され、ｂｉが負の場合はステップＳＴ７が実行される。このように、ｗＮＡＦ法では、非ゼロ演算処理として互いに異なる２つの非ゼロ演算処理（第１及び第２の非ゼロ演算処理）を有している。
【０１９１】
一方、値ｂｉが“０”の場合はステップＳＴ５及びＳＴ７は全てが実行されない。
【０１９２】
したがって、従来のｗＮＡＦ法に対するサイドチャネル攻撃については、桁部の値であるｂｉが“０”と非“０”との場合で処理が分岐しているため、タイミングリークを完全に隠蔽することができない問題点があった。
【０１９３】
（構成）
上記問題点の解決を図りつつ、ｗＮＡＦ法を採用したのが実施の形態４のスカラー倍算装置である。
【０１９４】
装置構成は図２で示した実施の形態１と同様であるが、変換スカラー値生成部３が後述するスカラー値変換処理を行い、スカラー値ｄから変換スカラー値ｂを得る点、スカラー倍算用演算部１が変換スカラー値ｂを演算用スカラー値として、後述するスカラー倍算本処理を行う点が大きく異なる。
【０１９５】
そして、実施の形態４において、スカラー倍算用演算部１及び変換スカラー値生成部３により、変換スカラー値ｂを演算用スカラー値とし、演算用スカラー値と入力座標点Ｐとを演算対象として、スカラー倍演算処理を行いスカラー倍算値ｄＰを得るスカラー倍演算機構が構成される。
【０１９６】
（アルゴリズム）
図１８はｗＮＡＦ法における実施の形態４のスカラー値変換処理の（ｗＮＡＦ）変換アルゴリズムＡＲ３１を模式的に示す説明図である。なお、図１８で示す変換アルゴリズムＡＲ３１において、１：，２：，…２１：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ２１と呼ぶ。
【０１９７】
図１８のステップＳＴ３においてｃ［０］は変数ｃの最下位ビットを示し、ステップＳＴ４においてｃ［ｗ：０］は変数ｃにおける最下位（ｗ＋１）ビットを意味する。
【０１９８】
図１８で示す変換アルゴリズムＡＲ３１を実行することにより、スカラー値ｄから、各々がＫビット（Ｋ＝１〜Ｍ（＝ｗ＋１）のいずれか）の情報量の複数の桁部を有する変換スカラー値ｂを得ることができる。ただし、変換スカラー値ｂを構成する複数の桁部の値ｂｉは正負の情報を含んでいる。値ｂｉの正負決定処理は、図１８のステップＳＴ５〜ＳＴ８の処理で行われる。
【０１９９】
例えば、スカラー値ｄが“１０１００１１１１０１１”２（＝（２６８３））の場合、変換アルゴリズムＡＲ３１を採用したスカラー値変換処理を実行することにより、スカラー値ｄをｗＮＡＦ変換して、変換スカラー値ｂ（データｂ３＝“１”（Ｋ＝１ビット情報量）、データｂ２＝“５”（Ｋ＝４ビット情報量）、データｂ１＝“０”（Ｋ＝３ビット情報量）、データｂ０＝“−５”（Ｋ＝４ビット情報量））を得ることができる。すなわち、変換スカラー値ｂは、データｂ３〜データｂ０を有する４個の桁部から構成される。
【０２００】
また、ｂｉが非“０”の場合のビット数Ｋとなるｌｅｎｉ（Window幅）は最大のＭ＝ｗ＋１（ビット）となり（図１８のステップＳＴ９〜ＳＴ１１の処理）、ｂｉが“０”の場合のビット数Ｋとなるｌｅｎｉは１〜Ｍビットのうちのいずれか（図１８のステップＳＴ１４〜ＳＴ１６の処理）となる。
【０２０１】
例えば、スカラー値ｄが“１０１００１１１１０１１”２の場合、ｂ３〜ｂ０の｛１，５，０，−５｝に対応して、ｌｅｎ３〜ｌｅｎ０＝｛４，４，３，４｝となる。
【０２０２】
変換スカラー値生成部３はスカラー値ｄを受け、スカラー値ｄに基づき、変換アルゴリズムＡＲ３１によるスカラー値変換処理を実行して変換スカラー値ｂを取得し、その後、変換スカラー値ｂをスカラー倍算用演算部１に出力する。この際、ｂｉのビット数Ｋを示すｌｅｎｉも併せてスカラー倍算用演算部１に出力する。
【０２０３】
そして、スカラー倍算用演算部１は、変換スカラー値生成部３から変換スカラー値ｂのｂｉ及びビット数Ｋを示すｌｅｎｉを受け、変換スカラー値ｂ及び入力座標点Ｐを演算対象として後述するスカラー倍算本処理を実行してスカラー倍算値ｄＰを得る。なお、変換スカラー値ｂ、入力座標点及びビット数Ｋを示すｌｅｎｉは必要に応じて記憶部８に格納される。
【０２０４】
図１９はｗＮＡＦ法における実施の形態４のテーブル作成処理である事前計算アルゴリズムＡＲ３２を模式的に示す説明図である。なお、図１９で示す事前計算アルゴリズムＡＲ３２において、１：，２：，…５：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ５と呼ぶ。
【０２０５】
図１９で示す事前計算アルゴリズムＡＲ３２を実行することにより、入力座標点Ｐを偶数倍して得られる偶数倍座標点を複数個計算し、｛テーブルＴ２，Ｔ４〜Ｔβ｝として記憶部８に格納される。この際、Ｔｉ（ｉ＝２〜βを満足する偶数）の値はｉ×Ｐとなる。
【０２０６】
図２０はｗＮＡＦ法における実施の形態４のスカラー倍算本処理である本計算アルゴリズムＡＲ３３を模式的に示す説明図である。なお、図２０で示す本計算アルゴリズムＡＲ３３において、１：，２：，…１８：は実行ステップ位置を示す。以下、実行ステップ位置を基準にしてステップＳＴ１〜ＳＴ１８と呼ぶ。
【０２０７】
図２１は実施の形態４のスカラー倍算装置による本計算アルゴリズムＡＲ３３の実行例を模式的に示す説明図（その１）である。図２２は実施の形態４のスカラー倍算装置による本計算アルゴリズムＡＲ３３の実行例を模式的に示す説明図（その２）である。以下、スカラー倍算用演算部１が実行する本計算アルゴリズムＡＲ３３の概要を、図２０〜図２２を参照して説明する。
【０２０８】
(1)スカラー倍算装置に入力座標点Ｐとスカラー値ｄ（入力スカラー値）を入力し、入力座標点Ｐをスカラー倍算用演算部１内に取り込まれ、必要に応じて記憶部８に格納される。さらに、変換アルゴリズムＡＲ３１を採用したスカラー値変換処理によってスカラー値ｄを変換して得られる変換スカラー値ｂが変換スカラー値生成部３によって得られる（図２０のInput：…に相当）。この際、変換スカラー値ｂとともに、ｂｎ−１〜ｂ０のビット数Ｋを示すｌｅｎｎ−１〜ｌｅｎ０がスカラー倍算用演算部１に出力される。
【０２０９】
(2)上記処理(1)の際、ｗＮＡＦ法のアルゴリズムで計算を行うため、変換スカラー値ｂに関しｎ個の桁部がそれぞれ正負を含むＭ（＝ｗ＋１）ビット以下のＫビットの情報を有する表記とする。
【０２１０】
図２０に示すように、変換スカラー値ｂ＝｛ｂｎ−１，…，ｂ０｝で表される。例えば、図２１(a)に示すように、ｎ＝４とした、変換スカラー値ｂ＝（ｂ３＝“１”、ｂ２＝“５”、ｂ１＝“０”、データｂ０＝“−５”）の値を有する、ｂ３〜ｂ０がｌｅｎ３〜ｌｅｎ０と共にスカラー倍算用演算部１に出力され、必要に応じて記憶部８に格納される。
【０２１１】
(3)１つ上位の桁部における桁部演算結果Ａ（初期値“０”）の２倍算点〜２ｗ＋１倍算点である２Ａ〜２ｗ＋１Ａ（１回倍算値〜Ｍ（＝ｗ＋１）回倍算値）を計算し、記憶部８に格納する（図２０のステップＳＴ２〜ＳＴ５に相当）。
【０２１２】
例えば、ＭＳＢ（最上位（ｎ−１））の桁部の値ｂ３に対する演算処理Ｐ１では、桁部演算結果Ａの初期値は無限遠点Ｏであるため、２倍算関数ＥＣＤＢＬ（Ａ）の演算結果も無限遠点Ｏとなり、ステップＳＴ２〜ＳＴ５が実行されない場合と実質的に同じになる（図２１では図示せず）。すなわち、図２２の加算・減算処理ＡＳ３のみが実行されることになる。
【０２１３】
また、ＭＳＢ−１（＝ｎ−２）の桁部の値ｂ２に対する演算処理Ｐ２（１〜４行目）では、１つ上位の桁部の演算処理Ｐ１（加算・減算処理ＡＳ３）の桁部演算結果ＡがＰであったため、Ｐの２倍算を１〜４（Ｍ＝ｗ＋１）回繰り返して、倍算値２Ｐ，４Ｐ，８Ｐ及び１６Ｐ（＝Ｐ×２×２×２×２）が得られる。この際、図２２に示すように、ビット数Ｋを示すｌｅｎ２＝４のため、倍数選択処理ＬＳ２（図２０のステップＳＴ６及びＳＴ７に相当）によって４回倍算値（＝Ｋ回倍算値）である１６Ｐが選択される。
【０２１４】
(4)ｂｉ（ｉ＝（ｎ−１）〜０のいずれか）が正の場合（非“０”）は｛Ｂ＝Ｔｂｉ＋１，Ｃ＝−Ｐ｝に設定し（図２０のステップＳＴ９に相当）、負の場合（非“０”）は｛Ｂ＝−Ｔ１−ｂｉ，Ｃ＝Ｐ｝に設定する（図２０のステップＳＴ１１）。その後、加算処理（Ａ＋Ｂ）（第１の加算処理）を実行し（図２０のステップＳＴ１５に相当）、さらに、その後、加算処理（Ａ＋Ｃ）（第２の加算処理）を実行する（図２０のステップＳＴ１６に相当）。
【０２１５】
例えば、ｂ２（＝“５”）に対して行う演算処理Ｐ２（５行目）では、第１の加算処理として、Ａ（＝１６Ｐ）＋Ｂ（＝６Ｐ＝Ｔ６）の加算処理が実行され、演算処理Ｐ２（６行目）では、第２の加算処理として、Ａ（＝２２Ｐ）＋Ｂ（＝−Ｐ）の加算処理が実行される。すなわち、図２２の加算・減算処理ＡＳ２のように、Ａ（＝１６Ｐ）に対して＋５Ｐを加算する処理が実行されたことになる。
【０２１６】
また、ｂ０（＝“−５”）に対して行う演算処理Ｐ４（５行目）では、第１の加算処理として、Ａ（＝２６８８Ｐ）＋Ｂ（＝−６Ｐ＝−Ｔ６）の加算処理が実行され、演算処理Ｐ４（６行目）では、第２の加算処理として、Ａ（＝２６８２Ｐ）＋Ｂ（＝Ｐ）の加算処理が実行される。すなわち、図２２の加算・減算処理ＡＳ０のように、Ａ（＝２６８８Ｐ）に対して−５Ｐを加算（５Ｐを減算する）する処理が実行されたことになる。
【０２１７】
一方、ｂｉが“０”の場合、｛Ｂ＝Ｐ，Ｃ＝−Ｐ｝に設定した（図２０のステップＳＴ１３）後、加算処理（Ａ＋Ｂ）（第１の加算処理）を実行し（図２０のステップＳＴ１５に相当）、さらに、その後、加算処理（Ａ＋Ｃ）（第２の加算処理）を実行する（図２０のステップＳＴ１６に相当）。
【０２１８】
例えば、ｂ１（＝“０”）に対して行う演算処理Ｐ３（５行目）では、第１の加算処理として、Ａ（＝１６８Ｐ）＋Ｂ（＝Ｐ）の加算処理が実行され、演算処理Ｐ３（６行目）では、第２の加算処理として、Ａ（＝１６９Ｐ）＋Ｂ（＝−Ｐ）の加算処理が実行される。すなわち、図２２の加算・減算処理ＡＳ１のように、Ａ（＝１６８Ｐ）に対して＋０Ｐを加算（−０Ｐを減算する）する処理が実行されたことになる。
【０２１９】
上述した第２の加算処理（図２０のステップＳＴ１６に相当）を実行した後、ｉ桁の桁部（ｂｉ）の桁部演算結果Ａを得ることができる。
【０２２０】
(5)桁数ｉを“１”繰り下げた後（ステップＳＴ１及びＳＴ１７に相当）、上記処理(3)〜(4)を繰り返す。
【０２２１】
そして、スカラー倍算用演算部１は、最終的にｉ＝０のとき、ｂ０に対する演算処理Ｐ４の第２の加算処理（処理(4)）によって得られるＬＳＢ（最下位“０”）桁部の桁部演算結果Ａ＝２６８３Ｐを、スカラー倍算値ｄＰとして出力する（図２０のステップＳＴ１８に相当）。
【０２２２】
このように、実施の形態４のスカラー倍算装置は、スカラー倍算処理として、変換アルゴリズムＡＲ３１を採用したスカラー値変換処理、事前計算アルゴリズムＡＲ３２を採用したテーブル作成処理及び本計算アルゴリズムＡＲ３３を採用したスカラー倍算本処理を実行している。
【０２２３】
したがって、スカラー倍算用演算部１は、演算処理Ｐ１〜Ｐ４のうち、最初の演算処理Ｐ１を除いて、ｂｉの値の“０”，非“０”（正，負）に関わらず、Ｍ（＝ｗ＋１）回繰り返して行う２倍算処理（図２０のステップＳＴ２〜ＳＴ５）→第１の加算処理（図２０のステップＳＴ９及びＳＴ１５、ＳＴ１１及びＳＴ１５あるいはＳＴ１３及びＳＴ１５）→第２の加算処理（図２０のステップＳＴ９及びＳＴ１６、ＳＴ１１及びＳＴ１６あるいはＳＴ１３及びＳＴ１６）の順番で３回実行するため、ダミー演算を行うことなく処理時間を一定にすることができる。
【０２２４】
なお、演算処理Ｐ３ではビット数Ｋを示すｌｅｎ１＝３のため、２倍算を３（＝ｗ＝Ｍ−１）回繰り返して得られる３回倍算値（Ｓ２）を選択している（ステップＳＴ６及びＳＴ７）。すなわち、図２２に示すように、２倍算を１〜４回繰り返して得られる１回倍算値（４２Ｐ）〜４回倍算値（３３６Ｐ）のうち、倍数選択処理ＬＳ１により３回倍算値（＝Ｋ回倍算値）である２倍算処理結果１６８Ｐを選択している。
【０２２５】
一方、演算処理Ｐ２及び演算処理Ｐ４では共にビット数Ｋを示すｌｅｎ２＝ｌｅｎ０＝４のため、２倍算を４（＝ｗ＋１＝Ｍ）回繰り返して得られる４回倍算値（Ｓ３）を選択している（ステップＳＴ６及びＳＴ７）。すなわち、図２２に示すように、２倍算を１〜４回繰り返して得られる１回倍算値（２Ｐ，３３６Ｐ）〜４回倍算値（１６Ｐ，２６８８Ｐ）のうち、倍数選択処理ＬＳ２及びＬＳ０により４回倍算値（＝Ｋ回倍算値）である２倍算処理結果１６Ｐ及び２６８８Ｐを選択している。
【０２２６】
しかしながら、演算処理Ｐ３も演算処理Ｐ２及び演算処理Ｐ４と同様、４回繰り返した２倍算処理（ステップＳＴ２〜ＳＴ５）を実行している。すなわち、図２２に示すように、倍数選択処理ＬＳ２〜ＬＳ０に先がけて、必ず４回繰り返した２倍算処理が実行されている。
【０２２７】
したがって、桁部のビット数Ｋに関わらず、常に２倍算は４回繰り返して実行されるため、桁部のビット数Ｋの違いによって２倍算処理間でタイミングリークが生じることはない。
【０２２８】
（効果等）
このように、実施の形態４のスカラー倍算装置において、スカラー倍算用演算部１によって行うスカラー倍演算処理は、変換スカラー値ｂを構成する複数の桁部に対応して実行され、各々が桁部演算結果を得る複数の桁部演算処理（図２１の演算処理Ｐ１〜Ｐ４に相当）を含んでいる。そして、複数の桁部演算処理の実行により、隣接する桁部間で上位から下位に桁部演算結果Ａを記憶部８を介して伝搬しつつ、最上位（ｎ−１）から最下位（０）にかけて桁部単位に桁部演算結果Ａを順次得て、最下位の桁部に対応する桁部演算処理（図２１の演算処理Ｐ４に相当）より得られる桁部演算結果Ａをスカラー倍算値ｄＰとして取得する。
【０２２９】
上述した複数の桁部演算処理はそれぞれ、加算演算部５及び２倍算演算部６を用いて実行され、スカラー倍算用演算部１は、桁部のｂｉが“０”の場合にゼロ演算処理（図２０のステップＳＴ１３を固有の実行とする処理）を実行して桁部演算結果Ａを取得し、非“０”の場合は上記ゼロ演算処理と異なる演算内容の非ゼロ演算処理（図２０のステップＳＴ９あるいはＳＴ１１を固有の実行とする処理）を実行して桁部演算結果Ａを取得している。
【０２３０】
そして、実施の形態４のスカラー倍算装置は、実施の形態１と同様、上記ゼロ演算処理及び上記非ゼロ演算処理を共に、（Ｍ（＝ｗ＋１）回繰り返して行う）２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、第２の加算処理の演算結果を桁部演算結果としたことを特徴としている。
【０２３１】
さらに、実施の形態４のスカラー倍算装置は、非ゼロ演算処理として桁部の値ｂｉが正の場合に実行される第１の非ゼロ演算処理（図２０のステップＳＴ２〜ＳＴ５，ＳＴ９、ＳＴ１５及びＳＴ１６に相当）と、桁部の値ｂｉが負の場合に実行される第２の非ゼロ演算処理（図２０のステップＳＴ２〜ＳＴ５，ＳＴ１１、ＳＴ１５及びＳＴ１６に相当）とを含んでいる。
【０２３２】
そして、実施の形態４のスカラー倍算装置は、第１の非ゼロ演算処理及び第２の非ゼロ演算処理を共に、（Ｍ回繰り返して行う）２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、第２の加算処理の演算結果を桁部演算結果としている。このため、第１の非ゼロ演算処理及び第２の非ゼロ演算処理間においても演算処理時の差異に基づくタイミングリークはなく、ダミー演算処理を含まない。
【０２３３】
実施の形態４のスカラー倍算装置は、上記特徴を有することにより、実施の形態１〜実施の形態３と同様、ゼロ演算処理及び非ゼロ演算処理間における演算処理時の差異に基づくタイミングリークを確実に回避することができる。
【０２３４】
さらに、実施の形態４において、ゼロ演算処理及び非ゼロ演算処理（第１及び第２の非ゼロ演算処理を含む）間で実行される（Ｍ回繰り返して行う）２倍算処理、第１及び第２の加算処理は全て桁部演算結果Ａを得るために必要な演算処理であり、演算結果が利用されないダミー演算処理ではない。したがって、ダミー演算処理に対するセーフエラー攻撃が実行されることもない。
【０２３５】
加えて、スカラー倍算処理以外のサイドチャネル攻撃用の演算処理を特に必要としていないため、実施の形態４のスカラー倍算装置を比較的簡単な構成で実現できる。
【０２３６】
その結果、サイドチャネル攻撃に強く、セキュリティー性が高いスカラー倍演算処理を実行する実施の形態４のスカラー倍算装置を得ることができる。
【０２３７】
なお、実施の形態４のスカラー倍算装置は、外部より入力されるスカラー値ｄ（入力スカラー値）がスカラー値変換処理によって変換された変換スカラー値ｂをスカラー倍算処理の演算用スカラー値として用いている。したがって、演算用スカラー値（変換スカラー値ｂ）を構成する複数の桁部はそれぞれ正負の情報を含むＭ（＝ｗ＋１）ビット以下のＫビットの情報量を有している。また、図２０のステップＳＴ２〜ＳＴ５として実行する、２倍算処理は２倍算演算部６をＭ回用いて１回倍算値〜Ｍ回倍算値を得た後、Ｋ回倍算値を選択的に得る処理となる。
【０２３８】
このように、実施の形態４のスカラー倍算装置は、変換スカラー値ｂを演算用スカラー値として用いるｗＮＡＦ法を採用したスカラー倍演算処理をセキュリティー性を高めて実行することができる効果を奏する。
【０２３９】
さらに、実施の形態４のスカラー倍算装置は、バイナリ法を採用した実施の形態１に比べて加算処理回数を少なくして処理速度を高めることができる効果も奏する。
【０２４０】
＜スカラー倍算方法＞
実施の形態１〜実施の形態４で示したスカラー倍算装置を用いて行う、入力座標点Ｐ及びスカラー値ｄからスカラー倍算値ｄＰを得るスカラー倍算方法について説明する。
【０２４１】
スカラー倍算方法は、実施の形態１のようにスカラー値ｄ（入力スカラー値）をそのまま演算用スカラー値として用いても、実施の形態２〜実施の形態４のようにスカラー値ｄを変換して得られる変換スカラー値ｂ（ａ）を演算用スカラー値として用いてもよい。
【０２４２】
スカラー倍算方法は、上記演算用スカラー値と入力座標点Ｐとを演算対象とし、上記演算用スカラー値は複数の桁部を有し、上記複数の桁部はそれぞれ少なくとも１ビットの情報量を有している。
【０２４３】
スカラー倍算方法は、複数の桁部に対応して実行され、各々が桁部演算結果を得る複数の桁部演算方法を含んでおり、複数の桁部演算方法の実行により、隣接する桁部間で上位から下位に桁部演算結果を伝搬しつつ、最上位から最下位にかけて桁部単位に桁部演算結果を順次得て、最下位の桁部より得られる桁部演算結果をスカラー倍算値ｄＰとして得る。
【０２４４】
複数の桁部演算方法はそれぞれ以下のステップ(a)及び(b)を実行することにより実現される。
【０２４５】
(a)桁部の値が“０”の場合はゼロ演算処理を実行して桁部演算結果を取得する。
【０２４６】
(b)桁部の値が“０”以外の場合は上記ゼロ演算処理と異なる演算内容の非ゼロ演算処理を実行して桁部演算結果を取得する。
【０２４７】
そして、上記ステップ(a)及びステップ(b)は共に、２倍算処理、第１の加算処理、及び第２の加算処理の順で行い、上記第２の加算処理の演算結果を桁部演算結果としたことを特徴としている。
【０２４８】
このように、本願発明におけるスカラー倍算方法は、上記特徴を有することにより、ステップ(a)，(b)間で共通の演算処理（２倍算処理、第１及び第２の加算処理）の実行後にはじめて桁部演算結果を得ているため、演算用スカラー値の桁部の値が“０”か非“０”かによってステップ(a)，(b)間に演算処理時間の変化が生じない。したがって、ゼロ演算処理及び非ゼロ演算処理間における演算処理時の差異に基づくタイミングリークを確実に回避することができる。
【０２４９】
さらに、ゼロ演算処理及び非ゼロ演算処理間で実行される２倍算処理、第１及び第２の加算処理は全て桁部演算結果を得るために必要な演算処理であり、演算結果が利用されないダミー演算処理ではない。したがって、ダミー演算処理に対するセーフエラー攻撃が実行されることもない。
【０２５０】
その結果、サイドチャネル攻撃に強く、セキュリティー性が高いスカラー倍演算処理を実行するスカラー倍算方法を得ることができる。
【０２５１】
＜その他＞
上述した実施の形態１〜実施の形態４では、スカラー倍演算機構としてスカラー倍算用演算部１及び変換スカラー値生成部３の組合せ（実施の形態１はスカラー倍算用演算部１のみ）を示したが、変換スカラー値生成部３の機能をスカラー倍算用演算部１内に含めるように構成してもよい。さらに、加算演算部５及び２倍算演算部６の機能をスカラー倍算用演算部１内に含まれる構成も考えられる。
【０２５２】
また、加算演算部５及び２倍算演算部６内にそれぞれ有限体加算器、有限体減算部及び有限体乗算部有する構成を説明したが、加算演算部５及び２倍算演算部６間で有限体加算器、有限体減算部及び有限体乗算部を共有するようにしても良い。
【０２５３】
また、図２で示したスカラー倍算用演算部１、変換スカラー値生成部３、加算演算部５及び２倍算演算部６は、例えば、ソフトウェアに基づくＣＰＵを用いたプログラム処理によって実行される。また、記憶部８は、ＨＤＤ、ＤＶＤ、メモリなどによって構成される。
【０２５４】
なお、本発明は、その発明の範囲内において、各実施の形態を自由に組み合わせたり、各実施の形態を適宜、変形、省略したりすることが可能である。
【符号の説明】
【０２５５】
１  スカラー倍算用演算部
３  変換スカラー値生成部
５  加算演算部
６  ２倍算演算部
８  記憶部
【図１】
0006457911.tif 000005
【図２】
0006457911.tif 000006
【図３】
0006457911.tif 000007
【図４】
0006457911.tif 000008
【図５】
0006457911.tif 000009
【図６】
0006457911.tif 000010
【図７】
0006457911.tif 000011
【図８】
0006457911.tif 000012
【図９】
0006457911.tif 000013
【図１０】
0006457911.tif 000014
【図１１】
0006457911.tif 000015
【図１２】
0006457911.tif 000016
【図１３】
0006457911.tif 000017
【図１４】
0006457911.tif 000018
【図１５】
0006457911.tif 000019
【図１６】
0006457911.tif 000020
【図１７】
0006457911.tif 000021
【図１８】
0006457911.tif 000022
【図１９】
0006457911.tif 000023
【図２０】
0006457911.tif 000024
【図２１】
0006457911.tif 000025
【図２２】
0006457911.tif 000026
【図２３】
0006457911.tif 000027
【図２４】
0006457911.tif 000028
【図２５】
0006457911.tif 000029