奇怪的sar
from Crypto.Util.number import *
key = 'flag{**********}'
bits = 1024
msg = bytes_to_long(key.encode())
e = 65537
p = getPrime(bits)
q = getPrime(bits)
n = p * q
def encrypt1(msg, e, n):
c = pow(msg, e, n)
return c
seed = p ^ q
a = getPrime(bits)
b = getPrime(bits)
n1 = getPrime(bits)
def encrypt2(seed):
enc = []
for i in range(10):
seed = (a * seed + b) % n1
enc.append(seed)
return enc
c = encrypt1(msg, e, n)
enc = encrypt2(seed)
print("n = ", n)
print("c = ", c)
print("n1 = ", n1)
print("enc = ", enc)
先求seed，LCG里的求m类型，套用模板即可：
output = [...]
t = []
for i in range(len(output)-1):
t.append(output[i+1] - output[i])
a = inverse((output[0] - output[1]), n1) * (output[1] - output[2]) % n1
b = inverse(a, n1) * output[1] - output[0] % n1
seed = (inverse(a, n1) * output[0] - b) % n1
接着计算p、q，在GKCTF2021中的XOR出现过类似的类型，可参考：[GKCTF] GKCTF x DASCTF应急挑战杯 个人(or团队) Crypto方向 writeup - 知乎 (zhihu.com)
第一次接触，作下记录：
已知：
- $n = p \cdot q$
- $seed = p \bigoplus q $
可从低位逐一爆破，
注意换下下爆破的位数。
import itertools
e = 65537
c = 14883053247652228283811442762780942186987432684268901119544211089991663825267989728286381980568977804079766160707988623895155236079459150322336701772385709429870215701045797411519212730389048862111088898917402253368572002593328131895422933030329446097639972123501482601377059155708292321789694103528266681104521268192526745361895856566384239849048923482217529011549596939269967690907738755747213669693953769070736092857407573675987242774763239531688324956444305397953424851627349331117467417542814921554060612622936755420459029769026126293588814831034143264949347763031994934813475762839410192390466491651507733968227
n = 24044063028844014127418595700558729326190738802687551098858513077613750188240082663594575453404975706225242363463089392757425008423696150244560748490108425645064339883915929498539109384801415313004805586193044292137299902797522618277016789979196782551492020031695781792205215671106103568559626617762521687128199445018651010056934305055040748892733145467040663073395258760159451903432330506383025685265502086582538667772105057401245864822281535425692919273252955571196166824113519446568745718898654447958192533288063735350717599092500158028352667339959012630051251024677881674246253876293205648190626145653304572328397
x = seed
p_list, q_list = [0], [0]
cur_mod = 1
for i in range(1024):
cur_mod *= 2#乘上2表示处理下一位
nxt_ps, nxt_qs = [], []
for pl, ql in zip(p_list, q_list):
for ph, qh in itertools.product([0, 1], repeat=2):#四种情况：[0,0],[0,1],[1,0],[1,1]
pp, qq = ph * (cur_mod // 2) + pl, qh * (cur_mod // 2) + ql
if ((pp * qq % cur_mod == n % cur_mod) and ((pp ^ qq) == x % cur_mod)):
nxt_ps.append(pp)
nxt_qs.append(qq)
p_list, q_list = nxt_ps, nxt_qs
for p, q in zip(p_list, q_list):
if (p * q == n):
print(p,q)
break
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
#b'flag{y0u_kn0w_Pruning_and_lcg}'
可参考：
[GKCTF] GKCTF x DASCTF应急挑战杯 个人(or团队) Crypto方向 writeup - 知乎 (zhihu.com)
HaM3
from Crypto.Util.number import *
from secret import flag
p, q = getPrime(64), getPrime(64)
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
assert isPrime(PP) and isPrime(QQ)
n = PP * QQ
m = bytes_to_long(flag)
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)
'''
n = 142672086626283587048017713116658568907056287246536918432205313755474498483915485435443731126588499776739329317569276048159601495493064346081295993762052633
c = 35771468551700967499031290145813826705314774357494021918317304230766070868171631520643911378972522363861624359732252684003796428570328730483253546904382041
'''
来自CRYPTO CTF2021的一道原题。
由题可知关系：
- $P = 10^x \cdot p + q$
- $Q = 10^y \cdot q + p$
- $PP = 10^{x^{‘}} \cdot P + Q$
- $QQ = 10^{y^{‘}} \cdot Q + P$
则$n = 10^{x+y+x^{‘}+y^{‘}} \cdot pq + … + pq$
只保留第一项和最后一项是因为这两项单独拿出来的值与pq相等，很显然的事。
也就是说n的部分高位与pq的相等，低位也如此。我们可以通过测试来验证：
while True:
p, q = getPrime(64), getPrime(64)
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
if isPrime(PP) and isPrime(QQ):
n = PP * QQ
break
print(str(n)[:18],str(pq)[:18])
print(str(n)[-19:],str(pq)[-19:])
#989521662502104542 989521662502104542
#5442470176580223011 5442470176580223011
也就是说我们知道了pq的36位，剩余的两位爆破即可。
不过上面的是我们测试的数据，实际可能不太一样，需要改下参数（总之知道解题思路就好）：
# sage
'''nbit = 64
n = 142672086626283587048017713116658568907056287246536918432205313755474498483915485435443731126588499776739329317569276048159601495493064346081295993762052633
high = str(n)[:19]
low = str(n)[-18:]
for i in range(10):
for j in range(10):
pq = int(high + str(i) + str(j) + low)
f = factor(pq)
if len(f) == 2 and f[0][0].nbits() == 64:
p = f[0][0]
q = f[1][0]
print(p,q)'''
p,q = 9937378783676979077,14357114660923972229
c = 35771468551700967499031290145813826705314774357494021918317304230766070868171631520643911378972522363861624359732252684003796428570328730483253546904382041
e = 65537
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
fai_n = (PP-1)*(QQ-1)
d = invert(e,fai_n)
m = pow(c,d,PP*QQ)
print(long_to_bytes(m))
#b'flag{HaMbu2g3r_1S_2ea1ll_D3lci0U3_By_R3A!!}'
可参考：
CRYPTO CTF2021 MEIDUM-EASY_cryptoctf2021_Paintrain的博客-CSDN博客
第四届美团网络安全高校挑战赛_hamburgerRSA_c = pow(m,65537,n)_M3ng@L的博客-CSDN博客
BigDataEnc
import pickle
from secret import flag
from Crypto.Util.number import *
N = 128
assert flag.startswith(b'flag{') and flag.endswith(b'}')
class BigDataEnc:
def __init__(self, N):
self.a = 1
self.b = 1
self.N = N
def enc(self, flag):
bits = bin(bytes_to_long(flag))[2:]
LEN = len(bits)
assert LEN == 254
for i in range(LEN):
t = getPrime(self.N)
if int(bits[i]):
self.b *= pow(t, 20)
self.a *= pow(t, 23 + i)
else:
self.a *= pow(t, 20)
self.b *= pow(t, 23 + i)
def save(self):
file_a = open('a', 'wb')
file_b = open('b', 'wb')
pickle.dump(str(self.a), file_a)
pickle.dump(str(self.b), file_b)
file_a.close()
file_b.close()
CheckIn = BigDataEnc(N)
CheckIn.enc(flag[5:-1])
CheckIn.save()
佬写的很详细，奈何不大理解，暂时放着先
2023陕西省赛Crypto BigDataEnc_无趣的浅的博客-CSDN博客
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com