Named Spritz ("since the output comes in one drops rather than big blocks"), it is a full "drop-in replacement for RC4". See http://en.wikipedia.org/wiki/RC4#Spritz
Here is my Purebasic version, but first of all FULL CREDIT must go to Pille, Friedhelm, Rings, Lars, Andre et. al and everyone else for their work in creating the original Purebasic RC4[/url] implementation (ive left the header intact from the one i used called RC4_SpeedImproved.pb), as this is nearly all their original work, just a slight tweak by me to change from RC4 to Spritz, which was embarrassingly simple thanks to their awesome groundwork!
Spritz PDF - http://people.csail.mit.edu/rivest/pubs/RS14.pdf
This note reconsiders the design of the stream cipher RC4, and proposes an improved variant, which we call "Spritz" (since the output comes in one drops rather than big blocks.)
Our work leverages the considerable cryptanalytic work done on the original RC4 and its proposed variants. It also uses simulations extensively to search for biases and to guide the selection of intermediate expressions. We estimate that Spritz can produce output with about 24 cycles/byte of computation. Furthermore, our statistical tests suggest that about 281 bytes of output are needed before one can reasonably distinguish Spritz output from random output; this is a marked improvement over RC4.
Our proposal Spritz not only provides a "drop-in replacement" for RC4, with much improved security properties, but also provides a suite of new cryptographic functionalities based on its new "sponge-like" construction and interface.
Ive only just finished it and it's based on pseudocode from Wiki and Bruce Schneier, but it looks right and is based on the same code and variables as RC4 (i, j, S() etc).
Bruce on Spritz - "I have always really liked RC4, and am happy to see a 21st-century redesign. I don't know what kind of use it'll get with its 8-bit word size, but surely there's a niche for it somewhere."
And I really like RC4 too, because it's such a simple algorithm and so small and easy to implement, and variable keysize means you can use keys <=56bit for no export hassles, but because RC4 is considered broken i like to look at the newer variants
Here's the pseudocode comparison taken from Bruce Schneier's page (https://www.schneier.com/blog/archives/ ... ew_rc.html):
Code: Select all
RC4:
1: i = i + 1
2: j = j + S[i]
3: SWAP(S[i];S[j])
4: z = S[S[i] + S[j]]
5: Return z
Spritz:
1: i = i + w
2: j = k + S[j + S[i]]
2a: k = i + k + S[j]
3: SWAP(S[i];S[j])
4: z = S[j + S[i + S[z + k]]]
5: Return zAnd last but not least here's my implementation (again thanks to all who provided the original code that laid the groundwork). IT COULD BE FLAWED, i dont know! But it seems to decrypt and encrypt ok and as the code is so simple it seems right. It looks correct anyway, but maybe somebody here will find a flaw
There are only a few test vectors in the PDF and they didn't mention which password was used, or which constant value for 'w' was used.
Anyway hopefully it will encourage others to look at the other https://en.wikipedia.org/wiki/RC4#RC4_variants (although it seems Spritz is the best of the variant proposals)
Code: Select all
;RC4-SPRITZ.PB
;-------------
; RC4-Spritz variant by Keya, but the majority of code is by others (see original header next)
; English forum: http://www.purebasic.fr/english/viewtopic.php?f=12&t=62455
;
;---Begin original 'RC4Mem' header:---
; German forum: http://www.purebasic.fr/german/archive/viewtopic.php?t=1708
; ^url 404s... instead today see http://purearea.net/pb/CodeArchiv/Encode+Decode/RC4_SpeedImproved.pb
; Author: Friedhelm (updated for PB3.92+ by Lars, updated for PB 4.00 by Andre)
; Date: 25. July 2003
; OS: Windows
; Demo: No
;
; RC4Mem for PB by Pille, 15.07.2003. Special Thanks to Rings
;
; RC4 is a stream cipher designed by Rivest for RSA Data Security (now RSA Security).
; It is a variable key-size stream cipher with byte-oriented operations. The algorithm is
; based on the use of a random permutation. Analysis shows that the period of the cipher is
; overwhelmingly likely To be greater than 10^100. Eight To sixteen machine operations are
; required per output byte, And the cipher can be expected to run very quickly in software.
; Independent analysts have scrutinized the algorithm and it is considered secure.
;---End Original RC4Mem header:---
Procedure.l RC4SpritzMem(Mem.l, memLen.l, key.s)
Dim S.l(255)
Dim K.l(255)
i.l=0: j.l=0: t.l=0: x.l=0
temp.l=0: y.l=0
j = 1
l.l = Len(key)
*Sp.LONG = @S()
*keyP.BYTE = @key
For i = 0 To 255
*Sp\l = i
*Sp + 4
If *keyP\b = 0
*keyP = @key
EndIf
K(i) = *keyP\b
*keyP+1
Next i
j = 0
For i = 0 To 255
j = (j + S(i) + K(i)) & 255
temp = S(i)
S(i) = S(j)
S(j) = temp
Next i
i = 0
j = 0
z = 0
w = 1 ;Schneier on 'w': "The parameter w is basically a constant. It's always 1 in RC4 but
;can be any odd number in Spritz (odd because that means it's always relatively prime to 256)."
*Memm.BYTE = Mem
For x = 0 To memLen-1
i = (i+w) & 255 ;i := (i + w) mod 256
j = (k + S((j + S(i)) & 255)) & 255 ;j := (k + S[(j + S[i]) mod 256]) mod 256
k = (k + i + S(j)) & 255 ;k := (k + i + S[j]) mod 256
temp = S(i)
S(i) = S(j) ;swap values of S[i] and S[j]
S(j) = temp
z = S((j + S((i + S((z + k) & 255)) & 255)) & 255) ;output z := S[(j + S[(i + S[(z + k) mod 256]) mod 256]) mod 256]
*Memm\b ! z
*Memm + 1
Next
ProcedureReturn Mem
EndProcedure
;------------------------------------------------------------------------------------------
;PARAMETERS
sTxt.s ="1234567890 The quick brown fox jumped over the lazy dog." ;String to encrypt
key.s = "s3cr3t k3y" ;Private cipher key
CompilerIf #PB_Compiler_Unicode
OrigLen.l = Len(sTxt) * 2
CompilerElse
OrigLen.l = Len(sTxt)
CompilerEndIf
;TEST ENCRYPT & DECRYPT
RC4SpritzMem(@sTxt,OrigLen,key)
MessageRequester("RC4-Spritz", "Encrypted=" + sTxt)
RC4SpritzMem(@sTxt,OrigLen,key)
MessageRequester("RC4-Spritz", "Decrypted=" + sTxt)
Speed-wise these two sister implementations are very close, I did five timing runs on each (well, six but discarded each first, and debugger disabled of course!), with 5,000,000 iterations with the above parameters.
Spritz is only ~6% slower on my i7, not bad considering the apparently much greater security margin.
;RC4: 14505, 14437, 14556, 14416, 14470 (avg 14477ms)
;Spritz: 15400, 15366, 15339, 15338, 15434 (avg 15375ms)
There is of course still much room for improvement - "We estimate that Spritz can produce output with about 24 cycles/byte of computation." I'm not sure if that would make it faster or not than RC4 (probably not as Wiki's page mentions RC4 is "7 cycles per byte on original Pentium"), but any way you look at it the performance is pretty good.
Again, thankyou to anyone who has ever made Purebasic RC4 contributions
