Applications and Benefits of Elliptic Curve Cryptography Krists Magons University of Latvia, Faculty of Computing, Raiņa bulvāris 19, Riga, LV-1586, Latvia km10054@lu.lv Abstract. This paper covers relatively new and emerging subject of the elliptic curve crypto systems whose fundamental security is based on the algorithmically hard discrete logarithm problem. Work includes the study of the following issues: mathematical background of the elliptic curve crypto systems, discrete logarithm problem, practical use cases in the industry, common implementation mistakes, performance comparison of elliptic curve and RSA crypto systems etc. The conclusion contains a brief summary of the elliptic curve cryptosystem prac- tical applications, the potential practical benefits and disadvantages with respect to the widely used RSA crypto system. 1 Introduction The origins of asymmetric cryptography are associated with Whitfield Diffie and Martin Hellman famous 1976 publication that launched the revolution in cryptography [1, 2]. That publication pointed out a number of algorithmically hard problems such as the discrete logarithm problem. Afterwards the foundation of modern public key cryptogra- phy was defined. One of the most significant results was the discrete logarithm problem which is used in several crypto systems like DSA, ECDH, as well as virtually in any elliptic curve based crypto system design. The problem is easily to define: G – finite cyclic group , g – generator of G, a ∈ G, find natural number s, such as gs = a, if s exists [1]. It is believed that such issue is an algorithmically hard prob- lem, which means that there is no general algorithm that solves the discrete logarithm problem in polynomial time. In this paper the author reviews the practical use of the elliptic curve public key crypto systems which are based on the discrete algorithm problem. Elliptic curves are studied for more than a century [3] and are used not only in cryptography, but also in the fields of computer science such as coding theory, pseudo-random number generation and others [3]. The origins of the elliptic curve cryptography date back to 1985 when two scientists N. Koblitz and V. Miller came up with the idea that it is possible to use the set of points defined by an elliptic curve over finite prime field in the crypto systems whose security is based on the discrete logarithm problem. Elliptic curve based crypto systems versus those crypto systems which are based on the integer factorization problem offer significant advantages because the known methods for computing the discrete logarithm Applications and Benefits of Elliptic Curve Cryptography 33 are not feasible to be practically used on the elliptic curve based crypto systems. One of the most important practical benefits is significantly reduced key sizes compared to other crypto systems. For instance, from the security standpoint elliptic curve based crypto system with key length of 163 bits is comparable to RSA based cryptosystem whose key length is equivalent to 1024 bits [4]. 2 Elliptic Curves Over Finite Prime Field F p Let F p be a finite prime field that contains exactly p elements and p is an odd prime number. For each odd prime number p exists exactly one finite prime field F p , however, the representation of field elements may vary [5]. If a, b ∈ F p and 4a3 + 27b2 6≡ 0 (mod p) then the elliptic curve over F p is the fol- lowing set of points [6]: E(F p ) = {(x, y)} ∈ F p 2| y2 ≡ x3 +ax+b (mod p) ∧ 4a3 +27b2 6≡ 0 (mod p) ∧ a, b, y, x ∈ F p } ∪ {O }, where O is the point at infinity The number of elements #E(F p ), in E(F p ) is equal to the number of points of elliptic curve over F p . According to the Hasse Theorem #E(F p ) belongs to the interval [5] : √ √ p + 1 − 2 p ≤ #E(F p ) ≤ p + 1 + 2 p It is proved that the elements of E (F p ) form abelian group. The number of elements #E(F p ) in E (F p ) is called the order of group. The order of group can be algorithmi- cally determined by taking full scan of elements in O(p) time, however, there are more efficient algorithms available, for instance, the Schoof’s algorithm [7, 8]. 2.1 The Algebraic Definition of Addition Operation in E(F p ) The addition operation in E(F p ) is defined by the following axioms [5]: 1. O + O = O 2. ∀ (x,y) ∈E (F p ) : (x, y) + O = O + (x, y) = (x, y) 3. ∀ (x,y) ∈E (F p ) : (x, y) + (x, −y) = (x, −y) + (x, y) = O 4. (x1 ,y1 ) ∈E (F p ) , (x2 ,y2 ) ∈E (F p ) , x1 6=x2, , then (x1 ,y1 ) + (x2 ,y2 ) = (x2 ,y2 )+(x1 ,y1 ) = (x3 ,y3 ) 5. x3 ≡λ2 −x1 −x2 (mod p) 6. y3 ≡λ (x1 −x3 ) −y1 (mod p) −y1 7. λ≡ xy22 −x 1 (mod p) 8. (x1 ,y1 ) ∈E (F p ) y1 6= 0 (x1 ,y1 ) + (x1 ,y1 ) = (x4 ,y4 ) 9. x4 ≡λ22 −2x1 (mod p) 10. y4 ≡λ2 (x1 −x4 )−y1 (mod p) 3x2 +a 11. λ2 ≡ 2y1 (mod p) 1 34 K. Magons 2.2 The Algebraic Definition of Scalar Multiplication Operation in E(F p ) Crypto systems based on elliptic curves over F p largely utilize the scalar multiplication operation. Let P be a point of an elliptic curve over F p , n ∈ N, then the scalar multipli- n cation is defined as addition of P n-times [8]. The result is denoted as nP. nP = ∑ P, i=1 where addition is the E (F p ) addition operation. The scalar multiplication operation can be effectively carried out in O (log n) time by using the addition operation axioms and algorithms such as Double and Add algorithm [8]. 2.3 Cyclic Subgroups of E(F p ) By examining an elliptic curve over fixed prime field F p , it is easy to observe that the set of all scalar multiplications of given point P forms a cyclic subgroup of E(F p ) [8, 9]. The point P is called the generator of subgroup. The order of subgroup is the smallest non-negative number n ∈ N such that nP = O . It is not possible to use the Schoof’s algorithm to find the order of subgroup [7, 8]. To find the order of cyclic subgroup it is required to use the Lagrange’s theorem on subgroup order which states that for any finite group G, the order of every subgroup H of G divides the order of G [9]. In practice it is important to use cyclic subgroups with maximum possible order. In order to construct an elliptic curve based crypto systems, the curve E and underlying field F p are fixed, the order of E(F p ) is calculated by using the Schoof’s algorithm, then the largest maximum prime factor n of #E(F p ) should be chosen as an order of cyclic subgroup [8]. To find a suitable group generator element (point on the curve E), calculate the cofactor h = #E(F p )/n, randomly select an element H of E(F p ). If hH 6= O , then H is the generator of cyclic subgroup, otherwise repeat the previous step [8]. 3 The Discrete Logarithm Problem If all the points of an elliptic curve over finite prime field F p form a group E(F p ) and P is one of the points of the curve and n ∈ N, then the scalar multiplication nP is called the discrete exponent at base P and power n. Discrete exponents have significant properties similar to classic exponents. [10]. For the discrete logarithm problem based crypto systems the following property is very important: (n+m) P=nP∗mP, where n, m ∈ N ∧P ∈E The question: given points Q ∈ E(F p ), P ∈ E(F p ) find positive integer n such that Q = nP if such n exists. As mentioned in previous chapters, the elliptic curve cryp- tography utilizes the cyclic subgroups of E(F p ), so it is clear that the n must be in the range 0 ≤ n <#hPi, where #hPi is the order of cyclic subgroup generated by P. The number n is the discrete logarithm of base P. It is proved that discrete logarithms, like discrete exponents, have similar characteristics to the classic logarithms of real numbers [10]. We can use familiar notation: n = logP (Q) , when Q = nP. Significant property of discrete logarithms [10]: logP (h ∗ j) ≡ logP (h) + logP ( j) ( mod #hPi ) Applications and Benefits of Elliptic Curve Cryptography 35 There is no such polynomial time algorithm which computes discrete logarithms for all cases. It should be noted that no proofs are available which states the non existence of such algorithm. In practice, exponential time algorithms are available [1, 3, 10] which compute discrete logarithms for cyclic subgroup G of E(F p ). For √ instance, Shank’s Baby-Steps, Giant-Steps algorithm computes discrete logarithms in #G steps where each step is one group addition operation [3] . Another algorithm √ is the Pollard πn p-method which computes discrete logarithms in approximately 2 steps where n is the order of subgroup G [3]. The mentioned algorithms are two of the best known methods of computing discrete logarithms for elliptic curve based crypto systems. To ensure maximum security of the crypto system (to increase the time required to solve the discrete logarithm problem), elliptic curve and underlying finite prime field must be properly selected. For instance, if #E(F p ) = p then there is an algorithm available which computes discrete logarithms in O(log p) time [11]. Despite the fact that virtually all public key cryptography solutions can be imple- mented by using the popular RSA crypto system, crypto systems based on the discrete logarithm problem have several advantages over the integer factorization problem based crypto systems like RSA [10]: • Technical advantages. If there are two algorithms which provide similar functio- nality, but one is based on the elliptic curve crypto system, while the other on the RSA crypto system, the first case of solving discrete logarithms is harder as integer factorization in the second case. The benefit is obvious. Discrete logarithm-based crypto systems have significantly smaller key sizes compared to RSA [10]. • Potential patent issues related to the RSA algorithms [10]. • Mathematical backgrounds. Possibility to improve the existing RSA crypto system security by introducing additional data-protection algorithms based on the discrete logarithm problem. 4 Crypto Systems Based on Elliptic Curves Algorithms of cryptosystems based on elliptic curves use tuples of parameters to define an underlying curve E. E = (p, a, b, P, n, h) where p is a prime number which determines the finite prime field, a and b are coefficients of the curve, P – point on the curve, generator of cyclic subgroup, n – order of subgroup, h – cofactor of subgroup [5, 12]. As mentioned, there are classes of elliptic curves which are considered unsafe for use in cryptography. For instance, there are weak elliptic curves which allow calculation of discrete logarithms in polynomial time [11, 12]. To prevent malicious use of ellip- tic curves in the implementations of crypto systems, the curve coefficients a, b and the subgroup generator P can be randomized by using hash functions. In such cases, the set of curve parameters is extended by adding probabilistic number s, which is used to generate parameters a, bandP. An elliptic curve with probabilistic parameter s is de- noted as verifiably random elliptic curve [12]. The generation of verifiably random curves is standardized, there are different methods of selecting the most appropriate hash function to generate the curve. 36 K. Magons Although such approach provides relative protection against maliciously selected elliptic curves, however, there are certain risks involved, such as security and reliability of hash function being used to generate the curve parameters. General key generation in elliptic curve based crypto systems: For an elliptic curve E = (p, a, b, P, n, h) , there are key pairs (d, Q), where d is the private key which is natural number from the interval [1, n − 1] and Q is the point of an elliptic curve which is the public key Q = (xq , yq ) = dP [5]. 4.1 ECDH Crypto System ECDH (Elliptic Curve Diffie-Hellman) is the version of Diffie-Hellman key exchange algorithm for elliptic curves, which determines the method how two communication participants A and B can generate key pairs and exchange their public keys via insecure channels. The algorithm determines only the method how key pairs are generated, the user defines the relation between encryption keys and data to be encrypted [7, 12]. After the keys have been exchanged it is common to use symmetric encryption methods. In practice, ECDH crypto system can be successfully adapted to different data security solutions [7]. The ECDH algorithm: Given an elliptic curve over finite prime field E(F p ). Com- munication participants A and B agree on a point Q ∈ E(F p ) , which is freely available in the communication medium. The participant A secretly chooses probabilistic posi- tive integer kA, calculates kA Q and sends it to the party B. The member B also selects probabilistic positive integer kB , calculates kB Q and sends it to the participant A. The shared secret P = kA kB Q. The participant A calculates P, by multiplying the received point kB Q with the secret private key kA . The participant B respectively calculates P by multiplying the received point kA Q with the secret private key kB [12]. After the public key exchange, one of the most typical methods how the encrypted messages are synchronized is the version of ElGamal crypto system for elliptic curves [1]. As the set E(F p ) is finite there is a limited set of information which could be en- crypted by using points of the curve [1]. Also, there are no practical methods available to deterministically generate points of the given curve [1]. The problem can be solved by creating relation between the x-coordinate of given curve point P ∈ E(F p ) and a field F p element that may not be a point on the curve [1]. There are algorithms Compress Point and Decompress Point available which allow reduction of the amount of memory required for storing the curve points in the computer memory by two times. It is possible to clearly identify the curve point P = (xy) by specifiying the x-coordinate of point P and parity bit b. b ≡ y (mod 2) [1]. 4.2 ECDSA Crypto System ECDSA (Elliptic Curve Digital Signature Algorithm) is DSA (Digital Signature Algo- rithm) digital signature standard analogue for elliptic curves. Like DSA, the goal of ECDSA is to provide verifiable digital signatures for data messages. ECDSA standard was approved in 2000 as NIST FIPS 186-2 [1]. Applications and Benefits of Elliptic Curve Cryptography 37 The author signs the data message by using his private key. The digital signature is added to the content of the message and can be freely validated by using the message author’s public key. Private keys are generated very much alike to ECDH crypto system. If P and Q are two points on an elliptic curve, then the private key is the discrete logarithm m=logP Q [1]. Algorithm of adding digital signatures works as follows: Participants A and B agree on a set of curve E(F p ) parameters E = (p, a, b, P, n, h). Let us suppose that the participant A wants to sign the message z ∈ N and the participant B wants to validate the digital signature of the received message by using the participant’s A public key. Computing the digital signature: 1 The participant A selects arbitrary integer k from the interval [1; n-1] where n is the order of cyclic subgroup hPi of E(F p ). 2 The participant A computes the point Q = kP. 3 The participant A computes r ≡ xQ (mod n) , where xQ isthe x − coordinate o f Q. 4 If r = 0, A repeats the previous step. 5 The participant A computes s ≡ k−1 (z + r ∗ kA ) (mod n), where kA is the private key of A. 6 If s = 0, choose different random k ∈ [1; n-1] and repeat the algorithm. 7 The tuple (r, s) is the digital signature [12]. Verification of digital signature: 1. The participant B computes i ≡ s−1 ∗ z (mod n). 2. The participant B computes j ≡ s−1 ∗ r (mod n). 3. The participant B computes the point Q = iP + jK’A , where k’A is the public key of A. 4. The digital signature is valid if and only if r ≡ xQ (mod n) [12]. The ECDSA crypto system standard is widely used in practice. Along with the ECDH crypto system, ECDSA is being used in various network cryptographic protocols such as SSL and TLS, smart card solutions, embedded systems etc. 5 Typical Implementation Issues Implementation issues of elliptic curve based crypto systems can be divided into four abstract categories. The first category includes technical errors with regard to hardware and software implementations in the form of lack of authentication, inadequate RAM and media pro- tection, errors in algorithms, incorrect network infrastructure etc. For those security problems it is common that the sensitive information, including private encryption keys, can come at the disposal of third parties without attempts of breaking the fundamen- tal security background of the crypto system but by accessing the information directly 38 K. Magons through the hardware and software security holes. This is the most common implemen- tation issue and is not related to the security of the fundamentals of crypto system. It is associated with insufficient software testing and computer system security audits. The second type of implementation issues is associated with the selection of under- lying elliptic curves and prime fields. As mentioned, there are classes of weak elliptic curves. For instance, it is possible to solve the discrete logarithm problem in polynomial time for certain class of curves where #E(F p ) = p – the number of points on a curve is equal to the number of elements in a finite field [3, 11]. Also, it is important to select large enough subgroups of E(F p ) to avoid feasible calculation of discrete logarithms by methods such as Pollard-p method [1, 13]. To ensure maximum security of the crypto system it is advisable to use verifiably random elliptic curves and prime fields such that the order of group #E(F p ) is divisible by a sufficiently large prime number n where n > 2160 [3]. The third type of implementations issues is associated with the performance of E(F p ) group operations like addition and scalar multiplication. It is advisable to use Mersenne primes, which can significantly improve the performance of the scalar mul- tiplication operation [3]. This result is related to the processor architecture that enables an effective execution of module arithmetic operations with binary representation of the number, which is close to power of two [14]. Also, it is important to select the most appropriate coordinate system to improve the performance of group operations [5]. De- pending on the selected coordinate system, the performance of group operations may vary. For instance, the performance of scalar multiplication can be improved by using Jacobi coordinate system in cases where the scalar multiplication takes place with even number (point doubling) [14]. It is possible to apply the Jacobi coordinate system by using the following connection to affine coordinates: Jacobi coordinates represent an affine point (X/Z 2 ,Y /Z 3 ) on elliptic curve y2 = x3 + ax + b as a point (X:Y:Z), where Y 2 = X 3 + aXZ 4 + bZ 6 , Z 6= 0 [15]. The fourth type of implementations problems is associated with the private key management. It is required to ensure that the private keys are being re-calculated and re-issued on regular basis. Usage of constant private keys seriously increases the risk of keys being intercepted by a third party. The most typical example is the interception of a private key from 2010 with Sony PlayStation application signature crypto system where a constant private key was used for all issued digital signatures [13]. 6 Security of Elliptic Curve Based Crypto Systems Versus RSA The fundamental security of elliptic curve crypto systems is based on the algorithmi- cally hard discrete logarithm problem. Elliptic curve cryptography is one of the most important practical applications of discrete logarithms nowadays [10]. According to the literature, MIPS (million instructions per second) capable com- puter can execute 4×104 E(F p ) group addition operations per second which is approxi- mately 240 additions per year [3]. It is clear, that this assumption is hypothetical and in practice may vary due to many factors related to the computer architecture, software and elliptic curve parameters. Applications and Benefits of Elliptic Curve Cryptography 39 Koblitz, Menezes and Vanstone have published the assessment of the required com- puting time to solve discrete logarithms by Pollard p-method in cyclic subgroups of E(F p ) with various orders n. The results are summarized in the table below. Table 1. The Assessment of the Required Computing Time to Solve Discrete Logarithms by Pollard p-method [3] Size of n MIPS (bits) (years) 512 3 x 104 768 2 x 108 1024 3 x 1011 1280 1 x 1014 1536 3 x 1016 2048 3 x 1020 Pollard p-method can be parallelized. Thus, by using multi-processor computer sys- tems, it is possible to reduce the time required to solve discrete logarithms. Theoretical assessment: if 10 000 computers capable of 1,000 MIPS are available and n is 2160, then the calculation of single discrete logarithm takes approximately 85,000 years [3]. There are very specific cryptographic processor architectures available, which pro- vide the hardware level support of execution of parallelized Pollard p-method [5]. How- ever, in practice modern general computers have built-in very capable graphic cards which are easily accessible and very strong cryptographic problem solving devices. It is obvious that the computation of a single discrete logarithm could lead to the leakage of a single private key. Easy to conclude that in general case the illegitimate private key computation of elliptic curve based crypto systems is extremely expensive operation. RSA (Rivest, Shamir, Adleman) is the most widely used public-key crypto system [4]. Since its introduction in 1977 [2] it is used around the world on wide range of security system solutions scaling from private users to global corporations. Opposite to elliptic curve crypto systems, which are fundamentally based on the algorithmically hard discrete logarithm problem, RSA fundamental security is based on the algorithmically hard integer factorization problem which could be defined as follows: given the product n of two primes q, p, find p and q such that n = qp [1]. The mathematical background of RSA is based on elementary modular arithmetic, which is relatively long known and well studied. Currently, one of the most effective methods of solving the integer factorization problem is General Number Field Sieve algorithm [1]. This algorithm works in sub- exponential time [16]. As mentioned, the best known algorithms for solving the discrete logarithm problem are capable of exponential running time. For comparisons, Koblitz, Menezes and Vanstone have also published the assessment of the required computing time to solve the integer factorization problem by General Number Field Sieve algo- rithm [3], the results are summarized in the table bellow. 40 K. Magons Table 2. The Assessment of the Required Computing Time to Solve the Integer Factorization Problem by General Number Field Sieve Algorithm [3] Size of n MIPS (bits) (years) 512 3 x 104 768 2 x 108 1024 3 x 1011 1280 1 x 1014 1536 3 x 1016 2048 3 x 1020 It is obvious that in general case the discrete logarithm problem is algorithmically harder than the integer factorization problem. Easy to notice, compared to elliptic curve based crypto systems, RSA keys can be obtained in relatively shorter time. In order to maintain the reasonable level of security, RSA keys must have longer bit length compared to elliptic curve based crypto systems. 6.1 Comparison of Key Generation Taking into account the relatively high computing resources required to compute dis- crete logarithms, elliptic curve crypto systems allow to significantly reduce size of the encryption keys. The small key size enables faster execution of various cryptographic operations. According to the literature, it is concluded that RSA key generation takes place substantially slower than elliptic curve based crypto systems of comparable level of security [4]. The results are listed on the table below (Please see the publication for details of the experiment): Table 3. Comparison of Key Generation [4] Key Size (bits) Generation time (seconds) ECC RSA ECC RSA 163 1024 0.08 0.16 233 2240 0.18 7.47 283 3072 0.27 9.89 409 7680 0.64 133.90 571 15360 1.44 679.06 Easy to notice, the key generation of elliptic curve based crypto systems is signifi- cantly faster than RSA due to smaller key size. In addition, increasing level of security significantly increases the generation time ratio. According to the literature, to ensure sufficient protection against elliptic curve crypto system key cracking, it is required to use keys with length of at least 150 bits for temporary security solutions and 180 bits for long term security solutions [3]. To meet the equivalent level of security, RSA keys must be at length of 1024 bits for short Applications and Benefits of Elliptic Curve Cryptography 41 term solutions and 2240 bits for long term solutions. Such RSA keys are not only 6 to 9 times longer, but also their generation is 2 to 40 times slower. There is a study available that compares elliptic curve based crypto systems and RSA on implementations for 8-bit processor architectures. The authors experimentally observed that there is a fundamental relationship between the processor word length and the key length of crypto system: The relative performance of ECC over RSA increases as the word size of the processor decreases [14]. 7 Summary Despite the several decades long history of the elliptic curve cryptography, there is still a lack of research. The popular RSA crypto system is more widely studied. A significant lack of research is one of the main reasons why elliptic curve based crypto systems have showed low popularity nowadays. It is possible to conclude that the lack of research is related to the relatively complex mathematical foundation of elliptic curves and lack of interest from the systems developers. It is expected that elliptic curves will play a growing role in various implementa- tions. As mentioned, the discrete logarithm problem is algorithmically harder than the integer factorization problem, allowing a significant reduction in the public key crypto- graphic key size, thus speeding up a variety of cryptographic operations. Elliptic curve based crypto systems can be effectively used on low resources and power system solu- tions such as smart cards, mobile devices, sensors and so on. The vast majority of implementation issues of elliptic curve based crypto systems are not directly related to the fundamental security backgrounds. These issues are re- lated to the factors such as faulty software, inappropriate system components, inade- quate private key protection, usage of defective random number generators and crypto- graphic hash functions etc. Implementation options: • The most used crypto systems such as ECDH and ECDSA are standardized and patent free. They are free to use. • There are available NIST standardized elliptic curves for various security require- ments. • Free access to the extensive information on algorithms for elliptic curves based crypto systems. Benefits of elliptic curve based crypto systems versus RSA crypto system: • Key size. The key of an elliptic curve based crypto system takes significantly less memory. The ratio increases rapidly with the increase of security levels. For in- stance, RSA crypto system with the key length of 1024 bits, is equivalent to an elliptic curve crypto system with the key length of 163 bits. • Cryptographic operations performance. Thanks to the smaller size of keys, the cryp- tographic operations such as key and digital signature generation are carried out sig- nificantly faster. For instance, an elliptic curve crypto system with the key length of 233 bits corresponds to RSA crypto system with the key length of 2240 bits. In the first case the key is generated approximately 40 times faster. 42 K. Magons • Resource savings. Due to the smaller key sizes, algorithms of an elliptic curve based crypto systems can be executed on very limited resources. Disadvantages of elliptic curve based crypto systems versus RSA crypto system: • Significantly more complex mathematical backgrounds. • Relatively large group of weak elliptic curves. • Lack of research. References 1. Stinson, D.R.: Cryptography Theory And Practice. 3th edition, Chapman & Hall/CRC, New York (2006) 2. Maurer, U.M., Wolf, S.: The Diffie–Hellman Protocol. In: ”Towards a Quarter-Century of Public Key Cryptography”, Kluwer Academic Publishers, pp. 147–171, Boston (2000) 3. Koblitz, N., Menezes, A., Vanstone, S.: The State of Elliptic Curve Cryptography. In: ”Towards a Quarter-Century of Public Key Cryptography”, Kluwer Academic Publishers, pp. 173–193, Boston (2000) 4. Arrendondo, B., Jansma, N: Performance Comparison of Elliptic Curve and RSA Digital Signatures. IPCSIT vol. 4, IACSIT Press, Singapore (2011) 5. Brown, D.R.L.: SEC 1: Elliptic Curve Cryptography. Certicom Corp (2009) 6. Novotney, P.: Weak Curves In Elliptic Curve Cryptography (2010) http://ftp.mpir.org/edu/2010/414/projects/novotney.pdf 7. Schoof, R.: Elliptic Curves Over Finite Fields and the Computation of Square Roots. Mathe- matics of Computation vol. 44, pp. 483–494 (1985) 8. Corbellini, A: Elliptic Curve Cryptography: Elliptic Curve Cryptography: finite fields and discrete logarithms (2015) http://andrea.corbellini.name/2015/05/23/ elliptic-curve-cryptography-finite-fields-and-discrete-logarithms 9. Robinson, J.S.D.: An Introduction to Abstract Algebra. Walter de Gruyer GmbH & Co (2003) 10. Odlyzko, A.: Discrete logarithms: The past and the future. In: ”Towards a Quarter-Century of Public Key Cryptography”, Kluwer Academic Publishers, pp. 129–145, Boston (2000) 11. Silverman, H.S.: An Introduction to the Theory of Elliptic Curves. University of Wyoming (2006) 12. Corbellini, A.: Elliptic Curve Cryptography: ECDH and ECDSA (2015) http://andrea. corbellini.corbellini.name/2015/05/30/elliptic-curve-cryptography- ecdh-and-ecdsa/ 13. Bos, J.W., Halderman, J.A., Heninger, N., Moore, J., Naehrig, M., Wustrow, E.: Elliptic Curve Cryptography in Practice (2014) https://eprint.iacr.org/2013/734.pdf 14. Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.C.: Comparing Elliptic Curve Crypto- graphy and RSA on 8-bit CPUs. LNCS, vol. 3156, pp. 119–132. Springer, Heidelberg (2004) 15. Brown, M., Hankerson, D., Lopez, J., Menezes, A.: Software Implementation of the NIST Elliptic Curves Over Prime Fields LNCS, vol. 2020, pp. 250–265. Springer, Heidelberg (2001) 16. Schaefer, E.: An introduction to cryptography and cryptanalysis (2011) http://math.scu.edu/\textasciitildeeschaefe/book.pdf