RSA 含两道oj 上ctf题目

　　蓝桥杯一个填空题是rsa，python也没跑出来，回来又学了学rsa

这个讲的很清楚，证明啥的都很清晰，（证明中，m与n不互质时，ed两次带入，似乎没必要。）

链接：https://blog.csdn.net/u014044812/article/details/80866759

其中附加的辗转相除法，手算ax+by=1这种式子也会了。

举个百度的例子：

已知不定方程为

，利用辗转相除法求出一组整数解

解：求

的算式为：

所以

即

所以

是不定方程

的一组解。

蓝桥杯中的题意是已知n,d,c求m，e是未知。

加密：

m^e≡c(modn)

解密：

c^d≡m(modn)

好像用公式一套就出来了？？！

反正oj上第一个flag是得到了

import rsa,sys
from rsa import common
#(pub_key,pri_key) = rsa.newkeys(256)
#m = b'hello'
#crpto = rsa.encrypt(m,pub_key)
#print(len(crpto),common.byte_size(pub_key.n))
#print(pri_key)
#print(sys.argv[0])
pri_k = open('rsa_private_key.pem','r').read()
#print(pri_k,'1')
#print("--------------------------------------------------")
pri_key = rsa.PrivateKey.load_pkcs1(pri_k)
#print(pri_key)
c = open('flag.encrypt','rb').read()
m = rsa.decrypt(c,pri_key)
print(m)

第二个：

找到了一个知乎的解法，然后n,e,d,p,q都一样，解密失败。。。

我就是解密失败。。无语

然后找到了一个博客上面是自己实现解密方法，然后调用。

我又试了试，自己写了个。

因为rsa解密在得到了私钥后，其实就是带mod的快速幂

然后解成功了，但是解码显示没出来，python3 str没有decode方法。

于是想到了之前bytes2int()会不会有反向的，因为bytes有decode

然后发现真有，就很愉悦了。

转为bytes后decode就出来了。

至于如何得到的n,e,p,q,d参考我之前写的随笔：https://www.cnblogs.com/zhibin123/p/10590743.html

# -*- coding:utf-8 -*-
import gmpy2
import rsa
from rsa import transform,core

def fastMod(c,d,n):
    t = c
    res = 1
    while d:
        if d & 1:
            res = (res * t)%n
        t = ( t * t ) % n
        d>>=1
    return res

def decrytption(c,d,n):
    return fastMod(c,d,n)

q = 319576316814478949870590164193048041239
p = 275127860351348928173285174381581152299
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
e = 65537
d = int(gmpy2.invert(e,(p-1) * (q-1)))
pri_key = rsa.PrivateKey(n,e,d,p,q)

c = open('flag.encrypt','rb').read()
print(c)

c = transform.bytes2int(c)
print(c)
m = decrytption(c,d,n)
print(m,type(m))
flag = transform.int2bytes(m).decode()
print(flag)