ElGamal数字签名？

Question

【问题描述】

在实际生活和工作中，许多事物的处理需要当事人的签名。尤其在现代通信中，签名更是起到了认证、核准、有效和负责等功效。数字签名是现代密码学的一个重要组成部分，自从Diffie和Hellman于1976年首次提出数字签名以来，数字签名就在学术界和计算机网络界得到了迅猛的发展。著名的公钥算法，椭圆曲线体制，在数字签名中都有一定的应用。ElGamal就是一种原理简单，应用广泛的数字签名方法，它的成功很大程度上取决于求解离散对数问题的困难。ElGamal的密钥和参数的产生过程如下： 它先选定一个足够大的素数P， 然后在比P小的正数中选取一个随机数g和随机数x， 并且计算出y=gx(mod P) 。然后，{y,g,P}作为公钥，而x则作为保密认证的私钥。如果你想获取他人的私人信息，那么，你就必须在已知 {y,g,P} 的情况下计算出x(当然，如果要获得明文，还必须攻破或获取签名时使用的Hash函数)。本题的任务并不复杂，它只需要你对于已知的三元组{y,g,P}，设法计算出签名验证的时候用户使用的私钥。

【要求】

【数据输入】本题有多组输入数据，你必须处理到EOF为止

输入数据有三个整数: P, g, y (2 <= P < 231)

【数据输出】输出仅仅一个数字x ,使得0<x<P并且 y=gx ( mod P) 。如果你认为不存在这样的x那么请输出 ERROR。如果存在多个可能的密钥，请输出最小的一个。

【样例输入】

7 5 3

5 1 4

【样例输出】

5

ERROR

Answer 1

由题目要求，要求求解出x，使得y=g^x （mod P），那么可以枚举x的值，对于每一个x的值，计算出g^x （mod P）的值，并与y进行比较，如果相等，则说明x是正确的答案。代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll P, g, y;

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

int main() {
    while(cin >> P >> g >> y) {
        bool flag = false;
        for(int i = 0; i < P; i++) {
            if(qpow(g, i, P) == y) {
                cout << i << endl;
                flag = true;
                break;
            }
        }
        if(!flag) cout << "ERROR" << endl;
    }
    return 0;
}