SHARE
TWEET

Untitled

a guest Aug 15th, 2019 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2.  
  3. from Crypto.Util.number import *
  4. from fractions import gcd
  5. import random
  6. import primefac
  7.  
  8. def encrypt(msg):
  9.     l = len(msg) // 2
  10.     k, m = bytes_to_long(msg[:l]), bytes_to_long(msg[l:])
  11.    
  12.     print("Step 1: Generate p and q")
  13.    
  14.     c = 0
  15.     A = []
  16.     while c < 2:
  17.         if isPrime(m):
  18.             A.append(m)
  19.             m <<= 1
  20.             m +=  1
  21.             c +=  1
  22.         else:
  23.             m *= l
  24.             m += l
  25.             m ^= l
  26.    
  27.     p, q = A
  28.     n = p * q
  29.    
  30.     print("p = {}".format(p))
  31.     print("q = {}".format(q))
  32.    
  33.     print("Step 2: check phi(p) and phi(q)")
  34.    
  35.     s = 3
  36.     while True:
  37.         t = (p - 1) / 2
  38.        
  39.         while t % 2 == 0:
  40.             t /= 2
  41.        
  42.         if t % s == 0:
  43.             r = t / s
  44.             if t % (r**2) != 0:
  45.                 if gcd(r, q - 1) == 1:
  46.                     break
  47.         s += 2
  48.         print(s)
  49.    
  50.     print("Step 3: ")
  51.    
  52.     while True:
  53.         y = random.randint(1, n)
  54.         if pow(y, (p - 1) * (q - 1) / r, n) != 1:
  55.             break
  56.    
  57.     print("Step 4")
  58.    
  59.     while True:
  60.         u, v = random.randint(1, n), random.randint(1, n)
  61.         if gcd(u, n) * gcd(v, n) == 1:
  62.             break
  63.    
  64.     print("y = {}".format(y))
  65.     print("u = {}".format(u))
  66.     print("v = {}".format(v))
  67.    
  68.     C = (pow(y, k, n) * pow(u, r, n), pow(y, m, n) * pow(v, r, n))
  69.    
  70.     return (C, n, y, r)
  71.  
  72. """
  73.     Get p and q based on low s
  74. """
  75. def getPQ(n, r):
  76.     s = 3
  77.    
  78.     while True:
  79.         t = r * s
  80.            
  81.         while t < n:
  82.             t *= 2
  83.            
  84.             p = t + 1
  85.             if n % p == 0:
  86.                 return p, n // p
  87.        
  88.         s += 2
  89.  
  90. """
  91.     Get the length of the flag
  92. """
  93. def getL(p, q):
  94.     for l in range(4, 1000):
  95.         m = p
  96.         m <<= 1
  97.         m += 1
  98.        
  99.         while m < q:
  100.             m *= l
  101.             m += l
  102.             m ^= l
  103.            
  104.             if m == q:
  105.                 return l
  106.  
  107. """
  108.     Get m based on p and l
  109. """
  110. def getStartM(p, l):
  111.     m = p
  112.    
  113.     m ^= l
  114.     m -= l
  115.    
  116.     while m % l == 0:
  117.         m /= l
  118.         m ^= l
  119.         m -= l
  120.    
  121.     m += l
  122.     m ^= l
  123.    
  124.     return m
  125.  
  126. def testC0(C):
  127.     C0_primes = {
  128.         2,              ## 2^4
  129.         3,
  130.         13,
  131.         47,
  132.         103,
  133.         151,
  134.         15259,
  135.         2640721,
  136.         68362159,
  137.         110555953,
  138.         197119171,
  139.         89990995683347761,
  140.     }
  141.    
  142.     new_C0 = C[0]
  143.     for p in C0_primes:
  144.         if(new_C0 % p == 0):
  145.             while(new_C0 % p == 0):
  146.                 new_C0 /= p
  147.         else:
  148.             print("Error on prime: {}".format(p))
  149.    
  150.     print(new_C0)
  151.    
  152.     C0_primes = list(primefac.primefac(new_C0))
  153.     print(C0_primes)
  154.  
  155. def testY(y, n, C):
  156.     v = y
  157.     k = 1
  158.    
  159.     while True:
  160.         v *= y
  161.         k += 1
  162.        
  163.         v %= n
  164.        
  165.         if C[0] % v == 0:
  166.             print("k = {}".format(k))
  167.    
  168. def decrypt(C, n, y, r):
  169.     ## Step 1: Find "p" and "q"
  170.     ##p, q = getPQ(n[0], r)
  171.     p = 4989129807835323600925746342351281749069253890019283025402600890078410481678260058327124935005055779504414139620146353163761641806444116972362222821271659018009275851165000503930797080375589643885401776592275121720807974563860615379616678611018107562091549120410638211902961097342872212922933696839364069012148663591392874188383589140455692575674446981058585856728101285007125492241010410452717975061191654062084020296669436540181029444450760983404908237185628800659695824554022178700743316668627544724772994293513764634197959290760375263606963894824905274337388727359093888808424387730351084512353391959848203541283722812369885629
  172.     q = 4590273446006533208343516816277046236179992023980522524205207608767005433305196964536917482331251108291516010603825289345601405300050545711449239478634796717371308695234558160245281778154285870464492088850850702966418131469793663515417856271740812372001655523408087500415191138359305960422212628189125689345087221756566093698407625389074466150946420903675172836548704299366241354277690275964957433214081355280546631440579995556034593116442847932138178563317604424947579693416640440592713056187675694376805138030329425433235942347269528892457438092463169471190349268102251711741082187113718811278093114050962855184458545748748071079677303118368611752753108709925358889396492517351103129891337708493898332645448192325357554698049562497884376920923042623482695966282850687237111786183887292656724661739868107095427029274170999356517718477205431908442830553873566411183348827741072744986427064459741622457295138485568669953445889291633183006610699428694513689941532674712884190622162689960473566635209583037541562168186691995467519273074301445066932407874607065909174462443703918952310037263647630272466794266177668299540637067280581268917190033770903048222865459973828954470534945499905205864610632913408130458485381679569791879214602894256512108104101848432939231467
  173.    
  174.     ## Step 2: Find "l"
  175.     l = getL(p, q) 
  176.    
  177.     ## Step 3: Find the start/end "m" state
  178.     start_m = getStartM(p, l)
  179.     end_m = (q << 1) + 1
  180.    
  181.     print("p = {}".format(p))
  182.     print("q = {}".format(q))
  183.     print("l = {}".format(l))
  184.     print("start_m(bytes) = {}".format(long_to_bytes(start_m)))
  185.     print("start_m(long) = {}".format(start_m))
  186.    
  187. ## Test case
  188. ##print encrypt("CCTF{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}")
  189.  
  190. """
  191.     flag:
  192.         found    = XXXXXXXXXXXXXXXXXXXXXXXXXXX4D3_1n__m1dNi9hT_witH_L0v3!}
  193.         expected = CCTF{XXXXXXXXXXXXXXXXXXXXXX4D3_1n__m1dNi9hT_witH_L0v3!}
  194. """
  195. C = (
  196.     5819292070406480811085660820121684985671629268018963982132536699725647918843283694617121921657838931587101590225263760024799793666517031049767630232605122310529477605044076653736529248800774468297886615085030594432380847056189731315409731283752811072465752766318724146451284304314421495539139626212954729438375907689028974223487961879300249316612242162890406934261715918744938816853884050292264330948330902633980432425294661660287645035512039258681080499048411965525947548130486656202195647728384616392349473002223694045570381580510054779134953039267119942667139562502015799350564249653361382194056520903470871981094611660206917710789757549586120158795670914693402750868070741314457624046296347187303939933952159335917103694118549822872185367357755110792988913191120997206682273033849647061483203518695842397743707624620823282999677524756575986173681443828302469098034168541177590265549317122216323562107520225822489858946300040305874928336538133576101128005661092143038349201512499962051895930781804095131300032451621952359536735758908540527106343054342352004997117132636910890760683649239577925459128980587945439268593440080576412987235375296552246816594028907321252568696589767025817426672255232185566211159416781052908839560435439592344070514988677275792232291259493470989645777198348183707530071986112866025861507507293282555572393736403021191275200011557806632914161739092322797126366326880758833269190901390777902624764696676799045667548935235846103780176434211711042546907973596291660624111891897882121640597416584365822571797167976546217166782848372881172967140559116219002220758042083132267287332733095909998101057886942602782420678728385733632549463069441859713095341841263204399996484627230930495780152662881791086967193412211073914858633407954957392134229626591235753422513781222601482079166627442563492252465989673544780856689749791552432968071894542470444953966340722026439262874806578218108212805575296394124014059063346511501465233174424553743244834299730521074927357222563004309783013503537621854277624790427286252823592755422496440291829481461141794527795567890732232048685353277684375890933236210761636976951373429789765290721652175032915510711042189843137201960438201705770971452222179036510108306111390318347627485301737860144780745415070806437561401757688909176794002955940565957759931658379819996107749478282860515691329179949375707667849755047628940381003273071984489251884284163068110275687439102223247813822799489347482551930642996104010307588397484155030595223014402307489909363357504547266040612693529697549234609457495272058691613157324613648595751495060142815170695119886468538117923509463632493113912974748677417734639419567776490823601639260359950035067616284983360475339561146853781432030578134499928922633486387783231236263486550749530420687999348754243990353938896076784784115224271778635535304299832539285302676774216355501732118875024844918895203010157681349372002035882381154655158609028671308979153050701254433832327379211621295135790115503306060741723412738435867074507726821018542947723591179747893082809653110140759326602376498218954253340544089735729960444612527501895410641744102795623394176304835079027520592500925579740801941260177284188463945903092219173434427990166967392697468131543297211045810960058276528502314853850891761192735546999176584306867768937250557951179292989154986420543825445478242672288134687427693004772276163591596575478779025940385891547185787883692649010820449394227046087526056976303918444852695549589995104694411608392601080838563727218725386389369918792759973643595398969001982565833270145386463891413223016684320940162653802262517525535895773423356478019875486565058647863418765417008131830367985745270295698747377377799371091638207634185189756636131450731797853882386841201892812037224644228361650995093607378032L,
  197.     42591871242043764312889725473599540968721967847487118892806947687396759345047650671701272452867254703101933138402472893794078187175223279057089672802535748008824393440274898969124460997397136014419596722259259467131682592003059959838263251382628656724042283019690685598097209635533789687123202710278326217200680696006296754706527107358548654940081127522938275248730789610638131308966863577712614387764806009517533347009404594095337590797010300035605661917619230188574920434116132317762671972985008289923162437637972035621816516415154344818193064934247903076481406644131584916119529681544397278048232997002514257600817233537223005250782800900862975891241522299348281793149616585879593587643003174676946133114024876401764715672846817436725539235886571005989262164121904059348514363447418044906192691825583226219690050160204213130637805270835236084681393346173925249654779833645576168961655919131742024564667055496572810709314258252026693591751631020395465338760039512512625265501223693990232234938721973577035039639422857724722241244219075097915759204320702558651624292330707869362202068110703802820211303456417233476619859786254835501987660277859941481168283834942905879716364677206312966148996005381383787026068482297199882717559480227972393821151548007002895737922065277438120865996765975976373928293266643635907136363779629169220406278690324111172738353262065923175151632550502254689329058794181498322982309988580275079459888270688780171478791411901165759879281068353023126473808361748136602399751609161258126008479929908131647422532713691212239438890355312189612781853128849634451684075517832071372777753861419442310160439528504116993455035380482201262236751918450366473306889616312449901725942548546898891953501092719620964132040185109027000058945923812744645731128584716078937001951108114250273584387694377590089430531036002756294335745544317449353952451145017620820019489070254180875046647636487865500183424420728884964109940623638807093376578589137410633364316244259353373926198278798937334594779039110173145698451438009159713979467959905770376957512133505842266643423136592946260507540393093693555003241730230703316464931465262440329882857162767788824748579495539829963485361398099800325714715180628514788721574888324906364659735222548420309100711988757680008322180752785365366613683406513200870778763112603056706058864729521321612248395242586709554379266160898066914781315022621975688074271069291378908208942817904379924994967912677565347313056801217115410249691347678930982784275233587320764033692635025050586382680322230412648231493385801342469998629490075497459316590695253250852522102562896382023608240472614421830758336163445950437342775147997754243049338216472484138441386106102455724617669339180196364502566006496348438923386230500593045643621519758600959515196269683678706897371707788528245952660168407131177650587897024918612308138066636441296025126048142263202427187233121724504506888079882445095609049563314505860134260843811916778942517557207718878748734646890476217095431906590480563600795230745306969278670988868152804407916766754744991895614002341942429933138953722729361958746136078657707114607838465711904466466497455947276961424615175872305431698867786127491920691309470311889898923192239444343254869698430488028866276175366099056773676917969558368667172395875406734885882275011293929377837133179849001626714492739376722828045430235928756733795154725317099569785039661942992149817590486825552656118907520921938559749021643847860713515842103304938520212065697023320753475431939498462310825862808245392724026292529354265811824784519275393655558572759489637214584156751623845837061060502775987223868199132062599604484324926337140340368512159293682064959353712609159997258461654745468486450074897480648147417401841594682732200600077386360652032956955958073163581528L
  198. )
  199.  
  200. n = 22901470075586163690633992639439372561020701798561430239687182111404103947309528645474113376751937467528705222925755112370375340596227149450841522137427355465951647892881106276332077300795173332800487209993879493989749770371789808085177037727140058086545528411223842686949104460730246644503569399288591937966908435240758176085274406815178288650300808822756249423905111348654552649605757674737877113443398895684154646297670181315897873420523883884051295690182671322252355276150669519860981566321380739367120151193946408398717798117449961228410215696659671670262226227947720857456077859381496897939844602125983820480917361702633694369086686835873705989745696043112334486777426147289566573858186753066864969153741456819611168061466138425425826866927235547587919751425226204432655502606058839221265757385213745176417426595957424725992058995248443744232581968935439662413808892346156057399157107255262593458417475052313391906067156837551581497479345336579203469805325850859285282437014529438169286362822872931716870211802932716243444389403315756757545415929013938026835614312338812600389900679163573931510515492209933890492252894985158916406449158440219991013321058253642477274699828980358027352111926621443095121426651206072827433757475929988055190893754904351277375987381993175172224704275194456434661632705024474260143764560481511028398144570613447985150454314341884433041515987833827225208366598460570400720770955869378329974766086867347863142127368999117395667985569204202057041831387359452486864768620963242878877376406627721303142902228036997455589625545384798015741453576603317596780677929357220705940802024985112544299896635889587847372269860560933637134603525698082435442671764338421714398733968431234998292149511290511024036363562513147872638425430813289870576733272718485404675723152659702360991422943416793000331948226827635948929947231998535939880856176164645121046511616517153947887743L,
  201. y = 11341550253591515592253525644318909255152188969429451555247549138582371475814732832006293670957254888623470733947605373849593119362683467553950252447391336253195071150588516074029292410929204746777578846637097984609588506161422544375869014493030986219989786489284433759978403907687960686411036833062895481314735087303803876329941664745795211398580620722529127821835039920725766530091932133950795341479543173536153171331682467585533100374930470287594151476317008307942433730918325379827642671328044536867935903012977284498705803730072753950278181794221930528212331361041566988192760383724669444368662866030422503477788222688516426843428708196231198900743967590462057978617887524786689253106450912277212419121890535066392701596812926250685513072282531292102342928300267683749758121971295503186625074292976190370565133079075264910226423081463273949265406107388912597884568469479942323478668882101599572312623738625036827308164047116897101082108814212712243130596209016601155129013905631836404282063417316549462183978508829843270391864051961940063355835581126785762932149492228910547323764081874287263417341427556288288704346101229608846188046617030575362118529701681341859165740848518121264417293222215391457695147913354344143291815066272938945404583376435533766509383667580389746434725534862869432056321398516657654739395678314625918770747026326096986772060737617801413115252716571890167481214366976849480377882535284443175018934448724593201029429298461640402890808740416352907037800488801738376254039564723432365740297285513712757238930874333628812434272208335495292968724440115719349996654417275249397197984258847952906080656329202086991035119393747461191344800729153464210909557139790320718033258901581094565580206972369431460161598065953281088625762814976900396390196204324727036094049533640079010595297970502698442162113164231771443001820971480409696424050175562257124809822866826149874231435L,
  202. r = 29006568650205369772824106641577219471332871453600482705829074942316340009757325920506540319796835927351244997791548564905590940735140214955594318728323598941914394483517444790295331862648776999333731259257413498376790549789887298718701619831500625360997378607038594255249773821760884958854265679298628308210166648787167873188276681049161003346944459192201080562372681889576311001401223316585569622448788686407465234282961840349889706072388145252354117658055981399184278049732687085469437887608299678632401129613452119966267205178839391067482348225726193455449934461390080748886188300757855142513682511394466299658626295420755149L
  203.  
  204. decrypt(C, n[0], y[0], r)
RAW Paste Data
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!
 
Top