跳转至

整数域上的离散对数

基本定义

在了解整数域上的离散对数时,我们先来了解几个基本定义

定义1

在群 G 中,g 为 G 的生成元,也就是说群 G 中每一个元素都可以写成 y=g^k,我们称 k 为 y 在群 G 中的对数。

定义2

m\geq 1,(a,m)=1,使得 a^d \equiv 1(\bmod m) 成立的最小正整数 d 称为 a 对模 m 的指数或者阶,我们一般将其记为 \delta_m(a)

定义3

\delta_m(a)=\varphi(m) 时,称 a 是模 m 的原根,简称 m 的原根。

一些性质

性质1

对于素数 p 来说,每一个与其互素的数都是它的原根。

性质2

使得 a^d \equiv 1(\bmod m) 成立的最小正整数 d ,必有d| \varphi(m)

性质3

模 m 存在原根的必要条件是 m=1,2,4,p^{\alpha},2p^{\alpha}

离散对数问题

如果 y=g^x \bmod p,那么已知 g,p,y,我们很难求得 x。但是当 p 具有一定的特性时就可能可以求解,比如,这个群的阶是一个光滑数。

正是上述这个问题构成了目前很大一部分现代密码学,包括密钥交换,ECC 等。

离散对数求解方式

暴力破解

给定 y=g^x \bmod p,我们可以暴力枚举 x 从而得到真正的 x 的值。

Baby-step giant-step

这一方法通常被称为小步大步法,这一方法使用了中间相遇攻击的思想。

我们可以令 x=im+j,其中 m= \lceil \sqrt n\rceil ,那么整数 i 和 j 都在 0 到 m 的范围内。

因此

y=g^x=g^{im+j}

也就是

y(g^{-m})^i=g^j

那么我们就可以枚举所有的 j 并进行计算,并将其存储到一个集合 S 中,然后我们再次枚举 i,计算 y(g^{-m})^i,一旦我们发现计算的结果在集合 S 中,则说明我们得到了一个碰撞,进而得到了 i 和 j。

这显然是一个时间与空间的折中的方式,我们将一个 O(n) 的时间复杂度,O(1) 空间复杂度的算法转换为了一个O(\sqrt n)的时间复杂度和O(\sqrt n) 的空间复杂度的算法。

其中

  • 每一次 j 的增加表示“baby-step”,一次乘上 g。
  • 每一次 i 的增加表示“giant-step”,一次乘上 g^{-m}

Pollard’s ρ algorithm

我们可以以O(\sqrt n)的时间复杂度和O(1) 的空间复杂度来解决上述问题。具体原理请自行谷歌。

Pollard’s kangaroo algorithm

如果我们知道 x 的范围为 a \leq x \leq b,那么我们可以以O(\sqrt {(b-a)}) 的时间复杂度解决上述问题。具体原理请自行谷歌。

The Pohlig-Hellman algorithm

不妨假设上述所提到的群的阶为 n, n 为一个光滑数,且n=\prod_{i=1}^r p_i^{e_i}

  1. 对于每个 $i \in {1,...,r} $
    1. 计算 g_i=g^{\frac{n}{p_i^{e_i}}}g_i 在模 m 中的阶为 p_i^{e_i},这个可以自行推导。
    2. 计算 y_i=y^{\frac{n}{p_i^{e_i}}}=g^{\frac{xn}{p_i^{e_i}}}=g_i^{x}=g_i^{x \bmod p_i^{e_i}} =g_i^{r_i}\bmod m,这里我们知道 y_i,m,g_i,而r_i 的范围为[0,p_i^{e_i}],由n 是一个光滑数,可知其范围较小,因此我们可以使用Pollard’s kangaroo algorithm 等方法快速求得r_i
  2. 根据上述的推导,我们可以得到对于 i \in \{1,...,r\}x \equiv r_i \bmod p_i^{e_i}
  3. 根据中国剩余定理可得,x \equiv ans \bmod n

我们可以将其作为用下图解释

Pohlig Hellman Algorithm

当然,原文中有一些优雅的做法,这里只是给出思想。

其复杂度为O(\sum\limits _i e_i(log_2 n+\sqrt p_i)),可以看出复杂度还是很低的。

如果m=2n+1,并且 n 是一个素数,那么复杂度就和原来的\sqrt m 几乎没有差别了。。

2018 国赛 crackme java

代码如下

import java.math.BigInteger;
import java.util.Random;

public class Test1 {
    static BigInteger two =new BigInteger("2");
    static BigInteger p = new BigInteger("11360738295177002998495384057893129964980131806509572927886675899422214174408333932150813939357279703161556767193621832795605708456628733877084015367497711");
    static BigInteger h= new BigInteger("7854998893567208831270627233155763658947405610938106998083991389307363085837028364154809577816577515021560985491707606165788274218742692875308216243966916");

    /*
     Alice write the below algorithm for encryption.
     The public key {p, h} is broadcasted to everyone.
    @param val: The plaintext to encrypt.
        We suppose val only contains lowercase letter {a-z} and numeric charactors, and is at most 256 charactors in length.
    */
    public static String pkEnc(String val){
        BigInteger[] ret = new BigInteger[2];
        BigInteger bVal=new BigInteger(val.toLowerCase(),36);
        BigInteger r =new BigInteger(new Random().nextInt()+"");
        ret[0]=two.modPow(r,p);
        ret[1]=h.modPow(r,p).multiply(bVal);
        return ret[0].toString(36)+"=="+ret[1].toString(36);
    }

    /* Alice write the below algorithm for decryption. x is her private key, which she will never let you know.
    public static String skDec(String val,BigInteger x){
        if(!val.contains("==")){
            return null;
        }
        else {
            BigInteger val0=new BigInteger(val.split("==")[0],36);
            BigInteger val1=new BigInteger(val.split("==")[1],36);
            BigInteger s=val0.modPow(x,p).modInverse(p);
            return val1.multiply(s).mod(p).toString(36);
        }
    }
   */

    public static void main(String[] args) throws Exception {
        System.out.println("You intercepted the following message, which is sent from Bob to Alice:");
        BigInteger bVal1=new BigInteger("a9hgrei38ez78hl2kkd6nvookaodyidgti7d9mbvctx3jjniezhlxs1b1xz9m0dzcexwiyhi4nhvazhhj8dwb91e7lbbxa4ieco",36);
    BigInteger bVal2=new BigInteger("2q17m8ajs7509yl9iy39g4znf08bw3b33vibipaa1xt5b8lcmgmk6i5w4830yd3fdqfbqaf82386z5odwssyo3t93y91xqd5jb0zbgvkb00fcmo53sa8eblgw6vahl80ykxeylpr4bpv32p7flvhdtwl4cxqzc",36);
    BigInteger r =new BigInteger(new Random().nextInt()+"");
    System.out.println(r);
        System.out.println(bVal1);
    System.out.println(bVal2);
    System.out.println("a9hgrei38ez78hl2kkd6nvookaodyidgti7d9mbvctx3jjniezhlxs1b1xz9m0dzcexwiyhi4nhvazhhj8dwb91e7lbbxa4ieco==2q17m8ajs7509yl9iy39g4znf08bw3b33vibipaa1xt5b8lcmgmk6i5w4830yd3fdqfbqaf82386z5odwssyo3t93y91xqd5jb0zbgvkb00fcmo53sa8eblgw6vahl80ykxeylpr4bpv32p7flvhdtwl4cxqzc");
        System.out.println("Please figure out the plaintext!");
    }
}

基本功能为计算

r_0=2^r \bmod p

r_1 =b*h^r \bmod p

可以发现,r 的范围为 [0,2^{32}],所以我们可以使用 BSGS 算法,如下

from sage.all import *

c1 = int(
    'a9hgrei38ez78hl2kkd6nvookaodyidgti7d9mbvctx3jjniezhlxs1b1xz9m0dzcexwiyhi4nhvazhhj8dwb91e7lbbxa4ieco',
    36
)
c2 = int(
    '2q17m8ajs7509yl9iy39g4znf08bw3b33vibipaa1xt5b8lcmgmk6i5w4830yd3fdqfbqaf82386z5odwssyo3t93y91xqd5jb0zbgvkb00fcmo53sa8eblgw6vahl80ykxeylpr4bpv32p7flvhdtwl4cxqzc',
    36
)
print c1, c2
p = 11360738295177002998495384057893129964980131806509572927886675899422214174408333932150813939357279703161556767193621832795605708456628733877084015367497711
h = 7854998893567208831270627233155763658947405610938106998083991389307363085837028364154809577816577515021560985491707606165788274218742692875308216243966916
# generate the group
const2 = 2
const2 = Mod(const2, p)
c1 = Mod(c1, p)
c2 = Mod(c2, p)
h = Mod(h, p)
print '2', bsgs(const2, c1, bounds=(1, 2 ^ 32))

r = 152351913

num = long(c2 / (h**r))
print num

参考


评论