Blog Post 7

\(1\) \(\underline{\text{Public Key Cryptography}}\)

Public key cryptography (from the Greek roots “crypto” and “graphon,” meaning “hidden writing”) is perhaps the most discreet application of discrete mathematics (Benjamin, 2009). The most famous method for public key cryptography is called the RSA method. This method was discovered in 1977 by three mathematicians Rivest, Shamier, and Adleman.

To carry out this method, one would begin by defining \(n\) to be the product of two primes \(p\) and \(q\). We must also choose a private key, as it is called, and we will name this \(d\). Then, we compute \(\phi({n})\) which is equivalent to \((p-1)(q-1)\). As long as \(d\) is relatively prime to \(\phi({n})\), we can set up the equation \(de-\phi({n})f=1\) and solve for \(e\) and \(f\) using the Euclidean Algorithm. The value for \(e\) is made public. Therefore, the information that is published is \(n\) and \(e\) while all other values are kept private.

The message that is sent is \(M^e \equiv C \pmod{n}\) where the original message is denoted \(M\) and the encrypted message is \(C\). To decrypt our message, one would compute \(C^d \equiv M \pmod{n}\).

Pictured (above) is a diagram illustrating the RSA method.