下载文档原格式
Comments on mutual authentication and key exchange protocols for low power wirelesscommunicationsSiaw-Lynn Ng and Chris MitchellAbstract—In[1],Shim describes“unknown key-share”attacks on the two protocols,server-specific MAKEP and linear MAKEP, proposed by Wong and Chan in[2].In this letter we point out an error in one of the attacks and demonstrate further undesirable properties in the protocols of Wong and Chan.Index Terms—Mutual authentication,key exchange.I.I NTRODUCTIONI N[2],Wong and Chan proposed two mutual authenticationand key exchange protocols(MAKEPs),namely server-specific MAKEP and linear MAKEP.They are designed to be used for establishing secure communications between a low-power wireless device(client)and a powerful base station (server).In[1],Shim described“unknown key-share”attacks on the two protocols.An unknown key-share attack on an authenti-cated key agreement protocol is an attack whereby an entity ends up believing it shares a key with an entity,and although this is in fact the case,mistakenly believes the key is instead shared with another entity.Here we point out that,while the attack on server-specific MAKEP works, the attack on linear MAKEP does not achieve the goals of an unknown key-share attack.In addition,we will demonstrate further limitations of the two protocols.Specifically,server-specific MAKEP allows the choice of the session key to be entirely under the control of the server,while in linear MAKEP,the authentication of the client to the server and the security of the public key scheme may be compromised in certain implementations.II.T HE PROTOCOLS AND THEIR LIMITATIONSA.Server-specific MAKEPThis protocol eliminates the use of public-key cryptographic operations at the client side and replaces them with symmetric key operations.Before running the protocol with a server, the clientfirst obtains a certificate from a trusted authority :Cert ID Sig IDwhere is’s long-live symmetric key.Inside the certificate is encrypted under’s public key.It is assumed Manuscript received July18,2003;revised September4,2003.The authors are with the Information Security Group,Royal Holloway, University of London,Egham,Surrey TW200EX,U.K.that and have authentic copies of.The protocol actions are as follows,with,representing nonces chosen by and respectively:1.:,Cert2.:ID3.:The session key is computed to be,which includes contributions from both party with the aim that no single party has full control over the selection of the session key.However,this aim is not achieved:the server can always ensure that the session key is its choice,by putting .It was pointed out in[1]that this protocol is susceptible to an unknown key-share attack,if an attacker is able to obtain the certificateCert ID Sig IDWe refer the reader to[1]for details.It was also pointed out in the same paper that by including ID in the encrypted message in step2,this attack can be prevented.We note, however,that in this improved protocol,the selection of the session key is still completely under the control of the server .This problem can be avoided by replacing in the first message by where is a one-way hash function, replacing in the second message by,and including in the encrypted message of the last step.B.Linear MAKEPThis protocol is designed to allow each client to commu-nicate with as many servers as it wants without inducing any scalability problems,and also to prevent any server impersonating its own clients.Let be a prime such that the discrete logarithm problem in is intractable.Let be a primitive element.The client randomly chooses a sequence of integersin as its secret keys.The corresponding sequence of public keys is in.For each pair of public keys,,a certificate is obtained from the:Cert ID Sig IDThe actions of the-th run of linear MAKEP are as follows, again with,representing nonces chosen by and respectively from.The session key is computed to be .1.:Cert2.:3.:,mod4.:Note that when receives and in step3,determines whethermod(1) before proceeding to decrypt to obtain.The unknown key-share attack described in[1]involves the attacker obtainingCert IDSig IDwhere,from’s public keys.When initiates linear MAKEP and sends Cert to, intercepts and replaces it with Cert.When sendsto in reply,forwards it to who computes using ’s public key,computes,and sends,to.Again, intercepts,and sends,to.Now,verifies that and are correct according to Cert and Equation (1).If so computes session key and sendsto,which forwards to.At this point however, the attack fails.This is because the last message expects is ,not,which cannot construct.Hence this“attack”described in[1]does not achieve the goals of an unknown key-share attack.However,there are some more serious weaknesses of this protocol.Firstly,the authentication of to relies on the asym-metric encryption method having certain properties that are not stated in[2],that is,a randomly chosen value should not decipher correctly.Consider the following attack,where has observed a successful run of the protocol and wishes to impersonate to.If,pretending to be,sends the old certificate to,will respond with a new nonce.Now lets,where and are the values from the intercepted run of the protocol,and sendsto.As specified in the protocol,determines whether and match using Equation(1).This will hold since.Thus will now decrypt.In most cases this will fail,but,for example,if RSA was used naively then it will work,and will believe it is communicating with.This is an instance of a successful unknown key-share attack:succeeds in misleading,without necessarily obtaining the session key.As pointed out by Shim in[1],such an attack will be detected if key confirmation is performed. Otherwise the protocol should include a requirement on the encryption function and also a test by as to whether decrypts correctly–only after this can be sure that it is communicating with.Another weakness in the protocol is the use of the secrets and in a linear equation for computing,without hiding the coefficient.It is not quite clear how these pairs of“public keys”are used,but if they are used more than once then an eavesdropper can simply obtain in thefirst run,in a subsequent run,compute to get,and then get.After that can impersonate to any other servers.A straightforward inclusion of in the third message(using instead of in) would prevent an eavesdropper from launching such an attack, but would still allow the server to impersonate its client .Hence treating the secret keys associated with Cert as long-term reusable secrets leads to a breach in security.This is a serious vulnerability,since some devices may be prone to“reset”attacks,where counters can be reset after a power failure,or some implementations may reuse certificates and keys due to the expensive overhead of updating the limited storage of key-signature sets.To prevent this,either servers will have to check with each other that Cert is never reused, which seems infeasible,or should delete the private keys as soon as they have been used.It would appear,then,that a secure implementation of linear MAKEP,while efficient in terms of computation,would incur a significant overhead in communication load,thereby potentially making it impractical.III.C ONCLUSIONIn this letter we have pointed out an error in the attack proposed by Shim in[1]on one of Wong and Chan’s MAKEPs ([2]).We have also shown further limitations of these protocols and suggested improvements.A CKNOWLEDGMENTThe authors would like to thank the anonymous referees for their suggestions and comments.R EFERENCES[1]Kyungah Shim.“Cryptanalysis of mutual authentication and key ex-change for low power wireless communications”.IEEE Communications Letters,V ol7,No5,2003,pp248–250.[2] D.S.Wong and A.H.Chan.“Mutual authentication and key exchangefor low power wireless communications”.Proc.IEEE MILCOM2001, V ol1,2001,pp39–43.。
软考信息安全工程师培训笔记5（1.5信息安全专业英语）软考信息安全工程师培训笔记五（1.5信息安全专业英语）1.5信息安全专业英语一.大纲要求1.5 信息安全专业英语* 阅读信息安全有关英文资料* 掌握本领域的基本英语词汇二.思维导图暂无三.备考知识要点1、cryptography:密码；plaintext明文；ciphertext密文；concealment隐藏；cryptology密码学；2、symmetric-key对称密钥；Symmetric-key cryptography refers to encryption methods in which both the sender and receiver share the same key(or,less commonly,in which their keys are different,but related in an easily computable way).对称密钥加密是指加密方法，在该方法中，发送者和接收者共享相同的密钥3、asymmetric key非对称密钥；Digita1 signatures 数字签名RSA and DSA are two of the most popular digital signature schemes4、elliptic curve cryptography椭圆曲线密码5、Cryptanalysis密码分析；quantum computer量子计算机；6、Antivirus software杀毒软件Network-attached storage (NAS,网络附加存储): is file-level computer data storage connected to a computer network providing data access to heterogeneous network clients.7、Penetration Testing Tools渗透测试工具四.历年真题分布2016年下半年上午真题71-75（1）is the science of hiding information. Whereas the goal of cryptography is to make data unreadable by a third party. the goal of steganography is to hide the data from a third party. In this article, I will discusswhat steganography is, what purposes it serves, and will provide an example using available software.There are a large number of steganographic （2）that most of us are familiar with (especially if you watch a lot of spy movies), ranging from invisible ink and microdots to secreting a hidden message in the second letter of each word of a large body of text and spread spectrumradio communication. With computers and networks, there are many other ways of hiding informations, such as:Covert channels (c,g, Loki and some distributed denial-of-service toolsuse the Internet Control （3）Protocol, or ICMP, a s the communicationchannel between the “bad guy”and a compromicyed system)Hidden text within Web pages Hiding files in “plain sight”(c,g. what better place to “hide”a file than with an important sounding name in the c:\winnt system32 directory) Null ciphers(c,g, using the first letter of each word to form a hidden message in an otherwise innocuous text)steganography today, however, is significantly more （4）than the example about suggest, allowing a user to hide large amounts of information within image and audio. These forms of steganography of tenare used in conjunction with cryptography so the information is doubleprotected; first it is encrypted and then hidden so that an advertisement first. find the information ( an often difficult taskin and of itself) and the decrypted it.The simplest approach to hiding data within an image file is called（5）signature insertion. In this method, we can take the binary representation of the hidden data and the bit of each byte within the covert image. If we are using 24-bit color the amount and will be minimum and indiscriminate to the human eye.（1）A、Cryptography B、Geography C、Stenography D、Steganography （2）A、methods B、software C、tools D、services（3）A、Member B、Management C、Message D、Mail（4）A、powerful B、sophistication C、advanced D、easy （5）A、least B、most C、much D、less正确答案：A、A、C、A、A试题解析：密码学是一门隐藏信息的科学。
强⽹杯2018-nextrsa-Writeup 强⽹杯2018 - nextrsa - Writeup原⽂地址：所有代码均已上传⾄我的俄罗斯套娃⼀样的rsa题⽬，基本把我见过的rsa套路出了⼀遍，值得记录⼀下level 0QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[*] Switching to interactive modeok!Firstly, please give me the proof of your work!x=chr(random.randint(0,0xff))+chr(random.randint(0,0xff))+chr(random.randint(0,0x1f))hashlib.sha256(x).hexdigest()[0:8]=='372c8af8'@ x.encode('hex')=[*] Got EOF while reading in interactive$发送teamtoken后，到第0关，较简单，爆破sha256即可，此时代码如下：QWB_nextrsa [master●] cat exp.py#!/usr/bin/env python# -*- coding: utf-8 -*-__Auther__ = 'M4x'from pwn import *from hashlib import sha256# context.log_level = "debug"def brute(cipher):# success("cipher -> {}".format(cipher))# print type(cipher)for a in xrange(0, 0xff):for b in xrange(0, 0xff):for c in xrange(0, 0xff):x = chr(a) + chr(b) + chr(c)if sha256(x).hexdigest()[0: 8] == cipher:# success("x -> {}".format(x))return xprint "not found"if __name__ == "__main__":io = remote("39.107.33.90", 9999)token = "icq9bae582b7f5d9ab6caed7d40150be"io.sendlineafter(":", token)io.recvuntil("=='")cipher = io.recvuntil("'", drop = True)x = brute(cipher)io.sendlineafter(")=", x.encode('hex'))success("Level 1 Clear!")io.interactive()io.close()碰撞失败的话多次尝试即可level 1为了⽅便后续处理，先写⼀个解rsa的函数，可以参考def rsa(n, p, q, e, c):assert n == p * qd = invert(e, (p - 1) * (q - 1))m = pow(c, d, n)return m下⼀关，给了n，e，c，并且经过尝试，n，c是不变的，只有c在改变QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![*] Switching to interactive modeok!input format:almost hex(m).replace("L","")=next-rsa=# n=0xc4606b153b9d06d934c9ff86a3be5610266387d82d11f3b4e354b1d95fc7e577# e=0x10001# c=0xa87fc50517b50db03a038c93c2a2c2c36de67660920da8720b787fedc3e19dd9@ m=[*] Got EOF while reading in interactive$尝试在分解n，发现能直接分解p = 289540461376837531747468286266019261659q = 306774653454153140532319815768090345109那么直接解开就可以了，此时代码如下：QWB_nextrsa [master●] cat exp.py#!/usr/bin/env python# -*- coding: utf-8 -*-__Auther__ = 'M4x'from pwn import *from hashlib import sha256from gmpy2 import invert# context.log_level = "debug"def brute(cipher):# success("cipher -> {}".format(cipher))# print type(cipher)for a in xrange(0, 0xff):for b in xrange(0, 0xff):for c in xrange(0, 0xff):x = chr(a) + chr(b) + chr(c)if sha256(x).hexdigest()[0: 8] == cipher:# success("x -> {}".format(x))return xprint "not found"def rsa(n, p, q, e, c):assert n == p * qd = invert(e, (p - 1) * (q - 1))m = pow(c, d, n)return mfmt = lambda m: hex(m).replace("L", "")if __name__ == "__main__":io = remote("39.107.33.90", 9999)token = "icq9bae582b7f5d9ab6caed7d40150be"io.sendlineafter(":", token)io.recvuntil("=='")cipher = io.recvuntil("'", drop = True)x = brute(cipher)io.sendlineafter(")=", x.encode('hex'))success("Level 1 Clear!")io.recvuntil("# n=")n = int(io.recvuntil("\n", drop = True), 16)io.recvuntil("# e=")e = int(io.recvuntil("\n", drop = True), 16)io.recvuntil("# c=")c = int(io.recvuntil("\n", drop = True), 16)p = 289540461376837531747468286266019261659q = 306774653454153140532319815768090345109m = fmt(rsa(n, p, q, e, c))io.sendlineafter("m=", m)success("Level 2 Clear!")io.interactive()io.close()level 2QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![+] Level 2 Clear![*] Switching to interactive modeok!=next-rsa=# n=0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da # e=0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a3371 # c=0x2add7528efe278a70a43f97fc5af83bbaab1238364735d998de005d7feb1a8ab931c7410f0f785db455857b8154a68de318bfffd2099c5b06d6a5e859b3812752e0c28dd626dfa1c26e1dbf8bc43686de75863da5f9df96331d81302cb6269e9d71661b0391 @ m=$给了n，e，c，求出m，发现e很⼤，直接尝试QWB_nextrsa [master●] python rsa-wiener-attack/RSAwienerHacker.py 0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc3 --------------------------Hacked!42043QWB_nextrsa [master●]求出了d，就可以解出明⽂了，代码太长就不贴了，所有代码都放在了我的中了level 3QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![+] Level 2 Clear![+] Level 3 Clear![*] Switching to interactive modeok!=next-rsa=# n=0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3 # e=0x3# c=0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e # b=0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000# m=b+x (x:64bit)@ x=[*] Got EOF while reading in interactive$已知n，c，e和明⽂的⾼位，本来看到e=3是想⽤低加密指数爆破的，尝试了⼀下没有出结果才注意到实际上我们已经有了明⽂的⾼位，这时才想起来在中有相关的介绍，同时也找到了⼀篇相关的，使⽤sage可以跑出结果，sage代码如下：QWB_nextrsa [master●] cat copper.sage# partial_m.sagen = 0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3 e = 3m = randrange(n)c = pow(m, e, n)beta = 1epsilon = beta^2/7nbits = n.nbits()kbits = floor(nbits*(beta^2/e-epsilon))#mbar = m & (2^nbits-2^kbits)mbar = 0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000c = 0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2 print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)PR.<x> = PolynomialRing(Zmod(n))f = (mbar + x)^e - cprint mx0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = nprint mbar + x0print x0使⽤sagemath运⾏即可得到缺失的明⽂可以使⽤在线运⾏sage的level 4QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![+] Level 2 Clear![+] Level 3 Clear![+] Level 4 Clear![*] Switching to interactive modeok!=next-rsa=# n=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b804 # e=0x10001# nextprime(p)*nextprime(q)=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377 # c=0x1c3588ac81ec3d1b439cfd2d5e6e8a5a95c8f95aaeff1b0ba49276ade80435323f307a17006ae2ffb4ca321e54387d9b33ed7ccda3117f7bc8d247ffd2ccdd67b7e2aad3d908d0a5187a73d13d532c1cf41758e2743bd4359bf72a99bbf0d716bb171cf636b @ m=$这⼀步的解决⽅式第⼀次遇到，⽐赛结束后也听许多表哥说了他们的⽅法，⼀个⽐⼀个精彩，这⾥介绍⼀下⼴外表哥和kira⼤佬的两种⽅法pq = n(p + x)(q + y) = n'-> xy + py + qx = t(t = n' - n)-> xq2 + (xy - t)q + ny = 0则该⽅程有素数接即可，可爆破x，y实现脚本QWB_nextrsa [master●] cat next.py#!/usr/bin/env python# -*- coding: utf-8 -*-__Auther__ = 'M4x'from gmpy2 import is_prime as primefrom gmpy2 import irootn = 1526047339891607168628775234024915827934301307714566779451471769235294187346669068628844220471458585486922687270529300883755401294959804429759601550703131500619523064472258174464375657398272934449945 nn = 152604733989160716862877523402491582793430130771456677945147176923529418734666906862884422047145858548692268727052930088375540129495980442975960155070313150061952306447225817446437565739827293444994 # print nn > nt = nn - nf1 = lambda x, y: pow(x * y - t, 2) - 4 * n * x * yf2 = lambda x, y, s: (t - x * y - s) / (2 * x)for x in xrange(1, 3000):for y in xrange(1, 3000):print x, yif f1(x, y) >= 0:s, b = iroot(f1(x, y), 2)if b:if prime(f2(x, y, int(s))):print "Success"print f2(x, y, int(s))exit()⼀分钟左右即可爆破出q另⼀种⽅法：虽然⽐较⿇烦，但分解那⼀步秒出level 5QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![+] Level 2 Clear![+] Level 3 Clear![+] Level 4 Clear![+] Level 5 Clear![*] Switching to interactive modeok!=next-rsa=# n=0x1daf9fab45ff83e751bf7dd1b625879b3a8c89d4a086e0806b31e2a2cc1c4c1bc8694db643acc4911f3d143c1951f006df9e0a7282b65839d84b36102b8f2307c4eaa561e65435350d9cb2b978ace582535ae00d948546520252d0f59d82dcfa59bac3381 # e=0x10001# c=0xdcb90409d48b54a73e408d16f5df6d4cc49183cd47eb8ccbc27837fecdf902233979895e8d789a30ca13ff0d9f452321c62864ea153aa7f9d4ed6af885a580d740a906230da76e1f8905e17ecad03f31ce2aaf1ad4f3a4416c80e4d1d220b85d90a533acb5 @ m=$下意识的就上yafu了（p，q相差过⼤或过⼩），秒解QWB_nextrsa [master●] yafu "factor(@)" -batchfile ./n_yafu=== Starting work on batchfile expression ===factor(89533915895730376845429388317318135465963715353319668296037460436832261571698764116420554922112987252021884948875657862384344377649170583262156985771188545996699834706518979095963558441172283692904 =============================================fac: factoring 89533915895730376845429388317318135465963715353319668296037460436832261571698764116420554922112987252021884948875657862384344377649170583262156985771188545996699834706518979095963558441172283 fac: using pretesting plan: normalfac: no tune info: using qs/gnfs crossover of 95 digitsdiv: primes less than 10000fmt: 1000000 iterationsrho: x^2 + 3, starting 1000 iterations on C317rho: x^2 + 2, starting 1000 iterations on C317rho: x^2 + 1, starting 1000 iterations on C317pm1: starting B1 = 150K, B2 = gmp-ecm default on C317Total factoring time = 6.6791 seconds***factors found***P9 = 743675299P309 = 1203938278118477306658929226010478740748974578397549658241875537092865868759999841226682384701780813779884397489927359579874178094076654054125804516887531395562727096930497608149864857097698006141 ans = 1eof; done processing batchfilelevel 6QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![+] Level 6 Clear![*] Switching to interactive modeok!=next-rsa=# n=0x7003581fa1b15b80dbe8da5dec35972e7fa42cd1b7ae50a8fc20719ee641d6080980125d18039e95e435d2a60a4d5b0aaa42d5c13b0265da4930a874ddadcd9ab0b02efcb4463a33361a84df0c02dfbd05c0fdc01e52821c683bd265e556412a3f55e495 # e=0x3# c=0xb2ab05c888ab53d16f8f7cd39706a15e51618866d03e603d67a270fa83b16072a35b5206da11423e4cd9975b4c03c9ee0d78a300df1b25f7b69708b19da1a5a570c824b2272b163de25b6c2f358337e44ba73741af708ad0b8d1d7fa41e24344ded8c613 @ m=$e只有3，这次应该是低加密指数攻击了QWB_nextrsa [master●] cat smallE.py#!/usr/bin/env python# -*- coding: utf-8 -*-__Auther__ = 'M4x'from gmpy2 import irootn=0x7003581fa1b15b80dbe8da5dec35972e7fa42cd1b7ae50a8fc20719ee641d6080980125d18039e95e435d2a60a4d5b0aaa42d5c13b0265da4930a874ddadcd9ab0b02efcb4463a33361a84df0c02dfbd05c0fdc01e52821c683bd265e556412a3f55e49517 e=0x3c=0xb2ab05c888ab53d16f8f7cd39706a15e51618866d03e603d67a270fa83b16072a35b5206da11423e4cd9975b4c03c9ee0d78a300df1b25f7b69708b19da1a5a570c824b2272b163de25b6c2f358337e44ba73741af708ad0b8d1d7fa41e24344ded8c61396 i = 0while True:if iroot(c + i * n, 3)[1] == True:print "Success!"print iroot(c + i * n, 3)breaki += 1QWB_nextrsa [master●] python smallE.pySuccess!(mpz(104006579428345283523433238671877178267428435064699466071750154062940835183547608420976538837779492110250431567788036381618153563653095305326927756386752215730090496214614571725271888752014603007820 level 7QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![+] Level 2 Clear![+] Level 3 Clear![+] Level 4 Clear![+] Level 5 Clear![+] Level 6 Clear![+] Level 7 Clear![*] Switching to interactive modeok!=next-rsa=# n1=0xb4e9991d2fac12b098b01118d960eb5470261368e7b1ff2da2c66b4302835aa845dd50a4f749fea749c6d439156df6faf8d14ce2a57da3bac542f1843bfc80dfd632e7a2ef96496a660d8c5994aea9e1b665097503558bc2756ab06d362abe3777d8c1f38 # e1=0x10001# c1=0x3a10c58ed3e8f9eade48dad7d36518dabeeca3d169c848f3b4b2bb027220e13d8b071c55046b14213e966ad9c381e5cad9773d455aa0d36ddff9b9f24873d0979f1caff95d9569e4f312514c7e01979b39c466aa2d27ad521ae3c1ea2025ca2290185b3d # n2=0xc31344c753e25135d5eed8febaa57dd7020b503a5569bdd4ae6747b5c36436dc1c4d7ead77bfc1034748bcc630636bae1c8f4ca5dee8246b3d6f3e8b14e16487733b14ec8e587e07a7a6de45859d32d241eaf7746c45ff404f1a767ab77e8493ae8141fe # e2=0x10001# c2=0xbefa7d62f15cafc81d098fdd524411537e948d83266ef22848f44d2e43d1f1388a26bb21c8fb08b571c7cbd6630d6f2b409c85c68a6419e472941e4978f60b93e1ce850344dbe99f1918cb5b8c35075bbdca82fa233d1300f108e4b75ce10d7b0ffa145bce @ m1=$给了n1，c1，n2，c2，且n⽆法分解，尝试公约数分解QWB_nextrsa [master●] cat gcdN.py#!/usr/bin/env python# -*- coding: utf-8 -*-__Auther__ = 'M4x'from libnum import gcdn1=0xb4e9991d2fac12b098b01118d960eb5470261368e7b1ff2da2c66b4302835aa845dd50a4f749fea749c6d439156df6faf8d14ce2a57da3bac542f1843bfc80dfd632e7a2ef96496a660d8c5994aea9e1b665097503558bc2756ab06d362abe3777d8c1f388c # e1=0x10001# c1=0x3a10c58ed3e8f9eade48dad7d36518dabeeca3d169c848f3b4b2bb027220e13d8b071c55046b14213e966ad9c381e5cad9773d455aa0d36ddff9b9f24873d0979f1caff95d9569e4f312514c7e01979b39c466aa2d27ad521ae3c1ea2025ca2290185b3 n2=0xc31344c753e25135d5eed8febaa57dd7020b503a5569bdd4ae6747b5c36436dc1c4d7ead77bfc1034748bcc630636bae1c8f4ca5dee8246b3d6f3e8b14e16487733b14ec8e587e07a7a6de45859d32d241eaf7746c45ff404f1a767ab77e8493ae8141fee # e2=0x10001# c2=0xbefa7d62f15cafc81d098fdd524411537e948d83266ef22848f44d2e43d1f1388a26bb21c8fb08b571c7cbd6630d6f2b409c85c68a6419e472941e4978f60b93e1ce850344dbe99f1918cb5b8c35075bbdca82fa233d1300f108e4b75ce10d7b0ffa145bce print "p -> {}".format(gcd(n1, n2))print "q1 -> {}".format(n1 / gcd(n1, n2))print "q2 -> {}".format(n2 / gcd(n1, n2))QWB_nextrsa [master●] python gcdN.pyp -> 1725568696754776279984980552098360717842471500051715632277468961561228721883664092077858616916298226242392904349624010793757959265471900335289014726294600982144849113624062993956860984568848023527676 q1 -> 132351070426725062043554691080648210190952108157658335988407251230007075283172499240825840919032041018784725171991038079646749244434399109751200470150528052302049968282955114052567000382702788528085 q2 -> 142712204088308994057536283419724413794506016166476894328600394909477811164746138340181564452439035177705892406900049909054445185976447566687912817760888522575392942071446149843167125603211027327213 level 8QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 1 Clear![+] Level 2 Clear![+] Level 3 Clear![+] Level 4 Clear![+] Level 5 Clear![+] Level 6 Clear![+] Level 7 Clear![+] Level 7 Clear![+] Level 8 Clear![*] Switching to interactive modeok!=next-rsa=# c1=pow(m,e1,n),c2=pow(m,e2,n)# n=0xace2aa1121d22a2153389fba0b5f3e24d8721f5e535ebf5486a74191790c4e3cdd0316b72388e7de8be78483e1f41ca5c930df434379db76ef02f0f8cd426348b62c0155cdf1d5190768f65ce23c60a4f2b16368188954342d282264e447353c62c10959fe # e1=0xac8b# c1=0x9e84763bdbe246fad0a9cd52fda6233e6128a6210efaf3e6dea4fe272f78ad1f8f5cc7022f62f4f542341128e42d6fd10e67c5f96edbd243917c0151289f7228e44019b8c65a541d7306b398465e26b69cab36cc61e4ac094832b4299bbaf4630b722a0fb4f # e2=0x1091# c2=0x9817fdc7b31a8f9cde1794096d3aa2bc6fe06fe34d4b7c9ca9a77982adf67fd4a7e636659553f4168a16757dc3a75e54ff850b9a94a5270f4f75502c7055a3a389df2ea6b00784a4e78e66901b427253c0f343f127e0ff162a349bb14eb4c1453fc6daace19 @ m=$⼀个n，多组c，e，采⽤共模攻击共模攻击写在最后的脚本⾥了level 9QWB_nextrsa [master●] python exp.py[+] Opening connection to 39.107.33.90 on port 9999: Done[+] Level 0 Clear![+] Level 1 Clear![+] Level 2 Clear![+] Level 3 Clear![+] Level 7 Clear![+] Level 8 Clear![*] Switching to interactive modeok!=next-rsa=# c1=pow(m,e,n1),c2=pow(m,e,n2),c3=pow(m,e,n3)# e=0x3# n1=0x43d819a4caf16806e1c540fd7c0e51a96a6dfdbe68735a5fd99a468825e5ee55c4087106f7d1f91e10d50df1f2082f0f32bb82f398134b0b8758353bdabc5ba2817f4e6e0786e176686b2e75a7c47d073f346d6adb2684a9d28b658dddc75b3c5d10a22a3 # c1=0x5517bdd6996b54aa72c2a9f1eec2d364fc71880ed1fa8630703a3c38035060b675a144e78ccb1b88fa49bad2ed0c6d5ad0024d4bb18e7d87f3509b0dbf238a0d1ff33f48ffc99c1bdf2f2547a193e7ab66eec562a7bc3f9521f70d453ff6d1fdb24de40b3f62 # n2=0x60d175fdb0a96eca160fb0cbf8bad1a14dd680d353a7b3bc77e620437da70fd9153f7609efde652b825c4ae7f25decf14a3c8240ea8c5892003f1430cc88b0ded9dae12ebffc6b23632ac530ac4ae23fbffb7cfe431ff3d802f5a54ab76257a86aeec1cf47d4 # c2=0x3288e3ea8c74fd004e14b66a55acdcbcb2e9bd834b0f543514e06198045632b664dac3cf8578cde236a16bef4a1246de692ec6a61ce507a220fa04e09044632787ba42b856cb13be6e905c20b493004822888d3c44c6fc367c7af0287f1683f08baae5bb # n3=0x280f992dd63fcabdcb739f52c5ed1887e720cbfe73153adf5405819396b28cb54423d196600cce76c8554cd963281fc4b153e3b257e96d091e5d99567dd1fa9ace52511ace4da407f5269e71b1b13822316d751e788dc935d63916075530d7fb89cbec9b # c3=0xb0c5ee1ac47c671c918726287e70239147a0357a9638851244785d552f307ed6a049398d3e6f8ed373b3696cfbd0bce1ba88d152f48d4cea82cd5dafd50b9843e3fa2155ec7dd4c996edde630987806202e45821ad6622935393cd996968fc5e251aa35 @ m=[*] Got EOF while reading in interactive$e = 3，给了三组数据，使⽤⼴播攻击，⼴播攻击也写在最后的脚本⾥了flag最终脚本太长，就不贴出来了，放到上了referencemore初次之外，还见过已知p⾼位的，可以参考以及修复证书的，参考Jarvis OJ 600分的RSA。
一个基于RSA 的改进公开密钥算法刘益和1,2 ，戴宗坤1， 李卉3(1.四川大学信息安全研究所，成都 610064；2.内江师范学院计算机与信息科学系，内江 641112；3.中国移动通讯集团公司市场部，北京 100032）摘要：针对RSA 公开密钥算法可能存在的同模攻击和选择密文攻击等安全问题,本文利用两个组合恒等式和RSA 公开密钥算法,构造出了一种改进的公开密钥算法,该算法简单,能避免或部分避免RSA 算法这几个典型的安全问题,从而比RSA 更具有安全性。
关键字：组合恒等式；RSA 公开密钥算法；公开密钥 中图分类号：TP 3091 引言自1976年Diffie 和Hellman [1] 首先公布公开密钥密码学的概念后,人们提出了多种公开密钥算法,其中许多是不安全的,而那些被视为安全的却不实用,要么密钥太大,要么密文远大于明文。
而RSA 公开密钥算法是到目前为止,已知的少数几个既安全又实用的算法之一。
但RSA也存在几个典型的安全问题[2－3],本文利用两个组合互逆恒等式和RSA 公开密钥算法,构造出了一种改进的公开密钥算法,该算法由于可以另设密码参数,从而比RSA 更具有安全性,算法中的组合恒等式、参数的设定并不复杂,所以该算法是实用的。
2已知结果2.1 RSA 公开密钥算法[4]及安全性问题RSA 公开密钥算法：公开密钥 n ：两个大素数p,q 的乘积（p 和q 必须保密）e: 与（p-1）(q-1)互素 私人密钥 d: 满足ed=1 mod (p-1)(q-1) 加 密 c=m e mod n 解 密 m=c d mod nRSA 公开密钥算法的安全性问题针对RSA 公开密钥算法可能面临的同模、选择密文、同态特性及循环等多方面的攻击[2－3],本文设计的算法,在秘密参数安全情况下,能避免或部分避免类似的攻击。
2.2 组合恒等式设{a m }和{b m }是两个给定的数列,对于任意的非负整数k,下面两个等式是等价的：a m =(-1)∑=mi 0iC k i km ++b i (1)b m =(-1)∑=mi 0iCk i km ++a i （m=0,1,2,…） （2）其中Cki km ++表示从m+k 元素中取出i+k 个元素的组合数,这两个组合恒等式的等价证明,基金项目：四川省教育厅自然科学重点项目2003A161。
基于RSA的前向安全的防欺诈的门限数字签名方案第25卷第6期2008年6月计算机应用与软件ComputerApplicationsandSoftwareV o1.25No.6Jun.2008基于RSA的前向安全的防欺诈的门限数字签名方案温翔袁丁(四川师范大学计算机科学学院四川成都610068)摘要以RSA数字签名方案和前向安全的理论为基础,结合Feldman可验证的秘密共享方案,提出了一种基于RSA的前向安全和防欺诈的门限数字签名方案.该方案中用于数字签名的私有密钥由一个单向函数控制随时间的推移不断更新,而公有密钥保持不变,即使攻击者获得了某个时期的私钥,他也无法伪造该时期之前的签名.该方案在签名过程中溶入了部分签名和防欺骗的秘密共享方案,相比干现有的RSA签名方案,该方案具有更高的安全性.关键词RSA前向安全防欺诈门限部分签名ATHRESHoLDDIGITALSIGNATURESCHEMEWITHFoRWARD.SECUREANDCHEA T.PRooFBASEDoNRSA WenXiangYuanDing(CollegeofComputerScience,SichuanNormalUniversity,Chengdu610068,Sichuan,Chin a)AbstractProposedaforward—secureandcheat?proofthresholddigitalsignaturescheme,whichbasedonRSAdigitalsignat ureschemeandtheforward—securetheory,whileFeldman'Sverifiablesecretsharing(VSS)wasemployed.Inthisscheme ,thedigitalsignature'Sprivatekeyisunderthecontrolofaone—wayfunctionandcontinuallychangeswithtimegoingby,butitspublickeyremainsthesame. Evenifanattack—erinterceptsandcapturestheprivatekeyatacertaintime,he/shestillcannotfakethesignature ofthetimebefore.Thedistributivesigna—tureandcheat?proofsecretsharingschemeareusedduringthecourseofthesignatureinthissc paredwithrecentRSAdigitalsig?nature,thisschemehasahighersecurity.KeywordsRSAForward??secureCheat-?proofThresholdDistributivesignature0引言数字签名技术作为信息安全领域的一项重要技术,在当今的信息时代所起到的作用越来越大.特别在电子商务领域,数字签名可以说是电子商务发展的基石.多年来,RSA是被研究得最广泛的公钥算法之一,经历了各种攻击的考验,逐渐成为比较安全的加密算法.相应的以RSA加密算法为基础的诸多RSA数字签名方案被广泛地加以应用.但是数字签名方案的安全性不仅体现在其签名算法本身基于数学理论的安全性,密钥的安全也是其安全性的重要体现.Shamir在1979年提出了一种秘密共享体制…,把密钥分解成多个子密钥,供多个秘密共享参与者共享密钥,密钥的安全性得到了一定的提高.于是基于此理论的门限的数字签名方案得到了广泛的应用.但实际上,对于一些应用时间比较长的数字签名方案,攻击者还是有足够的时间逐一攻破,使被攻破的子密钥的数量达到其门限数,从而攻破密钥.这就成为了传统数字签名方案的一个安全隐患.针对以上问题,1997年Anderson第一次提出了前向安全的数字签名方案.前向安全的基本思想是:将整个签名体制的生存期化为若干时间段,用于签名的私钥在不同的时间段更新,这样即使攻击者获得了某个时期的密钥,也无法对该时期之前的签名构成威胁.1999年,在文献[3]中,M.Bellare和S.K.Miner对前向签名进行了形式化定义,提出了一套系统公钥保持不变,私钥不断更新的前向数字签名方案.此后文献[4]和文献[5]根据此方案分别提出了一种基于椭圆曲线密码体制的前向的数字签名方案和基于ELGamal的前向数字签名方案,但文献[6]和文献[7]分别指出了上述两种方案不是真正的前向更新的签名方案,并提出了新的可前向更新的签名方案.本文提出的基于RSA的前向安全的防欺骗的门限数字签名,不仅对文献[7]的签名方案进行了简化和改进,而且结合了Feldman可验证的秘密共享方案j,是一种比较完备的RSA门限签名方案.1预备知识1.1一种基于RSA的前向安全的数字签名此方案对文献[7]的方案进行了简化和改进,是一种更为简单实用的RSA前向数字签名方案.其具体实现过程如下:1.1.1初始化设置任选两个互异强素数P,q,即有P=2u+1,q=2v+1.其中u和V是两个互异大的素数.令N=Pq,N=.有(』,『)=(P一1)(q一1)=4uv=4N.设g为z的一个阶为Ⅳ的收稿日期:2007一O6一Ol.四川I省科技厅科技攻关项目(05GGO07—008).温翔,硕士生,主研领域:信息安全和网络安全.第6期温翔等:基于RSA的前向安全的防欺诈的门限数字签名方案281 元素.任取e∈且满足(e,咖(,v))=1,计算d0,使得ed0=lmod4~(,v).将签名系统有效期分为个阶段.系统公钥为(e,,v),系统初始私钥为(u,,).任取一正整数n,且n满足1<n<,v,一般隋况下n取2.H()是一个公开的安全哈希函数,且H()<,v.1.1.2密钥的更新i表示第i时间段,d表示第i时间段的签名密钥.当时间从i一1时刻进入i时刻时,密钥进行以下更新.第一步:如果i=T+1,签名密钥d设为空串.第二步:如果1≤i<T+1,则d=mod4~(N),然后删除dH.1.1.3签名过程假设待签名的明文信息为m,则在i时间段,签名者计算U =gmodN,c=H(m『Ii),5=g~idlmodN.则签名为(i,U,c,S).1.1.4验证过程第一步:验证者首先检验i≤T是否成立,如果不成立,则为无效签名.否则进行下面计算..f第二步:验证者计算y=SimodN.如果y=modN,则签名为有效签名,否则为无效签名.1.1.5方案的有效性证明由数学归纳法可知d=簖'mod4~(,v),并且很容易得出'e=lmod4~(N)=1modN,g=gmodN.事实上:ySimodNgUCidienlmodNni.modNgimodN=DmodN因此y=-modN,即签名方案是有效的.由此我们可以看到,在整个签名过程中,用于验证的公钥e是不变的,而私钥d却通过一个单向函数的作用随着时间不断地改变,这样即使攻击者获得了当前时间段的密钥,他也无法伪造这之前的签名,这样就把损失减小到最低.1.2Feldman可验证秘密分享方案为了防止秘密分发者分发错误的密钥,Feldman于1987年提出了一个可验证秘密分享方案j,每个共享秘密参与者可以验证他所拥有子秘密的正确性.该方案的具体过程如下:1.2.1初始化阶段可信中心选择一个可公开大素数P,并有一素数q是P一1的大的素因子,即:qIP一1,再随机选择g∈Z.,且g的阶为q,即:g=lmodp.1.2.2密钥分发阶段假设共享秘密为,其中∈可信中心随机选择t一1阶多项式,()=00+0l+02+…+0—l'一,其中0=,计算并公布=g~modp(=0,1,2…,t一1).可信中心把子密钥=,()modq秘密分发给各个共享秘密参与者i(i=1,2, 3,…,n).1.2.3子密钥验证阶段l一1共享秘密参与者i接收到后,计算=兀m.,如JO果=moap,则接收,否则拒绝接收并且发送验证消息告知可信中心.2基于RSA的前向安全和防欺诈的门限数字签名方案基于上述理论,本文提出了一种基于RSA的前向安全和防欺诈的门限数字签名方案.该方案具有前向安全,防欺诈等功能,而且考虑到传统门限RSA签名体制中需要对剩余环中元素求逆的问题,所以对原有秘密共享体制作了一些改进,具有良好的抗攻击能力.该方案中有一个可信中心,一个是秘密分发中心CA,负责子密钥的发放和密钥的更新;一个是签名合成中心sc,负责部分签名的验证和密钥的合成.该方案有7个阶段构成.2.1初始化阶段在T=0时刻,CA任选两个互异强素数P,,即有P=2u+1,q=2v+1.其中u和是互异的两个大素数.令,v=Pq,=u.有(,v)=(P一1)(q一1)=4uv=4N.设g为的一个阶为,v的元素.任取e∈且满足(e,咖(,v))=1,计算d∞,使得ed=lmod4~(,v).系统公钥为(e,,v),系统初始私钥为(u,,d【0).明文为m,H()是一个公开的安全哈希函数,且1t()<,v.2.2私钥的分发阶段在T=时段,CA根据(t,n)f-j限方案分派时段的签名密钥d",具体的分发过程如下:第一步:cA密钥分发者随机选择t一1阶段多项式/()=d'+0l+02+…+0f-l卜modN,满足(0)=d∽,其中0∈zⅣ](=1,2,…,t一1),且1<0<,v一1,并计算d=()兀m.dN(12",n).注意,f1.2,…,且f≠I—I—f这里考虑到对剩余环z㈤中元素求逆的问题,在选择参数时,1≤.<rain(u,),且尽量取小整数,而且应该满足对任意的s,有((一),咖(,v))=1,即(一)在剩余环z()中有逆元素.为了简便地找到这样的,只需让(—)为奇数,且1≤(一)<rain(u,).第二步:cA向各共享秘密参与者i秘密发送,并令..=d∽,计算=g_1.2互音'modN(f=0,1,2,…,f一1),U=g"modN,并公布(i,,U).第三步:共享秘密参与者i接收到后,开始计算=一1兀()Im1od,v,(f=0,1,2,…,f一1),如果=modN亏,则各个共享秘密参与者i广播"确认"信息,否则广播"终止" 信息.第四步:如果所有共享秘密参与者i都广播的是"确认"信息,那么共享秘密参与者i接受并各自保存.2.3私钥更新阶段当时间从一1时刻进入时刻时,CA执行以下过程:如果=T+1,签名密钥d"设为空串.如果1≤<T+1,则有d"=(d【J)modN.然后删?除,随机选择一多项式使得/(0)=d【J,重复初始化密钥分发阶段的工作.这时各共享秘密参与者i得到的密钥是(i=1,2,…,n).282计算机应用与软件2008_q-2.4签名阶段当密钥分发等初始化工作结束后,各个共享秘密参与者就开始进行"部分签名".假设在时间段有t个共享秘密参与者G.,G2,…G来进行门限签名,签名者计算c"'=(mll),s=一f"modN.并把签名(i,c",)发送给sc.2.5验证部分签名阶段在时段,Sc新收到G的签名后,对G的签名进行验证.卜1,,SC计算=【丌()modN(z=0,1,2…,一1),如_-百果":smodN,则G部分签名是合法的,否则不合法,并且可信中心发送"警告"消息告知G.2.6合成签名阶段如果所有用户的部分签名都合法,则由sc负责合成签名.可信中心只需针对每个合法G(i=1,2,…,t)计算s"=rH,)rnodN,则合成的签名为(i,U,c,s'.f=l2.7验证合成签名阶段第一步:验证者首先检验i≤T是否成立,如果不成立,则为无效签名.第二步:要验证(i,U,C",S")是消息m的合法签名,即计算y=(.s)'modN,如果Y=modN,则签名为时段的有效签名,否则为无效签名.3安全性分析(1)本方案加密系统的设计是建立在经典加密算法RSA之上的,即基于大数分解的困难性问题.在一般情况下,RSA应当认为是安全的加密算法.(2)本方案的密钥的更新所用到的单向函数是建立在模合数的平方根计算困难性问题上的,d=.mo(N),即使攻击者得到当前密钥d,也无法计算之前的密钥d,从而无法伪造之前的签名.(3)在密钥的有效期内,用于签名的私钥随时间的推移不断更新,而公钥保持不变,相对于一般的密钥的前向更新来说,做到了真正意义上的前向安全.(4)本方案结合了Fledman可验证的秘密共享方案,使得可信中心和共享秘密参与者可以互相检验,从而比一般的门限方案具有更高的安全性.(5)在具体门限实现过程中,不是简单的合成私有密钥,而是每个共享秘密参与者都先用子密钥生成部分签名,再由部分签名来合成新的签名,从而使密钥的安全性大大提高.(6)本方案可以非常方便地直接对签名进行验证,在实际操作中易于实现.4结论本方案将RSA公钥加密体制,前向安全的理论和防欺诈的门限思想有机地集合在一起,形成了一套完整和安全的秘密共享体制,使其能够有效地抵御伪造签名和密钥的欺诈.在该方案中,用于签名的私有密钥由一单向函数控制,随时间的推移不断更新,而用于验证签名的共钥始终保持不变.在RSA门限的实现中,不是进行简单的秘密的恢复,而是用到了对分发的子密钥和签署的部分签名的验证,防止了门限中的欺诈行为的发生,从而保证了签名的可靠性.参考文献[municationsoftheACM,1979,24(11):612—613.[21AndersonR.TworemarksonpublickeycryptologT[R]InvitedLec—ture,ACM—CCS97,1997.[3]BellareM,MinerS.Aforward—securedigitalsignaturescheme[A.M Wiener.CRYPTO99,vol1666ofLNCS,Berlin:Springer—V erlag, 1999:431—448.[4]詹雄泉,洪景新.基于椭圆曲线密码体制的一种具有前向安全的数字签名方案[J].厦门大学,2005,44(2):189～192.[5]吴克力,王庆梅,刘风玉.一种具有前向安全的数字签名方案[J].计算机工程,2003,29(8):122—123.[6]符茂胜,任哲,侯整风.基于ECC的前向安全数字签名的研究与改进[J].计算机工程,2006,23(14):109一l10,l13.[7]李旒,何明星.基于RSA的前向安全的数字签名[J].计算机工程与应用,2006,42(16):124—126.『81FeldmanP.Apracticalschemefornon—interactiveverifiablesecretsha—ring『A].Proc.ofIEEEFund.ofComP.Sci,1987:427—437.(上接第261页)时贯用的平均方法所带来的水印信息严重削弱的缺点,使水印的鲁棒性特别是抗局部攻击能力大大提高.这种算法移植性高,已在小波域的算法上得到验证.参考文献[1]VanSchyndelRG,TirkelAZ,OsborneCF.Adigitalwatermark[A]. ProceedingoftheIEEEInternationalConferenceonImageProcessing, 1994:86—90.『21AndrewBWatson.Dctquantizationmatricesvisuallyoptimizedforindi—vidualimages[A].ProceedingofSPIE,1993:1913—1914.[3]MartinKutter,FabienAPPetttcolasb.Afairbenchmarkforimagewa—termarkingsystems[A].ProceedingofElectronicImaging,Securityand WatermarkingofMultimediaContents,1999:226—239.[4]张卫,高政.STIRMARK基准测试程序在数字水印方案评价中的应用[J].电视技术,2004,266(8):75—77.[5]燕晓,蒙应杰,王阳,郁军.一种强干扰背景下的盲加性水印算法[J].软件,2005,16(9):1678—1684.[6]JiannShuLee,ShihTsungLiang,KoChinaHsu.Promotingwatermark performancebyusingenergyreallocation[c].Proceedingofthe8th IEEEInternationalSymposiumonComputersandCommunication,Ke—merAntalya.Turkey,2003.(上接第279页)[7]ZhangZhen,WangXiaoming.AP2PGLOBALTRUSTMODELBASED ONRECOMMENDATION.ProceedingsoftheFourthInternationalCon—fereneeonMachineLearningandCybernetics,Guangzhou,18—2IAu—gust,2005.[8]XiongLi,LiuLing.PeerTrust:SupportingReputation—BasedTrustforPeerto—PeerElectronicCommunities.IEEEtransactionsonknowledge anddataengineering,2004,16(7).。
针对离散私钥比特泄漏的RSA格攻击方法刘向辉;韩文报;王政;权建校【期刊名称】《计算机工程》【年(卷),期】2014(000)003【摘要】RSA algorithm is one of the most widely used public key cryptosystems at present and lattice attacks play an important role for the analysis of RSA system. The problem of partial discrete private key bit leakage is transformed into the solution of multivariate linear congruence equations and a special lattice is constructed. And then by the lattice reduction algorithms such as LLL algorithm, the small roots of multivariate linear congruence equations can be obtained with a high probability. Based on the above technology, this paper proposes a lattice attack method on RSA for discrete private key bit leakage. With this method, if the public parameter satisfies e=Nβ≤N1/2 and the unkno wn part of private key d satisfies Nα≤N1/2-β, it can recover the private key d with a high probability. The experiment on 1 024 bit number is given with NTL package and the results verify the availability of the attack method.%RSA 算法是目前应用最广泛的公钥密码体制之一，而格攻击是针对RSA体制的一类重要攻击方法。
Partial Key Exposure Attacks on RSA up toFull Size ExponentsMatthias Ernst1,Ellen Jochemsz2⋆,Alexander May1⋆,and Benne de Weger2⋆1Faculty of Computer Science,Electrical Engineering and Mathematics,University of Paderborn,33102Paderborn,Germany{alder,alexx}@uni-paderborn.de2Department of Mathematics and Computer Science,Eindhoven University of Technology,Eindhoven,The Netherlands{e.jochemsz,b.m.m.d.weger}@tue.nlAbstract.We present several attacks on RSA that factor the modulusin polynomial time under the condition that a fraction of the most sig-nificant bits or least significant bits of the private exponent is availableto the attacker.Our new attacks on RSA are thefirst attacks of thistype that work up to full size public or private exponent.Keywords:RSA,cryptanalysis,partial key exposure,lattice reduction,Coppersmith’s method.1IntroductionThere have been a number of attacks on RSA given a portion of the private key. These attacks are so-called partial key exposure attacks,where an attacker has some knowledge of the bits of the private key and uses it to break the system. The results are of practical interest,since implementations may leak bits of the private key,e.g.via side channel attacks.In1998,Boneh,Durfee and Frankel presented several partial key exposure attacks on RSA in[2].Some of these attacks require knowledge of the least significant bits(LSBs)of the private exponent,others of the most significant bits (MSBs).Additionally,in their attacks,the public exponent must be relatively small.Wiener’s attack[12]and the improvement by Boneh and Durfee[1]can be seen as partial key exposure attacks where the most significant bits of the private exponent are known to be equal to zero.In[2]the question is posed whether there exist partial key exposure attacks on RSA that work for public exponents larger than the square root of the modulus. In2003,Bl¨o mer and May[3]described a number of attacks that do allow largerpublic exponents,but not yet to the full size of the modulus.In this paper we present attacks for full size public exponent that work up to full size private exponent.Additionally,we present a new attack for full size private exponent that works up to full size public exponent.Our attacks use Coppersmith’s ideas offinding small roots of polynomials [4].We look at variations on the RSA key equation over the integers,using Coppersmith’s method offinding small integer roots,reformulated by Coron[5].Our new results on known MSBs of d for small private exponent d and full size public exponent e are summarized in the following theorem.Theorem1(MSB small d).Under a common heuristic assumption concern-ing resultants,for everyǫ>0,there exists n0such that for every n>n0,the following holds:Let N=pq be an n-bit RSA-modulus,and p,q primes of bitsize n6−11+6β−ǫ(Section4.1.1),or–δ≤316(Section4.1.2),or–δ≤13β−14β2+2β−2−ǫandβ≥112,N].Our result is stated in the theorem below.Theorem2(MSB small e).Under a common heuristic assumption concern-ing resultants,for everyǫ>0,there exists n0such that for every n>n0,the following holds:Let N=pq be an n-bit RSA-modulus,and p,q primes of bitsize n2<α<1.Let e,d satisfy ed≡1modφ(N),such that bitsize(d)=n andbitsize(e)=αn.Given the(1−δ)n MSBs of d,N can be factored in polynomial time if:–δ≤13α−14α2+2α−2−ǫ(Section4.2).In Fig.1and2we illustrate our results on known MSBs of d.In Fig.1,the fraction of bits required for an attack is plotted as a function of the size of d.It shows the parts of the key space that are insecure by the attacks in Section4.1, and by the results of[12]and[1].Fig.2is a picture of the relation between the fraction of bits of d required for an attack and the size of e,showing the results of[2],[3],and Section4.2.Note that our attacks for known MSBs have natural starting and ending points.One MSB attack on small d coincides with the bound d≤N0.284from [1],the other runs up to the situation where d is of full size and is fully known. This links our results to that of May[9],proving a deterministic polynomial time equivalence between factoring and full knowledge of d.Our MSB attack on small e is a natural extension of the results of[2]and[3].Β log N d Β ∆ Β fraction ofd that is Fig.1.MSB attacks for small d 1Α log N e∆ fraction of d that Fig.2.MSB attacks for small eOur new result on known LSBs for relatively small d and full size e is as follows.Theorem 3(LSB small d ).Under a common heuristic assumption concern-ing resultants,for every ǫ>0,there exists n 0such that for every n >n 0,the following holds:Let N =pq be an n -bit RSA-modulus,and p ,q primes of bitsize n6−11+6β−ǫ(Section 4.3).Fig.3illustrates our result on known LSBs.The fraction of bits required for an attack is plotted as a function of the size of d .Fig.4is a picture of the relation between the fraction of bits required for an attack,and the size of e ,showing the work of [2]and [3].Analysis of our LSB method in the case where e is small results in a bound equivalent to thebest result of [3].Β log N d Β ∆Β fraction ofd that is Fig.3.LSB attacks for small d 1Α log N e∆ fraction d that Fig.4.LSB attacks for small eAgain,notice that the starting point of our new LSB attack for small d coincides with the bound d≤N0.284from[1].The bounds of Section4.1.1and4.3show a symmetry in the outcomes of the MSB and LSB situations for small d.Likewise,the bound of Section4.2and the second bound of Section4.1.2show a symmetry in the outcomes of the MSB cases for small d and small e.This is a result of the general character of our method. Instead of studying only special scenarios,we analyze the underlying polynomials in a general framework,which also makes it possible to study numerous old and new cryptanalytic situations,on which we shall comment in Section4.4.Our results can be viewed as evidence that side channel attacks are even more dangerous to RSA than we already knew.In essence,we show that there exist partial key exposure attacks up to full size exponents,hence if either e or d is chosen to be significantly smaller thanφ(N),the system is vulnerable to this type of attacks.This can be understood as a warning to crypto-designers to choose both private and public exponent at random,or take sufficient countermeasures to prevent private key bits from leaking.This paper is organized as follows.In Section2,we describe the typical RSA setting and show how we derive polynomials with small roots from the RSA key equation when MSBs or LSBs of the private exponent d are known.In Section3,we give an overview of the tools we use tofind the small roots of these polynomials.In Section4we give the description of our attacks,proving the results of Theorem1,2,and3.In Section5,experimental results are provided. 2Looking at the RSA Key EquationLet p,q,N,d,e be as usual,i.e.p and q are distinct primes,N=pq is taken as modulus,and the encryption exponent e and decryption exponent d satisfy ed≡1modφ(N).For all of the attacks in this paper,we assume that p and q√have the same bitsize,thus p+q<3<d.φ(N)When MSBs of d are known,we write d=˜d+d0,where˜d(representing the most significant bits of d)is known to the attacker,but d0(representing the least significant bits of d)is not.To make this precise,letβandδbe parameters such that d≤Nβ,and|d0|=|d−˜d|≤Nδ.For the MSB case,we can thus rewrite the RSA key equation intoe(˜d+d0)−1=k(N−(p+q−1)).Hence,the polynomialf MSB1(x,y,z)=ex−Ny+yz+R,where R=e˜d−1,has a root(x0,y0,z0)=(d0,k,p+q−1).Let X:=Nδ,Y:=Nβ,and Z:=3N1as an approximation to k,and setNk0=k−˜k as the unknown part of k.It can be shown(as was done in[3]) that|k0|<e2),so in our case we have|k0|<4Nγ,whereγ= max{δ,β−12,we have|x0|<X,|y0|<Y,and|z0|<Z.When LSBs of d are known,the attacker knows¯d≡d mod M for some M, and we write d=¯d+d1M,where¯d and M are known,and d1is not.We assume that d≤Nβ,and d1≤Nδ.We have no approximation of k in this case,so we rewrite the RSA key equation ase(d1M+¯d)−1=k(N−(p+q−1)).Thus,f LSB(x,y,z)=eMx−Ny+yz+R,with R=e¯d−1,has a root(x0,y0,z0)=(d1,k,p+q−1).Using X:=Nδ,Y:=Nβ,and Z:=3N1√Howgrave-Graham’s lemma is usually combined with LLL reduction of lat-tice bases[7].Fact1(LLL).Let L be a lattice of dimensionω.In polynomial time,the LLL-algorithm outputs two reduced basis vectors v1and v2,that satisfy||v1||≤||v2||≤2ωω−1.Thus,the condition2ωω−1<nωimplies that polynomials correspondingto the two shortest reduced basis vectors match Howgrave-Graham’s bound.This condition reduces to det(L)≤(2−ω√6−11+6β−ǫ.Recalling the situation where we do not use an approximation of k,we want to find a small root(x0,y0,z0)of the polynomial f MSB1(x,y,z)=ex−Ny+yz+R.Ourfirst observation is that f MSB1is irreducible over the integers.Thus, if we could construct two polynomials f1,f2with the same root(x0,y0,z0) which are not multiples of f MSB1,then they do not share a common divisor with f MSB1.Hence,the polynomials p1(y,z)=Res x(f MSB1,f1)and p2(y,z)= Res x(f MSB1,f2)cannot be the zero polynomials.Under the heuristic that the resultant Res y(p1,p2)does not vanish,we obtain z0=p+q−1from a lin-ear factor(z−z0)in Res y(p1,p2),which gives us the factorization of N.All attacks in this paper have a similar heuristic concerning resultants,common in cryptanalysis using multivariate polynomials.Therefore we will use the following assumption.Assumption1.The resultant computations for the polynomials in this paper yield non-zero polynomials.We will comment on how this assumption holds in practice in Appendix D, where we also provide experimental results.Now let usfind conditions under which we can construct f1and f2as defined above.Let X,Y,Z be upper bounds for x0,y0,z0,respectively.Wefix an integer m depending on1√whereρis the maximum degree of the polynomials h and f MSB1in each variable separately.If we let terms that do not depend on n contribute toǫ,wefind that a linear combination with norm smaller than n cannot be a multiple of f MSB1, and must satisfy Howgrave-Graham’s bound.We build a lattice L using as a basis the coefficient vectors of g ijk(xX,yY,zZ), h ijk(xX,yY,zZ),g′ijk(xX,yY,zZ)and h′ijk(xX,yY,zZ).We order the vectors such that the matrix is triangular,and the diagonal entries of g and h are equal to(XY)m Z m+t.For m=t=1,after dividing out XY Z2for simplicity,the coefficient matrix is the following(the rows correspond to the coefficient vectors of h,g,h′,and g′,respectively).z xz yz21x y yz x2z xyz2y2z3x2xy y2y2z xyz y2z2↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓1aX cY Z bYaX cY Z bY 11aX bY cY ZaX bY cY Z1bY aX cY ZW X2ZW Y2Z3W X2W Y2W XY Z2and W=max{eX,NY,Y Z,R}≥NY=N1+β.Wefind an optimal valueτ=16−11+6β.Thereby,we have derived thefirst result of Theorem1.4.1.2Attack using f2We will now show how to obtain the second and third result mentioned in Theorem1,namely that we have a polynomial time MSB attack wheneverδ≤316,orδ≤13β−14β2+2β−2−ǫandβ≥11Wefix an integer m depending on12},and Z=3N12−δ−γ3γ+1316,valid forβ≤112,we getδ≤13β−14β2+2β−2,valid forβ≥113+132.We can again use f MSB 1(x,y,z )=ex −Ny +yz +R ,now with |d 0|<X =N δ,|k |<Y =N αand |p +q −1|<Z =3N 16−11+6α.This result only holds for α>12,from [2,Theorem 4.1],we can assume that k is known,and the polynomial to be analyzed becomes bivariate.Since our attack using f MSB 1obtains a worse bound than the one using f MSB 2,it is not mentioned in Theorem 2.When we use partial information on k ,where k is partly unknown (so α>12},and |p +q −1|<Z =3N 13γ+132),we obtain the condition δ<3+4α−4α22,δ<3+4α−4α22,so we getno result.If γ=α−13+13√6−11+6β−ǫ.The polynomial f LSB (x,y,z )=eMx −Ny +yz +R ,where R =e ¯d −1,has the same monomials as f MSB 1.So we can directly apply the analysis of Section 4.1.1.We use X 1+3τY 2+3τZ 1+3τ+3τ2≤W 1+3τ,on X =N δ,Y =N β,Z =3N 16−11+6β,which concludes the proof of Theorem 3.If we adapt the LSB attack for the situation when e is not of full size,we get exactly the result from Bl¨o mer and May in [3,Section 6].4.4Other Applications of the General Method We have already mentioned that the analysis of the approaches using f MSB 1and f MSB 2is general,in the sense that for every irreducible polynomial with the monomials 1,x,y,yz ,the inequality X 1+3τY 2+3τZ 1+3τ+3τ2≤W 1+3τdefines the condition for a successful (heuristic)attack.Also,for every irreducible poly-nomial with the monomials 1,x,y,yz,z ,the condition X 2+3τY 3+6τ+3τ2Z 3+3τ≤W 2+3τimplies a successful (heuristic)attack.As a consequence,many known attacks on RSA are special cases of our general framework.As could be seen in Fig.1,and 3,one MSB attack and one LSB attacks for small d coincide with the bound d <N 0.284from [1].This result can also be found using our method by noticing that f BD (x,y,z )=ex −Ny +yz −1with the root(x0,y0,z0)=(d,k,p+q−1)has the same monomials as f MSB1.Therefore,we can substitute X,Y=Nβ,Z=3N16−17≈0.284.To get the improved Boneh-Durfee bound one has to use sublattices.We leave thisfor further research.Fig.1also shows that the graph of our(asymptotic)attack of Section4.1.2goes up toβ−δhours to reduce.4We performed the MSB2attack on small e forα=0.7,δ=0.08(e.g.8%of d is unknown),using m=2,t=2.The reduction of the50-dimensional lattice took23References1.Dan Boneh and Glenn Durfee:Cryptanalysis of RSA with Private Key d LessThan N0.292,IEEE Transactions on Information Theory46[2000],1339–1349.2.Dan Boneh,Glenn Durfee and Yair Frankel:An Attack on RSA given a SmallFraction of the Private Key Bits,Proceedings of ASIACRYPT1998,LNCS1514[1998],25–34.3.Johannes Bl¨o mer and Alexander May:New Partial Key Exposure Attacks onRSA,Proceedings of CRYPTO2003,LNCS2729[2003],27–43.4.Don Coppersmith:Small Solutions to Polynomial Equations and Low Expo-nent RSA Vulnerabilities,Journal of Cryptology10[1997],233–260.5.Jean-S´e bastien Coron:Finding Small Roots of Bivariate Integer EquationsRevisited,Proceedings of EUROCRYPT2004,LNCS3027[2004],492–505.6.Nick Howgrave-Graham:Finding Small Roots of Univariate Modular Equa-tions Revisited,Cryptography and Coding,LNCS1355[1997],131–142.7.Arjen Lenstra,Hendrik Lenstra,Jr.,and L´a szl´o Lov´a sz:Factoring Polynomialswith Rational Coefficients,Mathematische Ann.261[1982],513–534.8.Alexander May:Cryptanalysis of Unbalanced RSA with Small CRT-Exponent,Proceedings of CRYPTO2002,LNCS2442[2002],242–256.9.Alexander May:Computing the RSA Secret Key is Deterministic PolynomialTime Equivalent to Factoring,Proceedings of CRYPTO2004,LNCS3152[2004],213–219.10.Victor Shoup:NTL:A Library for doing Number Theory,online available at/ntl11.Benne de Weger:Cryptanalysis of RSA with Small Prime Difference,Ap-plicable Algebra in Engineering,Communication and Computing13[2002],17–28.12.Michael Wiener:Cryptanalysis of Short RSA Secret Exponents,IEEE Trans-actions on Information Theory36[1990],553–558.A The bound X1+3Y2+3Z1+3+32≤W1+3In this appendix,we show how to obtain the bound X1+3τY2+3τZ1+3τ+3τ2≤W1+3τfor the attack using f MSB1(Section4.1.1).In Section4.1.1,we described how to construct the lattice.The matrix con-taining the basis vectors is triangular and has the following diagonal entries (corresponding to the polynomials g,h,g′and h′,respectively):X m Y m Z m+t for i=0,...,m;j=0,...,m−i;k=0,...,jX m Y m Z m+t for i=0,...,m;j=0,...,m−i;k=j+1,...,j+tX m+i Y m+j Z m+t+k W for i=0,...,m+1;j=m+1−i;k=0,...,jX m+i Y m+j Z m+t+k W for i=0,...,m+1;j=m+1−i;k=j+1,...,j+t Since we have to optimize t in terms of m,we put t=τm.Elementary compu-tations show that the dimension of L is1ω=and thatdet(L)=X16(m4(1+3τ)+m3(11+18τ)+o(m3))·Z16(m2(3+6τ)+o(m2)).When we apply LLL-reduction to our lattice,the polynomials f1(x,y,z)and f2(x,y,z)corresponding to the shortest two vectors in the reduced basis sat-isfy f1(x0,y0,z0)≡0mod n and f2(x0,y0,z0)≡0mod n.In order to apply Howgrave-Graham’s lemma,we explained in Section3thatdet(L)≤(2−ω√(m3(2+3τ)+m2(15+15τ))+o(m2),6and the determinant of L is equal toX16(m4(2+5τ+3τ2)+m3(18+36τ+18τ2)+o(m3))·Z16(m2(6+6τ)+o(m2)).When we apply LLL-reduction to our lattice,the polynomials f1(x,y,z)and f2(x,y,z)corresponding to the shortest two vectors in the reduced basis sat-isfy f1(x0,y0,z0)≡0mod n and f2(x0,y0,z0)≡0mod n.In order to apply Howgrave-Graham’s Lemma,it must hold thatdet(L)≤(2−ω√N≤N2β−1N−z)−1has the same monomials as, f MSB1.When we substitute X,Y=Nδ,Z=N2β−14 we have W=N1+δ.Using X1+3τY2+3τZ1+3τ+3τ2≤W1+3τ,we getδ≤13(β+32.As the function has the same monomials as f MSB1,one can use the same inequality to conclude that the attack works forδ<53√2}=δ+κ,we obtain the boundδ≤3−4κ−4κ216+16κ.In the caseγ=β−13+1316+16κ.Naturally,equivalent bounds can be derived when d is full size and e is not.D More Experimental ResultsIn addition to Section5,we now show more experimental results.The experi-ments we did for this appendix are only for m=1and m=2,which means the lattices are relatively small and the lattice reduction can be performed in a matter of seconds or minutes.In the full version of this paper,experiments for larger parameters will be included.As in Section5,the experiments are performed on a server containing two Pentium III processors of1000Mhz,and all the lattice basis reductions are done using Shoup’s NTL[10].In contrast to the experimental results mentioned in Section5,we assume here that we have a256bit modulus.So one has to keep in mind that for N≈21024,the running time of the LLL-procedure will be longer.As the bounds onδstated in Theorem1and2are asymptotic bounds,the goal of the tables in this appendix is to provide some intuition of what bounds onδour attacks can achieve in practice.For example,the table in Fig.5shows that forβ=0.3,the asymptotic bound of the attack using f MSB1from Section 4.1.1isδ<0.28−ǫ.When we use the parameters m=2,t=1,our attack works forδ<0.21.The attack involves a lattice of dimension30,which takes approximately25seconds to reduce.This example is one of the three so-called’typical cases’of Section5.These are examples where the bound onδthat we obtain in practice exceeds the asymptotic bounds of other known attacks.In the tables in this appendix,the typical cases are written in bold.For the choice of t,recall from Section4.1.1that t=τm,and that we use τ=12−δ−γ2,using a larger t givesa better bound onδin the experiments(as can be seen in Fig.7).βm=1asympt.t=1t=0t=20.280.190.190.210.250.140.140.160.220.110.090.150.190.100.050.120.170.0800.110.140.0800.110.120.0400.100.10000.060.07000.010.050000.030000.01000102230LLL(sec):23100 Fig.5.Experiments f MSB1for small dβm=1asympt.t=1t=3t=10.300.190.200.190.190.190.160.160.160.400.120.120.140.150.190.110.120.130.500.080.120.120.130.190.110.120.130.600.050.110.110.130.190.050.060.080.700000.050.140000.8000000.080000.9000000.03000Dimension:203240LLL(sec):740180δm=2t=0t=2t=0t=20.500.330.400.370.550.170.230.210.240.270.140.180.160.650.020.100.070.130.180.020.040.040.750000.020.110000.8500000.050000.9500001426305011333520Fig.7.Experiments f MSB2for small eHaving done some experiments,we can now comment on Assumption1.Let g(x,y,z)and h(x,y,z)be polynomials that correspond to LLL-reduced vectors in our method,for which Howgrave-Graham’s bound is satisfied.If g(x0,y0,z0)= h(x0,y0,z0)=0,but the resultant computations with g and h yield the zero-polynomial,then Assumption1does not hold.Therefore,we performed some tests to see how often this occurs.We found that for approximately0.1%of pairs (g,h)the heuristic failed.This does not mean that the method will always fail in these ually,there are several vectors that satisfy Howgrave-Graham’s bound,hence if one pair fails,other pairs can yield the solution.Experiments also show that the theoretical bound under which our methods works,det(L)≤(2−ω√41ω)ω−1,when it is known that LLL-reductionachieves much better bounds in practice,and to the fact that we use the LLL-bound for the second smallest reduced vector.In practice,we experienced that our method works until we come close to det(L)≤nω(the bound for thefirst reduced vector to be small enough,omitting the constant term).。
