One of the difficulties with private-key encryption is how to share the secret key in a secure way. This issue gave rise to one of the most important breakthroughs in cryptography–public- or asymmetric-key encryption, which generally uses a pair of keys–a private one and a public one. Yes, public! That means anyone can see it! The keys are mathematically related so that one can be used for encryption and the other for decryption.
In general, it works like this: Alice has a public key and a private key. Bob has a public key and a private key. If Alice wants to send Bob a message, she encrypts the message using Bob’s public key. When Bob receives the message, he can decrypt it using his private key. So…two different keys for encryption and decryption! How is this possible? The answer is…MATH!
Public-key cryptography allows Alice and Bob to communicate securely without ever sharing their private key with anyone else–including each other! Public-key encryption systems tend to be less efficient than private-key systems, so it is often used to initially share a secret key, so that subsequent communication can take place using private-key encryption
A brief explanation of complexity
Some problems are considered so difficult to solve that even computers can’t solve them in a reasonable amount of time. Strangely enough, some of these problems seem very simple. Ask your students, for example, if they know how to find the factors of a number. Ask them if they know how to find out if a number is prime. Both of these would be good programming assignments to try. Have them write a program to find the factors of a number and to determine if a number is prime. Then have them test their programs on increasingly large numbers. It turns out that factoring large numbers is one problem that is considered infeasible with today’s computing power.
This is one example of a mathematical concept that is used in public-key cryptography. For example, the security of RSA, which is widely used and discussed below, depends on the assumption that today’s computers cannot factor numbers of a certain size in a reasonable amount of time!
Diffie Hellman Key Exchange
One example of public-key encryption is called Diffie Hellman Key Exchange, which was developed as a way to exchange a secret key over an insecure communication channel. The algorithm, like most public-key encryption algorithms, focuses on calculations that can be computed easily, but cannot be reversed easily.
After using the algorithm above, Alice and Bob now have a shared secret key that cannot be determined without knowing the secrets a and b even though they did not share their original secrets! The security of this system depends upon the assumption that an eavesdropper, who can gain access to the values Alice and Bob send each other (e.g. ga) cannot figure out the secrets. That is, it is assumed to be computationally infeasible given modern computing power to figure out a given ga mod p. For students, this is an easy programming project that can allow them to look at sending data over a network and computing with very large numbers.
See https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange for a discussion of Diffie Hellman key exchange that contains a simple example of the mathematics, a visual representation of the process using paint colors, and a discussion of using the algorithm to share a key among three or more parties.
Note that in public key cryptography, there is still a private key that must be kept secret. However, the secret key does not have to be shared with people one wants to communicate with, which reduces the problems associated with secret sharing.
This algorithm, however, is vulnerable to a common attack called the Man in the Middle Attack (MITM), in which an eavesdropper impersonates one or both of the parties in order to gain access to the secret information. This leads to the need for protocols for authentication, so that Alice, for example, can be sure that she is communicating with Bob and not with eavesdropper Eve. There are modified versions of the Diffie-Hellman Key Exchange algorithm that work to mediate these risks. See https://en.wikipedia.org/wiki/Man-in-the-middle_attack for more information on MITM attacks.
RSA
Another commonly used algorithm is much more complicated mathematically but has become one of the great tools to encrypt sensitive data. This is described in detail at http://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation.
RSA depends upon the assumption that it is computationally infeasible to factor large numbers! This may come as a surprise to many students, who most likely learned to factor numbers at a young age.
https://projecteuler.net/ has some very interesting problems to be solved by programming that would be relevant to this section. For example, find the largest prime factor of a given large number.
