thesis.txt

DIAMOND加密算法的原代码

now with a multiprocessor technique developed by Arjen K. Lenstra 
of the University of Chicago and Mark Manasse of Digital Equipment 
Corporation [COS].

The key generation for RSA is a bit nasty, but is reasonable using 
Rabin's test for primality:  Let n = 2^rd+1, where d is odd. 
Choose a at random from 1 < a < n - 1.  Accept n as prime if either 
a^d = 1 mod n or a^2jd = -1 mod n for some j such that 
0 <= j < r, otherwise reject it.

RSA is excellent for public key and authentication use, but it does 
have certain disadvantages for general encryption use.  The processing 
time required for key generation and for the encryption/decryption 
process makes it a poor choice for use with high data rates, although 
there are some reasonably efficient ways to do the exponentiation 
[CHI].  The complexity of the algorithm makes it more difficult to 
implement than many others [VAN].  The worst problem, though is the 
way that the complexity of solving the algorithm could be reduced 
by several orders of magnitude by mathematical research.  For example, 
J. Sattler and C. P. Schnorr recently published some algorithms that 
would appear to reduce the complexity of solving an RSA key by a factor 
of about 10^4 [SAT].  Granted that we are talking about taking 
9 x 10^8 years instead of 1.5 x 10^13 years, but it is 
the potential for other discoveries that may drastically reduce this 
time even further that is the real threat.

D.  Knapsack

A knapsack or trapdoor algorithm is one that is relatively easy to 
perform, but which is very difficult to invert.  The RSA algorithm 
is one such algorithm.  Another one, proposed by Ralph C. Merkle, 
uses the following vector operation:  given an integer s and an integer 
vector a = a1, a2, ..., an find a vector k 
= x1, x2, ..., xn where xi is in {0,1} 
such that s = x * a. (* denotes dot product.)  [MER]  This 
algorithm is referred to in another paper as having been broken [VAN].  Another 
algorithm using matrix operations is suggested by H. Retkin [RET].  This 
algorithm may be good, but it is not obvious to me that no one will 
come up with a good solution to breaking it, too.  Therefore, I prefer 
to use encryption algorithms that have simple brute force solutions 
that are well understood, but just take too long to perform to be 
of concern.

E.  Rotor Machines

Rotor machines were once the state of the art in cryptography.  They 
are a way to form a polyalphabetic solution automatically.  An excellent 
history of these machines is contained in [KAH], [DEA], and [KOZ].  Although 
they are obsolete now due to the superiority of many computer algorithms, 
they played a major role in the history of cryptography.

There were many different variations on the rotor machine, but the 
main principle of each of them was that the input, which is normally 
a indicated by one of 27 (or whatever the alphabet size in use is) 
wires is connected to a voltage level by a keyboard.  This wire is 
then connected via rotary contacts to a rotor that physically permutes 
the position of the wire.  This causes a simple substitution for each 
character, or a poly alphabetic substitution. The output is taken 
from rotary contacts on the other side of the rotor. Several of these 
rotors are placed in series.  After each character is encrypted, one 
or more of the rotors is moved to a new position by a ratchet mechanism.  The 
net effect is a different simple substitution for each letter in the 
message.  Common additions to this scheme are a plugboard style permutation 
performed before or after the rotors and the addition of a reflecting 
rotor to run the signal back through the rotors in the opposite direction, 
using each rotor twice.

The key used is a combination of several things:  (1) the permutation 
performed by each rotor (changed by rewiring it), (2) the order in 
which the rotors were assembled, (3) the starting position of the 
rotors, (4) the plugboard connections, (4) the number of rotors used, 
and (5) the ratchet arrangement.  Taken all together, these form a 
large key space.  If the entire key space is varied simultaneously 
and for every message, then this polyalphabetic substitution is very 
secure.  Due to the construction of these machines, some of the variables 
were not as easy to change as others. Therefore in practical use, 
the variables were not changed all at once.  For example, the number 
of rotors and the ratchet arrangement would probably be fixed for 
the life of the machine.  Therefore, if this portion of the key is 
solved for once, that is enough until a new kind of machine replaces 
it, perhaps years later.  The rotor wiring is tedious to change, and 
therefore unlikely to be changed very often.  The order of the rotors 
might be changed periodically, but during heavy use, the only thing 
that was changed for each message is usually the starting position 
of the rotors.

Using an alphabet size of 26 and five rotors, varying only the starting 
position of the rotors provides a key space of less than 12 million, 
which is within the range of possibility of solution by mechanical 
computer, and a quick task for one of today's PCs.  With many messages 
encrypted with the same rotors, the rotor wiring can be solved by 
frequency analysis ``in depth.''  In other words, the permutation 
applied to the first letter of each message can be solved by determining 
the frequency of occurrence of each code letter and comparing that 
with the language of the source language.  This can be done for each 
position in the message.  From these substitutions, the rotor wiring 
and plugboard connections may be reduced.  This is a more lengthy 
process than solving for the rotor starting position, but once done 
the solution is likely to be good for a while.  Using this kind of 
approach, isolating the parts of the key, the Allies read many German 
and Japanese messages during World War II.

Rotor machines can be simulated in a computer program with more flexibility 
than in mechanical hardware, with many improvements.  There are, however, 
better methods to use in computer algorithms that were not easy to 
use in mechanical devices.  Therefore, rotor machines are interesting 
to study for historical value, but they are obsolete at a time when 
computers are becoming almost as common as televisions.

F.  Codes

Codes, as opposed to ciphers, operate on linguistic units like words, 
phrases, and sentences, rather than directly on the units of the alphabet.  Codes 
have the advantage that they generally compress the message.  For 
example, the codeword ``APPLE'' might mean ``The supplies will be 
shipped on Monday via private courier'' and ``GRAPE'' might mean ``The 
bid is too high.  Reduce it by 10%.''  If there are only a few different 
messages that might be encoded, a substantial savings in space can 
be realized.

Codes are useful for compression of information, even when no encryption 
is intended.  For example, the Uniform Commercial Code, used for telegraphy 
saves on tolls, even though it is published and gives no real security.  Another 
example is the use of Q signals on amateur radio, where encryption 
is illegal but brevity is important, especially when using a slower 
mode of communication like Morse Code.  There QST means ``The following 
is a message of interest to all Amateurs'' and QSL means ``My location 
is _____.''

When used to hide the meaning of the message, the code must be changed 
often. This is much more difficult to do than to change the key to 
an encryption algorithm.  Therefore, this technique has limited value 
except for some diplomatic and military codes.  For commercial applications 
where brevity and security are both required, it is easier to first 
encode the plain text with a fixed code to reduce its size, then to 
encrypt the encoded text with an encryption algorithm whose key can 
be easily changed.  This technique is more secure than the use of 
the encryption algorithm alone, even if the code used is widely known.  See 
chapter VIII for more on the effects of data compression when used 
with encryption.

G.  Galois Field and Hill Cryptosystems

A Galois Field cryptosystem is one in which the letters of the encryption 
alphabet are assigned arbitrarily to the integers from 0 to p^n, 
where p is prime and n is an integer.  These integers are then operated 
on in blocks of m letters by matrix multiplication with a matrix that 
represents monic irreducible polynomials of order m - 1.  All operations 
are done modulo p^n.  To decrypt the data, the ciphertext is 
multiplied in the same manner by the inverse of the encryption matrix 
(obtained using the same modulo arithmetic).  The resulting numbers 
are then substituted back for the letters they represent.

The Hill cryptosystem is similar, except that n is fixed at one, and 
that p need not be absolutely prime as long as several integers less 
than p are relatively prime to it.  For more details on how these 
cryptosystems work, see the articles by Hill, Cooper, and Patti [HIL] 
[HLL] [COO] [PAT].

Both of these systems are based on linear algebra over a limited field 
of integers.  Therefore, they are subject to solution of the key in 
use by linear algebra if enough cipher text and corresponding plain 
text is available.  If the permutation of the encryption alphabet 
in use is known, then the amount of corresponding plain and cipher 
text needed for a solution is merely the key length.  If the permutation 
of the encryption alphabet in use is not known then there must be 
a sufficient quantity to also perform statistical analysis attacks 
on the alphabet in use.  Therefore, I do not recommend the use of 
these systems for serious encryption because of these vulnerabilities.  Not 
only are they less secure than their key length (the combined length 
of the coefficients of their matrices) would indicate, they are computationally 
less efficient than DES and MPJ.  Key generation for these systems 
becomes increasingly complex as the size of the key grows, too, because 
the probability of coming up with a valid set of monic irreducible 
polynomials that form an invertible matrix decreases rapidly with 
matrix size.

These cryptosystems, do, however, provide interesting mathematical 
illustrations on what can be done with Galois Fields.  They also provide 
adequate security for cases where the information being secured is 
not of great commercial value, and is therefore unlikely to be cryptanalyzed.

H.  DES

The National Bureau of Standards (now known as NITS) Data Encryption 
Standard (DES) was published in the Federal Information Processing 
Standards Publication Number 46, dated January 15, 1977 (FIPS PUB 
46) [DES].  For details, please refer to that publication.  A summary 
of the algorithm follows.

Encryption consists of an initial permutation, sixteen rounds of encryption, 
then an inverse of the initial permutation.  Each of the sixteen rounds 
of encryption consist of taking the right half of the input block 
(32 of the 64 bits) and running it through a nonlinear function of 
the 32 bits and an internal key, then adding this result to the left 
half of the input modulo two.  This 32 bit answer becomes the next 
round's right half block.  The next round's left half becomes the 
right half block without modification.  The nonlinear function used 
consists of a bit selection E that selects 48 bits from the input 
of 32 (several of the bits are repeated).  These 48 bits are added 
modulo 2 to the round key of 48 bits.  The result of that operation 
are then fed six bits each into eight substitution boxes.  Each of 
the eight substitution boxes are different, but the same set of eight 
boxes are used for each round.  Each substitution box gives an output 
of 4 bits.  The output of these boxes are fed into a permutation P 
that rearranges the output in a fixed manner.

The sixteen internal keys are generated from the 56 bit input key 
by feeding the input key into a fixed permutation that rearranges 
the order of the key bits.  The key is then split into left and right 
halves called C and D.  Each half is shifted left one or two times 
(according to a fixed table) before generating each internal key.  Each 
of the sixteen internal keys is generated by taking the two halves 
of the key as shifted and permuting them in a fixed manner.

The key and the resulting internal keys are the only things that vary 
in this algorithm.  The initial and final permutations and the contents 
of each of the substitution boxes are constant.  The two permutations 
used in generating the internal keys are constant.  The bit selection 
and permutation used within the nonlinear function are constant.

The strengths of the DES is that its cryptographic strength depends 
only on the key, that the algorithm is easy to implement in a single 
IC, that it has been well tested an no one has publicly announced 
a solution, that hardware and software that uses it is readily available, 
and that the algorithm places very few restrictions on key generation 
so that random numbers may be generated by the users for use as keys.

The weaknesses of the DES are that the key is too short for security 
in the face of anticipated increases of computing power, that it is 
old enough that it is likely that someone has broken it (found a short-cut 
solution), that hardware implementations of the DES are too slow for 
some applications, and that it limits itself to be simpler than is 
really necessary with current technology.

VI.  DESIGN CONSIDERATIONS FOR MPJ

The following paragraphs describe the design considerations that I 
used in creating the MPJ Encryption Algorithm, and the reasons for 
each.

A.  Strength Based on Key

The strength of the system must rely on the security of the key only.  It 
cannot depend on the algorithm being kept secret, because the algorithm 
will be published.  Even if the algorithm were not published, it would 
probably be reverse engineered from software implementations of the 
algorithm.  The algorithm must be constructed in such a way that there 
is no computationally feasible way to derive the key from samples 
of corresponding plain text and cipher text.

B.  Usability of Random Keys

The key selection should be as easy as the random selection of a number 
in a given range.  Selecting a very secure key should be no more difficult 
than flipping a coin once for each bit of the key, or generating keys 
using a pseudorandom sequence combined with random events such as 
timing of keystrokes on a computer.  A one bit change in the key should 
provide a drastically different transformation, so that a potential 
cryptanalyst has no idea when a key that he guesses might be ``close'' 
to the right one. 

C.  Key Length & Block Size