Exploration of Cryptography Based on Irrational Numbers

Chris Rossbach

chris@rossbach.to

 

 

This paper documents some preliminary considerations regarding use of irrational numbers to create key material as the basis for some highly flexible encryption algorithms. The essential insight here is that for a number to be considered irrational, it cannot be expressed as the ratio of two integers—the side effect of this property that we are interested in taking advantage of is that when the irrational number is expressed in decimal notation, no pattern ever occurs in the sequence of digits after the decimal point as the precision of the number approaches infinity. It is widely known that the only truly secure encryption algorithm is the one-time pad—that is the use of a key exactly as long as the plaintext message that has no pattern, and is used only once. It’s also widely known that anyone claiming to have implemented an algorithm equivalent to a one-time pad should be regarded with severe skepticism if not open laughter. However, the observation that irrational numbers have a property reminiscent of properties needed for a one-time pad, inspires some thought. Given that the cardinality of the set of irrational numbers is quite vast, it’s tempting to simply use the residue of a shared-secret irrational number as a cryptographic mask. Key distribution is non-trivial of course: if the set of irrational numbers from which key material may be chosen is unrestricted, sharing the key becomes intractable. We do know, however, that since the set of rational numbers is not complete with respect to certain arithmetic operations, that there is no lack of easy-to-represent irrational numbers (e.g. any prime square root), the problem can be made soluble by excluding irrational numbers that are not easily calculable from holes left on the real number line by arithmetic.  

 

To be more specific, knowing that the decimal representation of an irrational number will have pattern-less behavior to the right of the decimal point, key material can be derived from or represented by rational numbers, an arithmetic operation, a precision, and a length. An example should make the concept more obvious, if it is not already. Consider a key specified by the n-tuple:

            < p, x^^(1/2), pr, k >, where p is prime.

 

The square root of p is guaranteed to be irrational. If the square root of p is calculated to a level of precision specified by pr+k, then the digits in the sequence of digits in the square root of p starting at index pr, and ending at index pr+k-1 are guaranteed to be a pattern-free sequence of digits of length k.

 

The obvious objection makes the matter almost entirely academic: calculating p to a precision greater than the precision one expects from standard floating-point representations incurs a computational overhead that makes this algorithm a poor choice over existing algorithms. While key calculation occurs but once, and the actual method of encryption is un-specified, it is still worth acknowledgement that high-precision computation restricts candidate platforms to the point where any solution based on these ideas would be useful only in specialized applications. With that acknowledgement aside, it should be observed the advantage of being able to select arbitrarily large key material blocks without significantly increasing the size of the key representation makes the idea worth investigation.    

 

Described below are some preliminary ideas about how an algorithm might be implemented that takes some advantage of the pattern-less behavior of the residue of irrational numbers, but limits the set of irrational numbers in use, such that keys can be represented easily. In the first section are some ideas about how one might implement a block cipher using these concepts, and in the second section I briefly look into how one might go about a implementing a stream cipher that more closely resembles the use of irrational numbers in a way that imitates a one-time pad. The third section outlines my efforts to implement the algorithm, shows some results, and leaves a great deal of work analyzing the results to be done. Section 4 contains a list of areas for further exploration, where ideas that occurred along the way, or obvious problems were left for later investigation in the name of arriving at a prototype that could be used to examine results.

 

Caveats are numerous:

 

Section I: Block Cipher Illustration

 

Let R denote the set of Real numbers

Let Ir denote a “limited” set of irrational numbers.

Since the cardinality of Ir is infinite, so we need to limit the selection of numbers to a known set whose size is large enough that in combination with other aspects of the algorithm, we prevent simple brute force attempts to guess which irrational numbers are in use when the encryption is performed. This is saved for later work—for now, assume when Ir is used, it refers to a large but non-infinite set of irrational numbers.

 

Select a set of random integers, to used as indices for selection of a set if irrational numbers from a known domain. This set of random integers we shall denote K, as collectively, these numbers form the cryptographic key.  K will be used to select a set Kirr,  consisting of a finite number of irrational numbers.

Let K be defined as {k0,...,kn}

Let Kirr be defined as {ir0,...,irx}

It is intuitive that the cardinality of K is greater than or equal to the cardinality of Kirr: that is to say, x <= n, but as needs arise for more integers to use in the manipulation and selection of numbers in Kirr, this assertion may turn out to be untrue, and deserves further consideration. For now, suffice it say that the set Kirr is derived from the set K in the manner outlined below. First, some definitions:

 

k0 : an integer that denotes the lower bound on the domain from which irrational numbers in Kirr will be selected.

k1 : an integer that denotes the upper bound on the domain from which irrational numbers in Kirr will be selected.

The domain of integers defined by [k0,...,k1] is used to derive a set of irrational numbers Dirr such that Dirr consists of all irrational numbers greater than k0 and less than k1.

 

The members of the set Kirr are selected from the domain Dirr based on the remaining members of K.

Define the function iselect( lbound, i) that maps lbound and i to the irrational number at the index i where index 0 maps to the first known irrational number greater than lbound.

k2 is then used to select ir0, such that ir0 = iselect( k0, k2 )

k3 is then used to select ir1, such that ir1 = iselect( k0, k3 )

Thus we arrive at a set Kirr = { iselect(k0, k2),...iselect(k0, kn) } which is in essence a randomly selected set of irrational numbers known to be in the range between k0 and k1.

 

The members of Kirr resulting from this selection process are then used as follows:

define a function ikselect( ir, i, len ), which returns len numbers from ir beginning at index i. For clarity, consider a simple example:

            ikselect( PI, 2, 3 ) = 159

                        PI = 3.141596...

                        Taking  3 numbers from starting at index 2 gives the result 159

 

Assume for now that the length parameter is constant, chosen as a parameter that helps define the strength of the cipher. This length will be referred to as L and assumed constant.

 

Then the members of Kirr are chosen as follows:

ir0 : also IRkey, which is the irrational number from which base key material be selected

ir1 : also called IRk_index, which is used to select an index into IRKey defining the actual chosen key material.   

ir2 : also called IRtrans, which is irrational number from which transposition key material will be selected.

ir3 : also called IRt_index, which is the index into IRtrans at which ikselect() will be used select transposition key material.

ir4 : also called IRsub, which is the irrational number from which substitution key material will be selected.

ir5 : also called IRs_index, which is the index into IRsub at which ikselect() will be used to select actual substitution key material.

Other irX are potentially envisioned as parameters which can determine modes of operation, dimensionality of matrices constructed from key material used, and so forth--if multi-dimensional matrices can be used to determine substitutions and transpositions, then having the actual dimensions used be effectively selected randomly heightens the computational overhead of brute-force attacks considerably. For now, we will operate in a scalar mode for simplicity of understanding how the key data may be used to make the substitutions and transposition strategies variable to an extent that makes them beyond the scope of brute force attack.

 

Thus:

IRkey = iselect( k0, k2 )

IRk_index = iselect( k0, k3 )

IRtrans = iselect( k0, k4 )

IRt_index = iselect( k0, k5 )

IRsub = iselect( k0, k6 )

IRs_index = iselect( k0, k6 )

 

further IRmatrix and IRmatrix_dimensionality parameters can be calculated in the same way.

 

Finally we calculate Kencrypt  as a set of integers { Kxor, Ktrans, Ksub } such that

Kxor = ikselect( IRKey, ikselect( IRk_index, k7, L ), L )

Ksub = ikselect( IRSub, ikselect( IRs_index, k8, L ), L )

Ktrans = ikselect( IRtrans, ikselect( IRt_index, k9, L ), L )

 

Kmatrix, Kmatrix_dimensions, etc can be calcuated in the same way.

 

The final result of the calculations used to arrive at Kencrypt resemble original contents of K at first blush--a simple set of random integers. However, the integers in Kencrypt  should have an additional desirable property. A set K of sufficient size should reflect a distribution of numbers that are statistically random with respect to each other. The same should hold for a set Kencrypt of sufficient size, but additionally, each member of the set Kencrypt should also reflect a statistically random distribution with respect to the digits contained in the number, as it is a property of irrational numbers that there is no repeating pattern of digits in any infinitely precise representation of the number--any repeating detectable pattern would make the number rational by definition.

 

It is intuitive that this is a desirable property of integers whose digits can then be used to as indeces for substitution, transposition, or bitwise XOR.

 

Consider a degenerate example of the algorithm which was inspired by the idea of using an single random index into the number PI as a key for a cipher.

 

For purposes of ongoing elucidation, we restrict the plaintext material to base-10 integers.

Choose L = 10. Restrict the selection of kn such that 0 <= kn => 9 where the kn are used as indeces, and such that kn restrict the choice of irrational numbers PI for all the irx chosen.

For reference:

PI ~= 3.141592654

[sic. -- This section was written on an airplane, so digits beyond what I memorized are fudged. ]

My Fake PI = 3.1415926514213562373095

 

K = { 0, 9, 3, 3, 3, 3, 3, 5, 1, 8 }

Kirr = { PI, PI, PI, PI, PI, PI }

Kencrypt = { ikselect( PI, 5, 10 ), ikselect( PI, 1, 10), ikselect( PI, 8, 10 ) }

            = { 9265142135, 4159265142, 1421356237 }

 

 

The options for how to use these to implement some a simple block cipher are myriad, and ultimately, I would prefer to use matrices of high dimensionality to implement the actual substitution and transposition, but here, we restrict to block size of 4 (L MUST BE EQUAL TO BLOCK SIZE FOR THIS particular cipher) and simple scalar transposition and substitution. [NOTE: its worth investigating commutative properties of substitution and transposition to decide on ordering, but for now, lets just say we go a plaintext number at a time, choosing its transposition and substitution. Let KAfter a full block has been completed in this manner, a bit-wise XOR with Kxor can be performed.

 

Define trans( p(n), k ) = k(n), where n is the digit index into the key material. Of course modular arithmetic can yield the same result. There are definitely uniqueness issues here--solution could be to take enough key material such that collisions can always be resolved by moving further into the digit stream. For now, if a position mapping has already been consumed, subsequent non-unique mappings are marked and redistributed right-to-left in the remaining slots.

[Note: can this be exploited to make the function one-way, where a private key part indicates how the non-unique substitution possibilities are used? A fourth key that provides a transposition map for non-unique substitutions as a function of index in the block?]

 

Define sub( p(n), k ) = k(n) Since there are uniqueness issues here as well, we back-fill left-to right into after a rotational shift of index 1.

 

Kencrypt = { 9265142135, 4159265142, 1421356237 }

Plaintext block: 1234567890

 

trans( 1, Ktrans ) = 4 position

trans( 2, Ktrans ) = 1 position

trans( 3, Ktrans ) = 5 position

trans( 4, Ktrans ) = 9 position

trans( 5, Ktrans ) = 2 position

trans( 6, Ktrans ) = 6 position

trans( 7, Ktrans ) = 5 position--> taken, 7th slot empty

trans( 8, Ktrans ) = 1 position --> taken, 8th slot empty

trans( 9, Ktrans ) = 4 position --> taken, 9th slot empty

trans( 0, Ktrans ) = 2 position --> 10th slot empty

3rd slot remains unfilled.

 

Given the temporary collision solution above, the transposition result becomes: 25_136____, with 3,7..0 unassigned. Filling the slots we get: 2501369873

 

The substitution phase is simpler:

Given the key 1421356237, 0->1, 1->4, 3->2, 3rd slot empty, 4-> 3, 5->5, 6 -> 6, 7th slot empty, 8th slot empty, 9->7

2501369873

431_267___

leaving 1873 unsubstituted: rotate left-right 1 space -> 8731, backfill

------------------

4318267731

 

Then XOR with Kxor

 

4318267731 XOR 9265142135 = 13578883108

 

Of course, showing that a single encrypted message bears no resemblance to the original plaintext proves nothing, but it illustrates the basic ideas. Many variations on the ideas are available.

 

 

Section II: Stream Cipher Concept

 

Remember, the original attraction to use of irrational numbers was around use of the residue of the numbers as a never ending source of pattern-less digits, for use as a mask for other data similar to a one-time pad, where the key is really the integer-index of the starting place in the residue used to create the mask, Again, many ways of using a residue such as this are available. Additionally, it should be noted that the one-time pad is only provably secure if it is used only once. I have a number of concerns about detectable patterns not in the sequence of digits of a residue itself, but in successive groupings of them. [More on this later]. For now, a simple of what I have in mind, using PI and the square root of 2.

 

I call this algorithm a degenerate illustration because of the limitations on the set of irrational numbers to choose from, and because the indices into the residue of the irrational numbers used for key material should be collectively large enough to deter brute-force attack.

 

Consider the square root of two, PI, for reference, followed by a fake message. [The PI in use here is also fake in the same sense as the one used in the previous section].

Square Root of 2:      1.4121356237095

PI                                 3.1415926514213

Plaintext Message:   1098765432

 

Suppose we choose a key consisting of {2,3} which denote the indeces of PI and sqrt(2) into which we will advance to begin padding. We'll use bit-wise XOR for simplicity, but other strategies are probably more desirable,

Message index 0 --> iPI(2) XOR iS2(3) XOR P(0) = 1 XOR 1 XOR 1 = 1

Message index 1 --> iPI(3) XOR iS2(3) XOR P(1) = 5 XOR 3 XOR 0 = 2

Message index 2 --> iPI(4) XOR iS2(3) XOR P(2) = 9 XOR 5 XOR 9 = 5

Message index 3 --> iPI(5) XOR iS2(3) XOR P(3) = 2 XOR 6 XOR 8 = 13

Message index 4 --> iPI(6) XOR iS2(3) XOR P(4) = 6 XOR 2 XOR 7 = 12

Message index 5 --> iPI(7) XOR iS2(3) XOR P(5) = 5 XOR 3 XOR 6 = 4

Message index 6 --> iPI(8) XOR iS2(3) XOR P(6) = 4 XOR 7 XOR 5 = 2

Message index 7 --> iPI(9) XOR iS2(3) XOR P(7) = 2 XOR 0 XOR 4 = 6

Message index 8 --> iPI(10) XOR iS2(3) XOR P(8) = 1 XOR 9 XOR 3 = 11

Message index 9 --> iPI(11) XOR iS2(3) XOR P(9) = 3 XOR 5 XOR 2 = 6

 

RESULT becomes Ciphertext = {1,2,5,13,12,4,2,6,11,6}

 

Mapping the resulting text back into a representation equivalent to the original is a matter that has many solutions and is left for now since the point of the illustration has been made. Of course, as noted above, while most numbers are irrational, finding them and calculating them to sufficient precision to avoid re-use is worth putting on the list of things to consider the feasibility of.

 

Section III: Implementation

 

After sitting down to see if I could implement something to work with these ideas, it occurred to me that I hadn’t thought through the diffusion part of the problem very well, and what resulted is an algorithm that uses arbitrary length residue from irrational numbers in three phases:

1)      Bit Diffusion

2)      Byte Diffusion

3)      Mask Encryption

 

I build a little application that uses some of my favorite irrational numbers, and implements an algorithm whose key is the tuple: < KeyLength, BitDiffusionSource, ByteDiffusionSource, MaskSource, BitDiffusionResidueIndex, ByteDiffusionResidueIndex, MaskResidueIndex >

 

The non-trivial elements are the source and residue index members, which together, specify an irrational number to use as key material, and an index into the decimal representation of that number at which the key material starts. Consider the example:

< 256, e, Pi, Phi, 1543, 0, 9980 >

The algorithm will select 3 256-byte vectors of key material. The 256 digits starting at the 1543rd digit of precision will be used as a bit-diffusion key. The first 256 digits of Pi will be used to implement byte-wise diffusion, and the 9980th digit of precision in the golden ratio will be the start index of the 256-byte mask to be used in the final phase.

 

Much remains to be done, and the primary interest was in the feasibility, future work will look at better algorithms for creating bitwise and rearrangements of data before the final masking stage. The first prototype simply uses the diffusion key material to create the reorderings of bits and bytes that are unique with respect to key material, and that maximize distance between original and eventual location.


 

The results:

The application, in its opening state, features an area to enter plaintext, perform encryption and decryption, and observe that the results hopefully have the properties we want out of an encryption algorithm.

 

 

 

Key Specification controls allow the user to select an irrational number for each key type, along with an overall length. A grid below breaks all the data used up into 16 byte blocks, so that detail views can be observed. Here, I’ve chosen a 261 byte key length, and various indeces into the residue of the square root of 2, Pi, and Phi—the resulting material is displayed for verification.

 

 

Choose a plain-text:

Very bad terrorists are coming. We don't know when, or what they're going to do, but we know that they just want everyone to feel terrible. Which is why we need more law enforcement

 

Resulting Ciphertext:

V`u|(dfm)}curnphpsq"b{a'fgohje(#Wc%ljo$v"jikw(kgm$"fv'u`fr!sklz!vb$aham`$wn)bo, cp}"vm(cnht$s`ds&uog|"htr|&pegt$grlu~lhc)vf"fbfm!tltqokkg/&W```k'i{&qix%qb#j`ma#nkzf#nhr"`j`hwk`lcjpX^

 

Looks obscure, but I have not implemented test for randomness yet, and I can tell from looking that I need a better transformation on the decimal representations to get better diversity from the key material. More specifically, the key material needs to be better manipulated to match the entropy of the message material.

 

At least it features the highly desirable property of correctness when decrypting!

 

 

 

 

The data grid allowed me to examine individual byte and bitwise diffusion scenarios, 16 bits or bytes at a time respectively:

 

 

Conclusion:

Not yet concluded. Much to be done.

Feedback and ideas warmly welcomed, since this is obviously nascent work, and reflects a lack of formal training in the field. Be gentle though.

mailto:chris@rossbach.to

 

 

 

Section IV: Other notes, perhaps nonsense, collected in no particular order, and left as further avenues to explore if such exploration is feasible and justifiable.

 

1. Other functions tending to return irrational numbers (non-exhaustive…)

 

2. Consider using Navier-Stokes equation. The start state is representation is used to build encryption key material.

 

3. Consider using Lorenz attractor --> start state as key to creating key material: deterministic non-periodic flow as a source of pattern-less information…

 

4. Smale's horse shoe. What about stretching, bending, folding and compressing multi-dimensional matrices of text, using and eliminating nulls to account for the discreet nature of the underlying data… Other complex topologies could be used, and all amount to interesting transpositions, but making a chosen topology part of a key, makes transposition highly variable.

 

5. Pattern recognition v. Non-linearlity ideas:

If a pattern is produced by the behavior of a function that is recognizable in a local neighborhood, but after several iterations diverges toward chaos, how can the recognizable pattern be used to seduce a would-be decryptor? Since chaotic functions have ultimately recognizable patterns, are they harmonic to the extent that if you mask X with Mandelbrot at magnification Y, can you reproduce X with a different magnification sufficiently accurately to recover the original data? 

 

6. Lorenz' McBee machine--discovered using only 3 digits of precision at start state for 12 inputs produces chaos fairly quickly if you don't know the remaining 3 digits of the residue to make the input accurate. Consider a McBee machine start state where the 3 lowest precision digits of each input form a key, and the output of the machine is a mask that can be transformed into key material to encrypt data....