Re: RSA decryption exponent d (c++)

TJakobsen <TJakobsenDK@xxxxxxxxx> wrote:
According to various
sources i've used, d is calculated like this:

d = e^-1 (mod phi(n))

Anyway can anyone explain to me how i calculate d using c++ code or
just in plain easy-to-understand mathematics?

Your equation says that d should be an inverse of e modulo phi(n).

First, you need to understand what an inverse is. This is easy: a is
an inverse of b modulo n iff a times b is congruent to 1 modulo n.
For example: 3 is an inverse of 7 modulo 20 because

3*7 = 21 = 1 (mod 20).

Second, you need to understand how to calculate an inverse of a
number modulo a modulus. The hint is to use the extended Euclidian
algorithm. The basic idea is: You want to find an inverse of the
number x modulo a modulus n. If you can find integer solutions s
and t to the equation

sx + tn = 1

then it is easy to show that s is an inverse of x modulo n.

--
Kristian Gjøsteen
.

Relevant Pages

  • Re: Rabin vs. RSA/ElGamal
    ... roots for me modulo your modulus, ... But then, so is "raw RSA". ... permutation into a full-blown public-key encryption scheme. ... or cubing modulo N -- a building block, not something it makes sense to ...
    (sci.crypt)
  • Re: Is there any COBOL program for verify the SSN?
    ... Modulus 11 is NOT the same as Modulo 11. ... The Luhn algorithm or Luhn formula, also known as the "modulus 10" or "mod 10" algorithm, is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. ...
    (comp.lang.cobol)
  • Re: Summation, modulo and decimal
    ... >I'm trying to use the modulo (modulus, mod, %) to do the following: ... >The problem is that modulo is only def. ... It not worked because before it shift the ... >digit to the left the number is added to the previous value, so, I used ...
    (sci.math)
  • Re: How do I do this problem without a calculator?
    ... in response to what Chip Eastham wrote: ... You might want Euler's generalization of Fermat's Little Thm. ... to find the reduced nonnegative residue mod 22), the modulus ... would be to consider the computation modulo 2 and again ...
    (sci.math)
  • FLTMA: How to write (a,b,c) mod (a,b,c): six combinations
    ... combine three numbers in a binary operation (modulo) in all nine ... times the row vector gives the pattern above. ... Modulus is somewhat analogous to division. ...
    (sci.math)