Cryptography Implementation Discussion

[Ipquarx]

async?

As in using schedules so to not lag the client. ECC requires at least 380 very expensive operations to be done... If we don't split it up it could lag the client pretty severely until it's finished. (This is for 192-bit security, for 128 bit security it's most likely significantly faster.)

Also I might have underestimated how long it'll take. With async it could take upwards of 10 seconds. I'll still try to improve things but if I can't then that's just what it is.

Pushed my changes. Modular multiplication is still ~7x slower than regular multiplication, if someone can make some improvements please do :v

[Ad Bot]

[Greek2me]

It looks like the speed will vary depending on which number is entered as %num1 and as %num2.

You could try unrolling the for loops, although it would probably only give negligible savings.

[Ipquarx]

Nah I can't really do that as I need it to work on numbers of all sizes. Can't do it without a ton of IF statements which would probably be slower. I have my own methods I think might work, I'll give them a try later.

I also really need to clean up/comment the code..

Regarding which number is entered as %num1 and %num2, I have no idea. I'll look into it.

[Gordo12699]

This encryptor also decrypts?

[Lugnut]

This encryptor also decrypts?

yes

[Greek2me]

I just discovered that somebody else wrote an RSA implementation in TorqueScript. Want me to ask for it so we can add it to Support_Cryptography?

[Ipquarx]

I just discovered that somebody else wrote an RSA implementation in TorqueScript. Want me to ask for it so we can add it to Support_Cryptography?

Absolutely! It would be nice to get some details on it though.

Just going to leave these test results here in case someone other than me finds them useful, they're tests on the time it takes to assign different things into local variables:

Number into variable:                 0.0361 µs
Global variable into variable:        0.0957 µs (2.7x slower)
String into variable:                 0.3958 µs (11x slower)
Local var. into local var.:           0.4703 µs (13x slower)
Script object variable into variable: 0.6387 µs (17.7x slower)

The results are probably off a good bit; I'll refine them further later on

EDIT2: Yup, they were a good bit off... I subtracted the time it takes for the loop itself to go through. Updated results.

[Ipquarx]

I think I've found a way to speed up the calculation of modulus on large numbers, the downside to it however is that we need a pre-computed table of values for the modulus multiplied by numbers below a power of 10. If that number is 1000 then I think I can speed it up to ~9ms, which would bring modular multiplication down from 40-70ms to a consistent 20. And I've still yet to make a final speedup on multiplication which could improve that by 16%.

That could very well work because the prime modulus we use won't be changing, so it only has to be computed once.

[Ipquarx]

Wish I didn't have to triple post here...

An update on everything.
I've made a bunch more progress with things, fixed all incorrect results and added in two remainder methods, one for remainder to a constant and remainder from any number.

The regular, two argument one takes around 20ms to calculate, and that probably isn't going to get much faster unless I really improve on multiplication somehow.

However, the one argument one only takes 7ms. This is because it is taking the modulus of a number to a constant. In this context that means that it uses a precomputed array of multiplications, 1-9999 to be exact, to eliminate the need for multiplication altogether.

The precomputing only takes a couple of seconds, and at over twice the speed it's definitely worth it for our purposes. I'll also be making multiplication by a constant, which will be used as well.

After all that is done, I can start implementing ECC.

For the record, multiplying two RSA sized numbers (2048 bit) takes a third of a second rather than 10ms. That won't work. We need to use ECC otherwise it's infeasible.

[Lugnut]

a third of a second really isn't that bad...
also, rsa doesn't work by multiplication, it works by modular exponentiation, so if you're gonna shoot rsa out then you kinda need to test the right thing
ecc was... what, 486 bits? 386? i don't remember the number. how fast is that computation (which DOES use raw multiplication)?

[Ipquarx]

a third of a second really isn't that bad...
also, rsa doesn't work by multiplication, it works by modular exponentiation, so if you're gonna shoot rsa out then you kinda need to test the right thing
ecc was... what, 486 bits? 386? i don't remember the number. how fast is that computation (which DOES use raw multiplication)?

Modular exponentiation is repeated modular squaring and multiplication. For a 2048-bit key (which is equivalent to 112-bits symmetric) that means 2048 modular multiplications which each take a third of a second. Even re-implementing optimized multiplication algorithms like Karatsuba wouldn't help at all.

Here are the current benchmarks for operations on ECC sized numbers (384-bit, providing 192-bits of symettric security; more than RSA):
Addition and subtraction: ~0.14MS (* 2 when modular because of the added subtraction)
Multiplication: ~9.8MS
Mod: ~6MS

And the raw security for an ECC key of b bits is 2^(b/2), so a 384 bit ECC key is the same as 192-bit, the same number that is allowed for use on top secret documents and more than what google uses. (128-bit)

[Lugnut]

okay.
i presume all these operations lock up blockland during their duration (which isn't neccesarily very long)

[Ipquarx]

okay.
i presume all these operations lock up blockland during their duration (which isn't neccesarily very long)

it's basically instantaneous. I had to let the functions repeat for 10+ seconds to get the accurate estimations.

Also, we still need some sort of symmetric encryption to actually send data with. Implementing AES in TS is entirely possible since we can use bit wise operators on the full uint32 range.
If anyone wants to take a crack at translating this working PHP code into TS: http://www.movable-type.co.uk/scripts/aes-php.html

[0xBRIANSMITH]

If anyone wants to take a crack at translating this working PHP code into TS: http://www.movable-type.co.uk/scripts/aes-php.html

PHP is virtually identical to TS.

[Lugnut]

it's not literally identical though

sooooo

still has work to be done. at least it's well commented