Public/Private Keys

[hazar]

Hi all,

I've been looking at the idea of encryption of traffic over the internet, just finished reading a lot of articles on how public key encryption works.

Here is what I understand so far:

1. Large random number is generated, from this a private and public key is generated
2. The Public key is freely available to anyone
3. If someone wants to send a message to a person using private key encryption then they encrypt things with the public key, send them then they are decrypted using the private key

I know that that is a very simplistic view of how things work but I have one problem with it:

What is to stop someone simply 'going backwards' in terms of the encryption process, for example if I encrypt something using a public key why can't I simply decrypt it using the same public key?

An answer to this would be greatly appreciated as I am quite confused as to how this would work.

[ph03nix]

Hi all,

I've been looking at the idea of encryption of traffic over the internet, just finished reading a lot of articles on how public key encryption works.

Here is what I understand so far:

1. Large random number is generated, from this a private and public key is generated
2. The Public key is freely available to anyone
3. If someone wants to send a message to a person using private key encryption then they encrypt things with the public key, send them then they are decrypted using the private key

I know that that is a very simplistic view of how things work but I have one problem with it:

What is to stop someone simply 'going backwards' in terms of the encryption process, for example if I encrypt something using a public key why can't I simply decrypt it using the same public key?

An answer to this would be greatly appreciated as I am quite confused as to how this would work.

I´m not sure I got u right, but maybe this helps:
http://en.wikipedia.org/wiki/RSA

[AuburnMathTutor]

Take the public-key scheme RSA for example.

Take two primes, p and q. Let n = pq be public. Compute K = phi(pq) = (p-1)(q-1). Choose 1 < e < K so that gcd(e, K) = 1. Then compute d = e^inv (mod K). e is the public key, and d is the private key.

Encryption is done on message M by C = M^e mod n.
Decryption is done on message C by M = C^d mod n.

Alright... So I want to send you a message M, and I know n and e and you know n, e, d (and p, q).

I can certainly encrypt... I know M, n, and e, so I can compute C.
You know C (I gave it to you), d, and n, so you can decrypt.

Your question is really this: If I know e and n, why on earth can't I get d? All I need is d to decrypt any message you can decrypt. That's all anybody needs.

Well, here's the rub. You can actually find d. It's just very hard for you to do it, and takes a very long time. One algorithm for finding d is to try every integer between 1 and n until you find one such that ed = 1 (mod n). However, if n is a decimal number with 200 digits or something, that's a lot of numbers to try.

There is no known efficient algorithm for finding d given n and e from the modular congruence ed = 1 (mod n), unless you happen to know that n = pq and you have p and q. Then it becomes fairly trivial to do; the extended Euclidean algorithm works wonders in that case because you know a lot about the factors involved.

So, in summary, you can't decrypt using the public key because you need the private key (in this example of public key encryption; others are similar) in order to "undo" the public key (decrypt the encryption). And you can certainly *find* the private key given all the public information; but it will take you a long time to do it, hopefully longer than the information needs to be kept secret. Public-key schemes are based on intractable computational problems: for which the answer is easy (trivial?) to verify, but hard (never impossible) to compute a priori.

[arkoenig]

What is to stop someone simply 'going backwards' in terms of the encryption process, for example if I encrypt something using a public key why can't I simply decrypt it using the same public key?

The simplest answer is that if it were possible to do that, what you would have would not be a public-key encryption algorithm.

For example, imagine a program named crypt, to which you give a key and a message:

encrypted_message = crypt(key, unencrypted_message);

There are certainly encryption programs in which it is possible to get the original message back by using the same key:

unencrypted_message = crypt(key, encrypted_message);

but those are not public-key encryption programs. With a public-key encryption program, you get two keys, which we can call public_key and private_key, which you can use this way:

encrypted_message = pkencrypt(public_key, unencrypted_message);
unencrypted_message = pkdecrypt(private_key, encrypted_message);

For that matter, you can also use them backward:

alternative_encrypted_message = pkencrypt(private_key, unencrypted_message);
unencrypted_message = pkdecrypt(public_key, encrypted_message);

But if you encrypt a message with a key, and then try to decrypt it again with the same key, you get garbage.

The point, then, is that you get a pair of matched keys. You keep one of them to yourself; you publish the other. If I want to send you a secret message, I encrypt it with your public key, which enables you to decrypt it with your private key. Only someone who knows your private key can decrypt it.

Similarly, if you want to send me a message, and you don't care who reads it; but you want to be able to prove you sent it, you encrypt it with your private key. Anyone who knows your public key can decrypt it, but the mere fact that it is possible to do so proves that you sent it (or someone stole your private key).

[hazar]

thanks very much for the help, it makes a lot more sense now, thanks