Digital Signature - A Classical Introduction to Cryptography: Applications for Communications Security - page 252

The extraction scheme is thus performed as follows.

1. We open the signature. (In case of RSA, we raise the signature to the public
exponent.)
2. We first check that the signature is of length k and that the rightmost hexadecimal
digit is 6.
3. We perform a message recovery : we remove the leading bit 1, replace the right-
most two bytes y H y R x H x R by y H y R π − 1 ( y H ) x H , obtain ..., x 2 , x 1 , take z as

the smallest index such that x 2 z ⊕ S ( x 2 z − 1 ) = 0 (reject if it does not exist) and

set r equal to this value (and check that r ≤ 8), extract x 2 z , x 2 z − 2 ,..., x 2 , and

−

1 leftmost bits (reject if they are not equal to zero). We must
obtain a message m .
4. Check that the formatting scheme on m leads to the value obtained after opening
the signature. (Check the redundancy.)

remove the r

One important property of this scheme is the message recovery : as long as the message
m is of length at most d , we do not need to send it with the signature σ : the verification

process enables the recovery of m .

As an example, let us consider the message “ PAY 1'000'000.-CHF ” with

k = 512. The message (of 18 characters) turns in hexadecimal into

PAY 1'000'000. - CH F
50 40 59 20 31 27 30 30 30 27 30 30 30 2e 2d 43 48 46

hence

5040 5920312730303027 3030302e2d434846 .

We e z = 18

and we need t = 32 bytes. So we take

||

3127303030273030 302e2d434846 5040 5920312730303027 3030302e2d434846

i.e. the message plus an extra 14 bytes. We then add the S redundancy and get

83315f278e308e30 8e305f278e308e30 8e305c2era2d9843 904892464e509e40
4d595e2083315f27 8e308e308e305f27 8e308e308e305c2e 5a2d984390489246
(note that the z -th redundancy byte is 4e as S ( 50 )) and XORing the z -th redundancy
byte to r

=

1 we obtain

83315f278e308e30 8e305f278e308e30 8e305c2era2d9843 904892464f509e40
4d595e2083315f27 8e308e308e305f27 8e308e308e305c2e 5a2d984390489246
and the final operation leads to

83315f278e308e30 8e305f278e308e30 8e305c2era2d9843 904892464f509e40
4d595e2083315f27 8e308e308e305f27 8e308e308e305c2e 5a2d984390489266
which can now feed the plain RSA signature scheme.