Elliptic Curve Cryptography - Elliptic Curves: Number Theory and Cryptography - page 168

Chapter 6
Elliptic Curve Cryptography
In this chapter, we'll discuss several cryptosystems based on elliptic curves,
especially on the discrete logarithm problem for elliptic curves. We'll also
treat various related ideas, such as digital signatures.
One might wonder why elliptic curves are used in cryptographic situations.
The reason is that elliptic curves provide security equivalent to classical sys-
tems while using fewer bits. For example, it is estimated in [12] that a key
size of 4096 bits for RSA gives the same level of security as 313 bits in an
elliptic curve system. This means that implementations of elliptic curve cryp-
tosystems require smaller chip size, less power consumption, etc. Daswani and
Boneh [14] performed experiments using 3Com's PalmPilot, which is a small
hand-held device that is larger than a smart card but smaller than a laptop
computer. They found that generating a 512-bit RSA key took 3.4 minutes,
while generating a 163-bit ECC-DSA key to 0.597 seconds. Though certain
procedures, such as signature verifications, were slightly faster for RSA, the
elliptic curve methods such as ECC-DSA clearly offer great increases in speed
in many situations.
6.1 The Basic Setup
Alice wants to send a message, often called the plaintext ,toBob. In
order to keep the eavesdropper Eve from reading the message, she encrypts
it to obtain the ciphertext . When Bob receives the ciphertext, he decrypts
it and reads the message. In order to encrypt the message, Alice uses an
encryption key . Bob uses a decryption key to decrypt the ciphertext.
Clearly, the decryption key must be kept secret from Eve.
There are two basic types of encryption. In symmetric encryption ,the
encryption key and decryption key are the same, or one can be easily deduced
from the other. Popular symmetric encryption methods include the Data
Encryption Standard (DES) and the Advanced Encryption Standard (AES,
often referred to by its original name Rijndael ). In this case, Alice and Bob