高级密码学数论初步

第3部分数论初步 3 1素数 定义2 1 整除 倍数 因数 设a b为整数 例如30 2 15 3 10 5 6 2 3 5都是30的因数 30是2 3 5的倍数 若存在整数c 使b ac 则称a可整除b 记作a b b叫做a的倍数 a叫做b的因数 若不存在这样的整数c 则称a不能整除b 记作a b 我们有2 3 5分别整除30 记作分别记为 2 30 3 30 5 30 或30被2 3 5分别整除 如果a 1 则a 1 事实上 对于g b g1 g1为整数 有b g 又例如7 84 7 84 5 20 19 171 13 0 3 8 5 12 0是任何非零整数的倍数 1是任何整数的因数 任何非零整数a是其自身的倍数 由此我们可以得出这样的结论 如果a b b a 则a b 如果b 0 b则可整除0 如果b g b h 对于任何整数m和n 则满足b mg nh 对于h b h1 h1为整数 满足b h 所以有mg nh mbg1 nbh1 b mg1 nh1 所以b能整除mg nh 例b 7 g 14 h 63 m 3 n 2 7 14 7 63 必满足7 3 14 2 63 又由于 3 14 2 63 7 3 2 2 9 所以有 7 3 14 2 63 7 7 3 2 2 9 定义2 2 公约数 最大公约数 素数 互素 两两互素 设整数a b l 若有整数d满足d a d b d l 则称d为它们的公约数 公约数中最大者成为它们的最大公约数 记作 gcd a b l 如果gcd a b l 1 则说a b l互素 如果a b l中的每个数都与其它数互素 则称它们两两互素 性质2若 关于公约数有以下性质 性质1若a是b的倍数 则gcd a b b 则gcd a b gcd b c 定义2 3 素数 只有1和自身为其因数的大于1的整数叫素数 显然除2外 所有素数都是奇数 寻找素数的方法 设n是一个正整数 如果对所有素数p 根号n 都有p n 则n一定是素数 性质1若p为素数 则对任一整数a p a 或P a 性质2若p为素数 p ab 性质3素数有无穷多个 3 2同余或按模计算 定义2 5 同余 设n为一自然数 若a b为n的倍数 即 a b n 则称a与b关于模n同余 则p a或p b 记为 若a与b关于模n不同余 则记作 7 39 4 39mod7 4 性质1模n具有以下性质 1 自反性 对任一整数a 有 证 对任一正数a 我们有a a 0 n 所以有 2 对称性 如果amodn bmodn 则a b modn 证 若 则存在整数k使得 a b kn 从而有 b a k n 因此有 3 传递性 若 则 证 则分别存在整数k1 k2使得 a b k1n b c k2n 从而有a c k1 k2 n 因为k1 k2是整数 所以有 例3 3传递性例子 39 32 mod7 32 25 mod7 所以有 39 25 mod7 例3 4自反性 39 39mod7 25 25mod7 例3 5对称性 32 39 mod7 39 32 mod7 性质2若 则 根据以上性质 可得到以下两个重要的推论 推论1 若 则 定义2 6 同余类 定义2 6 完全剩余系 推论2 若 则 全体整数按照对模n的同余关系可分为n类 使得同类之数关于模n同余 不同类之数关于模n不同余 这样划分的类叫做模n同余类 整数a b模同余的充要条件是a b被n除的余数相同 全体整数对模n可划分为n个同余类 在模n的每个同余类中取出一个数作为代表构成的集合叫做模n的完全剩余系 能被n所整除其余数为0的为一个剩余类 其余数为1的为一个剩余类 余数为2的为一个剩余类 余数为n 1为一个剩余类 被分成n个不同的剩余类 这就是模n的一个完全剩余系 0 1 2 3 4 5 6 7 8 9为模10的一个完全剩余系 1 2 3 4 5 6 7 8 9 10为模10的一个完全剩余系 0 1 2 3 4 5 6 7 8 9为模10的一个完全剩余系 集合 定义3 7缩剩余系 若n为素数 则它的缩剩余系使n 1个元素的集合 定义3 8 Euler函数 显然模n的素剩余系含有 n 叫模n的绝对最小剩余系 从模n的n个同类中取出与n互素的同余类 从中各取一个代表构成的集合叫模n的缩剩余系 由于0能被任何数整除 所以它永远不会是素剩余系中的元素 设n唯一自然数 数列与n互素的个数叫n的Euler函数 记作 n 由于两个数很大 在运算时可能遇到困难 更重要的是会产生溢出 有了这个定理 使得参与运算的两个数在参与算时 各自先求一次模运算 使得在对整个取模运算时整个数据变小 从而在一定程度上解决以上问题 为此我们引出以下定理 定理3 1 按模计算原理 令a1和a2为整数 OP代表操作符 则 下面对op为 进行证明 证令 对加法 有 对于乘法 11mod8 15mod8 mod8 10mod8 2 验证 11 15 mod8 26mod8 2 11mod8 15mod8 mod8 21mod8 5 验证 11 15 mod8 165mod8 5 定理3 2对于任给证数 有 其中p1 p2 pt p1 p2 Pt ai 0 利用按模计算原理也可以用于形如 例3 791 7 13 11011 7 112 13 有了这公式 对于较高指数运算 可以将一个较复杂的运算 变为较简单的运算 下面具一个例子来说明 例2 8求 解 按最普通的算法 首先计算3的次方 然后对结果作取模运算 1 3的平方 2 再次平方 3 再乘以3 利用按模计算原理 即对每次计算的中间结果作取模运算 4 取模运算 1 3的平方 2 再次平方 3 再乘以3 对于上式指数运算作取模运算时 我们必须要小心 不能冒然作取指数运算 因为 一般不等于 但 定理3 3设n是一正整数 a1 a2 b1 b2是四个整数 如果 a1 b1 modn a2 b2 modn 则 a1 a2 b1 b2 modn a1 a2 b1 b2 modn a1 a2 b1 b2 modn 证 因为a1 b1 modn a2 b2 modn 所以存在k1 k2使得 a1 b1 k1n a2 b2 k2n a1 a2 b1 b2 k1 k2 n a1 a2 b1b2 k1b2 k2b1 k1k2n n 因为k1 k2 k1b2 k2b1 k1k2n都是整数 所以我们有 a1 a2 b1 b2 modn a1 a2 b1 b2 modn 推理2 1设n是一正整数 设a1 a2 at b1 b2 bt 如果有 a1 b1 modn a2 b2 modn at bt modn 1 a1 a2 at b1 b2 bt modn 2 a1 a2 at b1 b2 bt modn 特别 当b1 b2 bt b时 则 1 a1 a2 at tb modn 2 a1 a2 at bt modn 2 3一次同余方程 定义2 9设n位自然数 f x 为正系数多项式 且n am 其表现形式 则方程 称为关于模n的x的m次同余方程 定理2 2 素数模的同余方程解的个数 设n为素数 则同余方程 的解的个数 包括重解的重数在内 小于等于n 例x5 x 1 0mod 7 首项系数为1的模7同余式 而X 2 mod7 是该同余式的解 事实上 我们有 25 2 1 35 0 mod7 还有解x 4 mod7 所以解个数为2 在一次同余方程中我们特别感兴趣的是形如 这个方程的含义是 必存在x的值满足在modn的条件下 其余数为1 它是我们以后将上密钥体制是要经常用到 引理2 1 若gcd k n 1 则 为n的一个完全剩余系 证根据完全剩余系的定义 我们只要证明ik个属于 分别属于n的对模n的不同的同余类即可 若 而 则有 由 推出 但i j都大于0且小于n 因此是不可能的 故必有 定理2 2若gcd a n 1 则一次同余方程 有解 且有唯一的解 定义2 9 乘法逆元 令b 的解 则说在关于模n乘法运算中 a与b互逆 b是a关于模n的乘法逆元 有了乘法逆元为解方程创造一个条件 axmodn 1 例 求5关于模14的乘法逆元 的解 引理2 3若为模n的一个缩剩余系 又 则也为一个缩剩余系 证显然有 故每个kai 都属于n 的互素的同余类 我们只要证明彼此的不同 即可证明 了此引理 若 同时有 则有 或 由 k n 1得 即 这与ai aj为缩剩余系的不同元素矛盾 所以必有 即 分别属于不同的同余类 对于任一素数p 小0于p且与p互素的数正数的个数显然等于p 1 从而 下面我们将引入两个素数p和q的积的定理 定理2 3当p q为素数时 对 有 证考虑n的完全剩余系 除p 1个元素 和q 1个元素 以及0除外 其余所有元素都与n互素 因此有 下面我们将举一个例子对此定理的理解 例2 7求 解 3和5皆为素数 有定理2 3得 15的缩剩余系确有8个元素 它们是1 2 4 7 8 11 13 14 定理2 4对任意整数n 若其标准分解式为 则其Euler函数为 例2 8求 所以24的剩余系包含8个元素 它们是1 3 7 11 13 17 19 23 定理2 5 Euler定理 对任意整数k和n 若 k n 1 则 证若 为模n的一个缩剩余系 则 即 约简之后 得 当n为素数时 所以Euler定理也可以用来对 来对素数检测 若对任意 有 例2 9K 3 n 10 10 4 所以34 81 1 mod10 k 2 n 11 11 10 所以210 1024 1 mod11 定理2 5 Fermat定理 设P为素数 则对任意整数a 有 证由于p是素数 显然有 于是 当 时 由Euler定理 有 在 时 由于p为素数 必有 定理显然成立 例2 10若p 5 a 3 所以有35 243 3 mod5 若p 5 a 10 所以有105 100000 10 mod5 0 mod5 Fermat定理和Euler给出了方程 的解为 若n为素数 可进一步简化上式为 例 解 得 下面验算之 我们很容易进一步扩充此算法 以求解一般一次同余方程 若gcd a n 1 方法 第一步 求ax 1 modn 可得 第二步 求ax b modn 由 可得 所以方程的解为 定理2 7 孙子定理 又称为中国剩余定理 令nk d1d2 dk 且d1 d2 dk两两互素 则方程组 x x1 modd1 x x2 modd2 x xk moddk 在 0 n 1 内有惟一解 证对任意i 1 2 k 有 为了便于理解我们将上式写成 所以存在yi满足 令 又令 即 我们注意到dj是nk di的因子 对于i j 所以x是方程组 的解 现在我们来证明 它也是方程组在 0 n 1 内的唯一解 设x是方程组的第一个方程的解 所以可得 由于gcd 故由定理2 2知 以上方程中的k1对d2是唯一的解 于是满足第一 二个方程的x对模d1 d2也是惟一的解 设 将它代入第三个方程 仿照以上证明 又可证的k2对d3也是惟一的解既满足第一 二 三个方程的x对模d1d2d3也是惟一的解 如此类推 可以证明满足全部方程的x对模d1d2 dk是惟一解 例1 5解方程 解由于 所以 我们首先分别求解方程 的解 解出 x1 1 x2 2 然后用孙子定理求解方程 为此首相找出满足 Y1 1 y2 3 于是得到 2 4二次剩余 定义2 10 二次剩余 二次非剩余 平方根 设n为大于1的整数 a n 1 若二次同余方程 有解 则称a为对模n的二次剩余 否则 则称之为对模n的二次非剩余 满足以上方程的x成为未对模n的a的平方根 定义2 10 二次剩余系 在小于n正整数中 模n的二次剩余的集合称为二次剩余系 记作 R2 定理2 6对于任何奇素数p和任意a 0 a p方程 密码学中相关算法 在密码学中为了考虑更高级别的安全性需要密钥较长 如RSA密码体制有时需要密钥长度达到1024bit长 使得现有一般计算机无法满足对此的计算 产生溢出 造成运算结果错误 因此就有必要设计一个算法来解决运算产生溢出问题 为了解决以上问题我们主要从以下两个方面考虑 组织参与运算的数据 根据所组织参与运算的数据设计算法 1 组织参与运算的数据 假设实现运算的计算机的字长为W位 W通常是8的整数倍 通常工作站的字长为64位或32位 而低档的计算机字长w可能还小些 如某些嵌入式计算机的字长是16位 而智能卡的字长可能只有8位 设整数m的二进制长度为p t m W表示W位子的个数 显然整数m以二进制形式存储在一个t个w位字的数组A A为A t 1 A t 2 A 2 A 1 A 0 其中最右边的A 0 是存放最低的数据部分 如果两个数大数分别为m1 m2 按照以上的组合方法 将m1从高位到低位分别存放到数组A 即 A t 1 A t 2 A 2 A 1 A 0 M2从高位到低位分别存放到数组B中即 B t 1 B t 2 B 2 B 1 B 0 2 设计算法 加法 设加的结果放在数组元素C中即 C t 1 C t 2 C 2 C 1 C 0 设 用来存放进位位 执行以下算法 减法运算 步骤1 C 0 A 0 B 0 步骤2 1 C i A i B