Buuctf刷题Crypto 5day

标签：phi Buuctf gmpy2 Crypto 5day flag import 素数 mod

1、[WUSTCTF2020]佛说：只能四天

先看题目，给了三个文件：

Buuctf刷题Crypto 5day_费马小定理

尊即寂修我劫修如婆愍闍嚤婆莊愍耨羅嚴是喼婆斯吶眾喼修迦慧迦嚩喼斯願嚤摩隸所迦
摩吽即塞願修咒莊波斯訶喃壽祗僧若即亦嘇蜜迦須色喼羅囉咒諦若陀喃慧愍夷羅波若劫
蜜斯哆咒塞隸蜜波哆咤慧聞亦吽念彌諸嘚嚴諦咒陀叻咤叻諦缽隸祗婆諦嚩阿兜宣囉吽色
缽吶諸劫婆咤咤喼愍尊寂色缽嘚闍兜阿婆若叻般壽聞彌即念若降宣空陀壽愍嚤亦喼寂僧
迦色莊壽吽哆尊僧喼喃壽嘚兜我空所吶般所即諸吽薩咤諸莊囉隸般咤色空咤亦喃亦色兜
哆嘇亦隸空闍修眾哆咒婆菩迦壽薩塞宣嚩缽寂夷摩所修囉菩阿伏嘚宣嚩薩塞菩波吶波菩
哆若慧愍蜜訶壽色咒兜摩缽摩諦劫諸陀即壽所波咤聞如訶摩壽宣咤彌即嚩蜜叻劫嘇缽所
摩闍壽波壽劫修訶如嚩嘇囉薩色嚤薩壽修闍夷闍是壽僧劫祗蜜嚴嚩我若空伏諦念降若心
吽咤隸嘚耨缽伏吽色寂喃喼吽壽夷若心眾祗喃慧嚴即聞空僧須夷嚴叻心願哆波隸塞吶心
須嘇摩咤壽嘚吶夷亦心亦喃若咒壽亦壽囑囑

Buuctf刷题Crypto 5day_2d_02

首先将佛语解码：

Buuctf刷题Crypto 5day_费马小定理_03

得到核心价值观解码：

Buuctf刷题Crypto 5day_3c_04

看到最后doyouknowfence，得知用栅栏解码：

Buuctf刷题Crypto 5day_3c_05

但发现不对劲，所以将后面提示删掉

Buuctf刷题Crypto 5day_费马小定理_06

一样的步骤，再用凯撒解密，根据提示，凯撒为什么叫凯撒，位移为3是凯撒

Buuctf刷题Crypto 5day_2d_07

位移为3的字符串为：O5RXIZRSGAZDA63ONFPWQYLPL54GSYLOM5PXQ2LBNZTV6ZDBL53W67I_

再用base32解密，得到wctf2020{ni_hao_xiang_xiang_da_wo}，提交改为flag{ni_hao_xiang_xiang_da_wo}

2、[NCTF2019]childRSA

刚看题目，第一感觉就是什么玩意~，没有头绪，没办法，看代码就要戒急戒躁，心平气和，静~静~静~

首先看这个题，已知n、c、e，肯定最后是要求e，但是求e需要知道p和q，所以目前重点放到求p和q来，题目给了p和q的生成方法，即（p-1）和（q-1）是多个素数的乘积，但是如何求出p和q那？这里要引入费马小定理：

若b为一个素数，则对于任意整数a，有a(b-1) = 1 (mod b)

根据费马小定理，有a^(b-1) - 1是b的倍数

拓展一下，又有a^k*(b-1) - 1是b的倍数，系数k为正整数

回到题目中来，根据p和q的生成方式，我们知道(p-1)和(q-1)由前10000个素数中的若干个素数相乘得到

因此，前10000个素数的乘积记为∏，则∏肯定为(p-1)和(q-1)的倍数，令∏ = k*(p-1)

由费马小定理，有2^∏-1 = a^k*(p-1)-1是p的倍数

gcd(2^∏-1, n) = p，得到p，但是直接计算2^∏计算量会很大，所以再进一步优化

2∏ = 1 (mod p)，即2∏ = 1 + k1*p
而2∏ % n = 2∏ - k2n = 2∏ - k2pq
两边同时% p，有2∏ % n = 2∏ (mod p)
所以同样有2∏ % n = 1 (mod p)

现在只用计算2^∏ (mod n)，模幂计算会比直接幂计算快很多

代码如下：

import gmpy2
from Crypto.Util.number import *
from Crypto.Util.number import isPrime, sieve_base as primes
e=0x10001
n=32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c=26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
prd=1
#primes为前10000个素数的列表
for i in primes:
    prd=i*prd
p=gmpy2.gcd(gmpy2.powmod(2,prd,n)-1,n)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

运行得到NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}

3、这是什么

密码学好多奇形怪状的编码，这个题就称之为JSfuck编码，解密工具

Buuctf刷题Crypto 5day_费马小定理_08

得到flag{a0448fd730b62c13ca80200c4529daa2}

4、[HDCTF2019]bbbbbbrsa

这是一个简单的RSA，我不明白题目为什么最后给了c的取值，我们不难看出c被base64加密，倒着输出然后解密，那这个题的难度就只是暴力破解e了。

import gmpy2
from base64 import b64encode as b32encode
from base64 import b64decode as b32decode
from Crypto.Util.number import *
import random
p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
# c='==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM'
# print(str(c)[::-1])
# c1='MjM3Mzc0MDY5OTUyOTM2NDk5MTc2MzU4OTMyNDIwMDA5MzQ2NjIwNjc4NTU2MTgzNjEwMTg0MDM4MTYyMjIzNzIyNTUxMjIzNDYzMg=='
# print(b32decode(str(c1)))
c=2373740699529364991763589324200093466206785561836101840381622237225512234632q=n//p
phi=(p-1)*(q-1)
e=random.randint(50000,70000)
for e in range(50000,70000):
    if gmpy2.gcd(e,phi)==1:
        d=gmpy2.invert(e,phi)
        m=pow(c,d,n)
        m=str(long_to_bytes(m))
        if 'flag' in m:
            print(m)
            break

得出flag{rs4_1s_s1mpl3!#}