## 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 = g^{a} 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 = g^{a} (mod p)

Therefore 9 = 11^{6} (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=g^{k} mod p and C2=MA^{k} mod p

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

Therefore if C1=g^{k} mod p and C2=MA^{k} mod p

Then C1=11^{3} mod 23 and C2=10*9^{3} mod 23

C1=20, C2= 22

The cipher text is (20, 22)

**Simplified Decryption Example**

Alice receives (20,22)

The calculation is C2 / C1^{a}=(g^{k})^{a} mod p

where 20^{6} = (11^{3})^{6}^{ }mod 23. Both calculate as 16

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

## 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