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： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 // 导入对应模块 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.size() < num2.size()) return false; else if(num1.size() > num2.size()) return true; else if(num1.size() == num2.size()){ for (int i = 0; i < num1.size(); i++){ if(num1.get(i)<num2.get(i)) return false; else if(num1.get(i)>num2.get(i)) return true; } } return true; } /** * 此方法用于实现两个多精度整数相加 * 参数 num1, num2 为两个加数 * 返回存储有运算结果的 ArrayList<Integer> */ public static ArrayList<Integer> bigPlus (ArrayList<Integer> num1, ArrayList<Integer> num2){ // 判断特殊情况 if(num1.size() < num2.size()){ ArrayList<Integer> tmp = num1; num1 = num2; num2 = tmp; } if(num1.isEmpty()) return num2; if(num2.isEmpty()) return num1; //数组索引反向，使数字的位数与索引对齐 Collections.reverse(num1); Collections.reverse(num2); ArrayList result = new ArrayList(num1.size()+1); //创建结果对象 int c = 0; //进位值 for (int i = 0; i < num2.size(); i++){ //判断是否进位 if (num1.get(i) + num2.get(i) + c < 10){ result.add(num1.get(i) + num2.get(i) + c); c = 0; }else{ result.add(num1.get(i) + num2.get(i) + c - 10); c = 1; } } if(num1.size() == num2.size()) result.add(c); //若两数位数相等，则最高位直接为进位值 else{ //若两数位数不相等，把位数大的数的后续位直接与进位值相加，添加到结果中 result.add(c+num1.get(num2.size())); for(int i : num1.subList(num2.size()+1,num1.size())){ result.add(i); } } //把所有ArrayList的索引反向至正常状态 Collections.reverse(result); Collections.reverse(num1); Collections.reverse(num2); //消除前导0 if((int)result.get(0) == 0) { result.remove(0); } return result; } /** * 此方法用于实现两个多精度整数相减，若被减数小于减数则自动将两者调换后相减 * 参数 num1 为被减数, num2 为减数 * 返回存储有运算结果的 ArrayList<Integer> */ public static ArrayList<Integer> bigSub (ArrayList<Integer> num1, ArrayList<Integer> num2){ // 判断特殊情况 if(num1 == num2 || (num1.isEmpty() && num2.isEmpty())) return createArrayList(0); if(num1.isEmpty()) return num2; if(num2.isEmpty()) return num1; if(!BigNum.isBigger(num1,num2)){ System.out.println("检测到减数大于被减数，已自动将减数与被减数交换"); ArrayList<Integer> tmp = num1; num1 = num2; num2 = tmp; } //数组索引反向，使数字的位数与索引对齐 Collections.reverse(num1); Collections.reverse(num2); ArrayList result = new ArrayList(num1.size()); //创建结果对象 int c = 0; //借位值 for (int i = 0; i<num2.size();i++){ //判断是否借位 if(num1.get(i) - num2.get(i) + c >= 0){ result.add(num1.get(i) - num2.get(i) + c); c = 0; }else{ result.add(num1.get(i) - num2.get(i) + c + 10); c = -1; } } //若两数位数不相等，把位数大的数的后续位直接与进位值相加，添加到结果中 if(num1.size() > num2.size()){ result.add(c+num1.get(num2.size())); for(int i : num1.subList(num2.size()+1,num1.size())) result.add(i); } //把所有ArrayList的索引反向至正常状态 Collections.reverse(result); Collections.reverse(num1); Collections.reverse(num2); //消除前导0 if((int)result.get(0) == 0) { result.remove(0); } return result; } /** * 此方法用于实现两个多精度整数相乘 * 参数 num1, num2 为两个乘数 * 返回存储有运算结果的 ArrayList<Integer> */ public static ArrayList<Integer> bigMult (ArrayList<Integer> num1, ArrayList<Integer> num2){ //数组索引反向，使数字的位数与索引对齐 if(num1.hashCode()==num2.hashCode()){ Collections.reverse(num1); }else{ Collections.reverse(num1); Collections.reverse(num2); } ArrayList result = new ArrayList(num1.size()+num2.size()); //创建结果对象 int uv = 0; //乘法临时值 for (int i = 0; i<num1.size()+num2.size()+1; i++) result.add(0); //结果所有位置为0 for (int i = 0; i<num1.size(); i++){ int c = 0; //进位值 for (int j = 0; j<num2.size(); j++){ uv = (int)result.get(i+j) + num1.get(i) * num2.get(j) + c; //按手工计算的方式进行逐位的运算 result.set(i+j, uv%10); c = uv/10; } result.set(i+num2.size(), uv/10); } //把所有ArrayList的索引反向至正常状态 Collections.reverse(result); if(num1.hashCode()==num2.hashCode()){ Collections.reverse(num1); }else{ Collections.reverse(num1); Collections.reverse(num2); } //消除前导0 while((int)result.get(0) == 0) { result.remove(0); } return result; } /** * 此方法用于实现两个多精度整数相除 * 参数 num1 为被除数, num2 为除数 * 返回存储有运算结果的 List<ArrayList<Integer>>, List 中第一项为商，第二项为余数 * @return */ public static List bigDiv (ArrayList<Integer> num1, ArrayList<Integer> num2){ if(num1 == num2) { //若两数相等，返回商为1，余数为0 return Arrays.asList(createArrayList(1),createArrayList(0)); } if(num2.get(0) == 0 && num2.size() == 1){ //若除数为0，返回-1 System.out.println("除数不得为0"); return Arrays.asList(createArrayList(-1),createArrayList(0)); } if(!BigNum.isBigger(num1,num2)){ //若除数大于被除数，则商为0，余数为被除数的值 return Arrays.asList(createArrayList(0),num1); } while(num1.get(0)==0){ //消除产生的前导0 num1.remove(0); } while(num2.get(0)==0){ //消除产生的前导0 num2.remove(0); } //创建并初始化结果对象 ArrayList result = new ArrayList(); for (int i=0;i<num1.size()-num2.size()+1;i++){ result.add(i,0); } //为除数扩充0至位数与被除数相等，并计算扩大的倍数 ArrayList num2_duiqi = (ArrayList) num2.clone(); int mult_times = 0; //扩大倍数 int times = 0; //除法结果 while(num2_duiqi.size()!=num1.size()){ num2_duiqi.add(0); mult_times++; } while(true) { while (BigNum.isBigger(num1, num2_duiqi)) { //逐次相减，并在结果中乘以对应的倍数 num1 = BigNum.bigSub(num1, num2_duiqi); if(num1.size()!=0){ while(num1.get(0)==0){ //消除产生的前导0 num1.remove(0); if(num1.isEmpty()){ break; } } } times++; } result.set(mult_times, times); //结果中填入结果 times = 0; //除法结果重置 //除完一轮重新对齐，并修改扩大的倍数 if ((int) num2_duiqi.get(num2_duiqi.size() - 1) == 0 && num2_duiqi.size() > num2.size()){ num2_duiqi.remove(num2_duiqi.size() - 1); mult_times--; } else{ //除到末位后，将结果的索引反向 Collections.reverse(result); break; } } //返回结果 if(num1.size()==0){ return Arrays.asList(result,createArrayList(0)); } return Arrays.asList(result,num1); } public static ArrayList bigPow (ArrayList<Integer> a, ArrayList<Integer> k, ArrayList<Integer> m){ ArrayList A = (ArrayList)a.clone(); //A=a ArrayList b = createArrayList(1); //令b=1 if(k.isEmpty() || (k.size()==1 && k.get(0)==0)) return b; //如果k=0，则返回b List kk; ArrayList<Integer> k1 = (ArrayList<Integer>)k.clone(); ArrayList k2 = new ArrayList(); while(!(k1.size()==1&&k1.get(0)==0)){ //将k转换为二进制，结果为k2 kk = BigNum.bigDiv(k1,createArrayList(2)); k1 = (ArrayList<Integer>) kk.get(0); k2.add(((ArrayList) kk.get(1)).get(0)); } if((int)k2.get(0)==1){ //如果k0=1，则b=a b= (ArrayList) a.clone(); } for(int i = 1;i<k2.size();i++){ A = (ArrayList) BigNum.bigDiv(BigNum.bigMult(A,A), m).get(1); if((int)k2.get(i)==1){ b = (ArrayList) BigNum.bigDiv(BigNum.bigMult(A,b), m).get(1); } } return b; } } Python（注释可参考Java版本）： ...