数论基础——群环域

数论基础——群环域文章目录一、群环域基本概念1.群2.环常见环3.域与椭圆曲线椭圆FpF_pFp​PointadditionAlgebraicsum椭圆曲线群的阶数ScalarmultiplicationandcyclicsubgroupsSubgrouporder子群的阶FindingabasepointDomainparametersECC(EllipticCurveCryptography)EncryptionwithECDHSigningwithECDSA一、群环域基本概念1.群

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

一、群环域基本概念

1.群

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

  1. 结合律,即对任意的a,b,c∈G,都有(ab)c=a(bc)
  2. 单位元,即存在一个元素e∈G,使得对任意的a∈G,都有ae=ea=a
  3. 可逆性,即对任意的a∈,都存在a’∈G,使得aa’ = a’a = e

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

2.环

设R是具有两种结合法(通常表示为加法乘法)的非空集合,如果以下条件成立:
环的定义1——

  1. R对于加法构成交换群。
  2. (结合律)对于任意的 a , b , c ∈ R a,b,c∈R abcR,有 ( a b ) c = a ( b c ) (ab)c = a(bc) abc=abc
  3. (分配律)对于任意的 a , b , c ∈ R a,b,c∈R abcR,有
    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+bc=ac+bcab+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
Fp2y2=x3+ax+b,4a3+27b2=0}{
0}

  • 0是无穷远处的点, a , b ∈ F p a,b∈F_p abFp
  • 对称性,关于 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=(25), 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 p1不是计算点数的可行方法,因为它需要 O ( p ) O(p) Op步骤,这是”困难的”,如果 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 Ologn/Okk n n n的比特长度)时间复杂度内
我们称 P P Pgeneratorbase 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 nN&&nP=0,因此 G = h P G=hP G=hP
由此,我们得到了一个我们想要的群G,(阶数为n,协因子为h)
注意:n需要是素数,如果n不是素数,则群G的阶为n的一个因子
完整算法如下:
在这里插入图片描述

Domain parameters

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

  1. 素数 p p p,指定有限域 F p F_p Fp的大小
  2. 系数a和b,确定椭圆曲线方程
  3. 基点G,生成子群
  4. 子群的阶数n
  5. 子群的协因子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密钥协商机制基于椭圆曲线的变体。
工作原理:

  1. 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,两者使用相同的域参数
  2. 两者在不安全信道上交换公钥 H A    a n d    H B H_A\;and\;H_B HAandHB
  3. 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 为对消息进行签名而执行的算法的工作方式如下:

  1. 一个随机值 k ∈ { 1 , . . . , n − 1 } k∈\{1,…,n-1\} k{
    1...n
    1}
    (n是子群阶数)
  2. 计算点 P = k G , G P=kG,G P=kG,G是子群的基点
  3. 计算 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坐标)
  4. 如果 r r r等于0,重新选择 k k k
  5. 计算 s = k − 1 ( z + r d A )    m o d    n s=k^{-1}(z+rd_A)\;mod\;n s=k1(z+rdA)modn
  6. 如果 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账号...

(0)
blank

相关推荐

  • 2021山东安全员c证考试题库_C类安全员

    2021山东安全员c证考试题库_C类安全员题库来源:安全生产模拟考试一点通公众号小程序2022山东省安全员C证培训试题为山东省安全员C证判断题的新全考试题型!2022年山东省安全员C证考题及答案根据山东省安全员C证考试教材。山东省安全员C证复审模拟考试随时根据安全生产模拟考试一点通上手机同步练习。1、【多选题】一般模板工程通常由()等组成。(ABD)A、面板B、支架C、加固件D、连接件E、螺栓2、【多选题】下列沥青洒布车阀门及油路符合要求的是()。(ABCDE)A、各操作部分应灵活有效,各阀的…

  • 详解MIPI协议

    详解MIPI协议目录前言MIPI简介MIPI联盟的MIPIDSI规范MIPI名词解释MIPIDSI分层结构command和video模式D-PHYLane模组Lane全局架构Lane电压和状态DATALANE操作模式时钟LANE低功耗状态高速数据传输高速CLK传输D-PHY总结DSICSI前言MIPI接口的内部非常复杂,如果不是专门去做MIPI接口,没有必要像研究H264一样往深入的去研究。我们知道MIPI协议连接了camera与soc、LCD和soc,作为此间的开发者,我们只需要关注他怎么使用就可以了知识

  • 手把手教你linux系统安装和完美配置

    手把手教你linux系统安装和完美配置Linux系统虚拟机安装

  • weblogic环境,应用上传图片报Could not initialize class sun.awt.X11.XToolkit

    weblogic环境,应用上传图片报Could not initialize class sun.awt.X11.XToolkit

  • Linux offsetof宏定义

    Linux offsetof宏定义#include&lt;stddef.h&gt;size_t offsetof(type, member) #define offsetof(TYPE, MEMBER)        \           ((size_t)&amp;((TYPE*)0)-&gt;MEMBER) Themacroreturntheoffsetofthe…

  • 数字电路实验(01)基本逻辑运算及其电路实现

    数字电路实验(01)基本逻辑运算及其电路实现题目实验要求一、实验目的1.认识逻辑值1、0和逻辑门的输入、输出信号电平之间的关系;2.从逻辑门的输入、输出电平的关系去认识逻辑与(与非)、或、非的运算;3.熟悉基本逻辑门的使用。二、实验

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号