1
$\begingroup$

Assume a dumbed down RSA: the private hey is $3 \times 5 = 15$. $3$ and $5$ are the private key and $15$ is the public key. To brute force it, find the two prime factors of $15$ ($3$ and $5$).

Is there a way to demonstrate a "dumbed down" elliptic curve / discrete log problem that I can compute by hand? I get the feeling that it has to do with integer points on a complex curve so how do I know the value of n assuming that refers to the number of integers in the set {1,..,n-1}?

Or to put another way - is there a smallest key size I can investigate to learn about brute forcing this formula. Performing countless log functions does sound quite CPU intensive.

Simple Curve Example

According to https://en.wikipedia.org/wiki/Elliptic_curve the region [−3,3] is a very simple curve where you get a nice "coat-hanger" with values of a=-2 and b=2

enter image description here Considering that:

"the private key is a random integer $d$ chosen from $\{1, \dots, n - > 1\}$ (where $n$ is the order of the subgroup)."... and also: "The Diffie-Hellman problem for elliptic curves is assumed to be a "hard" problem. It is believed to be as "hard" as the discrete logarithm problem, although no mathematical proofs are available. What we can tell for sure is that it can't be "harder", because solving the logarithm problem is a way of solving the Diffie-Hellman problem." Source: https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/

Or to put it another way, how can I prove this, or where did these numbers come from:

Another way is with RSA, which revolves around prime numbers. Most cryptocurrencies — Bitcoin and Ethereum included — use elliptic curves, because a 256-bit elliptic curve private key is just as secure as a 3072-bit RSA private key. Smaller keys are easier to manage and work with.Apr 7, 2018

Or... perhaps n not knowable for curves like Curve25519 for example?

$\endgroup$
  • 2
    $\begingroup$ I don't understand what you ask. The private key is an integer in {1,..,n-1}. So the key space is exactly n, which is known given a curve. $\endgroup$ – Ruggero Apr 2 at 8:08
  • $\begingroup$ Although mathematicians study elliptic curves over both real numbers (similar to computer floating-point) and finite sets like modular integers, cryptography uses only the latter, so no floating-point is involved. Although the identity (aka neutral) element is conventionally called the 'point at infinity', this is just an analogy and is not the infinity used for floating-point numbers. For why elliptic curve crypto is secure using a smaller keysize (fewer bits) than RSA or 'classic' DSA DH EG etc., there are at least 10s maybe 100s of Qs already; please do some research. $\endgroup$ – dave_thompson_085 Apr 3 at 1:56
  • $\begingroup$ oops my bad, yes of course, i'll change out floats for ints now. i'll something about n. $\endgroup$ – Tomachi Apr 4 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.