🏠 vigrey.com

Cryptographic Concepts - Asymmetric Cryptography

2017-10-02 - [46] 7:16

Definitions

In this and further Cryptographic Concepts series posts, I will be using a few terms that I feel I should define ahead of time.

Asymmetric Key Cryptography

Asymmetric Encryption is a form of encryption in which a message is encrypted with a different key than it is decrypted with, so a user has 2 different keys, a public key which is used to encrypt a message plaintext with and a private key which you would use to decrypt a message ciphertext with. The origin of the mathematics behind asymmetric encryption tends to be quite technical, so be warned that this post will get at least a little bit technical on the math. That said, I will try to provide good resources to help explain how these math concepts were figured out and why they work.

Because the internet connects us all remotely, the cryptography on the internet relies very heavily on Asymmetric Cryptography. Everything from your email to bank account to Youtube uses Asymmetric cryptography.

Origins

Until the 1970s, encryption relied on symmetric key cryptography, where the same key was used to encrypt and decrypt data. This required people to pass the keys to each other in a way that couldn't others couldn't eavesdrop on. Physically meeting to secretly pass the encryption key was an option for some, but what if you were not physically able to meet up to pass off the key?

This problem meant that a new form of encryption needed to be created, one where someone could encrypt data using public information that only allowed the recipient of the ciphertext to decrypt it with private information.

What Was Needed?

To do encrypt plaintext with a different key than the key needed to decrypt the ciphertext, we need what is called a trapdoor function. A trapdoor is a mathematical function that is easy to do one way, but very hard to reverse unless you have some secret information. With a trapdoor function, it would be easy to encrypt plaintext, using a public key, but hard to reverse the process in order to decrypt the ciphertext unless you have the secret data, a private key. Modular Arithmetic can be useful for us in creating a trapdoor function.

Modular Arithmetic

Modular Arithmetic, also known as "Clock Arithmetic" is a system of arithmetic where integers wrap around at a certain value. An easy to understand example would be a 12 hour clock. You can start at 1 o'clock and keep adding 1 hour, so 2 o'clock, 3 o'clock, all the way to 12 o'clock. If you add 1 hour to 12 o'clock, you get back to 1 o'clock. This case in math terms is x MOD 12 = y, where x is a whole number and y is the remainder of x divided by 12. Another example would be 14 MOD 5 = 4, so if we had a clock with only 5 hours on it and we turn the clock ahead 14 hour from the starting point, it'll land at 4 o'clock.

RSA

A trapdoor function as found in the 1970s and then independently rediscovered by a group of researchers Ron Rivest, Adi Shamir, and Leonard Adleman (the first letter of each of their last names is where the name RSA came from). The trapdoor function relied on the fact that factorizing large numbers is hard, especially when the number is made of only two large primes, but multiplying two large primes is computationally easy. If a user gives the product of two large primes, it would take someone else a lot of bruteforce guess and checking to figure out what two large primes were used in that product. The larger the primes, the harder it would be to factorize the product of those primes. Mixing that fact with the use of modular arithmetic allowed for a trapdoor function to be found. With this method, a user Alice can create a public key that a user Bob can encrypt plaintext messages to Alice with and a private key that can decrypt that ciphertext with.

A great set of videos explaining how RSA was discovered and how the mathematics works can be found on Khan Academy in the "RSA Encryption: Step X" videos. Please check those videos out as they really do an excellent job at explaining the motivation, reasoning, and concepts behind RSA.

Diffie-Hellman Key Exchange

While not actually encryption itself, a Diffie-Hellman Key Exchange can allow two people to come up with a shared key value that can be used to encrypt data with symmetric encryption. To do this, Alice and Bob agree on a value g and a large prime number p. Both Alice and Bob each also create a large secret number that nobody else knows, which we'll call a for Alice and b for Bob.

Now, Alice calculates A = g^a MOD p and gives the value of A to Bob, while Bob calculates B = g^b MOD p and gives the value of B to Alice. To get the shared secret S, Alice can calculate S = B^a MOD p and Bob can calculate S = A^b MOD p. S is the same value for both Alice and Bob and the value was calculated without an eavesdropper being able to calculate S for themselves, because they do not know the values of a or b. This works because S for both Alice and Bob is calculated with S = g^(a * b) MOD p. It doesn't matter which order the exponents come in, because they will equal the same thing in the end for this case.

Khan Academy has a good video on Diffie-Hellman. Be sure to check it out.

Elliptic Curve Diffie-Hellman Key Exchange

Elliptic Curve Cryptography is a much more complicated concept, so I won't go into too much detail about it. It does provide more security in many ways, protecting from a set of attacks involving something called Index Calculus because the clock for modular arithmetic in elliptic curve cryptoraphy isn't a circle anymore. Along with resisting Index Calculus attacks, elliptic curves also allow the user to have much smaller key sizes for the same level of security and is much faster to compute.

A good explanation as to how elliptic curves work and how it can be used for Diffie-Hellman Key Exchanges can be found in this video and a more in depth explanation of how modular arithmetic and elliptic curve cryptography work by researchers Daniel J. Bernstein and Tanja Lange can be found here.

The Future of Asymmetric Cryptography

There is a weakness in modern asymmetric cryptography that may become a problem in the future. These systems revolve around the difficulty of factoring large numbers, but a sufficiently powerful quantum computer can make that much easier to do using something called Shor's Algorithm. To protect against this, asymmetric cryptography algorithms in a field called "Post Quantum Cryptography" are being created that do not rely on multiplication or factorization and instead rely on other problems in mathematics that are easy to calculate one way but difficult to reverse without secret information known only to the user.

In Conclusion

The point of Asymmetric Cryptography is to be able to share secrets in a channel that isn't secure by using some data that is secret to each user and public to other users. Without access the secret (private) data, an eavesdropper shouldn't be able to learn anything about the communications.

In the next post in the Cryptographic Concepts series, we will be going over cryptographic hashing and salting.

Cryptographic Concepts Series Posts

Symmetric Encryption

Asymmetric Cryptography

Cryptographic Hashing and Salting

Cryptographic Signatures

Blanket Fort Webring

<< Prev - Random - Full List - Next >>

What the heck is this?