打开 Math 未分类

密码学笔记

开一个密码学深坑。

V神告诉我看看深入浅出觅🐎学。

那就先看这本书还有刚买的CTF特训营中的觅🐎吧。

从零开始的Lord哥密码学历程

Pre Algorithm

BSGS（OI中的大步小步算法）

计算 a^x=b(mod p)
复杂度O(根号下P)

m=【根号p】
x=i*m-j
a^(i*m-j)=b(mod p)
a^(mi)=b*a^j(mod p)
枚举j 从 0-m
枚举i从1-m 找到满足上式的解。
x=i*m-j
#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
map<ll,int>mp;
ll p,a,b;
ll n,m,now,ans,t;
bool flag;
ll fast_pow(ll x)
{
    ll sum = 1;
    ll aa = a;
    while (x>0)
    {
        if (x&1) 
            sum = (sum*aa)%p;
        x = x>>1;
        aa = (aa*aa)%p;
    }
    return sum;
}
int main()
{
    while(scanf("%lld%lld%lld",&p,&a,&b)!=EOF)
    {
        if(a%p==0)
        {
            printf("no solution\n");
            continue;
        }
        mp.clear();
        m = ceil(sqrt(p));
        flag = false ;
        now = b%p;        //b*a^j 当j==0时 
        mp[now] = 0;
        for(int i=1;i<=m;++i)
        {
            now = (now*a)%p;
            mp[now] = i;
        }
        t = fast_pow(m);
        now = 1;
        for(int i=1;i<=m;++i)    //枚举 (a^m)^i
        {
            now = (now*t)%p;
            if(mp[now])
            {
                flag = true;
                ans = i*m-mp[now];
                printf("%lld\n",(ans%p+p)%p);    //printf("%lld\n",(ans%p+p)%p);
                break;
            }
        }
        if(!flag) printf("no solution\n");
    }
    return 0;
}

Polig-Hellman算法

同上计算离散对数问题
要求p-1的因子小。
p-1=p1^e1 * p2^e2 ~
0x2 Pohlig-Hellman算法
此算法应用于密码学中比bsgs算法更广，而且效果也更佳！（因为bsgs算法所能求解的p值不能太大，位数多了就不能在有限时间内跑完）

原理：

问题： 已知a,b,p,以及p-1的分解质因数，求x使得 ax=b(mod p)
设 p−1=pe11∗pe22...pekk
若能有 k 组可用的等式 x=xi (mod peii) ，就可以用中国剩余定理求解出 x(mod p−1)

b = mod(6,8101)
a = 7531
discrete_log(a,b)

Pollard's rho算法

因数分解。
在2-N-1 随机取 k 个x1....xk
判断是否村啊在gcd(xi-xj,N)!=1，若存在
gcd(xi-xy,N)就N因子一个
大约是N^1/4

Pollard's P-1算法

介绍Smooth与Powersmooth

一个证书得所有素因子不大于B，就是B-smooth数
720是 5-smooth
5^1\<3^2\<2^4=16 是个16-powersmooth

应用

若x=1(mod p) p为质数，可得
p|gcd(x-1,n)

这个算法的思想就是构造p-1，其有多个素因子，并且每个素因子的powersmooth不超过B，开始时随机选取一个x， 计算 xw mod n , w=∏primes q≤ B q⌊logqB⌋ ， 如果有gcd(xw−1,n) 不等于1， 那么我们就相当于找到一个素数p了

4.4 范例
If we want to factor the number n = 299.

We select B = 5.
Thus M=22×31×51.
We select a = 2.
g=gcd(aM−1,n)=13.
Since 1 < 13 < 299, thus return 13.
299 / 13 = 23 is prime, thus it is fully factored: 299 = 13 × 23.

推荐文章