大家好，又见面了，我是你们的朋友全栈君。

文章目录

一、群环域基本概念

一、群环域基本概念

1.群

环的概念：
G是一个具有结合律的非空集合，若G满足：

结合律，即对任意的a，b，c∈G，都有（ab）c=a（bc）
单位元，即存在一个元素e∈G，使得对任意的a∈G，都有ae=ea=a
可逆性，即对任意的a∈，都存在a’∈G，使得aa’ = a’a = e

特别的，当G的结合法写作乘法时，G叫乘群，当G写作加法时，G叫加群。
群G的元素个数叫做群G的阶，记为|G|，当|G|为有限数时，G叫做有限群，反之，无限群。
密码学中使用的群大多数为循环群

2.环

设R是具有两种结合法（通常表示为加法和乘法）的非空集合，如果以下条件成立：
环的定义1——

R对于加法构成交换群。
（结合律）对于任意的 $a ， b ， c \in R$ ，有 $（ a b ） c = a （ b c ）$ 。
（分配律）对于任意的 $a ， b ， c \in R$ ，有
（ $a + b ） c = a c + b c 和 a （ b + c ） = a b + a c$
则R叫做环.
整环：整环是无零因子的交换幺环

环的定义2——

常见环

3.域与椭圆曲线

满足：

两个二进制运算加法（+）和乘法（·），二者都满足封闭性，结合律，交换律，单位元，逆元，乘法对加法满足分配律
要求 $p$ 为素数很重要

椭圆 $F_p$

定义：
${(x,y）∈F_p^2\;\;\;|\;\;\;y^2=x^3+ax+b,4a^3+27b^2≠0\}∪\{0\}$

0是无穷远处的点， $a，b∈F_p$
对称性，关于 $y = p / 2$ 对称

Point addition

$F_p$ 上椭圆曲线的加法运算法则

$Q + 0 = 0 + Q = Q$
Given a non-zero point $Q$ , the inverse is the point $- Q$ having the same abscissa but opposite ordinate. Or, if you prefer, $Q=(x_Q,-y_Q\;mod\;p)$ . For example, if a curve in $F_29$ has a point $Q = (2 ， 5)$ , the inverse $-Q=(2,-5\;mod\;29)=(2,24)$
Also, $P + (- P) = 0$ (from the definition of inverse element).

Algebraic sum

椭圆曲线群的阶数

我们说过，在有限域上定义的椭圆曲线具有有限数量的点。我们需要回答的一个重要问题是：究竟有多少点？

首先，假设群中的点的个数称为群的阶。

尝试所有可能的值从 0 到 $p - 1$ 不是计算点数的可行方法，因为它需要 $O （ p ）$ 步骤，这是”困难的”，如果 $p$ 是一个大素数。

幸运的是，有一种更快的算法可以计算阶数：Schoof算法（在多项式时间内运行）这就是我们需要的。

Scalar multiplication and cyclic subgroups

标量乘法和循环子群
标量乘： $n P = P + P + . . . + P$
使用double and add algorithm算法在 $O（log\;n）/O（k），（k$ 是 $n$ 的比特长度）时间复杂度内
我们称 $P$ 为generator 或 base point
循环子群是ECC及其他密码系统的基础
在这里插入图片描述

Subgroup order子群的阶

子群的阶数是多少呢？
我们不能使用Schoof算法，因为Schoof算法只适用于整个有限域上的椭圆曲线，而不适用于子群。
我们可以定义：
子群的阶数是使得 $n P = 0$ 的最小正整数 $n$ ，比如前面的例子中，我们的子群包含五个点，我们有 $5 P = 0$
子群 $P$ 的阶数通过拉格朗日定理与父群的阶数相关，拉格朗日定理指出，子群P的阶数是父群的阶数的除数（divisor），换句话说，如果有限域上的椭圆曲线包含N个点，他的一个子群包含n个点，n|N

n|N   <=>   n是N的一个除数   <=>   n is a divisor of N

在这里插入图片描述
请注意，要采用最小的除数，而不是随机的除数

Finding a base point

对于一个ECC算法，我们需要一个高阶的子群，一般来说，我们会先选择一条椭圆曲线，然后计算他的阶数N，选择一个比较大的因子作为子群的阶，最终去寻找一个合适的基点
子群的协因子h（cofactor of subgroup）： $h = N / n$
由拉格朗日定理得到
一般我们喜欢群P为素阶，即n是一个素数， $N P = 0$ ，因为 $n|N\;\&\&\;nP=0$ ，因此 $G = h P$
由此，我们得到了一个我们想要的群G，（阶数为n，协因子为h）
注意：n需要是素数，如果n不是素数，则群G的阶为n的一个因子
完整算法如下：
在这里插入图片描述

Domain parameters

我们的椭圆曲线算法将在有限域 $F_p$ 上椭圆曲线的循环子群上工作，我们的算法将需要以下参数，

素数 $p$ ，指定有限域 $F_p$ 的大小
系数a和b，确定椭圆曲线方程
基点G，生成子群
子群的阶数n
子群的协因子h

$(p, a, b, G, n, h)$

ECC(Elliptic Curve Cryptography)

私钥：一个随机数 $d∈\{1,…,n-1\}$ ,n是子群的阶数
公钥：点 $H = d G$ （ $G$ 是子群的基点）
如果我们知道 $d$ 和 $G$ （以及其他域参数），计算 $H$ 是”容易”的。
如果我们知道 $H$ 和 $G$ ,查找私钥 $d$ 是”困难”的，因为它要求我们解决离散对数问题
基于此，我将描述两种公钥算法ECDH（椭圆曲线 Diffie-Hellman）和ECDSA（椭圆曲线数字签名算法）

Encryption with ECDH

ECDH是DH密钥协商机制基于椭圆曲线的变体。
工作原理：

Alice和Bob生成自己的公私钥对，Alice有私钥 $d_A$ 和公钥 $H_A=d_AG$ ，Bob有私钥 $d_B$ 和公钥 $H_B=d_BG$ ，两者使用相同的域参数
两者在不安全信道上交换公钥 $H_A\;and\;H_B$
Alice计算 $S=d_AH_B$ ,Bob计算 $S=d_BH_A$ ,
密钥协商完成shared secret S
$S=d_AH_B=d_A(d_BG)=d_B(d_AG)=d_BH_A$

Signing with ECDSA

$z$ 为截断的哈希值（长度与子群的阶数n长度相同）
Alice 为对消息进行签名而执行的算法的工作方式如下：

一个随机值 $k∈\{1，…，n-1\}$ （n是子群阶数）
计算点 $P = k G, G$ 是子群的基点
计算 $r=x_p\;mod\;n$ ( $x_p$ 是 $P$ 的 $x$ 坐标)
如果 $r$ 等于0，重新选择 $k$
计算 $s=k^{-1}(z+rd_A)\;mod\;n$
如果 $s = 0$ ，重新选取 $k$

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/150418.html原文链接：https://javaforall.net

数论基础——群环域

文章目录

一、群环域基本概念

1.群

2.环

常见环