SANS 15946-1-2009 Information technology - Security techniques - Cryptographic techniques based on elliptic curves Part 1 General《信息技术 安全技术 基于椭圆曲线的加密技术 第1部分 总则》.pdf

1、 Collection of SANS standards in electronic format (PDF) 1. Copyright This standard is available to staff members of companies that have subscribed to the complete collection of SANS standards in accordance with a formal copyright agreement. This document may reside on a CENTRAL FILE SERVER or INTRA

2、NET SYSTEM only. Unless specific permission has been granted, this document MAY NOT be sent or given to staff members from other companies or organizations. Doing so would constitute a VIOLATION of SABS copyright rules. 2. Indemnity The South African Bureau of Standards accepts no liability for any

3、damage whatsoever than may result from the use of this material or the information contain therein, irrespective of the cause and quantum thereof. ISBN 978-0-626-23722-6 SANS 15946-1:2009Edition 2 and ISO/IEC tech. corr. 1 ISO/IEC 15946-1:2008Edition 2 and tech. corr. 1SOUTH AFRICAN NATIONAL STANDAR

4、D Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General This national standard is the identical implementation of ISO/IEC 15946-1:2008 and ISO/IEC technical corrigendum 1, and is adopted with the permission of the International Organization for

5、Standardisation and the International Electrotechnical Commission. Published by SABS Standards Division 1 Dr Lategan Road Groenkloof Private Bag X191 Pretoria 0001Tel: +27 12 428 7911 Fax: +27 12 344 1568 www.sabs.co.za SABS SANS 15946-1:2009 Edition 2 and ISO/IEC tech. corr. 1 ISO/IEC 15946-1:2008

6、Edition 2 and tech. corr. 1 Table of changes Change No. Date Scope ISO/IEC tech. corr. 1 2009 Corrected to add Annex D on the contents page and a Note 2 on “elliptic curve” under definition of terms. National foreword This South African standard was approved by National Committee SABS SC 71F, Inform

7、ation technology Information security, in accordance with procedures of the SABS Standards Division, in compliance with annex 3 of the WTO/TBT agreement. This SANS document was published in December 2009 This SANS document supersedes SANS 15946-1:2009 (edition 2). ICS 35.040 Ref. No. ISO/IEC 15946-1

8、:2008/Cor.1:2009(E) ISO/IEC 2009 All rights reserved Published in Switzerland INTERNATIONAL STANDARD ISO/IEC 15946-1:2008 TECHNICAL CORRIGENDUM 1 Published 2009-02-15 INTERNATIONAL ORGANIZATION FOR STANDARDIZATION ORGANISATION INTERNATIONALE DE NORMALISATIONINTERNATIONAL ELECTROTECHNICAL COMMISSION

9、COMMISSION LECTROTECHNIQUE INTERNATIONALEInformation technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General TECHNICAL CORRIGENDUM 1 Technologies de linformation Techniques de scurit Techniques cryptographiques bases sur les courbes elliptiques Partie 1: Gnra

10、lits RECTIFICATIF TECHNIQUE 1 Technical Corrigendum 1 to ISO/IEC 15946-1:2008 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 27, IT Security techniques. Page iii, Contents Add the following entry above the entry for Bibliography: “Annex D (informativ

11、e) Summary of coordinates 28” Page 1, 2.2 Convert the existing note to NOTE 1 and add the following new note: “NOTE 2 A definition of a cubic curve is given in bibliography item 16.” Page 30, Bibliography Delete item 3. SANS 15946-1:2009This s tandard may only be used and printed by approved subscri

12、ption and freemailing clients of the SABS .This page has been left blank intentionally SANS 15946-1:2009This s tandard may only be used and printed by approved subscription and freemailing clients of the SABS .Reference numberISO/IEC 15946-1:2008(E)ISO/IEC 2008INTERNATIONAL STANDARD ISO/IEC15946-1Se

13、cond edition2008-04-15Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General Technologies de linformation Techniques de scurit Techniques cryptographiques bases sur les courbes elliptiques Partie 1: Gnralits SANS 15946-1:2009This s tandard may on

14、ly be used and printed by approved subscription and freemailing clients of the SABS .ISO/IEC 15946-1:2008(E) PDF disclaimer This PDF file may contain embedded typefaces. In accordance with Adobes licensing policy, this file may be printed or viewed but shall not be edited unless the typefaces which

15、are embedded are licensed to and installed on the computer performing the editing. In downloading this file, parties accept therein the responsibility of not infringing Adobes licensing policy. The ISO Central Secretariat accepts no liability in this area. Adobe is a trademark of Adobe Systems Incor

16、porated. Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In the unlikely event tha

17、t a problem relating to it is found, please inform the Central Secretariat at the address given below. COPYRIGHT PROTECTED DOCUMENT ISO/IEC 2008 All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means, electronic or mecha

18、nical, including photocopying and microfilm, without permission in writing from either ISO at the address below or ISOs member body in the country of the requester. ISO copyright office Case postale 56 CH-1211 Geneva 20 Tel. + 41 22 749 01 11 Fax + 41 22 749 09 47 E-mail copyrightiso.org Web www.iso

19、.org Published in Switzerland ii ISO/IEC 2008 All rights reservedSANS 15946-1:2009This s tandard may only be used and printed by approved subscription and freemailing clients of the SABS .ISO/IEC 15946-1:2008(E) ISO/IEC 2008 All rights reserved iiiContents Page Foreword iv Introduction v 1 Scope 1 2

20、 Terms and definitions1 3 Symbols 2 4 Conventions of fields 3 4.1 Finite prime fields F(p).3 4.2 Finite fields F(pm)3 5 Conventions of elliptic curves4 5.1 Definition of elliptic curves.4 5.2 The group law on elliptic curves5 5.3 Cryptographic bilinear map 5 6 Conversion functions5 6.1 Octet string

21、/ bit string conversion: OS2BSP and BS2OSP.5 6.2 Bit string / integer conversion: BS2IP and I2BSP5 6.3 Octet string / integer conversion: OS2IP and I2OSP 6 6.4 Finite field element / integer conversion: FE2IPF.6 6.5 Octet string / finite field element conversion: OS2FEPFand FE2OSPF.6 6.6 Elliptic cu

22、rve point / octet string conversion: EC2OSPEand OS2ECPE7 6.7 Integer / elliptic curve conversion: I2ECP.8 7 Elliptic curve domain parameters and public key 8 7.1 Elliptic curve domain parameters over F(q) 8 7.2 Elliptic curve key generation 9 Annex A (informative) Background information on finite fi

23、elds .10 A.1 Bit strings .10 A.2 Octet strings.10 A.3 The finite field F(q).10 Annex B (informative) Background information on elliptic curves12 B.1 Properties of elliptic curves12 B.2 The group law for elliptic curves E over F(q) with p 3.12 B.3 The group law for elliptic curves over F(2m) .16 B.4

24、The group law for elliptic curves over F(3m) .17 B.5 The existence condition of an elliptic curve E19 Annex C (informative) Background information on elliptic curve cryptosystems21 C.1 Definition of cryptographic problems21 C.2 Algorithms to determine discrete logarithms on elliptic curves.21 C.3 Sc

25、alar multiplication algorithms of elliptic curve points.22 C.4 Algorithms to compute pairings.24 C.5 Elliptic curve domain parameters and public key validation (optional).25 Bibliography 30 SANS 15946-1:2009This s tandard may only be used and printed by approved subscription and freemailing clients

26、of the SABS .ISO/IEC 15946-1:2008(E) iv ISO/IEC 2008 All rights reservedForeword ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for worldwide standardization. National bodies that are members of ISO or IEC

27、participate in the development of International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other international organizations, govern

28、mental and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1. International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Par

29、t 2. The main task of the joint technical committee is to prepare International Standards. Draft International Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as an International Standard requires approval by at least 75 % of the national

30、bodies casting a vote. ISO/IEC 15946-1 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 27, IT Security techniques. This second edition cancels and replaces the first edition (ISO/IEC 15946-1:2002), which has been technically revised. ISO/IEC 15946 con

31、sists of the following parts, under the general title Information technology Security techniques Cryptographic techniques based on elliptic curves: Part 1: General Part 3: Key establishment Elliptic curve generation will form the subject of a future Part 5. SANS 15946-1:2009This s tandard may only b

32、e used and printed by approved subscription and freemailing clients of the SABS .ISO/IEC 15946-1:2008(E) ISO/IEC 2008 All rights reserved vIntroduction One of the most interesting alternatives to the RSA and F(p) based cryptosystems that are currently available are cryptosystems based on elliptic cu

33、rves defined over finite fields. The concept of an elliptic curve based public-key cryptosystem is quite simple. Every elliptic curve over a finite field is endowed wi th an addition “+“ under which it forms a finite abelian group. The group law on elliptic curves extends in a natural way to a “disc

34、rete exponentiation“ on the point group of the elliptic curve. Based on the discrete exponentiation on an elliptic curve, one can easily derive elliptic curve analogues of the well-known public-key schemes of the DiffieHellman and ElGamal type. The security of such a public-key cryptosystem depends

35、on the difficulty of determining discrete logarithms in the group of points of an elliptic curve. This problem is, with current knowledge, much harder than the factorisation of integers or the computation of discrete logarithms in a finite field. Indeed, since Miller and Koblitz independently sugges

36、ted the use of elliptic curves for public-key cryptographic systems in 1985, the elliptic curve discrete logarithm problem has only been shown to be solvable in certain specific, and easily recognisable, cases. There has been no substantial progress in finding a method for solving the elliptic curve

37、 discrete logarithm problem on arbitrary elliptic curves. Thus, it is possible for elliptic curve based public-key systems to use much shorter parameters than the RSA system or the classical discrete logarithm based systems that make use of the multiplicative group of some finite field. This yields

38、significantly shorter digital signatures and system parameters and the integers to be handled by a cryptosystem are much smaller. This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for implementing any of the mechanisms described in other parts of ISO/I

39、EC 15946 and other ISO/IEC standards. It is the purpose of this part of ISO/IEC 15946 to meet the increasing interest in elliptic curve based public-key technology and describe the components that are necessary to implement secure elliptic curve cryptosystems such as key-exchange, key-transport and

40、digital signatures. The International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC) draw attention to the fact that it is claimed that compliance with this document may involve the use of patents. The ISO and IEC take no position concerning the evidence,

41、validity and scope of these patent rights. The holders of these patent rights have assured the ISO and IEC that they are willing to negotiate licences under reasonable and non-discriminatory terms and conditions with applicants throughout the world. In this respect, the statements of the holders of

42、these patent rights are registered with the ISO and IEC. Information may be obtained from: ISO/IEC JTC 1/SC 27 Standing Document 8 (SD 8) “Patent Information” SD 8 is publicly available at: http:/www.ni.din.de/sc27 Attention is drawn to the possibility that some of the elements of this document may

43、be the subject of patent rights other than those identified above. ISO and IEC shall not be held responsible for identifying any or all such patent rights. SANS 15946-1:2009This s tandard may only be used and printed by approved subscription and freemailing clients of the SABS .SANS 15946-1:2009This

44、 s tandard may only be used and printed by approved subscription and freemailing clients of the SABS .INTERNATIONAL STANDARD ISO/IEC 15946-1:2008(E) ISO/IEC 2008 All rights reserved 1Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General 1 Scope

45、ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. These include the establishment of keys for secret-key systems, and digital signature mechanisms. This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for implementing a

46、ny of the mechanisms described in other parts of ISO/IEC 15946 and other ISO/IEC standards. The scope of this part of ISO/IEC 15946 is restricted to cryptographic techniques based on elliptic curves defined over finite fields of prime power order (including the special cases of prime order and chara

47、cteristic two). The representation of elements of the underlying finite field when the field is not of prime order (i.e. which basis is used) is outside the scope of this part of ISO/IEC 15946. ISO/IEC 15946 does not specify the implementation of the techniques it defines. Interoperability of produc

48、ts complying with this part of ISO/IEC 15946 will not be guaranteed. 2 Terms and definitions For the purposes of this document, the following terms and definitions apply. 2.1 finite field any field containing a finite number of elements NOTE For any positive integer m and a prime p, there exists a f

49、inite field containing exactly pmelements. This field is unique up to isomorphism and is denoted by F(pm), where p is called the characteristic of F(pm). 2.2 elliptic curve any cubic curve E without any singular point NOTE The set of points of E is an abelian group. The field that includes all coefficients of the equation describing E is called the definition field of E. In this part of ISO/IEC 1