Glossary of Crypto Terms

From: tcmay@netcom.com (Timothy C. May)

Subject: Crypto Glossary

Date: Sun, 22 Nov 92 11:50:55 PST



Here's the glossary of crypto terms we passed out in printed form at

the first Cypherpunks meeting in September 1992. Some compromises had

to be made in going from the printed form to the ASCII of this

transmission, so I hope you'll bear with me.



I'm sending it to the entire list because nearly everyone who hears

about it says "Is it online?" and wants a copy. If you don't want it,

discard it.



I'm not going to be maintaining the "Cypherpunks FAQ," so don't send

me corrections or additions.



Enjoy!



--Tim May



CRYPTO GLOSSARY



Compiled by Tim May (tcmay@netcom.com) and Eric Hughes

(hughes@soda.berkeley.edu), circa September 1992.



Major Branches of Cryptology (as we see it)



-       (these sections will introduce the terms in context,

though complete definitions will not be given)



*** Encryption

-       privacy of messages

-       using ciphers and codes to protect the secrecy of

messages

-       DES is the most common symmetric cipher (same key for

encryption and decryption)

-       RSA is the most common asymmetric cipher (different

keys for encryption and decryption)



*** Signatures and Authentication

-       proving who you are

-       proving you signed a document (and not someone else)



*** Untraceable Mail

-       untraceable sending and receiving of mail and messages

-       focus: defeating eavesdroppers and traffic analysis

-       DC protocol (dining cryptographers)



*** Cryptographic Voting

-       focus: ballot box anonymity

-       credentials for voting

-       issues of double voting, security, robustness, efficiency



*** Digital Cash

-       focus: privacy in transactions, purchases

-       unlinkable credentials

-       blinded notes

-       "digital coins" may not be possible



*** Crypto Anarchy

-       using the above to evade government, to bypass tax collection,

etc.

-       a technological solution to the problem of too much

government



***     G L O S S A R Y    ***



***     agoric systems -- open, free market systems in which

voluntary transactions are central.



***     Alice and Bob -- cryptographic protocols are often made

clearer by considering parties A and B, or Alice and Bob,

performing some protocol. Eve the eavesdropper, Paul the

prover, and Vic the verifier are other common stand-in names.



***     ANDOS -- all or nothing disclosure of secrets.



***     anonymous credential -- a credential which asserts

some right or privilege or fact without revealing the identity

of the holder.  This is unlike CA driver's licenses.



***     asymmetric cipher -- same as public key

cryptosystem.



***     authentication -- the process of verifying an identity

or credential, to ensure you are who you said you were.



***     biometric security -- a type of authentication using

fingerprints, retinal scans, palm prints, or other

physical/biological signatures of an individual.



***     bit commitment -- e.g., tossing a coin and then

committing to the value without being able to change the

outcome. The blob is a cryptographic primitive for this.



***     blinding, blinded signatures -- A signature that the

signer does not remember having made.  A blind signature is

always a cooperative protocol and the receiver of the

signature provides the signer with the blinding information.



***     blob -- the crypto equivalent of a locked box. A

cryptographic primitive for bit commitment, with the

properties that a blobs can represent a 0 or a 1, that others

cannot tell be looking whether itUs a 0 or a 1, that the creator

of the blob can "open" the blob to reveal the contents, and that

no blob can be both a 1 and a 0. An example of this is a flipped

coin covered by a hand.



***     channel -- the path over which messages are

transmitted. Channels may be secure or insecure, and may

have eavesdroppers (or enemies, or disrupters, etc.) who alter

messages, insert and delete messages, etc. Cryptography is

the means by which communications over insecure channels

are protected.



***     chosen plaintext attack -- an attack where the

cryptanalyst gets to choose the plaintext to be enciphered,

e.g., when possession of an enciphering machine or algorithm

is in the possession of the cryptanalyst.



***     cipher -- a secret form of writing, using substitution or

transposition of characters or symbols.



***     ciphertext -- the plaintext after it has been encrypted.



***     code -- a restricted cryptosystem where words or

letters of a message are replaced by other words chosen from

a codebook. Not part of modern cryptology, but still useful.



***     coin flipping -- an important crypto primitive, or

protocol, in which the equivalent of flipping a fair coin is

possible. Implemented with blobs.



***     collusion -- wherein several participants cooperate to

deduce the identity of a sender or receiver, or to break a

cipher. Most cryptosystems are sensitive to some forms of

collusion. Much of the work on implementing DC Nets, for

example, involves ensuring that colluders cannot isolate

message senders and thereby trace origins and destinations

of mail.



***     computationally secure -- where a cipher cannot be

broken with available computer resources, but in theory can

be broken with enough computer resources. Contrast with

unconditionally  secure.



***     countermeasure -- something you do to thwart an

attacker.



***     credential -- facts or assertions about some entity. For

example, credit ratings, passports, reputations, tax status,

insurance records, etc.  Under the current system, these

credentials are increasingly being cross-linked. Blind

signatures may be used to create anonymous credentials.



***     credential clearinghouse  -- banks, credit agencies,

insurance companies, police departments, etc., that correlate

records and decide the status of records.



***     cryptanalysis -- methods for attacking and breaking

ciphers and related cryptographic systems. Ciphers may be

broken, traffic may be analyzed, and passwords may be

cracked. Computers are of course essential.



***     crypto anarchy -- the economic and political system

after the deployment of encryption, untraceable e-mail,

digital pseudonyms, cryptographic voting, and digital cash. A

pun on "crypto," meaning "hidden," and as when Gore Vidal

called William F. Buckley a "crypto fascist."



***     cryptography -- another name for cryptology.



***     cryptology -- the science and study of writing, sending,

receiving, and deciphering secret messages. Includes

authentication, digital signatures, the hiding of messages

(steganography), cryptanalysis, and several other fields.



***     cyberspace  -- the electronic domain, the Nets, and

computer-generated spaces. Some say it is the "consensual

reality" described in "Neuromancer." Others say it is the phone

system. Others have work to do.



***     DC protocol, or DC-Net -- the dining cryptographers

protocol. DC-Nets use multiple participants communicating

with the DC protocol.



***     DES -- the Data Encryption Standard, proposed in

1977 by the National Bureau of Standards (now NIST), with

assistance from the National Security Agency. Based on the

"Lucifer" cipher developed by Horst Feistel at IBM, DES is a

secret key cryptosystem that cycles 64-bit blocks of data

through multiple permutations with a 56-bit key controlling

the routing. "Diffusion" and "confusion" are combined to form

a cipher that has not yet been cryptanalyzed (see "DES,

Security of"). DES is in use for interbank transfers, as a

cipher inside of several RSA-based systems, and is available

for PCs.



***     DES, Security of  -- many have speculated that the NSA

placed a trapdoor (or back door) in DES to allow it to read

DES-encrypted messages. This has not been proved. It is

known that the original Lucifer algorithm used a 128-bit key

and that this key length was shortened to 64 bits (56 bits

plus 8 parity bits), thus making exhaustive search much

easier (so far as is known, brute-force search has not been

done, though it should be feasible today). Shamir and Bihan

have used a technique called "differential cryptanalysis" to

reduce the exhaustive search needed for chosen plaintext

attacks (but with no import for ordinary DES).



***     differential cryptanalysis -- the Shamir-Biham

technique for cryptanalyzing DES. With a chosen plaintext

attack, they've reduced the number of DES keys that must be

tried from about 2^56 to about 2^47 or less. Note, however,

that rarely can an attacker mount a chosen plaintext attack

on DES systems.



***     digital cash, digital money -- Protocols for

transferring value, monetary or otherwise, electronically.

Digital cash usually refers to systems that are anonymous.

Digital money systems can be used to implement any quantity

that is conserved, such as points, mass, dollars, etc.  There

are many variations of  digital money systems, ranging from

VISA numbers to blinded signed digital coins.  A topic too

large for a single glossary entry.



***     digital pseudonym -- basically, a "crypto identity." A

way for individuals to set up accounts with various

organizations without revealing more information than they

wish. Users may have several digital pseudonyms, some used

only once, some used over the course of many years. Ideally,

the pseudonyms can be linked only at the will of the holder. In

the simplest form, a public key can serve as a digital

pseudonym and need not be linked to a physical identity.



***     digital signature --  Analogous to a written signature

on a document. A modification to a message that only the

signer can make but that everyone can recognize.  Can  be used

legally to contract at a distance.



***     digital timestamping -- one function of a digital

notary public, in which some message (a song, screenplay, lab

notebook, contract, etc.) is stamped with a time that cannot

(easily) be forged.



***     dining cryptographers protocol (aka DC protocol,

DC nets) -- the untraceable message sending system

invented by David Chaum. Named after the "dining

philosophers" problem in computer science, participants form

circuits and pass messages in such a way that the origin

cannot be deduced, barring collusion. At the simplest level,

two participants share a key between them. One of them

sends some actual message by bitwise exclusive-ORing the

message with the key, while the other one just sends the key

itself. The actual message from this pair of participants is

obtained by XORing the two outputs. However, since nobody

but the pair knows the original key, the actual message

cannot be traced to either one of the participants.



***     discrete logarithm problem -- given integers a, n,

and x, find some integer m such that a^m mod n = x, if m

exists. Modular exponentiation, the a^m mod n part, is

straightforward (and special purpose chips are available), but

the inverse problem is believed to be very hard, in general.

Thus it is conjectured that modular exponentiation is a one-

way function.



***     DSS, Digital Signature Standard -- the latest NIST

(National Institute of Standards and Technology, successor to

NBS) standard for digital signatures. Based on the El Gamal

cipher, some consider it weak and poor substitute for RSA-

based signature schemes.



***     eavesdropping, or passive wiretapping --

intercepting messages without detection. Radio waves may be

intercepted, phone lines may be tapped, and computers may

have RF emissions detected. Even fiber optic lines can be

tapped.



***     factoring -- Some large numbers are difficult to factor.

It is conjectured that there are no feasible--i.e."easy," less

than exponential in size of number-- factoring methods. It is

also an open problem whether RSA may be broken more easily

than by factoring the modulus (e.g., the public key might

reveal information which simplifies the problem).

Interestingly, though factoring is believed to be "hard", it is

not known to be in the class of NP-hard problems. Professor

Janek invented a factoring device, but he is believed to be

fictional.



***     information-theoretic security -- "unbreakable"

security, in which no amount of cryptanalysis can break a

cipher or system. One time pads are an example (providing the

pads are not lost nor stolen nor used more than once, of

course). Same as unconditionally secure.



***     key -- a piece of information needed to encipher or

decipher a message. Keys may be stolen, bought, lost, etc.,

just as with physical keys.



***     key exchange, or key distribution -- the process of

sharing a key with some other party, in the case of symmetric

ciphers, or of distributing a  public key in an asymmetric

cipher. A major issue is that the keys be exchanged reliably

and without compromise. Diffie and Hellman devised one such

scheme, based on the discrete logarithm problem.



***     known-plaintext attack -- a cryptanalysis of a cipher

where plaintext-ciphertext pairs are known. This attack

searches for an unknown key. Contrast with the chosen

plaintext attack, where the cryptanalyst can also choose the

plaintext to be enciphered.



***     mail, untraceable  -- a system for sending and

receiving mail without traceability or observability.

Receiving mail anonymously can be done with broadcast of the

mail in encrypted form.  Only the intended recipient (whose

identity, or true name, may be unknown to the sender) may

able to decipher the message. Sending mail anonymously

apparently requires mixes or use of the dining cryptographers

(DC) protocol.



***     minimum disclosure proofs  -- another name for zero

knowledge proofs, favored by Chaum.



***     mixes -- David Chaum's term for a box which performs

the function of mixing, or decorrelating, incoming and

outgoing electronic mail messages. The box also strips off

the outer envelope (i.e., decrypts with its private key) and

remails the message to the address on the inner envelope.

Tamper-resistant modules may be used to prevent cheating

and forced disclosure of the mapping between incoming and

outgoing mail. A sequence of many remailings effectively

makes tracing sending and receiving impossible. Contrast this

with the software version, the DC protocol.



***     modular exponentiation  -- raising an integer to the

power of another integer, modulo some integer. For integers

a, n, and m, a^m mod n. For example, 5^3 mod 100 = 25. Modular

exponentiation can be done fairly quickly with a sequence of

bit shifts and adds, and special purpose chips have been

designed. See also discrete logarithm.



***     National Security Agency (NSA)  -- the largest

intelligence agency, responsible for making and breaking

ciphers, for intercepting communications, and for ensuring

the security of U.S. computers. Headquartered in Fort Meade,

Maryland, with many listening posts around the world.  The

NSA funds cryptographic research and advises other agencies

about cryptographic matters. The NSA once obviously had the

world's leading cryptologists, but this may no longer be the

case.



***     negative credential -- a credential that you possess

that you don't want any one else to know, for example, a

bankruptcy filing.  A formal version of a negative reputation.



***     NP-complete -- a large class of difficult problems.

"NP" stands for nondeterministic polynomial time, a class of

problems thought in general not to have feasible algorithms

for their solution.  A problem is "complete"  if  any other NP

problem may be reduced to that problem.   Many important

combinatorial and algebraic problems are NP-complete: the

traveling salesman problem, the Hamiltonian cycle problem,

the word problem, and on and on.



***     oblivious transfer -- a cryptographic primitive that

involves the probabilistic transmission of bits. The sender

does not know if the bits were received.



***     one-time pad -- a string of randomly-selected bits or

symbols which is combined with a plaintext message to

produce the ciphertext. This combination may be shifting

letters some amount, bitwise exclusive-ORed, etc.). The

recipient, who also has a copy of the one time pad, can easily

recover the plaintext. Provided the pad is only used once and

then destroyed, and is not available to an eavesdropper, the

system is perfectly secure, i.e., it is information-

theoretically secure. Key distribution (the pad)  is obviously a

practical concern, but consider CD-ROM's.



***     one-way function -- a function which is easy to

compute in one direction but hard to find any inverse for, e.g.

modular exponentiation, where the inverse problem is known

as the discrete logarithm problem. Compare the special case

of trap door one-way functions.  An example of  a one-way

operation is multiplication: it is  easy to multiply two

prime numbers of 100 digits to produce a 200-digit number,

but  hard to factor that 200-digit number.



***     P ?=? NP  -- Certainly the most  important unsolved

problem in complexity theory. If P = NP, then cryptography as

we know it today does not exist.  If P = NP,  all NP problems

are "easy."



***     padding -- sending extra messages to confuse

eavesdroppers and to defeat traffic analysis.   Also adding

random bits to a message to be enciphered.



***     plaintext -- also called cleartext, the text that is to be

enciphered.



***     Pretty Good Privacy (PGP)  -- Phillip ZimmermanUs

implementation of RSA, recently upgraded to version 2.0,

with more robust components and several new features. RSA

Data Security has threatened PZ so he no longer works on it.

Version 2.0 was written by a consortium of non-U.S. hackers.



***     prime numbers -- integers with no factors other than

themselves and 1. The number of primes is unbounded.  About

1% of the 100 decimal digit numbers are prime.  Since there

are about 10^70 particles in the universe, there are about

10^23  100 digit primes for each and every particle in the

universe!



***     probabilistic encryption  -- a scheme by Goldwasser,

Micali, and Blum that allows multiple ciphertexts for the

same plaintext, i.e., any given plaintext may have many

ciphertexts if the ciphering is repeated. This protects against

certain types of known ciphertext attacks on RSA.



***     proofs of identity -- proving who you are, either your

true name, or your digital identity. Generally, possession of

the right key is sufficient proof (guard your key!). Some work

has been done on "is-a-person" credentialling agencies, using

the so-called Fiat-Shamir protocol...think of this as a way to

issue unforgeable digital passports. Physical proof of identity

may be done with biometric security methods. Zero knowledge

proofs of identity reveal nothing beyond the fact that the

identity is as claimed. This has obvious uses for computer

access, passwords, etc.



***     protocol -- a formal procedure for solving some

problem. Modern cryptology is mostly about the study of

protocols for many problems, such as coin-flipping, bit

commitment (blobs), zero knowledge proofs, dining

cryptographers, and so on.



***     public key -- the key distributed publicly to potential

message-senders. It may be published in a phonebook-like

directory or otherwise sent. A major concern is the validity

of this public key to guard against spoofing or impersonation.



***     public key cryptosystem -- the modern breakthrough

in cryptology, designed by Diffie and Hellman, with

contributions from several others. Uses trap door one-way

functions so that encryption may be done by anyone with

access to the "public key" but decryption may be done only by

the holder of the "private key." Encompasses public key

encryption, digital signatures, digital cash, and many other

protocols and applications.



***     public key encryption -- the use of modern

cryptologic methods to provided message security and

authentication. The RSA algorithm is the most widely used

form of public key encryption, although other systems exist.

A public key may be freely published, e.g., in phonebook-like

directories, while the corresponding private key is closely

guarded.



***     public key patents  -- M.I.T. and Stanford, due to the

work of Rivest, Shamir, Adleman, Diffie, Hellman, and Merkle,

formed Public Key Partners to license the various public key,

digital signature, and RSA patents. These patents, granted in

the early 1980s, expire in the between 1998 and 2002. PKP

has licensed RSA Data Security Inc., of Redwood City, CA,

which handles the sales, etc.



***     quantum cryptography -- a system based on quantum-

mechanical principles. Eavesdroppers alter the quantum state

of the system and so are detected. Developed by Brassard and

Bennett, only small laboratory demonstrations have been

made.



***     reputations -- the trail of positive and negative

associations and judgments that some entity accrues. Credit

ratings, academic credentials, and trustworthiness are all

examples. A digital pseudonym will accrue these reputation

credentials based on actions, opinions of others, etc. In

crypto anarchy, reputations and agoric systems will be of

paramount importance. There are many fascinating issues of

how reputation-based systems work, how credentials can be

bought and sold, and so forth.



***     RSA -- the main public key encryption algorithm,

developed by Ron Rivest, Adi Shamir, and Kenneth Adleman. It

exploits the difficulty of factoring large numbers to create a

private key and public key. First invented in 1978, it remains

the core of modern public key systems. It is usually much

slower than DES, but special-purpose modular exponentiation

chips will likely speed it up. A popular scheme for speed is to

use RSA to transmit session keys and then a high-speed

cipher like DES for the actual message text.

***     Description -- Let p and q be large primes, typically with more than

100 digits. Let n = pq and find some e such that e is relatively prime to (p

- 1)(q - 1). The set of numbers p, q, and e is the private key for RSA. The

set of numbers n and e forms the public key (recall that knowing n is not

sufficient to easily find p and q...the factoring problem).  A message M is

encrypted by computing M^e mod n. The owner of the private key can

decrypt the encrypted message by exploiting number theory results, as

follows. An integer d is computed such that ed =1 (mod (p - 1)(q - 1)).

Euler proved a theorem that M^(ed) = M mod n and so M^(ed) mod n = M.

This means that in some sense the integers e and d are "inverses" of each

other. [If this is unclear, please see one of the many texts and articles on

public key encryption.]



***     secret key cryptosystem -- A system which uses the

same key to encrypt and decrypt traffic at each end of a

communication link.  Also called a symmetric or one-key

system.  Contrast with public key cryptosystem.



***     smart cards -- a computer chip embedded in credit

card.  They can hold cash, credentials, cryptographic keys,

etc. Usually these are built with some degree of tamper-

resistance. Smart cards may perform part of a crypto

transaction, or all of it. Performing part of it may mean

checking the computations of a more powerful computer, e.g.,

one in an ATM.



***     spoofing, or masquerading -- posing as another user.

Used for stealing passwords, modifying files, and  stealing

cash. Digital signatures and other authentication methods are

useful to prevent this. Public keys must be validated and

protected to ensure that others don't substitute their own

public keys which users may then unwittingly use.



***     steganography -- a part of cryptology dealing with

hiding messages and obscuring who is sending and receiving

messages. Message traffic is often padded to reduce the

signals that would otherwise come from a sudden beginning

of messages.



***     symmetric cipher -- same as private key

cryptosystem.



***     tamper-responding modules, tamper-resistant

modules (TRMs) -- sealed boxes or modules which are hard

to open, requiring extensive probing and usually leaving ample

evidence that the tampering has occurred. Various protective

techniques are used, such as special metal or oxide layers on

chips, armored coatings, embedded optical fibers, and other

measures to thwart analysis. Popularly called "tamper-proof

boxes." Uses include: smart cards, nuclear weapon initiators,

cryptographic key holders, ATMs, etc.



***     tampering, or active wiretapping -- interfering with

messages and possibly modifying them. This may compromise

data security, help to break ciphers, etc.  See also spoofing.



***     token -- some representation, such as ID cards, subway

tokens, money, etc., that indicates possession of some

property or value.



***     traffic analysis -- determining who is sending or

receiving messages by analyzing packets, frequency of

packets, etc. A part of steganography. Usually handled with

traffic padding.



***     transmission rules -- the protocols for determining

who can send messages in a DC protocol, and when. These

rules are needed to prevent collision and deliberate jamming

of the channels.



***     trap messages -- dummy messages in DC Nets which

are used to catch jammers and disrupters. The messages

contain no private information and are published in a blob

beforehand so that the trap message can later be opened to

reveal the disrupter. (There are many strategies to explore

here.)



***     trap-door -- In cryptography, a piece of secret

information that allows the holder of a private key to invert a

normally hard to invert function.



***     trap-door one way functions -- functions which are

easy to compute in both the forward and reverse direction but

for which the disclosure of an algorithm to compute the

function in the forward direction does not provide

information on how to compute the function in the reverse

direction. More simply put, trap-door one way functions are

one way for all but the holder of the secret information. The

RSA algorithm is the best-known example of such a function.



***     unconditional security -- same as information-

theoretic security, that is, unbreakable except by loss or

theft of the key.



***     unconditionally  secure -- where no amount of

intercepted ciphertext is enough to allow the cipher to be

broken, as with the use of a one-time pad cipher. Contrast

with computationally secure.



***     voting, cryptographic -- Various schemes have been

devised for anonymous, untraceable voting. Voting schemes

should have several properties: privacy of the vote, security

of the vote (no multiple votes), robustness against disruption

by jammers or disrupters, verifiability (voter has confidence

in the results), and efficiency.



***     zero knowledge proofs -- proofs in which no

knowledge of the actual proof is conveyed. Peggy the Prover

demonstrates to Sid the Skeptic that she is indeed in

possession of some piece of knowledge without actually

revealing any of that knowledge. This is useful for access to

computers, because eavesdroppers or dishonest sysops cannot

steal the knowledge given. Also called minimum disclosure

proofs. Useful for proving possession of some property, or

credential, such as age or voting status, without revealing

personal information.







--

..........................................................................

Timothy C. May         | Crypto Anarchy: encryption, digital money,

tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero

408-688-5409           | knowledge, reputations, information markets,

W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.

Higher Power: 2^756839 | PGP Public Key: by arrangement.