现代密码学(第六章)资料.ppt

第六章：密码技术应用 一、秘密共享 二、不经意传输 三、电子投票 四、零知识证明 五、电子现金支付 一、秘密共享 “海盗分割藏宝图”是秘密共享方案的原始模型。 设共有n个海盗有权参加宝物分配。为了防止独吞或联手作弊，规定：t个人以上同时到场才能找到宝物，而t-1个人以下同时到场是不能找到宝物的。 恰当地分割藏宝图就是解决这个问题的有效方法。在这里，一个秘密被分成了n份，任何t份并在一起，都能复原秘密。 t被称为门限值。 t≤ n。 一、秘密共享 秘密共享方案有多种用途。比如： 遗产的分配与公证。 多用户通信。 电子商务中的各种交易方案。 重大决策的控制阀（如核按钮等）。 一、秘密共享 例：一个最简单的秘密共享方案 设保险柜有三把锁，分别编号为①、②、③。 张三拥有①、②号锁的钥匙。 李四拥有①、③号锁的钥匙。 王五拥有②、③号锁的钥匙。 三个人中，任何两个以上的人同时到场均可以打开保险柜；任何一个以下的人到场均打不开保险柜。 此处，一个秘密指的是“①、②、③号锁的钥匙”；n=3（个人）；门限值t=2 （个人）。 一、秘密共享 Shamir的秘密共享门限方案 选择一个大素数p。 选择一个t-1次的整系数多项式h(x)： 一、秘密共享 设一共有n个参与者。 设第k位参与者拥有的公开身份名是ID(k)，其中ID(k)是整数。 设第k位参与者拥有的秘密身份名是h(ID(k))。此处k=1, 2, 3, …, n。 多项式h(x)对所有参与者保密。换句话说，多项式h(x)的系数{a0, a1, a2, …, at-2, at-1}对所有参与者保密。 第k位参与者拥有（ID(k)，h(ID(k))）。其中ID(k)对其他参与者公开，h(ID(k))对其他参与者保密。此处k=1, 2, 3, …, n。 一、秘密共享 多项式h(x) （即多项式h(x)的系数{a0, a1, a2, …, at-2, at-1}） 就是n个参与者所共享的秘密。任何t个人以上同时到场，每个人交出自己的身份名（ID(k)，h(ID(k))），拼在一起，就能计算出h(x)。任何t-1个人以下同时到场，每个人交出自己的身份名（ID(k)，h(ID(k))），拼在一起，则不能计算出h(x)。以下详细说明。 一、秘密共享 不失一般性,不妨设第1位~第t位参与者同时到场，每个人交出自己的身份名： （ID(k)，h(ID(k))）， k=1, 2, 3, …, t。 于是得到了如下的方程组：对于k=1, 2, 3, …, t， 一、秘密共享 即 一、秘密共享 这是一个关于未知系数 {a0, a1, a2, …, at-2, at-1} 的t元一次方程组（请注意，是模(modp)运算的t元一次方程组），有t个方程，因此容易解出{a0, a1, a2, …, at-2, at-1}。 当任何t-1个人以下同时到场，每个人交出自己的身份名（ID(k)，h(ID(k))），则获得了关于未知系数的t元一次方程组，有t-1个以下方程，因此无法唯一地确定h(x)。 一、秘密共享 在Shamir秘密共享方案中 检测“欺骗者” 设有t+1个以上参与者同时到场。其中有一个参与者是“欺骗者”Eve，他出示的是身份名（ID(k)，h(ID(k))）是假的。 设任何t个诚实的参与者组合在一起，计算出h(x)的系数向量都是真实的{a0, a1, a2, …, at-2, at-1}。 设Eve与某t-1个诚实的参与者组合在一起，计算出h(x)的系数向量是{a0’, a1’, a2’, …, at-2’, at-1’}。 设Eve与另外t-1个诚实的参与者组合在一起，计算出h(x)的系数向量是 {a0”, a1”, a2”, …, at-2”, at-1”}。 一、秘密共享 由于Eve难以由自己的所谓ID(k)求出对应的h(ID(k))，因此他的所谓身份名（ID(k)，h(ID(k))）很难成为“配套的”。 因此， {a0, a1, a2, …, at-2, at-1}， {a0’, a1’, a2’, …, at-2’, at-1’}， {a0”, a1”, a2”, …, at-2”, at-1”}， 三个系数向量中的任何两个向量都很难相互相等。 一、秘密共享 检测结论（一） 当某t个参与者组合计算出的系数向量与另外t个参与者组合计算出的系数向量不相等时，这两次被组合的全部人员中必有“欺骗者”。 检测结论（二） 当某t个参与者组合计算出的系数向量与另外t个参与者组合计算出的系数向量相等时，（几乎可以断定）这两次被组合的全部人员都是诚实的参与者。 一、秘密共享 习题 设：p=17；n=5；t=3； (ID(1), h(ID(1)))=(1, 8)； (ID(2), h(ID(2)))=(2, 7