rsa special

[ReSnAd] -- iqmp ipmq e,c,(phi(n))

题目：

class Key:
    PRIVATE_INFO = ['P', 'Q', 'D', 'DmP1', 'DmQ1']
    def __init__(self, **kwargs):
        for k, v in kwargs.items():
            setattr(self, k, v)
        assert self.bits % 8 == 0

    def ispub(self):
        return all(not hasattr(self, key) for key in self.PRIVATE_INFO)

    def ispriv(self):
        return all(hasattr(self, key) for key in self.PRIVATE_INFO)

    def pub(self):
        p = deepcopy(self)
        for key in self.PRIVATE_INFO:
            if hasattr(p, key):
                delattr(p, key)
        return p

    def priv(self):
        raise NotImplementedError()
def genkey(bits):
    assert bits % 2 == 0
    while True:
        p = genprime(bits // 2)
        q = genprime(bits // 2)
        e = 65537
        d, _, g = egcd(e, (p-1) * (q-1))
        if g != 1: continue
        iQmP, iPmQ, _ = egcd(q, p)
        return Key(
            N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
            iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
        )
def encrypt(key, data):
    data = bytes2num(pad(data, key.bits))
    assert 0 <= data and data < key.N
    data = pow(data, key.E, key.N)
    return num2bytes(data, key.bits // 8)

def decrypt(key, data):
    assert key.ispriv() and len(data) * 8 == key.bits
    data = bytes2num(data)
    assert 0 <= data and data < key.N
    v1 = pow(data, key.DmP1, key.P)
    v2 = pow(data, key.DmQ1, key.Q)
    data = (v2 * key.P * key.iPmQ + v1 * key.Q * key.iQmP) % key.N
    return unpad(num2bytes(data, key.bits // 8))

给出变量(ipmd,iqmp,e,phi(n),c)

注意到ipmq,iqmp,_=egcd(p,q)，得到

(ipmqcdot pequiv1(mod q)\iqmpcdot qequiv1(mod p))

目标是推出p,q

(egin{cases}ipmqcdot p=k_1cdot q+1\iqmpcdot q=k_2cdot p+1end{cases})

两式相加得

(ecause ipmqcdot pcdot iqmpcdot q=k_1cdot qcdot k_2cdot p+k_1cdot q+k_2cdot p+1)
( herefore (ipmqcdot iqmp-k_1cdot k_2)cdot n=k_1cdot q +k_2cdot p+1)

再注意iqmp=iqmp%p,ipmq=ipmq%q

(egin{cases}iqmpleq p\ipmqgeq qend{cases}longrightarrowegin{cases}0leq k_1<p\0leq k_2<qend{cases})

取(k_1,k_2)为右极限，带入前式右边

((ipmqcdot iqmp-k_1cdot k_2)cdot n<2n+1)

所以((ipmqcdot iqmp-k_1cdot k_2)cdot n)只能1 or 2

为2时，右边(k_1,k_2)必须取p,q，不可能。于是，只能为1

所以(n=k_1cdot q+k_2cdot p+1)

由3，4两相加得(ipmqcdot p+iqmpcdot q=k_1cdot q+k_2cdot p+2=n+1)

又(phi(n)=(p-1)cdot(q-1)=n-(q+p)+1)

列出方程组

(egin{cases}ipmqcdot p+iqmpcdot q=n+1\phi(n)=n-(p+q)+1\phi(n)=(p-1)cdot(q-1)end{cases})

三个未知数,n,p,q，三条方程，可解

用z3跑一下就好

Exp:

from z3 import *
import gmpy2
from Crypto.Util.number import long_to_bytes
q=Int("q")
p=Int("p")
n=Int("n")
phi = 11177929896833318778267064419554047209804133035532602158237892469506082395935495256139136112194510151728917586404919115707761109072628761295860181662822356164160284726297946695851442119129722147684494637497443200139538149832495961915450185804086755272971387407998204100589137627495400914243828434106078332327997903842841517071021248147779935078071506489655500155896938283840729728572328660647233974344849571246788826036265850539775145330135792207209473452843737567371694666658091855216070403504619639510901644370971614286091867701992201923071041178318790575030522483839410855929335515391080189720203086802888683798400
iqmp = 91015809392527255523072044687980286577671138545257803641612547883387289541035388722157767029686572001797549231630088970758132893695316792508265294751302240594796242084165161239587935396541914404832318478070695600559420277875549100164011180835754613742632525637982101603421982448705454195363628987806367263766
ipmq = 10870198964186987138989651624057552405853366954080463316431710442091837631287759912193054100505356356476481503550009625275319473929512195371174525538642232600176213853601253377888749818545192155785873323173291991086758912490744417777560275318548708479769299122462125768416235737869558154549710389717852257846
s=Solver()
s.add(iqmp*q+ipmq*p==n+1)
s.add(phi==(p-1)*(q-1))
s.add(phi==n-(q+p)+1)
s.check()
#print(s.model())
p = 100920329311023043792405408005417242117374946885462223687244834540168939266980874513828622981269823935831791149302266474816959342903482904850705622841034674617774508046423149433115499066314613920674997684075319293745518393044329170181630440249931588961323218471139932722932324367911140345310018504720309693151
q = 110759942750329561983364096770824818957156636845110590823134362698749612147788955083351174879972411435569300696393151260960779092387966200431706198509584768247841937719219850118991339268977853455607397866025870712323459278215127588375709815956587698977630219989552045686550681692693762584298742938231996726337

c = 0x3ce4e91042f61e3b03537d825e7619a02b3f729a91e2de4fb724b95cabe8fb2a7a92c4270025d93aed94f1726ca761083328a7784806e1467f0bc204ef95484ce6b0d207574c6dba4fa91664db4c787e3df517bcfc370a0c5eed8a70b45be8d1e757a9d40eb410e66d2110ac9ece435f76d71e134e2bdbe565e8853e1100ae276211c2b9c49219bca8805ff697dcf84be00b071c3be01f35ba9a4ea1d8ef2c69044982a7fc021d2f6f93b8755948a606a8a376e74d995f439aeeb844ecf678a189916adca406197a1d2eaf2abe84ae6e794560537bcde43a1504f135874d5de9e0a2d95093e4ba7a87641e769e46a911c94ff60525b21c9c709068a89808b6bf
e=65537

d=gmpy2.invert(e,phi)
m=gmpy2.powmod(c,d,p*q)
print(long_to_bytes(m))

Flag:fductf{b97ba9e174d916d30609a6e8b3d78ca3}

[RoarCTF2019] babyRSA -- wilson

题目：

import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

注意的事B!不是什么运算，是表示b的阶乘

威尔逊定理((p-1)!equiv-1mod p)
关键步骤就是运用威尔逊定理

(b=a-x)
((a-x)!cdot(a-x+1)cdot(a-x+2)cdot…(a-1)equiv-1mod a)

连乘b+1到a-1为止，并求逆。得到-b!，b!=a-b!

Exp:

import gmpy2
from Crypto.Util.number import long_to_bytes
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733

e=0x1001
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428

def wilison(b,a):
    p=1
    b=b+1
    while b<a:
        p*=b
        p%=a
        b+=1
    return a-p

p=gmpy2.next_prime(gmpy2.invert(wilison(B1,A1),A1))
q=gmpy2.next_prime(gmpy2.invert(wilison(B2,A2),A2))

r=n//q//p
phi=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

[NCTF2019]childRSA -- (phi(q),phi(p))是多个小因子累乘

题目：

from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag


def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108%

先讲非预期解

从加密过程中素数生成中可以看出p,q应该很接近，此时可以尝试yafu分解大素数

但是命令行模式下无法输入太长，我们新建一个n.txt,在里面写入n的值,注意最后要加换行!然后用在命令行用命令yafu-x64.exe "factor(@)" -batchfile n.txt。然后几秒钟后就得到了pq的值。

出题人想法:
http://www.soreatu.com/ctf/writeups/Writeup for Crypto problems in NCTF 2019.html#childrsa

[Crypto CTF] Time capsule

题目:

#!/usr/bin/python

from Crypto.Util.number import *
from secret import flag, n, t, z

def encrypt_time_capsule(msg, n, t, z):
    m = bytes_to_long(msg)
    l = pow(2, pow(2, t), n)
    c = l ^ z ^ m
    return (c, n, t, z) 

print encrypt_time_capsule(flag, n, t, z)

主要问题是pow(2,t),t过大，要运算时间过长

需要用到欧拉定理

(ecause2^{2^t}equiv lmod n\quad 2^e equiv lmod n\ herefore eequiv 2^tmod phi(n))

l=pow(2,pow(2,pow(2,t,phi(n)),n))就是解题的关键了
n可以在线网站分解，也可以sage分解

from functools import reduce
from Crypto.Util.number import *
n = 16801166465109052984956796702219479136700692152603640001472470493600002617002298302681832215942994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287393811934457789103209090873472485865328414154574392274611574654819495894137917800304580119452390318440601827273834522783696472257727329819952363099498446006266115011271978143149347765073211516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618066568854673260978968978974409802211538011638213976732286150311971354861300195440286582255769421094876667270445809991401456443444265323573485901383
factors = [15013, 583343756982313, 585503197547927, 609245815680559, 612567235432583, 634947980859229, 635224892351513, 639438000563939, 654170414254271, 654269804672441, 667954470985657, 706144068530309, 721443717105973, 737993471695639, 744872496387077, 746232585529679, 795581973851653, 815694637597057, 817224718609627, 841183196554507, 864339847436159, 873021823131881, 884236929660113, 899583643974479, 922745965897867, 942872831732189, 951697329369323, 971274523714349, 1017566110290559, 1018452110902339, 1025985735184171, 1027313536626551, 1059774237802229, 1067609726096989, 1070689247726159, 1079289330417443, 1098516592571807, 1107673252158281, 1108654254305327, 1110918654474373, 1111516996694389, 1112193819715441]
phi    = reduce(lambda curr, p: curr*(p-1), factors, 1)
test_n = reduce(lambda curr, p: curr*p, factors, 1)
assert test_n == n
assert pow(2, phi, n) == 1
c = 30263951492003430418944035844723976843761515320480688994488846431636782360488888188067655841720110193942081554547272176290791213962513701884837856823209432209367951673301622535940395295826053396595886942990258678430777333636450042181585837395671842878310404080487115827773100028876775230121509570227303374672524063165714509957850966189605469484201028704363052317830254920108664916139026741331552127849056897534960886647382429202269846392809641322613341548025760209280611758326300214885296175538901366986310471066687700879304860668964595202268317011117634615297226602309205086105573924029744405559823548638486054634428
t = 6039738711082505929
z = 13991757597132156574040593242062545731003627107933800388678432418251474177745394167528325524552592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446565880773029215057131908495627123103779932128807797869164409662146821626628200600678966223382354752280901657213357146668056525234446747959642220954294230018094612469738051942026463767172625588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109549686825235958909428605247221998366006018410026392446064720747424287400728961283471932279824049509228058334419865822774654587977497006575152095818
e = pow(2, t, phi)
l=pow(2,e,n)
m=l^z^c
print(long_to_bytes(m))

[GWCTF 2019] BabyRSA

这题不难，主要是工具的使用，记录一下
题目：

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

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '
')
output.write('m1=' + str(m1) + '
')
output.write('m2=' + str(m2) + '
')
output.close()

逻辑很清楚，先尝试分解因子，factor.com 和sage都没分开

但是看了一下，q=sympy.nextprime(p),判断p,q相差不大，用yafu可以分解

由于N太大了，不能直接命令行下分解，写入文件才可以。我们新建一个n.txt,在里面写入n的值,注意最后要加换行!然后用在命令行用命令yafu-x64.exe "factor(@)" -batchfile n.txt。然后几秒钟后就得到了pq的值

常规rsa手段求出c1,c2.

F1,F2满足两道方程，两个未知量，z3一把梭

exp:

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

N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
e=0x10001
p = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
q = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699

d=gmpy2.invert(e,(p-1)*(q-1))
flag1=gmpy2.powmod(m1,d,N)
flag2=gmpy2.powmod(m2,d,N)

c1=gmpy2.powmod(m1,d,N)
c2=gmpy2.powmod(m2,d,N)
#print("C1={}
C2={}".format(c1,c2))
C1=2732509502629189160482346120094198557857912754
C2=5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554


F1=Int('F1')
F2=Int('F2')
s=Solver()

s.add((F1+F2)==C1)
s.add(pow(F1,3)+pow(F2,3)==C2)
print(s.check())
print(s.model())

f2 = 1141553212031156130619789508463772513350070909
f1 = 1590956290598033029862556611630426044507841845

print(long_to_bytes(f1)+long_to_bytes(f2))

flag:GWHT{f709e0e2cfe7e530ca8972959a1033b2}

[BJDCTF2020] easyrsa --actan,arth,Derivative

题目：

from Crypto.Util.number import getPrime,bytes_to_long
from sympy import Derivative
from fractions import Fraction
from secret import flag

p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
m=bytes_to_long(flag)
c=pow(m,e,n)
print(c,z,n)
'''
output:
7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441

'''

arch,arctan不是python的函数，是反三角函数

fraction()是分数，Derivative()是求导函数

arth,arctan 的导数形式是

[arth'=frac{1}{1-x^2}\ arctan'=frac{1}{1+x^2} ]

化简一下z就是(p^2+q^2)

思路是

[(p+q)^2=p^2+q^2+2n ightarrow (p+q)\ (p-1)*(q-1)=n-(p+q)+1 ightarrow （p-1)*(q-1) ]

有了phi就可以直接求出d

exp:

import gmpy2
from Crypto.Util.number import long_to_bytes

c=7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z=32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n=15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
e=0x10001

p_add_q=gmpy2.iroot(z+2*n,2)[0]
phi=n-p_add_q+1
d=gmpy2.invert(e,phi)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

Flag:BJD{Advanced_mathematics_is_too_hard!!!}

[NCTF2019] babyrsa -- e,c,d

题目:

from Crypto.Util.number import *
from flag import flag

def nextPrime(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

p = getPrime(1024)
q = nextPrime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(flag.encode()), e, n)

# d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
# c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

目标是用d,e推出n

首先(ecdot d-1=kcdotphi(n))

推测一下k的范围，(或者直接爆破k的大小也可以)

(ecausephi(n)approx n\ecause d<n\ herefore k<e)

爆破可以得到所有的可能的(phi(n))

从代码可以看出p,q很接近，尝试对(phi(n))开方，在根(pm2000)左右要是能找到整除(phi(n))的值，就很可能是(p-1)或(q-1),然后就可以求出n

Exp:

from Crypto.Util.number import *
import gmpy2
​
e = 65537
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
kphi = e*d - 1
for k in range(1, e):
    if kphi % k == 0:
        phi = kphi // k
        root = gmpy2.iroot(phi, 2)[0]
        for p in range(root - 2000, root + 2000):
            if phi % (p-1) == 0: break
        else: continue
        break
q = phi//(p-1) + 1
m = pow(c, d, p*q)
print(long_to_bytes(m))
# 'NCTF{70u2_nn47h_14_v3ry_gOO0000000d}'

[RoarCTF2019] RSA

题目:

A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

A中的x,y可以爆破出来x=2,y=83

(ecause n=pcdot qapprox z^2cdot xcdot y\ herefore zapproxsqrt{frac{n}{xcdot y}})

又q=nextPrime(z)

可以先求出大概z的值，再爆破出q

e的话也可以先尝试常见的，不行再爆破一下试试，再不行就试试rabin

这里的e直接就是65537，常见

Exp:

import gmpy2
from Crypto.Util.number import long_to_bytes, inverse

def blast_x_y(A):
    for x in range(1000):
        for y in range(1000):
            try:
                if (((y % x)**5) % (x % y))**2019 + y**316 + (y + 1) // x == A:
                    print(x, y)
                    break
            except ZeroDivisionError:
                continue


def find_q(n, z):
    while (True):
        tmp = gmpy2.next_prime(z)
        if n % tmp == 0:
            return tmp


def main():
    A = 2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
    n = 117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
    c = 41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

    blast_x_y(A)
    z_about = gmpy2.iroot(n // 166, 2)[0]
    q=find_q(n,z_about)
    p=n//q
    e = 0x10001
    d=gmpy2.invert(e,(p-1)*(q-1))
    m=gmpy2.powmod(c,d,n)
    print(long_to_bytes(m))

if __name__ == '__main__':
    main()

Flag:RoarCTF{wm-l1l1ll1l1l1l111ll}

[新春战疫] warm_up -- e,(phi)不互素

题目:

challenge.py

from Crypto.Util.number import *
from encode import KEY

q=getPrime(1024)
p=getPrime(1024)
r=getPrime(1024)

s=getPrime(1500)

e1=125794
e2=42373

n1=p*q
n2=p*r
n3=p*q*s
c1=pow(s,e1,n1)
Key=int(KEY.encode('hex'),16)
key_encode=pow(Key,e2,n3)

with open("enc","a")as f:
    f.write("c1: "+str(c1)+"
")
    f.write("n1: "+str(n1)+"
")
    f.write("n2: "+str(n2)+"
")
    f.write("key_encode: "+str(key_encode)+"
")

Encode.py

from flag import flag
import os


KEY = os.urandom(len(flag))

dec=int(flag.encode('hex'),16)


assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)

#enc: 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809

思路是很清晰的,主要的问题就是在一开始求出s的地方,gcd(e,(p-1)*(q-1))==2

思路是

(b=gcd(e,phi(n))\e=acdot b)

此时(gcd(a,phi(n))=1)

原式是(m^eequiv c mod n)改写成(m^{ab}equiv cmod n)

又存在e的逆是d,所以(ecdot dequiv acdot bcdot dequiv 1 mod phi(n))

所以a的逆是(bcdot d),可以gmpy2.invert(a,(p-1)*(q-1))求出

所以(m^{abbd}equiv m^bequiv c^{bd}mod n)

这题就简化成了(s^2equiv c_1^{bd}mod n_1)

然后因为s=getPrime(1500)大的恐怖,没办法直接开方或者爆破求出,可以用算法去求解二次剩余,或者直接用rabin attack的方法去解,这里用rabin的方法解

后面的线性位移都可以直接逆,&mask,是纸老虎,没什么用的,不会的脚本可以直接用z3去跑

exp:

from Crypto.Util.number import *

c1 = 9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855
n1 = 15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2 = 16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
key_encode = 154190230043753146353030548481259824097315973300626635557077557377724792985967471051038771303021991128148382608945680808938022458604078361850131745923161785422897171143162106718751785423910619082539632583776061636384945874434750267946631953612827762111005810457361526448525422842867001928519321359911975591581818207635923763710541026422076426423704596685256919683190492684987278018502571910294876596243956361277398629634060304624160081587277143907713428490243383194813480543419579737033035126867092469545345710049931834620804229860730306833456574575819681754486527026055566414873480425894862255077897522535758341968447477137256183708467693039633376832871571997148048935811129126086180156680457571784113049835290351001647282189000382279868628184984112626304731043149626327230591704892805774286122197299007823500636066926273430033695532664238665904030038927362086521253828046061437563787421700166850374578569457126653311652359735584860062417872495590142553341805723610473288209629102401412355687033859617593346080141954959333922596227692493410939482451187988507415231993
enc = 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809

p = math.gcd(n1, n2)
q = n1 // p
r = n2 // p
phi1 = (p - 1) * (q - 1)
e1 = 125794
e2 = 42373

e1 = e1 // 2
d1 = inverse(e1, phi1)

sp = pow(c1, (p + 1) // 4, p)
sq = pow(c1, (q + 1) // 4, q)
yp = inverse(p, q)
yq = -(yp * p - 1) // q
r1 = (yp * p * sq + yq * q * sp) % n1
r2 = n1 - r1
r3 = (yp * p * sq - yq * q * sp) % n1
r4 = n1 - r3

sc = [r1, r2, r3, r4]
ss = []
print(sc)
for i in sc:
    s = pow(i, d1, n1)
    n3 = p * q * s
    phi2 = (p - 1) * (q - 1) * (s - 1)
    d2 = inverse(e2, phi2)
    key = pow(key_encode, d2, n3)
    dec = key ^ enc
    low200 = dec & ((1 << 200) - 1)
    low135 = dec & ((1 << 135) - 1)
    high135 = dec >> 200
    high135 ^= low135
    res = high135 << 200 | low200
    print(long_to_bytes(res))

其他题目之后再补充……