计算机安全(1)

少量概念

CIA

即Confidentiality(保密性)、Integrity(完整性)、Availability(可用性)

TCSEC、ITSEC、CC

计算机安全的标准,按时间排序,TCSEC最先提出了TCB(可信计算基)与访问控制机制,ITSEC提出了CIA,CC即现行的信息技术安全评估通用准则。

符号

P:Plain Text,即明文。

C:Cipher Text,即密文。

E:Encrypt,即加密。C=E(P)

D:Decrypt,即解密。P=D(C)

一个密码系统必须满足P=D(E(P))

分类

经典密码

即对称加密,加密与解密的密钥相同或能相互推导。包括DES、AES等。

公开密钥算法

非对称加密,加密使用公开的Pulic Key,解密使用私有的Private Key。包括RSA等,支持实现数字签名。

密码分析

包括穷举、统计分析、数学分析。

安全性

仅一次一密能达到无条件安全,但只要解密成本大于信息价值,或解密时间超过信息有效期即达到安全目的。

经典密码

替换技术

将明文替换成密文,可以用单表或多表,也可以替换单个字符或连续字符。

多字母替代:playfair

双字母作为一个单元,遇到连续的字母需要添加分隔符X,如果字符串长度是奇数补一个Q,然后对照5x5的密码表(英文有26个字母,所以将i、j视为同一字母),同行的字母右移,同列的字母下移,其他字母取形成的矩形的另外两角。

如密钥为gojam(密钥不能有重复字母),可以制成如下密码表:

g o j a m

b c d e f

h k l n p

q r s t u

v w x y z

现在加密明文“HeEatApple”,首先添加分隔符X,变成“HeXEatApXple”,刚好可以分为六组HE XE AT AP XP LE。

HE对应BN。(我默认了左下角对应左上角,右上角对应右下角)

XE对应DY。

AT对应EY。

AP对应NM。

XP对应LZ。

LE对应DN。

因此密文为BNDYEYNMLZ。

解密过程与加密过程相反,聪明的你一定可以解出来。

多字母替代:Hill Cipher 希尔密码

基于矩阵的线性变换,将m个连续字符转为m个密文。密钥K是m*m的矩阵,在模26运算中可逆,即K*K^-1=I(mod 26)。

加密时m个连续明文作为行向量与密钥K相乘并mod26,解密时m个连续密文与K^-1相乘并mod26。

矩阵乘法

a行b列的a*b矩阵与b行c列的b*c矩阵相乘,最终得到的矩阵a行c列。(即第一个矩阵的宽应该与第二个矩阵的高相同,否则可能无法相乘)

得到的a*c矩阵中,用C[i,j]表示第i行第j列元素,用A[i,j]与B[i,j]表示前两个矩阵的第i行第j列元素,有以下关系:

C[i, j]=A[i, 0]*B[0, j]+A[i,1]*B[1,j]+A[i,2]*B[2,j]+...+A[i, b]*B[b, j]

例如C[0,0]=A[0,0]*B[0,0]+A[0,1]*B[1,0] +A[0,2]*B[2,0]+...+A[0,b]*B[b,0]

也就是第一个矩阵的第一行乘以第二个矩阵的第一列,第一个矩阵的第一行乘以第二个矩阵的第二列,依次这样。

代数余子式

对矩阵A中的元素A(i,j),将第i行与第j列从矩阵A中移去,余下的部分作为行列式的值再乘以(-1)^(i+j)得到的数叫A[i,j]的代数余子式。

以A=[[3,2],[1,1]]作为例子,A(0,0)的代数余子式为1*(-1)^(0+0)即1。同理A(0,1)=-1,A(1,0)=-2,A(1,1)=3。

伴随矩阵

像上面由各个位置的代数余子式构成的矩阵被称为伴随矩阵,A的伴随矩阵A*=[[1,-1],[-2,3]]。

求逆矩阵

逆矩阵A^-1=A*/|A|,其中|A|代表A的行列式,等于3*1-2*1=1。

A*是转置后的伴随矩阵,因此A*=[[1,-2],[-1,3]]。

因此逆矩阵A^-1=[[1,-2],[-1,3]]。验证A乘以A^-1=[[1,0],[0,1]],即单位矩阵(对角线全是1,其余部分全是0)。

加密/解密

以上2*2矩阵作为例子,如明文为XD,即[23,3](26字母从0开始,25结束),乘以A等于[23*3+3*1,23*2+3*1]=[72,49],然后mod26=[20,23],即UX。

解密时[20,23]乘以A^-1,等于[20*1-23,20*(-2)+23*3]=[-3,29],mod26后等于[23,3]。

这种加密方式能够防止只有密文的统计学攻击,因为密钥矩阵本身包含了信息,不同频率的字符被分散到了不同密文。但如果有很多明文-密码对,或者攻击者可以获取各种明文的密码,那么密钥K很容易被计算出来。

置换技术

传统密码的两个要点,即替换与置换,交换位置能更好地保密信息。