单向函数及其交换性 单向函数的交换性( commutative property) 单向函数本身对近代密码学领域用处不大,但若具 有交换性,则作用大。 定义8.3交换性 令Z为一集合,F为将Z映射到Z本身的函数集合。令 z∈Z,Fx(z)表示此函数集合之第x函数, 若Fx(Fy(z)=F√F×(z),则称此函数集合具有交换性。 例:D(Em)=E(Dm) 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 13/81
mfy@ustc.edu.cn 现代密码学理论与实践 13/81 单向函数的交换性(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 Functio0 定义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)>={90,gl,g2,}为g所产生之序列。因 为G是有限群,Ex(g)不可能不重复,故E(g)产生之序列 为周期序列。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 14/81
mfy@ustc.edu.cn 现代密码学理论与实践 14/81 定义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)产生之序列 为周期序列
指数函数之特性(续) 当存在最小正整数T,使得Eq)=gT=1=g时,称T为 g在G中的阶或序( order)。根据 Fermat' s Theorem, 对于所有g,T必定整除p-1. 例: <Ex(g)>={20,21,22…,210}={1,2,4,8,5,10,9,7,3,6 即:20=1mod11 26=9mod11 21=2mod11 27=7mod11 22=4mod11 28=3mod11 23=8mod11 29=6mod11 24=5mod11 210=1mod11 25=10mod11 所以T=10=11-1=p-1 mfy@ustc.edu.cn 现代密码学理论与实践 15/81
mfy@ustc.edu.cn 现代密码学理论与实践 15/81 当存在最小正整数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} 即：20=1 mod 11 26=9 mod 11 21=2 mod 11 27=7 mod 11 22=4 mod 11 28=3 mod 11 23=8 mod 11 29=6 mod 11 24=5 mod 11 210=1 mod 11 25=10 mod 11 所以T=10=11-1=p-1
指数函数之特性(续) 2.本原元素(素根、原根) Primitive e| ement(Root) 本原元:若g∈G的阶为T=p-1,则称q为模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-1),称为尤拉商数Euer Totient Function),表示不大于p-1,且与p-1互素的 正整数之个数,即φ(p-1)。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 16/81
mfy@ustc.edu.cn 现代密码学理论与实践 16/81 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, 则ga mod p亦必为模p之本原元素。 (4) 模p的本原元素个数为φ(p-1), 称为尤拉商数(Euler Totient Function), 表示不大于p-1, 且与p-1互素的 正整数之个数, 即φ(p-1)
附:求本原元 求一个大素数p很容易,用现成的素性验证算法就 可以了。不过已知一个素数p,求其本原根则很困 难,因为需要将p-1的素因子q1,q2,……qk-1, qk都找出来,然后分别验证gq1modp,gq2 mod p, gqk-1modp, gk mod p,如果都 不等于1,则g是p的一个本原根。而然,如果 p是一个很大的素数,例如128个2进制位的素 数,要分解出p-1的所有素因子来则是一件很困 难的事情。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 17/81
mfy@ustc.edu.cn 现代密码学理论与实践 17/81 求一个大素数 p 很容易，用现成的素性验证算法就 可以了。不过已知一个素数 p，求其本原根则很困 难，因为需要将 p - 1 的素因子 q1，q2，……qk-1， qk都找出来，然后分别验证 gq 1 mod p， gq 2 mod p， ……gq k-1 mod p， gq k mod p，如果都 不等于 1，则 g 是 p 的一个本原根。而然，如果 p 是一个很大的素数，例如 128 个 2 进制位的素 数，要分解出 p - 1 的所有素因子来则是一件很困 难的事情