In any asymmetric encryption specifications, there is a step where we need to calculate
data ^ public_key mod e to get
encrypted_data, and, also, to decrypt using
encrypted_data ^ private_key mod e. it's recommended to have keys to be around 2048 bits in length, and considering that we want to encrypt something small, let's say 256 bits of data, and , according to the specification, we have to calculate
(2^256) ^ (2^2048), in which,
(2^256) how big our data is, and,
(2^2048) is how big our public_key. I can't even imagine how big the result going to be, it certainly doesn't seem possible to be calculated in seconds, but, on the other hand, it's calculated less than a second if you try the code below.
so, how is it done? how to calculate numbers with a very high exponent like this? do I miss something or there is a trick to calculate this very fast?
from time import time from cryptography.hazmat.primitives.asymmetric import padding from cryptography.hazmat.primitives import hashes from cryptography.hazmat.primitives.asymmetric import rsa message = b"encrypted data encrypted data encrypted data" private_key = rsa.generate_private_key( public_exponent=65537, key_size=2048, ) start_time = time() ciphertext = private_key.public_key().encrypt( message, padding.OAEP( mgf=padding.MGF1(algorithm=hashes.SHA256()), algorithm=hashes.SHA256(), label=None ) ) end_time = time() print(type(private_key)) end_time-start_time