/sci/ - Science & Math » Thread #13312076

123KiB, 820x567, ECC.png

View Same Google iqdb SauceNAO

Anonymous Tue 22 Jun 23:45:06 2021 No.13312076 View Reply Original Report

Quoted By: >>13312224

Can someone explain to me how to apply the discrete logarithm to elliptic curves? If I find a solution to the discrete log problem, how can I use that to crack Elliptic Curve Digital Signatures? I can see how they're similar in that the operate on groups, but I can't see how they would connect in application.

Any suggested reading would be much appreciated.

Anonymous

Anonymous Tue 22 Jun 2021 23:47:14 No.13312086 Report

Quoted By: >>13312121

im a math brainlet but im assuming if you can solve the elliptic curve using discreet logarithim then you can find where you are on the curve then then can predict the next number in the psuedo rng

Anonymous

Anonymous Tue 22 Jun 2021 23:57:49 No.13312121 Report

Quoted By: >>13312180

>>13312086
>if you can solve the elliptic curve using discreet logarithim
But this is exactly what I'm asking. I have read up on how points on an elliptic curve can be added/subtracted/multiplied by a constant, and thus multiplied by an exponentiated constant. But I don't see how finding x in a^x=b mod p is helpful with elliptic curves.

Anonymous

Anonymous Wed 23 Jun 2021 00:13:21 No.13312180 Report

Quoted By: >>13312317

>>13312121
you would have to collect data from stream of random numbers that the RNG is giving you, then apply the algorithm backwards, it's not a plug and chug solution

Anonymous

Anonymous Wed 23 Jun 2021 00:24:04 No.13312224 Report

Quoted By: >>13312317

>>13312076
Are you talking about ECDSA? https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
And what do you mean by cracking a signature?

Anonymous

Anonymous Wed 23 Jun 2021 00:44:19 No.13312317 Report

Quoted By: >>13312331

>>13312224
Yes ECDSA. I mean to find the private key from a known public key and elliptic curve/group.

>>13312180
What RNG are you talking about? What does RNG have to do with ECDSA or ECDLP?

Anonymous

Anonymous Wed 23 Jun 2021 00:47:10 No.13312331 Report

Quoted By: >>13312409

>>13312317
Look at the link I provided.
>d_A is the private key
>Q_A = d_A * G is the public key
>G is a public parameter
To find d_A just run your discrete log algorithm on Q_A and G

Anonymous

Anonymous Wed 23 Jun 2021 01:00:30 No.13312409 Report

Quoted By: >>13312501

>>13312331
I've visited this link before, forgive me if I don't read the entire thing again right now. The part I'm confused about is
>To find d_A just run your discrete log algorithm on Q_A and G

My supposed solution works on integers. Assuming I can find x in a^x=b mod p, all integers, p prime, with prime order. The problem is, what if my supposed solution algorithm uses operations on integers beyond the traditional operations of multiplying by a scalar, and adding other integers (or other points when using points)?

I'm asking because the way you and others talk is that all discrete log algorithms on integers can be directly altered to work on elliptic curve solution points.

Anonymous

Anonymous Wed 23 Jun 2021 01:19:52 No.13312501 Report

Quoted By:

>>13312409
Oh I see your confusion. Do you know about groups/rings?
Integers modulo p (for "normal" discrete log) form a ring, while points on an elliptic curve (for elliptic curve discrete log) also form a ring. Algorithms like Pohlig-Hellman or Baby Step Giant Step can be generalized to work for both rings.
a^x = b translates to A * x = B, where a, b are integers and A, B are points on an elliptic curve. So you replace "multiplication" with "point addition" and "exponentiation" with "point multiplication".

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches