5
To compute $kG$ you need $O(log(k))$ operations. (For every bit, double the result and and additionally add $G$ if bit is $1$).
As you mentioned in a comment for around $k=1024$ you would need like $10$ operations to compute $kG$.
But this example is way to small for practical use and the exponential effect does not really kick in yet.
Normally, when the ...
5
In public-key cryptography, there is NO SUCH THING as "encrypt with private key". It's a misnomer since the RSA days.
Also, what you describe as "M = function(pubkey, signature)" is signature with message recovery. These algorithms are rare nowadays and had been largely replaced with signature with appendix (which ECDSA is one of them).
...
3
The answer is not so simple;
First of all the number of points that satisfy the curve equation $N$ on the curve is bounded by the Hasse's bound $$|N - (q+1)| \le 2 \sqrt{q}$$ for a prime $q$. This simply says that if you want a curve that has a large number of points then you need a big prime ( short story).
The curve order must be prime ( prime curves) or ...
3
I'm wondering what motivation or thought process might have led to the discovery in the first place. What properties do elliptic curves possess that make them resilient to attack?
Well, in the first place, Elliptic Curves were studied by mathematicians long before their use in cryptography was realized; I believe much of the foundational work was done in ...
2
What you are describing is Diffie-Hellman on some group with neutral PointInf() [hereafter noted $\infty$] and law add() [hereafter noted $\boxplus$]. The problem statement does not say which, but the title suggests an Elliptic Curve group over some finite field. Function mul(R, P) computes scalar multiplication $R\boxtimes P=\underbrace{P\boxplus \ldots\...
2
Can the multiplication of a point on curve with the scalar result in a point that is not on curve? There would be a case where you get the infinity point as result and which is not considered to be on the curve, but is there any other case?
No. Addition on points of elliptic curves with the point at infinity forms a group. Groups have to be closed, i.e. ...
2
For Edwards curves the arithmetic is typically implemented using Montgomery ladder, and the algorithm works both for the curve and its quadratic twist. (Note that for Weierstrass curves $y^2 = x^3 + ax + b$, the arithmetic formulas depends only on $a$ and so the algorithm works for a larger set of curves - arbitrary $b$).
This allows an adversary to send a ...
2
in my mind there must be other points that exist that still yield $y^2 \bmod p=x^3 + ax + b \bmod p$ to be true but are never used
Actually, that's not true if the order of the curve is prime; examples of such curves are P256 and Sec256k1. In those curves, every single point can be expressed as $xG$ for some integer $x$.
Now, this is (usually) not true for ...
1
I'm wondering what motivation or thought process might have led to (ECDSA)
ECDSA evolved from ElGamal signature. This was originally defined in the multiplicative group $\mathbb Z_p^*$ for prime $p$. This is somewhat similar to the multiplicative group $\mathbb Z_n^*$ for composite $n$ used by RSA. There was two separate evolutionary steps:
DSA (circa 1991)...
1
When choosing elliptic curve parameters, there is a lot of freedom. For the size of elements, the two parameters worth noting are the prime, $p$, and the embedding degree, $k$.
If $\mathbb{G}_1$ is an elliptic curve over $F_p$1, then $\mathbb{G}_2$ is an elliptic curve over $F_{p^k}$, and $\mathbb{G}_T$ is a subgroup of $F_{p^k}$.
So an elements of $\mathbb{...
1
Yes, this non-interactive zero-knowledge proof works perfectly fine (with a suitable hash function) for proving knowledge of a discrete logarithm over e.g. ed25519. The basis $G$ is part of the statement: the statement is of the form "I know $\alpha$ such that $Y = G^\alpha$. As such, it works for any generator $G$ of your choice (which, over ed25519, ...
1
In elliptic curve cryptography using Diffie-Hellman protocol we need to use large prime numbers.
More precisely
We usually use a curve with a generator which order is divisible by a large prime, because that gives insurance against the Pohlig-Hellman method to compute discrete logarithms.
We often make the generator of exactly that prime order, because we ...
1
If it does matter, what is the current state of the art elliptic curve and how does it compare with popular elliptic curves such as Curve25519 or secp256k1?
Well, if you have an elliptic curve with a large subgroup of size $q$ (which is prime), then we know how to compute a discrete log within that subgroup in $O(\sqrt{q})$ time, and this applies to all ...
Only top voted, non community-wiki answers of a minimum length are eligible
