Cryptography is the study of how to transform information and communication so that it's concealed and secure. The most basic form of cryptography dates back to the classical era, via the use of substitution ciphers. These involve shifts of letters: if your cipher was shifted by 13, then you would map $a \rightarrow n, b \rightarrow o, c \rightarrow p, \dots$ and so forth. Such ciphers are still in use today, but not for secure communications. If you wanted to talk about your favourite currently screening movies and tv shows on Twitter or something, current internet etiquette is to conceal such spoilers by running it through a ROT13 encoding, which is just a substitution cipher with shift 13 that was just described.
The key to making cryptography work is by ensuring the encoding of the information remains secret. This doesn't work very well for substitution ciphers because the encoding is very simple. In fact, if you read enough ROT13 spoilers on Twitter, you can begin to see patterns of how words form. So one aspect of cryptography is ensuring that the key is complex and remains secret. However, this is only half the battle. The other problem that remains is how to communicate about the key.
In Canada, the banks collectively run a system called Interac, which, among other things, makes it very handy to transfer money via email and is why services like Venmo haven't really caught on. Suppose Alice and Bob, the two famous recurring characters of cryptography, want to transfer some Canadian money. So Alice logs onto her bank's website and initiates an email transfer that can be deposited by Bob into any bank account he wants once he gets the email. How does this stay secure? Alice will set a password that she communicates to Bob, who will then use the password to verify that he is allowed to accept the email transfer.
Hypothetically, what Alice needs to do is communicate the password to Bob in a secure way. What usually ends up happening is that Alice just emails Bob the password to the same account. This is bad, because if an eavesdropper, like Eve, gets access to Bob's email, then Bob is, as they say in Canada, hosed, because both the password and the email containing the transfer are sitting in Bob's email account. All Eve needs to do is use the password and then she can deposit the Canadian dollars into any bank account she wishes.
This highlights a common weakness: even though we may devise an unbreakable cryptographic scheme, if the key for that system is acquired, then we're screwed. This shifts the problem of secure communication from the message that we originally wanted to send to the problem of how to securely distribute our key.
One way to do this is to make it not a cryptographic problem anymore and do something like send the keys physically. Of course, this is what actually happened prior to communication with electronic computers. Note, however, that this is a cryptographically secure system, but that doesn't mean I couldn't just hire someone to steal your mail or break your kneecaps to get your key. Beyond those caveats, the big problem with such a scheme is that no one wants to wait for some mail just so they can log onto a website securely.
The use of a secret key for encryption and decryption is called private-key cryptography. This is also called symmetric-key cryptography. This name hints at the root of our problem and a possible solution: what if we separate the encryption and decryption key?
This leads us to the idea of public-key cryptography, or assymetric-key cryptography. Here, only the decryption keys are secret, while encryption keys are made public. This way, if Alice wants to send Bob a message that only Bob can read (perhaps containing Alice's credit card number or something), then Alice encrypts her message with Bob's public key, sends the encrypted message, and Bob would then decrypt the message.
The key to making this work is that the public and private keys need to be related in such a way that decryption is easy when the private key is known, but difficult when only the public key is known.
The most famous public-key cryptosystem (and definitely the most popular to teach in elementary number theory classes) is RSA, named for Rivest, Shamir, and Adleman who designed it in 1977 at MIT. RSA is commercially implemented in many Internet communication protocols currently in use and won Rivest, Shamir, and Adleman the Turing Award in 2002.
There are three parts to the system.
To see that this is true, we first recall that we have $$R = C^d = (M^e)^d = M^{ed} \bmod n.$$ Since $ed = 1 \bmod{(p-1)(q-1)}$, by the definitions of congruence and divisibility, we have $$ed = 1+k(p-1)(q-1)$$ for some integer $k$. This gives us $$R = M^{1+k(p-1)(q-1)} \bmod n.$$
Now, we show that $R = M \bmod p$. There are two cases: either $p \mid M$ or $p \nmid M$. In the first case, we have $M = 0 \bmod p$, which gives $$R = 0^{1+k(p-1)(q-1)} = 0 \bmod p$$ and therefore $R = 0 = M \bmod p$. In the second case, $p \nmid M$ implies $\gcd(p,M) = 1$ and therefore, by Fermat's Little Theorem, $M^{p-1} = 1 \bmod p$. Then we get $$R = M(M^{p-1})^{k(q-1)} = M\cdot 1^{k(q-1)} = M \bmod p.$$ Therefore, $R = M \bmod p$. A similar argument holds for $q$ and we can show $R = M \bmod q$. Since $p$ and $q$ are distinct primes, we must have $\gcd(p,q) = 1$ and therefore, by the Chinese Remainder Theorem, we can put together the two congruences to get $R = M \bmod{n}$.
RSA was the first practical public-key cryptosystem, but it was inspired by an earlier system proposed by Diffie and Hellman in 1976. They give a protocol for secure key-exchange, which, like RSA, is used all over the Internet today. Rather than factoring primes, their system is based on a related problem, the discrete logarithm problem.
Definition. A primitive root modulo a prime $p$ is an integer $r \in \mathbb Z_p$ such that every nonzero element of $\mathbb Z_p$ is a power of $r$.
Something that we won't prove is the fact that if $p$ is prime, then $\mathbb Z_p$ will contain a primitive root. We can think of this root as a generator, since all we need to generate every element in $\mathbb Z_p$ is to multiply $p$ by itself a bunch of times.
Now, if we can perform exponentation, we can also think of doing the "inverse" of exponentation: take a logarithm. Recall that a logarithm for base $b$ is $\log_b x = e$ if $x = b^e$. We want to "discretize" this notion.
Definition. Let $p$ be a prime, $r$ a primitive root modulo $p$, and $a$ an integer with $1 \leq a \leq p-1$. If $r^e \pmod p = a$ and $0 \leq e \leq p-1$, then $e$ is the discrete logarithm of $a$ modulo $p$ to the base $r$.
Then the discrete logarithm problem is: Given a prime $p$, primitive root $r$, and integer $a \in \mathbb Z_p$, find the discrete logarithm of $a$ for $r$. In other words, we want to find the $e$ such that $a = r^e \pmod p$.
The discrete logarithm problem turns out to be hard, for roughly the same reasons as factoring. Let's see how Diffie and Hellman make use of this.
As before, Alice and Bob want to share a private key using public pieces of information. They do the following.
Here, we distinguish between information that is made "public" (i.e., sent over an insecure channel and likely to be exposed) and "private" (information that is kept secure). The public pieces of information are $p$, $a$, $a^{k_1} \pmod p$, and $a^{k_2} \pmod p$. The private pieces of information are $k_1$, $k_2$, and $a^{k_1 k_2} \pmod p$.
If our eavesdropper Eve wanted to figure out the secret key $a^{k_1 k_2} \pmod p$, then something she could do is get $a^{k_1} \pmod p$ and $a^{k_2} \pmod p$, both of which have been transmitted insecurely, and compute $a^{k_1 k_2} \pmod p$ if she can figure out what $k_1$ and $k_2$ are. But figuring out $k_1$ and $k_2$ is exactly the discrete logarithm problem, since she would also know $a$ and $p$.
Why is this hard? Well, the obvious way to compute this would be to just try computing all the $a^i$s, which gives you up to $p$ things to check. A simple modification lets us go a bit quicker.
Take $r = \left\lceil \sqrt p \right\rceil$. We compute the following lists:
If we found the same number in both lists, say $a^{i \cdot r} = c \cdot a^j \pmod p$, then this gives us $a^{ir-j} = c \pmod p$ and $i\cdot r - j$ is the discrete logarithm for $c$.
Computing these takes $O(\sqrt p \log p)$ time. Then to do the search, we can sort both lists, which takes $O(\sqrt p \log p)$ time, and for each of the $\sqrt p$ elements in one list, perform binary search on the other list, for a total of $O(\sqrt p \log p)$ time.
This approach is called baby-step, giant-step, because one list consists of baby steps ($0,1,2,\dots,r-1$) and the other step consists of giant steps ($r,2r, \dots, r^2$).
As with the analysis of Euclid's algorithm, we have to be careful about what $O(\sqrt p \log p)$ means. Here, we're counting operations like multiplications and comparisons. However, you'll learn in algorithms that these computations should really be viewed at the bit level, like we did with Euclid's algorithm. This means that we should be considering the complexity of this algorithm in terms of $\log p$, not $p$. So if we let $n = \log p$, we actually have something like $O(n2^{\sqrt n})$.
The viability of the public-key cryptography systems that we've looked at rely on the ease of multiplying numbers together and the hardness of factoring numbers. This makes it very difficult to design new cryptosystems. Obviously, computing the secret key has to be difficult, but it would be very easy to do if we didn't need to make using the public key easy too.
However, even the assumption that factoring is difficult is a significant one for a variety of reasons. First of all, it is not quite proven that factoring really is "hard". Currently, the best we can say is that there are no known efficient algorithms for factoring, but no one has been able to prove that it's impossible to come up with one. If someone were to come up with one, then we would be in a lot of trouble.
However, the other big problem is that someone has come up with an efficient factoring algorithm—assuming that you have access to a quantum computer. Peter Shor's quantum factoring algorithm from 1994 was one of the first algorithms to demonstrate that quantum computers were provably more powerful than classical computers.
While there are no viable large-scale quantum computers yet, the possibility that they will get built is driving current cryptography research, particularly since secure systems that are built now, need to be secure for the next decade or so. The NSA has recently put out proposals for new quantum-secure cryptographic methods. Many of these proposed systems were weeded out in the first round, by being broken using classical methods.
This speaks to the difficulty of constructing new cryptosystems. One advantage that the elementary number theoretic systems that we're used to had was that the problems underlying these systems had been well-studied for a very long time. Factoring was a difficult problem, but we spent hundreds of years studying it. Newer systems are built on much newer mathematics that are only a couple of decades old. We simply haven't had time to digest and completely understand them.
However, even many current secure systems have moved on from systems based on elementary number theory, like RSA, to systems based on problems from algebraic number theory, like elliptic curve cryptography. These are fairly well-understood, but are not resistant to quantum attacks.