Mathematics in Cryptography

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

原作时间：2018年3月31日

密码学中的离散数学知识学习

密码学中的近世代数实在是让人头疼,在实际阅读文章中很吃力,于是决心下点苦工补一补代数的知识。(本科有学习过离散数学，终于还是吃了数学的亏。谁要是再说学数学没用我就*@$%!)

首先是学习这篇文章里的知识点,和之前学习过的离散数学无异，但是这篇文章好就好在了深度展开了许多知识点，并用较为简洁的例子讲解。但是呢，有点不足的是，因为代数系统他是一环扣一环的，有很强的迭代,往往会让人拎不清谁是谁。本文引用这篇文章就想能更加拎清楚概念。

离散数学基础

二次关系

一些其他的二次关系就暂且不提，只说一些与密码学相关的.

二次关系的一些性质:(其中，A是集合，R是集合中的关系)

- 自反性 反自反性 对称性 反对称性 传递性
定义 X∈A,有(x,x)∈R x∈A,有(x,x)不∈R 若(x,y)∈R,则(y,x)∈R 若(x,y)∈R,则(y,x)不∈R 若(x,y)∈R,且(y,z)∈R,则(x,z)∈R

等价关系和偏序关系

等价关系: R是非空集A的关系,如果R是 自反,对称,传递 的,则称R为A上的等价关系. 举个栗子: 在实数集合中，等号'='就是一个等价关系.假设a=b=c=1; a,b,c都∈实数R;符合自反性:a=b; 符合对称性:a=b则b=a;符合传递性:a=b且b=c,则a=c;

偏序关系: R是非空集A的关系,如果R是 自反,反对称,传递 的,则称R为A上的偏序关系. 举个栗子: 在实数集合中，大等于号'≥'就是一个偏序关系。假设a≥b≥c; a,b,c都∈实数R; 符合自反性: a≥a; 符合反对称性: a≥b 则 b不≥a; 符合传递性: a≥b且b≥c,则a≥c; 若集合S上定义了一个偏序R,则S成为 偏序集 (S,R) 设有偏序集(S,≤)，(note:偏序关系'≤'并非实数的小等于)

  1. 若有任意x∈S,且b≤x,则称b为S的 下界 ;
  2. 若有任意x∈S,且x≤b,则称b为S的 上界 ;
  3. 若b是一个下界,且对于每一个S的下界b'都有b'≤b,则b是S的 最大下界或下确界 .
  4. 若b是一个下界,且对于每一个S的下界b'都有b≤b',则b是S的 最小上界或上确界 . (Note: 上界和下界有可能不唯一)

二元运算及其性质

代数中的二元运算的内容和小学学过的乘法结合律,交换了,幂等律差不多,所以不再详细说. 主要介绍幺元,零元,逆元的定义。(假设*是集合S中的二元运算)

  1. 幺元 : 若存在元素e∈S,使任何x∈S,有 e*x=x，x*e=x 则,e是集合S中关于*运算的幺元。就像1在实数集合关于×运算的幺元。
  2. 零元 : 若存在元素θ∈S,使任何x∈S,有 θ*x=θ，x*θ=θ 则,θ是集合S中关于*运算的零元。就像0在实数集合关于+运算的零元。
  3. 逆元 : e∈S是运算*的幺元，对任意x∈S,若存在y∈S,且 y*x=e，x*y=e 则,y是x的逆元。就像所有实数(除0之外)在实数集合中的倒数,相乘都等于关于×运算幺元1,这些相应的倒数就是这些实数的逆元。

典型代数系统

半群

在一个集合S中定义了某种运算（记作加法“+”，但这个加法指代广泛意义上的运算，并不是指日常使用的加法），那么在这个集合上，如果这种运算满足以下性质，那么他和集合S共同组成一个半群，记作(S,+)：

封闭性。也就是运算的结果始终在集合S内

结合律。也就是满足：(a + b) + c= a + (b + c)

举例: 在实数集合R中,加法'+'符合封闭性:加法运算的所有结果都是实数; 符合结合律; 所以(R,+)形成半群。

幺半群

如果在一个半群(S,+)中存在一个幺元e,使得任意x∈S都有:

x + e = e + x = x

那么该半群就是一个幺半群.

举例: 在刚才例子中的半群(R,+)中,存在一个幺元0,使得任意x∈R都有 x + 0 = 0 + x = x.

群

如果在一个幺半群(S,+)中，任意元素x∈S,都存在唯一对应元素y使得:

x + y = y + x = e ， 其中e是幺元 即: 任意元素x∈S,都存在唯一逆元与之对应.

那么该幺半群就是一个 群。这样就在群中定义了减法.

交换群(Abel群)

如果一个群(S,+)符合交换律，即对于集合S中任意元素x,y∈S,有:

x+y=y+x

那么这个群就是交换群.

来总结一下刚才所提到的群概念的迭代:

- 半群 幺半群 群 交换群
性质 封闭性,结合律 封闭性,结合律,存在幺元 封闭性,结合律,存在幺元,存在逆元 封闭性,结合律,存在幺元,存在逆元,交换律
迭代 +封闭性,结合律 +存在幺元 +存在逆元 +交换律

环

设 (S,+,)是一个代数系统,其中S为集合，+,是二元运算。若有:

1。(S,+)是Abel群(交换群)。(结合律,交换律,存在幺元和逆元) 2。(S,)是半群。 (结合律) 3。二元运算对于+适合分配律.

则(S,+,*)是一个 环 .且群(S,+)中的 幺元 是环(S,+,*)的 零元 . 举例:在实数集合中,(R,+)是个交换群,(R,×)是半群,且加法和乘法符合分配律,所以(R,+,×)是一个环.

零因子 : 若在环(S,+,*)中,且该环零元为θ,存在a,b∈S,且a!=θ,b!=θ,但有a*b=θ,则称a为S中的左零因子,b为S中的右零因子.

整环

若环(S,+,*)中(S,*)半群 符合交换律,且存在幺元,且无零因子,那么该环就称为整环.

例如 整数环(R,+,×)就是整环.

除环

若环(S,+,*)中(S,*)半群存在幺元,无零因子,且对任意x∈S,都存在除 零元 以外的逆元,那么该环就成为除环

除环定义了乘法逆元的存在,也就是除法.

交换环

若环(S,+,*)中(S,*)满足交换律,那么环(S,+,*)是 交换环.

来总结一下刚才所提到的环概念的迭代: (其中环都表示为(S,+,*))

- 环 交换环 整环 除环
定义 (S,+)是交换群,(S,*)是半群,符合分配律 (S,+)是交换群,(S,*)是交换半群,符合分配律 (S,+)是交换群,(S,*)是幺半群且符合交换律,符合分配律 (S,+)是交换群,(S,*)是幺半群且有逆元(零元以外),符合分配律
迭代 (S,+)交换群,(S,*)半群 (S,*)+交换律 (S,*) +有幺元,无零因子,符合交换律 (S,*)+有幺元,有逆元,无零因子

域

如果一个环(S,+,*),既是除环又是交换环,那么它就是一个域.

例如:(R,+,*)既是除环又是交换环,所以它是一个域,成为 实数域.

格

设(S,R)是 偏序集 ,若有任意x,y∈S,{x,y}都有最小上界和最大下界,则称S关于偏序R构成一个格.

有限域

如果一个域的元素是有限的，那么就是一个有限域。相对地,无限域犹如实数域一样,元素个数是无限的.

有限域中的元素个数被称为有限域的 阶(Order).有限域的阶一定是某个素数p的正整数次幂.

模p的有限域 GF(p)

GF(p)是定义在整数集合{0,1,...,p-1}上的域。GF(p)上的加法和乘法分别是模加法和模乘法.

  1. 加法和乘法 .(br) 模加法和模乘法和普通的整数加法和乘法有些不同.例如在GF(7)定义在{1,2,..6}上,加法和乘法如下:(br)
1
2
1 + 2 = 3 mod 7 = 3
1 * 2 = 2 mod 7 = 2
  1. 减法 (br) a减去b,其实就是加上b的加法逆元。已知GF(7)的加法幺元是0,于是x的加法逆元y就有:( x + y ) mod 7 = 0;
1
2
1 - 2 = 1 + ( -2 ) = 1 + 5 = 6 mod 7 = 6    or
1 - 2 = -1 mod 7 = 6
  1. 除法 (br) a除以b,需要找到b的乘法逆元，已知GF(7)的乘法幺元是1,于是x的乘法逆元就有:
1
2
3
x * y mod 7 = 1
也就是解下面这个方程:
b * x = 1 + 7*k ,其中k是正整数.

实际求解过程并不简单,直接上实例:

1
2
3
4
5
3 ÷ 4
= 3 * (1/4)
= 3 * 2
= 6 mod 7
= 6;

有限域GF(2^m)

在里德-所罗门编码(二维码使用的编码)以及椭圆曲线加密中都有使用。

GF(2m)包含了2m个元素。因为计算机的二进制所以选用2这个质数。2m个元素恰好是长度为m的二进制.具有更高的计算效率。 为了方便,之后都将GF(2m)中的元素表示成长度为m的二进制形式,以m=3为例。

  1. 加法和减法 (br) GF(2m)上的加法减法都是异或运算。加法的幺元是0.(br) 010和110都是GF(23)的元素,有:
1
2
010 + 110 = 010 ⊕ 110 = 100
010 - 110 = 010 ⊕ 110 = 100
  1. 乘法 (br)太繁琐了,就不认真写了.看这链接.

因为之前学习ABE的构造加密策略的时候遇到了一些问题，例如LSSS的原理，拉格朗日多项式插值,双线性配对，DH密钥交换等问题。 需要进一步deep dive。

LSSS原理学习

这一篇博客从访问控制树开始说起，再到SSS密码分享方案，说得很详细。 所以我就以这篇博客为范本开始学习LSSS。

控制树就不说了，之前的学习有详细描述。

2008年RSA的S，Shamir提出来一种 秘密分享方案SSS(secret sharing scheme)。

Shamir秘密分享方案利用了 拉格朗日多项式插值方法,其基本思想是:如果预先定义了一个t-1阶的多项式,那么如果知道这个多项式上的t个点,则一定能完整恢复出这个多项式.

这个拉格朗日多项式插值法在之前的学习有学习到。在这个知乎@马同学的回答上有很详细很有趣的解说。 于是有拉格朗日多项式插值:

\(\Large L(x):= \sum_{j=0}^{k}y_i\ell_j(x)\)

其中 \(\Large \ell_j(x):=\prod_{i=0,i\ne j}^{k}\frac{x-x_i}{x_j-x_i}\)

拉格朗日多项式插值法如何运用在秘密的分享上? 假设有t-1阶的多项式, 如果有t个线性无关的等式就肯定可以还原出这个多项式.

所以假设所要分享的秘密是S, 任取t-1个随机数 \(a_1,a_2,..,a_{t-1}\) 构造一个t-1阶多项式: \(f(x)=a_{t-1}x^{t-1}+a_{t-2}x^{t-2}+...+a_1x+S\). 对于每个用户i, 所分享的结果为 \((i,f(i))\) 所以当t个用户在场时,可以得到秘密S.

线性秘密分享方案(Linear Secret Sharing Scheme,LSSS)

只要是线性的秘密分享方案, 都可以用LSSS来描述.

A secret sharing scheme \(Π\) over a set of parties \(P\) is called linear (over \(\mathbb{Z}_p\)) if

  1. the shares for each party form a vector over \(\mathbb{Z}_p\), and
  2. there exists a matrix \(M\) called the share-generating matrix for \(Π\). The matrix \(M\) has \(m\) rows and \(d\) columns. For \(i = 1, . . . , m\), the \(i^{th}\) row \(M_i\) of \(M\) is labeled by a party \(ρ(i)\) where \(ρ\) is a function from \(\{1, . . . , m\}\) to \(P\). Given a column vector \(\vec{v} = (s, r_2, . . , r_d)\), where \(s ∈ \mathbb{Z}_p\) is the secret to be shared and \(r_2, . . . , r_d ∈ \mathbb{Z}_p\) are randomly chosen, \(M\vec v\) is the vector of \(m\) shares of the secret \(s\) according to \(Π\). The share \(λ_i = (M\vec v)_i\), i.e., the inner product \(M_i · \vec v\), belongs to party \(ρ(i)\).

通过这个定义可以知道，一个秘密分享方案要被称作线性的需要符合如下:

  1. 每一个成员的份额通过 \(\mathbb{Z}_p\) 形成一个向量，且
  2. 存在一个分享生成矩阵 \(M\)，矩阵的每一行都依次被一个成员所标记。 有一个向量 \(\vec{v} = (s, r_2, . . , r_d)\), s是需要分享的秘密, \(r_2, . . , r_d\) 是在 \(\mathbb{Z}_p\) 中随机选择的. 第i个成员所拥有的分享份额就是: \(M_i · \vec v\). M的第i行和这一列的积(结果还是一个向量).

Any LSSS defined as above enjoys the linear reconstruction property defined as follows. Suppose that \(\Pi\) is an LSSS for access structure \(\mathbb{A}\). Let \(S \in \mathbb{A}\) be an authorized set, and \(I \subset \{1, \ldots, m\}\) be defined as \(I = \{i: \rho(i) \in S\}\). There exist constants \(\{\omega_i \in \mathbb{Z}_p\}_{i \in I}\) satisfying \(\sum_{i \in I}{\omega_i M_i} = (1, 0, \ldots, 0)\) , so that if \(\{\lambda_i\}\) are valid shares of any secret s according to \(\Pi\), then \(\sum_{i \in I}{\omega_i \lambda_i} = s\) . Furthermore, these constants \(\{\omega_i\}\) can be found in time polynomial in the size of the share-generating matrix M. For any unauthorized set, no such constants exists. The LSSS is denoted by \((M, \rho)\).

上面所定义的LSSS有如下定义的线性重建属性. 假设在一个访问结构A中, I为分享组的所有成员. 对于每个分享组成员 i 总在p阶整数域内存在一个常数 \(\omega_i\) ,满足 \(\sum_{i \in I}{\omega_i M_i} = (1, 0, \ldots, 0)\), 即对于每个合法分享成员所持有的秘密 \(\lambda_i\) 总有 \(\sum_{i \in I}{\omega_i \lambda_i} = s\) 得出最终秘密s. 所以这个常数的求解就是LSSS的解密关键.

求解常数 \(\omega\)

  1. 从定义可知 \(\vec \lambda = M \cdot \vec v\) ,M为分享生成矩阵,向量 \(\vec{v} = (s, r_2, . . , r_d)\),恢复出向量v的第一项S,也就是所要求的秘密. 因为矩阵M并不是一个方阵, 不存在它的逆矩阵, 所以想到使用M的某个子阵求逆.(博客原话,需要进一步推敲为什么.)
  2. 矩阵M的列d代表着至少需要d方参与才能恢复. 但是并不是属性个数满足列数就能访问, 例如(A or B)and(C or D), 若属性集合是{A,B}也不能访问, 所以意味着,A和B在矩阵对应的行是重复的,可以删去. 所以我们需要在集合中找到一个子集,使得子集对应的矩阵M的行所组成的子阵满足满秩就行了.
  3. 如何找到这样的矩阵,就要用到单调访问政策的单调性了. 单调性意味着,一个属性是冗余的,那么去掉这个属性也能满足访问控制政策. 用遍历的方法,去除各个属性,就能得到一个子矩阵M',其对应的分享为 \(\vec \lambda'\) M'满足可逆性.
  4. \(s = (1, 0, \ldots, 0) \cdot \vec v = (1, 0, \ldots, 0) \cdot M'^{-1} \vec \lambda'\) . 因为 \(\sum_{i \in I}{\omega_i \lambda_i} = s\) 所以有 \(\vec \omega = (1, 0, \ldots, 0) \cdot \vec M'^{-1}\). 这意味着不需要知道 \(\vec \lambda\) 只需要知道LSSS的矩阵M,已经知道能够满足恢复S条件的属性集合就行了.

构造LSSS矩阵

2010年, Lewko和Waters在论文5中提到,只要是 AND和OR描述的都可以转换为LSSS方案.

We now describe a general algorithm for converting a boolean formula into an equivalent LSSS matrix. We consider the boolean formula as an access tree, where interior nodes are AND and OR gates and the leaf nodes correspond to attributes. We will use \((1,0,\ldots,0)\) as the sharing vector for the LSSS matrix. We begin by labeling the root node of the tree with the vector (1)(a vector of length 1). We then go down the levels of the tree, labeling each node with a vector determined by the vector assigned to its parent node. We maintain a global counter variable c which is initialized to 1.

If the parent node is an OR gate labeled by the vector v, then we also label its children by v (and the value of c stays the same). If the parent node is an AND gate labeled by the vector v, we pad v with 0’s at the end (if necessary) to make it of length c. Then we label one of its children with the vector \((v|1)\) (where | denotes concatenation) and the other with the vector \((0,\dots, 0 | -1)\), where \((0, \ldots, 0)\) denotes the zero vector of length c. Note that these two vectors sum to \((v|0)\). We now increment the value of c by 1. Once we have finished labeling the entire tree, the vectors labeling the leaf nodes form the rows of the LSSS matrix. If these vectors have different lengths, we pad the shorter ones with 0’s at the end to arrive at vectors of the same length.

  1. 将布尔表达式化为访问树, 其中内部节点是AND和OR门, 叶子节点表示为属性.
  2. 将树的根节点标记为 1,从上往下依次向每个节点根据父节点的向量添加向量.
  3. 维护一个全局变量 C ,C从1开始记.
  4. 若父节点是OR门, 且父节点被标记为v, 那么子节点也标记为v,且变量C保持不变.
  5. 若父节点是AND门,且父节点被标记为v, 那么将用'0'来填充v的尾部(如果需要的话)来保证最终长度为C.将其中一个子节点标记为向量 \(v|1\) (其中'|'表示串联); 其他的子节点标记为 \((0,\dots, 0 | -1)\), 其中 \((0,\dots,0)\) 表示长度为 C 的零向量. 且C+1. 这两个向量的和为 \(v|1 + (0,\dots,0)|-1=v|0\).
  6. 当我们完成了整个树的标记, 标记的叶节点就是LSSS矩阵的行. 如果这些向量有不同的长度,就在尾部用'0'来填充.

不过不同的方案可以有不同的LSSS矩阵构造方案, 具体问题具体分析.

此外布尔表达式如何转化为访问树结构还需进一步学习. 这里有一些Parser源码,可以参考(链接).

Diffie-Hellman密钥交换学习

Diffie-Hellman密钥交换(简称DH密钥交换)是可以让对等的双方在完全缺乏对方信息的前提下, 通过不安全的信道达成一个共享的密钥.

DH密钥交换的方法是建立在计算离散对数(Discrete Logarithm Problem)的困难程度上的. 之前的学习(链接)有详细描述,在此就不展开探讨. 总而言之就是一个模p有限域的问题. 例如:

若p是一个素数,g和x都是p阶域中的整数, 计算 \(y=g^x \bmod p\) 很简单. 相反的, 若已知素数p,g和y,要求x满足等式 \(y=g^x \bmod p\) 就是非常困难的.

当然, 基于安全性的考虑, 这里的 p通常都是很大的素数,通常取1024bit, 且(p-1)/2也是素数. G是素数p的原根(primitive root). 原根可以保证: \(g^i\bmod p\ne g^j\bmod p,\ where\ i\ne j\ and\ i,j\in (0,p-1)\)

DH密钥交换具体算法如下:

  • Alice和Bob约定 \(p\) 和 \(g\) 的值
  • Alice生成私钥 \(x\)，计算 \(g^x\bmod p\) 作为公钥公布出去
  • Bob生成私钥 \(y\)，计算 \(g^y\bmod p\) 作为公钥公布出去
  • Alice得知 \(g^y\bmod p\) 后，计算 \(s=(g^y\bmod p)^x\bmod p=(g^y)^x\bmod p=g^{xy}\bmod p\)
  • Bob得到 \(g^x\bmod p\) 后，计算 \(s=(g^x\bmod p)^y\bmod p=(g^x)^y\bmod p=g^{xy}\bmod p\)
  • 双方都得到了相同的密钥的 \(s\)，交换完毕

在上面的流程中,私钥 \(x,y\) 始终是Alice和Bob自己保管的, 窃听到的只有 \(p,g,g^x\bmod p,g^y\bmod p\). 可以保证安全性.

双线性配对学习

双线性配对(Bilinear Pairing)最初在2001年由Boneh和Franklin利用它构造了第一个实用并且可证安全的基于身份的加密方案(IBE).

素数阶双线性群(Prime-Order Bilinear Groups)

双线性配对定义了三个素数p阶群乘法循环群(有些方案是加法循环群, 例如椭圆曲线的双线性构造) \(G_1,G_2和G_T\). 并且定义了这三个群的一个配对(映射)关系 \(e:G_1×G_2→G_T\) (这里的乘和矩阵的乘相似),并且满足如下性质:

  1. 双线性: 对于任意 \(g_1\in G_1,g_2\in G_2,\ a,b\in Z_p\) 均有 \(e(g_1^a,g_2^b)=e(g_1,g_2)^{ab}\) 成立.
  2. 非退化性: \(\exists g_1 \in G_1, g_2 \in G_2\), 满足 \(e(g_1,g_2) \neq 1_{G_T}\).
  3. 可计算性: 存在有效的算法, 对于 \(\forall g_1 \in G_1, g_2 \in G_2\), 均可计算 \(e(g_1,g_2)\).

若 \(G_1 = G_2\) 则称上述双线性群是对称的.

合数阶双线性群(Composite-Order Bilinear Groups)

与素数阶类似, 区别在于 \(G_1,G_2和G_T\) 的介数是一个 合数 ,该合数是一些很大的素数的乘积. 例如:\(N=p_1×p_2×\cdots×p_n\)

也满足素数阶双线性群的三个性质. 与之不同的是,合数阶双线性群中,有阶数分别为 \(p_1,p_2,\dots,p_n\) 的子群 \(G_{p_1},G_{p_2},\dots,G_{p_n}\). 这些子群满足正交性. 也就是说: \(\forall g_i\in G_{p_i},\forall g_j\in G_{p_j},\ and\ i\ne j\ and\ e(g_i,g_j)=1\)

参考文章

  1. 记线性秘密分享方案（Linear Secret Sharing Scheme，LSSS）的实现
  2. 如何直观地理解拉格朗日插值法？
  3. 拉格朗日插值法(图文详解)
  4. 线性秘密共享方案（LSSS）构造与解密
  5. Lewko, A., Waters, B.: Decentralizing attribute-based encryption. IACR Cryptology ePrint Archive, (2010) 351. https://eprint.iacr.org/2010/351.
  6. Diffie–Hellman 密钥交换协议简介
  7. 密码学中的离散数学知识学习
  8. [可以解释一下密码学中什么叫双线性配对吗？@SDKany的回答]8
  9. 双线性映射（密码学常用算法）
  10. 斯坦福大学pbc库
  11. 谈谈有限域那些事儿
  12. 离散数学偏序关系哈斯图上（下）确界极小（大）值最大（小）值
  13. 第18章 格与布尔代数
Buy me coffee☕️.