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.
随便看	3.9 The principle of unique choice 3DistributedDynamicalSystems 3. Distributed dynamical systems 3manifold 3-manifold 3-manifold 3manifold1 41Quasiinverses 4.1 Quasi-inverses 42HalfAdjointEquivalences 4.2 Half adjoint equivalences 43BiinvertibleMaps 4.3 Bi-invertible maps 44ContractibleFibers 4.4 Contractible fibers 45OnTheDefinitionOfEquivalences 4.5 On the definition of equivalences 46SurjectionsAndEmbeddings 4.6 Surjections and embeddings 47ClosurePropertiesOfEquivalences 4.7 Closure properties of equivalences 48TheObjectClassifier 4.8 The object classifier 49UnivalenceImpliesFunctionExtensionality 4.9 Univalence implies function extensionality