Subject | Computer and Network Security |
---|---|

NU Year | Set: 2.(c) Marks: 6 Year: 2017 |

RSA algorithm is a typical
public-key cryptosystem.

It is a basic technique of many
security protocols. It

can be described briefly as follows:

1. Choose two large strong primes, p
and q. Let n =

pq.

2. Compute Euler value of n: )(n) =
(p - 1)(q - 1).

3. Find a random number e satisfying
1 < e < )(n) and

gcd(e,)(n)) = 1.

4. Compute a number d such that d = e-1
mod )(n).

5. Encryption: Given a message m
satisfying m < n,

then the cipher text c = me mod n.

6. Decryption: m = cd mod n.

The security of RSA is based on the
hard of

factoring n. To enhance the hardness
of factoring n,

Ogiwara [6] suggests the following
constraints on p and

q:

1. Both (p - 1) and (q - 1) should
contain a large prime

factor such that r1|(p – 1) and t1|(q
– 1), where r1

and t1 are two large primes.

2. Both (p + 1) and (q + 1) should
contain a large prime

factor such that s1|(p + 1) and u1|(q
+ 1), where s1

and u1 are two large primes