Question

Suppose you are doing RSA encryption with \(p=13, q=7\), and \(e=5 .\) (a) Find the decryption exponent \(d\). (Hint: Use the Euclidean dividing algorithm.) (b) Encrypt the message \(m=7 .\) (c) Decrypt the cypher \(c=2\).

Short answer

Finding values for encryption exponent \( d = 29 \), cyphertext \( c = 14 \), decrypted message \( m = 64 \).

Step-by-step solution

Calculate n

First, we need to calculate the value of \( n \). It is given by the product of the primes \( p \) and \( q \). So, \( n = p \times q \). Here, \( p = 13 \) and \( q = 7 \), thus:\[ n = 13 \times 7 = 91 \]

Calculate Euler's Totient Function \( \Phi(n) \)

Next, calculate the value of Euler's totient function \( \Phi(n) \) which is given by \((p-1) \times (q-1) \). So:\[ \Phi(n) = (13-1) \times (7-1) = 12 \times 6 = 72 \]

Find the Decryption Exponent \( d \)

We need to find \( d \), the modular multiplicative inverse of \( e \) modulo \( \Phi(n) \). Using the Extended Euclidean Algorithm to solve for \( d \) in the equation:\[ e \times d \equiv 1 \pmod{\Phi(n)} \rightarrow 5 \times d \equiv 1 \pmod{72} \]Using the Extended Euclidean Algorithm:\[ 5d = 1 + 72k \rightarrow d = ... \]Finding the smallest positive \( d \), we get \( d = 29 \).

Encrypt the Message \( m \)

The encryption process involves computing the ciphertext \( c \) using the formula:\[ c = m^e \mod n \]Given \( m = 7 \) and \( e = 5 \), we find:\[ c = 7^5 \mod 91 \rightarrow c = 16807 \mod 91 = 14 \]

Decrypt the Cypher \( c \)

Finally, decrypt the cyphertext \( c \) using the decryption exponent \( d \) with the formula:\[ m = c^d \mod n \]Given \( c = 2 \), \( d = 29 \), and \( n = 91 \), we find:\[ m = 2^{29} \mod 91 \rightarrow m = 64 \]

Key concepts

RSA algorithm

The RSA algorithm is a cornerstone of public-key cryptography. Named after its creators Rivest, Shamir, and Adleman, this algorithm empowers secure data transmission even over insecure channels.
The RSA process involves two keys: a public key for encryption and a private key for decryption. The public key is known to everyone, but the private key remains secret.
RSA's security stems from the difficulty of factorizing large prime numbers. Here’s a high-level overview of the RSA steps:

• Choose two large prime numbers: p and q.
• Compute their product, n. This forms part of the public and private keys.
• Calculate Euler's Totient Function Φ(n).
• Select an encryption exponent e, typically a small odd number like 3 or 5.
• Determine the decryption exponent d using the Extended Euclidean Algorithm, ensuring e*d ≡ 1 (mod Φ(n)).

The encryption and decryption processes are mathematically intense but hinge on modular arithmetic and exponentiation.

Modular arithmetic

Modular arithmetic forms the backbone of many cryptographic algorithms, including RSA. It deals with integers within a fixed range, looping back to the start once a specified value, called the modulus, is reached.
Think of a clock: after 12 hours, it starts again from 1. In modular arithmetic, we say 13 ≡ 1 (mod 12).
Let's break down useful operations:

• Addition: (a + b) mod n
• Subtraction: (a - b) mod n
• Multiplication: (a * b) mod n
• Exponentiation: a^b mod n

For example, in RSA encryption, we use:

• Public key: (e, n) where e is the encryption exponent
• Private key: (d, n) where d is the decryption exponent

Encryption converts the message m to ciphertext c: c ≡ m^e (mod n). For decryption, we transform the ciphertext back to the message m: m ≡ c^d (mod n).
Understanding modular arithmetic lets us grasp how encryption and decryption stay secure yet feasible.

Extended Euclidean Algorithm

The Extended Euclidean Algorithm finds the greatest common divisor (GCD) of two numbers and expresses it as a linear combination of those numbers. This is particularly crucial in RSA for determining the decryption exponent d.
Here’s a short guide to its use:

• Start with two numbers, a and b.
• Apply the Euclidean algorithm to identify GCD(a, b).
• Extend this algorithm to backtrack and express GCD as a combination a*x + b*y.

For RSA, you'd solve for:

• e*d ≡ 1 (mod Φ(n))

where e is the encryption exponent. An example for our case study:

• Equation: e*d = 1 + k*Φ(n)
• With e = 5, Φ(n) = 72, our GCD process yields d = 29.

The Extended Euclidean Algorithm helps ensure d is the correct multiplicative inverse, crucial for decrypting messages securely.

Public-key cryptography

Public-key cryptography revolutionized secure communications. Unlike symmetric-key systems, where the same key is used for both encryption and decryption, public-key systems use paired keys.
In RSA, anyone can use the public key to encrypt a message, but only those with the private key can decrypt it.
Benefits include:

• Convenience: Distributing public keys publicly doesn't compromise security.
• Security: Private keys remain confidential, ensuring secure decryption.
• Versatility: Used in digital signatures, ensuring data integrity and authenticity.

Here’s how RSA utilizes this mechanism:

• Key generation involves selecting and multiplying large primes p and q to create n.
• Encryption applies the public key (e, n) to a message m.
• Decryption uses the private key (d, n) to revert the message.

With its unique key pairing and robust mathematical foundation, public-key cryptography like RSA ensures data confidentiality and security over potentially insecure channels.