更新一篇簡書 ? ?STM32開發(fā)RSA算法實驗過程，同時可以估算RSA算法在MCU上開發(fā)的可行性問題研究
? ? ? ? 開篇文章像寫論文一樣弱贼，RSA算法在ARM上開發(fā)蒸苇，由于算法計算量很大，常用C語言開發(fā)的RSA算法大多用遞歸調(diào)用的方式吮旅，如果單純的硬計算的話就不要考慮ARM芯片了溪烤，因為通過計算太耗時，這個時間是做項目不能接受的庇勃。而大多數(shù)遞歸算法處理的調(diào)用簡單的說也是比較消耗資源檬嘀，遞歸函數(shù)調(diào)用之所以消耗資源是因為函數(shù)堆棧的原因，遞歸不斷調(diào)用函數(shù)本身责嚷，而一個函數(shù)在開始執(zhí)行的時候是要先入棧鸳兽，首先是形參入棧，然后是函數(shù)入棧罕拂，由于遞歸調(diào)用揍异，函數(shù)是沒有退出的全陨，相當于函數(shù)沒有退棧處理，這樣的話每次遞歸調(diào)用一次函數(shù)就消耗一部分椫灾溃空間辱姨，最后棧空間被大量消耗戚嗅，對于單片機而言導致資源不夠雨涛。這也是為什么在很多資源不是特別多的情況下我們盡量比較少的考慮遞歸的使用，但是遞歸的使用確實能減少大量計算量并使程序簡單易懂渡处。
? ? ?? 1.了解RSA算法原理镜悉，利用兩個大素數(shù)乘積成為一個更巨大的數(shù)，很難被分解出質(zhì)因數(shù)的特性來進行加密解密處理医瘫。傳輸過程中將公鑰對發(fā)送給加密方侣肄，私鑰對自己保存，然后加密方通過公鑰對? 對文件進行加密醇份，通過各種傳輸?shù)阶约哼@邊稼锅，自己利用手中的私鑰對進行解密，由于其余的人不知道私鑰對僚纷，即便他們在網(wǎng)絡(luò)上截獲了你的公鑰對矩距，也截獲了你的加密文件，但是沒有私鑰對怖竭，依然無法解密锥债，這也是非對稱加密的原理。
?RSA算法原理以及相關(guān)例子介紹痊臭，推薦參考博客：https://www.cnblogs.com/jiftle/p/7903762.html
? ? ? 2.針對算法有部分了解后锌畸，查看算法實現(xiàn)岛抄，整理幾個C語言算法實現(xiàn)：https://blog.csdn.net/haroroda/article/details/46336053纸淮，百度上都是基本的偽代碼董栽，不過針對這種代碼可以了解一下實現(xiàn)原理，但是這種算法應用相對來說不好鸦致；在github 上有很多關(guān)于C語言實現(xiàn)RSA算法：https://github.com/KONGDejing/kongdejing.rsa
? ? ? 3.支持開源項目：關(guān)于github,在我前面一篇簡書中曾經(jīng)提到過潮剪，針對github一點點想法; 瀏覽github是一件很有趣的事情。
? ? ? 4.在STM32F407開發(fā)板上驗證算法可行性分唾，首先將算法在linux上進行驗證抗碰，然后移植到開發(fā)板上，STM32F407開發(fā)板默認的椪狼牵空間大小是0x00000400,堆空間是0x00000200改含；實際上STM32內(nèi)存大小有192K+4Kk擴展空間，驗證過程中會發(fā)現(xiàn)，不同的位數(shù)質(zhì)數(shù)相乘捍壤，會造成堆棧空間不夠從而讓算法無法正常運行鞍爱，在默認的堆椌榫酰空間下，我自測發(fā)現(xiàn)只能實現(xiàn)低3位質(zhì)數(shù)相乘的大素數(shù)作為module,修改堆棧大小能夠有效增加運算的數(shù)據(jù)量睹逃。在目前MCU上開發(fā)盗扇，數(shù)據(jù)大小最長是8個字節(jié)的數(shù)據(jù)，相當于二進制2的64位數(shù)據(jù)沉填，相當于十進制的數(shù)據(jù)的19位左右疗隶，對于1024位數(shù)據(jù)在mcu上是無法直接通過數(shù)據(jù)類型存儲的，這樣又需要做如何存儲這種大數(shù)據(jù)翼闹，但是這里我們不講如此大的數(shù)據(jù)存儲斑鼻，對于大多數(shù)應用場合其實經(jīng)過RSA加密后也是難以破解的，而對于long long 型數(shù)據(jù)我們質(zhì)數(shù)就有一定的限制猎荠，大小接近10億數(shù)量級坚弱。RSA在大小接近10億數(shù)量級乘積獲得module，這樣就有如何產(chǎn)生10億左右大小素數(shù)的算法关摇，相對這個算法實現(xiàn)10億大小的數(shù)據(jù)是完全有可能的荒叶，但是RSA算法其實只需要知道兩個大質(zhì)數(shù)和公鑰私鑰就行，對于產(chǎn)品開發(fā)完全可以用內(nèi)置的素數(shù)進行输虱，不需要通過MCU自行生成些楣。可以通過linux針對一部分算法進行驗證宪睹，生成兩個10億級大素數(shù)愁茁，然后通過RSA算法進行計算，目前來說大素數(shù)隨機生成方法是不存在的横堡，這是一個NPC問題埋市，NPC問題世界的七大難題之一，Miller-Rabin算法主要用途是檢驗一個大數(shù)是否是素數(shù)命贴，但是無法隨機產(chǎn)生一個大素數(shù)道宅。java中有BigInterger概念，是可以生成1024bit數(shù)量級的大素數(shù)胸蛛。針對C語言應用來說污茵，用到longlong的8個字節(jié)64bit數(shù)據(jù)就可以了。
5.生成10億數(shù)量級的大素數(shù)需要的時間也是比較長的葬项，針對C語言而言泞当，要找出10億數(shù)量級的大素數(shù)耗時也是非常夸張的民珍，博客：https://blog.csdn.net/huang_miao_xin/article/details/51331710即便是高效一點的算法襟士，在1000W大小的數(shù)據(jù)內(nèi)找到所有的素數(shù)盗飒，運行環(huán)境，CPU-i5-3210陋桂，內(nèi)存4G逆趣，win7，vs2012時間消耗是2.5S ,10億級數(shù)據(jù)遠大于250S嗜历，因為越到后面宣渗，每個數(shù)據(jù)越來越大，每次判斷耗時越來越大梨州，所以增加耗時時間甚至幾小時痕囱。所以不建議直接通過C語言來找兩個大素數(shù)，通過java來生成兩個比較大的素數(shù)還是比較容易的暴匠。直接利用java生成的素數(shù)內(nèi)置到設(shè)備端鞍恢。
6.利用生成的素數(shù)進行RSA算法處理，在STM32中根據(jù)兩個素數(shù)和公鑰生成私鑰巷查，然后將公鑰發(fā)送給加密方對重要信息加密有序，解密方對傳輸過來的文件進行解密。這里面還有一個問題岛请，如果素數(shù)越大的話旭寿，會導致加密文件越大，因為任何一個字符加密后的數(shù)據(jù)和素數(shù)的數(shù)據(jù)類型是一致的崇败，如果一開始素數(shù)是int型數(shù)據(jù)盅称，加密后每個字符數(shù)據(jù)變成Int大小，加密文件相當于擴大4倍后室，對于longlong型素數(shù)缩膝，加密文件相當于擴大8倍。在工程應用岸霹，產(chǎn)品開發(fā)過程中需要結(jié)合能容忍的范圍疾层，因為加密問價加大的話，傳輸時間相對來說增加不止一點半點贡避，也是成倍增加痛黎。能夠直觀感受到MCU跑的不容易。
7.? 結(jié)束語刮吧，找到學習方法湖饱，勇往直前，我始終相信任何工程項目只要想去做都是能夠?qū)崿F(xiàn)的杀捻。熱愛一個事情
