Public Key Encryption Algorithms
From Computing and Software Wiki
Public Key Encryption is also known as asymmetric cryptographyR1. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.
Contents |
Public Key Encryption
How does Public Key Encryption work?
The user has a pair of keys - public key and private key. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
Advantage over Symmetric Encryption
Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.
Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.
Digital signature to ensure authenticity
The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it.
Mathematical Theory
Many public key encryption algorithms are based on “Trap Door function”. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.
RSA
What is RSA?
RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.
Mathematical Theory
The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.
Speed
RSA is much slower than DES and other symmetric cryptosystems.
A Working Example
1. choose 2 prime numbers:
P=11, Q=3
2. compute N=P*Q:
N=11*3=33
3. compute L=(P-1)*(Q-1):
L= (11-1)*(3-1) = 10*2=20
4. choose E>1 and coprime to L:
Choose E=3
5. compute D such that E*D = 1 mod L:
D = 7 such that D*E =7*3 = 21 = 1 mod 20
6. public key is (N, E), private key is (N, D):
PK = (33, 3), SK= (33, 7)
7. Encrypt message using PK with C = M^E mod N:
Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13
8. Decrypt cipher text using SK with M' = C^D mod N:
Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7
Elliptic curve cryptography
What is ECC?
Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields.
Mathematical Theory
The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.
An elliptic curve has the following form:
y^2=x^3+ax+b.
The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.
Efficiency
Elliptic curves cryptography is more efficient with respect to key size.
Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key. However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.
Rabin cryptosystem
Rabin Cyptosystem is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization.
For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.
Rabin system is more secure than RSA.
References
[R1] http://en.wikipedia.org/wiki/Public-key_cryptography
