精华内容
下载资源
问答
  • 双线性映射

    2020-04-17 18:34:45
    双线性映射 文章目录双线性映射1 离散对数系统1.1 指标1.2 离散对数(DLP)2 双线性映射3 Diffie-Hellman 问题(DHP)3.1 Diffie-Hellman 密钥交换3.2 q-Strong Diffie-Hellman(q-SDH) 1 离散对数系统 1.1 指标 ...

    双线性映射

    1 离散对数系统

    1.1 指标

    定义:设 pp 是一素数,aapp 的原本根,则 a,a2,,ap1a,a^2,\ldots,a^{p-1} 产生出的 1p11\thicksim p-1 之间所有的值,且每一值只出现一次,即对于 b{1,,p1}\forall b \in\{1,\ldots,p-1\} 都唯一存在 i(1ip1)i(1\leq i\leq p-1) ,使得 baimodpb\equiv a^i\:mod\:p 。称 ii 为模 pp 下以 aa 为底 bb 的指标,记作 i=inda,p(b)i=ind_{a,p}(b)

    性质:(1) inda,p(1)=0{ind}_{a,p}(1) = 0

    ​ (2) inda,p(a)=1{ind}_{a,p}(a) = 1

    定理:若 azapmodpa^z\equiv a^p\:mod\:p ,其中 pp 为素数,aapp 的原本根,则有 zqmodφ(p)z\equiv q\:mod\:\varphi(p)

    性质:(3)inda,p(xy)=[inda,p(x)+inda,p(y)]modφ(p){ind}_{a,p}(xy)=[{ind}_{a,p}(x)+{ind}_{a,p}(y)]\:mod\:\varphi(p)

    ​ (4)inda,p(yr)=[r×inda,p(y)]modφ(p){ind}_{a,p}(y^r)=[r\times{ind}_{a,p}(y)]\:mod\:\varphi(p)

    1.2 离散对数(DLP)

    pp 是一素数,aapp 的原本根,则 a,a2,,ap1a,a^2,\ldots,a^{p-1} 产生出的 1p11\thicksim p-1 之间所有的值,且每一值只出现一次,即对于 b{1,,p1}\forall b \in\{1,\ldots,p-1\} 都唯一存在 i(1ip1)i(1\leq i\leq p-1) ,使得 baimodpb\equiv a^i\:mod\:p 。称 ii 为模 pp 下以 aa 为底 bb 的离散对数,记作 iloga(b)(modp)i\equiv {log}_a(b)(mod\:p)

    apia、p、i 已知时,用快指数算法可以比较容易的=地求出 bb ,但是如果已知 aba、bpp ,求 ii 则非常困难。目前已知的最快的求离散对数算法的事件复杂度为: O(exp(lnp)13ln(lnp)23)O(exp(ln\:p)^{\frac{1}{3}}ln(ln\:p)^{\frac{2}{3}}) 所以当 pp 很大时,该算法也不可行。

    2 双线性映射

    qq 是一大素数,G1\mathbb{G}_1G2\mathbb{G}_2 是两个阶为 qq 的群,其上的运算分别为加法和乘法。G1\mathbb{G}_1G2\mathbb{G}_2 的双线性映射 e:G1×G1G2e:\mathbb{G}_1\times\mathbb{G}_1\rightarrow\mathbb{G}_2 ,满足下面的性质:

    (1)双线性:如果对任意 P,Q,RG1P,Q,R\in \mathbb{G}_1a,bZa,b\in Z ,有 e(aP,bQ)=e(P,Q)abe(aP,bQ)=e{(P,Q)}^{ab} ,或 e(P+Q,R)=e(P,R)(Q,R)e(P+Q,R)=e(P,R)\cdot(Q,R)e(P,Q+R)=e(P,Q)(P,R)e(P,Q+R)=e(P,Q)\cdot(P,R) ,那么就称该映射为双线性映射。

    (2)非退化性:映射不把 e:G1×G1e:\mathbb{G}_1\times\mathbb{G}_1 中所有元素对(即序偶)映射到 G2\mathbb{G}_2 中的单位元。由于 G1G2\mathbb{G}_1、\mathbb{G}_2 都是阶为素数的群,这意味着:如果 PPG1\mathbb{G}_1 的生成元,那么 e(P,P)e(P,P) 就是 G2\mathbb{G}_2 的生成元。

    (3)可计算性:对任意 P,QG1P,Q\in \mathbb{G}_1 ,存在一个有效算法计算 e(P,Q)e(P,Q)

    3 Diffie-Hellman 问题(DHP)

    3.1 Diffie-Hellman 密钥交换

    Diffie-Hellman 密钥交换过程,其中 pp 是大素数,aapp 的本原根,ppaa 作为公开的全程元素。用户A选择一个保密的随机整数 XAX_A ,并将 YA=aXAmodpY_A =a^{X_A}\:mod\:p 发送给用户B。类似的,用户B选择一个保密随机数 XBX_B ,并将 YB=aXBmodpY_B =a^{X_B}\:mod\:p 发送给用户A。然后A和B分别由 K=YBXAmodpK=Y_B^{X_A}\:mod\:pK=YAXBmodpK=Y_A^{X_B}\:mod\:p 计算出的就是共享密钥。

    因为 XA,XBX_A,X_B 是保密的敌手只能得到 p,a,YA,YBp,a,Y_A,Y_B ,想要得到 KK ,则必须得到 XA,XBX_A,X_B 中的一个,这意味着要解离散对数。因此求 KK 是不可行的。

    3.2 q-Strong Diffie-Hellman(q-SDH)

    假设 ggG\mathbb{G} 的生成元,aZpa\in\mathbb{Z}_p ,我们说如果给定 q+1q+1 元组 (g,ga,ga2,,gaq)(g,g^a,g^{a^2},\ldots,g^{a^q}) ,计算一个对 (g1/a+x,x)xZp(g^{1/{a+x}},x)\qquad x\in\mathbb{Z}_p^* 是困难的。

    展开全文
  • 粗浅的介绍了双线性映射的概念以及在现实生活中的应用
  • 包含gmp-6.1.2和pbc-0.5.14.2018年12月28日的最新版,用于构造双线性映射
  • 密码学:双线性映射

    万次阅读 2018-08-13 10:43:57
    双线性映射(双线性配对):...理解:若B:V×W→X是一个双线性映射,则V固定,W可变时,W到X的映射是线性的,W固定,V可变时,V到X的映射也是线性的,也就是说保持双线性映射中的任意一个参数固定,另一个参数对X的...

    ##密码学常用数学基础,需要了解

    双线性映射(双线性配对):Bilinear Pairing

    定义:一个双线性映射是由两个向量空间上的元素,生成第三个向量空间上一个元素之函数,并且该函数对每个参数都是线性的。

    理解:B:V×WX是一个双线性映射,则V固定,W可变时,W到X的映射是线性的,W固定,V可变时,V到X的映射也是线性的,也就是说保持双线性映射中的任意一个参数固定,另一个参数对X的映射都是线性的。 

    抽象化的描述:在《An Efficient Signature Scheme from Bilinear Pairings and Its Applications》这篇文献中,有关双线性配对的描述如下:

          Let G1 be a cyclic additive group generated by P, whose order is a prime q, and G2 be a cyclic multiplicative group with the same order q. Let e : G1 ×G1 → G2 be a map with the following properties:
    1. Bilinearity: e(aP, bQ) = e(P, Q)ab for all P, Q ∈ G1, a, b ∈ Zq
    2. Non-degeneracy: There exists P, Q ∈ G1 such that e(P, Q)/= 1, in other words, the map does not send all pairs in G1 × G1 to the identity in G2;
    3. Computability: There is an efficient algorithm to compute e(P, Q) for all P, Q ∈ G1.

           In our setting of prime order groups, the Non-degeneracy is equivalent to e(P, Q) /= 1 for all P, Q ∈ G1. So, when P is a generator of G1, e(P, P) is a generator of G2. Such a bilinear map is called a bilinear pairing (more precisely called an admissible bilinear pairing).
    (如果P是G1的生成元,则 e(P, P)是G2的生成元,这一类的双线性映射更准确的应称为可接受的双线性映射)

    网上找到的一些中文的解释:(文献还是要读英文原版比较好)

    双线性映射可以用五元组(p,G1,G2,GT,e)来描述,G1,G2,GT是三个素数阶乘法循环群,阶数皆为p,定义在这三个三个群上的一个映射关系e:G1*G2 —>GT,满足以下性质: 

         1、双线性性:

    对于任意a,b∈Zp和R,S∈G1,有e(Ra, Sb) = e(R, S)ab;

          2、非退化性:

    存在R,S∈G1,使得e(R, S) ≠ 1G2(1G2代表G2群的单位元);

          3、可计算性:

    存在有效的算法对任意的R,S∈G1,计算e(R, S)的值。

    注:

    1、现在的密码学相关论文中,习惯将G1,G2设置为乘法循环群。但是,基于椭圆曲线的双线性群构造中,G1,G2是加法群。在大约2005年以前的论文中,G1,G2是加法循环群

    2、双线性映射可以通过有限域上的超椭圆曲线上的Tate对或Weil对来构造。

    展开全文
  • 利用双线性映射构建高效身份认证方案.pdf,
  • 理解密码学中的双线性映射

    万次阅读 2017-04-27 10:06:22
    理解密码学中的双线性映射

    回顾 - 什么是群

    一、定义
    定义1 设G是定义了一个二元运算+的集合,如果这个运算满足下列性质:
    (1)封闭性——如果a和b都属于G,则a+b也属于G。

    (2)结合律——对于G中的任意元素a、b和c,都有(a+b)+c=a+(b+c)成立。

    (3)单位元——G中存在元素e,对于G中任意元素a,都有a+e=e+a=a成立。

    (4)逆元——对于G中任意元素a,G中都存在元素a',使得a+a'=a'+a=e成立。G就叫作一个群,记为(G,+)。

    如果这里的运算+是加法运算,则称G为加法群;如果这里的运算+是乘法运算,则称G为乘法群。如果一个群中的元素是有限的,则称这个群是一个有限群;否则称这个群是一个无限群。有限群中元素的个数称为群的阶

    例:集合{0,1}关于xor运算是群,阶为2
    封闭性:0 xor 1 = 1属于该群
    结合律:(0 xor 1)xor 0 = 1 = 0 xor (1 xor 0)
    单位元为0:0 xor 0 = 0,0 xor 1 = 1
    逆元为1:1 xor 0 = 1,1 xor 1 = 0

    又如:自然数集合N={1,2,3…}对于通常的加法封闭且满足结合律,但不存在左单位元和左逆元,因此对于加法不是群。

    如果群(G,+)中的运算+还满足交换律,即对G中的任意元素a和b,都有a+b=b+a成立,则称G为一个交换群Abel群,例如整数关于加法的运算(Z,+)就为交换群。

    在群中定义求幂运算为重复使用群中的运算,如a4=a+a+a+a。规定a0=e为单位元。如果一个群的所有元素都是a的幂ak,则称这个群是一个循环群,这里的k是整数。a也被称为这个群的生成元

    例:整数加法群是一个循环群,1是生成元,每一个元素都是1的幂,如:
    4=14=1+1+1+1
    -3=1 -3=(-1)+(-1)+(-1)
    而且规定0=1 0,即0为0个1相加。

    (注:定义中的“+”并不代表具体的加法,而是抽象的加法——代表一种代数运算)

    定义2 给定群G中元素a,称满足ai=e的最小正整数i为元素a的阶。

    二、群的基本性质
    (1)左逆元同时也是右逆元,即对于a,b∈G,b+a=e,则a+b=e。

    (2)左单位元同时也是右单位元,即如果对于所有的a∈G有ea=e,则对于所有的a∈G也有ae=e。

    (3)单位元是唯一的。

    (4)逆元是唯一的。

    双线性映射

    抽象意义的双线性映射描述如下:

    设G1、G2都是阶为p的循环群,p是素数。如果映射e: G1 × G1 → G2 满足以下性质:
    (1)双线性性
    对于任意a,b∈Zp和R,S∈G1,有e(Ra, Sb) = e(R, S)ab

    (2)非退化性
    存在R,S∈G1,使得e(R, S) ≠ 1G2。这里1G2代表G2群的单位元;

    (3)可计算性
    存在有效的算法对任意的R,S∈G1,计算e(R, S)的值。

    那么称e是一个双线性映射。
    双线性映射可以通过有线域上的超椭圆曲线上的Tate对或Weil对来构造。

    展开全文
  • 在数论中,一个双线性映射是由两个向量空间上的元素,生成第三个向量空间上一个元素之函数,并且该函数对每个参数都是线性的。最简单的例子: xy→z,x,y∈R xy \to z, x,y \in R xy→z,x,y∈R 1. 双线性映射 设 V,WV...

    在数论中,一个双线性映射是由两个向量空间上的元素,生成第三个向量空间上一个元素之函数,并且该函数对每个参数都是线性的。最简单的例子:
    xyz,x,yR xy \to z, x,y \in R

    1. 双线性映射

    V,WV,WXX 是在同一个基础域F上的三个向量空间。双线性映射是函数:
    B:V×WX B:V \times W\to X

    使得对于任何 WWww,映射
    vB(v,w) v\mapsto B(v,w )

    是从 VVXX 的线性映射,并且对于任何 VV 中的 vv,映射
    wB(v,w) w\mapsto B(v,w )

    是从 WWXX 的线性映射。

    换句话说,如果保持双线性映射的第一个参数固定,并留下第二个参数可变,结果的是线性算子,如果保持第二个参数固定也是类似的。

    2. 对称双线性映射

    如果 V=WV=W 并且有 B(v,w)=B(w,v)B(v,w )=B(w,v ) 对于所有 VV 中的 v,wv,w,则我们称 BB 是对称的。

    3. 双线性形式

    当这里的 XXFF 的时候,我们称之为双线性形式,它特别有用(参见例子标量积、内积和二次形式)。

    4. 多线性

    如果使用在交换环R上的模替代向量空间,定义不需要任何改变。还可容易的推广到 nn 元函数,这里正确的术语是“多线性”。

    对非交换基础环 RR 和右模 MRM_R与左模RN_RN的情况,我们可以定义双线性映射 B:M×NTB:M\times N\to T,这里的 TT 是阿贝尔环,使得对于任何 NN 中的 nnmB(m,n)m \mapsto B(m,n) 是群同态,而对于任何 MM 中的 mm, nB(m,n)n \mapsto B(m,n) 是群同态,并还满足
    B(mt,n)=B(m,tn) B(mt,n ) =B(m,tn )

    对于所有的 MM 中的 mmNNnnRR 中的 tt

    展开全文
  • 该方案将TCG中层次化的密钥树进行虚拟的密钥链划分,为每一个外部实体随机产生唯一的授权参数,并基于双线性映射和RSA机制构造授权值的派生算法。分析表明,该方案具备授权数据的派生、抗合谋攻击能力,并进一步降低...
  • 近些年,在身份认证和零知识证明这一领域,双线性映射使用越来越多,也存在一些算法实现库,本文使用库PBC实现一个基本的零知识证明流程。一、库的下载、编译和使用 (windows 尝试失败,Ubuntu下测试成功)PBC库是...
  • 双线性映射 pbc

    千次阅读 2017-07-22 16:02:53
    pbc是做双线性映射密码学的库 下载了pbc的库,然后在/pbc-0.5.14/example 文件夹下输入:  ./bls pbc 简单编程 以下程序是用pbc的库来验证e(ab,cd) = e(ac,bd) #include ...
  • 密码学 双线性映射

    2019-03-29 11:22:18
  • 近些年,在身份认证和零知识证明这一领域,双线性映射使用越来越多,也存在一些算法实现库,本文使用库PBC实现一个基本的零知识证明流程。一、库的下载、编译和使用 (windows 尝试失败,Ubuntu下测试成功)PBC库是...
  • G1xG2->GT 其中G1和G2是循环加法群的例子很多,网上可以搜到 这里提供一个G1和G2是循环乘法群的e(x,y)例子(只是数学满足(好像满足又好像不满足))
  • 配对是一种特殊的映射,它模糊了信息但依然允许你进行有限的计算,非常令人着迷。 用自己熟悉的语言学习以太坊DApp开发: Java | Php | Python | .Net / C# | Golang | Node.JS | Flutter / Dart 配对的基本概念 ...
  • 双线性映射(密码学常用算法)

    万次阅读 多人点赞 2016-03-29 16:06:54
    Java密码学原型算法实现——第三部分:双线性对 背景介绍 技术博客已经好久没更新了。倒不是因为没得写,是因为实在是太忙了,而且研究也到了一个瓶颈期,需要大量阅读文献。 本来打算很长一段时间都不更新博客...
  • 合数阶群双线性映射 令Ψ\PsiΨ是群的生成算法, 输入安全参数λ\lambdaλ输出参数(p1,p2,p3,G,GT,e)(p_1, p_2, p_3, G, G_T, e)(p1​,p2​,p3​,G,GT​,e), 其中, p1,p2,p3p_1, p_2, p_3p1​,p2​,p3​表示3个不同的...
  • 仿真实验结果:冲击响应和频域响应
  • 双线性映射 概念理解

    千次阅读 2019-04-17 19:34:21
    双线性映射定义了三个素数p阶群乘法循环群G1,G2,GTG_1,G_2,G_TG1​,G2​,GT​,并且定义在这三个群上的映射关系e:G1×G2→GTe:G_1 \times G_2 \rightarrow G_Te:G1​×G2​→GT​,并且满足以下性质: Tips: 什么...
  • 一,图像变换与映射 我们在进行图像处理时常常需要对图像进行变换。比如对图像进行缩放,旋转,平移等。图像变换的本质是将像素点的坐标通过某一种函数关系,映射到另外的位置。假设变换前图像为I(x...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 296
精华内容 118
关键字:

双线性映射