RSA证明

一、RSA介绍

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。
RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。

二、已知条件

RSA的加密规则：$ \color{blue}{m^e \equiv c\pmod n}$
RSA的解密规则：$\color{red}{c^d \equiv m\pmod n}$

约束条件及规则说明：

m为明文字符，c为密文字符
m为0到n-1之间的数值
n=pq，p,q为素数
φ(n)=(p-1)*(q-1) [根据欧拉定理]
e与φ(n)互素
$ ed \equiv 1\pmod {φ(n)}$
欧拉公式$m^φ(n) \equiv 1\pmod n$

要根据加密规则，数论及欧拉定理，来证明解密公式正确性：$\color{red}{c^d \equiv m\pmod n}$

三、证明过程

step1、根据加密规则公式$ \color{blue}{m^e \equiv c\pmod n}$
可以得出 $$c=m^e-kn$$
step2、将C带入解密公式，得到
$$(m^e-kn)^d \equiv m\pmod n$$
step3、左边的展开中，除了第一项以外，其他项都与n相乘过，所以可以直接忽略左边括号中的kn项目，即：
$$m^{ed} \equiv m\pmod n$$
step4、因为 $ed\equiv1 \pmod {φ(n)}$ 即：
$$ed=hφ(n)+1$$
step5、上述结论代入step3的公式，得到
$$m^{hφ(n)+1} \equiv m \pmod n $$
step6、分情况讨论
6.1 、m与n互质（如果你已经忘了m和n是什么了，请往前再看一遍）
根据欧拉定理$m^φ(n) \equiv 1\pmod n$ 得到 $m^{φ(n)}=kn+1$
然后左右两边分别h次方得到(kn+1)的h次方还是kn+1只不过这里的k变了：
$$(m^{φ(n)})^h=kn+1$$
然后左右两边乘以m即得到$$m^{hφ(n)+1} \equiv m \pmod n $$
6.2 、m与n不互质
此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。
以 m = kp为例，这时k与q必然互质。如果k与q 不为互质关系，则k=tq, m= tqp=tn, 但是按照RSA规范，m∈(0…n−1) m\in(0…n-1)m∈(0…n−1), m < n的，所以k与q肯定是互质关系的。由于k与q互质，p与q互质，kp与q肯定互质，则根据欧拉定理，下面的式子成立：
$$\Large (kp)^{ q-1} \equiv 1\pmod q$$
进一步扩展，可得：
$$ \Large [(kp)^{ q-1}]^{h(p-1)}\times kp \equiv kp\pmod q$$
即
$$\Large (kp)^{ed} \equiv kp\pmod q$$
进一步改写成等式：
$$\Large (kp)^{ed} = kp+tq$$
显然，t能被p整除，即t=t’p,可以得出
$$\Large (kp)^{ed} = kp+t’pq$$

因为m=kp, n=pq, 最后得出
$$\Large m^{ed} \equiv m\pmod n$$
解密公式得到完全证明。

四、关于共模攻击脚本（其他的脚本要求安一堆奇怪的包，在win10还装不上，这里贴一个野生的共模攻击脚本

# coding=utf-8
import sys
sys.setrecursionlimit(10000000)
"""
选择相同的模 n 加密相同的信息 m
"""

helpstr = '''
usage:
    c1 = m ^ e1 % n
    c2 = m ^ e2 % n
'''


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


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def main():
    print(helpstr)
    n = int(input("input n: "))
    c1 = int(input("input c1: "))
    c2 = int(input("input c2: "))
    e1 = int(input("input e1: "))
    e2 = int(input("input e2: "))
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    # 求模反元素
    if s1 < 0:
        s1 = - s1
        c1 = modinv(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = modinv(c2, n)
    m = (c1**s1)*(c2**s2) % n
    print(m)


if __name__ == '__main__':
    main()

分解模数脚本

# 分解模数n
def rsa_moder(n):
    base = 2
    while base < n:
        if n % base == 0:
            return base, n // base
        base += 1


# 求欧拉函数f(n)
def rsa_get_euler(prime1, prime2):
    return (prime1 - 1) * (prime2 - 1)


# 求私钥
def rsa_get_key(e, euler):
    k = 1
    while True:
        if (((euler * k) + 1) % e) == 0:
            return (euler * k + 1) // e
        k += 1


# 根据n,e计算d(或根据n,d计算e)
def get_rsa_e_d(n, e=None, d=None):
    if e is None and d is None:
        return

    arg = e
    if arg is None:
        arg = d

    primes = rsa_moder(n)
    p = primes[0]
    q = primes[1]

    d = rsa_get_key(arg, rsa_get_euler(p, q))

    return d


def test():
    str_fmt = 'n: {:<10} e: {:<10} d: {:<10}'

    # 导入rsa库
    import rsa as rsa
    key = rsa.newkeys(24)

    # 产生rsa密钥对
    if isinstance(key[1], rsa.PrivateKey):
        print(str_fmt.format(key[1].n, key[1].e, key[1].d))

    # 解密
    n = 14666299
    d = 2101153
    e = get_rsa_e_d(n, None, d)
    print(str_fmt.format(n, e, d))

    n = 12748507
    e = 65537
    d = get_rsa_e_d(n, e, None)
    print(str_fmt.format(n, e, d))

if __name__ == '__main__':
    test()