9 Public key Algorithm Part 1

Hiteishi Diwanji

epgp books

The modulus:

  • ¨ Let a be an integer and n a positive integer. a mod n gives the remainder when a is divided by n.
  • ¨ n is called modulus.
  • ¨ a = qn + r 0<=r<n; q=└a/n┘
  • ¨ a= └a/n┘xn + (a mod n)

Congruent modulo n:

  • ¨ if (a mod n) = ( b mod n) then a ≡ b (mod n)
  • ¨ 73 ≡ 4 ( mod 23) as

73 mod 23 = 4 and

4 mod 23 = 4.

  • Is 21 ≡ -9 (mod 10) ?
  • ¨ 21 mod 10 =1
  • ¨ -9 mod 10

-9 = 10x-1 + 1

so -9 mod 10 = 1.

  • ¨ So It is true that 21 ≡ -9 (mod 10)

Practical public key cryptosystem – suitable trap door one way function:

 

  • ¨ Y=fk(X) easy if k and X are known
  • ¨ X=fk-1(Y) easy, if k and Y are known
  • ¨ X=fk-1(Y) infeaible, if Y is known but k is not known

 

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. C is the ciphertext.
  6. M= Cd mod n

Private key consist of [d,n] and public key consist of [e,n]

 

Greatest common divisor and relatively primenumbers :

 

  • ¨ GCD (a,b) of a and b is the largest number that divides a,b. GCD(16,12) = 4
  • ¨ When no common factors (except 1) , then numbers are relatively prime GCD(8,15) = 1

 

hence 8 & 15 are relatively prime

 

Ф(n) totient function:

 

  • ¨ Ф(n) is number of positive integers less than n and relatively prime to n.
  • ¨ Ф(1) = 1
  • ¨ To calculate Ф(24) , take all the positive integers less than 24 that are relatively prime to 24

 

1,5,7,11,13,17,19,23

 

There are 8 numbers so Ф(24) = 8.

 

Euclidean algorithm to find GCD(greatest common divisor) – uses theorem that: GCD(a,b) = GCD(b, a mod b)

 

EUCLID(a,b)

  1. A = a; B = b
  2. if B = 0 return A = gcd(a, b)
  3. R = A mod B
  4. A = B
  5. B = R
  6. goto 2

Example GCD(576,132):

 

576 = 132 x 2 + 48 GCD(576,132)
132 = 48 x 2 + 36 GCD(132,48)
48 = 36×1 + 12 GCD(48,36)
36= 12×3 + 0 GCD(36,12)
GCD(576,132)=12

 

To find multiplicative inverse b-1 mod m EXTENDED EUCLID(m, b):

 

EXTENDED EUCLID(m, b)

 

  1. (A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b)
  2. if B3 = 0

return A3 = gcd(m, b); no inverse

  1. if B3 = 1

return B3 = gcd(m, b); B2 = b–1 mod m

  1. Q = A3 div B3
  2. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)
  3. (A1, A2, A3)=(B1, B2, B3)
  4. (B1, B2, B3)=(T1, T2, T3)
  5. goto 2

 

Inverse of 550 mod 1759:

Q A1 A2 A3 B1 B2 B3
– 1 0 1759 0 1 550

 

3 0 1 550 1 -3 109
5 1 -3 109 -5 16 5
21 -5 5 106
16 -339 4
1 106 -339 4 -111 355 1

 

you can view video on Public key Algorithm Part 1

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