iOS应用安全 1 -- 密码学及RSA算法原理

本文主要是介绍iOS应用安全 1 -- 密码学及RSA算法原理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

密码学

概念

密码学是指研究信息加密，破解密码的技术科学。

发展历史

密码学的历史可以追溯到两千年前，相传古罗马凯撒大帝为了防止敌方截获情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表。这样，如果不知道密码本，即使截获一段信息也看不懂。
从密码出现到1976年以前，加密模式就只有一种，即加密和解密使用同一种算法。在进行数据交互时，A必须要将加密规则告诉B，B才能解密出真实数据。因此，加密和解密的规则（称为密钥）就显得尤为重要，并且密钥的传递就成了这种加密模式最大的隐患。而这种加密方式就被称为对称加密。
1976年，两位美国计算机学家 迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种新的方案，可以在不直接传递密钥的情况下完成密钥的交换，这种方案被称为 迪菲赫尔曼密钥交换。开拓了密码学的新方向。
时隔一年即1977年，三位麻省理工的数学家 罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir） 和 伦纳德·阿德曼（Leonard Adleman） 一起设计了一种算法，可以实现非对称加密。而这个算法就用他们三个的名字命名------RSA算法。

RSA算法

非对称加密算法，需要两个密钥，公开密钥简称公钥（publicKey） 和私有密钥简称私钥（privateKey）。公钥加密，私钥解密；私钥加密，公钥解密。

数学原理

讲解RSA数学原理之前，一定要明白的几个概念。

质数

在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。如：2、3、5、7、11、13。

互质

若两个自然数除了1之外没有其他公因子，则这两个数就是互质关系。如：3和5、7和10。

欧拉函数

题目：给定任意一个正整数n，在小于等于n的正整数中有几个与n互质？

计算这个题的函数就叫欧拉函数，用Φ(n)表示。
举例：

若n = 7，则1、2、3、4、5、6、7中1、2、3、4、5、6与n互质，则Φ(7) = 6。
若n = 8，则有1、3、5、7与8互质，则Φ(8) = 4。

欧拉函数特点

当n是质数时，Φ(n) = n - 1。
若n可以分解为两个互质的整数之积，如：n = a * b，a和b互质，则有Φ(n) = Φ(a) * Φ(b)。
若n可分解为两个质数之积，如：n = a * b，a和b均为质数，则Φ(n) = Φ(a) * Φ(b) = (a - 1) * (b - 1)。

举例：

Φ(56) = Φ(7) * Φ(8) = 6 * 4 = 24。
Φ(35) = Φ(5) * Φ(7) = (5 - 1) * (7 - 1) = 24。巧合了，都是24。

欧拉定理

如果a和b互质，则a的Φ(b)次方减1一定可以被b整除，即： $a^{\phi(b)}mod\ b=1$ 。

接下来我们可以对欧拉定理进行一些转换

由于 $1^k = 1$ ，所以 $a^{\phi(b) * k}mod\ b=1$ 。
由于 $1*a=a$ ，所以 $a^{\phi(b)*k+1}mod\ b=a$ 。
若转换过程不明白可以仔细分析，关键点就在于 $(x^ymod$ $z)^m=x^{y*m}mod\ z$ 和 $(x^ymod\ z)*x^m=x^{y+m}mod\ z$ ，可以自己验证一下。

模反元素

如果两个正整x和y互质，则一定可以找到一个整数z，使得xz-1能被y整除，此时z就叫做x相对于y的模反元素。
即： $(x*z)mod\ y=1$ ，也即 $x*z=y*k+1$ ，k是任意值的常量。

--------------------一条分割线先暂停一下-----------------------

小结

看到小结以为文章到这就结束了？NONONO，这只是上面那些推导定理的小结。

RSA数学原理所用到的数学定理及推导定理到这算是讲完了，先总结一下我们推导出来可以使用的条件：

如果a和b互质，则 $a^{\phi(b)*k+1}mod\ b=a$ 。（欧拉定理推导）
如果x和y互质，则可以找到一个z满足 $x*z=y*k+1$ 。（模反元素推导）

还有推导过程中我们用到的一些基础知识：

$(x^ymod$ $z)^m=x^{y*m}mod\ z$
$(x^ymod\ z)*x^m=x^{y+m}mod\ z$

迪菲赫尔曼密钥交换过程及原理

前面密码学的发展历史中讲到1976年迪菲和赫尔曼提出了一种不直接传递密钥就可完成密钥交换的方法叫做迪菲赫尔曼密钥交换，开拓了密码学的新篇章。并且仅仅时隔一年RSA非对称加密就诞生了，要说这两者之间没有任何关系估计鬼都不信吧。

借个图来解释一下迪菲赫尔曼密钥交换的原理。

客户端和服务端私下商定两个数，m = 3, n = 17。（外人一般不会知道，知道了也没关系）
客户端和服务端分别生成一个随机数，cr = 13, sr = 15。
客户端计算 $m^{cr}mod\ n = 3^{13}mod\ 17 = 12$ 的值发送给服务端。
同理，服务端计算 $m^{sr}mod\ n = 3^{15}mod\ 17 = 6$ 的值给客户端，这两个发送的过程都是不安全的，容易被第三方窃取到12和6，但是没关系，他窃取到也没用。
客户端拿到服务端计算的6，再计算 $6^{13}mod\ 17 = 10$ 。
服务端拿到客户端计算的12，再计算 $12^{15}mod\ 17 = 10$ 。

啊哦，发生了什么？这两个算出来的结果居然是相同的？
对，没错，这个最终算出来的10就是真正用来加密的密钥。

到这就不得不说这种方法的巧妙之处了，黑客可以从网络中截取到6和12，但是他想要算出真正的密钥10，就必须知道m，n，cr/sr的值。m和n也可能通过一些特殊手段得到，但是cr和sr这两个都是随机生成的。因此黑客想要破解出真正的密钥就只有暴力破解，而应对暴力破解，我们可以将cr/sr，n的值设置为非常大的数，例如1024或2048位，这样位数的数字破解难度就已经非常大了。这些就是迪菲赫尔曼密钥交换的原理。

等等，不是说讲RSA的原理吗？怎么讲到密钥交换原理了？还有前面说了一大堆欧拉定理、模反元素是干什么的？还说不是凑字数？

先把砖头🧱放下，我还有没讲完呢，接下来就把前面的东西都用上。😂😂

RSA原理

这里是整篇文章的重点和难点，不明白的可以找找纸笔画画，笔者学这一块的时候画了两张A4纸，正反两面。
下面把前面推导出来的原理再拿过来：

如果a和b互质，则 $a^{\phi(b)*k+1}mod\ b=a$ 。（欧拉定理推导）
如果x和y互质，则可以找到一个z满足 $x*z=y*k+1$ 。（模反元素推导）

有没有发现 $\phi(b)*k+1$ 和 $y*k+1$ 在格式上很相似？
所以现在像做应用题一样：
设 $y=\phi(b)$
则当a和b互质，x和Φ(b)互质时，有 $a^{x*z}mod\ b=a$ 。一定要记清楚这个结论的前提条件。

我们接着把上面的那个结论拆开，可以得到 $a^xmod\ b=c$ 和 $c^zmod\ b=a$ 。有没有觉得好像在哪见过这两个式子呢？就是在上面的迪菲赫尔曼密钥交换那里啊。
$a^xmod\ b=c$ 就相当于客户端进行的操作，计算出c发送给服务端，服务端通过 $c^zmod\ b=a$ 计算出终极密钥a。

说到这，细心的你有没有对比这两个式子和上面密钥交换不一样的地方呢？
什么？还有不一样的地方？

当然有，仔细看密钥交换的那两步计算，计算前是3，最终计算出来的结果是10。而这 $a^xmod\ b=c$ 和 $c^zmod\ b=a$ 两个式子，计算前是a，计算后还是a。是不是恍然大悟？如果说第一个式子是用x加密a得到c，第二个式子用z解密c再得到a，这样说你就该明白RSA的原理了吧?

再等等，先别结束，还有问题，这两个式子分别是加密和解密这我理解了，但是为什么它们计算前和计算后是一样的，而迪菲赫尔曼密钥交换计算前后是不一样的？不解释清楚别想结束！
所以别忘了这两个式子推导出来的前提条件：

a和b互质。
x和Φ(b)互质，由于乘法交换律，所以z和Φ(b)肯定也是互质的。
z是x对于Φ(b)的模反元素，即 $(x*z)mod\ \phi(b)=1$ 。

在加密解密过程中，a是需要传输的原始数据。b、x、z则都是未知的，因此我们需要针对上面的三个前提条件来找b、x、z的值。
举个例子：

要传输的数据a = 3，为了满足条件1，我让b = 5，则Φ(b) = Φ(5) = 4。
条件2中x需要和Φ(b)互质，我让x = 7。为了满足条件3的 $(x*z)mod\ \phi(b)=1$ ，我可以让z = 11，这样 $(7*11)mod\ 4 = 1$ 是成立的。也就是说现在3个条件都满足了。
下面就到了验证的时刻了，带入那两个式子 $c=a^xmod\ b=3^7mod\ 5=2$ ，而 $a=c^zmod\ b=2^{11}mod\ 5=3$ 。验证是成功的。

当然，在真正使用上肯定不会像上面例子那样简单，一般密钥都是在1024位以上。另外说明一下，这个加密和解密的过程中密钥并不单单是x和z，真正的加密密钥应该是x和b，解密密钥应该是z和b。

总结

好了，要讲的都已经讲完了，现在就来总结一下这篇文章中用到的知识点。

数学知识。质数、互质、欧拉函数、欧拉定理、模反元素。
迪菲赫尔曼密钥交换的过程及原理。
RSA原理及原理的推导过程。

差不多就这么多了，接下来还有就是，，，额，没什么事了，结束。

哦对了，维权。这就是原文

这篇关于iOS应用安全 1 -- 密码学及RSA算法原理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Swift教程