GOST 34.10—A brief overview of Russia's DSA

GOST 34.10 is Russia's DSA. Like its US counterpart, GOST is an ElGamal-like signature scheme used in Schnorr mode. It is similar to NIST DSA in many aspects. In this paper we will overview GOST 34.10 and discuss the three main differences between the two algorithms, (i) GOST's principal design criterion does not seem to be computational efficiency: the algorithm is 1.6 times slower than the DSA and produces 512-bit signatures. This is mainly due to the usage of the modulus q which is at least 254 bits long. During verification, modular inverses are computed by exponentiation (while the Extended Euclidian algorithm is roughly 100 times faster for this parameter size) and the generation of the public parameters is much more complicated than in the DSA. This choice of the parameters makes GOST 34.10 very secure. (ii) GOST signers do not have to generate modular inverses as the basic signature equation is s = xr + mk (mod q) instead of (mod q). (iii) GOST's hash function (the Russian equivalent of the SHA) is the standard GOST 34.11 which uses the block cipher GOST 28147 (partially classified) as a building block. The hash function will be briefly described. Copyright