笔记分享 | 组队学习密码学（1）——密码学与MPC基础

基础概念

1.1 对称加密

首先双方在安全的信道上共享一个对称密钥Key，然后发送方使用这个Key对数据X进行加密，产生一个密文Y。这个Y就可以在任意信道上传输，因此Y可以被攻击者也可以叫做密码分析人员获得，他们可以解析出是 和 。接收方获得Y之后，他可以通过Key解密获得X。因此如果一个密码算法足够安全，是要求黑客攻击者获得了Y仍然不能够解密获得Key。

1.2 哈希函数

哈希函数非常的简单，将任意一个很长的数据或者是很短的数据映射为一个固定长256 bit的数据，如果数据特别短怎么办？直接补0。下面是哈希函数的6个关键性质：

1.3 素数群

群是一个集合，这个集合需要满足以下6个条件：

群的两个关键概念：

概念1：如果群元素g能够通过有限次本身运算，表达群内其他元素，则称为群的生成元。

概念2：群内元素个数称为群的阶

1.4 椭圆曲线群

椭圆曲线群跟素数群非常的相似，对外的表达还是群的6个性质，只不过它的内部运算原理发生了一点变化。

数字签名

本次活动介绍的是应用于比特币的ECDSA签名。数字签名的签名方用自己的私钥进行签名，那些验证方就会用签名方的公钥对它进行校验，也叫做验证。

私钥一般是一个随机数，它的公钥就是。所以已知y和g，如果想要把它的指数x搜出来需要指数时间才能完成，这是不可行的。所以已知私钥能够快速计算公钥，已知公钥计算私钥的难度会非常大，可能需要100年的时间。

根据上图中的签名过程，计算逆元的过程是比较简单的，我们可以快速得到R，再通过哈希函数得到r，模运算后我们可以得到签名（r,s）。而验证过程，其他验证方只需要公钥就可以快速验证，只要R`=R，则验证成功。

公钥加密

基于素数群的ElGamal加密：发送方使用对方的公钥加密数据，那么接收方接收到数据的时候就会使用自己的私钥解密数据。

第一种加密方式，我们需要将消息编码为群元素再进行操作，因为编码为群元素了之后消息 m 才可以和群元素进行运算，这里叫做乘法运算。 

第二种加密方式，如果消息m就是一个256bit长度的随机数，就需要进行哈希操作，让变为群元素。

基于椭圆曲线群的ElGamal加密和基于素数群的ElGamal加密高度相似：

不经意传输协议

Alice 有两个数据， A0 和A1， Bob 有一个选择比特位 r = 0 或者 r = 1，这个是协议的输入。Alice 输入两个数据， Bob 输入 1 bit 的 r ，是协议运行之后有一个结果， Bob 获得这个Ar，然后 r 等于0 它就获得了A0。r 等于1，它就获得了A1， Bob 不能够获得两个数据。Alice 不知道 Bob 获得了哪个，只知道他一定获得了其中一个。

百万富翁问题与混淆电路

假设百万富翁是Alice和Bob， Alice 和 Bob 要进行一个两方运算，算法是f，然后需要构建一个与或非的门，构造出一个布尔电路。

混淆电路主要包括4个步骤：

第一步：Alice生成混淆电路

（1）生成与门逻辑电路的真值表，并且对于真值表按照与门进行计算标注

（2）将真值表中的值替换为随机数（隐藏一一映射表，隐藏真实值）

（3）使用替换值进行2次AES加密

（4）对加密结果顺序打乱，就是混淆表。混淆表内容和行号无关。就是混淆二字的由来。

第二步：Alice发送混淆表与相关数据

（1）Alice发送自己的输入值对应的替换值给Bob

（2）Bob通过不经意传输协议，从Alice那里获得他需要的的输入的替换值

（3）Alice发送与门的混淆表

第三步：Bob混淆表2次AES解密

第四步：Alice和Bob共享结果

Paillier同态加密及其应用

Paillier同态性在哪里？两个密文做密文加法运算，叫做密文抽象加。密文抽象加如何加？实际上就叫做两个密文直接相乘，把加法关系带进公式。

素性测试

小伙伴们可以点击 “在看” 并分享，公众号后台回复20230410，即可获得完整版PDF笔记《OpenMPC社区讲座：密码学与MPC基础》

往期推荐