(57)【特許請求の範囲】
【請求項１】
暗号化システムであって、
楕円曲線（Ｅ）のシステムパラメタを求める計算機を備え、
当該システムパラメタの情報を記憶するメモリのメモリセルは、あらかじめ設定されたビット長ｗを有し、
前記システムパラメタはそれぞれ、ビット長ｎのビット列として表され、ｄ＝ｎ／ｗ個のメモリセルに記憶され、
前記計算機によって、１つのシステムパラメタがそれぞれｅ＝ｎ ｍｏｄｕｌｏ ｗ＝ｎ−ｄ＊ｗ個の残余ビット列を有し、当該ｅ個の残余ビット列があらかじめ定めた一定のパターンを有するように、前記の楕円曲線（Ｅ）のシステムパラメタを求め、
前記計算機を介して、前記の求めた楕円曲線を使用して暗号化法を実行することを特徴とする、
暗号化システム。
【請求項２】
前記のシステムパラメタに対してそれぞれ、ビット長ｎ−ｅを有する前記の求めたビット列をｄ個のメモリセルに記憶する、
請求項１に記載の暗号化システム。
【請求項３】
前記の求めた楕円曲線（Ｅ）に対し、あらかじめ定めた暗号化の品質判定基準が満たされているか否かを、前記計算機を介して検査し、
当該のあらかじめ定めた暗号化の品質判定基準の一部として含まれているのは、前記のｅ個の残ビット列が、あらかじめ定めた一定のパターンを有することであり、
前記の暗号化の品質基準を満たしている場合、前記計算機を介して、前記の求めた楕円曲線（Ｅ）を、楕円曲線（Ｅ）として選択する、
請求項１または２に記載の暗号化システム。
【請求項４】
前記のメモリセルのビット長ｗは、２のべきである、
請求項１から３までのいずれか１項に記載の暗号化システム。
【請求項５】
前記暗号化法を実行する際に、
当該楕円曲線（Ｅ）の基点とスカラを選択し、スカラは秘密鍵を構成し、基点は公開鍵を構成する、
請求項１から４までのいずれか１項に記載の暗号化システム。
【請求項６】
暗号化システムであって、
楕円曲線（Ｅ）のシステムパラメタを求める計算機を備え、
当該システムパラメタの情報を記憶するメモリのメモリセルは、あらかじめ設定されたビット長ｗを有し、
前記システムパラメタはそれぞれ、ビット長ｎのビット列として表され、ｄ＝ｎ／ｗ個のメモリセルに記憶され、
前記計算機によって、１つのシステムパラメタがそれぞれｅ＝ｎ ｍｏｄｕｌｏ ｗ＝ｎ−ｄ＊ｗ個の残余ビット列を有し、当該ｅ個の残余ビット列があらかじめ定めた一定のパターンを有するように、前記の楕円曲線（Ｅ）のシステムパラメタを求め、
前記計算機を介して、前記の求めた楕円曲線を使用して暗号化法を実行し、
計算機を介して、前記のｄ個のメモリセルに記憶されたビット長ｎ−ｅ＝ｄ＊ｗのビット列をそれぞれ読み出し、
当該計算機を介してあらかじめ定めた一定のパターンを有する、あらかじめ定めたｅ個の残余ビットを補うことによって前記の各システムパラメタを再構成して、楕円曲線（Ｅ）を再構成する、暗号化システム。
【請求項７】
暗号化システムであって、
楕円曲線（Ｅ）のシステムパラメタを求める計算機を備え、
当該システムパラメタの情報を記憶するメモリのメモリセルは、あらかじめ設定されたビット長ｗを有し、
前記システムパラメタはそれぞれ、ビット長ｎのビット列として表され、ｄ＝ｎ／ｗ個のメモリセルに記憶され、
前記計算機によって、１つのシステムパラメタがそれぞれｅ＝ｎ ｍｏｄｕｌｏ ｗ＝ｎ−ｄ＊ｗ個の残余ビット列を有し、当該ｅ個の残余ビット列があらかじめ定めた一定のパターンを有するように、前記の楕円曲線（Ｅ）のシステムパラメタを求め、
前記計算機を介して、前記の求めた楕円曲線を使用して暗号化法を実行し、
さらに
計算機を介して、前記のｄ個のメモリセルに記憶されているビット長ｎ−ｅ＝ｄ＊ｗのビット列をそれぞれ読み出し、
当該計算機を介して、あらかじめ定めた一定のパターンを有するあらかじめ定めたｅ個の残余ビットを補うことによって各システムパラメタを再構成することによって前記の楕円曲線（Ｅ）を再構成し、
前記の求めた楕円曲線（Ｅ）上の点の局所座標だけを使用して、前記計算機を介して、前記の乗算を行う、暗号化システム。
【請求項８】
前記の楕円曲線上の点のｘ座標だけを使用して前記の乗算を行う、
請求項７に記載の暗号化システム。
【請求項９】
前記の楕円曲線上にある点と、当該の点自体とを前記のスカラに等しい回数だけ加算および倍々にすることによって前記の乗算を行う、
請求項７に記載の暗号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化アプリケーション向けに計算機の支援によって楕円曲線を求めて、暗号化パラメタの効率的な記憶を可能する方法および装置に関する。さらに上記のような方法によって求めた楕円曲線を再構成する方法および上記のようにして求めたないしは再構成した楕円曲線に基づき、計算機の支援によって点とスカラとを乗算する方法に関する。
【０００２】
有限体上の楕円曲線に基づく暗号化アプリケーションは、今日最も効率的な非対称暗号化法である。このことは、第１世代の非対称暗号化法とは異なり、楕円曲線においては準指数関数時間での攻撃法が知られていないことによる。この結果、使用するセキュリティパラメタのビット当たりのセキュリティ利得が高くなるため、実践的なアプリケーションに対して格段に短い鍵長を使用することができる。結果として得られる方法は、安全性が同程度の場合に一層高性能であり、またシステムパラメタを伝送するため、他の非対称暗号化法よりも一層少ない帯域幅しか必要としないのである。
【０００３】
上記のような方法を作動させるため、種々異なるデータを記憶しなければならない。このようなデータには一方では上記のシステムの各加入者に個別に割り当てられる鍵材料が含まれ、また一般的なシステムパラメタが含まれている。これらのシステムパラメタは公知であり、上記の暗号化法のすべてのユーザは同じシステムパラメタを使用する。上記のシステムパラメタの一部は、使用される暗号化法により、またはそのインプリメンテーションにより、すべての加入者に暗黙に知られているが、別の値は、各加入者が、例えば不揮発性の記憶装置（PROM，EEPROM，フラッシュ、別のデータ担体等）に持続的に記憶しなければならないのである。
【０００４】
有限体上の楕円曲線の点群に基づく暗号化法では、上記の一般的なシステムパラメタは少なくとも、使用する有限体（素数、素数べきおよび／または規約多項式）を定義するためのデータと、使用する楕円曲線を決定する曲線パラメタとからなる。場合によっては基点の座標または点群および／部分群の次数を決定するための別のデータがこれに加わる。
【０００５】
例えばRFIDまたは専用またはＩＣなどのような大量生産アプリケーション向けであって、剽窃から保護するための低価格の暗号化製品においてつねにあるのは、単価をできるかぎり抑えたいという要求である。このような半導体製品の製造コストはもっぱら所要のチップ面積によって決まり、このチップ面積そのものも、不揮発性のメモリの所要の容量に依存するのである。この点で上記のような方法において、持続的に記憶すべきシステムパラメタに必要なメモリスペースをさらに低減したいという要求が存在するのである。
【０００６】
したがって本願発明の課題は、非対称の暗号化法を提供して、この方法により、上記の非対称暗号化法において持続的に記憶すべきシステムパラメタに必要なメモリスペースを少なくすることである。
【０００７】
この課題は、請求項１，８および９に記載された特徴的構成を備えた方法ならびに請求項１２の特徴的構成を備えた装置によって解決される。本発明の有利な実施形態は従属請求項に示されている。
【０００８】
暗号化アプリケーション向けに計算機の支援によって楕円曲線を求める本発明の方法では、この楕円曲線（Ｅ）の複数のシステムパラメタを求める。ここでこれらのシステムパラメタの情報を記憶するためのメモリセルは、あらかじめ設定可能なビット長ｗを有する。上記のシステムパラメタはそれぞれ、ビット長ｎのビット列として表すことができるため、ｄ＝ｎ／ｗ個のメモリセルに記憶する場合、１つのシステムパラメタはそれぞれｅ＝ ｎ ｍｏｄｕｌｏ ｗ＝ｎ−ｄ＊ｗ個の残余ビット列を有する。
【０００９】
ここでは上記の楕円曲線（Ｅ）のシステムパラメタを求めて、上記のｅ個の残余ビット列が、あらかじめ定められる一定のパターンを有するようにする。
【００１０】
上記のようにして求めた楕円曲線（Ｅ）を再構成する本発明の方法では、ｄ個のメモリセルに記憶された、ビット長ｎ−ｅ＝ｄ＊ｗのビット列がそれぞれ読み出される。各システムパラメタは、あらかじめ設定することの可能な一定のパターンを有するあらかじめ定めた残余ビット長ｅを補うことによって再構成される。
【００１１】
計算機の支援によって点とスカラとを乗算する本発明の方法では、楕円曲線（Ｅ）を上記のように求めるかないしは再構成する。
【００１２】
ここで上記の点は、求めた楕円曲線上にある。この場合に上記の乗算は、上記の求めた楕円曲線（Ｅ）上の点の局所座標だけを使用して行われる。
【００１３】
楕円曲線を求める本発明の装置は、計算ユニットを有しており、この計算ユニットは、上で示したステップを実行するように構成されている。
【００１４】
以下では図面に基づき、実施例によって本発明を詳細に説明する。
【図面の簡単な説明】
【００１５】
【図１】本発明にしたがってｄ個のメモリセルに分割されまたｅ個の残余ビット列を有するシステムパラメタのビット列を示す図である。
【図２】本発明による残余ビット列の一定のパターンを示す略図である。
【００１６】
楕円曲線の点集合にはアーベル群構造Ｇを定義することができる。この群構造により、整数と曲線上の点とのスカラ乗算Ｚ×Ｇ→Ｇが導かれ、これが、楕円曲線ベースのすべての暗号化法の基本をなしている。ｓを整数、Ｐをこの楕円曲線Ｅの点、またＱ＝ｓＰを点Ｐのｓ倍とする。点ＰおよびＱが与えられた場合、Ｑ＝ｓＰである適当なスカラｓを計算することは、楕円曲線に対する離散対数問題と称される。有限体Ｋおよび楕円曲線Ｅのパラメタを適当に選択すると、今日利用可能なアルゴリズム手段によっては、許容される時間内で上記の離散対数問題を解くことはできない。楕円曲線を暗号化に応用する際の安全性は、この困難さに依拠しているのである。すなわち楕円曲線Ｅは一般にｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6の形の３次方程式によって表され、ただしａ1，ａ2，ａ3，ａ4，ａ6は有限体Ｋの元であり、これらの元は、曲線Ｅのパラメタであり、結果的にシステムパラメタと称されるのである。Ｋ2に属するすべての対（ｘ，ｙ）の集合であって上記の曲線方程式Ｅを満たす集合は、楕円曲線Ｅの点と称される。
【００１７】
上記の離散対数問題によれば、暗号化のため、電子署名の生成のため、および他の応用向けに対称暗号化法を構成することが可能である。このために上記の非対称暗号化法の使用者は、楕円曲線Ｅの点Ｐ、いわゆる基点と、スカラｓとを選択する。スカラｓは秘密鍵を構成し、点Ｑ＝ｓＰはこの非対称暗号化法の公開鍵を構成する。
【００１８】
暗号化への応用に対して有限体Ｋを使用する。上記のアーベル群Ｇも有限群を構成する。したがって上記の曲線の方程式Ｅを満たす点の個数も有限である。暗号化への応用向けに楕円曲線Ｅ（ａ1，ａ2，ａ3，ａ4，ａ6）が有利になるようにするため、パラメタａ1，ａ2，ａ3，ａ4，ａ6をＫから適当に選択しなければならない。上記のパラメタから得られる曲線Ｅおよび点群Ｇは、専門書に記載されている所定の特性を満たさなければならない。
【００１９】
これらは、例えば連邦電子情報保安局（ＢＳＩ  Bundesamtes fuer Sicherheit in der Informationstechnik）の要求目録から得ることができ、この要求目録には、ドイツ署名法にしたがって署名アプリケーション向けの有利な暗号化法が規定されている。
【００２０】
上記のように楕円曲線ベースの暗号化法の安全性は、選択される楕円曲線の暗号化特性に実質的に依存しているのである。
【００２１】
さて以下では標数２の有限体ＧＦ（２n）上の楕円曲線を考察する。このような有限体では、元はふつう長さｎのビットストリングとして表される。ここで個々のビットは、多項式基底または正規基底に関して、上記の元の係数を表す。この表現は極めてコンパクトでありかつメモリ効率が高い。
【００２２】
使用する楕円曲線の暗号化についての安全上の理由から、有限体の元を表すビットストリングの長さを決定する有限体ＧＦ（２n）の拡大次数を合成数とすることはない。例えば、実践的に関連するインプリメントに対して、拡大次数として２のべきは禁止される。その一方、慣用のすべてのメモリシステム（揮発性メモリおよび不揮発性メモリ）は、最小の記憶可能データ単位としてビットの列を使用しており、これらのビットの個数は、対応するコンピュータシステムのバス幅に適合される。ふつうバス幅として２のべきが使用される（例えば８ビット、１６ビット、３２ビット、６４ビットなど）。したがって暗号化の点から強力な、標数２の有限体ＧＦ（２n）上の楕円曲線のシステムパラメタを記憶する際には、使用されるメモリセルのすべてが最適には利用されないことがある。ここでは、上記のシステムパラメタについての情報によって部分的にしか占有されていないメモリセルがつねに生じる。この問題は、記憶ユニットの使用されるサイズが２のべきでない場合にも発生する。上記の有限体の拡大次数ｎは、素数でなければならず、したがって自明でない約数を有してないのである。
【００２３】
上記の揮発性メモリおよび不揮発性メモリを実現するために標準コンポーネントを使用する場合、これらの素子は、コンピュータシステムのバス幅に適合させたデータサイズをベースとするのがふつうである。例えばシステムパラメタを記録する際には、上記のようにして実現したメモリの複数の部分は、機能しておらず、またこの付加的なメモリに必要なチップ面積がむだに使用されてしまう。逆に上記のメモリが、記憶すべきパラメタの精確な長さに適合されている場合、このために頻繁にメモリを専用に発展させる必要が生じ、また利用可能な標準コンポーネントを使用することができない。また多くのインプリントにおいて、必要なチップ面積が、幅の広いバスを実現するために大きく増大してしまうのである。
【００２４】
この問題は、殊にＥＥＰＲＯＭ技術またはフラッシュ技術ベースの不揮発性メモリにおいて発生する。技術的な理由から、上記のようなメモリの個々のビットは、直接読み出したり書き込んだりすることはできない。そうではなくメモリ全体は、より小さなバンクに分割されて、１つのバンクのすべてのビットに同時にアクセスすることだけしかできないのである。これらのバンクの幅もふつう同様に２のべきである。
【００２５】
本発明により、標数２の有限体上の楕円曲線の暗号化パラメタを符号化および復号化する方法が得られ、上記のパラメタを記憶するのに必要なメモリスペースが、部分的にしか占有されていないメモリセルを有しないようにする。
【００２６】
以下では素数の拡張次数ｎを有する有限体ＧＦ（２n）と、（揮発性または不揮発性の）メモリのメモリセルの幅ｗとが与えられたとする。ｎをｗで除算した整数部分ｄとし、またｅをこの除算の残余とする。
【００２７】
この関係は、図１ａ，ｂ，ｃにも分かり易く示されている。図１ａにはｎ個のビットエレメントを有するシステムパラメタのビット列が示されている。メモリセルの幅がｗであることにより、除算ｄ＝ｎ／ｗが余りなしに行われる場合にだけ、このビット列が、個々のメモリセルをそれぞれ完全に占有することができる。
【００２８】
図１ｂおよび１ｃには、システムパラメタのビット列による上記のメモリセルの占有状態が示されている。ここではｄ＝ｎ／ｗ個のメモリセルは完全に占有されているのに対し、１つのメモリセルは、ｅ＝ｎ ｍｏｄｕｌｏ ｗ個のビットエレメントだけで占有されている。
【００２９】
この結果、有限体ＧＦ（２n）の元ａをメモリに格納するために少なくともｄ＋１個のメモリセルが必要である。これらのメモリセルのうち、ｄ個のメモリセルが情報で完全に占有されている。残りのメモリセルは、情報の入ったｅ個のビットだけを含んでおり、したがって部分的にしか占有されていないのである。
【００３０】
本発明により、楕円曲線における暗号化についてのシステムパラメタを符号化および復号化する方法が得られ、有限体ＧＦ（２n）の元でありかつ記憶すべき上記のパラメタをｄ個のメモリセルに記憶することができる。言い換えると、このような元を記憶するためにｎ個のビットの代わりにｄ＊ｗ＝ｎ−ｅ個のビットだけが必要なのである。
【００３１】
上記のパラメタの表現をｎ−ｅ個のビットで行うため、有限体ＧＦ（２n）の元を表すｅ個のビットを一定の値に設定する。この一定値は、暗黙的に知られており、したがって格納する必要はない。上記の暗号化法を実現するためのアルゴリズムにより、ｄ個のメモリセルに記憶されたｄ＊ｗ個のビットを読み出して上記のシステムパラメタを再構成し、また残余のｅ個のビットをその一定の値に設定する。
【００３２】
図２ａ，２ｂおよび２ｃはそれぞれ、ｅ個のビットエレメントを有する残余ビット列の一定のパターンの例が示されている。図２ａ，ｂ，ｃのビット列におけるそれぞれの最初のｎ−ｅ個のビット元は、この個所において相応するシステムパラメタの値を示している。これらのそれぞれ続くｅ個のビットエレメントは、上記の一定のビットパターンを示している。例えば、図２ａはビットパターン（１，１，１，１，…）を有しており、図２ｂはビットパターン（１，０，１，０，１，…）を有しており、また図２ｃはビットパターン（１，１，０，１，１，０，…）を有する。当然のことながら、これらのビットパターンは、単なる実施形態の例示ある。別の有利な一定のビットパターン、例えば（０，０，０，０，０，０，…）の使用は、当業者の判断による。
【００３３】
確かに利用可能なシステムパラメタの選択および個数はこれによって制限される。それは、起こり得るすべてのシステムパラメタにおいて上記のｅ個のビットが、あらかじめ定めた一定の値を有してないからである。しかしながら上記の一定のビットの個数ｅが大きすぎなければ、暗号化の点から見て強力な有限体ＧＦ（２n）上の楕円曲線の有利なパラメタを探すことは実践的に比較的に簡単であるため、このｅ個のビットに対する判定基準が満たされるのである。すなわち、上記のｅ個のビットの値は、あらかじめ設定される一定値に相応するのである。
【００３４】
したがって素数の拡大次数ｎを有する標数２の有限体ＧＦ（２n）上の楕円曲線の本発明によるシステムパラメタは、バス幅ｗのメモリを最適に利用して記憶される。ここでこの最適な利用は、システムパラメタのｅ個のビットを一定の値に設定し、したがって暗黙的に既知であり、記憶する必要がないことによって行われるのである。ここでｅは、ｎをｗで除算した際の残余である。
【００３５】
上記のようにコンパクトに表現されるシステムパラメタを有する楕円曲線に基づく暗号化システムにより、このシステムパラメタを適当に求めれば、ふつうに表現される楕円曲線が有するのと同程度の安全レベルが得られる。
【００３６】
殊に上記のシステムパラメタを上で説明したように符号化すれば、有限体の元を効率に完全に再構成することができる。
【００３７】
ｄ個のメモリセルにおける上記のようなコンパクトな表現を有しかつ強力な楕円曲線の有利なシステムパラメタを見つける手法では、システムパラメタを探す際に、付加的な品質判定基準を考慮して、上記のシステムパラメタの表現の選択したｅ個のビットがあらかじめ定めた一定のパターンを有するようにする。
【００３８】
別の１変形形態では、基礎体である有限体を定める規約多項式を変換することによってまたは曲線方程式を双有理変換することによって、すでに設けられている楕円曲線をつぎのような形にする。すなわち、上記のシステムパラメタの表現の選択したｅ個のビットが、あらかじめ定めた一定のパターンを有するような形にするのである。
【００３９】
上記の方法に適切な素数の拡張次数ｎの例は、１３１，１６３および２５７である。上記のメモリの使用するバス幅が、慣用の値のうち１つである８ビット、１６ビットまたは３２ビットである場合、上記の拡張次数においてそれぞれ単に３、３または１ビットを固定の値、例えば０に設定すればよい。
【図１Ａ−１Ｃ】
0005383806.tif 000002
【図２Ａ】
0005383806.tif 000003
【図２Ｂ】
0005383806.tif 000004
【図２Ｃ】
0005383806.tif 000005