1.6.1 密码学导论

author:Odyssey@cyberpeace

知识点

  • 密码体制

  • 古典密码

  • 密码安全性

学习目标

  • 掌握密码技术的基本思想

  • 掌握密码体制的组成结构

  • 熟悉置换、代替和代数等古典密码的编码方法

  • 掌握密码体制的分类

  • 掌握密码安全性的概念

  • 了解密码在信息安全领域的实际应用

密码学基本思想

密码学的定义 密码学是构建和分析不同加密解密方法的科学，该科学实际上包含两个部分：

  • 密码使用学是构建功能更强大、更有效的新密码的加密解密方法的科学。

  • 密码分析学则是发现已有加密法的弱点，以便不用密钥就能还原成明文的科学。

密码分析是确保密码体制安全的唯一方法，是密码学不可缺少的部分。密码学与通信有着密不可分的关系，往往还能决定着战争的胜负。

密码与信息安全

  • 密码总会被破解

  • 密码的算法总会被公开

  • 弱密码比不加密更危险

  • 密码只是信息安全的一部分

安全性原则

  • 计算安全性

  • 可证明安全性

  • 无条件安全性

密码学分类

  • 密码使用学

  • 密码分析学

1.2.1 密码使用学分类

  • 无秘钥算法

  • 对称秘钥算法

  • 公开秘钥算法

对称密钥算法

对称密钥算法重要术语：

明文：被传递的消息。用M表示，它可能是位序列、文本文件、位图、数字化的语音序列或数字化的视频图像等。对于计算机，M指的是二进制数据。

密文：加密后的消息。用C表示，对于计算机，C指的是二进制数据。

加密函数：作用于明文M得到密文C，用E表示。

数学公式：𝐶=𝐸(𝑀)

解密函数：作用于密文C还原明文M，用D表示。

数学公式：𝑀=𝐷(𝐶)

先加密后解密，原始明文将恢复：𝐷(𝐸(𝑀))=𝑀

公开密钥算法

公钥密码体制使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。解密密钥是接收者专用的秘钥，对其他人都保密。

公开密钥算法重要术语：

发送者 A 用 B 的公钥 PKB 对明文 X 加密（E 运算）后，在接收者 B 用自己的私钥 SKB 解密（D 运算），即可恢复出明文： DSKB(Y)=DSKB(EPKB(X))=XD_{SK_{B}}(Y)=D_{SK_{B}}(E_{PK_B}(X))=X 加密密钥是公开的，但不能用它来解密，即： DPKB(EPKB(X))≠XD_{PK_B}(E_{PK_B}(X))\neq X

1.2.2 密码分析学分类

古典密码学

1.3.1 古今密码学

密码学已经存在了几千年，密码学一词源于希腊语kryptós“隐藏的”，和gráphein“书写”。古典密码学的编码和破译通常依赖于设计者和敌手的创造力与技巧，作为一种实用性艺术存在，并没有对于密码学原理的清晰定义。而现代密码学则起源于20世纪末出现的大量相关理论，这些理论使得现代密码学成为了一种可以系统而严格地学习的科学。

1.3.2 常见替换密码

单表替换加密法：明文中的同一字母在加密时被同一固定的字母代换。

  • 凯撒密码

  • 简单替换密码

  • 仿射密码

  • Polybius密码

多表替换加密法：明文中的同一字母在加密时不是完全被同一固定的字母代换，可能是多个。

  • 维吉尼亚密码

  • ADFGVX密码

  • Enigma密码机

单表置换密码

1.4.1 凯撒密码

恺撒密码（英语：Caesar cipher），或称恺撒加密、恺撒变换、变换加密，是一种最简单且最广为人知的加密技术。当年恺撒曾用此方法与其将军们进行联系。

现在已经无法弄清恺撒密码在当时有多大的效果，但是有理由相信它是安全的。因为恺撒大部分敌人都是目不识丁的，而其余的则可能将这些消息当作是某个未知的外语。即使有某个敌人获取了恺撒的加密信息，根据现有的记载，当时也没有任何技术能够解决这一最基本、最简单的替换密码。

算法：

明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。𝐶=(𝑀+𝑘)𝑚𝑜𝑑26 例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。

破解凯撒密码

由于使用恺撒密码进行加密的语言一般都是字母文字系统，因此密码中可使用的偏移量也是有限的，因此可以通过穷举法，很轻易地进行破解。

密文：Q TQSM BW LZQVS UQTS 明文：I LIKE TO DRINK MILK

小实验

破解一个凯撒密码 密文：GR BRXO LNHF UBSWRJUDSKB

凯撒秘密在线分析网站

https://planetcalc.com/1434/

1.4.2 简单替换密码

将明文中所使用的字母替换为另一套字母表，形成新的对应关系。这种替换可以是任意的一对一关系。

例如：现有一个简单替换密码表

明文： crypto
密文： hzkrqb

简单替换密码很难通过穷举法来破译。 密钥空间：26！=26×25×24×⋯×3×2×1

破译简单替换密码

已知一段密文：

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

有用信息： 明文使用标准英文书写 使用简单替换密码 每个明文字母被唯一的密文字母替代

  • 高频字母可以成为线索

  • 低频字母可以成为线索

  • 常见的字母组合可以成为线索（the , it , here , per 等）

  • 密文越长越容易被破解

  • 需要加入适当的猜测和推理

我们再次分析密文：

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

  1. 猜测P Z可能是e和t；

  2. 统计字母的相对频率-双字母

  3. 猜测ZW可能是th，因此ZWP可能是the

  4. 经过反复猜测、分析和处理，得到明文

it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

在线进行词频分析网站

https://quipqiup.com/

1.4.3 仿射密码

它的加密函数是$C=(aM+b) mod\space 26$，其中

  • 数字对（a，b）为密钥

  • a和26互素，既：$gcd⁡(a,26)=1$

  • b为小于26的正整数

  • 在英文中有26个字母，因此是 $mod\space 26$

它的解密函数是$M=a^{−1} (C−b)mod\space 26$

解密函数，推导过程如下：

Previous1.6 密码学基础Next1.6.2 流密码

Last updated