什么是Oblivious Transfer协议-先知社区

Oblivious Transfer

简述：OT能做什么

想象你走进了一家神秘的魔法商店，店主拥有两本神秘魔法书

和

，但你只能获得其中一本的内容，而店主不会知道你选的是哪一本。这时，店主提供了一种特殊的交易方式，让你在

不泄露你的选择

的情况下，安全地拿到你想要的魔法书。

神秘的交易规则

●

你向店主提供一张特殊的魔法卷轴，这张卷轴含有一些神秘符文，使得

店主可以给你一本书的内容，但他不知道你想要的是 A 还是 B

。

●

店主在你的卷轴上施展魔法，让它承载

一本书的内容

，但他

无法知道你的选择

。

●

你拿到卷轴后，使用你的魔法解读它，成功获得

你想要的那本书

，但你无法解读另一种书的信息。

这个神秘的交易规则也就是OT协议的核心思想，

加密魔法卷轴

= OT 协议，可以在密码学中用于保护选择的隐私，同时确保数据安全

可供选择两条信息的OT协议记为

非法 TeX 公式

，可供选择n条消息的OT协议记为

非法 TeX 公式

OT的实现方式不止一种，本文主要介绍的是基于RSA的OT协议的实现方式

Oblivious Transfer by RSA

定义：

非法 TeX 公式

definition from

WIKI

A有两条消息

非法 TeX 公式

，A想要发送其中一条给B。B不希望A知道他收到的是哪一条。

A生成一个 RSA 密钥对，包括模数N, 公钥指数e 和私钥指数d。

A还生成两个随机值

非法 TeX 公式

并将其与她的公钥模数和指数一起发送给B。

B选择b为 0 or 1，并选择

非法 TeX 公式

。

B 生成一个随机值k ，用它来盲化

非法 TeX 公式

，通过计算

非法 TeX 公式

,然后将其发送给A。

爱丽丝将 v 与她的两个随机值相结合，生成：

非法 TeX 公式

和

非法 TeX 公式

。现在

非法 TeX 公式

将等于

非法 TeX 公式

,另一个将是一个无意义的随机值。然而，由于A不知道B选择的

非法 TeX 公式

的值，她无法确定

非法 TeX 公式

和

非法 TeX 公式

中哪一个等于

非法 TeX 公式

。

她将两个秘密信息与每个可能的密钥

非法 TeX 公式

和

非法 TeX 公式

相结合，并将它们都发送给B。

B 知道 k，因此他能够计算出

非法 TeX 公式

。然而，由于他不知道

非法 TeX 公式

,他无法计算出

非法 TeX 公式

,因此无法确定

非法 TeX 公式

。

实验：

根据以上的定义，下面给出我基于python 的 pwntools库写的A，B端完整的协议流程代码，希望可以帮助读者更清晰的了解整个协议过程。

实验结果如下：

我们可以看到B成功可以获得指定索引的消息，而A不会泄露B不需要的消息。

非法 TeX 公式

基于RSA公钥算法实现的 n 选 1的OT协议流程可以由下图清晰的呈现出来

ctf challenge

下面我们来看下OT在CTF中的实战，通常题目设置不会单一考察OT这一个知识点，且对OT的考察也不局限于基本概念，会更加的灵活。

OK - zer0pts CTF 2022

关键考点：OT-RSA，最低位翻转

题目：

分析：

首先分析一下题目，主程序加密逻辑：

●

非法 TeX 公式

并取它最近的素数（即

非法 TeX 公式

)

●

非法 TeX 公式

●

以

非法 TeX 公式

为单模数计算

非法 TeX 公式

●

生成随机 key，并计算：

非法 TeX 公式

●

生成随机数 x1、x2，要求输入 v

●

计算：

非法 TeX 公式

●

打印：

非法 TeX 公式

●

要求还原 flag

比较明显的是一个Oblivisous Tran,sfer by RSA，我们通过构造不同的

非法 TeX 公式

输入，会得到

非法 TeX 公式

假设我们想得到key，就需要构造

非法 TeX 公式

（k是随机数） ,这样可以就得到

非法 TeX 公式

（ciphertext同理），我们只能传递一次参数v，所以这样的构造只能key和ciphertext二选一。但是我们需要计算

非法 TeX 公式

，所以只能选其他的构造方式

step1:构造v

我们希望构造的v 满足：

非法 TeX 公式

化简为：

非法 TeX 公式

将

非法 TeX 公式

带入

非法 TeX 公式

，再将其带入

非法 TeX 公式

，计算

非法 TeX 公式

的和

这样可以得到：

非法 TeX 公式

step2：解M

为了描述方便，这里统一设

非法 TeX 公式

为

非法 TeX 公式

，设

非法 TeX 公式

为

非法 TeX 公式

，

非法 TeX 公式

为

非法 TeX 公式

。

由题：

非法 TeX 公式

所以

非法 TeX 公式

的和可以表示为：

非法 TeX 公式

我们得到的

非法 TeX 公式

有一个

非法 TeX 公式

干扰，我们想办法把它去掉

我们发现

非法 TeX 公式

，所以

非法 TeX 公式

，假设当

非法 TeX 公式

为奇数（即最低位为1）的时候,

非法 TeX 公式

一定是奇数，所以如果

非法 TeX 公式

也是奇数，那么可以得出：

非法 TeX 公式

反之当

非法 TeX 公式

不是奇数：

非法 TeX 公式

然后我们可以来恢复

非法 TeX 公式

的比特，根据真值表*（简单枚举四种情况便可以得出这个结论成立）可以得出如果

非法 TeX 公式

，那么有

非法 TeX 公式

，也就是说

非法 TeX 公式

必须成立，否则

非法 TeX 公式

.这样就可以恢复出

非法 TeX 公式

最后解一个单模数的RSA(

非法 TeX 公式

)便可以得到flag的值

exp:

**Decidophobia-**idekCTF 2022

题目：

分析：

step1：构造v （lv2）

题目很长，但是读一读就能发现这其实是个比较有意思的小故事啦，提炼一下有效信息有：

Oblivious Transfer 生成

非法 TeX 公式

三个随机数，需要传回一个

非法 TeX 公式

，计算并返回：

非法 TeX 公式

还有：

非法 TeX 公式

n需要被分解，但是传入

非法 TeX 公式

只能得到

非法 TeX 公式

中的一个，没有办法完全分解

非法 TeX 公式

。

类比上一题的思想，也就是利用

非法 TeX 公式

，通过发送两个相应随机数的中间值求和的思想，应用到这道题来说，就是

非法 TeX 公式

，上一题由分类讨论消去模

非法 TeX 公式

的作用，这里由于

非法 TeX 公式

，所以模

非法 TeX 公式

直接不作用了。但是我们明显没有办法只通过

非法 TeX 公式

和

非法 TeX 公式

就分解n。

改进：

从上一道题可以得出更广义的结论：当

非法 TeX 公式

和

非法 TeX 公式

成线性关系的时候，可以得到秘密消息的线性关系。

我们假设：

非法 TeX 公式

可以有：

非法 TeX 公式

这里也要不让

非法 TeX 公式

，我们只需取

非法 TeX 公式

就可以获得一个

非法 TeX 公式

的

非法 TeX 公式

位信息

step2：Coppersmith

很明显需要需要用到Coppersmith来解了，

我们有了

非法 TeX 公式

的值，还可以写作：

非法 TeX 公式

我们考虑多项式：

非法 TeX 公式

用Coppersmith求解就可以了

exp：