Cryptography's Role in Securing the Information Society (1996) / Chapter Skim
Currently Skimming:
C - A Brief Primer on Cryptography
C - A Brief Primer on Cryptography
Pages 364-395
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 364... ...
The scientific basis for modern cryptography was established in 1949 with the development of information theory by Claude Shannon, who determined for the first time a mathematically rigorous basis for defining 364
|
From page 365... ...
. The second major revolution occurred in 1976 with the first discussion in the open literature of asymmetric cryptography, inspired by a landmark paper of Whitfield Diffie and Martin Hellman.1 C.2 CAPABILITIES ENABLED BY CRYPTOGRAPHY Cryptography can help to ensure the integrity of data (i.e., that data retrieved or received are identical to data originally stored or sent)
|
From page 366... ...
In such cases, the integrity check (also known as a message authenticator) must use a process that involves information unknown to potential penetrators; that is, it has parts that are secret and known only to the communicating parties (usually a secret key)
|
From page 367... ...
In short, a cryptographic checksum depends on a secret key known to the au thorized transmitter and receiver, whereas a one-way hash value can be computed by anyone. The hash value is then acted on by the secret key in an asymmetric cryptographic system to produce a digital signature.
|
From page 368... ...
Vendors accepting credit cards use handwritten signatures to authenticate identities on the assumption that only the proper holder of a credit card can sign the credit card charge slip in a way that matches the signature on the card. Stronger authentication methods often involve hardware -- a tangible object or artifact -- that must be associated with authorized users and that is not easily duplicated.
|
From page 369... ...
For example, vendors accepting credit cards for face-to-face transactions check the signature on the card (or else accept liability for not performing the check)
|
From page 370... ...
, and any evildoer, Party B can check the digital signature of the message allegedly sent by Party A against the message actually received. If nothing improper has occurred, • Party B can be assured that Party A was in fact the sender; • Party B can be assured that the message received was actually the one Party A sent; and • If Party A ever denies having sent the message, Party B can prove that Party A did.8 Again, if the secrets on which authentication is based are compromised, a valid signature does not mean that a message was actually sent 7Although the entire message could be run through an encryption process and some part of the result used as the digital signature, in normal practice only a digest of the message is subject to this process to conserve both time and computer resources.
|
From page 371... ...
Conceptually, a digital document is mailed to this trusted third party, who provides a date/time stamp and a digital signature of the document-stamp combination. If the date/time stamp is inserted correctly by the third party, the digital signature of that party ensures that the document did indeed exist at the time and date in the document.
|
From page 372... ...
, such separation has obvious advantages. Even the most sophisticated cryptography today requires some keeping of secrets, but a properly implemented cryptography system reduces the problem of keeping messages secret to the problem of keeping secret a much smaller key, thereby simplifying the security problem.
|
From page 373... ...
require strong authentication (e.g., telephone orders) , even if security procedures are intended to minimize the incidence of fraud in such orders (e.g., not shipping an order to an address other than the billing address on the credit card)
|
From page 374... ...
that Party A uses, in combination with an encryption key, to generate the ciphertext. • A decryption algorithm that Party B uses, in combination with a decryption key, to retrieve the plaintext from the ciphertext.
|
From page 375... ...
, the encryption key is the same as the decryption key; thus, message privacy depends on the key being kept secret. A major problem faced by Party A is how to inform Party B of the key that is being used.
|
From page 376... ...
(Computational ease and difficulty refer to the computational resources that are required to perform the task.) An asymmetric cryptographic system based on factoring would regard the prod uct of the two prime integers as the public key and the two prime integers as the private key.
|
From page 377... ...
For example, people using an asymmetric cryptographic system can (in principle) publish their public keys in the equivalent of a telephone book that can be distributed freely.
|
From page 378... ...
Preserving the key management system has many of the same problems associated with it that preserving the older storage media poses. If the choice is made to rewrite unencrypted-and-then-reencrypted data, then the originally encrypted data must be decrypted, which opens another channel for loss of confidentiality.
|
From page 379... ...
Asymmetric cryptographic systems are more complex. The best-known algorithms provide cryptanalytic attacks that grow as exp[c · b1/3 · ln(b)
|
From page 380... ...
Both of these calculations demonstrate that it is clearly possible to specify a key size large enough to guarantee that an attack based on exhaustive search will never be feasible, regardless of advances in conventional computational hardware or algorithms. (The qualification to "conventional" computing is for quantum computing, discussed in Section C.6.6.)
|
From page 381... ...
If the eavesdropper has reason to believe that C1 (the ciphertext of the message of interest) has been produced by the same algorithm and key, he or she may be able to derive the decryption key with much less work than by exhaustive search or the case in which only C1 is available (i.e., the ciphertext-only case)
|
From page 382... ...
. Once the eavesdropper learns the decryption key, he or she can decipher easily any subsequent message that uses that key.
|
From page 383... ...
technique is to encrypt a message multiple times through the same algorithm with different keys; an approach based on multiple encryption using DES has been proposed as an alternative to the Skipjack encryption-decryption algorithm. (Skipjack is the name of the algorithm on which the Clipper chip is based.)
|
From page 384... ...
Medical records, on the other hand, can have privacy time constants on the order of 50 years. Because a company or governmental agency typically uses a single cryptographic system to protect all of its data, ideally the system should have a safety margin commensurate with the longest privacy time constant encountered.21 Symmetric cryptographic systems allow large safety margins at low 21See also footnote 15.
|
From page 385... ...
Even with conventional systems, where 50-year safety margins appear possible and cost-effective, national security and related export considerations may prevent their use. C.6.1 Background The need for safety margins stems from two general categories of technological advances: those due to improvements in computation and those due to breakthroughs in cryptanalytic attacks.
|
From page 386... ...
However, another factoring method that is applicable to breaking asymmetric cryptographic systems was being tested at about the time and would have been successful in factoring F8 in either 1980 or the next year.) Also, the factoring of F9 involved a large network of workstations, connected over the Internet and using idle time.
|
From page 387... ...
Today, factoring 512-bit numbers is extremely difficult, while factoring 1,024-bit numbers is computationally impossible. By using 512 bits as a reasonable security level for asymmetric cryptographic systems whose data must be secret only in the immediate future, a safety margin of 2 (the minimal indicated)
|
From page 388... ...
, and have access to modern integrated circuit technology. National intelligence organizations within the developed world meet all of these 24Whitfield Diffie and Martin Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard," Computer, June 1977, pp.
|
From page 389... ...
Munitions List controls. Unlike asymmetric cryptographic systems, the cost of increasing the key size of DES, or of most other conventional cryptographic systems, is minimal.
|
From page 390... ...
By computing the two running times (when that bit is 0 and when it is 1) for a large number of observed computations and correlating them with the observed computation time, the attacker can make a good guess on the first bit of the secret key.
|
From page 391... ...
The figure of $1 million per solution is appropriate since some data will be worth that much to an opponent. Again, any cryptanalytic improvements over exhaustive search would decrease the lifetime of Skipjack.
|
From page 392... ...
If logical operations are now performed -- and the laws of quantum mechanics do allow such operations -- then computations can be performed simultaneously and in parallel on all the represented numbers. Using these concepts, Shor was able to find a quantum algorithm that can, in principle, find the prime factors of a number N in a time propor 28Material in this section is based on two JASON reports, one on quantum computing called Boundaries of Computing, and the second called DNA Computing (A.
|
From page 393... ...
A small computational problem has indeed been solved by the use of a DNA computer.31 This successful demonstration puts DNA computing on a much firmer foundation than quantum computing. However, DNA computing does not fundamentally change the hard nature of cryptanalytic problems, such as factoring or breaking DES; it merely changes the cost of the computation.
|
From page 394... ...
If this exponential behavior continues to hold, asymmetric cryptographic systems can have significant safety margins, comparable to those obtainable with conventional cryptographic systems, without undue economic or time cost to legitimate users. Caution is warranted, however, since the elliptic curve systems are fairly recent and therefore not nearly as well studied as RSA and Diffie-Hellman.
|
From page 395... ...
At the same time, they note that quantum key distribution must compete with classical techniques for key exchange, which are much cheaper over long distances. 33The description in this subsection is taken from Charles Bennett et al., "Quantum Cryptography," Scientific American, Volume 267(4)
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.