PUBLISHED: Ritter, T. 1991. Transposition Cipher with Pseudo-Random Shuffling: The Dynamic Transposition Combiner.

Cryptologia. 15(1):1-17.

ADDRESS: Blue Jean Software, 2609 Choctaw Trail, Austin, Texas 78745.

ABSTRACT: Extensions are made to a class of transposition cipher based on continued shuffling. These ciphers permute plaintext into ciphertext by swapping every message element with some message element selected at pseudo-random; elements can be characters (e.g., bytes) or bits.

Extensions include operation on very large data blocks, cryptographic shuffling variations, and the efficient extraction of plaintext from ciphertext. In addition, selected extra data can be adjoined to the plaintext to eliminate the data-dependent weak encipherings otherwise inherent in transposition. This bit- balancing data is supposed to completely eliminate all normal usage-frequency statistics from bit-transposition ciphertext.

The same mechanism can also be viewed as a cryptographic combiner, and, with sequence-to-block and block-to-sequence conversions, can generally replace the exclusive-OR combining function used in Vernam stream ciphers.

KEYWORD LIST: cryptography, computer cryptography, cipher, block cipher, permutation, transposition, dynamic transposition, combiner, cryptographic combiner, mixer, shuffle, data balancing, bit-balancing

This paper extends an existing cryptographic mechanism which
can be described as dynamic transposition. This mechanism
*combines*
two data sources into a complex result; one data source is
accumulated into a block, and the other is used to re-arrange
that block. A related inverse mechanism can *extract* the
accumulated data from that result.

Any form of transposition would seem to require some accumulation of data. Since data accumulation and serialization are easy with modern technology, dynamic transposition can be used to replace the Vernam exclusive-OR combiner in stream ciphers. The various techniques used in Vernam ciphers can also be applied to dynamic transposition; any cryptographic advantage of the resulting cipher is thus due to the additional strength of the new combiner.

This paper develops a particular form of dynamic
*transposition*;
a related paper develops a form of dynamic *substitution*.
Advantages of the transposition form include an interesting level
of secrecy in the resulting ciphertext and the virtual elimination
of meaningful statistical analysis measurements. These advantages
are purchased at the cost of some inherent increase in processing
effort, and the need to encipher data in blocks instead of
individual characters.

For a general background in cryptology see Kahn
[14],
and for details on the classical systems and their analysis see
Gaines
[12].
More modern statistical approaches are given by Sinkov
[26]
and Deavours
[7].
A good partly-technical anthology is Deavours *et. al.*
[6].
There is a nice but older survey by Mellen
[19],
a major effort by Diffie and Hellman
[9],
and a newer one by Massey
[18]
(also see the other papers in that issue). A rigorous but not
always applicable theoretical base starts with Shannon
[25]
and is extended by Hellman
[13].
A relatively modern technical reference is Beker and Piper 1982
[1],
although the generally more introductory Beker and Piper 1985
[2]
is a major reference for this paper, and will henceforth be
referred to as B&P 85. Denning
[8]
and Pfleeger
[23]
present cryptography in the broader context of computer security
issues.

A *transposition* cipher re-orders or *permutes*
plaintext elements into ciphertext
[12, 26].
If a single transposition can be thought of as a simple exchange
in the positions of two elements, it is the simplest form of
permutation; moreover, any possible permutation can be constructed
(in many different ways) with sequences of transpositions.
Permutation has been used for entire ciphers (mainly in an era of
pencil-and-paper operations), and, in a limited form, is still in
common use inside substitution-permutation networks
[11]
of the sort from which the U.S. Data Encryption Standard
[e.g., 21]
is built.

Most previous descriptions of transposition or permutation
ciphers have generally concerned fixed or *static* permutations.
However, B&P 85
[2]
does give the basis for *dynamic* permutations, in the sense
that each overall permutation is newly created (one transposition
at a time) by a continuing pseudo-random sequence. (To some
degree, the paper by Costas
[3],
and comments by Klingler
[15]
and Costas
[4]
anticipate some of this work.) Although not stated in B&P 85, this
means that *every* block is likely to be permuted differently,
no matter how many blocks there are (within reason). Moreover,
dynamic transposition mechanisms can be made to handle very large
blocks, as well as dynamic changes in block size.

The execution time of the shuffle process (in a software implementation) is generally proportional to the number of elements being shuffled. Consequently, the shuffle algorithm gives us no particular reason to encipher plaintext in units of small blocks. And, since the complexity of the result would seem to increase with the number of elements in any particular permutation, there is a strong motivation to use large blocks. Indeed, in most cases, each message could probably be enciphered as a single large block, or even a sequence of variable-size, yet sizable, blocks; the shuffle process takes about the same amount of work however organized.

Mathematically, a cryptographic transposition process
generates a *permutation*
of the input data; that is, the data are
simply re-arranged. The shuffle algorithm is a convenient way to
construct one of the many possible re-arrangements at random.
How many possible arrangements are there? Suppose the block
has *n* different elements; the first element can be
positioned in
*n*
possible places, the second in
*(n - 1)*,
the third in
*(n - 2)*
and so on, for a total of
*(n)(n - 1)(n - 2)...(1)*,
or *n!*
(n factorial) possibilities. So the probability of getting the
correct deciphering at random would seem to be 1 out of
*n!*.
This is very encouraging, since factorials can yield some really
remarkable values. For example, a 64-element block would be
considered rather small, yet the probability of correctly
deciphering such a block at random would seem to be 1 out of 64!,
or about 1 in 10^89.

Unfortunately, the usual situation is somewhat more
complex, since a data block is not constrained to have just
*one*
occurrence of any particular data value. But when there are
multiple occurrences of the same value, it surely cannot matter
which of those goes in which position when deciphering. So
multiple reverse permutations will each generate a correct
deciphering (though most of these will yield no information about
how the block was permuted). There are
*k!*
different permutations which produce the same deciphering for
*k*
occurrences of any particular value. Consequently, there are
*(k1!)(k2!)...(ki!)*
equivalent decipherings, for
*ki*
occurrences of each value. So the probability of getting one of
the correct decipherings is the product
*(k1!)(k2!)...(ki!)*
out of a total of
*n!*
possible decipherings (for block size
*n*).
Note that all but one of the correct decipherings represent an
incorrect permutation, so even if the correct deciphering is known,
finding the particular permutation involved should be exceedingly
difficult.

Suppose there are 26 different characters in a 26-element block;
there are 26! (about 4 x 10^26) different ways to permute that
block. Since each element is different there can be only one
correct deciphering, so there is only one chance in 10^26 of finding
this permutation at random. But if the 26 characters in the block
are *all the same value*, no permutation of any kind will cause
any apparent change. Accordingly, there is no way to hide a block of
similar data values with a pure transposition cipher.

The realization that *the cryptographic strength of
transposition depends upon the data to be enciphered* is both an
unexpected and serious complication. It seems only reasonable
that a cipher should be able to protect any possible sequence of
plaintext data. For example, one user may wish to encipher
computer machine code, and another may wish to encipher
graphics images. Such computer-oriented data may be very
complex, yet still contain long sub-sequences of identical values.
It is up to the cipher system to handle these sequences in a strong
manner. Classical transposition cannot do this.

From one point of view, the shuffling process converts a
confusion sequence into an enciphering permutation. We know
that there are
*n!*
such permutations in an
*n*-bit
block, but how many confusion sequences are there?

The confusion sequence must select one of the
*n*
block elements as an "exchange partner" for each element in the
block. Accordingly, there are
*n*
possibilities for the first partner,
*n*
again for the second, and so on, for a total of
*(n)(n)...(n)*
or
*n^n*
possible different selection-sequences. But there are only
*n!*
possible permutations, so each enciphering permutation is created by
*(n^n / n!)*
different sequences, on average.

Suppose we are shuffling that same 26-element block. We need 26 pseudo-random values, each of which selects one of the 26 possible block elements; there are 26^26 such sequences, about 6 x 10^36 of them. But there are only 26! enciphering permutations (about 4 x 10^26), so about 1.5 x 10^10 (15 billion) different sequences will create each permutation. So, even if the correct permutation is somehow known, finding the particular pseudo-random sequence which created it should be exceedingly difficult.

Consider a byte-shuffling block cipher: The plaintext will be collected into a block, then a controller will walk through the block, byte-by-byte, exchanging each byte with "partner" bytes selected by a random number generator. For cryptographic purposes it may be reasonable to generalize the shuffle process: For example, it is unnecessary to visit bytes in sequential order, nor need the shuffling stop after exactly one pass [15], as long as the deciphering system follows similar rules.

Letter (byte) frequency statistics are obviously unchanged
by the shuffling process. But the frequency distribution statistics
do not seem to aid deciphering nearly as much as they would on
a simple substitution cipher. Block transposition ciphertext might
be compared to a set of alphabet tiles: A particular message can
be built from those characters, but once they go back into the
storage box, how can anyone decide what particular message they
once represented? Indeed, unordered letters on their own
*cannot*
represent
*any one particular* message; instead, they stand for
*all the possible* messages which can be made from them.

Actually, since the message is expected to be a correct grammatical example, with correctly-spelled words, on an expected subject, which exactly covers the ciphertext letters, cryptanalysis may not actually be impossible. The normal cryptanalytic technique for transposition ciphers consists of obtaining two messages of the same length, both of which are presumably permuted in the same way. By anagramming both messages in the same way, the correct permutation is found when both messages read clearly [14, pp. 225-226]. Some assistance is available in the form of letter digram and trigram counts, which can support a particular inverse transposition by indicating the presence of statistical plaintext [13, p. 402]. But dynamic transposition need not generate any similar permutations, even for consecutive blocks of similar size.

Because a character or byte transposition combiner can provide good performance only when given a block containing different values, it could be useful to place a Vernam system (an exclusive-OR operation with a pseudo-random stream) before the transposition data input. In this way the plaintext data could be "randomized," and thus need "never" produce a stream of identical values which would compromise the strength of the transposition encipherment.

B&P 85 [2, pp. 93-96] describes a multi-step process of explicitly defining the permutation, finding the inverse, and then un-permuting the block according to the inverse permutation. It may be surprising that there is an easier way.

The shuffling process destroys no data; elements are just repositioned. The values involved in any particular exchange could easily be replaced, simply by exchanging them again, if those values had not been moved by later processing. So the last pair exchanged can be exchanged back into their previous positions. Once that pair has been replaced, the next previous pair can be undone, and so on. Thus, to decipher the shuffled data, the exact same element pairs need only be exchanged in reverse order.

During enciphering, the exchange pair is generally selected by a counter or other process, and a pseudo-random value. It is easy enough to run a counter in reverse, or the desired number of values could be collected in a buffer, and then simply accessed in reverse sequence; the pseudo-random sequence can be "reversed" in the same way. This provides all the information needed for deciphering. (In practice, very long sequences can be accommodated by writing filled buffers to a disk file; the file- stored buffers can easily be recovered for use in reverse order.)

In the same way that letters or bytes can be shuffled,
individual bits
[2, p. 93]
can also be shuffled. In this way the elements of any particular
character or byte might be spread throughout the ciphertext. Since
any particular bit looks remarkably like any other, how is a
cryptanalyst to select those bits which belong to any particular
plaintext byte? Of course, the cryptanalyst does not have to find
the particular bits corresponding to a *particular* byte, since
any bit of a given value is exactly the same as any other. But this
also means that there can be no way to tell which bits belong
together.

Byte-level frequency statistics are destroyed by bit-level permutation; only bit-level statistics are left. The cryptanalyst can know how many ones and how many zeros there are in the block (these are the same as in the original plaintext), but this does not seem to help much. Since virtually any message can be constructed from those bits, how is the cryptanalyst to select the correct one?

One interesting implication of bit-level exchange operations is that they are often ineffective. When byte values are being exchanged, the exact same value is "exchanged" (for zero net effect) about one time in 256 (assuming an even distribution). But, when working on bits, the other bit is exactly the same about half the time, for no net effect, and when the bits are different, exchanging them simply changes both bits. Even though half of the exchange operations will have no effect, the number of effective bit-changes is still on the same order as the number of bits (two bits change on every effective exchange). And if this turns out not to be enough, each block could be additionally shuffled, perhaps twice or more. In the end, some bits may always remain unchanged, others will be changed, while still others will be changed and changed back again.

Suppose we continue working with that same small block of 26 character-elements, each of which we assume to have 5 bits (perhaps a Baudot coding); thus the block contains 130 bit-elements. There may be multiple occurrences of some characters in the block, but for a bit-level analysis this is irrelevant. Suppose we have an even number of ones and zeros (the best possible case), 65 of each: Since any one-bit could substitute for any other one-bit, and any zero-bit substitutes for any other zero-bit, there would then be (65!)(65!) deciphering permutations, out of the 130! possible.

The direct evaluation of expressions like these is far beyond the capabilities of a scientific calculator or most computer languages. But it is possible to build such numbers in logarithmic form, and once into logs we use addition and subtraction instead of multiplication and division. For the factorials 65! and 130!, we want the sum of the logs of the integers 2 through 65, and 2 through 130, respectively. There are approximations for the log factorial, but with a computer (and for the values here), it is probably about as easy to sum the logs explicitly.

By actually doing each log and the sum we get
ln(65!) = 209.34, and ln(130!) = 506.13, approximately. These
values are exponents or powers of *e* (the base of natural
logarithms), and would lead to results too large (or small) to
evaluate. It seems reasonable to change to the more-familiar base
2, so that we can think of these huge values as the number of bits
it takes to represent them. Dividing by ln(2) = 0.6931, we get
log2(65!) = 302.01 and log2(130!) = 730.19; these exponents thus
represent some binary values which are 303 and 731 bits long,
respectively.

For the 130-bit block, 130^130 or about 2^913 possible confusion sequences will generate 130! or 2^730 possible enciphering permutations: The number of possible permutations is huge, and this hides the plaintext. About (65!)(65!) or 2^604 different permutations will encipher a plaintext block into a particular ciphertext block: The number of deciphering permutations is huge, and this hides the correct permutation (even from known plaintext). An average of 130^130 / 130! or about 2^183 different sequences will create any particular permutation: The number of possible sequences is huge, and this hides any particular sequence (even from a known permutation). Thus, the classical attacks of brute force and known plaintext would seem to be wrong ways to penetrate dynamic transposition.

A seemingly different approach would be a bit-by-bit
defined-plaintext attack, since this might (if the rest of the system
does not prevent it) succeed in building up a complete description
of a particular enciphering permutation. Of course, this would
mean that the cryptanalyst had that plaintext already (indeed,
was *generating* the plaintext), so the attack would be on the
pseudo-random sequence. But 2^183 different sequences could have
created that permutation (and those sequences are distributed
among 2^913 possible sequences), so there would seem to be no way
for a cryptanalyst to select the correct one.

If all data to be enciphered and deciphered are already in
the form of blocks, then each block is (obviously) already full and
can simply be handled as a unit. But whenever variable amounts
of data are to be enciphered as blocks, the last block is unlikely to
be completely filled, and the unused area must then be filled or
*padded*
[21]
with extra data. On average, half a block of padding
is required for each message, thus expanding the ciphertext; this
is a motivation for limiting the block size. This may not be a
particularly significant motivation, however, considering the
amount of data which may be easily stored and quickly
communicated by computer, and padding is unnecessary when
variable-sized "blocks" are available.

A more significant complication is that any padding must be in some way distinguished from the plaintext data, so that it may be removed in deciphering. In general, a particular data value cannot be used as a separator, because "binary" data (such as computer object code) may be enciphered, and such data may contain every possible byte value. The conventional solution is to include some sort of length value along with the padding, which is then removed with the padding when deciphering.

Another complication of data blocking, at least for dynamic transposition, is that the block size defines the value range needed on the "random number" input (as well as the number of values required). Thus, if dynamic transposition is to accept variable block sizes, the random number range must be able to cover an arbitrary block size. And even fixed size blocks, if they are large, can demand a fairly large random number range. For example, a 256 kilobyte block contains 2,097,152 bits, which implies a 21-bit random value to select between them. Shuffling that block requires 2,097,152 of those 21-bit values (and about 6 megabytes of temporary disk storage to reverse that sequence when deciphering).

At first glance, it seems reasonable to pad with random data, since this should help to obscure the data in the block. This idea can be extended: Instead of completely filling each block (except the last) with message data, each block can instead be partially filled with plaintext data and then padded with random data [22]. Naturally, this causes some ciphertext expansion, but the random data should help to dilute the remaining bit statistics, and bit statistics seem to be the only statistics left.

But instead of just hoping that the random data will
smooth out the bit statistics, steps can be taken to guarantee this
result. In particular, the number of one-bits and zero-bits in the
plaintext data can actually be counted. Then the message can be
extended (or a block filled out) with non-random data so as to
balance the bit distribution *exactly*. (Of course we might
deliberately vary the bit-balance somewhat from block to block.)
After bit-shuffling the extended message, there seems to be very
little statistical frequency information left: no word statistics, no
letter statistics, and no bit statistics. If some statistical
relationship remains which might assist in entry, it is certainly
not clear what that might be.

With data balancing, the best possible situation for a
transposition cipher can be *guaranteed*. Blocks which might
be all ones or all zeros can be balanced and enciphered in a
strong way; without balancing, it would be impossible for
transposition to
provide any effective enciphering of such blocks. And, while the
normal block (not heavily weighted one way or the other) may not
seem to need additional strength, such blocks also require only a
minimum amount of balancing.

Bit-balancing does cause some ciphertext expansion (perhaps 25% to 33% on text files). Naturally, this expansion could be mostly eliminated if the input data had an even bit distribution, and a good distribution might be enforced by passing the data through a Vernam system before transposition. Alternately, modern data compression processing can reduce the size of typical text files by an amazing 60% while simultaneously improving their value distribution. Subsequent expansion due to final bit-balancing should be less than 10% of the resulting smaller file. Thus, if data expansion is a problem, that problem can be managed (at some expense); in many cases, a modest amount of data expansion is not a problem.

The fact that the strength of the transposition can now be guaranteed, independent of the input data, is very significant. Without such a guarantee, it might be necessary to monitor the input to a transposition module and make special provisions for alternate ciphering when strongly-unbalanced data are encountered. With a guarantee of strength, the transposition module can stand alone and handle any arbitrary data sequence before passing it along to another module.

Bit-balancing also provides the basis for an analysis of the strength of the resulting cipher. Since every block is to be balanced, each block should have the same permutation possibilities: one permutation is correct, others are incorrect but still decipher the block, and others are simply incorrect.

When working with blocks, there is some difficulty deciding how much space to leave for bit-balancing. A good distribution might need only a little extra data to achieve an exact balance, but some plaintext sequences might be all ones or all zeros, and those would require as much balancing data as plaintext data.

By counting data bits while filling the block, we need only
leave space for exactly the number of bytes needed for bit-
compensation. But there must be some way to isolate and remove
the bit-compensation when deciphering. One way might be to
enter bit-compensation data, of the least-used bit type (all-zeros
or all-ones bytes), backwards from the end of the block. This
continues until the bit counts are within a byte of balance. Then
exact balance can be achieved with a single byte containing at
least one bit of the most-used bit type. Because the previous
balancing bytes have contained only the least-used bit type, the
last balancing byte is a *contrasting* byte.

This means that the first byte (from the far end) that is a
contrasting value is also the identifiable last byte (from the far
end) of the bit-compensation data. Thus, the bit-compensation
area can be as large or small as needed, and there need be no
special code or count to delimit it. Moreover, all but one of the
bits of the minimum two balancing bytes can participate in
balancing. Since most data distributions will need at least two
balancing bytes anyway, the average overhead for defining the
balancing data area (beyond that required for simple balancing)
would seem to be *less than one byte*. The same technique
can be applied to huge or dynamically-variable blocks, and some
added computation can produce similar results for complete message
permutations.

All fixed-size-block ciphers which support variable-length data need a mechanism for padding the last block. But if bit- compensation is already supported, it is possible to bit-balance the filled portion of the last block, and then complete the block with particular bit-balanced byte values. After deciphering, proceeding from the end of the block, all the particular bit-balanced byte values can be skipped. Then, if there are all-ones or all-zeros bytes they can also be skipped, along with the next byte (which is the contrasting byte). In this way, the same mechanism which is used to delimit the bit-compensation can also remove the padding at little or no extra cost.

For a modest block of 512 bytes by 8 bits (the size of a single MSDOS logical disk sector) the block size is 4096 bits. (In actuality there will be a minimum of two balance bytes, so there will be at most 4080 data bits, and may actually be many less.) Assuming an even bit distribution (which we can now enforce), there are (2048!)(2048!) decipherings out of 4096! possible permutations. In logs, ln(2048!) = 13571.95, and ln(4096!) = 29978.65; so there are about e^29979 or 2^43250 possible permutations, a 43251-bit binary value, and only one of these permutations is "correct." (In ordinary terms, "many" other permutations would be "readably close," but in comparison to numbers like these, these possibilities pale to insignificance.)

The total number of deciphering permutations is e^27143 or 2^39160, a 39161-bit binary value; so finding the one correct permutation would seem to be a difficult task. And the average number of sequences which create any particular permutation is e^4091 or 2^5902, a 5903-bit binary value. Of course, instead of 1/2 K (byte) blocks, we might well do entire files of 10K, 100K, or perhaps even 350K in length.

These probability calculations have a strange other-world character to them. While the results do imply a sort of fundamental secrecy for the dynamic transposition mechanism itself, they do not imply that a cipher using this mechanism is necessarily secure; any cipher is only as secure as its weakest link. Basically, these results are useful only to say that an exhaustive search of permutations and sequences, for even a modest (correctly constructed) block, is completely out of the question. Then, if no other part of the cipher has an easy "shortcut" attack [21, p. 137], the cipher may be secure in practice.

A simple cipher module like this actually may be much more valuable than a complex one, for it may eventually be possible to understand its exact limitations, and then answer those limitations completely in other modules. Although it is elegant to have a single complex framework handle all aspects of secrecy, such systems usually cannot be completely understood in a deep way. For example, there has been suspicion of a DES "backdoor" for over a decade, and great strides have been made in factoring large numbers like those used in RSA. A reasonable alternative is the selection of simple mechanisms which can be deeply understood.

Note that a shuffle permutation of a 512-byte block requires 512 12-bit pseudo-random values. Thus, to encipher 4096 bits we need 49,152 pseudo-random bits, for a "key stream" expansion of 12:1. Since a Vernam cipher needs only a single random bit to encipher each data bit, shuffling dynamic transposition is seen to be relatively demanding of the random- number resource. But the expansion of this resource may be only a small part of the cost of a complete cryptosystem, and what it buys, hopefully, is cryptographic strength.

When transposing bit-balanced fixed-size blocks--each of
exactly the same length and with exactly the same number of
one-bits and zero-bits--in some sense
*there is only one block*, and
all of our different ciphertext blocks are only permutations of that
same aboriginal balanced block. Moreover, all of the
bit-compensated plaintext blocks and
*all possible decipherings* are
just other permutations of that same primitive block. Various
decipherings include all the possible bit-balanced messages which
will fit in the block, including a huge number of cases in which
the messages differ only in their crucial words. There would seem
to be no way for a cryptanalyst to distinguish the correct message
from all possible decipherings. So brute-force methods would
seem to be useless, as well as impractical.

The dynamic transposition combiner may be considered to
be a *black box*, with two input data ports ("Data In" and
"Random In"), and one output port ("Combiner Out"). Because the
block size can vary, the "Random In" range must also vary.
Evidently the mechanism inside the box in some way combines the
two input streams to produce the output stream. It seems
reasonable to analyze the output statistically, for various
input streams.

For these tests, the "Data In" stream was a sizable text file (a book chapter) with all spaces and punctuation deleted, and lower case converted to upper, leaving a 26-element alphabet of 18,135 capital letters.

The black box test results can be summarized in the form of standard "delta IC" [20], and "Z-coefficient" [7, 17] computations. In both cases, we count the number of occurrences of each element value in the stream being analyzed.

The index of coincidence (IC) is conceptually "the sum of the squares" (of the element counts) "over the square of the sum" (or total count); the IC is normalized to a delta IC by multiplying by the size of the alphabet. A delta IC value of 1.0 indicates a random distribution.

A Phi value is conceptually "the sum of the squares of the element counts," and an "expected" value of Phi and a statistical variance value can be derived for a random data stream. The Z-coefficient is just the difference between the actual and expected Phi values, normalized by dividing by the variance. A value of 0 would be expected, and a value between -2 and 2 would be most probable for a random sequence.

The results are summarized in Table 1.

Table 1. TRANSPOSITION DISTRIBUTION STATISTICS (delta IC / Z-coefficient) Data In Random In Combiner Out The Data are 26-Letter Text Byte Transposition 1.66 / 1684 1.00 / -0.9 1.61 / 1593 Bit Transposition 1.66 / 1684 1.00 / 1.8 1.32 / 257.5 Bit Balanced Trans. 1.66 / 1684 1.00 / 0.8 1.00 / -0.2 The Data are One Value Repeated Bit Balanced Trans. 26.0 / 36199 1.00 / 1.0 1.00 / 0.8

Apparently the bit-balanced bit transposition creates output with good random characteristics, even when the data input is just a repeated constant value. (If the data input is random, then clearly the resulting block must also be random, even if the random input is a constant value.)

In general, a cryptographic combiner can be expected only to increase (albeit greatly) the complexity of a cryptanalysis. Nevertheless, bit-balanced dynamic bit-transposition seems to have some interesting characteristics.

If a bit-balanced ciphertext block carries information, it does
so only in its bit arrangement, and any bit-balanced block can
obviously be re-arranged into any other. Since any message we can
possibly encipher must produce one or more bit-balanced ciphertext
blocks, any ciphertext block can obviously be re-arranged into any
part of any possible message; all except one of these is a
meaningful false solution, or "spurious message decipherment"
[13, p. 290].
Hellman defines the number of spurious message decipherments as
*nm*, and writes: "If *nm* takes on large values with
probability close to one, then the system will be secure even if
the cryptanalyst is allowed unlimited computation." A cryptanalyst
would seem to be unable to tell which of all possible message
blocks was sent.

Enciphering a block with bit-shuffling implies the existence of some sort of confusion sequence which may itself be penetrated; if the confusion sequence could be analyzed and replicated, the cipher would be broken. In mounting such an attack, the cryptanalyst's first problem would be to determine the correct deciphering permutation. Even an exact copy of the original plaintext block would seem to be of little help: There are a multitude of deciphering-but-incorrect permutations (too many to try them all), with apparently no way to identify the correct one. (Hellman calls this "spurious key decipherment.") The cryptanalyst's next problem would be to identify the particular confusion sequence which produced the known permutation. But since the shuffle process could produce any particular permutation from a host of different confusion sequences, there would seem to be no way to identify the one original confusion sequence so that it might be analyzed. (This would seem to be another level of "spurious key.")

Shannon
[25, p. 680],
defines *PM(E)* as the conditional probability of ciphertext
(block) *E* if message block *M* is chosen, and
*P(E)* as the probability of obtaining ciphertext *E*
from any cause. If the selected permutation process does indeed
map an arbitrary (balanced) block to every possible (balanced)
block, it certainly seems plausible that *PM(E) = P(E)*,
which is a necessary and sufficient condition for perfect secrecy.
That is, if any message block could generate any ciphertext block
with about equal probability, then the probability of obtaining
any particular ciphertext block cannot depend on the message;
Shannon writes, "*PM(E)* must be independent of *M*."

An implication of this is that "the number of different keys is
at least as great as the number of *M*'s." In this analysis,
the number of "keys" is the number of possible permutations, or
*n!*
(for an
*n*-bit block),
and the number of possible messages (blocks) is under
*2^n*,
which is far less. It appears that this does not necessarily imply
that the number of user-keys must be
*n!*,
or even
*2^n*,
because the confusion sequence is isolated by the strength of the
dynamic transposition mechanism. But, as always, the number of
user-keys must be sufficient to prevent a key-search attack.

Of course, a fully-detailed strength analysis probably depends upon a deeper understanding of the shuffle process. Of particular interest is the effect of the confusion sequence on permutation distribution. But the simplicity and intuitive generality of shuffling would seem to bode well for such an analysis, and shuffling is just the basis for this particular form of dynamic transposition.

One use for dynamic transposition would be as a
*combining* or *mixing* function for data blocks.
With some stream-to-block
conversion, and vice versa, such a combiner could be used to replace
the exclusive-OR logic function in a Vernam stream cipher.
Alternately, it could be used to combine two pseudo-random
sequences, to produce an even more complex sequence. Or it could
be applied in a product cipher
[25]
as one part of a chain or network of cipher operations.

Dynamic transposition may be slower, but perhaps also more secure than some other alternatives. Consequently, it might well be used for key delivery as opposed to general data encipherment.

Transposition--normally difficult to apply and potentially insecure--becomes substantially stronger when transposing bits within bit-balanced blocks, and driven with a pseudo-random sequence. Dynamic transposition combiners seem very protective of their pseudo-random sequence (a significant problem with a Vernam [27] combiner), can frustrate a statistical frequency-analysis of the ciphertext, and can guarantee strong mixing performance even with an input of unbalanced plaintext distributions.

My thanks to the referees, whose questions about the utility of this mechanism led to the inclusion of material on numerical and theoretical secrecy, and to Edward Rupp for conversations about potential attacks.

1. Beker, H. and F. Piper. 1982. *Cipher Systems.*
New York: John Wiley & Sons.

2. Beker, H. and F. Piper. 1985. *Secure Speech
Communications.* London/Orlando: Academic Press.

3. Costas, J. 1981. The Hand-Held Calculator as a Cryptographic
Machine. *Cryptologia.* 5:94 - 117.

4. Costas, J. 1981. Letter to the Editor. *Cryptologia.*
5:210-212.

5. Davies, D. and W. Price. 1984. *Security for Computer
Networks.* New York: John Wiley & Sons.

6. Deavours, C, D. Kahn, L. Kruh, G. Mellen, and B. Winkle. 1987.
*Cryptology Yesterday, Today, and Tomorrow.* Norwood, Mass:
Artech House.

7. Deavours, C. 1987. *Cryptanalytic Programs for the
IBM PC.* Laguna Hills, CA: Aegean Park Press.

8. Denning, D. 1982. *Cryptography and Data Security.*
Reading, Mass: Addison-Wesley.

9. Diffie, W. and M. Hellman. 1979. Privacy and Authentication:
An Introduction to Cryptography. *Proceedings of the IEEE.*
67: 397-427.

10. Durstenfeld, R. 1964. Algorithm 235, Random Permutation,
Procedure SHUFFLE. *Communications of the ACM.* 7: 420.

11. Feistel, H. 1973. Cryptography and Computer Privacy.
*Scientific American.* 228: 15-23.

12. Gaines, H. 1956 (original 1939). *Cryptanalysis.*
New York: Dover Publications.

13. Hellman, M. 1977. An Extension of the Shannon Theory Approach
to Cryptography. *IEEE Transactions on Information Theory.*
IT23: 289-294.

14. Kahn, D. 1967. *The Codebreakers.* New York: Macmillan.

15. Klingler, L. 1981. Letter to the Editor. *Cryptologia.*
5:209-210.

16. Knuth, D. 1981. *The Art of Computer Programming,*
Vol. 2, *Seminumerical Algorithms.* 2nd ed. Reading, Mass:
Addison-Wesley.

17. Kullback, S. 1976 (original 1938). *Statistical Methods in
Cryptanalysis.* Laguna Hills, CA: Aegean Park Press.

18. Massey, J. 1988. An Introduction to Contemporary Cryptology.
*Proceedings of the IEEE.* 76: 533-549.

19. Mellen, G. 1973. Cryptology, computers, and common sense.
*Proceedings of the National Computer Conference.*
42: 569-579.

20. Mellen, G. 1983. Cryptanalysts' Corner. *Cryptologia.*
7: 371.

21. Meyer, C. and S. Matyas. 1982. *Cryptography: A New
Dimension in Data Security.* New York: John Wiley & Sons.

22. Michener, J. 1985. The "Generalized Rotor" Cryptographic
Operator and Some of Its Applications. *Cryptologia.*
9: 97-113.

23. Pfleeger, C. 1989. *Security in Computing.*
Englewood Cliffs, New Jersey: Prentice Hall.

24. Rubin, F. 1987. Foiling An Exhaustive Key-Search Attack.
*Cryptologia.* 11: 102-107.

25. Shannon, C. 1949. Communication Theory of Secrecy Systems.
*Bell System Technical Journal.* 28: 656-715.

26. Sinkov, A. 1966. *Elementary Cryptanalysis.*
Washington, DC: The Mathematical Association of America.

27. Vernam, G. 1926. Cipher Printing Telegraph Systems.
*Transactions of the AIEE.* 45: 295-301.

Terry Ritter is a registered Professional Engineer, a member of IEEE and ACM, with a background in computer architecture, hardware, and software. He has enjoyed spending the past few years being Blue Jean Software and Blue Jean Computer Engineering.