How exactly does PGP work?

[darkes]

To elaborate a bit more.

The important thing here is that the values we have made public are E(17) & N(2773).

Crucially what we have not made public is J(N) i.e. 2668.

This is crucial as J(N) & D are used as seeds in Euclids algorithm to generate E.
In other words we provide it with D(157) & J(N) (2668), and most of the time it will find a satisfactory value for E - in this case 17 being a valid result (there may well be others as well!).

Incidentally, this branch of maths is called 'number theory', and some of the results you can get from it, like the PGP agorithm seem nonsensical unless you have gone through the maths yourself, and followed the proof. Showing my age here, but I first saw this published in a technical paper in 1975 when I was at university, folowed the proof with difficulty, and at the time thought 'that is really cool!'

The only mathematical link between E, N, & D is provided by J(N).
And obviously to calculate this we need to know what P & Q are in the first place!

This has stood the test of time, as in the last 30 years no one has found a mathematical way to reverse this process, and brute force doesn’t work either, as the number of primes (P) you have to guess is astronomical. Even on the fastest supercomputer on the planet you are typically looking at years of computing time for RSA 1024 bit - of course you might get lucky, but that is incredibly unlikely.

[SierraHotel]

Actually, J(N) was clearly labled as Euler's Totient, aka the PHI function. phi(k) for all naturals k returns the number of naturals less than k yet relatively prime to it. Since the phi function is mulitplicate to a degree (phi(a) * phi(b) = phi(ab) iff (a,b)=1), and since we have trivially that (p,q)=1, since phi(p)=p-1, phi(q)=q-1, phi(pq)=(q-1)(p-1).

J(n) isn't jacobi's symbol, since jacobi's symbol is just a composition of legendre symbol, it needs two imputs i.e. j(n,m).

And another important point is that D is the inverse of E in cyclic group of order j(n). This basically means than in the cyclic group of order j(n), we have D*E=1.

This means that if T is your plaintext message (T^D)^E = T^DE = 1*T = T (middle step by Fermat's little theorem).

[dwcnmv]

hmm... ok... I don't know if you saw earlier but I am in 10th grade and I don't get most of what you just said... could you explain it a little simpler?(sorry)

[SierraHotel]

Sure.

Here is the process in just a few simple (though not completely satsifiying in explaination) steps.

1. You find two LARGE primes, p and q. We multiply these to get n (so n=p*q)

2. From this n, we calculate phi(n). (search "euler's totient"; "phi" on google)

3. We find two numbers, E and D, such that E * D divided by phi(n) leaves a remainder of 1.

4. Say T is our message in number form. to decrypt it, we take T to the Eth power. So the encrypted message is T^E.

5. To decrypt our now encrypted message, T^E, we take the whole thing to the Dth power. So we get T^E^D = T^E*D.

Now here's the tricky part. It's impossible to explain this w/o lots of number theory terminology, but trust me when I say that because of the way we made E and D, when we divivde T^E*D by n, we get a remainder of T. Thus, we have our original plaintext message back.

I know this explaination is a bit unsatsfying, but no one can give a significatly better explaination without going to the roots of a lot of the concepts in number theory. If you really want to start to understand number theory, I suggest you pick up "Introduction to the Theroy of Numbers" by Hardy and Wright. Btw, i'm in 11th grade.

[dwcnmv]

Ok.... do you think that you could give me an example? Here are two prime numbers (obviously not anywhere large enough for a real 1024 bit encryption): 1299827 & 1144301. Can you please go through the steps for creating N and Creating E & D? I already have the equation for encrypting and decrypting (encrypting C=T^E % N, decrypting T=C^D % N) but can you please go through the getting of N,E, & D with those two numbers? (1299827 & 1144301). Please include all steps.

[SierraHotel]

1. We get n = 1299827*1144301 = 1487393335927 .

2. The euler totient of this number phi(1487393335927) = 1487390891800. To find out how this number is calculated, search "euler's totient" or "phi euler" in google).

3. We pick an encrytion key. In this case, we will pick 2003 as our encryption number. This number MUST be relatively prime to 1487390891800, which 2003 is. Then we find its inverse by using Euclid's Algorithm (search on google). This number happens to be 1440608252667. This number will be the decrytion key.

So E=2003. We selected THIS number by finding a number relatvively prime to 1487390891800.
And D= 1440608252667, which is calculated with Euclid's algorithm from 2003 and 1487390891800.

4. Say we have a plaintest message and we want to encrypt it. Let the message be 31337.
To encrypt it, we take 31337 ^ 2003 % 1487393335927 = 1331504076685.

1331504076685 is the ENCRYPTED message.

5. To decrypt it, we take 1331504076685^D % N = 1331504076685^1440608252667 % 1487393335927= 31337. And we're done.

[darkes]

Just to add to this, in the case of PGP where n=p*q, and p & q are prime, then Eulers totient is always (p-1)*(q-1) i.e. (1299827-1)*(1144301-1) = 1487390891800.

It doesn't matter from a mathematical point of view whether we choose d & calculate e, or vice versa (i.e. choose e & calculate d). We use Euclids algorithm in either case.

What does matter is that we cannot reverse the process that Euclids algorithm uses i.e. given e & n, what we need to help us calculate d is j(N) i.e. (p-1)*(q-1), which is not remotely obvious if n is large enough.

Which is why the fundamental maths behind PGP relies on keeping p & q secret.

Of course, when you get down to the implementation of PGP on a PC, there are all sorts of practical problems. For example, normally p & q are stored as encrypted numbers on your PC (using a different type of encryption). Also, you cannot be absolutely sure that p & q are prime in the first case, in which case it is trivial to break.

Which is why it is called Pretty Good Privacy - in other words it is not foolproof, even from a mathematical point of view, but if used correctly, then it is about 99.9999 ... etc. % reliable.