Merkle–Hellman knapsack cryptosystem

E434684

The Merkle–Hellman knapsack cryptosystem is an early public-key encryption scheme based on the subset sum (knapsack) problem, historically significant as one of the first practical public-key systems though later found to be insecure.

All labels observed (2)

How this entity was disambiguated

Statements (49)

Predicate Object
instanceOf encryption scheme ⓘ
knapsack cryptosystem ⓘ
public-key cryptosystem ⓘ
application theoretical study of cryptanalytic techniques ⓘ
basedOn knapsack problem ⓘ
subset sum problem ⓘ
linked to: Subset sum problem
brokenBy Adi Shamir ⓘ
brokenIn 1982 ⓘ
ciphertextType integer ⓘ
cipherType asymmetric-key cipher ⓘ
public-key cipher ⓘ
consideredSecure false ⓘ
constructionStep choose a modulus larger than the sum of the superincreasing sequence ⓘ
choose a multiplier relatively prime to the modulus ⓘ
choose a superincreasing sequence as private key ⓘ
compute public key by modular multiplication of private sequence ⓘ
creator Martin Hellman ⓘ
Ralph Merkle ⓘ
decryptionMethod multiply ciphertext by modular inverse of multiplier ⓘ
solve superincreasing subset sum greedily ⓘ
encryptionMethod encode bits as subset sums of public key weights ⓘ
field cryptography ⓘ
public-key cryptography ⓘ
hasComponent decryption algorithm ⓘ
encryption algorithm ⓘ
key generation algorithm ⓘ
hasVariant general knapsack cryptosystem ⓘ
multiple-iterated Merkle–Hellman knapsack cryptosystem ⓘ
historicalSignificance demonstrated practicality of public-key cryptography ⓘ
early example of public-key encryption ⓘ
inspiredBy Diffie–Hellman key exchange ⓘ
introducedIn 1978 ⓘ
keyType private key ⓘ
public key ⓘ
namedAfter Martin Hellman ⓘ
Ralph Merkle ⓘ
notableAs one of the first practical public-key cryptosystems ⓘ
plaintextType binary message ⓘ
problemType NP-complete problem (subset sum) ⓘ
publicationYear 1978 ⓘ
securityGoal confidentiality ⓘ
status broken ⓘ
taughtIn cryptography courses ⓘ
uses modular inverse ⓘ
modular multiplication ⓘ
superincreasing sequence ⓘ
vulnerableTo Shamir’s attack ⓘ
lattice-based attacks ⓘ
low-density subset sum attacks ⓘ

How these facts were elicited

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

Ralph Merkle → knownFor → Merkle–Hellman knapsack cryptosystem ⓘ
subject linked to: Merkle
Merkle–Hellman knapsack cryptosystem → hasVariant → multiple-iterated Merkle–Hellman knapsack cryptosystem ⓘ
linked to: Merkle–Hellman knapsack cryptosystem