Tag Info

New answers tagged

1

Consider the rational functions $f_P^k$ and $f_P'$. Since $\operatorname{div}$ is a homomorphism of semigroups (i.e. $\operatorname{div}(fg)=\operatorname{div}f+\operatorname{div}g$), we have $$\operatorname{div}(f_P^k)=k\cdot\operatorname{div}f_P=k\cdot(m[P]-m[\mathcal O])=km[P]-km[\mathcal O]=\operatorname{div}f_P'\text.$$ Now with theorem 5.36 of "An ...


0

"Elliptic curve encryption" is somewhat popular wording; one better be specific like ElGamal encryption with a group of points on elliptic curve. So, start with ElGamal to understand what kind of group is expected. Try ElGamal with multiplicative group modulo a (large) prime. At last, consider objects named points on a curve as an unusual set with highly ...


0

As suggested, here is a hopefully entry-level precis of the paper linked in the comment above. A Discrete Logarithm based asymmetric key system lacks a true trapdoor function - you can't compute a pre-image for an arbitrary image. Instead, a Schnorr signature relies on a slightly weaker condition. A generalized Schnorr signature can be considered to have ...


3

Ed25519 needs two secret values: The private scalar (~256 bits) A hash prefix used derive a secret nonce from the message (256 bits) Using the same value for these is bad style, as is deriving one of them from the other. You could also use their concatenation as private key, but that'd double its size to 512 bits. So Ed25519 chose the clean solution of ...


1

As Samuel Neves described in the comments it is trivially possible to obtain $P$ from $Q=nP$, given $Q$ and $P$. Simply compute $k=n^{-1} \bmod l$, with $l=|E(\mathbb F_p)|$ being the order (=the number of points) of the curve. $l$ is usually known. Then, to obtain the desired point $P$, calculate $P=kQ=knP$ and you're done.


0

To start things: Don't roll your own crypto. What you're proposing is using standard static Diffie-Hellman for key-exchange, which by itself is a bad idea, as it will always result in the same key for each communcication between Alice and Bob. The key by itself should be safe, but as soon as it's broken all messages are as well. So if either the sender's ...


1

Curve25519 was supposed to be mainly used for Diffie-Hellman key-exchange and it provides ~128bit security and should fulfill all standard security assumptions on elliptic curves (and even some more). Now to answer the question is: yes. ElGamal can be used securely with Curve25519, as ElGamal is simply a Diffie-Hellman key-exchange ($\delta= m*g^{\alpha ...


0

If you can express your operation well using plain groups, go with normal elliptic curves. But the pairing adds additional mathematical structure, which enables new algorithms. Some examples: BLS signatures They're verifiably deterministic and small, 2x security level, instead of 3 to 4 times, with DSA/Schnorr/ElGamal signatures. These use the pairing ...


2

Good blinding requires good randomness. Randomness is a hard requirement, especially for embedded systems. In a similar vein, the DSA and ECDSA signature algorithms require a strongly random integer (called k) for each signature, and several implementations have failed to use random enough values, with hilarious consequences; the most well-known case is Sony ...


0

Don't confuse h which is commonly adopted for the cofactor in EC (Cf p13 of the doc). The class number $\mathcal{H}(K)$ for any number field K is the cardinal of the class group Cl(K). Take a look to any course in algebraic number theory and specially H. COHEN and his famous book " A course in computational Alg. Numb Th ..." The ring theory is very vast, and ...


1

No, it's not a problem. What you've found is known as the square computational diffie-hellman problem(SCDH) and it can be shown that this is equivalent to the computational diffie-hellman problem(CDH). For completeness: SCDH: Given $g$ (your $G$) and $g^x$ (your $Q$), find $g^{x^2}$ (your $d_A^2G$). It is shown here that this problem is as hard as the ...


4

All of these are answered by the SafeCurves project: $x^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$ Edwards curves can be converted to Montgomery form.Montgomery curves can be converted to Weierstrass form.Some, but not all, Weierstrass curves can be converted to Montgomery form. The Montgomery ladder (applicable only to Edwards and Montgomery curves) is faster ...


1

Of course there are others. Of interest might be the paper 'Efficient ephemeral elliptic curve cryptographic keys' by Mieli and Lenstra, which claims to generate fresh Elliptic Curves sufficiently quickly that they can be created on the fly for a single ECDH exchange, and then discarded.


4

The formulae on the linked page deal with curves in short WeierstraƟ form, that is $y^2=x^3+ax+b$. Your curve is not given in this format. You can find the correct formulae for long WeierstraƟ curves (like yours, where the coefficients $a_1$ and $a_3$ are zero) on this page.


1

The inventors of the Supersingular Isogeny Key Exchange, Defeo, Jao and Plut have posted some code on GITHUB at: https://github.com/defeo/ss-isogeny-software/ There is also a paper on implementation of this key exchange by some people from the University of Waterloo. Their paper is "Efficient Implementations of A Quantum-Resistant Key-Exchange Protocol on ...


1

poncho has it right, I was calculating the inverse incorrectly. The inverse of a point $(x,y)$ is $(x, -y)$. It just so happens that $(x,y) + (x, y^{-1}) = 0$, but this was a red herring. Thanks!


2

Poncho's answer explains why finding a specific $Q$ in $Q = k x G$ is not feasible. If you could do this so could anyone else for any keypair and ECC would have no security. The short answer is ECC is secure specifically because there is no known method short of brute force to find $k$ for a given $Q$. Of course an exhaustive search (brute force) is always ...


1

lm = nm; low = nw; hm = lm; high = low; You're setting hm = nm since lm = nm. Correct is: hm = lm; lm = nm; high = low; low = nw;


8

If that were possible, that is, if you could take an x-coordinate, and find the private key $k$ such that $kG$ has that x-coordinate, well, you've just solved the discrete log problem. If you can do that, you've just shown that the curve is insecure. If you're thinking "I'm not specifying the y-coordinate; doesn't this make it easier than the discrete log ...


1

Two approaches to Post Quantum Key Exchange that have acceptable bandwidth requirements are the NTRU/Ring-LWE lattice designs and the ECC Isogeny Key exchange you mention. Since the UK spy agency published an attack on a lattice based scheme they had designed, there has been an active discussion between Dan Bernstein and the Lattice Cryptographers over the ...


3

The Supersingular Elliptic Curve Isogeny Key Exchange that you refer to was first published in 2011 by DeFeo, Jao, and Plut. It builds on but is quite distinct from earlier work by Rostovetsev and Stolbunov in 2006. As a Post Quantum/Quantum Safe replacement for Elliptic Curve Diffie-Hellman (ECDH) it has several good properties: The number of bits that ...



Top 50 recent answers are included