1
$\begingroup$

I was looking at a way for modular exponentiation $X=A^e \mod{n}$ with negative base $A$ in order to evaluate how it needs to be changed so I can use it with my hardware acceleration unit.

The crypto library I was looking at deals with negative base $A$ (MPI) as follows:

  • Check if A was negative and if it was, remember that it was negative and invert its sign (e.g. -5 --> 5)
  • Perform the actual modular exponentiation using a specific algorithm (e.g. sliding window method) with the positively signed $A$
  • If $A$ was positive at the beginning, you're done
  • If $A$ was negative at the beginning and the exponent $e$ was odd compensate by performing $ X = n-X$

This library can work with arbitrarily large (or small) values of $A$. However my crypto core which accelerates moudular exponentiation expects the input parameters $e$ and $A \in [0 \dots n-1]$ which is why I came up with following solution:

  • At the beginning always perform $A = A \mod{n}$. This would reduce $A$ if $A \ge n$. In case $A \lt 0$ this would make $A$'s sign positive.
  • Perform the actual modular exponentiation using a specific algorithm (e.g. sliding window method) with the positively signed $A$

I think that performing the reduction at the beginning to reduce A and make its sign positive should not change the final result as $A^e \mod{n} = (A \mod{n})^e \mod{n}$. However I wanted to make sure, that I did not forget anything.

$\endgroup$
  • 1
    $\begingroup$ Yea, i edited it to $X= n - X$, which is what the crypto library is doing. $\endgroup$ – TrinityTonic Jun 29 '17 at 6:30
  • $\begingroup$ If the library is doing $X = n - x$, then it's broken (or you're looking at the modular multiplication routine, not the modular exponentiation). As written, they'd have $X^{-1} = n - X$, which is wrong, as we know $X \cdot X^{-1} = X^0 = 1$, and $X \cdot (n - X)$ is not 1 in general. What they'd need to do at this set is known as a 'modular inverse', that's certainly doable, but is considerably more complex that $X = n-x$. $\endgroup$ – poncho Aug 28 '17 at 22:57
1
$\begingroup$

For any integer $A$ we have the congruence $A \equiv A + kn \text{ mod } n$ for all integers k. This means a generic algorithm to get $A$ (where $A < 0$) into the range $[0, n)$ would be something like:

function(A):
    while(A < 0):
        A = A + n
    return A

Doing A = A % n will work in some languages as well (e.g. python) but not all languages (e.g. C).

$\endgroup$
0
$\begingroup$

Here is a way to see that the library performs correctly. Assume $A$ (seen as an integer) be negative. Define $B = (-A)^e \bmod n$. Then: \begin{align*} A^e \bmod n &= [(-1)*(-A)]^e \bmod n\\ &= (-1)^e (-A)^e \bmod n\\ &= (-1)^e B \bmod n\\ &=\begin{cases} B \bmod n = B&\text{if $e$ is even}\\ -B \bmod n = n - B & \text{if $e$ is odd}\end{cases} \end{align*}

Note that the result remains correct if $-A$ is replaced with $-A \bmod n$ since $(-A)^e \bmod n = (-A \bmod n)^e \bmod n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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