RSA: One crypto algorithm to rule them all

In this article we will explain why the RSA algorithm is so important in the computation world, how the digital certificates work, and we will present a several cheatsheets with the most used commands when we are integrating the Mutual TLS capability in our application.

Index

RSA Algorithm explanation
RSA Digital Certificates
RSA in TLS Handshake
OpenSSL Cheatsheet
Java Keytool Cheatsheet
cURL CheatSheet
- 6.1 Connection using custom certificates
Conclusions
References

1. RSA Algorithm explanation

TL;DR

The algorithm is based on the mathematical rule that fulfills that:

(M^e)^d (mod n) = M

Being the numbers (e,n) the public key and (d,n) the private key, and ‘M’ the message that it is wanted to cipher.

It’s extremely hard to find ‘d’ knowing only ‘e’ and ‘n’ due to it is needed the prime factorization of ‘n’ to do it.

Check the full coded version of the RSA algorithm in this link

1.1. Key pair selection

RSA algorithm is based on an asymetric key pair:

Public key: Used to encrypt the message.
Private key: Used to decrypt the message by the key’s owner.

Let’s see how to select the Key pair.

while(not found):
        primes_seed = find_primes_seed(primes) #1
        p,q = primes_seed[0],primes_seed[1] #2
        n, phi = p*q, (p-1)*(q-1) #3

        e = 17 #4
        d = modinv(e, phi) #5
        if(d != -1):
            found = True

public_key = (e,n)
private_key = (d,n)

1) Two prime numbers are selected as seed of the keypair that has to be created. In this example, the prime numbers selected are very straighforwared, but in the real world, these numbers used to has 4096 bits, which means that the numbers could have more than 1200 digits!!

2) We call P and Q to the first and second prime numbers selected respectively. This is the standard notation to label these numbers in the algorithm.

3) Here comes the magic: We calculate ‘n’, which is the multiplication of p*q. Here is where the strengh of this algorithm resides due to find the private key, we MUST know which are the original primes numbers.

The prime factorization of a number costs so much computational time. If the selected primes are big enough, the person who wanted to break the code must spend years trying it!!

In this point, we calculate also phi(n), which is basically the amount of numbers which are coprimes of n, it is, how many numbers does exist which cannot divide n. Phi(n) is calculated based on the Euler’s totient function.

4) We select ‘e’, which basically is a prime number between [3, phi(n)) which fulfills that gcd(n, phi(n)) = 1, in other words, e has to be a coprime of phi(n) and n.

We could select every prime number (in this case we selected 17), but in real life, it used to select 65537 because of computational efficiency.

The ‘e’ number will be used to encrypt the message as part of the PUBLIC key.

5) We have to calculate ‘d’, which actually is the modular multiplicative inverse between ‘e’ and ‘phi(n)‘

There are a lot of maths underneath, but the most important thing that we should know is that:

((M^e)^d) (mod n) == M

if and only if

(e*d - 1) / phi(n) == 0

So finally, when this keypair selection algorithm is ended, we’ll have obtainted:

Public key: (e, n)
Private key: (d, n)

1.2 How to encrypt a certain content?

Because we know that:

((M^e)^d) (mod n) = M

we could apply only the first step to obtain the encrypted message C:

(M^e) (mod n) = C

Here in the code:

def encrypt(num, public_key):
    return (num**public_key[0]) % public_key[1]

1.3 How to decrypt a certain content?

We have to make the final step to recover the original message,

(C^d)(mod n) = M

Here in the code:

def decrypt(num, private_key):
    return (num**private_key[0]) % private_key[1]

1.4. Why it is so powerful?

To decrypt a message is needed ‘d’ exponent, BUT, there is no algorithm to calculate this number knowing ‘e’ and ‘n’ (public key) in acceptable time, because to do that, it is needed a prime factorization of ‘n’ in order to find ‘phi(n)’.

When the numbers are sufficient large, no efficient, non-quantum integer factorization algorithm is known. E.g. To factor a 232-digit number (RSA-768) it was spent 2 years utilizing hundreds of machines.

If an attacker is able to know which primes ‘p’ and ‘q’ were used to calculate the keypairs, OR is able to know ‘phi(n)’, therefore the private key ‘d’ could be calculated in O(1).

That’s why ‘d’, ‘p’, ‘q’ and ‘phi(n)’ should be maintained in SECRET.

1.5 RSA Practical example

Let’s select:

p: 97, q: 149
n: 97 * 149 = 14453
phi(n): (97-1)*(149-1) = 14208
e: 17
d: 10865

So:

Public key: (17, 14453)
Private key (10865, 14453)

Imagine that we’d like to encrypt “hello”, let’s encrypt every letter based on ASCII decimal:

“h” = 104
“e” = 101
“l” = 108
“l” = 108
“o” = 111

Encrypted “hello” would be:

C = M^e (mod n)

enc(“h”) = (104^17)(mod 14453) = 4423
enc(“e”) = (101^17)(mod 14453) = 13041
enc(“l”) = (108^17)(mod 14453) = 288
enc(“l”) = (108^17)(mod 14453) = 288
enc(“o”) = (111^17)(mod 14453) = 5039

Therefore, decrypted “hello” would be:

M = C^d (mod n)

dec(4423) = (4423^10865)(mod 14453) = 104 = “h“
dec(13041) = (13041^10865)(mod 14453) = 101 = “e“
dec(288) = (288^10865)(mod 14453) = 108 = “l“
dec(288) = (288^10865)(mod 14453) = 108 = “l“
dec(5039) = (5039^10865)(mod 14453) = 111 = “o“

2. RSA Digital Certificates

RSA algorithm is very important in the digital world as it is the most used method to authenticate and start encrypting communications based on the TLS protocol.

As you know, to encrypt communications between client / server, it is needed the certificates exchange.

To take a look how RSA digital certificates look like, we’re going to use:

OpenSSL: https://www.openssl.org/
ASN.1 Decoder: https://lapo.it/asn1js

2.1 Analyzing RSA Private Key.

First of all, let’s create a RSA Private Key using OpenSSL. In this case, let’s create a RSA Private Key using 1024 bits

$> openssl genrsa -out rsa.key 1024

Resulting the following file rsa.key

Now it’s time to check what this private key looks like in a more human friendly way using ASN.1 Decoder (https://lapo.it/asn1js).

SEQUENCE (9 elem)
  INTEGER 0
  INTEGER (1024 bit) 163005934720504414138835979861898900656555855760833305296400822626213…
  INTEGER 65537
  INTEGER (1024 bit) 954998835700213236076528721604203761174469175853785737851992917825973…
  INTEGER (512 bit) 1303102248512034216730640610384961639077703105041109437820613357952095…
  INTEGER (512 bit) 1250906710556558800169785331519483073262727639645891698605880451926999…
  INTEGER (512 bit) 6892004537577876622414432280568768838016898092212785958121076676279891…
  INTEGER (511 bit) 4838562203428409232083259556284067916933967936436418291905193929589307…
  INTEGER (511 bit) 6487917541152510302611720310690390868652810741187961499695627937822275…

which correspond to the following elements:

version           Version,
modulus           INTEGER,  -- n
publicExponent    INTEGER,  -- e
privateExponent   INTEGER,  -- d
prime1            INTEGER,  -- p
prime2            INTEGER,  -- q
exponent1         INTEGER,  -- d mod (p-1)
exponent2         INTEGER,  -- d mod (q-1)
coefficient       INTEGER,  -- (inverse of q) mod p

As you could check, those are the same ingredients that we managed in the previous section to explain what is and how the RSA algorithm works. And that’s explained why the key MUST be private: it contains the prime numbers used to generated the certificate!

2.2 Analyzing RSA Public Certificate.

Now, let’s create a public certificate using the previous private key.

$> openssl req -key rsa.key -new -x509 -days 365 -out rsa.crt

If we open the recent public certificate created, we could check that looks like very similar than the private key.

Finally, let’s check the content using ASN.1 Decoder (https://lapo.it/asn1js)

SEQUENCE (3 elem)
  SEQUENCE (8 elem)
    [0] (1 elem)
      INTEGER 2
    INTEGER (64 bit) 11118579931001561117
    SEQUENCE (2 elem)
      OBJECT IDENTIFIER 1.2.840.113549.1.1.11 sha256WithRSAEncryption (PKCS #1)
      NULL
    SEQUENCE (3 elem)
      SET (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.4.6 countryName (X.520 DN component)
          PrintableString AU
      SET (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.4.8 stateOrProvinceName (X.520 DN component)
          UTF8String Some-State
      SET (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.4.10 organizationName (X.520 DN component)
          UTF8String Internet Widgits Pty Ltd
    SEQUENCE (2 elem)
      UTCTime 2018-11-17 08:53:02 UTC
      UTCTime 2019-11-17 08:53:02 UTC
    SEQUENCE (3 elem)
      SET (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.4.6 countryName (X.520 DN component)
          PrintableString AU
      SET (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.4.8 stateOrProvinceName (X.520 DN component)
          UTF8String Some-State
      SET (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.4.10 organizationName (X.520 DN component)
          UTF8String Internet Widgits Pty Ltd
    SEQUENCE (2 elem)
      SEQUENCE (2 elem)
        OBJECT IDENTIFIER 1.2.840.113549.1.1.1 rsaEncryption (PKCS #1)
        NULL
      BIT STRING (1 elem)
        SEQUENCE (2 elem)
          INTEGER (1024 bit) 163005934720504414138835979861898900656555855760833305296400822626213…
          INTEGER 65537
    [3] (1 elem)
      SEQUENCE (3 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.29.14 subjectKeyIdentifier (X.509 extension)
          OCTET STRING (1 elem)
            OCTET STRING (20 byte) DE4579354C54970464CBDAA8E8FE03C67999C5D3
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.29.35 authorityKeyIdentifier (X.509 extension)
          OCTET STRING (1 elem)
            SEQUENCE (1 elem)
              [0] (20 byte) DE4579354C54970464CBDAA8E8FE03C67999C5D3
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.5.29.19 basicConstraints (X.509 extension)
          OCTET STRING (1 elem)
            SEQUENCE (1 elem)
              BOOLEAN true
  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.11 sha256WithRSAEncryption (PKCS #1)
    NULL
  BIT STRING (1024 bit) 101010000000110010000110010011011101001110101010011010110101000101100…

Pretty more extense than the private key, isn’t? :)

This is because the public certificates are used to follow the x.509 standard for its structure. The important thing we have to look for is the SEQUENCE about ‘rsaEncryption’ information, which basically is the public key.

SEQUENCE (2 elem)
      SEQUENCE (2 elem)
        OBJECT IDENTIFIER 1.2.840.113549.1.1.1 rsaEncryption (PKCS #1)
        NULL
      BIT STRING (1 elem)
        SEQUENCE (2 elem)
          INTEGER (1024 bit) 163005934720504414138835979861898900656555855760833305296400822626213…
          INTEGER 65537

which correspond to the following elements:

modulus           INTEGER,  -- n
publicExponent    INTEGER,  -- e

Notice that those numbers are exactly the ‘e’ and ‘n’ numbers which are kept in the private key.

2.3 Common RSA files extensions: Key, CSR, CRT

Depending what was the purpose of the RSA file created, the extesion could change between following:

Files .key

Contains the RSA private key based on a certain encoding (PEM or DER).
Normally, the RSA private key is encrypted using certain symmetric algorithms such as AES256 or 3DES.

Files .csr

CSR stands for “Certificate Signing Request”.
Created by the entity that wants to obtain a valid certificated signed by a valid CA.
These files could be created using PEM or DER encoding.

Files .crt

Contains the x509 Certificate signed by a valid CA.
- RSA Public key is kept inside.
These files could be created using PEM or DER encoding.

2.4 Common RSA files encodings: PEM, DER

Encoding PEM

This encoding standard is based on ASCII (Base64). It starts its content with the prefix:

-----BEGIN

Encoding DER

This encoding standard is based on a binary format.

2.5 Common RSA containers: P7B, PFX, P12

Files .p7b

This format file means that one or more PEM certificates are stored in this file.
The p7b file contains a certificate and its certificate chain, but does NOT contain the private key.

Files .pfx / .p12

Both PFX and P12 are binary formates to store the certificate (including its certificate chain) with its private key.

3. RSA in TLS Handshake

TLS (Transport Layer Security), as you probably know, is the used protocol to provide secured communications through a network, commonly in the Internet.

When a certain client requires a secured connection to a certain server, it is performed several steps that belong to what we call TLS Handshake.

During this handshake, both client and server agree in which Cipher Suite is going to be used. If you’d like to check which are the supported cipher suites in your browser, take a look to this website (https://cc.dcsec.uni-hannover.de/)

A Cipher Suite name looks like this:

TLS_ECDHE_RSA_AES128_GCM_SHA256

TLS: Indicates the protocol.
ECDHE: Indicates the Key-exchange algorithm
RSA: Indicates the Authentication algorithm
AES128_GCM: Indicates the Bulk encryption algorithm
SHA256: Indicates the MAC algorithm.

As you could check, in this case RSA is only used as the authentication algorithm. But, what does it mean?

Well, you have to know that TLS protocol uses an hybrid cryptosystem to handle secure connections:

Asymmetric-key cryptosystem used to authenticate and generate the shared-secret key.
Symmetric-key cryptosystem used to exchange encrypted large amount of data.

This means that, most of the times, RSA is only used to send the shared-secret key between client and server in a secure way. But, once both have this shared-secret, the data will be encrypted using this secret; in this case ECDHE algorithm (Elliptic-curve Diffie–Hellman).

Therefore, the encrypted application data is NOT encrypted using asymmetric cryptography system, but symmetric one. The main reasons are:

Size of the encrypted message: Symmetric encryption does not increase the size of the message. Asymmetric encryption does. When data is exchange in a network, it is mandatory to send as small message as possible.
Performance: On a moderm CPU, the encryption/decryption using AES (symmetric) is over 2000MB/second (per core); while decryption of a 1024-bit message using RSA (asymmetric) is just 0.4MB/second.

4. OpenSSL Cheatsheet

4.1 Working with RSA private keys

Generate an private key:

$> openssl genrsa -out example.key [bits]

Generate an AES256 encrypted private key:

$> openssl genrsa -aes256 -out example.key [bits]

Generate an 3DES encrypted private key:

$> openssl genrsa -des3 -out example.key [bits]

Encrypt an existant private key with AES256:

$> openssl rsa -aes256 -in example.key -out example_with_pass.key

Encrypt an existant private key with 3DES:

$> openssl rsa -des3 -in example.key -out example_with_pass.key

Remove encryption from the private key:

$> openssl rsa -in example.key -out example.key

4.2 Working with CSR requests

Create a CSR from existing private key:

$> openssl req -new -key example.key -out example.csr

Create a CSR from existing certificate and private key:

$> openssl x509 -x509toreq -in cert.pem -out example.csr -signkey example.key

Create a CSR and a private key (single command):

$> openssl req -nodes -newkey rsa:[bits] -keyout example.key -out example.csr

4.3 Working with x509 certificates

Create a self-signed certificate and a private key (single command):

$> openssl req -nodes -newkey rsa:[bits] -keyout example.key -out example.crt -x509 -days 365

Create a self-signed certificate using existint CSR and private key:

$> openssl x509 -req -in example.csr -signkey example.key -out example.crt -days 365

Sign a certificate:

$> openssl x509 -req -in example.csr -days 365 -CA ca.crt -CAkey ca.key -set_serial 01 -out example.crt

Print textual representation of the certificate:

$> openssl x509 -in example.crt -text -noout

Print certificate’s fingerprint:

$> openssl x509 -in cert.pem -fingerprint -sha256 -noout

Verify a certificate:

$> openssl verify example.crt

Verify a certificate providing intermediate cert chain:

$> openssl verify -untrusted intermediate-ca-chain.pem example.crt

Verify a certificate providing root and intermediate cer chain:

$> openssl verify -CAFile root.crt -untrusted intermediate-ca-chain.pem child.crt

4.4 Encoding convertions

From PEM to DER:

$> openssl x509 -in example.pem -outform der -out example.der

From DER to PEM:

$> openssl x509 -in example.der -inform der -out example.pem

4.5 Container format convertions

From certs to P7B:

$> openssl crl2pkcs7 -nocrl -certfile example.crt -certfile ca.crt -out example.p7b

From P7B to certs:

$> openssl pkcs7 -in example.p7b -print_certs -out example.crt

From certs with key to P12:

$> openssl pkcs12 -export -out certificate.pfx -inkey privkey.pem -in certificate.pem -certfile ca-chain.pem

From P12 to certs:

$> openssl pkcs12 -in keystore.pfx -out keystore.pem -nodes

4.6 Connection using custom certificates

Connection sending client certificate

$> openssl s_client -cert client.crt -key client.key -pass [key passphrase] -connect example.com:443

Connection sending client certificate informing about encoding

$> openssl s_client -cert client.crt -certform PEM -key client.key -keyform PEM -pass [key passphrase] -connect example.com:443

Connection sending client certificate and CA certificate chain

$> openssl s_client -CAfile ca.crt -cert client.crt -key client.key -pass [key passphrase] -connect example.com:443

Connection sending client certificate and CA certificate chain informing about encoding

$> openssl s_client -CAfile ca.crt -cert client.crt -certform PEM -key client.key -keyform PEM -pass [key passphrase] -connect example.com:443

5. Java Keytool Cheatsheet

5.1 Creation and generation

Generate a Java keystore and key pair

$> keytool -genkey -alias [alias] -keyalg RSA -keystore keystore.jks -keysize [bits]

Generate a CSR for an existing Java keystore

$> keytool -certreq -alias mydomain -keystore keystore.jks -file mydomain.csr

Generate a Java keystore and self-signed certificate

$> keytool -genkey -keyalg RSA -alias [alias] -keystore keystore.jks -storepass password -validity 360 -keysize [bits]

5.2 Import and export

Import a root or intermediate CA certificate to an existing Java Keystore

$> keytool -import -trustcacerts -alias root -file root.crt -keystore keystore.jks

Import a signed primary certificate to an existing Java keystore

$> keytool -import -trustcacerts -alias [alias] -file mydomain.crt -keystore keystore.jks

Export a certificate from a Java keystore

$> keytool -export -alias [alias] -file mydomain.crt -keystore keystore.jks

5.3 Check and list

Check a certificate

$> keytool -printcert -v -file mydomain.crt

Check a particular certificate using an alias

$> keytool -list -v -keystore keystore.jks -alias [alias]

List the certificates in a Java keystore in a human-readable format

$> keytool -list -v -keystore keystore.jks

List the certificates in a Java keystore in a PEM format

$> keytool -list -rfc -keystore keystore.jks

5.4 Delete

Delete a certificate from a Java keystore

$> keytool -delete -alias [alias] -keystore keystore.jks

5.5 Passwords

Change a Java keystore password

$> keytool -storepasswd -new new_storepass -keystore keystore.jks

6. cURL Cheatsheet

6.1 Connection using custom certificates

Connection sending client certificate

$> curl -kv --cert client.crt --key client.key --pass [key passphrase] https://example.com

Connection sending client certificate informing about encoding

$> curl -kv --cert client.crt --cert-type PEM --key client.key --pass [key passphrase] https://example.com

Connection sending client certificate and CA certificate chain

$> curl -kv -cacert ca.crt --cert client.crt --key client.key --pass [key passphrase] https://example.com

Connection sending client certificate and CA certificate chain informing about encoding

$> curl -kv -cacert ca.crt --cert client.crt --cert-type PEM --key client.key --pass [key passphrase] https://example.com

7. Conclusions

In this article we’ve seen how RSA algorithm works, its importance in the digital world, and we collected several cheatsheet that may be useful when we were working with secured connections.

8. References

rsa cryptography tls openssl keytool jks x509 curl