Ok, away from politics, and back to the good stuff. When I left off talking about

encryption, we were looking at

RSA, as an example of an asymmetric encryption system.

Since it’s been a while, I’ll start off with a quick review of RSA.

Asymmetric encryption systems like RSA are based on computations that are easy to perform if you know the keys, and incredibly hard to perform if you don’t. In the specific case

of RSA, everything is based on a pair of very large prime numbers. If you know those two

primes, and you know the public key, it’s really easy to compute the private key. But

if you *don’t* know the two prime numbers, then even given the public key,

it’s incredibly difficult to compute the private key.

To be a bit more specific, in RSA, you get a pair of large prime numbers, P and Q. You

compute from them a *totient* of their product, which is the number

N=(P-1)×(Q-1). Then you arbitrarily pick a public exponent, E, which is

smaller than N, and which is prime relative to N. You can then compute

the private key exponent, D. If you know what P and Q are, it’s pretty easy to compute

D.

Once you’ve got D and E, your public key is the pair is (N,E), and the private key is the pair is (N,D).

If you’ve got a plaintext message M, then encrypting it with the public key

is done by computing M^{E} mod N. If you’ve got a ciphertext C encrypted

with the public key, then decrypting it is done by computing C^{D} mod N.

*Encrypting* a plaintext with the public key is *exactly* the same process

as *decrypting* a ciphertext produced with the private key. And vice versa.

Continue reading →

### Like this:

Like Loading...