2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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