-
Notifications
You must be signed in to change notification settings - Fork 2
/
RSA.cpp
210 lines (185 loc) · 5.49 KB
/
RSA.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
/* Copyright (C) 2016 Levi Barnes - All Rights Reserved
* You may use, distribute and modify this code under the
* terms of the Apache license, version 2.0, 2004.
*
* You should have received a copy of the Apache 2.0 license with
* this file. If not, please write to: levi.barnes@gmail.com.
*/
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <iostream>
#define MAX_STR_LEN 10000
long int prime(long int);
long int gcd(long int p, long int q);
int publickey(long int p, long int q, long int* exp, long int* mod);
int privatekey(long int p, long int q, long int pubexp, long int* exp, long int* mod);
int encrypt(long int* inmsg, long int, long int, long int* outmsg);
int decrypt(long int* inmsg, long int, long int, long int* outmsg);
int char2long(char* in, long int* out);
int long2char(long int* in, char* out);
int main(void) {
long int p,q, pube, pubmod, prive, privmod;
char inmsg[MAX_STR_LEN];
long int inmsg_l[MAX_STR_LEN];
char outmsg[MAX_STR_LEN];
long int outmsg_l[MAX_STR_LEN];
char decrmsg[MAX_STR_LEN];
long int decrmsg_l[MAX_STR_LEN];
//Get inputs
// - two prime numbers
// - a message to be encrypted
std::cout << "ENTER A PRIME NUMBER" << std::endl;
std::cin >> p;
if (prime(p))
{
std::cerr << p << " is not prime." << std::endl;
return 1;
}
std::cout << "ENTER ANOTHER PRIME NUMBER" << std::endl;
std::cin >> q;
if (prime(q))
{
std::cerr << q << " is not prime." << std::endl;
return 1;
}
std::cout << "ENTER A MESSAGE (up to MAX_STR_LEN characters)." << std::endl;
std::cin.ignore(INT_MAX,'\n');
std::cin.getline(inmsg, MAX_STR_LEN);
std:: cout << inmsg << std::endl;
//Generate public and private keys from p and q
publickey(p,q,&pube,&pubmod);
std::cout << "public key: " << pube << ", " << pubmod << std::endl;
privatekey(p,q,pube,&prive,&privmod);
std::cout << "private key: " << prive << ", " << privmod << std::endl;
//Encrypt, then decrypt the message
std::cout << "Original text: " << inmsg << std::endl;
//Convert to long ints
char2long(inmsg, inmsg_l);
//Encrypt
encrypt(inmsg_l, pube, pubmod, outmsg_l);
long2char(outmsg_l, outmsg);
std::cout << "Encrypted text: " << outmsg << std::endl;
//Decrypt
decrypt(outmsg_l, prive, privmod, decrmsg_l);
long2char(decrmsg_l, decrmsg);
std::cout << "Decrypted text: " << decrmsg << std::endl;
}
long int prime(long int p)
//returns zero for prime numbers
{
long int j = sqrt(p);
for (long int z=2;z<j;z++) if (0==p%z) return z;
return 0;
}
int publickey(long int p, long int q, long int *exp, long int *mod)
//Generates a public key pair
//The modulus is given by (p-1)*(q-1)
//The exponent is any integer coprime of the modulus
{
*mod = (p-1)*(q-1);
//Choose an integer near sqrt(mod)
*exp = (int)sqrt(*mod);
//Find a coprime near that number
while (1!=gcd(*exp,*mod))
{
(*exp)++;
}
*mod = p*q;
return 0;
}
int privatekey(long int p, long int q, long int pubexp, long int *exp, long int *mod)
//Generates a private key pair
//The modulus is given by (p-1)*(q-1)
//The exponent is the number, n, which satisfies (n * pubexp) % mod = 1
{
*mod = (p-1)*(q-1);
*exp = 1;
long int tmp=pubexp;
while(1!=tmp%*mod)
{
tmp+=pubexp;
tmp%=*mod; //We can exploit the fact that (a*b)%c = ((a%c)*b)%c
// to keep the numbers from getting too large
(*exp)++;
}
*mod = p*q;
return 0;
}
int encrypt(long int* in, long int exp, long int mod, long int* out)
//Encrypt an array of long ints
//exp and mod should be the public key pair
//Each number, c, is encrypted by
// c' = (c^exp)%mod
{
//Note: pc is a pointer
for (long int *pc = in; *pc != '\0';pc++,out++)
{
long int c = *pc;
for (int z=1;z<exp;z++)
{
c *= *pc;
c %= mod; //We can exploit the fact that (a*b)%c = ((a%c)*b)%c
// to keep the numbers from getting too large
}
*out = c;
}
*out='\0'; //Terminate with a zero
return 0;
}
int decrypt(long int* in, long int exp, long int mod, long int* out)
//Decrypt an array of long ints
//exp and mod should be the private key pair
//Each number, c', is decrypted by
// c = (c'^exp)%mod
{
for (long int *pc = in; *pc != '\0';pc++,out++)
{
long int c = *pc;
for (int z=1;z<exp;z++)
{
c *= *pc;
c %= mod; //We can exploit the fact that (a*b)%c = ((a%c)*b)%c
// to keep the numbers from getting too large
}
*out = c;
}
*out='\0'; //Terminate with a zero
return 0;
}
long int gcd(long int p, long int q)
//greatest common devisor (AKA greatest common factor)
// by Euclid's method
{
if (p<q) {long int tmp=p;p=q;q=tmp;}
while (q!=0)
{
//In each step the new p is the old q and the new q is p%q
// p <- q
// q <- p%q
//The last modular remainder will be 0.
//The next to last modular remainder is the GCD.
long int tmp = q;
q = p%q;
p = tmp;
}
return p;
}
int long2char(long int* in, char* out)
//Converts a list of long ints to char
//Using automatic type conversion
//Useful for outputting to stdout
{
while(*in != 0) *out++ = (char)(*in++);
*out = '\0';
return 0;
}
int char2long(char* in, long int* out)
//Converts a list of chars to long ints
//Using automatic type conversion
//Useful for converting input from stdin
{
while(*in != '\0') *out++ = (long int)(*in++);
*out = 0;
return 0;
}