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)

7
votes
3answers
216 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
123 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
678 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 ...
5
votes
1answer
122 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 ...
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: ...
4
votes
0answers
246 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 ...
3
votes
1answer
121 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
148 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
306 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
381 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
695 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
546 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 ...
7
votes
1answer
243 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
268 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 co-...
6
votes
1answer
164 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
41 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
160 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
130 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
550 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 ...
4
votes
3answers
225 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
1answer
809 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 ...
3
votes
1answer
51 views

Is a hash function used to expand the key after ECC shared secret is complete?

I am trying not to solicit opinions, but I have not been able to find a reference to the question at hand. I have designed an ECC engine in silicon that handles any curve in the form of $y^2 = [ax^3 +...
3
votes
2answers
408 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
284 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 ...
3
votes
1answer
458 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
2answers
43 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
0answers
365 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
499 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 "...
2
votes
0answers
56 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
180 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
1answer
464 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
76 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
685 views

How do I convert the definition of E-521 into a curve definition a la Bouncy Castle?

I am currently trying to create an ECCCurve for E-521. Unfortunately, it is not currently a named curve in the library I am using, so I will have to define it manually. I am using the definition of ...
2
votes
2answers
261 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
425 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
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
2answers
318 views

How to derive a symmetric key from ECDH shared secret?

I am trying to implement the internal primitives of ECDH. Currently I'm able to multiply the receiver's public EC point with the sender's private key to arrive at the shared EC point. Next step is to ...
1
vote
1answer
56 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
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
2answers
133 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 -> (x,...
1
vote
1answer
70 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.
1
vote
1answer
459 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 http://en.wikipedia.org/wiki/...
1
vote
1answer
149 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
3answers
438 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 $x$...