A 3-digit number $x$ is encrypted as $y \equiv a \cdot x + b \pmod N$ and decrypted as $x \equiv a^{-1}(y - b) \pmod N$, with public $N = 11 \cdot 23 \cdot 41 = 10373$ and secret key $(a; b)$, where $a, b \in \{2, \dots, N-1\}$. Is this symmetric or asymmetric, and exactly how many keys are possible?

Question

Accepted Answer

Symmetric, because sender and receiver must share the same secret $(a; b)$. There are $(N - 2)(\varphi(N) - 1) = 10371 \cdot 8799 = 91\,254\,429$ keys.
Symmetric: both sides need the same secret pair $(a; b)$. That the receiver computes $a^{-1} \bmod N$ from it changes nothing: whoever can decrypt can also encrypt, and vice versa. A public $N$ does not make it asymmetric.
Choices for $b$: any value in $\{2, \dots, N-1\}$, so $N - 2 = 10371$.
Choices for $a$: $a$ must be invertible mod $N$, i.e. $\gcd(a, N) = 1$. There are $\varphi(N)$ such numbers in $\{1, \dots, N-1\}$; excluding $a = 1$ leaves $\varphi(N) - 1$:
$$\varphi(11 \cdot 23 \cdot 41) = 10 \cdot 22 \cdot 40 = 8800 \;\Rightarrow\; 8799$$
Total: $10371 \cdot 8799 = 91\,254\,429$ keys, about $2^{26.4}$. That is trivially brute-forceable, and with only 3-digit plaintexts a single known plaintext-ciphertext pair narrows things down fast.
Gotcha: $\varphi$ of a product of distinct primes is the product of $(p_i - 1)$. Forgetting to exclude non-invertible $a$ (multiples of 11, 23 or 41) is the classic mistake.