[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

New PKS (Warlock)



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 [email protected] 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.