the-rsa-cryptosystem-concepts.md

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:

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEApwni+ErA4h6wyqAYz39p
f3dOlvgRX8I1npz2Cx3Y1ASNl0zfhCK+9r48FisEuRb36iEz8OPk4O7hZIWb2cHg
7wNXwUL09jO0rdSquGyPiJXNM/v04CTZo61r5iZ1cLSnLSw0NU4BOedK2mZaFqJh
FJDeu44TGmz/x+8l50JAgD3XGk/NlTyYgRGwqpu8TFcCT8XoxEYq2QScfxq+2FnG
NFX6bVi1zDSj0yBv90uelsM226zwzdGO0MZnls4AqwfzayTL4zQlI/2CFajnf4no
agjbkR8jdFk4je5kLa58smRKA+ce1cb6UHfPQJD6+lVgSLU2uHmoj2KGmPDHtCDE
twIDAQAB
-----END PUBLIC KEY-----

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:

-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEApwni+ErA4h6wyqAYz39pf3dOlvgRX8I1npz2Cx3Y1ASNl0zf
hCK+9r48FisEuRb36iEz8OPk4O7hZIWb2cHg7wNXwUL09jO0rdSquGyPiJXNM/v0
4CTZo61r5iZ1cLSnLSw0NU4BOedK2mZaFqJhFJDeu44TGmz/x+8l50JAgD3XGk/N
lTyYgRGwqpu8TFcCT8XoxEYq2QScfxq+2FnGNFX6bVi1zDSj0yBv90uelsM226zw
zdGO0MZnls4AqwfzayTL4zQlI/2CFajnf4noagjbkR8jdFk4je5kLa58smRKA+ce
1cb6UHfPQJD6+lVgSLU2uHmoj2KGmPDHtCDEtwIDAQABAoIBABDyJyflUuLIa6Bt
ftbeKDJu73bQEoMnzWTFVmNo/cGp90CtjdIhQZpVUPyMFLM/qfBYufpARHdar1xm
qZmn2k1P24FBwl7lKU6mpUMx0EXyXJpff0eWCsuuIPonq1ZpyA6vI1odCxwiuNdQ
oZHA8MmzVhqqSTSEcQE0OSDYTyQzTTrwX+3g41WRHH24uN479DWQfIVcPX7u3k8U
jfgwtD3TYLQ2kiOawQ5WbxOPtLMPsa8GA8/PDNit9DSaDQuTv4mATnwuJMp2FeUa
9m3M/bcaEgTiEHq77kJZ8srJF/r+OwKbrxPE3eeSPEfuP+wkg5AgOjhLnrdzwVRU
DFGWvOECgYEAyIk7F0S0AGn2aryhw9CihDfimigCxEmtIO5q7mnItCfeQwYPsX72
1fLpJNgfPc9DDfhAZ2hLSsBlAPLUOa0Cuny9PCBWVuxi1WjLVaeZCV2bF11mAgW2
fjLkAXT34IX+HZl60VoetSWq9ibfkJHeCAPnh/yjdB3Vs+2wxNkU8m8CgYEA1Tzm
mjJq7M6f+zMo7DpRwFazGMmrLKFmHiGBY6sEg7EmoeH2CkAQePIGQw/Rk16gWJR6
DtUZ9666sjCH6/79rx2xg+9AB76XTFFzIxOk9cm49cIosDMk4mogSfK0Zg8nVbyW
5nEb//9JCrZ18g4lD3IrT5VJoF4MhfdBUjAS1jkCgYB+RDIpv3+bNx0KLgWpFwgN
Omb667B6SW2ya4x227KdBPFkwD9HYosnQZDdOxvIvmUZObPLqJan1aaDR2Krgi1S
oNJCNpZGmwbMGvTU1Pd+Nys9NfjR0ykKIx7/b9fXzman2ojDovvs0W/pF6bzD3V/
FH5HWKLOrS5u4X3JJGqVDwKBgQCd953FwW/gujld+EpqpdGGMTRAOrXqPC7QR3X5
Beo0PPonlqOUeF07m9/zsjZJfCJBPM0nS8sO54w7ESTAOYhpQBAPcx/2HMUsrnIj
HBxqUOQKe6l0zo6WhJQi8/+cU8GKDEmlsUlS3iWYIA9EICJoTOW08R04BjQ00jS7
1A1AUQKBgHlHrV/6S/4hjvMp+30hX5DpZviUDiwcGOGasmIYXAgwXepJUq0xN6aa
lnT+ykLGSMMY/LABQiNZALZQtwK35KTshnThK6zB4e9p8JUCVrFpssJ2NCrMY3SU
qw87K1W6engeDrmunkJ/PmvSDLYeGiYWmEKQbLQchTxx1IEddXkK
-----END RSA PRIVATE KEY-----

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)
• (m7)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.