Algorithms Class Homework

[K]

I thought some of you might be interested in this assignment from my 3104 class.  This is by far the simplest assignment we've had so far, but probably one of the more interesting.  Note that LEDA/integer.h (integer) represents an arbitrary length integer.

Here's the assignment (abbreviated from a nasy postscript file):

Your task is to write the two routines declared in rsa.h, exponentiate and rsa_decode.  exponentiate implements the modular exponentiation routine [we discussed in class].  You should optimize as you see fit, since there will be timing requirements. rsa_decode reads in the four provided ciphertext files and and returns the decrypted message.  here are the details:  

Each file contains an RSA encoded message.  The first two numbers in the file comprise the private key, n [the modulus] and d [the decoding exponent].  After these two numbers, the rest of the numbers decrypt to a sequence of one or more ASCII characters.  In addition, each character is 9 bits with the last bit being random.  Concatenate all these ASCII characters in the correct order to recover the original message.  Each successive file contains more ASCII characters per number.  The first file contains only one character for each number.

rsa.h

Code Select Expand


#ifndef RSA_H
#define RSA_H

#include <iostream>
#include <fstream>
#include <cassert>
#include <LEDA/integer.h>

// use this typedef if you are developing the program without LEDA:
// only the first three tests in main.cc will work.
//typedef long integer;

typedef char file_name [10];
const int message_length=10000;
typedef char plaintext [message_length];
// use this to terminate your decoded message
const char null_terminator = '\0';

// returns the value of a^n (mod m)
integer exponentiate( integer a, integer n, integer m );

/**********************************************************

  input parameter f is the name of a file containing
  the ciphertext, in the format  described in the assignment.
 
  rsa_decode opens & closes file f.

  rsa_decode sets the array message to the decrypted text.
  message[] should be in the form of a null-terminated string. i.e.,
  the original plaintext message consists of characters

         message[0],message[1],...,message[k],

  and message[k+1] contains the character '\0', available
  as the constant declared above.

************************************************************/
void rsa_decode (file_name f, plaintext message);

#endif




And here is my solution:

rsa.cc

Code Select Expand


#include "rsa.h"

using namespace std;

integer exponentiate( integer a, integer n, integer m )
{
   integer x = 1;
   while( n > 0 )
   {
      if ( (n & 1) != 0)
         x = (x * a) % m;
      a = (a * a) % m;
      n >>= 1;
   }
   return x;
}

inline void helper_swap(char& a, char& b)
{
   // a ^= (b ^= (a ^= b))
   char c = b; b = a; a = c;
}

void rsa_decode (file_name f, plaintext message)
{
   ifstream in;

   integer n, d;
   integer read_val, decoded_val;
   int i = 0, start_i, end_i, end_val;

   in.open(f);
   in >> n >> d;

   while(!in.eof())
   {
      in >> read_val;
      decoded_val = exponentiate(read_val, d, n);

      start_i = i;
      while( (decoded_val & 0xFF) != 0)
      {
         message[i] = static_cast<char>((decoded_val >>= 1) & 0xFF);
         ++i;
         decoded_val >>= 8;
      }
      end_i = i - 1;

      end_val = (end_i - start_i + 1) >> 1;
      
      // reorder the characters since we read them in the reverse order
      for(int q = 0; q < end_val; ++q)
         helper_swap(message[start_i + q], message[end_i - q]);
   }

   message[i] = null_terminator;
   in.close();
}


[Fr0z3N]

at what Grade do you get to learn to program?

[Yoni]

4th grade.
Requires high ambition and a good book. Knowledge of English is not a requirement.

[Fr0z3N]

My 4th grade teacher didn't teach me.

[j0k3r]

That's because you're not jewish.

[Fr0z3N]

WTF, Jews learn C++ before me!?

[j0k3r]

Only if they're named Yoni.

[Fr0z3N]

Hahaha!

[Noodlez]

I learned VB in 4th grade! I was making teh leet AOL proggiez~
(In VB 3.0)

[Newby]

I learned VB in 4th grade! I was making teh leet AOL proggiez~
(In VB 3.0)

I attempted to learn C in 4th grade.

I stopped after 3 days because the phrase "data types" scared me >_<

(I was only 10 @ the time and didn't have much of an attention span )

[j0k3r]

(I was only 10 @ the time and didn't have much of an attention span )

I'm 16 and still don't.

[Banana fanna fo fanna]

i was 9

[dxoigmn]

What book do you use in your Algorithms course?

[K]

What book do you use in your Algorithms course?

We use a collection of notes that my professor has written, but the suggested book that some our assignments reference is Introduction to Algorithms, Second Edition by  Cormen, Leiserson, Rivest, and Stein. (CLRS)

[Yoni]

What book do you use in your Algorithms course?

We use a collection of notes that my professor has written, but the suggested book that some our assignments reference is Introduction to Algorithms, Second Edition by  Cormen, Leiserson, Rivest, and Stein. (CLRS)

That is one of the best books ever written. I have it in Hebrew.