JP3278916B2 - User authentication method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION This invention, with respect to the user authentication to verify the identity of the sender, can be reduced high and traffic safety, it is to propose good user authentication method the efficiency.

[0002]

2. Description of the Related Art A Fiat-Shamir system has been proposed as a conventionally proposed user authentication system (Fiat, A. et al.
and Shamir, A: "How to prov
e YOURSELF: Practical Solu
tensions to identification a
nd signature problems ”, Pr
receiveds of Crypto 86, Sa
nta Barbara, August 1986, p.
p. 18-1-18-7). The Fiat-Shamir authentication scheme is as follows.

A reliable center generates k pieces of secret information s _j (1 ≦ j ≦ k) in the following procedure for a user who uses an ID as personal identification information (k is a parameter for determining security). And 1 or more). Step 1: Calculate v _j = f (ID, j) (1 ≦ j ≦ k) using the one-way function f.

Step 2: For each v _j , the prime factor P of N
S _j = √1 / v _j (mod N) is calculated using Q and Q. That is, s _j ² = 1 / v _j (mod
N). Step 3: k s _j are issued to the user secretly, and the number of composites N is made public.

[0005] The calculation of the square root in (mod N) is
It can be executed only when the prime factors of N (P and Q) are known. The method is described, for example, in Rabin, M .; O. : "Di
digitized Signatures and
Public-key Functions as I
ntractable as Factorizati
on ", Tech.Rep.MIT/LCS/TR-2
12 MIT Lab. Comput. Sci. 197
9. A specific configuration example of the square root calculator is disclosed in Japanese Patent Application No. 61-169350.
Is shown in

The sender A certifies to the authenticator B that A is genuine by the following procedure. Step 1: A sends ID to B. Step 2: B is v _j = f (ID, j) (1 ≦ j ≦
Calculate k).

Next, the following steps 3 to 6 are repeated t times for i = 1,..., T (t is a parameter for determining security, and a value of 1 or more). Step 3: Generate a random number r _i , calculate x _i = r _i ² (mod N), and send it to B.

Step 4: B is a bit string of 0, 1 (e
_i1 , ..., _eik ) are generated and sent to A. Step 5: A generates a signature sentence y _i by y _i = r _i Πs _j (mod N) and sends it to B. Π is j = 1 to k for e _ij
Step 6: B checks x _i = y _i ² Πv _j (mod N). Π is e _ij for j = y _i ² than how to make y _i from 1 to ^{_{k Πv j = r i 2 Π}} (s j 2 × v
because it is ^{_{j) = r i 2 = x}} i (mod N), if it passes all the t times of inspection, certifier B admits A is genuine.

[0009] At this time, the probability that the authenticator B will mistake the false user as the real A is 1/2 ^kt . Here, k is secret information (s
_j ), and t is the message (x _i , (e _i1 ,..., e)
_ik ) and y _i ) are determined. This method has been proven to be secure by a computational complexity method. That is,
This method has been described above as being a zero-knowledge proof.
And Shamir et al. If the user authentication method is a zero-knowledge proof, it is guaranteed from the computational complexity viewpoint that any fraudulent activity is difficult.

[0010]

However, Fiat-S
In the Hamir system, the number of bits of a message is N = 512.
The number of bits is (1024 × t + k × t) bits, and it is necessary to select k and t of a certain size in order to ensure security, so that the communication amount increases. As described above, the Fiat-Shamir method has a problem in that the amount of transfer information is large. The purpose of the invention is to provide a user authentication method that can reduce the amount of transfer information.

[0011]

According to the first aspect of the present invention, a user (authenticatee) device generates secret keys s1 and s2, and uses the secret keys to generate integers a, k, and public information that are public information. Using n, a public key v is generated by a modular exponentiation operation and a modular multiplication modulo n, and these a, k, n, and v are made public. In the authentication processing stage, the device to be authenticated has random numbers r1, r2 generates therewith a, k, than n, the remainder exponentiation modulo n, to calculate the x using modular multiplication, that the it
The x, I are transmitted to the certifier device together with the certifier ID.
Authenticator device receiving the D generates a random number e, and sends it to the person to be authenticated device, the authenticator device <br/> is r1, r2, s1, modulo k than s2 that received the e Y1 and y2 are calculated using the remainder operation modulo n and the remainder operation modulo n,
These were transmitted to the verifier apparatus, these y1, the verifier device receiving y2 searches for v from management book based on ID, the v and a, k, n, and n from e, y1, y2 A modular exponentiation operation and a modular multiplication are performed, and it is verified whether or not the result is equal to x.

According to the invention of claim 2, the user (authenticatee) device generates secret keys s1 and s2, and uses the prime numbers p and the integers g ₁ and g ₂ as public information from the secret keys. , P to generate a public key v by a modular exponentiation operation and a modular multiplication, and publish these p, g ₁ , g ₂ , and v
In the authentication processing stage, the device to be authenticated has random numbers r1 and r2.
Generate, at the same p, g _1, from g _2, modular exponentiation modulo p, compute the x using modular multiplication, its it
Is transmitted to the authenticator device together with the ID of the subject to be authenticated, and the authenticator device receiving these x and ID generates a random number e, sends it to the device to be authenticated, and receives the e to receive the authenticated device . 's device r1, r2, s1, s2 using the modulo operation from calculate the y1, y2, they were sent to the verifier device, these y1, y2 the verifier device that receives the I
A public key v is searched from the management book based on D, and v and p,
g ₁ , g ₂ , e, y 1, and y _{2 are} subjected to a modular exponentiation operation and a modular multiplication modulo p.
Is verified, and if the verification is passed, it is valid.

[0013]

The Fiat-Shamir method realizes a quadratic residue arithmetic expression modulo a composite number a plurality of times (kt times), while the method according to the first aspect of the present invention uses a modulo composite number. This is realized by using the “higher-order” remainder arithmetic expression only twice in the basic part. The level of security is Fiat-Sham
If superposition number (kt times) the size (number of bits) of the order of at Toko the invention how <br/> (k) is the same in the ir system,
Are equivalent. This security proof is based on the inventor's paper (“P
robustly secure and Practic
al Identification Schemes
andCorresponding Signature
re Schemes, "toappear int
he Proceedings of Crypto '
92, LNCS. Springer-Verlag). Incidentally, the safety of the present invention how depends on the difficulty of synthesis number of factoring law (Fiat-Sh
The amir scheme also depends on the difficulty of factoring the composite numbers of the modulus).

[0014] way of the invention of claim 2, "prime" the modulo realizing "higher order" modular arithmetic expression using only twice in the base portion. The level of security is Fiat-Sham
If superposition number (kt times) the size (number of bits) of the order of at Toko the invention how <br/> (e) are the same in the ir system,
Are equivalent. This proof of security is shown in the inventor's article. Incidentally, the safety of the present invention how depends on the difficulty of discrete logarithm problem modulo prime number.

While the Fiat-Shamir method is based on a form in which a Yes / No (1 bit) query response is repeated in the authentication process, the communication amount increases, whereas in the present invention, a query response of several hundred bits is used. Since the configuration is based on the one-and-a-half operation, the amount of communication can be reduced.

[0016]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below. FIG. 1 shows the overall configuration of the present invention. As shown in this figure, it is assumed that a user (authenticatee) device 100 to be authenticated and an authenticator device 200 to perform authentication are connected via an insecure communication path 300.

First, the user (authenticatee) A who has subscribed to the system, in the initial information setting stage which is basically performed only once by the user device 100 at the time of subscribing the system, performs the procedure shown in FIG. A key is generated, and the public key is paired with the identification information ID of the user and registered in the public key management book 400 and the authenticator apparatus 200. First, after two prime numbers p and q are determined using the prime number generator 101, n = pq is calculated using the multiplier 110, and an integer a of 1 or more and n-1 or less, and
Determine the safety factor k. Next, a random number generator 102 is used to generate a random number s1 from 0 to k-1 and an integer s2 from 1 to n-1.
05 and the remainder multiplier 104, the following equation is calculated.

V = a− ^s1 · s2− ^k mod n User A publishes (a, k, n, v) as a public key and holds (s1, s2) as its own private key. Note that the system may determine values other than v in the public key as values common to users. Next, the user A certifies the user authentication procedure for proving his / her validity to the authenticator B. Hereinafter, the authentication procedure will be described with reference to FIGS. FIG. 3 shows a state of communication of a message between the authenticated person A and the authenticated person B in user authentication, FIG. 4 is a block diagram of the authenticated person device 100, and FIG. 5 is a block diagram of the authenticated person device 200.

The user authentication procedure is as follows. Step 1: The device to be authenticated uses the random number generator 102 to generate a random number r1,
r2, the remainder multiplier 104 and the remainder exponentiation unit 1
The following equation is calculated by using 05. The ^{x = a r1 · r2 k mod} n x together with the ID of the person to be authenticated sends to the verifier device. Step 2: The authenticator apparatus searches the management book 400 for the public key v of the subject A based on the received ID, and then generates a random number e of 0 or more and (k-1) or less using the random number generator 202. And transmits it to the device to be authenticated. Step 3: The device to be authenticated stores its own private key (s
1, s2), and the following equation is calculated from the s1, r1, k, and the received e using the remainder multiplier 107 and the remainder adder 108.

Y1 = r1 + es1 mod k Further, e · s1 is obtained by using a multiplier 110, and e · s1 + r1 is further obtained by using an adder 111.
2 is divided by k, and the result of the division is rounded down.
At 13 the fractional part is rounded down, and the result is compared with s2, r2,
Residual exponentiation unit 114 for a, n and received e
Then, the following equation is calculated using the remainder multiplier 115.

Y2 = a ^{[(r1 + e} · ^{s1) / k]} · r2 · s2 ^e mod n (y1, y2) is transmitted to the authenticator. here,[ ]
Means truncation operation below the decimal point. Step 4: The authenticator apparatus receives e, a, k, n, v and received y1, y
, The remainder multiplier 204 and the remainder exponentiation unit 20
The following equation is calculated by using 5.

[0022] ^{w = a y1 · y2 k ·} v e mod n This operation result w is examined using a comparator 208 to see if it matches x previously received, and judged to be acceptable if they match, if disagreement If not, it will be rejected. Next, an embodiment of the present invention will be described. First, user A who joined the system
Generates a public key and a secret key according to the procedure shown in FIG. 6, and pairs the public key with the identification information ID of the user in the initial information setting stage which is basically performed only once by the user device 100 when joining the system. The registration in the public key management book 400 or the user device 200 is the same as in the above embodiment, but the key is generated as follows. First, the prime number generator 10
1 is used to determine two prime numbers p and q. Where q
Is chosen to be one of the factors of p-1 (i.e., q divides p-1). Next, the random number generator 102
, A random number r of 2 or more and p-1 or less is input to the order determination unit 103 together with p and q, and two of the order q are found and set as g ₁ and g ₂ . . Here, the order determiner 103 calculates r ^q mod p, and if the value is 1, the order is determined to be q. Next, using a random number generator 106 generates a 0 or q-1 following two random numbers s1, s2, s1, s2, g 1, g 2, p from modular multiplier 104
Then, the following equation is calculated using the remainder power calculator 105.

V = g ₁ ^-s ₁ · g ₂ ^-s ₂ mod p Furthermore, a parameter t indicating the degree of security is determined (the success probability of unauthorized use is 1/2 ^t ). User A
It is published _{(p, q, g 1,} g 2, t, v) as a public key, hold the (s1, s2) as its own secret key.
Note that the system may determine values other than v in the public key as values common to users.

The state of communication of the communication message between the authenticated person device and the authenticated person device is the same as in FIG.
7 is a block diagram of the authenticator 200, and FIG. 8 is a block diagram of the authenticator apparatus 200. The user authentication procedure is as follows. Step 1: The device to be authenticated uses the random number generator 102 to generate a random number r1,
r2, the remainder multiplier 104 and the remainder exponentiation unit 1
The following equation is calculated by using 05.

X = g ₁ ^r1 · g ₂ ^r2 mod ^px is transmitted to the authenticator apparatus together with the ID of the subject . Step 2: authenticator device, after searching the public key v of the person to be authenticated A from the management book based on the received ID, generates a random number e of t bits using a random number generator 202, a person to be authenticated it Send to device . Step 3: The device to be authenticated stores its own secret key (s1,
s2), and r1, r2, q and the received e
Then, the following equation is calculated using the remainder multiplier 104 and the remainder adder 108.

Y1 = r1 + es1 mod q, y2 = r2 + es2 mod q (y1, y2) are transmitted to the authenticator apparatus . Step 4: The verifier apparatus receives g ₁ , g ₂ , v, p, and e and receives y
Using 1,1 and y2, the following equation is calculated using the remainder multiplier 204 and the remainder exponentiation calculator 205.

[0027] ^{_{w = g 1 y1 · g 2}} y2 · v e mod p The operation result w is examined using a comparator 208 to see if it matches x previously received, and judged to be acceptable if they match, If they do not match, it is rejected. In the above description, one of the remainder multipliers 104, 107, and 115 may be commonly used. One modular exponentiation unit 105, 114 may be used in common. One random number generator 102, 106 may be commonly used.

[0028]

For, according to the present invention (i) safety claims authentication method of claim 1 of the invention is safe, it is sufficient to satisfy the following two conditions. (Condition 1) A valid subject (knows s1 and s2)
Passes with probability 1. (Condition 2) Assuming that an unauthorized subject (who does not know s1 and s2) passes, if it succeeds, b that satisfies a = b ^k mod n given RSA encryption (a, k, n) Can be solved. This is generally more inconsistent than it seems that it is difficult to decrypt the RSA cipher, so that an unauthorized subject is unlikely to pass.

[0029] for authentication method of the second aspect of the present invention is safe, it is sufficient to satisfy the following two conditions. (Condition 1) A valid subject (knows s1 and s2)
Passes with probability 1. (Condition 2) Assuming that an unauthorized subject (who does not know s1 and s2) succeeds, if it succeeds, given a discrete logarithm problem (g1, g2, p, g2 = g1 ^a mod)
(a problem of finding a that satisfies p) can be solved. This is generally considered more inconsistent than the discrete logarithm problem is considered difficult, and therefore it is considered that an unauthorized subject will not pass. (Ii) Traffic The message in the Fiat-Shamir system is (ID,
_{x 1, ..., x t,} (e ij), y 1, ..., a y _t),
The message according to the present invention is (ID, x, e, y1, y2).

Here, the number of bits of (e _ij ) is (k × t)
A _{bit, x 1, ..., x t} , y 1, ..., the number of bits of y _t) is equal to the number of bits of the N. In the case of the invention of claim 1, F
N bits in the iat-Shamir method correspond to the size of n. Therefore, x is equivalent to the number of bits of N, y1 is about 20 bits, y2 is about the number of bits of N, and e is about 20 bits (when the bit size of the parameter k of this method is 20 bits).
Is sufficient for practical use. Set the number of bits in the message to N
Is 512 bits and the parameters of the Fiat-Shamir method are compared when k = 4 and t = 5 (recommended values in their paper). The method of Fiat-Shamir: 5120 + 20 + ID
The number of bits of the claimed invention: 1064 + the number of bits of ID. Therefore, the communication amount of the invention of claim 1 is Fi
It can be seen that it is about 5 times better than the at-Shamir method.

In the case of the invention of claim 2, the Fiat-Sha
N bits in the mir method correspond to the size of p. Therefore,
x is equivalent to the number of bits of N, y1 and y2 are each about 140 bits, and e is about 20 bits (the parameter t = 20 of the present invention) is practically sufficient. When the number of bits of the message is N = 512 bits, Fiat-Shami
Comparing the parameters of the r method in the case of k = 4 and t = 5 (recommended values in their paper): Fiat-Shamir method: 5120 + 20 + number of bits of the invention Claim 2 invention: 812 + number of bits of ID Therefore, the communication amount of the invention of claim 2 is Fia
It can be seen that the improvement is at least six times that of the t-Shamir method.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a system configuration of the present invention.

FIG. 2 is a block diagram showing a process at an initial information setting stage in the invention of claim 1;

FIG. 3 is a diagram showing communication of a communication message between a user (authenticatee) device and an authenticator device .

FIG. 4 is a block diagram showing a user authentication process in the device to be authenticated in the embodiment of the first invention.

FIG. 5 is a block diagram showing a user authentication process in the authenticator device according to the embodiment of the first invention.

FIG. 6 is a block diagram showing a process at an initial information setting stage in the invention of claim 2;

FIG. 7 is a block diagram showing a user authentication process in a device to be authenticated in the embodiment of the second invention.

FIG. 8 is a block diagram showing a user authentication process in the authenticator device according to the embodiment of the second invention.

──────────────────────────────────────────────────続 き Continued on the front page (58) Fields investigated (Int. Cl. ⁷ , DB name) H04L 9/32 G09C 1/00 640 JICST file (JOIS)

Claims (2)

(57) [Claims] 1. A method for confirming the validity of a user, comprising: a prime number p, q, an integer a not less than n-1 and a safety factor
k, n = pq, and the device of the user (authenticatee)
Witness device), a random number s1 not less than 0 and not more than k-1
And a random number s2 of 1 or more and n-1 or less as a secret key,
These secret keys s1, s2, and integer a, k, with n, and generates a public key ^{v = a -s1 · s2 -k modn} ,
The person to be authenticated identification information ID and the a, k, and the n, the v vs. registered in management list, in the authentication process step, the person to be authenticated device random number r1, r2
Is generated, and from these a, k, and n, x = ^ar1 · r2
^k mod n is calculated, and the above x and the identification information ID of the person to be authenticated are transmitted to the authenticator apparatus . The authenticator apparatus having received these x and ID generates a random number e, and transmits it to the object to be authenticated. 's device and send it to, the person to be authenticated device that has received the e, the e, the r
1, private key s1, the above k y1 = r1 + e · s1
mod k is calculated, and the above e, r1, r2, secret key are calculated.
s2, y2 = a ^{[(r1 + e} · ^{s1) / k]} ·
r2 · s2 ^e mod n (where [A] is the value of A
Represents a truncation decimal), these (y1, y2) and transmitted to the verifier apparatus, these (y1, y2) the verifier device that has received the search from the management list of the public key v with respect to the ID And
From the above a, k, n, v, e, y1, y2, w = a ^y1 · y
Characterized in that the 2 ^k · v ^e mod n calculated, w verifies if it matches the x received above, to confirm the validity of the user who is to be authenticated by regarded as legitimate if they pass the verification User authentication method
Law . 2. A method for confirming the legitimacy of a user, wherein a prime number p, q, q is set in advance as one of factors of p−1, and a device (hereinafter referred to as a user) of a user (authenticatee). Authenticator device)
And random numbers g ₁ and g _{2 of order} q and 0 or more and q-1 or more
Generating a secret key s1, s2 consisting random below, these secret <br/> Mitsukagi s1, s2, with the prime number p and the random number g _1, g _2, the public key v = g ₁ ^-s1 · g ₂ ^-s2 m od p a total of
And the identification information ID of the person to be authenticated and the p, g ₁ , g
₂ and v are registered in a management list, and in the authentication processing stage, the device to be authenticated has random numbers r1 and r2.
Is generated, and from these p, g ₁ and g ₂ , x = g ₁ ^r1
· G ₂ calculates the ^r2 mod p, the x of that transmitted to the verifier device together with the identification information ID of the person to be authenticated <br/>, verifier device which has received these x, ID is a random number e produced, it was sent to the person to be authenticated device, the person to be authenticated device that has received the e is the e, the r
1, r2, secret key (s1, s2) , from the above q , y1 = r
1 + e · s1 mod q, y2 = r2 + e · s2 m
od q was calculated respectively, these (y1, y2) and transmitted to the verifier apparatus, these (y1, y2) the verifier device which has received the public key v searching than the management list for the ID , the v and the above-mentioned _{p, g 1, g 2,} e, y1, y 2 good Ri w = g ₁
^y1 · g ₂ ^y2 · v computes the ^e mod p, confirm the validity of the person to be authenticated by the result w verifies if it matches the x received above, regarded as legitimate if they pass the verification the user authentication method which is characterized in that.