Announcement

Collapse
1 of 2 < >

New Sub-Forum

In an effort to help make sure there are appropriate categories for topics of discussion that are happening, there is now a sub-forum for databases and database programming under Special Interest groups. Please direct questions, etc., about this topic to that sub-forum moving forward. Thank you.
2 of 2 < >

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

RC6 Algorithm Optimized

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • RC6 Algorithm Optimized

    Code:
    '  Note: BELOW CODE NOT YET CONFIRMED. I'm testing against known correct test vectors
    '        and this code may need modification to conform. The multiply overflows may need
    '        to be reinstated. Stay tuned....
    '  RC6 algorithm, AES finalist.
    '  I corrected f_rnd and i_rnd macro multiply overflows and significantly optimized
    '  this RC6 algorithm that was ported to PB from "C" by Aleksandr Dobrev, with testbed
    '  code by Mike Trader.
    '  Using it, my laptop averages 58 ticks/byte encoding, 53 ticks/byte decoding.
    '  This demo will encode, decode and verify all files included on a list of files
    '  stored in c:\fListCrypt.txt--one file per record--and display statistics after
    '  each file. Individual files can be tested also.
    '  Discussion here: http://www.powerbasic.com/support/pb...ad.php?t=35257
    '  John Gleason, Oct. 22, 07.
    ' ====================================================================================
    
    '  In cryptography, RC6 is a symmetric key block cipher derived from RC5.
    '  It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin
    '  to meet the requirements of the Advanced Encryption Standard (AES) competition.
    '
    '  The algorithm was one of the five finalists, and was also submitted to the NESSIE
    '  and CRYPTREC projects. It is a proprietary algorithm, patented by RSA Security.
    '
    '  RC6 proper has a block size of 128 bits and supports key sizes of 128, 192 and 256 bits,
    '  but, like RC5, it can be parameterised to support a wide variety of word-lengths,
    '  key sizes and number of rounds. RC6 is very similar to RC5 in structure,
    '  using data-dependent rotations, modular addition and XOR operations; in fact,
    '  RC6 could be viewed as interweaving two parallel RC5 encryption processes.
    '
    '  However, RC6 does use an extra multiplication operation not present in RC5 in
    '  order to make the rotation dependent on every bit in a word, and not just the
    '  least significant few bits.
    '
    '
    '  As RC6 has not been selected for the AES, it is not guaranteed that RC6
    '  is royalty-free. As of January 2007, a web page on the official web site
    '  of the designers of RC6, RSA Laboratories, states the following:
    '  "We emphasize that if RC6 is selected for the AES, RSA Security will
    '  not require any licensing or royalty payments for products using the algorithm".
    '  The emphasis on the word "if" suggests that RSA Security Inc. may now require
    '  licensing and royalty payments for any products using the RC6 algorithm.
    '  RC6 is a patented encryption algorithm
    
    
    ' RC6, an encryption algorithm designed by Ron Rivest (RSA Labs) and submitted as a candidate algorithm for the
    ' Advanced Encryption Standard programme of the US National Institute of Standards and Technology."
    
    ' Ported to PB from "C" by Aleksandr Dobrev - Thanks to wonsky Lu for provide source on C
    ' Ver. 0.0.1  December 03, 2006
    
    ' Padding and testbed Mike Trader 2007
    
    
    #COMPILE EXE
    #DIM ALL
    #REGISTER NONE
    
    
    #INCLUDE "win32api.inc"
    
    
    %LITTLE_ENDIAN = 1 ' For Little Endian Machines
    
    
    
    ' Utility macros
    MACRO zbs(xx) = STRING$(xx, 0)
    
    
    MACRO FUNCTION rotr(x,n)
       MACROTEMP s
       LOCAL s AS DWORD
       s = (x)
       ROTATE RIGHT s,n
    END MACRO = s
    
    
    '#define rotl(x,n)   (((x) << ((INT)((n) & 0x1f))) | ((x) >> ((INT)((32 - ((n) & 0x1f))))))
    MACRO FUNCTION rotl(x,n)
       MACROTEMP s
       LOCAL s AS DWORD
       s = (x)
       ROTATE LEFT s,n
    END MACRO = s
    '--------------------------------added 2 macros
    MACRO rotr2(x,n)
       MACROTEMP s
       LOCAL s AS DWORD
        s = x
       !mov eax, s
       !mov ecx, n
       !ror eax, cl
    END MACRO
    
    MACRO rotl2(x,n)
       !mov ecx, n
       !mov eax, x
       !rol eax, cl
    END MACRO
    '----------------------------end added 2 macros
    
    
    ' PUT OR GET a 32 BIT WORD (v) IN machine order FROM a BYTE address IN (x)
    #IF %DEF(%LITTLE_ENDIAN)
       '#define u4byte_in(x)        (*(u4byte*)(x))
       MACRO FUNCTION u4byte_in(x)
         MACROTEMP pdwZmacro
         DIM pdwZmacro AS DWORD PTR
         pdwZmacro = (x)
       END MACRO = @pdwZmacro
       '#define u4byte_out(x,v)    (*(u4byte*)(x) = (v))
       MACRO u4byte_out(x,v)
         MACROTEMP pdwZmacro
         DIM pdwZmacro AS DWORD PTR
         pdwZmacro = (x)
         @pdwZmacro = v
       END MACRO
    
    #ELSE
       '#define u4byte_in(x)        bswap(*(u4byte)(x))
       MACRO u4byte_in(x)
         MACROTEMP dwZmacro
         DIM pdwZmacro AS DWORD PTR
         pdwZmacro = (x)
         @pdwZmacro = bswap(@z)
       END MACRO
       '#define u4byte_out(x, v)    (*(u4byte*)(x) = bswap(v))
       MACRO u4byte_out(x, v)
         MACROTEMP pdwZmacro
         DIM pdwZmacro AS DWORD PTR
         pdwZmacro = (x)
         @pdwZmacro = bswap(v)
       END MACRO
    #ENDIF
    
    
    
    MACRO f_rnd(i,a,b,c,d)           'changed 2 macros------------------------
      MACROTEMP u,t,r,d2,b2
      LOCAL u, t, r AS LONG, d2, b2 AS DWORD
            !mov eax, d
            !mov ecx, d
            !add eax, eax
            !add eax, 1
            !mul ecx
            !mov d2,  eax
            rotl2(d2, 5)
            !mov u, eax
    
            !mov eax, b
            !mov ecx, b
            !add eax, eax
            !add eax, 1
            !mul ecx
            !mov b2,  eax
            rotl2(b2, 5)
            !mov t, eax
    
            !xor eax, a
            !mov r, eax
            rotl2(r      , u)
            !mov a, eax
            a = a + RC6Key(i)
    
            !mov eax, c
            !xor u,   eax
            rotl2(u      , t)
            !mov c, eax
            c = c + RC6Key(i + 1)
    END MACRO
    
    MACRO i_rnd(i,a,b,c,d)
      MACROTEMP u,t,d2,b2
      LOCAL u, t, d2, b2 AS DWORD
            !mov eax, d
            !mov ecx, d
            !add eax, eax
            !add eax, 1
            !mul ecx
            !mov d2,  eax
            rotl2(d2, 5)       'rotl2(d * (d + d + 1), 5)
            !mov u, eax
    
            !mov eax, b
            !mov ecx, b
            !add eax, eax
            !add eax, 1
            !mul ecx
            !mov b2,  eax
            rotl2(b2, 5)       'rotl2(b * (b + b + 1), 5)
            !mov t, eax
    
            rotr2(c - RC6Key(i + 1), t)
            !xor eax, u
            !mov c, eax
            rotr2(a - RC6Key(i), u)
            !xor eax, t
            !mov a, eax
    END MACRO                        'end change------------------------------
    
    
    UNION ConvertTwoByteTYPE          ' Converts a Two Byte Value
        str               AS STRING * 02
        igr               AS INTEGER
        wrd               AS WORD
        byt(1 TO 2)       AS BYTE
    END UNION
    GLOBAL CvtTwoByte AS ConvertTwoByteTYPE
    
    
    
    
    
    '¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤'
    SUB time_stamp_count(tick AS QUAD) ' CPU Clock count    Charles E V Pegge
    
      '---------------------------'
      '                           ' approx because it is not a serialised instruction
      '                           ' it may execute before or after other instructions
      '                           ' in the pipeline.
      ! mov ebx,tick              ' var address where count is to be stored.
      ! db  &h0f,&h31             ' RDTSC read time-stamp counter into edx:eax hi lo.
      ! mov [ebx],eax             ' save low order 4 bytes.
      ! mov [ebx+4],edx           ' save high order 4 bytes.
      '---------------------------'
    
    END SUB
    
    
    '¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
    FUNCTION StrToHex( sBin AS STRING ) AS STRING
    
      REGISTER i AS LONG, j AS LONG
      LOCAL a, b AS BYTE PTR
      LOCAL sHex AS STRING
    
        sHex  = STRING$( LEN(sBin)*2, " " ) ' make a string the right size
        a     = STRPTR(sHex)
        b     = STRPTR(sBin)
        j     = 0
        FOR i = 0 TO LEN(sBin)-1
          CvtTwoByte.str = HEX$(@b[i],2)  ' NO String concatenation
          @a[j] = CvtTwoByte.byt(1)
          INCR j
          @a[j] = CvtTwoByte.byt(2)
          INCR j
        NEXT i
    
      FUNCTION = sHex ' return string
    
    END FUNCTION
    
    
    '¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤'
    ' Invert BYTE order IN a 32 BIT variable
    '#define bswap(x)    (rotl(x, 8) & 0x00ff00ff | rotr(x, 8) & 0xff00ff00)
    FUNCTION bswap( BYVAL dwX AS DWORD ) AS DWORD
    
      LOCAL XXdwl,XXdwr AS DWORD
    
        XXdwl = dwX : XXdwr = dwX
        ROTATE RIGHT XXdwr,8 : XXdwr = XXdwr AND &Hff00ff00???
        ROTATE LEFT  XXdwl,8 : XXdwl = XXdwl AND &H00ff00ff???
    
      FUNCTION = XXdwl OR XXdwr
    
    END FUNCTION
    
    
    '¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤'
    ' initialise the key schedule FROM the USER supplied key
    SUB RC6_set_key( UserKey() AS BYTE, BYVAL key_len AS DWORD, RC6Key() AS DWORD )
    
      LOCAL i, j, k, a, b, t AS DWORD
      DIM l(7) AS DWORD
    
      REDIM RC6Key(43)  ' STATIC u4byte RC6(l_key[44]);
      RC6Key(0) = &Hb7e15163???
    
      LOCAL pdwUserKey AS DWORD PTR
      pdwUserKey = VARPTR(UserKey(0))
    
        k = 1
        WHILE k < 44
            RC6Key(k) = RC6Key(k - 1) + &H9e3779b9???
            INCR k
        WEND
    
        k = 0
        WHILE k < key_len / 32
            l(k) = u4byte_in(pdwUserKey + (4 * k))
            INCR k
        WEND
    
        t = (key_len / 32) - 1 ' t = (key_len / 32);
    
        a = 0: b = 0: i = 0: j = 0
    
        k = 0
        WHILE k < 132
           a = rotl(RC6Key(i) + a + b, 3): b = b+a
           b = rotl(l(j) + b, b)
           RC6Key(i) = a : l(j) = b
           i = IIF(i = 43, 0, i + 1) ' i = (i + 1) % 44;
           j = IIF(j = t , 0, j + 1) ' j = (j + 1) % t;
           INCR k
        WEND
    
    END SUB
    
    
    
    '¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤'
    
    MACRO mRC6_EnCrypt(pdw_InBlk, pdw_OutBlk) ' encrypt a 16byte block OF TEXT
      MACROTEMP a,b,c,d
      LOCAL  a,b,c,d AS DWORD
    
        a = u4byte_in(pdw_InBlk    ): b = u4byte_in(pdw_InBlk +  4) + RC6Key(0)
        c = u4byte_in(pdw_InBlk + 8): d = u4byte_in(pdw_InBlk + 12) + RC6Key(1)
    
        f_rnd( 2,a,b,c,d): f_rnd( 4,b,c,d,a)
        f_rnd( 6,c,d,a,b): f_rnd( 8,d,a,b,c)
        f_rnd(10,a,b,c,d): f_rnd(12,b,c,d,a)
        f_rnd(14,c,d,a,b): f_rnd(16,d,a,b,c)
        f_rnd(18,a,b,c,d): f_rnd(20,b,c,d,a)
        f_rnd(22,c,d,a,b): f_rnd(24,d,a,b,c)
        f_rnd(26,a,b,c,d): f_rnd(28,b,c,d,a)
        f_rnd(30,c,d,a,b): f_rnd(32,d,a,b,c)
        f_rnd(34,a,b,c,d): f_rnd(36,b,c,d,a)
        f_rnd(38,c,d,a,b): f_rnd(40,d,a,b,c)
    
        u4byte_out(pdw_OutBlk,     a + RC6Key(42))  : u4byte_out(pdw_OutBlk +  4, b)
        u4byte_out(pdw_OutBlk + 8, c + RC6Key(43))  : u4byte_out(pdw_OutBlk + 12, d)
    
    END MACRO
    
    
    
    '¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤'
    
    MACRO mRC6_DeCrypt(pdw_InBlk, pdw_OutBlk) ' decrypt a 16byte block OF TEXT
      MACROTEMP a,b,c,d
      LOCAL  a,b,c,d AS DWORD
    
        d = u4byte_in(pdw_InBlk + 12): c = u4byte_in(pdw_InBlk + 8) - RC6Key(43)
        b = u4byte_in(pdw_InBlk +  4): a = u4byte_in(pdw_InBlk    ) - RC6Key(42)
    
        i_rnd(40,d,a,b,c): i_rnd(38,c,d,a,b)
        i_rnd(36,b,c,d,a): i_rnd(34,a,b,c,d)
        i_rnd(32,d,a,b,c): i_rnd(30,c,d,a,b)
        i_rnd(28,b,c,d,a): i_rnd(26,a,b,c,d)
        i_rnd(24,d,a,b,c): i_rnd(22,c,d,a,b)
        i_rnd(20,b,c,d,a): i_rnd(18,a,b,c,d)
        i_rnd(16,d,a,b,c): i_rnd(14,c,d,a,b)
        i_rnd(12,b,c,d,a): i_rnd(10,a,b,c,d)
        i_rnd( 8,d,a,b,c): i_rnd( 6,c,d,a,b)
        i_rnd( 4,b,c,d,a): i_rnd( 2,a,b,c,d)
    
        u4byte_out(pdw_OutBlk + 12, d - RC6Key(1)) : u4byte_out(pdw_OutBlk + 8, c)
        u4byte_out(pdw_OutBlk +  4, b - RC6Key(0)) : u4byte_out(pdw_OutBlk,     a)
    
    END MACRO
    
    
    
    
    '¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤'
    FUNCTION PBMAIN() AS LONG
    
      DIM RC6Key(0) AS STATIC DWORD
      LOCAL KeyLen, SrcLen AS LONG
    
      LOCAL sKey, sFile, bsFile, sCipher, t, sFileName AS STRING
      LOCAL FileLen, i, k, hFile, PadLen, RetVal, nLoops, nBlocks, cryptFile AS LONG
      LOCAL PerfFreq, t1, t2 AS QUAD
      LOCAL cBeg, cEnd AS QUAD
      LOCAL Elapsed AS SINGLE
    
      LOCAL pIn, pOut AS BYTE PTR
    
    
    
        RetVal = QueryPerformanceFrequency(PerfFreq) ' Checkhardware supports High Resolution Timer
    
      DO
        sFile = "Low voltage cutoff should not be of great concern to the average user." ' Default
    
        IF cryptFile = 0 THEN
           cryptFile = 1
           hFile = FREEFILE
           OPEN "C:\fListCrypt.txt" FOR INPUT LOCK SHARED AS #1 ' <<this is a list of all the files you want to en/decrypt
                                                                ' and check for correctness of en/decryption. Does not write
                                                                ' to disk, only memory. 10K min size, 85MB max size tested.
        END IF
       newFile:
        LINE INPUT #1, sfileName
    '   sFileName = "D:\qencod2.dat" ' <<You can also test just a single file if uncommented -------  **   CHANGE THIS   **
        hFile = FREEFILE ' Save the Declarations
        OPEN sFileName FOR BINARY LOCK SHARED AS hFile
          IF ERR THEN MSGBOX "Problem opening file to be encrypted",48,"File Error"+STR$(ERRCLEAR): EXIT FUNCTION
          IF LOF(hFile) < 10000 OR LOF(hFile) > 85000000 THEN CLOSE hFile: GOTO newFile
          GET$ #hFile, LOF(hFile), sFile
        CLOSE hFile '
    
    
    
        bsFile = sFile                                          ' remove this line if not verification testing
        SrcLen = LEN(sFile)
        t = t + "Input File length :" + STR$(SrcLen) + $CRLF
    
    
    '          "12345678901234567890123456789012"
        sKey = "RC6SixteenByteKe"
    
        nLoops = 1 ' 999 for short string
    
        KeyLen = LEN(sKey)
        t = t + "Key length:" + STR$(KeyLen) + " (max=32)" + $CRLF
    
        DIM UserKey(KeyLen) AS STATIC BYTE
        POKE$ VARPTR(UserKey(0)), sKey  ' string to byte array
    
        RC6_set_key( UserKey(), KeyLen, RC6Key() ) ' Create password based key for crypt and decrypt
    
    
    
    
        t = t + sKey  + $CRLF + $CRLF
        t = t + "Input File: '"+sFileName+"', length=" + STR$(LEN(sFile)) + $CRLF
    
    
    
    
        PadLen = 16 - (SrcLen MOD 16)
        t = t + "PadLen :" + STR$(PadLen) + $CRLF
    
        nBlocks = (SrcLen+PadLen) / 16
        t = t + "nBlocks :" + STR$(nBlocks) + $CRLF
    
    
        sFile = sFile + zbs(LEN(PadLen))
    
        sCipher = zbs(SrcLen+PadLen) '
    
        t = t + "Cipher length :" + STR$(LEN(sCipher)) + $CRLF
    
        pIn  = STRPTR(sFile)
        pOut = STRPTR(sCipher)
    
    
    
    
    
    ' ----------------------------------------------------------  Encoding sCipher
        QueryPerformanceCounter t1
    
        time_stamp_count(cBeg) ' measuring cpu clock cycles. The overhead just for making this call is about 25 clocks
    
          LOCAL pi2, po2 AS LONG
          FOR k = 0 TO (nBlocks-1)*16 STEP 16
             pi2 = pIn+k
             po2 = pOut+k
             mRC6_EnCrypt(pi2, po2)
          NEXT
    
        time_stamp_count(cEnd) ' measuring cpu clock cycles. The overhead just for making this call is about 25 clocks
        t = t + "Encrypt Clock Cycles="+STR$( (cEnd-cBeg)\nLoops ) + $CRLF
    
        sCipher = sCipher + CHR$(PadLen) ' byte array to string
    
        QueryPerformanceCounter t2 : Elapsed = (t2-t1)/PerfFreq*1000 ' m/s
    
        t = t + "Encrypted in:"+STR$(Elapsed)+" m/s" + $CRLF
        t = t + "Encrypt Clock Cycles per Byte:"+STR$((cEnd-cBeg)\nLoops\LEN(sFile))+" c/b" + $CRLF + $CRLF
        sFile = "" ' Burn the Input.
        t = t + "Cipher length :" + STR$(LEN(sCipher)) + $CRLF
    '   t = t + StrToHex(LEFT$(sCipher, 30)) + $CRLF + $CRLF + $CRLF
    
    
    
    
    
    
    ' ----------------------------------------------------------  Decoding sCipher
        QueryPerformanceCounter t1
    
        PadLen = ASC(RIGHT$(sCipher, 1))
        t = t + "Recovered PadLen :" + STR$(PadLen) + $CRLF
    
        SrcLen = LEN(sCipher) - 1
    
        nBlocks = SrcLen / 16
        t = t + "Recovered nBlocks :" + STR$(nBlocks) + $CRLF
    
        sFile = zbs(SrcLen)
    
        pIn  = STRPTR(sCipher)
        pOut = STRPTR(sFile)
    
    
        time_stamp_count(cBeg) ' measuring cpu clock cycles. The overhead just for making this call is about 25 clocks
    
          FOR k = 0 TO (nBlocks-1)*16 STEP 16
             pi2 = pIn+k
             po2 = pOut+k
             mRC6_DeCrypt(pi2, po2)
          NEXT
    
        time_stamp_count(cEnd) ' measuring cpu clock cycles. The overhead just for making this call is about 25 clocks
        t = t + "Decrypt Clock Cycles="+STR$( (cEnd-cBeg)\nLoops ) + $CRLF
    
        sFile = LEFT$(sFile, SrcLen-PadLen) ' convert byte array to string
        IF sFile = "" THEN MSGBOX "Decryption Operation Failed",64,"RC6" : EXIT FUNCTION
        QueryPerformanceCounter t2 : Elapsed = (t2-t1)/PerfFreq*1000 ' m/s
        IF sFile <> bsFile THEN ? "Error, decryption file <> original file."  ' for verification testing only
    
        sCipher = "" ' Burn the Cipher
        t = t + "Decrypted File length :" + STR$(LEN(sFile)) + $CRLF
    
        t = t + "Decrypt Completed in:"+STR$(Elapsed)+" m/s" + $CRLF
        t = t + "Decrypt Clock Cycles per Byte:"+STR$((cEnd-cBeg)\nLoops\LEN(sFile))+" c/b" + $CRLF+ $CRLF
    
    
        MSGBOX t,64,"RC6 Encryption"
        RESET t': BEEP
     LOOP UNTIL EOF(1)
    
    END FUNCTION
    Last edited by John Gleason; 22 Oct 2007, 03:26 PM. Reason: added note: code not yet confirmed
Working...
X