10 Public key Algorithm Part 2
Hiteishi Diwanji
RSA algorithm:
1. p,q two prim numbers
2. n=pq
3. Encryption key e, with GCD(Ф(n),e) =1; 1<e< Ф(n), Ф(n) is called totient function.
4. d=e-1 (mod Ф(n))
5. C=Me mod n, M is the message to be transmitted called plaintext. C is the ciphertext. M<n
6. M= Cd mod n
Private key consist of [d,n] and public key consist of [e,n]
Example:
1. Select two primes, p=17 and q=11
2. Calculate n=pq=17×11=187
3. Calculate Ф(n) = (p-1)(q-1) = 16×10=160
4. Select e such that e is relatively prime to Ф(n)=160 and less than Ф(n). Suppose e=7
5. Determined such that de≡1 ( mod 160) and d<160. d=23 because
23×7=161=(1×160)+1;
Use extended Euclid’s algorithm to calculate d.
PU=[7,187] PR=[23,187]
M=88 C=?
C=887 mod 187
Exponentiation in modular arithmetic:
- ¨ a16 =axaxaxaxaxaxaxaxaxaxaxaxaxaxaxa
- ¨ a16 can be achieved by repeatedly squaring each partial result(a2,a4,a8,a16)
- ¨ To calculate a11 = (a) (a2)(a8). Calculate a mod n,a2 mod n,a4 mod n,a8 mod n. Then calculate [(a mod n)x(a2 mod n)x(a8 mod n)] mod n.
For ab mod n – a,b,n positive integers.
- ¨ b expressed as binary number bkbk-1…b0
Algorithm computing ab mod n. b is expressed as bkbk-1..b0
- ¨ C← 0, f ← 1
- ¨ For i ← k downto 0 do c ← 2xc
f ← (fxf) mod n
if bi = 1
then c ← c+1
f ← (fxa) mod n
Encryption – Decryption through RSA:
C=887 mod 187
C=11
For decryption, M=1123 mod 187 = 88
The security of RSA:
¨ Brute force – trying all possible keys
¨ Mathematical attack – factoring the product of two primes.
¨ Timing attacks – depends on running time of decryption algorithm.
¨ Hardware fault based attack – hardware fault in processor.
¨ Chosen ciphertext attack.
Distribution of public keys:
¨ Public announcement
¨ Publicly available directory
¨ Public key authority
¨ Public key certificates
Distribution of public keys – Public announcement
Suggested Reading:
- Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.
- Security in Computing by Charles Pfleeger & Shari Lawrence Pfleeger, fourth Edition, PEARSON.
- Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.
- The Complete Reference – Network Security by Roberta Bragg, Mark Rhodes-Ousley & Keith Strassberg, Tata McGraw Hill
- Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley
- Hacking 6 Exposed by Stuart McClure, Joel Scambray & George Kurtz , Tata McGraw Hill .
- www.snort.org
- https://nmap.org