密码学基础

有限域GF（p）

p为mod p，p须为素数，不然域中无乘法逆元。

有限域GF(p^n)，n为正整数，p为素数
n=1，GF§，
n=2，GF(p^2)：系数为0或1的多项式，最高次不超过n-1，可以表示成长度为2的矢量

多项式运算

1.Zp中，系数模p运送，p一般为2
2.GF(2^n)，系数模2，最高次小于n，对n次多项式取模，加减乘除模实际上是对比特串进行操作
3.Grobner基
p.<a,b>=PolynomialRing(Zmod(p))a、b为多项式生成元
可以用a、b构建多项式，在此多项式环上

椭圆曲线

$$y^2=x^3+ax+b$$

群定义：

1.群元素：所有群上点
2.单位元：0
3.逆元：关于x轴对称点
4.加法封闭性：一条直线与曲线交的三个点，P+Q+R=0，P+Q=-R，显然-R也在曲线上
5.结合律：显然√
6.交换律：显然√

sage:

Curve=EllipticCurve(F,[a,b])

F代表有限域
Curve.random_point()曲线上随机一点，返回（x,y,z)

Curve.lift_x()给出横坐标，返回此横坐标在曲线上的点

K.<x> = GF(2^4, modulus=[1, 0, 0, 1, 1]) #第一个参数声明域所在空间；modulus后的列表为多项式f(x)从最高次到0次项的系数列表

f.change_ring(QQ)将f的环改为QQ有理数环

f.degree()求次数

f(7)代入求值

f^3密运算
PR.<x1,x2,x3>=PolynomialRing(Zmod(N))生成元为x1,x2,x3的模N多项式整数环
polys=[]多项式集合，所有多项式默认等式右边为0

套椭圆曲线壳的意义：

1.在域下模
2.对象之间作用须是合适的类型

OS

b’string’为bytes类型
os.urandom(n)生成n个字节的随机数，bytes类型，长度为n

丢番图方程

网址：丢番图 — SymPy 1.8.dev 文档 (osgeo.cn)

利用sympy丢番图方程公式可以直接解线性、二元二次、三元二次、毕达哥拉斯、平方和方程等。

离散对数

1.e较小时，可以直接开根号，调用gmpy2的iroot()
2.mod值须为素数
3.

常用函数

os.random(n),os.urandom(n)返回n个bytes的string，类型为bytes
getRandomRange(a,b)随机生成[a,b]范围内的数

encode()编码，即加上b’’

gmpy2.iroot(num,开方次数)[第几个根]
str.strip()去除字符串两边的空格
str.split()根据空格、回车、tab进行切片
int.bit_length()返回二进制长度

哈希函数

输入任意，输出固定

sha256()输出256bits
digest()返回bytes类型摘要

椭圆曲线方程

1.y^2=x^3+ax+b+kp,联立多个方程解
2.求某个因子，可以由两个因式求公因数

椭圆曲线加密攻击

1.Pohlig-Hellman攻击

2.SmartAttack

E(Fp)=p，曲线的阶等于模数p的情况下可解离散对数

3.MOV攻击

4.ECDSA

5.随机整数k相同可预测

6.伪造e构造合法签名

7.空摘要构造合法签名

格密码

求正交矩阵

sage解方程

x,y,z=var('x y z')
eqution1= ...==...
eqution2= ...==...
eqution3= ...==...
solutions=solve((eqution1,eqution2,eqution3),x,y,z)
for solution in solutions:
	print(solution)

UUID

UUID的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的32个字符，如：550e8400-e29b-41d4-a716-446655440000。

RSA

wiener‘s attack 爆破

已知e，n，求d

$$设ed=1+k\phi(n),当q<p<2q时，若满足\\ d<\frac13n^{\frac14}$$

https://github.com/pablocelayes/rsa-wiener-attack

py文件要放在下载的库文件夹下

或用以下模板

n = 
d = 

from tqdm import tqdm
fra = (d/n).continued_fraction()
for i in tqdm(range(len(fra))):
    k = fra.numerator(i)
    e = fra.denominator(i)

    if k != 0 and (e*d-1) % k == 0:
      try:
        phi = (e*d-1) // k
        p_plus_q = n + 1 - phi
        p_min_q = (p_plus_q^2 - 4*n)^(1/2)
        p = (p_plus_q + p_min_q) // 2
        q = n // p
        if p*q == n:
          break
      except:
        continue
      
print('p = %s' % p)
print('q = %s' % q)
print('e = %s' % d)

// and %

设y=kx+b,若b<k,则y//k=x,y%k=b

dp泄漏

RSA-详解dp泄漏_来梦桃子的博客-CSDN博客

已知e，N，dp，即可分解得到p和q，dp=d mod p-1

for i in range(1,65538):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)/i)+1)==0:
            p=((dp*e-1)/i)+1
            q=n/(((dp*e-1)/i)+1)
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)%phi

coppersmith

Coppersmith 攻击 (ruanx.net)

Coppersmith 方法_哔哩哔哩_bilibili

密码学学习笔记 之 Coppersmith’s Method | Van1sh的小屋 (jayxv.github.io)

对于一个e阶多项式f：

$$①在模n下，求出n^{\frac{1}{e}}以内的f的根\\$$

$$②在模b下，求出较小根，b\geq n^{\beta}，其中，b是n的因数$$

其中，0<β≤1

PR.<m>=polynomialRing(Zmod(n))
f=...
f=f.monic()
m=f.small_roots(X=...,beta=...)
#在RSA中，n的因数是p和q
#当p和q位数相等时，beta一般取最接近0.5的0.4，因为其只有一位小数有效
#X为未知数的上界，可以不写参数

1.m的低比特泄漏

N =
e =
c =
m =

ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = (m + x)^e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0] 
print("m:", m + x0)

2.适用于N的因数P的高位或低位泄漏

kbit = 435#p的低位数
PR.<x> = PolynomialRing(Zmod(n))
f = p0+x#p0为p的高位，x为p的低位，p0已知
x = f.small_roots(X=2^kbit, beta=0.4)
p = p0+int(x[0])
q = n // p

3.d的低比特泄漏

4.Boneh Durfee Attack(d只有1024*0.27bit)

5.已知m%r和r

欧拉定理

$$m^{\phi(n)}\equiv 1\bmod n$$

卡米歇尔定理

$$\lambda(n)=\frac{(p-1)(q-1)}{gcd(p-1,q-1)}\\ m^{\lambda(n)}\equiv1\bmod n$$

欧拉$\phi$公式

$$\phi(n)=\prod_{i=1}^rp_i^{k_i-1}(p_i-1)$$

中国剩余定理CRT

$$x\equiv a\bmod p\\ x\equiv b\bmod q\\ x=aqq^{-1}+bpp^{-1} \bmod pq$$

利用CRT解RSA：

c=libnum.solve_crt([c1,c2],[q1,q2])

多素数因子分解

已知N和phi，N有多个素数因子，直接函数分解

def factorize(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method only works for a modulus consisting of 2 primes!
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors, or None if the factors were not found
    """
    s = N + 1 - phi
    d = s ** 2 - 4 * N
    p = int(s - isqrt(d)) // 2
    q = int(s + isqrt(d)) // 2
    return p, q


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)

Pollard_Rho算法——快速分解大素数

通过已知N，分解出p和q

条件：(p-1)和(q-1)有一个大公因数β，且p.nbits()=q.nbit()=½N.nbits()

def f(x, n):
    return (pow(x, n - 1, n) + 3) % n

def rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            print('{} in {} circle'.format(j, i))
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1

低加密指数广播攻击

相同m和e,m的e次方模不同的n,得到不同的密文c,已知e,n,c

def crt(a,n):
    sum=0
    prod =reduce(lambda a,b:a*b,n)
    for n_i,a_i in zip(n,a):
        p=prod/n_i
        sum+=a_i*gmpy2.invert(gmpy2.mpz(p),n_i)*p
    return sum%prod

n=[n1,n2,n3]
c=[c1,c2,c3]
x=crt(c,n)
print(gmpy2.iroot(x,e))

AMM开根算法

e与phi不互素，无法求逆元d

def get_oneroot(p, e):
    while True:
        Zp = Zmod(p)
        g = Zp.random_element()
        g = g^((p-1) // e)
        for mult in divisors(e):
            if (mult != e):
                g2 = g^mult
                if (g2 == 1):
                    break
        else:
            return g

def decrypt(p, c, e):
    w = gcd(e, p-1)
    e1, p1 = e // w, (p-1) // w
    d = inverse_mod(e1, p1)
    c1 = pow(c, d, p)
    g, a, b = xgcd(p1, w)
    g = get_oneroot(p, w)
    m = pow(c1, b, p)
    return [ZZ(m * g^i) for i in range(w)]

mp_list = decrypt(p, c, e)
print('Find root p OK')
mq_list = decrypt(q, c, e)
print('Find root q OK')
for mp, mq in itertools.product(mp_list, mq_list):
    m = crt([mp, mq], [p, q])
    msg = long_to_bytes(int(m))
    if (b'...CTF' in msg or b'flag' in msg):
        print(msg)

中国剩余定理

p=
q=
n=
e= 

R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
 
R.<x> = Zmod(q)[]
f = x ^ e - c
f = f.monic()
res2 = f.roots()

#这里在有限域内求根，求出多个根，但要求的m`只有最小的那一个(也可以分别用RSA解法求m)

for i in res1:
    for j in res2:
        # 普普通通中国剩余定理
        m =libnum.solve_crt([int(i[0]),int(j[0])],[p,q])#c3=libnum.solve_crt([c1,c2], [q1,q2])
        flag = long_to_bytes(m)
        if flag.startswith(b'flag'):
            print(flag)
            

多小素数因子分解

N有许多小的素数因子组成，可以用sage直接求phi，euler_phi()

中国剩余定理攻击

一个数取余几次的结果，求原数

def crt(a,n):
    sum=0
    prod =reduce(lambda a,b:a*b,n)
    for n_i,a_i in zip(n,a):
        p=prod/n_i
        sum+=a_i*gmpy2.invert(gmpy2.mpz(p),n_i)*p
    return sum%prod
e=...
n=[n1,n2,n3]
c=[c1,c2,c3]
x=crt(c,n)

或直接用sage函数

e = ...

n=[n1,n2,n3]#模数
c=[c1,c2,c3]#模后余数
mm=crt(c,n)#求被模数

m=mm.nth_root(e,truncate_mode=True)

爆破

当未知数少，未知数小时，谁小爆破谁

Franklin-Reiter相关消息攻击

Franklin-Reiter相关消息攻击_Emmaaaaaaaaaa的博客-CSDN博客

总结：
如果两个信息之间存在已知的固定差异，并且在相同的模数n下进行RSA加密，那么就有可能恢复出这两个消息。
简单点说就是m和m+a两个明文在相同的e和n下进行加密，那么m就可以破解

def franklinReiter(n,e,c1,c2,a,b):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (x)^e - c1
    g2 = (a*x+b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() # 
    return -gcd(g1, g2)[0]

m=franklinReiter(n,e,c1,c2,a,b)

相关消息变种

仅仅类似相关消息攻击的加密形式，加密明文是p和q的线性组合，明文在不同e相同n下进行加密，一般解密方法：
二项式定理，指数配平，求gcd等

已知d,c,e和hint

RSA系列（更新至unusualrsa5）_sagemath中monic函数-CSDN博客