Note: Descriptions are shown in the official language in which they were submitted.
CA 02588149 2007-05-09
A DIGITAL SIGNATURE SCHEME BASED ON THE DIVISION ALGORITHM
AND THE DISCRETE LOGARITHM PROBLEM.
This application claims the benefit of priority of Canadian Patent Application
No. CA
2,545,975 filed May 9, 2006, which is incorporated herein by reference.
1. INTRODUCTION
Digital Signature is a method of authenticating digital information. The
output of a
digital signature algorithm is a binary string (or a pair of strings) that
provides
authenticity, integrity and non-repudiation of the transmitted message.
Digital signature algorithms are based on public key cryptography (A. J.
Menezes, P. C.
van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography. CRC Press,
1997)
and consist of two parts - a signing algorithm and a verification algorithm.
Digital signature algorithms, such as Lamport Signatures, Matyas-Meyer
Signatures,
RSA Signatures, ElGamal Signatures and others, are well-known and widely-used
in
practice (Josef Pieprzyk, Thomas Hardjono, Jennifer Sebbery, Fundamentals of
Computer Security, Springer-Verlag, 2003).
The National Institute of Standards and Technology (NIST) has published the
Federal
Information Processing Standard FIPS PUB 186, also known as Digital Signature
Standard (DSS). The DSS uses SHA as hashing algorithm and the Digital
Signature
Algorithm (DSA). The DSA is based on the difficulty of computing the discrete
logarithm problem and is based on schemes presented by ELGamal and Shnorr
(Josef
Pieprzyk, Thomas Hardjono, Jennifer Sebbery, Fundamentals of Computer
Security,
Springer-Verlag, 2003).
We present a digital signature algorithm, which is also based on difficulty of
computing
the discrete logarithm problem (I. F. Blake, G. Seroussi, N. Smart, Elliptic
Curves in
CA 02588149 2007-05-09
Cryptography, LMS Lecture Notes 265, Cambridge University Press, Cambridge,
2000),
but is different from ELGamal and the DSA scheme.
The main advantages of the presented digital signature algorithm is the fact
that it can be
naturally and easily combined with the new scheme of Message Authentication
Coding
with transformations proposed by the authors (Canadian Patent Application No.
CA
2,552,085; U.S. Patent Application Serial No. 11/457,669). Thus, in this
framework, one
can easily implement both a Message Authentication Coding system (with
transformations that allow generating a MAC value with sufficiently improved
characteristics of security) and the proposed digital signatures scheme
without any
additional programming tools.
2. A DIGITAL SIGNATURE SCHEME
We will first consider some background information (Josef Pieprzyk, Thomas
Hardjono,
Jennifer Sebbery, Fundamentals of Computer Security, Springer-Verlag, 2003). A
digital
signature scheme is a collection of two algorithms: the signing algorithm and
the
verification algorithm.
The signing algorithm
SG:I'=O-> S
assigns a signature s to a pair d, m, where d E F is a secret key and m E A is
a message,
that is, SG(d, m) = s.
The verification algorithm
VER:I"=A =S --> {t,f}
CA 02588149 2007-05-09
using the public key e E F' of the signer, the message m E A and checks
whether the pair
( e, m) matches the signature s. If there is a match, the algorithm returns t-
TRUE.
Otherwise, it generates f - FALSE.
2.1. ELGamal Digital Signature Scheme. As an example of a digital signature,
consider the ElGamal algorithm variants of which are in actual use (Josef
Pieprzyk,
Thomas Hardjono, Jennifer Sebbery, Fundamentals of Computer Security, Springer-
Verlag, 2003).
A sender (Sally) considers a finite field GF( p) , in which the discrete
logarithm problem
is difficult. Then, she selects a primitive element g c- GF(p) * and a random
integer k in
the interval [1, p - 1]. This allows one to compute the public key gk mod p.
Then, Sally sends gk, g and p to the public registry.
The Signing algorithm:
For a message m E GF(p) , Sally selects a random integer r E [1,p -1], such
that
gcd(r, p - 1) =1, and calculates
xgYmodp.
Then, she solves the following congruence
mk=x+r=ymodp
for y.
The signature is
s=SGk(m)=(x,y).
Sally keeps secret k and r.
The Verification algorithm:
CA 02588149 2007-05-09
A receiver (Bob) receives the message m and s=(x, y) . He then checks whether
VER(m, s ) = (g ' (gk )X = x'' mod p).
3. THE PROPOSED DIGITAL SIGNATURE SCHEME
Now, we want to present a digital signature scheme that naturally arises and
can be
effectively combined with a MAC (or Hash) function with transformation,
considered
earlier by the authors (Canadian Patent Application No. CA 2,552,085; U.S.
Patent
Application Serial No. 11/457,669).
We remark that when we consider a message x in a digital signature, we deal
with the
hash or MAC value of the original message.
The Signing Procedure. We begin with a cyclic group G of prime order of size
2'. We
also fix a generator g of G. A sender chooses a private key K, say of k bits.
Then, the
sender computes the public key g'"(). Given a message i~f, it is hashed or MAC-
ed to
ni. We assume that iri has h bits where
(1) lz k
and
(2) tna~d~h, ~:; - h) : ec
Then a random sessional number :# 0 is generated, which is kept secret. The
number
of bits of z is at most h. Then, using the division algorithm, the sender
calculates a
unique pair of integers q and r such that
(3) t-nt(K) = (t;nt(tri) + z)q + :r.
CA 02588149 2007-05-09
Here, tnt(K) and irat(rn) are integers, the binary presentation of which are
the sequences
of bits K and ni, correspondingly.
The digital signature is the pair (x, y) where
:A = (,-zq-r)
and
gq.
If, by coincidence, zq + r is 0 it is necessary to choose another z and
recalculate the pair
q and r in accordance with (3).
The Verification Procedure. A receiver obtains a message M and a digital
signature in
the form of a pair Besides, a receiver knows the public key as well as the
group G and the generator g.
The message M is hashed (or MAC-ed with the corresponding key) to rx1', and
the
following two expressions are calculated
(4) X9mr.io ~,.nu(~~)
If they are equal, then the signature is valid. If they are not equal, the
signature is not
valid and the message may be rejected.
The next theorem shows that the proposed scheme and the evaluation procedure
are
correct.
Theorem 1. If AI and M are two messages for which the hash -Yn and -"rzare
distinct,
then the two quantities in (4) are unequal.
Proof. If the two quantities are equal then
riint(rn) , qint(m') (mod I G 1).
CA 02588149 2007-05-09
Note that the converse also holds. From (3), we have
q -. 2k -h
and by (1) and (2), this is strictly smaller than ( G (. As I Ci, I is prime,
( IG 1, q) _1, and so
the above congruence implies that
(5) an t(m) - t:nt(rri) (mod I G ~).
Again from (1) and (2), we have
tnt(m), int'(rta) <:. 2 ~ < 2- < IG ( .
Thus, the congruence (5) implies that m and m are equal, contradicting our
assumption.
4. IMPLEMENTATION
As one example, the method of the present invention can be readily implemented
in a
Dynamically Linked Library (or DLL), which is linked to a computer program
that
utilizes an algorithm that embodies the digital signature algorithm described
above, for
example, an encryption, decryption or authentication utility that is operable
to apply said
algorithm.
The computer program of the present invention is, therefore, best understood
as a
computer program that includes computer instructions operable to implement an
operation consisting of the calculation of the digital signature string (pair
of strings) as
described above.
Another aspect of the present invention is a computer system that is linked to
a computer
program that is operable to implement, on the computer system, the digital
signature
algorithm in accordance with the present invention, together with the System
of
Transformation of a MAC-value (Canadian Patent Application No. CA 2,552,085;
U.S.
CA 02588149 2007-05-09
Patent Application Serial No. 11/457,669). This invention will be of use in
any
environment where MAC functions are used for data integrity together with
digital
signatures.
As another example, the method of the present invention can be readily
implemented in a
specially constructed hardware device. As discussed above, an integrated
circuit can be
created to perform the calculations necessary to create a digital signatures
string. Other
computer hardware can perform the same function. Alternatively, computer
software can
be created to program existing computer hardware to create digital signature
values.
