Hot answers tagged

7

Is it possible to retrieve $x_1$ and $x_2$ in this scenario? Yes. We multiply each equation by it's corresponding $k_i$ and reformat, giving $$\begin{array}{rrrrrrr} s_1\,k_1&&-r_1\,x_1&&\equiv&h_1&\pmod p\\ s_2\,k_1&&&-r_1\,x_2&\equiv&h_2&\pmod p\\ &s_3\,k_2&-r_2\,x_1&&\equiv&h_3&\pmod ...


6

The original paper (Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA), International Journal of Information Security volume 1, 2001, pp. 36–63) is surprisingly quiet about the rationale for all of these. Check that $Q_a$ is not equal to the identity element $O$, and its coordinates are ...


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


5

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

This isn't completely standard terminology, so you should check the precise definitions in your lecture notes. But I can't think of anything else that the exercise should be. You have a definition of the DSA signature process: given some parameters $(p,q,g)$, a private key $x$ and a message $m$, generate a nonce $k$ and calculate $(r,s)$ given by a certain ...


5

ChainOfFools (or Microsoft's Chain of Fools) or CurveBall is a vulnerability in Microsoft's X.509 certificate verification affecting certificate chains that use ECDSA at any point, discovery by NSA!1. From Microsoft site for CVE-2020-0601 An attacker could exploit the vulnerability by using a spoofed code-signing certificate to sign a malicious executable, ...


4

ECDSA is specified in SEC1. It's instantiation with curve P-256 is specified in FIPS 186-4 (or equivalently in SEC2 under the name secp256r1), and tells that it must use the SHA-256 hash defined by FIPS 180-4. I'll leave aside ASN.1 decoration (since the question uses none), conversions between integer to bytestring of fixed width (which all are ...


4

It is not possible: Let $d_A, d_B$ be distinct private keys. Then $$ s=k^{-1}(z+rd_A)=k^{-1}((z+r\;(d_A-d_B)) + rd_B) $$ So the pair $(r, s)$ is not only a valid signature for the public key $d_AG$ and the (partial) hash $z$, but also for the public key $d_BG$ and the message hash $z+r\,(d_A-d_B) \pmod n$. So in many cases (if there are no restrictions ...


4

As pointed out by @SEJPM, you can read more about security proofs for DSA/ECDSA family on this thread. As for whether there exists an interactive protocol corresponding to DSA/ECDSA à la Schnorr identification/Schnorr signature, not that I am aware of. I would add that this is unlikely for two reasons: The (unfortunate) reason for coming up with DSA/ECDSA ...


4

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


4

The danger of revealing results in protective coordinates is pointed by David Naccache, Nigel P. Smart, and Jacques Stern's Projective Coordinates Leak, in proceedings of Eurocrypt 2004. As noted in comment, a concise re-exposition is in section 3 of Alejandro C. Aldaya, Cesar P. García and Billy B. Brumley's From A to Z: Projective coordinates leakage in ...


3

I am asking myself whether there are use cases were a fast signature verification is an important requirement and were RSA would be actually the preferred choice? Well, as you already mentioned the comparison is a bit tricky. For 128 bit security you'd use ECC-256 and RSA-3072 (and using 3072 is on the low end). For most RSA implementations 3072 seems at ...


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

In ECDSA one randomly selects the private key $d_A$ from interval $[1,n-1]$, where the $n$ is the order of the Elliptic curve with $n-1$ non-trivial points, and with the point at infinity, $\mathcal O$ as the trivial point. $n = \texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}$ that is 64 bytes, or as an integer $n = ...


2

Why does $p$ need to be a prime number? That's necessary for arithmetic modulo $p$ to be a field. For non-prime modulo, we only get a ring. That's important because we want to compute modular multiplicative inverses, and need a field for that to work consistently. More specifically: if $q$ is such that $0<q<p$ and $\gcd(p,q)\ne1$ (which is possible ...


2

However, suppose that you are aware of public key $K$ and are looking to do a tweak of $K$. Let $t$ be the tweaking factor, and so $tK=K'$. If you then wanted to prove that you are in possession of $t$, how would you do that? The obvious way to do this is a Schnorr proof of knowledge, which does precisely what you're looking for; given a public $K, tK$, it ...


2

No, the 00 simply indicates how many least significant bits are not used in the last octet of the BIT STRING. As the bit string contains an octet string (consisting of the sequence of two integers) it will always be zero, as all the bits in the BIT STRING are used. This is defined for the BER/DER encoding of BIT STRING itself. As for why the signature is ...


2

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? No. If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification. However, only the signature generated with the EdDSA signing ...


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

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


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

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

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


1

If the only change you make is removing the hashing step, things certainly fall apart. Using the description from Wikipedia you used in your question, this would mean to replace the first step with $e := m$ and then continue with the rest of the steps unchanged. The second step would then define $z$ as the $L_n$ leftmost bits of $m$. Thus, any messages that ...


1

I will first address the issues of the diagram; Encryption part Although the encryption is mentioned as optional there is no mention of how the AES key is generated. The common method is the Diffie-Hellman Key Exchange and the Elliptic Curve version of it is preferred ECDH. there is no mention of the mode of operation. CBC, CTR, GCM,... etc. There is no ...


1

It turns out this is possible and has been implemented in the libolm library of Matrix. The solution adopted in this library is to generate a signing key for each user. This is an Ed25519 keypair, which is used to calculate a signature on an object including both the public Ed25519 signing key and the public Curve25519 identity key. It is then the public ...


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