数学问题在现代密码学学习中的应用

数学作为一门自然科学,在人们的日常生活和学习中有着许多不可或缺的应用,在人们生活的各个方面均能看见数学的应用。作为信息安全专业的学生,这里,我们主要探讨数学在现代密码学中的应用与作用。

一般认为,1949年香农发表的《保密系统的通信理论》(Communication Theory of Secrecy System)一文开启了现代密码学的先河。最初,密码技术被其爱好者进行了深入广泛的研究,此时的密码学主要应用于外交、军事和政府等领域。密码学的学术研究始于20世纪70年代中期,1976年以前的所有密码系统均属于对称密码学范畴。1976年,Diffie和Hellman《密码学的新方向》一文的发表,使密码学研究步入一个新的时代。随后,随着密码算法与技术的进步与改进,密码学开始走进人们的日常生活中。现在,几乎每个人每天都在使用与密码有关的各种产品,如连接到无线网络、用银行卡在实体店或网上购物、收发电子邮件、拨打语音电话等。毋庸置疑,密码产品在保障信息安全领域起着不可替代的作用,因此密码产品的安全性更为重要。决定一个密码产品安全与否的条件是其使用的密码算法与密钥是否足够安全,而决定密码算法与密钥是否安全的因素是其基于的数学原理是否安全。当一个密码算法是建立在某一个数学问题的难解性之上,使用已知的算法与现有的计算工具不可能完成攻击所要求的计算量时,我们认为此算法是计算上安全的。在实际运用中,一般要求破解密码系统的成本不能超过被加密信息本身的价值,且破译密码系统的时间不能超过被加密信息的有效生命周期,我们称在此约束条件下无法破译的密码体制满足实际安全性。密码学的一个重要应用即为以DES、AES等为代表的对称密码算法。

对称密码算法是加密与解密过程中使用相同密钥的密码算法,解密算法一般是加密算法的逆运算。以数据加密标准(Data Encryption Standard, DES)为例,其加密时有16轮算术逻辑和非线性运算,解密时也有16轮与之对应的逆运算。在加密阶段,为实现混淆,使用了初始置换IP代换,则解密阶段使用其逆运算IP-1进行代换。IP序列与IP-1如图1所示,从图中可以看出IP表与IP-1表是有关联的。为了保证安全,除了一般的线性运算与确定的替换外,DES算法还引入了非线性的S盒。DES包含8个S盒,分别对应着8个非线性的代换表,其功能就是进行非线性代换,使得S(a)⨁S(b) ≠ S(ab)。其中第一个S盒如图2所示。但由于DES的密钥长度过短(56比特),随着技术水平的提升,破解DES变得越来越容易。到90年代后期,短短几个小时内就可以完成DES的破译,单重DES已经不能满足实际的需要了。此时,更安全的高级加密算法(Advanced Encryption Standard, AES)已被选出,并作为新的商用数据保密的秘密算法,于2002年正式生效。

图1  初始变换IP和逆初始变换IP-1

(IP表中的第1位是58,IP-1表中的第58位是1)

图2  S盒S1

由于对称密码体制中加解密需要的密钥是相同的,所以密钥的传输需要严格的保密,要在安全的信道中进行通信,而安全信道是不易实现的。同时,对称密码体制还存在密钥管理问题与数字签名问题等,随着计算机和网络的飞速发展,其局限性逐渐显现出来。1976年,Diffie和Hellman在论文《密码学的新方向》(New Direction in Cryptography)中首次提出了公钥密码思想:用户A有一对密钥:加密密钥Pk和解密密钥Sk,公开Pk,保密Sk,若B要给A发送加密信息,他需要在公开的目录中查出A的公钥Pk,用它加密信息;A收到密文后,用自己的私钥Sk解密密文,由于别人不知道Sk,即使截获了密文,也无法恢复明文。1978年,RSA算法提出,并得以广泛的应用。RSA的基础是数论的欧拉定理,它的安全性依赖于大整数因子分解的困难性。

RSA密钥生成算法分为以下几个步骤:

  • 选取两个安全大素数pq(“大”指其长度要足够长,目前推荐长度为至少1024比特);
  • 计算乘积n=p×q, φ(n)=(p-1)(q-1),其中φ(n)为n的欧拉函数;
  • 随机选取整数e (1<e<φ(n))作为公钥,要求满足gcd(eφ(n))=1,即eφ(n)互素;
  • 用扩展欧几里得算法计算私钥d,以满足d×e≡1 mod φ(n),即en是公钥,d是私钥。

算法中pq不能泄露。设明文为m,则加密时,密文me mod n,解密得到明文cd mod n

可以看出,数学知识在现代密码学中的应用非常广泛。在对称密钥体制中,会用到线性代数的知识进行求解,在非对称(公钥)密码体制中,数论等知识随处可见。欧几里得算法(Euclidean Algorithm, EA)使得求两个数(pq)的最大公约数gcd(p, q)变得简便,扩展欧几里得算法(Extended Euclidean Algorithm, EEA)在求其逆元方面作用很大。此外,欧拉定理、费马小定理等都在公钥密码体制中都起到了重要作用。

除了RSA算法外,在现代密码学中常用的算法还有基于有限域上离散对数问题的公钥加密体制ElGamal加密体制、基于椭圆曲线的离散密码体制ECC等。ElGamal加密体制如表1。

表1  ElGamal公钥加密算法

密钥生成算法 公钥 p:大素数;g:生成元 gZp*

y≡ gx mod p

私钥 x:1<x<p-1
加密算法 ri: 随机选择,1<ri<p-1

密文:c≡ g^(ri ) mod pci‘ ≡ mi y^(ri ) mod p

解密算法 明文:mi ≡ (ci)/(cix ) mod p

ElGamal算法的安全性基于离散对数求解的困难性。目前对离散对数问题的研究取得了一些成果,已经有了一些攻击算离散对数的算法,如小步大步法、指数积分法等。椭圆曲线密码算法如表2所示。ECC的安全性基于椭圆曲线上的离散对数问题的难解性,它优于基于有限乘法群上的离散对数密码体制。

表2  ECC算法

密钥生成算法 公钥 E:椭圆曲线yx3+ax+b mod p

n: 非常大的素数

G:椭圆曲线Ep(a, b)的生成元,nG=O

PBPB=nBG

私钥 nBPB=nBG
加密算法 kPt(xt, yt):随机选择

m:明文信息

P1=(x1, y1)=kG, P2=(x2, y2)=kPB

C=mxt+yt

加密数据:Cm=(kG, Pt+kPB ,C )

解密算法 Pt+kPBnB (kG) = Pt + k(nBG) – nB (kG)=Pt = (xt, yt)

明文:m=(Cyt)/xt

总体来说,大学数学在现代密码学的学习中起到了很重要的作用。线性代数知识在线性移位反馈寄存器(Linear Feedback Shift Registers, LFSR)的求解、AES的字节代换过程等起着关键作用,离散数学、数论等知识在AES算法、公钥密码算法中的应用增强了密码算法的安全性,在保障人们信息安全方面的作用不可替代。

 

参考文献:

[1] Christof Paar, Jan Pelzl. Understanding Cryptography. Springer. 2010

[2] 谷利泽,郑世慧,杨义先. 《现代密码学教程(第2版)》. 北京邮电大学出版社. 2015年3月

[3] (美)Christof Paar, Jan Pelzl著,马小婷译. 《深入浅出密码学——常用加密技术原理与应用》. 清华大学出版社. 2012年9月

(本文为中国民航大学2015-2016学年第一学期《数学学科导论》课程作业,完成时间为2015年11月18日。)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据