Differences

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

--- tanszek:oktatas:techcomm:rsa_encryption [2024/10/07 13:21] – 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 ====
-=== Basic communication model ===
 {{:tanszek:oktatas:techcomm:pasted:20241007-131716.png}}
@@ Line 39: / Line 37: @@
    * 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) \).
+   * 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) \).
@@ Line 61: / Line 59: @@
 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.
-Your original description was generally correct, but the conditions governing \( e \), \( d \), and \( N \), especially the relationship with Euler’s totient function, are crucial for the RSA algorithm to function securely. Let me know if you'd like further clarification, or I can provide an example with actual numbers to show the process step-by-step!
+==== 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.