An Implementation of the Chor-Rivest Knapsack Type Public Key Cryptosystem

Rochester Institute of Technology

RIT Scholar Works Theses

Thesis/Dissertation Collections

1986

An Implementation of the Chor-Rivest Knapsack Type Public Key Cryptosystem Robert Jr T. Salamone

Follow this and additional works at: http://scholarworks.rit.edu/theses Recommended Citation Salamone, Robert Jr T., "An Implementation of the Chor-Rivest Knapsack Type Public Key Cryptosystem" (1986). Thesis. Rochester Institute of Technology. Accessed from

This Thesis is brought to you for free and open access by the Thesis/Dissertation Collections at RIT Scholar Works. It has been accepted for inclusion in Theses by an authorized administrator of RIT Scholar Works. For more information, please contact [email protected].

Rochester Institute of Technology School of Computer Science and Technology

An Implementation of the Chor-Rivest Knapsack Type Public Key Cryptosystem

by Richard Thomas Salamone. Jr.

December 16, 1986

A thesis, submitted to The Faculty of the School of Computer Science and Technology, in partial fulfillment of the requirements for the degree of Master of Science in Computer Science.

Approved By:

Dr. Donald L. KIeher (Advisor)

Dr. Stanislaw P. Radziszowski

Dr. John L. Ellis

Title

of

Thesis: An Implementation

of

the Chor-Rivest Knapsack Type Public

Key

Cryptosystem

I Richard Thomas

R.I.T.,

Salamone,

Jr.

to reproduce my thesis in

cial use or profit.

hereby

grant permission to the

whole or

in

part.

Any

Wallace Memorial Library,

reproduction will not

be for

of

commer

Abstract

The Chor-Rivest cryptographers

Ben Zion Chor

tions to

Bose able

create

and

the knapsack are done

Chowla

[Bose62].

supplies a method of

Not only does

immune to the low density Odlyzko

An implementation

by fixing

h

=24.

run

of

knapsack

finite

over

public

algebraic

key

systems

fields.

An

in that

computa

interesting

result of

constructing higher densities than previously

levied

against

this cryptosystem

a pair of

parameters, p

Chor has implemented This thesis

time.

MIT

by

proposed

rate

arise, but the

attain

new system so

its predecessors, notably those

far is

of Lagarias-

In

so

is really h

and

an

instance

at the

,

of

the

outset.

general

These

scheme, dis

parameters then

throughout the life of the implementation (which supports a community of

remain constant

users).

earlier

increased information

attacks

first

cryptosystem

Radziszowski-Kreher [Laga85, Radz86].

and

tinguished

an

key

public

his doctoral thesis [Chor85]. Derived from the knapsack

differs from

cryptosystem

a

Ronald Rivest [Chor84]. More recently Chor has imple

and

mented the cryptosystem as part of

problem, this

is

cryptosystem

aspires

doing,

one

such

instance

to extend Chor's

a cryptanalyst

is

work

afforded

of

by

his cryptosystem,

admitting p

the means to

h

and

mimic

where

p

=197

as variable

the

action of

and

inputs

at

arbitrary

implementations.

A high degree

few

restrictions on

ity incurs needed

to

a

high

of success

the choice

cost

has been

achieved with respect to this goal.

of parameters

that may be selected.

in efficiency; up to thirty hours

generate a single

key

pair

in the desired

range

of

(p

Unfortunately

(VAX1 1-780) =

243

There

and

h

are

this

processor

=18).

only

a

general

time are

Table

of

Contents

0. ABSTRACT

1. INTRODUCTION AND BACKGROUND 1.1 Overview 1.2 Previous Work 1.2.1 General Background 1.2.2 Public Key Cryptosystems

1.2.3 The Knapsack Problem in Cryptography 1.2.4 Recent Developments in Knapsack Cryptology 1.3 Theoretical and Conceptual Development 1.3.1 Galois Fields 1.3.1.1 Definitions and Theorems 1.3.1.2 Representation of a Galois Field 1.3.1.3 Primitive Elements 1.3.1.4 Discrete Logarithms 1.3.1.5 Construction of a Galois Field 1.3.1.6 Field Extensions 1.3.2 The Bose-Chowla Theorem

2. PROJECT DESCRIPTION 2.1 How the Chor-Rivest Cryptosystem Works 2.1.1 Key Generation 2.1.2 Encryption 2.1.3 Decryption 2.2 Functional Specification 2.2.1 Design Criteria 2.2.2 Functions Performed 2.2.3 Limitations and Restrictions 2.2.4 User Inputs 2.2.5 User Outputs 2.3 Changes to Original Scope

IMPLEMENTATION DETAILS

3.1

Architectural Design

3.2 Naming Conventions 3.3 Data Structures and Global Variables

1

2 2 5 9 11 14 14 14

16 17 17 18 19 20

23 23 23 24 24 26 26 27 28

28 29 29

31 31 32

33

4. ALGORITHM DESIGN AND ANALYSIS 4.1 Polynomial Manipulation 4.1.1 Multiplication of Field Elements 4.1.2 Exponentiation of Polynomials

4.1.3 Evaluation of Polynomials 4.1.4 Generation of Random Polynomials 4.2 Construction of Galois Fields 4.3 Discrete Logarithms

5. SYSTEM PERFORMANCE 5.1 Security of the Chor-Rivest Cryptosystem 5.2 Efficiency of the Chorivest Cryptosystem 5.2.1 Time Requirements 5.2.2 Space Requirements 5.2.3 Information Rate

37 37 37

38 39 40 41

43

48 49 50 50 51 51

6. CONCLUSIONS 6.1 Problems Encountered and Solved 6.2 Discrepancies and Shortcomings of the System 6.3 Recommendations for Future Work

53

Bibliography

57

Appendix A Appendix B Appendix C

Appendix D

-

-

-

-

53 54 55

GF(64)

59

Example Chor-Rivest Knapsack

60

Makefile for the System

62

User's Manual

64

in

CHAPTER

Introduction

and

1

Background

1. Overview A Public Key Cryptosystem is implemented in

exchange secret

A

tion.

Fundamentally

system.

operating

information

key

public

correspondents

(encrypted)

do

such

that

cryptosystem

not

exchange

communication.

cryptosystem

a

any

along

This information is with

the

receiver

recover

the

contact, it generation

The

recipient.

may

call

With a

second

original message.

prerequisite

other

this

service

provide

sender consults a

public

key)

The

on

users

UNIXf

the

a

to

means

system

provided

not

added

directory

is unintelligible,

key)

reci

facility)

message,

deciphering facility)

users

in

except to

and the garbled

(the

necessary for the

desired

(the enciphering

facility

facility

The

of all participants

associated with the

private

bonus:

keys, before establishing

or

resultant message

information (his

an

with

information,

system provided

While it is

to

to have had previous

that the keys be precomputed for each participant (in the

key

facility).

particular

cryptosystem

Ronald Rivest in 1984 [Chor84]. on

to a

the message to be disguised.

the intended the

passed

this

secret

the system and obtains the information (the

pient.

should

run

eavesdroppers cannot understand the communica

provides

Rather,

to

software

the knapsack

scheme

as

fUNIX is

a

problem

implemented

was

In this scheme,

proposed

encryption and

from complexity theory (see

the Chor-Rivest Knapsack Type Public

trademark

of

Bell Laboratories.

by

1.2.3).

Ben-Zion Chor decryption

Thus

are

and

based

we shall refer

Key Cryptosystem,

or

to

the Chor-

Rivest

for

system

As

short.

a public

provides the above

system.

Instead

key

facilities. However,

we provide a

specifically, there has been

research at

breaking knapsack

has

been broken but there is

to include this scheme.

system

our goal was not

tool for cryptanalysts who

applied to

not yet

Chor-Rivest

cryptosystem our

based

develop

to

Technology

of

some confidence that this research

This implementation

will

which

The Chor-Rivest

[Radz86].

cryptosystems

a secure public

may be

key

More

to break the system.

wish

Rochester Institute

implementation naturally

may be system

extended

the data necessary for this

provide

task.

Because attacks,

based

we

provide

flexibility is

simplifies

for

system

of

required

the specific field used

defining

the implementation

without

arbitrary Chor-Rivest implementations.

of

the

or modification of

directory

ject. Hence,

all of

although we provide all

implementation

the

Furthermore,

for

different

cryptanalytic

system

would

facilities.

integrity

of

message

functions

the

system

results.

passing

scheme

fix

try his

facilities

Alternatively,

is

certain

This greatly

the system.

the cryptanalyst may alter to

important intermediate

of users and protocols

user oriented system

by

a given

compromising the

which

with

In particular, the Chor-Rivest

the system.

these same parameters are variables,

disclosure

experimentation

in finite fields. Typically,

on arithmetic

parameters

a

Here,

attack on

allow

easy

maintenance

are not a concern of this pro

as prescribed

this is not a ready to install

[Chor84].

2. Previous Work

2.1. General Background

In this thesis

we

are

primarily interested in

terminology

overview of

the techniques and

prerequisite

to the ensuing discussion.

public

of classical

The field

of

key

cryptology.

However

an

(or conventional) cryptology is

cryptology embraces the disciplines

of

cryptography

and

while cryptanalysis

of

disguising

cryptanalysis

is

Cryptography is

.

breaking

concerned with

a message such

(hopefully)

that

designing

the

Intuitively,

ciphers.

only the intended

of

cipher

systems,

is

a cipher

a means

recipient can recover

its

meaning.

Cryptology has B.C.)

[Beke82].

that it was

of

(1743-1826)

Thus cryptology is

very old science, but it

a

are the set of

text, by applying

a

cipher

system

messages, the

(also

one of

These

nal message.

associated

with

deduce the often

each

by trying

proceeds

information, ful

and

key

prior

the

the 1940's

of

by

ciphertext

a

of

better yet, the

always assumed

the

decryption

three-tuple:

called

and a set

the

key

used.

That

is,

given

cryptanalyst

the

The

the

origi

A

respectively.

sender

To

attain

require

system useless.

that

this goal, the

key and

information is

a

the secret

way to

information. privileged

this tact a partially success

only for

a subset of

the message

compromised.

that the cryptanalyst knows the entire cipher system, not the particular

avail

cryptanalyst will

progressively less

Using

works

only publicly

hopes to find

system given much or all of

an attack

transformations, but

plain

ciphertext.

recover

transformations, thus

polishing his technique to

Perhaps

message, yield

a

messages),

the transformation to

ciphertext, the

ultimately rendering the

set of

of

as

to exchanging messages.

space or when certain additional secret

ing

(or

disguises

to break the system.

to break the

attack often results.

It is

sender

the set

of

element

a portion

plaintext or

begin

He then

was not until

cryptosystem)

operations are called encryption and

cryptanalyst attempts

information

a

the transformations to the message to

receiver must agree upon a

able

called

set of cryptograms

the message performs the inverse

recipient of

The

Julius Caesar (100-44

are notable examples of prominent cryptogra

invertible transformations [Shan49]. The

is

history.

formalized.

Shannon defines These

practiced throughout much of

Thomas Jefferson

and

phers

been

key

used.

We may then

includ

categorize

into three levels

cryptanalysis

occurs when the

interceptor has only

text only attack.

A

stronger

attack, the known

is the

Here,

we can assess

plaintext

with

its

the security

encrypt messages of

ditionally

secure

the one-time

[Diff76].

In

A

is the only unconditionally

pad

only if

results

general

approaches are undesirable

ally

practical

secure.

(economic) Here the

several

it is necessary to

use

throughout the

reasons we are

even

is

So

considerably less

There security.

considered

remainder of

while a system

Perhaps the

M is the

rather

secure

subjected.

in

is

called uncon

in

A

system

common use.

for

exist

given

a

keys (as in the

that are

computational

one

These

Therefore,

requirements.

systems

its

a measure of

unconditional security.

if the

this paper,

will mean

of a system relative

may be

factors most

of

computation

cost

"computationally

to the levels

secure under a ciphertext

import in the

important

of

cryp

secure".

of attack

We

to which

it

only attack, it may be

of

evaluation of cipher systems

these

is the information

rate

R

in

addition

provided

by

to

a

[Chor84, Simm79]: R

where

solutions

time

the

secure under a chosen plaintext attack.

are other

particular system

interested

intercep

though the system might not resist an unbounded attack.

may further classify the security will succumb.

This is

inordinately long

cost or

cipher-

own choosing.

cipher system

meaningful

due to the increased

system

tanalysis is prohibitive,

Secure,

may be

secure cipher system

time pad) or extremely complicated algorithms to attain

for

his

a

Finally,

can withstand cryptanalysis with unlimited computation.

Unconditional security cipher

This is

occurs when the

of a given cryptosystem.

to the various levels of cryptanalytic attacks.

called

weakest attack

plaintext translation.

resilience

if it

attack,

strongest attack to which a cipher system

the cryptanalyst has the means to

Now

The

[Diff76].

system

encrypted messages to work with.

tor has at least one encrypted message along chosen plaintext attack

the

of attack upon

message space and

=

\og2\M\/N

N is the

number of

bits in the

ciphertext.

Thus the

information are

rate

is

an

efficiency

many times longer than the

secure

system

having

a

tioned above, requires a this is

impractical in

If

concern:

original

message,

higher information

key

long

as

one

rate.

as all of

is secure, but

a system

may

For

to choose a slightly less

want

instance,

the messages to

encrypted messages

the one-time pad

ever

be

encrypted.

men

Clearly

most applications!

2.2. Public Key Cryptosystems In 1976 Diffie

key

public

and

Hellman

that the communicants do

key is

The outstanding feature

[Diff76].

encryption

sparked a revolution

keys

not exchange

associated with each user

in

a public

prior

in cryptology of

this class

their idea for

with

of cipher systems

is

Instead,

a

to exchanging messages.

directory.

In this

section we outline

how

this is accomplished.

Recall that in

conventional

then hold in secret the key.

upon

tion functions are closely

is easy to deduce

related

systems, the

cipher

sender

and

This is necessary because the to each other.

Such

the enciphering transformation

a scheme

knowing

the

receiver

must

encryption and

is termed

agree

decryp

symmetric

deciphering

if it

transforma

tion and vice versa [Simm79].

If

on

encryption

keys, is

not

function

to deduce the decryption function

In

an asymmetric scheme results.

asymmetric schemes

one associated with encryption and the other associated with

feasible to

the keys is

posted

in

Thus

revealed.

a public

'By difficult

we

key from

compute one

encryption/decryption

is

difficult1

the other hand it is

key

a public

pair

directory

mean

computationally

the

there are two

decryption.

Since it

the other, there is no loss in security if one of

key

system

is found for

along

knowing

with

is

an

asymmetric scheme

each participant's

his name, but his

infeasible,

enciphering

in

which

an

(public) key

deciphering (private) key is

given modern equipment

and

technology.

held in

To

secret.

send messages one

encrypts the message

To

fying

using it. The

construct a public

key

the above constraint.

from complexity theory

by

the solution.

If

instance

lem;

of

of

For

An

our

complexity

into

of

pairs satis

computationally difficult

We

key.

private

key

problem

digress briefly to introduce

will

is

B".2

A

explain what we mean

problem

parameters and

is

a general question

stating the

the input parameters then

a

detailed

procedure

individual problems, then

one of the several equivalence classes

properties

we

for solving

algorithms are equivalent to computer programs.

purposes,

are placed

problem

algorithm

a

using his

matched

that attempts to

we are given all of

the general problem.

message

then

key

public

to us.

specificing its input

is to determine the complexity

taken

useful

recipient's

way to find

choosing

a collection of results

may be described

required

be

which will

say "problem A is harder than

when we

deciphers the

system one needs a

by

the

obtains

the basis of the system.

Complexity Theory is

which

recipient

This is done

as

terms from this field

some

simply

The

have

an

a prob

approach

problems with similar

constituting the

com

plexity hierarchy.

We classes.

putes

describe the

now

Say / is

/ (x )

on

to compute f(x).

Ta(n

)

of a on

function

some

input

x

).

This

input

criteria

We

count

in

a polynomial

polynomial

2No following

)

the

called

is

an algorithm that computes

number of

"primitive

equivalence

/ (i.e.

a(x

)

instructions"

required

the running time RT(a,x).

com

by

a

Now the complexity

)

=

such

max{RT(a, that Ta(n

)

x

) : size

< p

of

x

(n ) for

is

n

all n

,

}. we

say that

a computes

/

time and write:

attempt

results

p (n

a

predominant

is:

TJji If there is

is

value

of size n

and

for membership in the

is

made

largely

to be

follow

rigorous

Garey

and

in this

discourse;

Johnson [Gare79].

only

an

intuitive understanding is

necessary.

The

Ta(n) The

P

set

class

{all deterministic

=

If

of problems.

then

is

a

the other hand

on

EXP encompasses

EXP is the class NP

Exp,

and

Finally, in

which are

{all

=

P

c

the set

TJji)

more

B.

=

difficult

is

r.A

time problems} is the resulting

Exp?

some sense

that solves

rithm

polynomial

0(p(n)).

called an exponential time algorithm and

time problems).

CJVPC

=

NP -complete if

and

only if

1) A e NP, 2) for every It is

B e

members of

public

key

this class

cryptosystems4

Notice that the

puting

be

with

This

^There we

Consider

are

also

are able

has

not yet

a problem

X

which

is

a nondeterministic algorithm

is

X

which can

crucial

an

to

since we

of

infinite

exhibit

be

solved on a

computer,

worst case

a member of

X

on

any known

to solve

even

NP.

X,

In

com

there may

for very large input.

to our application, providing a means to construct matched

number

only

also proposed

been generally

the basis of

describes the

have

instances

4Wagner idea has

classification of problems presented above

But

use as

[Diff76].

we could not expect to solve

observation

However

that have been suggested for

sufficiently large input

machine.

several

of problems

of a given problem.

complexity general,

there is a polynomial-time transformation from B to A.

NP,

the

of

somewhat

use

accepted

complexity

levels

above

EXP

artificial problems as witnesses

of undecidable

[Wagn84]

.

problems

in the complexity hierarchy: to this

from the theory

hierarchy [Lewi8l].

of

computability, but this

public/private

The

key

pairs.

following

theory for

terms

applications to public

easy to compute if there is putes

/.

defined by Diffie

were

Otherwise, / is hard

hard to compute, then b is

If

a

augment

We say that

in the complexity

algorithm a

to compute.

said

Hellman to

cryptography [Diff76].

key

known

a

and

Finally,

which com

compute and

function t is

a

/ is

function

P

class

bijection b is easy to

to be a one way function.

a

complexity

b~x

a

is

trap

door function if

(1)

/is easy to compute;

(2)

there

exists

function, To

the

sion of

to

door function is

as the

general

constructed

in

embed a trapdoor

the

public

of

solved with

a given problem

key back

problem given

will

be

subject

Shortly proposed.

[Merk78].

His only

one

way

defines

by

a public

has two To

key

the design.

of the problem

key. In

One

Notice that

by

This

ver

is then dis

other words a

option

this attack, the

is to directly

con

Thus the technique

exhaustive search over a

other option

is

problem

trap

used

to

scheme.

options.

resist

this

NP -complete)

solve

the

is to try to

con

cryptographer must

prohibitively large general

their very nature, public

set

NP -complete

key

systems

chosen plaintext attack.

to

after

One

chosen problem.

to the private key.

the public key.

by

the

public

of

about

This instance

key.

cryptanalyst

insure that the only way to do this is of transformations.

a

(preferably in

information

problem, hence the on

in NP

An instance

the system.

private

based

To break the system, the vert

basis

becomes the

to be the

is

/

which

t~x

deterministicly

problem

appear

information (the key) without is easy to compute.

key

pairs then we select a problem

in P

not

that may be

strued

side

given the

key

generate

believed to be

guised

some

but

Diffie

was

The other,

and

the

set

Hellman introduced the

Merkle-Hellman

forth

system

by Rivest, Shamir

8

and

public

based

key idea on

the

two schemes were

knapsack

problem

Adleman (called the RSA method)

is based

the

on

difficulty

of

factoring

generally believed to be the best

being

the first

is

schemes

key

public

implemented in

an

improvements. We

[Rive78]. The RSA

LSI chip [Bric83]. The models

early

and

history

method

has the honor

of

is of

knapsack based

have been broken leading to

these developments in the next section,

shall examine

Chor-Rivest knapsack

the

with

numbers

technique in existence,

much more complicated as several

subsequent

minating

one

very large

cul

scheme.

2.3. The Knapsack Problem in Cryptography The knapsack theory.

Given

knapsack our

a

knapsack

problem

we

purposes,

problem

is

a

with

known NP -complete

well

very

fixed capacity

and several

problem

items

from complexity

is to determine how to completely fill the knapsack (if are

actually

concerned

with

the closely

weights, the

of various

possible).

For

problem

related subset sum

[Gare79, Radz86]: The Subset Sum Problem Given a vector of positive integers find, if it exists, a (0,l)-vector x*

=

a*

{aia2, (x1?x2, =

,an) ,xn)

integer M

and a positive

such

that

n

2

a,-

Xi

=

M.

1=1

To

a*

adapt this problem to

be

F

solved

=

a*

of

(b1,b2,

by

for

easily

we pick an

different

M's,

integer,

v

,

which

is relatively

b The

resultant random-looking

comprise

encrypt

f

=

the

a

(Pi,P2,

private

message, "

-

"

>/>)>

key P, tnen

This

merely

perform

is

we

by

performing

(mod

process

its

system

giving

a modular multiplication

modulus,

m :

m).

published as

take

the

scramble

prime with respect to the

a*-v

F,

vector,

[Merk78].

we

=

such that the subset sum problem can

then

An easy way to do this is

,bn).

some

cryptology

is

called

binary

the computation:

the public the

key

key

while

a*,

m

and v

generation phase.

representation

to

be

a

To

vector

C

=

Eft*.-, =i

where

C is the

length

of

F,

we

ciphertext to

be

merely break the message into blocks

Decryption is only slightly prime, there exists

N

C

=

Note that if the

sent.

more

v_1

modulo

-v_1, then solve the easy

such

m

of

that

vv_1

length

n

Because

complicated.

=

length

message

1 (mod

\~p |

exceeds

the

.

and

v

m

Thus

m).

are

relatively can

we

find

knapsack:

N

Y,Pi-ai,

=

=i

to

recover

the

The

binary

collection

message

f.

the

of

together define the system.

key

generation,

In the description above,

to create a*.

The

For

instance,

the Merkle-Hellman

that

is

we

identifies the type

method chosen

of

a*

that

system requires

decryption

and

encryption,

have

avoided

knapsack

be

a

algorithms

the topic

of

how

system we are using.

superincreasing sequence,

t-i a,-

fr

J] ai

>

'

2, 3,

=

,

n.

3=1

This

was

the first and simplest knapsack

A

system proposed.

solution

is found by

suc

cessive subtractions.

An important

measure of a

knapsack

system

is its density:

Knapsack

The

Density density d (a*) of a

This property

instance,

For 5*

=

represents

can

be

ments of 5*.

the

Both T

represented

a*

(a u a 2,

=

the information

consider

(45 9, 16, 32, 64).

in T

knapsack

in

and

six

bits

This relationship is

an ) is d

the system

rate of

knapsack

t have

,

vectors

reflected

bits

=

/ log2 (max

n

at ).

(19, 14, 31, 15,26)

25, but

are required

in the densities, d (T)

10

=

[Chor84, Laga85, Radz86].

T

an average weight of

whereas seven

(a*)

o

the weights

to represent the ele

>

=

each of

and

d (?)

=

.

/

There is

also a

relationship between the

apparent

in later

knapsacks

density

In this context

sections.

are

generally low

density

2.4. Recent Developments in Knapsack

Having described knapsack

tially,

each

systems

the

in specific,

however,

now

since

an

subset

must

of

high

notice that

be large

relative

will

become

low density

and

superincreasing to

n

.

Cryptology

we now review their

sum

in terms

key

properties of public

which

problem,

improvements in knapsack design! The of

For

its security that

and

time a knapsack system has been proposed,

in solving the

advances

important

knapsack

we will speak

the cutoff is roughly 1.0.

where

knapsacks like T

and

of a

cryptosystems

in

historical development.

its

has

cryptanalysis

in turn has

current state of affairs

caused

general

Essen

prompted

cryptographic

finds the ball in the

court

the cryptanalysts due to the appearance of the Chor-Rivest system.

The Merkle-Hellman knapsack (described above) 1978

as a

direct

result of

tion, the security

Merkle's doctoral

of trapdoor

and

Zipple

in the key

strengthened

iteration.

single-iteration method

multiple-iteration

Shamir,

although our example showed

phase,

this process

In 1982 Shamir found

it

was

several

realized

times

[Sham82b].

Brickell

soon

the

different

discovered

the cryp

system could

one modular mul

system

v

could

and m

be

at each

completely brake the

a technique to

break the

technique [Bric83].

working at the Weizmann Institute in

nature

a

with

that

by

the inventors of the

only

a polynomial time algorithm to

trapdoor was a superincreasing sequence

creasing

of

Stanford in

this introduc

that if the modulus m were known the

showed

generation

by iterating

at

regarded with suspicion

Indeed, in 1978 Adi Shamir (one

certainly be broken [Bric83]. Thus tiplication

developed

[Merk78, Merk82]. Since

knapsacks have been

tographic community [Bric83].

RSA scheme)

work

was

of

in his

the trapdoor imposes too

11

Israel,

attack.

used

the knowledge that the

It turns

much structure

on

out that

the superin

the system.

The

wor-

khorse in this

lattice [Lens83]. For

vectors.

is the Lovasz

attack

The

goal of

algorithm

in

basis

which

this operation is to find the basis

low-density knapsacks,

the shortest

vector

is

reduction

the shortest basis

with

found by the

performed on a

algorithm contains

the solution to the subset sum problem.

Coincidently lished

an

improved knapsack

sack need not

density.

a subset of

Such rithm

be

is

newer

attacks appeared

in the

Adleman (again

method

these

not guaranteed to

find the

fame)

vector

was

it, including

solved with

At this the case for

be

closer

together, yielding

a

knap higher

via modular multiplication of

The Merkle-Hellman knapsacks this improved

an attack on

as

shortest vector

system would

in the lattice it so

called

L3

several reasons.

important,

definition

all

reason

of

used

This

to

to break the new Shamir system

an

algorithm

improvement

improves

density (density

<

upon

on

the Lovasz

its

predecessor

0.6) knapsacks

could

be

the Shamir scheme.

point one might assume

to solve

reduction algorithm came closer

Algorithm,

many low

and

be

not appear to

due to its very low density.

system

if the basis could

the Lovasz algo

in the lattice. This does

the Merkle-Hellman noted that

Unfortunately,

expected.

As

of

that knapsack systems were doomed.

1982,

the

L3

problem; This happened only recently

an algorithm

our

thus

introduced [Lens82].

in that it is slightly faster

more

can

the trapdoor

new scheme

the keys are formed

very shortly

Also in 1982, the

above,

subset sum

the weights

knapsacks,

attack on

RSA

of

the shortest

[Adle83].

details,

[Sham82a]. In the

predecessors.

a problem

finding

so

the Merkle-Hellman scheme, Shamir pub

of

necessarily superincreasing) knapsacks.

not

apply to its

system

be superincreasing,

Without going into

easy (but

form

the cryptanalysis

with

sufficiently low

for

security.

not

dismissing

density

algorithm

when

Lagarias

problems

knapsack based

Recall that for

12

a

public

had

key

not

been

and

[Laga85].

was not

applied to the

Odlyzko

used

Another,

cryptosystems

system

This

perhaps

has to do

to work

it

it in

with

must

be

infeasible to break plexity, thus

a

the system.

aforementioned attacks

sufficiently large knapsack (i.e.

broken [Bric83].

The final

dismissed is (you

guessed

density

The

high

attacks with

and

it!),

most

important

density knapsacks.

in solving the

lattice basis

reduction

avoid

of

to

sacks

L3

[Radz86].

technique

faster.

the authors call weight

reduction operation.

of

than 0.6.

knapsack

density less

deliberately foil

This is the Chor-Rivest

system we must explore a

of

Rochester Institute

at

Although the

L3,

Another

these low

[Chor84].

scheme

very

of

develop

recent

Technology,

core of their algorithm

several enhancements are added.

major

improvement in this

Due to these

than 1.0 while

Z,3

improvements, works

this algorithm

any

again

Because they algorithm runs

is

a tech

knap

can solve

with

density less

assumption about

how the

was constructed.

present

time, the Chor-Rivest

rithm, producing knapsacks report

with

scheme appears

density

exceeding 1.0.

to be secure against this algo

However, Radziszowski

that further gains are to be had from their algorithm,

point of successful attack on

the Chor-Rivest scheme [Radz86a].

hopefully

This thesis is

limited

Prior to the

version produced

implementation

vectors

current

having

produces

weight

24.

by

project, the only implementation

Chor himself

knapsacks

The

of

as part of

197 elements,

general scheme

13

is

not

of

a sophis

Chor-Rivest,

cryp-

was

his doctoral thesis [Chor85]. with

a message

space

and

to the

ticated implementation of the Chor-Rivest scheme expressly designed to aid these

tanalysts.

the

to be found in the

reliably for knapsacks

neither algorithm makes

proposed

is

algorithm

reduction which causes shorter vectors

It is noteworthy that

At the

Kreher

feasibly

not

that knapsacks have not been

the multiprecision operations of the former method, their

an order of magnitude

basis

Kreher, based

and

an algorithm superior

nique

reason

time com

subset sum problem.

Radziszowski

many

polynomial

hundred weights) is

has been devised to

a system

Before proceeding to this latest knapsack ment

several

have

of

a

His

binary

limited to these parameters, there

are

many

The

suitable possibilities.

suggested parameters, not only 197 and mathematical

background

3. Theoretical

A

tem, providing the

orient

them.

the

Finally,

theorem

Rivest

will

exploit

Chowla is the

and

all of

the

chapter provides

the

knapsack

cryptosystem.

become We

Chor-Rivest

cornerstone of the

algebraic structures called

to Galois

fields,

apparent

provide a

in

The

proved.

2

chapter

where

example of

running

(summarized in

cryptosys

However this

Galois fields.

In this

con

section we

then we examine how to represent and manipulate

the Bose-Chowla theorem is

current problem

this

for nearly

to construct dense knapsacks [Bose62].

in finite

reader

it.

remainder of

needed to understand this most recent

means

struction takes place

first

24. The

works

Conceptual Development

and

from Bose

result

implementation

current

appendices

A

and

we

cryptographic usefulness of this

show

in detail how Chor

these concepts as

B for easy

they apply

and

to the

reference).

3.1. Galois Fields

This treatment

ing

of

Galois Fields is

several useful results

source

for

proof of

3.1.1. Definitions

Definition 1:

A

neither rigorous nor

exhaustive,

from Gilbert [Gilb76]. The interested

we

is

reader

and

to the

Theorems

Ring

ring (R, +, ) is a set R, together with two binary R satisfying the following axioms. For any a, b, c e R,

a + (b (i) associativity of addition (a + b) + c b +a; (ii) commutativity of addition a +b (iii) existence of additive identity there exists =

-

-

such that a +

(iv)

0

existence

=

of

a

+c

operations +

);

=

-

0

R

called

the

zero

;

additive

inverse

-

there

exists

-a

0; +(-a) a-(b c ); (v) associativity of multiplication (a b ) c b -a; (vi) commutativity of multiplication a b (vii) existence of multiplicative identity there exists 1

a

stat

the theorems.

Commutative

on

by

referred

commutative

and

begin

e

R

such

that

=

=

=

-

-

*

14

e R

such

that

1

a

=

a;

(viii) (b

a

distributivity

mutual

+c

)

(b

a -b + a -c and

=

of

+c

)

a

multiplication =

b-a

and

addition

+c-a.

Definition 2: Field A field is

a commutative

following

additional

(ix)

Definition 3: Polynomial

-a-1

=

R[x]

=

{a0 + axx

x

each a e

+

from the

with coefficients

a2x2

+

R there

a-1

exists

Yiaix'

=

commutative

ring R is

+atlxn:aieR,n>0}. called

the

where addition and multiplication of

P(x)

anc*

q(x)

=

polynomial ring with the polynomials

coeffi

YjbiX1

i=0

t'=0

are

for

-

1.

ring (R [x ], +, )

a commutative

from R

inverse

satisfying the

Ring

The set of all polynomials in denoted by R[x]. That is,

This forms

more than one element and

existence of multiplicative

e R such that a

cients

having

ring axiom,

defined by max

p(x)

+

(m,n)

q(x)=

(ai+b^x*

i=0

and

p(x)-q(x)=

"

ckXk

where

ck

a{bj.

=

fc=0

i+j=k

Definition 4: Reducible Polynomial

A polynomial f (x) is said to be factored into two (non-constant)

reducible

over

polynomials

the ring (or

in F[x],

field)

otherwise

F if it

f(x) is

can

be

called

irreducible. Theorem 5

The ring

F,

F[x]/(p(x)) is

where

the

notation

field if

only if p(x) is irreducible over the field the set of residues {/ (x) mod denotes F[x]/(p(x)) a

and

p(x):f(x)eF[x}).

Theorem 6 m

elements for some prime p and some integer m finite field, it has p characteristic of F and is the smallest nonzero integer called the is The prime p elements are isomorphic to such that p-\ =0. Furthermore, all fields having

If F is

a

.

pm

each other.

Definition 7:

Galois Field

15

A finite field

with

pm

denoted by GF(pm); they

3.1.2. Representation

modulo an

irreducible

are unique

GF(pn)

may be

polynomial

we can represent

/ (x )

the elements

< n-\ with coefficients

we will use

instance

from

"polynomial"

Galois field

a

pm

and

of order

is

up to isomorphism.

represented

^p

degree

of

GF(pn) Thus

called

Galois Field

of a

The Galois field

is

elements

of

.

set of polynomials

That is

the field

by

choosing the

polynomials of

In the

as equivalence class representatives.

the field

modulo some

GF(53) x2

2ZP

over

Zp[x]/(f(x))

=

to mean "polynomial

our representation of

n

the

as

+

will

irreducible

include the

degree

following For

polynomial".

polynomials

4x+2,

(1)

or

2x, but

not:

2x3

A degree 1,

so

(1)

m

is

by

polynomial

multiply

formed

(1)

called monic

modulo some

and

(2)

the

dividing

remainder

as

+

4x.

(of degree

m

(3) )

if the

coefficient of the x

to

m

term is

Addition

consists

is

polynomial addition and multiplication

of

accomplished

the

adding

by

multiplying

coefficients

of

each term of

the

term of the second, then combining like terms.

above,

(3)

results.

Note however that these

/ (x ). So, for instance if we 3x2

to

8x2

are similar

and multiplication

the resulting polynomial, amounts

""

algebra:

each

and

+

degree 2.

"+"

elementary

corresponding terms

first

is

monic of

operations of

in

learned

polynomial

above

The

we

(2)

+

2x +4, is

take

(3)

modulo

operations are per

f (t)

x3

=

+x +

a valid equivalence class representative.

the result of the elementary operations above

the final result, a

For example, if

member of

16

GF(pn). If

we can

by f (x)

find

and

such an

1 then This

taking

/ (x),

we

will

have defined

GF(p-)

=

field satisfying

a

all

the necessary

of

Thus

properties.

we

write

Zp[x]/(f(x)).

3.1.3. Primitive Elements A

(multiplicative) a*

property:

takes

through the

{0, a, a2, are

on

the value of each nonzero field element exactly once as /

ranges

1

easily multiply in the field.

For

theorem

e

denote the

we

field5.

This

the

GF(pn)

elements of

for

a

field,

as

these elements

allows us to

representation

instance, in GF(c), aa-ab

following

a

more than one generator

called primitive elements of the

collectively

The

Thus

pn-\.

There may be

_1}.

a"

GF(pn), has

special

natural numbers

,

Galois field,

following

generator of a

is the basis

f*^-1).

=aa+b

of our algorithm

to

construct

fields.

Theorem 8

Given any primitive,

n

(1)

ak

/ is irreducible

criteria

selected pair

/

are

to be

and a

/ ) 4 1 for 1. (mod/)

all

/

over

GF (p ) if

over

(mod

(2)aph-l These

monic polynomial

-degree

and

GF(p)

and

and a e

GF(pn),

then

a

is

only if

k