应用密码学之从零开始③-密码学的数学基础其一

本文作者：i春秋签约作家——黑照 前文笔者介绍了应用密码学下传统密码、现代密码对称和非对称算法的作用和简介。传统密码原理简单，笔者几乎没有计算，在现代密码学里面的非对称加密没有进行哪怕一位的加密计算过程因为不管是加、乘、异或还是位置变化都难度不大，从本文开始笔者将要介绍部分密码学中的数学原理、数据结构与算法原理。   1）基础运算 加、减、乘、异或和模运算 这个部分除了异或运算以外基本上小学生都知道，其中模运算就是小学学的取余数，因为之前介绍过密码学只进行自然数计算，不涉及小数，所以在模运算中加法、减法畅通无阻，互为逆运算，乘法不一定有乘法逆，但是在有限域中恒有乘法逆。关于有限域的概念即将介绍。 为了方便而不用公式编辑器现在文章做如下定义： 数学上+为加号，-为减号，*为乘号。模运算为a mod b,其中a是被除数，b是除数，结果为余数。A^B为A异或B，A^^B为A的B次方。 例1：计算6-7mod 8和6+7mod 8 6-7mod8 =-1+8mod8=7  6+7mod8=13-8mod8=5   2）位运算 位运算是计算机发展之处就有的运算，分别为和运算、乘运算、非运算、异或、同或等等。因为密码学的原因，笔者只介绍模二运算和异或。 模二运算是不进位的计算，其余原理和普通加减乘无差异。如普通加法中二进制数3为11，加1得4二进制表示为100，这个计算是大家都知道的，但是在模二加法里面11+01=10. 异或运算是密码学里面很常见的计算，计算规则一样没有进位，计算规则为不同的两数（只有0和1）异或为1，相同的两个数异或为0.即1^0=1 1^1=0 0^1=10^0=0 例2 计算1001异或1100 1001 1100 0101   3）软件和硬件 学习过C或者C++的应该知道在C和C++中不同的整数范围能够表示不同的数的大小，而在Java中因为和平台无关，所以数的大小进一步规定死了。如C语言中int的范围是一个字，在16位机上为2字节，32位机为4字节，64位机上为8字节。Java中int不管是多少位机器，只要能运行Java虚拟机，长度永远为32位，4字节。而在加密和破译密码时成本永远是需要考虑的重要因素。 通常来说硬件速度比软件快，GPU的速度比CPU快，而电路级的运算速度比芯片速度还要快。不过软件的特点是容易修改，灵活，几乎没有成本，而硬件的特点是速度快，价格高。 因为密码具有重要价值，所以密码机多为单独使用，国内有使用X86体系的网络安全设备，包括密码机。但实际情况是为了破解价值100万价值的密码哪怕花50万元造一台密码机也是允许的。   4）群、环、域和有限域的概念 PS：关于该节概念较为抽象，虽然一般非数学系不会学习，但是计算机系还会要学习的，概念在离散数学教程里面有。而相传BY复试考过这个概念。不过以下概念不重要，建议直接跳到有限域区域进度阅读。 群表示一个拥有满足封闭性、结合律、有单位元、有逆元 的 二元运算的 代数结构。 封闭性是指运算闭合，元素计算后依旧在集合内。数学定义如下： 给定一个非空集合S 和一个函数F : S X S -> S，则称 F 为在 S 上之二元运算(binaryoperation)，或称(S,F) 具有彩色文字封闭性(closure)。 结合律是指满足加法结合律和乘法结合律。 有单位元是指如集合中有特殊元素e（幺元）满足如下性质： 元素a和幺元发生计算，结果依旧为元素a，如a⊕e= e⊕a =a. 逆元给定任意一个集合中的元素a，存在集合中的另一个元素b，使得a⊙b=b⊙a=e；。 以一个例子结束关于群的概念，如非负有理数组成了一个群，运算符合为加法，其中满足封闭性（任意两个非负有理数的加法依旧是非负有理数），满足加法结合律，有单位元1，有乘法逆元（该数的倒数）。非负有理数及加法运算构成了一个群。 环(Ring)是一类包含两种运算(加法和乘法)的代数系统，是现代代数学十分重要的一类研究对象。 虽然概念比较抽象，刚才群的概念中可以只定义一种代数运算，而环中有两种代数运算并且限定为加法和乘法。 再举个例子，如全体自然数集合Z和加法乘法构成一个环，（自然数数一样有无限多个），其中任意两个整数A和B，进行计算，不管是加还是乘结果必然落在集合Z内。这个集合和运算组成了环。 域的概念：一组元素的集合，以及在集合上的四则运算，构成一个域。其中加法和乘法必须满足交换、结合和分配的规律。加法和乘法具有封闭性，即加法和乘法结果仍然是域中的元素。 有限域是仅含有限多个元素的域。   概念：最简单的有限域是整数环Z 模一个素数p得到的余环Z/(p),由p个元素0,1,…,p-1组成,按模p相加和相乘。 越解释概念越多并且很晦涩，不过密码学用到的代数结构相对简单。 而刚才的有限域的概念是指集合F={a，b，…n}，对F的元素定义了两种运算：“+”和“*”，并满足以下3个条件， ·F1：F的元素关于运算“+”构成交换群，设其单位元素为0。 ·F2：F除{0}以外的元素关于运算“*”构成交换群。即F中元素排除元素0后，关于*法构成交换群。 ·F3：分配律成立，即对于任意元素a，b，c∈F， 恒有 a*(b+c)=(b+c)*a=a*b+a*c p是素数时，可证F{0，1，2，…，p-1}，在modp意义下，关于求和运算“+”，及乘积“*”，构成了域。F域的元素数目有限时称为有限域。 5)不可约多项式 关于数学概念介绍如上，可能大家看的云里雾里，下面举个实际的例子，如在上一章介绍了AES使用有限域进行计算，并且AES中使用模二运算，所以在这里进位就失去了作用，具体怎么起作用呢？见下面的介绍。 该部分引用自知乎，感谢刘博士的回答。 密码学中模数为大质数或者大质数的幂。问题是模8里面4和6怎么办？多项式x如何起作用。 前面讲到了为什么要模质数，但为什么要模质数的幂呢？质数的幂显然不可能是质数啊！举个例子2是一个质数，8是2的幂，但显然8不是一个质数。模数为质数幂时，我们定义的运算⊙并不是整数上的乘法，而是多项式上的乘法。 【不支持外链图片，请上传图片或单独粘贴图片】 设置模数为2，多项式为3阶，满足条件的多项式有8个： 这些多项式中，哪些是不可约多项式呢？ 【不支持外链图片，请上传图片或单独粘贴图片】 【不支持外链图片，请上传图片或单独粘贴图片】 【不支持外链图片，请上传图片或单独粘贴图片】 其它2个多项式，就是不可约多项式了。 找到不可约多项式有什么用呢？我们把不可约多项式设置成“模数”，把各个系数看成集合中的“元素”，把运算⊙定义成多项式乘法，我们就得到了一个群！ 【不支持外链图片，请上传图片或单独粘贴图片】 【不支持外链图片，请上传图片或单独粘贴图片】 6）一次一密及随机序列 在香农博士的那篇文章中除了给出了攻击传统密码的方式之外他也给出了应对办法，使用一次一密进行加密。一次一密的原理很简单，就是采用近似随机的字符串对明文直接进行异或运算，当然解密的一方也需要使用相同的密钥，这样的加密方法被称为是一次一密。在不考虑密钥的安全性的情况下这个方案是很安全的。明文和密钥具有相同的长度，明文中可能具有一定的统计学信息。但是因为密钥是随机生成的，所以明文的每一位被变换成为0或者1的概率也是均等的，所以得到的密文不可能被破解，因为即使有了足够数量的密文样本，每个字符的出现概率都是相等的，每任意个字母组合出现的概率也是相等的。这种方法被称为“一次一密”。 一次一密的加密方案近似流密码，而历史上流密码也被搞定过，这个就不得不提到RC4和wep无线加密方案了。在无线路由器中大家都有一个wep的加密方案，信息安全专家建议大家不要使用这种方式。因为虽然RC4的流密码算法本身没有缺陷，但是因为密钥周期过短，所以即使不知道随机序列的初始状态，在一个周期之后自然也就有了相应的排列组合，并且按照异或加密的原则，两次异或之后就为原文，所以密钥的随机序列很重要。   以上就是传统密码体系中的数学部分，下一部分将进入非对称密码数学基础。再下一章之后开始处理坛友说的量子密码。