thesis.txt

DIAMOND2加密算法的原代码

testing keys at the rate of 10^12 per second for DES with its 
56 bit key, all of the keys can be tested in 7.2 x 10^4 seconds, 
or about 20 hours.  While trying a trillion keys a second is not realistic 
with current general purpose computers, current technology could be 
applied to dedicated, highly parallel encryption/decryption engines 
that could approach that speed - at a cost that would be prohibitive 
for all but large governments at today's prices.

Other than time, the other main measure of complexity of an algorithm 
is the storage capacity required to implement a lookup table attack.  Suppose 
a lookup table were to be constructed that contained the encrypted 
version of just one block of cipher text corresponding to a very common 
block of plain text (such as 16 ASCII spaces) for every key possible.  For 
the MPJ algorithm, this would take 2^128 x 128 = 4.356 x 10^40 
bits.  If this memory were constructed with some kind of device that 
could store one bit per atom of silicon, this would take 4.356 x 10^40 
bits x 28.086 amu/atom x 1.660531 x 10^-24 grams/amu x 10^-6 
metric tons/gram = 2.03 x 10^12 metric tons of silicon.  That 
is about one thousandth of the mass of Deimos, the smaller of Mars' 
two moons.  [CRC]  For DES, the same table would only require about 
215 micrograms of silicon.  Nobody has come up with memory that dense, 
and fundamental physical limits make such a task difficult, indeed.  It 
is not difficult to conceive of some breakthroughs in optical storage 
technology coming close, say using a thousand molecules of something 
per bit. Under those circumstances, DES would be vulnerable to such 
an attack, where MPJ would still be safe.

E.  Computational Efficiency

The MPJ encryption algorithm must be computationally efficient enough 
to be implemented in software on a standard IBM PC or compatible (or 
on an Apple computer of comparable power), and fast enough to handle 
at least 10 megabits per second when implemented in dedicated hardware.  Note 
that this is less restrictive with respect to the hardware for DES, 
which was required to be simple enough to implement on a single chip 
using 1970s technology.

F.  Communication Channel Efficiency

The MPJ encryption algorithm must not significantly increase the size 
of the plain text when encrypting it.  This precludes the use of noise 
addition as a technique to be used.

G.  No Back Doors or Spare Keys

While it may be impossible to guarantee that no ``back doors'' or  ways 
to decipher a message without the key exist, the algorithm should  be 
sufficiently complex combination of simple, well-understood operations  that 
no help is offered to the cryptanalyst from the structure of  the 
algorithm. Spare keys (the situation where more than one unique  key 
will decipher a message) are avoided by making the number of keys  possible 
much less than the number of possible transformations that can be 
done  on a set of blocks.  This is true for MPJ because 2^128 
<< 2^128!.

VII.      MPJ ENCRYPTION ALGORITHM

A.  Description

The MPJ Encryption Algorithm can be looked at from the outside like 
a rather large electronic codebook that operates on 128 bit blocks.  The 
algorithm may be used in several modes.  It can be used directly in 
electronic codebook mode, in block chaining with ciphertext feedback 
mode, in block chaining with plain text feedback mode, and in stream 
cipher generation mode.

Given a 128 bit key, instructions to encrypt or decrypt, and a 128 
bit input block, a unique 128 bit output block comes out. Encryption 
and decryption are inverse operations that can be done in either order.  For 
example, if P is the plain text block, C is the cipher text block, 
EK1 is encryption with key 1, and DK1 is decryption 
with key 1, then C = EK1(P); P = DK1(P).  A different 
cipher text results if the plain text is decrypted first, but DK1(EK1(P)) 
= P = EK1(DK1(P)).  Multiple encryption can be done 
with several keys, as in these examples with three:

C = EK1(EK2(EK3(P))); P = DK1(DK2(DK3(C))) 
or a different method:

C1 = EK1(DK2(EK3(P))); P = DK1(EK2(DK3(C)))

1.  Overall Structure of MPJ

Before encryption or decryption occurs, the substitution boxes are 
filled based on the input key.

To encrypt a 128 bit input block, it is run sequentially through ten 
rounds of substitution.  Each round of substitution operates on the 
16 eight-bit bytes that make up the input block individually.  In 
between each round of substitution is a round of permutation, for 
a total of 9 rounds of permutation.  The permutation operation is 
identical each time.  Each operation (substitution and permutation) 
has an inverse operation.  Decryption is done by running the inverse 
operation of each of the above steps in the opposite order.

After one round of permutation, each bit in the output block depends 
on every bit in the byte that it is in and on eight bits of the key.  After 
a round of permutation and the second round of substitution, each 
bit in the block depends on eight bytes of the input block and on 
eight bytes in the key.  After the third round of substitution, each 
bit in the block is functionally dependent on 15 of the input bytes 
and on 15 bytes of the key.  After the fourth round of substitution, 
each bit in the block is functionally dependent on every bit of the 
input block and on each bit of the key.  After the tenth round of 
substitution the functional dependence on every bit of the key and 
the input block is so complex that it would be infeasable to determine 
the key used, even if the cryptanalyst has known corresponding plain 
and cipher text and knows the algorithm used.  Because the substitution 
boxes are totally nonlinear functions, the problem of finding each 
of the 40,960 internal key bits is a tough one, indeed.  It would 
be easier to find the original key of only 128 bits by brute force 
- something that is difficult, indeed.

2.  Substitution Boxes

The substitution boxes are designed to be big enough to provide a 
large number of possible arrangements, but small enough to still fit 
comfortably within the memory of an MS-DOS computer.  Each substitution 
box is therefore a collection of 16 substitution boxes that operate 
on only 8 bits at a time, with a total of 256 entries.  The substitution 
boxes may be an array or look-up table in a computer, or they may 
be implemented in hardware using RAM.

The substitution boxes are filled during the internal key generation 
process with a permutation of numbers that depends on the main key 
in a different way for each substitution box.

3.  Wire Crossings

The wire crossings serve to extend the functional dependence of the 
output block on the input block across the internal byte boundaries.  This 
is done by making each byte of the output of the permutation to contain 
one bit from each of eight different bytes.  The selection of bits 
was chosen to make a computer implementation fairly efficient.  A 
pure hardware implementation of this operation is, of course, much 
faster, since it involves only the propagation delay of the signal 
from one end of a short wire to the other.  The input block bit positions 
are numbered from left to right (MSB to LSB) as 127 down to 0, then 
the new positions those bits occupy after the wire crossing are (MSB 
to LSB):

55, 46, 37, 28, 19, 10, 1, 120, 111, 102, 93, 84, 75, 66, 57, 48, 
39, 30, 21, 12, 3, 122, 113,  104, 95, 86, 77, 68, 59, 50, 41, 32, 
23, 14, 5, 124, 115, 106, 97,  88, 79, 70, 61, 52, 43, 34, 25, 16, 
7, 126, 117, 108, 99, 90, 81, 72, 63, 54, 45, 36, 27, 18, 9, 0

4.  Key Generation

Internal key generation in the MPJ encryption algorithm consists of 
filling all of the substitution boxes (arrays in software or RAM in 
hardware).  There are 16 substitution boxes used for each of 10 rounds.  Each 
substitution box contains 256 entries of 8 bits each.  Therefore, 
the actual internal keys have a combined length of 16 x 10 x 256 x 
8 = 327,680 bits.  These are obtained by manipulation of the 128 input 
key bits.  Note that trying to attack the MPJ encryption algorithm 
by brute force trial and error using internal keys instead of using 
the 128 input key bits is ridiculous.  The calculations given above 
indicate how difficult even a 128 bit random key is to solve by brute 
force.  The only way that an attack on internal keys is useful is 
if there are parts of the internal keys that can be solved for separately, 
without having to solve for as many as 128 bits at once.

Attacks against the internal key structure are made computationally 
intractable in three ways.  First, the smallest chunk of the internal 
key that could be meaningfully solved for is the contents of one of 
the substitution boxes.  Each of these contain 256 bytes, or 16 times 
the length of the input key. Remember that the addition of each bit 
doubles the complexity of the solution, so this is not attractive 
compared to solving for the input key.  The second impediment to this 
attack is to make the relationship between the contents of the substitution 
boxes and the input key quite nonlinear.  The way this is done is 
by using a combination of rotating bit selection and the use of the 
last substitution box filled to compute the contents of the next one.  The 
third line of defense against the solution of internal keys is the 
use of ten nonlinear rounds of encryption to make any attempt at constructing 
a system of linear equations to solve for the internal key given known 
plain text and corresponding cipher text infeasable.  Note that each 
round of encryption in MPJ causes the whole 128 bit block to be changed, 
where each of the rounds in DES only modifies half of its 64 bit block.  Therefore 
the internal structure of MPJ is very difficult to solve for, with 
each bit of the output having a nonlinear functional dependence on 
every bit of the input and on the contents of 1 + 8 + 15 + (7 x 16) 
= 136 of the substitution boxes, containing a total of 34,816 bits.  If 
the substitution boxes were linear, this solution would be possible, 
but there is no method I know of to solve such a system of nonlinear 
equations, either here or the simpler case of the DES internal structure.

To find the inverse of the substitution box functions, separate inverse 
substitution boxes are formed that place each address of a substitution 
box at the address of the data contained in the substitution box.  For 
example, if the contents of the first substitution box in the first 
round of encryption for the input value of 1 is 219, then the contents 
of the first inverse substitution box in the last round of decryption 
for the input of 219 will be 1.  In equations, SI[i, j, S[i, j, k]] 
= k for all i, j, k, where the first index of the array is the round 
of encryption, numbered from 0 to 9, or the round of decryption, numbered 
from 9 to 0 (defined differently for programming convenience); the 
second index is the position of the 8 bits that the substitution applies 
to in the input block, numbered from 0 to 15, left to right; and the 
third index is the value of the 8 bits input to the block.

The actual algorithm for substitution box filling consists of three 
main parts.  The first one is a nested loop to fill one substitution 
box, permute the key with the same permutation used for the encryption 
operation, then to run each byte of the key through the substitution 
box that was just filled. This is done for each round of encryption, 
from 0 to 9, with each substitution box used in one round of encryption, 
from left to right, done within each of these rounds.  In other words, 
the index of the three dimensional array that selects the position 
of the substitution box within each array varies faster than the index 
that selects the number of the round of encryption that the box uses.

The second algorithm is the one that fills each substitution box based 
on the contents of the input key, as modified by the previous steps.  This 
algorithm uses bit selection and rotation to determine where each 
value of the output of the substitution box goes.  To be an invertable 
function, each of the possible output values from 0 to 255 must appear 
exactly once somewhere within the array with 256 possible slots, numbered 
from 0 to 255.  The first number placed in the array is 255, and there 
are 256 possible places to put it.  The second one is 254, with 255 
places to put it.  This is continued until the last value, 0 is placed 
in the one remaining slot.  For the first half of the values, the 
formula pos = (n * m) div 255 is used to determine which of the unfilled 
slots (counting in index order from 0 to n) is to be used to contain 
n.  The variable pos is the position (counting only unfilled slots), 
* denotes multiplication, and div is the integer division operator 
(remainders are ignored).  The variable m is determined for the first 
value of n (255) by selecting one bit from each byte of the key, starting 
with the least significant bit from the least significant byte of 
the key.  The next bit (place value of 2) is selected from the next 
most significant bit of the key, and so on until m has eight bits.  For 
the next value of n (254), the same thing is done, except that the 
bit selected is one bit position to the left of the one selected last 
time.  The place value of the bit selected is the same in m as it 
is in the byte it came from.  The bit to the left of the MSB in a 
byte is the LSB of the byte to the left of it.  The byte to the left 
of the most significant byte is the least significant byte.  For the 
values of n from 127 to 0, then the same thing is done, except that 
only seven bits are selected for m, and the position is determined 
from pos = (n * m) div 127. For a more concise explanation of this 
process, see the commented pascal procedure makesbox in the program 
in appendix A.

The third algorithm used in internal key generation is the generation 
of inverse substitution boxes.  This is done with a simple nested 
loop that fills the inverse substitution boxes according to the formula 
si[i, j, s[i, j, k]] for i from 0 to 9, j from 0 to 15, and k from 
0 to 255.  The array si is the collection of inverse substitution 
boxes, and the array s is the collection of substitution boxes filled 
by the above two algorithms.  Filling of inverse substitution boxes 
is only needed for decryption mode.

B.  Implementation in Pascal

Pascal source code for a program to implement the MPJ Encryption Algorithm 
is given in Appendix A.

1.  Exceptions from Standard Pascal

This program was written for MS-DOS computers and compiled using Borland 
Turbo Pascal 5.0.  To adapt this program for use on another system, 
note that the following features of Turbo Pascal that do not conform 
to the ANSI/IEEE770X3.97-1983 Standard Pascal were used in this program:

(i)  The assign procedure is used to associate an operating system 
file name