Algorithm

简介 分组密码属于对称密码的一种，其特点是加解密都是对明文/密文进行分组后逐组进行加解密。通俗讲就是将明文分块，然后分块加密，解密同理。 分组密码的基本原理： 代换：明文分组到密文分组的可逆变换 扩散：将明文的统计特性散布到密文中去，使得明文的每一位影响密文中多位的值 混淆：使密文和密钥之间的统计关系变得尽可能复杂，使攻击者无法得到密钥，通常使用复杂的代换算法实现 分组密码体制基本上都是基于乘积（由一系列代换和置换构成）和迭代来构造的。常见的分组密码结构有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$变为：...

算法介绍 多项式的运算可以说比之前的多精度数运算还要简单一点，因为多项式的加减只能存在于同次数的项之间，所以不需要考虑加减法里面的进位退位问题，这也就使得乘除法简单了很多。 加减法的原理就没什么好说的了，乘除法都是基于多精度数的算法修改的，存储多项式也使用了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))$ ，所以可通过查表也很容易求出元素的逆元。...

多精度数指的是位数超过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....