New answers tagged

2

It's not harder. Solve the DL problem to get $x$ in $Q=x.P$. $Q = \sum_{i=1}^{n} x_i.P = (\sum_{i=1}^{n} x_i).P= x.P$ => any set of $x_i$ that sums to $x$ (modulo the group order) is a solution to ECFP.


2

The fact is that the discrete logarithm problem (DLP) is solved using different algorithms in the cases of multiplicative groups (where normal DH applies) and elliptic curves (where ECDH applies). The behavior of these algorithms is quite different. For multiplicative groups, where the NFS for logarithm is used, a huge part of the computation depends only ...


10

This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup $H$ of group $G$ divides the order of $G$. Since orders are elements of the ring of integers and since this is a principal ideal domain, unique factorization exists and primes make sense. Or put another way, ...


5

Yes, the attack you sketched out would work - in theory. In practice, it's an efficient (computable in polynomial time) mapping $\psi:E\rightarrow\mathbb Z_n$ we're lacking. As for the unefficient mappings, $\psi:x\cdot P\mapsto x$ would be perfectly fine theoretically, but we don't know how to calculate it (it's the elliptic curve discrete logarithm ...


1

In this state we have well known attack that is called invalid-curve attack. Let $E:y^2=x^3+ax+b$ and $E':y^2=x^3+ax+b'$ be two elliptic curves with reduced Weierstrass form. $E'$ is called an invalid curve relative to $E$. Since formulae for adding and doubling points on $E$ does not involve coefficient $b$ thus addition law for $E$ and $E'$ is same. In ...


1

There can be much simpler methods than CM for group orders of a specific form. For exemple if $p \equiv 2 \pmod 3$ and $b \not\equiv 0 \pmod p$, the curve $Y^2 = X^3 + b$ over $\mathbf{F}_p$ has $p+1$ points. (The proof of this is easy and left as an exercise.) Such methods are also used to easily construct "good enough" pairing-friendly curves. As Thomas ...


7

There is a method known as "Complex Multiplication". However, it is not simple at all, and tends to be overly expensive for most target orders. See this article for some details. There is also the (theoretical) concern that a curve constructed that way may have a special structure though could possibly be leveraged into an attack one day; generally speaking, ...


1

The Rho method is probabilistic, so it's possible you could find the solution within the first few iterations, or after you've generated almost the entire space. The probability starts getting in your favor around the square root of the order, because that's when the probability reaches approximately 50%. Since the probability increases quadratically, it's ...


2

If attackers can strip off RSA / EC / -DSA digital signature and conduct CCA on AES-CTR or CBC payload, why can't they do the same for AES-GCM? The scenario, you're talking about is iMessage or Signal Protocol or other protocols which allow optionally to sign the ciphertext and thereby don't MAC it. The problem here is a) that you could replace the ...


0

The problem with non-authenticated symmetric cipher modes is that they are PRP's. That means that - no matter what you do to the ciphertext - you'll get a valid and unique plaintext (not considering unpadding). This means that an attacker can change (part of) the outcome of decryption by altering the ciphertext. It can also lead to information leakage, e.g. ...


5

Let's suppose that you want to generate a classic $n$-bit curve in a prime field, with the complete curve order being prime. The process goes about thus: Get a prime $p$ of size $n$ bits. The curve will be defined in the field of integers modulo $p$. For all we know, you can use $p$ to have a "special form" that promotes more efficient computations (e.g. ...


0

Theorem : Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$. Then $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined recursively by $V_0 = 2, V_1 = t$, and $V_n = V_1V_{n−1}−qV_{n−2}$ for $n ≥ 2$. with above theorem you can find elliptic curve with $n$-bit order. Let $E:y^2+xy=x^3+x^2+1$ be ...


2

No, you do not add the ASN.1 encoding to the hash when generating an ECDSA signature. There are two reasons for this: The first is that there is no room, if we select a curve and a hash with equal security. To be secure against attacks that take $O(2^N)$ time, a curve needs to have a prime that's at least $2N$ bits; to be secure against collision attacks ...



Top 50 recent answers are included