rsa-loss
from Crypto.Util.number import *
from gmpy2 import *
import re
p = getPrime(100)
q = getPrime(100)
n = p * q
e = 65537
message = b""
m = bytes_to_long(message)
c = pow(m, e, n)
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')
d = invert(e,(p-1)*(q-1))
newm = pow(c, d, n)
print(long_to_bytes(newm))
# c = 356435791209686635044593929546092486613929446770721636839137
# p = 898278915648707936019913202333
# q = 814090608763917394723955024893
# m = b'Xxeex1eyx88x01dXxf6ix91x80hxf4x1f!xa7"x0cx9ax06xc8x06x81x15'
来自 bcactf-4.0 的原题，rsa_is_broken，找到解题脚本的话，改一下 flag 的头就可以了
https://github.com/BCACTF/bcactf-4.0/blob/main/rsa-is-broken/rsa-broken-sol.py
大致描述一下解题思路啊，首先题目给出了 ，然后有 ，于是我们有
首先毋庸置疑的是，对于任意的 ， 都是满足 ，因此我们的目标，就是找到一个 ，能使得 是以 DASCTF{ 开头, } 结尾的，就可以了。
首先第一步，我们先从0开始简单遍历一下 k，让 【因为是以} 结尾】
然后我们后面的遍历就是不断的加 了，这样是不影响最后一个字节的。
from Crypto.Util.number import *
from gmpy2 import *
import re
c = 356435791209686635044593929546092486613929446770721636839137
p = 898278915648707936019913202333
q = 814090608763917394723955024893
n = p*q
e = 65537
# the idea is that our retrieved m is in fact equivalent to the original m mod n
# so we add multiples of n to retrieve the flag
# but this is inefficient so we have to narrow it down using format
# The flag ends with }, so 7D = 125 mod 256
d = pow(e, -1, math.lcm(p-1, q-1))
m = pow(c, d, n)
while m % 256 != 125:
m += n
jump = n * 256
然后我们简单确定一下flag的长度，
我们知道 ，
经过测试我们会发现，如果我们设定一个目标flag：DASCTF{000000000000} ，我们不断的增加中间的 0，当这个目标 flag 和真的 flag 长度相同时，我们计算 ，这个 就会和 比较接近
然后我们该怎么判断我们的这个 就是 的近似值了呢？
我们可以计算 ，如果这个字符串是以 DASCTF{ 开头的，说明就差不多了，后续我们不断的加 就可以了。
target = b'DASCTF{' + b'0'*math.floor(math.log(m, 256)-7)
md = long_to_bytes(m)
while re.fullmatch(b'[0-9a-zA-Z_{}]+', md) == None:
while md[0:7] != b'DASCTF{':
mt = m + jump * math.ceil((bytes_to_long(target) - m)//jump)
target += b'0'
md = long_to_bytes(mt)
print(md)
mt += jump
md = long_to_bytes(mt)
print(md)
TH_Curve
和 2023 CTF barak 用的同一个曲线，也算是魔改题叭，具体可以看这里
转化成 Weierstrass 形式后发现 G 点的阶光滑，所以解一个dlp就行
然后这里的 d 未知，不过用给出的点的坐标带入曲线关系式算一下就行
p = 10297529403524403127640670200603184608844065065952536889
a = 2
d = 8817708809404273675545317762394593437543647288341187200
R.<x,y,z> = Zmod(p)[]
cubic = a*x^3+y^3-d*x*y*z+z^3
P = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464,1)
E = EllipticCurve_from_cubic(cubic, P, morphism=True)
P = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)
PP = E(P)
QQ = E(Q)
需要注意的点在于 m 只有120比特，然后 order 分解后最大的那个因子有点大，就不要了（降一下阶），去掉那个最大的因子剩下来的也比 120 比特大，所以问题不大。
TheremPlus
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
def decode_e(e):
if e > 1:
mul = 1
for i in range(1, e):
mul *= i
if e - mul % e - 1 == 0:
mulmod = mul % e - e
else:
mulmod = mul % e
return mulmod + decode_e(e - 1)
else:
return 0
q = getPrime(1024)
p = next_prime(q)
n = p * q
phi = (p - 1) * (q - 1)
e = abs(decode_e(703440151))
c = pow(bytes_to_long(flag), e, n)
print('n = {}n'
'c = {}'.format(n, c))
'''
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
'''
测了一下，发现 decode_e 其实就是计算素数的个数，sagemath直接算一下 prime_pi(e) 就行。不过记得 -2
剩下来就没啥了，直接开根就能分解 n，解rsa就行
baby_Curve
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import os
import hashlib
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import c, b, key, FLAG
def add_curve(P, Q, K):
a, d, p = K
if P == (0, 0):
return Q
if Q == (0, 0):
return P
x1, y1 = P
x2, y2 = Q
x3 = (x1 * y2 + y1 * x2) * pow(1 - d * x1 ** 2 * x2 ** 2, -1, p) % p
y3 = ((y1 * y2 + 2 * a * x1 * x2) * (1 + d * x1 ** 2 * x2 ** 2) + 2 * d * x1 * x2 * (x1 ** 2 + x2 ** 2)) * pow(
(1 - d * x1 ** 2 * x2 ** 2) ** 2, -1, p) % p
return x3, y3
def mul_curve(n, P, K):
R = (0, 0)
while n > 0:
if n % 2 == 1:
R = add_curve(R, P, K)
P = add_curve(P, P, K)
n = n // 2
return R
def AES_encrypt(k):
key = hashlib.sha256(str(k).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
cipher = cipher.encrypt(pad(FLAG, 16))
data = {}
data["iv"] = iv.hex()
data["cipher"] = cipher.hex()
return data
a = 46
d = 20
p1 = 826100030683243954408990060837
K1 = (a, d, p1)
G1 = (560766116033078013304693968735, 756416322956623525864568772142)
P1 = mul_curve(c, G1, K1)
Q1 = mul_curve(b, G1, K1)
print("P1 =", P1)
print("Q1 =", Q1)
# P1 = (528578510004630596855654721810, 639541632629313772609548040620)
# Q1 = (819520958411405887240280598475, 76906957256966244725924513645)
p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-c, b])
G = E.gens()[0]
P = G * key
data = AES_encrypt(key)
print("G =", G)
print("P =", P)
print("data =",data)
# G = (584273268656071313022845392380 : 105970580903682721429154563816 : 1)
# P = (401055814681171318348566474726 : 293186309252428491012795616690 : 1)
# data = {'iv': 'bae1b42f174443d009c8d3a1576f07d6', 'cipher': 'ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4'}
这里应该是非预期了，这里第一步的作用无非是想让我们计算出 c,d 来，但是我们直接用第二步给出的两个点，带入曲线方程，联立一下就能算出曲线的参数了，
然后发现点的阶是p+1。mov attack一把梭就行了
# sage: a = 770311352827455849356512448252
# ....: b = 98
# ....: p = 770311352827455849356512448287
# ....: order = 770311352827455849356512448288
# ....: gx = 584273268656071313022845392380
# ....: gy = 105970580903682721429154563816
# ....:
# ....: F = GF(p)
# ....: k = 2 # min_k E.order() | (p^k-1)
# ....: Fy = GF(p^k,'y')
# ....:
# ....: E = EllipticCurve(F,[a,b])
# ....: Ee = EllipticCurve(Fy,[a,b])
# ....:
# ....: G = E((gx,gy))
# ....: xG = E((401055814681171318348566474726 , 293186309252428491012795616690))
# ....:
# ....: Ge = Ee(G)
# ....: xGe = Ee(xG)
# ....:
# ....: R = Ee.random_point()
# ....: m = R.order()
# ....: d = gcd(m, G.order())
# ....: Q = (m//d)*R
# ....:
# ....: assert G.order()/Q.order() in ZZ
# ....: assert G.order() == Q.order()
# ....:
# ....: n = G.order()
# ....: print('computing pairings')
# ....: alpha = Ge.weil_pairing(Q,n)
# ....: beta = xGe.weil_pairing(Q,n)
# ....: print('computing log')
# ....: dd = beta.log(alpha)
# ....: print(dd)
# computing pairings
# computing log
# 2951856998192356
data = {'iv': 'bae1b42f174443d009c8d3a1576f07d6', 'cipher': 'ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4'}
key = hashlib.sha256(str(2951856998192356).encode()).digest()[:16]
iv =bytes.fromhex('bae1b42f174443d009c8d3a1576f07d6')
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(bytes.fromhex('ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4'))
print(flag)原文始发于微信公众号（Van1sh）：2024 羊城杯
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论