Abstract
This study examines the mathematical foundations and computational aspects of the Diffie-Hellman key exchange protocol through a custom-built Python simulation. Designed without external libraries, the simulator offers complete control over number-theoretic components such as primality testing, modular exponentiation, and primitive root generation. The project aims to deepen understanding of how these algorithms contribute to the protocol’s security and functionality. Test cases using small prime moduli and user-defined private keys confirmed that both parties independently derive identical shared secrets. This validates the protocol’s core principle: the commutative property of modular exponentiation. The simulation clearly demonstrates secure key agreement over insecure channels without revealing private keys. However, challenges emerged—particularly the increased computational cost of finding primitive roots as prime sizes grow. The study also acknowledges security limitations of small primes, which are susceptible to brute-force and discrete logarithm attacks. These insights point to future improvements, such as integrating probabilistic primality tests and optimizing for larger key sizes. In conclusion, the project bridges theoretical cryptography with hands-on implementation. It serves as both an educational tool and a foundation for further exploration into scalable, secure public-key systems.
Keywords: Cryptography, Diffie-Hellman, Key Agreement, Public-Key Exchange
Introduction
Cryptography plays a foundational role in protecting digital information—both during storage and transmission. It is implemented through cryptographic algorithms and the protocols that govern their use. These protocols define how encryption and decryption processes are executed and are applied directly in applications or serve as the foundation for broader frameworks such as TLS or IPsec. As outlined in the Handbook of Applied Cryptography, modern cryptographic design is driven by precise mathematical theory, formal models of security, and efficient algorithmic implementations1.
Although many cryptographic algorithms rely on complex number theory and computational hardness assumptions, their real-world implementations aim to be modular and user-friendly. Users interact with encryption tools without needing to understand the underlying operations like modular exponentiation or group theory, a design philosophy emphasized throughout the IETF’s standards such as RFC 7919, which standardizes ephemeral Diffie-Hellman key exchange parameters for enhanced forward secrecy2.
Several well-established cryptographic protocols are used today, including SSL/TLS for web communications, PGP for email security, and Kerberos for authentication. These systems are built to address core goals such as confidentiality, integrity, authentication, and non-repudiation3. Among these protocols, the Diffie-Hellman key exchange—proposed in 1976—stands as one of the earliest and most influential mechanisms enabling secure communication over insecure channels4.
The security of the Diffie-Hellman protocol is based on the difficulty of solving the discrete logarithm problem in a finite field. Instead of transmitting the actual secret key, both parties share public values that allow them to independently compute the same shared secret. This is further enhanced by standardized MODP groups defined in RFC 3526, which prescribe safe prime parameters and generator values for practical use5.
In this paper, I adopt a hands-on approach by implementing the Diffie-Hellman protocol from scratch using Python. The simulation covers key mathematical components such as large prime generation, primitive root selection, and modular arithmetic. Beyond correctness, I analyze computational performance and discuss limitations of naïve implementations. This work bridges the gap between theory and practice and offers an educational lens on one of cryptography’s most enduring protocols.
Results and Discussion
This study focused on analyzing the computational behavior and cryptographic implications of number-theoretic algorithms when applied to the simulation of the Diffie-Hellman key exchange protocol. The implementation was built from scratch in Python, without relying on any external cryptographic libraries, which enabled a granular understanding of the algorithmic processes involved. The core mathematical components—primality testing, modular exponentiation, and primitive root generation—were implemented manually to analyze their individual impact on the overall security and efficiency of the key exchange.
A custom primality check function was initially used to ensure the integrity of the prime number input, which is critical in the protocol since the security of Diffie-Hellman heavily depends on the hardness of the discrete logarithm problem in a finite prime field. In contrast to relying on prebuilt methods like Miller-Rabin or Fermat’s test, a basic trial division approach was used at first to maintain clarity and traceability in the educational scope of the simulation. However, this method became inefficient for primes larger than 64 bits. Therefore, it was replaced with the Miller-Rabin probabilistic primality test, which significantly improved performance and scalability for larger bit lengths. The algorithm was further validated using Baillie–PSW tests for spot-checking correctness on larger primes.
One of the key challenges addressed in this research was the identification of primitive roots modulo a prime, which is essential for generating the base used in the key exchange. An algorithm was designed to iteratively test potential candidates by verifying the distinctness of the residues:
or equivalently:
ensuring that all p-1values are distinct modulo ppp, which is the defining property of a primitive root modulo p. This component is crucial, as the security of the shared secret depends on the proper selection of a generator that fully spans the multiplicative group of integers modulo p.
Through a series of controlled experiments, the simulation successfully demonstrated the congruence between the shared secrets calculated independently by Alice and Bob. For each input, both parties generated their respective public keys using the formula:
To validate the correctness and efficiency of the implemented Diffie-Hellman key exchange simulator, a series of tests were conducted using prime numbers of increasing bit lengths—specifically 256, 512, 1024, and 2048 bits. For each test case, random private keys were selected for both participants, a valid primitive root was identified, and the corresponding public keys were generated. The shared secret computed independently by both parties consistently matched, confirming the correct execution of modular exponentiation and adherence to the protocol’s mathematical structure.
To evaluate both correctness and performance, the protocol was executed on a range of cryptographically meaningful prime sizes, specifically 32-, 64-, 128-, 256-, 512-, 1024-, and 2048-bit safe primes. For each size, average runtimes and standard deviations were recorded for three core operations: primality testing, primitive root generation, and a single modular exponentiation. The results show predictable scaling behavior, with clear distinctions in computational cost across operations.
Originally, primality checking was implemented using basic trial division, which became inefficient for primes larger than 64 bits. This was replaced with a Miller-Rabin probabilistic primality test, significantly improving performance and scalability for larger bit lengths. The algorithm was further validated using Baillie–PSW tests for spot-checking correctness on larger primes.
Primitive root generation, one of the computational bottlenecks in the protocol, was initially observed to scale approximately with 
, due to up to 
modular exponentiations performed in the worst case. However, by factoring 
and applying the Pohlig-Hellman condition for generator validation, the number of required exponentiations was dramatically reduced. Empirical results confirmed substantial speed gains, particularly for primes larger than 512 bits.
Modular exponentiation, implemented via exponentiation by squaring, scaled efficiently with time complexity O(log a), allowing shared secrets to be computed rapidly, even for 2048-bit parameters.
In terms of correctness, for each test case involving safe primes and random private key pairs, both participants computed identical shared secrets, validating that the simulation faithfully reproduces the Diffie-Hellman key exchange protocol.
A comprehensive set of tables summarizes average computation times and standard deviations for each core step. These demonstrate how the system performs under varying levels of cryptographic strength and confirm that, when implemented with algorithmic optimizations, the protocol remains practical even for high-security parameters.
To evaluate the practical implications of primitive root identification for Diffie-Hellman key exchange, we first contextualized our work with respect to recommended key sizes and their corresponding estimated security levels, as shown in Table 1.
| Prime Size(bits) | Estimated Security (bits) | Notes |
| 1024 | ~80 bits | Minimum for legacy systems |
| 2048 | ~112 bits | Recommended minimum for current use |
| 3072 | ~128 bits | Equivalent to AES-128 |
| 7680 | ~192 bits | Long-term security |
| 15360 | ~256 bits | Equivalent to AES-256 |
These values align with NIST and other international cryptographic standards. For example, a 2048-bit prime is considered the minimum safe size for use today, offering a level of security roughly equivalent to 112-bit symmetric encryption.
Generator Search Time and Algorithmic Optimization
In the classical approach, identifying a primitive root modulo a prime ppp involves testing multiple candidates ggg, ensuring that the set
covers all residues of the multiplicative group 
. This brute-force search is known to have a theoretical complexity of due to the exponentiation and uniqueness checks required.
However, in practice, the actual number of modular exponentiations performed is significantly fewer—approximately
based on our implementation. To optimize further, we employed the Pohlig-Hellman technique by factoring 
, which reduces the search space by verifying conditions against the prime factorization of p-1. This dramatically improves performance, especially for larger primes.
We validated this claim experimentally by measuring the average time and standard deviation for generator discovery across primes of varying bit lengths. The results are summarized in Table 2.
| Prime Bit Length | Average Time | Standard Deviation |
| 256 | 0.00012 | 0.00002 |
| 512 | 0.02360 | 0.00280 |
| 1024 | 0.06618 | 0.00522 |
| 2048 | 0.13071 | 0.00947 |
As observed, the execution time increases moderately with the bit length of the prime. This confirms that the optimization based on the Pohlig-Hellman strategy is effective even at scale. The difference becomes especially relevant when comparing small “toy” primes often used in theoretical demonstrations (e.g., 17, 19, 23) to cryptographically meaningful sizes such as 1024 or 2048 bits.
Methods
Mathematical Process of Diffie Hellman Key Portocol
The group-generation algorithm used for the protocol is determined by a group function 
, a prime number 
, and a generator function 
. All parties involved agree on these values and perform their calculations based on them.
When two parties wish to communicate securely, they use the group function 
and their own private keys 
to compute their public keys 
. The computed public key is then shared with the other party through the system. The other party follows the same procedure to calculate their own private key. Afterward, both parties exchange these values, so Alice obtains Bob’s public key 
, and Bob obtains Alice’s public key .
Thus, Bob can use the public key he received from Alice and his private key to compute 
, while Alice uses the public key she received from Bob and her private key to compute 
. Both parties now share a common secret key, which is the result of applying exponentiation in modular arithmetic. This method allows both parties to agree on a shared and secret key without revealing their private keys over an insecure channel.
The security of the shared key depends on the Diffie-Hellman problem, specifically the Decisional DiffieHellman problem. In simple terms, it is assumed that anyone intercepting the communication between Alice and Bob can only observe the value and cannot compute the individual values and because the oneway function makes it computationally hard to reverse the operation. This makes Diffie-Hellman a secure protocol, as it is considered difficult to solve.
- Alice and Bob agree on the prime number
and the base 
. - Alice selects a secret integer
and sends 
to Bob. 
- Bob selects a secret integer
and sends 
to Alice. 
- Alice computes the shared secret
. 
- Bob computes the shared secret
. 
- At this point, Alice and Bob both have the same shared secret: .
- This is because
. - Anyone who knows these two secret integers can compute the shared secret as follows:
Notice that only 
, 
, and are kept secret.
All other values — , , 
, and 
— were openly exchanged.
Once Alice and Bob have agreed on the shared secret key, they can use it for encryption in future messages over an open communication channel.
Coding For the Simulator
This Python script simulates the Diffie-Hellman key exchange protocol using only standard libraries. It begins by prompting the user to input a number, which it tests for primality using the Miller-Rabin probabilistic algorithm. Once a valid prime is provided, the script generates a primitive root modulo that prime using a brute-force approach. The simulation then proceeds to generate private keys for two parties (Alice and Bob), computes their corresponding public keys via modular exponentiation, and derives a shared secret for each party. The shared secrets are compared to verify that the key exchange was successful. Additionally, the script estimates the cryptographic security level based on the bit length of the prime. While this implementation is educational and demonstrates the core mechanics of the Diffie-Hellman protocol, it is not suitable for real-world use due to the use of small primes and basic algorithms for root generation and primality testing.
Conclusion
This project has effectively demonstrated the intersection of theoretical mathematics and practical cryptography through a self-contained simulation of the Diffie-Hellman key exchange. By focusing on the computational and cryptographic impact of elementary yet fundamental number-theoretic algorithms, the research highlights the essential role that prime numbers and group generators play in ensuring secure communication.
Unlike many studies that treat cryptographic protocols as black-box applications, this research approached the problem from the ground up—constructing each mathematical function manually. This allowed for deeper insight into how individual components such as primality, modular exponentiation, and group generation interact to create a secure cryptographic environment. It also provided an opportunity to observe the computational costs, efficiency limits, and mathematical elegance of these components.
The findings confirmed the correctness and internal consistency of the Diffie-Hellman scheme under controlled inputs. However, the analysis also revealed computational bottlenecks, particularly in the naïve implementations of primality testing and primitive root generation. These limitations suggest several promising directions for future research. One area involves the integration of probabilistic primality tests, such as the Miller-Rabin algorithm, to significantly reduce input validation time. Additionally, implementing more efficient primitive root discovery methods—especially those that leverage the known factorization of ϕ(p)—could enhance performance and scalability. Expanding the simulation to support large prime values (e.g., 2048 bits or more) would align it with current cryptographic standards and provide a more realistic assessment of performance. Lastly, incorporating basic threat models, such as man-in-the-middle attacks, could help evaluate the protocol’s robustness under adversarial conditions and further reinforce its educational value.
In conclusion, this study bridges the gap between mathematical theory and cryptographic application, showcasing the power of algorithmic number theory in the design of secure systems. By simulating the DiffieHellman protocol at a fundamental level, it contributes both educationally and analytically to the understanding of secure communication protocols.
References
- A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography. CRC Press (1996). [↩]
- RFC 7919. Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for TLS. IETF (2016). [↩]
- RFC 2631. Diffie-Hellman Key Agreement Method. IETF (1999). [↩]
- M. Al-Kuwari, R. Hussein. Diffie-Hellman Key Exchange Protocol and its Generalization. In Proceedings of the World Congress on Engineering, 1, 6–8 (2011). [↩]
- RFC 3526. More MODP Diffie-Hellman Groups for Internet Key Exchange (IKE). IETF (2003). [↩]
