Home-brewed encryption

[deltarho[1859]]

OK, your code makes sense but I still have an issue.

To simplify I looked at FB's Rnd as our generator and used Cast(Ulong, Rnd*2^32) as our 32-bit random number.

If we do a bucket load of '(Cast(Ulong, Rnd*2^32) Mod (Two-One+1)) + One' we should tend to (Two+One)/2.

So, consider this:

Code: Select all

Dim As Long One, Two, i, j
Dim As Double tot
 
Randomize
 
One = 100 : Two = 400
Print (Two+One)/2
Print
 
For i = 1 to 10
  tot = 0
  For j = 1 to 10^8
    tot += (Cast(Ulong, Rnd*2^32) Mod (Two-One+1)) + One
  Next
  tot = tot/10^8
  Print tot
Next
Print
Print "Done"
 
Sleep 

I get

Code: Select all

 250

 250.01042134
 249.98906134
 250.01741886
 249.99888382
 250.01529021
 249.98313448
 249.99826763
 249.98206929
 250.00873917
 249.99681567

Done

That is the Mod method is working.

However, if we use One = -857 and Two = 857 I get

Code: Select all

 0

 2146046036.586742
 2146303777.516746
 2146107025.05562
 2146282474.496294
 2146310477.693399
 2146113081.000696
 2145999049.627478
 2146383019.678879
 2146562334.515463
 2146294414.559095

Done

Something is seriously wrong here.

How about One = -100 and Two = -50 I get

Code: Select all

-75

 4294967222.172671
 4294967222.169378
 4294967222.173999
 4294967222.173287
 4294967222.172093
 4294967222.172445
 4294967222.170393
 4294967222.172475
 4294967222.173421
 4294967222.172063

Done

Added: It seems to me that we need to map our lower and upper limits into a domain where only positive values exist, do our arithmetic and then map back.

For example if we added 862 to -857 and 857 and then subtracted 862 at the end I get

Code: Select all

 0.04980794999999999
-0.01776288999999998
 0.009281009999999978
-0.00547114999999998
 0.09483583000000001
 0.04208870999999997
-0.02586748999999999
 0.03212702000000001
 0.01198539999999998
 0.01648302000000002

which is pretty close to the expected value of zero.

Adding 105 to -100 and -50 and then subtract 105 I get

Code: Select all

-75.00048656
-74.99729623
-74.99963022
-74.99998549
-74.99852961000001
-74.99874134
-75.00022214000001
-75.00174626
-75.00139839000001
-75.00080697999999

Rather than decide whether to map or not which will cost time we could map whether we needed to or not and remove the costly decision.

[deltarho[1859]]

Here we are mapping the lower and upper limits whether needed or not.

I am not getting any problems now because Mod is being fed a positive lower and upper limit.

What I have not fathomed out yet is why the Mod method can only be relied upon when both the lower and upper limit are in the positive domain.

Code: Select all

Dim As Long One, Two, map, i, j
Dim As Double tot
 
Randomize
 
One = -857 : Two = 857
Print (Two+One)/2
map = Abs(One) + 5
One = One + map ' map whether needed or not
Two = Two + map ' ditto

Print
 
For i = 1 to 10
  tot = 0
  For j = 1 to 10^8
    tot += (Cast(Ulong, Rnd*2^32) Mod (Two-One+1)) + One
  Next
  tot = tot/10^8
  Print tot - map ' map back into our original domain
Next
Print
Print "Done"
 
Sleep

[dodicat]

I tried with dmod, - OK.(Which told me something odd is going on)
If I cast your ulong generator to long then add the one - OK. -- With -857 to 857 range
(well, one is a long anyway, but I didn't think you would have to cast ulong to long to add a long)
If x mod y=z, looks like if x as ulong so is the answer

Code: Select all

Dim As Long One, Two, i, j
Dim As Double tot
var t=timer
 

 #define dmod(x,y) (y)*Frac((x)/(y))
 
 
One = -857 : Two = 857
Print (Two+One)/2
Print
 Randomize t
For i = 1 to 10
  tot = 0
  For j = 1 to 10^8
    tot += clng(Cast(Ulong, Rnd*2^32) Mod (Two-One+1)) + One
  Next
  tot = tot/10^8
  Print tot
Next
Print
Print "Done 1"
'dmod confirm
tot=0
randomize t
For i = 1 to 10
  tot = 0
  For j = 1 to 10^8
     tot+=dmod(Cast(Ulong, Rnd*2^32),Two-One+1)+one
  Next
  tot = tot/10^8
  Print tot
Next
Print
Print "Done 2"


Sleep
 

[deltarho[1859]]

In PCG32II I have replaced the asm with

Code: Select all

map = Abs(One) + 5
One = One + map
Two = Two + map
Return (TempVar Mod (Two-One+1)) + One - map

which is over 60% faster than the asm - a very significant increase.

I have tried a variety of ranges using PCG32II with the revised code and all seems well.

However, we must now limit Two to be <= 2^31-1 - Abs(One) - 5 for the integral range. I shouldn't think that many, if any, would be using such a large value of Two.

[dodicat]

But it is very confusing, freebasic is usually quite friendly, but not always.

Code: Select all

print 2024863461 mod 1715 -857
print 2024863461ul mod 1715 -857
print 2024863461ull mod 1715 -857
print

print 2036278952 mod 1715 -857
print 2036278952ul mod 1715 -857
print 2036278952ull mod 1715 -857
sleep
  

[deltarho[1859]]

I have just put '2024863461 mod 1715 -857' and '2036278952 mod 1715 -857' into Online Big Number Calculator and High precision calculator and got -166 and 285 repectively.

So, the second and third Prints are wrong. The question is then do we have a bug in Mod?

So, with my post beginning "OK, your code makes sense..." I replaced

Code: Select all

tot += (Cast(Ulong, Rnd*2^32) Mod (Two-One+1)) + One

with

Code: Select all

tot += Clng(Cast(Ulong, Rnd*2^32) Mod (Two-One+1)) + One

100/400, -857/857, and -100/-50 now work as required.

In PCG32II I removed my mapping into a positive domain and tried

Code: Select all

Return Clng(TempVar Mod (Two-One+1)) + One

I get this for a few ranges

Code: Select all

-400/400 0 -0.02122073
-100/-50 -75 -75.00079538999999
-100/200 50 49.99497156
50/100 75 74.99797881000001

The second item is the expected value for an infinite test as opposed to 10^8.

The speed is a tiny bit less than the mapping method because of the Clng but it is still 60% faster than the asm method and Two does not have it's maximum value cutback to accommodate the mapping shift.

It seems then your Mod method is OK now provided we tweak it with Clng, extraordinary.

I will test the living daylights out of this tweak with a view to revising PCG32II.

If you have time see if you can break the tweak.

Looks like well done, dodicat.

Added: Clng is about 2.3 times faster than dmod so Clng has it.

There is now hardly any difference in speed between PCG32II's integral range and floating-point range. Magic!

[deltarho[1859]]

@dodicat

I gave PCG32II a good work out using the Clng code and it didn't put a foot wrong.

I have published an updated PCG32II and revised the Help file giving you credit for the new integral range code.

It is worth noting that in 64-bit mode the Clng method is only 25% faster than the asm method. That is still a significant increase. For some reason PCG32II really shines in 32-bit mode but the 64-bit compiler does not make a good job of it. 64-bit is still much faster than any of the FB generators running in 64-bit mode but the roof comes off in 32-bit mode.

[dodicat]

Thanks deltarho.
"The upper class can kiss my ass,
DODICAT is up there at last."

[deltarho[1859]]

DODICAT is up there at last.


You already were for as long as I have been a member and goodness knows for how long before that and many members would reckon the same I shouldn't wonder.

I have noticed that many class acts underrate themselves which drives them to try to better themselves, and they become an even better class act. I have seen this with runners who are critical of their performance at an interview just after breaking a world record. Most of the top tennis players underrate themselves. You may have read: "The more incompetent someone is the more likely they are to overestimate their competence". I think the opposite may be true: "The more competent someone is the more likely they are to underestimate their competence".

[deltarho[1859]]

The asm code in MsWsRange.bas, in post #4, can now be replaced with 'Return Clng(TempVar Mod (Two-One+1)) + One'. This only gives an increase in speed of about 16% but this is because of the twin random number aspect employed to give us prediction resistance.

[deltarho[1859]]

Bit of a logic check here. Originally, with MsWs, I was going to use two generators MsWs0 and MsWs1 but then decided to have two engines in the one generator so now I only needed MsWs and not MsWs0 and MsWs1 but I still kept them and there was no need to. Worse still only MsWs0 was being used and Seed1 and Sequence1 were not, and they got initialized as zero. Oh dear! So we now only use MsWs and all the 'seeding' is being utilized.

Since, by using two engines, brute force is not practical then there is no need for Rounds, as with using PCG32II.

I see no reason to use a range other than (0,255) so the range function can have a simplified return of 'Clng(TempVar Mod 256)', using dodicat's Clng/Mod method.

The text example is now coming in at less than 3 microseconds. The 1MB file is coming in at 0.014s (average of 6 tests).

Revised code.

Code: Select all

'#Console On
#Include "MsWsRange.bas"
#Define CrLf Chr(10, 13)
 
' ------------------------------------------------------------
Sub EncDec( message As String, ByVal Seed0 As ulongint, ByVal Sequence0 As ulongint, _
                               ByVal Seed1 As Ulongint, ByVal Sequence1 As Ulongint, _
                               ByVal flag As Long )
' flag = 1 for encryption and -1 for decryption
Dim As MsWsParams MsWs
Dim As Long i, j, k = Len(message), temp
MsWs.MyRandomize( Seed0, Sequence0, Seed1, Sequence1 )
For j = 1 To k
  temp = MsWs.Range
  message[j-1] = Asc(message, j) + temp*IIf( (temp <= 128), flag, -flag ) ' Random addition/subtraction
Next
End Sub
' ------------------------------------------------------------
 
' Example usage
Dim s As String
Dim i As Long
Dim As Double t
 
s = "The time has come the walrus said" + CrLf
s += "to talk of many things" + CrLf
s += "of shoes, and ships, and sealing wax," + CrLf
s += "of cabbages, and kings," + CrLf
s += "and why the sea is boiling hot," + CrLf
s += "and whether pigs have wings."
 
'Open "Test.txt" For Binary As #1
's = String(Lof(1), 0)
'Get #1, , s
'Close #1
 
Print s + CrLf
t = Timer
EncDec( s, 45, 18, 69, 123, 1 )
t = Timer - t
Print s + CrLf
EncDec( s, 45, 18, 69, 123, -1 )
Print s
Print
Print t*1000000
 
Sleep

MsWsRange.bas

Code: Select all

Type MsWsParams
  Declare Constructor
  Declare Sub MyRandomize( ByVal As Ulongint = 0, ByVal As Ulongint = 0, _
                                ByVal As Ulongint = 0, ByVal As Ulongint = 0 )
  Declare Function Range() As Long
  Seed0 As Ulongint
  Sequence0 As Ulongint
  Seed1 As Ulongint
  Sequence1 As Ulongint
End Type
 
Sub MsWsParams.MyRandomize( ByVal Seed0 As Ulongint = 0, ByVal Sequence0 As Ulongint = 0, _
                                   ByVal Seed1 As Ulongint = 0, ByVal Sequence1 As Ulongint = 0 )
  this.Seed0 = Seed0 : this.Sequence0 = Sequence0
  this.Seed1 = Seed1 : this.Sequence1 = Sequence1
End Sub
 
Function MsWsParams.Range() As Long
  Dim TempVar As Ulong
  This.Seed0 *= This.Seed0 : This.Sequence0 +=  &Hfedc69454fc250b1ULL: This.Seed0 += This.Sequence0
  This.Seed0 = ( This.Seed0 Shr 32 ) Or ( This.Seed0 Shl 32 )
  This.Seed1 *= This.Seed1 : This.Sequence1 += &Hfedca2b5c97283d5ULL : This.Seed1 += This.Sequence1
  This.Seed1 = ( This.Seed1 Shr 32 ) Or ( This.Seed1 Shl 32 )
  TempVar = This.Seed0 Xor This.Seed1
  Return Clng(TempVar Mod 256)
End Function
 
Constructor MsWsParams
  This.MyRandomize()
End Constructor

[deltarho[1859]]

Just to make sure that nothing untoward has crept in here is the average of 10^8 requests of MsWs.Range which has a theoretical value of 127.5, I get 127.49894802.

Code: Select all

'#Console On
#Include "MsWsRange.bas"

Dim As MsWsParams MsWs
Dim As Long i
Dim tot As Double
Dim As Ulongint Seed0 = 123, Sequence0 = 45, Seed1 = 456, Sequence1 = 89

MsWs.MyRandomize( Seed0, Sequence0, Seed1, Sequence1 )
For i = 1 To 10^8
  tot += MsWs.Range
Next
Print tot/10^8
Sleep

[deltarho[1859]]

Actually, dodicat's method becomes rather obvious now.

(TempVar Mod 256) will have a remainder of 0, 1, 2, ..., 255.

If TempVar is random and uniformly distributed so will be the remainder.

For a range of 'one to two' we simply subtract one from the lower bound and subtract one from the upper bound and get '0 to two - one'.

So, we use (TempVar Mod (two - one + 1)) + one.