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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
/* SI 335 Spring 2015
 * Project 2, RSA program
 * YOUR NAME HERE
 */
 
#include <unistd.h>
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <cstdlib>
 
#include "posint.hpp"
 
using namespace std;
 
// Prints a message on proper usage and exits with the given code
void usage (const char* progname, int ret);
 
// Function prototype. You have to fill in the implementation below.
void powmod (PosInt& result, const PosInt& a, const PosInt& b, const PosInt& n);
 
int main (int argc, char** argv) {
  // Detect if standard in is coming from a terminal
  bool interactive = isatty(fileno(stdin));
 
  // Seed the random number generator
  srand (time(NULL));
 
  // Pick the base to use in the PosInt class
  PosInt::setBase (10);
 
  // These parameters determine the blocking of characters
  PosInt byte(256);
  int blocklen = 10;
  PosInt topByte(1);
  for (int i=0; i<blocklen-1; ++i) topByte.mul(byte);
 
  if (argc < 2 || argv[1][0] != '-') usage(argv[0],1);
  if (argv[1][1] == 'k') {
    if (argc != 4) usage(argv[0],3);
    ofstream pubout(argv[2]);
    ofstream privout(argv[3]);
    if (! pubout || ! privout) {
      cerr << "Can't open public/private key files for writing" << endl;
      return 4;
    }
    ////////////////////////////////////////////////////////////////////
    //                 KEY GENERATION                                 //
    ////////////////////////////////////////////////////////////////////
    
    // These are just "dummy" values! Replace with your actual code
    PosInt n (15);
    PosInt e (7);
    PosInt d (13);
 
    // Print out the keys to their respective files.
    pubout << e << endl << n << endl;
    privout << d << endl << n << endl;
    
    ///////////////// (end of key generation) //////////////////////////
    pubout.close();
    privout.close();
    if (interactive)
      cerr << "Public/private key pair written to " << argv[2]
           << " and " << argv[3] << endl;
  }
  else if (argv[1][1] == 'e') {
    if (argc != 3) usage(argv[0],3);
    ifstream pubin (argv[2]);
    if (! pubin) {
      cerr << "Can't open public key file for reading" << endl;
      return 4;
    }
    if (interactive)
      cerr << "Type your message, followed by EOF (Ctrl-D)" << endl;
    ////////////////////////////////////////////////////////////////////
    //                  ENCRYPTION WITH PUBLIC KEY                    //
    ////////////////////////////////////////////////////////////////////
    // Read public key from pubin file
    PosInt e, n;
    pubin >> e >> n;
 
    // Read characters from standard in and encrypt them
    int c;
    PosInt M (0); // Initialize M to zero
    PosInt curByte (topByte);
    
    bool keepGoing = true;
    while (keepGoing) {
      c = cin.get();
 
      if (c < 0) keepGoing = false; // c < 0 means EOF or error.
      else {
        PosInt next (c); // next character, converted to a PosInt
        next.mul(curByte); // next *= curByte
        M.add(next);     // M = M + next
        curByte.div(byte);
      }
 
      if (curByte.isZero() || (!keepGoing && !M.isZero())) {
        // HERE'S WHERE YOU HAVE TO DO THE ENCRYPTION!
        PosInt E (1234); // THIS IS JUST A "DUMMY" VALUE
        cout << E << endl;
 
        // Now reset curByte and M and keep going
        curByte.set(topByte);
        M.set(0);
      }
    }
    ////////////////// (end of encryption) /////////////////////////////
    if (interactive)
      cerr << "Message successfully encrypted." << endl;
    pubin.close();
  }
  else if (argv[1][1] == 'd') {
    if (argc != 3) usage(argv[0],3);
    ifstream privin (argv[2]);
    if (! privin) {
      cerr << "Can't open private key file for reading" << endl;
      return 4;
    }
    if (interactive)
      cerr << "Enter encrypted numbers, one at a time, ending with EOF" << endl;
    ////////////////////////////////////////////////////////////////////
    //                 DECRYPTION WITH PRIVATE KEY                    //
    ////////////////////////////////////////////////////////////////////
    // Get private key from file
    PosInt d, n;
    privin >> d >> n;
 
    // Read numbers from standard in and decrypt them
    PosInt E;
 
    while (cin >> E) {
      // You have to decrypt E and print out the 10 characters it holds.
      // Note: use the "convert" function to turn a PosInt into
      // a regular "int" - and then into a char!.
      // Follow the procedure from encryption, only in reverse.
      cout << "abcdefg\n"; // THIS IS JUST A DUMMY!
    }
    ////////////////// (end of decryption) /////////////////////////////
    if (interactive)
      cerr << "Message successfully decrypted." << endl;
    privin.close();
  }
  else if (argv[1][1] == 'h') usage(argv[0], 0);
  else usage(argv[0],2);
  return 0;
}
 
////////////////////////////////////////////////////////////
//              MODULAR EXPONENTIATION                    //
////////////////////////////////////////////////////////////
 
// Computes a^b mod n, and stores the answer in "result".
void powmod (PosInt& result, const PosInt& a, const PosInt& b, const PosInt& n) {
  // YOU HAVE TO FILL THIS IN!
}
 
 
////////////////////////////////////////////////////////////
//              KARATSUBA MULTIPLICATION                  //
////////////////////////////////////////////////////////////
 
// Sets "this" PosInt object to "this" times x.
void PosInt::fasterMul (const PosInt& x) {
  // This is a suggestion of how to do this one:
 
  // First figure out the larger of the two input sizes
  int n = digits.size();
  if (n < x.digits.size()) n = x.digits.size();
  
  // Now copy the inputs into vectors of that size, with zero-padding
  vector<int> mycopy(digits);
  vector<int> xcopy(x.digits);
  mycopy.resize(n, 0);
  xcopy.resize(n, 0);
 
  // Set "this" digit vector to a zeroed-vector of size 2n
  digits.assign (2*n, 0);
 
  // Now call the array version to do the actual multiplication
  fastMulArray (&digits[0], &mycopy[0], &xcopy[0], n);
 
  // We have to call normalize in case there are leading zeros
  normalize();
}
 
// This does the real work of Karatsuba's algorithm
// (or whatever multiplication algorithm you might write).
// The input is two arrays of digits, x and y, which both have length len.
// The output is stored in the array dest, which is already allocated
// to the proper length.
void PosInt::fastMulArray (int* dest, const int* x, const int* y, int len) {
  // Again, this is just a suggested general outline...
  if (len <= 3) {
    // base case
    // YOU FILL THIS IN
  }
  else {
    // recursive case
    // YOU FILL THIS IN TOO.
    // Hint: you will have to allocate some memory for U, V, P0, P1, and P2
    // Another hint: use the addArray and subArray helper methods from the
    // PosInt class!
  }
}
 
 
// Prints a message on proper usage and exits with the given code
void usage (const char* progname, int ret) {
  cout
    << "Generate a public-private key pair:" << endl
    << "\t" << progname << " -k PUBLIC_KEY_FILE PRIVATE_KEY_FILE" << endl
    << "Encrypt a message with public key:" << endl
    << "\t" << progname << " -e PUBLIC_KEY_FILE" << endl
    << "Decrypt a message with private key:" << endl
    << "\t" << progname << " -d PRIVATE_KEY_FILE" << endl
    << "Note: PUBLIC_KEY_FILE and PRIVATE_KEY_FILE are any filenames you choose."
    << endl
    << "      Encryption and decryption read and write to/from standard in/out."
    << endl
    << "      You have to end the input with EOF (Ctrl-D if on command line)."
    << endl
    << "      You can use normal bash redirection with < and > to read or" << endl
    << "      write the encryption results to a file instead of standard in/out."
    << endl;
  exit(ret);
}