crypto的小池塘

crypto的小池塘

是 crypto的小池塘 哒！

crypto内容持续更新中！

古典密码和其他

凯撒密码

凯撒密码有一个变种，即偏移量在原来的基础上会逐渐递增或递减，如：

1
_dX]pZT]VOUZNSh

根据flag的开头猜出第一个字母的偏移量然后再解即可

1
2
3
4
c='_dX]pZT]VOUZNSh'
for i in range(7,7+len(c)):
    print(chr(ord(c[i-7])+i),end='')
#flag{fake_flag}

rot密码

跟凯撒差不多，但rot会对数字、字母和符号采用不同的偏移量

维吉尼亚

这种一般都会有大段的英文组成，解出来后会有一段英文，在里面找到flag即可偶尔看看这些英文文章或许不错？
网站一把梭
维吉尼亚
字频分析

栅栏密码

有普通的栅栏密码和W型栅栏密码，以及其他的，但目前只遇到这两个
一般来说比较明显，可以一眼看出是打乱了顺序的flag
直接工具一把梭就好

burros wheeler变换

和栅栏密码有点类似
网站一把梭
burros wheeler变换

base家族

生活习性一般为群居，有较少的个体会单独出现
工具一把梭

rabbit加密

和base64有点像，但不是
特点就是rabbit加密的密文开头一定是U2FsdGVkX1

摩斯密码

无需多盐
有的时候可以考虑取倒序再解

各种奇怪的编码

一般会给提示，把提示里的名词/名词的英文+“加密”然后去网上搜搜看有没有
稍微整合一下遇到过的
1.unicode(开头带\u的)
2.hill密码
3.云影密码
4.阴阳怪气密码
5.Ook密码(只会出现.!?)
6….

RSA

N比较小

yafu分解或者factordb上去查

p,q比较接近

yafu分解
如果q是p的下一个素数可以直接开根然后取下一个素数
如果没那么接近可以尝试费马分解

已知p的高位(或低位)

需要知道p一半多一点的位
然后可以使用coppersmith来求出未知的部分

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
print(f'{n=}')
print('p=',p>>200)
#n=112504979083712229531952757191194732828499706371472784719813972405778703417247176790237513106376618450306935577929225321894114864615650356115078192433412933614500196557250554235973290182450168320807821949691618499503517524567476630509814549179909620880384733611969002850838245795773226688747995514766739694723
#p= 6523821383236155809139380148039921541898396152483777060219989822945258930310576045651663651099
1
2
3
4
5
6
7
8
9
10
n=112504979083712229531952757191194732828499706371472784719813972405778703417247176790237513106376618450306935577929225321894114864615650356115078192433412933614500196557250554235973290182450168320807821949691618499503517524567476630509814549179909620880384733611969002850838245795773226688747995514766739694723
p= 6523821383236155809139380148039921541898396152483777060219989822945258930310576045651663651099
p=p<<200

R.<x>=PolynomialRing(Zmod(n))
f=p+x
roots=f.small_roots(X=2^200,beta=0.4)
print(roots)
#[1021435571904691551547239506034919073476937520743412292671445]
p=p+roots[0]

已知低位也是一样的
需要注意一下这时方程x的系数不是1，所以要再加一句f=f.monic()

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
print(f'{n=}')
print('p=',p%2**312)
#n=89820736169682478448552519628218400705135210973260509778007045831883668969527110280533187547246617801981864105163972853781185965361518351893786764486150702831984065217897337271844754064100947812093154222574318035632483431419851762377108959021951925201490503252582574906016560633323642437493362618007712135887
#p= 5503879275028571598277317489624851891721566574579555947545006824124736548319357887871362651269
1
2
3
4
5
6
7
8
9
n=89820736169682478448552519628218400705135210973260509778007045831883668969527110280533187547246617801981864105163972853781185965361518351893786764486150702831984065217897337271844754064100947812093154222574318035632483431419851762377108959021951925201490503252582574906016560633323642437493362618007712135887
p= 5503879275028571598277317489624851891721566574579555947545006824124736548319357887871362651269

R.<x>=PolynomialRing(Zmod(n))
f=p+x*2**312
f=f.monic()
roots=f.small_roots(X=2^200,beta=0.4)
print(roots)
#[1005017440926667857292176627451616359396335830870171531975062]

如果已知p的低位，那么q的低位也可以求出来

1
2
3
4
5
6
x=100
px=p%2**x
qx=q%2**x
nx=n%2**x
px*qx%2**x==nx
#True

只需要在2^x上求出px的逆元然后乘nx即可
可以在已知q的高位，p的低位的时候用然后求出q

另外在别的地方看到了应该是coppersmith的具体实现，所以记录一下，平常用sagemath里自带的small_roots即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from subprocess import check_output
from re import findall
from sage.all import *

def flatter(M):  # flatter
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

def matrix_overview(BB):  # see the shape of matrix
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

def Small_Roots_Univariate(f, X=None, beta=1.0, epsilon=None):  # 多项式f,X,beta,epsilon

    delta = f.degree()  # 度delta
    N = f.parent().characteristic()  # 模数N
    PR = PolynomialRing(ZZ, 'x')
    x = PR.gen()

    Zm = f.base_ring()  # Zmod(N)
    f = f.change_ring(ZZ)  # ZZ下f(x)
    if not f.is_monic():  # 首一
        f = f.monic()  # f = f * f[delta].inverse_mod(N)

    m = ceil(max(beta * beta / (delta * epsilon), 7 * beta / delta))  # m
    t = floor(delta * m * (1 / beta - 1))  # t
    #print('m={}, t={}'.format(m, t))

    f_ij = []
    for i in range(m):
        for j in range(delta):
            f_ij.append(x ** j * N ** (m - i) * f ** i)  # shift g_ij(x)
    for i in range(t):
        f_ij.append(x ** i * f ** m)  # shift h_i(x)

    monomials = []
    for g in f_ij:
        monomials += g.monomials()  # 统计所有出现的单项 x^i
    monomials = sorted(set(monomials))  # 去重并排序

    M = Matrix(ZZ, len(f_ij), len(monomials))  # 行数为多项式个数，列数为所有单项可能个数
    for i in range(M.nrows()):
        for j, monomial in enumerate(monomials):
            M[i, j] = f_ij[i].monomial_coefficient(monomial) * monomial.subs(x=X)  # g_ij(xX)和h_i(xX)
    #matrix_overview(M)  # see
    assert M.nrows() == M.ncols()  # 方阵 nrows()=ncols()
    B = flatter(M)  # flater加速
    #print('end LLL')
    for j in range(M.nrows()):  # 得到f(xX)，构建f(x)，求根检验
        Cx = sum(ZZ(B[j, i] // monomials[i](X)) * monomials[i] for i in range(M.ncols()))  # construct polynomial,
        R = Cx.roots()  # get roots
        roots = [Zm(r[0]) for r in R if abs(r[0]) <= X]  # check x0<=X
        roots = [r for r in roots if gcd(N, ZZ(f(r))) >= ZZ(floor(N ** beta))]  # check gcd(f(x_0),N)>N^beta
        if roots:
            return roots  # 返回root

椭圆曲线

AES

to be continue…

crypto
#crypto
crypto的小池塘
https://bddye.github.io/2025/02/01/crypto的小池塘/
作者
蹦跶的鱼儿
发布于
2025年2月1日
许可协议