logo资料库

中国剩余定理在RSA解密中的应用.pdf

第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页,全文预览结束
2 河  北  省  科  学  院  学  报 the Hebei Academy of Sciences Journal of V ol . 20 No. 3 A ug. 2003 Ξ 第 20 卷 第 3 期 2003 年 8 月 文章编号 :1001 - 9383 (2003) 03 - 0138 - 06 中国剩余定理在 RSA 解密中的应用 贺毅朝1 ,刘建芹2 ,陈维海3 (1 石家庄经济管理学院信息工程系 ,石家庄  050000 ; 2 石家庄信息工程职业学院 ,石家庄  050035 3. 中国华融资产管理公司石家庄办事处 , 石家庄 050000) 【摘  要】 在分析 RSA 密码算法实现原理的基础上 ,着重论述了利用单基数转换法 ( SRC) 和混合基数转换法 (MRC) 计算中国剩余定理惟一解的方法以及利用这两种方法快速实现 RSA 的解密算法 。 【关键词】 P KC 算法 ; 中国剩余定理 ; RSA 算法 【中图分类号】 TP 311. 56 ;O156    【文献标识码】 A The application of CRT to RSA decryption HE Yi chao1 ,LIU Jian qin2 ,CHEN Wei hai3 ( 1 . College of I nf orm ation Engi neeri ng , S hijiaz huang U niversity of Econnomics , S hijiaz huang 050000 , Chi na ; 2 . S hijiaz huang I nf orm ation Engi neeri ng V ocational College , S hijiaz huang 050035 , Chi na ; 3 . S hijiaz huang Of f ice of Chi na Huarong Assets M anagements Corporation , S hijiaz huang 050000 , Chi na) Radix Conversion (SRC) and Mixed Abstract  Based on analysis of t he principle of RSA implementation ,t he application issues of Sin Radix Conversion (MRC) algorit hms on Chinese Remain gle der Theorem (CR T) and high speed realization of RSA decryption using above met hods were illu minated emphatically. Keywords  P KC algorit hm ; Chinese Remainder Theorem (CR T) ; RSA algorit hm way Trapdoor Function) 的公开密钥密码算法 ( Public 1978 年美国麻省理工学院的三位教授 R. L . Rivest ,A. Shamir 和 M. Adleman 提出了一种以基于因子分解 的指数函数作为单向陷门函数 [ 1 ] (One Key Cryptosystem , P KC) ,即著名的 RSA 算法 [ 2 ] 。RSA 算法是第一个较完善的 P KC 算法 ,也是非常容易理解和实现的 P KC 算 法 。它既可用于对传输信息的加密 ,也可用于数字签名系统 ,是当前民用与商业中使用最广泛的公开密钥密 码算法之一 ,已被国际标准化组织 ISO 、ITU 和 SWIFT 接受为标准 。RSA 的安全性是基于分解大数的难度 , 该算法在经受了多年深入的密码分析之后 ,虽然密码分析者既不能证明同时也不能否定其安全性 ,但这恰恰 说明了 RSA 算法的可信度 。因此 ,可以毫不怀疑地断言 :RSA 是安全的 P KC 算法 。 中国剩余定理 (又称孙子定理) 是数论中的基本定理 ,但在计算机密码学中有着重要的应用 。例如在 Ra bin 密码算法中用于解密运算 。在 RSA 密码算法中 ,中国剩余定理同样可用 RSA 的解密运算 ,而且使 RSA 的 解密速度大约提高 4 倍左右 ,这无论对于软件还是硬件实现 RSA 密码算法都是非常重要的 。 收稿日期 :2003 - 03 - 07 作者简介 :贺毅朝 (1969 - ) ,男 ,硕士 ,讲师 ,主要从事计算机密码学和算法分析与设计研究
2 2 3 931 2 < 3 < <  第 3 期        贺毅朝等 :中国剩余定理在 RSA 解密中的应用 1  RSA 密码算法 随机选取两个不同的大素数 p 和 q (约为 150 位或更大的十进制数) ,计算它们的乘积 N = pq 与相应的 ( N ) 、p 与 q 保密 ;显然 ,如 ( N ) = ( p - 1) ( q - 1) 的值 ,将 N 公开 ,而将 Euler 函数 ( Euler Totient Function) 果在不知道 N 的素因子 p 与 q 的前提下 ,计算 ( N ) 的值是属于 NP 问题 ,极难实现 。 ( N ) ) = 1 (即 e 与 ( N ) 且 GCD ( e , 再随机选取一个正整数 e ,使 e 满足条件 : e < ( N ) 的最大公因数是 ( N ) ) , 即计算满足 ed ≡1 ( N ) ) 的 d 。将 e 公开 ,而将 d 保密 ,就确定了 RSA 算法的公开密钥 P K = ( e , N ) ,私人密钥 S K = ( d , 1) ,根据扩展 Euclid 算法 ( Extended Euclidean Algorithm) [ 3 ] 计算 d = e - 1 ( mod (mod N ) ,密钥空间 : K = { ( N , p , q , e , d) | N = pq , p 与 q 为不同大素数 , ed ≡1 (mod 相应地 , RSA 算法中的单向陷门函数为 f ( x ) = x t ( mod N ) (其中 t ∈ K 且 x ∈ZN ) ,称为 RSA 函数 。其 ( N ) ) } 。 秘密陷门信息为 ( N ) 及素数 p 、q 的值 。 确定公钥 P K = ( e , N ) 和私钥 S K = ( d , N ) 之后 , RSA 算法的加密运算定义为 : c = Epk ( m) = me (mod N ) ,其中 1 ≤m ≤N - 1 为明文 。 解密运算定义为 : m = Dsk ( c) = cd (mod N ) ,其中 1 ≤c ≤N - 1 为密文 。 RSA 密码算法的明文 m 应为 1 到 N - 1 之间的整数 ,即 m ∈[1 , N - 1 ] 。如果明文 m 太长 ,可将其转换 成 N 进制的形式 ,即 m = msNs + ms - 1 Ns - 1 + …+ m 1 N + m 0 ,于是得到分组后的明文序列 m = ( m 0 , m 1 , …, ms) ,其中 m i ∈[1 , N - 1 ] ,0 ≤i ≤s 。与之相应的密文序列为 c ( c0 , c1 , …, cs) ,其中 c1 对应于 m 1 (0 ≤i ≤s) 。 ( N ) 且与 ( N ) = ( p - 1) ( q - 1) 的值 ; 综上所述 , RSA 密码算法的实现步骤为 : 算法 1  RSA 密码算法 (1) 随机选择两个不同的秘密大素数 p 与 q ; (2) 分别计算 N = pq 和 (3) 选择一个小于 (4) 计算 e 的乘法逆元 d = e - 1 (mod (5) 利用数制转换将明文分组 ,使每组中明文 m 的取值范围在 1 至 N - 1 之间 ; (6) 执行加密运算 c = Epk ( m) = me (mod N ) ,将明文 m 加密成密文 c ; (7) 执行解密运算 m = Dsk ( c) = cd (mod N ) ,将密文 c 恢复成明文 m 。 RSA 密码算法的正确性是基于下述数论定理 : 定理 1  ( Euler′s Theorem) [3 ,4 ,5 ]对任意的 a ∈Z ( N ) 互素的正整数 e ,定义 P K = ( e , N ) ; ( N ) ) ,并定义 S K = ( d , N ) ; N 有 : a ( N) ≡1 (mod N ) ,其中 ( N ) 为 Euler 函数 , Z N = { x ∈ZN| GCD ( x , N ) = 1} 。 由 RSA 算法可知 : ed ≡1 (mod ( N ) ) ,因此必定存在非负整数 k , 使得等式 : ed = k ( N ) + 1 成立 , 这样 对于明文 m ∈[1 , N - 1 ] ,应用定理 1 有 :   Dsk ( Epk ( m) ) = Dsk ( c) = cd (mod N ) = ( Epk ( m) ) d = ( me) d (mod N ) = med (mod N ) = m k ( N) + 1 (mod N ) = m ( m ( N) ) k (mod N ) = m 1 (mod N ) = m . 同理可证 Epk ( Dsk ( m) ) = m ,因此 Esk ( Dpk ( m) ) = Dpk ( Esk ( m ) ) = m , 这说明无论用于加密还是数字签 名 , RSA 都是正确的 。 2  中国剩余定理 中国剩余定理 (Chinese Remainder Theorem ,CR T) 是初等数论中重要的基本定理之一 ,它主要是刻画剩余 系的结构和求解形如 x ≡di (mod pi) (1 ≤i ≤s) 的一次同余式方程组 。在计算数论中 ,计算中国剩余定理惟 一解的方法有两种 :单基数转换法 ( Single Radex Conver Radex Conversion , SRC) 和混合基数转换法 ( Mixed
041 河北省科学院学报           2003 年第 20 卷   sion ,MRC) ,这两种方法都是非常实用的计算方法 。 定理 2  (CR T) [ 3 ,4 ,5 ]设 p1 , p2 , …, ps 是两两互素的正整数 , 即 GCD ( pi , pj ) = 1 ( i ≠j) , 对于任意整数 d1 , d2 , …, ds (0 ≤di ≤pi - 1 , i = 1 ,2 , …, s) ,同余式方程组      x ≡d1 (mod p1) x ≡d2 (mod p2) …… x ≡ds (mod ps) 有惟一解 。 (2. 1) 利用单基数转换法 ( SRC) 计算 CR T 惟一解是较常用的方法 ,在一般的数论文献中均有详细地论证 ,因此 不再过多的叙述 ,仅给出其算法描述形式 。 算法 2  CR T 的单基数转换法 (SRC) [ 4 ,5 ] 。 (1) 计算 P ←p1 p2 …ps 和 Pi ←P/ pi (1 ≤i ≤s) ; (2) 计算 Q1 ←P - 1 (3) 计算惟一解 x ←d1 P1 Q1 + d2 P2 Q2 + …+ ds PsQs (mod P) 。 利用混合基数转换法 ( MRC) 求 CR T 惟一解的方法是 H. L . Garner 在 1958 年首先提出的 。之后 ,D. E. (mod pi) , (1 ≤i ≤s) ; 1 Kunth 将其用于计算数论 ,并进行了有益的改进 。经 Kunth 改进后的 MRC 方法用算法描述如下 : 算法 3  CR T 的混合基数转换法 (MRC) [ 3 ] 。 (1) 计算 Bji ←p - 1 (2) 分别计算 v1 ←d1 (mod p1) ; (mod pi) , (1 ≤j < i ≤s) ; j v2 ←( d2 - v1) B 12 (mod p2) ; …… vs ←( ds - ( v1 + p1 ( v2 + p2 ( v3 + …+ ps - 2 vs - 1) …) ) ) B 1 sB 2 s …B ( s - 1) s (mod ps) . (3) 计算惟一解 X ←vs ps - 1 …p2 p1 + …+ v3 p2 p1 + v2 p1 + v1 。 在上述算法的第 (2) 步中 ,感觉上计算 v1 , v2 , …, vs 的过程好象比较杂乱 ,不容易实现 。其实不然 ,深入 分析各式 ,发现其中隐含着递归成分 ,很容易利用递归公式完成相应计算 。事实上 ,不 妨 设 ai1 = di (mod pi) (1 ≤i ≤s) ,构造递归公式     ai ( j + 1) = ( aij - ajj) B ji (mod pj) , 其中 1 ≤j < i ≤s ,并利用等式 pjB ji ≡1 (mod pi) (1 ≤j < i ≤s) ,将会得到 :   a11 = d1 (mod p1) = v1 ;   a21 = d2 (mod p2) ,  a22 = ( a21 - a11) B 12  (mod p2) = ( d2 - v1) B 12  (mod p2) = v2 ;   a31 = d3 (mod p3) ,  a32 = ( a31 - a11) B 13  (mod p3) = ( d3 - v1) B 13  (mod p3) ,   a33 = ( a32 - a22) B 23 (mod p3) = ( ( d3 - v1) B 13 - v2) B 23  (mod p3) = ( d3 B 13 - v1 B 13 - v2 p1 B 13) B 23  (mod p3) = ( d3 - ( v1 + p1 v2) ) B 13 B 23   (mod p3) = v3 ;  ………………   as1 = ds (mod ps) ,  as2 = ( as1 - a11) B 1 s  (mod ps) = ( ds - v1) B 1 s   (mod ps) , ……,   ass = ( as ( s - 1) - a ( s - 1) ( s - 1) ) B ( s - 1) s   (mod ps) = ( as ( s - 1) - v ( s - 1) ) B ( s - 1) s  (mod ps) = ( ( as ( s - 2) - a ( s - 2) ( s - 2) ) B ( s - 2) s - v ( s - 1) ) B ( s - 1) s   (mod ps) = ( ( as ( s - 2) - v ( s - 2) ( s - 2) ) B ( s - 2) s - v ( s - 1) p ( s - 2) B ( s - 2) s) B ( s - 1) s  (mod ps) = ( as ( s - 2) - ( v ( s - 2) ( s - 2) + p ( s - 2) v ( s - 1) ) ) B ( s - 2) s) B ( s - 1) s   (mod ps) = ( ( as ( s - 3) - a ( s - 3) ( s - 3) ) B ( s - 3) s - ( v ( s - 2) ( s - 2) + p ( s - 2) v ( s - 1) ) ) B ( s - 2) sB ( s - 1) s  (mod ps)
1  第 3 期        贺毅朝等 :中国剩余定理在 RSA 解密中的应用 = ……………… = ( ds - ( v1 + p1 ( v2 + p2 ( v3 + …+ ps - 2 vs - 1) …) ) ) B 1 sB 2 s …B ( s - 1) s  (mod ps) = vss 。 这样 ,通过递归计算得到一个如下的三角形数值表 。     a11     a21  a22     a31  a32  a33     ………………     as1  as2  as3  … ass    利用此表可将算法 3 改进为如下算法 (Modified Mi xed Radix Conversion ,MMRC) 。 141 算法 4  改进的 MRC 算法 (MMRC) 。 (1) 计算 B ji ←p - 1 (2) 令 ai1 = di (1 ≤i ≤s) ,由递归公式 ai ( j + 1) = ( aij - ajj) B ji ( mod pi) , 1 ≤j < i ≤s 。计算出三角形数值 (mod pi) , (1 ≤j < i ≤s) ; j 表斜边上的数值 (即 a11 , a22 , …, ass) ; (3) 计算惟一解 x ←a11 + a22 p1 + a33 p1 p2 + …+ ass p1 p2 p3 …ps 。 4  利用 CR T 的 RSA 解密 利用中国剩余定理对 RSA 密码解密 ,首先要将 RSA 的解密运算由计算模 N 的指数形式转化为求解同余 方程组的情形 。为此 ,先介绍两个必需的数论定理 :即中国剩余定理的一个推论 (定理 3) 与费马小定理 ( Fer mat′s Little Theorem) 。 定理 3  ( CRT 的推论) [ 4 ,5] 设 p1 , p2 , …, ps 是 s 个两两互素的正整数 , P = p1 p2 …ps ,则同余式 f ( x ) ≡0 (mod P) 与同余式方程组 f ( x) ≡0 (mod pi) (1 ≤i ≤s) 等价 。 定理 4  ( 费马小定理) [ 4 ,5] 设 p 是一个素数 ,x 是一个满足 x (mod p) ≠0 的整数 ,则 : x p - 1 ≡1 (mod p) 。 下面 ,将着重分析利用 SRC(即算法 2) 和 MRC(即算法 4) 实现的 RSA 解密算法 。 对于 RSA 的解密运算 m = Dsk ( c) = cd (mod N ) ,由于拥有私钥 S K = ( d , N ) 的合法解密者已知 N = pq ( p 和 q 为不同的素数) ,因此根据定理 3 ,可将 RSA 的解密由计算模 N 的指数运算 m = Dsk ( c) = cd ( mod N ) 转化为计算模 p 和模 q 的同余式方程组 :      m 1 ≡cd (mod p) m 2 ≡cd (mod q) . 而 d 和 c 通常是不小于 p (或 q) 的 ,因此可利用定理 4 及同余式的性质 ,简化同余式方程组 (2 q) 的指数运算 。 (2. 2) 2) 中的模 p (或 事实上 ,根据定理 4 及同余式的性质 ,同余式 m 1 = cd ( mod p) 可以如下简化 :令 r = d ( mod p - 1) ,则存 在 k 满足 : d = k ( p - 1) + r 。于是 m 1 = cd ( mod p) ≡ck ( p - 1) + r ( mod p) ≡ck ( p - 1) cr ( mod p) ≡( c ( p - 1) mod p) kcr (mod p) ≡1 kcr (mod p) ≡cd mod( p - 1) (mod p) ≡( c mod p) d mod( p - 1) ( mod p) 。同理对于同余式 m 2 ≡cd (mod q) 有 : m 2 ≡cd (mod q) ≡cd mod( q - 1) (mod q) ≡( c mod q) d mod ( q - 1) ( mod q) 。最终 ,同余式方程组 (2 2) 转化为 :      m 1 ≡( c mod p) d m 2 ≡( c mod q) d 1 (mod p) 2 (mod q) , 其中 d1 = d (mod p - 1) , d2 = d (mod q - 1) 。 于是 , RSA 的解密运算转化为解同余式方程组 (2 密算法 。 算法 5  RSA 的 SRC 解密算法 。 3) 。利用算法 2 (即 SRC) 解之 ,即得到下面的快速 RSA 解 (2. 3)
3 241 河北省科学院学报           2003 年第 20 卷   11 (mod p) 与 M 2 ←Cd (1) 计算 d1 ←d (mod p - 1) 与 d2 ←d (mod q - 1) ; (2) 计算 C1 ←c (mod p) 与 C2 ←c (mod q) ; (3) 计算 M 1 ←Cd 22 (mod q) ; (4) 计算 B 1 ←q - 1 (mod p) 与 B 2 ←p - 1 (mod q) ; (5) 计算 m ←M 1 B 1 q + M 2 B 2 p (mod N ) 。 为了方便算法 1 中 (7) 与算法 5 的估算和对比 , 不妨采用标准的乘法算法 [3 ] ( The Standard Multiplication Algorithm) 、恢复余数算法[ 3 ] (Restoring Division Algorithm) 和扩展 Euclid 算法实现乘法 、模余及求逆元运算 , 用“平方 —乘”[ 3 ,6 ]方法 (Square Multiply Method) 实现指数计算 。又设 Mu1 (k) 表示 k 比特二进制整数乘法的 计算量 ,根据 Karatsuba 算法[ 7 ] ,2k 比特二进制数的乘法计算量 Mul (2k) 可近似记为 Mul (2k) ≈4Mul (k) ;因为 上述的标准乘法算法与恢复余数算法的计算复杂度均为 O ( (lo g N ) 2) ,故 k 比特二进制数的取余运算的计算 量可用 M ul ( k) 近似表示 。 设 N 是 2 k 比特二进制整数 ,那末 d1 、d2 、C1 、C2 、p 与 q 等均为不超过 k 比特的二进制数 。根据 Knuth 的证明[ 3 ] :扩展 Euclid 算法计算乘法逆元约为 0. 5641 log2 N + 1. 47 次除法 , 计算模指数运算约为 1. 5 log2 N - 2 次乘法 。注意到算法 1 的 (7) 和算法 5 中主要是这两种运算 ,故算法 1 中 (7) 的计算量约为 :     T (1) ≈ (1. 5 log2 N - 2) Mul (2 k) = (1. 5 log222 k - 1 - 2) Mul (2 k) = (3 k - 5) Mul (2 k) ≈12 kMul ( k) 。 算法 5 的计算量约为 :    T (5) ≈[ (1. 5 log2 p - 2) + (1. 5 log2 q - 2) + (0. 564 log2 p + 1. 47) + (0. 564 log2 q + 1. 47) ]Mul ( k) ≈ (1. 5 log22 k - 1 + 1. 5 log22 k - 1 + 0. 564 log22 k - 1 + 0. 564 log22 k - 1) Mul ( k) ≈4. 128 kMul ( k) 。 显然 T (1) ≈3 T (5) ,因此 ,算法 5 比算法 1 的 (7) 能更快地实现 RSA 的解密 。 同样地 ,可利用改进的混合基数计算法 (MMRC) (即算法 4) 解同余式方程组 (2 3) 。首先 ,同上所示构造 三角形数值表 :     M 11     M 21  M 22 其中 M 11 = m 1 , M 21 = m 2 , M 22 = ( M 21 - M 11) ( p - 1 mod q) ( mod q) = ( m 2 - m 1) ( p - 1 mod q) (mod q) ,再由 MMRC(算法 4) 得到 : m = m 1 + [ ( m 2 - m 1) ( p - 1 mod q) p 。这样就得到另一个快速 RSA 解密 算法 。 ( mod q) ] 11 (mod p) 与 M 2 ←Cd 22 (mod q) ; p 。 算法 6  RSA 的 MMRC 解密算法 (1) 计算 d1 ←d (mod p - 1) 与 d2 ←d (mod q - 1) ; (2) 计算 C1 ←c (mod p) 与 C2 ←c (mod q) ; (3) 计算 M 1 ←Cd (4) 计算 B ←p - 1 (mod p) ; (5) 计算 m ←M 1 + [ ( M 2 - M 1) 由于算法 5 和算法 6 的 (1) - (3) 相同 ,因此只需比较它们的后两步 。对于算法 5 , 需要计算 2 次逆元 、4 次乘法 、1 次加法和 1 次模余 (2 k 比特) 运算 ;而对于算法 6 ,需要计算 1 次逆元 、2 次乘法 、1 次加法 、1 次减法 和 1 次模余 ( k 比特) 运算 。显然 ,算法 6 后两步的计算量比算法 5 的少一半 (加法与减法的计算量相对较少 , 忽略不计) ,因此明显好于算法 5 。类似前面对算法 5 的计算量估算 ,算法 6 的计算量约为 3. 564 kMul ( k) ≈ 1/ 4 T (1) ,自然更易于解密实现 。 B (mod q) ] 结论 :利用 MMRC 的解密算法 (算法 6) 是实现 RSA 解密的最佳算法 ,它使 RSA 的解密速度加快大约 4 倍 ,可大大提高用于 RSA 的软硬件解密实现 。
 第 3 期        贺毅朝等 :中国剩余定理在 RSA 解密中的应用 341 5  结束语 结合数论的相关知识 ,作者详细阐述和讨论了中国剩余定理的单基数转换法 ( SRC) 和混合基数转换法 (MRC) ,给出了易于计算的改进 MRC 算法 (MMRC) ,利用这些结果阐述并分析了两个快速实现 RSA 解密的 算法 ,指出利用 MMRC 得出的算法 6 是实现 RSA 解密的最佳算法 ,有效地提高了 RSA 的软硬件实现速度 。 众所周知 ,公开密钥密码算法又称为非对称密码算法 ,在计算机网络和电子商务中的应用日趋成熟 。例 如在提供鉴别和机密性服务的著名的 PGP( Prett y Good Privacy) 软件中 ,就是利用了 RSA 密码算法完成密钥 管理 。应该看到的是 : P KC 算法还远远没有对称密码算法的应用广泛 。究其原因 ,主要是由于其实现速度相 对太慢 ,例如 RSA 密码算法的软件实现比 DES 大约慢 100 倍 。因此 ,为促进公开密钥密码算法的广泛应用 , 对 P KC 密码算法的加密和解密速度的深入研究是非常重要的 。 参考文献 [ 1 ]  W. Diffie and M. E. Hellman ,New Direction in Cryptography[J ] , I EEE Transactions on Information Theory ,1976 , IT - 22 (6) :644 - 654 [ 2 ]  R. L . Rivest ,A. Shamir and L . M. Adleman ,A Method for Obtaining Digital Signature and Public - key Cryptosystems ,Com munications of the ACM[J ] 1978 ,21 (2) :120 - 126 [3 ]  D. E. Knuth , The Art of Computer Programming : Seminumerical Algorithms[ M ] ,Volume 2. Addtion - Wesley , Third edi tion ,1998 [ 4 ]  K. H. Rose , Elementary Number Theoryand Its Application[ M ] ,Addison - Wesley ,1984. 北京 :高等教育出版社 ,1986 [ 5 ]  柯召 ,孙琦 [ 6 ]  冯登国 ,裴定一 北京 :科学出版社 ,2001 [ 7 ]  M. H. Alsuwaiyel[ 沙特 ] ,算法设计技巧与分析 (英文版) [ M ] 数论讲义 (上册) [ M ] 密码学导引[ M ] 北京 :电子工业出版社 ,2003
分享到:
收藏