Question

Consider an RSA cryptosystem using \(p=7, q=\) 11 and \(g=13\) a. Compute \(n\) b. Compute \(\varphi\) c. Find \(h\)

Short answer

The computed values are \(n = 77\), \(\varphi(n) = 60\) and \(h = 37\)

Step-by-step solution

Computing n

The first requirement in the RSA algorithm is to compute \(n\). \(n\) is the multiplication of two prime numbers \(p\) and \(q\). Here, \(p = 7\) and \(q = 11\), hence \(n = p*q = 7*11 = 77\)

Computing φ(n)

The next step involves computing the function \(\varphi(n)\). In RSA, \(\varphi(n) = (p-1)*(q-1)\). Therefore, \(\varphi(n) = (7-1)*(11-1) = 6*10 = 60\)

Finding h

This involves determining the decryption exponent. \(h\) is the multiplicative inverse of \(g\) modulo \(\varphi(n)\). More formally, \(h = g^{-1} \mod \varphi(n)\). Given that \(g = 13\) and \(\varphi(n) = 60\), this can be computed using the Extended Euclidean Algorithm. With this process, \(h = 37\)

Key concepts

Prime Numbers

Prime numbers are the building blocks of the RSA cryptosystem. These are numbers greater than 1 that have no positive divisors other than 1 and themselves. In the RSA algorithm, the security is predicated on the difficulty of factoring the product of two large prime numbers.

In the context of RSA, two prime numbers, typically denoted as \(p\) and \(q\), are chosen and kept secret. They are crucial in computing the public and private keys. The product of these primes, \(n = p \times q\), determines the modulus for both the public and private keys, and its length, usually expressed in bits, is the key length.

• Prime numbers are chosen because of their fundamental properties in number theory.
• The factoring of their product, particularly if the primes are large, is a computationally hard problem which provides security for RSA.

In our example, the primes 7 and 11 are used to compute \(n\), which is at the heart of the RSA cryptosystem.

Euclidean Algorithm

The Euclidean Algorithm is a technique used to find the greatest common divisor (GCD) of two numbers, which is the largest number that divides both of them without leaving a remainder. In cryptography, particularly in RSA, the Extended Euclidean Algorithm plays a pivotal role as it is used to find the modular multiplicative inverse.

The Extended Euclidean Algorithm not only computes the GCD of two numbers \(a\) and \(b\), but also finds integers \(x\) and \(y\) such that \(a \times x + b \times y = \text{GCD}(a,b)\).

In RSA, we use this extended form to calculate the decryption key \(h\) which satisfies the congruence \(g \times h \equiv 1 \mod \varphi(n)\). This means that \(h\) is the multiplicative inverse of \(g\) modulo \(\varphi(n)\).

• The Euclidean Algorithm assures us that the multiplicative inverse exists if \(g\) and \(\varphi(n)\) are coprime—meaning they have a GCD of 1.
• For RSA, the multiplicative inverse is essential for decoding messages that have been encoded with the public key.

In the given exercise, the Extended Euclidean Algorithm would be employed to find the value of \(h\) that makes \(13 \times h \equiv 1 \mod 60\).

Modular Arithmetic

Modular arithmetic, often referred to as 'clock arithmetic', is a system of arithmetic for integers, where numbers 'wrap around' upon reaching a certain value—the modulus. The RSA cryptosystem heavily relies on this concept for its encryption and decryption processes.

A congruence of the form \(a \equiv b \mod m\) indicates that \(a\) and \(b\) leave the same remainder when divided by \(m\). In an RSA context, this is crucial for both key generation and the process of encrypting and decrypting messages.

Fundamentals of Modular Arithmetic in RSA:

• Encryption is performed using the public key exponent and the modulus, where the message \(M\) is raised to the power of the public key exponent and the result is taken modulo \(n\).
• Decryption involves the private key exponent and the same modulus, where the encrypted message is raised to the power of the private key exponent and the result is again taken modulo \(n\).
• The security of RSA comes from the fact that while it is easy to compute exponentiations modulo \(n\), it is difficult to reverse the process without the private key.

For example, in our exercise, finding the decryption exponent \(h\) involves computing the inverse of \(13\) modulo \(60\), which is a practical application of modular arithmetic.