Plaid CTF 2021: xorsa | szymanski.ninja

xorsa

Category: crypto

100 points

XOR + RSA = XORSA

File: xorsa.29fb8e0ef0173eef5953d792373b7db98169018db6747f5e27d26c1c7cb98873.tgz

xorsa.sage

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import p,q

x = 16158503035655503426113161923582139215996816729841729510388257123879913978158886398099119284865182008994209960822918
533986492024494600106348146394391522057566608094710459034761239411826561975763233251722937911293380163746384471886598967
490683174505277425790076708816190844068727460135370229854070720638780344789626637927699732624476246512446229279134683464
388038627051524453190148083707025054101132463059634405171130015990728153311556498299145863647112326468089494225289395728
401221863674961839497514512905495012562702779156196970731085339939466059770413224786385677222902726546438487688076765303
358036256878804074494

assert p^^q == x

n = p*q
e = 65537
d = inverse_mod(e, (p-1)*(q-1))

n = int(n)
e = int(e)
d = int(d)
p = int(p)
q = int(q)

flag = open("flag.txt","rb").read().strip()
key = RSA.construct((n,e,d,p,q))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(flag)
open("flag.enc","wb").write(ciphertext)
open("private.pem","wb").write(key.exportKey())
open("public.pem","wb").write(key.publickey().exportKey())

flag.enc

Binary file (encrypted flag).

public.pem

Solution

n = p * q

x = p ^ q

y = p + q => p = y - q

n = (y - q) * q = > n = y * q - q ** 2 => q ** 2 - y * q + n = 0

Ok, so we got quadrant equation. One missing piece is y which may be calculated from x by guessing which bits were zeroed by xor operator. Fortunately, in case of this challenge the search space is “only” 524288 combinations long, so the solution can be achieved in short time.

Just for remark - n has been retrieved from public.pem. It can be done programmatically or like in my case by executing openssl asn1parse -in public.pem -strparse 19.

I’ve used sagemath to implement the solution and to achieve the goal. The source with some comments is below.

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util import number
from itertools import combinations
import concurrent.futures
import sys


x = int(16158503035655503426113161923582139215996816729841729510388257123879913978158886398099119284865182008994209960822918533986492024494600106348146394391522057566608094710459034761239411826561975763233251722937911293380163746384471886598967490683174505277425790076708816190844068727460135370229854070720638780344789626637927699732624476246512446229279134683464388038627051524453190148083707025054101132463059634405171130015990728153311556498299145863647112326468089494225289395728401221863674961839497514512905495012562702779156196970731085339939466059770413224786385677222902726546438487688076765303358036256878804074494)
e = int(65537)
n = int('8C6DDBF9A2DD53A2466FF61BB62CF5BE3AF89DE821BB75A581ABC8514A84392A6613EAA3269C159843EEF781DF5522A92D2D5ADC3C95'
        'A54C5FEB427D082C157D4F2DB6901411C0CE29F1571573FB488885EEC8D36F8C79482B5123A82047D79588A95FB2C1A1671042785F5D'
        '0C1469EBA21858D643F664659F9E6303395A05DABB0503F2E880A899A67E7840BD20FAC2831693620928D0C90C47ABD695D00D27E48E'
        '7862A3150159AC58E50B64D1C9D46CC7C6C195DF61EC0FEF79937F5545B08A53517382C07362FC8A2475A99E9CB41E4FC544A700E11C'
        'A23C658ADFCED9EEBB795E3AA5A332D1E39BC728D8E039F07D2B2BF93C4E1120A3D4CB1B7AE1E0D78CEAC37595F0BD994EC78EBF8D39'
        'C5FB12D803CDF9BB019A6FDA4D20BFFDE8FEF052A6189433EDCF94F6D7BB6A8D9CC1919650E0139B6F284D44BF1D672E5CE8A56F2E7B'
        'D3E2EBEE6FB7F631E0039CF5079ECF74B1C7565E6058B81F46B5B66EAF7F834E942CCE5A6CC3BD47EF4BD418B179C1114AA0FB68AB3F'
        'AA91EDBC510407E10524B3790F04E3B27E46EBC25E5BB2B934D4E46BF09405A567F3C7E77CE3F0AEE383BD0C8D72ECB2A399737C3FD2'
        '79261BF27B7CCFEE8BB2141E202EFB78687D1585609AAF7C2C6F3597F84B003B55A9F2EAD1AEDFE00056CBB5509942C288DDD208FC05'
        'DA803335B5E062B2709EF59FD0E3D4EA217B8F295D4AC021FF37', 16)
flag_encrypted = open('/home/luc/Pobrane/xors/dist/flag.enc', 'rb').read()

# solving quadrant equation, if successfully -> try to decrypt the flag
def check(difference):
    global x, e, n
    y = x + difference
    delta = (y ** 2) - (4 * n)
    if delta < 0:
        q_candidates = []
    elif delta == 0:
        q_candidates = [y / 2]
    else:
        q_candidates = [(y + sqrt(delta)) / 2,
                        (y - sqrt(delta)) / 2]
    for q in q_candidates:
        p = y - q
        try_solve(p, q)

# flag decrypting...
def try_solve(p, q):
    global e, n, flag_encrypted
    p = int(p)
    q = int(q)
    if number.isPrime(p) and number.isPrime(q):
        try:
            d = int(inverse_mod(e, (p - 1) * (q - 1)))
            key = RSA.construct((n, e, d, p, q))
            cipher = PKCS1_OAEP.new(key)
            flag = cipher.decrypt(flag_encrypted)
            print('')
            print('flag={}'.format(flag))
            print('p={}'.format(p))
            print('q={}'.format(q))
        except Exception as exc:
            if str(exc) not in ['RSA modulus is not odd',
                                'No inverse value can be computed',
                                'RSA factors do not match modulus']:
                print('Generated an exception: {}'.format(exc))


def batch_try(jobs):
    for job in jobs:
        check(job)
    # printing something just to track the progress ;-)
    print('.', end='')
    sys.stdout.flush()
    return

# preparing bitmasks which reflect bits negatively xored
xored_x = (pow(2, 2048) - 1) ^^ x
p_plus_q_masks = set()
mask = 1
for i in range(2050):
    p_plus_q_masks.add((xored_x & (mask << i)) * 2)

# prepare all combinations which added to x may give us p + q
jobs = []
for r in range(0, len(p_plus_q_masks) + 2):
    for i in combinations(p_plus_q_masks, r):
        jobs.append(sum(i))

# process the jobs in parallel
with concurrent.futures.ProcessPoolExecutor(max_workers=8) as executor:
    for i in range(0, len(jobs), 10000):
        executor.submit(batch_try, jobs[i:i+10000])

flag=b'PCTF{who_needs_xor_when_you_can_add_and_subtract}'
p=2042096967947189110867834870665601474658393495391177987563842506235460819158718352795066916473070093427296418249578795
330442946868976299132283455141564512670837651674068083241784228622842032159395166926105153674797245788486313731088428240
849049757569832542354728786048517758003000107722013898635877629617191968726636473303381965204082403846202326487548625234
742652291676372480889884141038768570943164453161845659957763397266633200741543084158996104497651924550914951529693056460
845395739986036583533836155624925414948587026095974413146123324854691326687513720581422489526741353073424050946436862603
6706116974009128413
q=2805453942749461961814968990559607642985698444564543366951615629041822542141051778777966851705529013385264993613982786
480436268801211833388417824272775294451907404859036075031861237853943815966278635332637306288483526480137185909944884547
362442066339043338586251910554553253645326241592431627938537482222440671747353813124439785657101598480873731181099268355
636536722644245903795642301286450578793982438797576298881611860914666356095768828987955573407573821083419656087491373740
914298717584660758992156362258050568069500431420123894358244028086055361600414678231738314486859729524989582162003747866
2736479377036405283

Surprisingly as I’m a total math noob ;-)

Flag

PCTF{who_needs_xor_when_you_can_add_and_subtract}