Redshift Academy

Public Key Encryption
---------------------

Public Key Infrastructure (PKI) is the cornerstone of information security technology for the internet. Public key cryptography was invented in 1976 by Whitfield Diffie and Martin Hellman.

ASYMMETRIC KEY ALGORITHMS

Asymmetric key algorithms use public (available to everyone) and private (only you have access to) key pairs. The two keys work together, so a message encrypted with the private key can only be decrypted with the public key and vice versa. This is illustrated in the following diagram.

This is all well and good but how do you know that the public key returned is genuine and not a fake? Enter the Certificate Authority (CA). The CA is a trusted third party organization that is responsible for verifying that a given site is genuine. Once a CA has verified a site it will issue a certificate that contains information about the owner of the site, for example e-mail address, owner's name, certificate usage, duration of validity, resource location or Distinguished Name (DN) which includes the Common Name (CN) (web site address or e-mail address depending of the usage) and the certificate ID of the person who certifies (signs) this information. It also contains the public key and finally a hash to ensure that the certificate has not been tampered with. The public key is encrypted using the CA's private root key. The CA includes both the unencrypted and encrypted versions of public key in the result. The browser then decrypts and checks the signature included with that public key. So how does it do that? All browsers securely maintain a predefined set of public keys on a local machine for each of the official CAs. When the browser establishes a new https:// connection it validates the signature on the public key it gets from the site using the public root key contained in one of those trusted root certificates in its store. Root certificates are generally managed securely by the OS to ensure that only official and trusted root certificates are made available on the local machine. Root certificates are updated from time to time as CAs update their own certificates, or CAs are added to or removed from the list. An example certificate is shown below:

Version: 3 (0x2)
Serial Number: 1 (0x1)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=FJ,ST=Fiji,L=Suva,O=SOPAC,OU=ICT,CN=SOPAC Root CA/Email=admin@sopac.org
Validity Not Before: Nov 20 05:47:44 2001 GMT
Not After : Nov 20 05:47:44 2002 GMT
Subject: C=FJ,ST=Fiji,L=Suva,O=SOPAC,OU=ICT,CN=www.sopac.org/Email=admin@sopac.org
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit):
00:ba:54:2c:ab:88:74:aa:6b:35:a5:a9:c1:d0:5a:
9b:fb:6b:b5:71:bc:ef:d3:ab:15:cc:5b:75:73:36:
b8:01:d1:59:3f:c1:88:c0:33:91:04:f1:bf:1a:b4:
7a:c8:39:c2:89:1f:87:0f:91:19:81:09:46:0c:86:
08:d8:75:c4:6f:5a:98:4a:f9:f8:f7:38:24:fc:bd:
94:24:37:ab:f1:1c:d8:91:ee:fb:1b:9f:88:ba:25:
da:f6:21:7f:04:32:35:17:3d:36:1c:fb:b7:32:9e:
42:af:77:b6:25:1c:59:69:af:be:00:a1:f8:b0:1a:
6c:14:e2:ae:62:e7:6b:30:e9
Exponent: 65537 (0x10001)
X509v3 extensions:
X509v3 Basic Constraints:
CA:FALSE
Netscape Comment:
OpenSSL Generated Certificate
X509v3 Subject Key Identifier:
FE:04:46:ED:A0:15:BE:C1:4B:59:03:F8:2D:0D:ED:2A:E0:ED:F9:2F
X509v3 Authority Key Identifier:
keyid:E6:12:7C:3D:A1:02:E5:BA:1F:DA:9E:37:BE:E3:45:3E:9B:AE:E5:A6
DirName:/C=FJ/ST=Fiji/L=Suva/O=SOPAC/OU=ICT/CN=SOPAC Root CA/Email=admin@sopac.org
serial:00
Signature Algorithm: md5WithRSAEncryption
34:8d:fb:65:0b:85:5b:e2:44:09:f0:55:31:3b:29:2b:f4:fd:
aa:5f:db:b8:11:1a:c6:ab:33:67:59:c1:04:de:34:df:08:57:
2e:c6:60:dc:f7:d4:e2:f1:73:97:57:23:50:02:63:fc:78:96:
34:b3:ca:c4:1b:c5:4c:c8:16:69:bb:9c:4a:7e:00:19:48:62:
e2:51:ab:3a:fa:fd:88:cd:e0:9d:ef:67:50:da:fe:4b:13:c5:
0c:8c:fc:ad:6e:b5:ee:40:e3:fd:34:10:9f:ad:34:bd:db:06:
ed:09:3d:f2:a6:81:22:63:16:dc:ae:33:0c:70:fd:0a:6c:af:
bc:5a
-----BEGIN CERTIFICATE-----
MIIDoTCCAwqgAwIBAgIBATANBgkqhkiG9w0BAQQFADCBiTELMAkGA1UEBhMCRkox
DTALBgNVBAgTBEZpamkxDTALBgNVBAcTBFN1dmExDjAMBgNVBAoTBVNPUEFDMQww
CgYDVQQLEwNJQ1QxFjAUBgNVBAMTDVNPUEFDIFJvb3QgQ0ExJjAkBgkqhkiG9w0B
CQEWF2FkbWluaXN0cmF0b3JAc29wYWMub3JnMB4XDTAxMTEyMDA1NDc0NFoXDTAy
MTEyMDA1NDc0NFowgYkxCzAJBgNVBAYTAkZKMQ0wCwYDVQQIEwRGaWppMQ0wCwYD
VQQHEwRTdXZhMQ4wDAYDVQQKEwVTT1BBQzEMMAoGA1UECxMDSUNUMRYwFAYDVQQD
Ew13d3cuc29wYWMub3JnMSYwJAYJKoZIhvcNAQkBFhdhZG1pbmlzdHJhdG9yQHNv
cGFjLm9yZzCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEAulQsq4h0qms1panB
0Fqb+2u1cbzv06sVzFt1cza4AdFZP8GIwDORBPG/GrR6yDnCiR+HD5EZgQlGDIYI
2HXEb1qYSvn49zgk/L2UJDer8RzYke77G5+IuiXa9iF/BDI1Fz02HPu3Mp5Cr3e2
JRxZaa++AKH4sBpsFOKuYudrMOkCAwEAAaOCARUwggERMAkGA1UdEwQCMAAwLAYJ
YIZIAYb4QgENBB8WHU9wZW5TU0wgR2VuZXJhdGVkIENlcnRpZmljYXRlMB0GA1Ud
DgQWBBT+BEbtoBW+wUtZA/gtDe0q4O35LzCBtgYDVR0jBIGuMIGrgBTmEnw9oQLl
uh/anje+40U+m67lpqGBj6SBjDCBiTELMAkGA1UEBhMCRkoxDTALBgNVBAgTBEZp
amkxDTALBgNVBAcTBFN1dmExDjAMBgNVBAoTBVNPUEFDMQwwCgYDVQQLEwNJQ1Qx
FjAUBgNVBAMTDVNPUEFDIFJvb3QgQ0ExJjAkBgkqhkiG9w0BCQEWF2FkbWluaXN0
cmF0b3JAc29wYWMub3JnggEAMA0GCSqGSIb3DQEBBAUAA4GBADSN+2ULhVviRAnw
VTE7KSv0/apf27gRGsarM2dZwQTeNN8IVy7GYNz31OLxc5dXI1ACY/x4ljSzysQb
xUzIFmm7nEp+ABlIYuJRqzr6/YjN4J3vZ1Da/ksTxQyM/K1ute5A4/00EJ+tNL3b
Bu0JPfKmgSJjFtyuMwxw/Qpsr7xa
-----END CERTIFICATE-----

Note: The certificate does not contain the private key as it should never be transmitted in any form whatsoever.

Summarizing:

A browser requests a secure page (https://).
The web server sends a certificate containing the server's public key that has been encrypted with the CAs private key.
The browser refers to its root certificate store to check that the certificate was issued by a trusted party. If the certificate is valid, the CAs public key is used to decrypt the certificate and obtain the server's public key.

From that point on:

The web server uses its private key to encrypt messages to the client.
The client uses the server's public key to:

1. Decrypt messages from the server.
2. Encrypt messages to the server.

SYMMETRIC KEY ALGORITHMS

With symmetric key encryption both parties share the same key for en- and decryption. Symmetric key encryption does not consume as much computing power as asymmetric encryption power but is potentially highly insecure. Generally symmetric keys are chosen randomly so that if a key is discovered then the next transaction will be totally different. In many applications, a combination of both asymmetric and symmetric keys are being used. The asymmetric keys are used for authentication and after this has been successfully done, one or more symmetric keys are generated and exchanged using the asymmetric encryption. This way the advantages of both algorithms can be used. The flow is: Symetric Key-->[Public Key]-->Encrypted Symetric Key-->[Private Key]-->Symetric Key. The browser creates a random session key, which is encrypted with the server's public key and then sends it to the server. The server then decrypts this information using its private key. Both the browser and the server now are using the same session key. This is a symmetric key used to encrypt and decrypt data exchanged by the browser and server. Browsers and servers usually negotiate the strongest mutually supported session. This means that if the user's browser and your Web server both support 128-bit SSL sessions, a 128-bit session is established. If the user's browser only supports 40-bit SSL sessions, then a 40-bit session is established even if your Web server supports 128-bit sessions.

DIGITAL SIGNATURES

To sign a message, you create its hash, and then encrypt the hash with your private key, you then add the encrypted hash and your signed certificate with the message. The recipient will recreate the message hash, decrypt the encrypted hash using your public key stored in your signed certificate, check that both hash are equals and finally check the certificate. The digital signature for a message is generated in two steps:

A "message digest" is created by taking a mathematical hash of the message. The hash is a calculated number that is much smaller than the original message
The message digest is encrypted using the sender's private key.

The digital signature is attached to the message, and sent to the receiver. The receiver then does the following: Using the sender's public key, it decrypts the digital signature to obtain the message digest generated by the sender. The receiver then uses the same message digest algorithm used by the sender to generate a message digest of the received message. Both message digests (the one sent by the sender as a digital signature, and the one generated by the receiver) are then compared. If they are not exactly the same, the message has been tampered with by a third party. We can be sure that the digital signature was sent by the sender (and not by a malicious user) because only the sender's public key can decrypt the digital signature. If decrypting using the public key renders a faulty message digest, this means that either the message or the message digest are not exactly what the sender sent.

Using public-key cryptography in this manner ensures integrity, because we have a way of knowing if the message we received is exactly what was sent by the sender. However, notice how the above example guarantees only integrity. The message itself is sent unencrypted. This is not necessarily a bad thing: in some cases we might not be interested in keeping the data private, we simply want to make sure it isn't tampered with. To add privacy to this conversation, we would simply need to encrypt the message as explained in the first diagram. The digital signature process is summarized in the following diagram: