|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 =
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  suggests the following constraints on p and
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