Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
JP3862500B2 - 直接埋め込み方式による高速楕円曲線暗号化の方法と装置 - Google Patents
[go: Go Back, main page]

JP3862500B2 - 直接埋め込み方式による高速楕円曲線暗号化の方法と装置 - Google Patents

直接埋め込み方式による高速楕円曲線暗号化の方法と装置 Download PDF

Info

Publication number
JP3862500B2
JP3862500B2 JP2000503629A JP2000503629A JP3862500B2 JP 3862500 B2 JP3862500 B2 JP 3862500B2 JP 2000503629 A JP2000503629 A JP 2000503629A JP 2000503629 A JP2000503629 A JP 2000503629A JP 3862500 B2 JP3862500 B2 JP 3862500B2
Authority
JP
Japan
Prior art keywords
clue
value
elliptic
computer
elliptic curve
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
JP2000503629A
Other languages
English (en)
Other versions
JP2001510912A (ja
Inventor
クランダル,リチャード・イー
ガースト,ブレイン
Original Assignee
アプル・コンピュータ・インコーポレーテッド
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by アプル・コンピュータ・インコーポレーテッド filed Critical アプル・コンピュータ・インコーポレーテッド
Publication of JP2001510912A publication Critical patent/JP2001510912A/ja
Application granted granted Critical
Publication of JP3862500B2 publication Critical patent/JP3862500B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/727Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724Finite field arithmetic
    • G06F7/725Finite field arithmetic over elliptic curves
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3247Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures
    • H04L9/3249Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures using RSA or related signature schemes, e.g. Rabin scheme

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Computing Systems (AREA)
  • Computer Security & Cryptography (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Algebra (AREA)
  • Storage Device Security (AREA)
  • Computer And Data Communications (AREA)

Description

【0001】
これは、1991年9月17日出願の米国特許出願第761276号(現在は米国特許第5159632号として発行されている)の継続出願である1992年10月2日出願の米国特許出願第955479号(現在は米国特許第5271061号として発行されている)の継続出願である1993年12月14日出願の米国特許出願第167408号の一部継続出願である米国特許出願第484264号(現在は米国特許第5581616号として発行されている)の継続出願である米国特許出願第758688号の一部継続出願である。
【0002】
発明の背景
1.発明の分野
本発明は暗号化システムの分野に関するものである。
【0003】
2.背景技術
暗号化システムは、媒体上で送信側から受信側へメッセージを送信するためのシステムであって、メッセージが「安全」である、つまり対象となる受信側のみがメッセージを復元できるような媒体を使用する。暗号化システムは、「平文」と呼ばれるメッセージを「暗号文」と呼ばれる暗号化形式に変換する。暗号化は、「暗号鍵」つまり鍵を使用してメッセージを操作または変換することにより実行される。受信側は、暗号鍵または鍵を使用して操作または変換プロセスを反転することにより、メッセージを「復号化」する、つまり暗号文から平文に変換する。送信側と受信側のみが暗号鍵を知っている限り、このような暗号化された送信は安全である。
【0004】
「古典的」暗号システムは、暗号化情報を使用して復号化情報を決定することができる暗号システムである。セキュリティのために、古典的暗号システムでは暗号化鍵を秘匿し、安全なチャネル上でシステムのユーザに送る必要がある。秘密宅配便、盗聴防止機能付き電話伝送回線などの安全チャネルは多くの場合、非実用的で、高価である。
【0005】
安全暗号化鍵を交換する難しさをなくしたシステムのことを「公開鍵暗号化」と呼んでいる。定義により、公開鍵暗号システムは、メッセージを暗号化する方法を知っているだけでは計算に法外に長い時間をかけないと暗号化鍵を使用して復号化鍵を見つけられないという特性を持つ。暗号化機能としては、暗号化鍵が判明したら、暗号化機能を比較的容易に計算できるようなものを選択する。ただし、暗号化変換機能の逆の計算は困難であるか、または計算上実行不可能である。このような機能を「一方向機能」または「トラップドア機能」と呼ぶ。公開鍵暗号システムでは、鍵に関するある種の情報は公開される。この情報は、安全でない方法で公開または送信されることがあり、またそうされることが多い。さらに、鍵に関するある種の情報は秘密にされる。この情報は、プライバシー保護のため安全なチャネル上で配布することができる(あるいは、プライバシー確保のためローカル・ユーザが作成することもできる)。
【0006】
代表的公開鍵暗号化システムのブロック図を図1に示す。破線100内のブロックで表される送信側が、平文メッセージPtxtを、破線115内のブロック図で表される受信側に送信する。平文メッセージは、暗号文メッセージCに暗号化され、何らかの送信媒体上で送信され、受信側115によって復号化され、平文メッセージPtxtが再現される。
【0007】
送信側100は、暗号化デバイス101、安全鍵ジェネレータ102、および鍵ソース103を備える。鍵ソース103は、回線104を介して安全鍵ジェネレータ102に接続されている。安全鍵ジェネレータ102は、回線105を介して暗号化デバイス101に結合されている。暗号化デバイスは、回線106上に暗号文出力Cを送る。安全鍵ジェネレータ102は、回線107上に鍵出力を出す。この出力は、暗号文メッセージ106とともに、送受信機109に送られる。送受信機109は、たとえば、モデムなどのコンピュータ送信デバイスや、無線周波送信信号を送信するためのデバイスであってもよい。送受信機109は安全でないチャネル110上で安全鍵と暗号文メッセージを受信側の送受信機111に出力する。
【0008】
受信側115も、暗号化デバイス116、安全鍵ジェネレータ117、および鍵ソース118を備える。鍵ソース118は、回線119上で安全鍵ジェネレータ117に結合されている。安全鍵ジェネレータ117は、回線120上で暗号化デバイス116に結合されている。暗号化デバイス116は、回線121を介して送受信機111に結合されている。安全鍵ジェネレータ117は、回線122および123上で送受信機111に結合されている。
【0009】
動作中に、送信側100には、受信側115に送信する平文メッセージPtxtがある。送信側100と受信側115は両方とも、それぞれ、同じ暗号化方式を使用する暗号化デバイス101と116を備える。暗号化デバイスに実装できる適当な暗号システムがいくつかある。たとえば、データ暗号化標準(DES)や他の適当な暗号化方式を実装することができる。
【0010】
送信側と受信側はさらに、それぞれ、安全鍵ジェネレータ102および117を備える。これらの安全鍵ジェネレータは、複数のよく知られている公開鍵交換方式のうちの1つを実装している。後述するこれらの方式は、Diffie−Hellman方式、RAS方式、Massey−Omura方式、およびElgamal方式を含む。
【0011】
送信側100は、鍵ソース103を使用して秘密鍵を生成するが、この鍵ソースは乱数ジェネレータであってよい。秘密鍵が安全鍵ジェネレータ102に提供され、これを使用して暗号化鍵eKを生成する。暗号化鍵eKは回線105上で暗号化デバイスに送信され、これを使用して、平文メッセージPtxtを暗号化し、回線106上に用意される暗号文メッセージCを生成して送受信機109に送る。安全鍵ジェネレータ102はさらに、安全鍵を鍵ソース103から暗号化鍵eK に変換するために使用される情報も送信する。この情報は、秘密鍵を知らずにこの情報から暗号化鍵を再現するのは実際上不可能なので、安全でないチャネル上で送信することができる。
【0012】
受信側115は、鍵ソース118を使用して、秘密鍵および安全鍵119を生成する。この秘密鍵119は、復号化鍵DK を生成するために送信側100によって用意される鍵生成情報とともに安全鍵ジェネレータ117で使用される。この復号化鍵DK は、回線120上で暗号化デバイス116に送られ、そこで、これを使用して暗号文メッセージを復号化し、元の平文メッセージを再現する。
【0013】
Diffie−Hellman方式
DiffieとHellmanの論文「New Directions in Cryptography」、IEEE Trans.Inform.Theory、vol.IT−22、pp.644−654、1976年11月(「DH」方式)で公開鍵交換の方式が述べられている。DH方式では、離散指数および対数関数に基づく公開鍵システムを記述している。「q」を素数、「a」を原始元とすると、1≦X、Y≦(q−1)の範囲のXとYについて1対1の関係があり、有限体上でY=aX mod q、かつX=loga Yを満たす。第1の離散指数関数は与えられたaおよびXについて容易に評価できるため、公開鍵Yの計算に使用される。Diffie−Hellmanシステムのセキュリティは、与えられたXおよびYについて離散対数関数X=logaYを解く汎用の高速アルゴリズムが知られていないという事実に依っている。
【0014】
Diffie−Hellmanシステムでは、公開鍵のディレクトリが公開されるか、もしくは何らかの手段で一般に利用できるようにされる。与えられた公開鍵はユーザにしか知られていない関連付けられた秘密鍵に依存している。しかし、公開鍵から秘密鍵を決定することは実質的に不可能である。たとえば、送信側が「myPub」という公開鍵を持つとする。受信側は「theirPub」という公開鍵を持つとする。送信側はさらに、「myPri」という秘密鍵を持つ。同様に、受信側も、「theirPri」という秘密鍵を持つ。
【0015】
公開鍵システムでは多数の要素が公に知られている。Diffie−Hellmanシステムの場合には、これらの要素は、素数pと原始元gを含む。pとgは両方とも、公に知られている。公開鍵を生成するには、(mod p)に関してgに秘密鍵指数を累乗する。たとえば、送信側の公開鍵myPubは次の式で生成される。
myPub=gmyPri(mod p) 式(1)
【0016】
同様に、受信側の公開鍵は次の式で生成される。
theirPub=gtheirPri(mod p) 式(2)
【0017】
公開鍵は、指数演算と剰余演算(modulo arithmetic) を使って容易に作成できる。前記のように、公開鍵は一般の人々が容易に入手することができる。つまり、公開され、配布されている。さらに、安全でないチャネル上で送信することもできる。公開鍵が知られていても、離散対数問題を解くのは困難であるため、逆関数によって秘密鍵を計算することは非常に難しい。
【0018】
図2は、Diffie−Hellman型システムを使用した鍵交換の例の流れ図である。ステップ201で、素数pを選択している。この素数pは、公開されている。次に、ステップ202で、原始根gを選択している。この数gも公に知られている。ステップ203で、暗号化鍵eKを生成し、受信側の公開鍵(theirPub)を底、送信側の秘密鍵(myPri)を指数とするべき乗を計算する。つまり、次のようになる。
(theirPub)myPri(mod p) 式(3)
【0019】
すでにtheirPubは、gtheirPri(mod p)に等しいと定義している。したがって、式(3)は次の式で求められる。
(gtheirPrimyPri(mod p) 式(4)
【0020】
この値が、平文メッセージを暗号化し、暗号文メッセージを作成するために使用される暗号化鍵eKである。メッセージを暗号文にする、あるいは暗号化する特定の方法は、よく知られているいくつかの方法のうちの1つであってよい。どの暗号化メッセージを使用するにせよ、暗号鍵は式4で計算した値である。その後ステップ204で、暗号文メッセージが受信側に送信される。
【0021】
ステップ205で、受信側は、送信側の公開鍵(myPub)を底、受信側の秘密鍵(theirPri)を指数とするべき乗を計算して次のように復号化鍵DKを生成する。
K=(myPub)theirPri(mod p) 式(5)
【0022】
式1から、myPubはgmyPri(mod p)に等しい。したがって、
K=(gmyPritheirPri(mod p) 式(6)
【0023】
(gABは(gBAに等しいので、暗号化鍵eKと復号化鍵DKは同じ鍵である。これらの鍵を「一回の暗号パット」と呼ぶ。一回の暗号パットは、メッセージの暗号化および復号化に使用される鍵である。
【0024】
受信側は単に、ステップ206で平文メッセージを復元するために復号化鍵を使用して変換アルゴリズムまたは暗号化方式の逆を実行するだけである。送信側と受信側の両方が暗号化鍵の生成にその秘密鍵を使用しなければならないため、他のユーザは暗号文メッセージを読んだり、復号化したりできない。ステップ205はステップ201〜204よりも前またはそれと同時に実行できることに注意されたい。
【0025】
RSA
Rivest、Shamir、およびAdelmanらの論文「On Digital Signatures and Public Key Cryptosystems」,Commum.Ass.Comput.Mach.,vol.21,pp.120−126,Feb.1978(「RSA」方式)では他の公開鍵暗号システムを提案している。RSA方式は、非常に大きな2つの素数を生成し、それらを掛け合わせることが簡単にできるという事実に基づいているが、その結果を因数分解する、つまりその積から非常に大きな素数を求めることはきわめて困難である。したがって積は、復号化鍵を効果的に構成する素数を損なうことなく暗号化鍵の一部として公開することができる。
【0026】
RSA方式では、鍵生成アルゴリズムを使用して2つの大きな素数pおよびqを選択し、それらを掛け合わせてn=pqを求める。数pおよびqは、数百桁の長さになりうる。次に、Eulerの関数をφ(n)=(p−1)(q−1)として計算する(φ(n)は、1からnまでの範囲の整数値で、nと公約数を持たない)。φ(n)は0からn−1までの範囲の任意の整数aと、整数kについて、akφ(n)+1=a(mod n)となる特性を持つ。
【0027】
1からφ(n)−1の範囲で、φ(n)との公約数を持たない乱数Eを選択する。乱数Eは、暗号化鍵であり、公開されている。そこで、2つの数の最大公約数を計算するEuclidのアルゴリズムの拡張バージョンを使用してD=E-1(mod φ(n))を簡単に計算できる。Dは復号化鍵であり、秘密にしておく。
【0028】
情報(E,n)を暗号化鍵として公開し、これを使って暗号化されていない平文メッセージを暗号文メッセージに次のように変換する。まずメッセージをそれぞれ0からn−1までの範囲の整数列として表す。Pをそのような整数とする。次に、関係式C=PE(mod n)により対応する暗号文整数を与える。情報(D,n)を復号化鍵として使用し、P=CD(mod n)を介して暗号文から平文を復元する。これらは、CD=PED=pkφ(n)+1=Pなので、逆変換である。
【0029】
MASSEY−OMURA
Massey−Omura暗号システムは、米国特許第4567600号に記述されている。Massey暗号システムでは、有限体Fqを選択する。体Fqは固定であり、公に知られている体である。送信側と受信側はそれぞれ最大公約数G.C.D.(e,q−1)=1となるような0からq−1の範囲の乱数整数eを選択する。次に、ユーザはEuclidアルゴリズムを使用してその逆D=e-1(mod q−1)を計算する。したがって、De=1(mod q−1)となる。
【0030】
Massey−Omura暗号システムでは、安全な送信を実現するために3つのメッセージを送信する必要がある。送信者Aは受信者BにメッセージPを送信する。送信者Aは乱数eAを計算し、受信者Bは乱数eBを計算する。送信者はまず、受信者に要素Pe Aを送信する。受信側はeA を知らないのでPを復元できない。その代わりに、受信側はその要素を底、自分の秘密鍵eB を指数とするべき乗を計算し、第2のメッセージPe A e Bを送信側に返信する。次に、送信側はその要素を底、DA-thを指数とするべき乗を計算してeAの効果を除去し、Pe B を受信者Bに返信する。受信者Bは、その要素を底、DB-thを指数とするべき乗を計算してこのメッセージを読むことができる。
【0031】
ELGAMAL暗号システム
ElGamal公開鍵暗号システムでは公に知られている有限体FqとF* q の要素gを使用する。それぞれのユーザは0>a>q−1の範囲の整数aを無作為に選択する。整数aは秘密復号化鍵である。公開暗号化鍵はF* qの要素ga である。Pで表されているメッセージをユーザAに送信するために、整数Kを無作為に選択している。Fqの要素のペア、つまり(gK,PgaK)がAに送信される。平文メッセージPtxtが鍵gaKによって暗号化される。値gK は平文メッセージPtxtを決定するための受信側の「手がかり」である。しかし、この手がかりは安全な復号化鍵「a」を知っている人しか使用できない。受信者Aは、「a」を知っており、第1の要素gKを底、aを指数とするべき乗を計算して、(gKaを求め、その結果を第2の要素に除算することにより、このペアからメッセージPを復元する。
【0032】
楕円曲線
他に「楕円曲線」暗号システムと呼ばれる公開鍵暗号システムもある。楕円曲線暗号システムは、有限体F上で定義された楕円曲線Eの点に基づいている。楕円曲線暗号システムは、セキュリティに関して、離散対数問題を解くのが困難であるという事実に依存している。楕円曲線暗号システムの利点は、有限体を選択するよりも楕円曲線を選択するほうが自由度が高いという点である。しかしながら、楕円曲線暗号システムは、多量の計算を必要とすることからコンピュータ・ベースの公開鍵交換システムでは広く使用されるにいたっていない。コンピュータ・ベースの楕円曲線暗号システムは、他のコンピュータ公開鍵交換システムに比べて低速である。楕円曲線暗号システムは、「A Course in Number Theory and Cryptography」(Koblitz著、1987年、Springer−Verlag、New York)に記述がある。
【0033】
現在まで、楕円曲線方式は鍵交換と認証に使用されてきた。しかしながら、楕円曲線代数を暗号化方式自体として使用するにあたって適当な方式が提案されていない。
【0034】
発明の要旨
本発明は、平文を直接、楕円曲線上の点として暗号化する手段を提示するものである。このような楕円曲線代数を使用する直接埋め込み法では、いわゆるDES段などの中間暗号生成器段を回避している。本発明で埋め込みが容易になるのは、pをp=2q−C=3(mod 4)となる素数としたときに、有限体Fp上の楕円曲線パラメータ化を選択した結果である。整数qとCの選択では、pを素数とし、高速な算術演算を実行できるようにC(負の場合もある)を十分小さくとっている。
【0035】
平文を2つの関係する曲線のうちの1本の上の点として直接取り扱えるのは、p=3(mod 4)となるように素数pを選択したからである。平文点を含む曲線を選択するプロセスのことをここでは、「直接埋め込み」と呼ぶ。直接埋め込みを使用すると、通常であれば込み入ったプロセスとなるKoblitz他の非決定論的アルゴリズムを回避できる。
【0036】
2つの動作モードがあり、第1のモードは予備ステップとして第2のモードで使用される。E+および捻れE-と表記された2つの楕円曲線、これらの曲線P1 +とP1 -上の初期点、それぞれ初期点と秘密鍵theirPriおよびourPriから楕円乗算で導かれるtheirPub+、theirPub-とourPub+、ourPub-の両方に対する公開鍵点があると仮定する。0からp−1までの範囲の1パーセルの平文xtextを選択する。E+またはE-にx座標xtextの点が含まれているかどうかを調べる。乱数rを選択し、これを使用して、適切な公開点theirPub-の楕円曲線乗算によりその曲線上に新しい座標xqを生成する。楕円曲線上の2点の加算と減算の両方のx座標を計算できるが、どの結果がどの演算に対応しているかを区別しないelliptic_add演算を仮定する。
点xtextとxqのelliptic_add演算を実行し、2つの結果のうちの1つを選択して、暗号化メッセージ点xm(たとえば、xmはxtext+xqまたはxtext−xqのいずれか)を生成する。xtextとxqに対してelliptic_addの逆演算を実行し、結果のどれにより演算が逆になるか(xm+xqまたはxm−xqからxtextが明らかになる)を判別し、選択をgと表す。手がかりxcを乱数rと適切な初期公開点P±の楕円乗算により生成する。3つ組(xm ,g,xc)を受信側に送信する。受信側はxcとtheirPriの楕円乗算によりxq を計算し、さらにxmとxqに対してelliptic_addを計算し、gを使用して結果xmを選択する。xmのx座標は平文の元のパーセルである。
【0037】
第2の動作モードを使用すると、たとえば第1のモードで2つの乱数rとsを送信することにより送信者と受信者との間に同期乱数ジェネレータを設定してそれぞれの暗号化されたパーセルのサイズを縮小することができる。第1の同期している手がかりは、送信側ではtheirPub± とourPriおよびrとの連続楕円乗算、受信側ではourPubとtheirPri± およびrとの連続楕円乗算によって構成される。連続する手がかりxcluenは、手がかりxcluen-1に対するelliptic_add演算の第1の結果と初期点P1 ±とsの楕円乗算で構成される点を選択することで構成される。次に、第1にどの曲線に点xtextが含まれているかを判別し、xtextとxcluen のelliptic_addの第1の結果でxmを構成し、さらにxmおよびxcluen に対するelliptic_addの結果におけるxm の位置をgと記することで平文のそれぞれのパーセルを暗号化する。ペア(xm ,g)が受信側に送信される。受信側はどの曲線がxmに属し、xmおよびxcluen に対してelliptic_addを実行するかを判別し、gを使用して2つの結果から元のメッセージ・パーセルxm を選択する。
【0038】
発明の詳細な説明
楕円曲線暗号化方式について説明する。以下の説明では、本発明を完全に理解できるように、ビット数、実行時間など多くの具体的内容を詳細に取りあげている。しかし、本発明は、こうした具体的内容を示さなくても実施可能であることは当業者には明白なことであろう。他に、本発明をわかりにくくするのを避けるため、よく知られている機能については詳細に説明しなかった。
【0039】
従来技術によるコンピュータ実装楕円曲線暗号化方式の欠点は、他の従来技術によるコンピュータ実装暗号化方式に比べて満足な速度を達成できないという点である。従来技術による楕円曲線暗号システムで必要なモジュロ演算と楕円曲線代数演算は、除算の実行を必要とする。除算があると、コンピュータのCPU(中央処理装置)の計算オーバーヘッドが増大する。CPUは、除算よりも、加算と乗算を高速に、しかも少ない処理ステップで実行できる。したがって、従来技術による楕円曲線暗号システムは、これまで、Diffie−HellmanおよびRSA方式などの他の従来技術による暗号システムに比べて実用的あるいは望ましいものとなっていなかった。
【0040】
本発明は、明示的な除算を必要としない公開鍵交換の楕円曲線暗号システムを実装する方法と装置を提供する。本発明の好ましい実施形態の利点は、数の高速クラス、逆変換のないパラメータ化、FFT乗算剰余演算(multiply mod operation)を実装することにより実現できる。
【0041】
楕円曲線代数
本発明で使用する楕円曲線は、
2=x3+cx2+ax+b 式(7a)
または
−y2=x3+cx2+ax+b 式(7b)
を満たす点(x,y)εFpkXFpkと「無限遠点」Aから成り立っている。
【0042】
上の式でb=0かつa=1と置いた、
±y2=x3+cx2+x 式(7c)
は、「Montgomeryパラメータ化」と呼ばれるもので、後で説明のため使用し、
上の式でc=0とした、
±y2=x3+ax+b 式(7d)
は、Weierstrassパラメータ化と呼ばれるもので、これもまた後で説明のため使用する。
【0043】
送信側(「our」)と受信側(「their」)の秘密鍵は整数であると仮定し、
ourPri、theirPriεZ
と表記する。
【0044】
次に、送信側と受信側の両方にパラメータを設定する。パラメータは、次のとおりである。
p=2q−Cが高速クラス数(qは「ビット深さ」)となるようなq。値qは、公に知られている値である。
pkが体となるpとk。素数pと整数kは公に知られている数である。
公に知られている、初期x座標である(x1,y1)εFpk。
すべて公に知られている、整数曲線定義パラメータである(a,b,c)εFpk。
【0045】
本発明では、「楕円乗算」と呼ばれ、記号「°」で表される演算を使用する。楕円乗算の演算は文献でもよく知られており、本特許で、次のように式7dのWeierstrassパラメータ化を使用して説明する。Montgomeryパラメータ化などの他のパラメータ化についても類似の規則が得られる。
【0046】
式7dの曲線上に初期点(X1,Y1)を定義する。整数nの集合について、式n°(X1,Y1)は、加算および2倍の規則と呼ばれる、次の関係式により求められる点(Xn,Yn)を表す。
n+1=((Yn−Y1)/(Xn−X1))2−X1−Xn 式(8)
n+1=−Y1+((Yn−Y1)/(Xn−X1))(X1−Xn+1) 式(9)
【0047】
(X1,Y1)=(Xn,Yn)のとき、使用する2倍関係は、
n+1=((3X1 2+a)/2Y12−2X1; 式(10)
n+1=−Y1+((3X1 2+a)/2Y1)(X1−Xn+1) 式(11)
【0048】
算術演算は体Fpk上で実行されるので、すべての(mod p)が実行される。特に、式8から11の除算は逆(mod p)を伴う。
【0049】
Weierstrass以外のパラメータ化は簡単に公式化できる。
【0050】
楕円曲線公開鍵交換
送信側と受信側は両方とも前記の同じパラメータのセットを使用する必要がある。送信側と受信側は共に、楕円曲線上の特定のx座標として共有暗号パッドを生成する。
【0051】
以下の説明では、「自分」および「自分側」という用語で送信側を示す。「相手」および「相手側」という用語で受信側を示す。この規約を使用するのは、本発明の鍵交換は1人または複数の送信者と1人または複数の受信者との間で実行可能だからである。そのため、「自分」および「自分側」と「相手」および「相手側」はそれぞれ1人または複数の送信者と受信者を指している。
【0052】
本発明の楕円曲線暗号システムの公開鍵交換を図3の流れ図に説明してある。
【0053】
ステップ301−自分側で、公開鍵を計算する。ourPubεFpkXFp
ourPub=(ourPri)°(x1,y1) 式(12)
【0054】
ステップ302−相手側で、公開鍵を計算する。theirPubεFpkXFp
theirPub=(theirPri)°(x1,y1) 式(13)
【0055】
ステップ303−2つの公開鍵ourPubとtheirPubが公開され、したがってすべてのユーザに知られる。
【0056】
ステップ304−暗号パッドを自分側で計算する。ourPadεFpkXFp
ourPad=(ourPri)°(theirPub)=(ourPri)°(theirPri)°(x1,y1) 式(14)
【0057】
ステップ305−相手側で、暗号パッドを計算する。theirPadεFpkXFp
theirPad=(theirPri)°(ourPub)=(theirPri)°(ourPri)°(x1,y1) 式(15)
【0058】
楕円曲線上の点は、上記の加算および2倍演算のもとでアーベル群をなす。したがって、式14と15の演算の順序は、式の結果に影響を与えることなく入れ替えることができる。したがって、
ourPad=(ourPri)°(theirPri)°(x1,y1)=(theirPri)°(ourPri)°(x1,y1)=theirPad 式(16)
【0059】
送信側と受信側は両方とも、同じ暗号パッドを使用しているので、送信側が暗号化したメッセージを受信側で復号化することができる。(ステップ305はステップ301−304のどれかよりも前または同時に実行できることに注意されたい)。
【0060】
ステップ306では、送信側はourPadを使用して平文メッセージPtxtを暗号化し、暗号文メッセージCを受信側に送信する。ステップ307で、受信側はtheirPadを使用して、暗号文メッセージCを復号化し、平文メッセージPtxtを復元する。
【0061】
高速クラス数
楕円曲線暗号システムでは、モジュロ演算を使用して公開鍵、1回限りの暗号パッドなどのある種のパラメータを決定する。モジュロ演算は、式の結果の中のビット数を一定の数に制限し、セキュリティを実現するという2つの目的に使用される。離散対数問題は、モジュロ演算を使用しているため一部非対称である。モジュロ演算の欠点は、除算を実行する必要があるという点である。モジュロ演算の解は、数値を一定の数で除算したときの余りである。たとえば、12 mod 5は2に等しい。(12を5で割ると商は2で余りは2になり、余り2が解となる)。したがって、モジュロ演算では除算が必要である。
【0062】
本発明では特別な高速クラスの数を使用し、除算をなくすことで、暗号化と復号化で必要なモジュロ演算を最適化している。本発明で使用するクラスの数は一般に、Cを奇数で、比較的小さな値とし(たとえば、コンピュータのワード長以下)、C=1(mod 4)とした場合の2q−Cという形式で記述される。
【0063】
数値がこの形式であれば、モジュロ演算は、シフト、簡単な乗算、および加算のみを使い、除算を使わずに、実行することができる。この高速クラスの一群に、Mersenne数と呼ばれる数があり、2q −1という形式である。本発明で使用できる他のクラスは、Fermat数と呼ばれるもので、2q +1という形式であり、qは2m に等しい。Fermat数は、本発明では素数でも素数でなくてもよい。
【0064】
本発明では、有限体Fpk上の楕円曲線代数を使用するが、ただしp=2q−Cで、かつpは高速クラス数である。式p=2q −CによってqとCのすべての値について素数が得られるわけではないことに注意されたい。たとえば、qが4に等しく、Cが1に等しい場合、2q−Cは15に等しいが、これは素数ではない。しかし、qの値が2、3、または5で、C=1であれば、式2q −Cは素数3、7、および31を生成する。
【0065】
本発明では、有限体Fpk上に楕円曲線代数を実装する。ただしpは2q−Cで、高速クラスの数の要素である。データの2進表現を使用してコンピュータ上で実行する場合、高速クラスの数を使用することでシフト演算と加算のみにより(mod p)演算を実現できる。それとは対照的に、「低速な」数を使用した場合には、時間のかかる除算を実行して(mod p)演算を実行する必要がある。以下の例では、高速クラスの(mod p)演算の利点を示している。
【0066】
例1:基数10(mod p)除算
32ビットの2進数nとして、11101101111010111100011100110101(基数10では、この数値は3,991,652,149である)を考える。
【0067】
そこで、n(mod p)を考え、pを127に等しいとする。式n mod 127は除算では次のように計算できる。
【数1】
Figure 0003862500
【0068】
余り112がn mod 127の解である。
【0069】
例2:Mersenne数(mod p)演算
本発明では、pがMersenne数で、p=2q−1の場合、(mod p)演算は、除算を使用せずに、シフト演算と加算だけで実行できる。再びn(mod p)を考え、nは3,991,652,149で、pは127であるとする。pが127であれば、p=2q−1からqは7に等しい。127=27−1=128−1=127である。
【0070】
(mod p)演算は、nの2進数形式、つまり11101101111010111100011100110101を使用して実行できる。図5では、まずnのq個の下位ビット(LSB)501、つまり0110101をラッチしてシフト演算と加算を実行する。残りの桁のq個のLSB 502つまり、0001110をq個の桁501に加算し、和503(1000011)を得る。nの次のq個のLSB 504(0101111)を和503に加算して、和505(1110010)を生成する。nのビット506(1101111)を和505に加算し、和507(11100001)を得る。
【0071】
残りのビット508(1110)は、ビットよりも数が少ないが、和507に加算して、和509(11101111)を生成する。この和のビット数はqよりも多い。したがって、第1のqビット510(1101111)と次のqビット511との和をとり(この場合単一ビット1)、和512(1110000)を生成する。この和は、ビット数がq以下であり、n(mod p)の解である。1110000=26+25+24=64+32+16=112。
【0072】
したがって、n mod 127の解112は、Mersenne数の体上の楕円曲線を使用する場合にシフト演算と加算のみで決定される。Mersenne数を楕円曲線暗号システムで使用すると、明示的な除算が不要になる。
【0073】
例3:Fermat数(mod p)演算
本発明では、pがFermat数で、p=2q +1であれば、(mod p)演算は、除算を使用せずに、シフト演算、加算、および減算(負の加算)のみで実行できる。再びn(mod p)を考え、nを3,991,652,149、pを今度は257とする。pが257だと、qはp=2q+1から8に等しく、257=28+1=256+1=257となる。
【0074】
(mod p)演算は、nの2進数形式、つまり11101101111010111100011100110101を使用して実行できる。図6では、シフト演算と加算はまずq(8)個の下位ビット(LSB)601(00110101)をラッチすることで実行される。残りの桁の次のq個のLSB602、つまり11000111をq桁601から減算する。これを実行するために、ビット602の1の補数を生成し、1をMSB側に加算して、負数とし、ビット602’(100111000)を得る。この負数602’をビット601に加算して、結果603(101101101)を生成する。nの次のq個のLSB604(11101011)を和603に加算して、結果605(1001011000)を生成する。nのビット606(11101101)を結果605から減算する。したがって、ビット606の1の補数が生成され、1の負の符号ビットがMSB側に加算され、ビット606’(100010010)が生成される。ビット606’が結果605に加算されて、和607(1101101010)を生成する。
【0075】
和607のビット数はqよりも多いので、q個のLSBはビット608(01101010)としてラッチされる。次のqビット(この場合、2ビットのみ、11)をビット608に加算し、和610(01101101)を生成する。この和は、ビット数が以下であり、n(mod p)の解である。01101101=26+25+23+22+20=64+32+8+4+1=109。
【0076】
例4:高速クラスmod演算
本発明では、pがクラスp=2q −Cの数で、Cが奇数であり、比較的小さい値(たとえば、2進ワードの長さ以下)の場合、(mod p)演算は、除算なしでシフト演算と加算のみを使用して実行できる。再びn(mod p)を考え、nが685、pが13であるとする。pが13のとき、p=2q −Cから、qは4に等しく、Cは3に等しい。13=24−3=16−3=13である。
【0077】
(mod p)演算は、nの2進数形式、つまり1010101101を使用して実行できる。図7において、まずnのq(4)個の下位ビット(LSB)701、つまり1101をラッチしてシフト演算と加算を実行する。残りのビット702(101010)にC(3)を掛けると、積703(1111110)が生成される。積703をビット701に加算して、和704(10001011)を生成する。和704のq個の下位ビット705(1011)をラッチする。残りのビット706(1000)にCを掛けて、積707(11000)を生成する。積707をビット705に加算して、和708(100011)を生成する。和708のq個の下位ビット709(0011)をラッチする。残りのビット710(10)にCを掛けて、積711(110)を生成する。積711をビット709に加算して、和712(1001)を生成する。和712は、ビット数がq以下であり、n(mod p)の解である。1001=23+20=8+1=9である。685を13で割ると、余りは9となる。この高速クラス算術演算では、シフト演算、加算、および乗算のみを使用して解を求めることができる。
【0078】
シフト演算と加算の実施
高速Mersenne mod演算は、よく知られているシフト手順により実現できる。p=2q−1の場合、
x=(x&p)+(x>>q) 式(17)
を数回使用して、0からp−1までの区間で正のxを適切な剰余値にすることができる。この手順では、シフト演算と加算のみが必要である。それとは別に、数値x(mod p)を、
x=a+b2(q+1)/2=(a,b) 式(18)
で表すことができる。
【0079】
他の整数yを(c,d)と表すと、
xy(mod p)=(ac+2bd,ad+bc) 式(19)
が得られ、その後、xyの正しい簡約された剰余値を得るためにいくつかの自明なシフト−加算の演算が必要になる場合がある。
【0080】
逆(mod p)を計算するために、少なくとも、2通りの手順がある。1つは、古典的な拡張GCD手順の2進数形式を使用するものである。もう1つは、関係簡約方式を使用するものである。関係簡約方式は次のように動作する。
【0081】
p=2q−1、x≠0(mod p)とし、
-1(mod p)を返す。
1)Set(a,b)=(1,0)and(y,z)=(x,p);
2)If(y==0)return(z);
3)Find e such that 2e//y;
4)Set a=2q-ea(mod p);
5)If(y==1)return(a);
6)Set(a,b)=(a+b,a−b)and(y,z)=(y+z,y−z);
7)Go to(2).
【0082】
2進数拡張GCD手順は、a/bを超えない2の最大べき乗と定義される演算[a/b]2により、明示的な除算を使用せずに実行できる。
【0083】
pを与え、x≠0(mod p)とし、
-1(mod p)を返す。
1)If(y==1)return(1);
2)Set (x,v0)=(0,1)and(u1,v1)=(p,x);
3)Set u0=[u1/v12
4)Set (x,v0)=(v0,x_u00)and(u1,v1)=(v1,u1_u01
5)If(v1==0)return(x);else go to(3).
【0084】
本発明は、従来のまたは汎用コンピュータ・システムで実施することができる。本発明を実施するためのコンピュータ・システムの一実施形態を図4に示す。キーボード410およびマウス411が双方向システム・バス419に結合されている。キーボードとマウスは、ユーザ入力をコンピュータ・システムに送り、そのユーザ入力をCPU413に伝達するためのものである。図4のコンピュータ・システムは、さらに、ビデオ・メモリ414、メイン・メモリ415、および大容量記憶装置412を備えており、すべてキーボード410、マウス411、およびCPU413とともに双方向システム・バス419に結合されている。大容量記憶装置412は、磁気、光、または光磁気記憶装置システムや他の利用可能な大容量記憶装置技術などの固定媒体と取り外し可能媒体の両方を備えることもできる。大容量記憶装置は、ネットワークで共有したり、専用大容量記憶装置とすることもできる。バス419には、たとえば、ビデオ・メモリ414やメイン・メモリ415をアドレス指定するために32本のアドレス線を備えることができる。システム・バス419も、たとえば、CPU413、メイン・メモリ415、ビデオ・メモリ414、および大容量記憶装置412などの構成要素間でデータをやり取りするための32ビット・データ・バスを備える。それとは別に、データ線とアドレス線を別々にする代わりに、データ線とアドレス線を多重化することもできる。
【0085】
本発明の好ましい実施形態では、CPU413は、68030や68040などの、Motorola社製の32ビット・マイクロプロセッサである。ただし、他の適当なマイクロプロセッサやマイクロコンピュータでもかまわない。Motorola社製マイクロプロセッサとその命令セット、バス構造および制御線については、アリゾナ州フェニックスのMotorola Inc.で出版している『MC68030 User’s Manual』および『MC68040 User’s Manual』で説明されている。
【0086】
メイン・メモリ415は、ダイナミック・ランダム・アクセス・メモリ(DRAM)で構成されており、本発明の好ましい実施形態では、8メガバイトのメモリ構成である。本発明の範囲を逸脱することなく、メモリ容量を増減することができる。ビデオ・メモリ414はデュアル・ポート・ビデオ・ランダム・アクセス・メモリであり、本発明では、たとえば、256Kバイトのメモリ構成である。ただし、これもまたビデオ・メモリの増減が可能である。
【0087】
ビデオ・メモリ414の1つのポートがビデオ・マルチプレクサとシフタ416に結合されており、さらにビデオ増幅器417に結合されている。ビデオ増幅器417を使用して、陰極線管(CRT)ラスタ・モニタ418を駆動する。ビデオ多重化シフタ回路416およびビデオ増幅器417はよく知られている技術であり、適当な手段で実装が可能である。この回路は、ビデオ・メモリ414に格納されているピクセル・データをモニタ418で使用するのに適したラスタ信号に変換する。モニタ418は、グラフィック画像を表示するのに適した種類のモニタであり、本発明の好ましい実施形態では、解像度が約1020×832となっている。他の解像度のモニタも本発明では使用可能である。
【0088】
上述のコンピュータ・システムは例としてのみ取りあげたものである。本発明は、どのような種類のコンピュータ・システムあるいはプログラミングまたは処理環境であっても実装できる。
【0089】
ブロック図
図8は、本発明のブロック図である。破線801に囲まれている構成要素で表されている送信側が、平文メッセージPtxtを暗号文メッセージCに暗号化する。このメッセージCは、破線802で囲まれた構成要素で表される受信側に送信される。受信側802は、暗号文メッセージCを復号化して、平文メッセージPtxtを復元する。
【0090】
送信側801は、暗号化/復号化手段803、楕円乗算器805、秘密鍵ソース807がある。暗号化/復号化手段803は、回線809を介して楕円乗算器805に結合されている。楕円乗算器805は、回線811を介して秘密鍵ソース807に結合されている。
【0091】
受信側802の暗号化/復号化手段804は、回線810を介して楕円乗算器806に結合されている。楕円乗算器806は、回線812を介して秘密鍵ソース808に結合されている。
【0092】
送信側801の秘密鍵ソース807には、送信側の安全な秘密パスワード「ourPri」が含まれる。秘密鍵ソース807は、コンピュータ・システム内の記憶レジスタ、メッセージが送信されると送信側から暗号システムに送られるパスワード、あるいはメッセージが送信されたり、取り出されたりしたときに図8の暗号システムによって読み取られる符号化された物理的な鍵であってよい。同様に、受信側802の秘密鍵ソース808は、受信側の安全な秘密パスワード、つまり「theirPri」を含む。
【0093】
別のソース813には、送信側801と受信側の802の公開鍵「ourPub」および「theirPub」、初期点(X1、Y1)、体Fpk、および曲線パラメータa、b、cなどの公知の情報が格納される。この情報源は、コンピュータ・システムによって使用されるオンライン・ソースである、公開されているディレクトリであってもよく、また安全でない送信媒体上で送信側と受信側との間で送信することもできる。公開ソース813は図では、回線815を介して送信側801に、また回線814を介して受信側802に記号的に結ばれている。
【0094】
動作時に、送信側と受信側は安全な送信で暗号化および復号化鍵として使用するため共有の暗号パッドを生成する。送信側の秘密鍵ourPriが、受信側の公開鍵theirPubとともに楕円乗算器805へ送られる。楕円乗算器805は、暗号化鍵eKを(ourPri)°(theirPub)(mod p)
から計算する。暗号化鍵は、平文メッセージPtxtとともに暗号化/復号化手段803に送られる。暗号化鍵は、暗号文メッセージCを生成するために、DES方式や本発明の楕円曲線方式などの暗号化方式で使用される。暗号文メッセージを安全でないチャネル816上で受信側802に送信する。
【0095】
受信側802は受信側の秘密鍵theirPriを使用して復号化鍵DK を生成する。theirPriは、送信側の(公開ソース813からの)公開鍵ourPubとともに秘密鍵ソース808から楕円乗算器804に送られる。復号化鍵DK は、(theirPri)°(ourPub)(mod p)から生成される。復号化鍵DKは、楕円乗算機能の可換であるという性質から暗号化鍵eKに等しい。したがって、受信側802は、復号化鍵DK を使用して、暗号化方式を逆にし、暗号文メッセージCから平文メッセージPtxtを復元する。
【0096】
送信側801と受信側802の暗号化/復号化手段と楕円乗算器は、プログラム・ステップとして実装し、マイクロプロセッサで実行させることができる。
【0097】
逆変換なしのパラメータ化
高速クラス数を使用すると、(mod p)算術演算で除算が不要になる。しかし、上の式13−16に示されているように、楕円乗算「°」は、除算を何回か実行する必要がある。本発明を使用すると、逆変換なしにする初期パラメータ化を選択することで、楕円乗算に必要な除算の回数を減らすことができる。これは、「Y」項が不要になるように初期点を選択することで実現される。
【0098】
本発明では、送信側と受信側の両方が、楕円曲線上の特定のx座標として、共有の暗号パッドを生成する。初期点(X1,Y1)を適切に選択することにより、乗算n°(X1,Y1)を設定するプロセスから除算をなくすことができる。次のステップでは、整数nについて、
n°(Xm/Zm) 式(20)
は、座標(Xn+m/Zn+m)を表している。x=X/Zについて、Xn/Znとしての乗算n(x,y)のx座標は、乗算剰余演算を必要とする加算−2倍規則にしたがって「2進はしご」法を使用して計算する。Montgomeryパラメータ化(式7c)では、これらの規則は、
Figure 0003862500
である。
【0099】
そうでない場合、i=jであれば、
2i=(Xi 2−Zi 22 式(23)
2i=4Xii(Xi 2+cXii+Zi 2) 式(24)
である。
【0100】
これらの式は、除算を必要としないため、本発明を好ましい実施形態に実装したときに計算が簡略化される。これは、「逆変換なしのパラメータ化」と呼ばれ(除算がないので)、Montgomery,P.著『Speeding the Pollard and Elliptic Curve Methods of Factorization』(Math.Comp.、48(243−264)、1987年)に記載されている。体が単なるFp であった場合、この方式により、乗算、加算、(高速)Mersenne mod演算を使用して複数のnxを計算することができる。これはさらに、体がFp 2の場合にも、成立する。任意のMersenne数pについてp=3(mod 4)なので、Xi またはZi を複素整数として表し、複素数算術演算を実行して、乗算後の実部と虚部の両方を(mod p)で素早く簡約することができる。さらに、Z1 =1も選択し、曲線上の初期点が、yが不要になる場合に(X1 /1,y)となるようにする。
【0101】
高速クラスの数と逆変換なしのパラメータ化の両方を使用することで、本発明の方法を使用する公開鍵交換を次のように実行できる。次の例では、素数はMersenne数である。ただし、ここで説明するどの高速クラス数を代替することもできる。
【0102】
1)「自分」側で、曲線パラメータ(a,b,c)を使用して、公開鍵を計算する。ourPubεFpkXFp
(X/Z)=ourPri°(X1/1)
ourPub=XZ-1
2)「相手」側で、曲線パラメータ(a,b,c)を使用して、公開鍵を計算する。theirPubεFpkXFp
(X/Z)=theirPri°(X1/1)
theirPub=XZ-1
3)2つの公開鍵ourPubとtheirPubは公開されており、従って知られている。
4)共有の暗号パッドを計算する。ourPadεFpkXFp
(X/Z)=ourPri°(theirPub/1)
ourPad=XZ-1
5)共有の暗号パッドを計算する。theirPadεFpkXFp
(X/Z)=theirPri°(ourPub/1)
theirPad=XZ-1
【0103】
通常の鍵交換が完了し、次のようになる。
ourPad=theirPad
【0104】
「自分」側と「相手」側との間のメッセージ暗号化/復号化は、この相互暗号パッドに従って進む。
【0105】
FFT乗算
q>5000など、指数が非常に大きな場合には、数列のFourier変換を使って乗算を実行すると都合がよい。FFT乗算は、p=2q −1がq=220(約100万)ビット以下の場合に汎用演算xy(mod p)について、たとえば、68040ベースのNeXTstation上で正確に動作する。さらに、Mersenne数pについても、2進ビットの位数qの巡回たたみ込みが乗算(mod 2q −1)に等価であることが観察されたときにさらに無駄を省ける。FFT乗算手法を使用すると、q2 ではなく、qlogqにおおよそ比例する時間で乗算−modを実行することができる。
【0106】
FFT手法を使用すると本質的に楕円曲線代数を高速化することができる。を一般にXの数列のFourier変換とすると、この変換はFFT乗算で使用するものと同じである。次に、式21−24から座標を計算することができる。たとえば、Xi+j を計算するには、5つの適切な変換(X i 、X j 、Z i 、Z j 、およびZ i-j )(一部は、すでに格納されている)を使用して、次の変換を作成できる。
i+j=Zi-j i j i j2
【0107】
この方法で、7つのFFTを使って答えXi+jを求めることができる。(平方に2つのFFT、乗算に3つのFFTを使用する通常のやり方だと「標準」のFFT方式に対してFFTは11個になることに注意されたい)。比7/11では、固有の方法の無駄がかなり省かれる。pがMersenne数で、誤りのない数論的変換も利用できるような場合には、過去からのスペクトルを確保し、長時間の計算でスペクトル空間にとどまることができ、この方法により、時間がいっそう短縮する。
【0108】
高速クラス数、逆変換なしのパラメータ化、およびFFT乗算を使用したときの本発明の動作を示す流れ図を図9に掲載した。ステップ901で、高速クラス数pは、p=2q −Cとなるように選択する。項qは、暗号化方式のビット深さである。ビット数が多ければ多いほど、セキュリティは高くなる。大きな値のqについて、FFT乗算を使用してpを計算する。項pを公開して使用できるようにする。
【0109】
ステップ902で、体Fpk の要素kを選択し、公開する。ステップ903で、楕円曲線上の初期点(X1/Z)を選択する。初期点を逆変換なしになるように選択することにより、コストのかかる除算を避ける。初期点を公開する。ステップ904で曲線パラメータaを選択し、公開する。
【0110】
ステップ905で、送信側は逆変換なしのパラメータ化を使用してX1 /Z=ourPri°(X1 /1)を計算する。送信側の公開鍵が、ourPub=(XZ-1)(mod p)で生成される。受信側の公開鍵theirPub=(XZ-1)(mod p)はステップ906で生成される。
【0111】
送信側の1回限りの暗号パッドourPadがステップ907で生成される。X/Z=(ourPri)°(theirPub/1)。ourPud=(XZ-1)(mod p)。ステップ908で、受信側の1回限りの暗号パッドtheirPadを生成する。X/Z=(theirPri)°(ourPub/1)。theirPud=(XZ-1)(mod p)。ourPadとtheirPadの計算で、FFT乗算を使用して、逆変換Z-1を不要にする。ステップ909で、送信側はourPadを使用して平文メッセージPtxtを暗号文メッセージCに変換する。暗号文メッセージCは受信側に送信される。ステップ910で、受信側は、theirPadを使用して暗号文メッセージCを復号化して平文メッセージPtxtを復元する。
【0112】
FEEセキュリティ
楕円曲線法(ECM)を採用したときに「自然な」統計によりMersenne数である代数的因数M89=289−1が発生する。これは、M445=2445−1の因数分解を実行しようとして示された。つまり、乱数パラメータc(a=0,b=1としてMontgomeryパラメータ化を使用する)について、p=M89としたFp 上の楕円曲線の出現k(X1/1=0は統計的に、M445のM89を見つける時間がO(exp(√(2log p log log p))であるという漸近的推定と統計的に一致していた。そこで、これらの観察から、Mersenne数については乱数cパラメータを仮定した場合にFp 上の群の位数を見つけるのが「偶然にも」あまり容易でないということが示唆された。
【0113】
第2に、FEEに付随する離散対数問題が偶然に自明でないということをチェックするために、特定のcパラメータについて、束縛されている整数の集合では、
(pN−1)(X1/1)≠0
が成立することを検証できる。
【0114】
不等号は、離散対数評価の対応する有限体上の等価な評価への自明な簡約を避けるためである。不等号が成立しないというのは非常にまれであり、実際、この時点ではq>89なる数について自明でない実例が知られている。
【0115】
本発明では、従来技術に勝る多くの利点を提示しており、特に、RSA方式などの因数分解方式を特徴とする。本発明は、少ないビットと高速な演算でありながら、同じセキュリティを実現できる。それとは別に、本発明のシステムでは同じビット数にして、セキュリティを高めることもできる。
【0116】
従来技術に勝る本発明の暗号システムの他の利点として秘密鍵の配布がある。RSAなどの従来技術の方式では、秘密鍵を作成するために大きな素数を生成する必要がある。本発明では、秘密鍵を素数にする必要はない。したがって、ユーザは、正しい公知のパラメータを使用して公開鍵が生成され公開される場合に限り、自分の秘密鍵を生成することができる。ユーザは、RSAシステムで自分の秘密鍵を生成することはできない。
【0117】
電子署名
本発明は、上記の楕円代数とハッシュまたはダイジェスト関数を使用する電子署名を作成し認証する改良された方法を提示する。送信側は暗号化メッセージ「暗号文」を作成済みである。このメッセージを前記のように暗号化するか、または他の暗号化方式を使用して暗号化することができる。送信側は、次に、電子署名を作成して、メッセージの「署名」の手段としてメッセージに添付する。好ましい実施形態の署名方式について以下の段で説明し、その後、計算を減らす方法を説明する。
【0118】
署名の作成
開始点(X1 /1)を持つa、b、cでパラメータ化された曲線を仮定する。さらに、開始点は楕円曲線上で位数Nであると仮定する。送信側の公開鍵ourPubを複数のourPri°(X1 /1)として生成するが、ここでourPriは自分の秘密鍵(整数)、°は楕円曲線上の乗算である。電子署名は次のように作成される。
1)約qビットの乱数整数mを選択する。
2)点を
P=m°(X1/1)
を計算する。
3)メッセージ・ダイジェスト関数Mを使用して、整数
u=(m+ourPri*M(暗号文,P))(mod N)
を計算する。ただし、暗号文は送信する暗号化されたメッセージである。
4)暗号文とともに、電子署名をペア(u,P)として送信する。uは約2q ビットの整数であるが、Pは曲線上の点であることに注意されたい。
【0119】
本発明の好ましい実施形態では、MD2やMD5などのメッセージ・ダイジェスト関数Mを電子署名の生成の一部として使用する。ただし、本発明は他のダイジェスト関数を使用したり、適当なハッシュ関数を使用しても、実装できる。
【0120】
電子署名の認証
受信側は、暗号文メッセージと、意図されている送信側の公開鍵を使用して、点のペアを生成して電子署名の一致を調べることにより署名を認証しようとする。受信側は、次のステップで署名を検証する。
1)署名のu部分を使用して、点
Q=u°(X1/1)
を計算する。
2)点Qと点 R=P+M(暗号文,P)°ourPubを比較する。
【0121】
署名は、楕円点QおよびRが正確に比較されていない場合には無効である。つまり、署名が信頼のあるものであれば、次の式が成立しなければならない。
u°(X1/1)=P+M(暗号文,P)°ourPub
【0122】
上の式の左辺のuを置き換えると、
(m+ourPri*M(暗号文,P))°(X1/1)=P+M(暗号文,p)°ourPub
または
m°(X1/1)+(ourPri*M(暗号文,P))°(X1/1)=P+M(暗号文,P)°ourPub
となる。
【0123】
式の右辺のourPubを置き換えると、
m°(X1/1)+(ourPri*M(暗号文,P))°(X1/1)=P+M(暗号文,P)°ourPri°(X1/1)
となる。
上記よりP=m°(X1/1)なので、左辺は
P+(ourPri*M(ciphertext,P))°(X1/1)=P+M(ciphertext,P)°ourPri°(X1/1)
となる。
【0124】
式の右辺でourPriを移行すると、
P+ourPri*M(暗号文,P))°(X1/1)=P+ourPri*M(暗号文,P)°(X1/1)
となる。
【0125】
したがって、曲線上の点は、送信されたペア(u,P)を使用して2つの異なる式を使用して計算される。送信された点uからのQを計算し、さらに送信されたP、暗号文メッセージ、および意図されている送信側の公開鍵からRを計算することにより、QとRが一致すれば電子署名が認証されたと仮定する。
【0126】
セキュリティ
この方式の電子署名方式は、次の観察結果をもとに安全なものである。署名を偽造するには、ペア(u,P)と式
u°(X1/1)=P+M(暗号文,P)°ourPub
を満たす暗号文を見つけなければならなくなる。
【0127】
これは、楕円対数演算(本発明の暗号化セキュリティの基盤)を実行するか、またはハッシュ関数Mを破る必要がある。
【0128】
認証の最適化
本発明の電子署名方式における受信側の最終ステップでは、2つの点、つまりPとM(暗号文,P)°ourPubを加えてRを求め、その和を点Qと比較する必要がある。各ステップで指定されたy座標を使用して楕円加算を実行することもできる。本発明の方式では、注目している要素の2つの点のそれぞれのx座標のみを使用して、2つの点の和のx座標の可能な値を小さくする方法を実現する。点QとP+M(暗号文,P)°ourPubが同一のx座標を持つかどうかをチェックする必要があるが、この方法を使用して、そのチェックを高速に実行することができる。
【0129】
x座標のみを使用して和の高速検証を行う原理は次のように動作する。たとえば、Montgomeryパラメータ化を使用し、曲線を
2=x3+cx2+x
とする。
【0130】
定理:P1=(x1,y1)、P2=(x2,y2)、Q=(x,y)を与えられた曲線上の3つの点とし、x1≠x2とする。このとき、
x(C−x)=B2
の場合、かつその場合に限り、
1+P2=Q
が成立する。
ただし、
B=(x12−1)/(x1−x2
C=2((x12+1)(x1+x2+2c)−2c)/(x1−x22
とする。
【0131】
証明は次の通りである。P1とP2のy座標はわかっていないので、和P1+P2のx座標について唯一可能性があるのは、任意に固定されたペア(y1,y2)について、2つの形式(x1,y1)±(x2,y2)のそれぞれのx座標(e、fと呼ぶ)であることに注意されたい。前記のように、
ef=B2
e+f=C
をMontgomeryの場合のように計算できる。xはe、fのうちの一方または他方なので、定理の2次方程式が成り立つには、(x−e)(x−f)=0である必要がある。
【0132】
したがって、本発明のx座標方式を使用した場合、(x−e)(x−f)=0を満たす2つの解を持つ可能性がある。したがって、偽物の署名から一方の可能な解が生成される。ただし、(x−e)(x−f)=0を満たすときに、文字通り何100万もの解があるので、署名は信頼できると仮定しても安全である。
【0133】
実用的な応用例では、P1 は、送信側が署名の一部として送信した計算で求めた点Pを表す。P2 は、式M(暗号文,P)°ourPubを表す。もちろん、Qはu°(X1/1)を表す。P1+P2はRを表し、Qと比較される。
【0134】
流れ図
図10は、本発明を使用する電子署名の生成を説明する流れ図である。ステップ1001で、送信側は乱数整数mを選択する。この乱数整数は、マイクロプロセッサで使用する適当な乱数生成器を使用して生成できる。ステップ1002では、mを使用して点Pを計算する。前記のように、本発明の好ましい実施形態では、この点は関係式P=m°(X1 /1)を使用して生成される。ただし、本発明の範囲を逸脱することなく点Pを生成するために他の方式を使用することもできる。
【0135】
ステップ1003で、第2の数uは、m、P、ourPri、および暗号文メッセージを使用して計算する。本発明の好ましい実施形態では、これは、関係式u=m+ourPri*M(暗号文,P) を使用して生成する。前記のように、ダイジェスト関数MD2およびMD5以外のハッシュ関数を使用することもできる。さらに、uを計算するために、他の関係式を使用することもできる。他の関係式を使用する場合には、そのm、P、ourPri、および暗号文メッセージを使用するようお勧めする。ステップ1004で、計算で求めたペア(u,P)を電子署名として送信する。
【0136】
図11は、本発明の電子署名の認証を説明する流れ図である。ステップ1101で、メッセージの受信者は電子署名(u,P)と暗号文メッセージを受信する。ステップ1102で、点uを使用して、点Qを生成する。好ましい実施形態では、関係式Q=u°(X1/1)を使用してQを生成する。送信側がu、Pを計算するのにどのような関係式を使用したかに応じて他の関係式を使用することもできる。
【0137】
ステップ1103で、ourPubと暗号文メッセージを使用して点P2を生成する。好ましい実施形態では、関係式M(暗号文,P)°ourPubを使用してP2を生成する。送信側がu、Pを計算するのにどのような関係式を使用したかに応じて他の関係式を使用することもできる。
【0138】
ステップ1104で、P1とP2のx値を使用して、値BとCを決定し、最終的にeとfを決定する。これにより、P1とP2の和の可能な2つのx値が得られる。決定ブロック1105で、引数「e,f=x?」を付けて、P1+P2=Qの等式を可能なx値のいずれかが満たすかどうかを判断する。計算で求めたx値のいずれも方程式を満たさない場合、つまり、決定ブロック1105での引数が偽であれば、署名は信頼できるものではなく、ブロック1106で指示される。x値のうちの1つが方程式を満たす場合、つまり決定ブロック1105での引数が真であれば、有効な署名であると仮定され、ブロック1107で指示される。
【0139】
ブロック図
図12は、本発明の電子署名方式を実装するブロック図である。図12の要素が図8の要素と共通である場合には、同じ要素番号を使用する。楕円乗算を使用する暗号化方式で使用する署名方式を取りあげているが、これは例として取りあげただけである。本発明は、どのような種類の暗号化方式とも使用することができる。
【0140】
破線1201で囲まれている構成要素で表されている送信側が、平文メッセージPtxtを暗号文メッセージCに暗号化し、署名(u,P)を生成する。このメッセージCと署名(u,P)は、破線1202で囲まれている構成要素で表されている受信側に送信される。受信側1202は、暗号文メッセージCを復号化して、平文メッセージを復元し、署名(u,P)を認証する。
【0141】
送信側1201は、暗号化/復号化手段1203、楕円乗算器805、乱数生成器1205、ハッシュ生成器1207、および秘密鍵ソース807を備えている。暗号化/復号化手段1203は、回線809を介して楕円乗算器805に結合されている。楕円乗算器805は、回線811を介して秘密鍵ソース807に結合されている。乱数生成器1205は、回線1209上で乱数mを楕円乗算器805とハッシュ生成器1207に送る。楕円乗算器805は、回線1211を介して安全でないチャネル816に数値uを送る。暗号化されている暗号文Cが回線1213を介してハッシュ生成器1207に送られる。ハッシュ生成器1207は、回線1215を介して点Pを安全でないチャネル816に送る。
【0142】
受信側1202の暗号化/復号化手段1204は、回線810を介して楕円乗算器806に結合されている。楕円乗算器806は、回線812を介して秘密鍵ソース808に結合されている。数値uは、回線1212を介して安全でないチャネル816から楕円乗算器806に送られる。楕円乗算器806は、点Qを生成し、回線1216を介して比較器1208に送られる。ハッシュ生成器1206は、回線1210を介して安全でないチャネル816から暗号文メッセージCおよび点Pを受信し、さらに回線1218を介してソース813からourPubを受信する。ハッシュ生成器1206は、回線1214を介して点Rを比較器1208に出力する。
【0143】
送信側801の秘密鍵ソース807は、送信側の安全な秘密パスワード「ourPri」を含む。秘密鍵ソース807は、コンピュータ・システム内の記憶レジスタ、メッセージが送信されたときに送信側が暗号システムに送るパスワード、さらにはメッセージを送信または受信したときに図12の暗号システムによって読み取られる符号化された物理的鍵であってもよい。同様に、受信側802の秘密鍵ソース808は受信側の安全な秘密パスワード「theirPri」を含む。
【0144】
別のソース813は、送信側1201と受信側1202の公開鍵「ourPub」および「theirPub」、初期点(x1,y1)、体Fpk、曲線パラメータa、b、cなどの公知の情報を格納する。この情報源は、コンピュータ・システムによって使用されるオンライン・ソースである、公開されているディレクトリであってもよく、また安全でない送信媒体上で送信側と受信側との間で送信することもできる。公開ソース813は図では、回線815を介して送信側1201に、また回線814と1218を介してそれぞれ受信側1202とハッシュ生成器1206に記号的に結ばれている。
【0145】
動作時に、前記のように送信側と受信側は安全な送信で暗号化および復号化鍵として使用するため1回限りの共通の暗号パッドを生成する。暗号化鍵を、平文メッセージとともに暗号化/復号化手段1203に送る。DES方式や本発明の楕円曲線方式などの暗号化方式とともに暗号化鍵を使用して、暗号文メッセージCを生成する。乱数生成器1205は、乱数mを生成し、楕円乗算器805に送る。楕円乗算器805は、数値uを生成し、安全でないチャネル816を介して受信側に送る。暗号文メッセージCは、乱数mとourPriとともにハッシュ生成器1207に送られる。ハッシュ生成器1207は、点Pを生成し、安全でないチャネル816に送る。暗号文メッセージは、署名(u,P)とともに、安全でないチャネル816上で受信側1202に送信される。
【0146】
受信側1202は、受信側の秘密鍵theirPriを使用して復号化鍵DK を生成する、theirPriが、送信側の公開鍵ourPub(公開ソース813からの)とともに、秘密鍵ソース808から楕円乗算器806に送られる。復号化鍵DK は、(theirPri)°(ourPub)(mod p)から生成される。復号化鍵DKは、楕円乗算機能の可換性のため、暗号化鍵eKに等しい。したがって、受信側1202は、復号化鍵DK を使用して暗号化方式を逆にし、暗号文メッセージCから平文メッセージを復元する。
【0147】
受信側1202の楕円乗算器806は、安全でないチャネル816から数値uを受信する。楕円乗算器806は、点Qを生成し、比較器1208に送る。ハッシュ生成器は、安全でないチャネル816から暗号文メッセージCと点P、ソース813から意図されている送信側の公開鍵ourPubを受信して、点Rを生成し、点Rを比較器1208に送る。比較器1208は、点QとRを比較し、一致している場合には、署名は有効であると仮定する。本発明では、前記のx値を使用して最適化されている方式により点QとRの比較を実行する。
【0148】
送信側1201と受信側の1202の暗号化/復号化手段および楕円乗算器は、プログラム・ステップとして実装し、マイクロプロセッサ上で実行させることができる。
【0149】
直接埋め込み
本発明では、2つの曲線E±のうちの一方にテキスト・パーセルをマッピングできるという事実を利用している。受信側の公開鍵を使用し、送信側はメッセージ座標、手がかりの値および符号を生成し、3つ組として受信者側に送信する。手がかりと受信側の秘密鍵を使用して、メッセージ座標からテキスト・パーセルを復号化することができる。展開できない形では、送信側と受信側は自分の共有の暗号パッドを使用して、共有の手がかりを計算し、それぞれのメッセージ座標が1ビットの符号とともに送信されるようにする。
【0150】
前記の高速楕円代数を使用して生成した楕円曲線は、充分に特別なもの(つまり、密に定義されている)であり、平文の任意のパーセルが直接埋め込まれ、当然、可能な2つの曲線のうちの1つに埋め込まれる。この曲線を「+」曲線および「−」曲線と呼んでいる。
【0151】
展開のない直接埋め込み
本発明をさらに精密化した場合、各3つ組の手がかり構成要素をなくすことにより暗号化されているパーセルのサイズを縮小することができる。これは、送信側と受信側との間で同期をとる際に手がかりを生成する手段を設定することにより実現される。たとえば、前記の直接埋め込みの方法を使用して、送信側から受信側に2つの乱数r、sを安全に送信することができる。送信側は、第1の手がかりを
clue1=r°ourPri°theirPub
として計算し、同様に、受信側は同じ手がかりを
clue1=r°theirPri°ourPub
として計算する。
【0152】
後の手がかりは、次のように楕円加算を実行して両側に形成することができる。
cluen+1=cluen+s°P
ただし、Pは曲線上の初期点である。
【0153】
直接埋め込みの場合のように、埋め込まれたメッセージ・パーセルの点Ptextはclueに楕円加算されて、メッセージ点を構成し、復元の手がかりgを計算し、ただ1つのペア(message,g)として送信される。
【0154】
楕円曲線演算
後述のように、直接埋め込まれた平文の送信側は1ビットを送信して、受信側で復号化できるようにどの曲線を使用するかを識別する。
【0155】
直接埋め込みという考えは、楕円曲線自体に平文のパーセルを埋め込むというものである。点Ptextを暗号化する平文のパーセルを含む曲線の点とする。前記の高速楕円曲線代数を使用することで、点のペアと単一ビットgからなる3つ組を送信することができる。
(Ptext+r°theirPub,r°P1,g)
(実際、本来の曲線点のペアと1ビットではなく、送信するx座標のペアと1ビットだけが送信される)。ただし、rは乱数整数である。この送信を
(メッセージ、手がかり、パリティ)
として定性的に考える。
【0156】
「相手」側では、受信側は「手がかり」と「パリティ」およびその秘密鍵「theirPri」を使用して、「メッセージ」から平文を推論する。パリティ・ビットは、曲線の曖昧さと2次式の符号曖昧さに応じて全体的な符号の結果となる。
【0157】
テキストの直接埋め込みは、次の楕円曲線の関係を検討することにより理解される。
【0158】
ここでは、体Fpの場合に集中するが、ただし
p=2q−1
は、Mersenne数である。注目している楕円曲線をEとすると、これは
sy2=x3+cx2+bx+a
を満たす点P=(x,y)εFpXFpで構成されるように組み立てられるが、「無限遠点」Oとともに曲線の符号sは+1または−1、およびc≠2のいずれかに制限される。実際の曲線点には太字を使用していることに注意されたい。つまり、ここまでの記法は、
x、yは両方とも整数(mod p)である
曲線上の点Pはペア(x,y)である
または抽象的な「無限遠点」Oの場合もある
Eは、すべてのPの集合である。
【0159】
強力な古典的結果がHasseの定理であり、曲線の位数|E|である、つまり点Pの総数は
【数2】
Figure 0003862500
が成立するという意味でp自体に近いということである。
【0160】
点の間にある種の演算が用意されている場合、楕円曲線Eは加法群になる。点Oは加法的な単位要素であるが、加法の群の公理は次のように働く。2つのOでない点
1=(x1,y1) P2=(x2,y2
について、曲線の加法を
3=P1+P2=(x3,y3
で定義し、減法を
4=P1−P2=(x4,y4
で定義し、その際にMontgomeryパラメータ化a=1、b=0の関係式
【数3】
Figure 0003862500
とともに、否定の規則
−P1=(x1,−y1
を使用している。
【0161】
そこで、x1≠x2について、和と差のx座標は、
【数4】
Figure 0003862500
を使用して、関係付けられることが導かれる。
【0162】
これらの定義済み関数F、Gは、直接埋め込みの理論で計算される。特にG関数は別に
【数5】
Figure 0003862500
と書くことができ、Q関数は楕円曲線の定義2次形式、つまり
Q(z)=z2+cz+1
であることに注意されたい。
【0163】
楕円乗算はしご
実際の実装では、y座標を無視する[Montgomery 1987]の逆変換のないパラメータ化を使用して、高速楕円曲線乗算を実行する。いくつかの点P=(X1,y)について、Pのn回乗算をPのn個のコピーの楕円和として定義し、n°Pと表す。(整数n=0の時、0°Pを抽象点0と解釈する。)そこで、Z1 =1がわかっているとして、複数のn°Pのx座標をXn/Znと表す。整数Xn、Znは、いくつかの加算−2倍規則に従って2進はしご法により評価することができる。これらの規則は前記の基本的な加法/減法の法則から導くことができ、上の式21、22、23、および24の形式をとる。
【0164】
Mersenne mod演算
楕円乗算はしご法では、加算−2倍規則を通じて乗算−mod演算が関わる。これらの演算は、効率化することができる。さらに、鍵または暗号パッドを解決するために必要な単一の逆変換Z-1も高速に実行できる。いずれにせよ、すべての算術演算は乗算、シフト演算、加算で実行することができ、そのため除算を使用しないシステムができあがる。
【0165】
高速Mersenne mod演算は、上の式17、18、および19に関して説明したように実行できる。逆(mod p)は、上述のように式19に従って計算することができる。
【0166】
さらに、多項式GCD法に基づく再帰的逆変換アルゴリズムもあり、これは実際に、ある小さな整数mについてO(qlogmq) の時間がかかる。逆変換の時間は、上述のような累積FFT乗算手法と競合する。
【0167】
定理
次の定理は、本発明の直接埋め込み方式を補助するものである。
【0168】
定理1
楕円曲線E上の点Pと整数m、nについて、
mn°P=nm°P=m(n°P)=n(m°P)
が成り立つ。
【0169】
これは、可換性と結合性の規則を示している。
定理2
与えられたパラメータa=0、b=1、c≠2について、任意の正数xは、2つの高速楕円曲線
±:±y2=xQ(x)
の1つに存在するある点の有効なx座標である。
pはMersenne数で、したがって=3(mod 4)なので、整数s=xQ(x)は平方またはその負の値であることに注意されたい。
【0170】
定理3
1=(x1,y1)、P2=(x2,y2)とし、P3=P1+P2=(x3,y3) と仮定する。このとき、x3は、次の式を満たさなければならない。
1≠x2の場合:2次関係式x3(G(x1,x2)−x3)=F(x1,x22
1=x2の場合:関係式x3=(x1 2−1)2/4x1Q(x1))
【0171】
定理4
1=(x1,y1)、P2=(x2,y2)、x1≠x2とする。次のように表記する。
3=P1+P2=(x3,y3
4=P1−P2=(x4,y4
このとき、x3は次の2つの値のうちの1つである。
(x1Q(x2)+x2Q(x1)±2(x1Q(x1)x2Q(x2))(p+1)/4)/((x1−x22
ただし、x4は他の値である。
【0172】
上の定理3の2次関係式を解くと、
【数6】
Figure 0003862500
が得られる。
【0173】
p=3(mod 4)について、aの平方(mod p)の平方根は常にプラスまたはマイナスa(P+1)/4(mod p)である。
【0174】
定理5
曲線E±の1つの上の任意の整数x(mod p)について、正しい符号+または−が次の式で成立するいずれかの符号により与えられる。
(xQ(x))(P+1)/2=±xQ(x)(mod p)
xQ(x)が0であれば、+曲線が使用される。
【0175】
直接埋め込みアルゴリズム
次のように仮定する。
パラメータq、a=0、b:=±1、c≠2で、2つの可能な楕円曲線E±が得られる。
2つの点
1 +=(X1 +,?) P1 -=(X1 -、?)
が曲線E±上にそれぞれ存在するような2つの公開されている初期x座標X1±。y座標(「?」で表されている)は、高速楕円代数を使用する場合には無視できる。
公開鍵のペアが存在している。theriPub±は
(theirPub±、?)=theirPri°P1 ±
に従って、単一の秘密鍵theirPriから生成される。
平文を、それぞれqビット以下のパーセルに分ける。つまり、パーセルは値(mod p)である。
符号sを使用して上の定理4からまたはまれなケースであるx1=x2の場合は定理3から、x3またはx4のうちの1つを計算する関数elliptic_add(x1,x2,s)が存在すること。
【0176】
平文パーセルxtextを暗号化するには、次のようにする。
1.定理5からパーセルxtextが有効なx座標である2つの曲線E±のうちのいずれかを決定する。前記曲線を符号s=±1で表す。
2.乱数rを選択し、前記のはしご算術演算を使用して(xq,?):=r°(theirPub±,?)を計算する。
3.メッセージ座標xm:=elliptic_add(xtext,xq,+1)を計算する。
4.乱数rを使用して手がかりxcを計算し、公開点を(xc,?):=r°P1 ±として計算する。
5.elliptic_add(xm,xq,±1)=xtext内で有効な符号を決定し、これを符号gとする。
6.メッセージ座標の3つ組、手がかり、および符号を送信側に(xm,xc,g)として送信する。
【0177】
1パーセルの平文を復号化するには、次のようにする。
1.(xm,xq,g)を受信すると仮定して、手がかりxcを使用し、
(xq,?)=theirPri°(xc,?)
からx座標xqを計算する。
2.次の式を使用して平文を復元する。
text=elliptic_add(xm q ,g)
【0178】
アルゴリズム3をソフトウェアで実現したものを本書巻末に付録コードとして添付した。実際の実施では、乱数整数楕円乗算(rによる)は定期的にしか実行しないので、実行時間が短縮する。事実、rの乗算は、たとえば定理4で具現化されているべき乗以上に実際にコストがかかることがわかっている。
【0179】
直接埋め込みの流れ図
図13は、直接埋め込みを使用して平文メッセージを暗号化する流れ図である。ステップ1301で、平文をそれぞれqビット以下のパーセルに分割する。各パーセルxtextについて、ステップ1302で、2つの曲線E±のうちのどれに対してパーセルが有効なx座標であるかを決定する。これは、前記の定理5を使用して実行できる。ステップ1303で、しかるべき曲線を符号=±1で表す。
【0180】
ステップ1304で、乱数rを選択する。ステップ1305で、(xq,?)=r°(theirPub±,?)を計算する。これは、はしご算術演算を使用して実行できる。ステップ1306で、メッセージ座標xmを計算する。これは、xm:=elliptic_add(xtext,xq,+1)または他の適当な方法により実行できる。ステップ1307で、手がかりを計算する。これは、(xc,?):=r°P1 ±で実行できる。
【0181】
ステップ1308で、xtextについて成立する符号をgと定義する。この符号は、elliptic_add(xm,xq,+1)がxtextに等しいかどうかをテストして決定することができる。ステップ1309で、メッセージ座標、手がかり、および符号を3つ組として(xm,xc,g)という形式で受信側に送信する。
【0182】
図14は、図13の暗号化されたメッセージを復号化する流れ図である。ステップ1401で、送信側から3つ組(xm,xc,g)を受信する。ステップ1402で、(xq,?):=theirPri°(xc,?)からx座標xqを計算する。次にステップ1403で、xtext:=elliptic_add(xm,xc,g)により平文を復元することができる。
【0183】
拡張のない直接埋め込みアルゴリズム
一連の平文パーセルxtextnを暗号化するには、次のようにする。
1.2つの乱数r、s∈Fpkを選択して、たとえば、直接埋め込みアルゴリズムを使用して受信側に送信する。
2.式
clue=r°ourPri°theirPub±
s=s°P±
を計算して、両方の曲線の初期手がかりを計算する。
3.平文パーセルxtextiについて、2つの曲線のうちどれに関してxtextiが有効な点か(またはxtextiが有効な座標であるものはどれか)を決定する。
4.正しい曲線点を使用して、メッセージ座標
i:=elliptic_add(xtexti,cluei,+1)
を計算する。
5.elliptic_add(mi,cluei,±1)のどの符号でxtextiを復元するかを決定し、この符号をgとする。
6.ペア(mi,g)を送信する。
7.後のパーセルについて、
cluei+1=elliptic_add(r°cluei,s,+1)
を計算し、ステップ3−6を繰り返す。
【0184】
一連のペア(m,g)を復号化するには、次のようにする。
1.乱数r、sを復元し、初期手がかりを次のように計算する。
clue=r°theirPri°ourPub±
s=s°P±
2.各ペア(m,g)について、どの曲線に点mがあるかを決定する。
3.決定された曲線から次の点に対する演算を使用して平文を復元する。
elliptic_add(clue,m,g)
4.後続のペアの手がかりを再計算する。
cluei+1=elliptic_add(r°cluei,s,+1)
【0185】
拡張なしの直接埋め込みの流れ図
図15は、拡張なしの直接埋め込みを使用して平文メッセージを暗号化する流れ図である。ステップ1500で、平文をそれぞれqビット以下のパーセルに分割する。ステップ1501で2つの乱数rとsを選択し、ステップ1502で受信側に送信する。ステップ1503で、乱数rとsを使用して両方の曲線について初期手がかりclueとsを決定する。
【0186】
ステップ1504で、それぞれのパーセルxtextについて、送信側はパーセルが有効なx座標になるのは2つの曲線E±のうちどちらであるかを決定する。ステップ1505で、mi:=elliptic_add(xtexti,cluei,+1)を使用してメッセージ座標を計算する。ステップ1506で、送信側は、elliptic_add(mi,cluei,±1)内のどの符号でxtextiを復元するかを決定し、この符号をgとする。
【0187】
ステップ1507で、現在のペア(m,g)を受信側に送信し、前の手がかりと乱数rとsを使用してステップ1508で次の手がかりを計算する。ステップ1508の後で、プロセスはステップ1504に戻り、次のパーセルを暗号化する。
【0188】
図16は、図15の暗号化されているメッセージを復号化する流れ図である。ステップ1600で、受信側は、受信側によって送信された乱数rとsを復元し、ステップ1601で、乱数rとsを使用して、初期手がかりを決定する。ステップ1602で、受信側は送信側が送信したペア(m,g)を復元する。現在のペア(m、g)について、ステップ1603で、受信側はどの楕円曲線に点mがあるかを決定する。決定された曲線の点を使用して、ステップ1604でelliptic_add(clue、m,g)を使って平文パーセルを復元する。ステップ1605で、前の手がかりおよび乱数rとsに基づいて次の手がかりを計算する。ステップ1605の後で、プロセスはステップ1602に戻り、次のパーセルに取りかかる。
【0189】
コード
直接埋め込みを使用して暗号化と復号化を実装するコードで、Mathematicaを使って書いたコード例を以下に示す。
【表1】
Figure 0003862500
【表2】
Figure 0003862500
【表3】
Figure 0003862500
【0190】
最適化された方式を使用して署名を比較する関数を以下に示す。
【表4】
Figure 0003862500
【0191】
Qを計算し、(P+M(暗号文,P)°ourPub)と比較する関数を以下に示す。
【表5】
Figure 0003862500
【0192】
暗号化/復号化
本発明の暗号化/復号化方式は、プログラミング言語Cを用いて実装することができる。以下は、本発明の暗号化/復号化の実装に適したプログラム・インタフェース(.hファイル)とテスト・プログラム(.cファイル)の例である。
【表6】
Figure 0003862500
【表7】
Figure 0003862500
【表8】
Figure 0003862500
【表9】
Figure 0003862500
【0193】
【表10】
Figure 0003862500
【表11】
Figure 0003862500
【0194】
【表12】
Figure 0003862500
【0195】
【表13】
Figure 0003862500

【図面の簡単な説明】
【図1】 従来技術による公開鍵交換システムのブロック図である。
【図2】 従来技術による公開鍵交換トランザクションの流れ図である。
【図3】 本発明の鍵交換を説明する流れ図である。
【図4】 本発明を実装することが可能なコンピュータ・システムのブロック図である。
【図5】 Mersenne数を使用しpを法とする算法を実行するシフトおよび加算演算を説明する図である。
【図6】 Fermat数を使用しpを法とする算法を実行する動作を説明する図である。
【図7】 高速クラス数を使用しpを法とする算法を実行する動作を説明する図である。
【図8】 本発明のブロック図である。
【図9】 本発明の一実施形態の動作を説明する流れ図である。
【図10】 本発明を使用して電子署名を生成する方法を説明する流れ図である。
【図11】 本発明における電子署名の認証を説明する流れ図である。
【図12】 本発明の電子署名方式を実装するためのブロック図である。
【図13】 直接埋め込みを使用して平文メッセージを暗号化する流れ図である。
【図14】 図13の暗号化されたメッセージを復号化する流れ図である。
【図15】 展開なしの直接埋め込みを使用して平文メッセージを暗号化する流れ図である。
【図16】 図15の暗号化されたメッセージを復号化する流れ図である。

Claims (22)

  1. 送信側コンピュータ・システム内で平文メッセージを暗号化する方法であって、
    受信側に送信するため送信側コンピュータ・システムのメモリから値xtextを有する1パーセルの平文を選択するステップと、
    x座標として値xtextを有する第1の点を含む第1の楕円曲線、すなわち、第1の式2 = x3 + cx2 + ax + bで表される楕円曲線E+と第2の式−y2 = x3 + cx2 + ax + bで表される楕円曲線E-とからなる楕円曲線の集合から選択された楕円曲線ここで、a、b、cは既知の値である、を決定するステップと、
    乱数rと公開鍵とを第1の楕円乗算器に与えて、前記メモリに前記第1の楕円曲線上の第2の点x座標を表す値xqを生成するステップと、
    前記の値xtextとxqとを第1の楕円加算器に与えて、前記メモリに前記第1の楕円曲線上のx座標の第3の点を表すメッセージ値xmを生成するステップと、
    乱数rと前記第1の楕円曲線の初期公開点とを前記第1の楕円乗算器に与えて、前記メモリに手がかり値xcを生成するステップと、
    前記のメッセージ値xmとxqを前記第1の楕円加算器に与えて、前記第3の点が第1の点と第2の点の和であるかまたは第1の点から第2の点を減じた差であるかを表す符号値gを得るステップと、
    前記のメッセージ値xm、手がかり値xc及び符号値gを含む前記暗号化されたメッセージを生成するステップを含む方法。
  2. 前記メッセージ値xm、前記手がかり値xc、および前記符号値gは、受信側に送信されることを特徴とする請求項1に記載の方法。
  3. 前記公開鍵は前記受信側の公開鍵であることを特徴とする請求項2に記載の方法。
  4. x座標として第1の点xtextを含む第1の楕円曲線を決定するステップは、
    (xtextQ(xtext))(p+1)/2 = +xtextQ(xtext)(mod p)なら、第1の楕円曲線は楕円曲線E+であり、
    (xtextQ(xtext))(p+1)/2 = −xtextQ(xtext)(mod p)なら、第1の楕円曲線は楕円曲線E-である
    (ここで、p = 3(mod 4)、 Q(xtext)=(xtext2+c(xtext)+b)と決定するステップを含むことを特徴とする請求項1に記載の方法。
  5. さらに、前記受信側で、
    前記手がかり値xcを第2の楕円乗算器に与えて値xqを得るステップと、
    メッセージ値xm、値xq及び符号値gを第2の楕円加算器に与えて値xtextを得、前記のパーセルの平文を復元するステップとを含むことを特徴とする請求項2に記載の方法。
  6. 楕円曲線代数を使用して平文メッセージを暗号化するためにコンピュータ読み取り可能なプログラム・コードが埋込まれているコンピュータ使用可能な記録媒体であって、前記コンピュータ読み取り可能なプログラム・コードは、
    コンピュータにメモリから値xtextを有する1パーセルの平文を選択させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータにx座標としてxtextを有する第1の点を含む第1の楕円曲線、すなわち、第1の式2 = x3 + cx2 + ax + bで表される楕円曲線E+と第2の式−y2 = x3 + cx2 + ax + bで表される楕円曲線E-とからなる楕円曲線の集合から選択された楕円曲線ここで、a、b、cは既知の値である、を決定させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに乱数rと公開鍵を前記第1の楕円乗算器に与えて、前記第1の楕円曲線上の第2の点x座標を表す値xqをメモリに生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに前記の値xqと値xtextを第1の楕円加算器に与えて、前記第1の楕円曲線上のx座標の第3の点を表すメッセージ値xmを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに乱数rと前記第1の楕円曲線の初期公開点を前記第1の楕円乗算器に与えて、手がかり値xcを前記メモリに生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに前記のメッセージ値xmと値xqを第1の楕円加算器に与えて、前記第3の点が第1の点と第2の点の和であるかまたは第1の点から第2の点を減じた差であるかを表す符号値gを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに前記のメッセージ値xm、手がかり値xcおよび符号値gを含む前記の暗号化されたメッセージを生成させるように構成されたコンピュータ・プログラム読み取り可能なプログラム・コードとを含むことを特徴とする記録媒体。
  7. 前記のメッセージ値xm、手がかり値xc及び符号値gは受信側に送信されるものであることを特徴とする請求項6に記載の記録媒体。
  8. 前記公開鍵が前記受信側の公開鍵であることを特徴とする請求項7に記載の記録媒体。
  9. コンピュータにx座標としてxtextを有する第1の点を含む第1の楕円曲線を決定させるように構成されたコンピュータ読み取り可能なプログラム・コードは、
    (xtextQ(xtext))(p+1)/2=+xtextQ(xtext)(mod p)なら、第1の楕円曲線は楕円曲線E+であり、
    (xtextQ(xtext))(p+1)/2=−xtextQ(xtext)(mod p)なら、第1の楕円曲線は楕円曲線E-である(ここで、p = 3(mod 4)、 Q(xtext)=(xtext2+c(xtext)+b)ようにコンピュータに決定させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項6に記載の記録媒体。
  10. 更に、コンピュータに前記受信側で、前記手がかりxcを第2の楕円加算器に与えて、xqを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに前記受信側で、前記のメッセージ値xmと値xqと符号値gとを第2の楕円加算器に与えて、値xtextから平文を復元させるように構成されたコンピュータ読み取り可能なプログラム・コードとを含むことを特徴とする請求項6に記載の記録媒体。
  11. 平文メッセージを暗号化する方法であって、
    2つの乱数rとsを選択するステップと、
    楕円乗算器において、前記乱数r、第1の公開鍵/秘密鍵ペアからの公開鍵、第2の公開鍵/秘密鍵ペアからの秘密鍵を使用して現在の手がかりclueiの初期手がかり値clue0を生成するステップと、
    受信側に送信するため送信側コンピュータ・システムのメモリから値xtextiを有する1パーセルの平文を選択するステップと、
    x座標として値xtextiを有する第1の点を含む第1の楕円曲線、すなわち、第1の式2 = x3 + cx2 + ax + bで表される総ての楕円曲線E+と第2の式−y2 = x3 + cx2 + ax + bで表される総ての楕円曲線E-とからなる楕円曲線の集合から選択された楕円曲線ここで、a、b、cは既知の値である、を決定するステップと、
    前記の値xtextiと現在の手がかりclueiとを第1の楕円加算器に与えて、前記メモリに前記第1の楕円曲線上の第2の点x座標を表すメッセージ値miを生成するステップと、
    前記のメッセージ値miと現在の手がかりclueiとを前記第1の楕円加算器に与えて、前記第2の点が前記現在の手がかりclueiと第1の点の和であるかまたは第1の点から現在の手がかり clue i を減じた差であるかを表す符号値gを生成するステップと、
    ペア(mi、 g)で前記の暗号化されたメッセージを表すステップと、
    後続のパーセルについて、前記の現在の手がかりclueiおよび前記の乱数rとsを使用して後続の手がかりcluei+1を生成するステップを含む方法。
  12. さらに、送信側から受信側に前記乱数rとsを送信するステップと、
    前記送信側から前記受信側に前記の暗号化されたメッセージを送信するステップを含む請求項11に記載の方法。
  13. 前記公開鍵が前記受信側の公開鍵であり、前記秘密鍵が前記送信側の秘密鍵であることを特徴とする請求項12に記載の方法。
  14. x座標としてxtextiを有する第1の点を含む第1の楕円曲線を決定する前記ステップは、
    (xtextiQ(xtexti))(p+1)/2 = +xtextiQ(xtexti)(mod p)なら、前記第1の楕円曲線はE+であり、
    (xtextiQ(xtexti))(p+1)/2 = -xtextiQ(xtexti)(mod p)なら、前記第1の楕円曲線はE-である
    (ここで、p = 3(mod 4)で、 Q(xtexti)=(xtexti2+c(xtexti)+b)と決定するステップを含むことを特徴とする請求項11に記載の方法。
  15. 前記の後続の手がかりcluei+1を生成する前記ステップは、
    前記の乱数rと現在の手がかりclueiとを前記第1の楕円乗算器に与えて、積を生成するステップと、
    その積と前記乱数sとを前記第1の楕円加算器に与えるステップとを含むことを特徴とする請求項11に記載の方法。
  16. さらに、前記受信側で実行される、
    第2の楕円乗算器において、前記乱数r、前記の第1の公開鍵/秘密鍵ペアの秘密鍵、前記の第2の公開鍵/秘密鍵ペアの公開鍵から前記の初期手がかりclue0を決定するステップと、
    前記楕円曲線E+とE-の中から前記メッセージ値miが有効なx座標である前記第2の点を含む前記第1の楕円曲線を決定するステップと、
    前記の現在の手がかりclueiと、前記のメッセージ値miと、前記の符号値gとを第2の楕円加算器に与えて、xtextiを決定するステップと、
    現在の手がかりclueiと前記乱数rとsを使用して後続の手がかりcluei+1 を計算するステップを含むことを特徴とする請求項12に記載の方法。
  17. コンピュータに楕円曲線、すなわち、第1の式2 = x3 + cx2 + ax + bで表される楕円曲線E+と第2の式−y2 = x3 + cx2 + ax + bで表される楕円曲線E-とからなる楕円曲線ここで、a、b、cは既知の値である、の集合について楕円曲線代数を使用して平文メッセージを暗号化させるためのコンピュータ読み取り可能なプログラム・コードが埋込まれているコンピュータ使用可能な記録媒体であって、前記コンピュータ読み取り可能なプログラム・コードは、
    コンピュータに2つの乱数rとsを選択させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに前記乱数r、第1の公開鍵/秘密鍵ペアからの公開鍵、第2の公開鍵/秘密鍵ペアからの秘密鍵を使用して現在の手がかりclueiの初期手がかり値clue0を第1の楕円乗算器において生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータにメモリから値xtextiを有する1パーセルの平文を選択させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに前記楕円曲線の集合から選択された、x座標としてxtextiを有する第1の点を含む第1の楕円曲線を決定させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータにxtextiと現在の手がかりclueiを使用して、前記第1の楕円曲線上の第2の点のx座標を表すメッセージ値miをメモリに生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータにメッセージ値miと現在の手がかりclueiを第1の楕円加算器に与えて、前記第2の点が前記現在の手がかりclueiと第1の点の和であるかまたは第1の点から現在の手がかり clue i を減じた差であるかを表す符号値gを生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータにペア(mi、g)で前記の暗号化されているメッセージを表現させるように構成されたコンピュータ・プログラム読み取り可能なプログラム・コードと、
    コンピュータに後続のパーセルについて、前記の現在の手がかりclueiおよび前記乱数rとsを使用して後続の手がかりcluei+1を生成させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする記録媒体。
  18. さらに、コンピュータに送信側から受信側に前記乱数rとsを送信させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータに前記送信側から前記受信側に前記の暗号化されたメッセージを送信させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項17に記載の記録媒体。
  19. 前記公開鍵が、前記受信側の公開鍵であり、前記秘密鍵が前記送信側の秘密鍵であることを特徴とする請求項18に記載の記録媒体。
  20. コンピュータにx座標としてxtextiを有する第1の点を含む第1の楕円曲線を決定させるように構成された前記のコンピュータ読み取り可能なプログラム・コードは、
    (xtextiQ(xtexti))(p+1)/2=+xtextiQ(xtexti)(mod p)なら、第1の楕円曲線は楕円曲線E+であり、
    (xtextiQ(xtexti))(p+1)/2=−xtextiQ(xtexti)(mod p)なら、第1の楕円曲線は楕円曲線E-である(ここで、p = 3(mod 4)で、 Q(xtexti)=(xtexti2+c(xtexti)+b)ようにコンピュータに決定させるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項17に記載の記録媒体。
  21. コンピュータに前記の後続の手がかりcluei+1 を生成させるように構成された前記のコンピュータ読み取り可能なプログラム・コードは、
    コンピュータに前記の乱数rと現在の手がかりclueiとを前記第1の楕円乗算器に与えて、積を生成させるように構成されたコンピュータ読み取り可能なプログラム・コードと、
    コンピュータにその積と前記乱数sとを前記第1の楕円加算器に与えさせるように構成されたコンピュータ読み取り可能なプログラム・コードを含むことを特徴とする請求項17に記載の記録媒体。
  22. さらに、前記受信側のコンピュータが、
    前記乱数r、前記の第1の公開鍵/秘密鍵ペアの秘密鍵、および前記の第2の公開鍵/秘密鍵ペアの公開鍵から第1の楕円乗算器において前記の初期手がかりclue0を決定するステップと、
    前記の楕円曲線E+とE-からx座標としてメッセージ値miを有する前記第2の点を含む前記第1の楕円曲線を決定するステップと、
    前記の現在の手がかりclueiと、前記のメッセージ値miと、前記の符号値gとを第2の楕円加算器に与えて、xtextiを決定するステップと、
    現在の手がかりclueiと前記の乱数rとsとを使用して後続の手がかりcluei+1を計算するステップを実行するように構成されたプログラム・コードを含む請求項18に記載の記録媒体。
JP2000503629A 1997-07-18 1998-07-17 直接埋め込み方式による高速楕円曲線暗号化の方法と装置 Expired - Lifetime JP3862500B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US08/896,993 1997-07-18
US08/896,993 US6307935B1 (en) 1991-09-17 1997-07-18 Method and apparatus for fast elliptic encryption with direct embedding
PCT/US1998/014892 WO1999004531A1 (en) 1997-07-18 1998-07-17 Method and apparatus for fast elliptical encryption with direct embedding

Publications (2)

Publication Number Publication Date
JP2001510912A JP2001510912A (ja) 2001-08-07
JP3862500B2 true JP3862500B2 (ja) 2006-12-27

Family

ID=25407187

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2000503629A Expired - Lifetime JP3862500B2 (ja) 1997-07-18 1998-07-17 直接埋め込み方式による高速楕円曲線暗号化の方法と装置

Country Status (6)

Country Link
US (1) US6307935B1 (ja)
EP (1) EP0997016B1 (ja)
JP (1) JP3862500B2 (ja)
CA (1) CA2297059A1 (ja)
DE (1) DE69829967T2 (ja)
WO (1) WO1999004531A1 (ja)

Families Citing this family (59)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5271061A (en) * 1991-09-17 1993-12-14 Next Computer, Inc. Method and apparatus for public key exchange in a cryptographic system
CA2253009C (en) * 1997-11-04 2002-06-25 Nippon Telegraph And Telephone Corporation Method and apparatus for modular inversion for information security and recording medium with a program for implementing the method
JPH11242434A (ja) * 1998-02-26 1999-09-07 Hitachi Ltd 楕円曲線暗号実行方法及び暗号処理システム
US6724895B1 (en) 1998-06-18 2004-04-20 Supersensor (Proprietary) Limited Electronic identification system and method with source authenticity verification
JP3796993B2 (ja) * 1998-12-22 2006-07-12 株式会社日立製作所 楕円曲線暗号実行方法及び装置並びに記録媒体
US6611597B1 (en) * 1999-01-25 2003-08-26 Matsushita Electric Industrial Co., Ltd. Method and device for constructing elliptic curves
FR2791497B1 (fr) * 1999-03-26 2001-05-18 Gemplus Card Int Procedes de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de crytographie a cle publique de type courbe elliptique
US20020038420A1 (en) * 2000-04-13 2002-03-28 Collins Timothy S. Method for efficient public key based certification for mobile and desktop environments
AU2001290547A1 (en) * 2000-09-11 2002-03-26 Jinglong F. Zhang A method and apparatus employing one-way transforms
JP3794266B2 (ja) * 2000-11-08 2006-07-05 株式会社日立製作所 楕円曲線スカラー倍計算方法及び装置並びに記憶媒体
US7113594B2 (en) 2001-08-13 2006-09-26 The Board Of Trustees Of The Leland Stanford University Systems and methods for identity-based encryption and related cryptographic techniques
US7137000B2 (en) 2001-08-24 2006-11-14 Zih Corp. Method and apparatus for article authentication
JP4067818B2 (ja) 2001-12-10 2008-03-26 富士通株式会社 楕円曲線暗号装置、楕円曲線暗号プログラム及び楕円曲線暗号の演算方法
US7228417B2 (en) * 2002-02-26 2007-06-05 America Online, Inc. Simple secure login with multiple-authentication providers
US7290278B2 (en) 2003-10-02 2007-10-30 Aol Llc, A Delaware Limited Liability Company Identity based service system
EP1745572A4 (en) * 2004-04-30 2010-12-08 Utc Fire & Security Corp SECURITY SYSTEM COMMUNICATION WITH ENCRYPTION
US20060013387A1 (en) * 2004-07-14 2006-01-19 Ruei-Shiang Suen Method and system for implementing KASUMI algorithm for accelerating cryptography in GSM/GPRS/EDGE compliant handsets
US7483533B2 (en) * 2004-08-05 2009-01-27 King Fahd University Of Petroleum Elliptic polynomial cryptography with multi x-coordinates embedding
US7483534B2 (en) * 2004-08-05 2009-01-27 King Fahd University Of Petroleum Elliptic polynomial cryptography with multi y-coordinates embedding
US7607019B2 (en) * 2005-02-03 2009-10-20 Apple Inc. Small memory footprint fast elliptic encryption
US8204232B2 (en) * 2005-01-18 2012-06-19 Certicom Corp. Accelerated verification of digital signatures and public keys
WO2006076804A1 (en) 2005-01-21 2006-07-27 Certicom Corp. Elliptic curve random number generation
TWI305548B (en) * 2005-05-09 2009-01-21 Nippon Steel Corp Low core loss grain-oriented electrical steel sheet and method for producing the same
US7587047B2 (en) * 2005-06-22 2009-09-08 Apple Inc. Chaos generator for accumulation of stream entropy
US7664258B2 (en) * 2005-12-28 2010-02-16 Microsoft Corporation Randomized sparse formats for efficient and secure computation on elliptic curves
US8160245B2 (en) * 2007-03-07 2012-04-17 Research In Motion Limited Methods and apparatus for performing an elliptic curve scalar multiplication operation using splitting
US8102998B2 (en) * 2007-05-02 2012-01-24 King Fahd University Of Petroleum And Minerals Method for elliptic curve scalar multiplication using parameterized projective coordinates
US20080273695A1 (en) * 2007-05-02 2008-11-06 Al-Gahtani Theeb A Method for elliptic curve scalar multiplication using parameterized projective coordinates
DE102008061483A1 (de) * 2008-12-10 2010-06-24 Siemens Aktiengesellschaft Verfahren und Vorrichtung zum Verarbeiten von Daten
US8184803B2 (en) * 2008-12-29 2012-05-22 King Fahd University Of Petroleum And Minerals Hash functions using elliptic curve cryptography
US8165287B2 (en) * 2008-12-30 2012-04-24 King Fahd University Of Petroleum & Minerals Cryptographic hash functions using elliptic polynomial cryptography
US8705740B2 (en) 2008-12-30 2014-04-22 King Fahd University Of Petroleum And Minerals Elliptic curve-based message authentication code system and method
US20100169658A1 (en) * 2008-12-30 2010-07-01 Lahouari Ghouti Elliptic curve-based message authentication code
FR2947404B1 (fr) * 2009-06-30 2011-12-16 Sagem Securite Cryptographie par parametrisation sur une courbe elliptique
US8385541B2 (en) * 2010-02-18 2013-02-26 King Fahd University Of Petroleum And Minerals Method of performing elliptic polynomial cryptography with elliptic polynomial hopping
IT1401937B1 (it) * 2010-09-16 2013-08-28 St Microelectronics Srl Metodo di generazione di una firma digitale
US8954749B2 (en) 2012-04-06 2015-02-10 At&T Intellectual Property I, L.P. Methods, systems, and product for hashing using twisted tabulation
US10148285B1 (en) 2012-07-25 2018-12-04 Erich Schmitt Abstraction and de-abstraction of a digital data stream
US9291320B2 (en) 2013-01-30 2016-03-22 Cree, Inc. Consolidated troffer
US9690029B2 (en) 2013-01-30 2017-06-27 Cree, Inc. Optical waveguides and luminaires incorporating same
US10436969B2 (en) 2013-01-30 2019-10-08 Ideal Industries Lighting Llc Optical waveguide and luminaire incorporating same
US9869432B2 (en) 2013-01-30 2018-01-16 Cree, Inc. Luminaires using waveguide bodies and optical elements
US9442243B2 (en) 2013-01-30 2016-09-13 Cree, Inc. Waveguide bodies including redirection features and methods of producing same
US9625638B2 (en) 2013-03-15 2017-04-18 Cree, Inc. Optical waveguide body
US9366396B2 (en) 2013-01-30 2016-06-14 Cree, Inc. Optical waveguide and lamp including same
DE102013002184A1 (de) 2013-02-06 2014-08-07 Florian Thie Computerimplementiertes Verfahren zum Verschlüsseln von Daten
US10436970B2 (en) 2013-03-15 2019-10-08 Ideal Industries Lighting Llc Shaped optical waveguide bodies
US10209429B2 (en) 2013-03-15 2019-02-19 Cree, Inc. Luminaire with selectable luminous intensity pattern
US10400984B2 (en) 2013-03-15 2019-09-03 Cree, Inc. LED light fixture and unitary optic member therefor
US9920901B2 (en) 2013-03-15 2018-03-20 Cree, Inc. LED lensing arrangement
US9366799B2 (en) 2013-03-15 2016-06-14 Cree, Inc. Optical waveguide bodies and luminaires utilizing same
US10795858B1 (en) 2014-02-18 2020-10-06 Erich Schmitt Universal abstraction and de-abstraction of a digital data stream
US11719882B2 (en) 2016-05-06 2023-08-08 Ideal Industries Lighting Llc Waveguide-based light sources with dynamic beam shaping
US10416377B2 (en) 2016-05-06 2019-09-17 Cree, Inc. Luminaire with controllable light emission
US20180063105A1 (en) * 2016-09-01 2018-03-01 AtCipher.com Limited Management of enciphered data sharing
US10484173B2 (en) * 2017-01-03 2019-11-19 Nxp B.V. X-only generic mapping function for PACE protocol
US11146397B2 (en) * 2017-10-31 2021-10-12 Micro Focus Llc Encoding abelian variety-based ciphertext with metadata
CN108446101A (zh) * 2018-06-06 2018-08-24 北京信任度科技有限公司 多物理噪声源的随机数产生方法及产生系统
CN110348229B (zh) * 2019-06-11 2021-09-21 北京思源理想控股集团有限公司 数据的加密方法及装置、数据的解密方法及装置

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
ATE128297T1 (de) * 1991-03-14 1995-10-15 Omnisec Ag Verschlüsselungssystem mit öffentlichem schlüssel unter verwendung elliptischer kurven über ringe.
US5272755A (en) * 1991-06-28 1993-12-21 Matsushita Electric Industrial Co., Ltd. Public key cryptosystem with an elliptic curve
US5351297A (en) * 1991-06-28 1994-09-27 Matsushita Electric Industrial Co., Ltd. Method of privacy communication using elliptic curves
US5271061A (en) * 1991-09-17 1993-12-14 Next Computer, Inc. Method and apparatus for public key exchange in a cryptographic system
US5159632A (en) * 1991-09-17 1992-10-27 Next Computer, Inc. Method and apparatus for public key exchange in a cryptographic system
US5442707A (en) * 1992-09-28 1995-08-15 Matsushita Electric Industrial Co., Ltd. Method for generating and verifying electronic signatures and privacy communication using elliptic curves
US5627893A (en) * 1992-12-22 1997-05-06 Telstra Corporation Limited Cryptographic method
US5497423A (en) 1993-06-18 1996-03-05 Matsushita Electric Industrial Co., Ltd. Method of implementing elliptic curve cryptosystems in digital signatures or verification and privacy communication
CA2129203C (en) * 1994-07-29 2010-01-12 Gordon B. Agnew Public key cryptography utilizing elliptic curves
US5737424A (en) * 1996-06-04 1998-04-07 Software Security, Inc. Method and system for secure distribution of protected data using elliptic curve systems
CA2310588A1 (en) * 1997-12-05 1999-06-17 Secured Information Technology, Inc. Transformation methods for optimizing elliptic curve cryptographic computations
UA57827C2 (uk) * 1998-02-18 2003-07-15 Інфінеон Текнолоджіз Аг Спосіб криптографічної обробки з використанням еліптичної кривої і пристрій для криптографічної обробки, що містить процесорний вузол
CN1235446A (zh) * 1998-03-05 1999-11-17 松下电器产业株式会社 椭圆曲线变换装置、利用装置和利用系统

Also Published As

Publication number Publication date
DE69829967D1 (de) 2005-06-02
US6307935B1 (en) 2001-10-23
EP0997016B1 (en) 2005-04-27
JP2001510912A (ja) 2001-08-07
EP0997016A1 (en) 2000-05-03
CA2297059A1 (en) 1999-01-28
WO1999004531A1 (en) 1999-01-28
DE69829967T2 (de) 2006-04-27

Similar Documents

Publication Publication Date Title
JP3862500B2 (ja) 直接埋め込み方式による高速楕円曲線暗号化の方法と装置
US5805703A (en) Method and apparatus for digital signature authentication
US5159632A (en) Method and apparatus for public key exchange in a cryptographic system
EP0503119B1 (en) Public key cryptographic system using elliptic curves over rings
Keerthi et al. Elliptic curve cryptography for secured text encryption
JPS5950068B2 (ja) 公開キ−式の暗号装置
Liao et al. On the Security of Public-Key Algorithms Based on Chebyshev Polynomials over the Finite Field $ Z_N$
Vanstone et al. Elliptic curve cryptosystems using curves of smooth order over the ring Z/sub n
EP0952697B1 (en) Elliptic curve encryption method and system
WO2012156254A1 (en) A method for performing a group digital signature
Jeng et al. An ECC-based blind signature scheme
Rachmawati et al. Instant Messaging Security Using Affine Cipher and RSA CRT Algorithm
JP3050313B2 (ja) 楕円曲線変換装置、利用装置及び利用システム
Ghadi Mathematical Modelling of Engineering Problems
KR100368204B1 (ko) 정규 기저를 이용한 역원 계산 알고리즘
Blackburn et al. Certification of secure RSA keys
JP3240723B2 (ja) 通信方法、秘密通信方法及び署名通信方法
SULTAN ElGamal Cryptosystem
Rohith et al. FPGA implementation of 16 bit RSA cryptosystem for text message
JP4502817B2 (ja) 楕円曲線スカラー倍計算方法および装置
Gupta et al. Enhanced ECC-driven Text Encryption Scheme using Chaotic Maps and Rhotrices.
Diko et al. RSA & EXTENDED EUCLIDEAN ALGORITHM WITH EXAMPLES OF EXPONENTIAL RSA CIPHERS, RSA EXAMPLE SOLUTION WITH EXTENDED EUCLIDEAN ALGORITHM
Rafiammal Implementation of Elliptic Curve Scalar Multiplier on FPGA
Ahmed et al. Public Key Cryptography Algorithm Using Binary Manipulation and Chinese Remainder Theorem
JPH11258986A (ja) 暗号化装置、復号化装置、暗号システムおよびそのプログラム記録媒体

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20050817

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20051117

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20051125

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060216

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20060627

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060808

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20060829

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20060926

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

S533 Written request for registration of change of name

Free format text: JAPANESE INTERMEDIATE CODE: R313533

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091006

Year of fee payment: 3

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091006

Year of fee payment: 3

S531 Written request for registration of change of domicile

Free format text: JAPANESE INTERMEDIATE CODE: R313531

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091006

Year of fee payment: 3

RD02 Notification of acceptance of power of attorney

Free format text: JAPANESE INTERMEDIATE CODE: R3D02

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091006

Year of fee payment: 3

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20101006

Year of fee payment: 4

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20111006

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20121006

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20131006

Year of fee payment: 7

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

EXPY Cancellation because of completion of term