rsa、gmpy2、python

简单 rsa 题&gmpy2 库

今天刚好看到一道 rsa 题,就来了解一下

rsa 是什么

RSA 算法,是一种由已知加密密钥推导出解密密钥在计算上是不可行的密码体制,是目前最优秀的公钥方案之一

rsa 如何计算

n = p * q

e大于p和q,且与p q互质

ed = 1( mod phi(n) )

phi (n) = (p-1) * (q-1)

计算rsa所需的公式

python 脚本编写

计算 rsa 要使用 gmpy2 库
下载:https://pypi.org/project/gmpy2/#files

pip install gmpy2

gmpy2 计算 mod 需要 invert:

import gmpy2

d = gmpy2.invert(e,n)
#计算de=1 mod n中的d

已知 epq 求 d

import gmpy2
import rsa

e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463

phin = (q-1)*(p-1)
d = gmpy2.invert(e, phin)

已知 edn 求 pq

https://err0rzz.github.io/2017/11/14/CTF%E4%B8%ADRSA%E5%A5%97%E8%B7%AF/

import random

def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a

def getpq(n,e,d):
    p = 1
    q = 1
    while p==1 and q==1:
        k = d * e - 1
        g = random.randint ( 0 , n )
        while p==1 and q==1 and k % 2 == 0:
            k /= 2
            y = pow(g,k,n)
            if y!=1 and gcd(y-1,n)>1:
                p = gcd(y-1,n)
                q = n/p
    return p,q

def main():

    n = 0xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab
    e =  0x10001
    d =  0x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881
    p,q = getpq(n,e,d)
    print "p: "+hex(p)
    print "q: "+hex(q)

if __name__ == '__main__':
    main()

gmpy2 库的其他方法

gmpy2.mpz(n) #初始化一个大整数

gmpy2.mpfr(x) # 初始化一个高精度浮点数x

d = gmpy2.invert(e,n) # 求逆元,de = 1 mod n

C = gmpy2.powmod(M,e,n) # 幂取模,结果是 C =
(M^e) mod n

gmpy2.is_prime(n) #素性检测

gmpy2.gcd(a,b) #欧几里得算法,最大公约数

gmpy2.gcdext(a,b) #扩展欧几里得算法

gmpy2.iroot(x,n) #x开n次根

推荐相关编辑器

Anaconda3
不需要提前安装库,省去许多麻烦(对,就是安个库都能把程序安坏


kamuXiY