Formal definition of mono-alphabetic Substitution Cipher

Question

I am trying to write the formal definition for mono-alphabetic Substitution Cipher. I have tried the following

---

$\mathcal{M}:=$ Set of all possible arbitrary length string of English language text, removing all punctuations, numerals, spaces in a string.

$\mathcal{C}=\mathcal{M}$

$\mathcal{K}:=S_{26}$

Let $m=m_1m_2\cdots m_l \in \mathcal{M}$ then

$Enc_{k}(m):=k(m_1)k(m_2)\cdots k(m_l)=c=c_1c_2\cdots c_l \ \ \text{where} \ \ c_i=k(m_i)$

&

$Dec_k(c):=k^{-1}(c_1)k^{-1}(c_2)\cdots k^{-1}(c_l)$

---

My question is how to define the Key generating algorithm $Gen$?

Answer 1

First of all a monoalphabetic substitution cipher can be the concept of monoalphabetic substitution or an encryption only using this technique. That means, Ceaser is a monoalphabetic substitution, because it uses this concept. The difference to the "real" monoalphabetic substitution is, that the key generation is not completely random.

I personally would not define $\mathcal{M}, \mathcal{C}, \mathcal{K}$ the way you did, because I think it's not clear enough. A more mathematically definition could be better:

• $\mathcal{M} = \{ a,b,c,...,z\}^*$ and $\mathcal{C} = \{ a,b,c,...,z\}^*$

I also want to avoid $\mathcal{M} = \mathcal{C}$ because it may be mathematically correct, but could imply a wrong understanding to the reader. I chose $\{ a,b,c,...,z\}^*$, because normally the message space is $\{0,1\}^*$ and I adapted that to the given context.

Now I think you can't define $\mathcal{K} = S_{26}$. What is $S$? I would define $\mathcal{K} = \{f_k\mid k \in \{a,...,z\}\}$, where $f_k$ is a bijective substitution function.

Encryption and Decryption looks good. I would do it like that for a message $m = m_1, ... m_n \in \mathcal{M}$:

• $Enc_k(m)$: $c_i = f_{m_i}(m_i)\forall i \in \{1,...,n\}$
• $Dec_k(c)$: $m_i = f^{-1}_{c_i}(c_i) \forall i \in \{1,...,n\}$

The Generation can then be defined as:

• $Gen$: Choose a random substitution $f_k$ for every $k \in \{a,...,z\}$, so that $f^{-1}_k$ is the bijective inverse function