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

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