Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 232

Adversary

Ciphertext
x e mod N

Plaintext
x

Encryption Decryption

y

y d mod N

Secret key

Public key

e , N e , N

AUTHENTICATED d , N

N = pq
ϕ ( N )=( p − 1 )( q − 1 )
1 = gcd ( e , ϕ ( N ))
d = e − 1

Generator

mod ϕ ( N )

Figure 9.7. Plain RSA Cryptosystem.

since it is described in a mathematical format. We will see that there are many bad ways
to use it in practice.)

Public parameter : an even integer s .
Setup : find two random different prime numbers p and q of size

s
2

bits. Set N =

, − − =

pq . Pick a random e until gcd( e ( p 1)( q 1)) 1. (Sometimes we pick a

= =

2 16

+

special e like e 17 or e 1 and we select p and q accordingly.) Set

d = e − 1 mod (( p − 1)( q − 1)).

Message : an element x ∈{ 1 ,..., N − 1 } .

Public key : K p = ( e , N ).

Secret key : K s = ( d , N ).

x e Encryption : y = mod N .

y d

Decryption : x = mod N .

We notice that the modulus N is of s bits. The security will highly depend on this
s parameter. In particular, if factoring integers of this size is easy, then RSA is not
secure because N is public and factoring N yields p and q , which are enough to enable
decryption. Typically, we take s

= 1024.

It is easy to check that the encryption is deterministic and that if we decrypt

x e mod N , we raise it to the power d modulo N and obtain x ed y = mod N . Since

ed ≡ 1 (mod ϕ ( N )), it can be written that ed = 1 + k ϕ ( N ). We have

y d x ed x 1 + k ϕ

( N )

mod N = mod N = mod N .

For gcd( x p , we can check that it is congruent to

x modulo p and modulo q separately, so it is x as well, due to the Chinese Remainder
Theorem. For gcd( x

, N ) = 1, this is x . For gcd( x , N ) =

, N ) = q , we similarly obtain x . Hence y decrypts well into x .

The complexity of the RSA algorithm is quite simple to analyze.