Deterministic Algorithm Computing All Generators: Application in Cryptographic Systems Design

• 作者: Boris Verkhovsky
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 数学
• 关键词: DIFFIE-HELLMAN Key Exchange ELGAMAL CRYPTOSYSTEM GENERATOR GENERATOR of PSEUDO-RANDOM Numbers Information Hiding Primitive Element Safe Prime
• 年，卷（期）: 2012,（11）
• 页码范围: 715-719
• 页数: 5页
• 分类号: O1

摘要

Primitive elements play important roles in the Diffie-Hellman protocol for establishment of secret communication keys, in the design of the ElGamal cryptographic system and as generators of pseudo-random numbers. In general, a deterministic algorithm that searches for primitive elements is currently unknown. In information-hiding schemes, where a primitive element is the key factor, there is the freedom in selection of a modulus. This paper provides a fast deterministic algorithm, which computes every primitive element in modular arithmetic with special moduli. The algorithm requires at most O(log2p) digital operations for computation of a generator. In addition, the accelerated-descend algorithm that computes small generators is described in this paper. Several numeric examples and tables illustrate the algorithms and their properties.