分类
综合技术

XDMSC技术沙龙:密码学简介

前一段时间,中国发布了密码法,西电的密码学一直位于全国第一,AI柠檬曾在西电微软学生俱乐部的技术沙龙活动中,为学弟学妹们介绍密码学的基础知识,相关加密算法等,希望有更多的同学对密码学感兴趣。

(在苹果系统下,如果文章中的图片不能正常显示,请升级Safari浏览器到最新版本,或者使用Chrome、Firefox浏览器打开。)

写在前面:2019年10月26日,中国发布了密码法,这对于促进我国密码的发展,保障网络信息安全,维护国家安全和社会公共利益,保护公民、法人和其他组织的合法权益,将起到重要作用。西安电子科技大学的密码学学科一直位于全国第一,包括网络信息安全在内的相关技术氛围浓厚,2016年西电胡予濮教授攻破了GGH密码方案,获得了广泛的关注。AI柠檬曾于2017年在西电微软学生俱乐部的技术沙龙活动中,为学弟学妹们介绍密码学的基础知识,相关加密算法等。博主也希望能有更多的同学对密码学感兴趣,为我国的相关事业的发展做出自己的一份贡献。

(多图预警)

技术沙龙演讲全文

引言

各位小伙伴们晚上好,今天我给大家来讲一些关于密码学的基础知识。

这里我首先放了一张猫和老鼠的图片。密码学就是一场猫和老鼠的游戏,老鼠总是想偷偷摸摸做些事情而不让猫知道,猫总是竭尽全力阻止老鼠。加密者就像老鼠,破解者就像猫。

这张图是数据加密传送和破解的一种模型。

A和B是两个在互相通信的人,而C是第三者,是中间人。

密码学的起源

密码学起源于古代战争,最初仅仅是为了将信息保密,从而不让敌方或者第三方知道,许多密码都起源于军事上,所以战争常常推动着密码学的发展。

古典密码

早期的古典密码学的出现,可以追溯到古中国周朝兵书《六韬.龙韬》记载的密码学的运用,以及公元前5世纪,古希腊城邦由于经常发生战争而产生的一些关于密码学的应用。

替换式密码

代换密码是字母(或是字母群)作有系统的代换,直到讯息被替换成其它难以解读的字。凯撒密码是广为人知的代换密码。为了用凯撒密码法加密讯息,每个密码字母集中的字母将会被其位置的后3个字母替代。因此字母A将会被字母D替代、字母B将会被字母E替代、字母C将会被字母F替代等,最后,X、Y和Z将分别的被替代成A、B和C。

移位式密码,它们字母本身不变,但它们在讯息中顺序是依照一个定义明确的计划改变。许多移位式密码是基于几何而设计的。一个简单的加密(也易被破解),可以将字母向右移1位。

这是一种中国式的移位式密码:

经典密码通常很容易被破解。许多经典密码可单单经由密文而破解,所以它们容易受到唯密文攻击法攻击(英语:ciphertext-only attack),通常有暴力破解和频率分析两种。

有些经典密码(像是凯撒密码)的金钥个数有限,所以这类密码可以使用暴力破解尝试所有的金钥。

替代式密码有比较大的密钥数,但是容易被频率分析,因为每个密码字母各代表了一个明文字母。

这是基于频率统计的破解方法示例,通过相同频率的字母的比对,我们可以很快还原出真实的内容。这样的密码,优点是很简单,缺点是太简单。西电校内的某XX账号在软件内部的加密就是这种类型的密码,以至于被我们轻松破解。

现代密码学

现代密码学主要分为这两种:对称加密、非对称加密。

其中,对称加密算法,发送方与接收方同时知道一个密钥,可以用来同时用来加密和解密数据。

比如RC4,RC4是由RSA Security的罗纳德·李维斯特在1987年开发出来的,基本原理:伪随机数生成器 + 异或运算。由于异或运算的对称性,RC4加密解密使用同一套算法。

左:

初始化长度为256的数组S。第一个for循环将0到255的互不重复的元素装入数组S。第二个for循环根据密钥打乱数组S。

右:

下面i,j是两个指针。每收到一个字节,就进行while循环。通过一定的算法((a),(b))定位数组S中的一个元素,并与输入字节异或,得到k。循环中还改变了S盒((c))。如果输入的是明文,输出的就是密文;如果输入的是密文,输出的就是明文。

此算法保证每256次循环中S盒的每个元素至少被交换过一次。

不过,2015年,比利时鲁汶大学的研究人员Mathy Vanhoef及Frank Piessens,公布了针对RC4加密算法的新型攻击程式,可在75小时内取得cookie的内容。RC4算法呢,现在已经不算安全了。

不过这并不妨碍它大量的使用,让它如此广泛分布和使用的主要因素是它不可思议的简单和速度,不管是软件还是硬件,实现起来都十分容易。

数据加密标准(英语:Data Encryption Standard,缩写为 DES)是一种对称密钥加密块密码算法,1976年被美国联邦政府的国家标准局确定为联邦资料处理标准(FIPS),随后在国际上广泛流传开来。它基于使用56位密钥的对称算法。

DES现在已经不是一种安全的加密方法,主要因为它使用的56位密钥过短。在2001年,DES作为一个标准已经被高级加密标准(AES)所取代。目前已经有了至少这四种破解方式:暴力破解、微分密码分析、线性密码分析,和改进的戴维斯攻击等。

高级加密标准(英语:Advanced Encryption Standard,缩写:AES),在密码学中又称Rijndael加密法,是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES,已经被多方分析且广为全世界所使用。

根据已经掌握的资料,在2006年之前,针对AES唯一的成功攻击是旁道攻击。美国国家安全局审核了所有的参与竞选AES的最终入围者(包括Rijndael),认为他们均能够满足美国政府传递非机密文件的安全需要。2003年6月,美国政府宣布AES可以用于加密机密文件。

ChaCha20

是流加密算法Salsa20的一种,基于add-rotate-xor(ARX)操作的伪随机函数之上——32位模加、异或(XOR)和循环移位操作。Google选择了带有Bernstein的Poly1305消息认证码的ChaCha20作为一个OpenSSL中RC4的替代品,用以完成互联网的安全通信。Google最初实现了https (TLS/SSL)流量在Chrome浏览器(Android手机版)与Google网站之间的通信。这种加密方法目前暂时找不到破解方法的资料,安全性较高。

总结

以上是一些对称加密的常见几种加密算法,对称加密的优点:简单易用、计算速度快,缺点就是需事前商定密钥。

非对称加密

RSA

RSA加密算法是一种非对称加密算法,在公开密钥加密和电子商业中,RSA被广泛使用。

数学原理

对极大整数做因数分解的难度决定了RSA算法的可靠性。

换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被暴力方式解破。到目前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。

应用实例:PGP。左边是加密用的公钥,右边是加密后的文本。

非对称加密优点:无需事前商定密钥,适用于恶劣环境下;保密性高;可验证数据完整性;可鉴别发送者身份;具有不可否认性。该加密算法的缺点:计算开销大。

中间人攻击(欺骗)

虽然有很强的加密算法,但是只能保证数据加密后,除了私钥拥有者以外,数据不会被解密,不能保证不会受到中间人的欺骗。第三方在中间分别冒充B和A,用自己的Public Key与A和B进行加密通信,可以让A和B误以为直接向对方发送了信息却不知道信息已经泄露给第三者C。

有一种解决方案是使用第三方公钥托管服务,任何人都可以从这里获取联系人的公钥,公钥所有者也可以检查这里的密钥是否被人篡改。不过,仍然不能保证A和B再次在与第三方托管服务通信的过程中受到欺骗,但是可以降低整体的信息泄露的可能性。正如我一开始所说的,这是一场猫和老鼠的游戏,没有绝对的安全,只有相对的安全。

生活中的密码

这是位于密码字典前十名的常用密码,破解这类密码甚至丝毫不费吹灰之力,其安全性跟没加密几乎一样。

这是网站用户登录时服务器端的相关操作过程。对于网站来说,密码是不能明文存储的,否则是极度不安全的,国内某大型IT技术网站的密码由于明文存储,就曾发生多次的密码泄露和撞库的事件。

密码学可以看成是破解者和反破解者之间的一场无休无止的战争,就像猫和老鼠一样,会一直进行下去,道高一尺魔高一丈。没有最安全的密码,只有更安全的密码。如果大家对密码学感兴趣,可以上网搜寻更多的资料。我们今天就到这里,谢谢大家!

参考资料

新华网发布:中华人民共和国密码法

http://www.xinhuanet.com/2019-10/26/c_1125156896.htm

版权声明
本博客的文章除特别说明外均为原创,本人版权所有。欢迎转载,转载请注明作者及来源链接,谢谢。
本文地址: https://blog.ailemon.net/2019/11/18/xdmsc-techsalon-introduction-to-cryptography/
All articles are under Attribution-NonCommercial-ShareAlike 4.0

关注“AI柠檬博客”微信公众号,及时获取你最需要的干货。


发表回复

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

3 × 4 =

如果您是第一次在本站发布评论,内容将在博主审核后显示,请耐心等待