Skip to main content
added 182 characters in body
Source Link
dr jimbob
  • 39.5k
  • 8
  • 95
  • 164

(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.

(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 takes 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). 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.

Textbook RSA signing of a message is sometimes called "encrypting with the private key", and works similarly, you sign a message m by modular exponentiation with the private key (similar to RSA decryption) computing a signature S = m^d mod N. Then when you give someone a signed message (that is m and S 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. Instead, you create a random symmetric key (e.g., an AES key), use that random key to encrypt your 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 key. That is you pass the ciphertext c_aes = AES(k, m) (which will be as many blocks as the plaintext message) and the 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 the hash value of the associated plaintext message.

(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 that is asymptotically more efficient than factoring N.)

Textbook RSA encryption let'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 make a ciphertext c 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.

Signatures in textbook RSA are sometimes called "encrypting with the private key" and works very similarly with the main difference being the order. The person signing the message at the start uses modular exponentiation with the private key (similar to RSA decryption) to create a signature S = m^d mod N. Then when you give someone a signed message (that is m and S 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., a 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 RSA-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.

Source Link
dr jimbob
  • 39.5k
  • 8
  • 95
  • 164

You seem to recall the basics of how digital signatures work in the case of textbook RSA (that is RSA slightly oversimplified).

The RSA public key is composed of N (the modulus) which is the product of two large prime numbers (e.g., in 2048-bit RSA, N is a 2048-bit product of two 1024-bit primes) and the public exponent, e which is usually set to be 65537. The private key similarly consists of N and d, the private exponent.

(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 takes 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). 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.

Textbook RSA signing of a message is sometimes called "encrypting with the private key", and works similarly, you sign a message m by modular exponentiation with the private key (similar to RSA decryption) computing a signature S = m^d mod N. Then when you give someone a signed message (that is m and S 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. Instead, you create a random symmetric key (e.g., an AES key), use that random key to encrypt your 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 key. That is you pass the ciphertext c_aes = AES(k, m) (which will be as many blocks as the plaintext message) and the 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 the hash value of the associated plaintext message.