# 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!

```Python
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)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jins-organization-2.gitbook.io/muse-on-engineering/engineering/cryptography/explore-kms-rsa-encryption-a-tale-of-two-keys.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.