Heavily sourced from: Cryptography and Network Security, Fourth Edition by William Stallings.

Key GenerationPick two prime numbers: p and q

p = 7Compute n=p.q

q = 13

n=p.qCompute the Euler Totient of n: Φ(n) = (p-1)(q-1)

n=7 x 13

n=91

Φ(n) = (7-1)(13-1)Pick an integer e, such that the greatest common denominator between Φ(n) and e is 1, and e is greater than 1 but less than Φ(n)

Φ(n) = 6 x 12

Φ(n) = 72

gcd(Φ(n),e)=1 and e>1 and e<Φ(n) gcd(72,e)=1 Choosing e: 5Determine the value of d using the formula:

de mod Φ(n) = 1With d, e, and n computed, we have our keys:

dx5 mod 72 = 1

Possible values for dx5 need to be 72*(some integer) + 1:

73 (won't work)

145 (that will work)

145/5 = 29

Plugging into:

dx5 mod 72 = 1

29x5 mod 72 = 1

d = 29

Public Key: KU = {e, n} = {5, 91}Encryption and Decryption

Private Key: KR = {d, n} = {29, 91}

Now, we're ready to encrypt. Assuming plaintext M, we compute ciphertext using the formula: C=(M^e)mod(n)

Assuming plaintext M=10Compute 10^5 mod 91 via wolframalpha.

C = (M^e) mod(n)

C = (10^5) mod(91)

C = 82

Decryption uses the formula: M=(C^d)mod(n)

C = 82 (from above)Compute 82^29 mod 91 via wolframalpha

M = (C^29)mod(91)

M = (82^29)mod(91)

M = 10 (that worked!)

What's remarkable is how monstrous the math gets using relatively tiny prime numbers to start with. We started with 7, and 13 to create our keys, and our final computation (the decryption) required us to compute 82^29, which is:

31666620625027474232451213268613396669946986162166956032Our keys, were of a really trivial bit-length {5,91}, and {29,91}. Consider that most asymmetric algorithms talk about keys that are of lengths greater than 1000 bits. Now consider what the size of the exponents may look like, and the corresponding products which need to be modulo divided.

## No comments:

## Post a Comment