博客

流加密RC4的C语言实现

2015/01/18 技术
2015-01-18-Rc4

2015-01-18-Rc4

1 前言

这段时间弄了一下加密算法RC4，一开始感觉这个算法很简单，就试着弄了一下，结果自己写了一下代码，调试了很久，都没通过，又用了网上的开源的代码，结果还是调试不通过，后来经过别人的提醒，才发现自己错在了那里，事后一想感觉自己太不应该了，所以想写一篇blog出来，总结一下自己为什么会出现这么幼稚的问题，再顺便把RC4算法的实现记录一下。

2 RC4算法介绍

关于RC4算法的历史的介绍，这里不再多介绍了，如果你感兴趣，可以点这里维基百科-rc4

2.1 算法原理的介绍

RC4算法有下面几个部分构成

  1. Sbox(S盒):256Byte(256个字节),Sbox是unsigned char类型的数据 该算法的关键的数据结构,构成加密操作的一个不可获取的结构.
  2. key(秘钥):长度范围是[1 Byte,255 Byte]. 加密数据输入的秘钥,任何加密数据里面都有秘钥的存在.为了是该算法的加密行更好一点,可以使秘钥长度大一点,当秘钥长度大于128位,就无法使用暴力破解的方式进行破解.
  3. inputByte/outputByte(要加密的数据/要解密的数据) 该算法的特殊之处就在于加密和解密使用同一个算法,所以输入的是明文,输出的就是密文,输入的密文,输出的就是明文.

该算法的核心就是两部分一个是伪随机数生成器,一个是异或操作.所以在我们实现的过程中,只需要实现这两个部分就可以了.

2.2 伪代码实现

该算法首先使用伪代码实现以下,然后再后边在使用c语言将伪代码实现出来.下面就是具体的伪代码的实现

  1. 构造Sbox 作为RC4算法的最重要的部分,该算法的第一部分就是构造Sbox,实现的伪代码如下所示 
  for i from 0 to 255
    S[i] := i
  endfor
  j := 0
  for( i=0 ; i<256 ; i++)
    j := (j + S[i] + key[i mod keylength]) % 256
    swap values of S[i] and S[j]
endfor

构造Sbox的第一步就是先将初始化长度为256的sbox,然后为了制造伪随机数,使用输入的key,Sbox[i]和j的值(每次都会改变),这三个项结合在一起,将初始化后的Sbox打乱.

  1. 对数据进行亦或运算 伪代码的实现如下所示: 
i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256   // 1
    j := (j + S[i]) mod 256 // 2
    swap values of S[i] and S[j]  //3
    k := inputByte ^ S[(S[i] + S[j]) % 256] //4
    output K
endwhile

对数据进行亦或操作主要在代码4处进行,代码1,2,3处的代码主要进行的工作也是对sbox进行处理,从这里看出,该算法的核心就是sbox.

3 算法实现

rc4的实现,网上有很多的版本,而且别的blog中,也有c和c++的版本实现.本人参考了一下,发现网上的c++版本的RC4实现,比较繁琐.C代码的实现主要是在Windows平台上,移植性差了点.所以我就想实现一个Linux平台上的RC4.本博客中,使用的是开源项目的代码,该代码的链接:点这里
一开始我是自己实现的上面的算法,但是发现自己实现的和开源组织的代码还是有一定差距的,所以这里直接使用开源的代码,并且学习一下别人的实现.

代码如下: 

  #ifndef _SYS_CRYPTO_RC4_RC4_H_
#define _SYS_CRYPTO_RC4_RC4_H_

struct rc4_state {
    u_char  perm[256];
    u_char  index1;
    u_char  index2;
};

extern void rc4_init(struct rc4_state *state, const u_char *key, int keylen);
extern void rc4_crypt(struct rc4_state *state,
        const u_char *inbuf, u_char *outbuf, int buflen);

#endif

#include <sys/types.h>
#include <crypto/rc4/rc4.h>

static __inline void
swap_bytes(u_char *a, u_char *b)
{
    u_char temp;

    temp = *a;
    *a = *b;
    *b = temp;
}

/*
 * Initialize an RC4 state buffer using the supplied key,
 * which can have arbitrary length.
 */
void
rc4_init(struct rc4_state *const state, const u_char *key, int keylen)
{
    u_char j;
    int i;

    /* Initialize state with identity permutation */
    for (i = 0; i < 256; i++)
        state->perm[i] = (u_char)i; 
    state->index1 = 0;
    state->index2 = 0;

    /* Randomize the permutation using key data */
    for (j = i = 0; i < 256; i++) {
        j += state->perm[i] + key[i % keylen]; 
        swap_bytes(&state->perm[i], &state->perm[j]);
    }
}

/*
 * Encrypt some data using the supplied RC4 state buffer.
 * The input and output buffers may be the same buffer.
 * Since RC4 is a stream cypher, this function is used
 * for both encryption and decryption.
 */
void
rc4_crypt(struct rc4_state *const state,
    const u_char *inbuf, u_char *outbuf, int buflen)
{
    int i;
    u_char j;

    for (i = 0; i < buflen; i++) {

        /* Update modification indicies */
        state->index1++;
        state->index2 += state->perm[state->index1];

        /* Modify permutation */
        swap_bytes(&state->perm[state->index1],
            &state->perm[state->index2]);

        /* Encrypt/decrypt next byte */
        j = state->perm[state->index1] + state->perm[state->index2];
        outbuf[i] = inbuf[i] ^ state->perm[j];
    }
}

该算法的比较有特色的地方就是将Sbox直接封装成一个结构体,而不是想我自己一样,直接就是一个长度为256的数组中.其余的就和伪代码一样了.

4 算法的优缺点

  1. 优点:
    • 容易实现,不用依赖第三方库.
    • 算法的输入和输出可以是同一个文件,也就是说可以在原地进行加密和解密.
    • 根据目前的分析结果，没有任何的分析对于密钥长度达到128位的RC4有效，所以，RC4是目前最安全的加密算法之一.
  2. 缺点:
    • 由于RC4算法加密是采用的xor，所以，一旦子密钥序列出现了重复，密文就有可能被破解.于如何破解xor加密，请参看Bruce Schneier的Applied Cryptography一书的1.4节Simple XOR.

5 需要注意的地方

在需要注意的这个地方就是在调用的时候,一定要注意构造Sbox,一开始在加密的时候,要初始化Sbox,在解密中,也要 初始化Sbox .我就是在解密的时候没有初始化Sbox,所以在解密的时候,就是不正确.

原因分析:该算法的加解密都是基于Sbox,当在加密的过程当中,对Sbox,进行初始化,然后对数据进行加密,会改变Sbox中数据的顺序.所以进行解密的时候,要重新初始化Sbox,在进行解密,这意味着,只要秘钥一样,每次初始化的Sbox,都是一样的.这个可以从算法中看出来.调用的代码如下所示: 

  int main(int argc, char* argv[]){

    int dataLength = 8;
    int keyLength = 8;
    const unsigned char dataStream[8] = {0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef};
    printf("before\n");
    for (int i = 0; i < dataLength ; i++) {
        printf("%x,",dataStream[i]);
    }
    printf("\n");
    unsigned char encryp[dataLength];
    unsigned char decryp[dataLength];
    unsigned char key[8] = {0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef};
    struct rc4_state state;

    rc4_init(&state, key, keyLength);// this code is very important

    rc4_crypt(&state, dataStream, encryp, dataLength);
    printf("\nencrypt\n");
    for (int i = 0; i < dataLength ; i++) {
        printf("%x,",encryp[i]);
    }
    printf("\nafter \n");
    rc4_init(&state, key, keyLength);// this code is very important
    rc4_crypt(&state, encryp, decryp, dataLength);
    for (int i = 0; i < dataLength ; i++) {
        printf("%x,",decryp[i]);
    }
    printf("\n");
    return 0;
}

6 感悟

在实现RC4的过程中,遇到的问题到时不多,唯一一个问题就是在解密的时候,怎么都不能正常的解密,原因就是没有对Sbox进行重新初始化,究其原因就是对算法的原理没有搞明白.还有就是没有好好的对别人的代码进行深入的理解.总是停留在表面上.这样是难以提高自己的能力.以后的工作中,要注意两点:

  1. 静下心来研究代码.
  2. 做个有心人,多学习人家代码中实现的好的地方.

Author: Tiankai

Created: 2015-01-20 Tue 01:01

Emacs 24.4.1 (Org mode 8.2.10)

Validate

Search

    Table of Contents