无标签

log

发布日期: 2021-10-17

Record（4）

1、ElGamal 加密

1、生成随机大素数

进度：完成

常用办法：伪素数生成，Miller Rabin素性检测
参考文章：
Miller-Rabin素数测试算法
 Elgamal 加密算法
 快速幂取模算法

实现：

int Pseudo_prime()//生成伪素数
{
    bool ifprime = false;
    int Pprime;
    int arr[50];
    for (int i = 0; i < 50; i++)
        arr[i] = i + 3;
    while (!ifprime)
    {
        ifprime = true;
        unsigned int TIME = (unsigned)time(0);
        srand(TIME+=100);
        Pprime = (rand() % 100) * 2 + 1;//生成大奇数
        for (int i = 0; i < 50; i++)
        {
            if (Pprime % arr[i] == 0)
            {
                ifprime = false;
                break;
            }
        }
    }
    return Pprime;
}

bool MillerRabin(int x)//素性检测
{
    int Prime[10] = { 2,3,5,7,11,13,17,19,23,29 };
    int s = 0, t = x - 1;
    int b;
    while (!(t&1))
    {
        s++;
        t >>= 1;
    }
    for (int i = 0; i < 10 && Prime[i] < x; ++i)      //随便选一个素数进行测试 
    {
        int a = Prime[i];
        int b = pow_mod(a, t, x);      //先算出a^t
        int k;
        for (int j = 1; j <= s; ++j)    //然后进行s次平方 
        {
            k = pow_mod(b, 2, x);   //求b的平方 
            if (k == 1 && b != 1 && b != x - 1)     //用二次探测判断 
                return false;
            b = k;
        }
        if (b != 1)  return false;   //用费马小定律判断 
    }

    return true;
}

2、快速幂、快速幂取模

原理：快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
时间复杂度：O(log₂N)
参考：
算法学习笔记(4)：快速幂
 快速积&快速幂的计算方法

实现：

long long qpow(long long a, long long b)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

int pow_mod(int g, int x, int p)//快速幂取模
{
    int ans = 1;    //记录结果
    int tmp = g % p;    //预处理，使得a处于c的数据范围之下
    while (x)
    {
        if (x & 1)    //奇数
            ans = ans * tmp % p;    //消除指数为奇数的影响
        x >>= 1;    //二进制的移位操作,不断的遍历b的二进制位
        tmp = tmp * tmp % p;    //不断的加倍
    }
    return ans;
}

3、扩展欧几里得算法

用途：求解**ax + by = gcd(a,b)**、计算模反元素元素

实现：

int e_gcd(int a, int b, int& x, int& y)//扩展欧几里得算法
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int item = e_gcd(b, a % b, y, x);
    y -= a / b * x;
    return item;
}

4、最后实现

代码实现由自己完成

#include <iostream>
#include <time.h>
using namespace std;

long long qpow(long long a, long long b)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

int pow_mod(int g, int x, int p)//快速幂取模
{
    int ans = 1;    //记录结果
    int tmp = g % p;    //预处理，使得a处于c的数据范围之下
    while (x)
    {
        if (x & 1)    //奇数
            ans = ans * tmp % p;    //消除指数为奇数的影响
        x >>= 1;    //二进制的移位操作,不断的遍历b的二进制位
        tmp = tmp * tmp % p;    //不断的加倍
    }
    return ans;
}

long long pow_mod_1(long long g, long long x, long long p)//快速幂取模
{
    long long ans = 1;    //记录结果
    long long tmp = g % p;    //预处理，使得a处于c的数据范围之下
    while (x)
    {
        if (x & 1)    //奇数
            ans = ans * tmp % p;    //消除指数为奇数的影响
        x >>= 1;    //二进制的移位操作,不断的遍历b的二进制位
        tmp = tmp * tmp % p;    //不断的加倍
    }
    return ans;
}

int e_gcd(int a, int b, int& x, int& y)//扩展欧几里得算法
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int item = e_gcd(b, a % b, y, x);
    y -= a / b * x;
    return item;
}

int Pseudo_prime()//生成伪素数
{
    bool ifprime = false;
    int Pprime;
    int arr[50];
    for (int i = 0; i < 50; i++)
        arr[i] = i + 3;
    while (!ifprime)
    {
        ifprime = true;
        unsigned int TIME = (unsigned)time(0);
        srand(TIME+=100);
        Pprime = (rand() % 100) * 2 + 1;//生成大奇数
        for (int i = 0; i < 50; i++)
        {
            if (Pprime % arr[i] == 0)
            {
                ifprime = false;
                break;
            }
        }
    }
    return Pprime;
}

bool MillerRabin(int x)//素性检测
{
    int Prime[10] = { 2,3,5,7,11,13,17,19,23,29 };
    int s = 0, t = x - 1;
    int b;
    while (!(t&1))
    {
        s++;
        t >>= 1;
    }
    for (int i = 0; i < 10 && Prime[i] < x; ++i)      //随便选一个素数进行测试 
    {
        int a = Prime[i];
        int b = pow_mod(a, t, x);      //先算出a^t
        int k;
        for (int j = 1; j <= s; ++j)    //然后进行s次平方 
        {
            k = pow_mod(b, 2, x);   //求b的平方 
            if (k == 1 && b != 1 && b != x - 1)     //用二次探测判断 
                return false;
            b = k;
        }
        if (b != 1)  return false;   //用费马小定律判断 
    }

    return true;
}

void Crea_Key(int& p, int& g, int& x, int& y)
{
    while (true)
    {
        p = Pseudo_prime();
        if (MillerRabin(p))
            break;
    }
    srand((unsigned)time(0));
    x = (rand() % p - 3) + 1;
    y = pow_mod(g, x, p);
}


void Encrypt(int& m, int& c1, int& c2, int& p, int& g, int& y)
{
    srand((unsigned)time(0));
    int k = (rand() % p - 3) + 1;
    c1 = pow_mod(g, k, p);
    c2 = m * pow_mod(y, k, p) % p;
}

int Decrypt(int& c1, int& c2, int& p, int& x)
{
    int item1, item2;
    e_gcd(c1, p, item1, item2);
    if (item1 < 0)
        item1 = (item1 % p) + p;
    return c2 * pow_mod(item1, x, p) % p;
}

int main()
{
    int x, y;//x为私钥，y为公钥
    int r, s;
    int m, c1, c2, p, g;
    srand((unsigned)time(0));
    g = (rand() % 20) + 1;//公共参数g
    Crea_Key(p, g, x, y);
    cout << "p=" << p << "  g=" << g << "  x=" << x << "  y=" << y << endl;
    cout << "请输入明文：";
    cin >> m ;
    Encrypt(m, c1, c2, p, g, y);
    cout << "密文（c1，c2）为：（" << c1 << "，" << c2 << "）"<< endl;
    m = Decrypt(c1, c2, p, x);
    cout << "解密结果为：" << m << endl;
    return 0;
}

5、主要技术难点

快速幂取模，伪素数生成，Miller-Rabin素性检测，扩展欧几里得算法

2、ElGamal 签名

进度：原理实现，签名后无法验签

参考：
ElGamal加密、签名算法笔记
 ELGAMAL公钥密码算法及ELGAMAL数字签名方案实现

实现：

代码实现由自己完成

void Sign(int& m, int& g, int& p, int& x, int& r, int& s)
{
    srand((unsigned)time(0));
    int k = rand() % 20 + 1;
    int item1, item2;
    r = pow_mod(g, k, p);
    e_gcd(k, p - 1, item1, item2);
    if (item1 < 0)
        item1 = (item1 % (p - 1)) + (p - 1);
    s = (m - x * r) * item1 % (p - 1);
}

void Verify(int& p, int& g, int& y, int& r, int& s, int& m)
{
    long long item2;
    int item1 = pow_mod(g, m, p);
    int item3 = pow_mod(y, r, p);
    if (s < 0)
    {
        int a, b;
        s = -s;
        item2 = qpow(r, s);
        e_gcd(item2, p, a, b);
        if (a < 0)
            a = (a % p) + p;
        item2 = a;
    }
    else
        item2 = pow_mod(r, s, p);
    int item4 = item2 * item3 % p;
    cout << item1 << "  " << item2 << "  " << item3 << "  " << item4 << endl;
}

3、RSA加密

进度：已完成

常用办法：伪素数生成，Miller Rabin素性检测，扩展欧几里德算法
参考文章：
RSA算法原理（一）

RSA算法原理（二）

扩展欧几里德算法详解

数论之拓展欧几里得

实现：
代码实现由自己完成

#include <iostream>
#include <time.h>
using namespace std;

unsigned int TIME = (unsigned)time(0);

int pow_mod(int g, int x, int p)//快速幂取模
{
    long long ans = 1;    //记录结果
    long long tmp = g % p;    //预处理，使得a处于c的数据范围之下
    while (x)
    {
        if (x & 1)    //奇数
            ans = ans * tmp % p;    //消除指数为奇数的影响
        x >>= 1;    //二进制的移位操作,不断的遍历b的二进制位
        tmp = tmp * tmp % p;    //不断的加倍
    }
    return ans;
}

int e_gcd(int a, int b, int& x, int& y) 
{
    if (!b) 
    {
        x = 1; y = 0;
        return a;
    }
    int gcd = e_gcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

int Pseudo_prime()//生成伪素数
{
    bool ifprime = false;
    int Pprime;
    int arr[50];
    for (int i = 0; i < 50; i++)
        arr[i] = i + 3;
    
    while (!ifprime)
    {
        ifprime = true;
        srand(TIME += 1000);
        Pprime = (rand() % 10000) * 2 + 1;//生成大奇数
        for (int i = 0; i < 50; i++)
        {
            if (Pprime % arr[i] == 0)
            {
                ifprime = false;
                break;
            }
        }
    }
    return Pprime;
}

bool MillerRabin(int x)//素性检测
{
    int Prime[10] = { 2,3,5,7,11,13,17,19,23,29 };
    int s = 0, t = x - 1;
    while (!(t & 1))
    {
        s++;
        t >>= 1;
    }
    for (int i = 0; i < 10 && Prime[i] < x; ++i)      //随便选一个素数进行测试 
    {
        int a = Prime[i];
        int b = pow_mod(a, t, x);      //先算出a^t
        int k;
        for (int j = 1; j <= s; ++j)    //然后进行s次平方 
        {
            k = pow_mod(b, 2, x);   //求b的平方 
            if (k == 1 && b != 1 && b != x - 1)     //用二次探测判断 
                return false;
            b = k;
        }
        if (b != 1)  return false;   //用费马小定律判断 
    }
    return 1;
}

void Crea_Key(int& p, int& q, int& e, int& d)//密钥生成，公钥（e，n），私钥d
{
    int y, item;
    for (int i = 0; i < 2;)
    {
        item = Pseudo_prime();
        if (MillerRabin(item) && i == 0)
        {
            p = item;
            i++;
        }
        else if (MillerRabin(item) && i == 1)
        {
            q = item;
            i++;
        }
    }
    int n = p * q;
    int Phi = (p - 1) * (q - 1);
    srand(TIME);
    while (true)
    {
        e = rand() % Phi;
        if (e_gcd(e, Phi, d, y) == 1 && d > 0)
            break;
    }
    //cout << "p=" << p << "  q=" << q << "  n=" << n << endl;
    //cout << "e=" << e << "  d=" << d << "  Phi=" << Phi << "  y=" << y << endl;
}

int Encrypt(int& m, int& e, int n)
{
    return pow_mod(m, e, n);
}

int Decrypt(int& c, int d, int n)
{
    return pow_mod(c, d, n);
}

int main()
{
    int p, q, e, d, n;
    int m, c, x, y, item1, item2;
    Crea_Key(p, q, e, d);
    n = p * q;
    cout << "请输入0~" << n << "的明文：";
    cin >> m;
    
    c = Encrypt(m, e, n);
    cout << "加密后的密文为c=" << c << endl;
    item1 = Decrypt(c, d, n);
    cout << "解密后的明文为m=" << item1 << endl;

    return 0;
}

4、RSA签名

参考：
RSA签名和验签
 RSA加密、解密、签名、验签的原理及方法

实现：

代码实现由自己完成

int Sign(int& x, int& d, int n)
{
    return pow_mod(x, d, n);
}

int Verify(int& y, int& e, int n)
{
    return pow_mod(y, e, n);
}

5、Paillier加密

进度：已完成

参考：
Paillier同态加密的介绍以及c++实现

原理：

实现：
代码实现由自己完成

#include <iostream>
#include <time.h>
using namespace std;

unsigned int TIME = unsigned(time(nullptr));

int pow_mod(int g, int x, int p)//快速幂取模
{
    int ans = 1;    //记录结果
    int tmp = g % p;    //预处理，使得a处于c的数据范围之下
    while (x)
    {
        if (x & 1)    //奇数
            ans = ans * tmp % p;    //消除指数为奇数的影响
        x >>= 1;    //二进制的移位操作,不断的遍历b的二进制位
        tmp = tmp * tmp % p;    //不断的加倍
    }
    return ans;
}

long long pow_mod_1(long long g, long long x, long long p)//快速幂取模
{
    long long ans = 1;    //记录结果
    long long tmp = g % p;    //预处理，使得a处于c的数据范围之下
    while (x)
    {
        if (x & 1)    //奇数
            ans = ans * tmp % p;    //消除指数为奇数的影响
        x >>= 1;    //二进制的移位操作,不断的遍历b的二进制位
        tmp = tmp * tmp % p;    //不断的加倍
    }
    return ans;
}

int L(long long x,long long n)
{
    return (x - 1) / n;
}

int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    return gcd(b, a % b);
}

int e_gcd(int a, int b, int& x, int& y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int item = e_gcd(b, a % b, y, x);
    y -= a / b * x;
    return item;
}

int Pseudo_prime()//生成伪素数
{
    bool ifprime = false;
    int Pprime;
    int arr[50];
    for (int i = 0; i < 50; i++)
        arr[i] = i + 3;

    while (!ifprime)
    {
        ifprime = true;
        srand(TIME += 100);
        Pprime = rand() % 100 * 2 + 1;//生成大奇数
        for (int i = 0; i < 50; i++)
        {
            if (Pprime % arr[i] == 0)
            {
                ifprime = false;
                break;
            }
        }
    }
    return Pprime;
}

bool MillerRabin(int x)//素性检测
{
    int Prime[10] = { 2,3,5,7,11,13,17,19,23,29 };
    int s = 0, t = x - 1;
    while (!(t & 1))
    {
        s++;
        t >>= 1;
    }
    for (int i = 0; i < 10 && Prime[i] < x; ++i)      //随便选一个素数进行测试 
    {
        int a = Prime[i];
        int b = pow_mod(a, t, x);      //先算出a^t
        int k;
        for (int j = 1; j <= s; ++j)    //然后进行s次平方 
        {
            k = pow_mod(b, 2, x);   //求b的平方 
            if (k == 1 && b != 1 && b != x - 1)     //用二次探测判断 
                return false;
            b = k;
        }
        if (b != 1)  return false;   //用费马小定律判断 
    }
    return true;
}

void Crea_Key(int& p, int& q, long long& g, int& Lam)//密钥生成，公钥（n，g），私钥Lam
{
    int item1, item2;
    while(true)
    {
        item1 = Pseudo_prime();
        item2 = Pseudo_prime();
        if (MillerRabin(item1) && MillerRabin(item2) && gcd(item1 * item2, (item1 - 1) * (item2 - 1)) == 1)
        {
            p = item1;
            q = item2;
            break;
        }
    }
    long long n = p * q;
    Lam = (p - 1) * (q - 1) / gcd((p - 1), (q - 1));
    cout << "p=" << p << "  q=" << q << "  n=" << n << "  Lam=" << Lam;

    srand(TIME);
    for (g = n + 1;; g++)
    {
        if (gcd(L(pow_mod_1(g, Lam, n * n), n), n) == 1)
            break;
    }
    cout << "   g=" << g << endl;
}

long long Encrypt(int& m, long long n, long long& g)//加密
{
    int r;
    long long item, item1, item2;
    srand(TIME);
    r = rand() % n;
    item1 = pow_mod_1(g, m, n * n);
    item2 = pow_mod_1(r, n, n * n);
    item = item1 * item2 % (n * n);
    return item;
}

int Decrypt(long long& c, long long n, int& Lam, long long& g)//解密
{
    int item1, item2, item3, item4;//item3为item2模n的逆，item4为丢弃值
    item1 = L(pow_mod_1(c, Lam, n * n), n);
    item2 = L(pow_mod_1(g, Lam, n * n), n);
    e_gcd(n, item2, item4, item3);
    if (item3 < 0)
        item3 = (item3 % n) + n;
    return item1 * item3 % n;
}

int main()
{
    int p, q, Lam, m;
    long long c, g, n;
    Crea_Key(p, q, g, Lam);
    n = p * q;
    cout << "请输入0~" << p * q << "的明文：";
    cin >> m;

    c = Encrypt(m, n, g);
    cout << "加密后的密文为c=" << c << endl;
    m = Decrypt(c, n, Lam, g);
    cout << "解密后的明文为m=" << m << endl;

    return 0;
}

6、其他

Cramer-Shoup 加密、BLS短签名、ZSS短签名、BB短签名：原理已经理解，还没开始编写程序
参考：
Cramer-Shoup非对称公钥密码体制
 Cramer-Shoup 密码系统安全证明内容小结
 理解 BLS 签名算法
目前存在的问题：
1. 基于身份的加密体制原理还不太理解
2. 哈希函数原理理解，但不知道如何代码实现
3. 对于曲线哈希和曲线配对的理解还存在问题

Daniel

https://eatingcrime.github.io/2021/10/17/Record%EF%BC%884%EF%BC%89/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Daniel !

无标签

常见Dos攻击

2022-06-16 log

Record（3）

2021-09-24 log