A cryptanalytic time-memory trade-off
- 1 July 1980
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 26 (4) , 401-406
- https://doi.org/10.1109/tit.1980.1056220
Abstract
A probabilistic method is presented which cryptanalyzes anyNkey cryptosystem inN^{2/3}operational withN^{2/3}words of memory (average values) after a precomputation which requiresNoperations. If the precomputation can be performed in a reasonable time period (e.g, several years), the additional computation required to recover each key compares very favorably with theNoperations required by an exhaustive search and theNwords of memory required by table lookup. When applied to the Data Encryption Standard (DES) used in block mode, it indicates that solutions should cost between1 and100 each. The method works in a chosen plaintext attack and, if cipher block chaining is not used, can also be used in a ciphertext-only attack.Keywords
This publication has 6 references indexed in Scilit:
- Privacy and authentication: An introduction to cryptographyProceedings of the IEEE, 1979
- Hiding information and signatures in trapdoor knapsacksIEEE Transactions on Information Theory, 1978
- An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)IEEE Transactions on Information Theory, 1978
- Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption StandardComputer, 1977
- New directions in cryptographyIEEE Transactions on Information Theory, 1976
- Cryptography and Computer PrivacyScientific American, 1973