Closed

Build RSA Project

This project was awarded to wangbeizou for $40 USD.

Get free quotes for a project like this
Employer working
Project Budget
$10 - $30 USD
Total Bids
8
Project Description

To build an RSA crypto system, you first need to find two random primes. Your primes will consist of 7 bits. You will set the first and the last bits to be 1 and randomly choose one-by-one the internal 5 bits. We could have used only 7 bits to store it, but to simplify the program, store it as a standard 32 bit integer, so there will be 25 leading 0 bits.

You will use the variant of the Miller-Rabin algorithm (and not as it is generally presented) to test if your 7-bit number n is a prime. You will pick some random a’s, such that 0 < a < n. You can do it either by a process similar to getting a candidate prime above, or to simplify your program, you can just get a pseudorandom number and “cut it down to size” by computing its remainder modulo n, and discarding it if it is 0. If your number passes the Miller-Rabin test for 20 values of a, you may declare it as prime. For completeness, make sure that one of the n’s turned out not to be a prime number. So, if you immediately find the prime numbers you need, pick any number you know not to be prime and perform the test on it. If the test says it is possibly a prime, look for another number that you know not to be a prime.

Print a line with the line number shown on the left and below that line, for one that turned out not to be prime and the a for which the answer was “not prime,” produce a trace.

Print a line with the line number shown on the left and below that line, for one n that turned out to be prime and one a for which the answer was “perhaps prime,” produce a trace. Now, given two primes p and q you found, you will get n = p × q. Note that p and q should be different, so you need to check for this. In a “real” search for large number the probability that p = q is so small that there is no need

to check for this, but as you are working with very small numbers, you need to

check for that. Pick a small number to be the public key e. It has to be relatively prime with φ(n). To check if it is relatively prime and to find a multiplicative inverse to serve as the private key d, use the Extended Euclidean Algorithm, which you will code. If e is not relatively prime with φ(n), then find another small number. Do not do it randomly, start with 3 and go up until you find an appropriate e. In the extremely unlikely case (which would not happen in a real RSA implementation), that all the values of e you try do not work, just pick another pair of random primes and continue from there. And if the smallest e you find is big which here means bigger than φ(n) that is also fine for your project.

Print a line with the line number shown on the left and below that line, for the system that Alice (see later) will use, show how you found e, that is show how you used the algorithm on the various candidates for e until you got the right one. (If you are lucky, the first e you tried, worked—this is fine too.). Produce a trace for each e just as we had in class for the Extended Euclidean algorithm. For the value of e found, find the corresponding value of d and normalize it so that it is positive and smaller than φ(n). (If it happens that d = e, this will be fine too for your project, though of course not in a real RSA system.) Print a line with the line number shown on the left and below that line, list the value of d. So, the public key of Alice, is really the pair ⟨n, e⟩ and the private key of Alice is ⟨n, d⟩; only she knows the latter, more precisely only she knows d. but you need to check for it in your implementation

Print a line with the line number shown on the left and below that line, list the following for Alice, both as integers and as sequences of bits: p,q,n,e,d.

Awarded to:

Looking to make some money?

  • Set your budget and the timeframe
  • Outline your proposal
  • Get paid for your work

Hire Freelancers who also bid on this project

    • Forbes
    • The New York Times
    • Time
    • Wall Street Journal
    • Times Online