API tools faq
paste
xdlq

Codes of the manuscript---Practical Attacks on Small Private Exponent RSA---New Records and New Insi

xdlq
Feb 20th, 2023
193
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 34.11 KB | None | 0 0
raw download clone embed print report
  1. #########Code of Table 7#########
  2. #########Code of Table 7#########
  3. #########Code of Table 7#########
  4. #########Code of Table 7#########
  5. import time
  6.  
  7. debug = True
  8.  
  9. strict = False
  10.  
  11.  
  12. helpful_only = True
  13. dimension_min = 7 # 如果晶格达到该尺寸，则停止移除
  14. ############################################
  15. # 函数
  16. ##########################################
  17.  
  18. # 显示有用矢量的统计数据
  19. def helpful_vectors(BB, modulus):
  20. nothelpful = 0
  21. for ii in range(BB.dimensions()[0]):
  22. if BB[ii,ii] >= modulus:
  23. nothelpful += 1
  24.  
  25. print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
  26.  
  27. # 显示带有 0 和 X 的矩阵
  28. def matrix_overview(BB, bound):
  29. for ii in range(BB.dimensions()[0]):
  30. a = ('%02d ' % ii)
  31. for jj in range(BB.dimensions()[1]):
  32. a += '0' if BB[ii,jj] == 0 else 'X'
  33. if BB.dimensions()[0] < 60:
  34. a += ' '
  35. if BB[ii, ii] >= bound:
  36. a += '~'
  37. #print (a)
  38.  
  39. # 尝试删除无用的向量
  40. # 从当前 = n-1（最后一个向量）开始
  41. def remove_unhelpful(BB, monomials, bound, current):
  42. # 我们从当前 = n-1（最后一个向量）开始
  43. if current == -1 or BB.dimensions()[0] <= dimension_min:
  44. return BB
  45.  
  46. # 开始从后面检查
  47. for ii in range(current, -1, -1):
  48. # 如果它没有用
  49. if BB[ii, ii] >= bound:
  50. affected_vectors = 0
  51. affected_vector_index = 0
  52. # 让我们检查它是否影响其他向量
  53. for jj in range(ii + 1, BB.dimensions()[0]):
  54. # 如果另一个向量受到影响：
  55. # 我们增加计数
  56. if BB[jj, ii] != 0:
  57. affected_vectors += 1
  58. affected_vector_index = jj
  59.  
  60. # 等级：0
  61. # 如果没有其他载体最终受到影响
  62. # 我们删除它
  63. if affected_vectors == 0:
  64. print ("* removing unhelpful vector", ii)
  65. BB = BB.delete_columns([ii])
  66. BB = BB.delete_rows([ii])
  67. monomials.pop(ii)
  68. BB = remove_unhelpful(BB, monomials, bound, ii-1)
  69. return BB
  70.  
  71. # 等级：1
  72. #如果只有一个受到影响，我们会检查
  73. # 如果它正在影响别的向量
  74. elif affected_vectors == 1:
  75. affected_deeper = True
  76. for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
  77. # 如果它影响哪怕一个向量
  78. # 我们放弃这个
  79. if BB[kk, affected_vector_index] != 0:
  80. affected_deeper = False
  81. # 如果没有其他向量受到影响，则将其删除，并且
  82. # 这个有用的向量不够有用
  83. #与我们无用的相比
  84. if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
  85. print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
  86. BB = BB.delete_columns([affected_vector_index, ii])
  87. BB = BB.delete_rows([affected_vector_index, ii])
  88. monomials.pop(affected_vector_index)
  89. monomials.pop(ii)
  90. BB = remove_unhelpful(BB, monomials, bound, ii-1)
  91. return BB
  92. # nothing happened
  93. return BB
  94.  
  95. """
  96. Returns:
  97. * 0,0 if it fails
  98. * -1，-1 如果 "strict=true"，并且行列式不受约束
  99. * x0,y0 the solutions of `pol`
  100. """
  101. def boneh_durfee(pol, modulus, mm, tt, XX, YY):
  102. """
  103. Boneh and Durfee revisited by Herrmann and May
  104.  
  105. 在以下情况下找到解决方案：
  106. * d < N^delta
  107. * |x|< e^delta
  108. * |y|< e^0.5
  109. 每当 delta < 1 - sqrt（2）/2 ~ 0.292
  110. """
  111.  
  112. # substitution (Herrman and May)
  113. PR.<u, x, y> = PolynomialRing(ZZ) #多项式环
  114. Q = PR.quotient(x*y + 1 - u) # u = xy + 1
  115. polZ = Q(pol).lift()
  116.  
  117. UU = XX*YY + 1
  118.  
  119. # x-移位
  120. gg = []
  121. for kk in range(mm + 1):
  122. for ii in range(mm - kk + 1):
  123. xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
  124. gg.append(xshift)
  125. gg.sort()
  126.  
  127. # 单项式 x 移位列表
  128. monomials = []
  129. for polynomial in gg:
  130. for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
  131. if monomial not in monomials: # 如果单项不在单项中
  132. monomials.append(monomial)
  133. monomials.sort()
  134.  
  135. # y-移位
  136. for jj in range(1, tt + 1):
  137. for kk in range(floor(mm/tt) * jj, mm + 1):
  138. yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
  139. yshift = Q(yshift).lift()
  140. gg.append(yshift) # substitution
  141.  
  142. # 单项式 y 移位列表
  143. for jj in range(1, tt + 1):
  144. for kk in range(floor(mm/tt) * jj, mm + 1):
  145. monomials.append(u^kk * y^jj)
  146.  
  147. # 构造格 B
  148. nn = len(monomials)
  149. BB = Matrix(ZZ, nn)
  150. for ii in range(nn):
  151. BB[ii, 0] = gg[ii](0, 0, 0)
  152. for jj in range(1, ii + 1):
  153. if monomials[jj] in gg[ii].monomials():
  154. BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
  155.  
  156. #约化格的原型
  157. if helpful_only:
  158. # #自动删除
  159. BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
  160. # 重置维度
  161. nn = BB.dimensions()[0]
  162. print("矩阵维数：",BB.dimensions())
  163. if nn == 0:
  164. print ("failure")
  165. return 0,0
  166.  
  167. # 检查向量是否有帮助
  168. if debug:
  169. helpful_vectors(BB, modulus^mm)
  170.  
  171. # 检查行列式是否正确界定
  172. det = BB.det()
  173. bound = modulus^(mm*nn)
  174. if det >= bound:
  175. print ("We do not have det < bound. Solutions might not be found.")
  176. print ("Try with highers m and t.")
  177. if debug:
  178. diff = (log(det) - log(bound)) / log(2)
  179. print ("size det(L) - size e^(m*n) = ", floor(diff))
  180. if strict:
  181. return -1, -1
  182. else:
  183. print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
  184.  
  185. # display the lattice basis
  186. if debug:
  187. matrix_overview(BB, modulus^mm)
  188.  
  189. # LLL
  190. if debug:
  191. print ("optimizing basis of the lattice via LLL, this can take a long time")
  192.  
  193. #BB = BB.BKZ(block_size=25)
  194. BB = BB.LLL()
  195.  
  196. if debug:
  197. print ("LLL is done!")
  198.  
  199. # 替换向量 i 和 j ->多项式 1 和 2
  200. if debug:
  201. print ("在格中寻找线性无关向量")
  202. found_polynomials = False
  203.  
  204. for pol1_idx in range(nn - 1):
  205. for pol2_idx in range(pol1_idx + 1, nn):
  206.  
  207. # 对于i and j, 构造两个多项式
  208.  
  209. PR.<w,z> = PolynomialRing(ZZ)
  210. pol1 = pol2 = 0
  211. for jj in range(nn):
  212. pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
  213. pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
  214.  
  215. # 结果
  216. PR.<q> = PolynomialRing(ZZ)
  217. rr = pol1.resultant(pol2)
  218.  
  219.  
  220. if rr.is_zero() or rr.monomials() == [1]:
  221. continue
  222. else:
  223. print ("found them, using vectors", pol1_idx, "and", pol2_idx)
  224. found_polynomials = True
  225. break
  226. if found_polynomials:
  227. break
  228.  
  229. if not found_polynomials:
  230. print ("no independant vectors could be found. This should very rarely happen...")
  231. return 0, 0
  232.  
  233. rr = rr(q, q)
  234.  
  235. # solutions
  236. soly = rr.roots()
  237.  
  238. if len(soly) == 0:
  239. print ("Your prediction (delta) is too small")
  240. return 0, 0
  241.  
  242. soly = soly[0][0]
  243. ss = pol1(q, soly)
  244. solx = ss.roots()[0][0]
  245. return solx, soly
  246.  
  247.  
  248. def example():
  249. ############################################
  250. # 随机生成数据
  251. ##########################################
  252. #start_time =time.perf_counter
  253. start =time.clock()
  254. size=512
  255. length_N = 2*size;
  256. ss=0
  257. M=100
  258. delta = 0.292
  259. # p = random_prime(2^512,2^511)
  260. for i in range(M):
  261. p = random_prime(2^size,None,2^(size-1))
  262. q = random_prime(2^size,None,2^(size-1))
  263. if(p<q):
  264. temp=p
  265. p=q
  266. q=temp
  267. N = p*q;
  268. d=floor(N^delta);
  269. for j in range(1000):
  270. d=d-1;
  271. if gcd(d,(p-1)*(q-1))==1:
  272. print('d=',d)
  273. print('N=',N)
  274. print('p=',p)
  275. print('q=',q)
  276. #print("p1=",len(bin(p)))
  277. print("p2=",int(log(p)/log(2))+1)
  278. # print("q1=",len(bin(q)))
  279. print("q2=",int(log(q)/log(2))+1)
  280. e=inverse_mod(d,(p-1)*(q-1))
  281. print('e=',e)
  282.  
  283. # 解密指数d的指数( 最大0.292)
  284.  
  285.  
  286.  
  287. m = 24 # 格大小（越大越好/越慢）
  288. guess=0
  289. # you need to be a lattice master to tweak these
  290. t = round(((1-2*delta) * m)) # 来自 Herrmann 和 May 的优化
  291. X = 2*floor(N^delta) #
  292. Y = floor(N^(1/2)/2^guess) # 如果 p、 q 大小相同，则正确
  293.  
  294.  
  295. P.<x,y> = PolynomialRing(ZZ)
  296. A = N+1
  297. pol = 1 + x * (A + y) #构建的方程
  298.  
  299. # Checking bounds
  300. if debug:
  301. print ("=== 核对数据 ===")
  302. print ("* delta:", delta)
  303. print ("* delta < 0.292", delta < 0.292)
  304. print ("* size of e:", ceil(log(e)/log(2))) # e的bit数
  305. # print ("* size of N:", len(bin(N))) # N的bit数
  306. print ("* size of N:", ceil(log(N)/log(2))) # N的bit数
  307. print ("* m:", m, ", t:", t)
  308.  
  309. # boneh_durfee
  310. if debug:
  311. ##print ("=== running algorithm ===")
  312. start_time = time.time()
  313.  
  314.  
  315. solx, soly = boneh_durfee(pol, e, m, t, X, Y)
  316.  
  317.  
  318. if solx > 0:
  319. print ("=== solution found ===")
  320. if False:
  321. print ("x:", solx)
  322. print ("y:", soly)
  323.  
  324. d = int(pol(solx, soly) / e)
  325. print ("私钥d:", d)
  326. ss=ss+1
  327. else:
  328. print ("=== no solution was found ===")
  329.  
  330. if debug:
  331. print("=== %s seconds ===" % (time.time() - start_time))
  332. break
  333. print("ss=",ss)
  334. #end=time.process_time
  335. end=time.clock()
  336. print('Running time: %s Seconds'%(end-start))
  337. if __name__ == "__main__":
  338. example()
  339. #########Code of Table 7#########
  340. #########Code of Table 7#########
  341. #########Code of Table 7#########
  342. #########Code of Table 7#########
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352. #########Code of Table 8#########
  353. #########Code of Table 8#########
  354. #########Code of Table 8#########
  355. #########Code of Table 8#########
  356.  
  357. import time
  358.  
  359. debug = True
  360.  
  361. strict = False
  362.  
  363.  
  364. helpful_only = True
  365. dimension_min = 7 # 如果晶格达到该尺寸，则停止移除
  366. # 显示有用矢量的统计数据
  367. def helpful_vectors(BB, modulus):
  368. nothelpful = 0
  369. for ii in range(BB.dimensions()[0]):
  370. if BB[ii,ii] >= modulus:
  371. nothelpful += 1
  372.  
  373. print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
  374.  
  375. # 显示带有 0 和 X 的矩阵
  376. def matrix_overview(BB, bound):
  377. for ii in range(BB.dimensions()[0]):
  378. a = ('%02d ' % ii)
  379. for jj in range(BB.dimensions()[1]):
  380. a += '0' if BB[ii,jj] == 0 else 'X'
  381. if BB.dimensions()[0] < 60:
  382. a += ' '
  383. if BB[ii, ii] >= bound:
  384. a += '~'
  385. #print (a)
  386.  
  387. # 尝试删除无用的向量
  388. # 从当前 = n-1（最后一个向量）开始
  389. def remove_unhelpful(BB, monomials, bound, current):
  390. # 我们从当前 = n-1（最后一个向量）开始
  391. if current == -1 or BB.dimensions()[0] <= dimension_min:
  392. return BB
  393.  
  394. # 开始从后面检查
  395. for ii in range(current, -1, -1):
  396. # 如果它没有用
  397. if BB[ii, ii] >= bound:
  398. affected_vectors = 0
  399. affected_vector_index = 0
  400. # 让我们检查它是否影响其他向量
  401. for jj in range(ii + 1, BB.dimensions()[0]):
  402. # 如果另一个向量受到影响：
  403. # 我们增加计数
  404. if BB[jj, ii] != 0:
  405. affected_vectors += 1
  406. affected_vector_index = jj
  407.  
  408. # 等级：0
  409. # 如果没有其他载体最终受到影响
  410. # 我们删除它
  411. if affected_vectors == 0:
  412. #print ("* removing unhelpful vector", ii)
  413. BB = BB.delete_columns([ii])
  414. BB = BB.delete_rows([ii])
  415. monomials.pop(ii)
  416. BB = remove_unhelpful(BB, monomials, bound, ii-1)
  417. return BB
  418.  
  419. # 等级：1
  420. #如果只有一个受到影响，我们会检查
  421. # 如果它正在影响别的向量
  422. elif affected_vectors == 1:
  423. affected_deeper = True
  424. for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
  425. # 如果它影响哪怕一个向量
  426. # 我们放弃这个
  427. if BB[kk, affected_vector_index] != 0:
  428. affected_deeper = False
  429. # 如果没有其他向量受到影响，则将其删除，并且
  430. # 这个有用的向量不够有用
  431. #与我们无用的相比
  432. if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
  433. #print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
  434. BB = BB.delete_columns([affected_vector_index, ii])
  435. BB = BB.delete_rows([affected_vector_index, ii])
  436. monomials.pop(affected_vector_index)
  437. monomials.pop(ii)
  438. BB = remove_unhelpful(BB, monomials, bound, ii-1)
  439. return BB
  440. # nothing happened
  441. return BB
  442.  
  443. """
  444. Returns:
  445. * 0,0 if it fails
  446. * -1，-1 如果 "strict=true"，并且行列式不受约束
  447. * x0,y0 the solutions of `pol`
  448. """
  449. def boneh_durfee(pol, modulus, mm, tt, XX, YY):
  450. """
  451. Boneh and Durfee revisited by Herrmann and May
  452.  
  453. 在以下情况下找到解决方案：
  454. * d < N^delta
  455. * |x|< e^delta
  456. * |y|< e^0.5
  457. 每当 delta < 1 - sqrt（2）/2 ~ 0.292
  458. """
  459.  
  460. # substitution (Herrman and May)
  461. PR.<u, x, y> = PolynomialRing(ZZ) #多项式环
  462. Q = PR.quotient(x*y + 1 - u) # u = xy + 1
  463. polZ = Q(pol).lift()
  464.  
  465. UU = XX*YY + 1
  466.  
  467. # x-移位
  468. gg = []
  469. for kk in range(mm + 1):
  470. for ii in range(mm - kk + 1):
  471. xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
  472. gg.append(xshift)
  473. gg.sort()
  474.  
  475. # 单项式 x 移位列表
  476. monomials = []
  477. for polynomial in gg:
  478. for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
  479. if monomial not in monomials: # 如果单项不在单项中
  480. monomials.append(monomial)
  481. monomials.sort()
  482.  
  483. # y-移位
  484. for jj in range(1, tt + 1):
  485. for kk in range(floor(mm/tt) * jj, mm + 1):
  486. yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
  487. yshift = Q(yshift).lift()
  488. gg.append(yshift) # substitution
  489.  
  490. # 单项式 y 移位列表
  491. for jj in range(1, tt + 1):
  492. for kk in range(floor(mm/tt) * jj, mm + 1):
  493. monomials.append(u^kk * y^jj)
  494.  
  495. # 构造格 B
  496. nn = len(monomials)
  497. BB = Matrix(ZZ, nn)
  498. for ii in range(nn):
  499. BB[ii, 0] = gg[ii](0, 0, 0)
  500. for jj in range(1, ii + 1):
  501. if monomials[jj] in gg[ii].monomials():
  502. BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
  503.  
  504. #约化格的原型
  505. if helpful_only:
  506. # #自动删除
  507. BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
  508. # 重置维度
  509. nn = BB.dimensions()[0]
  510. if nn == 0:
  511. print ("failure")
  512. return 0,0
  513.  
  514. # 检查向量是否有帮助
  515. if debug:
  516. helpful_vectors(BB, modulus^mm)
  517.  
  518. # 检查行列式是否正确界定
  519. det = BB.det()
  520. bound = modulus^(mm*nn)
  521. if det >= bound:
  522. print ("We do not have det < bound. Solutions might not be found.")
  523. print ("Try with highers m and t.")
  524. if debug:
  525. diff = (log(det) - log(bound)) / log(2)
  526. print ("size det(L) - size e^(m*n) = ", floor(diff))
  527. if strict:
  528. return -1, -1
  529. else:
  530. print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
  531.  
  532. # display the lattice basis
  533. if debug:
  534. matrix_overview(BB, modulus^mm)
  535.  
  536. # LLL
  537. if debug:
  538. print ("optimizing basis of the lattice via LLL, this can take a long time")
  539.  
  540. #BB = BB.BKZ(block_size=25)
  541. BB = BB.LLL()
  542.  
  543. if debug:
  544. print ("LLL is done!")
  545.  
  546. # 替换向量 i 和 j ->多项式 1 和 2
  547. if debug:
  548. print ("在格中寻找线性无关向量")
  549. found_polynomials = False
  550.  
  551. for pol1_idx in range(nn - 1):
  552. for pol2_idx in range(pol1_idx + 1, nn):
  553.  
  554. # 对于i and j, 构造两个多项式
  555.  
  556. PR.<w,z> = PolynomialRing(ZZ)
  557. pol1 = pol2 = 0
  558. for jj in range(nn):
  559. pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
  560. pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
  561.  
  562. # 结果
  563. PR.<q> = PolynomialRing(ZZ)
  564. rr = pol1.resultant(pol2)
  565.  
  566.  
  567. if rr.is_zero() or rr.monomials() == [1]:
  568. continue
  569. else:
  570. print ("found them, using vectors", pol1_idx, "and", pol2_idx)
  571. found_polynomials = True
  572. break
  573. if found_polynomials:
  574. break
  575.  
  576. if not found_polynomials:
  577. print ("no independant vectors could be found. This should very rarely happen...")
  578. return 0, 0
  579.  
  580. rr = rr(q, q)
  581.  
  582. # solutions
  583. soly = rr.roots()
  584.  
  585. if len(soly) == 0:
  586. print ("Your prediction (delta) is too small")
  587. return 0, 0
  588.  
  589. soly = soly[0][0]
  590. ss = pol1(q, soly)
  591. solx = ss.roots()[0][0]
  592. return solx, soly
  593.  
  594.  
  595. def example():
  596. ############################################
  597. # 随机生成数据
  598. ##########################################
  599. #start_time =time.perf_counter
  600. start =time.clock()
  601. size=512
  602. length_N = 2*size;
  603. ss=0
  604. s=27;
  605. M=100 # the number of experiments
  606. delta = 0.292
  607. # p = random_prime(2^512,2^511)
  608. for i in range(M):
  609. p = random_prime(2^size,None,2^(size-1))
  610. q = random_prime(2^size,None,2^(size-1))
  611. if(p<q):
  612. temp=p
  613. p=q
  614. q=temp
  615. print ("p真实高",s,"比特：", int(p/2^(512-s)))
  616. print ("q真实高",s,"比特：", int(q/2^(512-s)))
  617.  
  618. N = p*q;
  619. d=floor(N^delta);
  620. for j in range(1000):
  621. d=d-1;
  622. if gcd(d,(p-1)*(q-1))==1:
  623. print('d=',d)
  624. print('N=',N)
  625. print('p=',p)
  626. print('q=',q)
  627. #print("p1=",len(bin(p)))
  628. print("p2=",int(log(p)/log(2))+1)
  629. # print("q1=",len(bin(q)))
  630. print("q2=",int(log(q)/log(2))+1)
  631. e=inverse_mod(d,(p-1)*(q-1))
  632. print('e=',e)
  633. break
  634.  
  635.  
  636. # 解密指数d的指数( 最大0.292)
  637.  
  638.  
  639.  
  640. m = 7 # 格大小（越大越好/越慢）
  641. t = round(((1-2*delta) * m)) # 来自 Herrmann 和 May 的优化
  642. X = floor(N^delta) #
  643. Y = floor(N^(1/2)/2^s) # 如果 p、 q 大小相同，则正确
  644. for l in range(int(p/2^(512-s)),int(p/2^(512-s))+1):
  645. print('\n\n\n l=',l)
  646. pM=l;
  647. p0=pM*2^(size-s)+2^(size-s)-1;
  648. q0=N/p0;
  649. qM=int(q0/2^(size-s))
  650. A = N + 1-pM*2^(size-s)-qM*2^(size-s);
  651. #A = N+1
  652. P.<x,y> = PolynomialRing(ZZ)
  653. pol = 1 + x * (A + y) #构建的方程
  654.  
  655. # Checking bounds
  656. #if debug:
  657. #print ("=== 核对数据 ===")
  658. #print ("* delta:", delta)
  659. #print ("* delta < 0.292", delta < 0.292)
  660. #print ("* size of e:", ceil(log(e)/log(2))) # e的bit数
  661. # print ("* size of N:", len(bin(N))) # N的bit数
  662. #print ("* size of N:", ceil(log(N)/log(2))) # N的bit数
  663. #print ("* m:", m, ", t:", t)
  664.  
  665. # boneh_durfee
  666. if debug:
  667. ##print ("=== running algorithm ===")
  668. start_time = time.time()
  669.  
  670.  
  671. solx, soly = boneh_durfee(pol, e, m, t, X, Y)
  672.  
  673.  
  674. if solx > 0:
  675. #print ("=== solution found ===")
  676. if False:
  677. print ("x:", solx)
  678. print ("y:", soly)
  679.  
  680. d_sol = int(pol(solx, soly) / e)
  681. ss=ss+1
  682. if(d_sol==d):
  683. print ("=== solution found ===")
  684. print ("p的高比特为：",l)
  685. print ("q的高比特为：",qM)
  686. print ("d=",d_sol)
  687. print ("p真实高比特：", int(p/2^(512-s)))
  688. print ("q真实高比特：", int(q/2^(512-s)))
  689.  
  690.  
  691. else:
  692. print ("=== no solution was found ===")
  693.  
  694.  
  695. if debug:
  696. print("=== %s seconds ===" % (time.time() - start_time))
  697. #break
  698. print("ss=",ss)
  699. #end=time.process_time
  700. end=time.clock()
  701. print('Running time: %s Seconds'%(end-start))
  702. if __name__ == "__main__":
  703. example()
  704. #########Code of Tables 8#########
  705. #########Code of Tables 8#########
  706. #########Code of Tables 8#########
  707. #########Code of Tables 8#########
  708.  
  709.  
  710.  
  711.  
  712.  
  713.  
  714.  
  715.  
  716.  
  717.  
  718.  
  719. #########Code of Tables 9-10#########
  720. #########Code of Tables 9-10#########
  721. #########Code of Tables 9-10#########
  722. #########Code of Tables 9-10#########
  723.  
  724. import time
  725.  
  726. debug = True
  727.  
  728. strict = False
  729.  
  730.  
  731. helpful_only = True
  732. dimension_min = 7 # 如果晶格达到该尺寸，则停止移除
  733.  
  734. # 显示有用矢量的统计数据
  735. def helpful_vectors(BB, modulus):
  736. nothelpful = 0
  737. for ii in range(BB.dimensions()[0]):
  738. if BB[ii,ii] >= modulus:
  739. nothelpful += 1
  740.  
  741. print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
  742.  
  743. # 显示带有 0 和 X 的矩阵
  744. def matrix_overview(BB, bound):
  745. for ii in range(BB.dimensions()[0]):
  746. a = ('%02d ' % ii)
  747. for jj in range(BB.dimensions()[1]):
  748. a += '0' if BB[ii,jj] == 0 else 'X'
  749. if BB.dimensions()[0] < 60:
  750. a += ' '
  751. if BB[ii, ii] >= bound:
  752. a += '~'
  753. #print (a)
  754.  
  755. # 尝试删除无用的向量
  756. # 从当前 = n-1（最后一个向量）开始
  757. def remove_unhelpful(BB, monomials, bound, current):
  758. # 我们从当前 = n-1（最后一个向量）开始
  759. if current == -1 or BB.dimensions()[0] <= dimension_min:
  760. return BB
  761.  
  762. # 开始从后面检查
  763. for ii in range(current, -1, -1):
  764. # 如果它没有用
  765. if BB[ii, ii] >= bound:
  766. affected_vectors = 0
  767. affected_vector_index = 0
  768. # 让我们检查它是否影响其他向量
  769. for jj in range(ii + 1, BB.dimensions()[0]):
  770. # 如果另一个向量受到影响：
  771. # 我们增加计数
  772. if BB[jj, ii] != 0:
  773. affected_vectors += 1
  774. affected_vector_index = jj
  775.  
  776. # 等级：0
  777. # 如果没有其他载体最终受到影响
  778. # 我们删除它
  779. if affected_vectors == 0:
  780. #print ("* removing unhelpful vector", ii)
  781. BB = BB.delete_columns([ii])
  782. BB = BB.delete_rows([ii])
  783. monomials.pop(ii)
  784. BB = remove_unhelpful(BB, monomials, bound, ii-1)
  785. return BB
  786.  
  787. # 等级：1
  788. #如果只有一个受到影响，我们会检查
  789. # 如果它正在影响别的向量
  790. elif affected_vectors == 1:
  791. affected_deeper = True
  792. for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
  793. # 如果它影响哪怕一个向量
  794. # 我们放弃这个
  795. if BB[kk, affected_vector_index] != 0:
  796. affected_deeper = False
  797. # 如果没有其他向量受到影响，则将其删除，并且
  798. # 这个有用的向量不够有用
  799. #与我们无用的相比
  800. if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
  801. #print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
  802. BB = BB.delete_columns([affected_vector_index, ii])
  803. BB = BB.delete_rows([affected_vector_index, ii])
  804. monomials.pop(affected_vector_index)
  805. monomials.pop(ii)
  806. BB = remove_unhelpful(BB, monomials, bound, ii-1)
  807. return BB
  808. # nothing happened
  809. return BB
  810.  
  811. """
  812. Returns:
  813. * 0,0 if it fails
  814. * -1，-1 如果 "strict=true"，并且行列式不受约束
  815. * x0,y0 the solutions of `pol`
  816. """
  817. def boneh_durfee(pol, modulus, mm, tt, XX, YY):
  818. """
  819. Boneh and Durfee revisited by Herrmann and May
  820.  
  821. 在以下情况下找到解决方案：
  822. * d < N^delta
  823. * |x|< e^delta
  824. * |y|< e^0.5
  825. 每当 delta < 1 - sqrt（2）/2 ~ 0.292
  826. """
  827.  
  828. # substitution (Herrman and May)
  829. PR.<u, x, y> = PolynomialRing(ZZ) #多项式环
  830. Q = PR.quotient(x*y + 1 - u) # u = xy + 1
  831. polZ = Q(pol).lift()
  832.  
  833. UU = XX*YY + 1
  834.  
  835. # x-移位
  836. gg = []
  837. for kk in range(mm + 1):
  838. for ii in range(mm - kk + 1):
  839. xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
  840. gg.append(xshift)
  841. gg.sort()
  842.  
  843. # 单项式 x 移位列表
  844. monomials = []
  845. for polynomial in gg:
  846. for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
  847. if monomial not in monomials: # 如果单项不在单项中
  848. monomials.append(monomial)
  849. monomials.sort()
  850.  
  851. # y-移位
  852. for jj in range(1, tt + 1):
  853. for kk in range(floor(mm/tt) * jj, mm + 1):
  854. yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
  855. yshift = Q(yshift).lift()
  856. gg.append(yshift) # substitution
  857.  
  858. # 单项式 y 移位列表
  859. for jj in range(1, tt + 1):
  860. for kk in range(floor(mm/tt) * jj, mm + 1):
  861. monomials.append(u^kk * y^jj)
  862.  
  863. # 构造格 B
  864. nn = len(monomials)
  865. BB = Matrix(ZZ, nn)
  866. for ii in range(nn):
  867. BB[ii, 0] = gg[ii](0, 0, 0)
  868. for jj in range(1, ii + 1):
  869. if monomials[jj] in gg[ii].monomials():
  870. BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
  871.  
  872. #约化格的原型
  873. if helpful_only:
  874. # #自动删除
  875. BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
  876. # 重置维度
  877. nn = BB.dimensions()[0]
  878. if nn == 0:
  879. print ("failure")
  880. return 0,0
  881.  
  882. # 检查向量是否有帮助
  883. if debug:
  884. helpful_vectors(BB, modulus^mm)
  885.  
  886. # 检查行列式是否正确界定
  887. det = BB.det()
  888. bound = modulus^(mm*nn)
  889. if det >= bound:
  890. print ("We do not have det < bound. Solutions might not be found.")
  891. print ("Try with highers m and t.")
  892. if debug:
  893. diff = (log(det) - log(bound)) / log(2)
  894. print ("size det(L) - size e^(m*n) = ", floor(diff))
  895. if strict:
  896. return -1, -1
  897. else:
  898. print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
  899.  
  900. # display the lattice basis
  901. if debug:
  902. matrix_overview(BB, modulus^mm)
  903.  
  904. # LLL
  905. if debug:
  906. print ("optimizing basis of the lattice via LLL, this can take a long time")
  907.  
  908. #BB = BB.BKZ(block_size=25)
  909. BB = BB.LLL()
  910.  
  911. if debug:
  912. print ("LLL is done!")
  913.  
  914. # 替换向量 i 和 j ->多项式 1 和 2
  915. if debug:
  916. print ("在格中寻找线性无关向量")
  917. found_polynomials = False
  918.  
  919. for pol1_idx in range(nn - 1):
  920. for pol2_idx in range(pol1_idx + 1, nn):
  921.  
  922. # 对于i and j, 构造两个多项式
  923.  
  924. PR.<w,z> = PolynomialRing(ZZ)
  925. pol1 = pol2 = 0
  926. for jj in range(nn):
  927. pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
  928. pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
  929.  
  930. # 结果
  931. PR.<q> = PolynomialRing(ZZ)
  932. rr = pol1.resultant(pol2)
  933.  
  934.  
  935. if rr.is_zero() or rr.monomials() == [1]:
  936. continue
  937. else:
  938. print ("found them, using vectors", pol1_idx, "and", pol2_idx)
  939. found_polynomials = True
  940. break
  941. if found_polynomials:
  942. break
  943.  
  944. if not found_polynomials:
  945. print ("no independant vectors could be found. This should very rarely happen...")
  946. return 0, 0
  947.  
  948. rr = rr(q, q)
  949.  
  950. # solutions
  951. soly = rr.roots()
  952.  
  953. if len(soly) == 0:
  954. print ("Your prediction (delta) is too small")
  955. return 0, 0
  956.  
  957. soly = soly[0][0]
  958. ss = pol1(q, soly)
  959. solx = ss.roots()[0][0]
  960. return solx, soly
  961.  
  962.  
  963. def example():
  964. ############################################
  965. # 随机生成数据
  966. ##########################################
  967. #start_time =time.perf_counter
  968. start =time.clock()
  969. size=512 #The size of p; size=1024 in Tables 10
  970. length_N = 2*size;
  971. ss=0
  972. s=18; #s is the number of MSBs exhaustion, which can be chosen as we need.
  973. nw=3 #2^nw windows
  974. delta = 0.292
  975.  
  976. N= 46126089040452448339448600417060313922101098426244293259787635870745306734916761740947413085700089913080864291336942530825020832297938382575650566384847941135822852822252739532743510189124124500359010333442383692988340095271183825614638791911699269162046275028679426500348785157345976662456325437259705160061
  977. e= 36614584641331081308456049556562616703353184435474954472543851641598746555075132401789399242413012437952852904270269699841919341733637018625615174142612269063196723454327979744131149454548205774006091224643569311902728986446145416739772661245661572872595702072188094041649860081717657262961694486055770442903
  978. # The parameters (N, e) can be chosen as we need.
  979. m = 12 # 格大小（越大越好/越慢）
  980. #guess=100
  981. # you need to be a lattice master to tweak these
  982. t = round(((1-2*delta) * m)) # 来自 Herrmann 和 May 的优化
  983. X = floor(N^delta) #
  984. Y = 2*floor(N^(1/2)/2^s) # 如果 p、 q 大小相同，则正确
  985. #for l in range(2^int(s/2),2^s):
  986. for i in range(1,s-1-nw+1):
  987. for j in range(1,2^(i-1)+1):
  988. kk=2*j-1
  989. l=kk*2^(s-1-nw-i)
  990. pM=2^(s-1)+6*2^(s-1-nw)+l; #This is the seventh window
  991. #pM=2^(s-1)+i*2^(s-1-nw)+l; This is (i+1)-th window
  992. print('\n\n\n pM=',pM)
  993. p0=pM*2^(size-s)+2^(size-s-1);
  994. q0=N/p0;
  995. qM=int(q0/2^(size-s))
  996. A = N + 1-pM*2^(size-s)-qM*2^(size-s);
  997. #A = N+1
  998. P.<x,y> = PolynomialRing(ZZ)
  999. pol = 1 + x * (A + y) #构建的方程
  1000. if debug:
  1001. ##print ("=== running algorithm ===")
  1002. start_time = time.time()
  1003.  
  1004.  
  1005. solx, soly = boneh_durfee(pol, e, m, t, X, Y)
  1006.  
  1007.  
  1008. if solx > 0:
  1009. #print ("=== solution found ===")
  1010. if False:
  1011. print ("x:", solx)
  1012. print ("y:", soly)
  1013.  
  1014. d_sol = int(pol(solx, soly) / e)
  1015. #print ("私钥d:", d)
  1016. ss=ss+1
  1017. #if(d_sol==d):
  1018. print ("=== solution found ===")
  1019. print ("p的高比特为：",pM)
  1020. print ("q的高比特为：",qM)
  1021. #print("p的真实高比特：",int(p/2^(512-s)))
  1022. #print("q的真实高比特：",int(q/2^(512-s)))
  1023. print ("d=",d_sol)
  1024. break
  1025.  
  1026. #else:
  1027. #print ("=== no solution was found ===")
  1028.  
  1029.  
  1030. if debug:
  1031. print("=== %s seconds ===" % (time.time() - start_time))
  1032.  
  1033. if(ss==1):
  1034. break
  1035. print("ss=",ss)
  1036. #end=time.process_time
  1037. end=time.clock()
  1038. print('Running time: %s Seconds'%(end-start))
  1039. if __name__ == "__main__":
  1040. example()
  1041.  
  1042. #########Code of Tables 9-10#########
  1043. #########Code of Tables 9-10#########
  1044. #########Code of Tables 9-10#########
  1045. #########Code of Tables 9-10#########
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!