欢迎来到麦多课文档分享! | 帮助中心 海量文档,免费浏览,给你所需,享你所想!
麦多课文档分享
全部分类
  • 标准规范>
  • 教学课件>
  • 考试资料>
  • 办公文档>
  • 学术论文>
  • 行业资料>
  • 易语言源码>
  • ImageVerifierCode 换一换
    首页 麦多课文档分享 > 资源分类 > PDF文档下载
    分享到微信 分享到微博 分享到QQ空间

    BS ISO IEC 18032-2005 Information technology - Security techniques - Prime number generation《信息技术 安全技术 素数生成》.pdf

    • 资源ID:396449       资源大小:511KB        全文页数:26页
    • 资源格式: PDF        下载积分:5000积分
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    二维码
    微信扫一扫登录
    下载资源需要5000积分(如需开发票,请勿充值!)
    邮箱/手机:
    温馨提示:
    如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如需开发票,请勿充值!如填写123,账号就是123,密码也是123。
    支付方式: 支付宝扫码支付    微信扫码支付   
    验证码:   换一换

    加入VIP,交流精品资源
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    BS ISO IEC 18032-2005 Information technology - Security techniques - Prime number generation《信息技术 安全技术 素数生成》.pdf

    1、BRITISH STANDARD BS ISO/IEC 18032:2005 Information technology Security techniques Prime number generation ICS 35.040 BS ISO/IEC 18032:2005 This British Standard was published under the authority of the Standards Policy and Strategy Committee on 16 February 2005 BSI 16 February 2005 ISBN 0 580 45475

    2、4 National foreword This British Standard reproduces verbatim ISO/IEC 18032:2005 and implements it as the UK national standard. The UK participation in its preparation was entrusted to Technical Committee IST/33, IT security techniques, which has the responsibility to: A list of organizations repres

    3、ented on this committee can be obtained on request to its secretary. Cross-references The British Standards which implement international publications referred to in this document may be found in the BSI Catalogue under the section entitled “International Standards Correspondence Index”, or by using

    4、 the “Search” facility of the BSI Electronic Catalogue or of British Standards Online. This publication does not purport to include all the necessary provisions of a contract. Users are responsible for its correct application. Compliance with a British Standard does not of itself confer immunity fro

    5、m legal obligations. aid enquirers to understand the text; present to the responsible international/European committee any enquiries on the interpretation, or proposals for change, and keep the UK interests informed; monitor related international and European developments and promulgate them in the

    6、UK. Summary of pages This document comprises a front cover, an inside front cover, the ISO/IEC title page, pages ii to iv, pages 1 to 18, an inside back cover and a back cover. The BSI copyright notice displayed in this document indicates when the document was last issued. Amendments issued since pu

    7、blication Amd. No. Date Comments Reference number ISO/IEC 18032:2005(E) OSI5002 CEI/INTERNATIONAL STANDARD ISO/IEC 18032 First edition 2005-01-15 Information technology Security techniques Prime number generation Technologies de linformation Techniques de scurit Gnration de nombres premiers BSISO/IE

    8、C18032:2005IS/OIE23081 C:(5002E) DPlcsid Fremia ihTs PDF file may ctnoian emdebt dedyfepcaes. In ccaocnadrw eith Aebods licensilop gnic,y this file mairp eb ynted iv roweb detu slahl ton ide ebtlnu deess the typefaces whice era hml era deddebicsnede to i dnanstlaled t noeh computfrep reormign tide e

    9、htin.g In wodlnidaot gnhis file, trapise atpecc tiereht nser ehnopsiiblity fo not infriigngn Aebods licensilop gnic.y ehT ISO tneClar Secrteiraat caceptl on siibality in this .aera Ai ebods a tredamafo kr Aebod SystemI sncotaropr.de teDails fo teh softwacudorp erts sut deo crtaee this PDF file cna f

    10、 ebi dnuon tlareneG eh Info leratit evo the file; tP ehDc-Frtaeion marapterew setpo erimizde for irpnti.gn Evyre caer neeb sah taken to sneeru that the file is suitlbae fosu re yb ISO memdob rebeis. In tlnu ehikletneve y ttah lborp aem leratit gno it is f,dnuo plsaee inform ttneC ehlar Secrteiraat t

    11、a the serddaig sleb nevwo. ISO/IE5002 C All irthgs erse.devr lnUeto sswrehise specified, on trap fo this lbupictaion maeb y cudorperro de tuilizi den yna form ro na ybm ynae,s lecetrinoc ro mecinahcal, inclidung tohpcoiypodna gn micrfoilm, wittuoh repmissii non writign from ietI rehSa Ot tsserdda eh

    12、 ebolw or ISOs memreb i ydobn the cnuotrfo y ttseuqer ehe.r ISO cirypothg fofice saCe tsopale 65 eneG 1121-HC 02 av leT. 4 + 10 947 22 1 11 xaF0 947 22 14 + 9 74 E-mail coirypthgiso.o gr We bwww.is.o gro Pulbisdehi n Switlrez dnaii ISO/IE 5002 C Allr ihgtsser edevrBSISO/IEC18032:2005IS/OIE23081 C:(5

    13、002E) I SO/IE 5002 C All irhgts seredevr 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 primality test 4 6.2 Frobenius-Grantham primality test . 5 6.3 Lehmann primality

    14、 test. 5 7 Deterministic primality verification methods. 6 7.1 Elliptic curve primality certificate 6 7.2 Primality certificate based on Maurers algorithm 7 8 Prime number generation 8 8.1 Requirements 8 8.2 Using probabilistic tests 9 8.3 Using deterministic methods. 10 9 Candidate prime testing .

    15、11 Annex A (informative) Error probabilities 13 Annex B (informative) Generating primes with side conditions 16 Bibliography . 18 BSISO/IEC18032:2005IS/OIE23081 C:(5002E) iv I SO/IE 5002 C All irhgts seredevrForeword ISO (the International Organization for Standardization) and IEC (the International

    16、 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

    17、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 t

    18、echnical committee, ISO/IEC JTC 1. International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2. The main task of the joint technical committee is to prepare International Standards. Draft International Standards adopted by the joint technical committee ar

    19、e circulated to national bodies for voting. Publication as an International Standard requires approval by at least 75 % of the national bodies casting a vote. Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. ISO and IEC shall not b

    20、e held responsible for identifying any or all such patent rights. ISO/IEC 18032 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 27, IT Security techniques. BSISO/IEC18032:2005INTENRATIONAL TSANDADR IS/OIE23081 C:(5002E)I SO/IE 5002 C All irhgts serede

    21、vr 1Information technology Security techniques Prime number generation 1 Scope This International Standard specifies methods for generating and testing prime numbers as required in cryptographic protocols and algorithms. Firstly, this International Standard specifies methods for testing whether a gi

    22、ven number is prime. The testing methods included in this International Standard can be divided into two groups: Probabilistic primality tests, which have a small error probability. All probabilistic tests described here may declare a composite to be a prime. One test described here may declare a pr

    23、ime to be composite. Deterministic methods, which are guaranteed to give the right verdict. These methods use so-called primality certificates. Secondly, this International Standard specifies methods to generate prime numbers. Again, both probabilistic and deterministic methods are presented. NOTE R

    24、eaders with a background in algorithm theory may have had previous encounters with probabilistic and deterministic algorithms. We stress that the deterministic methods in this International Standard internally still make use of random bits, and “deterministic” only refers to the fact that the output

    25、 is correct with probability one. Annex B describes variants of the methods for generating primes so that particular cryptographic requirements can be met. The methods for generating, proving and verifying primality defined by this International Standard are applicable to cryptographic systems based

    26、 on the properties of the primes. NOTE The specifications of the tests given in this International Standard define the properties to be tested in the simplest possible form. Following these specifications directly will not necessarily produce the most efficient implementations. This is especially th

    27、e case for the Frobenius-Grantham test. 2 Normative references The following referenced documents are indispensable for the application of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendme

    28、nts) applies. ISO/IEC 9796-2:2002, Information technology Security techniques Digital signature schemes giving message recovery Part 2: Integer factorization based mechanisms ISO/IEC 15946-1:2002, Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: Ge

    29、neral BSISO/IEC18032:2005IS/OIE23081 C:(5002E) 2 I SO/IE 5002 C All irhgts seredevr3 Terms and definitions For the purposes of this document, the following terms and definitions apply. 3.1 composite number composite Integer N 1 is composite if it is not prime, i.e. there exist divisors of N that are

    30、 not trivial divisors. 3.2 entropy Total amount of information yielded by a set of bits. It is representative of the work effort required for an adversary to be able to reproduce the same set of bits. 3.3 Jacobi symbol Jacobi symbol of a with respect to an odd number n is the product of the Legendre

    31、 symbols of a with respect to the prime factors of n (repeating the Legendre symbols for repeated prime factors). NOTE Defined in Annex A of ISO/IEC 9796-2. 3.4 Legendre symbol Let p be an odd prime, and let a be a positive integer. The Legendre symbol of a with respect to p is defined as a (p - 1)/

    32、2mod p. NOTE Defined in Annex A of ISO/IEC 9796-2. 3.5 primality certificate Mathematical proof that a given number is indeed a prime. For small numbers primality is most efficiently proven by trial division. In these cases, the primality certificate may therefore be empty. 3.6 prime number prime In

    33、teger N 1 is prime if the only divisors of N are trivial divisors. 3.7 pseudo-random bit generator Deterministic algorithm which when given some form of a bit sequence of length k outputs a sequence of bits of length l k, computationally infeasible to distinguish from true random bits. 3.8 trial div

    34、ision Trial division of a number N means checking all prime numbers smaller than or equal to N to see if they divide N. 3.9 trivial divisor Any integer N is always divisible by 1, -1, N and N. These numbers are the trivial divisors of N. 4 Symbols a mod n for integers a and n, (a mod n) denotes the

    35、(non-negative) remainder obtained when a is divided by n. C a primality certificate C(N) primality certificate of the number N. BSISO/IEC18032:2005IS/OIE23081 C:(5002E) I SO/IE 5002 C All irhgts seredevr 3C 0 (N) the empty primality certificate. It indicates that trial division should be used to ver

    36、ify that N is a prime. gcd greatest common divisor g(x) mod (N,f(x) the remainder when the polynomial g(x) is divided by the polynomial f(x), calculating coefficients modulo the integer N k number of bits in N L limit below which primality is verified by trial division log b (a) the logarithm of a w

    37、ith respect to base b ln() the natural logarithm (i.e., with respect to the number e) M a lower bound on the size of an interval in which a prime number has to be found mina,b the minimum of the numbers a and b N candidate number to be tested for primality, where N is always a positive, odd number.

    38、n 0 a starting point in an incremental search for a prime n max an end point in an incremental search for a prime T a (probabilistic) test for primality Z N the set of the integer numbers 0, 1, 2, ., N-1, representing the ring of integers modulo N. Z N * the subset of Z N containing the numbers that

    39、 have a multiplicative inverse modulo N (i.e., if N is prime: the integer numbers 1, 2, ., N-1) Z N x/f(x) the ring of polynomials modulo f(x) with coefficients in Z N x the largest integer smaller than or equal to x. a parameter which determines the lower bound of the entropy of the output of a pri

    40、me generation algorithm the maximal number of steps in an incremental search for a prime 5 Trial division The primality of an integer N can be proven by means of trial division. This is done in the following way: 1. For all primes p N a. If N mod p = 0 then return “reject” 2. Return “accept” For sma

    41、ll integers N, trial division is less computationally expensive than other primality tests. Implementations of any primality test described in this standard may define a trial division bound L, below which trial division is used in order to prove the primality of integers. This International Standar

    42、d sets no value for L. NOTE It is assumed that the set of prime numbers below a certain size are already known. One practical way to implement the test may be to have a pre-computed table of the first few primes, do trial division by these, and then simply trial divide by all odd integers up to the

    43、square root. BSISO/IEC18032:2005IS/OIE23081 C:(5002E) 4 I SO/IE 5002 C All irhgts seredevrNOTE The size of integers for which trial division is less computationally expensive than another primality test, depends on the test and its implementation. A typical value for L might be L = 10 3 . 6 Probabil

    44、istic primality tests A probabilistic primality test takes a positive, odd number N as input and returns “accept” or “reject”. If N is a composite number, the tests described in this clause output “reject”, except with some error probability depending on the test being used. The probability that a c

    45、omposite number is accepted is not negligible. If N is a prime number, the Miller-Rabin test and the Frobenius-Grantham test always output “accept”. The Lehmann test rejects a prime number with a probability that is not negligible. In order to reduce the probability of errors, one usually makes seve

    46、ral iterations with the same input (and different choices for the random values). 6.1 Miller-Rabin primality test On input of a candidate number, N, the Miller-Rabin test starts with the following initialisation step: 1. Determine positive integers t and s such that N-1 = 2 t s, where s is odd. Subs

    47、equently, the Miller-Rabin test proceeds with one or more iterations of the following algorithm, which takes inputs t, s, N and outputs “accept” or “reject”. For each iteration, a different base b must be selected, with 2 b N-2. NOTE One iteration of the algorithm is called testing N for primality w

    48、ith respect to the base b. 1. Choose a random integer b such that 2 b N-2. 2. Let y = b smod N 3. if y 1 and y N-1 then do a. i = 1 b. while i t and y N-1 do i. y = y 2 mod N ii. if y = 1 then return “reject” iii. i = i + 1 c. if y N-1 then return “reject” 4. return “accept” A test for primality doe

    49、s not need to use exactly the same algorithm to be compliant with this International Standard. A test for primality is compliant with this International Standard if one iteration outputs “accept” if and only if one of the following requirements is satisfied for the chosen base: b smod N equals 1 b smod N equals N-1 For some i (0it): (b s ) 2 imod N equals N1 BSIS


    注意事项

    本文(BS ISO IEC 18032-2005 Information technology - Security techniques - Prime number generation《信息技术 安全技术 素数生成》.pdf)为本站会员(proposalcash356)主动上传,麦多课文档分享仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文档分享(点击联系客服),我们立即给予删除!




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1 

    收起
    展开