隐私计算密码学基础系列 - Diffie-Hellman 密钥交换

1 密码学

1.1 背景

隐私计算（Privacy-preserving computation）是指在保证数据提供方不泄露原始数据的前提下，对数据进行分析计算的一系列信息技术，保障数据在流通与融合过程中的可用不可见。 Gartner发布的2021年前沿科技战略趋势中，将隐私计算（其称为隐私增强计算）列为未来几年科技发展的九大趋势之一。 （数据流通需求推动隐私计算势头火热） 但仍存在诸多阻碍。

2021年被称为隐私计算的元年，这门技术是门综合性非常强的领域，涉及到众多方向，比如密码学、数学、大数据、实时计算、高性能计算、分布式、传统机器学习框架与算法，深度学习框架与算法等等。本系列文章主要介绍下隐私计算使用到的相关密码学的知识。

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等；

本系列文章将会重点描述下非对称加密即公钥加密的开山之作Diffie–Hellman key exchange。本文内容涉及到数学里面的数论相关知识，针对加密算法会用到的知识，本章会做些适当的介绍，对数论感兴趣的同学可以查阅相关《数论》书籍进行精进，里面推导如果有不严谨的地方，欢迎各位同学帮忙指正。

2 数论基础

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

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

然后，会根据前面讲解的数论的知识，进行RSA算法的安全性验证与推导的验证。

最后，通过这一系列的描述与讲解，相信读者对于RSA算法已经进行了掌握，后面会介绍下在网络传输中的应用。

所以本节主要介绍数论的基础知识，为后续的RSA算法的推导和证明提供理论基础。

2.1 质数

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

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

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

2.2 互质关系（互质数）

如果两个整数的公约数只有1，那么叫做互质整数。公约数只有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。

2.3 欧拉函数

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

欧拉被公认为人类历史上成就最为斐然的数学家之一。在数学及许多分支中都可以见到很多以欧拉命名的常数、公式和定理，他的工作使得数学更接近于现在的形态。他不但为数学界作出贡献，更把数学推至几乎整个物理领域。此外欧拉还涉及建筑学、弹道学、航海学等领域。瑞士教育与研究国务秘书Charles Kleiber曾表示：“没有欧拉的众多科学发现，今天的我们将过着完全不一样的生活。”法国数学家拉普拉斯则认为：读读欧拉，他是所有人的老师。

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

例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。

1. 如果n是质数，那么φ(n) =n-1。反之，如果n是正整数且满足φ(n) =n-1，那么n是质数。
2. 如果n是质数p的k次方，那么 $\phi(p^k) = p^k - p^{k-1}$。
3. 如果m和n是互质数，那么$\phi(mn) = \phi(m) * \phi(n)$。
4. 如果$n=p_1^{a_1} * p_2^{a_2}*...*p_n^{a_n}$（p是质数），那么$\phi(n) = n(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*...*(1-\frac{1}{p_n})$。

2.4 欧拉定理

上面我们介绍了质数、互质关系以及欧拉函数，基于这些知识，我们继续介绍欧拉定理，

• 定义

如果两个正整数a和n互质，则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与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成

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

也可以表示成

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

欧拉定理（费马小定理）的证明涉及到当模是合数（素数就是费马小定理）的时候如何处理包含指数的特定同余式，相关证明大家可以看下数论的相关书籍，推荐阅读《初等数论机及其应用》（Kenneth H. Rosen著），里面的讲解还是比较清晰的。

2.5 模反元素（模逆运算）

• 定义

模反元素亦叫模逆运算，定义如下：如果两个正整数a和n互质，那么一定可以找到整数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的模反元素。

2.6 原根

在数论中，特别是在除法理论中，原根是一个非常重要的概念。


对于两个互质的正整数a和n。有上面介绍的欧拉定理可知，存在正整数$d\leq m -1$，比如说欧拉函数$d=\phi(n)$，即小于等于m的正整数中与m互质的正整数的个数，使得 $a^d \equiv 1(mod \; n)$。

由此，对于对于两个互质的正整数a和n。定义a对模n的指数$\delta_n(a)$为使得 $a^d \equiv 1(mod \; n)$成立的最小的正整数d。由前面知道$\delta_n(a)$一定小于等于$\phi(n)$，若$\delta_n(a) =\phi(n)$，则称a是n的原根。

举例：

设n=7，则$\phi(n)$等于6。

• 设a=2，那么由于$2^1\equiv 2(mod \; 7)，2^2\equiv 4(mod \; 7)，2^3\equiv 1(mod \; 7)，2^4\equiv 2(mod \; 7)，2^5\equiv 4(mod \; 7)，2^6\equiv 1(mod \; 7)$，因此有$Ord_7(2) = 3 \neq \phi(7)$，所以2不是模7的一个原根。
• 设a=3，那么由于$3^1\equiv 3(mod \; 7)，3^2\equiv 2(mod \; 7)，3^3\equiv 6(mod \; 7)，3^4\equiv 4(mod \; 7)，3^5\equiv 5(mod \; 7)，3^6\equiv 1(mod \; 7)$