[Cfrg] 40 bit loop and DragonFly

["Igoe, Kevin M." <[e-mail]>]

Scott Fluhrer wrote:

I think we agree that what Dan specified in the draft is broken.  However, I believe that's because Dan got it wrong (and I was busy elsewhere, and did not review the draft).

I believe my suggestion is an improvement (but still needs caution; the checking if x^3+ax+b is a QR must be done in constant time, or in random time via blinding; I believe that in this case blinding is easier).

Now, I believe the issue is 'did Kevin endorse my suggestion, or did he endorse Dan's implementation?'
---------------------------------

Actually I had something more like the process outlined below in mind.  

First an elementary (and somewhat obscure)fact:

  For any prime p = 3 mod 4 and any non-zero f in Z/p, let 
            r = f**((p+1)/4).
  If f is a quadratic residue mod p (i.e. has a square root mod p),
  then r**2 = f, otherwise r**2 = -f.

(This is easy to see since 
             r**2 = f**((p+1)/2) mod p
                  = f * f**((p-1)/2) mod p
and f**((p-1)/2) = 1 mod p if f has a square root mod p and is 
-1 otherwise).  

Aside from cases of vanishingly small probability (e.g f = 0, 1 or -1),
the time to do this exponentiation  depends upon two publicly known 
values, the modulus p and the exponent ((p+1)/4), and not upon the secret 
values x and f.  I'd advise using Montgomery arithmetic as this is 
a very efficient and methodical technique for doing mod p arithmetic.

So what had I envisioned is something like this (in pythonese):

Bad = []
Good = []
for t in range(40):
    x  = one_way_update(x)
    f  = x**3 + a*x + b mod p
    r  = f**((p+1)/4)
    f1 = r**2
    if f1 == f:
        Good.append( (x,r) )
    else:
        Bad.append( (x,r) )

if len(Good) == 0:
    raise ValueError
else:
    return Good[0]


Observations:
 - This should be consant in time and memory usage.
 - Prob of hitting the error condition is 2**-40 ~= 10**-12.
 - The 40 could be increased if the RG deems that to be prudent.
  

Potential IPR issues:
Certicom has granted permission to the IETF to use the NIST curves, 
and at least two of these, P256 and P384, have p = 3 mod 4.  Not 
being a patent lawyer, I have no idea what impact the Certicom patents 
have on the use of newer families of curves, such as Edwards curves.  
RFC 6090 outlines elliptic curve technology which predates the Certicom
patents.