(If you know the prime numbers p and q, you can quickly calculate the private exponent, d, via Euclid's extended algorithm, where d is chosen to guarantee that (m^e)^d mod N = m
by finding d = e^-1 mod (p-1)(q-1)
which works due to Euler's theorem. In general, there is no publicly known way of finding d
given N and e without knowing the prime divisors other that is asymptotically more efficient than factoring N.)
Textbook RSA encryption takeslet's anyone with your public key take a message m
(which is assumed to be encoded into an integer that is smaller than N) and anyone with your public key can make a ciphertext c
that by calculating c = m^e mod N
(modular exponentiation), which can only be deciphered by people possessing the private key. Textbook RSA decryption is the same procedure of modular exponentiation, except instead of acting on the message and using the public exponent, it acts on the ciphertext with the private exponent. That is if you have the private key and the ciphertext, you can calculate m
via m = c^d mod N
.
TextbookSignatures in textbook RSA signing of a message isare sometimes called "encrypting with the private key", and works very similarly, you sign a with the main difference being the order. The person signing the message m
byat the start uses modular exponentiation with the private key (similar to RSA decryption) computingto create a signature S = m^d mod N
. Then when you give someone a signed message (that is mm
and SS
together), they can verify the message wasn't tampered with by doing modular exponentiation on the signature with the public key and verifying that S^e mod N
is equal to the original message.
The main difference between textbook RSA and real RSA for encryption, is that in real RSA you do not use RSA to encrypt the message you intend to send. Instead, you create a random symmetric key (e.g., ana 128-bit AES key), and use that random symmetric key to encrypt your arbitrarily sized message (which may be much larger than 2048 bits which is roughly the size of N), and then use textbook RSA to encrypt this random symmetric key. That is you pass the ciphertext c_aes = AES(k, m)
(which will be as many blocks as the plaintext message) and the encryptedRSA-encrypted AES key c_key = k^e mod N
to someone when you want to send an encrypted message. They then decrypt the AES key with their RSA private key, and use the decrypted key to decrypt c_aes
.
Similarly, the main difference between textbook RSA and real RSA for signing, is that in real RSA, you do not perform modular exponentiation on the message, which could be much larger than the modulus N. Instead, you run a cryptographic hash function on the message (like SHA-256), and then create a signature on this hash value. That is to sign you first hash the message h = sha256(m)
, then generate the signature S = h^d mod N
. To verify, someone with your public key, signature, and plaintext message can check that S^e mod N
is equal to their computation of the hash value of the associated plaintext message.