本章要点 素数是一种整数,在整除意义下,它只能被自身(正 负)和1整除。素数在数论和密码学里扮演重要角色。 在公钥密码里起重要作用的两个定理是费马定理和欧 拉定理。 丶许多密码算法的一个重要前提是能够选择一个大的素 数。开发有效算法判定一个随机整数是否为素数是密 码研究的重要课题。 离散对数是许多公钥算法的基础。离散对数和普通对 数类似,但是在模算术上进行运算。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 3/81
mfy@ustc.edu.cn 现代密码学理论与实践 3/81 素数是一种整数，在整除意义下，它只能被自身(正 负)和1整除。素数在数论和密码学里扮演重要角色。 在公钥密码里起重要作用的两个定理是费马定理和欧 拉定理。 许多密码算法的一个重要前提是能够选择一个大的素 数。开发有效算法判定一个随机整数是否为素数是密 码研究的重要课题。 离散对数是许多公钥算法的基础。离散对数和普通对 数类似，但是在模算术上进行运算
本章目录 8.1素数 8,2单向函数 8.3费马定理和欧拉定理 8.4素性测试 8.5计算乘法逆元素 8.6求解 ax mod n=b的问题 8,7中国余数定理 8.8离散对数问题 8.9二次剩余问题 8.10不经意传输 ash mfy@ustc.edu.cn 现代密码学理论与实践 4/81
mfy@ustc.edu.cn 现代密码学理论与实践 4/81 8.1 素数 8.2 单向函数 8.3 费马定理和欧拉定理 8.4 素性测试 8.5 计算乘法逆元素 8.6 求解ax mod n =b的问题 8.7 中国余数定理 8.8 离散对数问题 8.9 二次剩余问题 8.10 不经意传输
8.1素数 Prime Numbers 素数→合数→最大公因数 整数p>1是素数当且仅当它只有因子±1和±p,如 2,3,5,7是素数,而4,6,8,9,10不是素数 素数不能写作其他数的乘积形式 1是素数,但是通常没有什么用 素数是数论的核心 小于200的素数如下 23571113171923293137414347 53596167717379838997101103 107109113127131137139149151157 163167173179181191193197199 ash mfy@ustc.edu.cn 现代密码学理论与实践 5/81
mfy@ustc.edu.cn 现代密码学理论与实践 5/81 整数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 素数→合数→最大公因数
小于2000的素数如下 Table 8.1 Primes under 2000 1!13122934好490sn1乃78「89 1010310710913127131313911511571s3167i3171a11193197199 292332392412512572632627112772311283129 30731313373137373493533673733793831389|39 04941942143433439443449457461463457479487491499 503552523541547557563156571577 6016m137196316414364763659 673677683691 70107197277331394375117577617673787797 0a1]321823a7829a93535783633m7183887 o7q999299379179596791|9983y1997 l0091013|101910211031103310g104910511o6110631o69l107|10g10931097 1101011231291111153116311n11311187119 1201121311217 212121123719159127 1279123311289112911297 1浏[1331班3013713313139 1414231421|14314组[1均311143 143914 1499 1111523151551548155513591515159[15831397 l61l160710916131619162116716371657166160166l1693|16s71699 17091721172 4133[1mT1339 l801a11a181186113671118731371791389 1聊919[9191199 ash mfy@ustc.edu.cn 现代密码学理论与实践 6/81
mfy@ustc.edu.cn 现代密码学理论与实践 6/81
合数的素因子分解 分解一个数η就是把它写成其他数的乘积形式,如 n=a×b×C 比起用乘的方法把几个因子乘起来生成合数,分解 合数通常要困难得多。 (算术基本定理)任何整数a>1,都可以唯一地分 解为a=p1ap2pat,其中,p1<p2<.<p是素 数,所有的a都是非负整数。如91=7×13; 3600=24×32x52:11011=7×112×13 素因子分解就是把一个合数写成若干素数的乘积形 式,如3600=24×32×52, a=∏P“其中每个20,对于某整数a, 其大多数指数a为0 D∈D 2021/1/27 现代密码学理论与实践-08 7/69
2021/1/27 现代密码学理论与实践-08 7/69 分解一个数n就是把它写成其他数的乘积形式，如 n=a×b×c 比起用乘的方法把几个因子乘起来生成合数，分解 合数通常要困难得多。 （算术基本定理）任何整数a>1, 都可以唯一地分 解为a= p1 a1p2 a2…pt at , 其中, p1<p2<…<pt 是素 数，所有的ai都是非负整数。如91=7x13; 3600=24x32x52; 11011=7x112x13 素因子分解就是把一个合数写成若干素数的乘积形 式，如3600=24x32x52 ， 其中每个ap≥0, 对于某一整数a， 其大多数指数ap为0. = p P ap a P
合数的素因子分解 任一给定的正整数,可通过简单列出所有后面公式中 非零指数分量来说明 ■ EX:12可以表示为{a2=2,a3=13,18可以表示为 {a2=1,a3=2},91可以表示为{a7=1,a13=1 两个数的乘法等同于对应指数分量的加法 k=m→k=m+n对所有p Ex:k=12X18=(22×3)X(2X32)=216,k2=2+1=3, 1+2 3,∴216=23×3 任何以p形式表示的整数仅能被对应素数分量小于 或等于它的另一个整数p整除,其中/k,即有叫b a≤b,对所有素数成立 Ex:a=12,b=36,12|36,12=22X31,36=22×32 2=b2 ≤2=b3 ash mfy@ustc.edu.cn 现代密码学理论与实践 /81
mfy@ustc.edu.cn 现代密码学理论与实践 8/81 任一给定的正整数, 可通过简单列出所有后面公式中 非零指数分量来说明. Ex：12可以表示为{a2=2, a3=1}, 18可以表示为 {a2=1, a3=2}, 91可以表示为{a7=1, a13=1} 两个数的乘法等同于对应指数分量的加法 k=mn →kp = mp + np 对所有p Ex：k=12x18=(22x3)x(2x32 )=216, k2=2+1=3, k3=1+2=3, ∴ 216=23x33 任何以pk形式表示的整数仅能被对应素数分量小于 或等于它的另一个整数pj 整除, 其中j≤k，即有a|b →ap≤bp ，对所有素数p成立。 Ex：a=12, b=36, 12|36, 12=22x31 , 36=22x32 a2=2=b2 , a3=1≤2=b3
互素和最大公约数GCD gcd(a,b)=C,即c是a和b的最大公约数,当 C是a和b的因子 2任何a和b的因子也是c的因子 两个整数a,b,如果除了1以外没有公共因子,则称它们互 素( Relatively prime 8和15互素,因为8的因子是12,4,8,而15的因子是 它们唯一的公共因子。 〉如果将整数表示为素数之积,则容易确定两个正整数的最 公因子 下列关系总是成立的 如果k=gcd(a,b),则k=min(amb,对于任意的∈P 例子: 300=22x3l×52,18=2lX32 gcd(18,300)=2x3×50=6 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 9/81
mfy@ustc.edu.cn 现代密码学理论与实践 9/81 gcd(a, b)=c, 即c是a和b的最大公约数, 当 1.c是a和b的因子 2.任何a和b的因子也是c的因子 两个整数 a, b, 如果除了1以外没有公共因子, 则称它们互 素(Relatively Prime) 8和15互素, 因为8的因子是1,2,4,8, 而15的因子是 1,3,5,15, 1是它们唯一的公共因子。 如果将整数表示为素数之积, 则容易确定两个正整数的最 大公因子 下列关系总是成立的 如果k=gcd(a, b), 则 kp =min(ap , bp ), 对于任意的p∊P 例子： 300=22x31x52, 18=21x32 , gcd(18, 300)=21x31x50=6
82单向函数 One-way Function 单向陷井门函数One- way Trapdoor Function 定义8.1单向函数( One-way function) 函数f若满足下列条件,则称f为单向函数: (1)对于所有属于f之域的任一X,容易计算y(x) (2)对于几乎所有属于f之域的任一y求得x使≠=x),在计算上 不可行。 定义82单向陷井门函数(One- way Trapdoor Function) 可逆”函数f若满足下列两条件,则称F为单向陷井门函 数 (1)对于所有属于F之域的任一X,容易计算尺(x)=y (2)对于几乎所有属于f之域的任一%除非获得暗门信息 trapdoor),否则求出x,使得ⅹ=F1(y在计算上不可行,F1 为F之逆函数;如有额外信息暗门),则容易求出x=F1(,如 旅馆房间门。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 10/81
mfy@ustc.edu.cn 现代密码学理论与实践 10/81 定义8.1 单向函数(One-way Function) 一函数f 若满足下列条件, 则称f 为单向函数： (1)对于所有属于f 之域的任一x, 容易计算y= f(x) (2)对于几乎所有属于f 之域的任一y, 求得x, 使y= f(x), 在计算上 不可行。 定义8.2 单向陷井门函数(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)，如 旅馆房间门
单向函数举例 1离散对数问题 Discrete logarithm Problem(DP 令素数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=(111)2,Wx)=4,则g15=(g2)g)2·g)2gmod p,只需要3+4-1=6次乘法。 但是若给定p,g及y,求x,则为DLP问题,最快方法需 要L(p)=exp{(np)l/3(n(np)2/3}次运算。 当p=512位时,L(p)约为2256≈1077,计算上不可行, 因为2100%1030,计算要1016年。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 11/81
mfy@ustc.edu.cn 现代密码学理论与实践 11/81 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{(lnp) 1/3(ln(lnp)) 2/3 }次运算。 当p=512位时, L(p)约为2256≈1077 , 计算上不可行, 因为2100≈1030 , 计算要1016年
单向函数举例(续) 2.因数分解问题 Factorization prob|em 给定大素数p和q,求n=p×q,只要一次乘法 给定n,求p和q,即为因数分解问题(FAC,最快方法需要 T(n)=exp{c(nnn(nn)号次运算,其中C为大于 的正整数。 3.背包问题 Knapsack problem 给定有限个自然数序列集合B=(b1,b2,b)及二进制序列 =(X1,x2,Xn),X∈(0,1),求S=∑Xb最多只需n-1次 加法;但若给定B和S,求x则非常困难。 穷举时有2种可能,当n很大时为计算上不可行。 Garey和 Johnson证明,背包问题是NP问题 (Non-Polynomial) ash mfy@ustc.edu.cn 现代密码学理论与实践 12/81
mfy@ustc.edu.cn 现代密码学理论与实践 12/81 2. 因数分解问题Factorization Problem 给定大素数 p和q, 求n = p×q, 只要一次乘法 给定n, 求p和q, 即为因数分解问题(FAC), 最快方法需要 T(n) = exp {c(ln n ln (ln n))½ } 次运算, 其中c为大于 1的正整数。 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)