A method for encoding long messages for electronic signature schemes based on rsa

A method using an RSA modulus N, the said method using an encoding function μ taking as an input a message of size limited to k+1 bits, k being an integer parameter, and returning as an output a character string of size exactly k bits, the said method taking as an input an integer parameter a between 0 and k−1, the said method consisting in defining a new encoding function μ′ taking as an input a message of size no more than (2{circumflex over ( )}a)*(k−a) bits and returning as an output a message of size k bits, said method characterised in that it includes the following 4 steps:

• 1) Separating the message into blocks of size k−a bits, the message being denoted m=m[1]||m[2]|| . . . ||m[r] where r is the number of blocks.
• 2) Initialising to 1 an integer variable b.
• 3) For i ranging from 1 to r, calculating the result of the function μ applied to the string of bits formed by the concatenation of the bit 0, of the counter i represented by a string of a bits and of the block m[i], and multiplying the said result by the variable b, the result of the multiplication being stored in the variable b, the said multiplication being implemented modulo N;
• 4) Applying the function μ to the string of bits formed by the concatenation of the bit 1 and of the variable b, and returning the result as an output.