# Tag Info

The Pohlig-Hellman algorithm reduces the discrete logarithm from a group of composite order to subgroups of prime order. For instance, with an elliptic curve and a point $P$ whose order is a composite integer $q = p_1 \cdot p_2$, and we want to find $k$ such that $Q = [k]P$ for a given point $Q$. Then, since $[p_2]P$ is a point of order $p_1$. Let $$Q_2 = [... 0 According to Alternative Elliptic Curve Representations, each other point (x1,y1) of Edwards448 corresponds to the point (u,v) of Curve448, where: u = y1^2/x1^2 v = y1*(2-x1^2-y1^2)/x1^3. Under this isogenous mapping, the base point (G1x, G1y) of Edwards448 corresponds to the base point (Gu,Gv) of Curve448. The dual isogeny maps both the point ... 2 Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? No. If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification. However, only the signature generated with the EdDSA signing ... 0 For Ed448, this issue has happened for me. I design my scheme to work in twisted Edward space, and all results are verified by given test vector in RFC 8032. Now I wanna work over Montgomery space. The first three mentioned steps, i.e., convert the base point to Mont., Mont. ladder execution, and y-coordinate recovery can be performed simply. However, the ... 3 ECCDSA-keys can be merged such that the sum of two private keys S=S_1+S_2 yields a public key which is the sum of the respective public keys P=P_1+P_2. This is true, however it doesn't mean what you think it means; the + operators in the two equations are two different operations. The first one is simple addition (modulo the order of the elliptic ... 1 Yes it could be exploited to have a small performance advantage. In pseudocode, the montgomery ladder is defined as: x2,z2,x3,z3 = 1,0,x1,1 for i in reversed(range(255)): bit = 1 & (n >> i) x2,x3 = cswap(x2,x3,bit) z2,z3 = cswap(z2,z3,bit) x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2) x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^... 1 However in the case of a private set intersection we can use a secret key s, so if I am correct the discrete logarithm of h(m) *s would not be known : That is correct; it is not known; however that is not sufficient; the relationship between h(m_1) * s and h(m_2) * s would be known (if you know m_1, m_2), and that breaks security (at least, within ... 4 From the same paper: Use a fixed position for the leading 1 in the secret key; Multiply the secret key by a small power of 2 to account for cofactors in the curve group and the twist group. The first one is to make the scalar multiplication with always the same number of iterations of the loop, for constant-time reasons. The second one makes sure that the ... 1 I got the answer now! Curve25519 does not have key validation. Usually you have a point P =(x,y) on a elliptic curve E over F_p. But there is not a point P on the elliptic curve for every value in F_p. If you make a key exchange with such a system, you will get a point, or a x-Value (using Montgomery x-only computation). Now you have to test, ... 2 I don't really know so I'll tell you my best guess: One of the design goals was "free point validation". To do this, we want to make sure that no matter what x-value in F_p we're sent, it is a valid point on the curve. If x\in F_p, then to make an elliptic curve point we need y such that y^2=x^3+488862x^2+x. But we have no reason to ... 1 If you look at the FIPS Implementation Guidelines for FIPS-140-2 here https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf In section D.8 Key Agreements, you will find the recommendations. This recommendation points to NIST SP-800-56A, where in Appendix D, there is a table of "Approved ECC ... 2 Ok, it answer the specific question you asked: Bernstein says that it needs 640383 cycles for one multiplication Actually, when Dan talks about "multiplication", he is referring to a "point multiplication", that is, to the computation of [n]P (given a large integer n and a point P). In your simple-minded brute force search, you ... 3 Most symmetric cryptographic algorithms requires a key that is indistinguishable from random. This means that the process used to generate the key must have a uniform, independent distribution over all bit-strings of the appropriate length. Using a non-uniformly-random key not only reduces the brute force needed to guess it, but may also open the door to ... 1 The curve E given by the equation y^2 = x^3 + x is a Montgomery curve. Those are are the form By^2 = x^3 + Ax^2 + x, so in this particular case we have A=0 and B=1. The points of order 2 have their x-coordinate as a root of x^3 + x. If -1 is a square over \mathbf F_p, then the points of order 2 are (0,0), (\sqrt{-1},0) and (-\sqrt{-... 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 ... 1 Yes. The general construction is called IES (Integrated Encryption Scheme), most often practiced as ECIES (elliptic curve IES). The principle is the same: use the “key agreement” primitive (DH, ECDH, X25519, …) to construct a secret that is shared by two parties, each of which knows both sides' public keys but only their own private key. The shared secret is ... 3 Given two elliptic curves E_1 and E_2, an isogeny from E_1 to E_2 is an algebraic map \phi (it is basically defined from rational functions) that sends the neutral element from E_1 to the neutral element of E_2. As stated in Theorem 4.8 in page 71 of The Arithmetic of Elliptic Curves by J.H. Silverman: Let$$ \phi : E_1 \longrightarrow E_2  ...