PKCS#1 Schemes


Algorithm: Encryption using PKCS#1v1.5 INPUT: Recipient's RSA public key, (n, e) of length k = |n| bytes; data D (typically a session key) of length |D| bytes with |D|<=k-11.
OUTPUT: Encrypted data block of length k bytes

  1. Form the k-byte encoded message block, EB, EB = 00 || 02 || PS || 00 || D
    where || denotes concatenation and PS is a string of k-|D|-3 non-zero randomly-generated bytes (i.e. at least eight random bytes).
  2. Convert the byte string, EB, to an integer, m, most significant byte first, m = StringToInteger(EB, k)
  3. Encrypt with the RSA algorithm c = m^e mod n
  4. Convert the resulting ciphertext, c, to a k-byte output block, OB OB = IntegerToString(m, k)
  5. Output OB.


The conversions in steps (2) and (4) from byte string to large integer representative and back again may not be immediately obvious. Large integers and byte (bit) strings are conceptually different even though they may both be stored as arrays of bytes in your computer.
Worked Example

Bob's 1024-bit RSA encryption key in hex format:
n=
A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F
BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9
3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C
FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB
e=010001
d=
67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35
DE0E827830CBE7BA6A56AD77C6EB517970790AA0F4FE45E0A9B2F419DA8798D6
308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D14
9E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319
A randomly-generated one-off session key for AES-128 might be D=4E636AF98E40F3ADCFCCB698F4E80B9F
The encoded message block, EB, after encoding but before encryption, with random padding bytes shown in green, 0002257F48FD1F1793B7E5E02306F2D3228F5C95ADF5F31566729F132AA12009
E3FC9B2B475CD6944EF191E3F59545E671E474B555799FE3756099F044964038
B16B2148E9A2F9C6F44BB5C52E3C6C8061CF694145FAFDB24402AD1819EACEDF
4A36C6E4D2CD8FC1D62E5A1268F496004E636AF98E40F3ADCFCCB698F4E80B9F
After RSA encryption, the output is 3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
Note that the output for encryption will be different each time (or should be!) because of the random padding used.
Encrypting a message

For a plaintext message, say, PT="Hello world!"
that is, the 12 bytes in hex format, PT=48656C6C6F20776F726C6421
Then, using the 128-bit session key from above, KY=4E636AF98E40F3ADCFCCB698F4E80B9F
and the uniquely-generated 128-bit initialization vector (IV) IV=5732164B3ABB6C4969ABA381C1CA75BA
the ciphertext using AES-128 in CBC mode with PKCS padding is, CT=67290EF00818827C777929A56BC3305B
The sender would then send a transmission to the recipient (in this case, Bob) including the following information in some agreed format:



Recipient: Bob
Key Encryption Algorithm: rsaEncryption
Encrypted Key:
3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
Content Encryption Algorithm: aes128-cbc
IV: 5732164B3ABB6C4969ABA381C1CA75BA
Encrypted Content:
67290EF00818827C777929A56BC3305B