隐私计算加密技术基础系列（中）-RSA非对称加密
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 年以前的密码算法都属于古典密码学，基本使用在军事机密和外交领域，它的特点就是加解密过程简单，一般用手工或机械就可以完成，古典密码学现在已经很少使用了，下面是一个古典加密的密码本，提供一对一的映射变换，主要拥有这个密码本，就可以轻易的通过手工的方式进行信息加密与解密。
现代密码学中常见的加密算法，大致可以分为如下几种：
-
散列算法：MD5算法、Sha系列算法； -
对称加密：DES、3DES、RC2、RC4、AES等； -
非对称算法：RSA、ECC等；
本篇文章属于《隐私计算加密技术基础系列》的第二篇（中篇），在上篇《隐私计算加密技术基础系列（上）》中，我们介绍并讲解了对称加密以及非对称加密需要的数论的相关知识，本章将会在前面的基础上继续介绍非对称加密算法-RSA，在本章中会大量应用上篇文章的理论内容，建议读者按照章节顺序进行阅读。
2 非对称加密-RSA算法简介
2.1 RSA算法的历程
RSA加密算法（亦称公钥加密算法）是一种非对称加密算法，不同于公钥加密，RSA算法的秘钥由两部分组成：公钥+私钥。在人类目前的世界中，RSA算法可以说是最重要的算法之一，其应用非常广阔，在涉及到个人资产的金融领域、涉及网络安全的互联网领域、涉及军工秘密的军事安全领域，RSA都起到着主导的作用。那么这么牛的算法是如何诞生的呢？
上篇文章描述过对称加密，这个算法有个非常致命的问题就是加密者与解密者使用同一把秘钥，那么秘钥的保存与传递是个非常大的挑战，基于此天才们进行了伟大的构想，并且付诸实践。
❝1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。
❞
这种新的加密模式被称为非对称加密算法，它开创了加密学的新的时代！，并且由下面的三位大神发扬光大！
❝1977年，罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）共同提出RSA非对称加密算法。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的，直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。下面是三巨头的照片镇楼，话说三位还都是蛮帅的！
❞
1983年9月12日麻省理工学院在美国为RSA算法申请了专利。这个专利于2000年9月21日失效。由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认，所以在世界范围内被广泛使用，造福大众。
2.2 RSA算法的安全证明
许多公钥加密算法（RSA算法）都依赖于两个素数乘积的极大数。其他加密算法的安全性基于解决某些离散对数问题的难度。如果密钥足够长，则没有已知的方法可以破解它们提供的加密。对大数的分解和离散对数的计算破坏了给定密钥大小的加密保证，并迫使用户增加它所使用的熵位的数量。
事实上，「如果这个大数可以被因数分解，就意味着私钥被破解」。不过，大整数的因数分解是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。后面将会介绍，在RSA算法中因为公钥是两个数（E，N），如果可以对N进行快速的因式分解为两个质数，那么私钥（D，N）也就很容易破解了。但是目前典型密钥长度是2048位，破解这种密码需要最好的超级计算机用80年左右的时间。
❝维基百科这样写道："对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。「只要密钥长度足够长，用RSA加密的信息实际上是不能被破解的」。"
❞
这次的新记录包括「RSA-240」的分解。RSA-240密钥有240个十进制位，大小为「795 bits」。同一组研究人员还计算了同样大小的离散对数。
在此之前，人类破解的最长RSA密钥是2010年解开的RSA-768(尽管位数比RSA-240更小，有232个十进制位和768个二进制位)，以及2016年的768-bit素数离散对数的计算。
2.3 RSA算法秘钥生成
假设，Alice是秘钥（公钥+私钥）的生成者，并且单独与安全持有私钥；Bob持有Alice签发的公钥；
-
首先，随机生成两个不相同的质数P和Q（尽量大些，防止太弱容易被暴力破解）；
Alice随机选择两个素数，比如P=3，Q=11（实际应用中，P和Q要尽量大，防止被轻易的暴力破解）
-
然后，计算P和Q的乘积N。（N的二进制的位数就是RSA秘钥的长度，从安全性来说建议2048及以上较为稳妥）；
计算P和Q的乘积Q，3 * 11 = 33，则N=33
-
然后，计算N的欧拉函数φ(N)，由上章可知，一个数可以因式分解为两个素数，那么其欧拉函数为 ；
φ(N) = （p-1）*（q-1） = 20
-
然后，随机选择一个整数E，条件：1 < E < φ(N)，且E与φ(N)互质；
在1到20之间选择整数E=3，并且3与20互质
-
最后，计算E对于φ(N)的模反元素D；
由于7乘以3除以20余1，所以D选择7（也可以选择27，47，67等）
-
公钥与私钥的生成，封装（E，N）为公钥e，封装（D，N）为私钥d，并且Alice将公钥e（E，N）传递给Bob，私钥d（D，N）自己安全的妥善保存，不透漏给任何人。
Alice持有私钥（7，33），Bob持有公钥（3，33）
2.4 RSA算法交互流程
上面描述了RSA算法的机制，下面描述下具体的使用流程，帮助大家更好的理解。
-
Bob使用公钥加密，公钥是（3，33）,Bob要向Alice发送加密信息k，需要使用爱丽丝的公钥 (E,N) 对k进行加密，k加密后的信息是l，并且将l发送给Alice。这里需要注意，k必须是整数（字符串可以取ascii值或unicode值），且k必须小于n。
加密公式如下
❝❞
（式1）
假设k=2，则
❝❞
（式2）
那么，Bob将l=8传递给Alice；
-
Alice收到Bob发送的加密数据l，并且使用私钥解密，私钥是（7，33），流程如下：
解密公式如下
❝❞
（式3）
将c=8代入
❝❞
（式4）
-
至此，Alice已经解密出Bob发出的密文k是2，整个加密与解密流程验证完毕。
这个例子里面的选取的质数P和Q都相对简单，只是和大家分享下实际的流程如何运转，正如在上面的《2.2节 RSA算法的安全证明中》介绍的一样，在工业环境下，一般都会选择比较大的素数，N的二进制大小就是秘钥的长度，基本选择2048及以上才比较安全，下面介绍下为啥大的素数是比较安全的？
❝❞
Bob已知公钥（E，N），Bob想要破解这个秘钥的话，需要知道私钥（D，N）
因为ED ≡ 1 (mod φ(N))。只有知道e和φ(n)，才能算出d。
因为φ(N)=(P-1)(Q-1)。只有知道P和Q，才能算出φ(N)。
因为N=PQ。只有将N因数分解，才能算出P和Q。
前面2.2节介绍过：维基百科这样写道："对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。「只要密钥长度足够长，用RSA加密的信息实际上是不能被破解的」。"
2.5 RAS加密与解密的证明
下面我们证明下，为何用私钥解密l，一定可以正确地得到原始的数据k。也就是证明下面的「解密公式」：
❝❞
（式1）
-
首先，根据加密公式
❝❞
（式2）
-
然后，l可以写成下面的形式：
❝❞
，J为正整数 （式3）
-
然后，将l代入解密公式：
❝❞
（式4）
-
然后进行公式分解，则等同于推导
❝❞
（式5）
-
然后，由于E和D是关于φ(N)的模反元素
❝❞
（式6）
（式7）
-
然后，将ED代入式5， 则需要证明公式如下
❝❞
（式8）
「接下来，分成两种情况证明上面这个式子。」
「1. k与N是互质关系，推导如下。」
❝根据欧拉定理，此时
❞
（式9） （式10）， 由前面可知，k小于N，故式8成立。
故证明成立。
「2. k与N不是互质关系，推导如下。」
❝❞
因为N等于质数P和Q的乘积，k与N不互质，所以k必然等于CP或CQ（C是正整数）。以 k = CP为例（k小于N），则k与Q必然互质，则根据欧拉定理
（式11）（假设正整数a与质数p互质，因为质数p的φ(p)等于p-1）
(式12）
(式13）
(式14） （G是正整数）
(式15） （G是正整数，且G可以被P整除，则分解为 ）
最后，因为k=CP，N=PQ，则
（式16），由前面可知，k小于N，故式8成立。
故证明成立。
3 未完待续
至此，RSA加密算法推导与证明介绍完毕，后续章节将继续介绍RSA的应用场景TLS/SSL、数字证书与数字签名等。
4 参考资料
5 番外篇
❝个人介绍：杜宝坤，隐私计算行业从业者，从0到1带领团队构建了京东的联邦学习解决方案9N-FL，同时主导了联邦学习框架与联邦开门红业务。框架层面：实现了电商营销领域支持超大规模的工业化联邦学习解决方案，支持超大规模样本PSI隐私对齐、安全的树模型与神经网络模型等众多模型支持。业务层面：实现了业务侧的开门红业务落地，开创了新的业务增长点，产生了显著的业务经济效益。个人比较喜欢学习新东西，乐于钻研技术。基于从全链路思考与决策技术规划的考量，研究的领域比较多，从工程架构、大数据到机器学习算法与算法框架均有涉及。欢迎喜欢技术的同学和我交流，邮箱：[email protected]
❞
一切有为法，如梦幻泡影，如露亦如电，应作如是观