Overview of Knapsack Cryptosystems and Related Problems
The Merkle-Hellman knapsack cryptosystem is a cryptographic system that was initially proposed by Merkle, and later iterated versions were both broken by Shamir and Brickell in the early 1980s and 1985, respectively. This system is related to the classical knapsack problem, subset-sum problem, and easy knapsack problem, each dealing with different variations of subset selection. The easy knapsack problem involves super-increasing sequences, and a polynomial-time algorithm is available for solving it efficiently. An example is provided to illustrate the solution approach.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Merkle-Hellman Knapsack Cryptosystem Merkle offered $100 award for breaking singly - iterated knapsack Singly-iterated Merkle - Hellman KC was broken by Adi Shamir in 1982 At the CRYPTO 83 conference, Adleman used an Apple II computer to demonstrate Shamir s method Merkle offered $1000 award for breaking multiply-iterated knapsack Multiply-iterated Merkle-Hellman knapsack was broken by Brickell in 1985
Classical Knapsack Problem General 0-1 knapsack problem: given n items of different values viand weights wi, find the most valuable subset of the items while the overall weight does not exceed a given capacity W
Subset-Sum Problem Subset Sum problem is a special case of knapsack problem when a value of each item is equal to its weight Input: set of positive integers: A = {a1, a2, an} and the positive integer S Output: TRUE, if there is a subset of A that sums to S and the subset itself FALSE otherwise. The subset-sum problem is NP-hard
Easy Knapsack Problem An easy knapsack problem is one in which set A = {a1, a2, an} is a super-increasing sequence A super-increasing sequence is one in which the next term of the sequence is greater than the sum of all preceding terms: a2> a1, a3> a1+ a2, ., an> a1+ a2+ + an-1 Example: A= {1, 2, 4, 8, 2n-1} is super-increasing sequence
Polynomial Time Algorithm for Easy Knapsack Problem Input: A = {a1, an} is super-increasing sequence, and S >0 Output: TRUE and P binary array of n elements, P[i] =1 means: aibelongs to subset of A that sums to S, P[0] = 0 otherwise. The algorithm returns FALSE if the subset doesn t exist for i n to 1 if S ai then P[i] 1 and S S - ai else P[i] 0 if S != 0 then return (FALSE no solution) else return (P[1], P[2], P[n]).
Example Input: A= {1, 2, 4, 8}, S = 11 Solution: i = 4, S = 11 >= A[4] = 8, P[4]=1, S= S-A[4]=11-8=3 i=3, S=3 < A[3]=4, P[3]=0 i=2, S=3 >= A[2]=2, P[2]=1, S=S-A[2]=3-2=1 i=1, S=1 >= A[1]=1 P[1]=1, S=S-A[1]=1-1=0 Final answer: P[1]P[2]P[3]P[4]=1101
Merkle-Hellman Additive Knapsack Cryptosystem Alice: 1. Constructs the Knapsack cryptosystem 2. Publishes the public key 3. Receives the ciphertext 4. Decrypts the ciphertext using private key Bob: 1. Encrypts the plaintext using public key 2. Sends the plaintext to Alice
Alice Knapsack Cryptosystem Construction Chooses A = {a1, an} super-increasing sequence, A is a private (easy) knapsack a1+ + an = E Chooses M - the next prime larger than E. Chooses W that satisfies 2 W < M and (W, M) = 1(W is relatively prime with M) Computes Public (hard) knapsack B = {b1, .bn}, where bi = Wai (mod M), 1 i n Keeps Private Key: A, W, M Publishes Public key: B
Example: ALICE creates Public and Private Keys Alice Private Key: A= {1, 2, 4, 8} super increasing E = 1+2+4+8 = 15 and M = 17 first prime > 15 W = 7, 2 W < 17, and (7, 17) = 1 Public Key: (1*7) mod 17 = 7 (2*7) mod 17 = 14 (4*7) mod 17 = 28 mod 17 = 11 (8*7) mod 17= 56 mod 17 = 5 Public Key: B = {7, 14, 11, 5}
Bob Encryption Process Binary Plaintext P breaks up into sets of n elements long: P = {P1, Pk} n = = For each set Pi compute P b ij C j i 1 j Ci is the ciphertext that corresponds to plaintext Pi C = {C1, Ck) is ciphertext that corresponds to the plaintext P Cis sent to Alice
Example Continue: Bob Encryption Bob Encryption: Plaintext: 1101 0101 1110 Bob breaks the plaintext into blocks of 4 digits (since the public key has 4 numbers) P={(1101), (0101), (1110)}={P1, P2, P3} Ciphertext: For P1 you take 1101 and multiply by public key: C1= 1*7 + 1*14 + 0*11 + 1*5 = 26 For P2 and P3 do the similar C2 = 0*7 + 1*14 + 0*11 + 1*5 = 19 C3 = 1*7 +1*14 +1*11 + 0*5 = 32 Bob Sends Alice the following ciphertext: C={26, 19, 32}
Alice Decryption Process Computes w, the multiplicative inverse of W mod M: wW 1 (mod M) The connection between easy and hard knapsacks: Wai= bi (mod M) or wbi= ai (mod M) 1 i n For each Ci computes: Si = wCi(mod M) n = = = 1 n n = = S wC w P b ij P wb ij P a ij i i j j j = = 1 1 j j j Plaintext Picould be found using polynomial time algorithm for easy knapsack
Example continue: Alice Decryption: w = 5 multiplicative inverse of 7 (mod 17) 5*26 (mod 17) = 11 5*19 (mod 17) = 10 5* 32 (mod 17) = 7 Plaintext: P1 = 1101 (11 = 1*1 + 1*2 +0*4 + 1*8) P2 = 0101 (10 = 0*1 + 1*2 + 0*4 + 1*8) P3 = 1110 (7 = 1*1 + 1*2 + 1*4 + 0*8)
Programming Lab Encryption and Decryption 100 points Bonus: Dynamic Programming Algorithm Implementation of Cryptanalysis 5 points Bonus 5 points: plaintext string's length is an exact multiple of the public key sequence length Bonus 5 points: the plaintext is the string of lower case letters. In this case your program first will find the binary equivalent for each letter and after that will use the regular algorithm. Testing quiz will be done in class
Encryption and Decryption Write a program that can do either encryption or decryption. The program must take two inputs. The first input must be either 1 or 2, with 1 signaling encryption and 2 signaling decryption. The second input depends on the first input. In case of encryption, the second input - plaintext - is a binary string sequence of 0 s and 1 s. You can assume that plaintext string's length is equal to public key sequence length and the maximal length of the string is 16 bits. In case of decryption, the second input - ciphertext - is a decimal number. Your program should generate the private key and the public key based on the knapsack cryptosystem algorithm. Your program should output the private and public keys as well as encrypted or decrypted message accordingly. Also, print all intermediate important results to test your program for correctness.
PART II: Ciphertext Only Cryptanalytic Attack on Merkle-Hellman Knapsack: Dynamic Programming Algorithm Input:B={b1, b2, bn} public key, C - ciphertext Output: The binary array P plaintext Algorithm: Let Q[i, j] be TRUE if there is a subset of first i elements of B that sums to j, 0 i n, 0 j C Step 1: Computation of P Q[0][0] TRUE for j = 1 to C do: Q[0][j] FALSE for i = 1 to n do: for j = 0 to C do: if (j B[i] < 0): Q[i][j] = Q[i-1][j] else: Q[i][j] = Q[i-1][j-B[i]] or Q[i-1][j]
Step 2: Backtracking Let P be an array of n + 1 elements initialized to 0 i n, j C while i > 0: if (j B[i]) 0): if (Q[i-1][j-B[i]] is True): P[i] P[i] + 1 j j B[i] i i 1 else: i i 1 Output: arrayP, elements of P that equal to 1 construct a desired subset of B that sums to C
EXAMPLE Input: B={1, 4, 5, 2}, C =3 j = 0 TRUE j = 1 FALSE j = 2 FALSE j = 3 FALSE i = 0 i = 1 B[1] =1 i = 2 B[2] = 4 i = 3 B[3] = 5 i = 4 TRUE TRUE FALSE FALSE Element is taken TRUE TRUE FALSE FALSE TRUE TRUE FALSE FALSE TRUE TRUE TRUE TRUE B[4] = 2 Element is taken Q[i-1][j-B[i]] or Q[i-1][j]
