Comment utiliser l'algorithme de Wiedemann pour le calcul de l'immunité d'une fonction booléenne contre les attaques algébriques

Les attaques algébriques et les attaques algébriques rapides, proposées en 2002 et 2003 respectivement, constituent une avancée intéressante et puissante dans la cryptanalyse des chiffrements à flot. Leur but est de retrouver les bits de la clef en résolvant un système d'équations algébriques. Ce système est généralement fortement surdéterminé et des méthodes basées sur les algorithmes récents de calcul de bases de Gröbner peuvent s'avérer efficaces, particulièrement lorsque l'on peut construire un système d'équations de faible degré. C'est ce qui est arrivé pour certains chiffrements à flot fondés sur un registre linéaire filtré par une fonction non-linéaire. Pour construire un tel système algébrique, il est nécessaire que des relations de faible degré entre les bits d'entrée et de sortie de la fonction de filtrage existent. Dès lors, il devient intéressant d'être capable de savoir si une telle fonction admet ou non ce genre de relations. C'est dans cette optique que la notion d'immunité algébrique a été introduite. La recherche de ces relations peut encore une fois s'effectuer par le biais d'un calcul de base de Gröbner, mais à ce jour les méthodes les plus efficaces pour répondre à cette question sont fondées sur de l'algèbre linéaire. Elles reviennent à déterminer si un système linéaire est de rang plein ou non. Ce système présente une structure algébrique très forte et récemment plusieurs algorithmes ont été proposés pour l'exploiter. Je décrirai dans ma présentation un tel algorithme fondé sur des méthodes d'algèbre linéaire creuse et plus particulièrement sur l'algorithme de Wiedemann. Cette approche est actuellement l'une des plus efficace pour déterminer l'immunité d'une fonction booléenne contre les attaques algébriques.