Principles of Cryptography
Digital Signatures
Some publickey algorithms can be used to generate digital
signatures. A digital signature is a small amount of data that
was created using some secret key, and there is a public key that
can be used to verify that the signature was really generated using
the corresponding private key. The algorithm used to generate the
signature must be such that without knowing the secret key it is not
possible to create a signature that would verify as valid.
Digital signatures are used to verify that a message really comes
from the claimed sender (assuming only the sender knows the secret
key corresponding to his/her public key). They can also be used to
timestamp documents: a trusted party signs the
document and its timestamp with his/her secret key, thus testifying
that the document existed at the stated time.
Digital signatures can also be used to testify (or
certify) that a public key belongs to a particular person.
This is done by signing the combination of the key and the
information about its owner by a trusted key. The digital signature
by a third party (owner of the trusted key), the public key and
information about the owner of the public key are often called
certificates.
The reason for trusting that third party key may again be signed by
another trusted key. Eventually some key must be a root of
the trust hierarchy (that is, it is not trusted because it was
signed by somebody, but because you believe a priori that the key
can be trusted). In a centralized key infrastructure there
are very few roots in the trust network (e.g., trusted government
agencies; such roots are also called certification
authorities). In a distributed infrastructure there need
not be any universally accepted roots, and each party may have
different trusted roots (such of the party's own key and any keys
signed by it). This is the web of trust concept used in e.g.
PGP.
A digital signature of an arbitrary document is typically created by
computing a message digest from the document, and concatenating
it with information about the signer, a timestamp, etc. The resulting
string is then encrypted using the private key of the signer using a
suitable algorithm. The resulting encrypted block of bits is the
signature. It is often distributed together with information about
the public key that was used to sign it. To verify a signature, the
recipient first determines whether it trusts that the key belongs to
the person it is supposed to belong to (using the web of trust or a
priori knowledge), and then decrypts the signature using the public
key of the person. If the signature decrypts properly and the
information matches that of the message (proper message digest
etc.), the signature is accepted as valid.
Several methods for making and verifying digital signatures are
freely available. The most widely known algorithm is RSA.
Cryptographic Hash Functions
Cryptographic hash functions are used in various contexts, for example
to compute the message digest when making a digital signature. A hash
function compresses the bits of a message to a fixedsize hash value
in a way that distributes the possible messages evenly among the possible
hash values. A cryptographic hash function does this in a way that
makes it extremely difficult to come up with a message that would
hash to a particular hash value.
Cryptographic hash functions
typically produce hash values of 128 or more bits. This
number (2^{128}) is vastly larger than the number of
different messages likely to ever be exchanged in the world. The
reason for requiring more than 128 bits is based on the
birthday paradox. The birthday paradox roughly states that
given a hash function mapping any message to an 128bit hash
digest, we can expect that the same digest will be computed twice
when 2^{64} randomly selected messages have been
hashed. As cheaper memory chips for computers become available it
may become necessary to require larger than 128 bit message
digests (such as 160 bits as has become standard recently).
Many good cryptographic hash functions are freely available. The
most famous cryptographic hash functions are those of the MD family,
in particular MD4 and MD5. MD4 has been broken, and MD5, in widespread
use, should be still considered secure until is broken as well. SHA1
and RipeMD160 are two examples that are still considered state of the art.
Cryptographic Random Number Generators
Cryptographic random
number generators generate random numbers for use in cryptographic
applications, such as for keys. Conventional random number
generators available in most programming languages or programming
environments are not suitable for use in cryptographic applications
(they are designed for statistical randomness, not to resist
prediction by cryptanalysts).
In the optimal case, random numbers are based on true physical
sources of randomness that cannot be predicted. Such sources may
include the noise from a semiconductor device, the least significant
bits of an audio input, or the intervals between device interrupts
or user keystrokes. The noise obtained from a physical source is
then "distilled" by a cryptographic hash function to make every bit
depend on every other bit. Quite often a large pool (several
thousand bits) is used to contain randomness, and every bit of the
pool is made to depend on every bit of input noise and every other
bit of the pool in a cryptographically strong way.
When true physical randomness is not available, pseudorandom
numbers must be used. This situation is undesirable, but often
arises on general purpose computers. It is always desirable to
obtain some environmental noise  even from device latencies,
resource utilization statistics, network statistics, keyboard
interrupts, or whatever. The point is that the data must be
unpredictable for any external observer; to achieve this, the random
pool must contain at least 128 bits of true entropy.
Cryptographic pseudorandom number generators typically have a
large pool ("seed value") containing randomness. Bits are returned
from this pool by taking data from the pool, optionally running the
data through a cryptographic hash function to avoid revealing the
contents of the pool. When more bits are needed, the pool is stirred
by encrypting its contents by a suitable cipher with a random key
(that may be taken from an unreturned part of the pool) in a mode
which makes every bit of the pool depend on every other bit of the
pool. New environmental noise should be mixed into the pool before
stirring to make predicting previous or future values even more
impossible.
Even though cryptographically strong random number generators are
not very difficult to build if designed properly, they are often
overlooked. The importance of the random number generator must thus
be emphasized  if done badly, it will easily become the weakest
point of the system.
Several examples of cryptographic random number generators are
publicly available.
[INDEX The Previous Page The Next Page]
Information:
Enigma Story (illustrated)
· cryptography
· secure key generator
security expert
· system security
· JSCrypto info
· references
Tools:
JSHTML compiler
· PGPfone™
· PGPdisk™
steganography
· JSsreganography
· JSCODER/DECODER guide
· JSCODER/DECODER
Toys:
Lottery
· Cryptool 1
· Cryptool 2
· Calculator
· Calendar
adapted by Rafal Swiecki, p. eng. email
November, 2004
This document is in the public domain.
