Device and method for authenticating user's access rights to resources

• US RE42,762 E1
• Filed: 03/17/2000
• Issued: 09/27/2011
• Est. Priority Date: 02/23/1996
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Kobayashi, Kenichi, Shin, Kil-ho, Aratani, Toru
• Primary Examiner(s): Hewitt; Calvin
• Assistant Examiner(s): Winter; John M
• Application Number:
  US09/533,905
• Time in Patent Office: 4,211 Days
• Field of Search: 380/25, 380/30, 713/159, 713/184, 713/168, 713/167, 713/201, 709/229, 705/50
• US Class Current: 713/159
• CPC Class Codes: G06F 21/316 by observing the pattern of computer usage, e.g. typical user behaviour
• CPC Class Codes: G06F 21/34 involving the use of external additional devices, e.g. dongles or smart cards
• CPC Class Codes: G06F 2221/2139 Recurrent verification
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

The present invention provides a device for authenticating user'"'"'s access rights to resources, which comprises first memory means for storing challenging data, second memory means for storing unique identifying information of the user, third memory means for storing proof support information which is a result of executing predetermined computations to the unique identifying information of the user and unique security characteristic information of the device, response generation means for generating a response from the challenging data stored in the first memory means, the unique identifying information stored in the second memory means and the proof support information stored in the third memory means, and verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information of the device satisfy a specific predefined relation.

Claims

1. A device for authenticating user'"'"'s access rights to resources comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing predetermined computations to the user unique identifying information and unique security characteristic information of the device;

response generation means for generating a response from the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means; and

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information of the device satisfy a specific predefined relation.

2. The device for authenticating user'"'"'s access rights to resources of claim 1 further comprising:

A device for authenticating user'"'"'s access rights to resources comprising;

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means;

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation;

and protect means for preventing any data inside stored information from being observed or being tampered with from the outside, and for at least confining storing the second memory means and the response generation means.

3. The A device for authenticating user'"'"'s access rights to resources of claim 1, wherein comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means; and

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation;

wherein

at least the second memory means and the response generation means are implemented within a small portable device such as a smart card.

4. The A device for authenticating user'"'"'s access rights to resources of claim 1, wherein comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means; and

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation;

wherein

the response generation means comprises;

first calculation means for replaying the unique security characteristic information of the device by executing predetermined calculations to the unique identifying information of the user stored in the second memory means and the proof support information stored in the third memory means; and

second calculation means for generating a response by executing predetermined calculations to the challenging data stored in the first memory means and the unique security characteristic information of the device replayed by the first calculation means.

5. The A device for authenticating user'"'"'s access rights to resources of claim 1, wherein comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means; and

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation;

wherein

the response generation means comprises;

third calculation means for generating first intermediate information by executing predetermined calculations to the challenging data stored in the first memory means and the proof support information stored in the third memory means;

fourth calculation means for generating second intermediate information by executing predetermined calculations to the challenging data stored in the first memory means and the user unique identifying information stored in the second memory means; and

fifth calculation means for generating a response by executing predetermined calculations to the first intermediate information generated by the third calculation means and the second intermediate information generated by the fourth calculation means.

6. The device for authenticating user'"'"'s access rights to resources of claim 5, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, at least confining the second memory means and the fourth calculation means.

7. The device for authenticating user'"'"'s access rights to resources of claim 5, wherein

at least the second memory means and the fourth calculation means are implemented within a portable device such as a smart card.

8. The A device for authenticating user'"'"'s access rights to resources of claim 1, wherein comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means; and

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information of the device is a decryption key of a cipher function, satisfy a specific predetermined relation;

wherein

the challenging data is encryption of information using the cipher function with the encryption key corresponding to the decryption key, and

the verification means verifies the legitimacy of the response by verifying that the response generated by the response generation means is identical with decryption of the challenging data with the decryption key.

9. The A device for authenticating user'"'"'s access rights to resources of claim 1, wherein comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means; and

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information of the device is an encryption key of a cipher function, and satisfy a specific predefined relation;

wherein

the verification means verifies the legitimacy of the response by verifying that the response generated by the response generation means is identical with encryption of the challenging data with the encryption key.

10. The A device for authenticating user'"'"'s access rights to resources of claim 1, wherein comprising:

the characteristic information of the device is the signature key of a digital signature function, and

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means; and

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation;

wherein

the verification means verifies the legitimacy of the response by verifying that the response generated by the response generation means is identical with the digital signature for the challenging data, which is calculated with the signature key.

11. The device for authenticating user'"'"'s access rights to resources of claim 8, wherein

the cipher function is of the asymmetric key cryptography, and

the unique security characteristic information of the device is one component of the key pair of the cipher function.

12. The device for authenticating user'"'"'s access rights to resources of claim 9, wherein

the cipher function is of the asymmetric key cryptography, and

the unique security characteristic information of the device is one component of the key pair of the cipher function.

13. The device for authenticating user'"'"'s access rights to resources of claim 11, wherein

the cipher function is of the public key cryptography, and

the unique security characteristic information of the device is the private key of the public key pair of the cipher function.

14. The device for authenticating user'"'"'s access rights to resources of claim 12, wherein

the cipher function is of the public key cryptography, and

the unique security characteristic information of the device is the private key of the public key pair of the cipher function.

15. The device for authenticating user'"'"'s access rights to resources of claim 8, wherein

the cipher function is of the symmetric key cryptography, and

the unique security characteristic information of the device is the common key of the cipher function.

16. The device for authenticating user'"'"'s access rights to resources of claim 9, wherein

the cipher function is of the symmetric key cryptography, and

the unique security characteristic information of the device is the common key of the cipher function.

17. The A device for authenticating user'"'"'s access rights to resources of claim 1, further comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of executing a first computation using both the user unique identifying information and unique security characteristic information, wherein the unique security characteristic information is one of a decryption key of a cipher function, an encryption key of a cipher function, and a signature key of a digital signature function, which corresponds to the challenging data;

response generation means for generating a response by executing a second computation using the challenging data stored in the first memory means, the unique identifying information of the user stored in the second memory means, and the proof support information stored in the third memory means;

verification means for verifying legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation;

a proving device having the first memory means, the second memory means, the third memory means and the response generation means; and

a verification device having fourth memory means for storing the challenging data, fifth memory means for storing the response and the verification means, wherein

the verification device transfers the challenging data stored in the fourth memory means to the first memory means of the proving device, the proving device transfers the response generated by the response generation means to the fifth memory means of the verification device, and the verification means of the verification device verifies the legitimacy of the response stored in the fifth memory means.

18. The device for authenticating user'"'"'s access rights to resources of claim 17, wherein

the unique security characteristic information of the device is an encryption key of a cipher function,

the verification device comprises random number generation means for generating a random number and for storing it in the fourth memory means, and

the verification means verifies the legitimacy of the response by verifying that the response stored in the fifth memory means is identical with encryption of the challenging data stored in the fourth memory means with the encryption key.

19. The device for authenticating user'"'"'s access rights to resources of claim 17, wherein

the unique security characteristic information of the device is a decryption key of a cipher function,

the verification device comprises random number generation means for generating a random number, sixth memory means for storing the generated random number and seventh memory means for storing a seed for challenging data, and wherein

the random number generation means stores the generated random number in the sixth memory means while randomizing the seed for the challenging data stored in the seventh memory means by executing predefined calculations to the random number stored in the sixth memory means and the seed stored in the seventh memory means and then storing the randomized seed as challenging data in the fourth memory means, and

the verification means of the verification device de-randomizes the response stored in the fifth memory means by executing predefined calculations to the random number stored in the sixth memory means and the response stored in the fifth memory means, and then verifies the legitimacy of the de-randomized response by verifying that the de-randomized result is identical with decryption of the seed stored in the seventh memory means with the decryption key which is the unique security characteristic information of the device.

20. The device for authenticating user'"'"'s access rights to resources of claim 17, wherein

the unique security characteristic information of the device is the signature key of a digital signature function, and

the verification device comprises random number generation means for generating a random number and storing the generated random number as challenging data in the fourth memory means, and wherein

the verification means of the verification device verifies the legitimacy of the response by verifying that the response stored in the fifth memory means is identical with the digital signature for the challenging data stored in the fourth memory means, which is calculated with the signature key which is the unique security characteristic information of the device.

21. The device for authenticating user'"'"'s access rights to resources of claim 18, wherein

the unique security characteristic information of the device is the private key D of an RSA public key pair with a modulus n, and

the verification means verifies the legitimacy of the response by verifying that the E-th power of the response R stored in the fifth memory means, where E denotes the public key associated with the private key D, is congruent with the challenging data C stored in the fourth memory means modulo n (R^E mod n=C mod n).

22. The device for authenticating user'"'"'s access rights to resources of claim 19, wherein

the unique security characteristic information of the device is the private key D of an RSA public key pair with a modulus n, a seed C′

for challenging data stored in the seventh memory means is an RSA-encryption of data K with the public key E of the RSA public key pair (DE modφ

(n)=1, C′

=K^E mod n),

a random number r generated by the random number generation means is stored in the sixth memory means,

challenging data C generated and stored in the fourth memory means satisfies the relation C=r^EC′

mod n, and

the verification means verifies the legitimacy of the response R stored in the fifth memory means by verifying that the quotient of R divided by r modulo n is congruent with the data K modulo n (K mod n=r<sup>−

1</sup> R mod n).

23. The device for authenticating user'"'"'s access rights to resources of claim 21, wherein

a proof support information t stored in the third memory means satisfies the relation t=D−

e+wφ

(n), where e denotes user unique identifying information stored in the second memory means, w denotes a conflict-free random number determined dependent upon both n and e and φ

(n) denotes the Euler number of n, and

the response generated by response generation means is identical with the D-th power of challenging data C stored in the first memory means modulo n (R=C^D mod n).

24. The device for authenticating user'"'"'s access rights to resources of claim 22, wherein

a proof support information t stored in the third memory means satisfies the relation t=D−

e+wφ

(n), where e denotes user unique identifying information stored in the second memory means, w denotes a conflict-free random number determined dependent upon both n and e and φ

(n) denotes the Euler number of n, and

the response generated by response generation means is identical with the D-th power of challenging data C stored in the first memory means modulo n (R=C^D mod n).

25. The device for authenticating user'"'"'s access rights to resources of claim 23, wherein

the response generation means further comprises:

third calculation means for calculating the t-th power of challenging data C stored in the first memory means modulo n (C^t mod n), where t denotes proof support information stored in the third memory means;

fourth calculation means for calculating the e-th power of the challenging data C modulo n (C^e mod n), where e denotes user unique identifying information stored in the second memory means; and

fifth calculation means for calculating a response R by multiplying the result calculated by the third calculation means by the result calculated by the fourth calculation means modulo n (R=C^tC^e mod n).

26. The device for authenticating user'"'"'s access rights to resources of claim 24, wherein

the response generation means further comprises:

third calculation means for calculating the t-th power of challenging data C stored in the first memory means modulo n (C^t mod n), where t denotes proof support information stored in the third memory means;

fourth calculation means for calculating the e-th power of the challenging data C modulo n (C^e mod n), where e denotes user unique identifying information stored in the second memory means; and

fifth calculation means for calculating a response R by multiplying the result calculated by the third calculation means by the result calculated by the fourth calculation means modulo n (R=C^tC^e mod n).

27. The device for authenticating user'"'"'s access rights to resources of claim 25, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

28. The device for authenticating user'"'"'s access rights to resources of claim 26, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

29. The device for authenticating user'"'"'s access rights to resources of claim 21, wherein

proof support information t stored in the third memory means satisfies the relation t=D+F(n, e), where e denotes user unique identifying information stored in the second memory means, and F(x, y) denotes a two-variable collision-free function, and

a response generated by the response generation means is identical with the D-th power of challenging data C stored in the first memory means modulo n (R=C^D mod n).

30. The device for authenticating user'"'"'s access rights to resources of claim 22, wherein

proof support information t stored in the third memory means satisfies the relation t=D+F(n, e), where e denotes the user unique identifying information stored in the second memory means, and F(x, y) denotes a two-variable collision-free function, and

a response generated by the response generation means is identical with the D-th power of challenging data C stored in the first memory means modulo n (R=C^D mod n).

31. The device for authenticating user'"'"'s access rights to resources of claim 29, wherein

the response generation means further comprises:

third calculation means for calculating the t-th power of challenging data C stored in the first memory means modulo n, where t denotes the proof support information stored in the third memory means (C^t mod n);

fourth calculation means for calculating the F(n, e)-th power of the challenging data C modulo n (C^{F(n, e)} mod n), where e denotes the user unique identifying information stored in the second memory means and F(x, y) denotes a two-variable collision-free function; and

fifth calculation means for calculating a response R by dividing the result calculated by the third calculation means by the result calculated by the fourth calculation means modulo n (R=C^t C<sup>−

F(n, e)</sup> mod n).

32. The device for authenticating user'"'"'s access rights to resources of claim 30, wherein

the response generation means further comprises:

third calculation means for calculating the t-th power of challenging data C stored in the first memory means modulo n, where t denotes proof support information stored in the third memory means (C^t mod n);

fourth calculation means for calculating the F(n, e)-th power of the challenging data C modulo n (C^{F(n, e)} mod n), where e denotes user unique identifying information stored in the second memory means and F(x, y) denotes a two-variable collision-free function; and

fifth calculation means for calculating a response R by dividing the result calculated by the third calculation means by the result calculated by the fourth calculation means modulo n (R=C^t C<sup>−

F(n, e)</sup> mod n).

33. The device for authenticating user'"'"'s access rights to resources of claim 31, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

34. The device for authenticating user'"'"'s access rights to resources of claim 32, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

35. The device for authenticating user'"'"'s access rights to resources of claim 18, wherein

the unique security characteristic information of the device is a key D of a Pohlig-Heilman key pair of a modulus p, and

the verification means verifies the legitimacy of the response by verifying that the E-th power of the response R stored in the fifth memory means, where E denotes the counterpart key of the key D (DE mod (p−

1)=1), is congruent with the challenging data C stored in the fourth memory means modulo p (R^E mod p=C mod p).

36. The device for authenticating user'"'"'s access rights to resources of claim 19, wherein

the unique security characteristic information of the device is a key D of a Pohlig-Hellman key pair of a modulus p,

a seed C′

for challenging data stored in the seventh memory means is Pohlig-Hellman-encryption of data K with the counterpart key E of the key D (DE mod (p−

1)=1, C′

=K^E mod p),

a random number r generated by the random number generation means is stored in the sixth memory means,

challenging data C stored in the fourth memory means satisfies the relation C=r^EC′

mod p, and

the verification means verifies the legitimacy of the response R stored in the fifth memory means by verifying that the quotient of R divided by r modulo p is congruent with the data K modulo p (K mod p=r<sup>−

1</sup> R mod p).

37. The device for authenticating user'"'"'s access rights to resources of claim 35, wherein

proof support information t stored in the third memory means satisfies the relation t=D+F(p, e), where e denotes the user unique identifying information stored in the second memory means, and F(x, y) denotes a two-variable collision-free function, and

a response generated by the response generation means is identical with the D-th power of challenging data C stored in the first memory means modulo p (R=C^D mod p).

38. The device for authenticating user'"'"'s access rights to resources of claim 36, wherein

proof support information t stored in the third memory means satisfies the relation t=D+F(p, e), where e denotes the user unique identifying information stored in the second memory means, and F(x, y) denotes a two-variable collision-free function, and

a response generated by the response generation means is identical with the D-th power of challenging data C stored in the first memory means modulo p (R=C^D mod p).

39. The device for authenticating user'"'"'s access rights to resources of claim 37, wherein

the response generation means further comprises:

third calculation means for calculating the t-th power of challenging data C stored n the first memory means modulo p, where t denotes the proof support information stored in the third memory means (C^t mod p);

fourth calculation means for calculating the F(p, e)-th power of the challenging data C modulo p (C^{F(p, e)} mod p), where e denotes the user unique identifying information stored in the second memory means and F(x, y) denotes a two-variable collision-free function; and

fifth calculation means for calculating a response R by dividing the result calculated by the third calculation means by the result calculated by the fourth calculation means modulo p (R=C^t C<sup>−

F(p, e)</sup> mod p).

40. A device for authenticating user'"'"'s access rights to resources of claim 38, wherein

the response generation means further comprises:

third calculation means for calculating the t-th power of challenging data C stored in the first memory means modulo p, where t denotes the proof support information stored in the third memory means (C^t mod p);

fourth calculation means for calculating the F(p, e)-th power of the challenging data C modulo p (C^{F(p, e)} mod p), where e denotes the user unique identifying information stored in the second memory means and F(x, y) denotes a two-variable collision-free function; and

fifth calculation means for calculating a response R by dividing the result calculated by the third calculation means by the result calculated by the fourth calculation means modulo p (R=C^t C<sup>−

F(p, e)</sup> mod p).

41. The device for authenticating user'"'"'s access rights to resources of claim 39, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

42. The device for authenticating user'"'"'s access rights to resources of claim 40, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

43. The device for authenticating user'"'"'s access rights to resources of claim 19, wherein

the unique security characteristic information of the device is the private key X of an ElGamal public key pair with a modulus p and a generator G,

the public key Y corresponding to X is the X-th power of G modulo p (Y=G^X mod p),

u denotes the z-th power of the modulo p (u=G^z mod p) for a random number z,

K′

denotes the product modulo p of the z-th power of Y modulo p and a data K (K′

=Y^z K mod p),

the seventh memory means retains the pair of u and K′

,

a random number r generated by the random generation means is stored in the sixth memory means,

C denotes the product modulo p of K′ and

r (C=rK′

mod p),

the fourth memory means retains the pair C and u, and

the verification means verifies the legitimacy of the response R stored in the fifth memory means by verifying that the quotient of R divided by r modulo p is congruent with K modulo p (K mod p=r<sup>−

1</sup> R mod p).

44. The device for authenticating user'"'"'s access rights to resources of claim 43, wherein

proof support information t stored in the third memory means satisfies the relation t=X+F(p, e), where e denotes the user unique identifying information stored in the second memory means and F(x, y) denotes a two-variable collision-free function, and

a response R generated by the response generation means is identical with the quotient of C divided by X-th power of u modulo p (R=u⁻

xC mod p), where the pair C and u is the challenging data stored in the first memory means.

45. The device for authenticating user'"'"'s access rights to resources of claim 44, wherein

the response generation means further comprises:

third calculation means for calculating the t-th power of the component u of the challenging data pair stored in the first memory means modulo p, where t denotes proof support information stored in the third memory means (u^t mod p);

fourth calculation means for calculating the F(p, e)-th power of u modulo p (u^{F(p, e)} mod p), where e denotes the user unique identifying information stored in the second memory means and F(x, y) denotes a two-variable collision-free function; and

fifth calculation means for calculating a response R by dividing the product of the other component C of the challenging data pair and the result calculated by the fourth calculation means by the result calculated by the third calculation means modulo p (R=Cu^{F(p, e)} u<sup>−

t</sup> mod p).

46. The device for authenticating user'"'"'s access rights to resources of claim 45, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

47. The device for authenticating user'"'"'s access rights to resources of claim 20, wherein

the unique security characteristic information of the device is the signature key X of an ElGamal public key pair with a modulus p and a generator G,

the public key Y corresponding to X is the X-th power of G modulo p (Y=G^X mod p),

a response stored in the fifth memory means is a pair of R and S, and

the verification means verifies the legitimacy of the response R stored in the fifth memory means by verifying that the C-th power of G for the challenging data C stored in the fourth memory means is congruent modulo p with the product of the R-th power of Y and the S-th power of R (G^c mod p=Y^RR^S mod p).

48. The device for authenticating user'"'"'s access rights to resources of claim 47, wherein

proof support information t stored in the third memory means satisfies the relation t=X+F(p, e), where e denotes the user unique identifying information stored in the second memory means, and F(x, y) denotes a two-variable collision-free function, and

the response generation means generates a response pair R and S by carrying out the following steps of:

generating a random number k;

calculating R as the k-th power of G modulo p (R=G^k mod p); and

calculating S according to the relation S=(C−

RX) k<sup>−

1</sup> mod (p−

1).

49. The device for authenticating user'"'"'s access rights to resources of claim 48, further comprising:

protect means for preventing any data inside from being observed or being tampered with from the outside, confining the second memory means and the fourth calculation means.

50. The device for authenticating user'"'"'s access rights to resources of claim 4, wherein

the user unique identifying information stored in the second memory means is a decryption key of a cipher function,

the proof support information stored in the third memory means is an encryption of the unique security characteristic information of the device with the encryption key corresponding the decryption key, and

the first calculation means calculates the unique security characteristic information of the device by decrypting the proof support information stored in the third memory means with the decryption key stored in the second memory means.

51. The device for authenticating user'"'"'s access rights to resources of claim 50, wherein

the cipher function is of the asymmetric key cryptography, and

the user unique identifying information is a component of the key pair of the cipher function.

52. The device for authenticating user'"'"'s access rights to resources of claim 51, wherein

the cipher function is of the public key cryptography, and

the user unique identifying information is the private key of the public key pair of the cipher function.

53. The device for authenticating user'"'"'s access rights to resources of claim 50, wherein

the cipher function is of the symmetric key cryptography, and

the user unique identifying information is the common secret key of the cipher function.

54. The device for authenticating user'"'"'s access rights to resources of claim 8, wherein

the verification device further comprises:

eighth memory means for storing a clear data encryption of which is the challenging data stored in the first memory means; and

comparison means for examining whether the clear data stored in the eighth memory means is identical with data inputted to the comparison means, and wherein

the verification means feeds the response stored in the fifth memory means to the comparison means, receives the answer from the comparison means, and thereby the verification means verifies the legitimacy of the response if and only if the received answer shows that the clear data stored in the eighth memory means is identical with the data inputted to the comparison means.

55. The device for authenticating user'"'"'s access rights to resources of claim 19, wherein

the verification device further comprises:

eighth memory means for storing clear data encryption of which is the seed for challenging data stored in the seventh memory means; and

comparison means for examining whether the clear data stored in the eighth memory means is identical with data inputted to the comparison means, and wherein

the verification means feeds the de-randomized value of the response stored in the fifth memory means to the comparison means, receives the answer from the comparison means, and thereby the verification means verifies the legitimacy of the response if and only if the received answer shows that the clear data stored in the eighth memory means is identical with the de-randomized value of the response inputted to the comparison means.

56. The device for authenticating user'"'"'s access rights to resources of claim 8, wherein

the verification device further comprises:

ninth memory means for storing a value obtained by applying a one-way function to clear data encryption of which is the challenging data stored in the seventh memory means;

sixth calculation means for outputting a value calculated by applying the one-way function to an inputted data; and

comparison means for examining whether the value stored in the ninth memory means is identical with data inputted to the comparison means, and wherein

the verification means feeds the response to the sixth calculation means, receives a result from the sixth calculation means, feeds the result to the comparison means and receives an answer from the comparison means, and thereby the verification means verifies the legitimacy of the response if and only if the received answer shows that the result of the calculation by the sixth calculation means is identical with the data stored in the ninth memory means.

57. The device for authenticating user'"'"'s access rights to resources of claim 19, wherein

the verification device further comprises:

ninth memory means for storing a value obtained by applying a one-way function to clear data encryption of which is a seed for the challenging data stored in the seventh memory means;

sixth calculation means for outputting a value calculated by applying the one-way function to inputted data, and comparison means for examining whether the value stored in the ninth memory means is identical with data inputted to the comparison means, and wherein

the verification means feeds the de-randomized value of the response to the sixth calculation means, receives a result from the sixth calculation means, feeds the result to the comparison means and receives an answer from the comparison means, and thereby the verification means verifies the legitimacy of the response if and only if the received answer shows that the result of the calculation by the sixth calculation means is identical with the data stored in the ninth memory means.

58. The device for authenticating user'"'"'s access rights to resources of claim 8, wherein

the verification device further comprises:

program execution means for executing code of a program encryption of which is the challenging data stored in the seventh memory means, and wherein

the verification means feeds the response stored in the fifth memory means as program code to the program execution means, and

the program execution means correctly functions if and only if the response generation means correctly decrypts the challenging data which is an encryption of the code of the program, that is, the encryption of the program is correctly decrypted.

59. The device for authenticating user'"'"'s access rights to resources of claim 19, wherein

the verification device further comprises:

program execution means for executing code of a program encryption of which is the seed for challenging data stored in the seventh memory means, and wherein

the verification means feeds the de-randomized value of the response stored in the fifth memory means as program code to the program execution means, and

the program execution means correctly functions if and only if the response generation means correctly decrypts the seed for challenging data which is an encryption of the code of the program, that is, the encryption of the program is correctly decrypted.

60. The device for authenticating user'"'"'s access rights to resources of claim 8, wherein

the verification device further comprises:

program execution means;

program storing means; and

program decryption means, and wherein

the program storing means stores code of a program a part or all of which is encrypted,

an encryption of the decryption key for the partial or whole encrypted program code is the challenging data stored in the seventh memory means,

the verification means feeds the response to the program decryption means,

the program decryption means decrypts the program stored in the program storing means with the response as a decryption key, and

the program execution means correctly executes the decrypted program if and only if the response generation means correctly decrypts the challenging data, that is, the decryption key for decrypting the encryption of the program is correctly decrypted.

61. The device for authenticating user'"'"'s access rights to resources of claim 19, wherein

the verification device further comprises:

program execution means;

program storing means; and

program decryption means, and wherein

the program storing means stores code of a program a part or all of which is encrypted,

an encryption of the decryption key for the partial or whole encrypted program code is the seed for challenging data stored in the seventh memory means,

the verification means feeds the de-randomized value of the response to the program decryption means,

the program decryption means decrypts the program stored in the program storing means with the response as a decryption key, and

the program execution means correctly executes the decrypted program if and only if the response generation means correctly decrypts the seed for the challenging data, that is, the decryption key for decrypting the encryption of the program is correctly decrypted.

62. The device for authenticating user'"'"'s access rights to resources of claim 17, wherein

the proving device and the verification device are installed in a box material, and

the verification device transfers the challenging data stored in the fourth memory means to the first memory means of the proving device and the proving device transfers the response generated by the response generation means to the fifth memory means of the verification device without using a communication network outside of the box material.

63. A method for authenticating user'"'"'s access rights to resources by verifying the legitimacy of a response generated from challenging data for proving the user'"'"'s access rights, comprising:

a step for storing the challenging data;

a step for storing unique identifying information of the user;

a step for storing proof support information which is a result of predetermined computations to the unique identifying information of the user and unique security characteristic information;

a step for generating a response by executing predetermined computations to the challenging data, the unique identifying information of the user and the proof support information; and

a step for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation.

64. A computer program product for use with a computer, the computer program product comprising:

a computer usable medium having computer readable program code means embodied in the medium for causing the computer to authenticate user'"'"'s access rights to resources by verifying the legitimacy of a response generated from challenging data for proving the user'"'"'s access rights, the computer program product having;

computer readable program code means for causing the computer to store the challenging data;

computer readable program code means for causing the computer to store unique identifying information of the user;

computer readable program code means for causing the computer to store proof support information which is a result of predetermined computations to the unique identifying information of the user and unique security characteristic information;

computer readable program code means for causing the computer to generate a response by executing a predetermined computations to the challenging data, the unique identifying information of the user and the proof support information; and

computer readable program code means for causing the computer to verify the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation.

65. A computer program product for use with a computer, the computer program product comprising:

a computer usable medium having computer readable program code means embodied in the medium for causing the computer to generate a response from challenging data, the legitimacy of which is to be verified for authenticating user'"'"'s access rights, the computer program product having;

computer readable program code means for causing the computer to store the challenging data;

computer readable program code means for causing the computer to store unique identifying information of the user;

computer readable program code means for causing the computer to store proof support information which is a result of predetermined computations to the unique identifying information of the user and unique security characteristic information; and

computer readable program code means for causing the computer to generate a response by executing predetermined computations to the challenging data, the unique identifying information of the user and the proof support information.

66. A program execution control device for authenticating user'"'"'s access rights to resources by verifying the legitimacy of a response generated from challenging data for proving the user'"'"'s access rights and controlling execution of a program based on the authentication of the user'"'"'s access rights, comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of predetermined computations to the unique identifying information of the user and unique security characteristic information of the device;

response generation means for generating a response by executing predetermined computations to the challenging data, the unique identifying information of the user and the proof support information;

verification means for verifying the legitimacy of the response by verifying that the response, the challenging data and the unique security characteristic information satisfy a specific predefined relation; and

continuation means for continuing execution of the program if the legitimacy of the response is verified.

67. An information processing apparatus for authenticating user'"'"'s access rights to specific information processing resources by verifying the legitimacy of a response generated for proving the user'"'"'s access rights and permitting access to the specific information processing resources, comprising:

first memory means for storing challenging data;

second memory means for storing unique identifying information of the user;

third memory means for storing proof support information which is a result of predetermined computations to the unique identifying information of the user and unique security characteristic information;

response generation means for generating a response by executing predetermined computations to the challenging data, the unique identifying information of the user and the proof support information;

verification means for verifying the legitimacy of the response by verifying that tho response, the challenging data and the unique security characteristic information satisfy a specific predefined relation; and

permission means for permitting access to the specific information processing resources if the legitimacy of the response is verified.