64

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?

  • 17
    A nice video on RSA encryption: 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
  • 7
    I like this video that uses the mixing of colors: 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 – erich2k8 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) – immibis Apr 23 '15 at 0:34
88

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.

  • 4
    @AronFoster: We don't know if anyone has. – Guntram Blohm Apr 22 '15 at 16:50
  • 6
    @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
  • 15
    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. – Thomas Bonini Apr 22 '15 at 18:38
  • 5
    @AndreasBonini, this would be an instance of lying to children – sleblanc Apr 22 '15 at 19:22
  • 14
    @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
43

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.

  • 1
    Best answer compared to the rest. – Pacerier May 1 '15 at 11:09
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.)

  • 5
    Hahaha! Just for completeness, could you mention what 'balls' is a metaphor for? – Mike Ounsworth Apr 22 '15 at 17:26
  • 24
    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
  • 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. – Thomas Pornin Apr 22 '15 at 20:00
  • 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 9:04
  • 13
    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.

  • 4
    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
  • 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

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.

  • Where does the 143 come from? What's the public key here, and what's the private? This answer leaves a lot to be desired, but it is fixable. – Chris Cudmore Apr 24 '15 at 13:23
  • @ChrisCudmore thank you, I'll edit to improve it as you commented – woliveirajr Apr 24 '15 at 16:20
  • It looks like '5' is the message. – Chris Cudmore Apr 24 '15 at 17:02
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.

protected by Rory Alsop May 7 '15 at 7:25

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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