置换网

第３３卷

Ｌ３３

第２２期

Ｎｏ ２２

计算机工程

Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ

２００７年ｌ１月

Ｎｏｖｅｍｂｅｒ ２ＯＯ７

・安全技术・ 文章■号。１ ７８—ｏ３ 文■标识码ｌ Ａ 中圈分类号ｌ ＴＰ３０９

一种基于ＢＥＮＥＳ网络的可重构比特置换系统设计

向糖，囊紫彬，徐劲橙

（解放军信息工程大学电子技术学院，郑州４５０００４）

摘要：采用ＡＴＭ交换机中的ＢＥＮＥＳ网络，提出了一种简洁正确的寻径算法，在可重构密码芯片上实现比特置换功能单元，能够完成Ⅳ，

种Ⅳ到Ⅳ的任意比特置换。该方法可以支持新的密码算法，加速分组密码，减少资源占用。

关ｔ讨：比特置换；ＢＥＮＥＳ网络；可重构

Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ Ｓｙｓｔｅｍ ｆｏｒ Ｂｉｔ Ｐｅｒｍｕｔａｔｉｏｎ

Ｂａｓｅｄ ｏｎ ＢＥＮＥＳ Ｎｅｔｗｏｒｋ

ＸＩＡＮＧ Ｎａｎ，ＤＡＩ Ｚｉ－ｂｉｎ，ＸＵ Ｊｉｎ・ｓｏｎｇ

ｒＩｎｓｔｉｔｕｔｅ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ，ＰＬＡ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００４）

［Ａｂｓｔｒａｃｔ］Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ｗａｙ ｏｆｅｆｆｉｃｉｅｎｔｌｙ ｄｏｉｎｇ ａｒｂｉｔｒａｒｙ Ｎ－ｂｉｔ ｐｅｒｍｕｔａｔｉｏｎｓ ｉｎ ｒｅｃｏｎｆｉｇｕｒａｂｌｅ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｃｈｉｐ ｗｉｔｈ ｖｅｒｙ ｅｆｆｉｃｉｅｎｔ

ｈａｒｄｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｔｈｅ ｎｅｗ ｍｅｔｈｏｄ ｉｓ ｂａｓｅｄ ｏｎ ｔｈｅ ＢＥＮＥＳ ｍｕｌｔｉｓｔａｇｅ ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ ｎｅｔｗｏｒｋ ｗｈｉｃｈ ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ＡＴＭ ｓｗｉｔｃｈｅｒ．Ａｎ

ａｃｃｕｒａｔｅ ａｎｄ ｃｏｍｐａｃｔ ｓｏｒｔｉｎｇ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ａｌｓｏ ｄｅｓｃｒｉｂｅｄ．Ｔｈｉｓ ｍｅｔｈｏｄ ｃａｎ ｓｕｐｐｏｒｔ ｎｅｗ ｃｒｙｐｔ ａｌｇｏｒｉｔｈｍ，ｓｐｅｅｄ ｕｐ ｅｘｅｃｕｔｉｏｎ，ａｎｄ ｒｅｄｕｃｅ

ｒｅｓｏｕｒｃｅ ｃｏｎｓｕｍｐｔｉｏｎ．

［Ｋｅｙ ｗｏｒｄｓｌ ｂｉｔ ｐｅｒｍｕｔａｔｉｏｎ；ＢＥＮＥＳ ｎｅｔｗｏｒｋ；ｒｅｃｏｎｆｉｇｕｒａｂｌｅ

１概述

无论是密码学还是计算机体系结构方面，比特置换都是

重要而有意义的。从密码学的角度来说，比特置换提供了字

节操作所无法实现的混乱扩散等功能。置换作为扩散的首要

手段，在密码算法中得到了广泛应用。从计算机体系结构的

角度来说，随着多媒体和信息安全技术的发展，快速比特置

换将成为面向字节的处理器的一个重要发展方向…。

本文主要介绍在可重构密码芯片中设计构造置换单元。

根据重构元素的最大适应性原则，一个ＮｘＮ的置换单元应该

实现Ⅳ输入、Ⅳ输出的所有的选择变换，即ＮｘＮ置换单元的

Ⅳ个输出中的任何一个能够选择Ⅳ个输入中的任何一个。按

照该原则设计的可重构比特置换单元所需要的可控编码的宽

度和它所能实现的选择变换的个数可由下述定理描述：

定理对于Ⅳ比特置换，需要从Ⅳ！的结果空间中挑选

出一个作为结果，因此至少需要ｌｏｇ２（Ⅳ！）比特作为置换操作

指定。可以证明：Ⅳ！＝０（Ｍｖ），ｌｏｇ２（Ⅳ！）＝Ｏ［Ｎｌｏｇ２Ｎ］ 。这

意味着用于指定一个置换的比特数是Ｎｌｏｇ２Ｎ。设一个ＮｘＮ

置换单元能够实现其输入到输出的所有选择变换，即其Ⅳ个

输出中的任何一个能够选择Ⅳ个输入中的任何一个，则该置

换单元需要Ｍｏｇ：Ｎ位可控编码，它能够实现的选择变换的个

数为 ，即Ⅳ个Ⅳ选１，见表１。

表１一些常用分组密码算法涉及的比特置换

一ｌ７８一

由于发现交换网络和密码学中的置换网络功能非常相

似，本文借鉴通信交换网络及其路由算法方面的研究方法和

成果，来进行密码学中比特置换单元的构造，在可重构密码

芯片中实现任意的比特置换操作。

２ ＢＥＮＥＳ网络结构

随着通信技术和计算机技术的迅速发展，特别是ｗｗｗ

和多媒体业务的爆炸式增长、Ｉｎｔｅｒｎｅｔ的数据流量急剧增加，

对交换网络的研究也日益深入，出现了ＢＥＮＥＳ、ＣＬＯＳ、

ＢＵＴＴＥＲＦＬＹ、ＢＡＮＹＡＮ等形式的交换网络”ｊ。许多互联网

络被用于解决众多领域的交换排序问题。这些网络为了适应

不同的应用需求，具有各自不同的性质。由于交换网络和密

码学中的置换网络功能非常相似，笔者借鉴通信交换网络方

面的研究方法和系统架构来实现密码学中的比特置换，期望

找到一种合适密码算法中比特置换的网络。对于ＮｘＮ的任意

比特置换，这种网络的硬件实现要比文献【４】中用Ⅳ个Ⅳ选１

的交叉开关实现节省面积。

根据互联交换网络的阻塞特点，一般将其分为无阻塞型、

广义无阻塞型、可重排无阻塞型 。绝对无阻塞型的互联网

络是最为理想的实现方式，但是它对网络的级联级数以及相

关的硬件设施要求很高，所以在比特置换系统的设计中，没

有采用这种网络而是采用可重排无阻塞的ＢＥＮＥＳ网络。

ＢＥＮＥＳ网是一种可重排网，能实现输入端到输出端的所

有置换，作为非阻塞开关网络在通信领域得到广泛的应用。

这种网络的特点是可以通过具体的寻径路由算法，根据全通

道排序的要求，实时改变各级节点开关的状态（直通或交叉），

作者筒介：向楠（１９８２－－），女，硕士研究生，主研方向：信息安全；

戴紫彬，教授；徐劲松，讲师

收藕日期：２００６—１１－３０ Ｅ・ｍａｉｌ：ｔｈｉｎｃａｔ２００１＠１２６．ｃｏｍ

维普资讯

从而有效避免路径冲突。由于它能实现输入到输出的所有置

换，因此利用它来实现需要能实现输入端到输出端所有置换

的可重构比特置换单元。

ＢＥＮＥＳ网的结构在文献【６】中有详细的描述，这里就不再

赘述。８输入的ＢＥＮＥＳ网结构见图１。这种网络具有以下一

些很好的特性，可以用于解决可重构密码芯片中任意比特置

换的问题。

（１）ＢＥＮＥＳ网络由两个背靠背的ＢＡＮＹＡＮ网络连接而

成。该网络可以通过开关状态的改变实现ＮｘＮ的任意交换。

因此可以利用它来构造能完成任意比特置换的可重构比特置

换单元。应用于比特置换操作时，这种网络的特点就表现为

可以通过寻径算法，产生各个开关的控制信息，实时改变各

级节点开关的状态（直通或交叉），实现Ⅳ！种置换中要求的

任何一种。

（２）ＢＥＮＥＳ网络可以被拆分成不同的级，因此可以逐级利

用和控制这个网络。

（３）规模为Ⅳ的ＢＥＮＥＳ网是由２ｌｏｇ２Ⅳ－１级２ｘ２的开关构

成，开关总数是Ｎｌｏｇ２Ｎ－ＮＩ２。每个开关由两个２选１的数据

选择器构成。与文献【４］中用Ⅳ个Ⅳ选１的数据选择器来实现

的方法相比，能有效地节省面积。

（４）ＢＥＮＥＳ网的每一个２ｘ２开关，２个输入和２个输出定

义为互斥对。这些互斥对可以由一个比特配置。即每一级的

Ｎ／２个开关可以由ＮＩ２个比特来配置，决定其状态（交叉或直

通），进而决定数据在网络中的路径。利用网络寻径算法，给

定一个置换即可得出每个开关的状态。通过改变这些开关的

状态可以实现不同的置换。

（５）ＢＥＮＥＳ网络是一种递归结构。可以用较小的ＢＥＮＥＳ

网构成较大的ＢＥＮＥＳ网。

匪１ ８ｘ８的ＢＥＮＥＳ网络及其开关状态

３ ＢＥＮＥＳ网络的寻径算法

由于ＢＥＮＥＳ网络是一种可重排的网络，如何控制网络

中各个开关的状态（直通或交叉），进而决定各个待置换的比

特如何在网络中选路，而不至于发生阻塞，就需要有一种正

确简洁的寻径算法。

本文借鉴一种光互联网络排序算法，改进之后用于比特

置换网络寻径。这种算法本来是利用二分法构造二分图依次

确定内外各级开关的连接状态，可以在ＢＥＮＥＳ、ＯＭＥＧＡ等

网络中实现ＮｘＮ信号全排列无阻塞的输出和排序 ｊ。将这种

算法中利用二分法构造二分图的步骤加以改进，使原有算法

更简洁和有效，因而更适合编程实现。

算法描述如下：

利用该算法确定每级开关的状态。对于２ｘ２节点开关，

定义同一节点开关中，２输入互斥，２输出互斥，而任意属于

不同开关的输入或输出不互斥；根据实际的输入和输出互斥

对，得到一个二分图，确定两互斥对点集ｘ和ｙ。ｘ中的元

素开关连线接上，ｙ中的元素开关连线接下。这样确定出最

左最右两级开关的状态。根据这２列开关状态把待置换的比

特通过级间连线送往左边第２级和右边第２级。由此得到新

的互斥对，由互斥对确定新的ｘ、ｙ集合，进而确定两列开

关的状态。循环这个过程，直到所有的开关状态都确定完毕。

描述如下：

（１）输入待置换的比特序列１，２，３，…，Ⅳ－１，Ｎ；输出

１（１），Ｉ１（２），１（３），…，１（Ｎ－１），兀（Ｊｖ）。定义兀为置换变换关系。

（２）输入互斥对：Ｏ１＝｛１，２｝，０２＝｛３，４｝，…，Ｏｉｖｌ２＝｛Ｎ－１，Ｎ｝；

（３）输出互斥对：Ｐ产｛兀（１），１（２）｝，Ｐ２＝｛兀（３），兀（４）Ｊ，…，

ＰＮＩ２＝｛兀（Ⅳ－１），兀（１Ｖ３｝；

（４）构造ｘ、ｙ，每组均包含ＮＩ２个元素，满足条件

Ｉ ＸＮＰ Ｉ＝Ｉ ＸＮＯ Ｉ＝１ （１）

Ｉ ＹＮＰＩ ｌ＝Ｉ ＹＮＯｉ Ｉ＝１ （２）

其中，１＜ｉ＜ＮＩ２。

具体操作如下：

任选一个Ｐ ，在 中选择一个元素ａ作为ｘ中的一个元

素，令ａ∈ｏｊ，找出符合条件岣ｏｉ；设ｂ为除去ａ之外的另

一个元素，令ｂ∈Ｐ ，则ｂ不 被选为ｘ的元素，而只能选

择Ｐ 中的另一个元素作为ｘ的元素。依次对每个Ｐ （１＜ｉ＜ＮＩ２）

作筛选，如此循环，可得ｘ。则不在ｘ中的元素就组成了

（５）Ｘ、Ｙ用来确定位置左右对称的两级开关的状态（交叉

或直通）。对于左边的一级２ｘ２开关，ｘ中的元素对应接开关

两输出端中上面的一个输出，ｙ中的元素对应接开关两输出

端中下面的一个输出；对于右边的一级开关，ｘ中的元素对

应接开关两输入端中上面的一个输入，ｙ中的元素对应接开

关两输入端中下面的一个输入。由此左右两列开关状态得到

确定。

（６）根据步骤（５）确定的两列开关，把待置换的比特通过开

关经过级问连线送到中间两级开关的输入和输出。由此得到

新的互斥对。重复步骤（４）和步骤（５）。直到所有开关的状态都

被确定。

８ｘ８置换在ＢＥＮＥＳ网络上的举例见图２。

圈２ ８ｘ８置换在ＢＥＮＥＳ网络上的举倒

用８ｘ８的ＢＥＮＥＳ网络实现８ｘ８的置换。输入信号序列１，

２，３，４，５，６，７，８；输出８，３，１，５，４，２，７，６。

（１）兀（１）：８，ＩＩ（２）＝３，１１（３）＝１，１１（４）＝５，１１（５）＝４，１１（６）＝２，

１（７）＝７，兀（８）＝６；

（２）输入互斥对：

Ｏ１＝（ ，２｝，０２＝｛３，４｝，０３＝｛５，６｝，Ｏ４＝（７，墨｝；

（３）输出互斥对：

Ｐ１＝｛墨，３｝，Ｐ２＝（ ，５｝，Ｐ３＝｛４，２｝，Ｐ４＝｛７，６｝；

（４）构造ｘ、ｙ，每组均包含４个元素，满足条件

Ｉ ＸＮＰ。Ｉ＝Ｉ ＸＮＯ。Ｉ＝１ ｆ３）

维普资讯

ｌ ｙｎ ｌ＝ｆ ＹＮＯｉ ｌ＝ｌ （４）

其中，１＜ｉ＜４。

ｌ－ｆ ，４，鱼，墨｝，ｙ＝ｆ２，３，５，７｝；

（５）得到网络中最左和最右两级开关状态；

（６）得到新的互斥对；重复步骤（４）和步骤（５），得到中问两

级开关状态；最后得到最中问一级开关状态。

该算法用ＶＣ实现，用来提取用于进行比特置换的

ＢＥＮＥＳ网各个开关的控制信息。结果为２ｌｏｇ２Ｍ１列，Ｎ／２行

的矩阵，０表示对应位置的开关状态为直通，１表示对应位置

开关状态为交叉，见表２。

表２控■信息矩阵

０ ０ ０ １ ０

ｌ ０ ’ １ １ ０

１ ０ １ １ Ｏ

１ ０ ０ ０ １

４ 网络的硬件实现和性能分析

本文基于Ａｌｔｅｒａ的ＦＰＧＡ器件实现了１２８ｘ１２８比特置换

电路。电路由１３￣６４的开关矩阵组成，每个开关由两个数据

选择器构成，由控制信息ｃｏｎ控制其数据的选通，每个开关

对应１ｂｉｔ控制信息，整个置换电路共８３２ｂｉｔ控制信息。当其

为１时，数据交叉通过开关，当其为０时，数据直接通过开

关。如图３所示，１２８ｂｉｔ待置换的数据Ｄａｔａｉｎ［０…１２７］在

ｃｏｎ］０…８３１】的控制下，经过置换电路运算后得到１２８ｂｉｔ置换

结果Ｄａｔａｏｕｔ［０…１２７】。

Ｃｏｎ［Ｏ…６３】 Ｃｏｎ［６４…１２７】 Ｃｏｎ［７０８．７６７ＪＣｏｎ［７６８…８３１】

图３ １２８ｘ１２８的置换单元电路绪构

Ｄａｔａｏｕｔ［０】

Ｄａｔａｏｕｔ［１】

Ｄａｔａｏｕｔ［２】

Ｄａｔａｏｕｔ［３】

Ｄａｔａｏｕｔ［１２６】

Ｄａｔａｏｕｔ［１２７】

下面将本文中ＪＶ比特任意置换的实现方法和文献【４】中

的实现方法进行比较。对于ＮｘＮ的置换，本文以２１ｏｇ２Ｎ－Ｉ

级ＢＥＮＥＳ网络来实现，而文献【４】用ＪＶ个ＪＶ选１的数据选择

器来实现。以１２８ｘ１２８的置换为例，本文需要１３级２ｘ２的

开关，文献【４】中需要１２８个１２８选１的数据选择器，见表３。

表３ １２８ｘ１２８的置换单元硬件性簟参数

一个ＪＶ选１的多路选择器的功能可以由ｌｏｇ２Ｎ级共Ｎ－１

个２选１的选择器实现。那么一个１２８选１的多路选择器就

相当于７级１２７个２选１数据选择器。而１２８个１２８选１的

数据选择器就相当于１２８ｘ１２７＝１６２５６个２选１数据选择器。

这样的电路结构，延迟和资源占用都是相当大的。而本文提

出的置换单元的电路要相对简单得多。每个开关相当于两个

２选１的数据选择器，一共是１３开关，２ｘ６４ｘｌ３＝１ ６６４个

２选１的选择器，见表４。

表４以不同方法实现１２８ｘ１２８置换赉豫占用情况比较

５结束语 ．

本文基于ＡＴＭ交换机中的ＢＥＮＥＳ网，提出了一种简洁

正确的寻径算法，构造出能够实现任意置换的可重构比特置

换单元。该单元不仅能实现现有分组密码算法中的所有置换

表，而且任意置换还能支持新的密码算法。完成同种功能，

资源占用仅是文献【４】中所用方法的１０．２％。不仅能有效完成

任意置换，而且大幅度节省了面积。

参考文献

１ Ｓｈｉ Ｚ Ｊ．Ｂｉｔ Ｐｅｒｍｕｔａｔｉｏｎ Ｉｎｓｔｒｕｃｔｉｏｎｇ：Ａｒｃｈｉｔｅｃｔｕｒｅ，Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，

ａｎｄ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｐｒｏｐｅｒｔｉｅｓ］Ｄ］．Ｕ．Ｓ．Ａ：Ｐｒｉｎｃｅｔｏｎ Ｕｎｉｖｅｒｓｉｔｙ．

２００４—０６．

２ Ａｂｒａｍｏｗｉｔｚ Ｍ，Ｓｔｅｇｕｎ Ｉ Ａ．Ｈａｎｄｂｏｏｋ ｏｆ Ｍａｔｈｅｍａｔｉｃａ］Ｆｕｎｃｔｉｏｎｓ］Ｚ］．

Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳ：Ｄｅｐｔ．ｏｆ Ｃｏｍｍｅｒｃｅ ａｎｄ Ｎａｔｉｏｎａｌ Ｂｕｒｅａｕ ｏｆ

Ｓｔａｎｄａｒｄｓ，１９７０．

３ Ｃｏ￣ｅｎ Ｔ Ｈ，Ｌｅｉｓｅｒｓｏｎ Ｃ Ｅ，Ｒｉｖｅｓｔ Ｒ Ｌ，Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ

［Ｍ］．Ｃａｍｂｒｉｄｇｅ，Ｍａｓｓ：ＭＩＴ Ｐｒｅｓｓ，１９９４．

４曲英杰．可重组密码逻辑的设计原理［Ｄ］．北京：北京科技大学，

２ＯＨＤ３．

５金惠文．现代交换原理［Ｍ］．北京：电子工业出版社，２０００—０３．

６ Ｚｈｏｎｇ Ｊｉｌｉｎｇ．Ｕｐｐｅｒ Ｂｏｕｎｄ Ａｎａｌｙｓｉｓ ａｎｄ Ｒｏｕｔｉｎｇ ｉｎ Ｏｐｔｉｃａｌ ＢＥＮＥＳ

Ｎｅｔｗｏｒｋｓ］Ｄ］．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｇｅｏｒｇｉａ Ｓｔａｔｅ

Ｕｎｉｖｅｒｓｉｔｙ，２００５—１ １—１０．

７杨俊波．光互联网络中排序算法研究［Ｊ】＿光电工程，２００４，３１（增

刊）．

（上接第１５０页）

参考文献

１ Ｒｏｓｅｎｂｅｒｇ Ｊ．ＳＩＰ：Ｓｅｓｓｉｏｎ Ｉｎｉｔｉａｔｉｏｎ Ｐｒｏｔｏｃｏ１］Ｓ］．ＲＦＣ ３２６１，２００２．

２雷为民，张 伟．ＳＩＰＮＡＴ问题阐述及其解决方案［Ｊｊ．通信世界，

２００５，６（４）：３８—３９．

３ Ｋｏｓｋｉ Ｐ，Ｙｌｉｎｅｎ Ｊ，Ｌｏｕｌａ Ｐ．Ｔｈｅ ＳＩＰ－ｂａｓｅｄ Ｓｙｓｔｅｍ Ｕｓｅｄ ｉｎ

Ｃｏｎｎｅｃｔｉｏｎ ｗｉｔｈ ａ Ｆｉｒｅｗａｌｌ［Ｃ］／／Ｐｒｏｃ．ｏｆ ＡＩＣＴ—ＩＣＩＷ’０６．２００６．

４ Ａｒａｎｇｏ Ｍ．Ｍｅｄｉａ Ｇａｔｅｗａｙ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ（ＭＧＣＰ）［Ｓ］．ＲＦＣ ２７０５，

ｌ９９９．

５ Ｒｏｓｅｎｂｅｒｇ Ｊ．Ａｎ Ｅｘｔｅｎｓｉｏｎ ｔｏ ｔｈｅ Ｓｅｓｓｉｏｎ Ｉｎｉｔｉａｔｉｏｎ Ｐｒｏｔｏｃｏｌ（ＳＩＰ）ｆｏｒ

Ｓｙｍｍｅｔｒｉｃ Ｒｅｓｐｏｎｓｅ Ｒｏｕｔｉｎｇ］Ｓ］．ＲＦＣ ３５８１，２００３．

６张波，胡瑞敏，边学工．一种实现ＳＩＰ穿越ＮＡＴ的新方案［Ｊ】＿计

算机工程，２００５，３１（２）：１１９—１２１．

维普资讯