blowfish加密算法

Blowfish是1993年布鲁斯·施奈尔(Bruce Schneier)开发的对称密钥区块加密算法，区块长为64位，密钥为1至448位的可变长度。与DES等算法相比，其处理速度较快。因为其无须授权即 可使用，作为一种自由授权的加密方式在SSH、文件加密软件等被广泛地使用。
关于此算法的发明者：
布鲁斯·施奈尔 （Bruce Schneier，1963年1月15日－）是一位美国的密码学学者、信息安全专家与作家。他撰写了数本信息安全与密码学相关的书籍，并且创办了BT公司并担任其首席技术官(CTO)。

分组密码(Block cypher)

分组密码（Block cypher，又称分块密码），是一种对称密钥密码。它的特点是将明文分成多个等长的组，并用相同的密码算法和密钥对每组分别进行加密和解密。其中典型的如DES和AES作为美国政府核定的标准加密算法，应用领域从电子邮件加密到银行交易转帐，非常广泛。
blowfish属于分组密码中的一种。

要了解blowfish加密算法，也许我们应该先了解一下Feistel 密码,因为blowfish加密算法也是feistel密码算法中的一种：
假设F是轮函数，然后K₀到K_n作为0到n轮的sub-keys,
基本的操作如下：

把明文分为相等的两块：L₀和R₀,
对于每一轮i=0,1,2,…,n 进行如下运算：
L_i+1 = R_i
R_i+1 = L_i ^ F(R_i,K_i)
最后得到密文(R_n+1,L_n+1)
解密(R_n+1,L_n+1)是通过如下步骤来完成的：
令i=n,n-1,…,0
R_i = L_i+1
L_i = R_i+1 ^ F(L_i+1,K_i)
最后又得到原来的(L₀,R₀)了

这么说可能不好理解，看下图（来自wikipedia)就清楚了：

简单地说：
就是一种分组密码，一般分为64位一组，一组分左右部分，进行一般为16轮的迭代运算，每次迭代完后交换左右位置，可以自己进行设计的有:
分组大小
密钥长度
轮次数
子密钥生成
轮函数

然后应该了解一下块密码的工作模式：
from wikipedia:

密码学中，块密码的工作模式允许使用同一个块密码密钥对多于一块的数据进行加密，并保证其安全性。[1][2] 块密码自身只能加密长度等于密码块长度的单块数据，若要加密变长数据，则数据必须先被划分为一些单独的密码块。通常而言，最后一块数据也需要使用合适填充 方式将数据扩展到符合密码块大小的长度。一种工作模式描述了加密每一数据块的过程，并常常使用基于一个通常称为初始化向量的附加输入值以进行随机化，以保 证安全[1]。

工作模式主要用来进行加密和认证。[1][3] 对加密模式的研究曾经包含数据的完整性保护，即在某些数据被修改后的情况下密码的误差传播特性。后来的研究则将完整性保护作为另一个完全不同的，与加密无 关的密码学目标。部分现代的工作模式用有效的方法将加密和认证结合起来，称为认证加密模式。[2]

虽然工作模式通常应用于对称加密[2]，它亦可以应用于公钥加密，例如在原理上对RSA进行处理，但在实用中，公钥密码学通常不用于加密较长的信息，而是使用混合加密方案
一般来说常用的加密模式有这么几种：
电子密码本（ECB）
密码块链接（CBC）：在CBC模式中，每个平文块先与前一个密文块进行异或后，再进行加密。在这种方法中，每个密文块都依赖于它前面的所有平文块。同时，为了保证每条消息的唯一性，在第一个块中需要使用初始化向量。
填充密码块链接（PCBC）
密文反馈（CFB）
输出反馈（OFB）
计数器模式（CTR）

初始化向量（IV）

初始化向量（IV，Initialization Vector）是许多工作模式中用于随机化加密的一块数据，因此可以由相同的明文，相同的密钥产生不同的密文，而无需重新产生密钥，避免了通常相当复杂的这一过程。

初始化向量与密钥相比有不同的安全性需求，因此IV通常无须保密，然而在大多数情况中，不应当在使用同一密钥的情况下两次使用同一个IV。对于 CBC和CFB，重用IV会导致泄露平文首个块的某些信息，亦包括两个不同消息中相同的前缀。对于OFB和CTR而言，重用IV会导致完全失去安全性。另 外，在CBC模式中，IV在加密时必须是无法预测的；特别的，在许多实现中使用的产生IV的方法，例如SSL2.0使用的，即采用上一个消息的最后一块密 文作为下一个消息的IV，是不安全的[12]。

填充

块密码只能对确定长度的数据块进行处理，而消息的长度通常是可变的。因此部分模式（即ECB和CBC）需要最后一块在加密 前进行填充。有数种填充方法，其中最简单的一种是在平文的最后填充空字符以使其长度为块长度的整数倍，但必须保证可以恢复平文的原始长度；例如，若平文是 C语言风格的字符串，则只有串尾会有空字符。稍微复杂一点的方法则是原始的DES使用的方法，即在数据后添加一个1位，再添加足够的0位直到满足块长度的 要求；若消息长度刚好符合块长度，则添加一个填充块。最复杂的则是针对CBC的方法，例如密文窃取，残块终结等，不会产生额外的密文，但会增加一些复杂 度。布鲁斯·施奈尔和尼尔斯·弗格森提出了两种简单的可能性：添加一个值为128的字节（十六进制的80），再以0字节填满最后一个块；或向最后一个块填 充n个值均为n的字节[13]。

CFB，OFB和CTR模式不需要对长度不为密码块大小整数倍的消息进行特别的处理。因为这些模式是通过对块密码的输出与平文进行异或工作的。最后 一个平文块（可能是不完整的）与密钥流块的前几个字节异或后，产生了与该平文块大小相同的密文块。流密码的这个特性使得它们可以应用在需要密文和平文数据 长度严格相等的场合，也可以应用在以流形式传输数据而不便于进行填充的场合。

另外在mcrypt的man文档里也找到了加密模式的介绍：

加密模式

modes of encryption:
ECB: The Electronic CodeBook mode. It is the simplest mode to use with a block cipher. Encrypts each block independently.

CBC: The Cipher Block Chaining mode. It is better than ECB since the plaintext is XOR’ed with the previous ciphertext. A random block is placed as the first block so the same block or messages always encrypt to something different. (This is the default mode)

CFB: The Cipher-Feedback Mode (in 8bit). This is a self-synchronizing stream cipher implemented from a block cipher.

OFB: The Output-Feedback Mode (in 8bit). This is a synchronous stream cipher implemented from a block cipher. It is intended for use in noisy lines, because corrupted ciphertext blocks do not corrupt the plaintext blocks that follow. Insecure (because used in 8bit mode) so I recommend against using it. Added just for completeness.

nOFB: The Output-Feedback Mode (in nbit). n Is the size of the block of the algorithm. This is a synchronous stream cipher implemented from a block cipher. It is intended for use in noisy lines, because corrupted ciphertext blocks do not corrupt the plaintext blocks that follow.

via /> BTW,The author of mcrypt and libmcrypt is Nikos Mavroyanopoulos.

分块大小

Block size

现代加密算法中，对称密钥算法通常被分为stream ciphers和block ciphers。分块密码处理固定长度的字符串位数(bit)。这个比特字符串的长度必须和分块大小一样长。输入（明文）和输出（密文）都是同样长度的。输出不能比输入短——这是遵循Pigeonhole principle（鸽巢原理，又名狄利克雷抽屉原理、鸽笼原理）和密码必须是可逆的事实——然而，输出比输入更长又是不可取的。
鸽巢原理：
其中一种简单的表述法为：
若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。
另一种为：
若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。
拉姆齐定理是此原理的推广。

通俗点说：
10只鸽子放进9个鸽笼，那么一定有一个鸽笼放进了至少两只鸽子。

S-box (Substitution-box,替换盒)
在分块密码中，S-box通常被用来掩盖密钥和密文之间的关系。

In general, an S-Box takes some number of input bits, m, and transforms them into some number of output bits, n: an m×n S-Box can be implemented as a lookup table with 2m words of n bits each. Fixed tables are normally used, as in the Data Encryption Standard (DES), but in some ciphers the tables are generated dynamically from the key; e.g. the Blowfish and the Twofish encryption algorithms. Bruce Schneier describes IDEA’s modular multiplication step as a key-dependent S-Box.

IDEA(International Data Encryption Algorithm)

Rijndael S-box

算法说明：
BlowFish 使用了两个box,除了著名的S-box，还有一个p-box
pbox有18个unsigned long元素
sbox有4×256个unsigned long元素
BlowFish算法中，有一个核心加密函数，该函数输入64位信息，运算后， 以64位密文的形式输出。 用BlowFish算法加密信息，需要两个过程：
这里我看的源码是Paul Kocher的C语言版本。
源码下载地址：http:///blowfish-download.html

1.密钥预处理
2.信息加密

结构体定义：

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

1.密钥预处理
BlowFish算法的源密钥——pbox和sbox是固定的。此pbox和sbox的值来自PI的十六进制数字值，使用这些数的原因是这些数看不出有什么明显的规律。(PI)
这里摘取1-500位：
3.243F6A8885 A308D31319 8A2E037073 44A4093822 299F31D008
  2EFA98EC4E 6C89452821 E638D01377 BE5466CF34 E90C6CC0AC
  29B7C97C50 DD3F84D5B5 B547091792 16D5D98979 FB1BD1310B
  A698DFB5AC 2FFD72DBD0 1ADFB7B8E1 AFED6A267E 96BA7C9045
  F12C7F9924 A19947B391 6CF70801F2 E2858EFC16 636920D871
  574E69A458 FEA3F4933D 7E0D95748F 728EB65871 8BCD588215
  4AEE7B54A4 1DC25A59B5 9C30D5392A F26013C5D1 B023286085
  F0CA417918 B8DB38EF8E 79DCB0603A 180E6C9E0E 8BB01E8A3E
  D71577C1BD 314B2778AF 2FDA55605C 60E65525F3 AA55AB9457
  48986263E8 144055CA39 6A2AAB10B6 B4CC5C3411 41E8CEA154

void Blowfish_Init(BLOWFISH_CTX *ctx, unsigned char *key, int keyLen) {
  int i, j, k;
  unsigned long data, datal, datar;

  for (i = 0; i < 4; i++) {
    for (j = 0; j < 256; j++)
      ctx->S[i][j] = ORIG_S[i][j];
  }

  j = 0;
  for (i = 0; i < N + 2; ++i) {
    data = 0x00000000;
    for (k = 0; k < 4; ++k) {
      data = (data << 8) | key[j];
      j = j + 1;
      if (j >= keyLen)
        j = 0;
    }
    ctx->P[i] = ORIG_P[i] ^ data;
  }

  datal = 0x00000000;
  datar = 0x00000000;

  for (i = 0; i < N + 2; i += 2) {
    Blowfish_Encrypt(ctx, &#038;datal, &#038;datar);
    ctx->P[i] = datal;
    ctx->P[i + 1] = datar;
  }

  for (i = 0; i < 4; ++i) {
    for (j = 0; j < 256; j += 2) {
      Blowfish_Encrypt(ctx, &#038;datal, &#038;datar);
      ctx->S[i][j] = datal;
      ctx->S[i][j + 1] = datar;
    }
  }
}

我们要加密一个信息，
需要自己选择一个key，用这个key对pbox和sbox进行变换，得到下一步信息加密
所要用的pbox和sbox。
具体的变化算法如下：
用原sbox: ORIG_S 填充 sbox

然后，每次取key与data进行运算，运算后的结果送给pbox
运算过程是这样的：
进行N+2次运算（N=16),
令 32位无符号data为0,由于Key是unsigned char类型的，每次对data左移8位(一个字节)之后与
相应的key相或（即相加），当key长度小于4时，循环使用Key。

接下来，用bf_encypt加密一个全0的64位信息（分为datal和datar,各32位）
用输出的结果datal和datar分别替换pbox[0]和pbox[1]
然后，继续加密datal和datar,用输出结果替换pbox[2]和pbox[3]
……
这样循环18次，把pbox全部替换完成。

接下来是对sbox的替换了。
这次总共是循环4×256次，每次循环的过程与上面的一样。
不过这里用的datal和datar就是上面运算过后的datal和datar.

2.信息加密
接下来看这个加密函数，上面的初始化过程已经用到它了。

void Blowfish_Encrypt(BLOWFISH_CTX *ctx, unsigned long *xl, unsigned long *xr){
  unsigned long  Xl;
  unsigned long  Xr;
  unsigned long  temp;
  short       i;

  Xl = *xl;
  Xr = *xr;

  for (i = 0; i < N; ++i) {
    Xl = Xl ^ ctx->P[i];
    Xr = F(ctx, Xl) ^ Xr;

    temp = Xl;
    Xl = Xr;
    Xr = temp;
  }

  temp = Xl;
  Xl = Xr;
  Xr = temp;

  Xr = Xr ^ ctx->P[N];
  Xl = Xl ^ ctx->P[N + 1];

  *xl = Xl;
  *xr = Xr;
}

与上面说的Feistel 密码的运算过程是一样的：
把64位的明文分为l和r
进行16轮运算：
令i=0,1,2,3,…,N-1
Xl = Xl ^ ctx->P[i];
Xr = F(ctx, Xl) ^ Xr;
若i<N,交换Xl和Xr的值继续做上述运算。
16轮运算完了之后，再做一次Xl与Xr的交换，因为第16次运算完了之后，实际上
没有再做运算了，但是Xl与Xr还是交换了，因此，得换回来。

然后，Xr = Xr ^ ctx->P[N];
Xl = Xl ^ ctx->P[N + 1];
现在的Xl和Xr就是加密后的数据了。
加密过程图解：

这加密过程中用到了F变换：

static unsigned long F(BLOWFISH_CTX *ctx, unsigned long x) {
   unsigned short a, b, c, d;
   unsigned long  y;

   d = (unsigned short)(x & 0xFF);
   x >>= 8;
   c = (unsigned short)(x & 0xFF);
   x >>= 8;
   b = (unsigned short)(x & 0xFF);
   x >>= 8;
   a = (unsigned short)(x & 0xFF);
   y = ctx->S[0][a] + ctx->S[1][b];
   y = y ^ ctx->S[2][c];
   y = y + ctx->S[3][d];

   return y;
}

这个变换是这样的：
它接收一个32位的数据，然后从高位到低位分为四段，每段8位，依次给
a,b,c,d
取sbox[0][a]+sbox[1][b]，相加后的结果再与sbox[2][c]做异或运算，
得出的结果再加上sbox[3][d]
由于sbox的元素都是32位的，因此，F变换后的输出也是32位的。
轮函数图解：

解密函数：
可以看到解密函数与加密函数非常的相似，只是把p0,p1,…,p17 逆序使用：

void Blowfish_Decrypt(BLOWFISH_CTX *ctx, unsigned long *xl, unsigned long *xr){
  unsigned long  Xl;
  unsigned long  Xr;
  unsigned long  temp;
  short       i;

  Xl = *xl;
  Xr = *xr;

  for (i = N + 1; i > 1; --i) {
    Xl = Xl ^ ctx->P[i];
    Xr = F(ctx, Xl) ^ Xr;

    /* Exchange Xl and Xr */
    temp = Xl;
    Xl = Xr;
    Xr = temp;
  }

  /* Exchange Xl and Xr */
  temp = Xl;
  Xl = Xr;
  Xr = temp;

  Xr = Xr ^ ctx->P[1];
  Xl = Xl ^ ctx->P[0];

  *xl = Xl;
  *xr = Xr;
}

关于BlowFish 密码，个人认为可以把它理解为一种复杂的异或密码,异或运算的规律：
A ^ 0 = A
A ^ A = 0
(A ^ B) ^ C = A ^ (B ^ C)
(B ^ A) ^ A = B ^ 0 = B
按这种逻辑，文本序列的每个字符可以通过与给定的密钥进行按位异或运算来加密。如果要解密，只需要将加密後的结果与密钥再次进行按位异或运算即可。

/>