All Questions
Tagged with elliptic-curves cryptanalysis
48 questions
1
vote
1
answer
102
views
Could the "100 Prisoners Problem" strategy help find a private key from a public key in elliptic curve cryptography?
In elliptic curve cryptography (ECC), repeatedly adding the generator point G to itself essentially forms a long cycle, with the length of the cycle being equal to the order of the curve (the total ...
1
vote
0
answers
113
views
Is generating random blake256 hashes until packed points is on the curve, a safe algorithm to avoid the discrete log between the generated points?
I know there’re many questions that ask how to safely HashToCurve, but I want to know if the method I found in an actual implementation is secured against the ...
- 329
0
votes
1
answer
90
views
Getting the slope of a public key given its x and y coordinates
Is it possible to get the slope of a public key given its $x$ and $y$ coordinates?
Since all the ECC calculations come from geometry, I thought this calculation might be possible.
- 11
2
votes
1
answer
157
views
Not understanding elliptic curve scalar multiplication to produce Ethereum address
This is the equation
Public key = Private key * G
Here,
...
- 125
1
vote
1
answer
206
views
Double- and -add algorithm
I am currently doing the elliptic curves and I'm stuck for 8 hours without finding solutions. I under stand the process of double and add but don't know how to obtain 5 * 8P = 4OP =11 P. 11 P was in ...
- 11
0
votes
2
answers
208
views
Trouble detecting cyclic group order crossovers in SECP256K1
There's a problem in detecting whether the sum of public key addition has crossed the cyclic group order boundary
For this example, think of public keys $Pub$ as private keys $Priv$, (private scalars),...
- 49
1
vote
0
answers
74
views
Is it possible to get the negative point with −x in that version of the Pedersen hash over the BaybyJubJub curve?
The Pedersen hash is a low constraints friendly hash for Zk-Snarks.
Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
- 329
1
vote
1
answer
447
views
Pedersen Hash : when truncating the hash to keep only the X coordinate, is it possible to compute a collision when the Babyjubjub curve is used?
The Pedersen hash is a low constraints friendly hash for Zk-Snarks.
Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
- 329
2
votes
2
answers
588
views
Best Known Attacks on Discrete Logarithm in Generic Groups
This is a followup to my recent question Discrete Logarithm Challenges and Records.
I am interested in confirming my understandings from the answer to that question, stated below:
For a discrete ...
- 23.7k
5
votes
0
answers
626
views
How the mimc bug from circomlib was safely exploited to fake the merkle root in the witness in practice?
Several years ago, there was an unenforced constraint on verification in the cirmcomlib library : a tool for building projects using ZsNarks. The error allowed to forge cryptographic nullifiers/proofs ...
- 329
0
votes
1
answer
37
views
(Non)security of algebraically derived EC keys
I recently had a situation where I needed to derive a secondary Curve25519 private key from an existing one programmatically. The obvious solution was to use a KDF, but I wondered at the time about ...
3
votes
1
answer
1k
views
1
vote
1
answer
711
views
How to determine secp256r1 or secp256k1 is used on the web sites
I'm pretty new at Cryptography (and at Cryptanalysis), but I went to the website Elliptic to try to discover the elliptic curve they use, and I found they use ECDP 256. So, by SEC2 I discovered they ...
- 45
3
votes
1
answer
612
views
Excluding specific factors for Pohlig-Hellman
I want to use Pohlig-Hellman and BSGS to solve the discrete log of an Elliptic Curve which has a composite order generator.
The ...
- 1,454
1
vote
2
answers
306
views
Symmetric versus asymmetric self encryption
I can encrypt my files with a symmetric encryption algorithm like AES, or with an asymmetric encryption algorithm like RSA or ECC (I encrypt my files with my own public key). No communication is ...
- 11
7
votes
0
answers
559
views
Which is the smallest safe elliptic curve (bit-length)?
At https://safecurves.cr.yp.to/ some elliptic curves are listed which passed certain security tests. The smallest bit-length of a safe curve listed there is 221 bits.
At wiki page discrete logarithm ...
- 453
1
vote
2
answers
633
views
Can we retrieve his private key using his public key in ECC?
A paper wallet is the name given to an obsolete and unsafe method of storing bitcoin which was popular between 2011 and 2016. It works by having a single private key and bitcoin address, being printed ...
- 11
0
votes
1
answer
187
views
Is this the right way to implement ElGamal scheme over Elliptic Curves over prime field? [duplicate]
I'm fairly new to Cryptography, especially elliptic curves in general. I learned to do Point Multiplication, Scalar Multiplication and also programmatically implemented them. But I was trying to do ...
- 1,080
14
votes
2
answers
6k
views
Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different?
We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as:
$s=\frac{H(m)+xr}{k}$
Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, ...
- 2,296
2
votes
0
answers
186
views
Security of an Elliptic Curve Public Key with a "Small" x-coordinate
Consider an elliptic curve over a finite field $F_p$ with $p$ prime and order $n$. Let $Q$ be a generator for the field. Given a public key point $P = aQ$, suppose we have an algorithm that finds an ...
- 29
6
votes
2
answers
263
views
How sensitive to change are elliptic curve formulae In layman's terms?
Take for example a curve from a recent question such as #25519:-
$$y^2 = x^3 + 486662x^2 + x$$
It's considered "safe". What are are the implications of amending it very slightly to:-
$$y^2 = x^3 + ...
- 15.7k
1
vote
0
answers
54
views
Preserving location privacy
What are cryptographic techniques that could be used so that if I wanna to enable a server to send message to certain nodes in a network with preserving the privacy location for them ??
- 205
3
votes
1
answer
524
views
Understanding the q-SDH Problem (on elliptic curves)
I have some troubles in understanding the q-SDH problem. The discrete logarithm problem states the following.
Given a point P of order on an elliptic curve and a point Q on the same curve. It is hard ...
- 248
4
votes
0
answers
186
views
What is the difference between Elliptic curves and Hyper-elliptic curves in terms of security? [duplicate]
What is the difference between Elliptic curves and Hyperelliptic curves in terms of security? I am relatively new to cryptography and have heard a great deal more about Elliptic curves than ...
26
votes
3
answers
18k
views
How effective is quantum computing against elliptic curve cryptography?
I've been reading the Wikipedia page on Elliptic-Curve Cryptography and I came across the following.
in August 2015, the NSA announced that it plans to replace Suite B with a new cipher suite due ...
1
vote
2
answers
309
views
What are the properties of secure Elliptic Curves?
I have heard about the standard elliptic curves called NIST curves. What are the properties of such cryptographically secure elliptic curves?
Are they standardized according to certain protocols? Also,...
4
votes
0
answers
361
views
Encrypt using ECDH with two different EC public keys, minimizing payload size
Let's say Alice has the private EC keys $a$ and $b$, with a base point of prime order $G$. Alice computes the corresponding public keys $A = aG$ and $B = bG$, and sends them to Bob.
Bob now wants to ...
- 141
1
vote
1
answer
177
views
Elliptic curve representation
According to this page, Edward's curve point doubling can be represented in a different way by assuming $c=1$ and $d = r^2$.
It then says we can represent $x y$ as $Y Z$ satisfying $r\cdot y = \frac ...
- 11
6
votes
2
answers
907
views
Why do elliptic curves require fewer bits for the same security level?
I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits.
For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic ...
- 81
2
votes
2
answers
336
views
Knowing interval of discrete log for elliptic curve
Are there any special attacks I can apply if I know the upper bound for $n$ (meaning $0 \le n \le \text{Upper Bound}$) in the equation $Q = nP$, where $P$ is the base point and I'm trying to solve for ...
- 21
4
votes
1
answer
2k
views
Pollard's Lambda algorithm ecdlp with Pohlig Hellman
I'm trying to solve the ECDLP problem given an elliptic curve defined over a prime field. This prime is large (about 256 bits).
I managed to factor the order of the curve, and most of the prime ...
- 41
6
votes
0
answers
299
views
Index calculus over elliptic curve over function field
According to my understanding there are some pretty solid seeming roadblocks to carrying out an index calculus on an elliptic curve over a finite field. The general strategy is to take points over $E(\...
- 111
1
vote
1
answer
306
views
Problems when using PBKDF2 to create an ECDSA private key from a password?
System based on, e.g.:
PBKDF2, ECDSA and authenticator's random challenges.
Key derived from a password would be ECDSA's private key used to sign random challenges.
Is password brute force the only ...
- 11
0
votes
1
answer
260
views
Is there any way to test how secure is a new cryptosystem? [closed]
I have investigated Elliptic Curves and after that I have designed a cryptosystem using this technique. How can I test the safety of my scheme compared to another cryptosystems that use factoring such ...
0
votes
1
answer
745
views
Message Expansion / Encryption Blowup Factor / Ciphertext Expansion of ECC
In order to complete the following table with asymptotic times and message expansions,
$\quad \quad \quad \quad \quad \quad \quad \quad \quad$ RSA $\quad$ McEliece $\quad$ ECC
Encryption Speed $\...
- 325
0
votes
0
answers
97
views
Found weil pairing. Index Calculus method on the results of weil pairing
Consider Elliptic curve with p = 59, A = 1, B= 0, P = (25,30) and Q=(35,31).
So I tried to solve this using MOV attack.
The torsion point for them E[5] is R(-25,30i) where is sqroot -1
Chosen two ...
- 121
5
votes
1
answer
1k
views
Backdoor in NIST elliptic curves
Let $E$ be an elliptic curve defined over a finite field $F_q$ with prime order $n$ and $P,Q \in E$ and $k$ be private key such that $kP=Q$. Since $n$ is prime, $E$ is isomorphic to $Z_n$. Suppose $\...
- 2,353
20
votes
1
answer
4k
views
Does Curve25519 only provide 112 bit security?
In a recent mail on the IETF CFRG mailing list it was claimed that:
The (currently missing) security considerations (or somewhere) should describe why Curve25519 is ok when used in contexts where ...
- 46.4k
2
votes
1
answer
373
views
Is cryptanalysis of CTB-Locker really impossible?
It seems that CTB-Locker make a lot of victims nowadays, and yet, the full encryption scheme of it is now publicly known [1,2].
Would any of you could find a weakness to exploit in this encryption ...
- 605
2
votes
1
answer
545
views
Polynomial division hardware implementation
I am beginning the implementation of the polynomial binary division algorithm now as I understood i will be checking the MSB bit if 1 to XOR and shift the sum if 0 i will only shift.
What I am not ...
- 95
0
votes
0
answers
508
views
Polynomial Inversion over Galois Field
Hello guys I am looking to calculate the Inverse of a given polynomial in Galois field
I have found the little Fermat's algorithm and the Itoh-Tsujii
I am getting a bit confused with both algorithm ...
- 95
3
votes
1
answer
257
views
Twisted curves in protocol
I've come to understand that twisted curves, as for instance defined in the Brainpool specifications, are $F(p)$-isomorphic to their regular $F(p)$ equivalents. So brainpoolP256r1 is isomorphic to ...
- 94.5k
1
vote
1
answer
114
views
Why does knowing the number of points on a curve help solve ECCDLP?
Perhaps, this is a really obvious question, but I am still having trouble understanding how this all fits together. Why is knowing the number of points on an Elliptic Curve helpful in cracking it?
...
- 13
4
votes
0
answers
619
views
Using the same private key for two ECC key pairs
Let $(d_1,Q_1)$ and $(d_2,Q_2)$ be ECC key pairs over two different elliptic curves (say NIST P-224 and NIST P-256). According to the Elliptic Curve Discrete Logarithm Problem (ECDLP), if the private ...
- 41
3
votes
1
answer
583
views
Derive a public EC key from two public EC keys
Alice has two EC key pairs: $a_1$, $a_2$ are private keys (integers), $A_1$, $A_2$ are the corresponding public keys (points). Alice and Bob want to create a new public key $C$. Alice must prove that ...
- 31
5
votes
1
answer
928
views
Why doesn't this replay attack work on ECDSA?
I've just started working with elliptic curves and ECSDA in particular, so my understanding of the underlying math isn't great. The thing I'm currently stuck on is trying to understand why replay ...
- 51
9
votes
2
answers
3k
views
ECC algorithm pollard's $\rho$ complexity
One of the methods to break a ECDLP is Pollard's rho algorithm. When ECDLP is defined over a finite field $F_p$, and given a relation $S=w.T$, where S and T are a member of $F_p$. Then ECDLP is to ...
- 2,025
30
votes
2
answers
12k
views
How does the MOV attack work?
What exactly is the MOV attack, how does it actually work, and what is it used for?
It's explained briefly here and I'd like to know what it is more / what is it fully used for.
- 749