This post shall explain how the F5 stegosystem (in a simple case) can be implemented in Sage. I thank Carlos Munuera for teaching me these ideas and for many helpful conversations on this matter. I also thank Kyle TuckerDavis [1] for many interesting conversations on this topic.
Steganography, meaning “covered writing,” is the science of secret communication [4]. The medium used to carry the information is called the “cover” or “stegocover” (depending on the context – these are not synonymous terms). The term “digital steganography” refers to secret communication where the cover is a digital media file.
One of the most common systems of digital steganography is the Least Significant Bit (LSB) system. In this system, we assume the “cover” image is represented as a finite sequence of binary vectors of a given length. In other words, a greyscale image is regarded as an array of pixels, where each pixel is represented by a binary vector of a certain fixed length. Each such vector represents a pixel’s brightness in the cover image. The encoder embeds (at most) one bit of information in the least significant bit of eaach vector. Care must be taken with this system to ensure that the changes made do not betray the stegocover, while still maximizing the information hidden.
From a short note of Crandell [3] in 1998, it was realized that errorcorrecting codes can give rise to “stegoschemes”, ie, methods by which a message can be hidden in a digital file efficiently.
Idea in a nutshell: If is the rth binary Hamming code (so, is its length, is its dimension, and is its minimum distance), is a generating matrix, is a check matrix, and is the dual code of , then we take an element to be a cover, and the message we embed is an element of . Once we find a vector of lowest weight such that , we call the stegocover. The stegocover looks a lot like the original cover and “contains” the message m. This will be explained in more detai below.
(This particular scheme is called the F5 stegosystem, and is due to Westfeld.)
Quick background on errorcorrecting, linear, block codes [5]
A linear errorcorrecting block code is a finite dimensional vector space over a finite field with a fixed basis. We assume the finite field is the binary field .
We shall typically think of a such a code as a subspace of with a fixed basis, where is an integer called the length of the code. Moreover, the basis for the ambient space will be the standard basis,
There are two common ways to specify a linear code .

You can give as a vector subspace of by specifying a set of basis vectors for . This set of basis vectors is, by convention, placed as
the rows of a matrix called a generator matrix of . Obviously, the order in which the rows are presented does not
affect the code itself.If are the rows of then
is the set of linear combinations of the row vectors . The vector of coefficients, represents the information you want to encode and transmit.
In other words, encoding of a message can be defined via the generator matrix:
 You can give as a vector subspace of by specifying a matrix for which is the kernel of , . This matrix is called a check matrix of . Again, the order in which the rows are presented does not affect the code itself.
Note that if is a full rank matrix then a full rank check matrix must be a matrix.
These two ways of defining a code are not unrelated.
Fact:
If is the generating matrix for then is a parity check matrix.
Exaample:
Let be an integer and let be a matrix whose columns are all the distinct nonzero vectors of . Then, the code having as its check matrix is called a binary Hamming code, denoted Ham(r,2).
Let , and let
In this form, namely when the columns of are arranged in standard form such that the rightmost entries is the identity matrix , the generator matrix can be quickly found to be
A coset of is a subset of of the form for some . Let be a coset of . Then,
a coset leader of is an element of having smallest Hamming weight.
Fact:
The coset leaders of a Hamming code are those vectors of .
Steganographic systems from errorcorrecting codes
This section basically describes Crandell’s idea [3] in a more formalized language.
Following Munuera’s notation in [6], a steganographic system can be formally defined as
where
 is a set of all possible covers
 is a set of all possible messages
 is a set of all possible keys
 is an embedding function
 is a recovery function
and these all satisfy
for all , , . We will assume that a fixed key is used, and therefore,
the dependence on an element in the keyspace can be ignored. The original cover is called the plain cover, is called the message, and is called the stegocover. Let be , representing both plain covers and stegocovers. Also, let be , where is a fixed integer such that .
Sage examples
How do we compute the emb map?
We need the following Sage function.
def hamming_code_coset_leader(C, y): """ Finds the coset leader of a binary Hamming code C. EXAMPLES: """ F = C.base_ring() n = C.length() k = C.dimension() r = nk V0 = F^r if not(y in V0): RaiseError, "Input vector is not a syndrome." H = C.check_mat() colsH = H.columns() i = colsH.index(y) V = F^n v = V(0) v[i] = F(1) return v
Let and consider the cover . Regarded as a matrix,
V = GF(2)^(63) rhino = V([1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1, 1,1,1,1,0,0,1,1,1, 1,0,0,0,0,0,0,1,1, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,1,1, 1,0,0,1,1,0,0,1,1]) A = matrix(GF(2),7,rhino.list()) matrix_plot(A)
this looks like an elephant or a rhino:
Now we embed the message . First we compute the stegocover:
C = HammingCode(6,GF(2)) H = C.check_mat() V0 = GF(2)^6 m = V0([1,0,1,0,1,0]) z = hamming_code_coset_leader(C, m) stegocover = rhino+z A = matrix(GF(2),7,stegocover.list()) matrix_plot(A)
It looks like another rhino/elephant:
Note only one bit is changed since the Hamming weight of z is at most 1. To recover the message m, just multiply the vector “stegocover” by H.
That’s how you can use Sage to understand the F5 stegosystem, at least in a very simple case.
REFERENCES:
[1] Kyle TuckerDavis, “An analysis of the F5 steganographic system”, Honors Project 20102011
http://www.usna.edu/Users/math/wdj/tuckerdavis/
[2] J. Bierbrauer and J. Fridrich. “Constructing good covering codes for applications in Steganography}. 2006.
http://www.math.mtu.edu/jbierbra/.
[3] Crandall, Ron. “Some Notes on Steganography”. Posted on a Steganography Mailing List, 1998.
http://os.inf.tudresden.de/westfeld/crandall.pdf
[4] Wayner, Peter. Disappearing Cryptography. Morgan Kauffman Publishers. 2009.
[5] Hill, Raymond. A First Course in Coding Theory. Oxford University Press. 1997.
[6] Munuera, Carlos. “Steganography from a Coding Theory Point of View”. 2010.
http://www.singacom.uva.es/oldsite/Actividad/s3cm/s3cm10/10courses.html
[7] Zhang, Weiming and S. Li. “Steganographic Codes a New Problem of Coding Theory”. preprint, 2005.
http://arxiv.org/abs/cs/0505072.