RSA Digital Signatures and Public-Key Cryptosystems

This post is a paper review on the RSA algorithm proposed by R.L. Rivest, A.Shamir, and L.Adleman. Their proposed algorithm has a wide application in public-key cryptography in network security of maintaining secure data communication.

All classical encryption methods (including the NBS standard by IBM) suffer from the "key distribution problem." The problem is that before a private communication can begin, another private transaction is necessary to distribute corresponding encryption and decryption keys to the sender and receiver, respectively. Typically a private courier is used to carry a key from the sender to the receiver. Such a practice is not feasible if an electronic mail system is to be rapid and inexpensive. Instead, a public-key cryptosystem needs no private couriers; there should be an algorithm to distribute their secret keys to the sender and receiver over the insecure communications channel.

Public Key Cryptosystems

RSA is an implementation of a "public-key cryptosystem". The concept of "public-key cryptosystem" was invented by Diffie and Hellman's work [1]. The cryptosystem should meet these properties:

(a) D(E(M)) = M
(b) D and E should be in low time complexity
(c) The process is efficient iff E for encrypt and D for decrypt
(d) E(D(M)) = M

A function $E$ compliance (a), (b), and (c) is a "trap-door one-way function", additionally; if it also satisfies (d), then it is a "trap-door one-way permutation". The two concepts of "trap-door one-way" are introduced in [1]. In the reviewed paper, the author explained that a function is "one-way" since it is easy to compute in one direction but very difficult to compute in the reversed direction. The function is called "trap-door" since its inverse is easy to compute once certain private "trap-door" information is known.

Assume Alice has a secret decryption function $D_A$ and a public encryption function $E_A$ which could be called by anyone. Similarly, Bob has private $D_B$ and a public $E_B$. If Bob wants to send a private message to Alice in a public-key cryptosystem, he should first retrieve $E_A$ from the public. Then he sends Alice the encrypted message $E_A(M)$. On Alice's side, she deciphers the message sent from Bob by calculating $D_A(E_A(M)) = M$. According to the property: the process is efficient iff E for encrypt and D for decrypt, which means only Alice can decipher $E_A(M)$. This process maintains private communication between Alice and Bob without private transactions (symmetric ciphered transaction).

Signatures

In the previous example, Bob could guarantee the message could only be seen by Alice since Bob uses $E_A$ to encrypt the message. However, from Alice's perspective, she could not guarantee that the message was from the real Bob.

To implement signatures, the public-key cryptosystem must be implemented with trap-door one-way permutations (decrypted message could be encrypted with $E$) since the decryption algorithm will be applied to unenciphered messages. Bob can prove himself as real by computing his "signature":

$$S=D_B(M)$$

Note that any message could be deciphered, no matter whether it is a ciphered text or not. He then encrypts $S$ using $E_A$ (for security) and sends the result $E_A(S)$ to Alice.  $M$ is not needed to be sent due to:

$$M=E_B(S)$$  (where $E_B$ is public)

A message-signature pair $(M, S)$ is made, and Bob cannot deny it since he used his $D_B$ to generate $S$, moreover; $M$ cannot be modified by Alice since she would have to create the corresponding signature $S$.

Therefore, the message-signature pair provide proof of Alice and Bob mutually.

RSA Overview

RSA applies the encryption process by using a public encryption key $(e, n)$ where $e, n \in +\mathbb{Z}$.  the message $M$ should less than $n$. Then encrypt the message by the following formula and get $C$ as the ciphertext.

$$C=M^e\mod n$$

The ciphertext $C$ could be decrypted by raising it to power $d$ and modulo $n$, the following formula describes this process.

$$M=C^d \mod n$$

Hence, the encryption key is $(e, n)$, and the decryption key is $(d, n)$. And users make their encryption key public and keep the corresponding decryption key secret.

RSA Algorithm

In the previous section - RSA Overview, $e$ and $d$ need to be calculated as a pair. The way of choosing appropriate $e$ and $d$ is illustrated as follows. Randomly choose two large primes $p$ and $q$, and calculate the $n$ by the following formula, just guarantee that $n$ is larger than the message to be encrypted.

$$n=p\cdot q$$

Then find a $d$ which is relatively prime to $(p-1)\cdot(q-1)$.

$$\gcd[d, (p-1)\cdot(q-1)] = 1$$

And find the corresponding $e$ by calculating modulo inverse.

$$(e\cdot d) \equiv 1 \quad (\text{mod} (p-1)\cdot(q-1))$$

The preceding calculation: the greatest common divisor, could be calculated using Euclidean Algorithm in $\mathcal{O}(\log(N))$ time complexity. As for the inverse modulo, since we have known $d$ and $(p-1)\cdot(q-1)$, $e$ could be solved by applying Extend Euclidean Algorithm in $\mathcal{O}(\log(\min(d, (p-1)\cdot(q-1))))$ time complexity.

Until now, the key calculations are finished, and we can get $(e,n)$ and $(d,n)$ which are the encryption key (public) and decryption key (private).

How RSA works?

According to the Euler totient function [2], which returns a number of positive integers less than $n$ which are relatively prime to $n$. For example, $p$ is a prime, then

$$\phi(p)=p-1$$

Since the algorithm calculates $n=p\cdot q$. By elementary properties

$$\phi(n) = \phi(p) \cdot \phi(q) = (p-1)\cdot(q-1)$$

Since $d$ is relatively prime to $\phi(n)$ because of $\gcd[d, (p-1)\cdot(q-1)] = 1$, it has a multiplicative modulo inverse $e$ in the ring of integers modulo $\phi(n)$.

$$(e\cdot d) \equiv 1 \quad (\text{mod}\phi(n))$$

By the functionality of encryption and decryption

$$D(E(M)) \equiv (E(M))^d \equiv (M^e) ^d (\text{mod} n) = M^{e \cdot d} (\text{mod} n)$$ (encryption and decryption)

$$E(D(M)) \equiv (D(M))^e \equiv (M^d) ^e (\text{mod} n) = M^{e \cdot d}  (\text{mod} n)$$ (signaturing)

and

$$M^{e \cdot d} \equiv M^{k \cdot \phi(n) + 1} (\text{mod} n)$$ (multiplicative modulo inverse)

by Euler and Fermat: for any integer $M$ which is relatively prime to $n$

$$M^{\phi(n)} \equiv 1 (\text{mod} n)$$

for all $M$ such that $p$ does not divide $M$

$$M^{p-1} \equiv 1 (\text{mod}p)$$

and since $(p-1)$ divides $\phi(n)$.

$$M^{k \cdot \phi(n) + 1} \equiv M (\text{mod}p)$$

Similarly, $(q-1)$ divides $\phi(n)$,

$$M^{k \cdot \phi(n) + 1} \equiv M (\text{mod}q)$$

Hence, for all $M$

$$M^{e \cdot d} \equiv M^{k \cdot \phi(n) + 1} \equiv M (\text{mod} n)$$

Then we proved that $M$ could reveal by decrypting using $(d, n)$.

RSA Reliability

All the mathematical variables used in the algorithm are $p, q, n, e, d, \phi(n)$. According to the process, only $(e, n)$ is public, and $p, q, d,\phi(n)$ is private, where $d$ is a component of the private key and should be kept secret.

To prove the reliability of RSA, we should figure out if there is an approach to determine $d$ by having only $n$ and $e$. Regarding the algorithm, we have

$$(e\cdot d) \equiv 1 \quad (\text{mod};\phi(n))$$

(means we need to determine $\phi(n)$ to calculate $d$, since we already know $e$)

$$\phi(n) = (p-1)(q-1)$$

(means we have to figure out $p$ and $q$, the randomly selected large prime)

$$n = p\cdot q$$

(means that the only way to get $p$ and $q$ is by factoring the large integer $n$)

Hence, the difficulty of factorizing a very large integer determines the reliability of the RSA algorithm. In other words, the more difficult it is to factorize a very large integer, the more reliable the RSA algorithm is.

In the paper, the author mentioned the fastest factoring algorithms, in which factoring a number seems to be much more difficult than determining whether it is prime or composite.

Conclusion

RSA is an implementation of public-key cryptography put forward by R.L. Rivest, A.Shamir, and L.Adleman in 1977, and it has a broad application nowadays. RSA is a relatively slow algorithm. Hence, it is not usually used to encrypt user data directly. Instead, it could establish a private session between two terminals by transmitting shared session keys for symmetric-key cryptography, which are then used for maintaining encryption–decryption.

References

Original Paper: Rivest, R. L., Shamir, A., & Adleman, L. (1983). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 26(1), 96–99. https://doi.org/10.1145/357980.358017

1. Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6), 644–654. https://doi.org/10.1109/tit.1976.1055638
2. Niven, I., and Zuckerman, H.S. An Introduction to the Theory of Numbers. Wiley, New York, 1972.⏎