Scribd
Upload
5 views

Lecture22 Slides

Uploaded by

deepbhai866
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views

Lecture22 Slides

Uploaded by

deepbhai866
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

The Knapsack Cryptosystem

Ryan C. Daileda

Trinity University

Number Theory

Daileda The Knapsack Cryptosystem


Introduction

Today we will briefly consider a public key cryptosystem whose


security rests on the difficulty in solving a certain combinatorial
problem.

The idea is to encode messages using a scrambled “base” system


in such a way that only the intended recipient can retrieve the
message’s “digits” (bits).

Although no longer utilized in practice, this cryptosystem is


nonetheless another interesting example.

Daileda The Knapsack Cryptosystem


Knapsack Problems

Suppose we are given a “knapsack” of volume V ∈ N, and


“objects” of volume a1 , a2 , . . . , ar ∈ N.

The knapsack problem asks whether or not it it possible to choose


a subset of the ai whose total volume is V .

That is, do there exist ǫi ∈ {0, 1} so that

V = ǫ1 a 1 + ǫ2 a 2 + · · · + ǫr a r ?

In general, this is an extremely difficult question to answer.

Daileda The Knapsack Cryptosystem


Example

Suppose that a1 = 2, a2 = 5, a3 = 6, a4 = 9, a5 = 13.


If V = 20, the knapsack problem has a solution, since

20 = 0 · 2 + 1 · 5 + 1 · 6 + 1 · 9 + 0 · 13.

However, if V = 23, there is no solution to the knapsack problem.


To see this, notice that the sum of the first 4 terms is

2 + 5 + 6 + 9 = 22,

which means that if there is a solution, then ǫ5 = 1.


But then we must be able to choose from 2, 5, 6 and 9 and get a
sum of 10, which is clearly impossible.
Daileda The Knapsack Cryptosystem
Superincreasing Sequences

Definition
We say that a sequence {ai } is superincreasing if

an > an−1 + an−2 + · · · + a1

for all n ≥ 2.

Examples.
The sequence a1 = 3, a2 = 4, a3 = 10, a4 = 20 is
superincreasing.
The sequence a1 = 1, a2 = 2, a3 = 4, a4 = 8, a5 = 16 is
superincreasing.
More generally, given b ≥ 2, the sequence a1 = 1, a2 = b,
a3 = b 2 , . . . , ai = b i −1 , . . . , ar = b r −1 is superincreasing.
Daileda The Knapsack Cryptosystem
An important feature of solutions to knapsack problems involving
superincreasing sequences is that they are unique.

Theorem 1
Let {ai } ⊂ N be a superincreasing sequence. If ǫi , δi ∈ {0, 1} and
r
X r
X
ǫi a i = δi ai ,
i =1 i =1

then ǫi = δi for all i .

Proof. We induct on r . If r = 1, the result is trivial, since


ǫ1 a1 = δ1 a1 implies ǫ1 = δ1 , as a1 6= 0.

Daileda The Knapsack Cryptosystem


Now let r > 1 and assume the result for all superincreasing
sequences of length < r .
Then
X X X X
ǫi a i = δi ai ⇒ |ǫr − δr | ar = (δr − ǫr )ai ≤ ai < ar .
i ≤r i ≤r i <r i <r

Since |ǫr − δr | ≤ 1, this implies that ǫr = δr . Thus


X X
ǫi a i = δi ai ,
i <r i <r

and ǫi = δi for i < r by the inductive hypothesis.


Therefore ǫi = δi for all i ≤ r . This completes the inductive step,
and the proof.

Daileda The Knapsack Cryptosystem


It is relatively easy to solve a knapsack problem involving a
superincreasing sequence {ai }.
Suppose we are given V ∈ N and we want to determine ǫi ∈ {0, 1}
so that
Xr
V = ǫi a i .
i =1

Let n be the largest index so that an ≤ V . Then ai > V , and


hence ǫi = 0, for i > n.
Furthermore, X
ai < an ≤ V ,
i <n

which means that we can’t have ǫn = 0. Thus ǫn = 1.


Now recursively repeat this procedure for V − an .

Daileda The Knapsack Cryptosystem


Example

Consider the superincreasing sequence a1 = 3, a2 = 4, a3 = 10,


a4 = 20, a5 = 42.

To solve the knapsack problem

55 = 3ǫ1 + 4ǫ2 + 10ǫ3 + 20ǫ4 + 42ǫ5 ,

we start by observing 42 < 55, so that we must have ǫ5 = 1.

We then consider 55 − 42 = 7. Now we have a2 < 7 < a3 , so


ǫ4 = ǫ3 = 0 and ǫ2 = 1.

Finally we have a1 = 3 = 7 − 4, so that ǫ1 = 1. Therefore

55 = 3 · 1 + 4 · 1 + 10 · 0 + 20 · 0 + 42 · 1.

Daileda The Knapsack Cryptosystem


Knapsack Encryption

A public key cryptosystem utilizing the knapsack problem was


developed by Merkle and Hellman in 1978.

Every user:
1. Chooses a superincreasing sequence {ai }ri=1 , a modulus
m > 2ar , and a multiplier a with (a, m) = 1.

2. Computes bi ≡ aai (mod m).

3. Publishes the encryption key KE = {bi }.

4. Keeps {ai }ri=1 , m and a secret.

Daileda The Knapsack Cryptosystem


To encrypt a message to the individual with public key
KE = {bi }ri=1 , the sender first converts the plaintext into binary
blocks of length r .

A given binary block P = ǫ1 ǫ2 · · · ǫr is converted to the ciphertext


block
X r
C = ǫ i bi .
i =1

Because the transformed sequence {bi } is no longer


superincreasing, determining the ǫi from C is “hard” for an
eavesdropper, even given the sequence {bi }.

Daileda The Knapsack Cryptosystem


Unpacking the Knapsack
The decryption key is KD = ({ai }, m, b), where b satisfies ab ≡ 1
(mod m), which is easily computed from a and m using the EA.
The message recipient computes S ≡ bC (mod m), with
0 ≤ S < m.
Notice that
r
X r
X r
X
S ≡ bC ≡ ǫi bbi ≡ ǫi baai ≡ ǫi ai (mod m).
i =1 i =1 i =1

Because {ai } is superincreasing,


r
X
0≤ ǫi ai < ar + ar = 2ar < m.
i =1

Daileda The Knapsack Cryptosystem


r
X
It follows that S = ǫi ai , and the recipient can now compute
i =1
the plaintext P = ǫ1 ǫ2 · · · ǫr using the procedure described earlier.

Example 1
Encrypt the plaintext block 01001 using the superincreasing
sequence {3, 4, 10, 20, 42} with modulus m = 90 and multiplier
a = 17.

Solution. We first multiply our sequence by 17 (modulo 90),


obtaining {51, 68, 80, 70, 84}.

Our ciphertext is then C = 1 · 68 + 1 · 84 = 152 .

Daileda The Knapsack Cryptosystem


To decrypt we compute 17−1 ≡ 53 (mod 90) then multiply:

53 · C = 53 · 152 ≡ 62 · 53 ≡ 46 (mod 90)

Since 46 = 1 · 4 + 1 · 42, we recover the plaintext 01001.

Remark. While certainly interesting, the Merkle-Hellman knapsack


cryptosystem (and its variants) were proven to be insecure during
the 1980s.

It turns out that the transformation bi ≡ aai (mod m) doesn’t


sufficiently “disguise” the superincreasing nature of {ai }.

Daileda The Knapsack Cryptosystem

You might also like