# How can I compute the theoretical total key-space for 521 bit elliptic curve ECDH private keys?

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

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?

• 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. Commented Apr 2, 2019 at 8:08
• 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. Commented Apr 3, 2019 at 1:56
• oops my bad, yes of course, i'll change out floats for ints now. i'll something about n. Commented Apr 4, 2019 at 7:57
The text passage contains multiple questions related to understanding and computing aspects of elliptic curve cryptography, including the theoretical total key-space for 521-bit elliptic curve ECDH private keys, a "dumbed down" example of an elliptic curve problem, and the relationship between key sizes in elliptic curve cryptography and RSA.
multiple_questions
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# How can I compute the theoretical total key-space for 521 bit elliptic curve ECDH private keys?

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

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?

• 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. Commented Apr 2, 2019 at 8:08
• 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. Commented Apr 3, 2019 at 1:56
• oops my bad, yes of course, i'll change out floats for ints now. i'll something about n. Commented Apr 4, 2019 at 7:57
user
The text passage contains multiple questions related to understanding and computing aspects of elliptic curve cryptography, including the theoretical total key-space for 521-bit elliptic curve ECDH private keys, a "dumbed down" example of an elliptic curve problem, and the relationship between key sizes in elliptic curve cryptography and RSA.

TYPE: MULTIPLE_QUESTIONS