How To Pad Data in RSA: Meet PCKS#1 v1.5

How To Pad Data in RSA: Meet PCKS#1 v1.5

Many of the methods we have for encryption are based on PKCS (Public Key Cryptography Standards) documents. These were defined by RSA Security in the 1990s but have since become standards within RFC documents.

In symmetric key encryption, we use PKCS#5 (Cryptographic Message Syntax) padding. This fills a block with a value which equals the number of bytes to be padding. But, in RSA, we do not have a block and have a modulus (N). We thus need to pad our input data to make the encryption input equal to the length of the modulus. One of the most popular methods for this is PCKS#1 v1.5 [RFC3447].

With PCKS#1 v1.5, for a message of M, we create a padded input of:

EM=0x00 || 0x02 || random || 0x00 || M

and where random is a random byte stream which does not contain 0x00. The number of the padding input must equal the number of bytes in the module (L). Thus the number of random bytes will be:

L−3−len(M)

It should be noted that the random data cannot have a 0x00 value, as the unpadding process will think that the message follows. If we have a padded input of:

em = b('\x00\x02') + ps + bchr(0x00) + message

Then we need to make sure that ps does not have a 0x00 byte. Thus we can use a replace method to find the values of 0x00 in the random byte array and replace it with a random value (which is not zero):

ps = tobytes(randFunc(k-mLen-3))
ps = ps.replace(b'\x00',bchr(random.randint(1,255)))

PCKS#1v1.5 is not provable security and can be replaced with RSAES-OAEP for an increased level of security.

Coding

The coding is [here]:

from Crypto.Util.number import *
from Crypto import Random
from Crypto.Util.number import ceil_div
from Crypto.Util.py3compat import *
import Crypto.Util.number
import os
import sys
   
def genRSAKey(bits):
    p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
    q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
    PHI=(p-1)*(q-1)
    n=p*q
    e=65537
    d=pow(e,-1,PHI)
    return n,e,d

bits=256
msg="Hello"
if (len(sys.argv)>1):
    msg=(sys.argv[1])
if (len(sys.argv)>2):
    bits=int(sys.argv[2])    
 
message=msg.encode()
   
randFunc = Random.get_random_bytes
N,e,d=genRSAKey(256)

message=b'Hello'

modBits = Crypto.Util.number.size(N)
k = ceil_div(modBits,8) # Number of bytes in modulus
mLen = len(message)
    
if mLen > k-11:
    raise ValueError("Plaintext is too long.")

ps = tobytes(randFunc(k-mLen-3))

em = b('\x00\x02') + ps + bchr(0x00) + message  

print(f"e={e}, d={d}, N={N}")
print(f"\nModulus length: {len(em)//2} bytes or {len(em)*4} bits")  
        
print ("With padding: ",em.hex())

print(f"\n0002 -- {ps.hex()} -- 00 ---  {message.hex()}")

# x = 0x00 || 0x02 || r || 0x00 || m

# length of r is k-Len-3 bytes, and where k is the number of bytes in modulus (N)
# and Len is the number of bytes in the message

C=pow(int.from_bytes(em, byteorder='little'),e,N)
print(f"\nCipher: {C}\n")
M_rec = pow(C,d,N)
vals =M_rec.to_bytes(k , byteorder='little')
print(f"De-cipher: {vals.hex()}\n")

and a sample run for 256-bit prime numbers is [here]:

e=65537, d=10190917947404513550411160432275083486071267254246328819495466576473921743249866517071171351789965923432076534676997880501351521360050585839038879924010433, N=11016250012684935829800191684398240823835133555042170185614897537769828777399166203021419108635411627633434496021535370453761177749097120774288027938392779

Length: 32 bytes or 256 bits

With padding: 0002383eec50570debca717f53d839515513d8c1efcba7bd9ac0931420f42897341714f2872c0958541b66ca6a27ca912f0c51655ede4de8b6580048656c6c6f

0002 -- 383eec50570debca717f53d839515513d8c1efcba7bd9ac0931420f42897341714f2872c0958541b66ca6a27ca912f0c51655ede4de8b658 -- 00 ---  48656c6c6f

Cipher: 183424160850201022827866448761517703535053101425978766548474696429861112060003687875513703104831909036189361877088551020964124550197980536547062963310822

De-cipher: 0002383eec50570debca717f53d839515513d8c1efcba7bd9ac0931420f42897341714f2872c0958541b66ca6a27ca912f0c51655ede4de8b6580048656c6c6f

and 512 bits [here]:

e=65537, d=33132477793618774925467557000049625526160016587516734599868526306029585712180703571286684725527373577525978813130636957645262281016424013580320743615585446435862800362609347662272715161402708493101191837114776280075869430758819840938574070181268825808958191935689745511073984040072726992380999316034425337989, N=90095979302119980593766535957522605207582631720513017529213875296388571379577061945621155008376726366139167398703064366341544089912177112070597924332377240128941255245652067384085150005755328258626089394992284213829456953631951029554641717047070401420450742033661846484269238842786744044180559160181437370521

Modulus length: 64 bytes or 512 bits
With padding:  000286eca60603495edc02607e5929983e85393c7056bed18f38905805f018ab753f402e77c4b76d8a2c78d9565106f7260d548c30773d62991e9b77a5410489e90b43893f40ba0f83bfdfcbb19948eb5ca0260721cb04932344fd44d7c575002312170fccc2a38cdffb8128566e1b3c8961485ec24ae9c1b4840048656c6c6f

0002 -- 86eca60603495edc02607e5929983e85393c7056bed18f38905805f018ab753f402e77c4b76d8a2c78d9565106f7260d548c30773d62991e9b77a5410489e90b43893f40ba0f83bfdfcbb19948eb5ca0260721cb04932344fd44d7c575002312170fccc2a38cdffb8128566e1b3c8961485ec24ae9c1b484 -- 00 ---  48656c6c6f

Cipher: 89659767125445470058368319797099264904910265365002474676783301529043166078422359188746437874678312997221656189401033777932305035343772703301284588249833531051641459556494044614471187630505267207893455298121554974333929053627273744364653537159142713128169053016671096626572641936993612123963439722017698369586

De-cipher: 000286eca60603495edc02607e5929983e85393c7056bed18f38905805f018ab753f402e77c4b76d8a2c78d9565106f7260d548c30773d62991e9b77a5410489e90b43893f40ba0f83bfdfcbb19948eb5ca0260721cb04932344fd44d7c575002312170fccc2a38cdffb8128566e1b3c8961485ec24ae9c1b4840048656c6c6f

The padding can be split as:

0002 86eca60603495edc02607e5929983e85393c7056bed18f38905805f018ab753f402e77c4b76d8a2c78d9565106f7260d548c30773d62991e9b77a5410489e90b43893f40ba0f83bfdfcbb19948eb5ca0260721cb04932344fd44d7c575002312170fccc2a38cdffb8128566e1b3c8961485ec24ae9c1b484 
00 
48656c6c6f

And where the message is “48656c6c6f” (in hex this represents “hello”). Once we have the padding (em), we can convert it to an integer and then can then encrypt and decrypt:

inval=int.from_bytes(em, byteorder='little')
C=pow(inval,e,N)
print(f"\nCipher: {C}\n")
M_rec = pow(C,d,N)
vals =M_rec.to_bytes(k , byteorder='little')
print(f"De-cipher: {vals.hex()}\n")

Although PKCS#1 v1.5 is by far the most popular padding method, it is open to a range of attacks, including the Bleichenbacher’s attack:

https://asecuritysite.com/rsa/c_c3