Rabin数字签名 Lamport 一次签名

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/49720821

Rabin数字签名 代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<random>

using namespace std;

const int S = 10;

long long mult_mod(long long a, long long b, long long c)
{
    a %= c;
    b %= c;
    long long ret = 0;
    while (b)
    {
        if (b & 1) { ret += a; ret %= c; }
        a <<= 1;
        if (a >= c)a %= c;
        b >>= 1;
    }
    return ret;
}

//计算 ret =  x^n %c
long long pow_mod(long long x, long long n, long long mod)//x^n%c
{
    if (n == 1)return x%mod;
    x %= mod;
    long long tmp = x;
    long long ret = 1;
    while (n)
    {
        if (n & 1) ret = mult_mod(ret, tmp, mod);
        tmp = mult_mod(tmp, tmp, mod);
        n >>= 1;
    }
    return ret;
}

bool check(long long a, long long n, long long x, long long t)
{
    long long ret = pow_mod(a, x, n);
    long long last = ret;
    for (int i = 1; i <= t; i++)
    {
        ret = mult_mod(ret, ret, n);
        if (ret == 1 && last != 1 && last != n - 1) return true;//合数
        last = ret;
    }
    if (ret != 1) return true;
    return false;
}

bool Miller_Rabin(long long n)//Miller_Rabin算法判断素数
{
    if (n<2)return false;
    if (n == 2)return true;
    if ((n & 1) == 0) return false;//偶数
    long long x = n - 1;
    long long t = 0;
    while ((x & 1) == 0) { x >>= 1; t++; }
    for (int i = 0; i<S; i++)
    {
        long long a = rand() % (n - 1) + 1;
        if (check(a, n, x, t))
            return false;//合数
    }
    return true;
}

long long gcd(long long a, long long b)
{
    if (a == 0)return 1;
    if (a<0) return gcd(-a, b);
    while (b)
    {
        long long t = a%b;
        a = b;
        b = t;
    }
    return a;
}

bool Legendre(int a, int p)
{
    int tmp = pow(a, (p - 1) / 2);
    if (tmp % p == 1)
        return true;
    else
        return false;
}

int main()
{
    cout << "*******************************************" << endl;
    cout << "测试数据假定 p = 7 q = 11 ，进行签名和验证" << endl;
    cout << "*******************************************" << endl << endl << endl;
    static uniform_int_distribution<unsigned> u(1000000, 1000000000);
    static default_random_engine e(time(0));
    long long p = 6, q = 6;

    //随机产生素数p q
    while (!Miller_Rabin(p))
        p = u(e);
    while (!Miller_Rabin(q))
        q = u(e);

    //cout << p << " " << q << endl;
    long long n = p*q;
    cout << "素数p,q生成完毕！" << endl;
    p = 7;
    q = 11;

    //签名生成
    cout << "请输入 m 进行签名:" << endl;
    long long m;
    cin >> m;

    if (!(Legendre(m, p) && Legendre(m, q)))
    {
        while (!(Legendre(m, p) && Legendre(m, q)))
            m = m - 1;
    }

    long long s = ((long long)sqrt(m)) % n; 

    //签名验证
    cout << "请输入s进行签名验证:" << endl;
    int ss;
    cin >> ss;
    if (m == ss*ss%n)
        cout << "true 验证成功！" << endl;
    else
        cout << "false 验证失败！" << endl;

    return 0;
}

Lamport 一次签名：

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <string>

using namespace std;

int quickpow(int m, int n, int k)
{
    int  b = 1;
    while (n > 0)
    {
        if (n & 1)
            b = (b*m) % k;
        n = n >> 1;
        m = (m*m) % k;
    }
    return b;
}

int main()
{
    int n, MOD;
    cin >> n >> MOD;

    int y10, y11, y20, y21, y30, y31;
    cin>>y10>>y11>>y20>>y21>>y30>>y31;

    int z10, z11, z20, z21, z30, z31;
    //
    z10 = quickpow(n, y10, MOD);
    z11 = quickpow(n, y11, MOD);
    z20 = quickpow(n, y20, MOD);
    z21 = quickpow(n, y21, MOD);
    z30 = quickpow(n, y30, MOD);
    z31 = quickpow(n, y31, MOD);
    //

    string cl;
    cin >> cl;
    int len = cl.size();
    int Sign[100];

    if (cl[0] == '0')
        Sign[0] = y30;
    else 
        Sign[0] = y31;
    if (cl[1] == '0')
        Sign[1] = y20;
    else
        Sign[1] = y21;
    if (cl[2] == '0')
        Sign[2] = y10;
    else
        Sign[2] = y11;


    int Sign_ans[100];

    for (int i = 0; i < 3; i++)
    {
        Sign_ans[i] = quickpow(n, Sign[2-i],MOD);
        cout << Sign_ans[i] << endl;
    }


    return 0;
}