Talk:Merkle–Hellman knapsack cryptosystem

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]