Faster Encyrption / Obscuration than RC4 for Large 24MB & 15Mb Files?

I tried the rc4 code found on this post:

http://forums.realsoftware.com/viewtopic.php?p=204303#p204303

A 2.4 million character string takes about 39 seconds on a 2.8 Quad Core Mac Pro with 48GB RAM.

I am wanting to load data from a two text files which approximately 24MB and 15MB. I don’t want to store the files as plain text, but store the files as encrypted or obscured text in the files and them decrypt / unscramble them into a string variable. The rc4 method is still too slow. Even though I read that blowfish would be slower I tried it for the heck of it, but after minute I forced quit the compiled program as it was not not yet :0)

I’d like to stay away from plugins if at all possible as I do not want to deal with non working code in the future. I’d like have a reasonable amount of security to prevent competitors from taking the file data and dropping them into their own application, but I don’t expect to stop determined hackers.

I just tested that code on a 2.0MB string, and it took 3.2 seconds. This is on a core i7 Mac using the latest Xojo. I’m not sure why your version is taking 10x as long.

In addition, I made an optimized version which takes 1.3 seconds.

Here’s my modified version

  #Pragma DisableBackgroundTasks
  #Pragma DisableBoundsChecking
  
  Dim MM as MemoryBlock = strData
  Dim MM2 as New MemoryBlock(LenB(strData))
  dim memAsciiArray(255) as integer
  dim memKeyArray(255)   as integer
  dim memJump as integer
  dim memTemp as integer
  dim memY as integer
  dim intKeyLength as integer
  dim intIndex as integer
  dim intT as integer
  dim intX as integer
  
  
  intKeyLength = len(strKey)
  
  for intIndex = 0 to 255
    memKeyArray(intIndex) = asc(mid(strKey, ((intIndex) mod (intKeyLength)) + 1, 1))
  next
  
  for intIndex = 0 to 255
    memAsciiArray(intIndex) = intIndex
  next
  
  for intIndex = 0 to 255
    memJump = (memJump + memAsciiArray(intIndex) + memKeyArray(intIndex)) mod 256
    memTemp = memAsciiArray(intIndex)
    memAsciiArray(intIndex) = memAsciiArray(memJump)
    memAsciiArray(memJump) = memTemp
  next
  
  intIndex = 0
  memJump = 0
  
  for intX = 1 to MM2.Size
    intIndex = (intIndex + 1) mod 256
    memJump = (memJump + memAsciiArray(intIndex)) mod 256
    intT = (memAsciiArray(intIndex) + memAsciiArray(memJump)) mod 256
    memTemp = memAsciiArray(intIndex)
    memAsciiArray(intIndex) = memAsciiArray(memJump)
    memAsciiArray(memJump) = memTemp
    memY = memAsciiArray(intT)
    //mm2.Byte(intX - 1) = bitwise.bitxor(val("&h" + hex(MM.byte(IntX - 1))), bitwise.bitxor(memTemp,memY))
    mm2.byte(intX-1) = Bitwise.BitXor(mm.byte(intX-1), memTemp, memY)
  next
 
  return MM2

I suspect it could be sped up even more?

#If Not DebugBuild
#pragma DisableBackgroundTasks
#pragma DisableBoundsChecking
#pragma DisableAutoWaitCursor
#pragma StackOverflowchecking False
#pragma NilObjectChecking False
#EndIf

Here’s my 3rd revision : it’s 4x faster than the one in the original post, and will do 2MB of data in about 740msec.

Function rc4v3(strData as string, strKey as String) As string
  #Pragma DisableBackgroundTasks
  #Pragma DisableBoundsChecking
  #Pragma NilObjectChecking False
  
  Dim MM as MemoryBlock = strData
  Dim MM2 as New MemoryBlock(mm.Size)
  
  dim mmKey as MemoryBlock = strKey
  
  dim memAsciiArray as new MemoryBlock(256)
  dim memKeyArray as new MemoryBlock(256)
  dim memJump as integer
  dim memTemp as integer
  dim memY as integer
  dim intKeyLength as integer
  dim intIndex as integer
  dim intT as integer
  dim intX as integer
  
  
  intKeyLength = lenb(strKey)
  
  dim pK as ptr =memKeyArray
  dim pKey as ptr = mmKey
  for intIndex = 0 to 255
    pK.byte(intIndex) = pKey.byte( intIndex mod intKeyLength ) 
  next
  
  dim pA as ptr = memAsciiArray
  for intIndex = 0 to 255
    pA.byte(intIndex) = intIndex
  next
  
  for intIndex = 0 to 255
    memJump = (memJump + pA.byte(intIndex) + pK.byte(intIndex)) mod 256
    memTemp = pA.byte(intIndex)
    pA.byte(intIndex) = pA.byte(memJump)
    pA.byte(memJump) = memTemp
  next
  
  intIndex = 0
  memJump = 0
  
  dim p2 as ptr = mm2
  dim mm2size as integer = mm2.size
  for intX = 1 to mm2size
    intIndex = (intIndex + 1) mod 256
    memJump = (memJump + pA.byte(intIndex)) mod 256
    intT = (pA.byte(intIndex) + pA.byte(memJump)) mod 256
    memTemp = pA.byte(intIndex)
    pA.byte(intIndex) = pA.byte(memJump)
    pA.byte(memJump) = memTemp
    memY = pA.byte(intT)
    p2.byte(intX-1) = Bitwise.BitXor(p2.byte(intX-1), memTemp, memY)
  next
  
  return MM2
  End Function

[quote=110834:@Michael Diehr]Here’s my 3rd revision : it’s 4x faster than the one in the original post, and will do 2MB of data in about 740msec.

[/quote]

Impressive. Congratulations. Euh… How do you decrypt ?

Please note I haven’t tested any of this code, it may be buggy.

I believe that RC4 is symmetric, which means that if
cypherText = RC4(plainText,key)
then
plainText = RC4(cypherText,key)

Ok, here’s my 4th version which is about 7x faster than the last one - it looks like Bitwise.BitXOR(a,b,c) is much much slower than using a temp variable and calling BitXOr(a,b) and BitXor(b,c) in succession.

I also replaced some calls to Mod with an if then statement and subtraction which helps a tiny bit (and is only workable since we know the byte values can’t go above 256*2).

With these changes, it’s down to 117msec for 2MB of data, which is over 20x faster than the original code. :slight_smile:

Function rc4v4(strData as string, strKey as String) As string
  #Pragma DisableBackgroundTasks
  #Pragma DisableBoundsChecking
  #Pragma NilObjectChecking False
  
  Dim MM as MemoryBlock = strData
  Dim MM2 as New MemoryBlock(mm.Size)
  
  dim mmKey as MemoryBlock = strKey
  
  dim memAsciiArray as new MemoryBlock(256)
  dim memKeyArray as new MemoryBlock(256)
  dim memJump as integer
  dim memTemp as integer
  dim memY as integer
  dim intKeyLength as integer
  dim intIndex as integer
  dim intT as integer
  dim intX as integer
  
  
  intKeyLength = lenb(strKey)
  
  dim pK as ptr =memKeyArray
  dim pKey as ptr = mmKey
  for intIndex = 0 to 255
    pK.byte(intIndex) = pKey.byte( intIndex mod intKeyLength ) 
  next
  
  dim pA as ptr = memAsciiArray
  for intIndex = 0 to 255
    pA.byte(intIndex) = intIndex
  next
  
  for intIndex = 0 to 255
    memJump = (memJump + pA.byte(intIndex) + pK.byte(intIndex)) mod 256
    memTemp = pA.byte(intIndex)
    pA.byte(intIndex) = pA.byte(memJump)
    pA.byte(memJump) = memTemp
  next
  
  intIndex = 0
  memJump = 0
  
  
  
  dim p2 as ptr = mm2
  dim mm2size as integer = mm2.size
  for intX = 1 to mm2size
    intIndex = intIndex + 1
    if intIndex > 255 then
      intIndex = 0
    end if
    
    memJump = memJump + pA.byte(intIndex)
    if memJump > 255 then
      memJump = memJump - 256
    end if
    
    intT =  pA.byte(intIndex) + pA.byte(memJump)
    if intT>255 then
      intT = intT -256
    end if
    
    memTemp = pA.byte(intIndex)
    pA.byte(intIndex) = pA.byte(memJump)
    pA.byte(memJump) = memTemp
    memY = pA.byte(intT)
    //mm2.Byte(intX - 1) = bitwise.bitxor(val("&h" + hex(MM.byte(IntX - 1))), bitwise.bitxor(memTemp,memY))
    //mm2.byte(intX-1) = Bitwise.BitXor(mm.byte(intX-1), memTemp, memY)
    //p2.byte(intX-1) = Bitwise.BitXor(p2.byte(intX-1), memTemp, memY)
    dim tt as integer = BitwiseXor(p2.byte(intX-1), memTemp)
    tt = BitwiseXor(tt,memY)
    p2.byte(intX-1) = tt
  next
  
  return MM2
  
End Function

And here’s version 5 which is 2x as fast: now we are at 54msec for 2MB, a speedup of over 35x from the original. In this version we just use the plain XOR operator which (I think) does the right then when using integer operands:

Function rc4v5(strData as string, strKey as String) As string
  #Pragma DisableBackgroundTasks
  #Pragma DisableBoundsChecking
  #Pragma NilObjectChecking False
  
  Dim MM as MemoryBlock = strData
  Dim MM2 as New MemoryBlock(mm.Size)
  
  dim mmKey as MemoryBlock = strKey
  
  dim memAsciiArray as new MemoryBlock(256)
  dim memKeyArray as new MemoryBlock(256)
  dim memJump as integer
  dim memTemp as integer
  dim memY as integer
  dim intKeyLength as integer
  dim intIndex as integer
  dim intT as integer
  dim intX as integer
  
  
  intKeyLength = lenb(strKey)
  
  dim pK as ptr =memKeyArray
  dim pKey as ptr = mmKey
  for intIndex = 0 to 255
    pK.byte(intIndex) = pKey.byte( intIndex mod intKeyLength ) 
  next
  
  dim pA as ptr = memAsciiArray
  for intIndex = 0 to 255
    pA.byte(intIndex) = intIndex
  next
  
  for intIndex = 0 to 255
    memJump = (memJump + pA.byte(intIndex) + pK.byte(intIndex)) mod 256
    memTemp = pA.byte(intIndex)
    pA.byte(intIndex) = pA.byte(memJump)
    pA.byte(memJump) = memTemp
  next
  
  intIndex = 0
  memJump = 0
  
  
  
  dim p2 as ptr = mm2
  dim mm2size as integer = mm2.size
  for intX = 1 to mm2size
    intIndex = intIndex + 1
    if intIndex > 255 then
      intIndex = 0
    end if
    
    memJump = memJump + pA.byte(intIndex)
    if memJump > 255 then
      memJump = memJump - 256
    end if
    
    intT =  pA.byte(intIndex) + pA.byte(memJump)
    if intT>255 then
      intT = intT -256
    end if
    
    memTemp = pA.byte(intIndex)
    pA.byte(intIndex) = pA.byte(memJump)
    pA.byte(memJump) = memTemp
    memY = pA.byte(intT)
    //mm2.Byte(intX - 1) = bitwise.bitxor(val("&h" + hex(MM.byte(IntX - 1))), bitwise.bitxor(memTemp,memY))
    //mm2.byte(intX-1) = Bitwise.BitXor(mm.byte(intX-1), memTemp, memY)
    //p2.byte(intX-1) = Bitwise.BitXor(p2.byte(intX-1), memTemp, memY)
    p2.byte(intX-1) = p2.byte(intX-1) Xor memTemp Xor memY
  next
  
  return MM2
  
End Function

Thanks for all the replies!!! I have not had the chance to try them yet, but wanted to add some input regarding the following:

“I just tested that code on a 2.0MB string, and it took 3.2 seconds. This is on a core i7 Mac using the latest Xojo. I’m not sure why your version is taking 10x as long.”

It’s likely taking much longer, aside from the less efficient code, because the 39 seconds was for a file that is 24.8MB as opposed to 2.0MB


I am also curious as to the code regarding opening the file and dumping the contents into the rc4 method. Here’s what I am using for a quick test via a temporary button I added to the Window although the code will likely go into the App open event.

Is there any faster way to improve this? I had initially dumped the textinputstream into a string variable and then passed that variable to the rc4 method; however, I decided to simple use the readall method and skip a step. I’ll likely also rename the the rc4 method to some random string so its little less obvious in say a hex editor search.

  Dim T as String
  Dim F as FolderItem
  Dim TextIn as TextInputStream
  
  F = GetFolderItem("").Child("myfile.txt")
  
  If F.Exists then
    TextIn = F.OpenAsTextFile
  End If
  
  If TextIn <> Nil then
    T = RC4(TextIn.ReadAll, "passwordstring")
  End If

RC4 is a bi-directional encryption method. Using the same key and feeding the encrypted data back through the function will decrypt.

**Adding the StackOverflow pragma also increases the efficiency even more.

In this case, not so much, since there aren’t actually any user-level function calls happening. But in general, I agree it would.

Ok, that makes sense. I just tried my latest version and it can do 25MB in 776msec (0.7 seconds). That doesn’t include the time to load the data from disk or anything, it’s just the RC4 time.

Here’s version 6: I cleaned the code up to use the variable names that Wikipedia uses, and I also tested it to make sure it works. It’s a hair slower than version 5 but much more readable:

Function rc4v6(dataString as string, keyString as string) As string
  // highly optimized version of the RC4 algorithm written for Xojo 2014 
  // uses pointers and MemoryBlocks for speed
  // written to follow the pseudo-code algorithm described here:  http://en.wikipedia.org/wiki/Rc4
  #Pragma DisableBackgroundTasks
  #Pragma DisableBoundsChecking
  #Pragma NilObjectChecking False
  #Pragma StackOverflowChecking False
  
  
  Dim mbPlaintext as MemoryBlock = dataString  // input data
  dim Plaintext as Ptr = mbPlaintext // a pointer, used for speed
  
  Dim mbCyphertext as New MemoryBlock(mbPlaintext.Size)    // output data, same size as input
  dim Cyphertext as Ptr = mbCyphertext // a pointer, used for speed
  
  dim mbKey as MemoryBlock = keyString  // the key, as a MemoryBlock
  dim Key as Ptr = mbKey
  
  dim keylength as integer = mbKey.size
  
  
  // do the Key Scheduling Algorithm (KSA)
  dim mbS as new MemoryBlock(256)
  dim S as Ptr = mbS // a pointer, used for speed
  
  // first, fill it with Identity (0-255)
  for i as integer = 0 to 255
    S.byte(i) = i
  next
  
  // now, do the KSA
  dim i,j as integer
  for i = 0 to 255
    j = (j + S.byte(i) + Key.byte(i mod keylength) ) mod 256
    // swap values of S[i] and S[j]
    dim tmp as Byte = S.byte(j)
    S.byte(j) = S.byte(i)
    S.byte(i) = tmp
  next
  
  
  // now, do the encoding
  i = 0
  j = 0
  
  dim U as integer = mbPlaintext.Size-1 // iterate from 0...U
  for x as integer = 0 to U
    i= (i + 1 ) mod 256
    j = (j + S.byte(i) ) mod 256
    // swap values of S[i] and S[j]
    dim tmp as Byte = S.byte(j)
    S.byte(j) = S.byte(i)
    S.byte(i) = tmp
    
    // K is the keystream value which is XORed with the Plaintext to make the Cyphertext
    dim K as Byte  = S.byte( (S.byte(i) + S.byte(j))  mod 256)
    
    Cyphertext.byte(x) = Plaintext.byte(x) XOR K
  next
  
  return mbCyphertext
End Function

[quote=110898:@art ouette]
Is there any faster way to improve this? I had initially dumped the textinputstream into a string variable and then passed that variable to the rc4 method; however, I decided to simple use the readall method and skip a step.[/quote]

One thing to be aware of : Strings will auto-convert to MemoryBlocks (and vice-versa) but it isn’t instantaneous. The way this is written, you start with a string, it gets converted to a Memoryblock, and then the result is a MemoryBlock which is converted back to a String. It’s probably not hurting much, but if, say you knew you really wanted to use memory blocks, you could alter the function to use them instead of string parameters. Personally, I wouldn’t worry about it unless your data is greater than 100MB ish.

If this is for OSX, you can encrypt and decrypt the file using SHELL utilties…

another option depending on what you are storing in the file… an Encrypted SQLite Database?

I tested the 24.8MB file with version six of the code above and it reduced the time from 39 second to just under 6 seconds :0) so we are likely looking at maybe 10 seconds start up time, which may not be that bad for an application that users will likely just keep running all the time.

Thanks for the information.

I’ve been using a crude version of the application for in-house use for about 2 years, but I wanted to spruce it up a bit by improving the code, appearance, and converting the user files it generated to xml format, etc, as if I were going to deploy it to the public.

Those suggestions might be a good option as although offering the program to Windows users would increase the potential customer base I frankly have not used Windows, aside from a rare library catalog computer, since the days of Virtual PC running XP on some of my PPC Macs for a couple applications that were not made for Macs at the time. I just don’t think I would have the time to deal with the Windows side of it.

Encrypted SQLite database would be xplatform assuming that can be made to fit the data requirements… That way one set of code, and one method would handle both OSX and WIN

[quote=110891:@Michael Diehr]Please note I haven’t tested any of this code, it may be buggy.

I believe that RC4 is symmetric, which means that if
cypherText = RC4(plainText,key)
then
plainText = RC4(cypherText,key)[/quote]

I see. Thank you.

Has anyone ported this function to the new framework ?