RSA

此时， 为公钥， 为私钥。

将消息转换为一个小于 的整数 （若消息过长则分块）。利用公钥 进行加密：

利用私钥 进行解密：

即证明 。
已知 ，则 ，即证：

情况一：
根据欧拉定理，，则：

情况二：
由于 且 为质数，此时 必然是 或 的倍数。
假设 ，由于 ，则 。
根据费马小定理，，则：
由此可得 ，两边同乘 ：
因此：
证明完毕。