Generating safe primes

Safe primes and safe RSA moduli are used in several cryptographic schemes. The most common notion is that of a prime , where is also prime. The latter is then a Sophie Germain prime. Under appropriate heuristics, they exist in abundance and can be generated efficiently. But the modern methods of ana...

Full description

Saved in:
Bibliographic Details
Published in:Journal of mathematical cryptology 2013-12, Vol.7 (4), p.333-365
Main Authors: von zur Gathen, Joachim, Shparlinski, Igor E.
Format: Article
Language:English
Subjects:
Hofheinz–Kiltz–Shoup cryptosystem
Safe prime
Sophie Germain prime
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Safe primes and safe RSA moduli are used in several cryptographic schemes. The most common notion is that of a prime , where is also prime. The latter is then a Sophie Germain prime. Under appropriate heuristics, they exist in abundance and can be generated efficiently. But the modern methods of analytic number theory have – so far – not even allowed to prove that there are infinitely many of them. Thus for this notion of safe primes, there is no algorithm in the literature that is unconditionally proven to terminate, let alone to be efficient. This paper considers a different notion of safe primes and moduli. They can be generated in polynomial time, without any unproven assumptions, and are good enough for the cryptographic applications that we are aware of.
ISSN:1862-2976
1862-2984
DOI:10.1515/jmc-2013-5011