Application to McEliece Public Key Cryptosystem

We follow section 1.2 of [CHA].

Here is a brief description of this cryptosystem. Alice is sending a message to Bob. Eve is trying to read Alice's message. Given is a $ [n,k,d]$ binary code with generator matrix $ G$ and also given is a decoding algorithm that corrects up to $ t$ errors. As input parameters are an invertible $ k\times k$ matrix $ S$ and an $ n\times n$ permutation matrix $ P$. The triplet $ (S,G,P)$ will be the secret key and the pair $ (t,\hat{G}=SGP)$ will be the public key. Everyone knows the public key, but Alice and Bob are the only two who know the secret key. For Alice to transmit a $ k$ bit message $ m$, she sends the cipher text $ c=m\hat{G}+e$, where $ e$ is a random vector of weight at most $ t$. To decipher the cipher text Bob decodes $ cP^{-1}=mSG+eP^{-1}$ using the given algorithm.

To decrypt an encoded message, consider the matrix

\begin{displaymath}
G'=\left(
\begin{array}{c}
\hat{G}\\
m\hat{G}+e
\end{array}\right)
.
\end{displaymath}

This is the generator matrix of a linear code $ C'$ with minimum weight codeoword $ e$. Note that $ e$ is the only vector in $ C'$ of minimum weight, by construction. Algorithm 3 can be modified to yield not only the minimum distance, but also a vector of minimum wieght. Using this fact Eve can solve for $ e$, and therefore she can solve for the message $ m$ sent by Alice. This example illustrates the usefulness of fast minimum distance algorithms for cracking certain types of McEliese cyrptosystems.



Next: Appendix: GAP Code Up: foster_final_report Previous: Examples   Contents
David Joyner 2004-04-27