最近研究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,然后就可以计算出私钥了。
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
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
No comments:
Post a Comment