计算机网络安全技术第2章.ppt

第二章预备知识 2 1数论基础数论是一门古老的数学分支 以前人们都认为它是完全纯粹的数学 在现实生活中很难找到它的实际应用 自从1976年公开密钥体制诞生以来 现代密码学就和数论有着千丝万缕的联系 因此 我们先简单介绍一下有关的数论基本概念 1 引言我们约定 字母N表示全体自然数集合 Z表示全体整数集合 即N 0 1 2 Z 2 1 0 1 2 定义2 1 1如果存在一个整数k Z使得n kd 则称d整除n 记作d n 其中d称作n的因数 n称作d的倍数 如果不存在这样一个整数k Z使得n kd 则称d不整除n 记作d n 定义2 1 2整数p 1 称为素数 如果除了1和其本身外 p没有任何其他因数 不是素数的整数称为合数 例2 16 2 3 6是合数 2 6 2是6的因数 6是2的倍数 7 1 7 除了1和7之外 没有其他因数 因此7是素数 定理2 1 1 带余数除法 设a b是两个整数 其中b 0 则存在两个整数q r使得a bq r0 r b成立 其中q和r是唯一确定的 设a b是两个整数 既是a的因数又是b的因数的数称为a b的公因数 a和b的所有公因数中最大者 称为a和b的最大公因数 记作gcd a b 既是a的倍数又是b的倍数的数称为a和b的公倍数 a和b的所有公倍数中最小者称为a和b的最小公倍数 记作lcm a b 显然a和b的最大公因数与最小公倍数满足下列等式 lcm a b gcd a b ab如果对两个整数a b有gcd a b 1 则称a与b互素 定理2 1 2设a b N 则存在两个整数u和v使得ua vb gcd a b 定理2 1 3 算术基本定理 任何一个正整数m都存在唯一的因数分解形式m 其中 ei N pi是素数且p1 p2 pn 这个分解形式也称为m的标准分解形式 例2 26 2 3 20 22 5 100 22 52有了算术基本定理后 就可以把任意整数分解为标准形式 从而可以方便地求出两个整数的最大公因数和最小公倍数 设a b是两个整整数 且有标准分解形式 ei fi N 则gcd a b lcd a b 其中 min x y 表示x y中最小者 max x y 表示x y中最大者 2 Euclid算法利用算术基本定理 原则上可以求得任何两个整数的最大公因数 但当两个整数比较大时求他们的标准分解式就非常困难 目前还没有有效的算法 因此求他们的最大公因数也变得非常困难 Euclid算法从另一方面解决了求两个整数的最大公因数的问题 Euclid算法由称为辗转相除法 即带余数除法 有下列不等式 a bq1 r10 r1 bb r1q2 r20 r2 r1 rn 2 rn 1qn rn0 rn rn 1rn 1 rnqn 1 rn 1rn 1 0因为每进行一次带余数的除法 余数至少减1 而b是有限的 所以 最多进行b次带余数的除法 总可以得到一个余数是0的等式 即最后一个等式 而最后一个不为0的余数rn就是我们要求的最大公因数gcd a b 从上面的Euclid算法中可以看出 将r1 a bq1代入第二个等式中 将r2 b r1q2代入到第三个等式中 将rn 1 rn 3 rn 2qn 1代入倒数第二个等式中 就可得到rn关于a b的一个表示式 其中a b的系数分别就是定理2 1 2中的u v 故最后一个不为零的余数就是a b的最大公因数 例2 3求gcd 1694 917 1694 1 917 777917 1 777 140777 5 140 77140 1 77 6377 1 63 1463 4 14 714 2 7 0所以gcd 1694 917 7 进行回代7 63 4 14 63 4 77 63 4 77 5 63 4 77 5 140 77 5 140 9 77 5 140 9 777 5 140 9 777 50 140 9 777 50 917 777 50 917 59 777 50 917 59 1694 917 59 1694 109 917即7 u 1694 v 917其中u 59 v 109 3 同余定义2 1 3假设a和b是两个整数 m是一个正整数 如果m b a 则称a和b对模m同余 记作a b modm 例2 43和1对模2同余 4和1对模3同余 即3 1 mod2 4 1 mod3 定理2 1 4同余的性质设a b c和m是整数 则有 i a a modm ii 若a b modm 则b a modm 若a b modm b c modm 则a c modm 假设a和b被m除 获得整数商和余数 这个余数在0和m 1之间 即a q1m r1和b q2m r2 0 r1 m 1 0 r2 m 1 不难看出 a b modm 当且仅当r1 r2 我们使用符号a modm 来表示a被m除时的余数 即上面的r1 这样a b modm 当且仅当a modm b modm 如果我们用a modm 来代替a 我们说a是被模m约简的 现在我们能够定义模m的算术 Zm是一个集合 0 1 m 1 它有两种运算 和 在Zm中的加法和乘法 除了将结果被模m约减外 恰好象实数加法和乘法 例2 5在Z2种作加法0 0 0 mod2 0 1 1 mod2 1 0 1 mod2 1 1 0 mod2 一般地 在Z2种的加法称为模2加 有时也称为比特异或 用记号 表示 0 0 0 0 1 1 1 0 1 1 1 0 例2 5在Z16作乘法11 1311 13 143 8 16 15所以 11 13 mod16 15定义2 1 4Euler函数是定义在整数上的函数 它在正整数m的值等于1 2 m 1中与m互素的数的个数 记作 m 例2 6m 6 1 2 3 4 5 中与6互素的数为 1 5 共有两个 所以 m 6 2定理2 1 5设正整数的标准分解形式为m 则 m m 1 1 p1 1 1 p2 1 1 pn 例2 7m 6 其标准分解形式为6 2 3所以 6 6 1 1 2 1 1 3 2 定理2 1 6 Euler定理 若a和m互素 则a m 1 modm 设f x 表示多项式 anxn an 1xn 1 a0 其中an 0 ai N i 1 2 n 设n是一个正整数 则f x 0 modm 称作模m的同余式 n称作同余式的次数 n 1称为一次同余式 n 2称为二次同余式 若a是使f a 0 modm 成立的一个整数 则x a modm 叫做同余式的一个解 定理2 1 7 中国剩余定理 设m1 m2 mk 是k个两两互素的整数 m m1m1 mk Mi m mi i 1 2 k 则同余方程组x b1 modm1 x b2 modm2 x bk modmk 有解x M 1M1b1 M 2M2b2 M kMkbk modm 其中M iMi 1 modmi i 1 2 k由此定理可以看出 M i可以利用前面介绍的Euclid算法求出 4 二次剩余设gcd a m 1 若同余式x2 a modm 有解 则a称作模m的二次剩余 否则称作模m的非二次剩余 例2 9考虑下列同余式x2 1 mod5 x2 2 mod5 x2 3 mod5 x2 4 mod5 不难发现 x 1 x 4满足x2 1 mod5 x 2 x 3满足x2 4 mod5 不存在整数x满足x2 2 mod5 x2 3 mod5 所以1 4是模5的二次剩余 而2 3是模5的非二次剩余 定理2 1 8若gcd a p 1 则a是模p的二次剩余的充要条件为ap 1 2 1 modp a是模p的非二次剩余的充要条件为ap 1 2 1 modp 定理2 1 9两个模p的二次剩余的乘积或两个模p的非二次剩余的乘积 还是模p的二次剩余 一个模p的二次剩余与另一个模p的非二次剩余的乘积是非二次剩余 定义2 1 5Legendre符号 是一个对于给定素数p定义在一切整数a上的函数 它的值规定如下 例2 10 定理2 1 10legendre符号的性质a b 如果a b modp 则c d e 设p q均为奇素数 p q 则 定义2 1 6设m ei 0是一个奇正整数 u是与m互素的整数 则Jacobi符号定义为 u m 其中 是Legendre符号 定理2 1 11Jacobi符号的性质1 u m u m m 2 uv m u m v m 3 u mn u n u m 4 1 m 1当且仅当m 1 mod4 5 2 m 1当且仅当m 1 1 mod8 6 设m n都是奇数 且gcd m n 1则 1 m 1 n 1 4 2 2信息论基础Shannon信息论是密码学的理论基础 本节介绍Shannon信息论的基本概念 与密码学有关的概念将在后面介绍 1 熵的概念熵是信息的测度或不确定性 它是作为概率分布的一个函数来计算的 假设有一个随机变量x 它根据概率分布p x 在一个有限集合上取值 根据分布p x 发生的事件来获得的信息是什么 等价地 如果一个事件还没有发生 有关这个结果的不确定性是多少 这个量称为x的熵并用H x 表示 定义2 2 1离散随机变量x的熵H x 定义为H x P x Log2P x 其中 P x 表示随机变量x的概率分布 例2 11设离散随机变量x取 0 1 两个值 其中P x 0 P x 1 1 2 则H x 1P x 0 Log2P x 0 P x 1 Log2P x 1 1 2 1 1 2 1 1下面我们来定义联合熵和条件熵 定义2 2 2两个离散随机变量 x y 的联合熵定义为H xy 1P xy Log2P xy 其中 P xy 表示离散随机变量 x y 的联合概率分布 类似地 可以定义n个离散随机变量 x1 x2 xn 的联合熵 定义2 2 3两个离散随机变量 x y 的条件熵定义为H x y P xy Log2P x y 其中 P xy 表示离散随机变量 x y 的联合概率分布 P x y 表示两离散随机变量的条件分布 利用联合熵与条件熵的定义 容易证明定理2 2 1H xy H x H y x 2 互信息互信息是一个事件含有另一个事件的信息的度量 或者是已知另外一个事件 称作B 的情况下 事件 称作A 不确定性的减少 定义2 2 4两个离散随机变量x和y 它具有概率分布P x 和P y 和联合概率分布密度P xy 则互信息定义为I x y 从互信息的定义可以看出 如果随机变量x和y统计独立 即y中不含x的任何信息 则I x y 0 互信息具有对称性 这就是定理2 2 2I x y H x H y x H y H x y I y x 2 33计算复杂度简介计算复杂度理论是计算机科学理论的一个分支 它提供了一种分析不同密码技术和算法保密强度的方法 它对密码算法和技术进行比较 然后确定它们的安全性 现代密码学的许多理论和技术是建立在某些计算问题的复杂性基础之上的 1 算法复杂度一个算法的计算复杂度用符号 O 来表示 计算复杂度的数量级是这种类型的函数 即当n变大时 增长最快的函数 n是输入尺寸 所有常数和较低阶形式的函数忽略不计 例如 一个所给的算法复杂度是5n2 8n 10 那么 其计算复杂性表示为O n2 通常 算法按其事件和空间的复杂性进行分类 如果一个算法的复杂性是不依赖于n O 1 那么 它是 常数级的 如果它的复杂性是随n线性增长的 那么它是 线性的 O随n增长的其他一些算法也称为 二次方的 三次方的 等等 所有这些算法都是 多项式的 他们的复杂性是O nt 这里t是一个常数 有一个多项式的时间复杂性的算法簇称之为多项式时间算法 复杂性是O tf n 的算法 被称为是 指数的 这里t是一个常数 f n 是n的多项式函数 2 问题的分类复杂性理论按照解决问题的算法对问题进行分类 能够用多项式时间算法解决的问题称之为易解决的 不能在多项式时间内解决的问题称之为难处理的 难处理的问题有时也称为难解决的 定义2 3 1P类问题 在多项式时间内可以解决的问题 NP类问题 多项式时间内可以验证的问题 由于在多项式时间内可以解决的问题 在多项时间内也完全可以验证其正确性 因此一般有P NP 但现在还不知道是否有 P NP 成立 在NP问题中有些特殊的问题能够被证明与此类问题中的任何问题一样困难 这类问题称之为NP 完全类问题 有人已经编辑了一份NP 完全类问题的目录 下面将列出几个例子 3 几个例子1 整数分解问题前面介绍了算术基本定理 根据这个定理 任何一个正整数都可以分解成标准形式m pi是常数 ei N当m较小时 这个问题不太困难 例如6 2 3 100 22 52但当m较大时 这个问题就变得非常困难了 例如你能立即指出整数8616460789的标准分解形式吗 特别是当m达到几百位时 根据现有的算法用最快的计算机也不行 但反过来 如果给出一个整数的标准分解时 则可以很快验证这个标准分解式是否是这个整数的标准分解式了 例2 12861646079的标准分解式为861646079 89681 96079我们能立即验证这个分解式的正确性 2 背包问题背包问题是这样一个问题 已知长度为k的圆形背包及长度分别为a1 a2 an的n个圆形物品 假定这些物品的半径和背包的半径相同 要求从n个物品中选出若干个正好装满这个背包 把背包问题抽