第 4 章 数论和密码学
# 第 4 章 数论和密码学
# 4.1 整除性和模算术
# 4.1.1 引言
# 4.1.2 除法
笔记
整除 记作 - 有整数
,使得
- 有整数
不能整除 记作
# 4.1.3 除法算法
#
整除算法
,其中 是唯一存在的 为除数, 为被除数, 为商, 为余数 - 当
时,有些编程语言会返回 - 有些编程语言,对于
, 当 甚至 时也有定义
# 4.1.4 模算术
笔记
- 同余式
- 称为
模 同余
- 所有和
模 同余的整数集合称为 模 的同余类 - 加法和乘法是保同余的
- 推论
- 推论
# 4.1.5 模 m 运算
笔记
- 在小于
的非负整数的集合 上定义的算术运算 - 称为模
算术
- 称为模
连同模加法被称为一个交换群 连同模 算术被称为一个交换环
# 4.2 整数表示和算法
# 4.2.1 引言
提示
- 算法最初是指用整数的十进制表示来进行算术运算的过程
# 4.2.2 整数表示
笔记
- 构造
进制展开式的算法为辗转相除法 - 本质上是一个贪婪算法,因为在每一步都是取尽可能大的
进制数字
- 本质上是一个贪婪算法,因为在每一步都是取尽可能大的
# 4.2.3 整数运算算法
提示
- 加法运算引入进位进行运算
- 乘法运算相当于移位后进行加法运算
笔记
- 需要
次比特运算来计算 的商和余数
# 4.2.4 模指数运算
笔记
- 不使用过量的内存而有效的计算
- 借助指数
的二进制展开式来进行计算 - 借助迭代来计算
来减少运算量 - 每乘一项后,都做一次模
运算以缩小结果值
- 借助指数
# 4.3 素数和最大公约数
# 4.3.1 引言
提示
- 对大整数进行素因子分解所需的时间尺度是一些现代密码系统中密码强度的基础
# 4.3.2 素数
素数与合数
- 恰有两个不同的正整数因子的整数称为素数
- 大于 1 但又不是素数的正整数称为合数
- 整数
是合数当且仅当存在整数 使得 并且
- 整数
- 1 既不是素数也不是合数
#
算术基本定理
- 每个大于 1 的整数都可以唯一的写成两个或多个素数的乘积,其中素因子以非递减序排列
# 4.3.3 试除法
#
定理432
- 如果
是一个合数,那么 必有一个素因子小于等于
# 4.3.4 埃拉托斯特尼筛法
笔记
- 埃拉托斯特尼筛法用来寻找不超过一个给定整数
的所有素数 - 借助定理432可以确定只用筛选到不超过
的最大素数
- 借助定理432可以确定只用筛选到不超过
#
定理3.3
- 存在无限多个素数
- 证明可以采用反证法
梅森素数
- 已知的最大素数几乎都是形如
的整数 为素数 - 这种素数被称为梅森素数
#
素数定理
- 当
无限增长时,不超过 的素数个数与 之比趋进于
卡宁汉数
- 形如
的大数 为小正数,而 为大整数
算术级数
- 形如
,其中不存在比 1 大的整数能同时整除 和 - 每个这样的整数都有无穷多个素数
- 对于任意大于 2 的正整数
,存在完全由素数构成的长度为 的算术级数
# 4.3.5 关于素数的猜想和开放问题
多项式
- 对于每一个整数系数多项式
,存在一个正整数 使得 是合数
哥德巴赫猜想* 每个大于 2 的偶数是两个素数之和
特殊形式的素数猜想
- 猜想:存在无限多个正整数
使得 是素数 - 已证明:存在无限多的正整数
,使得 或者是素数,或者是至多两个素数的乘积
- 已证明:存在无限多的正整数
孪生素数猜想
- 孪生素数是指相差 2 的一对素数
- 孪生素数猜想断定存在无限多对孪生素数
- 设
为命题:存在无限多对差值恰为 的素数对 时即为孪生素数猜想
# 4.3.6 最大公约数和最小公倍数
最小公倍数
- 正整数
, 的最小公倍数记为 - 也可采用素因子分解式进行求解和分析
#
定理 3.5
- 令
和 为正整数,则 - 证明可以借助 算术基本定理
# 4.3.7 欧几里得算法
提示
- 欧几里得算法即为辗转相除法
#
引理 3.1
- 令
,其中 和 均为整数。则 证明
- 只需证
的公约数与 的公约数相同即可 - 借助此引理即可证明欧几里得算法
- 因为如果
,则 ,因此欧几里得算法一定会收敛
- 只需证
算法过程
- 连续应用整除算法,除法序列中最后一个非零余数即为最大公约数
- 假设
。 令 和
- 假设
# 4.3.8 gcd 的线性组合表示
#
贝祖定理
- 如果
和 为正整数,则存在整数 和 使得 - 整数
和 为 和 的贝祖系数 称为贝祖恒等式
- 整数
#
定理 37
- 令
为正整数, 和 为整数。如果 且 ,则 - 在同余式的两边同时除以一个整数,得到一个新的同余式
- 证明借助 引理32
# 4.4 求解同余方程
# 4.4.1 引言
# 4.4.2 线性同余方程
定义
- 具有下面形式的同余方程,被称为线性同余方程
- 其中
为正整数, 为整数, 为变量
- 其中
#
# 4.4.3 中国剩余定理
#
中国剩余定理
- 令
为大于 的两两互素的正整数,而 是任意整数。则同余方程组 - 有唯一的模
的解
- 有唯一的模
证明
- 存在性证明,采用构造性证明
- 令
即为满足方程组的一个解
- 令
- 唯一性证明
- 借助练习 29(P253) 中的结论采用反证法来证明
为大于 的整数且两两互素 - 若
- 则
,其中
- 若
- 可以借助同余的基本定义和 算术基本定理 来证明
- 借助练习 29(P253) 中的结论采用反证法来证明
实际求解线性同余方程时,可以采用 反向替换 的方法
# 4.4.4 大整数的计算机算术
将整数用序偶来表示
- 假定
是两两互素的模数,令 为其乘积 - 则满足
的整数 可以唯一的表示为一个 元组,即
大整数算术运算
- 一旦选定模数,大整数算术可以通过在表示这些整数的
元组分量上做运算来完成 - 一旦计算出结果的每个分量值,就可以通过求解
个模 的同余方程来恢复结果的值
优点
- 可以用来完成通常在一台计算机上不能做的大整数算术
- 对不同模数的计算可以并行操作,加快计算速度
# 4.4.5 费马小定理
#
费马小定理
- 如果
为素数, 是一个不能被 整除的的整数,则 - 再者,对于每个整数
都有
证明
- 参照练习 19 (P253) 中的证明思路
# 4.4.6 伪素数
伪素数的定义
- 令
为正整数。如果 是一个正合数且 ,则 称为以 为基数的伪素数 - 与素数相比,以
为基数的伪素数要少很少 - 这个可以作为素数测试的基础
- 与素数相比,以
卡米切尔数
- 一个正合数
如果对于所有满足 的正整数 都有同余式 成立,则称为卡米切尔数 - 尽管存在无限多个卡米切尔数,但是可以设计更精细的测试,作为有效的素数性测试的基础
- 这些随机的素数性测试能够而且已经用于在计算机上非常迅速地寻找大素数
# 4.4.7 原根和离散对数
原根
- 模素数
的一个原根是 中的整数 ,使得 中每个非零元素都与 的一个幂次模 同余 - 定义参照 模
算术 - 对于每个素数
都存在一个模 的原根
- 定义参照 模
离散对数的定义
- 假设
是一个素数, 是一个模 的原根 是介于(含) 和 之间的一个整数 - 如果
且 - 则说
是以 为底 模 的离散对数,写作
# 4.5 同余的应用
# 4.5.1 散列函数
笔记
- 散列函数
将内存地址 分配给以 为键值的记录 - 最常用的散列函数
为可供使用的内存地址的数目
- 散列函数应该是满射的,这样所有的内存地址均可利用
- 散列函数不是一对一的
- 键值的数量可能大于内存地址数
- 如此,会发生冲突,消解冲突的一个方法是使用线性探测函数
- 寻找分配的地址后面第一个未被占用的地址
🔲 待做事项
- 添加到 CLRS 中散列函数的链接
# 4.5.2 伪随机数
笔记
- 由系统方法产生的数并不是真正随机的,因为被称为伪随机数
- 最常用的产生伪随机数过程是线性同余法
- 模数
- 倍数
, - 增量
, - 要产生 [0, 1) 间的伪随机数,则使用
时称为纯倍式生成器 - 常用的生成器选择
- 常用的生成器选择
- 模数
# 4.5.3 校验码
笔记
- 同余可用于校验数字串中的错误
- 在串的结尾中添加一个额外的数字
- 称为校验码
- 是用特定的函数来计算的
- 实例
- 奇偶校验
- 可以检验奇数个错误,但不能检测到偶数个错误
- ISBN (国际标准书号)
- 即可以用来检测单错,也可用来检验换位错
- 单错:标识码中的一位发生错误
- 换位错: 两位数字发生颠倒
- 即可以用来检测单错,也可用来检验换位错
- 奇偶校验
# 4.6 密码学
# 4.6.1 引言
密码学
- 将信息作转换使得在没有特殊知识的情况下不能很容易的恢复出来
# 4.6.2 古典密码学
笔记
- 加密(encryption)是对信息进行保密处理的过程
- 从加密消息中来确定原始消息的过程称为解密(decryption)
移位密码
- 加密
- 解密
称为密钥(key)
仿射密码
- 加密
需要是一个双射函数,要求 称为仿射变换
- 解密
密码分析
- 在不具备加密方法和密钥知识的情况下从密文中恢复出明文的过程称为密码分析或破译密码
- 对于移位或仿射密码,可以通过找出密文中字母的相对频率来进行密码分析
分组密码
- 通过用一组字母替换另一组字母的密码称为分组密码(block cipher)
- 换位密码是一种简单的分组密码
- 通过移到字母的位置来进行加密
密码系统
- 密码系统 (cryptosystem) 是一个五元组
是明文(plaintext)串的集合 是密文(ciphertext)串的集合 是密钥空间 - 所有可能的密钥的集合
是加密函数的集合 - 用
表示在 中相对于密钥 的加密函数
- 用
是解密函数的集合 - 用
表示在 中用来解密由 加密的密文的解密函数 - 对于所有的明文
有
- 用
将移位密码描述为密码系统
- 假设字母和整数之间的翻译处于密码系统的外部
- 明文串的集合
和密文串的集合 都是 中元素串的集合 - 密钥集合
是所有可能的移位,即 - 集合
由所有 这样的函数构成 - 集合
由所有 这样的函数构成
# 4.6.3 公钥密码学
私钥密码系统
- 在私钥密码系统中,一旦知道了加密密钥,则可以很快找到解密密钥
- 因此希望安全通信的双方就需要安全的交换该密钥
- 现在私钥密码学的美国标准 -- 高级加密标准(Advanced Encryption Standard, AES) 是非常复杂私钥系统
公钥密码系统
- 为了避免每对希望安全通信的双方都需要共享密钥,20世记70年代引入了公钥密码系统
- 公钥密码系统中,知道怎样加密消息的人并不能解密消息
- 每个人都可以有一个公开的加密密钥,只有解密密钥是保密的
- 如果不做非常大量的计算(例如几十亿年的计算机时间),即使具有加密密钥的知识也不能恢复出明文信息
- 最常用的公钥密码系统为 RSA 系统
公钥密码系统的劣势是加密解密都会非常耗时
- 但公钥密码系统可以用于私钥密码系统的密钥交换过程
# 4.6.4 RSA 密码系统
加密密钥
- 每个人都有一个加密密钥
是两个大素数,一般超过 300 位,则 超过 600 位 - 超过 600 位的整数,迄今为止不可能在合理的时间内被因子分解
是一个与 互素的指数
量子计算机的发展直接威胁到了 RSA 密码系统的安全
- 因为量子计算机开发的因子分解算法能够用于快速分解大素数因子
大素数的生成一般采用素数的概率测试
- 参照 素数的概率测试
# 4.6.5 RSA 加密
加密过程
- 将明文翻译为整数序列
- 将整数序列
分成 位数字等长的分组,形成整数序列 是使得 位数字 不超过 的最大偶数
- 加密函数如下
RSA 密码系统将字符分组加密为字符分组,因此属于分组密码
# 4.6.6 RSA 解密
解密过程
- 解密密钥
为 模 的逆 - 由费马小定理和中国剩余定理可得
# 4.6.7 用 RSA 作为公钥系统
# 4.6.8 密码协议
密码协议是两方或多方为了达到一个特定的安全目标而进行消息交换
#
迪菲-赫尔曼密钥协商协议
数字签名
- 密码学不仅可以用来确保消息的保密性,还可以用来使消息的接收者知道消息来自那个该来自的人
RSA 密码系统的数字签名
- A 将明文用自己的解密函数处理得到签名信息
- 其它人收到签名信息后用 A 的加密函数对密文解密得到明文,从而确定消息确实是由 A 发送的
相当于逆反加密和解密过程
发送加密的签名信息
- A 生成签名信息后,用 B 的加密钥加密成密文
- B 接收到密文后,用自己的私钥解密得到签名信息,再用 A 的加密密钥加密生成明文,从而确定消息是由 A 发送的
# 4.6.9 同态加密
全同态密码系统
- 在加密数据上做任何计算,均能够产生由该非加密输入作相同运算所得的非加密输出的加密形式
- 如此,则可以安全的在云上处理加密数据
- 目前有基于格密码学的全同态密码系统,但还没有开发出实用的全同态密码系统
- RSA 是乘法同态的,但不是加法同态的,因此其被称为偏同态的
编辑 (opens new window)