Accueil > Research > Code-based cryptography > Code-based cryptosystems : implementations > Implementation of Goppa codes decoding algorithms in C

Implementation of Goppa codes decoding algorithms in C

dimanche 27 juillet 2014, par Amund Desmarais and Rayan Safieddine, Cayrel

Code implemented by Amund Desmarais and Rayan Safieddine.

Three decoding algorithms were implemented :

  • Patterson
  • Berlekamp-Massey
  • Extended Euclidean

Each algorithm creates a Goppa code and decodes a message independently. Methods implemented include, but not limited to :

  • Multiplication
  • Exponentiation
  • Division
  • Square Root
  • Extended Euclidean algorithm

An m and t are needed to define the dimension of the Goppa code. An irreducible polynomial and parity-check matrix will be generated. However, due to problems with the algorithm the polynomial generated is not always irreducible. Thus it is advised to generate an irreducible polynomial before.

A pari/gp version of the Patterson algorithm has been implemented using a modified previous design.

To generate an irreducible polynomial using the pari/gp code :

Copy the output into the key-generation method will give an irreducible polynomial.

Main function has full implementation of decoding algorithm.

The report

All the documents