RSA(3)

# RSA(3)

# 裴蜀定理

对于整数域中的不定方程 ax+by=m，其有解的充要条件为 gcd⁡(a,b)∣m。

# 欧几里得算法

extgcd 原理

1. 假设边界；
2. 假设递归量，并不断归约。

边界假设为 gcd (a, 0) = a，当 a>b 时，gcd (b, a% b)。

当 a=g,b=0 时：

x=0,y=1。

找这两个式子中的转移关系，x1 与 x2；y1 与 y2 之间的联系。

$$x_1 = y_2$$

$$y_1 = x_2 - \frac{a}{b} y_2$$

1
2
3
4
5
6

def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    
    g, x, y = extgcd(b, a%b)
    return g, y, x - (a//b)*y

# Rabin 算法

e=4

$$c\equiv (m^2)^2 \pmod n$$

# 连分数定理

当 a 和 b 满足：

$$\left| x - \frac{a}{b} \right| < \frac{1}{2b^2}$$

x 可以近似为 a/b。两个 n 接近时可以考虑连分数定理。

1
2

q1, q2 = attack(n1, n2)
assert n1/n2 - q1/q2 < 1/(2*q2*q2)

已知：

$$mr^{-1}\equiv a \pmod p$$

由整数域转换到实数域：

$$m=ar+kp$$

$$\frac{m}{rp} = \frac{a}{p}+\frac{k}{r}$$

$$\frac{a}{p} \approx -\frac{k}{r}$$

# 中国剩余定理

CAT 主要是利用同余式：

$$x\equiv a_1\pmod {n_1}$$

$$x\equiv a_2\pmod {n_2}$$

$$x \equiv x_0 \pmod{n_1 \ldots n_m}$$

$$x < \prod n_i$$

$$x_0=x$$

1
2
3
4
5

def getn(bits):
    n = 1
    while n.bit_length() < bits:
        n *= random.choice(sieve_base)
    return n

# 共模攻击

$$m^{3e}可以看成(m^3)^e$$