楕円曲線の点の符号化
本発明は、電子構成部品において、等式Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６に従う楕円曲線上の点Ｐを得るステップを含む、暗号化計算を実行するステップを有する。ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、また、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数から生じる正の整数であり、Ｉが２より高いか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、または、ｑが素数の整数の累乗である有限体Ｆｑであり、また、ＸおよびＹは、点Ｐの座標であり、かつＡの要素である。本方法は、パラメータ（１１）を決めるステップ、および前記パラメータに関数（１２）を適用することにより点Ｐ（１３）の座標ＸおよびＹを得るステップを有する。Ａのオイラー関数φは、等式φ（Ａ） ｍｏｄ ３＝１に対応する。前記関数は、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡ内の前記パラメータにおいて有理分数によって表される可逆的決定論的関数であり、Ｉが有限体Ｐｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐに到達する。本方法は、暗号化またはハッシングまたは署名または認証または識別のための暗号化計算において点Ｐを使用するステップをさらに有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線の点の使用に基づくメッセージの暗号化に関し、より具体的には、決定論的なやり方でのそのような暗号化に関する。
【背景技術】
【０００２】
メッセージに暗号化計算を適用するためには、通常、数学的構造の中に任意の値を挿入するためのアルゴリズムが実行される。この目的のために、楕円曲線は、そのような暗号化計算を容易にし、他の暗号化計算の実行に関してメモリ空間を節減することを可能にする数学的構造である。
【０００３】
しかし、楕円曲線を使用した、任意の値を挿入するための効率のよいアルゴリズムは、確率的である。したがって、そのようなアルゴリズムの実行時間は、一定でなく、符号化されるべきメッセージに依存する。したがって、攻撃者は、適用されたアルゴリズムの様々な実行時間を決めれば、符号化されたメッセージについての情報を得ることができる。
【０００４】
確率的挿入アルゴリズムによって使用された時間を隠すために、どのようなメッセージが処理されても、その適用が常に同一の長さの時間帯に及ぶように、このアルゴリズムに無用なステップを付加するための規定が行われてよい。
【０００５】
しかし、そのような処理は扱いにくく、多くの時間を消費する。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、この状況を改善することである。
【課題を解決するための手段】
【０００７】
本発明の第１の態様は、以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ パラメータ（１１）を決めるステップと、
／ｂ／ 前記パラメータに関数（１２）を適用することにより、点Ｐ（１３）の座標ＸおよびＹを得るステップであって、
Ａのオイラー関数φが、等式
φ（Ａ） ｍｏｄ ３＝１
を満たし、
上記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表された可逆的決定論的関数であり、Ｉが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記点Ｐを使用するステップと
を有する方法を提案する。
【０００８】
「少なくとも所与の個数の点を得る」という表現は、考察される関数が出力において少なくともこの所与の個数の異なる点を提供するように適応されるということを意味するものとする。
【０００９】
これらの規定によって、電子構成部品において、潜在的攻撃者に情報を提供することなく、高いレベルの実行効率を維持しながら、楕円曲線の点に基づく暗号化計算を実行することが可能である。実際、上記関数は、有理分数である楕円曲線上の点を得ることを可能にし、したがって、確率的関数ではく、決定論的関数であり、それを計算するのにかかる時間は、入力パラメータが何であっても、一定である。これらの条件の下で、楕円曲線上の点を得ることは効率がよく、計算時間は、従来技術とは対照的に、もはや符号化されるべきメッセージに依存しない。
【００１０】
環Ａは、ＲＳＡ（「Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ」を表す）環でよい。この場合、この環は、Ｚ／ｑＺと書かれることが可能であり、ｑは２つの素数の積に等しく、それらのための積φ（Ａ）は計算するのが難しい。
【００１１】
環Ａに関するオイラー関数φは、この環Ａにおける可逆的要素の数を提供する関数であることが留意される。Ａが有限体Ｆｑである場合は、
φ（Ａ）＝ｑ−１
を得る。
【００１２】
ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいかまたは等しい整数である、モジュラ整数Ｚ／ｑＺの環を考察することにより、
φ（Ａ）＝ｌｃｍ（ｐ１−１，ｐ２−１，．．．，ｐＩ−１）
を得る。
【００１３】
ここで、ｌｃｍは、最小公倍数を表し、ｐｉは、Ｉの素数である。
【００１４】
本発明の一実施形態による決定論的関数が有理分数の形で表されるとすれば、それらの適用は、それが適用されるメッセージまたはデータが何であっても、常に同じ時間を必要とする。
【００１５】
実際、集合Ａにおいては、３乗および１／３乗するための関数は、全単射である。したがって、それらの関数は有理分数の形で書かれ、したがって、決定論的関数ｆは、有理分数の形で書かれることが可能である。集合Ａにおいては、１／３乗の計算は、（２φ（ａ）＋１）／３乗の計算と同じである。後者は、φ（Ａ）ｍｏｄ３＝１なので、整数である。以下の等式がＡにおいて満たされる。
【００１６】
【数１】
この等式から、以下の等式が推定される。
【００１７】
【数２】
【００１８】
したがって、
【００１９】
【数３】
と書くことが可能である。
【００２０】
次に、楕円曲線の点Ｐを得ることを可能にする関数ｆは、この１／３乗することを有する。
【００２１】
したがって、Ａの要素が何であっても、１／３乗するための関数が一定の時間で計算されるということによって、確率を扱う必要なしに楕円曲線の点を得ることが可能である。したがって、暗号化計算のための実行時間が、従来技術において行われるような確率的なやり方でのそのような計算の実行の場合のあるようなメッセージに依存することは、この計算ではない。
【００２２】
さらに、Ａが有限体Ｆｑに対応する状況において、決定論的関数ｆは、楕円曲線の少なくともｑ／４個の点Ｐを提供することができる。ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいかまたは等しい整数である、モジュラ整数Ｚ／ｑＺの環にＡが対応する状況では、決定論的関数ｆは、楕円曲線の少なくともｑ／４Ｉ個の点Ｐを提供することができる。
【００２３】
楕円曲線上の、決定論的なやり方でこのようにして得られたそのような点の個数は、潜在的な攻撃に対する高いレベルのセキュリティを有する多くの暗号化アプリケーションを可能にする。
【００２４】
一実施形態では、使用される楕円曲線は、ワイエルシュトラス型の曲線であるか、そうでなければ特性ｐの曲線と呼ばれる。ここでは、ｑは２ｎとは異なると考えられる。
【００２５】
等式（１）は、
Ｙ２＝Ｘ３＋ａＸ＋ｂ
と書かれてよく、ａ＝ａ２、およびｂ＝ａ６である。
【００２６】
決定論的関数は、以下のそれぞれの等式によって楕円曲線の点の座標を提供する。
【００２７】
【数４】
ここで、ｕは、ステップ／ａ／において決められたパラメータであり、ｖ＝（３ａ−ｕ４）／（６ｕ）である。
【００２８】
他の実施形態では、本発明は、特性２の楕円曲線に適用される。
【００２９】
この場合、ｑは、等式
ｑ＝２ｎ
を満たし、
ここで、ｎは、奇数の整数であり、
等式（１）は、
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ
と書かれてよく、ａ＝ａ２、およびｂ＝ａ６であり、
決定論的関数は、以下のそれぞれの等式による楕円曲線の点の座標を提供し、
【００３０】
【数５】
ここで、ｕは、ステップ／ａ／において決められたパラメータであり、ここで、ｗ＝ａ＋ｕ２＋ｕである。
【００３１】
有利な特定の場合には、ｎは、素数の奇数の整数である。実際、そのようなｎは、いくつかの攻撃を制限することを可能にする。
【００３２】
この状況では、決定論的関数は、楕円曲線の少なくとも２ｎ−２個の点Ｐを有利に提供することができる。
【００３３】
ｂが１に等しく、ａがＦ２に属する特性２の楕円曲線の特定の場合に、この関数をコブリッツ型の楕円曲線に適用することは、有利に可能である。実際、コブリッツ楕円曲線を使用することにより、暗号化計算をより速く実行することが可能である。
【００３４】
この決定論的関数をハッシュ関数の結果に適用するための規定が行われてよい。したがって、ステップ／ａ／において、パラメータｕは、ハッシュ関数ｈを適用することにより得られることが可能である。
【００３５】
一実施形態では、ハッシュ関数は一方向関数である。この特性は保存され、決定論的関数とハッシュ関数を組み合わせることから生じる関数は、この一方向であるという特性を示す。
【００３６】
ここで、次いで、ハッシュ関数のような一方向である楕円曲線に関する関数が最終的に得られる。この関数は、さらに衝突耐性がある。
【００３７】
この決定論的関数が、楕円曲線に適用されるランダム関数から微分可能でないという特性（または「微分不可能」であるという特性）を示すようなやり方で、この決定論的関数を適用するための規定が行われてもよい。この特性は、特に、ハッシュ関数がランダムであると推定されるモデルにおいて安全であると分かっている暗号化方式においてこの関数が適用されたときに、利点を示す。実際、決定論的関数はランダム関数から微分可能でないという特性を示すので、この同じタイプの暗号化方式においてこの関数を適用することによって安全な暗号化方式が得られる。
【００３８】
ステップ／ａ／において、パラメータｕは、第１のハッシュ関数ｈおよび第２のハッシュ関数ｈ’を適用することにより得られることが可能である。楕円曲線の点の群の生成元は、Ｇとして示される。暗号化計算は、以下の関数の適用を有することができる。
【００３９】
【数６】
ここで、ｆは決定論的関数であり、ここで、Ｇは楕円曲線の点の群の生成元である。
【００４０】
この楕円曲線の点の群は、本発明の一実施形態による暗号化計算によって使用される点に対応することができる。
【００４１】
本発明の第２の態様は、本発明の第１の態様による暗号化計算を実行する方法を実施する少なくとも１つのパスワードによる認証の方法であって、ステップ／ａ／においてパラメータがパスワードの関数として決められ、前記パスワードがパラメータに含まれ、認証ステップが点Ｐに基づいて実行される、方法を提案する。
【００４２】
本発明の第３の態様は、データを暗号化する方法であって、前記暗号化は結合演算を許容する楕円曲線に関するボネ−フランクリン識別に基づき、前記識別は、エンティティを識別する数値であり、
前記方法が、
／ａ／ 請求項６に記載の暗号化計算を実行する方法を前記識別に適用することにより点を得るステップと、
／ｂ／ 前記点、ランダムパラメータおよびデータを組み合わせることにより、暗号化されたデータを得るステップと
を有する、方法を提供する。
【００４３】
ここで、用語「組み合わせる」は、結合演算、ハッシュ演算、「排他的論理和」演算およびスカラ乗法の組合せを適用するということを意味するものとする。
【００４４】
本発明の第４の態様は、以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ 楕円曲線上の座標ＸおよびＹを有する点Ｐを決めるステップと、
／ｂ／ 点Ｐに関数を適用することによりパラメータを得るステップであって、
Ａのオイラー関数φが、等式
φ（Ａ）ｍｏｄ３＝１
を満たし、
前記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表された決定論的関数の逆関数であり、Ｉが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記パラメータを使用するステップと
を含む方法を提案する。
【００４５】
ここで、本発明の第１の態様において述べられたような決定論的関数は、可逆的関数であることに留意されたい。したがって、この決定論的関数は、逆方向に有利に使用されることが可能であり、その逆関数が本発明のこの第１の態様において利用される。実際、第１の態様において述べられた関数の逆関数を介して楕円曲線の点に対応するパラメータを得るために楕円曲線の点から開始することは、暗号化分野において、特にデータ圧縮アプリケーションでは、有用であり得る。
【００４６】
したがって、本発明の第５の態様は、データ圧縮の方法であって、それぞれ、以下の等式を満たす楕円曲線の点Ｐの座標に対応するデータＸとＹの対に対応してデータが圧縮され、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいかまたは等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
本発明の第４の態様による暗号化計算を実行する方法のステップ／ａ／から／ｃ／がデータの前記対のそれぞれに適用され、
データの前記対がそれぞれステップ／ｃ／において得られたパラメータによって表される、
データ圧縮の方法を提案する。
【００４７】
本発明の第６の態様は、本発明の第１の態様による暗号化計算を実行する方法の実施に適応された手段を有する電子デバイスを提案する。
【００４８】
本発明の第７の態様は、本発明の第４の態様による暗号化計算を実行する方法の実施に適応された手段を有する電子デバイスを提案する。
【００４９】
本発明の第８の態様は、本発明の第６または第７の態様による電子デバイスを有するチップカードを提案する。
【００５０】
本発明の他の態様、目的、利点は、本発明の諸実施形態の１つの説明を読むと明らかになるであろう。
【００５１】
本発明はまた、本発明の一実施形態による暗号化計算の主なステップを図示する図１の助けを借りればよりよく理解されるであろう。
【図面の簡単な説明】
【００５２】
【図１】本発明の一実施形態による暗号化計算の主なステップを示す図である。
【発明を実施するための形態】
【００５３】
Ａに関するいかなる楕円曲線も、以下の等式を満たす。
【００５４】
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、Ａの要素であり、
ここで、ＸおよびＹは、集合Ａの要素である。
【００５５】
φがＡに適用されるオイラー関数である以下の等式が満たされる場合は、
φ（Ａ）＝１ｍｏｄ３ （２）
３乗するための関数および１／３乗するための関数は、計算される値が何であっても、一定の時間で効率よく計算されることが可能である。この特性は、パラメータの関数として楕円曲線の点Ｐを決定論的に得ることを可能にし、計算時間は、この決定論的関数ｆが適用されるパラメータに関係がない。
【００５６】
続いて、この関数ｆはまた、考察される楕円曲線の等式のタイプに応じて、ｆａ，ｂまたはそうでなければｆａとして示される。
【００５７】
図１は、ステップ１１において、パラメータｕ、考察される有限体Ｆｑの要素の決定を図示する。次に、ステップ１２において、最終的に、決定論的なやり方で楕円曲線の点Ｐを得るために、決定論的関数ｆがこのパラメータに適用される。すべてのこれらのステップは、等式（２）を満たす環Ａにおいて実行される。
【００５８】
以下のセクションは、楕円曲線の等式の特定の場合におけるこれらの特性の適用を提示する。本発明の一実施形態は、ワイエルシュトラス型の楕円曲線、すなわちｐ＞３である特性ｐを有する楕円曲線、および特性２を有する楕円曲線に適用されることが可能である。
【００５９】
以下のセクションでは、考察される楕円曲線は、体Ｆｑに関するワイエルシュトラス型のものである。
【００６０】
この状況では、考察される有限ガロア体の基数ｑは、ｐｎに等しく、ここで、ｐは、値２および３とは異なる素数である。等式（１）は、ワイエルシュトラスの等式、
Ｙ２＝Ｘ３＋ａＸ＋ｂ （３）
によって書かれることが可能であり、
ここで、ａおよびｂは、Ｅａ，ｂとして示される楕円曲線のパラメータである。
【００６１】
ｑが等式（２）を満たす要素の数ｑを有する有限体Ａ＝Ｆｑにおいては、３乗するための関数ｆおよび１／３乗するための関数は、それらが計算される値が何であっても、一定の時間で効率よく計算されることが可能である全単射である。
【００６２】
これらの条件の下で、楕円曲線の点Ｐの座標ＸおよびＹは、以下のそれぞれの等式を満たす。
【００６３】
【数７】
ここで、
ｖ＝（３ａ−ｕ４）／（６ｕ） （６）
であり、
ここで、ｕは、本発明の一実施形態によるパラメータであり、ｕは、有限体Ｆｑ＊に属する。
【００６４】
有限体Ｆｑにおいて、（（２φ（Ａ）＋１）／３）乗することは、１／３乗することに対応することが留意される。
【００６５】
したがって、暗号化計算の実行のために使用される楕円曲線が、ワイエルシュトラス型のものである場合、パラメータｕに関して一定の計算時間で決定論的なやり方で、等式（４）および（５）によって、パラメータｕの関数として楕円曲線の点Ｐを得ることが有利に可能である。
【００６６】
実際、等式（４）および（５）を満たす座標を有する点Ｐは、等式（５）による直線の考察される楕円曲線（３）との交点が以下の等式のシステムを満たすので、等式（３）による楕円曲線の一意の点に対応する。
【００６７】
Ｙ２＝Ｘ３＋ａＸ＋ｂ （７）
および
Ｙ＝ｕＸ＋ｖ （５）
【００６８】
この等式のシステムは、以下のように書かれることが可能である。
【００６９】
【数８】
【００７０】
前者の等式は、以下のようにさらに簡約されることが可能である。
【００７１】
【数９】
したがって、この等式のシステムは、最終的に、
【００７２】
【数１０】
と書かれることが可能である。
等式（１０）は等式（４）に対応し、そのことから、Ｐは考察される楕円曲線の点であることが推定される。
【００７３】
したがって、その座標ＸおよびＹが等式（４）および（５）を満たす点Ｐは、等式（３）による楕円曲線の点である。
【００７４】
以下で、我々は、
− ｆａ，ｂによって、Ｆｑ＊の要素を楕円曲線（３）の点にマップする関数を示し、
０は、ｆａ，ｂの入力であってはならず、そうでなければ０による割り算が生じることになる。それでもなお、楕円曲線の点の群の中間要素はｆａ，ｂによって得られることが不可能なので、我々は、ｆａ，ｂの下で、０を、点群の中間要素に対応すると定義する。
【００７５】
関数ｆａ，ｂは、３乗する、またはそうでなければ１／３乗するための関数が、考察される有限ガロア体における全単射関数である場合は、決定論的関数である。これらの条件の下でそのような関数ｆａ，ｂを適用するコストは、この有限体Ｆｑにおいて累乗することにほぼ対応することに留意されたい。
【００７６】
本発明の一実施形態において実行された計算によって符号化されたメッセージを復号するために、楕円曲線の所与の点Ｐを得ることを可能にした１つまたは複数のパラメータ値ｕを決めるための規定が行われる。
【００７７】
この目的のために、以下のセクションは、関数ｆａ，ｂとの逆関数をどのように計算するかを示す。
【００７８】
ｕ１およびｕ２はＦｑ＊の２つの要素であって、それぞれが以下の等式の解であるとする。
【００７９】
ｕ４−６ｕ２ｘ＋６ｕｙ−３ａ＝０ （１１）
ここで、ａ、ｘおよびｙは、Ｆｑの要素である。
【００８０】
ｂは以下の等式を満たすとする。
【００８１】
ｂ＝ｙ２−ｘ３−ａｘ
【００８２】
これらの条件の下で、次いで、以下の等式が満たされる。
【００８３】
【数１１】
実際、最初に、座標（ｘ１，ｙ１）を有する点Ｐ１、座標（ｘ２，ｙ２）を有する点Ｐ２、および座標（ｘ，ｙ）を有する点Ｐの３つはすべて、楕円曲線Ｅａ，ｂの点である。
【００８４】
さらに、等式（１１）によって、点ＰおよびＰ１は、以下の等式による直線上に置かれる。
【００８５】
【数１２】
次に、上記で示されたように、ｑは等式（２）を満たすので、上記の楕円曲線（３）および直線（１３）は、単一の点において互いに交差する。したがって、点ＰおよびＰ１は単一の一意の点に対応する。
【００８６】
同じ推論を点ＰおよびＰ２に適用することにより、そのことからＰおよびＰ２も単一の一意の点に対応することが同様に推定される。したがって、Ｐ、Ｐ１およびＰ２は、楕円曲線の同じ点に対応する。
【００８７】
したがって、パラメータｕが等式（１１）の解である場合かつその場合にのみ、
ｆａ，ｂ（ｕ）＝（ｘ，ｙ）
のようなパラメータｕが存在する。
【００８８】
したがって、等式（１１）を解くことは、パラメータｕを決めることを可能にし、このパラメータｕの関数として楕円曲線の点Ｐが以下の等式によって得られる。
【００８９】
ｆａ，ｂ（ｕ）＝Ｐ
【００９０】
等式（１１）は、バールカンプのアルゴリズム［Ｓｈｏｕｐ、Ｊｏｕｒｎａｌ ｏｆ Ｓｙｍｂｏｌｉｃ Ｃｏｍｐｕｔａｔｉｏｎ Ｖｏｌ ２０：３６３−３９７頁、１９９５年］などの標準的なアルゴリズムによって解かれることが可能である。したがって、この等式（１１）によって、楕円曲線の点Ｐに対応するパラメータｕを取り出すために、関数ｆａ，ｂを容易に逆にすることが可能である。
【００９１】
この特性はまた、ｆａ，ｂによって得られた点の数を制限する。関数Ｉｍ（ｆａ，ｂ）は、関数ｆａ，ｂの画像点の集合であるとする。画像集合Ｉｍ（ｆａ，ｂ）は、ｑがＦｑの基数なので、ｑより小さい基数を有する。さらに、等式（１１）は、画像点ごとに４つの前項の最大値があることを示すことを可能にする。実際、Ｆｑの基数は、多くてもＩｍ（ｆａ，ｂ）の４倍に等しい。したがって、以下の不等式が得られる。
【００９２】
ｑ／４≦＃Ｉｍ（ｆａ，ｂ）≦ｑ
【００９３】
Ｉｍ（ｆａ，ｂ）の基数にヒューリスティックな結果を与えることも可能である。等式（１１）は、有限体Ｆｑにおける４次の等式である。有限体Ｆｑにおいては、４次のいかなる任意の多項式も累乗根を有しない２／５の確率がある。したがって、楕円曲線の点の３／５が画像点Ｉｍ（ｆａ，ｂ）の集合内にあり、したがって、それらは本発明の一実施形態による暗号化計算において使用されることが可能であると考えることが可能である。
【００９４】
本発明の一実施形態では、ｑがＩの素数ｐｉ，．．．，ｐＩの積である環Ｚ／ｑＺに関する楕円曲線を使用することが可能である。中国の剰余定理、合同の解決システムを取り扱う合同算術の結果は、Ｚ／ｑＺはＺ／ｐ１Ｚｘ．．．ｘＺ／ｐＩＺと同型であると断言する。したがって、これは、Ｚ／ｐｉＺのそれぞれに関する楕円曲線を調べることに相当する。次に、各ｐｉは素数なので、Ｚ／ｐｉＺは、実際、Ｆｐｉとして示されることが可能である体である。さらに、各ｐｉは厳密には３より大きいので、Ｆｐｉに関する楕円曲線の等式は、ワイエルシュトラス型のものである。
【００９５】
したがって、等式（４）および（５）は、Ｆｐｉごとに示されるが、Ｆｐ１ｘ．．．ｘＦｐＩ＝Ｚ／ｑＺにも当てはまる。
【００９６】
さらに、Ｆｐｉごとに、
ｐｉ／４≦＃Ｉｍ（ｆａ，ｂ）≦ｐｉ
を得る。
【００９７】
したがって、これは、Ｚ／ｑＺに関して、
【００９８】
【数１３】
を得ることを証明することを可能にする。
【００９９】
本発明の一実施形態では、以下の等式を満たす特性２の楕円曲線を使用することも可能であり、
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ （１５）
ここで、ａおよびｂは、有限ガロア体Ａ＝Ｆ２ｎの要素である。
【０１００】
数ｎは、可能な攻撃を制限するために奇数の素数でよい。
【０１０１】
ここで、
２ｎｍｏｄ３＝２
を得る。
【０１０２】
３乗するための関数、および１／３乗するための関数は、ここでも、この有限ガロア体上でそれが適用される値が何であっても、一定の時間で計算可能な全単射である。
【０１０３】
我々は、以下の等式を満たすＦ２ｎの要素であるパラメータを、ｕおよびｗによって示す。
【０１０４】
ｗ＝ａ＋ｕ２＋ｕ
それぞれ以下の等式を満たす座標ＸおよびＹを有する点Ｐは、楕円曲線（１５）上にある。
【０１０５】
【数１４】
【０１０６】
したがって、暗号化計算の実行のために使用される楕円曲線が特性２のものである場合は、決定論的なやり方で、等式（１６）および（１６’）によって、パラメータｕの関数として楕円曲線の点Ｐを得ることが有利に可能である。
【０１０７】
実際、等式（１６）および（１６’）を満たす座標を有する点Ｐは、等式（１６’）による直線の考察される楕円曲線（１５）との交点が以下の等式のシステムを満たすので、等式（１５）による楕円曲線の一意の点に対応する。
【０１０８】
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ （１５）
および
Ｙ＝ｕＸ＋ｗ２（１６’）
【０１０９】
この等式システムは、以下のように書かれることが可能である。
【０１１０】
Ｘ３＋（ａ＋ｕ＋ｕ２）Ｘ２＋ｗ２Ｘ＋ｂ＋ｗ４＝０ （１７）
および
Ｙ＝ｕＸ＋ｗ２ （１６’）
【０１１１】
後者の等式は、以下のようにさらに簡約されることが可能である。
【０１１２】
Ｘ３＋ｗＸ２＋ｗ２Ｘ＋ｂ＋ｗ４＝０ （１８）
および
Ｙ＝ｕＸ＋ｗ２ （１６’）
したがって、この等式のシステムは、最終的に、
（Ｘ＋ｗ）３＋ｂ＋ｗ３＋ｗ４＝０ （１９）
および
Ｙ＝ｕＸ＋ｗ２ （１６’）
と書かれることが可能である。
【０１１３】
等式（１９）は、等式（１６）に対応し、そのことから、Ｐは考察される楕円曲線の点であることが推定される。
【０１１４】
したがって、その座標ＸおよびＹが等式（１６）および（１６’）を満たす点Ｐは、等式（１５）による楕円曲線の点である。
【０１１５】
ワイエルシュトラス型の楕円曲線の場合のように、ここでも、ｆａの画像Ｉｍ（ｆａ）に含まれる点の数を制限することが可能である。この集合Ｉｍ（ｆａ）は、これは開始集合Ｆ２ｎの要素の数なので、多くても２ｎの要素を有する。
【０１１６】
等式（１６’）は、
０＝Ｙ＋ａ＋ｕＸ＋ｕ２＋ｕ４ （１７）
と書かれることが可能である。
【０１１７】
上記等式を解くｕの値に関して、
ｆａ（ｕ）＝（ｘ，ｙ）
を得る。
【０１１８】
等式（１７）は４次のものである。したがって、パラメータｕの少なくとも４つのそれぞれ異なる値が、この等式を解く。したがって、ｆａの少なくとも２ｎ／４＝２ｎ−２の画像点がある。したがって、画像点Ｉｍ（ｆａ）の集合には、少なくとも２ｎ―１の要素がある。
【０１１９】
本発明の特性によって、決定論的関数ｆが利用可能にされ、考察される楕円曲線の型に応じてｆａ，ｂまたはｆａとして示され、その画像集合は楕円曲線上の点の集合であり、これらの点の数は、ワイエルシュトラス型の楕円曲線の場合は最小でも数ｑ（考察される有限体の基数）の１／４に等しいか、または特性２の楕円曲線の場合は最小でも２ｎ−２に等しいので、高い。この決定論的関数ｆは、それが適用される考察される有限ガロア体における３乗（および１／３乗）の関数の全単射特性に基づく。
【０１２０】
以下では、本発明の一実施形態によるこのような決定論的関数は、楕円曲線に関するハッシュ関数の実行のために使用される。
【０１２１】
本発明の一実施形態による関数ｆａ，ｂをハッシュ関数ｈから生じるビットの列に適用することにより、以下のような関数が得られる。
【０１２２】
ｆａ，ｂ（ｈ） （１８）
【０１２３】
楕円曲線に関するこの関数（１８）は、以下の特性を有利に示す。
【０１２４】
− ハッシュ関数ｈが一方向である場合は、一方向であり、
− 衝突耐性がある。
【０１２５】
そのような関数は、多数の暗号化計算に適用される。
【０１２６】
本発明の一実施形態では、楕円曲線に適用されたランダム関数から微分可能でない楕円曲線に関するハッシュ関数を得るために、本発明の一実施形態による関数ｆａ，ｂを２つのハッシュ関数と組み合わせるための規定が行われることが可能である。
【０１２７】
２つのランダムハッシュ関数ｈおよびｈ’を考察する。ハッシュ関数ｈは、Ａへの集合｛０，１｝＊に適用される。関数ｈ’は、有限体ＦＮへの集合｛０，１｝＊に適用され、ここで、Ｎは使用される曲線の点の群の位数である。
【０１２８】
これらの条件の下で、以下の関数は、楕円曲線に関するランダム関数から微分可能でない楕円曲線に関するハッシュ関数である。
【０１２９】
【数１５】
本発明の一実施形態による関数ｆａ，ｂは、楕円曲線上の点を決めるために使用される。Ｇ、使用される点の群の生成点、すなわち、本発明の実施形態の状況におけるｆａ，ｂの画像点は、決められた点の一様分布を保証するために使用される。
【０１３０】
本発明は、楕円曲線を使用するいかなるタイプの暗号化計算においても有利に実施されることが可能である。本発明は、ＰＡＣＥ（「パスワード認証接続確立」を表す）などのパスワードベースの認証プロトコルの中で特に有利であり得る。この場合、本発明は、関数（１８）の使用によって演算の改善を可能にし、一方、暗号化計算の実行時間に関するいかなる攻撃をも可能にしない。
【０１３１】
本発明はまた、電子パスポートなどの電子識別文書をチェックするために使用されるものなど、プライバシに関するプロトコルの関連で有利に適用されることが可能である。
【０１３２】
実際、そのようなプロトコルに従うことにより、http://www.larc.usp.br/~pbarreto/talesl.htmlにおいて入手可能な文書「Ｗｈｙ ｐｕｂｌｉｃ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｐａｒａｍｅｔｅｒｓ ａｒｅ ｐｕｂｌｉｃ」に記載されているように、使用される楕円曲線のパラメータを決めることが可能である。
【０１３３】
次に、これらのパラメータは、これらの電子文書を有する人の国籍を決めることを可能にする。
【０１３４】
ランダム関数で微分不可能なやり方で適用可能であり得る関数（１９）を使用することにより、楕円曲線の公開パラメータに関係のない点の表示を得ることが可能である。
【０１３５】
識別ベースの暗号化方式の関連においても、本発明は有利に適用されることが可能である。ボネ−フランクリン暗号化方式（Ｄａｎ Ｂｏｎｅｈ ａｎｄ Ｍａｔｔｈｅｗ Ｋ．Ｆｒａｎｋｌｉｎ，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｒｙｐｔｏ ２００１ ｃｏｎｆｅｒｅｎｃｅ）は、そのような構成を使用する例である。実際、安全な条件の下で使用されることが可能であるために、この方式は、ランダム関数がそれに関して存在する楕円曲線を必要とする。本発明は、通常のランダム関数に基づいて楕円曲線に関するランダム関数を返す構成を提供する。それにもかかわらず、ボネ−フランクリンによる暗号化に適した楕円曲線は、特定の関数、すなわち点結合関数を必要とする。結合関数は、２つの点を入力とみなし、有限体に関する値を返す関数
【０１３６】
【数１６】
である。この結合は、注目すべき数学的特性を有するので興味深い。以下の等式が満たされる。
【０１３７】
【数１７】
ここで、ｇはマップされた有限体の生成元であり、
ここで、ｃおよびｄは、Ｇを底とするｃＧおよびｄＧの離散対数であり、
ここで、Ｇは、使用される点の群の生成元である。
【０１３８】
ボネ−フランクリン方式の著者たちは、彼らの方式のために単一のタイプの楕円曲線しか提案していない。本発明は、彼らの暗号化方式が実施されることが可能な楕円曲線の数を増やすことを可能にする。実際、本発明の規定によって、結合を効率よく計算でき等式（２）が満たされるすべての曲線上で、この暗号化方式が実施されることが可能である。
【０１３９】
本発明の一実施形態では、点の座標の圧縮を行うことが有利に可能である。実際、本発明の規定は、パラメータｕによって点Ｐの座標ＸおよびＹを表すことを可能にする。したがって、その場合ｕは半分の情報で点Ｐ（Ｘ，Ｙ）を表すので、圧縮を行うためにパラメータｕを使用することが可能である。
【技術分野】
【０００１】
本発明は、楕円曲線の点の使用に基づくメッセージの暗号化に関し、より具体的には、決定論的なやり方でのそのような暗号化に関する。
【背景技術】
【０００２】
メッセージに暗号化計算を適用するためには、通常、数学的構造の中に任意の値を挿入するためのアルゴリズムが実行される。この目的のために、楕円曲線は、そのような暗号化計算を容易にし、他の暗号化計算の実行に関してメモリ空間を節減することを可能にする数学的構造である。
【０００３】
しかし、楕円曲線を使用した、任意の値を挿入するための効率のよいアルゴリズムは、確率的である。したがって、そのようなアルゴリズムの実行時間は、一定でなく、符号化されるべきメッセージに依存する。したがって、攻撃者は、適用されたアルゴリズムの様々な実行時間を決めれば、符号化されたメッセージについての情報を得ることができる。
【０００４】
確率的挿入アルゴリズムによって使用された時間を隠すために、どのようなメッセージが処理されても、その適用が常に同一の長さの時間帯に及ぶように、このアルゴリズムに無用なステップを付加するための規定が行われてよい。
【０００５】
しかし、そのような処理は扱いにくく、多くの時間を消費する。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、この状況を改善することである。
【課題を解決するための手段】
【０００７】
本発明の第１の態様は、以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ パラメータ（１１）を決めるステップと、
／ｂ／ 前記パラメータに関数（１２）を適用することにより、点Ｐ（１３）の座標ＸおよびＹを得るステップであって、
Ａのオイラー関数φが、等式
φ（Ａ） ｍｏｄ ３＝１
を満たし、
上記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表された可逆的決定論的関数であり、Ｉが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記点Ｐを使用するステップと
を有する方法を提案する。
【０００８】
「少なくとも所与の個数の点を得る」という表現は、考察される関数が出力において少なくともこの所与の個数の異なる点を提供するように適応されるということを意味するものとする。
【０００９】
これらの規定によって、電子構成部品において、潜在的攻撃者に情報を提供することなく、高いレベルの実行効率を維持しながら、楕円曲線の点に基づく暗号化計算を実行することが可能である。実際、上記関数は、有理分数である楕円曲線上の点を得ることを可能にし、したがって、確率的関数ではく、決定論的関数であり、それを計算するのにかかる時間は、入力パラメータが何であっても、一定である。これらの条件の下で、楕円曲線上の点を得ることは効率がよく、計算時間は、従来技術とは対照的に、もはや符号化されるべきメッセージに依存しない。
【００１０】
環Ａは、ＲＳＡ（「Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ」を表す）環でよい。この場合、この環は、Ｚ／ｑＺと書かれることが可能であり、ｑは２つの素数の積に等しく、それらのための積φ（Ａ）は計算するのが難しい。
【００１１】
環Ａに関するオイラー関数φは、この環Ａにおける可逆的要素の数を提供する関数であることが留意される。Ａが有限体Ｆｑである場合は、
φ（Ａ）＝ｑ−１
を得る。
【００１２】
ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいかまたは等しい整数である、モジュラ整数Ｚ／ｑＺの環を考察することにより、
φ（Ａ）＝ｌｃｍ（ｐ１−１，ｐ２−１，．．．，ｐＩ−１）
を得る。
【００１３】
ここで、ｌｃｍは、最小公倍数を表し、ｐｉは、Ｉの素数である。
【００１４】
本発明の一実施形態による決定論的関数が有理分数の形で表されるとすれば、それらの適用は、それが適用されるメッセージまたはデータが何であっても、常に同じ時間を必要とする。
【００１５】
実際、集合Ａにおいては、３乗および１／３乗するための関数は、全単射である。したがって、それらの関数は有理分数の形で書かれ、したがって、決定論的関数ｆは、有理分数の形で書かれることが可能である。集合Ａにおいては、１／３乗の計算は、（２φ（ａ）＋１）／３乗の計算と同じである。後者は、φ（Ａ）ｍｏｄ３＝１なので、整数である。以下の等式がＡにおいて満たされる。
【００１６】
【数１】
この等式から、以下の等式が推定される。
【００１７】
【数２】
【００１８】
したがって、
【００１９】
【数３】
と書くことが可能である。
【００２０】
次に、楕円曲線の点Ｐを得ることを可能にする関数ｆは、この１／３乗することを有する。
【００２１】
したがって、Ａの要素が何であっても、１／３乗するための関数が一定の時間で計算されるということによって、確率を扱う必要なしに楕円曲線の点を得ることが可能である。したがって、暗号化計算のための実行時間が、従来技術において行われるような確率的なやり方でのそのような計算の実行の場合のあるようなメッセージに依存することは、この計算ではない。
【００２２】
さらに、Ａが有限体Ｆｑに対応する状況において、決定論的関数ｆは、楕円曲線の少なくともｑ／４個の点Ｐを提供することができる。ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいかまたは等しい整数である、モジュラ整数Ｚ／ｑＺの環にＡが対応する状況では、決定論的関数ｆは、楕円曲線の少なくともｑ／４Ｉ個の点Ｐを提供することができる。
【００２３】
楕円曲線上の、決定論的なやり方でこのようにして得られたそのような点の個数は、潜在的な攻撃に対する高いレベルのセキュリティを有する多くの暗号化アプリケーションを可能にする。
【００２４】
一実施形態では、使用される楕円曲線は、ワイエルシュトラス型の曲線であるか、そうでなければ特性ｐの曲線と呼ばれる。ここでは、ｑは２ｎとは異なると考えられる。
【００２５】
等式（１）は、
Ｙ２＝Ｘ３＋ａＸ＋ｂ
と書かれてよく、ａ＝ａ２、およびｂ＝ａ６である。
【００２６】
決定論的関数は、以下のそれぞれの等式によって楕円曲線の点の座標を提供する。
【００２７】
【数４】
ここで、ｕは、ステップ／ａ／において決められたパラメータであり、ｖ＝（３ａ−ｕ４）／（６ｕ）である。
【００２８】
他の実施形態では、本発明は、特性２の楕円曲線に適用される。
【００２９】
この場合、ｑは、等式
ｑ＝２ｎ
を満たし、
ここで、ｎは、奇数の整数であり、
等式（１）は、
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ
と書かれてよく、ａ＝ａ２、およびｂ＝ａ６であり、
決定論的関数は、以下のそれぞれの等式による楕円曲線の点の座標を提供し、
【００３０】
【数５】
ここで、ｕは、ステップ／ａ／において決められたパラメータであり、ここで、ｗ＝ａ＋ｕ２＋ｕである。
【００３１】
有利な特定の場合には、ｎは、素数の奇数の整数である。実際、そのようなｎは、いくつかの攻撃を制限することを可能にする。
【００３２】
この状況では、決定論的関数は、楕円曲線の少なくとも２ｎ−２個の点Ｐを有利に提供することができる。
【００３３】
ｂが１に等しく、ａがＦ２に属する特性２の楕円曲線の特定の場合に、この関数をコブリッツ型の楕円曲線に適用することは、有利に可能である。実際、コブリッツ楕円曲線を使用することにより、暗号化計算をより速く実行することが可能である。
【００３４】
この決定論的関数をハッシュ関数の結果に適用するための規定が行われてよい。したがって、ステップ／ａ／において、パラメータｕは、ハッシュ関数ｈを適用することにより得られることが可能である。
【００３５】
一実施形態では、ハッシュ関数は一方向関数である。この特性は保存され、決定論的関数とハッシュ関数を組み合わせることから生じる関数は、この一方向であるという特性を示す。
【００３６】
ここで、次いで、ハッシュ関数のような一方向である楕円曲線に関する関数が最終的に得られる。この関数は、さらに衝突耐性がある。
【００３７】
この決定論的関数が、楕円曲線に適用されるランダム関数から微分可能でないという特性（または「微分不可能」であるという特性）を示すようなやり方で、この決定論的関数を適用するための規定が行われてもよい。この特性は、特に、ハッシュ関数がランダムであると推定されるモデルにおいて安全であると分かっている暗号化方式においてこの関数が適用されたときに、利点を示す。実際、決定論的関数はランダム関数から微分可能でないという特性を示すので、この同じタイプの暗号化方式においてこの関数を適用することによって安全な暗号化方式が得られる。
【００３８】
ステップ／ａ／において、パラメータｕは、第１のハッシュ関数ｈおよび第２のハッシュ関数ｈ’を適用することにより得られることが可能である。楕円曲線の点の群の生成元は、Ｇとして示される。暗号化計算は、以下の関数の適用を有することができる。
【００３９】
【数６】
ここで、ｆは決定論的関数であり、ここで、Ｇは楕円曲線の点の群の生成元である。
【００４０】
この楕円曲線の点の群は、本発明の一実施形態による暗号化計算によって使用される点に対応することができる。
【００４１】
本発明の第２の態様は、本発明の第１の態様による暗号化計算を実行する方法を実施する少なくとも１つのパスワードによる認証の方法であって、ステップ／ａ／においてパラメータがパスワードの関数として決められ、前記パスワードがパラメータに含まれ、認証ステップが点Ｐに基づいて実行される、方法を提案する。
【００４２】
本発明の第３の態様は、データを暗号化する方法であって、前記暗号化は結合演算を許容する楕円曲線に関するボネ−フランクリン識別に基づき、前記識別は、エンティティを識別する数値であり、
前記方法が、
／ａ／ 請求項６に記載の暗号化計算を実行する方法を前記識別に適用することにより点を得るステップと、
／ｂ／ 前記点、ランダムパラメータおよびデータを組み合わせることにより、暗号化されたデータを得るステップと
を有する、方法を提供する。
【００４３】
ここで、用語「組み合わせる」は、結合演算、ハッシュ演算、「排他的論理和」演算およびスカラ乗法の組合せを適用するということを意味するものとする。
【００４４】
本発明の第４の態様は、以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ 楕円曲線上の座標ＸおよびＹを有する点Ｐを決めるステップと、
／ｂ／ 点Ｐに関数を適用することによりパラメータを得るステップであって、
Ａのオイラー関数φが、等式
φ（Ａ）ｍｏｄ３＝１
を満たし、
前記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表された決定論的関数の逆関数であり、Ｉが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記パラメータを使用するステップと
を含む方法を提案する。
【００４５】
ここで、本発明の第１の態様において述べられたような決定論的関数は、可逆的関数であることに留意されたい。したがって、この決定論的関数は、逆方向に有利に使用されることが可能であり、その逆関数が本発明のこの第１の態様において利用される。実際、第１の態様において述べられた関数の逆関数を介して楕円曲線の点に対応するパラメータを得るために楕円曲線の点から開始することは、暗号化分野において、特にデータ圧縮アプリケーションでは、有用であり得る。
【００４６】
したがって、本発明の第５の態様は、データ圧縮の方法であって、それぞれ、以下の等式を満たす楕円曲線の点Ｐの座標に対応するデータＸとＹの対に対応してデータが圧縮され、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいかまたは等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
本発明の第４の態様による暗号化計算を実行する方法のステップ／ａ／から／ｃ／がデータの前記対のそれぞれに適用され、
データの前記対がそれぞれステップ／ｃ／において得られたパラメータによって表される、
データ圧縮の方法を提案する。
【００４７】
本発明の第６の態様は、本発明の第１の態様による暗号化計算を実行する方法の実施に適応された手段を有する電子デバイスを提案する。
【００４８】
本発明の第７の態様は、本発明の第４の態様による暗号化計算を実行する方法の実施に適応された手段を有する電子デバイスを提案する。
【００４９】
本発明の第８の態様は、本発明の第６または第７の態様による電子デバイスを有するチップカードを提案する。
【００５０】
本発明の他の態様、目的、利点は、本発明の諸実施形態の１つの説明を読むと明らかになるであろう。
【００５１】
本発明はまた、本発明の一実施形態による暗号化計算の主なステップを図示する図１の助けを借りればよりよく理解されるであろう。
【図面の簡単な説明】
【００５２】
【図１】本発明の一実施形態による暗号化計算の主なステップを示す図である。
【発明を実施するための形態】
【００５３】
Ａに関するいかなる楕円曲線も、以下の等式を満たす。
【００５４】
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、Ａの要素であり、
ここで、ＸおよびＹは、集合Ａの要素である。
【００５５】
φがＡに適用されるオイラー関数である以下の等式が満たされる場合は、
φ（Ａ）＝１ｍｏｄ３ （２）
３乗するための関数および１／３乗するための関数は、計算される値が何であっても、一定の時間で効率よく計算されることが可能である。この特性は、パラメータの関数として楕円曲線の点Ｐを決定論的に得ることを可能にし、計算時間は、この決定論的関数ｆが適用されるパラメータに関係がない。
【００５６】
続いて、この関数ｆはまた、考察される楕円曲線の等式のタイプに応じて、ｆａ，ｂまたはそうでなければｆａとして示される。
【００５７】
図１は、ステップ１１において、パラメータｕ、考察される有限体Ｆｑの要素の決定を図示する。次に、ステップ１２において、最終的に、決定論的なやり方で楕円曲線の点Ｐを得るために、決定論的関数ｆがこのパラメータに適用される。すべてのこれらのステップは、等式（２）を満たす環Ａにおいて実行される。
【００５８】
以下のセクションは、楕円曲線の等式の特定の場合におけるこれらの特性の適用を提示する。本発明の一実施形態は、ワイエルシュトラス型の楕円曲線、すなわちｐ＞３である特性ｐを有する楕円曲線、および特性２を有する楕円曲線に適用されることが可能である。
【００５９】
以下のセクションでは、考察される楕円曲線は、体Ｆｑに関するワイエルシュトラス型のものである。
【００６０】
この状況では、考察される有限ガロア体の基数ｑは、ｐｎに等しく、ここで、ｐは、値２および３とは異なる素数である。等式（１）は、ワイエルシュトラスの等式、
Ｙ２＝Ｘ３＋ａＸ＋ｂ （３）
によって書かれることが可能であり、
ここで、ａおよびｂは、Ｅａ，ｂとして示される楕円曲線のパラメータである。
【００６１】
ｑが等式（２）を満たす要素の数ｑを有する有限体Ａ＝Ｆｑにおいては、３乗するための関数ｆおよび１／３乗するための関数は、それらが計算される値が何であっても、一定の時間で効率よく計算されることが可能である全単射である。
【００６２】
これらの条件の下で、楕円曲線の点Ｐの座標ＸおよびＹは、以下のそれぞれの等式を満たす。
【００６３】
【数７】
ここで、
ｖ＝（３ａ−ｕ４）／（６ｕ） （６）
であり、
ここで、ｕは、本発明の一実施形態によるパラメータであり、ｕは、有限体Ｆｑ＊に属する。
【００６４】
有限体Ｆｑにおいて、（（２φ（Ａ）＋１）／３）乗することは、１／３乗することに対応することが留意される。
【００６５】
したがって、暗号化計算の実行のために使用される楕円曲線が、ワイエルシュトラス型のものである場合、パラメータｕに関して一定の計算時間で決定論的なやり方で、等式（４）および（５）によって、パラメータｕの関数として楕円曲線の点Ｐを得ることが有利に可能である。
【００６６】
実際、等式（４）および（５）を満たす座標を有する点Ｐは、等式（５）による直線の考察される楕円曲線（３）との交点が以下の等式のシステムを満たすので、等式（３）による楕円曲線の一意の点に対応する。
【００６７】
Ｙ２＝Ｘ３＋ａＸ＋ｂ （７）
および
Ｙ＝ｕＸ＋ｖ （５）
【００６８】
この等式のシステムは、以下のように書かれることが可能である。
【００６９】
【数８】
【００７０】
前者の等式は、以下のようにさらに簡約されることが可能である。
【００７１】
【数９】
したがって、この等式のシステムは、最終的に、
【００７２】
【数１０】
と書かれることが可能である。
等式（１０）は等式（４）に対応し、そのことから、Ｐは考察される楕円曲線の点であることが推定される。
【００７３】
したがって、その座標ＸおよびＹが等式（４）および（５）を満たす点Ｐは、等式（３）による楕円曲線の点である。
【００７４】
以下で、我々は、
− ｆａ，ｂによって、Ｆｑ＊の要素を楕円曲線（３）の点にマップする関数を示し、
０は、ｆａ，ｂの入力であってはならず、そうでなければ０による割り算が生じることになる。それでもなお、楕円曲線の点の群の中間要素はｆａ，ｂによって得られることが不可能なので、我々は、ｆａ，ｂの下で、０を、点群の中間要素に対応すると定義する。
【００７５】
関数ｆａ，ｂは、３乗する、またはそうでなければ１／３乗するための関数が、考察される有限ガロア体における全単射関数である場合は、決定論的関数である。これらの条件の下でそのような関数ｆａ，ｂを適用するコストは、この有限体Ｆｑにおいて累乗することにほぼ対応することに留意されたい。
【００７６】
本発明の一実施形態において実行された計算によって符号化されたメッセージを復号するために、楕円曲線の所与の点Ｐを得ることを可能にした１つまたは複数のパラメータ値ｕを決めるための規定が行われる。
【００７７】
この目的のために、以下のセクションは、関数ｆａ，ｂとの逆関数をどのように計算するかを示す。
【００７８】
ｕ１およびｕ２はＦｑ＊の２つの要素であって、それぞれが以下の等式の解であるとする。
【００７９】
ｕ４−６ｕ２ｘ＋６ｕｙ−３ａ＝０ （１１）
ここで、ａ、ｘおよびｙは、Ｆｑの要素である。
【００８０】
ｂは以下の等式を満たすとする。
【００８１】
ｂ＝ｙ２−ｘ３−ａｘ
【００８２】
これらの条件の下で、次いで、以下の等式が満たされる。
【００８３】
【数１１】
実際、最初に、座標（ｘ１，ｙ１）を有する点Ｐ１、座標（ｘ２，ｙ２）を有する点Ｐ２、および座標（ｘ，ｙ）を有する点Ｐの３つはすべて、楕円曲線Ｅａ，ｂの点である。
【００８４】
さらに、等式（１１）によって、点ＰおよびＰ１は、以下の等式による直線上に置かれる。
【００８５】
【数１２】
次に、上記で示されたように、ｑは等式（２）を満たすので、上記の楕円曲線（３）および直線（１３）は、単一の点において互いに交差する。したがって、点ＰおよびＰ１は単一の一意の点に対応する。
【００８６】
同じ推論を点ＰおよびＰ２に適用することにより、そのことからＰおよびＰ２も単一の一意の点に対応することが同様に推定される。したがって、Ｐ、Ｐ１およびＰ２は、楕円曲線の同じ点に対応する。
【００８７】
したがって、パラメータｕが等式（１１）の解である場合かつその場合にのみ、
ｆａ，ｂ（ｕ）＝（ｘ，ｙ）
のようなパラメータｕが存在する。
【００８８】
したがって、等式（１１）を解くことは、パラメータｕを決めることを可能にし、このパラメータｕの関数として楕円曲線の点Ｐが以下の等式によって得られる。
【００８９】
ｆａ，ｂ（ｕ）＝Ｐ
【００９０】
等式（１１）は、バールカンプのアルゴリズム［Ｓｈｏｕｐ、Ｊｏｕｒｎａｌ ｏｆ Ｓｙｍｂｏｌｉｃ Ｃｏｍｐｕｔａｔｉｏｎ Ｖｏｌ ２０：３６３−３９７頁、１９９５年］などの標準的なアルゴリズムによって解かれることが可能である。したがって、この等式（１１）によって、楕円曲線の点Ｐに対応するパラメータｕを取り出すために、関数ｆａ，ｂを容易に逆にすることが可能である。
【００９１】
この特性はまた、ｆａ，ｂによって得られた点の数を制限する。関数Ｉｍ（ｆａ，ｂ）は、関数ｆａ，ｂの画像点の集合であるとする。画像集合Ｉｍ（ｆａ，ｂ）は、ｑがＦｑの基数なので、ｑより小さい基数を有する。さらに、等式（１１）は、画像点ごとに４つの前項の最大値があることを示すことを可能にする。実際、Ｆｑの基数は、多くてもＩｍ（ｆａ，ｂ）の４倍に等しい。したがって、以下の不等式が得られる。
【００９２】
ｑ／４≦＃Ｉｍ（ｆａ，ｂ）≦ｑ
【００９３】
Ｉｍ（ｆａ，ｂ）の基数にヒューリスティックな結果を与えることも可能である。等式（１１）は、有限体Ｆｑにおける４次の等式である。有限体Ｆｑにおいては、４次のいかなる任意の多項式も累乗根を有しない２／５の確率がある。したがって、楕円曲線の点の３／５が画像点Ｉｍ（ｆａ，ｂ）の集合内にあり、したがって、それらは本発明の一実施形態による暗号化計算において使用されることが可能であると考えることが可能である。
【００９４】
本発明の一実施形態では、ｑがＩの素数ｐｉ，．．．，ｐＩの積である環Ｚ／ｑＺに関する楕円曲線を使用することが可能である。中国の剰余定理、合同の解決システムを取り扱う合同算術の結果は、Ｚ／ｑＺはＺ／ｐ１Ｚｘ．．．ｘＺ／ｐＩＺと同型であると断言する。したがって、これは、Ｚ／ｐｉＺのそれぞれに関する楕円曲線を調べることに相当する。次に、各ｐｉは素数なので、Ｚ／ｐｉＺは、実際、Ｆｐｉとして示されることが可能である体である。さらに、各ｐｉは厳密には３より大きいので、Ｆｐｉに関する楕円曲線の等式は、ワイエルシュトラス型のものである。
【００９５】
したがって、等式（４）および（５）は、Ｆｐｉごとに示されるが、Ｆｐ１ｘ．．．ｘＦｐＩ＝Ｚ／ｑＺにも当てはまる。
【００９６】
さらに、Ｆｐｉごとに、
ｐｉ／４≦＃Ｉｍ（ｆａ，ｂ）≦ｐｉ
を得る。
【００９７】
したがって、これは、Ｚ／ｑＺに関して、
【００９８】
【数１３】
を得ることを証明することを可能にする。
【００９９】
本発明の一実施形態では、以下の等式を満たす特性２の楕円曲線を使用することも可能であり、
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ （１５）
ここで、ａおよびｂは、有限ガロア体Ａ＝Ｆ２ｎの要素である。
【０１００】
数ｎは、可能な攻撃を制限するために奇数の素数でよい。
【０１０１】
ここで、
２ｎｍｏｄ３＝２
を得る。
【０１０２】
３乗するための関数、および１／３乗するための関数は、ここでも、この有限ガロア体上でそれが適用される値が何であっても、一定の時間で計算可能な全単射である。
【０１０３】
我々は、以下の等式を満たすＦ２ｎの要素であるパラメータを、ｕおよびｗによって示す。
【０１０４】
ｗ＝ａ＋ｕ２＋ｕ
それぞれ以下の等式を満たす座標ＸおよびＹを有する点Ｐは、楕円曲線（１５）上にある。
【０１０５】
【数１４】
【０１０６】
したがって、暗号化計算の実行のために使用される楕円曲線が特性２のものである場合は、決定論的なやり方で、等式（１６）および（１６’）によって、パラメータｕの関数として楕円曲線の点Ｐを得ることが有利に可能である。
【０１０７】
実際、等式（１６）および（１６’）を満たす座標を有する点Ｐは、等式（１６’）による直線の考察される楕円曲線（１５）との交点が以下の等式のシステムを満たすので、等式（１５）による楕円曲線の一意の点に対応する。
【０１０８】
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ （１５）
および
Ｙ＝ｕＸ＋ｗ２（１６’）
【０１０９】
この等式システムは、以下のように書かれることが可能である。
【０１１０】
Ｘ３＋（ａ＋ｕ＋ｕ２）Ｘ２＋ｗ２Ｘ＋ｂ＋ｗ４＝０ （１７）
および
Ｙ＝ｕＸ＋ｗ２ （１６’）
【０１１１】
後者の等式は、以下のようにさらに簡約されることが可能である。
【０１１２】
Ｘ３＋ｗＸ２＋ｗ２Ｘ＋ｂ＋ｗ４＝０ （１８）
および
Ｙ＝ｕＸ＋ｗ２ （１６’）
したがって、この等式のシステムは、最終的に、
（Ｘ＋ｗ）３＋ｂ＋ｗ３＋ｗ４＝０ （１９）
および
Ｙ＝ｕＸ＋ｗ２ （１６’）
と書かれることが可能である。
【０１１３】
等式（１９）は、等式（１６）に対応し、そのことから、Ｐは考察される楕円曲線の点であることが推定される。
【０１１４】
したがって、その座標ＸおよびＹが等式（１６）および（１６’）を満たす点Ｐは、等式（１５）による楕円曲線の点である。
【０１１５】
ワイエルシュトラス型の楕円曲線の場合のように、ここでも、ｆａの画像Ｉｍ（ｆａ）に含まれる点の数を制限することが可能である。この集合Ｉｍ（ｆａ）は、これは開始集合Ｆ２ｎの要素の数なので、多くても２ｎの要素を有する。
【０１１６】
等式（１６’）は、
０＝Ｙ＋ａ＋ｕＸ＋ｕ２＋ｕ４ （１７）
と書かれることが可能である。
【０１１７】
上記等式を解くｕの値に関して、
ｆａ（ｕ）＝（ｘ，ｙ）
を得る。
【０１１８】
等式（１７）は４次のものである。したがって、パラメータｕの少なくとも４つのそれぞれ異なる値が、この等式を解く。したがって、ｆａの少なくとも２ｎ／４＝２ｎ−２の画像点がある。したがって、画像点Ｉｍ（ｆａ）の集合には、少なくとも２ｎ―１の要素がある。
【０１１９】
本発明の特性によって、決定論的関数ｆが利用可能にされ、考察される楕円曲線の型に応じてｆａ，ｂまたはｆａとして示され、その画像集合は楕円曲線上の点の集合であり、これらの点の数は、ワイエルシュトラス型の楕円曲線の場合は最小でも数ｑ（考察される有限体の基数）の１／４に等しいか、または特性２の楕円曲線の場合は最小でも２ｎ−２に等しいので、高い。この決定論的関数ｆは、それが適用される考察される有限ガロア体における３乗（および１／３乗）の関数の全単射特性に基づく。
【０１２０】
以下では、本発明の一実施形態によるこのような決定論的関数は、楕円曲線に関するハッシュ関数の実行のために使用される。
【０１２１】
本発明の一実施形態による関数ｆａ，ｂをハッシュ関数ｈから生じるビットの列に適用することにより、以下のような関数が得られる。
【０１２２】
ｆａ，ｂ（ｈ） （１８）
【０１２３】
楕円曲線に関するこの関数（１８）は、以下の特性を有利に示す。
【０１２４】
− ハッシュ関数ｈが一方向である場合は、一方向であり、
− 衝突耐性がある。
【０１２５】
そのような関数は、多数の暗号化計算に適用される。
【０１２６】
本発明の一実施形態では、楕円曲線に適用されたランダム関数から微分可能でない楕円曲線に関するハッシュ関数を得るために、本発明の一実施形態による関数ｆａ，ｂを２つのハッシュ関数と組み合わせるための規定が行われることが可能である。
【０１２７】
２つのランダムハッシュ関数ｈおよびｈ’を考察する。ハッシュ関数ｈは、Ａへの集合｛０，１｝＊に適用される。関数ｈ’は、有限体ＦＮへの集合｛０，１｝＊に適用され、ここで、Ｎは使用される曲線の点の群の位数である。
【０１２８】
これらの条件の下で、以下の関数は、楕円曲線に関するランダム関数から微分可能でない楕円曲線に関するハッシュ関数である。
【０１２９】
【数１５】
本発明の一実施形態による関数ｆａ，ｂは、楕円曲線上の点を決めるために使用される。Ｇ、使用される点の群の生成点、すなわち、本発明の実施形態の状況におけるｆａ，ｂの画像点は、決められた点の一様分布を保証するために使用される。
【０１３０】
本発明は、楕円曲線を使用するいかなるタイプの暗号化計算においても有利に実施されることが可能である。本発明は、ＰＡＣＥ（「パスワード認証接続確立」を表す）などのパスワードベースの認証プロトコルの中で特に有利であり得る。この場合、本発明は、関数（１８）の使用によって演算の改善を可能にし、一方、暗号化計算の実行時間に関するいかなる攻撃をも可能にしない。
【０１３１】
本発明はまた、電子パスポートなどの電子識別文書をチェックするために使用されるものなど、プライバシに関するプロトコルの関連で有利に適用されることが可能である。
【０１３２】
実際、そのようなプロトコルに従うことにより、http://www.larc.usp.br/~pbarreto/talesl.htmlにおいて入手可能な文書「Ｗｈｙ ｐｕｂｌｉｃ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｐａｒａｍｅｔｅｒｓ ａｒｅ ｐｕｂｌｉｃ」に記載されているように、使用される楕円曲線のパラメータを決めることが可能である。
【０１３３】
次に、これらのパラメータは、これらの電子文書を有する人の国籍を決めることを可能にする。
【０１３４】
ランダム関数で微分不可能なやり方で適用可能であり得る関数（１９）を使用することにより、楕円曲線の公開パラメータに関係のない点の表示を得ることが可能である。
【０１３５】
識別ベースの暗号化方式の関連においても、本発明は有利に適用されることが可能である。ボネ−フランクリン暗号化方式（Ｄａｎ Ｂｏｎｅｈ ａｎｄ Ｍａｔｔｈｅｗ Ｋ．Ｆｒａｎｋｌｉｎ，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｒｙｐｔｏ ２００１ ｃｏｎｆｅｒｅｎｃｅ）は、そのような構成を使用する例である。実際、安全な条件の下で使用されることが可能であるために、この方式は、ランダム関数がそれに関して存在する楕円曲線を必要とする。本発明は、通常のランダム関数に基づいて楕円曲線に関するランダム関数を返す構成を提供する。それにもかかわらず、ボネ−フランクリンによる暗号化に適した楕円曲線は、特定の関数、すなわち点結合関数を必要とする。結合関数は、２つの点を入力とみなし、有限体に関する値を返す関数
【０１３６】
【数１６】
である。この結合は、注目すべき数学的特性を有するので興味深い。以下の等式が満たされる。
【０１３７】
【数１７】
ここで、ｇはマップされた有限体の生成元であり、
ここで、ｃおよびｄは、Ｇを底とするｃＧおよびｄＧの離散対数であり、
ここで、Ｇは、使用される点の群の生成元である。
【０１３８】
ボネ−フランクリン方式の著者たちは、彼らの方式のために単一のタイプの楕円曲線しか提案していない。本発明は、彼らの暗号化方式が実施されることが可能な楕円曲線の数を増やすことを可能にする。実際、本発明の規定によって、結合を効率よく計算でき等式（２）が満たされるすべての曲線上で、この暗号化方式が実施されることが可能である。
【０１３９】
本発明の一実施形態では、点の座標の圧縮を行うことが有利に可能である。実際、本発明の規定は、パラメータｕによって点Ｐの座標ＸおよびＹを表すことを可能にする。したがって、その場合ｕは半分の情報で点Ｐ（Ｘ，Ｙ）を表すので、圧縮を行うためにパラメータｕを使用することが可能である。
【特許請求の範囲】
【請求項１】
以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ パラメータ（１１）を決めるステップと、
／ｂ／ 前記パラメータに関数（１２）を適用することにより点Ｐ（１３）の座標ＸおよびＹを得るステップであって、
Ａのオイラー関数φが、等式
φｐ（Ａ） ｍｏｄ ３＝１
を満たし、
前記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表される可逆的決定論的関数であり、Iが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記点Ｐを使用するステップと
を有する方法。
【請求項２】
ＡがＦ２ｎと異なり、関数（１）が、
Ｙ２＝Ｘ３＋ａＸ＋ｂ
と書かれ、
ここで、ａ＝ａ２、およびｂ＝ａ６であり、
前記決定論的関数が、以下のそれぞれの関数による楕円曲線の点の座標を提供し、
【数１】
ここで、ｕはステップ／ａ／において決められたパラメータであり、
ここで、
ｖ＝（３ａ−ｕ４）／（６ｕ） （６）
である、
請求項１に記載の計算を実行する方法。
【請求項３】
ｑが等式、
ｑ＝２ｎ
を満たし、
ここで、ｎは奇数の整数であり、
式（１）が、
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ
と書かれ、
ここで、ａ＝ａ２、およびｂ＝ａ６であり、
前記決定論的関数が以下のそれぞれの等式による楕円曲線の点の座標を提供し、
【数２】
ここで、ｕはステップ／ａ／において決められたパラメータであり、
ここで、ｗ＝ａ＋ｕ２＋ｕである、
請求項１に記載の計算を実行する方法。
【請求項４】
ステップ／ａ／において、前記パラメータがハッシュ関数を適用することによって得られる、請求項１から３のいずれか一項に記載の計算を実行する方法。
【請求項５】
前記ハッシュ関数が一方向である、請求項４に記載の計算を実行する方法。
【請求項６】
ステップ／ａ／において、前記パラメータが第１のハッシュ関数ｈおよび第２の関数ｈ’を適用することにより得られ、
前記暗号化計算が以下の関数の適用を備え、
ｆ（ｈ）＋ｈ’．Ｇ
ここで、ｆは、決定論的関数であり、
ここで、Ｇは、楕円曲線の点の群の生成元である、
請求項１から５のいずれか一項に記載の計算を実行する方法。
【請求項７】
請求項１から６のいずれか一項に記載の暗号化計算を実行する方法を実施する、少なくとも１つのパスワードによる認証の方法であって、ステップ／ａ／において、前記パラメータが前記パスワードの関数として決められ、前記パスワードが前記パラメータに含まれ、認証ステップが、前記点Ｐに基づいて実行される、認証の方法。
【請求項８】
データを暗号化する方法であって、前記暗号化が、結合演算を許容する楕円曲線に関するボネ−フランクリン識別に基づき、
前記識別が、エンティティを識別する数値であり、
前記方法が、
／ａ／ 請求項６に記載の暗号化計算を実行する方法を前記識別に適用することにより、点を得るステップと、
／ｂ／ 前記点、ランダムパラメータおよびデータを組み合わせることにより、暗号化されたデータを得るステップと
を有する、データを暗号化する方法。
【請求項９】
以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ 楕円曲線上の座標ＸおよびＹを有する点Ｐを決めるステップと、
／ｂ／ 関数を点Ｐに適用することによりパラメータを得るステップであって、
Ａのオイラー関数φが、等式
φ（Ａ）ｍｏｄ３＝１
を満たし、
前記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表された可逆的決定論的関数の逆関数であり、Ｉが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記パラメータを使用するステップと
を有する、電子構成部品において暗号化計算を実行する方法。
【請求項１０】
データ圧縮の方法であって、圧縮されるべきデータが、それぞれ以下の等式を満たす楕円曲線の点Ｐの座標に対応するデータＸおよびＹの対に対応し、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
請求項９に記載の暗号化計算を実行する方法のステップ／ａ／から／ｃ／が、データの前記対のそれぞれに適用され、
データの前記対が、それぞれステップ／ｃ／において得られたパラメータによって表される、
データ圧縮の方法。
【請求項１１】
請求項１から６のいずれか一項に記載の暗号化計算を実行する方法の実施に適応された手段を有するデバイス。
【請求項１２】
請求項９に記載の暗号化計算を実行する方法の実施に適応された手段を有する電子デバイス。
【請求項１】
以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ パラメータ（１１）を決めるステップと、
／ｂ／ 前記パラメータに関数（１２）を適用することにより点Ｐ（１３）の座標ＸおよびＹを得るステップであって、
Ａのオイラー関数φが、等式
φｐ（Ａ） ｍｏｄ ３＝１
を満たし、
前記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表される可逆的決定論的関数であり、Iが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記点Ｐを使用するステップと
を有する方法。
【請求項２】
ＡがＦ２ｎと異なり、関数（１）が、
Ｙ２＝Ｘ３＋ａＸ＋ｂ
と書かれ、
ここで、ａ＝ａ２、およびｂ＝ａ６であり、
前記決定論的関数が、以下のそれぞれの関数による楕円曲線の点の座標を提供し、
【数１】
ここで、ｕはステップ／ａ／において決められたパラメータであり、
ここで、
ｖ＝（３ａ−ｕ４）／（６ｕ） （６）
である、
請求項１に記載の計算を実行する方法。
【請求項３】
ｑが等式、
ｑ＝２ｎ
を満たし、
ここで、ｎは奇数の整数であり、
式（１）が、
Ｙ２＋ＸＹ＝Ｘ３＋ａＸ２＋ｂ
と書かれ、
ここで、ａ＝ａ２、およびｂ＝ａ６であり、
前記決定論的関数が以下のそれぞれの等式による楕円曲線の点の座標を提供し、
【数２】
ここで、ｕはステップ／ａ／において決められたパラメータであり、
ここで、ｗ＝ａ＋ｕ２＋ｕである、
請求項１に記載の計算を実行する方法。
【請求項４】
ステップ／ａ／において、前記パラメータがハッシュ関数を適用することによって得られる、請求項１から３のいずれか一項に記載の計算を実行する方法。
【請求項５】
前記ハッシュ関数が一方向である、請求項４に記載の計算を実行する方法。
【請求項６】
ステップ／ａ／において、前記パラメータが第１のハッシュ関数ｈおよび第２の関数ｈ’を適用することにより得られ、
前記暗号化計算が以下の関数の適用を備え、
ｆ（ｈ）＋ｈ’．Ｇ
ここで、ｆは、決定論的関数であり、
ここで、Ｇは、楕円曲線の点の群の生成元である、
請求項１から５のいずれか一項に記載の計算を実行する方法。
【請求項７】
請求項１から６のいずれか一項に記載の暗号化計算を実行する方法を実施する、少なくとも１つのパスワードによる認証の方法であって、ステップ／ａ／において、前記パラメータが前記パスワードの関数として決められ、前記パスワードが前記パラメータに含まれ、認証ステップが、前記点Ｐに基づいて実行される、認証の方法。
【請求項８】
データを暗号化する方法であって、前記暗号化が、結合演算を許容する楕円曲線に関するボネ−フランクリン識別に基づき、
前記識別が、エンティティを識別する数値であり、
前記方法が、
／ａ／ 請求項６に記載の暗号化計算を実行する方法を前記識別に適用することにより、点を得るステップと、
／ｂ／ 前記点、ランダムパラメータおよびデータを組み合わせることにより、暗号化されたデータを得るステップと
を有する、データを暗号化する方法。
【請求項９】
以下の等式を満たす楕円曲線上の点Ｐを得るステップを有する、電子構成部品において暗号化計算を実行する方法であって、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である、有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
前記方法が、
／ａ／ 楕円曲線上の座標ＸおよびＹを有する点Ｐを決めるステップと、
／ｂ／ 関数を点Ｐに適用することによりパラメータを得るステップであって、
Ａのオイラー関数φが、等式
φ（Ａ）ｍｏｄ３＝１
を満たし、
前記関数が、ａｌ、ａ２、ａ３、ａ４およびａ６において、およびＡの中の前記パラメータにおいて有理分数によって表された可逆的決定論的関数の逆関数であり、Ｉが有限体Ｆｑに関する１に等しい、少なくともｑ／４Ｉ個の点Ｐを得るステップと、
／ｃ／ 暗号法的暗号化またはハッシュまたは署名または認証または識別アプリケーションにおいて前記パラメータを使用するステップと
を有する、電子構成部品において暗号化計算を実行する方法。
【請求項１０】
データ圧縮の方法であって、圧縮されるべきデータが、それぞれ以下の等式を満たす楕円曲線の点Ｐの座標に対応するデータＸおよびＹの対に対応し、
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４＋Ｘ＋ａ６ （１）
ここで、ａｌ、ａ２、ａ３、ａ４およびａ６は、要素の集合Ａの要素であり、
ここで、Ａは、ｑが数Ｉの厳密には３より大きい異なる素数の正の整数積であり、Ｉが２より大きいか等しい整数である、モジュラ整数Ｚ／ｑＺの環であるか、あるいはＡは、ｑが素数の整数の累乗である有限体Ｆｑであり、
ここで、ＸおよびＹは、点Ｐの座標であり、かつＡの要素であり、
請求項９に記載の暗号化計算を実行する方法のステップ／ａ／から／ｃ／が、データの前記対のそれぞれに適用され、
データの前記対が、それぞれステップ／ｃ／において得られたパラメータによって表される、
データ圧縮の方法。
【請求項１１】
請求項１から６のいずれか一項に記載の暗号化計算を実行する方法の実施に適応された手段を有するデバイス。
【請求項１２】
請求項９に記載の暗号化計算を実行する方法の実施に適応された手段を有する電子デバイス。
【図１】
【公表番号】特表２０１２−５１５４８９（Ｐ２０１２−５１５４８９Ａ）
【公表日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願番号】特願２０１１−５４５７８１（Ｐ２０１１−５４５７８１）
【出願日】平成２２年１月８日（２０１０．１．８）
【国際出願番号】ＰＣＴ／ＦＲ２０１０／０５００２３
【国際公開番号】ＷＯ２０１０／０８１９８０
【国際公開日】平成２２年７月２２日（２０１０．７．２２）
【出願人】（５０９０６９９０６）
【Ｆターム（参考）】
【公表日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願日】平成２２年１月８日（２０１０．１．８）
【国際出願番号】ＰＣＴ／ＦＲ２０１０／０５００２３
【国際公開番号】ＷＯ２０１０／０８１９８０
【国際公開日】平成２２年７月２２日（２０１０．７．２２）
【出願人】（５０９０６９９０６）
【Ｆターム（参考）】
[ Back to top ]