[go: up one dir, main page]

WO2005041474A1 - 認証システム及び遠隔分散保存システム - Google Patents

認証システム及び遠隔分散保存システム Download PDF

Info

Publication number
WO2005041474A1
WO2005041474A1 PCT/JP2004/015184 JP2004015184W WO2005041474A1 WO 2005041474 A1 WO2005041474 A1 WO 2005041474A1 JP 2004015184 W JP2004015184 W JP 2004015184W WO 2005041474 A1 WO2005041474 A1 WO 2005041474A1
Authority
WO
WIPO (PCT)
Prior art keywords
value
authentication
server
data
terminal device
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2004/015184
Other languages
English (en)
French (fr)
Inventor
Hideki Imai
Kazukuni Kobara
Seonghan Shin
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Foundation for the Promotion of Industrial Science
Original Assignee
Foundation for the Promotion of Industrial Science
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Foundation for the Promotion of Industrial Science filed Critical Foundation for the Promotion of Industrial Science
Priority to JP2005514934A priority Critical patent/JP4774492B2/ja
Priority to US10/577,111 priority patent/US7895436B2/en
Priority to CN2004800307512A priority patent/CN1871810B/zh
Publication of WO2005041474A1 publication Critical patent/WO2005041474A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0891—Revocation or update of secret information, e.g. encryption key update or rekeying
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/3026—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters details relating to polynomials generation, e.g. generation of irreducible polynomials
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3226—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using a predetermined code, e.g. password, passphrase or PIN
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3271—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using challenge-response
    • H04L9/3273—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using challenge-response for mutual authentication
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/04—Masking or blinding

Definitions

  • the present invention relates to an authentication system that is resistant to leakage of information related to authentication and a remote distributed storage system that can securely store data using the authentication system.
  • a user ID and a password known only to the user are input from the terminal device and matched with the information stored on the server side. Then, a method of authenticating a valid user is known.
  • Non-Patent Documents 1 to 3 are based on the method of password analysis by offline analysis when information encrypted with a password is leaked from the user's terminal device or the password authentication data is leaked from the server. There is a problem that can be requested.
  • the method of repeatedly entering the password online to the server can take measures such as denying access according to the number of times the password is incorrect.However, in the offline analysis work, take preventive measures. There is also the problem that it cannot be changed. Also, if the password is leaked, there is also a problem that the data stored in the system that can log in with this password is leaked. Disclosure of the invention
  • An object of the present invention is to provide an authentication system that is resistant to information leakage and that can securely exchange encryption keys.
  • An object of the present invention is to provide a remote decentralized storage system that can securely store data using the authentication system according to the present invention.
  • the gist of the present invention is an authentication system that performs mutual authentication between a terminal device and a server, wherein the terminal device performs password authentication for server registration based on a password determined in advance by a user.
  • Data decompression means for obtaining data H and authentication information P 'for user storage; storage means for pre-stored authentication information P' obtained by the data decompression means; and authentication information P 'read from the storage means.
  • a value V1 is determined by a predetermined formula using the value MK as an input, and transmitted to a server, and a value obtained by a predetermined formula using the value V2 received from the server and the value MK as an input V2 is provided, and an authentication result judgment means is provided for authenticating the server if it matches.
  • the server includes a storage unit that stores password authentication data H obtained by the data decompression unit in advance, a password authentication data read from the storage unit, and a random number generated internally as input.
  • a mask calculating means for obtaining a value Y2 by a predetermined calculation formula, transmitting the value to the terminal device, a password authentication data H, a random number generated internally, and a value Y1 received from the terminal device as a predetermined value;
  • a master key generating means for obtaining a value MK by a calculation formula; a value V2 obtained by a predetermined calculation formula by using the value MK as an input; transmitting the value to the terminal device; and transmitting the value V1 and the value V1 received from the terminal device.
  • An authentication result determination unit is provided that compares the value MK as an input with a value VI based on a predetermined calculation formula, and authenticates the terminal device when the values match.
  • the gist of the present invention is an authentication program that operates on a terminal device in an authentication system that performs mutual authentication between the terminal device and a server.
  • the authentication program is based on a password determined in advance by a user.
  • a data decompression process for obtaining a pass-word authentication data H for one-pass registration and authentication information P ′ for storing a user; a storage process for previously storing the authentication information P ′ obtained by the data decompression process; Combination processing to obtain a value P by a predetermined calculation formula using the authentication information P 'stored in the process and the password input at the time of authentication, and a predetermined process using the value P and a random number generated inside as inputs
  • a value Y1 is calculated by the following formula, and a mask calculation process for transmitting the value to the server is performed.
  • the value P, the internally generated random number, and the value Y2 received from the server are input as predetermined values.
  • An authentication program operating on a server in an authentication system for performing authentication comprising: a storage process for storing password authentication data H in advance; and a path stored by the storage process.
  • the password authentication data H and the internally generated random number are input, a value Y2 is obtained by a predetermined calculation formula, a mask calculation process to be transmitted to the terminal device is performed, and the password authentication data H and the internally generated random number are calculated.
  • a master key generation process for obtaining a value MK by a predetermined formula using the value Y1 received from the terminal device as an input, obtaining a value V2 by a predetermined formula using the value MK as an input, and transmitting the value to the terminal device.
  • the computer receives the value V1 received from the terminal device and the value MK, compares the value V1 with the value VI according to a predetermined calculation formula, and if the values match, authenticates the terminal device. .
  • the gist of the present invention is an authentication system for performing mutual authentication between a terminal device and a server, wherein the terminal device performs password authentication data for server registration based on a password determined in advance by a user.
  • H and the data decompression means for obtaining the authentication information P 'for storing the user, and the authentication information P' obtained by the data decompression means and the RSA public key (N, e) obtained by the RSA key generation means are stored in advance.
  • Storage means combining means for obtaining a value W by a predetermined calculation formula by using the authentication information P 'read from the storage means and the password input at the time of authentication, and reading the value W and the storage means
  • a mask calculating means for obtaining a value Z by a predetermined formula using the RSA public key (N, e) and a random number T generated internally as input, and transmitting the value to the server, and a value received from the server V2 and the random number T are input and compared with a value V2 according to a predetermined calculation formula, and an authentication result determining means for authenticating the server when they match, and a value VI is calculated by a predetermined calculation formula using the random number T as an input.
  • a verifier generating means for transmitting to the server, the server comprising: an RSA key generating means for obtaining an RSA public key (N, e) and an RSA secret key (N, d); and the RSA key.
  • Storage means for previously storing the RSA secret key (N, d) obtained by the generation means and the password authentication data H obtained by the data expansion means; and an RSA secret key (N, d) read from the storage means.
  • Master key generating means for inputting the value H and the value Z received from the terminal device to obtain a value T by a predetermined calculation formula; and inputting the value T to obtain a value V 2 by a predetermined calculation formula.
  • the gist of the present invention is an authentication program that operates on a terminal device in an authentication system that performs mutual authentication between the terminal device and a server.
  • the authentication program for server registration is performed based on a password determined in advance by a user.
  • the gist of the present invention is an authentication program that operates on a server in an authentication system that performs mutual authentication between a terminal device and a server, wherein an RSA public key (N, e) and an RSA secret key (N, d) are used.
  • the computer is made to perform the result determination process.
  • the gist of the present invention is a remote distributed storage system for mutually authenticating between a terminal device and a plurality of servers, and distributing and storing data to be stored in the terminal device in the server.
  • the terminal device includes: a data decompression unit that obtains a password authentication data H for server registration and authentication information P ′ for user storage based on a password determined in advance by a user; Storage means for preliminarily storing the authentication information P 'obtained by the above, and coupling means for obtaining the value P. by a predetermined formula using the authentication information P' read from the storage means and the password input at the time of authentication.
  • the value P1 and a random number generated internally are input and a value Y1 is obtained by a predetermined calculation formula, and a mask calculating means for transmitting the value Y1 to the server is generated.
  • a master key generating means for inputting a random number and a value Y2 received from the server to obtain a value MK by a predetermined calculation formula; obtaining a value V1 by a predetermined calculation formula by receiving the value MK as an input; Then, the value V2 received from the server is compared with the value VI, and the authentication result determining means for authenticating the server when the values match, and the session key SK when the server is authenticated.
  • Session key generating means for generating the same number of servers; data dividing means for dividing the data to be stored to obtain the same number of divided data as the number of authenticated servers; and each of the divided data and the storage object Data storing means for encrypting the identification information for identifying the data using the session key SK shared with the storage destination server and transmitting the encrypted data to each server; A data restoring means for receiving the divided data from the storage device and restoring the data to be saved; the server comprising: a storage means for previously storing the password authentication data H obtained by the data decompression means; and the storage means.
  • Mask calculation means for obtaining the value Y2 by a predetermined formula using the password authentication data H read out from the memory and the internally generated random number as an input, and transmitting the password authentication data H to the terminal device;
  • a master key generation means for inputting the random number generated in step 2 and the value Y1 received from the terminal device to obtain a value MK according to a predetermined calculation formula; and a value V2 according to a predetermined calculation formula using the value MK as input.
  • the gist of the present invention is that a terminal device and a plurality of servers mutually authenticate each other, and the data to be stored in the terminal device is distributed and stored in the server on the terminal device in the remote distributed storage system.
  • a remote storage program that operates, a data decompression process for obtaining password authentication data H for server registration and authentication information P ′ for user storage based on a password predetermined by the user;
  • a storage process in which the authentication information P 'obtained by the data decompression process is stored in advance, and a value P is obtained by a predetermined formula using the authentication information P' read from the storage process and the password input at the time of authentication as inputs.
  • the value VI is obtained and transmitted to the server, and the value V2 and the value V1 received from the server are compared and collated, and if they match, an authentication result determination process for authenticating the server and server authentication are performed.
  • the gist of the present invention is that a terminal device and a plurality of servers mutually authenticate each other, and operate on a server in a remote distributed storage system in which data to be stored in the terminal device is distributed and stored in the server.
  • a remote storage program that stores password authentication data H obtained by data decompression processing in advance, and stores a password authentication data H read from the storage processing and a random number generated internally.
  • a value Y2 is obtained by a predetermined calculation formula as an input, a mask calculation process to be transmitted to the terminal device, and the password authentication data H, a random number generated inside, and a value Y1 received from the terminal device are obtained.
  • Master-key generation processing for obtaining a value MK by a predetermined calculation expression as an input, and obtaining a value V2 by a predetermined calculation expression by inputting the value MK to a terminal device
  • Authentication value judgment processing for comparing the value V1 and the value V2 received from the terminal device, and authenticating the terminal device when the values V1 and V2 match.
  • a session key generation process for generating a key; a data reception process for receiving the divided data received from the terminal device; a data storage process for storing the divided data; and the divided data stored in the data storage process And transmitting the data to a terminal device.
  • FIG. 1 is a block diagram illustrating a configuration of a terminal device according to an embodiment of the present invention. .
  • FIG. 2 is a block diagram showing a configuration of the data decompressor 11 shown in FIG.
  • FIG. 3 is a block diagram showing a configuration of the data decompressor 11 shown in FIG.
  • FIG. 4 is a block diagram showing a configuration of the data decompressor 11 shown in FIG.
  • FIG. 5 is a block diagram showing the configuration of a device that performs mutual authentication and key exchange.
  • FIG. 6 is a block diagram showing a configuration of the terminal device 1 shown in FIG.
  • FIG. 7 is a block diagram showing a configuration of the server 2 shown in FIG.
  • FIG. 8 is a block diagram showing a configuration of the data decompressor 11 shown in FIG.
  • FIG. 9 is a block diagram showing the configuration of the terminal device 1 for updating the password authentication data 11.
  • FIG. 10 is a block diagram showing the configuration of the server 2 for updating password authentication data-1.
  • FIG. 11 is a block diagram showing the configuration of the terminal device 1 for updating the password authentication data 12.
  • FIG. 12 is a block diagram showing the configuration of the server 2 for updating password authentication data-2.
  • FIG. 13 is a block diagram showing a configuration of the data decompressor 11 shown in FIG.
  • FIG. 14 is a block diagram showing a configuration of the data decompressor 11 shown in FIG.
  • FIG. 15 is a block diagram illustrating a configuration of the server 2 when performing initialization processing using secure communication.
  • FIG. 16 is a block diagram showing the configurations of the terminal device 1 and the server 2 when performing the initialization process using insecure communication.
  • FIG. 17 is a block diagram showing a configuration of the terminal device 1 shown in FIG.
  • FIG. 18 is a block diagram showing a configuration of the server 2 shown in FIG.
  • FIG. 19 is a block diagram showing a configuration of the terminal device 1 in a case where the updating process is performed using the master key.
  • FIG. 20 is a block diagram showing a configuration of the server 2 in a case where an update process is performed using a master key.
  • FIG. 21 is a block diagram showing a configuration of the remote distributed storage device 5 when the distributed data is not stored in the terminal.
  • FIG. 22 is a block diagram showing a configuration of the data distributor 51 shown in FIG.
  • FIG. 23 is a block diagram showing a configuration of the remote distributed storage device 5 when data is not stored in the terminal.
  • FIG. 24 is a block diagram showing the configuration of the data decompressor 54 shown in FIG.
  • FIG. 25 is a block diagram showing a configuration of the remote distributed storage device 5 when the distributed data is also stored in the terminal.
  • FIG. 26 is a block diagram showing the configuration of the data divider 51 shown in FIG.
  • FIG. 27 is a block diagram showing a configuration of the remote distributed storage device 5 when the distributed data is also stored in the terminal.
  • FIG. 28 is a block diagram showing a configuration of data restorer 54 shown in FIG. Best mode for carrying out the invention.
  • the user's terminal device and the server's authentication device mutually authenticate each other and secure the same session key.
  • P and q are prime numbers and have a relationship of d I p-l.
  • QI p-1 means that Q is a value divisible by p-1.
  • g j mod p means the remainder of the power of g raised to the j-th power divided by p in the exponential operation.
  • p and Q indicate the operation system (characteristic of the prime field).
  • the random number generated by the random number generator generates RG (Z / q Z) * at random.
  • (Z / qZ) * indicates a set of ⁇ 1, 2, ⁇ , Q ⁇ .
  • N indicates the length of the password. II means concatenation of values (conc at ena ti on).
  • FIG. 1 is a block diagram showing a configuration of an initialization process of a user terminal device.
  • the data decompressor 11 When a user inputs a password, the data decompressor 11 generates password authentication data H for server registration and a value P for user storage, and the password authentication data H is received by the server. Passed, the value P, is stored in memory 12.
  • the data decompressor 11 can be composed of a polynomial, a polynomial and a hash function, a hash function, a pseudorandom number generator, and the like.
  • a polynomial is randomly generated by a polynomial generator 1 1 1.
  • the first-order polynomial ( ⁇ '( ⁇ ) !-Xmo dq) with X as a variable
  • the n-th polynomial ( ⁇ ' ( ⁇ ) ⁇ ! ⁇ ⁇ + ⁇ 2 ⁇ ⁇ 2 + ⁇ ⁇ -+ ⁇ -x n mod dq).
  • the password authentication data generator 111 When the polynomial and the password of the user are input, the password authentication data generator 111 generates password authentication data H.
  • p '(1) is the value calculated by inserting the server ID (for example, "1") in place of X (' X).
  • the password authentication data H must be securely notified by the user by directly passing it to the server, sending it by mail, or notifying it by telephone.
  • a polynomial is randomly generated by a polynomial generator 1 1 1.
  • the first-order polynomial (p, (X) l-xmo dq) with ⁇ ⁇ ⁇ as a variable
  • the n-th polynomial (p, (x) CE I ⁇ ⁇ + ⁇ 2 ⁇ x 2 +- ⁇ -+ ⁇ ⁇ ⁇ x n mo dq).
  • ⁇ is randomly chosen from (Z / qq) *.
  • the user enters a password that he remembers (for example, "Pooh 93").
  • the password authentication data generator 111 When the polynomial and the password of the user are input, the password authentication data generator 111 generates password authentication data H.
  • p, (1) is the value calculated by inserting the server ID (for example, “1”) in place of x in p, (x). It is necessary for the user to notify the user of the password authentication data safely by directly passing it to the server, sending it by mail, or notifying him by telephone.
  • a polynomial is randomly generated by a polynomial generator 1 19.
  • the first-order polynomial ( ⁇ '(X) 1-xmodN) with X as a variable
  • the nth-order polynomial ( ⁇ ' ( ⁇ ) a! ⁇ ⁇ ⁇ - ⁇ 2 ⁇ ⁇ 2 + ⁇ ⁇ ⁇ + Q! N ⁇ x n mod dN).
  • the hash function generator 120 generates a hash function HASH randomly.
  • HASH is a one-way hash function.
  • the user enters a password that he remembers (for example, "Pooh 93").
  • the password authentication data generator 1 2 1 generates password authentication data H.
  • ID (U) and ID (S) represent user and server IDs, respectively.
  • p, (1) is the value calculated by inserting "1" in place of X in p '(X).
  • the password authentication data generator 122 generates password authentication data H for the i-th server.
  • ID (U) and ID (S) represent the ID of the user and the i-th server, respectively.
  • (i) is the value calculated by inserting "i" in place of X in the nth degree polynomial p '(X).
  • the password authentication data H must be securely notified by the user by directly passing it to the server, sending it by mail, or notifying it by telephone.
  • the hash function generator 120 generates a hash function HASH randomly.
  • HASH is a one-way hash function.
  • the user enters a password that he remembers (for example, "Pooh 93").
  • Polynomial, hash function and user password
  • the password authentication data generator 121 generates password authentication data H.
  • ID (U) and ID (S) represent user and server IDs, respectively.
  • p '(1) is the value calculated by inserting' 1 'in place of X in p' (X).
  • the password authentication data generator 121 when the number of servers to be registered is n, the password authentication data generator 121 generates password authentication data H for the i-th server.
  • I D (U) and I D (S) represent the ID of the user and the i-th server, respectively.
  • p '(i) is the value calculated by inserting "i" in place of X in the nth degree polynomial p' (x).
  • the password authentication data H must be securely notified by the user by directly passing it to the server, sending it by mail, or notifying it by telephone.
  • a hash function HASH is randomly generated by a hash function generator 113.
  • secret value generator 114 also randomly generates secret value S.
  • the user enters the password he remembers (for example, "Poo 93").
  • the password authentication data generator 1 15 generates password authentication data H.
  • ID (U) and ID (S) are Indicates the user and server ID.
  • the password authentication data H must be securely notified by the user by passing it directly to the server, sending it by mail, or notifying it by telephone.
  • a hash function HASH is randomly generated by a hash function generator 113.
  • secret value generator 114 also randomly generates secret value S.
  • the user enters a password that he remembers (for example, "Poo 93").
  • the password authentication data generator 1 15 generates password authentication data H.
  • I D (U) and I D (S) represent the user and server I D, respectively.
  • the password authentication data H must be securely notified by the user by directly passing it to the server, sending it by mail, or notifying it by telephone.
  • a pseudorandom number function PRNG is randomly generated by a pseudorandom number generator 116.
  • the secret value generator 117 also randomly generates the secret value S.
  • the user enters a password that he remembers (for example, "Pooh 93").
  • the password authentication data generator 118 generates the password authentication data H.
  • H h PRNG (sllp .
  • a pseudo-random number function PRNG is randomly generated by a pseudo-random number generator 116.
  • secret value generator 117 also randomly generates secret value S.
  • the user enters a password that he remembers (for example, "Pooh 93").
  • the password authentication data generator 118 In response to the input of the pseudo-random function PRNG, the secret value S, and the user's password, the password authentication data generator 118 generates the password authentication data H.
  • ID (U) and ID (S) represent user and server IDs, respectively.
  • the password authentication data H must be securely notified by the user by passing it directly to the server, sending it by mail, or notifying it by telephone.
  • the terminal device 1 operates as follows irrespective of whether the above-described polynomial is used (part 1) or the case where the polynomial is used (part 2).
  • the mask calculator 34 calculates from the P input from the combiner 32 and the random number generated by the random number generator 33 by Y gK 1 ⁇ h— p (1) mo.
  • the communication processing unit 35 transmits to the server 2 and receives Y 2 from the server 2.
  • the authentication result judgment unit 37 receives MK as input, calculates by Vi-HASH (00 II Y! II Y 2 II MK), transmits this to the server 2 by the communication processing unit 35, and receives from the server 2 the V 2 and HASH (0 1 II Y x II Y 2 II MK) Compare.
  • HASH is a directional hash function
  • MAS Message Au thenticati on Code
  • authentication result determination unit 37 V 2 and HASH (01 II Y! II Y 2 II MK) do not match gar
  • authentication result determination unit 37 informs the error generator 38 does not match I do.
  • the error generator 38 generates an error and suspends the processing.
  • the authentication result of the determination unit in the 37 V 2 and HASH (0 1
  • Yi II Y 2 II MK) If match Gar authenticated as the server 2 legitimate device set Chillon key generator 39, SK HASH (1 1 II II Y 2 II MK) Generate an application key SK.
  • the terminal device 1 operates as follows irrespective of whether the above-mentioned polynomial and the hash function are used (part 1), or whether the polynomial and the hash function are used (part 2).
  • the stored polynomial and hash function P ′ ( ⁇ ′ (X), HASH) are read from the memory 12 provided in the terminal device 1 of the user.
  • the mask calculator 34 calculates P from the combiner 32 and the random number generated by the random number generator 33 by using -gK 1 '! ⁇ mo dp.
  • p '(1) is the value calculated by inserting "1" in place of x in p' (x).
  • the communication processing unit 35 transmits to the server 2 and receives Y 2 from the server 2.
  • the mass key generator 36 receives the ⁇ output from the combiner 32 and the Y 2 received from the random number generator 33 as inputs, and outputs MK and MK (Y 2 ⁇ h—P R1 mod dp Calculate and output.
  • p '(i) is the value calculated by inserting "i" in place of X in p' (X) for the i-th server.
  • the communication processing unit 35 transmits to the server 2 and receives Y 2 from the server 2.
  • the authentication result determining unit 37 receives MK as input, calculates by HASH (00 II Yi II Y 2 II MK), transmits this to the server 2 by the communication processing unit 35, and receives V from the server 2. Compare 2 with HASH (01 II ⁇ II ⁇ 2 II MK).
  • HASH is a one-way hash function, and MAC (Message Autheticati on Code) may be used instead of HASH.
  • authentication result determination unit 37 V 2 and HASH (01 II Y x II Y 2 II MK) do not match gar
  • authentication result determination unit 37 informs the error generator 38 does not match I do.
  • the error generator 38 generates an error and suspends the processing.
  • Terminal device 1 operates as follows regardless of whether the above-described hash function is used (part 1) or the case where the hash function is used (part 2).
  • Mask calculator 34 The random number R i and color which is generated in the P and the random number generator 33 that is input from the coupler 32 is calculated by Yi g ⁇ h one p mo dp.
  • the communication processing unit 35 transmits the ⁇ to the server 2, receives the Upsilon 2 from the server 2.
  • the master key generator 36 receives the K output from the combiner 32 and the Y 2 received from the random number generator 3 3 as inputs, and calculates MK by ⁇ -( ⁇ 2 ⁇ h— p ) R1 mod dp. Calculate and output.
  • the authentication result determination unit 37 receives MK as input, calculates by V-HASH (0 II Y x II ⁇ 2 II MK), and transmits this V to the server 2 by the communication processing unit 35. Compare V 2 and HASH received from the server 2 (0 1 II Y! II Y 2 II MK).
  • HASH is a one-way hash function, and MAC (Message Authentication Code) may be used instead of HASH.
  • Terminal device 1 operates as follows irrespective of whether the pseudo-random number generator described above is used (part 1) or the pseudo-random number generator is used (part 2).
  • Part 1 When using a polynomial (Part 1), When using a polynomial and a hash function (Part 1), When using a hash function (Part 1), When using a pseudo-random function (Part 1)
  • Server 2 uses the above-mentioned polynomial (Part 1), uses a polynomial and a hash function (Part 1), uses a hash function (Part 1), uses a pseudorandom number generator (Part 1) Regardless of 1), it operates as follows.
  • the mask calculator 43 Reads the user ID and password authentication data H stored in the memory 41 provided in the server 2.
  • the communication processing unit 44 transmits the calculated Y 2 to the terminal device 1, and outputs the received Y 2 from the terminal device 1 to the master key generator 45.
  • Mask key generator 45 of MK as input from R 2 to a communication processing unit 44 from H and a random number generator 42 which is read out from the memory 41, MK (Yi - H ) calculated by R2 mo d P Output MK.
  • HASH is a one-way hash function, and MAC (Message Authentication Code) may be used instead of HASH.
  • Server 2 uses the above-mentioned polynomial (Part 2), uses a polynomial and a hash function (Part 2), uses a hash function (Part 2), uses a pseudo-random number generator (Part 2) Regardless of 2), it operates as follows.
  • the communication processing unit 44 transmits the Y 2 obtained by calculating in the terminal apparatus 1, and outputs the received from the terminal 1 to the master key generator 45.
  • HASH is a one-way hash function
  • MAC Message Au thenticati on Code
  • HASH (00 II Y! II Y 2 II MK) does not match in the authentication result judgment unit 46
  • the authentication result judgment unit 46 notifies the error generator 47 that they do not match. .
  • the error generator 47 generates an error and interrupts the processing.
  • HASH (00 11 Y 1 II ⁇ 2 II MK) matches in the authentication result determination unit 46
  • FIG. 9 is a block diagram illustrating a configuration of a user terminal device update process.
  • the update value generator 14 A value H 'and an updated polynomial P' for user storage are generated, H 'is passed to the server, and the updated polynomial P' is stored in memory 12.
  • the updating process here uses the above-mentioned polynomial (Part 1), uses the polynomial (Part 2), uses the polynomial and hash function (Part 1), and uses the polynomial and hash function. When used. (Part 2) It is possible to apply.
  • a polynomial is randomly generated by the polynomial generator 13.
  • j3 is chosen at random from (Z / q Z) *.
  • the stored polynomial ⁇ ′ ⁇ ′ ( ⁇ ) is read from the memory 12 provided in the user terminal device 1.
  • the update value generator 14 When the polynomial t ′ (x) and the polynomial P ′ (x) are input, the update value generator 14 generates an updated polynomial P ′ for user storage and a value for server update.
  • the value H 'for updating the server is —They need to be notified securely by handing them over to the server, sending them by mail, or notifying them by telephone.
  • a polynomial is randomly generated by the polynomial generator 13.
  • a first-order polynomial (t '(X) ⁇ ! Xmo dq) with X as a variable
  • an n-order polynomial (t , to generate a (x) ⁇ 8 i ⁇ x + j8 2 ⁇ x 2 + ⁇ ⁇ ⁇ + j8 n ⁇ x n mo dq).
  • j3 is chosen at random from (Z / q Z) *.
  • (X) i3 xmodq.
  • the update value generator 14 When the polynomial t ′ (x) and the polynomial P ′ (X) are input, the update value generator 14 generates an updated polynomial P ′ for storing the user and a value H ′ for updating the server.
  • t '(1) is the value calculated by inserting the server ID (for example, "1") in place of x in t' (x).
  • the value H 'for updating the server must be securely notified by the user, such as by passing it directly to the server, sending it by mail, or notifying it by telephone.
  • a polynomial is randomly generated by the polynomial generator 13.
  • a first-order polynomial ⁇ 1 -xmo dN
  • x as a variable
  • n-th polynomial (t' (x) i3! ⁇ x + jS 2 ⁇ x 2 +- ⁇ ⁇ + j8 n ⁇ x n mod n ).
  • 3 is chosen at random from ( ⁇ / qZ) *.
  • Polynomial !; '(X) and polynomial p' (X) are input
  • the update value generator 14 generates an updated polynomial P 'for user storage and a value H' for server update.
  • the update value generator 14 For example, if the number of registered servers is n, the update value generator 14 generates a server update value H 'for the i-th server.
  • t '(i) is the value calculated by inserting "i" in place of x in the n-th order polynomial t' (x).
  • the value H 'for updating the server must be securely notified by the user, such as by passing it directly to the server, sending it by mail, or notifying it by telephone.
  • a polynomial is randomly generated by the polynomial generator 13.
  • a first-order polynomial i ⁇ xmod dN
  • X as a variable
  • the polynomial and the hash function P ′ (p, (X), HASH) stored from the memory 12 provided in the user terminal device 1 are read.
  • the update value generator 14 When the polynomial t ′ (X) and the polynomials p and (X) are input, the update value generator 14 generates an updated polynomial P ′ for storing the user and a value H ′ for updating the server.
  • the update value generator 14 generates a server update value H 'for the i-th server.
  • t '(i) is the value calculated by inserting "i" in place of x in the n-th order polynomial t' (x).
  • the value H 'for updating the server must be securely notified by the user by directly passing it to the server, by mail, or by telephone.
  • Part 1 When using a polynomial (Part 1), When using a polynomial and a hash function (Part 1)
  • Server 2 operates as follows regardless of whether the above-mentioned polynomial is used (part 1) or polynomial and hash function (part 1).
  • the user ID and the password authentication data H stored in the memory 41 provided in the server 2 are read.
  • the server update value H 'sent from the user's terminal device and the password authentication data H read from the memory 41 are input, the updated value is entered.
  • the generator 21 generates updated password authentication data H for storing in the server.
  • the memory 41 inside the server stores and stores the updated password authentication data H.
  • the update value generator 21 When the value H 'for server update sent from the user's terminal device and the password authentication data H read from the memory 41 are input, the update value generator 21 generates updated password authentication data H for server storage. .
  • the memory 41 inside the server stores and stores the updated password authentication data H.
  • the update value generator 21 When the server update value H 'sent from the user's terminal device and the password authentication data H read from the memory 41 are input, the update value generator 21 generates the updated password authentication data H for server storage. .
  • the memory 41 inside the server stores and stores the updated password authentication data H.
  • FIG. 11 is a block diagram showing the configuration of a user terminal updating process.
  • the update process is performed when the secret value S 'by the secret value generator 15, the new password PW' of the user, and the P 'stored from the memory 12 provided in the user terminal device 1 are input, and the password authentication data is updated.
  • the device 16 generates password authentication data H 'for updating the server and updated P' for storing the user, H 'is passed to the server 2, and the updated P' is stored in the memory. Save to 12.
  • the updating process uses the above-mentioned hash function (Part 1), uses the hash function (Part 2), uses the pseudo-random number generator (Part 1), generates the pseudo-random number. It can be applied to cases where a container is used (Part 2). The same applies when using a polynomial (Part 1), when using a polynomial (Part 2), when using a polynomial and a hash function (Part 1), and when using a polynomial and a hash function (Part 2). As described above, the application can be applied by using the same operation as the initialization processing, and thus the detailed description is omitted here. Terminal device update process>
  • the secret value generator 15 randomly generates a secret value S '.
  • the password authentication data updater 16 updates the updated P' for saving the user and the password authentication for updating the server.
  • Part 2 When a hash function is used (Part 2)
  • the secret value generator 15 randomly generates a secret value S '.
  • P ′ (S, HASH) stored in the memory 12 provided in the user terminal device 1 is read.
  • the password authentication data updater 16 updates the updated P 'for user storage and the password authentication for server update.
  • ID (U) and ID (S) represent the ID of the user and the server, respectively.
  • Part 1 When using a hash function (Part 1), When using a hash function (Part 2), When using a pseudo-random number generator (Part 1), When using a pseudo-random number generator (Part 2) )
  • server 2 operates as follows regardless of whether it uses the above-mentioned hash function (parts 1 and 2) or the pseudorandom number generator (parts 1 and 2).
  • the password authentication data update unit 22 transmits the password authentication data for server storage.
  • H is updated to H ′ sent from the user terminal 1.
  • a pair (PubK, PriK) of a public key (PubK) and a secret key (PriK) exists.
  • the public key is not secret and can be obtained by anyone.
  • En c PubK (m) for message m using a public key.
  • the ciphertext is based on the public key Cannot decrypt.
  • p and Q the same length.
  • RSA gains security from the difficulty of factoring large numbers N.
  • cryptographic systems have security parameters that describe their level of security.
  • k is used as the security parameter of the hash function HASH (provided that lZ2 k is small enough to be ignored), and 1 is used as the security parameter of the RSA public key method.
  • modulo N of A has length 1.
  • ⁇ 0, 1 ⁇ * indicates a set of finite binary strings
  • ⁇ 0, 1 ⁇ k indicates a set of binary strings of length k.
  • the hash function HASH is a secure one-way function that outputs ⁇ 0, 1 ⁇ k from the input of ⁇ 0, 1 ⁇ *
  • the FDH (Full-Doma in Hash) function is ⁇ 0, 1 ⁇ Is a safe one-way function that outputs Z N * ⁇ ⁇ 1 ⁇ from the input of *.
  • the random number generated by the random number generator randomly generates T (TGZ N *).
  • II means to concatenate values.
  • FIG. 1 is a block diagram showing a configuration of an initialization process of a user terminal device.
  • the data decompressor 11 When a user inputs a password, the data decompressor 11 generates password authentication data H for server registration and a value P 'for user storage, and the password authentication data H is received by the server. Passed and the value ⁇ '- is stored in memory 12.
  • the data decompressor 11 can be composed of a polynomial, an FDH function, an FDH function, and the like.
  • ⁇ ⁇ + ⁇ 2 ⁇ ⁇ 2 + ⁇ ⁇ + ⁇ ⁇ ⁇ x n mod d)
  • ⁇ is chosen at random from ⁇ ⁇ *
  • the password authentication data generator 124 generates the password authentication data H.
  • p, (1) is' (x) in the server's ID in place of x (e.g., "1") is a value calculated taking the.
  • the password authentication data H must be securely notified by the user by directly passing it to the server, sending it by mail, or notifying it by telephone.
  • ⁇ '(X) is P' (x) ⁇ xmodN, where the user enters a password that he or she remembers (for example, "Poo 93").
  • the password authentication data generator 124 When the polynomial, the FDH function, and the user password are input, the password authentication data generator 124 generates the password authentication data H.
  • the password authentication data generator 124 generates password authentication data H for the i-th server.
  • I D (U) and I D (S) represent the I D of the user and the i-th server, respectively.
  • p '(i) is the value calculated by inserting "i" in place of X in the nth degree polynomial p' (x).
  • the password authentication data H must be securely notified by the user by directly passing it to the server, sending it by mail, or notifying it by telephone.
  • the FDH function FDH is randomly generated by the 011 function generator 125.
  • the secret value generator 126 randomly generates a secret value S.
  • S is long enough to prevent traversal attacks (for example, S is 80 bits or more).
  • the user enters a password that he remembers (eg, "Pooh93").
  • the password authentication data generator 127 generates the password authentication data H.
  • I D (U) and I D (S) represent the user and server I D, respectively. It is necessary for the user to pass the passcode authentication data H safely, such as by passing it directly to the server, sending it by mail, or notifying it by telephone.
  • the server performs initialization when it wants to send the RSA public key to the user.
  • the server generates a public / private key pair according to the RSA public key method, and sends the public key to the user.
  • the initialization can be realized by secure communication or insecure communication.
  • the user determines whether the received public key is correct. This user decision provides the user with a way to determine whether the server has generated the selected public key in an appropriate manner.
  • the RSA key generator 23 generates a pair of a public key (N, e) and a secret key (N, d).
  • the RSA public key (N, e) must be securely notified by the server, such as by handing it directly to the user, sending it by mail, or notifying it by telephone.
  • the memory 41 inside the server stores and stores the RSA private key (N, d). -
  • a random number (RiG ⁇ 0, 1 ⁇ k ) is randomly generated by the random number generator 17 in the user terminal device 1 and transmitted to the server.
  • a pair of a public key (N, e) and a secret key (N, d) is generated by an RSA key generator 24 in the server 2.
  • the random number generator 25 randomly generates a random number R 2 (R 2 e ⁇ 0, 1 ⁇ k ).
  • RS A signature text generator 26 as input and received from the terminal apparatus 1 RS A secret key generated from the key generator 24 (N, d) the random number R 2 generated from a random number generator 25 and, ⁇ mj ⁇ generates a signature ⁇ s 1 ⁇ j ⁇ n of 1 ⁇ j ⁇ n , where n is an integer such that n ⁇ 1 og e (PW- (e-1) / e), where , PW stands for password.)
  • the signature ⁇ S j ⁇ 1 ⁇ j ⁇ n is calculated by ⁇ S jm mod d ⁇ , ⁇ j ⁇ n .
  • (m 1 ⁇ j ⁇ n is obtained by dividing the block of length 1 into n blocks from the output of HASH (n II N II e II ID (U) II ID (S) II Rx II R 2 ) It is a thing.
  • ID (U) and ID (S) represent the user and server IDs, respectively.
  • the server 2 transmits the public key (N, e) and the signature (R 2 , ⁇ s 1 ⁇ j ⁇ n) obtained to the terminal device 1.
  • the memory 41 provided inside the server 2 stores and stores the secret key (N, d) generated from the RSA key generator 24.
  • the verification result judging unit 18 in the user terminal 1 receives from the server 2 that the random number generator 17 has generated it ((N, e), (R 2 , ⁇ s, ⁇ 1 ⁇ j ⁇ the n)) as input, the signature sentence (R 2, verifies the ⁇ sj ⁇ 1 ⁇ j ⁇ n).
  • ⁇ mj S jemo dN ⁇ This calculates the ⁇ nij ⁇ 1 ⁇ j ⁇ n by 1 ⁇ j ⁇ n ⁇ nij ⁇ 1 ⁇ j ⁇ n and HASH (n II N II e II ID (U) II ID (S )
  • the stored polynomial and the FDH function P ′ ( ⁇ ′ (x), FDH) are read from the memory 12 provided in the terminal device 1 of the user.
  • p ′ (X) is a first-order polynomial
  • the calculation is performed using p.
  • ⁇ , (1) is the value calculated by inserting “1” in place of X in ⁇ '(X).
  • p (X) p '(x) + Pooh 93mo dN.
  • p '(i) is the value calculated by inserting "i" in place of x in p' (x) for the i-th server.
  • the communication processing unit 5.5 sends Z to the server 2 and receives V 2 from the server 2.
  • the authentication result determination unit 56 calculates the HASH (0 1 II T II ID (U) II ID (S)) using the T output from the random number generator 53 as an input, and calculates the VASH received from the server 2. Compare with 2 .
  • MAC may be used instead of HASH. If the authentication result determination unit 56 V 2 and HASH (01 II T II ID ( U) II ID (S)) do not match gar, authentication result determination section 56, to the error one generator 57, that no match Notify. In response, the error generator 57 generates an error and interrupts the processing.
  • the stored polynomial and FDH function P ′ ( ⁇ ′ (X), FDH) are read from the memory 12 provided in the terminal device 1 of the user.
  • p (x)-'(x) + FDH (Po oh 93 II ID (U) il ID (S)) is calculated by modN.
  • p, (1) is the value calculated by inserting “1” in place of x in p, (x).
  • p '(i) is the value calculated by inserting "i" in place of x in p' (x) for the i-th server.
  • the communication processing unit 55 transmits ⁇ ⁇ to the server 2 and receives V 2 from the server 2.
  • the authentication result determining unit 56 receives the T output from the random number generator 53 as an input, calculates HASH (0 1 II T II ID (U) II ID (S)), and receives the HASH (0) from the server 2. compared with the V 2.
  • MAC may be used instead of HASH. If the authentication in the results determination section 56 V 2 and HASH (0 1 II T II ID (U) II ID (S)) do not match gar, authentication result determination section 56, to the error one generator 57 does not match Notify that. In response, the error generator 57 generates an error and suspends the processing.
  • V 2 and HASH in the authentication result of the determination unit 56 are examples of the authentication result of the determination unit 56.
  • the verifier generating unit 58 calculates a verifier using Vi-HASH (00 II T II ID (U) II ID (S)) and sends it to the server 2.
  • the communication processing unit 55 transmits Z to the server 2 and receives V 2 from the server 2.
  • the authentication result determination unit 56 calculates HASH (01 II T II ID (U) II ID (S)) using T output from the random number generator 53 as an input, and calculates V 2 Compare with Here, MAC may be used instead of HASH. If the authentication result determination unit 56 V 2 and HASH (0 1 II T II ID (U) II ID (S)) do not match gar, authentication result determination section 56, to the error generator 57, that no match Notify. In response, the error generator 57 generates an error and interrupts the processing.
  • Server 2 When using a polynomial and FDH function (Part 1), When using a polynomial and FDH function (Part 2) Server 2 operates as follows regardless of whether the above-mentioned polynomial and FDH function are used (Part 1), or whether the polynomial and FDH function are used (Part 2).
  • the stored authentication data H of the user ID and the password is read from the memory 41 provided in the superuser 2.
  • the communication processing unit 64 transmits the V 2 resulting et the calculated to the terminal apparatus 1, and outputs a V i received from the terminal apparatus 1 to the authentication result of the determination section 65.
  • the authentication result determination unit 65 calculates the HASH (00 II T II ID (U) II ID (S)) by using the T output from the mass key generator 62 as an input, and calculates the terminal device 1 Compare with received from.
  • MAC may be used instead of HASH.
  • a session key SK is generated using I II T II ID (U) II ID (S)).
  • the stored user ID and password authentication data ⁇ ⁇ is read from the memory 41 provided in the server 2.
  • the communication processing unit 64 transmits the V 2 obtained by calculation to the terminal apparatus 1, and outputs the received from the terminal apparatus 1 to the authentication result of the determination section 65.
  • the authentication result determination unit 65 calculates the HASH (00 II T II ID (U) II ID (S)) using the T output from the master key generator 62 as an input and receives it from the terminal device 1. Compare with.
  • MAC may be used instead of HASH.
  • a session key SK is generated using I II T II ID (U) II ID (S)).
  • FIGS. 9 and 19 are block diagrams showing the configuration of the updating process of the terminal device of the user.
  • the updating process here can be applied when using the above-mentioned polynomial and FDH function (Part 1), when using the polynomial and FDH function (Part 2), and when using the master key. is there.
  • this updating process can prevent a rep 1 ay attack on the server.
  • the update value generator 14 generates a server update value H 'for the i-th server.
  • t '(i) is the value calculated by inserting "i" in place of x in the n-th order polynomial t (x).
  • the value H 'for updating the server must be securely notified by the user by directly passing it to the server, by mail, or by telephone.
  • a random number T (TeZ N *) is randomly generated by a random number generator 53.
  • the update value generator 20 When the random number T and the polynomial p ′ (X) are input, the update value generator 20 generates an updated polynomial P ′ for storing the user.
  • Server 2 operates as follows regardless of whether the above-mentioned polynomial and FDH function are used (Part 1) or the case where polynomial and FDH function are used (Part 2).
  • the update value generator 21 outputs the updated password authentication data H for server storage.
  • the memory 41 inside the server stores and stores the updated pass-word authentication data H.
  • the master key generator 62 generates a master key T.
  • the stored user ID and password authentication data H are read from the memory 41 provided in the server 2.
  • Master key T and password authentication data read from memory 41
  • the update value generator 27 When the data H is input, the update value generator 27 generates an updated password authentication data H for storing the server.
  • the memory 41 inside the server stores and stores the updated password authentication data H.
  • FIG. 11 is a block diagram showing the configuration of a user terminal updating process.
  • the update process is performed when the secret value S 'by the secret value generator 15, the user's new password PW', and the P 'stored from the memory 12 provided in the user's terminal device 1 are input.
  • the data updater 16 generates password authentication data H 'for updating the super and updated P' for storing the user, H 'is passed to the server 2, and the updated P' is Save to memory 12.
  • the updating process here can be applied when the above-mentioned FDH function is used.
  • this updating process can prevent a rep1ay attack on the server.
  • this updating process can prevent a rep1ay attack on the server.
  • the same operation as the initialization process can be applied. Therefore, detailed description is omitted here.
  • the secret value generator 15 randomly generates a secret value S '.
  • P ′ (S, FDH) stored in the memory 12 provided in the user terminal device 1 is read.
  • FDH function FDH and secret value S ' the pass-pad authentication data updater 16 updates the updated P' for storing the user and the password for updating the server.
  • ID (U) and ID (S) represent user and server IDs, respectively.
  • the password authentication data update unit 22 transmits the password authentication data H for server storage. Update to H 'sent from user terminal 1.
  • the user's password is safe in terms of information theory even if the person who intends to exploit it has another person's terminal device. Also, even if you gain information stored by breaking into a server, your password is safe in terms of information theory. Also, when using a hash function, a pseudo-random number generator, and an FDH function, the user's password is computationally safe for anyone who intends to exploit it.
  • FIG. 21 is a block diagram illustrating a configuration of the remote distributed storage device 5 when the distributed data is not stored in the terminal.
  • the user processes the data DATA to be distributed and stored by his / her own terminal device 21, and divides the data into data S'1,..., S'n to be stored in n servers.
  • the divided data S ′ i is transmitted to the server ID by the communication device 52 that can use the secure communication path created by the user terminal device 21 using the key SK i shared with the server authentication device together with the DID which is the data ID.
  • Sent to i and saved By the same method, it is possible to divide the saved data list information and save it on the server.
  • the user's terminal device authentication data update mode
  • the user's terminal device is operated at appropriate intervals (at intervals shorter than the interval at which stored information is obtained by offline exhaustive search, for example, every time authentication is performed or once every few days) Then, generate information UP ', UH1,..., UHn for updating P' and H recorded in each server, and update them.
  • both the data stored in the server and the authentication data can be configured to be resistant to leakage and damage.
  • the resistance to leakage and breakage can be expressed by four sets of parameters (n, DS, LSI, LS2).
  • DS, LS I, and LS 2 are all sets of combinations of entities (where leakage and corruption occur).
  • DS represents resistance to data corruption
  • LSI and LS 2 represent resistance to leakage.
  • DS describes a combination of entities that can be broken. Even if the stored data including the local backup is completely unavailable due to a disaster or other reasons, a damaged combination that allows the user to restore his / her own data is described. In the LSI, a combination of entities that may omit recorded information is described.
  • L S2 a combination of entities within a range where some countermeasures can be taken even if recorded information is leaked is described. Even if the stored data is leaked, use a combination of leaks that has countermeasures that make it difficult for an attacker to recover the user's data.
  • LS 1 could not contain server ⁇ S ⁇ and user property ⁇ U ⁇ respectively.
  • an authentication method that is strong against leakage it is possible to include the server ⁇ S ⁇ and the user's property ⁇ U ⁇ in LS 1 respectively.
  • the secret sharing device 512 converts the stored data DATA into (k, n) shared data SI, S 2,..., Sn according to the input parameters n, k.
  • the adjuster 511 generates the input X of the data decompressor 513 from the DID, which is the data ID, and passes it to the data decompressor 513.
  • the data decompressor 513 outputs the corresponding information H and passes it to the encryptor 514.
  • H is long enough for offline exhaustive search.
  • the data decompressor 513 outputs a short H, a different X is passed to the plural data decompressor 513, and the obtained plural Hs are used.
  • the encryptor 514 encrypts n ⁇ k + 1 or more shared data using H as a key. Also, a tampering detection code may be added to each of S l,..., Sn 1 k + 1. .., S ′ n are output from the data divider 51 together with DID, ID 1, ID 2, ID 2,..., IDn.
  • (k, n) distributed data is data in which the original data is divided into n pieces, and the original data can be restored from any of the k pieces, but cannot be restored from less than k pieces. It is data having properties. (K, n) Other than distributed data It is possible to use distributed data with any access structure.
  • the secret sharing device can use not only a secure distribution method using information such as polynomials and matrices but also a computationally secure distribution method that can reduce the size of stored data by using encryption. .
  • ⁇ CS ⁇ means the record information of the client and the server and its partial information
  • ⁇ S n ⁇ means the record information of the n servers and its partial information.
  • ⁇ C, S ⁇ means “all information and its partial information recorded in the client or all information and its partial information recorded in the server”. Leakage from UCS k-1 ⁇ can be dealt with by updating authentication information. If the authentication information is updated while the attacker seeks stored information from ⁇ UC S k-1 ⁇ , the attacker will not be able to seek user data.
  • the loss of the user's property ⁇ U ⁇ (the loss of ⁇ ') can be solved by making a local copy of the data recorded in ⁇ U ⁇ every time the data is updated.
  • all or part of the data and stored information recorded in the user's property, or a part of them, are divided into (k ', n) shared data by a secret sharing device and stored on each server. If this is done, even if the user forgets the stored information, the stored information (and the recorded information of the property) can be restored by offline analysis. At that time, 1) the off-line analysis can be omitted when all are distributed, and 2) the off-line analysis calculation amount can be reduced according to the amount when distributing the — part. This feature allows the user to recover data when authorizing a third party to decrypt the data. The ease of adjustment (similar to the ease of data recovery when an attacker gets ⁇ CS k ' ⁇ ) can be adjusted.
  • FIG. 23 is a block diagram showing a configuration of the remote distributed storage device 5 when data is not stored in the terminal.
  • the data decompressor 54 transmits at least k of the distributed data S ′ 1,..., S ′ n corresponding to the input DID from the server ID 1, ID 2,. receive.
  • the data restorer 54 processes at least k of S'1,..., S'n to restore DATA. In the same way, it is possible to restore the list of saved data.
  • the user's terminal device 21 authentication data update mode
  • the user's terminal device 21 authentication data update mode
  • P ′ and information UP ′, UH1,..., UHn for updating H recorded in each server are generated and updated.
  • the coordinator 541 outputs the input n servers ID, ID1, ID2,..., IDn and DID.
  • the adjuster 541 also generates an input X of the data decompressor 542 from D ID and passes it to the data decompressor 542.
  • the data decompressor 542 outputs the corresponding information H and passes it to the encryptor 543.
  • the encryptor 543 decrypts the encrypted distributed data S'1, S'2,..., S'n and secrets S1, S2,..., Sn. Pass to decentralized reconstructor.
  • the secret sharing restoration unit 544 restores the data from the given sharing data. It should be noted that tampering detection may be performed and only k distributed data that has not been tampered may be passed.
  • FIG. 25 is a block diagram showing the configuration of the remote distributed storage device 5 when the distributed data is also stored in the terminal. Here, only the configuration different from the configuration shown in FIG. 21 will be described.
  • the user processes the data DATA to be distributed and stored in his / her own terminal device 21 and divides the data into data DL to be kept at hand and data RS'1,..., RS'n to be stored in n servers.
  • the DL is stored in the recording device 55 at hand, and the divided data RS'l is created by the user's terminal device 21 using the key SKi shared with the server's authentication device together with the data ID DID. It is sent to the server ID i via a secure communication channel and stored. In the same way, it is possible to divide the saved data list information and save it on the server.
  • the amount of communication with the server can be reduced. It is possible to use a method in which the amount of communication changes according to the combination of damaged servers and a method that does not change, but in the case of a method that changes, the storage area of the entire n servers can be reduced. It should be noted that the resistance to leakage and breakage can be maintained at the same level as when "'--evening is not at hand.
  • the configuration of the data divider 51 shown in FIG. 25 will be described with reference to FIG. Here, only the parts that are different from the configuration shown in Fig.
  • the encryptor 5 15 receives the random number R from the random number generator 5 16
  • the coordinator 5 1 1 passes the input parameters n and k to the secret sharing device 5 12.
  • the secret sharing device 512 sets R (k, n) according to the input parameters n and k.
  • the coordinator 5 1 1 generates the input x of the data decompressor 513 from the DID, which is the data ID, and decompresses the data.
  • the data decompressor 5 13 outputs the corresponding information H, and passes this as a key to the encryptor 514.
  • H is an offline Different if the data decompressor 513 outputs a short H: X is passed to multiple data decompressors 513, and the obtained multiple Hs are used. Use.
  • the encryptor 514 encrypts n ⁇ k + 1 or more shared data using H as a key.
  • each of RS1,..., And RSn-k + 1 may have a tampering detection code.
  • the output of the encryptor is RS 'l, ..., RS' n.
  • the secret sharing device 512 can use a sharing method that is secure in terms of the amount of information using polynomials or matrices, or a sharing method that is secure in terms of the amount of computation using cryptography. Since the size reduction effect of using a computationally secure distribution method is small, it is better to use an information amount secure distribution method.
  • FIG. 27 is a block diagram showing the configuration of the remote distributed storage device 5 when the distributed data is stored in the terminal. Here, only portions different from the configuration shown in FIG. 23 will be described.
  • the data decompressor 54 transmits at least k of the distributed data RS'1,..., RS'n corresponding to the input DID to the server ID1, ID2,. Receive from I Dn.
  • the data decompressor 54 processes at least k of RS'1,..., RS'n to decompress DATA. In the same way, it is possible to restore the list of saved data.
  • FIG. 27 the configuration of the data decompressor 54 shown in FIG. 27 will be described with reference to FIG. Here, only portions different from the configuration shown in FIG. 24 will be described.
  • the coordinator 541 generates an input X of the data decompressor 542 from the DID and passes it to the data decompressor 542.
  • Data decompressor 542 outputs the corresponding information H and passes it to decoder 543.
  • the decoder 543 decodes the encrypted data among the obtained shared data RS'1, RS'2,..., RS'n, and converts RS1,.
  • Pass to The secret sharing recovery unit 544 decrypts the DATA from the passed shared data. Restore by. Alteration detection may be performed, and k distributed data items that have not been altered may be passed.
  • a program for realizing the functions of the respective processing units shown in the drawings is recorded on a recording medium readable by a computer, and the program recorded on the recording medium is read into a computer system and executed to execute an authentication process. A key exchange process may be performed.
  • the “computer system” includes an OS and hardware such as peripheral devices.
  • “computer system J.” also includes a WWW system provided with a homepage providing environment (or display environment), and “computer-readable recording medium” includes a flexible disk, a magneto-optical disk, a ROM, This refers to portable media such as CD-ROM, and storage devices such as hard disks built into computer systems.
  • a “computer-readable recording medium” is a volatile memory (RAM) in a computer system that functions as a server or a client when a program is transmitted through a network such as the Internet or a communication line such as a telephone line.
  • RAM volatile memory
  • the above program may be transmitted from a computer system storing the program in a storage device or the like to another computer system via a transmission medium or by a transmission wave in the transmission medium.
  • the “transmission medium” for transmitting a program refers to a medium having a function of transmitting information, such as a network (communication network) such as the Internet or a communication line (communication line) such as a telephone line.
  • the above program may be for realizing a part of the functions described above.
  • a so-called difference file may be used.
  • the present invention even if the information stored in the device is leaked from the terminal device side or the server side, the password cannot be found by the offline analysis, thereby preventing unauthorized use of the server. The effect is obtained. Further, since there is no need to use a tamper-resistant module for preventing information stored in the device from being stolen, the device configuration can be simplified. Also, since there is no need to perform complicated key management processing as in a public key cryptosystem, the calculation processing can be improved and the processing content can be simplified. It can also be extended to a plurality of supers. Furthermore, by dynamically changing the user ID between each server and the terminal device while synchronizing the same, it is possible to prevent an eavesdropper from using the user ID to associate the user's privacy information.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Algebra (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Storage Device Security (AREA)

Description

認証システム及び遠隔分散保存システム 技術分野
本発明は、 認証に関する情報の漏洩に強い認証システムとこの認証システム を用いて安全にデータを保存することができる遠隔分散保存システムに関す 明
る。 .
本願は、 2003年 10月 28日に出願された特願 2003- 367527 書 .
号に対し優先権を主張し、 その内容をここに援用する。 背景技術
従来からユーザの端末装置とサーバとの間において認証を行う方法として、 ユーザ I Dとュ一ザのみが知っているパスワードとを端末装置から入力し、 サ —バ側に蓄えられている情報と一致すれば、 正当なユーザであることを認証す る方法が知られている。
しかし、 この方法は、 端末装置とサーバ間の通信経路中において、 不正にこ れらの情報が盗まれてしまうと、 簡単に不正利用を許してしまうため、 S SL (文献 1) 、 TLS (文献 2) 、 S SH (文献 3) 等の暗号化技術を用いて、 情報の送受信を行うのが一般的である。 これは、 パスワードと秘密の値と公開 されている値とを使用して認証を行うものである。
(文献 1) A. Frier，： P.Karl ton, and P. Kocher. The SSL 3.0 Protocol. Netsca pe Communications Corp. , 1996, http://wp. netscape. com/eng/ssl3/
(文献 2 ) IETF (Internet Engineering Tas.k Force) . Transport Layer secu rity (t Is) Charter. http://ww . ietf. org/html, char ters/t Is - charter, html
(文献 3) IETF (Internet Engineering Task Force) . Secure Shell (secsh)C harter. http:// ww. ietf. org/html, char ters/secsh - charter. html しかしながら、 非特許文献 1〜 3に示す方法は、 ユーザの端末装置側からパ スヮードで暗号化された情報あるいはサーバ側からパスヮ一ド認証デ一夕が 漏れた場合は、 オフラインの解析作業によってパスワードを求めることができ てしまうという問題がある。サーバに対してオンラインでパスヮード入力を繰 り返し行う方法は、 パスワードを間違えた回数に応じてアクセスを拒否するな どの対策を講じることが可能であるが、 オフラインの解析作業は、 防止策を講 じることができないという問題もある。 また、 パスワードが漏洩してしまった 場合、 このパスワードでログインできるシステム内に保存されているデ一夕も 漏洩してしまうという問題もある。 発明の開示
本発明の目的は、 情報の漏洩に強く、 安全に暗号鍵の交換を行うことができ る認証システムを提供することである。
本発明の目的は、 本発明による認証システムを用いて安全にデータを保存す ることができる遠隔分散保存システムを提供することであ ¾。 本発明の要旨は、 端末装置とサーバ間において相互に認証を行う認証システ ムであって、 前記端末装置は、.ユーザが予め決定しておいたパスワードに基づ いて、 サーバ登録用のパスワード認証データ Hとユーザ保存用の認証情報 P ' を求めるデータ伸長手段と、 前記データ伸長手段によって求めた認証情報 P ' を予め記憶しておく記憶手段と、 前記記憶手段から読み出した認証情報 P ' と 認証時に入力されたパスヮードを入力として所定の計算式により値 Pを求め る結合手段と、 前記値 Pと内部において発生させた乱数を入力として所定の計 算式により値 Y 1を求め、 前記サーバへ送信するマスク演算手段と、 前記値 P と内部において発生させた乱数と前記サーバから受信した値 Y 2を入力とし て所定の計算式により値 MKを求めるマスター鍵生成手段と、 前記値 MKを入 力として所定の計算式により値 V 1を求め、 サーバへ送信するとともに、 前記 サーバから受信した値 V 2と前記値 MKを入力として所定の計算式による値 V 2と比較照合し、 一致した場合にサーバを認証する認証結果判断手段とを備 え、 前記サーバは、 前記データ伸長手段によって求めたパスワード認証データ Hを予め記憶しておく記憶手段と、 前記記憶手段から読み出したパスワード認 証デ一夕 Hと内部において発生させた乱数を入力として所定の計算式により 値 Y 2を求め、 前記端末装置へ送信するマスク演算手段と、 前記パスワード認 証データ Hと内部において発生させた乱数と前記端末装置から受信した値 Y 1を入力として所定の計算式により値 MKを求めるマスター鍵生成手段と、 前 記値 MKを入力として所定の計算式により値 V 2を求め、.端末装置へ送信する とともに、 前記端末装置から受信した値 V 1と前記値 MKを入力として所定の 計算式による値 V Iと比較照合し、 一致した場合に端末装置を認証する認証結 果判断手段とを備える。 " 本発明の要旨は、 端末装置とサ一パ間において相互に認証を行う認証システ ムにおける端末装置上で動作する認証プログラムであって、 ユーザが予め決定 しておいたパスヮードに基づいて、サ一パ登録用のパスヮ一ド認証データ Hと ユーザ保存用の認証情報 P ' を求めるデータ伸長処理と、 前記データ伸長処理 によって求めた認証情報 P ' を予め記憶しておく記憶処理と、 前記記憶処理に より記憶しておいた認証情報 P ' と認証時に入力されたパスワードを入力とし て所定の計算式により値 Pを求める結合処理と、 前記値 Pと内部において発生 させた乱数を入力として所定の計算式により値 Y 1を求め、 前記サーバへ送信 するマスク演算処理と、 前記値 Pと内部において発生させた乱数と前記サーバ から受信した値 Y 2を入力として所定の計算式により値 MKを求めるマスタ 一鍵生成処理と、 前記値 MKを入力として所定の計算式により値 V 1を求め、 サーバへ送信するとともに、 前記サーバから受信した値 V 2と前記値 MKを入 力として所定の計算式による値 V 2と比較照合し、 一致した場合にサーバを認 証する認証結果判断処理とをコンピュータに行わせる。 本発明の要旨は、 端末装置とサーバ間において相互に認証を行う認証システ ムにおけるサーバ上で動作する認証プログラムであって、 パスワード認証デ一 夕 Hを予め記憶しておく記憶処理と、 前記記憶処理により記憶しておいたパス ヮード認証データ Hと内部において発生させた乱数を入力として所定の計算 式により値 Y 2を求め、 前記端末装置へ送信するマスク演算処理と、 前記パス ワード認証データ Hと内部において発生させた乱数と前記端末装置から受信 した値 Y 1を入力として所定の計算式により値 MKを求めるマスタ一鍵生成 処理と、 前記値 MKを入力として所定の計算式により値 V2を求め、 端末装置 へ送信するとともに、 前記端末装置から受信した値 V 1と前記値 MKを入力と して所定の計算式による値 VIと比較照合し、 一致した場合に端末装置を認証 する認証結果判断処理とをコンピュータに行わせる。 本発明の要旨は、 端末装置とサーバ間において相互に認証を行う認証システ ムであって、 前記端末装置は、 ユーザが予め決定しておいたパスワードに基づ いて、 サーバ登録用のパスワード認証データ Hとユーザ保存用の認証情報 P' を求めるデータ伸長手段と、 前記データ伸長手段によって求めた認証情報 P' と RS A鍵生成手段によって求めた RS A公開鍵 （N， e) を予め記憶してお く記憶手段と、 前記記憶手段から読み出した認証情報 P' と認証時に入力され たパスワードを入力として所定の計算式により値 Wを求める結合手段と、 前記 値 Wと前記記憶手段から読み出した RSA公開鍵 （N， e) と内部において発 生させた乱数 Tを入力として所定の計算式により値 Zを求め、 前記サーバへ送 信するマスク演算手段と、 前記サーバから受信した値 V 2と前記乱数 Tを入力 として所定の計算式による値 V 2と比較照合し、 一致した場合にサーバを認証 する認証結果判断手段と、 前記乱数 Tを入力として所定の計算式により値 VI を求め、 .前記サーバへ送信する検証子生成手段とを備え、 前記サーバは、 RS A公開鍵 （N， e) と RSA秘密鍵 （N， d) を求める R S A鍵生成手段と、 前記 RS A鍵生成手段によって求めた RSA秘密鍵 （N, d) と前記データ伸 長手段によって求めたパスヮード認証データ Hを予め記憶しておく記憶手段 と、 前記記憶手段から読み出した RSA秘密鍵 （N， d) とパスワード認証デ —夕 Hと前記端末装置から受信した値 Zを入力として所定の計算式により値 Tを求めるマスタ一鍵生成手段と、 前記値 Tを入力として所定の計算式により 値 V 2を求め、 前記端末装置へ送信する検証子生成手段と、 前記端末装置から 受信した値 V 1と前記値 Tを入力として所定の計算式による値 V 1と比較照 合し、 一致した場合に端末装置を認証する認証結果判断手段とを備える。 本発明の要旨は、 端末装置とサーバ間において相互に認証を行う認証システ ムにおける端末装置上で動作する認証プログラムであって、 ユーザが予め決定 しておいたパスワードに基づいて、 サーバ登録用のパスワード認証デ一夕 Ηと ユーザ保存用の認証情報 P' を求めるデータ伸長処理と、 ίί記データ伸長処理 によって求めた認証情報 P' と RS Α鍵生成処理によって求めた RS Α公開鍵 (N.， e) を予め記憶しておく記憶処理と、 前記記憶処理により記憶しておい た認証情報 P' と認証時に入力されたパスワードを入力として所定の計算式に より値 Wを求める結合処理と、 前記値 Wと前記記憶処理により記憶しておいた RSA公開鍵 （N, e) と内部において発生させた乱数 Tを入力として所定の 計算式により値 Zを求め、 前記サーバへ送信するマスク演算処理と、 前記サー バから受信した値 V 2と前記乱数 Tを入力として所定の計算式による値 V 2 と比較照合し、 一致した場合にサーバを認証する認証結果判断処理と、 前記乱 数 Tを入力として所定の計算式により値 V 1を求め、 前記サーバへ送信する検 証子生成処理とをコンピュータに行わせる。 本発明の要旨は、 端末装置とサーバ間において相互に認証を行う認証システ ムにおけるサーバ上で動作する認証プログラムであって、 RSA公開鍵 （N， e) と RSA秘密鍵 （N， d) を求める R S A鍵生成処理と、 前記 RSA鍵生 成処理によって求めた RS A秘密鍵 （N， d) とパスワード認証データ Hを予 め記憶しておく記憶処理と、 前記記憶処理により記憶しておいた RS A秘密鍵 (N, d) とパスワード認証データ Hと前記端末装置から受信した値 Zを入力 として所定の計算式により値 Tを求めるマスター鍵生成処理と、 前記値 Tを入 力として所定の計算式により値 V 2を求め、 前記端末装置へ送信する検証子生 成処理と、 前記端末装置から受信した値 VIと前記値 Tを入力として所定の計 算式による値 VIと比較照合し、 一致した場合に端末装置を認証する認証結果 判断処理とをコンピュータに行わせる。 本発明の要旨は、 端末装置と複数のサーバ間において相互に認証を行い、 前 記端末装置内の保存対象のデータを前記サーバ内に分散して保存する遠隔分 散保存システムであって、 前記端末装置は、 ユーザが予め決定しておいたパス ワードに基づいて、 サーバ登録用のパスヮ一ド認証データ Hとュ一ザ保存用の 認証情報 P ' を求めるデータ伸長手段と、 前記データ伸長手段によって求めた 認証情報 P ' を予め記憶しておく記憶手段と、 前記記憶手段から読み出した認 証情報 P ' と認証時に入力されたパスワードを入力として所定の計算式により 値 P.を求める結合手段と、 前記値 Pと内部において発生させた乱数を入力とし て所定の計算式により値 Y 1を求め、 前記サーバへ送信するマスク演算手段と、 前記値 Pと内部において発生させた乱数と前記サーバから受信した値 Y 2を 入力として所定の計算式により値 MKを求めるマスター鍵生成手段と、 前記値 MKを入力として所定の計算式により値 V 1を求め、 サーバへ送信するととも に、 前記サーバから受信した値 V 2と値 V Iと比較照合し、 一致した場合にサ ーバを認証する認証結果判断手段と、 サーバの認証が行われた場合に、 セッシ ョン鍵 S Kをサーバの数だけ生成するセッション鍵生成手段と、 前記保存対象 のデータを分割して、 認証したサーバの数と同数の分割データを得るデ一夕分 割手段と、 前記分割データのそれぞれと保存対象のデータを識別する識別情報 とを、 保存先のサーバと共有した前記セッシヨン鍵 S Kを用いて暗号化して、 各サーバに対して送信するデータ保存手段と、 分割データが保存された各サ一 バから分割データを受信し、 前記保存対象のデータを復元するデータ復元手段 とを備え、 前記サーバは、 前記データ伸長手段によって求めたパスワード認証 データ Hを予め記憶しておく記憶手段と、 前記記憶手段から読み出したパスヮ ード認証データ Hと内部において発生させた乱数を入力として所定の計算式 により値 Y 2を求め、 前記端末装置へ送信するマスク演算手段と、 前記パスヮ ード認証データ Hと内部において発生させた乱数と前記端末装置から受信し た値 Y 1を入力として所定の計算式により値 M Kを求めるマスター鍵生成手 段と、.前記値 MKを入力として所定の計算式により値 V 2を求め、 端末装置へ 送信するとともに、 前記端末装置から受信した値 V 1と値 V 2と比較照合し、 一致した場合に端末装置を認証する認証結果判断手段と、 端末装置の認証が行 われた場合に、 セッション鍵を生成するセッション鍵生成手段と、 端末装置か ら受信した分割データを受信するデータ受信手段と、 前記分割データを記憶す るデ一夕記憶手段と、 前記データ記憶手段に保存されている分割データを読み 出して端末装置へ送信するデータ送信手段とを備えたことを特徴とする遠隔 分散保存システム。 本発明の要旨は、 端末装置と複数のサーバ間において相互に認証を行い、 前 記端末装置内の保存対象のデータを前記サーバ内に分散して保存する遠隔分 散保存システムにおける端末装置上で動作する遠隔分 ¾保存プログラムであ つて、 ユーザが予め決定しておいたパスワードに基づいて、 サーバ登録用のパ スワード認証データ Hとユーザ保存用の認証情報 P ' を求めるデータ伸長処理 と、 前記データ伸長処理によって求めた認証情報 P ' を予め記憶しておく記憶 処理と、 前記記憶処理から読み出した認証情報 P ' と認証時に入力されたパス ワードを入力として所定の計算式により値 Pを求める結合処理と、 前記値 Pと 内部において発生させた乱数を入力として所定の計算式により値 Y 1を求め、 前記サーバへ送信するマスク演算処理と、 前記値 Pと内部において発生させた 乱数と前記サーバから受信した値 Y 2を入力として所定の計算式により値 M Kを求めるマスター鍵生成処理と、 前記値 MKを入力として所定の計算式によ り値 V Iを求め、 サーバへ送信するとともに、 前記サーバから受信した値 V 2 と値 V 1と比較照合し、 一致した場合にサ一パを認証する認証結果判断処理と、 サーバの認証が行われた場合に、 セッション鍵 S Kをサーバの数だけ生成する セッション鍵生成処理と、 前記保存対象のデータを分割して、 認証したサーバ の数と同数の分割データを得るデータ分割処理と、 前記分割データのそれぞれ と保存対象のデータを識別する識別情報とを、保存先のサーバと共有した前記 セッション鍵 S Kを用いて暗号化して、 各サーバに対して送信するデータ保存 処理と、 分割データが保存された各サーバから分割データを受信し、 前記保存 対象のデータを復元するデータ復元処理とをコンピュータに行わせることを 特徴とする遠隔分散保存プログラム 本発明の要旨は、 端末装置と複数のサーバ間において相互に認証を行い、 前 記端末装置内の保存対象のデータを前記サーバ内に分散して保存する遠隔分 散保存システムにおけるサーバ上で動作する遠隔分散保存プログラムであつ て、 データ伸長処理によって求めたパスワード認証データ Hを予め記憶してお く記憶処理と、 前記記憶処理から読み出したパスワード認証データ Hと内部に おいて発生させた乱数を入力として所定の計算式により値 Y 2を求め、 前記端 末装置へ送信するマスク演算処理と、 前記パスワード認証データ Hと内部にお いて発生させた乱数と前記端末装置から受信した値 Y 1を入力として所定の 計算式により値 MKを求めるマスタ一鍵生成処理と、 前記値 MKを入力として 所定の計算式により値 V 2を求め、 端末装置へ送信するとともに、 前記端末装 置から受信した値 V 1と値 V 2と比較照合し、 一致した場合に端末装置を認証 する認証結果判断処理と、 端末装置の認証が行われた場合に、 セッション鍵を 生成するセッション鍵生成処理と、 端末装置から受信した分割デー夕を受信す るデータ受信処理と、 前記分割データを記憶するデータ記憶処理と、 前記デー タ記憶処理に保存されている分割データを読み出して端末装置へ送信するデ 一夕送信処理とをコンピュータに行わせることを特徴とする遠隔分散保存プ ログラム。 · 図面の簡単な説明
図 1は、 本発明の一実施形態における端末装置の構成を示すプロック図であ る。 .
図 2は、 図 1に示すデータ伸長器 1 1の構成を示すブロック図である。 図 3は、 図 1に示すデータ伸長器 1 1の構成を示すブロック図である。 図 4は、 図 1に示すデータ伸長器 1 1の構成を示すブロック図である。 図 5は、 相互認証及び鍵交換を行う装置の構成を示すブロック図である。 図 6は、 図 5に示す端末装置 1の構成を示すプロック図である。
図 7は、 図 5に示すサーバ 2の構成を示すブロック図である。
図 8は、 図 1に示すデータ伸長器 1 1の構成を示すブロック図である。 図 9は、 パスワード認証データ更新一 1の端末装置 1の構成を示すプロック 図である。
図 1 0は、 パスワード認証データ更新— 1のサーバ 2の構成を示すブロック 図である。
図 1 1は、 パスワード認証データ更新一 2の端末装置 1の構成を示すブロッ ク図である。
図 1 2は、 パスワード認証データ更新— 2のサーバ 2の構成を示すブロック 図である。
図 1 3は、 図 1に示すデータ伸長器 1 1の構成を示すブロック図である。 図 1 4は、 図 1に示すデータ伸長器 1 1の構成を示すブロック図である。 図 1 5は、 安全な通信を利用して初期化処理を行う場合のサーバ 2の構成を 示すブロック図である。
図 1 6は、 安全ではない通信を利用して初期化処理を行う場合の端末装置 1 及びサーバ 2の構成を示すブロック図である。
図 1 7は、 図 5に示す端末装置 1の構成を示すブロック図である。
図 1 8は、 図 5に示すサーバ 2の構成を示すブロック図である。
図 1 9は、 マスター鍵を利用して更新化処理を行う場合の端末装置 1の構成 を示すブロック図である。
図 2 0は、 マスター鍵を利用して更新化処理を行う場合のサーバ 2の構成を 示すブロック図である。
図 2 1は、 端末に分散データを保存しない場合の遠隔分散保存装置 5の構成 を示すブロック図である。
図 2 2は、 図 2 1に示すデータ分散器 5 1の構成を示すブロック図である。 図 2 3は、 端末にデータを保存しない場合の遠隔分散保存装置 5の構成を示 すブロック図である。
図 2 4は、 図 2 3に示すデータ復元器 5 4の構成を示すプロック図である。 図 2 5は、 端末にも分散データを保存する場合の遠隔分散保存装置 5の構成 を示すブロック図である。
図 2 6は、 図 2 5に示すデータ分割器 5 1の構成を示すプロック図である。 図 27は、 端末にも分散データを保存する場合の遠隔分散保存装置 5の構成 を示すブロック図である。
図 2 8は、 図 27に示すデータ復元器 54の構成を示すブロック図である。 発明を実施するための最良の形態.
<第 1実施例 >
以下、図面を参照しつつ、本発明の好適な実施例について説明する。ただし、 本発明は以下の各実施例に限定されるものではなく、 例えばこれら実施例の構 成要素同士を適宜組み合わせてもよい。
この認証システムは、 ユーザの端末装置とサーバの認証装置がお互いに相互 認証しながら同じセッション鍵を確保するためのシステムである。
ここで、 以下の説明において用いる記号について説明しておく。
P， qは素数であり、 d I p—lという関係がある。 Q I p— 1は、 Qは p — 1を割りきることのできる値であることを意味する。 また、 g, hは mod P上の位数 Qの有限体（群） G= {g j mod p： 0≤ j < q } の生成元であ る （楕円曲線上の群でも同じように構成できる） 。 ここで、 "gj mod p" は、 法指数演算で、 gを j乗した値を pで割った残り （Rema i nde r) という意味である。 ここで、 gは（l<gく p— 1, gq= lmo d p, gj≠ lmo d p (0く j <q) )であり、 hは h = g amo d pである。つまり、 p, Qは演算体系 （素体の標数） を示す。 例えば、 H=hxmo d p (0<X<QL) で xは秘密情報である （つまり、 Hが与えられた時、 x= l oghHを求める のは数学的に難しい問題； Hの生成元 hに対する離散対数問題） 。 また、 乱数 発生器から発生される乱数は RG (Z/q Z) *を無作為に生成する。 ここで、 (Z/qZ) *は { 1, 2， · · ·， Q} の集合を示す。 また、 Nはパスヮー ドの長さを示す。 また、 IIは値を連結 （c onc a t ena t i on) すると いう意味である。
<端末装置の初期化 >
ユーザは、 サーバに対して個人登録したい時、 自分の端末装置の初期化を行 う。 図 1は、 ユーザの端末装置の初期化処理の構成を示すブロック図である。 初期化は、 ユーザがパスワードを入力すると、 データ伸張器 1 1によって、 サ ーパ登録用のパスワード認証データ Hと、 ユーザ保存用の値 P， が生成され、 パスワード認証データ Hは、 サーバに受け渡され、 値 P， は、 メモリ 12へ保 存する。 ここで、 データ伸長器 1 1は、 多項式、 多項式とハッシュ関数、 ハツ シュ関数、 擬似乱数発生器などで構成することが可能である。
(1) 多項式を利用する場合 （その 1)
初めに、 図 2を参照して、 多項式を利用する場合 （その 1) について説明す る。 "
まず、 多項式発生器 1 1 1によりランダムに多項式を発生する。 このとき、 登録するサーバの数が一つだったら Xを変数とする 1次多項式 （ρ' (χ) = ！ - xmo d q) を、 サーバの数が n個だったら n次多項式 （ρ' (χ) = α！ · χ + α 2 · χ2+ · · - + η - xnmo d q) を発生する。 ここで、 αは (ZZQ Z) *から無作為に選ばれる。例えば、一つのサーバの場合、 p' (X) は、 ρ， （X) = ！ · xmo d Qとなる。 ここで、 ユーザは自分が覚えてい るパスワード （例えば、 " P o o h 9 3" ) を入力する。 多項式とユーザのパ スワードが入力されたらパスワード認証データ生成器 1 1 2は、 パスワード認 証データ Hを生成する。パスワード認証データ Hは、 例えば H=hp' (1) +Pooh 93 mo d pにより計算できる。 ここで、 p' (1) は ' （X) で Xの代わ りにサーバの I D (例えば、 「1」.） を入れて計算した値である。 パスワード 認証データ Hはユーザが直接にサーバに渡したり、 郵便で送付したり、 あるい は電話で知らせるなどして、 安全に通知する必要がある.。 ユーザの端末装置の 内部にあるメモリ 1 2は多項式発生器から発生された多項式 Ρ' =ρ' (χ) を記憶して保存する。
(2) 多項式を利用する場合 （その 2)
次に、図 2を参照して、多項式を利用する場合（その 2)について説明する。 まず、 多項式発生器 1 1 1によりランダムに多項式を発生する。 このとき、 登録するサーバの数が一つだったら χを変数とする 1次多項式 （p， （X) = l - xmo d q) を、 サーバの数が n個だったら n次多項式 （p， (x) = CE I · χ + α2 · x2+ - · - + αη · xnmo d q) を発生する。 ここで、 αは (Z/q Ζ) *から無作為に選ばれる。例えば、一つのサーバの場合、 p' (X) は、 ρ， （X) = · xmo d qとなる。 ここで、 ュ一ザは自分が覚えてい るパスワード （例えば、 " P o o h 93" ) を入力する。 多項式とユーザのパ スワードが入力されたらパスワード認証データ生成器 1 1 2は、 パスワード認 証データ Hを生成する。 パスワード認証データ Hは、 例えば H=p (1) =p， (1) + P o o h 93mo d Qにより計算できる。 ここで、 p， (1) は p， (x) で xの代わりにサーバの I D (例えば、 「1」 ） を入れて計算した値で ある。 パスワード認証デ一夕 Hはユーザが直接にサーバに渡したり、 郵便で送 付したり、 あるいは電話で知らせるなどして、 安全に通知する必要がある。 ュ 一ザの端末装置の内部にあるメモリ.1 2は多項式発生器から発生された多項 式 Ρ' = ρ ' (X) を記憶して保存する。
(3) 多項式とハッシュ関数を利用する場合 （その 1)
次に、 図 8を参照して、 多項式とハッシュ関数を利用する場合 （その 1) に ついて説明する。
まず、 多項式発生器 1 1 9によりランダムに多項式を発生する。 このとき、 登録するサーバの数が一つだったら Xを変数とする 1次多項式 （ρ ' (X) = 1 - xmo dN) を、 サーバの数が n個だったら n次多項式 （ρ' (χ) = a！ · χ τΙ- α 2 · χ2+ · · · + Q!N · xnmo dN) を発生する。 ここで、 αは (Z/Q Ζ) *から無作為に選ばれる。例えば、一つのサーバの場合、 p' (X) は、 p ' (X) = 0^ · xmo dNとなる。 そして、 ハッシュ関数発生器 1 2 0によりランダムにハッシュ関数 HASHを発生する。 HASHは一方向ハツ シュ関数である。 ここで、 ユーザは自分が覚えているパスワード （例えば、 " P o o h 93" ) を入力する。 多項式とハッシュ関数とユーザのパスワードが 入力されたらパスワード認証データ生成器 1 2 1は、 パスワード認証データ H を生成する。パスワード認証データ Hは、 例えば H = hp (1)mo d pにより計 算できる。 ここで！） (1) は、 p (1) =p， (1) +HASH (P o oh 9 3 II I D (U) II I D (S) ) mo dNにより計算する。 ここで、 I D (U) と I D (S) はそれぞれユーザとサーバの I Dを表す。 ここで、 p， （1) は p ' (X) で Xの代わりに 「1」 入れて計算した値である。
例えば、 登録するサーバの数が nの場合、 パスワード認証データ生成器 1 2 1は、 i番目のサーバに対してパスワード認証データ Hを生成する。 パスヮ ード認証デ一夕 Hは、 例えば H = hp (i)mo d pにより計算できる。 ここで p ( i ) は、 p ( i ) =p ' ( i ) +HASH (P o o h 9 3 II I D (U) II I D (S) ) mo dNにより計算する。 ここで、 I D (U) と I D (S) はそれ ぞれユーザと i番目のサーバの I Dを表す。 ここで、 ( i) は n次多項式 p' (X) で Xの代わりに 「 i」 を入れて計算した値である。
パスワード認証データ Hはユーザが直接にサーバに渡したり、 郵便で送付 したり、 あるいは電話で知らせるなどして、 安全に通知する必要がある。 ユー ザの端末装置の内部にあるメモリ 1 2は多項式発生器から発生された多項式 P ' (X) とハッシュ関数発生器から発生されたハッシュ関数 HASHとを一 緒に P' = (ρ' (x) , HASH) として記憶して保存する。
(4) 多項式とハッシュ関数を利用する場合 （その 2)
次に、 図 8を参照して、 多項式とハッシュ関数を利用する場合 （その 2) に ついて説明する。
まず、 多項式発生器 1 1 9によりランダムに多項式を発生する。 このとき、 登録する.サーバの数が一つだったら Xを変数とする 1次多項式 （ρ ' (χ) = 1 - xmo dN) を、 サーバの数が n個だったら n次多項式 （ρ' (χ) = 0；! · χ + α2 · χ2+ - · · -I- αη · xnmo dN) を発生する。 ここで、 は (Z/Q Z) *から無作為に選ばれる。例えば、.一つのサ一パの場合、 p' (X) は、 p ' (X) =ひ i · xmo dNとなる。 そして、 ハッシュ関数発生器 1 2 0によりランダムにハッシュ関数 HASHを発生する。 HASHは一方向ハツ シュ関数である。 ここで、 ユーザは自分が覚えているパスワード （例えば、 " P o o h 93 " ) を入力する。 多項式とハッシュ関数とユーザのパスワードが 入力されたらパスワード認証データ生成器 12 1は、 パスワード認証データ H を生成する。 パスワード認証データ Hは、 例えば H=P (1) =ρ' (1) + HASH (P o o h 93 II I D (U) II I D (S) ) mo dNにより計算でき る。 ここで、 I D (U) と I D (S) はそれぞれユーザとサーバの I Dを表す。 ここで、 p ' (1) は p ' (X) で Xの代わりに 「1」 入れて計算した値であ る。
例えば、 登録するサーバの数が nの場合、 パスワード認証データ生成器 12 1は、 i番目のサーバに対してパスワード認証データ Hを生成する。 パスヮー ド認証データ Hは、 例えば H=p ( i) =ρ' ( i ) +HASH (P o oh 9 3 II I D (U) II I D (S) ) m o d Nにより計算でき ¾。 ここで、 I D (U) と I D (S) はそれぞれュ一ザと i番目のサーバの I Dを表す。 ここで、 p' ( i) は n次多項式 p' (x) で Xの代わりに 「 i」 を入れて計算した値であ る。
パスワード認証データ Hはユーザが直接にサーバに渡したり、 郵便で送付し たり、 あるいは電話で知らせるなどして、 安全に通知する必要がある。 ユーザ の端末装置の内部にあるメモリ 12は多項式発生器から発生された多項式 p' (x) とハッシュ関数発生器から発生されたハッシュ関数 HASHとを一緒に P' = (ρ-' (x) , HASH) として記憶して保存する。
(5) ハッシュ関数を利用する場合 （その 1)
次に、 図 3を参照して、 八ッシュ関数を利用する場合 （その 1) について説 明する。.
まず、 ハッシュ関数発生器 1 13によりランダムにハッシュ関数 HASHを 発生する。 そして、 秘密値発生器 1 14もランダムに秘密値 Sを発生する。 こ こで、 ユーザは自分が覚えているパスワード.（例えば、 " P o oh 93" ) を 入力する。 ハッシュ関数 HASHと秘密値 Sとユーザのパスワードが入力され たらパスワード認証データ生成器 1 1 5はパスワード認証データ Hを生成す る。 パスワード認証デ一タ Hは、 例えば、 H=hHASH (sllp°°h93II ID (u) II ID <S) ) mo d pにより計算できる。 ここで、 I D (U) と I D (S) はそれぞれユー ザとサーバの I Dを表す。 パスヮード認証データ Hはユーザが直接にサーバに 渡したり、 郵便で送付したり、 あるいは電話で知らせるなどして、 安全に通知 する必要がある。 ユーザの端末装置の内部にあるメモリ 12はハッシュ関数発 生器 1 1 3と秘密値発生器 1 14から発生されたハッシュ関数 HASHと秘 密値 Sとを一緒に P' = (S, HASH) として記憶して保存する。
(6) ハッシュ関数を利用する場合 （その 2)
次に、 図 3を参照して、 ハッシュ関数を利用する場合 （その 2) について説 明する。
まず、 ハッシュ関数発生器 1 13によりランダムにハッシュ関数 HASHを 発生する。 そして、 秘密値発生器 1 14もランダムに秘密値 Sを発生する。 こ こで、 ユーザは自分が覚えているパスワード （例えば、 " P o oh 93" ) を 入力する。 ハッシュ関数 H A S Hと秘密値 Sとユーザのパスワードが入力され たらパスワード認証データ生成器 1 1 5はパスワード認証データ Hを生成す る。 パスワード認証データ Hは、 例えば、 H = HASH (S II P o o h 93 II I D (U) II I D (S) ) mo d qにより計算できる。 ここで、 I D (U) と I D (S) はそれぞれユーザとサーバの I Dを表す。 パスワード認証データ H はユーザが直接にサーバに渡したり、 郵便で送付したり、 あるいは電話で知ら せるなどして、 安全に通知する必要がある。 ユーザの端末装置の内部にあるメ モリ 1 2はハッシュ関数発生器 1 1 3と秘密値発生器 1 14から発生された ハッシュ関数 HASHと秘密値 Sとを一緒に P' = (S, HASH) として記 憶して保存する。
(7) 擬似乱数発生器を利用する場合 （その 1)
次に、 図 4を参照して、 擬似乱数発生器を利用する場合 （その 1) について 説明する。
まず、 擬似乱数発生器 1 16によりランダムに擬似乱数関数 PR NGを発生 する。そして、秘密値発生器 1 17もランダムに秘密値 Sを発生する。ここで、 ユーザは自分が覚えているパスワード （例えば、 " P o oh 93" ) を入力す る。擬似乱数関数 PRNGと秘密値 Sとユーザのパスワードが入力されたのを 受けて、 パスワード認証データ生成器 118はパスワード認証データ Hを生成 する。パスヮ一ド認証デ一夕 Hは、例えば、 H=hPRNG(sllp。°h93llID(u) IIID (S>) mo d pにより計算できる。 ここで、 ID (U) と ID (S) はそれぞれュ一 ザとサーバの I Dを表す。パスワード認証データ Hはユーザが直接にサーバに 渡したり、 郵便で送付したり、 あるいは電話で知らせるなどして、 安全に通知 する必要がある。ユーザの端末装置の内部にあるメモリ 1.2は擬似乱数発生器 116と秘密値発生器 117から発生させた擬似乱数関数 PRNGと秘密値 Sとを一緒に P' = (S, PRNG) として記憶して保存する。
(8) 擬似乱数発生器を利用する場合 （その 2)
次に、 図 4を参照して、 擬似乱数発生器を利用する場合 （その 2) について 説明する。
まず、 擬似乱数発生器 116によりランダムに擬似乱数関数 PRNGを発生 する。そして、秘密値発生器 117もランダムに秘密値 Sを発生する。ここで、 ユーザは自分が覚えているパスワード （例えば、 " Pooh 93" ) を入力す る。擬似乱数関数 PRNGと秘密値 Sとユーザのパスワードが入力されたのを 受けて、 パスワード認証データ生成器 118はパスワード認証データ Hを生成 する。 パスワード認証デ一夕 Hは、 例えば、 H = PRNG (S II Pooh 93 II I D (U) II I D (S) ) mo d Qにより計算できる。 ここで、 I D (U) と ID (S) はそれぞれユーザとサーバの I Dを表す。 パスワード認証データ Hはユーザが直接にサーバに渡したり、 郵便で送付したり、 あるいは電話で知 らせるなどして、 安全に通知する必要がある。 ユーザの端末装置の内部にある メモリ 12は擬似乱数発生器 116と秘密値発生器 117から発生させた擬 似乱数関数 PRNGと秘密値 Sとを一緒に Ρ'. = (S, PRNG) として記憶 して保存する。 次に、 図 6、 7を参照して、 前述した初期化を行った端末装置 1とサーバ 2 (図 5参照） との間で相互認証及び鍵交換を行う動作を説明する。 ぐ端末装置の動作 >
(1) 多項式を利用した場合 （その 1とその 2)
初めに、 多項式を利用した場合の端末装置 1の動作を説明する。 端末装置 1 は、 前述した多項式を利用した場合 （その 1) 、 多項式を利用した場合 （その 2) に関わらず次のように動作する。
まず、 ユーザの端末装置 1に備えたメモリ 12から記憶された多項式 P' = P' (x) を読み出す。 結合器 32はメモリ 12から読み出した多項式 P' と ュ一ザが入力したパスヮ一ドにより P = p (X)を計算して出力する。例えば、 p (x) = p ' (X) + P o o h 93 = ひ i · X + P o o h 93mo d qによ り計算する。 マスク演算器 34は、 結合器 32から入力された Pと乱数発生器 33において発生させた乱数 とから を、 Y gK1 · h— p (1)mo に より計算する。 ここで p (1) は、 p (1) = ρ ' (1) +P o oh 93 = Q! 丄 · 1 +P o o h 93mo d Qにより計算する。 ここで、 「1」 はサーバの認 証 IDを表す。 通信処理部 35は をサーバ 2へ送信し、 サーバ 2から Y2を 受信する。 マスター鍵生成器 36は結合器 32から出力される Ρと乱数発生器 33から出力される と受信した Υ 2を入力として ΜΚを、 ΜΚ= (Υ2 · h一 p R1 mo d pにより計算して出力する。
続いて認証結果判断部 37は、 MKを入力として、 Vi-HASH (00 II Y! II Y2 II MK) により を計算してこの を通信処理部 35によりサーバ 2へ送信し、 サーバ 2から受信した V2と HASH (0 1 II Y x II Y2 II MK) を比較する。 ここで、 HASHは 方向ハッシュ関数であるし、 HASHの代 わりに MA C (Me s s a g e Au t h e n t i c a t i on Co d e) を使ってもよい。
次に、 認証結果判断部 37において V2と HASH (01 II Y！ II Y2 II MK) がー致しない場合、 認証結果判断部 37は、 エラー発生器 38に対して、 一致 しないことを通知する。 これを受けて、 エラー発生器 38はエラ一を発生して 処理を中断する。 一方、 認証結果判断部 37において V2と HASH (0 1 || Yi II Y2 II MK) がー致した場合はサーバ 2が正当な装置として認証してセッ シヨン鍵生成器 39は、 SK = HASH (1 1 II II Y2 II MK)によりセッ ション鍵 S Kを生成する。
(2) 多項式とハッシュ関数を利用した場合 （その 1とその 2)
次に、 多項式とハッシュ関数を利用した場合の端末装置 1の動作を説明する。 端末装置 1は、 前述した多項式と八ッシュ関数を利用した場合 （その 1) 、 多 項式とハッシュ関数を利用した場合（その 2 )に関わらず次のように動作する。 まず、 ユーザの端末装置 1に備えたメモリ 1 2から記憶された多項式とハツ シュ関数 P' = (ρ' (X) , HASH) を読み出す。 結合器 32はメモリ 1 2から読み出した多項式 p ' (X) とハッシュ関数 HASHとユーザが入力し たパスワードにより P = p (x) を計算して出力する。 例えば、 p' (X) が 1次多項式の場合、 p (x) =p' (x) +HASH (P o o h 9 3 II I D (U) II I D (S) ) = a ! · x+HASH (P o o h 9 3 II I D (U) II I D (S) ) mo dNにより計算する。 マスク演算器 34は、 結合器 32から入力された P と乱数発生器 3 3において発生させた乱数 とから を、 - gK1 ' !! ^ mo d pにより計算する。 ここで p (1) は、 p (1) =p ' (1) +HAS H (P o o h 9 3 II I D (U) II I D (S) ) = 1 - 1 +HASH (P o o h 93 II I D (U) II I D (S) ) mo dNにより計算する。 ここで、 p' (1) は p' (x) で xの代わりに 「1」 入れて計算した値である。 通信処理部 3 5 は をサーバ 2へ送信し、 サーバ 2から Y2を受信する。 マス夕一鍵生成器 3 6は結合器 32から出力される Ρと乱数発生器 3 3から出力される と受信 した Y 2を入力として MKを、 MK (Y2 · h— P R1 mo d pにより計算 して出力する。
ユーザの端末装置 1に備えたメモリ 1 2から読み出した多項式 p' (x) が n次多項式の場合、 結合器 32は多項式 p' (x) とハッシュ関数 HASHと ユーザが入力したパスワードにより P = p (X)を計算して出力する。例えば、 p (x) =p ' (x) +HASH (P o o h 9 3 II I D (U) II I D (S) ) mo dNにより計算する。 マスク演算器 34は、 結合器 32から入力された P と乱数発生器 3 3において発生させた乱数 1^とから を、 Yi g^' h mo d pにより計算する。 ここで p ( i ) は、 p ( i ) =p， ( i ) +HAS H (P o o h 93 II I D (U) II I D (S) ) mo dNにより計算する。 ここ で、 p ' ( i ) は i番目のサーバに対して p ' (X) で Xの代わりに 「 i」 入 れて計算した値である。 通信処理部 35は をサーバ 2へ送信し、 サーバ 2 から Y2を受信する。 マスター鍵生成器 36は結合器 32から出力される Ρと 乱数発生器 33から出力される 1^と受信した Υ2を入力として ΜΚを、 ΜΚ = (Υ2 · h_p ")) R1 mo d pにより計算して出力する。
続いて認証結果判断部 37は、 MKを入力として、 Vi HASH (00 II Yi II Y2 II MK) により を計算してこの を通信処理部 35によりサーバ 2へ送信し、 サーバ 2から受信した V2と HASH (01 II Υχ II Υ2 II MK) を比較する。 ここで、 HASHは一方向ハッシュ関数で—あるし、 HASHの代 わりに MAC (Me s s a g e Au t h e n t i c a t i on Co d e) を使ってもよい。
次に、 認証結果判断部 37において V2と HASH (01 II Yx II Y2 II MK) がー致しない場合、 認証結果判断部 37は、 エラー発生器 38に対して、 一致 しないことを通知する。 これを受けて、 エラー発生器 38はエラーを発生して 処理を中断する。 一方、 認証結果判断部 37において V2と HASH (01 II Yi II Y2 II MK) がー致した場合はサーバ 2が正当な装置として認証してセッ シヨン鍵生成器 39は、 SK = HASH (1 1 II II Y2 II MK)によりセッ シヨン鍵 SKを生成する。
(3) ハッシュ関数を利用した場合 （その 1とその 2)
次に、 .八ッシュ関数を利用した場合の端末装置 1の動作を説明する。 端末装 置 1は、 前述したハッシュ関数を利用した場合 （その 1) 、 ハッシュ関数を利 用した場合 （その 2) に関わらず次のように動作する。
まず、 ユーザの端末装置 1に備えたメモリ 12から記憶された秘密値とハツ シュ関数 P' = (S, HASH) を読み出す。 結合器 32はメモリ 12から読 み出した秘密値 Sとハッシュ関数 H A S Hとユーザが入力したパスヮ一ドに より P = pを計算して出力する。 例えば、 pは、 p=HASH (S II P o o h 93 II I D (U) II I D (S) ) mo d qにより計算する。 マスク演算器 34 は、 結合器 32から入力された Pと乱数発生器 33において発生させた乱数 R iとから を、 Yi g · h一 pmo d pにより計算する。通信処理部 3 5は、 Υιをサーバ 2へ送信し、 サーバ 2から Υ2を受信する。 マスター鍵生成器 36 は結合器 32から出力される Ρと乱数発生器 3 3から出力される と受信し た Y2を入力として MKを、 ΜΚ- (Υ2 · h— p) R1 mo d pにより計算して 出力する。
続いて認証結果判断部 3 7は、 MKを入力として、 V -HASH (0 0 II Yx II Υ2 II MK) により を計算してこの V を通信処理部 3 5によりサーバ 2へ送信し、 サーバ 2から受信した V2と HASH ( 0 1 II Y！ II Y2 II MK) を比較する。 ここで、 HASHは一方向ハッシュ関数であるし、 HASHの代 わりに M A C (Me s s a g e Au t h e n t i c a t i o n Co d e) を使ってもよい。
次に、 認証結果判断部 37において V2と HASH (0 1 II Ύ1 II Υ2 II MK) がー致しない場合、 認証結果 断部 37は、 エラー発生器 38に対して、 一致 しないことを通知する。 これを受けて、 エラー発生器 38はエラーを発生して 処理を中断する。 一方、 認証結果判断部 37において V2と HASH (0 1 II Yx II Υ2 II MK) がー致した場合はサーバ 2が正当な装置として認証してセッ シヨン鍵生成器 39は、 SK = HASH (1 1 II II Y2 II MK)によりセッ シヨン鍵 SKを生成する。
(4) 擬似乱数発生器を利用した場合 （その 1とその 2)
次に、 疑似乱数関数を利用した場合の端末装置 1の動作を説明する。 端末装 置 1は、 前述した擬似乱数発生器を利用した場合 （その 1) 、 擬似乱数発生器 を利用した場合 （その 2) に関わらず次のように動作する。
疑似乱数関数を利用した場合は、 ユーザの端末装置 1に備えたメモリ 1 2に 記憶されたハッシュ関数 H A S Hの代わりに疑似乱数関数 PRNGを用いる 以外は、 ハッシュ関数を利用した場合と同様の動作であるため、 ここでは詳細 な説明を省略する。 <サーバの動作； >
(1) 多項式を利用した場合 （その 1) 、 多項式とハッシュ関数を利用した場 合 （その 1) 、 ハッシュ関数を利用した場合 （その 1) 、 擬似乱数関数を利用 した場合 （その 1)
サーバ 2は、 前述した多項式利用した場合 （その 1) 、 多項式とハッシュ関 数を利用した場合 （その 1) 、 ハッシュ関数利用した場合 （その 1) 、 擬似乱 数発生器を利用した場合 （その 1) に関わらず次のように動作する。
サーバ 2に備えたメモリ 4 1に保存されたユーザ I Dとパスワードの認証 データ Hを読み出す。マスク演算器 43はメモリ 41から読み出した Hと乱数 発生器 42から発生させた乱数 R2を入力として Y2を/ Y2=gR2 · Hmo d Pにより計算する。 通信処理部 44は、 計算して得られた Y2を端末装置 1に 送信し、 端末装置 1から受信した をマスタ一鍵生成器 45へ出力する。 マ スク鍵生成器 45はメモリ 41から読み出した Hと乱数発生器 42からの R2 と通信処理部 44からの を入力として MKを、 MK= (Yi - H) R2mo d Pにより計算して、 MKを出力する。
続いて認証結果判断部 46は、 MKを入力として、 V2 = HASH (0 1 II Yx II Ύ2 II MK) により V2を計算してこの V2を通信処理部 44により端末装 置 1へ送信し、 端末装置 1から受信した と HASH (00 II Yi II Y2 II Μ Κ) を比較する。 ここで、 HASHは一方向ハッシュ関数であるし、 HASH の代わりに M A C (Me s s a g e Au t h e n t i c a t i o n C o d e) を使ってもよい。
次に、.認証結果判断部 46において と HASH (00 II Y! II Y2 II MK) がー致しない場合、 認証結果判断部 46は、 エラー発生器 47に対して、 一致 しないことを通知する。 これを受けて、 エラー発生器 47はエラーを発生して 処理を中断する。 一方、 認証結果判断部 46.において と HASH (00 II Y II Y2 II MK) がー致した場合は端末装置 1が正当な装置として認証してセ ッシヨン鍵生成器 48は、 SK = HASH (1 1 II Y, II Y2 II MK)によりセ ッシヨン鍵 SKを生成する。 (2) 多項式を利用した場合 （その 2) 、 多項式とハッシュ関数を利用した場 合 （その 2) 、 ハッシュ関数を利用した場合 （その 2) 、 擬似乱数関数を利用 した場合 （その 2)
サーバ 2は、 前述した多項式利用した場合 （その 2) 、 多項式とハッシュ関 数を利用した場合 （その 2) 、 ハッシュ関数を利用した場合 （その 2) 、 擬似 乱数発生器を利用した場合 （その 2) に関わらず次のように動作する。
サーバ 2に備えたメモリ 41に保存されたユーザ I Dとパスヮードの認証 データ Hを読み出す。 マスク演算器 43はメモリ 41から読み出した Hと乱数 発生器 42から発生させた乱数 R 2を入力として Y2を、 Y2=gR2 · hHmo d pにより計算する。 通信処理部 44は、 計算して得られた Y2を端末装置 1に 送信し、 端末装置 1から受信した をマスター鍵生成器 45へ出力する。 マ スク鍵生成器 45はメモリ 41から読み出した Hと乱数発生器 42からの R 2 と通信処理部 44からの を入力として MKを、 ΜΚ= (Υχ - H) R2mo dpにより計算して、 MKを出力する。
続いて認証結果判断部 46は、 MKを入力として、 V2 = HASH (0 1 II II Y2 II MK) により V2を計算してこの V2を通信処理部 44により端末装 置 1へ送信し、 端末装置 1から受信した V！と HASH (00 II II Y2 II Μ Κ) を比較する。 ここで、 HASHは一方向ハッシュ関数であるし、 HASH の代わりに M A C (Me s s a g e Au t h e n t i c a t i on C od e) を使ってもよい。
次に、 認証結果判断部 46において と HASH (00 II Y! II Y2 II MK) がー致しない場合、 認証結果判断部 46は、 エラ一発生器 47に対して、 一致 しないことを通知する。 これを受けて、 エラ一発生器 47はエラーを発生して 処理を中断する。 一方、 認証結果判断部 46において と HASH (00 11 Y1 II Υ2 II MK) がー致した場合は端末装置 1が正当な装置として認証してセ ッシヨン鍵生成器 48は、 SK = HASH (1 1 II II Y2 II MK)によりセ ッション鍵 SKを生成する。
<パスワード認証データの更新一 1> ユーザは、 サーバに対してすでに登録されたパスワード認証データを、 自分 が覚えているパスワードを変えずに、 更新したい時、 自分の端末装置の更新化 を行う。 図 9は、 ユーザの端末装置の更新化処理の構成を示すブロック図であ る。 更新化処理は、 多項式発生器 1 3による多項式 T' とユーザの端末装置 1 に備えたメモリ 1 2から記憶された多項式 P， が入力されると、 更新値生成器 14によって、サーバ更新用の値 H' と、ユーザ保存用の更新された多項式 P' が生成され、 H' は、 サーバに受け渡され、 更新された多項式 P' は、 メモリ 12へ保存する。 ここでの更新化処理は、 前述した多項式を利用した場合 （そ の 1.) 、 多項式を利用した場合 （その 2) 、 多項式とハッシュ関数を利用した 場合 （その 1) 、 多項式とハッシュ関数を利用した場合.（その 2) に適用する ことが可能である。
<端末装置の更新化処理 >
( 1 ) 多項式を利用した場合 '(その 1 )
初めに、 図 9を参照して、 多項式を利用した場合 （その 1) の端末装置 1の 更新化処理の動作を説明する。
まず、 多項式発生器 1 3によりランダムに多項式を発生する。 このとき、 登 録したサーバの数が一つだったら Xを変数とする 1次多項式 （ t ' (χ) = β ι · xmo d q) を、 サーバの数が n個だったら n次多項式（ t， (x) = )3！ · x + ιδ 2 · χ2+ · · · +jSn · xnmo d q) を発生する。 ここで、 j3は （Z/ q Z) *から無作為に選ばれる。例えば、一つのサーバの場合、 T' = t ' (x) は、 t，. （X) =3 i · xmo d qとなる。 ここで、 ユーザの端末装置 1に備 えたメモリ 12から記憶された多項式 Ρ' =ρ' (χ) を読み出す。 多項式 t ' (x) と多項式 P' (x) が入力されたら更新値生成器 14は、 ユーザ保存用 の更新された多項式 P' とサーバ更新用の値 を生成する。 更新された多項 式 P， は、 例えば P ' = t ' (x) + p ' (x) = (α !+ iS χ) · xmo d qにより計算できる。 サーバ更新用の値 H' 、 例えば H， =h ("mo d p により計算できる。 ここで、 t， (1) は t ' (X) で Xの代わりにサーバの I D (例えば、 「1」 ） 入れて計算した値である。 サーバ更新用の値 H' はュ —ザが直接にサーバに渡したり、 郵便で送付したり、 あるいは電話で知らせる などして、 安全に通知する必要がある。 ユーザの端末装置の内部にあるメモリ 1 2は更新された多項式 P' = t ' (χ) +ρ' (x) を記憶して保存する。
(2) 多項式を利用した場合 （その 2)
次に、 図 9を参照して、 多項式を利用した場合 （その 1) の端末装置 1の更 新化処理の動作を説明する。
まず、 多項式発生器 1 3によりランダムに多項式を発生する。 このとき、 登 録したサーバの数が一つだったら Xを変数とする 1次多項式 （t ' (X) = β ！ · xmo d q) を、 サーバの数が n個だったら n次多項式（ t， (x) = ι8 i · x + j82 · x2+ · · · +j8n · xnmo d q) を発生する。 ここで、 j3は （Z/ q Z) *から無作為に選ばれる。例えば、 一つのサーバの場合、 T' = t ' (X) は、 t， （X) =i3 · xmo d qとなる。 ここで、 ユーザの端末装置 1に備 えたメモリ 1 2から記憶された多項式 Ρ' =ρ' (χ) を読み出す。多項式 t ' (x) と多項式 P' (X) が入力されたら更新値生成器 14は、 ユーザ保存用 の更新された多項式 P' とサーバ更新用の値 H' を生成する。 更新された多項 式！5' は、 例えば P， = t ' (x) + p ' (x) = ( t+ β 1) - xmo d Qにより計算できる。 サーバ更新用の値 H' 、 例えば H' = t ' (1) mo d Qにより計算できる。 ここで、 t ' (1) は t ' (x) で xの代わりにサ一 バの I D (例えば、 「1」 ） 入れて計算した値である。 サーバ更新用の値 H' はユーザが直接にサーバに渡したり、 郵便で送付したり、 あるいは電話で知ら せるなどして、 安全に通知する必要がある。 ユーザの端末装置の内部にあるメ モリ 1 2は更新された多項式 P' = t ' (χ) +ρ' (χ) を記憶して保存 する。
(3) 多項式とハッシュ関数を利用した場合 （その 1)
次に、 図 9を参照して、 多項式とハッシュ関数を利用した場合 （その 1) の 端末装置 1の更新化処理の動作を説明する。
まず、 多項式発生器 1 3によりランダムに多項式を発生する。 このとき、 登 録したサーバの数が一つだったら xを変数とする 1次多項式 （t ' (χ) = β 1 - xmo dN) を、 サーバの数が n個だったら n次多項式（ t ' (x) = i3！ · x + jS 2 · x2+ - · · +j8n · xnmo dN) を発生する。 ここで、 3は （Ζ/ q Z) *から無作為に選ばれる。例えば、 一つのサーバの場合、 T' = t ' (x) は、 t ' (x) =]3 i · xmo dNとなる。 ここで、 ユーザの端末装置 1に備 えたメモリ 1 2から記憶された多項式とハッシュ関数 Ρ， = (ρ' (χ) ， HASH) を読み出す。 多項式!； ' （X) と多項式 p' (X) が入力されたら 更新値生成器 14は、 ユーザ保存用の更新された多項式 P' とサーバ更新用の 値 H' を生成する。 更新された多項式 P' は、 例えば P' = t ' (X) +p，
(x) = ( 1 + 1) · xmo dNにより計算できる。サ一パ更新用の値 H，、 例えば H' =h ")mo d pにより計算できる。 ここで、 t， (1) は
(X) で Xの代わりに 「1」 を入れて計算した値である。
例えば、 登録したサーバの数が nの場合、 更新値生成器 14は、 i番目のサ —バに対してサーバ更新用の値 H' を生成する。 サーバ更新用の値 H' は、 例 えば H' =h (i)mo d pにより計算できる。 ここで、 t ' ( i ) は n次多 項式 t ' (x) で xの代わりに 「 i」 を入れて計算した値である。
サーバ更新用の値 H' は ーザが直接にサーバに渡したり、 郵便で送付した り、 あるいは電話で知らせるなどして、 安全に通知する必要がある。 ユーザの 端末装置の内部にあるメモリ 12は更新された多項式 P' = t ' (χ) +ρ'
(x) とメモリ 1 2から読み出したハッシュ関数 HASHとを一緒に Ρ' =
( t ' (x) +ρ' (χ) , HASH) として記憶して保存する。
(4) 多項式とハッシュ関数を利用した場合 （その 2)
次に、 図 9を参照して、 多項式とハッシュ関数を利用した場合 （その 2) の 端末装置 1の更新化処理の動作を説明する。 .
まず、 多項式発生器 1 3によりランダムに多項式を発生する。 このとき、 登 録したサーバの数が一つだったら Xを変数とする 1次多項式 （t ' (x) = i · xmo dN) を、サーバの数が n個だったら n次多項式（ I: ' (x) =j3！ · x + /32 · x2+ · · - + η - xnmo dN) を発生する。 ここで、 は / Q Z) *から無作為に選ばれる。例えば、 一つのサーバの場合、 T' = t ' (X) は、 t， (x) =)S i · xmo dNとなる。 ここで、 ュ一ザの端末装置 1に備 えたメモリ 1 2から記憶された多項式とハッシュ関数 P' = (p， （X) ， HASH) を読み出す。 多項式 t ' (X) と多項式 p， （X) が入力されたら 更新値生成器 14は、 ユーザ保存用の更新された多項式 P' とサーバ更新用の 値 H' を生成する。 更新された多項式 P' は、 例えば P' = t ' (χ) +ρ'
(χ) = (α ^ β ^ · xmo dNにより計算できる。サーバ更新用の値 H， 、 例えば H' = t ' (1) mo dNにより計算できる。 ここで、 t ' (1) は t '. (X) で Xの代わりに 「1」 を入れて計算した値である。
例えば、 登録したサーバの数が nの場合、 更新値生成器 14は、 i番目のサ —バに対してサーバ更新用の値 H' を生成する。 サーバ更新用の値 H' は、 例 えば H' = t ' ( i ) mo dNにより計算できる。 ここで、 t ' ( i ) は n次 多項式 t ' (x) で xの代わりに 「 i」 を入れて計算した値である。
サーバ更新用の値 H' はユーザが直接にサーバに渡したり、 郵便で送付した り、 あるいは電話で知らせるなどして、 安全に通知する必要がある。 ユーザの 端末装置の内部にあるメモリ 1 2は更新された多項式 P' = t ' (χ) +ρ' (χ) とメモリ 1 2から読み出したハッシュ関数 HASHとを一緒に Ρ ' = ( t ' (χ) +ρ' (χ) ， HASH) として記憶して保存する。
<サーバの更新化処理 >
(1) 多項式を利用した場合 （その 1) 、 多項式とハッシュ関数を利用した場 合 （その 1)
初めに、 図 1 0を参照して、 多項式を利用した場合 （その 1) 、 多項式とハ ッシュ関数を利用した場合 （その 1) のサーバ 2の更新化処理の動作を説明す る。 サーバ 2は、 前述した多項式利用した場合 （その 1) 、 多項式とハッシュ 関数を利用した場合 （その 1) に関わらず次のように動作する。
まず、 サーバ 2に備えたメモリ 41に保存されたユーザ I Dとパスワード認 証デー夕 Hを読み出す。 ユーザの端末装置から送られたサーバ更新用の値 H ' とメモリ 4 1から読み出したパスワード認証データ Hが入力されたら更新値 生成器 21は、 サーバ保存用の更新されたパスワード認証データ Hを生成する。 更新されたパスワード認証データ Hは、 例えば H= p (1) · (1)= p (1) + t' (1)mo d pにより計算できる。サーバの内部にあるメモリ 41は更新され たパスワード認証データ Hを記憶して保存する。
(2) 多項式を利用した場合 （その 2)
次に、 図 10を参照して、 前述した多項式を利用した場合 （その 2) のサー バ 2の更新化処理の動作を説明する。
まず、 サーバ 2に備えたメモリ 41に保存されたユーザ I Dとパスワード認 証データ Hを読み出す。 ユーザの端末装置から送られたサーバ更新用の値 H ' とメモリ 41から読み出したパスワード認証データ Hが入力されたら更新値 生成器 21は、 サーバ保存用の更新されたパスワード認証データ Hを生成する。 更新されたパスワード認証データ Hは、 例えば H= p (1) + t， (1) m o d qにより計算できる。サーバの内部にあるメモリ 41は更新されたパスヮ 一ド認証デー夕 Hを記憶して保存する。
(3) 多項式とハッシュ関数を利用した場合 （その 2)
次に、図 10を参照して、前述した多項式とハッシュ関数を利用した場合（そ の 2) のサーバ 2の更新化処理の動作を説明する。
まず、 サーバ 2に備えたメモリ 41に保存されたユーザ I Dとパスヮード認 証データ Hを読み出す。 ユーザの端末装置から送られたサーバ更新用の値 H' とメモリ 41から読み出したパスワード認証データ Hが入力されたら更新値 生成器 21は、 サーバ保存用の更新されたパスワード認証データ Hを生成する。 更新されたパスワード認証データ Hは、 例えば H= p (1) + t， (1) m o dNにより計算できる。サーバの内部にあるメモリ 41は更新されたパスヮ ―ド認証デー夕 Hを記憶して保存する。
<パスワード認証デ一夕の更新一 2 >
ユーザは、 サーバに対してすでに登録されたパスワード認証データを、 自分 が覚えているパスワードを変えながら、 更新したい時、 自分の端末装置の更新 化処理を行う。 図 1 1は、 ユーザの端末装置の更新化処理の構成を示すブロッ ク図である。 更新化処理は、 秘密値発生器 15による秘密値 S' とユーザの新 しいパスワード PW' とユーザの端末装置 1に備えたメモリ 12から記憶され た P' が入力されると、 パスワード認証データ更新器 16によって、 サーバ更 新用のパスワード認証データ H' と、 ユーザ保存用の更新された P' が生成さ れ、 H' は、 サーバ 2に受け渡され、 更新された P' は、.メモリ 12へ保存す る。 ここでの更新化処理は、前述したハッシュ関数を利用した場合（その 1)、 ハッシュ関数を利用した場合 （その.2) 、 擬似乱数発生器を利用した場合 （そ の 1) 、 擬似乱数発生器を利用した場合 （その 2) に適用することが可能であ る。 そして、 多項式を利用した場合 （その 1) 、 多項式を利用した場合 （その 2) 、 多項式とハッシュ関数を利用した場合 （その 1) 、 多項式とハッシュ関 数を利用した場合 （その 2) も同じように初期化処理と同様の動作を用いて適 用することが可能なため、 ここでは詳細な説明を省略する。 ぐ端末装置の更新化処理 >
(1) ハッシュ関数を利用した場合 （その 1)
初めに、 図 1 1を参照して、 ハッシュ関数を利用した場合 （その 1) の端末 装置 1の更新化処理の動作を説明する。
まず、 秘密値発生器 1 5によりランダムに秘密値 S' を発生する。 ここで、 ユーザの端末装置 1に備えたメモリ 12から記憶された P' = (S, HASH) を読み出す。 ユーザが覚えている新しいパスワード （PW' ) とハッシュ関数 HASHと秘密値 S， が入力されたらパスワード認証データ更新器 16は、 ュ —ザ保存用の更新された P' とサーバ更新用のパスワード認証データ H' を生 成する。 サーバ更新用のパスワード認証データ H， は、 例えば H， =hHASH (s" IIPW' II ID (u) II ID(s) ) mo d pにより計算できる。 ここで、 I D (U) と I D (S) はそれぞれユーザとサーバの I Dを表す。 サーバ更新用のパスワード認証デー 夕 H' はユーザが直接にサーバ 2に渡したり、 郵便で送付したり、 あるいは電 話で知らせるなどして、 安全に通知する必要がある。 ユーザの端末装置 1の内 部にあるメモリ 12は更新された P， = (S， ， HASH) を記憶して保存す る。
(2) ハッシュ関数を利用した場合 （その 2)
次に、 図 11を参照して、 ハッシュ関数を利用した場合 （その 2) の端末装 置 1の更新化処理の動作を説明する。
まず、 秘密値発生器 15によりランダムに秘密値 S' を発生する。 ここで、 ュ一ザの端末装置 1に備えたメモリ 12から記憶された P' = (S, HASH) を読み出す。 ユーザが覚えている新しいパスワード （PW' ) とハッシュ関数 HASHと秘密値 S' が入力されたらパスワード認証データ更新器 16は、 ュ —ザ保存用の更新された P' とサーバ更新用のパスワード認証データ H' を生 成する。 サーバ更新用のパスワード認証データ H， は、 例えば H， =HASH (S ' II PW II I D (U) II ID (S) ) mo d Qにより計算できる。 ここ で、 ID (U) と ID (S) はそれぞれユーザとサーバの I Dを表す。 サ一パ 更新用のパスワード認証データ H' はユーザが直接にサーバ 2に渡したり、 郵 便で送付したり、 あるいは電話で知らせるなどして、 安全に通知する必要があ る。 ユーザの端末装置 1の内部にあるメモリ 12は更新された P' = (S' , HASH) を記憶して保存する。
(3) 擬似乱数発生器を利用した場合 （その 1) 、 擬似乱数発生器を利用した 場合 （その 2)
次に、.図 11を参照して、 擬似乱数発生器を利用した場合 （その 1) 、 擬似 乱数発生器を利用した場合 （その 2) の端末装置 1の更新化処理の動作を説明 する。
擬似乱数関数を利用した場合 （その 1とその 2) は、 メモリ 12に記憶され たハツシュ関数 H A S Hの代わりに疑似乱数関数 P RN Gを用いる以外は、 ハ ッシュ関数を利用した場合 （その 1とその 2) と同様の動作であるため、 ここ では詳細な説明を省略する。 <サーバの更新化処理 >
(1) ハッシュ関数を利用した場合 （その 1) 、 ハッシュ関数を利用した場合 (その 2) 、 擬似乱数発生器を利用した場合 （その 1) 、 擬似乱数発生器を利 用した場合 （その 2)
初めに、 図 12を参照して、 ハッシュ関数を利用した場合 （その 1) 、 ハツ シュ関数を利用した場合（その 2 )、擬似乱数発生器を利用した場合（その 1 )、 擬似乱数発生器を利用した場合 （その 2) のサーバ 2の更新化処理の動作を説 明する。サーバ 2は、前述したハツシュ関数を利用した場合（その 1とその 2 )、 擬似乱数発生器を利用した場合 （その 1とその 2) に関わらず次のように動作 する。
まず、 サ一パ 2に備えたメモリ 41に保存されたユーザ I Dとパスワード認 証デー夕 Hを読み出す。 ユーザの端末装置 1から送られたサーバ更新用のパス ワード認証データ H' とメモリ 41から読み出したパスワード認証データ Hが 入力されたらパスワード認証データ更新器 22は、 サ一バ保存用のパスワード 認証データ Hをユーザの端末装置 1から送られた H' に更新する。 サーバの内 部にあるメモリ 41は更新されたパスワード認証データ Η = Η' を記憶して保 存する。
<第 2実施例 >
以下、 本発明の公開鍵暗号方式を使った実施例について説明する。 ただし、 本発明は以下の各実施例に限定されるものではなく、 例えばこれら実施例の構 成要素同士を適宜組み合わせてもよい。
ここで、 RS Α公開鍵暗号方式を使った実施例の説明する前に、 いくつかの 背景知識及び基礎的な記号について説明しておく。
公開鍵暗号方式では、 公開鍵（PubK)および秘密鍵（P r i K) の対（P ubK, P r i K) が存在する。 公開鍵は秘密ではなく、 誰でも得ることがで きる。 暗号化は、 公開鍵を用いてメッセージ mを C = En cPubK (m) とな るような暗号文 Cを生成することが可能である。 暗号文は、 秘密鍵を用いての み、 m = De cPr iK (C) と復号可能である。 暗号文は、 公開鍵を用いては 復号できない。 そして公開鍵署名方式では、 メッセ一ジ mを署名化して s = S i gPr iK (m) となるような署名文 （m， s) を生成することが可能である。 署名文の検証は、 公開鍵を用いて、 m' =Ve r PubK (s) を求め、 mと m' を比較することで可能である。 つまり、 mと m' がー致した場合はその署名文 (m, s) が正しいことを検証する。 そうではない場合は、 （m， s) が正し い署名文ではないことになる。
周知の RS A公開鍵方式では、 公開鍵は （N， e) であり、 秘密鍵は （N， d) である。 ただし、 Nは、 2つのランダムに選択された大きな素数 pと の 積であり （すなわち、 Ν=ρ· Q) 、 eは、 eと （p— 1) · (q— 1) の最 大公約数が 1であるような小さい任意の数 （例えば、 e = 3あるいは e = 216 + 1) であり、 dは、 e— imo d ( (p— 1) · (q- 1) ) である。 安全性 を最大化するには、 pと Qを同じ長さにする。 メッセージ m (meZN*) に対 して暗号化関数は、 En c PubK (m) =memo dNであり、 復号化関数は、 D e c Pr iK (C) =Cdmo dNである。 ここで、 暗号文 Cと公開鍵 （N， e) が与えられた時、メッセ一ジ mを求めるのは計算量的に困難である。 RSAは、 大きな数 Nの素因数分解が難しいことから安全性を得ている。 そして署名化関 数は、 S i gPr iK (m) =mdmo dNであり、 検証化関数は、 Ve r PubK (s ) = s'emo dNである。 一般に、 暗号システムでは、 その安全性のレべ ルを記述する安全性パラメータを有する。 ここでは、 ハッシュ関数 HASHの 安全性パラメ一夕として kを用い （ただし、 lZ2kは無視できるほど小さい と仮定する） 、 RS A公開鍵方式の安全性パラメ一夕として 1を用い、 特に、 RS Aの法 Nは長さ 1であると仮定する。 また、 { 0， 1 } *は有限の 2進数 のストリングの集合を、 { 0， 1 } kは長さ kの 2進数のストリングの集合を 示す。 ハッシュ関数 HASHは {0, 1 } *の入力から {0, 1 } kの出力を出 す安全な一方向関数であり、 FDH (Fu l l -D oma i n Ha s h) 関 数は { 0, 1 } *の入力から ZN*\ { 1 } の出力を出す安全な一方向関数であ る。 また、 乱数発生器から発生される乱数は T (TGZN*) を無作為に生成す る。 また、 IIは値を連結 （c on c a t e n a t i on) するという意味であ る。 <端末装置の初期化 >
ュ一ザは、 サーバに対して個人登録したい時、 自分の端末装置の初期化を行 う。 図 1は、 ユーザの端末装置の初期化処理の構成を示すブロック図である。 初期化は、 ユーザがパスワードを入力すると、 データ伸張器 1 1によって、 サ ーパ登録用のパスワード認証データ Hと、 ユーザ保存用の値 P' が生成され、 パスワード認証データ Hは、 サーバに受け渡され、 値 Ρ' -は、 メモリ 12へ保 存する。 ここで、 データ伸長器 1 1は、 多項式と FDH関数、 FDH関数など で構成することが可能である。
(1) 多項式と FDH関数を利用する場合 （その 1)
初めに、 図 13を参照して、 多項式と FDH関数を利用する場合 （その 1) について説明する。
まず、 01"1関数発生器122によりランダムに FDH関数 FDHを発生す る。 そして、 多項式発生器 123によりランダムに多項式を発生する。 このと き、登録するサーバの数が一つだったら Xを変数とする 1次多項式（ρ' (x) = α！ · xmo dN) を、 サーバの数が n個だったら n次多項式 （ρ'' (χ) =«! · χ + α2 · χ2+ · · · + αη · xnmo dN) を発生する。 ここで、 α は ΖΝ*から無作為に選ばれる。 例えば、 一つのサーバの場合、 ρ' (χ) は、 ρ ' (χ) = i · xmo dNとなる。 ここで、 ユーザは自分が覚えているパ スワード （例えば、 " P o oh 93" ) を入力する。 多項式と FDH関数とュ 一ザのパスワードが入力されたらパスワード認証データ生成器 124は、 パス ワード認証データ Hを生成する。 パスワード認証データ Hは、 例えば H=p (1) =p， (1) +P o o h 93mo dNにより計算できる。 ここで、 p， (1) は ' （x) で xの代わりにサーバの I D (例えば、 「1」 ） を入れて 計算した値である。パスヮード認証データ Hはユーザが直接にサーバに渡した り、 郵便で送付したり、 あるいは電話で知らせるなどして、 安全に通知する必 要がある。 ユーザの端末装置の内部にあるメモリ 12は多項式発生器から発生 された多項式 P' (X) と FDH関数発生器から発生された FDH関数 FDH とを一緒に P， = (p (x) FDH) として記憶して保存する。
(2) 多項式と FDH関数を利用する場合 （その 2)
次に、 図 1 3を参照して、 多項式と FDH関数を利用する場合 （その 2) を 利用する場合について説明する。
まず、 FDH関数発生器 122によりランダムに FDH関数 FDHを発生す る。 そして、 多項式発生器 123によりランダムに多項式を発生する。 このと き、登録するサーバの数が一つだったら Xを変数とする 1次多項式（ρ ' (χ) = α！ · xmo dN) を、 サーバの数が n個だったら n次多項式 （ρ' (χ) = £¾ 1 · χ + αί 2 · χ 2+ · · · +(¾„ · xnmo dN) を発生する。 ここで、 α は ΖΝ*から無作為に選ばれる。 例えば、 一つのサーバの場合、 ρ' (X) は、 P ' (x) · xmo dNとなる。 ここで、 ユーザは自分が覚えているパ スワード （例えば、 " P o oh 93" ) を入力する。 多項式と FDH関数とュ —ザのパスワードが入力されたらパスワード認証データ生成器 124は、 パス ワード認証データ Hを生成する。 パスワード認証データ Hは、 例えば H=p (1) =p ' (1) +FDH ( P o o h 93 II I D (U) II I D (S) ) mo dNにより計算できる。 ここで、 I D (U) と I D (S) はそれぞれユーザと サーバの I Dを表す。 ここで、 p ' (1) は p ' (X) で Xの代わりに 「1」 入れて計算した値である。
例えば、 登録するサーバの数が nの場合、 パスワード認証データ生成器 1 2 4は、 i番目のサーバに対してパスワード認証データ Hを生成する。 パスヮー ド認証データ Hは、 例えば H=p ( i ) =p ' ( i ) +FDH (P o o h 93 II I D (U) II I D (S) ) mo dNによりに計算できる。 ここで、 I D (U) と I D (S) はそれぞれユーザと i番目のサーバの I Dを表す。 ここで、 p' ( i ) は n次多項式 p' (x) で Xの代わりに 「 i」 を入れて計算した値であ る。
パスワード認証データ Hはユーザが直接にサーバに渡したり、 郵便で送付し たり、 あるいは電話で知らせるなどして、 安全に通知する必要がある。 ユーザ の端末装置の内部にあるメモリ 12は多項式発生器から発生された多項式 p' (x) と FDH関数発生器から発生された FDH関数 FDHとを一緒に P' = (ρ' (χ) , FDH) として記憶して保存する。
(3) FDH関数を利用する場合
次に、 図 14を参照して、 FDH関数を利用する場合について説明する。 まず、 011関数発生器125によりランダムに FDH関数 FDHを発生す る。 そして、 秘密値発生器 126によりランダムに秘密値 Sを発生する。 ただ し、 Sは全探索攻撃を防げるような長さの値である （例えば、 Sは 80ビット 以上の値） 。 ここで、 ユーザは自分が覚えているパスワード （例えば、 " P o o h 93 " ) を入力する。 FDH関数と秘密値 Sとユーザ、のパスワードが入力 されたらパスワード認証データ生成器 1 27はパスワード認証データ Hを生 成する。 パスワード認証データ Hは、 例えば、 H=FDH (S II P o o h 93 II I D (U) II I D (S) ) により計算できる。 ここで、 I D (U) と I D (S) はそれぞれユーザとサーバの I Dを表す。 パスヮ一ド認証データ Hはユーザが 直接にサーバに渡したり、 郵便で送付したり、 あるいは電話で知らせるなどし て、 安全に通知する必要がある。 ユーザの端末装置の内部にあるメモリ 12は 秘密値発生器 1 26から発生された秘密値 Sと FDH関数発生器 1 2 5から 発生された FDH関数 FDHとを一緒に P' = (S， FDH) として記憶して 保存する。 ぐ端末装置とサーバとの初期化 > .
サーバ.は、 RS A公開鍵をユーザに送信したい時、 初期化処理を行う。 サー バは、 RS A公開鍵方式に従って公開鍵と秘密鍵の対を生成し、 その公開鍵を ユーザに送信する。 ここで、 初期化は、 安全な通信、 安全ではない通信などで 実現することが可能である。安全ではない通信を利用する場合では、ユーザは、 受信した公開鍵が正しいであるかどうかを決定する。 このユーザによる決定は、 ユーザに、 サーバが適当な方法で選択した公開鍵を生成したかどうかを決定す る方法を提供する。 つまり、 サーバが提供した公開鍵 eと （p— 1) · (q- 1) の最大公約数が 1で （すなわち、 g c d (e， (p- 1) . (q- 1) ) = 1) あるかどうかを決定するために RS A署名方式を使う。
(1) 安全な通信を利用する場合
初めに、 図 1 5を参照して、 安全な通信を利用する場合の初期化処理につい て説明する。
まず、 RS A鍵生成器 23により公開鍵 （N， e) と秘密鍵 （N, d) の対 を生成する。 RSA公開鍵 （N, e) はサーバが直接にュ一ザに渡したり、 郵 便で送付したり、 あるいは電話で知らせるなどして、 安全に通知する必要があ る。.サーバの内部にあるメモリ 41は RS A秘密鍵 （N, d) を記憶して保存 する。 -
(2) 安全ではない通信を利用する場合
次に、 図 1 6を参照して、 安全ではない通信を利用する場合の初期化処理に ついて説明する。
まず、 ユーザの端末装置 1にある乱数発生器 1 7によりランダムに乱数 (RiG { 0， 1 } k) を発生し、 サーバに送信する。 一方、 サーバ 2にある R SA鍵生成器 24により公開鍵（N, e) と秘密鍵（N， d) の対を生成する。 そして、 乱数発生器 2 5によりランダムに乱数 R2 (R2e { 0， 1 } k) を発 生する。 RS A署名文生成器 26は、 端末装置 1から受信した と RS A鍵 生成器 24から生成された秘密鍵 （N, d) と乱数発生器 25から発生させた 乱数 R2を入力として、 {mj} 1≤j≤nの署名 { s 1≤j≤nを生成する （ただし、 nは n≥ 1 o ge (PW- (e— 1) / e ) になるような整数である。 ここで、 PWはパスワードを表す。 ） 。 署名 {S j} 1≤j≤nは、 { S j m mo dN} , ≤j≤nにより計算する。ここで、 {m 1≤j≤nは HASH (n II N II e II I D (U) II I D (S) II Rx II R2) の出力から長さ 1のブロックを n個に分けて得たも のである。 I D (U) と I D (S) はそれぞれユーザとサーバの I Dを表す。 サーバ 2は、 公開鍵 （N, e) と計算して得られた署名文 （R2, { s 1≤j≤ n) を端末装置 1に送信する。 サーバ 2の内部に備えたメモリ 41は、 RSA 鍵生成器 24から生成された秘密鍵 （N， d) を記憶して保存する。 ユーザの端末装置 1にある検証結果判断部 1 8は、 乱数発生器 1 7において 発生させた とサーバ 2から受信した （ （N， e) , (R2， { s ,·} 1≤j≤n) ) を入力として、 署名文 （R2， { s j} 1≤j≤n) の検証を行う。 {mj S jemo dN} 1≤j≤nにより {nij} 1≤j≤nを計算してこの {nij} 1≤j≤nと HASH (n II N II e II I D (U) II I D (S) || R1 II R2) を比較する。 検証結果判断部 1 8において {mj 1≤j≤nと HASH (n II N II e II I D (U) II I D (S) II Ri II R2) がー致しない場合、 検証結果判断部 1 8は、.エラ一発生器 1 9に 対して、 一致しないことを通知する。 これを受けて、 エラ一発生器 1 9はエラ 一を発生して処理を中断する。 一方、 検証結果判断部 1 8において {mj 1≤J ≤nと HASH (n II N II e II I D (U) II I D (S) II R i II R 2)がー致した 場合はサーバ 2の公開鍵 （N, e) が正当なものとして検証して、 ユーザの端 末装置 1の内部に備えたメモリ 12に、公開鍵（N, e)を記憶して保存する。 次に、 図 1 7、 1 8を参照して、 前述した初期化を行った端末装置 1とサー バ 2 (図 5参照） との間で相互認証及び鍵交換を行う動作を説明する。
<端末装置の動作 >
(1) 多項式と FDH関数を利用した場合 （その 1)
初めに、 多項式と FDH関数を利用した場合 （その 1) の端末装置 1の動作 を説明する。
まず、 ユーザの端末装置 1に備えたメモリ 1 2から記憶された多項式と FD H関数 P' = (ρ' (x) , FDH) を読み出す。 結合器 52はメモリ 1 2か ら読み出した多項式 p' (x) と FDH関数 FDHとユーザが入力したパスヮ ードにより W=FDH (p (x) II I D (U) II I D (S) ) を計算して出力 する。 ここで、 ρ (χ) =ρ' (x) +Pooh93 mo dNにより計算する。 例えば、 p ' (X) が 1次多項式の場合、 p . (x) = p (1) = p ' (1) + ?001193 = 0；! · 1 +Ρ o o h 93mo dNにより計算する。 ここで、 ρ， (1) は ρ ' (X) で Xの代わりに 「1」 入れて計算した値である。
ユーザの端末装置 1に備えたメモリ 1 2から読み出した多項式 ρ' (χ) が η次多項式の場合、 結合器 52は多項式 ρ' (X) と FDH関数 FDHとユー ザが入力したパスワードにより W=FDH (p (x) II I D (U) II I D (S) ) を計算して出力する。 ここで、 p (X) =p ' (x) +P o o h 93mo dN により計算する。 例えば、 p (x) =p ( i ) =p ' ( i ) +P o o h 93m o dNにより計算する。ここで、 p' ( i)は i番目のサーバに対して p' (x) で xの代わりに 「 i」 入れて計算した値である。
マスク演算器 54は、 メモリ 12から読み出した公開鍵 （N, e) と結合器 52から入力された Wと乱数発生器 53においてランダムに発生させた乱数 T (TeZN*) とから Zを、 Z = Te · Wmo dNにより計算する。 通信処理 部 5.5は Zをサーバ 2へ送信し、 サーバ 2から V 2を受信する。
続いて認証結果判断部 56は、乱数発生器 53から出力された Tを入力とし て、 HASH ( 0 1 II T II I D (U) II I D (S) ) を計算してサーバ 2から 受信した V2と比較する。ここで、 HASHの代わりに MACを使ってもよい。 認証結果判断部 56において V2と HASH(01 II T II I D (U) II I D(S)) がー致しない場合、 認証結果判断部 56は、 エラ一発生器 57に対して、 一致 しないことを通知する。 これを受けて、 エラ一発生器 57はエラーを発生して 処理を中断する。 一方、 認証結果判断部 56において V2と HASH (0 1 II T il I D (U) II I D (S) ) がー致した場合はサーバ 2が正当な装置として 認証して、 検証子生成器 58は、 Vi HASH ( 00 II T II I D (U) II I D (S) ) により検証子 を計算してサーバ 2へ送信する。 同時に、 セッシ ョン鍵生成器 59は、 SK = HASH (1 1 II T II I D (U) II I D (S) ) によりセッション鍵 SKを生成する。
(2) 多項式と FDH関数を利用した場合 （その 2)
次に、 多項式と FDH関数を利用した場合 （その 2) の端末装置 1の動作を 説明する。
まず、 ユーザの端末装置 1に備えたメモリ 12から記憶された多項式と FD H関数 P' = (ρ' (X) ， FDH) を読み出す。 結合器 52はメモリ 12か ら読み出した多項式 p' (X) と FDH関数 FDHとユーザが入力したパスヮ ードにより W=FDH (p (X) II I D (U) || I D (S) ) を計算して出力 する。 ここで、 p (x) - ' (x) +FDH (P o oh 93 II I D (U) il I D (S) ) mo dNにより計算する。 例えば、 p' (x) が.1次多項式の場 合、 p (x) =p (1) =ρ' (1) +FDH (P o o h 93 II I D (U) II I D (S) ) = 1 - 1 +FDH (P o o h 93 II I D (U) II I D (S) ) mo d'Nにより計算する。 ここで、 p， （1)は p， （x)で xの代わりに「1」 入れて計算した値である。
ユーザの端末装置 1に備えたメモリ 1 2から読み出した多項式 p' (x) が n次多項式の場合、 結合器 52は多項式 p' (x) と FDH関数 FDHとユー ザが入力したパスワードにより W=FDH (p (X) II I D (U) II I D (S) ) を計算して出力する。 ここで、 p (X) =p ' (X) +FDH (P o o h 93 II I D (U) II I D (S) ) mo dNにより計算する。 例えば、 p (x) =p ( i ) =p ' ( i ) +FDH (P o o h 93 II I D (U) II I D (S) ) mo dNにより計算する。 ここで、 p' ( i ) は i番目のサーバに対して p' (x) で xの代わりに 「 i」 入れて計算した値である。
マスク演算器 54は、 メモリ 12から読み出した公開鍵 （N, e) と結合器 52から入力された Wと乱数発生器 5 3においてランダムに発生させた乱数 T (TeZN*) とから Zを、 Z=Te · Wmo dNにより計算する。 通信処理 部 55は Ζ·をサーバ 2へ送信し、 サーバ 2から V2を受信する。
続いて認証結果判断部 56は、 乱数発生器 5 3から出力された Tを入力とし て、 HASH (0 1 II T II I D (U) II I D (S) ) を計算してサーバ 2から 受信した V2と比較する。ここで、 HASHの代わりに MACを使ってもよい。 認証結果判断部 56において V2と HASH (0 1 II T II I D (U) II I D (S)) がー致しない場合、 認証結果判断部 56は、 エラ一発生器 57に対して、 一致 しないことを通知する。 これを受けて、 エラー発生器 57はエラーを発生して 処理を中断する。 一方、 認証結果判断部 56.において V2と HASH (0 1 II T il I D (U) II I D (S) ) がー致した場合はサーバ 2が正当な装置として 認証して、 検証子生成器 58は、 Vi-HASH (0 0 II T II I D (U) II I D (S) ) により検証子 を計算してサーバ 2へ送信する。 同時に、 セッシ ヨン鍵生成器 59は、 SK = HASH ( 1 1 II T II I D (U) II I D (S) ) によりセッション鍵 SKを生成する。 (3) FDH関数を利用した場合
次に、 FDH関数を利用した場合の端末装置 1の動作を説明する。
まず、 ユーザの端末装置 1に備えたメモリ 12から記憶された秘密値と FD H関数 P' = (S, FDH) を読み出す。 結合器 52はメモリ 12から読み出 した秘密値 Sと FDH関数 FDHとユーザが入力したパスヮードにより Wを 計算して出力する。 例えば、 Wは、 W=FDH (S II P o o h 93 II I D (U) II I D (S) ) により計算する。 マスク演算器 54は、 メモリ 12から読み出 した公開鍵 （N， e) と結合器 52から入力された Wと乱数発生器 53におい てランダムに発生させた乱数 T (TG ZN*) とから Zを、 Z=Te * Wmo d Nにより計算する。 通信処理部 55は Zをサーバ 2へ送信し、 サーバ 2から V 2を受信.する。
続いて認証結果判断部 56は、 乱数発生器 53から出力された Tを入力とし て、 HASH (01 II T II I D (U) II I D ( S ) ) を計算してサーバ 2から 受信した V2と比較する。ここで、 HASHの代わりに MACを使ってもよい。 認証結果判断部 56において V2と HASH (0 1 II T II I D(U) II I D(S)) がー致しない場合、 認証結果判断部 56は、 エラー発生器 57に対して、 一致 しないことを通知する。 これを受けて、 エラ一発生器 57はエラ一を発生して 処理を中断する。 一方、 認証結果判断部 56において V2と HASH (0 1 II T il I D (U) II I D (S) ) がー致した場合はサーバ 2が正当な装置として 認証して、 検証子生成器 58は、 Vi-HASH (00 II T II I D (U) II I D (S) ) により検証子 を計算してサーバ 2へ送信する。 同時に、 セッシ ョン鍵生成器 59は、 SK = HASH (1 1 II T II I D (U) II I D (S) ) によりセッション鍵 SKを生成する。
<サーバの動作 >
(1) 多項式と FDH関数を利用した場合 （その 1) 、 多項式と FDH関数を 利用した場合 （その 2) サーバ 2は、 前述レた多項式と FDH関数を利用した場合 （その 1) 、 多項 式と FDH関数を利用した場合 （その 2) に関わらず次のように動作する。 まず、 サ一パ 2に備えたメモリ 41から保存されたユーザ I Dとパスワード の認証データ Hを読み出す。 マス夕一鍵生成器 62はメモリ 41から読み出し た Hと秘密鍵 （N, d) と端末装置 1から受信した Zを入力として Tを、 T = (ZZW) dmo dNにより計算して出力する。 ここで、 Wは、 W=FDH (H II ID (U) II ID (S) ) により計算する。 検証子生成器 63は、 マスター 鍵生成器 62から入力された tから検証子 V2を、 V2 = HASH (01 II T II I (U) II ID (S) ) により計算する。 通信処理部 64は、 計算して得ら れた V 2を端末装置 1へ送信し、 端末装置 1から受信した V iを認証結果判断部 65へ出力する。
続いて認証結果判断部 65は、 マス夕一鍵生成器 62から出力された Tを入 力として、 HASH (00 II T II I D (U) II I D (S) ) を計算して端末装 置 1から受信した と比較する。 ここで、 HASHの代わりに MACを使つ てもよい。 認証結果判断部 65において と HASH (00 II T il ID (U)
II ID (S) ) がー致しない場合、 認証結果判断部 65は、 エラー発生器 66 に対して、 一致しないことを通知する。 これを受けて、 エラー発生器 66はェ ラーを発生して処理を中断する。 一方、 認証結果判断部 65において と H ASH (00 II T il ID (U) II ID (S) ) がー致した塲合は端末装置 1が 正当な装置として認証して、 セッション鍵生成器 67は、 SK = HASH (1
I II T II I D (U) II ID (S) ). によりセッション鍵 S Kを生成する。
(2) FDH関数を利用した場合
次に、 FDH関数を利用した場合のサーバ 2の動作を説明する。
まず、 サーバ 2に備えたメモリ 41から保存されたユーザ I Dとパスワード の認証データ Ηを読み出す。 マスター鍵生成器 62はメモリ 41から読み出し た Ηと秘密鍵 （Ν, d) と端末装置 1から受信した Zを入力として Tを、 T = (Z/W) dmo dNにより計算して出力する。 ここで、 Wは、 W=Hである。 検証子生成器 63は、 マスター鍵生成器 62から入力された Tから検証子 V2 を、 V2 = HASH (01 II T II I D (U) II I D (S) ) により計算する。 通信処理部 64は、 計算して得られた V2を端末装置 1へ送信し、 端末装置 1 から受信した を認証結果判断部 65へ出力する。
続いて認証結果判断部 65は、 マスター鍵生成器 62から出力された Tを入 力として、 HASH ( 00 II T II I D (U) II I D (S) ) を計算して端末装 置 1から受信した と比較する。 ここで、 HASHの代わりに MACを使つ てもよい。 認証結果判断部 65において と HASH (00 II T II I D (U)
II I D (S) ) がー致しない場合、 認証結果判断部 65は、 エラー発生器 66 に対して、 一致しないことを通知する。 これを受けて、 エラー発生器 66はェ ラーを発生して処理を中断する。 一方、 認証結果判断部 65において と H ASH (00 II T il I D (U) II I D (S) ) がー致した場合は端末装置 1が 正当な装置として認証して、 セッション鍵生成器 67は、 SK = HASH (1
I II T II I D (U) II I D (S) ) によりセッション鍵 SKを生成する。
<パスワード認証データの更新一 1>
ユーザは、 サーバに対してすでに登録されたパスワード認証データを、 自分 が覚えているパスワードを変えずに、 更新したい時、 自分の端末装置の更新化 を行う。 図 9、 19は、 ユーザの端末装置の更新化処理の構成を示すブロック 図である。 ここでの更新化処理は、 前述した多項式と FDH関数を利用した場 合 （その 1) 、 多項式と FDH関数を利用した場合 （その 2) とマスター鍵を 利用する場合に適用することが可能である。 また、 この更新化処理によりサー バに対する r e p 1 a y攻撃を防ぐことが可能である。
<端末装置の更新化処理 >
(1) 多項式と FDH関数を利用した場合 （その 1) 、 多項式と FDH関数を 利用した場合 （その 2)
初めに、 図 9を参照して、 多項式と FDH関数を利用した場合 （その 1) 、 多項式と FDH関数を利用した場合 （その 2) の端末装置 1の更新化処理を説 明する。端末装置 1は、前述した多項式と F DH関数を利用した場合（その 1 )、 多項式と F D H関数を利用した場合（その 2 )に関わらず次のように動作する。 まず、 多項式発生器 1 3によりランダムに多項式を発生する。 このとき、 登 録したサーバの数が一つだったら Xを変数とする 1次多項式 （ t ' (χ) = β ！ · xmo dN) を、 サーバの数が n個だったら n次多項式（ t ' (x) =i3！ · x + jS 2 · χ2+ · · · +jSn · xnmo dN) を発生する。 ここで、 3は ZN* から無作為に選ばれる。 例えば、 一つのサーバの場合、 T' = t ' (X) は、 t ' (X) =/3： · xmo dNとなる。 ここで、 ユーザの端末装置 1に備えた メモリ 1 2から記憶された多項式と FDH関数 P' = (ρ' (x) , FDH) を読み出す。 多項式 t ' (x) と多項式 p' (x) が入力されたら更新値生成 器 14は、 ュ一ザ保存用の更新された多項式 P' とサー^?更新用の値 H' を生 成する。 更新された多項式 P' は、 例えば P' = t ' (χ) +ρ' (χ) =
( 1 + β 1) · xmo dNにより計算できる。 サーバ更新用の値 H' 、 例えば H' = t ' (1) mo dNにより計算できる。 ここで、 t ' (1) は t ' (x) で： xの代わりに 「1」 を入れて計算した値である。
例えば、 登録したサーバの数が nの場合、 更新値生成器 14は、 i番目のサ ーバに対してサーバ更新用の値 H' を生成する。 サーバ更新用の値 H' は、 例 えば H' = t ' ( i ) mo dNにより計算できる。 ここで、 t ' ( i ) は n次 多項式 t (x) で xの代わりに 「 i」 を入れて計算した値である。
サーバ更新用の値 H' はユーザが直接にサーバに渡したり、 郵便で送付した り、 あるいは電話で知らせるなどして、 安全に通知する必要がある。 ユーザの 端末装置の内部にあるメモリ 1 2は更新された多項式 P' = t ' (χ) +ρ'
(x) とメモリ 1 2から読み出した FDH関数 FDHとを一緒に Ρ' = (t '
(χ) +ρ' (χ) , FDH) として記憶して保存する。
(2) マスター鍵を利用する場合
次に、 図 1 9を参照して、 マスター鍵を利用する場合の端末装置 1の更新化 処理の動作を説明する。
まず、 乱数発生器 53によりランダムに乱数 T (TeZN*) を発生する。 こ こで、 ユーザの端末装置 1に備えたメモリ 1 2から記憶された多項式と FDH 関数 P' = (ρ' (x) ， FDH) を読み出す。 乱数 Tと多項式 p' (X) が入力されたら更新値生成器 20は、 ユーザ保存用の更新された多項式 P' を 生成する。 更新された多項式 P' は、 Ρ' =Τ+ρ' (X) mo dNにより計 算できる。 ユーザの端末装置の内部にあるメモリ 12は更新された多項式 P' =T+ p ' (χ)とメモリ 12から読み出した FDH関数 FDHとを一緒に Ρ， = (Τ + ρ' (χ) , FDH) として記憶して保存する。
<サーバの更新化処理 >
(1) 多項式と FDH関数を利用した場合 （その 1) 、 多項式と FDH関数を 利用した場合 （その 2) "
初めに、図 10を参照して、多項式と FDH関数を利用した場合（その 1)、 多項式と FDH関数を利用した場合 （その 2) のサーバ 2の更新化処理の動作 を説明する。 サーバ 2は、 前述した多項式と FDH関数を利用した場合 （その 1) 、 多項式と FDH関数を利用した場合 （その 2) に関わらず次のように動 作する。
まず、 サーバ 2に備えたメモリ 41に保存されたユーザ I Dとパスヮード認 証デー夕 Hを読み出す。 一ザの端末装置から送られたサーバ更新用の値 H ' とメモリ 41から読み出したパスワード認証データ Hが入力されたら更新値 生成器 21は、 サーバ保存用の更新されたパスワード認証デ一夕 Hを生成する。 更新されたパスワード認証データ Hは、 例えば H= p (1) + t ' (1) m o dNにより計算できる。 サーバの内部にあるメモリ 41は更新されたパスヮ 一ド認証データ Hを記憶して保存する。
(2) マスター鍵を利用する場合
次に、 図 20を参照して、 マスター鍵を利用する場合のサ一パ 2の更新化処 理の動作を説明する。
まず、 マスタ一鍵生成器 62によりマスタ一鍵 Tを生成する。 ここで、 サー パ 2に備えたメモリ 41から保存されたユーザ I Dとパスワード認証データ Hを読み出す。 マスター鍵 Tとメモリ 41から読み出したパスワード認証デー タ Hが入力されたら更新値生成器 27は、 サーバ保存用の更新されたパスヮー ド認証デ一夕 Hを生成する。 更新されたパスワード認証データ Hは、 H= p (1) +Tmo dNにより計算できる。 サーバの内部にあるメモリ 41は更新 されたパスワード認証デー夕 Hを記憶して保存する。
<パスヮ一ド認証データの更新一 2 >
ユーザは、 サーバに対してすでに登録されたパスワード認証データを、 自分 が覚えているパスワードを変えながら、 更新したい時、 自分の端末装置の更新 化処理を行う。 図 1 1は、 ユーザの端末装置の更新化処理の構成を示すブロッ ク図である。更新化処理は、秘密値発生器 15による秘^値 S'とユーザの新し いパスワード PW'とユーザの端末装置 1に備えたメモリ 12から記憶された P'が入力されると、 パスワード認証データ更新器 16によって、サ一パ更新用 のパスワード認証データ H'と、 ユーザ保存用の更新された P'が生成され、 H' は、 サーバ 2に受け渡され、 更新された P'は、 メモリ 12へ保存する。 ここで の更新化処理は、 前述した F DH関数を利用した場合に適用することが可能で ある。 また、 この更新化処理によりサーバに対する r e p 1 ay攻撃を防ぐこ とが可能である。 そして、 多項式と FDH関数を利用した塲合 （その 1) , 多 項式と FDH関数を利用した場合 （その 2) も同じように初期化処理と同様の 動作を用いて適用することが可能なため、 ここでは詳細な説明を省略する。 ぐ端末装置の更新化処理 >
(1) F.DH関数を利用した場合
図 1 1を参照して、 FDH関数を利用した場合の端末装置 1の更新化処理の 動作を説明する。
まず、 秘密値発生器 1 5によりランダムに ¾密値 S'を発生する。 ここで、 ュ 一ザの端末装置 1に備えたメモリ 12から記憶された P'= (S， FDH) を読 み出す。 ユーザが覚えている新しいパスワード （PW，） と FDH関数 FDHと 秘密値 S'が入力されたらパスヮ一ド認証データ更新器 16は、ユーザ保存用の 更新された P'とサーバ更新用のパスワード認証データ H'を生成する。 サーバ 更新用のパスワード認証データ H，は、 例えば H，=FDH (S' ll PW' ll I D (U) II I D (S) ) により計算できる。 ここで、 I D (U) と I D (S) は それぞれユーザとサーバの I Dを表す。サーバ更新用のパスワード認証デ一夕 H'はユーザが直接にサーバ 2に渡したり、 郵便で送付したり、 あるいは電話で 知らせるなどして、 安全に通知する必要がある。 ユーザの端末装置 1の内部に あるメモリ 12は更新された P，= (S'， FDH) を記憶して保存する。
<サーバの更新化処理 >
(1.) FDH関数を利用した場合
図 12を参照して、 FDH関数を利用した場合のサ一バ 2の更新化処理の動 作を説明する。
まず、 サ一バ 2に備えたメモリ 41に保存されたユーザ I Dとパスワード認 証データ Hを読み出す。ユーザの端末装置 1から送られたサーバ更新用のパス ワード認証データ H' とメモリ 41から読み出したパスワード認証データ Hが 入力されたらパスワード認証データ更新器 22は、 サーバ保存用のパスワード 認証データ Hをユーザの端末装置 1から送られた H' に更新する。 サーバの内 部にあるメモリ 41は更新されたパスワード認証データ H = H， を記憶して保 存する。 このように、 多項式を利用することにより、 不正利用しようと思っている者 が他人の端末装置を持っていたと.してもユーザのパスヮードは情報理論的に 安全である。 また、 サーバ内に侵入して保存されている情報を得たとしてもュ —ザのパスワードは情報理論的に安全である。 また、 ハッシュ関数と擬似乱数 発生器と FDH関数を利用する場合には、 不正利用しようと思っている者にと つてユーザのパスワードは計算量的に安全である。 次に、 前述した技術を応用した装置について説明する。
<端末に分散デ一夕を保存しない場合の遠隔分散保存装置におけるデータ保 存処理 > 次に、 図 21を参照して、 端末に分散データを保存しない場合の遠隔分散保 存装置におけるデータ保存処理について説明する。 図 21は、 端末に分散デー タを保存しない場合の遠隔分散保存装置 5の構成を示すブロック図である。 ユーザは分散保存したいデータ DATAを自分の端末装置 21で処理し、 n 台のサーバに保存するデータ S' 1， …， S'nへと分割する。 分割データ S' iはデータの I Dである D I Dと共にユーザの端末装置 21によりサーバの 認証装置と共有された鍵 SK iを用いて作成された安全な通信路を使用可能 な通信器 52によってサーバ I D iへと送られ保存される。 同様の方法により、 保存データの一覧情報を分割し、 サーバに保存することも可能である。 また、 ユーザの端末装置 （認証データ更新モード） を適当な間隔 （記憶情報がオフラ イン全数探索で求まる間隔より短い間隔で、 例えば、 認証を行う度や 2， 3日 に 1回など） で動作させ、 P'と各サーバに記録されている Hを更新する情報 UP', UH1， …， UHnを生成させ、 それらを更新する。
これにより、 サーバに保存されるデータと認証用データをともに、 漏洩と破 損に強くなるように構成することができる。漏洩と破損への耐性は（ n , D S， LS I, L S 2) の 4組のパラメータで表現できる。 DS, LS I, LS 2は ともに （漏洩や破損の起こる） エンティティの組み合わせの集合であり、 DS はデータの破損に対する耐性、 LS I, LS 2は漏洩に対する耐性を表現して いる。 DSには、 壊れても構わないエンティティの組み合わせが記述される。 災害などの理由によりローカルバックアップを含め保存しているデータが完 全に利用できなくなったとしても、.利用者が自分のデータを復元できる範囲の 破損組み合わせが記述される。 LS Iには、 記録情報が漏れても構わないェン ティティの組み合わせが記述される。 保存データが漏洩したとしても、 攻撃者 が利用者のデータを復元することが困難な範囲の漏洩組み合わせとする。 L S 2には、 記録情報が漏れたとしても、 後 何らかの対抗策がとれる範囲のェン ティティの組み合わせが記述される。 保存デ一夕が漏洩したとしても、 攻撃者 が利用者のデータを復元することを困難にする対抗策の存在する範囲の漏洩 組み合わせとする。
また、 ユーザの記憶情報はオフラインで全数探索できる程少量であると仮定 すると、 従来の漏洩に弱い認証方式を使う場合、 攻撃者は漏洩情報と通信路上 で得た情報を使って利用者の記憶情報を全数探索でき、 結果として、 利用者に 成りすまして遠隔分散保存されているデータをすベて入手できる。 つまり、 L S 1にサーバ {S} とユーザの所有物 {U} をそれぞれ含めることはできなか つた。 これに対して、 漏洩に強い認証方式を使うことで LS 1にサーバ {S} とユーザの所有物 {U} をそれぞれ含めることが可能となる。 漏洩に強い認証 方式を含む全ての遠隔認証方式はユーザの所有物 {U} とサーバ {S} の両方 から情報が漏洩すると利用者の記憶情報を全数探索でき、 結果として、 利用者 に成りすまして遠隔分散保存されているデータをすベて入手できる。 よって、 LS 2にユーザの所有物 {U} とサーバ {S} の組み合わせ {US} を入れる ことはできなかった。 これに対して、 P'と HI, …， Hnを更新することで L S 2にユーザの所有物とサーバの組み合わせを入れることが可能となる。 次に、図 22を参照して、図 21に示すデータ分散器 5 1の構成を説明する。 調整器 51 1は入力されたパラメータ n, kを秘密分散器 5 12に渡す。 秘密 分散器 512は入力されたパラメータ n, kに従い保存データ DATAを（k， n) 分散データ S I， S 2 , …， Snに変換する。 次に、 調整器 51 1はデー 夕の I Dである D I Dからデータ伸長器 51 3の入力 Xを生成しデ一タ伸長 器 513へ渡す。 データ伸長器 5 13は対応する情報 Hを出力し、 それを暗号 器 514に渡す。 ここでの Hはオフラインでの全数探索に強い長さのものを利 用する。データ伸長器 513が短い Hを出力する場合には異なる Xを複数デー 夕伸長器 513に渡し、 得られた複数の Hを利用する。 暗号器 514は、 Hを 鍵として n— k+ 1個以上の分散データを暗号化する。 また、 S l， ···， Sn 一 k+ 1のそれぞれに改ざん検出符号を付けてもよい。 喑号器の出力が S' 1， …， S' nであり、 D I D、 I D 1 , I D 2,. ···, I Dnと共にデ一夕分割器 51の出力となる。
なお、 （k, n) 分散データとは、 元データが n個に分割されたデータであ り、 かつ、 そのどの k個からでも元のデータを復元できるが k未満からでは復 元できないような性質を有するデータである。 （k， n) 分散データ以外にも 任意のアクセス構造を持った分散デ一夕を利用することが可能である。 また、 秘密分散器は多項式や行列を使つた情報量的に安全な分散方式以外に、 暗号化 を使うことで保存データサイズを少なくできる計算量的に安全な分散方式を 用いることが可能である。
このデータ分割器 51は、 （n， D S, LS I, L S 2) = (n， {CSn -k} , {UC， CSn} , {UC S k— 1 } ) を実現している。 {CS} は ケライアントおよびサーバの記録情報およびその部分情報を意味し、 {S n} は n台のサーバの全記録情報およびその部分情報を意味する。 {C， S}は「ク ライ.アントに記録されている全情報およびその部分情報あるいはサーバに記 録されている全情報およびその部分情報」 を意味する。 UCS k— 1} から の漏洩は認証情報のアップデ一ト処理で対処できる。攻撃者が {UC S k- 1 } から記憶情報を求める間に認証情報がァップデートされれば攻撃者は利用者 のデータを求めることができなくなる。 ユーザの所有物 {U} の紛失 （Ρ'の 紛失） に対しては、 {U} に記録してあるデータをアップデートするたびにそ のコピーをローカルに作成することで解決できる。災害などでローカルコピー もろとも {U} が破損する危険性に対しては、 {U} に記録してあるデ一夕を 秘密分散器で （k'， n) 分散データで分割して各サーバにも保存しておくこ とで解決できる。 k'>=kの場合、 （n, D S, LS I, L S 2) = (n， {UCSn-k', CSn-k} , {UC, C S k' - 1 } , {UC S k - 1 } ) を実現しており、 k'<kの場合、 （n， DS, LS I, L S 2) = (n， {U CSn-k, CSn-k} , {UC, CS k'— 1 } ， {UC S k- 1, CS k - 1 } .) を実現している。
さらに、 ユーザの所有物に記録してあるデ一夕と記憶情報のすべて、 あるい はそれらの一部も秘密分散器で （k'， n) 分散データに分割して各サーバに も保存しておけば、 ユーザが仮に記憶情報を忘れたとしてもオフライン解析に より （所有物の記録情報と） 記憶情報を復元できる。 その際、 1) すべてを分 散する場合はオフライン解析を省くことができ、 2) —部を分散する場合はそ の量に応じてオフライン解析の計算量を削減することができる。 この機能によ り、 ユーザは第三者にデータを復号する権限を与える際に、 データを復元する 容易さ （攻撃者が {CS k'} を得た場合のデータ復元の容易さとも同じ） を 調整できるようになる。
<端末にデータを保存しない場合の遠隔分散保存装置におけるデータ復元処 理>
次に、 図 23を参照して、 端末にデータを保存しない場合の遠隔分散保存装 置におけるデータ復元処理について説明する。 図 23は、 端末にデータを保存 しない場合の遠隔分散保存装置 5の構成を示すプロック図である。
データ復元器 54は、 入力された D I Dに対応する分散データ S' 1, …， S' nの内少なくとも k個を通信器 52を介してサーバ I D 1 , I D 2， '··， I Dnから受け取る。 データ復元器 54は S' 1, …， S' nの内少なくとも k 個を処理して DATAを復元する。 同様の方法で、 保存データの一覧を復元す ることも可能である。 また、 ユーザの端末装置 21 (認証データ更新モード） を適当な間隔 （記憶情報がオフライン全数探索で求まる間隔より短い間隔で、 例えば、 認証を行う度や 2， 3日に 1回など） で動作させ、 P'と各サーバに 記録されている Hを更新する情報 UP', UH 1, ···, UHnを生成させ、 そ れらを更新する。 次に、図 24を参照して、図 23に示すデータ復元器 54の構成を説明する。 調整器 541は、 入力された n台のサーバ I D、 I D 1 , I D 2, ···, I Dn と D I Dを出力する。 また、 調整器 541は D I Dからデータ伸長器 542の 入力 Xを生成しデータ伸長器 542へ渡す。 データ伸長器 542は対応する情 報 Hを出力し、 それを暗号器 543に渡す。 暗号器 543は得られた分散デ一 夕 S' 1， S' 2， ···， S' nの内、 暗号化されているものを復号し S 1， S 2, …， S nを秘密分散復元器に渡す。 秘密分散復元器 544は渡された分散デー 夕から DAT Aを復元する。 なお、 改ざん検出を行い改ざんの行われていない 分散データのみを k個渡してもよい。
<端末にも分散データを保存する場合の遠隔分散保存装置におけるデータ保 存処理 >
次に、 図 25を参照して、 端末にも分散データを保存する場合の遠隔分散保 存装置におけるデータ保存処理について説明する。 図 25は、 端末にも分散デ 一夕を保存する場合の遠隔分散保存装置 5の構成を示すプロック図である。 こ こでは、 図 2 1に示す構成を異なる部分のみを説明する。
ユーザは分散保存したいデータ DATAを自分の端末装置 21で処理し、 手 元に残すデータ DLと n台のサーバに保存するデータ RS' 1， ···， RS' nへ と分割する。 DLは手元の記録装置 55に保存され、 分割データ RS' lはデ ータの I Dである D I Dと共にユーザの端末装置 2 1によりサーバの認証装 置と共有された鍵 SK iを用いて作成された安全な通信路を通ってサーバ I D iへと送られ保存される。 同様の方法で、 保存データの一覧情報を分割し、 サーバに保存することも可能である。
このように、 分散データの一部を自分の端末装置 2 1に置くことで、 サーバ との通信量を削減できる。破損したサーバの組み合わせに応じて通信量が変わ る方式と変わらない方式が可能であるが、 変わる方法の場合 n台のサーバ全体 の記憶領域を削減できる。 なお、 漏洩と破損に対する耐性は、 " '—夕を手元に 置かない場合と同等に保つことができる。 次に、図 26を参照して、図 25に示すデータ分割器 5 1の構成を説明する。 ここでは、 図 22に示す構成と異なる部分のみを説明する。 暗号器 5 1 5は乱 数生成器 5 1 6から乱数 Rを受け取り、 これを鍵として保存データを暗号化し、 それを DLとして出力する。 調整器 5 1 1は入力されたパラメ一夕 n, kを秘 密分散器 5 12に渡す。 秘密分散器 512は入力されたパラメータ n， kに従 い Rを （k， n) 分散デ一夕 RS I, RS 2, ···, RS nに変換する。 次に、 調整器 5 1 1はデータの I Dである D I Dからデータ伸長器 51 3の入力 x を生成しデータ伸長器 513へ渡す。 データ伸長器 5 13は対応する情報 Hを 出力し、 これを鍵として暗号器 514に渡す。 ここでの Hはオフラインでの全 数探索に強い長さのものを利用する。 データ伸長器 5 13が短い Hを出力する 場合には異なる: Xを複数のデータ伸長器 5 13に渡し、 得られた複数の Hを利 用する。 暗号器 5 14は、 Hを鍵として n— k+ 1個以上の分散データを暗号 化する。 また、 RS 1， ···， RSn— k+ 1のそれぞれに改ざん検出符号を付 けてもよい。 暗号器の出力が RS' l, …， RS' nである。
なお、 （k， n) 分散デ一夕以外にも任意のアクセス構造を持った分散デー 夕を利用することが可能である。 また、 秘密分散器 512には多項式や行列を 使った情報量的に安全な分散方式や、 暗号を使う計算量的に安全な分散方式を 用いることが可能であるが、 Rのサイズが小さい場合には、 計算量的に安全な 分散方式を用いることによるサイズの削減効果は小さいため、 情報量的に安全 な分散方式を用いた方がよい。
<端末にも分散データを保存する場合の遠隔分散保存装置におけるデータ復 元処理 >
次に、 図 27を参照して、 端末にも分散データを保存する場合の遠隔分散保 存装置におけるデータ復元処理について説明する。 図 27は、 端末にも分散デ —夕を保存する場合の遠隔分散保存装置 5の構成を示すブロック図である。 こ こでは 図 23に示す構成と異なる部分のみを説明する。
データ復元器 54は入ガされた D I Dに対応する分散デ一夕 RS' 1, ···, RS' nの内少なくとも k個を通信器を介してサーバ I D 1， I D 2, ···, I Dnから受け取る。 データ復元器 54は RS' 1， …， RS' nの内少なくとも k個を処理して DATAを復元する。 同様の方法で、 保存データの一覧を復元 することも可能である。 . 次に、図 28を参照して、図 27に示すデータ復元器 54の構成を説明する。 ここでは、 図 24に示す構成と異なる部分のみを説明する。 調整器 541は、 D I Dからデータ伸長器 542の入力 Xを生成しデータ伸長器 542へ渡す。 データ伸長器 542は対応する情報 Hを出力し、 それを復号器 543に渡す。 復号器 543は得られた分散データ RS' 1， RS' 2， …， RS' nの内、 暗 号化されているものを復号し RS 1， ···， R S nを秘密分散復元器 544に渡 す。秘密分散復元器 544は渡された分散データから DATAを復号器 545 によって復元する。 また、 改ざん検出を行い改ざんの行われていない分散デー 夕を k個渡してもよい。 なお、 図面に示す各処理部の機能を実現するためのプログラムをコンビユー タ読み取り可能な記録媒体に記録して、 この記録媒体に記録されたプログラム をコンピュータシステムに読み込ませ、 実行することにより認証処理、 鍵交換 処理を行ってもよい。 なお、 ここでいう 「コンピュータシステム」 とは、 O S や周辺機器等のハードウェアを含むものとする。 また、 「コンピュータシステ ム J .は、 ホームページ提供環境 （あるいは表示環境） を備えた WWWシステム も含むものとする。 また、 「コンピュータ読み取り可能な記録媒体」 とは、 フ レキシブルディスク、 光磁気ディスク、 R O M、 C D— R O M等の可搬媒体、 コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをい う。 さらに 「コンピュータ読み取り可能な記録媒体」 とは、 インターネット等 のネットワークや電話回線等の通信回線を介してプログラムが送信された場 合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ (R AM) のように、 一定時間プログラムを保持しているものも含むものとす る。 また、 上記プログラムは、 このプログラムを記憶装置等に格納したコンビュ 一夕システムから、 伝送媒体を介して、 あるいは、 伝送媒体中の伝送波により 他のコンピュータシステムに伝送されてもよい。 ここで、 プログラムを伝送す る 「伝送媒体」 は、 インターネット等のネットワーク （通信網） や電話回線等 の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。 また、 上記プログラムは、 前述した機能の一部を実現するためのものであって も良い。 さらに、 前述した機能をコンピュータシステムにすでに記録されてい るプログラムとの組み合わせで実現できるもの、 いわゆる差分ファイル （差分 プログラム） であっても良い。 産業上の利用の可能性 ■ この発明によれば、 端末装置側あるいはサーバ側から装置内に保存している 情報が漏れたとしてもオフライン解析によってパスワードを見つけだすこと ができないため、 サーバの不正利用を防止することが可能になるという効果が 得られる。 また、 装置内に保存されている情報を盗まれないようにするための 耐タンパ一性のモジュールを使用する必要がないため、 装置構成を簡単にする ことができる。 また、 公開鍵暗号システムのように複雑な鍵管理処理を行う必 要がないため、 計算処理を向上させることができるとともに、 処理内容.を簡単 にすることができる。 また、 複数のサ一パに対しても拡張することができる。 さらに、 各サーバと端末装置とでユーザ I Dを同期させながら動的に変化さ せることで、 盗聴者がユーザ I Dを用いてユーザのプライバシ情報を紐付けす ることを防止することができる。

Claims

請 求 の 範 囲
1 . 端末装置とサーバ間において相互に認証を行う認証システムであって、 刖 Bci端末装置は、
ユーザ保存用の認証情報 P ' を予め記憶しておく記憶手段と、
前記記憶手段から読み出した認証情報 P ' と認証時に入力されたパスヮード を入力として所定の計算式により値 Pを求める結合手段と、
前記値 Pと内部において発生させた乱数を入力として^ f定の計算式により 値 Y 1を求め、 前記サーバへ送信するマスク演算手段と、
前記値 Pと内部において発生させた乱数と前記サーバから受信した値 Y 2 を入力として所定の計算式により値 MKを求めるマス夕一鍵生成手段と を備え、
前記サーバは、
サーバ登録用のパスワード認証データ Hを予め記憶しておく記憶手段と、 前記記憶手段から読み出したパスヮード認証データ Hと内部において発生 させた乱数を入力として所定の計算式により値 Y 2を求め、 前記端末装置へ送 信するマスク演算手段と、
前記パスワード認証データ Hと内部において発生させた乱数と前記端末装 置から受信した値 Y 1を入力として所定の計算式により値 M Kを求めるマス 夕一鍵生成手段と
を備えたことを特徴とする認証システム。
2 . ユーザが予め決定したパスワードに基づいて、 前記パスワード認証デー 夕 Hと前記認証情報 P ' を求めるデータ伸長手段をさらに備えたことを特徴 とする請求項 1に記載の認証システム。
3 . 前記端末装置は、
前記値 MKを入力として所定の計算式により値 V 1を求め、 サーバへ送信す るとともに、 前記サーバから受信した値 V 2と前記値 MKを入力として所定の 計算式による値 V 2と比較照合し、 一致した場合にサーバを認証する認証結果 判断手段をさらに備え、
前記サーバは、
前記値 MKを入力として所定の計算式により値 V 2を求め、 端末装置へ送信 するとともに、 前記端末装置から受信した値 V 1と前記値 MKを入力として所 定の計算式による値 V 1と比較照合し、 一致した場合に端末装置を認証する認 証結果判断手段をさらに備えた
ことを特徴とする請求項 1または 2に記載の認証システム。
4 . . 前記端末装置及びサーバは、 相互の認証が行われた場合に、 セッション 鍵を生成するセッション鍵生成手段をそれぞれに備えたことを特徴とする請 求項 3に記載の認証システム。
5 . 前記認証情報 P ' は、 多項式であることを特徴とする請求項 1から 4の いずれかに記載の認証システム。
6 . 前記認証情報 P ' は、 多項式とハッシュ関数であることを特徴とする請 求項 1から 4のいずれかに記載の認証システム。
7 . 前記認証情報 P ' は、 ハッシュ関数であることを特徵とする請求項 1か ら 4のいずれかに記載の認証システム。
8 . 前記認証情報 P ' は、 疑似乱数関数であることを特徴とする請求項 1か ら 4のいずれかに記載の認証システム。
9 . 端末装置とサーバ間において相互に認証を行う認証システムにおける端 末装置上で動作する認証プログラムであって、
ユーザ保存用の認証情報 P ' を予め記憶しておく記憶処理と、
前記記憶しておいた認証情報 P ' と認証時に入力されたパスワードを入力と して所定の計算式により値 Pを求める結合処理と、 前記値 Pと内部において発生させた乱数を入力として所定の計算式により 値 Y 1を求め、 前記サーバへ送信するマスク演算処理と、
前記値 Pと内部において発生させた乱数と前記サーバから受信した値 Y 2 を入力として所定の計算式により値 MKを求めるマスター鍵生成処理と をコンピュータに行わせることを特徴とする認証プログラム。
1 0 . ユーザが予め決定したパスワードに基づいて、 前記認証情報 P ' を求 めるデータ伸長処理をさらにコンピュータに行わせることを特徴とする請求 項 9に記載の認証プログラム。
1 1 . 前記値 MKを入力として所定の計算式により値 V 1を求め、 サーバへ 送信するとともに、 前記サーバから受信した値 V 2と前記値 MKを入力として 所定の計算式による値 V 2と比較照合し、 一致した場合にサーバを認証する認 証結果判断処理をさらにコンピュー夕に行わせることを特徴とする請求項 9 または 1 0に記載の認証プログラム。
1 2 . 端末装置とサーバ間において相互に認証を行う認証システムにおける サーバ上で動作する認証プログラムであって、
サーバ登録用のパスワード認証データ Hを予め記憶しておく記憶処理と、 前記記憶しておいたパスヮ一ド認証データ Hと内部において発生させた乱 数を入力として所定の計算式により値 Y 2を求め、 前記端末装置へ送信するマ スク演算処理と、
前記パスヮード認証データ Hと内部において発生させた乱数と前記端末装 置から受信した値 Y 1を入力として所定の計算式により値 M Kを求めるマス 夕一鍵生成処理と
をコンピュータに行わせることを特徴とする認証プログラム。
1 3 . ユーザが予め決定したパスワードに基づいて、 前記パスワード認証デ —夕 Hを求めるデータ伸長処理をさらにコンピュータに行わせることを特徴 とする請求項 12に記載の認証プログラム
14. 前記値 MKを入力として所定の計算式により値 V 2を求め、 端末装置 へ送信するとともに、 前記端末装置から受信した値 V 1と前記値 MKを入力と して所定の計算式による値 V 1と比較照合し、 一致した場合に端末装置を認証 する認証結果判断処理をさらにコンピュータに行わせることを特徴とする請 求項 12または 13に記載の認証プログラム。
15. 端末装置及びサーバにおいて相互の認証が行われた塲合に、 セッショ ン鍵を生成するセッション鍵生成処理をそれぞれに備えたことを特徴とする 請求項 1 1または 14に記載の認証プログラム。
16. 前記認証情報 P' は、 多項式であることを特徴とする請求項 9から 1 5のいずれかに記載の認証プログラム。
17. 前記認証情報 P' は、 多項式とハッシュ関数であることを特徴とする 請求項 9から 15のいずれかに記載の認証プログラム。
18. 前記認証情報 P' は、 ハッシュ関数であることを特徴とする請求項 9 から 15のいずれかに記載の認証プログラム。
19. .前記認証情報 P' は、 疑似乱数関数であることを特徴とする請求項 9 から 1 5のいずれかに記載の認証プログラム。
20. 前記端末装置は、
更新情報 T' を発生させる発生手段と、
前記記憶手段に記憶されている認証情報 P' と前記更新情報 T' を入力し、 所定の計算式によってサーバ更新用のパスヮード認証データ H' と新たな認証 情報 P， を求め、 サーバ更新用のパスワード認証データ H， を前記サーバへ送 信するとともに、 新たな認証情報 P， を前記記憶手段に記憶する更新情報生成 手段と
を備え、
前記サーバは、
前記端末装置から送信されたサーバ更新用のパスワード認証デー夕 H ' と前 記記憶手段に記憶されたパスワード認証データ Hを入力し、 所定の計算式によ つて新たなパスワード認証データ Hを求めて前記記憶手段に記憶されているパ スワード認証デー夕 Hを更新する更新情報生成手段を備えた
^とを特徴とする請求項 2に記載の認証システム。
2 1 . 前記端末装置は、
秘密情報 S ' を発生させる発生手段と、
前記記憶手段に記憶されている認証情報 P ' と前記秘密情報 S ' と新しいパ スワードを入力し、 所定の計算式によつてサーバ更新用のパスヮード認証デ一 夕 H ' と新たな認証情報 P ' を求め、サーバ更新用のパスワード認証データ H ' を前記サーバへ送信するとともに、 新たな認証情報 P ' を前記記憶手段に記憶 する更新情報生成手段と
を備え、 ·
前記サーバは、
前記端末装置から送信されたサーバ更新用のパスワード認証データ H ' と前 記記憶手段に記憶されたパスワード認証データ Hを入力し、 所定の計算式によ つて新たなパスワード認証データ Hを求めて前記記憶手段に記憶されているパ スワード認証データ Hを更新する更新情報生成手段を備えた
ことを特徴とする請求項 2に記載の認証システム。
2 2 . 端末装置とサーバ間において相互に認証を行う認証システムであって、 前記端末装置は、
ユーザ保存用の認証情報 P ' と R S A公開鍵 （N, e ) を予め記憶しておく 記憶手段と、 前記記憶手段から読み出した認証情報 P' と認証時に入力されたパスヮ一ド を入力として所定の計算式により値 Wを求める結合手段と、
前記値 Wと前記記憶手段から読み出した RS A公開鍵 （N， e) と内部にお いて発生させた乱数 Tを入力として所定の計算式により値 Zを求め、 前記サ一 バへ送信するマスク演算手段と
を備え、
前言己サーバは、
サーバ登録用のパスワード認証データ Hと RS A秘密鍵 （N， d) を予め記 憶レておく記憶手段と、
前記記憶手段から読み出したパスヮ一ド認証データ Hと RS A秘密鍵 （N, d) と前記端末装置から受信した値 Zを入力として所定の計算式により値 Tを 求めるマスター鍵生成手段と
を備えたことを特徴とする認証システム。
23. ユーザが予め決定したパスワードに基づいて、 前記パスワード認証デ 一夕 Hと前記認証情報 P' を求めるデータ伸長手段をさらに備えたことを特徴 とする請求項 22に記載の認証システム。
24. 前記 RSA公開鍵.（N, e) と前記 RSA秘密鍵 （N， d) を求める RS A鍵生成手段をさらに備えたことを特徴とする請求項 22に記載の認証 システム。
25. 前記端末装置は、
前記サーバから受信した値 V 2と前記乱数 Tを入力として所定の計算式に よる値 V 2と比較照合し、 一致した場合にサ一バを認証する認証結果判断手段 と、
前記乱数 Tを入力として所定の計算式により値 V 1を求め、 前記サーバへ送 信する検証子生成手段をさらに備え、
前記サーバは、 前記値 Tを入力として所定の計算式により値 V 2を求め、 前記端末装置へ送 信する検証子生成手段と、
前記端末装置から受信した値 V 1と前記値 Τを入力として所定の計算式に よる値 VIと比較照合し、 一致した場合に端末装置を認証する認証結果判断手 段をさらに備えた
ことを特徴とする請求項 22、 23または 24に記載の認証システム。
26. 前記端末装置及びサーバは、 相互の認証が行われた場合に、 セッショ ン鍵を生成するセッション鍵生成手段をそれぞれに備えたことを特徴とする 請求項 25に記載の認証システム。
27. 前記認証情報 P' は、 多項式と FDH関数であることを特徴とする請 求項 22から 26のいずれかに記載の認証システム。
28. 前記認証情報 P' は、 FDH関数であることを特徴とする請求項 22 から 26のいずれかに記載の認証システム。
29. 前記 RSA公開鍵 （Ν, e) は、 安全な通信を用いることを特徴とす る請求項 22から 26のいずれかに記載の認証システム。
30. 前記 RSA公開鍵 （N, e) は、 安全ではない通信を用いることを特 徴とする請求項 22から 26のいずれかに記載の認証システム。
31. 端末装置とサーバ間において相互に認証を行う認証システムにおける 端末装置上で動作する認証プログラムであって、
ユーザ保存用の認証情報 P' と RSA公開鍵 （N, e) を予め記憶しておく 記憶処理と、
前記記憶しておいた認証情報 P' と認証時に入力されたパスヮードを入力と して所定の計算式により値 Wを求める結合処理と、 前記値 Wと前記記憶しておいた RS A公開鍵 （N, e) と内部において発生 させた乱数 Tを入力として所定の計算式により値 Zを求め、 前記サーバへ送信 するマスク演算処理と
をコンピュータに行わせることを特徴とする認証プログラム。
32. ユーザが予め決定したパスワードに基づいて、 前記認証情報 P' を求 めるデ一夕伸長処理をさらにコンピュータに行わせることを特徴とする請求 項 31に記載の認証プログラム。
33. 前記 RSA公開鍵 （N， e) を求める RSA鍵生成処理をさらにコン ピュー夕に行わせることを特徴とする請求項 31に記載の認証プログラム。
34. 前記サーバから受信した値 V 2と前記乱数 Tを入力として所定の計算 式による値 V 2と比較照合し、 一致した場合にサーバを認証する認証結果判断 処理と、
前記乱数 Tを入力として所定の計算式により値 V 1を求め、 前記サーバへ送 信する検証子生成処理をさらにコンピュータに行わせることを特徴とする請 求項 3 1、 32または 33に記載の認証プログラム。
35. 端末装置とサーバ間において相互に認証を行う認証システムにおける サーバ上で動作する認証プログラムであって、
サーバ登録用のパスワード認証データ Hと RSA秘密鍵 （N, d) を予め 記憶しておく記憶処理と、
前記記憶しておいたパスワード認証データ Hと RS A秘密鍵 （N, d) と前 記端末装置から受信した値 Zを入力として所定の計算式により値 Tを求める マスター鍵生成処理と
をコンピュータに行わせることを特徴とする認証プログラム。
36. ユーザが予め決定したパスワードに基づいて、 前記パスワード認証デ 一夕 Hを求めるデータ伸長処理をさらにコンピュータに行わせることを特徴 とする請求項 35に記載の認証プログラム。
37. 前記 RSA秘密鍵 （N, d) を求める RS A鍵生成処理をさらにコン ピュー夕に行わせることを特徴とする請求項 35に記載の認証プログラム。
38. 前記値 Tを入力として所定の計算式により値 V 2を求め、 前記端末装 置へ送信する検証子生成処理と、
前記端末装置から受信した値 V 1と前記値 Tを入力として所定の計算式に よる値 VIと比較照合し、 一致した場合に端末装置を認証する認証結果判断処 理をさらにコンピュータに行わせることを特徴とする請求項 35、 36または 37に記載の認証プログラム。
39. 端末装置及びサーバにおいて相互の認証が行われた場合に、 セッショ ン鍵を生成するセッション鍵生成処理をそれぞれに備えたことを特徴とする 請求項 34または 38に記載の認証プログラム。
40. 前記認証情報 P' は、 多項式と FDH関数であることを特徴とする請 求項 31から 39のいずれかに記載の認証プログラム。
41. 前記認証情報 P' は、 FDH関数であることを特徴とする請求項 3 1 から 39.のいずれかに記載の認証プログラム。
42. 前記 RS A公開鍵 （N， e) は、 安全な通信を用いる
る請求項 31から 39のいずれかに記載の認証プログラム。
43. 前記 RS A公開鍵 （N， e) は、 安全ではない通信を用いることを特 徵とする請求項 3 1から 39のいずれかに記載の認証プログラム。
4 4 . 前記端末装置は、
更新情報 T ' を発生させる発生手段と、
前記記憶手段に記憶されている認証情報 P ' と前記更新情報 T ' を入力し、 所定の計算式によってサーバ更新用のパスワード認証データ H ' と新たな認証 情報 P， を求め、 サーバ更新用のパスワード認証データ H ' を前記サーバへ送 信するとともに、 新たな認証情報 P ' を前記記憶手段に記憶する更新情報生成 手段と
を備え、
前記サーバは、
前記端末装置から送信されたサーバ更新用のパスヮード認証データ H ' と前 記記憶手段に記憶されたパスワード認証データ Hを入力し、 所定の計算式によ つて新たなパスワード認証デ一夕 Hを求めて前記記憶手段に記憶されているパ スワード認証デー夕 Hを更新する更新情報生成手段を備えた
ことを特徴とする請求項 2 3に記載の認証システム。
4 5 . 前記端末装置は、
前記記憶手段に記憶されている認証情報 P ' と前記乱数 Tを入力し、 所定の 計算式によって新たな認証情報 P ' を求め、 新たな認証情報 P ' を前記記憶手 段に記憶する更新情報生成手段と
を備え、
前記サーバは、 .
前記記憶手段に記憶されたパスヮ一ド認証データ Hと前記マスター鍵生成 手段によって求めた値 Tを入力し、 所定の計算式によって新たなパスワード認 証データ Hを求めて前記記憶手段に記憶されているパスワード認証デ一夕 Hを 更新する更新情報生成手段を備えた
ことを特徴とする請求項 2 2に記載の認証システム。
4 6 . 前記端末装置は、
秘密情報 S ' を発生させる発生手段と、 前記記憶手段に記憶されている認証情報 P ' と前記秘密情報 S ' と新しいパ スワードを入力し、 所定の計算式によつてサーバ更新用のパスヮード認証デー 夕 H ' と新たな認証情報 P ' を求め、サーバ更新用のパスワード認証データ H ' を前記サーバへ送信するとともに、 新たな認証情報 P ' を前記記憶手段に記憶 する更新情報生成手段と
を備え、
前記サーバは、
前記端末装置から送信されたサーバ更新用のパスワード認証デー夕 H ' と前 記記憶手段に記憶されたパスヮード認証デ一夕 Hを入力し、 所定の計算式によ つて新たなパスヮード認証デー夕 Hを求めて前記記憶手段に記憶されているパ スワード認証データ Hを更新する更新情報生成手段を備えた
ことを特徴とする請求項 2 3に記載の認証システム。
4 7 . 端末装置と複数のサーバ間において相互に認証を行い、 前記端末装置内 の保存対象のデータを前記サーバ内に分散して保存する遠隔分散保存システムで あって、
前記端末装置は、
ユーザが予め決定しておいたパスヮ一ドに基づいて、 サーバ登録用のパスヮー ド認証データ Hとユーザ保存用の認証情報 P ' を求めるデータ伸長手段と、 前記データ伸長手段によって求めた認証情報 P ' を予め記憶しておく記憶手段 と、
前記記憶手段から読み出した認証情報 P ' と認証時に入力されたパスヮードを 入力として所定の計算式により値 Pを求める結合手段と、
前記値 Pと内部において発生させた乱数を入力として所定の計算式により値 Y 1を求め、 前記サーバへ送信するマスク演算手段と、
前記値 Pと内部において発生させた乱数と前記サーバから受信した値 Y 2を入 力として所定の計算式により値 MKを求めるマスター鍵生成手段と、
前記値 MKを入力として所定の計算式により値 V 1を求め、 サーバへ送信する とともに、 前記サーバから受信した値 V 2と値 V Iと比較照合し、 一致した場合 にサーバを認証する認証結果判断手段と、
サーバの認証が行われた場合に、 セッション鍵 S Kをサーバの数だけ生成する セッション鍵生成手段と、
前記保存対象のデ一夕を分割して、 認証したサーバの数と同数の分割データを 得るデータ分割手段と、
前記分割データのそれぞれと保存対象のデータを識別する識別情報とを、 保存 先のサーバと共有した前記セッション鍵 S Kを用いて暗号化して、 各サーバに対 して送信するデ一夕保存手段と、
分割データが保存された各サーバから分割データを受信し、 前記保存対象のデ 一夕を復元するデー夕復元手段と
を備え、
前記サーバは、
前記データ伸長手段によって求めたパスワード認証データ Hを予め記憶してお く記憶手段と、
前記記憶手段から読み出したパスワード認証デ一夕 Hと内部において発生させ た乱数を入力として所定の計算式により値 Y 2を求め、 前記端末装置へ送信する マスク演算手段と、
前記パスワード認証データ Hと内部において発生させた乱数と前記端末装置か ら受信した値 Y 1を入力として所定の計算式により値 MKを求めるマスター鍵生 成手段と、
前記値 MKを入力として所定の計算式により値 V 2を求め、 端末装置へ送信す るとともに、 前記端末装置から受信した値 V Iと値 V 2と比較照合し、 一致した 場合に端末装置を認証する認証結果判断手段と、
端末装置の認証が行われた場合に、 セッション鍵を生成するセッション鍵生成 手段と、
端末装置から受信した分割デー夕を受信するデータ受信手段と、
前記分割デー夕を記憶するデータ記憶手段と、
前記データ記憶手段に保存されている分割データを読み出して端末装置へ送信 するデータ送信手段と を備えたことを特徴とする遠隔分散保存システム
4 8 . 前記分割データの一部を前記端末装置内に保存することを特徴とする請 求項 4 7に記載の遠隔分散保存システム。
4 9 . 端末装置と複数のサーバ間において相互に認証を行い、 前記端末装置内 の保存対象のデータを前記サーバ内に分散して保存する遠隔分散保存システムに おける端末装置上で動作する遠隔分散保存プログラムであって、
ユーザが予め決定しておいたパスヮードに基づいて、 サ一バ登録用のパスヮー ド認証データ Hとユーザ保存用の認証情報 P ' を求めるデータ伸長処理と、 前記データ伸長処理によって求めた認証情報 P ' を予め記憶しておく記憶処理 と、
前記記憶処理から読み出した認証情報 P ' と認証時に入力されたパスヮードを 入力として所定の計算式により値 Pを求める結合処理と、
前記値 Pと内部において発生させた乱数を入力として所定の計算式により値 Y 1を求め、 前記サーバへ送信するマスク演算処理と、
前記値 Pと内部において発生させた乱数と前記サーバから受信した値 Y 2を入 力として所定の計算式により値 MKを求めるマスター鍵生成処理と、
前記値 MKを入力として所定の計算式により値 V 1を求め、 サーバへ送信する とともに、 前記サーバから受信した値 V 2と値 V Iと比較照合し、 一致した場合 にサーバを認証する認証結果判断処理と、
サーバの認証が行われた場合に、 セッション鍵 S Kをサーバの数だけ生成する セッション鍵生成処理と、
前記保存対象のデータを分割して、 認証したサーバの数と同数の分割データを 得るデータ分割処理と、
前記分割データのそれぞれと保存対象のデータを識別する識別情報とを、 保存 先のサーバと共有した前記セッション鍵 S Kを用いて暗号化して、 各サーバに対 して送信するデー夕保存処理と、
分割デー夕が保存された各サーバから分割デー夕を受信し、 前記保存対象のデ 一夕を復元するデータ復元処理と
をコンピュー夕に行わせることを特徴とする遠隔分散保存プログラム
5 0 . 端末装置と複数のサーバ間において相互に認証を行い、 前記端末装置内 の保存対象のデータを前記サーバ内に分散して保存する遠隔分散保存システムに おけるサーバ上で動作する遠隔分散保存プログラムであって、
データ伸長処理によって求めたパスワード認証データ Hを予め記憶しておく記 憶処理と、
前記記憶処理から読み出したパスワード認証データ Hと内部において発生させ た乱数を入力として所定の計算式により値 Y 2を求め、 前記端末装置へ送信する マスク演算処理と、
前記パスワード認証データ Hと内部において発生させた乱数と前記端末装置か ら受信した値 Y 1を入力として所定の計算式により値 MKを求めるマスター鍵生 成処理と、
前記値 MKを入力として所定の計算式により値 V 2を求め、 端末装置へ送信す るとともに、 前記端末装置から受信した値 V Iと値 V 2と比較照合し、 一致した 場合に端末装置を認証する認証結果判断処理と、
端末装置の認証が行われた場合に、 セッション鍵を生成するセッション鍵生成 処理と、
端末装置から受信した分割データを受信するデー夕受信処理と、
前記分割データを記憶するデータ.記憶処理と、
前記データ記憶処理に保存されている分割データを読み出して端末装置へ送信 するデータ送信処理と
をコンピュータに行わせることを特徴とする遠隔分散保存プログラム。
PCT/JP2004/015184 2003-10-28 2004-10-07 認証システム及び遠隔分散保存システム Ceased WO2005041474A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2005514934A JP4774492B2 (ja) 2003-10-28 2004-10-07 認証システム及び遠隔分散保存システム
US10/577,111 US7895436B2 (en) 2003-10-28 2004-10-07 Authentication system and remotely-distributed storage system
CN2004800307512A CN1871810B (zh) 2003-10-28 2004-10-07 认证系统和远隔分散保存系统

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2003-367527 2003-10-28
JP2003367527 2003-10-28

Publications (1)

Publication Number Publication Date
WO2005041474A1 true WO2005041474A1 (ja) 2005-05-06

Family

ID=34510297

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2004/015184 Ceased WO2005041474A1 (ja) 2003-10-28 2004-10-07 認証システム及び遠隔分散保存システム

Country Status (5)

Country Link
US (1) US7895436B2 (ja)
JP (1) JP4774492B2 (ja)
KR (1) KR100845018B1 (ja)
CN (1) CN1871810B (ja)
WO (1) WO2005041474A1 (ja)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2008219177A (ja) * 2007-02-28 2008-09-18 Kddi Corp 端末装置、データ管理装置およびコンピュータプログラム
JP2009267451A (ja) * 2008-04-21 2009-11-12 National Institute Of Advanced Industrial & Technology Ｒｓａをベースとしたパスワード認証方式及びその応用
JP2012186635A (ja) * 2011-03-04 2012-09-27 Toyota Motor Corp 車両ネットワークシステム
US8422670B2 (en) 2008-07-10 2013-04-16 National Institute Of Advanced Industrial Science And Technology Password authentication method
JP2013090199A (ja) * 2011-10-19 2013-05-13 National Institute Of Advanced Industrial & Technology 鍵共有システム、鍵生成装置、及びプログラム
WO2020100929A1 (ja) * 2018-11-15 2020-05-22 株式会社東海理化電機製作所 認証システム及び認証方法
JP2021500760A (ja) * 2017-10-18 2021-01-07 クリプトグラフィ リサーチ， インコーポレイテッド 外部監視攻撃からモジュラーインバージョン演算を保護すること

Families Citing this family (48)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8363837B2 (en) * 2005-02-28 2013-01-29 HGST Netherlands B.V. Data storage device with data transformation capability
JP2006334803A (ja) * 2005-05-31 2006-12-14 Konica Minolta Business Technologies Inc 画像処理装置、および、その制御方法
GB0513375D0 (en) * 2005-06-30 2005-08-03 Retento Ltd Computer security
NO324315B1 (no) * 2005-10-03 2007-09-24 Encap As Metode og system for sikker brukerautentisering ved personlig dataterminal
JP4575283B2 (ja) * 2005-11-15 2010-11-04 株式会社東芝 暗号装置、復号装置、プログラム及び方法
KR101391151B1 (ko) * 2007-06-01 2014-05-02 삼성전자주식회사 세션 키를 이용한 인증 방법 및 이를 위한 장치
GB2467462A (en) * 2007-09-14 2010-08-04 Millennium Force Co Ltd Data security apparatus
KR100926631B1 (ko) * 2007-09-14 2009-11-11 (주)밀레니엄 포스 데이터 보안장치
CN101425897B (zh) * 2007-10-29 2011-05-18 上海交通大学 一种用户认证方法、系统、服务器和用户节点
KR101016277B1 (ko) * 2007-12-20 2011-02-22 건국대학교 산학협력단 보안성이 강화된 ｓⅰｐ 등록 및 ｓⅰｐ 세션 설정 방법 및장치
JP2009175197A (ja) * 2008-01-21 2009-08-06 Toshiba Corp 暗号装置、復号装置、鍵生成装置及びプログラム
US8959199B2 (en) * 2008-03-18 2015-02-17 Reduxio Systems Ltd. Network storage system for a download intensive environment
US7522723B1 (en) * 2008-05-29 2009-04-21 Cheman Shaik Password self encryption method and system and encryption by keys generated from personal secret information
EP2285042A1 (fr) * 2009-07-07 2011-02-16 Gemalto SA Module logiciel de sécurisation utilisant le chiffrement du haché d'un mot de passe concaténé avec une graine
US8433918B2 (en) * 2009-10-14 2013-04-30 Texas Instruments Incorporated Methods and systems for improving the security of password-based authentication protocols for IEEE 802.11 networks
US8671265B2 (en) 2010-03-05 2014-03-11 Solidfire, Inc. Distributed data storage system providing de-duplication of data using block identifiers
US9015489B2 (en) * 2010-04-07 2015-04-21 Microsoft Technology Licensing, Llc Securing passwords against dictionary attacks
KR101630462B1 (ko) * 2010-04-14 2016-06-14 주식회사 넥슨코리아 키보드 보안 장치 및 방법
US8874868B2 (en) * 2010-05-19 2014-10-28 Cleversafe, Inc. Memory utilization balancing in a dispersed storage network
KR20130050696A (ko) * 2011-11-08 2013-05-16 삼성전자주식회사 메모리 시스템
US9838269B2 (en) 2011-12-27 2017-12-05 Netapp, Inc. Proportional quality of service based on client usage and system metrics
US9054992B2 (en) 2011-12-27 2015-06-09 Solidfire, Inc. Quality of service policy sets
US9521130B2 (en) * 2012-09-25 2016-12-13 Virnetx, Inc. User authenticated encrypted communication link
US20140331061A1 (en) * 2013-05-02 2014-11-06 Solidfire, Inc Drive level encryption key management in a distributed storage system
US20150033016A1 (en) * 2013-07-23 2015-01-29 Battelle Memorial Institute Systems and methods for securing real-time messages
US9405783B2 (en) * 2013-10-02 2016-08-02 Netapp, Inc. Extent hashing technique for distributed storage architecture
US9448924B2 (en) 2014-01-08 2016-09-20 Netapp, Inc. Flash optimized, log-structured layer of a file system
US9529546B2 (en) 2014-01-08 2016-12-27 Netapp, Inc. Global in-line extent-based deduplication
US9256549B2 (en) 2014-01-17 2016-02-09 Netapp, Inc. Set-associative hash table organization for efficient storage and retrieval of data in a storage system
US9268653B2 (en) 2014-01-17 2016-02-23 Netapp, Inc. Extent metadata update logging and checkpointing
US20150244795A1 (en) 2014-02-21 2015-08-27 Solidfire, Inc. Data syncing in a distributed system
US9798728B2 (en) 2014-07-24 2017-10-24 Netapp, Inc. System performing data deduplication using a dense tree data structure
US10133511B2 (en) 2014-09-12 2018-11-20 Netapp, Inc Optimized segment cleaning technique
US9671960B2 (en) 2014-09-12 2017-06-06 Netapp, Inc. Rate matching technique for balancing segment cleaning and I/O workload
US9836229B2 (en) 2014-11-18 2017-12-05 Netapp, Inc. N-way merge technique for updating volume metadata in a storage I/O stack
US9720601B2 (en) 2015-02-11 2017-08-01 Netapp, Inc. Load balancing technique for a storage array
US9762460B2 (en) 2015-03-24 2017-09-12 Netapp, Inc. Providing continuous context for operational information of a storage system
US9710317B2 (en) 2015-03-30 2017-07-18 Netapp, Inc. Methods to identify, handle and recover from suspect SSDS in a clustered flash array
US9740566B2 (en) 2015-07-31 2017-08-22 Netapp, Inc. Snapshot creation workflow
US9876783B2 (en) 2015-12-22 2018-01-23 International Business Machines Corporation Distributed password verification
US10929022B2 (en) 2016-04-25 2021-02-23 Netapp. Inc. Space savings reporting for storage system supporting snapshot and clones
US10642763B2 (en) 2016-09-20 2020-05-05 Netapp, Inc. Quality of service policy sets
WO2019107314A1 (ja) * 2017-11-30 2019-06-06 株式会社アドテクニカ 情報処理装置、情報処理方法、情報処理システム及びプログラム
US12255889B2 (en) * 2018-08-16 2025-03-18 Cyberark Software Ltd. Detecting and preventing unauthorized credential change
DE102019001731A1 (de) * 2019-03-12 2020-09-17 data-team Datendienste GmbH Autorisierungsverfahren mittels Einmalpasswörtern
CN110768792B (zh) * 2019-09-30 2023-09-05 奇安信科技集团股份有限公司 主密钥生成方法、装置及敏感安全参数的加解密方法
JP7273742B2 (ja) * 2020-02-07 2023-05-15 株式会社東芝 暗号化装置、復号装置、暗号方法、復号方法、暗号化プログラム及び復号プログラム
JP7768872B2 (ja) * 2022-12-06 2025-11-12 株式会社東芝 暗号化装置、復号装置、鍵生成装置、暗号方法、復号方法、鍵生成方法、暗号化プログラム、復号プログラム及び鍵生成プログラム

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH04245287A (ja) * 1991-01-31 1992-09-01 Matsushita Electric Ind Co Ltd 識別情報に基づく秘密鍵生成方法

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6061799A (en) * 1997-10-31 2000-05-09 International Business Machines Corp. Removable media for password based authentication in a distributed system
CN1338841A (zh) * 2000-08-11 2002-03-06 海南格方网络安全有限公司 计算机安全认证智能密钥
JP2002208925A (ja) 2001-01-10 2002-07-26 Ntt Advanced Technology Corp 可変認証情報を用いる資格認証方法
US6912653B2 (en) 2001-01-23 2005-06-28 Erika Monika Gohl Authenticating communications
CN1150726C (zh) * 2002-10-01 2004-05-19 华中科技大学 一种安全网络传输方法及其系统
US7607009B2 (en) * 2003-02-10 2009-10-20 International Business Machines Corporation Method for distributing and authenticating public keys using time ordered exchanges

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH04245287A (ja) * 1991-01-31 1992-09-01 Matsushita Electric Ind Co Ltd 識別情報に基づく秘密鍵生成方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
KOBARA K. ET AL.: "Pretty-simple password-authenticated key-exchange protocol proven to be secure in the standard model", IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS, COMMUNICATIONS AND COMPUTER SCIENCES, vol. E85-A, no. 10, 1 October 2002 (2002-10-01), pages 2229 - 2237, XP002984269 *
SHIN S. ET AL.: "A new password-based authentification protocol", vol. 15, 29 October 2003 (2003-10-29), pages 7 - 12, XP002984270 *

Cited By (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2008219177A (ja) * 2007-02-28 2008-09-18 Kddi Corp 端末装置、データ管理装置およびコンピュータプログラム
JP2009267451A (ja) * 2008-04-21 2009-11-12 National Institute Of Advanced Industrial & Technology Ｒｓａをベースとしたパスワード認証方式及びその応用
US8422670B2 (en) 2008-07-10 2013-04-16 National Institute Of Advanced Industrial Science And Technology Password authentication method
JP5224481B2 (ja) * 2008-07-10 2013-07-03 独立行政法人産業技術総合研究所 パスワード認証方法
JP2012186635A (ja) * 2011-03-04 2012-09-27 Toyota Motor Corp 車両ネットワークシステム
US9413732B2 (en) 2011-03-04 2016-08-09 Toyota Jidosha Kabushiki Kaisha Vehicle network system
JP2013090199A (ja) * 2011-10-19 2013-05-13 National Institute Of Advanced Industrial & Technology 鍵共有システム、鍵生成装置、及びプログラム
JP2021500760A (ja) * 2017-10-18 2021-01-07 クリプトグラフィ リサーチ， インコーポレイテッド 外部監視攻撃からモジュラーインバージョン演算を保護すること
JP7155173B2 (ja) 2017-10-18 2022-10-18 クリプトグラフィ リサーチ， インコーポレイテッド 外部監視攻撃からモジュラーインバージョン演算を保護すること
WO2020100929A1 (ja) * 2018-11-15 2020-05-22 株式会社東海理化電機製作所 認証システム及び認証方法
JP2020088408A (ja) * 2018-11-15 2020-06-04 株式会社東海理化電機製作所 認証システム及び認証方法
JP7057944B2 (ja) 2018-11-15 2022-04-21 株式会社東海理化電機製作所 認証システム及び認証方法

Also Published As

Publication number Publication date
US20070061572A1 (en) 2007-03-15
US7895436B2 (en) 2011-02-22
JPWO2005041474A1 (ja) 2007-04-26
KR20060073647A (ko) 2006-06-28
KR100845018B1 (ko) 2008-07-10
JP4774492B2 (ja) 2011-09-14
CN1871810A (zh) 2006-11-29
CN1871810B (zh) 2010-09-08

Similar Documents

Publication Publication Date Title
JP4774492B2 (ja) 認証システム及び遠隔分散保存システム
US12242621B2 (en) Protecting data from brute force attack
US20060195402A1 (en) Secure data transmission using undiscoverable or black data
US8396218B2 (en) Cryptographic module distribution system, apparatus, and program
US20110145576A1 (en) Secure method of data transmission and encryption and decryption system allowing such transmission
US20120087495A1 (en) Method for generating an encryption/decryption key
WO2017147503A1 (en) Techniques for confidential delivery of random data over a network
JP2001513227A (ja) ネットワーク環境における秘密最新乱数の管理および使用
CN110868291A (zh) 一种数据加密传输方法、装置、系统及存储介质
EP2945347B1 (en) Methods and devices for securing keys when key-management processes are subverted by an adversary
JP5047638B2 (ja) 暗号文復号権委譲システム
CN113824713B (zh) 一种密钥生成方法、系统及存储介质
JP6041864B2 (ja) データの暗号化のための方法、コンピュータ・プログラム、および装置
CN111211897A (zh) 一种基于随机预言模型的时间控制加密安全增强方法
JP5324813B2 (ja) 鍵生成装置、証明書生成装置、サービス提供システム、鍵生成方法、証明書生成方法、サービス提供方法およびプログラム
JP2005252384A (ja) 暗号化データ保管サーバシステム、暗号化データ保管方法及び再暗号化方法
Shakiba Security analysis for chaotic maps-based mutual authentication and key agreement using smart cards for wireless networks
KR20140071775A (ko) 암호키 관리 시스템 및 방법
JP4758110B2 (ja) 通信システム、暗号化装置、鍵生成装置、鍵生成方法、復元装置、通信方法、暗号化方法、暗号復元方法
Chang et al. Authentication schemes with no verification table
WO2005018138A1 (en) Generation and validation of diffie-hellman digital signatures
US20250379734A1 (en) Enhanced RSA Algorithm Using Transform Function
Kara et al. An encrypted and signed plaintext symmetric cryptosystem
EP1394981A2 (en) Public key cryptograph communication method
JP3638501B2 (ja) 匿名通信路

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200480030751.2

Country of ref document: CN

AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): BW GH GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2005514934

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 2007061572

Country of ref document: US

Ref document number: 1020067008005

Country of ref document: KR

Ref document number: 10577111

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 1020067008005

Country of ref document: KR

122 Ep: pct application non-entry in european phase
WWP Wipo information: published in national office

Ref document number: 10577111

Country of ref document: US