密码学学习笔记 之 introduction to mathematical cryptography

来,用 introduction to mathematical cryptography 入个门~

Lattices and Cryptography(Updating)

A congruential public key cryptosystem

首先来介绍一个低维度的NTRU。这里同你高中的朋友李华一样,我们这里的朋友仍然是Alice和Bob

preparation

Alice首先选一个要公开的大素数$q$,然后再选择他自己的私钥对$(f,g)$,其中,$f< \sqrt{\frac{q}{2}},\sqrt{\frac{q}{4}}<g<\sqrt{\frac{q}{2}} $ 并且,$gcd(f,g) = 1$,然后Alice计算她的公钥 $h \equiv f^{-1}g \pmod q$。

encryption

Alice准备接受加密信息了,于是她首先将$h$传给Bob,然后Bob准备加密消息m,他首先随机选择一个临时密钥$r$,然后需要满足$0<m< \sqrt{\frac{q}{4}},0<r<\sqrt{\frac{q}{2}} $。然后他计算密文$e \equiv rh+m \pmod q$

decryption

Alice要解密消息了,她首先计算一个$a \equiv fe \pmod q $,然后计算$b \equiv f^{-1}a \pmod g$。

proof

这里证明一波这个解密的正确性:

首先 $a \equiv fe \equiv f(rh+m)\equiv frf^{-1}g+fm\equiv rg + fm \pmod q$

然后这里我们看一下$r,g,f,m$的大小

由于$rg+fm<\sqrt{\frac{q}{2}}\sqrt{\frac{q}{2}}+\sqrt{\frac{q}{2}}\sqrt{\frac{q}{4}}<q$

所以这里这个同余符号可以扔掉了,即$a = rg+fm$

然后$b \equiv f^{-1}a \equiv f^{-1}(rg + fm)\equiv f^{-1}fm \equiv m \pmod g$

因为之前说好的 $m < \sqrt{\frac{q}{4}}<g$ , 所以这个$b=m$。

Table

来个总体流程

attack

新伙伴来了,Eve,是个hacker

他将如何破解这个低维度的NTRU呢?

解密的关键是获得私钥对$(f,g)$,而他目前能获得的是$(q,h)$

因为$h \equiv f^{-1}g \pmod q$

所以有$fh = g + rq$ ,r是某个整数

这里来一个式子 $F(1,h) - R(0,q) = (F,G)$,其中$Fh = G+Rq$

因此,Eve有两个向量$v_1=(1,h),v_2=(0,q)$,他现在只需要找到两个整系数$F,R$ 使得$L = {Fv_1+Rv_2}$是一个比较短的向量,那么这个向量就相当于Alice的私钥对了。

为啥嘞?Eve手里的两个已知向量的模长的位长(bit length)都是跟 $q$ 一个级别的,而$F,G$都小于$\sqrt{\frac{q}{2}}$,所以$(F,G)$在这个向量空间里来说是相对比较短的向量了。

那么有什么方法能够快速地获得这个短向量呢?

慢慢来,不急~

Subset-sum problems and knapsack cryptosystems

密码学中的利用knapsack problem的加密。大意就是,你公开一个序列,然后你把你的消息转为二进制,如果你消息的这一位是1,就从你序列中取处对应位置的值,最后密文就是你所有取出的值的和。

但是这样就产生一个问题,加密是加过去了。那该怎么解密呢?

蛮力攻击的时间复杂度是$O(2^n)$,就算中途相遇也只能降低到$O(2^{\frac{n}{2}})$。太难了。。。

那Alice怎么解决这个问题呢?公钥密码系统如何体现呢?别急,来了。

Alice现在的序列不一般了,她这次用的是超递增序列。什么是超递增序列呢?就是后一项是前一项的两倍+,也就意味着,后一项大于前面的所有项之和。

有超递增序列后,给你一个密文,你只需要一项一项对比过来,你就能知道加密者选取的元素是哪几个了。

这不难理解。我们将序列中的每一项放到二进制下就很明显。如果第一项的位长是2,那第二项的位长就至少是3,第三项的位长至少是4。如果你的密文最后是个2位长的,那加密者必没有用到第三项,必用到了第二项。【当然,这在每一项只能用一次的大前提下】

preparation

Alice准备加密了,首先她先整了一个超递增序列,$r = (r_1,r_2,,,r_n)$,然后她整了两个大数A和B,其中要求$B>2r_n$ 也就是B大于这个超递增序列之和啦。然后要需要$gcd(A,B)=1$,因为之后要求一个A在B下的逆。

encryption

Alice要加密了,她先用她的A和她的超递增序列生成一个新的序列M,其中$M_i \equiv Ar_i \pmod B$

这个新的序列就是Alice的公钥了,她把这个序列甩给Bob,然后Bob按照之前描述的方式,用这个序列和他的明文生成密文$S = x*M = \sum_ \limits {i=1}^{n}x_iM_i$,然后把这传给Alice

decryption

Alice要解密了,她整到了这个密文S,然后计算一波$S’ \equiv A^{-1}S \equiv A^{-1}\sum_\limits {i=1}^{n}x_iM_i\equiv A^{-1}\sum_\limits{i=1}^{n}x_iAr_i\equiv \sum_\limits{i=1}^{n}x_ir_i \pmod B$

所以这个$S’$就是密文在超递增序列下的值了,之后再像之前那样判断一下这个$S’$和序列里面每一项的关系就能解出明文了。【记得从序列大的一端开始判断,如果满足关系别忘了减掉那一项再判断下一项】

伪代码走一波

1
2
3
4
5
6
for i in reverse(r):
if s >= i:
m = '1' + m
s -= i
else:
m = '0' + m

table

来个总体流程

attention

这里出于安全性考虑,要让$r_1 > 2^n$,那$r_n > 2r_{n-1}>2^nr_1>2^{2n}$,至于为啥要求$r_1$大于这个数,俺还暂时没去深究。

如果现在假设这个n=160,那么这整个公钥的长度就大约有$2n^2 = 51200$ bits了。真顶。但是这个密码系统加密的时候没用到模运算,解密的时候也就用了一次模乘,这方面在硬件实现上似乎比RSA,Diffie-Hellman效率些。

further more

之前提到Alice最开始整的一个无序的序列,由于这玩意儿没有陷门(trapdoor),因此这无法成为一个密码系统。但自从有关LLL这个密码学大杀器的paper发表后,基于背包的密码系统出现了一个大weakness,这使得n现在要大于300了,那么私钥的长度要达到惊人的180000bits,约等于176KB,这在实际运用中有点太难顶了。

这里简短的介绍下Eve怎么去解决这个无序序列的背包问题。

first-step

Eve先整了一个矩阵$M =
\begin{bmatrix}
2&0&0&\dots&0&0&m_1 \newline
0&2&0&\dots&0&0&m_2 \newline
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots \newline
0&0&0&\dots&2&0&m_{n-1}\newline
0&0&0&\dots&0&2&m_{n}\newline
1&1&1&\dots&1&1&S\newline
\end{bmatrix}$

其中这个$m_1,m_2,m_3…$就是那个序列,S就是密文

然后Eve从这个矩阵中,把每一条行向量给整了出来,分别为$V_1,V_2,…,V_n,V_{n+1}$

我们现在假设向量$x = (x_1,x_2,x_3,…,x_n)$ 是明文,($x_i = 0$ or $1$)

那么这个格中就会有这么一条向量

$t = \sum \limits _ {i=1}^{n} x _ i V _ i - V _ {n+1} = (2x_1 - 1,2x_2 - 1,…,2x_n - 1,0)$

我们之前的$V_1,V_2$这些向量的模长,因为$m_i,S$的原因,大概都有个$2^n$吧,而这个t,因为$2x_i-1=\pm 1$,所以t的模长是$\sqrt{n}$,

所以,如果Eve知道如何找到lattice中的短向量,那么他就可以破解这玩意啦。

关于找到lattice中短向量的算法我们称之为reduction algorithm,最著名的就是LLL algorithm了,然后它还有变体LLL-BKZ。这些东西,以后再介绍啦。下面我们回到起点,来讲讲这令人迷醉的lattice

A brief review of vector spaces

Vector Spaces

在讲格之前,我们这里再回忆一些线代中比较重要的定义和想法。

首先我们来说说向量空间

向量空间就是由一系列向量构成的一个空间咯,

n维向量空间的一个基就是由n条线性无关的向量构成的

这个基里的n条线性无关的向量可以相互之间的加、减,或者一条向量自己乘以一个系数,得到的结果都在这个这个空间里。我们称之为,向量空间是闭合的。

Linear Combinations

换个说法就是,你找到n条线性无关的向量,然后把他们线性组合$w = a_1v_1+a_2v_2+\dots + a_kv_k$

其中$a_i$ 是任意的实数,把可以生成的所有的$w$组合起来为一个集合,我们就称之为${v_1,…,v_k}$的向量空间。

Independence

而所谓线性无关就是,n条线性无关的向量,其中任何一条都不能由剩下的其他向量来表示,

即式子$a_1v_1+a_2v_2+…+a_kv_k = 0$的解有且仅有一个,就是$a_1=a_2=…=a_k=0$

然后在由这n条线性无关的向量所组成的向量空间中的其他任意向量,都可以由这n条线性无关的向量来表示

Bases

显然一个向量空间不只有一个基,那么如何找到其他的基呢?

这里首先拿到一组基$v_1,,,,v_n$,然后利用这一组向量再生成另外一组向量,表示为

$w_1 = a_{11}v_1+a_{12}v_2+…+a_{1n}v_n$

$w_2 = a_{21}v_1+a_{22}v_2+…+a_{2n}v_n$

$\vdots $

$w_n = a_{n1}v_1+a_{n2}v_2+…+a_{nn}v_n$

当矩阵$M =
\begin{bmatrix}
a_{11}&a_{12}&\dots&a_{1n} \newline
a_{21}&a_{22}&\dots&a_{2n} \newline
\vdots&\vdots&\ddots&\vdots \newline
a_{n1}&a_{n2}&\dots&a_{nn} \newline
\end{bmatrix}$的行列式的值不为0

这时,$(w_1,w_2,…,w_n)$也是该向量空间的一个基了。

length, or Euclidean norm

向量$v$的模长,也叫欧几里得范数,为

$||v|| = \sqrt{x_1^2+x_2^2+…+x_m^2}$

dot product

设有向量$v=(x_1,x_2,…,x_m),w=(y_1,y_2,…,y_m)$

向量$w$和$v$的点积,即:$v\cdot w = x_1y_1 + x_2y_2+…+x_my_m$

当它们的点积结果为0,我们称$w$和$v$是正交( orthogonal )的。

此时这两个向量间的夹角是90°

当这两个向量间的夹角不是90°时,我们设之为θ

则$v\cdot w = ||v||||w||cos(θ)$

这里有个著名的不等式,即为柯西不等式(Cauchy–Schwarz inequality)$|v\cdot w|≤||v||||w||$

orthogonal basis

如果一个向量空间的积两两正交,我们称这组基为这个向量空间的orthogonal basis 俺叫他正交基,如果里头的每个向量的欧几里得范式都为1,那么它将再次进化,得到称号 orthonormal basis,俺叫他标准正交基。

正交基可以让一些事情变得简单。

比如,我们有一组正交基$v_1,v_2,…,v_n$,而 $v = a_1v_1+…+a_nv_n$是这组正交基 的某个线性组合。那么有:

$||v||^2 = ||a_1v_1+..a_nv_n||^2 = (a_1v_1+…+a_nv_n)\cdot(a_1v_1+…+a_nv_n)$

$=\sum_\limits{i=1}^{n}\sum_\limits{j=1}^{n}a_ia_j(v_i\cdot v_j)$

$=\sum_\limits{i=1}^{n}a_i^2||v_i^2||$

如果是标准正交基,那就直接$||v||^2 = \sum_\limits{i=1}^n a_i^2$就好了

然后这里有一个方法,叫做Gram–Schmidt Algorithm,可以整出一个正交基来。

Gram–Schmidt Algorithm

假设我们有一组基,$v_1,v_2,…,v_n$,然后设这个向量空间的正交基为$v^_1,v^_2,…,v^*_n$

上伪代码:

Set $v^*_1 = v_1$

Loop $i=2,3,…,n$

  Compute $μ_{ij} = \frac{v_i \cdot v^ * _j}{||v^ * _j||^2}$ for $1≤j<i$

  Set $v^ * _ i = v_ i - \sum_\limits{j=1}^{i-1}μ_ {ij}v^ * _ j$

End Loop

这里的正交基里头的向量我们是一个一个找的,每找后一个,都要用到前面已经找好的属于正交基的向量。

(PS:这个算法是用在LLL里头的,有关LLL的文章可以看这篇Building Lattice Reduction (LLL) Intuition

proof

这里证明一下$v_i^ *$与其他已经找到的相互正交的向量$v_1^ *,v_2^ *,,,v_{i-1}^ *$是正交的。那我们就随便设一个k,$k<i$,

计算 $v^ * _ i\cdot v^ * _ k = (v _ i - \sum _ \limits{j=1}^{i-1}μ _ {ij}v _ j^ * )\cdot v _ k^ * $

$∵v_k^ *\cdot v_j^ *=0$( 当$j≠k$)

$∴v^ * _ i\cdot v^ * _ k = (v _ i - \sum _ \limits{j=1}^{i-1}μ _ {ij}v_j^ * )\cdot v _ k^ * =v _ i\cdot v _ k^ * -μ _ {ik}||v _ k^ * ||^2 = v _ i\cdot v _ k^ * -v _ i\cdot v _ k^ * =0$

(PS:有点像数学归纳法哈~)

Lattices: Basic definitions and properties

好了,终于要开始正式的lattice相关的内容了。

lattice

其实格很像向量空间

假设格的一组基$v_1,,,,v_n$,然后格里还有另一组向量$w_1,…,w_n$,可以表示为

$w_1 = a_{11}v_1+a_{12}v_2+…+a_{1n}v_n$

$w_2 = a_{21}v_1+a_{22}v_2+…+a_{2n}v_n$

$\vdots $

$w_n = a_{n1}v_1+a_{n2}v_2+…+a_{nn}v_n$

系数矩阵$A =
\begin{bmatrix}
a_{11}&a_{12}&\dots&a_{1n}\newline
a_{21}&a_{22}&\dots&a_{2n}\newline
\vdots&\vdots&\ddots&\vdots\newline
a_{n1}&a_{n2}&\dots&a_{nn}\newline
\end{bmatrix}$

因为我们现在是格,所以这个矩阵里的所有数都是整数,从而有:

$1 = det(I) = det(AA^{-1})=det(A)det(A^{-1})$

因为$det(A)$是一个整数,所以我们有$det(A)=\pm 1$

由此可以得出一个很有趣的结论:格的两组基可以通过一个行列式为1的矩阵相互转换。

e.g.

我们考虑一个三维格$L$,然后我们拿到了三个向量

$v_1 = (2,1,3),v_2=(1,2,0),v_3=(2,-3,-5)$作为矩阵A的行向量,$A =
\begin{bmatrix}
2&1&3\newline
1&2&0\newline
2&-3&-5\newline
\end{bmatrix}$

然后我们创建属于$L$的三个新的向量

$w_1=v_1+v_3,w_2=v_1-v_2+2v_3,w_3=v_1+2v_2$

这相当于将左边的矩阵A乘以矩阵$U =
\begin{bmatrix}
1&0&1\newline
1&-1&2\newline
1&2&0\newline
\end{bmatrix}$,

然后我们就发现$w_1,w_2,w_3$是矩阵$B=UA=\begin{bmatrix}
4&-2&-2\newline
5&-7&-7\newline
4&5&3\newline
\end{bmatrix}$的行向量。

然后又因为$det(U)=-1$,所以向量$w_1,w_2,w_3$也是格$L$的基,

并且矩阵$U$的逆矩阵$U^{-1}=\begin{bmatrix}
4&-2&-1\newline
-2&1&1\newline
-3&2&1\newline
\end{bmatrix}$的行向量说明了怎么用$w_i$来表示$v_i$,即

$v_1=4w_1-2w_2-w_3,v_2=-2w_1+w_2+w_3,v_3=-3w_1+2w_2+w_3$

discrete additive subgroup

格也可以被定义为可加离散子群,因为格中任何一个格点的周围都是空旷的,不显得很离散么?

这里有一个Theorem说,一个m维向量空间的子集,当且仅当它是一个离散可加子群是,我们称之为格。

其实格也是某种意义上的向量空间,只不过他的一个基的 所有向量的 线性组合的 系数都是整数( all linear combinations of its basis vectors using integer coefficients)。我们可以把格视为在一个空间中一系列排序规则的点集。

fundamental domain

这里我们又有一个定义,叫做fundamental domain,我们用式子来表示这个东西,就是

$F(v_1,…,v_n)={t_1v_1+t_2v_2+…+t_nv_n:0≤t_i<1}$,就是下图中阴影部分

显然,这些fundamental domain不止一块,其他的块可以由这一块和格中的向量表示为

$F + v = {t+v:t∈F}$

这里我们可以把这个fundamental domain看作是由向量包围而成的一个四边形。在给定向量的长度后,当向量间相互正交,此时这个fundamental domain的面积达到最大。

这引出了下面一个关于格的行列式的上界的理论。

Hadamard’s Inequality

设$L$是一个格,其一组基为$v_1,v_2,…,v_n$,设$F$为$L$的一个fundamental domain,那么有

$det(L)=Vol(F)≤||v_1||||v_2||\dots ||v_n||$

当这一组基趋于相互正交时,不等式两边的值趋于一致,$Vol$可以看作是F的长度,面积,体积等度量,随维度的变化其有不同的含义。

这似乎还给出了一个计算格$L$行列式的简单方法。(具体计算细节涉及到多变量微积分,是高数,awsl)

即$|det(F(v_1,v_2,…,v_n))| = Vol(F(v_1,…,v_n))=det(L)$

这里的$v_i$不是格$L$的向量$v_i$,是${F(v_1,…,v_n)={t_1v_1+t_2v_2+…+t_nv_n:0≤t_i<1}}$里的$v_i$

e.g.

$det(L) = |det (A)|=|-36|=36$,这里的A就上面那个e.g.中的那个$A =
\begin{bmatrix}
2&1&3\newline
1&2&0\newline
2&-3&-5\newline
\end{bmatrix}$

det(L) is an invariant

对于给定的一个L,图之前的图上来看,显然$Vol(F)$是固定的,所以$det(L)$也是一个定值

proof

我们设$L$的两个 fundamental domains $v_1,v_2,…,v_n ;w_1,w_2,…,w_n$ (这里的向量$v_i$也不是格$L$里的向量)

然后我们有$F(v_1,…,v_n) = AF(w_1,…,w_n)$ 【这个定义在这一章的最前面,类比格的两组基可以通过一个行列式为1的矩阵相互转换】

所有我们有:

$Vol(F(v_1,…,v_n))$

$=|det(F(v_1,…,v_n))|$

$=|det(AF(w_1,…,w_n))|$

$∵det(AB)=det(A)det(B)$

$=|det(A)||det(F(w_1,…,w_n))| $

$∵det(A)=\pm1$

$=|det(F(w_1,…,w_n))|$

$=|Vol(F(w_1,…,w_n))|$

Short vectors in lattices

系统中断,这边要咕咕咕一会儿了。。。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 643713081@qq.com

文章标题:密码学学习笔记 之 introduction to mathematical cryptography

文章字数:4.3k

本文作者:Van1sh

发布时间:2020-05-27, 21:05:00

最后更新:2020-07-26, 12:41:25

原始链接:http://jayxv.github.io/2020/05/27/密码学学习笔记之introduction to mathematical cryptography/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏