In the paper for curve25519 is described how the prime was chosen. But I don't understand why the biggest 255-Bit prime was chosen instead of a 256 Bit prime. Can someone explain this to me?
$\begingroup$
$\endgroup$
-
2$\begingroup$ moderncrypto.org/mail-archive/curves/2014/000237.html $\endgroup$ – Samuel Neves Sep 19 '20 at 8:56
-
1$\begingroup$ Do I get this right: $2^{255} - 19$ is faster than $2^{256} - 189$ and this is more important than a non significant boost in security? $\endgroup$ – Titanlord Sep 19 '20 at 9:16
$\begingroup$
$\endgroup$
A pretty good answer to the question can be found here
I try to give a shorter and more precise answer: The Curve25519-standard uses a pretty specific modulo-algorithm. A pseudocode of the algorithm looks like this:
def fastModulo(num, prime):
# Basecase:
if num < prime: return num
if num < 2*prime: return num-prime
# Split number in upper and lower bits:
upper = upperBits(num)
lower = lowerBits(num)
# calculation:
factor = differenceToPowerOfTwo(prime)
nextnum = factor * upper + lower
# recursion:
return fastModulo(nextnum, prime)
The algorithm is faster if factor is smaller. So the difference to a power of two is important for the speed of the standard. Therefore the biggest 255 Bit prime was chosen instead of the biggest 256 Bit prime, because a significant speed boost is more important than a non signficiant security boost.
