一、群的定义
在密码学中,群(Group)的概念是从抽象代数借用来的,它是一种数学结构,通常用于描述具有特定性质的运算集合。
![](https://i-blog.csdnimg.cn/direct/0ae4a216cc6042c2b04c16e4ff02ed8b.png)
群定义中的几个关键要素:
-
集合:首先,群是由一系列元素组成的集合,通常记作 𝐺
-
二元运算:群中存在一个闭合的二元运算,通常用 ⋅ 或 + 表示,这个运算是对群中任意两个元素 𝑎 和 𝑏 定义的,其结果仍然是群 𝐺 中的一个元素,即 𝑎⋅𝑏∈𝐺。在密码学中,这个运算通常是某种形式的加法或乘法,但也可以是更复杂的运算,只要满足群的其他条件即可
-
封闭性:群中的二元运算对所有群内元素都是封闭的,即如果 𝑎 和 𝑏 都属于 𝐺,那么 𝑎⋅𝑏 也一定属于 𝐺
-
结合律:群中的二元运算遵循结合律,即对于所有 𝑎,𝑏,𝑐∈𝐺,有 (𝑎⋅𝑏)⋅𝑐=𝑎⋅(𝑏⋅𝑐)
-
单位元:群中存在一个特殊的元素 𝑒e(也称为单位元或恒等元),对于群中任意元素 𝑎,有 𝑎⋅𝑒=𝑒⋅𝑎=𝑎
-
逆元:对于群中每一个元素 𝑎,存在另一个元素 𝑏(称为 𝑎 的逆元),使得 𝑎⋅𝑏=𝑏⋅𝑎=𝑒,其中 𝑒 是群的单位元
【注】如果一个集合只满足封闭性和结合律,可以称这个它为半群。
二、举例几个群
(1)整数加法群
全体整数Z对于通常的加法成一个群,这个群称为整数加群,在整数加群中,单位元是,
的逆元是
,同样全体有理数集合
,全体实数集合
,全体复数集合
对加法也构成群。
(2)非零实数乘法群
全体非零实数对通常的乘法构成一个群,全体正实数
对通常的乘法也构成一个群。
(3)整数模n加法群
模正整数n的最小非负完全剩余系,对于模
的加法构成一个群,这个群称为整数模
加法群,其单位元为
,
的逆元是
三、有限群和无限群
若群G中只含有有限个元素,则称群G为有限群;若群G中含有无限多个元素,则称群G为无限群。一个有限群G中的元素个数称为群的阶,记为
- 有限群:元素个数有限,是密码学中常见的群类型,因为它们提供了有限的运算空间,适合于设计加密算法和安全协议。
- 无限群:元素个数无限,虽然在纯数学中有着丰富的理论和应用,但在密码学的实际应用中不如有限群普遍。
上例子中的整数加法群和非零实数乘法群是无限群,而整数模n加法群是有限群。
四、交换群
定义:如果群G上的运算还满足交换律,即对于群G中的任意元素都有
则称群G为交换群(又叫Abel群或阿贝尔群)
举例:整数加法群是一个交换群;有理数乘法群也是一个交换群;
五、循环群
定义:如果一个有限群 𝐺 称为循环群,那么存在 𝐺 中的一个元素 𝑔,使得 𝐺 中的每一个元素都可以表示为 𝑔 的幂次,即对于 𝐺 中的任一元素 𝑥,存在一个整数 𝑛 使得 。这里 𝑔 被称为 𝐺 的一个生成元。
我的理解:循环群是一种特殊的抽象代数结构,它满足群的定义,同时还具有一个关键特性:群中存在一个元素,通过其自身的幂次运算可以生成群中的所有其他元素。这个元素被称为群的生成元。
举例:
-
模 𝑛 加法群:考虑整数集
上的加法运算(这里的加法是模 𝑛 加法),如果 𝑛 是质数,则
构成一个循环群,且存在一个生成元 𝑔,使得
中的每个元素都可以表示为 𝑔 的幂次(模 𝑛 运算下)。
-
模 𝑛 乘法群:考虑集合
,即模 𝑛 下与 𝑛 互质的所有整数构成的集合,当 𝑛 是质数时,
构成一个循环群,且存在生成元。
循环群的性质:
- 循环群的阶:循环群的阶等于其生成元的阶,即生成元的最小正整数幂次回到单位元的次数。
- 循环群的子群:循环群的任何子群本身也是一个循环群。
- 循环群的生成元数量:在一个循环群中,生成元的数量通常超过一个,具体数量取决于群的阶和结构。
在了解循环群的概念后,可以进一步的探讨群中的离散对数问题:【密码学】大整数分解问题和离散对数问题https://blog.csdn.net/qq_39780701/article/details/140327361
六、群在密码学中的使用
在密码学中,有限群的性质,如循环子群、生成元、离散对数问题等,被广泛用于设计公钥加密算法、数字签名方案和密钥交换协议。有限群的结构和性质为构建安全的密码系统提供了坚实的数学基础。下面举两个主要的应用:
(1)公钥加密算法
许多公钥加密算法,如RSA、Diffie-Hellman密钥交换协议和椭圆曲线密码学(ECC),都是基于特定的数学难题,而这些问题往往与有限群的性质有关。
- RSA算法:基于大整数分解的困难性,但其数学模型涉及到了模算术下的乘法群,这可以看作是一种特殊的有限群。
- Diffie-Hellman密钥交换:依赖于离散对数问题的难度,这个问题是在有限循环群中定义的。
- 椭圆曲线密码学(ECC):利用了椭圆曲线上点的加法运算形成的有限群。椭圆曲线上的点组成了一个群,这个群的运算规则是由曲线的几何性质决定的。
(2)数字签名
数字签名技术,如DSS(Digital Signature Standard)和ECDSA(Elliptic Curve Digital Signature Algorithm),也基于有限群中的离散对数问题或相关的难题。通过使用群的性质,这些技术能够确保消息的完整性和来源的真实性。