I try to reproduce the analysis conducted in this presentation by R. Lifchitz. Namely, data signed by an 1024-bit key $n$ (Rabin scheme) and following ISO/IEC 9796-2. From what I understand, for a message $m$ that went through an encoding function $\mu$, the signature $s$ is produced as $s=(\mu(m))^d \pmod{n}$, or maybe using a hash function $h$: $s=(h(\mu(m)))^d \pmod{n}$.

Assume that we know the public key $n$ (given in the presentation):

n = 0xAB9953CBFCCD9375B6C028ADBAB7584BED15B9CA037FADED9765996F9EA1AB983F3041C90DA3A198804FF90D5D872A96A4988F91F2243B821E01C5021E3ED4E1BA83B7CFECAB0E766D8563164DE0B2412AE4E6EA63804DF5C19C7AA78DC14F608294D732D7C8C67A88C6F84C0F2E3FAFAE34084349E11AB5953AC68729D07715

The signature taken as example in the presentation is as follows:

s = 0x01ccc173930a67cfa5623f4921c1eb63116a658c2604d90a5567e5a3db2ec2bd0041c22898f912f70c4ce91f173b735472183d4314eb1ff543f603800f371a40e891b94e452639c5975bc6a47028e57e34e143a9fec48b92354616c5ed5453d2fea03f2301de468ab465b919fc79b8da94df3e8828c96ed5e5b973fd88e4fd2f

Verifying it with $w=s^e \pmod{n}$ yields $v=2(n-w)$ since $w=7\pmod{n}$. The value for $v$ shown in hexadecimal below is highly structured.

 00000000: dc 00 13 09 00 71 dc 01 c4 0c 72 29 d2 09 fc e1  .....q....r)....
 00000010: c6 03 ca 05 dc 01 dc 01 de 0f 77 54 a8 4a ef 99  ..........wT.J..
 00000020: ce 18 ef 99 dc 01 dc 01 dc 01 dc 01 dc 01 dc 01  ................
 00000030: dc 01 dc 00 13 09 00 71 dc 01 c4 0c 72 29 d2 09  .......q....r)..
 00000040: fc e1 c6 03 ca 05 dc 01 dc 01 de 0f 77 54 aa 4a  ............wT.J
 00000050: ef 99 ce 18 ef 99 dc 01 dc 01 dc 01 dc 01 dc 01  ................
 00000060: dc 01 dc 01 dc 00 13 09 00 71 dc 01 c4 0c 72 29  .........q....r)
 00000070: d2 09 fc e1 c6 03 ca 05 dc 01 dc 01 de 0f 77 4c  ..............wL

From this, and seeing the data actually signed given in the presentation (Slide #30), I cannot figure out the encoding function (there does not seem to have a hash function $h$). I have read in https://eprint.iacr.org/2009/203.pdf that that ISO standard should used 0x6A header and 0xBC trailer values, but I cannot find them here. (I add that for a second signature using the same public key, I have the same structured $v$.)

Is there a public description of the encoding function that was used here? A public code implementing the signing algorithm? Any other indication would be helpful.

  • $\begingroup$ Thanks for the comment @fgrieu. Indeed, I did $n-J^*$ instead of $2(n-J^*)$, thanks for the correction. I have edited my question to change this. $\endgroup$ – chewbaca Oct 1 '19 at 18:18
  • $\begingroup$ I apologize that my earlier comment has mislead you. That was unintentional: I gave indications that do apply to the standard in the question's title, but the signature is per a different standard, as proved by the fact that the rightmost byte you now get for v is neither 6c nor cc. I had not noticed that for lack of time to read the link in the question. Because that's about a deployed system, I won't help you more, as a matter of policy. For the record: I have not participated to the design of this system. $\endgroup$ – fgrieu Oct 1 '19 at 20:27
  • $\begingroup$ This is not the padding I get when I decrypt a Bouncy Castle / Java generated signature, so the mystery is not solved by that. However, I hope you do know that ISO/IEC 9796-2 is about signatures giving message recovery, so you'd expect part of the data to be included in the signature, and of course most data is "highly structured". $\endgroup$ – Maarten Bodewes Oct 1 '19 at 20:48
  • $\begingroup$ Yes, I know that some part of the message should be there, that is why I try to parse the result. $\endgroup$ – chewbaca Oct 2 '19 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.