A lightweight attribute-based encryption scheme for the Internet of Things

发表于 | 分类于 | | 阅读次数:
字数统计: 4.4k | 阅读时长 ≈ 18

论文阅读：A lightweight attribute-based encryption scheme for the Internet of Things

文如其名, 比较lightweight, 才9页(笑. 由北京科技大学的博士与中科院博士联手出品.

ABSTRACT

In this paper, a lightweight no-pairing ABE scheme based on elliptic curve cryptography (ECC) is proposed to address the security and privacy issues in IoT. The security of the proposed scheme is based on the ECDH assumption instead of bilinear Diffie–Hellman assumption, and is proved in the attribute based selective-set model. By uniformly determining the criteria and defining the metrics for measuring the communication overhead and computational overhead, the cMomparison analyses with the existing ABE schemes are made in detail. The results show that the proposed scheme has improved execution efficiency and low communication costs. In addition, the limitations and the improving directions of it are also discussed in detail.

We propose a no-pairing ECC-Based ABE scheme to deal with the data security and privacy issues in IoT. Since it replaces the expensive bilinear pairing operation with point scalar multiplication on elliptic curve, it can meet the lightweight requirement and is suitable for IoT.

本文提出了个适用于IoT的ABE解决方案, 因为双线性配对型的ABE很复杂,代价很高,所以采用基于ECC的方法. 同时, 在安全方面采用基于ECDH假设来取代二线Diffie-Hellman假设.

用在椭圆曲线上的点标量乘法代替代价高的双线性配对,可以减少计算开销和通信开销,更适用于IoT设备.

ps:Diffie-Hellman密钥交换(csdn和知乎)

预备知识

1.ECC基础

ECC首先是个公钥加密的算法,生成一对公私钥,私钥用来加密,公钥进行解密与验证.

私钥是一个数字(非常大),通常是随机选出来的. 通过椭圆曲线乘法生成一个公钥. 比特币是在公钥的基础上继续进行哈希函数生成比特币地址.

私钥

为了生成私钥,需要挑选一个足够安全的熵源以保证随机性.从编程的角度来看,一般是通过在一个密码学安全的随机源中 去除一长串随机字节,对其进行SHA256哈希算法进行运算,就可以产生一个256位二进制数,一般是以16进制表示.

有如下随机生成的秘药,以十六进制格式表示:

1
1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD

比特币私钥空间大小是2256,用十进制表示的话,大约是1077. 目前可见宇宙被估计只含有10^80个原子.

公钥

公钥K是通过使用私钥k进行椭圆曲线乘法运算得到公钥,这个过程不可逆: K=k*G,其中G是生成点的常数点. 逆向求私钥及其困难,只能暴力破解.

椭圆曲线密码学解释

比特币使用的是secp256k1标准的特殊椭圆曲线. 由下述函数定义:

1
y^2=(x^3 + 7) over (Fp)  or  y^2 mod p=(x^3 + 7) mod p

上述mod p(素数p取模)表明该曲线实在素数阶p的有限域内, 也写作Fp, 其中: >p = 2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1, 这是⼀个⾮常⼤的素数.

上面的素数阶和有限域让我看得头疼,是啥? 带着问题,来到这个博客认真补习了一下离散数学的知识. 这个博客学习ECC的原理.

椭圆曲线普通方程 :

\(\large y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6\)
无穷远点(0,Y,0)

平常点(x,y)斜率k: >\(\Large k=-\frac{F_x(x,y)}{F_y(x,y)}=\frac{3x^2+2a_2x+a_4-a_1y}{2y+a_1x+a_3}\)

椭圆曲线Abel群 :

在椭圆曲线定义了交换群(Abel群) >任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点R'，过R'做y轴的平行线交于R，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律.

有限域椭圆曲线 :

因为椭圆曲线是连续的,需要将曲线上的点变成离散的点.把椭圆曲线定义在有限域上. 所以椭圆曲线是模p的有限域,记作GF(p)或Fp.

可表示为(P,+,*),其中p是一个质数,P集合表示{0,1,..,p-1}.其中加运算和乘运算都是模运算. 详情可以看这个博客,在这不展开.

椭圆曲线在有限域就表示为 Ep(a,b) ,p是质数, x,y∈[0,p-1] >\(\large y^2=x^3+ax+b\pmod p\)

选择两个满足下列条件的小于p的非负整数a,b >\(\large 4a^3+27b^2\ne0\pmod p\)

Fp上的椭圆曲线同样有加法

  • 无穷远点O∞是零元, 有O∞+ O∞= O∞，O∞+P=P
  • P(x,y)的逆元是 (x,-y mod p)= (x,p-y) ，有P+(-P)= O∞
  • P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系：
    1. \(x_3\equiv k^2-x_1-x_2\pmod p\)
    2. \(y_3\equiv k(x_1-x_3)-y_1\pmod p\)
    3. 若P=Q, 则 \(k=(3x_2+a)/2y_1\pmod p\)
    4. 若P≠Q, 则 \(k=(y_2-y_1)/(x_2-y_1)\pmod p\)

举例 :椭圆曲线已知E_23(1,1)上两点P(3,10)，Q(9,7)，求(1)-P，(2)P+Q，(3) 2P

公式

椭圆曲线加密 : >考虑K=kG ，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶（nG=O∞），k为小于n的整数。则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。因为实际使用中的ECC原则上把p取得相当大，n也相当大，要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据. > >点G称为基点（base point） > >k（kn）为私有密钥（privte key） > >K为公开密钥（public key)

ECC保密通信算法 :

  1. Alice选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G 假设选定E29(4,20)，基点G(13,23) , 基点G的阶数n=37
  2. Alice选择一个私有密钥k，并生成公开密钥K=kG 比如25, K= kG = 25G = (14,6）
  3. Alice将E和点K、G传给Bob
  4. Bob收到信息后，将待传输的明文编码到上的一点M（编码方法略），并产生一个随机整数r（r小于n,n为G的阶数） 假设r=6 要加密的信息为3,因为M也要在E29(4,20) 所以M=(3,28)
  5. Bob计算点C1=M+rK和C2=rG C1= M+6K= M+625G=M+2G=(3,28)+(27,27)=(6,12) C2=6G=(5,7)
  6. Bob将C1、C2传给Alice
  7. Alice收到信息后，计算C1-kC2，结果就应该是点M C1-kC2 =(6,12)-25C2 =(6,12)-25*6G =(6,12)-2G =(6,12)-(27,27) =(6,12)+(27,2) =(3,28)

数学原来上能解密是因为:C1-kC2=M+rK-krG=M+rkG-krG=M

论文对ECC进行了剖析. >ECC can provide security based on the known public key cryp-tography primitives, which are Elliptic Curve Digital Signature Al-gorithm (ECDSA), key exchange/agreement (ECDH, Elliptic Curve Diffie–Hellman) and Elliptic Curve Integrated Encryption Standard (ECIES). Compared with other public key cryptography schemes, ECC has 3 distinguished features, which make it very fit for resources-constrained environments [22]. > - It only requires significantly smaller key size than RSA and the modular exponent based public key schemes on the same level of security. > - Its point scalar multiplication operation is much faster than modular exponent operation and bilinear mapping operation. > - It is easy to be implemented in hardware. > > In this paper, we take these advantages of ECC and the features of ABE to construct an ABE scheme for IoT, where Elliptic Curve Decisional Diffie–Hellman Problem (ECDDHP) serves as the complexity assumption, and the Elliptic Curve Integrated Encryption Standard (ECIES) is adopted to encrypt the data.

ECC提供的安全性基于ECDSA,ECDH,ECIES.与其他的公钥加密算法,ECC有如下几个非常适用于资源节约型的环境的特性.

  1. 相对于RSA,可以用较小量级的密钥大小提供与RSA相同等级的安全性.
  2. 标量乘法运算比模指数运算和双线性映射快得多.
  3. 在硬件上更容易实现.

本文基于这些ECC的功能,来构建在IoT上的ABE方案. ECDDH 来作复杂度假设, ECIES 对数据加密.

ECDDH

ECDH 是一种在椭圆曲线上的Diffie-Hellman的密钥交换协议. 可以帮助具有椭圆曲线公私钥对的双方通过不安全的通道生成 共享密钥. 这个共享密钥可以直接当成密钥或者派生出新的密钥来加密接下来通讯内容. >例如, Alice与Bob使用同一套ECC系统(q,a,b,G,p) > > Alice的密钥对是(S_A , P_A=S_A*G). Bob的密钥对(S_B , P_B=S_B*G) > >那么他们的共享密码K_{A,B}就是: K_{A,B}=S_A* P_B=S_B* P_A=S_A* S_B* G

ECDDH(elliptic curve decisional Diffie–Hellman problem) 是ECDH的重要变体. >对于具有生成元G的q阶椭圆曲线群G_E, DHH表明, 给定c*G和d*G的条件下,c*d*G是G_E中的随机元素. > (其中,c,d都是在q阶整数上随机取的.) > >也就是说，对于给定的三元组（c·G，d·G，c·d·G）和（c·G，d·G，Z），无法判断Z = c·d·G

ECIES

ECIES椭圆曲线集成加密方案,包含有密钥交换和公钥加密的部分.

使用ECDH生成共享密钥,数据的机密性由对称加密算法保证,密钥和数据完整性由MAC密钥的功能保证.

以下是ECIES的加密与解密步骤: 加解密步骤

Access structure

访问结构用于描述访问策略,可用访问树表示,由如下定义: >(Access Structure [11]). Let \(\{A_1, A_2,..., A_n\}\) be a set of attributes. A collection \(\mathbb{A}\) = \(2^\{A_1,A_2,...,A_n\}\) is monotone, for \(\forall B,C\): if \(B\in \mathbb{A}\) and \(B\subseteq C\), then \(C ∈ \mathbb{A}\). An access structure (respectively, monotone) is a collection (respectively, monotone) \(\mathbb{A}\) of non-empty subsets of \(\{A_1,A_2,..,A_n\}\), i.e.,\(\mathbb{A}⊆\)\(2^{A_1,A_2,..,A_n}\setminus \emptyset\). The sets in A are called the authorized attributes sets, and the sets not in A are called the unauthorized attributes sets.

有那么一组属性组 \(\{A_1, A_2,..., A_n\}\), 设有一二元集合 \(\mathbb{A}\) = \(2^\{A_1,A_2,...,A_n\}\), 如果对与任意的B与C,有B属于A,且B是C的子集,得到 C也属于A.那么二元集合A是单调的.

所以访问结构是属性集合 \(\{A_1, A_2,..., A_n\}\) 的非空子集 \(\mathbb{A}\) ,集合 \(\mathbb{A}\) 称为授权集.

访问树 的具体定义与原理 在这篇文章有详细提及, 在这不详细说.

算法实现细节

该算法是用KP-ABE的结构, 涵括了AA(attribute authority). 由四个算法步骤组成:

  1. Setup: 在中心节点生成public key parameters,PK和master key,MK. master key作为私钥在中心节点所用, public key parameters向外公开.
  2. Encrypt: 由发送者执行,将消息M输入,中心节点的PK加密输入(确定中心节点),设定属性集r,输出密文CM.
  3. key-Generation:由中心节点执行,将访问结构R和中心节点MK输入,根据R输出解密钥匙D.
  4. Decrypt: 由接收者执行,输入发送者发送的密文CM,中心节点给的解密钥匙D,中心节点的PK,当R(r)=1时, 可以得出解密后的消息M.

本文的给出的KP-ABE算法

本文所给出的轻量级的ABE是基于ECC的,假定ECC的参数是(q,a,b,G,p).

对于属性集w, 密钥是由基于拉格朗日插值法的secret sharing构建的. 且该方法有一个ECC-based的密钥生成中心. （拉格朗日插值法学习链接）

  1. Setup:首先是定义中心节点的属性集U,对U中每个属性\(i\), 在ECC的q阶正整数群内随机找一个对应的数字 \(s_i\),每个属性\(i\)的公钥就是\(P_i=s_i\cdot G\). 同样地,在q阶正整数群内随机找一个数字\(s\)作为中心节点的MK,中心节点的PK就等于 \(PK=s \cdot G\), 所以中心节点的公开参数可以表示为: \(Params=\{ PK,P_1,..,P_\left | U \right|\}\)

  2. Encryption(M,w,Params): 与现存的ABE不同的是, 消息M是由ECIES加密的,而不是模指数运算或者双线性配对加密的.

    • 随机从ECC的q阶正整数群选择k来计算C',\(C'=k \cdot PK=(K_x,K_y)\),若C'为0则重选k.
    • 分别对Params中\(P_i\)计算\(C_i\), \(C_i=k \cdot P_i, i \in w\).
    • \(K_x\)为加密密钥,\(K_y\)则是整合的密钥. \(C=ENC(M,K_x)\), \(MAC_M=HMAC(M,K_y)\)
    • 密文cipher-text就可以表示为\(CM=(w,C,MAC_M,C_i,i\in w)\).

  3. KeyGeneration(\(\Gamma,MK\)): 当且仅当 \(\Gamma (w)=1\)时,通过算法生成解密的密钥.

    • 对访问控制树 \(\Gamma\)上的每个节点u都自上而下进行定义,这些节点的门限都是\(d_u\). 多项式\(q_u(x)\)由此定义
    • 对于访问树 \(\Gamma\)的根R,设\(q_R(0)=s\) (ps: s就是setup步骤的MK) 并随机选择\(d_R-1\)个其他点做多项式\(q_R(x)\)
    • 对于其他节点u, \(q_u(0)=q_{parent(u)}(index(u))\),也要随机选择\(d_u-1\)个其他点来定义\(q_u(x)\)
    • 当访问树的叶子节点都被定义了之后,叶子节点u的secret share解密密钥就可以表示为: \(\large D_u=q_u(0)/s_i\),其中\(i\)是一个属性,\(s_i\)在setup步骤上就已经定义,\(s_i^-1\)是\(s_i\)在ECC群中的逆元.根据这样的访问树结构就能逐步还原.
    • 最终解密密钥可以表示为: \(D=(D_u=q_u(0)/s_i, i=attr(u)\ and\ \ i\in w)\).

  4. Decryption(CM,D,Params):与其他算法相似,在访问树里的节点的解密算法用递归的方法实现.

    • 对每个叶子节点u, 令 \(i=attr(u)\) 有: $ DecryptNode(CM,D,u)=$ \begin{cases} D_u C_i=q_u(0) s_i^-1kP_i\ =q_u(0) s_i^-1ks_iG\ =q_u(0) kG , &(iw)\ , &Otherwise. \end{cases}

    • 对非叶子节点,可以对每个子节点v调用\(DecryptNode(CM,D,v)\).

  • 令\(w_u\)为u的\(d_u\)个子节点的集合, 对每一个\(w_u\)的元素v进行\(DecryptNode(CM,D,v)\).

  • 若存在\(w_u\),那么有: >

  • 对根节点有: \(DecryptNode(CM, D, R) = q_R(0)·k·G = s·k·G = (K′_x, K′_y)\). 其中\(K'_x\)就是消息M的解密密钥,\(K'_y\)是消息M的集合密钥.\(M'=DEC(C,K'_X)\).

  • 如果\(HMAC(M',K'_y)=MAC_M\),那么就表示消息M已经被正确解密. 所以说所有的正确性,完整性都由\(MAC_M\)验证.

算法表现与分析

本文为了评估所提出的ABE方案的轻量级的特点,在 通信开销 和 KP-ABE和CP-ABE的 加算开销 上分析. 并给出该算法的限制.

通信开销指标

通信开销取决于所传输的消息的长度. 传输的消息包括了 密文cipher-text ,公钥 和 私钥.

现有大多数ABE方案都是基于双线性配对的RSA-based方案. 有两个群\(G_1,G_2\), \(G_1\)是一个大素数阶的双线性群, 双线性映射可以表示为 \(G_1 \times G_1 \rightarrow G_2\). 且\(G_1,G_2\) 的基本运算都是模指数运算. 在相同安全级别上,RSA的密钥对比ECC的密钥对长得多.RSA的密钥对长度在 \(G_1\) 是ECC的3.2倍,\(G_2\) 是6.4倍.

在ABE方案中,密文需要包含属性集, 密文的长度与属性集成线性增长.

密文 \(CM=(w,C,MAC_M,C_i,i\in w)\) ,\(C_i\)是椭圆曲线的一点,且长度为\(2l\),由于先前的假设,消息M和MAC的长度都为安全级别\(l\),所以\(C\)和\(MAC_M\)也是\(l\)位长. 所以给出的方案的密文长度是 \((l+l+k*2l)=(2k+2)l\).

另外,公钥是 \(\{PK,P_i,i\in U\}\),每一个元素都是椭圆曲线上的一点,所以公钥长度为 \((2l+n*2l)=(2n+2)l\). 私钥是 \(\{D_u=q_u(0)/s_i,\ i=attr(u)\mbox{ and }i\in w\}\), 长度是\(k\cdot l\).

计算开销指标

本文对比了现有的CP-ABE和KP-ABE. 计算开销一般是由双线性映射(公钥的加密解密操作)的成本衡量的.本方案中没涉及,所以不计算.本文的加密算法包括了(1+k)点标量乘法,且解密的递归过程不超过(2k-1)点标量乘法,所以总的最多有3k个点标量乘法.

与其他的方案的比较如下图:

可以看出在 公私钥长度 都远比其他方案要短, 密文长度 在属性大于10个时大于常数级的方案. 计算开销 也明显小于一般方案. 所以说在 轻量级 的属性加密方案上,该文的方案是很优秀的.

提出的ABE方案的限制

  1. 撤销属性灵活性较差: 使用的是单调访问结构和秘密共享机制,都是在"AND"和"OR"门上进行的,不支持"NOT"门, 难以表达复杂的访问策略,属性撤销也很麻烦.通常操作都是重新加密来实现属性撤销. 本文并没有讨论属性撤销属性.

  2. 可扩展性差: 通信开销和计算开销都与加密属性数量成线性关系.

  3. 通用性较差: 本方案是单一权限上的应用,不适用于多权限结构.

参考文章

  1. Yao X, Tian Y, Tian Y. A lightweight attribute-based encryption scheme for the Internet of Things[J]. Future Generation Computer Systems, 2015, 49(C):104-112.
  2. Bitcoin加密技术之椭圆曲线密码学
  3. 谈谈有限域那些事儿
  4. 离散对数和椭圆曲线加密原理
  5. ECC入门+实例 (身份证比特币加密算法)
  6. 数学、英语对程序员来说重要吗？记线性秘密分享方案（Linear Secret Sharing Scheme，LSSS）的实现
  7. [如何直观地理解拉格朗日插值法？ @马同学的回答]6
  8. 密码学中的离散数学知识学习
Buy me coffee☕️.