RSA, Dickson, LUC and Williams: a study on four polynomial-type public-key cryptosystems

被引:0
|
作者
Günther Brandner
机构
[1] University of Klagenfurt,Mobile Systems Group, Institute of Networked and Embedded Systems
来源
Applicable Algebra in Engineering, Communication and Computing | 2013年 / 24卷
关键词
RSA; Dickson; LUC; Williams; Implementation; Computational effort; Asymmetric cryptosystem; 94A60; 11T71;
D O I
暂无
中图分类号
学科分类号
摘要
In the work at hand we regard the public-key cryptosystems RSA, Dickson, LUC and Williams. The Dickson and LUC systems are, for parameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P=a=1$$\end{document}, identical, except for the fact that the LUC system reduces the degrees of the decryption functions by employing ciphertext-dependent decryption parameters. We show that also for the Dickson system with parameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a=-1$$\end{document} the degrees of the decryption functions can be reduced. Furthermore, we emphasize on the implementability of the systems and apply for Dickson and LUC a seemingly rather unknown algorithm proposed by Montgomery to evaluate recurrences of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_{m+n}=f(X_m,X_n,X_{m-n})$$\end{document}. It turns out that this algorithm reduces the computational efforts of Dickson and LUC compared to commonly applied binary algorithms by about \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$10\,\%$$\end{document}. For the Williams system we propose an algorithm which reduces its computational effort to almost one half compared to other proposed algorithms. Finally, we evaluate the computational efforts of the cryptosystems and show that the improvements proposed in this paper reduce the performance gaps between RSA and Dickson, LUC and Williams considerably.
引用
收藏
页码:17 / 36
页数:19
相关论文
共 2 条
  • [1] RSA, Dickson, LUC and Williams: a study on four polynomial-type public-key cryptosystems
    Brandner, Guenther
    APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2013, 24 (01) : 17 - 36
  • [2] Unified signed-digit number adder for RSA and ECC public-key cryptosystems
    Wang, Yi
    Maskell, Douglas L.
    Leiwo, Jussipekka
    Srikanthan, Thambipillai
    2006 IEEE ASIA PACIFIC CONFERENCE ON CIRCUITS AND SYSTEMS, 2006, : 1655 - +