tailieunhanh - Digital signature scheme based on a new hard problem

Information authentication in computer networks and information sys-tems is usually performed with digital signature schemes (DSSes) that are attributed to public key cryptosystems. | Computer Science Journal of Moldova 47 2008 Digital Signature Scheme Based on a New Hard Problem Nikolay A. Moldovyan Abstract Factorizing composite number n qr where q and r are two large primes and finding discrete logarithm modulo large prime number p are two difficult computational problems which are usually put into the base of different digital signature schemes DSSes . This paper introduces a new hard computational problem that consists in finding the feth roots modulo large prime p Nk2 1 where N is an even number and k is a prime with the length k 160. Difficulty of the last problem is estimated as O y k . It is proposed a new DSS with the public key y xk mod p where x is the private key. The signature corresponding to some message M represents a pair of the p -bit numbers S and R calculated as follows R tk mod p and S txf R M mod p where f R M is a compression function. The verification equation is Sk mod p yf R M R mod p. The DSS is used to implement an efficient protocol for generating collective digital signatures. 1 Introduction Information authentication in computer networks and information systems is usually performed with digital signature schemes DSSes that are attributed to public key cryptosystems. The DSSes are based on some well investigated hard computational problems. The upper boundary of the DSS security level is defined by the difficulty of the @2008 by N. A. Moldovyan This work was supported by Russian Foundation for Basic Research grants 08-07-00096-a and 08-07-90100-Moha. 163 N. A. Moldovyan used hard problem. To get sufficiently high security the signature generation and signature verification procedures use calculations modulo comparatively large numbers. The modulus length defines significantly performance of the DSSes. The most efficient known DSSes are based on the following three difficult problems 17 1. Factorization of a composite number n qr where q and r are two large primes. 2. Finding discrete logarithm modulo .