Browse Prior Art Database

Asymmetric Authentication Protocol

IP.com Disclosure Number: IPCOM000106290D
Original Publication Date: 1993-Oct-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 135K

Publishing Venue

IBM

Related People

Blakley, B: AUTHOR [+2]

Abstract

A protocol is disclosed for one-way authentication in the asymmetric model. In this protocol, a prover convinces a verifier that the prover knows the factors of a large composite number N. The prover does this in a way that it does not reveal the factors of N.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Asymmetric Authentication Protocol

      A protocol is disclosed for one-way authentication in the
asymmetric model.  In this protocol, a prover convinces a verifier
that the prover knows the factors of a large composite number N.  The
prover does this in a way that it does not reveal the factors of N.

      The disclosed protocol requires very little computation by the
prover and a reasonable amount by the verifier.  It uses neither
public key encryption nor digital signatures.  The disclosed protocol
assumes the intractability of factoring and the existence of an
"ideal" hash function.

      The disclosed protocol is useful for the software licensing
problem.  In this problem, the prover is a license server and the
verifier is an application program that wants to get permission to
run.  To obtain this, the application asks the license server if it
may run and the server answers "yes" by proving that the license
server possesses certain secret information embedded in the software
license.  With the disclosed protocol, no secret is kept in the
application, and the server performs the brunt of the computation.

      Informally, the authentication goal is the following:  that no
reasonable adversary (who may examine the code of the prover P and
the verifier V but not P's secret) should be able to interact with a
cooperative prover P in such a way as to learn information which
would afterwards allow it to authenticate itself to a verifier V as
though it were the prover P.

      The goal is achieved using ideas from the field of
zero-knowledge.  Zero-knowledge protocols were introduced in [1].
The disclosed protocol resembles the oblivious transfer protocol of
[4].

      Number Theory Background - Before stating the protocol, note
just a little bit of number theory.  Everything in this section is
well known and is explained in further detail in any standard
reference on number theory, such as [2,3].

      Let N = pq is the product of two large (e.g., 256-bit) primes.
All arithmetic is done in the multiplicative group of integers modulo
N, which contains the numbers between 1 and N - 1 which are
relatively prime to N.  To make matters easier for the prover, it is
convenient to demand that N be a Blum integer, so that p and q are
congruent to 3 (mod 4).

      The multiplicative group of integers modulo pq has (p - 1)(q -
1) elements.  It is, therefore, easy to choose a random number in the
group:  just choose a random number between 1 and N - 1 and check
that it is relatively prime to N.  Euclid's algorithm can be used to
check if two numbers are relatively prime.

      In the multiplicative group of integers modulo N (as in the
integers), some numbers have square roots and some do not.  A quarter
of the numbers have square roots and the ones which have square roots
have four of them.  The four square roots of a square x sup hat 2 are
of the form x, -x, y and -y.  Possession of two of th...