feistel

什么是feistal cipher

Feistel加密中最后一步交换左右分组是为了提高安全性。

Feistel结构就是交替使地使用替换和置换。替换和置换地定义如下：

替换：每个明文元素或元素组被唯一地替换为相应地密文元素或元素组。

置换：明文元素地序列被替换为该序列地一个置换，序列里没有添加新元素，但是元素出现的顺序变了。

分组密码，是将整个长明文分成若干组，以组为单位进行加密。分组越长意味着安全性越高，但是会降低加密解密的速度。为了简化加密过程，我们设定每个分组长度都相等，不足则补上空格。

将明文分成若干等长分组，对于每个分组进行以下加密：

取分组后KSIZE位字符生成子密钥，将子密钥与前 (PSIZE - KSIZE)为进行异或加密，再将子密钥拼接到异或得到的密文后，得到与原分组长度相等的密文C1，再对问C1进行栅栏密码的加密，最终得到该分组加密的密文。  。

分组密码中,Feistel结构和SPN结构的区别

feistal cipher是一种密码Feistel密码用于构造的对称结构。分组密码，以德国-出生物理学家和cryptographer霍斯特·Feistel在为的工作的同时，谁做了开拓性的研究ibm(美国)；它也通常被称为Feistel网络.密码使用该方案，包括数据加密标准(Des)。在结构具有以下优点：加密和解密操作非常相似，甚至在某些情况下是相同的，只需要反转关键进度表因此，实现这种密码所需的代码或线路的大小几乎减半。

一种网络是一种迭代密码，其内部函数称为圆函数。

子密钥压缩置换表怎么用

Feistel结构只对一部分进行变换，SPN结构是都进行变换。

不属于公开密钥加密算法

子密钥于Feistel结构中独立存在，在本题目的主要作用是作为计算hash值函数的一个参数。

1.1 DES的子密钥设计基本介绍。

作为一种分组密码，从DES的整个体制可以看出，DES分为两个部分，DES加解密部分和子密钥生成部分，密钥部分独立运行，产生加解密所需的子密钥然后作用于DES。

DES的最初64位密钥通过置换选择PC-1得到有效的56位密钥。这56位密钥分为2个28位数据C0和D0。每轮迭代中，Ci-1和Di-1分别循环左移1位或2位，移位后的值作为下一轮的输入，同时，也作为置换选择PC-2的输入，通过置换选择PC-2产生一个48位的输出，即为一个子密钥。



图1 DES的子密钥生成示意图。

其中，每一轮移位的密钥位数不同，若轮数为1、2、9、16，只移1位，否则移2位。置换PC-2是一个压缩置换，它将56位密钥数据压缩成48位的子密钥。压缩方法是将C中的第9、18、22、25位和D中的7、10、15、26位删去，同时，将其余位次序调换，从而得到48位子密钥。

由于使用了密钥移位和压缩置换PC-2，使得每一轮使用不同的密钥位子集，且每个密钥位出现的次数大致相同。在16个子密钥中，每一密钥位大约被使用到其中14个子密钥，这种特点增加了DES的破译难度。

通过对 DES算法的子密钥部分的分析，同时考虑到 DES易受穷举搜索等方法攻击的缺陷，我们关于子密钥部分的结构设计提出基于分组与哈希函数的改进方案。该改进方案首先将明文与密钥进行异或，然后根据分组结果或者哈希表查找比较次数，结合仿射变换决定子密钥的使用顺序，最后利用 RSA 加密子密钥的使用顺序。该改进方案因为输入明文的不同而引起子密钥的使用顺序不同，使得每次破解都需要 161次穷举，从而提高穷举搜索与选择明文攻击的难度，提高 DES算法的安全性。

1.2 改进方案介绍及示例

（1）改进方案1

① 输入64位明文M，并将64位明文与64位密钥K进行异或，得到64位数据C。

② 将得到的64位二进制数据C，每4位进行分组，得到16个大小在0-15之间的数据Ci（i为0-15）。

③ 令原子密钥的顺序为：K0K1K2…K14K15，采用下面的算法对子密钥的顺序进行交换，若Ci（i为0-15）的值为j，选定参数B，计算Bi+j的值（当B为1时，由仿射变换退化到移位操作），为了避免Bi+j的值大于15，再采用模16求余以确保Bi+j的值在0-15之间，将Ki的值与K（Bi+j）%16进行交换。

④ 按照改进后的子密钥顺序进行DES加密。

下面示例说明子密钥的变换过程。

① 选取明文M=00010001 00100011 10010011 10110001 11010011 00010111 10101010 01010101。选取密钥K=10011001 001100110 00010001 10010001 01011111 01100011 10000111 10011101。将明文M与密钥K进行异或得到数据C=10001000 01000101 10000010 00100000 10001100 01110100 00101101 11001000。

② 将二进制数据C每4位进行分组，得到16个十进制数值为{8，8，4，5，8，2，2，0，8，12，7，4，2，13，12，8}。

③ 令B=1，根据上面序列，C0=8所以K0与K8交换，经过一次交换子密钥的顺序为K8K1K2K3K4K5K6K7K0K9K10K11K12K13K14K15；同理C1=8所以K1与K9交换，经过二次交换子密钥的顺序为：K8K9K2K3K4K5K6K7K0K1K10K11K12K13K14K15；以此类推，经过16次交换后，子密钥的顺序为：K3K6K0K9K10K15K2K5K8K1K13K7K4K14K12K11。

④ 按此改进后的子密钥顺序K3K6K0K9K10K15K2K5K8K1K13K7K4K14K12K11进行DES加密。

（2）改进方案2

① 输入64位明文M，并将64位明文与64位密钥K进行异或，得到64位数据C。

② 将得到的64位二进制数据C，每4位进行分组，得到16个大小在0-15之间的数据Ci（i为0-15）。

③ 利用哈希函数和线性探测处理冲突的方法将数据Ci放入哈希表中，根据按顺序放数据C0C1C2…C14C15时所进行的地址计算次数（或者说是查找数据C0C1C2…C14C15时所进行的关键数比较次数），得到16个十进制数据{A0，A1，A2，…，A14，A15}。

④ 令原子密钥的顺序为：K0K1K2…K14K15，采用下面的算法对子密钥的顺序进行交换，若Ai（i为0-15）的值为j，选定参数B，计算Bi+j的值（当B为1时，由仿射变换退化到移位操作），为了避免Bi+j的值大于15，再采用模16求余以确保Bi+j的值在0-15之间，将Ki的值与K（Bi+j）%16进行交换。

⑤ 按照改进后的子密钥顺序进行DES加密。

下面示例说明子密钥的变换过程。

① 选取明文M=00010001 00100011 10010011 10110001 11010011 00010111 10101010 01010101。选取密钥K=10011001 001100110 00010001 10010001 01011111 01100011 10000111 10011101。将明文M与密钥K进行异或得到数据C=10001000 01000101 10000010 00100000 10001100 01110100 00101101 11001000。

② 将二进制数据C每4位进行分组，得到16个十进制数值为{8，8，4，5，8，2，2，0，8，12，7，4，2，13，12，8}。

③ 采用除留余数法构造哈希函数，待散列数据的长度为16，令哈希表长度m，p均为17，则哈希函数为：H（G）=Gi%17（i=0，1，2，…，15），当发生冲突时采用线性探测再散列法处理冲突，得到如表1所示的哈希表，按顺序查找16个十进制数值所进行的比较次数为A={10，1，2，1，1，3，1，1，2，3，4，1，12，2，4，1}，其中，地址比较次数的范围为1-16。

④ 令B=1，根据上面序列，A0=10所以K0与K10交换，经过一次交换子密钥的顺序为K10K1K2K3K4K5K6K7K8K9K0K11K12K13K14K15；同理A1=1所以K1与K2交换，经过二次交换子密钥的顺序为：K10K2K1K3K4K5K6K7K8K9K0K11K12K13K14K15；以此类推，经过16次交换后，子密钥的顺序为：K12K3K1K7K14K4K2K6K5K11K15K8K9K0K10K13。

⑤ 按此改进后的子密钥顺序K12K3K1K7K14K4K2K6K5K11K15K8K9K0K10K13进行DES加密。



下列算法中，不属于公开密钥加密算法的是 DES 。

解析：常用的加密算法依据所使用的秘钥数分为单钥和双钥加密体制，也称私钥和公钥加密算法。ECC、DSA 和 RSA 都属于公开密钥加密算法，DES 是典型的私钥加密体制。

DES 对称加密的原理：

DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位，产生最大 64 位的分组大小。这是一个迭代的分组密码，使用称为 Feistel 的技术，其中将加密的文本块分成两半。

使用子密钥对其中一半应用循环功能，然后将输出与另一半进行“异或”运算；接着交换这两半，这一过程会继续下去，但最后一个循环不交换。DES 使用 16 个循环，使用异或，置换，代换，移位操作四种基本运算。

以上内容参考：百度百科-des对称加密。

原文地址：http://www.qianchusai.com/feistel.html