View Thread > Duke182s-Spring2006 > Crypto > Good questions

First I read Why Johnny Can't encrypt, so I was a little confused about some terminology, but the first two sections of Applied Cryptography cleared most of that up.

1.  What exactly is the difference between the private key and signatures?
I know the receiver of the email has a private key to decrypt the received message, but what does signing it do?  Shouldnt the public key encrypt the message and the private key decrypt it?

2.  What type of encryption algorithms do RSA and Hellman/DSS use?

3.  i understand how the better decryption algorithms cannot be deduced from the encryption algorithm as to be similar to a puzzle piece fitting into a piece of a puzzle, but how exactly does that work on the computer / code level?

I agree that a general description of PGP would have been helpful especially defining the specific technical terms.  I would also be interested in the answers to questions 2 and 3.

1. You're right that the public key encrypts the message and the private key decrypts it, however signing is a different matter. With signatures, we need to know for a fact that there could have only been one possible person that signed this. If things were signed with public keys, we couldn't do this since public keys are, by their nature, available to anyone. Thus, a person signs with their private key and the receiver uses the public key to decrypt the signature. If a successful decryption occurs, then we know that the message originates from the owner of said public key (because only their private-key-encrypted message could have been decrypted by that public key). Think of encryption versus signing as essentially the same thing; with encryption we want only one person to be able to read it, with signing we want only one person to be able to assert it is from them.

2. RSA uses several properties of prime numbers and totients to generate a number that is very difficult (read: it takes a provably long time to brute force it) to decipher without some "helpful information." This helpful information is stored in the private key and is used to decrypt. The steps are as follows:
A. Choose 2 large prime numbers, p and q.
B. Compute n = pq.
C. Find the totient t = (p-1)(q-1).
D. Choose integer i such that 1 < i < t and there are no common factors of i and t besides 1 and -1.
E. Find x given {d: d in set of integers, d = (x(p-1)(q-1)+1)/(i).

The public key is n and i. Hash the message (for instance by character) with e = (c^i) mod (n) and c is the character value. The recipient can use the private key, consisting of p, q, dmod(p-1), dmod(q-1), (1/q)mod(p), to decrypt the message using the Chinese Remainder Theorem, which I don't really understand.

Hellman I'm not so sure about.

3. I think #2 gives you an idea about how this works at the code level. Especially if you work through an example for small values of p and q.