07-30135624-DC.pdf

Draft for Public Comment Head Office 389 Chiswick High Road London W4 4AL Telephone: +44(0)20 8996 9000 Fax: +44(0)20 8996 7001 Form 36 Version 6.1 DPC: 07/30135624 DC Date: 8 January 2007 Origin: International Latest date for receipt of comments: 20 April 2007 Project no.: 2005/01632 Responsible committee: IST/33 IT - Security techniques Interested committees: Title: Draft ISO/IEC 15946-1(REV) Cryptographic techniques based on elliptic curves Part 1: General Supersession information: If this document is published as a standard, the UK implementation of it will supersede BSISO/IEC15946-1 : 2002 and partially supersede NONE . If you are aware of a current national standard which may be affected, please notify the secretary (contact details below). WARNING: THIS IS A DRAFT AND MUST NOT BE REGARDED OR USED AS A BRITISH STANDARD. THIS DRAFT IS NOT CURRENT BEYOND 30 April 2007. This draft is issued to allow comments from interested parties; all comments will be given consideration prior to publication. No acknowledgement will normally be sent. See overleaf for information on commenting. No copying is allowed, in any form, without prior written permission from BSI except as permitted under the Copyright, Designs and Patent Act 1988 or for circulation within a nominating organization for briefing purposes. Electronic circulation is limited to dissemination by e-mail within such an organization by committee members. Further copies of this draft may be purchased from BSI Customer Services, Tel: +44(0) 20 8996 9001 or email ordersbsi-global.com. British, International and foreign standards are also available from BSI Customer Services. British Standards on CD or Online are available from British Standards Publishing Sales Limited. Tel: 01344 404409 or email bsonlinetechindex.co.uk. Information on the co-operating organizations represented on the committees referenced above may be obtained from the responsible committee secretary. Cross-references The British Standards which implement International or European publications referred to in this draft may be found via the British Standards Online Service on the BSI web site http:/www.bsi-global.com. Direct tel: 020 8996 7424 Responsible Committee Secretary: Mr P Restell (BSI) E-mail: peter.restellbsi-global.com a Licensed Copy: London South Bank University, London South Bank University, Thu Jan 18 01:09:45 GMT+00:00 2007, Uncontrolled Copy, (c) BSI Introduction This draft standard is based on international discussions in which the UK has taken an active part. Your comments on this draft are welcome and will assist in the preparation of the consequent standard. If no comments are received to the contrary, then the UK will approve this draft. There is a high probability that this text could be adopted by CENELEC as a reference document for harmonization or as a European Standard. Recipients of this draft are requested to comment on the text bearing in mind this possibility. UK Vote Please indicate whether you consider the UK should submit a negative (with reasons) or positive vote on this draft. BSI Committee Responsibilities Whether or not the standard is published in its original (international) form, or as a formal British Standard Implementation, the BSI committee's responsibilities are to: - aid enquirers to understand the text; - present to the responsible international committee any enquiries on interpretation, or proposals for change, and keep UK interests informed; - monitor related International and European developments and promulgate them in the UK. Submission The guidance given below is intended to ensure that all comments receive efficient and appropriate attention by the responsible BSI committee. Annotated drafts are not acceptable and will be rejected. All comments must be submitted, preferably electronically, to the Responsible Committee Secretary at the address given on the front cover. Comments should be compatible with Version 6.0 or Version 97 of Microsoft® Word for Windows, if possible; otherwise comments in ASCII text format are acceptable. Any comments not submitted electronically should still adhere to these format requirements. All comments submitted should be presented as given in the example below. Further information on submitting comments and how to obtain a blank electronic version of a comment form are available from the BSI web site at:http:/www.bsi-global.com/British_Standards/Getting_involved/DPCs/instructions.xalter Template for comments and secretariat observationsDate: xx/xx/200x Document: ISO/DIS xxxxx 1 2 (3) 4 5 (6) (7) MB Clause No./ Subclause No./ Annex (e.g. 3.1) Paragraph/ Figure/Table/ Note (e.g. Table 1) Type of com- ment Comment (justification for change) by the MB Proposed change by the MB Secretariat observations on each comment submitted 3.1 Definition 1 ed Definition is ambiguous and needs clarifying. Amend to read . so that the mains connector to which no connection . 6.4 Paragraph 2 te The use of the UV photometer as an alternative cannot be supported as serious problems have been encountered in its use in the UK. Delete reference to UV photometer. Microsoft and MS-DOS are registered trademarks, and Windows is a trademark of Microsoft Corporation. b Licensed Copy: London South Bank University, London South Bank University, Thu Jan 18 01:09:45 GMT+00:00 2007, Uncontrolled Copy, (c) BSI © ISO/IEC 2002 All rights reserved Document type: International Standard Document subtype: Document stage: (60) Publication Document language: E Lss2-is38lablunaUserkumiko-uISO15946-1CD15946-1-7.doc STD Version 2.0jd1 ISO/IEC JTC 1/SC 27 Date: 2006-12-27 ISO/IEC FCD 15946-1 ISO/IEC JTC 1/SC 27 Secretariat: DIN Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General Technologies de I'information Techniques de sécurité Techniques cryptographiques basées sur les courbes elliptiques Partie 1: Généralités Licensed Copy: London South Bank University, London South Bank University, Thu Jan 18 01:09:45 GMT+00:00 2007, Uncontrolled Copy, (c) BSI ISO/IEC FCD 15946-1 ii © ISO/IEC 2002 All rights reserved Copyright notice This ISO document is a Draft International Standard and is copyright-protected by ISO. Except as permitted under the applicable laws of the user's country, neither this ISO draft nor any extract from it may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, photocopying, recording or otherwise, without prior written permission being secured. Requests for permission to reproduce should be addressed to either ISO at the address below or ISO's member body in the country of the requester. ISO copyright office Case postal 56 CH-1211 Geneva 20 Tel. + 41 22 749 01 11 Fax + 41 22 749 09 47 E-mail copyrightiso.ch Web www.iso.ch Reproduction may be subject to royalty payments or a licensing agreement. Violators may be prosecuted. Licensed Copy: London South Bank University, London South Bank University, Thu Jan 18 01:09:45 GMT+00:00 2007, Uncontrolled Copy, (c) BSI ISO/IEC FCD 15946-1 © ISO/IEC 2002 All rights reserved iii Contents Page 1 Scope1 2 Normative reference(s) .1 3 Terms and definitions .1 3.1 Elliptic curve 1 3.2 Finite fields.1 3.3 Cryptographic bilinear map2 4 Symbols (and abbreviated terms)2 5 Conventions of fields3 5.1 Finite prime fields F(p) 3 5.2 Finite fields F(pm) .3 6 Conventions of elliptic curves .4 6.1 Definition of elliptic curves.4 6.1.1 Elliptic curves over F(pm) .4 6.1.2 Elliptic curves over F(2m) .4 6.1.3 Elliptic curves over F(3m) .4 6.2 The group law on elliptic curves5 6.3 Cryptographic bilinear map5 7 Conversion functions5 7.1 Octet string / bit string conversion: OS2BSP and BS2OSP 5 7.2 Bit string / integer conversion: BS2IP and I2BSP.6 7.3 Octet string / integer conversion: OS2IP and I2OSP6 7.4 Finite field element / integer conversion: FE2IPF.6 7.5 Octet string / finite field element conversion: OS2FEPF and FE2OSPF.6 7.6 Elliptic curve point / octet string conversion: EC2OSPE and OS2ECPE7 7.6.1 Compressed elliptic curve points.7 7.6.2 Point decompression algorithms7 7.6.3 Conversion functions.7 7.7 Integer / elliptic curve conversion: I2ECP.8 8 Elliptic curve domain parameters and public key8 8.1 Elliptic curve domain parameters over F(q)8 8.2 Elliptic curve key generation9 Annex A (informative) Background Information on finite fields.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 curves .12 B.2 The group law for elliptic curves E over F(q) with p 3 12 B.2.1 Overview of coordinates12 B.2.2 The group law in affine coordinates.12 B.2.3 The group law in projective coordinates .13 B.2.4 The group law in Jacobian coordinates.14 B.2.5 The group law in modified Jacobian coordinates.15 B.2.6 Mixed coordinates15 B.3 The group law for elliptic curves over F(2m).16 B.3.1 The group law in affine coordinates.16 B.3.2 The group law in projective coordinates .16 B.4 The group law for elliptic curves over F(3m).17 B.4.1 The group law in affine coordinates.17 B.4.2 The group law in projective coordinates .18 B.5 The existence condition of an elliptic curve E .19 B.5.1 The order of an elliptic curve E defined over F(p).19 B.5.2 The order of an elliptic curve E defined over F(2m).19 Licensed Copy: London South Bank University, London South Bank University, Thu Jan 18 01:09:45 GMT+00:00 2007, Uncontrolled Copy, (c) BSI ISO/IEC FCD 15946-1 iv © ISO/IEC 2002 All rights reserved B.5.3 The order of an elliptic curve E defined over F(pm) with p 319 B.6 The pairings.20 B.6.1 The overview of pairings20 B.6.2 The definitions of Weil and Tate pairings 20 B.6.3 The cryptographic bilinear map20 Annex C (Informative) Background Information on elliptic curve cryptosystems.21 C.1 Definition of cryptographic problems .21 C.1.1 The elliptic curve discrete logarithm problem (ECDLP).21 C.1.2 The elliptic curve computational Diffie Hellman problem (ECDHP)21 C.1.3 The elliptic curve decisional Diffie Hellman problem (ECDDHP) 21 C.1.4 The bilinear Diffie-Hellman (BDH) problem21 C.2 Algorithms to determine discrete logarithms on elliptic curves21 C.2.1 Security of ECDLP21 C.2.2 Overview of algorithms22 C.2.3 The MOV condition.22 C.3 Scalar multiplication algorithms of elliptic curve points.22 C.3.1 Basic algorithm.22 C.3.2 Algorithm with pre-computed table23 C.4 Algorithms to compute pairings 24 C.4.1 The auxiliary functions.24 C.4.2 Algorithm to compute the Weil pairing 25 C.4.3 Algorithm to compute the Tate pairing 25 C.5 Elliptic curve domain parameters and public key validation (optional).25 C.5.1 Elliptic curve domain parameter validation over F(q).26 C.5.2 Public Key Validation (Optional).26 Annex D (Informative) 28 Bibliography29 Licensed Copy: London South Bank University, London South Bank University, Thu Jan 18 01:09:45 GMT+00:00 2007, Uncontrolled Copy, (c) BSI ISO/IEC FCD 15946-1 © ISO/IEC 2002 All rights reserved v Foreword 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 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, governmental 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, Part 3. 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 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. ISO/IEC 15946 consists of the following parts, under the general title Information technology Security techniques - Cryptographic techniques based on elliptic curves: Part 1: General Part 2: Digital signatures Part 3: Key establishment Part 4: Digital signatures giving message recovery Part 5: Elliptic curve generation Annexes A, B, C, and D of this part of ISO/IEC 15946 are for information only. Licensed Copy: London South Bank University, London South Bank University, Thu Jan 18 01:09:45 GMT+00:00 2007, Uncontrolled Copy, (c) BSI ISO/IEC FCD 15946-1 vi © ISO/IEC 2002 All rights reserved Introduction One of the most interesting alternatives to the RSA and GF(p) based cryptosystems that are currently available are cryptosystems based on elliptic curves defined over finite fields. The concept of an elliptic curve based public key cryptosystem is rather simple: Every elliptic curve over a finite field is endowed with an addition “+“ 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 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 - 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 suggested 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 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 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/IEC 15946. It is the purpose of this document to meet the in