WO2015056236A1

WO2015056236A1 - A method of generating key arrays of random numbers and encryption

Info

Publication number: WO2015056236A1
Application number: PCT/IB2014/065409
Authority: WO
Inventors: Andre Keith Joubert
Original assignee: Andre Keith Joubert
Priority date: 2013-10-17
Filing date: 2014-10-17
Publication date: 2015-04-23

Abstract

The invention relates to a method of encryption, using an initial, large, secret Truly Random Number [TRN] array, produced by a non-deterministic method, preferably quantum physical, and of length greater than the longest plaintext, together with some referencing data, recording predetermined random offsets in the TRN array. Many TRN keys are created by (a), using an offset in the TRN array that is unique to each plaintext; (b), extracting TRN data from that offset to fill the state-space of a Pseudo-Random Number Generator [PRNG] that generates uniform random numbers; and (c), using PRNG output to provide the indices for a Durstenfeld-Fisher-Yates shuffle [DFYS] (or equivalent) algorithm to re-order a subset copy of the TRN of length equal to that of the plaintext. The resultant key array comprises TRN data and is indistinguishable from that produced by a TRN generator and can be used with a Vernam-Mauborgne (One-time Pad) [OTP] cipher for encryption. No PRNG data is exposed to ciphertext attack, nor used in the key. These steps can be repeated numerous times, producing new, unique TRN key arrays, overcoming the key storage drawback. When desired, a newly-generated TRN array and referencing data can be encrypted with the existing key and transmitted between parties.

Description

A METHOD OF GENERATING KEY ARRAYS OF

RANDOM NUMBERS AND ENCRYPTION

FIELD OF THE INVENTION

The invention relates to a method of generating multiple key arrays of random numbers for cryptographic and statistical purposes; and, more specifically, to a method of encryption and associated decryption of data using such key arrays.

BACKGROUND TO THE INVENTION

The well-known Vernam-Mauborgne Cipher¹ (or One Time Pad [OTP]) provides perfect secrecy, proven mathematically by Shannon². This quality of the cipher depends on a secret key being truly random, unpredictable, as long as the plaintext, and used only once.

In addition to being information-theoretically secure, the cipher has the further advantage that actual encryption of a plaintext to a ciphertext is simple and fast.

A drawback of this cipher is the fact that the amount of key material required is as large as the plaintext being encrypted. If the cipher is used to encrypt data for storage, secret key storage equal to the plaintext length is required, doubling

1 Vernam patent 1919: US 1310719, later improved in conjunction with Mauborgne.

2 Communication Theory of Secrecy Systems by CE Shannon, from confidential report "A Mathematical Theory of Cryptography" dated 1 Sept 1946, since declassified. This is available as a pdf file at http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf, a work by Dr Jiejun Kong. total storage volume. Therefore, other than for small amounts of data, key management becomes onerous.

It should be emphasized that this cipher requires truly random data for its key. Thus, a deterministic process cannot be used, for it must not be possible to determine any other value from one or more observed values. A source of natural randomness, free of cyclical variation is required, as provided by sources obeying quantum physics. Some examples providing excellent sources of such randomness utilise timing of intervals between the emission of nuclear decay particles from a radioactive source, or those between the emission of photons from a light source, or counting the number of photons passing through and being reflected by a semi-reflective mirror.

A further drawback of this cipher is that, if it is employed to secretly communicate between two or more parties, the secure transport of a unique set of replenishment key data for each ciphertext becomes an additional problem.

A traditional replenishment method uses trusted couriers. However, this does not provide certainty that an adversary has not acquired the data.

A modern alternative replenishment method is Quantum Key Distribution [QKD]³, which utilizes the Heisenberg uncertainty principle of quantum physics to enable detection of any attempt by an adversary to read the data in the quantum channel (optical fibre or free space/air, etc). QKD can thus ensure the key is secret. However, the verification process requires numerous between- party communications, and discarding of portions of the key stream, reducing the net rate of ciphertext generation. In addition, there is an exponential increase in channel losses with increase in path-length. Thus, only a small fraction of the channel's capacity can be used for OTP-encrypted traffic, which fraction reduces rapidly with increase in path-length. For example, a 45km channel has been able to provide 1 Mb/s, sufficient for the transmission of video. 1 Mb/s is -0.01 % of a typical 10 Gb/s optical fibre channel. It is for this reason that block ciphers are used to achieve better utilization of expensive

3 Quantum key distribution: https://en.wikipedia.org/wiki/Quantum_key_distribution, a descriptive overview. channel capacity. Such ciphers only require short keys, but cannot provide perfect secrecy.

It follows that the OTP, although providing a secure method of encryption, is impractical in many instances.

OBJECT OF THE INVENTION

It is an object of the current invention to address and overcome some of the problems and drawbacks described above.

SUMMARY OF THE INVENTION

In accordance with a first aspect of the invention there is provided a method of encryption, comprising: a. providing a master random number array; b. selecting a plurality of predetermined unique indices to serve as offsets within the master random number array; c. recording as referencing data the details of each offset; d. using an offset in the master random number array that is unique to a plaintext data set to be encrypted; e. extracting first random number data from the offset within the master random number array, which random number data corresponds in length to a state-space of a Pseudo-Random Number Generator [PRNG], to provide a seed; f. using the seed to fill the state-space of the PRNG that generates uniform random numbers; g. extracting second random number data from the next index within the master random number array, which second random number data corresponds in length to that of the plaintext data set to be encrypted, to provide a master array copy; h. generating PRNG output and using the PRNG output to provide indices for a shuffle algorithm to re-order the master array copy to produce an encryption key as an array of random number data; and i. using the encryption key to encrypt the plaintext data set into a ciphertext.

The invention further provides for a method as defined, in which the steps d. to i. are repeated for each plaintext data set to be encrypted.

A further feature of the invention provides for a method as defined, in which decryption of the ciphertext comprises: a. using the referencing data to identify the master random number array and offset relevant to the encrypted plaintext data set; b. repeating the steps taken during encryption, substituting the ciphertext length for the plaintext length, to recreate the original encryption key; and c. using the encryption key to decrypt the ciphertext.

Further features of the invention provide for a method as defined, wherein the master random number array is used as a circular, continuous array starting from the offset unique to the plaintext data set to be encrypted; and in which the master random number array is a truly random number [TRN] array (produced by a truly random number generator [TRNG]).

A further feature of the invention provides for a method as defined, in which the PRNG has a repeat period greater than the length of the plaintext data set to be encrypted.

Further features of the invention provide for a method as defined, in which the shuffle algorithm is a Durstenfeld-Fisher- Yates shuffle [DFYS] algorithm; and in which the key array of random number data is used with a Vernam-Mauborgne (One-time Pad) [OTP] cipher to encrypt the plain text data set. A further feature of the invention provides for a method as defined, which is used to encrypt a newly-generated master random number array and referencing data and transmit the newly-generated master random number array and referencing data as ciphertext between parties each in possession of the existing master random number array and referencing data used to produce the ciphertext.

In accordance with a first aspect of the invention there is provided a method of generating multiple key arrays of random numbers, comprising: a. providing a master random number array; b. selecting a plurality of predetermined unique indices to serve as offsets within the master random number array; c. recording as referencing data the details of each offset; d. selecting an offset in the master random number array; e. extracting first random number data from the selected offset within the master random number array, which first random number data corresponds in length to a state-space of a Pseudo-Random Number Generator [PRNG], to provide a seed; f. using the seed to fill the state-space of a PRNG that generates uniform random numbers; g. extracting second random number data from the next index within the master random number array, which second random number data corresponds in length to the key array of random numbers required, to provide a master array copy; h. generating PRNG output and using the PRNG output to provide the indices for a shuffle algorithm to re-order the master array copy to produce a key as an array of random number data. The invention further provides for a method as defined, wherein the master random number array is used as a circular, continuous array starting from the offset.

A further feature of the invention provides for a method as defined, in which the master random number array is a truly random number [TRN] array (produced by a truly random number generator [TRNG]).

A further feature of the invention provides for a method as defined, in which the PRNG has a repeat period greater than a length of the key array of random numbers required.

DEFINITIONS

For the purposes of the "Description of the Invention" that follows in this patent specification, each term listed below in bold type shall be taken to include/mean the term/s listed in normal type following it.

Truly random number/s [TRN]: Members of a set of such numbers generated by a non-deterministic process, each within a given range of values, of which none can be predicted after observing one or more, or a series thereof, whether isolated or contiguous, and indicated to be random by suitable statistic tests.

Statistic tests: Given a large set of many random numbers (bytes), they should be unpredictable, substantially uncorrelated, uniformly distributed, and have few long repeat runs. The set should be tested for incompressibility, correlation, entropy, and distribution, at least.

Truly random number generator [TRNG]: A non deterministic means of generating a sequence of truly random numbers/bytes with substantially equal counts of all values in its output, when considering a large output array.

Array: A list, array, table, file, or the like, wherein reference can be made to each contained data item by an index. It can loosely include a string of characters, indexed by their positions in the string. Large (when applied to random number arrays): Of such size the criteria being considered are satisfied thereby.

Index/indices: Reference's in an array, enabling individual data items to be inserted, accessed, replaced, modified, and/or removed.

Offset: A selected starting index in an array.

Circular array: An array of n elements, having indices (j) from (0 to n-1 ), addressed by external indices (k) with the same limits, starting from a selected starting point index (the offset), and traversed in the direction of increasing indices up to its end, whereupon the traverse loops to the array's beginning and continues up to the index before the offset. A circular array is typically produced by using a linked list or a simple array, i.e., an array comprising one value for each index.

For a simple array, the following illustrative algorithm indicates one addressing method: let max = n - offset; if (k < max) { j = k + offset } else { j = k - max }

Note: this algorithm excludes multiple traversals that will be required if the external indices exceed n-1 .

Seed: Initializing data supplied to initialize a pseudorandom number generator so as to enable it to begin generating random numbers of the required quality.

Pseudorandom number generator [PRNG]: A deterministic or algorithmic means of generating random numbers, over a given range, having a uniform distribution of values, as determined by the best or suitable current randomness tests, and such that different initializing seeds result in different series of random numbers being generated.

Preferred pseudorandom number generator [PPRNG]: A fast pseudorandom number generator producing uniformly distributed numbers, as well as having a very long repeat period, greater than that of the data set for which it is required e.g. the dSFMT 2,2 2012 Mersenne-Twister⁴, or better. This has repeat periods of 2⁵²¹-1 to 2²¹⁶⁰⁹¹-1 values (2¹⁹⁹³⁷-1 is common). For very fast generation, a Graphic Process Unit [GPU] or Field Programmable Gate Arrays [FPGA] implementation is appropriate.

Plaintext: An array or string of data, words, figures, bits or bytes, which forms the subject matter of an operation, e.g., data (image, text, program file, etc) storage, message transfer, random sampling, etc., optionally containing hash values used for verification and authentication.

Durstenfeld-Fisher-Yates shuffle⁵ [DFYS] algorithm: An algorithm which, provided the random numbers used to index it are uniformly distributed and unbiased, ensures that the resulting permutation is random and unbiased. One version to shuffle an array in place is illustrated below: let sArr be an array of n elements (indices 0..n-1 ); for i from n - 1 down to 1 do { j = random integer with 0≤ j≤ i; exchange sArr[ j ] and sArr[ i ] }

Note: the above shows a shuffle-in-place version. Alternative versions may be employed.

In this document, whenever this particular shuffle is mentioned, an alternative shuffle may be employed, as long as it is capable of ensuring that the resultant permutation is random and unbiased.

Key or key text: An array of truly random numbers/bytes used to encrypt a plaintext/decrypt a ciphertext.

Ciphertext: An array or string produced by a cipher algorithm that encodes a plaintext using a key, rendering the plaintext in an unreadable form without the proper cipher and key to decrypt it.

4 Mersenne-Twister: invented by Makoto Matsumoto & Takuji Nishimura - refer http://www.math.sci.hiroshima-u.acJp/~m-mat7MT/emt.htrnl

5 Durstenfeld-Fisher-Yates algorithm: origins can be seen in "Statistical tables for biological, agricultural and medical research" (3rd ed.), Fisher, R. A., Yates, F., Oliver & Boyd, London, 1938, pp. 26-27 and "Algorithm 235: Random permutation", Durstenfeld, Richard, Communications of the ACM 7 (7): 420, 1964). Wikipedia ref: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates shuffle XOR: Bitwise Exclusive OR produces a value of True if one but not both of its operands is True, i.e., returns True if either the value to the left or the value to the right of the operator is True, but not both. If both values are False or both values are True, the result of the operation is False.

QKD (Quantum Key Distribution): Method of cryptographic key distribution that utilizes the Heisenberg uncertainty principle of quantum physics to enable detection of any attempt by an adversary to read the data in the quantum channel (optical fibre or free space/air, etc).

GENERAL DESCRIPTION OF THE INVENTION

Under this heading, an overview of the method of the invention, described in simplified form, is provided.

It is convenient for a human to view a set of truly random binary data in 8-bit byte chunks that comprise the extended ASCII code (American Standard Code for Information Interchange), e.g., alphabet characters, numerals and special characters. However large a set of TRN may be, it contains a maximum of 256 different byte-values. In a large set, the TRN are by definition substantially uniformly random, and therefore the set contains substantially equal counts of each byte-value. Similarly, the order in which the individual bytes are generated is truly random. In the course of time, the generator delivers an array of TRN.

If the array indices are reordered in a uniformly random manner by a PPRNG and DFYS, a new set of TRN is obtained. If this shuffling process is carried out in private, it is impossible for an observer of the TRN array to determine whether the array was generated by the TRN generator, or by the shuffle. Neither can the observer determine the PPRNG output.

Now, any large set of TRN, although possessing good statistics, will not have exactly equal numbers of each byte-value, by the very nature of randomness. However, if large subsets are randomly taken from this large set of TRN, differing statistics of the shuffled subsets are obtained, because the byte-counts will differ between subsets. However, all subsets will have acceptable variations and be TRN. If each subset's PPRNG seed is extracted from a unique offset, the shuffled subset will be unique.

The quality of the shuffled TRN set is dependent on that of the original set, the quality of the indexing PPRNG, the shuffle algorithm used, and the PPRNG seed. To ensure good quality PPRNG outputs, the seeds should comprise TRN subsets and be unique to each shuffling operation.

The fact that one set of TRN generated by the TRNG can provide many OTP keys enables the periodic transmission of a newly-generated TRN set by encrypting the latter with the previous key. This solves the OTP key distribution problem. It also diminishes the necessity of QKD, as will be evident from the "Application of the method together with Quantum Key Distribution" that follows below.

The key storage requirement, if keys need to be stored, is reduced from one whole key per encryption, to a single TRN array and a small amount of key shuffling data that will enable recreation of a particular key. This solves the OTP key storage problem.

A high rate of OTP encryption is enabled, because the required rate of new TRN generation is reduced to a small fraction of the encryption rate (see the "comment" under Example 1 below, for example).

BRIEF DESCRIPTION OF THE DRAWING

The features of the invention will now be described, by way of example only, with reference to specific embodiments, in which reference is made to the accompanying drawing

Figure 1 which shows a schematic layout of the method of the invention as it is used to achieve secrecy of data during storage and/or transmission.

DETAILED DESCRIPTION OF THE INVENTION An array, hereinafter termed the Master array, of non-deterministically generated truly random numbers is considered as a circular array, starting from an offset unique to each data set to be encrypted, and a unique set of truly random numbers sufficient to fill the state-space of a preferred pseudo-random generator extracted.

A copy array of the following truly random numbers, of length equal to the data set in question, is then extracted. This copy is shuffled in an unbiased manner, indexed by the uniformly-distributed numbers generated by the preferred pseudo-random generator. This array is used as a Vernam-Mauborgne encryption key.

Encryption key management is greatly simplified, as many encryptions can be executed using the original Master array of truly random numbers Thus, each stored truly random number array generated by an often relatively slow-paced quantum process, can provide unique encryption keys for each of many sets of data, eliminating the key storage problem normally associated with the Vernam- Mauborgne cipher.

An ID file or array containing the unique offsets associated with each plain/ciphertext is maintained. This enables the correct unique encryption/decryption key to be generated. Each entry is securely deleted when no longer required.

If the Master array file and its relevant ID file or array are safely stored and kept secret until no longer required, the requirements of the Vernam-Mauborgne cipher will be met.

One typical application using the above simple method would be data archiving, where a single user encrypts and decrypts the data. The ID file record concerning a particular plaintext/ciphertext is securely deleted when decryption is no longer required.

If the method is employed to pass data between two or more users, then it may be modified to include Master array file shuffling between each encryption/decryption, dedicated Master/ID file ranges per user, and erasing of the particular offsets.

This enables any user to decrypt a message received from any other user, and prevents an attacker who gains possession of a user's system from generating any previously- used key.

If more than one party is employing the cipher to secretly communicate, a new set of truly random number data can be sent encrypted under a key from the existing Master array, as a message or group of messages, i.e., without secret physical transfer or quantum key distribution. From this set of truly random number data, new Master and associated ID array/s can be generated. This overcomes the seed resupply problem normally experienced with the Vernam- Mauborgne cipher, and enables almost full channel capacity to be used for transmission of perfectly secret data.

These advantages of the method eliminate the principle objections to the use of the Vernam-Mauborgne cipher.

Examples of application:

The examples provided below are illustrative of method applications and are intended to show good-practice approaches.

Firstly, an example of the application of the method when employed by one party to achieve perfect secrecy of data during transmission and local or remote storage, via the internet or dedicated means, is described. See Example 1 , below.

Secondly, an example of the application of the method when employed by two or more parties to achieve perfect secrecy of data exchange is described, including steps that nullify attacks on previously-generated ciphertexts by an attacker who has gained possession of the system. See Example 2, below. Thirdly, the application of the method used in conjunction with QKD is described. See the description of "Application of the method together with Quantum Key Distribution" below.

Lastly, a note is made regarding the use of a portion of the method for non- encryption applications, such as statistical analysis, random sampling, etc. See the description of "Non-encryption applications of certain steps of the method" below.

The reference numbers in bold type, e.g. 100, refer to numbers in the accompanying Figure 1 , and/or serve to identify elements being described in the text.

Example 1 : Achieving secrecy of data during transmission and/or storage

The method comprises the following steps:

Master array: From a truly random number generator, the TRNG 10, obtain a large Master array 20 of truly random bytes, verified by statistical tests.

(The length should be chosen while bearing in mind the size of plaintexts likely to be encountered, and the minimum statistical test-size required. It could typically have a length of 10 MB to 10 GB with one byte in the range [0..255] at each index in the Master array. For the purpose of this document, as an example, a Master array length of 20 MB is chosen, which is considered to be larger than 90% of the files normally processed by an average user.)

ID array: Create an ID array 30 with column labels Input Name 32, Offset 33, Output Name 34.

Fill the Offset 33 column with unique random indices into the Master array 20, substantially evenly spaced throughout its length. (Considering the 20 MB Master array example, the number of files to be encrypted using this Master array could be, say, 200 000. The offsets could then be at approximately 100 byte intervals, within say 10 %.)

The offsets should be shuffled before being inserted in the ID array.

Fill the Output Name 34 column with archive file identifiers such that the Master and ID array identities are registered, but otherwise random, e.g., "05605^*~8f!" meaning the Master number 56 is being used together with the ID array number 5, with a unique random number.

Insert the unique name of each Plaintext being encrypted into the Input Name 32 column.

(The Master array 20 might be used to supply data to encrypt 200 000 Plaintexts, for example. There might be 100 ID arrays of 2000 rows used in conjunction with that Master array, to facilitate sorting/searching.)

Usage: For each Plaintext to be handled, enter the name into the first available empty field in the Input Name 33 column of the ID Array 30. This name might comprise the Plaintext's file name, with its last-modified date-time data and should end with the first five digits of the Output Name 34 appended. Consider this row in the ID array 30 as the "active row".

Using a cryptographic hash algorithm⁶, e.g., MD5, create a hash of the resultant Plaintext, and append it to the Plaintext to create the Plaintext- with-Hash 160.

Determine the Length 190 of the Plaintext-with-Hash 160.

Seed: Create Seed 80 by sequentially extracting truly random numbers from the Master array 20, considering it as a circular array starting from the Offset 60 determined by the ID array's offset in column 33.

6 Cryptographic Hash algorithm: a general overview is provided here: http://en.wikipedia.or /wiki/Crvptoqraphic hash function. The fact that the cryptographic hash is encrypted with the plaintext renders it secret. Thus, an adversary cannot attack it. Therefore, even if the hash is considered to be vulnerable when visible in the clear, e.g., the MD5 hash, it is adequate for the required duty. The number of truly random numbers that will form the Seed 80 depends upon the chosen pseudo-random generator (PRNG). If the PPRNG 90 (a Mersenne-Twister, in this case) is selected, as indicated in example of Figure 1 , the state-space requires 624 x 32-bit integers to fill it, or 2496 Bytes.

The Offset 70 is that index immediately after the index used to extract the final truly random number extracted for the Seed 80 from the Master array 20. Offset 70 now serves as the zero index of the Master array 20, configured as a circular array.

Master Array Copy: Starting at the Offset 70, create Master array copy 130 of the Masterarray 20 equal to the Plaintext-with-Hash 160 of Length 190, by reading sequential bytes from Master array 20, considered as a circular array, until the required array length is reached.

If the Length 190 exceeds, say, three times the Master array 20 length, then split the Plaintext into two or more portions and treat them as separate Plaintexts with appropriately annotated Input Names 32 so that, on decryption, they can be correctly concatenated into the original Plaintext. The steps from 'Usage', above, must be carried out for each portion.

Note: if many Plaintexts of such length are to be handled, clearly the size of the Master array 20 was incorrectly chosen, and should be increased.

Encryption Key: With the Durstenfeld-Fisher- Yates shuffle algorithm 140, indexed by the random numbers issued by the PPRNG 90, shuffle the Master array copy 130 (preferably in-place) to create the Encryption key 150.

Encryption: XOR 170 each byte of the Plaintext-with-Hash 160 with the corresponding byte of the Encryption key 150 to create the Ciphertext 180. If volatile memory was not used for the Master array copy 130 and if the Encryption key 150 was not created by shuffling the Master array copy 130 in place, then securely delete it/them.

Storage: Store the Ciphertext 180 using its Output Name 34 as the file name, either locally or at one or more remote location/s.

Note: Several copies, each stored at different locations, increase data security in that retrieval of error-free data is more assured.

Retrieval: When it is desired to retrieve the Plaintext, identify the correct Master and ID files from the stored file name.

Using the identified ID file, locate the relevant Input Name 32 in the ID array 30 and thereby retrieve the Plaintext's stored Output Name 34. Retrieve the Ciphertext 180 file from storage, using that name.

Repeat the steps taken during encryption, substituting the Ciphertext 180 length for the Plaintext-with-Hash 160, thus recreating the original Encryption key 150.

Decryption: XOR 170 each byte of the Ciphertext 180 with the corresponding byte of the Encryption key 150 to retrieve the Plaintext- with-Hash 160.

Verify Integrity & Authenticity: Remove the hash from the Plaintext- with-Hash 160, compute the hash of the remaining Plaintext using the original hash algorithm, and compare with the decrypted hash. If the hashes differ, the ciphertext contains errors or has been corrupted, and retrieval from another storage location should be tried.

Comment:

If one takes 5 MB to be the average Plaintext-with-Hash size and uses the example Master array size of 20MB, and total ID arrays' length of 200 000 rows of typically -128 Bytes each, or -25.6 MB, it can be seen that the ratio of Plaintext-with-Hash to key and reference data would be: -(200000 x 5)/(20+25.6), or -21930:1 (1TB :45.6 MB).

Each Plaintext is encrypted with a unique truly random key.

It is not possible: to decrypt the stored Plaintext without possession of the Master array 20 and the ID array 30.

A passive attacker viewing the Ciphertext cannot learn anything more about the Plaintext than he knew prior to viewing the Ciphertext.

Although an attacker possessing a ciphertext-plaintext pair will, as with any cipher, be able to determine the applicable key, that key is not reused. Thus the knowledge is useless as far as other decryptions are concerned,

Knowledge of a Plaintext's encryption key wii! not enable an attacker to deduce the Master array.

Note; although occasional plaintexts of length greater than the Master array can be handled, it is suggested that such length should not exceed 300% of the Master array. This is because the deviation from perfect distribution, inherent in any Truly Random Number sequence, may be - exaggerated by the repetition, I.e., the effects of skew that always exists can increase, resulting in inferior sequences (mostly as regards correlation). It is best to use a Master array of length greater than any plaintext to be encrypted.

Example 2: Method of achieving secrecy of data message transmission between two or more parties

The method in Example 1 , above, can be adapted to provide perfect secrecy of data message transmission between two, or more, parties, by providing duplicate Master and ID files to each party, and allocating unique ranges of ID data to each. This system is simple and fast. It provides perfect secrecy provided each party preserves the secrecy of the Master and ID arrays.

However, an attacker who gains possession of a set of Master/ID data could then use it to decrypt an intercepted data message, by brute-force search of the Master for the relevant offset.

Therefore, a highly secure version is described, which denies an attacker access to used keys even after gaining possession of Master and ID array data.

When multiple parties are involved, the communication topology is likely to have a mesh structure, i.e., any party can communicate with any other party. The method comprises the following steps.

Master array/s: As per Example 1 Master Array. As many unique Masters as there are parties are required. Each party has all Masters and their associated ID arrays m his possession. Each party has a unique Master allocated for him to encrypt data. He uses the sender's Master to decrypt that sender's data.

ID array: As per Example 1 ID Array, except that no Input Name 32 is used, there being only the two columns 33 and 34. Each Master has its own ID array.

Initially, the party generating the Truly Random Numbers and creating the Masters and ID arrays transfers copies of the Master and ID arrays to all parties in a secure physical manner, maintaining data secrecy.

Note: Each party uses his allocated Master and its ID array to encrypt all data messages he sends, and the sender's allocated Master and its ID array to decrypt a received data message.

X. Sender's Usage: As per Example 1 Usage, except that the Input Name, with a unique termination character, is prefixed to the Plaintext, and then the Cryptographic hash, e.g., MD5, of that lengthened Plaintext, is created and appended to the Plaintext, to create the Plaintext-with- Hash 160. i. Plaintext-with-Hash length: As per Example 1 Plaintext-with- Hash length. ii. Seed: As per Example 1 Seed. iii. Master array copy: As per Example 1 Master array copy. iv. Encryption key: As per Example 1 Encryption key. v. Encryption: As per Example 1 Encryption. vi. Append the Output Name 34 from the ID array 30 to the ciphertext. vii. Transmission: Send the Ciphertext 180 to B under any arbitrary name, via the internet or any other suitable means, in the usual manner. viii. Shuffle the Master array: reseed the chosen preferred pseudorandom generator [PPRNG] 90 with the previously-used seed and shuffle the Master 20 array.

Y. Receivers Usage: On receiving a Ciphertext 180: i. First remove the Output Name 34 from the ciphertext and use it to search the sender's ID array 30 for a match. ii. Shuffle: If the preceding row is not empty, successively check previous rows, until an empty row is found. Then, using the first full row, successively shuffle the sender's Master, using the Offset 33 in each row of the ID array 30, and securely deleting each processed row, until the required Output Name 34 is reached. This ensures that the Master is the same as that used to make the ciphertext, although intervening ciphertexts were not received by this particular receiver. iii. Repeat the steps from 'Plaintext-with-Hash length' X.i to 'Encryption key' X.iv, above, substituting the 'ciphertext' for 'plaintext', thus recreating the original encryption key. iv. XOR 170 each byte of the Ciphertext 180 with the corresponding byte of the Encryption key 150 to retrieve the Plaintext-with-Hash 160, including its prefixed Input Name 32, and, if applicable, its prefixed annotation regarding its Plaintext portion. v. Remove the hash from the Plaintext-with-Hash 160, compute the hash of the remaining Plaintext, using the original hash algorithm, and compare with the decrypted hash. If the hashes differ, the ciphertext contains errors or has been corrupted or attacked, and the sender should be notified. vi. Remove the Input Name that was prefixed 10 the Plaintext, which has now been decrypted. This is the original Plaintext filename. Securely delete the used row in the ID array 30. vii. Shuffle the sender's Master array 30, as per X.vi. That Master array is now identical to that of the sender after he encrypted the data message.

Periodically, a data message should be sent to all parties, by each party, so that all parties' Masters are updated to the same state.

Comment:

As per Example 1 above.

The shuffling of the Master array, after key generation, prevents an attacker from determining any previously used keys, should he gain possession of the Master and ID array files. The periodical sending of a data message from each party to all other parties and the resultant up to date state of the Masters ensures that no previous message, between any parties, can be decrypted by an attacker in possession of one or more party's/parties' Masters and ID arrays. Replacement truly random number data sets may be securely transferred by sending them as messages secured with the existing Master/s and ID array/s. From these data sets, new sets of Master/s and ID arrays can be generated by each party.

This overcomes one of the principle difficulties associated with the use of the Vernam-Mauborgne cipher when used for message interchange, i.e., that of key resupply.

Application of the method together with Quantum Key Distribution:

If, despite the considerable cost of QKD equipment and the distance limitations imposed by channel losses on effective QKD, it is not considered feasible to physically deliver an initial TRN array to both parties who are communicating via optical fibre, space, or air paths, then QKD can be used to deliver this data from the party having the TRNG or PTRNG to the other. This would be a one-time requirement, on initial channel setup.

As QKD will only be required to transfer one initial set of TRN data, it is feasible to use QKD over a long path-length. Published figures for QKD over a 250km optical fibre channel indicate ~2b/s, or ~7kB/h, is possible. For that path-length, the time taken to transfer the required initial data might run to a day or more.

A large TRN array can be generated by concatenating, say, 100kB sets, and then shuffling. The resultant key can then be used to transfer a TRNG key and then discarded. Thereafter, QKD is not required further, and high channel data-rate is enabled. Normal periodic TRN key replenishment is then effected as described in Example 2.

Note that the initial shuffled key is guaranteed secret, is only used once and encrypts a TRNG set. The resultant ciphertext cannot be analysed.

Non-encryption applications of certain steps of the method: For certain applications, e.g., statistical analysis, random sampling, etc., large amounts of truly random data are preferred. The method described above in Example 2 for transmission between two or more parties can be applied, with omission of the encryption/decryption steps. The ID array 30 will omit the Output Name 34 column. The Encryption key 150 forms the required data set. The recipients can duplicate any set of data by using the Input Name 32 and retrieving the Offset 33.

The invention accordingly provides a method of achieving Shannon's perfect secrecy of data transmission and storage. The method incorporates authenticity and integrity verification. It eliminates the main problems, i.e., the key length resulting in twice the data storage requirement, and key replenishment requiring secure physical transfer.

As the information-theoretically secure encryption is immune to attack, the current concerns regarding insecurity of file storage, on or off-site, in the cloud, etc., fall away. This should result in a significant marketing advantage.

In addition to data storage, the method provides perfect secrecy of data during communication between two or more parties, e.g., using a mesh topology. Replenishment of key material is effected without the necessity of secure physical delivery.

A person skilled in the art will appreciate that a number of variations may be made to the features of the embodiments described without departing from the scope of the present invention.

Claims

CLAIMS:

1 A method of encryption, comprising: a. providing a master random number array; b. selecting a plurality of predetermined unique indices to serve as offsets within the master random number array; c. recording as referencing data the details of each offset; d. using an offset in the master random number array that is unique to a plaintext data set to be encrypted; e. extracting first random number data from the offset within the master random number array, which random number data corresponds in length to a state-space of a Pseudo-Random Number Generator [PRNG], to provide a seed; f. using the seed to fill the state-space of the PRNG that generates uniform random numbers; g. extracting second random number data from the next index within the master random number array, which second random number data corresponds in length to that of the plaintext data set to be encrypted, to provide a master array copy; h. generating PRNG output and using the PRNG output to provide indices for a shuffle algorithm to re-order the master array copy to produce an encryption key as an array of random number data; and i. using the encryption key to encrypt the plaintext data set into a ciphertext.

2. A method as claimed in claim 1 , in which the steps d. to i. are repeated for each plaintext data set to be encrypted.

3. A method as claimed in claim 1 or claim 2, in which decryption of the ciphertext comprises: a. using the referencing data to identify the master random number array and offset relevant to the encrypted plaintext data set; b. repeating the steps taken during encryption, substituting the ciphertext length for the plaintext length, to recreate the original encryption key; and c. using the encryption key to decrypt the ciphertext.

4. A method as claimed in any one of claims 1 to 3, wherein the master random number array is used as a circular, continuous array starting from the offset unique to the plaintext data set to be encrypted.

5. A method as claimed in any one of claims 1 to 4, in which the master random number array is a truly random number [TRN] array.

6. A method as claimed in any one of claims 1 to 5, in which the PRNG has a repeat period greater than the length of the plaintext data set to be encrypted.

7. A method as claimed in any one of claims 1 to 6, in which the shuffle algorithm is a Durstenfeld-Fisher- Yates shuffle [DFYS] algorithm.

8. A method as claimed in any one of claims 1 to 7, in which the key array of random number data is used with a Vernam-Mauborgne (One-time Pad) [OTP] cipher to encrypt the plain text data set.

9. A method as claimed in any one of claims 1 to 8, which is used to encrypt a newly-generated master random number array and referencing data and transmit the newly-generated master random number array and referencing data as ciphertext between parties each in possession of the existing master random number array and referencing data used to produce the ciphertext.

10. A method of generating multiple key arrays of random numbers, comprising: a. providing a master random number array; b. selecting a plurality of predetermined unique indices to serve as offsets within the master random number array; c. recording as referencing data the details of each offset; d. selecting an offset in the master random number array; e. extracting first random number data from the selected offset within the master random number array, which first random number data corresponds in length to a state-space of a Pseudo-Random Number Generator [PRNG], to provide a seed; f. using the seed to fill the state-space of a PRNG that generates uniform random numbers; g. extracting second random number data from the next index within the master random number array, which second random number data corresponds in length to the key array of random numbers required, to provide a master array copy; and h. generating PRNG output and using the PRNG output to provide the indices for a shuffle algorithm to re-order the master array copy to produce a key as an array of random number data.

1 1 . A method as claimed in claim 10, wherein the master random number array is used as a circular, continuous array starting from the offset.

12. A method as claimed in claim 10 or claim 1 1 , in which the master random number array is a truly random number [TRN] array.

13. A method as claimed in any one of claims 10 to 12, in which the PRNG has a repeat period greater than a length of the key array of random numbers required.