AAAAnnnnaaaallllyyyyssssiiiissss ooooffff tttthhhheeee	DDDDEEEESSSS

	    aaaannnndddd	tttthhhheeee DDDDeeeessssiiiiggggnnnn ooooffff tttthhhheeee LLLLOOOOKKKKIIII EEEEnnnnccccrrrryyyyppppttttiiiioooonnnn SSSScccchhhheeeemmmmeeee




			   unicrest here



















			      A	THESIS
	  SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE
	  UNIVERSITY COLLEGE, UNIVERSITY OF NEW	SOUTH WALES
		  AUSTRALIAN DEFENCE FORCE ACADEMY
			 FOR THE DEGREE	OF
			DOCTOR OF PHILOSOPHY


				 By
			Lawrence Peter Brown
			        1991






















			    ii














			  c Copyright 1991
				 by
			Lawrence Peter Brown





















































		CCCCeeeerrrrttttiiiiffffiiiiccccaaaatttteeee ooooffff OOOOrrrriiiiggggiiiinnnnaaaalllliiiittttyyyy





    I hereby declare that this submission is my	own work and that, to the best of
    my knowledge and belief, it	contains no material previously	published or
    written by another person nor material which to a substantial extent has been
    accepted for the award of any other	degree or diploma of a university or
    other institute of higher learning,	except where due acknowledgement is
    made in the	text.

    I also hereby declare that this thesis is written in accordance with the
    University's Policy	with respect to	the use	of Project Reports and Higher
    Degree Theses.







    Lawrence Peter Brown



























			   iii









			    iv






































































			 AAAAbbbbssssttttrrrraaaacccctttt




This  thesis  will  analyse   some   existing	encryption
algorithms  used  to provide secrecy in	communications and
data storage, and will detail the  development	of  a  new
private	 key  algorithm.  It starts with a brief survey	of
modern encyption algorithms and	their uses.  It	then takes
a  closer  look	 at  the  RSA  public  key algorithm, with
particular reference to	its practical implementation.	It
shows  that  whilst RSA	has some very desirable	properties
for use	in public  networks  in	 that  keys  need  not	be
exchanged previously, limitations in implementation speeds
mean that RSA alone is	not  sufficient.   Consequently	 a
hybrid	scheme	is  required  which  combines a	public key
scheme for authentication and key exchange, with a private
key  scheme  for  privacy. At present the DES algorithm	is
the  sole  certified  private  key  scheme.  It	 has  been
extensively  analysed  for  possible  weaknesses since its
adoption in 1977. It is	generally agreed that  whilst  the
structure is sound, its	key size of 56-bits has	become too
small with the	improvements  in  computational	 speed	on
modern computers.  Whilst the DES algorithm is public, its
design criteria	are classified.	 This thesis examines  the
design	of  the	 DES data encryption algorithm and related
schemes, particularly with reference  to  the  fundamental
avalanche   and	 completeness  properties.  From  this	is
developed some possible	design criteria	for such  schemes.
Using these criteria, along with insights based	on generic
substitution-permutation cipher	construction,  suggestions
and  support  from  the	 authors colleagues, and with some
results	 on  substitution  box	design	by  Pieprzyk   and
Seberry,  a  new  group	 of  private key schemes, the LOKI
family,	is designed and	presented as the major achievement
of this	thesis.














			    v









			    vi






































































			 FFFFoooorrrreeeewwwwoooorrrrdddd




To my supervisors Jennifer Seberry,  Ah	 Chung	Tsoi,  and
David  Anderson,  for  their  help,  advice,  support  and
encouragement both directly on the  thesis  material,  and
indirectly  though  their help in supporting this research
environment.

To the current and former members  of  the  Department	of
Computer  Science,  and	 particularly  to  Geoff  Collins,
George	Gerrity,  Andrzej  Goscinski,	Mike   and   Cathy
Newberry,  Josef  Pieprzyk,  Rei  Safavi-Naini,	 and Chris
Vance for their	support, help and suggestions. Thankyou.

This work  could  not  have  been  completed  without  the
support	  of  ARC  grant  A48830241,  ATERB,  and  Telecom
Australia contract 7027. To all	 of  those  organisations,
thankyou for your encouragement	of this	research.






























			   vii









			   viii






































































			 CCCCoooonnnntttteeeennnnttttssss




Chapter	1. Some	Introductory Words ..................	 1
1 Genesis and Goals of the Thesis ...................	 1
2 Content of the Thesis	.............................	 5
2.1 Main Thesis	.....................................	 5
2.2 Appendices ......................................	 8
3 Other	Work by	the Author ..........................	 9
4 Definitions .......................................	10

Chapter	2. Data	Encryption - an	 Introduction  and
     Overview .......................................	13
1 Introduction ......................................	13
2 Modern Private-Key Cryptography ...................	13
2.1 Introduction ....................................	13
2.2 Fundamental	Concepts ............................	14
2.3 Lucifer .........................................	17
2.4 DES	.............................................	20
2.5 DES	Variants ....................................	24
2.6 FEAL ............................................	24
2.7 Khufu, Khafre and Snefru ........................	25
2.8 LOKI ............................................	27
3 Public-Key Cryptography ...........................	27
3.1 Introduction ....................................	27
3.2 Public-Key Distribution Systems (PKDS) ..........	29
3.2.1 Description ...................................	29
3.2.2 Implementation ................................	31
3.3 The	Rivest-Shamir-Adleman (RSA) PKC	.............	32
3.3.1 An Overview of RSA ............................	32
3.3.2 RSA Weaknesses and Related Schemes ............	34
3.3.3 Implementation ................................	35
4 Further Reading ...................................	36
5 Conclusions .......................................	37

Chapter	3. Techniques  for  Implementing  the  RSA
     Public Key	Cryptosystem ........................	39
1 Introduction ......................................	39
2 RSA Encryption and Decryption	.....................	39
3 RSA Key Generation ................................	46
4 RSA Implementation in	Practice ....................	49
4.1 Software Implementations of	RSA .................	49
4.2 Hardware Implementations of	RSA .................	50
5 Conclusion ........................................	51

Chapter	4. Design Rules	for the	DES .................	53
1 Introduction ......................................	53


			    ix









			    x


2 Description of the DES ............................	53
3 Known	DES Design Criteria .........................	54
3.1 S-box Design Criteria ...........................	54
3.2 P-box Design Criteria ...........................	56
3.2.1 IP and IP-1 ...................................	56
3.2.2 PC1 ...........................................	57
3.2.3 P	and E .......................................	57
3.2.4 PC2 ...........................................	59
3.3 Key	Scheduling ..................................	60
4 Ciphertext Dependency	Analysis ....................	61
4.1 Ciphertext Dependence of Plaintext Bits .........	61
4.2 Ciphertext Dependence on Key Bits ...............	62
5 Design of new	DES style Ciphers ...................	65
5.1 S-box Redesign ..................................	65
5.2 P-box Redesign ..................................	66
5.3 Key	Scheduling Extension ........................	67
5.4 Dependency Analysis	of An Extended DES ..........	68
6 Conclusion ........................................	68

Chapter	5. On  the  Design  of	Permutation  P	in
     Feistel Ciphers ................................	71
1 Introduction ......................................	71
2 Empirical P-box Design Criteria ...................	71
3 Further Analysis of the Design of Permutation	 P
     ................................................	74
4 Analysis of the Best Latin-Square Permutations P
     ................................................	75
5 A Regular Form for Permutation P ..................	77
6 A Further Criterion for Best Permutations .........	78
7 Design Rules for Permutation P ....................	79
8 Regular Permutations P in Feistel Ciphers .........	80
9 Conclusion ........................................	81

Chapter	6. Key Scheduling in Feistel Ciphers ........	83
1 Introduction ......................................	83
2 The Key Schedule in DES ...........................	83
3 Empirical Key	Schedule Design	Criteria ............	84
4 Ciphertext Dependence	on Key Bits .................	85
5 Alternatives for the Key Schedule .................	85
6 Some Trials on New Key Schedules ..................	86
7 Design Criteria for New Key Schedules	.............	89
8 An Alternative Key Schedule Design ................	90
9 Conclusion ........................................	91

Chapter	7. LOKI	- A  Cryptographic  Primitive  for
     Authentication and	Secrecy	Applications ........	93
1 Introduction ......................................	93
1.1 Overview ........................................	94
1.2 Encryption ......................................	95
1.3 Decryption ......................................	97
1.4 Function f ......................................	97












			    xi


2 Design Philosophy .................................  100
2.1 Overall LOKI Algorithm Design ...................  100
2.2 Overall Design, Permutation	P, E, and the  Key
     Schedule .......................................  102
2.3 Key	Representation and Choice ...................  105
2.4 LOKI S-boxes ....................................  106
2.5 Selection of Alternate Substitution	 Functions
     S ..............................................  109
3 Additional Modes of Use ...........................  112
3.1  Single Block Hash (SBH) Mode ...................  112
3.2 Double Block Hash (DBH) Mode ....................  113
4 Performance and Implementations ...................  114
4.1 Software Implementation .........................  114
4.2 Hardware Implementation .........................  115
5 Conclusion ........................................  115

Chapter	8. Conclusion ...............................  118
1 Results Obtained in this Thesis ...................  118
2 Assumptions and Limitations of the Research .......  121
3 Suggestions for Further Research ..................  122

Appendix A. Analysis of	the LOKI Primitive ..........  123
1 LOKI Dependency Analysis ..........................  123
1.1 LOKI CPdep Analysis	.............................  125
1.2 LOKI CKdep Analysis	.............................  129
2 Analysis of the LOKI S-Boxes ......................  133

Appendix B. Dependency Analysis	Programs ............  137
1 cp_dep.c ..........................................  137
2 ck_dep.c ..........................................  142

Appendix C. LOKI - Sample Implementation ............  150
1 Overall Program Structure .........................  150
2 Test Data .........................................  151
3 Program Listings ..................................  154

Bibliography ........................................  171


























			   xii






































































		     IIIInnnnddddeeeexxxx ooooffff FFFFiiiigggguuuurrrreeeessss



Fig 1.1	- The Need for Privacy ......................	 1
Fig 1.2	- The Need for Authentication ...............	 2
Fig 1.3	- Private-Key Cryptosystems .................	 3
Fig 1.4	- Public-Key Cryptosystems ..................	 4
Fig 2.1	- Substitution Operation ....................	14
Fig 2.2	- Permutation Operation	.....................	15
Fig 2.3	 -  Sample  S-P	 Network,  with	 Avalanche
     Characteristic .................................	16
Fig 2.4	- A Round of a Feistel Cipher ...............	17
Fig 2.5	- Lucifer ...................................	18
Fig 2.6	- Lucifer Function f ........................	19
Fig 2.7	- DES Enciphering ...........................	20
Fig 2.8	- DES Function g ............................	22
Fig 2.9	- DES Key Scheduling ........................	23
Fig 5.1	- DES as a Mixing Function ..................	72
Fig 7.1	- LOKI Encryption Computation ...............	95
Fig 7.2	- LOKI Function	_f Detail ....................	99
Fig 7.3	- LOKI S-Box Detail .........................  100
Fig 7.4	- LOKI Single Block Hash (SBH) ..............  113
Fig 7.5	- LOKI Double Block Hash (DBH) ..............  114



























			   xiii









			   xiv






































































		     IIIInnnnddddeeeexxxx ooooffff TTTTaaaabbbblllleeeessss



Table 2.1 - Key	Schedule for DES ....................	23
Table  3.1  -  Complexity  of  Factorization   and
     Exponentiation Operations Mod R ................	40
Table 3.2 - Example of Long-hand Multiplication	.....	40
Table 3.3 - Number and Remainder (mod 517) ..........	42
Table 3.4 - Example of Modulo Reduction	.............	42
Table 4.1 - P.E	Permutation .........................	58
Table 4.2 - Worst Case DES P ........................	61
Table 4.3  -  Dependency  of  Ciphertext  bits	on
     Plaintext bits in DES ..........................	62
Table 4.4 - Dependency of Ciphertext bits  on  Key
     bits in DES with Current PC2 ...................	63
Table 4.5 - Dependency of Ciphertext bits  on  Key
     bits in DES with Worst Case PC2 ................	64
Table 4.6 - Dependency of Ciphertext bits  on  Key
     bits in DES with Sample PC2 ....................	64
Table 4.7 - Sample DES PC2 ..........................	64
Table 4.8 - Sample Extended DES	P ...................	66
Table 4.9 - Sample Extended DES	PC2 .................	67
Table 4.10 - Key Schedule for an Extended DES .......	67
Table 4.11 -  Dependency  of  Ciphertext  bits	on
     Plaintext bits in Extended	(128-bit) DES with
     a Sample PC2 ...................................	68
Table 4.12 - Dependency	of Ciphertext bits on  Key
     bits  in  Extended	(128-bit) DES with a Worst
     Case PC2 .......................................	69
Table 4.13 - Dependency	of Ciphertext bits on  Key
     bits  in Extended (128-bit) DES with a Sample
     Regular PC2 ....................................	69
Table 4.14 - Worst Case	Extended DES P ..............	70
Table 4.15 - Worst Case	Extended DES PC2 ............	70
Table 5.1 - P.E	Permutation .........................	73
Table 5.2 - Worst Case DES P ........................	74
Table 5.3 - Dependency of Ciphertext on	 Plaintext
     Bits  for various DES permutations	P by Round
     ................................................	75
Table 5.4 - Fixed Columns in Sample Permutations P
     ................................................	76
Table 5.5 - Best Latin-Square Permutations P ........	77
Table 5.6 - Best Regular Form Permutations P ........	78
Table 5.7  -  Dependency  of  Ciphertext  bits	on
     Plaintext	bits  via  Message,  Autoclave and
     Both Inputs ....................................	78
Table 5.8 - Best Latin Square  Permutations  P	by
     both  Ciphertext-Plaintext	and Ciphertext-Key


			    xv









			   xvi


     Dependence	.....................................	79
Table	5.9   -	  Best	 Regular   Form	  Extended
     Permutations P .................................	80
Table 5.10 -  Dependency  of  Ciphertext  bits	on
     Plaintext bits in Extended	(128-bit) DES .......	80
Table 6.1 - Key	Schedule for DES ....................	83
Table 6.2 - Current DES	Permutation PC2	.............	84
Table 6.3 - Form of generated Permutations PC2 ......	86
Table 6.4 - Dependency of Ciphertext bits  on  Key
     bits  Using Current DES Permutation P and Key
     Schedule .......................................	87
Table 6.5 - Dependency of Ciphertext bits  on  Key
     bits  Using Current DES Permutation P and Key
     Schedule by Both Message and Autoclave  S-box
     Inputs .........................................	88
Table 6.6 - Trial Key Schedules	.....................	89
Table 6.7 - Null and Local  Permutations  PC2  for
     Alternative Key Schedule .......................	90
Table 6.8  -  Alternative  Constant  Key  Rotation
     Schedule .......................................	90
Table 6.9 - Dependency of Ciphertext bits  on  Key
     bits  Using Current DES Permutation P and the
     Alternative Key Schedule by Both Message  and
     Autoclave S-box Inputs .........................	91
Table 7.1 - LOKI Expansion Function E ...............	98
Table 7.2 - LOKI S-box ..............................	99
Table 7.3 - LOKI Permutation P ......................  100
Table 7.4 - LOKI Key Schedule Overview ..............  104
Table 7.5  -  Dependency  of  Ciphertext  bits	on
     Plaintext	and  Key  bits by Both Message and
     Autoclave S-box Inputs .........................  105
Table 7.6  -  LOKI  S-box  Non-linearity  for  the
     Boolean  function	of  all	Input Bits to each
     Output bit	.....................................  109
Table 7.7 - LOKI - S-box Analysis ...................  109
Table 7.8 - Irreducible	Polynomials  for  LOKI	S-
     boxes ..........................................  110
Table 7.9 - Exponents Inverse Pairs Available  for
     use in the	LOKI S-boxes ........................  111


























































































							 0




































































			CCCCHHHHAAAAPPPPTTTTEEEERRRR	 1111


		 SSSSoooommmmeeee IIIInnnnttttrrrroooodddduuuuccccttttoooorrrryyyy WWWWoooorrrrddddssss




_1.  _G_e_n_e_s_i_s _a_n_d	_G_o_a_l_s _o_f _t_h_e _T_h_e_s_i_s

Cryptography, the study	of secret writing, has a long his-
tory  which  until  recently has been primarily	associated
with military and government needs.  Cryptography has  two
major  purposes.  The first is the provision of	_p_r_i_v_a_c_y	by
concealing the contents	of some	message	from _e_a_v_e_s_d_r_o_p_p_e_r_s
who are	not intended to	be able	to read	it (Fig	1.1). This
has been the traditional application of	cryptography.


















	     FFFFiiiigggg 1111....1111 ---- TTTThhhheeee NNNNeeeeeeeedddd	ffffoooorrrr PPPPrrrriiiivvvvaaaaccccyyyy


However, with the  increasing  use  of	electronic  media,
there  has  been  a  developing	 need  for  an	electronic
equivalent of the written signature.  This  addresses  the
need  for  _a_u_t_h_e_n_t_i_c_a_t_i_o_n, of proving who has sent a given
message, such as legal	contracts,  letters,  etc.   in	 a
manner	that they cannot subsequently repudiate	(Fig 1.2).
Both of	these aspects are important in	modern	commercial
cryptography.







			    1









			    2



















	  FFFFiiiigggg 1111....2222 ---- TTTThhhheeee	NNNNeeeeeeeedddd ffffoooorrrr AAAAuuuutttthhhheeeennnnttttiiiiccccaaaattttiiiioooonnnn


Traditional cryptographic schemes have relied on a  series
of  _s_u_b_s_t_i_t_u_t_i_o_n  (where  letters or words are replaced	by
others), and _t_r_a_n_s_p_o_s_i_t_i_o_n or _p_e_r_m_u_t_a_t_i_o_n (where the order
of  letters or words is	changed) operations to conceal the
message. The particular	substitution or	transposition used
is  controlled	by  a  _k_e_y.  This  key is used by both the
sender and the recipient  of  the  concealed  mesage,  and
hence  has  to	be  kept  secret  in  order to protect the
secrecy	of the message.	 Such schemes are called  _P_r_i_v_a_t_e-
_K_e_y  _C_r_y_p_t_o_s_y_s_t_e_m_s  for	this reason (Fig 1.3). The need	to
exchange keys via a trusted  courier,  and  to	keep  them
secret,	 was manageable	whilst the communications channels
were restricted	to  well  defined  miltary  or	diplomatic
hierarchies.

However	the explosion of electronic communications  media,
the rise of Electronics	Funds Transfer (EFT), and the need
for secure communications in business and  the	public	in
electronic  mail schemes, have all lead	to a need for some
alternative scheme where this previous exchange	of keys	is
not  needed.  Since the	number of keys which would need	to
be exchanged grows as the square of the	number of partici-
pants,	this  soon  becomes infeasible.	 What is needed	is
the ability to be able to publish an encryption	key  (used
either	to  conceal the	message, or to verify a	signature)
in  the	 equivalent  of	 a  telephone  directory,  without
compromising  the decryption key (used to restore the mes-
sage or	create a signature), and hence the security of the
message.   Such	 schemes  are called _P_u_b_l_i_c-_K_e_y	_C_r_y_p_t_o_s_y_s_-
_t_e_m_s, or _T_w_o-_K_e_y _C_r_y_p_t_o_s_y_s_t_e_m_s (Fig 1.4).  They	were  ori-
ginally	 proposed in a pivotal paper by	Diffie and Hellman


			Chapter	1









			    3


[DiH76], who developed these concepts, and proposed a pos-
sible scheme; and also independently by	Merkle [Mer78] who
outlined the basic concepts, but did not propose a  feasi-
ble system.




















	  FFFFiiiigggg 1111....3333 ---- PPPPrrrriiiivvvvaaaatttteeee----KKKKeeeeyyyy	CCCCrrrryyyyppppttttoooossssyyyysssstttteeeemmmmssss


Ideally, public-key cryptosystems should be able  to  pro-
vide  all  the features	desired	in a secure communications
system.	However, as shown in Chapter 3,	limitations in the
implementation	speed  of such schemes at present restrict
their  usefulness  to  authentication  and  key	  exchange
(important  though  these  are).   Consequently	there is a
need for hybrid	schemes	which use a public-key	cryptosys-
tem  to	 exchange session keys and to sign messages, and a
private-key cryptosystem to efficiently	encrypt	 the  mes-
sage  for  privacy.   This  implies a need for good modern
private	keys schemes, preferably  a  number  of	 different
schemes	 which	may be employed	in applications	of varying
sensitivity in the commercial and government  confidential
areas.	 Current  schemes in use are either proprietry,	or
are felt to have key  sizes  which  are	 too  small.   The
remainder of this thesis details the development of a good
new private key	scheme,	which is the major achievement	of
this thesis.








			Chapter	1









			    4





















	  FFFFiiiigggg 1111....4444 ---- PPPPuuuubbbblllliiiicccc----KKKKeeeeyyyy CCCCrrrryyyyppppttttoooossssyyyysssstttteeeemmmmssss


To  achieve  this,  the	 Data  Encryption  Standard  (DES)
[NBS77]	 is  analysed in detail	as a source of insights	to
be used	in the design of the new cipher.  DES has achieved
wide  utilization,  particularly  in the banking and elec-
tronic funds transfer areas, where it is now an	Australian
standard  [ASA85].   At	the time of its	introduction there
was a considerable amount of controversy,  primarily  with
the choice of a	56-bit key [DiH77], [Hel79a].  This was	on
the grounds that such a	key length was small enough to	be
exhaustively  searched	on  machines  which  could be con-
structed in the	foreseeable future.   With  the	 march	of
computer technology, this risk appears to be rising.  How-
ever, on all other accounts DES	appears	to be an excellent
cryptosystem.	The DES	has withstood a	concerted analysis
by the open research  community,  since	 its  adoption	in
1977.	The  most successful attack to date, that of Biham
and Shamir [BiS90] still performs worse	than an	exhaustive
key-space search on the	DES with the full 16 rounds.

With the current significant use  of  DES  (especially	in
banking),  there  is  interest in designing and	building a
DES-type cryptosystem with an  extended	 key  length,  for
several	reasons. These include:

+o     Doubts about the ability	of  DES	 to  withstand	an
     attack  based  on	exhaustive  key-space  searches	on
     specialised hardware (cf. the decision of the US  NBS
     to	 withdraw certification	of DES for all but banking
     applications).  This may be  overcome  by	increasing


			Chapter	1









			    5


     the key length.

+o     The difficulty in	obtaining DES systems outside  the
     US, due to	export restrictions.

+o     The desire to develop a scheme  for  which  all  the
     design  criteria  used  are  known, and hence open	to
     criticism.

Given these reasons, and the confidence	with which the DES
is  otherwise  regarded,  it  was  felt	to be suitable for
analysis to derive some	 design	 rules.	  Whilst  the  DES
algorithm  is  public, its design criteria are classified.
This thesis examines the design	of the DES data	encryption
standard,  and	develops some possible design criteria for
it in Chapters 4, 5 and	6.  Using  these  criteria,  along
with  insights	based  on generic substitution-permutation
cipher construction,  suggestions  and	support	 from  the
authors	 colleagues, and with some results on substitution
box design  by	Pieprzyk  and  Seberry	[PiF89],  [Pie90],
[Pie89],  [PiS89], a new group of private key schemes, the
LOKI family is designed.  This development is detailed	in
Chapter	 7.   A	preliminary analysis of	one of the members
of this	family is  then	 given.	 The  appendices  of  this
thesis	present	 the detailed results from the analysis	of
one of the LOKI	ciphers; the code used for the	dependency
analysis  programs;  and  a sample LOKI	cipher implementa-
tion.

_2.  _C_o_n_t_e_n_t _o_f _t_h_e _T_h_e_s_i_s

_2._1.  _M_a_i_n _T_h_e_s_i_s

The detailed contents of each chapter are as follows.

Chapter	1 is this overview of the thesis.

Chapter	2 surveys the field of cryptography, providing	an
overview  of  the modern private and public key	cryptosys-
tems used to provide privacy and authentication.  It  con-
trasts	 their	 strengths  and	 weaknesses,  and  briefly
describes a number of schemes either in	use,  or  proposed
for  use.  These  algorithms  form the basis against which
further	algorithm development will be compared.

Chapter	3 examines the RSA public key cryptosystem,  which
at present is generating considerable interest as a scheme
with a wide  range  of	potential  uses.  Indeed,  it  has
already	 been  adopted	to  provide  authentication in EFT
application in the UK.	However,  its  practical  use  for
providing  secrecy  has	 been  limited because of the time


			Chapter	1









			    6


taken to perform its essential encryption  and	decryption
functions.  Whilst  the	 times achieved	to date	are suffi-
ciently	short for key exchange and authentication schemes,
they  are  not	fast enough for	encrypting data	to provide
privacy. Thus in the near  term,  practical  schemes  will
very  likely  use  hybrid  systems. These use a	public key
algorithm to exchange session keys, and	to provide authen-
tication  and  non-repudiation	of  messages,  and  a fast
private	key scheme to provide privacy.	This chapter  con-
cludes that whilst public key schemes would seem to be the
obvious	realm of research  into	 cryptographic	algorithms
because	 of  their  advantages in public networks, present
limitations indicate that good	private	 key  schemes  are
still  required. This chapter includes material	previously
presented to the "Secure  Data	Communications	Workshop",
organized  by  the  IEEE Communications	Section, Victorian
Branch,	held at	the Town House,	Melbourne,  on	31st  July
1987 [Bro87].

Chapter	4 examines the Data Encryption Standard	DES.  This
is  the	 most widely used private key encryption system	at
present, especially  in	 the  financial	 industry.  Though
there were some	initial	doubts about the design	of DES,	it
has withstood considerable analysis by the  open  research
community  since  its adoption in 1977.	 The design of the
DES is regarded	as  sound,  though  the	 size  of  key	is
thought	 to  be	 too small.  Whilst DES	is a standard, the
design criteria	used in	its development	have been  classi-
fied  by  the  US  government.	Because	 of  this,  and	of
increasing doubts about	the ability of DES to withstand	an
attack	based  on  an  exhaustive  key-space  search using
specialised hardware, there is	considerable  interest	in
developing an encryption scheme	for which the design rules
used are known,	and hence open to analysis and	criticism.
This  is  the  primary	goal  of  this thesis. In order	to
achieve	this, a	detailed examination of	the DES	 is  done,
since  its  design  has	 withstood the test of time.  This
chapter	reviews	what is	known about  the  design  criteria
for  the  S-boxes,  P-boxes,  and  key	scheduling  in the
current	DES. It	then presents some initial observations	by
the  author  on	possible design	rules for the permutations
P, PC2,	and the	key rotation schedule KS in the	 DES.	It
then  indicates	 how  this  information	 could	be used	to
design new private key schemes	with  either  full  64-bit
keys  (instead	of  the	 56-bits used in the DES), or with
double length keys of  128-bits.   This	 chapter  includes
material  previously presented to IFIP Sec'88, held on the
Gold Coast, Australia, in May 1988, and	subsequently  pub-
lished in [Bro89].




			Chapter	1









			    7


The next two chapters examine two key  components  of  the
DES  structure	in more	detail:	the permutations P and PC2
and the	key schedule KS.

Chapter	5 develops some	design criteria	for  the  permuta-
tion  P	in a DES style cryptosystem. This permutation pro-
vides  the  diffusion	component   of	 a   substitution-
permutation  network.	Some empirical rules which seem	to
account	for the	derivation of the permutation used in  the
DES  are first presented. The author then notes	that these
permutations may be regarded as	latin-squares  which  link
the  outputs of	S-boxes	to their inputs	at the next stage.
A subset of these with a regular structure, and	which per-
form  well  in	a  dependency analysis are then	presented.
The author then	generalises the	design rules for  permuta-
tion  P.   These  rules	will be	used later in Chapter 7	in
the design of the LOKI algorithm.  This	 chapter  includes
material   previously	presented   to	Eurocrypt  '89	in
Houthalen,  Belgium,  in  April	 1989,	and  published	in
[BrS90a].

Chapter	6  develops  some  design  criteria  for  the  key
schedule  in  a	 DES style cryptosystem.  The key schedule
involves a Key Rotation	component KS, and the  permutation
PC2.  Together these provide for a diffusion of	dependency
of ciphertext bits on  key  bits.   Some  empirical  rules
which  seem  to	 account  for  the  derivation	of the key
schedule used in the DES are first presented.  A number	of
trials	were  run  with	 various  key  schedules, and some
further	design rules were derived. An alternative form	of
key schedule was then tested. This used	either a null PC2,
or one in which	 permutations  only  occurred  within  the
inputs	to  a  given  S-box,  and  a  much larger rotation
schedule than used in the DES. This was	 found	to  be	as
effective as the key schedule used in the current DES, and
is proposed for	use later in Chapter 7 in  the	design	of
the LOKI algorithm.  This chapter includes material previ-
ously presented	to Auscrypt '90, in Sydney, Australia,	in
January	1990, and published in [BrS90b].

Chapter	7 presents the major achievement of  this  thesis.
It  provides  an overview of the LOKI encryption algorithm
which may be used to encrypt and decrypt a 64-bit block	of
data  using  a	64-bit key. It was developed by	the author
and his	colleagues  Professor  Jennifer	 Seberry  and  Dr.
Josef  Pieprzyk.   The	structure  of  the LOKI	encryption
algorithm was designed by the author based on the  general
design principles developed in the previous chapters.  The
design	principles  for	 selecting  S-boxes  developed	by
Pieprzyk  and  Seberry	[PiF89], [Pie90], [Pie89], [PiS89]
were used in the design	of the S-boxes used in LOKI.  This


			Chapter	1









			    8


chapter	 completely details the	proposed publicly standar-
dised version of the LOKI cipher. It  also  describes  how
customised versions of the cipher may be constructed which
are believed to	have the same degree of	 security  as  the
standard  version  of the cipher.  The author then summar-
ises the encouraging results from the initial  testing	of
the LOKI cipher, details of which are given in Appendix	1.
The LOKI cipher	may be	used  in  any  mode  of	 operation
currently defined for DES, with	which it is interface com-
patible	[AAA83].  In addition, the author has adapted  two
modes  of operation of LOKI which compute a 64-bit or 128-
bit Message Authentication Code	(or hash  values)  respec-
tively,	 from  previous	 work by Davies	and Price [DaP89],
Winternitz [Win83], and	Quisquater  and	 Girault  [QuG90].
These  modes of	operation may be used to provide authenti-
cation of a communications  session,  or  of  data  files.
Finally	 the  author  presents some observations about the
likely performance of the LOKI cipher in both software and
hardware  implementations,  which  show	 that  it compares
extremely  favorably  against  the   alternatives.    This
chapter	includes material previously presented to Auscrypt
'90, in	Sydney,	Australia, in January 1990, and	 published
in [BrS90b]. Versions of this material have also been sup-
plied to the European RIPE consortium  [BPS89],	 to  Stan-
dards  Australia,  and to the Defence Signals Directorate,
for evaluation.

Chapter	8 summarises the results and achievements of  this
thesis,	as described in	the preceeding chapters.

_2._2.  _A_p_p_e_n_d_i_c_e_s

The  Appendices	 of  this  thesis  comprise  the  detailed
results	 from  the  analysis  of the LOKI algorithm; the C
program	source for the DES dependency  analysis	 programs;
and  the  C  program source for	a sample implementation	of
the LOKI algorithm.

Appendix 1 presents the	detailed results from  the  depen-
dency  analysis	 and  preliminary  statistical analysis	of
LOKI cipher.

Appendix 2 contains a listing of two programs  ccccpppp____ddddeeeepppp  and
cccckkkk____ddddeeeepppp,	which perform a	dependency analysis of output bits
on input and key bits for a DES	like cipher. This analysis
provides a measure of effectiveness of the permutations	P,
PC2, and the key schedule KS, in achieving  the	 avalanche
and  completeness  properties.	This was used as a measure
of effectiveness in evaluating variations of the  permuta-
tions P, PC2, and the key schedule KS in DES like schemes,
and in LOKI, in	the development	of the design criteria.	In


			Chapter	1









			    9


detail,	the programs are:

cp_dep.c
     builds a dependency matrix	for each  ciphertext  bit,
     based  on	plaintext bits,	for a given P.	It assumes
     that the S-boxes provide an adequate degree of confu-
     sion sufficient to	ensure that all	outputs	are depen-
     dent on all inputs, and that the  S-Box  outputs  are
     all equivalent.  It takes as input	a permutation P	to
     use in the	cipher structure being analysed.

ck_dep.c
     builds a dependency matrix	for each  ciphertext  bit,
     based  on	keytext	 bits,	for a given P, PC2 and key
     schedule.	It assumes that	 the  S-boxes  provide	an
     adequate  degree  of  confusion  sufficient to ensure
     that all outputs are dependent  on	 all  inputs,  and
     that  the S-Box outputs are all equivalent.  It takes
     as	input permutations P, and PC2, and a key  schedule
     KS	to use in the cipher structure being analysed.

Appendix 3 contains a listing of a  sample  implementation
of  the	LOKI cipher.  These implement the first	(small but
slow) of the possible software implementations	identified
in Chapter 7.

_3.  _O_t_h_e_r _W_o_r_k _b_y _t_h_e _A_u_t_h_o_r

During the period when the work	detailed  in  this  thesis
was being developed, the author	was engaged in a couple	of
other related projects which may be of interest.

One discusses some  alternative	 approaches  to	 providing
security  in remote terminal sessions. Since remote termi-
nal sessions mean that information is carried over a  net-
work  that may not be trusted, there is	a need for mechan-
isms to	protect	the security of	information exchanged dur-
ing  the  session.  The	protocols implemented will need	to
address	the issues of authentication of	the parties, nego-
tiation	 of  a suitable	cipher to use, and the exchange	of
keys for that cipher.  This paper examines each	 of  these
issues,	describes a prototype implementation incorporating
some of	these features in the sssseeeecccclllloooogggg program, and finishes
with  a	 description  of work in progress on extending the
widely used tttteeeellllnnnneeeetttt protocol to incorporate some	 of  these
security   features.	This  material	was  presented	to
AUUGC'90, World	Trade Centre,  Melbourne,  Victoria,  Aus-
tralia 26th - 28th September, 1990 [Bro90b], [Bro90].

The other project surveys the various alternatives  avail-
able  for  the provision of a Pay-TV service in	Australia.


			Chapter	1









			    10


In particular, the technical  alternatives  available  for
the  delivery, transmission, scrambling	and key	management
components are presented. A selection of  systems  in,	or
proposed  for  use  are	 then compared.	 This material was
published in [Bro90a].

_4.  _D_e_f_i_n_i_t_i_o_n_s

Within this thesis, the	following definitions apply:

Algorithm
     a clearly specified mathematical process for computa-
     tion;  a set of rules which, if followed, will give a
     prescribed	result.

Autoclave
     a process of incorporating	information from the  mes-
     sage  input  to  an encryption algorithm into the key
     scheduling	of that	algorithm. Thus	different  message
     inputs  result  in	 different  keying  choices in the
     various stages of	the  algorithm.	 This  is  usually
     acomplished  by  using some message bits as inputs	to
     both the key selection as well as the message substi-
     tution parts of the algorithm.

Avalanche Property
     of	a function implies that	a change in an	input  bit
     should  result  in	 approximately	half of	the output
     bits changing [Fei73].

Bit Numbering
     bits within a 64-bit block	b are numbered from 63	to
     0,	  left	 to   right,   MSB  to	LSB,  and  denoted
     [b	 b  ...b b ].  The bits	within a 32-bit	block  are
     nu6m3be6r2ed  l1ik0ewise	 from 31 to 0, ie the string 10010
     represents	 the  number  eighteen.	  When	 used	to
     represent	a polynomial in	a Galois field,	a block	is
     interpreted as having the left  most  bit	being  the
     most significant.	ie the string 100011011	represents
     the polynomial x8+x4+x3+x+1.

Ciphertext
     clear text	that has been encrypted.

Cleartext
     intelligible text or signals that	have  meaning  and
     that can be read and used.

Completeness Property
     of	a function implies that	each output bit	must be	 a
     complex function of all input bits	[KaD79].


			Chapter	1









			    11


Concatenation
     of	two blocks L and R of 32 bits, denoted L | R, will
     result in LR a 64-bit block consisting of the bits	of
     L followed	by the bits of R.

Confusion
     a term coined by Shannon [Sha49] to describe a  func-
     tion whose	output is a complex function of	its inputs
     (usually composed of a data block and a sub-key).

Diffusion
     a term coined by Shannon [Sha49] to describe a linear
     function  whose  output  is  a  permutation (or wire-
     crossing) of its inputs, and which	distributes  input
     bits so as	to remove any local clustering.

Data Encryption	Algorithm (DEA)
     an	algorithm designed to encrypt and  decrypt  blocks
     of	data.

Decryption
     the transformation	of ciphertext into cleartext.

Encryption
     the transformation	of cleartext into  ciphertext  for
     the purpose of security or	privacy.

Encryption algorithm
     a set of mathematically expressed rules for rendering
     information  unintelligible, by effecting a series	of
     transformations to	the normal representation  of  the
     information,  through  the	 use  of variable elements
     controlled	by the application of a	key.

Galois Field
     denoted GF(pn), is	an extension of	degree n of GF(p).
     In	 particular,  this thesis refers to binary fields,
     eg	GF(28).

Initialization Vector
     a binary vector used in the initial  input	 block	in
     cipher block chaining mode	of operation.

Key
     a 64-bit quantity which is	used  for  transformations
     between ciphertext	and cleartext.

LOKI the name of the DEA being developed in this thesis.

Modulo 2 addition
     a	mathematical  operation	  equivalent   to   binary


			Chapter	1









			    12


     addition  without carry.  Sometimes referred to as	an
     'exclusive	OR' operation.

Non-Linearity
     of	a function f, belonging	 to  the  set  F   of  all
     Boolean  functions	 of  n	Boolean	 variablnes, is the
     minimum Hamming distance between f	and the	set of all
     linear  Boolean  functions	L  existing in F  [Pie90],
     [Pie89].			 n		n

Permutation
     a function	that reorders a	set of n  input	 bits.	It
     may be described by a table of size n. nb:	this usage
     differs from that of Pieprzyk, for	whom this term	is
     a synonym for substitution.

ROL(B,n)
     the operation of rotating a block B n places  to  the
     left,  with  wraparound  from  the	MSB to LSB. ie;	b
     becomes b , b  becomes b	 etc.			 0
	      n	  1	     n+1
ROR(B,n)
     the operation of rotating a block B n places  to  the
     right,  with  wraparound  from the	LSB to MSB. ie;	b
     becomes b , b    becomes b	 etc.			 n
	      0	  n+1	       1
Substitution
     a function	mapping	a set of m bit input words onto	 a
     set  of  n	bit output words. It may be described by a
     table of size 2m.























			Chapter	1












			CCCCHHHHAAAAPPPPTTTTEEEERRRR	 2222


      DDDDaaaattttaaaa EEEEnnnnccccrrrryyyyppppttttiiiioooonnnn ----	aaaannnn IIIInnnnttttrrrroooodddduuuuccccttttiiiioooonnnn	aaaannnndddd OOOOvvvveeeerrrrvvvviiiieeeewwww




_1.  _I_n_t_r_o_d_u_c_t_i_o_n

This chapter provides an overview of some  modern  encryp-
tion  algorithms,  both	 private  and  public key. It will
describe the general framework within which these  schemes
have  been  developed,	briefly	 detail	 a number of algo-
rithms,	 and  then   describe  in  detail  two	particular
schemes:  DES  and  RSA. These have been chosen	as the two
algorithms generating the most interest	in the private and
public-key realms respectively.

The aim	of this	chapter	is  to	establish  the	background
against	  which	 the  remainder	 of  the  thesis  will	be
developed.  In	particular  it	intends	 to  describe  the
theoretical  framework,	 so far	as is known, that has been
used  to  design  the  DES  and	 RSA  algorithms.  In  the
remainder of this thesis the author will be extending that
analysis, ultimately using it to develop a new	family	of
private	key algorithms.

As described earlier, encryption algorithms may	 be  cata-
gorised	 into  two  broad  families. Private key (one-key)
algorithms in which both sender	and recipient share a com-
mon  secret  key  for  both encryption and decryption; and
public key (two-key) algorithms	in which the sender uses a
well  known  public  encryption	 key, whilst the recipient
uses a secret  decryption  key.	  These	 classes  will	be
detailed separately.

_2.  _M_o_d_e_r_n _P_r_i_v_a_t_e-_K_e_y _C_r_y_p_t_o_g_r_a_p_h_y

_2._1.  _I_n_t_r_o_d_u_c_t_i_o_n

With the advent	 of  computers,	 data  encryption  schemes
underwent  a  revolutionary  change.  The use of computers
enabled	the cracking of	hitherto secure	schemes, but  also
enabled	 the  implementation  of  schemes which	until then
were too complex for use by a manual cipherclerk. Based	on
the  work  of  Shannon [Sha49],	a new family of	cryptosys-
tems,  known  as  _S_u_b_s_t_i_t_u_t_i_o_n-_P_e_r_m_u_t_a_t_i_o_n  _n_e_t_w_o_r_k_s  were
developed.  These led to the development of a system known
as LLLLuuuucccciiiiffffeeeerrrr, at the IBM Research	Laboratories [Fei73],  and
subsequently   to   the	 DDDDaaaattttaaaa  EEEEnnnnccccrrrryyyyppppttttiiiioooonnnn  SSSSttttaaaannnnddddaaaarrrrdddd  ((((DDDDEEEESSSS))))


			    13









			    14


[NBS77]. DES has since achieved	wide utilization, particu-
larly  in the banking and electronic funds transfer areas,
where it is now	 a  standard  in  a  number  of	 countries
including the USA [NBS77], [Ins81], [AAA83], and Australia
[ASA85].

_2._2.  _F_u_n_d_a_m_e_n_t_a_l _C_o_n_c_e_p_t_s

In designing cryptographic algorithms, there are two basic
cryptographic  primitives:  _s_u_b_s_t_i_t_u_t_i_o_n and _t_r_a_n_s_p_o_s_i_t_i_o_n
(or _p_e_r_m_u_t_a_t_i_o_n).  In a	substitution function, each  char-
acter  is  replaced  by	 some other character (see example
instance in Fig	2.1).















	   FFFFiiiigggg 2222....1111 ---- SSSSuuuubbbbssssttttiiiittttuuuuttttiiiioooonnnn OOOOppppeeeerrrraaaattttiiiioooonnnn


The particular substitution used is selected by	some  _k_e_y.
If  characters	are represented	by a small number of bits,
then such a scheme may be defeated by enumerating all pos-
sible  cases to	find the substitution used. If made suffi-
ciently	large and a suitably  complex  function	 is  used,
such  a	 scheme	is in practice unbreakable, since it would
require	the enumeration	of all n! cases	(where	n  is  the
number	of possible characters).  Unfortunately	it is also
unworkable, since the number of	 permutations,	and  hence
keys, would be equally large.

Traditionally, in a transposition function a set of  char-
acters	were permuted (rearranged) into	a new order, again
with the particular rearrangement selected  by	some  key.
In  modern  implementations, this becomes a permutation	of
bits or	a wire-crossing	(see example instance in Fig 2.2).






			Chapter	2









			    15




















	    FFFFiiiigggg	2222....2222 ---- PPPPeeeerrrrmmmmuuuuttttaaaattttiiiioooonnnn OOOOppppeeeerrrraaaattttiiiioooonnnn


Since the complexity of	such an	operation is  only  linear
in  the	 number	 of  bits used,	it may be easily broken	by
testing	each bit in turn to find  its  new  location.	It
also  implies that it is easy to build such a function for
large numbers of bits.

Because	of these weaknesses in both the	basic  primitives,
the  concept of	_p_r_o_d_u_c_t	_c_i_p_h_e_r_s	arose, whereby a series	of
substitution and transposition functions were combined	to
form  a	function which is much more secure than	any of its
components. Prior to the introduction of  rotor	 machines,
only  simple  product ciphers were possible.  The develop-
ment  of  rotor	 machines,  and	 subsequently	computers,
changed	this significantly.

Shannon	[Sha49], in a key paper,  described  a	particular
class of product ciphers which used a number of	small (and
hence implementable) substitution boxes,  termed  S-boxes,
connected  by large permutation	boxes, termed P-boxes (see
Fig 2.3).  He termed these _m_i_x_i_n_g _t_r_a_n_s_f_o_r_m_a_t_i_o_n_s, whereby
the  S-boxes  provided	_c_o_n_f_u_s_i_o_n of the input,	and the	P-
boxes provide _d_i_f_f_u_s_i_o_n	of the S-box  outputs  across  the
inputs	to  the	 next  stage.  Such schemes are	now termed
_S_u_b_s_t_i_t_u_t_i_o_n-_P_e_r_m_u_t_a_t_i_o_n (_S-_P) _n_e_t_w_o_r_k_s.








			Chapter	2









			    16




















    FFFFiiiigggg	2222....3333 ---- SSSSaaaammmmpppplllleeee SSSS----PPPP NNNNeeeettttwwwwoooorrrrkkkk,,,, wwwwiiiitttthhhh AAAAvvvvaaaallllaaaannnncccchhhheeee CCCChhhhaaaarrrraaaacccctttteeeerrrriiiissssttttiiiicccc


Two key	properties of such S-P networks	are the	 _a_v_a_l_a_n_c_h_e
property, identified by	Feistel	[Fei73]; and the _c_o_m_p_l_e_t_e_-
_n_e_s_s property, identified by Kam and Davida [KaD79].   The
avalanche  property  states  that  changing  one input bit
should result in approximately half  of	 the  output  bits
changing.  The completeness property states that each out-
put bit	must be	a complex function  of	every  input  bit.
These  properties appear to be important criteria for pro-
viding cryptographic strength in the resultant system.

More formally, these are defined (see [WeT86]) as follows.
A function f has a good	_a_v_a_l_a_n_c_h_e effect if:
				   m
    for	each bit i, 0m_<i-<m1, if the 2  plaintext vectors are
    divided  into  2	   pairs  X  and Xmi-1with each pair
    differing only in bit i; and if the	2     exclusive-or
    sums, termed avalanche vectors

			 Vi = f(X) XOR f(Xi)	  (Eq 2.1)

    are	compared, then about half of these sums	should	be
    found to be	1.

A function f is	_c_o_m_p_l_e_t_e if:

    for	each bit j, 0_<j<m in the ciphertext output vector,
    there  is at least one pair	of plaintext vectors X and
    Xi,	which differ only in bit i, and	for which f(X) and
    f(Xi) differ in bit	j



			Chapter	2









			    17


For a practical	scheme however,	it is obviously	 necessary
for  the  recipient  to	 be  able to decipher the message.
This implies that one must be able to compute the  inverse
of  the	 enciphering  function.	For the	simple S-P network
shown above, it	would be necessary to provide  a  separate
decryption stage incorporating the inverses of the substi-
tutions	and permutations used.	This is	expensive in terms
of  both  hardware  and	 software.  It is preferable to	be
able to	use the	same  hardware	for  both  encryption  and
decryption.  This  may	be done	by an elegant scheme which
partitions the input and output	blocks	into  two  halves,
L(i - 1)  and R(i-1), and uses only R(i-1) at each round i
(see Fig 2.4).	This half R(i-1), along	with a	key  K(i),
is  used  as  input  to	 the  encryption function g (which
incorporates one stage of the S-P network), and	R(i-1)	is
also copied to L(i) for	the next round.	 The output from g
is added modulo	2 to L(i-1) to	form  R(i)  for	 the  next
round.	Thus when decrypting, L(i) is copied back into R(i
-1) where it is	used as	input to g in order to recover L(i
-1).  Thus it can be used to recover the other half of the
input upon decryption.	Ciphers	with  this  form  are  now
refered	 to  as	 _F_e_i_s_t_e_l  _C_i_p_h_e_r_s  after  Horst	Feistel, a
researcher from	the IBM	Thomas J. Watson Research  Labora-
tory who did much of the early development of this type	of
cipher in the early 70s.












       FFFFiiiigggg 2222....4444 ---- AAAA RRRRoooouuuunnnndddd ooooffff aaaa FFFFeeeeiiiisssstttteeeellll CCCCiiiipppphhhheeeerrrr


_2._3.  _L_u_c_i_f_e_r

The first scheme developed  based  on  the  concept  of	 a
substitution-permutation  network  was	the  Lucifer algo-
rithm.	This was developed at  the  IBM	 Thomas	 J  Watson
Research  Laboratory in	the early 1970s, by a team includ-
ing Horst Feistel, William Notz	and J. Lynn  Smith.   This
development  is	 detailed  in  a number	of papers [Fei73],
[FNS75], [SNO72], [Gir71]. The best current description	of
the  Lucifer  algorithm	 is  that by Sorkin [Sor84], which
also includes a	Fortran	implementation of  the	algorithm.


			Chapter	2









			    18


Given the sparseness of	detail in the earlier descriptions
of Lucifer, this is a very useful aid to implementing it.



































		  FFFFiiiigggg 2222....5555 ---- LLLLuuuucccciiiiffffeeeerrrr


Lucifer	is a Feistel cipher. It	has a block size  of  128-
bits,  and  a  key of 128-bits.	The input block	is divided
into two halves, the upper  and	 lower	halves,	 with  the
leftmost  bit and byte being the lowest, and the rightmost
bit and	byte being the highest.	In each	round,	the  lower
half  of  the  input  is modified by being summed modulo 2
with a function	f of the upper half of the input, and  the
lower  half  of	 the  key.  The	 two input halves are then
exchanged, and the key is rotated 7 bytes (56-bits) to the
left.  This is shown in	Fig 2.5.



			Chapter	2









			    19


In more	detail,	function f  consists  of  a  substitution,
addition  of  the key, and a permutation. This is shown	in
Fig 2.6. The substitution consists of eight identical sub-
stitution functions which map 8-bits of	input and 1-bit	of
key to 8-bits of output. The substitution function in turn
is composed of a pair of 4-bit to 4-bit	substitution func-
tions. Depending on the	key-bit,  these	 are  composed	as
either	S0|S1 or S1|S0.	The eight bits of key used in this
are taken from the leftmost byte of the	partial	 key  used
in  the	 round,	 with bit-7 used to select the function	on
message	byte 0,	bit-6 on message byte 1	etc. The output	of
the  substitution  functions are then summed modulo 2 with
the partial key, a process termed _k_e_y _i_n_t_e_r_r_u_p_t_i_o_n in  the
descriptions  of Lucifer. Finally, the result is permuted.
This permutation is described as  having  two  components.
First  a  regular  8-bit to 8-bit _p_e_r_m_u_t_a_t_i_o_n repeated for
every byte of the result. Then an 8-bit	to 64-bit _c_o_n_v_o_l_u_-
_t_i_o_n  which  maps  those outputs a fixed displacement over
the final function f  output.	From  the  perspective	of
modern	analysis  of this cipher, these	two components may
be regarded as a single	64-bit to 64-bit permutation  with
a  very	regular	structure. For details of the actual func-
tions used,  and  the  key  access  schedule,  see  Sorkin
[Sor84].


















	      FFFFiiiigggg 2222....6666 ----	LLLLuuuucccciiiiffffeeeerrrr	FFFFuuuunnnnccccttttiiiioooonnnn f


From the little	discussion of Lucifer in the open  litera-
ture,  the  consensus  appears	to  be	that  it is a well
designed and sound cipher. It was the predecessor  of  the
DES. However, with the development of the DES, Lucifer has
been eclipsed, apart  from  mainly  theoretical	 interest.
What  little  work has been published on the cryptanalysis


			Chapter	2









			    20


of  Lucifer  and  similar  Feistel  ciphers  is	 given	in
[GrT78], [KaD79], [AnR82].







































	       FFFFiiiigggg 2222....7777 ---- DDDDEEEESSSS EEEEnnnncccciiiipppphhhheeeerrrriiiinnnngggg


_2._4.  _D_E_S

The Data Encryption Standard (DES) [NBS77]  was	 developed
out  of	 the  Lucifer  cipher in the mid 70s. It has since
achieved wide utilization, particularly	in the banking and
electronic  funds  transfer  areas.   It  is an	Australian
standard [ASA85] for this purpose, and in the US has  been


			Chapter	2









			    21


certified until	1992, again for	this purpose.

However, there was a considerable amount of controversy	at
the time of its	introduction, primarily	with the choice	of
a 56-bit key [DiH77], [Hel79a].	 This was on  the  grounds
that such a key	length was small enough	to be exhaustively
searched on machines which could  be  constructed  in  the
foreseeable  future.   With the	march of computer technol-
ogy, this risk appears to be rising. However, on all other
accounts DES appears to	be an excellent	cryptosystem.  The
DES  has  withstood  a	concerted  analysis  by	 the  open
research  community, since its adoption	in 1977.  The most
successful attack  to  date,  that  of	Biham  and  Shamir
[BiS90]	 still performs	worse than an exhaustive key-space
search on the DES with the full	16 rounds.

The basic DES enciphering chain	is shown in  Fig  2.7.	In
brief,	the input block	is permuted by an initial permuta-
tion IP, is then subjected to a	complex	key-dependent com-
putation,  and is finally permuted by IP-1, the	inverse	of
the initial permutation. On deciphering, the same  process
is  used,  except  that	the complex component is run back-
wards,	using  keys  in	 reverse  order,  via  the  method
described previously (see Fig 2.4).

In more	detail,	the input block	X of 64	bits is	first per-
muted by the initial permutation IP, and then divided into
two halves L(0)	and R(0).  The complex key-dependent func-
tion  consists	of  sixteen  rounds in which the left com-
ponent L(i-1) is added modulo 2	to the output  of  a  non-
linear	function g whose input is both the right component
R(i-1) and part	of the	key  K(i).  The	 halves	 are  then
interchanged  to  form	the input for the next round (with
the exception of the final round). Finally the	output	is
permuted by IP-1 (the inverse of the input permutation IP)
to yield the output ciphertext Y.  For	details	 of  these
permutations,  and all the other functions in the DES, see
[ASA85], or any	of the modern  textbooks  on  cryptography
(eg [SeP89], [Den82]).

The cryptographic security of DES rests, in the	 main,	on
the  complex function g. It is shown in	more detail in Fig
2.8.  Its purpose is to	ensure that the	final  DES  output
vector Y (see Fig 2.7),	is a complex nonlinear function	of
the input, such	that there is no easy way of deriving  the
input  knowing	only  the output, short	of enumerating all
possible keys.	In detail, in round i, 1_<i_<16,	the  right
component  of  the  message input R(i-1) is first expanded
from 32	to 48 bits via an expansion function  E(R(i - 1)).
These are then XORd with a 48-bit component extracted from
the key	K(i) to	form vector A.	This vector is partitioned


			Chapter	2









			    22


into  eight  6-bit blocks which	are used as input to eight
substitution boxes (S-boxes). Each S-box produces a  4-bit
output,	 all  of which are concatenated	to form	the vector
B.  This vector	is permuted by P and then  XORd	 with  the
left component L(i-1) of the message. In more detail, each
S-box may be regarded as being composed	of four	 substitu-
tion functions (row functions or rows).	 The two (outer	or
selector) bits of the 6-bit input  selects  one	 of  these
four  functions,  which	then operate on	the four (inner	or
substitution) bits to give a 4-bit output.  This output	is
then  permuted	by  P. Together	these form one stage of	an
S-P network. The  repetition  of  this	procedure  sixteen
times forms the	full S-P network.






















		FFFFiiiigggg 2222....8888	---- DDDDEEEESSSS FFFFuuuunnnnccccttttiiiioooonnnn gggg


The other critical component in	the DES	algorithm  is  the
_k_e_y  _s_c_h_e_d_u_l_i_n_g	 stage.	 It is responsible for forming the
sixteen	48-bit sub-keys	used in	the rounds of the  encryp-
tion  procedure,  as  shown  in	Fig 2.9.  This function	is
important since	if the same  key  is  used  on	successive
rounds,	 it  can weaken	the resulting algorithm. This trap
is mostly avoided with the specified key scheduling  algo-
rithm,	except for a small number of keys known	as _w_e_a_k	or
_s_e_m_i-_w_e_a_k keys (see [GrT78],  [MeM82],	[MoS87],  [MoS86],
and [ASA85]).





			Chapter	2









			    23


























	      FFFFiiiigggg 2222....9999 ----	DDDDEEEESSSS KKKKeeeeyyyy	SSSScccchhhheeeedddduuuulllliiiinnnngggg


In detail, the 64-bit key is permuted by PC1. This  permu-
tation	performs  two functions. First it strips the eight
parity bits out. Then it distributes the remaining 56 bits
over two 28-bit	halves C(0) and	D(0).  Subsequently, these
form two distinct paths. At each round,	each 28-bit regis-
ter  is	rotated	left either one	or two places according	to
the schedule shown in Table 2.1.

   ____________________________________________________
  |	     TTTTaaaabbbblllleeee 2222....1111 ---- KKKKeeeeyyyy SSSScccchhhheeeedddduuuulllleeee ffffoooorrrr DDDDEEEESSSS	      |
  |_______________________________________________________________________________________________________|_
  |_R_o_u_n_d__|__1__2__3__4__5__6___7___8___9___1_0__1_1__1_2__1_3__1_4__1_5__1_6__|
  | Shift|  1 1	2 2 2 2	 2  2  1  2  2	2  2  2	 2  1 |
  |_______|_____________________________________________|
  |_T_o_t_a_l__||__1__2__4__6__8__1_0__1_2__1_4__1_5__1_7__1_9__2_1__2_3__2_5__2_7__2_8__|



After the shift, the resultant 28-bit vectors are permuted
by PC2 (which in fact consists of two 28-bit permutations,
not one	56-bit permutation), and are concatenated together
to  form  the  sub-key for that	round. Note that the total
number of shifts is 28;	hence C(16) = C(0),  and  D(16)	 =
 D(0).	When  decrypting,  it is necessary to generate the


			Chapter	2









			    24


keys in	reverse	order. Because the  final  vector  is  the
same  as  the initial vector, this can be done by rotating
right, reading the table in reverse  order  (and  with	no
shift  before  generating the first key). Thus,	with minor
changes, the same hardware is used for both encryption and
decryption.


_2._5.  _D_E_S _V_a_r_i_a_n_t_s

Given that it is generally accepted that the DES cipher	is
well  formed,  and  that  there	 are no	known shortcuts	to
cryptanalysing it, then	its main shortcoming appears to	be
its 56-bit key size, which is widely regarded as being too
small. Several variants	of DES have been developed.   Some
of  these  use the same	S-box and permutation P	structure,
but alter the key schedule  used.  They	 include  the  KSX
scheme	described  in  [Out86],	 and  the  extended KS128X
scheme [Out89].	In these schemes, Outerbridge has designed
a  key schedule	inspired by that used in Lucifer. KSX uses
a 64-bit key partitioned into 16 nybbles (of 4-bits each).
The  nybbles are selected according to a fixed permutation
and are	presented to the S-box inputs, and  then  the  key
register  is  rotated  1 nybble	before the next	round.	In
KS128X a 128-bit key is	used, partitioned into bytes,  the
lower 6	being selected as the partial key. Again the whole
register is rotated, this time by 5 bytes to the left.	It
is very	similar	to the schedule	used in	Lucifer.

The author believes this approach has advantages, particu-
larly  in  the use of a	much cleaner key schedule. However
it still retains the original  DES  S-P	 function.  Recent
developments,  referred	to later in this thesis	have indi-
cated how improvements can be made in this area	which will
result in a more secure	algorithm.

Other schemes retain the same overall structure, but  also
amend  the  function  f.  These	include	the family of sub-
tractive encryptors  [Mor83],  and  the	 layered  approach
[MoT86]. These schemes have not	been investigated further.


_2._6.  _F_E_A_L

The FEAL algorithm, developed by  researchers  at  NTT	in
Japan  is  one of the strongest	contenders amongst the new
set of private-key algorithms. It too is a Feistel cipher,
able  to encrypt 64-bit	data blocks with a 64-bit key.	It
has been optimised for implementation on eight-bit proces-
sors,  and  in hardware, and for this reason a very simple
function S is used to replace S-boxes in each round of the


			Chapter	2









			    25


cipher.	This function is used four times per round and is

	  T = X	 + X  +	D mod 256,	  D=0,1	  (Eq 2.2)
	       1    2

		   S(x,	y, D) =	ROT2(T)		  (Eq 2.3)

where ROT2 refers to a rotation	of 2 bits to the  left	of
an  8-bit  operand.   It is also used in the key schedule.
FEAL was originally described  as  a  4-round  version	in
[ShM88]. This version was subsequently broken [Boe89]. The
FEAL cipher was	then strengthened to an	 8-round  version,
and  a	challenge  was issued to anyone	who could break	it
[Miy90].   This	 version  has  also  been  implemeted	in
hardware,  as  described in [Miy88]. An	n-round	version	of
FEAL was also submitted	to the	European  RIPE	consortium
for  evaluation	as a possible authentication primitive for
use in the RACE	European high-speed network.

The author's main reservation about FEAL is in the  choice
of  the	function S (Eq 2.2). This function is near-linear,
in contrast to the conventional	wisdom that states that	 a
good  cryptographic  substitution  function  should  be	as
non-linear as possible.	Also, the absence of a permutation
means  that  the  dispersion of	bit dependencies of output
bits on	input and key occur  only  via	the  rotation  and
action	of  function  S, significantly slowing its disper-
sion. Biham and	Shamir [BiS90] in their	description of the
differential  cryptanalysis  technique,	 have  stated that
FEAL-8 may be broken using a known plaintext  attack.	It
appears	 clear	that more than 8 rounds	should be used for
this scheme.

_2._7.  _K_h_u_f_u, _K_h_a_f_r_e _a_n_d	_S_n_e_f_r_u

Khufu, Khafre and Snefru are a family of ciphers developed
by  Ralph Merkle from Xerox Parc. They are described in	an
internal report	which was subsequently published  (without
permission)  on	USEnet.	 A corrected version of	this paper
was presented to Crypto	 '89  by  Merkle.   Khufre  is	an
encryption  function  designed for fast	bulk encryption	of
data. It uses precomputed tables for speed. Khafre is also
an  encryption	function,  but	is designed for	encrypting
only small amounts of data. It uses a fixed set	of tables,
at  the	cost of	a more complex scrambling function in each
round. Snefru is a one-way hash	function which is used	to
reduce	a  message of arbitary length into a small residue
(of 64,	128, or	256 bits).

The basic design philosophy that Merkle	has used  is  that
of  a  Feistel	cipher,	 in  common with most of the other


			Chapter	2









			    26


modern private-key schemes.  However,  he  has	emphasised
ease  of  implementation  in  software.	In doing so he has
decided	that since table lookups will be used to implement
a  SP  function, rather	than doing 4 or	8 in parallel, and
ORing the results together, as would be	done  when  imple-
menting	 most  Feistel	ciphers,  he would incorporate the
results	from each lookup into the next stage.  Effectively
this  results  in  having  a much larger number	of rounds,
each of	which only maps	a 8-bits of input onto 32-bits	of
output,	 which	is  then  added	modulo 2 to the	other data
half. The input	half is	then rotated according to a  rota-
tion  schedule	to  bring a new	byte into position for the
next round. Overall, the same number of	table lookups  may
well result, depending on how many rounds are done. Merkle
claims that this process greatly improves  the	spread	of
dependencies of	output bits on input and key.

Rather than a standard key schedule component, Merkle  has
incorporated  the  key	into the schemes via either the	S-
boxes used, or the rotation schedule. In Khufu,	the key	is
used, along with an initial set	of S-boxes, to dynamically
calculate a  pseudo-random  set	 of  S-boxes  for  use	in
encrypting  the	 message.  The	key  is	 also expanded and
summed modulo 2	to the data at the start and  end  of  the
data  process.	 In  Khafre, a standard	set of S-boxes are
used, and  the	key  is	 incorporated  into  the  rotation
schedule. In Snefru, the standard S-boxes are also used	in
the hashing process.

For more details on these algorithms see Merkle	[Mer89]

Merkle has subsequently	announced that a 2  round  version
of  Snefru has been broken by Eli Biham	from Israel, in	an
article	to the USEnet news network on 19  April	 1990.	He
has  subsequently recommended that at least a 4	round, and
probably 8 round version should	be used. A $1000 prize	is
offered	 to  anyone  who can break the 4 round version,	in
the same article.

The author believes that these	ciphers	 incorporate  some
interesting concepts. However, the author has major reser-
vations	about the use of random	S-boxes	in the	encryption
function in each round.	All the	research to date indicates
that the role of these functions in providing confusion	of
the  input  are	critical to the	security of the	cipher.	If
the encryption functions should	be linear or near  linear,
a  significant	advantage  is given to the cryptanalyst. A
further	problem	with these schemes is that whilst the idea
of running the table lookups serially is fine, in practice
Merkle has recommended a number	of rounds that is far  too
small.	Since Bihar and	Shamir [BiS90] report that 8 round


			Chapter	2









			    27


versions of traditional	Feistel	 ciphers  can  be  broken,
this  would  seem  to  indicate	 that  32  to 64 rounds	of
Merkle's ciphers would be required  for	 equivalent  secu-
rity, rather than the 4	or 8 he	nominates.

_2._8.  _L_O_K_I

The LOKI scheme	is the latest of the new private key block
algorithms.   It  was developed	by the author and his col-
leagues	Professor Jennifer Seberry and Dr. Josef Pieprzyk.
It  is	a  family of block ciphers, with Feistel structure
similar	to  the	 DES,  but  with  a  much  simplified  key
schedule, and different	permutation and	substitution func-
tions. It is the major achievement of this thesis, and	is
documented in Chapter 7.

_3.  _P_u_b_l_i_c-_K_e_y _C_r_y_p_t_o_g_r_a_p_h_y

_3._1.  _I_n_t_r_o_d_u_c_t_i_o_n

_P_u_b_l_i_c-_K_e_y _C_r_y_p_t_o_g_r_a_p_h_y	(PKC), or _T_w_o-_K_e_y _C_r_y_p_t_o_g_r_a_p_h_y was
originally proposed in a pivotal paper by Diffie and Hell-
man [DiH76], who developed the	concept,  and  proposed	 a
possible  scheme.  It  was also	developed independently	by
Merkle [Mer78] who outlined the	basic  concepts,  but  did
not  propose  a	feasible system.  Such schemes provide the
ability	to publish an encryption key (used to conceal  the
message)  in  the  equivalent  of  a  telephone	directory,
without	compromising the decryption key	(used  to  restore
the  message),	and hence the secrecy of the message. This
distinction from traditional private-key schemes was shown
in Figs	1.1 and	1.2.

More formally, in a PKC	the enciphering	(concealing) algo-
rithm  E  , and	deciphering (restoring)	algorithm D  , are
	K1					   K2
controlled by  two  distinct  pieces  of  information,	an
_e_n_c_r_y_p_t_i_o_n  _k_e_y	K1, and	a _d_e_c_r_y_p_t_i_o_n _k_e_y K2, with the pro-
perty that it is computationally infeasible to compute the
decryption  key	 DK   from the encryption key K1. Computa-
tionally infeasible2implies that with the speed	of comput-
ers  currently	available,  the	 time  taken  to break the
scheme is unreasonably large (usually at  least	 of  order
years, if not orders of	magnitude greater). This contrasts
with the keys used in traditional  Private Key	Cryptosys-
tems  where  the encryption and	decryption keys	are either
identical, or can easily  be  computed	from  each  other.
Before	a secure communications	channel	can be established
using such a scheme, this key must be exchanged	over  some
other  secure  channel,	traditionally by courier. If there
are n participants, then up to n_(_n_-_1_)_ keys would  have	to
				 2

			Chapter	2









			    28


be exchanged in	advance, a practical impossibility for any
reasonably sized n. Thus  traditionally	 cryptography  has
had  applications limited to use in hierarchical organiza-
tions where the	number	of  links  can	be  minimised  and
predicted in advance.  In contrast a PKC encryption key	K
can be placed in a public directory, for use by	anyone wh1o
wishes	to  communicate	 securely with the holder, without
compromising the decryption key	K , and	without	them  hav-
ing  to	have anticipated the need2to communicate with each
other.	Consequently it	enables	the possibility	 of  users
on an electronic network to communicate	securely with each
other with little more difficulty than	that  required	to
establish a link between them.

A relative of a	PKC is a  _P_u_b_l_i_c-_K_e_y  _D_i_s_t_r_i_b_u_t_i_o_n  _S_c_h_e_m_e
(PKDS).	 In a PKDS, the	two participants exchange messages
until a	common key is known by each, which it is  computa-
tionally  infeasible  to  compute by any eavesdropper from
the messages exchanged.	This common key	is then	used in	 a
Private	 Key  Cryptosystem.  Obviously any PKC can be used
as a PKDS. The main reason for using a PKDS rather than	 a
PKC  is	that public key	functions tend to be difficult and
slow to	implement, thus	in a PKDS it  need  only  be  done
once  per  session,  rather  than continuously.	Also, some
PKDS are easier	to implement than a fully fledged PKC. The
original  scheme proposed by Diffie and	Hellman	was such a
PKDS. Many current  "public-key"  implementations  are	in
fact PKDS, where a Private-Key scheme is used to carry the
bulk of	the traffic for	a session.

Given the obvious  advantages  of  public-key  schemes	in
modern applications, the obvious question is why they have
not yet	been extensively used. The answer lies partly with
the inate conservatism of some of these	fields,	who prefer
to wait	until  the  security  of  such	schemes	 has  been
repeatedly  confirmed (a valid stance, given that one pro-
posed class of schemes,	low-density knapsack PKC  such	as
the Merkle-Hellman scheme have all proved to be	insecure),
but mostly from	the computational complexity  involved	in
implementing many of these schemes.  That is, they involve
using operations such  as  exponentiation  on  very  large
numbers, which,	as we shall see	later, take a considerable
amount of time.	Consequently, they are simply not able	to
compete	with the speed of Private-Key schemes such as DES.
Although a considerable	amount of effort is being expended
to  improve their performance, and indeed some progress	is
being made, nonetheless	it appears that	we  need  to  wait
for computational speeds to increase further, before these
schemes	become widely used.  Meanwhile the  major  use	at
present	 and  for  the	short  term  future, of	public key
schemes	is in  hybrid  systems,	 in  which  a  public  key


			Chapter	2









			    29


algorithm  is  used to exchange	a session key, and to pro-
vide authentication and	 non-repudiation,  whilst  a  fast
private	key scheme is used to provide privacy.

One of the major advantages of PKC's is	 their	relatively
straightforward	 and  simple mathematic	description, which
contrasts strongly with	the opaqueness of such private key
systems	as DES.	Public key schemes are based on	a class	of
functions known	as  one-way  trapdoor  functions,  derived
from  a	class of computationally difficult problems termed
NP (non-deterministic polynomial) problems  (see  Williams
[Wil82]).  Private  key	 schemes,  in  contrast, rely on a
series of substitution and transposition operations  which
are  very complex to analyse mathematically.  Consequently
there is a chance of providing a mathematical proof of the
security  of PKC's, which is not possible with private key
schemes.  Although no  conclusive  proofs  have	 yet  been
obtained, Brassard [Bra79] has shown that for both the RSA
and the	Diffie-Hellman key distribution	schemes	if a  suc-
cessful	 cryptanalytic	attack	is  possible in	polynomial
time then it would imply that NP=CoNP, a  result  that	is
regarded  as improbable	at present, and	is thus	indicative
of the probable	security of these schemes.

An excellent introduction to number theory and its  appli-
cations	is the book by Schroeder [Sch84], which	introduces
the various axioms and	theorems  in  number  theory,  and
illustrates  their  applications  in  many diverse fields,
including cryptography.	A synopsis of the material covered
in the book is given in	his paper [Sch85].  An overview	of
the area's of mathematics used in cryptology, including	in
PKC's,	along with a number of simple examples is given	by
Simmons	[Sim79b].

An overview of computational complexity	is provided in the
Turing	Award  lecture by Cook,	reprinted in [Coo83].  Yao
[Yao82]	presents an introduction to extensions to Informa-
tion  Theory made possible by using the	concepts developed
in modern computational	complexity theory.  He provides	 a
precise	 definition  of	 trapdoor  functions and describes
their applications in cryptography,  pseudo-random  number
generation and abstract	complexity theory.

_3._2.  _P_u_b_l_i_c-_K_e_y _D_i_s_t_r_i_b_u_t_i_o_n _S_y_s_t_e_m_s (_P_K_D_S)

_3._2._1.	_D_e_s_c_r_i_p_t_i_o_n

The first type of system developed to use the  concept	of
publicly  available  cryptographic keys	was the	public key
distribution system (PKDS).  A PKDS permits two	 users	to
exchange  a  private  key  over	an insecure channel.  Once


			Chapter	2









			    30


this private key is exchanged, it is  used  in	a  conven-
tional	private	 key  cipher.  This approach to	public key
systems	is of considerable interest since the  "expensive"
calculations needed for	the public key component need only
be done	infrequently on	relatively small  blocks  of  data
(namely	 the  key),  and then fast hardware implementing a
private-key scheme may be used to exchange the actual mes-
sages  needed in that session.	This form of hybrid system
has already been implemented by	a number of  people.   The
feature	 distinguishing	 a  PKDS  from	a  PKC is that the
private	key exchanged is determined solely from	the publi-
cally distributed keys,	and cannot be any arbitrary value.

In their original paper	Diffie and Hellman  [DiH76],  pro-
posed  a  PKDS,	 whose security	rests on the difficulty	of
computing discrete logarithms over a  finite  field  GF(q)
where q	is prime. Let

    Y =	AX (mod	q),	    for	1 _< X _<	q-1,	  (Eq 2.4)

where A	is a fixed primitive element of	GF(q); then  X	is
referred to as the logarithm of	Y to base A (mod q).  Cal-
culation of Y from X is	relatively easy,  taking  at  most
2 log q	 multiplications   (Knuth  [Knu81]), and with more
recent algorithms and special hardware,	possibly much fas-
ter. However computing X from Y	is still regarded as being
very difficult,	though the modulus of  the  field  in  use
needs to be chosen carefully, (see Odlyzko [Odl84]).

In the Diffie-Hellman scheme each user generates a  random
number	X ,  chosen  from  the	set  [1,q-1], and keeps	it
secret whiilst publishing Y  s.t.
			  i
	  Xi					  (Eq 2.5)
    Yi = A   mod q,

in a public file along	with  their  name  and	electronic
address.  When two users i and j wish to communicate, they
use as a key Kij s.t.
	   X  X
    K	= A i  j mod q				  (Eq 2.6)
     ij

	   Xi
	= Yj   mod q	    (which user	i can compute)

	   X
	= Y j  mod q	    (which user	j can compute)
	   i
Both users i and j can compute K    efficiently.   However
any  other  user would have to ciojmpute K   from	Y  and Y ,
					ij	 i	j

			Chapter	2









			    31


which would require computing the  discrete  logarithm	of
one of these; ie

	   logAYj				  (Eq 2.7)
    Kij	= Yi	  mod q.

Hence the security of this scheme rests	on the	difficulty
of  computing these logarithms.	This is	known to be a hard
problem, currently orders of magnitude more difficult than
the effort needed to exchange keys.

_3._2._2.	_I_m_p_l_e_m_e_n_t_a_t_i_o_n

Several	hybrid public-key, private-key systems	have  been
implemented  using  the	 Diffie-Hellman	PKDS to	exchange a
session	key subsequently used by  a  DES  encryptor  chip.
Mitre  Corporation have	developed such a system	for use	on
their LAN. It uses a Z-80 microprocessor  to  perform  the
public	key  exchange,	and  a	DES chip for the main data
encryption operations; Berkovits, Kowalchuk and	 Schanning
[BKS79],  and  Hershey [Her80].	 A hardware implementation
of the public key part of this system was done by  Hewlett
Packard, Yiu and Peterson [YiP82], which increased the key
encryption rate	from 25	bits/sec to 3 Kb/sec. Subsequently
Mitre  designed	a VLSI parallel/pipeline processor to per-
form these modular  exponentiations,  Fam  [Fam82].127 When
designing  the implementation used, the	field GF(2   ) was
chosen since it	has a number of	computational  advantages,
which  make  it	 easy  to  implement  efficiently  in both
hardware and software.	However	 Gait  [Gai79],	 Herlestam
[HeJ81],  Mullin  [MNW84],  and	 Odlyzko [Odl84] show that
because	of these advantages the	 field	is  insecure  with
respect	 to computing discrete logarithms, and hence cryp-
tosystems based	on it must be  regarded	 as  having  being
compromised for	all but	the lowest level of security.

Additional  PKDS  schemes  are	 defined   in	Matsumoto,
Takashima  and	Imai [MTI86], which presents a classifica-
tion of	the proposed schemes, determines the most computa-
tionally  efficient,  and  shows  that it is equivalent	in
security to the	original Diffie-Hellman	scheme.

El Gamal [ElG85] describes  a  true  PKC  related  to  the
Diffie-Hellman PKDS. This scheme also relies on	the diffi-
culty of computing discrete logarithms for  its	 security.
It is regarded as a serious alternative	to RSA for authen-
tication and key exchange uses,	 but  like  RSA,  requires
efficient modular exponentiation.





			Chapter	2









			    32


_3._3.  _T_h_e _R_i_v_e_s_t-_S_h_a_m_i_r-_A_d_l_e_m_a_n	(_R_S_A) _P_K_C

Rivest,	Shamir and  Adleman  [RSA78]  outlined	the  first
practical and fully-fledged public key cryptosystem (RSA),
the security of	which is based on the difficulty  of  fac-
toring	large  integers.   This	 system	 is still the most
highly regarded, and is	the one	 most  commonly	 suggested
for  use  in public key	systems.  It has been placed as	an
appendix in a number of	standards related to key  exchange
in Electronic Funds Transfer (EFT) schemes, in the authen-
tication of certificates issued	by an Electronic Directory
Service,  and  in  the	authentication	of participants	in
wide-area networks.  Zimmerman [Zim86] outlines	in detail,
a set of protocols which could form the	basis of an indus-
try standard for RSA usage.

The major advantages of	RSA are	that it	does not  increase
the size of the	message	and that it may	be used	to provide
both privacy and authentication	(by  providing	a  digital
signature)  over communications	links.	Its main disadvan-
tage is	its reliance on	modular	exponentiation,	an  opera-
tion which is still moderately time consuming, though much
effort is being	expended to improve the	efficiency of this
operation.


_3._3._1.	_A_n _O_v_e_r_v_i_e_w _o_f _R_S_A

In the RSA system, each	user wishing to	receive	 encrypted
messages, performs the following steps:

+o     selects two large	primes p and  q	 at  random,  each
     about  100	 digits	 long  (for  key  lengths believed
     secure at present),

+o     calculates the modulus of	their system R = pq,

+o     selects at random	a number e with	 e<R, GCD(e,U(R))=
     1,	 where	 U (R)	= (p-1)(q-1), is the Euler totient
     function of R, (and e is usually small,  for  example
     3,	 and  may be fixed for all users [QuC82], [Wil86],
     [KBS86b], and [KBS86a]).

+o     solves for the unique  d	in  the	 congruence  de	 _=
      1	(mod U(R)),  0 _< d < R,

+o     broadcasts the public key	E = <e,R>

+o     and keeps	secure the private key D = <d>.




			Chapter	2









			    33


A sender can encrypt a message M (expressed as some  large
integer	of a size less than the	length of the modulus used
in the system, and  created  by	 concatenating	characters
together  to  form a bit-string	of the appropriate length)
to form	the ciphertext C using the public  encryption  key
<e,R> by calculating:

    C =	Me (mod	R), 0 _<	C < R			  (Eq 2.8)

The receiver can then  decipher	 this  using  his  private
decryption key <d> by calculating:

    M =	Cd (mod	R)				  (Eq 2.9)

The system relies on  the  following   well  known  number
theoretic  identity  (Euler's  generalization  of Fermat's
theorem):

    If GCD(X,R)	= 1,				 (Eq 2.10)


       then XU(R) _= 1 (mod R)	hence


    Cd = Med _= M1+nU(R)	_=


	 M1MnU(R) _= M1 _= M (mod	R).


RSA can	also be	used  as  a  signature	scheme	since  the
encryption  and	 decryption  operations	 are  commutative.
That is, a sender can create a signature S for a message M
using  their  private key <d> (which only they have access
to), by	calculating:

    S =	Md (mod	R)				 (Eq 2.11)

which may be verified by anyone	using the sender's  public
key  <e,R> (obtained from the public directory), by calcu-
lating:

    M =	Se (mod	R),				 (Eq 2.12)

The signature can then be encrypted using the  recipient's
public key, in order to	privately transfer it to the reci-
pient.






			Chapter	2









			    34


_3._3._2.	_R_S_A _W_e_a_k_n_e_s_s_e_s _a_n_d _R_e_l_a_t_e_d _S_c_h_e_m_e_s

There is a minor problem known as the signature	reblocking
problem,  which	 must  be overcome when	the same scheme	is
used for  both	secrecy	 and  authentication.	It  occurs
because	 each  user  has modulii R of different	sizes, and
hence a	block of ciphertext in one user's field	may not	be
a  valid  block	 in  the other users field. This becomes a
problem	when user A signs a message for	B, and then wishes
to  protect its	privacy	by encrypting with B's public key.
If user	A's field is larger than B's, and the signed  mes-
sage  also  turns  out	to be too large	(ie R  < S   <R	),
					  eB B	  AB   A
then it	cannot be directly encrypted (ie SAB (mod RB) can-
not  be	decrypted correctly).  Several strategies are sug-
gested to overcome  this  problem.   These  include  using
separate  modulii  for	secrecy	 and  for  authentication,
guaranteeing that the signature	modulii	is always  smaller
than  any secrecy modulii [RSA78], and reversing the order
of signature and secrecy encryptions,  since  these  func-
tions  are commutative [Koh78].	 Alternatively the problem
may be avoided by using	a hashing function to compress the
message	into a single block, which is then signed with the
private	key only. Because a one-way function  is  used	to
perform	 the hashing operation,	no significant information
is conveyed about the content of  the  message.	 Hence	no
secrecy	step is	needed.	[Dav83], [Den83], [Den84].

Another	problem	caused	by  RSA	 being	an  authentication
scheme	as well	as a privacy scheme, is	that it	is exposed
to attack when a cryptanalyst is permitted to obtain  sig-
natures	on arbitrary messages of his choice, and thus over
several	messages build up enough information to	break some
other message.	Denning	[Den84]	proposes a method of form-
ing signatures by performing a transformation on the  ori-
ginal  message,	 which	both  overcomes	this weakness, and
reduces	the computation	involved in  creating  the  signa-
ture.

A number of other attacks have been suggested on  the  RSA
system.	 The  first was	by Simmons and Norris [SiN77], and
was rebutted by	Rivest in [Riv78]. Then	Herlestam  [Her78]
suggested  a generalised form of attack, based on iterated
encipherment of	 the  ciphertext,  and	dependent  on  the
number	of  fixed  points in the encryption function. This
was refuted by Rivest [Riv79], who indicated errors in the
analysis.   Williams  and  Schmid  [WiS79]  analysed  this
attack and several others, and indicated  some	conditions
on  the	 primes	p and q	which minimised	the possibility	of
such attacks.  Gordon [Gor84] in  a  key  paper	 collected
these  various	requirements, analysed all of the proposed


			Chapter	2









			    35


attacks	on the RSA system, and outlined	an  algorithm  for
generating  primes  p and q which satisfied all	the condi-
tions necessary	to minimise the	chance of success  of  any
of these attacks, and thus construct a secure system. This
algorithm has been suggested as	the basis of  an  appendix
on  generating p and q in several standards suggesting the
use of RSA.

The security of	the RSA	system is known	to be at  most	as
difficult  as  factoring the modulus R=pq. It is not known
whether	it is as difficult as  that.   Rabin  [Rab79]  has
proposed a PKC scheme, related to RSA, for which it may	be
proved that cracking the scheme	is equivalent to factoriz-
ing  the  modulus.  Williams [Wil80]  and [Wil84] has also
derived	such an	encryption scheme for which this is  true.
However	 because of the	constructive nature of this proof,
the Williams systems are open to chosen	ciphertext  attack
under  certain	conditions. Hence these	schemes	are not	as
highly regarded	as RSA,	and are	of interest mostly because
of   the  proof	 of  difficulty	 of  breaking  them  being
equivalent to factoring	provides  further  indications	of
the difficulty of cracking the similar RSA scheme.

Another	related	alternative scheme is proposed in  Kravitz
and  Reed  [KrR82a], [KrR82b]. The security of this system
is based on the	difficulty of determining the  degrees	of
the irreducible	factors	of a high-degree polynomial. It	is
not as secure as the RSA scheme, however it is interesting
in  that  it  presents	a generalization of the	RSA scheme
into a polynomial ring message space.

A recent comparison of the relative security  of  RSA  and
the ElGamal schemes is given in	[Oor91].

_3._3._3.	_I_m_p_l_e_m_e_n_t_a_t_i_o_n

Muller [Mul83] describes the development of  a	cryptopro-
cessor,	 a  microprocessor-based board added to	a worksta-
tion, which handles all	the  tasks  necessary  to  support
secure	communications	links  between	workstations. This
system uses an 8086 microprocessor to perform  the  house-
keeping	tasks and the public key (RSA) key encryption; and
a WD2001  DES  chip  to	 perform  high-speed  private  key
encryption.  The  whole	 system	is contained on	a Multibus
board which may	be  plugged  into  a  workstation.  It	is
assumed	 that  there  is a secure host on the system which
can act	as a name and public key server. For key sizes	of
288  bits  it  took  about  4  minutes	to perform the two
encryptions needed for a secret	and  signed  letter.  They
conclude   that	 this  performance  could  undoubtably	be
improved with better algorithms	or special hardware.


			Chapter	2









			    36


Serpell, Brookson and Clark [SBC84] suggest the	use  of	 a
stand-alone  unit  which may be	connected between an RS232
terminal and its host or modem to  perform  the	 necessary
link  encryption.  Each	 users	key  certificate  would	be
stored on a magnetic key inserted into	this  device,  and
would  be  created  by	a  secure  central  key	certifying
authority whose	public key is  well  known.   Users  would
exchange  key  certificates  over  the unsecure	link, from
which the other's public key may be  obtained.	 The  unit
developed  was	based on an 8085 microprocessor	performing
the housekeeping, a hardware exponentiator built using TTL
logic,	and a British Telecom B-Crypt private key chip.	It
could exchange 512-bit session keys in 3 seconds.

Jackson, McEnvoy and Newman [JMN84] describe  the  Project
Universe  experiment,  in  which local area, and wide area
networks are linked, with optional transport layer encryp-
tion. They used	RSA as a PKDS to exchange DES master keys,
which in turn were used	to exchange session keys.  Perfor-
mance  measurements  indicate  that  the use of	encryption
added only a constant overhead,	which  was  not	 of  major
significance, especially on the	wide-area links.

Brickell provides a brief survey of  hardware  implementa-
tions of RSA in	[Bri90].

_4.  _F_u_r_t_h_e_r _R_e_a_d_i_n_g

A survey of modern cryptographic techniques may	 be  found
in  Diffie  and	Hellman	[DiH79], who provides an introduc-
tion to	cryptographic fundamentals, a taxonomy of  crypto-
graphic	systems	both private and public-key, a description
of some	of  the	 practical  problems  encountered,  and	 a
review	of  their  various applications.  More specialised
coverage may be	found  in  Computing  Surveys  11(4)  1979
which  contains	 three	articles  ([Lem79],  [Sim79a], and
[PoK79]) surveying the status of cryptology at that  time.
There is a particular emphasis on the emerging PKC, and	on
the evolution of the relevance of  cryptology  from  being
strictly  a  government	 and military concern, to being	of
major interest to business (especially banking), and even-
tually	to  the	 public	 as  well. This	trend continues	as
electronic messaging and funds transfer	becomes	more  pre-
valent.	  Other	 popular  introductions	to, and	surveys	of
public key systems  are	 given	by  Simmons  [Sim79b]  who
presents  a  popular summary of	these recent developments,
Hellman	[Hel79b] who presents an overview of the mathemat-
ics  used  in  public  key  schemes, and Beker [Bek84] who
presents a brief survey	of currently used encryption tech-
niques.	  Simmons  [Sim82]  collects  all the original key
papers on public key systems, along with  some	commentary


			Chapter	2









			    37


into  one  book.   Denning [Den82] provides an overview	of
encryption techniques and access control methods, as  used
in  current  computing	and  data  communications systems.
Seberry	and Pieprzyk in	their  book  [SeP89]  provide  the
latest	survey of the field, and is an excellent introduc-
tory text.

_5.  _C_o_n_c_l_u_s_i_o_n_s

This chapter provides the background  information  on  the
design	of modern private and public key schemes which was
used as	the basis from which the research  detailed  later
in this	thesis was developed.








































			Chapter	2









			    38























































			Chapter	2












			CCCCHHHHAAAAPPPPTTTTEEEERRRR	 3333


TTTTeeeecccchhhhnnnniiiiqqqquuuueeeessss ffffoooorrrr IIIImmmmpppplllleeeemmmmeeeennnnttttiiiinnnngggg tttthhhheeee	RRRRSSSSAAAA PPPPuuuubbbblllliiiicccc KKKKeeeeyyyy CCCCrrrryyyyppppttttoooossssyyyysssstttteeeemmmm




_1.  _I_n_t_r_o_d_u_c_t_i_o_n

From the preceeding survey  of	cryptographic  algorithms,
public-key  cryptosystems  are shown to	embody a number	of
desirable properties.  In particular, when used	in a large
network,  with	participants  previously unacquainted, the
ability	to exchange public-keys	 is  highly  desirable	in
providing efficient communications.

For practical use though, these	schemes	need  to  be  fast
and  efficient.	  This	chapter	will examine in	detail the
implementation of the most common public-key cryptosystem,
RSA.  It  will show that the essential exponentiation com-
ponent of the RSA scheme is inherently time-consuming, and
that  the best generally available implementations, whilst
being suitable for key-exchange	 and  authentication,  are
not  fast  enough  for	providing  secrecy  of all traffic
exchanged. Further, whilst dealing specifically	with  RSA,
most of	these comments are equally applicable to the other
exponentiation based public-key	schemes	including  Diffie-
Hellman	[DiH76], and ElGamal [ElG85].

It will	conclude that a	 complete  security  package  will
need  to  incorporate a	fast, efficient	and secure private
key cryptosystem in a hybrid scheme, in	order to provide a
total  solution.  The remainder	of this	thesis will detail
the development	of suitable private key	schemes	 for  this
use.

_2.  _R_S_A	_E_n_c_r_y_p_t_i_o_n _a_n_d _D_e_c_r_y_p_t_i_o_n

The RSA	public-key cryptosystem	has been described in  the
preceeding  chapter.   Fundamental to the RSA algorithm	is
the modular exponentiation of very large integers,  of	up
to  200	 digits	 (or 600 bits) in length. These	very large
numbers	are  necessary	to  ensure  the	 security  of  the
scheme,	 as the	effort needed to break the scheme (by fac-
toring the modulus R), is of O(ef(R)), an exponential of a
function  f  on	 the  modulus R.  The best currently known
algorithm for factorizing a number R with  a  large  prime
factor	p is a variation on Lenstra's elliptic curve algo-
rithm proposed by Brent	[Bre86], which runs in time



			    39









			    40

			 ___________
		       \|ln p lnln p
		    O(e______________)		  (Eq 3.1)
			   lnp
and which leads	to the choice of R around 200  digits  (or
600 bits) in length [DHS84], [Bre86]


Table 3.1 provides a comparison	of the effort required for
encryption   and   factorisation   based  on  various  key
lengths[1].

      ______________________________________________
     | TTTTaaaabbbblllleeee 3333....1111 ---- CCCCoooommmmpppplllleeeexxxxiiiittttyyyy ooooffff FFFFaaaaccccttttoooorrrriiiizzzzaaaattttiiiioooonnnn aaaannnndddd |
     |______E_EEEx_xxxp_pppo_ooon_nnne_eeen_nnnt_ttti_iiia_aaat_ttti_iiio_ooon_nnn_O_OOOp_pppe_eeer_rrra_aaat_ttti_iiio_ooon_nnns_sss_M_MMMo_oood_dddu_uuul_lllo_ooo_R_RRR______|
     | Digits in R|  Operations	in|  Operations	in |
     |		  |  Factorization|  Exponentiation|
     |_____________|________________|_________________|
     |	   20	  |	7.2e+03	  |	8.0e+03	   |
     |	   40	  |	3.1e+06	  |	6.4e+04	   |
     |	   60	  |	4.6e+08	  |	2.1e+05	   |
     |	   80	  |	3.7e+10	  |	5.1e+05	   |
     |	   100	  |	1.9e+12	  |	1.0e+06	   |
     |	   120	  |	7.6e+13	  |	1.7e+06	   |
     |	   140	  |	2.3e+15	  |	2.7e+06	   |
     |	   160	  |	5.9e+16	  |	4.0e+06	   |
     |	   180	  |	1.2e+18	  |	5.8e+06	   |
     ||_____2_0_0______|_____2_._3_e_+_1_9_____|_____8_._0_e_+_0_6______||


Since no conventional computers	support	 integer  calcula-
tions of this size, the	problem	can be approached from two
basic directions. One is to break the numbers  into  words
of  a  size supported by the hardware on current machines,
and carry out each step	of the calculation in a	number	of
stages	using multi-precision arithmetic.  The other tech-
nique is to design and build  specialised  hardware  which
supports  the  large  wordsize	required.  Both	 of  these
methods	have been attempted, and both can utilise some	of
the techniques described below.




____________________

   [1] currently 1e+16 operations is regarded as  a  limit
for  computational  feasibility	 (ie  1	year on	a 1000 MIP
machine).   Times  may	be   derived   by   assuming   one
instruction  per  microsecond  on  a  1	 MIP  machine, and
knowing	that there are 3e+13 microseconds in a year.



			Chapter	3









			    41


    _________________________________________________
   |_T_TTTa_aaab_bbbl_llle_eee_3_333._...2_222_-_---_E_EEEx_xxxa_aaam_mmmp_pppl_llle_eee_o_ooof_fff_L_LLLo_ooon_nnng_ggg-_---h_hhha_aaan_nnnd_ddd_M_MMMu_uuul_lllt_ttti_iiip_pppl_llli_iiic_ccca_aaat_ttti_iiio_ooon_nnn_|
   |	 452		    |	   452		    |
   |   * 125		    |	 * 125		    |
   |  ______		    |	______		    |
   |	2260   (* 5*1)	    |	   452	 (* 1)	    |
   |			    |	______		    |
   |			    |	  4520	 (pp *10)   |
   |  +	9040   (* 2*10)	    |	 + 904	 (* 2)	    |
   |  ______		    |	______		    |
   |  =11300   (pp step	1)  |	= 5424	 (pp step 2)|
   |			    |	______		    |
   |			    |	 54240	 (pp *10)   |
   |  +45200   (* 1*100)    |	+ 2264	 (* 5)	    |
   |  ______		    |	______		    |
   |  =56500   (Result)	    |	=56500	 (Result)   |
   |  ______		    |	______		    |
   |_________________________|________________________|
   |	  RRRRiiiigggghhhhtttt----TTTToooo----LLLLeeeefffftttt	    |	   LLLLeeeefffftttt----TTTToooo____RRRRiiiigggghhhhtttt    |
   ||_______E_EEEv_vvva_aaal_lllu_uuua_aaat_ttti_iiio_ooon_nnn________|_______E_EEEv_vvva_aaal_lllu_uuua_aaat_ttti_iiio_ooon_nnn_______||


In multi-precision arithmetic the calculation is  done	on
each  digit  of	 the number in succession, with	a carry	or
borrow being propagated	into the next word of the  number.
The  size  of  the digit used depends on the complexity	of
the algorithm, and on the word size  of	 the  machine  (or
specialised hardware) being used. The algorithms needed	to
do this	are well known,	and may	be found in Knuth [Knu81],
and  also  in  Schroeder's  excellent introductory text	to
number theory  applications  [Sch84].	The  basic  multi-
precision  multiplication algorithm they describe, runs	in
O(n2) time on a	number n bits in length.  This corresponds
to performing long-hand	multiplication of decimal integers
(Table 3.2); which can be done	either	right-to-left,	or
left-to-right.	 The  former  is  more	usual,	though the
latter is often	more convenient	for  computer  implementa-
tion.

Since in RSA, both encryption and decryption involve modu-
lar  multiplication,  a	 division  stage must be performed
after the multiplication to extract the	remainder (mod R).
Several	 techniques  have  been	 suggested to minimise the
time taken by this process.

One is to precompute a multiplication table for	one of the
operands,  and use it to perform the multiplication with a
series of additions and	table lookup steps,  as	 described
by Henry [Hen81] and Quisquater	et al. [QuC82].




			Chapter	3









			    42


Another	is to perform the  modulo  reduction  in  parallel
with  each  stage  of  the  multiplication calculation,	by
removing  the  most  significant  digit,  and  adding  its
remainder  (mod	 R)  to	 the  partial  sum.  This  process
achieves a saving by a factor of about 6, and  the  author
strongly  recommends  that  it	be used.  It is	based on a
result presented in the	paper by  Chivers  [Chi84],  which
states that

		   (n-1	   i)
		   | R ai b |(mod m) _=		  (Eq 3.2)
		   (i=0	    )

     (n-2    i	      n-1	 )
     | R ai b  + an-1b	 (mod jm)|(mod m), for all j
     (i=0			 )
The technique is described  by	Chivers	 [Chi84],  Blakley
[Bla83], and Willoner et al. [WiC81] and produces a result
that it	is never larger	than n + ln n bits long.  In  more
detail,	 it  involves  removing	the most significant digit
(MSD) of the result, and adding	its remainder mod m to the
number	represented  by	the remaining digits. To use it, a
table is constructed of	these remainders for all  possible
digits.	  The  size  of	the table obviously depends on the
size of	the base used.	Typically bases	of 1, 4, or 8 bits
are used, leading to table sizes of 1, 16, or 256 entries.
See Tables 3.3 and 3.4 for examples (which  are	 presented
in  base  10). This process can	be generalised to an algo-
rithm for reducing any number larger than the modulus down
until it has no	more digits than the modulus, by iterating
over all digits	larger than the	modulus	length,	and  scal-
ing up the remainders appropriately.


       ____________________________________________
      |_T_TTTa_aaab_bbbl_llle_eee_3_333._...3_333_-_---_N_NNNu_uuum_mmmb_bbbe_eeer_rrr_a_aaan_nnnd_ddd_R_RRRe_eeem_mmma_aaai_iiin_nnnd_ddde_eeer_rrr_(_(((m_mmmo_oood_ddd_5_5551_1117_777)_)))_|
      |		     n		    |  n (mod 517)|
      |______________________________|______________|
      |		    1000	    |	   483	  |
      |		    2000	    |	   449	  |
      |		    3000	    |	   415	  |
      |		    4000	    |	   381	  |
      |		    5000	    |	   347	  |
      |		    6000	    |	   313	  |
      |		    7000	    |	   279	  |
      |		    8000	    |	   245	  |
      ||_____________9_0_0_0______________|______2_1_1______||






			Chapter	3









			    43


	__________________________________________
       |_T_TTTa_aaab_bbbl_llle_eee_3_333._...4_444_-_---_E_EEEx_xxxa_aaam_mmmp_pppl_llle_eee_o_ooof_fff_M_MMMo_oood_dddu_uuul_lllo_ooo_R_RRRe_eeed_dddu_uuuc_ccct_ttti_iiio_ooon_nnn__|
       |   4120	  (mod 517)			 |
       | ______					 |
       |   0120	  (remove MSD)			 |
       |  + 381	  (add remainder of 4000 mod 517)|
       | ______					 |
       |  = 501	  (result mod 517)		 |
       |					 |
       |__________________________________________|



Some, or all of	the above techniques could be used  by	an
implementor  in	 conjunction  with  a  conventional multi-
precision  arithmetic  package.	  Alternatively	  one	of
several	fast multiplication algorithms,	followed by a fast
division algorithm designed for	this application, could	be
used.  This technique is outlined by Mohan et al. [MoA85].
Asymptotically,	the fastest integer  multiplication  algo-
rithm  known, is the Schonhage-Strassen	Algorithm [AHU74].
It is one of a family of algorithms which break	the number
into blocks, and treat each block as the coefficients of a
polynomial.  The polynomials  are  evaluated  at  suitable
points,	 the  products calculated, and the product polyno-
mial found by interpolation. Any one of	a number of inter-
polation  schemes  can	be  used,  the	fastest	 uses  the
Discrete Fourier Transform and	the  Convolution  Theorem,
and  can  multiply  two	 integers of length n in O(n logn)
steps.	An iterative process is	then used to  perform  the
division  step,	optimised by careful choice of the modulus
R. This	 technique  seems  particularly	 well  suited  for
implementation on current digital signal processing chips.

The use	 of  addition  chains,	rather	than  conventional
binary	 arithmetic,   provide	 another  alternative  for
hardware implementations. This technique for computing the
multiplications	 in  the  modular exponentiation has effi-
ciencies approaching that of FFT methods, but with a  much
easier	implementation.	 Yacobi	 [Yac91]  describes such a
method.

A further alternative, where special hardware is used,	is
to  have special carry-save multiplication hardware, where
the addition of	carries	 between  digits  in  the  partial
result is delayed until	the end	of the multiplication step
by using two registers for each	number.	 An  extension	of
this technique which incorporates modulo reduction similar
to that	described above, is presented by Brickell  [Bri82]
and  performs  modular	multiplication in time O(n+7) with
O(n) gates.  This is the preferred approach  when  special


			Chapter	3









			    44


hardware  is  to  be designed.	It is possible to multiply
two numbers in O(logn) time, using O(n2) gates.	 Currently
for the	size of	numbers	proposed with RSA, this	appears	to
be unachievable. However, as circuit  densities	 increase,
it will	undoubtably lead to faster implementations.

Modular	exponentiation is  performed  using  a	series	of
modular	multiplications, in the	well known square and mul-
tiply algorithm	(see example below) [Knu81].

    8053 _= ((((((802.80)2)2).80)2)2.80)		  (Eq 3.3)

This appears to	be an essentially sequential process whose
time  efficiency  cannot be generally improved upon beyond
the improvements in the	underlying multiplication stages.

In the specific	case of	 RSA  some  optimizations  can	be
made.	Encryption can be performed using a small exponent
e (possibly fixed),  which  limits  the	 number	 of  steps
needed	significantly  (since if e only	has say	8 signifi-
cant bits, then	at most	8 square and multiply  steps  need
to  be done).  The decryption key however, must	be long	to
ensure security	[Wei90]. However in the	 decryption  stage
the  calculations  can	be  done independently (mod p) and
(mod q),  and  the  results  combined  using  the  Chinese
Remainder  Theorem.  Since  p and q are	each about 1/2 the
size of	R, this	results	in a saving of 1/2 to 3/4  of  the
time,  depending on the	multiplication algorithm used.	In
more detail, the Chinese  Remainder  Theorem  states  that
there  can  only  be one solution to a set of congruences,
given that the modulii are relatively  prime  [Knu81].	In
this specific case, form:

    M  = M (mod	p) = (C	(mod p))d (mod (p-1))	  (Eq 3.4)
     1

    M  = M (mod	q) = (C	(mod q))d (mod (q-1))	  (Eq 3.5)
     2
Then the system	of equations:

    M =	M  (mod	p), M =	M  (mod	q)		  (Eq 3.6)
	 1		 2
will have a single solution (being the required	message	 M
by construction) of the	form:

    M =	[((M  +	q - M )u)(mod q)]p + M		  (Eq 3.7)
	    2	     1		      1,

	    where pu (mod q) _= 1

The  multiplicative  inverse  u	 is  calculated	  at   key


			Chapter	3









			    45


generation time, and is	kept along with	the secret decryp-
tion key.  This	method is described by Quisquater  et  al.
[QuC82].

These various choices (outlined	above),	which can be  made
in  implementing  RSA, and the tradeoff's between them are
summarised in  a  significant  overview	 paper	by  Rivest
[Riv84]. They are:

IIIInnnntttteeeeggggeeeerrrr	MMMMuuuullllttttiiiipppplllliiiiccccaaaattttiiiioooonnnn	of  two	 n-bit	integers  requires
time:

+o     O(n2) on a  sequential  computer	using  a  standard
     algorithm

+o     O(n) on special purpose serial/parallel  multiplica-
     tion hardware, with O(n) gates,

+o     O(log n) on special purpose parallel/parallel multi-
     plication hardware	with O(n2) gates.

MMMMoooodddduuuullllaaaarrrr	MMMMuuuullllttttiiiipppplllliiiiccccaaaattttiiiioooonnnn of  two	n-bit  integers	 modulo	 a
third  n-bit  integer requires the same	order of time, but
with a constant	speedup	factor if special  algorithms  are
used as	described previously.

MMMMoooodddduuuullllaaaarrrr	EEEExxxxppppoooonnnneeeennnnttttiiiiaaaattttiiiioooonnnn requires	O(n)  multiplications.	 A
constant improvement in	time efficiency	may be obtained	by
using either:

+o     a	left-to-right exponentiation algorithm and precom-
     puting powers of M, or alternatively

+o     a	right-to-left exponentiation  algorithm	 and  per-
     forming the two modular multiplications in	parallel.

IIIImmmmpppplllleeeemmmmeeeennnnttttaaaattttiiiioooonnnn	ttttrrrriiiicccckkkkssss	appropriate  to	  performing   RSA
encryption and decryption include:

+o     using a fast clock rate

+o     using a short encryption	exponent  e  (however  the
     decryption	exponent d must	be long)

+o     using  the  Chinese  Remainder  Theorem  to  operate
     modulo p and q separately.







			Chapter	3









			    46


_3.  _R_S_A	_K_e_y _G_e_n_e_r_a_t_i_o_n

The first stage	of the	key  generation	 process  for  RSA
involves  finding  two	large  primes p	and q, to form the
modulus	of the system R=pq.  The choice	of these primes	is
critical  to  the success of RSA as a secure cryptosystem.
Several	proposed attacks on RSA	are based on the possibil-
ity  of	a bad choice in	these primes. The necessary condi-
tions imposed on the primes are	summarised in  a  signifi-
cant  paper  by	 Gordon	[Gor84], which is recommended as a
basis on which the primality selection routines	should	be
based.	 He  designates	 as   _s_t_r_o_n_g _p_r_i_m_e_s  those numbers
which satisfy the following conditions:

+o     p	is a large prime

+o     p	is chosen at random from a random seed

+o     p	has a specified	number of bits

+o     p-1 has a	large prime factor r

+o     p+1 has a	large prime factor s

+o     r-1 has a	large prime factor t

These conditions imply the following:

    p =	2jr + 1					  (Eq 3.8)


    p =	2ks - 1					  (Eq 3.9)


    r =	2Lt + 1					 (Eq 3.10)

for some j, k, L, where	r, s, t	are primes. The	 algorithm
consists  of  finding primes s,	t, and then constructing r
and p from them. The details needed to do this	are  given
in Gordon's paper [Gor84].

One of the crucial steps though, is to	first  identify	 a
prime number.  Much recent work	has been done on primality
testing	 algorithms.  Near  polynomial-time  deterministic
algorithms have	been developed,	as well	as polynomial-time
probabilistic algorithms which trade-off speed against the
probability  of	error).	It thus	appears	at this	time, that
primality testing is significantly easier than	factoriza-
tion of	large integers (and hence that RSA is both reason-
ably secure and	efficient).  A survey and overview of  the
recent	developments  in  primality  testing  is  given	by


			Chapter	3









			    47


Pomerance [Pom81], who outlines	the various algorithms	in
use.  Nearly  all of these are probabilistic, and make use
of strong pseudo-prime tests, which if failed  prove  that
the  integer  is  definitely  composite.  An analysis of a
couple of pseudo-prime tests in	practical use is given	in
Bond  [Bon84].	The original test is derived from Fermat's
Little Theorem,	which states that:  If n  is  prime,  then
for all	a: 0<a<n

		     an-1 = 1 mod n.		 (Eq 3.11)

All prime numbers will satisfy this test.  Some	 composite
numbers,  termed _p_s_e_u_d_o-_p_r_i_m_e_s,	will also satisfy it. How-
ever, if the test is repeated a	large (say 100)	number	of
times,	then  the  chance of a composite being accepted	is
very small. Nonetheless, there are  some  numbers,  called
_s_t_r_o_n_g _p_s_e_u_d_o-_p_r_i_m_e_s, which pass this test for all n. Thus
other tests have been suggested, which reduce further  the
chance	of  such  numbers  being accepted as primes. These
include	the  SSSSoooolllloooovvvvaaaayyyy SSSSttttrrrraaaasssssssseeeennnn TTTTeeeesssstttt:

    Choose a at	random from 1<a<n-1
    Accept n if:

    GCD(a,n) = 1,


			   (_n_-_1_)_
    and	    (a_)	(mod n)	= a  2	 (mod n)
	    (n)


    where   (a_)	(mod n)	is the Jacobi symbol
	    (n)
    Otherwise reject.


and the	RRRRaaaabbbbiiiinnnn TTTTeeeesssstttt:















			Chapter	3









			    48


    Let	n = 2rd	+ 1, where d is	odd.
    Choose a at	random from 1<a<n-1
    Accept n if	either:

    ad = 1 (mod	n)

	   or

    a2jd = -1 (mod n),


	    for	some j:	0_<j<r

    Otherwise reject.


These tests may	be iterated by	repeating  them	 for  dif-
ferent,	randomly chosen	values of a.

The major algorithms for primality testing  are	 described
in several recent papers:

+o     Solovay et al. [SoS77]  present  the  fast  Solovay-
     Strassen  probabilistic algorithm for primality test-
     ing.

+o     Couvreur et al. [CoQ82] survey  all  the	techniques
     known  in	1982, summarizing their	various	advantages
     and disadvantages (a good overview	paper).

+o     Adams et al. [AdS82] present a new  set  of  pseudo-
     prime tests which result in fewer inaccurate results.

+o     Adleman et al. [APR83] present a	very  fast  deter-
     ministic  algorithm  for determining whether a number
     is	prime or not. It uses  a  series  of  pseudo-prime
     tests  to	narrow the range of possible divisors of a
     number, which is then exhaustively	searched to deter-
     mine  whether  there are any factors. It has an upper
     bound on the running time for a number p of:

	    (log p)clogloglog p,   for some constant c

     An	improved version of the	algorithm is presented	by
     Cohen et al. [CoL84], along with results from a prac-
     tical implementation.

Having found the primes	p and q, and obtained R	= pq,  and
selected  an encryption	exponent e (which may well be con-
stant for all users, but otherwise will	 usually  be  some
small	prime,	 see   [QuC82],	  [Wil86],  [KBS86b],  and


			Chapter	3









			    49


[KBS86a]), the final stage of the key  generation  process
to find	a number d such	that

    de _= 1 (mod	U(R)),	    0 _<	d < R.		 (Eq 3.12)

The usual technique suggested for performing this calcula-
tion  is to use	an extended Euclid's algorithm for finding
the GCD(U(R),e), as described in Knuth	[Knu81].  Alterna-
tives  to  this	 include  using	 a  binary algorithm, also
described in Knuth [Knu81], and	extended by Purdy  [Pur83]
who  describes	a  variant using carry-save hardware which
can perform the	GCD calculation	in  time  O(n)	with  O(n)
gates;	or  a  systolic	 algorithm  developed by Brent and
modified by Bojanczyk [BoB86], which  provides	a  similar
level  of  performance.	  Some constructive techniques for
generating strong RSA  primes  are  described  by  Demytko
[Dem89]	and Maurer [Mau90].

_4.  _R_S_A	_I_m_p_l_e_m_e_n_t_a_t_i_o_n _i_n _P_r_a_c_t_i_c_e

The better known RSA implementations (either in	 full,	or
of  modular  exponentiation  implementations), may be con-
sidered	in two groups, software	implementations	on  exist-
ing computers, and specialised hardware	implementations:

_4._1.  _S_o_f_t_w_a_r_e _I_m_p_l_e_m_e_n_t_a_t_i_o_n_s _o_f _R_S_A

A number of software  implementations  of  RSA,	 typically
encrypting at 1-10 bits/second,	have been attempted. These
include:

+o     Schaller et al. [ScA83] describe	an  implementation
     for  a  Z-80  microprocessor of a system where RSA	is
     used to distribute	keys for a private-key	cryptosys-
     tem  (DES),  along	 with  the associated name and key
     servers, and message flow control,	as  an	experiment
     in	 the  use  of  such  a system; Similar schemes are
     described by  Jackson  et	al.  [JMN84]  and  Muller-
     Schloer [Mul83].

+o     Coyne [Coy85] describes a	full RSA system,  used	to
     provide secure electronic mail, which has been imple-
     mented at the Basser Dept.	of Computer Science at the
     University	of Sydney.

+o     Aruliah [Aru85]  presents	 an  ISO  Standard  Pascal
     implementation  which  has	 been  fully  tested  on a
     number of systems,	and which it is	suggested  may	be
     used as a comparison suite	for other implementations.




			Chapter	3









			    50


+o     Burton [Bur84] gives code	in Ratfor which	implements
     a full RSA	system.

+o     Dusse [Dus91] describes an implementation	of RSA and
     other  cryptographic algorithms on	the Motorola 56000
     DSP. The RSA implmentation	is capable  of	encrypting
     at	11 kbits/sec.  a full RSA system.

_4._2.  _H_a_r_d_w_a_r_e _I_m_p_l_e_m_e_n_t_a_t_i_o_n_s _o_f _R_S_A

A number of hardware  implementations  of  RSA	have  been
attempted. These include:

+o     Rivest [Riv80]. This is a	VLSI implementation  using
     a	512 bit	ALU providing modular arithmetic including
     exponentiation, prime number generation, GCD calcula-
     tion,  extraction	of  a  small common divisor if one
     exists, and RSA key generation.  It could achieve	an
     encryption	rate of	1200 bits/second.

+o     Rieden et	al. [RSW82] report on the work done  by	 a
     team  at  Sandia National Labs in the US, designing a
     radiation	hardened  LSI  chip  set,  which  provided
     exponentiation  of	 336-bit messages at a rate of 430
     bits/sec, using two chips.

+o     British Telecom have released  advanced  information
     on	a 256-bit RSA exponentiator chip [BBB86], known	as
     the METEOR	VLSI Public  Key  Device,  which  will	be
     capable of	encrypting at 9600 bits/second.

+o     Serpell et al. [SBC84], describe	a  hybrid  crypto-
     graphic  system  which  uses  RSA	to distribute keys
     which  are	 then  used  in	 a  private-key	  (B-Crypt
     scheme). The RSA calculations are done on the British
     Telecom hardware exponentiation chip.

+o     Orton et al. [ORS87] present some	results	 from  the
     implementation  of	 a  modular  RSA chip which may	be
     stacked to	obtain longer bit-lengths.

+o     Janiak [Jan87] describes a chip set,  based  on  the
     TMS320C10	DSP  processor,	which can exponentiate 640
     bit numbers in 1.7	secs. It is designed to	be used	as
     an	auxiliary processor in PC's and	Workstations.

+o     Hoornaert	 et  al	 [HDV89]  describe  a  chip  being
     developed	by  Cryptech,  capable of encrypting at	17
     kbits/sec.




			Chapter	3









			    51


These and other	hardware RSA implementations are  compared
in a recent survey by Brickell [Bri90].	The fastest imple-
mentation that he notes	is  that  by  Cryptech.	 Chips	by
British	 Telecom, Plessey and Sandia are quoted	to encrypt
at 10 kbits/sec.  Brickell  also  notes	 that  recent  DSP
implementations	have achieved speeds comparable	to this.

_5.  _C_o_n_c_l_u_s_i_o_n

In this	chapter, various alternative  methods  for  imple-
menting	 the  RSA  cryptosystem,  being	 the  most  widely
regarded  public-key  cryptosystem,  have  been	 outlined.
Methods	  surveyed  include  conventional  multi-precision
arithmetic  with  modulo  reduction  performed	either	in
software  on  conventional  machines or	specially designed
long bit-length	hardware; specialised multiplication algo-
rithms	which may be optimised for use on high-speed Digi-
tal Signal Processing (DSP) chips; and the use	of  carry-
save   multiplication  techniques  on  specially  designed
chips.	None of	these methods seem to offer much  hope	of
implementing exponentiation, and hence the RSA scheme suf-
ficiently fast enough to be able to encrypt all	data being
exchanged  on modern high-speed	data links. Hence there	is
a need for good	private-key algorithms for use in a hybrid
scheme.




























			Chapter	3









			    52























































			Chapter	3












			CCCCHHHHAAAAPPPPTTTTEEEERRRR	 4444


		 DDDDeeeessssiiiiggggnnnn	RRRRuuuulllleeeessss ffffoooorrrr tttthhhheeee DDDDEEEESSSS




_1.  _I_n_t_r_o_d_u_c_t_i_o_n

The Data Encryption Standard (DES) [NBS77]  was	 developed
out  of	 the Lucifer cipher.  At the time of its introduc-
tion, there was	a considerable amount of controversy  over
the choice of a	56-bit key [DiH77], [Hel79a].  This was	on
the grounds that such a	key length was small enough to	be
exhaustively  searched	on  machines  which  could be con-
structed in the	foreseeable future.   With  the	 march	of
computer  technology, this risk	appears	to be rising. How-
ever, on all other accounts DES	appears	to be an excellent
cryptosystem.	The DES	has withstood a	concerted analysis
by the open research  community,  since	 its  adoption	in
1977.	The  most successful attack to date, that of Biham
and Shamir [BiS90] still performs worse	than an	exhaustive
key-space search on the	DES with the full 16 rounds.

Given this basically favorably assessment, the DES will	be
closely	 examined  as  a basis for developing design rules
for new	cryptosystems.	This  chapter  will  discuss  some
possible design	criteria which could have been used in the
DES, derived both from those reported in  the  literature,
and  from  some	initial	observations by	the author.  These
show that the DES was very carefully  designed,	 and  that
its  various components	are far	from random.  It will then
illustrate how these criteria  could  be  applied  in  the
design	of  new	Feistel	ciphers	with either 64-bit or 128-
bit keys and data.

_2.  _D_e_s_c_r_i_p_t_i_o_n	_o_f _t_h_e _D_E_S

The basic DES enciphering chain	was shown in Fig 2.7.	In
brief,	the input block	is permuted by an initial permuta-
tion IP, is then subjected to a	complex	key-dependent com-
putation  (Fig	2.8), and is finally permuted by IP-1, the
inverse	of the initial permutation.  On	 deciphering,  the
same process is	used, except that the complex component	is
run backwards, using keys in reverse order, via	the method
shown above.

In more	detail,	the input block	X of 64	bits is	first per-
muted by the initial permutation IP, and then divided into
two halves  L(0)  and  R(0).   The  complex  key-dependent


			    53









			    54


function consists of sixteen rounds in which the left com-
ponent L(i-1) is exclusive-or'd	(XOR'd)	with the output	of
a non-linear function g	whose input is both the	right com-
ponent R(i-1) and part of the  key  K(i)  (Fig	2.9).  The
halves	are  then  interchanged	 to form the input for the
next round  (with  the	exception  of  the  final  round).
Finally	the output is permuted by IP-1 (the inverse of the
input permutation IP) to yield the output ciphertext Y.

_3.  _K_n_o_w_n _D_E_S _D_e_s_i_g_n _C_r_i_t_e_r_i_a

All the	functions used in the DES are specified	in tabular
form.  No  description is provided on why they are chosen.
In fact	it is stated that the design criteria are  classi-
fied.	Nonetheless,   some  of	 the  criteria	have  been
released, and others  may  be  deduced	by  examining  the
tables	as  given.  The	 search	for the	design criteria	is
motivated by two  reasons,  first  to  aid  in	the  cryp-
tanalysis  of  the  DES,  and  second in designing new and
extended Feistel ciphers. Whilst the  primary  concern	in
this thesis is with the	latter purpose,	the results should
also be	of interest to those interested	 in  cryptanalysis
of such	ciphers. The structure of the DES will be examined
in terms of the	various	permutation, substitution and  key
scheduling components, with design rules being devised for
each.

_3._1.  _S-_b_o_x _D_e_s_i_g_n _C_r_i_t_e_r_i_a

The S-boxes in DES are the prime source	of  complexity	in
the  algorithm,	 and are largely responsible for the secu-
rity of	the scheme.  Consequently, considerable	 time  has
been  spent  on	 analysing  them,  and hence more is known
about them than	the P-boxes.  The actual criteria used are
classified secret. It has been stated[1] that  there  were
12  (possibly  13)  criteria used, which resulted in about
1000 suitable S-boxes, of which	the implementors chose	8.
Some of	the criteria used were reported	to an NBS workshop
on cryptography	[BGK77], and are:

+o S1   Each row	function in an S-box is	a  permutation	of
     the integers 0 to 15

+o S2   No S-box	is a linear  or	 affine	 function  of  the
     input.

____________________

   [1]	by  Alan  G.  Konheim  at  a  Seminar  series	on
Cryptography in	Amsterdam, 1986	[Kon86]



			Chapter	4









			    55


+o S3   Changing	1 input	bit to an S-box	results	in  chang-
     ing at least 2 output bits

+o S4   S(x) and	S(x XOR	001100 ) must differ in	at least 2
     bits  (where  S(x)	 is  t2he  output of an S-box given
     input vector x).

The following rules were labelled (see [BGK77])	as result-
ing from design	criteria:

+o S5   S(x) =/ S(x XOR 11ef00 ) for any choice of e or f.
			    2
+o S6   The S-boxes were	chosen to minimise the	difference
     between the number	of 1's and 0's in any S-box output
     when any single input bit is held constant.

These rules were analysed  by  Brickell	 et  al.  [BMP87].
Rule  S1 states, in effect, that each row of each S-box	is
a 1-1 function.	 Rule S2 ensures that the DES algorithm	as
a whole	is not linear or affine. If it were, it	would sub-
stantially reduce the security of the scheme,  and  enable
reasonably   easy   recovery  of  a  key  with	a  set	of
plaintext/ciphertext pairs. The	next two rules S3 and  S4,
seem  to  incorporate the concept of the avalanche effect,
in that	it ensures that	small changes to one or	 two  bits
of  input  result in large changes in the output. Rule S5,
reduces	the probability	that two different inputs would	be
mapped onto the	same output (nb: function g is neither 1-1
nor onto, it must only generate	the same output	 from  the
same  input  and  key);	 and that the image space (ie: the
range of possible values generated by g) is  as	 large	as
possible.   Rules  S1,	S3,  and  S4 seem to imply rule	S6
(which accords with the	original statement that	 it  is	 a
consequence of the design criteria), and is related to the
S-boxes	being permutation functions.

Another	consequence of design criteria was noted by  Meyer
and Matyas in their book [MeM82], namely that:

+o S7   the S-boxes chosen required significantly more log-
     ical minterms to implement	than a random choice would
     require.  A minterm is a logical  AND  (boolean  pro-
     duct) of input bits (and their negations),	which form
     a necessary (but not sufficient) condition	for a par-
     ticular  output bit to be asserted. An output bit may
     have its value completely described by the	logical	OR
     (boolean  sum)  of	 all  its minterms.  The number	of
     minterms in such an expression (after simplification)
     is	 a  measure  of	its complexity.	In the worst case,
     for n input  bits,	 2n  minterms  may  be	needed	to
     describe each output bit.


			Chapter	4









			    56


A random choice	of S-box would lead to a d