Python public-key cryptography example

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

):

Implemented functions:

• 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.