Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen
Читать онлайн книгу.
each. Of course, with longer keys, transmission errors become more and more prevalent.
Several additional remarks are in order.
1 P. Shor has proved that factoring numbers is computationally feasible with a quantum computer. Thus, if quantum computers ever become a reality, RSA will no longer be viable: it will be completely insecure.
2 The problem of transmission errors has to be addressed given that primes , should be at least 308 digits (1024 bits) each, ensuring a modulus of 617 digits (2048 bits) for long‐term security.
3 Despite the recent mathematical results of Agrawal et al., [AKS04] which shows that one can quickly test for primality3 of a given number, one still has to generate large primes , of roughly the same size which are suitable for RSA use. In particular, they must be resistant to factorization algorithms, one of which is discussed later in the book.
4 For frequent RSA communications, one also needs a fast algorithm for ensuring that has no factors in common with and .
5 The RSA algorithm is slow relative to some comparable symmetric‐key algorithms.
6 The security of RSA is in jeopardy without extensive “preprocessing” of plain text message units before encryption (see Mollin [Mol02]).
7 Other attacks on RSA include timing attacks and “man‐in‐the‐middle” attacks. These are discussed in Chapter 7.
Apart from guaranteeing the secrecy of the message from A to B (or B to A), other fundamental issues in cryptography are as follows:
1 Authentication. Roughly, how can B be sure that the message came from A?
2 Message integrity. How can B be sure that the message has not been altered?
3 Digital signatures. 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