Books / Practical Cryptography for Developers (Unfinished) / Chapter 6b

The RSA Cryptosystem - Concepts

The RSA cryptosystem is one of the first public-key cryptosystems, based on the math of the modular exponentiations and the computational difficulty of the RSA problem and the closely related integer factorization problem (IFP). The RSA algorithm is named after the initial letters of its authors (Rivest–Shamir–Adleman) and is widely used in the early ages of computer cryptography.

Later, when ECC cryptography evolved, the ECC slowly became dominant in the asymmetric cryptosystems, because of its higher security and shorter key lengths than RSA.

The RSA algorithm provides:

Key-pair generation: generate random private key (typically of size 1024-4096 bits) and corresponding public key.
Encryption: encrypt a secret message (integer in the range [0…key_length]) using the public key and decrypt it back using the secret key.
Digital signatures: sign messages (using the private key) and verify message signature (using the public key).
Key exchange: securely transport a secret key, used for encrypted communication later.

RSA can work with keys of different keys of length: 1024, 2048, 3072, 4096, 8129, 16384 or even more bits. Key length of 3072-bits and above are considered secure. Longer keys provide higher security but consume more computing time, so there is a tradeoff between security and speed. Very long RSA keys (e.g. 50000 bits or 65536 bits) may be too slow for practical use, e.g. key generation may take from several minutes to several hours.

RSA Key Generation

Generating an RSA public + private key pair involves the following:

Using some non-trivial math computations from the number theory, find three very large integers e, d and n, such that:

(me)d ≡ m (mod n) for all m in the range [0…n)

The integer number n is called “modulus” and it defines the RSA key length. It is typically very large prime number (e.g. 2048 bits).

The pair {n, e} is the public key. It is designed to be shared with everyone. The number e is called “public key exponent”. It is usually 65537 (0x010001).

The pair {n, d} is the private key. It is designed to be kept in secret. It is practically infeasible to calculate the private key from the public key {n, e}. The number d is called “private key exponent” (the secret exponent).

RSA Public Key - Example

Example of 2048-bit RSA public key (represented as 2048-bit hexadecimal integer modulus n and 24-bit public exponent e):

n = 0xa709e2f84ac0e21eb0caa018cf7f697f774e96f8115fc2359e9cf60b1dd8d4048d974cdf8422bef6be3c162b04b916f7ea2133f0e3e4e0eee164859bd9c1e0ef0357c142f4f633b4add4aab86c8f8895cd33fbf4e024d9a3ad6be6267570b4a72d2c34354e0139e74ada665a16a2611490debb8e131a6cffc7ef25e74240803dd71a4fcd953c988111b0aa9bbc4c57024fc5e8c4462ad9049c7f1abed859c63455fa6d58b5cc34a3d3206ff74b9e96c336dbacf0cdd18ed0c66796ce00ab07f36b24cbe3342523fd8215a8e77f89e86a08db911f237459388dee642dae7cb2644a03e71ed5c6fa5077cf4090fafa556048b536b879a88f628698f0c7b420c4b7
e = 0x010001

The same RSA public key, encoded in the traditional for RSA format PKCS#8 PEM ASN.1 looks like this:

The above PEM ASN.1-encoded message, holding the RSA public key, can be decoded here: https://lapo.it/asn1js.

RSA Private Key - Example

Example of 2048-bit RSA private key, corresponding to the above given public key (represented as hexadecimal 2048-bit integer modulus n and 2048-bit secret exponent d):

n = 0xa709e2f84ac0e21eb0caa018cf7f697f774e96f8115fc2359e9cf60b1dd8d4048d974cdf8422bef6be3c162b04b916f7ea2133f0e3e4e0eee164859bd9c1e0ef0357c142f4f633b4add4aab86c8f8895cd33fbf4e024d9a3ad6be6267570b4a72d2c34354e0139e74ada665a16a2611490debb8e131a6cffc7ef25e74240803dd71a4fcd953c988111b0aa9bbc4c57024fc5e8c4462ad9049c7f1abed859c63455fa6d58b5cc34a3d3206ff74b9e96c336dbacf0cdd18ed0c66796ce00ab07f36b24cbe3342523fd8215a8e77f89e86a08db911f237459388dee642dae7cb2644a03e71ed5c6fa5077cf4090fafa556048b536b879a88f628698f0c7b420c4b7
d = 0x10f22727e552e2c86ba06d7ed6de28326eef76d0128327cd64c5566368fdc1a9f740ad8dd221419a5550fc8c14b33fa9f058b9fa4044775aaf5c66a999a7da4d4fdb8141c25ee5294ea6a54331d045f25c9a5f7f47960acbae20fa27ab5669c80eaf235a1d0b1c22b8d750a191c0f0c9b3561aaa4934847101343920d84f24334d3af05fede0e355911c7db8b8de3bf435907c855c3d7eeede4f148df830b43dd360b43692239ac10e566f138fb4b30fb1af0603cfcf0cd8adf4349a0d0b93bf89804e7c2e24ca7615e51af66dccfdb71a1204e2107abbee4259f2cac917fafe3b029baf13c4dde7923c47ee3fec248390203a384b9eb773c154540c5196bce1

The same RSA private key, encoded in the traditional for RSA format PKCS#8 PEM ASN.1 looks a bit longer:

It holds the entire RSA key-pair structure, along with several additional parameters: 2048-bit modulus n, 24-bit public exponent e, 2048-bit secret exponent d, first factor p, second factor q, and 3 other integers from the RSA internal data structure:

The above PEM ASN.1-encoded message, holding the RSA private key data, can be decoded here: https://lapo.it/asn1js.

RSA Cryptography: Encrypt a Message

Encrypting a message using certain RSA public key {n, e} is done by the following transformation:

encryptedMsg = (msg)e mod n

The msg here is a number in the range [0…n). Text messages should be encoded as integers in the range [0…n) before encryption (see EAOP). For larger texts, hybrid encryption should be used (encrypt a secret key and use it to symmetrically encrypt the text, see RSA-KEM).

The above operation cannot be reversed: no efficient algorithm exists to calculate msg from encryptedMsg, e and n (see the RSA problem), which all are public (non-secret) by design.

RSA Cryptography: Decrypt a Message

Decrypting the encrypted message using the corresponding RSA private key {n, d} is done by the following transformation:

decryptedMsg = (encryptedMsg)d mod n

Why this is correct? Recall, that by definition the RSA key-pair has the following property:

(me)d ≡ m (mod n) for any m in the range [0…n)

From the encryption transformation we have:

encryptedMsg = (msg)e mod n

Hence:

decryptedMsg = (encryptedMsg)d mod n = ((msg)e mod n)d = ((msg)e)d mod n = (msg) mod n = msg

RSA Encrypt and Decrypt - Example

Let examine one example of RSA encryption and decryption, along with the calculations, following the above formulas. Assume we have generated the RSA public-private key pair:

modulus n = 143
public exponent e = 7
private exponent d = 103
public key = {n, e} = {143, 7}
private key = {n, d} = {143, 103}

Let’s encrypt a secret message msg = 83. Just follow the formula:

encryptedMsg = msge mod n = 837 mod 143 = 27136050989627 mod 143 = 8

Now, let’s decrypt the encrypted message back to its original value:

decryptedMsg = encryptedMsgd mod n = 8103 mod 143 = 1042962419883256876169444192465601618458351817556959360325703910069443225478828393565899456512 mod 143 = 83

The RSA calculations work correctly. This is because the key-pair meets the RSA property:

(me)d ≡ m (mod n) for all m in the range [0…n)
(m_7)103 ≡ _m (mod 143) for all m in the range [0…143)

In the real world, typically the RSA modulus n and the private exponent d are 3072-bit or 4096-bit integers and the public exponent e is 65537.

For further reading, look at this excellent explanation about how RSA works in detail with explainations and examples: http://doctrina.org/How-RSA-Works-With-Examples.html.

Because RSA encryption is a deterministic (has no random component) attackers can successfully launch a chosen plaintext attack against by encrypting likely plaintexts with the public key and test if they are equal to the ciphertext. This may not be a problem, but is a weakness, that should be considered when developers choose an encryption scheme.

Hybrid encryption schemes like RSA-KEM solve this vulnerability and allow encrypting longer texts.

Licenses and Attributions

Speak Your Mind Cancel reply

-->

Related Books