BUUOJ rsa

0x01 题目

image-20220313201840503

0x02 RSA非对称加密算法

公钥与私钥的产生 ：

  1. 随机选择两个不同大质数 p 和 q，计算 N=p×q
  2. 根据欧拉函数，求得 φ(N)=φ(p)φ(q)=(p−1)(q−1)
  3. 选择一个小于 φ(N) 的整数 e，使 e 和 φ(N) 互质。并求得 e 关于 φ(N) 的模反元素，命名为 d，有 ed≡1(modφ(N))
  4. 将 p 和 q的记录销毁

此时，(N,e)是公钥，(N,d) 是私钥。

0x0201 消息加密

首先需要将消息 以一个双方约定好的格式转化为一个小于 N，且与 N 互质的整数 m。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

m^e≡c(modN)

0x0202 消息解密

利用密钥 d 进行解密。

c^d≡m(modN)

0x03 解密脚本：

1
2
3
4
5
6
7
8
9
Python 3.10.2 (main, Feb  2 2022, 05:51:25) [Clang 13.0.0 (clang-1300.0.29.3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from gmpy2 import *
>>> p = 473398607161
>>> q = 4511491
>>> e = 17
>>> d = gmpy2.invert(e,(p-1)*(q-1))
>>> print(d)
125631357777427553