网络信息安全crypto-8数论入门.ppt

2017/7/28
现代密码学理论与实践-08
1
网络信息安全Chapter 8 Introduction to Number Theory
2017/7/28
现代密码学理论与实践-08
2/68
第二部分公钥密码和散列函数
第8章:数论入门
第9章:公钥密码与RSA
第10章:密钥管理和其他公钥密码体制
第11章:消息认证和散列函数
第12章:散列和MAC算法
第13章:数字签名和认证协议
2017/7/28
现代密码学理论与实践-08
3/68
本章要点
素数是一种整数,在整除意义下,它只能被自身(正负)和1整除。素数在数论和密码学里扮演重要角色。
在公钥密码里起重要作用的两个定理是费马定理和欧拉定理。
许多密码算法的一个重要前提是能够选择一个大的素数。开发有效算法判定一个随机整数是否为素数是密码研究重要课题。
离散对数是许多公钥算法的基础。离散对数和普通对数类似,但是在模算术上进行运算。
2017/7/28
现代密码学理论与实践-08
4/68
素数Prime Numbers
素数的因子是1和其自身
不能写作其他数的乘积形式
1是素数,但是通常没有什么作用
如,2,3,5,7是素数, 4,6,8,9,10不是
素数是数论的核心
小于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
2017/7/28
现代密码学理论与实践-08
5/68
小于2000的素数
2017/7/28
现代密码学理论与实践-08
6/68
One-way Function and One-way Trapdoor Function
单向函数(One-way Function)
一函数f 若满足下列条件, 则称f 为单向函数:
(1)对于所有属于f 域的任一x, 容易计算y= f(x)
(2)对于几乎所有属于f 域的任一y, 求得x, 使y= f(x), 在计算上不可行。
单向陷井门函数(One-way Trapdoor Function)
一“可逆”函数F若满足下列二条件, 则称F为单向陷井门函数:
(1)对于所有属于F域的任一x, 容易计算F(x)=y;
(2)对于几乎所有属于F域的任一y, 除非获得暗门信息(trapdoor), 否则求出x, 使得 x = F-1(y)在计算上不可行, F-1为F之逆函数; 如有额外信息(暗门), 则容易求出 x = F-1(y)。
2017/7/28
现代密码学理论与实践-08
7/68
1. Discrete Logarithm Problem (DLP) 离散对数问题
令质数p满足p-1含有另一大质数q (q整除p-1)及一整数g, 1<g< p-1。
若给定整数x, 求y = gx mod p, 最多需要Llog2x｣+w(x)-1次乘法, w(x)为x中所有1的个数。如x =15, 即
x =(1111)2, w(x)=4, 则g15 =((g2)g)2·g)2·g mod p, 只需要3 + 4 -1=6次乘法。
但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需要L(p)=exp{(lnpln(lnp))½}次运算。
当p=512位时, L(p)约为2256≈1077, 计算上不可行, 因为2100≈1030, 计算要1016年。
单向函数举例
2017/7/28
现代密码学理论与实践-08
8/68
2. Factorization Problem 因数分解问题
给定大素数 p和q, 求n = p×q, 只要一次乘法
给定n, 求p和q, 即为因数分解问题(FAC), 最快方法需要 T(n) = exp {c(ln n ln (ln n))½} 次运算, 其中c为大于1的正整数。若p≈n, 解离散对数比因数分解难。
3. 背包问题Knapsack Problem
给定有限个自然数序列集合B=(b1,b2,…bn)及二进制序列x=(x1,x2,…xn), xi∈(0,1), 求S=∑xibi最多只需n-1次加法;但若给定B和S, 求x则非常困难。
穷举时有2n种可能, 当n很大时为计算上不可行。
Garey和Johnson证明, 背包问题是NP问题(Non-Polynomial)
单向函数举例(续)
2017/7/28
现代密码学理论与实践-08
9/68
mutati