0

I am oversimplifying but I understand that a public key is the product of two large prime numbers. In essence as long as the private key is kept private, the owner knows something that the outside world does not.

My question is, how, in simple terms does one take a string or number (like a proposed symmetric key for a session) and encrypt it with the public key, in such a way that:

a) the rest of the world with the public key cannot decrypt it (since they also have the public key) and b) the owner with the private key can?

Thanks.

8

There's a few different things here.

a public key is the product of two large prime numbers

That is partially true for RSA, though RSA public keys also contain an additional integer (e, in the algorithm's description). Other public key algorithms, and even public key ciphers, do not work the same way (see ElGamal Encryption, for example.)

as long as the private key is kept private, the owner knows something that the outside world does not

This is correct. Specifically, the critical element is that only the holder of the private key can perform operations (in practice, generally just "reversal") related to operations that can be performed with the public key, and the private key cannot be derived (in a remotely plausible amount of computation) from the public key.

how, in simple terms does one take a string or number (like a proposed symmetric key for a session) and encrypt it with the public key

The Wikipedia link for RSA, given above, has a very nice step-by-step breakdown of the algorithm in use for both encryption and decryption, in math you can probably follow (the other algorithms arguably require more mathematical background).

in such a way that the rest of the world with the public key cannot decrypt it (since they also have the public key)

Anybody can encrypt a given plaintext with a given public key, and produce a ciphertext that cannot be decrypted without the corresponding private key.

Two parties with the same plaintext and the same public key will, if they use the same padding (basically, a way to convert or short string or number into a number of the correct size for the cipher in question) and cipher, produce the same ciphertext; an adversary who knows that the plaintext was one of a limited number of values could potentially use this to identify which value it was, but for a key exchange (such as is used in OpenPGP, SSH, TLS, etc.) it'd be just as easy or easier to simply try each candidate symmetric key on the message (and its authentication code) until one of them matches. Symmetric encryption (and decryption) is way faster than public-key encryption. In practice, the attacker has no knowledge about the symmetric key beyond perhaps its length, and brute-forcing even a 128 bit key takes a quite impractically long time (terms like "lifetime of the sun" are sometimes used to describe such time spans).

in such a way that the owner with the private key can?

Well, that's the whole point of public-key cryptosystems; two keys, and (at least) one of them can be used to do some operation but the complementary operation requires the other. For RSA in particular, the trick is to set up modular exponentiation (c = (m^e) mod(n)) such that it can be reversed only via modular exponentiation using a number d that is related to e and n (m = (c^d) mod(n)).

Specifically, d is the modular multiplicative inverse of e modulo Carmichael's totient function of n, and computing that requires knowing the prime factors of n, and since n is a really stupidly big number, factoring it is completely impractical (but simply finding any two stupidly big primes and multiplying them together is a lot easier, and then you already have the factors, so key generation is practical).

To use even smaller, more "toy-like" numbers than the example from Wikipedia:

  • Choose p = 11 and q = 13 (these are distinct primes; they're also only four bits long so this is going to be a really weak key).
  • n = 11 * 13 = 143 (eight bits long - that is, between 128 and and 255 inclusive - so yeah, really weak).
  • Carmichael's totient of n is the least common multiple of p-1 and q-1; LCM(10, 12) = 60.
  • Choose an e that is in the range 1 < e < 60 and is coprime (has no factors in common) with 60: e = 7 (2,3,4,5,6 are all factors of 60; 7 is prime so it's coprime with anything except its own multiples and 60 is not a multiple of 7).
  • To compute d, we find the number such that 1 = (d * e) mod 60 (or in other words, d * e is one more than a multiple of 60); 301 is one more than a multiple of 60, and 43 * 7 = 301, so d = 43.
  • So the public key is n = 143, e = 7
  • The private key is n = 143, d = 43

The ciphertext c is m^e mod(n). Anybody with the public key (which contains m and e) can compute this, for any given m. Let's say we want to encrypt the message "42" (we'll say m = 42). In our case, the math looks like this:

  • 42^7 = 230,539,333,248
  • 81 = 230539333248 mod(143), so c = 81.

We (who have the public key but not the private key) send the number 81, along with the fact that it was encrypted with this particular public key. The recipient, holding the corresponding private key, decrypts the message using m = c^d mod(n):

  • 81^43 is a quite large number, approximately 1.161 * 10^82 (if you're following along at home, make sure you have a calculator that uses a good bignum library!)
  • That giant number, modulo 143, is... 42!

So, we successfully decrypted the message, using our knowledge that d was 43. However, it'd be quite impractical to figure out what d is without knowing p and q. A TI-83 can probably tell you the prime factors of n = 143 in milliseconds, but a "real" RSA public key's modulus n is so large, it puts the value of 81^43 (which is 83 digits long in base 10, and takes 273 bits to represent!!) to shame. We're talking really big numbers here, like 7.5x that long. Good luck figuring out the prime factors of one of those!


If you want to know more about the general theory behind public-key cryptosystems, or want an explanation of how any particular one works, you might want to check out https://cryptography.stackexchange.com/.

  • This answer is very complete and accurate. I would just add that, in real world, one usually will crypt with a symmetric algorithm (AES for example) and crypt the symmetric key with RSA. – binarym Jul 14 at 10:08
  • @binarym One usually agree on a key as DHKE or better the ECDHKE then use AES-GCM. See TLS 1.3 cipher suites. – kelalaka Jul 14 at 14:01
  • 81^43 is really large and is quite difficult to compute without a bignum library, but 81^43 (mod 143) is much easier to compute and can be computed without ever having intermediary numbers larger than 11583. – Lie Ryan Jul 15 at 0:53
2

In simple terms, RSA encryption is a trap-door function: easy to calculate in one way, hard in reverse. Chiphertext is generated by using modulo operation on a result of the computation involving public key and the message.

message = 123
result of the computation = 1234567890
ciphertext (result of the computation modulo 1000) = 890

The numbers in the private key, public key and the modulo operation are set up in such way to map each message number to exactly one ciphertext number. Because ciphertext is a result of the modulus operation, the maximum ciphertext length is limited (in my example ciphertext < 1000). This also means that message number should be < 1000, or you would not decrypt the message correctly.

The "one way" property is given by the modulo operation: it's really easy to calculate if you know the result of the computation, but really hard to find out what was the result of the computation that resulted in a given ciphertext. However this task becomes really simple if you know original primes (the private key).

This is only useful for surface-level understanding of the RSA, the real math is not much more complicated, but the devil hides in the proper choice of the numbers that are used in the RSA. Even the message has both lower and upper limits of secure length.

Use wikipedia if you need to understand this algorithm, use cryptographic libraries if you actually need to do RSA encryption, and use high-level "authenticated asymmetric encryption" cryptographic protocols (such as TLS) if you want to transmit data securely.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.