Prompt

Our analysts have obtained several artifacts from a message that was encrypted with RSA. We need you to decrypt the message and figure out what the hackers are up to.

n = 1079
e = 43
c = 996 894 379 631 894 82 379 852 631 677 677 194 893

Tutorial Video

Walk-Through

This challenge involves using math to decrypt an RSA message. The premise behind this challenge is that the prime numbers that are used to generate the RSA keypairs are too small, making it trivial to reconstruct the keypair.

RSA Primer

Before attempting to decrypt the RSA message, it is important to understand how RSA encrypts messages. The simplified RSA process is as follows:

Generate the priv/pub key pair

Generate two prime numbers p and q
Calculate n, which is the value of $p * q$
Calculate values d and e such that $d * e \equiv 1 \bmod(p-1)(q-1)$
The public key consists of n and e and the private key consists of d p and q

⚠️

What will make the decryption attack possible later is the use of small prime numbers in step 1. These must be large numbers for the encryption process to be secure.

Encrypt the message

Convert the plaintext message into an integer, m
Encrypt the message to obtain the ciphertext c, where $c \equiv m^e \pmod n$

Decrypt the message

Calculate the plaintext message m, where is $m = c^d \pmod n$

A deep understanding of the math equations used in RSA is not necessary to decrypt the message - just an understanding of the relationship between the different variables and where they are used in the process.

Breaking RSA

The information provided in the prompt includes the cipher text (c) and the public key used to encrypt the message (n and e). To decrypt the message, we will need to obtain the private key (d p and q). Once we have the private key, we can calculate m, the plaintext message.

We have	We need
`c` - The ciphertext	`d` - Part of the private key
`n` - Part of the public key	`p` - Part of the private key
`e` - Part of the public key	`q` - Part of the private key
	`m` - The plaintext message

From step 2 of the key generation process, we know that $n = p * q$ . By using a factor calculator, we can generate possible values for p and q. There should be only two possible values: 83 and 13.

\begin{align*} \nonumber n = p * q \\ 1079 = p * q \\ 1079 = 83 * 13 \\ p = 83, q = 13 \end{align*}

⚠️

This trivial factoring of n to obtain p and q is a result of p and q being small numbers. Larger values of p and q would have made this process much more difficult.

We can also rewrite the equation from step 3 of the key generation process to obtain d.

\begin{aligned} d * e = 1 \bmod(p-1)(q-1) \\ d * 43 = 1 \bmod(83-1)(13-1) \\ d = 43 ^ {-1} \bmod 984 \\ d = 595 \end{aligned}

With these calculations, we now have all the values needed to decrypt the ciphertext.

n = 1079
e = 43
c = 996 894 379 631 894 82 379 852 631 677 677 194 893

p = 83
q = 13
d = 595

With these values, the decryption equation can be used to obtain the plaintext, m. This step must be repeated for each item within the cipher text array.

\begin{aligned} m = c^d \pmod n \\ m = 996^{595} \bmod {1079} \\ m = 83 \end{aligned}

The resulting value of m = 83 can then be looked up using the ASCII table to reveal that the first character of the plaintext message is “S”.

996^{595} \bmod {1079} = 83 = S\\ 894^{595} \bmod {1079} = 75 = K\\ 379^{595} \bmod {1079} = 89 = Y\\ 631^{595} \bmod {1079} = 45 = - \\ 894^{595} \bmod {1079} = 75 = K\\ 82^{595} \bmod {1079} = 82 = R\\ 379^{595} \bmod {1079} = 89 = Y\\ 852^{595} \bmod {1079} = 71 = G\\ 631^{595} \bmod {1079} = 45 = -\\ ...

The remainder of the plaintext message can then be calculated by plugging in the remaining values of c into the equation.

Questions

What is the value of p (the smaller prime)?

Use the factor calculator on the value of n (1079)

What is the value of q (the larger prime)

Use the factor calculator on the value of n (1079)

What is the plaintext of the encrypted message?

Plug in each value of the ciphertext into the decryption function