16.5 Public Key Cryptography

Suppose that you are connecting to your bank’s website. It is possible that someone could intercept any communication between you and your bank, so you’ll want to encrypt the communication. The problem is that all the encryption methods we’ve discussed require than both parties have already agreed on a shared secret encryption key. How can you and your bank agree on a key if you haven’t already?

This becomes the goal of public key cryptography – to provide a way for two parties to agree on a key without a snooping third party being able to determine the key. The method relies on a one-way function; something that is easy to do one way, but hard to reverse. We will explore the Diffie-Hellman-Merkle key exchange method.

As an example, let’s consider mixing paint. It’s easy to mix paint to make a new color, but much harder to separate a mixed paint into the two original colors used.[1][2]

Using this analogy, Alice and Bob publically agree on a common starter color. Each then mixes in some of their own secret color. They then exchange their mixed colors.

Since separating colors is hard, even if a snooper were to obtain these mixed colors, it would be hard to obtain the original secret colors.

Once they have exchanged their mixed colors, Alice and Bob both add their secret color to the mix they obtained from the other person. In doing so, both Alice and Bob now have the same common secret color, since it contains a mix of the original common color, Alice’s secret color, and Bob’s secret color.

They now have a common secret color they can use as their encryption key, even though neither Alice nor Bob knows the other’s secret color.

Likewise, there is no way for a snooper to obtain the common secret color without separating one of the mixed colors.

To get this process to work for computer communication, we need to have the process result in a share common number to act as the common secret encryption key. For this, we need a numerical one-way function.

Modular arithmetic

If you think back to doing division with whole numbers, you may remember finding the whole number result and the remainder after division.

Modulus[3]

The modulus is another name for the remainder after division.

For example, 17 mod 5 = 2, since if we divide 17 by 5, we get 3 with remainder 2.

Modular arithmetic is sometimes called clock arithmetic, since analog clocks wrap around times past 12, meaning they work on a modulus of 12. If the hour hand of a clock currently points to 8, then in 5 hours it will point to 1. While $8 + 5 = 13$ , the clock wraps around after 12, so all times can be thought of as modulus 12. Mathematically, 13 mod 12 = 1.

Recall that when we divide 17 by 5, we could represent the result as 3 remainder 2, as the mixed number $3 \frac{2}{5}$ , or as the decimal 3.4. Notice that the modulus, 2, is the same as the numerator of the fractional part of the mixed number, and that the decimal part 0.4 is equivalent to the fraction. We can use these conversions to calculate the modulus of not-too-huge numbers on a standard calculator.

Example 2

Calculate 31345 mod 419

Show solution

$\begin{matrix} 31345 / 419 = 74.8090692 & Now subtract 74 to get just the decimal remainder \\ 74.8090692 - 74 = 0.8090692 & Multiply this by 419 to get the modulus \\ 0.8090692 \times 419 = 339 & This tells us 0.8090692 was equivalent to \frac{339}{419} \end{matrix}$

In the text above, only a portion of the decimal value was written down. In practice, you should try to avoid writing down the intermediary steps, and instead allow your calculator to retain as many decimal values as it can.

The one-way function

When you use a prime number $p$ as a modulus, you can find a special number called a generator, $g,$ so that $g^{n}$ mod $p$ will result in all the values from 1 to $p minus 1$

n	$3 to the power n$	$3 to the power n m o d 7$
1	3	3
2	9	2
3	27	6
4	81	4
5	243	5
6	729	1

In the table to the top, notice that when we give values of $n$ from 1 to $6,$ we get out all values from 1 to $6 .$ This means 3 is a generator when 7 is the modulus.

This gives us our one-way function. While it is easy to compute the value of $g^{n}$ mod $p$ when we know $n$ , it is difficult to find the exponent $n$ to obtain a specific value.

For example, suppose we use $p equals 23$ and $g equals 5.$ If I pick $n$ to be $6,$ I can fairly easily calculate $5 to the power 6$ mod $23 equals 15625$ mod $23 equals 8$

If someone else were to tell you $5^{n} mod 23 = 7$ , it is much harder to find $n$ . In this particular case, we’d have to try 22 different values for $n$ until we found one that worked – there is no known easier way to find $n$ other than brute-force guessing.

While trying 22 values would not take too long, when used in practice much larger values for $p$ are used, typically with well over 500 digits. Trying all possibilities would be essentially impossible.

The key exchange

Before we can begin the key exchange process, we need a couple more important facts about modular arithmetic.

You may remember a basic exponent rule from algebra:

${(a^{b})}^{c} = a^{b c} = a^{c b} = {(a^{c})}^{b}$

For example:

$64^{2} = {(4^{3})}^{2} = 4^{6} = {(4^{2})}^{3} = 16^{3}$

We can combine the modular exponentiation rule with the algebra exponent rule to define the modular exponent power rule.

Note

Modular Exponent Power Rule

${(a^{b} mod n)}^{c} mod n = (a^{b c} mod n) = {(a^{c} mod n)}^{b} mod n$

Example 4

Verify the rule above if $a = 3, b = 4, c = 5,$ and $n equals 7$

Show solution

${(3^{4} mod 7)}^{5} mod 7 = (81 mod 7)^{5} mod 7 = 4^{5} mod 7 = 1024 mod 7 = 2$

${(3^{5} mod 7)}^{4} mod 7 = (243 mod 7)^{4} mod 7 = 5^{4} mod 7 = 625 mod 7 = 2,$ the same result.

Your Turn

Try it Now 6

Use the modular exponent rule to calculate $10000 mod 7,$ by noting $10000 = 10^{4}$

Answer

$10000 mod 7 = 10^{4} mod 7 = (10 mod 7)^{4} mod 7 = 3^{4} mod 7 = 81 mod 7 = 4$

This provides us the basis for our key exchange. While it will be easier to understand in the following example, here’s the process:

Alice and Bob agree publically on values a prime $p$ and generator $g$ .
Alice picks some secret number $a,$ while Bob picks some secret number $b$ .
Alice computes $A = g^{a} mod p$ and sends it to Bob.
Bob computes $B = g^{b}$ mod $p$ and sends it to Alice.
Alice computes $B^{a} mod p,$ which is ${(g^{b} mod p)}^{a} mod p$ .
Bob computes $A^{b} mod p,$ which is ${(g^{a} mod p)}^{b} mod p$ .

The modular exponent power rule tells us ${(g^{a} mod p)}^{b} mod p = {(g^{b} mod p)}^{a} mod p,$ so Alice and Bob will arrive at the same shared value to use as a key, even though neither knows the other's secret number, and no eavesdropper can determine this value knowing only $g, p, A,$ and $B$

Example 5

Alice and Bob publically share a generator and prime modulus. In this case, we’ll use 3 as the generator and 17 as the prime.

# Diffie-Hellman-Merkle key exchange. EDIT the four numbers and re-run.
G, P = 3, 17          # public: generator and prime modulus
ALICE_SECRET = 8      # only Alice knows this
BOB_SECRET = 6        # only Bob knows this

powers = [pow(G, n, P) for n in range(1, P)]
print(f"is {G} a generator modulo {P}?")
print(f"   {G}^n mod {P} for n = 1..{P - 1}: {powers}")
print(f"   hits every value 1..{P - 1}? {sorted(powers) == list(range(1, P))}\n")

A = pow(G, ALICE_SECRET, P)
B = pow(G, BOB_SECRET, P)
print(f"{'':<12}{'Alice':<26}{'Bob':<26}{'a snooper sees'}")
print(f"{'public':<12}{f'g={G}, p={P}':<26}{f'g={G}, p={P}':<26}g={G}, p={P}")
print(f"{'secret':<12}{f'a={ALICE_SECRET}':<26}{f'b={BOB_SECRET}':<26}nothing")
print(f"{'sends':<12}{f'A = {G}^{ALICE_SECRET} mod {P} = {A}':<26}"
      f"{f'B = {G}^{BOB_SECRET} mod {P} = {B}':<26}A={A}, B={B}")
alice_key = pow(B, ALICE_SECRET, P)
bob_key = pow(A, BOB_SECRET, P)
print(f"{'computes':<12}{f'B^a mod p = {alice_key}':<26}{f'A^b mod p = {bob_key}':<26}stuck")
print(f"\nshared key: Alice got {alice_key}, Bob got {bob_key}   same? {alice_key == bob_key}")
print(f"why: (g^b mod p)^a mod p = g^(ab) mod p = (g^a mod p)^b mod p = "
      f"{pow(G, ALICE_SECRET * BOB_SECRET, P)}")

print(f"\nthe snooper's job: knowing g={G}, p={P}, A={A}, find Alice's secret a")
tries = [n for n in range(1, P) if pow(G, n, P) == A]
print(f"   brute force over n = 1..{P - 1} finds a = {tries}   after at most {P - 1} guesses")
print("   that is easy here. Real exchanges use a prime with 500+ digits, so the same")
print("   search would need more guesses than there are atoms in the observable universe.")
# Try it: change ALICE_SECRET and BOB_SECRET. The shared key changes, but they still agree.

Show solution

$\begin{matrix} Alice & Bob \\ Alice and Bob publically & g = 3, p = 17 & Common info & g = 3, p = 17 \\ share a generator and prime \\ modulus. \\ Each then secretly picks a & n = 8 & secret number & n = 6 \\ number n of their own. \\ Each calculates g^{n} mod p & 3^{8} mod 17 = 16 & 3^{6} mod 17 = 15 \\ They then exchange these & A = 16 & B = 15 \\ resulting values. & B = 15 & A = 16 \\ Each then raises the value & B^{n} mod p = & mix in secret & A^{n} mod p = \\ they received to the power of & number \\ their secret n mod p & 15^{8} mod 17 = 1 & 16^{6} mod 17 = 1 \\ The result is the shared secret key. & 1 & shared secret key & 1 \end{matrix}$

The shared secrets come out the same because of the modular exponent power rule

${(a^{b} mod n)}^{c} mod n = {(a^{c} mod n)}^{b} mod n .$ Alice computed ${(3^{6} mod 17)}^{8} mod 17$ while Bob computed ${(3^{8} mod 17)}^{6} mod 17,$ which
the rule says will give the same results.

Notice that even if a snooper were to obtain both exchanged values $A equals 16$ and $B equals 15$ , there is no way they could obtain the shared secret key from these without having at least one of Alice or Bob’s secret numbers. There is no easy way to obtain the secret numbers from the shared values, since the function was a one-way function.

Using this approach, Alice and Bob can now use the shared secret key obtained as the key for a standard encryption algorithm like DES or AES.

RSA

There are several other public-key methods used, including RSA, which is very commonly used. RSA involves distributing a public encryption key, which anyone can use to encrypt messages to you, but which can only be decrypted using a separate private key. You can think of this as sending an open padlock to someone – they can lock up information, but no one can unlock it without the key you kept secret.

RSA’s security relies on the difficulty of factoring large numbers. For example, it’s easy to calculate that 53 times 59 is 3127, but given the number 12,317 that is a product of two primes, it’s much harder to find the numbers that multiply to give that number. It’s exponentially harder when the primes each have 100 or more digits. Suppose we find two primes $p$ and $q$ and multiply them to get $n = p q$ . This number will be very hard to factor. If we also know $p$ and $q$ , there are shortcuts to find two numbers $e$ and $d$ so that $m^{e d} mod n = m mod n$ for all numbers $m$ . Without knowing the factorization of $n$ , finding these values is very hard.

To use RSA, we generate two primes $p$ and $q$ and multiply them to get $n = p q$ . since we know the factorization, we can easily find $e$ and $d$ so $m^{e d} = m mod n .$ Now, we lock away $p$
$q,$ and $d .$ We then send the values $e$ and $n$ out publically. To encrypt a message $m,$ the sender computes $S = m^{e} mod n .$ As we saw earlier, the modulus is a one-way function which makes the original message very hard to recover from $S$ . However, we have our private key $d$ we can use to decrypt the message. When we receive the secret message $S$ , we compute $S^{d} mod n = {(m^{e})}^{d} mod n = m^{e d} mod n = m mod n,$ recovering the original message[4].

Example 6

Suppose that Alice has computed $n = 3127, e = 3,$ and $d equals 2011.$ Show how Bob would encrypt the message 50 and how Alice would then decrypt it.

from math import gcd

# RSA end to end with small primes. EDIT P, Q, E and re-run.
P, Q, E = 53, 59, 3

N = P * Q
PHI = (P - 1) * (Q - 1)
if gcd(E, PHI) != 1:
    raise SystemExit(f"e = {E} shares a factor with (p-1)(q-1) = {PHI}; pick another e")
D = pow(E, -1, PHI)          # the modular inverse: e*d = 1 more than a multiple of PHI

print("KEY GENERATION (only Alice can do this - she is the one who knows p and q)")
print(f"   p = {P}, q = {Q}          two primes she keeps secret")
print(f"   n = p*q = {N}            easy to compute, hard to undo")
print(f"   (p-1)(q-1) = {PHI}")
print(f"   e = {E}                    chosen so it shares no factor with {PHI}")
print(f"   d = {D}                 solves e*d = 1 (mod {PHI}):  {E}*{D} = {E * D} "
      f"= {E * D // PHI}*{PHI} + 1")
print(f"\n   PUBLIC KEY  (n, e) = ({N}, {E})   -> Alice publishes this, like an open padlock")
print(f"   PRIVATE KEY      d  = {D}        -> Alice alone keeps this\n")

print("SENDING MESSAGES (anyone with the public key can encrypt; only Alice can decrypt)")
print(f"{'message m':>11}{'m^e mod n':>14}{'S^d mod n':>14}   recovered?")
for m in (50, 7, 1234, 3000):
    if m >= N:
        continue
    S = pow(m, E, N)
    back = pow(S, D, N)
    print(f"{m:>11}{S:>14}{back:>14}   {'yes' if back == m else 'NO'}")

print(f"\nWHY IT IS SAFE: the padlock (n = {N}) is public, the key (d) is not.")
factor = next(k for k in range(2, N) if N % k == 0)
print(f"   an attacker who can FACTOR n gets everything: trial division found "
      f"{factor} x {N // factor} after {factor - 1} tries")
print(f"   with p and q in hand, (p-1)(q-1) = {PHI} and then d = {pow(E, -1, PHI)}")
print("   real RSA uses primes of 300+ digits each; the same trial division would run")
print("   for longer than the age of the universe, so the private key stays private.")
print("\nno key exchange was needed - Bob never had to talk to Alice first.")
# Try it: P, Q, E = 11, 3, 7 gives the book's exercise n = 33, e = 7, d = 3.

Show solution

Bob would only know his message, $m equals 50$ and Alice's public key: $n equals 3127$ and $e equals 3.$ He would encrypt the message by computing $m^{e} mod n : 50^{3} mod 3127 = 3047$

Alice can then decrypt this message using her private key $d$ by computing $S^{d}$ mod $n$ :

$3047^{2011} mod 3127 = 50$

This method differs from Diffie-Hellman-Merkle because no exchange process is needed; Bob could send Alice an encrypted message using Bob’s public key without having to communicate with Alice beforehand to determine a shared secret key. This is especially handy for applications like encrypting email, where both parties might not be online at the same time to perform a Diffie-Hellman-Merkle style key exchange.

[1] en.Wikipedia.org/w/index.php?...nge.svg&page=1

[2] For a video overview of this process, see http://www.youtube.com/watch?v=YEBfamv-_do

[3] Sometime, instead of seeing 17 mod 5 = 2, you’ll see 17 ≡ 2 (mod 5). The ≡ symbol means “congruent to” and means that 17 and 2 are equivalent, after you consider the modulus 5.

[4] Many details have been left out, including how e and d are determined, and why this all works. For a bit more detail, see http://www.youtube.com/watch?v=wXB-V_Keiu8, or http://doctrina.org/How-RSA-Works-With-Examples.html

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.