第八届全国职工职业技能大赛 省初赛

赛后拿到题目简单看了一下两道密码题，不是很难。

但是给你们看一下茶茶的小肚腩~

crypto1

pri.pem

-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAwAAAAOkAAAAAAABgAIAAAAtqAAAAAgAAzSAAAAo+AAAAAAB+
AAAG0KAEowAAAAAAAAiwAM53AMCwjQAAAAAAB+AABIUAAAAAAAAAADC4AAAAH4AA
bbdwAAAAAAAAAD+AAMoA2VAAAACX4ACVOQAAAAjQAAZgAAANUAAHAAYAAABNAAAA
AADDAAAA1wAAAAkAAAAAMAAN0ADAAAAAAK0AAAAFcACT0AAAAADLkAAAAADcAAAA
gAAJAAwBAAAAAgAAAQBQAAMgAAAAAAAgAPMAAAACAAAAAACAAMwAAAYAAB4AAAAA
AOgAAAAAAAoOAAAA0AACIACGAAAAYgAA5gACAQIDAQABAoIBAAAAAAAB4KUzFgAA
AAAAAO8AAAAAC9AAAABAAACAAAAAAAAAAAAAAAAwAAAAAAAAagAAAAAAAAAAAAAA
DcAAsAAAAAoAAAAAAAAAAAAAAAAAAAQHUAAAAAAAAAAAAAAMYAAAkAcAAAwAAAAA
AAAAAAAARADwAAAAAAAAAAAAABAACgAAAAAAAAAAAAAAAAAAAACw3jAAAAAAAAAA
AAAAAAAAAEAAAAAAAAAAAAAAYAADAAAAAAAAAAAAAAAAAAAAJwsCAAAL8QAAAAAA
AAAAAAAAAAAAYKAAAAAAAAAAAC4AAAAAAAAAAAAAAAAOrwAAAAAAAAAAAAAAsMgO
AAAFAAACgYEAAAAOwAAAAAAAAg8AICAAAAAAAAAAAAAAAAALpwoAAAAAAAAN4QAA
AAAAAAAAAAAAAAQgAAAAAAYAAAAAAAAAAAAAAAAABwAAAAAAAAAA8AAAAAAAAAAA
AAAAAAAABSAAAAAAAAAAAAAAAAAAAADuAAAAAAAAAAAAAAgAAAAQAAACgYEAAAAA
AAAB8AAACwsAAAgPAAAAAAAAAAAAAAAABQAAAAAAAABgAAAAAAAAAAAAAADQ8AAA
AAAAAAAAAM0AAAAAAA8AAAAAAAAdAAAAAAAAAOYAAAAAAAAAKAAAAAAAAAAAAAAA
AADQAAAAAAAAAqAAAAAv7lvTxT5Qu0X/olRp8YUCgYEA6FGUyZWkh7UYHUCb/GTA
RYoNBWW7fiqo8CafKhDqkyfqtypFZQIBuen+Z/MNSLrE9Qk8PUUdi1VHY+QQDdRQ
91a92YdBG63y/xgkznKNeGeNuR5CrTfzOb04ktXG7uY/rWMFRH83CUJZ07Ka/pYS
rtvVXAAv5r45BbJcYTyd43ECgYBuLtsbq9u9UXQFrYurD8JvH1e9t6r8fJc63kgz
uMZtkbNjQ6Ft9Ur0sZEE/J1olArtqSmocL9anqIAnP1MpaN5mgJfCHcvo5W3nDNb
bcc9iyShH45cOdjgTMRqDWpTejwWEwLok0UMvdluaPOF1e5ELGAS/r+QxyOW+/YP
PYIa1QKBgCYr1JCZqJ8JM0x3KoXSfMlqIfjE2ZXVotYvr0PV/nBk+4yP139hoHrl
GMo075P9bG4uLkvnEWn9q4JxxG0zTXuxyRcGzYFJ62v2/ty2tWtbax3y3tbamqrG
Foy9yWzewL1RBKNDabz8DEZRsNwf5WaXz4XoKPNbC0x+aWVn7CCD
-----END RSA PRIVATE KEY-----

是一份不完整的 RSA 私钥文件，对其中数据base64解码得到

308204a30201000282010100c0000000e900000000000060008000000b6a000000020000cd2000000a3e00000000007e000006d0a004a300000000000008b000ce7700c0b08d000000000007e0000485000000000000000030b80000001f80006db770000000000000003f8000ca00d95000000097e000953900000008d000066000000d50000700060000004d0000000000c3000000d7000000090000000030000dd000c000000000ad00000005700093d000000000cb9000000000dc000000800009000c0100000002000001005000032000000000002000f30000000200000000008000cc00000600001e0000000000e800000000000a0e000000d00002200086000000620000e60002010203010001028201000000000001e0a53316000000000000ef000000000bd0000000400000800000000000000000000000300000000000006a00000000000000000000000dc000b00000000a0000000000000000000000000000040750000000000000000000000c600000900700000c000000000000000000004400f00000000000000000000010000a00000000000000000000000000000000b0de3000000000000000000000000000004000000000000000000000600003000000000000000000000000000000270b0200000bf1000000000000000000000000000060a000000000000000002e0000000000000000000000000eaf0000000000000000000000b0c80e00000500000281810000000ec00000000000020f0020200000000000000000000000000ba70a0000000000000de10000000000000000000000000420000000000600000000000000000000000000070000000000000000f000000000000000000000000000000520000000000000000000000000000000ee000000000000000000000800000010000002818100000000000001f000000b0b0000080f0000000000000000000000000500000000000000600000000000000000000000d0f0000000000000000000cd00000000000f0000000000001d00000000000000e6000000000000002800000000000000000000000000d000000000000002a00000002fee5bd3c53e50bb45ffa25469f18502818100e85194c995a487b5181d409bfc64c0458a0d0565bb7e2aa8f0269f2a10ea9327eab72a45650201b9e9fe67f30d48bac4f5093c3d451d8b554763e4100dd450f756bdd987411badf2ff1824ce728d78678db91e42ad37f339bd3892d5c6eee63fad6305447f37094259d3b29afe9612aedbd55c002fe6be3905b25c613c9de3710281806e2edb1babdbbd517405ad8bab0fc26f1f57bdb7aafc7c973ade4833b8c66d91b36343a16df54af4b19104fc9d68940aeda929a870bf5a9ea2009cfd4ca5a3799a025f08772fa395b79c335b6dc73d8b24a11f8e5c39d8e04cc46a0d6a537a3c161302e893450cbdd96e68f385d5ee442c6012febf90c72396fbf60f3d821ad5028180262bd49099a89f09334c772a85d27cc96a21f8c4d995d5a2d62faf43d5fe7064fb8c8fd77f61a07ae518ca34ef93fd6c6e2e2e4be71169fdab8271c46d334d7bb1c91706cd8149eb6bf6fedcb6b56b5b6b1df2ded6da9aaac6168cbdc96cdec0bd5104a34369bcfc0c4651b0dc1fe56697cf85e828f35b0b4c7e696567ec2083

根据 pem 文件编码格式简单分割一下（搜索一下 8181 或者 8180）

308204a302010002

820101

00c0000000e900000000000060008000000b6a000000020000cd2000000a3e00000000007e000006d0a004a300000000000008b000ce7700c0b08d000000000007e0000485000000000000000030b80000001f80006db770000000000000003f8000ca00d95000000097e000953900000008d000066000000d50000700060000004d0000000000c3000000d7000000090000000030000dd000c000000000ad00000005700093d000000000cb9000000000dc000000800009000c0100000002000001005000032000000000002000f30000000200000000008000cc00000600001e0000000000e800000000000a0e000000d00002200086000000620000e6000201

0203010001

02
820100

0000000001e0a53316000000000000ef000000000bd0000000400000800000000000000000000000300000000000006a00000000000000000000000dc000b00000000a0000000000000000000000000000040750000000000000000000000c600000900700000c000000000000000000004400f00000000000000000000010000a00000000000000000000000000000000b0de3000000000000000000000000000004000000000000000000000600003000000000000000000000000000000270b0200000bf1000000000000000000000000000060a000000000000000002e0000000000000000000000000eaf0000000000000000000000b0c80e000005000002

8181

0000000ec00000000000020f0020200000000000000000000000000ba70a0000000000000de10000000000000000000000000420000000000600000000000000000000000000070000000000000000f000000000000000000000000000000520000000000000000000000000000000ee000000000000000000000800000010000002

8181

00000000000001f000000b0b0000080f0000000000000000000000000500000000000000600000000000000000000000d0f0000000000000000000cd00000000000f0000000000001d00000000000000e6000000000000002800000000000000000000000000d000000000000002a00000002fee5bd3c53e50bb45ffa25469f18502

8181

00e85194c995a487b5181d409bfc64c0458a0d0565bb7e2aa8f0269f2a10ea9327eab72a45650201b9e9fe67f30d48bac4f5093c3d451d8b554763e4100dd450f756bdd987411badf2ff1824ce728d78678db91e42ad37f339bd3892d5c6eee63fad6305447f37094259d3b29afe9612aedbd55c002fe6be3905b25c613c9de37102

8180

6e2edb1babdbbd517405ad8bab0fc26f1f57bdb7aafc7c973ade4833b8c66d91b36343a16df54af4b19104fc9d68940aeda929a870bf5a9ea2009cfd4ca5a3799a025f08772fa395b79c335b6dc73d8b24a11f8e5c39d8e04cc46a0d6a537a3c161302e893450cbdd96e68f385d5ee442c6012febf90c72396fbf60f3d821ad502

8180

262bd49099a89f09334c772a85d27cc96a21f8c4d995d5a2d62faf43d5fe7064fb8c8fd77f61a07ae518ca34ef93fd6c6e2e2e4be71169fdab8271c46d334d7bb1c91706cd8149eb6bf6fedcb6b56b5b6b1df2ded6da9aaac6168cbdc96cdec0bd5104a34369bcfc0c4651b0dc1fe56697cf85e828f35b0b4c7e696567ec2083

所以我们就是拥有完整的 e,  dp 和 dq

e = 0x10001
dp = 0x00e85194c995a487b5181d409bfc64c0458a0d0565bb7e2aa8f0269f2a10ea9327eab72a45650201b9e9fe67f30d48bac4f5093c3d451d8b554763e4100dd450f756bdd987411badf2ff1824ce728d78678db91e42ad37f339bd3892d5c6eee63fad6305447f37094259d3b29afe9612aedbd55c002fe6be3905b25c613c9de371
dq = 0x6e2edb1babdbbd517405ad8bab0fc26f1f57bdb7aafc7c973ade4833b8c66d91b36343a16df54af4b19104fc9d68940aeda929a870bf5a9ea2009cfd4ca5a3799a025f08772fa395b79c335b6dc73d8b24a11f8e5c39d8e04cc46a0d6a537a3c161302e893450cbdd96e68f385d5ee442c6012febf90c72396fbf60f3d821ad5

由于

所以

而 ，所以我们只需要爆破 ，找到 并且满足 是素数，那么这大概率就是 了， 同理

exp

from Crypto.Util.number import *

e =  0x10001
dp = 0x00e85194c995a487b5181d409bfc64c0458a0d0565bb7e2aa8f0269f2a10ea9327eab72a45650201b9e9fe67f30d48bac4f5093c3d451d8b554763e4100dd450f756bdd987411badf2ff1824ce728d78678db91e42ad37f339bd3892d5c6eee63fad6305447f37094259d3b29afe9612aedbd55c002fe6be3905b25c613c9de371
dq = 0x6e2edb1babdbbd517405ad8bab0fc26f1f57bdb7aafc7c973ade4833b8c66d91b36343a16df54af4b19104fc9d68940aeda929a870bf5a9ea2009cfd4ca5a3799a025f08772fa395b79c335b6dc73d8b24a11f8e5c39d8e04cc46a0d6a537a3c161302e893450cbdd96e68f385d5ee442c6012febf90c72396fbf60f3d821ad5


for k in range(1,e):
 if (e*dp-1)%k == 0:
  if isPrime((e*dp-1)//k + 1):
   p = ((e*dp-1)//k + 1)
   break

for k in range(1,e):
 if (e*dq-1)%k == 0:
  if isPrime((e*dq-1)//k + 1):
   q = ((e*dq-1)//k + 1)
   break
with open("flag.enc","rb") as f:
 c = bytes_to_long(f.read())

d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,p*q)))

得到

b"x02xabGx9dxa2Pxb4xcbx03xf6xc3Rxfbxb3jzxe1]xfdx0f$xe4xb6xa8xe7Gxc9 x9cx1dx8bxdfyxb2Wx02xd5x17x87hxa7xd2x04xbfxb0xcexa5x17x93&xf1fx04xa2axd08xbeWx1dx91xf1rxa7xa9tx8fxff=]xc7x89&xacxfex04{/xac'x92x18x94xbfc*x96x0c]x03xf3x19x98x0fxf5-wx98xb3xe0#x12wrx8cx07Z,cxaexbd20xb76Odm{5xe7xaaxc7V-xd9xf9x9ex1f]xb4xd4x914x06+xe9.x06>[xcdxf4x16xa2xd3Kx17xceyx95x95xc6xeax0eRrx<e&x19xd2Ux0bx8exd5xc6[xf7x12Wx92x10xe0xc8,xf3]^x8exaa1'y_}H\nxc8x97xdbxd6xd09xa5xfd$jx04x97x9ax1fxcdxafxeex95xb6x7fxc5Xx88=xbfx06x00flag{622808a53003167cf7c391e9ecfd07cf}"

看来还是走了一手 PKCSv1.5 编码的。

crypto2

import random
from Crypto.Util.number import *
from flag import flag
assert len(flag) == 38
p = getPrime(512)
q = getPrime(512)
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, p*q)

n = getPrime(670)
hint = [getPrime(670), getPrime(670)]
for i in range(38):
    r = random.getrandbits(600)
    hint += [(p * hint[-2] + q * hint[-1] + r) % n]
print('hint =', hint)
print('n =', n)
print('c =', c)

# hint = [2720494314462626434759505113331611042078834745252921526772080004892926640828737817651467732895089125237909585543341228717279341268563550551207574194717155403366916944942140719274803540045574475403178509, 2807726059095345976957632960851346706069322884564357066467527778830478759555272700440959414709984033612643422808362900056118016815708080398529459590092998058311073623309843137823718818310496680675130313, 773460812596291034260523527300369834728062933507082081693735057179307271958505768354683217992511302512369902777058160377716198417907671981426290482409335216584645332979899193066561075891290898948045997, 1982768866468454335725786891790380160620336293012184347099101704772150876586024697854596045431572376369018024837937408123573595982470099399431353036723963395278635232677939887327463274572997307414710818, 317221993916611911442476097872136697882215004326352671070900917189729289839015072600174989636634981445942517118790690578759469122050092793263387329045675462810875155632750900320768838081181441783750801, 1379342083443637291160134275480526957030295019431794270322900305633647577977145898520591563598302227297274149520036344721858105783727738948941367825115629319762112409571823501402167099181778708406919992, 2790988233637747404718617965350747408215309308259447602183680015005964138764701567275644593735144201231400025485853797350532915847586403169164294417001426164597015967198341714987548442691134830861549980, 2540914652259014263273417932951653147429416237460503829879213976070241316912661821326273138886562085349352351472602982233735823298762263637792314437868898784590517434477715110010151920930053765249417294, 2356715170807888313045264536371248245754016168871367936962479519266225590311925082424653434693533171636216471598523474567464550881695140556443295315298705440111012107704029929531525920203335575692587422, 186300864996558926457608176323516051112596947535253477606583589440952161710119683641225042232637353722445117029760060678860879361321237402338932087435290746636286686053156197052590909442849710827437548, 2448105070302665025790261292022770323422855294026968438391221054263869890413151581480061138320646243590760594083891120366367565454599110513423006693661564679022083434108717488116152765724256169962817677, 1778310779400076033204591976342441425365814378197415626598808057675921593491893593022022411479822046289251357959691617630537843165192133277591161868439664413083367709005915489842461257933921278520437290, 2476380999932634871279391634343416041442030050827895101213040295536289311335043219367558327777314426029582524300681672057238145338459157922753209853227237828379439214909337699122123808378433659116027331, 539098377467518872740801420707068178555682761335521543774072661091281479015005439635045535239215556393917224347211368239659187327875558158391610067734441481030831910829941556575658660121731816664903005, 924781612402045015019980609543211672358337196278498970288199022240062100189262223372558128426801402296419365833758031861036917038806805587834775665570798102953989802033407544511654480720658516676857636, 2515245066250489318248347251927999387016159208157714926900823727002933207912873011379351613018065471591896029797105034976724267105488769743010073554476843083243859622308662937146098925407822071814473015, 1111500378174241883478059849322390354437649999289148333755841000066899561986530379593213500592418260937727953253745587259094349255425090538748139843265236349890369740349045490250691225395980093240189974, 2667387129049322355164571453395541363834644831159128756224468628317482046326919461065822686304732242415628868793218779249193789155939945172133247067381111925052552993101151667455109960484175011588867286, 2729966894239410331707370604742565503127326584926278873475629765721780350982787612443150274308995258118018213275295588713225059359997391894241896386873228098449701937615360984606540203927516481083888649, 810127125411345744892762557255740006201674117298917492199805636625499113310819069343225207256187530876830504188682142758367937930352570855006530343929021594061003754699932974682653320345851364783952352, 1406478522639598778556470898589982920113551339002024213780249158521756590996228960226049659661880980409938981359475875089683133933510213693861037483496481936946654764667509807579936834016616943116804322, 2839880340597121437166130858626267780232877932967189602341880930551309585482267892622005079387260908302680251964572223233427864271367854495962217049509936102720888331792674673988163529785734466599201366, 2033506238014182641146620128076458590739440877137855970906608778687566499771996269655530668411488701993300923253872763958909556740570069238643623990253545754727956146063974577721672645451546062746526247, 1768390692443834916263920779100748196199927459742223388765303283532637018860639470653950768540153383952363792304370879901777822274644917679971941729229020229367685039026909716314988098144879804073587957, 1108587820831228307102233821857852104202914161613856207153912222590162227851206013304077518245368120678762002116466069777709879549020641077409545645741532049699625677347789722036350094791118103188186254, 2449805667921840975788958008747666697168541982396101801036086086031791763787638811226728306608005802092318774955450967322797262349071091376480067085339814507400485941983269535390041410541130004202891510, 1419995074729409386592631232897555261335659110553657305840810431526845737338760910109509815882016521439484576467870140194623263229968415249475298476844169864562438175835533137000350314422833902891142463, 1174573907951978531086741335913901248037293580280857280721589009460808284314204707475594177855088804809436634086978941294503295926821894598992350129605525656867136308224035057642071262306188745104800330, 842288783813400517935003081200719637646352523587269796086641505101612562927432879980167767162918836468933416612894312209471338691864508609093479457502667215583331436724865557471668434108471152481290579, 374659064188408908508936597469021817487829911525386568588631208566940317079816443239318038642126296217395136491267399190092977146566483056228712121530478109485957509471408401315452468984521645383580189, 2357042770040559903221667108082739697735062872286466932132184298210805696036453664692972646818799976659381991295614091566788842241638382082263541437798427760671670848670044926393233751302783159439232952, 357176762668974901586579062417050483736862337750033169822688855436887894791960535384810816755417634680631245860053518883970766592985549914578874988225771534998721159614011096335034255846007034687335034, 1648113240479689614955454321172273383950367778981901219173402160410575490786106279875770836000561541128014562344419173192181388047012473223440359620885274231167017709092592511379847309555129502007173743, 1500054522167286991331751851830058429874586003131397451490704714438614595215672499540267590898526412909272116733129557379176633008086609516037361279066375517138973690392091852040762290295964262310588179, 648843671518580613116004540100760695183146134458140581802093813203126786504141747550776651098671810615776943253360934867809344130662904853674144717263018842852759445859773044138014223690372573976267408, 869932661788353349011628404320056016297477004613629605343255096590500065368913275349614142657607758748470500421784791663426348162654246959812616212341152673728097794200886989787433574141255122190127201, 36411897886202043241122504213496371404234300966627207270758517145007753748902828140186535780137306837119132900185562380096238898584052303948905141223337420154386498178021447529251832963544892873505845, 2628548502924556353953327106441850225989719372935269869398252481662406260878692737748068301770238888128683203279086166836969411921659070889662216112180622563228435470812357304774569737207781624797380278, 1174356643751138017086589720836614722377360910311288616451034569624915178434983991501515377808686400523960636927479039142227492833127685461301727910811624392768147873740404514758851631058106984859809996, 1375080395001952679485483884014893759616836086145330588338140372102402885533608071836584964968854506233393510875472129115132445604720520184457470245125773064888429699375589335374815585549316219278525168]
# n = 2923276556393306465975776608715617918820939733635306287316282928405826711944180807129458880976159847005801863680416075330326850146841550985087091569849369045131250588698063717548052968842737338925409099
# c = 73467709314298937420528773100032385349264953840593051286765944483277051482711719263011412049885652417973034070791950500981281499976480232797731332189457557296635986803388364022955884633545005207148035439241209382999814841832221291623320878954270072389534737744214350916065734321564127564255702187572055696459

题目也还是基于 RSA，其中 用在了 hint 的生成

是两个 512 比特的素数； 是 670 比特的已知素数； 是 600 比特随机数

很显然是一个手搓 lattice 的题。

设

是一个 的对角矩阵

搓一个

这样来一个  就能得到

刚好 也都比较小，

不过我们需要记录一下 ，然后我们的目标 是 600 比特的，所以右边再来一个   “接”一下

这样也好根据结果向量里最后一个元素是不是 来找到我们需要的 

exp.sage

h1 = hint[:20]
h2 = hint[1:21]
h3 = hint[2:22]

H = [h1,h2,h3]
H = matrix(ZZ,[h1,h2,h3])

t = diagonal_matrix([2^88,2^88,2^600])
t = matrix(ZZ,t)

n = 
n = diagonal_matrix([n]*20)

M = block_matrix(ZZ,[[H,t],[n,0]])
L = M.LLL()

for each in L:
    if abs(each[-1]) == 2^600:
        p = abs(each[-2])//2**88
        q = abs(each[-1])//2**88
        break
        
from Crypto.Util.number import *

c = 
print(long_to_bytes(pow(c, inverse(65537,(p-1)*(q-1)),p*q)))