Strengthened public key protocol

Details Strengthened public key protocol Strengthened public key protocol

1999-04-01

2003-05-13

Hayes, Gail (Department: 2766)

Cryptography

Particular algorithmic function encoding

Public key

C380S028000, C380S285000

Reexamination Certificate

active

06563928

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to public key cryptography.
2. Discussion of Related Art
It is well known that data can be encrypted by utilising a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted by the public key may only be decrypted by the private key. In this way, the public key of a recipient may be made available so that data intended for that recipient may be encrypted with the public key and only decrypted by the recipients private key.
One well-known and accepted public key cryptosystem is that based upon discrete logarithms in finite groups. Different finite groups may be used, for example the multiplicative group Z*
p
of integers mod p where p is a prime; the multiplicative group of an arbitrary finite field e.g. GF2
n
or an elliptic curve group over a finite field.
The discrete log problem used in such cryptosystems is based on the difficulty of determining the value of an integer x from the value of &agr;
x
, even where &agr; is known. More particularly, if &agr; is an element of G (which is considered to be written multiplicatively) and &bgr; is a second element of G, then the discrete logarithm problem in G is that of determining whether there exists an integer x such that &bgr;=&agr;
x
, and if so, of determining such a value x.
The Diffie-Hellman key exchange protocol is widely accepted and there are numerous examples of implementations of the Diffie-Hellman protocol in use around the world.
The Diffie-Hellman key agreement protocol is typically stated as follows using as an example the finite group Z
p
·
:
Setup
The protocol requires a base &agr; that generates a large number of elements of the selected group G and a pair of integers x,y that are retained confidential by respective correspondents A,B. Select a prime number p and let a be &agr; generator of the multiplicative group Z
p
·
, i.e. the group of integers modulo p.
The Protocol
1. Correspondent A generates a random integer x, computes &agr;
x
and sends this to correspondent B.
2. Correspondent B generates a random integer y, computes &agr;
y
and sends this to correspondent A.
3. A computes (&agr;
y
)
x
=&agr;
xy
.
4. B computes (&agr;
x
)
y
=&agr;
xy
.
A and B now share the common key &agr;
xy
which may be used as a secret key in a conventional cryptosystem. A similar protocol maybe used in a public key system, generally referred togas an El-Gamal protocol in which each correspondent has a secret key x and a public key &agr;
x
.
The security of these protocols seems to rest on the intractability of the discrete logarithm problem in the finite group G. It should also be noted that the protocol carries over to any finite group.
The applicants have now recognized that unless the generator &agr; and the group G are selected carefully then the exchange of information may be weak and provide almost no security.
To explain the potential problem, consider the cryptosystem described above using the group Z
p
·
. The modulus p is public information that defines the cryptosystem and can be expressed as t.Q+1 with t≧2 and t relatively small. This is always possible since p is odd for large primes (i.e. t could be 2).
Let S be a subgroup of Z*
p
of order t (i.e. it has t elements, each of which is element of Z
p
·
) and let &ggr; be a base for S, i.e. each element of S can be expressed as an integral power of &ggr; and raising &ggr; to an integral power produces an element that is itself in the subgroup S. If &agr; is a generator for Z
p
·
, then we can take &ggr;=&agr;
Q
without loss of generality.
If E is an active adversary in the key exchange protocol between two parties A and B then the attack proceeds as follows:
1. E intercepts the message &agr;
x
sent by A and replaces it by (&agr;
x
)
Q
=&ggr;
x
and sends it on to entity B.
2. E intercepts the message &agr;
y
sent by B and replaces it by (&agr;
y
)
Q
=&ggr;
y
and sends it on to entity B.
3. A computes (&ggr;
y
)
x
=&ggr;
xy
.
4. B computes (&ggr;
x
)
y
=&ggr;
xy
.
5. Although E does not know the key &ggr;
xy
, E knows that the common key &ggr;
xy
lies in the subgroup S of order t as &ggr; is a generator of S. By definition &ggr;
xy
must produce an element in the subgroup S. Since S is of order t it has precisely t elements. If t is small enough then E can exhaustively check all possibilities and deduce the key.
Since E selects Q, t can always be taken to be 2 and so the threat is practical.
A similar attack may be mounted with cryptosystems using groups other than Z*
p
which will be vulnerable if the element selected as a base or generator generates a subgroup which itself has a small subgroup of order t.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a method for checking if modification of messages has occurred or in the alternative some method to prevent the attack from being mounted.
In general terms, the present invention is based upon utilization of predefined characteristics of the order of the subgroup.
In one aspect, the base of the cryptosystem is chosen to be a generator of a subgroup of a relatively large prime order. Substitution of any other non-unit generator is of no advantage to an attacker since it does not produce an element in a smaller subgroup that can be exhaustively searched.
In another aspect, factors of the order of the group generated by the base are used to ensure that the key does not lie in or has not been modified to lie in a proper subgroup of relatively small order, i.e. one that may feasibly be exhaustively searched by an interloper.


REFERENCES:
patent: 4351982 (1982-09-01), Miller et al.
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4633036 (1986-12-01), Hellman et al.
patent: 4956863 (1990-09-01), Goss
patent: 5150411 (1992-09-01), Maurer
patent: 5159632 (1992-10-01), Crandall
patent: 5271061 (1993-12-01), Crandall
patent: 5272755 (1993-12-01), Miyaji et al.
patent: 5299263 (1994-03-01), Beller et al.
patent: 5442707 (1995-08-01), Miyaji et al.
patent: 5463690 (1995-10-01), Crandall
patent: 5497423 (1996-03-01), Miyaji
patent: 5581616 (1996-12-01), Crandall
patent: 5600725 (1997-02-01), Rueppel et al.
patent: 5625692 (1997-04-01), Herzberg et al.
patent: 5724425 (1998-03-01), Chang et al.
patent: 5761305 (1998-06-01), Vanstone et al.
patent: 5768388 (1998-06-01), Goldwasser et al.
patent: 5987131 (1999-11-01), Clapp
Abdalla,Bellare,Rogaway;DHIES: An encryption scheme based on the Diffie-Hellman Problem,Sep. 18, 2001, pp. 1-25.*
Tilborg,Elliptic Curver Cryptosystems;too good to be true?; Sep. 2001,pp. 220-225.*
Schroeppel,Orman,O'Malley; Fast Key exchange with Elliptic Curve Systems; Mar. 31, 1995; pp. 1-9.*
Schneier; Applied Cryptography;second edition, 1996, pp. 513-525,480-481.

Affiliated with

Also associated with

Rating

Strengthened public key protocol does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Strengthened public key protocol, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strengthened public key protocol will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3080226