密码学应用在生活中的方方面面,而基于数学的密码学也被广泛应用于各个场景之中,如银行加密等,现在来回顾一下几个概念。

1.密码学简介

密码学是信息安全的一个重要基础和分支,是一门古老而新兴的学科。它的主要研究范围是密码系统和通信安全,但办函内容十分广泛,不仅局限于我们常用的口令和耳熟能详的信息加密和解密。

密码学分为密码编码学和密码分析学。前者主要研究如何对信息进行编码之后对信息的保护作用,包括保护其机密性、认证性、完整性等。后者则截然相反,它是通过对编码信息的分析来去除或者削弱由编码带来信息的保护,例如,破译消息、篡改消息、伪造信息等。

2.对称密码(单钥密码)

2.1 简介

简单来说,对称密码的对称指的是加密和解密的过程互为逆运算,常见的例子,如Alice要与Bob通信,不能够直接发送明文,因为在信道中传输的过程中可能会被窃听,这时,我们需要一种加密手段,如图2-1所示:

2.png

图2-1

这里的数字e被称为密钥,加密遵循从明文到密文再到明文的过程。当然,实际的算法比这都要复杂。例如,明文可以乘以e,那么解密除以e就可以了。常见的对称密钥加密模型,如下图2-2所示:
1.png
图2-2

2.2 流密码

简单来说,在流密码加密体系之中,加密就是明文流和密钥流进行逐位的异或运算,输出的密文Ci=Ek(Pi⊕Ci-1)。流密码主要就是指利用一个密钥流生成器产生一个密钥流,然后用这个密钥流来对明文消息进行加密和解密。

流密码算法分为两种,一种是同步流密码,另一种是自同步流密码。区分的关键在于是否生成的密钥流与明文相关(前者无关,后者相关)。其核心问题是密钥流生成器的问题。流密码算法具有速度快、效率高、加解密对称的优点,并且研究分析透彻,有着很深的数学理论基础,是核心密码中的主流密码。例如RC4、美国的eSTREAM。

流密码算法一般是由移位寄存器来实现的,因此更有利于硬件实现。对于视频流的加解密时,一般采用流密码算法,移位寄存器包括线性移位寄存器和非线性移位寄存器两种。
- 根据西安电子科技大学李晖教授的课程,线性移位寄存器用于产生周期较大的伪随机序列。
- 非线性移位寄存器则用于产生非线性序列,因为非线性,可以保证序列的复杂性和安全性。

实际应用中,往往会先进行线性变换后再进行非线性变换,提高安全性。

2.3 分组密码

分组密码是许多系统安全的一个重要组成部分,用于构造:

  • 拟密码生成器
  • 流密码
  • 消息认证码(MAC)和杂凑函数
  • 消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分

2.3.1 DES算法

  • 分组长度为64bits(8 bytes)
  • 密码分组长度也是64bits
  • 密钥长度为64 bits,有8 bits奇偶校验,有效密钥长度为56 bits
  • 算法主要包括:初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥生成器。

由上述描述可知,对于DES来说,它加密的明文数据仅有64bit,而且在这64bit的数据中,还有8位要用于奇偶校验,这样以来,大大削减了DES的加密安全性,因为其有效密钥只有56位,对于小数据的信息加密还具有一定的保密性,但是我们日常对于一些数据量较大的信息加密时,由于各次迭代中使用的密钥K是递推产生的,这种相关性必然降低了密码体制的安全性。

其实我们如果使用穷举搜索法,不仅耗时耗材耗力,也大大拉长了破解的周期,针对于目前的计算技术以及DES加密技术的分析来看,采用16轮迭代的DES加密技术,在一定程度上仍然是可以保证安全的,但是对于16轮以下的DES加密技术,我们应该谨慎使用。

尽管如此,我们仍然需要不断的对DES算法进行进一步的改进,主要的改进方案就是通过增加密钥长度,来确保加密算法的安全性、保密性。DES算法是两种加密技术的组合:混乱和扩散。

2.3.2 AES算法

  • AES是公开的
  • AES为单钥体制分组密码
  • AES的密钥长度可变,可按需要变大
  • AES适用于软件和硬件实现

分组和密钥长度可变,可各自独立指定为128、192、256比特。加密时,AES算法的加密过程都包含4个步骤:

  1. SubBytes(字节代替):通过非线性替换函数,用查找表的方式,独立的对每个字节进行替换。代换表 (也就是S-盒) 都是可逆(也就是说替换以后的字节可以通过查表找到原始的字节)。

  2. ShiftRows(行移位):目的就是将矩阵中的横和列,进行循环式移位。

  3. MixColumns(列混淆):列混淆的方法就是使用线性转换将每列的四个字节进行混合。为了充分混合矩阵中各个行,而进行的一步。

  4. AddRoundKey(轮密钥加):矩阵中的各个字节都要与轮秘钥进行异或(XOR)运算,从而生产子密钥。

3.非对称密码(双钥密码、非对称密码)

因为公钥和私钥之间是不对称的,所以得名非对称密码体制。由于同时具有公钥、私钥两种完全不同类型的密钥,所以又称双钥体制。

在非对称密码之中,多使用公钥加密,而用私钥解密,这多用于保密数据的机密性。下面以RSA密码为例,简单描述非对称密码的特点。

3.1数论简介

  1. 素数和互素数
  • 素数:对于自然数p来说,除了1和p本身,再没有其他的因子了,称为素数。
  • 设c是a和b最大公因子,c=gcd(a,b)
    c是a的因子也是b的因子
    a和b的任一公因子也是c的因子 gcd(a,b)=1,称为a,b互素
  1. 模运算,设n是一正整数,a是整数,若a=qn+r,0<=r<n,则a mod n=r;

  2. 费尔马定理

  3. 欧拉函数

  • 设n为以正整数,小于n且与n互素的正整数的个数称为n的欧拉函数,记为j(n)
  • 定理:若n是两个素数p和q的乘积,则j(n)=j(p)* j(q)=(p-1)* (q-1)
  1. 欧拉定理

3.2 RSA加密

  1. 找出质数p,q

  2. n=p*q

  3. φ(n)=(p-1)* (q-1) 这一项称为欧拉函数

  4. 公钥e 其中1<e<φ(n) e和φ(n)互质 私钥为d e* d modφ(n)=1
    例如其中e=3 d=7 这样取φ(n)=20 则满足条件


加密:明文为m,则m的e次幂除以n,其余数为C
解密:密文为c,则除以n,从数学上可以证明,其余数必为m

从上述问题可以得知:
- 传播:n、e、c(密文)
- 解密:n、d(私钥,解密密钥)、c

正是由于窃听者只能够获取到n、e、c,得不到d,所以密文无法被破译,下面就如何得到d进行讨论:
由e* d modφ(n)=1可知,求φ(n)要先把n质因数分解,也就是p和q,看到这里有读者可能会疑惑了,认为质因数分解容易,不就是小学学过的。实际上,在商业应用中,大整数的质因数分解很困难,RSA算法常用1024位的2进制数,基本不可能进行质因数分解,人类目前做不到。这样,就基本杜绝了被窃听者解密的可能。

3.3 椭圆曲线密码体制


短暂地别离是为了更好地相逢