0x00 系列开始
最近本鹅在学习多方安全计算，为了记录自己学习过程，梳理思路，计划模仿结城浩大佬的《图解密码学》的风格，写写一个菜鸡学习多方安全计算的笔记。
0x01 OT是个什么鬼
维基百科词条里写到：不经意传输（英语：Oblivious transfer）是密码学中的一类协议，实现了发送方将潜在的……
(打住打住，教程不是这样开始的)
故事的开始，是关于 你 和 你亲爱的室友周格林的。
周格林是你们年级的Social King，今天周格林答应你给你旁边社团一个帅气小哥哥/漂亮小姐姐的联系方式。但心黑的周格林作为室友，开出了一百块钱外加帮着带一周早饭的价码。同时，羞涩的你也并不想让周格林知道你心仪的那个TA具体是谁。
于是，这个问题变成了：
- 周格林手握一把微信好友联系方式，但是只能提供给你你需要的那一个人的联系方式
- 而你只需要那一个人的联系方式，同时却不能让周格林知道你到底选择了谁
如何解决这个困局呢？隆重请出今天故事的主角 —— OT(Oblivious transfer 不经意传输)
不经意传输的作用，便是解决了上面的一个困局：发送方（周格林）提供若干条信息的选项，接收方（你）选择其中一条信息；OT保证了接收方（你）只能获得你选择的那条信息，而发送方（周格林）无法知道你选择了哪一条消息。我们一般使用$ _{n}^{1}\textrm{OT} $ （n选1 OT）来表示这种从n条消息里选择一条的操作。
上面的图示，表示的便是周格林向OT输入了一堆人对应的微信号（$ X_0 $, $ X_1 $, $ X_2 $ …… ），从获得的一堆标签中，你向OT输入了你选择的小哥哥/小姐姐的代号（b），而最终你得到了心仪的TA的联系方式（$ X_b $）
0x02 如何实现一个最简单的2选1 OT
上面讲了OT的定义，下一步就是看看数学上是如何实现一个2选1 OT的了。作者表示，我们这种实现方式就是最简单的OT实现方式：The Simplest Protocol for Oblivious Transfer。
不过，为了介绍清楚整个过程中的一些运算，我们需要先插入一些小学二年级的数论知识：
时钟运算
这里我们不涉及复杂的数论定理和证明，我们借用《图解密码技术》里的内容讲解一下背景知识。
加法
先想象一个没有分针、秒针，只有时针的时钟：
在这个时钟里面，我们往右转动了一下时钟的时针，时钟从0指向1，表示加了1。继续加下去，从2、3……一直到了刻度11，再加1就又回到了0，也就是说这个时钟上是只有0到11的，我们在这个时钟里所有运算的结果，都只会是0到11之间的数字。
例如，我们让7加上7，也就是时针在7的位置再向右拨7个数字，此时的结果是14吗？并不，表盘转了一圈会回到0，所以此时的结果是2。
计算方法是：
（7 + 7）÷ 12 = 1 余 2
我们为“除一个数的余数”定义一个符号，叫做 “mod” 。而上面的运算就可以表示为：
（7 + 7）mod 12 = 2
所以，在时钟运算上的所有运算都落在时钟上面数字的区间内，加法对应的是 加和后的结果求余数
减法
减法运算中，我们很容易想到，既然减法是加法的逆运算，则需要减去多少数字，我们把表盘往左拨动多少个数就好了。
但在钟表运算中，我们暂且规定时钟只能向右转动，那不能向左逆时针拨动的钟表，如何才能得到正确的结果呢？
比如，还是时针指向7，我们现在需要减去7才能让时针回到0，但是不能向逆时针方向拨动，只能继续顺时针向前转，需要转多少个数才能回到0呢？
我们可以看到，再转动5个格就可以让时针回到0了，所以5这个数字，在时针表盘上的运算中，发挥的作用和 -7 是一样的，因为逆时针拨动7个数字，相当于顺时针拨动了5个数字。
所以，针对表盘上的减法运算，有：
| X | Y |
|---|---|
| 0 | 0 |
| -1 | 11 |
| -2 | 10 |
| -3 | 9 |
| -4 | 8 |
| -5 | 7 |
| -6 | 6 |
| -7 | 5 |
| -8 | 4 |
| -9 | 3 |
| -10 | 2 |
| -11 | 1 |
这样一张表，X列对应的操作，可以通过加Y列实现
乘法
乘法运算作为加法运算的衍生运算，相当于多次做加法。比如求7×4的结果，也就是求 7+7+7+7 的结果。而在时钟上，由于每转过一圈时钟都回到了原点，所以时钟运算的乘法需要最后再做个求余运算：
(7×4) mod 12 = 28 mod 12 = 4
除法
乘方
总结
总结下来，我们下面的OT推导过程中，需要用到的结论包括如下几条（可以下面推倒过程中用到的时候再回来看）：
- 已知g、a，求 $ g^{a} mod: p $ 是一个比较简单的问题，而在知道 $ g^{a} mod: p $ 结果和g的情况下要反推a是多少，在目前的技术下是个很难的问题
- g的a次方求除p的余数 再做b次方运算的结果，是等于g求(a × b)次方再求除p的余数，用公式来表示是：
$ \left (g^{a} mod: p \right )^{b}= g^{ab} mod: p $
补充知识结束，回到我们构造OT的施工现场。
我们先看一下全部的流程图：
下面具体讲解一下我们的步骤：
扩展知识：
看完整个交换步骤，熟悉D-H秘钥交换（Diffie–Hellman key exchange）的同学已经发现了，这个步骤其实和D-H秘钥协商的机制是差不多的，如果大家感兴趣，可以去研究下 D-H秘钥交换 是如何在不交换任何秘钥内容的情况下在参与秘钥交换的两方之间协商出一个相同的加密秘钥来的。
0x03 带上数字试试
0x04 怎么能更给力一点呢？
整个过程轻松愉快，但是有一个很严重的问题，每次传输数据都需要先进行一堆的大数的N次方运算，实在是太慢了，有没有办法能优化一下整个流程让传输变得快一点呢？
下一篇，我们将使用ROT（random OT, 随机OT）让我们的每次传输变得快一点。
参考资料
- [1] 结城浩 图解密码技术
- [2] 整数模n乘法群 https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E6%A8%A1n%E4%B9%98%E6%B3%95%E7%BE%A4