# Tag Info

7

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

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

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 = ... 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 ... 3 In your particular case the order of the point divides$p-1$, this means that the embedding degree of your curve is 1. You should be able to apply the MOV attack to transfer your instance of ECDLP into an instance of DLP over$\mathbb{F}_{p}^*$. This would allow you to use the Index Calculus to solve your problem. As the Index Calculus is subexponential, ... 3 The conversion formula from twisted Edwards to Montgomery form is: $$x_{mont} = \frac{X_{mont}}{Z_{mont}}= \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y_{ed}}{Z_{ed}}}{1-\frac{Y_{ed}}{Z_{ed}}} = \frac{Z_{ed}+Y_{ed}}{Z_{ed}-Y_{ed}}$$ If you want the affine$x_{mont}$, you need to compute the inversion. But if you just need$X_{mont}$and$Z_{mont}$you can ... 2 Your calculation is broken. First as pointed out correctly the expected run-time of GNFS (general number field sieve) is:$O(exp((\sqrt[3]{\frac{64}9}+o(1))*\sqrt[3]{ln(n)}*\sqrt[3]{ln(ln(n))}^2))$. So next you can't just set these$O$s equal, as$O(f(x))$means$O(f(x))< k*f(x)$which means this is an asymptotic upper bound meaning you need some ... 1 For a pre-shared secret, you just use a secure MAC to authenticate the key exchange, e.g. for the exchanged public ephemeral keys$A$,$B$and the resultant shared secret$S$, one side could send$HMAC(PSK, S, A, B)$and the other$HMAC(PSK, S, B, A)$. Each side can easily verify that the other is using the same exchanged values and shared secret, and that ... 1 I don't know your exact scenario. However you have two options to encrypt data using elliptic curve cryptography (ECC). I'd recommend going with the first option I present. Use elliptic curve integrated encryption scheme (ECIES). ECIES basically performs ElGamal-like encryption on a key. The key is generated at random and encrypted like in ElGamal (replace ... 1 From what you say, I assume that you are talking about the Crypto 3 challenge from HackingWeek. As Ruggero explained, the curve is vulnerable to both the MOV attack and the older FR attack that works similarily, using Weil or Tate pairings (respectivly). A simple sage code for the FR-attack would be: q = 134747661567386867366256408824228742802669457 Zq = ... 1 You want to hash the existing generator$g$then coerce that hash to a curvepoint. This will result in a generator which is uniformly independent of$g$(well, in the random oracle model anyway) and also commits to$g\$ so that neither generator can be changed (say, to introduce a correlation) without changing the other. The "obvious" way to avoid ...

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