multiplication speed problem

[hamnaz]

here i love to share info

12million lines read and write takes 5 min maximum

Point Addition

R = S + T

12million lines read and write takes 5 min maximum

Point Subtraction: (xs, ys) - (xt, yt) = (xs, ys) + (xt, -yt)

R = S - T

12million lines read and write takes 5 min maximum

Point Doubling

R = S + S # produces the same value as the operation below

12million lines read and write takes 3 hours 13 min R = 2 S # S 2 works fine too i.e. order doesn't matter

*12million lines read and write takes 3hours to 4 hours where ever i use in calc **

d = 0xc51e4753afdec1e6b6c6a5b992f43f8dd0c7a8933072708b6522468b2ffb06fd

Scalar Multiplication

R = d S # S d works fine too i.e. order doesn't matter

e = 0xd37f628ece72a462f0145cbefe3f0b355ee8332d37acdd83a358016aea029db7

Joint Scalar Multiplication

R = d S + e T

pls correct this problem where 3 to 4 hours take for point to point (scalar) multiplication Thankx

[AntonKueltz]

Can you please clean up the formatting in the issue? It's currently difficult to read and figure out what the actual issue is. Is the issue that you're noticing that point multiplication is a lot slower than point addition? (If so, that's a known characteristic of EC groups, since point multiplication requires lots of additions and doublings).

[hamnaz]

i mean point + point for 12 million line like for i in range (0, 12000000), max time for process is 5 min when we use point * 123456789 same loop for 12 million lines, its take couple of hours

[AntonKueltz]

I'll have to run the actual numbers to see if there's a problem here as far as expected runtime vs actual runtime. My initial comment is that multiplication in this package uses the Montgomery ladder, which requires a point addition and point doubling for each bit of the secret key. So I would expect point multiplication to take about 2 * log_2(q) times longer than point addition when performed on the same curve (where q is the order of the curve). I'll follow up with whether or not this aligns with the values you're observing.

[hamnaz]

could you write email , where i send 2 scripts, you can test

[hamnaz]

your email address ?

[EggPool]

@hamnaz please don't spam the issues. Anton answered with great details and said he will follow up. Just be patient.

[hamnaz]

ok thankx

[AntonKueltz]

Sorry, I'm not in the habit of giving out my email so that folks can send me arbitrary scripts to run, call it a quirk of being a security guy. I did verify that this behavior is consistent with what would be expected -

• 5 min to run 12_000_000 point additions
• The smallest q in the common published curve parameters is 192 bits
• If we're multiplying by a randomly sampled value in the range [0, q] we'll expect it to be 191 bits
• Multiplication takes a factor of 2 * log_2(scalar_multiplier) = 2 * 191 = 382 times longer than addition
• 5 * 382 =1910 minutes or about 30 hours

So actually your metrics are much lower for multiplication than would be expected. So I suspect you're using smaller multipliers which yield faster times, which implies something like trying 0, 1, 2, ... or basically some kind of brute force. If you're trying to brute force a curve with reasonable parameters you're wasting your time, no ECC library is fast enough to do this, that's part of the security assumptions underlying ECC.

[hamnaz]

point to point multiplication possible ? 2nd if you see https://github.com/Telariust/pollard-kangaroo here ver 1, useing simple python and runnign were at 15k, and in next ver , he used import gmpy2, and speed boost to 390k, mostly around i see after apply gmpy2, speed bosst to 30 times to 50 times faster,

[AntonKueltz]

You can’t multiply a point by a point, multiplication in an EC group is only defined between a point and a scalar.

Pollard’s Kangaroo algorithm is not part of this package, it’s for performing index calculus i.e. solving ECDLP. And yes it’s faster than brute force. But it still won’t solve ECDLP for EC parameters large enough to be suitable for cryptography.

I’m closing this topic as this seems to be about the fact that this package isn’t fast enough to brute force ECDLP.