CTF-RSA_算法简介及原理_rsa ctf

RSA简介及原理

rsa算法简介

RSA是公钥密码体制，是一种使用不同的加密密钥与解密密钥

选择两个大素数p和q，计算出模数N = p * q

计算φ(N) = (p−1) * (q−1) 即N的欧拉函数，然后选择一个e (1<e<φ(N))，且e和φN互素

取e的模反数为d(逆元)，计算方法: e * d ≡ 1 (mod φ(N))

对明文m进行加密：c=m^e%N
c = pow(m, e, N)，得到的c即为密文

对密文c进行解密:m=c^d%N
m = pow(c, d, N)，得到的m即为明文
1
2
3
4
5
6
7
8
9
10
11

p 和 q ：大整数N的两个因子（factor）

N：大整数N，我们称之为模数（modulus）

e 和 d：互为模反数的两个指数（exponent）

c 和 m：分别是密文和明文，这里一般指的是一个十进制的数
1
2
3
4
5
6
7

（N，e）：公钥

（N，d）：私钥
1
2
3

rsa算法原理

欧拉函数φ(n)

欧拉函数φ(n)的定义是小于n的自然数中与n互质的数的个数

欧拉定理

若n,a为正整数，且n,a互质，则:a^φ(n)≡1 mod n

费马小定理

若p 是质数,a 与p 互质，
a p ≡ a m o d    p a^p ≡a \mod p