CTF之Crypto学习笔记(一)_ctf q n

原理

加密

随便找出两个 整数 q 和 p （q，p互素，即：公因数只有1）
求出n = q * p
φ(n)= （p-1）*（q-1） 欧拉公式
公钥 e ： 随机取，要求 ：e 和 φ(n) 互素（公因数只有 1）； 1< e < φ(n)）；
私钥 d ： ed ≡ 1 （mod φ(n) ） （ed 除以 φ(n) 的 余数 为 1 ）

RSA加密其实是对明文的E次方后除以N后求余数的过程。只要知道E和N任何人都可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说E和N的组合就是公钥，用(E,N)来表示公钥。

E：加密指数

解密

前面说到，RSA的加密过程是对明文的E次方后除以N后求余数的过程

那么，RSA解密过程则是密文进行D次方后除以N的余数，即明文
我们知道D和N就能进行解密密文了，所以D和N的组合就是私钥
D：解密指数

RSA的加密方式和解密方式是一样的，变化的是加密指数与解密指数的不同

加密是求 E次方的mod N
解密是求 D次方的mod N

解密过程详细解读

做一道曾经望而生畏的简单题

题目：

p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551
e = 65533
n = p*q
c = 27565231154623519221597938803435789010285480123476977081867877272451638645710
1
2
3
4
5

根据题目给出的信息，已知加密指数e,密文c，模n,以及p和q
由此编写解密脚本

import gmpy2
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex


p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551

e = 65533
n = p*q

c = 27565231154623519221597938803435789010285480123476977081867877272451638645710
phi = (p-1)*(q-1)					#求φ(n)，φ(n)=(p-1)(q-1)
d = gmpy2.invert(e,phi)				#求e对于模n的逆元，即解密指数d
m = pow(c,d,n)						#m=c^d mod n，m为10进制格式
print(long_to_bytes(m))				#m的字符串格式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

flag{B4by_Rs4}

参考链接：
https://blog.csdn.net/vhkjhwbs/article/details/101160822

https://blog.csdn.net/vanarrow/article/details/107846987?utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~default-1.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~default-1.no_search_link

【大夜定灯，小梦思乡，被莺唤起，一枕黄粱。】