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.

Filter by
Sorted by
Tagged with
1
vote
0answers
57 views

Calculating ECDSA Private Key From Multiple Signatures With Shared k (random nonce)

I've been experimenting with ECDSA signatures and with how the Sony PS3 private key was leaked. Specifically where: $$k = \frac{z_1 - z_2}{s_1 - s_2}$$ $$d_A = \frac{z_1s_2 - z_2s_1}{k(s_1 - s_2)}$$ ...
0
votes
0answers
49 views

what it means by A dot B yields C in Elliptic Curve Cryptography?

I don't understand what the dot notation is. Is it like a multiplication operation or an addition operation or what? and how is that related to the Elliptic Curve Discrete Logarithm Problem? For ...
1
vote
1answer
23 views

ecdsa nonce reuse to compute the private key, modular inverse question

I am following along some cryptography challenges:, in particular ECDSA Nonce Reuse here (second problem): https://blog.coinbase.com/capture-the-coin-cryptography-category-solutions-fe94d82165c5 I ...
0
votes
1answer
233 views

Can I use ECC for encryption/decryption, just like RSA? [duplicate]

I'm familiar with RSA for asymmetric encryption. I also understand it's only supposed to encrypt small amounts of data (smaller than the key) so for encrypting arbitrary data I would typically ...
5
votes
1answer
924 views

Generating a random point on an elliptic curve over a finite field

I have coded an implementation of elliptic curves in order to apply some of the ECC algorithms. However, in most of them, Alice needs to choose a point P on a given curve. What is the general ...
4
votes
0answers
69 views

secp256k1 scalar decomposing and prime field arithmetic

I'm currently studying the elliptic curve secp256k1 implementation. In my understanding, it has efficiently computable endomorphisms: We can find out a pair of number $\lambda$ and $\beta$ from the ...
0
votes
1answer
84 views

CSIDH Squaring Fixing the Base Curve

Consider the following variants of the CSIDH squaring problem. P1. Given $sE, E$ where $s$ is a random ideal class and $E$ is a random curve (reachable from initial $E_0$), find $s^2E$ P2. Given $sE_0$...
2
votes
1answer
109 views

How is a generator found for a group, both in case of DH & ECDH?

First step in DH & ECDH is to choose a random prime $p$. Then you choose a generator $g$ for the group $\mathbb Z_p^*$. How do you find a generator? Likewise in ECDH, you would need to find a ...
0
votes
1answer
134 views
+50

Homomorphic mapping between elliptic curve point and Zq

I'm trying to figure out how to do a mapping between elliptic curve points and Zq without breaking homomorphic properties. Sorry, I'll write the problem in multiplicative notation because it's easier. ...
0
votes
0answers
45 views

Generate Keypair with PKCS11 on curve secp256r1 and sign with it [migrated]

I'm trying to generate an EC-Keypair with PKCS11 on SoftHSM2 with "github.com/miekg/pkcs11" I got curve-parameters from here: https://github.com/ANSSI-FR/libecc/blob/master/src/curves/known/...
4
votes
3answers
61 views

Is it secure to compute the exponentiation and the LWE operation?

Suppose Alice and Bob have specified an elliptic curve, for example, secp256k1. Alice has a secret number $s$ (can be seen as secret key), Bob choose a point $g$ on the curve and send it to Alice. ...
0
votes
2answers
64 views

Wrong key length for EC public key

I have a problem with EC public key reading from smartcard using pkcs11 library. With the secp256r1 EC algorithm, I always get 65 or 67-byte length public key with different smartcards. But with the ...
6
votes
1answer
358 views

Is there any reason not to use EdDSA with Weierstrass curves?

I'm volunterely working for a crypto library and we're planning on adding Curve25519 support (finally). At the same point I had the idea of adding support for EdDSA in the same run. Our library is ...
7
votes
1answer
186 views

ECIES vs. RSA + AES

I am confused about the distinction between RSA and ECC (Elliptic curve) regarding encryption and would appreciate it if someone could confirm whether my understanding is correct. To encrypt a large ...
1
vote
1answer
40 views

Is prime order group used in ECDSA unique?

In ECDSA, we use a prime order group $\langle G\rangle$ for cryptographical use. Assume $\#\langle G\rangle = p$. Is there another subgroup in the curve used for ECDSA whose order is also $p$?
0
votes
1answer
63 views

What are the extended homogeneous coordinates in the EdDSA specification?

According to the EdDSA specification from the IETF: For point addition, the following method is recommended. A point (x,y) is represented in extended homogeneous coordinates (X, Y, Z, T), with x = X/...
16
votes
3answers
2k views

What does the special form of the base point of secp256k1 allow?

The popular ECC parameters secp256k1 are documented in SEC2 as using curve $y^2\equiv x^3+a\cdot x+b\pmod p$ with $a=0$, $b=7$, $p=2^{256}-2^{32}-\mathtt{3d1_h}$, base point $G$ with the apparently ...
3
votes
2answers
250 views

Can you compress an elliptic curve private key in half?

According to this, an $n$-bit key offers about $n/2$ bits of security. That got me wondering, can you compress the key in half? At first blush, no, because the key is essentially a random number, and ...
1
vote
1answer
114 views

Find Consecutive X-Coordinate algorithm

The question is as follows: Is there an algorithm to calculate a $(x,y)$ pair which is consecutive to an existing $x$-Coordinate on an elliptic curve? Background Information for the curve: Known ...
2
votes
3answers
62 views

Can schnorr-signatures be used to ensure public keys are of the correct form (namely $Y= x \cdot G$)?

Assume a Schnorr-signature scheme in an elliptic curve setting with a publicly known generator base point $G$ where the the discrete logarithm is hard. That is, given $x \cdot G$, it is hard to find $...
8
votes
1answer
439 views

What are the characteristics of a quantum secure protocol?

What are the characteristics of quantum secure protocol, and does it always need to be information theoretic to be called as quantum secure? Are the current techniques used in bitcoins quantum secure?
5
votes
1answer
642 views

EdDSA Signature Algorithm - hash of secret key

Why does EdDSA use the (SHA-512) hash of the secret key as the exponent for the public key rather than using the secret key value directly? This seems inefficient, and I can't see how it adds any ...
3
votes
2answers
246 views

Why isn't f(G) uniform in ECDSA?

In ECDSA, $f(G)=r$, where $r$ is the $x$-coordinate of group element $G$. My question is, how to prove this $f$ is not uniform? In other words, how to prove that, given a random element $G$ with ...
1
vote
0answers
47 views

Can the subgroup membership problem still be hard in known order subgroup?

For example: Given an elliptic curve $E$ over $\mathbb{Z}_q$, and $\#E(\mathbb{F}_q) = p^2$, where $p$ is a prime. Now given a subgroup $\langle G \rangle$ of $E$, and the order of the subgroup $\...
0
votes
0answers
21 views

elliptic curve scalar addition

say there is an homomorphic cryptosystem on elliptic which allows unlimited addition and only one multiplication. So in order to same the mult operation for a later functionality, I need to add a ...
9
votes
2answers
6k views

Can elliptic curve cryptography encrypt with public key and decrypt with private key like RSA?

I know that RSA can be used for both, encryption and signature. What about EC? I know about ECDSA/EdDSA, but to my knowledge it can only be used to sign. I also know about ECDH, but it is a key ...
3
votes
1answer
170 views

Likelihood of signature collision with EdDSA

Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload, what is the probability of a collision where there is another 512-bit value that is also a valid ...
0
votes
0answers
31 views

How to generate a random point on an elliptic curve without knowing it's corresponding scalar private key

Given an elliptic curve with generator $G$, is it possible to generate a random point on the curve $Q = a \cdot G$ without knowing the secret value $a$ that generated it? Note that just using an $a$ ...
2
votes
0answers
28 views

what does small scalar multiplication in ECC means?

I came across this table a lot in many articles, but I didn't understand what's the difference between Scalar multiplication operation in a group based on ECC and a Small scalar point multiplication ...
7
votes
1answer
431 views

What does Shor's algorithm tell us about the complexity class of RSA and the DLP?

If quantum computers operate in BQP and (using Shor's algorithm) they are able to factor large integers and break the discrete log problem, what does that tell us about the complexity class of these ...
1
vote
1answer
90 views

Ensure Data Integrity In An ECDH Key Excange

Been playing around with the inner workings of onion routing and I have a problem. If I wanted to send the 2nd node of a relay network an ephemeral ECC public key, it has to go through node 1, so that ...
1
vote
1answer
52 views

Implications of Shor's algorithm on $F_{2^m}$ elliptic curves and GHASH

The security of elliptic curves depends on the difficulty of the discrete logarithm problem. Should Shor's Algorithm ever prove viable then elliptic curves would cease to offer any useful security ...
7
votes
2answers
924 views

Is it possible to derive a public key from another public key without knowing a private key (Ed25519)?

I have a following use case: User has his master public (pk) - private (sk) key pair (Ed25519). In DB we store a public key. Is ...
1
vote
1answer
363 views

Is this EdDSA modification secure?

I am hoping to employ a signed set membership system which is valid iff each signer's contribution to the set is present. The system should allow for two or more mutually exclusive signed sets to be ...
2
votes
1answer
733 views

Shor's algorithm for elliptic curve discrete logarithm problem

Could someone write Shor's algorithm for solving the discrete logarithm problem and how it could apply to elliptic curves in a few, easy to understand steps? I have a basic understanding of quantum ...
6
votes
0answers
225 views

Precomputation attacks against ECDH

Diffie-Hellman groups are vulnerable to sieving precomputation attacks. These attacks allow a one-time computation against a given DH modulus that makes it practical to attack all subsequent key ...
16
votes
2answers
21k views

What curve and key length to use in ECDSA?

I'm developing a client/server system in Java which is not interacting with third-party software, so I don't have to worry about compatibility. At a certain point, I need the client and server to ...
2
votes
1answer
82 views

How do I multiply two points on an elliptic curve?

Tell me if there is a way to multiply two points on an elliptic curve? For example, as in secp256k1 ...
26
votes
1answer
12k views

ECDSA, EdDSA and ed25519 relationship / compatibility

I'm trying to understand the relationship between those three signature schemes (ECDSA, EdDSA, and ed25519) and mainly to what degree they are mutually compatible in the sense of key-pair derivation, ...
5
votes
1answer
2k views

How can Shor's Algorithm be applied to ECC?

I have not found a specific answer to this question on here. Shor's algorithm can be used to factorize a large (semi)prime $N$ by reducing the task to period-finding of a function $f(x)=x^a$ mod $N$. ...
2
votes
1answer
132 views

Generating a small EdDSA curve

I have an application that would benefit from very small (e.g., 16-20 byte) EdDSA keys and small signatures. It's an application where the goal is more to deter DOS attacks than "hard" ...
2
votes
1answer
42 views

In The Ristretto Group, do all points sampled with Elligator have the same order?

Assume the Hash-to-ristretto255 function Elligator as laid out here. Assume a random hash that is then mapped to a point in the <...
0
votes
1answer
34 views

the probability of sampling a group element that falls in the subgroup on elliptic curve

Given an elliptic curve $E$ on $Z_q$. There is a subgroup $<G>$ on $E$, and the order of $<G>$ is $p$, where $p$ is a prime. And the discrete log problem on $<G>$ is hard. Now we ...
1
vote
1answer
71 views

Modified ECIES using EC point ADD with DH key

I have questions about ECIES. ECIES Vanillia ECIES Encryption side (Alice's side) In "vanilla" ECIES when Alice wants to send Bob an encrypted message: Alice uses some Elliptic Curve, e.g. <...
-1
votes
1answer
73 views

How to find “k” in system of equations?

This is a $y^2=x^3+7$ elliptic curve points - $Q,G_1,G_2,G_3. k_1,k_2,k$? - secret exponents: $k_1*G_1( x_1,y_1) = Q(X,Y)$ $k_2*G_2( x_2,y_2) = Q(X,Y)$ $k*G_3( x_3,y_3) = Q(X,Y)$ How to find a $k$?...
1
vote
0answers
21 views

what is the probability for an adversary to find the new key after adding new entropy in a group where computational diffie hellman is hard?

Let's say I have an Elliptic curve group $E(\mathbb{F}_q)$ with base Point $G$ and large prime order $n$. Computational Diffie-Hellman is assumed to be hard in that group. $H: \{0,1\}^*\rightarrow \{...
4
votes
1answer
316 views

Does Elliptic Curve Integrated Encryption Scheme (ECIES) provide IND-CCA2 security?

I am looking for a faster alternative to RSA with OAEP as a IND-CCA2 public key scheme. Elliptic Curve Integrated Encryption Scheme might be a candidate, but I am not sure if it provides IND-CCA2 ...
1
vote
0answers
25 views

Signature algorithm for constrained environment, curve25512 already present for ECDH

I'm working in a very constrained (in code size/memory) microcontroller environment where I'll need public key signature verification. The algorithm to be used can be chosen, and there's no ...
1
vote
0answers
31 views

How hard will it be to solve an equation in elliptic curve group/ cyclic group where Discrete Logarithm is hard?

Given an Elliptic curve group $E(\mathbb{F}_q)$ where the Discrete Logarithm Problem (DLP) is hard and a base point $G \in E(\mathbb{F}_q)$ with large prime order $n$, what will be the advantage of a ...
0
votes
1answer
58 views

Adding curve25519 to tinyec

I am testing a TLS server that uses x25519 for key exchange. I am relying on Scapy-ssl_tls for building the TLS connection. However, this tool uses tinyec as its crypto library, and tinyec does not ...

1
2 3 4 5
33