Public-key cryptography

Overview of public-key cryptography

Unlike symmetric key encryption where a single key is used for both encryption and decryption, public key cryptography (PKC) uses two separate keys - a public key and a private key (the latter is also called secret key).

A private key is used for decryption and signing and it must be kept secret. A public key is used for encryption and verifying signatures given with the corresponding private key. Hence, different keys are used for opposite functions: encrypting/decrypting, signing/verifying a signature. Here comes the alternative name of public key cryptography: asymmetric encryption.

Private and public keys are generated in pairs and they are linked by the underlying mathematical formula. However, a public key does not reveal information about the corresponding private key and so it cannot be misused.

Public key cryptography is based on making the public key public. It makes possible to encrypt messages meant for the key pair owner and verify if a signature is given by the corresponding private key. Hence the name public key cryptography.

The security of public key cryptosystems is based on mathematical hardness assumptions. For example, the common public key cryptosystem RSA uses the assumption that large numbers are hard to factor (if they have only a few large prime factors). Cryptosystems DSA and ElGamal are based on the fact that discrete logarithms are hard to compute in cyclic groups. Public key systems based on elliptic curves (Estonian: elliptkõverad) are based on the infeasibility of division of elliptic curves over finite fields.

Like in symmetric cryptosystems, the key length in public key cryptosystems is expressed in bits. Key length shows how hard it is for an attacker to crack the cryptography, i.e. "solve" the underlying hard problem that the cryptosystem is based on. As public key cryptography is based on hardness assumptions, the keys used here are much longer then the ones used in symmetric cryptography.

Security level in bits	RSA/DLOG	EC
48	480	96
56	640	112
64	816	128
80	1248	160
112	2432	224
128	3248	256
160	5312	320
192	7936	384
256	15424	512

Table. Key length (in bits) for obtaining a required security level when using RSA, a cryptosystem based on discreet logarithm hardness assumption (DLOG) or elliptic curves (EC). The key length for symmetric cryptosystems is equivalent to the security level. Source: ECRYPT II Yearly Report on Algorithms and Keysizes, http://www.ecrypt.eu.org/

RSA/DLOG	Security level in bits
512	50
768	62
1024	73
1536	89
2048	103

Table. The symmetric encryption key length equivalent for most used RSA and discrete logarithm (DLOG) based public key cryptosystems. Source: ECRYPT II Yearly Report on Algorithms and Keysizes, http://www.ecrypt.eu.org/

Public key cryptography is used in:

Estonian ID-card - contains two key pairs
HTTPS protocol - used in SSL / TLS e.g., for key agreement
PGP - provides end-to-end security for emails
SSH - protocol that allows to securely create a terminal connection
Bitcoin - virtual currency
DNSSEC - provides integrity for DNS

Encryption

In public key cryptography the public key is used to encrypt messages and private key is used to decrypt them. This means that encryption is targeted: everybody is able to encrypt a message as the public key is published. However, only the owner of the private key is able to decrypt these messages.

It is important to understand that public key cryptography is much more resource intensive (mainly CPU time) than symmetric cryptography. Therefore, for encrypting large messages a hybrid encryption system is used. First, a random key is generated for the symmetric encryption algorithm (e.g. AES), which is used to encrypt the message. Next, the generated symmetric encryption key is encrypted with the public key and bundled with the encrypted message. To decrypt the message, the private key is first needed to decrypt the symmetric encryption key and then the symmetric key can be used to decrypt the message.

Digital signature and hash functions

If keys are used in opposite order: private key for encryption and public key for decryption, then this is called digital signing.

As mentioned before, operations in public key cryptography, especially operations that use the private key (e.g. signing) are slow. Therefore, instead of signing the (potentially large) file, only its hash (Estonian: räsi) is signed.

Cryptographic hash functions

A hash function (Estonian: räsifunktsioon) is a deterministic algorithm that takes an arbitrary amount of data as input and produces a fixed length output. Consequently, each possible output of a hash function can be produced by an infinite number of different inputs. It is important that similar (but still different) inputs give non-similar outputs.

Source: Wikimedia

Hash functions are widely used in cryptography but a cryptographic hash function is restricted by the following requirements:

One-wayness: a hash function is a one-way function, i.e. it is not possible to learn (any possible) input from a given output.
Second pre-image resistance: Given an input value and its hash, it is hard to find any other input value that gives the same hash value.
Collision resistance: It is hard to find a pair of different input values that yield the same hash value.

Most used hash functions are MD5, SHA-1, SHA-2 family (SHA-224, SHA-256, SHA-384, SHA-512) and SHA-3 (Keccak). However, MD5 is shown not to be collision resistant which means that it should not be used anymore for security critical tasks. It is also not recommended to use SHA-1 in newer applications as a collision was found in 2017. More info about the collision can be found in:

An example: Hash values for the input sentence "cryptographic hash function is one-way":

Hash function	Output length	Hash of the sentence
MD5	128 bits	217c7df9519a23f0f0a591b582a1f5ef
SHA-1	160 bits	e9170bbca1c8085ee5d72852bde474296a506f7c
SHA-256	256 bits	ba98a1a3e0c7cca08a12039f97d224c734aa88ba84b11733c83f207927399611

These properties of cryptographic hash functions make it possible to use them for digital signatures, where hash is used as a reference to the file to be signed. When signing a document, a hash value (also called digest) is first computed from the document. This hash value is then encrypted with the private key of the signer and the result is bundled with the document. To verify a given signature, the encrypted hash value is decrypted with the public key of the signer. A new hash value (using the same hash function) is then computed from the document and compared with the decrypted hash value. If the hash values match, it means that the document has not been changed after it was signed and so the signature is valid.

Quantum computers and public key cryptography

Quantum computers could break most of todays public key cryptography. Quantum computers use quantum effects and therefore are able to solve some computational tasks much more efficiently compared to traditional computers. E.g., integer factorization is a hard problem that is not known to be efficiently solvable on traditional computers. Such factors have to exist as all natural number bigger than one can be uniquely represented either as a prime or a multiplication of primes. This is a result of the fundamental theorem of arithmetic.

An image that shows how the number 864 can be factored / decomposed into primes. Source: Wikimedia

However, quantum computers can solve the integer factorization problem efficiently by using quantum effects. The quantum algorithm for efficiently factoring integers on quantum computers is called Shor's algorithm. It could be used to break RSA cryptosystem. However, in order to break a 2048 bit RSA key one would need a quantum computer with more than ten thousand quantum bits. This number might be significantly higher depending on the required error correction codes.

The second important algorithm for quantum computers is Grover's algorithm, which improves the speed of brute force attacks. Trying all possible combinations with this algorithm reduces the number of attempts by square root of the number of all possible combinations. For example, a 128-bit AES key could be brute forced with {$ 2^{64} $} operation by running Grover's algorithm. A 64-bit key is too weak and thus NSA suggests US government institutions to use AES with 256-bit keys. Even if powerful quantum computers would appear in the near future then they would not be able to brute force 256-bit keys. By applying Grover's algorithm the security level would be reduced to 128-bits, which is still unbreakable.

It is estimated that quantum computers will become useful in 10-30 years. Therefore, it is important to start using public key algorithms that are secure even when quantum computers emerge. This problem is discussed in the following article: The Tricky Encryption That Could Stump Quantum Computers.

In the recent years companies and universities have invested a lot of resources into developing quantum computers. IBM introduced a new quantum computer in 2017, which had 50 quantum bits. In the beginning of 2018 Google introduced a quantum computer with 72 quantum bits, which is the current record. However, these computers are not yet practical due to the amount of errors that come as a side-effect. Thus, error correcting codes have to be applied in order to get correct computation results. Unfortunately, error correction takes up a lot of quantum bits. Therefore, research is being focused on reducing the amount of errors and fixing the errors with efficient error correction codes.

IBM's 50 quantum bit quantum computer (on the left) and Google's 72 quantum bit chip on the right, Sources: IBM's quantum computer ja Google's chip.

Google's estimate for the ratio of quantum bits to effective error connection codes.
Source: https://research.googleblog.com

Public key infrastructure

Some of the most common questions regarding the usage of public key cryptography are:

How do I know that the web page I'm visiting is authentic, i.e. controlled by the entity it is supposed to be controlled by?
How does a computer know whom the electronic ID (e.g. Estonian ID-card) belong to?

This describes a common problem known as the "key exchange problem". By design, public keys are supposed to be public and available for everyone. However, how can you verify that a public key (that is technically just a bunch of numbers) you found somewhere on the internet really belongs to the person/company you think it belongs to? If attacker can substitute the real public key with his own then he can decrypt all the messages encrypted with the public key.

To tie a key pair to specific person (or a company, a website), some textual information is bundled together with the public key. A public key together with the identifying information is called a certificate. The textual information on a certificate can be person/company name, contact information, validity information, usage constraints, etc. Like public keys, certificates are published. Private key is still connected with the public key in the certificate but it is not part of the certificate and kept secret.

Now we have a new problem - anybody can take his public key and create a certificate stating that he is the president of the United States. Technically, everybody could do that, but probably nobody would believe such certificates. To make a certificate trustworthy, a trusted third party must approve that certificate. For digital certificates this trusted party is called a certification authority (CA, Estonian: sertifitseerimiskeskus) and it approves a certificate (public key + information) by signing it with its private key.

Example: The general information from the web certificate of Facebook:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            0b:3c:3b:60:1a:18:f5:9e:e2:b6:bb:05:60:5e:f2:c0
    Signature Algorithm: sha256WithRSAEncryption
        Issuer: C=US, O=DigiCert Inc, OU=www.digicert.com, CN=DigiCert SHA2 High Assurance Server CA
        Validity
            Not Before: Dec 15 00:00:00 2017 GMT
            Not After : Mar 22 12:00:00 2019 GMT
        Subject: C=US, ST=California, L=Menlo Park, O=Facebook, Inc., CN=*.facebook.com
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key: (256 bit)
                pub: 
                    04:88:03:ce:c8:8e:aa:8c:e8:90:57:a6:e3:76:d0:
                    15:c2:56:c0:e3:a0:ff:70:9c:5d:ab:49:5e:b4:a8:
                    2d:77:d2:82:d3:ae:07:ce:43:75:24:d5:db:f5:47:
                    a2:c5:0b:1e:20:b3:6a:49:52:ee:a2:0c:a0:52:fd:
                    bf:81:5c:e5:1b
                ASN1 OID: prime256v1
                NIST CURVE: P-256

This means that the certification authority also has its own private key and a certificate. Moreover, this CA's certificate may be signed by one of the even more prestigious certification authorities. This yields a tree-like trust relationship structure where the root certification authorities are widely trusted parties. Their certificates are signed by themselves (self-signed certificates). This is the public key infrastructure (PKI).

Infoturve 2018/19 sügis