Cryptanalysis of Countermeasures Proposed for Repairing ISO 9796-1.
M. Girault and J.-F. Misarsky

ISO 9796-1, published in 1991, was the first standard specifying a digital signature scheme with message recovery. In [4], Coron, Naccache and Stern described an attack on a slight modification of ISO 9796-1. Then, Coppersmith, Halevi and Jutla turned it into an attack against the standard in full [2]. They also proposed five countermeasures for repairing it. In this paper, we show that all these countermeasures can be attacked, either by using already existing techniques (including a very recent one), or by introducing new techniques, one of them based on the decomposition of an integer into sums of two squares.