密(研)8-数论入门.pdf

第8章 数论入门 Introduction to Number Theory 课程内容大纲 1. 引言 第一部分：对称密码 第三部分：密码学数据完整性算法 2. 传统加密技术 11.密码学与Hash函数 （ 3. 分组密码与数据加密标准 DES） 12.消息认证码（MAC） 4. 数论与有限域的基本概念 13.数字签名 （ 5. 高级加密标准 AES ） 6. 分组密码的工作模式 第四部分：相互信任 7. 伪随机数的产生和流密码 14.密钥管理与分发 15.用户认证 第二部分：公钥密码 8. 数论入门 9. 公钥密码学与RSA 10. 密钥管理和其他公钥密码体制 讲课内容 8.1 素数 8.2 费马定理和欧拉定理 8.3 素性测试 8.4 中国剩余定理 8.5 离散对数 数论入门 • 素数是一种整数，在整除意义下，它只能被自身(正负)和1 整除。素数在数论和密码学里扮演重要角色。 • 在公钥密码里起重要作用的定理是费马小定理\欧拉定理\ 中国剩余定理。 • 许多密码算法的一个重要前提是能够选择一个大的素数。 开发有效素性检测算法判定一个随机整数是否为素数是密 码研究重要课题。 • 离散对数是许多公钥算法的基础。离散对数和普通对数类 似，但是在模算术上进行运算。 8.1 素数 Prime Numbers 素数 • 整数p 1是素数当且仅当它只有因子±1和±p 。 0，1都不是素数 2是最小的素数，也是唯一的偶素数 如2,3,5,7是素数, 4,6,8,9,10不是 素数是数论的核心 整数的素因子分解 • 分解是指将任何整数n1, 分解为其他整数乘积的形式，即 n=a×b×…×c • 比起用乘的方法把几个因子乘起来生成合数, 分解合数通常 要困难得多。 a 1 a2 at • 任何整数a1, 都可以唯一分解为a= p 1 p 2 …p t , 其中, p p …p 是素数, 每一个a 是正整数（算数基本定理） 1 2 t i 2 4 2 2 如91=7 ×13，11011=7×11 ×13，3600=2 ×3 ×5 • 另一种表示方法，设P是所有素数的集合，则任意正整数a ap p 可唯一表示成： a ∏P 其中每一个a ≥0 p ∈P 整数的素分解 • 任一给定的正整数, 可通过简单列出所有后面公式中非零指 数分量来说明. 12可以表示为{a =2, a =1}, 18可以表示为 {a =1, a =2}, 91可以表 2 3