数论基础——群环域

数论基础——群环域文章目录一、群环域基本概念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)


相关推荐

  • JAVA:基于ARCGIS二次开发可视化开发环境搭建

    JAVA:基于ARCGIS二次开发可视化开发环境搭建这两天为了搭建这么一个基于java的ArcGIS二次开发环境可着实花了一番心血。在网上搜索各种资料,大部分都是基于C#的,关于JAVA的很少,而且很杂乱,没有一个完整的、详细的、适合新手的这么一个教程。所以,当我在奋斗两天且重装一次系统,终于安装成功之后,写下这篇文章,让用java进行基于ArcEngine二次开发的人可以少走弯路。因为ArcEngine只能在32位系统上面运行,所以当前系统为64

  • 最全的PHP后台管理系统源码「建议收藏」

    最全的PHP后台管理系统源码「建议收藏」一款PHP语言基于ThinkPhp6.x+Layui+MySQL等框架精心打造的一款模块化、插件化、高性能的前后端分离架构敏捷开发框架,可用于快速搭建前后端分离后台管理系统,本着简化开发、提升开发效率的初衷,框架自研了一套个性化的组件,实现了可插拔的组件式开发方式:单图上传、多图上传、下拉选择、开关按钮、单选按钮、多选按钮、图片裁剪等等一系列个性化、轻量级的组件,是一款真正意义上实现组件化开发的敏捷开发框架,框架已集成了完整的RBAC权限架构和常规基础模块,同时支持多

  • SqlTransaction——事务详解[通俗易懂]

    SqlTransaction——事务详解[通俗易懂]Postedon2008-07-2001:46停留的风http://www.cnblogs.com/yank/archive/2008/07/20/1246896.html事务处理基本原理           事务是将一系列操作作为一个单元执行,要么成功,要么失败,回滚到最初状态。在事务处理术语中,事务要么提交,要么中止。若要提交事务,所有参与者都必须保证对数据

  • SQL SERVER与C#中数据类型的对应关系

    对应关系表SQLServer2000 http://hovertree.com/menu/sqlserver/C#CodeSmith数据类型取值范围数据类型取值范围空值代

    2021年12月27日
  • java二维数组初始化和基本操作

    java二维数组初始化和基本操作来源:http://www.jb51.net/article/73871.htm

  • 二叉树的先序,中序,后序遍历的序列_二叉树先序遍历和后序遍历正好相反

    二叉树的先序,中序,后序遍历的序列_二叉树先序遍历和后序遍历正好相反    二叉树的遍历主要有三种:(1)先(根)序遍历(根左右)(2)中(根)序遍历(左根右)(3)后(根)序遍历(左右根)举个例子:先(根)序遍历(根左右):ABDHEICFJKG中(根)序遍历(左根右):DHBEIAJFKCG后(根)序遍历(左右根):HDIEBJKFGCA    以后(根)序…

发表回复

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

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