专业信息安全工程师网站|培训机构|服务商(2018信息安全工程师学习QQ群:327677606,客服QQ:270019001)

软题库 培训课程
当前位置:信管网 >> 信息安全工程师 >> 综合知识 >> 文章内容
EIGamal密码体制的数学基础-信息安全工程师知识点
来源:信管网  2018年10月10日  【信管网:项目管理师专业网站所有评论

信息安全工程师知识点:EIGamal密码体制的数学基础

设p为素数,若存在一个正整数α,使得α1,α2,α3,…,αp-1关于模p互不同余,则称α 为模p 的本原元。显而易见若α为模p的本原元,则对于y∈{1 ,2,3···,p-1}一定存在一个正整数X,使得y=ax mod p。

于是我们有如下的运算:

设p为素数,α为模p的本原元,α的幂乘运算为

y=ax mod p, 1≤x≤p-1       (2-44)

则称x为以α为底的模p的对数。求解对数x的运算为

x=logay,1≤y≤p-1       (2-45)

从x计算y是容易的,至多需要2×log2p次乘法运算。可是从y计算x就困难得多,目前己知最快的求解离散对数算法的时间复杂度为:

O(exp((1n p)1/3 1n(1n p))2/3)

可见,只要p足够大,求解离散对数问题是相当图难的。这便是著名的离散对数问题。可见,离散对数问题具有较好的单向性。

由于离散对数问题具有较好的单向性,所以离散对数问题在公钥密码学中得到广泛应用。除了ELGamal密码外,Diiffie-Hellman密钥分配协议和美国数字签名标准算法DSA等也都是建立在离散对数问题之上的。




分享到: 新浪微博 腾讯朋友 收藏本页
发表评论  查看完整评论  

相关内容

推荐文章
合作网站内容