RSA Encryption System

The RSA encryption system is a public-key cryptographic method based on mathematical principles, designed to securely encrypt and decrypt messages. Its security relies on the computational challenge of factoring large numbers—products of two prime numbers—ensuring the confidentiality of communications.

Each user generates a pair of keys:

• Public key \((n, e)\): used to encrypt messages.
• Private key: kept confidential and required for decryption.

Only the private key owner can decrypt messages, ensuring their security.

RSA’s security is built on a mathematical "trapdoor function," which is easy to compute in one direction but extremely difficult to reverse without the private key.

This trapdoor function enables secure message encryption.

Why is it called RSA? The RSA system is named after its creators: Rivest, Shamir, and Adleman. Although the concept of public-key encryption was initially introduced by W. Diffie and M. E. Hellman, RSA was developed and refined by L. M. Adleman, R. L. Rivest, and A. Shamir at MIT. Today, RSA is one of the most widely used encryption methods for securing communications.

How It Works

To use RSA, each user generates two very large prime numbers, \(p\) and \(q\).

A random number with many digits (e.g., 100 digits) is typically generated and tested for primality. If it’s not prime, subsequent numbers are checked until a prime is found.

The two prime numbers are then multiplied to calculate:

$$ n = p \cdot q $$

Note: In examples, \(p\) and \(q\) are often small for simplicity. In real-world applications, RSA uses primes with around 100 decimal digits, resulting in an \(n\) with approximately 200 digits. This ensures robust security, as no efficient algorithm currently exists for factoring such large numbers.

A value \(e\) is then selected, ensuring it is relatively prime to \((p-1)(q-1)\), meaning:

$$ \text{GCD}(e, (p-1)(q-1)) = 1 $$

The pair \((n, e)\) is made public and serves as the public encryption key.

However, \(p\) and \(q\) remain secret, forming the private key known only to the owner.

When user A wants to send an encrypted message to user B, they use B’s public key to encrypt the message.

The encryption formula is:

$$ C_i = P_i^{e_B} \mod n_B $$

Here, \(P_i\) represents individual blocks of the message, converted into numerical values.

Once the message is encrypted, user A sends it to user B.

Finally, user B decrypts the message using their private key.

A Practical Example

Let’s consider two users, A and B. Each user generates their own public encryption key.

$$ K_A = (65,11) $$

$$ K_B = (1003,3) $$

A public directory lists the encryption keys of all users.

Note: The first element of each public key is the product of two prime numbers, \( p \) and \( q \). For instance, \( p = 5 \) and \( q = 13 \), which results in \( n = p \cdot q = 5 \cdot 13 = 65 \). These two prime numbers remain private. The second element is a number that is relatively prime to \( (p-1) \cdot (q-1) = (5-1) \cdot (13-1) = 4 \cdot 12 = 48 \). For example, \( e = 11 \) is relatively prime to \( 48 \) because \( \text{GCD}(48, 11) = 1 \).

User A wants to send a confidential message ("ALGEBRA") to user B using the RSA encryption system.

To do this, A retrieves B’s public encryption key from the directory, consisting of \( n_B = 1003 \) and \( e_B = 3 \).

Next, A must convert the message "ALGEBRA" into numerical form, encrypt it using B’s public key, and send the encrypted message to B.

1. Encrypting the Message

First, A converts each letter of the message into a numeric value using a predefined table where each letter corresponds to a two-digit number (e.g., "A = 00", "B = 01", ..., "Z = 25").

Letter	Number	Letter	Number	Letter	Number
A	00	B	01	C	02
D	03	E	04	F	05
G	06	H	07	I	08
J	09	K	10	L	11
M	12	N	13	O	14
P	15	Q	16	R	17
S	18	T	19	U	20
V	21	W	22	X	23
Y	24	Z	25

The message "ALGEBRA" is converted into:

$$ \text{A = 00, L = 11, G = 06, E = 04, B = 01, R = 17, A = 00} $$

Its numerical sequence becomes:

$$ 00 \ 11 \ 06 \ 04 \ 01 \ 17 \ 00 $$

Next, A divides the sequence into two-letter blocks (digraphs), each represented by a number.

Each block must meet two criteria:

1. The numeric value of the block must be smaller than \( n_B = 1003 \).
2. The block must be relatively prime to \( n_B \) (i.e., \( \text{GCD}(P_i, n_B) = 1 \)).

The resulting blocks are:

$$ \text{AL = 0011, GE = 0604, BR = 0117, AX = 0023} $$

Since the message has an odd number of characters, A appends the letter "X" to complete the final block.

The corresponding numeric values are:

$$ P_1 = 11, \quad P_2 = 604, \quad P_3 = 117, \quad P_4 = 23 $$

All these values are less than 1003 and relatively prime to 1003 (verified using \( \text{GCD} \)).

$$ \text{GCD}(11, 1003) = 1 $$

$$ \text{GCD}(604, 1003) = 1 $$

$$ \text{GCD}(117, 1003) = 1 $$

$$ \text{GCD}(23, 1003) = 1 $$

Encryption can now proceed.

Note: If any block exceeds \( n_B = 1003 \), the blocks must be further divided into smaller groups, such as \( k_B - 1 \), where \( k_B = 4 \), representing the number of digits in \( n_B \). Since \( n_B \) is known to both sender and recipient, they can coordinate this adjustment. In this case, however, it’s unnecessary as all blocks are already smaller than \( n_B \). Similarly, if a block is not relatively prime to \( n_B \), padding characters can be added to adjust the block values until they meet the required condition.

To encrypt each block \( P_i \), A uses B’s public key, \((n_B, e_B)\).

The encryption formula is:

$$ C_i = P_i^{e_B} \mod n_B $$

A performs the following calculations for each block:

$$ C_1 = 11^3 \mod 1003 = 328 $$

$$ C_2 = 604^3 \mod 1003 = 797 $$

$$ C_3 = 117^3 \mod 1003 = 825 $$

$$ C_4 = 23^3 \mod 1003 = 131 $$

The encrypted message is:

$$ C_1 = 328, \quad C_2 = 797, \quad C_3 = 825, \quad C_4 = 131 $$

Finally, A sends the encrypted message to B:

$$ [328, 797, 825, 131] $$

B receives the encrypted message and uses their private key to decrypt it. Only B can decrypt the message since they possess the private key required to reverse the encryption process.

2. Decrypting the Message

To decrypt the message, user B uses their private key \( d_B \), which is known only to them.

User B’s public key is \( n_B = 1003 \) and \( e_B = 3 \):

$$ K_B = (1003, 3) $$

B also knows the prime numbers \( p \) and \( q \) used to generate \( n_B = 1003 \). For example, \( p_B = 17 \) and \( q_B = 59 \):

$$ n_B = p_B \cdot q_B = 17 \cdot 59 = 1003 $$

Using the Euler’s Totient Function, B calculates \( \varphi(n_B) = 928 \), which counts the positive integers less than \( n_B = 1003 \) that are relatively prime to \( n_B \):

$$ \varphi(n_B) = (p_B - 1)(q_B - 1) $$

$$ \varphi(1003) = (17 - 1)(59 - 1) = 16 \cdot 58 = 928 $$

To determine the private key \( d_B \), B solves the congruence:

$$ e_B \cdot d_B \equiv 1 \pmod{\varphi(n_B)} $$

In this case:

$$ 3 \cdot d_B \equiv 1 \pmod{928} $$

This linear congruence is solved using the extended Euclidean algorithm.

First, divide \( 928 \) by \( 3 \) to find the greatest common divisor (GCD):

$$ 928 \div 3 = 309 \ \text{with a remainder of } r = 1 $$

The remainder is \( 1 \), confirming that \( \text{GCD}(3, 928) = 1 \) and that a solution exists.

Rewriting the equation in linear form allows \( 1 \) to be expressed as a linear combination of \( 3 \) and \( 928 \):

$$ 1 = 928 - 3 \cdot 309 $$

The coefficient of \( 3 \) gives the private key \( d_B \):

$$ d_B = -309 $$

Since private keys must be positive, B adjusts \( d_B \) using modulo \( \varphi(n_B) \):

$$ d_B = -309 + 928k $$

Setting \( k = 1 \):

$$ d_B = -309 + 928 = 619 $$

Thus, user B’s private key is:

$$ d_B = 619 $$

To decrypt each encrypted block \( C_i \), B uses the following formula:

$$ P_i = C_i^{d_B} \mod n_B $$

Where \( d_B = 619 \) and \( n_B = 1003 \).

B performs the calculation for each block of the encrypted message \( [328, 797, 825, 131] \):

1. For \( C_1 = 328 \):

$$ P_1 = 328^{619} \mod 1003 $$

The result is:

$$ P_1 = 11 $$

2. For \( C_2 = 797 \):

$$ P_2 = 797^{619} \mod 1003 $$

The result is:

$$ P_2 = 604 $$

3. For \( C_3 = 825 \):

$$ P_3 = 825^{619} \mod 1003 $$

The result is:

$$ P_3 = 117 $$

4. For \( C_4 = 131 \):

$$ P_4 = 131^{619} \mod 1003 $$

The result is:

$$ P_4 = 23 $$

The decrypted blocks \( P_i \) are:

$$ P_1 = 11, \quad P_2 = 604, \quad P_3 = 117, \quad P_4 = 23 $$

Adding leading zeros to ensure uniformity:

$$ P_1 = 0011, \quad P_2 = 0604, \quad P_3 = 0117, \quad P_4 = 0023 $$

The numerical sequence of the decrypted message is:

$$ 00 \ 11 \ 06 \ 04 \ 01 \ 17 \ 00 \ 23 $$

Using the letter-to-number conversion table, B reconstructs the original message:

$$ 00 = A, \quad 11 = L, \quad 06 = G, \quad 04 = E, \quad 01 = B, \quad 17 = R, \quad 00 = A, \quad 23 = X $$

The reconstructed message is "ALGEBRAX," where the final "X" is padding and can be removed.

Thus, B successfully decrypts the original message sent by A as "ALGEBRA."

This highlights the security of the RSA system, where only the private key holder can decrypt the encrypted message.