0

This is a follow on from this question:

"Diffie-Hellman Key Exchange" in plain English

In the answer to that question, the standard Diffie Hellman key exchange equation is derived:

(g^a mod p)^b mod p = g^ab mod p
(g^b mod p)^a mod p = g^ba mod p

In this answer, only the generator g and a prime number p are used. What I would like to know is how this equation is affected/modified when we include the optional subprime q value to the initial parameters?

I have found this:

The order of G should have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b. For this reason, a Sophie Germain prime q is sometimes used to calculate p = 2q + 1, called a safe prime, since the order of G is then only divisible by 2 and q. g is then sometimes chosen to generate the order q subgroup of G, rather than G, so that the Legendre symbol of ga never reveals the low order bit of a. A protocol using such a choice is for example IKEv2.[11]

Reference: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

But it goes a bit over my head. The above makes it sound as though p is derived directly from q, but to use a practical example of some parameters I am given:

        "p": "CFE27C72A2ACD5F32580934D6771064A6F1CF57B154AB0E32EBF1A9E1CE80D74E2006D064EE664EE7CC29B44F1B93FFEA4100176CC898B48343EF2B6A5E5F5EFEE5CDFAD828B0CD83D7DD8CAF8B0338A17694DC165D3A9E0C5421D88D1DE6AD0AC08CD24E9AB1513B827116B2192EB20ADED55CAB76D93F420C072CF8B9C0BD9D40DDE91C6BD3FCB4520CE8FCC662176BC5750BC552FD5B85C58C8C48FF86CFB05C99E006645CD8CE1B951DFEBF5E91D15AA64A22DCAA962B4CBD93D81344B12DCAB01C3EA81EF0B32079D4092D9E2FB99D5EF4716CBC9445D1ED8B4166C4C1312BD5C3B0596FD48476556A4331F5DB600E2A1A05B62A222B0FD0ACA607DB943",
        "q": "8000000092C37D5F1106277105CB36B6E775199D9075B6D6934444D1EE78D78D",
        "g": "354950D327791775BF956AA086E7AB71788BF0C33D54E20E56936742CB947DB827032F3040E2A19F1EA8E882DD919CFEF51B11B76429AB4283CF0F2E1A7250B99F30C165CD16A5FE4ECE5A4FB01726A36DB6842466A2C8908409B62D658E213F3AB77EF4551BA06E16465B7D550B384F9EBE23AC7AE843E9823258441B9A3DAEE6B9624520A40D7C34AA163D19C68A011AF7A90D9E4C4E3F82CF858BBFC4F6558D8A1C724D27996ABC2FE9DC5EB14158BC60F16CC7A96088174D902E2BBB814F13D54DA425610D61F6C2EC3BC4226180CC8B7B02FF0687D2786592907B0ABF3C119029740820F04F611F86899EF54EDF10540E1B3CE5663327EA79F9CBE167A2",

The p value does not equal 2q + 1

Side note, I have also seen this q value referred to as

"q is an (odd) prime divisor of p – 1"

dave_thompson_085
  • 10,064
  • 1
  • 26
  • 29
factor2
  • 1
  • 1
  • Despite the question title, the top answer at https://security.stackexchange.com/questions/73505/use-of-safe-prime-in-rsa-digital-signature-scheme/73542#73542 also addresses DH. https://security.stackexchange.com/questions/5263/where-do-i-get-prime-numbers-for-diffie-hellman-can-i-use-them-twice/5264#5264 and https://security.stackexchange.com/questions/112313/what-is-the-current-security-status-of-diffie-hellman-key-exchange/112318#112318 may also be of interest. – Gilles 'SO- stop being evil' Jul 22 '21 at 14:31
  • Those links definitely helped with my understanding of the safe primes and why they are useful, thank you very much for the references. I'm still not quite able to wrap my head around how to actually use the q value within the diffie hellman key exchange algorithm though. – factor2 Jul 22 '21 at 14:56
  • It isn't used during the key exchange. You can throw q away after generating the parameters if you only care about using the parameters and not checking their correctness. – Gilles 'SO- stop being evil' Jul 22 '21 at 15:18
  • wikipedia says 'sometimes' p is a safe prime = 2q+1 with q prime; 'sometimes' is not 'always'. It is also fairly common to use a [_Schnorr_ group](https://en.wikipedia.org/wiki/Schnorr_group) with p = rq+1 with q prime of the desired size and r an integer of suitable size to make p the desired size; that's presumably the case for your example: p and g are 2048 bits and q 256 bits, one of the combinations defined for DSA which _always_ uses Schnorr parameters (even though its signing equation was altered to avoid his patent). – dave_thompson_085 Jul 23 '21 at 01:37

0 Answers0