公钥密码(中Elgamal).ppt

文档介绍：密码学第十讲公钥密码 ——******@:每个函数值都存在唯一的逆,并且计算函数值是容易的但求逆却是不可行的: 已知X,求Y=f(X)容易已知Y,求X=f-1(Y)不可行单向函数单向函数是求逆困难的函数,而单向陷门函数(Trapdoorone-wayfunction),是在不知陷门信息下求逆困难的函数,当知道陷门信息后,求逆是易于实现的。单向限门函数是一族可逆函数fk,=fk(x)易于计算(当k和x已知)=fk-1(y)易于计算(当k和y已知)=fk-1(y)计算上不可行(y已知但k未知)研究公钥密码算法就是找出合适的单向限门函数单向陷门函数背包问题(Knapsackproblem)已被攻破大整数分解问题(TheIntegerFactorizationProblem)RSA密码离散对数问题有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem)——ElGamal密码定义在有限域的椭圆曲线上的离散对数问题(urveDiscreteLogarithmProblem)——ECC密码公钥密码基于的数学难题理论上:不能证明单向函数一定存在;实际上:只要函数的单向性足够工程应用就行;实际上已找到的单向性足够的函数有:①合数的因子分解问题大素数的乘积容易计算(pqn),而大合数的因子分解困难(npq)。②有限域上的离散对数问题有限域上大素数的幂乘容易计算(abc),而对数计算困难(logacb)。单向函数研究现状合数的因子分解问题单向函数研究现状有限域上的离散对数问题例如GF(19)中模19的整数幂单向函数研究现状1、基本情况:ELGamal密码是除了RSA密码之外最有代表性的公开密钥密码。ELGamal密码建立在离散对数的困难性之上。RSA密码建立在大合数分解的困难性之上。ELGamal公钥密码的基本情况2、离散对数问题:①设p为素数,则模p的剩余构成域:Fp={0,1,2,…,p-1}Fp的非零元构成循环群Fp*Fp*={α,α2,α3,,αp-1},则称α为Fp*的生成元或模p的本原元(根)。②设p为素数,α为模p的本原元,α的幂乘运算为Y=αXmodp,1≤X≤p-1,则称X为以α为底的模p的对数。离散对数问题