精华内容
下载资源
问答
  • S盒的C语言加解密实现,环境VC++6.0,内含注释解析
  • AES128加密-S盒和逆S盒构造推导及代码实现

    万次阅读 多人点赞 2018-07-26 15:53:48
    AES128加密-S盒和逆S盒构造推导及代码实现 1.1 S盒产生概述 文档引用了《密码编码学与网络安全–原理和实践》里边的推导过程,如有不妥,请与我联系修改。 文档《FIPS 197》高级加密标准AES,里边有个S盒构造,...

    AES128加密-S盒和逆S盒构造推导及代码实现
    1.1 S盒产生概述
    文档引用了《密码编码学与网络安全–原理和实践》里边的推导过程,如有不妥,请与我联系修改。
    文档《FIPS 197》高级加密标准AES,里边有个S盒构造,涉及到了数论和有限域的一些概念,一脸懵逼,所以贱贱的研究了下,花了好久时间。
    在网上找的S盒构造的详细步骤总是缺了点什么,要么步骤不详细,要么只贴了程序,难以搞清楚由几个基本概念一步一步推导出最终的S盒。最后,还是《密码编码学与网络安全–原理和实践》这本书讲得比较详细。教材果然还是经过精雕细琢过的,符合大部分人的认知过程。
    这篇文章其一是记录下来这个学习步骤,其二是希望我的这篇能够更详细些。
    先贴出来《FIPS 197》中对S盒构造的描述步骤:
    这里写图片描述
    就这两条。实际上是三个步骤,《密码编码学与网络安全–原理和实践》教材里会讲得更详细些。
    这里写图片描述
    以下都按照《密码编码学与网络安全–原理和实践》教材里边的三个步骤进行推导。步骤1、3都比较浅显,即使没有数论和有限域概念,一样可以编程写出来。
    1.2 产生S盒初始数组
    根据行标号和列标号组合成16X16的二维数组,行标号作为高4bit,列标号作为低4bit;生成代码如下:

         for(i=0;i<0x10;i++)
         {
             for(j=0;j<0x10;j++)
             {
                 s_box_ary[i][j] = ((i<<4)&0xF0) + (j&(0xF));
             }
         }

    代码产生的数组:

         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
      0  0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
      1 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
      2 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f
      3 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f
      4 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f
      5 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f
      6 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f
      7 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f
      8 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f
      9 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f
      a a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af
      b b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
      c c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf
      d d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df
      e e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef
      f f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff

    1.3 求解字节的逆
    本文重点叙述步骤2的推导。
    这里边有三个概念:有限域、GF(2^8)、逆。
    有限域:我的理解是,有一些元素构成了一个集合,集合中的一个或多个元素,进行某种运算,所得的结果仍然是集合中的元素。 元素,可以是具体的数字,也可以是字母,或是表达式,等等;某种运算,可以是加减乘除,或者逻辑运算,或者求余,或者是这几种运算的组合,等等。 这个定义当然很不严格,但是我觉得对于理解这个S盒推导够用了。
    GF(2^8):GF()是代表一个有限域,2^8=256,是指这个有限域内的元素的个数,即256个。
    举个是有限域的集合的例子吧:
    GF(7)={0,1,2,3,4,5,6},它是关于任意两个元素的相加/乘积模7运算的有限域。特点是任意两个元素相加/乘积,对7取余数,这个余数仍然在GF(7)内。
    截取《密码编码学与网络安全–原理和实践》中的例子:
    这里写图片描述
    此外,这个GF(7)的7叫做阶,特点是阶与域内的元素都互素(互质)。
    在计算机中,一个字节是8位,0~255刚好是一个字节所能代表的所有数字,但是呢,GF(256),256对于0~255内的元素并不是每个都互素(互质),当以251为模时,251~255又不能用,造成浪费,所以不能直接使用上边的计算形式。但是我们还得必须用0~255这256个整数作为一个集合,通过某种运算构成有限域,所有只能把研究重点放在“某种运算”上。可能是为了区分GF(256),所以用GF(2^8)。
    逆:乘法逆元。定义:GF(p), (a)、(b)、(a-1)都在GF(p)内,其中(a)、(a-1)互为乘法逆元,则有:[(a) X (a-1)] mod p = 1;
    第二个步骤,就是 在步骤一得到的数组基础上,对每个元素 在 GF(2^8)有限域上求解出乘法逆元,在原位置替换该元素。
    如何求解有限域上的逆元?《密码编码学与网络安全–原理和实践》中从欧几里得算法开始做知识铺垫,到扩展欧几里得算法。我们可以得出求乘法逆元的一个程序上可实现的方法。
    d=gcd(a,b),d是a和b的最大公约数,或者叫最大公因子。求解步骤:
    1、定义变量:r0, r1, r2
    2、赋初值r0=a;r1=b;
    3、求解r0、r1的余数:r3=r0 Mod r1;
    4、更新变量:r0=r1;r1=r2;
    5、从3开始重复,一直到求解的余数r1是0结束。
    6、r0就是要求解的最大公约数。

    long gcd(long a, long b)
    {
        long tmp;
        while(b)
        {
            tmp=a;
            a=b;
            b=tmp%b;
        }
        return a;
    }

    欧几里得算法的关键是gcd(a,b)=gcd(b,(a mod b));为什么能成立?
    可以证明:
    当a>b,就有,a=q1 * b + r1,r1 = a - q1 * b;
    假设 d=gcd(a,b),那么d分别是a和b的最大公因子,记作:d|a,d|b,所以:
    d|(a-q1 * b)=d|r1
    所以有d=gcd(b,r1)=gcd(b, (a mod b));
    《密码编码学与网络安全–原理和实践》里边讲解会更详细:
    这里写图片描述
    扩展欧几里得算法的计算步骤同欧几里得算法的步骤相似,由一个公式迭代计算,一直到某个条件成立,结束迭代,返回结果。
    扩展欧几里得算法用来求解乘法逆元,为什么?
    上边已经有了公式:[(a) * (a-1)] mod p = 1;
    可以等效变换成:p * x + 1 = (a) * (a-1)
    ========> - p * x + (a) * (a-1) = 1
    与ax+by=1的形式是不是很像?与ax+by=gcd(a,b)=1的形式是不是很像?gcd(a,b)=1,即a、b互素即可。
    可以看出,可以运用欧几里得算法的步骤计算乘法逆元,但是怎么计算呢?这点照搬《密码编码学与网络安全–原理和实践》里边的讲解步骤,我觉得不会比他讲得更好了。
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    总结一下:
    1. 初始条件:(R-1) = a; R0=b; (X-1)=1;X0=0;(Y-1)=0;Y0=1;
    2. 迭代步骤:
    Rn=(Rn-2) Mod (Rn-1);Qn = [(Rn-2) /(Rn-1)] {(Rn-2) /(Rn-1)的商};
    Xn = (Xn-2) - (Xn-2) ;Yn = (Yn-2) - (Yn-2) 。
    3. 终止条件:Rn=1时,计算出来的Yn即是结果。
    如果结果为负数,需要加上模值变为正数。
    代码如下:

    long multiplicativeInverse(long a, long b)
    {
        long r0,r1,r2,q1,x0,x1,x2,y0,y1,y2;
    
        long d = gcd(a,b);
        if((d!=1)&&(d!=-1))
        {
            printf("ab不互质\r\n");
            return -1;    
        }
    
        r0=a;
        r1=b;
    
        x0=1;
        y0=0;
    
        x1=0;
        y1=1;
    
        if((b==1)||(b==-1))
        {
            y2=y1;
        }
    
        while((r1!=1)&&(r1!=-1))
        {
            q1=r0/r1;
    
            r2=r0%r1;
    
            x2=x0-q1*x1;
            y2=y0-q1*y1;
    
            r0=r1;
            r1=r2;
    
            x0=x1;
            x1=x2;
    
            y0=y1;
            y1=y2;
        }
    
        if(y2 < 0)
        {
            y2=a+y2;
        }
    
        return y2;
    }

    回归到GF(2^8)有限域,需要找到“某种运算”,使GF(2^8)有限域成立。这种运算是多项式除法运算。
    多项式如下形式:
    这里写图片描述
    我们可以把GF(2^8)有限域内的每一个元素,按照下列方式写成多项式的形式:设 字节a ∈ GF(2^8),写成二进制的形式a=b7b6b5b4b3b2b1b0,用bn代表a的每一位,其中n是二进制数中的位置;那么,bn当作系数,n作为变量x的指数;可以把一个字节写成:这里写图片描述 这种形式。
    举例:
    0x9A=(b)10011010,写成多项式形式:x^7+x^4+x^3+x。
    多项式除法运算,计算规则:
    1、遵循代数基本规则中的普通多项式运算规则;
    2、系数运算遵循以2为模的加法和乘法运算;(原话是:系数运算以p为模,即遵循有限域Zp上的运算规则);
    3、如果乘法运算的结果是次数大于7(原文:n-1)的多项式,那么必须将其除以某个次数为8(原文:n)的即约多项式m(x)并取余式,对于多项式f(x),这个余数可表示为:即
    r(x) = f(x) mod m(x)。
    高级加密标准AES使用有限域GF(2^8)上的运算,其中即约多项式
    m(x)=x^8 + x^4 + x^3 + x + 1;
    举例:
    m(x)=x^8 + x^4 + x^3 + x + 1;
    f(x) =x^6 + x^4 + x^2 + x + 1;g(x) =x^7 + x + 1;
    f(x) * g(x) = (x^6 + x^4 + x^2 + x + 1) * (x^7 + x + 1)
    = x^13 + x^11 + x^9 + x^8 + x^7
    + x^7 + x^5 + x^3 + x^2 + x
    + x^6 + x^4 + x^2 + x + 1
    = x^13 + x^11 + x^9 + x^8 + x^6+ x^5 + x^4 + x^3 + 1
    r(x) = [f(x) * g(x)] mod m(x) => m(x) * q(x) + r(x) = f(x) * g(x):
    这里写图片描述
    q(x) = x^5 + x^3;r(x) = x^7 + x^6 + 1。
    上文已经讲到:扩展欧几里得算法用来求解乘法逆元。
    (b-1)*b mod a = 1; => ax+by=1=gcd(a, b)
    把a、b用多项式替代,形式如下:
    b-1(x) * b(x) mod m(x) = 1 => m(x)v(x) + b(x)w(x) = 1 = gcd(m(x), b(x))
    直接引用上边求乘法逆元的步骤,用多项式直接替代数值计算:
    重述如下:
    1、把带求解的字节变换成多项式形式b(x);
    2、初始条件:
    (R-1) = m(x); R0=b(x);
    (v-1)(x)=1; v0(x)=0;
    (w-1)(x)=0; w0(x)=1;
    3、迭代步骤:
    Rn(x)=(Rn-2)(x) Mod (Rn-1)(x);
    Qn(x) = [(Rn-2)(x) / (Rn-1)(x)] 即:{(Rn-2) /(Rn-1)的商};
    vn(x) = (vn-2)(x) - Qn(x)*(vn-2)(x) ;
    wn(x) = (wn-2)(x) - Qn(x)*(wn-2) 。
    4、终止条件:
    Rn(x)=1时,计算出来的wn(x)即是结果多项式。
    5、把wn(x)变换回字节。
    上述步骤中,需要专门的多项式乘法、多项式除法、多项式求余运算的实现函数。
    多项式乘法函数:

    //GF(2^8)的多项式乘法
    uint16_t polynomialMutil(uint8_t a, uint8_t b)
    {
        uint16_t tmp[8]={0};
        uint8_t i;
        for(i=0;i<8;i++)
        {
            tmp[i] = (a<<i)*((b>>i)&0x1);
        }
    
        tmp[0] = tmp[0] ^ tmp[1] ^ tmp[2] ^ tmp[3] ^ tmp[4] ^ tmp[5] ^ tmp[6] ^ tmp[7];
    
        return tmp[0];
    }

    多项式除法函数:

    //找到最高位
    uint8_t findHigherBit(uint16_t val)
    {
        int i=0;
        while(val)
        {
            i++;
            val = val>>1;
        }
        return i;
    }
    //GF(2^8)的多项式除法
    uint8_t gf28_div(uint16_t div_ed, uint16_t div, uint16_t *remainder)
    {
        uint16_t r0=0; 
        uint8_t  qn=0;
        int bitCnt=0;
    
        r0=div_ed;
    
        bitCnt = findHigherBit(r0)-findHigherBit(div);
        while(bitCnt>=0)
        {
            qn = qn | (1<<bitCnt);
            r0 = r0 ^ (div<<bitCnt);
            bitCnt = findHigherBit(r0)-findHigherBit(div);
        }
        *remainder = r0;
        return qn;
    }

    多项式的扩展欧几里得算法:

    //GF(2^8)多项式的扩展欧几里得算法
    uint8_t extEuclidPolynomial(uint8_t a, uint16_t m)
    {
        uint16_t r0, r1, r2;
        uint8_t  qn, v0, v1, v2, w0, w1, w2;
    
        r0=m;
        r1=a;
    
        v0=1;
        v1=0;
    
        w0=0;
        w1=1;
    
        while(r1!=1)
        {
            qn=gf28_div(r0, r1, &r2);
    
            v2=v0^polynomialMutil(qn, v1);
            w2=w0^polynomialMutil(qn, w1);
    
            r0=r1;
            r1=r2;
    
            v0=v1;
            v1=v2;
    
            w0=w1;
            w1=w2;
        }
        return w1;
    }

    至此,S盒变换的第二步骤实现完成。
    根据 扩展欧几里得算法,得到的中间状态的S盒如下:

        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
     0  0  1 8d f6 cb 52 7b d1 e8 4f 29 c0 b0 e1 e5 c7
     1 74 b4 aa 4b 99 2b 60 5f 58 3f fd cc ff 40 ee b2
     2 3a 6e 5a f1 55 4d a8 c9 c1  a 98 15 30 44 a2 c2
     3 2c 45 92 6c f3 39 66 42 f2 35 20 6f 77 bb 59 19
     4 1d fe 37 67 2d 31 f5 69 a7 64 ab 13 54 25 e9  9
     5 ed 5c  5 ca 4c 24 87 bf 18 3e 22 f0 51 ec 61 17
     6 16 5e af d3 49 a6 36 43 f4 47 91 df 33 93 21 3b
     7 79 b7 97 85 10 b5 ba 3c b6 70 d0  6 a1 fa 81 82
     8 83 7e 7f 80 96 73 be 56 9b 9e 95 d9 f7  2 b9 a4
     9 de 6a 32 6d d8 8a 84 72 2a 14 9f 88 f9 dc 89 9a
     a fb 7c 2e c3 8f b8 65 48 26 c8 12 4a ce e7 d2 62
     b  c e0 1f ef 11 75 78 71 a5 8e 76 3d bd bc 86 57
     c  b 28 2f a3 da d4 e4  f a9 27 53  4 1b fc ac e6
     d 7a  7 ae 63 c5 db e2 ea 94 8b c4 d5 9d f8 90 6b
     e b1  d d6 eb c6  e cf ad  8 4e d7 e3 5d 50 1e b3
     f 5b 23 38 34 68 46  3 8c dd 9c 7d a0 cd 1a 41 1c

    1.4 S盒字节变换和逆S盒字节变换:

    //S盒字节变换
    uint8_t byteTransformation(uint8_t a, uint8_t x)
    {
        uint8_t tmp[8]={0};
    
        for(uint8_t i=0;i<8;i++)
        {
            tmp[i]= (((a>>i)&0x1)^((a>>((i+4)%8))&0x1)^((a>>((i+5)%8))&0x1)^((a>>((i+6)%8))&0x1)^((a>>((i+7)%8))&0x1)^((x>>i)&0x1)) << i;
        }
        tmp[0] = tmp[0]+tmp[1]+tmp[2]+tmp[3]+tmp[4]+tmp[5]+tmp[6]+tmp[7];
        return tmp[0];
    }
    
    //逆S盒字节变换
    uint8_t invByteTransformation(uint8_t a, uint8_t x)
    {
        uint8_t tmp[8]={0};
    
        for(uint8_t i=0;i<8;i++)
        {
            tmp[i]= (((a>>((i+2)%8))&0x1)^((a>>((i+5)%8))&0x1)^((a>>((i+7)%8))&0x1)^((x>>i)&0x1)) << i;
        }
        tmp[0] = tmp[0]+tmp[1]+tmp[2]+tmp[3]+tmp[4]+tmp[5]+tmp[6]+tmp[7];
        return tmp[0];
    }

    S盒变换代码:

    //S盒产生
    void s_box_gen(void)
    {
        uint8_t i,j;
        uint8_t s_box_ary[16][16] = {0};
    
    //初始化S盒
        for(i=0;i<0x10;i++)
        {
            for(j=0;j<0x10;j++)
            {
                s_box_ary[i][j] = ((i<<4)&0xF0) + (j&(0xF));
            }
        }
    
        printf("    0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F");
        for(i=0;i<0x10;i++)
        {
            printf("\r\n%2x",i);
            for(j=0;j<0x10;j++)
            {
                printf(" %2x",s_box_ary[i][j]);
            }
        }
    //求在GF(2^8)域上的逆,0映射到自身
        printf("\r\n");
        for(i=0;i<0x10;i++)
        {
            for(j=0;j<0x10;j++)
            {
                if(s_box_ary[i][j] != 0)
                {
                    s_box_ary[i][j] = extEuclidPolynomial(s_box_ary[i][j],0x11B);
                }
            }
        }
    
        printf("\r\n\r\n    0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F");
        for(i=0;i<0x10;i++)
        {
            printf("\r\n%2x",i);
            for(j=0;j<0x10;j++)
            {
                printf(" %2x",s_box_ary[i][j]);
            }
        }
    //对每个字节做变换
        for(i=0;i<0x10;i++)
        {
            for(j=0;j<0x10;j++)
            {
                s_box_ary[i][j]=byteTransformation(s_box_ary[i][j], 0x63);
            }
        }
    
        printf("\r\n\r\n    0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F");
        for(i=0;i<0x10;i++)
        {
            printf("\r\n%2x",i);
            for(j=0;j<0x10;j++)
            {
                printf(" %2x",s_box_ary[i][j]);
            }
        }
    }

    输出如下:

        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
     0  0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
     1 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
     2 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f
     3 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f
     4 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f
     5 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f
     6 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f
     7 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f
     8 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f
     9 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f
     a a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af
     b b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
     c c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf
     d d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df
     e e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef
     f f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff
    
        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
     0  0  1 8d f6 cb 52 7b d1 e8 4f 29 c0 b0 e1 e5 c7
     1 74 b4 aa 4b 99 2b 60 5f 58 3f fd cc ff 40 ee b2
     2 3a 6e 5a f1 55 4d a8 c9 c1  a 98 15 30 44 a2 c2
     3 2c 45 92 6c f3 39 66 42 f2 35 20 6f 77 bb 59 19
     4 1d fe 37 67 2d 31 f5 69 a7 64 ab 13 54 25 e9  9
     5 ed 5c  5 ca 4c 24 87 bf 18 3e 22 f0 51 ec 61 17
     6 16 5e af d3 49 a6 36 43 f4 47 91 df 33 93 21 3b
     7 79 b7 97 85 10 b5 ba 3c b6 70 d0  6 a1 fa 81 82
     8 83 7e 7f 80 96 73 be 56 9b 9e 95 d9 f7  2 b9 a4
     9 de 6a 32 6d d8 8a 84 72 2a 14 9f 88 f9 dc 89 9a
     a fb 7c 2e c3 8f b8 65 48 26 c8 12 4a ce e7 d2 62
     b  c e0 1f ef 11 75 78 71 a5 8e 76 3d bd bc 86 57
     c  b 28 2f a3 da d4 e4  f a9 27 53  4 1b fc ac e6
     d 7a  7 ae 63 c5 db e2 ea 94 8b c4 d5 9d f8 90 6b
     e b1  d d6 eb c6  e cf ad  8 4e d7 e3 5d 50 1e b3
     f 5b 23 38 34 68 46  3 8c dd 9c 7d a0 cd 1a 41 1c
    
        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
     0 63 7c 77 7b f2 6b 6f c5 30  1 67 2b fe d7 ab 76
     1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
     2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
     3  4 c7 23 c3 18 96  5 9a  7 12 80 e2 eb 27 b2 75
     4  9 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
     5 53 d1  0 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
     6 d0 ef aa fb 43 4d 33 85 45 f9  2 7f 50 3c 9f a8
     7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
     8 cd  c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
     9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e  b db
     a e0 32 3a  a 49  6 24 5c c2 d3 ac 62 91 95 e4 79
     b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae  8
     c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
     d 70 3e b5 66 48  3 f6  e 61 35 57 b9 86 c1 1d 9e
     e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
     f 8c a1 89  d bf e6 42 68 41 99 2d  f b0 54 bb 16

    逆S盒变换代码:

    //逆S盒产生
    void inv_s_box_gen(void)
    {
        uint8_t i,j;
        uint8_t s_box_ary[16][16] = {0};
        uint8_t b=0, bb=0;
    
    //初始化S盒
        for(i=0;i<0x10;i++)
        {
            for(j=0;j<0x10;j++)
            {
                s_box_ary[i][j] = ((i<<4)&0xF0) + (j&(0xF));
            }
        }
    
        printf("    0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F");
        for(i=0;i<0x10;i++)
        {
            printf("\r\n%2x",i);
            for(j=0;j<0x10;j++)
            {
                printf(" %2x",s_box_ary[i][j]);
            }
        }
    //对每个字节做变换
        for(i=0;i<0x10;i++)
        {
            for(j=0;j<0x10;j++)
            {
                s_box_ary[i][j]=invByteTransformation(s_box_ary[i][j], 0x05);
            }
        }
    
        printf("\r\n\r\n    0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F");
        for(i=0;i<0x10;i++)
        {
            printf("\r\n%2x",i);
            for(j=0;j<0x10;j++)
            {
                printf(" %2x",s_box_ary[i][j]);
            }
        }
    
    //求在GF(2^8)域上的逆,0映射到自身
        printf("\r\n");
        for(i=0;i<0x10;i++)
        {
            for(j=0;j<0x10;j++)
            {
                if(s_box_ary[i][j] != 0)
                {
                    s_box_ary[i][j] = extEuclidPolynomial(s_box_ary[i][j],0x11B);
                }
            }
        }
    
        printf("\r\n\r\n    0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F");
        for(i=0;i<0x10;i++)
        {
            printf("\r\n%2x",i);
            for(j=0;j<0x10;j++)
            {
                printf(" %2x",s_box_ary[i][j]);
            }
        }
    }

    输出如下:

        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
     0  0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
     1 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
     2 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f
     3 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f
     4 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f
     5 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f
     6 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f
     7 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f
     8 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f
     9 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f
     a a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af
     b b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
     c c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf
     d d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df
     e e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef
     f f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff
    
        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
     0  5 4f 91 db 2c 66 b8 f2 57 1d c3 89 7e 34 ea a0
     1 a1 eb 35 7f 88 c2 1c 56 f3 b9 67 2d da 90 4e  4
     2 4c  6 d8 92 65 2f f1 bb 1e 54 8a c0 37 7d a3 e9
     3 e8 a2 7c 36 c1 8b 55 1f ba f0 2e 64 93 d9  7 4d
     4 97 dd  3 49 be f4 2a 60 c5 8f 51 1b ec a6 78 32
     5 33 79 a7 ed 1a 50 8e c4 61 2b f5 bf 48  2 dc 96
     6 de 94 4a  0 f7 bd 63 29 8c c6 18 52 a5 ef 31 7b
     7 7a 30 ee a4 53 19 c7 8d 28 62 bc f6  1 4b 95 df
     8 20 6a b4 fe  9 43 9d d7 72 38 e6 ac 5b 11 cf 85
     9 84 ce 10 5a ad e7 39 73 d6 9c 42  8 ff b5 6b 21
     a 69 23 fd b7 40  a d4 9e 3b 71 af e5 12 58 86 cc
     b cd 87 59 13 e4 ae 70 3a 9f d5  b 41 b6 fc 22 68
     c b2 f8 26 6c 9b d1  f 45 e0 aa 74 3e c9 83 5d 17
     d 16 5c 82 c8 3f 75 ab e1 44  e d0 9a 6d 27 f9 b3
     e fb b1 6f 25 d2 98 46  c a9 e3 3d 77 80 ca 14 5e
     f 5f 15 cb 81 76 3c e2 a8  d 47 99 d3 24 6e b0 fa
    
    
        0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
     0 52  9 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
     1 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
     2 54 7b 94 32 a6 c2 23 3d ee 4c 95  b 42 fa c3 4e
     3  8 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
     4 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
     5 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
     6 90 d8 ab  0 8c bc d3  a f7 e4 58  5 b8 b3 45  6
     7 d0 2c 1e 8f ca 3f  f  2 c1 af bd  3  1 13 8a 6b
     8 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
     9 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
     a 47 f1 1a 71 1d 29 c5 89 6f b7 62  e aa 18 be 1b
     b fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
     c 1f dd a8 33 88  7 c7 31 b1 12 10 59 27 80 ec 5f
     d 60 51 7f a9 19 b5 4a  d 2d e5 7a 9f 93 c9 9c ef
     e a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
     f 17 2b  4 7e ba 77 d6 26 e1 69 14 63 55 21  c 7d
    展开全文
  • DES算法S盒学习

    千次阅读 2020-08-20 04:25:07
    S盒是将48比特压缩成32比特,S盒接受特定数量的输入48比特,经过8个盒将其转换为32比特输出。 在DES算法中替代由8个不同的S盒完成,每个S盒有6位输入4位输出。 一个S盒就是一个4行16列的表,盒中的每一项都是...

    在密码学中,S盒(Substitution-box)是对称密钥算法执行置换计算的基本结构。
    S盒用在分组密码算法中,是唯一的非线性结构。

     

    S盒是将48比特压缩成32比特,S盒接受特定数量的输入48比特,经过8个盒将其转换为32比特输出。

    在DES算法中替代由8个不同的S盒完成,每个S盒有6位输入4位输出。

    一个S盒就是一个4行16列的表,盒中的每一项都是一个4位二进制数表示的十进制数。
    输入的高低两位做为行数H,中间四位做为列数L,在S-BOX中查找第H行L列对应的数据。
    S盒的行列计数都是从0开始。

    例如,S1盒如下;
    S1盒
    0    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15
    0    14    4    13    1    2    15    11    8    3    10    6    12    5    9    0    7
    1    0    15    7    4    14    2    13    1    10    6    12    11    9    5    3    8
    2    4    1    14    8    13    6    2    11    15    12    9    7    3    10    5    0
    3    15    12    8    2    4    9    1    7    5    11    3    14    10    0    6    13


    以s8盒为例,输入110011,
    第一位和第六位(最高位和最低位)组合为11(二进制),转换为十进制为3,则在s8盒中行号为3;
    接下来计算列,原始数据第二位到第五位为1001(二进制),转换为十进制为9,则在s8盒中列号为9;
    s盒8的03行09列的数字为12,转换为二进制为1100,因此用二进制1100来代替110011;

     

    S盒代替是DES算法的关键步骤,所有的其他的运算都是线性的,易于分析,而S盒是非线性的,相比于其他步骤,提供了更好安全性。

    展开全文
  • 为了在有限的资源下,提高分组密码算法的安全强度,对分组密码算法以及S盒构造设计进行了深入的分析研究,结合Feistel架构和S盒重构的思想,提出了动态S盒的设计方案,并对其进行了相关分析验证。结果表明,经过该...
  • S盒评价标准.docx

    2020-03-25 10:43:24
    条=S盒作为传统加密算法中惟一的非线性结构,其评价标准至关重要,本文档列举8条准则,如有出入,敬请校正。
  • visio软件下载 N-S盒图 用Visio画N-S盒图插件visio软件下载 N-S盒图 用Visio画N-S盒图插件visio软件下载 N-S盒图 用Visio画N-S盒图插件visio软件下载 N-S盒图 用Visio画N-S盒图插件visio软件下载 N-S盒图 用Visio画N...
  • 提出一种基于遗传蚁群算法的S盒构造方法,算法中两次插入遗传算法,利用遗传算法前期收敛速度较快及交叉变异操作避免陷入局部最优的特性,加快蚁群算法的收敛速度,提高求解的效率。基于该方法,给出了构造S盒的完整算法...
  • 生成DES的S盒

    千次阅读 2019-11-09 14:41:29
    DES的S盒满足的规则2. 设计思路2.1 总的思路2.2 满足S盒规则2.2.1 满足①+②2.2.2 满足③2.2.3 满足④2.2.4 满足⑤3. 编程实现3.1 矛盾组3.2 ⑤的不等组3.3 S盒存放3.4 ③④规则实现3.5 ⑤的实现3.6 摆放数字4. ...

    1. DES的S盒满足的规则

    ①S盒的每一行是整数0-15的一个置换;
    ② 每个S盒的传输函数都不是线性的或仿射的;
    ③对一个S盒而言,输入端每改变一位,至少引起输出端改变两位;
    ④S(x)和S(x⊕001100)至少有2位不同;
    ⑤对于任何e与f,S(x)≠S(x⊕11ef00)
    ⑥当输入端任何一位保持不变时,S盒应保证在其输出端0和1的个数之差达到最小。

    • 文中实现了①~⑤条,第⑥条是统计规律。实际上主要需要实现的是3、4、5这3条规则。

    2. 设计思路

    2.1 总的思路

      总的思路是,类比用栈实现走迷宫的方法,生成一个符合要求的S盒,实际上就是把数字按照顺序从(0,0)一个个摆放到(3,15)。所以实现时,就依顺序,从(0,0)开始放置数字,直到成功放到(3,15)。如果在摆放数字到(r,c)失败时,回退一步,消除影响,再次尝试换一个数据来进行摆放。
    在这里插入图片描述

    2.2 满足S盒规则

    2.2.1 满足①+②

      因为本身摆放数字的时候,每行是独立的,所以实现第①条很容易,并且在满足③和④后,不满足第②的几率很小很小。用数组haveput[16]来防止生成的S盒出现列内重复数字。

    2.2.2 满足③

      要满足第③条,输入变化1位,输出至少变化2位。
      首先考虑简单的,输入变化导致选择到了同一列中的不同行。只改变S=b1b2b3b4b5b6中的1/6位,实际上就是在列内行变化。原来是第0(00)行,可能会变到第1行(01)或者第2行(10)。再考虑行内的列变化,如果改变b2b3b4b5中的某一位,则会导致行内列变化,变化到同一行中的不同列。
      实现行内列变化,引入矛盾组的概念,相当于黑名单。组<x>内的数字,都是与<x>只有一位差别,或者为x。例如,下图中每列为1个组,组<1>={0,3,5,9},组<9>={8,11,13,1}。
    在这里插入图片描述
      先实现输入变化一位导致的行内列变化,输出变化2位。实现时,在放置(2,4)时,需要让(2,4)与(2,0),(2,5),(2,6),(2,12)内的数字相差至少2位。因为(2,5),(2,6),(2,12)还没有摆放,所以在放置(2,4)只需要考虑(2,0),如果(2,0)中现在摆放着6,摆放(2,4)时,摆放的数字只要满足不在组<6>中即可,就满足了摆放的不是相差1位的要求。
    在这里插入图片描述
      再实现输入变化一位导致的列内行变化,输出变化2位。放置(3,3)时,需要检查<3>的矛盾组<3>={2,1,7,11},因为2,1都小于3,所以放(3,3)时需要考虑(2,3)和(1,3)中放的数字γ和β,(3,3)中放的数字不能是<γ>和<β>中的数字,也就是不能只相差一位。
    在这里插入图片描述
      对于不能相同数字,行内不同列数字不相同是用haveput数组保证的,列内则需要第一次扩展矛盾组。组<3>扩展为<3> ={3,2,1,7,11},组中第一个数字就是组号,这样检查矛盾组的时候,就能检查是否相同和相差一位。这样,放(3,3)时需要考虑(2,3)和(1,3)中放的数字γ和β,(3,3)中放的数字不能是<γ>和<β>中的数字,就考虑到了相同和只相差一位。
      到此为止,S盒就满足了输入相差一位,输出变化至少两位。

    2.2.3 满足④

      用满足第三条的方法,只不过在矛盾组中再加入一个数字即可。如<4>={4, 5, 6, 0, 12},满足第四条,就再次扩展<4>,加入4与0110异或的结果2,扩展后的<4>={4, 5, 6, 0, 12, 2}, ,因为第四条仅仅是行内的列规则,所以实现时只需要检查行内的列即可。
      如放置(2,4)时,<4>的最后一位存放着与0110异或结果,为2,所以考虑中(2,2)存放的数字,假设为8,那么(2,4)中不能存放与8相差一位的数字即<8>中的9, 10, 12, 0。
    在这里插入图片描述

    2.2.4 满足⑤

      类比满足前面准则的方法,引入不等组。观察以后发现,⑤的实现实际上是先选择行,在选择列不相等。第0行和第1行的摆放不受⑤的影响,因为b1=1,b6=0不会让第0和第1之间影响。但是第0行和第2行、第1行与第3行间有影响,摆放第2、3行数据的时候,要对应考虑第0、1内的数据。
      具体来说,2/3行中元素,需要查不等表: 0/2/4/6列查0/1行的8/10/12/14列不等,1/3/5/7列查0/1行的9/11/13/15列不等,8/10/12/14列的查0/1行的0/2/4/6列不等,9/11/13/15列的查0/1行的1/3/5/7列不等。
      这样一来,就实现了模2变化11ef00元素的不相等。
    在这里插入图片描述
    在这里插入图片描述


    3. 编程实现

    3.1 矛盾组

    int exgroup[16][6] = {//列矛盾是[0]--[4].行矛盾是[1]--[5]
    	{0,  1,  2,  4,  8,  6},   //0 group
    	{1,  0,  3,  5,  9,  7},   //1 group
    	{2,  3,  0,  6, 10,  4},   //2 group
    	{3,  2,  1,  7, 11,  5},   //3 group
    	{4,  5,  6,  0, 12,  2},   //4 group
    	{5,  4,  7,  1, 13,  3},   //5 group
    	{6,  7,  4,  2, 14,  0},   //6 group
    	{7,  6,  5,  3, 15,  1},   //7 group
    	{8,  9, 10, 12,  0, 14},   //8 group
    	{9,  8, 11, 13,  1, 15},   //9 group
    	{10, 11, 8, 14,  2, 12},   //10 group
    	{11, 10, 9, 15,  3, 13},   //11 group
    	{12, 13,14,  8,  4, 10},   //12 group
    	{13, 12,15,  9,  5, 11},   //13 group
    	{14, 15,12, 10,  6,  8},   //14 group
    	{15, 14,13, 11,  7,  9}    //15 group
    };
    

    3.2 ⑤的不等组

    int forrule4[4][4]{
    	{8,10,12,14}, // 0/2/4/6
    	{9,11,13,15}, // 1/3/5/7
    	{0, 2, 4, 6}, // 8/10/12/14
    	{1, 3, 5, 7}  // 9/11/13/15
    };
    

    3.3 S盒存放

    typedef struct
    {
    	int x = 0;		//当前单元格的行号
    	int num;    //num is the current num of the cell
    	set <int>tried;//some have try but fail
    } Cell;		//定义单元格类型
    typedef struct
    {
    	Cell data[4][BoxSize];//存放1个S盒
    	int top;		//栈顶指针
    } StType;		//顺序栈类型
    

    3.4 ③④规则实现

    //行内规则
    for (int k = 1; k < 6; k++)//考虑行内规则
    		{
    		if (exgroup[i][k] < i)
    			for (int m = 1; m < 5; m++)//因为有havaput检查,所以行里面本身不会有相同的
    				{
    					notchoose.insert(exgroup[st.data[row][exgroup[i][k]].num][m]);
    				}
    		}
    

      行内规则③,就遍历矛盾组的[1]-[5]列,如果它们比当前列号小,已经摆放上了,就得考虑。考虑时,不用担心重复0-15,有haveput保证。保证不是只相差1位就行,也就是内部考虑矛盾组的[1]-[4]列。
      行内规则④,存在矛盾组的第[5]列,所以合并以后就可以和③一起实现。

    //列内规则
    for (int k = 1; k < 5; k++)//考虑列内规则
    {
    if (exgroup[row][k] < row)//行号小于row的,需要考虑
    	for (int m = 0; m < 5; m++)//与矛盾的列中数字相差一位不能选,相同也不能选,所以要到m=4
    {
    	notchoose.insert(exgroup[st.data[exgroup[row][k]][i].num][m]);//索引次序不能搞错
    	}
    }
    

      列内规则,也是遍历矛盾组的[1]-[4]列,如果如果它们比当前行号小,已经摆放上了,就得考虑。haveput是一维的,所以需要考虑重复和差一位,内部考虑矛盾组[0]-[4]列。

    3.5 ⑤的实现

    mod = i % 2;
    		if (row > 1)//第2/3行开始才要和前面对比,第2行对比第0行,第3行对比第1行
    		{
    			if (mod==0 && i < 8)
    				notequal = 0;
    			else if(mod==1 && i < 8)
    				notequal = 1;
    			else if (mod == 0 && i >7)
    				notequal = 2;
    			else if (mod == 1 && i > 7)
    				notequal = 3;
    			for (int q = 0; q < 4; q++)
    				notchoose.insert(st.data[row - 2][forrule4[notequal][q]].num);
    		}
    

      只有row>1才要判断,判断当前列号大于8还是小于8,奇数还是偶数,0/2/4/6列查0/1行的8/10/12/14列不等notequal = 0, 1/3/5/7列查0/1行的9/11/13/15列不等notequal = 1,8/10/12/14列的查0/1行的0/2/4/6列不等notequal = 2, 9/11/13/15列的查0/1行的1/3/5/7列不等notequal = 3,然后对应到索引查表即可。

    3.6 摆放数字

    //数字摆放
    	//当前单元格选哪个数字好呢?	
    for (int j = 0; j < 16; j++)
    	if (haveput[j] == 1)
    		notchoose.insert(j);//不仅要满足矛盾组规则,还要满足同一行不重复
    	if (notchoose.size() < 16)
    	{
    	//做差集,全集与不能选的相减,得到的就是可以选的
    	it = set_difference(U.begin(), U.end(), notchoose.begin(), notchoose.end(), canchoose.begin());
    	canchoose.resize(it - canchoose.begin());
    	if (canchoose.size() > 1)random_shuffle(canchoose.begin(), canchoose.end());//不然就随机选一个
    	currentnum = *canchoose.begin();//重排列以后选第一个
    	flag = 1;//OhYeah!找到一个可以放在这个单元格的了
    	canchoose.resize(16);//把那个向量大小复原
    		}
    

      判断能不能放数字,做全集U=[0-15]差集就可以了,如果差集非空就说明可以放,找到这样的数字,就立下flag=1。如果flag=1说明可以放数字,那就放。

    if (flag == 1)//可以在当前单元格放数字
    {
    		st.top++; st.data[row][st.top].x = i; st.data[row][st.top].num = currentnum;
    		st.data[row][st.top].tried.insert(currentnum);//记住这个单元格放过这个数字
    		haveput[currentnum] = 1;//放好了,行内重复标记
    		notchoose.clear();//清空,准备下一个单元格
    		flag = 0;
    		if (st.top < 15)//可能现在是之前的回溯,把下一个单元格的黑历史清空
    			{
    			if (!st.data[row][st.top + 1].tried.empty())
    					st.data[row][st.top + 1].tried.clear();
    			}
    		else if (st.top == 15 && row < 3)//如果在最后一列,要清空下一行第一个的黑历史
    			if (!st.data[row + 1][0].tried.empty())
    					st.data[row + 1][0].tried.clear();
    		}
    

      放数字放下以后,haveput进行标记,不能重复放,放完以后,flag=0复位准备下一次,同时为了回溯时不走重复的路,S盒结构的那个单元需要记住自己放了这个数字。如果不凑巧这个单元格没有数字可以放,那就怪前面的单元格放错了,回溯,如下:

    else {//不凑巧,这个单元格没有数字可以放,回溯
    	notchoose.clear();
    	haveput[st.data[row][st.top].num] = 0;//退一步,之前放的更改,其它单元可以放
    	notchoose.insert(st.data[row][st.top].tried.begin(), st.data[row][st.top].tried.end());//不在同一个地方摔倒两次
    	st.top--;
    	if (st.top == -1 && row > 0)//注意放置在哪里!!!
    	{
    		st.top = 15;//最右上
    		row--;
    		for (int m = 0; m < 16; m++) haveput[m] = 1;
    		haveput[st.data[row][st.top].num] = 0;
    	}
    }
    

      什么时候会知道放完了呢,那就是i=16(只有[15]列且row为3),跳出while循环:

    i = st.data[row][st.top].x + 1;//现在在放第row行第i个单元格
    		if (row == 3 && i == 16) break;//已经做完了!注意顺序!!!
    		if (i == 16)//往下走一行,走到下一行的最左边
    		{
    			row++;
    			st.top = -1;
    			i = 0;
    		for (int m = 0; m < 16; m++) haveput[m] = 0;//新起一行了,把行内重复标记清空
    		}
    

    4. 结果呈现

    在这里插入图片描述
      总共有8个S盒:
    在这里插入图片描述
    在这里插入图片描述

    5. 完整代码

    #include <cstdlib>
    #include <set>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    const int BoxSize = 16;
    using namespace std;
    typedef struct
    {
    	int x = 0;		//当前单元格的行号
    	int num;    //num is the current num of the cell
    	set <int>tried;//some have try but fail
    } Cell;		//定义单元格类型
    typedef struct
    {
    	Cell data[4][BoxSize];//存放1个S盒
    	int top;		//栈顶指针
    } StType;		//顺序栈类型
    
    // the neibough of a is exgroup[a],they diff 1 bit from a
    int exgroup[16][6] = {//列矛盾是[0]--[4].行矛盾是[1]--[5]
    	{0,  1,  2,  4,  8,  6},   //0 group
    	{1,  0,  3,  5,  9,  7},   //1 group
    	{2,  3,  0,  6, 10,  4},   //2 group
    	{3,  2,  1,  7, 11,  5},   //3 group
    	{4,  5,  6,  0, 12,  2},   //4 group
    	{5,  4,  7,  1, 13,  3},   //5 group
    	{6,  7,  4,  2, 14,  0},   //6 group
    	{7,  6,  5,  3, 15,  1},   //7 group
    	{8,  9, 10, 12,  0, 14},   //8 group
    	{9,  8, 11, 13,  1, 15},   //9 group
    	{10, 11, 8, 14,  2, 12},   //10 group
    	{11, 10, 9, 15,  3, 13},   //11 group
    	{12, 13,14,  8,  4, 10},   //12 group
    	{13, 12,15,  9,  5, 11},   //13 group
    	{14, 15,12, 10,  6,  8},   //14 group
    	{15, 14,13, 11,  7,  9}    //15 group
    };
    
    int forrule4[4][4]{
    	{8,10,12,14}, // 0/2/4/6
    	{9,11,13,15}, // 1/3/5/7
    	{0, 2, 4, 6}, // 8/10/12/14
    	{1, 3, 5, 7}  // 9/11/13/15
    };
    
    void genSbox(int times, FILE*&fid)
    {
    	StType st; st.top = -1;//初始化结构
    	int haveput[16] = { 0 };//行内重复标记,行内不能有重复的!
    	int currentnum;//当前单元格决定摆放的数字
    	int a[16] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
    	vector<int>U(a, a + 16);//全集,用于与不能摆的数字集合notchoose做差运算,得到可以摆的
    	set<int> notchoose;//当前单元格不能摆放的数字
    	vector<int> canchoose(16);//当前单元格可以摆的数字,由全集U和不能摆的数字集合notchoose做差运算得到
    	vector<int>::iterator it;//用于获得当前单元格可以摆的所有数字
    	int flag = 0;//当前单元格摆成功了,flag=1.当前单元格摆不了,要回溯,flag=0
    	int i = 0;//列号,正在摆的那一列
    	int  row = 0;//行号,摆到哪一行了
    	int notequal = 0;
    	currentnum = rand() % 16;//摆第一个,启动
    	st.top++; st.data[row][st.top].x = i; st.data[row][st.top].num = currentnum;
    	haveput[currentnum] = 1;
    	int mod = 0;
    	while (1)
    	{
    		i = st.data[row][st.top].x + 1;//现在在放第row行第i个单元格
    		if (row == 3 && i == 16) break;//已经做完了!注意顺序!!!
    		//printf("(row,i,st.top)===(%d,%d,%d)\n", row, i, st.top);
    		if (i == 16)//往下走一行,走到下一行的最左边
    		{
    			row++;
    			st.top = -1;
    			i = 0;
    			for (int m = 0; m < 16; m++) haveput[m] = 0;//新起一行了,把行内重复标记清空
    		}
    
    		for (int k = 1; k < 6; k++)//考虑行内规则
    		{
    			if (exgroup[i][k] < i)
    				for (int m = 1; m < 5; m++)//因为有havaput检查,所以行里面本身不会有相同的
    				{
    					notchoose.insert(exgroup[st.data[row][exgroup[i][k]].num][m]);
    				}
    		}
    		for (int k = 1; k < 5; k++)//考虑列内规则
    		{
    			if (exgroup[row][k] < row)//行号小于row的,需要考虑
    				for (int m = 0; m < 5; m++)//与矛盾的列中数字相差一位不能选,相同也不能选,所以要到m=4
    				{
    					notchoose.insert(exgroup[st.data[exgroup[row][k]][i].num][m]);//索引次序不能搞错
    				}
    		}
    		mod = i % 2;
    		if (row > 1)//第2/3行开始才要和前面对比,第2行对比第0行,第3行对比第1行
    		{
    			if (mod == 0 && i < 8)
    				notequal = 0;
    			else if (mod == 1 && i < 8)
    				notequal = 1;
    			else if (mod == 0 && i > 7)
    				notequal = 2;
    			else if (mod == 1 && i > 7)
    				notequal = 3;
    			for (int q = 0; q < 4; q++)
    				notchoose.insert(st.data[row - 2][forrule4[notequal][q]].num);
    		}
    
    		//当前单元格选哪个数字好呢?	
    		for (int j = 0; j < 16; j++)
    			if (haveput[j] == 1)
    				notchoose.insert(j);//不仅要满足矛盾组规则,还要满足同一行不重复
    		if (notchoose.size() < 16)
    		{
    			//做差集,全集与不能选的相减,得到的就是可以选的
    			it = set_difference(U.begin(), U.end(), notchoose.begin(), notchoose.end(), canchoose.begin());
    			canchoose.resize(it - canchoose.begin());
    			if (canchoose.size() > 1)random_shuffle(canchoose.begin(), canchoose.end());//不然就随机选一个
    			currentnum = *canchoose.begin();//重排列以后选第一个
    			flag = 1;//OhYeah!找到一个可以放在这个单元格的了
    			canchoose.resize(16);//把那个向量大小复原
    		}
    
    		if (flag == 1)//可以在当前单元格放数字
    		{
    			st.top++; st.data[row][st.top].x = i; st.data[row][st.top].num = currentnum;
    			st.data[row][st.top].tried.insert(currentnum);//记住这个单元格放过这个数字
    			haveput[currentnum] = 1;//放好了,行内重复标记
    			notchoose.clear();//清空,准备下一个单元格
    			flag = 0;
    			if (st.top < 15)//可能现在是之前的回溯,把下一个单元格的黑历史清空
    			{
    				if (!st.data[row][st.top + 1].tried.empty())
    					st.data[row][st.top + 1].tried.clear();
    			}
    			else if (st.top == 15 && row < 3)//如果在最后一列,要清空下一行第一个的黑历史
    				if (!st.data[row + 1][0].tried.empty())
    					st.data[row + 1][0].tried.clear();
    		}
    		else {//不凑巧,这个单元格没有数字可以放,回溯
    			notchoose.clear();
    			haveput[st.data[row][st.top].num] = 0;//退一步,之前放的更改,其它单元可以放
    			notchoose.insert(st.data[row][st.top].tried.begin(), st.data[row][st.top].tried.end());//不在同一个地方摔倒两次
    			st.top--;
    			if (st.top == -1 && row > 0)//注意放置在哪里!!!
    			{
    				st.top = 15;//最右上
    				row--;
    				for (int m = 0; m < 16; m++) haveput[m] = 1;
    				haveput[st.data[row][st.top].num] = 0;
    			}
    		}
    	}
    	fprintf(fid, "%s%d%s", "-------------------S[", times + 1, "]----------------------\n");
    	for (int h = 0; h < 4; h++)
    	{
    		for (int n = 0; n <= 15; n++)
    		{
    			fprintf(fid, "%d", st.data[h][n].num);
    			if (n < 15) fprintf(fid, "%s", ",");
    		}
    		fprintf(fid, "%s", "\n");
    	}
    	fprintf(fid, "%s", "\n");
    
    }
    
    int main()
    {
    	cout << "please enter your rand seed,an integer like 123:" << endl;
    	int myseed;
    	cin >> myseed;
    	srand(myseed);
    
    	char sboxpath[81] = "Sbox.csv";
    
    	FILE * fid = fopen(sboxpath, "w");
    	for (int i = 0; i < 8; i++)
    		genSbox(i, fid);
    	fclose(fid);
    	cout << "Your Sbox has stored in " << sboxpath << ". Please check it!";
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 本压缩包里包括一些常见用来测试并分析S盒性能的库函数。
  • 随着4 bit S盒在轻量级密码算法中的广泛应用,如何捕获这些4 bit S盒输入及输出的代数关系成为了目前的研究热点之一。根据S盒的输入及输出关系,提出了<i>n</i> bit S盒的非线性回路代数关系的通用求解算法。针对4 ...
  • DES算法S盒学习.pdf

    2021-09-13 14:20:34
    DES算法S盒学习.pdf
  • 利用混沌系统产生的序列,经过一系列简单处理,结果作为S盒部分密钥,从而保障S盒相对安全性,进而在保障加密码算法的基础上,提高运算效率。
  • 轻量S盒密码性质研究

    2021-03-27 22:35:05
    轻量S盒密码性质研究
  • S盒构造函数

    2011-11-23 19:02:11
    本代码是DEV C++ 编译通过的,描述了S盒的构造函数
  • AES S盒分析PPT

    2011-04-22 22:21:41
    介绍了AES S盒实现的原理和机制,以及在实现S盒之前所要掌握的数学知识。
  • 本软件是为实现对称密码算法中...用户能够利用本软件实现密码算法中核心组件S盒的非线性度、差分均匀性、最佳线性逼近优势、代数次数,代数正规式、代数项数分布、不动点个数、扩散特性以及雪崩特性等指标的自动计算。
  • S盒是大多数分组密码算法中... 本文介绍用硬件实现的两种规格的S盒变换,它能实现8×8和6×4两种规格S盒的任意布尔函数变化。文中最后给出了电路仿真结果及其电路规模和延时估计。S盒的设计原理S盒的功能就是一种简单
  • S盒的变换

    千次阅读 2016-01-13 15:58:19
    假设输入A=a1a2a3a4a5a6,则 A(行号)=a1a6, B(列号)=a2a3a4a5 再看S盒查表,第A行B列的数输出。 例如:输入为 011101 则行号A= 01 列号 B=1110 所以查找S盒表,输出第1行 第14列的数 =3

    假设输入A=a1a2a3a4a5a6,则 A(行号)=a1a6, B(列号)=a2a3a4a5
    再看S盒查表,第A行B列的数输出。
    例如:输入为 011101 则行号A= 01 列号 B=1110
    所以查找S盒表,输出第1行 第14列的数 =3

    这里写图片描述

    这里写图片描述

    展开全文
  • 研究了Rijndael算法中非线性变换S盒的构造机制,通过类似的方法构造出了一批密码性能接近最优的4×4和6×6的S盒,...对这类S盒的雪崩概率进行统计分析,从而找到若干规律,这将有助于生成安全性更高、规模更大的S盒
  • S盒是分组密码算法中唯一的非线性部件,设计一个性能良好的S盒具有重要的实际意义。...最后在提出的S盒的Lyapunov指数定义的基础上计算了该S盒的Lyapunov指数,结果表明该方法生成的S盒具有良好的密码学性质。
  • AES s盒生成代码

    热门讨论 2011-04-22 22:15:30
    AES的S盒可以用扩展的欧几里德和费马定理来写,这里我采用费马定理。要注意的是S盒的求逆过程是在加瓦罗域下进行的,所以里面的所有乘法、除法、加法、减法都是在加瓦罗域下进行。
  • DES密码算法 S盒P盒

    2012-03-21 14:46:30
    C语言自编DES加密算法S盒与P盒,原理简单明了,注释全面,需要的同学拿去吧!
  • 基于矩阵幂乘法的S盒性能分析
  • 在介绍了数据加密标准DES加密算法的基础上,对其唯一非线性组件-S盒的设计进行分析,得出输入的某一位(这里只分析了最高位和最低位)改变,对输出位的改变是成对出现的这一结论。
  • 通过实验找到了一类新的基于元胞自动机的S盒,分析了该S盒的置换性质,证明了其仅在规模为5时是一个置换。通过构造差分矩阵的方法给出了该S盒的非平凡差分转移概率与差分矩阵的秩之间的关系,从而得到其取值范围。...
  • 基于S盒的WSN加密算法

    2015-04-03 11:07:19
    基于S盒的WSN加密算法 针对无线传感器网络的特点 实现的分组加密
  • 采用遗传算法来构造S盒,并引入了启发式变异策略。该策略既可以防止优良的基因受到破坏,又可以保证群体中个体的多样性。基于该方法,给出了6×6的S盒构造的完整程序描述,并获得了一批高非线性度和低差分均匀度的S...
  • S盒差分分布表

    热门讨论 2013-01-07 23:04:51
    S盒差分分布表,详细地给出了求解差分分布表的方法,简单实用!!
  • 提出一种基于遗传蚁群算法的S盒构造方法,算法中两次插入遗传算法,利用遗传算法前期收敛速度较快及交叉变异操作避免陷入局部最优的特性,加快蚁群算法的收敛速度,提高求解的效率。基于该方法,给出了构造S盒的完整...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,475
精华内容 38,190
关键字:

s盒