RSA之费马分解 | 司南的博客

ctfshow切记务必一定要简单

from Crypto.Util.number import *
import random, sys

def get_prime(base, offset):
    l = base - (1 << offset)
    r = base + (1 << offset)
    p = random.randrange(l, r) | 1
    while (not isPrime(p)):
        p += 2
    return p

if __name__ == "__main__":
    p = getPrime(1127)
    q0 = p * 13 // 17
    q = get_prime(q0, 573) # Konami
    with open('flag.txt', 'rb') as f:
        flag = bytes_to_long(f.read())
    N = p * q
    assert isPrime(p) and isPrime(q) and flag < N
    e = 0x10001
    c = pow(flag, e, N)
    print(f"N = {N}")
    print(f"e = {e}")
    print(f"c = {c}")

p是一个1127位的素数，q是介于[p 13 - 17 - 2^573，p 13 - 17 + 2^573]。题目还给了一个相关链接

根据q的生成算法，直接定位到p - q较小，2^573可不小啊。。。

费马分解的原理是这样的：

令a = (p + q) / 2，因为(p - q)较小，所以a^2和n很接近，所以我们可以从根号n开始往后遍历，如果a^2-n能够开平方，则表明我们找到了n的因子。这里的很明显是px13 - 17xq较小。所以套用上面的公式：

脚本如下：

import gmpy2
from Crypto.Util.number import *
from gmpy2 import *
from sympy import *

N = 2537578464060405716805986209629349306801585799475566769629753550869939275098596985321844853409568013133264210149682740766024366488982429837531169509250859483526118776072099712258599263748732430570800661306460224380741403478451009927665855604092871949705081574682507168392533782265954982321389235080917435497979848348321877319477780053855288297818739223795823021264136388271573286209636548206594797813576810688640228747147522219625866870777713858310084857747151891233766790129427051420839675334815589489194938107230004427317376438129284740257550482956744843496127593401991789197386269415091390162278183972481279010769071314265529328954115911712467352483233380953386631332500882467
e = 65537
c = 1595212140002311449986774328911538131302021292459414446518934463751924694901681197719356391632660947700772362140375795419149621042035212501260054901239960931458611414432758551692762707025705203714868544808208482382713403084945106505851948109261999900909705955010772382362799626266428855540493176898287751627555377040483120618564113186968911259319525250268854097054159722810266326281435235140862840574780793343440289233893489065111751815693510473980454574606688640074455096644717769189843656600438932454630073349737743755427817726253307163184245099133341515200474243399626081459226215410055396366269535409932990065250476999485239927630147382130648035686165068584532121265385100009

N = 221 * N
a = iroot(N, 2)[0]
while True:
    if gmpy2.iroot(abs(a**2 - N), 2)[1]:
        k = gmpy2.iroot(abs(a**2 - N), 2)[0]
        p = Symbol('p')
        q = Symbol('q')
        re = solve([221 * p * q - N, 13 * p - 17 * q - 2 * k], [p, q])[0]
        p = int(abs(re[0]))
        q = int(abs(re[1]))
        assert p * q == N // 221
        d = inverse(e, (p - 1) * (q - 1))
        print(long_to_bytes(pow(c, d, N // 221)))
        break
    a += 1

RSA2

绿城杯的题，这里一样贴出来。

题目如下：

from Crypto.Util.number import *
import gmpy2
from flag import flag
assert flag[:5]==b'flag{'

m1 = bytes_to_long(flag[:20])
p  = getPrime(512)
p1 = gmpy2.next_prime(p)
q  = getPrime(512)
q1 = gmpy2.next_prime(q)
n1 = p*q*p1*q1
print('n1 =',n1)
e = 0x10001
c1 = pow(m1,e,n1)
print('c1 =',c1)


m2 = bytes_to_long(flag[20:])
p2 = getPrime(1024)
q2 = getPrime(1024)
print('p2+q2 =',p2+q2)
print('q2*q2 =',p2*q2)
n2 = p2*p2*q2*q2*q2
print('n2 =',n2)
c2 = pow(m2,e,n2)
print('c2 =',c2)

#n1 = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
#c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826

#p2+q2 = 274773146761138462708137582309097386437793891793691383033856524303010811294101933454824485010521468914846151819876043508541879637544444256520741418495479393777132830985856522008561088410862815913292288683761657919121930016956916865849261153721097671315883469348972925757078089715102032241818526925988645578778
#q2*q2 = 18514724270030962172566965941723224386374076294232652258701085781018776172843355920566035157331579524980108190739141959926523082142273672741849552475156278397131571360099018592018959785627785130126477982765210498547680367230723634424036009539347854344573537848628061468892166199866227984167843139793429682559241317072979374002912607549039431398267184818771503468116379618249319324788996321340764624593443106354104274472601170229835219638093242557547840060892527576940077162990069687019966946826210112318408269749294366586682732614372434218768720577917368726530200897558912687470088583774711767599580037663378929000217
#n2 = 40588227045595304080360385041082238507044292731344465815296032905633525556943787610712651675460810768762763493579129831271018141591546207557410817432455139315527674932933085299277599173971912445226532235814580879585317211349524406424200622675880992390782025158621241499693400288031658194434641718026910652327933253877313106112861283314274635124734817398465059373562194694957841264834312640926278890386089611103714990646541470577351599526904458342660444968591197606820361364761648205241041444681145820799054413179462285509661124362074093583494932706249461954240408827087015525507173082129412234486228092002841868365895837463699200959915782767657258729794037776401995309244941171415842403617486719492483671490834562579225506831496881542530519595438932482796867853234159664409420977526102480385193101883785161080269573707156626838551506024455480650224305894501968583442346807126920740779780593650871645915149689424292912611578291912721896864772950410266629045542480009266574096080138709683466489568290569363478444349563498507530805502511051165160827192795520182720802422213364247355775222858214648603034743679187470844212529134374975737510982287957316878179964602394749601431823167982157434890459245394370728942790117156485268116758052636794417268680901420193002289035538753620555488506926366624641291881353268617130968991258983002165300186971963661666476600998389048880565199317280428349802824448329898502788492233381873026217202981921654673840142095839603360666049476100561268336225902504932800605464136192275593886736746497955270280541423593
#c2 = 25591090168544821761746024178724660839590948190451329227481168576490717242294520739865602061082558759751196452117720647426598261568572440942370039702932821941366792140173428488344932203576334292648255551171274828821657097667106792872200082579319963310503721435500623146012954474613150848083425126987554594651797477741828655238243550266972216752593788734836373144363217639612492397228808215205862281278774096317615918854403992620720969173788151215489908812749179861803144937169587452008097008940710091361183942268245271154461872102813602754439939747566507116519362821255724179093051041994730856401493996771276172343313045755916751082693149885922105491818225012844519264933137622929024918619477538521533548551789739698933067212305578480416163609137189891797209277557411169643568540392303036719952140554435338851671440952865151077383220305295001632816442144022437763089133141886924265774247290306669825085862351732336395617276100374237159580759999593028756939354840677333467281632435767033150052439262501059299035212928041546259933118564251119588970009016873855478556588250138969938599988198494567241172399453741709840486953189764289118312870580993115636710724139809708256360212728127786394411676427828431569046279687481368215137561500777480380501551616577832499521295655237360184159889151837766353116185320317774645294201044772828099074917077896631909654671612557207653830344897644115936322128351494551004652981550758791285434809816872381900401440743578104582305215488888563166054568802145921399726673752722820646807494657299104190123945675647

先看看flag左半边的加密，可以知道p和p1很接近，q和q1很接近。直接进行费马分解，就会算出有[p q, p1 q1]和[p q1,p1 q]的两组组合。接着找到两个组合中的公因子，最后就是RSA的基本流程。脚本如下：

e = 65537
n1 = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826
def format(n):
    get_context().precision = 2048
    x = int(sqrt(n1))
    factor_list = []
    while True:
        x += 1
        y2 = x ** 2 - n1
        if is_square(y2):
            y2 = mpz(y2)
            get_context().precision = 2048
            y = int(sqrt(y2))
            factor_list.append([x + y, x - y])
        if len(factor_list) == 2:
            break
    return factor_list

x1, y1 = format(n1)[0]
x2, y2 = format(n1)[1]
assert x1 * y1 == n1
assert x2 * y2 == n1
p = gcd(x1, x2)
q = gcd(y1, y2)
p1 = x1 // p
q1 = y1 // q
assert isPrime(p) and isPrime(q) and isPrime(p1) and isPrime(q1)
phin = (p - 1) * (q - 1) * (p1 - 1) * (q1 - 1)
d = inverse(e, phin)
m = pow(c1, d, n1)

再来看看后半部分，两个因子的相加和相乘的结果都给了，直接z3或者sympy解方程，脚本如下：

add = 274773146761138462708137582309097386437793891793691383033856524303010811294101933454824485010521468914846151819876043508541879637544444256520741418495479393777132830985856522008561088410862815913292288683761657919121930016956916865849261153721097671315883469348972925757078089715102032241818526925988645578778
mul = 18514724270030962172566965941723224386374076294232652258701085781018776172843355920566035157331579524980108190739141959926523082142273672741849552475156278397131571360099018592018959785627785130126477982765210498547680367230723634424036009539347854344573537848628061468892166199866227984167843139793429682559241317072979374002912607549039431398267184818771503468116379618249319324788996321340764624593443106354104274472601170229835219638093242557547840060892527576940077162990069687019966946826210112318408269749294366586682732614372434218768720577917368726530200897558912687470088583774711767599580037663378929000217
n2 = 40588227045595304080360385041082238507044292731344465815296032905633525556943787610712651675460810768762763493579129831271018141591546207557410817432455139315527674932933085299277599173971912445226532235814580879585317211349524406424200622675880992390782025158621241499693400288031658194434641718026910652327933253877313106112861283314274635124734817398465059373562194694957841264834312640926278890386089611103714990646541470577351599526904458342660444968591197606820361364761648205241041444681145820799054413179462285509661124362074093583494932706249461954240408827087015525507173082129412234486228092002841868365895837463699200959915782767657258729794037776401995309244941171415842403617486719492483671490834562579225506831496881542530519595438932482796867853234159664409420977526102480385193101883785161080269573707156626838551506024455480650224305894501968583442346807126920740779780593650871645915149689424292912611578291912721896864772950410266629045542480009266574096080138709683466489568290569363478444349563498507530805502511051165160827192795520182720802422213364247355775222858214648603034743679187470844212529134374975737510982287957316878179964602394749601431823167982157434890459245394370728942790117156485268116758052636794417268680901420193002289035538753620555488506926366624641291881353268617130968991258983002165300186971963661666476600998389048880565199317280428349802824448329898502788492233381873026217202981921654673840142095839603360666049476100561268336225902504932800605464136192275593886736746497955270280541423593
c2 = 25591090168544821761746024178724660839590948190451329227481168576490717242294520739865602061082558759751196452117720647426598261568572440942370039702932821941366792140173428488344932203576334292648255551171274828821657097667106792872200082579319963310503721435500623146012954474613150848083425126987554594651797477741828655238243550266972216752593788734836373144363217639612492397228808215205862281278774096317615918854403992620720969173788151215489908812749179861803144937169587452008097008940710091361183942268245271154461872102813602754439939747566507116519362821255724179093051041994730856401493996771276172343313045755916751082693149885922105491818225012844519264933137622929024918619477538521533548551789739698933067212305578480416163609137189891797209277557411169643568540392303036719952140554435338851671440952865151077383220305295001632816442144022437763089133141886924265774247290306669825085862351732336395617276100374237159580759999593028756939354840677333467281632435767033150052439262501059299035212928041546259933118564251119588970009016873855478556588250138969938599988198494567241172399453741709840486953189764289118312870580993115636710724139809708256360212728127786394411676427828431569046279687481368215137561500777480380501551616577832499521295655237360184159889151837766353116185320317774645294201044772828099074917077896631909654671612557207653830344897644115936322128351494551004652981550758791285434809816872381900401440743578104582305215488888563166054568802145921399726673752722820646807494657299104190123945675647

p2, q2 = Ints('p2 q2')
sol = Solver()
sol.add(p2 + q2 == add)
sol.add(p2 * q2 == mul)
if (sol.check() == sat):
    print(sol.model())
q2 = 118403784459455138582919377906131738592946190895354489225890530955489713357948723774385902598164582767355529878101682058998518634444589192617157682795489868846289962039288493883412519273541770945888153150197763095564026103787571812611196732248676365740482179339301570536662025044058993433932899960459852671737
p2 = 156369362301683324125218204402965647844847700898336893807965993347521097936153209680438582412356886147490621941774361449543361003099855063903583735699989524930842868946568028125148569137321044967404135533563894823557903913169345053238064421472421305575401290009671355220416064671043038807885626965528792907041
phin2 = p2 * (p2 - 1) * q2 * q2 * (q2 - 1)
d2 = inverse(e, phin2)
m = pow(c2, d2, n2)
flag += str(long_to_bytes(m))
print(flag)

完整脚本如下：

from Crypto.Util.number import *
from gmpy2 import *
from z3 import *
import sympy

flag = ""
e = 65537
n1 = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826
def format(n):
    #设置精度
    get_context().precision = 2048
    x = int(sqrt(n1))
    factor_list = []
    while True:
        x += 1
        y2 = x ** 2 - n1
        if is_square(y2):
            y2 = mpz(y2)
            #设置精度
            get_context().precision = 2048
            y = int(sqrt(y2))
            factor_list.append([x + y, x - y])
        if len(factor_list) == 2:
            break
    return factor_list

x1, y1 = format(n1)[0]
x2, y2 = format(n1)[1]
assert x1 * y1 == n1
assert x2 * y2 == n1
p = gcd(x1, x2)
q = gcd(y1, y2)
p1 = x1 // p
q1 = y1 // q
assert isPrime(p) and isPrime(q) and isPrime(p1) and isPrime(q1)
phin = (p - 1) * (q - 1) * (p1 - 1) * (q1 - 1)
d = inverse(e, phin)
m = pow(c1, d, n1)
flag += str(long_to_bytes(m))


add = 274773146761138462708137582309097386437793891793691383033856524303010811294101933454824485010521468914846151819876043508541879637544444256520741418495479393777132830985856522008561088410862815913292288683761657919121930016956916865849261153721097671315883469348972925757078089715102032241818526925988645578778
mul = 18514724270030962172566965941723224386374076294232652258701085781018776172843355920566035157331579524980108190739141959926523082142273672741849552475156278397131571360099018592018959785627785130126477982765210498547680367230723634424036009539347854344573537848628061468892166199866227984167843139793429682559241317072979374002912607549039431398267184818771503468116379618249319324788996321340764624593443106354104274472601170229835219638093242557547840060892527576940077162990069687019966946826210112318408269749294366586682732614372434218768720577917368726530200897558912687470088583774711767599580037663378929000217
n2 = 40588227045595304080360385041082238507044292731344465815296032905633525556943787610712651675460810768762763493579129831271018141591546207557410817432455139315527674932933085299277599173971912445226532235814580879585317211349524406424200622675880992390782025158621241499693400288031658194434641718026910652327933253877313106112861283314274635124734817398465059373562194694957841264834312640926278890386089611103714990646541470577351599526904458342660444968591197606820361364761648205241041444681145820799054413179462285509661124362074093583494932706249461954240408827087015525507173082129412234486228092002841868365895837463699200959915782767657258729794037776401995309244941171415842403617486719492483671490834562579225506831496881542530519595438932482796867853234159664409420977526102480385193101883785161080269573707156626838551506024455480650224305894501968583442346807126920740779780593650871645915149689424292912611578291912721896864772950410266629045542480009266574096080138709683466489568290569363478444349563498507530805502511051165160827192795520182720802422213364247355775222858214648603034743679187470844212529134374975737510982287957316878179964602394749601431823167982157434890459245394370728942790117156485268116758052636794417268680901420193002289035538753620555488506926366624641291881353268617130968991258983002165300186971963661666476600998389048880565199317280428349802824448329898502788492233381873026217202981921654673840142095839603360666049476100561268336225902504932800605464136192275593886736746497955270280541423593
c2 = 25591090168544821761746024178724660839590948190451329227481168576490717242294520739865602061082558759751196452117720647426598261568572440942370039702932821941366792140173428488344932203576334292648255551171274828821657097667106792872200082579319963310503721435500623146012954474613150848083425126987554594651797477741828655238243550266972216752593788734836373144363217639612492397228808215205862281278774096317615918854403992620720969173788151215489908812749179861803144937169587452008097008940710091361183942268245271154461872102813602754439939747566507116519362821255724179093051041994730856401493996771276172343313045755916751082693149885922105491818225012844519264933137622929024918619477538521533548551789739698933067212305578480416163609137189891797209277557411169643568540392303036719952140554435338851671440952865151077383220305295001632816442144022437763089133141886924265774247290306669825085862351732336395617276100374237159580759999593028756939354840677333467281632435767033150052439262501059299035212928041546259933118564251119588970009016873855478556588250138969938599988198494567241172399453741709840486953189764289118312870580993115636710724139809708256360212728127786394411676427828431569046279687481368215137561500777480380501551616577832499521295655237360184159889151837766353116185320317774645294201044772828099074917077896631909654671612557207653830344897644115936322128351494551004652981550758791285434809816872381900401440743578104582305215488888563166054568802145921399726673752722820646807494657299104190123945675647

'''p2, q2 = Ints('p2 q2')
sol = Solver()
sol.add(p2 + q2 == add)
sol.add(p2 * q2 == mul)
if (sol.check() == sat):
    print(sol.model())'''
q2 = 118403784459455138582919377906131738592946190895354489225890530955489713357948723774385902598164582767355529878101682058998518634444589192617157682795489868846289962039288493883412519273541770945888153150197763095564026103787571812611196732248676365740482179339301570536662025044058993433932899960459852671737
p2 = 156369362301683324125218204402965647844847700898336893807965993347521097936153209680438582412356886147490621941774361449543361003099855063903583735699989524930842868946568028125148569137321044967404135533563894823557903913169345053238064421472421305575401290009671355220416064671043038807885626965528792907041
phin2 = p2 * (p2 - 1) * q2 * q2 * (q2 - 1)
d2 = inverse(e, phin2)
m = pow(c2, d2, n2)
flag += str(long_to_bytes(m))
print(flag)