Page 1 of 2 12 LastLast
Results 1 to 10 of 17

Thread: How exactly does PGP work?

  1. #1

    Question 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.

  2. #2
    Master-Jedi-Pimps0r & Moderator thehorse13's Avatar
    Join Date
    Dec 2002
    Location
    Washington D.C. area
    Posts
    2,885
    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 man-given. Be grateful. Conceit is self-given. Be careful. -- John Wooden

  3. #3
    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

  4. #4
    Senior Member
    Join Date
    Aug 2001
    Posts
    485
    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.

  5. #5

    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) = (P-1)(Q-1) 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.

  6. #6

    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.

  7. #7
    Senior Member
    Join Date
    Aug 2001
    Posts
    485
    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'

  8. #8

    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.

  9. #9
    Senior Member
    Join Date
    Aug 2001
    Posts
    485
    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

  10. #10

    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
  •