Algorithm

Algorithm#

In this part of the documentation, we will try to explain what is going on under the hood of this library.

1. Mathematical Foundation#

1.1 The Special Property of 1/89#

The method is based on an interesting mathematical property of the number 89, which appears in its own decimal expansion when written as \(\frac{1}{89}\):

\[\frac{1}{89} = 0.011235955056179775280898876404494382022471910112359...\]

Key properties: - The decimal expansion has a period of 44 digits - The number “89” appears symmetrically in the middle of this period - This creates a natural cryptographic seed

1.2 Generalization to \(\frac{1}{n9}\)#

The method extends this property to numbers of the form \(\frac{1}{n9}\), where \(n\) is a positive integer. Many such numbers exhibit similar symmetric properties with “89” appearing in their decimal expansions.

\[\frac{1}{49} = 0.\underbrace{02040816326530612244}_{\text{20 characters here}}\underbrace{\textbf{89}}_{+2}\underbrace{79591836734693877551}_{\text{the next 20}}...\]

  • Period: 42 digits

  • Symmetric pattern around “89”

2. Cryptographic Algorithm#

2.1 Key Generation#

For a given \(n\), three cryptographic keys are generated: 1. Primary key \(n\) (determines which \(\frac{1}{n9}\) fraction to use) 2. Matrix key \(K\) (2×2 matrix derived from decimal digits) 3. Caesar shift key \(p\) (derived from period length)

2.2 Matrix Formation#

The key matrix \(K\) is formed using four digits from the decimal expansion:

\[\begin{split}K = \begin{bmatrix} u & v \\ x & y \end{bmatrix}\end{split}\]

where \(uv\) and \(xy\) are two-digit numbers selected from positions around “89” in the expansion.

Requirements for \(K\): - \(\text{det}(K) \neq 0\) (matrix must be invertible) - \(\text{det}(K) = u \cdot y - v \cdot x\)

2.3 Caesar Shift Calculation#

For period \(d\) of \(\frac{1}{n9}\):

\[p = d \mod 10\]

3. Encryption Process#

3.1 Message Preprocessing#

  1. Convert message to numerical values using alphabet mapping

  2. Apply Caesar shift of \(p\) positions

  3. Form matrix \(M\) of dimensions \(2 \times \lceil \frac{m}{2} \rceil\) where \(m\) is message length

3.2 Matrix Encryption#

The encryption process uses Hill cipher methodology:

\[C = K \cdot M\]

where: - \(C\) is the encrypted matrix - \(K\) is the key matrix - \(M\) is the message matrix

4. Decryption Process#

4.1 Matrix Decryption#

The decryption process involves: 1. Computing \(K^{-1}\) (inverse of key matrix) 2. Computing \(M = K^{-1} \cdot C\) 3. Applying reverse Caesar shift of \(-p\) positions

For \(2 \times 2\) matrix \(K\):

\[\begin{split}K^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\end{split}\]

5. Security Analysis#

5.1 Security Features#

  1. Multiple layers of encryption: - Hill cipher (matrix multiplication) - Caesar shift - Symmetric number properties

  2. Three independent keys: - \(n\) (primary key) - \(K\) (matrix key) - \(p\) (shift key)

5.2 Cryptographic Strength#

The method combines: - Modular arithmetic (Caesar cipher) - Linear algebra (Hill cipher) - Number theory (decimal expansion properties)

Making it resistant to: - Known plaintext attacks - Brute force attempts (due to multiple key layers)

6. Implementation Example#

For \(n = 4\) (using \(\frac{1}{49}\)):

Step 1: Decimal Expansion

We begin by considering the decimal expansion of \(\frac{1}{49}\):

\[\frac{1}{49} = 0.\underbrace{02040816326530612244}_{\text{20 characters here}}\underbrace{\textbf{89}}_{+2}\underbrace{79591836734693877551}_{\text{the next 20}}...\]

Step 2: Key Generation

  • Primary key \(n = 4\)

  • Matrix key \(K\) is derived from the decimal digits around “89”. We will extract two two-digit numbers, say \(u = 4\), \(v = 4\), \(x = 7\), and \(y = 9\), from the expansion.

Thus, the key matrix \(K\) is:

\[\begin{split}K = \begin{bmatrix} 4 & 4 \\ 7 & 9 \end{bmatrix}\end{split}\]

Step 3: Caesar Shift Calculation

The period of the decimal expansion for \(\frac{1}{49}\) is 42 digits. We calculate the Caesar shift key \(p\):

\[p = 42 \mod 10 = 2\]

Step 4: Message Preprocessing

Suppose the message is “HELLO”. First, we map the letters to numerical values (e.g., H = 7, E = 5, L = 12, O = 15):

  • Message: [7, 5, 12, 12, 15]

  • Apply Caesar shift of 2 positions: [9, 7, 14, 14, 17] (by shifting each number by 2)

Step 5: Matrix Formation

Now we form the message matrix \(M\) with dimensions \(2 \times \lceil \frac{5}{2} \rceil = 2 \times 3\):

\[\begin{split}M = \begin{bmatrix} 9 & 14 & 17 \\ 7 & 12 & 14 \end{bmatrix}\end{split}\]

Step 6: Matrix Encryption

The encryption step involves matrix multiplication between the key matrix \(K\) and the message matrix \(M\):

\[\begin{split}C = K \cdot M = \begin{bmatrix} 4 & 4 \\ 7 & 9 \end{bmatrix} \cdot \begin{bmatrix} 9 & 14 & 17 \\ 7 & 12 & 14 \end{bmatrix}\end{split}\]

Step 7: Decryption

To decrypt the message, we compute the inverse of the key matrix \(K^{-1}\). First, we compute the determinant of \(K\):

\[\text{det}(K) = 4 \cdot 9 - 4 \cdot 7 = 8\]

Now, we calculate the inverse of \(K\):

\[\begin{split}K^{-1} = \frac{1}{8} \begin{bmatrix} 9 & -4 \\ -7 & 4 \end{bmatrix}\end{split}\]

Step 8: Final Message Recovery

Using the inverse key matrix, we can now decrypt the encrypted matrix \(C\) by computing \(M = K^{-1} \cdot C\). Finally, we reverse the Caesar shift to obtain the original message.

Contents