Problem with generating keys for RSA

Question

https://www.sololearn.com/compiler-playground/cMy45Pknj91R

Im trying to generate public and private keys, but no matter which input i give public and private keys are the equal.

Answer 1

First, you should understand the algorithm before you try debugging it.

https://en.m.wikipedia.org/wiki/RSA_(cryptosystem)

Try to play it on pen and paper, how the keys should be calculated, make sure you can follow each step of the math.
Then try to write it down (with text, or draw a flowchart).
Finally you can match it with the code.

Can you describe with an example, what are the inputs to your function, and how the result should be calculated?

Answer 2

Do you understand your own algorithm?
Try printing the variables in strategic places of your code, to track how they change.
For example:
System.Console.WriteLine(quot;e_ = {e_}");

With your current test, before your while loop starts, feul is 516, d_ is 515, and e_ is 10
Then e_ is incremented as long as it reaches the same value as d_

Answer 3

Yes, but I meant the actual math part.
Given any two specific input numbers, for example what you just mentioned, what is the expected return value and the public and private keys.

If you are not sure about the formula, go ahead and read the wikipedia link that I gave in the previous comment, particularly the Operation / Key generation chapter. This algorithm is implemented in your code, at least it seems so to me (just with slightly different variable names).

Answer 4

Евгений you can find it in his profile.
https://code.sololearn.com/cMy45Pknj91R/?ref=app

Unfortunately the code link from the Sololearn website, does not work in the mobile app. Old bug.

Answer 5

Tibor Santa I just wanted the OP to put a little more effort into his question. But thanks anyway.

Answer 6

Artur Looks like you made a typo or some other little error while implementing the algorithm. What algorithm are you implementing? Can you provide us with a description?

Answer 7

Tibor Santa, this code was provided to me by my teacher, so i did not really questioned it. But as he explained, d_ and feult should be mutually simple, with for loop we check if there are any common divisor and if so, we decrement d_.

Answer 8

Sure!
Firstly, e_, d_ n_ are BigIntegers, not ulong.
Along with this function we use PrimeNumber generator, but for simplicity we will take numbers 43 and 59 as arguments;
This is how the function is used:

BigInteger d_, e_;
d_ and e_ are keys (private and public)

BigInteger n_ = Public_PrivateKey(43, 59, out d_, out e_);
n_ is a variable which needed to encrypt/decrypt file with RSA later.

Answer 9

Talking about math, feul is used to determine the possible values for the e_ and d_.
Loop attempts to find a value of d_ that is coprime with feul. If both feul % i == 0 and d_ % i == 0, it means i is a common divisor of feul and d_, so d_ is decremented by 1 and i is set to 1, to restart the loop.
e_ is initially set to 10. While loop checks if (e_ * d_) % feul == 1, which ensures that e_ and d_ are multiplicative inverses modulo feul. If this condition fails, e_ is incremented by 1.

This is the explanation my professor told me, but i still dont understand why keys are the same

Answer 10

for toy examples, it is possible to get identical public and private keys, but this might not be the case here...

https://crypto.stackexchange.com/questions/5937/what-happens-if-an-rsa-key-pair-has-identical-public-and-private-exponents

Answer 11

Bob_Li, that's the problem, both keys are identical

Answer 12

Your code is unaccessible. Did you make it private? Artur

Answer 13

Евгений , its public

Answer 14

Artur the link is inactive for some reason. And it doesn't show the "preview" box. Looks like something wrong with your link. Can you open the code via the link in your question?

Answer 15

The working link should look like this (some random code from Playground):
https://code.sololearn.com/W9kU4i2RtC07/