RC 算法是由 Ron Rivest 发明的一系列对称密钥加密算法。虽然这一系列的算法名字相似,但实际上算法之间没有太大的关联。

Intro

现在总共有六个 RC 系列的算法。其中 RC1 从来没有发布过,RC3 在开始使用前就被证明是不安全的。余下的都是现如今有所运用的算法。

  1. RC2 是一个于 1987 年发布的 64 位分组加密算法。
  2. RC4 是当今运用最广泛的序列密码。
  3. RC5 是一个于 1994 年发布的 32/64/128 位分组加密算法。
  4. RC6 是一个于 1997 年发布的基于 RC5 的 128 位分组加密算法,在当年 AES 的评选中曾是 AES 决赛算法。

了解过算法的基本知识后,下面是 RC2、RC5 以及 RC6 在 C 语言下的实现。

RC2

RC2 是一种分组密码,和 DES 很像,它的输入和输出的长度都是 64 位,而密钥是可变的,长度范围是从 1 到 128 比特,目前使用的是 8 比特的密钥。RC2 被设计成能够在 16 位处理器上运行。在 IBM AT 上它能够比 DES 的加密速度快一倍(假设在完成密钥扩展的情况下)。

RC2 总共分为三个算法步骤。分别是密钥扩展、加密、解密。

密钥扩展算法

密钥扩展通过一个长度变化的密钥生成 64 个字数组。

void rc2_keygen(unsigned short xkey[64], const unsigned char *key, unsigned len, unsigned bits)
{
    unsigned char x;
    unsigned i;
    /* 256-entry permutation table, probably derived somehow from pi */
    static const unsigned char PITABLE[256] = {0xD9, 0x78, 0xF9, 0xC4, 0x19, 0xDD, 0xB5, 0xED, 0x28, 0xE9, 0xFD, 0x79, 0x4A, 0xA0, 0xD8, 0x9D, 0xC6, 0x7E, 0x37, 0x83, 0x2B, 0x76, 0x53, 0x8E, 0x62, 0x4C, 0x64, 0x88, 0x44, 0x8B, 0xFB, 0xA2, 0x17, 0x9A, 0x59, 0xF5, 0x87, 0xB3, 0x4F, 0x13, 0x61, 0x45, 0x6D, 0x8D, 0x09, 0x81, 0x7D, 0x32, 0xBD, 0x8F, 0x40, 0xEB, 0x86, 0xB7, 0x7B, 0x0B, 0xF0, 0x95, 0x21, 0x22, 0x5C, 0x6B, 0x4E, 0x82, 0x54, 0xD6, 0x65, 0x93, 0xCE, 0x60, 0xB2, 0x1C, 0x73, 0x56, 0xC0, 0x14, 0xA7, 0x8C, 0xF1, 0xDC, 0x12, 0x75, 0xCA, 0x1F, 0x3B, 0xBE, 0xE4, 0xD1, 0x42, 0x3D, 0xD4, 0x30, 0xA3, 0x3C, 0xB6, 0x26, 0x6F, 0xBF, 0x0E, 0xDA, 0x46, 0x69, 0x07, 0x57, 0x27, 0xF2, 0x1D, 0x9B, 0xBC, 0x94, 0x43, 0x03, 0xF8, 0x11, 0xC7, 0xF6, 0x90, 0xEF, 0x3E, 0xE7, 0x06, 0xC3, 0xD5, 0x2F, 0xC8, 0x66, 0x1E, 0xD7, 0x08, 0xE8, 0xEA, 0xDE, 0x80, 0x52, 0xEE, 0xF7, 0x84, 0xAA, 0x72, 0xAC, 0x35, 0x4D, 0x6A, 0x2A, 0x96, 0x1A, 0xD2, 0x71, 0x5A, 0x15, 0x49, 0x74, 0x4B, 0x9F, 0xD0, 0x5E, 0x04, 0x18, 0xA4, 0xEC, 0xC2, 0xE0, 0x41, 0x6E, 0x0F, 0x51, 0xCB, 0xCC, 0x24, 0x91, 0xAF, 0x50, 0xA1, 0xF4, 0x70, 0x39, 0x99, 0x7C, 0x3A, 0x85, 0x23, 0xB8, 0xB4, 0x7A, 0xFC, 0x02, 0x36, 0x5B, 0x25, 0x55, 0x97, 0x31, 0x2D, 0x5D, 0xFA, 0x98, 0xE3, 0x8A, 0x92, 0xAE, 0x05, 0xDF, 0x29, 0x10, 0x67, 0x6C, 0xBA, 0xC9, 0xD3, 0x00, 0xE6, 0xCF, 0xE1, 0x9E, 0xA8, 0x2C, 0x63, 0x16, 0x01, 0x3F, 0x58, 0xE2, 0x89, 0xA9, 0x0D, 0x38, 0x34, 0x1B, 0xAB, 0x33, 0xFF, 0xB0, 0xBB, 0x48, 0x0C, 0x5F, 0xB9, 0xB1, 0xCD, 0x2E, 0xC5, 0xF3, 0xDB, 0x47, 0xE5, 0xA5, 0x9C, 0x77, 0x0A, 0xA6, 0x20, 0x68, 0xFE, 0x7F, 0xC1, 0xAD};

    assert(len > 0 && len <= 128);
    assert(bits <= 1024);
    if (!bits)
        bits = 1024;

    memcpy(xkey, key, len);

    /* Phase 1: Expand input key to 128 bytes */
    // for i = T, T+1, ..., 127 do
    //     L[i] = PITABLE[L[i-1] + L[i-T]];
    if (len < 128)
    {
        i = 0;
        x = ((unsigned char *)xkey)[len - 1];
        do
        {
            x = PITABLE[(x + ((unsigned char *)xkey)[i++]) & 255];
            ((unsigned char *)xkey)[len++] = x;
        } while (len < 128);
    }

    /* Phase 2 - reduce effective key size to "bits" */
    // L[128-T8] = PITABLE[L[128-T8] & TM];
    len = (bits + 7) >> 3; // bits = T1, len = T8, T8 = (T1+7)/8;
    i = 128 - len;
    x = PITABLE[((unsigned char *)xkey)[i] & (255 >> (7 & -bits))]; // (255 >> (7 & -bits) = TM, TM = 255 MOD 2^(8 + T1 - 8*T8);
    ((unsigned char *)xkey)[i] = x;

    // for i = 127-T8, ..., 0 do
    //     L[i] = PITABLE[L[i+1] XOR L[i+T8]];
    while (i--)
    {
        x = PITABLE[x ^ ((unsigned char *)xkey)[i + len]];
        ((unsigned char *)xkey)[i] = x;
    }

    /* Phase 3 - copy to xkey in little-endian order */
    i = 63;
    do
    {
        xkey[i] = ((unsigned char *)xkey)[2 * i] +
                  (((unsigned char *)xkey)[2 * i + 1] << 8);
    } while (i--);
}

加密算法

加密操作将一组 64 比特的字存入 4 个字中再进行加密。

void rc2_encrypt(unsigned short xkey[64], unsigned char *plain, unsigned char *cipher)
{
    // xkey = K, plain = R
    unsigned x76, x54, x32, x10, i;

    x76 = (plain[7] << 8) + plain[6];
    x54 = (plain[5] << 8) + plain[4];
    x32 = (plain[3] << 8) + plain[2];
    x10 = (plain[1] << 8) + plain[0];

    for (i = 0; i < 16; i++)
    {
        // R[i] = R[i] + K[j] + (R[i-1] & R[i-2]) + ((~R[i-1]) & R[i-3]);
        // j = j + 1;
        // R[i] = R[i] rol s[i];
        x10 += (x32 & ~x76) + (x54 & x76) + xkey[4 * i + 0];
        x10 = (x10 << 1) + (x10 >> 15 & 1);

        x32 += (x54 & ~x10) + (x76 & x10) + xkey[4 * i + 1];
        x32 = (x32 << 2) + (x32 >> 14 & 3);

        x54 += (x76 & ~x32) + (x10 & x32) + xkey[4 * i + 2];
        x54 = (x54 << 3) + (x54 >> 13 & 7);

        x76 += (x10 & ~x54) + (x32 & x54) + xkey[4 * i + 3];
        x76 = (x76 << 5) + (x76 >> 11 & 31);

        // R[i] = R[i] + K[R[i-1] & 63];
        if (i == 4 || i == 10)
        {
            x10 += xkey[x76 & 63];
            x32 += xkey[x10 & 63];
            x54 += xkey[x32 & 63];
            x76 += xkey[x54 & 63];
        }
    }

    cipher[0] = (unsigned char)x10;
    cipher[1] = (unsigned char)(x10 >> 8);
    cipher[2] = (unsigned char)x32;
    cipher[3] = (unsigned char)(x32 >> 8);
    cipher[4] = (unsigned char)x54;
    cipher[5] = (unsigned char)(x54 >> 8);
    cipher[6] = (unsigned char)x76;
    cipher[7] = (unsigned char)(x76 >> 8);
}

解密算法

解密操作即为加密操作的逆运算。

void rc2_decrypt(unsigned short xkey[64], unsigned char *plain, unsigned char *cipher)
{
    unsigned x76, x54, x32, x10, i;

    x76 = (cipher[7] << 8) + cipher[6];
    x54 = (cipher[5] << 8) + cipher[4];
    x32 = (cipher[3] << 8) + cipher[2];
    x10 = (cipher[1] << 8) + cipher[0];

    i = 15;
    do
    {
        // R[i] = R[i] ror s[i];
        // R[i] = R[i] - K[j] - (R[i-1] & R[i-2]) - ((~R[i-1]) & R[i-3]);
        // j = j - 1;
        x76 &= 65535;
        x76 = (x76 << 11) + (x76 >> 5);
        x76 -= (x10 & ~x54) + (x32 & x54) + xkey[4 * i + 3];

        x54 &= 65535;
        x54 = (x54 << 13) + (x54 >> 3);
        x54 -= (x76 & ~x32) + (x10 & x32) + xkey[4 * i + 2];

        x32 &= 65535;
        x32 = (x32 << 14) + (x32 >> 2);
        x32 -= (x54 & ~x10) + (x76 & x10) + xkey[4 * i + 1];

        x10 &= 65535;
        x10 = (x10 << 15) + (x10 >> 1);
        x10 -= (x32 & ~x76) + (x54 & x76) + xkey[4 * i + 0];

        // R[i] = R[i] - K[R[i-1] & 63];
        if (i == 5 || i == 11)
        {
            x76 -= xkey[x54 & 63];
            x54 -= xkey[x32 & 63];
            x32 -= xkey[x10 & 63];
            x10 -= xkey[x76 & 63];
        }
    } while (i--);

    plain[0] = (unsigned char)x10;
    plain[1] = (unsigned char)(x10 >> 8);
    plain[2] = (unsigned char)x32;
    plain[3] = (unsigned char)(x32 >> 8);
    plain[4] = (unsigned char)x54;
    plain[5] = (unsigned char)(x54 >> 8);
    plain[6] = (unsigned char)x76;
    plain[7] = (unsigned char)(x76 >> 8);
}

RC5

RC5 同样也是分组密码,它支持可变的分组大小(32、64 或 128 比特),密钥长度(0 至 2040 位)和加密轮数(0 ~ 255)。RC5 中有几个参数,w 代表一个字的字节大小,RC5 是以一个字为单位来进行所有操作的;r 代表加密轮数;b 代表密钥的长度。RC5 常用的 w 通常为 16、32 和 64。下面实现的是 w 为 32 时的 RC5 算法。

RC5 和 RC2 类似,总共分为三个算法步骤。分别是密钥扩展、加密、解密。

算法中需要一些宏定义:

typedef unsigned int WORD;           /* Should be 32-bit = 4 bytes        */
#define w 32                         /* word size in bits                 */
#define r 12                         /* number of rounds                  */
#define b 16                         /* number of bytes in key            */
#define c 4                          /* number words in key               */
#define t 26                         /* size of table S = 2*(r+1) words   */
WORD S[t];                           /* expanded key table                */
WORD P = 0xb7e15163, Q = 0x9e3779b9; /* magic constants                   */
/* Rotation operators. x must be unsigned, to get logical right shift     */
#define ROTL(x, y) (((x) << (y & (w - 1))) | ((x) >> (w - (y & (w - 1)))))
#define ROTR(x, y) (((x) >> (y & (w - 1))) | ((x) << (w - (y & (w - 1)))))

密钥扩展算法

密钥扩展首先分别初始化 L 数组和 S 盒,随后通过 L 进行按字异或得到 S 盒。

void rc5_keygen(unsigned char *K) /* secret input ket K[0...b-1] */
{
    WORD i, j, k, u = w / 8, A, B, L[c];
    /* Initialize L, then S, then mix key into S */
    for (i = b - 1, L[c - 1] = 0; i != -1; i--)
    {
        L[i / u] = (L[i / u] << 8) + K[i];
    }
    for (S[0] = P, i = 1; i < t; i++)
    {
        S[i] = S[i - 1] + Q;
    }
    for (A = B = i = j = k = 0; k < 3 * t; k++, i = (i + 1) % t, j = (j + 1) % c) /* 3*t > 3*c */
    {
        A = S[i] = ROTL(S[i] + (A + B), 3);
        B = L[j] = ROTL(L[j] + (A + B), (A + B));
    }
}

加密算法

加密涉及的一个简单轮函数的加密。基于安全需要和时间方面的考虑,建议 12 或 20 轮加密。

void rc5_encrypt(unsigned char *plain, unsigned char *cipher) /* 2 WORD input pt/output ct */
{
    WORD pt[2], ct[2];
    for (int i = 0; i < 2; i++)
    {
        pt[i] = plain[4 * i] + (plain[4 * i + 1] << 8) + (plain[4 * i + 2] << 16) + (plain[4 * i + 3] << 24);
    }

    WORD A = pt[0] + S[0], B = pt[1] + S[1];
    for (int i = 1; i <= r; i++)
    {
        A = ROTL(A ^ B, B) + S[2 * i];
        B = ROTL(B ^ A, A) + S[2 * i + 1];
    }
    ct[0] = A;
    ct[1] = B;
    for (int i = 0; i < 2; i++)
    {
        cipher[4 * i] = ct[i] & 0xFF;
        cipher[4 * i + 1] = (ct[i] >> 8) & 0xFF;
        cipher[4 * i + 2] = (ct[i] >> 16) & 0xFF;
        cipher[4 * i + 3] = (ct[i] >> 24) & 0xFF;
    }
}

解密算法

解密实际上就是加密过程的逆运算。

void rc5_decrypt(unsigned char *cipher, unsigned char *plain) /* 2 WORD input ct/output pt */
{
    WORD pt[2], ct[2];
    for (int i = 0; i < 2; i++)
    {
        ct[i] = cipher[4 * i] + (cipher[4 * i + 1] << 8) + (cipher[4 * i + 2] << 16) + (cipher[4 * i + 3] << 24);
    }
    WORD B = ct[1], A = ct[0];
    for (int i = r; i > 0; i--)
    {
        B = ROTR(B - S[2 * i + 1], A) ^ A;
        A = ROTR(A - S[2 * i], B) ^ B;
    }
    pt[1] = B - S[1];
    pt[0] = A - S[0];
    for (int i = 0; i < 2; i++)
    {
        plain[4 * i] = pt[i] & 0xFF;
        plain[4 * i + 1] = (pt[i] >> 8) & 0xFF;
        plain[4 * i + 2] = (pt[i] >> 16) & 0xFF;
        plain[4 * i + 3] = (pt[i] >> 24) & 0xFF;
    }
}

RC6

RC6 是一个从 RC5 派生而来的对称分组加密算法,用以满足高级加密标准(AES)竞赛的要求。RC6 拥有 128 位的块大小,支持 128、192、256 位乃至 2040 位的密钥长度。像 RC5 一样,RC6 是可以被参数化的。它也因而支持变长的分组大小、密钥长度以及加密轮数。RC6 和 RC5 在结构、使用基于数据的置换规则、取模加法以及异或操作等很多方面都很相似。事实上,RC6 可以被看做是交织的两组平行的 RC5 加密。其中,RC6 使用了乘法运算,能够让置换基于字中每一位,而不是其中的几位。

算法中需要一些宏定义:

typedef unsigned int WORD;           /* Should be 32-bit = 4 bytes        */
#define w 32                         /* word size in bits                 */
#define r 20                         /* based on security estimates       */
#define bytes (w / 8)                /* bytes per word                    */
#define c ((b + bytes - 1) / bytes)  /* key in words, rounded up          */
#define R24 (2 * r + 4)              /* length of array S                 */
#define lgw 5                        /* log2(w) -- wussed out             */
WORD S[R24 - 1];                     /* Key schedule                      */
WORD P = 0xb7e15163, Q = 0x9e3779b9; /* magic constants                   */
/* Rotation operators. x must be unsigned, to get logical right shift     */
#define ROTL(x, y) (((x) << (y & (w - 1))) | ((x) >> (w - (y & (w - 1)))))
#define ROTR(x, y) (((x) >> (y & (w - 1))) | ((x) << (w - (y & (w - 1)))))

密钥扩展算法

RC6 中接受的密钥长度相比于 RC5 更长,生成的 S 盒大小为 2r+4。

void rc6_keygen(unsigned char *K, int b)
{
    int i, j, s, v;
    WORD L[(32 + bytes - 1) / bytes]; /* Big enough for max b */
    WORD A, B;

    L[c - 1] = 0;
    for (i = b - 1; i >= 0; i--)
        L[i / bytes] = (L[i / bytes] << 8) + K[i];

    S[0] = P;
    for (i = 1; i <= 2 * r + 3; i++)
        S[i] = S[i - 1] + Q;

    A = B = i = j = 0;
    v = R24;
    if (c > v)
        v = c;
    v *= 3;

    for (s = 1; s <= v; s++)
    {
        A = S[i] = ROTL(S[i] + A + B, 3);
        B = L[j] = ROTL(L[j] + A + B, A + B);
        i = (i + 1) % R24;
        j = (j + 1) % c;
    }
}

加密算法

RC6 加密时比 RC5 多了乘法运算,加密过程也变得更复杂。

void rc6_encrypt(unsigned char *plain, unsigned char *cipher)
{
    WORD pt[4], ct[4];
    for (int i = 0; i < 4; i++)
    {
        pt[i] = plain[4 * i] + (plain[4 * i + 1] << 8) + (plain[4 * i + 2] << 16) + (plain[4 * i + 3] << 24);
    }

    WORD A, B, C, D, t, u, x;

    A = pt[0];
    B = pt[1];
    C = pt[2];
    D = pt[3];
    B += S[0];
    D += S[1];
    for (int i = 2; i <= 2 * r; i += 2)
    {
        t = ROTL(B * (2 * B + 1), lgw);
        u = ROTL(D * (2 * D + 1), lgw);
        A = ROTL(A ^ t, u) + S[i];
        C = ROTL(C ^ u, t) + S[i + 1];
        x = A;
        A = B;
        B = C;
        C = D;
        D = x;
    }
    A += S[2 * r + 2];
    C += S[2 * r + 3];
    ct[0] = A;
    ct[1] = B;
    ct[2] = C;
    ct[3] = D;

    for (int i = 0; i < 4; i++)
    {
        cipher[4 * i] = ct[i] & 0xFF;
        cipher[4 * i + 1] = (ct[i] >> 8) & 0xFF;
        cipher[4 * i + 2] = (ct[i] >> 16) & 0xFF;
        cipher[4 * i + 3] = (ct[i] >> 24) & 0xFF;
    }
}

解密算法

解密过程同样是加密过程的逆运算。

void rc6_decrypt(unsigned char *cipher, unsigned char *plain)
{
    WORD pt[4], ct[4];
    for (int i = 0; i < 4; i++)
    {
        ct[i] = cipher[4 * i] + (cipher[4 * i + 1] << 8) + (cipher[4 * i + 2] << 16) + (cipher[4 * i + 3] << 24);
    }

    WORD A, B, C, D, t, u, x;

    A = ct[0];
    B = ct[1];
    C = ct[2];
    D = ct[3];
    C -= S[2 * r + 3];
    A -= S[2 * r + 2];
    for (int i = 2 * r; i >= 2; i -= 2)
    {
        x = D;
        D = C;
        C = B;
        B = A;
        A = x;
        u = ROTL(D * (2 * D + 1), lgw);
        t = ROTL(B * (2 * B + 1), lgw);
        C = ROTR(C - S[i + 1], t) ^ u;
        A = ROTR(A - S[i], u) ^ t;
    }
    D -= S[1];
    B -= S[0];
    pt[0] = A;
    pt[1] = B;
    pt[2] = C;
    pt[3] = D;

    for (int i = 0; i < 4; i++)
    {
        plain[4 * i] = pt[i] & 0xFF;
        plain[4 * i + 1] = (pt[i] >> 8) & 0xFF;
        plain[4 * i + 2] = (pt[i] >> 16) & 0xFF;
        plain[4 * i + 3] = (pt[i] >> 24) & 0xFF;
    }
}

References

RC_algorithm
A Comparative Study of Rivest Cipher Algorithms
现代密码学教程
A Description of the RC2(r) Encryption Algorithm
The RC5 Encryption Algorithm
The RC6 Block Cipher


c crypto

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

Have Fun with Metasploit-Framework
Python实现TEA、XTEA、XXTEA加密解密算法