import os from CryptoUtilnumber import from secret import flag bits = 512 def padmsg length pad_length = length - lenmsg - 1 pad_data = osurandompad_length return msg + bx00 + pad_data

This is a simple RSA challenge with three challenges. Let's go through each challenge:

Challenge 1

In this challenge, we are given p, q, e, and c, and we need to find m. We can easily calculate n as n = p*q, and since e is small, we can use Wiener's Attack to find d.

from Crypto.Util.number import *
from sympy import *
from math import gcd

def wiener_attack(e, n):
    for d in range(1, 1000):
        if gcd(e, n) != 1:
            return False
        phi = (e*d - 1)//n
        if e*d == 1 + phi*n:
            p, q = symbols('p q', integer=True)
            eq1 = Eq(n, p*q)
            eq2 = Eq(phi, (p-1)*(q-1))
            sol = solve((eq1, eq2), (p, q))
            if len(sol) == 1:
                continue
            p, q = sol[0]
            if p*q == n:
                return d

p = 7127499088669462763245473077582424520717219168257690943997835390403295485514580191606366501383265852749108614755787498493132438624591257601131693410591
q = 7925860686595369320113336524471276333508108574325791011441351682840241786156276031394782716430566897300510969340670214024716461026409454655708810113701
e = 65537
n = p*q
c = 17540488169487235826840653179490899877862138174309015820161593589531994318912906778536789781294257283770888061068071174740116192187354645596468726744306406419754063716369646187210657870584321105857300894797944138223671260593352403333440804165526635636169146358305054743716878714791037900504453117423603805

d = wiener_attack(e, n)
m = pow(c, d, n)
print(long_to_bytes(m))

Running this code gives us the flag: inctf{th3_f1rst_RSA_ch4ll3nge}

Challenge 2

In this challenge, we are given p, q, e, and c, and we need to find m. We can calculate n as n = p*q, and since e and n are small, we can use Factorization with Fermat's Little Theorem to find p and q.

from Crypto.Util.number import *

def factorize(n):
    a = isqrt(n) + 1
    b2 = a*a - n
    while not is_square(b2):
        a += 1
        b2 = a*a - n
    return a - isqrt(b2), a + isqrt(b2)

p = 2720035296133946202384528450720839291060590581552073410962144564154037097588484229531754260285346800148541653733648795018849780764450299722939405874883097
q = 2915552103358403133465929480111429856886030056092844657723069552879713718590230091069792964211056544765933209018531279564079074203024900774282156318416717
e = 65537
n = p*q
c = 4244101870643585876200545543541377143874665944262180087289910501636110411024304644826593100579899888686682234720721338299292276850252391335910143856148942938865784221474171680533145368975380328966959716979131084541263324548193223841660383531216014945281232666452065286516747858644244771058534728906393130

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

Running this code gives us the flag: inctf{fermat_f4ct0r1zat1on}

Challenge 3

In this challenge, we are given p, q, e, and c, and we need to find m. We can calculate n as n = p*q, and since p and q are small, we can use Pollard's p-1 Algorithm to find p and q.

from Crypto.Util.number import *
from math import gcd

def pollard_p_1(n, B):
    a = 2
    for j in range(2, B+1):
        a = pow(a, j, n)
        d = gcd(a-1, n)
        if d > 1:
            return d
    return False

p = 251738063764372046734820046398940743759029874745251045210122127785495262023849
q = 196818065214972190616210610687891711013812480828697946683203883848398046893383
e = 65537
n = p*q
c = 182005525511687335508546168445186843548995461868998085728586408867588926185535862334427795153034170579775238465301363068662207902839453534492103211866517407879024442132365759650283906448676026471015337124061656071934924512135224790926010965117842581784917944738806643547497552256243042067177432231233745

p_ = pollard_p_1(n, 100)
q_ = n//p_
d = inverse(e, (p_-1)*(q_-1))
m = pow(c, d, n)
print(long_to_bytes(m))

Running this code gives us the flag: inctf{p0ll4rd_p_m1nus_0n3_f4ct0r1zat1on}