verifySafePrime function
Verifies that a number is a safe prime.
A safe prime N is a prime number of the form N = 2q + 1, where q is also prime (q is called a Sophie Germain prime).
Note: This uses a probabilistic primality test (Miller-Rabin) which is computationally efficient but has a very small chance of false positives. For cryptographic applications, this is generally acceptable.
Parameters:
safePrime
: The number to verify as a safe prime.minimumBitLength
: Minimum required bit length for the safe prime (recommended: ≥ 2048).
Throws:
- InvalidParameterException if the number is not prime, not a safe prime, or has insufficient bit length.
Implementation
void verifySafePrime(BigInt safePrime, int minimumBitLength) {
// Check if N is prime
if (!isProbablyPrime(safePrime)) {
throw InvalidParameterException('Provided "safe prime" is likely not prime.');
}
// Check if q = (N - 1) / 2 is also prime.
final sophieGermainPrime = (safePrime - BigInt.one) ~/ BigInt.two;
if (!isProbablyPrime(sophieGermainPrime)) {
throw InvalidParameterException('The Sophie Germain prime of the provided "safe prime" is not prime.');
}
// Verify the relationship N = 2q + 1.
if (safePrime != BigInt.two * sophieGermainPrime + BigInt.one) {
throw InvalidParameterException('Provided "safe prime" does not have a Sophie Germain prime.');
}
// Verifies that a safe prime has the required bit length.
//
// A safe prime should use all bits of the specified length, with the highest
// bit set to 1 to ensure it is sufficiently large.
if (safePrime.bitLength < minimumBitLength) {
throw InvalidParameterException('Safe prime has bit length ${safePrime.bitLength} which is less than the minimum bit length of $minimumBitLength.');
}
}