3

I understand the "public" part of public key cryptography. Not the "private" part.

For example, let's say our public key is %7 (modulo 7). And the message to be encrypted is 22.

And we know that 22 % 7 = 1

Here, 1 is the encrypted message.

The reason why public keys work is that despite knowing the public key (%7) and the encrypted message (1), I cannot confirm that the original message was 22.

So, this begs the question, how does the private key figure out that the original message was 22?

7
  • You are confusing hashing with asymmetric cryptography. Hashes are not reversible. Jul 17, 2015 at 17:55
  • 1
    This isn't an encryption scheme. At all. It's not an encryption scheme for the precise reason that you can't decrypt anything.
    – cpast
    Jul 17, 2015 at 18:03
  • @cpast Some public key cryptosystems (take RSA for example) can be used to encrypt.
    – Cthulhu
    Jul 17, 2015 at 18:05
  • 1
    @Cthulhu But this is not RSA. The scheme in the question is not an encryption scheme.
    – cpast
    Jul 17, 2015 at 18:10

1 Answer 1

6

What you presented is not an encryption scheme, you just took a number and modded it by 7. This can not be an encryption scheme because there is more than one "message" which will produce the same "cipher text", for example:

  • the message 22 produces the cipher text 22 % 7 = 1
  • the message 29 produces the same cipher text 29 % 7 = 1
  • the message 36 produces the same cipher text 36 % 7 = 1
  • . . .

So your question:

how does the private key figure out that the original message was 22?

It doesn't because for the cipher text "1", there are an infinite number of possible original messages.


What you have looks kinda similar to RSA, so I'm guessing that you read something about RSA and are trying to work through the math. There's a nice easy sample calculation of RSA here that you could try working through.

For a more detailed description of the math of RSA, you can go to the wikipedia page for RSA.


Edit: in comments you said:

if a modulo (public key) produces a result that cannot be reverse engineered, then how is the private key able to do it?

Alright, let's walk through that example of RSA.

  • You choose two primes, let's take p = 3, and q = 11
  • You compute n as n = p * q = 3 * 11 = 33
  • You compute φ(n) = (p-1)*(q-1) = 2 * 10 = 20
  • You choose a public exponent e such that 1 < e < φ(n), and that e and n are coprime. e = 7 will do.
  • You choose a private exponent d such that (d * e) % φ(n) = 1. d = 3 will work since (3 * 7) % 20 = (21) % 20 = 1

Now your public key is (7, 33), (e, n), and your private key is (3, 33), (d, n).

Ok, now let's say that you want to encrypt the plaintext message "22", as in your question. The encryption calculation is: m^e % n = c, where m is the original message and c is the ciphertext, so 22^7 % 33 = 22 (heh, that's a coincidence), so the encrypted message is "22".

Now, the person who has the private exponent d can decrypt the ciphertext by calculating c^d % n = m, is our example 22^3 % 33 = 22.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .