Explore KMS' RSA encryption: a tale of two keys

I can never remember how RSA encryption works, so I made up a story ...

Picture this: A prison shaped like an enormous clock, laden with slots arranged circularly. The number of slots equals two ginormous prime numbers "P" and "Q" multiplied together.

In this prison resides our protagonist, Mike, making himself at home in slot 'm'. One fateful day, a guard with an IQ off the charts proposes a peculiar escape plan.

Guard: "How about a shot at freedom, Mike?"

Mike, seeing a glimmer of hope, takes up the offer. The task? Simple! Well, Mike needs to take exactly m^(65537) steps around this clock-like prison, one slot a step.

With the promise of freedom fueling his spirit, Mike trudges on and completes his epic m^(65537) steps, ending up in slot 'c'.

Guard: "Bravo, Mike! Now, walk back to your starting point."

Mike's joy fades quickly. He can't remember his starting slot!

But here's where things get interesting. The guard pulls out a mystical key that can decrypt the steps for Mike's return trip. This key harnesses some wizardry similar to RSA encryption, divulging a magic number 'd'. Now, Mike needs to undertake (c^d) steps around the clock.

Once 'd' is revealed, Mike sets off on his return journey. Gradually, each step begins to feel familiar, like he's nearing his original spot.

After (c^d) steps, Mike finds himself back at 'm'. He recognizes his starting point, and the guard's key magic proves successful!

The magical formula in the spotlight:

n = p * q φ(n) = (p-1) * (q-1) d = e^(-1) mod φ(n)

For RSA: Encryption: c = (m^e) mod n, e is a fixed prime number, often 65537 Decryption: m = (c^d) mod n

Now, let's delve into KMS APIs for RSA encryption and decryption using AWS CodeWhisperer!

kms_rsa_pub_der = kms.get_public_key(KeyId=keyId)["PublicKey"]
rsa_pub = serialization.load_der_public_key(kms_rsa_pub_der, backend=default_backend())

assert(rsa_pub.public_numbers().e == 65537, 'e from KMS RSA key is always 65537')

# Local encryption with oaep_padding using the public key c=m^e mod n
oaep_padding_sha = padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()), algorithm=hashes.SHA256(), 
 
ciphertext = rsa_pub.encrypt(message, oaep_padding_sha)

# Asking KMS to decrypt it, m=c^d mod n
decrypted = kms.decrypt(KeyId=keyId, CiphertextBlob=ciphertext, EncryptionAlgorithm='RSAES_OAEP_SHA_256')['Plaintext']

# Success! 
assert(decrypted == message)