Cryptography - History and Basics
Cryptography - Symmetric Key Algorithms
Cryptography - Asymmetric Key Algorithms
Cryptography - Hash Functions & Digital Signatures
Asymmetric Key Algorithms (Public-Key) - Definition
Public-Key cryptography is a relatively new system (compared to symmetric cryptography) and relies on the usage of a pair of keys. This pair is the private key and the public key. The generation of the key pair is based on cryptographic algorithms to produce a mathematical one-way function.
In this system, any person can encrypt a message using the receivers public key. The encrypted message can then only be decrypted with the receivers private key. Authentication is also possible when the sender is encrypting a digital signature with his private key. Receivers with the matching public key can verify this signature to be valid by decrypting with the public key.
Alternative terms: public key cryptography or Asymmetric key cryptography
Advantage of Asymmetric Key Cryptography
Key distribution is not an issue. Public Keys are meant to be made publicly available. There is no overhead for secret key distribution.
Nonrepudiation is ensured because a party cannot dispute its authorship of a document or communication.
Scalability the number of keys is directly proportional to the number of participants in the system. Each party has two keys.
Number of Keys = n * 2
Disadvantages of Asymmetric Key Cryptography
Slow public-key cryptography is notable slower than symmetric key cryptography
RSA - Rivest, Shamir, and Adleman
Invented in 1977, the most famous public-key cryptosystem is named after its creators. They patented the algorithm and formed a commercial organization (RSA Security). Today, the RSA algorithm has been released into the public domain and is widely used in commercial and opensource products to archieve secure communication. RSA depends on the computational difficulty in factoring large prime numbers.
Key Generation[1]
1: two large prime numbers (approximately 200 digits each) are required -> p q
2: compute the product of those two numbers n = pq
3: now we need the Carmichael function λ, and the least common multiple lcm to compute:
λ(n), λ(n) = lcm(λ(p),λ(q)), since p and q are prime, λ(p) = p − 1 and likewise λ(q) = q − 1.
Hence λ(n) = lcm(p − 1, q − 1).
(p - 1) and (q -1) are relatively prime, the two numbers have no common factors other than 1.
4: choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1. gcd is greatest common divisor.
5: compute d as d ≡ e−1 (mod λ(n)). This means d is the modular multiplicative inverse of e modulo λ(n)`.
The public key consists of n and e
The private key is d
p, q, and λ(n) must be kept secret or have to be discarded because they can be used to calculate d
Key Distribution
Bob wants to send a secret message to Alice. Bob needs to know the public key of Alice to encrypt the message. Alice sends Bob her public key (n, e) in a reliable, but not necessarily secret way. Alice keeps her private key (d) and will never distribute it.
Encryption
The message Bob wants to send is m and he is in the possession of Alices public-key n, e.
c = m^e mod n
This can be done rather quickly using modular exponentiation. Bob then send c to Alice.
Decryption
Alice can recover Bobs message m by using her private key d.
m = c^d mod n
El Gamal
The El Gamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. Dr. Taher El Gamal published an article in 1985, describing how the mathematics behind the Diffie-Hellman algorithm could be extended to support an entire public-key cryptosystem. El Gamal did not obtain a patent for his extension of Diffie-Hellman, unlike the then patented RSA technology.
El Gamal has a major disadvantage which is that it produces a 2:1 expansion in size from plaintext to ciphertext. This presents an issue when encrypting long messages.
ECC - Elliptic Curve Cryptography
In 1985, two mathematicians independently proposed the application of elliptic curve cryptography to develop a secure cryptographic system. Neal Koblitz from the University of Washington and Victor Miller from IBM, suggested to use the elliptic curve discrete logarithm problem as the basis for this system.
Any elliptic curve can be defined by the following equation:
y^2 = x^3 + ax + b
In this equation x, y, a, and b are all real numbers. Each elliptic curve has a matching elliptic curve group made up of the points of the elliptic curve along with the point O, which is located in infinity. Two points within in the same elliptic curve group (P, Q) can be added with an elliptic curve addition algorithm.
P + Q
The problem is extended by assuming that Q is a multiple of P:
Q = x^P
Mathematicians believe that it is extremely difficult to find x, even if P and Q are known. It is widely accepted that this problem is harder to solve than both the prime factorization problem of RSA and the standard discrete logarithm problem of Diffie-Hellman/El Gamal. Because of this, a 160-bit ECC key is cryptographically equivalent to a 1024-bit RSA key.
For further reading on the detailed mathematics behind ECC, I can recommend the following tutorial
Alteration of public keys
As mentioned earlier in this posting, public keys are meant to be in the public domain. The advantage of the systems is that communication can be encrypted between parties without previous interaction or knowledge. One common attack vector to public-key cryptography is exactly targeting this strength.
In a so-called man in the middle attack, the communication of public keys is intercepted by a third party and then modified public keys are provided instead. Intercepted messages are decrypted and re-encrypted by the attacker to avoid suspicion.
This is possible on all insecure media (e.g. wireless, public networks). One approach to prevent such attacks involves the usage of a PKI. It describes a set of policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates and manage public-key encryption.
PKI has potential weaknesses like the correctness of a public key when a certificate is issued or the overall security resistance of an authority organization.
The PKI system is commonly used to provide encryption for web traffic via TLS.