Cipher text only attack?

Question

I would like to get some feedback on the process by which I attempted to solve the problem below, I think my answer is wrong (even though I checked by re encrypting it) as its supposed to be a meaningful word.

encrypted using an affine map on digraphs in the 37-letter alphabet {0,1,...,9,a,b,...,z, }.The letters A-Z have numerical equivalents 10−35, and blank space = 36.A digraph whose two characters have numerical equivalents x and y corresponds to $37⋅x+y$ Most frequent digraphs are GW and R3 in that order and the most common digraphs in English are TH and HE in that order. Find deciphering key and read the message

Here is what I did:

I have tried to use frequency analysis to get my equations, one of which was $a=(393−1922mod1369)$

which I solved using the extended euclidean algorithm.

I then did the final decryption to get 92uqd98uowud as my solution.

Answer 1

The encoded digraphs live in $\mathbb Z_{37^2}$. To permute elements in this space, we have a line which maps ciphertext to plaintext: $$ P = aC + b \pmod {37^2} $$

Frequency analysis provides us two points on this line: $$ (c_1, p_1) = (624, 1090) \\ (c_2, p_2) = (1002, 643) $$

Two points uniquely determine a line, so we can solve for the unknowns $a$ and $b$ in the usual way: $$ a = \frac{p_2 - p_1}{c_2 - c_1} \pmod{37^2} \\ b = p_1 - ac_1 \pmod{37^2} $$

Using the below PowerShell script, we find that $a = 1031$ and $b = 1176$, with a plaintext of:

GZ U WON 12P

---

$ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ "
$SIZE = $ALPHABET.Length * $ALPHABET.Length

function Encode-Digraph([string]$Digraph){
    $x = $ALPHABET.IndexOf($Digraph[0])
    $y = $ALPHABET.IndexOf($Digraph[1])
    $encoded = $ALPHABET.Length * $x + $y
    return $encoded
}

function Decode-Digraph([int]$Encoded){
    $y = $Encoded % $ALPHABET.Length
    $x = ($Encoded - $y) / $ALPHABET.Length
    return $ALPHABET[$x] + $ALPHABET[$y]
}

function invmod($a,$n){
    if ([int]$n -lt 0) {$n = -$n}
    if ([int]$a -lt 0) {$a = $n - ((-$a) % $n)}

    $t = 0
    $nt = 1
    $r = $n
    $nr = $a % $n
    while ($nr -ne 0) {
        $q = [Math]::truncate($r/$nr)
        $tmp = $nt
        $nt = $t - $q*$nt
        $t = $tmp
        $tmp = $nr
        $nr = $r - $q*$nr
        $r = $tmp
    }
    if ($r -gt 1) {return -1}
    if ($t -lt 0) {$t += $n}
    return $t
}

function Get-Remainder([int]$X) {
    $x = $X % $SIZE
    if ($x -lt 0) {
        $x += $SIZE
    }
    return $x
}

function Modular-Divide([int]$A, [int]$B) {
    $a = Get-Remainder $A
    $b = Get-Remainder $B
    $inv = invmod $b $SIZE
    return Get-Remainder ($a * $inv)
}

$c1 = Encode-Digraph -Digraph "GW"
$c2 = Encode-Digraph -Digraph "R3"
$p1 = Encode-Digraph -Digraph "TH"
$p2 = Encode-Digraph -Digraph "HE"

# Solve P = aC + b.
$a = Modular-Divide ($p2 - $p1) ($c2 - $c1)
$b = Get-Remainder ($p1 - (Get-Remainder ($a*$c1)))
Write-Host "Equation of line: P = $a * C + $b (mod $SIZE)"

# Decrypt.
$ciphertext = "9LIMKTOG5DNN"
$decodedPlainDigraphs = [regex]::Matches($ciphertext, '..') | % {
    $cipherDigraph = $_.Value
    $encodedCipherDigraph = Encode-Digraph $cipherDigraph
    $encodedPlainDigraph = Get-Remainder ($a * $encodedCipherDigraph + $b)
    $decodedPlainDigraph = Decode-Digraph $encodedPlainDigraph
    return $decodedPlainDigraph
}

Write-Host "Plaintext: '$($decodedPlainDigraphs -join '')'"