(57)【特許請求の範囲】
【請求項１】
送信側コンピュータ・システム内で平文メッセージを暗号化する方法であって、
受信側に送信するため送信側コンピュータ・システムのメモリから値ｘtextを有する１パーセルの平文を選択するステップと、
ｘ座標として値ｘtextを有する第１の点を含む第１の楕円曲線、すなわち、第１の式：ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される楕円曲線Ｅ+と第２の式：−ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される楕円曲線Ｅ-とからなる楕円曲線の集合から選択された楕円曲線、ここで、ａ、ｂ、ｃは既知の値である、を決定するステップと、
乱数ｒと公開鍵とを第１の楕円乗算器に与えて、前記メモリに前記第１の楕円曲線上の第２の点のｘ座標を表す値ｘqを生成するステップと、
前記の値ｘtextとｘqとを第１の楕円加算器に与えて、前記メモリに前記第１の楕円曲線上のｘ座標の第３の点を表すメッセージ値ｘmを生成するステップと、
乱数ｒと前記第１の楕円曲線の初期公開点とを前記第１の楕円乗算器に与えて、前記メモリに手がかり値ｘcを生成するステップと、
前記のメッセージ値ｘmとｘqを前記第１の楕円加算器に与えて、前記第３の点が第１の点と第２の点の和であるかまたは第１の点から第２の点を減じた差であるかを表す符号値ｇを得るステップと、
前記のメッセージ値ｘm、手がかり値ｘc及び符号値ｇを含む前記暗号化されたメッセージを生成するステップを含む方法。
【請求項２】
前記メッセージ値ｘm、前記手がかり値ｘc、および前記符号値ｇは、受信側に送信されることを特徴とする請求項１に記載の方法。
【請求項３】
前記公開鍵は前記受信側の公開鍵であることを特徴とする請求項２に記載の方法。
【請求項４】
ｘ座標として第１の点ｘtextを含む第１の楕円曲線を決定するステップは、
（ｘtextQ（ｘtext））(p+1)/2 = ＋ｘtextQ（ｘtext）（ｍｏｄ ｐ）なら、第１の楕円曲線は楕円曲線Ｅ+であり、
（ｘtextQ（ｘtext））(p+1)/2 = −ｘtextQ（ｘtext）（ｍｏｄ ｐ）なら、第１の楕円曲線は楕円曲線Ｅ-である
（ここで、ｐ = ３（ｍｏｄ ４）、 Q（ｘtext）=（ｘtext）2＋ｃ（ｘtext）＋ｂ）と決定するステップを含むことを特徴とする請求項１に記載の方法。
【請求項５】
さらに、前記受信側で、
前記手がかり値ｘcを第２の楕円乗算器に与えて値ｘqを得るステップと、
メッセージ値ｘm、値ｘq及び符号値ｇを第２の楕円加算器に与えて値ｘtextを得、前記のパーセルの平文を復元するステップとを含むことを特徴とする請求項２に記載の方法。
【請求項６】
楕円曲線代数を使用して平文メッセージを暗号化するためにコンピュータ読み取り可能なプログラム・コードが埋込まれているコンピュータ使用可能な記録媒体であって、前記コンピュータ読み取り可能なプログラム・コードは、
コンピュータにメモリから値ｘtextを有する１パーセルの平文を選択させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータにｘ座標としてｘtextを有する第１の点を含む第１の楕円曲線、すなわち、第１の式：ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される楕円曲線Ｅ+と第２の式：−ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される楕円曲線Ｅ-とからなる楕円曲線の集合から選択された楕円曲線、ここで、ａ、ｂ、ｃは既知の値である、を決定させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに乱数ｒと公開鍵を前記第１の楕円乗算器に与えて、前記第１の楕円曲線上の第２の点のｘ座標を表す値ｘqをメモリに生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに前記の値ｘqと値ｘtextを第１の楕円加算器に与えて、前記第１の楕円曲線上のｘ座標の第３の点を表すメッセージ値ｘmを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに乱数ｒと前記第１の楕円曲線の初期公開点を前記第１の楕円乗算器に与えて、手がかり値ｘcを前記メモリに生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに前記のメッセージ値ｘmと値ｘqを第１の楕円加算器に与えて、前記第３の点が第１の点と第２の点の和であるかまたは第１の点から第２の点を減じた差であるかを表す符号値ｇを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに前記のメッセージ値ｘm、手がかり値ｘcおよび符号値ｇを含む前記の暗号化されたメッセージを生成させるように構成されたコンピュータ・プログラム読み取り可能なプログラム・コードとを含むことを特徴とする記録媒体。
【請求項７】
前記のメッセージ値ｘm、手がかり値ｘc及び符号値ｇは受信側に送信されるものであることを特徴とする請求項６に記載の記録媒体。
【請求項８】
前記公開鍵が前記受信側の公開鍵であることを特徴とする請求項7に記載の記録媒体。
【請求項９】
コンピュータにｘ座標としてｘtextを有する第１の点を含む第１の楕円曲線を決定させるように構成されたコンピュータ読み取り可能なプログラム・コードは、
（ｘtextQ（ｘtext））(p+1)/2=＋ｘtextQ（ｘtext）（ｍｏｄ ｐ）なら、第１の楕円曲線は楕円曲線Ｅ+であり、
（ｘtextQ（ｘtext））(p+1)/2=−ｘtextQ（ｘtext）（ｍｏｄ ｐ）なら、第１の楕円曲線は楕円曲線Ｅ-である（ここで、ｐ = ３（ｍｏｄ ４）、 Q（ｘtext）=（ｘtext）2＋ｃ（ｘtext）＋ｂ）ようにコンピュータに決定させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項６に記載の記録媒体。
【請求項１０】
更に、コンピュータに前記受信側で、前記手がかりｘcを第２の楕円加算器に与えて、ｘqを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに前記受信側で、前記のメッセージ値ｘmと値ｘqと符号値ｇとを第２の楕円加算器に与えて、値ｘtextから平文を復元させるように構成されたコンピュータ読み取り可能なプログラム・コードとを含むことを特徴とする請求項６に記載の記録媒体。
【請求項１１】
平文メッセージを暗号化する方法であって、
２つの乱数ｒとｓを選択するステップと、
楕円乗算器において、前記乱数ｒ、第１の公開鍵／秘密鍵ペアからの公開鍵、第２の公開鍵／秘密鍵ペアからの秘密鍵を使用して現在の手がかりclueiの初期手がかり値clue0を生成するステップと、
受信側に送信するため送信側コンピュータ・システムのメモリから値ｘtextiを有する１パーセルの平文を選択するステップと、
ｘ座標として値ｘtextiを有する第１の点を含む第１の楕円曲線、すなわち、第１の式：ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される総ての楕円曲線Ｅ+と第２の式：−ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される総ての楕円曲線Ｅ-とからなる楕円曲線の集合から選択された楕円曲線、ここで、ａ、ｂ、ｃは既知の値である、を決定するステップと、
前記の値ｘtextiと現在の手がかりclueiとを第１の楕円加算器に与えて、前記メモリに前記第１の楕円曲線上の第２の点のｘ座標を表すメッセージ値ｍiを生成するステップと、
前記のメッセージ値ｍiと現在の手がかりclueiとを前記第１の楕円加算器に与えて、前記第２の点が前記現在の手がかりclueiと第１の点の和であるかまたは第１の点から現在の手がかりclueiを減じた差であるかを表す符号値ｇを生成するステップと、
ペア（ｍi、 ｇ）で前記の暗号化されたメッセージを表すステップと、
後続のパーセルについて、前記の現在の手がかりclueiおよび前記の乱数ｒとｓを使用して後続の手がかりcluei+1を生成するステップを含む方法。
【請求項１２】
さらに、送信側から受信側に前記乱数ｒとｓを送信するステップと、
前記送信側から前記受信側に前記の暗号化されたメッセージを送信するステップを含む請求項１１に記載の方法。
【請求項１３】
前記公開鍵が前記受信側の公開鍵であり、前記秘密鍵が前記送信側の秘密鍵であることを特徴とする請求項１２に記載の方法。
【請求項１４】
ｘ座標としてｘtextiを有する第１の点を含む第１の楕円曲線を決定する前記ステップは、
（ｘtextiQ（ｘtexti））(p+1)/2 = ＋ｘtextiQ（ｘtexti）（ｍｏｄ ｐ）なら、前記第１の楕円曲線はＥ+であり、
（ｘtextiQ（ｘtexti））(p+1)/2 = -ｘtextiQ（ｘtexti）（ｍｏｄ ｐ）なら、前記第１の楕円曲線はＥ-である
（ここで、ｐ = ３（ｍｏｄ ４）で、 Q（ｘtexti）=（ｘtexti）2＋ｃ（ｘtexti）＋ｂ）と決定するステップを含むことを特徴とする請求項１１に記載の方法。
【請求項１５】
前記の後続の手がかりcluei+1を生成する前記ステップは、
前記の乱数ｒと現在の手がかりclueiとを前記第１の楕円乗算器に与えて、積を生成するステップと、
その積と前記乱数ｓとを前記第１の楕円加算器に与えるステップとを含むことを特徴とする請求項１１に記載の方法。
【請求項１６】
さらに、前記受信側で実行される、
第２の楕円乗算器において、前記乱数ｒ、前記の第１の公開鍵／秘密鍵ペアの秘密鍵、前記の第２の公開鍵／秘密鍵ペアの公開鍵から前記の初期手がかりclue0を決定するステップと、
前記楕円曲線Ｅ+とＥ-の中から前記メッセージ値ｍiが有効なｘ座標である前記第２の点を含む前記第１の楕円曲線を決定するステップと、
前記の現在の手がかりclueiと、前記のメッセージ値ｍiと、前記の符号値ｇとを第２の楕円加算器に与えて、ｘtextiを決定するステップと、
現在の手がかりclueiと前記乱数ｒとｓを使用して後続の手がかりcluei+1 を計算するステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１７】
コンピュータに楕円曲線、すなわち、第１の式：ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される楕円曲線Ｅ+と第２の式：−ｙ2 = ｘ3 ＋ ｃｘ2 ＋ ａｘ ＋ ｂで表される楕円曲線Ｅ-とからなる楕円曲線、ここで、ａ、ｂ、ｃは既知の値である、の集合について楕円曲線代数を使用して平文メッセージを暗号化させるためのコンピュータ読み取り可能なプログラム・コードが埋込まれているコンピュータ使用可能な記録媒体であって、前記コンピュータ読み取り可能なプログラム・コードは、
コンピュータに２つの乱数ｒとｓを選択させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに前記乱数ｒ、第１の公開鍵／秘密鍵ペアからの公開鍵、第２の公開鍵／秘密鍵ペアからの秘密鍵を使用して現在の手がかりclueiの初期手がかり値clue0を第１の楕円乗算器において生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータにメモリから値ｘtextiを有する１パーセルの平文を選択させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに前記楕円曲線の集合から選択された、ｘ座標としてｘtextiを有する第１の点を含む第１の楕円曲線を決定させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータにｘtextiと現在の手がかりclueiを使用して、前記第１の楕円曲線上の第２の点のｘ座標を表すメッセージ値ｍiをメモリに生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータにメッセージ値ｍiと現在の手がかりclueiを第１の楕円加算器に与えて、前記第２の点が前記現在の手がかりclueiと第１の点の和であるかまたは第１の点から現在の手がかりclueiを減じた差であるかを表す符号値ｇを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータにペア（ｍi、ｇ）で前記の暗号化されているメッセージを表現させるように構成されたコンピュータ・プログラム読み取り可能なプログラム・コードと、
コンピュータに後続のパーセルについて、前記の現在の手がかりclueiおよび前記乱数ｒとｓを使用して後続の手がかりcluei+1を生成させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする記録媒体。
【請求項１８】
さらに、コンピュータに送信側から受信側に前記乱数ｒとｓを送信させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータに前記送信側から前記受信側に前記の暗号化されたメッセージを送信させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項１７に記載の記録媒体。
【請求項１９】
前記公開鍵が、前記受信側の公開鍵であり、前記秘密鍵が前記送信側の秘密鍵であることを特徴とする請求項１８に記載の記録媒体。
【請求項２０】
コンピュータにｘ座標としてｘtextiを有する第１の点を含む第１の楕円曲線を決定させるように構成された前記のコンピュータ読み取り可能なプログラム・コードは、
（ｘtextiQ（ｘtexti））(p+1)/2=＋ｘtextiQ（ｘtexti）（ｍｏｄ ｐ）なら、第１の楕円曲線は楕円曲線Ｅ+であり、
（ｘtextiQ（ｘtexti））(p+1)/2=−ｘtextiQ（ｘtexti）（ｍｏｄ ｐ）なら、第１の楕円曲線は楕円曲線Ｅ-である（ここで、ｐ = ３（ｍｏｄ ４）で、 Q（ｘtexti）=（ｘtexti）2＋ｃ（ｘtexti）＋ｂ）ようにコンピュータに決定させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項１７に記載の記録媒体。
【請求項２１】
コンピュータに前記の後続の手がかりcluei+1 を生成させるように構成された前記のコンピュータ読み取り可能なプログラム・コードは、
コンピュータに前記の乱数ｒと現在の手がかりclueiとを前記第１の楕円乗算器に与えて、積を生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
コンピュータにその積と前記乱数ｓとを前記第１の楕円加算器に与えさせるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項１７に記載の記録媒体。
【請求項２２】
さらに、前記受信側のコンピュータが、
前記乱数ｒ、前記の第１の公開鍵／秘密鍵ペアの秘密鍵、および前記の第２の公開鍵／秘密鍵ペアの公開鍵から第１の楕円乗算器において前記の初期手がかりclue0を決定するステップと、
前記の楕円曲線Ｅ+とＥ-からｘ座標としてメッセージ値ｍiを有する前記第２の点を含む前記第１の楕円曲線を決定するステップと、
前記の現在の手がかりclueiと、前記のメッセージ値ｍiと、前記の符号値ｇとを第２の楕円加算器に与えて、ｘtextiを決定するステップと、
現在の手がかりclueiと前記の乱数ｒとｓとを使用して後続の手がかりcluei+1を計算するステップを実行するように構成されたプログラム・コードを含む請求項１８に記載の記録媒体。
【発明の詳細な説明】
【０００１】
これは、１９９１年９月１７日出願の米国特許出願第７６１２７６号（現在は米国特許第５１５９６３２号として発行されている）の継続出願である１９９２年１０月２日出願の米国特許出願第９５５４７９号（現在は米国特許第５２７１０６１号として発行されている）の継続出願である１９９３年１２月１４日出願の米国特許出願第１６７４０８号の一部継続出願である米国特許出願第４８４２６４号（現在は米国特許第５５８１６１６号として発行されている）の継続出願である米国特許出願第７５８６８８号の一部継続出願である。
【０００２】
発明の背景
１．発明の分野
本発明は暗号化システムの分野に関するものである。
【０００３】
２．背景技術
暗号化システムは、媒体上で送信側から受信側へメッセージを送信するためのシステムであって、メッセージが「安全」である、つまり対象となる受信側のみがメッセージを復元できるような媒体を使用する。暗号化システムは、「平文」と呼ばれるメッセージを「暗号文」と呼ばれる暗号化形式に変換する。暗号化は、「暗号鍵」つまり鍵を使用してメッセージを操作または変換することにより実行される。受信側は、暗号鍵または鍵を使用して操作または変換プロセスを反転することにより、メッセージを「復号化」する、つまり暗号文から平文に変換する。送信側と受信側のみが暗号鍵を知っている限り、このような暗号化された送信は安全である。
【０００４】
「古典的」暗号システムは、暗号化情報を使用して復号化情報を決定することができる暗号システムである。セキュリティのために、古典的暗号システムでは暗号化鍵を秘匿し、安全なチャネル上でシステムのユーザに送る必要がある。秘密宅配便、盗聴防止機能付き電話伝送回線などの安全チャネルは多くの場合、非実用的で、高価である。
【０００５】
安全暗号化鍵を交換する難しさをなくしたシステムのことを「公開鍵暗号化」と呼んでいる。定義により、公開鍵暗号システムは、メッセージを暗号化する方法を知っているだけでは計算に法外に長い時間をかけないと暗号化鍵を使用して復号化鍵を見つけられないという特性を持つ。暗号化機能としては、暗号化鍵が判明したら、暗号化機能を比較的容易に計算できるようなものを選択する。ただし、暗号化変換機能の逆の計算は困難であるか、または計算上実行不可能である。このような機能を「一方向機能」または「トラップドア機能」と呼ぶ。公開鍵暗号システムでは、鍵に関するある種の情報は公開される。この情報は、安全でない方法で公開または送信されることがあり、またそうされることが多い。さらに、鍵に関するある種の情報は秘密にされる。この情報は、プライバシー保護のため安全なチャネル上で配布することができる（あるいは、プライバシー確保のためローカル・ユーザが作成することもできる）。
【０００６】
代表的公開鍵暗号化システムのブロック図を図１に示す。破線１００内のブロックで表される送信側が、平文メッセージＰｔｘｔを、破線１１５内のブロック図で表される受信側に送信する。平文メッセージは、暗号文メッセージＣに暗号化され、何らかの送信媒体上で送信され、受信側１１５によって復号化され、平文メッセージＰｔｘｔが再現される。
【０００７】
送信側１００は、暗号化デバイス１０１、安全鍵ジェネレータ１０２、および鍵ソース１０３を備える。鍵ソース１０３は、回線１０４を介して安全鍵ジェネレータ１０２に接続されている。安全鍵ジェネレータ１０２は、回線１０５を介して暗号化デバイス１０１に結合されている。暗号化デバイスは、回線１０６上に暗号文出力Ｃを送る。安全鍵ジェネレータ１０２は、回線１０７上に鍵出力を出す。この出力は、暗号文メッセージ１０６とともに、送受信機１０９に送られる。送受信機１０９は、たとえば、モデムなどのコンピュータ送信デバイスや、無線周波送信信号を送信するためのデバイスであってもよい。送受信機１０９は安全でないチャネル１１０上で安全鍵と暗号文メッセージを受信側の送受信機１１１に出力する。
【０００８】
受信側１１５も、暗号化デバイス１１６、安全鍵ジェネレータ１１７、および鍵ソース１１８を備える。鍵ソース１１８は、回線１１９上で安全鍵ジェネレータ１１７に結合されている。安全鍵ジェネレータ１１７は、回線１２０上で暗号化デバイス１１６に結合されている。暗号化デバイス１１６は、回線１２１を介して送受信機１１１に結合されている。安全鍵ジェネレータ１１７は、回線１２２および１２３上で送受信機１１１に結合されている。
【０００９】
動作中に、送信側１００には、受信側１１５に送信する平文メッセージＰｔｘｔがある。送信側１００と受信側１１５は両方とも、それぞれ、同じ暗号化方式を使用する暗号化デバイス１０１と１１６を備える。暗号化デバイスに実装できる適当な暗号システムがいくつかある。たとえば、データ暗号化標準（ＤＥＳ）や他の適当な暗号化方式を実装することができる。
【００１０】
送信側と受信側はさらに、それぞれ、安全鍵ジェネレータ１０２および１１７を備える。これらの安全鍵ジェネレータは、複数のよく知られている公開鍵交換方式のうちの１つを実装している。後述するこれらの方式は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ方式、ＲＡＳ方式、Ｍａｓｓｅｙ−Ｏｍｕｒａ方式、およびＥｌｇａｍａｌ方式を含む。
【００１１】
送信側１００は、鍵ソース１０３を使用して秘密鍵を生成するが、この鍵ソースは乱数ジェネレータであってよい。秘密鍵が安全鍵ジェネレータ１０２に提供され、これを使用して暗号化鍵ｅKを生成する。暗号化鍵ｅKは回線１０５上で暗号化デバイスに送信され、これを使用して、平文メッセージＰｔｘｔを暗号化し、回線１０６上に用意される暗号文メッセージＣを生成して送受信機１０９に送る。安全鍵ジェネレータ１０２はさらに、安全鍵を鍵ソース１０３から暗号化鍵ｅK に変換するために使用される情報も送信する。この情報は、秘密鍵を知らずにこの情報から暗号化鍵を再現するのは実際上不可能なので、安全でないチャネル上で送信することができる。
【００１２】
受信側１１５は、鍵ソース１１８を使用して、秘密鍵および安全鍵１１９を生成する。この秘密鍵１１９は、復号化鍵ＤK を生成するために送信側１００によって用意される鍵生成情報とともに安全鍵ジェネレータ１１７で使用される。この復号化鍵ＤK は、回線１２０上で暗号化デバイス１１６に送られ、そこで、これを使用して暗号文メッセージを復号化し、元の平文メッセージを再現する。
【００１３】
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ方式
ＤｉｆｆｉｅとＨｅｌｌｍａｎの論文「Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、ｖｏｌ．ＩＴ−２２、ｐｐ．６４４−６５４、１９７６年１１月（「ＤＨ」方式）で公開鍵交換の方式が述べられている。ＤＨ方式では、離散指数および対数関数に基づく公開鍵システムを記述している。「ｑ」を素数、「ａ」を原始元とすると、１≦Ｘ、Ｙ≦（ｑ−１）の範囲のＸとＹについて１対１の関係があり、有限体上でＹ＝ａX  ｍｏｄ  ｑ、かつＸ＝ｌｏｇa Ｙを満たす。第１の離散指数関数は与えられたａおよびＸについて容易に評価できるため、公開鍵Ｙの計算に使用される。Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎシステムのセキュリティは、与えられたＸおよびＹについて離散対数関数Ｘ＝ｌｏｇaＹを解く汎用の高速アルゴリズムが知られていないという事実に依っている。
【００１４】
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎシステムでは、公開鍵のディレクトリが公開されるか、もしくは何らかの手段で一般に利用できるようにされる。与えられた公開鍵はユーザにしか知られていない関連付けられた秘密鍵に依存している。しかし、公開鍵から秘密鍵を決定することは実質的に不可能である。たとえば、送信側が「ｍｙＰｕｂ」という公開鍵を持つとする。受信側は「ｔｈｅｉｒＰｕｂ」という公開鍵を持つとする。送信側はさらに、「ｍｙＰｒｉ」という秘密鍵を持つ。同様に、受信側も、「ｔｈｅｉｒＰｒｉ」という秘密鍵を持つ。
【００１５】
公開鍵システムでは多数の要素が公に知られている。Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎシステムの場合には、これらの要素は、素数ｐと原始元ｇを含む。ｐとｇは両方とも、公に知られている。公開鍵を生成するには、（ｍｏｄ  p）に関してｇに秘密鍵指数を累乗する。たとえば、送信側の公開鍵ｍｙＰｕｂは次の式で生成される。
ｍｙＰｕｂ＝ｇmyPri（ｍｏｄ  ｐ）               式（１）
【００１６】
同様に、受信側の公開鍵は次の式で生成される。
ｔｈｅｉｒＰｕｂ＝ｇtheirPri（ｍｏｄ  ｐ）      式（２）
【００１７】
公開鍵は、指数演算と剰余演算(modulo arithmetic) を使って容易に作成できる。前記のように、公開鍵は一般の人々が容易に入手することができる。つまり、公開され、配布されている。さらに、安全でないチャネル上で送信することもできる。公開鍵が知られていても、離散対数問題を解くのは困難であるため、逆関数によって秘密鍵を計算することは非常に難しい。
【００１８】
図２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ型システムを使用した鍵交換の例の流れ図である。ステップ２０１で、素数ｐを選択している。この素数ｐは、公開されている。次に、ステップ２０２で、原始根ｇを選択している。この数ｇも公に知られている。ステップ２０３で、暗号化鍵ｅKを生成し、受信側の公開鍵（ｔｈｅｉｒＰｕｂ）を底、送信側の秘密鍵（ｍｙＰｒｉ）を指数とするべき乗を計算する。つまり、次のようになる。
（ｔｈｅｉｒＰｕｂ）myPri（ｍｏｄ  ｐ）        式（３）
【００１９】
すでにｔｈｅｉｒＰｕｂは、ｇtheirPri（ｍｏｄ  ｐ）に等しいと定義している。したがって、式（３）は次の式で求められる。
（ｇtheirPri）myPri（ｍｏｄ  ｐ）              式（４）
【００２０】
この値が、平文メッセージを暗号化し、暗号文メッセージを作成するために使用される暗号化鍵ｅKである。メッセージを暗号文にする、あるいは暗号化する特定の方法は、よく知られているいくつかの方法のうちの１つであってよい。どの暗号化メッセージを使用するにせよ、暗号鍵は式４で計算した値である。その後ステップ２０４で、暗号文メッセージが受信側に送信される。
【００２１】
ステップ２０５で、受信側は、送信側の公開鍵（ｍｙＰｕｂ）を底、受信側の秘密鍵（ｔｈｅｉｒＰｒｉ）を指数とするべき乗を計算して次のように復号化鍵ＤKを生成する。
ＤK＝（ｍｙＰｕｂ）theirPri（ｍｏｄ  ｐ）      式（５）
【００２２】
式１から、ｍｙＰｕｂはｇmyPri（ｍｏｄ  ｐ）に等しい。したがって、
ＤK＝（ｇmyPri）theirPri（ｍｏｄ  ｐ）         式（６）
【００２３】
（ｇA）Bは（ｇB）Aに等しいので、暗号化鍵ｅKと復号化鍵ＤKは同じ鍵である。これらの鍵を「一回の暗号パット」と呼ぶ。一回の暗号パットは、メッセージの暗号化および復号化に使用される鍵である。
【００２４】
受信側は単に、ステップ２０６で平文メッセージを復元するために復号化鍵を使用して変換アルゴリズムまたは暗号化方式の逆を実行するだけである。送信側と受信側の両方が暗号化鍵の生成にその秘密鍵を使用しなければならないため、他のユーザは暗号文メッセージを読んだり、復号化したりできない。ステップ２０５はステップ２０１〜２０４よりも前またはそれと同時に実行できることに注意されたい。
【００２５】
ＲＳＡ
Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ、およびＡｄｅｌｍａｎらの論文「Ｏｎ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」，Ｃｏｍｍｕｍ．Ａｓｓ．Ｃｏｍｐｕｔ．Ｍａｃｈ．，ｖｏｌ．２１，ｐｐ．１２０−１２６，Ｆｅｂ．１９７８（「ＲＳＡ」方式）では他の公開鍵暗号システムを提案している。ＲＳＡ方式は、非常に大きな２つの素数を生成し、それらを掛け合わせることが簡単にできるという事実に基づいているが、その結果を因数分解する、つまりその積から非常に大きな素数を求めることはきわめて困難である。したがって積は、復号化鍵を効果的に構成する素数を損なうことなく暗号化鍵の一部として公開することができる。
【００２６】
ＲＳＡ方式では、鍵生成アルゴリズムを使用して２つの大きな素数ｐおよびｑを選択し、それらを掛け合わせてｎ＝ｐｑを求める。数ｐおよびｑは、数百桁の長さになりうる。次に、Ｅｕｌｅｒの関数をφ（ｎ）＝（ｐ−１）（ｑ−１）として計算する（φ（ｎ）は、１からｎまでの範囲の整数値で、ｎと公約数を持たない）。φ（ｎ）は０からｎ−１までの範囲の任意の整数ａと、整数ｋについて、ａkφ(n)+1＝ａ（ｍｏｄ  ｎ）となる特性を持つ。
【００２７】
１からφ（ｎ）−１の範囲で、φ（ｎ）との公約数を持たない乱数Ｅを選択する。乱数Ｅは、暗号化鍵であり、公開されている。そこで、２つの数の最大公約数を計算するＥｕｃｌｉｄのアルゴリズムの拡張バージョンを使用してＤ＝Ｅ-1（ｍｏｄ  φ（ｎ））を簡単に計算できる。Ｄは復号化鍵であり、秘密にしておく。
【００２８】
情報（Ｅ，ｎ）を暗号化鍵として公開し、これを使って暗号化されていない平文メッセージを暗号文メッセージに次のように変換する。まずメッセージをそれぞれ０からｎ−１までの範囲の整数列として表す。Ｐをそのような整数とする。次に、関係式Ｃ＝ＰE（ｍｏｄ  ｎ）により対応する暗号文整数を与える。情報（Ｄ，ｎ）を復号化鍵として使用し、Ｐ＝ＣD（ｍｏｄ  ｎ）を介して暗号文から平文を復元する。これらは、ＣD＝ＰED＝ｐkφ(n)+1＝Ｐなので、逆変換である。
【００２９】
ＭＡＳＳＥＹ−ＯＭＵＲＡ
Ｍａｓｓｅｙ−Ｏｍｕｒａ暗号システムは、米国特許第４５６７６００号に記述されている。Ｍａｓｓｅｙ暗号システムでは、有限体Ｆqを選択する。体Ｆqは固定であり、公に知られている体である。送信側と受信側はそれぞれ最大公約数Ｇ．Ｃ．Ｄ．（ｅ，ｑ−１）＝１となるような０からｑ−１の範囲の乱数整数ｅを選択する。次に、ユーザはＥｕｃｌｉｄアルゴリズムを使用してその逆Ｄ＝ｅ-1（ｍｏｄ  ｑ−１）を計算する。したがって、Ｄｅ＝１（ｍｏｄ  ｑ−１）となる。
【００３０】
Ｍａｓｓｅｙ−Ｏｍｕｒａ暗号システムでは、安全な送信を実現するために３つのメッセージを送信する必要がある。送信者Ａは受信者ＢにメッセージＰを送信する。送信者Ａは乱数ｅAを計算し、受信者Ｂは乱数ｅBを計算する。送信者はまず、受信者に要素ＰeAを送信する。受信側はｅA を知らないのでＰを復元できない。その代わりに、受信側はその要素を底、自分の秘密鍵ｅB を指数とするべき乗を計算し、第２のメッセージＰeAeBを送信側に返信する。次に、送信側はその要素を底、ＤA-thを指数とするべき乗を計算してｅAの効果を除去し、ＰeB を受信者Ｂに返信する。受信者Ｂは、その要素を底、ＤB-thを指数とするべき乗を計算してこのメッセージを読むことができる。
【００３１】
ＥＬＧＡＭＡＬ暗号システム
ＥｌＧａｍａｌ公開鍵暗号システムでは公に知られている有限体ＦqとＦ*q の要素ｇを使用する。それぞれのユーザは０＞ａ＞ｑ−１の範囲の整数ａを無作為に選択する。整数ａは秘密復号化鍵である。公開暗号化鍵はＦ*qの要素ｇa である。Ｐで表されているメッセージをユーザＡに送信するために、整数Ｋを無作為に選択している。Ｆqの要素のペア、つまり（ｇK，ＰｇaK）がＡに送信される。平文メッセージＰｔｘｔが鍵ｇaKによって暗号化される。値ｇK は平文メッセージＰｔｘｔを決定するための受信側の「手がかり」である。しかし、この手がかりは安全な復号化鍵「ａ」を知っている人しか使用できない。受信者Ａは、「ａ」を知っており、第１の要素ｇKを底、ａを指数とするべき乗を計算して、（ｇK）aを求め、その結果を第２の要素に除算することにより、このペアからメッセージＰを復元する。
【００３２】
楕円曲線
他に「楕円曲線」暗号システムと呼ばれる公開鍵暗号システムもある。楕円曲線暗号システムは、有限体Ｆ上で定義された楕円曲線Ｅの点に基づいている。楕円曲線暗号システムは、セキュリティに関して、離散対数問題を解くのが困難であるという事実に依存している。楕円曲線暗号システムの利点は、有限体を選択するよりも楕円曲線を選択するほうが自由度が高いという点である。しかしながら、楕円曲線暗号システムは、多量の計算を必要とすることからコンピュータ・ベースの公開鍵交換システムでは広く使用されるにいたっていない。コンピュータ・ベースの楕円曲線暗号システムは、他のコンピュータ公開鍵交換システムに比べて低速である。楕円曲線暗号システムは、「Ａ  Ｃｏｕｒｓｅ  ｉｎ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」（Ｋｏｂｌｉｔｚ著、１９８７年、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、Ｎｅｗ  Ｙｏｒｋ）に記述がある。
【００３３】
現在まで、楕円曲線方式は鍵交換と認証に使用されてきた。しかしながら、楕円曲線代数を暗号化方式自体として使用するにあたって適当な方式が提案されていない。
【００３４】
発明の要旨
本発明は、平文を直接、楕円曲線上の点として暗号化する手段を提示するものである。このような楕円曲線代数を使用する直接埋め込み法では、いわゆるＤＥＳ段などの中間暗号生成器段を回避している。本発明で埋め込みが容易になるのは、ｐをｐ＝２q−Ｃ＝３（ｍｏｄ  ４）となる素数としたときに、有限体Ｆp上の楕円曲線パラメータ化を選択した結果である。整数ｑとＣの選択では、ｐを素数とし、高速な算術演算を実行できるようにＣ（負の場合もある）を十分小さくとっている。
【００３５】
平文を２つの関係する曲線のうちの１本の上の点として直接取り扱えるのは、ｐ＝３（ｍｏｄ  ４）となるように素数ｐを選択したからである。平文点を含む曲線を選択するプロセスのことをここでは、「直接埋め込み」と呼ぶ。直接埋め込みを使用すると、通常であれば込み入ったプロセスとなるＫｏｂｌｉｔｚ他の非決定論的アルゴリズムを回避できる。
【００３６】
２つの動作モードがあり、第１のモードは予備ステップとして第２のモードで使用される。Ｅ+および捻れＥ-と表記された２つの楕円曲線、これらの曲線Ｐ1+とＰ1-上の初期点、それぞれ初期点と秘密鍵ｔｈｅｉｒＰｒｉおよびｏｕｒＰｒｉから楕円乗算で導かれるｔｈｅｉｒＰｕｂ+、ｔｈｅｉｒＰｕｂ-とｏｕｒＰｕｂ+、ｏｕｒＰｕｂ-の両方に対する公開鍵点があると仮定する。０からｐ−１までの範囲の１パーセルの平文ｘtextを選択する。Ｅ+またはＥ-にｘ座標ｘtextの点が含まれているかどうかを調べる。乱数ｒを選択し、これを使用して、適切な公開点ｔｈｅｉｒＰｕｂ-の楕円曲線乗算によりその曲線上に新しい座標ｘqを生成する。楕円曲線上の２点の加算と減算の両方のｘ座標を計算できるが、どの結果がどの演算に対応しているかを区別しないｅｌｌｉｐｔｉｃ＿ａｄｄ演算を仮定する。
点ｘtextとｘqのｅｌｌｉｐｔｉｃ＿ａｄｄ演算を実行し、２つの結果のうちの１つを選択して、暗号化メッセージ点ｘm（たとえば、ｘmはｘtext＋ｘqまたはｘtext−ｘqのいずれか）を生成する。ｘtextとｘqに対してｅｌｌｉｐｔｉｃ＿ａｄｄの逆演算を実行し、結果のどれにより演算が逆になるか（ｘm＋ｘqまたはｘm−ｘqからｘtextが明らかになる）を判別し、選択をｇと表す。手がかりｘcを乱数ｒと適切な初期公開点Ｐ±の楕円乗算により生成する。３つ組（ｘm ，ｇ，ｘc）を受信側に送信する。受信側はｘcとｔｈｅｉｒＰｒｉの楕円乗算によりｘq を計算し、さらにｘmとｘqに対してｅｌｌｉｐｔｉｃ＿ａｄｄを計算し、ｇを使用して結果ｘmを選択する。ｘmのｘ座標は平文の元のパーセルである。
【００３７】
第２の動作モードを使用すると、たとえば第１のモードで２つの乱数ｒとｓを送信することにより送信者と受信者との間に同期乱数ジェネレータを設定してそれぞれの暗号化されたパーセルのサイズを縮小することができる。第１の同期している手がかりは、送信側ではｔｈｅｉｒＰｕｂ± とｏｕｒＰｒｉおよびｒとの連続楕円乗算、受信側ではｏｕｒＰｕｂとｔｈｅｉｒＰｒｉ± およびｒとの連続楕円乗算によって構成される。連続する手がかりｘcluenは、手がかりｘcluen-1に対するｅｌｌｉｐｔｉｃ＿ａｄｄ演算の第１の結果と初期点Ｐ1±とｓの楕円乗算で構成される点を選択することで構成される。次に、第１にどの曲線に点ｘtextが含まれているかを判別し、ｘtextとｘcluen のｅｌｌｉｐｔｉｃ＿ａｄｄの第１の結果でｘmを構成し、さらにｘmおよびｘcluen に対するｅｌｌｉｐｔｉｃ＿ａｄｄの結果におけるｘm の位置をｇと記することで平文のそれぞれのパーセルを暗号化する。ペア（ｘm ，ｇ）が受信側に送信される。受信側はどの曲線がｘmに属し、ｘmおよびｘcluen に対してｅｌｌｉｐｔｉｃ＿ａｄｄを実行するかを判別し、ｇを使用して２つの結果から元のメッセージ・パーセルｘm を選択する。
【００３８】
発明の詳細な説明
楕円曲線暗号化方式について説明する。以下の説明では、本発明を完全に理解できるように、ビット数、実行時間など多くの具体的内容を詳細に取りあげている。しかし、本発明は、こうした具体的内容を示さなくても実施可能であることは当業者には明白なことであろう。他に、本発明をわかりにくくするのを避けるため、よく知られている機能については詳細に説明しなかった。
【００３９】
従来技術によるコンピュータ実装楕円曲線暗号化方式の欠点は、他の従来技術によるコンピュータ実装暗号化方式に比べて満足な速度を達成できないという点である。従来技術による楕円曲線暗号システムで必要なモジュロ演算と楕円曲線代数演算は、除算の実行を必要とする。除算があると、コンピュータのＣＰＵ（中央処理装置）の計算オーバーヘッドが増大する。ＣＰＵは、除算よりも、加算と乗算を高速に、しかも少ない処理ステップで実行できる。したがって、従来技術による楕円曲線暗号システムは、これまで、Ｄｉｆｆｉｅ−ＨｅｌｌｍａｎおよびＲＳＡ方式などの他の従来技術による暗号システムに比べて実用的あるいは望ましいものとなっていなかった。
【００４０】
本発明は、明示的な除算を必要としない公開鍵交換の楕円曲線暗号システムを実装する方法と装置を提供する。本発明の好ましい実施形態の利点は、数の高速クラス、逆変換のないパラメータ化、ＦＦＴ乗算剰余演算(multiply mod operation)を実装することにより実現できる。
【００４１】
楕円曲線代数
本発明で使用する楕円曲線は、
ｙ2＝ｘ3＋ｃｘ2＋ａｘ＋ｂ               式（７ａ）
または
−ｙ2＝ｘ3＋ｃｘ2＋ａｘ＋ｂ             式（７ｂ）
を満たす点（ｘ，ｙ）εＦpｋＸＦpｋと「無限遠点」Ａから成り立っている。
【００４２】
上の式でｂ＝０かつａ＝１と置いた、
±ｙ2＝ｘ3＋ｃｘ2＋ｘ                   式（７ｃ）
は、「Ｍｏｎｔｇｏｍｅｒｙパラメータ化」と呼ばれるもので、後で説明のため使用し、
上の式でｃ＝０とした、
±ｙ2＝ｘ3＋ａｘ＋ｂ                    式（７ｄ）
は、Ｗｅｉｅｒｓｔｒａｓｓパラメータ化と呼ばれるもので、これもまた後で説明のため使用する。
【００４３】
送信側（「ｏｕｒ」）と受信側（「ｔｈｅｉｒ」）の秘密鍵は整数であると仮定し、
ｏｕｒＰｒｉ、ｔｈｅｉｒＰｒｉεＺ
と表記する。
【００４４】
次に、送信側と受信側の両方にパラメータを設定する。パラメータは、次のとおりである。
ｐ＝２q−Ｃが高速クラス数（ｑは「ビット深さ」）となるようなｑ。値ｑは、公に知られている値である。
Ｆpｋが体となるｐとｋ。素数ｐと整数ｋは公に知られている数である。
公に知られている、初期ｘ座標である（ｘ1，ｙ1）εＦpｋ。
すべて公に知られている、整数曲線定義パラメータである（ａ，ｂ，ｃ）εＦpｋ。
【００４５】
本発明では、「楕円乗算」と呼ばれ、記号「°」で表される演算を使用する。楕円乗算の演算は文献でもよく知られており、本特許で、次のように式７ｄのＷｅｉｅｒｓｔｒａｓｓパラメータ化を使用して説明する。Ｍｏｎｔｇｏｍｅｒｙパラメータ化などの他のパラメータ化についても類似の規則が得られる。
【００４６】
式７ｄの曲線上に初期点（Ｘ1，Ｙ1）を定義する。整数ｎの集合について、式ｎ°（Ｘ1，Ｙ1）は、加算および２倍の規則と呼ばれる、次の関係式により求められる点（Ｘn，Ｙn）を表す。
Ｘn+1＝（（Ｙn−Ｙ1）／（Ｘn−Ｘ1））2−Ｘ1−Ｘn            式（８）
Ｙn+1＝−Ｙ1＋（（Ｙn−Ｙ1）／（Ｘn−Ｘ1））（Ｘ1−Ｘn+1）  式（９）
【００４７】
（Ｘ1，Ｙ1）＝（Ｘn，Ｙn）のとき、使用する２倍関係は、
Ｘn+1＝（（３Ｘ12＋ａ）／２Ｙ1）2−２Ｘ1；                  式（１０）
Ｙn+1＝−Ｙ1＋（（３Ｘ12＋ａ）／２Ｙ1）（Ｘ1−Ｘn+1）       式（１１）
【００４８】
算術演算は体Ｆpｋ上で実行されるので、すべての（ｍｏｄ  ｐ）が実行される。特に、式８から１１の除算は逆（ｍｏｄ  ｐ）を伴う。
【００４９】
Ｗｅｉｅｒｓｔｒａｓｓ以外のパラメータ化は簡単に公式化できる。
【００５０】
楕円曲線公開鍵交換
送信側と受信側は両方とも前記の同じパラメータのセットを使用する必要がある。送信側と受信側は共に、楕円曲線上の特定のｘ座標として共有暗号パッドを生成する。
【００５１】
以下の説明では、「自分」および「自分側」という用語で送信側を示す。「相手」および「相手側」という用語で受信側を示す。この規約を使用するのは、本発明の鍵交換は１人または複数の送信者と１人または複数の受信者との間で実行可能だからである。そのため、「自分」および「自分側」と「相手」および「相手側」はそれぞれ１人または複数の送信者と受信者を指している。
【００５２】
本発明の楕円曲線暗号システムの公開鍵交換を図３の流れ図に説明してある。
【００５３】
ステップ３０１−自分側で、公開鍵を計算する。ｏｕｒＰｕｂεＦpｋＸＦpｋ
ｏｕｒＰｕｂ＝（ｏｕｒＰｒｉ）°（ｘ1，ｙ1）              式（１２）
【００５４】
ステップ３０２−相手側で、公開鍵を計算する。ｔｈｅｉｒＰｕｂεＦpｋＸＦpｋ
ｔｈｅｉｒＰｕｂ＝（ｔｈｅｉｒＰｒｉ）°（ｘ1，ｙ1）      式（１３）
【００５５】
ステップ３０３−２つの公開鍵ｏｕｒＰｕｂとｔｈｅｉｒＰｕｂが公開され、したがってすべてのユーザに知られる。
【００５６】
ステップ３０４−暗号パッドを自分側で計算する。ｏｕｒＰａｄεＦpｋＸＦpｋ
ｏｕｒＰａｄ＝（ｏｕｒＰｒｉ）°（ｔｈｅｉｒＰｕｂ）＝（ｏｕｒＰｒｉ）°（ｔｈｅｉｒＰｒｉ）°（ｘ1，ｙ1）            式（１４）
【００５７】
ステップ３０５−相手側で、暗号パッドを計算する。ｔｈｅｉｒＰａｄεＦpｋＸＦpｋ
ｔｈｅｉｒＰａｄ＝（ｔｈｅｉｒＰｒｉ）°（ｏｕｒＰｕｂ）＝（ｔｈｅｉｒＰｒｉ）°（ｏｕｒＰｒｉ）°（ｘ1，ｙ1）        式（１５）
【００５８】
楕円曲線上の点は、上記の加算および２倍演算のもとでアーベル群をなす。したがって、式１４と１５の演算の順序は、式の結果に影響を与えることなく入れ替えることができる。したがって、
ｏｕｒＰａｄ＝（ｏｕｒＰｒｉ）°（ｔｈｅｉｒＰｒｉ）°（ｘ1，ｙ1）＝（ｔｈｅｉｒＰｒｉ）°（ｏｕｒＰｒｉ）°（ｘ1，ｙ1）＝ｔｈｅｉｒＰａｄ      式（１６）
【００５９】
送信側と受信側は両方とも、同じ暗号パッドを使用しているので、送信側が暗号化したメッセージを受信側で復号化することができる。（ステップ３０５はステップ３０１−３０４のどれかよりも前または同時に実行できることに注意されたい）。
【００６０】
ステップ３０６では、送信側はｏｕｒＰａｄを使用して平文メッセージＰｔｘｔを暗号化し、暗号文メッセージＣを受信側に送信する。ステップ３０７で、受信側はｔｈｅｉｒＰａｄを使用して、暗号文メッセージＣを復号化し、平文メッセージＰｔｘｔを復元する。
【００６１】
高速クラス数
楕円曲線暗号システムでは、モジュロ演算を使用して公開鍵、１回限りの暗号パッドなどのある種のパラメータを決定する。モジュロ演算は、式の結果の中のビット数を一定の数に制限し、セキュリティを実現するという２つの目的に使用される。離散対数問題は、モジュロ演算を使用しているため一部非対称である。モジュロ演算の欠点は、除算を実行する必要があるという点である。モジュロ演算の解は、数値を一定の数で除算したときの余りである。たとえば、１２ ｍｏｄ ５は２に等しい。（１２を５で割ると商は２で余りは２になり、余り２が解となる）。したがって、モジュロ演算では除算が必要である。
【００６２】
本発明では特別な高速クラスの数を使用し、除算をなくすことで、暗号化と復号化で必要なモジュロ演算を最適化している。本発明で使用するクラスの数は一般に、Ｃを奇数で、比較的小さな値とし（たとえば、コンピュータのワード長以下）、Ｃ＝１（ｍｏｄ  ４）とした場合の２q−Ｃという形式で記述される。
【００６３】
数値がこの形式であれば、モジュロ演算は、シフト、簡単な乗算、および加算のみを使い、除算を使わずに、実行することができる。この高速クラスの一群に、Ｍｅｒｓｅｎｎｅ数と呼ばれる数があり、２q −１という形式である。本発明で使用できる他のクラスは、Ｆｅｒｍａｔ数と呼ばれるもので、２q ＋１という形式であり、ｑは２m に等しい。Ｆｅｒｍａｔ数は、本発明では素数でも素数でなくてもよい。
【００６４】
本発明では、有限体Ｆpｋ上の楕円曲線代数を使用するが、ただしｐ＝２q−Ｃで、かつｐは高速クラス数である。式ｐ＝２q −ＣによってｑとＣのすべての値について素数が得られるわけではないことに注意されたい。たとえば、ｑが４に等しく、Ｃが１に等しい場合、２q−Ｃは１５に等しいが、これは素数ではない。しかし、ｑの値が２、３、または５で、Ｃ＝１であれば、式２q −Ｃは素数３、７、および３１を生成する。
【００６５】
本発明では、有限体Ｆpｋ上に楕円曲線代数を実装する。ただしｐは２q−Ｃで、高速クラスの数の要素である。データの２進表現を使用してコンピュータ上で実行する場合、高速クラスの数を使用することでシフト演算と加算のみにより（ｍｏｄ  ｐ）演算を実現できる。それとは対照的に、「低速な」数を使用した場合には、時間のかかる除算を実行して（ｍｏｄ  ｐ）演算を実行する必要がある。以下の例では、高速クラスの（ｍｏｄ  ｐ）演算の利点を示している。
【００６６】
例１：基数１０（ｍｏｄ  ｐ）除算
３２ビットの２進数ｎとして、１１１０１１０１１１１０１０１１１１０００１１１００１１０１０１（基数１０では、この数値は３，９９１，６５２，１４９である）を考える。
【００６７】
そこで、ｎ（ｍｏｄ  ｐ）を考え、ｐを１２７に等しいとする。式ｎ  ｍｏｄ  １２７は除算では次のように計算できる。
【数１】
0003862500.tif 000002
【００６８】
余り１１２がｎ  ｍｏｄ  １２７の解である。
【００６９】
例２：Ｍｅｒｓｅｎｎｅ数（ｍｏｄ  ｐ）演算
本発明では、ｐがＭｅｒｓｅｎｎｅ数で、ｐ＝２q−１の場合、（ｍｏｄ  ｐ）演算は、除算を使用せずに、シフト演算と加算だけで実行できる。再びｎ（ｍｏｄ  ｐ）を考え、ｎは３，９９１，６５２，１４９で、ｐは１２７であるとする。ｐが１２７であれば、ｐ＝２q−１からｑは７に等しい。１２７＝２7−１＝１２８−１＝１２７である。
【００７０】
（ｍｏｄ  ｐ）演算は、ｎの２進数形式、つまり１１１０１１０１１１１０１０１１１１０００１１１００１１０１０１を使用して実行できる。図５では、まずｎのｑ個の下位ビット（ＬＳＢ）５０１、つまり０１１０１０１をラッチしてシフト演算と加算を実行する。残りの桁のｑ個のＬＳＢ  ５０２つまり、０００１１１０をｑ個の桁５０１に加算し、和５０３（１００００１１）を得る。ｎの次のｑ個のＬＳＢ  ５０４（０１０１１１１）を和５０３に加算して、和５０５（１１１００１０）を生成する。ｎのビット５０６（１１０１１１１）を和５０５に加算し、和５０７（１１１００００１）を得る。
【００７１】
残りのビット５０８（１１１０）は、ｑビットよりも数が少ないが、和５０７に加算して、和５０９（１１１０１１１１）を生成する。この和のビット数はｑよりも多い。したがって、第１のｑビット５１０（１１０１１１１）と次のｑビット５１１との和をとり（この場合単一ビット１）、和５１２（１１１００００）を生成する。この和は、ビット数がｑ以下であり、ｎ（ｍｏｄ ｐ）の解である。１１１００００＝２6＋２5＋２4＝６４＋３２＋１６＝１１２。
【００７２】
したがって、ｎ  ｍｏｄ  １２７の解１１２は、Ｍｅｒｓｅｎｎｅ数の体上の楕円曲線を使用する場合にシフト演算と加算のみで決定される。Ｍｅｒｓｅｎｎｅ数を楕円曲線暗号システムで使用すると、明示的な除算が不要になる。
【００７３】
例３：Ｆｅｒｍａｔ数（ｍｏｄ  ｐ）演算
本発明では、ｐがＦｅｒｍａｔ数で、ｐ＝２q ＋１であれば、（ｍｏｄ  ｐ）演算は、除算を使用せずに、シフト演算、加算、および減算（負の加算）のみで実行できる。再びｎ（ｍｏｄ  ｐ）を考え、ｎを３，９９１，６５２，１４９、ｐを今度は２５７とする。ｐが２５７だと、ｑはｐ＝２q＋１から８に等しく、２５７＝２8＋１＝２５６＋１＝２５７となる。
【００７４】
（ｍｏｄ  ｐ）演算は、ｎの２進数形式、つまり１１１０１１０１１１１０１０１１１１０００１１１００１１０１０１を使用して実行できる。図６では、シフト演算と加算はまずｑ（８）個の下位ビット（ＬＳＢ）６０１（００１１０１０１）をラッチすることで実行される。残りの桁の次のｑ個のＬＳＢ６０２、つまり１１０００１１１をｑ桁６０１から減算する。これを実行するために、ビット６０２の１の補数を生成し、１をＭＳＢ側に加算して、負数とし、ビット６０２’（１００１１１０００）を得る。この負数６０２’をビット６０１に加算して、結果６０３（１０１１０１１０１）を生成する。ｎの次のｑ個のＬＳＢ６０４（１１１０１０１１）を和６０３に加算して、結果６０５（１００１０１１０００）を生成する。ｎのビット６０６（１１１０１１０１）を結果６０５から減算する。したがって、ビット６０６の１の補数が生成され、１の負の符号ビットがＭＳＢ側に加算され、ビット６０６’（１０００１００１０）が生成される。ビット６０６’が結果６０５に加算されて、和６０７（１１０１１０１０１０）を生成する。
【００７５】
和６０７のビット数はｑよりも多いので、ｑ個のＬＳＢはビット６０８（０１１０１０１０）としてラッチされる。次のｑビット（この場合、２ビットのみ、１１）をビット６０８に加算し、和６１０（０１１０１１０１）を生成する。この和は、ビット数がｑ以下であり、ｎ（ｍｏｄ ｐ）の解である。０１１０１１０１＝２6＋２5＋２3＋２2＋２0＝６４＋３２＋８＋４＋１＝１０９。
【００７６】
例４：高速クラスｍｏｄ演算
本発明では、ｐがクラスｐ＝２q −Ｃの数で、Ｃが奇数であり、比較的小さい値（たとえば、２進ワードの長さ以下）の場合、（ｍｏｄ  ｐ）演算は、除算なしでシフト演算と加算のみを使用して実行できる。再びｎ（ｍｏｄ  ｐ）を考え、ｎが６８５、ｐが１３であるとする。ｐが１３のとき、ｐ＝２q −Ｃから、ｑは４に等しく、Ｃは３に等しい。１３＝２4−３＝１６−３＝１３である。
【００７７】
（ｍｏｄ  ｐ）演算は、ｎの２進数形式、つまり１０１０１０１１０１を使用して実行できる。図７において、まずｎのｑ（４）個の下位ビット（ＬＳＢ）７０１、つまり１１０１をラッチしてシフト演算と加算を実行する。残りのビット７０２（１０１０１０）にＣ（３）を掛けると、積７０３（１１１１１１０）が生成される。積７０３をビット７０１に加算して、和７０４（１０００１０１１）を生成する。和７０４のｑ個の下位ビット７０５（１０１１）をラッチする。残りのビット７０６（１０００）にＣを掛けて、積７０７（１１０００）を生成する。積７０７をビット７０５に加算して、和７０８（１０００１１）を生成する。和７０８のｑ個の下位ビット７０９（００１１）をラッチする。残りのビット７１０（１０）にＣを掛けて、積７１１（１１０）を生成する。積７１１をビット７０９に加算して、和７１２（１００１）を生成する。和７１２は、ビット数がｑ以下であり、ｎ（ｍｏｄ  ｐ）の解である。１００１＝２3＋２0＝８＋１＝９である。６８５を１３で割ると、余りは９となる。この高速クラス算術演算では、シフト演算、加算、および乗算のみを使用して解を求めることができる。
【００７８】
シフト演算と加算の実施
高速Ｍｅｒｓｅｎｎｅ  ｍｏｄ演算は、よく知られているシフト手順により実現できる。ｐ＝２q−１の場合、
ｘ＝（ｘ＆ｐ）＋（ｘ＞＞ｑ）            式（１７）
を数回使用して、０からｐ−１までの区間で正のｘを適切な剰余値にすることができる。この手順では、シフト演算と加算のみが必要である。それとは別に、数値ｘ（ｍｏｄ  ｐ）を、
ｘ＝ａ＋ｂ２(q+1)/2＝（ａ，ｂ）         式（１８）
で表すことができる。
【００７９】
他の整数ｙを（ｃ，ｄ）と表すと、
ｘｙ（ｍｏｄ  ｐ）＝（ａｃ＋２ｂｄ，ａｄ＋ｂｃ）      式（１９）
が得られ、その後、ｘｙの正しい簡約された剰余値を得るためにいくつかの自明なシフト−加算の演算が必要になる場合がある。
【００８０】
逆（ｍｏｄ  ｐ）を計算するために、少なくとも、２通りの手順がある。１つは、古典的な拡張ＧＣＤ手順の２進数形式を使用するものである。もう１つは、関係簡約方式を使用するものである。関係簡約方式は次のように動作する。
【００８１】
ｐ＝２q−１、ｘ≠０（ｍｏｄ  ｐ）とし、
ｘ-1（ｍｏｄ  ｐ）を返す。
１）Ｓｅｔ（ａ，ｂ）＝（１，０）ａｎｄ（ｙ，ｚ）＝（ｘ，ｐ）；
２）Ｉｆ（ｙ＝＝０）ｒｅｔｕｒｎ（ｚ）；
３）Ｆｉｎｄ  ｅ  ｓｕｃｈ  ｔｈａｔ  ２e／／ｙ；
４）Ｓｅｔ  ａ＝２q-eａ（ｍｏｄ  ｐ）；
５）Ｉｆ（ｙ＝＝１）ｒｅｔｕｒｎ（ａ）；
６）Ｓｅｔ（ａ，ｂ）＝（ａ＋ｂ，ａ−ｂ）ａｎｄ（ｙ，ｚ）＝（ｙ＋ｚ，ｙ−ｚ）；
７）Ｇｏ  ｔｏ（２）．
【００８２】
２進数拡張ＧＣＤ手順は、ａ／ｂを超えない２の最大べき乗と定義される演算［ａ／ｂ］2により、明示的な除算を使用せずに実行できる。
【００８３】
ｐを与え、ｘ≠０（ｍｏｄ  ｐ）とし、
ｘ-1（ｍｏｄ  ｐ）を返す。
１）Ｉｆ（ｙ＝＝１）ｒｅｔｕｒｎ（１）；
２）Ｓｅｔ  （ｘ，ｖ0）＝（０，１）ａｎｄ（ｕ1，ｖ1）＝（ｐ，ｘ）；
３）Ｓｅｔ  ｕ0＝［ｕ1／ｖ1］2；
４）Ｓｅｔ  （ｘ，ｖ0）＝（ｖ0，ｘ＿ｕ0ｖ0）ａｎｄ（ｕ1，ｖ1）＝（ｖ1，ｕ1＿ｕ0ｖ1）
５）Ｉｆ（ｖ1＝＝０）ｒｅｔｕｒｎ（ｘ）；ｅｌｓｅ  ｇｏ  ｔｏ（３）．
【００８４】
本発明は、従来のまたは汎用コンピュータ・システムで実施することができる。本発明を実施するためのコンピュータ・システムの一実施形態を図４に示す。キーボード４１０およびマウス４１１が双方向システム・バス４１９に結合されている。キーボードとマウスは、ユーザ入力をコンピュータ・システムに送り、そのユーザ入力をＣＰＵ４１３に伝達するためのものである。図４のコンピュータ・システムは、さらに、ビデオ・メモリ４１４、メイン・メモリ４１５、および大容量記憶装置４１２を備えており、すべてキーボード４１０、マウス４１１、およびＣＰＵ４１３とともに双方向システム・バス４１９に結合されている。大容量記憶装置４１２は、磁気、光、または光磁気記憶装置システムや他の利用可能な大容量記憶装置技術などの固定媒体と取り外し可能媒体の両方を備えることもできる。大容量記憶装置は、ネットワークで共有したり、専用大容量記憶装置とすることもできる。バス４１９には、たとえば、ビデオ・メモリ４１４やメイン・メモリ４１５をアドレス指定するために３２本のアドレス線を備えることができる。システム・バス４１９も、たとえば、ＣＰＵ４１３、メイン・メモリ４１５、ビデオ・メモリ４１４、および大容量記憶装置４１２などの構成要素間でデータをやり取りするための３２ビット・データ・バスを備える。それとは別に、データ線とアドレス線を別々にする代わりに、データ線とアドレス線を多重化することもできる。
【００８５】
本発明の好ましい実施形態では、ＣＰＵ４１３は、６８０３０や６８０４０などの、Ｍｏｔｏｒｏｌａ社製の３２ビット・マイクロプロセッサである。ただし、他の適当なマイクロプロセッサやマイクロコンピュータでもかまわない。Ｍｏｔｏｒｏｌａ社製マイクロプロセッサとその命令セット、バス構造および制御線については、アリゾナ州フェニックスのＭｏｔｏｒｏｌａ  Ｉｎｃ．で出版している『ＭＣ６８０３０  Ｕｓｅｒ’ｓ  Ｍａｎｕａｌ』および『ＭＣ６８０４０  Ｕｓｅｒ’ｓ  Ｍａｎｕａｌ』で説明されている。
【００８６】
メイン・メモリ４１５は、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）で構成されており、本発明の好ましい実施形態では、８メガバイトのメモリ構成である。本発明の範囲を逸脱することなく、メモリ容量を増減することができる。ビデオ・メモリ４１４はデュアル・ポート・ビデオ・ランダム・アクセス・メモリであり、本発明では、たとえば、２５６Ｋバイトのメモリ構成である。ただし、これもまたビデオ・メモリの増減が可能である。
【００８７】
ビデオ・メモリ４１４の１つのポートがビデオ・マルチプレクサとシフタ４１６に結合されており、さらにビデオ増幅器４１７に結合されている。ビデオ増幅器４１７を使用して、陰極線管（ＣＲＴ）ラスタ・モニタ４１８を駆動する。ビデオ多重化シフタ回路４１６およびビデオ増幅器４１７はよく知られている技術であり、適当な手段で実装が可能である。この回路は、ビデオ・メモリ４１４に格納されているピクセル・データをモニタ４１８で使用するのに適したラスタ信号に変換する。モニタ４１８は、グラフィック画像を表示するのに適した種類のモニタであり、本発明の好ましい実施形態では、解像度が約１０２０×８３２となっている。他の解像度のモニタも本発明では使用可能である。
【００８８】
上述のコンピュータ・システムは例としてのみ取りあげたものである。本発明は、どのような種類のコンピュータ・システムあるいはプログラミングまたは処理環境であっても実装できる。
【００８９】
ブロック図
図８は、本発明のブロック図である。破線８０１に囲まれている構成要素で表されている送信側が、平文メッセージＰｔｘｔを暗号文メッセージＣに暗号化する。このメッセージＣは、破線８０２で囲まれた構成要素で表される受信側に送信される。受信側８０２は、暗号文メッセージＣを復号化して、平文メッセージＰｔｘｔを復元する。
【００９０】
送信側８０１は、暗号化／復号化手段８０３、楕円乗算器８０５、秘密鍵ソース８０７がある。暗号化／復号化手段８０３は、回線８０９を介して楕円乗算器８０５に結合されている。楕円乗算器８０５は、回線８１１を介して秘密鍵ソース８０７に結合されている。
【００９１】
受信側８０２の暗号化／復号化手段８０４は、回線８１０を介して楕円乗算器８０６に結合されている。楕円乗算器８０６は、回線８１２を介して秘密鍵ソース８０８に結合されている。
【００９２】
送信側８０１の秘密鍵ソース８０７には、送信側の安全な秘密パスワード「ｏｕｒＰｒｉ」が含まれる。秘密鍵ソース８０７は、コンピュータ・システム内の記憶レジスタ、メッセージが送信されると送信側から暗号システムに送られるパスワード、あるいはメッセージが送信されたり、取り出されたりしたときに図８の暗号システムによって読み取られる符号化された物理的な鍵であってよい。同様に、受信側８０２の秘密鍵ソース８０８は、受信側の安全な秘密パスワード、つまり「ｔｈｅｉｒＰｒｉ」を含む。
【００９３】
別のソース８１３には、送信側８０１と受信側の８０２の公開鍵「ｏｕｒＰｕｂ」および「ｔｈｅｉｒＰｕｂ」、初期点（Ｘ1、Ｙ1）、体Ｆpｋ、および曲線パラメータａ、ｂ、ｃなどの公知の情報が格納される。この情報源は、コンピュータ・システムによって使用されるオンライン・ソースである、公開されているディレクトリであってもよく、また安全でない送信媒体上で送信側と受信側との間で送信することもできる。公開ソース８１３は図では、回線８１５を介して送信側８０１に、また回線８１４を介して受信側８０２に記号的に結ばれている。
【００９４】
動作時に、送信側と受信側は安全な送信で暗号化および復号化鍵として使用するため共有の暗号パッドを生成する。送信側の秘密鍵ｏｕｒＰｒｉが、受信側の公開鍵ｔｈｅｉｒＰｕｂとともに楕円乗算器８０５へ送られる。楕円乗算器８０５は、暗号化鍵ｅKを（ｏｕｒＰｒｉ）°（ｔｈｅｉｒＰｕｂ）（ｍｏｄ ｐ）
から計算する。暗号化鍵は、平文メッセージＰｔｘｔとともに暗号化／復号化手段８０３に送られる。暗号化鍵は、暗号文メッセージＣを生成するために、ＤＥＳ方式や本発明の楕円曲線方式などの暗号化方式で使用される。暗号文メッセージを安全でないチャネル８１６上で受信側８０２に送信する。
【００９５】
受信側８０２は受信側の秘密鍵ｔｈｅｉｒＰｒｉを使用して復号化鍵ＤK を生成する。ｔｈｅｉｒＰｒｉは、送信側の（公開ソース８１３からの）公開鍵ｏｕｒＰｕｂとともに秘密鍵ソース８０８から楕円乗算器８０４に送られる。復号化鍵ＤK は、（ｔｈｅｉｒＰｒｉ）°（ｏｕｒＰｕｂ）（ｍｏｄ  ｐ）から生成される。復号化鍵ＤKは、楕円乗算機能の可換であるという性質から暗号化鍵ｅKに等しい。したがって、受信側８０２は、復号化鍵ＤK を使用して、暗号化方式を逆にし、暗号文メッセージＣから平文メッセージＰｔｘｔを復元する。
【００９６】
送信側８０１と受信側８０２の暗号化／復号化手段と楕円乗算器は、プログラム・ステップとして実装し、マイクロプロセッサで実行させることができる。
【００９７】
逆変換なしのパラメータ化
高速クラス数を使用すると、（ｍｏｄ  ｐ）算術演算で除算が不要になる。しかし、上の式１３−１６に示されているように、楕円乗算「°」は、除算を何回か実行する必要がある。本発明を使用すると、逆変換なしにする初期パラメータ化を選択することで、楕円乗算に必要な除算の回数を減らすことができる。これは、「Ｙ」項が不要になるように初期点を選択することで実現される。
【００９８】
本発明では、送信側と受信側の両方が、楕円曲線上の特定のｘ座標として、共有の暗号パッドを生成する。初期点（Ｘ1，Ｙ1）を適切に選択することにより、乗算ｎ°（Ｘ1，Ｙ1）を設定するプロセスから除算をなくすことができる。次のステップでは、整数ｎについて、
ｎ°（Ｘm／Ｚm）            式（２０）
は、座標（Ｘn+m／Ｚn+m）を表している。ｘ＝Ｘ／Ｚについて、Ｘn／Ｚnとしての乗算ｎ（ｘ，ｙ）のｘ座標は、乗算剰余演算を必要とする加算−２倍規則にしたがって「２進はしご」法を使用して計算する。Ｍｏｎｔｇｏｍｅｒｙパラメータ化（式７ｃ）では、これらの規則は、
0003862500.tif 000003
である。
【００９９】
そうでない場合、ｉ＝ｊであれば、
Ｘ2i＝（Ｘi2−Ｚi2）2                      式（２３）
Ｚ2i＝４ＸiＺi（Ｘi2＋ｃＸiＺi＋Ｚi2）     式（２４）
である。
【０１００】
これらの式は、除算を必要としないため、本発明を好ましい実施形態に実装したときに計算が簡略化される。これは、「逆変換なしのパラメータ化」と呼ばれ（除算がないので）、Ｍｏｎｔｇｏｍｅｒｙ，Ｐ．著『Ｓｐｅｅｄｉｎｇ  ｔｈｅ  Ｐｏｌｌａｒｄ  ａｎｄ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｍｅｔｈｏｄｓ  ｏｆ  Ｆａｃｔｏｒｉｚａｔｉｏｎ』（Ｍａｔｈ．Ｃｏｍｐ．、４８（２４３−２６４）、１９８７年）に記載されている。体が単なるＦp であった場合、この方式により、乗算、加算、（高速）Ｍｅｒｓｅｎｎｅ  ｍｏｄ演算を使用して複数のｎｘを計算することができる。これはさらに、体がＦp2の場合にも、成立する。任意のＭｅｒｓｅｎｎｅ数ｐについてｐ＝３（ｍｏｄ  ４）なので、Ｘi またはＺi を複素整数として表し、複素数算術演算を実行して、乗算後の実部と虚部の両方を（ｍｏｄ  ｐ）で素早く簡約することができる。さらに、Ｚ1 ＝１も選択し、曲線上の初期点が、ｙが不要になる場合に（Ｘ1 ／１，ｙ）となるようにする。
【０１０１】
高速クラスの数と逆変換なしのパラメータ化の両方を使用することで、本発明の方法を使用する公開鍵交換を次のように実行できる。次の例では、素数はＭｅｒｓｅｎｎｅ数である。ただし、ここで説明するどの高速クラス数を代替することもできる。
【０１０２】
１）「自分」側で、曲線パラメータ（ａ，ｂ，ｃ）を使用して、公開鍵を計算する。ｏｕｒＰｕｂεＦpｋＸＦpｋ
（Ｘ／Ｚ）＝ｏｕｒＰｒｉ°（Ｘ1／１）
ｏｕｒＰｕｂ＝ＸＺ-1
２）「相手」側で、曲線パラメータ（ａ，ｂ，ｃ）を使用して、公開鍵を計算する。ｔｈｅｉｒＰｕｂεＦpｋＸＦpｋ
（Ｘ／Ｚ）＝ｔｈｅｉｒＰｒｉ°（Ｘ1／１）
ｔｈｅｉｒＰｕｂ＝ＸＺ-1
３）２つの公開鍵ｏｕｒＰｕｂとｔｈｅｉｒＰｕｂは公開されており、従って知られている。
４）共有の暗号パッドを計算する。ｏｕｒＰａｄεＦpｋＸＦpｋ
（Ｘ／Ｚ）＝ｏｕｒＰｒｉ°（ｔｈｅｉｒＰｕｂ／１）
ｏｕｒＰａｄ＝ＸＺ-1
５）共有の暗号パッドを計算する。ｔｈｅｉｒＰａｄεＦpｋＸＦpｋ
（Ｘ／Ｚ）＝ｔｈｅｉｒＰｒｉ°（ｏｕｒＰｕｂ／１）
ｔｈｅｉｒＰａｄ＝ＸＺ-1
【０１０３】
通常の鍵交換が完了し、次のようになる。
ｏｕｒＰａｄ＝ｔｈｅｉｒＰａｄ
【０１０４】
「自分」側と「相手」側との間のメッセージ暗号化／復号化は、この相互暗号パッドに従って進む。
【０１０５】
ＦＦＴ乗算
ｑ＞５０００など、指数が非常に大きな場合には、数列のＦｏｕｒｉｅｒ変換を使って乗算を実行すると都合がよい。ＦＦＴ乗算は、ｐ＝２q −１がｑ＝２20（約１００万）ビット以下の場合に汎用演算ｘｙ（ｍｏｄ  ｐ）について、たとえば、６８０４０ベースのＮｅＸＴｓｔａｔｉｏｎ上で正確に動作する。さらに、Ｍｅｒｓｅｎｎｅ数ｐについても、２進ビットの位数ｑの巡回たたみ込みが乗算（ｍｏｄ  ２q −１）に等価であることが観察されたときにさらに無駄を省ける。ＦＦＴ乗算手法を使用すると、ｑ2 ではなく、ｑｌｏｇｑにおおよそ比例する時間で乗算−ｍｏｄを実行することができる。
【０１０６】
ＦＦＴ手法を使用すると本質的に楕円曲線代数を高速化することができる。Ｘを一般にＸの数列のＦｏｕｒｉｅｒ変換とすると、この変換はＦＦＴ乗算で使用するものと同じである。次に、式２１−２４から座標を計算することができる。たとえば、Ｘi+j を計算するには、５つの適切な変換（Ｘi、Ｘj、Ｚi、Ｚj、およびＺi-j ）（一部は、すでに格納されている）を使用して、次の変換を作成できる。
Ｘi+j＝Ｚi-j（ＸiＸj−ＺiＺj）2
【０１０７】
この方法で、７つのＦＦＴを使って答えＸi+jを求めることができる。（平方に２つのＦＦＴ、乗算に３つのＦＦＴを使用する通常のやり方だと「標準」のＦＦＴ方式に対してＦＦＴは１１個になることに注意されたい）。比７／１１では、固有の方法の無駄がかなり省かれる。ｐがＭｅｒｓｅｎｎｅ数で、誤りのない数論的変換も利用できるような場合には、過去からのスペクトルを確保し、長時間の計算でスペクトル空間にとどまることができ、この方法により、時間がいっそう短縮する。
【０１０８】
高速クラス数、逆変換なしのパラメータ化、およびＦＦＴ乗算を使用したときの本発明の動作を示す流れ図を図９に掲載した。ステップ９０１で、高速クラス数ｐは、ｐ＝２q −Ｃとなるように選択する。項ｑは、暗号化方式のビット深さである。ビット数が多ければ多いほど、セキュリティは高くなる。大きな値のｑについて、ＦＦＴ乗算を使用してｐを計算する。項ｐを公開して使用できるようにする。
【０１０９】
ステップ９０２で、体Ｆpｋ の要素ｋを選択し、公開する。ステップ９０３で、楕円曲線上の初期点（Ｘ１／Ｚ）を選択する。初期点を逆変換なしになるように選択することにより、コストのかかる除算を避ける。初期点を公開する。ステップ９０４で曲線パラメータａを選択し、公開する。
【０１１０】
ステップ９０５で、送信側は逆変換なしのパラメータ化を使用してＸ1 ／Ｚ＝ｏｕｒＰｒｉ°（Ｘ1 ／１）を計算する。送信側の公開鍵が、ｏｕｒＰｕｂ＝（ＸＺ-1）（ｍｏｄ  ｐ）で生成される。受信側の公開鍵ｔｈｅｉｒＰｕｂ＝（ＸＺ-1）（ｍｏｄ  ｐ）はステップ９０６で生成される。
【０１１１】
送信側の１回限りの暗号パッドｏｕｒＰａｄがステップ９０７で生成される。Ｘ／Ｚ＝（ｏｕｒＰｒｉ）°（ｔｈｅｉｒＰｕｂ／１）。ｏｕｒＰｕｄ＝（ＸＺ-1）（ｍｏｄ  ｐ）。ステップ９０８で、受信側の１回限りの暗号パッドｔｈｅｉｒＰａｄを生成する。Ｘ／Ｚ＝（ｔｈｅｉｒＰｒｉ）°（ｏｕｒＰｕｂ／１）。ｔｈｅｉｒＰｕｄ＝（ＸＺ-1）（ｍｏｄ  ｐ）。ｏｕｒＰａｄとｔｈｅｉｒＰａｄの計算で、ＦＦＴ乗算を使用して、逆変換Ｚ-1を不要にする。ステップ９０９で、送信側はｏｕｒＰａｄを使用して平文メッセージＰｔｘｔを暗号文メッセージＣに変換する。暗号文メッセージＣは受信側に送信される。ステップ９１０で、受信側は、ｔｈｅｉｒＰａｄを使用して暗号文メッセージＣを復号化して平文メッセージＰｔｘｔを復元する。
【０１１２】
ＦＥＥセキュリティ
楕円曲線法（ＥＣＭ）を採用したときに「自然な」統計によりＭｅｒｓｅｎｎｅ数である代数的因数Ｍ89＝２89−１が発生する。これは、Ｍ445＝２445−１の因数分解を実行しようとして示された。つまり、乱数パラメータｃ（ａ＝０，ｂ＝１としてＭｏｎｔｇｏｍｅｒｙパラメータ化を使用する）について、ｐ＝Ｍ89としたＦp 上の楕円曲線の出現ｋ（Ｘ1／１＝０は統計的に、Ｍ445のＭ89を見つける時間がＯ（ｅｘｐ（√（２ｌｏｇ ｐ ｌｏｇ ｌｏｇ ｐ））であるという漸近的推定と統計的に一致していた。そこで、これらの観察から、Ｍｅｒｓｅｎｎｅ数については乱数ｃパラメータを仮定した場合にＦp 上の群の位数を見つけるのが「偶然にも」あまり容易でないということが示唆された。
【０１１３】
第２に、ＦＥＥに付随する離散対数問題が偶然に自明でないということをチェックするために、特定のｃパラメータについて、束縛されている整数の集合では、
（ｐN−１）（Ｘ1／１）≠０
が成立することを検証できる。
【０１１４】
不等号は、離散対数評価の対応する有限体上の等価な評価への自明な簡約を避けるためである。不等号が成立しないというのは非常にまれであり、実際、この時点ではｑ＞８９なる数について自明でない実例が知られている。
【０１１５】
本発明では、従来技術に勝る多くの利点を提示しており、特に、ＲＳＡ方式などの因数分解方式を特徴とする。本発明は、少ないビットと高速な演算でありながら、同じセキュリティを実現できる。それとは別に、本発明のシステムでは同じビット数にして、セキュリティを高めることもできる。
【０１１６】
従来技術に勝る本発明の暗号システムの他の利点として秘密鍵の配布がある。ＲＳＡなどの従来技術の方式では、秘密鍵を作成するために大きな素数を生成する必要がある。本発明では、秘密鍵を素数にする必要はない。したがって、ユーザは、正しい公知のパラメータを使用して公開鍵が生成され公開される場合に限り、自分の秘密鍵を生成することができる。ユーザは、ＲＳＡシステムで自分の秘密鍵を生成することはできない。
【０１１７】
電子署名
本発明は、上記の楕円代数とハッシュまたはダイジェスト関数を使用する電子署名を作成し認証する改良された方法を提示する。送信側は暗号化メッセージ「暗号文」を作成済みである。このメッセージを前記のように暗号化するか、または他の暗号化方式を使用して暗号化することができる。送信側は、次に、電子署名を作成して、メッセージの「署名」の手段としてメッセージに添付する。好ましい実施形態の署名方式について以下の段で説明し、その後、計算を減らす方法を説明する。
【０１１８】
署名の作成
開始点（Ｘ1 ／１）を持つａ、ｂ、ｃでパラメータ化された曲線を仮定する。さらに、開始点は楕円曲線上で位数Ｎであると仮定する。送信側の公開鍵ｏｕｒＰｕｂを複数のｏｕｒＰｒｉ°（Ｘ1 ／１）として生成するが、ここでｏｕｒＰｒｉは自分の秘密鍵（整数）、°は楕円曲線上の乗算である。電子署名は次のように作成される。
１）約ｑビットの乱数整数ｍを選択する。
２）点を
Ｐ＝ｍ°（Ｘ1／１）
を計算する。
３）メッセージ・ダイジェスト関数Ｍを使用して、整数
ｕ＝（ｍ＋ｏｕｒＰｒｉ*Ｍ（暗号文，Ｐ））（ｍｏｄ  Ｎ）
を計算する。ただし、暗号文は送信する暗号化されたメッセージである。
４）暗号文とともに、電子署名をペア（ｕ，Ｐ）として送信する。ｕは約２q ビットの整数であるが、Ｐは曲線上の点であることに注意されたい。
【０１１９】
本発明の好ましい実施形態では、ＭＤ２やＭＤ５などのメッセージ・ダイジェスト関数Ｍを電子署名の生成の一部として使用する。ただし、本発明は他のダイジェスト関数を使用したり、適当なハッシュ関数を使用しても、実装できる。
【０１２０】
電子署名の認証
受信側は、暗号文メッセージと、意図されている送信側の公開鍵を使用して、点のペアを生成して電子署名の一致を調べることにより署名を認証しようとする。受信側は、次のステップで署名を検証する。
１）署名のｕ部分を使用して、点
Ｑ＝ｕ°（Ｘ1／１）
を計算する。
２）点Ｑと点 Ｒ＝Ｐ＋Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂを比較する。
【０１２１】
署名は、楕円点ＱおよびＲが正確に比較されていない場合には無効である。つまり、署名が信頼のあるものであれば、次の式が成立しなければならない。
ｕ°（Ｘ1／１）＝Ｐ＋Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂ
【０１２２】
上の式の左辺のｕを置き換えると、
（ｍ＋ｏｕｒＰｒｉ*Ｍ（暗号文，Ｐ））°（Ｘ1／１）＝Ｐ＋Ｍ（暗号文，ｐ）°ｏｕｒＰｕｂ
または
ｍ°（Ｘ1／１）＋（ｏｕｒＰｒｉ*Ｍ（暗号文，Ｐ））°（Ｘ1／１）＝Ｐ＋Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂ
となる。
【０１２３】
式の右辺のｏｕｒＰｕｂを置き換えると、
ｍ°（Ｘ1／１）＋（ｏｕｒＰｒｉ*Ｍ（暗号文，Ｐ））°（Ｘ1／１）＝Ｐ＋Ｍ（暗号文，Ｐ）°ｏｕｒＰｒｉ°（Ｘ1／１）
となる。
上記よりＰ＝ｍ°（Ｘ1／１）なので、左辺は
Ｐ＋（ｏｕｒＰｒｉ*Ｍ（ｃｉｐｈｅｒｔｅｘｔ，Ｐ））°（Ｘ1／１）＝Ｐ＋Ｍ（ｃｉｐｈｅｒｔｅｘｔ，Ｐ）°ｏｕｒＰｒｉ°（Ｘ1／１）
となる。
【０１２４】
式の右辺でｏｕｒＰｒｉを移行すると、
Ｐ＋ｏｕｒＰｒｉ*Ｍ（暗号文，Ｐ））°（Ｘ1／１）＝Ｐ＋ｏｕｒＰｒｉ*Ｍ（暗号文，Ｐ）°（Ｘ1／１）
となる。
【０１２５】
したがって、曲線上の点は、送信されたペア（ｕ，Ｐ）を使用して２つの異なる式を使用して計算される。送信された点ｕからのＱを計算し、さらに送信されたＰ、暗号文メッセージ、および意図されている送信側の公開鍵からＲを計算することにより、ＱとＲが一致すれば電子署名が認証されたと仮定する。
【０１２６】
セキュリティ
この方式の電子署名方式は、次の観察結果をもとに安全なものである。署名を偽造するには、ペア（ｕ，Ｐ）と式
ｕ°（Ｘ1／１）＝Ｐ＋Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂ
を満たす暗号文を見つけなければならなくなる。
【０１２７】
これは、楕円対数演算（本発明の暗号化セキュリティの基盤）を実行するか、またはハッシュ関数Ｍを破る必要がある。
【０１２８】
認証の最適化
本発明の電子署名方式における受信側の最終ステップでは、２つの点、つまりＰとＭ（暗号文，Ｐ）°ｏｕｒＰｕｂを加えてＲを求め、その和を点Ｑと比較する必要がある。各ステップで指定されたｙ座標を使用して楕円加算を実行することもできる。本発明の方式では、注目している要素の２つの点のそれぞれのｘ座標のみを使用して、２つの点の和のｘ座標の可能な値を小さくする方法を実現する。点ＱとＰ＋Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂが同一のｘ座標を持つかどうかをチェックする必要があるが、この方法を使用して、そのチェックを高速に実行することができる。
【０１２９】
ｘ座標のみを使用して和の高速検証を行う原理は次のように動作する。たとえば、Ｍｏｎｔｇｏｍｅｒｙパラメータ化を使用し、曲線を
ｙ2＝ｘ3＋ｃｘ2＋ｘ
とする。
【０１３０】
定理：Ｐ1＝（ｘ1，ｙ1）、Ｐ2＝（ｘ2，ｙ2）、Ｑ＝（ｘ，ｙ）を与えられた曲線上の３つの点とし、ｘ1≠ｘ2とする。このとき、
ｘ（Ｃ−ｘ）＝Ｂ2
の場合、かつその場合に限り、
Ｐ1＋Ｐ2＝Ｑ
が成立する。
ただし、
Ｂ＝（ｘ1ｘ2−１）／（ｘ1−ｘ2）
Ｃ＝２（（ｘ1ｘ2＋１）（ｘ1＋ｘ2＋２ｃ）−２ｃ）／（ｘ1−ｘ2）2
とする。
【０１３１】
証明は次の通りである。Ｐ1とＰ2のｙ座標はわかっていないので、和Ｐ1＋Ｐ2のｘ座標について唯一可能性があるのは、任意に固定されたペア（ｙ1，ｙ2）について、２つの形式（ｘ1，ｙ1）±（ｘ2，ｙ2）のそれぞれのｘ座標（ｅ、ｆと呼ぶ）であることに注意されたい。前記のように、
ｅｆ＝Ｂ2
ｅ＋ｆ＝Ｃ
をＭｏｎｔｇｏｍｅｒｙの場合のように計算できる。ｘはｅ、ｆのうちの一方または他方なので、定理の２次方程式が成り立つには、（ｘ−ｅ）（ｘ−ｆ）＝０である必要がある。
【０１３２】
したがって、本発明のｘ座標方式を使用した場合、（ｘ−ｅ）（ｘ−ｆ）＝０を満たす２つの解を持つ可能性がある。したがって、偽物の署名から一方の可能な解が生成される。ただし、（ｘ−ｅ）（ｘ−ｆ）＝０を満たすときに、文字通り何１００万もの解があるので、署名は信頼できると仮定しても安全である。
【０１３３】
実用的な応用例では、Ｐ1 は、送信側が署名の一部として送信した計算で求めた点Ｐを表す。Ｐ2 は、式Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂを表す。もちろん、Ｑはｕ°（Ｘ1／１）を表す。Ｐ1＋Ｐ2はＲを表し、Ｑと比較される。
【０１３４】
流れ図
図１０は、本発明を使用する電子署名の生成を説明する流れ図である。ステップ１００１で、送信側は乱数整数ｍを選択する。この乱数整数は、マイクロプロセッサで使用する適当な乱数生成器を使用して生成できる。ステップ１００２では、ｍを使用して点Ｐを計算する。前記のように、本発明の好ましい実施形態では、この点は関係式Ｐ＝ｍ°（Ｘ1 ／１）を使用して生成される。ただし、本発明の範囲を逸脱することなく点Ｐを生成するために他の方式を使用することもできる。
【０１３５】
ステップ１００３で、第２の数ｕは、ｍ、Ｐ、ｏｕｒＰｒｉ、および暗号文メッセージを使用して計算する。本発明の好ましい実施形態では、これは、関係式ｕ＝ｍ＋ｏｕｒＰｒｉ*Ｍ（暗号文，Ｐ） を使用して生成する。前記のように、ダイジェスト関数ＭＤ２およびＭＤ５以外のハッシュ関数を使用することもできる。さらに、ｕを計算するために、他の関係式を使用することもできる。他の関係式を使用する場合には、そのｍ、Ｐ、ｏｕｒＰｒｉ、および暗号文メッセージを使用するようお勧めする。ステップ１００４で、計算で求めたペア（ｕ，Ｐ）を電子署名として送信する。
【０１３６】
図１１は、本発明の電子署名の認証を説明する流れ図である。ステップ１１０１で、メッセージの受信者は電子署名（ｕ，Ｐ）と暗号文メッセージを受信する。ステップ１１０２で、点ｕを使用して、点Ｑを生成する。好ましい実施形態では、関係式Ｑ＝ｕ°（Ｘ1／１）を使用してＱを生成する。送信側がｕ、Ｐを計算するのにどのような関係式を使用したかに応じて他の関係式を使用することもできる。
【０１３７】
ステップ１１０３で、ｏｕｒＰｕｂと暗号文メッセージを使用して点Ｐ2を生成する。好ましい実施形態では、関係式Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂを使用してＰ2を生成する。送信側がｕ、Ｐを計算するのにどのような関係式を使用したかに応じて他の関係式を使用することもできる。
【０１３８】
ステップ１１０４で、Ｐ1とＰ2のｘ値を使用して、値ＢとＣを決定し、最終的にｅとｆを決定する。これにより、Ｐ1とＰ2の和の可能な２つのｘ値が得られる。決定ブロック１１０５で、引数「ｅ，ｆ＝ｘ？」を付けて、Ｐ1＋Ｐ2＝Ｑの等式を可能なｘ値のいずれかが満たすかどうかを判断する。計算で求めたｘ値のいずれも方程式を満たさない場合、つまり、決定ブロック１１０５での引数が偽であれば、署名は信頼できるものではなく、ブロック１１０６で指示される。ｘ値のうちの１つが方程式を満たす場合、つまり決定ブロック１１０５での引数が真であれば、有効な署名であると仮定され、ブロック１１０７で指示される。
【０１３９】
ブロック図
図１２は、本発明の電子署名方式を実装するブロック図である。図１２の要素が図８の要素と共通である場合には、同じ要素番号を使用する。楕円乗算を使用する暗号化方式で使用する署名方式を取りあげているが、これは例として取りあげただけである。本発明は、どのような種類の暗号化方式とも使用することができる。
【０１４０】
破線１２０１で囲まれている構成要素で表されている送信側が、平文メッセージＰｔｘｔを暗号文メッセージＣに暗号化し、署名（ｕ，Ｐ）を生成する。このメッセージＣと署名（ｕ，Ｐ）は、破線１２０２で囲まれている構成要素で表されている受信側に送信される。受信側１２０２は、暗号文メッセージＣを復号化して、平文メッセージを復元し、署名（ｕ，Ｐ）を認証する。
【０１４１】
送信側１２０１は、暗号化／復号化手段１２０３、楕円乗算器８０５、乱数生成器１２０５、ハッシュ生成器１２０７、および秘密鍵ソース８０７を備えている。暗号化／復号化手段１２０３は、回線８０９を介して楕円乗算器８０５に結合されている。楕円乗算器８０５は、回線８１１を介して秘密鍵ソース８０７に結合されている。乱数生成器１２０５は、回線１２０９上で乱数ｍを楕円乗算器８０５とハッシュ生成器１２０７に送る。楕円乗算器８０５は、回線１２１１を介して安全でないチャネル８１６に数値ｕを送る。暗号化されている暗号文Ｃが回線１２１３を介してハッシュ生成器１２０７に送られる。ハッシュ生成器１２０７は、回線１２１５を介して点Ｐを安全でないチャネル８１６に送る。
【０１４２】
受信側１２０２の暗号化／復号化手段１２０４は、回線８１０を介して楕円乗算器８０６に結合されている。楕円乗算器８０６は、回線８１２を介して秘密鍵ソース８０８に結合されている。数値ｕは、回線１２１２を介して安全でないチャネル８１６から楕円乗算器８０６に送られる。楕円乗算器８０６は、点Ｑを生成し、回線１２１６を介して比較器１２０８に送られる。ハッシュ生成器１２０６は、回線１２１０を介して安全でないチャネル８１６から暗号文メッセージＣおよび点Ｐを受信し、さらに回線１２１８を介してソース８１３からｏｕｒＰｕｂを受信する。ハッシュ生成器１２０６は、回線１２１４を介して点Ｒを比較器１２０８に出力する。
【０１４３】
送信側８０１の秘密鍵ソース８０７は、送信側の安全な秘密パスワード「ｏｕｒＰｒｉ」を含む。秘密鍵ソース８０７は、コンピュータ・システム内の記憶レジスタ、メッセージが送信されたときに送信側が暗号システムに送るパスワード、さらにはメッセージを送信または受信したときに図１２の暗号システムによって読み取られる符号化された物理的鍵であってもよい。同様に、受信側８０２の秘密鍵ソース８０８は受信側の安全な秘密パスワード「ｔｈｅｉｒＰｒｉ」を含む。
【０１４４】
別のソース８１３は、送信側１２０１と受信側１２０２の公開鍵「ｏｕｒＰｕｂ」および「ｔｈｅｉｒＰｕｂ」、初期点（ｘ1，ｙ1）、体Ｆpｋ、曲線パラメータａ、ｂ、ｃなどの公知の情報を格納する。この情報源は、コンピュータ・システムによって使用されるオンライン・ソースである、公開されているディレクトリであってもよく、また安全でない送信媒体上で送信側と受信側との間で送信することもできる。公開ソース８１３は図では、回線８１５を介して送信側１２０１に、また回線８１４と１２１８を介してそれぞれ受信側１２０２とハッシュ生成器１２０６に記号的に結ばれている。
【０１４５】
動作時に、前記のように送信側と受信側は安全な送信で暗号化および復号化鍵として使用するため１回限りの共通の暗号パッドを生成する。暗号化鍵を、平文メッセージとともに暗号化／復号化手段１２０３に送る。ＤＥＳ方式や本発明の楕円曲線方式などの暗号化方式とともに暗号化鍵を使用して、暗号文メッセージＣを生成する。乱数生成器１２０５は、乱数ｍを生成し、楕円乗算器８０５に送る。楕円乗算器８０５は、数値ｕを生成し、安全でないチャネル８１６を介して受信側に送る。暗号文メッセージＣは、乱数ｍとｏｕｒＰｒｉとともにハッシュ生成器１２０７に送られる。ハッシュ生成器１２０７は、点Ｐを生成し、安全でないチャネル８１６に送る。暗号文メッセージは、署名（ｕ，Ｐ）とともに、安全でないチャネル８１６上で受信側１２０２に送信される。
【０１４６】
受信側１２０２は、受信側の秘密鍵ｔｈｅｉｒＰｒｉを使用して復号化鍵ＤK を生成する、ｔｈｅｉｒＰｒｉが、送信側の公開鍵ｏｕｒＰｕｂ（公開ソース８１３からの）とともに、秘密鍵ソース８０８から楕円乗算器８０６に送られる。復号化鍵ＤK は、（ｔｈｅｉｒＰｒｉ）°（ｏｕｒＰｕｂ）（ｍｏｄ  ｐ）から生成される。復号化鍵ＤKは、楕円乗算機能の可換性のため、暗号化鍵ｅKに等しい。したがって、受信側１２０２は、復号化鍵ＤK を使用して暗号化方式を逆にし、暗号文メッセージＣから平文メッセージを復元する。
【０１４７】
受信側１２０２の楕円乗算器８０６は、安全でないチャネル８１６から数値ｕを受信する。楕円乗算器８０６は、点Ｑを生成し、比較器１２０８に送る。ハッシュ生成器は、安全でないチャネル８１６から暗号文メッセージＣと点Ｐ、ソース８１３から意図されている送信側の公開鍵ｏｕｒＰｕｂを受信して、点Ｒを生成し、点Ｒを比較器１２０８に送る。比較器１２０８は、点ＱとＲを比較し、一致している場合には、署名は有効であると仮定する。本発明では、前記のｘ値を使用して最適化されている方式により点ＱとＲの比較を実行する。
【０１４８】
送信側１２０１と受信側の１２０２の暗号化／復号化手段および楕円乗算器は、プログラム・ステップとして実装し、マイクロプロセッサ上で実行させることができる。
【０１４９】
直接埋め込み
本発明では、２つの曲線Ｅ±のうちの一方にテキスト・パーセルをマッピングできるという事実を利用している。受信側の公開鍵を使用し、送信側はメッセージ座標、手がかりの値および符号を生成し、３つ組として受信者側に送信する。手がかりと受信側の秘密鍵を使用して、メッセージ座標からテキスト・パーセルを復号化することができる。展開できない形では、送信側と受信側は自分の共有の暗号パッドを使用して、共有の手がかりを計算し、それぞれのメッセージ座標が１ビットの符号とともに送信されるようにする。
【０１５０】
前記の高速楕円代数を使用して生成した楕円曲線は、充分に特別なもの（つまり、密に定義されている）であり、平文の任意のパーセルが直接埋め込まれ、当然、可能な２つの曲線のうちの１つに埋め込まれる。この曲線を「＋」曲線および「−」曲線と呼んでいる。
【０１５１】
展開のない直接埋め込み
本発明をさらに精密化した場合、各３つ組の手がかり構成要素をなくすことにより暗号化されているパーセルのサイズを縮小することができる。これは、送信側と受信側との間で同期をとる際に手がかりを生成する手段を設定することにより実現される。たとえば、前記の直接埋め込みの方法を使用して、送信側から受信側に２つの乱数ｒ、ｓを安全に送信することができる。送信側は、第１の手がかりを
ｃｌｕｅ1＝ｒ°ｏｕｒＰｒｉ°ｔｈｅｉｒＰｕｂ
として計算し、同様に、受信側は同じ手がかりを
ｃｌｕｅ1＝ｒ°ｔｈｅｉｒＰｒｉ°ｏｕｒＰｕｂ
として計算する。
【０１５２】
後の手がかりは、次のように楕円加算を実行して両側に形成することができる。
ｃｌｕｅn+1＝ｃｌｕｅn＋ｓ°Ｐ
ただし、Ｐは曲線上の初期点である。
【０１５３】
直接埋め込みの場合のように、埋め込まれたメッセージ・パーセルの点Ｐtextはｃｌｕｅに楕円加算されて、メッセージ点を構成し、復元の手がかりｇを計算し、ただ１つのペア（ｍｅｓｓａｇｅ，ｇ）として送信される。
【０１５４】
楕円曲線演算
後述のように、直接埋め込まれた平文の送信側は１ビットを送信して、受信側で復号化できるようにどの曲線を使用するかを識別する。
【０１５５】
直接埋め込みという考えは、楕円曲線自体に平文のパーセルを埋め込むというものである。点Ｐtextを暗号化する平文のパーセルを含む曲線の点とする。前記の高速楕円曲線代数を使用することで、点のペアと単一ビットｇからなる３つ組を送信することができる。
（Ｐtext＋ｒ°ｔｈｅｉｒＰｕｂ，ｒ°Ｐ1，ｇ）
（実際、本来の曲線点のペアと１ビットではなく、送信するｘ座標のペアと１ビットだけが送信される）。ただし、ｒは乱数整数である。この送信を
（メッセージ、手がかり、パリティ）
として定性的に考える。
【０１５６】
「相手」側では、受信側は「手がかり」と「パリティ」およびその秘密鍵「ｔｈｅｉｒＰｒｉ」を使用して、「メッセージ」から平文を推論する。パリティ・ビットは、曲線の曖昧さと２次式の符号曖昧さに応じて全体的な符号の結果となる。
【０１５７】
テキストの直接埋め込みは、次の楕円曲線の関係を検討することにより理解される。
【０１５８】
ここでは、体Ｆpの場合に集中するが、ただし
ｐ＝２q−１
は、Ｍｅｒｓｅｎｎｅ数である。注目している楕円曲線をＥとすると、これは
ｓｙ2＝ｘ3＋ｃｘ2＋ｂｘ＋ａ
を満たす点Ｐ＝（ｘ，ｙ）εＦpＸＦpで構成されるように組み立てられるが、「無限遠点」Ｏとともに曲線の符号ｓは＋１または−１、およびｃ≠２のいずれかに制限される。実際の曲線点には太字を使用していることに注意されたい。つまり、ここまでの記法は、
ｘ、ｙは両方とも整数（ｍｏｄ  ｐ）である
曲線上の点Ｐはペア（ｘ，ｙ）である
または抽象的な「無限遠点」Ｏの場合もある
Ｅは、すべてのＰの集合である。
【０１５９】
強力な古典的結果がＨａｓｓｅの定理であり、曲線の位数｜Ｅ｜である、つまり点Ｐの総数は
【数２】
0003862500.tif 000004
が成立するという意味でｐ自体に近いということである。
【０１６０】
点の間にある種の演算が用意されている場合、楕円曲線Ｅは加法群になる。点Ｏは加法的な単位要素であるが、加法の群の公理は次のように働く。２つのＯでない点
Ｐ1＝（ｘ1，ｙ1）    Ｐ2＝（ｘ2，ｙ2）
について、曲線の加法を
Ｐ3＝Ｐ1＋Ｐ2＝（ｘ3，ｙ3）
で定義し、減法を
Ｐ4＝Ｐ1−Ｐ2＝（ｘ4，ｙ4）
で定義し、その際にＭｏｎｔｇｏｍｅｒｙパラメータ化ａ＝１、ｂ＝０の関係式
【数３】
0003862500.tif 000005
とともに、否定の規則
−Ｐ1＝（ｘ1，−ｙ1）
を使用している。
【０１６１】
そこで、ｘ1≠ｘ2について、和と差のｘ座標は、
【数４】
0003862500.tif 000006
を使用して、関係付けられることが導かれる。
【０１６２】
これらの定義済み関数Ｆ、Ｇは、直接埋め込みの理論で計算される。特にＧ関数は別に
【数５】
0003862500.tif 000007
と書くことができ、Ｑ関数は楕円曲線の定義２次形式、つまり
Ｑ（ｚ）＝ｚ2＋ｃｚ＋１
であることに注意されたい。
【０１６３】
楕円乗算はしご
実際の実装では、ｙ座標を無視する［Ｍｏｎｔｇｏｍｅｒｙ  １９８７］の逆変換のないパラメータ化を使用して、高速楕円曲線乗算を実行する。いくつかの点Ｐ＝（Ｘ1，ｙ）について、Ｐのｎ回乗算をＰのｎ個のコピーの楕円和として定義し、ｎ°Ｐと表す。（整数ｎ＝０の時、０°Ｐを抽象点０と解釈する。）そこで、Ｚ1 ＝１がわかっているとして、複数のｎ°Ｐのｘ座標をＸn／Ｚnと表す。整数Ｘn、Ｚnは、いくつかの加算−２倍規則に従って２進はしご法により評価することができる。これらの規則は前記の基本的な加法／減法の法則から導くことができ、上の式２１、２２、２３、および２４の形式をとる。
【０１６４】
Ｍｅｒｓｅｎｎｅ  ｍｏｄ演算
楕円乗算はしご法では、加算−２倍規則を通じて乗算−ｍｏｄ演算が関わる。これらの演算は、効率化することができる。さらに、鍵または暗号パッドを解決するために必要な単一の逆変換Ｚ-1も高速に実行できる。いずれにせよ、すべての算術演算は乗算、シフト演算、加算で実行することができ、そのため除算を使用しないシステムができあがる。
【０１６５】
高速Ｍｅｒｓｅｎｎｅ  ｍｏｄ演算は、上の式１７、１８、および１９に関して説明したように実行できる。逆（ｍｏｄ  ｐ）は、上述のように式１９に従って計算することができる。
【０１６６】
さらに、多項式ＧＣＤ法に基づく再帰的逆変換アルゴリズムもあり、これは実際に、ある小さな整数ｍについてＯ（ｑｌｏｇmｑ） の時間がかかる。逆変換の時間は、上述のような累積ＦＦＴ乗算手法と競合する。
【０１６７】
定理
次の定理は、本発明の直接埋め込み方式を補助するものである。
【０１６８】
定理１
楕円曲線Ｅ上の点Ｐと整数ｍ、ｎについて、
ｍｎ°Ｐ＝ｎｍ°Ｐ＝ｍ（ｎ°Ｐ）＝ｎ（ｍ°Ｐ）
が成り立つ。
【０１６９】
これは、可換性と結合性の規則を示している。
定理２
与えられたパラメータａ＝０、ｂ＝１、ｃ≠２について、任意の正数ｘは、２つの高速楕円曲線
Ｅ±：±ｙ2＝ｘＱ（ｘ）
の１つに存在するある点の有効なｘ座標である。
ｐはＭｅｒｓｅｎｎｅ数で、したがって＝３（ｍｏｄ  ４）なので、整数ｓ＝ｘＱ（ｘ）は平方またはその負の値であることに注意されたい。
【０１７０】
定理３
Ｐ1＝（ｘ1，ｙ1）、Ｐ2＝（ｘ2，ｙ2）とし、Ｐ3＝Ｐ1＋Ｐ2＝（ｘ3，ｙ3） と仮定する。このとき、ｘ3は、次の式を満たさなければならない。
ｘ1≠ｘ2の場合：２次関係式ｘ3（Ｇ（ｘ1，ｘ2）−ｘ3）＝Ｆ（ｘ1，ｘ2）2ａ
ｘ1＝ｘ2の場合：関係式ｘ3＝（ｘ12−１）2／４ｘ1Ｑ（ｘ１））
【０１７１】
定理４
Ｐ1＝（ｘ1，ｙ1）、Ｐ2＝（ｘ2，ｙ2）、ｘ1≠ｘ2とする。次のように表記する。
Ｐ3＝Ｐ1＋Ｐ2＝（ｘ3，ｙ3）
Ｐ4＝Ｐ1−Ｐ2＝（ｘ4，ｙ4）
このとき、ｘ3は次の２つの値のうちの１つである。
（ｘ1Ｑ（ｘ2）＋ｘ2Ｑ（ｘ1）±２（ｘ1Ｑ（ｘ1）ｘ2Ｑ（ｘ2））(p+1)/4）／（（ｘ1−ｘ2）2）
ただし、ｘ4は他の値である。
【０１７２】
上の定理３の２次関係式を解くと、
【数６】
0003862500.tif 000008
が得られる。
【０１７３】
ｐ＝３（ｍｏｄ  ４）について、ａの平方（ｍｏｄ  ｐ）の平方根は常にプラスまたはマイナスａ(P+1)/4（ｍｏｄ  ｐ）である。
【０１７４】
定理５
曲線Ｅ±の１つの上の任意の整数ｘ（ｍｏｄ  ｐ）について、正しい符号＋または−が次の式で成立するいずれかの符号により与えられる。
（ｘＱ（ｘ））(P+1)/2＝±ｘＱ（ｘ）（ｍｏｄ  ｐ）
ｘＱ（ｘ）が０であれば、＋曲線が使用される。
【０１７５】
直接埋め込みアルゴリズム
次のように仮定する。
パラメータｑ、ａ＝０、ｂ：＝±１、ｃ≠２で、２つの可能な楕円曲線Ｅ±が得られる。
２つの点
Ｐ1+＝（Ｘ1+，？）      Ｐ1-＝（Ｘ1-、？）
が曲線Ｅ±上にそれぞれ存在するような２つの公開されている初期ｘ座標Ｘ１±。ｙ座標（「？」で表されている）は、高速楕円代数を使用する場合には無視できる。
公開鍵のペアが存在している。ｔｈｅｒｉＰｕｂ±は
（ｔｈｅｉｒＰｕｂ±、？）＝ｔｈｅｉｒＰｒｉ°Ｐ1±
に従って、単一の秘密鍵ｔｈｅｉｒＰｒｉから生成される。
平文を、それぞれｑビット以下のパーセルに分ける。つまり、パーセルは値（ｍｏｄ  ｐ）である。
符号ｓを使用して上の定理４からまたはまれなケースであるｘ1＝ｘ2の場合は定理３から、ｘ3またはｘ4のうちの１つを計算する関数ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘ1，ｘ2，ｓ）が存在すること。
【０１７６】
平文パーセルｘtextを暗号化するには、次のようにする。
１．定理５からパーセルｘtextが有効なｘ座標である２つの曲線Ｅ±のうちのいずれかを決定する。前記曲線を符号ｓ＝±１で表す。
２．乱数ｒを選択し、前記のはしご算術演算を使用して（ｘq，？）：＝ｒ°（ｔｈｅｉｒＰｕｂ±，？）を計算する。
３．メッセージ座標ｘm：＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘtext，ｘq，＋１）を計算する。
４．乱数ｒを使用して手がかりｘcを計算し、公開点を（ｘc，？）：＝ｒ°Ｐ1±として計算する。
５．ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘm，ｘq，±１）＝ｘtext内で有効な符号を決定し、これを符号ｇとする。
６．メッセージ座標の３つ組、手がかり、および符号を送信側に（ｘm，ｘc，ｇ）として送信する。
【０１７７】
１パーセルの平文を復号化するには、次のようにする。
１．（ｘm，ｘq，ｇ）を受信すると仮定して、手がかりｘcを使用し、
（ｘq，？）＝ｔｈｅｉｒＰｒｉ°（ｘc，？）
からｘ座標ｘqを計算する。
２．次の式を使用して平文を復元する。
ｘtext＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘm，ｘq，ｇ）
【０１７８】
アルゴリズム３をソフトウェアで実現したものを本書巻末に付録コードとして添付した。実際の実施では、乱数整数楕円乗算（ｒによる）は定期的にしか実行しないので、実行時間が短縮する。事実、ｒの乗算は、たとえば定理４で具現化されているべき乗以上に実際にコストがかかることがわかっている。
【０１７９】
直接埋め込みの流れ図
図１３は、直接埋め込みを使用して平文メッセージを暗号化する流れ図である。ステップ１３０１で、平文をそれぞれｑビット以下のパーセルに分割する。各パーセルｘtextについて、ステップ１３０２で、２つの曲線Ｅ±のうちのどれに対してパーセルが有効なｘ座標であるかを決定する。これは、前記の定理５を使用して実行できる。ステップ１３０３で、しかるべき曲線を符号＝±１で表す。
【０１８０】
ステップ１３０４で、乱数ｒを選択する。ステップ１３０５で、（ｘq，？）＝ｒ°（ｔｈｅｉｒＰｕｂ±，？）を計算する。これは、はしご算術演算を使用して実行できる。ステップ１３０６で、メッセージ座標ｘmを計算する。これは、ｘm：＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘtext，ｘq，＋１）または他の適当な方法により実行できる。ステップ１３０７で、手がかりを計算する。これは、（ｘc，？）：＝ｒ°Ｐ1±で実行できる。
【０１８１】
ステップ１３０８で、ｘtextについて成立する符号をｇと定義する。この符号は、ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘm，ｘq，＋１）がｘtextに等しいかどうかをテストして決定することができる。ステップ１３０９で、メッセージ座標、手がかり、および符号を３つ組として（ｘm，ｘc，ｇ）という形式で受信側に送信する。
【０１８２】
図１４は、図１３の暗号化されたメッセージを復号化する流れ図である。ステップ１４０１で、送信側から３つ組（ｘm，ｘc，ｇ）を受信する。ステップ１４０２で、（ｘq，？）：＝ｔｈｅｉｒＰｒｉ°（ｘc，？）からｘ座標ｘqを計算する。次にステップ１４０３で、ｘtext：＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘm，ｘc，ｇ）により平文を復元することができる。
【０１８３】
拡張のない直接埋め込みアルゴリズム
一連の平文パーセルｘtextnを暗号化するには、次のようにする。
１．２つの乱数ｒ、ｓ∈Ｆpｋを選択して、たとえば、直接埋め込みアルゴリズムを使用して受信側に送信する。
２．式
ｃｌｕｅ＝ｒ°ｏｕｒＰｒｉ°ｔｈｅｉｒＰｕｂ±
ｓ＝ｓ°Ｐ±
を計算して、両方の曲線の初期手がかりを計算する。
３．平文パーセルｘtextiについて、２つの曲線のうちどれに関してｘtextiが有効な点か（またはｘtextiが有効な座標であるものはどれか）を決定する。
４．正しい曲線点を使用して、メッセージ座標
ｍi：＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘtexti，ｃｌｕｅi，＋１）
を計算する。
５．ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｍi，ｃｌｕｅi，±１）のどの符号でｘtextiを復元するかを決定し、この符号をｇとする。
６．ペア（ｍi，ｇ）を送信する。
７．後のパーセルについて、
ｃｌｕｅi+1＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｒ°ｃｌｕｅi，ｓ，＋１）
を計算し、ステップ３−６を繰り返す。
【０１８４】
一連のペア（ｍ，ｇ）を復号化するには、次のようにする。
１．乱数ｒ、ｓを復元し、初期手がかりを次のように計算する。
ｃｌｕｅ＝ｒ°ｔｈｅｉｒＰｒｉ°ｏｕｒＰｕｂ±
ｓ＝ｓ°Ｐ±
２．各ペア（ｍ，ｇ）について、どの曲線に点ｍがあるかを決定する。
３．決定された曲線から次の点に対する演算を使用して平文を復元する。
ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｃｌｕｅ，ｍ，ｇ）
４．後続のペアの手がかりを再計算する。
ｃｌｕｅi+1＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｒ°ｃｌｕｅi，ｓ，＋１）
【０１８５】
拡張なしの直接埋め込みの流れ図
図１５は、拡張なしの直接埋め込みを使用して平文メッセージを暗号化する流れ図である。ステップ１５００で、平文をそれぞれｑビット以下のパーセルに分割する。ステップ１５０１で２つの乱数ｒとｓを選択し、ステップ１５０２で受信側に送信する。ステップ１５０３で、乱数ｒとｓを使用して両方の曲線について初期手がかりｃｌｕｅとｓを決定する。
【０１８６】
ステップ１５０４で、それぞれのパーセルｘtextについて、送信側はパーセルが有効なｘ座標になるのは２つの曲線Ｅ±のうちどちらであるかを決定する。ステップ１５０５で、ｍi：＝ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｘtexti，ｃｌｕｅi，＋１）を使用してメッセージ座標を計算する。ステップ１５０６で、送信側は、ｅｌｌｉｐｔｉｃ＿ａｄｄ（ｍi，ｃｌｕｅi，±１）内のどの符号でｘtextiを復元するかを決定し、この符号をｇとする。
【０１８７】
ステップ１５０７で、現在のペア（ｍ，ｇ）を受信側に送信し、前の手がかりと乱数ｒとｓを使用してステップ１５０８で次の手がかりを計算する。ステップ１５０８の後で、プロセスはステップ１５０４に戻り、次のパーセルを暗号化する。
【０１８８】
図１６は、図１５の暗号化されているメッセージを復号化する流れ図である。ステップ１６００で、受信側は、受信側によって送信された乱数ｒとｓを復元し、ステップ１６０１で、乱数ｒとｓを使用して、初期手がかりを決定する。ステップ１６０２で、受信側は送信側が送信したペア（ｍ，ｇ）を復元する。現在のペア（ｍ、ｇ）について、ステップ１６０３で、受信側はどの楕円曲線に点ｍがあるかを決定する。決定された曲線の点を使用して、ステップ１６０４でｅｌｌｉｐｔｉｃ＿ａｄｄ（ｃｌｕｅ、ｍ，ｇ）を使って平文パーセルを復元する。ステップ１６０５で、前の手がかりおよび乱数ｒとｓに基づいて次の手がかりを計算する。ステップ１６０５の後で、プロセスはステップ１６０２に戻り、次のパーセルに取りかかる。
【０１８９】
コード
直接埋め込みを使用して暗号化と復号化を実装するコードで、Ｍａｔｈｅｍａｔｉｃａを使って書いたコード例を以下に示す。
【表１】
0003862500.tif 000009
【表２】
0003862500.tif 000010
【表３】
0003862500.tif 000011
【０１９０】
最適化された方式を使用して署名を比較する関数を以下に示す。
【表４】
0003862500.tif 000012
【０１９１】
Ｑを計算し、（Ｐ＋Ｍ（暗号文，Ｐ）°ｏｕｒＰｕｂ）と比較する関数を以下に示す。
【表５】
0003862500.tif 000013
【０１９２】
暗号化／復号化
本発明の暗号化／復号化方式は、プログラミング言語Ｃを用いて実装することができる。以下は、本発明の暗号化／復号化の実装に適したプログラム・インタフェース（．ｈファイル）とテスト・プログラム（．ｃファイル）の例である。
【表６】
0003862500.tif 000014
【表７】
0003862500.tif 000015
【表８】
0003862500.tif 000016
【表９】
0003862500.tif 000017
【０１９３】
【表１０】
0003862500.tif 000018
【表１１】
0003862500.tif 000019
【０１９４】
【表１２】
0003862500.tif 000020
【０１９５】
【表１３】
0003862500.tif 000021
【図面の簡単な説明】
【図１】  従来技術による公開鍵交換システムのブロック図である。
【図２】  従来技術による公開鍵交換トランザクションの流れ図である。
【図３】  本発明の鍵交換を説明する流れ図である。
【図４】  本発明を実装することが可能なコンピュータ・システムのブロック図である。
【図５】  Ｍｅｒｓｅｎｎｅ数を使用しｐを法とする算法を実行するシフトおよび加算演算を説明する図である。
【図６】  Ｆｅｒｍａｔ数を使用しｐを法とする算法を実行する動作を説明する図である。
【図７】  高速クラス数を使用しｐを法とする算法を実行する動作を説明する図である。
【図８】  本発明のブロック図である。
【図９】  本発明の一実施形態の動作を説明する流れ図である。
【図１０】  本発明を使用して電子署名を生成する方法を説明する流れ図である。
【図１１】  本発明における電子署名の認証を説明する流れ図である。
【図１２】  本発明の電子署名方式を実装するためのブロック図である。
【図１３】  直接埋め込みを使用して平文メッセージを暗号化する流れ図である。
【図１４】  図１３の暗号化されたメッセージを復号化する流れ図である。
【図１５】  展開なしの直接埋め込みを使用して平文メッセージを暗号化する流れ図である。
【図１６】  図１５の暗号化されたメッセージを復号化する流れ図である。
【図１】
0003862500.tif 000022
【図２】
0003862500.tif 000023
【図３】
0003862500.tif 000024
【図４】
0003862500.tif 000025
【図５】
0003862500.tif 000026
【図６】
0003862500.tif 000027
【図７】
0003862500.tif 000028
【図８】
0003862500.tif 000029
【図９】
0003862500.tif 000030
【図１０】
0003862500.tif 000031
【図１１】
0003862500.tif 000032
【図１２】
0003862500.tif 000033
【図１３】
0003862500.tif 000034
【図１４】
0003862500.tif 000035
【図１５】
0003862500.tif 000036
【図１６】
0003862500.tif 000037