加密原理詳解:對稱式加密 VS 非對稱式加密

互聯(lián)網(wǎng)科普站
密鑰是作用于加密時的一串密碼,通過密鑰進行信息加密,傳輸,到達接收者和監(jiān)聽者,由于接收者也有密鑰,所以接收者可以根據(jù)密鑰進行解密。從而防止通訊信息泄露。

一、前言

在了解加密原理前,我們來看看這樣一個故事。

小紅和小明是情侶,一天,小紅給小明發(fā)短信說:“親愛的,我銀行卡上沒有錢了,你給我轉1萬塊吧。”有過上當受騙經(jīng)歷的人都知道這有可能是小偷偷了小紅手提包,然后拿手機發(fā)的短信。不過我們小明學過加密原理,于是他回復說:“你直接拿我的銀行卡刷吧,密碼加上我們第一次約會的日期就是663156。”很明顯,只有小明和小紅知道他們第一次約會是什么時候,假設是2008年4月1號,那么小紅就可以根據(jù)計算663156-200841=462315得到銀行卡密碼,就可以消費了。

這就是加密的本質,將信息與密鑰相加得到加密后的信息。只有知道密鑰的人才能解密。

二、什么是秘鑰

既然加密需要密鑰,那么密鑰是什么呢?

密鑰是作用于加密時的一串密碼,通過密鑰進行信息加密,傳輸,到達接收者和監(jiān)聽者,由于接收者也有密鑰,所以接收者可以根據(jù)密鑰進行解密。從而防止通訊信息泄露。

三、什么是對稱加密

前言講的故事就是一個對稱式加密,小明和小紅都知道第一次約會的日期。所以傳統(tǒng)的對稱式加密需要通訊雙方都保存同一份密鑰,通過這份密鑰進行加密和解密。所以非對稱加密也稱為單密鑰加密。

對稱加密的優(yōu)勢在于加解密速度快,但是安全性較低,密鑰一旦泄露,所有的加密信息都會被破解。同時密鑰的傳輸和保密也成為難題。為了解決密鑰傳輸?shù)膯栴},出現(xiàn)通過密鑰交換建立共享密鑰的技術。具體如何建立共享密鑰呢?我們往下看。

3.1建立共享密匙

在小明、小紅和小偷的三人世界中,由于小明是學過加密原理的,知道迪菲–赫爾曼密鑰交換(Diffie-Hellman Key Exchange),所以他知道如何建立共享密鑰。

3.1.1顏料混合把戲:

接下來我們看看如何通過顏料混合把戲建立共享密鑰吧。

假設在房間中有小明、小紅和小偷三個人,每個人各自擁有相同顏色的顏料。在房間的正中間也有這些顏料。接下來,小明要和小紅建立共享密鑰了。此時,小明對大家說:“我要用藍色。”然后小明從自己的顏料里選擇了黃色,這個黃色就是小明的私鑰,小紅和小偷都不知道。小明將自己的私鑰黃色與公鑰藍色混合后,得到了一種不能分解的顏色,我們就叫“小明-藍色”吧(雖然大家都知道黃+藍變綠,但是這里我們?yōu)榱酥朗钦l的混合色,還是以名字加公鑰顏色來稱呼),然后小明將“小明-藍色”公布了出來。同樣,小紅聽到了小明說用藍色后,也選擇了自己的私鑰紅色與公鑰藍色混合,得到了“小紅-藍色”并公布了出來。

此時,房間中小明、小紅、小偷三人都知道了幾個信息。

1.他們都用了藍色

2.小明公布了“小明-藍色”(小紅和小偷不知道是什么顏料與藍色的混合)

3.小紅公布了“小紅-藍色”(小紅和小偷不知道是什么顏料與藍色的混合)

接下來,見證奇跡的時刻到了,小明拿到“小紅-藍色”與自己的私鑰“黃色”混合,得到“小紅-藍色-小明”的新顏料。同樣的,小紅拿到“小明-藍色”與自己的私鑰“紅色”混合,得到“小明-藍色-小紅”。大家發(fā)現(xiàn)了嗎?“小紅-藍色-小明”和“小明-藍色-小紅”是一模一樣的顏色。而小偷不知道小明和小紅的私鑰顏色,無法混合出與他們相同的顏色。

至此,共享密鑰建立起來了。在了解了共享密鑰的建立過程后,我們將告別實體顏料,采用數(shù)字的方式來建立共享密鑰。

注:大家可能想到了,小偷可以根據(jù)自己的顏料與公鑰“藍色”混合,嘗試得出“小明-藍色”和“小紅-藍色”。這樣的方法稱之為窮舉法,也就是嘗試所有的可能性,進行信息破解,所以加密算法在理論上都是可以通過窮舉法破解的,只不過實際上,超級計算機都需要計算萬億年才能窮舉出所有可能性。

3.1.2乘法把戲:

首先,我們假設乘法如同顏料混合一樣,是不能分解的,看看如何用乘法與數(shù)字建立共享密鑰。

小明公開了一個數(shù)字5,然后小明選擇了一個私人數(shù)字4,然后利用乘法將兩者混合起來,得到“小明-5”(20),接下來小紅也選擇了一個私人數(shù)字7得到“小紅-5”(35),小明拿到35*4=140,小紅拿到20*7=140。共享密鑰建立完成。

大家也發(fā)現(xiàn)了,小偷知道20,35,5這三個數(shù)字后,用除法就能算出小明和小紅的私鑰。所以,接下來我們將了解實際使用中的如何使用乘法把戲來防止私鑰被計算出來的。

3.2迪菲–赫爾曼密鑰交換算法

我們都知道冪運算,但是要讓計算機計算就比較難了。所以,我們會用冪運算作為建立共享密鑰的乘法把戲。同時,我們還要了解鐘算的原理,這里的鐘可以理解成我們經(jīng)??吹降臅r鐘,我們常見的時鐘最大是12,如果當前是10點,過了4個小時后,就變成了下午2點。也就是(10+4)mod12=2。了解了鐘算和冪運算后,就開始進入正題吧。

還是小明、小紅和小偷的房間,小明聲明了鐘為11,冪運算的底為2,接下來小明和小紅分別選擇了自己的私鑰4和7。

第一步,小明混合自己的“小明-11,2”得到,小紅混合自己的“小紅-11,2”得到。

第二步,小明拿到“小紅-11,2”(7)進行計算,小紅拿到“小明-11,2”(5)進行計算。

大家注意到了嗎,小明和小紅建立了共享密鑰3,而小偷無法根據(jù)已知的11,2,5,7這幾個數(shù)字計算出密鑰或小明小紅的私鑰。有了共享密鑰后,小明和小紅就可以安全進行加密傳輸了。

2345截圖20211028093243.png

3.3 AES對稱加密過程

AES的全稱是Advanced Encryption Standard,是最流行的對稱加密算法,其加解密速度快。AES支持128位,192位,256位三種長度的密鑰,密鑰越長安全性越高。AES加密時會把明文切分成許多小塊的明文,然后對每塊明文單獨加密,將加密后的密文傳送出去,接收方再將密文切塊解密,得到明文。

如下圖所示:

2345截圖20211028093243.png

上一步中小明和小紅已經(jīng)協(xié)商好了密鑰3。接下來就可以通過對稱加密進行通信了。

在小明、小紅和小偷的房間中,小明想把密碼“462315”告訴小紅,于是:

第一步:將密碼按照一位的長度進行切分(實際中通常按128位進行切分);就變成了“4”“6”“2”“3”“1”“5”;

第二步:對每塊明文通過密鑰3進行加密,結果就是“795648”,然后小明告訴小紅和小偷:“我的密碼是795648”;

第三步:小紅拿到密文后,對密文進行切塊,對每塊通過密鑰3進行解密,就得到了正確的密碼“462315”,而小偷由于不知道密鑰,就無法解密出正確的信息。

四、什么是非對稱加密

在對稱加密中,加密和解密使用的是同一份密鑰。所以,在非對稱加密中,加密和解密使用的是不同的密鑰。非對稱加密中的密鑰分為公鑰和私鑰。公鑰顧名思義就是公開的,任何人都可以通過公鑰進行信息加密,但是只有用戶私鑰的人才能完成信息解密。非對稱加密帶來了一個好處,避免了對稱式加密需要傳輸和保存同一份密鑰的痛苦。

現(xiàn)在最流行的非對稱加密算法就是RSA加密算法,具體是怎么做的呢,我們繼續(xù)往下看。

4.1 RSA加密過程

維基百科是這么解釋的:RSA加密算法是一種非對稱加密算法,在公開密鑰加密和電子商業(yè)中被廣泛使用。RSA是由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

前面我們講了如何通過鐘算和冪函數(shù)建立不可逆(計算機可以通過窮舉法計算出私鑰,實際場景中就算是超級計算機也要計算幾萬億年之久)的共享密鑰。由于小紅是小明的女朋友,小明天天在小紅面前給她講RSA加密算法的原理,所以小紅也知道怎么得出自己的公鑰和私鑰。接下來我們一起跟著小紅的腳步,看看RSA加密的公鑰和私鑰是怎么計算出來的。

第一步:小紅選擇了兩個很大的質數(shù)p和q,這里為了便于計算,選擇2和11;

第二步:計算p和q的乘積n=p*q=2*11=22;

第三部:計算n的歐拉函數(shù)φ(n)=(p-1)*(q-1)=10;

第四步:選擇一個小于φ(n)且與φ(n)互質的整數(shù)e,,這里選擇e=7;

第五步:計算e對于φ(n)的模反元素(ed modeφ(n)=1)d,d=3

到這里小紅就得到了他自己的公鑰(n,e)和私鑰(n,d)。其中n就是鐘大小,e和d就是冪函數(shù)的冪。接下來就通過計算出來的公鑰和私鑰進行數(shù)據(jù)的加解密。

還是小明、小紅和小偷三個人,小紅對大家說,我的公鑰是(22,7),小明知道了小紅的公鑰后,想講自己的信息“14”告訴小紅,于是就用小紅公開的公鑰進行加密。

具體步驟如下:

第一步:小明根據(jù)要加密的信息14進行計算,得到加密后的信息20,然后將20告訴小紅和小偷;

第二步:小紅有自己的私鑰,將加密信息20進行解密,,得到了小明想傳遞給小紅的信息。而小偷呢,知道22,7,20,但是不知道小紅的密鑰(22,3),無法解密出正確的信息。

RSA加密算法在數(shù)字簽名中也發(fā)揮著巨大的作用,假設小偷可以假冒小紅,說小紅的公鑰是(22,9),而小明不知道是小偷假扮的,按照小偷的公鑰加密后,結果被小偷解密了。數(shù)字簽名的作用就是防止信息被篡改,小紅說她的公鑰是(22,7)的同時,使用私鑰給這段信息(通常使用MD5值計算簽名)加上簽名,小明得到公鑰(22,7)和簽名13,小明拿到簽名后利用公鑰計算出信息是否被篡改。

2345截圖20211028093243.png

五、加密的實際作用

本文使用的很小的數(shù)來進行加密原理的講解,為了是讀者可以方便進行計算。在實際使用中(n,e)都是特別大的數(shù),其中n的長度都在768以上,1024長度被認為是基本安全的。

(1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413=

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489

×

36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917)

六、總結

最后總結一下,首先我們通過一個詐騙短信的例子,引出了加密的原理就是信息+密鑰,密鑰就是對信息進行加解密的一串數(shù)字。然后通過顏料混合把戲形象的演示了如何建立共享密鑰。在使用乘法建立共享密鑰的過程中,學習了鐘算和冪運算,接著我們了解了RSA加密算法的過程,通過兩個質數(shù)生成公鑰和私鑰,最后,我們根據(jù)公鑰進行信息加密,再通過私鑰完成信息解密。

七、寫在最后

或許看到這里,大家心里還有許多疑惑。為什么小明和小紅建立共享密鑰時,通過幾次冪運算和鐘算就能得到一樣的共享密鑰?為什么RSA加密算法要用兩個質數(shù)?為什么通過公鑰加密的信息可以通過私鑰解開?

加密算法的背后,是一道道迷人的數(shù)學難題,而RSA加密算法之所以被廣泛運用,是因為一個名為整數(shù)分解的古老數(shù)學問題,你可以輕易找到兩個很大的質數(shù)相乘得到一個結果n,但是要將這個結果n分解回兩個質數(shù)就變得極其困難。盡管這個所謂的“整數(shù)分解”問題被研究了數(shù)個世紀,還沒人能找到一個足夠高效的通用方法解決它,并對標準RSA鐘大小造成危害。

數(shù)學史中充滿了未解決的問題,盡管這些迷人的問題缺乏任何實際應用,卻單靠其美學特質就吸引了數(shù)學家進行深入探究。令人頗感驚訝的是,許多這類迷人但顯然無用的問題后來都有了很大的實用價值,這一價值只有在問題被研究數(shù)個世紀后才得以破解。整數(shù)分解這一問題由來已久。對其最早的嚴肅研究似乎是在17世紀,由數(shù)學家費馬(Fermat)和梅森(Mersenne)進行的。歐拉(Euler)和高斯(Gauss)兩位數(shù)學“泰斗”也在接下來的世紀里對這一問題做出了貢獻。但直到公鑰加密于20世紀70年代被發(fā)明,分解大數(shù)字的困難才成為一個實際應用的關鍵。

八、參考資料

1.《RSA算法原理》

2.《RSA加密》

3.《RSA加密算法》

4.《改變未來的九大算法》

THEEND

最新評論(評論僅代表用戶觀點)

更多
暫無評論