Asymmetric cryptography

Asymmetric cryptography is also called public key cryptography. Asymmetric keys are generated in pairs (encrypting and decrypting). The keys can be interchangeable meaning a key could both encrypt and decrypt, but that is not a requirement. The typical use, however, is to generate a pair of keys and keep one private and the other public. This section describes the three foundational public key cryptograms: RSA, Diffie-Hellman, and Elliptical Curves.

Note that unlike symmetric key counts in a mesh where any node can communicate with any other node, asymmetric cryptography only requires 2n keys or O(n).

The first asymmetric public key encryption method described is the Rivest-Shamir-Adleman algorithm, or RSA, developed in 1978. It is based on a user finding and publishing the product of two large prime numbers and an auxiliary value (public key). The public key can be used by anyone to encrypt a message but the prime factors are private. The algorithm operates as follows:

Find two large primes, p and q
n = pq
φ(n) =(p1)(q-1)
Public key: Choose an integer e so that 1<e<φ(n), e is coprime to φ(n); a typical value is 2¹⁶ + 1 = 65537
Private key: Compute d to solve the congruence relation de≡1 (mod φ(n))

Therefore, to encrypt a message using the public key (n,e) and to decrypt a message using the private key (n,d):

Encrypt: Ciphertext = (plaintext)^e mod n
Decrypt: Plaintext = (ciphertext)^d mod n

It is often the case that artificial padding is injected into m before encryption to avoid cases of short messages failing to produce good ciphertext.

Perhaps the best-known form of asymmetric key exchange is the Diffie-Hellman key exchange process (named after Whitfield Diffie and Martin Hellman). Typical of asymmetric cryptography is the notion of a Trapdoor Function which takes a given value A and produces an output B. However, trapdoor function B does not produce A.

The Diffie-Hellman method of key exchange allows two parties (Alice A and Bob B) to exchange keys without any previous knowledge of any shared secret key s. The algorithm is based on the plaintext exchange of a starting prime number, p, and a prime generator. The generator g is a primitive root modulo p. Let Alice's private key be a and Bob's private key be b. Then, A=g^a mod p and B=g^b mod p. Alice computes the secret key as s=B^a mod p and Bob computes the secret key as s=B^a mod p.

In general, (g^a mod p)^b mod p = (g^b mod p)^a mod p:

Diffie-Hellman key exchange. The process begins with the plaintext exchange of an agreed upon prime and generator of prime. With an independent private key generated by Alice and Bob, the public keys are generated and sent in plaintext over the network. This is used to generate a secret key used for encryption and decryption.

The strength of this form of secure key exchange is generating a true random number for each private key. Even the slight predictability of a pseudo-random number generator (PRNG) can lead to breaking the encryption. However, the principal issue is the lack of authentication which can lead to an MITM attack.

The other form of key exchange is Elliptic-Curve Diffie-Hellman (ECDH) and was proposed by Koblitz and Miller in 1985. It is based on the algebra of elliptic curves over a finite field. NIST has endorsed ECDH and the NSA allows ECDH for top-secret material using 384-bit keys. Elliptic Curve Cryptography (ECC) shares these basic tenets regarding the properties of an elliptical curve:

Symmetric about the x-axis
A straight line will intersect the elliptic curve at no more than three points

The process of ECC starts with drawing a straight line from a given point on the edge towards MAX. A line is drawn from point A to B. A dot function is used to draw a line between two points and then to draw a line straight up (or down) from the new unlabelled intersection to its counterpart on the positive or negative y-axis. This process is repeated n times, where n is the key size.

This process is analogous to seeing the end results of a pool table after a ball has been hit and strikes the cushions many times. An observer seeing the ending location of the ball would have a difficult time determining where the original location of the ball was.

MAX corresponds maximum value on the x-axis, placing a limit on how far a vertex will stretch. If by chance the vertex is greater than MAX, the algorithm forces the value that would have extended beyond the MAX limit and sets a new point x-MAX distance away from the origin A. MAX is equivalent to the key size being used. A large key size results in more vertices being constructed and increasing strength of secrecy. Essentially this is a wrap around function:

Elliptical Curve Cryptography (ECC). Here is a standard elliptical curve on an x, y-axis. The process starts by following straight line paths from a given point A to a second point and locating the third new unlabelled intersection. A line is drawn to the opposite but identical y plane coordinate which now becomes a labeled entity. The process continues for n points which correspond to the key length.

Elliptical curves are becoming prevalent over RSA. Modern browsers are capable of supporting ECDH, which is the preferred method of authentication over SLL/TLS. ECDH is also found in Bitcoins, as we will see later, and several other protocols. RSA is only used now if an SSL certificate has a matching RSA key.

The other advantage is that the key lengths can be kept short and still have the same cryptographic strength as a legacy method. For example, a 256-bit key in ECC is equivalent to a 3072-bit key in RSA. The importance of this should be considered for constrained IoT devices.

Table of Contents for Asymmetric cryptography

Create new playlist

Sign In

Sign Up

Table of Contents for
Asymmetric cryptography