Monthly Archives: May 2012

Generating safe prime numbers in Python

Recently, I tried to generate safe prime numbers in a Python program. Python is a nice language when it comes to implementing code that needs to deal with long numbers and arbitrary precision integer arithmetic. Python has build in support for arbitrary precision integers, and operators like +, *, or ** can be overloaded.

If the native support for long numbers in Python seems to be to slow, there is gmpy, a Python C-binding, that allows you to use the GMP library from your python code. Due to the nice operator overloading in Python, you don’t need to change anything in your calculations, except for the initialization of your data.

GMP supports finding prime numbers and also efficient prime testing, bue there is no support for generating safe prime numbers in python and/or in GMP. A number p is a safe prime number, if p is prime, and (p-1)/2 is a prime number too. OpenSSL supports the generation of such numbers. So I decided to write an OpenSSL Python binding, to make it possible to generate these numbers in a Python script, without having to call an external program.

My implementation gensafeprime can be downloaded from github, and is also available on PyPi. Using the code is easy. The following example will generate a 512 bit safe prime number:

import gensafeprime
print gensafeprime.generate(512)