Editing Safe and Sophie Germain primes (section)

===Cryptography===
Safe primes are also important in cryptography because of their use in [[discrete logarithm]]-based techniques like [[Diffie–Hellman key exchange]]. If {{nowrap|2''p'' + 1}} is a safe prime, the multiplicative [[group (mathematics)|group]] of integers [[modular arithmetic|modulo]] {{nowrap|2''p'' + 1}} has a [[subgroup]] of large prime [[order (group theory)|order]]. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to ''p''.  

A prime number ''p''&nbsp;=&nbsp;2''q''&nbsp;+&nbsp;1 is called a ''safe prime'' if ''q'' is prime. Thus, ''p''&nbsp;=&nbsp;2''q''&nbsp;+&nbsp;1 is a safe prime if and only if ''q'' is a Sophie Germain prime, so finding safe primes and finding Sophie Germain primes are equivalent in computational difficulty. The notion of a safe prime can be strengthened to a strong prime, for which both ''p''&nbsp;−&nbsp;1 and ''p''&nbsp;+&nbsp;1 have large prime factors. Safe and strong primes were useful as the factors of secret keys in the [[RSA_(cryptosystem)|RSA cryptosystem]], because they prevent the system being broken by some [[Integer factorization|factorization]] algorithms such as [[Pollard's p − 1 algorithm|Pollard's ''p'' − 1 algorithm]]. However, with the current factorization technology, the advantage of using safe and strong primes appears to be negligible.<ref>{{citation|title=Are 'strong' primes needed for RSA?|first1=Ronald L.|last1=Rivest|first2=Robert D.|last2=Silverman|date=November 22, 1999|url=https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf |archive-date=2022-10-09 |url-status=live}}</ref>

Similar issues apply in other cryptosystems as well, including [[Diffie–Hellman key exchange]] and similar systems that depend on the security of the [[discrete logarithm problem]] rather than on integer factorization.<ref>{{citation
 | last = Cheon | first = Jung Hee | author-link = Cheon Jung-Hee
 | contribution = Security analysis of the strong Diffie–Hellman problem
 | doi = 10.1007/11761679_1
 | pages = 1–11
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06), St. Petersburg, Russia, May 28 – June 1, 2006, Proceedings
 | volume = 4004
 | year = 2006| url = http://www.iacr.org/cryptodb/archive/2006/EUROCRYPT/2143/2143.pdf| doi-access = free
 | isbn = 978-3-540-34546-6 }}.</ref> For this reason, key generation protocols for these methods often rely on efficient algorithms for generating strong primes, which in turn rely on the conjecture that these primes have a sufficiently high density.<ref>{{citation
 | last = Gordon | first = John A.
 | contribution = Strong primes are easy to find
 | doi = 10.1007/3-540-39757-4_19
 | pages = 216–223
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proceedings of EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9–11, 1984
 | volume = 209
 | year = 1985| doi-access = free
 | isbn = 978-3-540-16076-2
 }}.</ref>

In [[Sophie Germain Counter Mode]], it was proposed to use the arithmetic in the [[finite field]] of order equal to the safe prime 2<sup>128</sup>&nbsp;+&nbsp;12451, to counter weaknesses in [[Galois/Counter Mode]] using the binary finite field GF(2<sup>128</sup>). However, SGCM has been shown to be vulnerable to many of the same cryptographic attacks as GCM.<ref>{{citation
 | last1 = Yap | first1 = Wun-She
 | last2 = Yeo | first2 = Sze Ling
 | last3 = Heng | first3 = Swee-Huay
 | last4 = Henricksen | first4 = Matt
 | doi = 10.1002/sec.798
 | journal = Security and Communication Networks
 | title = Security analysis of GCM for communication
 | year = 2013| volume = 7
 | issue = 5
 | pages = 854–864
 | doi-access = 
 }}.</ref>