18

Let's assume I need to encrypt data only for one minute, after that time the data is useless. Couldn't I still use ECC2K-130 as it would require 525600 times more PlayStations to crack it in a single minute instead of a year? !!! NO !!! Decryption by an unauthorized party could occur within a fraction of a second following the release of the ciphertext. In ...


17

How is the set of discrete points on elliptic curves determined for ECC applications? One common method to define a point on an elliptic curve over a suitable finite field $(\Bbb F,+,\cdot)$ is that such point is one of any pair of coordinates $(x,y)$ with $x$ and $y$ elements of the field that obey an equation $y^2\,=\,x^3+a\cdot x+b$, where $a$ and $b$ ...


15

It is an open standard by IETF.org We can find the details in the mail archive of IETF, D. J. Bernstein's response; It has become increasingly common for "Curve25519" to refer to an elliptic curve, while the original paper defined "Curve25519" as an X-coordinate DH system using that curve. "Ed25519" unambiguously refers to an ...


12

What is the minimum, secure enough, certificate that you can build? How could I generate it using OpenSSL? Generally you'd need to flatten certificates if you want to go below 256 bytes. X.509 version 3 certificates have a certain overhead due to the ASN.1 tree structure. So those are not as efficient as they could be. For smart card systems generally so ...


11

The points on an elliptic curve are not discretized, they're discrete by definition. An elliptic curve is the set of $(x,y)$ such that $y \odot y = (x \odot x \odot x) \oplus (a \odot x) \oplus b$, where $\oplus$ is something we consider to be “addition” and $\odot$ is something we consider “multiplication”, and $a$ and $b$ are two constants. You can write ...


11

(1) I'm curious whether the following 10 different DH Groups are the only groups that TLS 1.3 supports, Yes, in the sense that TLS 1.3 only allows groups that are explicitly declared as supported in 1.3. This currently includes not only the groups from RFC 8446, but possibly more recent RFC as well, such as Brainpool curves from RFC 8734. The TLS supported ...


9

The general rule for curves is given in; 2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone They defined a point is valid if $P \neq \mathcal{O}$ The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field. $P$ satisfies the curve equation - against the twist ...


8

Let's call the problem Square Diffie-Hellman (SDH). SDH is at least as hard as CDH in groups of known order and the reduction goes as follows.$^*$ Given an adversary $\mathsf{A}$ that breaks SDH, our goal is to construct an adversary $\mathsf{A}'$ that breaks CDH. Given the CDH challenge $(g,g^x,g^y)$, $\mathsf{A}'$ runs $\mathsf{A}$ thrice -- first on $(g,g^...


8

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections? If you could create such a rainbow table that allows you to compute discrete logs of random values to a base $G$ with nontrivial probability $p$, then you can solve the discrete log to any base (with work that takes an expected $O(1/p)$ time. ...


8

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


8

$y^2 = x^3 + ax + b\bmod p$ is the Short Weierstrass equation. The theory behind it is here Using Bezout’s Theorem, it can be shown that every irreducible cubic has a flex (a point where the tangent intersects the curve with multiplicity three) or a singular point (a point where there is no tangent because both partial derivatives are zero). [Reducible ...


7

There are two questions here: What's the minimum, and what's the minimum standard certificate you can build. The former is shorter than the latter, as noted in Maarten Bodewes' answer. If you're willing to go beyond what OpenSSL supports, you can modify the client and server to only send/receive the non-constant bits of the certificate, and hard-code the ...


7

Is this correct? The principles are right, but a number of details are missing. Among these: For RSA "Encrypt the file" can't be with AES only, since that's a 128-bit block cipher, and it would be insecure past 16 bytes. There is an operating mode involved, and likely it involves generation of an Initialization Vector. It's a good idea to use ...


7

No (See 2.). An alternative way to test a library could be to change the base point. You can find the point with x coordinate equal to zero, multiply it by a random $r$ and then use the result as the base point of ECDSA with $k=r^{-1}$. This is equivalent to solving an ECDLP (discrete logarithm problem) which on standard curves, is believed to be hard (...


6

I would go further than fgrieu and say that in general you should not use (significantly) weakened cryptographic primitives for only time sensitive crypto, regardless of the time window. Why? Because there is nothing that guarantees hardness of any crypto. Mathematically the status quo is that we are generally have nothing more than 'a bunch of smart and ...


6

Given an $x$-coordinate of a point on the SECP256K1 curve, is it possible to calculate the corresponding $y$-coordinate? Yes, if there exists such $y$ for the given $x$. And, absent other indication, such $y$ can only be found within sign (or equivalently, parity). That limitation is because if $y^2\equiv x^3+7\pmod p$ with $p=2^{256}−2^{32}−2^{10}+2^6-2^4−...


6

That's insecure. In BLS signatures: for private key $x$ and public key $X = xP$, the signature is computed as $T = xS$, and the verification checks if $e(T, P) = e(S, X)$, which works because: $e(T, P) = e(xS, P) = e(xS, P) = e(S, P)^x$ $e(S,X) = e(S, xP) = e(S, P)^x$ If you know that $S = kP$, then you can forge a signature for a message with hash $k'$ ...


6

Long to be a comment and this is not going to a perfect answer; First of all, an early exit is always a bad move. The simple idea is that turning the $\mathbf{If\; Else}$ 's if S then A else then B into constant time expressions without changing the output by $$Q = (A * S) + (B * S') $$ where $S$ is the binary if condition. #have a return point RET RET =...


6

I couldn't figure out a field of order, say, 4, 8, 9 or 16. What are examples of such fields? Let's do that with $8=2^3$. Elements of that field $\mathbb F_{2^3}$ will be assimilated to $3$-bit quantities, that is the set $\{\mathtt0,\mathtt1\}^3$, or equivalently polynomials of degree less than $3$ with binary coefficients, where e.g. $\mathtt{110}$ is ...


6

The responsibility of the user of Curve25519 for DHKE is Section 3; The legitimate users are assumed to generate independent uniform random secret keys. A user can, for example, generate 32 uniform random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the last byte, and set bit 6 of the last byte. This is a guarantee that the legitimate users ...


6

Regarding the [B] and [C] parts of the question per the comments: I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $By^2 = x^3 + Ax^2 + x$. If $B$ is 1, then it fits into the generalized Weierstrass form, and most ...


5

Point multiplication is defined as: $$kG = \underbrace{G+G+G+...+G}_{k \text { times}}$$ That is, you take $k$ copies of $G$, and add them up. To define $111254.3945890....G$ or $54/33 G$, you need to define what it means to add up a nonintegral number of $G$s (or some other extension of point multiplication) that preserves the essential properties of ...


5

Why can't you encrypt a message with a public key generated via ECC? Well, for starters, you need to realize that ECC is a collective term for a number of protocols that use elliptic curves to do cryptography. Some of these protocols (ECIES, ECElGamal) are public key encryption methods (that is, they have a public encryption key, and the private ...


5

For something to be a group, it must have an identity. This is a definition. The order of an element, $g$, in a group is defined to be the smallest positive number $n$ such that $g^n = 1$, where $1$ is the identity of the group. By this definition, the order of the identity in any group is $1$.


5

Although there is an answer here saying "no" for usual definitions, I want to strongly warn that there is no rigorous basis for that. Specifically, it is true that there is no known way of recovering a private key from an encryption of it with its associated public key. However, there is also no proof whatsoever that it isn't possible. Security of ...


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


5

At the risk of talking like an actual mathematician, I'd like to try to clarify the matter of "infinity" here. If for fixed $a$ and $b$ (with $b \ne 0$), we look at solutions to $$ y^2\,=\,x^3+a\cdot x+b $$ they're in 1-to-1 correspondence with solutions to $$ ty^2\,=\,x^3+a\cdot xt^2+bt^3 $$ where $t = 1$, i.e., if $(x,y)$ is a solution to the ...


5

RFC 8734 defines how to use Brainpool curves within TLS 1.3, including how they can be used in ECDSA signatures (section 4) . Hence, yes, there is an official way to negotiate Brainpool curves for use in the SERVER KEY EXCHANGE.


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