programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Tim Cooke
• Devaka Cooray
• Ron McLeod
• Jeanne Boyarsky
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Piet Souris
• Carey Brown
• Tim Holloway
Bartenders:
• Martijn Verburg
• Frits Walraven
• Himai Minh

# New RSA Question

Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:
So it turns out that we weren't allowed to use BigInteger, so I had to restart coding. I'm havng trouble figuring out how to code D right now. D is defined to us as:

// Generate D with the following properties:
// 1. 0 < D <= PQ
// 2. (DE-1) is evenly divisible by phiPQ

Here is the code so far:

I just really have no clue how to make that loop work. Wouldn't it always just stop at one if I just start counting up with D by 1 until I find a divisible number? And on a side note, my computation for e is wrong, but I can fix that later. :P

lowercase baba
Posts: 13082
67
• Number of slices to send:
Optional 'thank-you' note:
Do you know how to calculate PQ?
Do you know how to calculate DE - 1?
Do you know how to calculate phiPQ?
Do you know how to test, in general, if A is evenly divisible by B?

Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

fred rosenberger wrote:Do you know how to calculate PQ?
Do you know how to calculate DE - 1?
Do you know how to calculate phiPQ?
Do you know how to test, in general, if A is evenly divisible by B?

Alright, I think I figured it out, but that section with e is giving me problems. Whem assigning p to 109 and q to 71, I should be getting e = 11, but i get e = 7559 and (PhiPQ is 7560, don't know if that's relevant).

Sheriff
Posts: 27460
88
• Number of slices to send:
Optional 'thank-you' note:
I would have just called the local variable in your findD() method "d", since that's how you are using it. That class-level variable "d"... your findD() method assumes it's initialized to zero. You're better off not having it all, and just letting findD() do its job and find the right value.

And does your pickPrime() method actually return only primes? My impression is that it will always return the first random number it picks, prime or not.

Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:I would have just called the local variable in your findD() method "d", since that's how you are using it. That class-level variable "d"... your findD() method assumes it's initialized to zero. You're better off not having it all, and just letting findD() do its job and find the right value.

And does your pickPrime() method actually return only primes? My impression is that it will always return the first random number it picks, prime or not.

I actually need to keep d as a class thought because I use it gain in the encryptMsg method. Now e just outputs as zero. Also, For the encrypt and decrypt message sections, Im pretty positive that the encrypt method is correct ( I cant test it yet because of the e problem), but I can tell that my decrypt message is completely wrong starting with . What's the easiest way to reverse the encryption method?

And yes, it does in fact only pick primes.

Bartender
Posts: 3323
86
• Number of slices to send:
Optional 'thank-you' note:

And yes, it does in fact only pick primes

Really, when I called the method 20 times I got:

75
73
57
39
119
112
90
55
38
80
72
14
106
93
47
52
127
31
91
76

Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

Tony Docherty wrote:

And yes, it does in fact only pick primes

Really, when I called the method 20 times I got:

75
73
57
39
119
112
90
55
38
80
72
14
106
93
47
52
127
31
91
76

Oh, I think it has something to do with the loop then... This project is turning into a mess. T_T

Paul Clapham
Sheriff
Posts: 27460
88
• Number of slices to send:
Optional 'thank-you' note:

Dan Bolens wrote:Oh, I think it has something to do with the loop then... This project is turning into a mess. T_T

Not that loop. This one:

Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:

Dan Bolens wrote:Oh, I think it has something to do with the loop then... This project is turning into a mess. T_T

Not that loop.

@OP: That outer loop won't make your prime test fail, but it will make it take a lot longer than necessary. If you want to look for factors of X, you don't need to go up to X - 1. You only need to go up to sqrt(X). Do you understand why that is true?

Also, rather than putting the code to test whether a number is prime inside the findPrime() method, you should create a separate method calls isPrime() that takes in a number and returns a boolean. You can write and test that method completely independently of anything else. Once you have it working, you can write findPrime(), which will be much smaller now--just a small loop that generates a random number and then calls isPrime() until it returns true.

You mentioned the project becoming a mess. A major reason for that is a failure to do things in small pieces like that. If you focus on one small piece that does one job, and get that piece working independently of any others before moving on, you'll find your overall task becomes much more manageable.

Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

Not that loop. This one:

The "fakecode" we were given is:

Do until a prime is found
randomly select a number between 3 and 128
loop from i equal to 2 to P - 1 and increment i by one each time
if P mod i is zero
break; // it isn't prime, no need to continue
if i is greater than or equal to P - 1 then P is prime

I'm not quite sure what I have that's missing... (apologies if it's obvious. I've been staring at this screen for 12 hours now working on different projects.)

Paul Clapham
Sheriff
Posts: 27460
88
• Number of slices to send:
Optional 'thank-you' note:
It's not that you are missing anything. On the contrary, you have an extra line of code which doesn't match your "fakecode".

Specifically, it's the line of code in your real code which comes after your implementation of the "fakecode".

Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:It's not that you are missing anything. On the contrary, you have an extra line of code which doesn't match your "fakecode".

Specifically, it's the line of code in your real code which comes after your implementation of the "fakecode".

*shoot self in foot* I'm assuming it ha something to do with the while (true) but I honestly can't see it. I know I have this problem, a problem with findE, and a problem with my decryption. It probably makes the most sense to just start over now... Between my laptop screen breaking (Im working on my TV) and breaking a hand, doing well in class has just been near impossible this last week. T_T

Paul Clapham
Sheriff
Posts: 27460
88
• Number of slices to send:
Optional 'thank-you' note:

Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:

Well, getting rid of the return just throws the program into an infinite loop, and I obviously cant remove the while... I knew it was one of these lines, but getting rid of one or the other just causes more problems.

Oh, now I see. I remove it and a conflict occurs between

while (i < randomNumber - 1)

and

if (i >= randomNumber - 1)

GOT IT!!! n :D Now on to the findE problem...

Paul Clapham
Sheriff
Posts: 27460
88
• Number of slices to send:
Optional 'thank-you' note:
Yes, it looks like you're on the right track. But in my opinion you've got too much code there, it's doing two different things, and that's leading to confusion. I would have written the loop like this:

The code you have is partly for finding if a number is prime, and partly for repeatedly trying random numbers until you get one you like. So you should split that code into two parts. What I posted there is code for repeatedly trying random numbers until you get one you like. Now you just need code which tells you if a number is prime.

Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:Yes, it looks like you're on the right track. But in my opinion you've got too much code there, it's doing two different things, and that's leading to confusion. I would have written the loop like this:

The code you have is partly for finding if a number is prime, and partly for repeatedly trying random numbers until you get one you like. So you should split that code into two parts. What I posted there is code for repeatedly trying random numbers until you get one you like. Now you just need code which tells you if a number is prime.

Well, whatever I just changed in mine seems to work just fine. Thanks for the help so far. :D The problem I have with the findE loop is that is goes to whatever PhiPQ equals - 1. For instance, it should be stopping at 11 when P = 109 and Q = 71.

The code we were given is:

// Generate an E with the following properties:
// 1. 1 < E < phiPQ
// 2. E and phiPQ are relatively prime
// relatively prime means that gcd(E, phiPQ) == 1
// 3. There may be several candidates for E, so pick the smallest one
// (for consistency with the rest of the class -- there is no
// theoretical reason for this constraint)

Along with

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Dan Bolens wrote:

Paul Clapham wrote:But in my opinion you've got too much code there, it's doing two different things, and that's leading to confusion. I would have written the loop like this:
[snip]
The code you have is partly for finding if a number is prime, and partly for repeatedly trying random numbers until you get one you like. So you should split that code into two parts.

Well, whatever I just changed in mine seems to work just fine.

He's telling you exactly the same thing I did. You might want to pause to think if we might know what we're talking about and maybe have a good reason for suggesting this. Sure, your code works now, but...

• If you find you have to modify it, it's a mess, and it will be harder to modify than if you had well-defined methods that did one well-defined job each, even more so as time passes.
• If you need to test for primeness in a future project, you won't have a method you can just grab and re-use. You'll have to write it from scratch, or figure out what part of that big blob of code is relevant for the prime test.
• Most importantly, you're writing off a very bad habit as not a big deal. You'll be likely to continue with that habit in the future. Learning about loops is much less important right now than developing the habit of breaking problems down into small, independent pieces.

•
Dan Bolens
Greenhorn
Posts: 25
• Number of slices to send:
Optional 'thank-you' note:

Jeff Verdegan wrote:

Dan Bolens wrote:

Paul Clapham wrote:But in my opinion you've got too much code there, it's doing two different things, and that's leading to confusion. I would have written the loop like this:
[snip]
The code you have is partly for finding if a number is prime, and partly for repeatedly trying random numbers until you get one you like. So you should split that code into two parts.

Well, whatever I just changed in mine seems to work just fine.

He's telling you exactly the same thing I did. You might want to pause to think if we might know what we're talking about and maybe have a good reason for suggesting this. Sure, your code works now, but...

• If you find you have to modify it, it's a mess, and it will be harder to modify than if you had well-defined methods that did one well-defined job each, even more so as time passes.
• If you need to test for primeness in a future project, you won't have a method you can just grab and re-use. You'll have to write it from scratch, or figure out what part of that big blob of code is relevant for the prime test.
• Most importantly, you're writing off a very bad habit as not a big deal. You'll be likely to continue with that habit in the future. Learning about loops is much less important right now than developing the habit of breaking problems down into small, independent pieces.

• I do plan on reworking the code, but for time sake (this should be finished tomorrow), I'm just trying to squeeze out what I can. And doing it with a broken hand doesnt help my speed much.

I think the problem once again is my loop in FindE.

And I know the problems for FindD is the while loop. I think the combined levels of stress and working at this all day have made me forget basic Java code. I can't think of what loop to change to. T_T

Well, after working with a CS Major friend for another hour on this, I think Im pretty much stuck taking whatever grade I'll get. I honestly just can't for the life of me figure out what's wrong or how to fix it. There's just too much wrong with each method still (including my encryption) and 16 hours of programming tons of stuff is enough for today. Thanks for all your help everyone. I'll take all your advice and apply it towards future programs. :D

Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

Dan Bolens wrote:Well, after working with a CS Major friend for another hour on this, I think Im pretty much stuck taking whatever grade I'll get. I honestly just can't for the life of me figure out what's wrong or how to fix it. There's just too much wrong with each method still (including my encryption) and 16 hours of programming tons of stuff is enough for today. Thanks for all your help everyone. I'll take all your advice and apply it towards future programs. :D

I hope so, because otherwise you're likely to simply repeat the same mistakes.

Programming is about thinking, not coding; and good programming also requires planning, so the likelihood of an 11th-hour change turning a bad program into a good one is extremely remote.

However, best of luck with your exam.

Winston

 Montana has cold dark nights. Perfect for the heat from incandescent light. Tiny ad: the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising