Enciphering method, deciphering method and certifying method

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates to an enciphering method, a deciphering method and a certifying method, and more particularly to an enciphering method, a deciphering method and a certifying method adapted for use in various information services.

Related Background Art

The ciphers can be generally classified into (A) common ciphers and (B) public key ciphers.

The common cipher (A) employs a same key secretly owned by the transmitter and the receiver, and is also called the common key cipher or the secret key cipher.

In the public key cipher (B), the enciphering key and the deciphering key are mutually different, and the enciphering key is made publicly open while the deciphering key is held secret. In the following there will be given an explanation on the public key cipher, with respect to (a) features, (b) protocol, (c) representative example, and (d) RSA cipher as a specific example thereof.

(a) Features of the public key cipher

<ul id="ul0001" list-style="none" compact="compact"><li>1. Since the enciphering key and the deciphering key are different and the enciphering key can be made public, it is not necessary to deliver the enciphering key in secret and the key delivery is made easier.</li><li>2. Since the enciphering key of each user is made public, each user is only required to maintain the deciphering key secret.</li><li>3. There can be realized a certifying function allowing the receiver to confirm that the transmitter of the transmitted message is not false and that the transmitted message has not been tampered with.</li></ul>

(b) Protocol of the public key cipher

For a message M to be communicated, with a public enciphering key k^P (hereinafter called public key) for defining an enciphering operation E(k^P, M) and a secret deciphering key k^S for defining a deciphering operation D(k^S, M), the public key cipher algorithm in the first place satisfies the following two conditions: <ul id="ul0002" list-style="none" compact="compact"><li>(1) If the public key k^P is known, the enciphering operation E(k^P, M) can be easily calculated. Also if the secret key k^S is known, the deciphering operation D(k^S, M) can be easily calculated.</li><li>(2) In case the secret key k^S is not known, even if the above-mentioned public key k^P and the calculating procedure C = E(k^P, M) for the above-mentioned enciphering operation E are known, the determination of the message M is difficult in consideration of the amount of calculation. The secret communication can be realized by satisfying the following condition (3), in addition to the foregoing conditions (1) and (2): </li><li>(3) The enciphering operation E(k^P, M) can be defined for all the messages (plain texts) M and there stands a relation:<maths id="math0001"><math display="block"><mrow><msup><mrow><mtext>D(k</mtext></mrow><mrow><mtext>S</mtext></mrow></msup><msup><mrow><mtext>, E(k</mtext></mrow><mrow><mtext>P</mtext></mrow></msup><mtext>, M)) = M</mtext></mrow></math><img file="EP0802654B1_D0001.tif" /></maths> Thus, since the k^P is made public, anybody can execute the calculation of the enciphering operation E(k^P, M), but the restoration of the message M through the deciphering operation D(k^S, E(k^P, M)) can only be made by the person who has the secret key k^S. On the other hand, the certified communication can be realized by satisfying the following condition (4), in addition to the foregoing conditions (1) and (2): </li><li>(4) D(k^S, M) can be defined for all the messages (plain texts) M and there stands a relation:<maths id="math0002"><math display="block"><mrow><msup><mrow><mtext>E(k</mtext></mrow><mrow><mtext>P</mtext></mrow></msup><msup><mrow><mtext>, D(k</mtext></mrow><mrow><mtext>S</mtext></mrow></msup><mtext>, M)) = M</mtext></mrow></math><img file="EP0802654B1_D0002.tif" /></maths></li></ul>

The deciphering operation D(k^S, M) can be calculated only by the proper holder of the secret key k^S, and, even if another person pretends to be such proper holder of the secret key k^S by calculating D(k^S', M) with a false secret key k^S', the receiver can confirm that the received information is false since E(k^P, D(k^S' , M)) ≠ M. Also if D(k^S, M) is tampered with, there results E(k^P, D(k^S, M)') ≠ M, so that the receiver can confirm that the received information is improper.

In the following there will be shown the protocols of secret communication, certified communication and secret communication with signature from a transmitter A to a receiver B by the public key cipher, wherein the transmitter A is assumed to have a secret key k^S_A and a public key k^P_A, and the receiver B is assumed to have a secret key k^S_B and a public key k^P_B.

Secret communication

The secret communication of a message (plain text) M from the transmitter A to the receiver B is executed in the following procedure.

At first, in a step 1, the transmitter A enciphers the message M with the public key k^P_B of the receiver B and sends the cipher text C to the receiver B, wherein:<maths id="math0003"><math display="block"><mrow><msup><mrow><mtext>C = E(k</mtext></mrow><mrow><mtext>P</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>B</mtext></mrow></msub><mtext>, M).</mtext></mrow></math><img file="EP0802654B1_D0003.tif" /></maths>

Then, in a step 2, the receiver B deciphers the received cipher text C with his own secret key k^S_B to obtain the original plain text M by:<maths id="math0004"><math display="block"><mrow><msup><mrow><mtext>M = D(k</mtext></mrow><mrow><mtext>S</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>B</mtext></mrow></msub><mtext>, C).</mtext></mrow></math><img file="EP0802654B1_D0004.tif" /></maths>

Since the public key k^P_B of the receiver B is made public to unspecified plural persons, the secret communication to the receiver B can be made not only by the transmitter A but also by any other person.

Certified communication

The certified communication of a message (plain text) M from the transmitter A to the receiver B is executed in the following procedure.

At first, in a step 1, the transmitter A generates a transmission text S with his secret key k^S_A of the transmitter and sends it to the receiver B, wherein:<maths id="math0005"><math display="block"><mrow><msup><mrow><mtext>S = D(k</mtext></mrow><mrow><mtext>S</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>A</mtext></mrow></msub><mtext>, M).</mtext></mrow></math><img file="EP0802654B1_D0005.tif" /></maths>

The transmission text S mentioned above is called a signature text, and the operation of obtaining such signature text S is called signing.

Then, in a step 2, the receiver B executes the restoring conversion of the signature text S with the public key k^P_A of the transmitter A, thereby obtaining the original plain text M by:<maths id="math0006"><math display="block"><mrow><msup><mrow><mtext>M = E(k</mtext></mrow><mrow><mtext>P</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>A</mtext></mrow></msub><mtext>, S)</mtext></mrow></math><img file="EP0802654B1_D0006.tif" /></maths>

By the confirmation that the restored plain text M mentioned above constitutes a meaningful message, it is certified that the above-mentioned plain text M has certainly been transmitted from the transmitter A.

Since the public key of the transmitter A is made public to the unspecified plural persons, the signature text of the transmitter A can be certified not only by the receiver B but also any other person. Such certification is called digital signature.

Signed secret communication

The signed secret communication of a message (plain text) M from the transmitter A to the receiver B is executed in the following procedure.

At first, in a step 1, the transmitter A prepares a signed text S by signing the message M with the secret key k^S_A of the transmitter A, wherein:<maths id="math0007"><math display="block"><mrow><msup><mrow><mtext>S = D(k</mtext></mrow><mrow><mtext>S</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>A</mtext></mrow></msub><mtext>, M).</mtext></mrow></math><img file="EP0802654B1_D0007.tif" /></maths>

Then the transmitter A enciphers the signed text S with the public key k^P_B of the receiver B and sends the cipher text C to the receiver B, wherein:<maths id="math0008"><math display="block"><mrow><msup><mrow><mtext>C = E(k</mtext></mrow><mrow><mtext>P</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>B</mtext></mrow></msub><mtext>, S).</mtext></mrow></math><img file="EP0802654B1_D0008.tif" /></maths>

Then, in a step 2, the receiver B deciphers the cipher text C with the secret key k^S_B of the receiver B to obtain the signed text S by:<maths id="math0009"><math display="block"><mrow><msup><mrow><mtext>S = D(k</mtext></mrow><mrow><mtext>S</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>B</mtext></mrow></msub><mtext>, C).</mtext></mrow></math><img file="EP0802654B1_D0009.tif" /></maths>

Also the receiver B executes the restoring conversion of the signed text S with the public key k^P_A of the transmitter A, thereby obtaining the original plain text M by:<maths id="math0010"><math display="block"><mrow><msup><mrow><mtext>M = E(k</mtext></mrow><mrow><mtext>P</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>A</mtext></mrow></msub><mtext>, S).</mtext></mrow></math><img file="EP0802654B1_D0010.tif" /></maths>

By the confirmation that the restored plain text M mentioned above constitutes a meaningful message, it is certified that the above-mentioned plain text M has certainly been transmitted from the transmitter A.

The order of applications of the functions in the foregoing steps of the signed secret communication may also be inverted. More specifically, in addition to the above-mentioned procedure: <ul id="ul0003" list-style="none" compact="compact"><li>Step 1: C = E(k^P _B, D(k^S _A, M))</li><li>Step 2: M = E(k^P _A, D(k^S _B, C))</li></ul> the signed secret communication can also be realized by the following procedure: <ul id="ul0004" list-style="none" compact="compact"><li>Step 1: C = D(k^S _A, E(k^P _B, M))</li><li>Step 2: M = D(k^S _B, E(k^P _A, C))</li></ul>

(c) Specific example of public key cipher

As it is difficult to explain the individual cipher systems, in the following there will be explained the RSA cipher system as a specific example. The RSA cipher was invented by Rivest, Shamir and Adleman of MIT and was named after their names.

The RSA cipher is presently one of the most promising public key ciphers. In the following there will be explained the basic principle of the RSA cipher, in the order (1) key generation, (2) enciphering and (3) deciphering.

(1) Key generation

The public key and the secret key are determined by the following algorithm. <ul id="ul0005" list-style="none" compact="compact"><li>1. Mutually different large prime numbers p, q are arbitrarily selected and the product n thereof is calculated by:<maths id="math0011"><math display="block"><mrow><mtext>n = pq</mtext></mrow></math><img file="EP0802654B1_D0011.tif" /></maths></li><li>2. The least common multiple L of (p-1) and (q-1) is calculated, and there is selected an arbitrary integer e, which is relatively prime to thus calculated least common multiple L and is smaller than the least common multiple by:<maths id="math0012"><math display="block"><mrow><mtext>L = LCM((p-1), (q-1))</mtext></mrow></math><img file="EP0802654B1_D0012.tif" /></maths><maths id="math0013"><math display="block"><mrow><mtext>GCD(e, L) = 1</mtext></mrow></math><img file="EP0802654B1_D0013.tif" /></maths><maths id="math0014"><math display="block"><mrow><mtext>1 &lt; e &lt; L</mtext></mrow></math><img file="EP0802654B1_D0014.tif" /></maths> wherein LCM indicates the least common multiple and GCD indicates the greatest common divisor.</li><li>3. The following congruence equation is solved, based on the arbitrary integer e and the least common multiple L determined in the foregoing step 2:<maths id="math0015"><math display="block"><mrow><mtext>ed ≡ 1(modL)</mtext></mrow></math><img file="EP0802654B1_D0015.tif" /></maths></li></ul>

The values (e, n) thus determined are used as the enciphering key while those (d, n) are used as the deciphering key, in which e and n are the public keys while d is the secret key.

(2) Enciphering

For a plain text M and a cipher text C, the enciphering algorithm E is represented by:<maths id="math0016"><math display="block"><mrow><msup><mrow><mtext>C = E(M) = M</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><mtext>modn</mtext></mrow></math><img file="EP0802654B1_D0016.tif" /></maths> wherein each of the plain text M and the cipher text C is an integer between 0 and n-1. If the original message is larger than the integer n, it is divided into blocks of a size n and the enciphering or the deciphering is applied in succession to such blocks.

(3) Deciphering

The deciphering algorithm D is represented by:<maths id="math0017"><math display="block"><mrow><msup><mrow><mtext>M = D(C) = C</mtext></mrow><mrow><mtext>d</mtext></mrow></msup><mtext>modn</mtext></mrow></math><img file="EP0802654B1_D0017.tif" /></maths>

In case of deciphering the plain text M enciphered by the above-mentioned enciphering algorithm E(M) = M^emodn:<maths id="math0018"><math display="block"><mrow><msup><mrow><mtext>D(C) = D(E(M)) ≡ (M</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>d</mtext></mrow></msup><msup><mrow><mtext> ≡ M</mtext></mrow><mrow><mtext>ed</mtext></mrow></msup><mtext> ≡ M(modn)</mtext></mrow></math><img file="EP0802654B1_D0018.tif" /></maths> so that the original plain text M can be obtained.

Based on the above-explained principle, the public key can be disclosed for example in a telephone directory and it is no longer necessary to maintain a key individually with each of the unspecified plural persons. Therefore, in contrast to the secret key cipher system in which a key has to be secretly shared by the partners of communication prior to the execution of the communication, the public key cipher system has an advantage that the management and use of the keys are easier.

However, most public key cipher systems are unable, because of the structural limitation thereof, to select arbitrary public keys, so that the public key has merely been a number which is meaningless to the persons concerned.

On the other hand, a serious problem will arise unless the proper correlation is maintained between the key and the corresponding entity (entity of communication which is the user or the computer).

More specifically there will result a situation where a document intended for a person A is erroneously delivered to a person B, or a situation of "pretense" where a signature intended to be obtained from a person A is obtained from another person B.

However, as long as the public key is a number meaningless to the involved persons, the correlation between an entity and its public key cannot be verified directly by other arbitrary entities, so that the keys have been managed by a key list to be publicized by a reliable organization.

On the other hand, "the cipher system and the signature method based on ID", capable of employing an ID (personalized identification information such as name or address) as the public key, has been proposed for example by A. Shamir, "Identity-based cryptosystems and signature schemes", Proc. of Crypto '84, 1984 and by T. Okamoto and A. Shiraishi, "Safe user verifying method by single management information", IN83-92, 1984.

Such systems, having a structure allowing to use the ID of the entity as the public key, allows the user to understand the public key as the ID information. Since the correctness of the public key can be understood in easier manner in comparison with other public key cipher systems, signature schemes, secret key cipher systems or identification systems, there can be dispensed with the list of the keys.

As an example of the "ID-based cipher systems" mentioned above, there will be explained, in the following, the system proposed by S. Tsujii, T. Ito and K. Kurosawa, "ID-based cryptosystems using discrete logarithm problem" Elect. Lett., Vol. 23, No. 24, 1987. Preparation

At first, in a step 1, the center publicizes n-dimensional vectors: <ul id="ul0006" list-style="none" compact="compact"><li>a = (a1 , a2 , ..., an )</li><li>h = (h₁, h₂, ...,h_n)</li><li>h₁ = g^almodp (1 ≤ 1 ≤ n)</li></ul> based on a prime number p, an original element g of a Galois field GF(p) and a Galois field GF(p), and a one-dimensional function f.

Then, in a step 2, an entity i registers its ID: <ul id="ul0007" list-style="none" compact="compact"><li>ID_i = (x_i1, x_i2, ..., x_ik)</li><li>(k &lt; n), x_i1∈{0, 1} (i ≤ 1 ≤ k)</li></ul> at the center.

Then, in a step 3, the center determines a modified ID:<maths id="math0019" num="(1)"><math display="block"><mrow><msub><mrow><mtext>EID</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext></mtext><munder accentunder="true"><mrow><mtext>Δ</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext> f(ID</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>) = (y</mtext></mrow><mrow><mtext>i1</mtext></mrow></msub><msub><mrow><mtext>, y</mtext></mrow><mrow><mtext>i2</mtext></mrow></msub><msub><mrow><mtext>, ..., y</mtext></mrow><mrow><mtext>in</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0802654B1_D0019.tif" /></maths><maths id="math0020"><math display="block"><mrow><msub><mrow><mtext>y</mtext></mrow><mrow><mtext>i1</mtext></mrow></msub><mtext>∈{0,1}   (i ≤ 1 ≤ n)</mtext></mrow></math><img file="EP0802654B1_D0020.tif" /></maths> and calculates a secret key Si of the entity i:<maths id="math0021"><img file="EP0802654B1_D0021.tif" /></maths> and sends it to the entity i through a safe communication path.

Enciphering

The transmitting entity j at first determines an arbitrary integer k, which is a secret of the transmitter only. Then it enters the ID of the receiving entity i into the enciphering apparatus, which generates EID_i according to the foregoing function (1) and calculates the product Z_i of the elements h₁, for which the corresponding y_i1 is 1, among the elements h, namely:<maths id="math0022"><img file="EP0802654B1_D0022.tif" /></maths>

Z_i can in fact be represented by:<maths id="math0023"><img file="EP0802654B1_D0023.tif" /></maths>

The transmitting entity j prepares a cipher text:<maths id="math0024"><math display="block"><mrow><msup><mrow><mtext>C ≡ (g</mtext></mrow><mrow><mtext>k</mtext></mrow></msup><msub><mrow><mtext>, MZ</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>k</mtext></mrow></msup><mtext>)mod p</mtext></mrow></math><img file="EP0802654B1_D0024.tif" /></maths> from a plain text M according to the ElGamal cipher system, and sends the cipher text to the receiving entity i.

Deciphering

The receiving entity i calculates the S_i-th power of the first term g^k of the received cipher text C to obtain:<maths id="math0025"><math display="block"><mrow><msup><mrow><mtext>(g</mtext></mrow><mrow><mtext>k</mtext></mrow></msup><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>Si</mtext></mrow></msup><msup><mrow><mtext> ≡ (g</mtext></mrow><mrow><mtext>Si</mtext></mrow></msup><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>k</mtext></mrow></msup><msub><mrow><mtext> ≡ Z</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>k</mtext></mrow></msup><mtext> mod p</mtext></mrow></math><img file="EP0802654B1_D0025.tif" /></maths> and divides the second term with Z_i^k to obtain the plain text M.

In the following, as an example of the "ID-based signature scheme", there will be explained a system proposed by A. Fiat and A. Shamir, "How to prove yourself: practical solution to identification and signature problems", Proc. Of Crypt '86, 1986.

System preparation

The center selects prime numbers p and q, and publicizes the product N thereof and a one-way function f for converting an arbitrary character train into [O, N).

An entity A receives a secrecy s_Aj for its identifier I_A from the center. The center confirms the correctness of I_A of the entity, then determines:<maths id="math0026"><math display="block"><mrow><msub><mrow><mtext>ID</mtext></mrow><mrow><mtext>Aj</mtext></mrow></msub><msub><mrow><mtext> = f (I</mtext></mrow><mrow><mtext>A</mtext></mrow></msub><mtext>, j)</mtext></mrow></math><img file="EP0802654B1_D0026.tif" /></maths> wherein j is a small parameter, then calculates:<maths id="math0027"><math display="block"><mrow><msub><mrow><mtext>s </mtext></mrow><mrow><mtext>Aj</mtext></mrow></msub><msub><mrow><mtext> = 1/√I D</mtext></mrow><mrow><mtext>Aj</mtext></mrow></msub><mtext>m o d N</mtext></mrow></math><img file="EP0802654B1_D0027.tif" /></maths> and transfers it to the entity A (for the purpose of simplicity, representation is made as j = 1, 2, 3, ..., k).

Generation of signature

The entity A signs the plain text M.

In a step 1, the entity A generates random numbers:<maths id="math0028"><math display="block"><mrow><msub><mrow><mtext>γ</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>, ..., γ</mtext></mrow><mrow><mtext>t</mtext></mrow></msub><mtext> ∈[0, N)</mtext></mrow></math><img file="EP0802654B1_D0028.tif" /></maths> and calculates:<maths id="math0029"><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> = γ</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> mod N</mtext></mrow></math><img file="EP0802654B1_D0029.tif" /></maths>

Then, in a step 2, the entity A calculates:<maths id="math0030"><math display="block"><mrow><msub><mrow><mtext>f (M, x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>, ..., x</mtext></mrow><mrow><mtext>t</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0802654B1_D0030.tif" /></maths> and takes the initial kt bits as the value of e_ij, wherein:<maths id="math0031"><math display="block"><mrow><mtext>(1 ≤ i ≤ t, 1 ≤ j ≤ k)</mtext></mrow></math><img file="EP0802654B1_D0031.tif" /></maths>

In a next step 3, the entity A calculates:<maths id="math0032"><img file="EP0802654B1_D0032.tif" /></maths> and takes I_A, M, e_ij and y_i as the digital signature.

Verification of signature

An entity B, receiving I_A, M, e_ij and y_i, calculates:<maths id="math0033"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext>Aj</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">I</mtext></mrow><mrow><mtext mathvariant="italic">A</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>) (1 ≤ </mtext><mtext mathvariant="italic">j</mtext><mtext> ≤ </mtext><mtext mathvariant="italic">k</mtext><mtext>),</mtext></mrow></math><img file="EP0802654B1_D0033.tif" /></maths><maths id="math0034"><img file="EP0802654B1_D0034.tif" /></maths> and confirms that the initial kt bits of f(M, z₁, ..., z_i) coincide with e_ij.

In the following, there will be explained an example of an ID-based shared key (key delivery) system.

Preparation

The center generates a modulus n, a public key e and a secret key d. The center is assumed to be reliable and d is maintained as the secret of the center.

Entry of user

The center transfers (ID_x, s_x, n, e, g) to a user X, wherein g is a constant, and s_X is represented by:<maths id="math0035"><math display="block"><mrow><msub><mrow><mtext>s</mtext></mrow><mrow><mtext>X</mtext></mrow></msub><msub><mrow><mtext> = ID</mtext></mrow><mrow><mtext>X</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>-d</mtext></mrow></msup><mtext> mod n</mtext></mrow></math><img file="EP0802654B1_D0035.tif" /></maths>

Generation of work key

In the following it is assumed that a key is generated between entities A and B. In a step 1, the entity A generates a random number r_A and sends:<maths id="math0036"><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>A</mtext></mrow></msub><msub><mrow><mtext> = s</mtext></mrow><mrow><mtext>A</mtext></mrow></msub><msup><mrow><mtext> • g</mtext></mrow><mrow><mtext>rA</mtext></mrow></msup><mtext> mod n</mtext></mrow></math><img file="EP0802654B1_D0036.tif" /></maths> to the entity B, which similarly generates a random number r_B and provides the entity A with:<maths id="math0037"><math display="block"><mrow><msub><mrow><mtext>x</mtext></mrow><mrow><mtext>B</mtext></mrow></msub><msub><mrow><mtext> = s</mtext></mrow><mrow><mtext>B</mtext></mrow></msub><msup><mrow><mtext> • g</mtext></mrow><mrow><mtext>rB</mtext></mrow></msup><mtext> mod n</mtext></mrow></math><img file="EP0802654B1_D0037.tif" /></maths>

In a step 2, the entity A obtains:<maths id="math0038"><math display="block"><mrow><msub><mrow><mtext>WK</mtext></mrow><mrow><mtext>AB</mtext></mrow></msub><msub><mrow><mtext> = (ID</mtext></mrow><mrow><mtext>B</mtext></mrow></msub><msup><mrow><mtext>•x</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>B</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>rA</mtext></mrow></msup><msup><mrow><mtext> = g</mtext></mrow><mrow><mtext>e•rA•rB</mtext></mrow></msup><mtext>mod n</mtext></mrow></math><img file="EP0802654B1_D0038.tif" /></maths> while the entity B obtains:<maths id="math0039"><math display="block"><mrow><msub><mrow><mtext>WK</mtext></mrow><mrow><mtext>AB</mtext></mrow></msub><msub><mrow><mtext> = (ID</mtext></mrow><mrow><mtext>A</mtext></mrow></msub><msup><mrow><mtext>•x</mtext></mrow><mrow><mtext>e</mtext></mrow></msup><msub><mrow><mtext> </mtext></mrow><mrow><mtext>A</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>rB</mtext></mrow></msup><msup><mrow><mtext> = g</mtext></mrow><mrow><mtext>e•rA•rB</mtext></mrow></msup><mtext>mod n</mtext></mrow></math><img file="EP0802654B1_D0039.tif" /></maths>

In the following, as an example of the "ID-based identification confirmation system", there will be explained the foregoing system proposed by A. Fiat and A. Shamir, "How to prove yourself: practical solution to identification and signature problems", Proc. Of Crypt '86, 1986.

System preparation

This is the same as that described in connection with "ID-based signature scheme".

Confirmation of identity

An entity A proves that it is truly A, to another entity B.

In a step 1, the entity A sends I_A to the other entity B.

Then, in a step 2, the other entity B calculates f(I_A, j) (j = 1, 2, ..., k).

Then, following steps 3 to 6 are repeated from i = 1 to i = t.

In the step 3, the entity A generates a random number r₁ ∈[0, n) and sends x_i = r_i² mod n to the other entity B.

In the step 4, the other entity B sends a random binary vector (e_i1, ..., e_ik) to the entity A.

In the step 5, the entity A sends, to the other entity B:<maths id="math0040"><img file="EP0802654B1_D0040.tif" /></maths>

In the step 6, the other entity B confirms:<maths id="math0041"><img file="EP0802654B1_D0041.tif" /></maths>

However, the pretense may not be unavoidable even if the ID is taken as the public key. For example, in the case of effecting communication by exchanging the ID with a business partner, there can be considered a case where the given ID is not of such business partner itself but of another similar person or of an entirely different person.

Stated differently, even in the "ID-based cipher systems and signature schemes", though the public key has an understandable meaning, the adequacy of the given ID cannot be securely identified from the ID alone. Consequently the proper correspondence between the entity providing the public key (ID) and the provided public key (ID) is still not guaranteed, as in other public key systems.

It is known from WO-A-9608093 to generate a public key by manipulation of fingerprint information of a subscriber.

It is also known from PATENT ABSTRACTS OF JAPAN vol. 012, no. 125 (P-691), 19 April 1988 &amp; JP 62 249276A (HITACHI LTD), 30 October 1987 to synthesise an RSA decoding key from a cipher number input by a user and decoding key data stored in a memory card. The key is used to decode encoded facial image data to be compared with image data obtained from a camera to allow certification of an individual.

It is also known from DE-A-4243908 to process observed identification data to reduce the amount of attribute information.

Aspects of the invention are set out in the appended claims.

An embodiment of the present invention provides an enciphering method, a deciphering method and a certifying method allowing secure confirmation of the correspondence between the entity itself and its public key, thereby preventing so-called pretense.

In an enciphering method, the enciphering employs information correlated with an attribute of the entity as a key. In a preferred embodiment, the above-mentioned attribute is the biophysical attribute information of the entity.

Also according to an embodiment, there is provided a certifying method which is featured by judging the adequacy of the correspondence between the key and the entity, based on the result of comparison of the attribute information of the entity and the information provided as the key of the entity.

Still other objects of the present invention, and the features thereof, will become fully apparent from the following detailed description of the embodiments, to be taken in conjunction with the attached drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

<ul id="ul0008" list-style="none" compact="compact"><li>Fig. 1 is a schematic view showing the concept of an embodiment of the present invention;</li><li>Fig. 2 is a schematic view showing an embodiment in which the concept shown in Fig. 1 is applied to the confirmation of identity;</li><li>Fig. 3 is a schematic view showing an embodiment in which the concept shown in Fig. 1 is applied to the enciphering; and</li><li>Fig. 4 is a view showing a hardware configuration of an enciphering apparatus utilizing the concept of the present invention.</li></ul>

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Now the present invention will be clarified in detail by embodiments thereof, with reference to the attached drawings.

At first an embodiment will be explained with reference to a concept view shown in Fig. 1. In Fig. 1, there are shown an entity 11 that can be a user or a terminal device of various types, and a recording medium 12 (hereinafter called data carrier) such as an IC card, held by the entity 11.

The present embodiment employs attribute information B₁₁ specific to the entity 11 as the public key K₁₁ to be employed in one or plurality of the "ID-based enciphering system", "ID-based signature system", "ID-based shared key system" and "ID-based identification system" explained in the foregoing, and the center of the system records the above-mentioned attribute information B₁₁ in the data carrier 12 after the confirmation of the correspondence between the attribute information B₁₁ and the entity 11. In case the entity 11 is a user (person), the attribute information mentioned above can be the information on the biophysical (biomedical) features of such entity (user).

Consequently, in verifying the public key K₁₁ of the entity 11, the verifier reads the public key K₁₁, namely the attribute information B₁₁ of the entity 11, from the data carrier 12 provided by the entity 11 by means of a reader 13, then observes the attribute information of the entity 11 by an observing device 14 and compares thus obtained information, thereby confirming that the entity 11 is the proper (true) owner of the carrier 12 or that the biophysical attribute information recorded on the data carrier 12 is the public key of the entity 11 and being allowed to proceed to various subsequent operations.

The result <img file="EP0802654B1_D0042.tif" /> of the above-mentioned observation is compressed in conversion means 16 with a one-way function such as a hash function to obtain a converted value h(<img file="EP0802654B1_D0043.tif" />), and it is verified whether the value h(<img file="EP0802654B1_D0044.tif" />) is equal to the attribute information B₁₁ of the entity 11, read from the data carrier 12.

In this case, the above-mentioned attribute information B₁₁ is obtained by a conversion process similar to that in the converting means 16. In such case, data indicating the processing method (for example data indicating the kind of the function) are recorded in the data carrier 12 and are informed to the converter 16.

By constituting the attribute information B₁₁ with the data obtained by compressing the biophysical feature of a person, the data of a large data amount, such as the data of the face of the person, can also be stored in the carrier 12 such as an IC card. Also the comparison of such compressed data allows to reduce the time required therefor.

In the above-explained embodiment, the attribute information B₁₁ itself is employed as the public key K₁₁, but such public key K₁₁ may become undesirably known by secret observation of the attribute information. In such case, the public key K₁₁ may be obtained by applying a process of a predetermined algorithm to the attribute information B₁₁.

In such case, the public key K₁₁ cannot be obtained from the attribute information B₁₁ as long as the above-mentioned algorithm remains secret.

In the following there will be explained, with reference to Fig. 2, a more specific embodiment utilizing the above-explained concept for the personal identification. In Fig. 2 there are shown a first entity 21, a second entity 22, a data carrier 23 storing the public key provided by the second entity 22, a computer 24, and a display 25.

The data carrier 23, provided as the public key by the second entity 22, is a recording medium such as a magnetic card, an IC card, a floppy disk or a CD-ROM. It is assumed, in the present embodiment, that the biophysical attribute information of the entity is the face (or photographic data thereof) of the entity and that the data carrier 23 is a floppy disk.

System preparation

The center (not shown) selects prime numbers p, q, and publicizes the product N thereof, a one-way function f for converting an arbitrary character train into [O, N) and a program for displaying the photographic data of the face.

The entity A, joining the system, receives secret s_Aj corresponding to such facial photographic data from the center in the following manner.

The center confirms that the above-mentioned entity A and the facial photographic data I_A have a proper correspondence, then determines:<maths id="math0042"><math display="block"><mrow><msub><mrow><mtext>ID</mtext></mrow><mrow><mtext>Aj</mtext></mrow></msub><msub><mrow><mtext> = f(I</mtext></mrow><mrow><mtext>A</mtext></mrow></msub><mtext>, j)</mtext></mrow></math><img file="EP0802654B1_D0045.tif" /></maths> wherein j is a small parameter, and calculates:<maths id="math0043"><math display="block"><mrow><msub><mrow><mtext>s </mtext></mrow><mrow><mtext>Aj</mtext></mrow></msub><msub><mrow><mtext> = 1/ √I D </mtext></mrow><mrow><mtext>Aj</mtext></mrow></msub><mtext>m o d N</mtext></mrow></math><img file="EP0802654B1_D0046.tif" /></maths> (for the purpose of simplicity representation is made as j = 1, ..., k).

Then the above-mentioned secret s_Aj is transferred to the entity A by any method that is available only to the entity A (for example by storage in an IC card of which the secret code number is only known to the entity A). The entity A retains the facial photographic data I_A stored in its data carrier.

Confirmation of public key

In the following there will be explained the procedure, to be executed by the entity 21, for confirming the identity of the second entity 22 that has undergone a procedure similar to the above-explained one for the entity A.

The first entity 21 receives the data carrier 23 from the second entity 22, and confirms that the public key provided therein properly corresponds to the second entity 22 itself in the following manner.

The first entity 21 reads the public key (facial photographic data) I_A by a floppy disk drive connected to the computer 24, and displays such data on the display 25 by the facial photographic data displaying program. Then the first entity itself visually compares such display with the face of the second entity 22. In this manner the first entity 21 itself can securely judge whether the second entity 22 properly corresponds to the public key (facial photographic data) provided thereby.

Confirmation of identity

In an embodiment in which the concept of the present embodiment is applied to the identity confirming method explained above, the ID is the biophysical attribute information of the entity, and any physical attribute information enabling direct onsite confirmation by human observation can be employed as the public key.

In addition to the facial photograph, there may be employed, for example, the handwriting, fingerprint, palm print or voice print, which can be directly confirmed by persons, utilizing an image displaying program or a voice reproducing program on the computer 24, and such data are recorded as the public key in the data carrier 23.

Also such principle is applicable not only to the ID-based identification system but naturally also to the ID-based enciphering system, the ID-based signature system, or the ID-based shared key system, or plurality thereof.

In the following there will be explained, with reference to Fig. 3, another embodiment in which the concept of the present invention is applied to an enciphering system. This embodiment employs an input device instead of the human eyes.

In Fig. 3, there are shown a first entity 31, a second entity 32, a data carrier 33 recording the public key provided by the second entity 32, a computer 34, a display 35 and an input device 36.

The present embodiment employs the fingerprint and an IC card instead of the facial photograph and the floppy disk in the foregoing embodiment.

System preparation

In a step 1, the center publicizes n-dimensional vectors: <ul id="ul0009" list-style="none" compact="compact"><li>a = (a₁ , a₂ , ..., a_n)</li><li>h = (h₁, h₂, ..., h_n)</li><li>h₁ = g^almodp (1 ≤ 1 ≤ n)</li></ul> defined by a prime number p, an original element g of a Galois field GF(p) and a Galois field GF(p), also a one-way function f and a fingerprint comparing program.

In a step 2, an entity i, joining the system, registers its fingerprint data: <ul id="ul0010" list-style="none" compact="compact"><li>ID₁ = (x_i1, x_i2, ..., x_ik)</li></ul> wherein:<maths id="math0044"><math display="block"><mrow><msub><mrow><mtext>(k &lt; n), x</mtext></mrow><mrow><mtext>il</mtext></mrow></msub><mtext>∈{0, 1} (i ≤ 1 ≤ k)</mtext></mrow></math><img file="EP0802654B1_D0047.tif" /></maths> at the center.

Then, in a step 3, the center confirms the correspondence between the entity i and its fingerprint data ID_i, then determines:<maths id="math0045" num="(2)"><math display="block"><mrow><msub><mrow><mtext>EID</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext></mtext><munder accentunder="true"><mrow><mtext>Δ</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext> f(ID</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>) = (y</mtext></mrow><mrow><mtext>i1</mtext></mrow></msub><msub><mrow><mtext>, y</mtext></mrow><mrow><mtext>i2</mtext></mrow></msub><msub><mrow><mtext>, ..., y</mtext></mrow><mrow><mtext>in</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0802654B1_D0048.tif" /></maths><maths id="math0046"><math display="block"><mrow><msub><mrow><mtext>y</mtext></mrow><mrow><mtext>i1</mtext></mrow></msub><mtext>∈{0, 1}   (i ≤ 1 ≤ n)</mtext></mrow></math><img file="EP0802654B1_D0049.tif" /></maths> also calculates the secret key S_i of the entity i:<maths id="math0047"><img file="EP0802654B1_D0050.tif" /></maths> and sends it to the entity i through a safe communication path.

In a step 4, the entity i stores the fingerprint data ID_i, in its data carrier.

Confirmation of public key

Now there will be explained the case of cipher communication by the first entity 31, with the second entity 32 that has undergone a process similar to the above-explained one for the entity i.

The first entity 31 receives the data carrier (ID card) 33 and confirms that the public key provided therein properly corresponds to the second entity 32 itself, in the following manner.

The first entity 31 reads the public key (fingerprint in this case) from the data carrier 33, utilizing an IC card reader connected to the computer 34. At the same time, the fingerprint of the second entity 32 is scanned by the input device 36 (for example a surface irregularity detector) connected to the computer 34, and thus scanned fingerprint of the second entity 32 is compared with the fingerprint data read as the public key by the fingerprint comparing program of the computer 34. Such procedure allows to judge whether the second entity 32 properly corresponds to the public key (fingerprint data) provided by the second entity 32.

Cipher communication

The first entity 31 executes the cipher communication with the second entity 32, by a procedure similar to that for the entity j in the "ID-based enciphering system" explained in the foregoing.

In the present embodiment, the biophysical attribute information of the entity constitutes the public key, and any attribute information allowing confirmation of the entity itself through the use of any device can be utilized as the public key.

In addition to the fingerprint explained above, there may be employed, for example, the palm print, handwriting, voice print, iris pattern or retina pattern may be selected as the public key. Such palm print, handwriting, voice print, iris pattern or retina pattern can be directly confirmed by an input device, such as a surface irregularity sensor, a pen tablet, a microphone or a camera, connected to the computer 34, and the data carrier 33 stores the data, obtained with such input device and suitably converted if necessary, as the public key. In case of rewriting the above-mentioned attribute information, there is preferably employed a security measure such as entry of a password representing the entity itself.

Also such principle is applicable not only to the ID-based enciphering system but naturally also to the ID-based signature system, the ID-based shared key system or the ID-based identification system, or plurality thereof.

In any of the foregoing embodiments, if the biophysical attribute information has a large data amount, the public key may be obtained by reducing the data amount of such information by a known compression function indicated as h() in Fig. 1 (for example a one-way function for projecting the input into a smaller random size).

Fig. 4 shows an example of the hardware configuration in which the concept of the present invention is applied to an enciphering apparatus or the like.

As shown in Fig. 4, the apparatus is composed of a microcomputer consisting of a CPU 1, a ROM 2 and a RAM 3 connected by a data bus 4.

There are also provided biophysical attribute information input means 5 such as an IC card reader or a scanner for entering the biophysical attribute information, display means 6 for displaying various information on an image display area, sound generation means 7 for generating various sound information, and a camera 8 for observing the entity.

The ROM 2 is used for storing various programs constituting function means of the above-mentioned units, while the RAM 3 is used for temporarily storing various data and as the work memory of the CPU 1.

The CPU 1 mechanically, optically or magnetically detects and recognizes the medium, such as an IC card, storing such attribute information, detects the attribute information by the biophysical attribute input means 5, also observes the entity by the camera 8 and executes a process of conversion and/or comparison according to the programs or algorithms stored in the ROM 2.

The camera 8 is adapted to normalize the data taken from a photo so as to obtain a predetermined size within the imaging angle, and the above-mentioned algorithm of comparison is adapted to absorb the fluctuation in size within a predetermined range, in the data obtained from the camera 8.

In such configuration, the microcomputer consisting of the CPU 1, ROM 2, RAM 3 and data bus 4 constitutes conversion means (converter) for compressing the biophysical attribute information of the entity, observation means (observing device) for observing the biophysical attribute information of the entity, comparison means (reader) for comparison with the key information provided as the key of the entity, judgment means (comparator) for judging the adequacy of the correspondence between the biophysical attribute information of the entity and the key information, and verification means for verifying whether the key information read from the medium storing the key information is equal to the observed biophysical attribute information of the entity, thereby providing an enciphering apparatus, a signing apparatus, a key sharing apparatus or an identity confirming apparatus utilizing the concept of the present invention.

Also in the present embodiment, in case the attribute information read from the carrier does not coincide with the data through the camera 8, such situation may be displayed on the display means 6, and, in consideration of the possibility of an improper use, the entity photographed by the camera 8 and the time of operation may be stored in the memory 3 or may be transmitted as a warning to another location through an unrepresented network. In this manner the system can prevent trouble and can assist the survey of a crime.

As explained in the foregoing, the present invention, utilizing the attribute information specific to the entity or the information obtained by suitable compression and/or conversion as the key or a key corresponding to such information, enables direct confirmation of the correspondence between the entity and the key through the physical attribute information mentioned above. Thus the present invention enables secure communication with the true entity person and can securely prevent pretense by any other third person. Also, even between the entities in mutually distant locations, the correspondence between the unseen entity and his public key can be confirmed as long as the communication line between the entities and the devices thereof are reliable.

Many widely different embodiments of the present invention may be constructed without departing from the scope of the present invention. It should be understood that the present invention is not limited to the specific embodiments described in the specification, except as defined in the appended claims.