0

Problem with generating keys for RSA

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.

27th May 2023, 1:12 PM
Artur
Artur - avatar
15 ответов
+ 5
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?
27th May 2023, 2:59 PM
Tibor Santa
Tibor Santa - avatar
+ 4
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_
27th May 2023, 1:58 PM
Tibor Santa
Tibor Santa - avatar
+ 1
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).
27th May 2023, 3:23 PM
Tibor Santa
Tibor Santa - avatar
+ 1
Евгений 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.
30th May 2023, 6:05 PM
Tibor Santa
Tibor Santa - avatar
+ 1
Tibor Santa I just wanted the OP to put a little more effort into his question. But thanks anyway.
30th May 2023, 6:37 PM
Евгений
Евгений - avatar
+ 1
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?
30th May 2023, 7:19 PM
Евгений
Евгений - avatar
0
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_.
27th May 2023, 2:51 PM
Artur
Artur - avatar
0
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.
27th May 2023, 3:08 PM
Artur
Artur - avatar
0
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
27th May 2023, 3:42 PM
Artur
Artur - avatar
0
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
28th May 2023, 2:59 PM
Bob_Li
Bob_Li - avatar
0
Bob_Li, that's the problem, both keys are identical
28th May 2023, 3:49 PM
Artur
Artur - avatar
0
Your code is unaccessible. Did you make it private? Artur
30th May 2023, 11:46 AM
Евгений
Евгений - avatar
0
Евгений , its public
30th May 2023, 12:46 PM
Artur
Artur - avatar
0
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?
30th May 2023, 4:00 PM
Евгений
Евгений - avatar
0
The working link should look like this (some random code from Playground): https://code.sololearn.com/W9kU4i2RtC07/
30th May 2023, 4:01 PM
Евгений
Евгений - avatar