Sherwood算法求解离散对数问题

﹏ヽ暗。殇╰゛Y 2022-12-13 12:45 114阅读 0赞

一、离散对数问题  
1.定义  
设 a = g x    m o d    p a = g ^ x\\;mod\\;p a=gxmodp，记 l o g g ,    p a = x log\_\{g,\\;p\} a = x logg,pa=x，称x为a的对数(以g为底，模p)。  
给定p, g, a计算x称为**离散对数问题**。  
2.应用之一：加密  
若g，p已知，x为私钥，求a公钥很容易，即解密；  
若g，p已知，a为公钥，求x公钥很困难(p是很大的质数更难)，即破解困难(下文将描述)；

二、简单算法  
根据费马小定理( a p − 1    m o d    p = 1 a^\{p - 1\}\\;mod\\;p = 1 ap−1modp=1，p是质数，整数a不是p的倍数)， x = 0 x = 0 x=0 和  x = p − 1 x = p - 1 x=p−1计算 g x    m o d    p g ^ x\\;mod\\;p gxmodp重复，最坏的情况下，x从0~p-2都不重复；所以，简单算法的思想就是遍历x，找到满足 a = g x    m o d    p a = g ^ x\\;mod\\;p a=gxmodp的x(一般a不取0，所以遍历x从1~p-1)。

代码如下：

#include <cstdio>
    
    int dlog(int g, int a, int p) {
        
        int x = 0, y = 1;
        do{
        
            x++;
            y *= g;
        }while((a != y % p) && (x != p));
        return x;
    }
    
    int main() {
        
        //测试
        int g = 2, a = 6, p = 19;
        int ans = dlog(g, a, p);
        if(ans == p) printf("无解");
        else printf("x = %d", ans);
        return 0;
    }

分析：  
当a = 14时， x = 7；意味着尝试了7次；  
当a = 7时，x = 14；意味着尝试了14次；  
也就是说，执行时间与a的取值相关。

动机：用sherwood算法使得执行时间与a无关。

三、sherwood算法  
1.一般算法f(x)改造成Sherwood算法：

RH(x) {
        
         // 用Sherwood算法计算f(x)
         n ← length[x];             // x的size为n
         r ← uniform(An);           // 随机取一元素
         y ← u(x, r);                 //将原实例x转化为随机实例y
         s ← f(y);                  // 用确定算法求y的解s
         return v(r, s);                 // 将s的解变换为x的解
    }

> Sherwood算法的核是找到u，v方法  
> 这个伪码看不明白，看下面实例

2.计算离散对数的改造思路  
(1)构造 :  y = l o g g ,    p c y=log\_\{g,\\;p\}c y=logg,pc  
其中，  
 c = b ⋅ a    m o d    p c = b·a \\;mod\\; p c=b⋅amodp ( b = g r    m o d    p b = g^r\\;mod\\;p b=grmodp)  
r对应于uniform(An)，实际是从0~p-2中随机选一个数。

l o g g ,    p b = r log\_\{g,\\;p\} b = r logg,pb=r  
 l o g g ,    p a = x log\_\{g,\\;p\} a = x logg,pa=x

(2)推导过程  
 y = l o g g ,    p c = l o g g ,    p ( b ⋅ a    m o d    p ) = ( l o g g ,    p b + l o g g ,    p a )    m o d   ( p − 1 ) = ( r + x )    m o d    ( p − 1 ) y =log\_\{g,\\;p\} c=log\_\{g,\\;p\}(b·a\\;mod\\;p)=(log\_\{g,\\;p\} b + log\_\{g,\\;p\} a)\\;mod\\:(p - 1)=(r+x)\\;mod\\;(p-1) y=logg,pc=logg,p(b⋅amodp)=(logg,pb\+logg,pa)mod(p−1)=(r\+x)mod(p−1)

> 推导依据的定理  
>  l o g g ,    p ( s ⋅ t    m o d    p ) = ( l o g g ,    p s + l o g g ,    p t )    m o d   ( p − 1 ) log\_\{g,\\;p\}(s·t\\;mod\\;p)=(log\_\{g,\\;p\} s + log\_\{g,\\;p\} t)\\;mod\\:(p - 1) logg,p(s⋅tmodp)=(logg,ps\+logg,pt)mod(p−1)

总结：  
 y = ( r + x )    m o d    ( p − 1 ) y=(r+x)\\;mod\\;(p-1) y=(r\+x)mod(p−1)，得 x = ( y − r )    m o d    ( p − 1 ) x = (y - r) \\;mod \\;(p - 1) x=(y−r)mod(p−1)

> 推导过程：  
>  r + x = k ⋅ ( p − 1 ) + y ( k 为 一 常 系 数 ) r + x = k·(p-1) + y (k为一常系数) r\+x=k⋅(p−1)\+y(k为一常系数)， x = k ⋅ ( p − 1 ) + y − r x = k·(p-1) + y - r x=k⋅(p−1)\+y−r, 故 x = ( y − r )    m o d    p x = (y-r)\\;mod\\;p x=(y−r)modp

上述提到的：  
u指的便是，把求x转化为求y，即 y = g c    m o d    p y=g^c\\;mod\\;p y=gcmodp， c = u ( x , r ) = b ⋅ a    m o d    p c = u(x, r)=b·a \\;mod\\; p c=u(x,r)=b⋅amodp  
v指的便是，已知y后求x，即 x = ( y − r )    m o d    ( p − 1 ) x = (y - r) \\;mod \\;(p - 1) x=(y−r)mod(p−1)

3.代码

#include <cstdio>
    #include <random>
    #include <ctime>
    
    int dlog(int g, int a, int p) {
        
        int x = 0, y = 1;
        do{
        
            x++;
            y *= g;
        }while((a != y % p) && (x != p));
        return x;
    }
    
    int uniform(int maxN) {
        
        return rand() % maxN;
    }
    
    int ModularExponent(int g, int r, int p) {
        
        long long sum = 1;
        for(int i = 1; i<= r; i++) sum *= g;
        return sum % p;
    }
    
    
    int dlogRH(int g, int a, int p) {
        
        int r = uniform(p - 1);
        int b = ModularExponent(g, r, p);
        int c = (b * a) % p;
        int y = dlog(g, c, p);  //这里y可能已经无解了；
        if(y == p) return -1;
        else return (y - r + p -1) % (p - 1);   //C++,y-r可能是负数，所以要加p - 1;
    }
    
    
    int main() {
        
        //测试
        srand((unsigned)time(NULL));
        int g = 2, a = 6, p = 19;
        printf("确定算法的结果：\n");
        int ans1 = dlog(g, a, p);
        if(ans1 == p) printf("无解\n");
        else printf("x = %d\n", ans1);
         printf("Sherwood算法的结果：\n");
        int ans2 = dlogRH(g, a, p);
        if(ans2 == -1) printf("无解\n");
        else printf("x = %d\n", ans2);
        return 0;
    }

4.结果  
①g = 2, a = 6, p = 19![在这里插入图片描述][20201011193943773.png_pic_center]  
②g = 2, a = 3, p = 7![在这里插入图片描述][20201011194815453.png_pic_center]

[20201011193943773.png_pic_center]: /images/20221123/7d7c3acf2d104d20ba36800a63e44ced.png
[20201011194815453.png_pic_center]: /images/20221123/339d8b7b5fef4b4795c906d635192bf7.png