BS ISO IEC 15946-5-2017 Information technology Security techniques Cryptographic techniques based on elliptic curves Elliptic curve generation《信息技术 安全技术 基于椭圆曲线的密码技术 椭圆曲线类生成》.pdf

1、Information technology Security techniques Cryptographic techniques based on elliptic curvesPart 5: Elliptic curve generationBS ISO/IEC 159465:2017BSI Standards PublicationWB11885_BSI_StandardCovs_2013_AW.indd 1 15/05/2013 15:06Information technology Security techniques Cryptographic techniques base

2、d on elliptic curves Part 5: Elliptic curve generationTechnologies de linformation Techniques de scurit Techniques cryptographiques fondes sur les courbes elliptiques Partie 5: Gnration de courbes elliptiquesINTERNATIONAL STANDARDISO/IEC15946-5Reference numberISO/IEC 15946-5:2017(E)Second edition201

3、7-08 ISO/IEC 2017National forewordThis British Standard is the UK implementation of ISO/IEC 159465:2017. It supersedes BS ISO/IEC 159465:2009, which is withdrawn.The UK participation in its preparation was entrusted to Technical Committee IST/33/2, Cryptography and Security Mechanisms.A list of orga

4、nizations represented on this committee can be obtained on request to its secretary.This publication does not purport to include all the necessary provisions of a contract. Users are responsible for its correct application. The British Standards Institution 2017 Published by BSI Standards Limited 20

5、17ISBN 978 0 580 92922 9ICS 35.040; 35.030Compliance with a British Standard cannot confer immunity from legal obligations. This British Standard was published under the authority of the Standards Policy and Strategy Committee on 30 September 2017.Amendments/corrigenda issued since publicationDate T

6、ext affectedBRITISH STANDARDBS ISO/IEC 159465:2017Information technology Security techniques Cryptographic techniques based on elliptic curves Part 5: Elliptic curve generationTechnologies de linformation Techniques de scurit Techniques cryptographiques fondes sur les courbes elliptiques Partie 5: G

7、nration de courbes elliptiquesINTERNATIONAL STANDARDISO/IEC15946-5Reference numberISO/IEC 15946-5:2017(E)Second edition2017-08 ISO/IEC 2017BS ISO/IEC 159465:2017ii ISO/IEC 2017 All rights reservedCOPYRIGHT PROTECTED DOCUMENT ISO/IEC 2017, Published in SwitzerlandAll rights reserved. Unless otherwise

8、 specified, no part of this publication may be reproduced or utilized otherwise in any form or by any means, electronic or mechanical, including photocopying, or posting on the internet or an intranet, without prior written permission. Permission can be requested from either ISO at the address below

9、 or ISOs member body in the country of the requester.ISO copyright officeCh. de Blandonnet 8 CP 401CH-1214 Vernier, Geneva, SwitzerlandTel. +41 22 749 01 11Fax +41 22 749 09 47copyrightiso.orgwww.iso.orgISO/IEC 15946-5:2017(E)BS ISO/IEC 159465:2017ii ISO/IEC 2017 All rights reservedCOPYRIGHT PROTECT

10、ED DOCUMENT ISO/IEC 2017, Published in SwitzerlandAll rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized otherwise in any form or by any means, electronic or mechanical, including photocopying, or posting on the internet or an intranet, without pri

11、or written permission. Permission can be requested from either ISO at the address below or ISOs member body in the country of the requester.ISO copyright officeCh. de Blandonnet 8 CP 401CH-1214 Vernier, Geneva, SwitzerlandTel. +41 22 749 01 11Fax +41 22 749 09 47copyrightiso.orgwww.iso.orgISO/IEC 15

12、946-5:2017(E)ISO/IEC 15946-5:2017(E)Foreword ivIntroduction v1 Scope . 12 Normative references 13 Terms and definitions . 14 Symbols and conversion functions 24.1 Symbols . 24.2 Conversion functions . 35 Framework for elliptic curve generation 35.1 Types of trusted elliptic curve . 35.2 Overview of

13、elliptic curve generation . 36 Verifiably pseudo-random elliptic curve generation . 46.1 General . 46.2 Constructing verifiably pseudo-random elliptic curves (prime case) 46.2.1 Construction algorithm 46.2.2 Test for near primality 56.2.3 Finding a point of large prime order 56.2.4 Verification of e

14、lliptic curve pseudo-randomness 66.3 Constructing verifiably pseudo-random elliptic curves (binary case) . 76.3.1 Construction algorithm 76.3.2 Verification of elliptic curve pseudo-randomness 87 Constructing elliptic curves by complex multiplication 87.1 General construction (prime case) 87.2 Miyaj

15、i-Nakabayashi-Takano (MNT) curve . 97.3 Barreto-Naehrig (BN) curve . 107.4 Freeman curve (F curve) . 117.5 Cocks-Pinch (CP) curve . 138 Constructing elliptic curves by lifting 13Annex A (informative) Background information on elliptic curves 15Annex B (informative) Background information on elliptic

16、 curve cryptosystems 17Annex C (informative) Numerical examples 20Annex D (informative) Summary of properties of elliptic curves generated by the complex multiplication method .28Bibliography .29 ISO/IEC 2017 All rights reserved iiiContents PageBS ISO/IEC 159465:2017ISO/IEC 15946-5:2017(E)ForewordIS

17、O (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 participate in the development of International Standards through technical committ

18、ees 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, governmental and non-governmental, in liaison with ISO and IEC, also take part in the wor

19、k. In the field of information technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1.The procedures used to develop this document and those intended for its further maintenance are described in the ISO/IEC Directives, Part 1. In particular the different approval criteri

20、a needed for the different types of document should be noted. This document was drafted in accordance with the editorial rules of the ISO/IEC Directives, Part 2 (see www .iso .org/ directives).Attention is drawn to the possibility that some of the elements of this document may be the subject of pate

21、nt rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights. Details of any patent rights identified during the development of the document will be in the Introduction and/or on the ISO list of patent declarations received (see www .iso .org/ patents).Any trade

22、 name used in this document is information given for the convenience of users and does not constitute an endorsement.For an explanation on the voluntary nature of standards, the meaning of ISO specific terms and expressions related to conformity assessment, as well as information about ISOs adherenc

23、e to the World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT) see the following URL: www .iso .org/ iso/ foreword .html.This document was prepared by Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 27, IT Security techniques.This second editio

24、n cancels and replaces the first edition (ISO/IEC 15946-5:2009), which has been technically revised.It also incorporates the Technical Corrigendum ISO/IEC 15946-5:2009/Cor.1:2012.The main technical changes between the first edition and this second edition are as follows: the terms and definitions gi

25、ven in ISO/IEC 15946-1 are used; the scope of verifiably pseudo-random elliptic curve generation has been added; the numerical examples in C.4.2 and C.4.3 have been modified.A list of all parts in the ISO/IEC 15946 series can be found on the ISO website.iv ISO/IEC 2017 All rights reservedBS ISO/IEC

26、159465:2017ISO/IEC 15946-5:2017(E)ForewordISO (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 participate in the development of Inter

27、national 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, governmental and non-governmental, in liaison

28、 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.The procedures used to develop this document and those intended for its further maintenance are described in the ISO/IEC Directives, Part 1.

29、In particular the different approval criteria needed for the different types of document should be noted. This document was drafted in accordance with the editorial rules of the ISO/IEC Directives, Part 2 (see www .iso .org/ directives).Attention is drawn to the possibility that some of the elements

30、 of this document may be the subject of patent rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights. Details of any patent rights identified during the development of the document will be in the Introduction and/or on the ISO list of patent declarations rec

31、eived (see www .iso .org/ patents).Any trade name used in this document is information given for the convenience of users and does not constitute an endorsement.For an explanation on the voluntary nature of standards, the meaning of ISO specific terms and expressions related to conformity assessment

32、, as well as information about ISOs adherence to the World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT) see the following URL: www .iso .org/ iso/ foreword .html.This document was prepared by Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 2

33、7, IT Security techniques.This second edition cancels and replaces the first edition (ISO/IEC 15946-5:2009), which has been technically revised.It also incorporates the Technical Corrigendum ISO/IEC 15946-5:2009/Cor.1:2012.The main technical changes between the first edition and this second edition

34、are as follows: the terms and definitions given in ISO/IEC 15946-1 are used; the scope of verifiably pseudo-random elliptic curve generation has been added; the numerical examples in C.4.2 and C.4.3 have been modified.A list of all parts in the ISO/IEC 15946 series can be found on the ISO website.iv

35、 ISO/IEC 2017 All rights reserved ISO/IEC 15946-5:2017(E)IntroductionSome of the most interesting alternatives to the RSA and F(p) based systems are cryptosystems based on elliptic curves defined over finite fields. The concept of an elliptic curve based public-key cryptosystem is rather simple. Eve

36、ry elliptic curve over a finite field is endowed with an addition operation “+”, under which it forms a finite abelian group. The group law on elliptic curves extends in a natural way to a “discrete exponentiation” on the point group of the elliptic curve. Based on the discrete exponentiation on an

37、elliptic curve, one can easily derive elliptic curve analogues of the well-known public-key schemes of Diffie-Hellman and ElGamal type.The security of such a public-key system depends on the difficulty of determining discrete logarithms in the group of points of an elliptic curve. This problem is, w

38、ith current knowledge, much harder than the factorization of integers or the computation of discrete logarithms in a finite field. Indeed, since Miller and Koblitz independently suggested the use of elliptic curves for public-key cryptographic systems in 1985, the elliptic curve discrete logarithm p

39、roblem has only been shown to be solvable in certain specific and easily recognizable cases. There has been no substantial progress in finding an efficient method for solving the elliptic curve discrete logarithm problem on arbitrary elliptic curves. Thus, it is possible for elliptic curve based pub

40、lic-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 a finite field. This yields significantly shorter digital signatures and system parameters.This document describes elliptic curve generati

41、on techniques useful for implementing the elliptic curve based mechanisms defined in ISO/IEC 29192-4, ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3, and ISO/IEC 18033-2.It is the purpose of this document to meet the increasing interest in elliptic curve based public-key technology by describing e

42、lliptic curve generation methods to support key-exchange, key-transport and digital signatures based on an elliptic curve. ISO/IEC 2017 All rights reserved vBS ISO/IEC 159465:2017Information technology Security techniques Cryptographic techniques based on elliptic curves Part 5: Elliptic curve gener

43、ation1 ScopeThe ISO/IEC 15946 series specifies public-key cryptographic techniques based on elliptic curves described in ISO/IEC 15946-1.This document defines elliptic curve generation techniques useful for implementing the elliptic curve based mechanisms defined in ISO/IEC 29192-4, ISO/IEC 9796-3,

44、ISO/IEC 11770-3, ISO/IEC 14888-3 and ISO/IEC 18033-2.This document is applicable to cryptographic techniques based on elliptic curves defined over finite fields of prime power order (including the special cases of prime order and characteristic two). This document is not applicable to the representa

45、tion of elements of the underlying finite field (i.e. which basis is used).The ISO/IEC 15946 series does not specify the implementation of the techniques it defines. Interoperability of products complying with the ISO/IEC 15946 series will not be guaranteed.2 Normative referencesThe following docume

46、nts are referred to in the text in such a way that some or all of their content constitutes requirements of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies.ISO/IEC 15946-1, I

47、nformation technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General3 Terms and definitionsFor the purposes of this document, the terms and definitions given in ISO/IEC 15946-1 and the following apply.ISO and IEC maintain terminological databases for use in sta

48、ndardization at the following addresses: IEC Electropedia: available at h t t p :/ www .electropedia .org/ ISO Online browsing platform: available at h t t p :/ www .iso .org/ obp3.1definition field of an elliptic curvefield that includes all the coefficients of the formula describing an elliptic cu

49、rve3.2hash-functionfunction which maps strings of bits of variable (but usually upper bounded) length to fixed-length strings of bits, satisfying the following two properties: for a given output, it is computationally infeasible to find an input which maps to this output;INTERNATIONAL STANDARD ISO/IEC 15946-5:2017(E) ISO/IEC 2017 All rights reserved 1BS ISO/IEC 159465:2017Information technology Security techniques Cryptographic techniques based on elliptic curves Part 5: Ellip