As we have seen in the previous blogs, when implementing cryptographic schemes, one of the mostly frequently invoked operation is the modulo operation. Unfortunately, despite its massive usage modulo cannot be performed easily like some other arithmetic operations such as additions and multiplications. Montgomery representation provides one solution to this problem, and we will discuss another solution, Psudo-Mersenne Prime reduction.
Definition: A prime number $p$ is called a Psudo-Mersenne Prime if $p$ can be written in the form:
\begin{equation}
p = b^n - c
\end{equation}
where
\begin{equation}
0 < |c| < 2^{\lfloor n/2 \rfloor}
\end{equation}
Practically, $b$ is always $2$ and we pick $c$ within a word size which is usually $32$ or $64$ bits.
It can then be easily derived from its definition that
\begin{equation}
p \equiv b^n - c \equiv 0 (\mod p)\\
b^n \equiv c (\mod p)
\end{equation}
Therefore given an integer $z$ of $k$ bits, we let $z'$ be its Least Significant $n$ bits and $z''$ its Most Significant $k-n$ bits, i.e. $z = z''2^n + z'$, we can then rewrite $z \mod p$ as:
\begin{equation}
z \equiv z''b^n + z' \equiv z''c + z' (\mod p)
\end{equation}
The modulo of $z$ can then be computed by recursively apply this until it yields in $\mathbb{Z}_p$.
There are several points might worth mentioned here:
- Both $z'$ and $z''$ can be computed efficiently by simply shifting $z$.
- Since $c$ is picked within a word size, the multiplication can be done very efficiently.
- Each iteration shrinks the left hand side $k$ bits to the right hand side $max(k-n+w, n)$ bits where $w$ is the word size.
Nevertheless, drawback of using such method is also obvious as such implementation will usually requires multiple parties to use a fixed setup which will potentially results into both interoperability and security problems.
More details about this solution can be found in [1] and [2].
$GF(2^n)$ is another filed of common usage in cryptography. Trinomial and pentanomial are the mostly used modular in this scenario. We will show how trinomial simplifies the reduction. Same technique can be applied to pentanomial straight forward.
The idea is very similar to the prime field one. Presume we have the trinomial modulo $f(x)$ such that
\begin{equation}
f(x) = x^n + x^t + 1
\end{equation}
where $0 < t < n/2$.
We immediately have
\begin{equation}
x^n \equiv x^t + 1 (\mod f(x))
\end{equation}
Given a polynomial $z(x)$ with degree greater to $n$, we rewrite $z(x)$ as
\begin{equation}
z(x) = z''(x) x^n + z'(x)
\end{equation}
where $z'(x)$ is the polynomial represented by the Least Significant $n-1$ bits of $z(x)$ and $z''(x)$ the others.
Then just like what we have done on $GF(p)$, we compute the modular by
\begin{equation}
z(x) = z''(x) x^n + z'(x) \equiv z''(x) (x^t + 1) + z'(x)\\
\equiv z''(x) x^t + z''(x) + z'(x) (\mod f(x))
\end{equation}
This can be done very efficiently as $t$ is a "small" number.
[2] also described another optimization to the standard reduction. Consider during a standard procedure of reducing $z(x)$ of degree $m$ to $f(x)$ of degree $n$:
\begin{equation}
z(x) = a_m x^m + a_{m-1} x^{m-1} + ... a_1 x^1 + a_0 x^0\\
f(x) = x^n + x^t + 1
\end{equation}
When we try to reduce $a_ix^{i}$, there are two cases:
- If $a_{i} = 0$, then nothing will be changed to the remainder, or
- If $a_{i} = 1$, then $1$ will be added to the bits aligned to $x^t$ and $1$ in $f(x)$, namely $a_{i - n + t}$ and $a_{i-n}$.
INPUT: $z(x)$
OUTPUT: $z(x)$
1. for $i = m$ to $n$ by $-1$
2. {
3. $a_{i - n + t} += a_i$
4. $a_{i - n} += a_i$
5. }
6. return $z(x)$
The advantage of using such algorithm does not seem obvious from a software perspective; however, it can be implemented very efficiently by hardware as it simply updates $z(x)$ and requires no extra storage.
Another advantage is that such code requires only $0 < t < n$ and can be executed in a constant time.
[1]Menezes, Alfred J., Paul C. Van Oorschot, and Scott A. Vanstone. Handbook of applied cryptography. CRC press, 1996.
[2]Blake, Ian F., Gadiel Seroussi, and Nigel Smart. Elliptic curves in cryptography. Vol. 265. Cambridge university press, 1999.
No comments:
Post a Comment