Feistel密码结构、原理及java代码实现

terry 2年前 (2023-09-27) 阅读数 63 #数据结构与算法

在密码学研究中，Feistel密码结构是分组密码中使用的对称结构。了解Feistel密码的结构对于理解DES算法的原理有很大帮助。Feistel建议使用乘积数字的概念来近似理想的分组密码。乘积密码是指按顺序使用两个或多个基本数字，从而得到的密码比任何单个数字都更强。Feistel密码交替使用替换和排列来执行加密和解密。替换和排列的定义如下：替换：每个单个文本元素或元素组唯一地被相应的密文元素或元素组替换。排列：纯文本元素的序列被替换为该序列的排列。也就是说，序列中没有元素被添加、删除或替换，但元素在序列中出现的顺序发生了变化。

原理

Feistel的加解密流程如下图所示：

上图是Feistel的密码结构。加密算法的输入是一个2w位的明文块和一个密钥K。明文数据包被分为两个相等的部分：L0和R0。经过n轮迭代后，两半数据组合成密文组。第 i 次迭代的输入 Li-1 和 Ri-1 来自上一次迭代的输出；输入子密钥Ki是从整个密钥K推导出来的。一般来说，Ki与K不同，并且彼此不同。尽管可以使用任意数量的轮次，但上图中使用了 16 轮。每次迭代都有相同的结构。替换适用于数据的左半部分。它是通过使用轮函数F作用于右半部分数据，然后将其与左半部分数据进行异或来完成的。每次迭代的轮函数相同，但输入子密钥 Ki 不同。换句话说，F 是 w 位长的右半分组和 y 位长的子密钥的函数，并输出 w 位值：F(REi,K i+ 1）。交换完成后，将交换数据的左右半部分进行交换，完成交换。

影响因素

Feistel结构的具体实现取决于以下参数和特性：

组长度：数据包长度越长，安全性越高，但会降低加解密速度。安全性的提高来自于更好的分散性。传统上，64 位分组长度更为合理，常用于分组密码设计。

密钥长度：密钥越长也意味着安全性越高，但会降低加解密的速度。这种安全性的提高来自于更好地抵抗耗尽攻击和更好的混淆。现在普遍认为64位密钥是不够的。常用的密钥长度为128位。

迭代轮数：Feistel密码的本质是单轮无法提供足够的安全性，但多轮加密可以实现较高的安全性。迭代轮数的典型值为 16。

子密钥生成算法：子密钥生成越复杂，密码分析就越困难。

轮函数F：同样，轮函数越复杂，抵抗攻击的能力越强。

代码实现

只要理论清楚，代码实现并不难。具体代码如下：

package com.general.encryanddecode;

import java.util.Arrays;

/**
 *
 *@author generalandroid
 *
 *Feistel密码算法
 * **/
public class FeistelTest {

    /**加密轮数**/
    private static final int LOOP_NUM=16;
    private String [] keys=new String[LOOP_NUM];
    private String [] pContent;
    private String [] cContent;
    private int origin_length;

    public static void main(String[] args){

        FeistelTest feistelTest=new FeistelTest("Android将军->GeneralAndroid","ABCDE");
        feistelTest.encrypt();
        feistelTest.decrypt();


    }
    public FeistelTest(String content,String key){
        generateKey(key);
        divideGroups(content);

        System.out.println("原始明文："+content+"\n原始密钥："+key);
    }


    public void encrypt(){
        StringBuilder c=new StringBuilder();
        for(int i=0;i<pContent.length;i++){
                cContent[i]=loop(pContent[i],0);
            c.append(cContent[i]);
        }

       System.out.println("密文:\n"+c.toString());
    }
    public void decrypt(){
        StringBuilder p=new StringBuilder();
        for(int i=0;i<cContent.length;i++){
            pContent[i]=loop(cContent[i],1);
            p.append(pContent[i]);
        }
        System.out.println("明文：\n"+p.toString().substring(0,origin_length));
    }
    /**生成子密钥，采用简单移位操作来实现**/
    public void  generateKey(String key){
        while (key.length()<16){
            key=key+key;
        }
        key=key.substring(0,16);
//        System.out.println("after sub key:"+key);
        for(int i=0;i<16;i++){
            key=swapStr(key,i);
            keys[i]=key;
        }
//        System.out.println(Arrays.toString(keys));
    }
    private String swapStr(String key,int i){
        char last=key.charAt(key.length()-1);
        key=last+key.substring(0,key.length()-1);
//        System.out.println("i:"+i+"\t key:"+key);
        return key;
    }

    /**对明文进行分组**/
    public void divideGroups(String content){
        int g_num;
        int m_num;
        int b_num;
        origin_length=content.length();
        g_num=origin_length/8;
        m_num=origin_length%8;
        b_num=8-m_num;
//        System.out.println("g_num:"+g_num+"\t m_num:"+m_num+"\t b_num:"+b_num);
        if(m_num!=0){
            for (int i=0;i<=b_num;i++){
                content=content+b_num;
            }
        }
        g_num=content.length()/8;
        pContent=new String[g_num];
        cContent=new String[g_num];
        for(int i=0;i<g_num;i++){
            pContent[i]=content.substring(8*i,8*(i+1));
        }
//        System.out.println(Arrays.toString(pContent));
    }



    /**轮加密与解密**/
    public String loop(String content,int flag){
        if(flag==0){
            for(int i=0;i<16;i++){
                content=f(i,content,flag);
            }
        }else if(flag==1){
            for(int i=15;i>-1;i--){
                content=f(i,content,flag);
            }
        }
        return content;

    }
    /**f函数**/
    public String f(int time,String content,int flag){
        if(content.length()>8){
            System.out.println("ERROR!!!!!");
        }
        String LE=content.substring(0,4);
        String RE=content.substring(4,8);
        String LE1=null;
        String RE1=null;
        String key=keys[time];
//        System.out.println("LE:"+LE+"\t RE:"+RE+"\t key:"+key);
        char[] tmp=new char[4];
        for(int j=0;j<4;j++){
            tmp[j]=(char)(RE.charAt(j)^key.charAt(4*j)^LE.charAt(j));
        }
//        System.out.println("tmp re:"+Arrays.toString(tmp));
        LE1=RE;
        RE1=new String(tmp);
//        System.out.println("time:"+time+"\t L:"+LE1+RE1+"\t key:"+key);


        if (((flag == 0) && (time == 15)) || ((flag == 1) && (time == 0))) {
           return RE1+LE1;
        }

        return LE1+RE1;
    }


}
/****
 * 运行结果：
 * 
 * 
 原始明文：Android将军->GeneralAndroid
 原始密钥：ABCDE
 密文:
 oAB尴ooc尀冿uehbtDXlGdthoFB@7101
 明文：
 Android将军->GeneralAndroid

 * 
 * *****/
复制代码