格密码学习笔记

前言

这篇文档的目的是促使我更认真的学习格密码,要搞懂过程和原理,打好基础,由于是学习的笔记所以可能比较长。。。。

主要记录的就是一些密码的基本原理,和一些格的基础知识。

当然学了密码的加密解密过程,最重要的还是要自己写一个加解密的脚本出来,或者再想想还有没有什么变体之类的,自己出题给自己做,一方面可以强化自己写脚本的能力,还有就是深化了对密码的理解

A Congruential Public Key Cryptosystem(NTRU密钥系统)

首先讲讲加密过程:

密钥生成

选择一个大正整数 $q$ 作为模数

选择$f$ 和 $g$ 作为私钥,并且 $f$ 和 $g$ 满足 $f < \sqrt\frac q2,\sqrt\frac q4<g<\sqrt\frac q2,gcd(f,qg)=1$

计算$h \equiv f^{-1}g \quad(mod\ q)$

$(f,g)为私钥,(q,h)为公钥$

加密

选取随机数 $0<r<\sqrt\frac q2$ ,明文 $m$ 满足 $m< \sqrt \frac q4,计算密文e\equiv rh+m \quad (mod\ q)$

解密

计算辅助值$a \equiv fe \quad (mod\ q)$

计算 $b \equiv f^{-1}a\quad(mod\ g),b=m$

正确性证明

$a \equiv fe \equiv frh+fm \equiv ff^{-1}rg+fm\equiv rg+fm\quad(mod\ q)$

$\because f<\sqrt \frac q2,\ g<\sqrt \frac q2,\ m<\sqrt \frac q4,\quad\therefore rg<\frac q2\quad \therefore fm<\frac q{2\sqrt2}$

$可以得到rg+fm<q,\ \therefore a = rg+fm,\ 而不是mod\ q后的余数$

$则b \equiv f^{-1}rg+f^{-1}fm\quad (mod\ g),注意这里f^{-1}是f对g的逆元,而这里的f就是真实的f,$$所以f^{-1}f\quad \equiv1(mod\ g),又因为f^{-1}rg一定是g的倍数,所以mod\ g后为0,因此b=m$

这里贴一张流程图

1

攻击

如何破解这个密钥系统涉及到$SVP$问题,后面在讲。。。。(因为还没有学完)


Subset-Sum Problems and Knapsack Cryptosystems(子集和问题与背包问题)

子集和问题:
有由一系列正整数构成的集合M与一个正整数S,找到一个或多个M的子集其元素的和等于S

例如有M={2,3,4,9,14,23},S=21,可以很容易的得出有M的子集{3,4,14}的和等于S

用数学的表示方法来描述这个问题:

$$ M=\lbrace M_1,M_2,…,M_n\rbrace $$

并且选择另一个二元向量

$$ X=\lbrace x_1,x_2,…,x_n\rbrace\quad(x_i\in\lbrace0,1\rbrace) $$

$$ S=\sum_{i=1}^n x_iM_i $$

如果要遍历整个二元向量,即遍历$2^n$次,需要很长时间,**碰撞算法(collision algorithm)**可以将时间减半

$使I\subset\lbrace i:1\leq i\leq\frac12n\rbrace,\ J\subset\lbrace j:\frac12n\leq j\leq n\rbrace$

计算

$$ A_I=\sum_{i\in I}M_i\quad and\quad B_J=S-\sum_{j\in J}M_j $$

$若存在一对I_0和J_0使A_{I_0}=B_{J_0},则可以解决这个问题$

$$ S=\sum_{i\in I_0}M_i + \sum_{j \in J_0}Mj $$

如果n很大,M又是一个随机序列,那么解决子集和很难。但有没有一个特殊的序列可以很好的解决这个问题。答案是有的

超递增序列(superincreasing sequence)

正实数序列$(s_1,s_2,…s_n)$如果序列的每个元素都大于序列中所有先前元素的总和,则称为超递增

从形式上讲,此条件可以写为

$$ s_{n+1}=\sum_{i=1}^ns_i $$

超递增序列的另一条性质:

$$ r_{i+1}\geq2r_i\quad (1\leq i\leq n-1) $$

在超递增序列中解决子集和问题是简单的,可以用一下算法解决:

for i in range(1, len(M)+1):
	if S >= M[-i]:
		x.insert(0,1)
		S -= M[-i]
	else:
		x.insert(0,0)

密码系统

基于超递增序列可以创造出一种密码系统

生成密钥

$选择一个超递增序列r=(r_1,r_2,…r_n),和两个大整数A,B$

$A,B满足B>2r_n,\quad gcd(A,B)=1$

生成一个新的序列M(非超递增序列)

$$ M_i\equiv Ar_i\ (mod\ B) $$

$M$为公钥,$(A,B)$为私钥

加密

将明文转为二元向量$x$,bin(s2n(m))[2:]

计算密文$S$

$$ S=x\cdot M=\sum_{i=1}^nx_iM_i $$

解密

$$ 计算S^\prime\equiv A^{-1}S\ (mod\ B)$$

$$ 然后用上面说的算法计算明文x $$

证明正确性

$$ S^\prime\equiv A^{-1}S\equiv A^{-1}\sum_{i=1}^nx_iM_i\equiv A^{-1}\sum_{i=1}^nx_iAr_i\equiv\sum_{i=1}^nx_ir_i\ (mod\ B)$$ $$由于B>2r_n,且\sum_{i=1}^nx_ir_i<2r_n,\ \therefore S^\prime=\sum_{i=1}^nx_ir_i,而非同余 $$

还是贴一张流程图:

安全性

下次把。。。看这个英文的书籍是真的累。。。:cry:

向量空间(Vector Spaces)

终于到有关于格的基本知识了,前面两个引子看了大概一天多了wc,我看的是真的慢啊

向量空间$V$是$R^m$的子集($R^m$是$m$维的实数集)

$$ \alpha_1v_1+\alpha_2v_2 \in V \quad \alpha_1,\alpha_2\in R $$

也就是说向量空间V在加法和数乘运算下是闭合的

$若 v_1,v_2,…,v_n \in V, v_1,v_2,…,v_n所有的线性组合w=\alpha_1v_1+…+\alpha_nv_n,\alpha_i\in R,$

$构成的集合称为v_1,…,v_n的span$

线性相关性

这里就看线代数吧,不想写了。。。。。还是懒,主要是这里我感觉学的挺好的,毕竟线代考试满分。。。。。

基向量的一些性质

$令V\subset R^m是一个向量空间$

$(a)V一定有一组基向量$

$(b)任意两个基向量拥有相同数量的元素,元素的数量n称为向量空间V的维数$

$(c)令\ v_1,…,v_n\ 是V的一组基,令w1,…,2_n\ 是另一组向量,w_j可以由v_j线性表出$

$$w_1=\alpha_{11}v_1+\alpha_{12}v_2+…+\alpha_{1n}v_n\\ w_2=\alpha_{21}v_1+\alpha_{22}v_2+…+\alpha_{2n}v_n\\ \vdots\quad\quad\quad\quad\quad\quad\vdots\\ w_n=\alpha_{n1}v_1+\alpha_{n2}v_2+…+\alpha_{nn}v_n $$

$如果w_1,…,w_n\ 也是V的一组基,那么当且仅当以下矩阵的行列式$

$$ \begin{pmatrix}\alpha_{11}&\alpha_{12}\cdots\alpha_{1n}\\ \alpha_{21}&\alpha_{22}\ \cdots\alpha_{2n}\\ \vdots&\vdots\\ \alpha_{n1}&\alpha_{n2}\cdots\alpha_{nn}\end{pmatrix}=0$$

定义

用坐标来表示向量空间$V$中的向量$v,w$

$$ v=(x_1,x_2,…,x_m)\quad和\quad w=(y_1,y_2,…,y_n) $$

$则v和w的点积也就是数量积为$

$$ v\cdot w=x_1y_1+x_2y_2+…+x_my_m $$

$还可以记为v和w的内积[v,w]$

若$[v,w]=0,则称v,w正交$

$向量v的模(欧几里得范数)记为$

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

$$并且有\quad[v,v]=||v||^2 $$

柯西-施瓦茨不等式

$$ |v\cdot w|\leq ||v||\ ||w|| $$

证明

$$设\quad f(t)=||v-tw||^2\quad展开后是关于t的二次函数,容易知道对于任意的t都有f(t)\geq0\然后f(t)的最小值也是大于等于0,移项一下就得到了$$

施密特正交化

看课本吧

向量空间的一组正交基要求两两正交

格的基础定义

格空间

跟向量空间差不多,取定一个线性无关的向量组$v_i(i \in(1,n))$,格$L$由向量组$v_i$生成,则$L$是$v_i$的线性组合,只不过系数在整数域$Z$

格基的一些性质

$若w,v均为格L的基,那么w可以由v表示,w=Av,其中系数矩阵A的行列式满足det(A)=\pm1$

证明

证明过程很简单,因为$w,v$均为$L$的基,所以它们可以互相表示,$w=Av,同时v=A^{-1}w$,由于都在格空间所以$A和A^{-1}的元素都是整数,又因为|A|\ |A^{-1}|=1,所以有|A|=\pm1$

基础域(基础平行六面体)