p = getPrime(5120) q = getPrime(5120) n = 1392208858696945158251408085300402884210409327605255122395601049457847957306648819174395014931778575812308192875319127224095733396726388842605854427013313599830150182564652493067830031524869535522568868597852507293377043240832819715539722122306829543983051745406887140154364256267942350230636870212935356815475345989038318923389132101208917912083817520799490534351545373438629367819085151041702754019127891155542476560972125790519584018715794669416759039955180436830478697704458250990786586357019211642837879273967620287257818400267757312623543898635740200839249361087580046496969637043238450499583879116276661827372750638403042213043389905183760455450595752578482968202040860053524276678108325784161897719093223308370971388068813420487879756084379519128232693549989942550047529174783976176943482484756074638704076740157397067892580297182979526978967352014250386678155843772313996171396582929433057131989693861316408604436872931427368192437680361830753162284661119995125858203931094922686321756465463988790748131178263745308042820480140189644732824717255521633534750635979508673908361269979175726073254050574688259969290376926807033728165164896588540691889207252105903436659968119091774687841336252628343233161941187968365128093917171537997137001140227677728923114895809278926486615010954871408034272872411042537353956193868948909981683850857262457369506288525323882308421700421661036191853577105238753230479541719001794464585534292774768292358961920606891227776349593589481547577148801600196035588544512224775960892265021565124673788852875005526313525709353599584812394138968970647681759439523307392275602626903789154682706839530654070108096741181206975334567778238856983205004289416400671597321919876279909765650782227834097342294844294386380646928266942749144240020420237153276705785759403019072953506982997681174635673907151856644499332322321579088035719680421458310273802481031746012298208449699089203065699598926690947025679591160106357130634946357609420125223580319677387654711233585375013067828291928349946599077331636017784447090096340360087970540477975170379810969501197027775838769222713506443846417124839450184827707739588007707714623211453528342755023849716924694572679150284882978804641986457119009272574734697043321033091757474387114449914271460113979531460465175717705674905568446670579332667139075523255580471183372714211547822093365025438653384719374474230360983878837077517864405475258349436531094649276628214288499716485354283135575921258757214288792410583835467572916298688718758374714560819702413058421373661892101033513816116981698045524150518509405086125781764762145577981637953775680403132163846782252745029783387112660812179706752454175492501665442704630131729362621965258498471247871904163412798544329515689112368523703890083138721480476796720323855371775568097188216621368341228806795058046403892301673157631331636430392885315997250027372621883549649614866115616619234953579196607399899485002042456482969222428121605212017146571466818179341621066715472184636758016242256725063854155219754299817717414423725704356940589670902509021070871847017199593680033 e = 97 phi = (p-1)*(q-1) c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125
由
\[
c \equiv m^e \pmod{N}
\]
\[
当m^e很小时,对N取模后并不会丢失信息,相当于c =m^e
\]
1 2 3 4 5 6 7 8 9 10 11 12
from Crypto.Util.number import long_to_bytes from gmpy2 import iroot
def small_msg_rsa(N, e, c): m, exact = iroot(c, e) return long_to_bytes(int(m)) if exact and pow(int(m), e) < N else None
N = e = c = print(small_msg_rsa(N, e, c))
3.低加密指数攻击
一般e=3
1 2 3 4 5
n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793 e: 0x3 c: 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365 #so,how to get the message?
from gmpy2 import * from Crypto.Util.number import * import math n = e = c =
k = 0 whileTrue: # 计算一个候选值 flag = k * n + c # 检查这个候选值是否是一个完美的e次方 if iroot(flag, e)[1]: # 如果是,就计算它的e次方根 m = iroot(flag, e)[0] print(long_to_bytes(m)) break k += 1
4.共模攻击
特征:
同一个模数 N
同一个明文 m
两个不同指数 e1, e2(互质)
\[
已知𝑐1=𝑚^{e1} mod𝑁,𝑐2=𝑚^{e2} mod𝑁
\]
攻击思路:
求 egcd(e1,e2)=1的扩展欧几里得系数:
\[
a e_1 + b e_2 = 1
\]
根据:
\[
m = m^{a e_1 + b e_2}
= m^{a e_1} \cdot m^{b e_2}
\equiv c_1^a \cdot c_2^b \pmod{N}
\]
from Crypto.Util.number import getPrime from binascii import hexlify from hashlib import md5 from random import choices from string import hexdigits import gmpy2 from flag import flag
inv_p = gmpy2.invert(p, q) inv_q = gmpy2.invert(q, p) mp = pow(c, (p + 1) // 4, p) mq = pow(c, (q + 1) // 4, q) a = (inv_p * p * mq + inv_q * q * mp) % n b = n - int(a) c = (inv_p * p * mq - inv_q * q * mp) % n d = n - int(c) aa = [a, b, c, d]
for i in aa: print(i)
print(libnum.n2s(int(i)))
8.dp泄露
1.e较小
已知N, e, dp, c
\[
dp=dmod(p-1)
\]
把RSA的加密步骤拆开来看
RSA 私钥 d 满足:
\[
e d \equiv 1 \pmod{\varphi(N)}
\]
对于素数 p、q,有:
\[
\varphi(N) = (p-1)(q-1)
\]
所以必然也有:
\[
ed \equiv 1 \pmod{p-1}
\]
根据Dp的定义,意味着一定存在整数Kp,使得下式成立:
\[
d =dp+kp(p-1)
\]
将此式代入得
\[
e d_p - 1 = k_p (p-1)
\]
这里 Kp, Kq是某些正整数,最后化简得
\[
p=\frac{ed_p-1}{K_p}+1
\]
接下来便是对k的枚举
1 2 3 4
n =156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847 dp =734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825 c =108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869 e =65537
import gmpy2 from Crypto.Util.number import * n = dp= c = e = tmp = e * dp -1 #根据联立条件有: e*dp = 1 + k(p-1),故求解p的式子为:(p-1) = (e*dp-1) / k for k inrange(1, e):#因为K上限只到e,故遍历求解 if tmp % k == 0:#验证(p-1)是否为整除结果 p = (tmp // k) + 1 if n % p == 0:#验证p能否被n整除 q = n // p if gmpy2.is_prime(p) and gmpy2.is_prime(q):#验证求解的p, q是否为素数 # print(k) print("N的分解结果为 : ") print("%d = %d * %d" % (n, p, q)) break phi = (p-1)*(q-1) d=gmpy2.invert(e,phi) m=gmpy2.powmod(c,d,n) print(long_to_bytes(m))
''' n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069 e = 305691242207901867366357529364270390903 c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661 dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513 '''
当e比较大时,我们构造p的倍数,再用gcd分解n
无论 e 多大,只要知道 dp,就有:
\[
e⋅dp \equiv 1 \mod(p-1)⇒e⋅dp=1+k(p−1)
\]
对任意整数 a mod p != 0,由 Fermat 小定理:
\[
a
^{p−1}
≡1(modp)⇒a^
{e⋅dp}
=a ^{
1+k(p−1)}
≡a⋅(a^{
p−1}
) ^
k
≡a(modp)
\]
for a inrange(2, 10): # 关键一步:计算 a^(e * dp) mod n x = pow(a, e * dp, n) p = math.gcd(x - a, n) if1 < p < n: print(f"[+] p = {p}") q = n // p d = inverse(e, (p-1)*(q-1)) m = pow(c, d, n) flag = long_to_bytes(m) print(flag) break
from Crypto.Util.number import long_to_bytes import gmpy2 N = c = e= a = 2 n = 2 whileTrue: a = pow(a, n, N) res = gmpy2.gcd(a-1, N) if res != 1and res != N: q = N // res print("n=",n) print("p=",res) print("q=",q) break n += 1 d=gmpy2.invert(e,(res-1)*(q-1)) m=pow(c,d,N) print(long_to_bytes(m))
from math import isqrt from gmpy2 import gcd from Cryptodome.Util.number import long_to_bytes from itertools import count from sympy import primerange # 示例已知参数,待分解的n n = # Lucas 序列(Williams p+1 用的) defmlucas(v, a, n): v1, v2 = v, (v ** 2 - 2) % n for bit inbin(a)[3:]: if bit == "0": v1, v2 = (v1 ** 2 - 2) % n, (v1 * v2 - v) % n else: v1, v2 = (v1 * v2 - v) % n, (v2 ** 2 - 2) % n return v1 # 素数生成器 defprimegen(): yieldfrom primerange(2, 10**6) # 生成到 10^6 的素数,够用了 # 整数对数:ilog(x, b) = 最大整数 l,使得 b^l <= x defilog(x, b): l = 0 while x >= b: x //= b l += 1 return l # Williams p+1 分解攻击 defattack(n): for v in count(1): # 不断尝试新的 v for p in primegen(): e = ilog(isqrt(n), p) if e == 0: break for _ inrange(e): v = mlucas(v, p, n) g = gcd(v - 2, n) if1 < g < n: returnint(g), int(n // g) if g == n: break # 开始攻击 p1, q1 = attack(n) print(f"p = {p1}") print(f"q = {q1}")
defcontinued_fraction(n, d): """生成连分数""" cf = [] while d: q = n // d cf.append(q) n, d = d, n - q * d return cf
defconvergents(cf): """由连分数生成收敛项 k/d""" convs = [] for i inrange(len(cf)): num, den = 1, 0 for q inreversed(cf[:i+1]): num, den = den + num * q, num convs.append((num, den)) return convs
defwiener_attack(e, n): cf = continued_fraction(e, n) for k, d in convergents(cf): if k == 0: continue
# ed ≡ 1 (mod φ(n)) if (e * d - 1) % k != 0: continue
phi = (e * d - 1) // k s = n - phi + 1# p + q delta = s * s - 4 * n
if delta < 0: continue
t = isqrt(delta) if t * t == delta: p = (s + t) // 2 q = (s - t) // 2 if p * q == n: return d, p, q
returnNone
if __name__ == "__main__": e = n =
res = wiener_attack(e, n) if res: d, p, q = res print("[+] Wiener Attack Success!") print("d =", d) print("p =", p) print("q =", q) else: print("[-] Attack Failed")
""" Setting debug to true will display more informations about the lattice, the bounds, the vectors... """ debug = True
""" Setting strict to true will stop the algorithm (and return (-1, -1)) if we don't have a correct upperbound on the determinant. Note that this doesn't necesseraly mean that no solutions will be found since the theoretical upperbound is usualy far away from actual results. That is why you should probably use `strict = False` """ strict = False
""" This is experimental, but has provided remarkable results so far. It tries to reduce the lattice as much as it can while keeping its efficiency. I see no reason not to use this option, but if things don't work, you should try disabling it """ helpful_only = True dimension_min = 7 # stop removing if lattice reaches that dimension
# display stats on helpful vectors def helpful_vectors(BB, modulus): nothelpful = 0 for ii in range(BB.dimensions()[0]): if BB[ii,ii] >= modulus: nothelpful += 1
print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# display matrix picture with 0 and X def matrix_overview(BB, bound): for ii in range(BB.dimensions()[0]): a = ('%02d ' % ii) for jj in range(BB.dimensions()[1]): a += '0' if BB[ii,jj] == 0 else 'X' if BB.dimensions()[0] < 60: a += ' ' if BB[ii, ii] >= bound: a += '~' print(a)
# tries to remove unhelpful vectors # we start at current = n-1 (last vector) def remove_unhelpful(BB, monomials, bound, current): # end of our recursive function if current == -1 or BB.dimensions()[0] <= dimension_min: return BB
# we start by checking from the end for ii in range(current, -1, -1): # if it is unhelpful: if BB[ii, ii] >= bound: affected_vectors = 0 affected_vector_index = 0 # let's check if it affects other vectors for jj in range(ii + 1, BB.dimensions()[0]): # if another vector is affected: # we increase the count if BB[jj, ii] != 0: affected_vectors += 1 affected_vector_index = jj
# level:0 # if no other vectors end up affected # we remove it if affected_vectors == 0: print("* removing unhelpful vector", ii) BB = BB.delete_columns([ii]) BB = BB.delete_rows([ii]) monomials.pop(ii) BB = remove_unhelpful(BB, monomials, bound, ii-1) return BB
# level:1 # if just one was affected we check # if it is affecting someone else elif affected_vectors == 1: affected_deeper = True for kk in range(affected_vector_index + 1, BB.dimensions()[0]): # if it is affecting even one vector # we give up on this one if BB[kk, affected_vector_index] != 0: affected_deeper = False # remove both it if no other vector was affected and # this helpful vector is not helpful enough # compared to our unhelpful one if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]): print("* removing unhelpful vectors", ii, "and", affected_vector_index) BB = BB.delete_columns([affected_vector_index, ii]) BB = BB.delete_rows([affected_vector_index, ii]) monomials.pop(affected_vector_index) monomials.pop(ii) BB = remove_unhelpful(BB, monomials, bound, ii-1) return BB # nothing happened return BB
""" Returns: * 0,0 if it fails * -1,-1 if `strict=true`, and determinant doesn't bound * x0,y0 the solutions of `pol` """ def boneh_durfee(pol, modulus, mm, tt, XX, YY): """ Boneh and Durfee revisited by Herrmann and May finds a solution if: * d < N^delta * |x| < e^delta * |y| < e^0.5 whenever delta < 1 - sqrt(2)/2 ~ 0.292 """
# x-shifts gg = [] for kk in range(mm + 1): for ii in range(mm - kk + 1): xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk gg.append(xshift) gg.sort()
# x-shifts list of monomials monomials = [] for polynomial in gg: for monomial in polynomial.monomials(): if monomial not in monomials: monomials.append(monomial) monomials.sort() # y-shifts (selected by Herrman and May) for jj in range(1, tt + 1): for kk in range(floor(mm/tt) * jj, mm + 1): yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk) yshift = Q(yshift).lift() gg.append(yshift) # substitution # y-shifts list of monomials for jj in range(1, tt + 1): for kk in range(floor(mm/tt) * jj, mm + 1): monomials.append(u^kk * y^jj)
# construct lattice B nn = len(monomials) BB = Matrix(ZZ, nn) for ii in range(nn): BB[ii, 0] = gg[ii](0, 0, 0) for jj in range(1, ii + 1): if monomials[jj] in gg[ii].monomials(): BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
# Prototype to reduce the lattice if helpful_only: # automatically remove BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1) # reset dimension nn = BB.dimensions()[0] if nn == 0: print("failure") return 0,0
# check if vectors are helpful if debug: helpful_vectors(BB, modulus^mm) # check if determinant is correctly bounded det = BB.det() bound = modulus^(mm*nn) if det >= bound: print("We do not have det < bound. Solutions might not be found.") print("Try with highers m and t.") if debug: diff = (log(det) - log(bound)) / log(2) print("size det(L) - size e^(m*n) = ", floor(diff)) if strict: return -1, -1 else: print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
# display the lattice basis if debug: matrix_overview(BB, modulus^mm)
# LLL if debug: print("optimizing basis of the lattice via LLL, this can take a long time")
BB = BB.LLL()
if debug: print("LLL is done!")
# transform vector i & j -> polynomials 1 & 2 if debug: print("looking for independent vectors in the lattice") found_polynomials = False for pol1_idx in range(nn - 1): for pol2_idx in range(pol1_idx + 1, nn): # for i and j, create the two polynomials PR.<w,z> = PolynomialRing(ZZ) pol1 = pol2 = 0 for jj in range(nn): pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY) pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
# are these good polynomials? if rr.is_zero() or rr.monomials() == [1]: continue else: print("found them, using vectors", pol1_idx, "and", pol2_idx) found_polynomials = True break if found_polynomials: break
if not found_polynomials: print("no independant vectors could be found. This should very rarely happen...") return 0, 0 rr = rr(q, q)
# solutions soly = rr.roots()
if len(soly) == 0: print("Your prediction (delta) is too small") return 0, 0
soly = soly[0][0] ss = pol1(q, soly) solx = ss.roots()[0][0]
# return solx, soly
def example(): ############################################ # How To Use This Script ##########################################
# # The problem to solve (edit the following values) #
# the modulus N = # the public exponent e =
# the hypothesis on the private exponent (the theoretical maximum is 0.292) delta = .18 # this means that d < N^delta
# # Lattice (tweak those values) #
# you should tweak this (after a first run), (e.g. increment it until a solution is found) m = 4 # size of the lattice (bigger the better/slower)
# you need to be a lattice master to tweak these t = int((1-2*delta) * m) # optimization from Herrmann and May X = 2*floor(N^delta) # this _might_ be too much Y = floor(N^(1/2)) # correct if p, q are ~ same size
# # Don't touch anything below #
# Problem put in equation P.<x,y> = PolynomialRing(ZZ) A = int((N+1)/2) pol = 1 + x * (A + y)
# # Find the solutions! #
# Checking bounds if debug: print("=== checking values ===") print("* delta:", delta) print("* delta < 0.292", delta < 0.292) print("* size of e:", int(log(e)/log(2))) print("* size of N:", int(log(N)/log(2))) print("* m:", m, ", t:", t)