
September 12th, 2003, 11:56 PM
#1
Member
How exactly does PGP work?
Ok.... I am new to the encryption stuff and i've heard about this encryption called PGP, i've heard it is one of the best encryption things out there. How does it work? What is the math behind it?

E, the modern pi.

September 13th, 2003, 12:01 AM
#2
It stands for Pretty Good Privacy.
Here is more info than you'll ever want about it.
http://www.pgpi.org/doc/faq/pgpi/en/
Our scars have the power to remind us that our past was real.  Hannibal Lecter.
Talent is God given. Be humble. Fame is mangiven. Be grateful. Conceit is selfgiven. Be careful.  John Wooden

September 13th, 2003, 12:03 AM
#3
Member
http://www.lostvault.com/vault/docs/PGPx.htm
and
http://www.labnet.com/irg/pgp1.htm
Are a good place to start  they explains how PGP came to be and what it is. It also referances a few good books that explains it in more detail.
RRP

September 13th, 2003, 06:07 AM
#4
This is a pretty good basic description on the maths behind PGP at:
http://www.momentus.com.br/PGP/doc/howpgp.html#maths
As you can see it is all to do with prime numbers, and what happens when you multiply two of them together. This was first suggested as an encryption technique in the 1970's, but at that time there were few computers powerful enough to run this.
Today, any PC can easily run PGP.

September 13th, 2003, 04:16 PM
#5
Member
Ok.....
Ok, I think I have the math down:
Encrypt: Plain text^public key % n = encrypted text
Decrypt: encrypted text ^ private key % n = plain text
but I don't get the making of the keys thing, what is the J in J(N)?
and in this: J(N) = (P1)(Q1) do they actually mean subtract one from the prime number you chose?
also after reading that I still don't understand how we pick the keys, could you actually make a set of keys? showing me the numbers and all?

E, the modern pi.

September 13th, 2003, 05:48 PM
#6
Member
also...
also, forgot to ask, is there a max on the prime number you should pick before the equation just gets to big to work with? like is a prime number of 1299827 or up there ok?

E, the modern pi.

September 14th, 2003, 08:03 AM
#7
The J(N) refers to Eulers quotient , aka the Jacobi symbol (hence the 'J').
You are getting into high level maths at this point, but yes, that does mean subtract 1 from each of the numbers p & q.
What happens is that PGP chooses the prime numbers p & q for you. When you see reference to a 1024 bit RSA algorithm it means that p & q are 1024 bits long, which is one hell of a big number  about 300+ (decimal) digits long. So 1299827 doesn't even come close !!
These are chosen by picking pseudo random 300+ odd digit numbers (p & q) and seeing if they are likely to be a prime. It uses the four Fermat tests to see if they are likely to be a prime. The odds of these tests getting it wrong are about 1 in 10^50 (that's a lot of zeros, and far, far less than your chance of winning the lottery!).
Any prime number will pass the four tests, but of course, most of the time the number chosen will not be prime, and fail one of the tests. So PGP has to try again, and again ... etc. until it finds one that passes. So you now have p, and the same process is repeated for q.
The reason for this not being guaranteed a prime number is that there are some numbers known as Carmichael numbers which can slip through (about 1 in 10^50).
There is no limit to how big these numbers are  it just depends on the power of your PC.
So to summarise it relies on the fact that you can make public the result of n, which equals p*q.
To break it you need to able to find out what p or q are, which for practical purposes is regarded as impossible  if the FBI want you they will try and seize your PC instead
The items in bold are just some things you may wish to read up on, as the maths does get very heavy at this point.
I know, as I struggled with some of it when I was at university.
EDIT: Oops: should have said you make 'e' public, not 'n'

September 14th, 2003, 06:18 PM
#8
Member
wow
Wow, ok now I don't feel stupid... i'm in 10th grade, . Ok, well since rsa encryption is close to impossible to crack, i'll just use the same prime numbers for each encryption, but I still don't understand the equation to get E & D.
Also, I hate to be even more of a pain... but how do you get J out of J(N) so you can have just N when you want to encrypt it? Since I don't know what to mod it by for the prime numbers.
Also Also, , for a 1024 bit thing wouldn't that mean 128 bytes/digits? or is this 1024 thing referring to something else(when you said 300+ digits is that right?)

E, the modern pi.

September 14th, 2003, 11:17 PM
#9
There is no specific equation to get D, but once you have chosen it then you can work out E.
Let's take a 'simple' worked example, where we have chosen P=47 & Q=59.
So N = 47*59 = 2773, and therefore J(N) = 46 * 58 = 2668.
Next we need to choose D which must be relatively prime to J(N)  seems weird I know, as these were not quite the numbers we started off with !!
So, in this example 157 will do.
We then use our PC to calculate a value for E using a variation of Euclids algorithm  you'll need to read up on this, as it is not straightforward, but the result is 17 in this case.
It can turn out that we cannot find a satisfactory value for E, in which case we try another value for D, and start over.
So now we have the numbers we require: E (17), which we make public, together with N (2773) & D(157) which we keep a closely guarded secret.
To give a simple example encrypting the number 920.
920^17 = 948 (mod 2773).
To decrypt, we use
948^157 = 920 (mod 2773)
Of course in real life, the numbers for N/E/D are far bigger, and the 1024 bits that RSA uses is a binary number (not a character string) i.e. about 10^308  in other words a 300+ decimal number as you or I would write it down.
Hope this helps

September 15th, 2003, 01:22 AM
#10
Member
thanks
actually that does help, thanks for the help, this was really confusing. Probably doesn't help i'm only in tenth grade, . But now I understand it more, thanks.

E, the modern pi.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

