Oblivious Transfer (OT) 协议详解<\/h1>

一、基本概念<\/h2>

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

Bob只能获取Alice提供的部分信息（而非全部）<\/li>

Alice不知道Bob具体获取了哪些信息<\/li> <\/ol>

二、协议类型<\/h2>

1. OT₁²（1-out-of-2 OT）<\/h3>

Alice有两条消息 m₀ 和 m₁<\/li>
Bob可以选择获取其中一条消息<\/li>

Alice不知道Bob选择了哪条消息<\/li> <\/ul>

2. OT₁ᴺ（1-out-of-N OT）<\/h3>

Alice有N条消息<\/li>
Bob可以选择获取其中一条消息<\/li>

Alice不知道Bob选择了哪条消息<\/li> <\/ul>

三、基于RSA的OT₁²实现<\/h2>

协议流程<\/h3>

初始化阶段<\/strong>：<\/p>

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

选择阶段<\/strong>：<\/p>

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

加密阶段<\/strong>：<\/p>

Alice计算：

k₀ = (v - x₀)ᵈ mod N<\/li>
k₁ = (v - x₁)ᵈ mod N<\/li> <\/ul> <\/li>
Alice加密消息：

m₀' = (m₀ + k₀) mod N<\/li>
m₁' = (m₁ + k₁) mod N<\/li> <\/ul> <\/li>
Alice将(m₀', m₁')发送给Bob<\/li> <\/ul> <\/li>

解密阶段<\/strong>：<\/p>

Bob计算 m_b = (m_b' - k) mod N<\/li>
Bob无法计算另一条消息，因为不知道另一个k值<\/li> <\/ul> <\/li> <\/ol>
安全性分析<\/h3>

Alice不知道b的值，因为：<\/p>

她只能看到v = x_b + kᵉ<\/li>
无法区分是x₀还是x₁被使用<\/li> <\/ul> <\/li>

Bob只能获取一条消息，因为：<\/p>

他只知道k，不知道d<\/li>
无法计算另一个k值<\/li> <\/ul> <\/li> <\/ol>
四、OT在CTF中的应用<\/h2>
案例1：OK - zer0pts CTF 2022<\/h3>
题目特点<\/strong>：<\/p>

基于OT-RSA协议<\/li>
结合最低位翻转攻击<\/li> <\/ul>
解题思路<\/strong>：<\/p>

构造v使得v - x₁ ≡ -(v - x₂) mod N<\/p>

解得：v = (x₁ + x₂)\/2 mod N<\/li> <\/ul> <\/li>

计算c₁ + c₂ = key + ciphertext mod N<\/p>

由于key ∈ (0, N)，可以判断是否超过N<\/li> <\/ul> <\/li>

利用关系C = M ⊕ K恢复M的比特：<\/p>

如果bit(M,i)=1，则bit(S,i)=1必须成立<\/li>
否则bit(M,i)=0<\/li> <\/ul> <\/li>

最后解单模数RSA获取flag<\/p> <\/li> <\/ol>
案例2：Decidophobia - idekCTF 2022<\/h3>
题目特点<\/strong>：<\/p>

扩展OT到三个秘密(p, q, r)<\/li>
需要分解n = pqr<\/li> <\/ul>
解题思路<\/strong>：<\/p>

构造v使得v - x₁ ≡ -(v - x₂) mod N<\/p>

得到s ≡ c₁ + c₂ ≡ p + q mod N<\/li> <\/ul> <\/li>

使用Coppersmith方法：<\/p>

构造多项式f(x) = (q_high × 2²⁵⁶ + (s - x))(x × 2²⁵⁶ + p_lower) mod N<\/li>
求解多项式的小根<\/li> <\/ul> <\/li> <\/ol>
五、实现代码示例<\/h2>
Alice端实现（Python）<\/h3>
from<\/span> pwn import<\/span> *<\/span> <\/span><\/span>import<\/span> logging <\/span><\/span>from<\/span> Crypto.Util.number import<\/span> *<\/span> <\/span><\/span> <\/span><\/span>def<\/span> rsa_keygen<\/span>(): <\/span><\/span> p =<\/span> getPrime(512<\/span>) <\/span><\/span> q =<\/span> getPrime(512<\/span>) <\/span><\/span> n =<\/span> p *<\/span> q <\/span><\/span> phi =<\/span> (p -<\/span> 1<\/span>)*<\/span>(q -<\/span> 1<\/span>) <\/span><\/span> e =<\/span> 65537<\/span> <\/span><\/span> d =<\/span> pow(e, -<\/span>1<\/span>, phi) <\/span><\/span> return<\/span> n, e, d <\/span><\/span> <\/span><\/span># 初始化<\/span> <\/span><\/span>server =<\/span> listen(55556<\/span>, bindaddr=<\/span>"127.0.0.1"<\/span>) <\/span><\/span>m0 =<\/span> 1234<\/span> # 第一条消息<\/span> <\/span><\/span>m1 =<\/span> 5678<\/span> # 第二条消息<\/span> <\/span><\/span> <\/span><\/span># 生成RSA密钥<\/span> <\/span><\/span>N, e, d =<\/span> rsa_keygen() <\/span><\/span> <\/span><\/span># 生成随机值<\/span> <\/span><\/span>x0 =<\/span> getRandomInteger(13<\/span>) <\/span><\/span>x1 =<\/span> getRandomInteger(13<\/span>) <\/span><\/span> <\/span><\/span># 发送公钥和随机值<\/span> <\/span><\/span>server.<\/span>send(f<\/span>"<\/span>{<\/span>N}<\/span>\n<\/span>{<\/span>e}<\/span>\n<\/span>{<\/span>x0}<\/span>,<\/span>{<\/span>x1}<\/span>\n<\/span>"<\/span>.<\/span>encode()) <\/span><\/span> <\/span><\/span># 接收v值<\/span> <\/span><\/span>v =<\/span> int(server.<\/span>recvline().<\/span>strip()) <\/span><\/span> <\/span><\/span># 计算k值<\/span> <\/span><\/span>k0 =<\/span> pow(v -<\/span> x0, d, N) <\/span><\/span>k1 =<\/span> pow(v -<\/span> x1, d, N) <\/span><\/span> <\/span><\/span># 加密消息<\/span> <\/span><\/span>m0_enc =<\/span> (m0 +<\/span> k0) %<\/span> N <\/span><\/span>m1_enc =<\/span> (m1 +<\/span> k1) %<\/span> N <\/span><\/span> <\/span><\/span># 发送加密后的消息<\/span> <\/span><\/span>server.<\/span>send(f<\/span>"<\/span>{<\/span>m0_enc}<\/span>\n<\/span>{<\/span>m1_enc}<\/span>\n<\/span>"<\/span>.<\/span>encode()) <\/span><\/span>server.<\/span>close() <\/span><\/span><\/code><\/pre>Bob端实现（Python）<\/h3> from<\/span> pwn import<\/span> *<\/span> <\/span><\/span>import<\/span> random as<\/span> rd <\/span><\/span> <\/span><\/span>client =<\/span> remote('127.0.0.1'<\/span>, 55556<\/span>) <\/span><\/span> <\/span><\/span># 接收Alice的公钥和随机值<\/span> <\/span><\/span>N =<\/span> int(client.<\/span>recvline()) <\/span><\/span>e =<\/span> int(client.<\/span>recvline()) <\/span><\/span>x0, x1 =<\/span> map(int, client.<\/span>recvline().<\/span>split(','<\/span>)) <\/span><\/span> <\/span><\/span># Bob的选择<\/span> <\/span><\/span>choice =<\/span> input('Choose 0 or 1: '<\/span>) <\/span><\/span>x_b =<\/span> x0 if<\/span> choice ==<\/span> '0'<\/span> else<\/span> x1 <\/span><\/span> <\/span><\/span># 生成随机k<\/span> <\/span><\/span>k =<\/span> rd.<\/span>randint(1000<\/span>, 10000<\/span>) <\/span><\/span> <\/span><\/span># 计算并发送v<\/span> <\/span><\/span>v =<\/span> (x_b +<\/span> pow(k, e, N)) %<\/span> N <\/span><\/span>client.<\/span>send(f<\/span>"<\/span>{<\/span>v}<\/span>\n<\/span>"<\/span>.<\/span>encode()) <\/span><\/span> <\/span><\/span># 接收加密消息<\/span> <\/span><\/span>m0_enc =<\/span> int(client.<\/span>recvline()) <\/span><\/span>m1_enc =<\/span> int(client.<\/span>recvline()) <\/span><\/span> <\/span><\/span># 解密选择的消息<\/span> <\/span><\/span>m =<\/span> (m0_enc -<\/span> k) %<\/span> N if<\/span> choice ==<\/span> '0'<\/span> else<\/span> (m1_enc -<\/span> k) %<\/span> N <\/span><\/span>print(f<\/span>"Decrypted message: <\/span>{<\/span>m}<\/span>"<\/span>) <\/span><\/span> <\/span><\/span>client.<\/span>close() <\/span><\/span><\/code><\/pre>六、安全注意事项<\/h2> 随机数生成必须加密安全<\/li> 模数N必须足够大（通常≥2048位）<\/li> 实现中要注意防止时序攻击<\/li> 在实际应用中应考虑使用更高效的OT实现（如基于椭圆曲线的OT）<\/li> <\/ol> 七、应用场景<\/h2> 安全多方计算<\/li> 隐私保护的数据查询<\/li> 电子投票系统<\/li> 匿名通信系统<\/li> 加密货币中的隐私保护交易<\/li> <\/ol> OT协议作为密码学基础构件，在现代密码学中扮演着重要角色，理解其原理和实现对于深入密码学和网络安全领域至关重要。<\/p>