At Programming Homework Tutors, we believe in providing our students with practical, real-world examples of how to apply the concepts they learn in class. That’s why we’ve developed a variety of sample projects to help you see how our courses can be used to create impactful solutions in your field of study.

Project Description

In this project, you will first learn how to generate large prime numbers followed by implementing the RSA algorithm. Since you will have to compute large exponents as part of the RSA algorithm, the standard integer types (int – 16 or 32 bits, long int – 32 bits and even long long int – 64 bits) of most computer languages will not suffice. Here are a few choices suggested:

Java has a built-in bigint class that behaves exactly like an int, except that it is not bounded by a finite value

C++ you will have to use a library such as NTL (http://shoup.net/ntl/) (Library for doing Number Theory) or GMP (http://directory.fsf.org/wiki/GNU) (the GNU Multiple Precision Arithmetic Library)

In Ruby you do not have to worry about the size of numbers at all, Ruby automatically takes care of any conversion between numbers of fixed size (Fixnum – 16, 32, 64 bits) and Bignum (numbers with an arbitrary number of digits)

Students can use other coding languages than the suggested ones above.

This project is broken down into two main parts. Each part will be graded separately, but each part will also be reused for other parts of the assignment. This will allow you to test each part conclusively before moving on.

Part 1: Prime Numbers (50%)

RSA requires finding large prime numbers very quickly. You need to implement a method for primality testing of large numbers. You are suggested to implement the Miller-Rabin test as studied in ECE543/444. It is also allowed to implement other well adopted test methods such as Solovay–Strassen primality test or Frobenius pseudoprimality test. Your task is to develop two programs (make sure you use your two programs to check each other).  

The first program is called primecheck and will take a single argument, an arbitrarily long positive integer and return either True or False depending on whether the number provided as an argument is a prime number or not. You may NOT use the library functions that come with the language (such as in Java or Ruby) or provided by 3rd party libraries.

Example (the $ sign is the command line prompt):

$ primecheck 32401 

$ True

$ primecheck 3244568 

$ False

Your second program will be named primegen and will take a single argument, a positive integer which represents the number of bits, and produces a prime number of that number of bits (bits not digits). You may NOT use the library functions that come with the language (such as in Java or Ruby) or provided by 3rd party libraries.

$ primegen 1024 

$ 14240517506486144844266928484342048960359393061731397667409591407

34929039769848483733150143405835896743344225815617841468052783101

43147937016874549483037286357105260324082207009125626858996989027

80560484177634435915805367324801920433840628093200027557335423703

9522117150476778214733739382939035838341675795443

$ primecheck 14240517506486144844266928484342048960359393061731397

66740959140734929039769848483733150143405835896743344225815617841

46805278310143147937016874549483037286357105260324082207009125626

85899698902780560484177634435915805367324801920433840628093200027

5573354237039522117150476778214733739382939035838341675795443  $ True

Part 2: RSA Implementation (50%)

You will implement three programs: keygen, encrypt and decrypt.

keygen will generate a (public, private) key pair given two prime numbers.

Example (the $ sign is the command line prompt):

$ keygen 127 131 

$ Public Key: (16637,11) 

$ Private Key: (16637,14891)

In the table below you’ll find some test cases for testing your keygen function. For those cases where you have to select your own numbers, make sure you select numbers that are at least 10 digits long.

encrypt will take a public key (n,e) and a single character c to encode, and returns the cyphertext corresponding to the plaintext, m.

Example:

$ encrypt 16637 11 20  

$ 12046

In the table below you’ll find some test cases for testing your encrypt function. For those cases where you have to select your own numbers, make sure you select n such that it is at least 20 digits long and that e is two digits long. The character c is a positive integer smaller than 256.

decrypt will take a private key (n, d) and the encrypted character and return the corresponding plaintext.

Example:

$ decrypt 16637 14891 12046  $ 20

In the table below you’ll find some test cases for testing your decrypt function.

Project Report and Code Chec

You need to write a technical report for this project. The report should describe the algorithms that are applied in your codes. You should have executable codes to support your results. Using your codes, we should be able to generate the results you present in your report. 

Disclaimer

The sample projects provided on our website are intended to be used as a guide and reference for educational purposes only. While we have made every effort to ensure that the projects are accurate and up-to-date, we do not guarantee their accuracy or completeness. The projects should be used at your own discretion, and we are not responsible for any loss or damage that may result from their use.
At Programming Homework Tutors, we are dedicated to helping students and educators achieve their goals by providing them with the resources they need to succeed. Our website offers a variety of tools and resources that can help you with the project mentioned above.
Whether you need help with research, project management, or technical support, our team of experts is here to assist you every step of the way. We offer online courses, tutorials, and community forums where you can connect with other learners and get the support you need to succeed.
If you’re looking to take your skills to the next level and make an impact in your field, we invite you to explore our website and see how we can help you achieve your goals.