Talk:Merkle–Hellman knapsack cryptosystem

Request for Move

I believe this article title is ambiguous. Merkle-Hellman seems too much like an article on their numerous cooperation in cryptosystems. I propose Merkle-Hellman knapsack cryptosystem, similar to Naccache-Stern knapsack cryptosystem. If noone objects I will move.--Michael miceli (talk) 20:48, 2 August 2009 (UTC)

Request for clarification

I don't get the decryption. someone needs to clarify it. Also, I want info on how the cypher was broken. --anon

I fixed a minor error in the key generation section and added some to the previously incredibly vague section on decryption. I hope this makes a little more sense. There is still a lot left unexplained (modular arithmatic, how the cryptosystem was broken, etc), but at least it's a start. I know very little about the topic, but it's really interesting. Anyone who knows more should totally add there insight, I'dbe interested in learning more. -- User:ApatheticToTheCause.

I agree that there needs to be something about how the cypher was broken. The article seems to indicate that "solving" the cypher without knowing the private key is an NP-complete problem, but one of the references is entitled "A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem", which contradicts this. There needs to be some explanation of why this cryptosystem is in the P complexity class while the subset sum problem is in NP. Augurar (talk) 03:31, 30 July 2010 (UTC)

Potential replacement for unclear Subset Sum Problem description

Quote:

• The Merkle-Hellman system is based on the subset sum problem (a special case of the knapsack problem): given a list of numbers and a third number, which is the sum of a subset of these numbers, determine the subset.

This is particularly vague for me but not-being experienced in the field of cryptography or knapsack problems I have a hesitance to fix it myself. If my understanding of the Subset Sum Problem (according to the wikipedia page on that topic) is correct then would this make more sense:

• The Merkle-Hellman system is based on the subset sum problem (a special case of the knapsack problem): given a list of numbers a and a number b, which is the sum of some subset of a, determine the subset of a which sums to b.

If you can verify this to be a correct interpretation of the subset sum problem please update the article. Thanks in advance. --Diploid (talk) 16:27, 21 April 2010 (UTC)

I changed the sentence. Let me know if you don't think it is good. Michael miceli (talk) 16:40, 22 April 2010 (UTC)

all cipher system are breackable accept one time pad

all cipher system are breackable accept one time pad

Not necessarily true. Although, given enough time, one can certainly exhaust the keyspace for any cipher (although sometimes it's a nearly impossibly long amount of time) and thus crack the encryption, this doesn't constitute breaking the cipher's encryption. In cryptography we're basically finding a way to transform one piece of data (plaintext) into another (ciphertext) in such a way that the reverse transformation is very efficient, if you know some secret (like a key), and very inefficient if you don't know the secret. BREAKING a cryptosystem requires that you find a way to efficiently decrypt the data without finding out the key. --Duplico 22:37, 16 May 2007 (UTC)

gcd

what is gcd? i looked around and the best match i could find was greatest common divisor. Is this correct? I'm not totally sure how to add to wikipedia in the proper format so i put it in talk. if so, could "gcd(r,q) == 1" be better expressed as "r and q are coprime", since coprime has already been mentioned.

yes gcd is "greatest common divisor", I will add "(i.e. are coprime)".. —Preceding unsigned comment added by 87.123.24.0 (talk) 08:53, 27 April 2009 (UTC)

Why is Bob using Alice's PRIVATE key?

How does Bob know Alice's private key, and why is that being used to decrypt? — Preceding unsigned comment added by 68.40.171.174 (talk) 00:11, 21 August 2012 (UTC)

Why is Bob using Alice's PRIVATE key?

How does Bob know Alice's private key, and why is that being used to decrypt?

IE - what's the use of the public key if it doesn't get used? — Preceding unsigned comment added by 68.40.171.174 (talk) 00:14, 21 August 2012 (UTC)