# Formal definition of mono-alphabetic Substitution Cipher

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$$?

• Select a random key from $\mathcal{K}$? And, $c_i=k(m_i)$ is not clear for substitution cipher. Should be $c_i = (m_i + k) \bmod 26$. Also message encoding and decoding is an impartant part $A=0, B=1,...$ Oct 19, 2021 at 18:59
• Yes this is ok. But is there any algorithm for this?
– user96171
Oct 19, 2021 at 19:01
• language-specific yes, algorithmic saying uniformly select an element from should be enough. Oct 19, 2021 at 19:03
• @kelalaka it's not addition mod 26, you're thinking of the Caesar cipher. Oct 19, 2021 at 21:46
• But I agree that key generation does not need to be part of the algorithm. Oct 19, 2021 at 21:46

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