0x00 Introduction

Blowfish是一种对称密钥分组密码，Bruce Schneier在1993年设计并公布。它没有专利，任何人均可自由使用。

0x01 Detail

• 密钥长度：32-448位
• 分组长度：64位
• 16轮循环的Feistel结构

0x02 Feistel Structure

在介绍Blowfish之前先来搞清楚Feistel Structure(下图来自Wikipedia):

1. 将原数据分成左右两部分
2. 原数据的右侧不变，直接变成下次循环的左侧
3. 将原数据的右侧与子密钥传递给轮函数F
4. 轮函数返回值与原数据左侧进行异或运算，变成下次循环的右侧

上述4个步骤是一轮循环的工作过程，Feistel Structure是进行了16轮循环方才完成一次加密。需要说明一点，在最后一轮循环中左右数据不对调。解密过程是加密过程的反向，具体可参照上图，不再赘述。

##0x03 Source Code

笔者分析的源码是Paul Kocher版本，并没有使用Bruce Schneier版本。Schneier版本中的子密钥来源是BLOWFISH.DAT文件，而Kocher版本是直接在源文件中定义子密钥，分析起来较为直观。如需其他版本可到此网站下载

0x03.1 BLOWFISH_CTX

在blowfish.h头文件中有如下定义：

typedef struct {
  unsigned long P[16 + 2];
  unsigned long S[4][256];
} BLOWFISH_CTX;

为结构体定义别名，结构体中的两数组即P-Box与S-Box。

0x03.2 ORIG_P[16 + 2]与ORIG_S[4][256]

ORIG_P与ORIG_S取自圆周率的小数位，每4个字节赋值给其中的一个元素。

0x03.3 void Blowfish_Init(BLOWFISH_CTX *ctx, unsigned char *key, int keyLen)

该函数用来初始化S-Box与P-Box。传递参数中的key即密钥，keyLen是密钥长度。

1. 对BLOWFISH_CTX *ctx中S-Box进行初始化，直接将ORIG_S中的每个元素逐一赋值给S-Box
2. 对BLOWFISH_CTX *ctx中P-Box进行初始化，具体过程如下：
   a. data=0x00000000;
   b. 如果参数中的字符数组key长度不足4，则循环使用key中字符(当使用到key中最后一个字符时，下一个字符是key中第一个字符)与data << 8进行或运算
   上述过程总结起来就是将参数中的字符数组key转换为ASCII码形式(e.g.:key[3]="abc"---->>0x61626361并存储于data中)
   c. 将ORIG_P中的每个元素与data作异或运算后逐一赋值给P-Box

3. datal=0x00000000;
datar=0x00000000;

4. 将上面经过变换后的ctx，datal与datar传递给Blowfish_Encrypt

5. 将加密后的datal与datar赋值给P-Box中的元素
6. 重复9次步骤4-5
7. 与步骤4类似，不过这次传递的是上面过程中已经加密后的datal与datar
8. 将加密后的datal与datar赋值给S-Box中的元素
9. 重复512次步骤7-8

   步骤5、8中提到的赋值过程是这样的(以步骤5来举例)：
   第一次 P[0]=datal，P[1]=datar
   第二次 P[2]=datal，P[3]=datar
   ......

0x03.4 void Blowfish_Encrypt(BLOWFISH_CTX *ctx, unsigned long *xl, unsigned long *xr)

该函数是Blowfish的加密部分。传递参数中的ctx应该已经初始化过S-Box与P-Box，xl指向原数据的左半部分，xr指向原数据的右半部分。

1. 左侧数据与P-Box中第i个元素作异或运算(i=n-1,其中n是轮数)
2. 将左侧数据与ctx传递给轮函数F
3. 右侧数据与轮函数F返回值作异或运算
4. 交换运算后的左右两侧数据
5. 重复16次步骤1-5
6. 将最后一轮运算互换的左右两侧数据换回来
7. 右侧数据与P-Box中第16个元素作异或运算
8. 左侧数据与P-Box中第17个元素作异或运算

上述过程即一次完整的加密过程，可参照下图来理解(来自Wikipedia，其中轮函数F的工作过程见0x03.6)：

0x03.5 void Blowfish_Decrypt(BLOWFISH_CTX *ctx, unsigned long *xl, unsigned long *xr)

解密过程是加密过程的反向，如有困惑，可参照源码理解，不再赘述。

0x03.6 static unsigned long F(BLOWFISH_CTX *ctx, unsigned long x)

轮函数工作过程：

1. 将参数x逐字节分割，赋值给a,b,c,d四个变量(e.g.:x=0x21564378,则a=0x21,b=0x56,c=0x43,d=0x78)
2. y = ((ctx->S[0][a] + ctx->S[1][b]) ^ ctx->S[2][c]) + ctx->S[3][d];
3. 返回y的值

0x04 Demo

此Demo来自Paul Kocher版本根目录下的blowfish_test.c：

#include <stdio.h>
#include "blowfish.h"

void main(void) {
  unsigned long L = 1, R = 2;
  BLOWFISH_CTX ctx;

  Blowfish_Init (&ctx, (unsigned char*)"TESTKEY", 7);
  Blowfish_Encrypt(&ctx, &L, &R);
  printf("%08lX %08lX\n", L, R);

  if (L == 0xDF333FD2L && R == 0x30A71BB4L)
      printf("Test encryption OK.\n");
  else
      printf("Test encryption failed.\n");
  Blowfish_Decrypt(&ctx, &L, &R);
  if (L == 1 && R == 2)
        printf("Test decryption OK.\n");
  else
      printf("Test decryption failed.\n");
}

需要说明的一点是Paul Kocher这个版本并没有考虑到小端序的情况，它均按大端序来处理，所以如果在Linux平台运行此Demo会像下图所示：

可以看到加密结果并非源码中给出的结果，而在Windows平台下一切正常：

0x05 参考

• Wikipedia
• 圆周率小数部分

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课