扩散算法是一种数据处理方法，目的在于通过扩散处理使得元素之间相互影响，从而实现完全的雪崩效应。该算法可用于数据加密/解密，计算消息摘要（Message Digest），生成消息认证码（Message Authentication Code），生成随机数等。

扩散算法是一种数据处理方法，目的在于通过扩散处理使得元素之间相互影响，从而实现完全的雪崩效应。雪崩效应是指原始输入中的微小变化，经过积累发展后而造成输出的巨大改变。而完全的雪崩效应，对于输入中任意的微小变化都会造成输出全部产生改变（100%的扩散率）。

扩散算法通过在元素之间建立扩散路径，使元素沿着该路径向其他元素扩散。每一个元素都沿着指定的路径扩散，从而使元素间相互发生影响。

扩散算法的核心在于扩散过程，扩散过程由扩散网络决定。所谓扩散，是指元素传递影响的过程，若元素A扩散到元素B，则当A发生改变时，B也发生改变。

若有N（N＞=1）个元素组成的集合M。通过一定的规则使M中的元素相对应，如M1（起点）对应M4（终点），M4对应M8，M8对应M2，M2对应M6…，描述为Mi向Mj扩散，记作Mi→Mj；分别取出相对应的元素并组成表达式，通过一定的方法对表达式进行处理，再使用处理的结果更新被对应的元素（终点）。当起点元素发生改变时，终点元素也发生改变；在处理的过程中这种改变会发生传递，进而影响其他元素，最终影响所有元素。

在上述过程中，元素间的对应关系用扩散路径（以下简称路径）表示，起点元素（Mi）叫做原体，终点元素（Mj）叫做受体；由元素组成的表达式叫做扩算式；对扩算式的处理叫做扩散运算（为防止受体丢失，扩散运算时需加入受体一同运算）；所有路径的集合叫做扩散网络（以下简称网络）；对整个网络执行一次扩散叫做一个周期。

参照图1，X、Y为元素数量均为8的分组；方框中的数字为元素索引，连接方框之间的线条为扩散路径，箭头指向的元素为受体元素，其中虚线表示元素X[0]完成完全扩散所走的路径；元素索引上方的“*”号表示被X[0]所影响的元素；整个网络的扩散分为四个阶段完成，执行扩散时需从上到下顺序执行；

建立网络时，若要达到100%的扩散率，必须要保证所建立的网络对于每一个输入元素都能影响任何一个输出元素；每个扩散式的扩散运算都必须满足原体中任意元素的变化都将引起受体的变化（受体为元素组时，则元素组内的每一个元素都要发生变化）。

丰富的网络建立规则

网络可以建立为有序的（图1），也可以建立为无序的（图2）。

对于有序的网络，则不需要手动建立路径，直接套用公式即可。设N为分组长度，先计算对数 ，对G进行向上取整；计算基于N的长度 ；计算完成完全扩散所需的阶段数量round=G+E, E＞=0；E的取值范围跟分组数量有关，E的具体取值可根据分组数量或者需要来设定。

对于无序的网络，则需要手动建立路径，对于任意N长度的分组均存在最短路径（即单位元素完成完全扩散所需的路径长度，每一阶为一个长度），或许可以通过算法找出该最短路径，应该不是什么难事；或许为了某种目的可以增加一些额外的路径，让网络看起来更加复杂。

丰富的扩散式建立方式

扩散式的建立除必须包含原体和受体外，还可以包含其他任意元素（元素组），想怎么建，就怎么建了。

丰富的扩散运算方式

世间函数千千万万，谁人知道你用了谁。想从数据中分析出使用了什么样的函数，这几乎是天方夜谭。只需稍稍更改一点函数参量，就能使数据变得面目全非，犹如蝴蝶扇翅而飓风忽起。

丰富的元素组织方式

完成完全扩散所需要的扩散阶段跟元素数量有关，对于1024字节长度的分组（元素类型为byte），则需要 个扩散阶段。若将4个元素组成int类型，则只需要 个扩散阶段。若将8个元素组成long类型，则仅需要 个扩散阶段。当然，元素可以任意组合。不过使用组合元素也没那么容易，这还需要满足对于元素组内任意一个元素的变化都需要引起其他元素的变化（包括原体和受体）。元素组织方式可参见图3。

天生的并行计算支持

每个扩散阶段都需要对当前阶段的每一条路径进行扩散运算，因为目前的计算机以串行的方式执行指令，因此需要对这些路径逐一执行扩散运算。但显然这些路径是可以一并执行的，不同路径内的元素互不影响。如果每个阶段的扩散运算都可以同一时刻并行处理的话，那么对于N个元素的扩散算法，理论上速度将提升N倍。

其他特性

简洁，扩散算法真的只有那么简单，区区几行码就可以达到那么不可思议的效果；灵活，如可以定制网络、定制扩散式、定制函数等。

扩散算法有着好的扩散率，因此能够很好的进行数据加密。而且加密过程非常简单，天生的并行计算支持能够极大提升加密速度。

可以将密匙作为分组一同建立路径，或者将密匙作为扩散运算的参数一同参与运算。使用定制的函数并保密，可让攻击者不知所措。使用定制的网络并保密，将会使攻击者感到异常头疼。即便攻击者知道网络建立规则，扩散式建立方式以及所使用的函数，那么也只能束手无策，攻击方法就是穷举攻击。然而对于支持任意长度密匙的扩散加密，穷其所有，也只能望洋兴叹。当然密匙也不能太短了!

扩散算法其良好的扩展性，可有如下加密模式：

对称分组加密：使用扩散算法进行加密，对每一组明文的加密都使用的相同的密匙（可以在每一阶都使用不同的密匙）。

对称流加密：仅使用扩散算法生成子密匙流（参见生成随机数），再使用所生成的密匙流和明文进行异或运算（xor）即可得到密文。使用可靠的扩散运算（函数）再以消除线性，将使密匙重复变得遥遥无期。

对称分组流加密：使用扩散算法以密匙为基础生成子密匙流，再使用扩散算法对明文进行分组加密。此模式可以满足对每一组明文的加密都使用不同的密匙。

半非对称加密：应用扩散算法，可提高非对称的加密效率。用非对称加密数据时，不需要将整个明文组块合成一个大整数进行加密，只需对明文中的各个元素（元素组）分别加密即可（密匙不同）。

此模式共分三次加密。设有明文M，长度为n；应用非对称分别对M中的各个元素（M1,M2,M3…Mn）进行加密后得到T1；应用扩散算法对T1进行加密后得到T2；最后再次应用非对称分别对T2中的各个元素加密得到密文C（密匙与第一次加密相同）。

全非对称加密：设函数F与函数Fˊ为非对称互斥函数，通过F(Fˊ)加密后的数据只能通过F’(F)进行解密。应用扩散算法，在进行扩散运算的过程中使用F(Fˊ)进行加密，用Fˊ(F)进行解密即可。

扩散算法可用于生成任意长度的消息摘要。其100%的扩散率可计算出可靠的消息摘要数据。对于其定制的扩散算法而言，在不泄露细节的情况下，碰撞攻击几乎变得毫无意义。

不过计算消息摘要时，扩散运算的运算质量直接影响的到消息摘要的计算质量，可不能马虎。

MAC即消息认证码（带密匙的消息摘要）。这也不用说了，计算消息摘要时加入密码就好了。

用扩散运算生成伪随机数，随机性好，生成速度快，周期长。使用可靠的函数是生成随机数质量的前提保障，用多种网络交替使用更使随机效果如虎添翼。可别忘了消除线性哦！

本示例的网络建立规则参照图1。处理步骤：

S1. 设N(n)为分组长度。计算对数 ，并对G进行向上取整，计算长度 ，计算处理所需扩散阶段的数量round = G + E，E＞=1，本例E = 1。

S2. 取2组长度为n的分组X和Y，i、j分别是X、Y的元素索引。

S3. 设整数r是扩散阶段索引号。第一阶r = 0。由X向Y的扩散命名为EY，记作EY=X[i]+Y[j]→Y[j]；由Y向X的扩散命名为EX，记作EX= Y[j]+X[i]→X[i]。组建扩散式分别为：

X[0]+Y[0]→Y[0], Y[0]+X[0]→X[0];

X[1]+Y[1]→Y[1], Y[1]+X[1]→X[1];

X[2]+Y[2]→Y[2], Y[2]+X[2]→X[2];

…

X[n-1]+Y[n-1]→Y[n-1], Y[n-1]+X[n-1]→X[n-1].

S4. 分别取出EY中的原体，使用函数FY计算结果后，更新EY中的受体，即Y[j] = FY(X[i], Y[j])。

S5. 分别取出EX中的原体，使用函数FX计算结果后，更新EX中的受体，即X[i] = FX(Y[j], X[i])。

S6. 第二阶，r = 1。组建扩散式分别为：

X[0]+Y[P/2+0]→Y[P/2+0], Y[P/2+0]+X[0]→X[0];

X[1]+Y[P/2+1]→Y[P/2+1], Y[P/2+1]+X[1]→X[1];

X[2]+Y[P/2+2]→Y[P/2+2], Y[P/2+2]+X[2]→X[2];

…

X[n-1] +Y[P/2+n-1]→Y[P/2+n-1], Y[P/2+n-1] X[n-1]→X[n-1];

然后执行步骤S4、S5。

S7. 第三阶，r = 2。组建扩散式分别为：

X[0]+Y[P/4+0]→Y[P/4+0], Y[P/4+0]+X[0]→X[0];

X[1]+Y[P/4+1]→Y[P/4+1], Y[P/4+1]+X[1]→X[1];

X[2]+Y[P/4+2]→Y[P/4+2], Y[P/4+2]+X[2]→X[2];

…

X[n-1] +Y[P/4+n-1]→Y[P/4+n-1], Y[P/4+n-1]+X[n-1]→X[n-1];

然后执行步骤S4、S5。

S8. 第r阶（仅当此示例中不是第一阶时）。组建扩散式分别为：

X[0]+Y[P/2r+0]→Y[P/2r+0], Y[P/2r+0]+X[0]→X[0];

X[1]+Y[P/2r+1]→Y[P/2r+1], Y[P/2r+1]+X[1]→X[1];

X[2]+Y[P/2r+2]→Y[P/2r+2], Y[P/2r+2]+X[2]→X[2];

…

X[n-1] +Y[P/2r+n-1]→Y[P/2r+n-1], Y[P/2r+n-1]+X[n-1]→X[n-1];

然后执行步骤S4、S5。

本示例的网络建立规则参见图2，处理步骤：

S1. 设有分组X、Y，分组长度为N，本例N=8。

S2. 计算处理所需扩散阶段的数量round，round可根据网络建立规则和N进行调整，本例round 可取4。由X向Y的扩散记作EY=X[i] +Y[j]→Y[j]，由Y向X的扩散记作EX=Y[j]+X[i]→X[i]，i、j为元素索引。

S3. 第1阶，组建扩散式分别为：

X[0]+Y[3]→Y[3], Y[3]+X[0]→X[0];

X[1]+Y[0]→Y[0], Y[0]+X[1]→X[1];

X[2]+Y[7]→Y[7], Y[7]+X[2]→X[2];

…

X[7]+Y[5]→Y[5], Y[5]+X[7]→X[7].

S4. 分别取出EY中的原体，分别使用函数FY计算结果后，更新EY中受体的各元素，即:Y[j] = FY(X[i], Y[j])。

S5. 分别取出EX中的原体，分别使用函数FX计算结果后，更新EX中受体的各元素，即X[i] = FX(X[i], Y[j]), 。

S6. 第2阶，组建扩散式分别为：

X[0]+Y[5]→Y[5], Y[5]+X[0]→X[0];

X[1]+Y[3]→Y[3], Y[3]+X[1]→X[1];

X[2]+Y[4]→Y[4], Y[4]+X[2]→X[2];

…

X[7]+Y[1]→Y[1], Y[1]+X[7]→X[7];

然后执行S4、S5。

S7. 第3阶，组建扩散式分别为：

X[0]+Y[2]→Y[2], Y[2]+X[0]→X[0];

X[1]+Y[4]→Y[4], Y[4]+X[1]→X[1];

X[2]+Y[0]→Y[0], Y[0]+X[2]→X[2]

…

X[7]+Y[3]→Y[3], Y[3]+X[7]→X[7];

然后执行S4、S5。

S6. 第4阶，组建扩散式分别为：

X[0]+Y[0]→Y[0], Y[0]+X[0]→X[0];

X[1]+Y[1]→Y[1], Y[1]+X[1]→X[1];

X[2]+Y[2]→Y[2], Y[2]+X[2]→X[2];

…

X[7]+Y[7]→Y[7], Y[7]+X[7]→X[7];

然后执行S4、S5。