# Hide45: A Method for Optimal Payload Data Hiding in Base45 Encoded Strings
## 5 Proposed Algorithm  
In [20] we proposed to consider a printable encoding method based on an alphabet \(\mathbf{A}\) with \(a\) characters that uses a sequence of \(t\) symbols to represent binary strings of \(n\) bits. The total number of sequences of length \(t\) is \(a^{t}\) and there are \(2^{n}\) binary strings of length \(n\): if \(a^{t}>2^{n}\), like in the case of Base45 [21] or Base85 [22], the unused (sometimes called \"illegal\") \(a^{t}-2^{n}\) sequences can be configured to carry extra information, possibly in a reversible manner. Consider an alphabet \(\mathbf{A}\) of \(a\) symbols. Call \(\mathcal{S}\) the set of the \(a^{t}\) possible sequences of length \(t\) made of symbols from \(\mathbf{A}\). Call \(\mathcal{B}\) the set of the \(2^{n}\) binary strings of length \(n\). If \(\mathbf{\mathrm{card}}(\mathcal{S})\geq\mathbf{\mathrm{card}}(\mathcal{B})\) then it is possible to use the sequences in \(\mathcal{S}\) to encode the strings in \(\mathcal{B}\) defining a bijective mapping \(\mu\) (and \(\mu^{-1}\)) between \(\mathcal{B}\) and a subset \(\mathcal{W}\subseteq\mathcal{S}\) such that \(\mathbf{\mathrm{card}}(\mathcal{W})=\mathbf{\mathrm{card}}(\mathcal{B})\) (see Figure 1). In case \(\mathcal{W}\subset\mathcal{S}\) let us call \(\mathcal{D}=\mathcal{S}-\mathcal{W}\
eq\varnothing\) the set of unused sequences in \(\mathcal{S}\). In [20] we proposed to build a one-to-one mapping \(\eta\) between \(\mathcal{D}\) and a subset \(\mathcal{E}\) of \(\mathcal{W}\) that may be used for reversible data hiding into the sequences of \(\mathcal{S}\) (see Figure 2). Note that [20] assumes that \(\mathbf{\mathrm{card}}(\mathcal{D})\leq\mathbf{\mathrm{card}}(\mathcal{W})\) but we relax this constraint in the present work. As an example, let us consider the Base41 encoding proposal [30]: there, three symbols from an alphabet of 41 characters are used to represent 65,536 two octet strings, 256 one octet strings, and 255 bit strings of length from 0 to 7 bits. We may thus see a generalization of the concepts shown in Figure 1. In this embodiment \(\mathcal{S}\) is composed of the \(41^{3}=68\),921 sequences of symbols of Base41; \(\mathcal{B}\) consists of the previously listed \(65\),\(536+256+255=66\),047 binary strings represented by Base41. The subset \(\mathcal{W}\) of \(\mathcal{S}\) is composed by 66,047 strings, each one associated to a binary string with a function \(\mu\) specified in [30]. The remaining \(68\),\(921-66\),\(047=2874\) Base41 sequences constitute the set \(\mathcal{D}\) (Figure 2). When a binary string in \(\mathcal{B}\) is encoded with a sequence \(\mathrm{S}\) in \(\mathcal{E}\) then it is possible to store a bit \(b\) of data by encoding the binary string with \(\mathrm{S}\) if \(b=0\) or with \(\eta(\mathrm{S})\in\mathcal{D}\) if \(b=1\). Instead, if the binary string is encoded with a sequence belonging to \(\mathcal{W}-\mathcal{E}\) no bit is embedded. Figure 1: Mapping \(\mu\) between binary strings of length \(n\) and sequences of \(t\) symbols from an alphabet \(\mathbf{A}\). This method is proposed in [20] where it is also shown the reversibility of the process and the data extraction: please refer to that paper for more details. To improve the data payload, in [23] we proposed to build \(\mathcal{E}\) using the sequences in \(\mathcal{W}\) mapped through \(\mu\) to the most probable binary strings in \(\mathcal{B}\): this depends on the statistic distribution of the binary strings in the input data (e.g., a file) which may be built analyzing a large set of files of the same type (for example, PDF or PNG format).