# cctv电竞直播网: P.H. ROBERTS and R.N. ZOBEL A DISCUSSION OF ELLIPCTIC CURVE A DISCUSSION OF ELLIPTIC CURVE

P.H. ROBERTS and R.N. ZOBEL: A DISCUSSION OF ELLIPCTIC CURVE I.J. of SIMULATION Vol. 5 No 1-2 ISSN 1473-804x online, 1473-8031 print 47 A DISCUSSION OF ELLIPTIC CURVE CRYPTOGRAPHY AND CONFIGURABLE ECC SYSTEM DESIGN WITH APPLICATION TO DISTRIBUTED SIMULATION P.H. ROBERTS and R.N. ZOBEL Department of Computer Science University of Manchester Oxford Road Manchester M13 9PL Abstract: Distributed simulation, outside of the military area, necessarily operates over the internet, which implies the risk of many forms of attack. Current security systems offer limited protection because of the cost and complexity of using sufficient key lengths in existing public key encryption schemes. The use of the Discrete Logarithm Problem over elliptic curves defined over finite fields as a basis for trap-door based public key encryption (ECC) appears to offer improved performance with lower cost in terms of processor speed, memory requirement and processing time. This paper provides an outline of ECC and the complexities of a practical implementation of the technology. Some issues regarding choice of EC parameters, security, interoperability and performance are discussed. A proposal is made for a configurable ECC system architecture and the high-level design of a toolkit to enable the development of ECC systems is discussed. ECC cryptographic systems may be considered particularly suitable for supporting distributed interactive simulation, with its stringent timing requirements and particular security problems, with additional reference to mobile systems. Keywords: Cryptography, Elliptic Curve, Distributed Simulation, ECC, System Architecture, Authentication 1. INTRODUCTION Increasingly, distributed simulation is required for a variety of reasons, such as models running under differing operating systems, clock speeds or simulation environments, or for reasons of commercial, government or military secrecy. For cost reasons, many of these systems now have to use the internet to carry their intercommunication traffic. Consequently, the risk of lost or modified data, loss of secrecy and interference with simulation studies, makes it imperative to use some form of encryption. Further, it is necessary to provide adequate authentication facilities for all intended participants in a shared distributed simulation environment. 1.1 Attacks There are many forms of attack. Passive attacks concern listening, observing and collecting information. Active attacks include masquerade, replay, modification, and denial of service. Of these the last is the most dangerous, since the others can be defended against by using authentication and encryption techniques. Denial of service and worse still, distributed denial of service, can be targeted or undirected random attacks, but are less likely to be targeted if it is difficult to identify who are the participants in a distributed simulation exercise and where on the network they are. 1.2 Security services There are several important aspects of security which directly impact on the use of authentication and encryption for distributed simulation. They relate to maintaining privacy, strictly protecting data and messages, and system integrity during the set- up, simulation and post simulation analysis. Further, sophisticated authentication procedures ensure that only bona fide participants are permitted to join a federation, whether active in simulations or just as observers. 1.2.1 Confidentiality This concerns providing protection against passive attacks, such as acquisition of data by copying and traffic analysis for operational analysis. Encryption is often used to provide protection against such attacks. However, this may not give a complete guarantee of protection in respect of some currently employed encryption schemes. P.H. ROBERTS and R.N. ZOBEL: A DISCUSSION OF ELLIPCTIC CURVE I.J. of SIMULATION Vol. 5 No 1-2 ISSN 1473-804x online, 1473-8031 print 48 1.2.2 Integrity Maintaining system integrity is, at a lower level, concerned with ensuring that the contents of a message have not been changed. Full integrity concerns the entire message stream making up a communication, ensuring that no messages or parts of messages have disappeared, have been replayed and that no additional messages or parts thereof have been inserted by active attacks. 1.2.3 Authentication Masquerade attacks occur when unauthorized participants assume the identity of those who are authorized. Authentication concerns ensuring that, at all times, the authorized principals are in fact who they claim to be. 1.2.4 Non-repudiation This is not necessarily of particular interest to simulationists, but ensures that once a party has sent a communication, they are not able to deny having sent it, and that the receiving party can prove that the original party did indeed send the message. 1.2.5 Symmetric/Asymmetric key encryption Discussed in detail later, this concerns the use of symmetric, shared encryption/decryption key, schemes with their associated problems of key distribution and management, and asymmetric, public key, systems. 1.2.6 Current limitations and susceptibility The use of authentication and encryption for distributed simulation, and other related real-time activities, is limited by the additional time delay imposed by message construction, interchange and message encryption/decryption at each end of each interaction pair. With the use of real equipment and personnel the issue of mobile simulation arises and brings up the general issue of the use of mobile computing devices. First there is the issue of the physical security of small portable digital devices such as mobile phones, PDAs and smart cards. They are easily lost or stolen. Then there are the limited resources of such devices which limit the complexity and degree of security currently possible. For example processor power and memory size constrain the complexity of encryption/decryption algorithms. Additionally, there is limited bandwidth available in wireless networks resulting in transmission speed restrictions. Finally, there is the basic problem of the insecure nature of the radio medium, since it is a broadcast medium which may be received, decrypted, decoded and interpreted by any person with a suitable receiver. 2. ENCRYPTION Many methods have been used over the centuries with varying degrees of success. However, with the advent of computers, life has become easier for the attacker. Cryptanalysis has become a sophisticated topic, available to security professionals, criminals and hackers alike. Consequently, existing systems are under threat of serious attack. Unconditional security is not a reality. Realistic conditions for computational security might be that the cost of breaking the cipher is more than the value of the encrypted data, and the time to break the cipher is longer than the useful lifetime of the encrypted data [Stallings W. 1995]. The latter condition can, in principle, be obviated by the use of time stamps. The first condition is less easy to achieve, because of novel backdoor approaches and clever mathematicians. 2.1 Classical or Symmetric Encryption This usually involves three players. Two are the communicants (the principals) and the third is the attacker. The communicants use a publicly known encryption scheme and share a secret key. The important concepts are that the same secret key is used for both encryption and decryption, and usually, the decryption algorithm is simply the inverse of the encryption algorithm. Although potentially very efficient, there are three main problems with such schemes. The first is key distribution, which must be in itself secure; the second is key management, where the number of keys required in a system with a large number of principals does not scale well, as can be clearly seen in figure 1. Figure 1: Number of keys required for symmetric encryption system This can be a major problem for distributed simulation with a large number of players. Thirdly, symmetric key cryptographic systems suffer from a lack of provision for strong authentication, digital signatures and non-repudiation services. These problems can be solved through the use of Public Key encryption schemes, for a full discussion see [Stalling W. 1999]. 0 1000 2000 3000 4000 5000 6000 0 20 40 60 80 100 No. of principals in system No. of secret keys require d P.H. ROBERTS and R.N. ZOBEL: A DISCUSSION OF ELLIPCTIC CURVE I.J. of SIMULATION Vol. 5 No 1-2 ISSN 1473-804x online, 1473-8031 print 49 2.2 Public Key or Asymmetric Encryption Public Key Cryptosystems, first proposed theoretically by Diffie and Helman [Diffie et al, 1976], employ asymmetric key pairs, where each user has an individual key pair consisting of a publicly available encryption key, and a corresponding private decryption key. It should be computationally infeasible to compute the private key from knowledge of the corresponding public key and encryption algorithm, or from examples of encrypted and decrypted message pairs. The consequence of this is the need to find so called trap- door one-way functions (TOFs) which fulfill these criteria. A trap door is easy to open from the inside, but difficult from the outside without the key. 2.2.1 Public Key Cryptographic Services Numerous different schemes, based on asymmetric key pairs, have been suggested to achieve the security services outlined in section 1 since Diffie and Helman’s paper. There are three main classes of scheme, ? Digital signature schemes ? Encryption schemes ? Key Exchange schemes The above three schemes are used as the building blocks of current network security systems. 2.3 The RSA Scheme The RSA scheme [Rivest. et al, 1978], along with the Digital Signature Algorithm (DSA) and Diffie- Helman Key Exchange schemes are the most widely used and commercially accepted Public Key systems using the product of large prime integers as the basis of a family of TOFs. Their security is based on the difficulty of factoring large integers. However to provide adequate security it is currently necessary to use keys with at least 1024 bits, with encryption and decryption operations orders of magnitude slower than conventional symmetric cryptosystems. Thus their practical use in distributed simulation is limited. Additionally due to recent improvements in factoring algorithms the security per key bit provided by these schemes has been reduced. This means that as computer hardware power continues to increase, prohibitively large key sizes will become necessary to maintain current security levels. 3. ELLIPTIC CURVE CRYPTOGRAPHY (ECC) 3.1 Introduction and Motivation Koblitz [Koblitz, N. 1987] and Miller [Miller, V. 1986] proposed the use of the discrete logarithm problem over a group of elliptic curve points, known as the ECDLP, as a basis for public key cryptographic schemes, as the difficulty of computing the ECDLP is much harder than factoring integers. Therefore the security offered per key bit by such schemes is greater and such schemes require smaller key sizes to provide comparable levels of security. Such schemes will also be more resilient to future improvements in computer hardware, assuming no significant improvements in the efficiency of algorithms for solving the ECDLP. Given that these schemes have now been under investigation for over 15 years such a dramatic breakthrough seems unlikely. A comparison of the key sizes required by ECC, Integer factorization (RSA) and traditional symmetric schemes is shown in table 1, adapted from [SEC 1, 2000]. Symmetric scheme ECDLP based scheme Integer factorisation based scheme 56 112 512 80 160 1024 112 224 2048 128 256 3078 192 384 7680 256 512 15360 Table 1: Comparison of key sizes Smaller key sizes are beneficial in systems where keys must be transported across networks and stored on devices with limited memory. Additionally, smaller key sizes may result in faster execution timings for the schemes, which is beneficial to systems where real time performance is a critical fasctor. 3.2 Mathematical background ECC schemes are based on the scalar multiplication of elliptic curve points and the computational intractability of the inverse operation, the Elliptic Curve Discrete Logarithm Problem (ECDLP). 3.2.1 Elliptic Curves An elliptic curve E(F), is the set of solutions, or points, which satisfy a Weierstrass equation, given by: y2z+a1xyz+a2yz2 = x3+a3x2z+a4xz2+a5z3 Where, ai and the coordinates of each point are elements in a field F. For a full mathematical description see [Menezes, A. 1993]. P.H. ROBERTS and R.N. ZOBEL: A DISCUSSION OF ELLIPCTIC CURVE I.J. of SIMULATION Vol. 5 No 1-2 ISSN 1473-804x online, 1473-8031 print 50 3.2.2 Finite Fields For a full introduction to the theory of fields and finite fields, see [Koblitz, N. 1987]. Two types of field are suitable for ECC, namely, characteristic two finite extension fields, where the Weierstrass equation can be simplified to, y2 + xy = x3 + ax2 + b and large prime characteristic finite fields, where the short Weierstrass form defines the curve, y2 = x3 + ax + b In both cases the field chosen can be defined by its order, denoted q, and the chosen curve defined by the parameters a and b to the simplified Weierstrass equation. 3.2.3 Operations required by ECC The scalar multiplication, or repeated addition, of EC points is the main operation required by ECC schemes, although other operations such as division may also be needed. For exact long integer word length mathematical arithmetic operations implied by such encryption/decryption systems are slow and possibly unique to this application area, since all rounding schemes are automatically excluded The addition of two EC points is illustrated in figure 2 below. Figure 2: Illustration of adding two EC points. As it is the scalar multiplication operation that dominates the actual execution timing of ECC schemes, its efficient implementation is crucial. The actual mathematics depends on the chosen curve and underlying field, see [Blake, I et al. 1999], however there is a clear hierarchy of underlying mathematical operations, as shown in figure 3 below. Figure 3: Hierarchy of required underlying mathematical operations EC point compression techniques also require square root computation in the field. All the field operations require integer arithmetic, with operand lengths which may be considerably larger than typical computer word length. These low level integer arithmetic operations may be best implemented as hand coded assembler routines. Clearly, to efficiently implement ECC it is crucial to select the optimal algorithms at each level. These underlying algorithm choices depend first on the chosen curve and type of underlying finite field and then can often be optimised depending on the computing environment. Clearly in a distributed simulation environment the devices involved may h