PGP = Pretty Good Privacy. 

This is the name of a program written originally by 
Philip R. Zimmerman and which implements the RSA public-key cryptography 
technology.  It was done as a political statement. Zimmerman wanted to get the 
technology into the hands of ordinary people, because it offers a way to secure
communications from the prying eyes of your enemies, your boss, the
government, anybody you want to secure it from.

The fact of the matter regarding email is that it really isn't very secure.
If you are planning something illegal, you would be just plain stupid
to use email to describe this, because you really don't know who can read
your email. But the purpose of PGP isn't to protect crooks from the law,
but rather to protect everyone from anyone.

Similarly, email can easily be "spoofed". By that I mean that email can
be written to appear to be from user abc without that user's knowledge, 
so email cannot be used for financial transactions.

RSA's technology is positioned to change all that. They own patents on 
some of it, and MIT owns other patents, so when PGP first appeared, there 
ensued a long drawn-out battle over the legality of it, its use, etc. Many
(including me) were afraid to use it because we were afraid of the 
possibility of being held liable for damages to RSA for use of
patent-infringing technology. That's the bad news.

The good news is that several months ago MIT and RSA came to an agreement
which terminates their disagreements over who owes whom how much,
and legalizes access to a modified version of PGP (version 2.6).
Users must assure that they have read the licenses, will not export the
software, and will use it only for personal use (not for commercial use).
Distribution of PGP is being done by MIT over the internet.

PGP is available for Macs, PCs, Workstations, etc. PGP should only be run
on a machine which one has physical security over. In other words, it
should not be run on a timesharing system such as Grex. Grex is a 
wonderful platform for sharing information about PGP, though, and
that is what I am trying to do here.

I have downloaded my copy of MacPGP, and created my key pair. It is a 
characteristic of Public key systems like this that keys come in pairs.
I have a public key and a private key. The Private Key is my secret.
My public key needs to be published in a place where people can 
obtain it, and most importantly trust it. They must trust that they have 
my correct public key. If they do, they can send messages that only I
can read, and they can verify that messages I send are sent by me
and not spoofed by someone else. This is a powerful thing.

My public key is in my .plan file, and looks exactly like this

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6

mQCPAy7XYBwAAAEEAMDAfTE8rLsOefdFqKZhSSdVFxmKFyGfHRtv56bc1LD+DwqD
QXHUoUWiL3OVN6aW7Yz6x2AvXlAHYeYPgpJ0MPUvSQuHxTkQrtBnT6nIKnJxPGRj
2NQzrdtLJm7gRql8IW2VsPEKAKs0B9X+0YLORLOm8ltGj+XrEBBS3bjyRrs1ABEB
AAG0JFN0ZXZlbiBSLiBXZWlzcyA8c3J3QGN5YmVyc3BhY2Uub3JnPg==
=mIza
-----END PGP PUBLIC KEY BLOCK-----

Fortunately, users of PGP do not need to memorize public keys like the above.
Rather, once they are placed in a file PGP calls a keyring, it can be
called up painlessly by my name, within PGP. Very cool.
I think that both PGP and the privacy that the RSA algorithm affords are both
a lot better than the name "Pretty Good" implies.

There are many topics worthy of discussion with respect to this, including
the following ones which I can actually think of at the moment:

(1) How to get your own legal copy of PGP
(2) What are the advantages and disadvantages of a public key cryptosystem?
(3) Why is this such a political issue?
(4) How does the RSA algorithm work - trapdoors in general.
(5) Uses for digital signatures.

Each of these probably deserves an item of its own, but I have written
enough for now. Based on the level of interest I saw in the announcements
item in Agora when I anticipated creating this item, I think it would be a 
good idea to link this item and any related ones from Jellyware to Agora.
We'll see if the interest level wararants having multiple items.
If it does, I'm sure someone will enter them, if not me.

152 responses total.

Are PGP versions prior to 2.6 considered "illegal"?

I think versions 2.3 and earlier are considered by RSA to infringe on
their patents. I cannot say what they plan to do about it.
I think 2.4 and 2.5 were kind of short-lived or beta releases.
I am giving my best guess here - I am not absolutely certain about the
release numbers.

   Here's how I understand the advantage of public key encription:  With a
standard code, if I want to send you a message, you have to tell me how
the code works.  Then if someone squeezes me, *they* can find out how the
code works, and then they can read all encoded messages to *you*.  So
naturally you'd have to be careful about who you gave to description of
the code to. 
   Public key encription systems combat this problem by separating the
coding process into encription and decription, and the neat thing is, you
can tell me how to *en*cript a message without telling me how to *de*cript
it.  That way you can give as many people as you want the ability to send
you messages without compromising the code (i.e. without increasing the
risk that someone might be able to read your mail).  In fact, why not
just publish the number (key) that allows people to send you messages in a
sort of phone book, along with everyone else's keys.  Then anybody at all
can send you a message, but only you can decode it.  I think that's a
pretty neat idea.
   The public key encription systems I'm familiar with depend on the fact
that it's very hard to factor the product of two large primes.  (The
public key is such a product, and the information that allows you to
decode a message is the factorization.)  It's worth noting that
mathematicians are getting better and better at factoring large numbers,
so keys may have to get larger as time goes by. 

That's a pretty accurate description, Mark. The RSA trapdoor algorithm
is in fact based upon the difficulty of factoring a number which is a 
product of two extremely large primes into its component primes.

The Public key is based on the product of the two primes. The secret
key contains the two primes. Data encrypted with either key is 
decrypted only with the other one. The size of the keys is adjustable,
but the highest setting is 1024 bits, which is around 300 digits decimal.

The system can be used in two ways, which are the converse of each other.
(1) you can encrypt a message with Mr X's public key.
   This ensures that only Mr. X can read your message, because only Mr. X
   has the private key to decrypt it.

(2) you can encrypt a message with your own private key. This is normally
   done to a small checksum calculated from a message and appended to it.
   This small appendix to a message is called a "digital signature".
   Anyone can decrypt it, because everyone knows your public key.
   It verifies that the received message is identical to the one that you sent.
   No one else could have sent it,  because no one else could have encrypted
   it so that your public key would restore it, and the message could not
   have been tampered with because the signature contains a checksum of it.A
   Thus it is an unforgeable sign of authenticity. strong stuff!

You can do both, if you need to. You can add a digital signature and also
encrypt it. Thus only Mr X can see what you sent, and he knows that
only you could have sent it.

A fundamental breakthrough in the solution to the mathematical problem
of factoring would indeed yank the rug from under the RSA technology, and
in particular PGP. I'm not worried. 

The best problem is that of ensuring you have a valid public key for 
someone. This is probably the biggest weakness of this system.
You must be able to trust that you have the right public key.
This issue is discussed at length in the PGP documentation.

That's neat about the digital signature.

Except that someone could substitute a different message that happened
to have the same checksum.

Hopefully the checksum is actually a hash that's obscure enough so as to
make creating a message witha particular hash difficult.  Though not
impossible, of course.

I think this is harder than it looks, but I am not certain of the hashing
algorithm used here. I am basing my suspicions mainly on the fact the
the security experts don't seem to be worried about this prospect.

So, from whence can one download a copy of PGP?

        I think they have PGP at soda.berkeley.edu (last time I checked).
It's a big file (like close to a meg) so you probably don't want to download
ithere at 2400 baud.
        This is a great item by the way which I'm linking to the cyberpunk
conf.  Now for the plug join cyber for more discussions about internet
privacy, copyright issues, internet zines etc.

I am not aware of PGP 2.6 being available anywhere except at MIT.
There is no fixed named site for it. They rename the site twice an hour.
This is because they want to force anyone who downloads it to first
fill out a form that agrees to certain constraints.

Here is the URL for the MIT site:
   Linkname:  PGP Distribution Authorization Form
        URL:  http://bs.mit.edu:8001/pgp-form.html

If you are a Grex Member, type
lynx http://bs.mit.edu:8001/pgp-form.html
but you will not want to do this when the link is busy.

Grex users with other access to the internet (not through Grex)
will probably have an easier time of it. I used a commercial service
to get it, myself.

There is a PGP FAQ at http://www.mit.edu:8001/people/warlord/pgp-faq.html

Phil actually originally was hoping to make money with PGP, the
political part came in later, as I understand it.

The salient patents are actually "owned" (in the sense of having
exclusive sublicensing rights) by a firm called Public Key Partners.
The most salient one, on RSA, expires in 2000.

Re #2:  2.4, if memory serves, was the ViaCrypt commercial release of
PGP.  It was the first version that was legal in the U.S., and is
still the only version which is legal for commercial use.  Note that
"commercial use" is defined differently by differnet entities, but for
the IDEA cipher it's defined rather broadly.

Re #5-7:  PGP uses the MD5 hash, which is cryptographically secure.
This means there is no way (yet known) significantly cheaper than
brute force over a 128 bit space to find another message which
produces the same hash.

There are a lot of curious and funky things about PGP and related mail
developments.  What's probably most unfortunate is that Phil didn't
get along with the rest of the community of cryptographic mail
security developers very well, which is why PGP totally ignored
existing and developing standards for cryptographic mail (at first,
though over time it took some of their ideas) and so is not compatible
with anything but itself.  Pity.

Do I gather that when you fill out the form, you should be ready to
download the file immediately?

        I guess the Berkeley address is for 2.3.  I guess I should update.
Does anyone know if 2.6 is more or less secure than 2.3?

Not sure.  There was some argument over 2.6's backward compatibility with
2.3 PGP files, and some belly-aching over 2.6's limited key lengths
compared to 2.3.  Don't know how it was all resolved.

PGP 2.3 is illegal, and that's why I waited for 2.6 before getting interested.
I really don't know how agressively RSA (or PKP) is going after users
of 2.3, but it seems that if you have anything to lose, you're exposed
by using 2.3. I am particularly sensitive to this as a software developer
myself, although I detest software patents. For now they are the law.

PGP 2.6 allows 1024 bit keys. I think that is beyond what's needed. (IMO)
I consider 2.6 to be fully secure. 2.6 will decode 2.3's messages,
but I believe 2.3 will not decode 2.6's messages. This was done on
purpose to force 2.3 users to upgrade. 

In answer to your question #13, Rane: yes. If you are going to go to the
trouble to fill out the form, then you should be prepared to download
immediately.

This stuff sounds very neat.  I would think lots of people would want
to buy it.  I'm thinking of banks, hospitals, stock brokers, etc.

Do I understand correctly that everyone gets their own particular pair
of very large prime numbers - isn't there a chance of someone picking out
the same pair as yourself?

Excellent question. The answer is yes. But lets look more closely at it.
The key is a 1024 bit number that is the product of two smaller primes.
For the sake of argument let's say they are both 512 bit primes.
these are numbers in the vicinity of 10^154.

Even though primes aren't very dense, lets see if we can guess approximately
how many 512 bit primes there are. There are going to be a lot of
primes between 2^511 and 2^512. The average density of primes in the region
of the number n is given by 1/ln(n). So I think our number is approximated by:

   2^511/ln(3*2^510)
            ^^^^^^^midpoint of the range - hey it's only an approximation.

Don't try to evaluate these numbers on your calulcator. Lets take the
log base 2 of numerator and denominator:

logbase2 of the numerator is 511
denominator is ln(3) + ln(2)*510  = 354.6
logbase2 of the denominator is 8.47

So the difference is the log base 2 of the fraction. The fraction itself,
the number of primes in the range,  is 2^(511-8.47) = 10^151.3

Now pick any two of them to form a key. There are 10^302 such pairs.

Ok, so what are the chances that any two people will get the same key?
How many particles are there in the universe?

(admittedly a back-of-the-envelope analysis)

You have to choose the two primes completely at random, to get those
odds. It would be impractical to do that - how is it done?

Primes are often chosen using various pseudo-random generators,
driven by a seed that is most often derived from the time of day.

Do they just generate a couple of pseudo-random 512 digit numbers
(or whatever), and then fiddle with them to make them prime? It would
be laborious to generate pseudo random prime numbers directly (if it
is possible, at that size).

Thanks for entering this item!  Up until I read it, I'd been trying to make
sense out of how PGP let person A encrypt a message and send it to person B
so that only person B could decrypt it, but nobody else in the middle could.
It's explained by the fact that person B has a private key.  <a little
lightbulb appears over valerie's head>

Regarding key generation:

Having been through the key generating process in PGP, I know that it uses
two pieces of info. (1) You enter a "pass phrase", (2) you type
random keys and it measures the intervals between keystrokes to produce a 
random bitstream.

I am not privy to how it then uses this information, but I am a pretty
good guesser (PGG (tm)) . I would guess it forms a hash based on the
pass phrase and attaches the random bits to that. This result is then
probably split in two to form 2 seeds from which to begin a search for 
large prime numbers. This can take quite a while, I'm told. It spent about
a minute on my Powermac.

On Public and Private keys:

Once the primes are decided upon, the public and private keys are produced.
The actual encrypting and decrypting algorithm is not a secret. it is in fact
revealed in a patent, I believe. I used to remember more about it.
Without doing research I can say (semi-vaguely) that the process consists
of a bunch of very-extended-precision polynomial and modulus calculations
that involve the text and the key. The encryption and decryption algorithms
are different, I believe, but closely related.

So if j is the public key and k is the complementary private key, 
and E and D are the Encryption and Decryption functions, 
we usually write it this way:

(please imagine the j's and k's to be subscripts)

Ej(x) is the ciphertext encryption of the plaintext x with public key j
Dk(y) is the plaintext decryption of the ciphertext y with private key k

The math works out (and this is easy to show if you remember the math,
sorry, I don't) that Dk(Ej(x)) = x, which means that one can recover
x from Ej(x) only if one knows the complementary private key k.

It is also true that Dj(Ek(x)) = x, which gives this system the 
signature feature. Ek(x) can be deciphered by anyone, since j is a
public key and presumably widely known. But everyone who deciphers
it can know with a certainty that the person who created it must
have known the private key j.

If you add to that last bit a very secure hash function, you can 
sign a document or file this way, and the rest of the world can 
be sure that only the holder of your private key could have done so.
Thus this offers the digital replacement for the familiar signature.

By doubly encypting with ones private key and the recipients public key,
one can send a secure message which is authenticated upon arrival.

None of this would be worth talking about if someone could determine
a private key by extensive mathematical cracking based on the known
public key. But this problem has been shown to be mathematically
equivalent to factoring a 300 (or so) digit number into its two
prime factors. If anyone ever does crack this problem, computer
scientists will cry, but mathematicians will rejoice.

I am squarely in the computer scientists' camp on this one.

I hadn't looked at the PGP code before, but I just did, so:

The pass phrase is used to encrypt the keys file - a weak form of
security.  I *think* the pass phrase is not used to generate the primes,
but could be wrong.  The "random keys" are definitely used for making
the initial random number seed; the variation in timing between the key
strokes is the major source of randomness in the system.  Even that
could be considered a bit suspect - even on a local system, serial
multiplexors are less random than one might wish.  Over a network, or
onto a heavily loaded system, it could be very non-random -- PGP
attempts to measure the degree of non-randomness -- and will echo '?'s
if it thinks isn't random enough.  It may be possible for the user to
increase the "randomness" by typing slowly, and turning off any
background music or other source of rhythmic sound while typing in the
"random" text.

Both primes are generated independently but use the same random number
generator in succession.  So both are using "all" the bits of the
initial random seed, but since the generator isn't re-initialized, the
result is not "more" truely random than the number of bits that made the
initial seed.  The primes are in fact generated by making large random
numbers, then testing to see if they are "probably" random.  That means
there's a *small* chance they aren't random -- the odds are supposedly
something like 10^-44 which is probably considerably less likely than
the chances of the computer silently malfunctioning - good enough for
most purposes!

I think that you mean there's a small chance they're not prime, rather
than there's a small chance they aren't random.

There must be times when there's a need to verify the authenticity of a
document but not scramble it. Does anyone knows how an electronic 
signature works?

Yes Marcus meant a small chance that they're not prime.
There is that microscopic chance. The test for primeness is not a perfect
test, because such a test would take too long. It's a pseudoprime test,
but apparently a pretty darn good one.

In answer to 26, PGP can either encrypt, add a signature or both.
They're independent.

As I said in #23, encrypting and making a signature
are almost the same thing. The difference is that when you encrypt, you
use the recipient's public key to do so, so only he or she can decrypt it
(as it requires the private key to undo what the public key did).
When you sign, you encrypt a bit of plain text with your own private key.
Thus anyone who knows your public key can decrypt it, but that's everyone.
However they all know for certain that only your private key could have
produced such a cipher.  The plaintext you encrypt to form the signature
is a very secure hash of whatever document you are "signing".

I sent my key to the public key server at MIT. There are a bunch of these
around the world, and they coordinate their databases of public keys.
Thus you should now (or soon) be able to find my public key on any 
public key server.

The authenticity and trustworthiness of a public key is a critical part
of the PGP system. This is a fascinating area, too. More later.

That property of RSA (that E_k(D_k(m)) = D_k(E_k(m)) = m for all m)
is somewhat unusual and what distinguishes it from most other public-key
approaches.

Another important property is that "authentication" is informally used
to actually mean two different things:

- Originator authenticity.  This means you know, for instance, who a
  mail message came from.  You're sure it came from Alice.
- Non-repudiation of origin.  This means you can prove to an impartial
  third party, like a judge or arbitrator, that the message came from
  Alice and nobody else, not even you, could have created it.

If you use a conventional secret-key system where you and Alice share a
secret key, you don't get the latter, because you could have written
a message and encrypted it with the key too.  You can prove to yourself
Alice wrote it, but you can't prove it to anybody else.  Obviously this
is not satisfactory for, say, business transactions.

If somebody's account were cracked, could their private key be gotten?

This response has been erased.

Not if you run it on your home machine (if you're doing terminal emulation).
It's smarter to encrypt the messge at home and past it into the mailer
than keep PGP in your account IMO.

The answer is no. They could not.

PGP recommends strongly that you run it on a machine that you have physical
security over, such as your home machine. The specifically advise that is
a bad idea to run it on a time-sharing system (like Grex).
This is not because your account on Grex might somehow get broken into.
Yes, it might, but that will not compromise your keys.
The real reason for this is that you don't want the unencrypted copy to 
be traveling over any unsecured network, and the phone line is unsecured.

If someone were to break into your house and take your copy of PGP and
your secret key ring, they could not use it unless they knew the 
pass phrase that you created your key with.

However, it's more likely somebody would break into your house and replace
your copy of PGP with one that seemed to work but actually had a hole
that made it easy for him to crack, or any of several approaches.  People
are still always the weak link in security.

Umm. I don't think they could do that without it affecting my
PGP conversations. I.e. my correspondents would notice something
different about my messages (like they wouldn't unscramble).
You are right about people being the weak link, but as long as we 
send unencrypted data on the net, we have no security and no authentication.
PGP changes that drastically. Public Key crypotsystems in general are
(IMO) revolutionary and will become a standard for conducting business
on the net in the fullness of time.

More on the key servers.
There are about a dozen located around the world, and they
sync up their databases regularly, so if you send your public key
to any one of them it will appear on all of them.
pgp-public-keys@pgp.mit.edu is the one I used.
This is an email server. To add your key you put ADD in the subject
and your public key block (asciified) in the body, and send it.

My Public key is now registered on the Keyserver and it has been signed by 
my son, Jonathon, as authentic. Thus anyone who trusts my son at MIT
will be able to use my public key (should they desire) and won't have
to verify its authenticity first. The Keyservers rely on this concept
of a "Web of trust" for verifying the authenticity of public keys,
because the servers themselves make no attempt to verify the keys they 
hold.

Thus if you see a PGP key on the server with the ID
Bill Clinton <president@whitehouse.gov>
You really have no idea if that is who you think it is unless his key
has been "signed" as authentic by someone whose key you trust.
(I don't expect he's using PGP, but that wasn't the point.)

If anyone on Grex wants me to sign their public key, they should send me email.

Are you using PGP routinely for anything, Steve? It is a very interesting
technology, but I haven't been able to identify a practical use for
it in my activities. Certainly no instance has arisen where it would
have a scintilla of use. (I am not, currently, doing any proprietary
consulting over the internet, but I doubt I'd worry even if I were. It
is more likely the client would be paranoid!)

There are plenty of ways PGP could be altered that would make
life easier for the bad guy, while still preserving compatibility.

What Marcus said.  One approach would be to change the session key such
that it is not generated randomly.  Another would be to change the program
to record your passphrase when typed, though this requires a second breakin
to get it.  Or countless other ways.  The truly paranoid carry their
copies of PGP around on floppy, and have another floppy with a secure
checksum of the executable along with the checksum algorithm itself, and
inspect their computer for hardware modifications, and quite generally 
clearly have no life interesting enough for anybody to want to snoop on. :-)

OK, I'll cede the point in #37 and #38. I am not that paranoid.
Re #36. Not yet.

I sent a message to my son, because at the moment he is the only one
I really know well enough to send email to and who uses PGP. He's in
a similar situation to me, except that PGP is becoming more common
around MIT, so he knows more PGP users than I do.

My main motivation for doing this is that I knew in principle that I wanted
the ability to communicate privately over the public network. I also knew
that when the moment finally arrived that I wanted to do this I would
be out of luck unless I had greased the wheels already.

I see what I have done so far as just preparedness.

Sometimes I help my kids out with their tax returns. We'd all feel a lot
more comfortable encrypting them. Now, that's possible.  
I expect that uses will become evident only after the technology has
been enabled. So I enabled it and now I'm waiting.

- Backtalk version 1.3.30 - Copyright 1996-2006, Jan Wolter and Steve Weiss