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

[gimre]

My approach is a bit different, and I don't even have sign+verify yet. Will share results once I have some.

[hoax]

I think the speed could be improved a lot but it will take time.
What are you replacing the int10 and Long with?

Can you test my latest update?

I just posted a working version of the curve stuff here: https://github.com/Jaguar0625/JavaScriptNrs

I'm afraid that using Long class for all math isn't good. I think that better use Long only in mul and sqr functions. Then we can remove all unnecessary optimizations from Long class.

But fastest approach must forgive about Long class and use only JS-friendly math. I have working(and fast, more faster than latest version on github) sign function, but can't solve problems with verify, so continue my work.

[BloodyRookie]

Here is my implementation. Didn't optimize yet.

https://github.com/BloodyRookie/nxtCrypto/tree/master

Core duo 2.4GHz:

Test
message: This is a secret message that needs to be signed
secret phrase: This is my very secret phrase
public key: 698168d8669c9310d68101dfcc974ed4ef454692da6f028f68114db5fdcc4f6a
Signing...
Signature: 94956bf3de7cfdedb2562a0eff698fed7f3e54bbf4476fbb23a192ddea04040f68efa5d03c3f9eb ec4109401b50433f1df267299d8b1ad2c485046c45e6b38da
Verifying...
verify returned: true
Speed test
Javascript needs 35.7ms/getPublicKey
Javascript needs 77.1ms/sign
Javascript needs 73ms/verify
Finished

Edit: hoax, I test your latest version, it needs about 120ms/sign and 90ms/verify.

[hoax]

Yep, i also mean approach from https://github.com/kosta/confidential-publishing/blob/master/js/curve25519/curve25519.js

And your version of verifyalso return false for

Code:

var message = "Hello World!";
var secretPhrase = "secretPhrase";

[BloodyRookie]

Yep, i also mean approach from https://github.com/kosta/confidential-publishing/blob/master/js/curve25519/curve25519.js

And your version of verifyalso return false for

Code:

var message = "Hello World!";
var secretPhrase = "secretPhrase";

Interesting...
And the original Java code also returns false on verifying

[hoax]

Yep, i also mean approach from https://github.com/kosta/confidential-publishing/blob/master/js/curve25519/curve25519.js

And your version of verifyalso return false for

Code:

var message = "Hello World!";
var secretPhrase = "secretPhrase";

Interesting...
And the original Java code also returns false on verifying

Yep, just noticed that. Damn, i spend a lot of time for fixing wrong testcase!

Ok, but your verify also return false for:

Can you give some input and expected output?

Verification:
public key = "7c3ff12215636a7b246dea25d5e446a91fa59a9150c6ed50d8126ee86a648b68"
message = "0000a9d63800a0057c3ff12215636a7b246dea25d5e446a91fa59a9150c6ed50d8126ee86a648b6 87e2fad81dbf18f2da0860100640000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000"
signature = "4f0626ccd4edebb17e9d06e928b5b4e944aa7ef88a111081919794a3e265c206f9d9b0ce42a8d2e 7f6d902a172159bcd39dcaab8468373258fccea9e5d2ed319"
output = true

(The data from http://localhost:7874/nxt?requestType=getTransaction&transaction=14039483471941095190 and http://localhost:7874/nxt?requestType=getTransactionBytes&transaction=14039483471941095190)

Signing:

Similar, but take values from a transaction signed by ur account. This requires to reveal a secret phrase.

So, let's examine this approach further.

[Jaguar0625]

I just posted a working version of the curve stuff here: https://github.com/Jaguar0625/JavaScriptNrs

I'm afraid that using Long class for all math isn't good. I think that better use Long only in mul and sqr functions. Then we can remove all unnecessary optimizations from Long class.

But fastest approach must forgive about Long class and use only JS-friendly math. I have working(and fast, more faster than latest version on github) sign function, but can't solve problems with verify, so continue my work.

I have a few ideas about how to optimize the long class, but I need to spend time with a profiler first and see where all the time is being spent. Has anyone tried this already?

[Jaguar0625]

So, right now, I think there are three working implementations: hoax, me, BloodyRookie. Am I missing anyone? Has anyone compared the performance of all three?

[Jaguar0625]

Just an update from the other thread in case you missed it:

Regarding the performance criteria, are you referring to curve25519 or crypto operations per second? And, if you're looking for running this in the browser, what browsers are you looking at supporting? Considering curve25519's heavy reliance on 64-bit arithmetic (which JavaScript doesn't support natively), it will probably be a lot slower than you're expected (especially running outside of v8). Do you have test data you are using for a benchmark?

Crypto operations. Chrome. No test data, I'll take an ordinary payment transaction.

Also, are you giving the whole bounty to the fastest solution, or going to split it among functionally correct submissions?

The fastest submission will get (a part of) the bounty.

[BloodyRookie]

Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js, 16 bit arithmetic is used there. Doesn't have sign and verify though.

[BloodyRookie]

hoax, did you test the original cpp code? I tried but I got funny results

BTW: I think the bounty should be split among those who have a fast working version. Giving all nxt to one guy because his code is 1% faster doesn't make sense to me.

[gimre]

my Curve (not Crypto) times:
I was measuring time with console.time, console.timeEnd, not sure how precise it is...

x	chrom-opera 19	chrome 31	ff 26
public Without s	~35ms	~46ms	~68ms
public with s	~70ms	~70ms	~60ms
sign	~1ms	~1ms	~1ms
verify	~57ms	~72ms	~178ms

I still got some console.logs, which might tell why FF (last result) looks so bad. seems to me FF have pretty bad console handling.

Also it's not finished yet...

P.S. I'm amazed new opera has slightly better times > chrome, I thought they both use V8

edit out of curiosity, I've checked old opera (12.15)
2493ms, 2602ms, 3ms, 4264ms

[Jaguar0625]

Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js, 16 bit arithmetic is used there. Doesn't have sign and verify though.

Thanks for the link!

[Jaguar0625]

Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js, 16 bit arithmetic is used there. Doesn't have sign and verify though.

Thanks for the link!

Just as an FYI, I swapped my getPublicKey implementation for the one from the link you provided and I saw an improvement of ~15% (without any additional optimizations) with the test message you're using. But I am not seeing as great an improvement with the test set I generated.

[hoax]

hoax, did you test the original cpp code? I tried but I got funny results

Sources of what?

I have a few ideas about how to optimize the long class, but I need to spend time with a profiler first and see where all the time is being spent. Has anyone tried this already?

Look at my repo. I removed from Long all codepathsthat useless for long10 implementation. Also added multiplySmall, which faster when we multiple int64 by 1,2,4,9,19,38,76.

Maybe we can optimize further but with loss of readability or insignificantly

As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work.

[BloodyRookie]

Sources of what?

https://code.google.com/p/gvl/source/browse/crypt/curve25519.cpp?r=3c26171fd2d914484f03b7b63ca2065fa03a7aa3

As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work.

The only thing not working is the is_negative function, right?

[hoax]

Sources of what?

https://code.google.com/p/gvl/source/browse/crypt/curve25519.cpp?r=3c26171fd2d914484f03b7b63ca2065fa03a7aa3

My js ported directly from this, not from Nxt sources

And about "helloworld" false result: CfB said that this is normal behavior :O

As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work.

The only thing not working is the is_negative function, right?

Not only, as i can see.

[BloodyRookie]

My js ported directly from this, not from Nxt sources

ok, but did you actually test the c++ program?

The only thing not working is the is_negative function, right?

Not only, as i can see.

What else do you think is not working?

[gimre]

My code is finally working uff, took me a lot to figure out how to do that is_negative crap in my representation.

My current times:

Code:

 priv in:  210, 196, 255, 153, 6, 54, 138, 84, 232, 24, 222, 198, 233, 178, 192, 61, 46, 110, 249, 92, 37, 250, 62, 206, 16, 71, 242, 136, 153, 234, 194, 151, 
genPubWithS: 58.000ms 
    pub:  18, 173, 235, 164, 40, 128, 113, 104, 72, 242, 216, 5, 56, 18, 81, 45, 182, 177, 242, 122, 147, 174, 222, 226, 103, 224, 136, 35, 255, 173, 112, 52,
   sess:  74, 142, 86, 157, 36, 54, 116, 31, 195, 152, 94, 81, 151, 234, 6, 58, 52, 159, 55, 156, 194, 136, 214, 121, 86, 234, 144, 80, 73, 255, 6, 14,
msghash:  224, 94, 33, 147, 82, 148, 111, 121, 162, 115, 175, 49, 25, 9, 193, 102, 90, 114, 177, 246, 58, 178, 213, 252, 205, 21, 160, 52, 210, 239, 202, 17,
genPub: 30.000ms
      x:  56, 202, 26, 238, 143, 109, 13, 46, 68, 242, 230, 144, 117, 26, 35, 82, 185, 104, 189, 171, 185, 231, 219, 160, 226, 15, 25, 173, 12, 47, 149, 72,
      Y:  255, 86, 46, 149, 26, 72, 141, 90, 42, 124, 209, 211, 33, 126, 7, 149, 222, 249, 90, 197, 87, 173, 210, 15, 153, 198, 14, 116, 91, 27, 139, 99,
signing:
    sha:  77, 170, 60, 190, 71, 254, 202, 56, 39, 211, 119, 32, 153, 190, 64, 97, 46, 28, 8, 115, 115, 149, 16, 121, 182, 69, 186, 159, 37, 229, 120, 65,
sign: 0.000ms
  vh[0]:  38, 92, 148, 183, 122, 6, 174, 55, 94, 129, 218, 168, 118, 156, 21, 98, 10, 23, 24, 244, 169, 75, 62, 154, 5, 88, 16, 114, 241, 17, 201, 1, 
  vh[1]:  77, 170, 60, 190, 71, 254, 202, 56, 39, 211, 119, 32, 153, 190, 64, 97, 46, 28, 8, 115, 115, 149, 16, 121, 182, 69, 186, 159, 37, 229, 120, 65,
verify: 49.000ms
 hashing sig:  255, 86, 46, 149, 26, 72, 141, 90, 42, 124, 209, 211, 33, 126, 7, 149, 222, 249, 90, 197, 87, 173, 210, 15, 153, 198, 14, 116, 91, 27, 139, 99,
h_verify:  77, 170, 60, 190, 71, 254, 202, 56, 39, 211, 119, 32, 153, 190, 64, 97, 46, 28, 8, 115, 115, 149, 16, 121, 182, 69, 186, 159, 37, 229, 120, 65,
 verification =?= vh[1]:
ALL TIME: 160.000ms 

Code:

 priv in:  212, 215, 120, 183, 50, 2, 38, 73, 6, 176, 105, 222, 132, 202, 18, 161, 165, 186, 129, 60, 222, 69, 25, 30, 201, 220, 102, 201, 246, 118, 112, 127, 
genPubWithS: 62.000ms
    pub:  223, 120, 104, 231, 254, 142, 4, 197, 103, 120, 80, 42, 121, 163, 172, 175, 112, 183, 92, 53, 174, 174, 106, 175, 52, 132, 33, 254, 147, 202, 189, 89,
   sess:  1, 235, 206, 226, 194, 0, 108, 59, 21, 56, 112, 230, 43, 5, 58, 166, 186, 14, 192, 10, 136, 169, 0, 168, 141, 157, 253, 109, 92, 164, 141, 6,
msghash:  224, 94, 33, 147, 82, 148, 111, 121, 162, 115, 175, 49, 25, 9, 193, 102, 90, 114, 177, 246, 58, 178, 213, 252, 205, 21, 160, 52, 210, 239, 202, 17,
genPub: 31.000ms
      x:  160, 134, 16, 204, 227, 72, 60, 80, 61, 72, 20, 184, 27, 50, 91, 144, 58, 143, 93, 94, 182, 218, 63, 185, 180, 103, 235, 92, 143, 69, 250, 90,
      Y:  25, 68, 99, 3, 220, 120, 0, 254, 135, 235, 145, 49, 33, 175, 178, 51, 85, 109, 83, 123, 79, 242, 47, 246, 21, 239, 130, 81, 185, 235, 67, 122,
signing:
    sha:  49, 103, 140, 21, 153, 144, 6, 45, 72, 166, 26, 232, 129, 182, 10, 195, 121, 74, 78, 165, 215, 241, 27, 222, 250, 58, 48, 194, 134, 161, 137, 176,
sign: 1.000ms 
  vh[0]:  89, 34, 99, 164, 248, 105, 148, 205, 219, 19, 132, 9, 153, 239, 28, 161, 205, 194, 27, 242, 214, 227, 85, 241, 251, 224, 148, 72, 150, 64, 18, 15, 
  vh[1]:  49, 103, 140, 21, 153, 144, 6, 45, 72, 166, 26, 232, 129, 182, 10, 195, 121, 74, 78, 165, 215, 241, 27, 222, 250, 58, 48, 194, 134, 161, 137, 176, 
verify: 50.000ms 
 hashing sig:  25, 68, 99, 3, 220, 120, 0, 254, 135, 235, 145, 49, 33, 175, 178, 51, 85, 109, 83, 123, 79, 242, 47, 246, 21, 239, 130, 81, 185, 235, 67, 122, 
h_verify:  49, 103, 140, 21, 153, 144, 6, 45, 72, 166, 26, 232, 129, 182, 10, 195, 121, 74, 78, 165, 215, 241, 27, 222, 250, 58, 48, 194, 134, 161, 137, 176, 
 verification =?= vh[1]:
ALL TIME: 168.000ms

Is that fast or slow?

(above I'm doing equivalent of java code):

Code:

Curve25519.keygen(pub,sigPriv,priv); // generate pub and sigPriv  // time1
..
Curve25519.keygen(sigPub, null, sigPriv); // generate sigPub from sigPriv  // time2   
..
Curve25519.sign(v, hash1, hash2, sigPriv); // return (v, hash1) as a sig   // time3

Curve25519.verify(Y, v, hash1, pub); // generate Y  // time4
hash(hash(message)+Y) == hash1

)

[Jaguar0625]

hoax, did you test the original cpp code? I tried but I got funny results

I wouldn't be shocked if there is a bug in the Java code. Cfb's expectation that ~25% of signatures can't be verified is surprising to me. Also, the fact that the C++ code is using uint8 types whereas the JavaScript code is using longs for essentially the same thing is suspicious.