CS 341: Cryptography
RSA Party
The second attempt at a party will happen from 8:30-9:40AM Wednesday, February 2. Code and results will
be due by 11:59PM the same day.
Each person or team should come to CMC 306 equipped with:
- A collection of at least 20 ASCII text messages. Keep these secret.
- A program written by the person or team in Python, C, C++, Java, or Perl,
named rsa.py (or .c, .cpp, .java, .pl), with usage as described below.
- Any other code (again written by the person or team in question)
that seems like it might be handy if, hypothetically, you have the opportunity to try to
spy on other people's communications during the party.
Message representations
For our purposes, messages will begin life as ASCII text, which is then
transformed into "encoded" text. The RSA algorithm will be used to encrypt,
decrypt, sign, etc. encoded text.
The ASCII text will be encoded in five-character blocks, each of which will
be transformed into a 12-digit upper-case hexadecimal number. The first two
digits of the encoded block will be 00. Then each character in the five-character
ASCII block will be represented as the two-digit hexadecimal representation of
its ASCII value. For example, "moose" will be encoded to "006D6F6F7365".
If the last block in the message has fewer than five characters, its encoded
version will start with enough 00's to fill the encoding to 12 hexadecimal digits.
For example, if the last block is "r.", its encoding will be "00000000722E".
To make it easier to read the encoded text, the encoding will be separated into
60-digit lines.
For example, the ASCII text:
The moose and the goat plotted the downfall of the tapir.
will be encoded as:
00546865206D006F6F73652000616E64207400686520676F00617420706C
006F7474656400207468652000646F776E6600616C6C206F006620746865
00207461706900000000722E
Once you have encoded text, you'll need to separate it into blocks for
encryption or decryption. We are going to use 48-bit n's, and we want each block
to be an integer smaller than n. By encrypting the 12-hexadecimal-digit blocks
described above, we achieve this goal with room to spare (since the encoded blocks
represent integers no more than 40 bits long).
For example, the first M to be encrypted will be the integer whose
hexadecimal representation is 00546865206D. This number
is 39 bits long in binary, since the leading hexadecimal 5 has a leading 0 in its
binary form 0101, and is thus plenty small enough to be encrypted using a public
key (e, n) for which n is a 48-bit number.
Really, all we're doing here is treating ASCII text like a big long
bit string, which we then break into 40-bit (i.e. 5-character) chunks for
encryption. The folderol about "encoding" just gives us input and output
routines and a uniform way of writing long bit strings (encrypted or not)
to make it easy for us to deliver these long binary numbers via e-mail.
The program
Your program should support, at minimum, the following command-line options.
I have written them here as Python command lines, but the C/C++, Java, or
Perl variants should be straight-forward.
python rsa.py --keygen
Input: none
Output: three lines of text to standard output. The first line
will be "n: " followed by a 48-bit integer expressed in upper-case
hexadecimal. The second and third lines will start with "e: " and
"d: " respectively, with upper-case hexadecimal representations of
the encryption and decryption integers following. (Your integers
may have leading 0's or not, as you prefer.)
The value of n should be at least 2^46 and strictly less than 2^48 (i.e.
either 47 or 48 bits when leading 0's are removed).
You may have additional output (e.g. lines for p and q) if that helps
you debug or do anything else of value.
python rsa.py --encrypt e n
Input: e and n are expressed as upper-case hexadecimal integers (with
or without leading zeros).
The message to be encrypted will be delivered via standard input, and
may be assumed to be encoded text as described above.
Output: The encrypted message, expressed as encoded text, sent to
standard output.
python rsa.py --decrypt d n
Input and output are the same as for --encrypt. In fact, the --decrypt
syntax is just a convenience for clarity, since it will perform precisely
the same operation as --encrypt.
python rsa.py --encode [message]
Input: The ASCII message to be transformed into encoded text is either
provided as command-line argument, or as text via standard input if the
message argument is absent. (Don't forget quotation marks if you type
your message as a command-line argument, so the shell will interpret the
message as a single argument rather than one argument per word.)
Output: The encoded text, to standard output.
python rsa.py --decode
Input: Encoded text delivered via standard input.
Output: The corresponding ASCII text, to standard output.
Example results
Here are results from my implementation. I generated these items and stored them
in like this:
python rsa.py --keygen
echo "The moose and the goat plotted the downfall of the tapir." > message.txt
python rsa.py --encode < message.txt > encoded.txt
python rsa.py --encrypt 000000000017 AA93FC019C7F < encoded.txt > encrypted.txt
python rsa.py --decrypt 4674C605851B AA93FC019C7F < encrypted.txt > decrypted.txt
python rsa.py --decode < decrypted.txt > decoded.txt
Key:
n: AA93FC019C7F
e: 000000000017
d: 4674C605851B
Original message:
The moose and the goat plotted the downfall of the tapir.<newline>
Encoded message:
00546865206D006F6F73652000616E64207400686520676F00617420706C
006F7474656400207468652000646F776E6600616C6C206F006620746865
002074617069000000722E0A
Encrypted message:
4B5E43EFBA952060F7FF0F2F861223FD88AC0B34F827323F797015274AF2
7B81975736FF469718AE79EF48F9C8401877564E7AFBE243A3727DEE7ED1
992F80D7A4B6507594595522
Decrypted message:
00546865206D006F6F73652000616E64207400686520676F00617420706C
006F7474656400207468652000646F776E6600616C6C206F006620746865
002074617069000000722E0A
Decoded message:
The moose and the goat plotted the downfall of the tapir.<newline>