Dec 302017

Description of Warlock public key encryption scheme. | |||
---|---|---|---|

File Name | File Size | Zip Size | Zip Type |

WARLOCK.TXT | 43264 | 13968 | deflated |

# Download File WARLOCK.ZIP Here

## Contents of the WARLOCK.TXT file

From digex.com!lynx.unm.edu!umn.edu!news-feed-1.peachnet.edu!darwin.sura.net!howland.reston.ans.net!sol.ctr.columbia.edu!PASCAL.ACM.ORG!WARLOCK Fri Jun 4 18:36:12 1993

Newsgroups: sci.crypt

Path: digex.com!lynx.unm.edu!umn.edu!news-feed-1.peachnet.edu!darwin.sura.net!howland.reston.ans.net!sol.ctr.columbia.edu!PASCAL.ACM.ORG!WARLOCK

From: [email protected]

Subject: New matrix-based PK Cryptosystem

Message-ID: <[email protected]>

Sender: [email protected]

Reply-To: [email protected]

Organization: ACM Network Services, Waco, TX

Date: Fri, 4 Jun 1993 08:59:15 GMT

X-Posted-From: acm.org

NNTP-Posting-Host: sol.ctr.columbia.edu

Lines: 875

.OJ OFF

.UL ON

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

msecret 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.

Newsgroups: sci.crypt

Path: digex.com!lynx.unm.edu!umn.edu!news-feed-1.peachnet.edu!darwin.sura.net!howland.reston.ans.net!sol.ctr.columbia.edu!PASCAL.ACM.ORG!WARLOCK

From: [email protected]

Subject: New matrix-based PK Cryptosystem

Message-ID: <[email protected]>

Sender: [email protected]

Reply-To: [email protected]

Organization: ACM Network Services, Waco, TX

Date: Fri, 4 Jun 1993 08:59:15 GMT

X-Posted-From: acm.org

NNTP-Posting-Host: sol.ctr.columbia.edu

Lines: 875

.OJ OFF

.UL ON

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

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.

December 30, 2017
Add comments