Public Key Cryptography From Scratch In Python
Public key cryptography empowers data encryption, secure data transmission, digital signatures, authentication, privacy or confidentiality and key exchange mechanisms for symmetric key algorithms. This course covers the most common public key algorithms: Diffie Hellman, RSA, ElGamal and DSA.
This is a hands on programming course including theoretical background and practical usage for real world problems to explore different public key algorithms.
Diffie Hellman Key Exchange Algorithm
Diffie hellman key exchange protocol enables to generate shared keys between parties in a secure way. We'll mention the background of the algorithm.
We'll adapt Diffie Hellman Key Exchange algorithm in python. Also, we'll use shared key in symmetric encryption.
RSA is the most common public key cryptography algorithm. Today, we'll mention its key generation and encryption - decryption procedures.
In RSA Overview, we've mentioned that randomly generated e and totient function must be coprime (or relatively prime). The question is that how can this tested? Euclidean algorithm finds the greatest common divisors. If GCD is equal to 1, then these two numbers are coprime. In this lecture, we'll mention the euclidean algorithm.
In RSA Overview, we've mentioned that randomly generated e and its multiplicative inverse d are public and private key pairs. So, how can we calculate the multiplicative inverse? Extended euclidean algorithm finds the multiplicative inverse of an integer faster. We'll mention the extended euclidean algorithm.
Until now, we have mentioned the key generation and encryption - decryption procedures. Now, we'll adapt all of these steps into a python code. Also, we'll work on really large prime numbers.
RSA can be used for signing messages digitally and verifying them. In this video, we'll mention the overview of digital signatures.
We are going to use RSA algorithm to exchange key between parties.
We are going to adapt key exchange schema to python in this lecture
Digital Signature Algorithm
Discrete Logarithm Problem
Decryption is handled by m = c^privatekey mod n formula. One can restore the message for known ciphertext, private key and n. However, extracting private key is not easy task for knwon message, ciphertext and n even though an attacker has plaintext, ciphertext pair. This refers to discrete logarithm problem.