Algebraic Cryptanalysis of an Elliptic-Curve-Based Polyalphabetic Hill Cipher over Z/26Z

Abstract

This study revisits a Hill-type polyalphabetic cipher in which the 26 uppercase letters are represented by points of the elliptic curve y² = x³ + 9x + 1 over F₂₉. We prove that the selected curve group contains 26 elements and that B = (0,1) has order 26; hence the group is cyclic and isomorphic to Z₂₆. Under the generator-coordinate map, the point-valued matrix transformation is therefore conjugate to the classical Hill transformation over Z₂₆. This characterization yields explicit plaintext-based attacks. Under the stated fixed-key and public-mapping assumptions, m chosen plaintext blocks recover an m × m key exactly. For the reported 4 × 4 key, a known-plaintext attack also recovers the key from the first four plaintext-ciphertext block pairs because the resulting plaintext matrix is invertible modulo 26. For the Indonesian Constitution benchmark, a reproducible experiment using 100 random invertible keys for each block size m = 2, 3, 4, 5 shows that mean ciphertext entropy increases from 4.5592 to 4.6769 bits per symbol and the index of coincidence approaches 1/26, while chosen-plaintext key recovery remains 100%. Thus, flatter symbol frequencies do not remove the linear weakness of the construction or provide elliptic-curve discrete-logarithm security.