Sophie Germain and Safe Key Generation for RSA

Sophie Germain (born 1776 in Paris) was a French mathematician and who used safe primes to investigate Fermat’s Last Theorem. She gained…

Sophie Germain and Safe Key Generation for RSA

Sophie Germain (born 1776 in Paris) was a French mathematician and who used safe primes to investigate Fermat’s Last Theorem. She gained her knowledge of mathematics by studying the works of Euler and communicated her ideas with other famous mathematics scholars, including Legendre and Gauss.

In fact, at the time, she faced great resistance in her studies, including from her parents, and who confiscated her candles and took away her clothes in order to stall her research. Sophie also hid her gender when communicating with Gauss and used the pseudonym of Monsieur LeBlanc. But, against all the obstacles she faced, she overcame them and even learnt Greek and Latin so that she could read about the works of Euler and Newton.

The Sophie Germain prime

A Sophie Germain prime (p) is a prime number which also generates a prime at 2p + 1. 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. We can create a Golang program to generate a random prime number with n bits and then test it to see if it is safe [here]:

package main
import (
 "crypto/rand"
 "fmt"
 "math"
 "math/big"
 "os"
 "strconv"
)
func main() {
 bits := 16
 argCount := len(os.Args[1:])
 if argCount > 0 {
  bits, _ = strconv.Atoi(os.Args[1])
 }
 if bits < 3 {
  fmt.Printf("We need at least three bits")
 }
 var p *big.Int
 checks := int(math.Max(float64(bits)/16, 8))
 for {
  p, _ = rand.Prime(rand.Reader, int(bits)-1)
  p.Add(p.Lsh(p, 1), big.NewInt(1))
  if p.ProbablyPrime(checks) {
   break
  }
 }
 fmt.Printf("Safe prime: %s", p)
}

With this, we shift p by one position to the left and is equivalent to a 2.p, and where we can add 1:

p.Add(p.Lsh(p, 1), big.NewInt(1))

A sample run for a 96-bit prime is: [here]:

Bits:		96
Selections:	13
Prime:		37053578410686858579548491583
Safe prime:	74107156821373717159096983167

A sample prime for 512 bits is:

Bits:		512
Selections:	216
Prime:		6215641074915422390891487240873485166396563079583149872792235087315853337457206134539638799981401165118482893105922463329240778055363535077155714487851623
Safe prime:	12431282149830844781782974481746970332793126159166299745584470174631706674914412269079277599962802330236965786211844926658481556110727070154311428975703247

RSA Key Generation from Safe Primes

In RSA, Bob generates two random prime numbers (p and q), and create a public modulus of:

N=p.q

Next Bob computes φ:

φ=(p−1).(q−1)

Bob then picks a public exponent of e and which does not share a factor with φ, and computes the private exponent as:

d=e^{−1} (mod φ)

Bob will then use a public exponent (e) to cipher a message (M) with:

C=M^e (modN)

To decrypt we use the private exponent (d) to decipher the ciphertext:

M=C^d (modN)

Bob’s public key is [e,N] and his private key is [d,N].

Safe primes

Now we can generate RSA prime numbers (p and q) from the Sophie Germain prime —and which is safe when 2p+1 and 2q+1 are also prime. The method is:

func SafePrime(bits int) *big.Int {
var p *big.Int
 p1 := new(big.Int)
 checks := int(math.Max(float64(bits)/16, 8))
 for {
  p, _ = rand.Prime(rand.Reader, int(bits)-1)
  p1.Set(p)
  p.Add(p.Lsh(p, 1), big.NewInt(1))
  if p.ProbablyPrime(checks) {
   return (p)
  }
 }
}

The code:

p.Add(p.Lsh(p, 1), big.NewInt(1))

is the same as 2.p+1. The coding is then [here]:

package main
import (
 "crypto/rand"
 "fmt"
 "math"
 "math/big"
 "os"
 "strconv"
)
func SafePrime(bits int) *big.Int {
 var p *big.Int
 p1 := new(big.Int)
 checks := int(math.Max(float64(bits)/16, 8))
 for {
  p, _ = rand.Prime(rand.Reader, int(bits)-1)
  p1.Set(p)
  p.Add(p.Lsh(p, 1), big.NewInt(1))
  if p.ProbablyPrime(checks) {
   return (p)
  }
 }
}
func main() {
 bits := 512
 argCount := len(os.Args[1:])
 if argCount > 0 {
  bits, _ = strconv.Atoi(os.Args[1])
 }
 p := SafePrime(bits / 2)
 q := SafePrime(bits / 2)
 n := new(big.Int).Mul(p, q)
 pminus1 := new(big.Int).Sub(p, new(big.Int).SetInt64(1))
 qminus1 := new(big.Int).Sub(q, new(big.Int).SetInt64(1))
 PHI := new(big.Int).Mul(pminus1, qminus1)
 e := new(big.Int).SetInt64(65537)
 d := new(big.Int).ModInverse(e, PHI)
 fmt.Printf("Safe RSA-%d\n", bits)
 fmt.Printf("e=%s\n", e)
 fmt.Printf("p=%s\n", p)
 fmt.Printf("q=%s\n", q)
 fmt.Printf("N=%s\n", n)
 fmt.Printf("PHI=%s\n", PHI)
 fmt.Printf("d=%s", d)
}

A sample run for RSA-512 is [here]:

Safe RSA-512
e=65537
p=98762546123746664154961805355705549307155302550185032287868206536366418562019
q=110517457421244417238609129760169836655264057662891428257441410420417295659447
N=10914985486044859821538351241179067409764019202050992915995491936272351774827466179305186422526206809616323321178897992563950240046657823259043340072743493
PHI=10914985486044859821538351241179067409764019202050992915995491936272351774827256899301641431444813238681207445792935573203737163586112513642086556358522028
d=5400950063734207533952838738425560782935401051365055606341727695826420124599434120992003448133479538538426785779317144566031287332866055890553808324313149

A sample run for RSA-1024 is [here]:

Safe RSA-1024
e=65537
p=11060427570309635985661873394562603602441474690779479735484461914563374162763601914391717841829748984954919766609428496612897119595567348246544676717072059
q=11348153636925764904542269311978224358568433793738107934832588633549319439933517002247718850660120854704444109008020632228265493200188865709933518642900047
N=125515431357963296930349616286355272328314756627458562045555293182007583902381257606803907342617012590275910216285617838098568426457635126452825495768997846521987134210370007732401277536159664740762050414794759778740572008450485087317862941663215557615713314638874158723645808698131479715632754378994433486773
PHI=125515431357963296930349616286355272328314756627458562045555293182007583902381257606803907342617012590275910216285617838098568426457635126452825495768997824113405926974969117528258570995331703730853565897207089461690023895756882390198946302226523067745873655274998541274516967535518683959418797900799073514668
d=24797805899307395343915144600389521432275195215104955389563909488085115222973778529577139513133116850311922814295225289038257228523940058551828501750415548874992446136867725616917038882578618183729678978852211641514906532222410442777300711372644775946008698727446802759089456271265024641142478221760935103345