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"

4
  • Despite the question title, the top answer at security.stackexchange.com/questions/73505/… also addresses DH. security.stackexchange.com/questions/5263/… and security.stackexchange.com/questions/112313/… may also be of interest. Commented Jul 22, 2021 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
    Commented Jul 22, 2021 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. Commented Jul 22, 2021 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 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). Commented Jul 23, 2021 at 1:37

0

Browse other questions tagged .