0

I’ve encountered what might be a problem. I calculate all the values p, q, Phi, N, e, d, and when I go to check if e*d=1mod(p-1)(q-1) instead of getting 1 I get .999999327… or another extremely long decimal that’s close to 1. Is this due to an incorrect step or maybe because I do not use 512 bit long numbers, but rather short ones? Also I used d=(1/e)mod(phi).

Jeff Holt
  • 2,940
  • 3
  • 22
  • 29
Dylan
  • 21
  • "Short" numbers are fine, and in principle you can *carefully* use JavaScript's `Number` type (cursed as it is), but this looks like you accidentally did some floating point operations. Can you show any code? Can you use the `BigInt` type? – harold Mar 22 '22 at 01:35
  • 1
    Just show an example of one variable whose value, when emitted, is not what you expect. Minimal, complete examples, please. – Jeff Holt Mar 22 '22 at 01:36
  • 4
    Likely duplicate of [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) – esqew Mar 22 '22 at 01:36
  • 2
    @esqew I don't think that's a good duplicate for this question, because this question is about modular arithmetic really (not covered by that QA), not so much about floating point arithmetic being strange. All that QA comes down is "yes, floats are weird, accept it", but for the purpose of this question that doesn't even matter because it is simply incorrect to use floating point arithmetic in this context to begin with. – harold Mar 22 '22 at 01:41
  • 5
    In modular arithmetic "division" uses a different algorithm than the usual division of real numbers you are used to, so you cannot compute `d = 1/e mod phi` using the javascript `/` operator. Instead, you should use a variant of something called the extended euclidean algorithm to compute a [modular inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse). – President James K. Polk Mar 22 '22 at 02:01
  • my p and q generate random prime numbers anywhere between 100 and 1000 (I know thats very low but gotta start somewhere), to which I generate N = p*q and QN(Phi) = (p-1)(q-1) and then this is the code i use to get e and d. var e = randomNumber(1, QN); for (var i = 2; i < e; i++) { if (e%i == 0) { e = randomNumber(1, QN); i = 2; } } var d = (1/e)%QN; "%" is the same thing as MOD in this program I take these digits and check d with de mod Phi(N) = 1 but instead of 1 I get this really long integer – Dylan Mar 22 '22 at 22:32
  • also could the problem be my d variables? they look like this 0.0000067568937208186655 – Dylan Mar 22 '22 at 22:39
  • None of your values should look like floating point numbers. Everything in RSA is an non-negative integer. – harold Mar 23 '22 at 00:51
  • Made some changes to the d formula and it works now – Dylan Mar 24 '22 at 01:06

0 Answers0