# Background for modular arithmetic function

I'm investigating this function:

$a := ((b\cdot c) \bmod k) - (b \cdot c)/k$

where $/$ indicates integer division.

Two things I've noticed:

1. It's equivalent to multiplying a·b, and then subtracting the high digits from the low digits (in a radix which divides k)
2. It's completely linear and can be inverted (that is, given a and b, determine c) in constant time.

Is there any background on this function? Does anyone discuss it, or similar functions? Does it belong to a known family? Does it have any known applications?

In short: Where can I look to find out more about it? I'm especially interested in applications for cryptography.

-
You can only determine c given a and b if $\gcd(b,k-(b*c)/k)=1$, right? (similarly for determining b given a and c only if $\gcd(c,k-(b*c)/k)=1)$ –  mikeazo Sep 15 '11 at 1:23

As discovered by D.W., this is in fact part of recommended IDEA implementation. IDEA uses $a\cdot b \bmod (2^{16}+1)$, with a special case of handling $0$ as $2^{16}$. From the Handbook of Applied Cryptography, note 7.016:

Note (implementing $ab \bmod 2^{n}+1$) Multiplication $\bmod 2^{16}+1$ may be efficiently implemented as follows, for $0 \leq a, b \leq 2^{16}$ (cf. §14.3.4). Let $c = ab = c_0·2^{32} +c_H·2^{16} +c_L$, where $c_0 \in \{ 0, 1\}$ and $0 \leq c_L, c_H < 2^{16}$. To compute $c' = c \bmod (2^{16} + 1)$, first obtain $c_L$ and $c_H$ by standard multiplication. For $a = b = 2^{16}$, note that $c_0 = 1$, $c_L = c_H = 0$, and $c' = (−1)(−1) = 1$, since $2^{16} \equiv −1 \mod (2^{16}+1)$; otherwise, $c_0 = 0$. Consequently, $c' = c_L − c_H + c_0$ if $c_L \geq c_H$, while $c' = c_L − c_H + (2^{16} + 1)$ if $c_L < c_H$ (since then $−2^{16} < c_L − c_H < 0$).

Which is exactly consistent.

This of course leaves me with some greater questions, such as how IDEA is secure with only linear operations, and where I can read more about it (there's precious little deep discussion online), but those are for a different post. One other interesting thing is that, unlike other ciphers with constant tables, it's not trivial to look at binary code and recognize IDEA. You can scan for $2^{16}+1$, but that's not as certain as for instance finding the md5 table.

-

At first glance, it doesn't look like that interesting of a function. If we define:

f(b, c) = (b*c)%k - (b*c)/k


then we always have:

f(b, c) == b*c  (mod k+1)


In other words, largely it's just an odd way of doing a modular multiplication. Of course, f(b, c) is not always (b*c) % (k+1); sometimes it is negative. At first glance, I don't see any interesting pattern to that.

-
Interesting! To give some more context, I encountered this while reverse engineering some crypto, apparently DIY. The code had special cases for when b or c is zero (return k + 1 - c [or b]), which clearly isn't multiplying. But if f was < 0, it returned k + 1 + f, which indeed fits with your hypothesis. So how do you explain the special case for zero? –  S. Robert James Sep 15 '11 at 2:13
Was it the IDEA block cipher? IDEA involves doing a multiplication modulo 2^16 + 1, but where zero is treated specially (zero is replaced with 2^16 before multiplying). This sounds consistent with your description. –  D.W. Sep 15 '11 at 2:50
Indeed, looking at it closely, it prob. is. I had assumed it must be homemade, since it uses only XOR, +, *, and % - all linear operations. No permutations, s-boxes, or other look ups. But looking at IDEA and the code, there's too many similarilities for it to be anything else. How does IDEA reach security if it is purely linear ops? –  S. Robert James Sep 15 '11 at 4:35
@S. Robert: XOR and + are linear, but not in the same space. XOR is linear in the vector space $\mathbb{Z}_2^n$ (space of vectors of 0s and 1s). Addition is linear in $\mathbb{Z}_{2^n}$ (ring of integers modulo a power of 2). Mixing them together tends to break linearity, and is a common tool in the design of ciphers and hash functions. –  Thomas Pornin Sep 15 '11 at 10:08
@S. Robert: (an addition to what Thomas commented) The multiplication modulo the prime $2^{16}+1$ (but leaving out zero) serves as non-linear layer for the IDEA. It is not linear, but only bilinear over the field $\mathbb{F}_{2^{16}+1}$ with $2^{16}+1$ elements. This means, it is linear for a fixed key, but a different permutation for each (round) key. And the linearity is now over $\mathbb{F}_{2^{16}+1}$, which is slightly, but crucially, different from linearity over $\mathbb{Z}/2^{16}\mathbb{Z}$. –  j.p. Sep 15 '11 at 12:47