4

I am trying to understand RSA encryption but the algorithm seems quite complex.

I know that with asymmetric encryption you use a key and a function to encrypt data and a different function to decrypt it.

I understand the xor-ing used in most basic symmetric algorithms (functions). The same key (a series of bits of the same length as the plain data is used to encrypt and decrypt). This is possible because the xor function is symmetric (from what I know).

What are some examples of asymmetric functions? What is the function that you use to encrypt and what is the function you use to decrypt and how do you compute the second argument of the function (the first one being the data you are trying to encrypt/decrypt)?

Simon East
  • 440
  • 5
  • 10
yoyo_fun
  • 183
  • 7
  • 1
    You may want to ask this question to the crypto community. You will probably get a more technical and reasoned answer there. – Brent Kirkpatrick Mar 20 '16 at 19:24
  • If you think of algebraic theory, then an asymmetric function would be one that is not its own inverse. – Brent Kirkpatrick Mar 20 '16 at 19:25
  • That is correct. That is what I had in mind when I said symmetric ( I am not sure if it is the right term though). So xor is symmetric because the inverse of xor is xor. Is there any other definition of symmetric function? – yoyo_fun Mar 20 '16 at 19:29
  • Okay, then you know the definition and you are asking for examples. Most functions seem not to be symmetric: mod, division, addition, etc. Some permutations are symmetric. – Brent Kirkpatrick Mar 20 '16 at 19:35
  • Yes but I would like an example that is / can be used in an encryption / decryption scheme. I would like to know an example of some function whose inverse is more harder to calculate than the function itself. – yoyo_fun Mar 20 '16 at 19:39
  • 1
    RSA isn't that complicated, actually. You can do it on paper and [there is a simple example on the wiki](https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example) that may help you to understand what is happening there. Rather than trying to understand schemes that are simpler (they exists, but are insecure), you may as well understand RSA. You only need to know a tiny part of maths to understand that (and parts of it you learned when learning to tell the time) – Tobi Nary Mar 20 '16 at 19:45
  • If you expand that some, I think it would be a good answer @SmokeDispenser – Neil Smithline Mar 20 '16 at 19:49
  • @SmokeDispenser Thanks for that comment. Perhaps you should answer the question, instead of just comment! – Brent Kirkpatrick Mar 20 '16 at 19:53
  • 1
    Brent - we have a rule: Be Nice! You are very close to overstepping the line here. I will respond to flags. – Rory Alsop Mar 20 '16 at 20:49
  • Reading the introductory theory on encryption is a good place to start. The main idea is that reversing the encryption function should be an NP-hard problem (for which the fastest known algorithms are exponential-time algorithm). Please bare in mind that we do not know if NP-hard problems are actually harder to invert than to compute in the forward direction. – Brent Kirkpatrick Mar 21 '16 at 01:10
  • Cross-posted on Crypto.SE: https://crypto.stackexchange.com/questions/33850/what-would-be-a-simple-example-of-an-asymmetric-encryption-function-asymmetric – SEJPM Mar 21 '16 at 09:00

1 Answers1

7

RSA is about the simplest known instance of asymmetric encryption. There are a few others, but all of them rely on mathematics.

Symmetric encryption is easy (conceptually), because it is just about making a big knot with the data, and remembering how the knot was made; with that knowledge (that's the "key") you can untie the knot, basically by undoing all operations in reverse order.

Asymmetric encryption requires something magical. If you want to go with the knot metaphor, then it is a kind of knot where even knowing how things were tied up does not reveal how to untie them. In cryptographic terms, it must not be feasible to recover the private key (which is the power to decrypt data), even if the public key (the power to encrypt data) is known. Private and public key share a common mathematical structure, since one decrypts what the other encrypts, but that structure must resist analysis.

In this answer, I tried to explain RSA in simple terms. If you want to understand asymmetric cryptography, then you have to grasp enough mathematics to understand RSA. The good news is that such knowledge is not that hard, and it is reusable. So I encourage you to work up your algebra. Basically, you have to get familiar with the notion of computing things "modulo" an integer.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • I remember a dictionary metaphor being useful. – Deer Hunter Mar 20 '16 at 20:24
  • Is this "modulo" the modulo from C programming language: with the % symbol ? – yoyo_fun Mar 20 '16 at 20:26
  • 1
    @yoyo_fun: it is, except that in order to reach decent security (i.e. resistance to attackers who know their maths), RSA is done with integers which are quite bigger than that C offers. With C, integers are up to 64-bit, but with RSA we usually handle 2048-bit integers. Some libraries (e.g. gmp) or programming languages have support for big integers (e.g. Java's `BigInteger` class). – Thomas Pornin Mar 20 '16 at 20:43