0
$\begingroup$

So people say to choose $d$ such that $e*d=1(mod((p-1)*(q-1)))$.

However, $1\%$ anything always equals $1$. Maybe I am not understanding it correctly, but the only way to get $e \cdot d=1$ is just by doing $e^{-1}$ which leads into a very very small number $\lll 1$ because $e$ is large.

How are people getting $e$ and $d$ such that they are both large numbers?

My main confusion really just comes from that $1\%$ anything always equals $1$.

$\endgroup$
  • 2
    $\begingroup$ You appear to be conflating two notations: a mod n (no parentheses) including x = a mod n means, for positive numbers, the remainder of a divided by n, the same as the % operator in some programming languages. (For negative numbers remainder and modulo are not always the same, but in crypto we mostly don't care about negative numbers.) $a \equiv b$ (mod n) with triple-bar and parentheses means the difference $a-b$ is a multiple of n, also said as a and b are equivalent modulo n. $\endgroup$ – dave_thompson_085 Feb 3 at 9:01
5
$\begingroup$

There are no percentages, fractions, real or floating point numbers involved.

When using modular arithmetic, the "division" operation is defined differently. If you have some values $a, b$ that have been multiplied together into $ab$, what you want from division is that $\frac{ab}{b} = a$, or stated alternatively that $\frac{a}{a} = 1$.

When working with modular arithmetic, you need a different division operation than the "normal" one taught in basic math classes. This is easy to see with an example. Suppose that you have $$a=5\\b=7\\N=19\\ab \equiv 16 \bmod N$$ It is easy to see that dividing (in the traditional sense) $16$ by $7$ is not going to yield $5$.

Instead, you can multiply $16$ by $11$, which happens to be equivalent to $5$ modulo $19$. This fulfills the behavior expected of the division operation, which is what we really care about.

A value $\frac{1}{b}$ such that $\frac{ab}{b} \equiv a \bmod N$ is called a modular multiplicative inverse.

Back to the specific question

In the case of RSA, $e$ and $d$ are modular multiplicative inverses: $ed \equiv 1 \bmod \lambda(N)$.

Alternatively, you can denote $d$ by $\frac{1}{e}$ or $e^{-1}$; These are different ways of writing the same value.

A multiplicative inverse exists if the element is coprime to the modulus $N$. To actually find a modular multiplicative inverse of an element, you can use the extended euclidean algorithm.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.