Project #2 :: RSA Cryptosystem

CIS341 - Due: March 29, 2005

Implement a prototype of the RSA algorithm using medium sized integers and explore ways of implementing RSA using very large integers.

You may use the programs Plain-to-Bits,  Bits-to-Ints  and LongBitsToInts to do some of your work for you.

Component 1::

   Use p = 7; q = 11; e = 13; and d = 37.

   Convert the plaintext to a bit stream, representing each character with its 7-bit ASCII value.  Write code to encode plaintext and decode cipher text 6 bits at a time.

   Encrypt plaintext #1.

   Decode cipher text #1.

Component 2::

   Use p = 23; q = 43; e = 41; and d = 293.

   Convert the plaintext as before.  Write code to encode plaintext and decode cipher text 9 bits at a time.

   Encrypt plaintext #2.

   Decode cipher text #2.

Component 3::

   Use p = 139; q = 151; e = 73; and d = 4537.

   Convert the plaintext as before.  Write code to encode plaintext and decode cipher text 14 bits at a time.

   Encrypt plaintext #3.

   Decode cipher text #3.

Component 4::

  Find your own values for p & q and appropriate values for e & d.  Remember, e can be any number relatively prime to p, q and f(n).  And, to find d, you can use the Extended Euclid program.

   Convert the plaintext as before.  Write code to encode plaintext and decode cipher text 24 bits at a time.  The program skelEncRSA can be used to handle the large integer operations required.

{{The only code that you need to add to this program is this:

Public Sub cmdDoIt_Click()
Dim i As Long
Dim baseFileName, plainFileName As String
Dim numInts As Long
'Get base file name from user
' Read from base file: p, q, e, and name of plain integer file
n = MultInt(p, q)
' Multiply p & q to obtain n
' Call readPlainInts to read integers of plain text, returning the number of
' integers read, assigning that to numInts
' Echo print the plain text integers into debug file (debugF)
' For loop: 0 to numInts-1
' Call HiPowMod with each integer in array plainNum along with e & n
' assigning returned value to array cipherNum, at the same time
' calling WriteInt to print values of cipherNum to cipher text file, cipherF
End Sub

Private Sub Form_Activate()
txtFileName.SetFocus
End Sub

Public Function readPlainInts(ByVal fileNum As Integer) As Integer
Dim intCount As Integer
' Set intCount to 0
' While Loop: condition = not EOF fileNum
' Assign value returned from function call to ReadInt to array plainNum
' using intCount as index into that array
' Increment intCount
' Return value of intCount as function value
End Function

}}

   Encrypt plaintext #4.

   Decode cipher text #4, using p=4111, q=4133, e=4201, and d=10567081.

   [Hint: Look into data type “long long int”:

http://www.ictp.trieste.it/~manuals/programming/sun/c-plusplus/c++_ug/Diff_C_C++.doc.html]

Component 5 (Extra credit)::

  Do the above for 100 or more bits.  You can use this VB program for working with super-long integers or use one of several C++ or Java modules for working with long integers.  Adapt this code to your program.  Encrypt and decrypt plaintext #5.  A special prize to the person who succeeds in using the largest values for p and q.

Sources of Prime Numbers::

   There are lists of primes up to 5987 and up to 9413 on my CIS135 website.  Two 4 digit primes will give you an 8 digit value for n.  Or, you can use the code supplied to the 135 class to generate even large primes.  There are many lists of primes on the web.  The Mersenne primes are especially large.

Project Submission::

1. Please follow the directions found here.

2. For each component, be sure to specify the values of p, q, e, d, and n.  Hand in your source code along with the input used and all output produced.