Extending the ElGamal Cryptosystem to the Third Group of Units of ℤ n \mathbb{Z}_{n}
Jana Hamza, Mohammad EL Hindi, Seifeddine Kadri, Therrar Kadri, Yahya Awad · 2025
Read Extending the ElGamal Cryptosystem to the Third Group of Units of ℤ n \mathbb{Z}_{n} by Jana Hamza, Mohammad EL Hindi, Seifeddine Kadri, Therrar Kadri, Yahya Awad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15202.txt.
Introduction
Jana Hamza and co-authors move a famous encryption scheme onto new mathematical ground. The ElGamal cryptosystem normally lives in the unit group of a number ring, and earlier work had already tried a second such group. Their 2025 paper extends the scheme to the third group of units of the ring of integers modulo n, and argues this setting is more secure than the previous extensions.
The team spells out the arithmetic the new home requires, since every encryption step, from key generation to decryption, must be rebuilt for the new group's operation. Numerical simulations then test the proposal, checking both that the security behaves as claimed and that the scheme runs at a practical speed. The paper belongs to a steady line of work asking how much of classical public-key cryptography survives, and improves, when its algebraic stage is swapped.
Catalog record
| CREATOR | Jana Hamza, Mohammad EL Hindi, Seifeddine Kadri, Therrar Kadri, Yahya Awad |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15202
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extending the ElGamal Cryptosystem to the Third Group of Units of ℤ n \mathbb{Z}_{n} Jana Hamza, Mohammad EL Hindi, Seifeddine Kadri, Therrar Kadri, Yahya Awad Abstract In this paper, we extend the ElGamal cryptosystem to the third group of units of the ring ℤ n \mathbb{Z}_{n} , which we prove to be more secure than the previous extensions. We describe the arithmetic needed in the new setting. We also provide some numerical simulations that shows the security and efficiency of our proposed cryptosystem. Keywords: ElGammal Cryptosystem,Group of units, Order of groups, Cyclic groups, Rings 1 Introduction ElGamal crptosystem was first introduced by T. ElGamal in [ 7 ] . Classically the system was defined on the multiplicative group \mathbb{Z}_{p}^{\ast} , the group of integers modulo a prime p , which is a cyclic group generated by one of its elements, yet this cryptosystem can work in the setting of any cyclic group G . The intractability of the discrete logarithm problem in the group G is the basis for the security of the generalized ElGamal cryptosystem. Moreover, this group G should be carefully chosen so that the operations of G are relatively easy to apply for efficiency. This cryptosystem has been generalized several times over different groups. For more information about these generalizations, we guide the reader for the following ( [ 9 ] , [ 10 ] , [ 11 ] , [ 13 ] , [ 14 ] , [ 16 ] ). In 2006, El-Kassar and Chehade in [ 1 ] introduced a generalization of the group of units of the ring \mathbb{Z}_{n} denoted by the k th group of units of \mathbb{Z}_{n} , U^{k}(\mathbb{Z}_{n}) . For more information about the k th group of units, see ( [ 1 ] , [ 6 ] , [ 9 ] ). The authors in [ 1 ] determined all rings R=\mathbb{Z}_{n} having the 2^{nd} group of units cyclic. These groups were used as an extension of the ElGamal Cryptosystem given by Haraty et al in [ 9 ] . They examined two cases of U^{2}\mathbb{(}{Z}_{n}) : 1. Both U(\mathbb{Z}_{n}) and U^{2}(\mathbb{Z}_{n}) are cyclic. 2. U^{2}(\mathbb{Z}_{n}) is cyclic, while U(\mathbb{Z}_{n}) is not cyclic. Kadri and El-Kassar in [9] examined the third group of units of \mathbb{Z}_{n} and determined all rings \mathbb{Z}_{n} having U^{3}(\mathbb{Z}_{n}) cyclic and proposed to extend the ElGamal cryptosystem to these groups in the case when they are cyclic. In this paper, we extend the ElGamal cryptosystem to the third group of units of \mathbb{Z}_{n} in the case when they are cyclic. In other words, we modify the ElGamal public key encryption scheme from its classical domain natural to the domain of U^{3}(\mathbb{Z}_{n}) by extending the arithmetic needed for the modifications in this domain. In Section 2 we describe the construction of U^{3}(\mathbb{Z}_{n}) and some theorems related to this group. Section 3 provides the description of our proposed cryptosystem. Finally, Section 4 shows a comparison between our work and some previous results. 2 Preliminaries In this section we give a brief presentation of the Classical ElGamal public key cryptosystem, and the modified ElGamal cryptosystem in the setting of the second group of units of the ring of integers modulo n . The basic algorithms for the functioning of this cryptosystem are described in the following three algorithms: Algorithm 1 Key generation 1. Find a generator \alpha of the \mathbb{Z}_{p}^{\ast} . 2. Select a random integer a , 1\leq a\leq p-2 , and compute a^{\alpha}\bmod{p} . 3. A ’s public key is (p,\alpha,\alpha^{a}) ; A ’s private key is a . The following algorithm shows how B can encrypt a message m to A . Algorithm 2 Encryption 1. Obtain A ’s authentic public key (p,\alpha,\alpha^{a}) . 2. Represent the message as an integer m in the range (0,1,...,p-1) . 3. Select a random integer k , 1\leq k\leq p-2 . 4. Compute \gamma=\alpha^{k}\bmod{p} and \delta=m\cdot(\alpha^{a})^{k}\bmod{p} . 5. Send the ciphertext c=(\gamma,\delta) to A . Here is the algorithm that A uses to recover the message m . Algorithm 3 Decryption 1. Use the private key a to compute \gamma^{p-1-a}\bmod{p}=\gamma^{-a} 2. Recover m by computing (\gamma^{-a})\cdot\delta\bmod{p} . Now for the modified ElGamal cryptosystem over U^{2}(\mathbb{Z}_{n}) , as we mentioned before, two cases were considered. Case 1: U(\mathbb{Z}_{n}) and U^{2}(\mathbb{Z}_{n}) are cyclic : The elements of U^{2}(\mathbb{Z}_{n}) in this case have the form U^{2}(\mathbb{Z}_{n})=\{r^{i}\bmod n:\gcd(i,\varphi(n))=1\} , where r is the generator of U(\mathbb{Z}_{n}) . The extended ElGamal public key cryptosystem over U^{2}(\mathbb{Z}_{n}) follows the next four algorithms: Algorithm 4 Generator of U^{2}(\mathbb{Z}_{n}) 1. Find a generator \theta_{1} of U(\mathbb{Z}_{n}) . 2. Write the order of U^{2}(\mathbb{Z}_{n}) as p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{k}^{\alpha_{k}} . 3. Select a random integer s , 0\leq s\leq\varphi(n)-1 , (s,\varphi(n))=1 . 4. For j=1 to i , do: 4.1. Compute \theta_{1}^{N/p_{j}}\bmod n . 4.2. If \theta_{1}^{s(N/p_{j})}\bmod n\equiv\theta_{1} , then go to step 3 . 5. Return s . For the key generation, use this algorithm: Algorithm 5 Key generation 1. Find a generator \theta_{1} of U(\mathbb{Z}_{n}) . 2. Find s using the previous algorithm. 3. Compute the order of U^{2}(\mathbb{Z}_{n}) using \varphi^{2}(n) . 4. Select a random integer a , 2\leq a\leq\varphi^{2}(n)-1 , and compute f=s^{a}(\bmod\varphi(n)) . 5. A ’s public key is (n,\theta_{1},s,f) and A ’s private key is a . For the encryption of a message m , the following algorithm is used: Algorithm 6 Encryption 1. B obtains A ’s authentic public key (n,\theta_{1},s,f) . 2. Represent the message as an integer in U^{2}(\mathbb{Z}_{n}) . 3. Select a random integer k , 2\leq k\leq\varphi^{2}(n)-1 . 4. Compute q=s^{k}(\bmod\varphi(n)),r=f^{k}(\bmod\varphi(n)), \gamma=\theta^{k}=\theta_{1}^{q}(\bmod n) and \delta=m^{r}(\bmod n) . 5. Send the cipher text c=(q,\delta) to A . Finally, to decrypt the message, use the next algorithm: Algorithm 7 Decryption 1. Use the private key a to compute b=\varphi^{2}(n)-a . 2. Recover the message by computing t=q^{b}(\bmod\varphi(n)) and \delta^{t}(\bmod n) . Case 2 : U^{2}(\mathbb{Z}_{n}) is cyclic, while U(\mathbb{Z}_{n}) is not cyclic: The extended ElGamal public key cryptosystem over U^{2}(\mathbb{Z}_{n}) follows the next four algorithms: Algorithm 8 Generator of U^{2}(\mathbb{Z}_{n}) 1. Find a generator \theta_{1} of U(\mathbb{Z}_{n}) . 2. Write the order of U^{2}(\mathbb{Z}_{n}) as p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{k}^{\alpha_{k}} . 3. Select a random integer s , 0\leq s\leq\varphi(p)-1 , (s,\varphi(p))=1 . 4. For j=1 to i , do: 4.1. Compute \theta_{1}^{N/p_{j}}\bmod p . 4.2. If \theta_{1}^{s(N/p_{j})}\bmod p\equiv\theta_{1} , then go to step 3 . 5. Use the Chinese Remainder Theorem to find \theta , and s by solving the system of congruencies: x\equiv 2(\bmod 3) and x\equiv\theta_{1}^{s}(\bmod p) . 6. return s . Now, for the key generation, A uses the following algorithm: Algorithm 9 Key generation 1. Find a generator \theta_{1} of U(\mathbb{Z}_{p}) . 2. Find s using the previous algorithm. 3. Compute the order of U^{2}(\mathbb{Z}_{p}) using \varphi^{2}(p) . 4. Select a random integer a , 2\leq a\leq\varphi^{2}(p)-1 , and compute f=s^{a}(\bmod\varphi(p)) . 5. A ’s public key is (p,\theta_{1},s,f) and A ’s private key is a . For B to encrypt a message m for A , he uses this algorithm: Algorithm 10 Encryption 1. B obtains A ’s authentic public key (n,\theta_{1},s,f) . 2. Represent the message as an integer in U^{2}(\mathbb{Z}_{p}) . 3. Select a random integer k , 2\leq k\leq\varphi^{2}(p)-1 . 4. Compute q=s^{k}(\bmod\varphi(p)),r=f^{k}(\bmod\varphi(p)), \gamma=\theta^{k}=\theta_{1}^{q}(\bmod p) and