Differences

This shows you the differences between two versions of the page.

--- tanszek:oktatas:techcomm:rsa_encryption [2024/10/07 13:14] – created knehez
+++ tanszek:oktatas:techcomm:rsa_encryption [2024/11/26 08:25] (current) – [Example] knehez
@@ Line 1: / Line 1: @@
 ==== The Basic Model of Public Key Systems ====
-=== Communication model: ===
+{{:tanszek:oktatas:techcomm:pasted:20241007-131716.png}}
-. Alice generates a pair of keys: **e** (public key) and **d** (private key).
+. Alice generates a pair of keys: **e** (public key) and **d** (private key). In this context **e** means (**e**ncryption key) and **d** (**d**ecryption key).
 . She keeps **d** secret, but makes **e** public.
@@ Line 14: / Line 14: @@
 The system is secure from a decryption perspective because only Alice can decrypt the message, but Alice can never be sure if Bob sent the message, as the public key **e** can be used by anyone.
+==== RSA ====
+**Rivest, Shamir, Adleman (1977)** developed the RSA algorithm, which is based on exponentiation and modular arithmetic (remainder division). The RSA encryption relies on the fact that if the following equation holds:
+\[
+T^d \mod N = T
+\]
+Then the equation can be split into two parts, where the first equation represents encryption and the second represents decryption:
+  * **Encryption**: \( C = T^e \mod N \)
+  * **Decryption**: \( T = C^d \mod N \)
+However, this relationship does not work for just any arbitrary choice of \( e \), \( d \), and \( N \). The algorithm relies on specific conditions for these values. Let’s explore what conditions are required for the RSA algorithm to function correctly.
+=== How RSA Works ===
+The RSA algorithm uses both **public** and **private keys**. For it to work correctly, the following steps are followed:
+.) **Key Generation**:
+   * Choose two large prime numbers: \( p \) and \( q \).
+   * Calculate \( N = p \times q \).
+   * Compute Euler’s totient function \( \phi(N) = (p-1) \times (q-1) \). ([[https://en.wikipedia.org/wiki/Euler's_totient_function| totient function]])
+   * Choose a public exponent \( e \) such that \( e \) is relatively prime to \( \phi(N) \) (i.e., \( 1 < e < \phi(N) \) and \( \gcd(e, \phi(N)) = 1 \)).
+   * Compute the private key \( d \), which is the modular multiplicative inverse of \( e \), meaning \( d \times e \equiv 1 \mod \phi(N) \).
+.) **Encryption**:
+The message \( T \) is encrypted using the public key: \( C = T^e \mod N \).
+. **Decryption**:
+The ciphertext \( C \) is decrypted using the private key: \( T = C^d \mod N \).
+=== Conditions for the Keys ===
+The equations work correctly only when specific conditions are met:
+  * \( N \) must be large enough to prevent attackers from easily factoring \( N \) into \( p \) and \( q \), which would compromise the encryption.
+  * The public exponent \( e \) and the private exponent \( d \) must have a specific relationship with \( N \) and Euler’s totient \( \phi(N) \). The relationship between \( e \) and \( d \) is that \( e \times d \equiv 1 \mod \phi(N) \), ensuring that decryption reverses the encryption process.
+=== Summary ===
+The RSA algorithm depends on the correct choice of prime numbers \( p \) and \( q \), the calculation of \( N \), and the mathematical relationship between the exponents \( e \) (public key) and \( d \) (private key). Without these specific conditions, the encryption and decryption process will not work properly.
+==== Example ====
+=== Step 1: Key Generation ===
+.) **Choose two large prime numbers** \( p \) and \( q \):
+   * \( p = 61 \)
+   * \( q = 53 \)
+.) **Compute \( N \)** (the modulus):
+\[
+   N = p \times q = 61 \times 53 = 3233
+\]
+So, \( N = 3233 \).
+.) **Compute Euler’s totient function** \( \phi(N) \):
+\[
+   \phi(N) = (p - 1) \times (q - 1) = (61 - 1) \times (53 - 1) = 60 \times 52 = 3120
+\]
+So, \( \phi(N) = 3120 \).
+. **Choose a public exponent** \( e \), such that \( 1 < e < \phi(N) \) and \( \gcd(e, \phi(N)) = 1 \):
+   * Let’s choose \( e = 17 \), which is relatively prime to 3120.
+. **Calculate the private exponent** \( d \), which is the modular multiplicative inverse of \( e \mod \phi(N) \):
+\[
+   d \times e \equiv 1 \mod \phi(N)
+\]
+Using the extended Euclidean algorithm, we find that \( d = 2753 \).
+=== Step 2: Encryption ===
+Now that the keys are set, let’s encrypt a message. Suppose our message is a number \( m = 65 \).
+.) **Public key** is \( (e, N) = (17, 3233) \).
+.) **Encryption formula**:
+\[
+   c = m^e \mod N
+\]
+   * \( m = 65 \), \( e = 17 \), \( N = 3233 \).
+   * Compute \( 65^{17} \mod 3233 \):
+Using modular exponentiation:
+\[
+^{17} \mod 3233 = 2790
+\]
+So, the **ciphertext** \( c = 2790 \).
+=== Step 3: Decryption ===
+Now, Alice receives the ciphertext \( c = 2790 \) and uses her private key \( d = 2753 \) to decrypt the message.
+.) **Private key** is \( (d, N) = (2753, 3233) \).
+.) **Decryption formula**:
+\[
+   m = c^d \mod N
+\]
+   * \( c = 2790 \), \( d = 2753 \), \( N = 3233 \).
+   * Compute \( 2790^{2753} \mod 3233 \):
+Again, using modular exponentiation:
+\[
+^{2753} \mod 3233 = 65
+\]
+Thus, Alice successfully decrypts the message and retrieves the original plaintext **65**.
+=== Summary of the RSA Example: ===
+  * Public key: \( (e = 17, N = 3233) \)
+  * Private key: \( (d = 2753, N = 3233) \)
+  * Message to encrypt: \( m = 65 \)
+  * Ciphertext: \( c = 2790 \)
+  * Decrypted message: \( m = 65 \)
+This is a simple RSA example. In real-world applications, much larger prime numbers \( p \) and \( q \) are used to ensure security.