Asymmetric Cryptography
Unlike Symmetric crypto, where the same key is used to encipher and decipher messages. Asymmetric (or Public Key) cryptography uses different keys for encryption and decryption (or signing / verifying messages)
This addresses our main problem with Symmetric Cryptography, how do we let the right people know the shared key.
How Public Key Crypto works
Rather than the single shared key we have a pair of keys:
- The Public Key (which anyone can have)
- The Private Key (which we need to keep secret)
Encoding Data
When someone wants to send you a message, they can use your public key, to encipher it. However, once a message is enciphered only the private key can decipher the message.
Signing Messages
We can also use public keys for verifying information, for example to demonstrate the author of a file.
In this case the file is signed using the private key, and this signature can later be verified using the public key. I like to think of this like using a hashing function to check if a message has been tampered with, but the hashing function is unique to a particular user.
Authorisation
We (hopefully) use this all the time in the form of SSH keys.
Services like SSH (or GitHub) can make be made aware of a users public key. The private key is then used to authenticate with the service. As we expect only the user to have access to their own private key, this provides and excellent replacement for passwords.
Limitations of Public Keys
Public Keys are an excellent way to address the problem of key distribution. However, they do have some significant limitations.
-
The size of the message that can be encrypted is limited.
In general the message is limited by the size of the public key. This means that for RSA and a 1024 bit key, we are limited to ~117 Bytes of data (about 980 bits)
-
They are slow to encrypt and decrypt information
And they are much slower than Symmetric key algorithms. This is undesirable for the same reasons, as symmetric. An attacker will focus on getthing the key to the message, as without it it is impossible to get the plain text. Therefore, a faster encipher / deciper process improves the usablity of the algorithm
The main way these limitations are addressed is to use a hybrid encryption. Where public key cryptography is used to exchange keys for the much faster and more versatile symmetric algorithms.
Well known Public Key Algorithms
The two most well known Public Key algorithms are
Isn't this the same as Diffie Hellman
We talked about the Diffie Hellman Key exchange earlier, Public keys take a similar approach to solving the same problem, of sharing synchronous encryption keys.
- DH is about agreeing what key to use for encryption. This means that two parties can negotiate a shared secret key before starting to talk. It has the advantage that we don't need to have any prior infrastructure in place.
- With PKI we can use a known public key to tell the recipient the key that we will use in the future. Here our recipient will need to have a key pair available, for the message to be sent.
RSA
From Rivest, Shamir, Adleman. If you have ever used SSH keys, then you have probably used RSA.
RSA makes use of some mathematical properties.
Its easy to multiply two numbers together, but its hard to work out what two numbers were multiplied to get the result.
Example
Lets imagine we have been asked to discover what two numbers were multipled to make \(31\) (6 Bytes)
This example is not that hard, we keep dividing the number till we get a whole number as the result.
- \(31 / 1 == 31\)
- \(31 / 2 == 15.5\)
- \(31 / 3 == 7\)
But what about \(4757\)
- \(4757 / 3 == 1585\)
- \(4757 / 5 == 951\)
- ..... (Another 30 something attempts)
- \(4757 / 67 == 71\)
Now what about \(27788083011628481335025236747741173042866014272925140802013\) (195 Bytes)
Its \(235563344245157871525476745619 * 117964376421437564138652523727\) Which means we need to make \(58982188210718782069326261863\) Attempts using our linear approach. (Somewhere around 187,000,000,000,000) years at 1 million guesses a second.
So the larger the number we have, the harder it is to find the factors that go into it. As RSA uses key sizes of large than 2046 bytes. We hit the computationally infeasible problem
My old coursework
Yes it was some years ago, but this integer factorisation problem was set as a coursework once.
It took me about a week to find that the prime factors of \(30167 == 97 \times 311\) That's a 16 Bit number, and we were using the best factorisation algorithm of its time.
ECC
Ecliptic curve cryptography, is a more modern approach. Rather than work with large prime numbers, it uses coordinates on an flat-field curve.
ECC is popular because it is stronger for much smaller key sizes. For example a 256-Bit EEC Key, is mathematically as strong as a 3072-bit RSA Key.
ECC is commonly used for key signing, and certificate authorities, and is considered more future proof than RSA
The Technical Bit.
Important
You dont need to understand the maths behind it. But if you are interested
Practical Use of PKI
While it has some limitations (in the size of the message and speed) PKI is still heavily used.
- Key Exchange between parties
- Digital Signatures
- For authentication with systems like SSH
In the Lab we will take a look: - at securing servers using HTTPS. - Writing our own secure chat client