1
$\begingroup$

I know that the message space is the set of all possible messages, but I'm not sure how to generally define it, rather than for a specific cipher. For example, I've seen $$\{\forall c \in A\}$$, where "$A$" is the set of characters being used.
But I think there should be a superscript at the end to denote the length. Would this be correct?

$\endgroup$
1
$\begingroup$

How to generally define it

Modern applied cryptography usually defines the (unbounded) message space as: $$\mathcal M=\{0,1\}^*$$ where the star denotes you can have arbitrary lengths. Formally, $A^*:=\bigcup_{n\geq0}A^n, A^0=\varepsilon,A^{n+1}=A^n\cdot A,n\in\mathbb N$ where $\cdot$ denotes concatenation.


If you ask somebody who's really into the theory of programming languages, they're gonna basically say you the same, but will probably replace the $\{0,1\}$ with an arbitrary alphabet $A$.


Now to the formula you asked about: $$\{\forall c\in A\}$$

This is not only syntactically wrong (a quantor always needs an accompanying statement), but also makes no sense at all. After all, you're saying that "the set consisting of 'for all c in A' " which is at most a set of syntactically wrong logical formulae. However if we were to leave the $\forall$ away, you basically wouldn't have gained anything over a plain use of $A$, as the set consisting of all elements in A basically is just A.
If $A$ is assumed to be an alphabet, you'd indeed need a length qualifier, something like the star in the above notation or a concrete instance where you'd fix the length to some (arbitrary) value $n$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.