计算机应用 ›› 2013, Vol. 33 ›› Issue (11): 3244-3246.

• 信息安全 • 上一篇    下一篇

关于RSA算法中代数结构的进一步研究

裴东林,李旭   

  1. 兰州文理学院 师范学院,兰州 730000
  • 收稿日期:2013-05-30 修回日期:2013-07-23 出版日期:2013-11-01 发布日期:2013-12-04
  • 通讯作者: 裴东林
  • 作者简介:裴东林(1961-),男,甘肃兰州人,副教授,主要研究方向:密码学、应用数学;李旭(1982-),男,甘肃天水人,讲师,博士研究生,主要研究方向:计算数学。

Further study on algebraic structure of RSA algorithm

PEI Donglin,LI Xu   

  1. Normal College, Lanzhou University of Arts and Science, Lanzhou Gansu 730000, China
  • Received:2013-05-30 Revised:2013-07-23 Online:2013-12-04 Published:2013-11-01
  • Contact: PEI Donglin

摘要: 针对RSA算法中Z*φ(n)的代数结构问题,提出了一种在强素数条件下应用二次剩余理论进行研究的方法。给出了Z*φ(n)中元素阶的计算公式和元素的最大阶表达式,计算了Z*φ(n)中二次剩余的个数和二次非剩余的个数,同时估计出Z*φ(n)中元素的最大阶上限为φ(φ(n))/4并得到了Z*φ(n)中元素的最大阶达到φ(φ(n))/4的一个充要条件。另外还给出了全部二次剩余构成的子群A1成为循环子群的充分条件及Z*φ(n)的一种分解方法。最后证明了Z*φ(n)可由7个二次非剩余元素生成,商群Z*φ(n)/A1是一个Klein八元群。

关键词: RSA算法, 代数结构, 二次剩余, 强素数, 循环群, 欧拉函数

Abstract: By making use of the theory of quadratic residues under the condition of strong prime, a method for studying the algebraic structure of Z*φ(n) of RSA (Rivest-Shamir-Adleman) algorithm was established in this work. A formula to determine the order of element in Z*φ(n) and an expression of maximal order were proposed; in addition, the numbers of quadratic residues and non-residues in the group Z*φ(n) were calculated. This work gave an estimate that the upper bound of maximal order was φ(φ(n))/4 and obtained a necessary and sufficient condition on maximal order being equal to φ(φ(n))/4. Furthermore, a sufficient condition for A1 being cyclic group was presented, where A1 was a subgroup composed of all quadratic residues in Z*φ(n), and a method of the decomposition of Z*φ(n) was also established. Finally, it was proved that the group Z*φ(n) could be generated by seven elements of quadratic non-residues and the quotient group Z*φ(n)/A1 was a Klein group of order 8.

Key words: Rivest-Shamir-Adleman (RSA) algorithm, algebra structure, quadratic residue, strong primer, cyclic group, Euler's Phi-function

中图分类号: