Elliptic curves and public key cryptography

By Dan Klanke, Brandon Myers, Antong Li and Chenghao Cai

Abstract

Along with the rapid development of modern communication network, especially the Internet, using the Internet as an information communication and processing is becoming more and more common. Traditional social affairs and business operation model are facing the unprecedented impact. At present, both governments and enterprises are integrated into the Internet revolution, from its traditional management mode to the network schema evolution. The future of e-government, e-commerce, electronic business will become an irreversible trend. In the growing network activities, people are becoming more and more concerned about the information security problem, which includes: confirming customer's true identity, personal or confidential information system and data protection, preventing illegal data modification, and non-repudiation for the behavior under the network environment.

Thus improving the security level of cryptography, the most core technology in information security, is brought to the table. Based on the difficulty of solving the discrete logarithm problem on a general elliptic curve, Neal Koblitz and Victor S. Miller proposed an elliptic curve cryptosystem. Cryptosystem based on elliptic curves offer the benefits of good realization using hardware and software, smaller bandwidth, smaller memory and etc. These benefits make elliptic curve cryptosystems be a new promising area in public-key cryptography.

In this report, the principal of public key cryptography is discussed, represented by the asymmetric cryptography Diffie-Hellman and RSA systems, which are based on number theory. Then, the properties and application of elliptic curve cryptosystem, together with the operation guides are explained. Finally, the reasons of causing the difference of asymmetric cryptography and elliptic curve cryptography deepen the understanding of the algebraic geometry field.

Intro to Public Key Cryptography

Public key cryptography also known as asymmetric cryptography refers to a cryptographic algorithm which requires two separate keys one of which is secret and one of which is public. Although different, the two parts of this key pair are mathematically linked. The public key is used to encrypt plaintext or to verify a digital signature; whereas the private key is used to decrypt ciphertext or to create a digital signature. The term "asymmetric" stems from the use of different keys to perform these opposite functions, each the inverse of the other.

Cryptography is a way for two people, commonly referred to as Alice (A) and Bob (B), to communicate over an insecure communications channel without an opponent, Eve (E), intercepting what is being said. It provides the foundation for key management and digital signatures, both integral parts of any cryptosystem. Below is a pictorial representation illustrating the general idea of key exchange.

Usage / Current Applications

Key Management:
Key Management entails the generation, exchange, storage, use, and replacement of keys. It includes cryptographic protocol design, key servers, user procedures, and other relevant protocols. Successful key management is critical to the security of a cryptosystem.

Digital Signatures:
A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, such that the sender cannot deny having sent the message and that the message was not altered in transit.

Principle of Operation

Public and private keys:
Alice and Bob each have a key, some number or mathematical procedure that can be applied to messages, composed of a public piece and a private piece. The private pieces of these keys are never transmitted, while the public pieces are accessible to everyone.

Based on mathematics:
Public-key algorithms are based on mathematical problems which currently admit no efficient solution that are inherent in certain integer factorization, discrete logarithm, and elliptic curve relationships.

Authentication:
Alice and Bob may also have public and private signatures, which work similarly to the keys. If Alice wants Bob to know that the message he receives from her is authentic, she’ll apply a private signature to some authentication message before sending it; when Bob wants to know that it’s hers, he’ll apply the easily accessible public part of her signature to that, which will return the authentication.

Asymmetric Cryptography Systems

First Generation:
Internet communications have been secured by the first generation of public key cryptographic algorithms developed in the mid-1970's. Notably, they form the basis for key management and authentication for IP encryption (IKE/IPSEC), web traffic (SSL/TLS) and secure electronic mail. Examples of such are the Diffie – Hellman and RSA methods.

Diffie-Hellman:
Diffie–Hellman key exchange (D–H) is a specific method of exchanging cryptographic keys. It is a first generation of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher, so that a third party cannot intercept the message. The Diffie-Hellman method makes use of certain one-way functions called trap-door functions, to make it almost impossible to decipher encrypted data without a key.

RSA:
Known as one of the first practicable public-key cryptosystems and is yet widely used for secure data transmission. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977.

Intro to elliptic curves in public key cryptography

In 1985, two American mathematician Neal Koblitz and Victor S. Miller suggested the use of elliptic curves in cryptography for the first time independently. Before this, another algorithm called Rivest-Shamir-Adleman (RSA) is already published in 1970s. RSA is the very first well-established public key cryptosystem and it is wildly used after publishing. Elliptic Curve Cryptography (ECC) often used to compare with RSA after Koblitz and Miller suggested it. According to an IEEE article Performance Analysis of Identity Management in the Session Initiation Protocol by Rebahi, Pallares, Nguyen and etc, ECC encryption only need 160-bit keys to provide equivalent level of security while RSA encryption needs 1024 bits. More details for the key size is shown in the following table:

Also, in another paper The Advantages of Elliptic Curve Cryptography For Wireless Security written by K. Lauter in February 2004, she wrote “Wireless devices are rapidly becoming more dependent on security features such as the ability to do secure email, secure Web browsing, and virtual private networking to corporate networks, and ECC allows more efficient implementation of all of these features.” So ECC is particularly crucial in small cards or portable devices where CPU consumption, battery life and memory usage are limited. In this high-technology era, ECC is extremely wild used.

Even though ECC is efficient, it has a few drawbacks just like other algorithms. ECC requires more complicated operation than RSA, so it is harder to verify whether a specific implementation is correct or not. Therefore ECC has higher possibility of operation errors. However, ECC is still one of the most efficient and popular cryptography so far.

Conclusion

With the development and application of information technology, the problem of information security becomes more and more important. In order to improve the security, secrecy and reliability of communication, we need cryptosystem of high dependability and good security. The elliptic curve cryptosystem provides the highest strength of any cryptosystem known. Because its shorter key size, less computation, less memory space and lower bandwidth, the application prospect in information field of the elliptic curve cryptosystem will keep growing as it become more sophisticated though years of research and practice.

Reference:

Hendrix, Joe. April 8, 2013. Elliptic Curve Cryptography.
http://www.linuxjournal.com/content/elliptic-curve-cryptography

Leslie, Martin. Class Handout.
http://math.arizona.edu/~mleslie/files/handout.pdf

January 15, 2009. The Case for Elliptic Curve Cryptography.
http://www.nsa.gov/business/programs/elliptic_curve.shtml

Class Handout. Elliptic Curves in Public Key Cryptography: The Diffie Hellman Key Exchange Protocol and its Relationship to the Elliptic Curve Discrete Logarithm Problem.
http://ocw.mit.edu/courses/mathematics/18-704-seminar-in-algebra-and-number-theory-rational-points-on-elliptic-curves-fall-2004/projects/haraksingh.pdf

Brow, Elaine. December 2010. Elliptic Curve Cryptography.
http://www.math.hmc.edu/~ursula/teaching/math189/finalpapers/elaine.pdf

Rebahi. Y, Pallares. J. J, Nguyen. T.M, and etc, 2008, Performance Analysis of Identity Management in the Session Initiation Protocol
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4493606&isnumber=4493499&tag=1

K. Lauter, February 2004, The Advantages of Elliptic Curve Cryptography For Wireless Security
http://research.microsoft.com/en-us/um/people/klauter/IEEEfinal.pdf