Modular exponentiation Confusion

[Siksissk]

Hi all,

First off, not sure which forum maybe the most relevant, hopefully this one is the most suited?

I do not have much of a background in maths, so bare with me.

I am trying to implement a Modular exponentiation encryption method, I am using
http://en.wikipedia.org/wiki/Modular_exponentiation

the encryption I am happy with, but what I am stuck on is the decryption method.

Can anyone point me to a good bit of text, that explains the method in simple terms.

Thank you.

P.S. apologies if this belongs in the comp science forums.

 

[Deveno]

ok, so what you are doing is creating an encryption c, by taking the original message b, and computing b^e (mod m).

in this case, e can be thought of as "the encryption key", and the reduction mod m keeps the encryption c = b^e in a manageable range. we want to choose e and m in such a way that we can also uniquely "decrypt" c, by taking:

c^d = b (mod m), for some "decryption" (private) key d. so we need 3 integers, e,d and m that makes this all work out. the most popular method (RSA algorithm) does it this way:

1. choose 2 prime numbers, p and q. we are going to use m = pq (the idea being that even if m is known (public information), p and q are quite difficult to recover).

2. compute φ(m) = φ(p)φ(q) = (p-1)(q-1). this is sensitive information, as knowing either p or q, would allow the other to be calculated quickly, thus revealing φ(m). conversely, if φ(m) were to be discovered, it is possible to calculate p and q in terms of m and φ(m).

3. choose e so that gcd(e,φ(m)) = 1. this is critical, because it is what allows us to devise the decryption key d. often, e is chosen to be a small prime, such as 3 (most of the numbers < m = pq will be co-prime to φ(m), so it's likely 3 will be. in the rare cases where it's not, 7 or 13 also make good choices).

now if gcd(e,φ(m)) = 1, there is always a unique d such that de = 1 (mod φ(m)). obviously, d must be kept secret (private key).

then c^d (mod m) = (b^e)^d (mod m) = b^de (mod m) = b^{(1 + kφ(m))} (mod m)

= (b)(b^φ(m))^k (mod m)

= b(1^k) (mod m) = b (mod m).

this is because the group of units mod m, has φ(m) elements, and any group element raised to the order of the group gives the identity, and the identity of the group of units mod m is 1 (mod m). we chose e to be in this group of units, and this allows us to pick d = e^-1 (mod m).

to give an unrealistically small example, let p = 3, q = 7. so we are going to work mod 21.

now φ(21) = φ(3)φ(7) = 12. so our choices of e are limited to numbers relatively prime to 12. 11 works. so let's say our original message is "12".

our encrypted message is (12)¹¹ mod 21 = 3.

to decrypt this message, we need to know d. as we saw above d = 11^-1 (mod 12). although one can use the euclidean algorithm to compute d, since 12 is so small, it is quicker to use trial-and-error (showing why larger primes p and q should be used). in this case, 11 is its own inverse (mod 12) (11*11 = 121 = 1 (mod 12)).

so, decrypting, we take 3¹¹ (mod 21), which gives us back 12.