Hot answers tagged

50

From a cryptographic standpoint it is OK to expose a public key in the sense of revealing its value. The most basic assumption in cryptography involving public/private key pairs is that the value of a public key is public; hence its name. It is extremely important that an adversary can not alter a public key. Any exposition that would allow alteration must ...


30

Ed25519 is a specific instance of the EdDSA family of signature schemes. Ed25519 is specified in RFC 8032 and widely used. The only other instance of EdDSA that anyone cares about is Ed448, which is slower, not widely used, and also specified in RFC 8032. Keys and signatures in one instance of EdDSA are not meaningful in another instance of EdDSA: Ed25519 ...


27

While it is true that Elliptic Curve Diffie Hellman, Elliptic Curve Signature Generation and Elliptic Curve Signature Verification rely on scalar multiplications, these are usually implemented as different types of scalar multiplication for both security and efficiency reasons. In fact there are three types of scalar multiplications used in practice for ...


22

Clearing the lower 3 bits of the secret key ensures that is it a multiple of 8, which in turn ensures that no information, small as it may be, about the secret key is leaked in the case of an active small-subgroup attack. The typical simple Diffie-Hellman key exchange works like this: $$ \text{Alice} \xrightarrow{\hspace{3cm} a G \hspace{3cm}} \text{Bob} \\...


17

If I understand your question correctly, you are essentially asking if points in Edwards and Montgomery curves can be represented in Weierstrass coordinates. This is true; in fact, any elliptic curve over a field of characteristic $\neq2,3$ can be represented in Weierstrass form $\mathcal{E}_{w}^{a, b} : y^2 = x^3 + ax + b$, and by extension its points can ...


17

The old terminology was confusing, so they've rebranded a bit. X25519 is Elliptic Curve Diffie-Hellman (ECDH) over Curve25519 Ed25519 is Edwards-curve Digital Signature Algorithm (EdDSA) over Curve25519 Libsodium's ref10 curve25519 code is actually used both by crypto_scalarmult()/crypto_box() as well as crypto_sign().


16

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer? Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ is the number of bits of the modulus $N$, i.e. the key size of RSA. So 4096 for 2048-bit RSA, double that for 4096-bit. This paper (PDF) has an algorithm using ...


13

If you can store the private key with some pre-computed work, then you can pick almost any public key you want. So in a way, it depends on the implementation. Here's a diagram of how Ed25519 works, note how keys are generated: (Image source.) A more detailed description (that is simpler than the actual paper) of the process is in these slides (slides 9 - ...


13

The advent of quantum computing, real usable out of the lab QC, will pretty much be the end of any encryption that relies on the difficulty of the discrete log problem via Shor's Algorithm et al. That is not to say it is the death of all modulus based encryption schemes, probably just asymmetric public/private key based schemes. That said, QC's aren't magic,...


13

if Ed25519 has gone through rigorous cryptanalysis It is based on Curve25519 which has gone through extensive cryptanalysis. The Ed25519 signature scheme as well is being heavily reviewed and adoption is rapid. There are already a number of papers on the algorithm itself, as well as a few papers on specific implementations. Every part of the algorithm and ...


13

Edwards25519 is the twisted Edwards curve $$-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$$ over the prime field $\mathbb F_p$ where $p = 2^{255} - 19$. The coefficient $d = -121665/121666$ was chosen to so that this curve is birationally equivalent to the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, called Curve25519, whose coefficient 486662 was chosen to be ...


12

It is not possible to double security level of Ed25519 any trivial way. Instead, doubling security level requires using another curve that is approximately 512 bit curve. In systems compliant with RFC 7748, i.e. some of IETF specifications, there is Curve448 curve (Ed448-goldilocks). It is almost twice as strong as Curve25519 (its strength is 224 bits). ...


11

Trevor Perrin wrote a library doing exactly that. Explanation can be found on in the curves mailing list archives. To convert a Curve25519 public key $x_C$ into an Ed25519 public key $y_E$, with a Ed25519 sign bit of $0$: $$y_E = \frac{x_C - 1}{x_C + 1} \mod 2^{255}-19$$ The Ed25519 private key may need to be adjusted to match the sign bit of $0$: if ...


11

Yes, this should be secure. I am not familiar with TweetNaCl, so I cannot speak on the concrete implementation. However, the general construction of signing a hash of a message instead of the message should be secure. It is in fact a standard way to sign messages. In general it should work for any secure signature scheme and cryptographic hash function. ...


11

There's a few different related parts here, and the nomenclature of the library you've cited is a little confusing. Curve25519 is an elliptic curve over the finite field $\mathbb F_p$, where $p = 2^{255} - 19$, whence came the 25519 part of the name. Specifically, it is the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, but you don't need to know the ...


10

Well, lets go through the issues: It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone Nope, not quite. You also need the message being signed. And, with that, it doesn't give you the unique public key; it does allow you to narrow it down to two possibilities (assuming you're using a ...


10

All of these are answered by the SafeCurves project: For twisted Edwards curves, $ax^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$. Edwards curves are the special case a = 1. 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 ...


10

Curve25519 makes use of a special x-coordinate only form to achieve faster multiplication. Ed25519 uses Edwards curve for similar speedups, but includes a sign bit. While it could have been done differently, doing it this way simplifies implementations that only need one of encryption or signing.


10

That example private key is not encoded with PKCS#8, but with the format described in RFC 5958, which is supposed to replace PKCS#8 (at least, in IETF parlance, RFC 5958 "obsoletes" RFC 5208, which is a copy of PKCS#8 v1.2). The ASN.1 type if called OneAsymmetricKey: OneAsymmetricKey ::= SEQUENCE { version Version, ...


10

The formulas actually work. You just have to keep in mind to make computation in the field of intergers modulo $2^{255}-19$ and that there are actually two square roots, you need to use the right one if you want to have the expected result. You can test the following SAGE code gf=GF(2^255-19) X_P = gf(...


9

No, conversion of an EC key pair from a curve to another of unrelated order is not possible. One of the closest things that could be done would be that parties generate a new P256 key pair, then certify their new P256 public key using their C25519 private key, check the other party's certificate using the other party's trusted C25519 public key, and now ...


9

(minisign author here) As noted by corpsfini, keys encode the Y coordinate. The X coordinate is recovered using the curve equation: X = sqrt((Y^2 - 1) / (d Y^2 + 1)). The square root has two solutions, so we need to encode the sign of x as well. Since coordinates only require 255 bits, we have a extra bit, used to encode the sign. X and Y ∈ [0; 2^255-19[, ...


8

First off, your equation is correct and there seems to be no calculation mistake. To understand on how to get from $$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$ to $$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}$$ one first needs to observe that $e=(d-2)/(d+2)=121665/121666$ holds. The next step is to consider: "What operations are actually allowed with birational ...


8

As you said, you need to define the goals. You can take a look at SafeCurves, which is a joint work by Bernstein and Lange to help choose/construct elliptic curves w.r.t. ECDLP difficulty and ECC security. Note that if you need a pairing-friendly elliptic curve you need to look at other criteria related to the embedding degree. You can read this paper by ...


8

Yes! You can use the ephemeral key derivation mechanism that is for example used in Monero (they call it stealth keys there). Consider public key $A=aG$, with private key $a$. Then, a derived key can be generated, parametrised by the random scalar $r$: $$A'=H_s(rA)G+A$$ and the party that knows $a$ can use the public parameter $R=rG$ to compute their ...


8

The leading 04 byte is specified by the SEC standard (which is based on the ANSI X9.62 standard). It indicates that the public key point is not compressed. If the key is compressed, it uses 02 or 03 as leading byte depending on the lower bit of the y coordinate. EdDSA public keys do not use this byte for two reasons: It always uses compressed points; there ...


7

Opening and sealing a box involves your private scalar and the other party's public key. So the private key is simply the private scalar. Signing with Ed25519 involves your private scalar and your public key (to strictly bind the signature to that key). Since computing the public key from the private scalar is expensive, NaCl chooses to store it as part of ...


7

Yes, this is possible using Hierarchical Deterministic (HD) Keys. There are 2 variations for key generation, hardened and non-hardened. In hardened, generating child keys (both public and private) requires knowledge of parent private key but in non-hardened, child public key can be generated using parent public key. You need non-hardened key generation. The ...


6

You could try the 112-bit secp112r1 cited in [1]. Before you do this, the problem with that paper is they actually show how to break the discrete log problem on this curve! And this was back in 2012. So any export-strength implementation of ECC is definitely breakable by governments, research groups and sufficiently determined/resourceful commercial ...


6

Any key generation algorithm for any cryptosystem is going to be weak if the attacker can predict what seed was used to generate the key. They can just generate the same key. However, assuming the the random number generator is not that bad, different algorithms start to look different. If you are just using the output of the random number generator as a ...


Only top voted, non community-wiki answers of a minimum length are eligible