第二讲数学基础和流密码(3,4章)

北京科技大学数理学院卫宏儒Weihr168,第二讲数学基础和流密码,一、数学基础,1、整数的带余除法,2、整除,3、最大公约数,4、素数和合数,5、同余,6、几个重要定理,7、离散对数,8、素性检验,9、有限域,二、流密码,公钥密码体制的思想是在1976年由Diffie和Hellman提出的。然后在1977年由Rivest,Shamir和Adleman发明了著名的RSA密码体制，将在第六章中研究。此后，几个公钥密码体制被提出，其安全性依赖于不同的计算问题。其中，最著名的是RSA密码体制（及其变种），其安全性基于分解大整数的困难性；ElGamal密码体制（及其变种，例如：椭圆曲线密码体制），其安全性基于离散对数问题。我们在第六章中讨论RSA密码体制和它的变种、ElGamal密码体制。在Diffie和Hellman之前，公钥密码学的思想已经由JamesEllis在1970年1月的一篇题为“非隐秘加密的可能性”的文章中（短语“非秘密加密”即是公钥密码学）提出。JamesEllis是电子通讯安全小组（CESG）的成员，这个小组是英国政府通讯司令部（GCHQ）的一个特别部门。这篇文章没有在公共文献中发表，而是在1997年12月由GCHQ正式解密的五篇文章中的一篇。在这五篇文章中，还有一篇由CliffordCocks在1973年发表的题为“关于非秘密加密的注记”的文章，其中描述的公钥密码体制跟RSA密码体制基本一致。,一、数学基本知识1、整数的带余除法整数对于加法、减法、乘法运算都是封闭的，即任意两个整数的和、差、积仍然是整数。但是对除法运算不再是封闭的，例如，4除以3就不是整数了。,2、整除,3、最大公约数,最大公约数,最大公约数,4、素数和合数,定义：大于1而且只能被1和自身整除的自然数，称为素数。大于1的不是素数的自然数，称为合数。,关于素数的几条性质,5、同余,定义：是一个大于1的自然数，若是整数且整除，则称整数和模是同余的，记作。,例1任何两个奇数模都是同余的，任何两个偶数模也都是同余的。,例2和模是同余的，和模也是同余的。即和。,同余性质,交换律结合律有单位元分配律可约律逆元：,同余性质（续）,性质：（1）若，则,同余性质（续）,（2）若：则：证明：由条件有所以即,同余性质（续）,同余类,定理1：整数模的同余关系是等价关系，即：（1）反身性；（2）对称性；（3）传递性；,同余类（续）,同余类（续）,定理2：对于模的同余类，有下列性质：,例题1、对于模5的同余类，有2、模5的同余类的加法和乘法运算表。,6、几个重要定理,7、离散对数,通过对对数概念的理解引入指标的概念。,离散对数定义,、素性检验,素性检验的具体方法：,1、利用p64的算法（小整数）,2、Solovag-Strassen概率检验法,3、小素数迭代来产生一个大素数,4、Rabin-Miller方法,Rabin-Miller算法,9、有限域,二、流密码,六、线性反馈移位寄存器序列,1、线性反馈移位寄存序列,2、线性反馈移位寄存器序列的特征多项式,3、m序列的伪随机性和m序列密码的破译,1）m序列的伪随机性,2）m序列密码的破译,伴侣矩阵,破译过程,因为产生m序列的线性移位寄存器的连续n个状态是线性无关的，所以X矩阵是满秩矩阵，它存在逆矩阵，于是,只要求出矩阵M，就可以确定出特征多项式f(x)，从而确定出线性移位寄存器的结构。,例4-2-3,七、非线性序列密码,1、非线性反馈移位寄存器序列,2、非线性前馈序列,3、基于LFSR的流密码生成器,1）Geffe生成器,2）Pless生成器,3）钟控生成器,4、流密码算法-RC4算法,RC4是一个密钥长度可