decoding an encrypted text with modulo

Question

A  B  C  D  E  F  G  H  I  J  K  L  M  N  O
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

P  Q  R  S  T  U  V  W  X  Y  Z  Ä  Ö  Ü  ß
16 17 18 19 20 21 22 23 24 25 26 27 28 29 00

A encryption method relates a letter Ω to letter $Δ\equiv aΩ + d$ $(mod 30)$ with $a, d\in {\Bbb N}$.
$gcd(a, 30) = 1$

Decode following text:
PXFHKAR ARXHKAR XßIJKAR

Any hints how to decode it?

Answer 1

I "brute forced" it. We apply all $k\Delta+c \pmod {30}$ for $k,c \in \{0,1,\ldots,29\}$ and $k$ coprime to $30$. This gives $8 \times 30$ items to inspect. I inspected the list, and it turns out $k=13$ and $c=21$ works.

Answer 2

This is an affine cipher. This is a simple substitution cipher and in general is cryptalanyzed with frequency analysis.

$\Delta = a\Omega+d (\text{mod}30)\Rightarrow \Delta-d=a\Omega(\text{mod}30)$. Since $\text{gcd}(a,30)=1$, $a$ has an inverse $a^{-1}$ modulo 30. So, $$ \Omega = a^{-1}(\Delta-d)(\text{mod}30)$$

Here, $\Omega$ is a plaintext digit and $\Delta$ is its corresponding ciphertext digit. So, you have an equation with which from ciphertext you can find the plaintext. If you find two (plainletter, cryptoletter) pairs, then you can solve the equation and find $a$ and $d$.

For each language there is a letter frequency table. I guess that the plaintext in question is in German. What you have to do now is to count how many times each cipherletter appears on the ciphertext. The one with most appearances might correspond to the plainletter with highest frequency in German (which is "e"). So, once you have a pair (e,some cryptoletter), you can do the same for the next most frequent letter in German. Attention, that this might not give you the solution for sure, especially when the ciphertext is as short as yours. You might need to make many trials or notice patterns, too. For example, the "KAR" sequence appears a lot! Can you think of a corresponding plaintext for this sequence?