💻 computer science

A Deterministic Complete Graph Hill Cipher with Shift128 Residual Encryption for Universal Binary Files

This paper presents CGHC-S128, a hybrid encryption framework that combines a Complete Graph Hill Cipher with Shift128 residual encryption to securely and efficiently encrypt universal binary files of any size without padding, while ensuring mathematical key invertibility, perfect decryption, and strong resistance to cryptanalytic attacks.

Original authors: Samsul Arifin¹, Paskalis Farelnata Zamasi, Ade Kurniawan, Tiawan Tiawan, Merios Gusan Putra, Edwin Kristianto Sijabat, Dani Lukman Hakim, Dwi Wijonarko

Published 2026-07-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Samsul Arifin¹, Paskalis Farelnata Zamasi, Ade Kurniawan, Tiawan Tiawan, Merios Gusan Putra, Edwin Kristianto Sijabat, Dani Lukman Hakim, Dwi Wijonarko

Original paper licensed under CC BY 4.0 (https://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 are trying to send a secret message to a friend, but instead of just letters, you are sending a whole digital suitcase filled with photos, documents, and videos. In the world of computer security, this is called "encryption." Think of encryption like a magical lock that scrambles your suitcase so that if a thief steals it, they only see a jumbled mess of nonsense. For decades, scientists have used a classic trick called the "Hill Cipher" to do this. It works like a giant math puzzle where you multiply your message by a special grid of numbers (a matrix) to turn it into gibberish. The problem is, this old trick is a bit finicky: it's hard to find the right grid of numbers that can be easily unlocked later, and it gets very confused if your suitcase isn't the exact right size, often forcing you to stuff in extra "padding" material just to make it fit.

Now, imagine a new team of inventors who decided to fix this by looking at a different kind of math: graph theory. Instead of just guessing random number grids, they looked at a "complete graph," which is like a party where every single guest shakes hands with every other guest. They realized that the map of these handshakes creates a perfect, predictable grid that is guaranteed to be unlockable. They combined this with a simple "shift" trick for the leftover bits of data that don't fit perfectly into the main puzzle. The result is a new system called CGHC-S128, designed to lock up any digital file—whether it's a PDF, a video, or a weird binary file—without changing its size or leaving any loose ends.

The New "Party Handshake" Lock

In this study, the researchers from Institut Teknologi Sains Bandung and the University of Jember introduced a new way to protect digital files called CGHC-S128. Think of it as a two-step security system for your digital suitcase.

First, they tackle the main bulk of the file using a "Complete Graph Hill Cipher." In the old days, making a Hill Cipher key was like trying to find a specific key in a dark room full of thousands of keys; you had to keep trying until you found one that worked. This new method is smarter. It uses the structure of a "complete graph"—imagine a party where everyone knows everyone else—to create a key. Because of the way these handshakes work mathematically, the researchers proved that this key is always the right shape to be unlocked later. It's like having a master key that is guaranteed to fit the lock every single time, no guessing required.

Second, they deal with the "leftovers." Digital files are rarely the perfect size to fit neatly into these mathematical grids. Usually, you'd have to add "padding" (extra junk data) to fill the gap, which makes the file bigger. This new system uses a lightweight "Shift128" trick for the remaining bytes. Imagine if you had a few extra socks that didn't fit in the main drawer; instead of throwing them away or stuffing them in a box, you just slide them into a special side pocket that shifts their position. This ensures every single byte of your file is protected without adding any extra bulk.

What They Found in the Lab

The team tested their new system using PDF documents and various sizes of mathematical grids to see how well it worked. They didn't just hope it worked; they ran the numbers to see if the scrambled files looked truly random and if they could be perfectly unscrambled later.

The results were impressive. When they locked the files, the scrambled data looked almost perfectly random. In the world of encryption, "randomness" is measured by a score called entropy. A perfect score is 8.0. Their encrypted files scored a 7.999810, which is incredibly close to perfect. This means the scrambled file looks so much like static noise that it's nearly impossible to guess what's inside.

They also checked how well the system scrambled the data. If you change just one tiny bit of the original file (like changing a single letter), a good lock should change about half of the entire scrambled message. This is called the "avalanche effect." Their system achieved an avalanche effect of 49.9241%, which is almost exactly the ideal 50%. This suggests that even a tiny change in the input creates a massive, unpredictable change in the output, making it very hard for hackers to find patterns.

Furthermore, they tested how sensitive the system was to the key. If a hacker tried to use a key that was just slightly wrong, the system should produce a completely different result. The researchers found that changing the key slightly resulted in a 99.6114% difference in the output, meaning the system is extremely sensitive and secure against guessing games.

The Trade-Off: Speed vs. Size

While the security was excellent, the team also looked at how fast the system runs. They found that encrypting (locking) the file was very fast, even with large grids. However, decrypting (unlocking) the file got slower as the grids got bigger. This is because unlocking requires a complex math operation called "matrix inversion," which is like trying to solve a giant Sudoku puzzle in reverse.

For smaller grids (where the parameter n was between 9 and 99), the system was lightning fast, taking less than a second to lock and unlock a file. But when they tried a very large grid (where n was 999), the unlocking process took over 327 seconds (more than five minutes). If they tried an even larger grid (n = 9999), the system got stuck and couldn't finish unlocking within a reasonable time. This tells us that while the math works perfectly for huge grids, in the real world, you'd want to stick to medium-sized grids to keep things fast.

The Bottom Line

The researchers concluded that their CGHC-S128 system is a solid, mathematically sound way to protect any kind of binary file. It guarantees that the file size stays exactly the same (no extra padding needed), it scrambles the data so well that it looks like random noise, and it can be perfectly restored to the original file every time.

They verified this by locking a PDF file, scrambling it, and then unlocking it. The file came out exactly the same, with the same digital fingerprint (MD5 and SHA-256 hashes) as the original. The team suggests that for practical use, sticking to medium-sized grids offers the best balance between strong security and fast performance. While they didn't test it on every type of file in the universe, their tests on PDFs and binary data suggest this method could be a powerful new tool for keeping digital secrets safe, combining the elegance of graph theory with the practicality of modern file protection.

Technical Summary: A Deterministic Complete Graph Hill Cipher with Shift128 Residual Encryption for Universal Binary Files

Problem Statement
The rapid expansion of digital information exchange necessitates cryptographic techniques capable of securely protecting binary data of arbitrary formats (e.g., PDFs, ZIPs, multimedia) while maintaining computational efficiency. Traditional Hill Cipher schemes, while mathematically elegant, face two primary practical limitations:

Key Generation Difficulty: Generating invertible key matrices modulo $m$ is computationally inefficient, often requiring trial-and-error processes, especially for large dimensions.
Handling Arbitrary File Sizes: Binary files rarely have lengths that are exact multiples of the matrix dimension. Traditional implementations rely on padding, which increases storage requirements and introduces structural artifacts.

Existing hybrid approaches often focus on specific data types (images or video) or rely on unimodular matrices and logistic maps, leaving a gap in universal binary file encryption using graph-theoretic structures with analytically guaranteed invertibility.

Methodology
The paper proposes CGHC-S128, a hybrid encryption framework integrating a Complete Graph Hill Cipher (CGHC) with a Shift128 residual encryption mechanism. The methodology operates directly on binary byte sequences without file-format conversion.

Deterministic Key Generation (Complete Graph Hill Cipher):
- The encryption key is derived from the adjacency matrix of a complete graph $K_N$ , defined as $A(K_N) = J - I$ , where $J$ is the all-one matrix and $I$ is the identity matrix.
- The matrix dimension $N$ is set to $2n$ (an even number).
- Analytical Invertibility: The determinant of this matrix is analytically proven to be $\det(A(K_N)) = (-1)^{N-1}(N-1)$ . Since $N$ is even, $N-1$ is odd. Consequently, $\gcd(N-1, 256) = 1$ , guaranteeing that the matrix is invertible modulo 256 without random generation or trial-and-error.
Partitioning and Hybrid Encryption:
- The plaintext file is partitioned into two segments: $P_H$ (processed by CGHC) and $P_S$ (processed by Shift128).
- Main Segment: The file is divided into blocks of size $N$ . Each block is treated as a vector and encrypted via modular matrix multiplication: $C_i = A(K_N) \times B_i \pmod{256}$ .
- Residual Segment: Any remaining bytes that do not fit into a complete block are processed using the Shift128 Cipher: $c = (p + 128) \pmod{256}$ .
- This approach eliminates the need for padding, preserving the exact file size.
Decryption:
- The modular inverse matrix $A^{-1}(K_N)$ is computed once using Gauss–Jordan elimination.
- Ciphertext blocks are recovered via $B_i = A^{-1}(K_N) \times C_i \pmod{256}$ .
- Residual bytes are restored via $p = (c - 128) \pmod{256}$ .
- The segments are merged to reconstruct the original file exactly.

Key Contributions

Deterministic Key Construction: The paper introduces a method to generate Hill Cipher keys using complete graph adjacency matrices where invertibility is mathematically guaranteed by the parity of the dimension, removing the computational cost of finding valid keys.
Universal Binary Support: The framework supports arbitrary binary file formats by operating directly on byte streams, avoiding the need for format-specific parsing.
Exact File-Size Preservation: By utilizing the Shift128 algorithm for residual bytes, the system encrypts files of any length without padding, ensuring the ciphertext size matches the plaintext size exactly.
Hybrid Architecture: The integration of graph-based matrix transformations for the bulk of the data with a lightweight shift cipher for residuals creates a unified, lossless encryption architecture.

Experimental Results
The framework was evaluated using PDF documents with varying matrix dimensions ( $n$ ) and security metrics:

Correctness: All decryption processes resulted in perfect file reconstruction, verified by 100% matching MD5 and SHA-256 hashes between original and decrypted files.
Statistical Randomness:
- Entropy: The ciphertext achieved an entropy of 7.999810, approaching the theoretical maximum of 8.0.
- Correlation: The correlation coefficient dropped from 0.018530 (original) to -0.000795 (encrypted), indicating the removal of linear dependencies.
- Chi-Square: The value decreased from 30,345.36 to 215.00, with a p-value of 0.967350, confirming a uniform byte distribution.
Diffusion and Sensitivity:
- Avalanche Effect: Measured at 49.9241%, indicating that a single-bit change in input affects nearly half the output bits.
- NPCR (Number of Pixel Change Rate): 99.6061%, exceeding the ideal threshold of 99%.
- UACI (Unified Average Changing Intensity): 33.6548%, close to the ideal 33%.
- Key Sensitivity: 99.6114%, demonstrating that minor key changes produce entirely different ciphertexts.
Performance: Encryption time scales linearly with matrix size. However, decryption time is dominated by the $O(N^3)$ complexity of modular matrix inversion. While efficient for small to moderate dimensions (e.g., $n=9$ to $99$), decryption becomes computationally expensive for very large matrices (e.g., $n=999$ took ~327 seconds).

Significance and Claims
The paper claims that CGHC-S128 offers a mathematically sound and computationally efficient solution for universal binary file encryption. Its primary significance lies in combining deterministic key generation with guaranteed matrix invertibility and lossless decryption within a graph-based architecture.

The authors position the framework as a practical alternative that bridges the gap between the mathematical simplicity of classical ciphers and the security requirements of modern data protection. While acknowledging that large matrix dimensions introduce computational overhead during decryption, the study asserts that for moderate dimensions (specifically $n$ between 9 and 99), the system provides a balanced trade-off between strong cryptographic transformation and execution efficiency. The work is presented as a step toward advancing graph-based cryptography for real-world secure storage and digital security applications, distinct from existing text or image-specific implementations.

The New "Party Handshake" Lock

What They Found in the Lab

The Trade-Off: Speed vs. Size

The Bottom Line

Technical Summary: A Deterministic Complete Graph Hill Cipher with Shift128 Residual Encryption for Universal Binary Files

More like this