2021 | 第十四届全国大学生信息安全竞赛 | 线上初赛 | Crypto

CISCN - rsa

解题思路

题目提供了 RSA 加密部分代码以及输出，明文被拆成了三部分进行加密

from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime

assert md5.new(text).hexdigest() == flag[6:-1]

msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]

msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)

p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)

p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)

p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200

低加密指数攻击

• 第一部分加密，\(e1\) 只有 \(3\)，属于低加密指数攻击
• 直接使用工具 Ganapati/RsaCtfTool Cube-Root 攻击

  $ ./RsaCtfTool.py -e 3 -n 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009 --uncipher 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893 --attack cube_root
  private argument is not set, the private key will not be displayed, even if recovered.
  
  [*] Testing key /tmp/tmp_l5kh68w.
  [*] Performing cube_root attack on /tmp/tmp_l5kh68w.
  
  Results for /tmp/tmp_l5kh68w:
  
  Unciphered data :
  HEX : 0x200a4f2077696c6420576573742057696e642c2074686f7520627265617468206f6620417574756d
  INT (big endian) : 267334379257781603687613466720913534310764480084016847281446486946801530200295563483353634338157
  INT (little endian) : 913291388310064586979227686933669644206016064403638123402129058189456441650304517698024417200672
  STR : b' \nO wild West Wind, thou breath of Autum'
  

共模攻击

• 第二部分使用了相同的模数 \(n\)，不同的 \(e\) 对同一段文本进行加密
• 使用工具 Ganapati/RsaCtfTool 的共模攻击（same_n_huge_e），e与密文在顺序上需要对应

  $ ./RsaCtfTool.py -e 17,65537 -n 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977 --uncipher 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610,91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950 --attack same_n_huge_e
  private argument is not set, the private key will not be displayed, even if recovered.
  [*] Multikey mode using keys: /tmp/tmpdgzqh3f2, /tmp/tmp9fa7r378
  [*] Performing same_n_huge_e attack.
  
  Results for /tmp/tmpdgzqh3f2,/tmp/tmp9fa7r378:
  
  Unciphered data :
  HEX : 0x6e2773206265696e672c0a54686f752c2066726f6d2077686f736520756e7365656e2070726573656e636520746865206c656176657320646561640a4172652064726976656e2c206c696b652067686f7374732066726f6d20616e20656e6368616e74657220666c6565696e672c0a59656c6c6f772c2061
  INT (big endian) : 4193305853284549103821195807609492624095031428085219879448342104337322945001387680236011960472296815293233144303730273979905837762067652913308898433728800864776794638198055607422503065410595894676740531680367227696622352026247676452540064020322619036125381146346603655445487695574824919137
  INT (little endian) : 3697344670341776042819034986158075076536873171472590072336800110388597776652983023588023111158079096754137966151154403318011693149935108642418525130993932032045777394368194102308289062036168961367389701205240426686201519457468290650177310915303466740807866707603445131602629565993519884142
  STR : b"n's being,\nThou, from whose unseen presence the leaves dead\nAre driven, like ghosts from an enchanter fleeing,\nYellow, a"
  
  [*] Testing key /tmp/tmpdgzqh3f2.
  
  [*] Testing key /tmp/tmp9fa7r378.
  

已知 P 的高位攻击（Coppersmith 攻击）

• 第三部分已知 P 的高位，为私钥的一部分，而工具 Ganapati/RsaCtfTool 主要专注于公钥攻击，尚未实现攻击partial_q
• 使用 SageMath

  # sage
  n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
  c = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
  p = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
  e = 65537
  
  pbits = 512 # p 的原始长度
  kbits = pbits-p.nbits()
  p = p << kbits
  print("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))
  PR.<x> = PolynomialRing(Zmod(n))
  f = x + p
  x0 = f.small_roots(X = 2^kbits, beta = 0.4)[0]  # 多项式小值根求解及因子分解
  p = p + int(x0)
  fn = (p - 1) * (n / p - 1)
  text = pow(c, inverse_mod(e,fn), n)
  hex_str = hex(text)
  
  print(hex_str)
  print(bytes.fromhex(hex_str[2:]))
  

• 获得输出

  upper 312 bits (of 512 bits) is given
  0x6e6420626c61636b2c20616e642070616c652c20616e6420686563746963207265642c0a50657374696c656e63652d73747269636b656e206d756c746974756465733a204f2074686f752c0a57686f2063686172696f7465737420746f207468656972206461726b2077696e747279206265640a
  b'nd black, and pale, and hectic red,\nPestilence-stricken multitudes: O thou,\nWho chariotest to their dark wintry bed\n'
  

• 拼接各部分结果再 MD5 即可获得 Flag

参考资料

• Dense univariate polynomials over Z/nZ , implemented using NTL

---

最后更新: 2021年6月7日 16:20:56

Contributors: YanhuiJessica
Pageviews:

评论