2
$\begingroup$

This question already has an answer here:

I'm trying to figure out how to convert a message to a message representative (non-negative integer) in RSA. I think I understand how the OS2IP primitive (converting from message to integer). It involves finding the sum of all the integer representations of each byte multiplied by 256 to the power of the length of the message minus the index for the byte. However, I don't understand how the opposite process works. PKCS#1 says to write the message representative x in its xLen-digit unique representation in base 256. I'm not very good with the actual mathematical processes here, so I'm not sure how the integer is supposed to be separated into the separate bytes multiplied by powers of 256.

$\endgroup$

marked as duplicate by Maarten Bodewes, otus, e-sushi Dec 13 '16 at 10:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

Basically I2OSP is nothing more than a fixed size big endian representation of the integer, using a given number of bytes (or octets, same thing). The way that this is described in PKCS#1 is very technical, but this is what it comes down to. Big endian (or network order, same thing) numbers need to be left padded with zero bytes in case they are too small.

For RSA, the length given to I2OSP is nothing more than the modulus size in bytes. Usually this is just the modulus divided by 8 as most RSA key sizes can are multiples of 8. The standard however does define that the minimum number of bytes required for the unsigned representation of the number is to be used.

Obviously I2OSP would have to report an error if the integer doesn't fit. However, given that RSA calculations are performed modulus $n$, this can never happen.


Usually runtimes already have methods to encode a number (usually called a bignum or BigInteger or something similar) into big endian encoding. If only little endian is available you'll have to reverse the bytes in the array yourself before proceding.

After you're retrieved the big endian encoding you simply have to left-pad with zero's, and that's it.

You may have to strip a single zero byte from the output in case you only have a signed encoding available within your runtime.


What you do not want to do is perform the mathematical calculations yourself. What is described is nothing more than a binary representation of the number, and this binary representation is already present in one form or other in the memory of your runtime.

$\endgroup$