Cryptix logo

A JavaTM implementation of RPK

(Cryptix Application Note #4 -- October 1997)

 Table of Contents

Return to the Application Notes Index or the FAQ or the Overview.


Overview

The RPK system is a comprehensive set of procedures for secure exchange of communication designed by William Raike . The publicly available documents describing the system and a Borland Delphi/Pascal implementation of it are available at http://crypto.swdev.co.nz/.

The reader is encouraged to examine those documents since they describe more formally the mathematical basis used in constructing the algorithm, and the resultant cryptographic qualities.

This application note only deals with programming decisions adopted in the Java implementation of the system and how and why they differ from the Delphi one. It is not a substitute for a proper understanding of the algorithm. The term RPK is applied to the algorithm of that name, rather than the company.


RPK --An informal introduction

RPK cryptography relies basically on an instance of a keystream generator that both Alice and Bob --the parties wishing to communicate securely-- have to synchronise to the same state (by convention referred to as K). Once the keystream automaton is initialised to the state K, Alice creates a ciphertext by combining the plaintext with the keystream output, while Bob reconstructs the plaintext from the ciphertext by combining the latter with the same keystream output. The combination function in this case being a bit-wise XOR of both sources (plaintext/ciphertext and keystream).

The secure exchange of the value K (i.e., the starting state of the keystream automaton) relies on the mathematics of polynomials in the field F2L = Z2 / f(x), f(x) a primitive polynomial of degree L. In this field, the following formula, which embodies the RPK system, is true:

(x D) R = (x R) D = K (mod f(x))

Written differently, the same equality can be stated as follows:

E R = Q D = K (mod f(x))

In this syntax, E and Q are called states of the keystream generator, while D and R are referred to as distances or exponents.

If E is the public key of the recipient, and D is his private one, then transmitting the crucial value of the state K is equivalent to the originator Alice generating another functionally similar pair (Q, R), and sending only the Q portion to Bob. In turn, for Bob to synchronize the keystream generator, he needs to compute Q D, from the state Q and his private key D.

 

Keys in the RPK scheme are either states of a Non-Linear Feedback Shift Register (NLFSR), or distances; ie. number of steps to advance the said NLFSR by. Effectively, RPK uses a special case of a Combination Generator, where one NLFSR called the Mixer, is used to select the source of the next output among two other NLFSRs. This NLFSR triplet arrangement is called a Mixture Generator.


Java implementation specifics

The publicly available Delphi implementation of the RPK system is programmed in Borland's Delphi 2.0. Some parts of the code are removed but the available documentation is sufficient to re-implement the missing code.

 

CRC32 and SecureRandom

The major characteristic of the Delphi implementation, is that everything is built from scratch. I don't know if this is the case because (a) no basic utilities and/or classes exist for Delphi programmers which are unencumbered by intellectual property rights, or (b) the author chose to re-code these basic classes to better control their behaviour, enhance the performance, etc...

For the Java implementation I chose to use and rely on the available classes of Sun's JDK (1.1.4 was used for this project). More specifically, java.util.zip.CRC32 and java.security.SecureRandom classes were used for CCITT CRC 32-bit handling and cryptographically strong pseudo random number generation respectively.

The rational for using java.util.zip.CRC32 is trivial: why re-invent the wheel? The JDK CRC32 class is the CCITT version, although the documentation of the class does not state it explicitly. Any class that implements the java.util.zip.Checksum interface can be substituted.

The choice for SecureRandom as the source of random data, instead of building a class from RPK's NLFSR as suggested by the Delphi implementation, is less obvious. Contrary to what it may seem from browsing the Delphi sources, RPK is not about generating random numbers. The concept of NLFSR as used by RPK, surely yields to building pseudo random number generators, but ultimately, any cryptographically secure PRNG should fill the requirement. In fact, and for the sake of argument, java.util.Random could have been used instead. However, since we're dealing with cryptographic classes, it makes sense to only use cryptographically strong PRNGs.

The documentation for SecureRandom states:

This class provides a cryptographically strong pseudo-random number generator based on the SHA-1 hash algorithm.

The calls inherited from Random will be implemented in terms of the strengthened functionality.

and further on:

... We attempt to provide sufficient seed bytes to completely randomize the internal state of the generator (20 bytes). Note, however, that our seed generation algorithm has not been thoroughly studied or widely deployed. It relies on counting the number of times that the calling thread can yield while waiting for another thread to sleep for a specified interval.

In the absence of tools to measure the claimed strength/randomness of the generated output sequence, I'll take Sun's word for it! However, any class that implements the java.security.SecureRandom interface can be substituted by the user of the provider.

 

Key exponentiation

The Delphi implementation uses pre-computed values of all possible powers of a given RPK Key. Remember an RPK Key is a triplet of NLFSRs. Each one, called also a Generator is chosen so its underlying LFSR has a maximum-length output of 2L-1. The default specifications for the Generators used in generating RPK Keys have: 289-1, 2127-1 and 2521-1 different non-zero states/powers respectively. Each state is represented by 12, 16, and 66 bytes respectively.

The Java implementation does not pre-compute these values. Instead it computes the required exponentiation using an adaptation of Knuth's Algorithm A. In doing so, the Java implementation gains in storage requirements but loses in speed.

 

RPK Keys

The differences between the Delphi and Java implementations of an RPK key relate to three areas.

Key data

An RPK Key is an instance of a Mixture Generator; ie. a triplet of Generators, with the first one acting as the Mixer. The source of the final key output is selected according to the value of the Mixer's underlying NLFSR output value: if it's zero then the first sub-generator (the second Generator in the list) is chosen, otherwise it's the second sub-generator (the last Generator in the list).

The specifications for a Generator are a pair of integers that define the powers of the terms of the polynomial: xn + xk + 1, which govern the output sequence of the underlying LFSR.

The Delphi implementation uses {{89, 38}, {127, 30}, {521, 163}} as default values, while the Java one uses: {{89, 38}, {127, 63}, {521, 168}}. The reason for this deviation is to improve the performance of the Java code; this minimises the shift operations on the contents of the LFSR without loosing any meaningful output. See the code for a fuller comment.

In order to generate keys with the same behaviour as the Delphi implementation, do this:

    // use delphi/pascal generator specs
    int[][] newspecs = {{89, 38}, {127, 30}, {521, 163}};
    int newgranularity = 8;
    SecureRandom newprng = new SecureRandom();
    RPKKeyGenerator kg = new RPKKeyGenerator();
 
    kg.initialize(newspecs, newgranularity, newprng);
 
    RPKKey k = (RPKKey) kg.generateKey();
 
Key granularity

The granularity property tells how many bits of the Mixture Generator output are to be combined with the plain/cipher-text to produce a cipher/plain-text. The smaller this value is, the less secure the final output becomes.

The Delphi code defines three values for this property: 1, 8 and 32 bits, with 8 being the default value.

The Java implementation, using the byte as the basic data storage unit to allow for platform independence, re-defines the granularity property as a value between 1 and 8 inclusive. This new property is then a superset of the Delphi one, which allows for more complexities in the produced output. 8-bit Granularity is also the default here as well.

 

Key ID

The Delphi implementation implicitly associates a notion of certificate to the contents of an RPK Key when computing the ID of a Key. Specifically, the ID is based on the actual contents of an encoding of the Key framed within a packet whose header contains application dependent information. This certificate does not follow any standard but is rather specific to the implementation itself. Furthermore, and for the specific case of a Key, it contains information that is alien to the key itself.

The Java implementation computes the ID based on the Raw-Encoded bytes of the key only. The Raw-Encoded bytes contains enough information to reproduce the Key on any other platform/implementation.

 

Encryption/Decryption block size

In the Delphi implementation, the encryption process is done as follows:

For every block-size bytes of input generate a new swap-table and divide the input into n blocks of 256 bytes each. For every one of these 256-byte blocks do the following:

  1. Update a CRC on the total input data processed so far including the current 256-byte block,
  2. Transpose the 256-byte block contents according to the current swap-table,
  3. Combine the session key's generator output with the data to produce the cipher-text using the key's granularity property,
  4. Discard a number of the session key's generator output obtained by masking the CRC value obtained in step 1 above with a specified Mask.

The default block-size value is 4096.

The Java implementation does not use the block-size property at all. Rather, it generates a new swap-table for every new 256-byte block. Implicitly this is equivalent to being hard-wired for a block-size equal to 256.

 

Using the IJCE API for stream and block cipher operations

The Java implementation provides two classes that permit the use of the RPK system as either a stream cipher or as a 256-byte block cipher.

The standard JCE/IJCE API for instantiating and using java.security.Cipher instances are catered for. 

 

Using the IJCE API for signing/verification of digital signatures

In public cryptography, a digital signature is computed from the message to be signed, and the signer's private key. Anybody wishing to verify the obtained digital signature, would use the alleged signer's public key and the signed message to check the authenticity of the fact that the digital signature was indeed produced by the signer.

In the RPK system, a digital signature can not be produced without prior knowledge of the intended recipient or recipients. As a consequence, the usual passing of the signer's private key as the argument to the initSign() method is replaced by passing the recipient's public key instead. Also, the passing of the owner's public key to the initVerify() method is replaced by the passing of the owner's private key instead.

More specifically, here are the steps involved in RPK digital signature/verification:

Signer:

  1. Hash the message to be signed, obtaining its md;
  2. Frame md in a PKCS#1 type 0 frame. Call this Mp;
  3. Choose a random number. Call it R;
  4. Compute Q = x R;
  5. Compute K = E R, where E is the recipient's public key;
  6. Encrypt Mp with an RPK stream cipher initialised to state K. Call the result Mc;
  7. Return the digital signature as the concatenation of Q || Mc.

Recipient:

  1. Hash the message to be verified, obtaining its md;
  2. Frame md in a PKCS#1 type 0 frame. Call this Mp;
  3. Extract Q and Mc from the digital signature to be checked;
  4. Compute K' = Q D, where D is the recipient's private key;
  5. Decrypt Mc with an RPK stream cipher initialised to state K'. Call the result Mp';
  6. Assert that Mp = Mp'.

For performance reasons, the Java implementation, only uses the last generator in the RPK Key triplet during exponentiation steps.


Using the Java RPK package

In the following code examples we will assume that prng is an instance of java.security.SecureRandom or one of its subclasses.

 

Generating Secret Keys

To generate new RPK Secret Keys with default specifications and default granularity (8 bits) for use with java.security.Cipher objects:

KeyGenerator kg = KeyGenerator.getInstance("RPK");
kg.initialize(prng);
RPKKey key1 = (RPKKey) kg.generateKey();
RPKKey key2 = (RPKKey) kg.generateKey();
...
RPKKey keyN = (RPKKey) kg.generateKey();

 

Visualising the actual contents of an RPK Key

To view the actual contents of an RPK Key:

System.out.println(key);

The output will be similar to the following:

 
RPK Key...
          ID: [EIEJFBIF]
      Length: 737 bits
 Granularity: 8
    Material: RPK Mixture Generator (1 + 2)...
Mixer: [...
 TrinomialLFSR <89, x89 + x38 + 1>...
 current state is: Binary dump of a BigRegister [89-bit]...
Byte #:|........|........|........|........|........|........|........|........|
    12:                                     00000001 11111000 00110010 11111001
     8: 10000100 11110101 11001100 11100010 00011111 00010100 01000001 10001111
...]
 
Generator #1: [...
 TrinomialLFSR <127, x127 + x63 + 1>...
 current state is: Binary dump of a BigRegister [127-bit]...
Byte #:|........|........|........|........|........|........|........|........|
    16: 00000010 10011111 01110011 01010110 00101101 10001011 11101010 01011110
     8: 01100010 10011101 00100010 00010100 10111010 10000101 01011000 00000101
...]
 
Generator #2: [...
 TrinomialLFSR <521, x521 + x168 + 1>...
 current state is: Binary dump of a BigRegister [521-bit]...
Byte #:|........|........|........|........|........|........|........|........|
    66: 00000000 11110001
    64: 01001000 01101010 01011010 11101000 10101111 11110011 10110010 11000111
    56: 11101000 11001110 01100000 10111100 00100010 01001000 00001000 10101010
    48: 11101111 11000111 01001110 11100010 00001000 10011111 11110011 11010010
    40: 10100111 00101010 10001100 01011000 11010001 01011110 01010001 11011101
    32: 01001001 01010101 11101000 10011100 00101011 01110011 01011111 11101100
    24: 10000000 11110111 10100011 10101111 10111010 01001100 10000010 10001111
    16: 10010010 11110000 01111111 11011001 10001010 01110101 11001101 01100101
     8: 00010100 00110010 01111001 00011000 00001101 10100100 01110110 01111111
...]

 

Generating Pairs of Public and Private Keys

To generate new RPK key pairs of public and private keys with default specifications, default pseudo-random number generator (java.security.SecureRandom), and a granularity of 8 for use with java.security.Signature objects:

KeyPairGenerator kg = KeyPairGenerator.getInstance("RPK");
kg.initialize(8);
KeyPair pair = kg.generateKeyPair();
RPKKey E = (RPKKey) pair.getPublic();
RPKKey D = (RPKKey) pair.getPrivate();

 

Creating and using stream and block Cipher instances

To create a new RPK stream cipher object and initialise it to state K (an instance of RPKKey) and encrypt an input byte array:

Cipher rpk = Cipher.getInstance("RPK.stream.cipher", "Cryptix");
rpk.initEncrypt(K);
byte[] output = rpk.crypt(input);

To do the same with an RPK block cipher used in ECB mode with no padding:

Cipher rpk = Cipher.getInstance("RPK.block.cipher", "Cryptix");
rpk.initEncrypt(K);
byte[] output = rpk.crypt(input);

 

Creating and using RPK-based digital signatures

To create an RPK-SHA digital signature and use it to sign a byte[] message addressed to Bob who claims to own the public key E:

Signature ds = Signature.getInstance("RPK-SHA");
ds.initSign((PrivateKey) E);    // role reversal in RPK
ds.update(message);
byte[] signature = ds.sign();

To verify that a received digital signature relates to a message that was originally signed by Alice who is supposed to have used our public key.

ds.initVerify((PublicKey) D);    // D is our private key
ds.update(message);
System.out.println(ds.verify(signature) ? "OK..." : "Failed...");


Does it work?

Two test classes are provided to test the RPK package: TestRPK and TestRPK2.

The first one tests the key pair generation process, the basic RPK formula, the stream cipher operation and the digital signature classes, while the other tests the key generation and the block cipher operations in ECB, CBC, CFB and OFB modes with no padding.


References

William Raike, RPK Implementation in Borland Delphi/Pascal, documentation.
Alfred Menezes et al, Handbook of Applied Cryptography, pp 195-222.
Bruce Schneier, Applied Cryptography, chap. 16.
Donald E. Knuth, The Art of Computer Programming, Vol 2. pp 442.


Cryptix
Raif S. Naffah
Chatswood, 30 September 1997.

Copyright © 1996-1997 Systemics Ltd
on behalf of the Cryptix Development Team.
All rights reserved.
Cryptix is a trademark of Systemics Ltd.
RPK is a patent-pending algorithm of RPK Ltd.
All other trademarks and registered trademarks
are the property of their respective owners.