RCQ

From HashNet Wiki
Jump to: navigation, search

RCQ is a patented encryption/decryption/hashing algorithm similar to RC4 created by Anthony Mai under Sony Interactive Entertainment LLC. An extremely fast data encryption, decryption and secure hash scheme encrypts or hashes data of any size, and can be implemented in a variety of software or hardware based data processing devices. A key and data are prepared for processing by separating them into a series of four byte integers, pad with zero bytes as necessary. A bit manipulation unit having four registers A, B, C and D that are each thirty-two bits long is initialized by loading the key into the registers. A series of operations are performed on the registers to manipulate bits in the registers. An exclusive OR (XOR) operation is then performed on contents of register D and a portion of the data to be processed.

Usage

This algorithm is known to be used in the PlayStation 3's Medius (SCE-RT) network cryptography engine/library.

The following libraries implement RCQ encryption/decryption for Medius:

Snippets

//1.  For data encryption or decryption:
//   1a. Call
//      rcqInit   or   rcqSaltyInit
//      Which one to call depends on the situation in application.
//      But the encrypting side and decrypting side will always
//      call the same thing out of these two.
//   1b. Call
//      rcqEncrypt for encryption, or
//      rcqDecrypt for decryption
//
// Below are the functions for encryption and decryption
// There are 4 functions:
//
//  rcqInit:
//   Initialize the processing unit for both encryption and decryption,
//   using a 16 bytes key. Both encrypting and decrypting sides will
//   know the same key.
//
//  rcqSaltyInit:
//   Initialize the processing unit for both encryption and decryption,
//   using both a 16 bytes key and a random 4 bytes salt, which changes
//   from one encryption.decryption session to another. Both sides will
//   know the same key and the same salt.
//  (Please note, one of either rcqInit or rcqSaltyInit will be used, but not
//   both. Which one will be used depends on the application situation.)
//
//  rcqEncrypt:
//   Function to call to encrypt data. To encrypt data, you first call
//   either rcqInit( ) or rcqSaltyInit( ), and then call rcqEncrypt( ).
//
//  rcqDecrypt:
//   Function to call to decrypt data. To decrypt data, you first call
//   either rcqInit( ) or rcqSaltyInit( ), and then call rcqDecrypt( ).

void rcqInit (const struct RC_KEY* pKey, RCQ* pRCQ) {
    memcpy(pRCQ, pKey, sizeof(*pRCQ));
    rcqEncrypt(pRCQ, (Byte*)pRCQ, sizeof(*pRCQ));
}

void rcqSaltyInit (const struct RC_KEY* pKey, Int32 nSalt,RCQ* pRCQ ) {
    memcpy(pRCQ, pKey, sizeof(*pRCQ));
    rcqHashUpdate(pRCQ, (Byte*)&nSalt, sizeof(nSalt)); rcqEncrypt(pRCQ, (Byte*)pRCQ, sizeof(*pRCQ));
}

Int32 rcqEncrypt (RCQ*pRCQ, Byte* pData, Int32 nBytes) {
    Int32 A = pRCQ->A;
    Int32 B = pRCQ->B;
    Int32 C = pRCQ->C;
    Int32 D = pRCQ->D; 

    //Back up 4 bytes beyond our data. This will be restored later
    Int32 R = *((Int32*)&(pData[nBytes])); 

    //Make those 4 bytes zero. Part of it padding bytes and encrypted
    *((Int32*)&(pData[nBytes])) = 0; 

    //Loop until all input data are encrypted.
    while (nBytes > 0) {
        nBytes = sizeof(Int32);
        D {circumflex over ()}= 0x5B3AA654;
        C += D + A;   C = (C<<7)|(C>>25);
        B += C + D;   C {circumflex over ()}= 0x75970A4D;
        B = (B<<11)|(B>>21);
        A += B + C;
        A = (A<<17)|(A>>15);
        D += (A&B)|(C&(˜B));
        B = ˜B;
        A = ˜A;
        D {circumflex over ()}= *((Int32*)pData);
        *((Int32*)pData) = D;
        pData += sizeof(Int32);
    } pRCQ->A = A; pRCQ->B = B; pRCQ->C = C; pRCQ->D = D;

    //Restore the original 4 bytes backed up.
    *((Int32*)&(pData[nBytes])) = R;

    //Return the sum of A,B,C,D as a checksum.
    return (A+B+C+D);
}

Int32 rcqDecrypt (RCQ* pRCQ, Byte* pData, Int32 nBytes) {
    Int32 A = pRCQ->A;
    Int32 B = pRCQ->B;
    Int32 C = pRCQ->C;
    Int32 D = pRCQ->D;
    //Back up 4 bytes beyond our data. This will be restored later
    Int32 R = *((Int32*)&(pData[nBytes]));
    //Make those 4 bytes zero. Part of it padding bytes and decrypted
    *((Int32*)&(pData[nBytes])) = 0;
    //Loop until all input data are decrypted.
    while (nBytes > 0) {
        nBytes = sizeof(Int32);
        D {circumflex over ()}= 0x5B3AA654;
        C += D + A;
        C = (C<<7)|(C>>25);
        B += C + D;
        C {circumflex over ()}= 0x75970A4D;
        B = (B<<11)|(B>>21);
        A += B + C;
       A = (A<<17)|(A>>15);
        D += (A&B)|(C&(˜B));
        B = ˜B;   A = ˜A;
        *((Int32*)pData) {circumflex over ()}= D;
        D {circumflex over ()}= *((Int32*)pData);
        pData += sizeof(Int32);
     }
    //Do we exactly decrypt all data and no padding, if nBytes==0
    if (nBytes) {
        //No, so do another XOR to adjust D, for the padding bytes, which
        // should decrypt to zero bytes.
        D {circumflex over ()}= pData[1] & (0  (1<<((4+nBytes)*8)));
    } pRCQ->A = A; pRCQ->B = B; pRCQ->C = C; pRCQ->D = D;
    //Restore the 4 bytes we originally backed up.
    *((Int32*)&(pData[nBytes])) = R;
    //Return the sum of A,B,C,D as a checksum.
    return (A+B+C+D);
}

An example of an implementation of the method 50 (FIG. 4) and the method 90 (FIG. 6) in C code in accordance with another embodiment of the present invention is as follows:

typedef struct RCQ {
    Int32 A;
    Int32 B;
    Int32 C;
    Int32 D;
} RCQ;

Initializing the Processing Unit:

void rcqInit(const Byte pKey[16], RCQ* pRCQ) {   memcpy(pRCQ, pKey, sizeof(*pRCQ));   rcqEncrypt(pRCQ, (Int32*)pRCQ, sizeof(RCQ)/sizeof(Int32)); }

Encrypting Data:

Int32 rcqEncrypt(RCQ* pRCQ, Int32* pData, Int32 nWords) { Int32 A = pRCQ->A; Int32 B = pRCQ->B; Int32 C = pRCQ->C; Int32 D = pRCQ->D; while (nWords-- > 0) {   D {circumflex over ()}= 0x5B3AA654;   C += D + A;   C = (C<<7)|(C>>25);   B += C + D;   C {circumflex over ()}= 0x75970A4D;   B = (B<<11)|(B>>21);   A += B + C;   A = (A<<17)|(A>>15);   D += (A&B)|(C&(˜B));   B = ˜B;   A = ˜A;   D {circumflex over ()}= (*pData);   *pData = D;   pData++; } pRCQ->A = A; pRCQ->B = B; pRCQ->C = C; pRCQ->D = D; return (A+B+C+D); }

Decrypting Data:

Int32 rcqDecrypt(RCQ* pRCQ, Int32* pData, Int32 nWords) { Int32 A = pRCQ->A; Int32 B = pRCQ->B; Int32 C = pRCQ->C; Int32 D = pRCQ->D; while (nWords-- > 0) {   D {circumflex over ()}= 0x5B3AA654;   C += D + A;   C = (C<<7)|(C>>25);   B += C + D;   C {circumflex over ()}= 0x75970A4D;   B = (B<<11)|(B>>21);   A += B + C;   A = (A<<17)|(A>>15);   D += (A&B)|(C&(˜B));   B = ˜B;   A = ˜A;   *pData {circumflex over ()}= D;   D {circumflex over ()}= (*pData);   pData++; } pRCQ->A = A; pRCQ->B = B; pRCQ->C = C; pRCQ->D = D; return (A+B+C+D); }

An example of an implementation of the method 50 (FIG. 4) and the method 90 (FIG. 6) in C code in accordance with another embodiment of the present invention is as follows:

void rcqInit(const struct RC_KEY* pKey, RCQ* pRCQ) { memcpy(pRCQ, pKey, sizeof(*pRCQ)); rcqEncrypt(pRCQ, (RT_U4BYTE*)pRCQ, sizeof(*pRCQ)/sizeof(RT_U4BYTE)); } RT_U4BYTE rcqEncrypt ( RCQ* pRCQ, RT_U4BYTE* pData, RT_U4BYTE nWords ) { RT_U4BYTE A = pRCQ->A; RT_U4BYTE B = pRCQ->B; RT_U4BYTE C = pRCQ->C; RT_U4BYTE D = pRCQ->D; while (nWords-- > 0) {   D {circumflex over ()}= 0x5B3AA654;   C += D + A;   C = (C<<7)|(C>>25);   B += C + D;   C {circumflex over ()}= 0x75970A4D;   B = (B<<11)|(B>>21);   A += B + C;   A = (A<<17)|(A>>15);   D += (A&B)|(C&(˜B));   B = ˜B;   A = ˜A;   D {circumflex over ()}= (*pData);   *pData = D;   pData++; } pRCQ->A = A; pRCQ->B = B; pRCQ->C = C; pRCQ->D = D; return (A+B+C+D); } RT_U4BYTE rcqDecrypt ( RCQ* pRCQ, RT_U4BYTE* pData, RT_U4BYTE nWords ) { RT_U4BYTE A = pRCQ->A; RT_U4BYTE B = pRCQ->B; RT_U4BYTE C = pRCQ->C; RT_U4BYTE D = pRCQ->D; while (nWords-- > 0) {   D {circumflex over ()}= 0x5B3AA654;   C += D + A;   C = (C<<7)|(C>>25);   B += C + D;   C {circumflex over ()}= 0x75970A4D;   B = (B<<11)|(B>>21);   A += B + C;   A = (A<<17)|(A>>15);   D += (A&B)|(C&(˜B));   B = ˜B;   A = ˜A;   *pData {circumflex over ()}= D;   D {circumflex over ()}= *pData;   pData++; } pRCQ->A = A; pRCQ->B = B; pRCQ->C = C; pRCQ->D = D; return (A+B+C+D); }

An example of an implementation of the method 50 (FIG. 4) in C code in accordance with another embodiment of the present invention for performing a hash operation is as follows:

void rcqHashInit ( RCQ* pRCQ ) { memset(pRCQ, 0, sizeof(*pRCQ)); rcqEncrypt(pRCQ, (RT_U1BYTE*)pRCQ, sizeof(*pRCQ)); } void rcqHashFinal ( const RCQ*    pRCQ, char         hashOut[16] ) { Int32      theOutput[4]; theOutput[3] = pRCQ->A {circumflex over ()} pRCQ->B {circumflex over ()} pRCQ->C {circumflex over ()} pRCQ->D; theOutput[0] = theOutput[3] {circumflex over ()} pRCQ->A; theOutput[1] = theOutput[3] {circumflex over ()} pRCQ->B; theOutput[2] = theOutput[3] {circumflex over ()} pRCQ->C; theOutput[3] = theOutput[3] {circumflex over ()} pRCQ->D; memcpy(hashOut, theOutput, sizeof(theOutput)); } Int32 rcqChecksum ( char*      pData, Int        nBytes ) { RCQ   theRCQ; rcqHashInit(&theRCQ); rcqHashUpdate(&theRCQ, pData, nBytes); return (theRCQ.A + theRCQ.B + theRCQ.C + theRCQ.D); }

An example of an implementation of the hashing function and checksum functions in C code in accordance with another embodiment of the present invention is as follows:

//Explanation of the usage of these functions: //1.For data hashing which produces 16 bytes as final output: //  1a. Call //    rcqHashInit //   to initialize the processing unit. As in fig. 7, step 20. //   It does the initialization by encrypting the processing //   unit itself. //    In the sample code below, in rcqHashInit, this “fixed and //    known 16 bytes key is simply an all-bytes-zero 16 bytes key. //  1b. Call //    rcqHashUpdate //   to process the data to be hashed. The process is as in //   step 36,38, 40. And is virtually identical to the encryption //   process as detailed in fig.3 and fig.4, except there is no //   step 78 (no data is put back to the buffer). //  1c. Call //    rcqHashFinal //   This step extracts the final 16 bytes hash output, //   as in fig. 7, step 130. It outputs the check sum in four 4- bytes //   integer, calculated respectively using B{circumflex over ( )}C{circumflex over ( )}D, C{circumflex over ( )}D{circumflex over ( )}A, D{circumflex over ( )}A{circumflex over ( )}B, A{circumflex over ( )}B{circumflex over ( )}C. //2. For calculating data checksum, a 4 bytes output. Call function // rcqChecksum //    Note the Checksum calculation process is exactly the same //    as hashing, except it gets the 4 bytes output at the end //    in slightly different way: It simply output the sum of ABCD. ///////////////////////////////////////////////////////////////////// ///////// // Forward declaration struct RC_KEY; typedef struct RCQ {  Int32 A;  Int32 B;  Int32 C;  Int32 D; } RCQ; // Below is the Hash functions: rcqHashInit, rcqHashUpdate, rcqHashFinal void rcqHashInit (  RCQ* pRCQ ) {  memset(pRCQ, 0, sizeof(*pRCQ));  rcqEncrypt(pRCQ, (Byte*)pRCQ, sizeof(*pRCQ)); } void rcqHashUpdate (  RCQ*   pRCQ,  Byte*   pData,  Int32   nBytes ) {  Int32 A = pRCQ->A;  Int32 B = pRCQ->B;  Int32 C = pRCQ->C;  Int32 D = pRCQ->D;  //Back up 4 bytes beyond our data. This will be restored later  Int32 R = *((Int32*)&(pData[nBytes]));  //Make those 4 bytes zero. Part of it padding bytes and encrypted  *((Int32*)&(pData[nBytes])) = 0;  //Loop until all input data are encrypted.  while (nBytes > 0)  {   nBytes −= sizeof(Int32);   D {circumflex over ( )}= 0x5B3AA654;   C += D + A;   C = (C<<7)|(C>>25);   B += C + D;   C {circumflex over ( )}= 0x75970A4D;   B = (B<<11)|(B>>21);   A += B + C;   A = (A<<17)|(A>>15);   D += (A&B)|(C&(˜B));   B = ˜B;   A = ˜A;   D {circumflex over ( )}= *((Int32*)pData);   //This step not taken. This is the only difference from the encrypting   //function. We do not put the encrypted data back to the buffer.   //*((Int32*)pData) = D;   pData += sizeof(Int32);  }  pRCQ->A = A;  pRCQ->B = B;  pRCQ->C = C;  pRCQ->D = D;  //Restore the original 4 bytes backed up.  *((Int32*)&(pData[nBytes])) = R; } void rcqHashFinal (  const RCQ* pRCQ,  Byte hashOut[16] ) {  Int32  theOutput[4];  theOutput[3] = pRCQ->A {circumflex over ( )} pRCQ->B {circumflex over ( )} pRCQ->C {circumflex over ( )} pRCQ->D;  theOutput[0] = theOutput[3] {circumflex over ( )} pRCQ->A;  theOutput[1] = theOutput[3] {circumflex over ( )} pRCQ->B;  theOutput[2] = theOutput[3] {circumflex over ( )} pRCQ->C;  theOutput[3] = theOutput[3] {circumflex over ( )} pRCQ->D;  memcpy(hashOut, theOutput, sizeof(theOutput)); } ///////////////// Below is the Checksum function //////// // Note the Checksum process is exactly identical to hash, // except it use different way to get the final output. // That's why whithin this function it calls the same // rcqHashInit( ) and rcqHashUpdate( ), but do slightly // different thing than rcqHashFinal( ). Int32 rcqChecksum (  Byte* pData,  Int32 nBytes ) {  RCQ  theRCQ;  rcqHashInit(&theRCQ);  rcqHashUpdate(&theRCQ, pData, nBytes);  return (theRCQ.A + theRCQ.B + theRCQ.C + theRCQ.D); }

Implementation

Below are docs regarding the implementation of RCQ.

Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7