RSA破解算法研究的一些心得

最近研究RSA破解算法，找了大量资料，得到一些心得，这里记录下。
1、RSA算法有公钥和私钥，一般资料上都是数字来举例，实际看见的有字母，这里要注意下资料上的是10进制，实际是16进制。
2、公钥和私钥是一对，一个私钥对应一个公钥，用公钥可以计算出私钥，用私钥可以计算出公钥，不过用私钥计算公钥的计算量比用公钥计算私钥的计算量小。
3、公钥本身也是一对，私钥本身也是一对的，公钥(n,e)，私钥(n,d)，其中n=pq，p和q是互不相等的质数，令t=(p-1)(q-1)，有p和q了就可以计算出n，e是自己选的，一般是用的65537（16进制10001），e需要和t互质，且1<e<t，然后公式ed%t=1，这里e和t是已知的，解出一个d就可以了。
4、知道怎么用p、q生成公钥、私钥了，那么现在就知道了破解RSA算法的方法了，把公钥中的n拿来分解质因数，就可以得到p、q，然后就可以计算出私钥了。

补充：公钥和私钥区分并不明显，公钥加密用私钥解密，私钥加密的用公钥解密。

下面是我用python写的代码，测试了些简单的，可以很快计算出，代码用的python 3

# lanyu19950316#gmail.com
import math
import multiprocessing
import os
import time


def factorization(q, public_key, start, end=0):
    if start % 2 == 0:
        start -= 1
    if end < start or end > public_key:
        end = public_key
    pid = str(os.getpid())
    if not os.path.exists("./log/"):
        os.mkdir("./log/")
    fp = open("./log/" + str(pid) + "_log.txt", "w")
    fp.write(str(time.time()) + "\n")
    fp.close()
    ranges = range(start, end, 2)
    j = 1
    for i in ranges:
        if public_key % i == 0:
            fp = open("./log/" + str(pid) + "_success.txt", "w")
            fp.write(str(time.time()) + "\n" + str(i))
            fp.close()
            q.put(["success", pid, i])
            break
        if j % 100 == 0:
            q.put(str(j) + ":" + str(i))
            fp = open("./log/" + str(pid) + "_log.txt", "a")
            fp.write(str(j) + ":" + str(i) + "\n")
            fp.close()
        j += 1
    fp = open("./log/" + str(pid) + "_log.txt", "a")
    fp.write(str(time.time()) + "\n")
    fp.close()
    q.put(["no_value", pid])


if __name__ == '__main__':
    try:
        public_key = int(str(input("Please input the public key (Hex):")), 16)
        if public_key % 2 == 0:
            print("Fuck!")
            input("Please input Enter, and close the application.")
            os._exit(-1)
        start = 3
        flag = str(input("The start value is " + str(start) + ", do you want to update?(Y/N)"))
        if flag == "Y":
            start = int(str(input("Please input the start value (Dec):")))
            flag = "N"
        end = int(math.sqrt(public_key)) + 1
        flag = input("The end value is " + str(end) + ", do you want to update?(Y/N)")
        if flag == "Y":
            end = int(str(input("Please input the end value (Dec):")))
    except:
        print("Your input is error!\n")
    print("The public key is " + str(public_key) + ", the start value is " + str(start) + ", the end value is " + str(
        end))

    q = multiprocessing.Queue()
    p = multiprocessing.Process(target=factorization, args=(q, public_key, start, end))
    p.start()

    while True:
        if not q.empty():
            value = q.get()
            if value[0] == "success":
                print("the factorization result is successful of pid " + str(value[1]))
                p.join()
                break
            if value[0] == "no_value":
                print((str(value[1]) + ": No Value"))
                break
            print(value)
    if value[0] == "success":
        p = value[2]
        q = public_key / value[2]
        print("p: " + str(p) + "\nq: " + str(q))
        t = (p - 1) * (q - 1)
        e = int(str(input("Please input the E (Hex,max is " + str(t) + "):")), 16)
        if e < 1 or e > t:
            print("Fuck!")
            input("Please input Enter, and close the application.")
            os._exit(-1)
        d = 0
        while ((e * d) % t) != 1:
            d += 1
        print("The private key is :" + str(d))
    input("Please input Enter, and close the application.")

推荐文章：
1、http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
2、http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
3、http://www.xfocus.net/releases/200503/a778.html
4、https://github.com/mitchellwrosen/rsa-crack-cuda