-
Notifications
You must be signed in to change notification settings - Fork 13
KeyNotes
Information on using OpenSSL properly and the general use of RSA for encryption, signing etc. is somewhat scarcely documented. This page attempts to put together some basic information learned from multiple sources. In retrospect it may seem trivial, but it look quite a while to assemble the pieces.
Public-key cryptography is essentially based on the ability to encrypt content with one key - the public key - and decrypt it with another key - the private key. The public key can only encrypt, but it cannot decrypt. Thus, it is employed by disseminating the public key which allows others to send encrypted information, but only the holder of the private key (which has to be kept safe) to decrypt it. The most commonly employed algorithm is RSA which relies on the difficulty to factor large integers. The public key consists of an exponent e and modulus n which is a factor of two large primes. The encryption of x is simply x^e mod n. The private key can only be constructed by knowing the two prime factors of n and essentially boils down to having an exponent d that inverses the encryption so with encrypted y we get y^d mod n = x.
The above works fine with encryption, but for signing we need the inverse - we want to sign with the private key but only need public key to verify. The nice thing about RSA is that it is symmetric in the sense that if you encrypt with the private key, only the public key can encrypt it - exactly what we need.
Note, however, standards (typically PKCS = Public-Key Cryptography Standards) only cover the encryption with public key and decryption with private key, not the other way around. Also signing is only covered with the private key. This is logical, but may be confusing when you are looking for APIs in both directions which don't necessarily exist (i.e. in software the symmetry typically doesn't exist).
Since RSA encryption uses integers, the payload the encrypt has to be of a certain bit length. The length of the key (more precisely modulus) defines the maximum size of the integer that can be encrypted. On the other hand, this means that the payload may have to be padded. To avoid payload attacks, secure encryption uses complicated padding schemes which means the payload is smaller than the key length - this means you have to leave space for the padding. It also means that the size of your message has to vary depending on the key size. Finally, it is expensive, so typically this is used for a small amount of data such as a symmetric key (e.g. AES key) that is used for subsequent transmission.
Anyway, OpenSSL provides two functions: RSA_public_encrypt and RSA_private_decrypt to encrypt and decrypt given set of bits. The two most useful padding schemes are RSA_PKCS1_PADDING (old from PKCS#1 v1.5 standard, 11+ bytes) and RSA_PKCS1_OAEP_PADDING (new from PKCS#1 v2.0, 41+ bytes).
The relevant standards: RFC 2313 for PKCS#1 v1.5 and RFC 2437 for PKCS#1 v2.0 (PKCS#1 = RSA Cryptography Standard)
This is where the fun starts. Let's talk about the public key first - as we said it consists of the exponent e and modulus n. How hard can it be to store two integers? Well, we'll see it can be made quite hard. You will typically see the public key in some form like this:
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANrcc/WuHzMJSFZ7Rp0ZerVYmjOrBiJB
GEj77NLdbtSZdOZ/4z8c1vbkzsfjJdxPT6ldwpqy0Z+y5DrZKyg4cJECAwEAAQ==
-----END PUBLIC KEY-----
It is the base64 encoding of the binary representation. The above is typically called "PEM". This originates in RFC 1421 which describes "Privacy Enhanced Mail" and (among other things which are not really used today) it essentially defined base64 encoding plus -----BEGIN *----- and ----END *----- boundary lines. So if you decode the above into binary you get
[0] 30 5c 30 0d 06 09 2a 86 48 86 f7 0d 01 01 01 05 00 03 4b 00 30 48 02 41 00 da dc 73 f5 ae 1f 33
[32] 09 48 56 7b 46 9d 19 7a b5 58 9a 33 ab 06 22 41 18 48 fb ec d2 dd 6e d4 99 74 e6 7f e3 3f 1c d6
[64] f6 e4 ce c7 e3 25 dc 4f 4f a9 5d c2 9a b2 d1 9f b2 e4 3a d9 2b 28 38 70 91 02 03 01 00 01
This is often called the DER format, which is in turn a canonicalized version of the ASN.1 (Abstract Syntax Notation One) format. This is turn specifies the serialization of items into binary form. It tags each item with a type (first byte above 0x30 means "SEQUENCE") and specifies its length (second byte above 0x5c means it is 92 bytes long -- above 127 it gets a little more complicated adding extra bytes). If you interpret the above, you get the following:
SEQUENCE(
SEQUENCE(
ObjectIdentifier: so(1) member-body(2) us(840) rsadsi(113549) pkcs(1) 1 1
NULL
)
BIT-STRING: SEQUENCE(
INTEGER:
INTEGER: 65537
)
)
Eureka, we see two integers, but lot of other stuff. The "ObjectIdentifier" tells us that this is rsaEncryption defined by PKCS#1 standard. The above is "Subject Public Key Info" structure from the X.509 standard which defines the format of X.509 digital certificates (See RFC 5280 for details). The second sequence is the "AlgorithmIdentifier" section which in our case identifies RSA. The integers are in fact the modulus and exponent in big-endian format. The above format is commonly referred to as "X.509 subjectPublicKeyInfo". Just the bit-string inside consisting of the sequence of two integers is known as "PKCS#1 RSAPublicKey" since it is defined in the PKCS#1 standard.
Another commonly encountered format is the one used by SSH2. You may have seen it if you use OpenSSH as ssh-rsa in the authorized_keys file or your id_rsa.pub file. That one doesn't use ASN.1 but just sequence with being a 32-bit integer in big-endian format. The first entry is just the string "ssh-rsa" second is the exponent and third is the modulus. So the above key in binary SSH2 form would be
[0] 00 00 00 07 73 73 68 2d 72 73 61 00 00 00 03 01 00 01 00 00 00 41 00 da dc 73 f5 ae 1f 33 09 48
[32] 56 7b 46 9d 19 7a b5 58 9a 33 ab 06 22 41 18 48 fb ec d2 dd 6e d4 99 74 e6 7f e3 3f 1c d6 f6 e4
[64] ce c7 e3 25 dc 4f 4f a9 5d c2 9a b2 d1 9f b2 e4 3a d9 2b 28 38 70 91
and in SSH2 PEM
---- BEGIN SSH2 PUBLIC KEY ----
AAAAB3NzaC1yc2EAAAADAQABAAAAQQDa3HP1rh8zCUhWe0adGXq1WJozqwYiQRhI
++zS3W7UmXTmf+M/HNb25M7H4yXcT0+pXcKastGfsuQ62SsoOHCR
---- END SSH2 PUBLIC KEY ----
This format is defined in RFC 4716 and the binary payload in RFC 4253, Section 6.6.
OpenSSH uses the same encoding, but instead of PEM format it consists of one line with the algorithm prepended and the user@machine appended, so:
ssh-rsa AAAAB3NzaC1yc2E...4yXcT0+pXcKastGfsuQ62SsoOHCR foo@mymachine
To recap, those are the most commonly used formats:
- PKCS#1 RSAPublicKey RFC 2313 7.1, ASN.1-DER, PEM header
BEGIN RSA PUBLIC KEY - X.509 SubjectPublicKeyInfo RFC 5280 (which just wraps RSAPublicKey), ASN.1-DER, PEM header
BEGIN PUBLIC KEY - SSH2 RFC 4716, binary , pseudo-PEM header
BEGIN SSH2 PUBLIC KEY- note that this uses 4 dashes and a space whereas PEM is 5 dashes - PGP (PEM header
BEGIN PGP PUBLIC KEY BLOCK) uses something entirely different - see OpenPGP section below
You can tell the SSH from the ASN.1 simply by the first letters in the base64 encoding -- the SSH one always starts with AAAAB3 whereas the ASN.1 always starts with M.
The same chaos also applies the private keys. If a key has only BEGIN PRIVATE KEY header then it is a wrapped version of the actual key and thus ASN.1-DER encoded with and extra outer layer defining the type of key inside. The actual RSA key will start with BEGIN RSA PRIVATE KEY and which is the ASN.1-DER encoded list of modulus, exponents etc.
If you thought the above is complicated, then you have not seen anything yet - welcome to the nightmare which is OpenPGP. It is defined in a series of RFCs (most recent is RFC9580), but unlike most other standards this one was not designed nor based on any serialization format, but rather cobbled together based on hastily created data-structures which changed in each iteration. That's why there are many "versions" of each structure which are entirely incompatible with each other so there is very limited support for those formats (probably the only readable implementation is by BouncyCastle).
The OpenPGP-based structure in DER format will start with ---BEGIN PGP blocks. For example, the public keys start with -----BEGIN PGP PUBLIC KEY BLOCK-----. PKI provides PKI.readPGP() function which attempts to parse a PGP key:
## get a PGP key
key = readLines("https://tukaani.org/misc/lasse_collin_pubkey.txt")
## parse
> str(ki <- PKI:::PKI.readPGP(key))
List of 1
$ :List of 5
..$ user.id : chr "Lasse Collin <lasse.collin@tukaani.org>"
..$ pub.key :List of 5
.. ..$ algorithm: chr "RSA"
.. ..$ public :Dotted pair list of 2
.. .. ..$ : raw [1:512] b1 83 f2 2e ...
.. .. ..$ : raw [1:3] 01 00 01
.. ..$ private : NULL
.. ..$ created : num 1.29e+09
.. ..$ user.id : chr "Lasse Collin <lasse.collin@tukaani.org>"
..$ priv.key : NULL
..$ pub.subkeys :Dotted pair list of 1
.. ..$ :List of 5
.. .. ..$ algorithm: chr "RSA"
.. .. ..$ public :Dotted pair list of 2
.. .. .. ..$ : raw [1:512] bf c5 c0 a7 ...
.. .. .. ..$ : raw [1:3] 01 00 01
.. .. ..$ private : NULL
.. .. ..$ created : num 1.29e+09
.. .. ..$ user.id : NULL
..$ priv.subkeys: NULL
RSA keys are fortunately compatible so the first entry is the modulus and the second in the exponent, thus they can be converted or used as follows:
> PKI:::PKI.mkRSApubkey(ki[[1]]$pub.key$public[[1]], k[[1]]$pub.key$public[[2]], "PEM")
[1] "-----BEGIN PUBLIC KEY-----"
[2] "MIICITANBgkqhkiG9w0BAQEFAAOCAg4AMIICCQKCAgCxg/IuXERlDB48JBWmF4Nx"
[3] "NUuuup1IhJAJyFGFSKh3OGAO2ArdsNuRLjANsFXA7m7P5eTFcG+BoHHuAVYmKnI3"
[4] "PPZtHVLnUt4pGItPczQZ2BE1WpcIayjGTBJeKItX3Npqg9D/odO9WWS1i3FQPVdr"
[5] "Ln0YH37/BA66jeMQCRo7g7GLpaNfIrvYGsqTbxCwsmA37rpE7oyU4Yrf74HT091W"
[6] "BsRIoq/MelhbxTDMR8eu/dUGZQVcKj3lN55RepwWwUUKyqarY0zMt4HkFJ7v7yRL"
[7] "+Cvzy92Ouv4Wf2FlhNtEs5LE4TaxW0PO5AEmUoKjX87SezQK0f652018b4u6Ex52"
[8] "cY7p+n5TII/UyoowH6+tY8UHo9ybfStrqgNE/mY2bhA6+AwCaOUGsFzVVPTbjtxL"
[9] "3HacUP/jlA1h78V8VTvTs5d55iG7jSqR9o05wje8rwNiXXK0xtiJahyNzL97Kn/D"
[10] "gPSqPIi45G+8nxWSPFM5eunBKRl9vAnsvwrdPRsR6YR3uMHTuVhQX9/CY891MHka"
[11] "ZJ6wydWtKt3yQwJLYqwo5d4DwnUXCduUwSKv+6RmtWI5ZmTQYOcBRcZyGKml9X9Q"
[12] "8iSbm6cnpFXmLrNQwCJN+D3SiYGcMtbltZo0ysPMa6Xj5xFaYqWk/BI4iLb2Gs+B"
[13] "yGo/+a0Eq4XYBMOpitNniQIDAQAB"
[14] "-----END PUBLIC KEY-----"
> .POSIXct(ki$pub.key$created, "GMT")
[1] "2010-10-24 13:50:10 GMT"