基于模二次剩余的对称与非对称加密算法

首先介绍有关模二次剩余的相关数论基础。然后介绍了BBS伪随机数发生器的构造以及使用BBS PRNG的对称机密系统。此外介绍因数分解假设以外的另一种假设——二次剩余假设在公钥密码系统的应用,即Rabin算法。

二次剩余的数论基础

二次剩余的定义

QR_n \coloneqq {x \in Z_n^* \ | \ \exists y \in Z_n^*: y^2 \equiv x \ \ mod \ n}

给定模n乘法群,如果对于x \in Z_n^*,存在群元素y满足y^2 = x,则x是一个二次剩余,此时y是x的一个根。QR_n是模n二次剩余的集合。

一个元素不是二次剩余就是二次非剩余,集合记作QNR_n

QR_n乘法群

对于QR_n的元素x_1x_2有以下性质:

  • x_1 \cdot x_2 \in QR_n

    两个群元相乘结果仍在群中

  • x_1^{-1} \in QR_n

    存在逆元

素数模二次剩余Z_p^*

当p>2且为素数时,Z_p^*中每个二次剩余都有两个平方根。因此平方取模的函数具有“二对一”的映射关系,这意味着Z_p*中恰好有一半的元素为二次剩余,也即|QR_p| = \frac{p-1}{2}

讲义上给出的是Z_p域,有小于等于2个根。

x \not\equiv 0, p \ne 2时,有0或2个根。

Jacobi符号

设p>2且为素数,x \in Z_p^*,Jacobi符号定义为:

\Bigl(\frac{x}{p}\Bigr) \coloneqq \begin{cases}
    1 &\text{if } x \in QR_p\\
    -1 &\text{else}
\end{cases}

实际上还有一个符号称为Legendre符号,要求模数必须为奇素数。而Jacobi符号的模数可以是任何正整数。所以Jacobi符号是Legendre符号的推广,当模数为奇素数时,Jacobi符号等于Legendre符号。

欧拉准则 Euler Criterion(模p二次剩余的判断)

\Bigl(\frac{x}{p}\Bigr) \equiv x^{\frac{p-1}{2}} mod p

欧拉准则用于判断x是否是素数p的二次剩余

继续阅读“基于模二次剩余的对称与非对称加密算法”