2密码学基础

密码学的数学基础及其应用

密码学是现代信息安全领域中的重要分支，它涵盖了加密、解密、数字签名、密钥管理等方面。其基本目的是确保信息的安全性、可靠性和隐私性。密钥是解密或解码所需的加密或编码过的文本，因此，密码学的基础是在数学和其他相关学科中找到可行的方法来创建和管理密钥。

一、密码学的数学基础

密码学的数学基础主要包括大量的数学理论、算法和问题，这些是建立密码体系必不可少的基础。其中，最基础也最重要的是数论、代数、离散数学和计算机科学。

1. 数论

数论是密码学的基础。在密码学中，一种常用的数论方法叫做模运算。模运算是在某一范围内进行的算术运算，例如将100除以7得到的余数是2，即100 mod 7 = 2。这个方法被用于创建密钥和密码。

2. 代数

代数在密码学中的作用与数论一样重要。这是因为密码的创建和破解过程中，有时需要用到代数方法。例如，当使用基于公钥的密码体系时，常常需要使用解方程式的方法来计算密钥。

3. 离散数学

离散数学是密码学的关键，特别是在数据结构、图论、组合数学等方面。在密码学中，离散数学的一种应用是用于构建Diffie-Hellman密钥交换协议和ElGamal加密算法等。

4. 计算机科学

计算机科学是密码学的另一个重要基础。密码学中使用的大多数算法都需要计算机的支持。因此，对于密码学的学习者，必须了解计算机科学的基础知识，例如数据结构、算法、计算机体系结构和操作系统等。

二、密码学的应用

密码学的应用涵盖了众多领域。在计算机网络安全领域，有四种常见的密码学应用。

1. 对称加密技术

对称加密技术是一种常见的密码技术，使用相同的密钥加密和解密数据。这种技术能够快速加密和解密数据，但有一个问题是，不安全地传输密钥会导致密钥泄漏的风险。

2. 公钥加密技术

公钥加密技术也被称为非对称加密技术。它使用两个密钥，一个用于加密数据，另一个用于解密数据，因此只有拥有私钥的人才能读取数据。这种技术缺点是速度慢，因为加密和解密都需要昂贵的数学计算。

密码学的数学基础

密码学是研究信息安全和通信保密的一门学科，它涉及到数据加密、解密、认证、签名以及密码系统的设计等领域。密码学作为信息安全的基石，具备坚实的数学基础。本文将探讨密码学中涉及的一些重要的数学原理和算法。

一、模运算

在密码学中，模运算是一种关键的数学运算，它对于生成密码算法和破解密码算法都有着重要作用。模运算是指对于给定的正整数n，将一个整数a除以n所得的余数。

模运算具有以下几个重要性质：

1. 加法的封闭性。对于任意的整数a和b，(a+b) mod n=(a mod n + b

mod n) mod n。

2. 乘法的封闭性。对于任意的整数a和b，(a×b) mod n=(a mod n × b

mod n) mod n。

3. 乘法的分配律。对于任意的整数a、b和c，(a+b) mod n=(a mod n

+ b mod n) mod n。

二、欧拉函数和费马小定理

在密码学中，欧拉函数和费马小定理是密码算法设计的重要数学基础。

1. 欧拉函数 欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数。对于任意正整数n，欧拉函数满足以下性质：

- 如果p是一个质数，那么φ(p)=p-1。

- 如果a和b互质，那么φ(a×b)=φ(a)×φ(b)。

2. 费马小定理

费马小定理是一个基本的数论定理，它指出如果p是一个质数，a是不可被p整除的整数，那么a^(p-1) mod p ≡ 1。

费马小定理在密码学中应用广泛，特别是在RSA算法中。RSA算法是一种非对称加密算法，基于大数因子分解的困难性。

三、素数和大数因子分解

密码学中的许多算法都依赖于素数和大数因子分解的困难性。

1. 素数

素数是只能被1和自身整除的正整数。在密码学中，素数的选取十分重要，因为对于一个大的合数，将其分解质因数是非常困难的。

2. 大数因子分解

大数因子分解是指将一个大的合数分解成质因数的过程。在密码学中，大数因子分解的困难性是许多加密算法的基础，如RSA算法。

1第5章密码学基础

梁彬中国人民大学信息学院计算机系V 1.0信息安全

2内容•什么是密码学•古典密码系统•公钥密码学•密码校验和

35.1 什么是密码学•密码学（Cryptography）这个词源自两个意为“秘密书写”的希腊词，是一门隐匿消息的艺术和科学•密码分析（Cryptanalysis）：研究破译密码•密码学的基础组件是密码系统（cryptosystem）

45.1 什么是密码学•定义5.1：密码系统是一个五元组（E, D, M, K, C）–M是明文集–K是密钥集–C是密文集–E：M ×K →C是加密函数集–D：C ×K →M是解密函数集

5实例•凯撒密码（Cæsarcipher）–M={字母序列}–K={i| i为整数，并且0 ≤i≤25 }–E={Ek| k∈K 且对所有的m∈M,Ek(m) = (m+ k) mod 26 }–D={Dk| k∈K且对所有的c ∈C,Dk(c) = (26 + c–k) mod 26 }–C=M•假若密钥为3，则“HELLO”Æ“KHOOR”65.1 什么是密码学•攻击：假设攻击者知道加密明文的算法，而不知道具体的密钥（即知道D和E），可使用以下3种攻击方法：–唯密文（ciphertextonly）攻击，攻击者只拥有消息的密文，目的是找出相应的明文，如果可能，也可能试图寻找密钥；–已知明文（known plaintext）攻击，攻击者拥有密文和这些密文对应的明文，目的是找到以上明密文所用的密钥；–选择明文（chosen plaintext）攻击，攻击者可以对一些特定的明文进行加密，可得到明文所对应的密文，目的是找到以上明密文所用的密钥。

275.1 什么是密码学攻击类型：•数学攻击–基于对密码系统的基本数学原理的分析•统计学攻击–假定明文的统计特征，并且检查密文的统计特征是否符合这些假定

8实例：英语中的字母频率表

0.002z0.015g0.020y0.060s0.030m0.020f0.005x0.065r0.035l0.130e0.015w0.002q0.005k0.040d0.010v0.020p0.005j0.030c0.030u0.080o0.065i0.015b0.090t0.070n0.060h0.080a

密码学基础

1. 密码学概述

（1）密码学的发展历程

密码学是一门古老而深奥的学科，是结合数学、计算机科学、电子与通信等诸多学科于一体的交叉学科，是研究信息系统安全保密的一门科学。密码学主要包括密码编码学和密码分析学两个分支，其中密码编码学的主要目的是寻求保证信息保密性或仁整形的方法，密码分析学的主要目的是研究加密消息的破译或消息的伪造。密码学经历了从古代密码学到现代密码学的演变。

最早将现代密码学概念运用于实际的是Caesar大帝，他是古罗马帝国末期著名的统帅和政治家。Caesar发明了一种简单的加密算法把他的信息加密用于军队传递，后来被称为Caesar密码。它是将字母按字母表的顺序排列，并且最后一个字母与第一个字母相连。加密方法是将明文中的每个字母用其后边的第三个字母代替，就变成了密文。

替代密码的基本思想，是将明文中的每个字母用此字符在字母表中后面第 k个字母替代，加密过程可以表示为函数E(m)=(m+k) mod

n。其中：m 为明文字母在字母表中的位置数，n 为字母表中的字母个数，k 为密钥，E(m)为密文字母在字母表中对应的位置数。其解密过程可以表示为函数E(m)=(m-k) mod n。

置换密码的基本思想，不改变明文字符，只是将字符在明文中的排列顺序改变，从而实现明文信息的加密，又称为换位密码。矩阵换位法是实现置换密码的一种常用方法，它将明文中的字母按照给的顺序安排在一个矩阵中，然后根据密钥提供的顺序重新组合矩阵中字母，从而形成密文。

第一阶段：古代―1949年

这阶段的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭知觉和信念来进行密码设计和分析，而不是推理和证明，没有形成密码学的系统理论。这一阶段设计的密码称为经典密码或古典密码，并且密码算法在现代计算机技术条件下都是不安全的。

第二阶段：1949―1975年

1949年C.E.Shannon（香农）发表在《贝尔实验室技术杂志》上的《保密系统的信息理论（Communication Theory of Secrecy