CAN CSA-ISO IEC 18032-2006 Information technology - Security techniques - Prime number generation.pdf

1、 Reference numberISO/IEC 18032:2005(E)ISO/IEC 2005INTERNATIONAL STANDARD ISO/IEC18032First edition2005-01-15Information technology Security techniques Prime number generation Technologies de linformation Techniques de scurit Gnration de nombres premiers National Standard of CanadaCAN/CSA-ISO/IEC 180

2、32:06(ISO/IEC 18032:2005)International Standard ISO/IEC 18032:2005 (first edition, 2005-01-15) has been adopted withoutmodification (IDT) as CSA Standard CAN/CSA-ISO/IEC 18032:06, which has been approved as a NationalStandard of Canada by the Standards Council of Canada.ISBN 1-55436-382-9 December 2

3、006Legal Notice for StandardsCanadian Standards Association (CSA) standards are developed through a consensus standards development process approved by the Standards Council of Canada. This process brings together volunteers representing varied viewpoints and interests to achieve consensus and devel

4、op a standard. Although CSA administers the process and establishes rules to promote fairness in achieving consensus, it does not independently test, evaluate, or verify the content of standards.Disclaimer and exclusion of liabilityThis document is provided without any representations, warranties, o

5、r conditions of any kind, express or implied, including, without limitation, implied warranties or conditions concerning this documents fitness for a particular purpose or use, its merchantability, or its non-infringement of any third partys intellectual property rights. CSA does not warrant the acc

6、uracy, completeness, or currency of any of the information published in this document. CSA makes no representations or warranties regarding this documents compliance with any applicable statute, rule, or regulation. IN NO EVENT SHALL CSA, ITS VOLUNTEERS, MEMBERS, SUBSIDIARIES, OR AFFILIATED COMPANIE

7、S, OR THEIR EMPLOYEES, DIRECTORS, OR OFFICERS, BE LIABLE FOR ANY DIRECT, INDIRECT, OR INCIDENTAL DAMAGES, INJURY, LOSS, COSTS, OR EXPENSES, HOWSOEVER CAUSED, INCLUDING BUT NOT LIMITED TO SPECIAL OR CONSEQUENTIAL DAMAGES, LOST REVENUE, BUSINESS INTERRUPTION, LOST OR DAMAGED DATA, OR ANY OTHER COMMERC

8、IAL OR ECONOMIC LOSS, WHETHER BASED IN CONTRACT, TORT (INCLUDING NEGLIGENCE), OR ANY OTHER THEORY OF LIABILITY, ARISING OUT OF OR RESULTING FROM ACCESS TO OR POSSESSION OR USE OF THIS DOCUMENT, EVEN IF CSA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES, INJURY, LOSS, COSTS, OR EXPENSES.In publi

9、shing and making this document available, CSA is not undertaking to render professional or other services for or on behalf of any person or entity or to perform any duty owed by any person or entity to another person or entity. The information in this document is directed to those who have the appro

10、priate degree of experience to use and apply its contents, and CSA accepts no responsibility whatsoever arising in any way from any and all use of or reliance on the information contained in this document. CSA is a private not-for-profit company that publishes voluntary standards and related documen

11、ts. CSA has no power, nor does it undertake, to enforce compliance with the contents of the standards or other documents it publishes. Intellectual property rights and ownershipAs between CSA and the users of this document (whether it be in printed or electronic form), CSA is the owner, or the autho

12、rized licensee, of all works contained herein that are protected by copyright, all trade-marks (except as otherwise noted to the contrary), and all inventions and trade secrets that may be contained in this document, whether or not such inventions and trade secrets are protected by patents and appli

13、cations for patents. Without limitation, the unauthorized use, modification, copying, or disclosure of this document may violate laws that protect CSAs and/or others intellectual property and may give rise to a right in CSA and/or others to seek legal redress for such use, modification, copying, or

14、disclosure. To the extent permitted by licence or by law, CSA reserves all intellectual property rights in this document.Patent rightsAttention is drawn to the possibility that some of the elements of this standard may be the subject of patent rights. CSA shall not be held responsible for identifyin

15、g any or all such patent rights. Users of this standard are expressly advised that determination of the validity of any such patent rights is entirely their own responsibility.Authorized use of this documentThis document is being provided by CSA for informational and non-commercial use only. The use

16、r of this document is authorized to do only the following:If this document is in electronic form:.load this document onto a computer for the sole purpose of reviewing it;.search and browse this document; and.print this document. Limited copies of this document in print or paper form may be distribut

17、ed only to persons who are authorized by CSA to have such copies, and only if this Legal Notice appears on each such copy.In addition, users may not and may not permit others to.alter this document in any way or remove this Legal Notice from the attached standard;.sell this document without authoriz

18、ation from CSA; or.make an electronic copy of this document.If you do not agree with any of the terms and conditions contained in this Legal Notice, you may not load or use this document or make any copies of the contents hereof, and if you do make such copies, you are required to destroy them immed

19、iately. Use of this document constitutes your acceptance of the terms and conditions of this Legal Notice.The Canadian Standards Association (CSA), under whose auspices this National Standard has been produced, was chartered in 1919 and accredited by the Standards Council of Canada to the National S

20、tandards system in 1973. It is a not-for-profit, nonstatutory, voluntary membership association engaged in standards development and certification activities. CSA standards reflect a national consensus of producers and users including manufacturers, consumers, retailers, unions and professional orga

21、nizations, and governmental agencies. The standards are used widely by industry and commerce and often adopted by municipal, provincial, and federal governments in their regulations, particularly in the fields of health, safety, building and construction, and the environment. Individuals, companies,

22、 and associations across Canada indicate their support for CSAs standards development by volunteering their time and skills to CSA Committee work and supporting the Associations objectives through sustaining memberships. The more than 7000 committee volunteers and the 2000 sustaining memberships tog

23、ether form CSAs total membership from which its Directors are chosen. Sustaining memberships represent a major source of income for CSAs standards development activities. The Association offers certification and testing services in support of and as an extension to its standards development activiti

24、es. To ensure the integrity of its certification process, the Association regularly and continually audits and inspects products that bear the CSA Mark. In addition to its head office and laboratory complex in Toronto, CSA has regional branch offices in major centres across Canada and inspection and

25、 testing agencies in eight countries. Since 1919, the Association has developed the necessary expertise to meet its corporate mission: CSA is an independent service organization whose mission is to provide an open and effective forum for activities facilitating the exchange of goods and services thr

26、ough the use of standards, certification and related services to meet national and international needs.For further information on CSA services, write toCanadian Standards Association5060 Spectrum Way, Suite 100Mississauga, Ontario, L4W 5N6CanadaThe Standards Council of Canada is the coordinating bod

27、y of the National Standards system, a federation of independent, autonomous organizations working towards the further development and improvement of voluntary standardization in the national interest. The principal objects of the Council are to foster and promote voluntary standardization as a means

28、 of advancing the national economy, benefiting the health, safety, and welfare of the public, assisting and protecting the consumer, facilitating domestic and international trade, and furthering international cooperation in the field of standards. A National Standard of Canada is a standard which ha

29、s been approved by the Standards Council of Canada and one which reflects a reasonable agreement among the views of a number of capable individuals whose collective interests provide to the greatest practicable extent a balance of representation of producers, users, consumers, and others with releva

30、nt interests, as may be appropriate to the subject in hand. It normally is a standard which is capable of making a significant and timely contribution to the national interest. Approval of a standard as a National Standard of Canada indicates that a standard conforms to the criteria and procedures e

31、stablished by the Standards Council of Canada. Approval does not refer to the technical content of the standard; this remains the continuing responsibility of the accredited standards development organization. Those who have a need to apply standards are encouraged to use National Standards of Canad

32、a whenever practicable. These standards are subject to periodic review; therefore, users are cautioned to obtain the latest edition from the organization preparing the standard.The responsibility for approving National Standards of Canada rests with theStandards Council of Canada270 Albert Street, S

33、uite 200Ottawa, Ontario, K1P 6N7CanadaAlthough the intended primary application of this Standard is stated in its Scope, it is importantto note that it remains the responsibility of the users to judge its suitability for their particular purpose.Registered trade-mark of Canadian Standards Associatio

34、nCette norme est offerte en anglais seulement pour le moment. La CSA publiera la version enfranais ds quelle sera produite par lorganisme rdacteur.Approved byStandards Council of CanadaNational Standard of CanadaPublished in December 2006 by Canadian Standards AssociationA not-for-profit private sec

35、tor organization5060 Spectrum Way, Suite 100, Mississauga, Ontario, Canada L4W 5N61-800-463-6727 416-747-4044Visit our Online Store at www.ShopCSA.caCAN/CSA-ISO/IEC 18032:06Information technology Security techniques Prime number generationPrepared by InternationalOrganizationforStandardization/ Inte

36、rnational Electrotechnical CommissionReviewed byCAN/CSA-ISO/IEC 18032:06Information technology Securitytechniques Prime number generationDecember 2006 Canadian Standards Association CSA/3CAN/CSA-ISO/IEC 18032:06Information technology Security techniques Prime number generationCSA PrefaceStandards de

37、velopment within the Information Technology sector is harmonized with international standards development. Through the CSA Technical Committee on Information Technology (TCIT), Canadians serve as the Canadian Advisory Committee (CAC) on ISO/IEC Joint Technical Committee 1 on Information Technology (

38、ISO/IEC JTC1) for the Standards Council of Canada (SCC), the ISO member body for Canada and sponsor of the Canadian National Committee of the IEC. Also, as a member of the International Telecommunication Union (ITU), Canada participates in the International Telegraph and Telephone Consultative Commi

39、ttee (ITU-T).At the time of publication, ISO/IEC 18032:2005 is available from ISO and IEC in English only. CSA will publish the French version when it becomes available from ISO and IEC.This International Standard was reviewed by the CSA TCIT under the jurisdiction of the Strategic Steering Committe

40、e on Information Technology and deemed acceptable for use in Canada. (A committee membership list is available on request from the CSA Project Manager.) From time to time, ISO/IEC may publish addenda, corrigenda, etc. The CSA TCIT will review these documents for approval and publication. For a listi

41、ng, refer to the CSA Information Products catalogue or CSA Info Update or contact a CSA Sales representative. This Standard has been formally approved, without modification, by the Technical Committee and has been approved as a National Standard of Canada by the Standards Council of Canada.December

42、2006 Canadian Standards Association 2006All rights reserved. No part of this publication may be reproduced in any form whatsoever without the prior permission of thepublisher. ISO/IEC material is reprinted with permission. Where the words “this International Standard” appear in the text, they should

43、 be interpreted as “this National Standard of Canada”.Inquiries regarding this National Standard of Canada should be addressed toCanadian Standards Association5060 Spectrum Way, Suite 100, Mississauga, Ontario, Canada L4W 5N61-800-463-6727 416-747-4000www.csa.caTo purchase CSA Standards and related

44、publications, visit CSAs Online Store at www.ShopCSA.ca or call toll-free 1-800-463-6727 or 416-747-4044.Reference numberISO/IEC 18032:2005(E)ISO/IEC 2005INTERNATIONAL STANDARD ISO/IEC18032First edition2005-01-15Information technology Security techniques Prime number generation Technologies de linfo

45、rmation Techniques de scurit Gnration de nombres premiers ISO/IEC 18032:2005(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 are embedded are licensed to

46、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 Incorporated. Details of the softw

47、are 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 that a problem relating to it is

48、 found, please inform the Central Secretariat at the address given below. ISO/IEC 2005 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 mechanical, including photocopying and microfilm, without permi

49、ssion 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.org ii ISO/IEC 2005 All rights reservedISO/IEC 18032:2005(E) ISO/IEC 2005 All rights reserved iiiContents Page Foreword iv 1 Scope 1 2 Normative references . 1 3 Terms and definitions. 2 4 Symbols . 2 5 Trial division 3 6 Probabilistic primality tests . 4 6.1 Miller-Rabin primal