The B.O.R.N. (Binary Oblong Random Number) Engines             Switch view to Greek

Alternative Applications in Cryptography                            (Windows) encoding!

                                                                                         by Panagiotis C. Karagiorgis

Declaration of notations used                                                      Ó 2006            

χÎΧ : element χ belongs to set Χ.                                      phone:   (30) 210.825.3209

"χ : for every χ.                                                                e-mail:   karagiorgis@tellas.gr

$χ : there exists some χ.

[χ] : the integer part of χ³0.

Χ-Υ : set of all contents of Χ not belonging to set Υ.

“:” : such that.

Ν={1,2,3,…} is the set of positive integer numbers.

Ν₀={0,1,2,3,…}=Νîø{0} the set of nonnegative integers.

Ζ={0,±1,±2,±3,…} is the set of all integer numbers.

x»y : numbers x and y are similar in size.

The congruence χºψ (mod β), where appearing, denotes that integers χ and ψ give the same nonnegative remainder, once being divided by a certain positive integer β.

The function mod(α,β) is the nonnegative remainder, upon division of αÎΖ by βÎΝ.

The expression “numbers … are identical/different modulo β” means that, once divided by a certain positive integer β, give the same/different nonnegative remainder.

The function gcd(α,β) gives the greatest common divisor of numbers α,β: (α,β)ÎΝ².

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

The first two theorems (1 and 2) state that, if μ=2^ν, where νÎΝ, then:

5^μº1 (mod 4·μ)            and       μ£η "ηÎΝ: 5^ηº1 (mod 4·μ).

 

Theorem 1.

If μ=2^ν, for νÎΝ, then 5^μº1 (mod 4·μ).

 

Proof

When ν=1, then μ=2¹=2 and it is obvious that 5²º1 (mod 4·2).

To proceed by induction, we accept that, for some κÎΝ, the next congruence holds:

5^μº1 (mod 4·μ), where μ=2^κ.

Then, 5^μ-1º0 (mod 4·μ) Þ (5^μ-1)·(5^μ+1)º0 (mod 4·2·μ) Þ 5^2·μ-1º0 (mod 4·2·μ). Consequently 5^2·μº1 (mod 4·2·μ) and since 2·μ=2^κ+1, it follows that: 

5^λº1 (mod 4·λ), where λ=2·μ=2^κ+1.

The induction is complete and, therefore, 5^μº1 (mod 4·μ) "νÎΝ, where μ=2^ν.

 

Theorem 2.

If μ=2^ν, for νÎΝ, then μ£η "ηÎΝ: 5^ηº1 (mod 4·μ).

 

Proof

From the 1^st theorem, it follows (since μ=2^ν) that the least positive integer τ, for which 5^τº1 (mod 4·μ), has to be of the form τ=2^ρ, where ρÎΝ (0<ρ£μ), because, for τ=2⁰=1 we would get the contradiction 5¹º1 (mod 4·μ), where 4·μ³8.

We also observe that the assumption ρ<μ would justify the congruence:

5^μ/2º1 (mod 4·μ), for μ=2^ν, where νÎΝ.

When ν=1, then the last congruence is obviously false.

We’ll show by induction that this is also false "νÎΝ, based on the assumption that:

$κÎΝ-{1}: 5^μ/2º1 (mod 4·μ), for μ=2^ν, when ν=κ.

Then, for μ=2^κ, we would get 5^μ/2-1º0 (mod 4·μ) ) Þ (5^μ/4-1)·(5^μ/4+1)º0 (mod 4·μ)

            Þ 5^μ/4-1º0 (mod 4·μ/2), given that 5^μ/4+1º2 (mod 4).

Hence: 5^(μ/2)/2º1 (mod 4·μ/2), and since μ/2=2^κ-1, it follows that:

5^λ/2º1 (mod 4·λ), where λ=μ/2=2^κ-1.

As we just show, the induction hypothesis contradicts the initially realized fact, that the congruence 5^μ/2º1 (mod 4·μ) is false, when ν=1 and μ=2^ν=2¹.

Consequently, if μ=2^ν, for νÎΝ, then μ£η "ηÎΝ: 5^ηº1 (mod 4·μ).

Theorem 3.

If ρº1 (mod 2), then and only then, the retrospective sequence:

λ_κ=mod(α·λ_κ-1+ρ,2^ν) "κÎΝ, where (ν,α)ÎΝ²: αº5 (mod 8), λ₀ÎΝ₀ (and ρÎΝ₀),

admits (in any circular order) all values λÎΝ₀: λ<2^ν

(in mathematical terms:  "(ν,k)ÎΝ² and "λÎΝ₀: λ<2^ν  $κÎΝ: κ>k and λ_κ=λ).

 

Proof

The converse of the implication (the “only then” part) proposed in this theorem, can be proven, rather easily, by contradiction. Because, if ρ was an even number, then λ_κ=mod(α·λ_κ-1+ρ,2^ν) would result (beyond some λ_κ-1 of even value) to a circular sequence of even terms, only. Surely, there is at least one even λ_κ-1, considering that:

"(ν,k)ÎΝ² and "λÎΝ₀: λ<2^ν   must  $κÎΝ: κ>k and λ_κ=λ,

counts for λ=0, as well. But, then, the above statement would be false for λ=1 (which is impossible).

To verify the direct implication, one is obliged (for ν>2) to implement the above theorems (1 and 2), as well as a corollary from the Diophantic-equations theory.  

(For ν£2, we have αº1 (mod 2^ν) Þ λ_κ=mod(λ_κ-1+ρ,2^ν) "κÎΝ and, thereby, the equivalent to the congruence ρº1 (mod 2) condition gcd(ρ,2^ν)=1 is necessary and sufficient, for the above sequence λ_κ to run over all values λÎΝ₀: λ<2^ν.)

 

By theorems 1 and 2, we confirm, step by step, the following results:

α΄. For μ=2^ν, where νÎΝ, and since 5^τº1 (mod 4) "τÎΝ, the congruences:

5^μº1 (mod 4·μ) and μ£η "ηÎΝ: 5^ηº1 (mod 4·μ)

imply that, for τ=1,2,3,…,μ , the numbers 5^τ admit typically all values 1,5,9,…,4·μ-3 modulo 4·μ, in a different order.

β΄. For any constant odd positive integer σ<μ, and for τ=1,2,3,…,μ , the numbers 5^σ·τ form a complete coverage of all values 1,5,9,…,4·μ-3 modulo 4·μ, in some order, depending on the choice of σ.

γ΄. For all acceptable values of σ, the constants 5^σ cover precisely the values 5,13,21,…,4·μ-3 modulo 4·μ, and this makes us consider the circular retrospective sequence: ρ_κ=mod(α·ρ_κ-1,β) "κÎΝ and for any ρ₀º1 (mod 4), by implementing the constants αÎ{5,13,21,…,4·μ-3} and β=4·μ (for μ=2^ν, where νÎΝ). As a result, ρ_κ runs over the values 1,5,9,…,4·μ-3 modulo 4·μ, in some circular order, determined by the choice of constant α.

δ΄. For π_υ=(ρ_υ-1)/4 "υÎΝ₀, we find the retrospective formula of the transformed circular sequence π_κ=mod((4·a+1)·π_κ-1+a,μ) "κÎΝ, for π₀ÎΝ₀ and aÎ{1,3,5,…,μ-1} (where π₀=(ρ₀-1)/4 and a=(α-1)/4). Now, π_κ runs over all different values modulo μ.

ε΄. For χ_κ=mod(π_κ+b,μ) "κÎΝ, with χ₀=π₀+b and bÎΝ₀ arbitrary, we identify the retrospective form of this third sequence, as χ_κ=mod((4·a+1)·χ_κ-1+(1-4·b)·a,μ) "κÎΝ, where χ₀ÎΝ₀. Again, χ_κ admits all different values modulo μ.

ς΄. For ψ_υ=mod(-χ_υ,μ) "υÎΝ₀, we finally get the fourth retrospective sequence ψ_κ=mod((4·a+1)·ψ_κ-1+(4·b-1)·a,μ) "κÎΝ, with ψ₀ÎΝ₀, which is complementary to the third one, and leads to the generalization:

(1)     λ_κ=mod((4·a+1)·λ_κ-1+(4·b±1)·a,2^ν) "κÎΝ, for λ₀ÎΝ₀ and νÎΝ.   Obviously:

(2)     "(ν,k)ÎΝ² and "λÎΝ₀: λ<2^ν  $κÎΝ: κ>k and λ_κ=λ.                    Moreover:

(3)     "aÎ{1,3,5,…, 2^ν-1} and "(ν,ρ)ÎΝ²: ρº1 (mod 2)  $bÎΝ₀: ρº(4·b±1)·a (mod 2^ν) ,

considering that a is odd, and one can chose 4·b±1 among all odd positive integers. According to the Diophantic-equations theory, gcd(a,2^ν)=1 implies that, regarding the value of 4·b±1, there is a unique modulo 2^ν, solution ξ. If ν>1, then ξº±1 (mod 4) and b=-(±1-mod(ξ,2^ν))/4, with ± matching, everywhere, the appropriate sign in 4·b±1 (either + or -). When ν=1, then a=1 Þ b=0. As for a, we realize that:

(4)  "(ν,α)ÎΝ²: αº5 (mod 8)

$ qÎ{0,1,2,3}, aÎ{1,3,5,…, 2^ν-1}: 4·a+1º2^ν·q+α (mod 2^ν+2) , because the integer (α-1)/4 is odd. For qÎ{0,1,2,3} being arbitrary (excluding the case ν£2, when q=mod((1-α)/4-ρ,ν²) "ρÎΝ₀), we get the short formula: a=mod((2^ν·q+α-1)/4,2^ν).

Relations (1), (2), (3), and (4) prove, together, the direct implication of this theorem.

 

Theorem 4.

The recursively computable value:         x_u+1=mod(g-(x_u-1)²/2,2^u),

for x₃=1 and "(g,u)ÎΝ²: gº1 (mod 4) and u³3,

is a unique, modulo 2^u, solution of the simultaneous congruences:

x²º2·g-1 (mod 2^u+1)                 and                   xº1 (mod 4) .

 

Proof

Consider the retrospective sequence y_u+1=mod(c-2·y_u²,2^u-2), where y₃=0, c=(g-1)/4, and u³3. For x_u=4·y_u+1 "uÎΝ-{1,2}, we have x₃=1, and x_u+1=mod(g-(x_u-1)²/2,2^u) when u>3. We intend to show by induction that, "uÎΝ-{1,2}, the critical congruence (4·y+1)²º8·c+1 (mod 2^u) is equivalent to: yºy_u (mod 2^u-3). Starting with u=3, we have:

(4·y+1)²º8·c+1 (mod 2³) Û (2·y+1)·yºc (mod 1), which is true "yÎZ, as is, always, the congruence yºy₃ (mod 2⁰). Hence, there is at least one suitable u³3, satisfying the equivalence: (4·y+1)²º8·c+1 (mod 2^u) Û yºy_u (mod 2^u-3). The question is, if such a u serves for the following equivalence to hold:

(4·y+1)²º8·c+1 (mod 2^u+1) Û yºy_u+1 (mod 2^u-2).

Before proceeding, assume that the congruences:           (4·y+1)²º8·c+1 (mod 2^u+1)       and

(4·(y+z)+1)²º8·c+1 (mod 2^u+1),

hold simultaneously for some zÎΖ. Then,

2·y²+yº2·(y+z)²+y+z (mod 2^u-2) Þ 0º4·y·z+2·z²+z (mod 2^u-2) Þ

Þ 0º(4·(y+z/2)+1)·z/2 (mod 2^u-3) Þ zº0 (mod 2^u-2),  which implies

that the solution y=y_u+1: (4·y+1)²º2·g-1 (mod 2^u+1), the existence of which shall be proven right away, is unique modulo 2^u-2. Indeed, we have:

(4·y_u+1)²º8·c+1 (mod 2^u) Þ 2·y_u²+y_uºc (mod 2^u-3) Þ (c-2·y_u²-y_u)/2^u-3=r₀ÎZ. Hence:

y_u+1=mod(c-2·y_u²,2^u-2) Þ (c-2·y_u²-y_u+1)/2^u-2=r₁ÎZ Þ r₀·2^u-3+y_u-y_u+1=r₁·2^u-2 Þ

Þ y_u+1=y_u+r·2^u-3, for r=r₀-2·r₁. Then, 2·y_u+1²+y_u+1=2·(y_u+r·2^u-3)²+y_u+r·2^u-3=2·y_u²+y_u+ +(4·y_u+1+r·2^u-2)·r·2^u-3=c+(r·(4·y_u+1+r·2^u-2)-r₀)·2^u-3=c+(r·(2·y_u+1+r·2^u-3)-r₁)·2^u-2 Þ

Þ 2·y_u+1²+y_u+1ºc (mod 2^u-2) Þ (4·y_u+1+1)²º8·c+1 (mod 2^u+1), which had to be shown.

 

 

From theory to practice

1. The sequence τ_κ=(λ_κ+0.5)/2^ν covers uniformly the interval (0,1). For a sufficiently great νÎΝ, the size of μ=2^ν permits us to regard τ_κ as a continuous random variable following the uniform distribution U(0,1). In usual applications, it’s enough to have ν>50. However, for serious implementation in cryptography, special simulations, or other scientific applications, the size required for ν may extend to several millions… 

2. Binary Oblong Random Number (B.O.R.N.) engines are extremely fast, since based on the sequences  λ_κ and τ_κ, the calculations for them being free from time consuming divisions, confined only to multiplications and binary translations. The number of operations is, of course, proportional to ν² and this could be a problem, in the case where ν is very big. To minimize such a problem, one may use a smaller ν, together with a special αº5 (mod 8), it depending on τ=2^λ, ν-4³λÎΝ, and ψÎ{Ö(5)-1,3-Ö(5)}, through the congruence: α^τº4·τ·(2·[ψ·2^ν-4/τ]+1)+1 (mod 2^ν+2).

3. The above optimization technique originates, theoretically, from a property characterizing all simple, natural multiples of the so-called golden ratio: They just tend to have their fractional parts rather uniformly distributed in the (0,1) interval.

Implementing this property in B.O.R.N. engines has the following result: "τ_κ: |τ_κ-χ|<ε, where χÎ(0,1) and ε>0 reasonably small, the future τ_κ+τ, after τ executions, will spread uniformly in the (0,1) interval, as long as ζ lies sufficiently close to any odd integer. We obtain such a distribution for ν-λ=35, 51, 56, 65, …, 303402, 1913791, 3912915, 7868057 and infinite other numbers, for which the random-numbers recycling period, 2^ν, becomes inconceivably extensive.

4. The apparent independence of random numbers generated improves, when the choice of λ is such that: number ζ=2^ν-3·ψ/τ gets close enough to an odd integer and, at the same time, (2^λ=) τ»ν². For instance, if ν=78 and λ=13, then τ=2¹³=8192 (which is similar in size to ν²=6084), and the odd integer 2·[ζ_ψ<1/2]+1 lies sufficiently near to ζ_ψ<1=ψ·2^78-3/8192=3523014627193176565.0241… (for ψ=3-Ö(5)). The formula of α^τ gives α^τº115442143303866009681921 (mod 2⁸⁰), and the respective theory (here advising to implement the 4^th theorem 13 times, repetitively) enables us to calculate α=α₀=α_min(ζ_ψ<1)=126179576654017396061, one of the optimal values for the engine λ_κ=mod(α·λ_κ-1+ρ,2⁷⁸), the effectiveness of which is not influenced by the choice of the odd integer ρ. The value of ρ may be chosen freely (say, ρ=71300379), or based on a truly random λ₀ÎΝ₀: λ₀<2^2·ν-1 (instead of λ₀<2^ν), through the formula: ρ=2·[λ₀·2^-ν]+1.

5. In general, the congruence α^τº4·τ·(2·[ψ·2^ν-4/τ]+1)+1 (mod 2^ν+2) is satisfied by 2·τ different modulo 2^ν+2 integers α, the following: α_2·i+δ=α_δ+2^ν+2·i/τ, για i=0,1,2,…,τ-1 and δ=1 or 0, when ζ=ζ_ψ>1 or ζ_ψ<1, respectively. Obviously, for τ=2 (λ=1), the only incongruent numbers, modulo 2^ν, are α₀ and α₁. When τ>2 (Û τ³4, and λ³2), then all α_2·i+δ are different to each other, modulo 2^ν, provided i<τ/4. For every such α=α_2·i+δ, we set α΄=mod(α^w,2^ν), where w=2^ν-2-1. Then, for ρ΄º-α΄·ρ (mod 2^ν), the generator λ_κ=mod(α΄·λ_κ-1+ρ΄,2^ν), admits in inverse order the terms of λ_κ=mod(α·λ_κ-1+ρ,2^ν). The new generation of engines, thus arising, retains the advantage of maximal distribution and can be used alternatively. The so-called secondary B.O.R.N. generators, in combination with the respective primary, are also suitable for variable string coding and decoding transformations, in packs being originally [ν/8] characters long, before extended by one extra byte, this concealing the transmission code for the current pack. In our example, [ν/8]=[78/8]=9, and the first step, for the sender, is to form the integer χ³0, from the 9 characters of each group. Next, he constructs the term λ_κ-1=64·χ+ω, by choosing an arbitrary ωÎ{0,1,2,…,63}, and computes λ_κ=mod(α΄·λ_κ-1+ρ΄,2⁷⁸), from ρ΄ and α΄=mod(α^w,2⁷⁸), for w=2⁷⁶-1 and for any selection of αÎ{α₀,α₂,α₄,α₆} (since δ=0). In practice, the sender doesn’t need to know the value of α=α_2·i(+δ), provided he knows which iÎ{0,1,2,3} represents each feasible pair (α΄,ρ΄), among the ones corresponding to his 4 private keys α΄, processed with the given value of ρ. The encrypted pack of 9+1=10 bytes transmitted to the recipient is, finally, the quantity n=4·λ_κ+i. Since that fellow knows the values of α₀,α₂,α₄,α₆ (and ρ), he just sets λ_κ-1=[n/4] and α=α_2·i(+δ), for i=mod(n,4), so as to decipher the concrete pack, through λ_κ=mod(α·λ_κ-1+ρ,2⁷⁸). Once χ=[λ_κ/64] is obtained, it actually reveals the 9 characters of that pack. After reading the full series of packs, the recipient can send his response, well encrypted, by simply using his own parameters. The owner of the respective pairs (α΄,ρ΄) will certainly be able to decipher his response.

6. When ν is relatively small, the need for a good choice of ζ gets crucial, and its exact value depends, exclusively, on the difference of the parameters ν and λ. Here, ν-λ=65 (=78-13), and we have the opportunity to construct one more primary generator of typical specifications. By setting ν=77 and λ=12, in this case, we steadily have ν-λ=65 (=77-12), while τ=2^λ=2¹²=4096»5929=77²=ν². So, we have every reason to calculate a few of the optimal τ/2=2048 pairs (α,α΄), and we already known how. (For λ>1, there are always τ/2 such pairs, incongruent modulo 2^ν, while for λ=1, their number is τ=2¹=2.)

Generally, the best choices of ν appear in pairs of successive integers, with partners adjacent λ-values, all arising from a known difference f=ν-λ: |2·[ζ/2]+1-ζ|<ε(f)<0.05, for some decreasing function ε(f)>0, slowly tending to 0, as f tends to ¥. For λ=[log₂(f²)] ή [log₂(f²)]+1, we obtain the respective successive values of ν=f+λ. When f=65, then log₂(65²)=12.0447… and λ=12 or 13. So, ν=λ+65=77 or 78, respectively. 

7. Filtering files through xor bit-operations, with operant a key-file of totally random contents, requires two programs: α) “Key Maker” (rarely used), which produces a reasonably large “binary.key” and β) “Key Holder” (often used), which serves to encrypt or decipher any file. The files being encrypted by the sender are, in practice, already compressed folders with the desired contents, and are sent as attached to an email being addressed to other owners of the exact binary.key file, that was used for encryption. Only a variant part of this large key file applies, each time, and its end determines, automatically, the beginning of the next key part to be used for secret communication, as far as the same pair of correspondents is concerned.