Cryptanalysis

[dodicat]

Deltarho
I notice that you divide by 2^64 each time in your KnuthRange .
It seems faster to use the ulongint seed directly (via mod).

Code: Select all

Function KnuthRange( Byref seed As Ulongint, Byval first As Longint,byval last as longint) As Longint
#define IRangeX( f, l ) Int( seed/2^64*( l+1 - f ) ) + f

if first>last then swap first,last
#define Irange(f,l) clngint((seed mod (((l)-(f))+(1))) + (f))
seed = 6364136223846793005ull * seed + 1442695040888963407ull
Return IRange(first,last)
End Function
 

dim as longint L,last
dim as ulongint seed=1000000000
dim as long a(-1 to 1)
dim as ulong lim=50000000
var t=timer
for n as long=1 to lim
    a(KnuthRange(seed,-1,1))+=1
next n
print timer-t
for n as long=-1 to 1
    print a(n)
    next
sleep

 

[deltarho[1859]]

@dodicat

Ah, your famous Mod method introduced in PCG32II, if I recall correctly. Here is a line from PCG32II's published code:

Code: Select all

Return Clng(TempVar Mod (Two-One+1)) + One ' By dodicat

I have been using the form

Code: Select all

#define IRange( f, l ) Int( seed/2^64*( l+1 - f ) ) + f

where seed is usually Rnd for quite a while.

I never got around to revising that with Mod.

With your test piece, I get 0.423s with Mod compared to 0.807s with the old, classical way.

You wrote "It seems faster". Yes, I think we can say that as in 90% faster.

I did have a speed for the Walrus encryption, but I don't have the time to search for it. Anyway, it is now down to 25 microseconds.

Thanks

[adeyblue]

Deltarho
I notice that you divide by 2^64 each time in your KnuthRange .
It seems faster to use the ulongint seed directly (via mod).

Does crash though

Code: Select all

Dim As Ulongint seed = 123456 '' doesn't matter
Dim as longInt min = &h8000000000000000
Dim as longInt max = &h7fffffffffffffff
Dim as longint num = KnuthRange( seed, min, max ) '' crash

[deltarho[1859]]

I see machine accuracy raises its head again.

A simple warning will do as I cannot see anyone using min, max like those.

[dafhi]

We could do with a better way than 'temp*IIf( (temp <= 128), flag, -flag )' provided that it still produces alternating values as above.

Code: Select all

enum
  encode
  decode
end enum

Sub EncDec( .., ByVal flag As Long = encode )
..
      message[j-1] = Asc(message, j) + temp * iif(flag, -1, 1)

Have you realized yet that encrypt/decrypt and decrypt/encrypt both return the same plaintext, but have a different ciphertext?

hehe nope

Added: seed has to be Byref because it is not a static variable, and we need to remember its last value when we enter KnuthRange each time.

amazing what skips my noggin. could make encDec's byval though

what you could do with the range is just make it a single, no more accuracy issues

Code: Select all

Function KnuthRange( Byref seed As Ulongint ) As single
  #define IRange( f, l ) Int( seed/2^64*( l+1 - f ) ) + f
  seed = 6364136223846793005ull * seed + 1442695040888963407ull
  Return (seed shr 32) / ((culngint(1) shl 32) + 128)
End Function

Sub EncDec( ..,
  ..
      temp = 255.499 * KnuthRange( seed )

[deltarho[1859]]

@dafhi

Code: Select all

temp*IIf( (temp <= 128), flag, -flag )

is definitely convoluted.

Your latest approach is better.

However, here is another approach and one that I should have considered in the first place.

Instead of KnuthRange(0,255) we can use KnuthRange(-255,255)

The two procedures are now:

Code: Select all

Function KnuthRange( Byref seed As Ulongint, byval first as longint, byval last as longint ) As longint
#define Irange(f,l) clngint((seed mod (((l)-(f))+(1))) + (f))
seed = 6364136223846793005ull * seed + 1442695040888963407ull
Return IRange(first,last)
End Function
 
Sub EncDec( Byref message As String, Byval seed as Ulongint, Byval rounds As Ulong, ByVal flag As Long )
Dim As ULong  k = Len(message)
For i As Ulong = 1 to rounds
  For j As Ulong = 1 To k
    message[j-1] = Asc(message, j) + KnuthRange( seed, -255, 255 )*flag  ' Random addition/subtraction
  Next
Next
End Sub

including dodicat's Mod improvement. There is no need for dodicat's 'if first>last then swap first,last' because the range is hard-wired.

Speed wise, surprisingly, is the same as before.

If the procedures get any smaller, they will disappear.

could make encDec's byval though

Agreed and done.

what you could do with the range is just make it a single, no more accuracy issues

I will look into that.

If we use two 64-bit seeds, with an attacker facing 128 bits, with three rounds each, the Walrus time drops to 15 microseconds.

It is remarkable what can be achieved when a couple of guys collaborates with you.

Thanks, dafhi.

[dafhi]

If the procedures get any smaller, they will disappear.

that's what we're here for xD

[deltarho[1859]]

that's what we're here for xD

And you are having as much fun as I am.

However, it must be remembered this is fun. I would not dream of using this in my Encrypterent application. That is serious stuff, and AES-CBC is used. That is hardware encryption on my CPU and it belts along.

[neil]

Quantum computers threaten to end digital security. Here’s what’s being done about it
https://fortune.com/2020/09/11/post-qua ... ithm-nist/

Post-quantum encryption contender is taken out by single-core PC and 1 hour
https://arstechnica.com/information-tec ... smackdown/

[deltarho[1859]]

It is worth noting that the cryptography at risk is the public key encryption schemes such as RSA and ECDSA which could well be dead in the water by the mid-2030s. SHA2 and AES should be quantum resistant. Remember DES and triple DES? A quantum computer will not scratch the paint on triple AES. SHA512 or SHA1024 should be OK.

You may say that they will be slower. Yes, they will be, but the Google's of this world and the pharmaceutical companies will be using them on their quantum computers.

What about a small company who wants to keep something secret from a big competitor who has a quantum computer, and they cannot afford one? Tough – they will have to ditch their public key systems and buy time from outfits specializing in providing a quantum service. They will start to spring up until quantum computers become affordable.

So, when will quantum computers be available for our desktops. I couldn't even hazard a guess – may be never. In the beginning, only rich people will have them in a spare bedroom or a shed in the garden. They will not be small for a while yet.

[neil]

This is a strong Encryption idea.
A 16384 Byte file was downloaded from random.org this was created with atmospheric noise.
No one else has this file it's unique this would be the key file.
If I XOR every single byte of "mydata XOR random.org file". The key is the entire file.
Every single byte is unique because of the atmospheric noise file and using XOR to encrypt mydata file.
Could this be decrypted by a quantum computer without the unique key?
I just thought about it and only a person who has access to a quantum computer could answer this.
This is a very strong encryption idea.

Code: Select all

''This is a very strong encryption idea
''Example only this has not been tested

open "atmospherenoise.bin" For Input as #1 ''16384 byte file from random.org
open "mydata.dat" For Input as #2 ''15822 byte file mydata
open "encrypted.dat" For Binary as #3 ''encrypted data file

Dim as UByte mydata,randorg,encrypt
Dim as UShort i

for i = 1 to 15822
get #1,,randorg
get #2,,mydata
encrypt = (mydata xor randorg) 
put #3,,encrypt
next

close #1
close #2
close #3

[neil]

Last year when I was working on storing data efficiently. I used this method for storing data. I just thought this also could be used as a simple cipher. Each 4 letters forms 1 letter there are 4 words. The only letters that are used is "ABCD". This could be solved on paper. Or you could write a simple algorithm to do it. I just posted it for fun to see how long it takes for someone to solve it.

Hint 4 alphabet letters forms 1 new alphabet letter. Just separate them in blocks of 4. There are 4 words.
BBBABCCABCCBBCDCBCCDACAABCDDBDBBBDBABDADBCCBBCBABCBBACAABDBABCCABCBBACAABAACBCDDBDCAACDC

[deltarho[1859]]

We can replace 'Mod n' with 'And (n-1)' if n is a power of 2.
So, I replaced

Code: Select all

#define IRange(f,l) clngint((seed mod (l-f+1)) + f)
...
Return IRange(first,last)

with

Code: Select all

Return CLngInt ((seed and 511) - 256)

in KnuthRange.

In EncDec

Code: Select all

KnuthRangex( seed, -255, 255) )*flag

was replaced with simply

Code: Select all

KnuthRange( seed )*flag

On a close to zero test the Mod method gave -0.0016604 compared with -0.49997184 for a 10^8 test. Our distribution uniformity is starting to drift a bit, but not excessively.

I did another test to see how many of a 10^8 tests were negative. Ideally, we should get fifty million. I got, 50000011 and pretty much the same on several runs with different seeds.

The big question: "Is it faster?"

The original Walrus encryption took 32 microseconds. The latest time after a few revisions gave 25 microseconds. We are now down to 13 microseconds. This latest incarnation is then twice as fast.

If we use two 64-bit seeds, with an attacker facing 128 bits, with three rounds each, the Walrus time drops to 8 microseconds. The previous fastest was 15 microseconds.

Latest code:

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  k = Len(message)
For i As Ulong = 1 to rounds
  For j As Ulong = 1 To k
    message[j-1] = Asc(message, j) + KnuthRange( seed )*flag
  Next
Next
End Sub

KnuthRange is now less versatile, but it was never intended to be used as a PRNG in a normal context.

I am out of this thread now. The code is shorter still, and we are now getting blistering speeds for something which I will probably never use. It ended up as simply a programming exercise.

[deltarho[1859]]

Actually '(seed and 511) – 256' is considering a range of [-256, 255]. I had to that to exploit the power of 2. 10^8 averages will tend to -0.5 which is what we are getting with -0.49997184. So, it wasn't a drift of distribution uniformity – It was expected. The PRNG is being 'nudged' but that doesn't matter – the encryption is robust.

Added: A final note. Earlier a 100MiB was loaded and encrypted which took 1.8 seconds. That is now 1.3 seconds

[Provoni]

Optimization by ChatGPT 4.0, if going for many rounds it's faster:

Code: Select all

Sub EncDec(ByRef message As String, ByVal seed As ULongInt, ByVal rounds As ULong, ByVal flag As Long)
    Dim As ULong k = Len(message), i, j
    For i = 1 To rounds * k
        j = (i - 1) Mod k
        message[j] = Asc(message, j + 1) + KnuthRange(seed) * flag
    Next
End Sub

Edit: Actually tested to be slower by deltarho.