抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

CryptoCTF题目总结

crypto日常学习

发布于：2024年12月23日

次浏览

By 4cad

加密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env python

import gmpy2
from fractions import Fraction
from secret import p, q, s, X, Y
from flag import flag

assert gmpy2.is_prime(p) * gmpy2.is_prime(q) > 0
assert Fraction(p, p+1) + Fraction(q+1, q) == Fraction(2*s - X, s + Y)
print 'Fraction(p, p+1) + Fraction(q+1, q) = Fraction(2*s - %s, s + %s)' % (X, Y)

n = p * q
c = pow(int(flag.encode('hex'), 16), 0x20002, n)
print 'n =', n
print 'c =', c

1
2
3
4
gmpy2.is_prime(p) * gmpy2.is_prime(q) > 0
Fraction(p, p+1) + Fraction(q+1, q) = Fraction(2*s - 153801856029563198525204130558738800846256680799373350925981555360388985602786501362501554433635610131437376183630577217917787342621398264625389914280509, s + 8086061902465799210233863613232941060876437002894022994953293934963170056653232109405937694010696299303888742108631749969054117542816358078039478109426)
n = 161010103536746712075112156042553283066813155993777943981946663919051986586388748662616958741697621238654724628406094469789970509959159343108847331259823125490271091357244742345403096394500947202321339572876147277506789731024810289354756781901338337411136794489136638411531539112369520980466458615878975406339
c = 64166146958225113130966383399465462600516627646827654061505253681784027524205938322376396685421354659091159523153346321216052274404398431369574383580893610370389016662302880230566394277969479472339696624461863666891731292801506958051383432113998695237733732222591191217365300789670291769876292466495287189494

挺有意思的一道题，就是要想办法从Fraction(p, p+1) + Fraction(q+1, q) == Fraction(2*s - X, s + Y)里面再得到一个有用的信息，首先我们可以得到如下的等式

pp+1+q+1q=2∗s−Xs+Y\frac{p}{p+1} + \frac{q+1}{q} = \frac{2*s-X}{s+Y}

很明显左边直接通分的话是不能得到有用的信息的（因为一边是+，一边式-，X和Y检验一下也都不是素数）

因为是从再拿一个关于p和q的等式入手，所以我们可以把右边的分子未知的给消掉，很容易想到

pp+1+q+1q−2=2∗s−Xs+Y−2pp+1+q+1q−2=−X−2∗Ys+Yp−q+1q∗(p+1)=−X−2∗Ys+Y\begin{array}{l} \frac{p}{p+1} + \frac{q+1}{q} - 2= \frac{2*s-X}{s+Y} - 2\\ \frac{p}{p+1} + \frac{q+1}{q} - 2= \frac{-X-2*Y}{s+Y}\\ \frac{p-q+1}{q*(p+1)} = \frac{-X-2*Y}{s+Y} \end{array}

这边很明显可以得到

p−q+1=−X−2∗Yp-q+1=-X-2*Y

再结合n的等式解个方程就可以拿到flag了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import bytes_to_long
from gmpy2 import iroot



X = 153801856029563198525204130558738800846256680799373350925981555360388985602786501362501554433635610131437376183630577217917787342621398264625389914280509
Y = 8086061902465799210233863613232941060876437002894022994953293934963170056653232109405937694010696299303888742108631749969054117542816358078039478109426
n = 161010103536746712075112156042553283066813155993777943981946663919051986586388748662616958741697621238654724628406094469789970509959159343108847331259823125490271091357244742345403096394500947202321339572876147277506789731024810289354756781901338337411136794489136638411531539112369520980466458615878975406339
c = 64166146958225113130966383399465462600516627646827654061505253681784027524205938322376396685421354659091159523153346321216052274404398431369574383580893610370389016662302880230566394277969479472339696624461863666891731292801506958051383432113998695237733732222591191217365300789670291769876292466495287189494

p, q = var('p q')
res = solve([p - q + 1 + X + 2 * Y == 0, p * q - n == 0], p, q)
res

p, q = 12604273285023995463340817959574344558787108098986028639834181397979984443923512555395852711753996829630650627741178073792454428457548575860120924352450409, 12774247264858490260286489817359549241755117653791190036750069541210299769639605520977166141575653832360695781409025914510310324035255606840902393222949771
d = inverse(0x10001, (p - 1) * (q - 1))
print(long_to_bytes(int(iroot(pow(c, d, n), 2)[0]))) #b'CCTF{4Ll___G1rL5___Are__T4len73E__:P}'

Oak land

加密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from secrets import flag

flag = b'D0g3xGC{**************}'

p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576

x = bytes_to_long(flag)
assert x < p
c = (110 * pow(e, x, p) + 313 * pow(f, x, p) + 114 * pow(g, x, p)) % p
print(f'c = {c}')

'''
c = 5003324252656056930087505194738200296872282299746430611085214151768620410152366859389263573717075916742795347155844500093363517699628404615954372680403623746687159249269535039393284499190947340286216945761058
'''

这题和XYCTF的fakeRSA有点像，我刚开始是想到转到矩阵上去解题了

这边的p我们分解一下可以发现p-1是光滑的，那么dlp就很好求了

那么我们现在只要求出exe^x、fxf^x、gxg^x其中任意一个的值，就可以拿到x的值

这边其实是有如下的隐含条件

f≡e−1 (mod p)g≡e−2 (mod p)\begin{array}{l} f\equiv e^{-1} \ (mod\ p)\\ g\equiv e^{-2}\ (mod\ p) \end{array}

带入原方程，很容易得到

110∗ex+313∗e−x+114∗e−2x≡c (mod p)110*e^x+313*e^{-x}+114*e^{-2x} \equiv c \ (mod\ p)

简单换元法一下，有ex=te^x = t，再整理一下，有

110∗t3−c∗t2+313∗t+114≡0 (mod p)110*t^3-c*t^2+313*t+114 \equiv 0 \ (mod\ p)

直接roots解一下然后再dlp一下就行了

exp：

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
c = 5003324252656056930087505194738200296872282299746430611085214151768620410152366859389263573717075916742795347155844500093363517699628404615954372680403623746687159249269535039393284499190947340286216945761058

R.<t> = Zmod(p)[]
F = 110 * t ^ 3 - c * t ^ 2 + 313 * t + 114

g = 31337
y = F.roots()[0][0]
x = discrete_log(y, mod(g, p))
print(long_to_bytes(int(x)))  #b'D0g3xGC{C0mbin@ti0n_0f_d1sCretE}'

更新于：2024年12月23日

评论

评论区