Private and public key exchange method preventing man-in-the-middle attack without electronic certificate and digital signature

Abstract

An apparatus, process, and system, that enables secure information and communication across channels based on a perfect key-exchange method. The secure channel between two users enables each to use the public key of the other user—to derive a secret key specific to both users. Traditional (but yet widely used) key-exchange methods are not perfect-secure; the public key encryption makes these methods to be broken under many kinds of attacks. Unlike these methods, the apparatus, process, and system of the present invention is not based on the computational assumptions like: Integer Factorization and Discrete Logarithm Problem. The apparatus, process, and system of the present invention inhibits and/or prevents the man-in-the-middle attack, which is a problem that has not been solved to this day.

Claims

1. A method comprising: using one or more computer processors to randomly select a first set of two large numbers (a.sub.1,A, a.sub.2,A), for a first user A, at least one of the first set of two large numbers being a prime number; using one or more computer processors to randomly select a second set of two large numbers (a.sub.1,B, a.sub.2,B), for a second user B, at least one of the second set of two large numbers being a prime number; using one or more computer processors to determine a first user A public key, wherein the first user A public key is based on the first set of two large numbers, and a set of predefined public parameters including a modulus (p) and a base (a.sub.1, a.sub.2); using one or more computer processors to determine a second user B public key, wherein the second B user public key is based on the second set of two large numbers, and the set of predefined public parameters; using one or more computer processors to calculate a value k.sub.A for the first user A as follows: k.sub.A=[(n.sub.B.sup.a.sup.2,A).sup.−1 mod p×(a.sub.1.sup.s.sup.B).sup.a.sup.2,A mod p]mod p wherein n.sub.B, is calculated by one or more computer processors for the second user B as (a.sub.1.sup.a.sup.2,B, a.sub.2.sup.a.sup.2,B) mod p; and s.sub.B is calculated by one or more computer processors for the second user B as (a.sub.1,A, a.sub.2,B); using one or more computer processors to calculate a value k.sub.B; for the second user B as follows: k.sub.B=[(n.sub.A.sup.a.sup.2,B).sup.−1 mod p×(a.sub.1.sup.s.sup.A).sup.a.sup.2,B mod p]mod p wherein n.sub.A is calculated by one or more computer processors for the first user A as (a.sub.1.sup.a.sup.2,A, a.sub.2.sup.a.sup.2,A) mod p; and s.sub.A is calculated by one or more computer processors for the first user A as (a.sub.1,A+a.sub.2,A); using one or more computer processors to encrypt a first message using k.sub.A, to form a first encrypted message; sending the first encrypted message from a computer processor controlled by the first user A to a computer processor controlled by the second user B; using one or more computer processors to encrypt a second message using k.sub.B, to form a second encrypted message; sending the second encrypted message from a computer processor controlled by the second user B to a computer processor controlled by the first user A; using one or more computer processors controlled by the first user A to decrypt the second encrypted message using k.sub.A; using one or more computer processors controlled by the second user B to decrypt the first encrypted message using k.sub.B; and providing, based on comparison of data between one or more computer processors controlled by the first user A and one more computer processors controlled by the second user B, an indication in one or more computer memories controlled by the first user A and in one or more computer memories controlled by the second user B that neither the first user A nor the second user B is a hacker when k.sub.A is determined to equal k.sub.B.

2. The method of claim 1 wherein k.sub.A is a cryptographic key used to encrypt the first message and decrypt the second encrypted message in a first key cryptography method; and wherein k.sub.B is a cryptographic key used to encrypt the second message and decrypt the first encrypted message in a second key cryptography method.

3. The method of claim 2 wherein the first key cryptography method is a symmetric key cryptography method; and the second key cryptography method is a symmetric key cryptography method.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1A shows a simplified diagram of an apparatus for use by a first user A in accordance with one or more embodiments of the present invention including a computer interactive device, a computer display, a computer processor under first user A's control, a computer input/output port, and a computer memory;

(2) FIG. 1B shows a simplified diagram of an apparatus for use by a second user B in accordance with one or more embodiments of the present invention including a computer interactive device, a computer display, a computer processor under second user B's control, a computer input/output port, and a computer memory;

(3) FIG. 1C shows a simplified diagram of an apparatus or server computer in accordance with one or more embodiments of the present invention including a computer interactive device, a computer display, a server computer processor, a computer input/output port, and a computer memory;

(4) FIG. 2 shows a high level representation diagram of one or more methods to be executed by the computer processor of FIG. 1, including use of public parameters, a public key generation method, a secret sharing method, and a key distribution and verification method.

(5) FIG. 3 is a detailed diagram of the public key generation method referred to in FIG. 2;

(6) FIG. 4 is a detailed diagram of the secret sharing method referred to in FIG. 2;

(7) FIG. 5 is a top level diagram of the key distribution and verification method referred to in FIG. 2;

(8) FIG. 6A is a first part of a detailed diagram of the key distribution and verification method referred to in FIG. 2; and

(9) FIG. 6B is a second part of a detailed diagram of the key distribution and verification method referred to in FIG. 2.

DETAILED DESCRIPTION OF THE DRAWINGS

(10) FIG. 1A shows a simplified diagram of a first user A computer 1 for use in accordance with one or more embodiments of the present invention including a computer interactive device 2, a computer display 4, a computer processor 6 under a first user A's control, a computer input/output port 8, and a computer memory 10. The computer processor 6 may include one or more computer processors. The computer memory 10 may include one or more computer memories. The computer interactive device 2 may include one or more computer interactive devices. The computer interactive device 2 may be one or more computer mice, computer touch screens, computer keyboards, or any other known computer interactive devices. The computer display 4 may include one or more computer displays. The computer input/output port 8 may include one or more computer input/output ports.

(11) FIG. 1B shows a simplified diagram of a second user B computer 20 for use in accordance with one or more embodiments of the present invention including a computer interactive device 22, a computer display 24, a computer processor 26 under a second user B's control, a computer input/output port 28, and a computer memory 30. The computer processor 26 may include one or more computer processors. The computer memory 30 may include one or more computer memories. The computer interactive device 22 may include one or more computer interactive devices. The computer interactive device 22 may be one or more computer mice, computer touch screens, computer keyboards, or any other known computer interactive devices. The computer display 24 may include one or more computer displays. The computer input/output port 28 may include one or more computer input/output ports.

(12) FIG. 1C shows a simplified diagram of a server computer 40 for use in accordance with one or more embodiments of the present invention including a computer interactive device 42, a computer display 44, a server computer processor 46, a computer input/output port 48, and a computer memory 50. The server computer processor 46 may include one or more computer processors. The computer memory 50 may include one or more computer memories. The computer interactive device 42 may include one or more computer interactive devices. The computer interactive device 42 may be one or more computer mice, computer touch screens, computer keyboards, or any other known computer interactive devices. The computer display 44 may include one or more computer displays. The computer input/output port 48 may include one or more computer input/output ports.

(13) FIG. 2 shows a high level representation diagram 100 of one or more methods to be executed by one or more of the computer processors 6, 26, and 46 of FIGS. 1A, 1B, and 1C, respectively, in accordance with computer software stored in one or more of computer memories 10, 30, and 50 of FIGS. 1A, 1B, and/or 1C, respectively, including use of public parameters at step 102 (typically executed separately by both computer processors 6 and 26), a public key generation method 108 (typically executed separately by both computer processors 6 and 26), a secret sharing method 110 (typically executed separately by both computer processors 6 and 26), and a key distribution and verification method 112 (executed by first user A computer processor 6, second user B computer processor 26, and server computer processor 46). The public parameters may include a modulus 104 or modulus (p) and a base 106 or base (a.sub.1, a.sub.2).

(14) FIG. 3 is a detailed diagram of the public key generation method 108 referred to in FIG. 2. The public key generation method 108 is executed separately by both first user A computer processor 6 and second user B computer processor 26 in accordance with computer software stored in computer memories 10, and 30, respectively. The public key generation method refers to a first user A controlling computer processor 6, who may be using a computer interactive device 2, such as a personal computer, smart phone or tablet computer, a second user B controlling computer processor 26, who may be using a computer interactive device 2, such as a personal computer, smart phone or tablet computer, and any further number of users controlling any further number of computer processors through any further number of computer interactive devices. At step 200, the first user A computer processor 6 executes a random selection of two large numbers for the first user A, at least one of these being a prime number. The two large numbers are shown as (a.sub.1,A, a.sub.2,A) and are stored in computer memory 10.

(15) At step 202, the first user A computer processor 6 calculates S.sub.A as programmed by computer software stored in computer memory 10.

(16) A step 204 the first user A computer processor 6 determines as programmed by computer software stored in computer memory 10

(17) At step 206 a public key, which is (n.sub.A, s.sub.A) is determined by the first user A computer processor 6 and stored in computer memory 10, as programmed by the computer memory 10. In addition, (a.sub.1,A, a.sub.2,A) Is stored in computer memory 10 as a private key for the first user A.

(18) At step 208, the second user B computer processor 26 executes a random selection of two large numbers for the second user B, at least one of these being a prime number. The two large numbers are shown as (a.sub.1,B, a.sub.2,B) and are stored in computer memory 30.

(19) At step 210, the second user B computer processor 26 calculates S.sub.B as programmed by computer software stored in computer memory 30.

(20) A step 212 the second user B computer processor 26 determines n.sub.B as programmed by computer software stored in computer memory 30

(21) At step 214 a public key, which is (n.sub.B, s.sub.B), is determined by the second user B computer processor 26 and stored in computer memory 30, as programmed by the computer memory 30. In addition, (a.sub.1,B, a.sub.2,B) Is stored in computer memory 30 as a private key for the second user B.

(22) At step 216, public keys and private keys are determined in a similar and/or identical manner by one or more further computer processors, similar or identical to computer processors 6 and 26, for one or more further users.

(23) FIG. 4 is a detailed diagram of the secret sharing method 110 referred to in FIG. 2. At step 300 the computer processor 6 controlled by the first user A, determines a unique key k.sub.A and this may be stored in computer memory 10.

(24) B

(25) At step 302 the computer processor 26 controlled by the second user B, determines a unique key k.sub.B and this may be stored in computer memory 30.

(26) The unique keys k.sub.A and k.sub.B are to be used for the communications (encryption and decryption processes) between the first user A computer processor 6 and the second user B computer processor 26.

(27) The value of k.sub.A is used to encrypt a message programmed to be sent by the computer processor 6, via input/output port 8 to the input/output port 28 and received by the computer processor 26 controlled by the second user B and decrypt a message received at the first user A computer processor 6 from the computer processor 26 controlled by the second user B, via the input/output ports 8 and 28.

(28) The value of k.sub.B is used to encrypt a message sent by the second user B computer processor 26 to the first user A computer processor, via the input/output ports 6 and 8, and decrypt a message coming from the first user A computer processor 6 to the second user B computer processor 26, via the input/output ports 6 and 8.

(29) At step 304 if the two user computer processors 6 and 26 end up with the same value (k.sub.A=k.sub.B), the key exchange method is satisfied (i.e., the messages between the two users, first user A and second user B would be encrypted and decrypted correctly, allowing the two users A and B to correctly communicate with each other).

(30) The value of (k.sub.A=k.sub.B) should be a value between 2 and p −1.

(31) FIG. 5 is a top level diagram of the key distribution and verification method 112 referred to in FIG. 2. A module 400 refers to a private key, and a public key. The public key from the method a of FIG. 3 is accessed by all players or users, such as the first user A and the second user B, and a the appropriate private key from the method of FIG. 3 is accessed by its owner, i.e. one private key for the first user A and one private key for the second user B, and a private key for each of any number of further users. The top level diagram of FIG. 5 refers to the server computer 40, the first user A computer 1, and the second user B computer 20. The server computer 40 has communications links with and from both the first user computer A 1 and the second user computer B 20. The computers 1 and 20 have communications links with one another. A hacker 402, may attempt to intercept communications between first user A computer 1 and second user B computer 20, and/or may attempt to imitate one of the computers 1 and 20 to improperly receive data and/or communications meant for computer 1 or computer 20.

(32) The server computer processor 46 of server computer 40 for a communication is accessed by each user computer processor, or processors 6 and 26, to decrypt each user's private key and send it to the other user. The first user A computer processor 6 verifies the keys sent by server computer processor 46 and the second User B computer processor 26. The second user B computer processor 26 verifies the keys sent by the server computer processor 46 and the first User A computer processor 6. In at least one embodiment a hacker will never be able guess, and/or it will be very difficult to guess, the keys communicated between computers 1, 20, and 40 and between computer processors 6, 26, and 46.

(33) One or more embodiments of the present invention introduce a new scheme that allows any user, such as a user of a personal computer, tablet computer, or smart phone accessing the server computer processor 46 through input/output port 48 and through the internet and/or some other network, such as a first user A or a second user B using first user A computer processor 6 or second user B computer processor 26, respectively, to share a secret or private key such as (a.sub.1,A, a.sub.2,A) for the first user A and (a.sub.1,B, a.sub.2,B) for the second user B with any other user on a network, without giving any other information about that secret or private key to the other user. A perfect key exchange scheme is defined as follows.

(34) Definition (perfect key exchange scheme): A key exchange scheme is said to be a perfect if two parties share the secret or private key in an unsecure channel and they give no information about that secret key for others.

(35) Note that if the scheme is perfect then it is unconditionally secure (information theoretically secure). RSA (initials stand for Rivest, Shamir, and Adleman) and similar/derived algorithms are under attack by the fact that the big Integer is known, and it is subject to factorization. The key exchange method with public Modules' Arithmetic Number N in one or more embodiments of the present invention is different from the other methods that use Deffie-Hellman and RSA (like the Advanced Encrypten Standard AES, Certificate Authorities, and Digital Signatures). The current process of one or more embodiments of the present invention is secure under any computational assumption. The only way that an attacker or hacker 402 shown in FIG. 5 can break this method is by using a brute-force attack. The brute-force attack needs thousands of years, to hack a first user A computer processor 6 (or second user B computer processor 26), using one in many private keys in a network, using hundreds of personal computers, for hundreds of users.

(36) The information theoretically secure key exchange process of one or more embodiments of the present invention is comprised of the following two methods. Suppose that alphas (a.sub.1, a.sub.2) of the base 106 shown in FIG. 2 are two prime numbers, and p is a large prime number. The primes (a.sub.1, a.sub.2) and p are public parameters of an overall method in accordance with an embodiment of the present invention.

(37) One or more embodiments of the present invention generate a strong secure shared key (k.sub.A for the first user A, and k.sub.B for the second user B) at steps 300 and 302 in FIG. 4. This key enables the use of any kind of symmetric encryption (the key used in encryption and decryption is the same). If the two user computer processors 6 and 26 end up with the same value (k.sub.A=k.sub.B), the key exchange method is satisfied (i.e., the messages between the two users would be encrypted and decrypted correctly, allowing the two users to correctly communicate with each other).

(38) The man-in-the-middle attack is the most known problem that current (and past) security algorithms face. This attack exists because of the existence of the distributed public key. Security algorithms use the third trusted parties to distribute and save the public and private keys. They further use Digital Signatures to verify that keys belong to the intended users. This issue makes the information transfer between users to be unsecure because third parties know the public and private keys too. To solve the issue, certificate authorities exist to distribute keys, and Digital Signatures exist to verify users, to protect the schemes from the man-in-the-middle attack. However, certificate authorities and Digital Signatures still get attacked, because they are generated based on Diffie-Hellman key exchange and RSA algorithms, which are not information theoretically secure as explained previously.

(39) To prevent third party vendors from reading the information shared between users, and to prevent the man-in-the-middle attack (for the key distribution and verification), one or more embodiments of the present invention improves the process to work as shown in FIG. 5. An overall method of one or more embodiments of the present invention hides the secrete keys or private keys shown at step 200 and 208 of FIG. 3, while communicating with the server computer 46 (i.e., it gives no information about the party's secret or private keys from step 200 or 208 of FIG. 3. The proposed scheme is an end-to-end encryption, in the following ways:

(40) It is not based on any computational assumption.

(41) The authentication and verification processes (depicted in FIGS. 5 and 6A-6B) are imbedded in the method as programmed in computer memory 50 of the server computer 40 of FIG. 1C, (e.g., transferring the secure public keys satisfies the method or process to be information theoretically secure (perfect secure).

(42) Preventing the man in the middle attack by introducing the workflow depicted in FIG. 5; and by making it impossible to find the keys shown in steps 200 and 208 (using a brute-force attack) when the shared keys shown in steps 200 and 208 of FIG. 3 length is up to 2048 binary bits.

(43) Although at least one embodiment of the present invention has been explained for a first user A and a second user B, the invention can be applied to one or more embodiments for any number of users.

(44) FIG. 6A is a first part of a detailed diagram of the key distribution and verification method 112 referred to in FIG. 2; and FIG. 6B is a second part of a detailed diagram of the key distribution and verification method 112 referred to in FIG. 2.

(45) At step 500 of FIG. 6A, the first user A computer processor 6 determines:

(46) x.sub.A=U.sub.AMAC.sub.APk.sub.A; and

(47) y.sub.A=E(x.sub.A,Pk.sub.S)

(48) wherein x.sub.A is a first unique key for the first user A;

(49) wherein U.sub.A is a unique identification number for the first user A;

(50) wherein MAC.sub.A is a unique identification number for the computer processor 6 controlled by the first user A;

(51) wherein Pk.sub.A is a public key of the first user A;

(52) wherein y.sub.A is an encrypted first unique key, i.e. and encryption of x.sub.A;

(53) wherein Pk.sub.S is a public key of the server computer processor 46;

(54) and wherein E stands for encryption operator.

(55) At step 502, the first user A computer processor 6 sends y.sub.A to the second user B computer processor 26 and the server computer processor 46.

(56) At step 504, the second user B computer processor 26 receives y.sub.A and determines x.sub.B=U.sub.BMAC.sub.BPk.sub.By.sub.A; and y.sub.B=E(x.sub.B,Pk.sub.S)

(57) wherein x.sub.B is a second unique key for the second user B;

(58) wherein U.sub.B is a unique identification number for the second user B;

(59) wherein MAC.sub.B is a unique identification number for the computer processor 26 controlled by the second user B;

(60) wherein Pk.sub.B is a public key of the second user B; and

(61) wherein y.sub.B is an encrypted second unique key, i.e. and encryption of x.sub.B.

(62) At step 506, the second user B computer processor 26 sends y.sub.B to the first user A computer processor 6 and to the server computer processor 46.

(63) At step 508 the server computer processor 46 receives y.sub.B and then determines a decryption, D(y.sub.B, Pr.sub.S)=x.sub.B wherein Pr.sub.S Is a private key of the server computer processor 46, to ensure that the value y.sub.B belongs to the second user B, then the server computer processor 46 calculates D(y.sub.A, Pr.sub.S)=x.sub.A

(64) At step 510 the server computer processor 46 sends x.sub.A to the second user B computer processor 26.

(65) At step 512, the second user B computer processor 26 receives x.sub.A from the server computer processor 46 then determines an encryption

(66) $E\left(x_A,{\mathrm{Pk}}_S\right)\stackrel{\mathrm{yields}}{.fwdarw.}{y}_A$
wherein Pk.sub.S is the public key of the server computer processor 46.

(67) The second user B computer processor 26 compares the encryption of step 512 with the received value from the first user computer processor 6 and if these are the same, then an indication is stored in computer memory 30 that hacking has not occurred, and the second user B computer processor 26 will not prevent communications between processors 6 and 26.

(68) The method continues to step 514, as shown by node A on FIG. 6A, which is also shown on FIG. 6B.

(69) At step 514, the first user A computer processor 6 receives y.sub.B from the second user B computer processor 26 and then determines R.sub.1=y.sub.Ay.sub.B; and R.sub.2=E(R.sub.1, Pk.sub.S).

(70) At step 516, the first user A computer processor 6 sends R.sub.2 to the server computer processor 46.

(71) At step 518, the server computer processor 46 receives R.sub.2 from the first user A computer processor 6 and then calculates

(72) $D\left(R_2,{\mathrm{Pr}}_S\right)\stackrel{\mathrm{yields}}{.fwdarw.}{R}_1$
to ensure that the first user A computer processor 6 received the correct y.sub.B.

(73) At step 520, the server computer processor 46 then determines D(y.sub.B, Pr.sub.S)=x.sub.B; and sends x.sub.B to the first user A computer processor 6.

(74) At step 522 the first user A computer processor 6 receives x.sub.B From the server computer processor 46 and then first user A computer processor 6 determines

(75) $E\left(x_B,{\mathrm{Pk}}_S\right)\stackrel{\mathrm{yields}}{.fwdarw.}{y}_B;$
and compares the received value from the second user B computer processor 26, and if they are the same, and indication is stored in computer memory 10 that hacking has not occurred and the first user A computer processor 6 will not prevent communications between processors 6 and 26.

(76) If both computer processors 6 and 26 are not preventing communications between the processors 6 and 26, i.e. if both processors 6 and 26 have set indications that hacking has not occurred, then communications are allowed to occur between processor 6 and 26.

(77) Although the invention has been described by reference to particular illustrative embodiments thereof, many changes and modifications of the invention may become apparent to those skilled in the art without departing from the spirit and scope of the invention. It is therefore intended to include within this patent all such changes and modifications as may reasonably and properly be included within the scope of the present invention's contribution to the art.