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):
QuoteYour 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
#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
#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();
}
at what Grade do you get to learn to program?
4th grade.
Requires high ambition and a good book. Knowledge of English is not a requirement.
My 4th grade teacher didn't teach me.
That's because you're not jewish.
WTF, Jews learn C++ before me!?
Only if they're named Yoni.
Hahaha!
I learned VB in 4th grade! I was making teh leet AOL proggiez~
(In VB 3.0)
Quote from: Noodlez on April 02, 2004, 02:33 PM
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 :P)
Quote from: Newby on April 02, 2004, 11:44 PM
(I was only 10 @ the time and didn't have much of an attention span :P)
I'm 16 and still don't.
i was 9
What book do you use in your Algorithms course?
Quote from: dxoigmn on April 04, 2004, 03:49 PM
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)
Quote from: K on April 04, 2004, 03:58 PM
Quote from: dxoigmn on April 04, 2004, 03:49 PM
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.
Quote from: Yoni on April 04, 2004, 09:55 PM
Quote from: K on April 04, 2004, 03:58 PM
Quote from: dxoigmn on April 04, 2004, 03:49 PM
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.
Well I have it in Latin.
Quote from: K on April 04, 2004, 03:58 PM
Quote from: dxoigmn on April 04, 2004, 03:49 PM
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)
Hehe ahh yes. Tom Cormen is the CS Undergraduate Advisor here, and teaches the Algorithms course sometimes. Is a good book indeed, I hope he teaches the course when I take it :)
You know that Dartmouth College has the same engineering rating as San Jose State.
Haha I wonder what our engineering rating is...I know what our party school rating is. ;)
Ours at Arizona State is (from US News and World Report) 33, but it's definitely not because of our CS department. :-/
I've been programming in BASIC since I was 8 or 9 (when I first could get my hands on GW-BASIC and some Apple II's). I started Javascript when I was 13.
Quote from: K on April 05, 2004, 06:15 PM
Haha I wonder what our engineering rating is...I know what our party school rating is. ;)
Some of the top 100 best undergraduate engineering programs
5 is the highest.
MIT : 4.8
UCLA : 3.7
University of Colorado - Boulder : 3.5
Az. Sate: 3.3
Yale : 3.3
Dartmouth : 3.2
Washington State : 2.9
San Jose State : 3.2
Quote from: Maddox on April 05, 2004, 07:37 PM
Quote from: K on April 05, 2004, 06:15 PM
Haha I wonder what our engineering rating is...I know what our party school rating is. ;)
Some of the top 100 best undergraduate engineering programs
5 is the highest.
MIT : 4.8
UCLA : 3.7
University of Colorado - Boulder : 3.5
Az. Sate: 3.3
Yale : 3.3
Darmouth : 3.2
Washington Sate ; 2.9
San Jose State : 3.2
Sweet, I have a 3.5 GPA too.