大家好,又见面了,我是你们的朋友全栈君。
文章目录
一、群环域基本概念
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 ∈ R a,b,c∈R a,b,c∈R,有 ( a b ) c = a ( b c ) (ab)c = a(bc) (ab)c=a(bc)。
- (分配律)对于任意的 a , b , c ∈ R a,b,c∈R a,b,c∈R,有
( a + b ) c = a c + b c 和 a ( b + c ) = a b + a c a + b)c = ac + bc 和a(b + c)= ab +ac a+b)c=ac+bc和a(b+c)=ab+ac
则R叫做环.
整环:整环是无零因子的交换幺环
环的定义2——
常见环
3.域与椭圆曲线
满足:
- 两个二进制运算加法(+)和乘法(·),二者都满足封闭性,结合律,交换律,单位元,逆元,乘法对加法满足分配律
- 要求 p p p为素数很重要
椭圆 F p F_p Fp
定义:
{ ( x , y ) ∈ F p 2 ∣ y 2 = x 3 + a x + b , 4 a 3 + 27 b 2 ≠ 0 } ∪ { 0 } \{(x,y)∈F_p^2\;\;\;|\;\;\;y^2=x^3+ax+b,4a^3+27b^2≠0\}∪\{0\} {
(x,y)∈Fp2∣y2=x3+ax+b,4a3+27b2=0}∪{
0}
- 0是无穷远处的点, a , b ∈ F p a,b∈F_p a,b∈Fp
- 对称性,关于 y = p / 2 y=p/2 y=p/2对称
Point addition
F p F_p Fp上椭圆曲线的加法运算法则
- Q + 0 = 0 + Q = Q Q+0=0+Q=Q Q+0=0+Q=Q
- Given a non-zero point Q Q Q , the inverse is the point − Q -Q −Q having the same abscissa but opposite ordinate. Or, if you prefer, − Q = ( x Q , − y Q m o d p ) -Q=(x_Q,-y_Q\;mod\;p) −Q=(xQ,−yQmodp). For example, if a curve in F 2 9 F_29 F29 has a point Q = ( 2 , 5 ) Q=(2,5) Q=(2,5), the inverse − Q = ( 2 , − 5 m o d 29 ) = ( 2 , 24 ) -Q=(2,-5\;mod\;29)=(2,24) −Q=(2,−5mod29)=(2,24)
- Also, P + ( − P ) = 0 P+(-P)=0 P+(−P)=0 (from the definition of inverse element).
Algebraic sum
椭圆曲线群的阶数
我们说过,在有限域上定义的椭圆曲线具有有限数量的点。我们需要回答的一个重要问题是:究竟有多少点?
首先,假设群中的点的个数称为群的阶。
尝试所有可能的值从 0 到 p − 1 p-1 p−1不是计算点数的可行方法,因为它需要 O ( p ) O(p) O(p)步骤,这是”困难的”,如果 p p p是一个大素数。
幸运的是,有一种更快的算法可以计算阶数:Schoof算法(在多项式时间内运行)这就是我们需要的。
Scalar multiplication and cyclic subgroups
标量乘法和循环子群
标量乘: n P = P + P + . . . + P nP=P+P+…+P nP=P+P+...+P
使用double and add algorithm算法在 O ( l o g n ) / O ( k ) , ( k O(log\;n)/O(k),(k O(logn)/O(k),(k是 n n n的比特长度)时间复杂度内
我们称 P P P为generator 或 base point
循环子群是ECC及其他密码系统的基础
Subgroup order子群的阶
子群的阶数是多少呢?
我们不能使用Schoof算法,因为Schoof算法只适用于整个有限域上的椭圆曲线,而不适用于子群。
我们可以定义:
子群的阶数是使得 n P = 0 nP=0 nP=0的最小正整数 n n n,比如前面的例子中,我们的子群包含五个点,我们有 5 P = 0 5P=0 5P=0
子群 P P 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 h=N/n h=N/n
由拉格朗日定理得到
一般我们喜欢群P为素阶,即n是一个素数, N P = 0 NP=0 NP=0,因为 n ∣ N & & n P = 0 n|N\;\&\&\;nP=0 n∣N&&nP=0,因此 G = h P G=hP G=hP
由此,我们得到了一个我们想要的群G,(阶数为n,协因子为h)
注意:n需要是素数,如果n不是素数,则群G的阶为n的一个因子
完整算法如下:
Domain parameters
我们的椭圆曲线算法将在有限域 F p F_p Fp上椭圆曲线的循环子群上工作,我们的算法将需要以下参数,
- 素数 p p p,指定有限域 F p F_p Fp的大小
- 系数a和b,确定椭圆曲线方程
- 基点G,生成子群
- 子群的阶数n
- 子群的协因子h
( p , a , b , G , n , h ) (p,a,b,G,n,h) (p,a,b,G,n,h)
ECC(Elliptic Curve Cryptography)
私钥:一个随机数 d ∈ { 1 , . . . , n − 1 } d∈\{1,…,n-1\} d∈{
1,...,n−1},n是子群的阶数
公钥:点 H = d G H=dG H=dG( G G G是子群的基点)
如果我们知道 d d d和 G G G(以及其他域参数),计算 H H H是”容易”的。
如果我们知道 H H H和 G G G,查找私钥 d d d是”困难”的,因为它要求我们解决离散对数问题
基于此,我将描述两种公钥算法ECDH(椭圆曲线 Diffie-Hellman)和ECDSA(椭圆曲线数字签名算法)
Encryption with ECDH
ECDH是DH密钥协商机制基于椭圆曲线的变体。
工作原理:
- Alice和Bob生成自己的公私钥对,Alice有私钥 d A d_A dA和公钥 H A = d A G H_A=d_AG HA=dAG,Bob有私钥 d B d_B dB和公钥 H B = d B G H_B=d_BG HB=dBG,两者使用相同的域参数
- 两者在不安全信道上交换公钥 H A a n d H B H_A\;and\;H_B HAandHB
- Alice计算 S = d A H B S=d_AH_B S=dAHB,Bob计算 S = d B H A S=d_BH_A S=dBHA,
密钥协商完成shared secret S
S = d A H B = d A ( d B G ) = d B ( d A G ) = d B H A S=d_AH_B=d_A(d_BG)=d_B(d_AG)=d_BH_A S=dAHB=dA(dBG)=dB(dAG)=dBHA
Signing with ECDSA
z z z为截断的哈希值(长度与子群的阶数n长度相同)
Alice 为对消息进行签名而执行的算法的工作方式如下:
- 一个随机值 k ∈ { 1 , . . . , n − 1 } k∈\{1,…,n-1\} k∈{
1,...,n−1}(n是子群阶数) - 计算点 P = k G , G P=kG,G P=kG,G是子群的基点
- 计算 r = x p m o d n r=x_p\;mod\;n r=xpmodn( x p x_p xp是 P P P的 x x x坐标)
- 如果 r r r等于0,重新选择 k k k
- 计算 s = k − 1 ( z + r d A ) m o d n s=k^{-1}(z+rd_A)\;mod\;n s=k−1(z+rdA)modn
- 如果 s = 0 s=0 s=0,重新选取 k k k
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/150418.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...