密码算法详解——Simon

浏览数：37 / 时间：2015年06月08日

0 Simon简介

　　以前只知道DES、AES之类非常出名的密码学算法，最近看了Simon，觉得还比较简单，在此做一个简单的介绍。课上听老师说Simon算法是一个非常优秀的密码学算法，但我还是没发现究竟经典在何处，o(╯□╰)o，这都是体外话了。

　　由于表达能力有限，单纯的介绍可能不能理解的比较清楚，有问题建议直接阅读参考文献[1]。

　　Simon属于轻量级分组密码算法（LIGHTWEIGHT BLOCK CIPHER）。主要用于硬件或软件条件受限制（例如：芯片面积、微处理器、内存较小等），同时对安全有一定需求的环境。相比DES、AES等，Simon在结构上相对简单，轮函数操作也不复杂。因此在计算速度和资源消耗上更有优势，更能适应软硬件条件受限的情况。但同时，安全性有所下降。

　　为了适应不同的场合，Simon提供了不同的方案，如图0.

技术分享

图0 Simon种类图1 Simon轮加密原理图

　　其中，　

　　　　block size : 明文块大小；

　　　　key size : 初始密钥大小；

　　　　word size : "字"大小；

　　　　key words : 初始密钥包含"字"的个数；

　　　　const seq : 计算轮密钥应该使用的z的值；

　　　　rounds : 加解密的轮数。

1 算法流程

　　Simon的整个流程比较简单，主要包括每一轮的加密和轮密钥计算。接下来分别进行介绍。

1.1 轮加密

　　每一轮的操作如图1。明文被分成两个"字"，每个"字"的二进制位数都为n（即word size），X_i+1和X_i分别表示高位部分和低位部分（个人认为，这个没有特别要求，X_i+1也可以表示低位、X_i表示高位部分，只要加解密按照同样的顺序即可。为了叙述统一，本文按照X_i+1表示高位、X_i表示低位）。

　　每轮的加密主要涉及到3种操作，如图2所示，分别是异或、按位与和循环左移（如果j是负数则表示循环右移）。每轮加解密的过程用公式表示如图3，其中x对应X_i+1、y对应X_i、k为轮密钥。

技术分享

图2 Simon运算图3 Simon轮加解密公式

　　在C++实现中，按位异或和与都有直接的操作符，对于循环移位可以按照如下方法实现。将x循环左移i（i>=0）位，假设x对应的二进制位数为n，则可以表示为: (x<<i) | (x>>(n-i))。当然，x应该是无符号的数，不然会出错。

 1         /*
 2          * 加密后的低32位是明文的高32位
 3          */
 4         tempCipherLower  = plainText[0];
 5         tempCipherHigher = plainText[1] ^ keys[i] ^ 
 6                         ( ((plainText[0]<<1)|(plainText[0]>>(SIMON_WORD_SIZE-1))) & ((plainText[0]<<8)|(plainText[0]>>(SIMON_WORD_SIZE-8))) ) ^
 7                         ((plainText[0]<<2)|(plainText[0]>>(SIMON_WORD_SIZE-2)));
 8         /*
 9          * 重新将加密的结果复制到plainText中
10          */
11         plainText[0]     = tempCipherHigher;
12         plainText[1]     = tempCipherLower;

1.2 轮密钥

　　轮密钥扩展公式如图4，其中m表示的是原始密钥中"字"的个数，图5是当m为2时的原理图。

技术分享

图4 轮密钥扩展公式图5 轮密钥扩展原理图

　　c为一个常数，它的二进制位数为n，最低两位为0，其余高位为1。

　　z是一个常数数组，值如图6，在每种情况下z的取值都是固定的（见图0，不是图灵，O(∩_∩)O~），每轮加解密时只取一个比特位参与运算。

　　k_i、k_i+1、k_i+2等都是轮密钥。

　　I表示不进行移位。

技术分享

图6 z

　　C++代码实现如下（只包含block size为64，key size为96和128的两种情况）：

 1 /*
 2  * Simon：计算密钥，字大小为32
 3  * inputKey：初始的密钥
 4  * keys：计算后得到的每轮密钥
 5  */
 6 void setSimonKeys32 ( unsigned int * inputKey, unsigned int * keys ) {
 7 
 8     /*
 9      * 算法中的常数c，大小为2^n - 4，其中n是字的长度，即SIMON_WORD_SIZE
10      * 转化为二进制，即最低两位为0，其它位全为1
11      */
12     unsigned int c = 0xfffffffc;
13 
14     int i;
15     for ( i = 0; i < SIMON_KEY_WORDS; i++ )  {
16         keys[i] = inputKey[i];
17     }
18 
19     /*
20      * 求解后面轮的密钥
21      * 先求其它的异或，最后求Zji，如果为1则对最低位进行修改，否则不变
22      */
23     if ( SIMON_KEY_WORDS == 3 ) {
24         for ( i = 0; i < SIMON_ROUNDS-SIMON_KEY_WORDS; i++ ) {
25             keys[i+SIMON_KEY_WORDS] = c ^ keys[i] ^
26                             ((keys[i+2]>>3) | (keys[i+2]<<(SIMON_WORD_SIZE-3))) ^
27                             ((keys[i+2]>>4) | (keys[i+2]<<(SIMON_WORD_SIZE-4)));
28             // SIMON_WORD_SIZE为32时，无论SIMON_KEY_WORDS为3还是4，周期都是62
29             if ( z[SIMON_SEQUENCE_NUMBER][i%62] == 1 ) {
30                 keys[i+SIMON_KEY_WORDS] ^=  0x1;
31             }
32         }
33     } else if ( SIMON_KEY_WORDS == 4 ) {
34         // int cycle = (SIMON_SEQUENCE_NUMBER == 0 || SIMON_SEQUENCE_NUMBER == 1)?31:62;
35         unsigned int temp = 0x00000000;
36         for ( i = 0; i < SIMON_ROUNDS-SIMON_KEY_WORDS; i++ ) {
37             temp = ((keys[i+3]>>3) | (keys[i+3]<<(SIMON_WORD_SIZE-3))) ^ keys[i+1];
38             keys[i+SIMON_KEY_WORDS] = c ^ keys[i] ^ temp ^ ((temp>>1) | (temp<<(SIMON_WORD_SIZE-1)));
39             if ( z[SIMON_SEQUENCE_NUMBER][i%62] == 1 ) {
40                 keys[i+SIMON_KEY_WORDS] ^=  0x00000001;
41             }
42         }
43     }
44 
45 }

2 代码实现

　　自己实现的代码（C++ ）：https://github.com/openluopworld/Crypt/tree/master/SimonAndSpeck/code

　　Github上的一份代码（C）：https://github.com/mmeh/simon-speck-cryptanalysis

　　（比一比就能发现差距真大，╮(╯▽╰)╭）

3 参考文献

[1] Beaulieu R, Shors D, Smith J, et al. The SIMON and SPECK Families of Lightweight Block Ciphers[J]. IACR Cryptology ePrint Archive, 2013, 2013: 404.

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

密码算法详解——Simon