RSA Security 5.2.2 Summary, Security, Calculation is shown in Table, 1Calculation of 827 mod

Cryptography Overview

The calculation is shown in Table 3-1:

Table 3-1Calculation of 827 mod 55

80							1 mod 55
81							8 mod 55
82		81	· 81		= 8 · 8 = 64	64 – 55 = 9	9 mod 55
84		82	· 82		= 9 · 9 = 81	81 – 55 = 26	26 mod 55
88	84	· 84		= 26 · 26 = 676		676 – (12 · 55) = 16	16 mod 55
816	88	· 88		= 16 · 16 = 256		256 – (4 · 55) = 36	36 mod 55
81 · 82				8 · 9 = 72		72 – 55 = 17
(81 · 82) · 88			17 · 16 = 272			272 – (4 · 55) = 52	52 mod 55
(81 · 82 · 88) · 816		52 · 36 = 1872				1872 – (34 · 55) = 2	2 mod 55

Summary

Take two large primes, p and q, and find their product n = p · q. Set n to be the modulus. Choose a public exponent, e, less than n and relatively prime to (p–1)(q–1). Find d, the inverse of e mod (p–1)(q–1),that is, ed ≡ 1 mod (p–1)(q–1). The pair (n,e) is the public key; d is the private key (or the private exponent). The primes p and q must be kept secret or destroyed.

To compute ciphertext c from a plaintext message m, find c = me mod n. To recover the original message, compute m = cd mod n. Only the entity that knows d can decrypt.

Note: In public-key cryptography, it is also possible to encrypt using a private key. In this case, the sender takes the plaintext input and the private key and follows the same steps need to decrypt an encrypted file. This creates a ciphertext that can be read using the public key; to read it, the recipient follows the same steps needed to encrypt with the public key and restores it to the plaintext. This is used in authentication and digital signatures.

Security

The security of the RSA algorithm relies on the difficulty of factoring large numbers. In theory, it is possible to obtain the private key d from the public key (n,e) by factoring n into p and q. To find d, one must know the product (p–1)(q–1). But to find that value, one must know p and q. For example, in the earlier example, an attacker would know that p · q = 55, but what is (p–1)(q–1)? Factoring 55 into its component primes is easy: the answer is 5 and 11.

5 4 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e