Safe Primes, Goldilocks and Riddenhood

As a cryptography professor, I spend a good deal of my time dealing with prime numbers. Basically they are at the core of public key…
Photo by Clarissa Watson on Unsplash

Safe Primes, Goldilocks and Riddinghood

As a cryptography professor, I spend a good deal of my time dealing with prime numbers. Basically they are at the core of public key signing and used to encrypt things, prove identities, and also to prove the credibility of digital signatures. So, as you may remember, a prime number is only divisible by itself and 1. So, 15 isn’t prime, but 17 is. In a recent version of Pointless on the TV, there was even a question on naming a prime number less than 200. For me, it was 97, and this is one I use in testing programs. For larger ones, I use 2¹⁹-1 (19 bits) and 2²⁵⁵-19 (256 bits). In most cases, of course, we would pick random prime numbers, and which will make them difficult to crack.

But not all primes are the same.

Safe primes

In cryptography, we often search for safe primes. A safe prime (p) — or also known as a Sophie Germain prime — is safe when 2p + 1 is also prime. Sophie Germain was a French mathematician and who used safe primes to investigate Fermat’s Last Theorem.

A Sophie Germain prime (p) is a prime number which also generates a prime at 2p + 1 — and which is defined as a safe prime. Thus 11 is a Sophie Germain prime, and where 23 is a safe prime. But 17 is not a Sophie Germain prime, as we get 35 for 2x17+1, and which can be factorized. These primes have been seen as being important when selecting prime numbers to be used in the RSA method. For this, we create a public modulus (N) and which is the multiplication of two large prime numbers (p and q). If these prime numbers are weak, it can make the factorization of N easier.

The first few Sophie Germain primes are 2, 3, 5, 11, 23, and 29, and which lead to the safe primes of 5, 7, 11, 23, 47 and 59. Overall safe primes are used in cryptography, as they are robust against attacks within discrete log methods (such as for the Diffie Hellman methods). In the following we use the Miller Rabin test for primality:

Thus:

  • p=47 (safe as 46/2=23) Try!
  • p=59 (safe as 58/2=29) Try!
  • p=83 (safe as 82/2=41) Try!
  • p=99 (Not a prime!) Try!

The largest-ever safe prime found was 2618163402417 × 2¹²⁹⁰⁰⁰⁰ − 1.

The Goldilocks and the Riddinghood primes

And, so we meet Goldilocks. With this, we have an elliptic curve known as Curve 448 and which uses the Goldilocks prime number (2⁴⁴⁸-2²²⁴-1). The curve itself fits in with y²+x²=1−39081x²y², and where we use our Goldilocks prime number [here]:

Goldilocks prime is defined golden ratio ϕ≡2²²⁴. Have a look at we see the form of ϕ²-ϕ-1, and which is the form of the golden ratio and because 224 = 32 x 7 = 28 x 8 = 56 x 4. This makes it easier to process with 32 bits and 54 bits at a time. Overall this choice of prime makes the calculations related to the prime number extremely fast. The paper also outlines the Riddinghood prime number, and which is 2⁴⁸⁰-2²⁴⁰-1. This is a useful prime number for performance for a 64-bit processing engine, while the Goldilocks prime is useful for both 32-bit and 64-bit processing.

Conclusions

Prime numbers are magic, and you can thank them for securing the Internet and in proving your identity.