c5QZYRkR

1// ------------------------------------------------
2// ------------------------------------------------
3// main.cpp
4// ------------------------------------------------
5#include <algorithm>
6#include <chrono>
7#include <cmath>
8#include <complex>
9#include <fstream>
10#include <initializer_list>
11#include <iomanip>
12#include <iostream>
13#include <limits.h>
14#include <queue>
15#include <regex>
16#include <sstream>
17#include <stdint.h>
18#include <thread>
19#include <vector>
20
21#include "MyRsa.h"
22
23int main()
24{
25MyRsa rsaObj;
26BigInteger_t p("1000000000039"), q("2000000000003"), e("65537");
27//BigInteger_t p("3"), q("7"), e("13");
28rsaObj.key(p,q,e);
29std::cout << "dump:\n" << rsaObj.dump() << "\n";
30
31BigInteger_t plain("666");
32std::cout << "plain = " << plain << "\n";
33BigInteger_t enc = rsaObj.enc(plain);
34std::cout << "enc = " << enc << "\n";
35BigInteger_t plain2 = rsaObj.dec(enc);
36std::cout << "plain2 = " << plain2 << "\n";
37
38}
39
40
41// ------------------------------------------------
42// ------------------------------------------------
43// MyRsa.h
44// ------------------------------------------------
45#ifndef VIvKKYveBVbaWbpXgyat
46#define VIvKKYveBVbaWbpXgyat 1
47
48#include <algorithm>
49#include <functional>
50#include <iostream>
51#include <map>
52#include <numeric>
53#include <stdexcept>
54#include <stdint.h>
55#include <string>
56#include <vector>
57#include <tuple>
58
59#include <boost/multiprecision/miller_rabin.hpp>
60#include <boost/multiprecision/cpp_int.hpp>
61
62using BigInteger_t = boost::multiprecision::cpp_int;
63
64class MyRsa
65{
66private:
67	struct PublicKey
68	{
69		// a multiprecision integer (MPI) of RSA public modulus n;
70		// an MPI of RSA public encryption exponent e.
71		BigInteger_t n, e;
72	} m_pubKey;
73
74	struct SecretKey
75	{
76		// multiprecision integer (MPI) of RSA secret exponent d;
77		// MPI of RSA secret prime value p;
78		// MPI of RSA secret prime value q.
79		BigInteger_t d, p, q;
80	} m_secKey;
81	// n = p*q
82	// e: gcd(n,e) == 1
83	// m = (p-1)*(q-1)
84	// d: d*e = 1 (mod m)
85	// Y = X**e mod n
86	// X = Y**d mod n
87
88public:
89	void key(const BigInteger_t& p, 
90			const BigInteger_t& q,
91			const BigInteger_t& e);
92	BigInteger_t enc(const BigInteger_t& X) const;
93	BigInteger_t dec(const BigInteger_t& Y) const;
94	std::string dump() const;
95	// Multiplicative inverse for a modulo m.
96	static BigInteger_t mulInv(const BigInteger_t& a, const BigInteger_t& m);
97private:
98};
99#endif
100
101// ------------------------------------------------
102// ------------------------------------------------
103// MyRsa.cpp
104// ------------------------------------------------
105#include "MyRsa.h"
106
107void MyRsa::key(const BigInteger_t& p, 
108			const BigInteger_t& q,
109			const BigInteger_t& e)
110{
111	m_secKey.p = boost::multiprecision::abs(p);
112	m_secKey.q = boost::multiprecision::abs(q);
113	const int millerAttempts = 25;
114	if(!boost::multiprecision::miller_rabin_test(m_secKey.p, millerAttempts)
115		|| !boost::multiprecision::miller_rabin_test(m_secKey.q, millerAttempts))
116		throw std::runtime_error("MyRsa::key: p and q are not prime");
117	
118	const BigInteger_t m = (m_secKey.p-1) * (m_secKey.q-1);
119	m_pubKey.n = m_secKey.p * m_secKey.q;
120	const BigInteger_t inv = mulInv(e, m);
121	if(inv == 0)
122		throw std::runtime_error("MyRsa::key: mulInv(m,e) == 0");
123	m_pubKey.e = e;
124	m_secKey.d = inv;
125}
126
127BigInteger_t MyRsa::enc(const BigInteger_t& m) const
128{
129	// c = m**e mod n
130	return boost::multiprecision::powm(m, m_pubKey.e, m_pubKey.n);
131}
132
133BigInteger_t MyRsa::dec(const BigInteger_t& c) const
134{
135	// m = c**d mod n
136	return boost::multiprecision::powm(c, m_secKey.d, m_pubKey.n);
137}
138
139std::string MyRsa::dump() const
140{
141	std::ostringstream os;
142	os << "PubKey n = " << m_pubKey.n << "\n";
143	os << "PubKey e = " << m_pubKey.e << "\n";
144	os << "SecKey d = " << m_secKey.d << "\n";
145	os << "SecKey p = " << m_secKey.p << "\n";
146	os << "SecKey q = " << m_secKey.q << "\n";
147	return os.str();
148}
149
150
151BigInteger_t MyRsa::mulInv(const BigInteger_t& a_, const BigInteger_t& m)
152{
153	// If a has a multiplicative inverse modulo m, this gcd must be 1.
154	// a*x+m*y = gcd(a,m) = 1
155	// a*x+m*y = 1, a*x-1=m*y.
156	// mod m: a*x-1=0 (mod m), a*x=1 (mod m), x = ..?
157	// Knuth, vol.2, Algorithm X (Extended Euclid's algorithm), p.342.
158	// u*u1 + v*u2 = u3 = gcd(u,v).
159	
160	if(m <= 0)
161		return 0;
162	BigInteger_t a = a_;
163	if(a < 0) a %= m;
164	if(a < 0) a += m; // residue can be less 0
165	BigInteger_t u1,u2,u3, v1,v2,v3, t1,t2,t3;
166
167	u1 = 1, u3 = a;
168	v1 = 0, v3 = m;
169	while(v3 != 0)
170	{
171		const BigInteger_t q = u3 / v3;
172		t1 = u1-v1*q, t3 = u3-v3*q;
173		u1 = v1, u3 = v3;
174		v1 = t1, v3 = t3;
175	}
176	if (u3 != 1)
177	{
178		return 0;	/* Error: No inverse exists */
179	}
180	if (u1 < 0)
181	{
182		u1 += m;
183	}
184	return u1;
185 }