Questions tagged [elliptic-curves]
Elliptic curves are algebraic-geometric structures with applications in cryptography. Such a curve consists of the set of solutions to a cubic equation over a finite field equipped with a group operation. Questions relating to elliptic curves and derived algorithms should use this tag and might also consider more specific tags such as discrete-logarithm and ecdsa.
1,859
questions
1
vote
1
answer
50
views
ECC Range proof
In ECC, the proof showing that given $G$, $x$ and $y$ is in the range $[-z,z]$ is known as the range proof.
Related to: Proving that two points on elliptic curve are within range
So, if:
$$H=xG−yG$$
...
1
vote
2
answers
52
views
How to expand elliptic curve public key from compressed form?
Following this page https://en.bitcoin.it/wiki/Secp256k1, secp256k1 curve's equation is
$$y^2=x^3+7$$
Does this mean that I can substitute $G_x$ in the equation to get $G_y$?
I think yes and that's ...
- 13
1
vote
1
answer
84
views
Addition on elliptic curves on finite fields: what if X_1 = X_2 and Y_1 != Y_2?
Given the following curve:
$$ y^3 = x^2 - 7x $$
over the finite field $GF(271)$.
We have $P = (201, 247)$ belongs to the curve:
$$ 247^2 \equiv 201^3 - 7 \cdot 201 \equiv 34 \mod 271 $$
We also have $...
- 115
-1
votes
1
answer
36
views
The benefit of the shared key generated from ECDH key exchange protocol [duplicate]
What the benefit of the shared key that generated from ECDH key exchange protocol?
Can I use it to encrypt the message or encrypt the public key of asymmetric encryption?
3
votes
2
answers
128
views
Isomorphism of Curve25519 and Ed25519?
According to this page, Curve25519 and Ed25519 are not isomorphic, because the birational equivalence equation has singularities:
What does "birational equivalence" mean in a cryptographic ...
- 2,214
2
votes
2
answers
71
views
Is it possible to calculate the modular inverse of a secp256k1 public key?
I know that it wouldn't be possible to use the extended Euclidean algorithm, since it would require the ability to divide a public key and calculate the remainder. I was wondering if there were any ...
- 21
1
vote
1
answer
52
views
How to do addition in Montgomery form?
I'm trying to do ECDSA signing, and I need to compute
$$\left(k^{-1} \bmod n \cdot (m + d\cdot r) \bmod n\right) \bmod n$$
I'm able to do the inverse function and multiplication in Montgomery form, ...
- 13
1
vote
1
answer
52
views
Working with Paillier and ECDSA - Order issue
I'm trying to implement two party computation for ECDSA signing using Paillier cryptosystem.
But my problem is that the order of Paillier is different from the order of the curve (secp256k1 in my case)...
- 113
1
vote
0
answers
28
views
How is point addition for points of elliptic curve in $\mathbb{F}_p$ carried out technically? [duplicate]
From a very basic introduction text to elliptic curve cryptography point arithmetic is derived from "standard analysis": The (negative) sum of $P_1$ and $P_2$ is defined as the Point $P_3$, ...
- 1,447
1
vote
0
answers
58
views
Minimal, secure and reasonably efficient P384 implementations
For a project I'm working on, I need to implement ECDSA over the NIST P-384 curve (AKA secp384r1). For what it's worth, the choice of curve is beyond my control in ...
- 111
1
vote
2
answers
57
views
How to safely and randomly iterate a key derived from Scrypt?
I'm developing a way to deterministically generate private keys for arbitrary elliptic curves based on some user-input (a brain-wallet). Currently, I'm using the Scrypt password hashing algorithm with ...
- 13
1
vote
0
answers
35
views
Implementation size of post quantum schemes
I was comparing classical schemes with post-quantum schemes. Therefore I was interested in the round three candidates of the NIST standardization process. So far I know, that those post-quantum ...
- 1,492
0
votes
0
answers
43
views
Paper that specifies how to define number ranges inside the ECC with varying equations
I am looking for a textbook or published paper that provides specific information on how to configure an ECC. I came across it several years ago and now cannot find it. Does anyone know the source? ...
- 27
1
vote
0
answers
32
views
What’s the relationship between P-256 and Dual EC DRBG?
It is said that Dual EC DRBG has a backdoor given the values of the curve. Hence some people do not trust it.
With that in mind, some people also distrust NIST P-256 Curve. Why? Is it purely because ...
1
vote
1
answer
77
views
Distribution of elliptic curves with rank 2?
An elliptic curve defined over a finite field is either cyclic, or a direct sum of two cyclic groups. In cryptography, we use exclusively the former. I was wondering if there is any result on how ...
- 89
0
votes
1
answer
70
views
Can form of elliptic curve digital signature equation be simpler?
I am curious why equations for signing/validating with ECDSA have forms they have. Is it possible to use simpler equation that have same properties.
For example, this is an equation I found in the ...
1
vote
2
answers
304
views
Elliptic Curve - distinguish between two points after multiplication
If $P$ and $Q$ are two points on an elliptic curve of large prime order, given $P, Q$, and a point $R$ which is either (a) $nP$ or (b) $nQ$, is it possible to determine if $R$ is of form (a) or form (...
- 11
1
vote
1
answer
58
views
Schnorr based ZK scheme
TL;DR: This ABSOLUTELY does not work and presents a huge security risk. Posting it anyways in case there are other threats I missed or to dissuade any other person who comes up with this idea.
Hi! I’m ...
1
vote
0
answers
24
views
What is an advantage of the Charles--Lauter--Goren hash function?
What is an advantage of the Charles--Lauter--Goren hash function (based on isogenies of elliptic curves) among other provably secure collision-resistance hash functions ? I heard that it is slower.
- 175
4
votes
1
answer
126
views
If a curve $E/\mathbb{F}_q$ is secure, what can be said about $E/\mathbb{F}_{q^2}$
Let $E$ be a known, "secure" curve, defined over a field $\mathbb{F}_q$ where $q$ is either a prime $\geq 5$ or a power of $2$. Denote by $n$ the amount of rational points of $E$.
Consider $...
- 89
1
vote
0
answers
55
views
Can we solve the ECC DLP if we can distinguish whether the doubling of a public key is accompanied by reduction (modulo n) or not?
Let $E$ be an elliptic curve over a prime or a binary extension field $GF(2^m)$, and let $G(x_g,y_g)$ be a generator point on the curve. Let $Q$ be an arbitrary point $Q = r*G$, with $r$ scalar, and $...
- 115
3
votes
1
answer
141
views
Strauss-Shamir trick on EC multiplication by scalar
I'm studying ECDSA, and almost all somewhat detailed articles talk about using Strauss-Shamir trick on the verification step.
Then I searched, and found this explanation (more like a stating) for the ...
- 33
2
votes
1
answer
114
views
Curve448 - Can Ed448 key material be reused for X448?
Currently I am facing a situation in which Ed448 key pairs (private + public key) are available and the system should be extended by a Diffie-Hellman (ECDH) operation. First of let me summarize what I ...
- 23
1
vote
0
answers
26
views
Differing result between doubling and addition in extended twisted Edwards coordinates [closed]
While coding for Edwards curve, I noticed that, the addition formula and the doubling formula return what seems to be different result.
I took the adding and doubling formula from both RFC-8032 and ...
- 6,621
5
votes
1
answer
1k
views
Can there be identical elliptic curve groups of points from different irreducible polynomials in binary extension fields?
Let $E$ be an elliptic curve over a binary extension field $GF(2^m)$, with constructing polynomial $f(z)$ be an irreducible, primitive polynomial over $GF(2)$, and let $G(x_g,y_g)$ be a generator ...
- 115
0
votes
0
answers
49
views
Comparing the performance of ECC/RSA with post quantum protocols
I wanted to compare the performance of different cryptographic systems. There is a pretty good paper comparing the 3rd round finalists of the NIST competition.
I was wondering if there are good ...
- 1,492
0
votes
0
answers
26
views
Multiplicities of poles of a divisor of a rational function w.r.t. an elliptic curve
I am reading Sec 5.8.2 in the textbook Introduction to Mathematical Cryptology (Hoffstein, Pipher and Silverman), a precursor to introducing the structure of Weil pairing. It first defines a rational ...
- 249
4
votes
3
answers
644
views
Do you know protocols, where it is necessary to obtain several "independent" points on the same elliptic curve?
Consider an elliptic curve $E$ defined over a finite field $\mathbb{F}_{\!q}$ with a fixed non-zero $\mathbb{F}_{\!q}$-point $P$. For simplicity, let the order of the $\mathbb{F}_{\!q}$-point group $E(...
- 175
1
vote
1
answer
73
views
Test vectors (points) for Ed25519
I am trying to verify an Ed25519 implementation, but I can't find any test vectors for the curve points. All test vectors focus directly on signature constructions (EdDSA).
I tried to use https://...
- 1,615
3
votes
1
answer
308
views
Is it theoretically possible to delegate public key generation?
Imagine the following scenario:
In a given cryptocurrency, privacy should be as high as possible.
For this purpose, a new account with a new address is created for every incoming transaction (the ...
1
vote
0
answers
28
views
Developing a Simmetric Key Distribution protocol to use with rfc6238
I'm trying to develop a Key Distribution Protocol to share symmetric keys in RFC 6238 (OTP).
I started with RFC 6063, but this protocol is developed over old and known insecure algorithms like PBKDF ...
6
votes
2
answers
3k
views
EC Public key encryption scheme where Alice does not know Bob's public key
I've found ECDH and ECIES, but those both require Alice to know Bob's public key and Bob to know Alice's public key in order to derive a shared secret.
Now assume Bob knows Alice's public key $A$, but ...
- 217
1
vote
1
answer
64
views
Order of point on elliptic curve vs order of base field
I'm looking at the FIPS-186 standard. On page 88, it gives a table recommending the size of the base field for the elliptic curve versus the order $n$ of a point on the curve. The numbers don't seem ...
3
votes
1
answer
94
views
Whats the reason for using elliptic curves of order |E| = fr
To be more precise, in the books I sometimes see that they just require you that the order of your elliptic curve is $|E| = fr$, where $f$ is some small integer with possible factors, but $r$ is a ...
- 239
2
votes
1
answer
130
views
Generating and validating a signature with ED25519 expanded private key
I am building a encrypted messaging app over tor network and currently I'm struggling on using tor generated ed25519 private key to sign and verify any message.
Below piece of code works with a 32 ...
- 21
1
vote
0
answers
31
views
Verifiable Base Point generation via NIST SP 800-186 method
I'm looking at D.3.2 Verifiably Random Base Points of NIST SP 800-186. Looks like step 5 is there to ensure that $hashlen > bitLen(q)+1$ and (potentially) discard big $e$, so $t$ is distributed ...
- 400
1
vote
1
answer
88
views
P256 seed problem
I'm reading up on elliptic curves and their history and it seems that people don't trust P256 seed which is defined in FIPS 186-3 on page 89 to be
SEED = c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
...
- 11
1
vote
1
answer
270
views
What is the order of the generator point G=9 in curve25519?
In Curve25519 we typically have this generator point or base point:
...
- 1,315
2
votes
1
answer
322
views
Can I generate two similar ECDSA public keys?
I am using a system that relies on base64 encoded ECDSA public keys.
I have managed to brute-force a public key that when encoded starts with a word I like.
Is it possible for me, given the private ...
- 23
0
votes
0
answers
70
views
EC ElGamal multiplicatively Homomorphic
Can we make EC ElGamal have multiplicative homomorphic property?
- 1
2
votes
0
answers
46
views
ECDSA adaptor signing and decryption
I am trying to understand this article. Can someone explain to me how the ECDSA adaptor signing is work?
From the article:
1.
ECDSA adaptor signing
$$s' = (H(m) + R t p)r^{-1}$$
As I understand this ...
- 21
0
votes
1
answer
27
views
EC cardinality $P^3+c$ with 3 gen $G$, $F = P\cdot G,H=P^2\cdot G$ and 2 random members $M_1+iG+jF+kH=M_2$. How long would it take to find $i,j,k$?
Given a EC with cardinality $C=P^3+c$ with $P$ a prime $P \approx \sqrt[3]{C}$ and $c>0$.
Out of a given generator $G$ we generate two additional generator $F,H$ with
$$F = P \cdot G$$
$$H = P^2 \...
- 475
0
votes
1
answer
57
views
Practical check the point is on the Curve [duplicate]
The curve I am using is secp256r1. Its formulae is
$y^2 == x^3 + a\cdot x + b$
$a$ = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc (...
- 21
2
votes
1
answer
37
views
Random Generation a Valid Scalar on the Chosen Curve
My implementation requires me to generate randomly a valid scalar on the curve. As far as I understand it is not a random number generation but more complicated thing.
I have to generate such scalars ...
- 21
0
votes
0
answers
42
views
Elliptic Curve Encryption [duplicate]
I know about ECDH when you need 2 pairs of public/private keys.
But I wonder what is a simplest way to encrypt with just single public key?
Should I select a second random pair of public/private keys ...
- 136
1
vote
1
answer
53
views
Embedding degree of curves of characteristic 2 and ECDLP transfer
It is known that we can transfer an ECDLP instance on a curve $E$ defined over $\mathbb{F}_p$ for prime $p$, to a discrete-log instance in $\mathbb{F}_{p^k}$ for some $k$. It is referred to as the ...
- 47
0
votes
0
answers
41
views
EC NIST P-256 FIPS-186-4 B.5.1 Per-Message Secret Number Generation Using Extra Random Bits operation
I need to implement following operation:
w = (z mod (n-1)) + 1
where
z: 40-byte array
n: the order n of base point defined for NIST P-256.
I assume that resulted 'w' could be a point on the curve.
Any ...
- 21
1
vote
0
answers
85
views
Invalid point attack yields wrong results for low order points
I've recently tried to replicate the results of the question Ruggero asked and which Samuel Neves answered here: Understanding Twist Security with respect to short Weierstrass curves
In my attempt to ...
1
vote
0
answers
73
views
"Add" points that are not on the same elliptic curve?
Assume elliptic curve in Weierstrass form.
$y^2 = x^3 + a x + b$ where $x,y,a,b \in F$
I noticed the point addition formula does not involve parameters $a,b$.
Furthermore, one can always solve for $a,...
- 121
0
votes
0
answers
13
views
Distributing the Master Public Key in Identity-based Encryption systems
I was just wondering how the private key generator should publish the master public key inside of an IBE system. This key is needed for all devices in the network to derive the public key of receiving ...
