分组密码总结-DES,AES,SM4

简介 分组密码属于对称密码的一种,其特点是加解密都是对明文/密文进行分组后逐组进行加解密。通俗讲就是将明文分块,然后分块加密,解密同理。 分组密码的基本原理: 代换:明文分组到密文分组的可逆变换 扩散:将明文的统计特性散布到密文中去,使得明文的每一位影响密文中多位的值 混淆:使密文和密钥之间的统计关系变得尽可能复杂,使攻击者无法得到密钥,通常使用复杂的代换算法实现 分组密码体制基本上都是基于乘积(由一系列代换和置换构成)和迭代来构造的。常见的分组密码结构有Feistel网络和SP(Substitution Permutation)网络。DES算法和AES算法分别就是基于Feistel网络和SP网络实现的。 Feistel网络的加密过程为:将明文$x$一分为二,即$x=L_0R_0$,$L_0$是左边的$m$bit,$R_0$是右边的$m$bit,于是对于迭代次数$r$,设$1\le i\le r$,则: $$\left \{ \begin{array}{c} L_i=R_{i-1} \\ R_i=L_{i-1}\oplus F(R_{i-1},K_i) \end{array} \right.,F为圈函数$$ 为了可以利用同一个算法进行加密和解密,Feistel分组密码加密过程的最后一轮没有左右对换。 SP网络主要是对明文进行两项操作:由子密钥控制的替换S、置换或可逆的线性变换P。前者主要起混淆作用,后者主要起扩散作用。 设计分组密码,有以下几个要求: 分组长度$n$要足够大 密钥量要足够大(置换字集中的元素足够多),尽可能消除弱密钥 由密钥确定的置换算法要足够复杂,充分实现扩散和混淆 加解密运算简单,易于实现 数据扩展(一般没有) 差错传播尽可能小 DES DES(Data Encryption Standard)是第一个众所周知的分组密码,其分组长度为64bit,密钥长度也为64bit。于1977年1月15日被公布,现已被AES取代。 DES采用Feistel网络进行实现,一共迭代16轮,64bit密钥中包含56bit密钥和8bit奇偶校验位。下图简要介绍了其工作原理: 初始置换和逆初始置换 初始置换和逆初始置换在密码方面作用不大,其主要作用是打乱明文ASCII码字划分的关系,打乱各位的次序。 初始置换 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 逆初始置换 408481656246432 397471555236331 386461454226230 375451353216129 364441252206028 353431151195927 342421050185826 33141 949175725 置换的方法是,将置换表中数字对应位置的值替换原来的值。经过初始置换,明文$X$变为:...

Apr. 8, 2020 · 3 min · 509 words

有关多项式的算法——四则运算、求逆

算法介绍 多项式的运算可以说比之前的多精度数运算还要简单一点,因为多项式的加减只能存在于同次数的项之间,所以不需要考虑加减法里面的进位退位问题,这也就使得乘除法简单了很多。 加减法的原理就没什么好说的了,乘除法都是基于多精度数的算法修改的,存储多项式也使用了ArrayList,索引值对应项的次数,其元素大小对应项的系数。 求逆则使用了欧几里得算法: 以及有限域 $F_{2^8}$ 上基于指数对数表的乘法和求逆,对应的不可约多项式 $f(x)=x^8+x^6+x^5+x+1$ 。 指数对数表的构建方法如下: 将元素$02$表示成为$\alpha$,依次计算 $\alpha^i\space modf(\alpha)\space,i=0,1,\cdots, 254$ ,将所得结果转变为十进制数,设为$\beta_i ,i=0,1,\cdots, 254$; 建表。第一行为 $\alpha_i ,i=0,1,\cdots, 254$,第二行元素依次为 $\beta_i ,i=0,1,\cdots, 254$。由于 $\alpha^0\equiv\alpha^{255}\space modf(\alpha)$,约定第$2$行,第$255$列元素为$0$; 0 1 2 3 … 253 254 255 1 2 4 8 … 233 177 0 按所建表的第二行元素的大小进行重排列; 255 0 1 197 … 72 230 104 0 1 2 3 … 253 254 255 将(3)中表的第一行放在(2)中表的第三行。 序号 0 1 2 3 … 253 254 255 $(02)^i$ 1 2 4 8 … 233 177 0 $log_{(02)^i}$ 255 0 1 197 … 72 230 104 建立上述指数对数表之后,通过查表很容易求出两个元素的乘积。又由于对于 $i=0,1,\cdots, 254$ 均有 $(\alpha^i)^{-1}\equiv\alpha^{255-i}mod(f(\alpha))$ ,所以可通过查表也很容易求出元素的逆元。...

Dec. 18, 2019 · 8 min · 1500 words

多精度数的四则运算-Java和Python实现

多精度数指的是位数超过1024Bit的数。由于这一类数的位数超过了计算机CPU寄存器表达,也就是超出了计算机的字长,所以不能够使用计算机进行直接的运算。除此之外,多精度数的大小也超出了计算机中定义的整型变量的最大大小,所以也不能使用标准的整型来存储这一类数,而需要使用数组或是字符串来存储。 对于多精度数的计算,目前有两种处理办法: 模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。 这个方法的优点是操作逻辑符合人们的日常思维,易于理解,缺点是效率较低。 将多精度数当作一个二进制流进行处理,使用各种移位和逻辑操作来进行加减乘除运算。 这个方法的优点是执行效率高,缺点是代码极其复杂,可读性低,难以理解。 下面的算法都是基于第一种办法进行处理。 算法原理 先重新理一下竖式计算的流程: 加法在手工竖式计算中,当两个位相加得到的值大于10时就会产生一个进位值,并会在高一位的计算中把进位值也加入计算,这样从低位到高位一直计算直到计算结束为止。所以在算法中也需要定义一个进位值的变量。 减法与加法类似,当被减数位小于减数位时,会产生一个退位值,即向更高一位去借10,来避免产生负数。若这一位产生了借位,那么高一位的计算中就要减去1再进行计算。所以在算法中也需要定义一个退位值的变量。 乘法的运算在竖式计算中是把乘数逐位的与被乘数相乘,且运算结果随着乘数的位数向左移,最后再全部相加。所以在对单个结果位的处理中要考虑到三个因素:第一个是当前的计算结果;第二个是前一位产生的进位;第三个是之前的计算中在这一位得出的结果。 除法在竖式运算中可以理解为是多次的减法。下图展示了除法算法的流程: 模指数运算 除此之外,还有多精度数的模指数运算,即计算以下式子的值: $$\Large{a^e\space mod\space m} $$ 可采用重复平方乘算法来实现: 算法实现 理解了竖式计算的流程与规则后,就可以使用算法进行实现了。由于课程实验原因,我做了Java和Python两个语言的版本,其中Java里面使用了ArrayList对数进行存储,Python中则使用了列表List进行存储。 Java: // 导入对应模块 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class BigNum { /** * 此方法用于快速创建一个存储有多精度整数的ArrayList对象 * 参数 elements 为整个整数的每一位数字 * 返回 ArrayList<Integer> */ public static ArrayList<Integer> createArrayList(int ... elements) { ArrayList<Integer> list = new ArrayList<Integer>(); for (Integer element : elements) { list.add(element); } return list; } /** * 此方法用于比较两个数的大小。若第一个数大于等于第二个数则返回true,否则返回false * 参数 num1, num2 为要比较的数 * 返回比较结果 boolean */ public static boolean isBigger(ArrayList<Integer> num1, ArrayList<Integer> num2) { if(num1....

Nov. 10, 2019 · 6 min · 1088 words