Secret key cryptosystem and method utilizing factorizations of permutation groups of arbitrary order 2.sup.l

Abstract

A secret-key block-cipher utilizing the principles of factorization and composition with respect to general logarithmic signatures in permutation groups of arbitrary size 2.sup.l, and methods of use thereof are disclosed. The preferred embodiment uses two encryption/decryption stages from composition and factorization means including novel and efficient circuits for multiplication and inversion of permutations, operating in their compact form representation. The system is scalable to any input/output block size l and performs encryption/decryption at very high data rates.

Claims

We claim:

1. A system for receiving input vectors, of length L, and outputting encrypted vector, versions of said input vectors, of length L, each of said input and output vectors consisting of a sequential plurality of binary digits, said system comprising, in functional combination:

a) a vector accepting means for receiving input binary digit vectors; and

b) a data key expanding pseudo-random number generator means for accepting a user provided input data key, and generating and outputting a data key dependent sequence of pseudo-random numbers; and

c) a first logarithmic signature containing storage means which comprises memory for containing a first logarithmic signature, said first logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers; and

d) a second logarithmic signature containing storage means which comprises memory for containing a second logarithmic signature, said second logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said first and second logarithmic signatures are characterized by a requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

e) a primary mathematical operations means which comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said second logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing at least a second logarithmic signature, and storing it in said second logarithmic signature containing storage means; and

f) a primary factorization means for identifying, accessing and concatenating into a primary factorization means output vector, binary pointers which identify locations of permutations in a second logarithmic signature stored in said second logarithmic signature containing storage means, which permutations, when sequentially composed, duplicate a vector input into said primary factorization means;

said system being functionally structured such that inputting a user defined data key to said data key expanding pseudo-random number generator means, results in said data key expanding pseudo-random number generator means outputting a sequence of pseudo-random numbers in response; and

said system being further functionally structured such that after receipt of a sequence of pseudo-random numbers by said primary mathematical operations means, mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means is performed to form a second logarithmic signature, which second logarithmic signature is then stored in said second logarithmic signature containing storage means, while preserving the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after entering at least one input vector to said primary factorization means from said vector accepting means for receiving input binary digit vectors, said primary factorization means identifies permutations present in said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature storage means, which when sequentially composed result in said at least one input vector; and

said system being further functionally structured such that said primary factorization means further assigns identified permutations in each of said mathematical construct blocks of a second logarithmic signature, stored in said second logarithmic signature containing storage means, a binary digit pointer which identifies the permutation location within said second logarithmic signature, and

said system being further functionally structured such that said primary factorization means further sequentially concatenates identified binary digit location pointers into a once encrypted vector, of length L, of said at least one input vector, of length L, which is input to said vector accepting means for receiving input binary digit vectors, and makes said once encrypted vector, of length L, of said at least one input vector of length L, available as output therefrom, at an output means thereof.

2. A system as in claim 1, which further functionally comprises:

g) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

h) a composition means which comprises means for identifying, accessing and sequentially multiplying a plurality of permutations, of a sequential plurality of binary digits, in a third logarithmic signature stored in said third logarithmic signature containing storage means, to provide a composition means output vector;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo-random number generator means, to a selection from the group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means;

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means;

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means, to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector version of said at least one input vector output by said primary factorization means,

to said composition means, said once encrypted vector version of at least one input vector output by said primary factorization means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, such that a permutation in each of said mathematical construct blocks of said third logarithmic signature is identified; and

said system being further functionally structured such that said identified permutations in each of said mathematical construct blocks of said third logarithmic signature are then sequentially multiplied in said composition means, and

said system being further functionally structured such that said composition means makes the results of said sequential multiplication available as a twice encrypted vector version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, as output therefrom, at an output means thereof.

3. A system as in claim 2, in which said composition means is an "N" bit multiplier system for multiplying two compact form binary vectors A and B input thereto, each of said two compact form binary vectors A and B being of length L=2.sup.n -1, which compact form binary vectors A and B represent elements of a carrier group of permutations which is a Sylow-2 subgroup of a full symmetric group of degree 2.sup.n, said carrier group being of size .sub.2 (2.sup.n -1); said multiplier system comprising a swapping means for accepting input of two compact form binary vectors A and B of length L=2.sup.n -1 at an input thereof and providing output of two compact form binary vectors of length L=2.sup.n -2 at an output thereof in an order selected from the group consisting of:

unchanged order; and

swapped order;

and said multiplier system further comprising two "N/2" bit "self-similar" sub-multiplier systems therein, wherein each of said two "self-similar" sub-multiplier systems comprises a sub-swapping means and two sub-sub-multiplier systems; said swapping means in said multiplier system being located with respect to said two sub-multipliers in said multiplier system at a location selected such that compact binary form vectors input thereto are input sequentially first to a selection from the group consisting of:

said swapping means; and

said two sub-multipliers;

and then into a selection from the group consisting of:

said two sub-multipliers; and

said swapping means respectively;

said order of said swapping means and two sub-multipliers being determinative of the result of multiplication, said result being a member of the group consisting of:

AB; A.sup.-1 B; AB.sup.-1 ; B.sup.-1 A and BA.sup.-1.

4. A system as in claim 1, which further functionally comprises:

g) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

h) a secondary factorization means for identifying, accessing and concatenating into a secondary factorization means output vector, binary pointers which identify locations of permutations in a third logarithmic signature stored in said third logarithmic signature containing storage means, which permutations, when sequentially composed, duplicate a vector input into said secondary factorization means;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo-random number generator means to a selection from the group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means;

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means;

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means, to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector version of said at least one input vector output by said primary factorization means,

to said secondary factorization means, said once encrypted vector version of at least one input vector output be said primary factorization means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, and permutations present in said mathematical construct blocks of said third logarithmic signature are identified which when sequentially composed result in said at least one once encrypted vector, of version input thereto; and

said system being further functionally structured such that said secondary factorization means further assigns identified permutations in each of said mathematical construct blocks of said third logarithmic signature stored in said third logarithmic signature containing storage means, a binary digit pointer which identifies the permutation location within said third logarithmic signature, and

said system being further functionally structured such that said secondary factorization means further sequentially concatenates said identified binary digit location pointers into a twice encrypted vector version of said at least one input vector, of length L, input to said vector accepting means for receiving input binary digit vectors, and makes said twice encrypted vector version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, available as output therefrom, at an output means thereof.

5. A system for receiving input vectors, of length L, and outputting encrypted vector versions of said input vectors, of length L, each of said input and output vectors consisting of a sequential plurality of binary digits, said system comprising, in functional combination:

a) a vector accepting means for receiving input binary digit vectors; and

b) a data key expanding pseudo-random number generator means for accepting a user provided input data key, and generating and outputting a data key dependent sequence of pseudo-random numbers; and

c) a first logarithmic signature containing storage means which comprises memory for containing a first logarithmic signature, said first logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers; and

d) a second logarithmic signature containing storage means which comprises memory for containing a second logarithmic signature, said second logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said first and second logarithmic signatures are characterized by a requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

e) a primary mathematical operations means which comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said second logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing at least a second logarithmic signature, and storing it in said second logarithmic signature containing storage means; and

f) a primary composition means which comprises means for identifying, accessing and sequentially multiplying a plurality of permutations, of a sequential plurality of binary digits, in a second logarithmic signature stored in said second logarithmic signature containing storage means, to provide a primary composition means output vector;

said system being functionally structured such that inputting a user defined data key to said data key expanding pseudo-random number generator means, results in said data key expanding pseudo-random number generator means outputting a sequence of pseudo-random numbers in response; and

said system being further functionally structured such that after receipt of a sequence of pseudo-random numbers by said primary mathematical operations means, mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means is performed to form a second logarithmic signature which is then stored in said second logarithmic signature containing storage means, while preserving the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after entering at least one input vector to said primary composition means from said vector accepting means for receiving input binary digit vectors, said primary composition means identifies a permutation in each of said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature containing storage means; and

said system being further functionally structured such that said identified permutations in each of said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature containing storage means, are then caused to be sequentially multiplied in said primary composition means; and

said system being further functionally structured such that said primary composition means makes the results of said sequential multiplication available, as a once encrypted vector, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, as output therefrom, at an output means thereof.

6. A system as in claim 5, which further functionally comprises:

g.) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

h.) a factorization means for identifying, accessing and concatenating into a factorization means output vector, binary pointers which identify locations of permutations in a third logarithmic signature stored in said third logarithmic signature containing storage means, which permutations, when sequentially composed, duplicate a vector caused to be input into, said factorization means;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo-random number generator means to a selection from the group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means;

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means; and

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector version of at least one input vector output by said primary composition means,

to said factorization means, said once encrypted vector version of at least one input vector output by said primary composition means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, and permutations present in said mathematical construct blocks of said third logarithmic signature are identified which when sequentially composed result in said at least one once encrypted vector version input thereto from said primary composition means; and

said system being further functionally structured such that said factorization means further assigns identified permutations in each of said mathematical construct blocks of said third logarithmic signature stored in said third logarithmic signature containing storage means, a binary digit pointer which identifies the permutation location within said third logarithmic signature, and

said system being further functionally structured such that said factorization means further sequentially concatenates said identified binary digit location pointers into a twice encrypted vector version of said at least one input vector, input to said vector accepting means for receiving input binary digit vectors, and makes said twice encrypted vector version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, available as output therefrom, at an output means thereof.

7. A system as in claim 5, which further functionally comprises:

g.) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

h.) a secondary composition means which comprises means for identifying, accessing and sequentially multiplying a plurality of permutations, of a sequential plurality of binary digits, in a third logarithmic signature stored in said third logarithmic signature containing storage means, to provide a secondary composition means output vector;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo-random number generator means to a selection from said group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means; and

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means, to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector version of at least one input vector output by said primary composition means,

to said secondary composition means, said once encrypted vector version of at least one input vector output by said primary composition means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, such that a permutation in each of said mathematical construct blocks of said third logarithmic signature is identified; and

said system being further functionally structured such that said identified permutations in each of said mathematical construct blocks of said third logarithmic signature are then caused to be sequentially multiplied in said composition means, and

said system being further functionally structured such that said secondary composition means makes the results of said sequential multiplication available as a twice encrypted vector, of length L, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, as output therefrom, at an output means thereof.

8. A system as in claim 7, in which said secondary composition means is an "N" bit multiplier system for multiplying two compact form binary vectors A and B input thereto, each of said two compact form binary vectors A and B being of length L=2.sup.n -1, which compact form binary vectors A and B represent elements of a carrier group of permutations which is a Sylow-2 subgroup of a full symmetric group of degree 2.sup.n, said carrier group being of size .sub.2 (2.sup.n -1); said multiplier system comprising a swapping means for accepting input of two compact form binary vectors A and B of length L=2.sup.n -1 at an input thereof and providing output of two compact form binary vectors of length L=2.sup.n -2 at an output thereof in an order selected from the group consisting of:

unchanged order; and

swapped order;

and said multiplier system further comprising two "N/2" bit "self-similar" sub-multiplier systems therein, wherein each of said two "self-similar" sub-multiplier systems comprises a sub-swapping means and two sub-sub-multiplier systems; said swapping means in said multiplier system being located with respect to said two sub-multipliers in said multiplier system at a location selected such that compact binary form vectors input thereto are input sequentially first to a selection from the group consisting of:

said swapping means; and

said two sub-multipliers;

and then into a selection from the group consisting of:

said two sub-multipliers; and

said swapping means respectively;

said order of said swapping means and two sub-multipliers being determinative of the result of multiplication, said result being a member of the group consisting of:

AB; A.sup.-1 B; AB.sup.-1 ; B.sup.-1 A and BA.sup.-1.

9. A system as in claim 5, in which said primary composition means is an "N" bit multiplier system for multiplying two compact form binary vectors A and B input thereto, each of said two compact form binary vectors A and B being of length L=2.sup.n -1, which compact form binary vectors A and B represent elements of a carrier group of permutations which is a Sylow-2 subgroup of a full symmetric group of degree 2.sup.n, said carrier group being of size .sub.2 (2.sup.n -1); said multiplier system comprising a swapping means for accepting input of two compact form binary vectors A and B of length L=2.sup.n -1 at an input thereof and providing output of two compact form binary vectors of length L=2.sup.n -2 at an output thereof in an order selected from the group consisting of:

unchanged order; and

swapped order;

and said multiplier system further comprising two "N/2" bit "self-similar" sub-multiplier systems therein, wherein each of said two "self-similar" sub-multiplier systems comprises a sub-swapping means and two sub-sub-multiplier systems; said swaping means in said multiplier system being located with respect to said two sub-multipliers in said multiplier system at a location selected such that compact binary form vectors input thereto are input sequentially first to a selection from the group consisting of:

said swapping means; and

said two sub-multipliers;

and then into a selection from the group consisting of:

said two sub-multipliers; and

said swapping means respectively;

said order of said swaping means and two sub-multipliers being determinative of the result of multiplication, said result being a member of the group consisting of:

AB; A.sup.-1 B; AB.sup.-1 ; B.sup.-1 A and BA.sup.-1.

10. A method of receiving input vectors of length L, and outputting encrypted vectors, of length L, each of which input and output vectors consists of a sequential plurality of binary digits, said method comprising the steps of:

A) providing an electronic system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors, each of said input and output vectors consisting of a sequential plurality of binary digits, said electronic system comprising, in functional combination:

A1) a system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors, each of said input and output vectors consisting of a sequential plurality of binary digits, said system comprising, in functional combination:

a) a vector accepting means for receiving input binary digit vectors; and

b) a data key expanding pseudo-random number generator means for accepting a user provided input data key, and generating and outputting a data key dependent sequence of pseudo-random numbers; and

c) a first logarithmic signature containing storage means which comprises memory for containing a first logarithmic signature, said first logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers; and

d) a second logarithmic signature containing storage means which comprises memory for containing a second logarithmic signature, said second logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said first and second logarithmic signatures are characterized by a requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

e) a primary mathematical operations means which comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said second logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing at least a second logarithmic signature, and storing it in said second logarithmic signature containing storage means; and

f) a primary factorization means for identifying, accessing and concatenating in to a primary factorization means output vector, binary pointers which identify locations of permutations in a second logarithmic signature stored in said second logarithmic signature containing storage means, which permutations, when sequentially composed, duplicate a vector input into said primary factorization means;

said system being functionally structured such that inputting a user defined data key to said data key expanding pseudo-random number generator means, results in said data key expanding pseudo-random number generator means outputting a sequence of pseudo-random numbers in response; and

said system being further functionally structured such that after receipt of a sequence of pseudo-random numbers by said primary mathematical operations means, mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means is performed to form a second logarithmic signature, which second logarithmic signature is then stored in said second logarithmic signature containing storage means, while preserving the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after entering at least one input vector to said primary factorization means from said vector accepting means for receiving input binary digit vectors, said primary factorization means identifies permutations present in said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature storage means, which when sequentially composed result in said at least one input vector; and

said system being further functionally structured such that said primary factorization means further assigns identified permutations in each of said mathematical construct blocks of a second logarithmic signature, stored in said second logarithmic signature containing storage means, a binary digit pointer which identifies the permutation location within said second logarithmic signature, and

said system being further functionally structured such that said primary factorization means further sequentially concatenates identified binary digit location pointers into a once encrypted vector, of length L, of said at least one input vector, of length L, which is input to said vector accepting means for receiving input binary digit vectors, and makes said once encrypted vector, of length L, of said at least one input vector of length L, available as output therefrom, at an output means thereof;

B) entering a first logarithmic signature to said first logarithmic containing storage means, and entering a data key to said data key expanding pseudo-random number generator means for accepting a user provided input data key;

C) entering at least one input vector to said primary factorization means from said vector accepting means for receiving input binary digit vectors; and

D) outputting a once encrypted vector, of length L, version of the input vector, of length L, of said at least one input vector, of length L, input to said vector accepting means for receiving input binary digit vectors, at the output means of said primary factorization means.

11. A method of receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, said method comprising the steps of:

A) providing an electronic system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors, each of said input and output vectors consisting of a sequential plurality of binary digits, said electronic system comprising, in functional combination:

A1) a system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors, each of said input and output vectors consisting of a sequential plurality of binary digits, said system comprising, in functional combination:

a) a vector accepting means for receiving input binary digit vectors; and

b) a data key expanding pseudo-random number generator means for accepting a user provided input data key, and generating and outputting a data key dependent sequence of pseudo-random numbers; and

c) a first logarithmic signature containing storage means which comprises memory for containing a first logarithmic signature, said first logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers; and

d) a second logarithmic signature containing storage means which comprises memory for containing a second logarithmic signature, said second logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said first and second logarithmic signatures are characterized by a requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

e) a primary mathematical operations means which comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said second logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing at least a second logarithmic signature, and storing it in said second logarithmic signature containing storage means; and

f) a primary composition means which comprises means for identifying, accessing and sequentially multiplying a plurality of permutations, of a sequential plurality of binary digits, in a second logarithmic signature stored in said second logarithmic signature containing storage means, to provide a primary composition means output vector;

said system being functionally structured such that inputting a user defined data key to said data key expanding pseudo-random number generator means, results in said data key expanding pseudo-random number generator means outputting a sequence of pseudo-random numbers in response; and

said system being further functionally structured such that after receipt of a sequence of pseudo-random numbers by said primary mathematical operations means, mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means is performed to form a second logarithmic signature which is then stored in said second logarithmic signature containing storage means, while preserving the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after entering at least one input vector to said primary composition means from said vector accepting means for receiving input binary digit vectors, said primary composition means identifies a permutation in each of said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature containing storage means; and

said system being further functionally structured such that said identified permutations in each of said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature containing storage means, are then caused to be sequentially multiplied in said primary composition means; and

said system being further functionally structured such that said primary composition means makes the results of said sequential multiplication available, as a once encrypted vector, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, as output therefrom, at an output means thereof;

B) entering a first logarithmic signature to said first logarithmic signature containing storage means, and entering a data key to said data key expanding pseudo-random number generator means for accepting a user provided input data key;

C) entering at least one input vector to said primary factorization means from said vector accepting means for receiving input binary digit vectors; and

D) outputting a once encrypted vector, of length L, version of the input vector, of length L, of said at least one input vector, input to said vector accepting means for receiving input binary digit vectors, at the output means of said primary composition means.

12. A method of encrypting input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, said method comprising the steps of:

A) providing an electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, said system comprising:

A1) a system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors, each of said input and output vectors consisting of a sequential plurality of binary digits, said system comprising, in functional combination:

a) a vector accepting means for receiving input binary digit vectors; and

b) a data key expanding pseudo-random number generator means for accepting a user provided input data key, and generating and outputting a data key dependent sequence of pseudo-random numbers; and

c) a first logarithmic signature containing storage means which comprises memory for containing a first logarithmic signature, said first logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers; and

d) a second logarithmic signature containing storage means which comprises memory for containing a second logarithmic signature, said second logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said first and second logarithmic signatures are characterized by a requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

e) a primary mathematical operations means which comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said second logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing at least a second logarithmic signature, and storing it in said second logarithmic signature containing storage means; and

f) a primary factorization means for identifying, accessing and concatenating into, a primary factorization means output vector, binary pointers which identify locations of permutations in a second logarithmic signature stored in said second logarithmic signature containing storage means, which permutations, when sequentially composed, duplicate a vector input into said primary factorization means;

said system being functionally structured such that inputting a user defined data key to said data key expanding pseudo-random number generator means, results in said data key expanding pseudo-random number generator means outputting a sequence of pseudo-random numbers in response; and

said system being further functionally structured such that after receipt of a sequence of pseudo-random numbers by said primary mathematical operations means, mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means is performed to form a second logarithmic signature, which second logarithmic signature is then stored in said second logarithmic signature containing storage means, while preserving the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after entering at least one input vector to said primary factorization means from said vector accepting means for receiving input binary digit vectors, said primary factorization means identifies permutations present in said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature storage means, which when sequentially composed result in said at least one input vector; and

said system being further functionally structured such that said primary factorization means further assigns identified permutations in each of said mathematical construct blocks of a second logarithmic signature, stored in said second logarithmic signature containing storage means, a binary digit pointer which identifies the permutation location within said second logarithmic signature, and

said system being further functionally structured such that said primary factorization means further sequentially concatenates identified binary digit location pointers into a once encrypted vector, of length L, of said at least one input vector, of length L, which is input to said vector accepting means for receiving input binary digit vectors, and makes said once encrypted vector, of length L, of said at least one input vector of length L, available as output therefrom, at an output means thereof;

said electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, further comprising additional structure selected from the group consisting of A2 and A3, in which said A2 and A3 are:

A2) said system for receiving input vectors of length L, and outputting encrypted vectors of length L, as described supra in A1, which further functionally comprises:

g) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to, composition being selected from each of said ordered mathematical construct blocks; and

h.) a composition means which comprises means for identifying, accessing and sequentially multiplying a plurality of permutations, of a sequential plurality of binary digits, in a third logarithmic signature stored in said third logarithmic signature containing storage means, to provide a composition means output vector;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo-random number generator means, to a selection from the group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means;

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means;

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means, to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector version of said at least one input vector output by said primary factorization means,

to said composition means, said once encrypted vector version of at least one input vector output by said primary factorization means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, such that a permutation in each of said mathematical construct blocks of said third logarithmic signature is identified; and

said system being further functionally structured such that said identified permutations in each of said mathematical construct blocks of said third logarithmic signature are then sequentially multiplied in said composition means, and

said system being further functionally structured such that said composition means makes the results of said sequential multiplication available as a twice encrypted vector, of length L, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, as output therefrom, at a second stage output means thereof; and

A3) said system for receiving input vectors of length L, and outputting encrypted vectors of length L, as described supra in A1, which further functionally comprises:

g.) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

h.) a secondary factorization means for identifying, accessing and concatenating into a secondary factorization means output vector, binary pointers which identify locations of permutations in a third logarithmic signature stored in said third logarithmic signature containing storage means, which permutations, when sequentially composed, duplicate a vector input into said secondary factorization means;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo-random number generator means to a selection from the group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means;

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means;

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means, to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector version of said at least one input vector output by said primary factorization means,

to said secondary factorization means, said once encrypted vector version of at least one input vector output be said primary factorization means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, and permutations present in said mathematical construct blocks of said third logarithmic signature are identified which when sequentially composed result in said at least one once encrypted vector version input thereto; and

said system being further functionally structured such that said secondary factorization means further assigns identified permutations in each of said mathematical construct blocks of said third logarithmic signature stored in said third logarithmic signature containing storage means, a binary digit pointer which identifies the permutation location within said third logarithmic signature, and

said system being further functionally structured such that said secondary factorization means further sequentially concatenates said identified binary digit location pointers into a twice encrypted vector, of length L, version of said at least one input vector, of length L, input to said vector accepting means for receiving input binary digit vectors, and makes said twice encrypted vector, of length L, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, available as output therefrom, at a second stage output means thereof; and

said method further comprising the steps of:

B) entering a first logarithmic signature to said first logarithmic signature containing storage means, and entering a data key to said data key expanding pseudo-random number generator means for accepting a user provided input data key;

C) entering at least one input vector into said primary factorization means, via said means for receiving input binary digit vectors; and

D) outputting a twice encrypted vector, of length L, version of said at least one input vector, of length L, input to said vector accepting means for receiving input binary digit vectors, at said second stage output means.

13. A method of encrypting input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, said method comprising the steps of:

A) providing an electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, said system comprising:

A1) a system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors, each of said input and output vectors consisting of a sequential plurality of binary digits, said system comprising, in functional combination:

a) a vector accepting means for receiving input binary digit vectors; and

b) a data key expanding pseudo-random number generator means for accepting a user provided input data key, and generating and outputting a data key dependent sequence of pseudo-random numbers; and

c) a first logarithmic signature containing storage means which comprises memory for containing a first logarithmic signature, said first logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers; and

d) a second logarithmic signature containing storage means which comprises memory for containing a second logarithmic signature, said second logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said first and second logarithmic signatures are characterized by a requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

e) a primary mathematical operations means which comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said second logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing at least a second logarithmic signature, and storing it in said second logarithmic signature containing storage means; and

f) a primary composition means which comprises means for identifying, accessing and sequentially multiplying a plurality of permutations, of a sequential plurality of binary digits, in a second logarithmic signature stored in said second logarithmic signature containing storage means, to provide a primary composition means out put vector;

said system being functionally structured such that inputting a user defined data key to said data key expanding pseudo-random number generator means, results in said data key expanding pseudo-random number generator means outputting a sequence of pseudo-random numbers in response; and

said system being further functionally structured such that after receipt of a sequence of pseudo-random numbers by said primary mathematical operations means, mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means is performed to form a second logarithmic signature which is then stored in said second logarithmic signature containing storage means, while preserving the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after entering at least one input vector to said primary composition means from said vector accepting means for receiving input binary digit vectors, said primary composition means identifies a permutation in each of said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature containing storage means; and

said system being further functionally structured such that said identified permutations in each of said mathematical construct blocks of said second logarithmic signature, stored in said second logarithmic signature containing storage means, are then caused to be sequentially multiplied in said primary composition means; and

said system being further functionally structured such that said primary composition means makes the results of said sequential multiplication available, as a once encrypted vector, of length L, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, as output therefrom, at an output means thereof; and

said electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, further comprising additional structure selected from the group consisting of A2 and A3 in which said A2 and A3 are:

A2) said system for receiving input vectors of length L, and outputting encrypted vectors of length L, as described supra in A1, which further functionally comprises:

g.) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

h.) a factorization means for identifying, accessing and concatenating into a factorization means output vector, binary pointers which identify locations of permutations in a third logarithmic signature stored in said third logarithmic signature containing storage means, which permutations, when sequentially composed, duplicate a vector caused to be input into said factorization means;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo--random number generator means to a selection from the group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means;

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means;

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector version of at least one input vector output by said primary composition means,

to said factorization means, said once encrypted vector version of at least one input vector output by said primary composition means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, and permutations present in said mathematical construct blocks of said third logarithmic signature are identified which when sequentially composed result in said at least one once encrypted vector, of length L, version input thereto from said primary composition means; and

said system being further functionally structured such that said factorization means further assigns identified permutations in each of said mathematical construct blocks of said third logarithmic signature stored in said third logarithmic signature containing storage means, a binary digit pointer which identifies the permutation location within said third logarithmic signature, and

said system being further functionally structured such that said factorization means further sequentially concatenates said identified binary digit location pointers into a twice encrypted vector, of length L, version of said at least one input vector, of length L, input to said vector accepting means for receiving input binary digit vectors, and makes said twice encrypted vector, of length L, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, available as output therefrom, at a second stage output means thereof; and

A3) said system for receiving input vectors of length L, and outputting encrypted vectors of length L, as described supra in A1, which further functionally comprises:

a) a third logarithmic signature containing storage means which comprises memory for containing a third logarithmic signature, said third logarithmic signature consisting of a plurality of mathematical construct blocks, each of said mathematical construct blocks containing at least two permutations of a sequential plurality of numbers;

wherein said third logarithmic signature is characterized by the requirement that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one, composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

b) a secondary composition means which comprises means for identifying, accessing and sequentially multiplying a plurality of permutations, of a sequential plurality of binary digits, in a third logarithmic signature stored in said third logarithmic signature containing storage means, to provide a secondary composition means output vector;

said system being functionally structured such that after inputting a sequence of pseudo-random numbers produced by said pseudo-random number generator means to a selection from said group consisting of:

said primary mathematical operations means; and

a mathematical operations means other than said primary mathematical operations means which is functionally equivalent to said primary mathematical operations means

which selection comprises:

means for accepting a sequence of pseudo-random numbers;

means for accessing said first logarithmic signature containing storage means;

means for accessing said third logarithmic signature containing storage means; and

means for applying a sequence of pseudo-random numbers to a first logarithmic signature, said first logarithmic signature being stored in said first logarithmic signature containing storage means, and producing a third logarithmic signature, and storing it in said third logarithmic signature containing storage means;

said selection performs mathematical manipulation of a first logarithmic signature stored in said first logarithmic signature containing storage means, to form a third logarithmic signature, said third logarithmic signature being non-identical to said second logarithmic signature, and which third logarithmic signature is then stored in said third logarithmic signature containing storage means, while preserving the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation subjected to composition being selected from each of said ordered mathematical construct blocks; and

said system being further functionally structured such that after the entering of,

said once encrypted vector, of length L, version of at least one input vector, of length L, output by said primary composition means,

to said secondary composition means, said once encrypted vector version of at least one input vector output by said primary composition means is applied to said third logarithmic signature stored in said third logarithmic signature containing storage means, such that a permutation in each of said mathematical construct blocks of said third logarithmic signature is identified; and

said system being further functionally structured such that said identified permutations in each of said mathematical construct blocks of said third logarithmic signature are then caused to be sequentially multiplied in said composition means, and

said system being further functionally structured such that said secondary composition means makes the results of said sequential multiplication available as a twice encrypted vector, of length L, version of said at least one input vector, of length L, entered to said vector accepting means for receiving input binary digit vectors, as output therefrom, at a second stage output means thereof; and

said method further comprising the steps of:

B) entering a first logarithmic signature to said first logarithmic signature containing storage means, and entering a data key to said data key expanding pseudo-random number generator means for accepting a user provided input data key;

C) entering at least one input vector into said primary composition means, via said means for receiving input binary digit vectors; and

D) outputting a twice encrypted vector, of length L, version of said at least one input vector, of length L, input to said vector accepting means for receiving input binary digit vectors, at said second stage output means.

14. A method as in claim 12 in which the step of providing an electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, includes providing:

first, second and third logarithmic signature containing storage means which each physically comprise computer memory, and primary mathematical operations means and primary factorization means and data key expanding pseudo-random number generator means which all physically comprise computer software driven computer system hardware.

15. A method as in claim 13 in which the step of providing an electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, includes providing:

first, second and third logarithmic signature containing storage means which each physically comprise computer memory, and primary mathematical operations means and primary composition means, and said data key expanding pseudo-random number generator means all physically comprise computer software driven computer system hardware.

16. A method as in claim 10 or 12, in which the step of providing an electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, includes providing:

a primary factorization means which functionally comprises a decomposition means with the operational property that an output vector produced thereby and made present at an output means thereof is a product of a first vector input thereto at a first input means thereof and a reverse bit order inverse of a second vector input thereto at a second input means thereof; an input to said factorization means being capable of accessing, via a feedback means, said output means;

such that repeated application is made thereof in which, at each application after the first, the output of said primary factorization means produced at said output means thereof by a previous application, is input to said first input means thereof simultaneous with input of an inverted is reverse bit ordered vector, to said second input means.

17. A method as in claim 11 or 13, in which the step of providing an electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, includes providing:

a primary composition means which functionally comprises a multiplier means with the operational property that an output vector produced thereby and made present at an output means thereof is a product of a first vector input thereto and of a second vector input thereto,; an input to said primary composition means being capable of accessing, via a feedback means, said output means;

such that repeated application is made thereof in which, at each application after the first, the output of said multiplier means produced at said output means thereof by a previous application, is input to said first input means thereof simultaneous with input of a vector to said second input means which is to be multiplied by said vector input to said first input means.

18. A method as in claim 10, 11, 12 or 13, in which the step of entering a first logarithmic signature to said first logarithmic signature containing storage means includes forming said first logarithmic signature by a process of:

a) defining a vector I.sub.s =(1,2,3, . . . ,2.sup.s);

b) defining a vector I.sub.s (2.sup.2 +I.sub.2);

c) defining an array ##EQU17## d) defining an array ##EQU18## e) defining logarithmic signatures ##EQU19## and ##EQU20## each of strength 1; f) utilizing the above defined I.sub.s, I.sub.s, J.sub.1, J.sub.1, .alpha..sub.1 and .alpha..sub.1 in a recursive manner to construct additional first logarithmic signatures of increasing strengths: ##EQU21## where the recursively progressing .alpha.'s of increasing strengths s are the first logarithmic signature.

19. A method as in claim 18, in which the step of entering a first logarithmic signature to said first logarithmic signature containing storage means includes in the step of forming said first logarithmic signature, the forming of:

a first logarithmic signature of strength S, where s is an integer, in which, an input vector input to said vector accepting means for receiving input binary digit vectors consists of a plurality sequence of binary digits of length L=2.sup.s -1.

20. A method as in claim 10, 11, 12, or 13, in which the step of entering a data key to said data key expanding pseudo-random number generator means for accepting a user provided input data key includes the step of providing a data key expanding pseudo-random number generator which comprises providing:

a fourth logarithmic signature and a fifth logarithmic signature in fourth logarithmic signature containing storage and fifth logarithmic signature containing storage means, respectively;

such that when a user provided data key is input to said pseudo-random number generator means and applied to said fourth logarithmic signature, by a procedure involving a selection from the group consisting of:

factorization; and

composition;

a first encrypted version of said data key is produced, and such that said first encrypted version of said data key is applied to said fifth logarithmic signature, by a procedure involving a selection independently selected from the group consisting of:

factorization; and

composition);

to produce a second encrypted version of said data key is produced, said second encrypted version of said data key being an expanded data key dependent sequence of pseudo-random numbers.

21. A method as in claim 10, 11, 12, or 13, in which the step of providing an electronic system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors, of length L, each of which input and output vectors consists of a sequential plurality of binary digits, includes providing a primary mathematical operations means which accesses said first logarithmic signature and produces said second logarithmic signature therefrom; wherein said primary mathematical operations means comprises means for performing at least one mathematical operation selection from the group functionally consisting of:

1) commutation shuffle;

2) fusion procedure;

3) randomization procedure; and

4) permutation shuffle;

A) wherein said commutation shuffle comprises the steps of:

a) identifying at least one pair of adjacent mathematical construct blocks in said first logarithmic signature, in which permutations in one said mathematical construct block commute with permutations in the adjacent mathematical construct block in that the same product result is achieved when said permutations are multiplied together regardless of an order in which said pair of permutations are multiplied together; and

further proceed to:

interchange the positions of said identified adjacent mathematical construct blocks in said first logarithmic signature or leave the positions of said identified adjacent permutations unchanged in said first logarithmic signature; and

b) optionally repeating step a; and

B) wherein said fusion procedure comprises the steps of:

identifying at least one sequential grouping of mathematical construct blocks in said first logarithmic signature, each of which mathematical construct blocks contains two permutations of a sequential plurality of numbers;

from each of said at least one sequential grouping of mathematical construct blocks in said first logarithmic signature forming and adding a separate mathematical construct block which contains more than two permutations of a sequential plurality of numbers;

such that the resulting logarithmic signature does not then consist entirely of a plurality of mathematical construct blocks each of which contain only two permutations of a sequential plurality of numbers, but rather consists of a number of mathematical construct blocks, some of which have more than two permutations therein; and

C) wherein said randomization procedure comprises the steps of:

a) selecting a mathematical construct block in a logarithmic signature which consists of a plurality of mathematical construct blocks, said selected mathematical construct block consisting of at least two permutations of a sequential plurality of numbers,

then selecting a permutation therein;

then for said selected permutation selecting permutation(s), one each, from at least one alternative, other, mathematical construct block located below said selected mathematical counstruct block in said logarithmic signature;

then multiplying said selected permutations in said selected mathematical construct block and in said alternative, other, mathematical construct blocks together and replacing said selected permutation in said selected mathematical construct block with the result of said multiplication, to form a replacement mathematical construct block for said selected mathematical construct block, and

b) optionally repeating step a for other permutations in said selected mathematical construct block in said logarithmic signature; and

then replacing said selected mathematical construct block in said logarithmic signature with said replacement mathematical construct block; and

c) repeating step a but selecting an alternative, other, mathematical construct block in said logarithmic signature to be the selected mathematical construct block than was selected in the first application of step a; and

then replacing said selected alternative, other, mathematical construct block in said logarithmic signature with said replacement mathematical construct block; and

D) wherein said permutation shuffle comprises the step(s) of:

a. identifying at least one pair of permutations in a selected mathematical construct block in a logarithmic signature, and optionally proceed to reverse the positions of said identified permutations in said mathematical construct block; and

b) optionally repeating step a for other permutation pairs in said selected mathematical construct block in said logarithmic signature; and

c) optionally repeating step a but modified by the selection of an alternative, other, mathematical construct block in said logarithmic signature;

in which said electronic system for receiving input vectors of length L, and outputting encrypted vectors of length L, each of which input and output vectors consists of a sequential plurality of binary digits, is further structured so that any of said:

1) commutation shuffle;

2) fusion procedure;

3) randomization procedure; and

4) permutation shuffle;

is/are performed only if, and only in a sequence, which provides that the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation being composed being selected from each of said logarithmic signature ordered mathematical construct blocks, is preserved.

22. A method as in claim 10, 11, 12, or 13, wherein the step of entering at least one input vector, via said means for receiving input binary digit vectors; involves entering at least one compact form binary vector of length L=2.sup.n -1, which compact form binary vector represent elements of a carrier group of permutations which is a Sylow-2 subgroup of a full symmetric group of degree 2.sup.n, said carrier group being of size .sub.2 (2.sup.n -1).

23. A system for receiving input vectors, of length L, and outputting encrypted vector, of length L, versions of said input vectors each of said input and output vectors consisting of a sequential plurality of binary digits, which system can also be used as a pseudo-random number generator means, said system functionally comprising a first logarithmic signature containing storage means and a second logarithmic signature containing storage means for containing first and second logarithmic signatures, respectively; said first and second logarithmic signature containing storage means having first and second non-identical logarithmic signatures, respectively, stored therewithin; logarithmic signatures being a collection of ordered mathematical construct blocks in which each input vector data key encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation being composed being selected from each of said logarithmic signature ordered mathematical construct blocks; and

a vector data input means for inputting a user provided input vector data key thereinto;

said system being functionally structured such that after inputting a user provided input vector/data key thereto at said vector/data input means, said system for receiving input vectors and outputting encrypted vector versions of said input vectors each of said input and output vectors consisting of a sequential plurality of binary digits,

said first logarithmic signature stored in said first logarithmic signature containing storage means is utilized in a procedure selected from the group consisting of:

factorization; and

composition,

so that a once encrypted version of said user provided input vector data key is produced; and

such that said once encrypted version of said input vector data key is then applied to said second logarithmic signature stored in said second logarithmic signature containing storage means by a procedure selected independently selected from the group consisting of:

factorization; and

composition;

so that a twice encrypted version of said input vector data key is produced.

24. A system as in claim 23;

wherein said system is further functionally structured such that said first logarithmic signature is produced by a procedure comprising the steps of:

a) defining a vector I.sub.s =(1,2,3, . . . ,2.sup.2);

b) defining a vector I.sub.s =(2.sup.s +I.sub.s);

c) defining an array ##EQU22## d) defining an array ##EQU23## e) defining logarithmic signatures ##EQU24## and ##EQU25## each of strength 1; f) utilizing the above defined I.sub.s, I.sub.s, J.sub.1, J.sub.1, .alpha..sub.1 and .alpha..sub.1 in a recursive manner to construct additional first logarithmic signatures of increasing strengths: ##EQU26## where the recursively progressing .alpha.'s of increasing strengths s are the first logarithmic signature.

25. A system as in claim 24 wherein said system is further functionally structured such that after inputting a user provided input vector data key thereto at said vector/data input means, said first logarithmic signature is optionally further developed, and said second logarithmic signature is developed by applying mathematical manipulation to said first logarithmic signature, said mathematical manipulation comprising at least one mathematical operation selection from the group consisting of:

1) commutation shuffle;

2) fusion procedure;

3) randomization procedure; and

4) permutation shuffle;

A) wherein said commutation shuffle comprises the steps of:

a) identifying at least one pair of adjacent mathematical construct blocks in said first logarithmic signature, in which permutations in one said mathematical construct block commute with permutations in the adjacent mathematical construct block in that the same product result is achieved when said permutations are multiplied together regardless of an order in which said pair of permutations are multiplied together; and

further proceed to:

interchange the positions of said identified adjacent mathematical construct blocks in said first logarithmic signature or leave the positions of said identified adjacent permutations unchanged in said first logarithmic signature; and

b) optionally repeating step a; and

B) wherein said fusion procedure comprises the steps of:

identifying at least one sequential grouping of mathematical construct blocks in said first logarithmic signature, each of which mathematical construct blocks contains two permutations of a sequential plurality of numbers;

from each of said at least one sequential grouping of mathematical construct blocks in said first logarithmic signature forming and adding a separate mathematical construct block which contains more than two permutations of a sequential plurality of numbers;

such that the resulting logarithmic signature does not then consist entirely of a plurality of mathematical construct blocks each of which contain only two permutations of a sequential plurality of numbers, but rather consists of a number of mathematical construct blocks, some of which have more than two permutations therein; and

C) wherein said randomization procedure comprises the steps of:

a) selecting a mathematical construct block in a logarithmic signature which consists of a plurality of mathematical construct blocks, said selected mathematical construct block consisting of at least two permutations of a sequential plurality of numbers,

then selecting a permutation therein;

then for said selected permutation selecting permutation(s), one each, from at least one alternative, other, mathematical construct block located below said selected mathematical construct block in said logarithmic signature;

then multiplying said selected permutations in said selected mathematical construct block and in said alternative, other, mathematical construct blocks together and replacing said selected permutation in said selected mathematical construct block with the result of said multiplication, to form a replacement mathematical construct block for said selected mathematical construct block, and

b) optionally repeating step a for other permutations in said selected mathematical construct block in said logarithmic signature; and

then replacing said selected mathematical construct block in said logarithmic signature with said replacement mathematical construct block; and

c. repeating step a but selecting an alternative, other, mathematical construct block in said logarithmic signature to be the selected mathematical construct block than was selected in the first application of step a; and

then replacing said selected alternative, other, mathematical construct block in said logarithmic signature with said replacement mathematical construct block; and

D) wherein said permutation shuffle comprises the step(s) of:

a. identifying at least one pair of permutations in a selected mathematical construct block in a logarithmic signature, and optionally proceed to reverse the positions of said identified permutations in said mathematical construct block; and

b) optionally repeating step a for other permutation pairs in said selected mathematical construct block in said logarithmic signature; and

c) optionally repeating step a but modified by the selection of an alternative, other, mathematical construct block in said logarithmic signature;

any of said:

1) commutation shuffle;

2) fusion procedure;

3) randomization procedure; and

4) permutation shuffle;

being performed being performed only if, and only in a sequence, which provides that the property of logarithmic signatures requiring that logarithmic signatures be a collection of ordered mathematical construct blocks in which each input vector data key encrypted by utilization thereof can be uniquely represented as one, and only one composition of permutations which are present in said logarithmic signature, one such permutation being composed being selected from each of said logarithmic signature ordered mathematical construct blocks, is preserved.

Description

TECHNICAL FIELD

The present invention relates to secret key cryptosystems and more particularly is a secret key block cipher utilizing logarithmic signatures of permutation groups of arbitrary order 2.sup.l, and method of use thereof. The system is scalable to an arbitrary input/ouput block size l, and operates at very high speeds. The present invention is also a new and efficient method of representing and/or multiplying and/or factoring elements of said permutation groups with respect to said logarithmic signatures. Preferred embodiment uses two logarithmic signatures and two encryption stages selected from composition and factorization means. Said two logarithmic signatures, are obtained by a randomization process seeded by a user key. The encryption transformation is performed using a multiplier means operating on input vectors in compact form.

BACKGROUND OF THE INVENTION

Related Work

Our new cryptosystem will be referred to as TST from the initials of the first names of the inventors. TST is theoretically related to, yet dramatically different from cryptosystem PGM which is, to our knowledge, the only cryptosystem based on factorizations of arbitrary non-abelian permutation groups.

Private key cryptosystem PGM was invented by S. Magliveras in the late 1970's. The system was described in his paper titled "A cryptosystem from logarithmic signatures of finite groups", Proceedings of the 29th Midwest Symposium on Circuits and Systems, Elsevier Publishing Company (1986), pp 972-975. An earlier paper by S. S. Magliveras, B. A. Oberg and A. J. Surkan, titled "A New Random Number Generator from Permutation Groups", Rend. del Sem. Matemat. e Fis. di Milano, LIV (1984), pp 203-223 also discusses PGM. The statistical and algebraic properties of PGM were studied by S. S. Magliveras and N. D. Memon in their papers "Algebraic Properties of Cryptosystem PGM", Journal of Cryptology, 5 (1992), pp 167-183, and "The Linear Complexity Profile of Cryptosystem PGM", Congressus Numerantium, Utilitas Mathematica, 72 (1989), pp 51-60. Additional related work appeared in the papers: "Complexity tests for cryptosystem PGM, Congressus Numerantium, Utilitas Mathematica, 79 (1990). pp 61-68, by S. S. Magliveras, N. D. Memon and K. C. Tam, and in "Factorizations of elementary Abelian p-groups and their cryptographic significance", J. of Cryptology, 7 (1994), pp 201-212 by M. Qu and S. A. Vanstone. Here we include only a brief description of PGM.

PGM is based on certain fundamental data structures for permutation groups, which are called logarithmic signatures. Let G be a permutation group of degree n. A logarithmic signature for G is an ordered collection .alpha.=(A.sub.0, A.sub.1 , . . . , A.sub.w-1) of ordered subsets A.sub.i =(a.sub.i,0 , . . . , a.sub.i,r.sbsb.i.sub.-1) of G, such that each element g .epsilon. G has a unique representation as a product of the form

g=a.sub.0,x.sbsb.0 .multidot.a.sub.1,x.sbsb.1 . . . a.sub.w-1,x.sbsb.w-1 a.sub.i,x.sbsb.i .epsilon. A.sub.i (1)

Thus, g corresponds to a unique vector x=(x.sub.0, . . . , x.sub.w-1), where 0.ltoreq.x.sub.i .ltoreq.r.sub.i =.vertline.A.sub.i .vertline.. The property that (A.sub.0 , . . . , A.sub.w-1) is a logarithmic signature can best be described by means of the equation:

G=A.sub.0 . . . A.sub.w-2 .multidot.A.sub.w-1 (2)

holding in the group ring G. It is a necessary condition for cryptographic security that the order of G be exponential in n, while for computational efficiency it is necessary that ##EQU1## be bounded by a polynomial in n.

The A.sub.i are called the blocks of .alpha., the vector of block lengths r=(r.sub.0, . . . , r.sub.w-1) is called the type of .alpha., and ##EQU2## is called the length of .alpha.. There are tame logarithmic signatures i.e. those for which the factorization for each g can be obtained in time polynomial in n, supertame signatures (the factorization can be obtained in time O(n.sup.2)) and there are wild signatures for which the factorization requires time O(.vertline.G.vertline.). The question of existence of tame logarithmic signatures has been settled. It has been shown that each member of an extremely large class of signatures is tame. This is the class of so called transversal logarithmic signatures. There exist an even larger number of non-transversal logarithmic signatures (see "On Logarithmic Signatures and Applications", M. Sc. Thesis, University of Nebraska--Lincoln, (1989), pp 1-59), but the question of whether the class of non-transversal logarithmic signatures is identical with the class of wild signatures is open and appears to be equivalent to the complexity-theory question P.noteq.NP. Surprisingly, the smallest group which has non-transversal logarithmic signatures is the cyclic group .sub.8. Let .LAMBDA.=.LAMBDA.(G) denote the family of all logarithmic signatures of a given group G.

Each signature .alpha. .epsilon. .LAMBDA. of type (r.sub.0, . . . , r.sub.w-1) induces a bijection .alpha.:.sub..vertline.G.vertline. (.apprxeq..sub.r.sbsb.0 .sym. . . . .sym..sub.r.sbsb.w-1).fwdarw.G, which is efficiently invertible if and only if .alpha. is tame.

To understand some of the significant differences between TST and PGM it is important to describe the mapping .alpha. mentioned above. If .alpha.=(A.sub.0, . . . , A.sub.w-1) is a logarithmic signature for G, we denote by .alpha..sub.ij the j.sup.th element of block A.sub.i of .alpha.. Let r=(r.sub.0, . . . , r.sub.w-1) be the type of .alpha.. We now define a bijection .THETA..sub..alpha. : .sub.r.sbsb.0 .sym. . . . .sym. .sub.r.sbsb.w-1 .fwdarw.G by:

.THETA..sub..alpha. (x.sub.0, . . . , x.sub.w-1)=.alpha..sub.0,x.sbsb.0 .multidot..alpha..sub.1,x.sbsb.1 . . . .alpha..sub.w-1,x.sbsb.w-1(3)

Next, define the integers m.sub.i, i=0, 1, . . ., w-1 by ##EQU3## and let .lambda. be the bijection from .sub.r.sbsb.0 .sym. . . . .sym. .sub.r.sbsb.w-1 onto .sub..vertline.G.vertline., defined by ##EQU4## For any x .epsilon. .sub..vertline.G.vertline., .lambda..sup.-1 (x) is efficiently computable by successive subtractions. This corresponds to obtaining the mixed base representation of x with respect to (r.sub.0, . . . , r.sub.w-1). Next, for any .alpha. .epsilon. .LAMBDA., define a map .alpha.: .sub..vertline.G.vertline. .fwdarw.G by composing .lambda..sup.-1 with .THETA..sub..alpha., thus .alpha.=.lambda..sup.-1 .THETA..sub..alpha.. FIG. 5. illustrates the definition of .alpha..

The .lambda..sup.-1 or .lambda. portions in computing .alpha.=.lambda..sup.-1 .THETA..sub..alpha., or .alpha..sup.-1 =.THETA..sub..alpha..sup.-1 .lambda. are referred to as knapsack segments.

The function .alpha. is always efficiently computable, but .alpha..sup.-1 is not unless .alpha. is tame. We denote by .LAMBDA. the collection {.alpha.:.alpha. .epsilon. .LAMBDA.}.

Basic PGM uses a pair of tame logarithmic signatures (.alpha.,.beta.) and defines the encryption transformation as the mapping E.sub..alpha.,.beta. =.alpha. .beta..sup.-1 :.sub..vertline.G.vertline. .fwdarw..sub..vertline.G.vertline. and the corresponding decryption transformation as D.sub..alpha.,.beta. =E.sub..beta.,.alpha. =.beta. .alpha..sup.-1.

We illustrate basic PGM by means of a small example. The group used is the alternating group on five points, A.sub.5, of order 60. This implies that the message space is the set .sub.60 ={0, 1, . . . , 59}. Consider below a table consisting of two log signatures .alpha. and .beta. for A.sub.5. For simplicity we have selected both .alpha. and .beta. to be of type (5,4,3). For compatibility reasons with the new TST system we list the blocks of a logarithmic signature .alpha.=(A.sub.0, . . . , A.sub.w-1) so that the A.sub.i are stacked sequentially one on top of the other with A.sub.0 at the bottom and A.sub.w-1 at the top. The central column of the table displays the common knapsack vector v to be used in the knapsack segments of the encrypting and decrypting functions. The integers m.sub.i are 1, 5 and 20 respectively. Let us now demonstrate the operation of enciphering. If for example, the plaintext message is 56, it can be uniquely decomposed with respect to v as, 56=(1+15+40)=1.multidot.m.sub.0 +3.multidot.m.sub.1 +2.multidot.m.sub.2. This determines uniquely the vector of row-indices .lambda..sup.-1 (56)=(1,3,2). We next compute

.pi.=.THETA..sub..alpha. (1,3,2)=(1 5 4 3 2).multidot.(1)(2 4)(3 5).multidot.(1)(2)(3 5 4)=(1 5 2)(3)(4).

We then compute .THETA..sub..beta..sup.-1 (.pi.), that is the representation of .pi. with respect to .beta.. Because .beta. is supertame the factorization can be obtained very efficiently but we will not go into this process here. After the factorization has been achieved we have

.pi.=(1 5 2)(3)(4)=(1 3 5 4 2).multidot.(1)(2 3 4)(5).multidot.(1)(2)(3 4 5 )

This determines the indices for .beta. as (3,1,0), i.e.

.THETA..sub..beta..sup.-1 (.pi.)=(3,1,0)

Finally, .lambda.(3, 1, 0)=3+5+0=8. Hence, E.sub..alpha.,.beta. (56)=8. It can be easily verified now that D.sub..alpha.,.beta. (8)=E.sub..beta.,.alpha. (8)=56.

    ______________________________________
    .alpha.     v             .beta.
    ______________________________________
    (1)(2)(3)(4)(5)
                0             (1)(2)(3 4 5)
    (1)(2)(3 4 5)
                20            (1)(2)(3 5 4)
    (1)(2)(3 5 4)
                40            (1)(2)(3)(4)(5)
    (1)(2)(3)(4)(5)
                0             (1)(2 5)(3 4)
    (1)(2 3)(4 5)
                5             (1)(2 3 4)(5)
    (1)(2 5)(3 4)
                10            (1)(2 4 3)(5)
    (1)(2 4)(3 5)
                15            (1)(2)(3 4 5)
    (1)(2)(3)(4)(5)
                0             (1 4 2 3 5)
    (1 5 4 3 2) 1             (1)(2)(3 5 4)
    (1 3 5 2 4) 2             (1 2 5 4 3)
    (1 2 3 4 5) 3             (1 3 5 4 2)
    (1 4 2 5 3) 4             (1 5 4)(2)(3)
    ______________________________________

    ______________________________________
    3,962,539 Jun., 1976  Ehrsam et al.
                                       380/29
    4,087,152 Mar., 1978  Tuckerman    178/22
    4,200,770 Apr., 1980  Hellman et al.
                                       380/30
    4,405,829 Sept., 1983 Rivest et al.
                                       380/30
    4,850,019 Jul., 1989  Shimizu et al.
                                       380/29
    5,003,597 Mar., 1991  Merkle       380/37
    5,214,703 May, 1993   Massey et al.
                                       380/37
    5,276,737 Jan., 1994  Micali       380/30
    5,351,299 Sept., 1994 Matsuzaki et al.
                                       380/29
    5,511,123 Apr., 1996  Adams        380/29
    5,515,307 May, 1996   Aiello et al.
                                       364/717
    5,577,123 Nov., 1996  Shimada      380/30
    ______________________________________