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.

This encryption method is widely used for securing sensitive data. In particular, it is utilized when the network has proven to be insecure, such as the Internet. “It provides a method of assuring the confidentiality, integrity, authenticity and non-reputability of electronic communications and data storage” (Rouse, 2014). It is one of the most commonly performed operations in Information Technology.

Although the method seems fairly straightforward, it derives its security from the difficulty of factoring integers when such numbers become incredibly large. An example would be an integer that is $$2000$$ digits long. Even the super computers of today’s time cannot possibly perform such a task.

The typical length of an RSA key is $$1024$$-bits. However, experts are starting to believe that these could be deciphered in the near future as technology advances. Therefore, the government and industries are moving toward keys that have a length of $$2048$$-bits.

$$2$$ $$\underline{\text{Suggested Exam Problem}}$$

Suppose that $$p=3$$ and $$q=7$$. Further assume that the bank publishes the enciphering number $$e=203$$. Find the value of $$d$$, the secret number that the bank uses to decipher messages.