I started working with RSA two weeks ago. But I couldn't really understand how exactly I2OSP & OS2IP are working. I am using some open source for signature verification through RSA PSS algorithm.
I am trying to generate "EM" from a signature of length 256 bytes, public modulus $n$ (256 bytes) and exponent $e$ (0x10001). But I am not getting the expected output ("EM"). So I started debugging code.
Can someone clearly explain what OS2IP & I2OSP do?
I2OSP and OS2IP mean Integer to Octet Stream Primitive and Octet Stream to Integer Primitive. There is an often used play on words here: "two" (2) has almost the same pronunciation as "to". The word "octet" simply means 8-bit "byte" and that "stream" can be replaced with "array". So these are conversion functions between integers to byte arrays.
The I2OSP function simply represents an integer in a statically sized byte array. For this it requires two inputs: the integer itself and the required size of the byte array. If the integer "doesn't fit" then an error is produced.
The integer is encoded as an unsigned big endian (network order) number, prefixing leading zero bits and bytes at the left hand side until the size is reached.
So lets take a look at some examples with output size of 2 octets with the integer (in decimals) on the left and octets / bytes at the right (in hexadecimals, separated by colons):
-1 -> error
0 -> 00:00
1 -> 00:01
255 -> 00:FF
256 -> 01:00
65535 -> FF:FF
65536 -> error
So any integer will be represented with the same number of bytes, and each number will have a unique (or canonical) representation.
This function is used to make sure that signatures and encrypted values for a specific key size will also be represented in the same way, using the same number of bytes. For instance in RSA - for which these functions are defined - the size of the signature and ciphertext is always the same as the key size (or: modulus size) in bytes.
The size of the array used for RSA is the minimum size of the modulus encoded using I2OSP. The size of the modulus in bits is the same as the key size. So signatures for RSA with a 2047 bit key size (generally not used) and 2048 bit key size will both be 256 bytes in size.
The error conditions of I2OSP should never happen for RSA / PKCS#1 as all calculations will result in a number smaller than the modulus. So the number will fit - by definition - in an array that can also hold the modulus.
The encoding returned by I2OSP is specific to RSA instead of specific to the internal number representation within a language / runtime / operating system / CPU architecture. This means that the byte encoding of the signature is portable across the different runtimes.
OS2IP will do the exact reverse. It's usually easier to implement as languages/runtimes generally simply skip leading zeros when converting integers from bytes. You must however make sure that the bytes are interpreted as an unsigned big endian value.
For little endian machines it may be required to reverse the order of bytes. It could also be required to add a 00 valued byte at the most significant location. Otherwise the number may be interpreted as a (two-complement) signed value, which may result in a negative value.
Often I2OSP is programmed the way it is described in the PKCS#1 specifications. This however is a rather mathematical description of the encoding. Generally integers are already represented in a way that is largely compatible with the description of I2OSP, which means that some copying and resizing (and possibly reversing for little endian systems) is all that is required. For instance, check my implementation for Java here.
