Differences

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

--- tanszek:oktatas:techcomm:breaking_rsa [2024/10/07 13:36] – created knehez
+++ tanszek:oktatas:techcomm:breaking_rsa [2024/11/26 08:23] (current) – [Example: Breaking RSA if we find \( p \) and \( q \)] knehez
@@ Line 1: / Line 1: @@
 ==== Breaking RSA ====
-### Breaking RSA
 The weak point of the RSA algorithm lies in the key generation: specifically, the difficulty of factoring \( N \) into its prime components. This factorisation is only possible through trial and error, and the algorithm remains secure until someone discovers a heuristic method to do it efficiently.
@@ Line 29: / Line 27: @@
 You can sense how difficult this task is: we are dealing with 617 digits, and unfortunately, the last digit is not even.
+==== Example: Breaking RSA if we find \( p \) and \( q \) ====
+=== Step 1: Given Data ===
+Suppose we know the **public key** \( (e, N) \):
+  * Public exponent \( e = 17 \)
+  * Modulus \( N = 55 \)
+To break the RSA encryption, we need to find the **private key** \( d \). This requires us to factor \( N \) into its prime factors \( p \) and \( q \).
+=== Step 2: Factor \( N \) ===
+We need to factor \( N = 55 \):
+  * \( p = 5 \)
+  * \( q = 11 \)
+These are the two prime factors of \( N \).
+==== Step 3: Calculate \( \phi(N) \) (Euler’s Totient Function) ====
+Once we have \( p \) and \( q \), we can compute \( \phi(N) \), which is required to compute the private key \( d \).
+\[
+\phi(N) = (p - 1) \times (q - 1)
+\]
+\[
+\phi(55) = (5 - 1) \times (11 - 1) = 4 \times 10 = 40
+\]
+==== Step 4: Find the Private Key \( d \) ====
+The private key \( d \) is the modular inverse of \( e \mod \phi(N) \), which satisfies the equation:
+\[
+d \times e \equiv 1 \mod \phi(N)
+\]
+We need to find \( d \) such that:
+\[
+d \times 17 \equiv 1 \mod 40
+\]
+Using the extended Euclidean algorithm, we find that:
+\[
+d = 33
+\]
+So the **private key** is \( d = 33 \).
+==== Step 5: Decrypt the Ciphertext ====
+Now that we have \( d \), we can decrypt the ciphertext. Suppose the ciphertext is \( C = 18 \).
+To decrypt, we use the formula:
+\[
+m = C^d \mod N
+\]
+\[
+m = 18^{33} \mod 55
+\]
+To compute this efficiently, we can use modular exponentiation:
+\[
+^{33} \mod 55 = 2
+\]
+So, the original **message** \( m = 2 \).
+=== Summary: ===
+  * We started with the public key \( (e = 17, N = 55) \) and a ciphertext \( C = 18 \).
+  * After factoring \( N \) into \( p = 5 \) and \( q = 11 \), we calculated \( \phi(N) = 40 \) and found the private key \( d = 33 \).
+  * Using \( d \), we decrypted the ciphertext \( C = 18 \) to recover the original message \( m = 2 \).
+This example illustrates how RSA encryption can be broken if someone manages to factor \( N \) into its prime factors \( p \) and \( q \).