Skip to main content

Section 11.7 Other applications

The methods of Diffie-Hellman and RSA are just the most typical and famous encryption systems used in introductory number theory texts; there is a huge amount of active research into the mathematics of cryptography, much of which uses rather more advanced mathematics. The important point is that we have observed some of the basic issues to consider in such systems.

A good next system to check out which has mathematics at the same level is the El-Gamal system (see Exercise 11.8.12). After reading Chapter 17 you may wish to explore the system mentioned in Subsection 17.5.3. For something slightly more advanced, see the very brief discussion of elliptic curves in cryptography at the beginning of Subsection 11.5.1.

There are also tons of other cryptographic applications which are not directly about encryption. Two of my favorites are finding ways to flip a coin over the Internet and how to find out if someone makes more money than you without them revealing their actual salary. For now, we just share one secret.

Subsection 11.7.1 Secret sharing

Suppose that a company with a particular trade secret has three employees with clearance to know details of this secret process. However, the company wants to avoid one of the three being bought off by a competitor and revealing it in an act of corporate espionage.

The company needs to devise a system where, in order to actually gain access to the details of the trade secret, one needs two of the people involved. In a movie, you would have an impressive safe with three locks; each person would have a separate key to one of the locks, and the safe would be constructed so that any two of the keys would open it.

But real cryptography is not the movies! For one thing, the data is probably electronic, so it's really something we need to do digitally. Cryptography provides the perfect way to deal with these issues. What we will do is indeed give each person a key – a digital encryption key, of course. (The following description is a simplified exposition based on the one in the book where I first learned it, [E.2.4, Chapter 7.6].)

What good do these do us? Well, the Chinese Remainder Theorem allows us to reconstruct \(K_0\) modulo \(m_im_j\) with any two keys \(k_i\) and \(k_j\text{.}\) That may not seem like a lot; that just gives us things to within multiples of \(m_im_j\text{.}\)

But by our choice of \(M=m_1m_2>pm_3\text{,}\) we know that \(M/p>m_3\) (and hence \(M/p>m_i\) as well). So

\begin{equation*} K_0=K+tp<p+tp=(t+1)p\leq (M/p)p=M \end{equation*}

And certainly if \(K_0<M\text{,}\) then \(K_0<m_im_j\text{,}\) since \(M\) is the smallest such product. So the Chinese Remainder Theorem allows us to reconstruct \(K_0\) uniquely, and then \(K=K_0-tp\text{!}\)

Finally, note that just one person doesn't have enough information to get \(K\text{,}\) since that just tells that

\begin{equation*} K_0\equiv k_i\text{ (mod }m_i)\text{,} \end{equation*}

so that

\begin{equation*} K_0=k_i+\ell m_i \end{equation*}

for all \(\ell\) modulo \(m_i\text{.}\)

Obviously, we'll want to see this in action.

Example 11.7.2.

Suppose your secret was \(K=5\text{.}\) Let's pick \(p=13\text{,}\) and numbers \(17,19,16\text{.}\)

We'll check quickly that \(m_1m_2>pm_3\text{:}\)

So \(M=17\cdot 19=323\text{,}\) and we can pick \(t=12\) more or less randomly as being less than \(M/p=323/13=20\frac{11}{13}\text{.}\)

So \(K_0=K+tp=5+12\cdot 13=161\text{:}\)

This gives keys \(k_i\text{,}\) which are \(K_0\) modulo \(m_i\text{.}\) Note that in our example, we can check all the conditions in the proof by hand, but with industrial-size numbers that would not be possible.

The three keys are now \(8,9,1\) for moduli \(17,19,16\text{.}\)

Now let's actually reconstruct the secret \(K\text{.}\) First, let's see that any two people do have enough information. We do the Chinese Remainder Theorem on each pair:

Now we subtract \(tp\) from these outcomes.

Great!

One might suspect that a lone person, without one of the other secret sharers, might be able to just ‘guess’ which of the various solutions was right in this very small example.

As you can see, without all the information it would not be so clear which is the correct \(K_0\text{.}\) If you get only one chance, you might not want to try to be lucky!

As a note, we should point out that this secret sharing method doesn't just protect against someone defecting. It also provides protection against one of the three becoming incapacitated somehow. If all three were necessary to unlock the secret, the company is one illness or death or resignation away from its secret being irretrievably lost without a system of this type.

Finally, it is not terribly hard to extend this to a system that works by sharing a secret among \(n\) individuals in such a way that only \(k\) of them are needed to access the secret. For full details, I recommend [E.2.4, Chapter 7.6]; Example 11.7.2 was originally based on [E.2.4, Example 7.8].