记录CTF中的RSA非常规题解

如果你熟悉去年所有CTF比赛中的web题解，那么比赛中一半以上的题都能轻松解决 —— posix小姐姐

2020 网鼎杯 you raise me up#

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

是未知$e$的情况，我们知道当$e< 2^{64}$时可以通过$bsgs$解决，但这里$e$明显太大了，不过sage提供了discrete_log()进行求解

e=discrete_log(Mod(c,n),Mod(m,n))
# sage

THUCTF 2020#

n = 114343085046463433411381776220543901901873928314903659614100254404100269463417499891993902366447489777312635887492019329010394661845440919768114220413686723810221962634122271643213501630972122082386450374407459824201848960741304431687915771670375151120891105793486536323734874929422017875459395117658992059677
c = 1384608876124927489441910327904528237548776368399531206044083800790774090882345964210476594356727800470845410695005386749381538164481432608783364583808558364847427405367871028396194497762440888707116196989953055035065121701440531497100049016077277959253415273999314575036822476336014586783215416497277921943
2*d+e*phi+2020 = 22046774932370586482011989351077962586470998216913397840682653185876350155036481792005139545363427307155556226952079206673782623819821327455802429601369994136121668582623039411726516755690052737901843564168187074397101479942270643179299412053210417686126964426668454289595567836618481967225032457758237543611808222

• https://writeups.amosng.com/2018/easyctf_2018/cryptography/hidden-key_250/

一般我们找$d$都是在$d < \phi(n)$找，但其实$d$只要满足$ed \mod \phi(n) = 1$即可，所以在这里$d = s//2$

from Crypto.Util.number import *
from tqdm import tqdm
n = 114343085046463433411381776220543901901873928314903659614100254404100269463417499891993902366447489777312635887492019329010394661845440919768114220413686723810221962634122271643213501630972122082386450374407459824201848960741304431687915771670375151120891105793486536323734874929422017875459395117658992059677
c = 1384608876124927489441910327904528237548776368399531206044083800790774090882345964210476594356727800470845410695005386749381538164481432608783364583808558364847427405367871028396194497762440888707116196989953055035065121701440531497100049016077277959253415273999314575036822476336014586783215416497277921943
s = 22046774932370586482011989351077962586470998216913397840682653185876350155036481792005139545363427307155556226952079206673782623819821327455802429601369994136121668582623039411726516755690052737901843564168187074397101479942270643179299412053210417686126964426668454289595567836618481967225032457758237543611808222
s = s - 2020

d = s//2
m = pow(c, d, n)
print(long_to_bytes(m))
# THUCTF{99049c76-3447-46d0-b52e-299e25755a48}

2020 巅峰极客 tryRSA#

from secret import e1,e2,flag
from Crypto.Util.number import *

msg = bytes_to_long("=========Hint:e1="+str(e1)+"=============")
p = getPrime(512)
q = getPrime(512)
N = p*q
print N
print pow(msg,3,N)

msg = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
N = p*q
c = pow(msg, e2, N)
print N,e2
print c
print(pow(p+q,e1,N ))
print(pow(p+e1, q, N))


'''
92492770373119584460081987762423642921257844727187836762004909281192459271971634726161143981458071695340994591107972425352531669271078740978901135762304359798469976380706711716397909327202889036066332030534806956149533263677365472375053769919044969923810993041551455618809123044195807478835222921551845223673
28249132350044579687091110964285446575404805400757326954185222098803605008954490760462246663674360047951197296557689347856716297531621331430289344669498939239588624311221464757652619402073234993515450143594805022438694559765344247838048186137683783869848355994953125
27015781782143176377305444708803319343811009307670517970464768333771120997045181708841835585570829548449323842457013912871572311489720085833836018287540353234899258733164425361573491416926759037218022548655403489670177828691645649124879974295681372533797388585691439378293643867458900873524289213226600650695273378214798580343627514294295063280759129845430749116891862775979009255567653541999885963152760100703226634896555671676063304361506854160585739743294659176171738147833879545955904927967598053108666430271719503999512230196683852929862867406713611436850146222646354297511499309143157446775247989917315728885081 65537
6960471390887676836770576717723665527999812876556281118485164081998911577875381908446602930344333654944091349042662834710841686602096786488652321359862587616056255592745697363730350424006430304398118412822538778460783959334956287873626339403915923932633438142296099193868446694776583016981952887671846310453413799566390944727222387714300425256165444782922011140095044159890292073622972447390685582541707094791774266611010707510165706469905665511940032155195482276746347896610980037890500866671279623501021060117466463857453415816945239635341057570437059560066260202940898394476654111403345827675113200431405898577228
1043358162140860962273728863918690254907683549241317489027248804399285815575770538413854959643097587139967903983728298468193229257795104589966904860928102961617976618240299512928763147662509317818932641083203337246219100049009339117603571633877302978817219689048124475419370026280279605865626353406562716520200330156419718727010377305953369496577186008235640834052476174479818668164269356133941979167253165318046864430749941469717776898395077805761110978284600985034996774850879017975655590682283621730288960471273895327469257980443060594976109602435213897419646191853646130932643009667656100697739228571988907108326
2367294939363830936563488061919820815242930281093184747199533909423831655805653462926444204702027721204809679004109764873839689145594088483842010258154637719914884625388278232087919706082381019835448905310742695003695950771324141473767622775925225996118945331612570816055138158026344226500272784973866690432399708551301786027237710788172551956598563031161785118254195771411706070504960683710473948125061842911067623875812101363911946970263021272358739604106737786749756437515890114561301491995915709307108967981619075610635000644793538253463486203886648971971414160634218354735619624263269704236191332074536463815524
'''

$e1$通过开根即可求出，对$(p+q)^{e_1} \mod N$和$(p+e_1) ^ q \mod N$化简如下：

$$c_1 = (p+q)^{e_1} \mod N = (p+q)^{e_1} \mod pq = (p+q)^{e_1}+kpq$$

$$c_1 \mod q = p^{e_1} \mod q = p^{e_1}+k_1q$$

$$c_2 = (p+e_1)^q \mod N = (p+e_1)^q + kpq$$

$$c_2 \mod q = (p+e_1) \mod q (费马小定理) = (p+e_1) + k_2q$$

因此我们有$gcd((c_2-e_1)^{e_1}-c_1,N) = q$

from Crypto.Util.number import long_to_bytes, inverse
from gmpy2 import iroot, gcd
N = 92492770373119584460081987762423642921257844727187836762004909281192459271971634726161143981458071695340994591107972425352531669271078740978901135762304359798469976380706711716397909327202889036066332030534806956149533263677365472375053769919044969923810993041551455618809123044195807478835222921551845223673
c = 28249132350044579687091110964285446575404805400757326954185222098803605008954490760462246663674360047951197296557689347856716297531621331430289344669498939239588624311221464757652619402073234993515450143594805022438694559765344247838048186137683783869848355994953125

msg = iroot(c, 3)[0]
msg = long_to_bytes(msg)
e1 = msg.split(b"e1=")[1].replace(b'=', b'')
e1 = int(e1)

N = 27015781782143176377305444708803319343811009307670517970464768333771120997045181708841835585570829548449323842457013912871572311489720085833836018287540353234899258733164425361573491416926759037218022548655403489670177828691645649124879974295681372533797388585691439378293643867458900873524289213226600650695273378214798580343627514294295063280759129845430749116891862775979009255567653541999885963152760100703226634896555671676063304361506854160585739743294659176171738147833879545955904927967598053108666430271719503999512230196683852929862867406713611436850146222646354297511499309143157446775247989917315728885081
e2 = 65537
c = 6960471390887676836770576717723665527999812876556281118485164081998911577875381908446602930344333654944091349042662834710841686602096786488652321359862587616056255592745697363730350424006430304398118412822538778460783959334956287873626339403915923932633438142296099193868446694776583016981952887671846310453413799566390944727222387714300425256165444782922011140095044159890292073622972447390685582541707094791774266611010707510165706469905665511940032155195482276746347896610980037890500866671279623501021060117466463857453415816945239635341057570437059560066260202940898394476654111403345827675113200431405898577228
c1 = 1043358162140860962273728863918690254907683549241317489027248804399285815575770538413854959643097587139967903983728298468193229257795104589966904860928102961617976618240299512928763147662509317818932641083203337246219100049009339117603571633877302978817219689048124475419370026280279605865626353406562716520200330156419718727010377305953369496577186008235640834052476174479818668164269356133941979167253165318046864430749941469717776898395077805761110978284600985034996774850879017975655590682283621730288960471273895327469257980443060594976109602435213897419646191853646130932643009667656100697739228571988907108326
c2 = 2367294939363830936563488061919820815242930281093184747199533909423831655805653462926444204702027721204809679004109764873839689145594088483842010258154637719914884625388278232087919706082381019835448905310742695003695950771324141473767622775925225996118945331612570816055138158026344226500272784973866690432399708551301786027237710788172551956598563031161785118254195771411706070504960683710473948125061842911067623875812101363911946970263021272358739604106737786749756437515890114561301491995915709307108967981619075610635000644793538253463486203886648971971414160634218354735619624263269704236191332074536463815524

ans = pow(c2-e1, e1, N) - c1
q = gcd(ans, N)
p = N//q

phi = (p-1)*(q-1)
d = inverse(e2, phi)
m = pow(c, d, N)

print(long_to_bytes(m))
# flag{5b55c69f-398d-47bc-ad37-4f268e8ae4b2}

2020 西湖论剑 Wake me up until May ends#

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag, source_p
from random import randint, shuffle
from sympy.ntheory import factorint


def all_factor(n):
    factors = []
    limit = n//2 + 1
    for i in range(1, limit):
        if n % i == 0:
            factors.append(i)
    factors.append(n)
    return factors


def u(d):
    if d == 1:
        return 1
    factors = factorint(d)
    primes = list(factors.keys())
    index = list(factors.values())
    for i in index:
        if i >= 2:
            return 0
    return pow(-1, len(primes) % 2)


def f(d):
    factors = factorint(d)
    primes = list(factors.keys())
    index = list(factors.values())
    base = 1
    for i in range(len(primes)):
        base *= pow(primes[i], index[i]-1)
        base *= (primes[i] - 1)
    return base


def combine(n):
    factors = all_factor(n)
    base = 0
    for i in factors:
        base += u(i) * f(i)
    return base


def Yusa(m):
    p = getPrime(533)
    q = getPrime(533)
    n = p * q
    _phi = (p - 1) * (q - 1)
    limit1 = (3 * n) // (2 * (int(iroot(n, 4)[0]) + 3 * (p + q)))

    while True:
        x = getPrime(256)
        y = getPrime(256)
        if x * y < limit1:
            break

    limit2 = (abs(p-q) * int(iroot(n, 4)[0]) * y) // (6 * (max(p, q)))
    e = (y * _phi) // x
    while True:
        z = e * x - y * _phi
        if abs(z) < limit2 and gcd(e, _phi) == 1:
            break
        e -= 1

    c = pow(m, e, n)
    return c, e, n


shuffle(source_p)
p = source_p[:7]
length = 7
index = []
n = 1
for i in range(length):
    index.append(randint(1, 23))
    n *= p[i] ** index[i]

n = -combine(n)
assert n.bit_length() > 2048

e = getPrime(256)
_c, _e, _n = Yusa(e)


m = bytes_to_long(flag.encode())
c = pow(m, e, n)
print('c =', c)
print('p =', source_p)
print('index =', index)
print('_e =', _e)
print('_n =', _n)
print('_c =', _c)

# data
'''
primes = [6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503118559, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503126443, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503193349, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503562289, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503734189, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503760301, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503782813, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503951191, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504074953, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504107911, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504191461, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504448729, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504539989]
c = 84010209207136400037674900630630399007540527378939350615722225527845587559010102178617103738600464258190430641037546648203366413208680794400023737381999928100638870193135477985407368386033167118399673001236960699550393986712868487827560601610546135335952667201927052409197291462799539018091792246183307678928298241645258411316936304167124933556606198943248215284393941957893610109127025761289673484220381931928088574316265497075872825588843686573267223321714224535003053507039588501110165036609252972283465620670619170664971316238808580562960566239652372002792893860381585262550998380705474210656337505369024906108022045918104803080765059727578165530772500933465284347893453376016683018177839155666453880461050298815103588796089076127048997409337740340488597725920421812209214132626919132717242722587461710190518049279845280531076833361229586237230905386909567570882397978261647980071794688572393137428928552335623610968045342130104152766075095859252589558838654095036476181115093298573203118822557283958028992348972004110923680696213759378910314691270631431638964147123334674
index = [17, 4, 10, 5, 22, 23, 3]
_e = 372077403420031165815439199213704344304928202869941592969972103002464355333911024937074871410825817568355544126574173758702600945390438495248751733573391345292294888885607465578329781858741122278411513362633310583564023669185613282939355138576537165757775740881908805743008022348524049466231348651228609449357106436669219
_n = 470335762637936005588762180827192207993663594416060284974932410896705386687847439702920143090437462997342000428130417147164245577372958674672171462397851600930104979198327224831772288314005311036009419876584852939180439595289349509330868790367408195151323961061772542485151690708678904080061050887466315542337191307236199
_c = 333271281173306446630548720678701979402616631681988817880871964537046235416970583988475783551455814258102380169630603934095599959443467742430556704688855518165068592402751863811686579302153371106333344752494076921552527417915731880831363624299780159503812111855009880750695443491602523883753510968162389168190126033304497
'''

论文题，可参考：Blomer May Weak Key Revisited

from Crypto.Util.number import *
from gmpy2 import iroot
from tqdm import tqdm
import itertools
from sympy.ntheory import factorint


def u(d):
    if d == 1:
        return 1
    factors = factorint(d)
    primes = list(factors.keys())
    index = list(factors.values())
    for i in index:
        if i >= 2:
            return 0
    return pow(-1, len(primes) % 2)


def f(d):
    factors = factorint(d)
    primes = list(factors.keys())
    index = list(factors.values())
    base = 1
    for i in range(len(primes)):
        base *= pow(primes[i], index[i]-1)
        base *= (primes[i] - 1)
    return base


def combine_check(primes):
    base = 1
    for i in range(len(primes)):
        base *= (1-f(primes[i]))
    return base


def rational_to_quotients(x, y):  # calculate the series of continued fraction
    a = x // y
    quotients = [a]
    while a * y != x:
        x, y = y, x - a * y
        a = x // y
        quotients.append(a)
    return quotients


def convergents_from_quotients(quotients):  # calculate the convergent series of continued fraction
    convergents = [(quotients[0], 1)]
    for i in range(2, len(quotients) + 1):
        quotients_partion = quotients[0:i]
        denom = quotients_partion[-1]  # 分母
        num = 1
        for _ in range(-2, -len(quotients_partion), -1):
            num, denom = denom, quotients_partion[_] * denom + num
        num += denom * quotients_partion[0]
        convergents.append((num, denom))
    return convergents


def Blomer_May_attack(e, n):
    quotients = rational_to_quotients(e, n)
    convergents = convergents_from_quotients(quotients)
    for (_x, _y) in convergents:
        if _x != 0:
            T = n + 1 - (e * _y) // _x
            if T ** 2 - 4 * n > 0:
                tmp_p = (T + int(iroot(T ** 2 - 4 * n, 2)[0])) // 2
                for i in range(-2**5, 2**5):
                    _p = tmp_p + i
                    if n > _p > 1 and n % _p == 0:
                        print('Got solution!')
                        _q = n//_p
                        return _p, _q

    print('No solution')
    return None


def all_ascii(s):
    for i in s:
        if i in range(0x20, 0x7f):
            continue
        else:
            return False
    return True


primes = [6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503118559, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503126443, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503193349, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503562289, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503734189, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503760301, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503782813, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503951191, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504074953, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504107911, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504191461, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504448729, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504539989]
c = 84010209207136400037674900630630399007540527378939350615722225527845587559010102178617103738600464258190430641037546648203366413208680794400023737381999928100638870193135477985407368386033167118399673001236960699550393986712868487827560601610546135335952667201927052409197291462799539018091792246183307678928298241645258411316936304167124933556606198943248215284393941957893610109127025761289673484220381931928088574316265497075872825588843686573267223321714224535003053507039588501110165036609252972283465620670619170664971316238808580562960566239652372002792893860381585262550998380705474210656337505369024906108022045918104803080765059727578165530772500933465284347893453376016683018177839155666453880461050298815103588796089076127048997409337740340488597725920421812209214132626919132717242722587461710190518049279845280531076833361229586237230905386909567570882397978261647980071794688572393137428928552335623610968045342130104152766075095859252589558838654095036476181115093298573203118822557283958028992348972004110923680696213759378910314691270631431638964147123334674
index = [17, 4, 10, 5, 22, 23, 3]
_e = 372077403420031165815439199213704344304928202869941592969972103002464355333911024937074871410825817568355544126574173758702600945390438495248751733573391345292294888885607465578329781858741122278411513362633310583564023669185613282939355138576537165757775740881908805743008022348524049466231348651228609449357106436669219
_n = 470335762637936005588762180827192207993663594416060284974932410896705386687847439702920143090437462997342000428130417147164245577372958674672171462397851600930104979198327224831772288314005311036009419876584852939180439595289349509330868790367408195151323961061772542485151690708678904080061050887466315542337191307236199
_c = 333271281173306446630548720678701979402616631681988817880871964537046235416970583988475783551455814258102380169630603934095599959443467742430556704688855518165068592402751863811686579302153371106333344752494076921552527417915731880831363624299780159503812111855009880750695443491602523883753510968162389168190126033304497


_p, _q = Blomer_May_attack(_e, _n)
_phi = (_p-1) * (_q-1)
_d = inverse(_e, _phi)
e = pow(_c, _d, _n)

tmp = list(itertools.combinations(primes, 7))
for l in tqdm(tmp):
    phi = 1
    for j in l:
        phi *= j-3
    n = -combine_check(l)
    d = inverse(e, phi)
    flag = long_to_bytes(pow(c, d, n))
    if all_ascii(flag):
        print(flag)
        break
# 9e519e65a9a492c10f31d4296699f00f