We can check the co-primeness of two integer with math module of python. Thereafter, we should pick a random integer that co-prime to phi.

We do not want to spend that time! Private Public Key Pair Remember that n should be multiplication of two large primes. Otherwise, we can build a for loop to find positive integer numbers that co-prime to it but this requires O(n) complexity. In that way, we can find the phi with O(1) complexity. Instead of counting positive integer numbers that co-prime to it, we can find the multiplication of its multipliers’s totient function results. Herein, totient function is a multiplicative function. Even though, n is a prime number, it is the multiplication of two prime numbers. However, we picked the n as the multiplication of two prime numbers. We know that if n is a prime number, then positive integer number that co-prime to it should be (n-1). Totient function of n counts the positive integer numbers that co-prime to n. These variables are coming from the Euler’s generalization of Fermat’s Little Theorem. Then, we will find the module n and totient n (or shortly phi) variables from p and q. If you set a non-prime number to p or q, then this program will raise an error. A prime number must not be divided by another number less than it without remainder. To have a safety net, we should check the primeness of this p and q pair. In a practical application, these should be large primes but we will use small ones in this example. With that change, the code above decodes the message quickly.įurther improvements are possible, but more complicated, and won't be drop-in replacements.The algorithm expects to pick two prime numbers first. So decrypt can be written as: def decrypt(kenc, d, n): You could implement it yourself, but Python handily provides a built-in function for this: pow(x, e, n)

There is a simple remedy: use modular exponentiation, which keeps the size of the numbers that it is working with low throughout the whole calculation by reducing modulo n as it goes along. This does not finish in a reasonable time. Key = RSA.generate(1024, random_generator) For example, trying it out with 1024bit RSA (the lowest setting!): import Crypto Kenc**d is in general a very big number that takes a long time to compute, and then it takes a long time again to reduce it modulo n. There is a serious problem with this implementation: it computes kenc**d. In this case though, there is a much more efficient solution that is about equally simple, and is probably sufficient. Usually the most efficient way to perform a non-trivial task is not also the simplest way to do it. Simple does not mean fast, so you cannot judge performance based on how simple the implementation looks.

Python 3 decrypt rsa example