Cryptography Overview
54 RSA BSAFE Crypto-C Developer’s Guide
The calculation is shown in Table 3-1:
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 = m
e
mod n. To recover the
original message, compute m = c
d
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.
Table 3-1 Calculation of 8
27
mod 55
8
0
1 mod 55
8
1
8 mod 55
8
2
8
1
· 8
1
= 8 · 8 = 64
64 – 55 = 9 9 mod 55
8
4
8
2
· 8
2
= 9 · 9 = 81
81 – 55 = 26 26 mod 55
8
8
8
4
· 8
4
= 26 · 26 = 676 676 – (12 · 55) = 16
16 mod 55
8
16
8
8
· 8
8
= 16 · 16 = 256 256 – (4 · 55) = 36
36 mod 55
8
1
· 8
2
8 · 9 = 72
72 – 55 = 17
(8
1
· 8
2
) · 8
8
17 · 16 = 272 272 – (4 · 55) = 52
52 mod 55
(8
1
· 8
2
· 8
8
) · 8
16
52 · 36 = 1872 1872 – (34 · 55) = 2
2 mod 55
