6MPik68W

1#include <boost/multiprecision/cpp_int.hpp>
2#include <boost/random.hpp>
3#include <iostream>
4
5using namespace boost::multiprecision;
6namespace mp = boost::multiprecision;
7
8
9struct OpenKey {
10    cpp_int p; // usually 1024 bits (prime!)
11    cpp_int q; // usually 160 bits; (p - 1) % q == 0
12    // w < q
13    cpp_int g; // (g^q) % p == 1
14    cpp_int y; // y = g^(-w) % p
15};
16
17struct SecretKey {
18    cpp_int w;
19};
20
21
22auto init_int_distribution(const OpenKey &open_key) {
23    return boost::random::uniform_int_distribution<cpp_int>(0, open_key.q);
24}
25
26
27cpp_int pre_signing(const OpenKey &open_key, const cpp_int &rand_power) {
28    return mp::powm(open_key.g, rand_power, open_key.p);
29}
30
31
32template<typename T>
33auto init_int_distribution(T bits_count) {
34    // multiprecision do not allow cpp_int as exponent, because https://stackoverflow.com/a/43508036
35    const cpp_int &base = 2;
36
37    return boost::random::uniform_int_distribution<cpp_int>(0, mp::pow(base, bits_count) - 1);
38}
39
40cpp_int sign(const OpenKey &open_key, const SecretKey &secret_key, const cpp_int &r, const cpp_int &e) {
41    return (r + e * secret_key.w) % open_key.q;
42}
43
44
45bool check_sign(const OpenKey &open_key, const cpp_int &e, const cpp_int &x, const cpp_int &s) {
46    // I spend 3 hours to force this code to compile.
47    // A bug in Boost forces an expression to be split into multiple parts
48    // For details, see https://t.me/supapro/757592
49    cpp_int p1 = mp::powm(open_key.g, s, open_key.p);
50    cpp_int p2 = mp::powm(open_key.y, e, open_key.p);
51    cpp_int p3 = p1 * p2;
52    cpp_int maybe_x = p3 % open_key.p;
53
54    return maybe_x == x;
55}
56
57
58bool singing(const OpenKey &open_key, const SecretKey &secret_key, int bit_count) {
59    // Note: Alice has secret key
60    using namespace boost::multiprecision;
61
62    boost::random::mt19937 mt;
63
64    auto r_int_dist = init_int_distribution(open_key);
65    cpp_int r = r_int_dist(mt);
66    cpp_int x = pre_signing(open_key, r);
67    
68    auto e_int_dist = init_int_distribution(bit_count);
69    cpp_int e = e_int_dist(mt);
70
71    cpp_int s = sign(open_key, secret_key, r, e);
72    return check_sign(open_key, e, x, s);
73}
74
75
76int main() {
77    using namespace std;
78
79    OpenKey open_key{48731, 443, 11444, 7355};
80    SecretKey secret_key{357};
81
82    cout << singing(open_key, secret_key, 72) << endl;
83    return 0;
84}