Primitives for NIST P-521

[alax]

Hey guys,

Here are the primitives for the NIST 521-bit curve, as taken from: http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf and http://www.secg.org/collateral/sec2_final.pdf

I have implemented this code into SJCL:

  c521: new sjcl.ecc.curve(
    sjcl.bn.prime.p521,
    "0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
    -3,
    "0x051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
    "0xC6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
    "0x11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650")

But it seems like the curve length is only 520 on the generated keys. Am I doing something wrong? There's a good chance I am just completely misunderstanding something as well. Thanks!

[alax]

Does anyone have any input on this?

[bitwiseshiftleft]

Hi Alax,

Sorry to be so slow in getting back to you. I haven’t had time to work on SJCL for a while, so I haven’t looked into the problem. However, it’s entirely possible that there’s a byte alignment issue, since of course 520 is a multiple of 8, but 520 is not. Most of the other code does not use non-byte-aligned bitfields, so the code paths aren’t very well tested.

Again, sorry, — Mike

On Nov 29, 2013, at 1:19 PM, Alax Villmann notifications@github.com wrote:

Does anyone have any input on this?

— Reply to this email directly or view it on GitHub.

[stbuehler]

Hi, I think the bug is in https://github.com/bitwiseshiftleft/sjcl/blob/master/core/bn.js#L355

All limbs but the most significant one should always be this.radix bits long, this should be completely unrelated to len (len is used for the partial length of the most significant limb, i.e. the first that is serialized).

[stbuehler]

I was wrong; although len shouldn't be used in that place, it actually is never smaller than this.radix, so it doesn't matter (removing it didn't break any tests).

var sjcl = require('./sjcl');
var i = new sjcl.bn.prime.p521(0);
console.log(sjcl.bitArray.bitLength(i.toBits()));

var r = new sjcl.bn("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409");
console.log(r.bitLength());

prints 528 twice; so perhaps @alax could clarfiy what the actual "problem" was - perhaps some code examples :)

[alax]

The only problem is that after adding the curve, I wasn't 100% sure I had done it correctly, with the curve length mismatch. I guess it makes sense, since the prime length is the same as well. Should I submit a pull request with the new code at this point? It seems that everything is in order.

[stbuehler]

[...] curve length is only 520 on the generated keys. [...]

how exactly did you get this "520"? I tried it myself (not just my snippet above, but your curve and generated real keys), and I only saw 528 in the data, not 520 (the _curvelength property is private anyway, and got renamed to s on my system).

And the prime length should actually be 521; 2^521 has 522 bits, and the prime is 2^521 - something, and should have length 521.

[alax]

Here's how I got to 520 for the curve length. First, generate the keys:

var crypto_keys = sjcl.ecc.elGamal.generateKeys(521);

Then output the public key with console.log(crypto_keys.pub), and you should see something like:

K: sjcl.ecc.point
get: function (){var a=this.K.toBits(),b=sjcl.bitArray.bitLength(a),e=sjcl.bitArray.bitSlice(a,0,b/2),a=sjcl.bitArray.bitSlice(a,b/2);return{x:e,y:a}}
k: sjcl.ecc.curve
q: 520
__proto__: Object

where q = 520. If you check the minified source (at least on my system), q maps to the _curveBitLength property of the basicKey object on line 335 in ecc.js. This is where my confusion stems from. Also, thanks for all the help!

[stbuehler]

Perhaps we need to specify the environment more closely to find the differences :)

current upstream git head:

$ git describe 
1.0.0-7-g59b0a67
$ ./configure --with-ecc
[...]
$ make
[...]
$ node testbn.js
There was an error collecting entropy from the browser:
{ toString: [Function],
  message: 'random: addEntropy only supports number, array of numbers or string' }
{ g: 
   { field: { [Function: c] modulus: [Object], fromBits: [Function] },
     r: { limbs: [Object] },
     a: { limbs: [Object] },
     b: { limbs: [Object] },
     G: 
      { x: [Object],
        y: [Object],
        isIdentity: false,
        curve: [Circular],
        X: [Object] } },
  k: 528,
  D: 
   { x: { limbs: [Object] },
     y: { limbs: [Object] },
     isIdentity: false,
     curve: 
      { field: [Object],
        r: [Object],
        a: [Object],
        b: [Object],
        G: [Object] } },
  get: [Function] }

using the following testbn.js

var sjcl = require('./sjcl');

sjcl.ecc.curves.c521 = new sjcl.ecc.curve(
    sjcl.bn.prime.p521,
    "0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
    -3,
    "0x051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
    "0xC6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
    "0x11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650");

var crypto_keys = sjcl.ecc.elGamal.generateKeys(521);
console.log(crypto_keys.pub);

I'm using nodejs 0.10.23~dfsg1-3 from debian (amd64).

[alax]

Sorry for the lack of updates on this; I have been busy with work and forgot to reply. Can someone far more knowledgeable than me tell me if the primitives are correct and SJCL functions as intended with them? I'd like to have full support for all of the NIST curves in SJCL, and as far as I can tell it looks correct, but I really have no way to verify that.

[Nilos]

I created a ticket to keep track of all curve addition requests here: #158 Closing this ticket for cleanness of backlog.