Thanks Provoni.
That did not look faster, and it wasn't – about 20% slower in normal use.
I couldn't see how the number of rounds would have any effect but looked at 100, and it was still slower.
Cryptanalysis
-
- Posts: 4307
- Joined: Jan 02, 2017 0:34
- Location: UK
- Contact:
-
- Posts: 4307
- Joined: Jan 02, 2017 0:34
- Location: UK
- Contact:
Re: Cryptanalysis
I have found a flaw. I was doing something else with KnuthRange and discovered that it had a perfectly uniform distribution. I did not believe that. After some investigation, it turns out that '(seed and 511) - 256' has a period of 512. So, after 512 KnuthRange requests the '(seed and 511) - 256' starts repeating. That is bad.
The following compares two arrays v() and w().
As is the arrays are equal, NotEqual = 0, showing a repetition.
Uncommenting the two commented statements and the arrays are not equal, NotEqual = 512, showing fresh sequences.
The solution was straightforward. After 512 KnuthRange requests seed is incremented by one. At that point, we have no idea what the value of seed is. However, seed is not the issue - '(seed and 511) – 256' is.
The Walrus text is 186 bytes so I looked at s = s+s+s+s+s+s+s+s+s+s ie 1860 bytes => 3.63 x 512.
The decryption was fine.
I then played around with enc and dec without issue.
Without the update, the 1860 bytes took 80 microseconds using two initial seeds and three rounds each. With the update, the time increased to 92 microseconds, costing an additional 12.5%. That is not a problem after '(seed and 511) – 256' doubled our speed.
Should I have known '(seed and 511) – 256' has a period of 512? Perhaps Melissa O'Neill or Sebastiano Vigna would, but then they are professors, and I am not.
Latest pairing:
The following compares two arrays v() and w().
Code: Select all
Function KnuthRange( ByRef seed As ULongInt ) As LongInt
seed = 6364136223846793005ull * seed + 1442695040888963407ull
Return CLngInt ((seed And 511) - 256)
End Function
Dim As ULong count
Dim As ULongInt seed = 1254834
Dim As Long v(-256 To 255)
Dim As Long w(-256 To 255)
Dim As ULong NotEqual
For i As Long = -256 To 255
v(i) = KnuthRange(seed)
'count += 1
Next
'if count = 512 then seed += 1
For i As Long = -256 To 255
w(i) = KnuthRange(seed)
Next
For i As Long = -256 To 255
If v(i) <> w(i) Then NotEqual += 1
Next
Print NotEqual
Sleep
Uncommenting the two commented statements and the arrays are not equal, NotEqual = 512, showing fresh sequences.
The solution was straightforward. After 512 KnuthRange requests seed is incremented by one. At that point, we have no idea what the value of seed is. However, seed is not the issue - '(seed and 511) – 256' is.
The Walrus text is 186 bytes so I looked at s = s+s+s+s+s+s+s+s+s+s ie 1860 bytes => 3.63 x 512.
The decryption was fine.
I then played around with enc and dec without issue.
Without the update, the 1860 bytes took 80 microseconds using two initial seeds and three rounds each. With the update, the time increased to 92 microseconds, costing an additional 12.5%. That is not a problem after '(seed and 511) – 256' doubled our speed.
Should I have known '(seed and 511) – 256' has a period of 512? Perhaps Melissa O'Neill or Sebastiano Vigna would, but then they are professors, and I am not.
Latest pairing:
Code: Select all
Function KnuthRange( Byref seed As Ulongint ) As Longint
seed = 6364136223846793005ull * seed + 1442695040888963407ull
Return CLngint ((seed and 511) - 256)
End Function
Sub EncDec( Byref message As String, Byval seed as Ulongint, Byval rounds As Ulong, ByVal flag As Long )
Dim As Ulong count
For i As Ulong = 1 to rounds
For j As Ulong = 1 To Len(message)
message[j-1] = Asc(message, j) + KnuthRange( seed ) * flag
count += 1
If count = 512 Then seed += 1 : count = 0
Next
Next
End Sub