Crypto 4: Math for Crypto, DHKE
by Rathul Anand
Modular arihmetic is an important language underlying modern cryptosystems. Many cryptographic alogirhtms rely on this arithmetic, where numbers "wrap around" after reaching a certain modulus. For example, the Diffie-Hellman Key Exchange (DHKE), which we cover in these slides, leverages modular exponentiation to enable tow parties to share a secret over an insecure channel. By applying modular arithmetic, both parties can compute the same shared secret without revealing or sharing their private keys. This principle forms the basis for secure communication in many asymmetric encryption schemes.
Slides
Challenges
The following challenges in increasing difficulty are deployed to platform.acmcyber.com to practice the concepts covered in the slides.
- Challenge 1 -
crypto/chinese-lazy-theorem-1 - Challenge 2 -
crypto/modular-practice - Challenge 3 -
crypto/lunchly-exchange - Challenge 4 -
crypto/chinese-lazy-theorem-2 - Challenge 5 -
crypto/golden-ticket - Challenge 6 -
crypto/lazy-lagrange
Resources
The following resources are great to practice/learn about the ciphers covered in the slides.
- pycryptodome: A library that implements many modern-day cryptographic algorithms.
- alperton: Has a discrete logarithm solver that works fast for small
n. - SageMath: An open-source mathematical software tool. Works with Python and has many constructs that are very useful in modular arithmetic/cryptography.