Merkle-Hellman scheme

The Merkle-Hellman cryptosystem was one of the earliest examples of public key cryptography, and depends on the NP-complete problem “SUBSET SUM” for its security.

Suppose Bob wants to send Alice a message.

Alice generates private key ${a_{1},a_{2},\\dots a_{n}}$ which is a superincreasing sequence. She then picks $d\\gg\\sum_{i=1}^{n}a_{i}$ and $h$ comprime with $d$ . Using the euclidean algorithm, she finds $h^{-1}$ such that $hh^{-1}\\equiv 1\\quad(\\textrm{mod }d)$ .

Alice now generates her public key ${b_{1},b_{2},\\dots b_{n}}$ where $b_{i}=ha_{i}\\quad(\\textrm{mod }d)$ and sends this to Bob.

Bob breaks up his message into binary strings of length $n$ . To send the string $m_{1}m_{2}\\dots m_{n}$ to Alice, he forms $C=\\sum_{i=1}^{n}m_{i}b_{i}$ and sends $C$ to Alice.

On receiving $C$ , Alice forms $V=h^{-1}C\\quad(\\textrm{mod }d)$ . Now, since $b_{i}=ha_{i}\\quad(\\textrm{mod }d)$ , we have that $V=\\sum_{i=1}^{n}m_{i}a_{i}$ . Since ${a_{i}}$ is a superincreasing sequence, it is easy to recover the $m_{i}$ if you know $V$ and ${a_{i}}$ , and it takes $O(n)$ arithmetic operations.

In 1982, a fast algorithm was found for recovering the message knowing only the public key and the cryptogram $C$ . It takes advantage of the fact that the public key ${b_{i}}$ is not generated in a random way, but comes from a superincreasing sequence.

单词	MerkleHellmanScheme
释义	Merkle-Hellman scheme The Merkle-Hellman cryptosystem was one of the earliest examples of public key cryptography, and depends on the NP-complete problem “SUBSET SUM” for its security. Suppose Bob wants to send Alice a message. Alice generates private key ${a_{1},a_{2},\\dots a_{n}}$ which is a superincreasing sequence. She then picks $d\\gg\\sum_{i=1}^{n}a_{i}$ and $h$ comprime with $d$ . Using the euclidean algorithm, she finds $h^{-1}$ such that $hh^{-1}\\equiv 1\\quad(\\textrm{mod }d)$ . Alice now generates her public key ${b_{1},b_{2},\\dots b_{n}}$ where $b_{i}=ha_{i}\\quad(\\textrm{mod }d)$ and sends this to Bob. Bob breaks up his message into binary strings of length $n$ . To send the string $m_{1}m_{2}\\dots m_{n}$ to Alice, he forms $C=\\sum_{i=1}^{n}m_{i}b_{i}$ and sends $C$ to Alice. On receiving $C$ , Alice forms $V=h^{-1}C\\quad(\\textrm{mod }d)$ . Now, since $b_{i}=ha_{i}\\quad(\\textrm{mod }d)$ , we have that $V=\\sum_{i=1}^{n}m_{i}a_{i}$ . Since ${a_{i}}$ is a superincreasing sequence, it is easy to recover the $m_{i}$ if you know $V$ and ${a_{i}}$ , and it takes $O(n)$ arithmetic operations. In 1982, a fast algorithm was found for recovering the message knowing only the public key and the cryptogram $C$ . It takes advantage of the fact that the public key ${b_{i}}$ is not generated in a random way, but comes from a superincreasing sequence.
随便看	CommutingNormalMatricesAreSimultaneouslyDiagonalizable commuting normal matrices are simultaneously diagonalizable CommutingVectorFields commuting vector fields Comodule comodule ComoduleAlgebra comodule algebra ComoduleCoalgebra comodule coalgebra Compact compact CompactElement compact element CompactGroupsAreUnimodular compact groups are unimodular CompactHausdorffSpaceIsExtremallyDisconnectedIfItsFunctionAlgebraIsABoundedCompleteLattice compact Hausdorff space is extremally disconnected if its function algebra is a bounded complete lattice Compactification compactification CompactlyGenerated compactly generated CompactlySupportedContinuousFunctionsAreDenseInLp compactly supported continuous functions are dense in L^p Compactness