# Tag Info

15

The answer is about the difficulty of discrete logarithm. The notion of isomorphism does not capture all that matters in cryptography; we also need to consider computing costs. Suppose that we have an abelian group $\mathbb{G}$ with additive notation. Let $G$ be a conventional element of $\mathbb{G}$ of order $n$. The subgroup generated by $G$ is: $$\langle ... 14 Let's assume that everyone agreed on some elliptic curve and a public base point g somewhere on the curve. When two parties Alice and Bob want to agree on a shared secret, they proceed as follows: Alice chooses some random number a and applies the curve operation to g, the public base point, a times. She obtains some result ... 14 Some claim that Curve25519 has 112 bit security, others that it has 128 bit security; which is it? Well, actually, neither - it's actually somewhere in the middle. For a curve without known weaknesses (and Curve25519 doesn't have known weaknesses), then if the curve order has a large prime factor around 2^{2k}, then the best known attacks against it ... 9 Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form x_i = a_iP + b_iQ until we find a distinguished one, i.e., one that shares some common property (like the lowest k bits of x_i set to 0). We accumulate enough distinguished points until we find a ... 8 If that were possible, that is, if you could take an x-coordinate, and find the private key k such that kG has that x-coordinate, well, you've just solved the discrete log problem. If you can do that, you've just shown that the curve is insecure. If you're thinking "I'm not specifying the y-coordinate; doesn't this make it easier than the discrete log ... 8 There is a rather deep polynomial-time algorithm for counting the \mathbb F_q-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas: The number of points is closely linked to a functional equation$$ \varphi^2-t\varphi+q = 0 ...

7

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem): Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$. Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. ...

7

These are "red flags". No one knows of a specific exploit, only some possible reasons to be concerned that one might exist. Since no one knows of a specific attack, we can't possibly know how much speedup such a hypothetical attack might allow. Basically, you're asking for speculation where there is not enough information to allow meaningful speculation, ...

7

ECC is indeed used by CloudFlare's website but only for the session key agreement. The authentication is performed using an RSA 2048 bit private key. The corresponding RSA public key is in the certificate. In other words, although ECC is being used, it is not used for authentication and therefore not part of the certificate. The ciphersuite is: ...

7

First off, your equation is correct and there seems to be no calculation mistake. To understand on how to get from $$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$ to $$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}$$ one first needs to observe that $e=(d-2)/(d+2)=121665/121666$ holds. The next step is to consider: "What operations are actually allowed with birational ...

7

If I understand your question correctly, you are essentially asking if points in Edwards and Montgomery curves can be represented in Weierstrass coordinates. This is true; in fact, any elliptic curve over a prime field can be represented in Weierstrass form $\mathcal{E}_{w}^{a, b} : y^2 = x^3 + ax + b$, and by extension its points can too. The question, ...

6

Yes, there are a few reasons to prefer ECDH over RSA: ECDH will perform much better; ECDH can provide forward security when used with ephemeral key pairs without a large performance overhead for creating those key pairs; ECDH should be impervious to most oracle attacks, i.e. timing based padding oracle attacks on OAEP. For the forward secrecy you require ...

6

Non-Adjacent Form (NAF), also called Balanced Binary Representation (BBR), is a representation of integers reminiscent of binary, but with an extra $-1$ value for digits, and such that at least one of two adjacent digits is $0$. Because the resulting representation has at least half of its digits at zero (typically about $2/3$), it can be used to speed-up ...

6

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = ... 6 SHA-1 is still thought to be secure whenever collision resistance isn't required. The hash is both used for signing certificates and ECDHE public keys. There's however a difference with regard to collision attacks. It is possible for an attacker to attack the collision resistance with certificates by getting their own certificate signed by a CA. In ECDHE ... 6 Yes a brute force key-guessing attack would be faster, but: It would be ridiculously slow for either. E.g. see this for 256-bit keys. There are faster attacks on both and those attacks break larger RSA sizes than ECC sizes. Related: Why can ECC key sizes be smaller than RSA keys for similar security? 6 A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ... 5 It is possible to find the desired values in an acceptable amount of time. TL;DR: Find the curve order, factor it, select a (random) point until you have one with the desired order and calculate the cofactor as quotient of curve and point order. First, you can use yyyyyyy's answer to find the order$n$of the described curve using Schoof's algorithm. ... 5 The following is more or less a copy-paste of a comment I made on the related ArsTechnica thread. Indeed, StackExchange is probably one of the better places to debate this. A few reminders first: there are approximately$p$elliptic curves over the finite field of integers$\pmod{p}$; of these curves, only those with (almost) prime order are of ... 5 You might want to checkout Wikipedia page of elliptic curves to get a basic overview. The difference between DH and ECDH is mainly the group which is being chosen to compute the secret key(s). While DH uses a multiplicative group of integers modulo a prime$p$, ECDH uses a multiplicative group of points on an elliptic curve: Alice and Bob agree on an ... 5 In short: the question does not explain well the notion of asymmetry in ECC; and the exposition is not how Elliptic Curve Cryptography works. A reasoning sidestepping the notion of Discrete Logarithm Problem over a finite group can not really explain asymmetry as meant in ECC. Asymmetry is in the knowledge Alice and Bob have about the key, not asymmetry of ... 5 After a multiplication you have a number with$2 \cdot 255$bits. Since$2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an equivalent number smaller than$20 \cdot 2^{255}$. Repeat this to get a number that's smaller than$2 \cdot q$. Now check if the value is greater or equal to$q$and ... 5 To generate your pair of keys with elliptic curves first you have to chose your domain parameters (I think this name may comes from the P1363 naming convention, or perhaps it's previous). Those domain parameters will be public. For example for curves over finite fields those parameters are:${p,a,b,G,n,h}$. The lower level operations will be made in ... 5 We, for the most part, don't bother with elliptic curve-based pseudorandom generators. DUAL_EC_DRBG was shoehorned into a NIST standard that also included a block cipher generator, CTR_DRBG, and two hash-based ones—Hash_DRBG and HMAC_DRBG—that are actually used in the field. Number-theoretic generators, which include Blum-Blum-Shub, DUAL_EC_DRBG, and ... 5 Bits of entropy The assumption for all cryptographic operations is that a random key of n bits has n bits of entropy. If it doesn't (due to PRNG defect or implementation error) then the key will be weaker than expected but the underlying assumption of all cryptographic primitives is that an n bit key has n bits of entropy. This is the same for all types ... 5 Any key generation algorithm for any cryptosystem is going to be weak if the attacker can predict what seed was used to generate the key. They can just generate the same key. However, assuming the the random number generator is not that bad, different algorithms start to look different. If you are just using the output of the random number generator as a ... 5 I'll consider that you are using a 256-bit curve per ANSI X9.62:2005. Not all 256-bit bitstrings are a formally valid private key; when using big-endian conventions, these must represent a positive integer less than$n$, the order of the largest prime order subgroup. For the Koblitz curve secp256k1 of SEC 2, ... 4 Let$x\in\mathbb Z/p\mathbb Z$be the point's first coordinate, and define$z := x^3+ax+b$. We know that there exists a square root$y\in\mathbb Z/p\mathbb Z$of$z$, i.e.$y^2=z$. Let's assume we have already found such an$y$. Since the order of$(\mathbb Z/p\mathbb Z)^\ast$is$p-1$, Lagrange's theorem implies$y^p=y\text,$hence ... 4 In the usual definition of security of Elliptic Curves, curve25519 security is in fact 126 bits. If look at safecurves's rho page you can see the rho complexity for curve25519 is$2^{125.8}\$ in accordance to what you say. Curve25519 author basically doesn't accept that definition of security. In the Curve25519 paper he states in section 1: Every known ...

4

The encryption part of NaCl is older. I think NaCl itself still doesn't have official signature support. NaCl's box uses montgomery form public keys together with the montgomery ladder. This ladder only returns the x-coordinate of the result and thus is not compatible with most signature algorithms. Ed25519 on the other hand uses (twisted) edwards form, ...

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