2
$\begingroup$

"Optimal Prime Field is a family of 'low-weight' prime fields that allow for efficient software implementation of all operations requiring a modular reduction, in particular the field-multiplication. More formally, an OPF is a finite field defined by a prime of the form p = u · 2^k + v, whereby the two coefficients u and v are “small” (in relation to 2^k)".

Eg: p = 0xCD3E000000000000000000000000000000000001

Only the 4 MSB words are non-zero and rest are always zero, except the last bit. I have read in the literature, OPF can be clubbed with ECC to speed up the computation involved. However, wouldn't a 160bit OPF with hamming weight 16bit used as key, make it vulnerable to brute force attack. I couldn't find any mention of it in literature. Please comment.

$\endgroup$
3
  • $\begingroup$ The key k is a random integer between 1 and order prime. And your public key is calculated as $[k]P$ with the base point G. I think you are confusion with the prime that used to define the curve. When the EC group operations are performed the calculation are performed with the field. $\endgroup$
    – kelalaka
    Nov 12, 2020 at 11:45
  • $\begingroup$ Thanks for the response. If I am calculating my public key P as p*G where p is an Optimal prime (instead of integer) and G is the base point, would it affect the security of ECC operations? $\endgroup$
    – APS
    Nov 12, 2020 at 12:13
  • $\begingroup$ That is totally insecure, and you totally mixing the concepts. Where did you see that the secret is selected from the small set? You couldn't find it since the secret is a uniform random integer. $\endgroup$
    – kelalaka
    Nov 12, 2020 at 12:28

1 Answer 1

2
$\begingroup$

Preliminary: the present answer assumes an Elliptic Curve group of order $n$ built on a prime field of order $p$, with one of $p$ or $n$ a 160-bit prime of the form in the question (rather $p$, which will give the most computational benefit, and is close to common practice). Choosing "public key $P$ as $p*G$ where $p$ is an Optimal prime" is not proper, and not considered.

Rather yes: ECC cryptography would be dangerously close to being vulnerable to brute force attack.

That's because the order $n$ of the Elliptic Curve group would be at most roughly $2^{160}$ (due to Hasse's bound when the 160-bit prime is $p$), thus vulnerable to a generic Pollard's rho attack with cost about $2^{160/2}=2^{80}$ field operations, e.g. recovering a private key from a public key. Further, that attack is not too difficult to parallelize. That's not entirely out of reach for well funded adversaries.

However, the largest similar attack publicly performed (by Nov. 2020) seems to be against secp112r1, requiring about $2^{56}$ field operations, that is about $2^{25}$ less work than for the above. See Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, and Peter L. Montgomery's Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles using Sloppy Reduction, in International Journal of Applied Cryptography, 2012.

Thus for a 160-bit prime, a similar attack would be worth publication in the applied cryptography field. And in the unlikely cases that it it required sizably less than $2^{80}$ field operations, or less than $2^{25}$ more computing power than the secp112r1 attack on any given sufficiently flexible hardware, that would be a major theoretical breakthrough.


Update per comment: I fixed the above to use proper notation for $p$ and $n$. Yes proper ECC on a 160-bit prime field is not publicly broken in practice so far. Yes a 256-bit OPF $p$ would be on par with current practice: common curves such as secp256k1 and Ed25519 use primes of the form $2^{256}-2^{32}-977$ or $2^{255}-19$, which is similar to the question's OPF. Beware however that what matters to security is (half) the number of bits of the highest prime factor of $n$ (that is $n$ if it is prime), which depends on $p$ and other curve parameters. And there are other complex considerations in choosing an ECC curve, that I do not master, see safecurves.

$\endgroup$
2
  • $\begingroup$ Thanks for the detailed insight. I re-read the material and I understand now that the curve used in ECC is defined over OPF p. From your answer, what I could gather is that even though it is not impossible to break the ECC with 160bit prime field, it has not been broken in practice so far. Please correct me if I am wrong. In continuation, would choosing a 256bit OPF be a significantly better choice than 160bit variant? That way i get a lot more OPFs. Thanks again for your time. $\endgroup$
    – APS
    Nov 12, 2020 at 14:31
  • 1
    $\begingroup$ Please consider accepting the answer; it's the best way to say thanks on Stack Exchange. $\endgroup$
    – Maarten Bodewes
    Apr 11, 2021 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.