(57)【要約】【課題】ＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズムを提供する。【解決手段】モンゴメリ電力ラダーアルゴリズムは、初期化ステップ及び反復演算ステップを含む。初期化ステップは、反復演算変数ｉの初期値を設定し、任意の楕円曲線に含まれる基本ポイントＰ及びスカラーｋを受信し、基本ポイントＰを利用して、少なくとも２つの変数を初期化する。反復演算ステップは、２つの変数を利用して、スカラーｋと基本ポイントＰとを乗算した値Ｑを演算し、乗算演算中に２つの変数と基本ポイントＰとの関係を分析して、フォールトが流入されたか否かを検査し、検査結果によってＱを出力するか、または警告信号ＳＴＯＰを出力する。【選択図】図３
2007189692.tif 000002
【特許請求の範囲】
【請求項１】
素数有限フィールドまたは２進有限フィールドでスカラー乗算演算を行うモンゴメリ電力ラダーアルゴリズムにおいて、
反復演算変数ｉの初期値を設定し、任意の楕円曲線に含まれる基本ポイントＰ及びスカラーｋを受信し、前記基本ポイントＰを利用して少なくとも２つの変数を初期化するステップと、
前記２つの変数を利用して前記スカラーｋと前記基本ポイントＰとを乗算した値Ｑを演算し、前記乗算演算中に前記２つの変数と前記基本ポイントＰとの関係を分析してフォールトが流入されたか否かを検査し、検査結果によって前記Ｑを出力するか、または警告信号ＳＴＯＰを出力する反復演算ステップと、を実行することを特徴とするＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項２】
前記フォールトが流入されたか否かについての検査は、
前記Ｑを求めるために実行される、繰り返されるあらゆるスカラー乗算演算で検査するか、または繰り返されるスカラー乗算演算から選択された任意の瞬間にのみ検査することを特徴とする請求項１に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項３】
前記初期化ステップは、
反復演算変数ｉの初期値としてｔ−１（ｔは、整数）を設定し、前記基本ポイントＰ及び前記スカラーｋを受信するステップと、
第１変数Ｐ１を前記基本ポイントＰに置換し、第２変数Ｐ０を２倍の前記基本ポイント２Ｐに置換するステップと、を含むことを特徴とする請求項２に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項４】
前記反復演算ステップは、
前記スカラーｋを２進ビットで（ｋｔ−１，ｋｔ−２，…，Ｋ１，Ｋ０)２のように表示するとき、
前記反復演算変数ｉに設定された値を変化させつつ、前記スカラーｋに対応する２進ビットの一つであるｋｉ値によって、前記第１変数Ｐ１及び前記２変数Ｐ０を所定の値に置換する変数置換ステップと、
前記第１変数Ｐ１、前記２変数Ｐ０及び前記基本ポイントＰの間に所定の関係を満足するか否かを検査して乗算演算を続けると決定するか、または前記警告信号ＳＴＯＰを発生させるフォールト流入検査及び措置ステップと、
前記反復演算変数ｉが０より小さいか否かを判断するステップと、を含み、
前記乗算演算を中止すると決定される前には、前記反復演算変数ｉが０となるまで前記変数置換ステップを反復して行うことを特徴とする請求項３に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項５】
前記変数置換ステップは、
前記反復演算変数ｉの値を１ずつ減少させるステップと、
前記ｋｉの値が１であるか否かを判断するステップと、
前記ｋｉの値が１である場合、前記第１変数Ｐ１を、前記第１変数Ｐ１と前記第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換し、前記２変数Ｐ０を、前記第２変数Ｐ０の２倍である値２Ｐ０に置換する第１変数置換ステップと、
前記ｋｉの値が１ではない場合、前記第１変数Ｐ１を、前記第２変数Ｐ０の２倍である値２Ｐ０に置換し、前記第２変数Ｐ０を、前記第１変数Ｐ１と前記第２変数Ｐ１とを合算した値Ｐ１＋Ｐ０に置換する第２変数置換ステップと、を含むことを特徴とする請求項４に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項６】
フォールト流入検査及び措置ステップは、
前記変数置換ステップで置換された２つの変数Ｐ１，Ｐ０と最初の基本ポイントＰとの関係が３つの同じ数式Ｐ０-Ｐ１=Ｐ、Ｐ０- P =Ｐ１及びＰ１＋Ｐ=Ｐ０のうちいずれか一つを満足するか否かを検査し、前記数式に表示された数式のうち一つを満足する場合には、前記反復演算変数ｉが０であるか否かを判断するステップに進むフォールト流入検査ステップと、
前記３つの同じ数式のうち何れの一つも満足しない場合には、次の乗算演算を中断するか否かを決定し、次の乗算演算を中断すると決定した場合には、警告信号ＳＴＯＰを発生させ、次の乗算演算を続けると決定した場合には、前記反復演算変数ｉが０であるか否かを判断するステップに進む措置ステップと、を含むことを特徴とする請求項４に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項７】
前記反復演算ステップは、
前記スカラーｋを２進ビットで（ｋｔ−１，ｋｔ−２，…，Ｋ１，Ｋ０)２のように表示するとき、
前記反復演算変数ｉの値を変化させつつ、前記スカラーｋに対応する２進ビットの一つであるｋｉの値によって、前記第１変数Ｐ１及び前記２変数Ｐ０を所定の値に置換する変数置換ステップと、
変数チェックに設定された値によってフォールト検査を行うか否かを決定するステップと、
前記変数チェックに設定された値によって、前記第１変数Ｐ１、前記２変数Ｐ０及び前記基本ポイントＰの間の関係を検査して、次の乗算演算を続けると決定するか、または次の乗算演算を中止し、前記警告信号ＳＴＯＰを発生させるフォールト流入検査及び措置ステップと、
乗算演算を続けると決定された場合には、前記反復演算変数ｉが０より小さいか否かを判断するステップと、を含み、
前記ステップの判断結果、前記反復演算変数ｉが０より小さくないと判断された場合には、変数置換ステップに進むことを特徴とする請求項３に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項８】
前記変数置換ステップは、
前記反復演算変数ｉの値を１ずつ減少させるステップと、
前記ｋｉの値が１であるか否かを判断するステップと、
前記ｋｉの値が１である場合、前記第１変数Ｐ１を、前記第１変数Ｐ１と前記第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換し、前記２変数Ｐ０を、前記第２変数Ｐ０の２倍である値２Ｐ０に置換する第１変数置換ステップと、
前記ｋｉの値が１ではない場合、前記第１変数Ｐ１を、前記第２変数Ｐ０の２倍である値２Ｐ０に置換し、前記第２変数Ｐ０を、前記第１変数Ｐ１と前記第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換する第２変数置換ステップと、を含むことを特徴とする請求項７に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項９】
前記フォールト検査を行うか否かを決定するステップは、
変数チェックに任意の数を設定するステップと、
前記変数チェックに設定された値が、所定の基準値と一致するか否かを判断するステップと、を含み、
前記変数チェックに設定された値が前記基準値と一致する場合には、フォールト検査を行い、そうでない場合には、乗算演算を続けることを特徴とする請求項８に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１０】
前記変数チェックに設定される値は、
２進ビットの０または１のうち何れか一つであることを特徴とする請求項９に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１１】
フォールト流入検査及び措置ステップは、
前記変数置換ステップで置換された２つの変数Ｐ１，Ｐ０と最初の基本ポイントＰとの間が、３つの同じ数式Ｐ０-Ｐ１=Ｐ、Ｐ０-Ｐ=Ｐ１及びＰ１＋Ｐ=Ｐ０のうち何れか一つを満足するか否かを検査し、前記３つの同じ数式のうち何れか一つを満足する場合には、前記反復演算変数ｉが０であるか否かを判断するステップに進むフォールト流入検査ステップと、
前記３つの同じ数式のうち何れの一つも満足しない場合には、次の乗算演算を中断するか否かを決定し、次の乗算演算を中断すると決定した場合には、警告信号ＳＴＯＰを発生させ、次の乗算演算を続けると決定した場合には、前記反復演算変数ｉが０であるか否かを判断するステップに進む措置ステップと、を含むことを特徴とする請求項８に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１２】
前記Ｑを使用する演算装置に前記Ｑを伝達するステップをさらに含むことを特徴とする請求項３に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１３】
素数有限フィールドまたは２進有限フィールドでスカラー乗算演算を行うモンゴメリ電力ラダーアルゴリズムにおいて、
反復演算変数ｉの初期値を設定し、任意の楕円曲線に含まれる基本ポイントＰ及びスカラーｋを受信し、前記基本ポイントＰを利用して少なくとも２つの変数を初期化するステップと、
前記２つの変数を利用して前記スカラーｋと前記基本ポイントＰとを乗算した値Ｑを演算する反復演算ステップと、
前記２つの変数と前記基本ポイントＰとの関係を分析して、フォールトが流入されたか否かを検査し、検査結果によって前記Ｑまたは警告信号ＳＴＯＰを出力するフォールト流入検査及び措置ステップと、を実行することを特徴とするＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１４】
前記初期化ステップは、
反復演算変数ｉの初期値としてｔ−１（ｔは、整数）を設定し、基本ポイントＰ及びスカラーｋを受信するステップと、
第１変数Ｐ１を前記基本ポイントＰに置換し、第２変数Ｐ０を、２倍の前記基本ポイント２Ｐに置換するステップと、を含むことを特徴とする請求項１３に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１５】
前記反復演算ステップは、
前記スカラーｋを２進ビットで（ｋｔ−１，ｋｔ−２，…，Ｋ１，Ｋ０)２のように表示するとき、
前記反復演算変数ｉに設定された値を１ずつ減少させるステップと、
前記スカラーｋに対応する２進ビットの値が１であるか否かを判断するステップと、
前記ｋｉの値が１である場合、前記第１変数Ｐ１を、前記第１変数Ｐ１と前記第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換し、前記２変数Ｐ０を、前記第２変数Ｐ０の２倍である値２Ｐ０に置換する第１変数置換ステップと、
前記ｋｉの値が１ではない場合、前記第１変数Ｐ１を、前記第２変数Ｐ０の２倍である値２Ｐ０に置換し、前記第２変数Ｐ０を、前記第１変数Ｐ１と前記第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換する第２変数置換ステップと、
前記反復演算変数ｉが０より小さいか否かを判断するステップと、を含み、
前記ステップの判断結果、前記反復演算変数ｉが０より小さくない場合には、前記反復演算変数ｉの値を１ずつ減少させるステップに進み、そうでない場合には、前記フォールト流入検査及び措置ステップを行うステップに進むことを特徴とする請求項１４に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１６】
前記フォールト流入検査及び措置ステップは、
前記変数置換ステップで置換された２つの変数Ｐ１，Ｐ０及び最初の基本ポイントＰを利用して、３つの数式Ｐ０-Ｐ１=Ｐ、Ｐ０-Ｐ=Ｐ１及びＰ１＋Ｐ=Ｐ０に表示された数式のうち何れか一つを満足するか否かを検査するフォールト流入検査ステップと、
前記数式に表示された数式のうち何れか一つの数式を満足する場合には、演算結果Ｑを出力するステップと、
前記数式に表示された数式のうち何れの一つの数式も満足しない場合には、警告信号ＳＴＯＰを発生させるステップと、を含むことを特徴とする請求項１４に記載のＤＦＡに対抗する方法を含むモンゴメリ電力ラダーアルゴリズム。
【請求項１７】
請求項１に記載のモンゴメリ電力ラダーアルゴリズムがプログラム言語に変換されて保存されている記録媒体。
【請求項１８】
請求項１７に記載の記録媒体を使用する暗号システム。
【請求項１９】
請求項１３に記載のモンゴメリ電力ラダーアルゴリズムがプログラム言語に変換されて保存されている記録媒体。
【請求項２０】
請求項１９の記録媒体を使用する暗号システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号システムに係り、特に、ＤＦＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｆａｕｌｔ Ａｎａｌｙｓｉｓ）に対抗する方法を含むモンゴメリ電力ラダーアルゴリズム（Ｍｏｎｔｇｏｍｅｒｙ Ｐｏｗｅｒ Ｌａｄｄｅｒ Ａｌｇｏｒｉｔｈｍ；以下、ＭＰＬＡという）に関する。
【背景技術】
【０００２】
情報化社会の到来と共に暗号アルゴリズム及び暗号プロトコルを利用した情報の保護の重要性は次第に増大している。情報の保護に使用される暗号アルゴリズムのうち、ＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号システム及び楕円曲線暗号システム（Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ；以下、ＥＣＣ）で使用する公開キー暗号アルゴリズムは、秘密キー暗号アルゴリズムの短所であるキーの分配問題、電子署名の問題などを解決しつつ、インターネットや金融網のような多様な分野への応用に広く適用されている。
【０００３】
ＲＳＡ公開キー暗号システム及びＥＣＣ公開キー暗号システムに侵入しようとするときにサイドチャンネル分析が使用される。サイドチャンネル分析の種類としては、タイミング分析、電力分析、電磁気分析及びフォールト分析などが広く知られている。サイドチャンネル分析は、解析しようとする暗号システムのハードウェア構成を具体的に知っている場合に有効な攻撃方法である。
【０００４】
フォールト分析のうち、演算されている変数の差値を利用して暗号システムの秘密キーを捜し出す差動フォールト分析（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｆａｕｌｔ Ａｎａｌｙｓｉｓ；以下、ＤＦＡという）が広く知られている。ＤＦＡは、フォールトを暗号システムに投入させ、投入されたフォールトに対応する演算結果を分析して、暗号システムの秘密キーを探す接近方法である。レジスタに保存されるか、または保存された値は、フォールトによって変更される。暗号システムが所定の演算を行うとき、レジスタに保存された値を参照するため、フォールトによって変更された値に対応するエラーが演算結果に含まれる。暗号分析者は、出力されるエラーを伴なった演算結果を解析して、秘密キーなどについての情報を得る。
前記のようなＤＦＡに対応するために、ＥＣＣで使用できる多様な方法が提案されている。
【０００５】
図１は、ＤＦＡに対応する従来のＣＴ＆Ｃ方法についての信号フローチャートである。
図１に示すように、ＣＴ＆Ｃ（Ｃａｌｃｕｌａｔｅ Ｔｗｉｃｅ ａｎｄ Ｃｈｅｃｋ）方法１００は、まず、楕円曲線のうち任意の一点Ｐを選択し（１１０）、Ｐに任意の整数ｋを乗算して第１比較値Ｑ１を求め（１２０）、Ｐに整数ｋを乗算して第２比較値Ｑ２を求め（１３０）、第１比較値Ｑ１と第２比較値Ｑ２との大きさを比較する（１４０）。
【０００６】
第１比較値Ｑ１と第２比較値Ｑ２とが同じである場合には、乗算演算にいかなるフォールトも流入されていないと判断して、第１比較値Ｑ１及び第２比較値Ｑ２のうち何れか一つが演算結果Ｑとして出力される（１５０）。しかし、第１比較値Ｑ１と第２比較値Ｑ２とが異なる場合には、乗算演算中にフォールトが流入されたと判断して、このときには、演算結果Ｑの代わりに警告信号が出力される（１６０）。
【０００７】
ここで、あらゆるフォールトは、一定の規則なしに流入され、２つの乗算演算に同じ値を有するフォールトが同時に流入される確率は無視すべきであると仮定する。また、所定の整数ｋは、秘密キーを意味し、第１比較値Ｑ１と第２比較値Ｑ２とは同時に計算されることが一般的である。
【０００８】
図１に示すＣＴ＆Ｃ方法は、対称、非対称及びストリームなど、いかなる種類の暗号アルゴリズムにも適用されうるという長所があるが、同じ乗算計算を２回も行わなければならないという短所がある。また、ほとんどのスマートカード及び移動機器の使用領域にはフォールト成分が常に存在するため、スマートカードや移動機器に前記ＣＴ＆Ｃ方法をそのまま適用できないという短所がある。
【０００９】
図２は、ＤＦＡに対応する従来のＣＯＰ（Ｃｈｅｃｋ ｔｈｅ Ｏｕｔｐｕｔ Ｐｏｉｎｔ）方法についての信号フローチャートである。
図２に示すように、ＣＯＰ方法２００は、まず、楕円曲線のうち任意の一点Ｐを選択し（２１０）、Ｐに所定の整数ｋを乗算して比較値Ｑを求め（２２０）、比較値Ｑが楕円曲線Ｅの一点であるか否かを判断する。（２３０）
【００１０】
比較値Ｑが前記楕円曲線Ｅの一点である場合には、乗算演算にいかなるフォールトも流入されていないと判断して、比較値Ｑが出力される（２４０）。しかし、比較値Ｑが楕円曲線Ｅの一点ではない場合には、乗算演算中にフォールトが流入されたケースに該当すると判断して、比較値Ｑの代わりに警告信号が出力される（２５０）。
【００１１】
ここで、あらゆるフォールトは、一定の規則なしに流入され、乗算演算に投入されたフォールトに影響を受けて計算された比較値Ｑが楕円曲線Ｅの一点に含まれる確率は無視すべきであると仮定する。また、所定のｋ値は、一般的に秘密キーを意味する。
【００１２】
ＣＯＰ方法２００は、ＤＦＡに対応しつつも暗号システムの実行能力を低下させない。しかし、ＣＯＰ方法は、ＥＣＣを基盤とする暗号システムにのみ適用されるので、その適用範囲が狭いという短所がある。また、符号が変わるフォールトを利用した攻撃に対応する場合には、システムの実行能力が非常に低下するという短所がある。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明が解決しようとする技術的課題は、追加的な演算が簡単であり、フォールトが常に存在する所でも使用可能であり、ＥＣＣ及びＲＳＡなどの多様な暗号システムに適用可能なＤＦＡに対抗する方法を含むＭＰＬＡを提供することである。
【課題を解決するための手段】
【００１４】
前記技術的課題を解決するための本発明の一面によるＤＦＡに対抗する方法を含むＭＰＬＡは、初期化ステップ及び反復演算ステップを含む。前記初期化ステップは、反復演算変数ｉの初期値を設定し、任意の楕円曲線に含まれる基本ポイントＰ及びスカラーｋを受信し、前記基本ポイントＰを利用して、少なくとも２つの変数を初期化する。前記反復演算ステップは、前記２つの変数を利用して、前記スカラーｋと前記基本ポイントＰとを乗算した値Ｑを演算し、前記乗算演算中に前記２つの変数と前記基本ポイントＰとの関係を分析して、フォールトが流入されたか否かを検査し、検査結果によって前記Ｑを出力するか、または警告信号ＳＴＯＰを出力する。
【００１５】
前記他の技術的課題を解決するための本発明の他の一面によるＤＦＡに対抗する方法を含むＭＰＬＡは、初期化ステップ、反復演算ステップ、フォールト流入検査ステップ及び措置ステップを含む。前記初期化ステップは、反復演算変数ｉの初期値を設定し、任意の楕円曲線に含まれる基本ポイントＰ及びスカラーｋを受信し、前記基本ポイントＰを利用して、少なくとも２つの変数を初期化する。前記反復演算ステップは、前記２つの変数を利用して、前記スカラーｋと前記基本ポイントＰとを乗算した値Ｑの演算を行う。前記フォールト流入検査及び措置ステップは、前記２つの変数と前記基本ポイントＰとの関係を分析して、フォールトが流入されたか否かを検査し、検査結果によって前記Ｑまたは警告信号ＳＴＯＰを出力する。
【発明の効果】
【００１６】
本発明に係るＤＦＡに対抗する方法を含むＭＰＬＡは、アルゴリズムが実行されている途中にＤＦＡを利用した暗号システムの侵入に能動的に対応しうる。
【発明を実施するための最良の形態】
【００１７】
本発明と、本発明の動作上の利点及び本発明の実施によって解決される目的を十分に理解するためには、本発明の望ましい実施形態を例示する添付図面及び図面に記載された内容を参照しなければならない。
【００１８】
以下、添付した図面を参照して本発明の望ましい実施形態を説明することによって、本発明を詳細に説明する。各図面に付された同一参照符号は、同一部材を示す。
ＥＣＣでは、任意の楕円曲線Ｅと、Ｅ上の一点Ｐとがシステムパラメータとして選択される。暗号化通信を所望する甲は、ランダムに整数ｄを生成させ、整数ｄとＰとを乗算してＱ（＝ｄ×Ｐ）を生成させる。甲は、Ｑを公開キーとして公開し、ｄを甲の秘密キーとして安全に保存する。
【００１９】
逆に、甲にメッセージＭを秘密裡に伝送しようとする乙は、まず、ランダムに整数ｋを生成させ、システムパラメータの一つであるＰと整数ｋとを乗算してＡ（＝ｋ×Ｐ）を生成させる。甲が提供した公開キーＱと、伝送しようとするメッセージＭとを使用してＢ（＝Ｍ＋ｋＱ）を生成させる。最後に、乙は、最終的な結果暗号文（Ａ、Ｂ）を甲に伝送する。
【００２０】
暗号文（Ａ、Ｂ）を乙から伝達された甲は、自身の秘密キーｄを使用してｄＡを計算した後、数式１のような演算を行ってメッセージＭを復元する。
【００２１】
【数１】
2007189692.tif 000003
数式１に表わすように、ＥＣＣ公開キー暗号システムで最も重要な演算は、加算演算及びスカラー乗算演算である。
【００２２】
楕円曲線Ｅ上の任意の一点（ｘ、ｙ）は、数式２を満足する。
【００２３】
【数２】
2007189692.tif 000004
【００２４】
暗号の応用分野において、素数有限フィールドＧＦ（ｐ）または２進有限フィールドＧＦ（２ｎ）の演算に、数式２で表わした楕円曲線の特性を使用することができる。ここで、素数有限フィールドは、構成要素の数が、素数ｐに限定された領域を意味し、構成要素の数がｐ個である素数有限フィールドＧＦ（ｐ）は、一つのみ存在する。
【００２５】
素数有限フィールドＧＦ（ｐ）において、異なる二つの変数Ｐ＝（ｘ１，ｙ１）とＱ＝（ｘ２，ｙ２）とを合算した（Ｐ＋Ｑ）変数Ｒ＝（ｘ３，ｙ３）を求めるためには、数式３の演算を行わなければならない。
【００２６】
【数３】
2007189692.tif 000005
【００２７】
素数有限フィールドＧＦ（ｐ）において、二つの変数ＰとＱとが同じである場合には、変数Ｒは、数式４の演算を行って求めることができる。
【００２８】
【数４】
2007189692.tif 000006
【００２９】
ここで、二つの変数ＰとＱとが同じであるので、ｘ１及びｘ２はｘで、ｙ１及びｙ２はｙで表示した。２進有限フィールドＧＦ（２ｎ）において、異なる二つの変数Ｐ＝（ｘ１，ｙ１）とＱ＝（ｘ２，ｙ２）とを合算した（Ｐ＋Ｑ）変数Ｒ（ｘ３，ｙ３）を求めるためには、数式５の演算を行わなければならない。
【００３０】
【数５】
2007189692.tif 000007
【００３１】
２進有限フィールドＧＦ（２ｎ）において、二つの変数ＰとＱとが同じである場合には、前記変数Ｒは、数式６の演算を行って求めることができる。
【００３２】
【数６】
2007189692.tif 000008
【００３３】
前記の加算演算と共に、楕円曲線Ｅ上の任意の点Ｐに任意の定数ｋを乗算した数Ｑ（＝ｋ・Ｐ）を求めるスカラー乗算演算も、ＥＣＣで行う重要な演算のうち一つである。ここで、定数ｋは、一般的に秘密キーであって、Ｑは、Ｐをｋ回乗算して求めることができる。Ｑ及びＰ値を利用してｋを求めるためには、離散対数演算を行わなければならない。離散対数演算は、有限フィールドに楕円曲線の特性を適用して行われ、暗号プロトコルの秘密性の基礎となる。
【００３４】
スカラー乗算演算も、ポイント演算、言い換えれば、有限フィールド演算を基本とする。スカラー乗算演算を行うために、ＭＰＬＡが多く使用される。ＭＰＬＡは、本来、簡単な電力分析の攻撃に対応するために考案されたが、現在は、ＥＣＣのあらゆるフィールドで行うスカラー乗算演算だけでなく、ＲＳＡで行うモジュール指数演算にも適用される普遍的なアルゴリズムである。
【００３５】
以下では、ＥＣＣでＭＰＬＡを利用したスカラー乗算演算について説明する。
ＭＰＬＡでは、まず、２つの変数を数式７のように定義する。
【００３６】
【数７】
2007189692.tif 000009
【００３７】
ここで、任意の整数ｋは、複数の２進ビット（ｋｔ−１，ｋｔ−２，…，Ｋ１，Ｋ０）で表示し、ｋｉは、前記複数の２進ビットの一つに対応し、ｋｔ−１は、常に１の値を有する。数式７に表現された二つの変数間の関係は、数式８のように再表現できる。
【００３８】
【数８】
2007189692.tif 000010
【００３９】
数式８に表示された二つの変数間の関係、及び変数ｊ値による２進ビット（ｋj）の値を利用すれば、二つの変数の関係についての他の数学的な表現を数式９のように表示できる。
【００４０】
【数９】
2007189692.tif 000011
【００４１】
数式３ないし数式９を利用すれば、スカラー乗算演算の結果Ｑ（＝ｋＰ）を求める一般的なＭＰＬＡは、下記のように表現できる。
ｉｎｐｕｔ：
ｋ＝(ｋｔ−１,ｋｔ−２,…，Ｋ１,Ｋ０)２， with  ｋｔ−１＝１,Ｐ（ｘ１,ｙ１）
ｏｕｔｐｕｔ：ｋＰ（ｘ３，ｙ３）
１．Ｐ１←Ｐ
２．Ｐ０←２Ｐ
３．ｆｏｒ ｉ＝ｔ−２ ｔｏ ０，ｄｏ
３．１  ｉｆ  ｋｉ＝１ ｔｈｅｎ
Ｐ０←２Ｐ０ ；    Ｐ１←Ｐ１+Ｐ０
３．２  ｅｌｓｅ
Ｐ０←Ｐ１+Ｐ０；  Ｐ１←２Ｐ０
ｅｎｄ ｆｏｒ；
４．ｒｅｔｕｒｎ  ｋＰ（ｘ３，ｙ３）
【００４２】
ステップ３で変数ｉがｔ−２から始めるのは、既にステップ１及びステップ２で、変数ｉがｔ−１である場合について考慮したためである。加算演算（Ｐ１＋Ｐ０）は、数式３ないし数式６の方程式を行って得られ、ここで、ステップ１及びステップ２に示すように、Ｐ１とＰ０とが異なるので、加算演算（Ｐ１＋Ｐ０）には、数式３及び数式５が適用される。
【００４３】
数式７に表示された二つの変数Ｌｊ及びＨｊの関係を考慮すれば、暗号システムで行われる演算に所定のフォールトが流入されていない場合、二つの変数ＬｊとＨｊとの差は、常に１となる。このような事実は、前述した一般的なＭＰＬＡに適用される任意の変数及びＰ１とＰ０との差が常にＰとなるということと同じ意味である。
【００４４】
２つのランダムフォールトが流入されたにもかかわらず、２つの任意の変数Ｐ１とＰ０との差がＰとなる可能性、すなわち、フォールトが流入されていないのと同じ結果が発生する可能性はほぼ０に近い。このような事実は、当業者には自明な事実として受入れられるので、前記のような特別な場合については、ここでは考慮しない。
【００４５】
一般的なＭＰＬＡに適用される任意の変数、Ｐ１、Ｐ０及びＰが、同じ条件を異ならせて表現した数式１０の３つの数式の一つを満足すれば、フォールトが流入されていないと判断できる。
【００４６】
【数１０】
2007189692.tif 000012
【００４７】
一方、ＥＣＣでフォールトの流入如何を判断する条件を、ＲＳＡで行うモジュール指数演算を行うアルゴリズムに適用するためには、数式１１の方程式を考慮しなければならない。
【００４８】
【数１１】
2007189692.tif 000013
【００４９】
ここで、数式１１の三つの変数Ｍ、Ｒ１及びＲ０は、数式１０の三つの変数Ｐ、Ｐ１及びＰ０にそれぞれ対応する。数式１０及び数式１１は、当業者ならば、誰でも容易に得られるので、ここではその具体的な説明を省略する。
【００５０】
ＥＣＣでは、前記三つの変数Ｐ、Ｐ１及びＰ０が、数式１０に表示された同じ意味の３つの数式のうち一つを満足するか否かを検査し、ＲＳＡでは、前記三つの変数Ｍ、Ｐ１及びＰ０が、数式１１に表示された同じ意味の３つの数式のうちの一つを満足するか否かを検査することによって、演算中にフォールトが流入されたか否かを判断することができる。
【００５１】
本発明では、数式１０及び数式１１に表示された三つの変数間の関係を検査するステップを、ＥＣＣ及びＲＳＡに適用されるアルゴリズムに含めることによって、システムの実行能力を低下させずとも多様な種類の暗号システムに容易に適用できるアルゴリズムを提案する。
【００５２】
前述の数式１０及び数式１１の条件を検査するステップをアルゴリズムに適用する位置によって、スカラー乗算演算中に検査を実施する正規検査及びランダム検査と、スカラー乗算演算が全て終わった後、演算の結果値が出力される前に検査を実施する最終検査の３つの検査方法を提案する。
【００５３】
正規検査は、繰り返される全てのスカラー乗算演算で毎回検査を実施し、ランダム検査は、繰り返されるスカラー乗算演算のうち選択された任意のスカラー乗算演算でのみ検査を実施する。最終検査は、繰り返されるスカラー乗算演算が全て終わった直後、演算結果を出力する前に検査を実施する。
【００５４】
まず、正規検査を適用するＭＰＬＡの実施形態について説明する。
図３は、本発明に係るＤＦＡに対抗するＭＰＬＡの第１実施形態を示すフローチャートである。
図３に示すように、正規検査を適用するアルゴリズム３００は、初期化ステップ３１０、反復演算ステップ３３０及び伝送ステップ３５０を含む。
【００５５】
初期化ステップ３１０は、反復演算変数ｉの初期値としてｔ−１（ｔは、整数）を設定し、基本ポイントＰ及びスカラーｋを受信するステップ３１１及び第１変数（Ｐ１）を基本ポイントＰに置換し、第２変数（Ｐ０）を２倍の基本ポイント２Ｐに置換するステップ３１２を備える。スカラーｋは、２進ビットで(ｋｔ−１,ｋｔ−２,…，Ｋ１,Ｋ０)２のように表示することができる。
【００５６】
反復演算ステップ３３０は、スカラーｋと基本ポイントＰとを乗算した値Ｑを演算するために、２つの変数Ｐ１とＰ０と利用した繰り返されるスカラー乗算演算を行い、フォールトが流入されたか否かを検査するために、乗算演算中に２つの変数と基本ポイントＰとの間の関係を検査し、検査結果によってＱを出力するか、または警告信号ＳＴＯＰを出力する。
【００５７】
反復演算ステップ３３０は、変数置換ステップ３３１、フォールト流入検査、措置ステップ３４１、及び反復演算変数ｉが０より小さいか否かを判断するステップ３４５を含む。変数置換ステップ３３１は、反復演算変数ｉの値を１ずつ減少させるステップ３３２、反復演算変数ｉの値によって、スカラーｋに対応する２進ビットｋｉの値が１であるか否かを判断するステップ３３３、第１変数置換ステップ３３４及び第２変数置換ステップ３３５を含んでスカラー乗算演算を行う。第１変数置換ステップ３３４は、ｋｉの値が１である場合に適用され、第１変数Ｐ１は、第１変数Ｐ１と第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換し、２変数Ｐ０は、第２変数Ｐ０の２倍である値２Ｐ０に置換する。第２変数置換ステップ３３５は、ｋｉの値が１ではない場合に適用され、第１変数Ｐ１を第２変数Ｐ０の２倍である値２Ｐ０に置換し、第２変数Ｐ０を、第１変数Ｐ１と第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換する。
【００５８】
フォールト流入検査及び措置ステップ３４１は、第１変数Ｐ１、２変数Ｐ０及び基本ポイントＰの値が、それらの間に所定の関係を満足するか否かを検査して乗算演算を続けると決定するか、または乗算演算を中止し、警告信号ＳＴＯＰを発生させる。
【００５９】
フォールト流入検査及び措置ステップ３４１は、フォールト流入検査ステップ３４２及び措置ステップ３４３を含む。フォールト流入検査ステップ３４２は、変数置換ステップ３３１で置換された２つの変数Ｐ１,Ｐ０及び最初の基本ポイントＰが、数式１０で表現した３つの数式Ｐ０-Ｐ１=Ｐ、Ｐ０-Ｐ=Ｐ１及びＰ１+Ｐ=Ｐ０のうち一つを満足するか否かを検査し、検査結果、数式１０に表現された数式のうち一つを満足する場合には、反復演算変数ｉが０であるか否かを判断するステップ３４５に進む。措置ステップ３４３は、数式１０に表現された数式のうち何れの一つの数式も満足しない場合には、次の乗算演算を中断させるか否かを決定し、次の乗算演算を中断すると決定した場合には、警告信号ＳＴＯＰを発生させ、次の乗算演算を続けると決定した場合には、反復演算変数ｉが０であるか否かを判断するステップ３４５に進む。
【００６０】
乗算演算を中止すると決定される前には、反復演算変数ｉが０となるまで変数置換ステップ３３１を繰り返して行う。
伝送ステップ３５０は、所定の演算装置にＱを伝達する。
【００６１】
次いで、ランダム検査を適用するＭＰＬＡの他の実施形態について説明する。
図４は、本発明に係るＤＦＡに対抗するＭＰＬＡの第２実施形態を示すフローチャートである。
図４に示すように、ランダム検査を適用するアルゴリズム４００は、初期化ステップ４１０、反復演算ステップ４３０及び伝送ステップ４５０を含む。
【００６２】
まず、スカラーｋを２進ビットで(ｋｔ−１,ｋｔ−２,…，Ｋ１,Ｋ０)２のように表示する。初期化ステップ４１０及び伝送ステップ４５０は、図３に示す第１実施形態３００の初期化ステップ３１０及び伝送ステップ３５０と同じであるので、その説明を省略する。
【００６３】
反復演算ステップ４３０は、変数置換ステップ４３１、変数チェックの値によってフォールト流入検査を行うか否かを決定するステップ４３６、フォールト流入検査及び措置ステップ４４１、及び反復演算変数ｉが０より小さいか否かを判断するステップ４４５を含む。
変数置換ステップ４３１は、図３に示す変数置換ステップ３３１と同じ機能を行うので、その説明を省略する。
【００６４】
変数のチェックに割り当てられた値によってフォールト流入検査を行うか否かを決定するステップ４３６は、変数のチェックに任意の数を割り当てるステップ４３７、変数のチェックに割り当てられた値が所定の基準値と一致するか否かを判断するステップ４３８を含む。変数チェックに割り当てられた値が基準値と一致する場合には、フォールト流入検査及び措置ステップ４４１を行い、そうでない場合には、乗算演算を続ける（４４５）。この点が、図３に示す正規検査と異なる点である。正規検査は、スカラー乗算演算が実行される演算ごとにフォールト流入検査を行うが、図４に示すランダム検査は、変数であるチェックに割り当てられる値をランダムに定め、フォールト流入如何を検査する場合も、変数チェックに割り当てられた値によって決定されるため、図３に示す方法に比べて、フォールト流入検査の回数が減る。図４では、基準値として１を仮定したが、２進数を使用するシステムでは、０とすることも可能であり、システムによって適応的に変更させることができる。
【００６５】
フォールト流入検査及び措置ステップ４４１は、図３に示すフォールト流入検査及び措置ステップ３４１と同じ過程を行うので、その説明を省略する。
ステップ４４５の判断結果、反復演算変数ｉが０より小さくない場合には、変数置換ステップ４３１に進んで、スカラー乗算演算を続ける。
【００６６】
最後に最終検査を適用するＭＰＬＡのさらに他の実施形態を説明する。
図５は、本発明に係るＤＦＡに対抗するＭＰＬＡの第３実施形態を示すフローチャートである。
図５に示すように、最終検査を適用するアルゴリズム５００は、初期化ステップ５１０、反復演算ステップ５３０及び伝送ステップ５５０を含む。
【００６７】
まず、スカラーｋを２進ビットで(ｋｔ−１,ｋｔ−２,…，Ｋ１,Ｋ０)２のように表示する。初期化ステップ５１０は、図３に示す第１実施形態３００の初期化ステップ３１０、及び図４に示す第２実施形態４００の初期化ステップ４１０と同じであるので、その説明を省略する。
反復演算ステップ５３０は、２つの変数を利用した繰り返されるスカラー乗算演算を行って、スカラーｋと基本ポイントＰとを乗算した値Ｑを演算する。
【００６８】
反復演算ステップ５３０は、反復演算変数ｉの値を１ずつ減少させるステップ５３１、反復演算変数ｉの値によってスカラーｋに対応する２進ビットｋｉの値が１であるか否かを判断するステップ５３２、第１変数置換ステップ５３３、第２変数置換ステップ５３４及び反復演算変数ｉが０より小さいか否かを判断するステップ５３５を含む。第１変数置換ステップ５３３は、ｋｉの値が１である場合に適用され、第１変数Ｐ１を、第１変数Ｐ１と第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換し、第２変数Ｐ０を、第２変数Ｐ０の２倍である値２Ｐ０に置換する。第２変数置換ステップ５３４は、ｋｉの値が１ではない場合に適用され、第１変数Ｐ１を、第２変数Ｐ０の２倍である値２Ｐ０に置換し、第２変数Ｐ０を、第１変数Ｐ１と第２変数Ｐ０とを合算した値Ｐ１＋Ｐ０に置換する。
【００６９】
ステップ５３５の判断結果、反復演算変数ｉが０より小さくない場合には、反復演算変数ｉの値を１ずつ減少させるステップ５３１に進み、そうでない場合には、フォールト流入検査及び措置ステップ５５０を行うステップに進む。
フォールト流入検査及び措置ステップ５５０は、２つの変数と基本ポイントＰとの間に所定の関係を分析して、フォールトが流入されたか否かを検査し、検査結果によって演算結果Ｑまたは警告信号ＳＴＯＰを出力する。
【００７０】
前記フォールト流入検査及び措置ステップ５５０は、フォールト流入検査ステップ５２２、演算結果Ｑを出力するステップ５５２及び警告信号ＳＴＯＰを発生させるステップ５５３を含む。フォールト流入検査ステップ５５１は、変数置換ステップ３３１で置換された２つの変数Ｐ１,Ｐ０と最初の基本ポイントＰとの関係が、数式１０に表示した３つの式Ｐ０-Ｐ１=Ｐ、Ｐ０-Ｐ=Ｐ１及びＰ１+Ｐ=Ｐ０のうちいずれか一つを満足するか否かを検査する。演算結果Ｑを出力するステップ５５２は、数式１０に表示された数式のうち何れか一つの数式を満足する場合には、演算結果Ｑを出力する。警告信号ＳＴＯＰを発生させるステップ５５３は、数式に表示された数式のうち何れかの一つの数式も満足しない場合には、警告信号ＳＴＯＰを発生させる。
【００７１】
図３ないし図５に示す措置ステップ３４３、４４３、５５３で発生する警告信号ＳＴＯＰを利用して行える措置は非常に多く、下記にその例を記載する。
１．実行中である演算を中断し、演算に使用したレジスタの値をセットまたはリセットさせ、出力を０に設定する。
２．韓国に出願された特許出願番号２００５−００２２９２９号で提案したように、秘密キー値にフォールト拡散を適用させた後に演算を続ける。
３．韓国に出願された特許出願番号２００５−００１８４２９号で提案したように、出力点を変形させて使用する。
【００７２】
図３に示す正規検査を適用するＭＰＬＡは、フォールトが流入されるやいなや措置が行えるので、秘密等級の高い暗号システムへの適用に適している。一方、暗号システムのパフォーマンスは低くなるが、図１に示す従来の技術である“ｃｏｍｐｕｔｅ ｔｗｉｃｅ ａｎｄ ｃｈｅｃｋ”の接近法に比べてはパフォーマンスが高い。
【００７３】
図４に示すランダム検査を適用するＭＰＬＡは、正規検査を適用するＭＰＬＡの長所を有しつつも、パフォーマンスをあまり低下させない。
【００７４】
図５に示す最終検査を適用するＭＰＬＡは、正規検査及びランダム検査を適用するＭＰＬＡに比べて、パフォーマンスの低下が最も少ないという長所がある。
しかし、本発明に係るＭＰＬＡの最大の長所は、ＤＦＡに能動的に対応しうるという点であり、さらに、電力分析による攻撃に対しても対応しうる。
【００７５】
図３ないし図５に本発明に係るＭＰＬＡの３つの実施形態を示した。前記実施形態は、ＥＣＣで適用されるスカラー乗算演算に適用される場合について説明されている。しかし、
１．図３ないし図５に示す図、
２．それらについての説明及び
３．ＥＣＣでのスカラー乗算演算とＲＳＡでのモジュール指数演算との関係
を考慮すれば、当業者ならば、誰でも前記ＭＰＬＡをＲＳＡのモジュール指数演算に使用できるＭＰＬＡに変形させることができる。
【００７６】
以上のように、図面及び明細書で最適の実施形態が開示された。ここでは特定の用語が使用されたが、これは単に、本発明を説明するための目的で使用されたものであり、意味限定や特許請求の範囲に記載された本発明の範囲を制限するために使用されたものではない。したがって、当業者ならば、これから多様な変形及び均等な他の実施形態が可能であるという点が理解できるであろう。したがって、本発明の真の技術的保護範囲は、特許請求の範囲の技術的思想によって決めなければならない。
【産業上の利用可能性】
【００７７】
本発明に係るＭＰＬＡは、ＥＣＣ及びＲＳＡなどの多様な暗号システムに利用可能である。
【図面の簡単な説明】
【００７８】
【図１】ＤＦＡに対応する従来のＣＴ＆Ｃ方法についての信号フローチャートである。
【図２】ＤＦＡに対応する従来のＣＯＰ方法についての信号フローチャートである。
【図３】本発明に係るＤＦＡに対抗するＭＰＬＡの第１実施形態を示すフローチャートである。
【図４】本発明に係るＤＦＡに対抗するＭＰＬＡの第２実施形態を示すフローチャートである。
【図５】本発明に係るＤＦＡに対抗するＭＰＬＡの第３実施形態を示すフローチャートである。
【図１】
2007189692.tif 000014
【図２】
2007189692.tif 000015
【図３】
2007189692.tif 000016
【図４】
2007189692.tif 000017
【図５】
2007189692.tif 000018