基本認識基礎

歐拉函數(shù)：任意給定正整數(shù)，歐拉函數(shù)表示在小于等于的正整數(shù)中與構成互質關系的的個數(shù)。

關于歐拉函數(shù)的計算需要明白一點，任意一個大于1的正整數(shù)可以寫成一系列質數(shù)的積，及如果

,其中均為質數(shù)，那么，并且剩余部分切分以后也存在互質關系。因此根據(jù)歐拉函數(shù)的性質可以推倒出：

歐拉定理：如果兩個正整數(shù)互質，那么,即就是

RSA的加密過程，假設alice和bob要通信。

1、alice隨機選擇兩個不相等的大質數(shù)。

2、計算的乘積，即。

3、隨機選擇一個整數(shù)。

4、計算

5、將n，e封裝成公鑰,n，d封裝成私鑰。

知道n，e的情況下很難推倒出d，。

現(xiàn)在公鑰和私鑰已經(jīng)生成，假設bob要向alice發(fā)送的明文為m,那么Bob需要用alice的公鑰進行加密：

先在alice收到密文c需要進行解密：