Asymmetric Cryptography

What is it?  Asymmetric Cryptography, also known as public-key cryptography, is a form of cryptography in which the key that is used to encrypt a message is not the same as the key that is used to decrypt the same message. Rather, a public key is used to encrypt a message and a private key is used to decrypt it. Up till now, all of the cryptographic algorithms we have looked at are part of symmetric-key cryptography, in which the same key is used to encrypt and decrypt a message. But now, we will look at an asymmetric, modern cryptographic algorithm known as RSA. 

To understand how an asymmetric key-exchange protocol works, let's use a classic example: Alice wants to send a message to Bob, but he wants him to know the symmetric key that was used to encrypt it. So she encrypts the symmetric key using Bob's public key and sends it to Bob. Bob can then decrypt the symmetric key using his private key. Note that everyone knows Alice and Bob's public keys, but only Alice knows her private key and only Bob knows his public key. 

The RSA algorithm relies on large prime numbers. Initially, two secret prime numbers p and q are multiplied by each other to generate a modulus n. Then, an exponent e is generated. The following illustrates a simplified version of the RSA encryption process:

P = 123 (Note that RSA only works on NUMERIC plaintexts)

e = 17

p = 29

q = 37

n = p * q = 1073

Encryption: C = (P^e) mod n

                     C = (123^17) mod 1073 = 256

But decryption is different from encryption because this is an asymmetric algorithm. In fact, to decrypt, one needs to calculate two new values: 

totient = (p - 1) * (q - 1) = 1008

d = modular multiplicative inverse of e modulo totient = 17^(-1) mod 1008 = 593

Decryption: P = (C^d) mod n

                      P = (256^593) mod 1073 = 123

In our example, things worked out well. But there are two important conditions that must be satisfied for RSA to work in general:

  1. The exponent should be coprime to the totient -- you can read a proof about WHY this is the case here.

  2. The plaintext P should not be greater than n. This is simply because if P > n, then it can be simplified in the modulo n system, and when the message is decrypted it will decode to the simplified numerical value instead of P.

How is this a form of asymmetric cryptography, you might ask? The public key is given by (n, e) and is visible to everyone. Hence, someone can easily encrypt a message using the public key by raising it to the power e and taking it modulo n. But the private key is given by (d, e). The value for d cannot be computed without knowing the value for totient, and the value for totient cannot be determined without factoring n to determine the values for p and q. It turns out that factoring large relatively prime numbers is considered a "hard" problem. Once the numbers get big enough, factoring them is beyond modern computing. So the private key remains secure.. for now. We'll see what the future has to say.  Quantum computing may one day be able to compromise RSA.

How do I break it?  RSA can be broken if it is implemented poorly. One example of this is using a very small value for the exponent e such that when the message is raised to the power of the exponent, it is not greater than the modulus. In this case, the message can simply be decrypted by taking the eth root of the ciphertext. Another example is using a small value for n. If you can factor n, then you can break RSA. You can read about some of the more powerful online factoring algorithms over here. One other special case is called multi-prime RSA. With this algorithm, many prime numbers are multiplied together to generate the modulus n. Everything remains the same in multi-prime RSA except one thing: calculating totient. To calculate totient, find the product (p - 1) * (q - 1) * (r - 1) * (s - 1) ... etc. (where p, q, r, s, ... represent the prime factors of n). 

Additional Notes: RSA is used to share symmetric keys, but it can also be used to directly exchange messages. The only issue is finding a way to represent plaintext numerically. The following are some options:

  1. convert the plaintext to ASCII hexadecimal and then reverse it. Interpret the result as a hexadecimal NUMBER rather than an ASCII string and convert it to decimal (picoCTF 2019)

  2. convert the plaintext to 5-bit binary (00000 - 11001) and then break it into 3-grams. Interpret each 3-gram as a binary value and convert it to decimal [0-7]. Splice together the decimal values to get the number that you will use in RSA.

  3. convert each letter in the plaintext to its corresponding numerical value such that either [A-Z] --> [0-25] or [A-Z] --> 0-26. Splice together the numerical values to get the decimal number that will be used. This method can be difficult to work with because, for example, the digits "23" can be interpreted as "23" or "2" "3". But it makes the message more difficult to decode :-)