 |
|
|
|
|
|
 Title: |
WO9836526A1:
CYCLOTOMIC POLYNOMIAL CONSTRUCTION OF DISCRETE LOGARITHM CRYPTOSYSTEMS OVER FINITE FIELDS[French]
[ Derwent Title ]
|
Country:
Kind: |
WO World Intellectual Property Organization (WIPO)
A1 INTERNATIONAL APPLICATION PUBLISHED WITH INTERNATIONAL SEARCH REPORT i
|
| |
| Inventor: |
LENSTRA, Arjen, K.; 114 West Oak Street, Basking Ridge, NJ 07920, United States of America
|
| Assignee: |
CITIBANK, N.A., 399 Park Avenue, New York, NY 10043, United States of America
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-08-20
/ 1997-09-26
|
| Application Number: |
WO1997US0017304
|
| IPC Code: |
Advanced:
G09C 1/00;
H04L 9/30;
Core:
H04L 9/28;
more...
IPC-7:
H04L 9/30;
|
| ECLA Code: |
H04L9/30L;
|
| Priority Number: |
| 1997-02-14 |
US1997000800669 |
|
| Abstract: |
Cyclotomic polynomials are used to construct subgroups of multiplicative groups of finite fields that allow very efficient implementation of discrete logarithm based public key cryptosystems, including public key encryption schemes and digital signature schemes. A field is represented with an optimal normal basis, and a generator of a subgroup of the multiplicative group of the field is used to form a public key.
[French]
|
| Representative Image: |
[Show "fr" image]
|
| Attorney, Agent or Firm: |
CALVARUSO, Joseph, A. ;
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Designated Country: |
AL AM AT AU AZ BA BB BG BR BY CA CH CN CU CZ DE DK EE ES FI GB GE GH HU IL IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK SL TJ TM TR TT UA UG UZ VN YU ZW,
European patent:
AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE,
OAPI patent:
BF BJ CF CG CI CM GA GN ML MR NE SN TD TG,
ARIPO patent:
GH KE LS MW SD SZ UG ZW,
Eurasian patent:
AM AZ BY KG KZ MD RU TJ TM
|
| Family: |
Show 14 known family members
|
First Claim:
Show all claims |
What is claimed is: 1. A method of determining public and private keys for a public key cryptosystem, comprising the steps of.
|
Description
Expand description |
+ CYCLOTOMIC POLYNOMIAL CONSTRUCTION OF
DISCRETE LOGARITHM CRYPTOSYSTEMS OVER FINITE
+ BACKGROUND OF THE INVENTION
The present invention relates to data security, encryption, and, generating and using electronic signatures to verify the identity of a communicating party.
+ SUMMARY OF THE INVENTiON In accordance with an aspect of this invention, a method of and an apparatus for determining public and private keys for a public key cryptosystern comprises selecting a first prime number, obtaining a cyclotomic polynomial evaluated at the first prime number, obtaining a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finding a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, obtaining a public value based on the generator and a selected integer, forming the public key to include the first and second prime numbers, the generator and the public value, and forming the private key to include the selected integer.
In accordance with a further aspect of this invention, the finite field may be represented with an optimal normal basis.
+ Brief Description of the Drawings
Fig. 1A is a flowchart illustrating system setup according to the ElGamal scheme; Fig. IB is a flowchart illustrating signature generation according to the ElGamal scheme; Fig. IC is a flowchart illustrating signature verification according to the ElGamal scheme; Fig. 2A is a flowchart illustrating system setup according to the Schnorr and DSA schemes; Fig. 2B is a flowchart illustrating signature generation according to the Schnorr scheme; Fig. 2C is a flowchart illustrating signature verification according to the Schnorr scheme; Fig. 2D is a flowchart illustrating signature generation according to the DSA scheme; Fig. 2E is a flowchart illustrating signature verification according to the DSA scheme; Fig. 3A is a flowchart illustrating system setup according to the ECDSA scheme; Fig. 3B is a flowchart illustrating signature generation according to the ECDSA scheme; Fig. 3C is a flowchart illustrating signature verification according to the ECDSA scheme; Fig. 4A is a flowchart illustrating system setup according to the present invention; Fig. 4B is a flowchart illustrating signature generation according to the present invention; Fig. 4C is a flowchart illustrating signature verification according to the present invention; Fig. 4D is a table of cyclotomic polynomial coefficients; Fig. 4E is a flowchart illustrating a DES system setup according to the present invention; Fig. 4F is a flowchart illustrating encryption for the DES system setup according to the present invention; Fig. 4G is a flowchart illustrating decryption for the DES system setup according to the present invention; Fig. 4H is a flowchart illustrating encryption for the ElGamal system setup according to the present invention; Fig. 4J is a flowchart illustrating decryption for the ElGamal system setup according to the present invention; Fig. 5A is a table of results for comparing signature generation performance of schemes for public key cryptosystems; Fig. 5B is a table of results for comparing signature verification performance of schemes for public key cryptosystems; Fig. 6 is a chart showing the message encrypted and decrypted to obtain the performance results of Figs. 5A and 5B; Figs. 7A- I I D are charts showing the public key, private key, signature, and signature generation parameter k, for each of the public key cryptosystems in the examples used to obtain the performance results of Figs. 5A and 5B; and Fig. 12 is a block diagram of an environment in which the present invention may be implemented. ###
+ DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Cyclotomic polynomials are used to construct subgroups of multiplicative groups of finite fields that allow very efficient implementation of discrete logarithm based public key cryptosystems, including public key encryption schemes and digital signature schemes. A field is represented with an optimal normal basis, and a generator of a subgroup of the multiplicative group of the field is used to form a public key. Depending on the type of application and implementation, public key encryption according to the cyclotomic scheme may be up to three times faster than schemes using more conventional choices of subgroups or finite fields.
|
| Other Abstract Info: |
DERABS G1998-457468
DERABS G1998-457468
|
|
 Nominate this for the Gallery...
|
|
