[Hardware] RC5 algorithm

[Martin Klingensmith]

Dan Oetting wrote:

> You are right that RC5 doesn't care what comes after the current  
> block. But it does care about what came before. The RSA contests use  
> RC5-CBC so you are given an IV that represents the result from the  
> previous block that needs to be XOR'd with the plain text for the  
> current block before applying the RC5 encryption. The resulting  
> cypher text is then used as the IV for the next block.
>
> Here is a description with sample code: <http://www.ietf.org/rfc/ 
> rfc2040.txt>
>
> -- Dan O. 


Thanks for the tip, Dan.
I did a lot of studying and reducing the rfc2040.txt into something that 
can fit on a page and is specifically for RC5-32/12/9. There are a few 
examples of this out on the 'net but I thought I'd send it anyway in 
case someone is interested in looking at it. The next step is to figure 
out what I need to do to make an FPGA run this as fast as possible. I 
believe it /may/ be possible to pipeline this into something that cranks 
through one key each clock cycle but I'm not so much a professional VLSI 
designer, I don't know how that works in real designs.

Serially, the following happens:
---------------------------
The key expansion loop for: S[i] = S[i-1] + Qw; has to iterate 25 times
The S table creation loop iterates 78 times
The actual block encryption routine only runs through 12 rounds
---------------------------
If you have any wise advice for how to pipeline this, I would much 
appreciate it.


Here is the C code. It is not mine, I just hacked it up from rfc2040.c 
which started out at around 500 lines:
////////////////
#include <stdio.h>

#define Pw  0xb7e15163
#define Qw  0x9e3779b9
#define RC5_WORD     unsigned int
#define SHL(x,s)    ((RC5_WORD)((x)<<((s)&31)))
#define SHR(x,s,w)  ((RC5_WORD)((x)>>((w)-((s)&31))))
#define ROTL(x,s,w) ((RC5_WORD)(SHL((x),(s))|SHR((x),(s),(w))))

int main(){
    RC5_WORD    S[42];
    RC5_WORD    L[3];  /* Based on max key size */
    RC5_WORD    A, B, ivA, ivB;
    int i, k;   
    int        j=0;

    // iv = 07 ce 59 1f 86 14 9a 41
    ivA = 0x1f59ce07;
    ivB = 0x419a1486;
   
    // key = c9 0c 03 53 c0 d4 e1 fe 85
    L[0] = 0x53030cc9;
    L[1] = 0xfee1d4c0;
    L[2] = 0x85;


    S[0] = Pw;
    for(i=1;i<26;i++)
        S[i] = S[i-1] + Qw;
   
    i = j = 0;
    A = B = 0;

    for (k = 0 ; k < 3*26 ; k++)  {
        A = ROTL(S[i] + A + B, 3, 32);
        S[i] = A;
        B = ROTL(L[j] + A + B, A + B, 32);
        L[j] = B;
        i = (i + 1) % 26;
        j = (j + 1) % 3;
    }

    // p = 54 68 65 20 75 6e 6b 6e = "The Unkn"
    A = 0x20656854;
    B = 0x6e6b6e75;
   
    // RC5-CBC requires the IV to be XORed with the input block
    A = (A ^ ivA);
    B = (B ^ ivB);
   
    printf("\nA: %x\nB: %x\n",A,B);

    A = A + S[0];
    B = B + S[1];

    for(i=1;i<=12;i++){
        A = A ^ B;
        A = ROTL(A, B, 32) + S[2*i];
        B = B ^ A;
        B = ROTL(B, A, 32) + S[2*i+1];
    }   
   
    printf("\nA: %x\nB: %x\n",A,B);

    return (0);
}

////////////////

-- 
---
Martin Klingensmith
nnytech.net
infoarchive.net