We changed our privacy policy. Read more.

Hot answers tagged

10

Is X25519 and Ed25519 the same curve? No. X25519 isn't a curve, it's an Elliptic-Curve Diffie-Hellman (ECDH) protocol using the x coordinate of the curve Curve25519. Ed25519 is an Edwards Digital Signature Algorithm using a curve which is birationally equivalent to Curve25519. Is X25519 used by ECDSA? No. It's not a curve, it's an ECDH protocol. What does ...


5

What is the security level of DSA algorithm when q is a 224 bit prime? About 112-bit, at most. More precisely, there's an attack recovering the private key from the public key, by solving a Discrete Logarithm Problem, costing roughly $2^{113}$ modular multiplications, and little else: the attack can be efficiently distributed and requires little memory. See ...


5

EdDSA is not ECDSA over a different curve. Rather, it is a type of Schnorr signature. Indeed the name is very confusing, and I'm pretty sure that it was chosen in order to give this impression, since Schnorr is less well known. Schnorr is essentially a zero-knowledge proof of knowledge of the discrete log of the public key, obtained via the Fiat-Shamir ...


5

I was expecting that the signature verification will be faster than the signature generation Because signature verification is faster in RSA? Well, as you can see, RSA != ECDSA; the operations involved in both signing and verification are completely different. what makes the signature generation faster ? Because signature generation involves only one ...


4

For example, I could use: If the discrete log is already backdoored with the standard base point $G$, then changing the base to another point on the curve doesn't solve this issue. Let you know that $G$ is backdoored and you changed the base to $G' \neq G$. Then the entity that created the backdoor can use this to find the private keys. Let $P = [k]G'$ be a ...


4

TL;DR There are no standards or RFCs that use this idea. There is a slightly improved number field sieve attack on your example number based on back of the envelope calculations (see below). Your proposed generator would be fine. The follow on proposal should not admit special polynomials for $\ell\ge 768$. The back-of-the-envelope generic attack To attack ...


4

How does this attack works on the high level? Resource sharing on multicore CPUs has benefits like low cost and efficiency. This, however, is the attack point that we saw over the years. With the cache attack, the victim's data extracted with cache manipulations. The countermeasure against the various cache attacks is disabling simultaneous multi-threading (...


4

TL;DR: the signature verification process in ECDSA is very different from the one in RSA. The question's description of these signature schemes is incorrect for ECDSA, approximate for RSA. Alice who holds the private key is able to encrypt a message into a signature. That's incorrect terminology. Alice who holds the private key is able to sign a message, ...


3

Per the notation of the wiki article, all signatures produced with the same random k would lead to the same value r which is published as part of the signature.


3

The video (at least, where the question links) illustrates the Baby-step/Giant-step Discrete Logarithm method in the multiplicative group modulo $p$, for prime $p$. That is the set $\{1,2,\ldots,p-2,p-1\}$, under the internal operation multiplication modulo $p$. This group has essentially nothing to do with an Elliptic Curve group. The principle of Baby-step/...


3

You can. Low-embedding degree may be bad due to the MOV attack, but pairing-friendly curves are particularly chosen so that the embedding degree is low but still enough to not decrease security. So any elliptic curve algorithm should be safe on the curve, not only pairing-based ones. Some observations: ECDSA if often used with NIST curves with cofactor 1. ...


3

Indeed, the industry-standard specification of ECDSA has a step (5) requiring to reject the signature if the point at infinity is encountered. This condition can happen at least If the holder of the private key generated a suitable (invalid) signature, with $r=-e\,q_u^{-1}\bmod n$ or something on that tune. Granted, that reveals the private key, and (thus) ...


2

If the attacker has the ability of choosing the private key, then he can create a valid signature $(r,s)$ with a target value for $s$ for any message $m$. The attack works in the following way: The attacker choose its target $s$, generates a random ephemeral key $k$ and computes the hash of the message $e = H(m)$. Then the attacker computes the scalar ...


2

Can someone help with an example? Ok, here's a simple example; suppose we precompute a table that contained all the points of the form $(a \cdot 256^b) G$, for $0 < a < 256$ and where $b$ be within the scalar we intend to support. For example, the table (if we support 2 byte scalars) would contain the points $\text{0x01}G, \text{0x02}G, …,\text{0xff}G,...


2

You're wrong. This is a difference between TLS 1.2 and 1.3. In 1.2 SignatureAndHashAlgorithm identifies only the algorithm (not curve) and hash. In 1.3 SignatureScheme does identify the curve for ECDSA, and the certificate OID for RSA-PSS. See the next to last para on page 44: [1.3] ECDSA signature schemes align with TLS 1.2's ECDSA hash/signature pairs. ...


2

Using the notation there, ECDSA signature generation requires a single Elliptic Curve point multiplication, $k\times G$. Whereas naive signature verification uses two, computing $u_1\times G$ and $u_2\times Q_A$ before adding them. Point multiplication is typically by far the slowest operation in signature generation/verification, beside perhaps the hash (...


2

The truthful answer here is that I don't know. I am pretty sure actually that the better answer is that this is unknown. The assumption that the hash is only required for collision resistance is blatantly false, since typically one needs a random oracle for such schemes. In ECDSA specifically, we don't have actually have proof of security even with a random ...


2

However, I'm confused by what I should do with two different messages ($e_1 \ne e_2$) with the same $s_1$ and $s_2$ Well, if we consider how $s$ is computed: $$s_i = m^{-1} ( \text{hash}(e_i) + r \cdot k )$$ If $s_1 = s_2$, then (because the private key $k$ is the same in both cases, and $m$ (the secret nonce) and $r$ are assumed to be the same, we have $\...


2

To obtain (62, 4) you just add points $\textbf{but on elliptic curves}$. This is different from a "regular" addition, since the result must be a point of the curve (or a point said to be at infinity, I'm not explaining I try to keep things simple) . Addition is defined and to do so either you use the heavy addition formulas (If you have seen groups ...


2

The algorithm would work fine without the restriction, although it's debatable whether NIST owns the name DSA and you would have to call it something else, the way non-RSA-licensed implementations of RC4 were for a long time called ARCFOUR (alleged RC4) or similar. How about Schnorr Patent Evading Digital Signature SPEDS? Why did NIST do it (originally, see ...


2

Yes, this is secure provided the message to be signed is unique on each login to prevent replay attacks. Usually that's done with either a random challenge or the signature over a shared secret. In fact, SSH does this already with ECDSA keys: the two sides agree on a shared secret, which is hashed, and the client signs the hashed secret and some other data ...


2

I have to be honest and say that I never really understood why systems use the signature as the record rather than just the hash of the message that was signed. If that was used, then there would be no problem with using malleable signatures. If someone has a reason why not to just do what I said, please let me know and I'll change the answer. More to the ...


2

I had emailed Dr Thomas Pornin the very same question and received his reply. With his permission I cross post his answer as followed From: "Thomas Pornin" ... Date: 2021/04/22 11:38 Q1: Additional data k' is concatenated after bits2octets(H(m)) in HMAC input in step d. May we also need to concatenate k' after bits2octets(H(m)) in HMAC input in ...


2

But is it necessary? What is necessary is that someone else could not guess what $k$ was; after all, if they guessed that, they could recover the private key from the signature with a bit of simple algebra. If they used only public information (the public key and the message), well, the attacker could compute $k$ himself, and that'd be bad. Of course, you ...


2

The existing security proofs for DSA and ECDSA require k to be chosen uniformly at random. HMAC_DRBGB is already an approved CSPRNG for use in either signature scheme. So this just changes the instantiation and entropy source, making it a minimal change for existing implementations to add. See section 3.5, "Rationale"


2

The short answer is: There is nothing wrong with the idea. The main reason I did not attack successfully after changing sign is because there was an optimization in TPM-FAIL paper. It eliminates the first signature by some transformation. This could decrease the dimension of lattice by 1, which increase the calculation speed slightly. The result of ...


2

First, note that $g$ is not the generator of the full cyclic group $(\mathbb Z/p\mathbb Z)^*$, but of a cyclic subgroup of order $q$. As such then we can only see at most $q$ possible $r$ values and we expect to see any given $r\pmod q$ value roughly Poisson(1) times.This does mean that we do expect roughly $(1-2/e)q$ $r$ values corresponding to more than ...


2

But the question is, can the Chinese remainder theorem in ECDSA be applied to the parameters in secp256k1? That precise attack doesn't work - we don't use the Chinese remainder theorem when computing with secp256k1 (as the group order is prime). On the other hand, there are certainly side channel attacks available against naïve implementations of ECDSA and ...


1

A general commitment scheme consists of two pharse: commitment phase: the sender encrypts a message to a commitment value by using one-way function with some random values, such as the coin tosses r in your post. This pharse can make sure that no malicious receiver gain any information about the message. decommitment phase: the sender should transmit some ...


1

Normally, coin tosses are random variables $r$ drawn (usually uniformly unless otherwise specified) from a finite set $R.$ In this case however $R=g^{k^{-1}}$ where $r=H’(R)$ and $H’$ is a hash function from a cyclic group of prime order into $Z_q$ and $k$ is a uniformly distributed random variable from $Z_q.$ So $R$ is a random variable which is a function ...


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