United States Patent: 3657476

[US Patent & Trademark Office, Patent Full Text and Image Database]

( 687 of 687 )

United States Patent	3,657,476
Aiken	April 18, 1972

CRYPTOGRAPHY

Abstract

The cryptographic system to be described is based on a unique number theoretical approach to the generation of pseudo-random digits derived from the N = (m-1)m.sup.n.sup.-1 Distinct powers of r modulo M where M = m.sup.n, m is a prime, and r is a properly chosen primitive root of m. The digits of the powers of r are transformed into Boolean vectors, and these in turn are used as arguments of a Boolean function employed to generate pseudo-random digits. Subsequently, the pseudo-random digits are combined with digits representing the data to be encoded in a manner facilitating the decoding. Security is provided by the very great periodicy that the invention provides. Known electrical components are arranged in a manner to provide solid state circuitry for the implementation of the cryptographic method.

Inventors:	Aiken; Howard H. (Fort Lauderdale, FL)
Appl. No.:	05/005,307
Filed:	January 23, 1970

Current U.S. Class: 380/28 ; 331/78; 380/44; 705/55; 713/190

Current International Class: H04L 9/18 (20060101); H04L 9/22 (20060101); H04l 009/04 ()

Field of Search: 178/22

Other References

Savage, Some Simple Self-Synchronizing Digital Data Scramblers, Bell Sys. Tech. J., February, 1967, pp. 449-487..

Primary Examiner: Bennett, Jr.; Rodney D.
Assistant Examiner: Kaufman; Daniel C.

Claims

What is claimed is:

1. A cryptographic method of the type using pseudo-random digits to encode and decode data, comprising:

a. means for generating a sequence of powers .vertline.r.sup.p .vertline..sub.M where M = m.sup.n, m is a prime and r is a primitive root of m, so chosen that the number of distinct powers is N = (m-1)m.sup.(n.sup.-1),

b. transforming the digits of the powers .vertline.r.sup.p .vertline..sub.M obtained in step (a) into Boolean vectors,

c. entering the Boolean vectors as arguments of Boolean functions to generate pseudo-random digits of radix-r.

2. A method as in claim 1 wherein r = 2 and the Boolean vectors are partitioned into two subsets each having 2.sup.n.sup.-1 vectors and each having an equal number of vector occurrences en toto as the powers .vertline.r.sup.p .vertline..sub.M are generated in the interval 0 .ltoreq. p < N thus providing binary pseudo-random digits having substantially an equal number of 0's and 1's.

3. A method as in claim 2 wherein the Boolean vectors are partitioned in accordance with the following,

so that the Boolean function defining the pseudo-random digits may be implemented by a mod-2 adder.

4. A method as in claim 1 wherein r=3, m=7.

5. A cryptographic method using pseudo-random digits derived from N=(m-1)m.sup.n.sup.-1 distinct powers of .vertline.r.sup.p .vertline..sub.M where M=m.sup.n, m is a prime, and r is a primitive root of m, the pseudo-random digits being obtained by

a. generating the powers of r modulo M by the recurrence relationship .vertline.r.sup.p.sup.+1 .vertline.M = .vertline.r .sup.. r.sup.p .vertline..sub.M ,

b. transforming the digits of .vertline.r.sup.p .vertline..sub.M into Boolean vectors by means of the transformation T( d) = .delta..sub.0, 67.sub.1, . . . .delta..sub.m.sub.-1 where the .delta.'s are all 0's or 1's so that 2.sup.m such transformations exist,

c. entering the Boolean vectors into Boolean functions to generate pseudo-random digits of radix-r.

6. A cryptographic method as in claim 5 wherein r= 2, for the generation of radix-2 pseudo-random digits.

7. A cryptographic method as in claim 5 where r= 3 and m=7 for the generation of radix-3 pseudo-random digits.

8. A cryptographic method as defined in claim 5 further comprising additional encrypting means to modify the order of the pseudo-random digits.

9. A cryptographic system including a method of generating pseudo-random digits of extremely great periodicy comprising;

a. generating the powers of .vertline.r.sup.p .vertline..sub.M where M=m.sup.n, m= prime number, r= primitive root of m, and r is chosen such that the number of distinct powers of r modulo M is N = (m-1) m.sup.(n.sup.-1)

b. applying the transformation T(dpq) to the digits of .vertline.r.sup.p .vertline..sub.M to form Boolean vectors having all digits 0 and 1,

c. using the results of (b) as arguments of a Boolean function f(p) to produce pseudo-random binary digits.

10. Apparatus for generating pseudo-random digits used in a cryptographic system, the apparatus comprising a serial delay line with means for entering a cryptographic key number .vertline.r.sup.p 0.vertline..sub.M where m is a prime, and r is a primitive root of m so chosen that the number of distinct powers of r modulo-M is N = (m-1) m.sup.n.sup.-1, a multiply by r means in a recirculation circuit of the delay line to produce the powers .vertline.r.sup.p .vertline..sub.M successively beginning with .vertline.r.sup.p 0.vertline..sub.M the key, means for transforming the output of the delay line into Boolean vectors, means for entering the Boolean vectors as arguments of Boolean functions to generate pseudo-random digits, and means for combining the pseudo-random digits with a message for encrypting or decrypting the same.

11. Apparatus as in claim 10 further comprising additional encrypting means in combination to modify the order of pseudo-random digits.

12. Apparatus as in claim 11 wherein the additional encrypting means includes trigger pairs controlled by puller functions, interruption means, and delay line.

13. Apparatus as in claim 12 wherein the two states of the trigger pairs are used to complement or not complement the digits of f(p) according to trigger state; delete or not delete the digits of f(p) according to the trigger state; open or close the gates at the input and output of a delay line so that blocks of digits can be deleted from or inserted into the digit stream according to the trigger state.

14. A cryptographic apparatus comprising; a serial delay line, means for manually entering a crytographic key in the serial delay line representing .vertline.r.sup.p 0.vertline..sub.M where M=m.sup.n, m = 5 r = 2, a multiply by 2 circuit connected to the output of the delay line, and having one output connected to the input of the delay line, an output of the multiply by 2 circuit to provide carry digits, a mode 2 adder connected to the times 2 circuit to receive the carry digits and produce binary pseudo-random digits f(p), the output of the mod 2 adder connected to another mod 2 adder for combining with a clear or encrypted message to provide an encrypted or clear message respectively.

15. A cryptographic method for encrypting the letters of the alphabet comprising; regarding the alphabet letters as integers of a radix 27 number system represented by three ternary digits, and operating upon the ternary digits in accordance with the rules of ternary arithmetic.

16. A method as in claim 15 wherein the alphabet letters are regarded as the following triples of ternary digits in the radix 27 number system:

17. A method of generating a sequence of pseudo-random digits

by utilizing the carry digits arising in the formation of .vertline.r.sup.p.sup.+1 .vertline..sub.M by multiplication of .vertline.r.sup.p .vertline..sub.M by r modulo M where m is a prime M=m.sup.n, r is a primitive root of m so chosen that N = (m-1) m.sup.n.sup.-1 and that (m-1)/r = an integer.

18. A method of generating a sequence of binary digits based upon Boolean vectors obtained from transforms of the digits in the powers .vertline.2.sup.p .vertline..sub.M where m is a prime, M=m.sup.n, r=2 is a primitive root of m and m is so chosen that the number of distinct power is N = (m-1)m.sup.n.sup.-1 and the transform is defined by

and thus made identical with the carry digits generated by multiplying .vertline.2.sup.p .vertline..sub.M by 2 modulo M to form

19. A method of generating a sequence of pseudo-random binary digits

by utilizing the carry digits arising in the formation of .vertline.2.sup.p.sup.+1 .vertline..sub.M by multiplication of .vertline.2.sup.p .vertline..sub.M by r=2 modulo M when m is a prime being 2 as a primitive root and so chosen that N = (m-1) m.sup.n.sup.-1.

20. A cryptographic system for encrypting the programs, input, and output of computers and data processing machines comprising:

a. generating the powers .vertline.2.sup.p .vertline..sub.M where M=m.sup.n, m is a prime having r=2 as a primitive root, and m is so chosen that the number of distinct powers of 2 modulo M is N=(m-1)m.sup.n.sup.-1

b. applying the transformation T(dpq) to digits of .vertline.2.sup.p .vertline..sub.M to form Boolean vectors having all digits 0 or 1,

c. partitioning the Boolean vectors into two subsets such that each subset has an equal number of vectors and an equal number of vector occurrences in the range 0 .ltoreq. p < N,

d. using one of the subsets to define a Boolean function to produce pseudo-random binary digits,

e. combining the pseudo-random digits with the digits representing program input data, and output data for purposes of encoding and decoding.

21. A cryptographic system for encrypting the programs, input, and output of computers and data processing machines comprising:

a. generating a sequence of pseudo-random digits of great period, and

b. combining the pseudo-random digits with digits representing program input data, and output data for purposes of encoding and decoding.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to the field of cryptography and particularly to the generation of pseudo-random digits of very great periodicy for use in a cryptographic system.

2. Description of the Prior Art

In the prior art, electromechanical devices have been employed for the generation of a series of digits to be employed in the cryptographic treatment of messages in preparation for transmission. The speed and range of such devices are necessarily limited by their mechanical character. Further they are noisy and subject to the undesirable radiation of electromagnetic signals.

The present day cryptographic machines are intended primarily to meet the needs of the military and the affairs of state. Such machines are too large and expensive to even be considered for application in common data processing operations.

Automatic computers, especially those interconnected by communication networks, have the power to be of inestimable value in the affairs of government, industry, and commerce; indeed data processing systems have become so vast and so complicated that present day operations could hardly exist in the absence of information processing machines. This statement is especially true when applied to the manipulation of the huge data banks often stored in memory systems of computer networks. Such data banks, when properly used, yield important summaries and conclusions necessary in day to day operations and in governmental, industrial, and corporate planning. Their value has also been demonstated in the political, social and medical sciences through the application of statistical sampling and other mathematical techniques.

On the other hand, the very existence of large data banks and the power to draw conclusions from them is often deplored by representatives of government and the academic community as well as others concerned with public welfare. Misapplication of great data systems can lead to results harmful to the state and to the individual whose complete record and personal characteristics are set forth in such files, e.g., the Bureau of the Census, the Internal Revenue Service, and other government agencies. But the Government is not alone in information gathering and storing activities; corporations maintain detailed files on the characteristics of their customers; credit bureaus are prepared to supply credit and other risk information on individuals residing in the area served on a momentary basis. These are in addition to a host of other state, municipal, and private agencies engaged in a great variety of information processing activities intended to minimize the cost of direct by mail advertising, to aid the police in the capture of felons, and to assist in the distribution of welfare funds, for example.

Especially when central computing facilities are wire connected to the diverse and often competing activities which they serve, improper switching operations, either accidental or deliberate, stand as a threat to the integrity of proprietary information. The misuse of private and personal information, and the fear that "big brother is watching you" must be minimized by proper definition of the responsibilities of those engaged in the data processing business. If the misuse of this information is not minimized or eliminated, the public will demand laws to do so. Such legislation can help to protect the public and the individual from acts resulting from the misuse of information, especially by persons within the walls of computer establishments. However, switching errors which result in the delivery of information to improper recipients, and accidental and deliberate wire tapping operations, can still result in serious invasions of privacy of an individual.

At present there is no known cryptographic system which is simple and inexpensive enough to be useful in data processing systems although there is a critical need for such security. Consider, for example, computer programs. Although computer programs can be copyrighted, under certain circumstances, and the U.S. Patent Office is considering applications to patent computer programs, the area of protection is not certain. Most proprietors of computer programs attempt to rely on the law of unfair competition (trade secrets and confidential relationships) to protect their proprietary programs. This type of protection is ethereal and while most consider it the best presently available, is not completely satisfactory for obvious reasons. On the other hand, if computer programs could be sufficiently encrypted so that they could not be decoded except by the proprietor's small device added to his customers' machine, a unique way would be found of keeping a computer program truly a secret.

SUMMARY OF THIS INVENTION

This invention provides a unique and low cost method of generating a string of pseudo-random digits of great periodicy which can be combined with message digits to provide an extremely secure cryptographic system. The cryptographic system is secure even to one who knows how the system works and can only be decoded by one who has the "key" number. Means for changing the key at will are incorporated in the circuitry employed to implement this invention.

The pseudo-random digits used in this cryptographic system are derived from the N = (m- 1)m.sup.n.sup.-1 distinct powers of r modulo M where M = m.sup.n and r is a primitive root of m, a prime. The pseudo-random digits are obtained as follows:

a. First generate the powers of r modulo M by the recurrance relationship

.vertline.r.sup.p.sup.+1 .vertline..sub.M =.vertline.r.sup.. r.sup.p .vertline..sub.M

b. then transfer the digits of .vertline.r.sup.p .vertline..sub.M into a Boolean vector by means of the transformation

T(d) = .delta..sub.0, .delta..sub.1, . . . .delta..sub.m.sub.-1

where the .delta.'s are all 0 or 1 and d is a digit in the radix m number system. In all, 2.sup.m such transformations exist.

c. then partition the Boolean vectors

000 . . . 0 to 111 . . . 11

into two partitions having total equal counts as the powers of r are generated in the interval

0 .ltoreq. p < N

d. Use the Boolean vector corresponding to .vertline.r.sup.p .vertline..sub.M as input to a Boolean function, f (p), defined by the partitions described in (c). The total equal counts there indicated will ensure that the digits generated by the Boolean function will take on the values 0 and 1 substantially an equal number of times in the interval 0 .ltoreq. p < N.

e. Combine the digits f (p) generated by the Boolean function with the digits of the message to be encoded or decoded.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic block diagram view of a cryptographic apparatus of this invention in a generalized sense;

FIG. 2 is a block diagram of the cryptographic apparatus of this invention where r=2, m=5;

FIG. 3 is block diagrams of circuits for modifying a sequence of pseudo-random digits.

For purposes of brevity and clarity, pulse generators, gates, start-stop circuits, end of number controls, and the like all being well known in the computer art have been omitted from the drawings.

DETAILED DESCRIPTION OF THE INVENTION

Because of the mathematical character of this invention, it is necessary to understand the number theory on which it is based in order to obtain a clear understanding of the invention itself.

Consider first the powers of primative roots.

If m is a prime, and r is a primative root of m, then by definition, there are m-1 distinct powers of r modulo m and furthermore

.vertline.r.sup.m.sup.-1 .vertline..sub.m = 1, 1.

Then let

M = m.sup.n, 2.

and let N be the number of distinct powers of r modulo M. There exist small primes such that the number of distinct powers of .vertline.r.sup.p .vertline..sub.M is,

N = (m-1) m.sup.n.sup.-1 3.

In order to establish the validity of (3) for a given r and m it is only necessary to show that

N = (m-1) m,

when 4. M = m.sup.2. In the following description of the invention, it will be assumed that r and m have been properly chosen so that (3) and (4) apply.

Now note that in radix m notation, m.sup.n integers can be expressed in terms of n digits, but of those

N = m.sup.n (m- 1)/m = (m-1)m.sup.n.sup.-1 5.

have a non-zero lowest order digit. Hence, the following:

Theorem: If r is a properly chosen primitive root of m, every n digit integer in radix m notation, having non-zero lowest order digit is an integral power of r modulo M. By "properly chosen" is meant that N=(m-1)m.sup.n.sup.-1 .

Hence, let

z.sub.p = .vertline.r.sup.p .vertline..sub.M 6.

be any integer as proscribed by the theorem chosen at will. Then the recurrence relationship,

z.sub.p.sub.+1 = .vertline.rz.sub.p .vertline..sub.M = .vertline.r.sup.p.sup.+1 .vertline..sub.M 7.

suffices to generate all N powers of r in sucession since the process of reduction modulo M after multiplication is provided by carry overflow.

Next let

d = 0, 1, 2, . . . m-1

be a radix-m digit, and let

T(d) = .delta..sub.0, .delta..sub.1, .delta..sub.2, . . . .delta..sub.m.sub.-1 8.

be a binary transformation. If the digits of z.sub.p are d.sub.pq with

0 .ltoreq. q < n,

and

0 .ltoreq. p < N,

then the transformation (8) transforms z.sub.p into a Boolean vector,

I.sub.p = .delta..sub.p n.sub.-1, .delta..sub.p n.sub.-2, . . . .delta..sub.p1, .delta..sub.p0

In all 2.sup.m, such transformations exist. There is however no loss in generality if T(d) is restricted so that

.delta..sub.0 = 0

Moreover, the transformation

T(d) = 0, 0 . . . 0

and

T(d) = 0, 1, . . . 1

need no consideration since the first reduces all vectors I.sub.p to

I.sub.p = 0, 0, . . . 0,

and the second restricts all of the I.sub.p so that they have unity as lowest order digit .delta..sub.p0.

Then 2.sup.m.sup.-1 -2 transformations remain to be considered. These have the property that all 2.sup.n possible Boolean vectors will be generated as z.sub.p takes on all values in the interval,

0 .ltoreq. p < N 9.

To see this, let the transformation (8) have a zero elements and b unit elements such that

a + b = m,

and consider a vector I.sub.p having .mu. zero elements .nu. unit elements so that

.mu. + .nu. = n.

First let .delta..sub.p0 = 0; then the frequency of occurrence of I.sub.p is,

But, when .delta..sub.pO = 1,

because of the restrictions placed on T(d), neither of the foregoing expressions can give .PHI.=0 for any values of .mu. and .nu.; hence all Boolean vectors are provided by the z.sub.p in the interval (9).

Consider now the theory relating to digit generation. If a and b are restricted so that,

a = b+1, 11.

reference to (10a) and (10b) shows that two Boolean vectors differing only in the element .delta..sub.p0 have the same frequency of occurrence .PHI.. Accordingly, the vectors I.sub.p can always be partitioned into two subsets such that each subset includes 2.sup.n.sup.-1 vectors, and moreover, so that the two subsets have an equal number of vector occurrences, entoto. Hence, the two subsets may be used to define a Boolean function, and its inverse, capable of generating a sequence of binary digits f(p) having period N as z.sub.p takes on all values in the interval (9). Moreover, the number of zero elements and unit elements in this sequence will be equal, thus providing one of the prerequisites that f(p) must meet in order to qualify as a pseudo-random sequence.

Even after the restrictions (8) and (11) are applied, there are

distinct transformations, T(d). Moreover, the number of ways the vectors I.sub.p can be partitioned while maintaining equal numbers of total vector occurrences in the two partitions is enormous inasmuch as the value of .PHI. is determined only by the number of unit elements in a vector.

Among all of these possibilities there exists one that has especially pleasing properties. Let r = 2 and let the transformation be defined as

That is, the definition of T(d) is identical with that of the carry digits arising in multiplication by 2. Since these must be provided in order to generate the z.sub.p when r = 2 , no special procedures are required by (12 ), per se.

Next, let the I.sub.p be partitioned in accordance with the following scheme:

0..0000 0..0001 0..0011 0..0010 0..0101 0..0100 0..0110 0..0111 0..1001 0..1000 0..1010 0..1011 0..1100 0..1101 0..1111 0..1110 .... ....

That is all vectors having an even number of unit digits are put in one subset and those having an odd number of digits are put in the other. Hence, f(p) can be evaluated by the expression:

The foregoing procedures can be extended to some other radices. Let m and r be related by

(m- 1)/r = an integer. 14.

This insures that the carry digits arising from the multiplication of dp0 by r take on each of the values

0, 1, 2, . . . r- 1 15.

an equal number of times. Hence,

represents a sequence of digits of radix r such that each of (15) occurs an equal number of times in the period N. An example is provided by m= 7, r= 3; and,

(m-1)/r = 2.

Since m is odd, r = 2 always satisfies the conditions of (14) but this is not true in general. For example, there is no small prime, m, that meets this restriction when r = 10.

Consider now character sets, including the character sets which are in common use for the representation of numerical and other information. Of these, the three most important are the alphabet, the 10 decimal digits, and a set of 256 "characters," each of which is composed of one of the combinations of the values of eight binary digits used in data processing machines. Since the letters of the alphabet are usually represented by 26 of the 256 characters just described, the alphabet requires special treatment only when the information being processed or transmitted consists primarily of words. It is then of interest to give the letters of the alphabet numerical significance in order to simplify the cryptographic process.

This is most easily done by prefixing the letters of the alphabet with some symbol, say *, to form the ordered set,

*A B C . . . X Y Z.

Then if the asterisk is given the meaning,

* = 0,

the 27 symbols (17) may be taken as the integers of a number system of radix 27. Thereafter, every word becomes a number, and hence, can be manipulated by arithmetic or other rules as in the case of the decimal digits and of the eight digit characters employed in data processing machines.

The addition and multiplication tables of radix 27 arithmetic have,

(27).sup.2 = 729,

entries. Since this number is inconveniently large, it is useful to represent each letter of the alphabet by three ternary digits in accordance with the scheme exhibited in Table I. --------------------------------------------------------------------------- TABLE I

* 000 I 100 R 200 A 001 J 101 S 201 B 002 K 102 T 202 C 010 L 110 U 210 D 011 M 111 V 211 E 012 N 112 W 212 F 020 O 120 X 220 G 021 P 121 Y 221 H 022 Q 122 Z 222 __________________________________________________________________________

as is well known, numbers represented in a number system of radix m may be translated to the equivalent values in the number system of radix M when,

M= m.sup.n,

by the simple process of pointing off the radix m digits into groups of n , and translating each group of digits into a single digit of radix M.

The reverse process consists of replacing each radix M digit by its equivalent in the radix m number system. These devices are available when dealing with the letters of the alphabet inasmuch as,

27 = (3).sup.3 ;

hence all arithmetic operations on letters of the alphabet are best carried out in radix 3 arithmetic for which the addition and multiplication tables are exhibited in the following tabulations: ##SPC1##

As an example of radix 27 addition consider:

USAF+FTD = 210201001020 + 020202011 = 210221210101 = UYUJ

this can be verified by reference to the above tables.

An example of radix 27 multiplication is:

WE .sup.. US = 212012 .sup.. 210201; = 200122012112; = RQEN;

this result may be verified by ordinary multiplication in radix 3 arithmetic.

Once the arithmetic nature of information has been recognized, it should be clear that any suitable mathematical function may be used as the basis of the cryptographic system. However, practical considerations dictate that:

a. The encoding process should not greatly increase the message length;

b. Characters should be encoded as individuals. Otherwise a transmission error could render all that part of a message following an error as unintelligible to the recipient even when provided with the appropriate cryptographic key.

Accordingly, most cryptographic systems are based on character by character combinations of the symbols of the message with those in a series of pseudo-random digits provided by a digit generator.

For example, let it be required to encode a clear message, C, with the digits, R, and let the encoded message ready for transmission be called T. Further, let the i.sup.th digits of C, R, and T be designated as C.sub.i, R.sub.i, and T.sub.i, respectively, where

i = 1, 2, 3, . . . .

Then the encoding process can be accomplished by the function

T.sub.i = f (C.sub.i, R.sub.i)

provided f (C.sub.i, R.sub.i) has the following properties:

1. The function must be single valued;

2. It must have a single valued inverse:

C.sub.i = f.sup..sup.-1 (T.sub.i, R.sub.i)

3. The frequencies of the several symbols in T should be nearly uniform so as to provide no clues to a cryptographer attempting to break the system;

4. The evaluation of the function and of its inverse should require only simple rules so as not to increase the cost and complexity of the cryptographic equipment.

A great many functions exist all of which satisfy the foregoing conditions. However, there is one having especially pleasing properties when viewed in connection with the design of cryptographic machines as a whole. This statement will be increasingly clear in consideration of the following; Assume the digits T are defined by,

T.sub.i = .vertline.C.sub.i + R.sub.i .vertline..sub.r 18.

read, "the sum of C.sub.i and R.sub.i modulo r," where r is the radix of the number system in which C.sub.i, R.sub.i, and T.sub.i are expressed. The above expression (18) may be solved for C.sub.i so that

C.sub.i = .vertline.T.sub.i + R.sub.i .vertline..sub.r 19.

where R.sub. i is the m complement of R.sub.i ; that is, when,

R.sub.i = 0, 1, 2, . . . r- 2, r-1,

then

R.sub.i = 0, r-1, r-2, . . . 2, 1,

As previously stated, any mathematical function meeting the conditions here stated may be used as the basis of a cryptographic system. However, formulas (18) and (19) will be taken as the defining equations for encoding and decoding procedures adopted.

EXAMPLE 1

Let

C = the fleet . . . ,

= 202022012020110012012202

for which m= 3. Further, let

R = 200011112120122022220112.

then,

T = 102000121110202001202011,

= k*pltatd.

but,

R = 100022221210211011110221;

so that the clear message may be recovered by the application of (19) as can be seen.

EXAMPLE 2

Let

C = 10110111 00101001 . . .

for which m = 2. Then if

R = 11000100 11010100 . . .

(18) gives

T = 01110011 11111101 . . .

in modulo 2 arithmetic, R and R are identical; hence C may be recovered by a second addition of R, modulo 2. This pleasing relationship simplifies the cryptographic equipment needed when operating in a system where r = 2.

In most practical cryptographic applications, the digits R are generated by a device making use of some predictive rule. Since all such devices are finite, they operate periodically; that is after cycling through N digits they repeat the sequence again and again. However, no two messages in close proximity should be encoded with the same digits R. Such practice would inevitably provide clues to an analyst attempting to read the encoded messages, and thus break the system. This can only be accomplished by making the period of the digit generator very great. With this invention, it is practical to choose the design parameters in order that the period of the generator is so great that it would not be repeated in a thousand years by a machine generating digits at 1,000 megacycles.

Consider now the following possible systems. In the first Example, consider the possibility of a system for the generation of radix 2 digits (a binary system). Since 2 is a primitive root of m = 3, and

(m-1)/r = (3-1)/ 2 = 1,

then,

N = 2 .sup.. 3.sup.n.sup.-1,

and

This scheme has the advantage of extremely simple arithmetic and the disadvantage of relatively large n for a given N.

As a second example, consider,

(m-1)/r = (5-1)/2 = 2

and

.vertline.2.sup.p .vertline..sub.5 = 1, 2, 4, 3, when p = 0, 1, 2, 3, so that m = 5 can also be used to devise a system for the generation of digits of radix 2. On the other hand,

.vertline.2.sup.p .vertline..sub.7 = 1, 2, 4, when p = 0, 1, 2

That is, 2 is not a primitive root of 7. Hence m = 7 is not permissible.

Another example is provided in the case of m = 37; r = 18 for which it may be shown by computation that

.vertline.18.sup.36 .vertline..sub.1369 = .vertline.18.sup.36 .vertline..sub.37.

Hence m = 37 and r = 18 do not satisfy the requirement that

N = (m- 1)m.sup.n.sup.-1.

Consider another example. Let m = 7 and r = 3. Since,

.vertline.3.sup.p .vertline..sub.7 = 1, 3, 2, 6, 4, 5, when p= 0,1,2,3,4,5

and

(m-1)/r = (7- 1)/3 = 2,

these parameters are satisfactory for the generation of ternary digits to be used in encoding the letters of the alphabet.

As another example, there exists no small prime having 4 as a primitive root. But 4 = 2.sup.2 ; hence a sequence of radix 4 digits is most easily obtained by taking radix 2 digits in pairs. A similar remark applies to radix 8 digits; these may be obtained by taking radix 2 digits in threes. Again radix 9 digits are most easily provided by taking radix 3 digits in pairs. Such simple devices are applicable in the case of other radices including 10.

To show that the cryptography of this system is more than adequate to meet all the needs of cryptographic practice, assume that a cryptographic machine is capable of generating 1,000 megadigits per second and the period of the machine is so great that 1,000 years would be required to complete a single cycle. Then, if m=7, it follows that N = 6 .sup.. 7.sup.n.sup.-1 = 1,000 .sup.. 365 .sup.. 86,400 .sup.. 10.sup. 9 from which n = 23 approximately.

The cryptographic system of this invention, as has been described, utilizes pseudo-random digits to encode and decode data and provides for pseudo-random number generation of great periodicy by first generating the powers of r modulo M where M = m.sup.n, m is a prime number, r is a primitive root of m, and r is chosen such that N = (m-1) m.sup.n.sup.-1, then transforming digits of the powers into Boolean vectors, entering the Boolean vectors into a Boolean function to generate pseudo-random digits.

Apparatus for accomplishing this is shown in FIG. 1 having a manual switch 11 or other means for introducing into a radix m multichannel serial delay line 12 an initial value of

z.sub.p = .vertline.r.sup.p .vertline..sub.M.

This initial value functions as the cryptographic key. The delay line is connected to and through a transformation means 14 to a times r multiplier 16. The output of the multiplier is returned to the delay line for recirculation after execution of the recurrance relationship,

z.sub.p.sub.+1 = .vertline.r z.sup.p .vertline..sub.M = .vertline.r.sup.p.sup.+ 1 .vertline..sub.M.

From the transformation means 14 the transforms of the digits of z.sub.p are taken to the circuit 18 where the pseudo-random digits f(p) are generated. The digits f(p) are then successively delivered to the encoding-decoding circuit 22 through the manually operated "code-decode" switch 21 where they are serially added to the digits of the clear message at the "input" to provide the encrypted message at the "output." When the manually operated "code-decode" switch is in the decode position, the digits f(p) pass through the r-complement circuit 20 in which case an encoded message at the input is decoded at the output.

Consider next a specific example, the case of r = 2, m = 5, and n = 10 for which

N = 4 .sup.. 5.sup.9 ;

= 7,812,500.

let

T(d) = 0,0,0,1,1,

where

d = 0,1,2,3,4;

and take

.vertline.2.sup.p0 .vertline..sub.M = 4442020332 (the cryptographic key chosen arbitrarily)

in the number system of radix 5. Then if

p = p.sub.0 + h

Table III gives f(p) in the interval

0 .ltoreq. h < 480.

The column headed "k" in the Table is the count of the carry digits or the 3 and 4 digits in .vertline.2.sup.p .vertline..sub.M for which .delta..sub.pq = 1, hence

f(p) = .vertline.k.vertline..sub.2

FIG. 2 shows a system designed to operate in accordance with the foregoing discussion. Referring to the Figure, the serial delay line 100 is provided with a switch 120 for introducing the cryptographic key or initial value known to both the coder and the decoder. Thus,

4442020332

is the arbitrarily chosen value to be used for purposes of illustration.

After this has been multiplied by 2 in radix 5 notation by the times 2 circuit 160, the product,

4434041214

as shown in line 1, column h of Table III is returned to the delay line. During the formation of this product, the carry digits generated were

1110000110.

Of these carry digits five were ones as indicated in the right hand column K of the Table. These carry digits were added modulo 2 by the adder 180 as the multiplication by 2 was in process thus forming the value of f(p) given in line 0 of the Table. The output of the mod 2 adder 180 is delivered to the mod 2 adder 200 for combination with the message delivered at the input. Since the 2-complement of a binary digit is equal to itself, no manual adjustment is needed to pass from the coding to the decoding mode.

While the value of n used in this example is too small for cryptographic practice, it is large enough to illustrate the application of this invention.

The pseudo-random digit sequence provided by this invention is sufficient to make decipherment during any useful time period virtually impossible. Nevertheless, certain techniques may be employed to make the probability of decipherment even smaller. The additional devices to be employed are primarily circuital in character and employ trigger pairs controlled by puller functions and delay lines to alter the character of the digit sequence, f(p). Since the number of such devices is practically unlimited, their use will be illustrated by examples.

When m = 5, r = 2, and n = 10, as in Table III, let

x.sub.9 (d) = 0, 0, 0, 1, 0

y.sub.9 (d) = 0, 0, 1, 0, 0

when

d = 0, 1, 2, 3, 4

be transforms applied to the highest order digits of z.sub.p. Further let

x.sub.0 (d) = 0, 0, 0, 1

y.sub.0 (d) = 1, 0, 0, 0

when

d = 1, 2, 3, 4

be transforms applied to the lowest order digit of z.sub.p. Then the puller function

P.sub.0 = x.sub.9 x.sub.0

and

P.sub.1 = y.sub.9 y.sub.0

can be used to control a trigger pair which can in turn be employed to alter the character of f(p).

Note that the puller functions can take on the pairs of values,

P.sub.0,P.sub. 1 = 0, 0; 0, 1; 1, 0.

They cannot, however, assume the pair of values

P.sub.0,P.sub. 1 .noteq. 1, 1.

Hence, when the trigger pair is pulled into its 0 position it will remain there until the highest order digit of some subsequent value of z.sub.p contains a 2 digit at the same time the lowest order digit is a 1. The trigger will then be pulled into its 1 position where it will remain until some value of z.sub.p provides a highest order digit 3 and a lowest order digit 4 at which time the trigger will return to its 0 position again.

The block diagrams of FIG. 3 represent circuitry for altering the character of the digit sequence f(p) in accordance with the puller functions P.sub.0, P.sub.1. In the general case the puller functions may be dependent upon any or all of the digits of z.sub.p. Since these digits are serially available at the output of the delay line 100, it will be recognized that the transformation means shown in FIG. 3 include storage elements to insure the simultaneous availability of the digits.

The two states of the trigger pair controlled by the 0 and 1 puller circuits can be used as illustrated in FIG. 3 to:

I. complement or not complement the digits of f(p) according to trigger state, see FIG. 3I,

Ii. delete or not delete the digits of f(p) according to the trigger state, see FIG. 3 II,

Iii. open or close the gates at the input and output of a delay line so that blocks of digits can be deleted from or inserted into the digit stream according to the trigger state, see FIG. 3 III.

Needless to say, circuits can be controlled by two or more triggers, and the control of the triggers can be vested in the variables x.sub.1, x.sub.2, . . . x.sub.n ; y.sub.1, y.sub.2, . . . y.sub.n, or in still other triggers. Indeed with 20 inputs and 20 internal triggers, circuits can be made so complicated that an observer who sees only the inputs and outputs can hardly be expected to deduce the wiring diagram in a single lifetime.

From the foregoing, it can be seen that this invention provides a relatively low cost, small size, low power consumption and highly reliable digit generator for cryptographic applications to provide pseudo-random numbers of extremely long periodicy. The apparatus built with components using integrated circuit techniques is not much larger than a package of cigarettes excluding read in and read out equipment. It is of a size and cost sufficient to enable it to be economically incorporated in typewriters or tape machines for encoding and decoding purposes.

* * * * *

Current U.S. Class:	380/28 ; 331/78; 380/44; 705/55; 713/190
Current International Class:	H04L 9/18 (20060101); H04L 9/22 (20060101); H04l 009/04 ()
Field of Search:	178/22