Secure communications (1)

I've been interested in cryptography and the whole question of secure communication over an insecure network, but never had the time to get into it.

I thought we could take a crack at it here. :)

The place to start is public key cryptography. I found a nice (though old) series at O'Reilly on ssh, which includes a very basic description of the cryptography part in the middle of the first article (link / printable). It's written to show Mac users how to use ssh (sorry). There is also a nice and much more extensive article at wikipedia.

As described in the wikipedia article on RSA (an algorithm for public key encryption), there are the following steps:

- choose two distinct large prime numbers p and q about the same size - compute n = pq - compute φ(n) = (p-1)(q-1) - choose e, the public key exponent, e.g. 0x10001 = 65537 - the private key exponent, d, is computed from e and φ(n) - the public key is then (n,e) - the private key is d

The computation to obtain d is described here.

Naturally, the private key is kept secret, while the public key is published.

The important thing is that the encryption and decryption methods have the property that decryption with the private key is the inverse of encryption with the public key:

ciphertext = public key encryption (plaintext)
plaintext = private key decryption (ciphertext)

Even better, the converse is also true:

ciphertext = private key encryption (plaintext)
plaintext = public key decryption (ciphertext)

Thus, Alice can use Bob's public key to encrypt a message that only Bob can decrypt. Bob's problem is that anyone can do this and claim to be Alice, since the encryption used only his public key.

Authentication, or signing, of messages relies on hash functions (like md5). The value computed by md5 from a message (sometimes called a fingerprint) is sensitive to small changes in the message, and also it is "impossible" to fashion a message to match a given hash.

Alice then adopts a modified strategy:

Alice encrypts a message for Bob using his public key Alice uses md5 to compute a hash of the message Alice encrypts the hash using her private key Bob reverses the operations

Only Bob can read the message. He authenticates Alice as the sender because he can decode the hash using her public key and see that it matches what md5 gives him from the message.

The version I've seen of this protocol uses the encrypted version of the message to generate the hash. But I'm not really sure whether you do md5 on the plaintext of the message or the encrypted version, and can't see that it makes a difference as far as Bob is concerned. However, I've also read that an attacker having both plaintext and ciphertext for some message is a weakness, so I think it's better if the hash is of the plaintext for the original message, to protect Alice's private key.

Eve (an evesdropper) cannot read the message, lacking Bob's private key. She cannot substitute a different message of her own, because the hash won't match. She cannot substitute both a different message and a hash, because then when Bob decrypts the hash using Alice's public key, it doesn't match the hash from Eve's message.

There are two more issues to think about right away. The first is that this process is really expensive computationally. So usually, public key cryptography is used to exchange a secret key that is then used for a block or stream cipher.

The second is the question of the validity of public keys. That's the whole purpose of digitally signed certificates (wikipedia).

If you look in the Keychain under Certificates > System Roots, you'll see a (frighteningly long---163 items for me) list of Certificate Authorities whose public key we trust implicitly, and who in turn guarantee say, Bank of America, when you get a logon page for online banking.

But, I'm not so interested in banking. I'm interested in ssh and virtual private networks, and Kerberos.. all sorts of things.

If you know something about this subject (actually the subject of any post) and see an error, or have something to add, feel free to comment.