CLIAMS:1. A method comprising:
ascertaining a friendly prime (p) based on a first variable (c) and Nth power of two, wherein N is an integer, and wherein base two logarithm of the first variable (c) has a minimum value greater than zero and a maximum value equal to half the value of the N given by the equation log2c = (1/2)N, and wherein the friendly prime (p) is congruent to 3 (mod 4), and wherein bit length of the friendly prime (p) is of at least 512 bits;
generating a super singular elliptic curve (E/GF(p)) over a finite field(GF(p)) based on a set of distinctive parameters, wherein the finite field (GF(p)) is determined based on the friendly prime (p);
determining a first torsion group (S[q]) over the super singular elliptic curve (E/GF(p)) based on the friendly prime (p), wherein the first torsion group (S[q]) is a subgroup of points onthe super singular elliptic curve (E/GF(p)), and wherein a torsion group prime order (q) of the first torsion group (S[q]) is a prime number of bit length of at least 160 bits;
constructing a second torsion group (T[q]) over a super singular elliptic curve (E/GF(p2)) based on the friendly prime (p), wherein the second torsion group (T[q]) is an isomorphic image of the first torsion group (S[q]), and wherein a torsion group prime order the second torsion group (T[q]) is equal to the torsion group prime order (q) of the first torsion group (S[q]); and
providing at least one of the friendly prime (p), the super singular elliptic curve (E/GF(p)), the first torsion group (S[q]), and the second torsion group (T[q]) to a user device for encrypting data using identity based elliptic curve cryptography.
2. The method as claimed in claim 1, wherein a bit length of the first variable (c) is a multiple of 8 bits.
3. The method as claimed in claim 1, wherein the number of points on the super singular elliptic curve (E/GF(p)) is equal to p+1, and wherein the points on super singular elliptic curve (E/GF(p)) includes a point at infinity.
4. The method as claimed in claim 1, wherein the torsion group prime order (q) of the first torsion group (S[q])perfectly divides a sum of the value of the friendly prime (p) and one, given by the expression q | p+1.
5. The method as claimed in claim 1, wherein each of the first torsion group (S[q]) and the second torsion group (T[q]) is an additive subgroup of points on the super singular elliptic curve (E/GF(p)) and the super singular elliptic curve (E/GF(p2)), respectively.
6. The method as claimed in claim 1, wherein the constructing further comprises obtaining the second torsion group (T[q]) using a distortion map given by the relation F: [e, f] e S[q] ? Point [p-e, sqrt(-1)*f] e T[q], wherein F is the distortion map, and wherein e and f are affine co-ordinates of an elliptic curve point belonging to the first torsion group S[q], and wherein [p-e, sqrt(-1)*f] are affine co-ordinates of an elliptic curve point, in the second torsion group T[q], isomorphic to the elliptic curve point in the first torsion group.
7. The method as claimed in claim 1 further comprising:
generating a master secrete key (s), wherein the value of the master secret key (s) is in the range of one to p-1;
selecting a first elliptic curve point (P) belonging to the first torsion group (S[q]); and
computing a second elliptic curve point(Q) belonging to the first torsion group(S[q])wherein the second elliptic curve point is obtainedas a product of the secret key (s) and the first elliptic curve point (P)
8. The method as claimed in any one of the preceding claims, wherein the method further comprises:
receiving a request for public cryptography parameters from a user device, wherein the public cryptography parameters include the friendly prime (p), the super singular elliptic curve (E/GF(p)), the first torsion group (S[q]), the second torsion group (T[q]), the first elliptic curve point (P), and the second elliptic curvepoint (Q); and
providing the public cryptography parameters to the user device for encrypting data using identity based elliptic curve cryptography.
9. The method as claimed in any one of the preceding claims, wherein the method further comprises generating a public key of the user based on a public identity of a user.
10. The method as claimed in any one of the preceding claims, wherein the method further comprising:
receiving a request for a private key from the user device;
computing a private key of the user based on the public key of the user and the master secret key; and
providing the private key based upon the request to the user device.
11. The method as claimed in any one of the preceding claims, wherein the encryption and decryption operations are performed usingTate pairing, and wherein the Tate pairing is computed using miller's algorithm.
12. The method as claimed in any one of the preceding claims, wherein all elliptic curve arithmetic computations are performed in Jacobian co-ordinate system.
13. A private key generator (104) comprising
a processor (202); and
a memory (206) coupled to the processor (202), the memory (206) comprising:
a parameter generation module (108) configured to:
ascertain a friendly prime (p) based on a first variable (c) and Nth power of two, wherein N is an integer, and wherein base two logarithm of the first variable (c) has a minimum value greater than zero and a maximum value equal to half the value of the N given by the equation log2c = (1/2)N, and wherein the friendly prime (p) is congruent to 3 (mod 4), and wherein bit length of the friendly prime (p) is of at least 512 bits;
generate a super singular elliptic curve (E/GF(p)) over a finite field(GF(p)) based on a set of distinctive parameters, wherein the finite field (GF(p)) is determined based on the friendly prime (p);
determine a first torsion group (S[q]) over the super singular elliptic curve (E/GF(p)) based on the friendly prime (p), wherein the first torsion group (S[q]) is a subgroup of points on the super singular elliptic curve (E/GF(p)), and wherein a torsion group prime order (q) of the first torsion group (S[q]) is a prime number of bit length of at least 160 bits; and
construct a second torsion group (T[q]) over a super singular elliptic curve (E/GF(p2)) based on the friendly prime (p), wherein the second torsion group (T[q]) is an isomorphic image of the first torsion group (S[q]), and wherein a torsion group prime order of the second torsion group (T[q]) is equal to the torsion group prime order (q) of the first torsion group (S[q]); and
a key generation module (214) configured to:
compute a private key of a user over the super singular elliptic curve (E/GF(p)), based on a public identity of the user of a user device (102) and a master secret key, for decrypting data using identity based elliptic curve cryptography.
14. The private key generator (104) as claimed in wherein the parameter generation module (108) is further configured to:
generate the master secret key (s), wherein the value of the secret key (s) is in the range of one to p-1;
select a first elliptic curve point (P) belonging to the first torsion group (S[q]); and
compute a second elliptic curve point(Q) belonging to the first torsion group (S[q]),wherein the second elliptic curve point is obtained as a product of the master secret key (s) and the first elliptic curve point (P).
15. The private key generator (104) as claimed in wherein the parameter generation module (108) is further configured to compute complex computations in T[q], wherein the complex computations involve complex multiplication in GF(p2), in two integer multiplications in GF(p).
16. The private key generator (104) as claimed in any wherein the private key generator (104) further comprises a user interaction module (212) configured to:
receive a request for public cryptography parameters from a user device and wherein the public cryptography parameters include the friendly prime (p), the super singular elliptic curve (E/GF(p)), the first torsion group (S[q]), the second torsion group (T[q]), the first elliptic curve point (P), and the second elliptic curve point (Q); and
providethe public cryptography parameters to the user for encrypting data using the identity based elliptic curve cryptography.
17. The private key generator (104) as claimed in wherein the user interaction module (212) is further configured to:
receive the request for the private key from the user device (102); and
provide the private key based upon the request to the user device (102).
18. The private key generator (104) as claimed in wherein the key generation module (214) is further configured to generate a public key of the user of the user device (102)
19. A computer-readable medium having embodied thereon a computer program for executing a method comprising:
ascertaining a friendly prime (p) based on a first variable (c) and Nth power of two, wherein N is an integer, and wherein base two logarithm of the first variable (c) has a minimum value greater than zero and a maximum value equal to half the value of the N given by the equation log2c = (1/2)N, and wherein the friendly prime (p) is congruent to 3 (mod 4), and wherein bit length of the friendly prime (p) is of at least 512 bits;
generating a super singular elliptic curve (E/GF(p)) over a finite field(GF(p)) based on a set of distinctive parameters, wherein the finite field (GF(p)) is determined based on the friendly prime (p);
determining a first torsion group (S[q]) over the super singular elliptic curve (E/GF(p)) based on the friendly prime (p), wherein the first torsion group (S[q]) is a subgroup of points onthe super singular elliptic curve (E/GF(p)), and wherein a torsion group prime order (q) of the first torsion group (S[q]) is a prime number of bit length of at least 160 bits;
constructing a second torsion group (T[q]) over a super singular elliptic curve (E/GF(p2)) based on the friendly prime (p), wherein the second torsion group (T[q]) is an isomorphic image of the first torsion group (S[q]), and wherein a torsion group prime order of the second torsion group (T[q]) is equal to the torsion group prime order (q) of the first torsion group (S[q]); and
providing at least one of the friendly prime (p), the super singular elliptic curve (E/GF(p)), the first torsion group (S[q]), and the second torsion group (T[q]) to a userdevicefor encrypting data using identity based elliptic curve cryptography. ,TagSPECI:[0001] The present subject matter relates to cryptography and, particularly, to determining parameters for identity based elliptic curve cryptography.
BACKGROUND
[0002] Cryptography is a well known method used for secure transmission of messages between two users. Cryptography involves encryption of data in one form, such as a plaintext, to another form, such as a ciphertext, at a sender's end and decryption of the ciphertext to the plaintext at a receiver's end. Cryptographic systems are typically classified into two types, symmetric cryptography and asymmetric cryptography based on a key used for encryption and decryption of messages. Symmetric or private key cryptography involves the same key for encryption and decryption of data, whereas asymmetric or public key cryptography involves separate keys for each cycle of encryption and decryption.
[0003] Public key cryptography is used for secure communication between two users over a network. The public key cryptography typically involves two keys known as a public key and a private key for encrypting and decrypting data, respectively. The private key and the public key are typically, mathematically linked and obtained using complex mathematical processes to ensure safety of the encrypted data. The public key is used for encryption of the plaintext, whereas the private key is used for decryption of the cipher text. Examples of algorithms used for public key cryptography include Rivert, Shamir, Aldeman (RSA), Diffie-Hellman key exchange (DH), and Elliptic curve cryptography (ECC). Typically, algorithms associated with cryptography are computationally intensive as they involve complex mathematical operations, such as arithmetic operations over large primes or integers, and modular reduction over these large primes or integers. Further, these mathematical operations involve many inversion operations over large primes. To overcome the aforementioned hindrances involved with cryptography, typically, ECC is deployed in many cryptography systems. Further, the cryptographic system makes use of special primes, such as, Crandall primes, Solinas primes, and modular reduction techniques, such as Montgomery modular reductions. Additionally, ECC offers high level of security and smaller sizes of the public keys and the private keys scalable for the cryptography.
[0004] Generation of the public keys and the private keys typically involves several mathematical calculations which are complex in nature and are thus a time consuming process. Further, encrypting the plaintext using the public keys requires additional steps of complex algorithms and calculations. Thus, applications using such algorithms are usually implemented on systems capable of fast computation speeds and having sufficient battery backup suitable for carrying out the complex algorithms associated with cryptographic process. Due to the complex algorithms and high system requirements, devices, such as mobile phones, smart phones, wireless sensors, wireless devices, machine to machine (M2M) devices, and handheld devices used for lightweight applications, may not be able to implement the ECC for encryption as computation of such algorithms may not be feasible on such devices due to less processing capabilities, less memory, and limited battery backup.
SUMMARY
[0005] This summary is provided to introduce concepts related to identity based elliptic curve cryptography. This summary is not intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[0006] In one embodiment, method(s) and system(s) for identity based elliptic curve cryptography are described. The method includes ascertaining a friendly prime based on a first variable (c) and Nth power of two, where N is an integer, and where the base two logarithm of the first variable has a minimum value greater than zero and a maximum value equal to half the value of the N given by the equation log2c = (1/2)N, and where the friendly prime p is congruent to 3 (mod 4), and where the friendly prime is of at least 512 bits length. Further, a super singular elliptic curve is generated over a finite field based on the friendly prime. The method further includes determining a first torsion group on the super singular elliptic curve based on the friendly prime, where the first torsion group is a subgroup of points on the super singular elliptic curve, and where a torsion group prime order of the first torsion group is of 160 bits length. Further, constructing a second torsion group over the super singular elliptic curve based on the friendly prime, where the second torsion group is an isomorphic image of the first torsion group, and where a torsion group prime order of the second torsion group is equal to the torsion group prime order of the first torsion group. Further, the friendly prime, the super singular elliptic curve, the first torsion group, and the second torsion group are provided to a user device for encrypting data using identity based elliptic curve cryptography.
BRIEF DESCRIPTION OF THE FIGURES
[0007] The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the figures to reference like features and components. Some embodiments of systems and/or methods in accordance with embodiments of the present subject matter are now described, by way of example only, and with reference to the accompanying figures, in which:
[0008] Figure 1 illustrates a network environment implementing identity based elliptic curve cryptography, according to an embodiment of the present subject matter;
[0009] Figure 2 illustrates a private key generator for generating public cryptography parameters for identity based elliptic curve cryptography, in accordance with an embodiment of the present subject matter; and
[0010] Figure 3 illustrates a method for generating public cryptography parameters for identity based elliptic curve cryptography, in accordance with an embodiment of the present subject matter.
DETAILED DESCRIPTION
[0011] The present subject matter describes method(s) and system(s) for generating public cryptography parameters for efficient identity based elliptic curve cryptography. Communication over a non-secure communication network, such as internet or any wireless communication network is prone to various threats and attacks, such as data theft, and alteration by malicious third parties. Such attacks may result not only in loss of private data but also monetary loss and other losses of higher magnitude, as in the case of documents related to national security or of national importance being stolen, copied, leaked, or altered.
[0012] In order to achieve secure transmission of data over the non-secure communication network, cryptography may be implemented by a sender for encrypting data before transmission to a receiver over the non-secure communication network. Cryptography is a methodology of encrypting and decrypting data, for example, before transmitting data over a communication network in such a manner that enables secure transmission of the data even in the presence of malicious third parties. Thus, even in case the malicious third parties gain access to the data, the malicious third parties may not be able to use the encrypted data.
[0013] Public key cryptography is a widely used method of cryptography for secure transmission of data over the communication networks. Public key cryptography, as will be understood, uses certain well-established algorithms for encryption of data. These algorithms are typically mathematical in nature and may thus encompass complex calculations and generally require apparatus having high processing capabilities in order to ensure quick computations of the algorithms.
[0014] One of the conventional methods of secure data transmission involves a method of identity based elliptic curve cryptography. Identity based elliptic curve cryptography typically involves generation of encryption keys, based on a public identity associated with a user or a device corresponding to the user, over an elliptic curve. Identity based elliptic curve cryptography typically requires encrypting data over an elliptic curve defined using one or more public cryptography parameters. Typically, a user intending to encrypt the data may request a centralized server, for example, a private key generator, for providing the public cryptography parameters for encryption. The centralized server is configured to generate the public cryptography parameters based on which the elliptic curve is generated. The centralized server then provides the user with the public cryptography parameters. In one case, the centralized server may also provide the user with a private key corresponding to the user which is used for decryption. The user then generates a public key of an intended receiver based on an identity of the intended receiver, such as an e-mail address, a phone number, date of birth, IP address, Mac-id or any other identity associated with a device corresponding to the intended receiver, and the like.
[0015] The user subsequently encrypts the data using the public key of the intended receiver and the public cryptography parameters. Encryption of data involves computationally exhaustive mathematical operations, for example, modular multiplicative inversion operations which are generally computed using complex extended Euclidean GCD algorithm and involve several multiplication and division operations, thereby increasing the computation time of encryption algorithms. Moreover, algorithms associated with cryptography are generally computationally intensive as they involve complex mathematical operations, such as arithmetic operations over large primes or integers, and modular reduction over these large primes or integers. Therefore, such a method of identity based cryptography may not be suitable for implementation on devices, such as mobile phone, smart phone, and handheld devices having low processing power, less memory, and less battery backup.
[0016] In another conventional method, elliptic curve cryptosystem is implemented for encrypting a confidential data which is to be sent to a receiver over a non-secure communication network. The elliptic curve cryptosystem involves operations involving points on an elliptic curve over a finite field, such as a Galois field GF(p), where p is a special class of prime number. Based on the classes of prime numbers, modular reductions can be achieved using shift and add operations. Typically, encryption algorithm involves complex computations over the elliptic curve for encrypting the confidential data. The encryption algorithm involves modular reductions and modular multiplicative inversion operations over a large prime, such as p, involving several multiplication operations computed using conventionally known extended Euclidean GCD algorithm.Typically, Montgomery modular reduction scheme is used in the above conventional methods for computing modular reductions over large primes. The Montgomery modular reduction over special primes can be realized using simple additions and shift operations. However, pertaining to the complex computations involved with the modular multiplicative inversion operations, the encryption algorithms have large computational time and such an encryption scheme is not suitable for devices, such as a mobile phone, a smart phone, and handheld devices having less memory, low processing power, and limited battery backup.
[0017] In such conventional systems, encryption of data may involve complex algorithms which are computationally exhaustive. Similarly, decryption of data at the recipient's end uses similar complex algorithm, such as extended Euclidean algorithm. As mentioned, such algorithms aregenerally computationally intensive and time consuming as they are attributed by complex computations of high order and may only be supported by devices having large processing capabilities, sufficient memory, and sufficient battery backup. Due to the complexity involved in such algorithms and the corresponding high processing requirements, implementation of identity based elliptic curve cryptography may not be suitable in devices, such as mobile phones, smart phones, and handheld devices used for lightweight applications, having less processing power, less memory, and limited battery backup.
[0018] The present subject matter describes method(s) and system(s) for identity based elliptic curve cryptography. In one implementation, the system described herein is configured to generate the public cryptography parameters such that the complex computations associated with identity based elliptic curve cryptography are eliminated. Further, less complex mathematical operations are performed for carrying out identity based elliptic curve cryptography, thereby using less resources and at faster speeds. In one implementation, all computations involving super singular elliptic curves for cryptographic purposes may be performed in Jacobian co-ordinate system. In one implementation the computations in Jacobian co-ordinate system are performed with z co-ordinate equal to one, which further helps in reduction of computation time of encryption and decryption algorithms by reducing number of complex modular multiplicativeinversion operations. The system thus facilitates in providing a lightweight application of identity based elliptic curve cryptography that may be implemented on devices, such as mobile phones and hand held devices having less computational power, less memory, and limited battery backup. Although the present subject matter is described with reference to identity based elliptic curve cryptography, the present subject matter may also be applicable to other cryptographic schemes, albeit with few modifications as will be understood by a person skilled in the art.
[0019] In one implementation, a user intending to encrypt a confidential data may send a request for public cryptography parameters to a private key generator through a corresponding user device. Public cryptography parameters are used for encrypting the confidential data to obtain an encrypted confidential data which is to be sent to an intended receiver over a communication network, such as internet, any wireless network, and the like. Public cryptography parameters may include a friendly prime, a super singular elliptic curve, a torsion group prime order, a first torsion group of points, a second torsion group of points, a first elliptic curve point, and a second elliptic curve point.The friendly prime is of a special form and is used for determining other public cryptography parameters used for encrypting the data. The friendly prime also determines the computational complexity of the cryptographic scheme and security level of the encryption system. The special form of friendly prime enables the use of faster modular reduction which is realized using simple addition and shift operations resulting in faster computation of the encryption keys and also reduces the computation time of encryption and decryption algorithms.
[0020] In one implementation, the friendly prime is based on a first variable and Nth power of two, where N is an integer, and where a maximum value of base two logarithm of the first variable is equal to half of N. Further, the base two logarithm of the first variable is greater than zero. The type of super singular elliptic curve used for cryptography is based on the friendly prime of a predetermined form. In one implementation, the friendly prime may be of the predetermined form:
p = 3 (mod 4).................................................(1)
where, p is the friendly prime. The friendly prime also satisfy the condition:
p = 2N ± c..................................................(2)
where, N is the length of the friendly prime p in bits and c, also referred to as a first variable, is a variable integer. The maximum value of base two logarithm of the first variable is based on a value equal to half the value of the N given by the equation :
log2c = (1/2)N..............................................(3)
In one implementation, the length of the friendly prime p may be 512 bits. In another implementation the length of the friendly prime p may be 1024 bits. Further, the binary length of c should be a multiple of bit width of standard processors, such as processors supporting bit width 8 bits, 16 bits, 32 bits, and 64 bits.
[0021] Thereafter, a finite field, such as a Galois field, is defined based on the friendly prime. The finite field comprises of a predetermined number of elements, where value of the elements is ranging from zero to a value equal to one less than the value of the friendly prime. For example, for the friendly prime p, the finite field may comprise of elements between 0 to p-1. In elliptic curve arithmetic, the friendly primes enable the use of fast modular reductions which speeds up mathematical operations such as multiplications and divisions involved in several cryptographic algorithms. The super singular elliptic curve is thus defined over the finite field in order to reduce the computations. The points on the super singular elliptic curve obtained is used in encryption and decryption of data such as the confidential data, and for generating encryption keys such as a private key of an intended receiver for decrypting any data encrypted using the public identity of the intended receiver. Public identity of the intended receiver may be any information associated with the intended receiver, such as an e-mail address, a phone number, date of birth, and the like. The super singular elliptic curve is determined using a set of distinctive parameters in elliptic curve equation.
[0022] Further, a first torsion group of points, hereinafter referred to as first torsion group, comprising of points lying on the super singular elliptic curve, is determined based on the friendly prime. In one implementation, the first torsion group comprises of all points obtained by repetitive addition of a point lying on the super singular elliptic curve to itself to obtain a point at infinity. The number of points in the first torsion group is termed as the torsion group prime order and is related to the friendly prime based on one or more predefined rules. Further, the first torsion group also includes a point at infinity, as would be understood by a person skilled in the art. In one implementation, the first torsion group may be an additive subgroup of points lying on the super singular elliptic curve.
[0023] Further, a second torsion group of points, hereinafter referred to as second torsion group, is constructed based on the first torsion group. In one implementation, the second torsion group is an isomorphic image of the first torsion group over the super singular elliptic curve under the distortion mapping given by the relation:
F: [e, f] e S[q] ? Point [p-e, sqrt(-1)*f] e T[q]..............(4)
wherein F is the distortion map e and f are the affine co-ordinates of an elliptic curve point belonging to S[q], and [p-e, sqrt(-1)*f] are the affine co-ordinates of an elliptic curve point in the T[q] which is isomorphic to [e,f] in S[q].As a result of the isomorphic mapping between the first and the second torsion groups, complex computation involving multiplication in complex field are reduced to two integer multiplications in GF(p).Here p is a friendly prime of the predetermined form. Both the points belong to the finite field based on the friendly prime. Further, the number of points in the second torsion group is equal to the number of points in the first torsion group, i.e., the first torsion group and the second torsion group have the same torsion grouporder. In one implementation, the second torsion group may be an additive subgroup of points lying over a super singular elliptic curve over a finite field over p2, where p is the friendly prime. The finite field over p2 is denoted as GF(p2).
[0024] Subsequently, a first elliptic curve point and a second elliptic curve points, hereinafter collectively referred to as elliptic curve points are selected from amongst the elements of the first torsion group based on one or more predetermined rules, for example, no degeneracy. In one implementation, the first elliptic curve point, for example P, belonging to the first torsion group, may be generated by selecting a random integer other than zero, say, x from within the range of the finite field.Generation of P involves several complex computations which are greatly reduced due to the form of the friendly prime. Subsequently, based on the elliptic curve point P, the second elliptic curve point, say Q, is obtained by selecting another random integer other than zero and the previously selected random integer, say s, from within the range of the finite field. In one implementation, the elliptic curve point Q may be obtained by product operation of s and P, represented as [s]P, where [s]P implies addition of point P to itself s times as shown below in the equation:
Q = [s]P=P+P+P+P....('s' times)...............................(5)
where, P and Q are the elliptic curve points and belong to the first torsion group and s is a master secret key of the private key generator. In one implementation, the elliptic curve points are disjoint and are in accordance with no degeneracy condition, i.e., the result of mathematical tate pairing operation, computed using Miller algorithm, is not equal to one. The elliptic curve points are used for encryption and decryption algorithms which involve complex mathematical operations.
[0025] Further, a public key and a private key of the user are generated. The public key of the user is generated based on a public identity (ID) of the user. The ID may be any public information of the user, such as an e-mail address, the date of birth, and the phone number of the user. Based on the public key, the private key of the user is computed using the equation given below:
uID = [s]qID = qID+qID+qID+ ('s' times)..................(6)
Here, uID is the private key, [s] is the master secret key, and qID is the public key of the user. The complexity of the computations and the operations for generation of the public key and the private key are significantly reduced as a result of the friendly prime and the super singular elliptic curve.
[0026] Subsequently, the public cryptography parameters and the private key of the user are provided to the user device for encrypting the confidential data using identity based elliptic curve cryptography. In one implementation, the user device generates a public key of the intended receiver based on the public identity of the intended receiver. Public identity of the intended receiver may be any known information about the intended receiver, such as e-mail address, phone number, date of birth, and the like. Based on the public cryptography parameters and the public key of the intended receiver, the user device encrypts the data. In one implementation, encryption of the data may be performed using a computationally intensive and complex mathematical structure called tate pairing. Tate pairing is a bilinear transformation of the form:
S[q] X T[q] ? GF (p2)............................(7)
where S[q] and T[q] represent the first torsion group and the second torsion group respectively, GF(p2) represents the Galois extension field over p2, where p is a friendly prime, as described previously.
[0027] As a result of the predetermined form of the friendly prime, the elliptic curve points selected from the torsion groups based on the friendly prime are disjoint and computationally intensive algorithms for obtaining disjoint elliptic curve points are averted. Typically, tate pairing operations in the encryption and decryption algorithms are performed using efficient miller's algorithm. Computation of miller's algorithm involves several operations, such as point addition, point multiplication, and complex multiplication modulo pon the elliptic curve points. The torsion groups S[q] and T[q], based on the friendly prime p, are of such a form that it helps in reducing these operations over the elliptic curve points by half. Similarly, tate pairing computations involved in decryption algorithm are also reduced by half. Thus, use of the public cryptography parameters based on the friendly prime reduces the complexity and computational time of the encryption and decryption algorithms.
[0028] The system(s) and method(s) of the present subject matter thus reduces the time required for implementing identity based cryptographic process and enables its use in devices running lightweight applications by using friendly primes having special form. The use of friendly prime, the super singular elliptic curve, and other public cryptography parameters along with computations performed in Jacobian co-ordinate system facilitates faster computation of cryptographic algorithms used for generating public cryptography parameters and encryption keys. Further, the use of friendly primes enables the use of fast modular reductions which further speeds up the algorithm involved in the cryptographic process. Thus, the use of friendly prime speeds up the process of cryptography and can be implemented over devices, such as mobile phones, smart phones, and handheld devices running lightweight applications, having less computational power, less memory, and limited battery power.
[0029] These and other advantages of the present subject matter would be described in greater detail in conjunction with the following figures. While aspects of described system(s) and method(s) for identity based elliptic curve cryptography can be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following exemplary system(s).
[0030] Figure. 1 illustrates a network environment 100 implementing identity based elliptic curve cryptography, according to an embodiment of the present subject matter. The network environment 100 includes a plurality of user devices 102-1, 102-2...102-N, hereinafter collectively referred to as user devices 102 and individually referred to as user device 102, in communication with a private key generator 104 through a communication network 106. Communication links between the user devices 102 and the private key generator 104 are enabled through a desired form of communication, for example, via dial-up modem connections, cable links, digital subscriber lines (DSL), wireless or satellite links, or any other suitable form of communication.
[0031] Further, the user devices 102 may be one or more computing devices, such as mainframe computers, workstations, personal computers, desktop computers, minicomputers, servers, multiprocessor systems, laptops, wireless devices, wireless sensors, M2M devices, a cellular communicating device, such as a personal digital assistant, a smart phone, and a mobile phone, online terminal, and the like. In one implementation, the private key generator 104 may be one or more system or computing devices, such as a desktop computer, hand-held device, cloud servers, mainframe computers, workstation, a multiprocessor system, a hand-held device, a personal digital assistant (PDA), a smart phone, a laptop computer, a network computer, a minicomputer, a server, and the like.
[0032] The communication network 106 may be a wireless network, a wired network, or a combination thereof. The communication network 106 can also be an individual network or a collection of many such individual networks, interconnected with each other and functioning as a single large network, e.g., the Internet or an intranet. The communication network 106 can be implemented as one of the different types of networks, such as intranet, local area network (LAN), wide area network (WAN), the internet, and such. The communication network 106 may either be a dedicated network or a shared network, which represents an association of the different types of networks that use a variety of protocols, for example, Hypertext Transfer Protocol (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), Wireless Application Protocol (WAP), etc., to communicate with each other. Further, the communication network 106 may include network devices, such as network switches, hubs, routers, HBAs, for providing a link between the private key generator 104 and the user devices 102. The network devices within the communication network 106 may interact with the private key generator 104 and the user devices 102 through communication links.
[0033] In one embodiment, a user of the user device 102-1, hereinafter referred to as a sender, may wish to send some confidential data to a user of the user device 102-2, hereinafter referred to as an intended receiver. In one implementation, the user device 102-1 may use any known technique of elliptic curve cryptography, such as an identity based elliptic curve cryptography for encryption of the confidential data before transmitting the confidential data to the intended receiver. For the purpose, the user sends a request to the private key generator 104 through the user device 102-1 requesting the private key generator 104 to provide one or more public cryptography parameters used for encryption of the confidential data. In one implementation, the user device 102-1 may send a request for generating a private key of the user device 102-1.
[0034] In another implementation, the intended receiver may send a request to the private key generator 104 for a private key corresponding to a public identity of the intended receiver through the user device 102-2. The private key is used for decrypting any data encrypted using the public identity of the intended receiver, such as an encrypted confidential data. The public identity of the intended receiver may be any known information about the intended receiver, such as an e-mail address, a phone number, date of birth, and the like. Further, the public identity may also include any IP address, Mac-id, or any other identity associated with the user device 102-2 corresponding to the intended receiver.
[0035] In one implementation, based on the request from the user device 102-1, the private key generator 104 generates the public cryptography parameters. In one implementation, the private key generator 104 performs all computations for cryptographic purposes in Jacobian co-ordinate system with z co-ordinate equal to one which further helps in reduction of computation time complex mathematical operations by reducing number of complex mathematical operations such as multiplicative modular inversions over large prime associated with cryptography. For the purpose, the private key generator 104 includes a parameter generation module 108 configured to generate the public cryptography parameters. In one implementation, the public cryptography parameters may include a friendly prime, a torsion group prime order, a super singular elliptic curve,a first torsion group, a second torsion group, a first elliptic curve point, and a second elliptic curve point, hereinafter collectively referred to as elliptic curve points.
[0036] The friendly prime may be understood to be of a special form determined such that the complex algorithms used in the identity based elliptic curve cryptography may be computed in lesser time as compared to conventional techniques of computing the complex algorithms.In one implementation, the friendly prime may be of the predetermined form illustrated using equation (1), reproduced below for convenience:
p = 3 (mod 4)....................................................(1)
The friendly prime is based on a first variable and Nth power of two, where N is an integer and satisfy the condition illustrated using equation (2), reproduced below for convenience:
p = 2N ± c ........................................................ (2)
Further the base two logarithm of the first variable is greater than zero and has a maximum value equal to half of N.
log2c = (1/2)N.....................................................(3)
In one implementation, the length of friendly prime p may be 512 bits. In another implementation the length of friendly prime p may be 1024 bits.
[0037] Further, the parameter generation module 108 may define a finite field, such as a Galois field, based on the friendly prime. The finite field comprises of elements ranging from zero to a value equal to one less than the value of friendly prime.The parameter generation module 108 may subsequently determine the super singular elliptic curve over the finite field based on a set of distinctive parameters in elliptic curve equation. The super singular elliptic curve generated over the finite field is used in encryption and decryption algorithms. The form of elliptic curve used for cryptography is based on the friendly prime of the predetermined form.
[0038] Further, the parameter generation module 108 determines the first torsion group based on the friendly prime. In one implementation, the first torsion group comprises of all points obtained by repetitive addition of a point on the super singular elliptic curve to itself to obtain a point at infinity. For example, upon repeated addition of point X, lying on the super singular elliptic curve, at most 'q' times, a point Y, which is a point at infinity, is obtained, i.e., X+X+X+X.....(q times) = Y, where Y is the point at infinity and q is the torsion group prime order. The elements of the first torsion group lie on the super singular elliptic curve and the number of elements of the first torsion group is equal to the torsion group prime order. The value of the torsion group prime order perfectly divides a value obtained by adding one to the value of the friendly prime. The friendly prime and the torsion group prime order are related according to the relation given below:
q | (p+1 )..................................................(8)
where q, also a prime, is the torsion group prime order and p is the friendly prime. In one implementation, the torsion group, of prime order 160 bits, is a subgroup of points in the super singular elliptic curve out of total points p+1.In another implementation, the first torsion group may be an additive subgroup of points lying on the super singular elliptic curve.
[0039] Subsequently, the parameter generation module 108 may be configured to construct the second torsion group. In one implementation, the second torsion group may be an isomorphic image of the first torsion group over the super singular elliptic curve. The isomorphic mapping between the first and the second torsion groups simplifies the complex multiplications. For example, due to the isomorphic mapping, the structure of co-ordinates of a point B are simplified to [b1, sqrt(-1)b2], where b1 and b2 belongs to a finite field based on the friendly prime. Thus, complex multiplications in a finite field based on a friendly prime with characteristic 2 are reduced to two integer multiplications in the finite field based on the friendly prime, thereby making the computations simpler to perform. Further, a distortion mapping exist between the first torsion group and the second torsion group as described previously using equation (4), reproduced below for convenience:
F: [e, f] e S[q] ? Point [p-e, sqrt(-1)*f] e T[q]..............(4)
Further, the order of the second torsion group is equal to the order of the first torsion group, i.e., q.In one implementation, the second torsion group may be an additive subgroup of points lying on the super singular elliptic curve.
[0040] Further, the parameter generation module 108 may select a first elliptic curve point and a second elliptic curve point, hereinafter collectively referred to as the elliptic curve points, from amongst the elements of the first torsion group based on one or more predetermined rules, as described previously. The elliptic curve points are points lying over the super singular elliptic curve and may be used for encryption and decryption algorithms. In one implementation, the parameter generation module 108 may select the elliptic curve points such that 'no degeneracy' condition is satisfied during tate pairing computation, i.e. the result of the tate pairing computation of the two elliptic curve points is not equal to one. The use of the friendly prime helps in faster modular reductions, thereby reducing the complexity of mathematical operations, such as point addition, point doubling, and complex integer multiplications involved in determining the elliptic curve points by half.
[0041] The private key generator 104 further generates the public key of the user device 102-1 based on a public identity (ID) of the user. The public ID of the user may be any known information of the user, such as date of birth, passport number, and phone number. In one implementation, the private key generator 104 converts the ID of the user into an integer, say hID, of bit length 256 bits using standard hashing techniques. Thereafter, a point belonging to the first torsion group, say qID, is obtained as the public key of the user based on the integer hID. Subsequently, the private key of the user of the user device 102-1 is computed based on the public ID of the user using equation (6) reproduced below for convenience:
uID = [s]qID = qID+qID+qID+ ('s' times)..................(6)
[0042] The private key generator 104 provides the public cryptography parameters to the user device 102-1. The user device 102-1 subsequently performs encryption of the confidential data using the public cryptography parameters and a public key of the intended receiver, to obtain the encrypted confidential data. The public key of the intended receiver corresponds to the public identity of the user, such as an e-mail address, a phone number, date of birth, and the like. The encryption process involves complex mathematical structure called tate pairing, the computation complexity of which is reduced by the form of the friendly prime used in the generation of public cryptography parameters, as described previously.The user device 102-1 sends the encrypted confidential data over the non-secure communication network to the intended receiver.
[0043] Subsequently, on receiving the encrypted confidential data, the intended receiver of the encrypted confidential data may decrypt the data using its private key. The private key of the intended receiver corresponds to the public identity of the intended receiver. The use of friendly prime, however, reduces the time taken by the private key generator 104 for computation of the private key by enabling the use of modular reduction method. The use of modular reduction for computation reduces the complexity of algorithm. Thus, the friendly prime enables the implementation of identity based elliptic curve cryptography in device, such as mobile phones, smart phones, and handheld devices running lightweight applications supported by limited battery backup, less memory, and less processing power.
[0044] Although the present subject matter has been defined in reference to identity based elliptic curve cryptography, it will be understood that the private key generator 104 generating the public cryptography parametersmay be used for other schemes of cryptography, albeit with few modifications.
[0045] Figure 2 illustrates components of the private key generator 104 implementing identity based elliptic curve cryptography for secure transmission of data over the network in the presence of potential malicious third party. The private key generator 104 facilitates fast implementation of the cryptographic process and enables its use for devices, such as mobile phones, smart phones, and handheld devices running lightweight applications, in accordance with an embodiment of the present subject matter. In said embodiment, the private key generator 104 includes one or more processor(s) 202, I/O interface(s) 204, and a memory 206 coupled to the processor(s) 202. The processor(s) 202 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. The processor(s) 202 can be a single processing unit or a number of units, all of which could also include multiple computing units. Among other capabilities, the processor(s) 202 are configured to fetch and execute computer-readable instructions stored in the memory 206.
[0046] Functions of the various elements shown in the figure, including any functional blocks labeled as “processor(s)”, may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term “processor” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing software, random access memory (RAM), and non volatile storage. Other hardware, conventional and/or custom, may also be included.
[0047] The I/O interface(s) 204 may include a variety of software and hardware interfaces, for example, interface for peripheral device(s), such as a keyboard, a mouse, an external memory, a printer, etc. Further, the I/O interface(s) 204 may enable the private key generator 104 to communicate over the communication network 106, and may include one or more ports for connecting the private key generator 104 with other computing devices, such as web servers and external databases. The I/O interface(s) 204 may facilitate multiple communications within a wide variety of protocols and networks, such as a network, including wired networks, e.g., LAN, cable, etc., and wireless networks, e.g., WLAN, cellular, satellite, etc.
[0048] The memory 206 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. The memory 206 further includes module(s) 208 and data 210. The module(s) 208 include routines, programs, objects, components, data structures, etc., which perform particular tasks or implement particular abstract data types. The data 210, amongst other things, serves as a repository for storing data processed, received, and generated by one or more of the module(s) 208.
[0049] The module(s) 208 further include a user interaction module 212, the parameter generation module 108, a key generation module 214, and other module(s) 216. The other module(s) 216 may include programs or hardwired instructions that supplement applications and functions of the private key generator 104, for example, programs in the operating system.
[0050] The data 210 includes interaction data 218, parameter data 220, key data 222, and other data 224. The other data 224 may include data generated as a result of the execution of one or more modules in the other module(s) 216.
[0051] As previously described in Figure. 1, the user device 102-1, in order to encrypt confidential data which is to be sent to the user device 102-2 over the network 106, may request the private key generator 104 to provide the public cryptography parameters. In one implementation the intended receiver may send a request to the private key generator 104 for obtaining a private key corresponding to its public identity through the user device 102-2.The private key generator 104, upon verification of the intended receiver, generates and provides the private key to the user device 102-2. The intended receiver may use the private key for decrypting any data encrypted using the public identity of the intended receiver, for example, the encrypted confidential data, addressed to the intended receiver.
[0052] In one implementation, the private key generator 104 may be configured for generating the public cryptography parameters used in the encryption process. The public cryptography parameters may include friendly prime which facilitates fast computation of the cryptographic algorithms. In another implementation, the private key generator 104 may be configured to generate the private key based on the request from the intended receiver. Use of friendly prime in generating public cryptography parameters and the private key reduces the complexity of cryptographic algorithms and speeds up their computation. In one implementation, the private key generator 104 performs all computations involving elliptic curves for cryptographic purposes in Jacobian co-ordinate system with z co-ordinate equal to one which further helps in reduction of computation time of the complex computations.
[0053] In one implementation, the user interaction module 212 may be configured to receive the request for thepublic cryptography parameters sent by the user device 102-1. In another implementation, the user interaction module 212 may be configured to receive the request for the private key sent by the intended receiver using the user device 102-2. The user interaction module 212 may receive the request over a network, such as internet or any wireless network. In another implementation, user interaction module 212 may be configured to respond to the requests from user device 102-1 and the intended receiver. The request is stored in the interaction data 218.
[0054] Further, the parameter generation module 108 is configured to generate public cryptography parameters, such as a friendly prime 'p', a super singular elliptic curve based on distinctive parameters ‘a’ and 'b', a torsion group prime order 'q', a first torsion group having the torsion group prime order 'q', a second torsion group having torsion group prime order 'q' and elliptic curve points P and Q. The public cryptography parameters are used for encrypting the confidential data to obtain the encrypted confidential data which is sent to the intended receiver.
[0055] The parameter generation module 108 generates the friendly prime such that it facilitates faster computation of the cryptographic process. In one implementation, the parameter generation module 108 is configured to generate the friendly prime p of a predetermined form. The friendly prime p is based on a first variable and Nth power of two, where N is an integer, and where a maximum value of base two logarithm of the first variable is equal to half of N as defined in equation (2) and shall also satisfy condition of equation (1) as illustrated in the description of figure 1, where N may be defined as the length of prime in bits.Further, the base two logarithm of the first variable is greater than zero. In one implementation the first variable may be an integer value and the length of friendly prime may either be 512, 1024 or 2048 bits or any other higher bit lengths.
[0056] For example, the parameter generation module 108 may generate the friendly prime p of the predetermined form p equal to 65287 which is equal to and may also be represented as 216 - 249, where N is equal to 16 and is an integer and c is equal to 249, where c is referred to as a first variable. Further, the values of p, N and c also satisfies the conditions as illustrated in equations (1) and equation (3), where log2 (249) is less than or equal to 8, respectively.
[0057] Determining the friendly prime p of such a form enables the use of modular reduction method in generation of encryption keys, such as the private key, thereby reducing the complexity of the algorithm and the computation time for performing the cryptography. Further, majority of the prevailing identity based elliptic curve cryptography schemes are based on mathematical functions called bilinear non-degenerate maps, such as Weil pairing and tate pairing. For instance, the tate pairing, used in encryption and decryption, involves long integer multiplications computed using modular reductions, and therefore, choice of above type of friendly prime p considerably reduces computational complexity. Friendly prime p enables faster computation of the algorithms involved in the cryptographic process, thereby making it useful for implementation in devices running lightweight applications.
[0058] Further, the parameter generation module 108 may define a finite field, such as a Galois field, based on the friendly prime. The finite field comprises of a pre-determined number of elements, where value of the elements is ranging from zero to a value equal to one less than the value of the friendly prime. In elliptic curve arithmetic, calculations performed in finite field domain speeds up mathematical operations involved in several cryptographic algorithms. Typically the finite field is denoted by GF(p).
[0059] The super singular elliptic curve is determined using a set of distinctive parameters in the elliptic curve equation obtained from weierstrass equation for the elliptic curve, as would be understood by a person skilled in the art. The super singular elliptic curve is used in the encryption and decryption algorithms and for generation of encryption keys, such as the private key of the intended receiver. In one implementation, the distinctive parameters a and b may be used to determine the form of the super singular elliptic curve based on the friendly prime to be used for cryptography. The distinctive parameters may be used to generate the super singular elliptic curve using the following elliptic curve equation:
y2 = x3 + ax + b ................................................... (9)
where a,b,x and y belong to GF(p). The super singular elliptic curve obtained using distinctive parameters is defined over the finite field and is used in the cryptographic operations for generation of encryption keys and in encryption and decryption algorithm. Typically, the super singular elliptic curve over the finite field GF(p) is expressed as E/GF(p).
[0060] In one implementation, the parameter generation module 108 is configured to generate the distinctive parameters a and b of a form such that the elliptic curve obtained using a and b is a super singular elliptic curve. For example, for a=1 and b=0, the equation of the super singular elliptic curve may be obtained as follows:
y2 = x3 + x .......................................................... (10)
[0061] Based on the super singular elliptic curve defined over the finite field, the parameter generation module 108 determines the first torsion group having torsion group prime order q related to the friendly prime p. The number of elements of the first torsion group is termed as the order q of the first torsion group. The order q is of a form illustrated using equation (8), reproduced below for convenience:
q | (p+1 ).........................................................(8)
The elements of the first torsion group are points on the super singular elliptic curve over the finite field.For example, the parameter generation module 108 determines the order of the first torsion group q equal to 8161 based on the value of the friendly prime p as described in the previous example. The prime order q also satisfies the relation as illustrated in equation (8), where the order the first torsion group perfectly divides the value of the friendly prime. For instance, as described in the previous example, the order q equal to 8161 divides the sum of friendly prime p and one equal to 65288 and the quotient of the division is 8 and the remainder is zero. Typically, the first torsion group is denoted as S[q].
[0062] Subsequently, the parameter generation module 108 may be configured to construct the second torsion group.Typically, the second torsion group is denoted as T[q]. In one implementation, the second torsion group is an isomorphic image of the first torsion group over the super singular elliptic curve under the distortion mapping given by relation (4), reproduced here for convenience:
F: [e, f] e S[q] ? Point [p-e, sqrt(-1)*f] e T[q]..............(4)
As described previously, due to the result ofthe isomorphic mapping between the first and the second torsion groups, the complex computations are reduced to two integer multiplications in the finite field based on the friendly prime., thereby making the computations simpler to perform. The order of the second torsion group is equal to that of the first torsion group, i.e., q.In one implementation, the second torsion group may be an additive subgroup of points lying over a super singular elliptic curve over a finite field over p2, where p is the friendly prime. The finite field over p2 is denoted as GF(p2).
[0063] Further, the parameter generation module 108 selects the elliptic curve points, P and Q from amongst the elements of the first torsion group based on one or more predetermined rules, for example, no degeneracy during tate paring computations. In one implementation, the parameter generation module 108 may generate the elliptic curve point P by conventional known methods involving selection of a random integer other than zero, say, x from within the range of the finite field. The conventional known methods involve a chain of point additions and point doublings in the first torsion group besides many other mathematical operations. Each point addition involves 2 additions modulo p and 12 multiplications modulo p, where p is the friendly prime of the aforementioned predetermined form. Further,each point doubling involves 1 addition modulo p and 3 multiplications modulo p. Point additions and point doublings are done in Jacobian coordinates to avoid inversion modulo p operation at the end of each point addition and point doubling. However the output of the conventional method, i.e., P is expressed in affine coordinates through a single inversion modulo p after the chain of point doublings and point additions. All of the operations, i.e., additions modulo p and multiplications modulo p involve modular reductions which are reduced to only a single modular reduction due to the form of p. In one implementation,the elliptic curve point P may be generated using MATLAB programs as would be understood by a person skilled in the art. Similarly, the parameter generation module 108 may generate another elliptic curve point Q based on the elliptic curve point P using conventional methods by selecting another random integer other than zero and the previously selected random integer, say s, from within the range of the finite field. For example, for the friendly prime p, the integers are selected from a range of 1 to p-1. In one implementation, the elliptic curve point Q may be obtained by a product operation of s and P as[s]P, where [s]P implies addition of point P to itself, s times as shown in equation (5) reproduced here for convenience:
Q = [s]P=P+P+P+P....('s' times)...............................(5)
where, P and Q are the elliptic curve points and belong to the first torsion group and the second torsion group, respectively, and s is a master secret key of the private key generator. The elliptic curve points P and Q are used for encryption and decryption algorithms which involve complex mathematical tate pairing operations computed using Miller algorithm.
[0064] For example,the parameter generation module 108 generates an elliptic curve point P on the elliptic curve using an integer x equal to 53630. Based on conventional MATLAB functions with x as input, the co-ordinates of P may be determined as P[x] equal to 20303, P[y] equal to 37742, and P[z] equal to 1. Here P[x], P[y], and P[z] are the co-ordinates of P in the Jacobian co-ordinate system.
[0065] Subsequently, the parameter generation module 108 generates another elliptic curve point Q based on equation as illustrated in equation (5) using P and the master secret key s, where s is equal to 4840. The elliptic curve point Q obtained using equation (5) has co-ordinates given by Q[x] equal to 54437, Q[y] equal to 44500, and Q[z] equal to 1.Here Q[x], Q[y], and Q[z] are the co-ordinates of Q in the Jacobian co-ordinate system.
[0066] The elliptic curve points P and Q are used for encryption and decryption algorithms which involve mathematically complex tate pairing operations. The use of friendly prime reduces the computation time for the encryption and decryption algorithms by enabling the use of modular reduction method, as described previously. The public cryptography parameters generated by the parameter generation module 108 are stored in the parameter data 220.
[0067] In one implementation, the key generation module 214 generates a public key and a private key of a user of the user device 102-1. The public key of the user is generated based on a public identity (ID) of the user. The ID may be any public information of the user, such as an e-mail address, date of birth, phone number of the user. In one example, the ID may be a MAC-ID of a user device corresponding to the user. In one implementation, the ID of the user is converted into an integer, say hID, using standard hashing techniques. In one example, the hID is an integer of bit length 256 bits. Thereafter, a point, say qID, belonging to the first torsion group is generated using hID. The point hID is the public key of the user generated based on the ID of the user. Further, the private key of the user, say uID, is computed based on product operation of s and the public key qID represented as [s]qID. Here, [s]qID implies addition of point qID, s number of times illustrated in the equation given below:
uID = [s]qID = qID+qID+qID+ ('s' times)..................(6)
The complexity of the computations and the operations for generation of the public key and the private key are significantly reduced as a result of the friendly prime and the super singular elliptic curve.
[0068] In another implementation, the key generation module 214 may be configured to compute the private key of the intended receiver based on the request from the intended receiver. As will be understood, the key generation module 214, generates the public key and the private key of the intended receiver in a manner as described above.
[0069] For computing the private key, the key generation module 214 performs point multiplication operation involving the public identity of the intended receiver and the master secret key s over the super singular elliptic curve. In another implementation, the key generation module 214 may obtain the public cryptography parameters stored in the parameter data 220 and generate an elliptic curve, such as the super-singular singular elliptic curve given by equation (10), as described previously. The key generation module 214 may then compute the private key based on the public identity of the intended receiver and the master secret key s over the elliptic curve. Computation of the private key involves complex mathematical operations, such as point addition, point doubling operations which involves integer addition, long integer multiplications. The complex mathematical operations involve modular reductions making the process complex and time consuming. Use of friendly prime p speeds up the process, as friendly prime p achieve faster modular reductions over large primes in a single step at the cost of one long integer multiplication. Further, friendly prime p and computation of all the elliptic curve operationsperformed in Jacobian coordinate system enables the use of fast modular reduction for computing the arithmetic operations and also reduces the number of multiplicative modular inverses, thereby reducing the number of extended Euclidean GCD operations. The public key computed by the key generation module 214 is stored in key data 222.
[0070] Further, the user interaction module 212 may be configured to provide the public cryptography parameters to the user device 102-1. In one implementation, the user interaction module 212 may be configured to provide the private key to the intended receiver.
[0071] Upon receiving the public cryptography parameters,the user device 102-1 encrypts the confidential data using the public cryptography parameters and a public key of the intended receiver. The user device 102-1 generates a public key of the intended receiver corresponding to the public identity of the intended receiver. The public key is based on the public identity, such as an e-mail id, a phone number, date of birth, and the like. In order to encrypt the data, the user device 102-1 may use any existing known encryption scheme for encrypting the confidential data. For example, the user device 102-1 may use identity based cryptography implementing tate pairing for encryption of the confidential data. The tate pairing computations involves long integer multiplications and modular multiplications and therefore, use of friendly prime p greatly reduces the complex computation involved in the encryption process.
[0072] The user device 102-1 sends the encrypted confidential data to the intended receiver over the non-secure communication network. For decrypting the encrypted confidential data, the intended receiver may use the private key corresponding to the public identity of the intended receiver.
[0073] For the purpose of validation of the efficiency of the above described subject matter, an analysis of the number of computational steps involved in the mathematical operations, such as point addition and point doubling, related to encryption algorithm was performed. Mathematical operations, such as point addition and point doubling involve a number of sub-operations, such as addition, subtraction, multiplication, and squaring. A comparison of the number of arithmetic operations involved in performing the group operations on elliptic for the present subject matter and a conventional encryption method, pairing based IBE scheme, proposed by Boneh and Franklin in 2001, as described earlier, is provided in the table 1 below. The comparison is done for each sub-operation involved in the mathematical operations to illustrate the efficiency of the present subject matter.
TABLE 1
Operation
Existing Method Our Method
Addition Subtraction Multiplication Squaring Total Addition Subtraction Multiplication Squaring Total
Point Addition 12 6 16 12 46 2 4 12 4 22
Point Doubling 3 3 10 9 25 1 3 3 6 13

As observed, the use of friendly prime leads to a reduction of 52% and 48% in number of modular reductions in point addition and point doubling operations, respectively, as compared to the conventional method.The use of friendly prime results in reduction in computation time and the resources needed for performing the encryption algorithm as it enables the use of modular reduction for performing complex computations. Thus, the friendly prime reduces the computational time and enables the use of identity based elliptic curve cryptography in devices, such as mobile phones, smart phones, and handheld devices running lightweight applications and having limited battery backup, less memory, and less processing power.
[0074] Thus, the private key generator 104 facilitates faster implementation of cryptographic process by reducing the complexity of the algorithms involved in the cryptographic process. Moreover,the private key generator 104 enables the use of cryptographic schemes for devices, such as mobile phones, smart phones, handheld devices running lightweight applications, having less processing, less memory and limited battery backup.
[0075] Figure. 3 illustrates an exemplary method 300 for identity based elliptic curve cryptography, according to an embodiment of the present subject matter. The method 300 may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, etc., that perform particular functions or implement particular abstract data types. The method 300 may also be practiced in a distributed computing environment, where functions are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.
[0076] The order in which the method 300 is described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method 300, or an alternative method. Additionally, individual blocks may be deleted from the method 300 without departing from the scope of the subject matter described herein. Furthermore, the method 300 can be implemented in any suitable hardware, software, firmware, or combination thereof. The method 300 is presently provided for identity based encryption. Although, the method 300 has been described in context of the network environment 100, the same should not be construed as a limitation. It will be apparent that the method 300 may be implemented for identity based elliptic curve cryptography in various other similar system and devices.
[0077] At block 302, a request for public cryptography parameters and a private key is received from a user device. In one implementation, the private key generator 104 receives the request from the user device 102 corresponding to a user. The public cryptography parameters are used for encrypting a plaintext to obtain a cipher text using identity based elliptic curve cryptography. Further, the ciphertext is decrypted using the private key. In one implementation, the public cryptography parameters include a friendly prime, a super singular elliptic curve, a torsion group prime order, a first torsion group, a second torsion group, a first elliptic curve point, and a second elliptic curve point.
[0078] At block 304, a friendly prime is ascertained based on the request. The friendly prime is used for determining other public cryptography parameters used in the encryption process. The form of friendly prime determines the computational complexity of the algorithms associated with the encryption process.For example, the form of friendly prime may affect the number of steps involved in the algorithms associated with encryption process. In one implementation, the private key generator 104 ascertains the friendly prime of a predetermined form illustrated using equation (1), reproduced below for convenience:
p = 3 (mod 4)..............................................(1)
In said implementation, the friendly primes is based on a first variable and Nth power of two, where N is an integer, illustrated using equation (2), reproduced below for convenience:
p = 2N ± c.....................................................(2)
Further, the base two logarithm of the first variable is greater than zero and has a maximum value equal to half of N.
illustrated using equation (3), reproduced below for convenience:
log2c = (1/2)N...............................................(3)
In one example, the length of prime p may be 512 bits, In another implementation the value of prime p may be 1024 bits or any higher bits.
[0079] At block 306, a finite field, such as a Galois field, is defined based on the friendly prime. In one implementation, the parameter generation module 108 may define the finite field based on the friendly prime. The finite field may comprise of elements ranging from zero to one less than the value of friendly prime. In one implementation, the elements of finite field may comprise of integers. For example, for a given prime integer j, the finite field Fj consists of integers between 0 and j-1.
[0080] At block 308, a super singular elliptic curve is generated over the finite field based on a set ofdistinctive parameters. The super singular elliptic curve generated is used in the encryption and decryption algorithms and for generation of encryption keys, for example, the private key of the user. In one implementation, the parameter generation module 108 may be configured to generate the super singular elliptic curve defined over the finite field.The distinctive parameters may be defined as parameters used for defining the form of the super singular elliptic curve. In one implementation, the distinctive parameters are of a form such that the elliptic curve obtained based on the distinctive parameters is a super singular elliptic curve illustrated using equation (10), reproduced below for convenience:
y2 = x3 + x............................................... (10)
[0081] At block 310, a first torsion group on the super singular elliptic curve is determined based on the friendly prime. In one implementation, the parameter generation module 108 may be configured to determine the first torsion group on the super singular elliptic curve based on the friendly prime. The number of elements of the torsion group is termed as the torsion group prime order. Further, the value of the torsion group prime order perfectly divides the value of friendly prime and is of a form such that it satisfies the relation as illustrated using relation (8), reproduced below for convenience:
q | (p+1 ).........................................................(8)
[0082] At block 312, a second torsion group is constructed based on the first torsion group.In one implementation, the second torsion group is an isomorphic image of the first torsion group over the super singular elliptic curve under the distortion mapping given by the relation stated in equation (4), reproduced below for convenience:
F: Point [e, f] e S[q] ? Point [p-e, sqrt(-1)*f] e T[q]..............(4)
As a result ofthe isomorphic mapping between the first and the second torsion groups, complex computation involving complex multiplication in GF(p2) are reduced to two integer multiplications in GF(p), where GF(p2) and GF(p) are Galois extension field and Galois finite fields respectively, based on the friendly prime.Further, the first torsion group and the second torsion group have the same torsion group prime order.
[0083] At block 314, at least one elliptic curve point is selected from amongst the elements of the first torsion group. In one implementation, the parameter generation module 108 is configured to select two elliptic curve points from the first torsion group. At first, a first elliptic curve point, say, P is selected based on an integer. The integer may be selected from within a range of one and p-1, where p is the friendly prime. Thereafter, the parameter generation module 108 determines a master secret key from a range of one and p-1. The master secret key is selected in a manner such that its value is not equal to the afore selected integer. Subsequently, a second elliptic curve is obtained based on the first elliptic curve point and the master secret key, as described previously.
[0084] At block 316, a public key and a private key of a user of the user device is generated. The public key of the user is generated based on a public identity (ID) of the user. The ID may be any information of the user, such as a phone number, date of birth, and MAC-ID of the user device of the user. In one implementation, the key generation module 214 generates the ID the user using standard hashing techniques. Thereafter, a point on the super singular elliptic curve is ascertained as the public key based on the ID. Subsequently, the private key of the user is computed based on the public key of the user as described previously using equation (6). The cryptographic operations typically involve complex and long integer multiplications and require lot of computation time. The use of friendly prime enables the use of modular reduction for complex computations, thereby reducing the computation time required for cryptographic operations. In one implementation, the private key generator 108 performs all computations for cryptographic purposes in Jacobian co-ordinate system which further helps in reduction of computation time of encryption and decryption algorithms. In said implementation, the computations are performed with z co-ordinate equal to one.
[0085] At block 318, the public cryptography parameters and the private key of the user are provided to the user device. In one implementation, the user interaction module 212 may be configured for providing the user device with the public cryptography parameters and the private key of the user.
[0086] The systems and methods of present subject matter enable implementation of identity based elliptic curve cryptography in lightweight applications. Thus, the present subject matter allows cryptographic operations to be carried out in lightweight devices having less processing power, less memory space, and low battery backup. The use of friendly primes along with the first torsion group, second torsion group, elliptic curve points and carrying out all the elliptic curve operations in Jacobian co-ordinate system reduces the complexity of the cryptographic algorithms and enables fast computation of the same.
[0087] Although implementations for identity based elliptic curve cryptography have been described in language specific to structural features and/or methods, it is to be understood that the appended claims are not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as exemplary implementations for identity based elliptic curve cryptography.