Swift5加密解密RSA算法適配

https://github.com/StevenGardnerGMJ/GMJRSASignRSAEncryptor

RSA算法的過(guò)程

RSA算法用到的數(shù)學(xué)知識(shí)特別多透揣，所以在中間介紹這個(gè)算法生成私鑰和公鑰的過(guò)程中會(huì)穿插一些數(shù)學(xué)知識(shí)拣宰。生成步驟如下：

1.尋找兩個(gè)不相同的質(zhì)數(shù)

隨意選擇兩個(gè)大的質(zhì)數(shù)p和q凑保，p不等于q晒衩，計(jì)算N=p*q;

什么是質(zhì)數(shù)?我想可能會(huì)有一部分人已經(jīng)忘記了，定義如下：

除了1和該數(shù)自身外山橄，無(wú)法被其他自然數(shù)整除的數(shù)（也可定義為只有1該數(shù)本身兩個(gè)正因數(shù)]的數(shù)）垮媒。

比如2，3航棱，5睡雇，7這些都是質(zhì)數(shù)，9就不是了饮醇，因?yàn)?*3=9了

2.?根據(jù)歐拉函數(shù)獲取r

r = φ(N) = φ(p)φ(q) = (p-1)(q-1)入桂。

這里的數(shù)學(xué)概念就是什么是歐拉函數(shù)了，什么是歐拉函數(shù)呢驳阎？

歐拉函數(shù)的定義：

歐拉函數(shù)?φ(n)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。

互質(zhì)的定義：

如果兩個(gè)或兩個(gè)以上的整數(shù)的最大公約數(shù)是 1，則稱它們?yōu)榛ベ|(zhì)

例如：φ(8) = 4呵晚，因?yàn)?,3,5,7均和8互質(zhì)蜘腌。

推導(dǎo)歐拉函數(shù):

（1）如果n = 1,?φ(1) = 1；(小于等于1的正整數(shù)中唯一和1互質(zhì)的數(shù)就是1本身)饵隙；

（2）如果n為質(zhì)數(shù)撮珠，φ(n) = n – 1；因?yàn)橘|(zhì)數(shù)和每一個(gè)比它小的數(shù)字都互質(zhì)金矛。比如5芯急，比它小的正整數(shù)1,2,3,4都和他互質(zhì)；

（3）如果n是a的k次冪驶俊，則?φ(n) = ?φ(a^k) ?= a^k – a^(k-1) = (a-1)a^(k-1)娶耍；

（4）若m,n互質(zhì)，則φ(mn) = φ(m)φ(n)

證明：設(shè)A,?B,?C是跟m,?n,?mn互質(zhì)的數(shù)的集饼酿，據(jù)中國(guó)剩余定理(經(jīng)抽啪疲看數(shù)學(xué)典故的童鞋應(yīng)該了解，剩余定理又叫韓信點(diǎn)兵故俐，也叫孫子定理)想鹰，A*B和C可建立雙射一一對(duì)應(yīng))的關(guān)系。（或者也可以從初等代數(shù)角度給出歐拉函數(shù)積性的簡(jiǎn)單證明） 因此的φ(n)值使用算術(shù)基本定理便知辑舷。（來(lái)自維基百科）

3.?選擇一個(gè)小于r并與r互質(zhì)的整數(shù)e

選擇一個(gè)小于r并與r互質(zhì)的整數(shù)e何缓，求得e關(guān)于r的模反元素筐乳，命名為d（ed = 1(mod r)模反元素存在歌殃，當(dāng)且僅當(dāng)e與r互質(zhì)），e我們通常取65537氓皱。

模反元素：

如果兩個(gè)正整數(shù)a和n互質(zhì)波材，那么一定可以找到整數(shù)b身隐，使得 ab-1 被n整除贾铝，或者說(shuō)ab被n除的余數(shù)是1。

比如3和5互質(zhì)玖绿，3關(guān)于5的模反元素就可能是2斑匪，因?yàn)?*2-1=5可以被5整除蚀瘸。所以很明顯模反元素不止一個(gè)，2加減5的整數(shù)倍都是3關(guān)于5的模反元素{…-3, 2,7,12…}??放在公式里就是3*2 = 1 (mod 5)

上面所提到的歐拉函數(shù)用處實(shí)際上在于歐拉定理：

歐拉定理：

如果兩個(gè)正整數(shù)a和n互質(zhì)贪惹，則n的歐拉函數(shù)?φ(n)?可以讓下面的等式成立：

a^φ(n) = 1(mod n)

由此可得：a的φ(n – 1)次方肯定是a關(guān)于n的模反元素馍乙。

歐拉定理就可以用來(lái)證明模反元素必然存在丝格。

由模反元素的定義和歐拉定理我們知道显蝌，a的φ(n)次方減去1曼尊，可以被n整除骆撇。比如父叙，3和5互質(zhì)趾唱，而5的歐拉函數(shù)φ(5)等于4甜癞，所以3的4次方(81)減去1悠咱，可以被5整除（80/5=16）。

小費(fèi)馬定理：

假設(shè)正整數(shù)a與質(zhì)數(shù)p互質(zhì)柒室，因?yàn)橘|(zhì)數(shù)p的φ(p)等于p-1，則歐拉定理可以寫成

a^(p-1) = 1 (mod p)

這其實(shí)是歐拉定理的一個(gè)特例纺讲。

4.銷毀p和q

此時(shí)我們的(N , e)是公鑰囤屹，(N, d)為私鑰乡括，愛(ài)麗絲會(huì)把公鑰(N, e)傳給鮑勃诲泌，然后將(N, d)自己藏起來(lái)敷扫。一對(duì)公鑰和私鑰就產(chǎn)生了葵第，然后具體的使用方法呢卒密？請(qǐng)看：SSL協(xié)議之?dāng)?shù)據(jù)加密過(guò)程詳解哮奇。

RSA算法的安全性

我們知道像RSA這種非對(duì)稱加密算法很安全，那么到底為啥子安全呢而芥？我們來(lái)看看上面這幾個(gè)過(guò)程產(chǎn)生的幾個(gè)數(shù)字：

p,q：我們隨機(jī)挑選的兩個(gè)大質(zhì)數(shù)棍丐；

N：是由兩個(gè)大質(zhì)數(shù)p和q相乘得到的歌逢。N = p * q砰苍；

r：由歐拉函數(shù)得到的N的值，r = φ(N) = φ(p)φ(q) = (p-1)(q-1)阱高。

e：隨機(jī)選擇和和r互質(zhì)的數(shù)字赚导，實(shí)際中通常選擇65537；

d： d是以歐拉定理為基礎(chǔ)求得的e關(guān)于r的模反元素赤惊，ed = 1 (mod r)吼旧；

N和e我們都會(huì)公開(kāi)使用圈暗，最為重要的就是私鑰中的d，d一旦泄露员串，加密也就失去了意義。那么得到d的過(guò)程是如何的呢？如下:

1.比如知道e和r海铆，因?yàn)閐是e關(guān)于r的模反元素；r是φ(N) 的值

2. 而φ(N)=(p-1)(q-1)，所以知道p和q我們就能得到d;

3. N = pq板乙，從公開(kāi)的數(shù)據(jù)中我們只知道N和e，所以問(wèn)題的關(guān)鍵就是對(duì)N做因式分解能不能得出p和q

募逞、

所以得出了在上篇博客說(shuō)到的結(jié)論蛋铆，非對(duì)稱加密的原理：

將a和b相乘得出乘積c很容易，但要是想要通過(guò)乘積c推導(dǎo)出a和b極難放接。即對(duì)一個(gè)大數(shù)進(jìn)行因式分解極難刺啦。

目前公開(kāi)破譯的位數(shù)是768位，實(shí)際使用一般是1024位或是2048位苟蹈，所以理論上特別的安全捧韵。

RSA算法的核心就是歐拉定理，根據(jù)它我們才能得到私鑰汉操，從而保證整個(gè)通信的安全