日期: 2023-11-09 19:11 查看: 156 次编辑

数论在密码中的应用

数论在密码中的应用
在现实生活中, 人们常常需要从一方向另一方传送信息, 如照片、一首歌曲、一封信、资料等. 有时由于某种原因, 传送和接收双方都不希望传送的信息被第三方截取、篡改或伪造. 为保证信息安全, 传送方常采用某种算法对原始信息进行加密, 然后对加密后的信息进行传送, 接收方收到信息后, 再按照某种算法对信息进行去密, 从而获知原始信息. 用于信息加密的算法和用于信息去密的算法共同组成了密码算法, 也就是密码. 数论在密码中有重要应用.

原始信息可以有很多种具体形式 (如图像、声音和文字等). 在无线电通信时代, 原始信息在传送时通常都转换成数字信息 $x$ (如十进制数字或计算机通用的二进制数字)。信息传送的一个简单模型如图 1 所示:

![图片](/uploads/2023-11/image_20231109e852c21.png)

即将数字信息 $x$ 直接通过信道传送给接收方.
下面看一个利用上述模型传送英文文字信息的例子.
首先传送和接收双方约定编码规则: 将每个英文字母 $a, b, c, \cdots, z$ 分别用十进制数字 $01,02,03, \cdots, 26$ 代替, 而英文中的空格、逗号、句号、感叹号、问号分别用数字 2728293000 代替.

假定要传送信息 Good morning! 给接收方, 传送方可以将十进制数字信息 $x: 0715$ 1504271315181409140730 直接通过信道发给接收方, 接收方收到上面的数字信息 $x$后, 根据上面的编码规则就可以识别原始信息.

信息的这种传送方式极不安全, 在传送的过程中数字信息 $x$ 很容易被第三方截取、篡改或伪造.

现实生活中许多信息需要保密, 如军事和外交机密、商业秘密、个人隐私等. 为此,传送方在发送之前需要将数字信息 $x$ 按某种方式进行变换 (这个过程叫做加密), 将变换

后的数字信息 $y$ 传送出去, 然后合法的接收方收到数字信息 $y$ 后, 再进行相反的变换（这个过程叫做去密), 恢复成数字信息 $x$, 而识别出原始信息.

历史上通过这种方式传送信息的事例并不鲜见. 例如, 我国古代就不乏以藏头露尾诗的形式将信息隐藏在整个诗篇中, 从而只让某些掌握了规律的人知晓的例子.

如用数学语言表示信息加密传送的机制, 就是先对数字信息 $x$ 作一个变换 $E$, 将变换后的信息 $y=E(x)$ 发出, 接收方收到信息 $y$ 后, 进行一个相反的变换 $D$ (也就是 $E$ 的逆运算), 恢复成数字信息 $x=D(y)$, 从而识别原始信息.
信息加密传送的一个简单模型如图 2 所示:
![图片](/uploads/2023-11/image_202311094e2746e.png)
通常把数字信息 $x$ 叫做明文, 加密后得到的数字信息 $y$ 叫做密文, 变换 $E$ 和 $D$ 分别叫做加密与去密的密钥. 一般来说, 密钥对 $\{E, D\}$ 只能由传送方和接收方约定和保存,不被外人所知. 由于非法接收方不知道密钥, 即使截取了密文 $y$, 也无法恢复成明文 $x$.

要使外人很难从密文破译出明文, 密钥的设计是关键. 密钥的设计方法多种多样, 数论在这方面起着重要的作用.
我们简要介绍一下恺撒大帝的加密方法.
假定要把信息 Good morning! 加密传送给接收方, 将每个英文字母或符号代表的十进制数作如下变换:

$$
E: k \rightarrow \begin{cases}k+19, & \text { 当 } k<12 \text { 时; } \\ k-12, & \text { 当 } k \geqslant 12 \text { 时. }\end{cases}
$$

若采用高斯的同余符号, 则加密运算 $E$ 可表示为

$$
E(k)=k+19(\bmod 31) \mathbf{0}, k=0,1,2, \cdots, 30 .
$$

这样一来, 原始信息由明文: 07151504271315181409140730 变成密文: 2603 0323150103060228022618 , 其加密过程如表 1 所示:

![图片](/uploads/2023-11/image_20231109ab4be8f.png)

传送方将密文 $y$ 通过信道发给接收方. 接收方收到密文 $y$ 之后, 对 $y$ 中的每个十进制数 (对应着伪装信息的字母或符号) 进行相反的变换:
$D: k \rightarrow \begin{cases}k-19, & \text { 当 } k \geqslant 19 \text { 时; } \\ k+12, & \text { 当 } k<19 \text { 时 }\end{cases}$
![图片](/uploads/2023-11/image_2023110967717ed.png)
同样地, 如用高斯的同余符号, 则去密运算 $D$ 可表示为

$$
D(k)=k+12(\bmod 31), k=0,1,2, \cdots, 30 .
$$

凯撒的加密方法的优点是加密和去密都是模 31 的加法或减法运算, 很容易进行. 但缺点是密钥个数太少, 只有 30 个. 第三方一旦知道了加密方法, 就可以逐个试验这 30 个密钥, 从而将 $y$ 恢复成明文.

另一方面, 原始信息中某个字母或符号重复出现时, 其对应的数字也重复出现, 经加密后都变成同一个数字. 那么, 第三方在截取足够长的一段密文后, 根据英文语言中某些字母出现的频率, 用统计学的方法也可以发现加密密钥, 进而得到去密密钥.

后来, 人们对这种加密方法加以改进. 例如, 将加密密钥改为 $E(k)=k+i(\bmod 31)$,其中 $i$ 是周期变化的. 这样一来, 密钥的个数大大增加了, 并且原始信息中同一字母或符号, 经加密后对应于不同的数字, 从而增加了密钥破译的难度.

上一篇：多元一次不定方程

下一篇：大数分解和公开密钥

本文对您是否有用？有用 (0) 无用 (0) 赞助我们

0 篇笔记写笔记

更多笔记