Crypto-8 - 中国科学技术大学.ppt

现代密码学理论与实践第8章数论入门
Fourth Edition by William Stallings
杨寿保苗付友
syang, ******@ustc.
./~hongjuny
2011年9月
2018/11/12
1
现代密码学理论与实践-08
第二部分公钥密码和散列函数
第8章:数论入门
第9章:公钥密码与RSA
第10章:密钥管理和其他公钥密码体制
第11章:消息认证和散列函数
第12章:散列和MAC算法
第13章:数字签名和认证协议
2018/11/12
2
现代密码学理论与实践-08
Chapter 8  Introduction to Number Theory
The Devil said to Daniel Webster: "Set me a task I can't carry out, and I'll give you anything in the world you ask for."
Daniel Webster: "Fair enough. Prove that for n greater than 2, the equation an + bn = cn has no non-trivial solution in the integers."
They agreed on a three-day period for the labor, and the Devil disappeared.
At the end of three days, the Devil presented himself, haggard, jumpy, biting his lip. Daniel Webster said to him, "Well, how did you do at my task? Did you prove the theorem?'
"Eh? No . . . no, I haven't proved it."
"Then I can have whatever I ask for? Money? The Presidency?'
"What? Oh, that—of course. But listen! If we could just prove the following two lemmas—"
—The Mathematical Magpie, Clifton Fadiman
2018/11/12
3
现代密码学理论与实践-08
本章要点
素数是一种整数,在整除意义下,它只能被自身(正负)和1整除。素数在数论和密码学里扮演重要角色。
在公钥密码里起重要作用的两个定理是费马定理和欧拉定理。
许多密码算法的一个重要前提是能够选择一个大的素数。开发有效算法判定一个随机整数是否为素数是密码研究的重要课题。
离散对数是许多公钥算法的基础。离散对数和普通对数类似,但是在模算术上进行运算。
2018/11/12
4
现代密码学理论与实践-08
素数 Prime Numbers
整数p>1是素数当且仅当它只有因子±1和±p,如2,3,5,7是素数,而4,6,8,9,10不是素数
素数不能写作其他数的乘积形式
1是素数,但是通常没有什么用
素数是数论的核心
小于200的素数如下
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
2018/11/12
5
现代密码学理论与实践-08
小于2000的素数如下
2018/11/12
6
现代密码学理论与实践-08
合数的素因子分解
分解一个数n就是把它写成其他数的乘积形式,如 n=a×b×c
比起用乘的方法把几个因子乘起来生成合数,分解合数通常要困难得多。
任何整数a>1, 都可以唯一地分解为a= p1a1p2a2…ptat , 其中, p1<p2<…<pt 是素数,所有的ai都是正整数。如91=7x13; 3600=24x32x52; 11011=7x112x13
素因子分解就是把一个合数写成若干素数的乘积形式,如3600=24x32x52,
其中每个ap≥0, 对于某一整数a,
其大多数指数ap为0.
2018/11/12
7
现代密码学理论与实践-08
合数的素因子分解
任一给定的正整数, 可通过简单列出所有后面公式中非零指数分量来说明.
Ex:12可以表示为{a