一、简单加解密原理

（1）加密

图中的E是公钥（E和 φ(N)互为质数），
N是公共模数（质数 P 、Q相乘得到N），
MOD就是模运算

（2）解密

图中的D是私钥（私钥由这个公式计算得出E * D % φ(N) = 1），
N是公共模数（质数 P 、Q相乘得到N），
MOD就是模运算，
φ(N)是欧拉函数（由这个公式计算得出φ(N) = (P-1)(Q-1)）。

二、例题及解题脚本--RE49-signin

此题中：
密文：ad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
大整数N：103461035900816914121390101299049044413950405173712170434161686539878160984549
公钥E：65537

1.先通过N算出P和Q：

方法一、通过大素数分解网站

http://factordb.com/index.php

方法二、用离线暴力破解工具yafu(使用教程见工具目录下README)

进入文件目录后打开cmd，输入yafu-x64 factor()，括号内填要分解的大素数
得到
P=282164587459512124844245113950593348271
Q=366669102002966856876605669837014229419

2.编写python脚本算出私钥d，解出明文

脚本如下：

import gmpy2

p = 366669102002966856876605669837014229419
q = 282164587459512124844245113950593348271
N = 103461035900816914121390101299049044413950405173712170434161686539878160984549
c = 0xad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
e = 65537

d = gmpy2.invert(e,(p-1)*(q-1))
m = gmpy2.powmod(c,d,p*q)

print(bytes.fromhex(hex(m)[2:]).decode('utf-8'))

需要使用到模块gmpy2
安装教程
只适用于3.10及以下的python版本

3.gmpy2 python 扩展库的用法笔记

（1）初始化一个高精度的数据类型

a. a=gmpy2.mpz(x) 可以为变量a赋予一个高精度的大整数（长度可达50位）
b. a=gmpy2.mpq(x) 可以为变量a初始化一个高精度的分数
c. a=gmpy2.mpfr(x) 可以为a初始化一个高精度的浮点数
d. a=gmpy2.mpc(x) 可以为a初始化一个高精度的复数

（2）其它的常用语法

a. 模幂运算：gmpy2.powmod(a,n,p)   #对于给定的整数p,n,a,计算aⁿ mod p
b. 对x开n次方根：gmpy2.iroot（x，n）
c. 欧几里得算法：gmpy2.gcd（a，b）#求得a，b的最大公约数
               gmpy2.lcm（a，b）#求得最小公倍数
d. 扩展欧几里得：gmpy2.gcdext（e1，e2）#求式子e1*x+e2*y=gcd(e1,e2)。在RSA加密算法中利用该公式来求e的逆元d，由于实际上公钥e的选取需要保证gcd（e，ψ(n)）=1，所以在这种情况下式子的右边就是1，且通常用下面这个公式来求逆元。
e. 模逆运算：gmpy2.invert（a，c）#对a，求b，使得a*b=1（mod c）
f. 检测
    i. 素数检测：gmpy2.is_prime（）
    ii. 奇数检测：gmpy2.is_even（）
    iii. 偶数检测：gmpy2.is_odd（）