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