1 密码学

1.1 背景

隐衷计算（Privacy-preserving computation）是指<font color=greem>在保证数据提供方不泄露原始数据</font>的前提下，对数据进行剖析计算的一系列信息技术，保障数据在流通与交融过程中的“可用不可见”。 Gartner公布的2021年前沿科技策略趋势中，将隐衷计算（其称为隐衷加强计算）列为将来几年科技倒退的九大趋势之一。 （数据流通需要推动隐衷计算势头炽热） 但仍存在诸多妨碍。

2021年被称为隐衷计算的元年，这门技术是门综合性十分强的畛域，波及到泛滥方向，比方<font color=greem>密码学、数学、大数据、实时计算、高性能计算、分布式、传统机器学习框架与算法，深度学习框架与算法</font>等等。本系列文章次要介绍下隐衷计算应用到的相干密码学的常识。

1.2 密码学简介

密码学在整个人类的历史进程中都有着重要的位置，涵盖了人类流动的方方面面。比方在谍战片中咱们常常看到公开工作者应用加密的报文传递重要的情报，比方在互联网冲浪的时候TLS/SSL也在保障咱们的信息安全，能够说密码学对人类的影响和作用是深远的，很难设想没有密码学爱护的日子是什么样的！那么到底什么是密码学？如何精确定义明码学习呢？本系列文章将会进行绝对详尽的介绍，欢送大家观看。

首先，密码学的精准定义还是援用下权威机构，以下内容来自百度百科：

密码学（在西欧语文中，源于希腊语kryptós“暗藏的”，和gráphein“书写”）是钻研如何隐密地传递信息的学科。在古代特地指对信息以及其传输的数学性钻研，常被认为是数学和计算机科学的分支，和信息论也密切相关。驰名的明码学者Ron Rivest解释道：“密码学是对于如何在敌人存在的环境中通信”，自工程学的角度，这相当于密码学与纯数学的异同。密码学是信息安全等相干议题，如认证、访问控制的外围。密码学的首要目标是暗藏信息的涵义，并不是暗藏信息的存在。密码学也促成了计算机科学，特地是在于电脑与网络安全所应用的技术，如访问控制与信息的机密性。密码学已被利用在日常生活：包含主动柜员机的芯片卡、电脑使用者存取明码、电子商务等等。

明码是通信单方按约定的法令进行信息非凡变换的一种重要窃密伎俩。按照这些法令，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。明码在晚期仅对文字或数码进行加、脱密变换，随着通信技术的倒退，对语音、图像、数据等都可施行加、脱密变换。

密码学一开始的性能是在有歹意攻击者存在的环境下，爱护单方通信安全，当初是用来爱护信息安全的核心技术。

古代信息安全的根本要求：

  • 信息的保密性 Confidentiality：避免信息透露给未经受权的人（加密解密技术）
  • 信息的完整性 Integrity：避免信息被未经受权的篡改（音讯认证码，数字签名）
  • 认证性 Authentication：保障信息来自正确的发送者（音讯认证码，数字签名）
  • 不可否认性 Non-repudiation：保障发送者不能否定他们已发送的音讯（数字签名）

1.3 密码学术语

  • 密钥：分为加密密钥和解密密钥。
  • 明文：没有进行加密，可能间接代表原文含意的信息。
  • 密文：通过加密解决解决之后，暗藏原文含意的信息。
  • 加密：将明文转换成密文的施行过程。
  • 解密：将密文转换成明文的施行过程。
  • 明码算法：明码零碎采纳的加密办法和解密办法，随着基于数学明码技术的倒退，加密办法个别称为加密算法，解密办法个别称为解密算法。
  • 加密(encryption）算法：将一般信息（明文,plaintext）转换成难以了解的材料（密文,ciphertext）的过程；
  • 解密(decryption）算法则是其相同的过程：由密文转换回明文；加解密蕴含了这两种算法，个别加密即同时指称加密(encrypt或encipher）与解密(decrypt或decipher）的技术。

加解密的具体运作由两局部决定：

一个是算法，另一个是密钥。密钥是一个用于加解密算法的机密参数，通常只有通信者领有。

1.4 古代密码学常见的算法流派

以工夫划分，1976 年以前的明码算法都属于古典密码学，根本应用在军事机密和内政畛域，它的特点就是加解密过程简略，个别用手工或机械就能够实现，古典密码学当初曾经很少应用了，上面是一个古典加密的密码本，提供一对一的映射变换，次要领有这个密码本，就能够轻易的通过手工的形式进行信息加密与解密。

古代密码学中常见的加密算法，大抵能够分为如下几种：

  1. 散列算法：MD5算法、Sha系列算法；
  2. 对称加密：DES、3DES、RC2、RC4、AES等；
  3. 非对称算法：RSA、ECC等；

本系列文章将会重点形容下对称加密与非对称加密技术，从数学原理、加密算法推导、加密算法原理都会进行介绍。本文内容波及到数学外面的数论相干常识，针对加密算法会用到的常识，本章会做些适当的介绍，对数论感兴趣的同学能够茶语相干《数论》书籍进行精进，外面推导如果有不谨严的中央，欢送各位同学帮忙斧正。

2 对称加密

2.1 对称加密的定义

采纳单钥明码零碎的加密办法，同一个密钥能够同时用作信息的加密和解密，这种加密办法称为对称加密，也称为单密钥加密。

  • 性能较好：须要对加密和解密应用雷同密钥的加密算法。因为其速度快，对称性加密通常在音讯发送方须要加密大量数据时应用。对称性加密也称为密钥加密。
  • 对称性：所谓对称，就是采纳这种加密办法的单方应用形式用同样的密钥进行加密和解密。密钥是管制加密及解密过程的指令。算法是一组规定，规定如何进行加密和解密。
  • 安全性：对称加密的安全性不仅取决于加密算法自身，密钥治理的安全性更是重要。因为加密和解密都应用同一个密钥，如何把密钥平安地传递到解密者手上就成了必须要解决的问题。

2.2 常见的对称加密算法

对称加密的特点是算法是公开的，然而秘钥是暗藏的（只有加密解密单方持有），公开的明码算法安全性更高，能被更多人评论和应用，增强破绽的修补。

对称加密的算法泛滥，历史上呈现过不少的算法实现，不同的算法在某些特定的期间，承当着重要的角色。尽管有些算法在当初曾经不再实用，存在着安全漏洞，然而在过后的算力状况下，的确起到过十分重要的作用。给予人们提供平安屏障，爱护信息安全。上面就简要比照介绍下比拟闻名的集中对称加密算法。

加密算法长处毛病破解形式应用场景安全性
DES算法公开、计算量小、加密速度快、效率高；DES目前曾经被破除；（1）秘钥位数太少，在现有算力的状况下，非常容易被暴力破解，无奈保障安全性；（2）DES是为硬件加密设计的，对于当初软件来说计算效率不够好；（3）始终有人狐疑DES的S盒中暗藏着后门，而这个后门被美国安全局把握。（4）秘钥治理的泄露危险；暴力破解、穷举一般数据加密低
3DES算法公开、计算量小、加密速度快、效率高；秘钥治理的泄露危险难度大一般数据加密较高
AES组模式抉择多，加密平安；同DES相似，明码治理都是问题；暴漏过线性明码攻打、查封明码攻打，难度大一般数据加密较高
RC4算法公开、计算量小、加密速度较快不平安，存在安全漏洞，目前根本废除；因为RC4算法加密是采纳的xor，所以，一旦子密钥序列呈现了反复，密文就有可能被破解。对于如何破解xor加密，请参看Bruce Schneier的Applied Cryptography一书的1.4节Simple XOR，在此我就不细说了。存在安全漏洞目前根本曾经废除低

2.3 对称加密的局限

其实，很多人表白过这样的观点，对称加密不平安，有被破解的危险。其实笔者认为这样的说法不是很谨严，单纯的对称加密比方AES还是很平安的，然而对称加密的一个重要的个性就是加密与解密应用同一个秘钥，对于秘钥的保留和传递都是个十分头疼的问题，一旦泄露就会造成极大的危险。

那么，有没有什么方法能够进一步升高这个泄露的危险呢？答案就是非对称加密。上面咱们来介绍下非对称加密。

3 数论根底

在正式介绍RSA算法之前，因为该算法须要较多的数学知识，正所谓“磨刀不误砍柴工，万丈高楼平地起”，所以依照如下的步骤进行解说。

首先，会介绍下数论的相干的基础知识，次要蕴含质数、互质关系、欧拉函数、欧拉定理以及模反元素。接着，会介绍下RSA算法的具体实现流程，并且会联合例子进行实践加实际的形容。

而后，会依据后面解说的数论的常识，进行RSA算法的安全性验证与推导的验证。

最初，通过这一系列的形容与解说，置信读者对于RSA算法曾经进行了把握，前面会介绍下在网络传输中的利用。

所以本节次要介绍数论的基础知识，为后续的RSA算法的推导和证实提供实践根底。

3.1 质数

质数在数学畛域是一个神奇的数字，很多数学定理都是基于质数的。

<font color=Greem>质数（Prime number），又称素数</font>，大于1的自然数中，除了1和该数本身外，无奈被其余自然数整除的数（也可定义为只有1与该数自身两个正因数的数）。<font color=Greem>大于1的自然数若不是素数，则称之为合数（也称为合成数）</font>。例如，5是个素数，因为其正约数只有1与5。而6则是个合数，因为除了1与6外，2与3也是其正约数。

算术根本定理确立了素数于数论里的外围位置：任何大于1的整数均可被示意成一串惟一素数之乘积。为了确保该定理的唯一性，1被定义为不是素数，因为在因式分解中能够有任意多个1（如3、1×3、1×1×3等都是3的无效约数合成）。

3.2 互质关系（互质数）

<font color=greem>如果两个整数的公约数只有1，那么叫做互质整数。</font>公约数只有1的两个自然数，叫做互质自然数，后者是前者的非凡情景。

例如：

1. 8,10的最大公因数是2，不是1，因而不是整数互质。2. 7,11,13的最大公因数是1，因而这是整数互质。3. 5和5不互质，因为5和5的公因数有1、5。4. 1和任何数都成倍数关系，但和任何数都互质。

对于互质关系，总结一下，有如下的性质

1. 两个不同的质数肯定互质。例如2与7，13和19。2. 一个数是质数，另一个数不是它的倍数，两者就形成互质关系，比方5和26。3. 如果两个数之中，较大的那个数是质数，则两者形成互质关系，比方97和57。4. 1不是质数也不是合数，它和任何一个自然数（1自身除外）在一起都是互质关系。如1和9908。5. 相邻的两个自然数是互质数。如 15与 16。6. 相邻的两个奇数是互质数。如 49与 51。7. 较大数是质数的两个数是互质数。如97与66。

3.3 欧拉函数

提到欧拉，就不得不多说几句，莱昂哈德•欧拉（Leonhard Euler，1707年4月5日～1783年9月18日）是瑞士巴塞尔左近一个牧师的儿子，他除了学习神学外，还钻研数学，并且获得了微小的问题。他被一些数学史学者称为历史上最平凡的两位数学家之一（另一位是卡尔•弗里德里克•高斯）。数学中很多名词以欧拉的名字命名，如欧拉常数，欧拉方程，欧拉恒等式，欧拉示性数等等。

欧拉被公认为人类历史上成就最为斐然的数学家之一。在数学及许多分支中都能够见到很多以欧拉命名的常数、公式和定理，他的工作使得数学更靠近于当初的状态。他岂但为数学界作出贡献，更把数学推至简直整个物理畛域。此外欧拉还波及建筑学、弹道学、航海学等畛域。瑞士教育与钻研国务秘书Charles Kleiber曾示意：“没有欧拉的泛滥迷信发现，明天的咱们将过着齐全不一样的生存。”法国数学家拉普拉斯则认为：读读欧拉，他是所有人的老师。

那么在数论中对于<font color=greem>正整数n来说</font>，欧拉函数 (n)的计算逻辑就是小于n的正整数中与n互质的整数的数目。

例如，在1到8之中，与8造成互质关系的是1、3、5、7，所以 (n) = 4。
  1. 如果n是质数，那么(n) =n-1。反之，如果n是正整数且满足(n) =n-1，那么n是质数。
  2. 如果n是质数，a是一个正整数，那么 $\phi(n^a) = p^a - p^{a-1}$。
  3. 如果m和n是互质数，那么$\phi(mn) = \phi(m) * \phi(n)$。
  4. 如果$n=p_1^{a_1} * p_2^{a_2}*...*p_n^{a_n}$，那么$\phi(n) = n(1-\frac{1}{p_1})*(1-\frac{1}{p_2}*...*(1-\frac{1}{p_n})$。

3.4 欧拉定理

下面咱们介绍了质数、互质关系以及欧拉函数，基于这些常识，咱们持续介绍欧拉定理，

  • 定义

如果<font color=greem>两个正整数a和n互质</font>，则n的欧拉函数 (n) 能够让上面的等式成立，能够了解为a的(n)次方被n除的余数为1。

$$a^{\phi(n)} \equiv 1(mod \; n)$$

用艰深的语言形容下，就是a的$\phi(n)$次方除以n的余数是1，也能够了解为a的$\phi(n)$次方加1能够被n整除。

  • 样例
正整数3和8互质，其中8的欧拉函数是4（互质数是1，3，5，7），则3的4次方是81，81减去1正好是80，80除以8正好被整除。
  • 非凡状况：费马小定理

假如正整数a与<font color=greem>质数p</font>互质，因为质数p的(p)等于p-1，则欧拉定理能够写成

$$a^{p-1} \equiv 1(mod \; n)$$

也能够示意成

$$a^{p} \equiv a(mod \; n)$$

欧拉定理（费马小定理）的证实波及到当模是合数（素数就是费马小定理）的时候如何解决蕴含指数的特定同余式，相干证实大家能够看下数论的相干书籍，举荐浏览《高等数论机及其利用》（Kenneth H. Rosen著），外面的解说还是比拟清晰的。

3.5 模反元素（模逆运算）

  • 定义

模反元素亦叫模逆运算，定义如下：如果两个<font color=greem>正整数a和n互质</font>，那么肯定能够找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。

$$a*b\equiv 1(mod \; n)$$

  • 样例

比方，3和14互质，那么3的模反元素就是5，因为 (3 × 5)-1 能够被14整除。显然，模反元素不止一个， 5加减14的整数倍都是3的模反元素 {...,-23, -9, 5, 19, 33,...}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。

4 未完待续

至此，进行RSA加密算法推导与证实的数学知识介绍结束，后续章节将持续介绍RSA相干常识以及利用场景。

5 参考资料

  • https://zhuanlan.zhihu.com/p/...
  • RSA加密算法：https://zh.wikipedia.org/wiki/R

6 番外篇

集体介绍：杜宝坤，隐衷计算行业从业者，从0到1率领团队构建了京东的联邦学习解决方案9N-FL，同时主导了联邦学习框架与联邦开门红业务。
框架层面：实现了电商营销畛域反对超大规模的工业化联邦学习解决方案，反对超大规模样本PSI隐衷对齐、平安的树模型与神经网络模型等泛滥模型反对。
业务层面：实现了业务侧的开门红业务落地，创始了新的业务增长点，产生了显著的业务经济效益。
集体比拟喜爱学习新货色，乐于钻研技术。基于从全链路思考与决策技术布局的考量，钻研的畛域比拟多，从工程架构、大数据到机器学习算法与算法框架均有波及。欢送喜爱技术的同学和我交换，邮箱：baokun06@163.com

<font color=Blue>所有有为法，如梦幻泡影，如露亦如电，应作如是观</font>

本文由mdnice多平台公布