Modular Arithmetic

In last blog, I discussed the difference between both symmetric and asymmetric algorithms. As a quick recap, symmetric key has the same key for both encryption and decryption while asymmetric key has a different key for the encryption and decryption side. I will dive now into the mathematics and the uses of the algorithms. Beware, we are entering a very nerdy field!

Cryptography in other words is a modern use for modular arithmetic. Modular arithmetic in simple terms can be used most often when describing an analog clock. For example, if it’s currently 10 am, you might want to know what the time will be in 4 hours. We know that the answer will be 2 pm. This is a perfect example of modular arithmetic. 10 + 4 = 2 mod 12. Cryptography is based on this concept. Cryptography comes into use with any transaction over the internet. The remainder of this blog will go in depth of the use of modular arithmetic in cryptography.

RSA encryption is a form of public key encryption. As I stated in my last blog before, public key encryption and asymmetric key encryption are the exact same thing (different names for the same concept). With RSA, the private key is not accessible to the public and thus it forms a secure way of passing information from an individual to a website. Here is a block diagram illustrating the concept:

We need to perform the calculation shown above, but even a small understanding of modular arithmetic will help us with the process. We first need to produce a private and public key. Use the following steps to do so:

  1. Choose two large prime numbers, p and q.
  2. Compute the modulus n, n = p * q.
  3. Compute the totient, totient = (p – 1) * (q – 1)
  4. Choose an “e” > that is co-prime to the totient.
  5. Choose a “d” such that d * e = 1 mod totient.

Once the steps are done, you will have two keys a public key and a private key. Public key (n, e) and a private key (n, d). Modular arithmetic really comes into play in play in step 5, because it allows an infinite pair of numbers to satisfy the constraint, but the user still might not be able to decrypt the message. For example, 10 + 4 = 2 mod 12, but 10 + 16 = 2 mod 12. This makes it extremely difficult to determine what the original number is. It could be any multiple of 12, 2, or 16.

The keys have been generated. Now, we need to encrypt and decrypt the text. To encrypt the message m given the public key (n, e) that was formed above, here is the formula:

C = me mod n

“C” is the encrypted message and it gets passed to the other parties. We now decrypt the message “C” that was created. Here is the formula for decryption:

M = Ce mod n

If we run a full example, we see that the message will be fully passed from one place to another.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s