Security Reduction学习笔记(2):预备知识(群环域,双线性配对,哈希函数)-526互联

省略部分可参考密码协议学习笔记(1.4):密码学的一些数学基础 - Isakovsky - 博客园 (cnblogs.com)

有限域:

$\mathbb{F}$是有限个元素的集合

若$(\mathbb{F},+,*)$满足某些条件(条件略),则称其为有限域(Finite Field,或称Galois域)

其零元,单位元分别记为$0_{\mathbb{F}} ,1_{\mathbb{F}} \in \mathbb{F}$

记$\mathbb{F}^*=\mathbb{F} \backslash \{0_{\mathbb{F}}\}$

$u\in \mathbb{F}$,记其对$+$的逆元为$-u$

$u\in \mathbb{F}^*$,记其对$*$的逆元为$u^{-1}$

$q$为素数时,两类特殊的有限域:

素数域$(\mathbb{F}_q,+,*)$:

由$\mathbb{Z}_q=\{0,1,2,\cdots,q-1\}$和模$q$的加法,乘法构成的有限域.

有限域$(\mathbb{F}_{q^n},+,*)$:

该域上的元素形式为$(x_0,x_1,\cdots,x_{n-1})$,其中$x_i \in \mathbb{Z}_q$

容易看出其阶为$q^n$

记$u=(u_0,u_1,\cdots,u_{n-1}),v=(v_0,v_1,\cdots,v_{n-1}) \in\mathbb{F}_{q^n}$

$u+v=(u_0+v_0 \mod q,u_1+v_1 \mod q,\cdots, u_{n-1}+v_{n-1} \mod q)$

$u*v=(u_0\times v_0 \mod q,u_1\times v_1 \mod q,\cdots, u_{n-1}\times v_{n-1} \mod q)$

$0_{\mathbb{F}_{q^n}}=(0,0,\cdots,0)$

$1_{\mathbb{F}_{q^n}}=(1,1,\cdots,1)$

$-u=(q-u_0,q-u_1,\cdots,q-u_{n-1})$

$u^{-1}=((u_0)^{q-2}\mod q,(u_1)^{q-2} \mod q,\cdots,(u_{n-1})^{q-2}\mod q)$

循环群:

定义:Abel群(交换群):

$(\mathbb{H},\cdot)$为Abel群,当且仅当满足以下条件:

封闭性
结合律
存在恒等元$e_{\mathbb{H}}$
对于每个元素$u\in \mathbb{H}$均存在逆元$u^{-1}$
交换律

设$x\in Z,h\in \mathbb{H}$,群上的幂运算按如下方式定义:

$$g^x=\underbrace{g\cdot g \cdots g}_x$$

定义:循环Abel群:

Abel群$(\mathbb{H},\cdot)$为循环Abel群,当且仅当满足以下额外条件:

存在(至少一个)生成元,记为$h$,以如下方式生成$\mathbb{H}$

$$\mathbb{H}=\{h^1,h^2,\cdots,h^{|\mathbb{H}|}\}=\{h^0,h^1,\cdots,h^{|\mathbb{H-1}|}\}$$

定义:素数阶的循环Abel群(循环群):

若生成元$g\in \mathbb{H}$,以 $$\mathbb{G}=\{g^1,g^2,\cdots,g^{|\mathbb{G}|}\}=\{g^0,g^1,\cdots,g^{|\mathbb{G-1}|}\}$$的方式生成子群$\mathbb{G}$,且

$|\mathbb{G}|$为质数
$|\mathbb{G}|$为$|\mathbb{H}|$的因数

则称$\mathbb{G}$为素数阶的循环Abel群.

素数阶的循环Abel群简称循环群(Cyclic Group)

循环群$\mathbb{G}$具有如下良好的性质:

$\mathbb{G}$是最小子群(其子群只有自身)
除$g^0$以外,元素均为生成元
可以容易地计算出逆元

要构造一个循环群,首先需要确定

元素空间$\mathbb{G}$
生成元$g$
阶$p$

可以用$(\mathbb{G},g,p)$来描述一个群.

循环群上的计算复杂性问题:

密码系统的构建,需要依赖一些容易求解的问题和难求解的问题的配合.

首先规定,在之后的讨论中,$|\mathbb{G}|\geq 2^{160}$

循环群$\mathbb{G}$上的幂运算是容易求解的,使用快速幂,需要进行的$\cdot$运算次数仅为$O(\log |\mathbb{G}|)$.

但对于离散对数问题,求解并不是那么容易.

定义:循环群$\mathbb{G}$上的离散对数问题

记$\mathbb{G}$上的恒等元为$e_{\mathbb{G}}$,$\mathbb{G}^*=\mathbb{G}\backslash \{e_{\mathbb{G}}\}$

若$g\in \mathbb{G}^*,x\in Z_p,g^x=h$,记$\log_gh=x$,

给定任意$g'\in \mathbb{G}^*,h'\in \mathbb{G}$,称求解$\log_{g'}h'$的问题为离散对数问题.

对于任意循环群$(\mathbb{G},g,p)$,求解离散对数问题的复杂度是$\Omega(\sqrt{p})$,这也就是为什么要规定$|\mathbb{G}|\geq 2^{160}$的原因.

(博主注:因为这样,$\mathbb{G}$中的每个元素只需要$160$这个数量级的比特位存储,然而现代超算每秒运行次数也不超过$10^{15}$,即使是$2^{80} \approx 10^{23}$次运算也需要三年多,这个复杂度足够了.)

(博主注:离散对数的求解方法:BSGS算法,见求解离散对数的方法:BSGS - Isakovsky - 博客园 (cnblogs.com))

(博主注:但并非所有循环群上的离散对数问题都是难解的,例如在模素数$p$加法循环群$$([0,p-1],+ \mod p)$$上,求解$$\log_gh$$只需引入整数的普通乘法$\times$,计算$g$的模$p$乘法逆元$$rev(g)=\underbrace{g\times g \cdots g}_{p-2}\mod p$$然后计算$$h \times rev(g) \mod p= \log_gh$$即可.

可能不那么直观,不妨举个例子,在循环群$$([0,1000000006],+ \mod 1000000007)$$上,幂运算的定义是$$g^x=\underbrace{(g+g+\cdots+g)}_x \mod 1000000007$$要求解$$\log_23$$只需使用整数的普通乘法$\times$计算$$rev(2)=\underbrace{(2\times 2\times \cdots \times 2)}_{1000000005} \mod 1000000007=500000004$$然后计算$$3 \times rev(2) \mod 10000000007 =500000005$$即为$$\log_23$$的值,实际上,$$2^{500000005}=\underbrace{(2+2+\cdots+2)}_{500000005} \mod 1000000007 = 3$$)