精华内容
下载资源
问答
  • 该资源为2019全国高校密码数学挑战赛 赛题 1 椭圆曲线离散对数问题
  • 离散对数赛题

    2018-11-30 17:23:34
    第三届全国高校面挑战赛的试题,由D—H氏密码协议引出的DLP问题
  • 本文讨论计算离散对数的高位比特与计算离散对数的等价性,利用D. Boneh所提出的方法对密码学上通常使用的强素数讨论了离散对数的比特安全性,得到结论:如果离散对数的高位比特可以计算,那么存在计算离散对数的有效...
  • 离散对数

    千次阅读 2019-10-06 16:06:42
     在数学中,对数是对求幂的逆运算,正如除法是乘法的倒数,反之亦然。 这意味着一个数字的对数是必须产生另一个固定数字(基数)的指数  如果a的x次方等于N(a>0,且a不等于1),那么数x叫做以a为底N的...

    写在前面:

      学习笔记,方便复习

      非原创标明出处

    我们都在努力奔跑,我们都是追梦人

     

    by skecchiart

     

    概念

    对数

      在数学中,对数是对求幂的逆运算,正如除法是乘法的倒数,反之亦然。 这意味着一个数字的对数是必须产生另一个固定数字(基数)的指数

      如果ax次方等于N(a>0,且a不等于1),那么数x叫做以a为底N的对数,记作x==logaN

      其中,a叫做对数的底数,N叫做真数

    ——bia度百科

     

      设ap是整数,ap互素,那么:使an ≡ 1 (mod p)成立的最小正整数n叫做ap的阶

    ——bia度百科

     

    原根

      设m是正整数,a是整数,若am的阶等于φ(m),则称a为模m的一个原根

    ——bia度百科

      即:aφ(m) ≡ 1 (mod m)

      此处am的阶为φ(m)

     

      循环节见:

      [◹]同余定理

      [◹]费马-欧拉定理

     

    离散对数

      在整数中,离散对数是一种基于同余运算和原根的一种对数运算

      任何群G([◹]初等群论)中可为所有整数k定义一个幂数为bx,而离散对数logba是指使得bx a的整数k

      离散对数在一些特殊情况下可以快速计算,然而,通常没有具非常效率的方法来计算它们

      公钥密码学中几个重要算法的基础,是假设寻找离散对数的问题解,在仔细选择过的群中,并不存在有效率的求解算法

    ——bia度百科

      The discrete log problem is of fundamental importance to the area of public key cryptography. Many of the most commonly used cryptography systems are based on the assumption that the discrete log is extremely difficult to compute; the more difficult it is, the more security it provides a data transfer

      One way to increase the difficulty of the discrete log problem is to base the cryptosystem on a larger group

    ——Wikipedia

    译:

      离散对数问题在公钥密码领域具有重要意义,许多最常用的密码系统都是基于这样一个现象:离散对数极难计算,而它越困难,提供数据传输的安全性就越高

      提高离散对数问题难度的一种方法是将密码建立在一个较大的群上

    举个例子:

    对数

    8==23

    log28==3

     

    离散对数

    8+n*k ≡ 23 (mod k)

    log2(8+n*k) ≡ 3 (mod φ(k))

      指数循环节见[◹]同余定理

     

    实现

    • [◹]Baby-step giant-step算法

    • [◹]拓展Baby-step giant-step算法

     

    转载于:https://www.cnblogs.com/Antigonae/p/10262342.html

    展开全文
  • 使用指数演算法求解离散对数问题 描述 使用指数演算法求解离散对数问题(β=αamod p)。 任务是找到一个已知的β值。 您将使用p = 10930889,并对由α= 2317547形成的子组执行计算。该子组的阶次为59407。请注意,...
  • 椭圆曲线密码学(英语:Elliptic curve cryptography,缩写为 ECC),一种建立公开密钥加密的算法,基于椭圆曲线数学。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的
  • 离散对数计算器

    2011-08-25 15:19:12
    离散对数计算器
  • 离散对数密码学原理

    千次阅读 2020-05-04 11:52:55
    这里写自定义目录标题简介离散对数基本概念离散对数密钥的产生离散对数加密离散对数系统的数字签名 简介 1976年,Diffifie和Hellman提出了首个离散对数系统,该方法是一种密钥协商协议。1984年,ElGamal提出了基于...

    一 简介

    离散对数被誉为当代密码学领域的三大基础之一。1976年,Diffifie和Hellman提出了一种密钥协商协议, 产生了首个离散对数系统模型;8年后,ElGamal提出了基于离散对数系统的公钥加密和签名方法,并奠定了离散对数密码学基础。从那时起,围绕离散对数系统产生了不少研究成果,本文阐述离散对数的基本概念,然后介绍基于离散对数的ElGamal的公钥加密方法和数字签名方法(DSA)。

    二 离散对数基本概念

    在实数域,对数 x = log ⁡ b a x=\log_b a x=logba表示b为底,目标数为a的幂x,换句话说,对数是求幂x的逆运算,使得 b x = a b^x=a bx=a。假设指数函数 b k ( k ∈ I ) b^k(k \in I) bk(kI)的所有元素组成群G,那么离散对数 l o g b a log_ba logba的值必定为整数k,满足 b k = a b^k=a bk=a。可见,离散对数专指满足幂等条件的整数值,属于数论范畴。不失一般性,通过引入索引 i n d r ind_r indr,可以得到一般形式的定义:
    x = i n d r a ( m o d   m ) x=ind_r a(mod \space m) x=indra(mod m)
    其中,r是基本根,m是模数,满足gcd(a,m) = 1(a和m互质)。
    基于以上定义,引出离散对数问题,即:给定质数p和正整数g,知道 y = g x ( m o d   p ) y=g^x(mod\space p) y=gx(mod p)的值,求解x。这个问题的求解超过多项式时间,难度是相当大的;反过来,知道x,求解 y = g x ( m o d   p ) y=g^x(mod\space p) y=gx(mod p)的速度却相当快。用一句歌词“爱到尽头,覆水难收”来比喻,像极了泼出去的水,把水泼出去很容易,要将地上的水收回来,超级难!
    离散对数加密系统正是利用了这一正反向求解难度不相同的原理。

    三 基于离散对数的ElGamal的加密方法

    离散对数系统的参数构成一个集合,称为与公共参数域(p,q,g),其中p是一个质数,q是p-1的分解质因数,具有阶数q(群元素的个数称为阶,若p是质数,阶为p-1)。

    离散对数密钥的产生

    设x为私钥,其值为整数,随机且均匀的从区域[1,q-1]中选取,y为公钥。参考前述定义,离散对数问题(DLP)可描述为给定公共参数域(p,q,g)和y,确定x的问题。具有以下关系:
    在这里插入图片描述
    离散对数参数域产生算法如下。

    离散对数参数生成算法

    输入:安全参数l(p的长度位数),t(q的长度位数).
    输出:离散对数参数域(p,q,g)
    1.选取长度位数为l的质数p,长度位数为t的质数q,确保q能够整除p-1;
    2.选择基本根g,具有阶数q; 
       2.1 选择任意的整数h,范围在[1,p-1],计算 g = h^(p-1)/q ( mod p).
       2.2 如果 g=1,goto 2.1
    3. 返回(p,q,g)   
    

    一个栗子
    这里举个栗子,作为对以上算法执行流程的复盘:设l 和 t 同为4,即p和q取值不大于15。假设选p为11,q为质数,且能整除11-1=10,因此q等于5。p,q一旦确定,接下来就可以求g了。 根据步骤2.1,g的取值范围在[1,10],我们从h=1开始逐个数遍历,计算
    g = h ( p − 1 ) / q m o d    p = h 2 m o d    11 g=h^{(p-1)/q}\mod p=h^2\mod 11 g=h(p1)/qmodp=h2mod11
    通过计算,依次得到这样一组数(h,g):( 1 , 1 ‾ \underline\bold{1,1} 11)(2,4) (3,9)(4,5)(5,3)(6,3)(7,5)(8,9)(9,4)( 10 , 1 ‾ \underline\bold{10,1} 101)。根据步骤2.2,只有第1组和第10组数(黑体下划线)的g=1,不满足选取要求。我们随机取g=3。

    下面给出公钥y和私钥x的 产生算法

    离散密钥对产生算法:

    输入:离散对数公共域(p,q,g)
    输出:(y,x)
    1. 随机选取私钥x,范围在[1,q-1]
    2. 计算 y = g^x mod p
    3. 返回(y,x)。在这里插入代码片
    

    继续前一个栗子
    在[1,10]的范围内选取x=6,计算 y = 3 6 m o d    11 = 3 y=3^6\mod 11=3 y=36mod11=3,返回 ( x , y ) = ( 6 , 3 ) (x,y)=(6,3) (x,y)=(6,3)

    离散对数加密

    一切准备就绪,我们现在获得了一组离散对数公有域 ( p , q , g ) = ( 11 , 5 , 3 ) (p,q,g)=(11,5,3) (p,q,g)=(11,5,3),还在此基础上创建了一个公私钥对 ( x , y ) = ( 6 , 3 ) (x,y)=(6,3) (x,y)=(6,3)。离散对数加密的基础就建立起来了。下面轮到我们年轻英俊的主角刘英俊出场了。刘英俊和美如花因为仙界诅咒,一直得不到凡间的祝福。地下恋情得以为继,促使男主人公在不公开恋情的同时,还和女主维系着剪不断理还乱的"亲情“和”友情“。那么怎么向如花传递爱的信号呢?
    某日,英俊向如花发了一条信息:“爱到尽头,覆水难收”,为了避开邪恶的损友和多情的闺蜜,他用事先约定的数字密码发送:2406(爱死你了),3344(生生世世)。
    设y为如花的提供的公钥,英俊利用y将明文m(24063344)转换成密文c1,具体操作为:
    在这里插入图片描述
    其中k=2是英俊随机挑选的随机数。计算的结果是 c 1 = 24063344 × ( 3 2 m o d    11 ) = 216 , 570 , 096 c_1=24063344 \times (3^2\mod 11)=216,570,096 c1=24063344×32mod11=216570096
    同时,计算参数c2如下:
    在这里插入图片描述
    结果是 c 2 = 3 2 m o d    11 = 9 c_2=3^2\mod11=9 c2=32mod11=9。随后,英俊将(c1,c2)=(216570096, 9)发给如花。如花用珍藏的私钥x=5计算以下同余公式:
    在这里插入图片描述
    得到 c 2 = 9 6 m o d    11 = 531441 m o d    11 = 9 c_2=9^6\mod11=531441\mod11=9 c2=96mod11=531441mod11=9。再用 c 2 = 9 c_2=9 c2=9除以c1,就可以计算出明文 m = 216570096 ÷ 9 = 2406 , 3344 m=216570096\div9=2406,3344 m=216570096÷9=2406,3344
    下面是具体的证明。
    在这里插入图片描述
    基本ElGamal加密算法和解密算法分别描述如下:

    基础ElGamal加密算法
    在这里插入图片描述
    基础ElGamal解密算法
    在这里插入图片描述

    美如花回信“爱你在心口难开”,用同样的方式将信息传递英俊。显然,邪恶损友要恢复明文m,须在已知公共域参数(p,q,g)和y的 前提下计算x,难度之大,足以使2人百年好合,白头偕老。这个任务也被成为Diffie-Hellman问题(DHP)。

    四 基于离散对数的ElGamal数字签名

    数字签名算法(DSA)是美国标准委员会(NIST)于1991年提出的,被指定为美国联邦信息处理标准(FIPS186)。为了进一步描述数字签名算法,假设签名者具有密钥x,他从整数区间[1,q-1]随机选取整数k,计算如下参数:
    在这里插入图片描述
    其中h=H(m)是用哈希函数计算的消息摘要。签名者对明文m的签名表示为(r,s)。为验证签名的真实性, 校验者需要根据(r,s)并计算上面公式。然而,校验者没有获得签名者的私钥x和随机数k,自然无法按照公式验签。因此, 需要对上面的公式做一下变形:
    在这里插入图片描述
    将k带入:
    在这里插入图片描述
    得到:
    在这里插入图片描述
    再根据公钥y的定义:
    在这里插入图片描述
    推导出:
    在这里插入图片描述
    验证者因此可以通过上式对T进行校验。
    离散对数系统签名算法
    在这里插入图片描述
    离散对数验签的算法在这里插入图片描述

    五 总结

    离散对数系统建立在有限循环群的基础上,为了增加系统的安全性,人们千方百计扩大质数p的取值范围, 迄今为止,人类发现的已知最大质数是 2 82 , 589 , 933 − 1 2^{82,589,933} − 1 282,589,9331。然而根据欧拉定理,p的值是无穷的。也许通过不断探索,科学家才能够发现迄今算力需要上亿年才能分解的超大型整数。

    [1]: Darrel Hankerson (Author), Alfred J. Menezes (Author), Scott Vanstone (Author),Guide to Elliptic Curve Cryptography,book,Springer Professional Computing,2003。
    [2]: https://en.wikipedia.org/wiki/Discrete_logarithm

    展开全文
  • Pollard ρ\rhoρ 算法求解离散对数问题 离散对数(DLP)问题:设有群(G,⋅)(G,\cdot)(G,⋅),α∈G\alpha \in Gα∈G是一个nnn阶元素。给定β∈<α>\beta \in \left< \alpha \right>β∈⟨α⟩,找到指数...

    Pollard ρ \rho ρ 算法求解离散对数问题

    离散对数(DLP)问题:设有群 ( G , ⋅ ) (G,\cdot) (G,) α ∈ G \alpha \in G αG是一个 n n n阶元素。给定 β ∈ < α > \beta \in \left< \alpha \right> βα,找到指数 c , 0 ≤ c ≤ n − 1 c,0\le c\le n-1 c0cn1,满足
    α c = β \alpha ^{c} =\beta αc=β前面分享过因子分解的Pollard ρ \rho ρ 算法(为了更好地理解Pollard ρ \rho ρ 离散对数算法,建议读者先看Pollard ρ \rho ρ 因子分解算法),也分享过求解离散对数问题的小步大步算法Pohlig-Hellman算法
    Pollard ρ \rho ρ 算法是启发式的算法,不是确定性的数学证明算法,它可能得到较好的解,也可能会失败,这取决于攻击者选取的初始参数。

    算法思想

    类似Pollard ρ \rho ρ 因子分解算法。为了求解出 c = log ⁡ α β c=\log_{\alpha}\beta c=logαβ,直接求是困难的,我们希望构造出一个关于 c c c的一次同余方程,通过解方程间接得到 c c c。Pollard ρ \rho ρ的因子分解算法是寻找一个碰撞 x = x ′ x=x' x=x,所以这里也想找一个碰撞。

    准备工作

    1. S 1 ∪ S 2 ∪ S 3 S_{1} \cup S_{2}\cup S_{3} S1S2S3是群 G G G的一个划分,它们元素个数大致相同。

    2. 定义函数 f : < α > × Z n × Z n → < α > × Z n × Z n f:\left< \alpha \right> \times \mathbb{Z}_{n} \times \mathbb{Z}_{n} \rarr \left< \alpha \right> \times \mathbb{Z}_{n} \times \mathbb{Z}_{n} f:α×Zn×Znα×Zn×Zn如下
      在这里插入图片描述
      并且要求构造的三元组 ( x , a , b ) (x,a,b) (x,a,b)满足 x = α a β b x=\alpha^{a}\beta^{b} x=αaβb,比如 ( 1 , 0 , 0 ) (1,0,0) (1,0,0)可以看出如果 ( x , a , b ) (x,a,b) (x,a,b)满足这个性质,则 f ( x , a , b ) f(x,a,b) f(x,a,b)也满足这个性质


    3. 在这里插入图片描述

    算法核心

    计算三元组 ( x i , a i , b i ) (x_{i},a_{i},b_{i}) (xi,ai,bi) ( x 2 i , a 2 i , b 2 i ) (x_{2i},a_{2i},b_{2i}) (x2i,a2i,b2i),直到发现 x 2 i = x i , i ≥ 1 x_{2i}=x_{i},i\ge 1 x2i=xii1。此时有
    α a i β b i = α a 2 i β b 2 i \alpha^{a_{i}}\beta^{b_{i}}=\alpha^{a_{2i}}\beta^{b_{2i}} αaiβbi=αa2iβb2i因为 β = α c \beta = \alpha ^{c} β=αc,所以有
    α a i + c b i = α a 2 i + c b 2 i \alpha^{a_{i}+cb_{i}}=\alpha^{a_{2i}+cb_{2i}} αai+cbi=αa2i+cb2i因为 α \alpha α的阶是 n n n,所以有
    a i + c b i ≡ a 2 i + c b 2 i ( m o d n ) a_{i}+cb_{i} \equiv a_{2i}+cb_{2i} \pmod{n} ai+cbia2i+cb2i(modn) c ( b 2 i − b i ) ≡ a i − a 2 i ( m o d n ) c(b_{2i}-b_{i}) \equiv a_{i} - a_{2i} \pmod{n} c(b2ibi)aia2i(modn)如果 g c d ( n , b 2 i − b i ) = 1 gcd(n,b_{2i}-b_{i}) = 1 gcd(n,b2ibi)=1,则可以解出
    c = ( a i − a 2 i ) ( b 2 i − b i ) − 1 m o d    n c=(a_{i} - a_{2i})(b_{2i}-b_{i})^{-1}\mod{n} c=(aia2i)(b2ibi)1modn如果 g c d ( n , b 2 i − b i ) ≠ 1 gcd(n,b_{2i}-b_{i}) \ne 1 gcd(n,b2ibi)=1,可以利用扩展的 g c d gcd gcd解一次线性同余方程

    例子

    问题:群 G = Z 809 ∗ G=\mathbb{Z}_{809}^{*} G=Z809 α = 89 \alpha = 89 α=89 β = 618 \beta = 618 β=618 α \alpha α的阶 n = 101 n=101 n=101。下面计算 log ⁡ α β \log_{\alpha}\beta logαβ

    1. G G G做划分:
      S 1 = { x ∈ Z 809 ∗ : x ≡ 1 ( m o d 3 ) } S 2 = { x ∈ Z 809 ∗ : x ≡ 0 ( m o d 3 ) } S 3 = { x ∈ Z 809 ∗ : x ≡ 2 ( m o d 3 ) } S_{1} = \lbrace x\in \mathbb{Z}_{809}^{*}:x\equiv 1\pmod{3} \rbrace \\ S_{2} = \lbrace x\in \mathbb{Z}_{809}^{*}:x\equiv 0\pmod{3} \rbrace \\ S_{3} = \lbrace x\in \mathbb{Z}_{809}^{*}:x\equiv 2\pmod{3} \rbrace S1={xZ809:x1(mod3)}S2={xZ809:x0(mod3)}S3={xZ809:x2(mod3)}

    2. i = 1 , 2 , ⋯ i=1,2,\cdots i=1,2,,计算三元组 ( x i , a i , b i ) (x_{i},a_{i},b_{i}) (xi,ai,bi) ( x 2 i , a 2 i , b 2 i ) (x_{2i},a_{2i},b_{2i}) (x2i,a2i,b2i),有

    i i i ( x i , a i , b i ) (x_{i},a_{i},b_{i}) (xi,ai,bi) ( x 2 i , a 2 i , b 2 i ) (x_{2i},a_{2i},b_{2i}) (x2i,a2i,b2i)
    1 ( 618 , 0 , 1 ) (618,0,1) (618,0,1) ( 76 , 0 , 2 ) (76,0,2) (76,0,2)
    2 ( 76 , 0 , 2 ) (76,0,2) (76,0,2) ( 113 , 0 , 4 ) (113,0,4) (113,0,4)
    3 ( 46 , 0 , 3 ) (46,0,3) (46,0,3) ( 488 , 1 , 5 ) (488,1,5) (488,1,5)
    4 ( 113 , 0 , 4 ) (113,0,4) (113,0,4) ( 605 , 4 , 10 ) (605,4,10) (605,4,10)
    5 ( 349 , 1 , 4 ) (349,1,4) (349,1,4) ( 422 , 5 , 11 ) (422,5,11) (422,5,11)
    6 ( 488 , 1 , 5 ) (488,1,5) (488,1,5) ( 683 , 7 , 11 ) (683,7,11) (683,7,11)
    7 ( 555 , 2 , 5 ) (555,2,5) (555,2,5) ( 451 , 8 , 12 ) (451,8,12) (451,8,12)
    8 ( 605 , 4 , 10 ) (605,4,10) (605,4,10) ( 344 , 9 , 13 ) (344,9,13) (344,9,13)
    9 ( 451 , 5 , 10 ) (451,5,10) (451,5,10) ( 112 , 11 , 13 ) (112,11,13) (112,11,13)
    10 ( 422 , 5 , 11 ) (422,5,11) (422,5,11) ( 422 , 11 , 15 ) (422,11,15) (422,11,15)

    可以发现, x 10 = x 20 x_{10} = x_{20} x10=x20
    3. 解方程 c = ( 5 − 11 ) ( 15 − 11 ) − 1 m o d    101 = 49 c=(5-11)(15-11)^{-1}\mod{101}=49 c=(511)(1511)1mod101=49。所以z在 Z 809 ∗ \mathbb{Z}_{809}^{*} Z809 log ⁡ 89 618 = 49 \log_{89}618=49 log89618=49

    注意事项

    1. 在划分群 G G G时,必须保证 1 ∉ S 2 1\notin S_{2} 1/S2,否则根据 f f f的定义,对 ∀ i ≥ 0 \forall i \ge 0 i0,都有 ( x i , a i , b i ) = ( 1 , 0 , 0 ) (x_{i},a_{i},b_{i})=(1,0,0) (xi,ai,bi)=(1,0,0)
    2. 如果初始参数设置合理,在 n n n阶循环群情况下算法复杂度为 O ( n ) O(\sqrt{n}) O(n )

    参考书籍:Stinson D , 斯廷森, 冯登国. 密码学原理与实践[M]. 电子工业出版社, 2009.

    展开全文
  • 本章的意义在于对因子分解和离散对数这些问题的有效算法 。这些算法本身是有趣 的 ,并可作为 己学过的数论知识的良好应用 。此外 ,理解这些算法的效率对于在实际应用中选择密码学参数是至关重要的 文章目录因式...

    本章的意义在于对因子分解和离散对数这些问题的有效算法 。这些算法本身是有趣的,并可作为己学过的数论知识的良好应用 。此外 ,理解这些算法的效率对于在实际应用中选择密码学参数是至关重要的

    因式分解算法

    • 亚指数:如果f(n)= 2^o(n) , 则f是关于n的亚指数
    • Pollard的p - 1方法 ,当p-1有 “ 小 ” 素数因子时它是种有效的方法 。
    • Pollard的rho方法, 这种方法适用于任意的N因此, 这种方法还被称为 “通用 ” 因子分解算法。对于本节开始部分讨论的那种类型的 整数N来 说 , 它的时间复 杂度是O(N^1/4*polylog(N))
    • 二次筛算法 ,这是一种通用因子分解算法,运行时间的复杂度为(关于N的长度)亚指数

    Pollard的p - 1方法

    整数N = pq且p - 1只有 “ 小 ” 因子时,能找到一个元素y属于Z*N且y<——>(1,y< q>),且y< q>!=1
    所以gcd(y, N) = p,于是就得到了一个因子,求y的方法如下:假设能找到一个B使得 (p − 1)| B and (q − 1)!| B,令B=r(p-1)于是算法如下:
    在这里插入图片描述下面证明算法生成的y是不是满足上述条件

    1. 证明 y=0modp
      在这里插入图片描述

    2. 证明 y!=0modq
      在这里插入图片描述
      但如果xq是生成元的话上述结论结不成立(生成元的B次方有可能正好为1),但因为生成元的个数为φ(q - 1 ),modq的域大小为q-1,所以概率由下面定理得到Ω(1/ log q) = Ω( 1/n),即可忽略

      • 一个定理:在这里插入图片描述通常认为
        在这里插入图片描述

    选择B的方法:
    在这里插入图片描述

    • pi表示第i个素数
    • k代表一个范 围 ,它影响时间复杂度和算法成功的概率
    • n是p的长度
    • pi^ [n/log pi]表示能整除p-1的最大的pi的幂
    • 只要q-1一个素数因子比Pk大,那么(q - 1) )!|B
    • 所以当增加k的值,会增加运算复杂度,但会提高找到B的成功率

    Pollard的rho方法

    对比p-1算法,rho算法可以找到任意整数N的非平凡因子,不用对p和q值有任何假设,算法复杂度:在这里插入图片描述

    思想:N=pq,找到Good对(x,x’)有x-x’=0 mod p,且x-x’ !=0 mod N,那么p=gcd(x − x’, N)。我们从均匀选取x1,x2…xk,其中k=2^(n/2)=O(p ^1/2),然后双射到在这里插入图片描述
    所以根据某种结论,约1/4的概率存在i,j使得x(i)=x(j)mod p,可以在O(√p)=O(N1/4)时间内生成k个元素,然后测试所有数对,将花费O(k2)=O(N1/2)的时间。这种方法因为p是未知的,需要计算所有数对来和N求gcd,所以并不比试除法好

    二次筛算法

    仅仅描述了算法的思想,对某些计算做了省略。
    如果存在元素x ∈Zn,满足条件x^2 = z mod N,则元素z ∈Zn是模N的一个二次剩余,这种情况下称x为z的平方根。一些结论:

    1. 如果N= pq是两个不同素数的乘积,那么N的每个二次平方剩余都恰好有四个平方根
    2. 给定x,y满足x2= ymod N且x≠ ±y mod N,则在多项式时间内计算N的一个非平凡因子是可能的。及gcd(x-y,N)为N的其中一个因子

    二次筛的目的是生成x,y,有x2=y2 mod N,且保证x!=±y,步骤如下:

    1. 规定一个小素数组成的集合B= {P1,…,Pk},寻找不同的数x1,…. xl∈ Zn(l>k)使得qi=[xi2mod N]足够“小”,以便能被分解,而且使qi的所有素数因子都在B中。(xi > √N,这能确保xi2 >N,从而在对N进行取模运算时不是平凡的)。这里省略如何寻找{xi}的细节。有下面的等式:右侧是q的素因子
      在这里插入图片描述2. 将指数e进行mod2 得到全是0,1的矩阵:在这里插入图片描述因为l>k,需要将其化为一个方阵,因此,部分行叠加到某一行,使该行结果对2取模全为0,S是{qi}的子集,即我们想选取的相叠加的行,因为我们想叠加后每项的指数都为2的倍数,所以在这里插入图片描述在这里插入图片描述于是我们就得到了z的两个平方根,虽然不能保证这两个值为z的因式分解,但至少能通过启发式的方法期望这种情况发生的概率约为1/2(因为X有四个平方根〉

    计算离散对数的算法

    给定g ∈G且y ∈< g>,找到.c,使得gx=y。(< g>是由g生成的循环子群,{g0,g1,…} ∈G。若 < g>=G,则g是G群的一个生成元,且G是循环群。)这个回答x=loggy表示

    “ 小步大步” 算法

    在时间O(√q· ploylog(q))计算阶为q的群中的离散对数

    给定输入g和h ∈ < g>,其中< g>的阶为q。外,以大小为t=[√q]的间隔“标记”这个循环,也就是说,计算和记录[q/t]+1 =O(√q)个元素,这就是大步
    在这里插入图片描述
    易知 = gx位于某个间隔中 , 因此t个元素

    在这里插入图片描述
    中的某一个必然等于刚才标记出来的某个大步点(这就是小步),有h*gi=gkt,便可以得到log< g>y=kt-i (mod q),伪代码如下:在这里插入图片描述

    Pohlig-Hellman 算法

    当群的阶q的任何非平凡因子已经知道的情况下,Pohlig-Hellman算法可用来加速对离散对数的计算。前面曾经提到,任何元素g的阶(记为ord(g))是最小的正整数i使得gi = 1。需要下面的引理:
    在这里插入图片描述
    也会使用到通用的中国剩余定理,现在描述Pohlig-Hellman 的方法。给定g和y,希望找到一个x满足9x= y。令ord(g)=q,其因式分解为在这里插入图片描述
    在这里插入图片描述
    令gi=gq/qi,因此得到在k个 “更小的 ” 群中的离散对数问题的k个实例 ,每1个大小为
    ord (gi) = qi,于是就简化了,然后能够通过任何其他解决离散对数 问题的算法来解决产生的k个实例中的每一个

    由碰撞而产生的离散对数法

    小步大步算法的一个缺点是,它使用了大量的内存,因为它需要存储O(√q)点。我们可以利用离散对数问题和抗碰撞哈希之间的联系寻找冲突,获得一个使用恒定内存的算法

    索引演算方法

    索引演算方法能够以p的长度表示的亚指数时间内,解决循环群Z*p(p为素数)上的离散对数问题。类似于二次筛

    1. 令q=p-1,是Z的阶。固定小素数的集合B={P1,…;Pk}。在这个步骤中,发现l≥k个不同的非零值x1 ,…, xl ∈Z,满足gi=gxi mod p]是“小”的,以便gi能因子分解(比如使用试除法),并且gi的所有素数因子都在集合B中。xi为随机尝试出的,然后有gi的因式分解:
      在这里插入图片描述
      取离散对数,将其转换为线性方程:在这里插入图片描述
      其中x和e是已知的,logp是未知的

    2. 现在给定一个元素h,来计算 logh。找到一个数x∈Zq,满足条件g=[gx* h mod p]是“小”的,使得g能够进行因子分解并且g的所有素数因子都在集合B中。在这里插入图片描述
      其中x*和 {e*i}都是己知的,于1️⃣中式子联立,发现在l + 1(>k+1)个线性方程中包含了{logg pi}f=1和log9 y的k + 1个变量和 logg h一共k+1个变量,可以得到所期望的logh

    展开全文
  • 求解某些奇异椭圆曲线上的椭圆曲线离散对数问题
  • 为了解决离散对数问题,本文首先介绍一些近世代数的基本知识,之后介绍几类基于离散对数的加密体制,最后列出几道CTF中的相关赛题。 代数基本知识 群 定义: 设G是非空集合,若在G内定义一种代数运算⨀,且满足下列4...
  • 数学 有限域 c语言 密码学 Pollard pho算法
  • 一、离散对数问题 1.定义 设a=gx  mod  pa = g ^ x\;mod\;pa=gxmodp,记logg,  pa=xlog_{g,\;p} a = xlogg,p​a=x,称x为a的对数(以g为底,模p)。 给定p, g, a计算x称为离散对数问题。 2.应用之一:加密 若g,...
  • Pohlig-Hellman算法求解离散对数问题

    千次阅读 2021-02-12 10:11:33
    Pohig-Hellman算法求解离散对数问题 离散对数(DLP)问题: ax≡b(modp) a^{x} \equiv b \pmod{p} ax≡b(modp) ppp是大素数。 前面已经介绍了求解离散对数问题的小步大步算法(BSGS)(时间复杂度是O(p)O(\sqrt{p})O(p​)...
  • 离散对数问题,英文是Discrete logarithm Problem,有时候简写为Discrete log,该问题是十几个开放数学问题(Open Problems in Mathematics, [0.a], [0.b])中的一个。为什么要从离散对数问题说起?因为后面的内容中会...
  • 离散对数问题——指数演算法 离散对数(DLP)问题:设有群(G,⋅)(G,\cdot)(G,⋅),α∈G\alpha \in Gα∈G是一个nnn阶元素。给定β∈<α>\beta \in \left< \alpha \right>β∈⟨α⟩,找到指数a,0≤a≤...
  • 小步大步算法(BSGS)求解离散对数问题 众所周知,离散对数问题(Discrete Logarithm Problem,DLP)一直被认为是困难问题。离散对数问题可以是基于循环群的,也可以是基于椭圆曲线的,本篇以循环群上的离散对数问题为例...
  • 离散对数求解实验

    2020-10-11 20:34:20
    数据如下: p= 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 g= ...
  • sage之离散对数求解

    千次阅读 2020-06-19 11:07:20
    sage中求解离散对数我目前知道的三个函数:discrete_log(a,base,ord,operation),discrete_log_rho(a,base,ord,operation),discrete_log_lambda(a,base,bounds,operation);这三个函数分别是通用的求离散对数的方法...
  • 前言 前几天参加了网鼎杯的比赛,第一道题就是简单粗暴的离散对数问题(DLP)。当时自己是用sagemath的discrete_log()函数的直接秒解的(另外第三题必须要用cmd打开flag才出来就很坑)。赛后发现这道离散对数题应该...
  • baby step giant step简称为大步小步算法,是一个用来求解离散对数的方法,设a的b次对m取模得b,a与m互质时我们令x=At-B,a的At次等于b*a的B次,之后先对右边的数进行存储,,哈希map速度快一点,之后再从左边找,有...
  • 本周的任务是写一个程序来计算模素数p的离散对数。 二.解题思路 根据实验文档中提供的思路,令B=q=220B=\sqrt{q}=2^{20}B=q​=220,x=x0B+x1x=x_0B+x_1x=x0​B+x1​,其中x0,x1∈[0,B)x_0,x_1\in[0,B)x0​,x1​∈[0,B...
  • 离散对数及其拓展 离散对数是在群Zp∗Z_{p}^{*}Zp∗​而言的,其中ppp是素数。即在在群Zp∗Z_{p}^{*}Zp∗​内,aaa是生成元,求关于xxx的方程ax=ba^x=bax=b的解,并将解记作x=logabx=log_{a}{b}x=loga​b,离散对数指...
  • 包括狭义的离散对数问题,和椭圆曲线上的点的数乘的逆运算,都算广义离散对数问题,他们的求解方案都差不多。 为了能够用统一的语言来描述,我们首先考虑,如何把广义离散对数问题,规约成狭义离散对数问题。 二,...
  • 离散对数问题之 Pohlig-Hellman algorithm

    千次阅读 2019-05-18 23:16:00
    离散对数问题之 Pohlig-Hellman algorithmintroductionPohlig-Hellman Algorithm 从任意阶到素数幂阶Pohlig-Hellman Algorithm 从素数幂阶到素数阶 introduction 在解决非广义离散对数问题(DLP)gx=h&...
  • 离散对数和椭圆曲线加密原理

    万次阅读 多人点赞 2017-08-03 11:35:05
    现代公钥加密系统中,常用的加密算法除了RSA还有离散对数加密和椭圆曲线加密。这两者原理比较相似,在这里一并介绍。 离散对数问题 我们在中学里学的对数问题是指, 给定正实数aaa和axaxa^x,求xxx。也就是...
  • 摘 要:提出了一种基于离散对数型的有序多重签名方案,该方案无需增设第三方信任机构,减少了通信和计算工作量。同时他的安全性基于求解离散对数难题,因此是一种安全有效的有序多重签名方案。关键词:多重签名;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,679
精华内容 11,871
关键字:

离散对数