In RSA, we must use a padding method to make sure that the data is securely processed. Typical methods of padding include OAEP (Optimal Asymmetric Encryption Padding) and PKCS #1. In this case we will use either OaepSHA1 or PKCS #1. 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.
RSA Padding for Encryption and Decryption with PowerShell |
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 is:
$plaintext=$Args[0] $size=$Args[1] $padding=[int]$Args[2] $plainBytes = [System.Text.Encoding]::UTF8.GetBytes($plaintext) $tt=[System.Security.Cryptography.RSACryptoServiceProvider]::new($size) $paddingmethod=[System.Security.Cryptography.RSAEncryptionPadding]::Pkcs1 if ($padding -eq 0) { $paddingmethod=[System.Security.Cryptography.RSAEncryptionPadding]::OaepSHA1 } elseif ($padding -eq 1) { $paddingmethod=[System.Security.Cryptography.RSAEncryptionPadding]::OaepSHA256 } elseif ($padding -eq 2) { $paddingmethod=[System.Security.Cryptography.RSAEncryptionPadding]::OaepSHA384 } elseif ($padding -eq 3) { $paddingmethod=[System.Security.Cryptography.RSAEncryptionPadding]::OaepSHA512 } else { $paddingmethod=[System.Security.Cryptography.RSAEncryptionPadding]::Pkcs1} $cipher=$tt.Encrypt($plainBytes,$paddingmethod) "Message: "+$plaintext "Padding method: "+$paddingmethod.ToString() "`nCipher: "+[System.Convert]::ToHexString($cipher) $plain=$tt.Decrypt($cipher,$paddingmethod) "`nDecryption: "+[System.Text.Encoding]::ASCII.GetString($plain) "`n== RSA Parameters ==" $a=$tt.ExportParameters($true) "E: "+[System.Convert]::ToHexString($a.Exponent) "Modulus: "+[System.Convert]::ToHexString($a.Modulus) "D: "+[System.Convert]::ToHexString($a.D) "P: "+[System.Convert]::ToHexString($a.P) "Q: "+[System.Convert]::ToHexString($a.Q) "`n=== As integer values === " "E: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Exponent),'AllowHexSpecifier') "Modulus: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Modulus),'AllowHexSpecifier') "D: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.D),'AllowHexSpecifier') "P: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.P),'AllowHexSpecifier') "Q: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Modulus),'AllowHexSpecifier')
A sample run for a 1,024-bit RSA key pair and with OaepSHA1 padding:
Message: Hello Padding method: OaepSHA1 Cipher: 26F267CDB198FB7090C53B5CE88B09F948A987D69A2B200D243355DE8E95F0045A86CB3215F00560AD358A01ACB7643D8F44DBC5D4B64DB941C6119B9241E9FB Decryption: Hello == RSA Parameters == E: 010001 Modulus: D05ED2FC3CE6CCF7D094C9D14242ECE229F36CB785C6C8C2BD9918DC84415049184C8C9A7819EA4870B69AD9E2D4B27727E04A8E53D517B35EC0AFE0D1394CBD D: 942958CC92616A8D2B7B20A5F2FFB3807D63E181FD55839B35458F2FFDBA93629D1246A30298F0F4F349E406757F4E76FFDF1D4C8FB9A05630150BFD40D7EDE1 P: F5F1E04427EE66D6ABC7CF48590C7FFF29430DAFF460890A5BA4E5D944907B93 Q: D8E3AF2A2E9D959012065AF8750CF46C39BC3CAC333588E76AAD69818620686F === As integer values === E: 65537 Modulus: 10913243725525103442895994490068882173124874893074242685244580589787677584457333586670450469473093615937826380027399657261500352565532909438577916002258109 D: 7759847988303856149029606836400962956308942582316244398315416565971981864224819409212539461922015044353587499463709987322434673146674675818217858032725473 P: 111244005874175162378852558964159734806877701528049943346849627228819558529939 Q: 10913243725525103442895994490068882173124874893074242685244580589787677584457333586670450469473093615937826380027399657261500352565532909438577916002258109