|
|
|
Having particular key generator |
Machine generation of cryptographic keys by non-linear processes similar to processes normally associated with encryption of data5297207
Abstract
A keystream generation system for producing a cryptographically secure keystream by an "amorphous" process. Three types of keystream generation are preferred. A large seed key is directly amorphously expanded into a cryptographically secure keystream. A small seed key seeds a pseudo random number generator whose output is made cryptographically secure through a contracting amorphous process or, alternately, the security of an extended keystream is strengthened through contraction. Finally, a state machine whose output and transition functions are based on amorphousness recursively operates on a seed key to generate an arbitrarily long, cryptographically secure, keystream. The recursive performance of such amorphous logical operations on seed keys in order to generate keystreams is akin to the encryption of data.
Claims
What is claimed is:
1. A machine for generating a cryptographic key by processes similar to those normally associated with encryption of plain text data, the machine comprising:
1) a base key source for providing a set of essentially random bits defined as a base cryptographic key;
2) a partition index source for providing an essentially random number called an amorphous partition index; and
3) an amorphous processor, receiving the base key from the base key source means and the amorphous partition index from the random number source,
for performing on the base key
a generalized combination with substitutions
in accordance with use of the amorphous partition index as a directive
in order to produce another essentially random set of bits called an amorphous bitstream, the amorphous processor including
3.1) a selector for selecting from the base key in accordance with the amorphous partition index a selected set of bits,
3.2) a sequencer for sequentially ordering the selected set of bits in accordance with the amorphous partition index to produce an ordered selected set of bits, and
3.3) a logical complimenter for logically complementing the ordered selected set of bits in accordance with the amorphous partition index to produce a logically-complemented ordered selected set of bits called an amorphous bitstream;
wherein a generalized combination with substitutions is performed on the base cryptographic key in accordance with the amorphous partition index; and
wherein the generalized combination with substitutions performed on the base cryptographic key, which base key is itself an essentially random set of bits, in accordance with the amorphous partition index, which partition index is itself an essentially random number, by the amorphous processor constitutes a process describable as amorphous, which is why the amorphous processor is called such, and is likewise why the set of bits produced by the amorphous processor is called an amorphous bitstream;
wherein the amorphous process by which the base cryptographic key is used to produce the amorphous bitstream is, because it is a generalized combination with substitutions, itself in the nature of a cryptographic transform;
as a cryptographic key likewise as is the base cryptographic key from which it is derived;
wherein no order has been imparted to the cryptographic keystream by the amorphous transformation thereof.
2. The machine according to claim 1
wherein the selector of the amorphous processor permissibly selects from the base key, in accordance with the amorphous partition index, a subset of bits that includes multiple instances of bits of the base key set;
wherein the selected set permissively contains more bits than are within the base key.
3. The machine according to claim 1 further comprising:
encryption means for using the amorphous bitstream produced by the amorphous processor as a cryptographic key in a cryptographic transform.
4. The machine according to claim 1 for generating an extended-length cryptographic key, the machine further comprising:
4) a feedback means, receiving the amorphous bitstream from the amorphous processor, for mapping the received amorphous bitstream into (i) a new amorphous partition index and (ii) a keystream portion, and for feeding back the new amorphous partition index to the amorphous processor for use therein and thereby; and
5) a recursive control means for repetitively cyclically exercising the amorphous processor and the feedback means so that, over a plurality of cycles, a plurality of amorphous bitstreams are produced by the amorphous processor and a plurality of keystream portions are produced by the feedback means;
wherein the amorphous processor recursively performs on the base key successive generalized combinations with substitutions in accordance with successive amorphous partition indices in order to produce a plurality of successive amorphous keystream portions;
wherein the plurality of successive amorphous keystream portions constitute, in aggregate, the extended-length cryptographic key;
wherein a recursive amorphous process by which the base cryptographic key is used, in successive cycles, to produce the extended-length cryptographic key is, because it is still a generalized combination with substitutions, still itself in the nature of a cryptographic transform.
5. The machine according to claim 4 wherein the amorphous processor comprises:
a mapping means which expands a received amorphous partition index into an amorphous bitstream of a greater number of bits than are within the amorphous partition index;
wherein feedback of the new amorphous partition index will leave one or more bits for the keystream portion;
wherein, because the amorphous process produces a number of bits beyond the partition index size, the amorphous process is called an expansion process and the amorphous processor is called an expanding amorphous processor.
6. The machine according to claim 1 for generating an extended-length cryptographic key, the machine further comprising:
6) a random number source for providing a supply of essentially random numbers;
7) a cycle control means for repetitively exercising the amorphous processor and the random number source so that, over a plurality of cycles, a plurality of amorphous bitstreams are produced by the amorphous processor;
wherein the random number source provides for a new amorphous partition index for each cycle, or in addition, the random number source provides for a new base key for each cycle as well;
wherein the entire amorphous bitstream is used as a keystream portion;
wherein the plurality of successive amorphous keystream portions constitute, in aggregate, the extended-length cryptographic key.
7. The machine according to claim 6 wherein the amorphous processor comprises:
a mapping means which contracts a received amorphous partition index into an amorphous bitstream of fewer bits than the amorphous partition index;
wherein a so5rce of amorphous partition indexes is necessary to produce a keystream;
wherein, because the amorphous process produces a number of bits fewer than the partition index size, the amorphous process is called a contracting process and the amorphous processor is called an contracting amorphous processor.
8. The machine according to claim 7 wherein the random number source comprises:
an expanding amorphous processor in a feedback configuration;
wherein cryptographic security of the plurality of amorphous bitstreams, and of the cryptographic key, generated by the machine is achieved by the contraction process;
wherein, because the expanding amorphous processor of the random number source expands while the mapping means of the amorphous processor, which amorphous processor uses the random number as a new amorphous partition index and a new base key for each cycle, contracts, the entire process is called an amorphous teeter-totter process.
9. The machine according to claim 6 wherein the random number source comprises:
a cryptographically insecure random number generator;
wherein cryptographic security of the plurality of amorphous bitstreams, and of the cryptographic key, generated by the machine is achieved by the contraction process.
10. An expanding-amorphous-process keystream generator for recursively producing
from a base key having a multiplicity of binary bits
in accordance with a partition index that serves to specify how an amorphous bitstream is to be formed from the base key,
which partition index is itself decomposed during its use by a parameter called a partition descriptor,
an amorphous keystream having binary bits of number greatly beyond those needed before cyclic behavior commences, the expanding-amorphous-process keystream generator comprising:
1) source registers for providing three quantities that are input to the keystream generation process, the source registers including
1.1) a base key source register for providing a base key having a multiplicity of binary bits,
1.2) an initial partition index source register for providing an initial partition index, the initial partition index serving to specify how an amorphous bitstream is to be formed from a base key, and
1.3) a partition descriptor source register for providing a partition descriptor, the partition descriptor serving to parameterize the decomposition of partition indexes;
2) process intermediary-result registers including
2.1) a base key register for storing the base key,
2.2) a partition descriptor register for storing the partition descriptor,
2.3) a partition index register for storing a current partition index commencing with the initial partition index,
2.4) a plurality of element descriptor registers each for storing a quantity called an element descriptor, each element descriptor elsewhere serving to parameterize a dividing of the base key into a data portion called an element, the collective element descriptors collectively serving to substantially define how a partition is to be performed on the base key to produce a plurality of elements therefrom,
2.5) a plurality of current-and-master holdback-register pairs, one register pair corresponding to each of the plurality of elements, each for holding a quantity called multiplexing information, the collective multiplexing information elsewhere serving to control the multiplexing of data from a the plurality of elements during formation of an amorphous stream, and
2.6) a plurality of emission-fragment-and-emission-count register pairs, one register pair corresponding to each element, each pair for holding a quantity called an emission fragment and also another data quantity called an emission count, these emission fragments and emission counts elsewhere serving to control the multiplexing of data from a corresponding element during the formation of the amorphous stream;
3) a partition extractor circuit means, receiving a current partition index from the partition index register and the partition descriptor from the partition descriptor register, for decomposing the current partition index in accordance with the partition descriptor into (i) a plurality of initial element descriptors for storage by the plurality of element descriptor registers, (ii) a plurality of multiplexing information for storage by the plurality of current-and-master holdback-register pairs, (iii) initial element chaining information for storage and use within a holdback multiplexer, and (iv) current element information for storage and use within the holdback multiplexer;
4) an emission generator circuit, receiving the base key from the base key register means and successive element descriptors from successive ones of plurality of element descriptor registers, for transforming each element descriptor into the emission fragments and the emission counts which are stored by the plurality of by emission-fragment-and-emission-count register pairs, and for storing a plurality of modified element descriptors back into the plurality of element descriptor registers, the emission generator means operating to
choose bits from among the bits of the base key in accordance with each element descriptor, and
selectively substitute bits in accordance with the same element descriptor;
5) a holdback multiplexer, receiving the emission fragments from the plurality of emission-fragment-and-emission-count register pairs plus multiplexing information from the current-and-master holdback-register pairs plus initial element chaining information and current element information from the partition extractor, for forming an amorphous stream by selecting bits from the emission fragments where each selection is subject to suspension for a given element cycle based on the multiplexing information;
6) a stream router means, receiving the amorphous stream from the holdback multiplexer,
for passing an initial portion of the amorphous stream to the partition index register means, and
for outputting a remainder of the amorphous stream as the keystream fragment; and
7) a control means including
7.1) an initialization cycle means serving to load the base key storage register means, the partition descriptor register means, and the partition index register means with their corresponding initial quantities respectively from the base key source register means, the partition descriptor source register means, and the initial partition index source register means,
7.2) a partition extraction cycle means serving to load the plurality of element descriptor register means, the holdback-register pairs, and the link registers internal to the holdback multiplexer means with quantities derived by the partition extractor means from its decomposition of the current partition index received from the partition index register means, and
7.3) a holdback multiplexer cycle control means for controlling the holdback multiplexer to generate the amorphous stream;
wherein feedback is provided through a next partition index which permits another partition and hence another amorphous stream to be formed;
wherein a plurality of keystream fragments result;
wherein a concatenation of successive keystream fragments is defined as the keystream.
11. The keystream generator according to claim 10 wherein the 5) holdback multiplexer comprises:
5.1) pairs for storing a doubly-linked list of the elements;
5.2) a target register for holding an address of a current element being multiplexed;
5.3) an emission counter for decrementing values contained in the emission count registers;
5.4) a holdback counter for decrementing values contained in the current holdback registers; and
5.5) a shift register for parsing bits from the emission fragment registers to form an amorphous stream.
12. The keystream generator according to claim 11 wherein the 5.1) plurality of previous-and-next-element-link register pairs means comprises:
5.1.1) a plurality of sets of previous-and-next-element-link register pairs with each set forming an chain of permuted elements;
wherein the multiplexing of element emissions proceeds by successive processing of the chains with each chain processed by assessing each element of that chain once, until all elements are exhausted.
13. The keystream generator according to claim 10 wherein the 7.3) holdback multiplexer cycle control means comprises:
7.3.1) an emission counter loading/decrementing/transferring control means for loading the emission counter means with an emission count of a target element, for decrementing the emission counter, and for transferring the decremented contents of the emission counter means back to the emission count register save for, alternatively, aborting the store cycle whenever a holdback suspension occurs or whenever an emission count is zero in which case a refill request to the emission generator is required;
7.3.2) a holdback counter loading/decrementing/transferring control means for loading the holdback counter means with a current holdback of a target element, for decrementing the holdback counter, and for transferring the contents of the holdback counter back to the current holdback register save for, alternatively, transferring a master holdback to the current holdback register whenever the decrement operation results in zero in which case a suspension has occurred;
7.3.3) a shift register loading/shifting/transferring control means for loading the shift register means with an emission fragment of a target element, for shifting the shift register means, for transferring the shifted bit to the amorphous stream, and for transferring the shifted contents of the shift register means back to the emission fragment;
7.3.4) a target element advancement control means for storing the target element contents of the element link next register in the target register means;
7.3.5) an element delinking control means for unmapping a target element from the element link registers by modifying proper registers therein whenever an element emission exhausted signal is received from the emission generator means upon a refill request failure;
7.3.6) a termination control means for detecting the unmapping of the last element and then signaling the partition extractor to evoke another partitioning of the base key; and
7. 3.7) a multiplexer cycle control means for controlling the holdback multiplexer to generate the amorphous stream, the multiplexing cycle means including
7.3.7.1) an emission count reset cycle means for zeroing the emission-count registers before processing a new partition,
7.3.7.2) an element selection means for cyclically successively selecting an element,
7.3.7.3) an emission count fetch means for reading the emission count register of the selected element,
7.3.7.4) a refill cycle means for filling the selected emission register pair whenever the emission count is zero, the refill being accomplished by sending a request to the emission generator means,
7.3.7.5) an element unlink means for removing an element from the chain of elements by modifying the element link registers whenever a refill emission request returns an element exhausted signal,
7.3.7.6) a current holdback fetch means for reading the current holdback register of the selected element, and
7.3.7.7) means for returning to the partition extraction cycle means once all elements are exhausted;
14. The keystream generator according to claim 13 wherein the 4) emission generator means comprises:
4.1) a plurality of work registers which duplicate those of an element descriptor except for the path register;
4.2) a fronts buffer, being a shift-right register for holding the next front bits used while forming an element emission;
4.3) a fronts counter, being a count-down counter for holding the number of valid bits in the fronts buffer;
4.4) a tails buffer, being a shift-left register for holding the next tail bits used while forming an element emission;
4.5) a tails counter, being a count-down counter for holding the number of valid bits in the tails buffer;
4.6) a shift register for filling the fronts and tails buffers;
4.7) a path and substitution generator means for providing a stream of path selection bits and substitution bits used to form emission fragments;
4.8) an XOR means for forming emission bits;
4.9) an emission buffer, being a shift-right register for collecting the emission bits;
4.10) an emission counter, being a count-up counter for holding the number of valid bits in the emission buffer;
4.11) an emission controller means for processing a refill request from the holdback multiplexer, the emission control means including
4.11.1) a means for loading the work registers and internal registers of the path and substitution generator with the contents of the element descriptor selected by the target register,
4.11.2) a means for checking if the remainder work register is zero whereupon the refill request is terminated by sending an element exhausted signal,
4.11.3) a means for filling the fronts buffer and fronts counter including
4.11.3.1) a means for loading the sift register with a word from the base key whose address is formed by taking the current front work register value and shifting it to the right by a number determined by the number of bits in a word,
4.11.3.2) a means for pulsing the shift register to the right by a number determined by the least significant bits of the current front work register whereupon the result consists of the leading bits of the next front bits,
4.11.3.3) a means for transferring the shift register contents to the fronts buffer,
4.11.3.4) a means for computing the number of valid front bits fetched through computations based on the current front work register and last front work register values,
4.11.3.5) a means for initializing the fronts counter with the computed count value;
4.11.4) means for filling the tails buffer and tails counter which utilizes and operates in a manner symmetrical to the means used to fill the fronts buffer and fronts counter;
4.11.5) a means for resetting the emission counter to zero,
4.11.6) a means for forming an emission bit including
4.11.6.1) a means for receiving a path selection bit from the path and substitution generator,
4.11.6.2) a means for pulsing either the fronts or tails buffer selected by the path selection bit to obtain an element bit,
4.11.6.3) a means for receiving from the path and substitution generator a substitution bit which is XORed with the element bit to form an emission bit using the XOR means,
4.11.6.4) a means for advancing the bit address in the associated current front or tail work register wrapping the address is necessary to either the first front value or last tail value, and
4.11.6.5) a means for pulsing either the fronts or tails counter selected by the path selection bit and refill associated buffer and counter whenever the decrement operation results in zero,
4.11.7) a means for pulsing the emission buffer to load the emission bit,
4.11.8) a means for pulsing the emission counter and to detect emission buffer full,
4. 11.9) a means for decrementing the remaining count work register and detect whenever the element emission is exhausted,
4.11.10) a means for pulsing the emission buffer to right justify the contents upon an exhausted element emission,
4.11.11) a means for transferring the emission buffer and emission counter contents to the emission fragment and emission count register pair, and
4.11.12) a means for saving the contents of the modified work registers and internal registers of the path and substitution generator to the element descriptor selected by the target register.
15. The keystream generator according to claim 14 wherein the 4.7) path and substitution generator means comprises:
4.7.1a) a path selection generation means including
4.7.1.1) a linear shift register with feedback provided directly from the linear shift register's output wherein an output bit-stream is uses successively as path selection bits; and
4.7.2) a substitution generation means including
4.7.2.1) a linear shift register with feedback provided directly from the linear shift register's output wherein output bit-stream is used successively as substitution datum bits.
16. The keystream generator according to claim 14 wherein the 4.7) path and substitution generator means comprises:
4.7.1b) a maximal length linear shift register whose output bit-stream is alternately passed as path selection bits and substitution bits.
17. The keystream generator according to claim 14 wherein the 4.7) path and substitution generator means comprises:
4.7.1c) a compound linear shift register.
18. The keystream generator according to claim 10 wherein the 2.4) plurality of element descriptor registers each for storing a quantity called an element descriptor comprise:
2.4.1) a first front register;
2.4.2) a current front register;
2.4.3) a last front register;
2.4.4) a first tail register;
2.4.5) a current tail register;
2.4.6) a last tail register;
2.4.7) a remainder register; and
2.4.8) a path register;
AND WHEREIN the 3) partition extractor circuit means comprises:
3.1) a partition index decomposition means for decomposing the partition index into (i) a permutation selector and (ii) a plurality of partition element specifiers;
3.2) a partition element specifier decomposition means for decomposing each of the plurality of partition element specifiers into a plurality of specification fields wherein each of the specification fields individually parameterizes a corresponding element, to wit
(i) a size specification field specifies the number of bits in each the element,
(ii) a hole specification field specifies the number of leading bits in the element to be excluded,
(iii) a path-picking specification field specifies a substitutive path to be taken within the non-hole element bits,
(iv) an initial item specification field specifies the starting bit for the substitutive path,
(v) a truncate specification field specifies a limit to the length of the substitutive path,
(vi) an initial holdback specification field specifies an initial value for the holdback counter, while
(vii) a master holdback specification field specifies a holdback reset value for the holdback counter;
3.3) evaluation means for processing the specification fields into element descriptor and holdback values therein to define a partition on the base key in the form of a plurality of contiguous elements, the element descriptor contained within each of the plurality of element descriptor registers serving to parameterize a element emission, to wit
(i) the 2.4.1) first front register contains a bit address of the base key of an element's first front bit,
(ii) the 2.4.2) current front register contains a bit address in the base key of the element's current front bit,
(iii) the 2.4.3) last front register contains a bit address in the base key of the element's last front bit,
(iv) the 2.4.4) first tail register contains the bit address in the base key of the element's first tail bit,
(v) the 2.4.5) current tail register contains the bit address in the base key of the element's current tail bit,
(vi) the 2.4.6) last tail register contains the bit address in the base key of the element's last tail bit,
(vii) the 2.4.7) remainder register contains the number of bits yet to be output as an element emission, and
(viii) the 2.4.8) path register contains a value which parameterizes a substitutive path;
3.4) means for successively transferring the evaluated values to the appropriate registers; and
3.5) permuting means for mapping the permutation selector into a randomly permuted order for the elements whose order is transmitted to the holdback multiplexer by initializing the element link registers therein.
19. The keystream generator according to claim 10 wherein the 3) partition extractor circuit means comprises:
3.1) partition index decomposition means for decomposing the partition index into (i) a plurality of dispersed element specifiers and (ii) a plurality of skipper groups with exactly one skipper group associated with each dispersed element specifier;
3.2) dispersed element specifier decomposition means for decomposing each of the plurality of dispersed element specifiers into a plurality of specification fields wherein each of the specification fields individually parameterizes a corresponding element, to wit
(i) a start point specification field specifies a starting bit in the base key,
(ii) a skip cycles specification field specifies the number of the skippers in the corresponding skipper group,
(iii) a next delta specification field specifies the number of bits to be added to the starting bit to define a secondary starting bit,
(iv) an XOR cycles specification field specifies the number of bits in an xor datum specification field,
(v) an initial holdback specification field specifies the initial value for the holdback counter, and
(vi) a master holdback specification field specifies the holdback reset value for the holdback counter;
3.3) evaluation means for processing the specification fields and a skipper group into element descriptor and holdback values thereby defining a partition on the base key in the form of a plurality of dispersed elements wherein the registers of each element descriptor parameterize a element emission, to wit
(i) a start register contains the bit address in the base key of the element's initial bit,
(ii) a pointer register contains the bit address in the base key of the element's current emission bit;
(iii) a skipper count register contains the number of valid skippers in the skipper table,
(iv) a skipper table is contained in a plurality of registers of sufficient number so as to hold the maximum possible count of skippers,
(v) a current skipper register selects some skipper in the skipper table,
(vi) a delta register contains the incremental value used to form a secondary starting bit or zero upon beginning generation of the secondary portion of the emission, as the case may be,
(vii) a tap register contains the feedback tap point for the dispersed substitution generator,
(vii) a XOR datum register contains the bit values for the dispersed substitution generator;
3. 4) means for successively transferring the evaluated values to the appropriate registers; and
3.5) means for generating a successive ordering of the elements whose order is transmitted to the holdback multiplexer by initializing the element link registers therein.
20. The keystream generator according to claim 19 wherein the 4) emission generator circuit comprises:
4.1) a plurality of work registers duplicating those of an element descriptor except for the tap and XOR datum register;
4.2) a dispersed substitution generator, being a linear shift register of controllable length employing direct feedback wherein a tap control register specifies the feedback point within the shift register;
4.3) an XOR means for forming emission bits;
4.4) an emission buffer, being a shift-right register for collecting the emission bits;
4.5) an emission counter, being a count-up counter for holding the number of valid bits in the emission buffer;
4.6) a dispersed emission controller means for processing a refill request from the holdback multiplexer, the dispersed emission controller means including
4. 6.1) means for loading the work registers and dispersed substitution generator with the contents of the element descriptor selected by the target register,
4.6.2) means for forming an emission bit including
4.6.2.1) means for fetching the base key bit selected by the pointer work register which is XORed using the XOR means with the output of the dispersed substitution generator to form an emission bit,
4.6.2.2) means for pulsing the dispersed substitution generator to advance the LSR to the next state,
4.6.2.3) means for advancing the pointer work register by adding to it the value of the skipper selected by the current skipper work register, plus one, assuming that arithmetic is such that an overflow wraps to the start address in the base key,
4.6.2.4) means for detecting the pointer crossing the starting bit whereupon the pointer work register is initialized with the secondary starting bit address computed from start and delta work registers with the delta work register zeroed unless the delta was already zero which then signals that the emission is exhausted,
4.6.2.5) means for advancing the current skipper work register by incrementing it once subject to bounding by the contents of the skipper count work register so that it addresses a valid skipper in the skipper work table,
4.6.3) means for pulsing the emission buffer to load the emission bit;
4.6.4) means for pulsing the emission counter and to detect emission buffer full;
4.6.5) means for pulsing the emission buffer to right justify the contents upon an exhausted element emission;
4.6.6) means for transferring the emission buffer and emission counter contents to the emission fragment and emission count register pair selected by the target register in the holdback multiplexer;
4.6.7) means for saving the contents of the modified work registers and dispersed substitution generator to the element descriptor selected by the target register.
21. The keystream generator according to claim 10 wherein the 1.2) initial partition index comprises:
1.2.1) a source of a message key specifying how an initial partition index is to be formed by a non-linear transformation;
1.2.2) a source of an encrypted explosion pointer which parameterizes the partition index formation;
1.2.3) CRC means for transforming a bit stream into its cyclic redundancy code;
1.2.4) a multiplicand register for holding the CRC result;
1.2.5) a holding register, being a shift register;
1.2.6) CEM means for performing a coarse encoder multiplication of an multiplicand and a multiplier stream, the CEM means including
1.2.6.1) means for forming a finite sequence of position value and XOR datum bit pairs from the multiplier stream, and
1.2.6.2) means for forming a product bit by modulo-2 addition of a XOR datum bit with a bit in the multiplicand selected by the corresponding position value;
1.2.7) a bit address register for selecting the next bit in the base key while forming a bit stream;
1.2.8) streamer means for forming a bit stream by successively incrementing the bit address register and outputting the base key bits selected, wherein cyclical addressing is employed;
1.2.9) a plain text RAM for holding a plurality of copies of the message key;
1.2.10) an encoder means including
1.2.10.1) means for forming a permutation selector and an XOR modifier of same size as the plain text from a bit stream,
1.2.10.2) means for adding bitwise modulo-2 the XOR modifier to the plain text, and
1.2.10.3) means for permuting the plain text bits in accordance with the permutation selector;
1.2.11) an expansion RAM for providing a scratch pad area while forming a partition index;
1.2.12) a bus switch means for providing access to the expansion RAM;
1.2.13) an exploder controller means including
1.2.13.1) means for storing a message key in the plain text RAM and to fill the remaining area with copies of the message key,
1.2.13.2) means for feeding the message key to the CRC and to store the result in the multiplicand register,
1.2.13.3) means for storing an encrypted explosion pointer in the bit address register,
1.2.13.4) means for filling the holding register by receiving successive product bits from the CEM which receives a multiplier stream from the streamer,
1.2.13.5) means for storing the holding register in the bit address register,
1.2.13.6) means for transforming the plain text and the streamer's bit stream by means of the encoder with the result stored in the expansion RAM as the first amorphous seed,
1.2.13.7) means for decomposing the first amorphous seed into a first partition index and a first partition descriptor,
1.2.13.8) means for transmitting first partition index and first partition descriptor to the expanding amorphous process keystream generator,
1.2.13.9) means for receiving from the keystream generator the amorphous stream, the stream router passing all of its bits, which is stored in the expansion RAM as a second amorphous seed;
1.2.13.10) means for expanding a second amorphous seed by the same process as first amorphous seed was expanded;
wherein the initial partition index is defined as the amorphous stream stored in the expansion RAM resulting from the second amorphous seed expansion;
wherein the initial partition index is derived from a smaller message key.
22. A contracting amorphous process keystream generator comprising:
1) a random number generator means for providing a random number stream, which random number stream will be amorphously compressed to form a keystream;
2) an XOR means, receiving the random number stream from the generator means, for performing modulo-2 addition on bit pairs derived from the random number stream in accordance with XOR bit values to form a plurality of data bits;
3) a segmented shift register means, receiving the plurality of data bits from the XOR means, for storing these data bits, for deleting a plurality of bit values at given addresses by process of shifting the data bits beyond a specified delete point address to recover a bit address being deleted, and for inserting a plurality of datum bits from the XOR means at specified insert addresses by first shifting the bits at and beyond an insert point to make room for a datum bit to be inserted;
4) a permuting means, receiving the random number stream from the generator means, for generating random permutations by forming a plurality of permuted indexes from the random number stream in accordance with a permutation selector;
5) a contraction controller means for forming the keystream, the contraction controller including
5.1) parsing means, receiving the random number stream from the random number generator means, for decomposing the random number stream into (i) a plurality of bit pairs sent to the XOR means as the XOR bit values, (ii) a permutation selector sent to the permuting means, (iii) a plurality of deletors sent to the segmented shift register means, each deletor serving as an deletion point address therein, and (iv) a plurality of creators sent to the segmented shift register means, each creator serving as an insert address therein, the number of creators being the same as the number of deletors;
5.2) filling means for storing a plurality of datum bits received from the XOR means in the segmented shift register means at addresses that are selected by the plurality of permuted indexes received from the permuting means;
5.3) deletion means for deleting a plurality of bits from the segmented shift register in accordance with deletors received from the parsing means, each deletor successively selects one bit to be deleted;
5.4) creation means for inserting a plurality of datum bits from the XOR means into the segmented shift register means in accordance with creators received from the parsing means, each creator successively selecting an address at which a datum bit is inserted;
wherein, upon completion of operations, the contents of the segmented shift register means forms a keystream fragment;
wherein decomposition of additional random numbers results in a plurality of keystream fragments;
wherein a concatenation of successive keystream fragments is defined as the keystream.
23. The keystream generator according to claim 22 wherein the 4) permuting means comprises:
4.1) an index extractor means for decomposing a permutation selector into a plurality of transposition indexes of quantity one less than the number of bits to permute;
4.2) a permutation buffer, being a plurality of registers of quantity equal to the number of bits to permute;
4.3) a slot counter, being a count-down counter used to address registers within the permutation buffer;
4.4) a permutation controller means for forming the permuted indexes, the permutation controller means including
4.4.1) means for initializing the permutation buffer by successively filling the registers therein with the consecutive integers starting with zero,
4.4.2) means for initializing the slot counter so that it addresses the last permutation buffer register;
4.4.3) means for receiving a transposition index used to address a permutation buffer register whose content is output as a permutated index,
4.4.4) means for storing the contents of the permutation buffer register addressed by the slot counter at the transposition index's location,
4.4.5) means for pulsing the slot counter with a registers exhausted detection capability, and permutation buffer register as a last permutated index,
wherein the transposition indexes are successively transformed into a sequence of permutated indexes which define a permutation.
24. The keystream generator according to claim 23 wherein the 4.1) index extractor means comprises:
4.1.1) a selector parser means for decomposing a permutation selector into (i) a direction value and (ii) a plurality of shuffle indexes with each transposition index to be derived from one shuffle index wherein successive shuffle indexes are formed using the minimal number of bits needed to span the registers in the permutation buffer up to and including the register addressed by the slot counter;
4.1.2) a shuffle register used for holding a shuffle index value;
4.1.3) a span counter, being a count-down counter for holding the number of permutation buffer registers that a shuffle index must span;
4.1.4) a first subtracter for subtracting the span counter contents from the shuffle register contents to provide a result and a borrow signal;
4.4.5) a decrementor for decrementing by one the contents of the span counter;
4.1.6) a second subtracter for subtracting the result from first subtracter from the output of the decrementor;
4.1.7) a direction source, being a shift register using the complemented output of itself as the feedback signal;
4.1.8) an index controller means for forming the transposition indexes including
4.1.8.1) means for initializing the direction source with the direction value from selector parser,
4.1.8.2) means for initializing the span counter with the number of bits to permute,
4.1.8.3) means for loading the shuffle register with the shuffle index from selector parser,
4.1.8.4) means for outputting the contents of the shuffle register as a transposition index whenever a borrow signal from the first subtracter is active,
4.1.8.5) means for outputting either the result from the first subtracter or the second subtracter as a transposition index whenever the borrow signal from the first subtracter is inactive, wherein result selection is determined in accordance with the direction source, and to pulse the shift register in the direction source, and
4.1.8.6) means for pulsing the span counter;
wherein a sequence of transposition indexes are formed.
25. A state machine keystream generator comprising:
1) a source of a key in the form of a machine index and a state variable;
2) a process intermediary-result register means including
2.1) a machine register means for storing a machine index, the machine index serving to parameterize a transition and output function of the state machine,
2.2) a state register means for storing a state variable, the state variable serving to further parameterize the transition and output function during each transition,
2.3) a dependency table means for storing pseudo random bits, filled at the start of each transition, which parameterize a state transition,
2.4) a garbage index means for storing a garbage index which specifies how a state transition is to proceed, a garbage index comprises the various fields of (i) a global dependency index, (ii) a plurality of packed function indexes, (iii) a nibble perm selector, (iv) an accumulation index, (v) a permutation selector, (vi) a state emitter index, and (vii) an output emitter index,
2.5) a function table means for storing a plurality of function values,
2.6) a sum table means for storing a plurality of sum elements,
2.7) an accumulator multiplicand register means for storing a plurality of accumulation elements; and
3) a process state transition computational means including
3.1) a random generator means for forming random numbers, in accordance with a seeding value received from the machine register means and state register means, for storage in the dependency table means,
3.2) a streaming CEM means for coarse encoder multiplication of a multiplicand and a multiplier stream specified by a starting address within the dependency table means to form a product value, the streaming CEM means including
3.2.1) a streamer means for forming a multiplier stream from a starting address which selects a bit in the dependency table means, the multiplier stream consisting of a selected bit and those bits immediately following, cyclically addressed,
3. 2.2) a parsing means for forming a plurality of position value and XOR datum bit pairs from the multiplier stream,
3.2.3) an XOR means for forming a product bit by modulo-2 addition of a XOR datum bit with a bit in the multiplicand selected by the corresponding position value, and
3.2.4) an accumulation means for concatenating the plurality of product bits to form a product value;
3.3) an unpacker means for expanding a packed function index received from the garbage index means into a function index, the expansion is in accordance with a global dependency index also received from the garbage index means with each resulting function index sent to an evaluator means;
3.4) the evaluator means for transforming a function index received from the unpacker means into a function value for storage in the function table means;
3.5) a permuting unit means for transforming function values received from the function table into sum elements for storage in the sum table, the permuting unit means including
3.5.1) an ordering means for providing a permutated ordering of the function values in accordance with a permutation selector received from the garbage index means,
3.5.2) a permuting-unit decomposition means for decomposing a nibble perm selector received from the garbage index means into a plurality of nib selectors, each nib selector corresponding to a pair of permutated function values taken consecutively,
3.5.3) a permutation means for resolving a nib selectors received from the permuting-unit decomposition means into a permutation, the permutation being applied to the nibbles of the corresponding function values pair to form a sum element;
3.6) a collecting unit means for transforming sum elements received from the sum table means into accumulation elements for storage in the accumulator multiplicand register means, the collecting unit means including
3. 6.1) a collecting-unit decomposition means for decomposing an accumulation index received from the garbage index means into a plurality of collector indexes, each collector index corresponding to a pair of sum elements, a pairing being formed with consecutive sum elements, and
3.6.2) a combining operation means for forming an accumulation element by using a collector index received from the collecting-unit decomposition means to select a combining operation, from a plurality of functions comprised of ADD and SUB and XOR and NEG, with the selected combining operation applied to the corresponding sum element pair;
4) a bus switch means for routing multiplicands to the streaming CEM means, and product values from the streaming CEM means;
5) a transition controller means for providing a keystream fragment and a next state value, the transition controller means including
5.1) a dependency initialization means for storing the random numbers from the random generator means into the dependency table means, wherein the random generator means is seeded with values received from the machine register means and state register means,
5.2) a garbage initialization means for storing the product value from the streaming CEM means into the garbage index means, wherein the starting address received by the streaming CEM means is zero and the multiplicand received by the streaming CEM means is the concatenation of the machine register means and state register means routed through the bus switch means,
5.3) a garbage parsing means for decomposing the garbage index means into its component fields,
5.4) an unpacking means for successively transmitting to the evaluator means a plurality of function indexes formed by the unpacker means,
5.5) an evaluation means for successively transmitting to the function table means a plurality of function values formed by the evaluator means,
5.6) a summation means for successively transmitting to the sum table means a plurality of sum elements formed by the permuting unit means,
5.7) a collection means for successively transmitting to the accumulator multiplicand register means a plurality of accumulation elements formed through by the collect unit means,
5.8) a next state means for storing the product value from the streaming CEM means as a next state variable into the state register means, wherein the starting address received by the streaming CEM means is the state emitter index from the garbage index means, and wherein the multiplicand received by the streaming CEM means is the contents of the accumulator multiplicand register means routed through the bus switch means, and
5.9) an output means for transmitting the product value from the streaming CEM means as a keystream fragment, wherein the starting address received by the streaming CEM means is the output emitter index from the garbage index means, and wherein the multiplicand received by the streaming CEM means is the contents of the accumulator multiplicand register means routed through the bus switch means;
wherein a state transition permits the process to continue;
wherein a plurality of keystream fragments result;
wherein a concatenation of successive keystream fragments is defined as the keystream.
26. The keystream generator according to claim 25 wherein the 3.1) random generator means comprises:
3.1.1) a source of an initialization value;
3.1.2) a multiplier with one multiplicand fixed serving as a congruential multiplier generator;
3.1.3) a seed register for providing a multiplicand to the multiplier;
3. 1.4) a parsing register for decomposing a product from the multiplier;
3.1.5) a key table for holding a plurality of values from the multiplier;
3.1.6) a selection register for addressing a bit in the key table;
3.1.7) an XOR means for performing modulo-2 addition on a bit pair;
3.1.8) a collection register, being a shift register used to form a random value by concatenating amorphous bits;
3.1.9) a random controller means for forming a fixed quantity of random outputs, the random controller means including
3.1.9.1) means for initializing the seed register with a first seed value formed by XORing together two portions of the initialization value,
3.1.9.2) means for advancing the seed register by replacing the seed register with the product from the multiplier with the seed register's content used as the other multiplicand,
3.1.9.3) means for initializing the key table with successive products from the multiplier using the first seed value;
3.1.9.4) means for resetting the selection register to address the first key table bit,
3.1.9.5) means for filling the seed register with a second seed value formed by XORing together two additional partitions of the initialization value,
3.1.9.6) means for generating a finite sequence of amorphous bits including
3.1.9.6.1) means for advancing the seed register with the multiplier's product also stored in the parsing register,
3.1.9.6.2) means for successively decomposing the parsing register into a plurality of delta value and XOR datum bit pairs,
3.1.9.6.3) means for forming an amorphous bit by using the output of the XOR means applied with an XOR datum bit received from the parsing register and a key table bit selected by the selection register,
3.1.9.6.3) means for advancing the selection register by adding to it a delta value received from the parsing register assuming that arithmetic is such that an overflow wraps to the start address in the key table
3.1.9.7) means for storing the amorphous bit in the collection register;
wherein a random value is contained in the collection register once enough amorphous bits are generated;
wherein random values are successively generated by a fixed number of amorphous bit formation operations.
27. The keystream generator according to claim 25 wherein the 3.3) unpacker means comprises:
3.3.1) a bit address register, used in forming an unpacking stream and a plurality of creature bits;
3.3.2) unpacking streamer means for forming the unpacking stream by successively incrementing the bit address register and outputting the dependency table bits selected, wherein cyclical addressing is employed;
3.3.3) an insertible shift register, being a generalized shift register with the capacity to insert a bit value at a given address by first shifting the bits at and beyond the insert point to make room for the bit value to be inserted;
3.3.4) an insert list, being a plurality of registers used to hold addresses selecting bits within the insertible shift register;
3.3.5) a dispersed descriptor, being another plurality of register pairs for holding skipper and xor datum bit pairs;
3.3.6) a dispersed count register for holding the number of valid skipper and xor datum bit pair;
3.3.7) a current pair register for selecting some pair in the dispersed descriptor;
3.3.8) an unpacking controller means for successively transforming each packed function index into a function index, the unpacking controller means including
3.3.8.1) means for loading the bit address register with the global dependency index,
3.3.8.2) means for loading the insertible shift register with a packed function index,
3.3.8.3) means for decomposing the packed function index into an insert list index composed of a plurality of position addresses used to fill the insert list,
3.3.8.4) means for decomposing the packed function index into an unpacking index used to fill the dispersed count register;
3.3.8.5) means for resetting the current pair register so it points to a first pair in dispersed descriptor;
3.3.8.6) means for forming skipper and xor datum bit pairs from consecutive unpacking stream bits with the pairs of number according to the dispersed count register stored in the dispersed descriptor;
3.3.8.7) means for forming a plurality of creature bits of same number as position addresses with a dispersed emission process, the means including
3.3.8 7.1) means for fetching the dependency table bit selected by the bit address register which is XORed with the current xor datum bit selected by the current pair register to form a creature bit,
3.3.8.7.2) means for advancing the bit address register by adding to it the value of the current skipper selected by the current pair register assuming that arithmetic is such that an overflow wraps to the start address in the dependency table,
3.3.8.7.3) means for advancing the current pair register by incrementing it once subject to bounding by the contents of the dispersed count register so that it addresses a valid pair in the dispersed descriptor; and
3.3.8.8) means for successively inserting each creature bit into the insertible shift register at the location selected by consecutive position addresses of the insert list;
wherein the residual bit address is used to form successive function indexes for a given transition stage; and
wherein upon creature bit insertion the insertible shift register contains the function index.
28. The keystream generator according to claim 25 wherein the 3.4) evaluator means comprises:
3.4.1) means for decomposing a function index into the various fields of (i) an order index, (ii) a dependency index, (iii) an operand 1 index, (iv) an operand 2 index, (v) an operand 3 index, (vi) an operation 1 index, and (vii) an operation 2 index;
3.4.2) operand maker means for transforming the three operand indexes into three operands;
3.4.3) logical operation means responsive to the operand 1 index for selecting a combining operation from a plurality of functions comprised of AND and OR and XOR and NOT, therein to combine two operands into a third;
3.4.4) arithmetic operation responsive to the operand 2 index for selecting a combining operation from a plurality of functions comprised of ADD and SUB and MUL and DIV, therein to combine two operands into a third;
3.4.5) ordering means responsive to the order index for selecting an order of the logical operation and the arithmetic operation, wherein a first operation is performed upon first and second operands followed by performing a second operation upon the third operand and a result from the first operation;
wherein the operand resulting from the second operation is defined as the function value.
29. The keystream generator according to claim 28 wherein the 3.4.2) operand maker means comprises:
3.4.2.1) operand streamer means responsive to the dependency index for selecting a bit in the dependency table with the selected bit and those bits immediately following, therein forming an operand stream from the dependency table using the dependency index to the select the starting bit;
3.4.2.2) a dispersed descriptor, being a plurality of register pairs for holding skipper and xor datum bit pairs;
3.4.2.3) a dispersed count register for holding the number of valid skipper and xor datum bit pair;
3.4.2.4) a current pair register for selecting some pair in the dispersed descriptor;
3.4.2.5) an emission pointer register for selecting a bit in the garbage index;
3.4.2.6) an operand register, being a shift register used to form an operand by concatenating emission bits;
3.4.2.7) an operand controller means for successively transforming each operand index into an operand, the operand controller means including
3.4.2.7.1) means for decomposing an operand index into an extraction index used to fill the dispersed count register, and a source index used to initialize the emission pointer register;
3.4.2.7.2) means for resetting the current pair register so it points to the first pair;
3.4.2.7.3) means for forming skipper and xor datum bit pairs from consecutive operand stream bits with the pairs of number according to the dispersed count register stored in the dispersed descriptor;
3.4.2.7.4) means for forming an emission bit including
3.4.2.7.4.1) means for fetching the garbage index bit selected by the emission pointer register which is XORed with the current xor datum bit selected by the current pair register to form an emission bit,
3.4.2.7.4.2) means for advancing the emission pointer register by adding to it the value of the current skipper selected by the current pair register assuming that arithmetic is such that an overflow wraps to the start address in the garbage index, and
3.4.2.7.4.3) means for advancing the current pair register by incrementing it once subject to bounding by the contents of the dispersed count register so that it addresses a valid pair in the dispersed descriptor;
3.4.2.7.5) means for storing the emission bit in the operand register;
wherein an operand is contained in the operand register once enough emission bits are generated;
wherein the three operands are successively generated using the operand stream continuously.
30. A state machine for generating an extended-length cryptographic key by non-linear processes, the machine comprising:
1) a state transition means for transforming a state variable into an keystream fragment and a next state variable in accordance with a directive called a machine index, the state transition means including
1.1) a dependency formation means for generating a plurality of random bits from the machine index and state variable, the dependency bits serving as dependent parameters for subsequent operations;
1.2) a garbage index formation means for deriving from the machine index, state variable, and dependency bits a garbage index;
1.3) a parsing means for decomposing the garbage index into a plurality of fields which provide for a transition function and an output function;
1.4) a field expansion means for exploding certain fields;
1.5) evaluation means, interpreting the fields of the transition and output functions as directives, for forming operands and selectively performing operations thereon, the selected operations on the formed operands producing intermediary results which are used as operands for additional operations to be selected with additional fields, this evaluation process terminating after a predetermined number of levels into a final result;
wherein a state transition permits the process to continue;
wherein a plurality of keystream fragments result;
wherein a concatenation of successive keystream fragments is defined as the keystream.
31. The machine according to claim 30 wherein the 1.1) dependency formation means comprises:
1.1.1) a dispersed amorphous process using the output of congruential multiplier random generators as input.
32. The machine according to claim 30 wherein the 1.2) garbage index formation means comprises:
1.2.1) a streaming CEM.
33. The machine according to claim 30 wherein the field expansion means operates to explode certain fields by injecting dependency bits into the fields at points selected by a dispersed emission stream of dependency bits.
Description
RELATION TO THE RELATED PATENT APPLICATIONS
The present patent application is related to U.S. patent application Ser. No. 07/388,331, now abandoned, filed Aug. 1, 1989 for an ELECTROMAGNETIC TO PHYSICAL LOCK to the selfsame inventor of the present application. The contents of the related patent application are incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally concerns cryptology and cryptographic machines, and particularly concerns machines for generating cryptographic keys of indeterminately long length.
2. Description of the Prior Art
2.1 Background to the Present Invention in a Nutshell
The art of secret writing is very ancient, and many different systems have been used throughout history. One of the oldest known ciphers is the Spartan scytale: a transposition cipher based on winding a narrow ribbon of parchment spirally around a cylindrical staff with the message then written on the parchment. The early Greeks used substitution of numerals for letters in some of their systems, while the Romans favored the substitution of one letter for another in the form of the Caesar cipher.
While transposition ciphers seem to have disappeared from use until relatively recently, substitution ciphers continued to evolve in many different ways. With the invention of the printing press, many types of "book ciphers" were devised wherein some book was chosen as the key for the substitutions. Of course, the entire book could be viewed as one long key; thus was born the running key cipher. The running key cipher can be improved dramatically by using a book of random letters, i.e. an incoherent key.
These ideas finally crystallized in the Vernam cipher where a message is bitwise XORed with a random key. Army cryptologist Major Joseph Mauborgne then suggested that the key be used only once, and thus was born the mother of all secret key ciphers, the one-time pad. Subsequently, both William Friedman and Mauborgne arrived at the conclusion that a secure system can be achieved only if an incoherent key is used whose length is at least as long as the message. The theoretical foundation was then laid by C.E. Shannon with the idea of equivocation to provide perfect secrecy. The bad news was that perfection requires a key as long as the message.
The generation, distribution, and storage problems associated with the one-time pad has heretofore made this system impractical for most applications, so the development of small key systems continued. One development was that of block ciphers following Shannon's suggestion of using a "mixing transformation" implemented by applying several rounds of transpositions and substitutions to "diffuse" and "confuse" the statistics of the message.
Another development was the keystream ciphers based on pseudo random number generators. There was temporary interest in using linear shift registers as random number generators until they were proved to be insecure.
The degree of non-linearity required to make small key cipher systems cryptographically secure is currently an open question. A recent approach to the generation of random numbers for purposes of cryptography is to exploit some mathematically intractable problem from number theory in order to gain cryptographic security, and considerable progress has been made with respect to the efficiency of certain methods of random number generation. However, until complexity theory can show decisively that these mathematical problems on which the number generators are based are indeed intractable, a certain wariness will remain.
The present invention will be seen to be concerned with the generation of large, very-large, and indefinitely-large cryptographic keys as suit large key cryptographic systems including, notably but not by way of limitation, the one time pad. The way by which these large cryptographic keys are derived will be seen to be analogous to cryptographic processes themselves.
One analogous class of ciphers that are of special interest to the present invention is the transposition block cipher. The transposition block cipher is performable by pencil and paper, as well as by faster means such as computers. In a transposition block cipher a message is decomposed by letters into fixed length sequences with these sequences consecutively used as the rows in a N.times.M matrix block. A cryptogram is formed by taking the letters from, say, the 3rd column starting from the top, followed by, say, the letters in the 2nd column starting from the bottom, and so on, with this path taken being the key. Many different "flavors" of columnar transposition ciphers were devised, including the so-called ADFGVX system once used by the German Army. The ADFGVX system also utilized substitution.
In order to reach the present invention, it will be seen that (i) the technologically obsolete notion of a small key is discarded, and then (ii) the same ingenuity that Gilbert Vernam used is applied. Namely, or in other words, it will be seen that the present invention calls for the application of a bitwise transposition to a large incoherent key to generate a keystream (subsequently usable for diverse cryptographic processes in the encryption/decryption of data). The bitwise transposition will be seen to include (i) substitution through selected XORings of the "columns", and/or (ii) annihilation through skipping some of the "rows" in each "column", and/or (iii) a method of multiplexing the columns. Finally, as still another essential idea of the present invention, it will be seen that this bitwise transposition is "amorphous", meaning that, complex as the transposition may be in its substitutions and/or annihilations and/or mutiplexing, it is (normally) repetitively recursively performed each time in a different way.
Cryptoanalysis of the amorphous transposition processes gives rise to a mechanical correlation problem. The intractable nature of this problem appears likely to be provable. Even if no proof of the cryptographic security of one or more of the amorphous transposition processes of the present invention is forthcoming, the apparent intractability of these amorphous processes are arguably more attractive than any competing cryptology systems having a supposed intractability of cryptoanalysis based on number theory because the latter systems have an undesirable profundity inherent in their fundamental objects such as the factoring problem. This profundity is continually being revealed as further mathematical research finds new structures which provide means for realizing better algorithms to these problems.
The bitwise transposition processes in accordance with the present invention, on the other hand, will be seen to be, quite intuitively, shapeless--hence the description "amorphous". The mathematical function(s) defined by such an amorphous process(es) will be seen to be so random that the prospects of finding any deep, analyzable, structures in the general amorphous method(s) of the present invention appears to be quite remote.
2.2 Particular Prior Art Cryptography Relevant to the Present Invention
The present invention does not directly concern the encryption or decryption of data. Instead, it concerns the generation of generally long cryptographic keys that are usable by diverse cryptographic processes, including the one time pad.
However, the present invention will be seen to call for the manipulation of a cryptographic key in a like manner, and by like processes, that former cryptographic methods and systems were wont to manipulate (e.g., encrypt or decrypt) data. Since they key manipulation methods of the present invention are (deemed by the Applicant to be) well considered as regards their preservation (and, indeed, even their inducement) of randomness, and amorphousness, in the data sets (i.e., the seed keys) to which they are applied, it will be no surprise that these manipulation methods have a certain correspondence with, and antecedents within, the known methods of cryptography. In some cases the preferred methods, and machines, of the present invention will be seen to constitute variations--arguably even improvements--to certain prior art cryptographic methods of the order of amorphous transforms. Accordingly, understanding certain particular ones of these prior art cryptographic methods will prove useful to placing the present invention in context.
2.3 It is Known to Use of the XOR Function in Cryptography
The present invention will be seen to perform the exclusive or, or XOR, function on the bits of a set. The basic idea of using an incoherent keystream to perform the XOR function on a message dates to the Vernam cipher of 1918.
2.4 Certain Types of Random Permutations Are Known to be Used in Cryptography
The present invention will also be seen to teach the manipulation of the bits of a set by (essentially) random permutations. The use of random permutations in encoding is known. Permutations have been used in voice scrambling systems in both the time and frequency domains. F. Ayoub appears, in his article "Encryption with keyed random permutations", Electronic Letters, Vol 17, 1981, pages 583-585, to have been first to suggest using random permutations for digital data. Ayoub applied an optimal permutation algorithm to minimize the key bits required. Ayoub notes that this method would be useful in substitution-permutation (SP)-type encryption systems.
Ayoub shows, at least implicitly, one part of what Applicant will call a "contracting amorphous process", although Ayoub appears to have only understood permutations in the sense of using such during the encoding of data. Ayoub does not seem to view his permutations as amorphous contraction, i.e. to make the observation that if a pseudo random sequence of bits representing a key is contracted via permutations then the resulting "cipher text" is really a new, secure, key.
Applicant will also be seen to teach the use of a permutation called an "expanding amorphous process". At least some particular forms of expanding amorphous processes are known, as would be expected because of the simplicity of these forms. One early type of an expanding amorphous process is a class of transposition ciphers in which the message is written in matrix form (letter by letter) with the cryptogram formed by taking some path through the matrix to define the letters of the cryptogram. The path taken together with the dimensions of the matrix comprise the cryptographic key of these systems. Other shapes besides rectangles, e.g. triangles, were also used, as well as blocking out certain squares in the template (the irregular columnar cipher). These ciphers were originally performed with pencil and paper so the paths were fairly simple. In one common version, the path went column by column, with the columns permutated, with the letters from the individual columns taken starting from the top, or starting from the bottom, or starting from the top and bottom alternately.
These columnar ciphers will be seen to be similar to the generalized expanding amorphous processes of the present invention. However, the present invention will be seen not only to extend the application of expanding amorphous processes (i.e., to keys as opposed to data), but to add some new "twists". The present invention will be seen to teach each of (i) permuting a matrix of random bits in a feedback mode, (ii) logically complementing some bits and then multiplexing the "columns" via a holdback scheme, and (iii) an amorphous process called "dispersed partitioning".
2.5 State Machines Are Known to be Used in Cryptography
Still furthermore, the present invention will be seen to employ, in one of its embodiments, a state machine. Use of at least some parts of a state machine in keystream generation is known. Specifically, the idea of using a machine index to select a function is discussed in C.E. Shannon's paper "Communication Theory of Secrecy Systems", Bell System Technical Journal, Vol. 28, 1949, pages 656-715. Shannon analyzed ways to combine cipher systems, one basic way being to form a weighted sum consisting of a plurality of different encoding transformations with each transformation assigned a probability of being chosen for use to encode a particular message. From a conceptual standpoint, Applicant's state machine method could be interpreted as a weighted sum of random number generators with a machine index (to be explained in this specification) selecting a function (to be explained). However, Applicant's "function" will be seen to be dynamically redefined at each transition: since the state variables are also used to define this function. Furthermore, Applicant's approach in generating a "garbage index" in order to define a state transition function will deserve careful consideration when later discussed.
As an aside, it may be understood that Shannon's paper is chiefly of theoretical interest dealing in entropy and equivocation. In the course of presenting his theory Shannon did point out some things which could be applied to build a secrecy system, but his paper did not really present any new systems, and to this extent does not relate to Applicant's invention. However, one interesting point that Shannon made was that even a very simple encryption system could be used if the message was first transformed to eliminate all of its redundancies. Unfortunately, such a transformation is in practice extremely difficult, if not impossible, because of the complexity inherent in natural languages.
2.6 Certain Types of Random Number Generators Are Known to be Used in Cryptography
Applicant's method and machine performs random number generation. There are several prominent approaches to random number generation (to form a keystream) that have been taken over the years that are worth mentioning. Linear shift registers have been thoroughly researched. Simple designs exist which have proven "good statistics" and very long cycle lengths. However these sequences are predicable: a small portion yields the whole sequence through a fairly simple process of inverting a matrix formed from this "intercepted" portion. The use of non-linear feedback for shift registers complicates the situation, but the security of such systems is somewhat dubious.
Shannon suggests employing a "mixing transformation" to "diffuse and confuse" the statistics of a message. Applicant's (encryption) of messages (at least directly), but rather of keys. However, Applicant's invention will perform something that could, at least broadly and generically, be called a "mixing transformation". Since most any modern digital circuitry can "throw" a lot a bits around, thereby performing the "mixing" with great vigor, it is useful to understand just how poorly "mixing transformations" have been implemented in the past in order to better assess whether the particular "mixing transformations" taught by Applicant within this specification (even though applied to keys) have cryptographic merit.
European patent number 0035048 shows, in some sense, an early non-linear shift register system. The system is an odd hybrid, comprised of block cipher type "non-affine transformations" in the form of "S" boxes (i.e. substitution tables), strangely, feedback from the message which is used to transform the key matrix. It's inventor, IBM's Horst Feistel, had in 1973 developed a well known block cipher named, of all things, LUCIFER. The banality of LUCIFER soon became apparent with this system duly broken. But its basic structure has been retained, and in fact, this structure was originally due to Shannon's suggestion of employing a "mixing transformation" to "diffuse and confuse" the statistics of a message.
Continuing with the block cipher approach to a "mixing transformation" to "diffuse and confuse", IBM was the main force behind the development of circuits (chips) to perform block ciphers. IBM waived its many patent claims for the particular block cipher derivative later called the "Data Encryption Standard", or DES. DES became the world's first encryption standard around 1978, recently losing its certification in 1986.
Linear congruential generators are another recent development. A proper choice of parameters for the equation x.sub.i +1=(a*x.sub.i +b) mod N yields good random number generators. The Applicant chose this generator as a reasonable "seeding source" as will be seen. However, the numbers produced are not secure. Reference A.M. Frieze, R. Kannan, and J.C. Lagarias, "Linear Congruential Generators do not produce Random Sequences", 25th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Oct. 24-26, 1984, pages 480-484.
However, linear congruential generators can be parameterized to produce random numbers. If a non-linear component is used, a secure sequence results. Here the equation takes the form x.sub.2 mod N (where N is the product of two distinct primes each congruent to 3 mod 4, and x.sub.0 is the quadratic residue mod N) and this is used to generate the sequence x.sub.0, x.sub.1, x.sub.2, . . . from which the bit sequence b.sub.0, b.sub.1, b.sub.2, . . . where b.sub.i =parity(x.sub.i) is formed. Messrs. L. Blum, M. Blum, and M. Shub show in their paper "A Simple Secure Pseudo-Random Number Generator", SIAM Journal of Computing, 1986, pages 364-383 (the main result goes back to about 1982, but many years passed before their paper was published) that the b.sub.i 's are secure.
While Blum's generator (1982) is simple enough, it is rather inefficient since only one bit is emitted for each modular multiplication (n.sup.2 steps) where n is the number of bits in N, typically around several hundred bits. Blum's open question of whether more than a single bit could be securely emitted was answered by the Umesh V. Vazirani and Vijay V. Vazirani in "Efficient and Secure Pseudo-Random Number Generation", 25th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Oct. 24-26, 1984, pages 458-463. The Vazirani's found a way to emit log n bits per multiplication, and their basic proof can be extended to (log n).sub.2 efficiency.
Then, in 1988, Micali and Schnorr came up with a system based on the expression x.sup.d mod N, with their system about as efficient as the simple linear congruential generators. Reference S. Micali and C.P. Schnorr, "Efficient, Perfect Random Number Generators", Lecture Notes in Computer Science, Vol. 403, Advances in Cryptology: Proceedings of CRYPTO 88, Springer-Verlag, 1989, pages 173-198. The "proofs" for the security of these generators are based on certain complexity assumptions. Consequently, if tomorrow a good algorithm for factoring is found, the security of these systems will be invalidated. The continuing research seems to indicate that the present assumptions are pretty good, with the evidence mounting in favor of the security of these systems, but a proof as such has remained elusive and may never be found.
Implementing Micali-Schnorr's generator with a modulus of 224 bits yields 96 bits per multiplication. This about matches the efficiency of an contracting amorphous process using a 128-bit frame feed by using the upper 16-bits of a 32-bit linear congruential generator. The Micali-Schnorr system is probably readily scalable for trade-offs between security and efficiency, and so may thus be superior to Applicant's system--not to mention that Applicant's random number generator is only conjectured to be random.
Yet another idea pertaining to random number generation is that of composite generators in which the outputs of several generators are added together, say, to form a secure keystream. Statistically this appears to be a good idea, although composite generators have not been cryptoanalyzed to Applicant's knowledge. Reference M. Brown and H. Solomon, "On combining pseudorandom number generators", Ann. Statistics, Vol. 7, 1979, pages 691-695. Linear shift registers have also multiplexed together in various ways to form composites, e.g. with one generator used to select the output bit from another generator.
In 1973, the linear shift register generator using characteristic function x.sup.607 +x.sup.334 +1 was shown to have "equidistribution and multidimensional uniformity properties vastly in excess of anything that has yet been shown for conventional congruentially generated sequences". Reference J.P.R Tootill and W.D. Robinson and D.J.Eagle, "An asymptotically random Tausworth Sequence", Journal of the Association for Computing Machinery, Vol. 20, 1973, pages 469-481. This generator has an astronomic period of 2.sup.607 -1. The output is extracted from the full bitstream 23 bits at a time, and then skipping 489 bits, then repeating. The upshot of this is what Applicant calls "contraction", and goes back to 1965 when Tausworth first used a LSR as a generator. Although such jettisoning of bits does falls under the broad category of contraction, a more narrow view of contraction, in particular what the Applicant calls "amorphous contraction", requires an "amorphous" processing which reduces a set of bits to a smaller set in an often simple, but functional, manner.
The keystreams delivered by Applicant's invention will be seen to suitably be used as secret encryption keys, and are thus unsuitable for public key encryption. As an aside, it may be noted for the sake of completeness that public key encryption is a relatively new idea originating with Diffie and Hellman. Reference W. Diffie and M.E. Hellman, "New directions in cryptography", IEEE Trans. Information Theory, IT-22, Vol. 6, Nov. 1976, pages 644-654. Public key encryption is based on asymmetric algorithms. The idea is this. The receiver generates a random number which is then transformed into two keys: a public key and a private key. The public key is insecurely transmitted to the sender. The sender encodes the message with the public key and then insecurely transmits the cryptogram to the receiver. The receiver decodes the cryptogram using the private key. This system is practical provided that a) the problem of decoding the cryptogram with the public key is cryptographically intractable, b) deriving the private key from the public key is cryptographically intractable, c) the generation of the public and private keys is simple, d) encoding with the public key is simple, and e) decoding with the private key is simple.
The only practical public key system that has survived scrutiny is the patented RSA system invented by Rivest, Shamir, and Adleman in 1978. Reference R. Rivest, A. Shamir and L. Adleman, "A method of obtaining digital signatures and public-key cryptosystems", CACM, Vol. 21, No. 2, Feb. 1978, pages 120-128. The encryption formula is C=E(Ks, M)=M.sup.Ks mod N. (The Micali-Schnorr random number generator is a RSA system.) Note that the security of even the DES is suspect. Reference John C. Dvorak, "Inside Track", PC Magazine, Vol. 11, No. 5, Mar. 17, 1992, page 95. Reference also BYTE magazine, May 1993, Vol. 18, No. 6 at page 130.
The Applicant, at various points, employs a permutator to resolve a "permutation selector" into a sequence of permuted indexes. The basic algorithm used follows one due to Moses and Oakford (reference L.E. Moses and R.V. Oakford, "Tables of Random Permutations", Stanford University Press, 1963) and to R. Durstenfeld (reference R. Durstenfeld, 1964, CACM, Vol 7, page 420). The method cited requires one multiplication per permuted index generated. A variant method based on division is reported by Knuth in his series "The Art of Computer Programming", specifically in "Volume 2: Seminumerical Algorithms", Addison-Wesley, second edition, 1981. This later method requires fewer bits in the permutation selector. An optimum permutation algorithm with respect to permutation selector size may be found in S. Even, "Algorithmic Combinatorics", Macmillan, 1973. Minimal selector size results when only the 1's bits of the data are "permutated" by considering only the combinations thereof, at the cost of increased computational complexity.
As a compromise between complexity and selector size, the Applicant has devised a new method based on "hashed division" which generates nearly uniform permutations with only a slightly larger permutation selector than the "division" method, while eliminating the need for multiplication and division.
SUMMARY OF THE INVENTION
The present invention contemplates the machine generation of cryptographic keys by non-linear, combinatorial, processes similar to processes that are normally associated with encryption of data.
1. The Utility of Amorphous Processes for Keystream Generation
The present invention deals with combinations of, and combinatorial processes performed on, the bits of a "seed" cryptographic key in order to produce a new, often larger and permissively much, much larger, cryptographic key, or "keystream", that is typically as, or more, cryptographically secure than is the "seed" cryptographic key itself. The combinatorial processes are typically recursive, and may typically be used to produce cryptographic keystreams of any desired length. The typically long output cryptographic key, or keystream, is usefully used to encrypt plain text, or to decrypt cipher text, data by any number of conventional cryptographic processes, including by a one time pad.
The combinatorial processes of the present invention are described as "amorphous", meaning that they are not the same from time to time, and over time. The amorphous processes, should the one in use at any particular instance not be known to a code breaker, present a great practical difficulty to a cryptoanalyst in discerning either (i) the "seed" key, or (ii) the amorphous process(es) operating thereon, from the output keystream. Of course, the output keystream is intended to be secret, and unavailable to the cryptoanalyst who typically has only cipher text data.
Accordingly, the strength of the present invention is that when a cryptographic "seed" key is itself "encrypted", and is the used to encrypt data, then (i) the problem of cryptoanalysis is magnified simultaneously that (ii) the utility of the key is enhanced. The cryptographic "seed" key must be so "encrypted" without destroying its functional utility as a cryptographic key. It is so "encrypted" by the combinatorial methods of the present invention. The utility of the key is enhanced because the combinatorial methods normally magnify the length, and thus the attendant utility, of the key.
2. The Nature of Amorphous Processes for Keystream Generation
The present invention deals with combinations. Specifically, the invention deals with taking a subset of bits from a set of (generally, substantially) random bits in some order. This combinatorial process is generalized to include subsets which contain multiple instances of bits from the set. The generalized combinatorial process, is called an "amorphous process"; the subset of bits produced by the amorphous process is called an "amorphous partition." Amorphous partitions also (generally) include logical complementing of selected bits. The term "amorphous partition index" (or "partition index" for short) refers to a particular partition given (i) a set and (ii) some partitioning scheme. The term "amorphous stream" refers to the subset output through a partition.
In order to illustrate these concepts, consider a set of 64 KB of random data, i.e. 524,288 random bits. Call this set a "seed", or "base" key. Base key partitioning, the "amorphous process" of the present invention, fall into three classes: expansion, equivocation, and contraction.
For expansion, the partition index has fewer bits than the amorphous stream. Say, for example, that the partitioning scheme is such that partition indexes are 3 KB and the subsets selected are 60 KB. Given an initial partition index (PI0), a 60 KB subset can thus be generated. The first 57 KB of this subset (amorphous stream) is output as a keystream component (KS1) with the remaining 3 KB used as the next partition index (PI1). Thus feedback yields the series KS1, KS2, . . . which is defined as the keystream (KS).
For equivocation (loosely defined), the partition index is the same size as the amorphous stream. This critical case will produce no output (i.e. NULL={KS1, KS2, . . .}) and thus is not a practical system in a feedback configuration.
For contraction, the partition index is larger than the amorphous stream. Amorphous contraction can be made practical by using an insecure keystream of sufficient length used as a sequence of partition indexes or possibly as a sequence of base keys also. E.g., the bitstream output of a linear congruential generator may be separated into a series of base keys and partition indexes. A process will also be called "contractive" if base key and partition index pairs are employed wherein the amorphous stream from each pair is smaller than the input, i.e. the base key and partition index pair input to the process. The conjecture of the present invention--supported by statistical tests--is that resulting "contracted randoms" output will be cryptographically secure.
To complete the description of the amorphous process, some base key bit order selection (the path) must be specified. Further, a XORing (substitution) component must also be described. The DESCRIPTION OF THE PREFERRED EMBODIMENTS section of this specification contains the details for several methods of path and substitution control, and the preferred structure of a keystream generators for implementing such path and substitution control.
3. Summary Descriptions of Expanding, and Contracting, Amorphous Process Keystream Generators of the Present Invention
The present invention is embodied in a digital electronic machine for generating a cryptographic key by processes similar to those normally associated with encryption of plain text data. The machine includes 1) a base key source for providing a set of essentially random bits defined as a base cryptographic key, 2) a partition index source for providing an essentially random number called an amorphous partition index; and 3) an amorphous processor receiving the base key from the base key source means and the amorphous partition index from the random number source.
The 3) amorphous processor act to perform on the base key a generalized combination with substitutions in accordance with use of the amorphous partition index as a directive in order to produce another essentially random set of bits called an amorphous bitstream. In order to do so, the 3) amorphous processor includes 3.1) a selector for selecting from the base key in accordance with the amorphous partition index a selected set of bits, 3.2) a sequencer for sequentially ordering the selected set of bits in accordance with the amorphous partition index to produce an ordered selected set of bits, and 3.3) a logical complimenter for logically complementing the ordered selected set of bits in accordance with the amorphous partition index to produce a logically-complemented ordered selected set of bits called an amorphous bitstream.
By these elements, and these functions, a generalized combination with substitutions is performed on the base cryptographic key in accordance with the amorphous partition index. More particularly, the generalized combination with substitutions performed on the base cryptographic key--which base key is itself an essentially random set of bits--in accordance with the amorphous partition index--which partition index is itself an essentially random number--by the amorphous processor constitutes a process fairly describable as amorphous. This is exactly why the amorphous processor is called such, and is likewise why the set of bits produced by the amorphous processor is called an amorphous bitstream.
Clearly the amorphous process by which the base cryptographic key is used to produce the amorphous bitstream is, because it is a generalized combination with substitutions, itself in the nature of a cryptographic transform.
The amorphously-produced amorphous bitstream is usable as a cryptographic key likewise as is the base cryptographic key from which it is derived.
Notably, no order has been imparted to the cryptographic keystream by the amorphous transformation thereof. This is very useful--long keystreams may be generated from short, "seed", keys without imparting order during the process of keystream generation.
In greater detail, the 3.1) selector of the 3) amorphous processor of the machine permissibly selects from the base key, in accordance with the amorphous partition index, a subset of bits that includes multiple instances of bits of the base key set. The selected set permissively contains more bits than are within the base key.
Further in accordance with the present invention, a cryptograph (an "encryption means") may use the amorphous bitstream produced by the amorphous processor as a cryptographic key in a cryptographic transform.
The machine of the present invention generating an extended-length cryptographic key permissively still further includes 4) a feedback circuit, receiving the amorphous bitstream from the amorphous processor, for mapping the received amorphous bitstream into (i) a new amorphous partition index and (ii) a keystream portion, and for feeding back the new amorphous partition index to the amorphous processor for use therein and thereby; and 5) a recursive control means for repetitively cyclically exercising the amorphous processor and the feedback means so that, over a plurality of cycles, a plurality of amorphous bitstreams are produced by the amorphous processor and a plurality of keystream portions are produced by the feedback means. By these elements, and this operation, the amorphous processor recursively performs on the base key successive generalized combinations with substitutions in accordance with successive amorphous partition indices in order to produce a plurality of successive amorphous keystream portions. This plurality of successive amorphous keystream portions constitute, in aggregate, the extended-length cryptographic key.
Notably, this recursive amorphous process by which the base cryptographic key is used, in successive cycles, to produce the extended-length cryptographic key is, because it is still a generalized combination with substitutions, still itself in the nature of a cryptographic transform.
In still greater detail, the 4) amorphous processor typically includes a mapping circuit which expands a received amorphous partition index into an amorphous bitstream of a greater number of bits than are within the amorphous partition index. A feedback of the new amorphous partition index thus leaves one or more bits for the keystream portion. Because the amorphous process produces a number of bits beyond the partition index size, the amorphous process is called an expansion process and the amorphous processor is called an expanding amorphous processor.
The machine of the present invention generating an extended-length cryptographic key permissively still further includes 6) a random number source for providing a supply of essentially random numbers and 7) a cycle control means for repetitively exercising the amorphous processor and the random number source so that, over a plurality of cycles, a plurality of amorphous bitstreams are produced by the amorphous processor. The random number source provides for a new amorphous partition index for each cycle, or in addition, the random number source provides for a new base key for each cycle as well. The entire amorphous bitstream is used as a keystream portion; the plurality of successive amorphous keystream portions constituting, in aggregate, the extended-length cryptographic key.
In this embodiment of the machine in accordance with the present invention using the 6) random number source, the amorphous processor includes a mapping circuit which contracts a received amorphous partition index into an amorphous bitstream of fewer bits than the amorphous partition index. Accordingly, a source of amorphous partition indexes is necessary to produce a keystream. Moreover, because the amorphous process produces a number of bits fewer than the partition index size, the amorphous process is called a contracting process and the amorphous processor is called an contracting amorphous processor.
Of great importance, the 6) random number source may be based on a cryptographically insecure random number generator! The cryptographic security of the plurality of amorphous bitstreams, and of the cryptographic key, generated by the machine is achieved by the contraction process, and not by the "randomness" of the numbers generated by the random number generator!
A preferred random number source is an expanding amorphous processor in a feedback configuration. In this case the cryptographic security of the plurality of amorphous bitstreams, and of the cryptographic key, generated by the machine is achieved by the contraction process. Moreover, because the expanding amorphous processor of the random number source expands while the mapping means of the amorphous processor--which amorphous processor uses the random number as a new amorphous partition index and a new base key for each cycle--contracts, the entire process is called an amorphous teeter-totter process.
4. In Accordance with the Present Invention, Keystreams Can Also be Generated by the Method, and Apparatus, of a "State Machine"
The present invention further contemplates the keystream generation method, and apparatus, of a "state machine". The term "state machine" is used somewhat liberally here. Normally, a desired set of state transitions are first specified and are then transformed into a state machine. However, the opposite is done in the "state machine" of the present invention. In the present invention a "state machine" is specified in which the resulting state transitions are desired to be the series S1, S2, S3, . . . until the machine begins repeating. In other words, the state machine method, and state machine, is simply a random number generator with an output series O1, O2, O3, used as the keystream.
Again, the idea of a "state machine" is to form a "function index" from the "state variable" and "machine index". This function index then is interpreted in a particular way to yield (i) a transition function and (ii) an output function. The state machine method can be viewed as an analog to the amorphous process described in preceding section 1. by interpreting the function index as the partition index, and viewing the transition and output mapping as an analog to the partitioning scheme.
In preferred operation, the state machine method takes as a key two values, a "machine index" and a "state variable". From these it amorphously forms a value called the "garbage index". This garbage index is decomposed into a plurality of fields which define, through a fairly involved process, a "transition function" and an "output function". The process includes the amorphous generation of operands which are then manipulated in a plurality of operations selected via the garbage index.
The "amorphousness" of the state machine, and the state machine method, lies in that operands and operations are selected via an expansion of the machine index and state variable wherein the expansion is intrinsically without form, and amorphous.
The conjectured cryptographic security of the state machine of the present invention results from the amorphous selection of both (i) the operands and (ii) the operations applied to the operands. It is respectfully suggested that this dual amorphism is a fairly powerful idea, and that it is likely to be exceedingly difficult for a cryptoanalyst to re-evolve the (i) key and/or (ii) the state machine from just the output keystream. Moreover, it should always be remembered that the output keystream itself is normally kept secret, and used to encrypt or decrypt data.
5. The State Machine In Accordance With the Present Invention Embodies At Least Two Ideas Promoting the Cryptographic Security of the Generated Key
As introduced in section 4, above, the basic idea of the state machine method is to form the so-called "garbage index". The garbage index plays an analogous role to that of the partition index in the amorphous expansion and contraction methods briefly described in section 1. above. However, instead of defining an amorphous stream through a partition, a garbage index defines a next state variable and an output value (i.e. a keystream fragment) through a two functions: an output function and transition function.
The partition index specifies a function which selects bits from the base key. Analogously, the garbage index specifies a function (actually two) which selects bits from the machine index and state variable, although this is not a direct selection: a transformation is a more accurate description.
A first idea expressed in the preferred embodiment of method, and the state machine, of the present invention is to interpret the so-called "garbage index" as a collection of fields. Some fields specify operands, others specify operations, still others specify the order of operations and operands, still others specify the expansion of fields, and/or still others do all sorts of strange things. Some of the strange things possible are described in the DESCRIPTION OF THE PREFERRED EMBODIMENTS section of this specification.
Once operands are formed and operations selected, the results from these operations provide values which can be treated as additional operands. Further fields from the garbage index can now provide more "operation indexes" to further transform the result operands. Many levels of operations can be performed before a final result is obtained. The total of such intermediary operations defines an output or transition function, though these functions could share some, or most (as in the preferred embodiment) of the intermediary operations.
Another, second, major idea expressed in the preferred embodiment of the method, and the state machine, of the present invention is the use of dependency bits. These dependency bits serve provide a pool of random bits used in such things as field expansion or operand formation. A dependency table could be generated by an amorphous process using the machine index and state variable directly as a base key and partition index. However, this requires that the state variable and particularly the machine index be random values; an undesirable constraint necessary for generation of a fairly random dependency table. To circumvent this problem, the preferred embodiment uses the machine index and state variable to form seed(s) for use in a conventional random generator(s) such as a congruential multiplier. The random output is then amorphously compressed to form a dependency table which is not only random regardless of the input, but also securely derived.
6. Summary Description of a State Machine Keystream Generator in Accordance With the Present Invention
In accordance with still another embodiment of the present invention, a state machine serves to generate an extended-length cryptographic key by non-linear processes that are normally associated with encryption of plain text data. The state machine operates to transform a state variable into an keystream fragment and a next state variable in accordance with a directive called a machine index.
A preferred embodiment of the state machine includes a dependency formation circuit for generating a plurality of random bits from the machine index and state variable. These dependency bits serve as dependent parameters for subsequent operations. The dependency formation circuit consists of, for example, a congruential multiplier random generator.
Further included is a garbage index formation circuit for deriving from the machine index, the state variable, and the dependency bits a garbage index. The garbage index formation circuit may consists, for example, a streaming CEM.
A parsing means decomposes the garbage index into a plurality of fields which provide for a transition function and an output function.
A field expansion means explodes certain fields. The field expansion circuit may so operate, for example, by injecting dependency bits into the fields at points selected by a dispersed emission stream of dependency bits.
An evaluation means interprets the fields of the transition function and output function as directives so as to perform selected operations on selected operands. The selected operations on the formed operands producing intermediary results which are used as operands for still additional operations that are selected with additional fields. The evaluation process terminates after a predetermined number of levels, producing a final result.
A state transition permits the process to continue.
A plurality of keystream fragments result.
A concatenation of successive keystream fragments is defined as the keystream.
7. Summary Statement of Merit of the Present Invention
The expanding amorphous process of the present invention is functionally and computationally simple. The amorphous processes of the present invention may be dramatically contrasted with the conventional wisdom of "small key" systems which attempt to get the most "mileage" possible out of a small key. The existing small key paradigm holds that larger key systems should be formed by combining the analyzed components of small key processes.
The expanding amorphous process of the present invention is almost the complete opposite to prior cryptographic key generation and key management systems. The present invention starts with a large key and then uses the simplest possible, almost trivial, operations to form a secure keystream. Instead of optimizing the "miles per gallon" of a small key, the expanding amorphous process of the present invention taps into a virtually infinite supply of possibilities and "inefficiently" converts these possibilities into the reality of a keystream--a keystream that is effectively distinct from the large key from which it was derived!
From an analytic, and also a philosophic, viewpoint, the expanding amorphous process of the present invention is arguably quite appealing: it exploits the infinite via the simple. The method's merit results from avoiding the "complexity" which historically has proven to be, all too often, less than effective.
The difference between the approach of the present invention and prior approaches to cryptology boils down to the use of, and the reliance upon, a complexity which is disperse versus a complexity which is dense. The merit of the disperse complexity of the present invention is in its clarity. Contrast the dense complexity of prior art small key systems: which complexity is problematic in that the complexity of such systems may be illusionary.
The expanding amorphous process of the present invention is, with all its disperse complexity (which is actually its simplicity), arguably more attractive then prior art small key systems based on dense complexity in that a sufficiently complete analysis of the cryptographic security of the process of the present invention is not only possible, it is highly believable that such an analysis is indeed thorough! As previously explained in the BACKGROUND OF THE INVENTION section, the cryptographic security of small key (dense complexity) systems depends strongly on the intractability of obtaining any reverse solution to the mathematical algorithm upon which the key generation is based.
While the expanding amorphous process of the present invention has the drawback of having a large storage requirement for keys, this liability can be mitigated significantly by expanding a small seed key into the much larger base key only when needed. Furthermore, an expanding amorphous processor in accordance with the present invention--although simple and straightforward in the data manipulations that it performs--is generally larger, and requires more silicon real estate, than would, for example, a Data Encryption Standard (DES) chip. Again, this is not a prohibitive factor considering that the price per transistor of integrated circuitry is already low, and is seemingly spiraling downward.
A strong case can be made that the small key paradigm of the prior art is an anachronism which emerged from the pencil and paper era of encryption. In an era of integrated circuits, it can be asserted that the large key expanding amorphous process of the present invention is indeed pound wise and yet penny frugal.
The merits of the contracting amorphous process of the present invention are similar to the merits of the expanding process because the contracting case is simply another mode of the amorphous process.
The state machine, and state machine method, of the present invention is probably the least attractive of the three machines, and three methods, of the invention. However, the state machine is still interesting because it is in essence a combination of the expanding and contracting amorphous processors. Or in other words, the state machine is a complex version of the amorphous teeter-totter. This teeter-totter action results from the expansion and contraction which occurs at each transition. Since the amorphousness of both operations is high, the resulting random output should be secure, and was empirically found to be highly random.
These and other aspects and attributes of the invention will become increasingly clear upon reference to the following drawings and accompanying specification.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a keystream generator using an expanding amorphous process in a feedback configuration.
FIG. 2 is a block diagram of the holdback multiplexer used to form an amorphous stream for the expanding process of FIG. 1.
FIG. 3 is a block diagram of an emission generator used to form element emissions which are then multiplexed in the expanding process of FIG. 1.
FIG. 4 is a block diagram of an emission generator used to form element emissions by a dispersed selection process which are then multiplexed in the expanding process of FIG. 1.
FIG. 5 is a block diagram of a message key exploder which expands a small message key into a larger partition index for use in the keystream generator of FIG. 1.
FIG. 6 is a block diagram of a keystream generator using a contracting amorphous process to contract a random number stream into a secure keystream.
FIG. 7 is a block of the "hashed division" index extractor used to generate permutations for use in the contracting amorphous process of FIG. 6.
FIG. 8 is a block diagram of a keystream generator using a state machine to generate random numbers.
FIG. 9 is a block diagram of the random generator used to form dependency bits via a contracting amorphous process for use in the state machine of FIG. 8.
FIG. 10 is a block diagram of the unpacker used to form function indexes from packed function indexes for use in the state machine of FIG. 8.
FIG. 11 is a block diagram of the operand maker used to form operands for use in the state machine of FIG. 8.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
1. Amorphous Processes for Keystream Generation
The keystream generators of the present invention in their various forms have, as their primary principle of operation, the concept of performing an "amorphous process". Accordingly, it is immediately appropriate to first explain more exactly what an "amorphous process" is.
An "amorphous process" consists of applying a "partition" to a large random "base key". A "base key" is a set of bits. A "partition" is a selection of certain base key bits, with some bits possibly selected more than once and with other bits possibly not selected at all, and with none, some, or all of the selected bits being logically complemented. Or in other words, a "partition" is a permuted generalized combination with substitutions.
The bits selected via some partition form a sequence called an "amorphous stream". A "partition index" is value which specifies a partition under some partitioning method, i.e. a "partition index" fully specifies how the amorphous stream is to be selected from the base key.
The amorphous process is conveniently divided into three classes. An "expanding" amorphous process results from a partitioning method in which the partition indexes are smaller than the amorphous streams produced. A "contracting" amorphous process results when the partition indexes are larger than the amorphous streams produced. And finally, an "equivocation" process is one with the same size of indexes as the amorphous streams. This last critical point case is still called equivocation even if a particular partitioning method is not tight enough to provide for true equivocation in the sense defined by Shannon. The limits of the ratios of amorphous expansion or contraction are both infinite, though in practice a finite ratio must be used to construct a practical system.
To implement the "key extension" method of the present invention, an expanding amorphous process is used to generate a keystream from a given initial partition index. The amorphous stream from the initial partition index will provide a "next" partition index with the excess bits used as part of the keystream. Continuing with successive partitions results in the generation of a keystream.
To implement the "contracted randoms" method of the present invention, a contracting amorphous process is applied to the output of some pseudo random number generator to produce a more secure keystream. Additional security is achieved since amorphous contraction will hide the underlying method of random number generation. Alternatively, a contracting process could follow an expanding process thus eliminating mathematical random number generation entirely. This configuration of expansion followed by contraction is called the "amorphous teeter-totter".
To better understand the amorphous process, consider an expanding process consisting solely of transpositions. The base key is first divided into a plurality of contiguous items called elements. For a given element of, for example, 1024 bits, the number of possible paths therein is a very, very, large number, with the actual value being 1024!. Since expansion is desired, a much smaller set of all paths must be selected. Furthermore, these paths should be simple with respects to transition complexity and the number of internal values necessary to represent any point in the path. One adequate class of paths which requires only two internal values is the FRONTs and TAILs method. Here, the path "FT" denotes the sequence F1, T1, F2, T2, F3, T3, etc where F1 is the first bit of the element, F2 is the second bit, and so on, and where T1 is the last bit, T2 is the second to the last bits, and so on. The sequence of bits from an element selected by a path is called an "element emission".
The FRONTs and TAILs method give rise to paths such as {F, T, FT, FFT, FFTT}, with each path defining a different element emission. To form the amorphous stream for a given partition, all of the element emissions must be multiplexed together in some manner. While these emissions could simply be taken one after the other in some permuted order as was done with transposition block ciphers, a better multiplexing method should be employed to complicate correlating an amorphous stream with the base key.
One such better method which is sufficiently simple is the holdback multiplexer which views all the elements as a permuted set but forms the amorphous stream by taking one bit at a time from successive element emissions in their permuted order. In addition, each element is associated with a holdback count which is decremented each time the multiplexer outputs a bit from that element emission. When the holdback count reaches zero, the pending bit in the element emission is "held back" at that point with the multiplexer continuing with the next element emission. The holdback counter is reset to some fixed value with the "held back" bit output during the next pass.
Substitution can readily be included in the above partitioning method. Let Fc denote the logical complement of a "front bit" and similarly Tc for tail bits. Now the set of paths could become {F, Fc, T, Tc, FT, FcT, Ftc, FcTc}. Annihilation can also be readily included by interpreting some of the leading bits in each element as a "hole" which are excluded from the element emissions.
The details of mapping partition indexes to partitions will be given in greater detail shortly below; however, it should be fairly clear how this could be done. Of note, finer and finer partitions can be made until a contracting process is reached. Furthermore, by using larger and larger number of bits to select the permutation of elements (this can be done in a very general way), any contraction ratio desired can be readily obtained. Other partitioning methods and generalization will be also be described in this section below.
The key extension method of generating a keystream is now described, as depicted by expanding amorphous process keystream generator 32 of FIG. 1. An initial partition index 15 is sent to partition index register 16, a partition descriptor 13 is sent to partition descriptor register 14, and a base key 11 is sent to base key ram 12. With the processor thus initialized, the first partition is then carved. Partition extractor 18 receives a partition index from partition index register 16 and a partition descriptor from partition descriptor register 14. Partition extractor 18 then carves a partition with respects to base key ram 12 and stores the partition information in the following registers: element descriptor one (1) 20 through element descriptor N 21, holdback register one (1) 24 through holdback register N 25, and several internal registers within holdback multiplexer 28.
After the partition information is stored, control is passed from partition extractor 18 to holdback multiplexer 28. Holdback multiplexer 28 first zeros the count field in emission register one (1) 26 through emission register N 27. Holdback multiplexer 28 then generates amorphous stream 33 which is sent to stream router 30. The details of this generation process are described shortly below. Stream router 30 first passes received amorphous stream 33 into a next partition index stored in partition index register 16. The remainder of amorphous stream 33 is passed as keystream 31.
Once amorphous stream 33 is completely generated, control is returned from holdback multiplexer 28 to partition extractor 18, which proceeds to carve a new partition with the new partition index just generated. Utilizing feedback as described, this process repeats resulting in a keystream 31 of desired length, quite possibly very long.
The operational details of holdback multiplexer 28 are now described. FIG. 2 depicts the internal structure of the multiplexer. First, the emission count reset stage. Multiplexing controller 51 initializes emission counter 46 with the maximum number of elements. Multiplexing controller 51 then successively zeros the count field in emission register N 27 through emission register one (1) 26 using emission counter 46 to address the emission registers. Emission counter 46 is decremented at each cycle until the counter reaches zero, which means that all the emission count registers have been reset.
The generation of amorphous stream 33 by multiplexing controller 51 is described next. The usual case for generating an amorphous bit is described first, with the various sub-cases described thereafter.
Target register 44 is read to provide for a target element. Target register 44 selects an emission count register (26-27) whose value is read and stored in emission counter 46. Emission counter 46 is then decremented. Target register 44 also selects a current holdback register (24-25) whose value is read and stored in holdback counter 50. Holdback counter 50 is then decremented. Target register 44 further selects an emission fragment register (26-27) whose value is read and stored in shift register one (1) 48. Multiplexing controller 51 pulses shift register one (1) 48 to obtain a bit which is sent as the next part of amorphous stream 33.
The selected emission fragment register (26-27) is updated by writing to it the modified contents of shift register one (1) 48 via emission bus 23. The selected current holdback register (24-25) is also updated by writing to it the modified contents of holdback counter 50 via holdback bus 29. Further, the selected emission count register (26-27) is updated by writing to it the modified contents of emission counter 46. Finally, target register 44 is updated by storing to it the value of the next field of the element link register (40-42) selected by the target register.
Now for the sub-cases. If the value read from the selected emission count register (26-27) is zero, then multiplexing controller 51 sends a emission refill request (and the contents of target register 44) via emission bus 23 to emission generator 22. Emission generator 22 gains control and refills the selected emission register (26-27). Emission Generator 22 returns control by sending an emission refilled signal to multiplexing controller 51, multiplexing then continues with the same element.
If holdback counter 50 is zero upon being decremented, a holdback occurs. Multiplexing controller 51 then reads the master field of the holdback register (24-25) selected by target register 44 with the master value written back to current field of selected holdback register. Multiplexing continues at the update point for target register 44.
If a refill request to emission generator 22 cannot be satisfied, i.e. when the selected element's emission is exhausted, then control is returned immediately by sending an element exhausted signal to multiplexing controller 51. The exhausted target element is "deleted" by unlinking the element selected by target register 44 from the doubly linked list of element link register one (1) 40 through element link register N 42 by modifying the proper registers therein. Target register 44 is also advanced. If another element exists, the multiplexing continues. If, however, the deleted element was the last element, multiplexing controller 51 returns control to partition extractor 18 by sending an emissions exhausted signal via holdback bus 29.
Holdback multiplexer 28 could be enhanced in the following manner to emit a plurality of bits at each element stage. To this end, each element specifier would include a cycle list specification with the multiplexer now employing an array of registers to hold the cycle lists. (Alternatively, a global cycle list could be used to keep the size of partition indexes small.) Consider the cycle list of {3, 1, 2, 1}. The multiplexer would cyclically access this list. The first modifier of 3 would cause three successive emission bits (instead of one) to be emitted into the amorphous stream during that element emission multiplexing stage, then 1 bit, then 2 bits, and then 1 bit (then repeat) emissions on the successive concatenating phases for that element emission.
Another enhancement for holdback multiplexer 28 would be to employ a plurality of element permutations with each permutation associated with a chain. Each chain would require an additional array of element link registers to hold its permutation. Here, |
