🔢 mathematics

A Matrix-Based Polyalphabetic Algorithm for Information Encoding and Decoding Using Number Sequences

This paper proposes a computationally efficient matrix-based polyalphabetic encryption scheme that utilizes Fibonacci, Leonardo, Jacobsthal, and Lucas number sequences for character substitution and block transformation to achieve improved distributional behavior and reduced frequency concentration compared to standard monoalphabetic methods.

Original authors: Muhammet Karagöz, Nihal Özgür

Published 2026-06-25

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Muhammet Karagöz, Nihal Özgür

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a secret message you want to send, but you're worried that someone might intercept it and figure out what it says just by counting how often certain letters appear (like noticing that "E" is the most common letter in English). This paper introduces a new way to hide messages that makes that kind of counting almost useless.

Here is a simple breakdown of how their method works, using everyday analogies:

1. The Three Different "Dictionaries"

Usually, when you encrypt a message, you might swap the letter "A" for the number "5" every single time. That's easy to crack.

This new method uses three different "dictionaries" (based on famous number patterns like Fibonacci, Leonardo, and Jacobsthal sequences) to translate letters into numbers.

The Analogy: Imagine you are translating a sentence into three different languages. Sometimes "A" becomes "5," sometimes it becomes "15," and sometimes it becomes "43."
The Trick: Which dictionary you use depends on two things:
1. Where the letter is in the message (its row and column in a grid).
2. How many times you've seen that letter before.
The Result: Even if the letter "A" appears 10 times in your message, it will likely turn into 10 different numbers. This breaks the pattern that code-breakers rely on.

2. The "Magic Grid" and the "Hidden Piece"

Once the letters are turned into numbers, the message is arranged into a big square grid (like a Sudoku board), which is then chopped up into smaller 3x3 squares.

The Transformation: Each small square is mixed up using a special mathematical "shaker" (called a Leonardo Q-matrix). The way it gets shaken depends on a secret key that changes for every single small square.
The Hidden Piece: To make sure the message can be put back together perfectly, the authors hide one number in each small square. Instead of sending that hidden number, they send a "checksum" (a special math result called a determinant) that allows the receiver to calculate exactly what that missing number was.
The Analogy: Imagine you have a puzzle where you remove one piece and write down a clue on the box that tells you exactly what that piece looks like. You send the box with the missing piece and the clue. The receiver uses the clue to reconstruct the missing piece and solve the puzzle.

3. The "Word Separator" Mystery

In normal text, spaces between words are obvious. In this system, spaces are replaced by a special sequence of numbers (based on Lucas numbers).

The Twist: These space-numbers aren't the same every time. They change based on a secret "seed" shared only between the sender and receiver.
The Benefit: An eavesdropper can't tell where one word ends and another begins because the "spaces" look like random, shifting numbers.

4. Why It's Fast and Secure

The "Collision-Free" Modulus: To keep the numbers from getting too huge and slowing down the computer, they use a specific "modulo" (a mathematical limit, like a clock that resets after 10,159). They carefully chose this limit so that no two different letters ever accidentally turn into the same number.
The Avalanche Effect: The paper tested what happens if you change just one tiny thing in the secret key (like changing a single digit). The result? The entire encrypted message changes drastically—about 50% of the numbers flip. This is like changing one ingredient in a cake recipe and ending up with a completely different dessert. This makes it very hard to guess the key.

What the Paper Actually Found

The authors ran tests on a standard English text and compared their method to older, simpler encryption methods.

Frequency Smearing: In old methods, the most common letters in the encrypted message still stood out. In this new method, the "most common" letters were spread out so thinly that they looked like random noise.
Speed: By using their specific mathematical limit, the computer could process the message about 7 to 8 times faster than if they had used the raw, massive numbers without the limit.
Security: The statistical tests showed that the encrypted message looked much more like random noise than a standard code, making it very difficult to crack using traditional frequency analysis.

In short: This paper proposes a new way to lock up messages by shuffling letters through three different number systems, hiding one piece of every puzzle, and changing the rules for every single block of text. The result is a message that looks like random gibberish to anyone who doesn't have the specific key to unlock it.

Technical Summary: A Matrix-Based Polyalphabetic Algorithm for Information Encoding and Decoding Using Number Sequences

Problem Statement
The paper addresses the vulnerability of standard monoalphabetic substitution ciphers to frequency analysis. In monoalphabetic systems, the same plaintext character always maps to the same ciphertext symbol, preserving the statistical distribution of the source language and allowing attackers to deduce the key through frequency counts. While polyalphabetic ciphers (like Vigenère) mitigate this by using multiple substitution alphabets, the authors propose a novel approach that combines polyalphabetic substitution with homophonic behavior. The goal is to distribute repeated plaintext symbols across different numerical representations based on position and occurrence count, thereby flattening the frequency distribution of the ciphertext and enhancing resistance to statistical cryptanalysis.

Methodology
The proposed scheme, termed FLLJ-POLY, is a matrix-based polyalphabetic encryption algorithm that leverages four specific integer sequences: Fibonacci, Lucas, Leonardo, and Jacobsthal. The methodology proceeds through the following stages:

Theoretical Foundation and Sequence Separation:
The authors establish that for sufficiently large indices, the Leonardo, Fibonacci, and Jacobsthal sequences generate pairwise disjoint sets of integers. Lucas numbers are reserved specifically for encoding word separators. A collision-free public prime modulus $P$ (e.g., $P=10159$ ) is selected to ensure that the modular reduction of these distinct sequence values remains injective, preserving the ability to uniquely decode the symbols.
Message Preparation and Substitution:
The plaintext is converted into a square matrix $M$ of size $3m \times 3m$ , with word separators denoted by a specific symbol (e.g., $\ast$ ).
- Character Substitution: Each letter is replaced by a value from one of three sequence-based alphabets (Fibonacci, Leonardo, or Jacobsthal). The choice of alphabet is determined by a position-dependent selector function:
  $\sigma = (v^2 + (i - 1) + (j - 1)) \pmod 3$
  where $v$ is the occurrence count of the character, and $(i, j)$ are its row and column indices. This mechanism ensures that the same character maps to different numerical values depending on its position and frequency, introducing homophonic behavior.
- Separator Encoding: Word separators are encoded using Lucas numbers with indices shifted by a key-dependent parameter $a_0$ , preventing predictable patterns in word boundaries.
Matrix Transformation and Encryption:
The substituted matrix is divided into $3 \times 3$ submatrices. A secret key sequence $a_0, a_1, \dots, a_{k-1}$ is generated using a pre-shared seed $s$ and a prime $p$ via a non-linear recurrence relation involving Leonardo numbers:
$a_{i+1} = (L_s a_i + a_i^2 + i) \pmod p$
Each $3 \times 3$ block is encrypted by multiplying it with a power of the Leonardo $Q$ -matrix ( $Q^{a_{j-1}}$ ) modulo $P$ .
Ciphertext Construction:
To reduce transmission size while maintaining integrity, the algorithm transmits the determinant of each encrypted block along with eight of the nine matrix entries. The missing "hidden" entry is recovered by the receiver using the determinant condition, provided the corresponding cofactor is non-zero modulo $P$ .

Key Contributions

Novel Sequence Integration: The paper introduces a unified framework utilizing Fibonacci, Leonardo, Jacobsthal, and Lucas sequences simultaneously, with rigorous proofs (Theorems 2.1–2.5) demonstrating the disjointness of their terms for specific index ranges.
Homophonic-Polyalphabetic Hybrid: The scheme combines polyalphabetic substitution (changing alphabets) with homophonic substitution (multiple representations for one symbol) via a quadratic selector function, effectively reducing frequency concentration.
Non-Linear Key Generation: The block keys are derived from a quadratic, non-autonomous recurrence relation, adding complexity to the key stream compared to linear congruential generators.
Efficient Modular Implementation: By employing a collision-free prime $P$ , the authors ensure that all operations remain within native integer arithmetic bounds, avoiding the computational overhead of large-integer arithmetic required by unreduced sequence values.

Results
The authors present a worked example and preliminary statistical analysis using a 576-character English text:

Statistical Security: The scheme significantly lowers the Index of Coincidence (I.C.) to approximately 0.0153, compared to 0.0667 for standard English and 0.0450 for a Vigenère cipher with a short key. The normalized Chi-square statistic ( $\chi^2/c$ ) is reduced by approximately 70.6% compared to monoalphabetic substitution. Shannon entropy efficiency reaches 87.8%, indicating a near-uniform distribution of ciphertext symbols.
Avalanche Effect: Small perturbations in the secret key parameters ( $s$ or $p$ ) result in ciphertext changes affecting approximately 48.5% of the bits on average, approaching the ideal Strict Avalanche Criterion of 50%.
Computational Performance: The modular implementation achieves a 7–8× speedup in encoding and decoding times compared to an unreduced implementation using large-integer arithmetic (GMP), with encoding times for a 500-character message dropping from ~1.47 ms to ~0.21 ms.

Significance and Claims
The paper positions FLLJ-POLY as a mathematically grounded alternative to standard substitution ciphers. The authors claim that the construction provides improved distributional behavior and computational efficiency. They emphasize that the primary contribution is the establishment of a rigorous number-theoretic basis for the encoding procedure, utilizing the disjointness properties of integer sequences to justify distinct numerical alphabets.

The authors explicitly state that the work focuses on developing and justifying the mathematical structure of the scheme rather than providing an exhaustive cryptanalytic treatment. Consequently, they do not claim the system is unbreakable; instead, they note that rigorous analysis against advanced attacks (such as known-plaintext, chosen-plaintext, and algebraic attacks) remains a subject for future work. The significance lies in demonstrating a reproducible, matrix-based framework that effectively flattens frequency distributions and offers a modular, efficient implementation strategy.