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:

 

  1. Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.
  2. Security in Computing by Charles Pfleeger & Shari Lawrence Pfleeger, fourth Edition, PEARSON.
  3. Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.
  4. The Complete Reference – Network Security by Roberta Bragg, Mark Rhodes-Ousley & Keith Strassberg, Tata McGraw Hill
  5. Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley
  6. Hacking 6 Exposed by Stuart McClure, Joel Scambray & George Kurtz , Tata McGraw Hill .
  7. www.snort.org
  8. https://nmap.org