文章目錄
- 一. 前言
- 二. 什么是非對稱加密演算法
- 三. 雙方交換資訊作業流程
- 四.密鑰生成數學原理
- 五.總結公鑰和私鑰生成步驟
- 六.解決大數運算
- 1.getCountAdd() 解決大數相加
- 2. getCountExp() 解決大數冪運算
- 3. getCountmod() 解決大數求余
- 七.舉個例子
- 八.完整代碼
- 1.隨機生成亂數
- 2. 判斷是否為質數
- 3. 最大公約數（輾轉相除演算法）
- 4.核心代碼
一. 前言
最近想模仿一下qq，做一個通信軟體，這是qq的登錄界面，當我們選擇記住密碼后，每次運行qq，就會顯示已保存的密碼，無論是否聯網，顯然這個密碼是保存在本地的，當點擊登錄，才會去和服務器上的資料庫進行比對，那么這個密碼顯然不能是明文的，一定是經過加密的密文，至于qq用的什么加密方法，這個就無從所知了，
通過百度，發現一個叫非對稱性加密演算法非常有意思，可以保證資料的安全，所以用了一些時間來學習這個演算法，這個演算法涉及了大數冪運算，所以還會學習如何設計撰寫能夠處理大數冪運算的函式，
看正題之前，說一些自己的感慨吧，
在一個專案中，實作功能的那一部分代碼很少，更多的是對這一功能的維護，如果用戶沒有按照預期的方式輸入資料，那么應該怎樣應對，例如下面是張老師給同學出的一道題，
實作一個簡單的輸入，要求用戶輸入兩個數，然后計算這兩個數和，我相信所有人都會寫出類似于下面的代碼：
cin>> a;
cin>> b;
cout<<a+b;
這三行代碼已經完成了老師的要求，但是真的完成了嗎？
這三行代碼就好像是剛出生boby，沒有自我健全，一旦照顧不周，就可以發生一些不可預料的后果，
如果我們輸入漢字，如果我們輸入一個數，如果，，，等等等等，我們的程式該如何應對，這就是代碼的健全性，
所以為了我們的代碼能夠很好的運行，請做出錯處理，
包括我們今天的主題，也是為了程式的健壯，話就說到這里，下面一起來看正文，
二. 什么是非對稱加密演算法
先說對稱加密，二狗想要傳遞一些甜言蜜語給他的老相好，但是在這個不安全的資訊時代，總有一些變態想偷窺他們的甜言蜜語，于是二狗就和他的老相好約定好，我們可以通過一個固定的規則，來對這些資訊進行加密或解密，例如給每個單詞加上某個數，例如I LOVE YOU通過加密變成J MPWF ZPV（實際上，對稱加密也沒有怎么簡單，這里只是簡單舉例），這樣一些無關人員就無法偷窺他們互相交流的資訊，同時，加密的資訊再也不用像以前一樣，躲躲藏藏，隨意公開，因為只有雙方才能解密，
但是經過時間的推移，二狗的老相好一時大意，將他們約定好的規則泄露了出去，于是他們戀愛的酸臭味又大白于天下，
對稱加密，需要對加密和解密使用相同密鑰的加密演算法，由于其速度快，對稱性加密通常在訊息發送方需要加密大量資料時使用，在安全性上，對稱加密，雙方使用的是相同的密鑰，也就是說有一方的密鑰泄露，整個資料都會被破解，
在現實面前，資料都被破解了，速度快，能加密大量資料，這些優點又有什么用呢，如何能將資訊安全的傳遞呢？這時，我們的主角非對稱RSA加密登場了，
RSA加密，使用兩個不同的密鑰e和d，將公鑰e公布于眾，包括老相好在內的其他人，都可以得到這個公鑰進行資訊加密，但只有二狗自己有一個私鑰用于解密，這樣，資訊的傳輸比之前的使用的對稱加密更加安全了，但是隨之而來，又出現了新問題，使用非對稱加密，雖然解密比較輕松，但是加密需要的時間比解密多的多，以至于非對稱加密只適用于少量資料加密，至于為什么慢，后面會填坑，雖然是實作了非對稱加密，但是，這并不是真正的RSA，直到一個被稱為迪菲赫爾曼密鑰交換的出現，讓RSA稱為了真正的RSA，
擴展：
1976年以前，所有的加密方法都是同一種模式：加密和解密使用同樣規則（簡稱"密鑰"），這被稱為"對稱加密演算法"，使用相同的密鑰，兩次連續的對等加密運算后會回復原始文字，也有很大的安全隱患，對稱加密中使用的主要演算法有：DES（Data Encryption Standard）、3DES（Triple DES）、AES（Advanced Encryption Standard）、Blowfish等，
1976年，兩位美國計算機學家Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構思，可以在不直接傳遞密鑰的情況下，完成解密，這就是迪菲赫爾曼密鑰交換
1977年，三位數學家Rivest、Shamir 和 Adleman 設計了一種演算法，可以實作非對稱加密，這種演算法用他們三個人的名字命名，叫做RSA演算法，從那時直到現在，RSA演算法一直是最廣為使用的"非對稱加密演算法"，毫不夸張地說，只要有計算機網路的地方，就有RSA演算法，這種演算法非常可靠，密鑰越長，它就越難破解，根據已經披露的文獻，目前被破解的最長RSA密鑰是232個十進制位，也就是768個二進制位，因此可以認為，1024位的RSA密鑰基本安全，2048位的密鑰極其安全，當然量子計算機除外，
非對稱加密中使用的主要演算法有：RSA、Elgamal、背包演算法、Rabin、D-H、ECC（橢圓曲線加密演算法）等，
更好的方法是用對稱加密加密大量資料，之后將對稱加密的密鑰進行非對稱加密，結合雙方優點和缺點，打造更完美的安全性，
三. 雙方交換資訊作業流程
| 步驟 | 描述 |
|---|---|
| 1 | 甲方和乙方發送資訊之前，兩方都要產生一對用于加密和解密的公鑰和私鑰， |
| 2 | 甲方的公鑰告訴乙方，私鑰保密，乙方的公鑰告訴甲方，私鑰保密， |
| 3 | 甲方要給乙方發訊息時，甲方用乙方提供的公鑰加密資訊，之后乙方用自己的私鑰解密， |
| 4 | 對應的，乙方要給甲方發資訊時，乙方用甲方提供的公鑰加密資訊，之后甲方用自己的私鑰解密， |
四.密鑰生成數學原理
知道了雙方交換資訊的流程，現在來看密鑰生成數學原理，
第一步是生成兩個質數，什么是質數？
素數是這樣的整數，它除了能表示為它自己和1的乘積以外，不能表示為任何其它兩個整數的乘積，例如 2，3，5，7，11這一類數，
第二步，求公共模值，也就是第一步生成的兩個數的乘積叫做模值，
第三步，求歐拉函式φ(n)，
任意一個正整數n，在小于等于n的正整數中有多少個數與n構成互質關系？計算這個值的方法叫做歐拉函式，
最后推算出來一個公式φ(n) = (p-1)(q-1)，p和q分別是第一步生成的兩個質數，
參考1https://www.zhihu.com/question/304030251
參考2https://blog.csdn.net/weixin_30399871/article/details/98251483
第四步，求e
e是一個與歐拉函式φ(n)互質的數，且e的取值必須在 1<e<φ(n)之間，
第五步，求模反元素d
什么是模反元素，如果兩個整數e和x互質，那么一定可以找到整數d，使得e*d-1被x整除，這里的x就是我們的歐拉函式，
d的取值也不唯一，
第六步，加密
m^e % n = c
第七步，解密
c^d % n = m
五.總結公鑰和私鑰生成步驟
| 步驟 | 說明 | 描述 | 備注 |
|---|---|---|---|
| 1 | 隨機找出兩個質數（素數） | p ，q | 一個大于1的正整數，如果除了1和它本身以外，不能被其他正整數整除，就叫素數 |
| 2 | 計算公共模數 | n = p*q | |
| 3 | 歐拉函式 | φ(n) = (p-1)(q-1) | |
| 4 | 計算公鑰e | 1<e<φ(n) | 取一個隨機整數e，且與φ(n)互為互質數 |
| 5 | 計算私鑰d | e*d%φ(n)=1 | d是模反元素，取值不唯一，滿足公式即可 |
| 6 | 公鑰加密 | m^e % n = c | m：明文 c：密文 |
| 7 | 私鑰解密 | c^d % n = m | c：密文 m：明文 |
現在來給大家舉一個例子：
假設 取質數q = 11，p=10
計算公共模數 n = 110
歐拉函式φ(n) = 90
隨機找一個與φ(n)互質的整數e = 7
求模反元素 d = 13（這個13也不唯一，符合條件即可）
假設有一個為" 43!1"50(3)+ ”的字串需要加密
’4‘的ascii碼為48+4=52，想要為字符’4’加密，就需要執行m^e % n = c，得到52^7%110=c，
這里有一個需要注意的點，需要加密的m必須小于n，這樣公式才能成立，
先來看下52^7等于多少
這是一個非常大的數，以至于，我必須使用long long的型別來保存該數，并得到剩下的加密字符，
好景不長，當我進行解密時，我得到了負數，我馬上意識到long long也不夠了，讓我們來看看這個數有多大，
加密后的字母D的ascii碼是68，也就意味著這個數是68^13，結果是：
這個數有24位，而longlong最大只能保存9后面再加18個0，超過了這個數就應該考慮精度問題了，
現在，你應該意識到一個問題，當程式計算步驟6和7的時候，盡管選用了很小的兩個素數，盡管是longlong型別，但這依舊無法保證資料不溢位（準確的說是基本上資料都會溢位），在java里面應該有對應的大數處理，但是對于所以C++，抱歉，需要我們自己實作，如何解決大數冪運算？，不論是int型別還是longlong型別，它總會有一個最大值，如果一個型別有最大值，那么就很難不溢位，有沒有什么資料型別是不溢位的呢？答案是字串，
六.解決大數運算
理論上來說，只要你的記憶體足夠，字串就不會被溢位，將一串數字用字串的思想表達有兩種方式：
一是使用int型別的陣列，int型別數值有限，但是int型別陣列長度無限，例如使用int a[]={1,2,3,4,5,6};來表示是十二萬三千四百五十六，
二是使用string型別來表示，例如 string a=“123456”; 同樣可以來表示十二萬三千四百五十六，
現在雖然你知道了這種規則，但是計算機不知道啊，你讓計算機計算a+a，得出來的結果是”123456123456“，計算機會把a+a當作字串相加操作，
所以我們要教計算機來識別字串數值并處理，在這之前，先要縷一縷思路，
所謂的冪運算，其本質也就是乘法，再經分解運算還可以得到加法，
所以我們現在來寫兩個函式，一個用于計算乘法并分解，另一個是將分解的內容進行相加，就得到了我們想要的答案，
1.getCountAdd() 解決大數相加
string getCountAdd(string a, string b)
{
string c = "";
int bit = -1; //判斷是否進位 -1為否，其他為進位數
int i = a.length()-1; //獲得a字串長度
int j = b.length()-1; //獲得b字串長度
//第一種情況 兩者都處理完
while (i != -1 && j != -1)
{
int t1 = a[i] - 48;
int t2 = b[j] - 48;
//不存在進位
if (bit == -1)
{
if (t1 + t2 >= 10)
{
int d = (t1 + t2) % 10;
c.insert(0, 1, d + 48);
bit = (t1 + t2) / 10;
}
else
{
c.insert(0, 1, t1 + t2 + 48);
}
}
//存在進位
else
{
if (t1 + t2 + bit >= 10)
{
int d = (t1 + t2 + bit) % 10;
c.insert(0, 1, d + 48);
bit = (t1 + t2 + bit) / 10;
}
else
{
c.insert(0, 1, t1 + t2 + bit + 48);
bit = -1;
}
}
i--;
j--;
}
//第二種情況 前者處理完
while (i == -1 && j != -1)
{
int t2 = b[j] - 48;
if (bit == -1)
{
c.insert(0, 1, b[j]);
}
else
{
if (t2 + bit >= 10)
{
int d = (t2 + bit) % 10;
c.insert(0, 1, d + 48);
bit = (t2 + bit) / 10;
}
else
{
c.insert(0, 1, t2 + bit + 48);
bit = - 1;
}
}
j--;
}
//第三種情況 后者處理完
while (i != -1 && j == -1)
{
int t1 = a[i] - 48;
if (bit == -1)
{
c.insert(0, 1, a[i]);
}
else
{
if (t1 + bit >= 10)
{
int d = (t1 + bit) % 10;
c.insert(0, 1, d + 48);
bit = (t1 + bit) / 10;
}
else
{
c.insert(0, 1, t1 + bit + 48);
bit = -1;
}
}
i--;
}
//最后再判斷是否存在進位
if (bit != -1)
{
c.insert(0, 1, bit + 48);
}
bit = -1;
return c;
}
執行效果
2. getCountExp() 解決大數冪運算
string getCountExp(int a, int b)
{
//計算a^b
string a1 = to_string(a);
//string b1 = to_string(b);
int i = a1.length()-1;//a的最后下角標
//int j = b1.length()-1;//b的最后下角標
//m位數*n位數長度不會超過m+n位
string temp = a1; //temp一直變化
string temp_2 = "0";
int bitcount = 0; //判斷當前位數
int bit = -1;//判斷是否存在進位
string * arr = new string[a1.length()];//保存每次計算的數
int arr_i = 0;
for (int x = 1; x < b; x++)//幾次方就回圈幾次
{
while (i != -1)//乘數的位數
{
//temp * a1
int t1 = a1[i] - 48;
int j = temp.length() - 1;//temp的最后下角標
for (int z = 0; z < bitcount; z++)
{
arr[arr_i].insert(0, 1, '0');
}
while (j != -1)//temp的位數
{
int t2 = temp[j] - 48;
if (bit == -1)//判斷是否有進位
{
if (t1*t2 >= 10)
{
int d = (t1*t2) % 10;
arr[arr_i].insert(0, 1, d + 48);
int d_2 = (t1*t2) / 10;
bit = d_2;
}
else
{
int d = t1*t2;
arr[arr_i].insert(0, 1, d + 48);
}
}
else
{
if ((t1*t2)+bit >= 10)
{
int d = ((t1*t2) + bit) % 10;
arr[arr_i].insert(0, 1, d + 48);
int d_2 = ((t1*t2) + bit) / 10;
bit = d_2;
}
else
{
int d = (t1*t2) + bit;
arr[arr_i].insert(0, 1, d + 48);
bit = -1;
}
}
j--;
}
if (bit != -1)
{
arr[arr_i].insert(0, 1, bit + 48);
bit = -1;
}
temp_2 = getCountAdd(temp_2, arr[arr_i]);
bitcount++;
arr_i++;
i--;
}
bitcount = 0;
temp = temp_2;
temp_2 = "0";
for (int z = 0; z < arr_i; z++)
{
arr[z] = "";
}
arr_i = 0;
i = a1.length() - 1;
}
return temp;
}
執行效果
3. getCountmod() 解決大數求余
最高位開始，有余數就乘以10再加上低位的數繼續求余，直到字串遍歷完畢，
int getCountMod(string a, int b)
{
int bit = -1; //判斷是否需要進位
//例如4255%5
int i = 0;
while (i < a.length())
{
int t1 = a[i] - 48;
if (bit == -1)
{
if (t1%b > 0)
{
bit = t1%b;
}
}
else
{
if (((bit * 10) + t1) % b>0)
{
bit = ((bit * 10) + t1) % b;
}
}
i++;
}
if (bit != -1)
{
return bit;
}
else
{
return 0;
}
return 0;
}
運行效果：
七.舉個例子
寫了怎么多了，現在來舉個例子，取q = 19， p = 17， n = 19*17 = 323， φ(n) = 288， e = 5， d = 173，
我本來是想使用字符型別來保存加密后的字符的，但是一個字符最多255位，圖中經過加密的字符在選取的數極小的情況下就可能會超過255，當選取的素數極大時，必然是直接截斷，應該這個問題，還耽誤了很長時間，所以圖中加密字符的顯示是改用整形變數來保存的，
八.完整代碼
1.隨機生成亂數
long getRandomPrimeNum()
{
long num = 0;
while (true)
{
num = abs(rand()); //隨機生成0 - RAND_MAX;
if (isPrimeNum(num))
return num;
}
return 0;
}
2. 判斷是否為質數
bool isPrimeNum(long long num)
{
if (num < 2)return false;
for (int i = 2; i < num / 2; i++)
{
if (num % i == 0)return false;
}
return true;
}
3. 最大公約數（輾轉相除演算法）
long long gcd(long long a, long long b)
{
if (b == 0)return a;
else return gcd(b, a%b);
return 0;
}
如果回傳值為1，則代表兩個數互質
4.核心代碼
int main()
{
fstream file;
ifstream in("C:\\Users\\fdog\\Desktop\\mingwen.txt", ios::in);
istreambuf_iterator<char> beg(in), end;
string strdata(beg, end);
in.close();
cout <<"讀取的資料為："<< strdata << endl;
string str = strdata;
srand((unsigned)time_t(NULL));
long long q = getRandomPrimeNum();
long long p = getRandomPrimeNum();
cout << "取隨機素數p = " << p << " q = " << q;
long long e = 0;
long long n = q*p;
cout << " n：" << n ;
long long fi = (q - 1)*(p - 1);
cout << " 歐拉函式：" << fi ;
long long * count = new long long[str.length()];
srand((unsigned)time_t(NULL));
while (1)
{
if (1 < e&&e < fi&& Prime::isPrimeNum(e) && gec(e,fi) ==1)
{
break;
}
e++;
}
cout << " e：" << e;
long long d =0;
while (1)
{
if ((e*d) % fi == 1)
{
break;
}
d++;
}
cout << " d: " << d << endl;
string strc="";
for (int i = 0; i < str.length(); i++)
{
long long m = str[i]; //明文
string str = getCountExp(m, e);
long long c = getCountMod(str, n);
cout << "當前需加密字符：" << m << " 加密之后 加密字符：" << c << endl;
count[i] = c;
strc.append(1, char(c));
}
string strm="";
for (int i = 0; i < strc.length(); i++)
{
long long c = count[i]; //密文
string str = getCountExp(c, d);
long long m = getCountMod(str, n);
strm.append(1, char(m));
cout <<"解密之后的字符：" << m << endl;
}
cout << "明文：" << strm << endl;
return 0;
}
創作不易，快來一鍵三連！
歡迎加入我的官方粉絲群：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272483.html
標籤：其他