rsa算法简介

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

rsa算法原理

欧拉函数φ(n)

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

欧拉定理

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

费马小定理

模运算

模运算与基本四则运算有些相似，但是除法除外。其规则如下：

推导过程

将式1带入式2 得 m = (m ^ e % N ) ^ d % N

需要证明：m == ( m ^ e % N ) ^ d % N

将 e * d ≡ 1 (mod φ(N)) 即 e * d = K * φ(N) + 1，K为任意正整数，代入得：