查看原文
其他

密码学的100个基本概念(上)

无忧 隐私计算研习社 2024-01-09

密码学作为信息安全的基础,极为重要,本文分为上下两部分,总计10个章节,回顾了密码学的100个基本概念,供小伙伴们学习参考。本文将先介绍前五个章节的内容。
0



目录


一、密码学历史

二、密码学基础

三、分组密码

四、序列密码

五、哈希函数

六、公钥密码

七、数字签名

八、密码协议

九、密钥管理

十、量子密码


1



密码学历史

1.密码学

密码学(cryptography)源于希腊语kryptós“隐藏的”和gráphein“书写”,是研究信息安全保密的学科,涉及密码编码与密码分析。

2.古典密码

古典密码主要采用代换(Substitution)和置换(Permutation)的方式,并通过手工或简单器械实现,其使用阶段从古代到19世纪末,长达上千年,包括棋盘密码、凯撒密码等。

3.凯撒密码

凯撒密码是罗马皇帝朱利尤斯·凯撒(Julius Caesar)在公元前约50年发明的一种用于战时秘密通信的方法。凯撒密码将字母按字母表的顺序构成一个字母序列链,然后将最后一个字母与第一个字母相连成环,加密方法是将明文中的每个字母用其后的第个字母代替。

4.近代密码

近代密码一般指20世纪初到20世纪50年代,通过机械或电动设备实现的加密方式,虽然技术上有了很大进步,但加密仍然依靠替代及置换的方式,包括单表代换密码(如仿射密码)、多表代换密码(如Vigenère密码和Hill密码等)。

5.现代密码

1949年香农发表《保密系统的通信理论》(Communication Theory of Secrecy System),标志着现代密码学的开端。香农将信息论引入到密码学研究中,利用概率统计的观点和熵的概念对信息源、密钥源、传输的密文和密码系统的安全性进行了数学描述和定量分析,并提出了对称码体制的模型,为现代密码学奠定了数学基础,这是密码学的第一次飞跃。

1976年,Diffie和Hellman发表的经典论文《密码学的新方向》(New Directions in Cryptography)提出了公钥密码体制思想,为现代密码学的发展开辟了崭新的方向,带来了密码学的第二次飞跃。


2



密码学基础

6.中断

中断(Interruption)也称拒绝服务,是指阻止或禁止通信设施的正常使用或管理,这是对可用性攻击。这种攻击一般有两种形式:一是攻击者删除通过某一连接的所有协议数据单元,从而抑制所有的消息指向某个特殊的目的地;二是使整个网络瘫痪或崩溃,可能采取的手段是滥发消息使之过载,使网络不能正常工作。

7.截取

截取(Interception)是未授权地窃听或监测传输的消息,从而获得对某个资源的访问,这是对机密性的攻击。攻击者一般通过在网络中“搭线”窃听,以获取他们通信的内容。

8.篡改

篡改(Modification)也就是修改数据流,对一个合法消息的某些部分被改变、消息被延迟或改变顺序,以产生一个未授权、有特殊目的的消息,是针对连接的协议数据单元的真实性、完整性和有序性的攻击。

9.伪造

伪造(Fabrication)是指将一个非法实体假装成一个合法的实体,是对身份真实性的攻击,通常与其他主动攻击形式结合在一起才具有攻击效果,如攻击者重放以前合法连接初始化序列的记录,从而获得自己本身没有的某些特权。

10.重放

重放(Replay)将一个数据单元截获后进行重传,产生一个未授权的消息。在这种攻击中,攻击者记录下某次通信会话,然后在以后某个时刻重放整个会话或其中的一部分。

11.机密性

机密性(Confidentiality)是指保证信息不泄露给非授权的用户或实体,确保存储的信息和被传输的信息仅能被授权的各方得到,而非授权用户即使得到信息也无法知晓信息内容。通常通过访问控制阻止非授权用户获得机密信息,通过加密阻止非授权用户获知信息内容。

12.完整性

完整性(Integrity)是指信息未经授权不能进行篡改的特征,确保信息的一致性,即信息在生成、传输、存储和使用过程中不应发生人为或非人为的非授权篡改(插人、修改、删除、重排序等)。一般通过访问控制阻止篡改行为,同时通过消息摘要算法来检验。

13.认证性

认证性(Authentication),或称真实性,指确保一个消息的来源或消息本身被正确地标识,同时确保该标识没有被伪造,通过数字签名、消息认证码(MAC)等方式实现。认证分为消息认证和实体认证。

  • 消息认证是指能向接收方保证该消息确实来自于它所宣称的源,

  • 实体认证是指在连接发起时能确保这两个实体是可信的,即每个实体确实是它们宣称的那个实体,第三方也不能假冒这两个合法方中的任何一方。

14.不可否认性

不可否认性(Non-Repudiation)是指能保障用户无法在事后否认曾经对信息进行的生成、签发、接收等行为,是针对通信各方信息真实性、一致性的安全要求。为了防止发送方或接收方抵赖所传输的消息,要求发送方和接收方都不能抵赖所进行的行为。通过数字签名来提供抗否认服务。

  • 当发送一个消息时,接收方能证实该消息确实是由既定的发送方发来的,称为源不可否认性

  • 当接收方收到一个消息时,发送方能够证实该消息确实已经送到了指定的接收方,称为宿不可否认性。

15.可用性

可用性(Availability)是指保障信息资源随时可提供服务的能力特性,即授权用户根据需要可以防时访问所需信息,保证合法用户对信息资源的使用不被非法拒绝。

16.密码系统

一个密码系统(体制)至少由明文、密文、加密算法和解密算法、密钥五部分组成。

17.明文

信息的原始形式成为明文(Plaintext)。

18.密文

经过变换加密的明文称为密文(Ciphertext)。

19.加密

对明文进行编码生成密文的过程称为加密(Encryption), 编码的规则称为加密算法。

20.解密

将密文恢复出明文的过程称为解密(Decryption),解密的规则称为解密算法。

21.密钥

密钥(Key)是唯一能控制明文与密文之间变换的关键,分为加密密钥和解密密钥。

22.柯克霍夫假设

柯克霍夫假设(Kerckhoffs Assumption),又称柯克霍夫原则(KerckhoffsPrinciple)或柯克霍夫公理(Kerckhoffs Axiom)是荷兰密码学家奥古斯特·柯克霍夫(Auguste Kerckhoffs)于1883年在其名著《军事密码学》中阐明的关于密码分析的一个基本假设:密码系统的安全性不应取决于不易改变的算法,而应取决于可随时改变的密钥,这就是设计和使用密码系统时必须遵守的。即加密和解密算法的安全性取决于密钥的安全性,而加密/解密的算法是公开的,只要密钥是安全的,则攻击者就无法推导出明文。

23.唯密文攻击

唯密文攻击(Ciphertext Only Attack)指密码分析者除了拥有截获的密文外(密码算法公开),无其他可以利用的信息。密码分析者的任务是恢复尽可能多的明文,或者最好是能推算出加密消息的密钥的信息。一般采用穷举搜索法文的尝试,直到得到有意义的明文。理论上穷举搜索是可以成功的,但实际上任何一种能保障安全要求的复杂度都是实际攻击者无法承受的。在这种情况下进行密码破译是最困难的,经不起这种攻击的密码体制被认为是完全不安全的。

24.已知明文攻击

已知明文攻击(Known Plaintext Attack)指密码分析者不仅掌握了相当数量的密文,还有一些已知的明-密文对可供利用。密码分析者的任务是用加密信息推出密钥或导出一个算法,该算法可对用同一密钥加密的任何新的信息进行解密。现代密码体制要求不仅要经受得住唯密文攻击而且要经受得住已知明文攻击。

25.选择明文攻击

选择明文攻击(Chosen Plaintext Attack)指密码分析者不仅能够获得一定数量的明密文对,还可选择任何明文并在使用同一未知密钥的情况下能得到相应的密文。如果攻击者在加密系统中能选择特定的明文消息,则通过该明文消息对应的密文有可能确定密钥的结构或获取更多关于密钥的信息选择明文攻击比已知明文攻击更有效,这种情况往往是密码分析者通过某种手段暂时控制加密机。此类攻击主要用于公开密钥算法,也就是说公开密钥算法必须经受住这攻击。

26.选择密文攻击

选择密文攻击(Chosen Ciphertext Attack)指密码分析者能选择不同的被加密的密文,并还可得到对应的明文密码分析者的售为是推出密钥及其他密文对应的明文。如果攻击者能从密文中选择特定的密文消息,则通过该密文消息对应的明文有可能推导出密钥的结构或产生更多关于密钥的信息。这种情况往往是密码分析者通过某种手段暂时控制解密机。

27.选择文本攻击

选择文本攻击(Chosen Text Attack)是选择明文攻击和选择密文攻击的组合,即密码分析者在掌握密码算法的前提下不仅能够选择明文并得到对应的密文,而且还能选择密文得到对应的明文。这种情况往往是密码分析者通过某种手段暂时控制加密机和解密机。

28.无条件安全

若在一种密码体制中,密码破译者无论知道多少密文以及采用何种方法都得不到明文或是密钥的信息,称其为无条件安全。无条件安全与攻击者的计算能力及时间无关。

29.有条件安全

有条件安全性是根据破解密码系统所需的计算量来评价其安全性,分为计算安全性、实际安全性和可证明安全性。

30.计算安全性

若破解一个密码系统是可行的,但使用已知的算法和现有计算工具不可能完成所要求的计算量,即已有最好的方法破解该密码系统所需要的努力超出了破解者的时间空间和资金等的破解能力,称该密码体制在计算上安全。

31.实际安全性

实际安全是指密码系统满足以下两个准则之一:破解该密码系统的成本超过被加密信息本身的价值;破译该密码系统的时间超过被加密信息的有效生命周期。

32.可证明安全性

可证明安全性是将密码体制的安全性归结为求解某个经过深入研究但尚未解决的数学难题,即将某种密码体制的安全性问题等价为一个数学难题的求解问题。这种判断方法存在的问题是:它只说明了该密码体制的安全和某个数学问题相关,但没有完全证明间题本身的安全性。

33.对称密码体制

对称密码体制(Symmetric Key Cryptosystem)又称单钥密码体制(One Key Cryptosystem)或秘密密钥密码体制(Secret Key Cryptosystem)。对称密码体制中,密钥必须完全保密,且加密密钥和解密密钥相同,或其中的一个可以很容易地推出另一个。典型算法有DES、3DES、AES、IDEA、RC4、A5、SEAL等。

对称密码体制的密钥相对较短,密文的长度往往与明文长度相同,具有较快的加解密速度,易于硬件实现。但发送方如何安全、高效地把密钥送到接收方是对称密码体制的软肋,往往需要“安全通道”;此外称密码体制密钥量大,难于管理。

34.非对称密码体制

1976年,Whitefield Diffie和MartinHellman《密码学的新方向》(New Directions in Cryptography)中开创性的提出了公钥密码体制,又称非对称密码体制(Asymmetric Key Cryptosystem)又称为双钥密码体制(Double Key Cryptosystem)、公开密钥密码体制(Public Key Cryptosystem)。

该体制中,用户A有一对密钥:加密密钥(公钥)和解密密钥(私钥),两者是不同的,且从加密密钥(公钥)无法推出解密密钥(私钥)。若B要给A发送加密信息,需要用A的加密密钥(公钥)(可在公开目录中查找)加密消息;A收到密文后,用自己的解密密钥(私钥)解密密文。

非对称密码体制主要是为了解决对称密码体制中的密钥分发和管理问题,与对称密码体制相比,非对称密码体制加解密速度较慢,密钥较长,密文长度往往大于明文长度。常见公钥密码体制包括基于大整数因子分解问题的RSA公钥密码体制,基于有限域乘法群上的离散对数问题的ElGamal公钥密码体制,基于椭圆曲线上离散对数问题的椭圆曲线公钥密码体制等。


3



分组密码

35.分组密码

分组密码(block cipher)本质是一个从明文空间长的比特串集合)到密文空间长的比特串集合)的一一映射(一般)。明文消息经编码表示后的二进制序列划分成若干固定长度的组(或块),各组分别在密钥的控制下转换成长度为的密文分组

分组密码主要提供数据保密性,也可用于构造伪随机数生成器、流密码、认证码和哈希函数。分组密码分为对称分组密码和非对称分组密码(公钥密码),在很多场合一般指是对称分组密码。

36.扩散

扩散(diffusion)指算法使每一比特明文的变化尽可能多地影响到输出密文序列的变化,以便隐蔽明文的统计特性;并且每一位密钥的影响也尽可能迅速地扩展到较多的输出密文比特中去。即扩散的目的是希望密文中的任一比特都要尽可能与明文、密钥相关联,或者说,明文和密钥中任何一比特值得改变,都会在某种程度上影响到密文值的变化(又称雪崩效应),以防止将密钥分解成若干个孤立的小部分,然后各个击破。

37.混乱

混乱(confusion)指在加密变换过程中是明文、密钥以及密文之间的关系尽可能地复杂化,以防密码破译者采用统计分析法进行破译攻击。混乱可以用“搅拌”来形象地解释,将一组明文和一组密文输入到算法中,经过充分混合,最后变成密文。同时要求,执行这种“混乱”作业的每一步都必须是可逆的,即明文混乱以后能得到密文,反之,密文经过逆向混乱操作后能恢复出明文。

38.白化

白化(whitening)是将分组密码算法的输入与一部分密钥异或,并将其输出与另一部分密钥异或的技术,用于阻止密码分析者在已知基本密码算法的前提下获得一组明文/秘文对。

39.雪崩效应

雪崩效应(Avalance Criteria)指输入(明文或密钥)即使只有很小的变化,也会导致输出(密文)产生巨大变化。严格雪崩效应(Strict Avalance Criteria)指当一个输入位发生改变时,输出位将有一半发生改变。

40.代换-置换网络

代换-置换网络(Subsituation Permutation Network)简称SP网络,是由多重S变换(S盒,混乱)和P变换(P盒,扩散)组合成的变换网络,是乘积密码的一种常见表现形式。SP网络中的S盒是许多密码算法唯一的非线性部件,其密码强度决定了整个密码算法的强度。

41.Feistel网络

Feistel网络由Feistel提出,将长度为bit(为偶数)的明文分组分为左右各半长为的两部分:。定义迭代算法如下:

其中,是第轮使用的子密钥,是任意轮函数。

Feistel网络保证了算法可逆性,即加密和解密可以采用同一算法实施。

42.DES

DES(Data Encryption Standards)是第一个广泛应用于商用数据保密的密码算法,为对称加密算法。美国国家标准局(NBS,National Bureau of Standards)于1973年开始征集联邦数据加密标准,许多公司提交了算法,IBM公司的Lucifer加密系统最终胜出。经过两年多的公开讨论,1977年1月15日NBS决定利用这个算法,并将其更名为数据加密标准(DES)。

43.AES

1997年美国国家标准与技术研究院(NIST,National Institute of Standards and Technology)公开征集高级加密标准(AES,Advanced Encryption Standard),基本要求是安全性能不低于三重DES,性能比三重DES快,并特别提出高级加密标准必须是分组长度为128位的对称分组密码,且支持长度为128位、192位、256位的密钥。此外,如果算法被选中,在世界范围内须是可免费获得的。

2000年10月2日,NIST宣布最终评选结果,根据安全性(稳定的数学基础、无算法弱点、可抗密码分析)、性能(速度快)、大小(内存与存储空间占用小)、易实现(良好的软硬件适应性)等标准,比利时密码学家Joan Daemen和Vincent Rijmen提出的“Rijndael数据加密算法”最终获胜。修改的Rijndael算法成为高级加密标准AES,2001年11月26日,NIST正式公布高级加密标准AES,并于2002年5月26日正式生效。

44.IDEA

国际数据加密算法(IDEA, International Data Encryption Algorithm)由瑞士的来学嘉(Xuejia Lai)和 James Massey于1990年公布,当时称为推荐加密标准(PES, Proposed Encryption Standard)。1991年,为抗击差分密攻击,他们对算法进行了改进,称为改进推荐加密标准(IPES,Im proved PES),并于1992年改名为国际数据加密算法IDEA。

IDEA受专利保护,要先获得许可证之后才能在商业应用程序中使用,著名的电子邮件隐私技术PGP就是基于IDEA的。

45.分组密码的工作模式

实际消息长度一般大于分组密码的分组长度,分组密码将消息分为固定长度的数据块来逐块处理。人们设计了许多不同的块处理方式,称为分组密码的工作模式,通常是基本密码模块、反馈和一些简单运算的组合。这些工作模式同时为密文分组提供了一些其他性质,如隐藏明文的统计特性、错误传播控制、流密码的密钥流生成等。

46.电子密码本

电子密码本(ECB, Electronic Code Book)模式一次处理一个明文分组,各个明文分组被独立加密成相应的密文分组,主要用于内容较短且随机的报文(如密钥)的加密传递。

  • 相同明文(在相同密钥下)得出相同的密文,易受实现统计分析攻击、分组重放攻击和代换攻击 

  • 链接依赖性:各组的加密都独立于其它分组,可实现并行处理 

  • 错误传播:单个密文分组中有一个或多个比特错误只会影响该分组的解密结果

47.密码分组链接

密码分组链接(CBC, Cipher Block Chaining)模式应用了反馈机制,明文在加密之前需要与前面的密文进行异或,即每个密文分组不仅依赖于产生它的明文分组,还依赖于它前面的所有分组。CBC适合文件加密,是软件加密的最佳选择。

  • 相同的明文,即使相同的密钥下也会得到不同的密文分组,隐藏了明文的统计特性 

  • 链接依赖性:对于一个正确密文分组的正确解密要求它之前的那个密文分组也正确,不能实现并行处理 

  • 错误传播:密文分组中的一个单比特错误会影响到本组和其后分组的解密,错误传播为两组

48.密码反馈

密码反馈(CFB, Cipher Feedback Block)将消息看作比特流,无需接受完整个数据分组后才能进行加解密,是自同步序列密码算法的典型例子,通常用于加密字符序列。

  • 可用于同步序列密码,具有CBC模式的优点 

  • 对信道错误较敏感且会造成错误传播 

  • 数据加解密的速率降低,其数据率不会太高

49.输出反馈

输出反馈(OFB, Output Feedback Block)是基于分组密码的同步序列密码算法的一种例子。

  • CFB模式的一种改进,克服由错误传播带来的问题,但对密文被篡改难于进行检测 

  • OFB模式不具有自同步能力,要求系统保持严格的同步,否则难于解密

4



序列密码

50.序列密码

序列密码,又称流密码,属于对称密码体制,它一次只对明文消息的单个字符(通常是二进制位)进行加解密变换,具有实现简单、速度快、错误传播少等特点.

在序列密码中,将明文消息按一定长度分组,对各组用相关但不同的密钥逐位加密产生相应密文,相同的明文分组会因在明文序列中的位置不同而对应不同的密文分组,接收者用相同的密钥序列对密文序列逐位解密恢复出明文。

令明文序列

密钥序列

密文序列


则称此类为加法序列密码

51.反馈移位寄存器

反馈移位寄存器(FSR,Feedback Shift Register)一般由移位寄存器和反馈函数(Feedback Function)组成。移位寄存器是由位组成的序列,其长度用位表示,每次移位寄存器中所有位右移一位,最左端的位根据寄存器中某些位计算得到,由寄存器某些位计算最左端位的部分被称为反馈函数,最右端一个寄存器移出的值是输出位。移位寄存器的周期是指输出序列从开始到重复时的长度。

52.线性反馈移位寄存器

线性反馈移位寄存器(LFSR,Linear Feedback Shift Register)的反馈函数是寄存器中某些位简单异或,这些位叫做抽头序列(Tap Sequence),有时也叫 Fibonacci 配置(Fibonacci Configuration)。

53.序列

线性反馈移位寄存器输出序列的性质完全由其反馈函数决定,一个位LSFR能够处于个内部状态中的一个,即理论上,位LFSR在重复之前能够产生位长的伪随机序列(由于全0的状态将使LFSR无止尽地输出0序列,因此是而不是)。

只要选择合适的反馈函数便可使序列的周期达到最大值,即只有具有一定抽头序列的LFSR才能循环地遍历所有个内部状态,这个输出序列被称为序列。为了使LFSR成为最大周期LFSR,由抽头序列加上常数1形成的多项式必须是本原多项式,多项式的阶即移位寄存器的长度。

54.RC4

RC4(Ron RivestCipher)以随机置换为基础,是一个可变密钥长度、面向字节操作的序列密码,该算法由于加解密速度快(比DES快约10倍)、易于软件实现,广泛应用于Microsoft Windows、Lotus Notes等软件中,以及安全套接字层(SSL,Secure Sockets Layer)传输信息。

与基于移位寄存器的序列密码不同,RC4是典型的基于非线性数组变换的序列密码。它以一个足够大的数组为基础,对其进行非线性变换,产生非线性的密钥序列,一般把这个大数组称为S盒。RC4的S盒的大小根据参数(通常)的值变化,RC4算法理论上可生成总数个的S盒。

55.A5

A5算法是GSM 系统中要使用的序列密码加密算法之一,用于加密手机终端基站之间的传输的语音和数据,目前已被攻破。

A5算法是一种典型的基于线性反馈移位寄存器的序列密码算法,由一个22bit长的参数(帧号码, Fn)和64 bit长的参数(会话密钥,Kc)生成两个114 bit长的序列(密钥流),然后与GSM会话每帧(228 bit/帧)异或。


5



哈希函数


56.Hash函数

Hash函数也称哈希函数/散列函数、杂凑函数,是一个从消息空间到像空间的不可逆映射,可将“任意”长度的输入经过变换以后得到固定长度的输出。它是一种单向密码体制,即只有加密过程,不存在解密过程。

57.消息摘要

Hash函数的单向性和输出长度固定的特征使其可生成消息的“数字指纹”(Digital Fingerprint),也称消息摘要(MD,Message Digest)或哈希值/散列值(Hash Value),主要应用于消息认证、数字签名、口令的安全传输与存储、文件完整性校验等方面。

58.MD5

MD5算法由美国麻省理工学院著名密码学家Rivest设计,他于1992年向IETF提交的RFC1321中对MD5作了详尽的阐述。MD5是在MD2、MD3、MD4的基础上发展而来,由于在MD4上增加了Safety-Belts,MD5又被称为是“系有安全带的MD4”。

算法的输入是最大长度小于bit的消息,输入消息以+bit的分组为单位处理,输出为bit的消息摘要。

59.SHA1

1993年,美国国家标准技术研究所NIST公布了安全散列算法SHA0(Secure Hash Algorithm)标准,1995年4月17日,公布的修改版本称为SHA-1,是数字签名标准中要求使用的算法。

SHA1算法的输入是最大长度小于bit的消息,输入消息以 bit的分组为单位处理,输出为bit的消息摘要,因此抗穷举性更好。

60.消息认证

消息认证指验证消息的真实性,包括验证消息来源的真实性,一般称之为信息源认证;验证消息的完整性,即验证消息在传输和存储过程中没有被篡改、伪造等

61.消息认证码

消息认证码(MAC,Message Authentication Code)用来检查消息是否被恶意修改,利用消息和双方共享的密钥通过认证函数来生成一个固定长度的短数据块,并将该数据块附加在消息后。

利用DES、AES等对称分组密码体制的密码分组链接模式(CBC)一直是构造MAC的最常见的方法,如FIPS PUB 113中定义的CBC-MAC。由于MD5、SHA-1等Hash函数软件执行速度比DES等对称分组密码算法要快,目前提出了许多基于Hash函数的消息认证算法,其中HMAC(RFC 2014)已作为FIPS 198标准发布,并且在SSL中用于消息认证。


本文作者:无忧

CSDN链接:

https://blog.csdn.net/apr15/article/details/128770449

作者简介:无忧,毕业于北京邮电大学,目前就职于华为技术有限公司, 长期从事信息安全、密码学领域研究。
END

往期推荐


1.CCVR:一种生成虚拟数据的联邦学习算法
2.PSI系列(2)组件 | OT Extension (IKNP)3.笔记分享 | 组队学习密码学(1)——密码学与MPC基础4.笔记分享 | 冯登国院士MPC讲座(1)——MPC基本概念和基础组件


继续滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存