Cryptographic primitives are the basic components of any cryptosystem. A cryptosystem is a system of encryption, for example GPG, PGP, IPSEC, and SSL.
Other cryptosystems have uses in the banking industry (they make ATMs possible), e-commerce (the padlock on your browser), and for governments - communications between embassies, storage of confidential data, and in the military. Strong encryption can also be used by the general public for privacy and confidentiality.
The cryptographic primitives:
-
The hash function.
Put simply, large amounts of data are compressed into a much shorter space in a non-reversible manner. This may be considered a secure version of the checksum.
-
The block cipher.
A block cipher takes data and encrypts it chunk at a time using a user-selected key. To regain the original data from the output of a good block cipher, you have an easy way: using the key, and the really hard way: trying every single possible key.
The stream cipher.
A stream cipher works just like a block cipher, except that it takes data in one continuous flow, and encrypts each unit of data individually.
This is used (for example) in encrypting communications, such as WEP1, rather than files, although it can be used for anything.
-
The asymmetric cipher.
Also known as public-key encryption, where two keys are used instead of the traditional one. Data encrypted with one key can only be read using the other. First conceived by Whitfield Diffie, and first implemented in RSA2.
Though this sounds simple, it has a host of far-reaching effects, and makes things like e-commerce possible.
-
The digital signature.
Not to be confused with a real signature, despite it's name. Like the asymmetric cipher, two keys are used. But instead of using them for encrypting and decrypting, there is a signature key, which is used to sign data, and a verification key, which is used for verifying a digital signature.
Unlike a real signature, digital signatures are not bound to a particular person. This is where numerous e-government proposals have fallen flat: because of their inherent nature, digital signatures authenticate one computer device to another, not one person to a computer device. That is another node.
Most of these primitives can be constructed using some combination of the other four. For example, a block cipher becomes a hash function if you have a single output that contains all the output blocks of a block cipher XORed together. A digital signature scheme can be constructed using a hash function and an asymmetric cipher.
However, in most cases you aren't limited to constructing primitives out of each other, which is just as well - each primitive normally has different design requirements. For example, hash functions have to avoid collisions, and block/stream ciphers are normally constructed to be resistant to differential and linear cryptanalysis.
From these basic components it is possible to build almost any system imaginable: online poker, anonymous but unforgeable digital cash, pseudononymous credit (think nom de plume), group signatures, time stamping, Zero knowledge proofs, to (if you wanted to) fairly 'flipping a coin' with someone on the other side of the 'net.
1: WEP (the 802.11b encryption standard) is a bad example, as it has been broken, due to a shoddy implementation and key-scheduling attacks in RC4.
2: There is a brilliant explanation of the mechanics behind RSA here.
Sources:
Security Engineering - Ross Anderson
Applied Cryptography - Bruce Schneier
Weaknesses in the Key Scheduling Algorithm of RC4 - Scott Fluhrer, Itsik Mantin, Adi Shamir