scientific article; zbMATH DE number 3912270
The basic knapsack public-key cryptosystem was presented by \textit{R. C. Merkle} and \textit{M. E. Hellman} [IEEE Trans. Inf. Theory 24, 525--530 (1978; Zbl 1487.94132)]. In this paper, a variant of a Shamir's attack [\textit{A. Shamir}, ibid. 30, 699--704 (1984; Zbl 0552.94007)] on the basic Merkle-Hellman knapsack cryptosystem, Algorithm S, is given. A performance analysis of Algorithm S is presented. The main result is: Let \(R\) be the information rate and \(n\) be the block size of a plain text, then for any fixed \(R\), Algorithm S runs to completion in time polynomial in \(n\) on all knapsacks with rate \(R'\geq R\), and it successfully breaks at least the fraction \(1-c/n\) of such knapsack cryptosystems as \(n\to \infty\), where \(c\) is a constant depending on \(R\). [For the entire collection see Zbl 0543.00014.]
- Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme
- A critical analysis of the security of knapsack public-key algorithms
- scientific article; zbMATH DE number 3865148
- A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
- On Breaking the Iterated Merkle-Hellman Public-Key Cryptosystem
- Simultaneous diophantine approximation of rationals by rationals
- New attacks for knapsack based cryptosystems
- Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme
- Knapsack public key cryptosystems and Diophantine approximation
- Evaluation of the Adleman attack on multiply iterated knapsack cryptosystems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3689090)