RSA Encryption SSH Keys

This is more of an exercise.  Blog readers can ignore.  Used Fermat's Little Theorem instead of Euler's since imho using Euler's Theorem is wrong.  

PS: What drove me to write this was that I found a couple proofs on the internet that seemed wrong to me.  Finally, I read this on wikipedia that made me happy:

Numerous references which explain RSA using Euler's theorem deal with the case that the message m is not relatively prime to the modulus pq by a misleading probabilistic argument: the proportion of integers mod pq that have a factor in common with the modulus is 1 - (p-1)(q-1)/pq = 1/p + 1/q - 1/pq, which is very small when p and q are large so the chance of the message having a factor in common with the modulus can be considered remote in practice. What is misleading here is that, as the proof with Fermat's little theorem shows, nothing breaks down in the case of messages having a factor in common with the modulus: one has m^ed ≡ m mod n for all m without exceptions. Therefore the correctness of RSA should really be considered an application of Fermat's little theorem rather than Euler's theorem, just as in the original RSA paper.

Facts:

1. Fermat's Little Theorem: If p is prime and p∤a then a^(p-1) ≡ 1 mod(p)

2. For distinct primes  p and q, if a ≡ b mod(p) and a ≡ b mod(q) then a ≡ b mod(pq)

3. For prime p, φ(p) = p - 1

Choose:

Choose distinct primes p,q.  Let N = pq.

Choose e where 1 < e < φ(N) and gcd(e,φ(N)) == 1

Choose d where ed ≡ 1 mod(φ(N))

Encrypt M to C:

C ≡ M^e mod(N)

Decrypt C to M:

M ≡ C^d mod(N)

How?

If M ≡ 0 mod(p) then M^ed ≡ 0 mod(p) so M^ed ≡ M mod(p)

If M ≢ 0 mod(p) use Fermat's Little Theorem (since p∤M we know M^(p-1) ≡ 1 mod(p) ): 

ed - 1 = k φ(N) = kφ(pq) = kφ(p)φ(q) = k(p-1)(q-1)

M^ed = M^{(ed - 1)}M = M^k(p-1)(q-1)M = (M^(p-1))^k(q-1)M ≡ (1)^k(q-1)M ≡ M mod(p) 

Similiarly: M^ed ≡ M mod(q)

So: M^ed ≡ M mod(pq) = M mod(N)

Finally: C^d ≡ (M^e)^d ≡ M mod(N)