# Rsa padding (Crypto, 303p, 47 solved)
In the task we can connect to a netcat service which gives us the crypto source code:
```python#!/usr/bin/env python3# -*- coding=utf-8 -*-
from Crypto.Util.number import getPrime, GCD, bytes_to_longfrom hashlib import sha256import randomimport signalimport sys, os
signal.alarm(20)
m = b"xxxxxxxxxxxxxx"n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941e = 3
def welcom():    batch = """ _   _      __ _         _____ _______ ______  | \ | |    /_ | |       / ____|__   __|  ____| |  \| |_   _| | |      | |       | |  | |__    | . ` | | | | | |      | |       | |  |  __|   | |\  | |_| | | |____  | |____   | |  | |      |_| \_|\__,_|_|______|  \_____|  |_|  |_|      
_|_|_|      _|_|_|    _|_|          _|_|_|    _|_|    _|      _|  _|_|_|_|  _|    _|  _|        _|    _|      _|        _|    _|  _|_|  _|_|  _|        _|_|_|      _|_|    _|_|_|_|      _|  _|_|  _|_|_|_|  _|  _|  _|  _|_|_|    _|    _|        _|  _|    _|      _|    _|  _|    _|  _|      _|  _|        _|    _|  _|_|_|    _|    _|        _|_|_|  _|    _|  _|      _|  _|_|_|_|                        """    print(batch)
def proof():    strings = "abcdefghijklmnopqrstuvwxyzWOERFJASKL"    prefix = "".join(random.sample(strings, 6))    starwith = str(random.randint(10000, 99999))    pf = """sha256("%s"+str).hexdigest().startswith("%s") == TruePlease give me str"""%(prefix, starwith)    print(pf)    s = input().strip()    if sha256((prefix+s).encode()).hexdigest().startswith(starwith):        return True    else:        return False
def cmd():    help = """1. get code2. get flagPlease tell me, what you want?"""    while True:        print(help)        c = input().strip()        if c == "1":            return True        elif c == "2":            return False        else:            print("Enter Error!")
def main():    if not proof():        print("Check Failed!")        return    welcom()    if cmd():        f = open("file.py")        print(f.read())        return    mm = bytes_to_long(m)    assert pow(mm, e) != pow(mm, e, n)    sys.stdout.write("Please give me a padding: ")    padding = input().strip()    padding = int(sha256(padding.encode()).hexdigest(),16)    c = pow(mm+padding, e, n)    print("Your Ciphertext is: %s"%c)
if __name__ == '__main__':    main()```
The only important part is:
```pythonn = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941e = 3######sys.stdout.write("Please give me a padding: ")padding = input().strip()padding = int(sha256(padding.encode()).hexdigest(),16)c = pow(mm+padding, e, n)print("Your Ciphertext is: %s"%c)```
We can give some string input, the script will calculate sha256 from it, add to the flag and then RSA encrypt.This is a textbook example for Franklin-Reiter related message attack, so we run a solver for it:
```pythonimport hashlib
def chunk(input_data, size):    return [input_data[i:i+size] for i in range(0, len(input_data), size)]
def long_to_bytes(data):    data = int(data)    data = hex(data).rstrip('L').lstrip('0x')    if len(data) % 2 == 1:        data = '0' + data    return bytes(bytearray(int(c, 16) for c in chunk(data, 2)))
def gcd(a, b):     while b:        a, b = b, a % b    return a.monic()
def franklin(n, pad1, pad2, c1, c2):    R.<X> = PolynomialRing(Zmod(n))    f1 = (X + pad1)^3 - c1    f2 = (X + pad2)^3 - c2    return -gcd(f1, f2).coefficients()[0]
def main():    n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941    pad1 = int(hashlib.sha256("1").hexdigest(),16)    pad2 = int(hashlib.sha256("2").hexdigest(),16)    c1 = 14550589053226237723784378782911157204367764723813789158271625147472004207734354619642445255036997940341703539883653916130592718879734436263217819317202435434496341973502556894834798718992952369685841347018901038478081710519253844078907000973324354805502890255414196801758171762906898874914776720897920729518384393581853690034053515213192846817920534901501370942556249012415259244063185938984570137371682805276444650716010228924732495062415330875872004691866847132147232457398743319930259327973290858489741376000333603734294893832124907092640953321640151851853501528390729805151850605432707293088635480863375398001441    c2 = 14550589053226237723784378782911157204367764723816957959635387925652898370034365455451983914571405062459535687617841302966938233065296973978472553109061974458935966754832788411876301179210585984208608247433383774246743661884093657109502619626436726032508763685599880808525861655167503719155953736308920858354069083437923495143680174206534169208623366776314544036377265501358254923029291010047210371394197963442022610746743020719292018028518885149189744832788117626194748311114409968846879212425054195323473068436359069318372735069308398135560733890706617536127579272964863500568572120716434126233695562326533941909353    result = franklin(n, pad1, pad2, c1, c2)    print(long_to_bytes(result))
main()```
And get: `N1CTF{f7efbf4e5f5ef78ca1fb9c8f5eb02635}`