第2章 密码学基础
密码学基础知识
❖ 密码技术在信息安全中的作用
信息安全的重要和核心部分之一是数据安全 数据安全的目标包括机密性、真实性、完整性、
不可否认性、可用性、可控性 实现数据安全目标的重要手段是密码技术 密码技术具有几千年的历史
❖ 密码学（Cryptology）是密码技术的基础， 包括：
密码编码学（Cryptography） 密码分析学（Cryptanalysis）
破解 密文
密钥kd 解密
明文
密码算法的基本定义
设：M是可能明文的集合，称为明文空间
C是可能密文的集合，称为密文空间
K是一切可能密钥构成的集合，称为密钥空间
E为加密算法，对密钥空间的任一密钥k都能进行加 密运算，即Ek: MC D为解密算法，对密钥空间的任一密钥都能进行解 密运算，即Dk: CM 则密码算法具有如下性质：
模余数举例
例1. 求9 mod 6 9 = 6+3，故 9 mod 6 =3
例2. 求–7 mod 6 –7 = -12+5，故 –7 mod 6=5
而 2X6 + (–7) mod 6 = 5 故， –7 mod 6 = 2X6 + (–7) mod 6 = 5 (即 a mod n = a + kn mod n)
一些关于模余数的基本知识
设n为大于1的正整数，a、b为任意整数，则 1) a + b mod n = (a mod n) + (b mod n) mod n 2) a – b mod n = (a mod n) + (–b mod n) mod n
= (a mod n) – (b mod n) mod n 3) ab mod n = (a mod n)*(b mod n) mod n 4) a mod n = a + kn mod n = a – kn mod n 5) a + (b mod n) mod n = a+b mod n
注意以下差别： a = b mod n a ≡ b (mod n) 前者表示：b的模n余数是a；后者表示： a和 b模n同余，即有相同的模n余数
在本课中用前一种表示，即mod作为一种算子
一些关于模余数的基本知识
❖ 定义 3. n为大于1的正整数，a、b为整数，则 a+b mod n，a*b mod n，ab mod n分别称 为整数的模n加法、乘法和乘方(幂)
= (9 mod 6) – (7 mod 6) mod 6 (即a – b mod n = (a mod n) + (–b mod n) mod n
= (a mod n) – (b mod n) mod n )
模余数举例(续)
例4. 求 2+(9 mod 6) mod 6 = 2+3 mod 6 =5 而 2+9 mod 6 = 11 mod 6 =5 故 2+(9 mod 6) mod 6 = 2+9 mod 6 (即a + (b mod n) mod n = a+b mod n)
Z XT X MHXYGHC 解密代替表
ABCDE FGH I J KLM
d
l
r
y vohEz
xwp
t
NOPQR S T U VWX Y Z
bg
f
j
q nmu s k a c
i
一些关于模余数的基本知识
定义1. 设n为大于1的正整数，a为任一整数，a可表示 为a=kn +r，r ≥0，则记为： a mod n = r，称r为a的模n余数
Cryptography)
古典密码
❖ 代替表代换密码 ❖ 移位密码 ❖ 乘数密码 ❖ 仿射密码
对照表代替密码
i am a teacher
加密代替表
abcde f gh i j k lm X N Y A H P OG Z QWB T
nopq r s t u vwx y z S F L RCVMUE K J D I
密码学基础知识
❖ 密码编码学：研究如何进行数据加密和解密 （机密性），以及防止和发现数据的伪造、 篡改（真实性、完整性、不可否认性）
❖ 密码分析学：分析发现密码算法的弱点、缺 陷，破解密码算法或者破译密码数据
数据加密、解密的基本过程
密钥kc
明文
加密 密文
密钥: key 明文: plaintext 密文: ciphertext 加密: encrypt 解密: decrypt
注意：负数的模n余数是正整数！ 例，若 –n<a<0，则a mod n = n+a
定义2.设n为大于1的正整数，a、b为任意整数，如果 a mod n = b mod n，即a、b有相同模n余数，则 称a、b模n同余
表示为 a ≡ b (mod n) a、b模n同余当且仅当n整除Leabharlann -b一些关于模余数的基本知识
一些关于模余数的基本知识
6) a*(b mod n) mod n = a*b mod n
7) (a mod n)p mod n = ap mod n 注意： mod的运算优先级最低 结论：
对于同一个模n，只要保存最外层的mod算子 ，给加、减、乘、乘方运算中的数据加上或去 掉mod 算子，不影响结果 请尝试证明一下！
例5. 求 2*(9 mod 6) mod 6 = 2*3 mod 6 =0 而 2*9 mod 6 = 18 mod 6 = 0 故，2*(9 mod 6) mod 6 = 2*9 mod 6 (即a*(b mod n) mod n = a*b mod n)
（1）Dk(Ek(x))=x，x属于M，k属于K （2）密码破译者获得密文c=Ek(x)后无法在有效的时
间内破解出密钥k和/或明文x
密码体制分类
❖ 古典密码(Classic Cryptography) ❖ 对称密钥密码(Symmetric Key
Cryptography) ❖ 公开密钥密码体系(Public Key
模余数举例(续)
例3. 求9 – 7 mod 6 9 – 7=2，故 9 – 7 mod 6 =2
而 (9 mod 6) + (–7 mod 6) mod 6 = 3+5 mod 6 = 8 mod 6 = 2
(9 mod 6) – (7 mod 6) mod 6 = 3 – 1 mod 6 =2 故 9-7 mod 6 = (9 mod 6) + (–7 mod 6) mod 6
