密码学相关的一些代数

Posted by rk700 on March 14, 2016

CTF比赛中遇到许多密码学的题目,往往最后都转化为相关的代数问题。因此,在这里就经常会用到的一些概念进行归纳总结。

原根(primitive root)

什么是原根

是模 的原根,如果所有与 互素的数,均与 的某个幂模 同余。换句话说,对于所有与 互素的 ,存在 使得

原根存在性

对于一般的 ,原根是不一定存在的。比如说,模8就不存在原根。但如果是模素数 ,那么原根即generator是存在的。

原根的个数

如果原根存在,那么其个数为 。这是因为,与 互素的数共 个,其构成的群如果有generator,那么其个数为

特别地,由于 ,因此模 有限域存在 个原根。

如何计算原根

并不存在快速计算原根的通用公式。如果使用PARI/GP,则可以通过如下命令:

znprimroot(n)

以下,将介绍同余意义下的平方根、立方根。

平方根

存在性

对于一般的 , 不一定存在 ,使得 。举例来说, 便不存在平方根。

唯一性

假设存在 的平方根,那么可能不止一个平方根。比如, 有平方根 ,而 便只有一个平方根 。再比如, 有4个平方根: , , ,

事实上, ,这是因为:

特别地,对于模 来说,除了以上性质,我们还知道,其平方根总是成对出现的。假设 ,那么 。而 为素数,必有 互素。因此, 。又因为 ,因此必有

此外,由于平方根至少是成对出现,因此所有可能的平方的总数是小于 的,这也说明了平方根不一定存在。

如何计算平方根

使用PARI/GP,可以计算模 的平方根如下:

sqrt(Mod(4,7))

当计算得到一个平方根 后,另一个则为

在RSA中,有时公钥会取3。当然实际没遇到过,只是在题目中见过。下面,将讨论计算模 立方根的相关问题。

立方根

存在性

与平方根类似,立方根也不总是存在的。比如, 便不存在立方根。

唯一性

在此,首先介绍另一个概念:root of unity modulo n. 顾名思义,k-th root of unity modulo n 指的便是 使得 . 当然,1便是满足条件的,但是非平凡的则不一定存在。如 便不存在除了其本身以外的立方根。

现在,假设k-th root of unity modulo p是存在的,其值为 。如果我们已经知道了 的一个 次根为 ,那么:

也为 的一个 次根。这便给出了一种由一个根求其他根的思路。

回到立方根,即 的情况,此时仍然假设 的立方根。

首先,如果 不是3的倍数,即3与 互素,那么3对于模 的逆是存在的,即存在 使得 。那么,根据费马小定理可知:

于是,类似于RSA解密的过程,此时可直接计算出 的立方根 ,而且此立方根是唯一的。

接下来,如果 是3的倍数,那么立方根若存在则有3个。为此,我们首先证明, 此时 的立方根有3个:

由于模 是存在原根的,假设为 。那么根据定义,存在 使得 。这里 是我们要计算的 的立方根。由此可知:

而由费马小定理和原根的性质可知,满足 的所有 ,必然是 的倍数,即 的倍数。那么 可以取的值便是0, 这3种,而 是3的倍数保证了这样的 是整数。由此可知, 的立方根为1, , ,其中

现在,假设 的两个不同的立方根。由于模 是域,逆是存在的,所以 存在且为 的立方根。我们已知 的立方根共3个,所以 的立方根也是3个。

如何计算立方根

从前述的证明便可知,如果 不是3的倍数,那么直接通过费马小定理便可计算出唯一的立方根;如果 是3的倍数,那么首先找到一个立方根,其他的立方根可通过乘以 的立方根得到。

对于PARI/GP来说,我们使用以下命令:

r=sqrtn(Mod(6,7),3,&z)

这里得到的 便是一个符合条件的立方根,而 则是 的立方根。全部的3个立方根就是 , ,

此外,我们还可通过PARI的有限域多项式分解求出全部的立方根:

? factor(x^3-Mod(6,7))

[Mod(1, 7)*x + Mod(1, 7) 1]

[Mod(1, 7)*x + Mod(2, 7) 1]

[Mod(1, 7)*x + Mod(4, 7) 1]

上述结果中的 , , 便为 的3个立方根。