[ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures

[Jaguar0625]

And for completeness, these are the numbers I see for hoax's implementation:

Code:

Javascript needs 16.6ms/getPublicKey
Javascript needs 33.8ms/sign
Javascript needs 27ms/verify

It looks like I have a lot of catching up to do :/.

[Come-from-Beyond]

Since the Java code is producing deterministic signatures, I'm assuming you want the JavaScript port to have the same behavior?

If not, that would potentially open up other areas for optimization.

I want the same behavior.

[Come-from-Beyond]

Javascript needs 5.5ms/getPublicKey
Javascript needs 12ms/sign
Javascript needs 9.5ms/verify

So, who said that 10ms is impossible?

[hoax]

Javascript needs 5.5ms/getPublicKey
Javascript needs 12ms/sign
Javascript needs 9.5ms/verify

So, who said that 10ms is impossible?

We talk about 1ghz core?

But in overall, yes, i was too pessimistic
On my pc(core i5 2.67ghz) i now get 7.5ms(avg) for sign and 5.5ms(avg) for verify in Chrome

[hoax]

Thanks to Jaguar0625 for tests. I just runned my latest version(on github) on them, all tests are passed

[BloodyRookie]

Hmmm...chrome is indeed faster but even on a 3GHz maschine I don't get your results:

Code:

Javascript needs 12.22ms/getPublicKey
Javascript needs 26.24ms/sign
Javascript needs 21.18ms/verify

What am I doing wrong?

[gimre]

@gimre: On what kind of cpu r u testing, gimre?

laptop, i7, 2.2G

@Jaguar0625: 9.8ms/getPublicKey with javascript?

Yes, but don't worry, I ran your code too and it was faster . These are the results for your code on my machine (i am using the test js/html from your repo):

Code:

Javascript needs 5.5ms/getPublicKey
Javascript needs 12ms/sign
Javascript needs 9.5ms/verify

I suspect you're seeing slower numbers on your machine because you're testing in FireFox. AFAIK, Chrome has a faster JavaScript interpreter.

WOW, these look incredible!

[BloodyRookie]

@hoax: I don't think your version of is_negative is compatible with the java version, or is it?

Code:

/* checks if x is "negative", requires reduced input */
function is_negative(x)
{
    return x[0] & 0xFF >= 0x80;
}

[hoax]

Hmmm...chrome is indeed faster but even on a 3GHz maschine I don't get your results:

Code:

Javascript needs 12.22ms/getPublicKey
Javascript needs 26.24ms/sign
Javascript needs 21.18ms/verify

What am I doing wrong?

Hmmm...chrome is indeed faster but even on a 3GHz maschine I don't get your results:

Code:

Javascript needs 12.22ms/getPublicKey
Javascript needs 26.24ms/sign
Javascript needs 21.18ms/verify

What am I doing wrong?

Just runned in ff26: 22ms(avg)/sign 16ms(avg)/verify.

As i can see it depends on loop count(more loops - better time) and browser wish(sometimes it do everything slower(extensions, synchronization, etc??).

We should test everything in same environment I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations).

@hoax: I don't think your version of is_negative is compatible with the java version, or is it?

Code:

/* checks if x is "negative", requires reduced input */
function is_negative(x)
{
    return x[0] & 0xFF >= 0x80;
}

This check for overflow. Tested on Jaguar0625 tests(generated from Java) and get 100/100 passed, so... You can correct me if i'm wrong.

And you can remove in your sources second argument from

Code:

SHA256_write(m, m.length);

it was my copy-paste typo, sorry

[BloodyRookie]

@hoax: I don't think your version of is_negative is compatible with the java version, or is it?

Code:

/* checks if x is "negative", requires reduced input */
function is_negative(x)
{
    return x[0] & 0xFF >= 0x80;
}

This check for overflow. Tested on Jaguar0625 tests(generated from Java) and get 100/100 passed, so... You can correct me if i'm wrong.

Hmmm.....you didn't understand what I was trying to say, so here we go again.
Your code: is_negative(1) returns 0 (hopefully the & operator gets executed before >= operator).
Java code: is_negative(1) returns 1.

Since u use your is_negativ for both siging and verifying, it works.
But if u sign with your code and try to verify with the java code, it should fail sometimes (didn't test that but it really should fail).

[gimre]

My new results, I forgot to turn off miner when doing previous tests

chrom-opera:

Code:

curveSelfTest : ok
sign time: 25.000ms
verify time: 16.000ms
sign+verify time: 41.000ms
 verified?  true
doing 20 signs
sigs20: 396.000ms
doing 20 verifies
verify20: 307.000ms
true,true,true,true,true,true,true,true,false,true,true,true,true,false,true,true,true,false,true,false 

chrome:

Code:

curveSelfTest : ok
sign time: 25.000ms
verify time: 16.000ms
sign+verify time: 41.000ms
 verified?  true
doing 20 signs
sigs20: 396.000ms
doing 20 verifies
verify20: 307.000ms
true,true,true,true,true,true,true,true,false,true,true,true,true,false,true,true,true,false,true,false 

I don't think I'll get to anything better than that...

Also on what data do you operate inside functions?
As I find requirement, to take input as "hex strings" quite ugly.

P.S. My sign looks more or less like this:

Code:

function crypto_sign(privKey, messageHash)
{
	var pubAndS = this.c.genPubWithS(privKey);
	var sess = pubAndS.s;

	var x = SHA256(...);
	var Y = this.c.genPub(x).key;

	var h = SHA256(...);

	var vh = this.c.sign(h, x, sess);
	return {sig: vh, key: pubAndS.key};
}

[hoax]

Hmmm.....you didn't understand what I was trying to say, so here we go again.

You're right. Thank you. I've fixed it and will look at this closer again

[Jaguar0625]

We should test everything in same environment I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations).

Here are the latest numbers for hoax's code:

Code:

Javascript needs 3.6ms/getPublicKey
Javascript needs 6.9ms/sign
Javascript needs 7.8ms/verify

Nice job!

[hoax]

We should test everything in same environment I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations).

Here are the latest numbers for hoax's code:

Code:

Javascript needs 3.6ms/getPublicKey
Javascript needs 6.9ms/sign
Javascript needs 7.8ms/verify

Nice job!

Thank you

[gimre]

Something told me, to do tests on Jaguar's test set, and glad I did, cause I've found small bug in my implementation.

Here's my code, https://github.com/gimer/curve25519nxt
inside testing.js there are some simple tests along with Jaguar's tests.

It's based on objects rather than modules.

I doubt it'll beat hoax implementation though.

Here are some numbers, from my machine.

Code:

testCurveKeygen: 764.000ms
testCurveSign: 0.000ms
testCurveVerify: 1200.000ms
testCryptoKey: 703.000ms
testCryptoSign: 1498.000ms     (~~ 15ms/sign)

Oh, PS, also api is a bit strange, I'd find it more covenient if everything passed to JS would be wrapped in typed arrays already.

[gimre]

We should test everything in same environment I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations).

Here are the latest numbers for hoax's code:

Code:

Javascript needs 3.6ms/getPublicKey
Javascript needs 6.9ms/sign
Javascript needs 7.8ms/verify

Nice job!

Could I kindly ask you to run test also on my code?

[Jaguar0625]

Could I kindly ask you to run test also on my code?

Are the inputs and outputs of all of your functions byte arrays?

[Jaguar0625]

I was finally able to get rid of all the Long math and replace it from fast math functions from curve255.js and got much better results :

Code:

Javascript needs 6.9ms/getPublicKey
Javascript needs 13.4ms/sign
Javascript needs 10.7ms/verify

Still not as good as hoax's, but a lot better than my earlier numbers.

[gimre]

Could I kindly ask you to run test also on my code?

Are the inputs and outputs of all of your functions byte arrays?

almost, was it specified anywhere how input output should look like?

take a look at github, there's description of input output there.

[Come-from-Beyond]

almost, was it specified anywhere how input output should look like?

- Input/output values must be strings like "8302504e4e57c6c65335289879c6915a273d3aae7bd086058e403fcd2bc18341"