|
|
| Author |
Message |
srw
|
|
PGP = Pretty Good Privacy
| 
Nov 28 03:54 UTC 1994 |
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. |
kentn
|
|
response 1 of 152:
|
Nov 28 04:24 UTC 1994 |
Are PGP versions prior to 2.6 considered "illegal"?
|
srw
|
|
response 2 of 152:
|
Nov 28 05:25 UTC 1994 |
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.
|
aruba
|
|
response 3 of 152:
|
Nov 28 05:57 UTC 1994 |
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.
|
srw
|
|
response 4 of 152:
|
Nov 28 06:55 UTC 1994 |
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.
|
aruba
|
|
response 5 of 152:
|
Nov 29 01:21 UTC 1994 |
That's neat about the digital signature.
|
polygon
|
|
response 6 of 152:
|
Dec 1 02:39 UTC 1994 |
Except that someone could substitute a different message that happened
to have the same checksum.
|
aruba
|
|
response 7 of 152:
|
Dec 1 05:17 UTC 1994 |
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.
|
srw
|
|
response 8 of 152:
|
Dec 1 05:32 UTC 1994 |
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.
|
aruba
|
|
response 9 of 152:
|
Dec 1 05:45 UTC 1994 |
So, from whence can one download a copy of PGP?
|
raven
|
|
response 10 of 152:
|
Dec 1 06:16 UTC 1994 |
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.
|
srw
|
|
response 11 of 152:
|
Dec 1 06:48 UTC 1994 |
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
|
marcvh
|
|
response 12 of 152:
|
Dec 1 13:14 UTC 1994 |
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.
|
rcurl
|
|
response 13 of 152:
|
Dec 1 16:32 UTC 1994 |
Do I gather that when you fill out the form, you should be ready to
download the file immediately?
|
raven
|
|
response 14 of 152:
|
Dec 1 19:03 UTC 1994 |
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?
|
kentn
|
|
response 15 of 152:
|
Dec 1 22:29 UTC 1994 |
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.
|
srw
|
|
response 16 of 152:
|
Dec 2 01:22 UTC 1994 |
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.
|
zook
|
|
response 17 of 152:
|
Dec 5 02:47 UTC 1994 |
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?
|
srw
|
|
response 18 of 152:
|
Dec 5 06:03 UTC 1994 |
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)
|
rcurl
|
|
response 19 of 152:
|
Dec 5 07:57 UTC 1994 |
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?
|
mdw
|
|
response 20 of 152:
|
Dec 5 09:10 UTC 1994 |
Primes are often chosen using various pseudo-random generators,
driven by a seed that is most often derived from the time of day.
|
rcurl
|
|
response 21 of 152:
|
Dec 5 16:17 UTC 1994 |
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).
|
popcorn
|
|
response 22 of 152:
|
Dec 5 22:21 UTC 1994 |
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>
|
srw
|
|
response 23 of 152:
|
Dec 6 03:10 UTC 1994 |
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.
|
mdw
|
|
response 24 of 152:
|
Dec 6 05:15 UTC 1994 |
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!
|
