thesis.txt

DIAMOND2加密算法的原代码

BEYOND DES:

DATA COMPRESSION AND THE MPJ ENCRYPTION ALGORITHM

by

Michael Paul Johnson

B. S., University of Colorado at Boulder, 1980









A thesis submitted to the

Faculty of the Graduate School of the

University of Colorado in partial fulfillment

of the requirements for the degree of

Master of Science

Department of Electrical Engineering

1989

Copyright (C) 1989 Michael Paul Johnson.

All Rights Reserved.

This thesis for the Master of Science degree by

Michael Paul Johnson

has been approved for the

Department of

Electrical Engineering

by




Mark A. Wickert




Charles E. Fosha, Jr.




Rodger E. Ziemer



Date                                   

Johnson, Michael Paul (M. S., Electrical Engineering)

Beyond DES:  Data Compression and the MPJ Encryption Algorithm


Thesis directed by Assistant Professor Mark A. Wickert

Many encryption algorithms have come and gone as cryptography, cryptanalysis, 
and technology have progressed.  Today's communication and computer 
technologies need cryptography to truly secure data in many applications. 
The demands on the cryptography needed for some commercial applications 
will exceed the security offered by the National Bureau of Standards 
Data Encryption Standard (DES) in the near future due to advances 
in technology, advances in cryptanalysis, and the increasing rewards 
for breaking such a heavily used algorithm.  To meet part of this 
need, a new block encryption algorithm is proposed.  A Pascal program 
to implement this algorithm is given.

One way to further increase security of encrypted data, as well as 
to achieve storage and/or transmission economy, is by redundancy reduction 
prior to encryption.  A linguistic approach to redundancy reduction, 
together with an example computer program to implement it, is given 
for this purpose.

LIST OF FIGURES	viii

I.	INTRODUCTION	1

A.  Motivation	2

B.  Approach	4

II.	HISTORY OF CRYPTOGRAPHY	6

III.	ELEMENTS OF ENCRYPTION	8

A.  Substitution	8

1.  Monoalphabetic	8

2.  Polyalphabetic	10

B.  Permutation	11

C.  Noise Addition	12

D.  Feedback & Chaining	13

1.  Plain Text Feedback	13

2.  Cipher Text Feedback	14

E.  Analog Encryption	15

IV.	FACTORS RELATED TO ENCRYPTION	17

A.  Change of Language	17

B.  Digitization	18

C.  Compression	18

D.  Multiplexing	19

V.	COMPARISON OF SELECTED ALGORITHMS	20

A.  One-Time Key Tape	20

B.  Linear Shift Register Feedback	21

C.  Exponential Encryption	22

D.  Knapsack	24

E.  Rotor Machines	24

F.  Codes	27

G.  Galois Field and Hill Cryptosystems	28

H.  DES	30

VI.	DESIGN CONSIDERATIONS FOR MPJ	33

A.  Strength Based on Key	33

B.  Usability of Random Keys	33

C.  Key Length & Block Size	34

D.  Effort Required to Break	34

E.  Computational Efficiency	35

F.  Communication Channel Efficiency	36

G.  No Back Doors or Spare Keys	36

VII.	MPJ ENCRYPTION ALGORITHM	37

A.  Description	37

1.  Overall Structure of MPJ	37

2.  Substitution Boxes	39

3.  Wire Crossings	39

4.  Key Generation	40

B.  Implementation in Pascal	44

1.  Exceptions from Standard Pascal	44

2.  Main Program	45

3.  Procedures Encrypt & Decrypt	46

4.  Procedures Permute & Ipermute	47

5.  Procedures Substitute & Isubst	47

C.  Implementation in Hardware	47

D.  Strengths & Weaknesses	48

VIII.	DATA COMPRESSION	50

A.  Purpose	50

B.  Linguistic Parsing	53

C.  Huffman Coding	55

D.  Pascal Programs	55

IX.	CONCLUSION	58

REFERENCES	59

APPENDIX

A.	MPJ in Pascal	64

B.	Linguistic Data Compression Programs	72

FIGURE

III.B	Permutation.	11

III.C.	Noise Addition	12

III.D.	Block Cipher Modes.	14

III.E.	Analog Time & Frequency Encryption	15

V.A.	One-time key tape (AKA One-time pad)	21

V.A.1	Typex Rotor Machine	25

V.E.2.	Wired Rotors	25

V.H.1.	DES Enciphering	30

V.H.2.	DES Nonlinear Function	30

V.H.3.	DES Internal Key Generation	31

VII.A.1.	Overall Structure of MPJ	38

VII.A.3.	Wire Crossings	39

I.   INTRODUCTION

The increasing proliferation of digital communication and computer 
data base storage has brought with it increasing difficulty of maintaining 
the privacy of that data.  There is only one effective way to protect 
the privacy of communications sent over such channels as satellites, 
terrestrial microwave, and cellular telephones.  This is by encryption.  It 
is clearly impossible to deny unauthorized access by a determined 
and knowledgeable interceptor to the communications, but it is possible 
to render the communications totally unintelligible to all but the 
intended receiver(s).

There are many ways to reversibly transform data from its plain form 
to something that looks unintelligible, but many of these can be figured 
out (broken) by someone else.  The study of how to hide secrets is 
cryptology. Trying to figure out the secrets that someone else has 
hidden is cryptanalysis.  These two sciences are, of course, very 
much intertwined. History reveals many examples of cryptology that 
worked, and that didn't [KAH]. Successful cryptanalysis depends on 
taking advantage of as many of the following as are available to the 
cryptanalyst: (1) taking advantage of the redundancy in any natural 
language to determine the validity of assumptions, (2) clues gained 
from corresponding plain and cipher text, (3) information that might 
be known about the algorithm(s) used, (4) the general expected content 
of the cryptograms, (5) all of the cipher text that is available in