71

As the title suggests, I am curious to know why you can't work backwards using a message, public key and encrypted message to work out how to decrypt the message!

I don't understand how a message can be encrypted using a key and then how you cannot work backwards to "undo" the encryption?

Max
  • 829
  • 1
  • 7
  • 6
  • 20
    A nice video on RSA encryption: https://www.youtube.com/watch?v=M7kEpw1tn50 It helped me in understanding why it's so damn hard to crack :) – BadSkillz Apr 22 '15 at 15:12
  • 8
    I like this video that uses the mixing of colors: https://www.youtube.com/watch?&v=3QnD2c4Xovk#! – nowen Apr 22 '15 at 19:57
  • 1
    The whole point of asymmetric key encryption is that the key that you use to encrypt *can't* be used to decrypt -- you need its counterpart. – Shadur Apr 22 '15 at 21:11
  • @BadSkillz - Thanks... now I'm going to end losing the rest of my day watching their other videos. :P – Eric Haynes Apr 22 '15 at 22:10
  • Why can't you just work backwards with an MD5 hash to find the original input? (or at least *an* input that gives you the same hash) – user253751 Apr 23 '15 at 00:34
  • Actually, you can! The problem is going forward and going backward are not something you can do at the same efficiency. We rely on working backwards being out of reach in terms of time to do it. – Rob Apr 23 '15 at 02:10
  • @BadSkillz Fairly good video, but it does have a couple of flaws. It suggests RSA is used in ECB mode, that's a bad idea for multiple reasons. Moreover using an even modulus is slightly misleading. – kasperd Apr 23 '15 at 07:32
  • Here are a few more answers that are possibly more useful for some people. I think the original intent of the question was "if X steps with Y inputs are well known, then why cant they be done in reverse already knowing these to get the original answer?" related the actual specific mechanics of operating the algorithms, and not so much the more self-evident human obfuscation/entropy using math part. The link: https://crypto.stackexchange.com/questions/18658/why-cant-you-decrypt-an-encrypted-message-with-just-the-public-key – Celess Jun 06 '15 at 23:58
  • It's actually possible for a hacker to decrypt the message using only the public key. But that's extremely hard for any computer today. Because reverting that encrypted message using that public key is a very hard mathematical operation especially when that key is as large as 2048-bit number. The strength of the mathematical operation relies on the hardness of the prime factorization of a large number. Here's great video explaining this https://www.youtube.com/watch?v=wXB-V_Keiu8 – Mahmoud Zalt Nov 20 '17 at 01:17

7 Answers7

99

There are one-way functions in computer science (not mathematically proven, but you will be rich and famous if you prove otherwise). These functions are easy to solve one way but hard to reverse e.g. it is easy for you to compute 569 * 757 * 911 = 392397763 in a minute or two on a piece of paper. On the other if I gave you 392397763 and asked you to find the prime factors, you would have a very hard time. Now if these numbers are really big, even the fastest computer in the world will not be able to reverse the factorization in reasonable time.

In public-key cryptography these one-way functions are used in clever ways to allow somebody to use the public key to encrypt something, but making it very hard to decrypt the resulting message. You should read the Wiki article RSA cryptosystem.

thesquaregroot
  • 203
  • 1
  • 8
Lucas
  • 1,371
  • 11
  • 11
  • Bold claims. Is the existence of one-way functions mathematically proven (a few years ago it wasn't)? Is there a proof that the functions used in public key crypto systems are really one-way? – jk - Reinstate Monica Apr 22 '15 at 16:20
  • 3
    @jknappen Proving their existence or lack thereof would be solving P=NP. However, we don't have to rely on them being mathematically proven to be one-way to use them for computer security: nobody has yet managed to find a quick way to factor large primes. – Aron Foster Apr 22 '15 at 16:29
  • 4
    @AronFoster: We don't know if anyone has. – Guntram Blohm Apr 22 '15 at 16:50
  • 1
    @jknappen:Fair enough (I added a note in parenthesis). To mathematically proof the existence of one-way functions has turned out to be extremely difficult, but crypto-systems work under the assumptions that they exist and I think the vast majority of mathematicians and computer scientists also assume that they exist. – Lucas Apr 22 '15 at 16:51
  • 7
    @GuntramBlohm And we don't know if every Intel chip has a backdoor that'll let the NSA read everything you write. There are an infinite number of risks out there, and there's a point where something's so unlikely that it's not worth focusing your attention on. – Aron Foster Apr 22 '15 at 17:06
  • 20
    Those remarks are really out of scope of the question, which is obviously a beginner question. Being lawyer-y pointing out that we haven't technically proven the existence of one-way functions when in practice they're used all the time as such, will just confuse the asker and provides no real value. So this is not "fair enough" and imo you shouldn't have edited it in. – Andreas Bonini Apr 22 '15 at 18:38
  • 5
    @AndreasBonini, this would be an instance of [lying to children](https://en.wikipedia.org/wiki/Lie-to-children) – sleblanc Apr 22 '15 at 19:22
  • @GuntramBlohm Being able to quickly factor the product of large primes isn't something that would remain a closely-held secret by some government. It would be a major mathematical accomplishment the likes of which happens maybe once in a generation. – Blazemonger Apr 22 '15 at 21:08
  • @AronFoster We dont? I thought everyone knew they had. – Cthulhu Apr 23 '15 at 09:07
  • You don't need just a one-way function (like a hash function), but usually a trap-door one-way function. (Also, you don't need them just to exist, but actually that the function you are using one is one.) – Paŭlo Ebermann Apr 23 '15 at 21:04
  • 19
    @AndreasBonini Stack Exchange sites aren't just for the person asking the question. They're also for others that come along with the same question. There's no need to intentionally leave out details: just explain it in simple terms (as Lucas has done). – mason Apr 23 '15 at 22:44
  • 3
    @AronFoster: Factoring large primes is easy. Factoring non-primes without small prime divisors is hard. – tomasz Apr 24 '15 at 02:08
  • 2
    @mason: it depends on how pedantic are the details. This is analogous as mentioning the potential disturbance from cosmic rays when someone asks how to do a multiplication in C++ – Andreas Bonini Apr 24 '15 at 10:13
  • 2
    @AronFoster I don't think that the factoring problem is equivalent to P=NP (or at least not proven to be). – ypercubeᵀᴹ Apr 24 '15 at 10:23
  • 4
    @AndreasBonini No, it's not similar to that at all. Lucas explained in clear terms how encryption works, and it's highly relevant to understand the limitations of that process. It doesn't take a genius to understand what Lucas wrote, which is what makes it a good answer. Don't encourage people to leave out important details on Stack Exchange, because the answers are for *everyone*, not just the first person to ask it. That's a core principal of SE sites. – mason Apr 24 '15 at 13:20
  • @tomasz "Factor large [semiprimes](http://mathworld.wolfram.com/Semiprime.html)" was probably meant. – Damian Yerrick Apr 25 '15 at 14:23
53

Your question is a little like this (with apologies to Tom Stoppard): "why can I stir the jam into my rice pudding, but not stir it out again?"

Some mathematical operations are as easy to do backwards as forwards. For instance you can add 100 to a number as easily as subtracting 100. However, some are more difficult to reverse. For instance, if I take x and find g(x) = a(x^5)+b(x^4)+c(x^3)+d(x^2)+ex+f, I have to do merely simple multiplies and adds. But to get back from g(x) to x is difficult (in an algebraic manner) as there is no general algebraic solution to a quintic equation. It's not immediately obvious why that should be the case (as opposed to a quadratic equation), but it is. For a more appropriate example, if I told you that 34129 and 105319 were both prime (which they are) you would be able to quickly work out that their product was 3594432151. However, if I asked you to find the two prime factors of 3594432151, you'd probably find that rather harder.

Public key cryptography takes a pair of keys. In general, the private key provides the parameters a difficult to reverse algorithm going in one direction (e.g. plain text to cypher text), and the public key provides parameters for a difficult to reverse algorithm going in the other.

So, the reason you can't work backwards is simply because the algorithm is designed to make this hard.

abligh
  • 2,026
  • 11
  • 12
39

Juggling is easy: you just throw the balls at the right time, so that you have a free hand when they fall. With one ball or two balls, this is trivial. With three, it is easy enough. With more balls, it (surprisingly) becomes harder. Even substantially harder.

In all generality, "reversing" encryption done using an n-bit key is like juggling with 2n balls. With a 2048-bit key this is like 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 balls. Or so.

(Of course, since public key algorithms use a lot of mathematical structure, smart minds have leveraged maths to reduce that number of balls to 162259276829213363391578010288128, which is considerably lower, but still way beyond the aggregate power of all existing computers on Earth.)

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 5
    Hahaha! Just for completeness, could you mention what 'balls' is a metaphor for? – Mike Ounsworth Apr 22 '15 at 17:26
  • 26
    It is a metaphor for the front row of a breadth-first exploration of a graph that represents the encryption system expressed as a finite-state automaton. – Thomas Pornin Apr 22 '15 at 17:34
  • 1
    @ThomasPornin: Great answer! Can you provide a citation for the `162259276829213363391578010288128` value? That looks like it's 2^107, and I found this: https://www.imperialviolet.org/2011/04/09/multiprime.html, but I was wondering if you had a more authoritative source or an explanation that you preferred. – John Feminella Apr 22 '15 at 19:08
  • 4
    There are various bodies that try to do estimates of how RSA key sizes compare to symmetric keys. Ultimately, there is not a single answer since we are comparing distinct kind of algorithms (for symmetric key cracking, RAM does not count; while it counts a lot for integer factorization). Equivalence for RSA thus ranges between about 100 and 112 bits, depending on whom you ask and what you consider to be a "unit" operation. "107" derived from the raw application of the complexity of the [General Number Field Sieve](http://en.wikipedia.org/wiki/General_number_field_sieve). – Thomas Pornin Apr 22 '15 at 20:00
  • 1
    If you want "authoritative" sources, have a look at [this site](http://www.keylength.com/en/). In particular, application of ECRYPT II's equations (from their last available yearly report, which appears to be from 2012...) leads to RSA-2048 being "equivalent" to a 103-bit symmetric algorithm. – Thomas Pornin Apr 22 '15 at 20:01
  • 4
    This answer kinda misses the point as it may make the impression that encryption with such a key is equally hard task. – Cthulhu Apr 23 '15 at 09:04
  • 14
    While this answer is entertaining for anyone who actually understands the basics of cryptography, it's hardly informative and I don't think it actually addresses the question asked. – Shaamaan Apr 23 '15 at 12:27
7

Max, the best tool ever created for thinking about cryptography is the Rubik's cube. If you presume a world where solving them is an unsolved problem, there are direct analogs for DiffieHellmanKeyExchange, RSA signing, RSA encryption, etc. You can play tricks with writing down moves and performing them on cubes and exchanging them; and the group theory equations are the same for the crypto and the rubiks cubes.

But the key thing to keep in mind, which I think is what must bother you: You are correct. It is "possible" to invert all of these operations. Technically, we have f(x) and f_inverse(x), where f(x) runs in polynomial time (ie: you can encrypt large numbers quickly), while f_inverse(x, s) runs in exponential time (ie: even medium numbers are infeasible) - unless you have the right secret s to plugin to f_inverse. Such function pairs are called trapdoors. The common trapdoors are number theory problems such as prime factorization and discrete logarithms.

Rob
  • 639
  • 3
  • 9
  • 6
    Thinking about a Rubik's Cube as an analogy for encryption would lead one to have the OP's question. If I do a bunch of steps (the key) with a cube in a given state (plaintext) to end up with a cube in a different state (cyphertext) I can then do the same steps backwards to get back to the original state (plaintext). That this doesn't apply to asymmetric encryption is the question being asked. – Jon Hanna Apr 24 '15 at 14:28
  • In Rubiks cube notation, the Reverse operation and Commutator operation are the same. To invert an operation, apply not only the inverse functions but apply them in reverse order. ie: (L * F * U).inv == (U.inv * F.inv * L.inv). The difference with asymmetric encryption is that the .inv operation is designed to be so inefficient that you can't do it without the help of a secret key. – Rob Apr 24 '15 at 15:00
  • This idea extends to hashes. A hash is a function for which the .inv operation is inefficient, and there is no secret key to help to make it efficient. Symmetric key encryption is where the .inv key is efficient. ie: Msg * SymmetricKey = CipherText. CipherText * SymmetricKey == Msg. Because X * X.inv == 1. – Rob Apr 24 '15 at 15:04
  • 2
    The point is that he is actually correct. It's not "impossible" to undo encryption. It's inefficient. Not only that, for the trapdoor schemes we use, it's not even proven that it's inefficient. We hope that nobody figures out prime factorization any time soon. – Rob Apr 24 '15 at 15:05
2

What you need to do is read up on Public-Key Cryptography. The short answer is it is based on an algorithm that allows one key to encrypt and the other key to do the decryption, which is why you cannot work backwards.

That is a simplified explanation of what is happening, if you want to get to the heart of the issue you can look at sources such as the following, but be warned it quickly steps off the cliff into some mathematics that may or may not be easy for you to follow: http://nrich.maths.org/2200

BeepBeep
  • 21
  • 1
0

In this public-key encryption (or assymetrical encription), to encrypt something, you do the following:

Take your message to be transmited (as a number) : let's say it's 5.

Calculate 3 ^ 5 (3 raised to the "secret") = 243

Calculate the modulus of it, divided by another number: let's say 143. So, 243 / 143 = 100.

There you go. Your encrypted secret is 100.

To find the secret, without the private key, you just need to find a number that when divided by 143 leaves 100 as result, and then find the cubic radix of it.

woliveirajr
  • 4,462
  • 2
  • 17
  • 26
0

Generally you can't work backwards—in the obvious way—because you don't have enough information.

RSA depends on the difficulty of factoring large numbers. You generate your RSA modulus n by multiplying two large primes, p and q. Multiplying p by q is easy. You can also reverse the operation by computing q = n / p (or p = n / q). What you can't easily do is throw away both p and q, then compute them from n. That's a different problem, not a reversal of some process you've already used.

Similarly, RSA encryption of a message m using encryption key e involves computing (m ^ e) mod n. You could theoretically invert m ^ e using logs, but without the modulo operation, this number would be too big to work with. In any case, the modulo operation discards part of the number, so again you don't have all the information you would need to work backwards in a trivial way.

Pete
  • 1
  • 1