I got this from PRZ (as in PGP) [Note: see ripem.msu.edu:/pub/crypt/other for source+binary] WARLOCK - A New Matrix-based Paradigm for Public Key Cryptography (C) 1993 by William J. Wilson and C. Larry Craig 1. INTRODUCTION The following narrative briefly reviews the functionality of contemporary private key and public key (PK) cryptosystems in meeting current and future private sector security needs. To assist in meeting these needs, the WARLOCK paradigm for achieving matrix-based PK cryptosystems is presented and explained. Sys- tems based on this paradigm are designed as alternatives to RSA and RSA-hybrid systems by making available single, high-speed, full bandwidth systems capable of the basic cryptographic func- tions of encryption, decryption, and source authentication (digital signature). The WARLOCK paradigm is outlined in the following paragraphs with actual examples of system keys and step-by-step encryption, decryption, and authentications transformations effected by those keys. User evaluations, comments and suggestions are solicited on the WARLOCK paradigm as well as the particular WARLOCK 4.0 PC imple- mentation (available in C++ source code from file WARLOCK.CPP and in MS DOS executable code as WARLOCK.EXE). Please direct such input to WARLOCK@ACM.org or Datasec Systems, PO Box 4152, Hunts- ville AL 35815-4152, or by calling Wilson at (205) 881-8002. User suggestions and improvements will be incorporated, as appro- priate, and improved versions (as well as other implementations of the WARLOCK paradigm) will made available to interested users in the future. ***************************************************************** WARNING: The WARLOCK cryptosystem provided herein is a copy- righted system protected by patents (awarded and pending) and is provided solely for private personal use and evaluation only. Modifications to (or copies of) WARLOCK source or executable programs must retain the warning and proprietary legend displayed on the first user screen. The use of WARLOCK cryptosystems for private-sector commercial or public-sector governmental purposes is strictly prohibited with- out proper licensing arrangements. Licensing information can be obtained from the above-noted sources. ***************************************************************** 2. BACKGROUND Today's telecommunications and information system designers contemplating cryptographic technology are confronted with a relatively limited set of choices and capabilities (e.g. DES, RSA, proposed NIST DSS (Digital Signature Standard), etc.) which, even when combined in hybrid systems, are inadequate in our opinion to the complex security and authentication needs of the burgeoning information age and the even more daunting require- ments of the emerging digital multimedia revolution. For exam- ple, the NIST DSS and RSA systems suffice for authentication but are too slow for ordinary encryption/decryption functions forcing users to employ more complicated hybrid systems resulting in "double exposure". Hybrid systems typically use the DES standard which has been widely assailed for its all-too-short key length (56 bits). Nor has the proposed NIST standard met with a warm reception either since it presently provides only a time-consum- ing signature capability. In terms of variety, flexibility, speed, and selectable and provable levels of security, we feel that contemporary cryptosystems fall short of efficiently meeting the wide range of known and predicted private sector application security needs, e.g. encrypted digital voice and video, digital satellite communication, ISDN, wireless LAN's, source authentica- tion, IFF (Interrogate Friend or Foe) protocols, smart cards, and a host of other emerging applications. To meet these needs, the authors over the past several years have developed and tested scores of high-speed matrix-based PK crypto- systems beginning with a patented private-key version of the Hill cipher and culminating in the development of the WARLOCK family of PK cryptosystems. Our goal throughout has been the attainment of a single, full-bandwidth PK cryptosystem paradigm (with digi- tal signature) of sufficient simplicity, speed, and selectable levels of security for meeting current and expected cryptographic needs of the private sector. 3. THE HILL PARADIGM In 1929 Lester H. Hill proposed a unique, matrix-based, block ciphering system (1.) unlike any ever proposed before. Although manifestly linear and later shown to be susceptible of chosen plaintext attack, Hill's system represented a quantum leap in the art of cryptography providing for the first time a true block ciphering capability with strengths substantially beyond those of the polyalphabetic systems of his day. If fact, if computing (but not creating) the inverse of a matrix were as difficult as computing its permanent, Hill would have invented in a single stroke the first provably secure public key cryptosystem complete with digital signature. Notwithstanding, Hill's method, employ- ing standard matrix transformations, established a new direction whose full cryptographic potential in our opinion is still unrealized and one capable of nullifying in large measure the standard tools of conventional cryptanalysis. Apart from the issue of cryptographic strength, Hill succeeded in inventing the first two-key cryptosystem and it remained only for Hellman and Diffie to establish a rigorous mathematical paradigm (2.) for one-way, two-key public key cryptosystems and for Rivest et al. to provide the first viable example of such a system (3.). In a later development, McEliece developed a matrix-based public key system (4.) based on Goppa error correction codes. Although inefficient in terms of bandwidth and initially lacking digital signature, his system demonstrated that workable matrix-based PK systems were indeed possible. In spite of the fact that the McEliece system was recently cryptanalyzed (5.), it nevertheless represented a significant step in the evolution of matrix-based cryptosystems. Still later, Rodney Cooper extended Hill's mod 26 systems to Galois Fields GF(p) and GF(q^n) to create a cryptosystem based on matrix theory and Galois Fields (6). In essence, Cooper provided for a matrix of polynomials (subject to two moduli) to be used as an encryption key with the paramount advantage that such ma- trices can be made as large as needed to accommodate any required level of user security. In fact, Patti (7.) has implemented such extensible multi-magabit cryptokeys in PC-based extended memory in which he also concatenates random bits with the plaintext vector prior to encryption to defeat linear attacks (cited in the above reference) as well as known-plaintext and chosen-plaintext attack. Rather than trying to impress a known NP-hard problem into the service of PK cryptography as others such as Merkle et al. (8.) have attempted, we have employed a two-step process instead. In the first step, we developed weak but workable full-bandwidth PK systems with digital signature capability. In the second step, we hardened the resulting system by incorporating artificial com- plexities in the key generation, encryption, and decryption processes with the goal of attaining selectable and provable levels of security -- ideally NP-hard. Payne and McMillen's formula (9.) defines the number of nonsingu- lar nxn binary matrices possible for each dimension of n and thereby the number of reversible linear mappings of n-bit strings possible with such matrices. It is worth noting that such map- pings are a tiny subset of the full range of (2**n)! possible mappings of unique n-bit values. Unfortunately, as Chaitin has noted in another context (10.), all but a small fraction of these mappings are essentially noncomputable and can be effected only by table lookup -- as the small S-box mechanisms of DES exempli- fy. For the WARLOCK paradigm, one of the required private keys consists of a large, non-singular nxn matrix used to disguise the rectangular mxn public key. In the implementation provided here, a smaller nonsingular nxn private key matrix is also required. In the paragraphs that follow, the term "matrix" always refers to a binary matrix and all forms of the term "addition" indicated by the + symbol designate addition modulo-two (XOR operation). Supporting figures for the WARLOCK paradigm and the particular implementation are all found at the end of the paper. 4. THE WARLOCK PARADIGM Overview WARLOCK is a paradigm for a family of advanced, high-speed, full- bandwidth, matrix-based PK cryptosystems with full digital signa- ture. These systems can be operated in ordinary encryption/de- cryption mode or in superencrypted mode, (achieving encryption and authentication simultaneously) as necessary with key and block sizes incrementally selectable according to security needs. All implementations of the WARLOCK paradigm share certain common- alities: - use of a single public key K consisting of a rectangular mxn binary matrix where m>n and where n is the system block size of plaintext and ciphertext - achievement of nonlinear plaintext to ciphertext mappings such that for plaintexts A and B under key K, the follow ing is true: MAP(A,K) + MAP(B,K) <> MAP(A+B). - incorporation of secret "row identifiers" in rows of the public key (which are injected in disguised form into the ciphertext by the encryption process) allowing a private key holder to identify public key rows selected by the encryption process. - use of entropy increasing "noise bits" for selected bit positions of the public key not occupied by row identifiers - use of a secret, nonsingular nxn matrix M to disguise the public key and to serve (in inverse form) as a private key - user-selectable key and system block sizes to accommodate varying levels of security requirements - system key generation from user-supplied "key-seeds" or pass phrases of 1 to 85 bytes As the example below shows, the public key for the implementation provided here is initially constructed of two parts -- an A-part and a B-part. The A-part consists of a key-seed generated and triplicated nxn nonsingular matrix whose n dimension is exactly 1/3 the row dimension of the public key. Construction of the B-part begins with a template matrix (T- matrix) containing a diagonal of submatrices each comprised of "row identifiers" whose value and row positions uniquely identify each matrix row. In the first hardening step, the area above the diagonal is filled with key-seed generated "noise bits" and the area below the diagonal is filled with "replacement bits" con- sisting of key-seed generated but replicated row values. The A- part and the B-part are concatenated to form an mxn matrix where m<n. This matrix is then disguised by being multiplied by a secret invertible nxn matrix_M whose inverse later serves as a private key. The result is then jumbled by row groups and (optionally) rows within row groups to create a single mxn public key K where m>n and where n is the block size of both the input plaintext and the resulting ciphertext. The purpose of row group jumbling is to disguise the original A-part and B-part row group sequence. WARLOCK encryption is accomplished by expanding an n-bit plain- text block in a nonlinear manner to form an m-bit vector which is multiplied by the public key to create an n-bit ciphertext. This multiplication is greatly hastened (as are all binary matrix multiplications) by the simple expedient of associating each bit position of the expanded vector with a row of K allowing 1-bits in the expanded plaintext vector to select corresponding rows of K which are added modulo two to produce the plaintext. In the first step of the decryption process, the ciphertext is multiplied by private key M_inverse to create the same value as if the plaintext had been multiplied by the completed T-matrix. Rows selected by the encryption process (whose row identifiers are encoded in the ciphertext) are then retrieved by a deconvolu- tion process which removes the effects of the noise bits identi- fied in the private key T-matrix. Accomplishing the inverse of the row selection process employed during encryption serves to identify the original plaintext. Like most computer-based cryptosystems, WARLOCK consists of three basic modules: a key generation module, an encryption module, and a decryption module. Digital signatures (as well as superencryp- tion) are accomplished conventionally by concatenating decryption and encryption functions employing appropriate public and private keys. WARLOCK Key Generation The WARLOCK T matrix is comprised of two major parts: an A-part and a B-part. The A-part consists of a triplicated and expanded nonsingular A matrix as shown in Figures 1. through 3. and the B- part consists of a set of rows each containing a unique 3-bit row identifiers as shown in Figure 5. Note that the triplicated rows of the A part when selected always produce a "fat bit" consisting of 000 or 111. These "fat bits" when combined with the row identifiers of the B-part in the encryption process either pre- serve the row identifier value or complement it with the result that identifiers are recovered in original or complemented form. For example, a row identifier 100 in a given ciphertext row position will be recovered either as 100 or as its complement 011 -- both identifying a particular B-part row selected in the encryption process. Row identifier values for the B-Part are chosen as shown below such that their values and their comple- ments form a unique set of unduplicated values allowing unambigu- ous row identification. 4-let Row Identifier Row Identifier Complement 1 100 011 2 010 101 3 001 110 4 111 000 In the encryption process, an information containing fat bit from the A-part consisting of 000 or 111 is always added to each 3-bit identifier value selected in the B-part. This technique not only preserves identification of the B-part row selected, but permits identification of the value of the information carrying fat bit as well. In other words, if a row identifier is recovered un- changed, its fat bit is known to be 000 otherwise its fat bit is known to be 111. Since the selection of fat bits is also deter- mined by plaintext values, fat bits are also information carry- ing. |----------| | | | B-part | | | |__________| | A-Part | |__________| WARLOCK T-matrix The A-part of the WARLOCK T-matrix is created as follows. A key- seed generated, nonsingular nxn matrix A (whose n dimension is exactly 1/3 the width of the T-matrix) and its inverse A_inverse is initially created as shown in Figures 1. and 2. The A-matrix is then triplicated to create the matrix shown in Fig. 3. As al- ready noted, triplication of the columns of matrix A produces the fat bits required by the encryption process. In the next step, shown in Fig. 4., the matrix row dimension is increased by adding each row pair of the matrix in Fig. 3. to create a third row. A fourth all-zero row is then created completing the row expansion. This last step is necessary to create A-part row groups (4-lets) that allow the row selection process (governed by plaintext values) to be identical for both the A-part and the B-part. Construction of the B-part of the T-matrix begins with an initial template containing row identifiers as shown in Figure 5. In the first hardening step, key-seed generated noise bits are added above the submatrix diagonal to produce the intermediate version shown in Figure 6. In the next step, the A-part and the B-part are joined to form a single T-matrix shown in Figure 7. To eliminate the "sea of zeroes" under the diagonal of the B-part (and to further disguise the T-matrix), a special "replacement bit or R-bit" matrix shown in Figure 8. is created with row values identical for each row 4-let. This matrix is added to the matrix in Figure 7. to produce the final T-matrix shown in Fig. 9. Not only does this step eliminate the "sea of zeroes" under the diagonal, but it also displaces and further disguises all other bits in the T-matrix. If the set of unique replacement row values in the R-matrix has been initially selected to sum to zero, the replacement row values vanish in the encryption proc- ess; otherwise their sum must be removed from the ciphertext as a special step in the decryption process. In the penultimate step of key generation, the T-matrix is multi- plied by the M-matrix in Figure 10. to produce the public key K- matrix shown in Figure 12. In the final step, this key is then key-seed jumbled in two ways: in four row groups (4-lets) and (optionally) by rows within groups. In the example below 4-lets are jumbled as follows: From To 4-let 4-let 6 1 4 2 1 3 2 4 3 5 5 6 WARLOCK Encryption Process The first encryption step consists of expanding the input plain- text block of n-bits (K-matrix column dimension) to a bit vector of m-bits (K-matrix row dimension) in accordance with the trans- lation table below. In the second and final step, this vector is then multiplied as a column vector by public key K to produce the ciphertext. Alternatively, the plaintext bit values could simply select the applicable rows of K directly as mentioned above and add them together. Expanded Plaintext Plaintext 2-bit Seg- Vector ment Segment 00 0001 01 1000 10 0100 11 0010 WARLOCK Decryption Process Decryption is a multi-step process. In the first step, the ciphertext is multiplied by private key M_inverse to produce an "unmasked version" having the same value as if the expanded plaintext had been multiplied by the T-matrix. In the second step, row identifiers of the B-part are recovered beginning with the leftmost row identifier which is always recov- ered in undisguised or complementary form (since it has not been altered by noise bits). The noise bits associated with this identifier row can now be identified using T-matrix private key information and removed from the ciphertext revealing the next leftmost row identifier in the same manner. This process is repeated iteratively until all row identifiers have been identi- fied -- in their original or complemented form. Each identifier value, thus recovered, unequivocally identifies an applicable 4- bit sector of the invoking expanded plaintext vector which, in turn, identifies a 2-bit sector of the plaintext. In addition, each recovered row identifier identifies its associated fat bit value as 000 or 111. When all row identifiers have been recovered, 2/3 of the plain- text has been decrypted. The remaining 1/3 can now be decrypted by examining fat bit values derived from the recovered identifier values themselves, i.e. for unchanged row identifiers, the ap- plicable fat bit = 000; otherwise the applicable fat bit = 111. When all fat bits have been identified, they are reduced from 3 bits to 1 bit and concatenated to form a value which is multi- plied by private key A_inverse (in Fig. 2.) to recover the re- maining 1/3 of the plaintext. In the final step of decryption, the full set of 2-bit plaintext segments are unjumbled to reverse the effects of the row 4-let jumbling of the public key. 7. WARLOCK 4.0 MANUAL EXAMPLE As an example of WARLOCK 4.0 operation, the WARLOCK 4.0 crypto- graphic keys shown in Figures 6., 11., and 12. may be used to manually encrypt and decrypt 12-bit inputs and to create and verify 12-bit digital signatures as desired. For example, to encrypt plain_text P = 001110000110 using pub- lic_key_K shown in Figure 12., accomplish the following steps: Expand plain_text P to expanded_text 000100100100000110000100. Select and add rows of public_key_K under control of 1-bits in expanded_text to produce encrypted_text as follows: bit 4 selects row 4 of K = 101000100001 bit 7 selects row 7 of K = 011110010011 bit 10 selects row 10 of K = 110011110001 bit 16 selects row 16 of K = 011000001000 bit 17 selects row 17 of K = 000010100101 bit 22 selects row 22 of K = 001001110001 encrypted_text = 010110011111 To facilitate understanding of the more complex decryption proce- dure detailed below, the following reference table is provided which relates row identifier values (as recovered) to the follow- ing necessary information: (1) row position selected within each row 4-let (2) selecting 2-bit plaintext values and (3) applicable fat bit values. Row Row Identi- Selected Selecting Associated fier Value within Plaintext Fat Bit (as recovered 4-let Value Value 100 1 01 000 011 1 01 111 010 2 10 000 101 2 10 111 001 3 11 000 110 3 11 111 000 4 00 000 111 4 00 111 The following steps detail the decryption process: A. Multiply encrypted_text 010110011111 by private key key_M_inverse shown in Figure 11. to create the initial value of reverted_text 100101101111. Note that the leftmost row identifier in bit positions 1, 5, and 9 is unaffected by noise bits and is seen to have the value 101 indicating that row 2 of the applica- ble 4-let of the public key was chosen. Accordingly, 1. Initialize the value of resultant_text with the first 2 recovered plaintext bit values, e.g. resultant_text 10. 2. Create the first iteration of intermediate_text by remov- ing from reverted_text the noise bits associated with row 2 of private key key_T_with_noise by XORing subject row 2 with the reverted_text to produce the first intermediate_text value as follows: 100101101111 (reverted_text) 011010010000 (row 2 template and noise bit values) 111111111111 (intermediate_text) This step also records the fat bits in positions 1, 5, and 9. of the intermediate_text and the reduced fat bit in position 1. B. Note that the value of the row identifier in bits 2, 6, and 10 "uncovered" by the previous step is seen to be 111 indicating that row position 4 of its respective 4-let was selected and further indicating an invoking plaintext value of 00 and an associated fat bit value of 000. Accordingly, 1. Append recovered plaintext bits 00 to the current result- ant_text value giving new resultant_text 1000. 2. Remove from the current intermediate_text value the noise bits associated with applicable row 4 of key_T_with_noise_bits by XORing subject row 4 with intermediate_text to produce a new intermediate_text value as follows: 111111111111 (current intermediate_text) 010101110110 (row 4 template and noise bit values) 101010001001 (new intermediate_text) This step also records the reduced fat bits in positions 1 and 2 of the new intermediate_text. C. The value of the third row identifier (bits 3, 7, and 11) uncovered by the previous step is seen to be 100 indicating that row 1 of its respective 4-let was invoked by a plaintext value of 01 and that its associated fat bit value is 000. Accordingly, 1. Append the recovered plaintext bits 01 to the current re- sultant_text value giving 10000. 2. Remove from the intermediate_text the noise bits associ- ated with row position 1 of private key key_T_with_noise_bits by XORing subject row 1 with the current intermediate_text to pro- duce a new intermediate_text value as follows: 101010001001 (current intermediate_text) 001000000000 (row 1 template and noise bit values) 100010001001 (new intermediate_text) This step also records the reduced fat bits in positions 1, 2, and 3 of the new intermediate_text. D. The fourth and final row identifier (bit positions 4, 8, and 12) uncovered by the previous step is seen to be 001 indicating that row 3 was selected by a plaintext value of 11 and that its associated fat bit value is 000. Accordingly, 1. Append recovered plaintext bits 11 to current resultant_text value giving 10000111. 2. Remove from the current intermediate_text value the noise bits associated with row position 3 of the subject 4-let of key_T_with_noise_bits by XORing row 3 with the current intermedi- ate_text to produce a new intermediate_text_value as follows: 100010001001 (current intermediate_text) 000000000001 (row 3 template value) 100010001000 (new intermediate_text) This step also records the final reduced fat bit in position 4 of the new intermediate_text whose current value is now seen to be 1000. D. This completed intermediate_text value 1000 will be multiplied by private key A_inverse to recover the final plaintext values (originally encoded by the A-part of the public key) as follows: 1000 x A_inverse = 1000 The recovered plaintext value 1000 is then appended to the cur- rent value of resultant_text to produce resultant_text = 100001111000. J. The completed resultant_text value 100001111000 (now seen to be a 2-bit permutation of the original plaintext) must now be unjumbled in the final decryption step by reversing the row jumbling accomplished in the last step of the key generation process (described on page 7.) as follows: Source Bit Desti- Destination Source Pair Position nation Bit Pair Position Bit Pair (resultant_ Bit Pair (decrypted_ Number text)/(value) Number text)/(value) 6 11-12 (00) 1 1-2 (00) 4 7-8 (11) 2 3-4 (11) 1 1-2 (10) 3 5-6 (10) 3 3-4 (00) 4 7-8 (00) 2 5-6 (01) 5 9-10 (01) 5 9-10 (10) 6 11-12 (10) This final permutation step produces the sought plaintext value 001110000110 completing the decryption process. Source Authentication and Superencryption To create a source authentication value S (for source authentica- tion purposes) represented by any selected 12-bit value, S must first be "decrypted" by the decryption module by the steps noted in the foregoing paragraphs to create signature value S*. When submitted to the encryption module for validation, S* produces the sought value S thereby proving unequivocally that S emanated from the private key holder. Because of the relatively high encryption and decryption speeds of WARLOCK 4.0, Alice and Bob may choose for purposes of enhanced security to exchange messages that are simultaneously encrypted and authenticated. To accomplish this, Alice and Bob first obtain each others public keys. In encrypting messages for Bob, Alice accomplishes the following: 1. Alice first "decrypts" each plaintext block using her private key to create an "authenticated version" of the plaintext. She then encrypts this version by Bob's public key to create a final ciphertext block which she transmits to Bob. 2. Bob first decrypts the ciphertext block by his private key recovering the "authenticated version". He then transforms this version to Alice's original plaintext by "encrypting" it with Alice's public key thus proving Alice to be the originator of the plaintext since she is the only holder of the private key. In encrypting messages for Alice, Bob follows the same procedure with the appropriate public and private keys. 8. SEEDING THE WARLOCK KEY GENERATION FUNCTION A basic desideratum of classic private key cryptosystems was easily generated and memorized keys to avoid a possibly compro- mising (or incriminating) recording of the key. This desideratum has all but vanished with DES and the advent of PK systems. Who, for example, can remember a thousand-bit RSA modulus or its constituent primes. Nevertheless, there are many occasions where one would not wish to transport private keys to a new operating locations, but regenerate them at their new location, use them, and destroy them. Such a capability is available through the unique WARLOCK key seeding feature which allows users to seed the key generation process with a user secret key-seed (or pass phrase) of 1 to 85 bytes (8 to 680 bits). Such a feature is typically absent from number theoretic cryptosystems such as RSA and the NIST DSS. With the WARLOCK key seeding feature, users can establish simple mnemonic seeding tokens or create elaborate- ly structured key-seeds as needed. Key seeding also facilitates the use of WARLOCK as a stream cipher where Bob and Alice at different locations independently generate a common private key based on a secret shared key-seed. Such a procedure allows then to generate and synchronize a common pseudorandom bit stream beginning with an agreed-on starting value v which is "decrypted" by the private key and the result XORed with plaintext to encrypt and decrypt in the manner of one- time pads or Vernam ciphers. The starting value v would then be incremented by +1 each iteration yielding a nonrepeating cycle of 2**n iterations where n is the system block size in bits. Key seeding also facilitates opportunistic encryption using devices such as PC's and workstations that are generally avail- able but not portable. For example, Bob could freely transport the encryption/decryption program on a 3 1/2" floppy in his shirt pocket without fear of compromising his secret key-seed. Alice could encrypt from any available PC initialized with an installed WARLOCK program. Both would enter their secret key-seed at the time of message exchange. As yet another example of the potential of key seeding, consider an environment where Bob and Alice are deployed as secret agents who must unequivocally authenticate each other's identity prior to commencing their mission. Each has memorized a key-seed given them by their faceless directors and each carries an unknown ciphertext segment as well. When they finally rendezvous in Vienna, Bob and Alice XOR the ASCII representation of their key- seeds to produce a new key-seed value which they use to generate cryptographic keys. Each then decrypts his ciphertext segment with the newly-generated keys. Bob hands his decrypted message to Alice who reads, "Of course, you know my name isn't Bob at all, it's Travis and I am pleased to meet you at last, Tatiana AKA Alice." 9. WARLOCK CRYPTOGRAPHIC STRENGTH It would be presumptuous at this point to assert that WARLOCK is categorically unassailable -- particularly in light of the vast resources of linear algebraic techniques (most of which are unknown to the authors) that might be mustered for its cryptanal- ysis. The rise and fall of numerous PK cryptosystems proposed during the last decade certainly recommend caution as well. However, based on our experience to date in making and breaking scores of matrix-based PK cryptosystems, it is our feeling that the only potentially effective assault possible against WARLOCK is the derivation of private keys (or workable alternatives) from the public key (assuming that the keys are sufficiently large to preclude other attacks). Clearly, the keys themselves cannot be exhaustively enumerated owing to their size. Simmons generalized PK system attack (11.) can be precluded in several ways. Users may choose to operate in superencrypted mode which accomplishes encryption and source authentication simultaneously or they may choose a suitably large system block size. Various kinds of pre- encryption scrambling (to increase input entropy) and post-de- cryption unscrambling may also be employed. Thus far we have been unable to cryptanalyze WARLOCK 4.0 with techniques successful against ancestors of WARLOCK. Under all the attacks that we have been able to muster, the work factor required to cryptanalyze WARLOCK 4.0 is an exponential function of block size which can be made arbitrarily large. What we are seeking from the user community is an assessment of the viability of the WARLOCK paradigm as well as a more precise quantification of the work factor required to cryptanalyze WARLOCK 4.0. 10. CONCLUSION Apart from the undecided issue of security, the WARLOCK paradigm meets our objective of providing users with single high-speed general purpose PK cryptosystems (exemplified by WARLOCK 4.0) as alternatives to number theoretic systems. We feel that WARLOCK cryptosystems can serve the security needs of private users to whom we grant free use subject to the restrictions noted in the source code and in the introduction to this paper. The WARLOCK paradigm also suggests a new direction for the development of PK systems free of the computational burden of number theoretic systems. Finally, the WARLOCK paradigm suggests a potentially fruitful direction for achieving a viable cryptographic embodi- ment of the NP-hard coding problem cited by Berlekamp et al.(12.). 11. WARLOCK 4.0 NUMBERED FIGURES Note: To facilitate de- 1000 1000 101010101010 cryption, Row 1. is row 2 1010 0110 100010001000 of Matrix A triplica- 1110 1100 001000100010 ted. Row 2 is row 1 0011 1101 000000000000 triplicated; row 3 is 001100110011 the XOR of rows 1 and Figure 1. Figure 2. 111011101110 2 and row 4 is the A-Part Private Key 110111011101 XOR of rows 1, 2, and Matrix A Matrix A_ 000000000000 3. The same process inverse using remaining row Figure 3. pairs of Matrix A is re- A-expanded peated to create A_expan- ded. 100000000000 100010101101 101101000011 010000000000 010100100010 011010010000 001000000000 001011001000 000001001110 111000000000 111111001001 110011001111 000100000000 000100101011 011000010011 000010000000 000010111111 001101110011 000001000000 000001111100 001100100110 000111000000 000111011110 010101110110 000000100000 000000100000 001000000000 000000010000 000000010001 000000100001 000000001000 000000001001 000000000011 000000111000 000000111000 001000100010 000000000100 000000000100 000100000000 000000000011 000000000010 000000010000 000000000001 000000000001 000000000001 000000000111 000000000111 000100010001 Figure 4. Figure 5. Figure 6. B-Part B-Part B-Part Initial key_T_temp- Columnar re- key_T_temp- late with arrangement late noise bits = key_T_with_ noise_bits 110000001000 101001010100 000110100011 100100111100 100000100001 010001110011 110101011011 000001101100 111010111100 001111001000 110101000010 110010110100 001000111100 110110001110 100100010001 111111110010 011000000100 101101101000 100001111010 110101000111 000000010010 111111110000 010111011110 010111011010 .OJ OFF Figure 7. Figure 8. key_M Private Key key_M_inverse 101101000011 110100100010 011001100001 011010010000 110100100010 101110110010 000001001110 110100100010 110101101100 110011001111 110100100010 000111101101 011000010011 001101010001 010101000010 001101110011 001101010001 000000100010 001100100110 001101010001 000001110111 010101110110 001101010001 011000100111 001000000000 010011011011 011011011011 000000100001 010011011011 010011111010 000000000011 010011011011 010011011000 001000100010 010011011011 011011111001 000100000000 101100110010 101000110010 000000010000 101100110010 101100100010 000000000001 101100110010 101100110011 000100010001 101100110010 101000100011 101010101010 011111101001 110101000011 100010001000 011111101001 111101100001 001000100010 011111101001 010111001011 000000000000 011111101001 011111101001 001100110011 011001110011 010101000000 111011101110 011001110011 100010011101 110111011101 011001110011 101110101110 000000000000 011001110011 011001110011 Figure 9. Figure 10. Figure 11. key_T_with_ replacement_ key_T_replaced noise (A rows (Figure 9. and B-Part XOR'd with Fi- joined) gure 10.) 11. BIOGRAPHICAL DATA William J. Wilson is an early-retiree of the Sperry half of the current UNISYS corporation. During his 23 years there, he spe- cialized in database design, information storage and retrieval, and system security. He is a member of ACM occasionally consult- ing in his areas of expertise and is also identified in the current Directory of American Fiction Writers and Poets as both a writer (science fiction and horror) and a poet. His light and satirical verse appeared frequently in DATAMATION (Churl's Garden of Verses, Solid-state Jabberwocky, Ode to the Indomitable GOTO, etc.) and other magazines. C. Larry Craig (co-inventor of WARLOCK and author of the C++ WARLOCK program) currently works as a private consultant and software designer in the fields of digital communication, commu- nication networks, and cellular and telephony applications. 12. REFERENCES 1. Hill, L. "Cryptography in an Algebraic Alphabet," Amer. Math. Monthly. 36: 306-312, 1929. 2. Diffie, W., and Hellman, M.E. "New Directions in Cryptog- raphy," IEEE Trans. Inform. Theory IT-22, 644-654, Nov. 1976. 3. Rivest, R. et al., A Method for Obtaining Digital Signa- tures and Public-key Cryptosystems, Communications of the ACM 21, pp. 120-126, Feb 1978. 4. McEleice, R.J. "A Public-key cryptosystem based on Alge- braic Coding Theory," DSN Progress Rep. 42-44, Jet Propulsion Laboratory, pp. 114-116, 1978. 5. Korzhik, V.L. and Turkin, A.I., "Cryptanalysis of McE- liece's Public-key Cryptosystem," Advances in Cryptology - Euro- crypt '91 Proceedings. 6. Cooper, R. "Linear Transformations in Galois Fields and Their Application to Cryptography," Cryptologia, Vol 4., No. 3, pp. 184-188, 1992. 7. Patti, T. "The SUMMIT Cryptosystem," Cryptosystems Jour- na, Vol 2., No. 2, 1992. 8. Merkle, C. and Hellman, M.E. "Hiding Information and Signatures in Trapdoor Knapsacks," IEEE Trans. Inform. Theory.IT- 24: pp. 525-530, 1978. 9. Payne, W.H. and McMillan, K.L., Orderly Enumeration of Nonsingular Binary Matrices Applied to Text Encryption, Communi- cations of the ACM, pp. 259-265, April 1978. 10. Chaitin, G. J. ""Randomness and Mathematical Proof," Scientific American pp. 47-52, May 1975. 11. Simmons, G.J., Forward Search as a Cryptanalytic Tool Against a Public Key Privacy Channel, Proceedings of the IEEE Symposium on Security and Privacy, April 1982. 12. Berlecamp, E.R., McEleice, R.J., and van Tilborg, H.C.A., On the Inherent Intractability of Certain Coding Problems, IEEE Trans. Inform. Theory, IT-24, pp. 384-386, May 1978.