Elliptic curve cryptosystem optimization using two phase key generation
View Patent ↗A computer-implemented method of generating an elliptic curve cryptosystem (ECC) signature includes the steps of: generating a first random key (k 1 ) having n bits, where n is a natural number; calculating a first ECC point (V) from k 1 and a base point; and storing k 1 and V securely in a computer-readable medium. To digitally sign electronic data, the method further includes the steps of generating a second random key (k 2 ), where k 2 has fewer than n bits; calculating a second ECC point (Q) from V and k 2 ; and digitally signing electronic data using Q.
1. A computer-implemented method of generating an elliptic curve cryptosystem (ECC) signature comprising:
a. generating a first random key (k 1 ) having n bits, wherein n is a natural number;
b. calculating a first ECC point (V) from k 1 and a base point;
c. storing k 1 and V securely in a computer-readable medium;
d. generating a second random key (k 2 ) by a signature generator, wherein k 2 has fewer than n bits;
e. calculating a second ECC point (Q) by the signature generator from V and k 2 ;
f. digitally signing electronic data by the signature generator using Q and k 1 *k 2 .
2. The method of claim 1 , wherein k 2 has about n/2 bits.
3. The method of claim 1 , wherein said computer-readable medium comprises one of: a universal serial bus (USB) token, a read-only memory (ROM), a hard disk drive, a memory, a processor-based token, or a smart card.
4. The method of claim 1 , further comprising:
g. destroying k 2 after said step f.
5. The method of claim 4 , further comprising:
h. generating a new random key (k 3 ), wherein k 3 is not the same as k 2 ;
i. calculating a new ECC point (Q 1 ) from V and k 3 ; and
j. digitally signing electronic data using Q 1 .
6. An apparatus for generating an elliptic curve cryptosystem (ECC) signature comprising:
a computer interface, operative to send and receive electronic data from a computer;
a computer-readable medium storing a first ECC point (V) calculated from a first random key k 1 , and a base point (P); and
a processor, coupled to said computer interface and to said computer readable medium, the processor adapted to execute program instructions that cause the processor to:
generate a second random key (k 2 ), wherein k 2 has fewer bits than k 1 ;
calculate a second ECC point (Q) from V and k 2 ; and
digitally sign electronic data using Q.
7. The apparatus of claim 6 , wherein the apparatus is a USB token and wherein said computer interface is a USB interface.