7
Suppose you publish a public key $P = [n]G$ for a secret scalar $n$, where $G$ is the standard base point.
If you are willing to tell me $H([n]Q)$ given $Q = (x, y)$ for any coordinates $x$ and $y$ of my choice, then I can send you a point $Q$ of (say) order 2 on some other curve whose arithmetic law happens to coincide with the curve you meant to use, and ...
5
I would appreciate an example showing how to find such a curve $E'$ and a point $R$ for some "popular" $E$ (e.g. one of the NIST curves).
I won't actually work out the example (it's a bit more work than I feel like doing at the moment), however I will walk you through the steps:
Pick a random $b'$ value, and so we have the curve $E' : y^2 = x^3 + ax + b'$
...
3
Don't use SHA-1.
There's unlikely to be a substantive difference between the other choices, as far as you're concerned, except performance:
SHA-256 is might be cheaper on 32-bit CPUs; SHA-384 and SHA-512 are cheaper on 64-bit CPUs.
NIST P-256 is likely to be cheaper than NIST P-384 which is likely to be cheaper than NIST P-521.
All of these choices ...
3
Is there an efficient algorithm for finding curves with small order points?
Yup, just choose a curve at random and you will find one soon enough. Example with P-256 in Pari/GP.
First create the curve and check that its order matches the expected one just to be sure:
(00:31) gp > p = ...
3
Yes. In fact, you can write the Weil and Ate pairings in terms of the Tate pairing.
Let $E$ be a curve over $\mathbb{F}_p$ of embedding degree $k$ and prime order $r$. The Weil pairing is related to the Tate pairing as
$$
e(P,Q)^\frac{p^k - 1}{r} = \frac{t(P, Q)}{t(Q, P)}\,,
$$
where $t(\cdot,\cdot)$ is the Tate pairing. Likewise, we have
$$
a(Q, P)^{kp^{k-...
3
It's the size of the prime number of the underlying field in G1, G2 and GT.
In BN256, G1 is $E(\mathrm{GF}(p))$, G2 is a subgroup of $E(\mathrm{GF}(p^{12}))$ (or $E'(\mathrm{GF}(p^{2}))$ when using a twist) and GT is a subgroup of $\mathrm{GF}(p^{12})$.
Elements of G1 requires the same number of bits as $p$ for each elliptic curve point coordinate. Note ...
3
Here is what's likely going on:
Charm represents Elliptic Curve points in affine coordinates, that is, explicit (x, y) values
When doing a single point addition, OpenSSL adds the two points (internally coming up with a point in projective coordinates) and then converts them back into affine coordinates. Then final conversion involves a modular inverse ...
3
I invented SIDH. $E_0[\ell_A^{e_A}]$ has cardinality $(\ell_A^{e_A})^2$. Each of $P_A$, $Q_A$, and $R$ has order $\ell_A^{e_A}$ and they all generate different subgroups. This is possible because $E_0[\ell_A^{e_A}]$ is a non-cyclic group.
3
The order of a point on $E(\mathbb F_p)$ merely divides the cardinality $\#E(\mathbb F_p)$ (or $|E(\mathbb F_p)|$) of the group. If $\#E(\mathbb F_p)$ has composite order, it may have small prime factors and therefore there may be low-order points that don't generate all of $E(\mathbb F_p)$. For example, on any Montgomery curve $y^2 = x^3 + A x^2 + x$, the ...
2
If $L[\alpha, c] = e^{(c + o(1)) \cdot (\log p^n)^\alpha \cdot (\log \log p^n)^{1 - \alpha}}$ then $$\log_2 L[\alpha, c] = (c + o(1)) \cdot (\log p^n)^\alpha \cdot (\log \log p^n)^{1 - \alpha}/\log 2.$$
Let $p \approx 2^{256}$ and $n = 12$ so that $\log p^n \approx 12\cdot256\cdot \log 2 \approx 2130$; and let $\alpha = 1/3$, $c \approx 1.54$. Then, if we ...
2
But in many places I saw that BN256 curve provided 128 bit security. Where I am doing wrong?
There are two potential attacks against the DLog problem in BN256
The first is to attack the DLog problem in the finite field; that is, given the points $G$ and $H$, we compute $e(G, G)$ and $e(G, H)$, and then find the value $x$ with $e(G, G)^x = e(G, H)$.
The ...
2
A group if a set of elements and some operation that satisfy some requirements. This operation is usually called "addition" or "multiplication", depending on the group, even though it may not be actually the classic addition or multiplication. The integers $0 < x < p$ for some prime $p$ form a group under the modular multiplication operation (multiply ...
2
You appear to be under the impression that Elliptic Curve groups are always cyclic, and that there is only one subgroup of a given order.
That is not the case, and it is most definitely not the case in the groups we use for isogenies. There are a huge number of subgroups of the same order; hence just knowing the subgroup order doesn't tell you which ...
2
Yes, they refer to the same curve. I'm not sure why the equations' different, but I believe that's just a transcription error. The 04 in basepoint is just standard way to encode a point in SECG #1.
EDIT: (Answer extracted from the comments)
In the SECG case:
a = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 ...
2
The private keys are integers $x$ with $2^{254} \leq x < 2^{255}$ and $x \equiv 0 \pmod 8$, or just $x \in 2^{254} + 8\{0,1,2,\dots,2^{251} - 1\}$, so there are exactly $2^{254}/8 = 2^{251}$ of them.
2
In the particular case of jubjub, it will be used in a Rank-1 Constraint System(R1CS) where inversion is cheap, costing one multiplication.
Jubjub is an embedded curve and the main purpose of developing it, is due that you can use it in a constraint system. Outside of its applications in R1CS, inversion is not cheap.
Since inversion is cheap, we can use ...
1
The attacks on RSA and Elliptic curve cryptography(ECC) are based on Shor's quantum algorithm which is used for integer factorization in the context of RSA.
Correction: Note that, as pointed out by @yyyyyyy in the comments, Shor's algorithm for DLP does not factor; neither is it based on finding the order of an element (which is usually known anyway in a ...
1
In $\mathbb{Z}_p$ all points $c\neq 0,$ are invertible.
Choosing any $c'\neq c$ will give you $c-c' \neq 0,$ thus it will be invertible.
1
The good thing about standards is that there are so many to choose from.
The P-192, P-224, P-256, P-384 and P-521 names come from the FIPS DSS (Latest version of which is FIPS 186-4):
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
The secp224r1, secp384r1 and secp521r1 names come from SEC2:
https://www.secg.org/sec2-v2.pdf
The prime192v1 and ...
1
As pointed out by @yyyyyyy, every curve does have an embedding degree, i.e., there is some $k$ for which $p^k - 1$ is a multiple of $r$, the order one of the subgroups of a curve defined over $\mathbb{F}_p$.
There is a relevant result from Koblitz and Balasubramanian that establishes that the probability that the embedding degree of a random $n$-bit curve ...
1
Generally, with cryptosystems based on secp256k1, a private key is a secret scalar $n$—an integer $n$ in the range $0 \leq n < \ell$ where $\ell$ is the order of the group, which for secp256k1 is a little under $2^{256}$—and a public key is a point on the curve obtained by repeatedly adding a standard base point $G$ to itself $n$ times, $$[n]G = \...
1
My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?
Not particularly; the factorization of $p-1$ is not specifically relevant to the strength of a curve over $\operatorname{GF}(p)$.
Now, it is quite relevant to the strength of the group $\mathbb{Z}_p^*$; ...
Only top voted, non community-wiki answers of a minimum length are eligible
