高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法及び加算演算装置
【課題】高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法及び加算演算装置を提供する。
【解決手段】楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、加算演算の結果の第１座標値を算出するステップと、第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、加算演算の結果の第２座標値を算出するステップと、を含む素数有限領域におけるポイント加算演算方法である。第１ポイント及び第２ポイントについての素数有限領域における加算演算は、第１ポイント及び第２ポイントの第１座標値及び第２座標値の差を反映する。これにより、高速モンゴメリ電力ラダーアルゴリズムを利用する暗号化システムで正確な欠陥検出動作を行える。
【解決手段】楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、加算演算の結果の第１座標値を算出するステップと、第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、加算演算の結果の第２座標値を算出するステップと、を含む素数有限領域におけるポイント加算演算方法である。第１ポイント及び第２ポイントについての素数有限領域における加算演算は、第１ポイント及び第２ポイントの第１座標値及び第２座標値の差を反映する。これにより、高速モンゴメリ電力ラダーアルゴリズムを利用する暗号化システムで正確な欠陥検出動作を行える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化方法に係り、特に高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法に関する。
【背景技術】
【０００２】
情報化社会の到来による情報伝送媒体の発達と共に、情報の安全性を保証するための暗号化及び復号化方案も多角的に摸索されている。そのうち、ＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号化システム及び楕円曲線暗号化（ＥＣＣ：Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ）システムのような公開キー形式の暗号化方式が広く使われている。整数除算(integer division)に対するアルゴリズムが定義されないので、十分に大きい整数を公開キーとして使用することによって、公開キー形式の暗号化方式は、システムの安全性を保証しうる。
【０００３】
特に、ＥＣＣシステムは、比較的に短いキーサイズでも高い安全性が確保でき、スマートカード及び電子署名に広く使われている。ＥＣＣシステムは、楕円曲線と呼ばれる数式によって定義される特殊な加算法を基盤として暗号化／復号化する暗号化方式である。
具体的に、ＥＣＣ方法は、任意の楕円曲線Ｅと楕円曲線Ｅ上の一点Ｐとをシステムパラメータとして使用する。暗号化通信を所望するユーザ１は、ランダムに整数ｋを生成し、ｋとＰとを乗算してＱ（＝ｋｘＰ）を生成する。ユーザ１は、Ｑを公開キーとして公開し、ｋをユーザ１の秘密キーとして安全に保存する。
【０００４】
逆に、ユーザ１にメッセージＭを秘密裏に伝送しようとするユーザ２は、まずランダムに整数ｄを生成し、システムパラメータのうち一つであるＰと整数ｄとを乗算してＡ（＝ｄｘＰ）を生成する。ユーザ１が提供した公開キーＱと伝送しようとするメッセージＭとを使用してＢ（＝Ｍ＋ｄｘＱ）を生成する。最後に、ユーザ２は、最終結果暗号文Ａ,Ｂをユーザ１に伝送する。
ユーザ２から暗号文Ａ,Ｂを伝達されたユーザ１は、自身の秘密キーｋを使用してｋｘＡを計算した後、次の数式（１）のような演算を行ってメッセージＭを復元する。
【０００５】
【数１】
【０００６】
このようなＥＣＣシステムを攻略するための方案として、演算されている変数値の差を利用して暗号システムの秘密キーを探し出す差分欠陥分析（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｆａｕｌｔ Ａｎａｌｙｓｉｓ：ＤＦＡ）が広く知られている。ＤＦＡは、欠陥を暗号システムに投入し、投入された欠陥に対応する演算結果を分析し、暗号システムの秘密キーを探す方法である。
【０００７】
暗号システムは、所定の演算を行う時にレジスターに保存された値を参照するが、レジスターに保存される値または保存された値は、欠陥によって変更される。したがって、暗号システムの演算結果に、欠陥によって変更された値に対応するエラーが含まれる。
エラーを含んで出力される演算結果を解釈することによって、秘密キーについての情報は露出される。したがって、ＤＦＡに対応するために、ＥＣＣシステムで使われる色々な方法が提案されている。
【０００８】
図１は、ＤＦＡに対応するＣＴ＆Ｃ（Ｃａｌｃｕｌａｔｅ Ｔｗｉｃｅ ａｎｄ Ｃｈｅｃｋ）方法を示すフローチャートである。
ＣＴ＆Ｃ方法１００は、まず、楕円曲線のうち任意の一点Ｐを選択した後（１１０）、Ｐに任意の整数ｋを乗算して第１比較値Ｑ１を求め（１２０）、Ｐに整数ｋを乗算して第２比較値Ｑ２を求める（１３０）。このとき、所定の整数ｋは、秘密キーを意味する。
【０００９】
次いで、第１比較値Ｑ１と第２比較値Ｑ２との大きさを比較し（１４０）、第１比較値Ｑ１と第２比較値Ｑ２とが同一ならば、乗算演算にいかなる欠陥も発生されていないと判断して、第１比較値Ｑ１及び第２比較値Ｑ２のうち一つが演算結果Ｑとして出力される（１５０）。一方、第１比較値Ｑ１と第２比較値Ｑ２とが同一でなければ、乗算演算に欠陥が発生されたと判断して、演算結果Ｑの代わりに警告信号が出力される（１６０）。
【００１０】
図２は、ＤＦＡに対応するＣＯＰ（Ｃｈｅｃｋ ｔｈｅ Ｏｕｔｐｕｔ Ｐｏｉｎｔ）方法を示すフローチャートである。
ＣＯＰ方法２００は、まず楕円曲線のうち任意の一点Ｐを選択し（２１０）、Ｐに所定の整数ｋを乗算して比較値Ｑを求める（２２０）。このとき、所定の整数ｋは、秘密キーを意味する。
【００１１】
次いで、比較値Ｑが楕円曲線Ｅの一点であるか否かを判断して（２３０）、比較値Ｑが楕円曲線Ｅの一点ならば、乗算演算にいかなる欠陥も発生されていないと判断して、比較値Ｑが出力される（２４０）。一方、比較値Ｑが楕円曲線Ｅの一点でなければ、乗算演算中に欠陥が発生されたケースに該当すると判断して、比較値Ｑの代わりに警告信号が出力される（２５０）。
【００１２】
しかし、図１のＣＴ＆Ｃ方法１００は、同じ乗算計算を２回もしなければならないという短所があり、図２のＣＯＰ方法２００は、図１のＣＴ＆Ｃ方法１００に比べて計算が簡単であるという長所があるが、その適用範囲が制限的であるだけでなく、符号の変わる欠陥を利用した攻撃に対応する場合には、システムの実行能力が非常に低下するという短所がある。したがって、モンゴメリ電力ラダーアルゴリズム（ＭＰＬＡ：Ｍｏｎｔｇｏｍｅｒｙ Ｐｏｗｅｒ Ｌａｄｄｅｒ Ａｌｇｏｒｉｔｈｍ）または高速ＭＰＬＡ（ＦＭＰＬＡ：Ｆａｓｔ Ｍｏｎｔｇｏｍｅｒｙ Ｐｏｗｅｒ Ｌａｄｄｅｒ Ａｌｇｏｒｉｔｈｍ）を利用して、ＤＦＡに対応する方案が摸索されている。
【００１３】
前述したＥＣＣ方法を参照すれば、Ｐ及びＱ値を通じてｋを求めるためには、離散対数演算が行われねばならない。離散対数演算は、有限フィールドに楕円曲線の特性を適用して行われ、暗号プロトコルの秘密性の基礎となる。簡単には、離散対数演算とは、Ｑ＝ｋｘＰで、ＱとＰとからｋを求める演算である。
【００１４】
したがって、ＥＣＣ方法でスカラー積演算は、重要な演算のうちの一つであるということが分かる。ＭＰＬＡとは、有限フィールドにおけるスカラー積演算を行う方法のうちの一つである。以下では、ＭＰＬＡについてさらに詳細に説明する。
一般的なＭＰＬＡでは、まず、２個の変数を次の数式（２）のように定義する。
【００１５】
【数２】
【００１６】
数式（２）の二変数間の関係に対する他の数学的表現は、次の数式（３）の通りである。任意の整数ｋは、複数の２進ビット（ｋ＝（ｋｔ−１，．．．，ｋ１，ｋ０）２、ｔは、整数、以下、同一）で表現され、ｋｉは、反復媒介変数ｉ（ｉは、整数、以下、同一）に対応するビットの値を表す。このとき、ｋｔ−１は、常に“１”の値を有する。数式（２）に表現された二変数間の関係は、次の数式（３）のように再整理されうる。
【００１７】
【数３】
【００１８】
数式（３）に表示された二変数間の関係を変数ｊ値によって異ならせて表現すれば、次の数式（４）のように表現しうる。
【００１９】
【数４】
【００２０】
数式（４）の誘導過程は、本発明の属する技術分野の当業者に広く知られた事項であるところ、それについての詳細な説明は省略する。ＬｊとＨｊとは、後述する図３及びアルゴリズム１で、ＥＣＣシステムにおける楕円曲線上の２ポイントであるＰ１及びＰ２にマッピングされる。
【００２１】
図３は、ＭＰＬＡを利用してＥＣＣ方法におけるスカラー積演算を行う方法を示すフローチャートである。
図３を参照すれば、ＭＰＬＡを利用したスカラー積演算方法３００は、まず、基本ポイントＰとスカラーｋ（ｋは、整数、以下、同一）とを受信する（Ｓ３０１）。次いで、スカラー積を反復演算するための変数が設定される（Ｓ３０３）。
【００２２】
ｋは、数式（２）で前述したように設定される。また、第１変数Ｐ１は、基本ポイントＰに、そして、第２変数Ｐ２は、基本ポイントＰの２倍、すなわち２ｘＰに設定される。反復媒介変数ｉは、ｔ−１に初期化される。
【００２３】
変数が設定された後には、反復演算によってスカラー積Ｑ＝ｋｘＰが計算される。すなわち、反復媒介変数ｉを０まで減少させつつ（Ｓ３０５、Ｓ３１３）、それぞれの２進ビットｋｉによって（Ｓ３０７）、第１及び第２変数を再設定（Ｓ３１０、Ｓ３１１）する過程を反復し、ｉが０まで減少した場合（Ｓ３１３）の第１変数Ｐ１をスカラー積Ｑ＝ｋｘＰとして出力する（Ｓ３１５）。
【００２４】
このとき、“Ｐ２←２Ｐ２”及び“Ｐ１←２Ｐ１”は、楕円曲線ポイントの２倍演算（例えば、２を乗算すること）を意味し、“Ｐ１←Ｐ１＋Ｐ２”及び“Ｐ２←Ｐ１＋Ｐ２”は、楕円曲線ポイントの加算演算を意味する。ところが、図３の一般的なＭＰＬＡは、それぞれの反復演算で加算演算と２倍演算とが行われるので、性能において、大きい劣化を発生させる。このような劣化を防止するために、Ｙ座標形態の計算が除外されたループ計算を行った後、Ｙ座標を再定義するＦＭＰＬＡを利用したスカラー積演算方法が提案された。
【００２５】
ＦＭＰＬＡを通じて楕円曲線上の２ポイント（Ｐ１（Ｘ１,Ｚ１）、Ｐ２（Ｘ２,Ｚ２））の２倍演算及び加算演算を行うための、素数有限フィールド(prime finit field)における２倍演算及び加算演算は、それぞれ次の数式（５）及び数式（６）で定義される。
【００２６】
【数５】
【００２７】
【数６】
【００２８】
数式（５）及び数式（６）を参照すれば、計算中にＹ座標が含まれないということが分かる。
ところが、数式（６）の加算演算は、２ポイント（Ｐ１（Ｘ１,Ｚ１）、Ｐ２（Ｘ２,Ｚ２））のＺ座標の差（ＺＤ＝Ｚ２−Ｚ１）が“１”であることを前提している。しかし、ＦＭＰＬＡを利用した欠陥検索方法は、２ポイントの差を利用して欠陥の発生如何を検出する。
【００２９】
したがって、数式（６）の加算演算を、ＦＭＰＬＡを利用する欠陥検出方法に使用する場合、ＥＣＣシステムは、誤った欠陥発生分析結果を導出する恐れがある。欠陥分析のエラーは、暗号化システムを無力化させて深刻な問題をもたらす。
【発明の開示】
【発明が解決しようとする課題】
【００３０】
本発明が解決しようとする技術的課題は、ＦＭＰＬＡを利用する欠陥検出動作で、エラーなしに欠陥を検出するための素数有限領域におけるポイント加算方法を提供することである。
本発明が解決しようとする他の技術的課題は、ＦＭＰＬＡを利用する欠陥検出動作で、エラーなしに欠陥を検出するための素数有限領域におけるポイント加算演算装置を提供することである。
【課題を解決するための手段】
【００３１】
前記課題を達成するための本発明の実施形態による素数有限領域におけるポイント加算演算方法は、所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するステップと、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するステップと、を含む。
【００３２】
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算は、前記第１ポイント及び前記第２ポイントの第１座標値と第２座標値との差を反映する。
前記ＦＭＰＬＡを利用する欠陥検出動作は、ＥＣＣシステムに適用される。前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値である。
【００３３】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の通りである。
【００３４】
【数７】
【００３５】
前記課題を達成するための本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法で、前記第２ポイントの前記第２座標値は、所定数に固定される。前記第２ポイントの第２座標値は、“１”である。
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,１）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（１−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の通りである。
【００３６】
【数８】
【００３７】
前記他の課題を達成するための本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置は、第１座標算出部及び第２座標算出部を備える。
【００３８】
第１座標算出部は、所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出する。第２座標算出部は、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出する。
【００３９】
前記第１座標算出部及び前記第２座標算出部は、前記第１ポイント及び前記第２ポイントの第２座標値の差を反映して、前記第１座標値及び前記第２座標値を算出する。前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値である。
【００４０】
前記第１座標算出部は、第１ないし第７乗算器、第１ないし第４加算器、第１及び第２算出手段及び第１減算器を備える。前記第２座標算出部は、第２１ないし第２３乗算器、第２１減算器及び第２１自乗器を備える。
【００４１】
前記他の課題を達成するための本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置は、前記第２ポイントの第２座標値が“１”である場合についての素数有限領域におけるポイト加算演算を行う。
【発明の効果】
【００４２】
本発明による素数有限領域におけるポイント加算方法及び加算演算装置によれば、ＦＭＰＬＡを利用する暗号化システムで正確な欠陥検出動作を行える。
【発明を実施するための最良の形態】
【００４３】
本発明と本発明の動作上の利点及び本発明の実施によって達成される目的を十分に理解するためには、本発明の望ましい実施形態を例示する添付図面及び図面に記載された内容を参照せねばならない。
以下、添付した図面を参照して本発明の望ましい実施形態を説明することによって、本発明を詳細に説明する。各図面に提示された同じ参照符号は、同じ部材を表す。
【００４４】
本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法を説明する前に、ＦＭＰＬＡを利用する欠陥検出方法についてさらに詳細に説明する。
ＦＭＰＬＡを利用する欠陥検出方法を具現するために、まず数式（２）及び数式（３）から次の数式（７）が誘導される。
【００４５】
【数９】
次いで、数式（７）から次の数式（８）が誘導される。
【００４６】
【数１０】
【００４７】
Ｈｊ＝Ｌｊ＋１は、数式（２）で表した。
以前計算で欠陥がなかったということを確認するために、判断を行う間に、計算にＨｊとＬｊ値とが含まれねばならない。Ｙ座標を含まず、二点であるＨｊとＬｊとの和をＸ座標で計算するモンゴメリ方法は、これらの二点の差に関する情報に基づく。
【００４８】
このような特徴は、次のような欠陥チェック動作を誘導するために使われ、これを可能にするために、かつパワートラック分析による分別不可能性(indistinguishability)の動作平衡(operation equilibrium)を満足するために、次のように、ｋｊ＝０とｋｊ＝１との２つを考慮せねばならない。
まず、ｋｊ＝１の場合、欠陥チェック動作は、次の順序によって行われる。
１．次の数式（９）を利用して２倍演算によってＬｊ−１を計算する。
【００４９】
【数１１】
【００５０】
２．１での結果から、加算演算によってＬｊ＋１を計算する。
３．Ｌｊ＋１＝Ｈｊであるかをチェックする。ここで、Ｈｊは、以前に計算された値である。
【００５１】
次いで、Ｋｊ＝０である場合、欠陥チェック動作は、次の順序によって行われる。
１．次の数式（１０）を利用して、２倍演算によって２Ｈｊ＋１を計算する。
【００５２】
【数１２】
【００５３】
２．Ｌｊを考慮して、加算演算によってＨｊ＋１を計算する。
３．Ｈｊ＋１＝２Ｈｊ＋１であるかを確認する。ここで、２Ｈｊ＋１は、以前に計算された値である。
【００５４】
欠陥が発生されていない場合、ＬｊとＨｊとの差は、常に“１”である。したがって、前記のような演算過程で欠陥が発生されていないならば、Ｌｊ＋１＝ＨｊまたはＨｊ＋１＝２Ｈｊ＋１である。また、二つの場合で何れもＨｊとＬｊとがチェック過程に含まれ、これは、計算された二ポイントで何れも欠陥が存在するか否かチェックされたということを意味する。
【００５５】
以下では、前述したＦＭＰＬＡを利用した新たな方式の欠陥チェック方法が適用される多様な実施形態が提案される。これは、欠陥チェックの実行ステップによって分けられる。すなわち、スカラー積演算中に欠陥の発生如何が判断される定期チェックとランダムチェック、そしてスカラー積演算が完了した後に演算結果が出力される前に欠陥の発生如何が判断される最終チェック方法が提案される。
【００５６】
さらに具体的に説明すれば、定期チェック方法は、欠陥が発生されたか否かがスカラー積演算が反復される度に行われる。ランダムチェック方法は、スカラー積演算が反復される度に行われず、ランダムに選択されるスカラー積演算に対して、スカラー積演算が行われた後に行われる。
【００５７】
図４は、定期チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
図４を参照すれば、定期チェック方法が適用された欠陥チェック方法４００は、スカラー積演算が行われる反復区間ごとに定期的にチェック動作が行われる方法である。欠陥チェック方法４００は、基本ポイントＰとスカラーｋとを受信して（Ｓ４０１）、スカラー積Ｑ（＝ｋｘＰ）を出力する（Ｓ４２９）。
【００５８】
ここで、基本ポイントＰは、所定の楕円曲線上のポイントであって、ハードウェア具現時にＥＰＲＯＭに保存される。スカラーｋは、数式（２）で説明した通りである。欠陥チェック方法４００は、基本ポイントＰとスカラーｋとを受信した後（Ｓ４０１）、暗号化のためのパラメータまたはポイントを初期化するか、または設定する（Ｓ４０３）。スカラーｋの２進ビットｋｉによる反復的な演算のために、本発明では、変数が使われて、変数は、所定の規則によって初期化されるか、または設定される（Ｓ４０３またはＳ４０７）。
【００５９】
まず、基本ポイントＰを利用して第１ポイントＰ１と第２ポイントＰ２とが初期化される。具体的に、第１ポイントＰ１は、基本ポイントＰに初期化され、第２ポイントＰ２は、基本ポイントＰの２倍に初期化される。暗号化方法４００に使われるパラメータまたはポイントが初期化された後には、反復的な演算を行ってスカラー積Ｑを計算する（Ｓ４０５ないしＳ４１３及びＳ４２７）。
【００６０】
２進ビットで表現されるスカラーｋの全てのビットについての反復演算のために、本発明の実施形態では、反復演算変数ｉを０まで減少させつつ（Ｓ４０５）、２進ビット値ｋｉについての反復演算が行われる。
【００６１】
図４の欠陥チェック方法４００では、再設定するステップが完了する度に欠陥が発生されたか否かチェックされるので、欠陥が発生されたか否が定期的にチェックされる。以下では、欠陥が発生されたか否かをチェックする動作について説明する（Ｓ４１５ないしＳ４２３）。
【００６２】
まず、２進ビットｋｉが“１”であるか否かが決定される（Ｓ４１５）。２進ビットｋｉが“１”であれば、第１変数Ｔ１の２倍を第１変数Ｔ１に再設定し、第１変数Ｔ１に応答して決定される第１ポイントＰ１と基本ポイントＰとの和を第１変数Ｔ１に再設定する（Ｓ４１７）。次いで、第２ポイントＰ２と再設定された第１変数Ｔ１が同一であるか否かを検査し、同一ならば、欠陥が発生されていないと判断し、そうではなければ、欠陥が発生されたと判断する（Ｓ４１９）。
【００６３】
一方、２進ビットｋｉが“１”でなければ、第２変数Ｔ２の２倍を第２変数Ｔ２に再設定し、第１変数Ｔ１に応答して決定される第２ポイントＰ２と基本ポイントＰとの和を第１変数Ｔ１に再設定する（Ｓ４２１）。次いで、再設定された第２変数Ｔ２と再設定された第１変数Ｔ１とが同一か否かを検査して、同一ならば、欠陥が発生されていないと判断し、そうではなければ、欠陥が発生されたと判断する（Ｓ４２３）。
【００６４】
欠陥チェック方法４００で欠陥が発生されていないと判断する場合、反復媒介変数ｉが０より小さいか否かを判断して（Ｓ４２７）、小さくなければ、ｉを減少させつつ、スカラー積演算と欠陥発生如何のチェック演算とを反復的に行う。しかし、反復媒介変数ｉが０より小さければ、そのときのＰ１値をスカラー積Ｑとして出力する（Ｓ４２９）。一方、欠陥チェック方法４００で欠陥が発生されたと判断する場合には、警告信号を出力する。
図５は、最終チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【００６５】
図５を参照すれば、欠陥チェック方法５００は、反復されるスカラー積が何れも行われた後にチェック動作が行われる方法である。すなわち、図４の欠陥チェック方法４００のように、２進ビットｋｉに応答して第１ポイントと第２ポイントとが再設定された後（Ｓ５１１及びＳ５１３）、直ぐ欠陥流入如何をチェックせず、反復媒介変数ｉが１より小さいか否かを判断して（Ｓ５１５）、スカラー積演算を反復するか否かについてまず判断した後、欠陥の流入如何が検査される。
図５の他の動作は、図４と同一であるので、具体的な説明は省略する。
【００６６】
図６は、ランダムチェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
図６を参照すれば、欠陥チェック方法６００は、スカラー積演算が反復的に行われる時に、任意のスカラー積演算を行った後に欠陥が発生されたか否かを検査する。すなわち、２進ビットｋｉに応答して第１ポイントＰ１と第２ポイントＰ２とが再設定された後（Ｓ６１３及びＳ６１５）、欠陥発生如何をチェックするか否かを決定する。
【００６７】
このとき、所定のチェック値ＣＨＥＣＫがチェックレートＲＡＴＥ以下であるか否かを決定し（Ｓ６１７）、チェック値ＣＨＥＣＫがチェックレートＲＡＴＥ以下である場合に、欠陥が発生されたか否かをチェックする。チェックレートＲＡＴＥは、欠陥発生如何をチェックする頻度を決定する値であって、図６を参照すれば、チェックレートＲＡＴＥは、暗号化方法で使われる媒介変数が初期化されるか、または設定されるステップで共に設定されうる（Ｓ６０３）。一方、チェック値ＣＨＥＣＫは、ランダム定数である。
【００６８】
例えば、チェック値ＣＨＥＣＫとチェックレートＲＡＴＥとが何れも０〜１００の値を有し、チェックレートＲＡＴＥが７０に設定されれば、ランダムに発生するチェック値ＣＨＥＣＫが７０以下であれば、欠陥発生如何をチェックし、チェック値ＣＨＥＣＫが７０より大きければ、欠陥発生如何をチェックしない。
【００６９】
図４ないし図６のＦＭＰＬＡを使用する欠陥チェック方法は、第１ポイントＰ１及び第２ポイントＰ２の再設定において、楕円曲線ポイントの２倍演算及び加算演算を行う。しかし、前述したように、数式（６）の加算演算を図４ないし図６の加算演算に使用する場合、正確な欠陥発生如何がチェックできないという問題が発生する。
【００７０】
図７は、本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算方法を示すフローチャートである。
図７を参照すれば、本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するためのポイント加算演算方法７００は、楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するＳ７２０と、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するＳ７４０と、を含む。
【００７１】
前記ＦＭＰＬＡを利用する欠陥検出動作は、ＥＣＣシステムに適用されうる。以下の第１ポイント及び第２ポイントは、図４ないし図６の欠陥チェック動作の第１ポイントＰ１及び第２ポイントＰ２と同一であるので、同じ符号として説明される。
【００７２】
第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算は、第１ポイントＰ１及び第２ポイントＰ２の第１座標値と第２座標値との差を反映する。このとき、第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値である。
【００７３】
すなわち、前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記第１ポイントＰ１及び第２ポイントＰ２のＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、第１ポイントＰ１及び第２ポイントＰ２の第１座標値及び第２座標値の差が第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）に反映される。
したがって、第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の数式（１１）の通りである。
【００７４】
【数１３】
【００７５】
ａ及びｂは、加算演算に使われる定数であって、本発明が属する技術分野の当業者が容易に理解できる事項であるところ、これについてのさらに詳細な説明は省略する。このとき、基本ポイントＰは、アフィン座標上のポイントであるので、第２ポイントＰ２の前記第２座標値を“１”に代替しうる。
この場合、第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の数式（１２）のように表現されうる。
【００７６】
【数１４】
【００７７】
数式（１１）及び数式（１２）のように、第１ポイントＰ１及び第２ポイントＰ２の第２座標値の差であるＺＤ値を二ポイントの素数有限領域における加算演算式に反映することによって、正確なモンゴメリアルゴリズムを利用した欠陥検出動作を行える。
【００７８】
図８は、本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
図８を参照すれば、本発明の実施形態による素数有限領域におけるポイント加算演算装置８００は、第１座標算出部及び第２座標算出部を備える。第１座標算出部は、楕円曲線上の基本ポイントを利用して設定された第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値Ｘ３を算出する。第２座標算出部は、第１ポイントＰ１及び第２ポイントＰ２の第２座標値についての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値Ｚ３を算出する。
【００７９】
このとき、前記第１座標算出部及び前記第２座標算出部は、第１ポイントＰ１及び第２ポイントＰ２の第２座標値の差を反映して、前記第１座標値及び前記第２座標値を算出する。
前記第１座標算出部は、第１ないし第７乗算器Ｘ１〜Ｘ７、第１ないし第４加算器＋１〜＋４、第１及び第２算出手段Ｃ１１，Ｃ１２及び第１減算器−１を備える。
【００８０】
第１乗算器Ｘ１は、前記Ｘ１と前記Ｚ２とを乗算して、第１乗算値（Ｘ１ｘＺ２）として算出する。第２乗算器Ｘ２は、前記Ｘ２と前記Ｚ１とを乗算して、第２乗算値（Ｘ２ｘＺ１）として算出する。第１加算器＋１は、前記第１乗算値と前記第２乗算値とを加算して、第１加算値（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）として算出する。
【００８１】
第３乗算器Ｘ３は、前記Ｘ１と前記Ｘ２とを乗算して、第３乗算値（Ｘ１ｘＸ２）として算出する。第４乗算器Ｘ４は、前記Ｚ１と前記Ｚ２とを乗算して、第４乗算値（Ｚ１ｘＺ２）として算出する。
【００８２】
第５乗算器Ｘ５は、前記第４乗算値に第１所定数である前記ａを乗算して、第５乗算値（ａｘＺ１ｘＺ２）として算出する。第２加算器＋２は、前記第３乗算値と前記第５乗算値とを加算して、第２加算値（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）として算出する。
【００８３】
第６乗算器Ｘ６は、前記第１加算値と前記第２加算値とを乗算して、第６乗算値（（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する。第３加算器＋３は、前記第６乗算値同士加算して、前記第６乗算値の２倍である第３加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する。
【００８４】
第１算出手段Ｃ１１は、前記第４乗算値を２倍にして自乗した結果に第２所定数である前記ｂを乗算して、第１算出値（４ｘｂｘＺ１２ｘＺ２２）として算出する。第１算出手段Ｃ１１は、第１１加算器＋１１、第１１自乗器Ｓ１１及び第１１乗算器Ｘ１１を備える。第１１加算器＋１１は、前記第４乗算値同士加算して、前記第４乗算値の２倍である第１１加算値（２ｘＺ１ｘＺ２）として算出する。第１１自乗器Ｓ１１は、前記第１１加算値を自乗して、第１１自乗値（４ｘＺ１２ｘＺ２２）として算出する。第１１乗算器Ｘ１１は、前記第１１自乗値に前記ｂを乗算して、前記第１算出値として算出する。
【００８５】
第４加算器＋４は、前記第３加算値と前記第１算出値とを加算して、第４加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２）として算出する。第７乗算器Ｘ７は、前記第４加算値に前記ＺＤを乗算して、第７乗算値（ＺＤｘ［２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２］）として算出する。
【００８６】
第２算出手段Ｃ１２は、前記第１乗算値から前記第２乗算値を減算して自乗した結果に前記ＸＤを乗算して、第２算出値（ＸＤｘ（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する。第２算出手段Ｃ１２は、第１２減算器−１２、第１２自乗器Ｓ１２及び第１２乗算器Ｘ１２を備える。第１２減算器−１２は、前記第１乗算値から前記第２乗算値を減算して、第１２減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する。第１２自乗器Ｓ１２は、前記第１２減算値を自乗して、第１２自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する。第１２乗算器Ｘ２１は、前記第１２自乗値と前記ＸＤとを乗算して、前記第２算出値として算出する。
【００８７】
第１減算器−１は、前記第７乗算値から前記第２算出値を減算して、前記第１ポイント及び前記第２ポイントについての加算演算の結果のＸ座標値（Ｘ３）として算出する。
第２座標算出部Ｃ２２は、第２１ないし第２３乗算器Ｘ２１，Ｘ２２，Ｘ２３、第２１減算器−２１及び第２１自乗器Ｓ２１を備えることである。
【００８８】
第２１乗算器Ｘ２１は、前記Ｘ１と前記Ｚ２とを乗算して、第２１乗算値（Ｘ１ｘＺ２）として算出する。第２２乗算器Ｘ２２は、前記Ｘ２と前記Ｚ１とを乗算して、第２２乗算値（Ｘ２ｘＺ１）として算出する。第２１減算器−２１は、前記第２１乗算値から前記第２２乗算値を減算して、第２１減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する。
【００８９】
前記第２１自乗器Ｓ２１は、前記第２１減算値を自乗して、第２１自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する。第２３乗算器Ｘ２３は、前記第２１自乗値に前記ＺＤを乗算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＺ座標値（Ｚ３）として算出する。
【００９０】
第２１乗算器Ｘ２１及び第２２乗算器Ｘ２２は、前記第１座標算出部の第１乗算器Ｘ１及び第２乗算器Ｘ２でありうる。また、第２１減算器−２１及び第２１自乗器Ｓ２１は、第２算出手段Ｃ１２の第１２減算器−１２及び第１２自乗器Ｓ１２でありうる。
【００９１】
図８の素数有限領域におけるポイント加算演算装置によって、前述した数式（１１）が具現されうる。数式（１２）は、次の図９の素数有限領域におけるポイント加算演算装置によって具現されうる。
【００９２】
図９は、本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
図９を参照すれば、本発明の実施形態による素数有限領域におけるポイント加算演算装置９００は、図８のポイント加算演算装置８００と同じ動作を行う。但し、図９のポイント加算演算装置９００は、第２ポイントＰ２の第２座標値（Ｚ座標値）が“１”である場合についてのポイント加算結果を算出する。したがって、図９のポイント加算演算装置９００は、図８のポイント加算演算装置８００と類似した構成を有するが、さらに少ない数の乗算器で具現されうる。
【００９３】
図９のポイント加算演算装置９００の第１座標算出部及び第２座標算出部は、図８のポイント加算演算装置８００の説明から容易に分かるので、これについてのさらに詳細な説明は省略する。
【００９４】
図１０は、図８及び図９の自乗器をさらに詳細に示す図面である。
図１０を参照すれば、自乗器Ｓは、同じ入力Ｉ１同士乗算Ｘする。このとき、自乗器Ｓは、図８及び図９の第１１自乗器Ｓ１１及び第１２自乗器Ｓ１２を表す。このように、同じ入力Ｉ１同士乗算Ｘするように自乗器Ｓを設計することによって、ポイント加算演算装置８００，９００のレイアウト面積を減らせるという長所がある。
【００９５】
以上、図面及び明細書で最適の実施形態が開示された。ここで、特定の用語が使用されたが、これは、単に本発明を説明するための目的で使われたものであり、意味限定や特許請求の範囲に記載された本発明の範囲を制限するために使われたものではない。したがって、当業者ならば、これから多様な変形及び均等な他の実施形態が可能であるという点が分かるであろう。したがって、本発明の真の技術的保護範囲は、特許請求の範囲の技術的思想によって決定されねばならない。
【産業上の利用可能性】
【００９６】
本発明は、暗号化方法関連の技術分野に適用可能である。
【図面の簡単な説明】
【００９７】
【図１】ＤＦＡに対応するＣＴ＆Ｃ方法を示すフローチャートである。
【図２】ＤＦＡに対応するＣＯＰ方法を示すフローチャートである。
【図３】ＭＰＬＡを利用してＥＣＣ方法におけるスカラー積演算を行う方法を示すフローチャートである。
【図４】定期チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【図５】最終チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【図６】ランダムチェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【図７】本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算方法を示すフローチャートである。
【図８】本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
【図９】本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
【図１０】図８及び図９の自乗器をさらに詳細に示す図面である。
【符号の説明】
【００９８】
８００ ポイント加算演算装置
Ｃ１１ 第１算出手段
Ｃ１２ 第２算出手段
Ｘ１〜Ｘ７ 第１ないし第７乗算器
＋１〜＋４ 第１ないし第４加算器
−１ 第１減算器
Ｓ１１ 第１１自乗器
Ｓ１２ 第１２自乗器
＋１１ 第１１加算器
−１２ 第１２減算器
【技術分野】
【０００１】
本発明は、暗号化方法に係り、特に高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法に関する。
【背景技術】
【０００２】
情報化社会の到来による情報伝送媒体の発達と共に、情報の安全性を保証するための暗号化及び復号化方案も多角的に摸索されている。そのうち、ＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号化システム及び楕円曲線暗号化（ＥＣＣ：Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ）システムのような公開キー形式の暗号化方式が広く使われている。整数除算(integer division)に対するアルゴリズムが定義されないので、十分に大きい整数を公開キーとして使用することによって、公開キー形式の暗号化方式は、システムの安全性を保証しうる。
【０００３】
特に、ＥＣＣシステムは、比較的に短いキーサイズでも高い安全性が確保でき、スマートカード及び電子署名に広く使われている。ＥＣＣシステムは、楕円曲線と呼ばれる数式によって定義される特殊な加算法を基盤として暗号化／復号化する暗号化方式である。
具体的に、ＥＣＣ方法は、任意の楕円曲線Ｅと楕円曲線Ｅ上の一点Ｐとをシステムパラメータとして使用する。暗号化通信を所望するユーザ１は、ランダムに整数ｋを生成し、ｋとＰとを乗算してＱ（＝ｋｘＰ）を生成する。ユーザ１は、Ｑを公開キーとして公開し、ｋをユーザ１の秘密キーとして安全に保存する。
【０００４】
逆に、ユーザ１にメッセージＭを秘密裏に伝送しようとするユーザ２は、まずランダムに整数ｄを生成し、システムパラメータのうち一つであるＰと整数ｄとを乗算してＡ（＝ｄｘＰ）を生成する。ユーザ１が提供した公開キーＱと伝送しようとするメッセージＭとを使用してＢ（＝Ｍ＋ｄｘＱ）を生成する。最後に、ユーザ２は、最終結果暗号文Ａ,Ｂをユーザ１に伝送する。
ユーザ２から暗号文Ａ,Ｂを伝達されたユーザ１は、自身の秘密キーｋを使用してｋｘＡを計算した後、次の数式（１）のような演算を行ってメッセージＭを復元する。
【０００５】
【数１】
【０００６】
このようなＥＣＣシステムを攻略するための方案として、演算されている変数値の差を利用して暗号システムの秘密キーを探し出す差分欠陥分析（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｆａｕｌｔ Ａｎａｌｙｓｉｓ：ＤＦＡ）が広く知られている。ＤＦＡは、欠陥を暗号システムに投入し、投入された欠陥に対応する演算結果を分析し、暗号システムの秘密キーを探す方法である。
【０００７】
暗号システムは、所定の演算を行う時にレジスターに保存された値を参照するが、レジスターに保存される値または保存された値は、欠陥によって変更される。したがって、暗号システムの演算結果に、欠陥によって変更された値に対応するエラーが含まれる。
エラーを含んで出力される演算結果を解釈することによって、秘密キーについての情報は露出される。したがって、ＤＦＡに対応するために、ＥＣＣシステムで使われる色々な方法が提案されている。
【０００８】
図１は、ＤＦＡに対応するＣＴ＆Ｃ（Ｃａｌｃｕｌａｔｅ Ｔｗｉｃｅ ａｎｄ Ｃｈｅｃｋ）方法を示すフローチャートである。
ＣＴ＆Ｃ方法１００は、まず、楕円曲線のうち任意の一点Ｐを選択した後（１１０）、Ｐに任意の整数ｋを乗算して第１比較値Ｑ１を求め（１２０）、Ｐに整数ｋを乗算して第２比較値Ｑ２を求める（１３０）。このとき、所定の整数ｋは、秘密キーを意味する。
【０００９】
次いで、第１比較値Ｑ１と第２比較値Ｑ２との大きさを比較し（１４０）、第１比較値Ｑ１と第２比較値Ｑ２とが同一ならば、乗算演算にいかなる欠陥も発生されていないと判断して、第１比較値Ｑ１及び第２比較値Ｑ２のうち一つが演算結果Ｑとして出力される（１５０）。一方、第１比較値Ｑ１と第２比較値Ｑ２とが同一でなければ、乗算演算に欠陥が発生されたと判断して、演算結果Ｑの代わりに警告信号が出力される（１６０）。
【００１０】
図２は、ＤＦＡに対応するＣＯＰ（Ｃｈｅｃｋ ｔｈｅ Ｏｕｔｐｕｔ Ｐｏｉｎｔ）方法を示すフローチャートである。
ＣＯＰ方法２００は、まず楕円曲線のうち任意の一点Ｐを選択し（２１０）、Ｐに所定の整数ｋを乗算して比較値Ｑを求める（２２０）。このとき、所定の整数ｋは、秘密キーを意味する。
【００１１】
次いで、比較値Ｑが楕円曲線Ｅの一点であるか否かを判断して（２３０）、比較値Ｑが楕円曲線Ｅの一点ならば、乗算演算にいかなる欠陥も発生されていないと判断して、比較値Ｑが出力される（２４０）。一方、比較値Ｑが楕円曲線Ｅの一点でなければ、乗算演算中に欠陥が発生されたケースに該当すると判断して、比較値Ｑの代わりに警告信号が出力される（２５０）。
【００１２】
しかし、図１のＣＴ＆Ｃ方法１００は、同じ乗算計算を２回もしなければならないという短所があり、図２のＣＯＰ方法２００は、図１のＣＴ＆Ｃ方法１００に比べて計算が簡単であるという長所があるが、その適用範囲が制限的であるだけでなく、符号の変わる欠陥を利用した攻撃に対応する場合には、システムの実行能力が非常に低下するという短所がある。したがって、モンゴメリ電力ラダーアルゴリズム（ＭＰＬＡ：Ｍｏｎｔｇｏｍｅｒｙ Ｐｏｗｅｒ Ｌａｄｄｅｒ Ａｌｇｏｒｉｔｈｍ）または高速ＭＰＬＡ（ＦＭＰＬＡ：Ｆａｓｔ Ｍｏｎｔｇｏｍｅｒｙ Ｐｏｗｅｒ Ｌａｄｄｅｒ Ａｌｇｏｒｉｔｈｍ）を利用して、ＤＦＡに対応する方案が摸索されている。
【００１３】
前述したＥＣＣ方法を参照すれば、Ｐ及びＱ値を通じてｋを求めるためには、離散対数演算が行われねばならない。離散対数演算は、有限フィールドに楕円曲線の特性を適用して行われ、暗号プロトコルの秘密性の基礎となる。簡単には、離散対数演算とは、Ｑ＝ｋｘＰで、ＱとＰとからｋを求める演算である。
【００１４】
したがって、ＥＣＣ方法でスカラー積演算は、重要な演算のうちの一つであるということが分かる。ＭＰＬＡとは、有限フィールドにおけるスカラー積演算を行う方法のうちの一つである。以下では、ＭＰＬＡについてさらに詳細に説明する。
一般的なＭＰＬＡでは、まず、２個の変数を次の数式（２）のように定義する。
【００１５】
【数２】
【００１６】
数式（２）の二変数間の関係に対する他の数学的表現は、次の数式（３）の通りである。任意の整数ｋは、複数の２進ビット（ｋ＝（ｋｔ−１，．．．，ｋ１，ｋ０）２、ｔは、整数、以下、同一）で表現され、ｋｉは、反復媒介変数ｉ（ｉは、整数、以下、同一）に対応するビットの値を表す。このとき、ｋｔ−１は、常に“１”の値を有する。数式（２）に表現された二変数間の関係は、次の数式（３）のように再整理されうる。
【００１７】
【数３】
【００１８】
数式（３）に表示された二変数間の関係を変数ｊ値によって異ならせて表現すれば、次の数式（４）のように表現しうる。
【００１９】
【数４】
【００２０】
数式（４）の誘導過程は、本発明の属する技術分野の当業者に広く知られた事項であるところ、それについての詳細な説明は省略する。ＬｊとＨｊとは、後述する図３及びアルゴリズム１で、ＥＣＣシステムにおける楕円曲線上の２ポイントであるＰ１及びＰ２にマッピングされる。
【００２１】
図３は、ＭＰＬＡを利用してＥＣＣ方法におけるスカラー積演算を行う方法を示すフローチャートである。
図３を参照すれば、ＭＰＬＡを利用したスカラー積演算方法３００は、まず、基本ポイントＰとスカラーｋ（ｋは、整数、以下、同一）とを受信する（Ｓ３０１）。次いで、スカラー積を反復演算するための変数が設定される（Ｓ３０３）。
【００２２】
ｋは、数式（２）で前述したように設定される。また、第１変数Ｐ１は、基本ポイントＰに、そして、第２変数Ｐ２は、基本ポイントＰの２倍、すなわち２ｘＰに設定される。反復媒介変数ｉは、ｔ−１に初期化される。
【００２３】
変数が設定された後には、反復演算によってスカラー積Ｑ＝ｋｘＰが計算される。すなわち、反復媒介変数ｉを０まで減少させつつ（Ｓ３０５、Ｓ３１３）、それぞれの２進ビットｋｉによって（Ｓ３０７）、第１及び第２変数を再設定（Ｓ３１０、Ｓ３１１）する過程を反復し、ｉが０まで減少した場合（Ｓ３１３）の第１変数Ｐ１をスカラー積Ｑ＝ｋｘＰとして出力する（Ｓ３１５）。
【００２４】
このとき、“Ｐ２←２Ｐ２”及び“Ｐ１←２Ｐ１”は、楕円曲線ポイントの２倍演算（例えば、２を乗算すること）を意味し、“Ｐ１←Ｐ１＋Ｐ２”及び“Ｐ２←Ｐ１＋Ｐ２”は、楕円曲線ポイントの加算演算を意味する。ところが、図３の一般的なＭＰＬＡは、それぞれの反復演算で加算演算と２倍演算とが行われるので、性能において、大きい劣化を発生させる。このような劣化を防止するために、Ｙ座標形態の計算が除外されたループ計算を行った後、Ｙ座標を再定義するＦＭＰＬＡを利用したスカラー積演算方法が提案された。
【００２５】
ＦＭＰＬＡを通じて楕円曲線上の２ポイント（Ｐ１（Ｘ１,Ｚ１）、Ｐ２（Ｘ２,Ｚ２））の２倍演算及び加算演算を行うための、素数有限フィールド(prime finit field)における２倍演算及び加算演算は、それぞれ次の数式（５）及び数式（６）で定義される。
【００２６】
【数５】
【００２７】
【数６】
【００２８】
数式（５）及び数式（６）を参照すれば、計算中にＹ座標が含まれないということが分かる。
ところが、数式（６）の加算演算は、２ポイント（Ｐ１（Ｘ１,Ｚ１）、Ｐ２（Ｘ２,Ｚ２））のＺ座標の差（ＺＤ＝Ｚ２−Ｚ１）が“１”であることを前提している。しかし、ＦＭＰＬＡを利用した欠陥検索方法は、２ポイントの差を利用して欠陥の発生如何を検出する。
【００２９】
したがって、数式（６）の加算演算を、ＦＭＰＬＡを利用する欠陥検出方法に使用する場合、ＥＣＣシステムは、誤った欠陥発生分析結果を導出する恐れがある。欠陥分析のエラーは、暗号化システムを無力化させて深刻な問題をもたらす。
【発明の開示】
【発明が解決しようとする課題】
【００３０】
本発明が解決しようとする技術的課題は、ＦＭＰＬＡを利用する欠陥検出動作で、エラーなしに欠陥を検出するための素数有限領域におけるポイント加算方法を提供することである。
本発明が解決しようとする他の技術的課題は、ＦＭＰＬＡを利用する欠陥検出動作で、エラーなしに欠陥を検出するための素数有限領域におけるポイント加算演算装置を提供することである。
【課題を解決するための手段】
【００３１】
前記課題を達成するための本発明の実施形態による素数有限領域におけるポイント加算演算方法は、所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するステップと、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するステップと、を含む。
【００３２】
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算は、前記第１ポイント及び前記第２ポイントの第１座標値と第２座標値との差を反映する。
前記ＦＭＰＬＡを利用する欠陥検出動作は、ＥＣＣシステムに適用される。前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値である。
【００３３】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の通りである。
【００３４】
【数７】
【００３５】
前記課題を達成するための本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法で、前記第２ポイントの前記第２座標値は、所定数に固定される。前記第２ポイントの第２座標値は、“１”である。
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,１）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（１−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の通りである。
【００３６】
【数８】
【００３７】
前記他の課題を達成するための本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置は、第１座標算出部及び第２座標算出部を備える。
【００３８】
第１座標算出部は、所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出する。第２座標算出部は、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出する。
【００３９】
前記第１座標算出部及び前記第２座標算出部は、前記第１ポイント及び前記第２ポイントの第２座標値の差を反映して、前記第１座標値及び前記第２座標値を算出する。前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値である。
【００４０】
前記第１座標算出部は、第１ないし第７乗算器、第１ないし第４加算器、第１及び第２算出手段及び第１減算器を備える。前記第２座標算出部は、第２１ないし第２３乗算器、第２１減算器及び第２１自乗器を備える。
【００４１】
前記他の課題を達成するための本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置は、前記第２ポイントの第２座標値が“１”である場合についての素数有限領域におけるポイト加算演算を行う。
【発明の効果】
【００４２】
本発明による素数有限領域におけるポイント加算方法及び加算演算装置によれば、ＦＭＰＬＡを利用する暗号化システムで正確な欠陥検出動作を行える。
【発明を実施するための最良の形態】
【００４３】
本発明と本発明の動作上の利点及び本発明の実施によって達成される目的を十分に理解するためには、本発明の望ましい実施形態を例示する添付図面及び図面に記載された内容を参照せねばならない。
以下、添付した図面を参照して本発明の望ましい実施形態を説明することによって、本発明を詳細に説明する。各図面に提示された同じ参照符号は、同じ部材を表す。
【００４４】
本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算方法を説明する前に、ＦＭＰＬＡを利用する欠陥検出方法についてさらに詳細に説明する。
ＦＭＰＬＡを利用する欠陥検出方法を具現するために、まず数式（２）及び数式（３）から次の数式（７）が誘導される。
【００４５】
【数９】
次いで、数式（７）から次の数式（８）が誘導される。
【００４６】
【数１０】
【００４７】
Ｈｊ＝Ｌｊ＋１は、数式（２）で表した。
以前計算で欠陥がなかったということを確認するために、判断を行う間に、計算にＨｊとＬｊ値とが含まれねばならない。Ｙ座標を含まず、二点であるＨｊとＬｊとの和をＸ座標で計算するモンゴメリ方法は、これらの二点の差に関する情報に基づく。
【００４８】
このような特徴は、次のような欠陥チェック動作を誘導するために使われ、これを可能にするために、かつパワートラック分析による分別不可能性(indistinguishability)の動作平衡(operation equilibrium)を満足するために、次のように、ｋｊ＝０とｋｊ＝１との２つを考慮せねばならない。
まず、ｋｊ＝１の場合、欠陥チェック動作は、次の順序によって行われる。
１．次の数式（９）を利用して２倍演算によってＬｊ−１を計算する。
【００４９】
【数１１】
【００５０】
２．１での結果から、加算演算によってＬｊ＋１を計算する。
３．Ｌｊ＋１＝Ｈｊであるかをチェックする。ここで、Ｈｊは、以前に計算された値である。
【００５１】
次いで、Ｋｊ＝０である場合、欠陥チェック動作は、次の順序によって行われる。
１．次の数式（１０）を利用して、２倍演算によって２Ｈｊ＋１を計算する。
【００５２】
【数１２】
【００５３】
２．Ｌｊを考慮して、加算演算によってＨｊ＋１を計算する。
３．Ｈｊ＋１＝２Ｈｊ＋１であるかを確認する。ここで、２Ｈｊ＋１は、以前に計算された値である。
【００５４】
欠陥が発生されていない場合、ＬｊとＨｊとの差は、常に“１”である。したがって、前記のような演算過程で欠陥が発生されていないならば、Ｌｊ＋１＝ＨｊまたはＨｊ＋１＝２Ｈｊ＋１である。また、二つの場合で何れもＨｊとＬｊとがチェック過程に含まれ、これは、計算された二ポイントで何れも欠陥が存在するか否かチェックされたということを意味する。
【００５５】
以下では、前述したＦＭＰＬＡを利用した新たな方式の欠陥チェック方法が適用される多様な実施形態が提案される。これは、欠陥チェックの実行ステップによって分けられる。すなわち、スカラー積演算中に欠陥の発生如何が判断される定期チェックとランダムチェック、そしてスカラー積演算が完了した後に演算結果が出力される前に欠陥の発生如何が判断される最終チェック方法が提案される。
【００５６】
さらに具体的に説明すれば、定期チェック方法は、欠陥が発生されたか否かがスカラー積演算が反復される度に行われる。ランダムチェック方法は、スカラー積演算が反復される度に行われず、ランダムに選択されるスカラー積演算に対して、スカラー積演算が行われた後に行われる。
【００５７】
図４は、定期チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
図４を参照すれば、定期チェック方法が適用された欠陥チェック方法４００は、スカラー積演算が行われる反復区間ごとに定期的にチェック動作が行われる方法である。欠陥チェック方法４００は、基本ポイントＰとスカラーｋとを受信して（Ｓ４０１）、スカラー積Ｑ（＝ｋｘＰ）を出力する（Ｓ４２９）。
【００５８】
ここで、基本ポイントＰは、所定の楕円曲線上のポイントであって、ハードウェア具現時にＥＰＲＯＭに保存される。スカラーｋは、数式（２）で説明した通りである。欠陥チェック方法４００は、基本ポイントＰとスカラーｋとを受信した後（Ｓ４０１）、暗号化のためのパラメータまたはポイントを初期化するか、または設定する（Ｓ４０３）。スカラーｋの２進ビットｋｉによる反復的な演算のために、本発明では、変数が使われて、変数は、所定の規則によって初期化されるか、または設定される（Ｓ４０３またはＳ４０７）。
【００５９】
まず、基本ポイントＰを利用して第１ポイントＰ１と第２ポイントＰ２とが初期化される。具体的に、第１ポイントＰ１は、基本ポイントＰに初期化され、第２ポイントＰ２は、基本ポイントＰの２倍に初期化される。暗号化方法４００に使われるパラメータまたはポイントが初期化された後には、反復的な演算を行ってスカラー積Ｑを計算する（Ｓ４０５ないしＳ４１３及びＳ４２７）。
【００６０】
２進ビットで表現されるスカラーｋの全てのビットについての反復演算のために、本発明の実施形態では、反復演算変数ｉを０まで減少させつつ（Ｓ４０５）、２進ビット値ｋｉについての反復演算が行われる。
【００６１】
図４の欠陥チェック方法４００では、再設定するステップが完了する度に欠陥が発生されたか否かチェックされるので、欠陥が発生されたか否が定期的にチェックされる。以下では、欠陥が発生されたか否かをチェックする動作について説明する（Ｓ４１５ないしＳ４２３）。
【００６２】
まず、２進ビットｋｉが“１”であるか否かが決定される（Ｓ４１５）。２進ビットｋｉが“１”であれば、第１変数Ｔ１の２倍を第１変数Ｔ１に再設定し、第１変数Ｔ１に応答して決定される第１ポイントＰ１と基本ポイントＰとの和を第１変数Ｔ１に再設定する（Ｓ４１７）。次いで、第２ポイントＰ２と再設定された第１変数Ｔ１が同一であるか否かを検査し、同一ならば、欠陥が発生されていないと判断し、そうではなければ、欠陥が発生されたと判断する（Ｓ４１９）。
【００６３】
一方、２進ビットｋｉが“１”でなければ、第２変数Ｔ２の２倍を第２変数Ｔ２に再設定し、第１変数Ｔ１に応答して決定される第２ポイントＰ２と基本ポイントＰとの和を第１変数Ｔ１に再設定する（Ｓ４２１）。次いで、再設定された第２変数Ｔ２と再設定された第１変数Ｔ１とが同一か否かを検査して、同一ならば、欠陥が発生されていないと判断し、そうではなければ、欠陥が発生されたと判断する（Ｓ４２３）。
【００６４】
欠陥チェック方法４００で欠陥が発生されていないと判断する場合、反復媒介変数ｉが０より小さいか否かを判断して（Ｓ４２７）、小さくなければ、ｉを減少させつつ、スカラー積演算と欠陥発生如何のチェック演算とを反復的に行う。しかし、反復媒介変数ｉが０より小さければ、そのときのＰ１値をスカラー積Ｑとして出力する（Ｓ４２９）。一方、欠陥チェック方法４００で欠陥が発生されたと判断する場合には、警告信号を出力する。
図５は、最終チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【００６５】
図５を参照すれば、欠陥チェック方法５００は、反復されるスカラー積が何れも行われた後にチェック動作が行われる方法である。すなわち、図４の欠陥チェック方法４００のように、２進ビットｋｉに応答して第１ポイントと第２ポイントとが再設定された後（Ｓ５１１及びＳ５１３）、直ぐ欠陥流入如何をチェックせず、反復媒介変数ｉが１より小さいか否かを判断して（Ｓ５１５）、スカラー積演算を反復するか否かについてまず判断した後、欠陥の流入如何が検査される。
図５の他の動作は、図４と同一であるので、具体的な説明は省略する。
【００６６】
図６は、ランダムチェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
図６を参照すれば、欠陥チェック方法６００は、スカラー積演算が反復的に行われる時に、任意のスカラー積演算を行った後に欠陥が発生されたか否かを検査する。すなわち、２進ビットｋｉに応答して第１ポイントＰ１と第２ポイントＰ２とが再設定された後（Ｓ６１３及びＳ６１５）、欠陥発生如何をチェックするか否かを決定する。
【００６７】
このとき、所定のチェック値ＣＨＥＣＫがチェックレートＲＡＴＥ以下であるか否かを決定し（Ｓ６１７）、チェック値ＣＨＥＣＫがチェックレートＲＡＴＥ以下である場合に、欠陥が発生されたか否かをチェックする。チェックレートＲＡＴＥは、欠陥発生如何をチェックする頻度を決定する値であって、図６を参照すれば、チェックレートＲＡＴＥは、暗号化方法で使われる媒介変数が初期化されるか、または設定されるステップで共に設定されうる（Ｓ６０３）。一方、チェック値ＣＨＥＣＫは、ランダム定数である。
【００６８】
例えば、チェック値ＣＨＥＣＫとチェックレートＲＡＴＥとが何れも０〜１００の値を有し、チェックレートＲＡＴＥが７０に設定されれば、ランダムに発生するチェック値ＣＨＥＣＫが７０以下であれば、欠陥発生如何をチェックし、チェック値ＣＨＥＣＫが７０より大きければ、欠陥発生如何をチェックしない。
【００６９】
図４ないし図６のＦＭＰＬＡを使用する欠陥チェック方法は、第１ポイントＰ１及び第２ポイントＰ２の再設定において、楕円曲線ポイントの２倍演算及び加算演算を行う。しかし、前述したように、数式（６）の加算演算を図４ないし図６の加算演算に使用する場合、正確な欠陥発生如何がチェックできないという問題が発生する。
【００７０】
図７は、本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算方法を示すフローチャートである。
図７を参照すれば、本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するためのポイント加算演算方法７００は、楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するＳ７２０と、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するＳ７４０と、を含む。
【００７１】
前記ＦＭＰＬＡを利用する欠陥検出動作は、ＥＣＣシステムに適用されうる。以下の第１ポイント及び第２ポイントは、図４ないし図６の欠陥チェック動作の第１ポイントＰ１及び第２ポイントＰ２と同一であるので、同じ符号として説明される。
【００７２】
第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算は、第１ポイントＰ１及び第２ポイントＰ２の第１座標値と第２座標値との差を反映する。このとき、第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値である。
【００７３】
すなわち、前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記第１ポイントＰ１及び第２ポイントＰ２のＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、第１ポイントＰ１及び第２ポイントＰ２の第１座標値及び第２座標値の差が第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）に反映される。
したがって、第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の数式（１１）の通りである。
【００７４】
【数１３】
【００７５】
ａ及びｂは、加算演算に使われる定数であって、本発明が属する技術分野の当業者が容易に理解できる事項であるところ、これについてのさらに詳細な説明は省略する。このとき、基本ポイントＰは、アフィン座標上のポイントであるので、第２ポイントＰ２の前記第２座標値を“１”に代替しうる。
この場合、第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、次の数式（１２）のように表現されうる。
【００７６】
【数１４】
【００７７】
数式（１１）及び数式（１２）のように、第１ポイントＰ１及び第２ポイントＰ２の第２座標値の差であるＺＤ値を二ポイントの素数有限領域における加算演算式に反映することによって、正確なモンゴメリアルゴリズムを利用した欠陥検出動作を行える。
【００７８】
図８は、本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
図８を参照すれば、本発明の実施形態による素数有限領域におけるポイント加算演算装置８００は、第１座標算出部及び第２座標算出部を備える。第１座標算出部は、楕円曲線上の基本ポイントを利用して設定された第１ポイントＰ１及び第２ポイントＰ２についての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値Ｘ３を算出する。第２座標算出部は、第１ポイントＰ１及び第２ポイントＰ２の第２座標値についての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値Ｚ３を算出する。
【００７９】
このとき、前記第１座標算出部及び前記第２座標算出部は、第１ポイントＰ１及び第２ポイントＰ２の第２座標値の差を反映して、前記第１座標値及び前記第２座標値を算出する。
前記第１座標算出部は、第１ないし第７乗算器Ｘ１〜Ｘ７、第１ないし第４加算器＋１〜＋４、第１及び第２算出手段Ｃ１１，Ｃ１２及び第１減算器−１を備える。
【００８０】
第１乗算器Ｘ１は、前記Ｘ１と前記Ｚ２とを乗算して、第１乗算値（Ｘ１ｘＺ２）として算出する。第２乗算器Ｘ２は、前記Ｘ２と前記Ｚ１とを乗算して、第２乗算値（Ｘ２ｘＺ１）として算出する。第１加算器＋１は、前記第１乗算値と前記第２乗算値とを加算して、第１加算値（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）として算出する。
【００８１】
第３乗算器Ｘ３は、前記Ｘ１と前記Ｘ２とを乗算して、第３乗算値（Ｘ１ｘＸ２）として算出する。第４乗算器Ｘ４は、前記Ｚ１と前記Ｚ２とを乗算して、第４乗算値（Ｚ１ｘＺ２）として算出する。
【００８２】
第５乗算器Ｘ５は、前記第４乗算値に第１所定数である前記ａを乗算して、第５乗算値（ａｘＺ１ｘＺ２）として算出する。第２加算器＋２は、前記第３乗算値と前記第５乗算値とを加算して、第２加算値（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）として算出する。
【００８３】
第６乗算器Ｘ６は、前記第１加算値と前記第２加算値とを乗算して、第６乗算値（（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する。第３加算器＋３は、前記第６乗算値同士加算して、前記第６乗算値の２倍である第３加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する。
【００８４】
第１算出手段Ｃ１１は、前記第４乗算値を２倍にして自乗した結果に第２所定数である前記ｂを乗算して、第１算出値（４ｘｂｘＺ１２ｘＺ２２）として算出する。第１算出手段Ｃ１１は、第１１加算器＋１１、第１１自乗器Ｓ１１及び第１１乗算器Ｘ１１を備える。第１１加算器＋１１は、前記第４乗算値同士加算して、前記第４乗算値の２倍である第１１加算値（２ｘＺ１ｘＺ２）として算出する。第１１自乗器Ｓ１１は、前記第１１加算値を自乗して、第１１自乗値（４ｘＺ１２ｘＺ２２）として算出する。第１１乗算器Ｘ１１は、前記第１１自乗値に前記ｂを乗算して、前記第１算出値として算出する。
【００８５】
第４加算器＋４は、前記第３加算値と前記第１算出値とを加算して、第４加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２）として算出する。第７乗算器Ｘ７は、前記第４加算値に前記ＺＤを乗算して、第７乗算値（ＺＤｘ［２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２］）として算出する。
【００８６】
第２算出手段Ｃ１２は、前記第１乗算値から前記第２乗算値を減算して自乗した結果に前記ＸＤを乗算して、第２算出値（ＸＤｘ（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する。第２算出手段Ｃ１２は、第１２減算器−１２、第１２自乗器Ｓ１２及び第１２乗算器Ｘ１２を備える。第１２減算器−１２は、前記第１乗算値から前記第２乗算値を減算して、第１２減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する。第１２自乗器Ｓ１２は、前記第１２減算値を自乗して、第１２自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する。第１２乗算器Ｘ２１は、前記第１２自乗値と前記ＸＤとを乗算して、前記第２算出値として算出する。
【００８７】
第１減算器−１は、前記第７乗算値から前記第２算出値を減算して、前記第１ポイント及び前記第２ポイントについての加算演算の結果のＸ座標値（Ｘ３）として算出する。
第２座標算出部Ｃ２２は、第２１ないし第２３乗算器Ｘ２１，Ｘ２２，Ｘ２３、第２１減算器−２１及び第２１自乗器Ｓ２１を備えることである。
【００８８】
第２１乗算器Ｘ２１は、前記Ｘ１と前記Ｚ２とを乗算して、第２１乗算値（Ｘ１ｘＺ２）として算出する。第２２乗算器Ｘ２２は、前記Ｘ２と前記Ｚ１とを乗算して、第２２乗算値（Ｘ２ｘＺ１）として算出する。第２１減算器−２１は、前記第２１乗算値から前記第２２乗算値を減算して、第２１減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する。
【００８９】
前記第２１自乗器Ｓ２１は、前記第２１減算値を自乗して、第２１自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する。第２３乗算器Ｘ２３は、前記第２１自乗値に前記ＺＤを乗算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＺ座標値（Ｚ３）として算出する。
【００９０】
第２１乗算器Ｘ２１及び第２２乗算器Ｘ２２は、前記第１座標算出部の第１乗算器Ｘ１及び第２乗算器Ｘ２でありうる。また、第２１減算器−２１及び第２１自乗器Ｓ２１は、第２算出手段Ｃ１２の第１２減算器−１２及び第１２自乗器Ｓ１２でありうる。
【００９１】
図８の素数有限領域におけるポイント加算演算装置によって、前述した数式（１１）が具現されうる。数式（１２）は、次の図９の素数有限領域におけるポイント加算演算装置によって具現されうる。
【００９２】
図９は、本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
図９を参照すれば、本発明の実施形態による素数有限領域におけるポイント加算演算装置９００は、図８のポイント加算演算装置８００と同じ動作を行う。但し、図９のポイント加算演算装置９００は、第２ポイントＰ２の第２座標値（Ｚ座標値）が“１”である場合についてのポイント加算結果を算出する。したがって、図９のポイント加算演算装置９００は、図８のポイント加算演算装置８００と類似した構成を有するが、さらに少ない数の乗算器で具現されうる。
【００９３】
図９のポイント加算演算装置９００の第１座標算出部及び第２座標算出部は、図８のポイント加算演算装置８００の説明から容易に分かるので、これについてのさらに詳細な説明は省略する。
【００９４】
図１０は、図８及び図９の自乗器をさらに詳細に示す図面である。
図１０を参照すれば、自乗器Ｓは、同じ入力Ｉ１同士乗算Ｘする。このとき、自乗器Ｓは、図８及び図９の第１１自乗器Ｓ１１及び第１２自乗器Ｓ１２を表す。このように、同じ入力Ｉ１同士乗算Ｘするように自乗器Ｓを設計することによって、ポイント加算演算装置８００，９００のレイアウト面積を減らせるという長所がある。
【００９５】
以上、図面及び明細書で最適の実施形態が開示された。ここで、特定の用語が使用されたが、これは、単に本発明を説明するための目的で使われたものであり、意味限定や特許請求の範囲に記載された本発明の範囲を制限するために使われたものではない。したがって、当業者ならば、これから多様な変形及び均等な他の実施形態が可能であるという点が分かるであろう。したがって、本発明の真の技術的保護範囲は、特許請求の範囲の技術的思想によって決定されねばならない。
【産業上の利用可能性】
【００９６】
本発明は、暗号化方法関連の技術分野に適用可能である。
【図面の簡単な説明】
【００９７】
【図１】ＤＦＡに対応するＣＴ＆Ｃ方法を示すフローチャートである。
【図２】ＤＦＡに対応するＣＯＰ方法を示すフローチャートである。
【図３】ＭＰＬＡを利用してＥＣＣ方法におけるスカラー積演算を行う方法を示すフローチャートである。
【図４】定期チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【図５】最終チェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【図６】ランダムチェック方法が適用されたＦＭＰＬＡを利用した新たな方式の欠陥チェック動作を示すフローチャートである。
【図７】本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算方法を示すフローチャートである。
【図８】本発明の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
【図９】本発明の他の実施形態によるＦＭＰＬＡを利用する欠陥検出動作を具現するための素数有限領域におけるポイント加算演算装置を示す図面である。
【図１０】図８及び図９の自乗器をさらに詳細に示す図面である。
【符号の説明】
【００９８】
８００ ポイント加算演算装置
Ｃ１１ 第１算出手段
Ｃ１２ 第２算出手段
Ｘ１〜Ｘ７ 第１ないし第７乗算器
＋１〜＋４ 第１ないし第４加算器
−１ 第１減算器
Ｓ１１ 第１１自乗器
Ｓ１２ 第１２自乗器
＋１１ 第１１加算器
−１２ 第１２減算器
【特許請求の範囲】
【請求項１】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算方法において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するステップと、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するステップと、を含み、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算は、
前記第１ポイント及び前記第２ポイントの第１座標値と第２座標値との差を反映することを特徴とする素数有限領域におけるポイント加算方法。
【請求項２】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項１に記載の素数有限領域におけるポイント加算方法。
【請求項３】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項１に記載の素数有限領域におけるポイント加算方法。
【請求項４】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数１】
であることを特徴とする請求項３に記載の素数有限領域におけるポイント加算方法。
【請求項５】
前記第２ポイントの前記第２座標値は、
“１”であることを特徴とする請求項４に記載の素数有限領域におけるポイント加算方法。
【請求項６】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算方法において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するステップと、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するステップと、を含み、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算は、
前記第１ポイント及び前記第２ポイントの第１座標値と第２座標値との差を反映し、
前記第２ポイントの前記第２座標値は、
所定数に固定されることを特徴とする素数有限領域におけるポイント加算方法。
【請求項７】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項６に記載の素数有限領域におけるポイント加算方法。
【請求項８】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項６に記載の素数有限領域におけるポイント加算方法。
【請求項９】
前記第２ポイントのＺ座標値は、
“１”であることを特徴とする請求項８に記載の素数有限領域におけるポイント加算方法。
【請求項１０】
前記第１ポイントを Ｐ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,１）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（１−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数２】
であることを特徴とする請求項９に記載の素数有限領域におけるポイント加算方法。
【請求項１１】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算装置において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出する第１座標算出部と、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出する第２座標算出部と、を備え、
前記第１座標算出部及び前記第２座標算出部は、
前記第１ポイント及び前記第２ポイントの第２座標値の差を反映して前記第１座標値及び前記第２座標値を算出することを特徴とする素数有限領域におけるポイント加算演算装置。
【請求項１２】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項１１に記載の素数有限領域におけるポイント加算演算装置。
【請求項１３】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項１１に記載の素数有限領域におけるポイント加算演算装置。
【請求項１４】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数３】
であることを特徴とする請求項１３に記載の素数有限領域におけるポイント加算演算装置。
【請求項１５】
前記第１座標算出部は、
前記Ｘ１と前記Ｚ２とを乗算して、第１乗算値（Ｘ１ｘＺ２）として算出する第１乗算器と、
前記Ｘ２と前記Ｚ１とを乗算して、第２乗算値（Ｘ２ｘＺ１）として算出する第２乗算器と、
前記第１乗算値と前記第２乗算値とを加算して、第１加算値（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）として算出する第１加算器と、
前記Ｘ１と前記Ｘ２とを乗算して、第３乗算値（Ｘ１ｘＸ２）として算出する第３乗算器と、
前記Ｚ１と前記Ｚ２とを乗算して、第４乗算値（Ｚ１ｘＺ２）として算出する第４乗算器と、
前記第４乗算値に第１所定数である前記ａを乗算して、第５乗算値（ａｘＺ１ｘＺ２）として算出する第５乗算器と、
前記第３乗算値と前記第５乗算値とを加算して、第２加算値（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）として算出する第２加算器と、
前記第１加算値と前記第２加算値とを乗算して、第６乗算値（（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する第６乗算器と、
前記第６乗算値同士加算して、前記第６乗算値の２倍である第３加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する第３加算器と、
前記第４乗算値を２倍にして自乗した結果に第２所定数である前記ｂを乗算し、第１算出値（４ｘｂｘＺ１２ｘＺ２２）として算出する第１算出手段と、
前記第３加算値と前記第１算出値とを加算して、第４加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２）として算出する第４加算器と、
前記第４加算値に前記ＺＤを乗算して、第７乗算値（ＺＤｘ［２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２］）として算出する第７乗算器と、
前記第１乗算値から前記第２乗算値を減算して自乗した結果に前記ＸＤを乗算して、第２算出値（ＸＤｘ（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する第２算出手段と、
前記第７乗算値から前記第２算出値を減算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＸ座標値（Ｘ３）として算出する第１減算器と、を備えることを特徴とする請求項１４に記載の素数有限領域におけるポイント加算演算装置。
【請求項１６】
前記第１算出手段は、
前記第４乗算値同士加算して、前記第４乗算値の２倍である第１１加算値（２ｘＺ１ｘＺ２）として算出する第１１加算器と、
前記第１１加算値を自乗して、第１１自乗値（４ｘＺ１２ｘＺ２２）として算出する第１１自乗器と、
前記第１１自乗値に前記ｂを乗算して、前記第１算出値として算出する第１１乗算器と、を備えることを特徴とする請求項１５に記載の素数有限領域におけるポイント加算演算装置。
【請求項１７】
前記第１１自乗器は、
前記第１１加算値同士乗算することを特徴とする請求項１６に記載の素数有限領域におけるポイント加算演算装置。
【請求項１８】
前記第２算出手段は、
前記第１乗算値から前記第２乗算値を減算して、第１２減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する第２１減算器と、
前記第１２減算値を自乗して、第１２自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する第１２自乗器と、
前記第１２自乗値と前記ＸＤとを乗算して、前記第２算出値として算出する第１２乗算器と、を備えることを特徴とする請求項１５に記載の素数有限領域におけるポイント加算演算装置。
【請求項１９】
前記第１２自乗器は、
前記第１２減算値同士乗算することを特徴とする請求項１８に記載の素数有限領域におけるポイント加算演算装置。
【請求項２０】
前記第２座標算出部は、
前記Ｘ１と前記Ｚ２とを乗算して、第２１乗算値（Ｘ１ｘＺ２）として算出する第２１乗算器と、
前記Ｘ２と前記Ｚ１とを乗算して、第２２乗算値（Ｘ２ｘＺ１）として算出する第２２乗算器と、
前記第２１乗算値から前記第２２乗算値を減算して、第２１減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する第２１減算器と、
前記第２１減算値を自乗して、第２１自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する第２１自乗器と、
前記第２１自乗値に前記ＺＤを乗算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＺ座標値（Ｚ３）として算出する第２３乗算器と、を備えることを特徴とする請求項１４に記載の素数有限領域におけるポイント加算演算装置。
【請求項２１】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算装置において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出する第１座標算出部と、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出する第２座標算出部と、を備え、
前記第１座標算出部及び前記第２座標算出部は、
前記第１ポイント及び前記第２ポイントの第２座標値の差を反映して前記第１座標値及び前記第２座標値を算出して、
前記第２ポイントの第２座標値は、
所定数に固定されることを特徴とする素数有限領域におけるポイント加算演算装置。
【請求項２２】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項２１に記載の素数有限領域におけるポイント加算演算装置。
【請求項２３】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項２２に記載の素数有限領域におけるポイント加算演算装置。
【請求項２４】
前記第２ポイントのＺ座標値は、
“１”であることを特徴とする請求項２３に記載の素数有限領域におけるポイント加算演算装置。
【請求項２５】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,１）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（１−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数４】
であることを特徴とする請求項２４に記載の素数有限領域におけるポイント加算演算装置。
【請求項２６】
前記第１座標算出部は、
前記Ｘ２と前記Ｚ１とを乗算して、第１乗算値（Ｘ２ｘＺ１）として算出する第１乗算器と、
前記第１乗算値と前記Ｘ１とを加算して、第１加算値（Ｘ１＋Ｘ２ｘＺ１）として算出する第１加算器と、
前記Ｘ１と前記Ｘ２とを乗算して、第２乗算値（Ｘ１ｘＸ２）として算出する第２乗算器と、
前記Ｚ１に第１所定数であるａを乗算して、第３乗算値（ａｘＺ１）として算出する第３乗算器と、
前記第２乗算値と前記第３乗算値とを加算して、第２加算値（Ｘ１ｘＸ２＋ａｘＺ１）として算出する第２加算器と、
前記第１加算値と前記第２加算値とを乗算して、第４乗算値（（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１））として算出する第４乗算器と、
前記第４乗算値同士加算して、前記第４乗算値の２倍である第３加算値（２ｘ（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１））として算出する第３加算器と、
前記Ｚ１を２倍にして自乗した結果に第２所定数である前記ｂを乗算して、第１算出値（４ｘｂｘＺ１２）として算出する第１算出手段と、
前記第３加算値と前記第１算出値とを加算して、第４加算値（２ｘ（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１）＋４ｘｂｘＺ１２）として算出する第４加算器と、
前記第４加算値に前記ＺＤを乗算して、第５乗算値（ＺＤｘ［２ｘ（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１）＋４ｘｂｘＺ１２］）として算出する第５乗算器と、
前記Ｘ１から前記第１乗算値を減算して自乗した結果に前記ＸＤを乗算して、第２算出値（ＸＤｘ（Ｘ１−Ｚ１ｘＺ２）２）として算出する第２算出手段と、
前記第５乗算値から前記第２算出値を減算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＸ座標値（Ｘ３）として算出する第１減算器と、を備えることを特徴とする請求項２５に記載の素数有限領域におけるポイント加算演算装置。
【請求項２７】
前記第１算出手段は、
前記Ｚ１同士加算して、前記Ｚ１の２倍である第１１加算値（２ｘＺ１）として算出する第１１加算器と、
前記第１１加算値を自乗して、第１１自乗値（４ｘＺ１２）として算出する第１１自乗器と、
前記第１１自乗値に前記ｂを乗算して、前記第１算出値として算出する第１１乗算器と、を備えることを特徴とする請求項２６に記載の素数有限領域におけるポイント加算演算装置。
【請求項２８】
前記第１１自乗器は、
前記第１１加算値同士乗算することを特徴とする請求項２７に記載の素数有限領域におけるポイント加算演算装置。
【請求項２９】
前記第２算出手段は、
前記Ｘ１から前記第１乗算値を減算して、第１２減算値（Ｘ１−Ｘ２ｘＺ１）として算出する第１２減算器と、
前記第１２減算値を自乗して、第１２自乗値（（Ｘ１−Ｘ２ｘＺ１）２）として算出する第１２自乗器と、
前記第１２自乗値と前記ＸＤとを乗算して、前記第２算出値として算出する第１２乗算器と、を備えることを特徴とする請求項２６に記載の素数有限領域におけるポイント加算演算装置。
【請求項３０】
前記第１２自乗器は、
前記第１２減算値同士乗算することを特徴とする請求項２９に記載の素数有限領域におけるポイント加算演算装置。
【請求項３１】
前記第２座標算出部は、
前記Ｘ２と前記Ｚ１とを乗算して、第２１乗算値（Ｘ２ｘＺ１）として算出する第２１乗算器と、
前記第２１乗算値から前記Ｘ１を減算して、第２１減算値（Ｘ１−Ｘ２ｘＺ１）として算出する第２１減算器と、
前記第２１減算値を自乗して、第２１自乗値（（Ｘ１−Ｘ２ｘＺ１）２）として算出する第２１自乗器と、
前記第２１自乗値に前記ＺＤを乗算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＺ座標値（Ｚ３）として算出する第２２乗算器と、を備えることを特徴とする請求項２５に記載の素数有限領域におけるポイント加算演算装置。
【請求項１】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算方法において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するステップと、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するステップと、を含み、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算は、
前記第１ポイント及び前記第２ポイントの第１座標値と第２座標値との差を反映することを特徴とする素数有限領域におけるポイント加算方法。
【請求項２】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項１に記載の素数有限領域におけるポイント加算方法。
【請求項３】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項１に記載の素数有限領域におけるポイント加算方法。
【請求項４】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数１】
であることを特徴とする請求項３に記載の素数有限領域におけるポイント加算方法。
【請求項５】
前記第２ポイントの前記第２座標値は、
“１”であることを特徴とする請求項４に記載の素数有限領域におけるポイント加算方法。
【請求項６】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算方法において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出するステップと、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出するステップと、を含み、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算は、
前記第１ポイント及び前記第２ポイントの第１座標値と第２座標値との差を反映し、
前記第２ポイントの前記第２座標値は、
所定数に固定されることを特徴とする素数有限領域におけるポイント加算方法。
【請求項７】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項６に記載の素数有限領域におけるポイント加算方法。
【請求項８】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項６に記載の素数有限領域におけるポイント加算方法。
【請求項９】
前記第２ポイントのＺ座標値は、
“１”であることを特徴とする請求項８に記載の素数有限領域におけるポイント加算方法。
【請求項１０】
前記第１ポイントを Ｐ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,１）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（１−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数２】
であることを特徴とする請求項９に記載の素数有限領域におけるポイント加算方法。
【請求項１１】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算装置において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出する第１座標算出部と、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出する第２座標算出部と、を備え、
前記第１座標算出部及び前記第２座標算出部は、
前記第１ポイント及び前記第２ポイントの第２座標値の差を反映して前記第１座標値及び前記第２座標値を算出することを特徴とする素数有限領域におけるポイント加算演算装置。
【請求項１２】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項１１に記載の素数有限領域におけるポイント加算演算装置。
【請求項１３】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項１１に記載の素数有限領域におけるポイント加算演算装置。
【請求項１４】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,Ｚ２）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（Ｚ２−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数３】
であることを特徴とする請求項１３に記載の素数有限領域におけるポイント加算演算装置。
【請求項１５】
前記第１座標算出部は、
前記Ｘ１と前記Ｚ２とを乗算して、第１乗算値（Ｘ１ｘＺ２）として算出する第１乗算器と、
前記Ｘ２と前記Ｚ１とを乗算して、第２乗算値（Ｘ２ｘＺ１）として算出する第２乗算器と、
前記第１乗算値と前記第２乗算値とを加算して、第１加算値（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）として算出する第１加算器と、
前記Ｘ１と前記Ｘ２とを乗算して、第３乗算値（Ｘ１ｘＸ２）として算出する第３乗算器と、
前記Ｚ１と前記Ｚ２とを乗算して、第４乗算値（Ｚ１ｘＺ２）として算出する第４乗算器と、
前記第４乗算値に第１所定数である前記ａを乗算して、第５乗算値（ａｘＺ１ｘＺ２）として算出する第５乗算器と、
前記第３乗算値と前記第５乗算値とを加算して、第２加算値（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）として算出する第２加算器と、
前記第１加算値と前記第２加算値とを乗算して、第６乗算値（（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する第６乗算器と、
前記第６乗算値同士加算して、前記第６乗算値の２倍である第３加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２））として算出する第３加算器と、
前記第４乗算値を２倍にして自乗した結果に第２所定数である前記ｂを乗算し、第１算出値（４ｘｂｘＺ１２ｘＺ２２）として算出する第１算出手段と、
前記第３加算値と前記第１算出値とを加算して、第４加算値（２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２）として算出する第４加算器と、
前記第４加算値に前記ＺＤを乗算して、第７乗算値（ＺＤｘ［２ｘ（Ｘ１ｘＺ２＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１ｘＺ２）＋４ｘｂｘＺ１２ｘＺ２２］）として算出する第７乗算器と、
前記第１乗算値から前記第２乗算値を減算して自乗した結果に前記ＸＤを乗算して、第２算出値（ＸＤｘ（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する第２算出手段と、
前記第７乗算値から前記第２算出値を減算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＸ座標値（Ｘ３）として算出する第１減算器と、を備えることを特徴とする請求項１４に記載の素数有限領域におけるポイント加算演算装置。
【請求項１６】
前記第１算出手段は、
前記第４乗算値同士加算して、前記第４乗算値の２倍である第１１加算値（２ｘＺ１ｘＺ２）として算出する第１１加算器と、
前記第１１加算値を自乗して、第１１自乗値（４ｘＺ１２ｘＺ２２）として算出する第１１自乗器と、
前記第１１自乗値に前記ｂを乗算して、前記第１算出値として算出する第１１乗算器と、を備えることを特徴とする請求項１５に記載の素数有限領域におけるポイント加算演算装置。
【請求項１７】
前記第１１自乗器は、
前記第１１加算値同士乗算することを特徴とする請求項１６に記載の素数有限領域におけるポイント加算演算装置。
【請求項１８】
前記第２算出手段は、
前記第１乗算値から前記第２乗算値を減算して、第１２減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する第２１減算器と、
前記第１２減算値を自乗して、第１２自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する第１２自乗器と、
前記第１２自乗値と前記ＸＤとを乗算して、前記第２算出値として算出する第１２乗算器と、を備えることを特徴とする請求項１５に記載の素数有限領域におけるポイント加算演算装置。
【請求項１９】
前記第１２自乗器は、
前記第１２減算値同士乗算することを特徴とする請求項１８に記載の素数有限領域におけるポイント加算演算装置。
【請求項２０】
前記第２座標算出部は、
前記Ｘ１と前記Ｚ２とを乗算して、第２１乗算値（Ｘ１ｘＺ２）として算出する第２１乗算器と、
前記Ｘ２と前記Ｚ１とを乗算して、第２２乗算値（Ｘ２ｘＺ１）として算出する第２２乗算器と、
前記第２１乗算値から前記第２２乗算値を減算して、第２１減算値（Ｘ１ｘＺ２−Ｘ２ｘＺ１）として算出する第２１減算器と、
前記第２１減算値を自乗して、第２１自乗値（（Ｘ１ｘＺ２−Ｘ２ｘＺ１）２）として算出する第２１自乗器と、
前記第２１自乗値に前記ＺＤを乗算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＺ座標値（Ｚ３）として算出する第２３乗算器と、を備えることを特徴とする請求項１４に記載の素数有限領域におけるポイント加算演算装置。
【請求項２１】
高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作を具現するためのポイント加算演算装置において、
所定の楕円曲線上の基本ポイントを利用して設定された第１ポイント及び第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第１座標値を算出する第１座標算出部と、
前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算を行って、前記加算演算の結果の第２座標値を算出する第２座標算出部と、を備え、
前記第１座標算出部及び前記第２座標算出部は、
前記第１ポイント及び前記第２ポイントの第２座標値の差を反映して前記第１座標値及び前記第２座標値を算出して、
前記第２ポイントの第２座標値は、
所定数に固定されることを特徴とする素数有限領域におけるポイント加算演算装置。
【請求項２２】
前記高速モンゴメリ電力ラダーアルゴリズムを利用する欠陥検出動作は、
楕円曲線暗号化システムに適用されることを特徴とする請求項２１に記載の素数有限領域におけるポイント加算演算装置。
【請求項２３】
前記第１座標値は、“Ｘ”座標値であり、前記第２座標値は、“Ｚ”座標値であることを特徴とする請求項２２に記載の素数有限領域におけるポイント加算演算装置。
【請求項２４】
前記第２ポイントのＺ座標値は、
“１”であることを特徴とする請求項２３に記載の素数有限領域におけるポイント加算演算装置。
【請求項２５】
前記第１ポイントをＰ１（Ｘ１,Ｚ１）、前記第２ポイントをＰ２（Ｘ２,１）とし、前記前記第１ポイント及び前記第２ポイントのＸ座標値の差（Ｘ２−Ｘ１）とＺ座標値の差（１−Ｚ１）とをそれぞれＸＤ及びＺＤとするとき、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果であるＰ３（Ｘ３,Ｚ３）は、
【数４】
であることを特徴とする請求項２４に記載の素数有限領域におけるポイント加算演算装置。
【請求項２６】
前記第１座標算出部は、
前記Ｘ２と前記Ｚ１とを乗算して、第１乗算値（Ｘ２ｘＺ１）として算出する第１乗算器と、
前記第１乗算値と前記Ｘ１とを加算して、第１加算値（Ｘ１＋Ｘ２ｘＺ１）として算出する第１加算器と、
前記Ｘ１と前記Ｘ２とを乗算して、第２乗算値（Ｘ１ｘＸ２）として算出する第２乗算器と、
前記Ｚ１に第１所定数であるａを乗算して、第３乗算値（ａｘＺ１）として算出する第３乗算器と、
前記第２乗算値と前記第３乗算値とを加算して、第２加算値（Ｘ１ｘＸ２＋ａｘＺ１）として算出する第２加算器と、
前記第１加算値と前記第２加算値とを乗算して、第４乗算値（（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１））として算出する第４乗算器と、
前記第４乗算値同士加算して、前記第４乗算値の２倍である第３加算値（２ｘ（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１））として算出する第３加算器と、
前記Ｚ１を２倍にして自乗した結果に第２所定数である前記ｂを乗算して、第１算出値（４ｘｂｘＺ１２）として算出する第１算出手段と、
前記第３加算値と前記第１算出値とを加算して、第４加算値（２ｘ（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１）＋４ｘｂｘＺ１２）として算出する第４加算器と、
前記第４加算値に前記ＺＤを乗算して、第５乗算値（ＺＤｘ［２ｘ（Ｘ１＋Ｘ２ｘＺ１）ｘ（Ｘ１ｘＸ２＋ａｘＺ１）＋４ｘｂｘＺ１２］）として算出する第５乗算器と、
前記Ｘ１から前記第１乗算値を減算して自乗した結果に前記ＸＤを乗算して、第２算出値（ＸＤｘ（Ｘ１−Ｚ１ｘＺ２）２）として算出する第２算出手段と、
前記第５乗算値から前記第２算出値を減算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＸ座標値（Ｘ３）として算出する第１減算器と、を備えることを特徴とする請求項２５に記載の素数有限領域におけるポイント加算演算装置。
【請求項２７】
前記第１算出手段は、
前記Ｚ１同士加算して、前記Ｚ１の２倍である第１１加算値（２ｘＺ１）として算出する第１１加算器と、
前記第１１加算値を自乗して、第１１自乗値（４ｘＺ１２）として算出する第１１自乗器と、
前記第１１自乗値に前記ｂを乗算して、前記第１算出値として算出する第１１乗算器と、を備えることを特徴とする請求項２６に記載の素数有限領域におけるポイント加算演算装置。
【請求項２８】
前記第１１自乗器は、
前記第１１加算値同士乗算することを特徴とする請求項２７に記載の素数有限領域におけるポイント加算演算装置。
【請求項２９】
前記第２算出手段は、
前記Ｘ１から前記第１乗算値を減算して、第１２減算値（Ｘ１−Ｘ２ｘＺ１）として算出する第１２減算器と、
前記第１２減算値を自乗して、第１２自乗値（（Ｘ１−Ｘ２ｘＺ１）２）として算出する第１２自乗器と、
前記第１２自乗値と前記ＸＤとを乗算して、前記第２算出値として算出する第１２乗算器と、を備えることを特徴とする請求項２６に記載の素数有限領域におけるポイント加算演算装置。
【請求項３０】
前記第１２自乗器は、
前記第１２減算値同士乗算することを特徴とする請求項２９に記載の素数有限領域におけるポイント加算演算装置。
【請求項３１】
前記第２座標算出部は、
前記Ｘ２と前記Ｚ１とを乗算して、第２１乗算値（Ｘ２ｘＺ１）として算出する第２１乗算器と、
前記第２１乗算値から前記Ｘ１を減算して、第２１減算値（Ｘ１−Ｘ２ｘＺ１）として算出する第２１減算器と、
前記第２１減算値を自乗して、第２１自乗値（（Ｘ１−Ｘ２ｘＺ１）２）として算出する第２１自乗器と、
前記第２１自乗値に前記ＺＤを乗算して、前記第１ポイント及び前記第２ポイントについての素数有限領域における加算演算の結果のＺ座標値（Ｚ３）として算出する第２２乗算器と、を備えることを特徴とする請求項２５に記載の素数有限領域におけるポイント加算演算装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００８−４２９０５（Ｐ２００８−４２９０５Ａ）
【公開日】平成２０年２月２１日（２００８．２．２１）
【国際特許分類】
【出願番号】特願２００７−１９６２６９（Ｐ２００７−１９６２６９）
【出願日】平成１９年７月２７日（２００７．７．２７）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】Ｓａｍｓｕｎｇ Ｅｌｅｃｔｒｏｎｉｃｓ Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２０年２月２１日（２００８．２．２１）
【国際特許分類】
【出願日】平成１９年７月２７日（２００７．７．２７）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】Ｓａｍｓｕｎｇ Ｅｌｅｃｔｒｏｎｉｃｓ Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]