# Tag Info

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

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

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

3

First of all, let us simplify the equation by replacing things that the attacker can compute with known constants. We come up with: $$a \cdot b^x = y$$ where the attacker knows $a$ (which is $e(g,h)^k$) and $b$ (which is $e(g, h)$, which he can compute, as he knows $g, h$), and the attacker solves for $x, y$. If it is sufficient for an attacker to find a ...

3

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

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

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

2

I am really not sure about what you are trying to do. If you simply want to prove that $Ans = e(g,h)^k \times e(g,h)^r$ is hidden given only $(g,h,e(g,h)^k)$, then this is trivial and does not require any hypothesis at all (in particular, no discrete logarithm problem is involved). Indeed, this is perfectly equivalent to the problem of finding $e(g,h)^r$ ...

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

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

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