Public key validation scheme for elliptic curve based cryptosystems

[0001] [Technical field to which the invention belongs] The present invention relates to the security of a communication system, and more particularly to a method (procedure) for validating parameters and keys in such a system. [0002] [Conventional technology] Information is sent and received between a set of communicators using a secure data communication system. At least part of the information exchanged is encrypted by the sender performing certain mathematical operations. Then, the receiver performs a complementary mathematical operation according to the above mathematical operation to break the code. In a public key or symmetric key system, communicators need to know some parameters in advance. For example, various methods and protocols have been devised so far, and validation of the sender's public key and identity is performed. Security of these systems Alternatively, validity depends on whether the signature is valid, if the system parameters (if any) are valid, the public key is valid, and the signature is verified. It will be secured as long as possible. In addition, the security of an asymmetric system is ensured that the system parameters (if any) are valid, the cryptographic public key is valid, the symmetric key is formatted as specified, and is symmetric. Only if the format is validated by recovery checks of the type key. [0003] On the other hand, the security of the key matching protocol is ensured that the system parameters (if any) are valid, the key matching public key is valid, and the shared secret and symmetric keys are generated as specified in the standard. Only if In all of the above, it is assumed that the public key or symmetric key, that is, the shared secret, is generated as specified by the protocol method and is valid. [0004] [Problems to be Solved by the Invention] However, problems arise when these parameters are fake or defective in some way. [0005] The following example will be used to explain what a defect in one or more parameters of a public key cryptosystem means. For example, consider the case of using a digital signature to show the authenticity of the sender. When recipient A receives the public key with a certificate from sender B, A confirms the certificate. Then, when B sends a signed message to A, A can confirm the signature and determine that further communication is possible. However, in this case, if B deliberately tampers with the public key, recipient A will not be able to identify this invalid public key. Similarly, assuming that Participant C generates a key pair, subsequently receives a public key certificate, and then Participant C above assumes that the public key contained in the certificate is valid. Consider sending a certificate followed by a signed message to B. Participant B can determine C's key information. As can be seen from both of the above cases, problems can arise due to the use of unauthenticated parameters when verifying the signature. [0006] In the key transmission protocol, the communicator A may mistakenly send a symmetric key to a different party. For example, when a communicator A receives a public key with a certificate from a sender B, A confirms the certificate and is encrypted with a public key-encrypted symmetric key and a symmetric key. Send a message to B. This approves A. Conversely, one of the correspondents, C, creates a key pair, obtains a public key certificate, and then sends it to A. In this case, A uses the public key to encrypt the symmetric key and message and sends it back to C. Therefore, in this case, C is approved. [0007] In the key matching protocol, one of the communicators, A, receives, for example, a certificated public key from B and sends A's certificated public key to B. A and B each check the other party's certificate and have symmetrical keys that match each other. In this example, A will be approved twice. [0008] As can be seen from the above example, even if the security of the public key system is ensured, the security of the system depends largely on one or both of the communicators, and the required predetermined key is actually used. It depends on being the given key of a particular algorithm. Typically, when the recipient receives a bit string, it considers the bit string to be the actual key required, which is especially problematic in symmetric key systems. That is, in a symmetric key system, typically any bit string of the correct size is interpreted as a key. Even if one bit in this bit string is different from a predetermined key, it is interpreted as another key, so that a valid crypto operation can be performed as long as the key is not incorrect. [0009] In an asymmetric private key system, the owner of the private key knows everything about the private key and can validate whether it is correct or not. However, if a third party sends the public key to the owner's system, whether the received key meets the mathematical requirements of the public key, or an operation using the requested public key. ) Is performed, a question arises as to whether or not the cryptographic operation ensures confidentiality. Only the owner knows, because the owner's system does not know for sure without inspection. [0010] As can be seen from the above, key establishment may not be secure. In a paper by Lim and Lee published in Crypto '97, the above problem was addressed in the Diffie-Hellman method by order. It was pointed out using an example that information about the other party's private key can be obtained when) uses an incorrect fake public key. In the RSA or Rabin method, the public key and the private key are used as a set of large prime functions to ensure security from the difficulty of factoring such a large number. These keys are generated from the product of two arbitrary large prime numbers. However, if n is a prime number and not the product of two prime numbers, then phi (n) = n-1 holds, so anyone can determine d from a fake "public key" (n, e). it can. These can be said to be problems that occur because the user of the public key cannot verify the validity of the arithmetic attributes that meet the requirements of the algorithm for the requested public key. [0011] An object of the present invention is to perform improved validation in a communication system having a security function. Furthermore, it is an object of the present invention to enable anyone to perform such validation at any time using only public information. [0012] [Means for solving problems] According to the method for verifying the validity of a digital signature in a public key communication system of the present invention, a step of confirming that the arithmetic attributes of the public key match the system algorithm and a step of confirming the digital signature are included. [0013] Further, a step of confirming the system parameters is provided. [0014] In addition, information indicating that validation has been performed to see if the requested public key is arithmetically consistent with the algorithm, and, where appropriate, the number of validations performed. A step is provided in which the indicated information is included in the certificate information. [0015] BEST MODE FOR CARRYING OUT THE INVENTION As shown in FIG. 1, the data communication system 10 includes a set of communicators, the set of communicators being a sender 12 and a receiver 14, which are connected to each other by a communication channel 16. The sender 12 and the receiver 14 have encryption units 18 and 20, respectively, that process digital information in preparation for transmission and reception via the communication channel 16. The data communication system 10 may further have a certificate authority (CA) 22. [0016] Hereinafter, a case where a public key algorithm is used as an embodiment of the present invention will be described. Key matching has the following six routines. That is, system parameter generation, system parameter validation, key pair generation, public key validation, shared secret derivation, and symmetric key derivation. In the above key verification process, anyone can verify the validity of the public key using only the public information at any time. These routines validate the range and order of the public key. If the validity of the public key is verified, it is logically possible that the corresponding private key exists, but it cannot be proved that it actually exists. [0017] The Elliptic Curve Digital Signature Algorithm (ECDSA) also contains six routines. That is, system parameter generation, system parameter validation, key pair generation, public key validation, signature generation, and signature verification (signature). verification). The first type of DSA, on the other hand, includes four routines: system parameter generation, key pair generation, signature generation, and signature verification. More recent DSAs include five routines: system parameter generation, (implicit) system parameter validation, key pair generation, signature generation, and signature verification. To validate the key, the DSA parameters p, q, and g are considered to have already been validated. Private key x, public key y y = g^xmod p. Then, for the range of y, the validity is verified by confirming that 1 <y <p, and for the order of y, y.^qValidate by confirming that mod p = 1. These validations confirm that a requested DSA public key meets the arithmetic requirements for such a key. Anyone can perform these validations at any time using only public information. [0018] RSA or Rabin signature algorithms generally include three routines: key pair generation, signature generation, and signature verification. Verifying the RSA public key (n, e) involves the following three steps: That is, first verify the validity of e, then verify the validity of n, and then verify that e and n are not inconsistent with each other. To verify the validity of the public index e, the index e is 2 e 2^(k-160)Take advantage of the fact that (k is the bit length of modulus n). This requirement that the range of the index e should be the specified range as described above makes the verification here particularly feasible. If e> 2, then e must be odd. Moreover, in the case of closed networks, it is known that the public index e should meet all other criteria. That is, for example, e must be an arbitrary number larger than 3, 65537, or 65537. These verifications may be performed to further validate the key. These validations may be included as part of the RSA public key partial validation routine specification. The verification of the exponent e above seems to be simple, but this verification confirms that e was selected before d, which is attempted to be selected by the RSA / Rabin algorithm. Because, by this verification, de = 1 mod (lcm (p-1, q-1)) ), And it turns out that e has at least 160 more zeros representing the number of digits than the method n, because it is not feasible if d is selected first. [0019] To verify the validity of method n, find the magnitude of n. It is known that n must contain exactly (1024 + 128s) bits (where s = 0,1,2,3, ... etc.). This can be easily verified and can be part of partial key authentication. Law n is the product of two prime numbers, and all prime numbers greater than 2 are odd, so even if we perform further validation on law n by determining whether law n is odd or not, Good. Therefore, the product of odd numbers is odd, so n must be odd. Furthermore, it is known that if e = 2 in the Rabin algorithm, then p = 3 mod n and q = 7 mod 8. From this, it must be n = pq = 21 mod 8 = 5 mod 8. This can be verified by confirming that n = 5 mod 8 when e = 2. In addition, n is perfect power ) Should not be. From this, it is certain that n consists of two different prime factors, and the validity can be verified by a simple test. The above validation is described in the "Handbook of Applied Cryptography" by Menezes, van Oorschot, and Vanstone. [0020] It is also known that n must be a composite number. Therefore, when n is a prime number, the inverse conversion can be easily performed, and security cannot be ensured at all. Verification of whether n is a composite number is Miller-Rabin probable prime verification (probable prime) in anticipation that n is actually proved to be a composite number. This can be achieved by performing test). Further inspections to verify Law n are based on: That is, it is based on the fact that n is the product of two large prime numbers, which is difficult to factor and therefore unsuccessful when attempted to factor by a simple method. For example, you may try to calculate GCD (n, i) for all prime numbers from small odd prime numbers to some size as i, for example the first 50000 (50K) odd prime numbers. [0021] [0021] The two validations above show that at least one factor must be less than half the bit size of the law from the former, and that the latter must be greater than the maximum prime number verified by each factor. I understand. Furthermore, there are only a limited number of potential factors (p, q, r, ...) that depend on the magnitude of the maximum prime numbers verified above. [0022] A synergistic effect can be obtained by combining the above plurality of verifications. The purpose of the verification is to significantly reduce the freedom of action that the enemy can take. Even when an attack is nearly impossible, partial key authentication can make the attack even more difficult, preferably impossible, or at least uneconomical. [0023] Furthermore, since the values of p and q should not be too close, when examining method n, we assume that they are close values and try to factor n. Let the square root of n be the initial prediction of p and q. Decrease p while increasing q to determine if n can be factored to a given limit. Furthermore, since we know that prime numbers must not be repeated in a set of RSA methods, we calculate GCD (ni, nj) for a set of methods n1 and n2 with RSA, and all the calculation results are 1. Can be confirmed to be equal to. [0024] Although there are limits to the offline validation described above, these validations can be extended because the owner of the parameter knows certain information, such as the factorization of n. Therefore, the owner may be used as an online oracle. By identifying that the answer to this Oracle question is incorrect, anyone can assert that the public key is invalid. [0025] According to Vanstone et al.'S "Handbook of Applied Cryptography", the owner can calculate (square root mod n), but others cannot. The verifier determines the Jacobian symbol (Jacobi Symbol) of (arbitrary value mod n) to be 1 or -1, half to 1 and the other half to -1. In the case of 1, it is divided in half again depending on whether the number is a square number or not. The verifier squares (a number mod n). The Jacobian sign for square numbers is always 1. [0026] The verifier chooses one of the known square number u and any element r with a Jacobian sign of 1. Then ask the owner, "Is this a square number?" For these two types of elements. The owner answers yes or no. If u is selected, the key law (modulus) is invalid unless the owner answers yes. If r is selected, the key law is invalid unless the owner answers yes and no by about half each. [0027] By repeating this many times, reliability is improved. If the verifier asks the owner about all square numbers, the owner must always answer yes. If the verifier asks the owner about any element that has a Jacobian sign of 1, the owner must answer yes to half and no to half. The fake key owner only knows that at least half of the answers are yes. However, the owner of the private key knows the factorization of n and knows the square numbers, so all he has to do is lie about the pseudo-square numbers that they are square numbers and deceive the verifier. Good. The verifier simply asks, "Is this a square number?" Using a known pseudo-square number. It is usually impossible to determine that a number is a pseudo-square number of the law without knowing the factorization of the law. However, the owner must answer the above question that some of the numbers where Jacobian is 1 are pseudo-square numbers. The verifier has a known pseudo-square number and (square number mod) Any known pseudo-square number can be generated by multiplying with n). The verifier knows that the resulting value is a pseudo-square number. Ask the owner about this third type of number t (known pseudo-square number), and in this case, even if the owner lied that some pseudo-square numbers are square numbers, the lie Known to verifiers. [0028] To verify both e and n, GCD (e, p-1) = 1 and GCD (e, q-1) = 1. If e is an odd number, p is not a number in the form of xe + 1 for the integers x and p, and q is not a number in the form of ye + 1 for the integer y. I know it won't be. If both p and q are invalid, n is xye²It must not be represented in the form + xe + ye + 1 and n 1 mod e must hold. [0029] Another method for verifying both e and n is described below. It is known that GCD (e, phi (n)) must be 1. Since we know that phi (n) = (p-1) (q-1), the verifier can factor n because there are two equations and two unknowns. [0030] It is assumed that other requirements for the key pair are met. The reason why GCD (e, phi (n)) = 1 must be satisfied is that the operation using e is surely a 1: 1 correspondence (inverse conversion possible) function. Otherwise, the number of operations using e will be 1: 1. When there are many operations using e and there is a one-to-one correspondence, d (inverse of e) does not exist, or at least it cannot be derived normally. The owner must provide proof that d actually exists. However, the above questions should not be asked under the control of the owner of the private key. That is, a self-signed certificate request ) Is not sufficient evidence. [0031] The challenger can also send some dummy messages to the owner who is requested to approve them for signature. The owner of the private key identifies them as dummy messages, signs them, and replies to the challenger. This is an online probabilistic oracle test in which d exists. [0032] Therefore, anyone can perform offline verification at any time. Anyone can perform online validation if the owner is online. Owners can perform offline and online verifications to verify that their private key is valid. The CA performs online verification to tell others what validity and to what extent the public key certificate has been validated. [0033] The system parameter in ECDSA is the field size q = p or 2^mIs. F so that (a, b) is generated by the optional seed and (a, b) causes the degree of the curve to be hn._qDefines an elliptic curve represented by, a singularity P on this curve, n, which is a large prime order of P, and a cofactor h. The field size EC and point P defined in (a, b) are the main parameters. [0034] It is important to check not only the EC system parameters but also the EC public key. For example, suppose the elliptic curve public key Q is assumed and Q is on E. If you are using a curve of prime degree in key matching, you do not need to check the degree of Q. This is because it is certain that Q has an accurate degree if it is on a curve. It is important to check that Q is on the curve. This is because if Q is not on the curve, the fake key reveals the private key a when calculating aQ. It is possible to confirm that the public key is on the curve by substituting it into the curve formula or performing verification. [0035] From the above, key authentication suppresses exposure to attacks, helps detect unexpected errors, and provides services that are valuable to CAs. As will be appreciated by those skilled in the art, the techniques and methods described above can be implemented in a suitable processor performing the steps of the present invention. In addition, the various methods described above are conveniently executed using a general-purpose computer and selectively booted or reconfigured by software, but such methods will be understood by those skilled in the art. May be implemented in hardware, firmware, or more specialized equipment configured to perform each required step. [0036] [Effect of the invention] According to the present invention, improved validation can be performed in a communication system having a security function. Furthermore, according to the present invention, anyone can perform such validation at any time using only public information. [Simple explanation of drawings] FIG. 1 is a schematic diagram of a communication system.