单向函数举例（续） 15 2.因数分解问题Factorization Problem 给定大素数p和q,求n=pXq,只要一次乘法 给定n,求p和q,即为因数分解问题(FAC),最快方法需要 T(n)=exp{c(In n In(Inn)}次运算，其中c为大于1的 正整数。若p≈n,解离散对数比因数分解难。 3.背包问题<napsack Problem 给定有限个自然数序列集合B=(b1,b2,.b)及二进制序列 X=(X1,X2,…X),×∈(0,1)，求S=∑xb最多只需n-1次加法； 但若给定B和S,求则非常困难。 穷举时有2种可能，当n很大时为计算上不可行。 Garey和Johnson证明，背包问题是NP问题 (Non-Polynomial) 2022/10/9 现代密码学理论与实践-08 12/70
2022/10/9 现代密码学理论与实践-08 12/70 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则非常困难。 穷举时有2 n种可能, 当n很大时为计算上不可行。 Garey和Johnson证明, 背包问题是NP问题 (Non-Polynomial) 单向函数举例(续)
海冷长 单向函数及其交换性 15 单向函数的交换性(commutative property) 单向函数本身对近代密码学领域用处不大，但若具 有交换性，则作用大。 定义8.3交换性 令Z为一集合，F为将Z映射到Z本身的函数集合。 令z∈Z,Fx(Z)表示此函数集合之第x函数， 若Fx(Fy(z)=Fy(Fx(z),则称此函数集合具有交换性。 例：D(E(m)=E(D(m) 2022/10/9 现代密码学理论与实践-08 13/70
2022/10/9 现代密码学理论与实践-08 13/70 ⚫ 单向函数的交换性(commutative property) 单向函数本身对近代密码学领域用处不大，但若具 有交换性，则作用大。 定义8.3 交换性 令Z为一集合，F为将Z映射到Z本身的函数集合。 令z∈Z, Fx(z)表示此函数集合之第x函数, 若Fx(Fy(z))=Fy(Fx(z))，则称此函数集合具有交换性。 例：D(E(m))=E(D(m)) 单向函数及其交换性
指数函数(Exponentiation Function) 定义8.4指数函数 令G为有限乘法群，g∈G,则对于所有整数×，Ex(g)=g× modp∈G,是为指数函数。 通常，令G={1,2,…,p-1},p为素数，则 Ex(g)=gx mod p为指数函数。 。指数函数之特性 1.周期性(Periodicity) 令序列<Exg)>={g°，g1,g2,.…}为g所产生之序列。因为G 是有限群，Ex《g)不可能不重复，故Ex(g)产生之序列为周 期序列。 2022/10/9 现代密码学理论与实践-08 14/70
2022/10/9 现代密码学理论与实践-08 14/70 指数函数(Exponentiation Function) 定义8.4 指数函数 令G为有限乘法群, g∈G, 则对于所有整数 x, Ex(g)=gx mod p ∈G, 是为指数函数。 通常, 令G={1,2,…,p-1}, p为素数, 则 Ex(g)= gx mod p为指数函数。 ⚫ 指数函数之特性 1. 周期性(Periodicity) 令序列<Ex(g)>={g0 ,g1 ,g2 ,…}为g所产生之序列。因为G 是有限群, Ex(g)不可能不重复, 故Ex(g)产生之序列为周 期序列
◆车在不 指数函数之特性（续） 15 当存在最小正整数T,使得E(g)=gT=1=g时，称T为g在 G中的阶或序(order)。根据Fermat's Theorem,对于 所有g,T必定整除p-1. 例：p=11,g=2, <Exg)>={20,21,22,…,210}={1,2,4,8,5,10,9,7,3,6,1} 即：20=1m0d11 26=9m0d11 21=2m0d11 27=7mod11 22=4m0d11 28=3mod11 23=8m0d11 29=6m0d11 24=5m0d11 210=1m0d11 25=10m0d11 所以T=10=11-1=p-1 2022/10/9 现代密码学理论与实践-08 15/70
2022/10/9 现代密码学理论与实践-08 15/70 当存在最小正整数T, 使得ET (g)=gT=1=g0时, 称T为g在 G中的阶或序(order)。根据Fermat’s Theorem, 对于 所有g, T必定整除p-1. 例：p=11, g=2, <Ex(g)>={20 ,21 ,22 ,…,210}={1,2,4,8,5,10,9,7,3,6,1} 即：2 0=1 mod 11 2 6=9 mod 11 2 1=2 mod 11 2 7=7 mod 11 2 2=4 mod 11 2 8=3 mod 11 2 3=8 mod 11 2 9=6 mod 11 2 4=5 mod 11 2 10=1 mod 11 2 5=10 mod 11 所以T=10=11-1=p-1 指数函数之特性(续)
指数函数之特性（续） 2.本原元素（素根、原根）Primitive Element(Root) 本原元：若g∈G的阶为T=p-1,则称g为模p的本原元。 (1)当g为modp的本原元时，由g产生的序列<Ex(g)>具有 最大周期（安全性较高）。 (2)对于所有素数p,其本原元必定存在。 (3)当g为模p的本原元且a与p-1互素时，即 gcd(a,p-1)=1,则ga mod p亦必为模p之本原元素。 (4)模p的本原元素个数为p(p-1),称为尤拉商数(Euler Totient Function),表示不大于p-1,且与p-1互素的正 整数之个数，即p(p-1)。 2022/10/9 现代密码学理论与实践-08 16/70
2022/10/9 现代密码学理论与实践-08 16/70 2. 本原元素(素根、原根)Primitive Element (Root) 本原元：若g∈G的阶为T=p-1, 则称g为模p的本原元。 (1) 当g为mod p的本原元时, 由g产生的序列<Ex(g)>具有 最大周期(安全性较高)。 (2) 对于所有素数p, 其本原元必定存在。 (3) 当g为模p的本原元且a与p-1互素时, 即 gcd(a, p-1)=1, 则g a mod p亦必为模p之本原元素。 (4) 模p的本原元素个数为φ(p-1), 称为尤拉商数(Euler Totient Function), 表示不大于p-1, 且与p-1互素的正 整数之个数, 即φ(p-1)。 指数函数之特性(续)