From: szabo@techbook.com (Nick Szabo)
Date: Tue, 20 Apr 93 23:26:42 PDT
To: cypherpunks@toad.com
Subject: FAQ: Overview of crypto
Message-ID: <m0nlYJS-000hvOC@techbook.techbook.com>
MIME-Version: 1.0
Content-Type: text/plain



The wiretap chip has generated quite a bit of new interest in
learning how to protect our electronic privacy.  We need to
bring folks up to speed quickly on practical use of crypto,
so I'm going to write up some mini-FAQs.  Experts, please send me 
succinct descriptions of PGP, anonymous remailers, the Clipper 
wiretap chip, GMS, or anything else you feel is an important basic.  
Alternatively, write up and post your own FAQ, and we'll sort it 
out later.

Here is an overview of computer-based crypto that Bill Stewart posted a
few weeks ago.

Nick Szabo					szabo@echbook.com

-----------------------------------------------------------------
You can get a proper faq by ftp from rsa.com, in the directory pub/faq.

Cryptography = writing stuff only authorized people can read.  Real crypto 
	depends on algorithms that are secure as long as the Bad Guys
	don't know the keys, even if they know everything else.
	Most of the interesting stuff depends on mathematical
	processes that take exponential amounts of time,
	so a 56-bit key would take 2**56 attempts to guess -
	you can't guess it a bit at a time in 56 steps.
	Factoring large numbers is believed to take roughly expontential time.
	M = plaintext message
	Cyphertext C = E(k, M), E = encryption function, k = key.
	Plaintext M = D(k, C)

ITAR - International Traffic In Armaments Regulations - the US has a bunch
	of laws about exporting munitions, and crypto hardware and software
	count as munitions - algorithms are OK, but our Benevolent Govt 
	KNOWS that foreigners aren't bright enough to turn algorithms into code.
	Lots of flamewars discuss exactly the boundaries, and the laws are
	contradictory about which bureaucrats are really in control,
	but nobody's wanted to get thrown in jail for arms dealing badly
	enough to force a court case ....
	Appears to apply to importing crypto also, though that hasn't been
	something anybody's made a big deal about.
	Other countries besides the US may have major restrictions as well.
Alice and Bob - the people sending messages to each other.
	Eve may be eavesdropping, and Charlie may be around also,
Secret-Key Cryptosystem, also called Symmetric-key or private-key -
	the same key k is used for E and D, or at least a closely related
	key that's easy to derive if you know the other one.
DES = Data Encryption Standard = IBM/NSA-designed secret-key system,
	very widely used, keys 56 bits long which may be a bit short,
	some people worry there may be an trapdoor put there by NSA,
	but if I told you I'd have to kill you :-)  Banks use it, for instance.
IDEA - a Swiss-written secret-key system, maybe more secure than DES,
	newer anyway.  Patented in Switz but not US, easy licensing.
Public-Key CryptoSystem - Encryption key ke and Decryption key kd are related,
	but in a way that you can't determine kd knowing only ke.
	ke is called the public key and kd the private key -
	you can publish ke where everyone can see it and encrypt stuff
	to mail to you, you can decrypt with private key kd.
	(If you want to reply, you've got to get their public key.)

	Public-key algorithms are pretty slow, so generally people
	use create a random secret key, encrypt their message with a
	secret-key algorithm like DES, and encrypt the secret key with
	the recipient's public key; recipient decrypts the secret key
	with his private key, then uses it to decrypt the message.

Digital Signatures - if you can do public-key crypto, then you can do the
	reverse as well to sign a message - you *decrypt* the message
	with your private key, and the recipient encrypts it with your
	public key - if it restores the original message, she knows it's good
	and knows that *you* sent it, because only you have your private key.
	For speed, you normally make a "hash" checksum of the message,
	and sign the hash instead of the whole thing.
	Some public-key algorithms can only be used for encryption, some only
	for signatures, some for both but you need different keys.

MD-4 and MD-5 - Message Digest hashing algorithms from (?) Rivest,
	which are thought to be unforgeable, unlike the CRC checksums
	used by many programs which are easily forged.

RSA - A public-key algorithm developed by Rivest, Shamir, and Adelman.
	It's the only well-known public-key algorithm that does everything everybody
	wants, including signatures and public-key, that's secure enough
	that you can't crack it as long as you use reasonably long keys.
	Unfortunately, it's patented in the US, by Public Key Partners,
	a company R, S, A, and friends started that owns most of the interesting
	patents related to public-key.  On the other hand, to avoid having the
	NSA classify their patent right when they applied (the NSA can do that),
	they published the algorithm before applying, which means that
	it's public-knowledge in most of the world and you can't patent it
	there, even in places that do allow algorithm patents.

	Their claims about what techniques their patents cover are *very* broad;
	if you want to do anything public-key related in the US,
	you've got to deal with them or carry a BIG lawyer, and so far
	everybody's chosen to deal with them rather than risk a long expensive
	difficult court case, or else chosen to ignore or infringe their patent 
	but not sell their products for cash, and hoped to get away with it.

RSAREF - an RSA implementation from PKP, which you may use free for personal
	non-commercial use as long as you agree to follow a set of rules
	that are much less restrictive than they used to be; you can't
	export it outside the US and Canada, and can't change the interface
	without their permission, and a few other terms.  Better implementations
	of RSA's algorithms have been done, but you can use this one free,
	with their permission.  Or you can pay them money and get support
	for incorporating their techniques into your products.

Key certification - Public Keys are usually long - RSA keys are often 1024 bytes.
	Public keys crypto is only secure if you can be SURE you have the
	public key for the person you're trying to send a message to,
	like Bob, and that Eve hasn't handed you HER public key instead -
	she could be intercepting all your mail to Bob, decrypting it,
	and re-encrypting with Bob's key.  So you need to find a secure way
	to transmit public keys, where "secure" means it can't be forged
	without you knowing about it (though anybody can read them.)
	Publishing in the New York Times classified ads is one approach,
	as is any other broadcast method you can be SURE everyone gets correctly.
	Another method is to use digital signatures - somebody you trust,
	whose public key you can be sure you know accurately, gets Bob's
	public key from Bob, and signs it with their public-key.
	Since not everybody knows somebody who knows Bob, the problem can
	be handled by a chain or hierarchy of key certifications -
	Charlie signs Bob's, Dave signs Charlie's ... and You know Xerxes yourself.
	Or George Bush signs all the general's keys, the generals all sign
	the keys for the colonels under them, the colonels sign for the
	majors under them, .... and you can check some sergeant's key
	because it's got a certificate from his lieutenant on up to Bush,
	and Bush's key is in the Phone Book.

PGP - Phil's Pretty Good Privacy program - a nice packaging of this technology
	that can be used easily to prepare secure email.  The original version
	used RSA and a choice of DES or a home-brew secret-crypto system;
	the current version uses RSA and IDEA.  For certification,
	the method is non-hierarchical - you have a "keyring" containing
	public keys you know, maybe with certificates, and you can sign
	the ones *you* trust and give your signed keyring to your friends.
	Hierarchies imply the potential for control; this is cooperative anarchy,
	and there's no chain of people you HAVE to obey to exchange keys.

	When PGP version 1 first came out, RSA yelled at Phil Zimmerman,
	the author, and told him he was risking patent infringement lawsuits
	and such if he didn't cease and desist, so he's no longer distributing it.
	But some of those SNEAKY FOREIGNERS *somehow* got a copy,
	and so ongoing development of PGP is taking place outside the US,
	unhindered by patent problems.  Version 2.1 is out, 2.2 real soon.
	Parts of PGP are probably not covered by PKP's patents,
	and parts are clearly not covered by ITAR, but some parts are a problem.

RIPEM - Mark Riordan's public-key email system, which uses RSAREF to do RSA,
	so it's legally kosher but not exportable, and is related to the
	internet Privacy Enhanced Mail stuff that was being developed
	for a while.  Still real new, but probably Pretty Good also;
	I seem to remember its key certification was more hierarchical.

----
More PGP info - PGP was originally written for a DOS environment (there are
	problems trusting any system you don't totally control,
	and it's tough to say you totally control a multi-user system),
	but it's been ported to lots of things by now, including
	UNIX and some early Mac ports (work is in progress to make the 
	Mac port feel like Mac-stuff rather than Unix-stuff.)
	You can get the source, compile it, play with it, and
	do anything you want that doesn't infringe PKP's patent,
	so remember not to use it to exchange keys with anyone or send them
	mail unless you've got a licensing agreement.....
	Once it's compiled, type 
		pgp -h
	to get help, and/or read the documentation.

Where to get things:  The fun place to shop is nic.funet.fi, by anonymous ftp,
	but if you telnet to an archie server like archie.rutgers.edu (login
	as archie) you can ask it wher to find anything.  Using a US site would
	be potentially better legally, and also cuts down on the bandwidth
	used between here and Finland....

				Bill Stewart