RSA-OAEP : How do Cryptographic hash functions expand a number of bits?

Question

First of, this question is not really code related, but i am trying to understand what happens behind the code. Hope someone know the anwser to this one, because it have been troubling me for some time.

I am writing a program in c#, which is using the RSA crypto service provider. From what i can understand, the class is using SHA1 by standard in its padding. I have been trying to understand what actually happens during the padding, but can't seem to get my head around a single step in the process.

The algorithm for OAEP that i am currently looking at, is simply the wiki one. http://en.wikipedia.org/wiki/OAEP

The step that is troubling me is 3). I thought hash functions always returned a certain amount of bits (SHA1 - 160bits), so how can it simply expand the amount of bits to n-k0, which with a standard 1024 key bit-strenght would be 864 bits?

Answer 1

I've never done anything with OAEP, but crypto hash functions (as described in step 3) use a procedure spelled out in http://en.wikipedia.org/wiki/PBKDF. Basically, to expand the number of output bits, you 1st repeat the hash with an incremented counter concatenated to the argument being hashed, then concatenate those results until you have enough bits. This technique doesn't add entropy to the result, but does allow you to create a longer output bitstream.

From wikipedia: If you want a key that's dklen long, and your crypto hash function U only outputs hlen bits:

DK = T1 || T2 || ... || Tdklen/hlen
Ti = F(Password, Salt, Iterations, i)

F(Password, Salt, Iterations, i) = U1 ^ U2 ^ ... ^ Uc

U1 = PRF(Password, Salt || INT_msb(i))
U2 = PRF(Password, U1)
...
Uc = PRF(Password, Uc-1)

(If you only need one iteration of the cryptographic hash function, c=1, so you don't need the XOR operator ^, and for each i, you only need to calculate U1)

Answer 2

Specifically for OAEP, the recommendation is to use an algorithm called MGF1, which operates. By repeatedly hashing a seed and a counter, and concatenating the results together, the spe I fixation comes from RfC 2437

From the RfC text, where Z is the seed and l is the length of the output:

3.For counter from 0 to {l / hLen}-1, do the following:

a.Convert counter to an octet string C of length 4 with the primitive I2OSP: C = I2OSP (counter, 4)

b.Concatenate the hash of the seed Z and C to the octet string T:

T =    T || Hash (Z || C)

4.Output the leading l octets of T as the octet string mask.