更新一篇简书 STM32开发RSA算法实验过程，同时可以估算RSA算法在MCU上开发的可行性问题研究
开篇文章像写论文一样，RSA算法在ARM上开发，由于算法计算量很大，常用C语言开发的RSA算法大多用递归调用的方式，如果单纯的硬计算的话就不要考虑ARM芯片了，因为通过计算太耗时，这个时间是做项目不能接受的。而大多数递归算法处理的调用简单的说也是比较消耗资源，递归函数调用之所以消耗资源是因为函数堆栈的原因，递归不断调用函数本身，而一个函数在开始执行的时候是要先入栈，首先是形参入栈，然后是函数入栈，由于递归调用，函数是没有退出的，相当于函数没有退栈处理，这样的话每次递归调用一次函数就消耗一部分栈空间，最后栈空间被大量消耗，对于单片机而言导致资源不够。这也是为什么在很多资源不是特别多的情况下我们尽量比较少的考虑递归的使用，但是递归的使用确实能减少大量计算量并使程序简单易懂。
1.了解RSA算法原理，利用两个大素数乘积成为一个更巨大的数，很难被分解出质因数的特性来进行加密解密处理。传输过程中将公钥对发送给加密方，私钥对自己保存，然后加密方通过公钥对 对文件进行加密，通过各种传输到自己这边，自己利用手中的私钥对进行解密，由于其余的人不知道私钥对，即便他们在网络上截获了你的公钥对，也截获了你的加密文件，但是没有私钥对，依然无法解密，这也是非对称加密的原理。
公钥和私钥RSA算法原理以及相关例子介绍，推荐参考博客：https://www.cnblogs.com/jiftle/p/7903762.html
2.针对算法有部分了解后，查看算法实现，整理几个C语言算法实现：https://blog.csdn.net/haroroda/article/details/46336053，百度上都是基本的伪代码，不过针对这种代码可以了解一下实现原理，但是这种算法应用相对来说不好；在github 上有很多关于C语言实现RSA算法：https://github.com/KONGDejing/kongdejing.rsa
3.支持开源项目：关于github,在我前面一篇简书中曾经提到过，针对github一点点想法; 浏览github是一件很有趣的事情。
圆明园4.在STM32F407开发板上验证算法可行性，首先将算法在linux上进行验证，然后移植到开发板上，STM32F407开发板默认的栈空间大小是0x00000400,堆空间是0x00000200；实际上STM32内存大小有192K+4Kk扩展空间，验证过程中会发现，不同的位数质数相乘，会造成堆栈空间不够从而让算法无法正常运行，在默认的堆栈空间下，我自测发现只能实现低3位质数相乘的大素数作为module,修改堆栈大小能够有效增加运算的数据量。在目前MCU上开发，数据大小最长是8个字节的数据，相当于二进制2的64位数据，相当于十进制的数据的19位左右，对于1024位数据在mcu上是无法直接通过数据类型存储的，这样又需要做如何存储这种大数据，但是这里我们不讲如此大的数据存储，对于大多数应用场合其实经过RSA加密后也是难以破解的，而对于long long 型数据我们质数就有一定的限制，大小接近10亿数量级。RSA在大小接近10亿数量级乘积获得module，这样就有如何产生10亿左右大小素数的算法，相对这个算法实现10亿大小的数据是完全有可能的，但是RSA算法其实只需要知道两个大质数和公钥私钥就行，对于产品开发完全可以用内置的素数进行，不需要通过MCU自行生成。可以通过linux针对一部分算法进行验证，生成两个10亿级大素数，然后通过RSA算法进行计算，目前来说大素数随机生成方法是不存在的，这是一个NPC问题，NPC问题世界的七大难题之一，Miller-Rabin算法主要用途是检验一个大数是否是素数，但是无法随机产生一个大素数。java中有BigInterger概念，是可以生成1024bit数量级的大素数。针对C语言应用来说，用到longlong的8个字节64bit数据就可以了。
长江行水5.生成10亿数量级的大素数需要的时间也是比较长的，针对C语言而言，要找出10亿数量级的大素数耗时也是非常夸张的，博客：https://blog.csdn.net/huang_miao_xin/article/details/51331710即便是高效一点的算法，在1000W大小的数据内找到所有的素数，运行环境，CPU-i5-3210，内存4G，win7，vs2012时间消耗是2.5S ,10亿级数据远大于250S，因为越到后面，每个数据越来越大，每次判断耗时越来越大，所以增加耗时时间甚至几小时。所以不建议直接通过C语言来找两个大素数，通过java来生成两个比较大的素数还是比较容易的。直接利用java生成的素数内置到设备端。
水木清华6.利用生成的素数进行RSA算法处理，在STM32中根据两个素数和公钥生成私钥，然后将公钥发送给加密方对重要信息加密，解密方对传输过来的文件进行解密。这里面还有一个问题，如果素数越大的话，会导致加密文件越大，因为任何一个字符加密后的数据和素数的数据类型是一致的，如果一开始素数是int型数据，加密后每个字符数据变成Int大小，加密文件相当于扩大4倍，对于longlong型素数，加密文件相当于扩大8倍。在工程应用，产品开发过程中需要结合能容忍的范围，因为加密问价加大的话，传输时间相对来说增加不止一点半点，也是成倍增加。能够直观感受到MCU跑的不容易。
7. 结束语，找到学习方法，勇往直前，我始终相信任何工程项目只要想去做都是能够实现的。热爱一个事情
网友评论