key = -1 % q fails with NIST/BP curves

[zrlsid]

I applied the NIST parameters (P192 - P521) as well as the BP parameters (BP192 - BP512) to the provided sage script. It works great with random key k . I further applied also my own finishing function according to the paper, which also works.

However, as soon as I tested the critical keys k = (-2, -1, 0, 1) % q it all worked but the value -1. I've fixed the critical final step numbers to 2, as the order q is prime.

I wonder if I found an issue in the provided script or is it a user mistake. Can somebody verify my findings. I can also provide my own sage code, based on Mike's code.

[bitwiseshiftleft]

Could you give more details? Which ladder did you use, with how many safe_steps, etc?

Here is an example with NIST P-256:

F  = GF(2^256-2^224+2^192+2^96-1)
ga = F(-3)
gb = F(41058363725152142129326129780047268409114441015993725554835256314039467401291)
xP = F(48439561293906451759052585252797914202762949526041747995844080717082404635286)
E  = EllipticCurve(F,[ga,gb])
P  = E.lift_x(xP)
q  = 115792089210356248762697446949407573529996955224135760342422259061068512044369

steps = 256
safe_steps = steps-2

for i in range(-5,5):
    xR = qr_ladder_avoid_zero(xP,(q+i-2^steps)%q,256,ga,gb,safe_steps)
    if i==0: xRcorrect = "infinity!"
    else: xRcorrect = (i*P).xy()[0]
    print(i,xR,xR==xRcorrect)

which results in:

-5 36794669340896883012101473439538929759152396476648692591795318194054580155373 True
-4 102369864249653057322725350723741461599905180004905897298779971437827381725266 True
-3 42877656971275811310262564894490210024759287182177196162425349131675946712428 True
-2 56515219790691171413109057904011688695424810155802929973526481321309856242040 True
-1 48439561293906451759052585252797914202762949526041747995844080717082404635286 True
0 infinity! True
1 48439561293906451759052585252797914202762949526041747995844080717082404635286 True
2 56515219790691171413109057904011688695424810155802929973526481321309856242040 True
3 42877656971275811310262564894490210024759287182177196162425349131675946712428 True
4 102369864249653057322725350723741461599905180004905897298779971437827381725266 True

[zrlsid]

Thank you for your quick reaction. I'm using the "QR"-Montgomery-Ladder like in your example and I fixed the safe-steps to steps-2

          p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
          a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
          b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
          x = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
          y = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
          q = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
          lgk = 256

          F = GF(p)
          E = EllipticCurve(F,[a,b])
          P = E(x,y)

          # k_q = 2^lgk % q
          k_q = 2^lgk - q

          k = q - 1

          k_m = 2^lgk + ((k - k_q) % q)

          # sage library scalar mult
          Q = k*P
          if Q.is_zero():
        xQR = "infinity!"
          else:
                xQR = Q.xy()[0]

          # QR Montgomery Ladder for short Weierstrass
          xQ = qr_ladder(P.xy()[0],P.xy()[1],k_m,lgk,a)

which results in:

FAIL QR: k=ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550, right=6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, wrong=ba0dabd2693216945557cf0be462937a5c942e756469cd843b1a47d6b4c4a0aa

But I start to suspect with your example, that something goes wrong in my environment. I'm only puzzled why in all the other cases it works fine.

[zrlsid]

I confirm, that your original supplementary.sage has not an issue with key k = -1 % q . The difference to my implementation is the finish_ladder function, which I've implemented it according to Section 2.4.1 of Mike's paper, where

    yP0*Z^3 = Yp / 2
    xP0*Z^2 = Xp = (M^2 - Xpq - Xrp)/3

    => 1/Z = (yP0 * (xP0*Z^2)) / (xP0 * (yP0*Z^3))
    => xQ  = (Xp + Xqp) / Z^2
    => yQ  = (Yp + 2*m*Xqp) / 2*Z^3

I've implemented it as:

def finish_ladder_simple(xP0,yP0,yP,m,xQP,xRP):
    # w/ div 2 and div 3 operations for readability only
    m     = m/2                # m is double at entrance
    nom   = m^2 - xQP - xRP    # = 3*Xp
    den   = 3*xP0*yP
    Zinv  = (nom*yP0*2)/den
    Zinv *= Zinv
    xQ    = (nom/3 + xQP)*Zinv
    return xQ

This functions delivers the correct result, except of the single case k = -1 % q . I also quickly ran it with in range(-5,5) and only the -1 case fails.

Thank you for your help!

[bitwiseshiftleft]

Ah, OK. Shall I close the issue then?

[zrlsid]

Yes, you can close this issue!

However, may I ask for a favor and can you add the "simple" finish_ladder (Section 2.4.1) function in your sage and test it with k = -1 % q . After all I was still not successful to find the issue in my implementation. It's only failing at this scalar.