System for enciphering or deciphering data

Abstract

A system for enciphering or deciphering wherein bit patterns in a binary number notation of a plurality of elements, which an irreducible polynomial in the Galois field GF (2.sup.i) has, are stored in registers arranged in a certain correspondence with the bit positions of input data or messages, as random numbers for an encryption key or decryption key. The bit patterns retained in the registers corresponding to the digit of bit "1" in the input data are subjected to a mod 2 addition operation independently for each digit of the random numbers, to thereby obtain encipher or decipher data corresponding to the input data. The elements to be used for the encipher and decipher keys have a specific relationship therebetween in conformity with the periodical characteristic of the elements the irreducible polynomial has.

Claims

I claim:

1. A system for enciphering or deciphering i binary digit data comprising:

first store means for temporarily storing input data to be enciphered or deciphered;

second store means for storing a matrix formed by a plurality of streams of i binary digit random numbers, each stream corresponding to a respective digit of said first store means; and

output means for outputting a signal as encryption or decryption data for said input data, said signal being obtained by performing mod 2 addition of the streams of random numbers, among a plurality of streams stored in said second store means, which correspond to those digits of the input data store in said first store means and having a "1" bit, said addition operation being performed independently for each digit of said random numbers;

wherein said plurality fo streams of random numbers to be stored in said second store means respectively correspond to i element consecutive in power number and selected from the (2.sup.1-1) elements of an i order irreducible primitive polynomial in the Galois field GF(2.sup.i).

2. A system as set forth in claim 1, wherein if in encryption operation the polynomials stored as the random numbers in said second store means correspond to the elements x.sup.E to x.sup.E+i-1 in a power form, then in decryption operation the polynomials stored as the random numbers in said second store means correspond to the elements x.sup.D to x.sup.D+i-1 in a power form, wherein E+D.ident.0 (mod 2.sup.i -1).

3. A system as set forth in claim 1, wherein

said second store means comprises i shift registers, each storing a stream of i digit random numbers;

said first store means comprises an input register for outputting in parallel i digit input data; and

said addition means comprises a plurality of AND circuit means provided for each digit of said input register for performing an AND between a one digit output from said input register and an output from said shift register corresponding to said one digit, and an adder for performing a mod 2 addition operation of the outputs from said plurality of AND circuit means.

Description

BACKGROUND OF THE INVENTION

(1) Field of the Invention

The present invention relates to a system for enciphering or deciphering data, and more particularly to a system for enciphering or deciphering data or messages by multiplying them by pseudorandom numbers.

(2) Description of the Prior Art

Recently, in an on-line system such as a bank system, protection of transmission data through encryption has strongly been requested in order to prevent illegal access to the transmission data and its abuse through cryptoanalysis. Not only the protection for transmission data through encryption, but also the protection for file data within a computer system has also been requested heretofore.

Of conventional data encryption systems, there are known systems in which pseudorandom numbers are added to data, as proposed for example in U.S. Pat. Nos. 3,535,642, 3,681,708, 3,691,472, 3,816,764, 3,838,259, 3,911,216. In these known systems, basically the bit patterns of transmission data and pseudorandom numbers are added together at each of the corresponding bits of the respective data and the resultant bit pattern is transmitted as a cipher message. With such system, if there is only one terminal for destination of a message, i.e., in case of an end-to-end type communication network, both sending and receiving terminals may suffice only if they have a single common stream of pseudorandom numbers as a cipher key for enciphering and deciphering. However, if the number of terminals in a communication network increases, then it is necessary to use a plurality of particular cipher keys for respective pairs of sending and receiving terminals. This results in a large number of cipher keys which must be prepared for the whole communication system.

The number of types of cipher keys may be reduced by allocating a particular cipher key for each communication channel. For instance, as shown in FIG. 1, in a system where terminals A, B, C, D and E are connected to each other via nodes P.sub.1, P.sub.2 and P.sub.3, the number of cipher keys necessary for each terminal becomes minimum on condition that different streams of pseudorandom numbers C.sub.1 to C.sub.7 are prepared for respective communication channels and enciphering and deciphering are performed by using as a cipher key C.sub.1 for the channel from A to P.sub.1, C.sub.2 for the channel from P.sub.1 to P.sub.2, C.sub.3 for the channel from P.sub.2 to P.sub.3 and C.sub.4 for the channel from P.sub.3 to B. However, if the above-noted encryption using an independent cipher key for each communication channel is employed for an encryption system where a transmission message and a stream of pseudorandom numbers are added together (EXCLUSIVE 0R operation), there arises a possibility of a cryptoanalysis of the message by performing an AND operation, relative to the same plain text, of the cipher texts obtained from a plurality of communication channels. Thus, data protection is not sufficient.

Among other encryption systems, also known is an American encryption standard system by the Department of Commerce of U.S. Government. This system however requires complicated circuits in order to perform iterative operations of combinations of substitution and transposition processings for the input data.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide a system which has little risk of cipher data being illegally cryptoanalized and is capable of enciphering or deciphering the data with a simple circuit arrangement.

It is another object of the present invention to provide an enciphering or deciphering system having an extremely high degree of freedom in selection and alteration of cipher keys.

It is a further object of the present invention to provide a system capable of enciphering and deciphering data by using the same circuit construction and changing only the cipher keys.

It is a still further object of the present invention to provide an enciphering system capable of transposition of the bit positions of a cipher text by using a selected set of cipher keys.

In order to achieve the above objects, the system for enciphering or deciphering i binary digit data according to the present invention comprises:

first store means for temporarily storing input data to be enciphered or deciphered;

second store means for storing a plurality of streams of i binary digit random numbers, each stream corresponding to each digit of said first store means; and

output means for outputting a signal as encryption or decryption data for said input data, said signal being obtained by performing mod 2 addition of the streams of random numbers, among a plurality of streams stored in said second store means, which correspond to those digits of the input data stored in said first store means and having "1" bit, said addition being performed independently for each digit of said random numbers.

A consecutive set of elements is used as said plurality of streams of random numbers, the set of elements being selected from the finite number of elements of an irreducible polynomial f(x) in the Galois field (2.sup.i). These elements can be expressed in a binary bit pattern when they are expressed in a polynomial form and the degree of x terms is made to correspond to the binary number digit. The enciphering system of the invention utilizes the characteristic of an irreducible polynomial and generates encryption data by performing a partial product operation between the inputted data and random number patterns. Also in deciphering, the original data is reproduced from a partial product operation between the inputted cipher data and random number patterns.

These and other objects, features, and uses will become more apparent as the description proceeds, when considered with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram showing a data communication network for enciphering and deciphering data;

FIG. 2 is a block diagram showing a schematic construction of a node in a data communication network;

FIG. 3 is a table for explaining the principle of enciphering a message according to the present 0180 invention;

FIG. 4 is a table for explaining the principle of deciphering a cipher text according to the present invention;

FIG. 5 is a circuit diagram showing one example of enciphering and deciphering circuits according to the present invention;

FIG. 6 is a flow chart illustrating a sequence for generating random numbers to be used as an encryption key; and

FIG. 7 is a flow chart illustrating a sequence for generating random numbers to be used in a decryption key.

DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 2 is a block diagram schematically showing the construction of the node P.sub.1 in the communication network of FIG. 1. The node P.sub.1 is provided with a data processor 30 for operation of a data exchange, modems 20, 20' and 20" between data communication channels C.sub.1, C.sub.2 and C.sub.5, encipher circuits 10A, 10A' and 10A" and decipher circuits 10B, 10B' and 10B". A cipher text from the data communication channel C.sub.1 received at the modem 20 is deciphered into a plain text at the decipher circuit 10B, and inputted to the processor 30 via a signal bus 31. Alternatively, a message to be transmitted on the communication channel C.sub.1 is transferred via the signal bus 31 to the encipher circuit 10A where it is enciphered into a cipher text and thereafter transmitted via the modem 20. A stream of random numbers used as a cipher key for enciphering and deciphering is supplied via a signal line 32 from the processor 30 to the circuits 10A and 10B. Reference numeral 33 denotes a control signal line for data transmission. The encipher circuits 10A' and 10A" and decipher circuits 10B' and 10B" between the data communication channels C.sub.2 and C.sub.5 and the processor 30, are constructed similarly to the circuits 10A and 10B.

According to the present invention, in the encipher circuits 10A, 10A' and 10A" and decipher circuits 10B, 10B' and 10B", a cipher key is used which is expressed as will be described later in a polynomial form of a set of elements selected from a plurality of elements obtained in association with an irreducible polynomial in the Galois field GF(2.sup.i).

An irreducible polynomial in the Galois field GF(2.sup.i) is generally expressed in the form of:

F.sub.i (x)=a.sub.i .multidot.x.sup.i +a.sub.i=1 .multidot.x.sup.i-1 +. . . +a.sub.1 .multidot.x.sup.1 +a.sub.0 (1)

Any desired element x.sup.n can be identified by performing a mod f.sub.i (x) operation, i.e., by obtaining a remainder through division of X.sup.n by f.sub.i (x), and expressed by a sum of x.sup.i-1 to x.sup.0 as in the following equation where b.sub.i-1, . . . , b.sub.0 are constants of "1" or "0".

X.sup.n .ident.b.sub.i-1 .multidot.x.sup.i-1 +b.sub.i-1 .multidot.x.sup.i-2 +. . . +b.sub.1 .multidot.x+b.sub.0 (mod f.sub.i (x)) (2)

Here, as an example of an irreducible polynomial in the Galois field GF(2.sup.6), the following equation is used.

f(x)=x.sup.6 +x+1 (3)

The above polynomial is an irreducible primitive polynomial having i=6 as the maximum degree of x. As shown in Table 1, all of the elements X.sup.n expressed in a power form can be expressed as a polynomial f.sub.i (x) formed of a sum of 1, x, x.sup.2, x.sup.3, x.sup.4 and x.sup.5. The number g of elements is (2.sup.i -1) since the element of the order 63 equals the value of X.sup.0.

The equation 3 can be expressed as a binary number of "1000011" by making the term of 6 order x correspond to the uppermost bit and the term of 0 order x to the lowermost bit. Simiarily, each element of Table 1 can be expressed in a 6 digit binary number.

                                      TABLE 1
    __________________________________________________________________________
    f.sub.(x) = x.sup.6 + x + 1
    X.sup.n
       X.sup.n = F (mod f.sub.(x))
                      X.sup.n
                         X.sup.n = F (mod f.sub.(x))
    __________________________________________________________________________
    X.sup.0
       1              X.sup.32
                         x.sup.3 + 1
    X.sup.1
       x              X.sup.33
                         x.sup.4 + x
    X.sup.2
       x.sup.2        X.sup.34
                         x.sup.5 + x.sup.2
    X.sup.3
       x.sup.3        X.sup.35
                         x.sup.3 + x + 1
    X.sup.4
       x.sup.4        X.sup.36
                         x.sup.4 + x.sup.2 + x
    X.sup.5
       x.sup.5        X.sup.37
                         x.sup.5 + x.sup.3 + x.sup.2
    X.sup.6
       x + 1          X.sup.38
                         x.sup.4 + x.sup.3 + x + 1
    X.sup.7
       x.sup.2 + x    X.sup.39
                         x.sup.5 + x.sup.4 + x.sup.2 + x
    X.sup. 8
       x.sup.3 + x.sup.2
                      X.sup.40
                         x.sup.5 + x.sup.3 + x.sup.2 + x + 1
    X.sup.9
       x.sup.4 + x.sup.3
                      X.sup.41
                         x.sup.4 + x.sup.3 + x.sup.2 + x + 1
    X.sup.10
       x.sup.5 + x.sup.4
                      X.sup.42
                         x.sup.5 + x.sup.4 + x.sup.3 + x
    X.sup.11
       x.sup.5 + x + 1
                      X.sup.43
                         x.sup.5 + x.sup.4 + x.sup.2 + x + 1
    X.sup.12
       x.sup.2 + 1    X.sup.44
                         x.sup.5 + x.sup.3 + x.sup.2 + 1
    X.sup.13
       x.sup.3 + x    X.sup.45
                         x.sup.4 + x.sup.3 + 1
    X.sup.14
       x.sup.4 + x.sup.2
                      X.sup.46
                         x.sup.5 + x.sup.4 + x
    X.sup.15
       x.sup.5 +  x.sup.3
                      X.sup.47
                         x.sup.5 + x.sup.2 + x + 1
    X.sup.16
       x.sup.4 + x + 1
                      X.sup.48
                         x.sup.3 + x.sup.2 + 1
    X.sup.17
       x.sup.5 + x.sup.2 + x
                      X.sup.49
                         x.sup.4 + x.sup.3 + x
    X.sup.18
       x.sup.3 + x.sup.2 + x + 1
                      X.sup.50
                         x.sup.5 + x.sup.4 + x.sup.2
    X.sup.19
       x.sup.4 + x.sup.3 + x.sup.2 + x
                      X.sup.51
                         x.sup.5 + x.sup.3 + x + 1
    X.sup.20
       x.sup.5 + x.sup.4 + x.sup.3 + x.sup.2
                      X.sup.52
                         x.sup.4 + x.sup.2 + 1
    X.sup.21
       x.sup.5 + x.sup.4 + x.sup.3 + x + 1
                      X.sup.53
                         x.sup.5 + x.sup.3  + x
    X.sup.22
       x.sup.5 + x.sup.4 + x.sup.2 + 1
                      X.sup.54
                         x.sup.4 + x.sup.2 + x + 1
    X.sup.23
       x.sup.5 + x.sup.3 + 1
                      X.sup.55
                         x.sup.5 + x.sup.3 + x.sup.2 + x
    X.sup.24
       x.sup.4 + 1    X.sup.56
                         x.sup.4 + x.sup.3 + x.sup.2 + x + 1
                                        D
    X.sup.25
       x.sup.5 + x    X.sup.57
                         x.sup.5 + x.sup.4 + x.sup.3 + x.sup.2 + x
    X.sup.26
       x.sup.2 + x + 1
                      X.sup.58
                         x.sup.5 + x.sup.4 + x.sup.3 + x.sup.2 + x + 1
    X.sup.27
       x.sup.3 + x.sup.2 + x
                      X.sup.59
                         x.sup.5 + x.sup.4 + x.sup.3 +  x.sup.2 + 1
    X.sup.28
       x.sup.4 + x.sup.3 + x.sup.2
                      X.sup.60
                         x.sup.5 + x.sup.4 + x.sup.3 + 1
    X.sup.29
       x.sup.5 + x.sup.4 + x.sup.3
                      X.sup.61
                         x.sup.5 + x.sup.4 + 1
    X.sup.30
       x.sup.5 + x.sup.4 + x + 1
                      X.sup.62
                         x.sup.5 + 1
    X.sup.31
       x.sup.5 + x.sup.2 + 1
                      X.sup.63
                         1
    __________________________________________________________________________

                  TABLE 2
    ______________________________________
    f = x.sup.5 + x.sup.2 + 1
    X.sup.n
         X.sup.n = F (mod f)
                         X.sup.n
                                X.sup.n = F (mod F)
    ______________________________________
    X.sup.0
         1               X.sup.16
                                x.sup.4 + x.sup.3 + x + 1
    X.sup.1
         x               X.sup.17
                                x.sup.4 + x + 1
    X.sup.2
         x.sup.2         X.sup.18
                                x + 1
    X.sup.3
         x.sup.3         X.sup.19
                                x.sup.2 + x
    X.sup.4
         x.sup.4         X.sup.20
                                x.sup.3 + x.sup.2
    X.sup.5
         x.sup.2 + 1     X.sup.21
                                x.sup.4 + x.sup.3
                                             D
    X.sup.6
         x.sup.3 + x     X.sup.22
                                x.sup.4 + x.sup.2 + 1
    X.sup.7
         x.sup.4 + x.sup.2
                         X.sup.23
                                x.sup.3 + x.sup.2 + x + 1
    X.sup.8
         x.sup.3 +  x.sup.2 + 1
                         X.sup.24
                                x.sup.4 + x.sup.3 + x.sup.2 + x
    X.sup.9
         x.sup.4 + x.sup.3 + x
                         X.sup.25
                                x.sup.4 + x.sup.3 + 1
    X.sup.10
         x.sup.4 + 1     X.sup.26
                                x.sup.4 + x.sup.2 + x + 1
    X.sup.11
         x.sup.2 + x + 1 X.sup.27
                                x.sup.3 + x + 1
    X.sup.12
         x.sup.3 + x.sup.2 + x
                         X.sup.28
                                x.sup.4 + x.sup.2 + x
    X.sup.13
         x.sup.4 + x.sup.3 + x.sup.2
                         X.sup.29
                                x.sup.3 + 1
    X.sup.14
         x.sup.4 + x.sup.3 + x.sup.2 + 1
                         X.sup.30
                                x.sup.4 + x
    X.sup.15
         x.sup.4 + x.sup.3 + x.sup.2 + x + 1
                         X.sup.31
                                1
    ______________________________________

• Inventors
  Shiraishi, Takayoshi;
• Assignee
  Hitachi, Ltd. (Tokyo, JP)
• Published
  Jan-10-1989
• Current US Classes:
  380/28
  380/30
  380/44
  380/46
• Application #
  796753
• International Classes
  H04K 001/00; H04K 009/00
• Field of Search
  178/22.10 178/22.19 178/22.15 178/22.14 380/28 380/30 380/44 380/46 380/50
• Examiner
  Cangialosi; Salvatore
• Agent
  Antonelli, Terry & Wands
• US Patent References:
  4165444
  4520232