信息安全数学基础自学笔记1——群

系列文章目录

->第一章 群的基本概念

---

文章目录

• 系列文章目录
• 前言
• 一、概论——简单介绍三个基础的数学难题
• • 1.1 大整数因数分解问题
  • 1.2 离散对数问题
  • 1.3 椭圆曲线离散对数问题
  • 1.4 我们要学习的内容
• 二、群——近世代数部分的开始
• • 2.1 群的概念
  • 2.2 群的例子
  • • 2.2.1 整数上的加法运算
    • 2.2.2 实数域R上n阶一般线性群
    • 2.2.3 希尔密码的例子
  • 2.3 子群
  • 2.4 循环群
  • 2.5 对称群
  • • 2.5.1 置换的定义与对称群
    • 2.5.2 例子1——置换密码（位置映射，S是数字的集合，代表的位置）
    • • 2.5.2.1 置换密码的加密
      • 2.5.2.2 置换密码的解密
    • 2.5.3 例子2——代换密码（元素映射，S是字母符号的集合）
  • 2.6 群上的离散对数

---

前言

现在是八月五日，昨天是快乐的七夕，但是八月22日就要开学了。计算机组成已经预习了七章，为了更好地应对下学期的考试课，这里在快开学的十几天提前预习以下密码学的先修课。唉，上学期的信息安全基础学的不是很明白，也没有怎么讲数学，听学长说下学期的密码学课很硬，还是有必要预习一下的。
这里是听的哈工大的《信息安全数学基础》的网课，这里是这里是传送门。毕竟这是门数学课，要插入不少公式，这里的笔记就简单记录一下，并不详细。

---

一、概论——简单介绍三个基础的数学难题

刚开始的这三个问题也只是简单介绍，后面学完了应该就知道了

1.1 大整数因数分解问题

1.2 离散对数问题

1.3 椭圆曲线离散对数问题

1.4 我们要学习的内容

二、群——近世代数部分的开始

集合上的二元运算：两个运算数都是S上的数字，运算的结果仍然是S上的数字

2.1 群的概念

群是需要具有封闭性的，这里的概念中没有写，是因为我们在上面定义二元运算的时候定义了封闭性
下图的“1”就是单位元

2.2 群的例子 2.2.1 整数上的加法运算

2.2.2 实数域R上n阶一般线性群

满足G1、G2、G3，即结合律、单位元以及逆元，但是不满足交换律

2.2.3 希尔密码的例子

这里对密钥的要求就是，密钥应该是在0~25的集合上的m阶方阵，这个方阵应该是可逆的，所以需要它的行列式不为0
定义以及加密过程如下：

实际运算的例子:
这里我们可以自己算一下，答案应该是：(16，17，19)，（q,r,t）
如果想要解密，可以对（ y 1 y 2 ⋅ ⋅ ⋅ y m y_1 y_2···y_m y1​y2​⋅⋅⋅ym​）进行右乘一个逆矩阵

如何求逆？

2.3 子群

也是三个条件
第一，集合是子集合
第二，单位元在子集中
第三，子集合构成群

2.4 循环群

无限阶元素的概念：找不到一个整数n让a的n次幂等于单位元

2.5 对称群 2.5.1 置换的定义与对称群

这里的置换其实就是一个映射，这里我们定义，把所有置换的集合记作 S n S_n Sn​
定义这所谓的 S n S_n Sn​上的所有映射都可以进行乘积，乘积的形式如图所示
这个 S n S_n Sn​集合，映射的乘法与1构成了n次对称群

2.5.2 例子1——置换密码（位置映射，S是数字的集合，代表的位置）

σ sigma σ这里是 S m S_m Sm​上的一个元素，也就是一个置换
循环群的一个元素 σ sigma σ是置换密码的一个密钥
但是古典密码不怎么用置换密码，因为很容易可以用频率攻击进行破解

2.5.2.1 置换密码的加密

这里看到置换密码的原则应该是，把第四个放到第一个，第一个放到第二个，第二个放到第三个，第三个放到第四个，四个一组地进行置换

2.5.2.2 置换密码的解密

置换密码的解密就是对 σ sigma σ进行求逆，上下两行反转即可

2.5.3 例子2——代换密码（元素映射，S是字母符号的集合）

这里的置换是字母到字母的映射

2.6 群上的离散对数

这里要看明白PPT需要一些后面数论的知识，所有在这里只做简要介绍
下面是一个例子
模n乘的意思是先相乘后再模n
Z n Z_n Zn​是0~n-1的n个整数的集合
注意下面定义中的 Z n Z_n Zn​和 Z n ∗ Z_n^* Zn∗​两者的区别，这个和后面学环的时候是否包含0的区别不同，这个带星号是指素数个元素，这里与别的地方星号含义不同，需要注意


这里对于有不同运算符号的群来说，如果是加法，那么对应离散对数问题的x次运算最后就是乘法