Precision mod calculations

Factual Questions
#1

The thread about the precision of the Windows calculator prompted this question. (BTW, just in case not everyone knows, you can click on view and choose scientific or standard.)

How can I calculate y[sup]B[/sup]mod§? Any but the very smallest numbers will overflow a calculator or spreadsheet.

The DHM key exchange and other encryption operations rely on exponentiation and modulus operations. I have found even in the most basic example you run into huge numbers which cannot be handled by the calculator or spreadsheets. Can any one tell me how they could be done?

Fer instance, suppose another person and I want to do a DHM key exchange. How can we do it? Here is an explanation of the key exchange, I need the capacity to perform the calculations.

The key exchange relies on the commutative property of the function:
(y[sup]B[/sup]mod§)[sup]A[/sup]mod§ = (y[sup]A[/sup]mod§)[sup]B[/sup]mod§

Let us say y=11 and p=13

I think of a number A and perform y[sup]A[/sup]mod§
you think of a number B and perform y[sup]B[/sup]mod§
we exchange the results publically
Now I can do (y[sup]B[/sup]mod§)[sup]A[/sup]mod§ and you can do (y[sup]A[/sup]mod§)[sup]B[/sup]mod§. We both end up with the same number but, although we traded the information publicly, no one knows what number we ended up with.

So much for the theory. How can it be done in practice?

#2

I looked at your problem and I really don’t know much about mod I tried it in my good friend Maple. It gave me some answer for 11^b mod 13 in under a second. Still I didn’t understand it so I looked at the help file. This has to be the most cryptic help file I have EVER seen… take a look

mod, modp, mods - computation over the integers modulo m
Calling Sequence:
e mod m
modp(e, m)
mods(e, m)
mod(e, m)
Parameters:
e - an algebraic expression
m - a nonzero integer
Description:
The mod operator evaluates the expression e over the integers modulo m. It incorporates facilities for doing finite field arithmetic and polynomial and matrix arithmetic over finite fields, including factorization.
The operator syntax e mod m is equivalent to the function call mod(e,m). The environment variable mod may be assigned either the modp function or the mods function. When assigned the value modp (the default), the positive representation for integers modulo m is used; i.e. all rational coefficients will be reduced to integers in the range [0,abs(m)-1]. When assigned the value mods, the symmetric representation is used; i.e. all rational coefficients will be reduced to integers in the range [-iquo(abs(m)-1,2), iquo(abs(m),2)].
If the modulus m is a prime integer, then all coefficient arithmetic is done in the finite field of integers modulo m. Elements of finite fields of characteristic m with q = m^n elements are represented as polynomials in alpha where alpha is a simple algebraic extension over the integers mod m. The extension alpha is a RootOf a monic univariate irreducible polynomial of degree n over the integers mod m. See RootOf and the examples below.
The following functions for polynomial and matrix arithmetic over finite rings and fields are known to mod.

To compute i^n mod m where i is an integer, it is undesirable to use this ``obvious’’ syntax because the powering will be performed first over the integers (possibly resulting in a very large integer) before reduction modulo m. Rather, the inert operator &^ should be used: i &^ n mod m. In the latter form, the powering will be performed intelligently by the mod operation. Similarly Powmod(a,n,b,x) mod m computes Rem(a^n,b,x) mod m (where a and b are polynomials in x) without first computing a^n mod m.
Other modular arithmetic operations are stated in their natural form:
i+j mod m; i-j mod m; i*j mod m;
j^(-1) mod m; i/j mod m;

where the latter case will perform i*j^(-1) modulo m.
The left precedence of the mod operator is lower than (less binding strength than) the other arithmetic operators. Its right precedence is immediately higher than +, - and lower than *, / .
There is an interface for user-defined mod functions. For example, if the user has defined the procedure mod/f then the operation f(x,y) mod 23 will generate the function call mod/f(x,y,23).
The mod operator is mapped automatically onto equations, the coefficients of polynomials, and the entries of lists and sets.
Because mod is an environment variable, any assignments to it inside a procedure body are undone on exit from the procedure.

Examples:

modp(12,7);

                              5

12 mod 7;

                              5

mods(12,7);

                              -2

1/3 mod 7;

                              5

5*3 mod 7;

                              1

5 &^ 1000 mod 100;

                              25

a := 15x^2+4x-3 mod 11;

                             2
                     a := 4 x  + 4 x + 8

mod := mods:
> b := 3x^2+8x+9 mod 11;

                             2
                     b := 3 x  - 3 x - 2

> gcd(a,b);

                              1

> g := Gcd(a,b) mod 11;

                          g := x + 5

> Divide(a,g,‘q’) mod 11;

                             true

> q;

                           4 x - 5

> factor(x^3+2);

                             3
                            x  + 2

> Factor(x^3+2) mod 5;

                              2
                    (x - 2) (x  + 2 x - 1)

> alias(alpha=RootOf(y^2+2*y-1)):
> Normal(1/alpha) mod 5;

                          alpha + 2

> Factor(x^3+2,alpha) mod 5;

             (x + alpha + 2) (x - alpha) (x - 2)

> Expand(%) mod 5;

                             3
                            x  + 2
#3

You can indeed compute y[sup]b[/sup] (mod p) for pretty large y, b, and p without resorting to bignum-style arithmetic. It takes some arcane trickery involving the Chinese Remainder Theorem and the Euler Totient function. Basically what you do is:

  1. factor p
  2. compute the Euler totient function phi(n) for each factor of p, and find the least common multiple of these–call it m.
  3. you now know that y[sup]m[/sup]==1 (mod p), so find the remainder of b divided by m–call it r.
  4. y[sup]b[/sup]==y[sup]r[/sup] (mod p) so now you calculate y[sup]r[/sup] (mod p), which will be much easier.

Here’s the example from my textbook (A Course in Number Theory and Cryptography, Neal Koblitz 1987):
Compute 2[sup]1000000[/sup] mod 77.
phi(7)==6 and phi(11)==10, and their l.c.m. is 30, so 2[sup]30[/sup]==1 mod 77. 1000000==30*33333+10, so 2[sup]1000000[/sup]==2[sup]10[/sup]==23 mod 77.

I hope that made sense.

#4

I really wish you’d waited a few days until I added that functionality to my Euclidian Algorithm program.

*rest of explanation clipped since Bobort did it better and used the sub scripting that I didn’t have patience with

#5

I should mention that there are other ways to do this, and the one I presented is the one I happen to be most familiar with. Some of the other ways are probably easier.

#6

I can’t believe I got several informative responses so fast!! I thought the subject was so obscure the thread would sink like a stone without a single reply. Thanks guys. You have given me enough to keep me busy for quite a while. the Chinese Remainder Theorem and the Euler Totient function?? Yes, busy indeed. Too bad it’s not as simple as plugging the numbers into the calculator.

#7

Well, the Euler totient function is the number of values less than the argument that are relatively prime to it. Since, with the Diffie-Hellman key-exchange, p is prime, that means that its factorization gives 1 factor, p, and phi§ = p-1. Assuming that b < p, then b <= p-1, so unless b == p-1, b % p-1 = b. So you’re still left with calculating y[sup]b[/sup]mod§. This is a good thing. If it were possible to reduce the search space for powers of y mod§, it would require making p much larger.

Under these conditions, I believe the best way is to calculate the powers of y mod§ to the powers of two which are less than or equal to b. Then, using b as a bitstring where bit 0 is the flag for y[sup]2[sup]1[/sup][/sup]mod§, bit 1 is the flag for y[sup]2[sup]2[/sup][/sup]mod§, etc., multiply the flagged powers together mod p.

The following pseudocode works on bc, the infinite-precision calculator available for free from the GNU project:



scale=0; /* Needed for % and / operators, just in case. */
/*
 * modpow:  returns y^b mod p
 */
define modpow(y,b,p) {
  auto current, value, i;
  current = y % p;
  value = 1;
  for(i = b; i > 0; i /= 2) {
    if (i % 2) {
      value = (value * current) % p;
    }
    current = (current * current) % p;
  }
  return(value);
}

It is important that y, b, and p be at most half of the maximum precision. So, if you are using unsigned 32-bit arithmetic, make sure they are less than 2[sup]16[/sup]. Otherwise, the expressions (value * current) or (current * current) might overflow. Note that this is only useful for showing examples, as decent security in the near future would have p on the order of 2048 bits.

#8

To be classed as a Precision Mod, your beatle boots must have heels at least one inch high and toes that come to a point at no more than a 43 degree angle, the bangs of your moptop may extend no more than 4mm below your eyebrows, and your turtleneck must reach to the height of the exact center of your adam’s apple while you are looking straight ahead. Oh, and your Vespa has to be a '69, medium white.

#9

Actually I was hoping for some program where I could plug in the numbers and get the results. I guess I will consider this an opportunity to expand my knowledge in this direction. Thanks again. I am pleasantly surprised by the responses.

#10

Sailor, do you have access to a Unix machine? If so, bc is already on it, so just put the wrapper below around the function above.



#!/bin/sh

if test $# -lt 3
then
 echo "Not enough arguments."
 exit -1
elif test $# -gt 3
then
 echo "Extra arguments after $1 $2 $3 ignored."
fi

echo "Calculating $1^$2 % $3."

bc <<END_OF_SCRIPT
#Put function here
modpow($1, $2, $3)
END_OF_SCRIPT

exit 0
#11

Nope, sorry, just my lowly pea see. Any way it could be done with VB or something?