密码学硬核笔记——特殊离散对数问题

前言

前几天参加了网鼎杯的比赛，第一道题就是简单粗暴的离散对数问题（DLP）。当时自己是用sagemath的discrete_log()函数的直接秒解的（另外第三题必须要用cmd打开flag才出来就很坑）。赛后发现这道离散对数题应该是用Pohlig–Hellman algorithm 做的，所以针对这次的题目学习了一遍该算法。

---

群

• 定义6.7：设$H$是群$G$的一个子集合，如果对于群$G$的二元运算，$H$也构成一个群，就称$H$为群$G$的子群，记作$H ≤ G$。
• 定义6.8： 若群$G$包含的元素个数有限，则称$G$为有限群，否则称为无限群。有限群$G$所包含的元素个数称为$G$的阶，记为$| G |$。
• 定义6.9 ：设$a$是群$G$中的一个元素，若存在正整数$n$使得$a^n = e$，则称$a$为有限阶元素，满足$a^n = e$的最小正整数$n$叫做$a$的阶，记为$| a |$。若不存在正整数$n$使得$a^n = e$，则称$a$为无限阶元素。
• 定义6.10 设$G$为群，若存在$G$的一个元素$a$，使得$G$中的任意元素均由$a$的幂组成，即
  $G = \{ a^n | n ∈ Z\}$
  则称群$G$为循环群，元素$a$为循环群$G$的生成元，记为$G = < a >$。

后面的内容都是围绕循环群的子群以及群和元素的阶展开的。

---

Pohlig–Hellman algorithm

维基百科解释如下：
是一种特殊算法，在阶为光滑数的有限阿贝尔群上解决离散对数问题。

同时

先看普遍情况下的算法：

大致流程如下：
(假设阶为$\phi(m)$)

首先，要解决的问题是
$g^x\equiv h \ mod\ m\ and\ n=\phi(m)=\prod_{i=1}^r p_i ^ {e_i}$

等式两边同乘上一个指数$\frac{n}{p_i ^ {e_i}}$，可以得到：
$\begin{cases} （g^{x_1})^\frac{n}{p_1 ^ {e_1}}\equiv h^\frac{n}{p_1 ^ {e_1}} \ mod\ m\\ （g^{x_2})^\frac{n}{p_2 ^ {e_2}}\equiv h^\frac{n}{p_2 ^ {e_2}} \ mod\ m\\ （g^{x_3})^\frac{n}{p_3 ^ {e_3}}\equiv h^\frac{n}{p_3 ^ {e_3}} \ mod\ m\\ ...\\ （g^{x_r})^\frac{n}{p_r ^ {e_r}}\equiv h^\frac{n}{p_r ^ {e_r}} \ mod\ m\\ \end{cases}$

对于每一条式子来说，通过遍历$x_i\in\{0,1,...,p_i ^ {e_i}\}$一定可以计算出一个$x_i$满足：$（g^{x_i})^\frac{n}{p_i ^ {e_i}}\equiv h^\frac{n}{p_i ^ {e_i}} \ mod\ m$

所以我们可以得到：

$\begin{cases} x\equiv x_1 \ \mod p_1 ^ {e_1}\\ x\equiv x_2 \ \mod p_2 ^ {e_2}\\ x\equiv x_3 \ \mod p_3 ^ {e_3}\\ ...\\ x\equiv x_r \ \mod p_r ^ {e_r}\\ \end{cases}$

最后用中国剩余定理可以算出最后的$x$：
$x \equiv x' \mod \prod_{i=1}^r p_i ^ {e_i}$

---

理论依据

（为什么能算出这个$x_i$?）

我们用群理论重新梳理一遍整个算法。

根据题目内容，我们可以构建生成元为$g$ ,阶为$\phi(m)$（用n表示），模$m$的有限循环群
群内元素为：
$G=\{1,g^1,g^2,...,g^n\}$
（这里先讲一下，循环群的阶与生成元的阶是一样的，暂且认为阶为$n$，因为根据欧拉定理 $g^{\phi(m)}\equiv1 \mod m$,即使存在元素的阶t小于$n$（即$g^{t}\equiv1 \mod m$)，那也是$n$的因子，可以通过遍历因子的方式得到$t$）

通过这个循环群我们可以知道$h$是在该群中的，而且$x\in\{0,1,..,n-1\}$

那为什么要乘上指数呢？
其实对每个式子乘上指数是为了构造多个不同的该循环群的子群。

令$g_i=g^\frac{n}{pi^{e_i}}$，可以构造一个以$g_i$为生成元,阶为$p_i^{e_i}$的循环群子群
元素为
$<g_i>=\{1,g^\frac{n}{pi^{e_i}},g^{\frac{n}{pi^{e_i}}*2},g^{\frac{n}{pi^{e_i}}*3},...,g^{\frac{n}{pi^{e_i}}*(p_i^{e_i}-1)}\}$

同时我们也构造$h_i=h^{\frac{n}{pi^{e_i}}}=(g^{x})^{\frac{n}{pi^{e_i}}} \mod m$（取模后$x$变成了$x_i$）
因此$h_i\in <g_i>$,$x_i$必定存在，我们可以通过遍历$x_i\in [0,p_i^{e_i}-1]$找到它。

同时我们要关注$g^x\equiv h \ mod\ m\rightarrow (g^{\frac{n}{p_i^{e_i}}})^{x_i}\equiv h^\frac{n}{p_i ^ {e_i}} \ mod\ m$
实际上是
$x\in[0,n-1]\rightarrow x_i\in [0,p_i^{e_i}-1]$
也就是说，每个等式计算出来的$x_i$是原来的$x$在不同模下的结果。所以我们才能用CRT把原来的$x$算出来。

---

特殊算法（当阶为素数幂prime power）：

其实就是普遍算法，为了美观代码简化了一点，差异不大。但可以与$BSGS$算法并用（其实我并不太清楚怎么并用）， 时间复杂度降为$O(e\sqrt{p})$。

---

实战演练

you_rise_me_up.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

离散对数问题，$n$为$2^{512}$,素数幂，可以使用Pohlig–Hellman algorithm。

首先找阶，因为生成元m的阶整除$\phi(n)$，所以我们可以通过遍历$2$的幂来找到这个阶。
遍历之后发现阶为$2^{510}$，直接使用上述特殊算法就可得到结果。

(自己写的辣鸡代码)

def Prime_power_Pohlig_Hellman(g,h,n,p,e):
    '''
    phi(n)=p^e
    g^(p^e)=1 mod n
    g^x=h mod n
    '''
    for a in range(e):
        if(pow(g,2**a,n)==1):
            break
    x_k=0
    e=a
    gm=pow(g,pow(p,e-1,n),n)
    print gm
    if(pow(g,p**e,n)!=1):
        print 'error'
    for k in range(e):
        _x=pow(p,e,n)-x_k
        if(pow(g,x_k,n)*pow(g,_x,n)%n !=1 ):
            print 'error'
        h_k=pow(pow(g,_x,n)*h,pow(p,e-1-k,n),n)
        for d_k in range(p):
            if(pow(gm,d_k,n)==h_k):
                print k,d_k
                break

        x_k=x_k+d_k*pow(p,k,n)
        
    return x_k  

if __name__ =='__main__':
    n=2**512
    m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
    c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
    print libnum.n2s(Prime_power_Pohlig_Hellman(m, c, 2**512, 2, 511) )   

最后得到

---

后记

这篇博客的内容是我第一次使用新学的群理论来分析（尽力了），可能有讲得不好的地方，请多多包涵。

个人体会有两个，一是其实算法并没有那么难看懂，英语也没有那么难读懂，莫名的恐惧只是因为不了解。所以多看几遍就好了。

二是我觉得了解算法就是一种说服自己的过程，这个算法为什么要这样做？理论依据又是什么？学习算法的过程中，我一直在寻找理由说服自己，这个算法这样做肯定是有它的理由的。可能有点吹毛求疵的感觉，但我只是想纯粹的去理解算法。

三是自己还有很大的进步空间。

转载：https://blog.csdn.net/jcbx_/article/details/106083612