El Gamal explained

May 19, 2010

This is a work in progress. I need to check as there is an Error in the Decryption ! I will edit when I get time to fix the issue.

El-Gamal (Simplified)

Key generation

Alice has a prime number (p) Special Number (g) and a random number for her private key (a)

  • (p) is the key so needs to be long (1024\2048)
  • (g) must be a primitive element modulo (p)
  • (a) must be bigger than 1 and smaller than p-1

The algorithm is A = ga mod p

Alice’s public key is A

Alice’s private key is a.

The system-wide parameters are p & g

Simplified key generation Example

p = 23

g = 11

a = 6

Therefore, A = ga (mod p)

Therefore 9 = 116 (mod 23)

Alice’s public key is 9 (A), and her private key is 6 (a).

The public key is known to everyone and the parameters p & g are known to everyone

Simplified Encryption Example

The example message Bob sends is 10 (M)

Bob generate a random number 3 (k).

Compute C1 and C2 where C1=gk mod p and C2=MAk mod p

Bob sends (C1,C2) to the Alice, this contains the message and value k.

Therefore if C1=gk mod p and C2=MAk mod p

Then C1=113 mod 23 and C2=10*93 mod 23

C1=20, C2= 22

The cipher text is (20, 22)

Simplified Decryption Example

Alice receives (20,22)

The calculation is C2 / C1a=(gk)a mod p

where 206 = (113)6 mod 23. Both calculate as 16

(This is where the final calculation goes, when I figure it out !)

Advertisements

Lifelock –

May 19, 2010

Lifelock is a company that guarantees to protect you from Identity theft, for only $10 dollars a month.

They are so cofident that they can protect your ID, that their advertisements include the Social Security Number of their CEO (From Wired.com)

Pretty good so far. Until you find out his identity has been stolen 13 times since 2007.

If the CEO of an identity protection company can’t even keep his own identity secure, would you trust them…….

RSA explained

May 5, 2010

I’ve been struggling to learn the mathematics behind RSA encryption. This is my “aid Memoir” I’m trying to memories.

Key Creation

• Choose primes p and q
Pick two prime numbers, e.g. 7 & 17
• Calculate the Modulus N, where N=pq
Multiply the two prime numbers to create N (7×17)=119
• Choose an e, where 1 < e <(p-1)(q-1) and GCD(e, (p-1)(q-1)) = 1
Pick a prime number e that is less than (p-1)*(q-1). (6*16)=96 and where the Greatest common devisor (GCD) of all three (e, p-1, q-1) is 1 (i.e. no other common devisors)
In This case, we pick 37.
• Public key is (N, e)
Public key are the two numbers N & e. (119,37)
• Compute d, where d = e^-1 mod (p-1)(q-1)
e^-1 mod (p-1)(q-1)
37^-1 mod 6×16
37^-1 mod 96
37*13=1 (Mod 96)
• Private key is d
The Private key is 13

p=7, q=17
N= 119
e = 37
d = 13

Public Key is (119,37)
Private Key is (13)

Encryption

We will use the cleartext “14” for this example

Encryption uses the algorithm C ^ e = E ( mod N )
This is Cleartext to the power of The Prime number from the Public Key = answer (Mod N (the multiplication of the original two prime numbers)

14^37= “Huge Number” (Mod 119) =63 (By my calculator)

The Encrypted text (E) is “63”

Decryption

Decryption uses the algorithm E ^ d = C ( mod N)

63^13 =C (mod 119)
63^13 = 14 (Mod 119)
63^13 = “Huge Number” (Mod 119) = 14