信息安全原理与技术ch02-数学基础.ppt

信息安全原理与技术 郭亚军宋建华李莉清华大学出版社 2020 2 20 Ch2 数学基础 2 第2章数学基础 主要知识点 数论 代数基础 计算复杂性理论 单向函数 2020 2 20 Ch2 数学基础 3 因子 设Z表示全体整数所构成的集合 定义2 1设a b Z a 0 c Z 使得b ac 则称a整除b 并称a是b的因子或者约数 b是a的倍数 记为a b 定理2 1 带余除法 设a b Z b 1 则存在唯一的整数q和r 使得a qb r 0 r b q称a除以b所得的商 r称为a除以b所得的最小非负剩余 定义2 2设a b Z a b不全为0 如果c a且c b 则称c为a和b的公因子 特别地 我们把a和b的所有公因子中最大的 称为a和b的最大公因子 记为gcd a b 或者 a b 2020 2 20 Ch2 数学基础 4 计算两个数的最大公因子的最容易的方法是用欧几里德 Euclid 算法定理2 3 欧几里德算法 给定整数a和b 且b 0 重复使用带余除法 即每次的余数为除数去除上一次的除数 直到余数为0 这样可以得到下面一组方程 a bq1 r1 0 r1 b b r1q2 r2 0 r2 r1 r1 r2q3 r3 0 r3 r2 rj 1 rjqj 1最后一个不为0的余数rj就是a和b的最大公因子 2020 2 20 Ch2 数学基础 5 例2 1求gcd 1970 1066 用欧几里德算法的计算过程如下 1970 1 1066 9041066 1 904 162904 5 162 94162 1 94 6894 1 68 2668 2 26 1626 1 16 1016 1 10 610 1 6 46 1 4 24 2 2 0因此gcd 1970 1066 2 2020 2 20 Ch2 数学基础 6 素数 定义2 4设p Z p 2 如果p的正因子只有1和p 则称p为素数 否则为合数若正整数a有一因子b 而b又是素数 则称b为a的素因子如果整数a与整数b的最大公因子是1 即gcd a b 1 则称a与b互为素数 简称互素设 m 为小于或等于m且与m互素的正整数个数 则称其为欧拉 Euler 函数 2020 2 20 Ch2 数学基础 7 同余 定义2 8两个整数a b分别被m除 如果所得的余数相同 则称a与b对模m是同余的 记为a b modm 正整数m称为模数同余具有下面的性质 1 若a b modm 则则m b a 反过来 若m b a 则a b modm 2 如果a km b k为整数 则a b modm 3 每个整数恰与0 1 m 1这m个整数中的某一个对模m同余 4 同余关系是一种等价关系 5 a b modm 当且仅当amodm bmodm 2020 2 20 Ch2 数学基础 8 定理2 8 乘法消去律 对于ab ac modm 来说 若gcd a m 1则b c modm 定理2 9 加法消去律 如果a b a c modm 则b c modm 加法消去律是没有条件 但乘法消去律的条件是gcd a m 1 即a和m互素例如6 3 6 7 2mod8 但3 7mod8不成立 2020 2 20 Ch2 数学基础 9 模运算 求余运算称为模运算 下面是模运算的一些性质 1 a b modm amodm bmodm modm 2 a b modm amodm bmodm modm 3 a b modm amodm bmodm modm 4 a b c modm a b modm a c modm modm例如11mod8 3 15mod8 7 那么 11mod8 15mod8 mod8 3 7 mod8 2 11 15 mod8 26mod8 2在模运算中 加法单位元是0 0 a modm amodm乘法单位元是1 1 a modm amodm 2020 2 20 Ch2 数学基础 10 定义2 13对a Zm 存在b Zm 使得a b 0 modm 则b是a的加法逆元 记b a 定义2 14对a Zm 存在b Zm 使得a b 1 modm 则称b为a的乘法逆元 加法一定存在逆元 乘法不一定存在逆元 在密码学特别是非对称密码体制中 常常需要求模逆元 求模逆元就是求乘法逆元 即寻找一个x 使得a x 1modm成立求模逆元问题很困难 有时有结果 有时没有结果利用扩展欧几里德算法能够计算出模逆元 2020 2 20 Ch2 数学基础 11 模8运算的例子 模8的加法和乘法运算与普通运算一样 只是将所得的值是去模8后的余数 2020 2 20 Ch2 数学基础 12 2020 2 20 Ch2 数学基础 13 模8的加法逆元和乘法逆元 对每一个x都有一个对应的y 使得x y 0mod8 则y是x的加法逆元 如对2 有6 使得2 6 0mod8 那么6是2的加法逆元如果对x 存在y 使得x y 1mod8 则y为x的乘法逆元 如3 3 1mod8 因此3的乘法逆元是3 2020 2 20 Ch2 数学基础 14 快速指数模运算 在非对称密码体制 公钥密码体制 中常常涉及指数模运算 如计算73327mod37一种方法是利用前面介绍的模运算性质 a b modm amodm bmodm modm 将指数模运算可以看做是多次重复乘法 并且在计算中间结果时就取模例如 计算117mod13 可以按照下面的思路 112 121 4mod13114 112 2 42mod13 3mod13117 11 112 114 11 4 3mod13 132mod13 2mod13 2020 2 20 Ch2 数学基础 15 快速求memodn算法一 1 a e b m c 1 其中a b c为三大整数寄存器 2 如果a 0 则输出结果c即为所求的模n的大整数次幂 3 如果a是奇数 转第 5 步 4 a a 2 b b b modn 转第 3 步 5 a a 1 c c b modn 转第 2 步 2020 2 20 Ch2 数学基础 16 计算3037mod77 2020 2 20 Ch2 数学基础 17 费马定理和欧拉定理 费马定理和欧拉定理在公钥密码体制中占非常重要的地位定理2 13 费马定理Format 若p是素数 且a是正整数 且gcd a p 1 则 ap 1 1 modp 定理2 14 欧拉定理 对于任何互素的两个整数a和n 有a n 1modn 2020 2 20 Ch2 数学基础 18 素性测试 很多密码算法需要随机选择一个或者多个非常大的素数一般做法是先生成大的随机整数 然后确定该大数是否是素数目前没有还没有简单有效的方法确定一个大数是否是素数定理2 15 如果p为大于2的素数 则方程x2 1 modp 的解只有x 1和x 1 定理2 15的逆否命题是 如果方程x2 1 modp 有一解 那么p不是素数 2020 2 20 Ch2 数学基础 19 Miller Rabin素性概率检验算法 WITNESS a n 1 将 n 1 表示为二进制形式bkbk 1 b0 2 d 1fori kdownto0do x d d d d modn if d 1 x 1 x n 1 thenreturnTRUE ifbi 1thend d a modn ifd 1thenreturnTRUE elsereturnFALSE 2020 2 20 Ch2 数学基础 20 算法有两个输入 n是待检验的数 a是小于n的整数 如果算法的返回值为TRUE 则n肯定不是素数 如果返回值为FALSE 则n有可能是素数 for循环后 有d an 1modn 由费马定理可知 若n为素数 则d为1 因此若d 1 则n不是素数 所以返回TRUE 因为n 1 1modn 所以x 1 x n 1 表示x2 1 modp 有不在 1 1 中的根 因此n不为素数 返回TRUE 2020 2 20 Ch2 数学基础 21 离散对数 离散对数是许多公钥算法的基础本原根这一个重要概念假设gcd a n 1 如果m是使am 1modn成立的最小正整数 则称它是a对模n的指数 记为Ordna若Ordna n 则称a是模n的本原根 primitiveroot 也称生成元 2020 2 20 Ch2 数学基础 22 求模7和模15的本原根 对于模7而言 满足gcd a n 1的a是 1 2 3 4 5 6 将它们的指数列表如下 从上表可以看到 当a是3和5时 Ord7a 7 因此 3和5是模7的本原根 2020 2 20 Ch2 数学基础 23 对于模15而言 满足gcd a n 1的a是 1 2 4 7 8 11 13 14 将它们的指数列表如下 上表中不存在一个a 使Ord15a 15 所以模15没有本原根定理2 18模m的本原根存在的必要条件是m 2 4 pa 或者2pa 此处p是奇素数 2020 2 20 Ch2 数学基础 24 本原根的测试 通常找出一个本原根不是一件容易的问题如果知道p 1的因子 它就变得容易测试方法 令q1 q2 qn是p 1的素因子 对于所有的q1 q2 qn 计算a p 1 q modp 如果对某个q的某个值其结果为1 那么a不是一个本原根 如果对某个q的所有值其结果都不为1 那么a是一个本原根 2020 2 20 Ch2 数学基础 25 例2 9假设p 11 检验2和3是否是一个本原根 解 当p 11时 p 1 10 p 1有两个素因子2和5 现测试2是否是一个本原根 2 10 1 5 mod11 42 10 1 2 mod11 10计算结果没有1 所以2是本根原 测试3是否是本根原3 10 1 5 mod11 93 10 1 2 mod11 1所以3不是本根原 2020 2 20 Ch2 数学基础 26 离散对数 模运算用于指数计算可以表示为axmodn 我们称为模指数运算模指数运算的逆问题就是找出一个数的离散对数 即求解x 使得ax bmodn定义2 17 离散对数 对于一个整数b和素数n的一个本原根a 可以找到唯一的指数x 使得b axmodn 其中0 x n 1 指数x称为b的以a为基数的模n的离散对数 2020 2 20 Ch2 数学基础 27 代数基础 有限域在现代密码学中的地位越来越重要本节先简单介绍群 环和域等概念 然后详细介绍有限域中的运算 2020 2 20 Ch2 数学基础 28 群 群G有时记做 G 是定义了一个二元运算的集合 这个二元运算可以表示为 它具有一般性 可以指加法 乘法或者其他的数学运算 G中每一个序偶 a b 通过运算生成G中的元素 a b 并满足以下公理 Al 封闭性 如果a和b都属于G 则a b也属于G A2 结合律 对于G中任意元素a b c 都有a b c a b c成立 A3 单位元 G中存在一个元素e 对于G中任意元素a 都有a e e a a成立 A4 逆元 对于G中任意元素a G中都存在一个元素a 使得式a a a a e成立 如果一个群的元素个数是有限的 则该群称为有限群 并且群的阶等于群中元素的个数 否则 称该群为无限群 一个群如果还满足以下条件 则称为交换群 或称Able群 A5 交换律 对于G中任意的元素a b 都有 a b b a成立 2020 2 20 Ch2 数学基础 29 环 环R有时记为 R 是一个有两个二元运算的集合 这两个二元运算分别称为加法和乘法 且对于R中的任意元素a b c 满足以下公理 Al A5 R关于加法是一个交换群 对于此种情况下的加法群 我们用0表示其单位元 a表示a的逆元 M1 乘法的封闭性 如果a和b都属于R 则ab也属于R M2 乘法的结合律 对于R中任意元素a b c 有a bc ab c成立 M3 分配律 对于R中任意元素a b c 式a b c ab ac和式 a b c ac bc总成立 环如果还满足一下条件则成为交换环 M4 乘法的交换律 对于R中的任意元素a b 有ab ba成立 在交换环的基础上 满足以下公理的环叫做整环 M5 乘法单位元 在R中存在元素1 使得对于R中的任意元素a 有al 1a a成立 M6 无零因子 如果有R中元素a b 且ab 0 则必有a 0或b 0 2020 2 20 Ch2 数学基础 30 域 域F有时记为 F 是有两个二元运算的集合 这两个二元运算分别称为加法和乘法 且对于F中的任意元素a b c 满足以下公理 Al M6 F是一个整环 也就是说F满足从Al到A5以及从M1到M6的所有原则 M7 乘法逆元 对于F中的任意元素a 除0以外 F中都存在一个元素a 1 使得式aa 1 a 1 a 1成立 2020 2 20 Ch2 数学基础 31 根据域中元素的个数是不是有限 把域划分成有限域和无限域无限域在密码学中没有特别的意义 然而有限域却在许多密码编码学中扮演着重要的角色 定义2 19 有限域中元素的个数称为有限域的阶 定理2 19 有限域的阶必为素数p的幂pn n为正整数定理2 20 对任意素数p和正整数n 存在pn阶的有限域 记为GF pn 当时n 1 有限域GF p 也称素域 在密码学中 最常用的域一般是素域GF p 或者阶为2m的GF 2m 域 2020 2 20 Ch2 数学基础 32 有限域GF p 给定一个素数p 元素个数为p的有限域GF p 定义为整数 0 1 p 1 的集合Zp 其运算为模p的算术运算最简单的有限域是GF 2 该域元素的个数是2 它们分别是0和1 在GF 2 上的加运算等价于异或运算 乘等价于逻辑与运算表2 5是在有限域GF 7 中的算术运算 这是一个阶为7 采用模7运算 它满足域的所有性质 需要注意的是 前面介绍的表2 1只是表示集合Z8中模8运算 其中的非零整数不一定有乘法逆元 因此不是域 2020 2 20 Ch2 数学基础 33 模7加法 2020 2 20 Ch2 数学基础 34 模7乘法 2020 2 20 Ch2 数学基础 35 模7的加法逆元和乘法逆元 2020 2 20 Ch2 数学基础 36 域上多项式 若ai 0 称n为该多项式的次数 并称an为首项系数 首项系数为1的多项式称为首1多项式 域F上x多项式全体集合记为F x 多项式运算包括加法 减法 乘法和除法 2020 2 20 Ch2 数学基础 37 在域F上的多项式加法运算定义为乘法运算定义为 2020 2 20 Ch2 数学基础 38 定理2 21设a x 和b x 是域F上的多项式 且b x 0 则存在唯一的一对多项式 使其中q x 为商式 r x 为余式 r x 的次数小于b x 的次数多项式除法具有与普通除法一样的长除法如整数运算类似 我们可以将余式r x 写成a x modb x 称为a x 模b x b x 称为模多项式 2020 2 20 Ch2 数学基础 39 定义2 21设a x 和b x 是域F上的多项式 1 设b x 0 若存在q x 使 则称b x 是a x 的因式或者除式 b x 整除a x 记为b x a x 2 设a x 和b x 不全为0 a x 和b x 的次数最高的首1公因式称为它们的最高公因式 记为gcd a x b x 若gcd a x b x 1 称a x 和b x 互素 3 若存在次数大于或者等于1的q x 和b x 使a x q x b x 则称a x 为可约多项式 否则称a x 为不可约多项式 也称既约多项式 2020 2 20 Ch2 数学基础 40 例如 GF 2 上的多项式是可约多项式 因为 而多项式则是不可约多项式 因为它没有一个因式 2020 2 20 Ch2 数学基础 41 有限域GF 2n 为pn模的模运算不一定能产生域用不可约多项式可以构造一个域对于F x 中的每个不可约多项式p x 可以构造一个域F x p x 设p x 是F x 中n次不可约多项式 令F x p x 为F x 中所有次数小于n的多项式集合其中ai F 即在集合 0 1 p 1 上取值 2020 2 20 Ch2 数学基础 42 定义F x p x 上的二元运算加法和乘法运算如下 域F x p x 中的单位元和零元分别是F中的单位元和零元上面的运算定义可以看到 1 该运算遵循基本代数规则中的普通多项式运算规则 2 系数运算以p模 即遵循有限域上Zp的运算规则 3 乘法运算是两个多项式相乘结果再模一个不可约多项式p x 如果两个多项式相乘结果是次数大于n 1的多项式 它将除以次数为n的不可约多项式p x 并取余 2020 2 20 Ch2 数学基础 43 定理2 22是域 当且仅当p x 是F上的不可约多项式 其中F是有限域 特别地 在GF 2n 中 F x p x 中所有次数小于n的多项式表示为 系数ai是二进制数 该多项式可以由它的n个二进制系数唯一地表示 因此GF 2n 中的每个多项式都可以表示成一个n位的二进制整数 2020 2 20 Ch2 数学基础 44 高级加密标准中的有限域GF 28 上运算 不可约多项式为假设多项式加法运算过程为 乘法运算过程为 2020 2 20 Ch2 数学基础 45 由于a x 和b x 相乘的多项式次数大于n 将它们相乘结果再除不可约多项式p x 可得商为x5 x3 余数为x7 x6 1 因此用十六进制表示为 57 83 C1 用二进制表示为 11000001 说明 在上面的十六进制表示中 是用一个十六进制字符表示4位二进制数 一个字节的二进制数用括号括起来的两个十六进制字符表示 2020 2 20 Ch2 数学基础 46 从上面的例子我们也可以发现 多项式加法是将对应的系数分别相加GF 2n 中两个多项式加法和减法等同于按位异或 需要注意的是加法不进位 减法不借位 2020 2 20 Ch2 数学基础 47 计算复杂性理论 计算复杂性理论提供了一种分析不同密码技术和算法的计算复杂性方法计算复杂性理论给出了求解一个问题的计算是 容易 还是 困难 的确切定义 这有助于确定一个密码算法的安全强度破译一个密码算法所花费的时间或者空间代价超出了密码本身所保密内容的价值 破译就没有意义计算机复杂性理论涉及算法的复杂性和问题的复杂性 2020 2 20 Ch2 数学基础 48 问题的复杂性 一个问题的复杂性是由可解这个问题的算法的计算复杂性所决定可解一个问题的算法可能有多个 在理论上定义一个问题的计算复杂性为可解该问题的最有效算法的计算复杂性计算复杂性粗分为三类 即P类 确定性多项式时间可解类 NP类 不确定性多项式时间可解类 和NP完全类 记为NPC 不确定性多项式时间可解完全类 P类问题称为易解问题 NP类问题称为难解问题 NPC问题称为困难问题 由于NPC问题不存在有效的算法 现在的密码算法的安全性都是基于NPC问题的 2020 2 20 Ch2 数学基础 49 算法的复杂性 算法的复杂性表示算法在实际执行时所需计算能力方面的信息 通常它由该算法所要求的最大时间与储存空间来确定算法所需的时间和空间往往取决于问题实例的规模n算法在用于相同规模n的不同实例时 其时间和空间需求也可能会有很大差异 因此 实际中我们常常研究的是算法关于输入规模n的所有实例的时间与空间需求的平均值表2 6显示 如果一个密码算法具有指数级的时间复杂性 那么可以认为它是计算上不可行的 2020 2 20 Ch2 数学基础 50 2020 2 20 Ch2 数学基础 51 单向函数 单向和陷门单向函数是公钥密码学的核心 可以说公钥密码体制的设计就是陷门单向函数的设计定义2 23 单向函数 一个可逆函数f A B 若它满足 1 对所有x A 易于计算f x 2 对几乎所有x A 由f x 求x极为困难 以至于实际上不可能做到 则称f为单向函数 One wayFunction 2020 2 20 Ch2 数学基础 52 定义2 24 单向陷门函数 一 可逆 函数F若满足下列二条件 则称F为单向陷门函数 One wayTrapdoorFunction 1 对于所有属于域F中的的任一x 容易计算F x y 2 对于几乎所有属于域F中的任一y 除非获得陷门信息 trapdoor 否则求出x 使得x F 1 y 在计算上不可行 F 1为F的逆函数单向函数是求逆困难的函数 而单向陷门函数是在不知陷门信息下求逆困难的函数 当知道陷门信息后 求逆是易于实现的 2020 2 20 Ch2 数学基础 53 目前 还不能从理论上证明单向函数是存在的现实中却存在几个候选单向函数 说他们是 候选 是因为他们表现出了单向函数的性质 但还没有办法从理论上证明它们一定是单向函数常见的候选单向函数 离散对数 因数分解问题 背包问题