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 ...

learn more… | top users | synonyms (2)

3
votes
1answer
686 views

Elliptic Curve Encryption Ciphertext Size

I'd like to know how much bigger is the ciphertext when encrypting a message using ECC encrytpion? ECIES (or ElGamal)
2
votes
1answer
488 views

Hide a weakness in ECC by choosing the prime or one of the curve coefficients

Suppose you are given a value $c$. Can you find a prime $p$ and an integer $b$ such that the elliptic curve $$E: y^2 \equiv x^3 -3x + b \pmod p$$ is cryptographically weak? You need to choose ...
13
votes
2answers
2k 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.
7
votes
3answers
210 views

Do I understand (below) why Q = dP is easy while finding d is hard

As we all know for discussion of Dual_EC_DBRG, the point on an elliptic curve Q can be calculated from P and some (large) integer d $Q = dP$ And we know that knowledge of Q and P is not sufficient ...
6
votes
1answer
118 views

What are the computational benefits of primes close to the power of 2?

Recently I was reading some article about the Bernstein's Curve25519. This is a particular Montgomery curve over $\mathbb{F}_q$ where $q = {2^{255}-19}$. What I missed or was unable to understand is ...
5
votes
1answer
119 views

Which attacks are possible against raw/textbook elliptic curve?

A quick question, we know that raw RSA is a no go. To solve this we have different PKCS standards forcing structure on the input messages. For EC the story is something else. For signatures we have ...
5
votes
1answer
661 views

Families of public/private keys in elliptic curve cryptography

I'm looking for a related key scheme for elliptic curve cryptography. The basic idea would be that there would be a master public key and a master private key. From the master public key, you could ...
4
votes
0answers
243 views

Is there a flaw in this ECC blind signature scheme?

Recently I've found the following work on the internet: An ECC-Based Blind Signature Scheme The paper claims to be an ECDSA blind signature however it seems that their scheme has a flaw in it. The ...
4
votes
1answer
1k views

Subtracting a point in elliptic curve cryptography?

I've had lots of practice adding points for my crypto class. However I've run into a situation where I need to subtract two points for decryption: ...
3
votes
1answer
117 views

Counting points on elliptic curve over binary field

How to count number of rational points on elliptic curve over binary field?
3
votes
3answers
145 views

Is there any alternative for extended euclidean algorithm to perform modulo division?

I'm implementing point addition and point doubling operations for elliptic curve cryptography. I have implemented extended euclidean algorithm to perform modulo division. It appears the that ...
3
votes
3answers
303 views

understanding pairing $e:G \times G \to G_T$ and ( Decision)BDH assumption

From DrLecter's comment, I know that DDH problem can be efficiently solved with this $$e(g^a,g^b)\stackrel{?}{=} e(g,g^z).$$ I have some trouble to understand this map $e:G \times G \to G_T$. Am I ...
2
votes
2answers
355 views

Why does NaCL have different keys for signing and encryption?

I want to start using NaCL to sign messages that will go into a message queue, and I noticed that it generates different keys for each operation. Is there a reason for this? Can I not use the same PK ...
1
vote
2answers
671 views

Reuse of a DH / ECDH public key

I was wondering whether it is safe to use the same DH or ECDH key pair in more than one key agreement, particularly if these public keys are in a public registry. These public keys could be used by ...
11
votes
1answer
521 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 ...
11
votes
1answer
256 views

Logjam on Elliptic Curves?

I think we're all aware of the Logjam attack. From now on we know that re-using primes for DH is a bad idea. But we also say that elliptic curves are safe from the attack (relying on the NFS), ...
7
votes
1answer
240 views

Is SHA-1 safe for signing ECDHE parameters?

Is using the SHA-1 algorithm insecure for hashing the ephemeral ECDH public key in the signed_params structure? There are some worrying articles about using SHA-1: ...
6
votes
1answer
250 views

Difference between “ECDH with cofactor key” and “ECDH without cofactor key”?

I need to use “ECDH with a cofactor key” for generating symmetric key. I have a fair idea on how ECDH works, but I don’t understand the cofactor part. What is the difference between ”ECDH with a ...
6
votes
1answer
163 views

Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard?

I know that there are elliptic curve groups, used in pairing-based cryptography, where the decisional Diffie Hellman problem (ie. given $g$, $g^a$, $g^b$ and $c$, determine if $c = g^{ab}$ is easy but ...
5
votes
0answers
56 views

Software timing attack using Kocher method

What's the minimum number of random sample points needed in Kocher's timing attack, so that we can determine enough valid measurements of $A_{i,r}$ and $D_{i,r}$? I'm working from this paper: Volker ...
5
votes
0answers
39 views

Is it possible and safe to use SAKKE for signing/verification, rather than for encryption?

Is it safe to use the Sakai–Kasahara key encryption algorithm (SAKKE) for signing/verification, rather than for encryption? (Example at bitbucket.org) In particular, I want many Bobs to be able to ...
5
votes
1answer
153 views

How can I find the order of the group that an elliptic curve is defined over?

I have a Weierstrass elliptic curve ($y^2=x^3+a \times x+b \mod p $) How can I find the order of the group itself? I have seen Mathematica has a GroupOrder[] ...
4
votes
1answer
758 views

ECC vs RSA: how to compare key sizes?

I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA. I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve ...
4
votes
1answer
123 views

Is it ever unsafe to compress an EC point?

I am working with a library that outputs EC points in uncompressed form. To save space, I'm considering modifying said library to use compressed EC points. Assuming that I keep track of the sign bit ...
4
votes
3answers
224 views

Why are we not using multiple ciphers per message?

I am aware of at least rsa, elgamal-encryption, and variations of elliptic-curves relying on different problems and that those problems are considered hard. However, if someone figures out a way to ...
4
votes
3answers
542 views

Why are elliptic curves better than cyclic groups?

The set of points of an elliptic curve over a finite field is isomorphic to the direct product of two cyclic groups (i.e. $E(F_{p^n}) \cong Z_{s} \times Z_{t})$. What is the advantage of representing ...
3
votes
2answers
394 views

Are all possible EC private keys valid?

I usually generate a key pair using openssl or Bouncy Castle. I'm using curve secp256k1. The 256bit private keys look fairly random. Do all values of "private ...
3
votes
1answer
450 views

What differences between Menezes–Vanstone ECC and ElGamal ECC?

After researching ECC encryption, I found that we can use ElGamal cryptosystem with elliptic curve and can we use Menezes-Vanstone cryptosystem with elliptic curve. What is the essential difference ...
2
votes
1answer
75 views

How to perfrom modular division while numerator is lesser than the denominator?

I'm implementing point addition and point doubling of elliptic curve cryptography. The formula that I'm using for slope is Point addition: $S = \frac{(P_y-Q_y)}{(P_x-Q_x)}$ where $P$ and $Q$ are the ...
2
votes
2answers
36 views

With EC secp256k1 is there a way of transforming a function of the private key to a function of the public key?

A key pair has a private key $D_A$ and a public key $Q_A$. $D_A$ is an integer less than the curve's $n$. Is there any (boolean) function of the private key $f(D_A)$ which can be transformed into a ...
2
votes
1answer
238 views

Simple digital signature example that one could compute without a computer?

I am working on a document to explain Bitcoin to students. But I am having a hard time translating the principle described in §2 of the Bitcoin whitepaper in layman's terms. There is a great question ...
2
votes
0answers
55 views

Using a product of a series of curve25519 scalars as a private key

There are a few systems like the GNU Name System and the Sphinx mixnet packet format that employ a series of curve25519 scalars all multiplied together as a private key. Are there any caveats to ...
2
votes
1answer
380 views

Koblitz encoding a message to a point, what is the “associated auxiliary base parameter”?

I am looking at the Koblitz method for encoding a message as an elliptic curve point. The first step given in the paper I'm reading is: "Choose an elliptic curve and its associated auxiliary base ...
2
votes
1answer
402 views

What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?

This page on Twist security mentions a combined attack and a twist rho attack, applicable in particular to NIST P-224 curve with cost $2^{58.4}$ something, with no mention precise definition of ...
2
votes
0answers
358 views

Elliptic Curve based blind signature implementation

I want to use Elliptic Curve based blind signature scheme for my research. There is no proper implementation of ECC-based blind signatures. Can someone describe to me which things I need to follow ...
2
votes
1answer
178 views

Verifying multiplicative inverse on a prime field in NIST's ECDSA_Prime.pdf

I am trying to learn about the Elliptic Curve Digital Signature Algorithm (ECDSA) by verifying the results in some example calculations. I found a PDF of example ECDSA calculations from NIST here: ...
2
votes
2answers
251 views

64 bit Elliptic Curve key?

For a simple proof of concept project i'm (attempting!) to do, i've started looking into openSSL elliptic curve cryptography. However instead of the standard key lengths, 160-512. I'm interested in ...
2
votes
1answer
452 views

Fast modular reduction

I am looking at ways to speed up modular reduction for the polynomial $$2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$$ I have read the paper "Generalized Mersenne numbers" by J.A. Solinas, but it does not ...
2
votes
1answer
123 views

How do I know if a given curve requires a FpCurve F2mCurve or ECCCurve?

I'm trying to read a public key into Bouncy Castle (secp256k1) and need to choose from the following objects FpPoint; FpCurve; or ...
2
votes
1answer
473 views

inverse problem about scalar multiplication on elliptic curve

Let $E$ be an elliptic curve over a finite field $F_p$. Given $n$ be a positive integer and $Q$ be a point on $E$, assume that $Q=nP$, how can we find this $P$? We can assume that $n|p-1$. If $n$ is ...
1
vote
1answer
52 views

What happens if you multiply a point with its order on complete Edwards curves?

I was recently working with some ECC crypto and stumbled across the following phrase on the SafeCurves page: The rational points of a complete Edwards curve are the pairs (x,y) of elements of ...
1
vote
1answer
111 views

With ECDSA is there a way for the verifier to calculate any properties of $k$?

With ECDSA, given $(r,s)$ and $m$, is there a way for a verifier to calculate any (boolean) properties of $k$, without knowing $k$ or the private key $D_A$? (I understand that $k$ should be random, ...
1
vote
2answers
131 views

Severity of Cooking NIST P Curve Constants

Bruce Schneier and Gregory Maxwell have both stated that they believe the constants chosen for NIST's P curves (i.e. P-256r) are cooked. DJB has put together a detailed list of red flags but, outside ...
1
vote
3answers
420 views

Point decompression on an elliptic curve

I'm programming an elliptic curve cryptosystem and I'm having difficulty with decompressing points. The following information is from my project specification as to my understanding: Given a point ...
1
vote
1answer
439 views

What are some restrictions when converting Montgomery Curves into Weierstrass Curves?

I want to represent a Montgomery Curve (curve25519) in Weierstrass form as a personal exercise. After doing some math and referencing the conversion equation at ...
0
votes
1answer
60 views

Is there an additive homomorphic encryption that supports exponentation

For example say we have two numbers a and b. Now is there any partial homomorphic encryption scheme that allows to compute (a-b)^2 over the ciphertexts of a and b without round trips.
0
votes
2answers
123 views

Determine if a public key point y is negative or positive, odd or even?

Take an elliptic curve cryptography public key (x, y) and its additive inverse (x, -y). How do you identify which is the positive point and which is the negative point? Examples: Private key 1 -> ...