Euler's Factoring to RSA

Outline

对于 RSA 中\(N=(ma^2+nb^2)(mc^2+nd^2)\)的情况进行分析以及安全性评测。

Euler's factorization method

欧拉因式分解法是通过两种方式将数字写成两个平方和来分解数字的方法，对于一个合数\(N\)来说，若\(N=a^2+b^2\)，则可以将\(N\)进行因式分解，例如\(1000009=1000^2+3^2=972^2+235^2=293\cdot3413\)

Theoretical basis

Brahmagupta-Fibonacci 恒等式 \[(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2=(ac+bd)^2+(ad-bc)^2\]

Proof

\[a-c=kl\] \[d-b=km\] \[a+c=hm\] \[d+b=hl\] 运用Brahmagupta-Fibonacci 恒等式 \[(k^2+h^2)(l^2+m^2)=(kl+hm)^2+(km-hl)^2=((a-c)+(a+c))^2+((d-b)-(d+b))^2=4a^2+4b^2=4n\] 所以得到 \[n=((\frac{k}{2})^2+(\frac{h}{2})^2)(l^2+m^2)\] 后续求解如下： \[khl^2+khm^2=(a-c)(d+b)+(a+c)(d-b)\] \[kh(l^2+m^2)=2ad-2bc\] \[l^2+m^2=GCD(ad-bc,n)\]

Generally

对于更一般的\(N\)来说，如果\(N=ma^2+nb^2=mc^2+nd^2\)的情况应用欧拉分解是否可以进行？ 当然是可以的，但可惜欧拉在 1891 年失去了生命，没能继续进行他的研究。后世 Lucas 和 Mathews 先后对这样的情况进行了分析推导，证明了\(N\)是可分解的。

My proof

对于\(a,b,c,d,m,n\in \mathbb{Z}^+,并且gcd(ma,nb)=gcd(mc,nd)=1\) \[N=ma^2+nb^2=mc^2+nd^2\] \[N=\frac{1}{2}[m(a^2+c^2)+n(b^2+d^2)]\]

\[N(d^2-b^2)=\frac{1}{2}(ma^2d^2+mc^2d^2+nb^2d^2+nd^4-ma^2b^2-mc^2b^2-nb^4-nb^2d^2)\] \[\because n(d^2-b^2)=m(a^2-c^2)\]

\[\therefore N=\frac{1}{2}[ma^2d^2-mb^2c^2+mc^2d^2-ma^2b^2+m(a^2-c^2)(d^2+b^2)]\] \[N=m(ad+bc)(ad-bc)\] 我们还需要另外一个等式，运用Brahmagupta-Fibonacci 恒等式得到 \[N^2=(ma^2+nb^2)(mc^2+nd^2)\] \[N^2=(mac-nbd)^2+mn(ad+bc)^2\] 因为\(gcd(m,N)=1\),由此得到 \[N=gcd(N,ad-bc)* \frac{N}{gcd(N,ad-bc)}\]

Apply to RSA

在 RSA 传统加密中我们知道，\(N\)的选取尤为重要，如果选取的\(N\)易于分解，那么明文将不再安全。 对于\(N=(ma^2+nb^2)(mc^2+nd^2)\)，即\(p=ma^2+nb^2,q=mc^2+nd^2\)

针对这种看似数字很大的\(N\),下面进行一些实际的代码生成与攻击。

P、Q_generate

def genprime(m,n):
    while True:
        x = random.getrandbits(150)
        y = random.getrandbits(150)
        p = m*x ** 2 +  n*y ** 2
        if isPrime(p) :
            return p, x, y

abcd_generate

while True:
    m = getPrime(212)
    n = getPrime(212)
    p, xp, yp = genprime(m,n)
    q, xq, yq = genprime(m,n)
    N = p * q
    a = abs(m*xp * xq - n * yp * yq)
    b = abs(xp * yq + xq * yp)
    assert N == a ** 2 + m*n * b ** 2
    c = abs(m*xp * xq + n * yp * yq)
    d = abs(xp * yq - xq * yp)
    assert N == c ** 2 + m*n * d ** 2
    if a.bit_length() <= 512 and b.bit_length() <= 300 and c.bit_length() <= 512 and d.bit_length() <= 300:
        break

Encrypt

flag = b"you_have_already_understood_this"
N = p*q
e=65537
msg = bytes_to_long(flag)
Cipher = pow(msg,e,N)

Attack

p=GCD(a*d-b*c,N)
q=N//p
d=gmpy2.invert(e,(p-1)*(q-1))
msg=long_to_bytes(pow(Cipher,d,N))
print(msg)
# b'you_have_already_understood_this'