15
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$ ...
10
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 ...
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^...
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
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−...
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
Curve25519 has order $8\cdot q$, and we want a point of order $8$. This is the laziest solution I can think of:
Generate a random point $P$ on the curve;
Compute $Q = [q]P$. This point has order $1$, $2$, $4$ or $8$.
If $Q$ is not of order $8$, go back to step 1.
A sample code to see the points we get:
E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
for i ...
4
An elliptic curve as used in cryptography is a finite group, constructed on top a finite field. A pair of elements of the field that obey the curve equation form the Cartesian coordinates of a point of the elliptic curve group (and vice versa for all points of the elliptic curve group, except the neutral / point at infinity, often noted $\infty$).
In the ...
4
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 ...
4
In both RSA and usual¹ Elliptic Curve Cryptography (ECC), there is a public key and a private key, forming a matching pair. In signature, the private key is used for signature generation, and the matching public key is used for signature verification. In (usually, hybrid) encryption, the public key is used for encryption, and the matching private key is used ...
3
The most general form of a bilinear map is $e : G_1 \times G_2 \to G_T$. We can categorize a scheme's usage of the bilinear map into 3 standard categories:
Type 1: in addition to the bilinear pairing, the scheme requires efficiently computable homomorphisms $\phi_{12} : G_1 \to G_2$ and $\phi_{21} : G_2 \to G_1$. In other words, the scheme sometimes needs ...
3
With RSA or ECC, if I encrypt my private key with my public key, is there a way to recover my private key?
No, at least for usual or safe definitions of encrypt: anything involving hybrid encryption (ECIES…) or random padding (RSAES-OAEP in ECB mode¹, likely RSAES-PKCS1-v1_5…). Argument (not a formal proof, but still strong): without the private key, we can'...
3
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 ...
3
Let $\beta$ a non-square element in $\mathbf{F}_p$, then the elliptic curve defined by $\beta y^2 = x^3 + 3$ is a quadratic twist of secp192k1 whose equation is $y^2 = x^3 + 3$.
It means that if $x_0^3 + 3$ is a square, there exists $y_0 \in \mathbf{F}_p$ that is a square root of $x_0^3 + 3$, so $(x_0, y_0)$ belongs to secp192k1, and on the other hand if $...
3
It is a mistake to think that the RSA keys can be interchanged. In all real systems the RSA public exponent is very small or even directly known. That means all the public key properties are known if the private key is known, as the private key contains the modulus - the only other part of that makes up the public key.
I'm not sure why you call the ...
2
Your analysis is pretty much on point. The cost of batch inversion is only justified if we have a computation involving a relatively large number of simultaneous point additions. In a project I work on, we set a threshold of 70 additions based on our benchmarks. Our code is here if you're interested.
To generalize your example a bit, a single summation ...
2
Suppose for simplicity we have an 4-bit key $k= (k_0,k_1,k_2,k_3)$, where each $k_i$ is a bit. To compute $kP$, we find
$$k_0P + k_1(2P)+k_2(4P)+k_3(8P)$$
But we could instead write $k=(k_{01},k_{23})$, where we separate it into 2-bit windows. Then we can write
$$ kP = (k_0+2k_1)P + (k_2+2k_3)(4P) = k_{01}P + k_{23}(4P)$$
Then one way to actually compute ...
2
The paper writes $z^r \cdot G$; however $z^r$ is a member of the extension group $\mathbb{F}_{q^{12}}$, while point multiplication is formally defined over the integers; you ask "what are we supposed to do here?"
Well, going through the paper, it appears that if we rewrite that equation to $h(z^r) \cdot G$, where $h$ is a function from $\mathbb{F}_{...
2
Is the assumption that AES is "best" a valid one, alongside the assumption for AES_GCM?
Opinionated, but Microsoft doesn't implement a lot of modern ciphers, so AES is the tried and true one. If GCM mode is best depends on the use case really, but as it is an authenticated mode - it includes a MAC - it is generally better than e.g. ECB / CBC which ...
2
The question is referring to Nigel P. Smart's The Discrete Logarithm Problem on Elliptic Curves of Trace One, in Journal of Cryptology (1999) (earlier version). Quoting the intro:
(…) we describe an elementary technique which leads to a linear algorithm for solving the discrete logarithm problem on elliptic curves of trace one. In practice, the method ...
2
It sounds like you're looking to implement something very similar to what was asked about here, with the addition of a signature of the ephemeral public key. But as poncho's answer points out, the potential malleability of the XORed key and the ciphertext could potentially pose some problems. The way the shared secret is derived may also introduce the ...
2
You seem confused about a few things. Bear with me, this is a very common confusion!
Encryption is defined with the intent of confidentially transporting information: if you encrypt information, it is meant to be hidden until decrypted by the receiving party. Note that in your pseudo code
hash = doHash(message)
signature = doAsymetricEncrypt(hash, ...
1
My First Attempts:
So I did some testings on the curve $E: y^2 = x^3 + x^2 + x$ with $F_{131}$ and the points $P = (42,69)$ and $Q = 42 \cdot P$. My results for different $N$:
My result for a different Hash function:
So this got me confused, because I did not see any results for different N and I thought only the hash-function is for optimization. But the ...
1
Let $P = (x,y)$ be a point on the curve $E$ with the $y^2 = x^3 + ax + b$ with Weierstrass equation over the prime field $\operatorname{GF}(p)$1, i.e. it satisfies the curve equation.
The consecutive $x$-coordinate point can be found with the below algorithm.
for i from 1 to number_of_poinst_on_the_curve
temp = x + i mod p
if (temp, y) satisfies the ...
Only top voted, non community-wiki answers of a minimum length are eligible
