Authors: 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 k th roots modulo large prime p=Nk
2+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(√k). It is proposed a new DSS with the public key x
kmodp, 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=t
k mod p and S=tx
f(R,M)modp, where f(R, M) is a compression function. The verification equation is S
k mod p=y
f(R, M)Rmodp. The DSS is used to implement an efficient protocol for generating collective digital signatures.
N. A. Moldovyan
Specialized Center of Program Systems "SPECTR",
Kantemirovskaya, 10, St.Petersburg 197342, Russia;
ph./fax.7-812-2453743,
E-mail:
Fulltext

–
0.19 Mb