Simpliest as possible implementation of asymmetric encryption with Public-key in Python. Something like RSA, but easier and clearer.
Python's built-in math functions are not used for clarity.
(:
Except for basic operators:
Floor Division
Modulo Division
Exponent
Bitwise Operators
):
- Binary search to find floor square root of positive integer
- Modular exponentiation by repeated squaring for fast computation of large positive integer powers of a number
- Euclidean algorithm for computing the greatest common divisor (GCD) of two numbers
- Extended Euclidean algorithm that computes coefficients of Bézout's identity to find Private-key exponent (modular multiplicative inverse of Public-key exponent)
- Trial division (easiest to understand of the integer factorization algorithms) to determine whether a number is a prime
- Fermat primality test to check it exponentially faster way
Large messages are splitts into blocks.