Optimal Asymmetric Encryption Padding (OAEP) allows for a message to be encrypted using RSA. It thus uses RSA encryption and integrates a padding scheme. It was defined by Bellare and Rogaway, and has been standardized in PKCS#v1.5 and RFC 2437 [
here
]. We use RSA-OAEP to pad the message, and then encrypt with \(C = {M_p}^e \pmod n\) and decrypt with \(M_p = C^d \pmod N\) and where \(M_p\) is the padded message. The padding is added before the encryption process, and then stripped off after decryption.
Private key:
-----BEGIN PRIVATE KEY-----
MIIBzQIBADANBgkqhkiG9w0BAQEFAASCAbcwggGzAgEAAlwA2SnbHxfOniQcFCtC
P9dlbm81plxThz8ngCDNaxO87CbiXiyCsFL3JgnOTNobT/QfD+5g+6Tpe5rXGh2X
Kxo8YVF5raPZsflvqgwLkvKsZGdXkFSbGWNrCSYtrQIDAQABAls64tGrJb5+PVZr
1asaOqMjhf5rRP/VXbetU7fAAFMrSgP5+2HYxDaGVwRc7IuRa9gi+KGsF1lGxyt9
IkrX1opXw7F1FDD3C4RI/Lc9VW7CEqxZclFxVCetWcx1Ai4PYIkp2ZFuGICCTWIP
mf0YCrqSJmLEuGk008/fU0xJKnN/OyoKZ3KqoprW5sUTAi4OH15PhLe+oLAMeEfn
f1pBmWTSLbVFz7VM7MLN62/XWYAUcfditbLJvnrAAVo/Ai4E8eNJ/Pgicmio/l+B
auCT4adbplJutmrGnTKku3G1uZwIlysOy3N5Ye7vGqjXAi4HbTeLWZ/G/3mVFSu6
8Z3lIWWDocXSEIinC1rmLwmBle9k0QnnPuXmceTbU9rBAi4JfgUGvAT0Ltxq8q6y
ppPjU+wJgKnQGmZBcY+2x7gHv66dWULOeX02nzfk8dSn
-----END PRIVATE KEY-----
Public key:
-----BEGIN PUBLIC KEY-----
MHcwDQYJKoZIhvcNAQEBBQADZgAwYwJcANkp2x8Xzp4kHBQrQj/XZW5vNaZcU4c/
J4AgzWsTvOwm4l4sgrBS9yYJzkzaG0/0Hw/uYPuk6Xua1xodlysaPGFRea2j2bH5
b6oMC5LyrGRnV5BUmxljawkmLa0CAwEAAQ==
-----END PUBLIC KEY-----
Encrypted: 849ceed6fc0f269a293909770dc7d156f447a055193a2d1bae9c328665192aebba807ffb58539fe0715bd1c8d0312189f38abf284e35fc272555ab59d6f762bbdc185ec201f30c434216789155beb5f24bc1b069796e7c074770e8
Encrypted: hJzu1vwPJpopOQl3DcfRVvRHoFUZOi0brpwyhmUZKuu6gH/7WFOf4HFb0cjQMSGJ84q/KE41/CclVatZ1vdiu9wYXsIB8wxDQhZ4kVW+tfJLwbBpeW58B0dw6A==
Decrypted: Test
Theory
While the RSA algorithm has required an increasing size of modulus in order to keep up with the advancement of computing hardware, it has continually been affected by the usage of its padding. So, let's dive in, and see if we can understand why this is the case.
If you're into cybersecurity, you should hopefully know that symmetric key ciphers often use blocks. With AES, for example, we have a block size of 128 bits (16 bytes), and where we process these blocks to cipher and decipher. But the last block is unlikely to fill all the bytes in this block, and so we add in padding. This padding is typically derived from the number of empty spaces and repeated for the number of spaces left. And so, "hello" is padded with 11 padding values (0b):
h e l l o 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b
This padded version of the block is then ciphered, and deciphered at the other end. Finally the padding is removed to reveal the plaintext message. But what about RSA? It uses integers and a mathematical ciphering operation of:
\(C=M^e \pmod N\)
and where \(M\) is an integer value of the message, \(e\) is the encryption exponent, and \(N\) is the modulus. This modulus is created by multiplying two random prime numbers (\(p\) and \(q\)). Our modulus will thus limit the size of \(M\) that we can have, as we cannot have a value of \(M\) greater than \(N\) (as it would wrap around - and where two or more inputs will give the same cipher value).
PKCS#v1.5 - Simple padding
The simplest way to pad is to use PKCS#v1.5. With this, we pad to the start of the message bytes, and where the first two bytes are 0x00 and 0x02, and followed by a number of non zero bytes. We then add a 0x00 byte to identify the end of the padding, and then followed by the message bytes:
0x00 0x02 [some non-zero bytes ] 0x00 [message bytes]
When unpadding, the 0x00, 0x02 sequence is detected, and then we search for the 0x00 byte and take remove all of the preceding bytes. Unfortunately, Daniel Bleichenbacher published a paper [2] that showed how the PCKS#v1.5 padding method could be cracked with a chosen cipher attack: [
here
]:
The Bleichenbacker's attack has been continually compromising some systems for decades, but TLS 1.3 now overcomes it by dropping support for PCKS#v1.5.
Optimal Asymmetric Encryption Padding (OAEP)
So, our solution is to use padding, and one of the most popular methods is Optimal Asymmetric Encryption Padding (OAEP). The method was first published by Bellare and Rogaway as [
here
][1]:
It has since been standardized in PKCS#1 v2 and RFC 2437 [
here
]:
Overall we operate on \(n\) bits at a time, and where n is the number of bits in the modulus (Figure 1). This is based on a Feistel network, and where if we EX-OR sometime with the same value twice, we end up with the original value.
With this - as illustrated in Figure 1 - we have two fixed values of \(k_0\) and \(k_1\). \(k_1\) defines the number of zeros to pad onto the message, and \(k_0\) defines the number of bits in a random number (\(r\)). The number of bits we are processing in the message is thus \(n-k_0-k_1\) bits. We then have two hashing functions of \(G\) and \(H\). The \(G\) function expands the \(k_0\) bits of \(r\) into \(n-k_0\) bits, and which is EX-OR with the padded message. This produces \(X\). Next, we take the value and feed it into H, and which hashes the bits to produce \(k_0\) bits. This is then EX-OR (\(\oplus\)) with \(r\) to produce \(Y\) (and which has \(k_0\) bits).
Figure 1: Padding and unpadding for RSA OAEP
We now have \(X\) and \(Y\) for our padding (\(M_p=X || Y\)), and where the total number of bits will be \(n\). This can then be operated on with a \(\pmod N\) operation. The values of \(X\) and \(Y\) can now go into our cipher for:
\(C={M_p}^e \pmod N\)
and then decrypted with:
\(P = C^d \pmod N\)
We can now strip off the padding. To recover the message we first recover the random value (\(r\)) from:
\(r= Y \oplus H(X)\)
and then with r we recover the padded message:
\(m00…0 = X \oplus G(r)\)
We then strip off \(k_1\) zeros from the end of this message and recover \(M\).
Coding
The coding using the Crypto Node.js library is:
const crypto = require("crypto");
var message="hello";
var modulus=728;
var method=crypto.constants.RSA_PKCS1_OAEP_PADDING;
var padding ="RSA_PKCS1_OAEP_PADDING";
var args = process.argv;
if (args.length>2) message=args[2];
if (args.length>3) modulus=parseInt(args[3]);
if (args.length>4) padding=args[4];
if (padding=="RSA_PKCS1_PADDING") method= crypto.constants.RSA_PKCS1_PADDING;
else if (padding=="RSA_PKCS1_OAEP_PADDING") method= crypto.constants.RSA_PKCS1_OAEP_PADDING;
else padding= crypto.constants.RSA_NO_PADDING;
const keyPair = crypto.generateKeyPairSync('rsa', {
modulusLength: modulus,
padding: method,
publicKeyEncoding: { format: 'pem', type: 'spki' },
privateKeyEncoding: { format: 'pem', type: 'pkcs8' }
encrypted = crypto.publicEncrypt({
key: keyPair.publicKey,
padding: method,
oaepHash: 'sha256'
},Buffer.from(message, 'utf8'));
var decrypted = crypto.privateDecrypt({
key: keyPair.privateKey,
padding: method,
passphrase: 'test',
oaepHash: 'sha256'
}, encrypted);
console.log("Message: ",message);
console.log("Padding:\t",padding);
console.log("Private key:\n",keyPair.privateKey);
console.log("Public key:\n",keyPair.publicKey);
console.log("Encrypted: ",encrypted.toString('hex'));
console.log("Encrypted: ",encrypted.toString('base64'));
console.log("\nDecrypted: ",decrypted.toString());
A sample run for a 728-bit modulus is:
Message: Test
Padding: RSA_PKCS1_OAEP_PADDING
Private key:
-----BEGIN PRIVATE KEY-----
MIIBzQIBADANBgkqhkiG9w0BAQEFAASCAbcwggGzAgEAAlwAvhcuS7xQJ33aLblz
FNUFcSlyPOujbJr4J5CNO5JlOHfpC0F1r2qxRLgjTWqaA9rqEpvNaHcyxA0inm/1
kHnRkruDWLpBssD8amGTS7CmculqNBhnD8O3iL4g9QIDAQABAltc/AXfcjxbNQrW
txJ+LD2/PyDsf++vHpco82LCszfkSXOr19dzeWNBVDmgkva6UKmiyTk3M5irLvU0
QGzJeFWpSdLWnCSdyMaJaaUddVzGlB4FHPU5MEPKEOLBAi4OTJVDsuEmB5JP97Vx
/sAt1gEsNwBEsDHL/4cw9Usz06gmdgAxT/rH/1+5ZpMpAi4NSzin2pCdPa+zF6zf
Wlh9kvi241jdAt2HfkPfS//5oFFEyyd/YZlA73kXSUTtAi4NXqPNycpkgX3XUXgQ
3y4XbVppWf/hOZFF+WURbLjk+4jkdT6W3P5R08BQHM2JAi4AlPts9beA+rNXXsD1
oinfjXCP6RH50udJyDBGdThGgEsufMpE3EvuOM2PRGjdAi4EXBGY31h2TWTfSec6
eVI07RRF0DNi0tT5Ce+W7d3vxF5aqUdd3MQXNSwW9zor
-----END PRIVATE KEY-----
Public key:
-----BEGIN PUBLIC KEY-----
MHcwDQYJKoZIhvcNAQEBBQADZgAwYwJcAL4XLku8UCd92i25cxTVBXEpcjzro2ya
+CeQjTuSZTh36QtBda9qsUS4I01qmgPa6hKbzWh3MsQNIp5v9ZB50ZK7g1i6QbLA
/Gphk0uwpnLpajQYZw/Dt4i+IPUCAwEAAQ==
-----END PUBLIC KEY-----
Encrypted: 7cf1fea8fc487c544d1e7a2085ac3583087fdba244bfbce43e817d4265e5228c58b239ef64b2d00d0eb961e461530d0b150794ed0bf7647e517a479c80e4a7b961590d9d783e691c019491e83c99df69dcd01e479ce67127472b5d
Encrypted: fPH+qPxIfFRNHnoghaw1gwh/26JEv7zkPoF9QmXlIoxYsjnvZLLQDQ65YeRhUw0LFQeU7Qv3ZH5RekecgOSnuWFZDZ14PmkcAZSR6DyZ32nc0B5HnOZxJ0crXQ==
Decrypted: Test
We can see that the encrypted cipher is much larger than the plaintext message. This is due to the padding involved. A sample run for a 1,024-bit modulus is:
Message: Test
Padding: RSA_PKCS1_PADDING
Private key:
-----BEGIN PRIVATE KEY-----
MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBAN459EkrHxmbT7ih
2b4TikysXn4Ej8S+PSOCweCIAXY0hURRpL7A/PCjD+G5cX+GsEBUfrzfhUVyXR+c
jI7pLY446qBfeuBtz4RXeDWvdtqTtNOXDrflBDoom70KZ+guBcLxQs7hicneVBW4
csD6Q+MRHl/Cpx03ZsoL5mD9KAQ3AgMBAAECgYBAH9sEzgOgYPelIFbziTHsJAT0
Oh6+N+Luf0mwn65ETK1z5Fc0j/2s9nCbwuYkVVpAheE4YQtU2cZTW9oXVuPEz5sw
iSY/pd+Fplabw11RKMC74sgbZ8dL1/EgzQctaNkBCbwYdyW/6p6HRCH8T+F8IZCB
OBjSMf8EjmXpKOdcaQJBAPdnbI2fwf9HfsDkmDSn3GSI8OwCd7wS2u3pn7l5bqbq
V88GFM9RolII3/AgzN/ofkhVMsizMt+qMTg+Y8RgIfMCQQDl8pVuX+8eMy2CzxiE
zEBWzzqZH/VGNs8RzPLSMpLsSpHadjPf6Z/7iR3k5L5nMkEZkQ3HXTds5+UI9X64
XGGtAkEAwO8itH81poJ20q5yE/4j3TL9zs9N2JlLqeVa7iVIqVpvB79SUyryTs8k
8/pgSuzgLkBizikRL2Nl5tqgqu/dCQJAcT/RMsQSy2ffMT53z+echGSZcpLXxNX3
k8fBi56W18M+JD70+4FfZo24aGP0FnUctM/I3nhddMic95WY7ImrHQJBANpQJXmU
k8vvYtWPLl728ROPzSAPy8mfUGoJ8rO2riTIz3jWaXg435Rx41xJ17VXdbLhlE5z
Vg2Qg+yYwChLKpg=
-----END PRIVATE KEY-----
Public key:
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDeOfRJKx8Zm0+4odm+E4pMrF5+
BI/Evj0jgsHgiAF2NIVEUaS+wPzwow/huXF/hrBAVH6834VFcl0fnIyO6S2OOOqg
X3rgbc+EV3g1r3bak7TTlw635QQ6KJu9CmfoLgXC8ULO4YnJ3lQVuHLA+kPjER5f
wqcdN2bKC+Zg/SgENwIDAQAB
-----END PUBLIC KEY-----
Encrypted: 1719a953346f98eba7cdfb84f745e33068fa721e8e174d72478b2ef790384e1a7da2fbb6869f10cf3564d5d419543478e204d2e4200d92c7960ed56bc0118510e52f5237a127bbe1a610dd89d011f3127c3263906735e84d102f710961a624da863ba8cbd7628b5e089d7a8ea9b7f14636e5e0b7ed52a3d7f7eb7c1ef529aa86
Encrypted: FxmpUzRvmOunzfuE90XjMGj6ch6OF01yR4su95A4Thp9ovu2hp8QzzVk1dQZVDR44gTS5CANkseWDtVrwBGFEOUvUjehJ7vhphDdidAR8xJ8MmOQZzXoTRAvcQlhpiTahjuoy9dii14InXqOqbfxRjbl4LftUqPX9+t8HvUpqoY=
Decrypted: Test
References
[1] Bellare, M., & Rogaway, P. (1994, May). Optimal asymmetric encryption. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 92-111). Springer, Berlin, Heidelberg.
[2] Bleichenbacher, D. (1998, August). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1. In Annual International Cryptology Conference (pp. 1-12). Springer, Berlin, Heidelberg.
Referencing this page
This site is currently free to use, but should be properly referenced when used to dissemination of knowledge, including within blogs, research papers and other related activities. Sample reference forms are given below.
Ref: Buchanan, William J (2023).
RSA Optimal Asymmetric Encryption Padding (OAEP) using Node.js
. Asecuritysite.com. https://asecuritysite.com/rsa/node_rsa
Bib: @misc{asecuritysite_94136, title = {RSA Optimal Asymmetric Encryption Padding (OAEP) using Node.js}, year={2023}, organization = {Asecuritysite.com}, author = {Buchanan, William J}, url = {https://asecuritysite.com/rsa/node_rsa}, note={Accessed: October 14, 2023}, howpublished={\url{https://asecuritysite.com/rsa/node_rsa}} }
Licence: This site is intended for the education and advancement of humans, and no rights are given for AI and ML bots to crawl this site.
[