How can a user “sign” a message?4 Nonrepudiation. How can B prove (in court, for example) that A sent the message?
Technically, authentication has two aspects. One relates to the verification of the origin of received data. The other refers to verifying the identity of a user. Traditional methods include passwords, P.I.N. numbers, etc. Biometric data has been used in recent years as well, for example, for logging into a smart phone. We discuss this in Chapter 8.
Message integrity can be achieved using hash functions as described in Chapter 4. Digital Signatures can be carried out using either symmetric or public key encryption. This is also described in Chapter 4.
3.5 Attacks, Security, Catch‐22 of Cryptography
There are many attacks on cryptosystems, i.e. attempts by an intruder to break the system by recovering the key and the message or the message directly. By far, the attack most difficult to defend against is an impersonation or man‐in‐the‐middle attack. Another type of attack is a brute‐force attack (see Section 7.3) in which the attacker systematically tries all possible keys on the key‐space. A variety of attacks are discussed in Chapter 7.
A basic issue in cryptography is this: If we are trying to guess one of
On the average, when trying to guess one of
First, we explain the concept of average value which is discussed also in Chapter 9. Suppose that, in a class of 6 students, 3 get 70%, 2 get 80%, and 1 gets 92%. What is the average grade? One can write this average as
Proof. The probability of guessing correctly the first time is
Public key algorithms and symmetric algorithms were compared in Section 3.4. With any public key algorithm such as RSA (or elliptic curve cryptography), given sufficient time and computing power, the eavesdropper is certain to recover the message. In fact, with RSA it is generally quicker to try to solve the factoring problem than to try all possible values of
A difficulty with key systems is the key distribution problem, i.e. the problem of getting the common secret key to A and B. This is eloquently expressed by Professor Lomonaco when he writes about the Catch‐22 of cryptography [Lom98].
Catch‐22 of Cryptography:
To communicate in secret, we must first communicate in secret.
For symmetric encryption, the private key has to be given secretly to each entity, whereas the public keys for each entity are
We have spoken already of the assumption that the encryption algorithms for public key cryptography are assumed to be mathematical one‐way functions. This means that enciphering has the property that its values are easily computed by a computer (i.e. are computed in polynomial time), yet the deciphering algorithm cannot be computed in a reasonable amount of time (even on a computer). In other words, the problem of deciphering the cipher text is intractable.
Of course, we emphasize again that the existence of such mathematical one‐way functions is still in doubt since nobody has discovered a mathematical function that is provably one‐way.
But one‐way functions abound in the physical world, many of them related to time. For example, as Beutelspacher [Beu94] points out, most people are not getting
