difficulty understanding the example in RFC 6979

Question

I'm trying to follow section A.1.2 of RFC 6979 and am having some difficulty.

So h1 is as follows:

   h1
      AF 2B DB E1 AA 9B 6E C1 E2 AD E1 D6 94 F4 1F C7
      1A 83 1D 02 68 E9 89 15 62 11 3D 8A 62 AD D1 BF

If that is run through bits2octets(h1) you're supposed to get this:

  01 79 5E DF 0D 54 DB 76 0F 15 6D 0D AC 04 C0 32
  2B 3A 20 42 24

I don't understand how.

Here's bits2octets defined in Java (from the RFC):

      private byte[] bits2octets(byte[] in)
      {
              BigInteger z1 = bits2int(in);
              BigInteger z2 = z1.subtract(q);
              return int2octets(z2.signum() < 0 ? z1 : z2);
      }

Here's bits2int:

      private BigInteger bits2int(byte[] in)
      {
              BigInteger v = new BigInteger(1, in);
              int vlen = in.length * 8;
              if (vlen > qlen) {
                      v = v.shiftRight(vlen - qlen);
              }
              return v;
      }

Heres q:

  q = 0x4000000000000000000020108A2E0CC0D99F8A5EF

h1 is 32 bytes long. q is 21 bytes long.

So bits2int returns the first 21 bytes of h1. ie.

af2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268

Convert that to an integer and then subtract q and you get this:

  af2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268
- 04000000000000000000020108A2E0CC0D99F8A5EF
  ------------------------------------------
  ab2bdbe1aa9b6ec1e2addfd58c513efb0ce9245c79

The result is positive so it - z2 - is kept.

Then int2octets() is called.

      private byte[] int2octets(BigInteger v)
      {
              byte[] out = v.toByteArray();
              if (out.length < rolen) {
                      byte[] out2 = new byte[rolen];
                      System.arraycopy(out, 0,
                              out2, rolen - out.length,
                              out.length);
                      return out2;
              } else if (out.length > rolen) {
                      byte[] out2 = new byte[rolen];
                      System.arraycopy(out, out.length - rolen,
                              out2, 0, rolen);
                      return out2;
              } else {
                      return out;
              }
      }

q and v are the same size so ab2bdbe1aa9b6ec1e2addfd58c513efb0ce9245c79 is returned. But that's not what the test vector says:

   bits2octets(h1)
      01 79 5E DF 0D 54 DB 76 0F 15 6D 0D AC 04 C0 32
      2B 3A 20 42 24

I don't get it. Did I mess up in my analysis somewhere?

Answer 1

The output is obtained as (0xaf2b...d1bf >> (256 - 163)) mod q = 0x0179...4224. Your mistake was assuming bits2int shifted bytes instead of bits.