Oblivious Transfer (OT) 协议详解

一、基本概念

Oblivious Transfer（茫然传输，简称OT）是一种密码学协议，允许发送方（Alice）向接收方（Bob）传输信息，同时满足以下两个关键特性：

1. Bob只能获取Alice提供的部分信息（而非全部）
2. Alice不知道Bob具体获取了哪些信息

二、协议类型

1. OT₁²（1-out-of-2 OT）

• Alice有两条消息 m₀ 和 m₁
• Bob可以选择获取其中一条消息
• Alice不知道Bob选择了哪条消息

2. OT₁ᴺ（1-out-of-N OT）

• Alice有N条消息
• Bob可以选择获取其中一条消息
• Alice不知道Bob选择了哪条消息

三、基于RSA的OT₁²实现

协议流程

1. 初始化阶段：

   • Alice生成RSA密钥对：(N, e, d)
   • Alice生成两个随机值 x₀ 和 x₁
   • Alice将(N, e, x₀, x₁)发送给Bob

2. 选择阶段：

   • Bob选择b ∈ {0,1}（决定获取哪条消息）
   • Bob选择对应的x_b
   • Bob生成随机数k
   • 计算 v = (x_b + kᵉ) mod N
   • Bob将v发送给Alice

3. 加密阶段：

   • Alice计算：
     • k₀ = (v - x₀)ᵈ mod N
     • k₁ = (v - x₁)ᵈ mod N
   • Alice加密消息：
     • m₀' = (m₀ + k₀) mod N
     • m₁' = (m₁ + k₁) mod N
   • Alice将(m₀', m₁')发送给Bob

4. 解密阶段：

   • Bob计算 m_b = (m_b' - k) mod N
   • Bob无法计算另一条消息，因为不知道另一个k值

安全性分析

1. Alice不知道b的值，因为：

   • 她只能看到v = x_b + kᵉ
   • 无法区分是x₀还是x₁被使用

2. Bob只能获取一条消息，因为：

   • 他只知道k，不知道d
   • 无法计算另一个k值

四、OT在CTF中的应用

案例1：OK - zer0pts CTF 2022

题目特点：

• 基于OT-RSA协议
• 结合最低位翻转攻击

解题思路：

1. 构造v使得v - x₁ ≡ -(v - x₂) mod N

   • 解得：v = (x₁ + x₂)/2 mod N

2. 计算c₁ + c₂ = key + ciphertext mod N

   • 由于key ∈ (0, N)，可以判断是否超过N

3. 利用关系C = M ⊕ K恢复M的比特：

   • 如果bit(M,i)=1，则bit(S,i)=1必须成立
   • 否则bit(M,i)=0

4. 最后解单模数RSA获取flag

案例2：Decidophobia - idekCTF 2022

题目特点：

• 扩展OT到三个秘密(p, q, r)
• 需要分解n = pqr

解题思路：

1. 构造v使得v - x₁ ≡ -(v - x₂) mod N

   • 得到s ≡ c₁ + c₂ ≡ p + q mod N

2. 使用Coppersmith方法：

   • 构造多项式f(x) = (q_high × 2²⁵⁶ + (s - x))(x × 2²⁵⁶ + p_lower) mod N
   • 求解多项式的小根

五、实现代码示例

Alice端实现（Python）

from pwn import *
import logging
from Crypto.Util.number import *

def rsa_keygen():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p - 1)*(q - 1)
    e = 65537
    d = pow(e, -1, phi)
    return n, e, d

# 初始化
server = listen(55556, bindaddr="127.0.0.1")
m0 = 1234  # 第一条消息
m1 = 5678  # 第二条消息

# 生成RSA密钥
N, e, d = rsa_keygen()

# 生成随机值
x0 = getRandomInteger(13)
x1 = getRandomInteger(13)

# 发送公钥和随机值
server.send(f"{N}\n{e}\n{x0},{x1}\n".encode())

# 接收v值
v = int(server.recvline().strip())

# 计算k值
k0 = pow(v - x0, d, N)
k1 = pow(v - x1, d, N)

# 加密消息
m0_enc = (m0 + k0) % N
m1_enc = (m1 + k1) % N

# 发送加密后的消息
server.send(f"{m0_enc}\n{m1_enc}\n".encode())
server.close()

Bob端实现（Python）

from pwn import *
import random as rd

client = remote('127.0.0.1', 55556)

# 接收Alice的公钥和随机值
N = int(client.recvline())
e = int(client.recvline())
x0, x1 = map(int, client.recvline().split(','))

# Bob的选择
choice = input('Choose 0 or 1: ')
x_b = x0 if choice == '0' else x1

# 生成随机k
k = rd.randint(1000, 10000)

# 计算并发送v
v = (x_b + pow(k, e, N)) % N
client.send(f"{v}\n".encode())

# 接收加密消息
m0_enc = int(client.recvline())
m1_enc = int(client.recvline())

# 解密选择的消息
m = (m0_enc - k) % N if choice == '0' else (m1_enc - k) % N
print(f"Decrypted message: {m}")

client.close()

六、安全注意事项

1. 随机数生成必须加密安全
2. 模数N必须足够大（通常≥2048位）
3. 实现中要注意防止时序攻击
4. 在实际应用中应考虑使用更高效的OT实现（如基于椭圆曲线的OT）

七、应用场景

1. 安全多方计算
2. 隐私保护的数据查询
3. 电子投票系统
4. 匿名通信系统
5. 加密货币中的隐私保护交易

OT协议作为密码学基础构件，在现代密码学中扮演着重要角色，理解其原理和实现对于深入密码学和网络安全领域至关重要。