Created
October 17, 2019 11:56
-
-
Save sea0h7e/84d216ada142991903c0d1ca6a8d01be to your computer and use it in GitHub Desktop.
HITCON CTF 2019 Quals - not so hard RSA (Crypto, 371pts, 6 solves)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# https://pdfs.semanticscholar.org/2d85/9e8937fe652558a60e82ffd39cd4ab835e31.pdf, Section4.4 | |
# As LLL is not precise for there are only 10 public keys, so I use Babai instead. | |
# Just randomly construct the target vector, if it is close enough to (dM, 1−k1Λ1, ..., 1−krΛr), we may recover d. | |
from Crypto.Util.number import * | |
import random | |
k = 10 | |
f = open('output', 'rb') | |
f.readline() | |
N = [] | |
e = [] | |
c = [] | |
for i in range(k): | |
x = eval(f.readline()) | |
N.append(x[0]) | |
e.append(x[1]) | |
c.append(x[2]) | |
f.close() | |
NN = max(N) | |
MM = floor(NN^0.5) | |
m = [] | |
m.append([-MM] + e) | |
for i in range(k): | |
ttt = [0] * (k + 1) | |
ttt[i + 1] = -N[i] | |
m.append(ttt) | |
R = matrix(QQ, m) | |
flagg = int(c[0], 16) | |
while True: | |
a = [2**976,2**977,2**975,2**974] | |
dd = [random.choice(a) for _ in range(10)] | |
def Babai(B, ssss): | |
def Babai_closest_vector(M, G, target): | |
small = target | |
for _ in xrange(1): | |
for i in reversed(range(M.nrows())): | |
c = ((small * G[i]) / (G[i] * G[i])).round() | |
small -= M[i] * c | |
return target - small | |
M = B.LLL() | |
G = M.gram_schmidt()[0] | |
target = vector(QQ, [2 ** ssss]+dd) | |
P = Babai_closest_vector(M, G, target) | |
return int(P[0] // MM) | |
for ssss in range(975, 978): | |
posd = Babai(R, ssss) | |
flag = long_to_bytes(pow(flagg, abs(posd), N[0])) | |
if 'hit' in flag: | |
print flag | |
#hitcon{recover_everything_by_amazing_LLL_algorithm!!} | |
print dd | |
exit(0) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from Crypto.Util.number import * | |
from secrets import * | |
from math import sqrt | |
from os import urandom | |
T = 10 | |
def encrypt(data): | |
num = bytes_to_long(data) | |
p = getPrime(512) | |
q = getPrime(512) | |
n = p*q | |
assert num < n | |
phi = (p-1)*(q-1) | |
e = inverse(d,phi) | |
a = pow(num,e,n) | |
enc = long_to_bytes(a).encode('hex') | |
return (n,e,enc) | |
if __name__ == '__main__': | |
flag = open('flag').read() | |
print d.bit_length() | |
for _ in xrange(T): | |
data = flag + urandom(40) | |
print encrypt(data) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
465 | |
(61608417975397048843788515638593839325111098880518441270527767841153782846066445099077365303960932518098100778959123136871039627996767023258612684873083420234538156646585282154245553305607644427220207313162116929585370583379703086997585339296145409828300576290109728682441066135201997295424597733433471586151L, 60032368056605168202792776655067640210910930719068898740685488293392455428589220656480049668823171895161714617099267690524276842795335016835073541061601545456195765907623303970146386500563913899580929779870429659650425339185233299118860275385880359287380867251468679962048998842668813298548390941601249105855L, '1e4433543ad3eab1d5a5490e33ee98c34785945c7b69dd0fd0a371c28e5ff45f6627ad0559d9837fd6439367543ff5670f4df4fd36cbee75950db62e51811f98e3f34db66b07196a5dfbd9867952d8e6d67c43becf086087181e5f78582e98945e5c8c08d754b998ef01e836729f9620cdcd2cc8aae9cb4bf3d8e4beec3ca8fd') | |
(52084595054768217522676979342755393306305099169414947960508049057119329537162079071100773540172780699842974838973453517862170568297372572652378982794735495836797191260523386985555538123219596180065060457770169661533302156160201909218943628670173938802399175928847179180982290051008255643478089280887936398779L, 15937444970326662770243305998311639639802081677519521519037892156989918335411343952028567001158781869582357356721336548356177945486289103616332672857562241745733313956089488246637981047367689313876169403573606972534488436195086998111247112950511965259280728899941655052549135516189815880662766290132607874671L, '15dbeced76ab710b84982e67a839846cfe38cfccce4dacc585df0e38d695e1c84eac7281d8c83b3c6eebfae7c27d91496b19de120374d08cbccc251a464c2f7bb10fb9d1c1f13b78f1fbfe0ce37d01350978dcb192c92db43560a9cd81481aa2e2d41a8c5b3c67d3e3ae4be50ddf37a5a0193da6f4befe71d5348bd7820f1b0a') | |
(121675354261226402523384817752122501670754379029920951567545832861118347020889141951034949457467042630795199347469665294677977729959566390358589470405088739543312116123816666440234661644847943610733959265939955886506334607329368744886743083353218982597246897307234102346047327550059519916639261619453107169923L, 1958149621008109700386193021020256359555810444022322757777842537494487439895477039590251808463946583928481366538370998263830913239177109491659797444270949612728937519312683847609162235917948298810271512469482956117395111528004250206351805086758526770795159863075378020975086922955262230095667701740508170151L, '5b445089b4578b115b0293cc1922f5fdb784701fd533eec7ec9bd7fdad995baefb051b9793ff3dadc24ff8d5b52c89f9565f65409c58506c7e79dd787f8e388f019497461fa3db0eac5284d398f9e6a1b81c59ba74677cc01c38ddd6461df029e1179f3ee63ccce20f3090835b7bd7b4de25c38ccddf2ec622cd41fafb49d68f') | |
(70820434096887624688036248070441718528107270792728727307197623356369639890276828895683705436125317302252834211775910545775001651922925694194466935425170969939539346172633115232030274859268960310846965871663926227518137713901150141826470260092611613639370170779217268337906342955347156686598981918675591938393L, 6264211827826908864953215815104077572906230669747226774603059704547415338199956437981145121700015020477626176620200121575740530313039227764537541481272011717745292622796843631960318813842515397395192806936521180850750841260559451018598913158548097304919304754876270597286947644956943158352022152801127867879L, '4f56516d8e197a8fd6ed76433a836635dd5ad1247be9ccbb5a88ea940f5746221b4bb5b60ef925019a11d36fbe8f1d948e9afb4305937d7e017148b8ba324682d60ed6fb7f3de80031432023bbef81a96d0c1bd26c3a728bc6fdebbd48bf86b93325584c1a1386e26374c9747754b858a01b73996cea8fe4edd2a8130504e63e') | |
(82396665631738285668995082087133930047188890932442133336046256534530991902128696466596278088102928917626464109384091264437455382690583003229076491363732222934817133536320704449557698925700841043105303694696203472531025908797520768019280257689521302427077849286757365739653728248123114986191011560571298134089L, 77541341309162852568860774868359137598587882474829780783306540898574011860779494674673722444562346968736216806881154962981695851598965376893425170303668270087989094501452417979429678869102952038600630142304872749698942475289176861137563927160985001506014089253274664444041660282426708388957971134224538326179L, '6b35dffadd327c0999efc909a3c1d1482c6a286808801095eec5ea88224467881b4081c1aef02c273cc5dc4d3505dc50fcf4ce60052b6a5a9dc005faad4709fbcca254c6fc1c552d51c8e15fbd8fc404b0136758e1ba57f6c04b1049e303a43ae60c1eb0b671289f6689d1cd104c407549c1bcfc081a28a3f3324a1611e81555') | |
(64885222129962661919689742957615146346855998523264787345799887210230045803423356080820154546050540728264000944692170729880161760807788699983366314269171423680987673788784023826885067996007133127166699735414920427997399513922777341273346196540175237091469555617281522541592407225697228219483666768990986901207L, 47625666889348051674457306461777570860477708163951567694477110559722255361844497439523737482859577232793119885759760321686098657292699849459852343686370029321619072315457562131610624443702007471950020751311592439673932509558946203816066868221203483167079506399876187240483994566182748627389022243608934595071L, '0f79419a86361d668ced50fbcfa521c5117f7b2f72c3cc248dba4b2b1c9e7dc3a32fa500f5167a0360aeefcb8daa973bc67b0537d641617c2d96d98ee27179de1644b480c120b2d14054db032b42af33b23f8182f72cc8e752d6f89d556800f637bc492bd8eb2fb294eee61bc3c55677066b6962c4d2a1f1896703d446d903f3') | |
(130307595686638523389042871138355252466828093625912424932382409748014813151912412889866698513547588105179569464359905871041351306187955332098310075195714887141180801001191398677311128761953690562878908997464309620384635922453765468745206262477334243233099872249671186622159533482223573972729351847574480258349L, 15517881429792452627724339825487038872077384939873021432131971858090290889497162855962736652640866521963165312583164013911162455865793567436833813352448640307756786561236246631146444590597902995591016928432988304077340670079503467394770901559567924809126517090243024890436892801283564005789256977822007581731L, '69a8e0bb49427f3465c9f3a41a22e047bd348c886cdb07264a321f8b890bb48cd7a878e43c1eb4b2f496dafb50677b3eea032c8f7f2ee59695398c56cc3b183bb6e2f1ab2d5d633461a6592ca0c98c0f2dae4100d6aaaf0d1166bdd46beb68b07d9c9cf6c5a92ef7db019dc065b3a8300ca25b50cba51a3294d954c178bf3770') | |
(65386448419573832864151040666988491321490532636782967162806795276671017479566436411594017000387653366263378617189553041765586083217125727980734225153709370447270596363822524978426540069479632490507360491377612488876553715272119578498102854909764339676652952568021321118127618560269626549257296451954041925283L, 62417639911670877600600895776941278119707067464948560335387709799367122896567813566638216057171867961437006927011778910808189676129022776796728833211435603542364704330783289218396426543693678813151580911213239650850603907199690825764030369692366216968117035006819175280930722880390482701178418013436415892711L, '2231e71788fe0fec78ada4f24a58bbaa5b1a0fb48dc94b18bf7409637dbcfd8e2755d80b5e4b309e20a69474a6e2eb245e40c1b3f81c6151dbf7e6871e90a9616a32f4a8443d30bfaaff5d711be39bc8f38c13234af9fd867f508b8a6b097a49fb07a1392ec08c38f0939620cf644ec6631f7566b6bc7a1f1d01a9c736eceda4') | |
(131618812326147470215836136712095159211663684841466199972335887950664101678748935713203393931245541362772506324940879455504378545672259298894346211770983161798960234145317156224604949365110464634198678301644727985645228605590810190481288852412139519629077007437022950591320600450976104529132138396249413028099L, 14318453997383587408499979509282945054981178882287936277795320451723285671391694914929520724692059461777785480850364952738183846512279857119933447174333240691522012746191524101263192457454032837995702952840654708026147079321112397181981380295129696518148352311994008219805602114421675331461920408832158576071L, '71a370974f020d338071e2b0480f38f2d5b488252f5eb206636d6dcd3c93ea586a507c29d2e611a9a8d5d0f849b913116b37e69345d6eae71cf87cdb6b74e75bccdb374c372562777a727f07e4272a5ff17b451d582074b565879453d028c5e9b91cb67ae923f0f09492e508422e65c1daada0564d91a9feec094af77ab190fa') | |
(99041226655569332839951771030354960649881033648844611842019981984694036670092050113949713459076512100815903654289240773362239468428010238444408944822516190193861719380849620966232652503444079295871086550223067647300451354087943235559953597249075277760677450645744584993036921709483731953822197438848939991653L, 45917328654051873455626365238806652384056265616606200025887647202756379007355041189714541493038574645714670682101129613041399879280497291675656671383417575172090283625761438606371062142083212903854592596935358334738253893062615061401134834123551055465985828525720791523020773994634134135284036947641526947783L, '336e810e66eeac255f1714b290187773de92ec044b654a4cc0eef2070e9d8d86fa37d424b2e4b71fd135e634034e06dbc31e77bd13d470aa5d3e5dcc5e689b565178a4a445d4560f5569967315a0bbe163ef83063429ec8d1fbba1a8dbd9e30a2a67e17793f8b19e7b184c3b989dadc85b7f060e3daefb66ff803c98bda8862f') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment