中国剩余定理在RSA算法中应用的 研究实验

简析RSA数据加密算法的分析与改进摘要：RSA加密算法中存在着大素数查找的问题，导致RSA运算速度缓慢。

本文利用小素数筛值法、偶数排除法、小素数整除法等方法对伪素数进行了初步的剔除，然后利用米勒-拉宾法来进行素数的检测，从而大大地改善了对素数的探测效果。

实验证明，与传统Miller-Rabin方法比较，该方法在较短的时间内产生大素数，而不是大素数的几率低于0.1%。

因此，RSA的加密速度和RSA的可操作性都得到了改善。

关键词：RSA数据加密算法改进引言：当前，信息化已成为社会发展的中心趋势，它作为一种重要的战略资源，随着互联网的发展突破了传统的空间和区域概念，使真正意义上的全球信息化逐渐呈现在我们的面前，但由于互联网的互联性、共享性和可开发性，假冒、篡改、泄露等一系列问题也需要我们去正面认识与解决。

因此，网络时代确保信息安全始终是一个重要的课题。

为了保障网络中的数据安全性，信息加密技术一定是最主要且最基础的保护方式。

在大多数情况下，只有通过加密技术才能进一步确保网络中的数据通信安全。

为了达到对资料数据的加密处理，一般可以采用多种加密算法技术。

目前，已公布的加密算法主要有DESRC4和FEAL-N等，RSA是在1977年由RSA、AdiShamirh和LenAdleman三位科研人员在美国麻省理工大学开发的，而RSA命名是基于三个开发者的姓名组合和零知识证明算法等密钥算法所命名。

在这些算法中，RSA算法是综合效果最佳的，对于它的普遍应用，以及更多被证实的安全性测试，本文都将针对此进行更深入的研究和完善，从而尽可能再提高它的性能，使RSA算法具备更佳的可操作性。

1公开RSA加密算法RSA加密属于公开密钥加密算法，它自身具有很强的代表性，对于密钥来说，不论是加密，还是解密，在关联中都存在着些许的差异。

在公开密钥算法里，加密密钥是透明化的，而对于此，解密密钥就具备鲜明的私有性。

众所周知，对于公钥和私钥，在被包含的RSA加密算法里，它们具备对数据进行加密的时效性，理论上没有任何限制；而另一个关键在于对应的解密过程，无法从根本上进行密钥的相互的推导，那么在某种程度上就能更好地解决在传输过程中因密钥丢失而造成的安全隐患。

中国剩余定理及其应用Chinese Remainder Theorem and Its Application专业:作者:指导老师:摘要本文主要讨论了中国剩余定理及其应用, 文中研究了中国剩余定理在初等数论范畴下的应用及在密码学方面的贡献, 说明了中国剩余定理的应用的广泛性.关键词: 中国剩余定理; 初等数论; RSA算法; 解密AbstractThe paper discusses the Chinese Remainder Theorem and Its Application. It studies the application in the context of Elementary Number Theory and the contributions in cryptography, and it illustrates the broad application of Chinese Remainder Theorem.Keywords:Chinese Remainder Theorem; Elementary Number Theory; RSAalgorithm; decrypt目录摘要 (I)ABSTRACT (II)0 引言 (1)1 中国剩余定理 (1)2 中国剩余定理的应用 (2)2. 1 中国剩余定理在赋值领域的体现 (2)2. 2 中国剩余定理在多项式中的应用 (3)2. 3 中国剩余定理在密码学中的应用 (4)3结束语 (11)参考文献 (12)0 引言中国剩余定理源于我国古代《孙子算经》, 其中有一题: “ 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何？” 这就是求解一次同余式组:()()()⎪⎩⎪⎨⎧≡≡≡7mod 25mod 33mod 2x x x《孙子算经》中给出最小正整数解23, 解法传至今世. 中国剩余定理又称“孙子定理”. 它数初等数论中重要定理之一, 在代数数学和计算机领域中也有重要应用. 本文讨论中国剩余定理及其一些简单的应用.1 中国剩余定理中国剩余定理:设r m m m ,,,21 是两两互素的正整数, 设r a a a ,,,21 使整数, 则同余方程组 r i m a x i i ,,2,1),(mod =≡ 模r m m m M 21=有唯一解∑==ri i i i M y M a x 1mod其中i i m M M =, i i i m M y mod 1-=, r i ,,2,1 =.举世闻名的中国剩余定理最早以“ 物不知其数” 的问题载于《孙子算经》[1]中, 该问题可以理解为: 一个数除以3余2, 除以5余3, 除以7余2, 求合适这些条件的最小的自然数. 用现代数学符号表示, 即已知)7(mod 2)5(mod 3)3(mod 2≡≡≡N 求最小的正整数, 答案是23=N .《孙子算经》的解法是:“ 术曰: 三三数之剩二, 置一百四十; 五五数之剩三, 置六十三; 七七数之剩二, 置三十; 并之, 得二百三十三, 以二百一十减之即得.凡三三数之剩一, 则置七十;五五数之剩一, 则置二十一, 七七数之剩一, 则置十五. 一百六以上, 以一百五减之即得.”把“物不知其数”问题推广到一般情况[2], 设d c b a ,,,为非负整数, 且a 为某个数除以3的余数, b 为这个数除以5的余数, c 为这个数除以7的余数, 试求符合条件的最小的数m . 按《孙子算经》的解法有d c b a m 105152170-++=.我们可以证明, 因为d c b a m 105152170-++=可以改写为 c d c b a m +-++=)105152169(.又因为)105152169(3d c b a -++且20≤≤a , 所以m 除以3的余数必为a , 同理可得m 除以5的余数必为b , m 除以7的余数必为c . 又因为[]1057,5,3=, 所以m 减去105的整数倍就能得到符合题意的最小自然数.2中国剩余定理的应用中国定理是中国古代数学家为世界数学发展作出的巨大贡献, 它的数学思想在近代数学、当代秘密学研究及日常生活都有着广泛应用.2. 1中国剩余定理在赋值理论中的体现赋值理论是域论的一个分支, 是研究近代数学中几个重要分支如代数数论、交换数论的一个重要工具, 而中国剩余定理在赋值论中起着重要作用, 下面介绍中国剩余定理在赋值理论中的应用.定理 (赋值的独立性)对于任意n 个p 赋值pn p p V V V ,,,21 , Q a ∈, n i ,,2,1 =,以及任意0>ε, lm l l P P P ,,,21 --, 则存在Q b ∈使(1)()ε<-=-∞1a b a b V ; (2)()i l i i pi P a b V -≤-, n i ,,2,1 =证明 设m 为n a a a ,,,21 的最小公分母, 令()m V P pi Si i =, i i i s l r +=, n i ,,2,1 =,{}n r r r r ,,,,1max 21 =. 根据中国剩余定理, 可求得一个c , 使得()r p ma c 11mod ≡, ()r pr ma c 22mod ≡, , ()rnn p ma c mod ≡ 即 ()r i i pi p ma c V -≤-, i l i i pi p a m c V -≤⎪⎭⎫⎝⎛-设()rn p p p q 21=, 取适当的Z v u ∈,, 使ε<-++a vq uq m c 11, 再令a vquqm c =++11, 则b 显然满足条件(1).又由p 距离p D 的性质: ()()()()c a D c b D b a D p p p ,,,,max ≥有()i l i i pi i pi p a m c m c b V a b V -≤⎭⎬⎫⎩⎨⎧⎪⎭⎫ ⎝⎛-+⎪⎭⎫ ⎝⎛-=≤-max , n i ,,2,1 =.2. 2 中国剩余定理在多项式中的应用由中国剩余定理可得相似定理. 设()()()x m x m x m n ,,,21 是n 个两两互素的多项式,()()()x a x a x a n ,,,21 是n 个多项式, 则一定存在多项式, 使()()()()()()()()()()()()⎪⎪⎩⎪⎪⎨⎧≡≡≡x m x a x f x m x a x f x m x a x f n n mod mod mod 2211当()x f 的次数不超过()()()()()()x m x m x m x m x m n 21=的次数是, ()x f 唯一确定.特别地, 当()[]x Q b x x m i i ∈-=(或[]x R ), n i ,,2,1 =, ()n i b i ,,2,1 =是互不相等的常数, 从而()()n i x m i ,,2,1 =也是两两互素的多项式, 由余数定理可知()()()()i i i i b x b m x m -≡mod , ()n i ,,2,1 = 从而定理可叙述为, 一定存在多项式()x f , 是()()()()()()()()()()()()⎪⎪⎩⎪⎪⎨⎧-≡-≡-≡n n n b x m x a x f b x m x a x f b x m x a x f mod mod mod 222111其中()x a i ()n i ,,2,1 =是任意给定的常数, 且多项式()x f 在次数不超过n 的条件下唯一确定的, 有()()()i i b x a x f -≡mod 等价于()i i a b f ≡()n i ,,2,1 =得: 对任意互不相同的i b()n i ,,2,1 =存在唯一的次数小于n 的多项式()x f , 是()i i a b f ≡()n i ,,2,1 =. 这就是插值多项式的存在与唯一性定理.由中国剩余定理的证法, 只要找到多项式()x M i ()n i ,,2,1 =, 使()()()i i b x x M -≡mod 1 ()()()j j b x x M -≡mod 0, j i ≠ (1) 而()()()()()()()()()n i i i i i i n i i i b b b b b b b b b x b x b x b x x M --------=+-+-111111 满足(1), 于是的插值多项式()x f :()()()()()()()∑∏==≠--=+++=nj ni i ji j n n j i b bb x a x M a x M a x M a x f 112211这就是著名的Lagrange 内插多项式.中国剩余定理推导出的内插多项式是处理许多多项式问题的基本工具如简化数列求和问题: 计算()22221210-++++n解 假设和为n 的三次多项式()n f , n 代表项数, 于是有 ()()()()53,12,01,00====f f f f 由插值公式得()()()()()()()()()()()()()()()()()()()12161231303210532120231051004321--=-----++------=⋅+⋅+⋅+⋅=n n n n n n n n n n M n M n M n M n f 所以, ()()()1216112102222--=-++++n n n n .中国剩余定理主要是解决一次同余式问题, 在算术中还可以利用它来检查因数和验算整数计算的结果.2. 3中国剩余定理在密码学中的应用中国剩余定理虽是数论中的基本定理, 但是在计算机秘密学中有着重要的应用. 例如在Rabin 密码算法中用于解密运算. 在RSA 密码算法中, 中国剩余定理同样可用于RSA 的解密运算, 而且使RSA 的机密速度大约提高4倍左右, 这无论对于软件还是硬件实现RSA 密码算法都是非常重要的. 本文主要从基于中国剩余定理的一种加密算法和中国剩余定理在RSA 解密中的应用两点来说.2. 3. 1基于中国剩余定理的一种加密算法根据中国剩余定理, 可以得出一种新的网络信息加密算法. n A A A A ,,,,321 为n 个互质的素数, 若已知一个整数Y 除以n A A A A ,,,,321 余数分别为n B B B B ,,,,321 , 求Y .令n A A A A M ⨯⨯⨯⨯= 321,1X 表示能n A A A ,,,32 被n A A A ,,,32 整除的所有整数,1Y 表示能被n A A A ,,,32 整除的所有整数且除以1A 余1B 的所有整数, 2X 表示能被n A A A ,,,31 整数的所有整数,2Y 表示能被n A A A ,,,31 整数的所有整数且除以2A 余2B 的所有整数,i X 表示能被n i i A A A A A A ,,,,,,,11321 +-整除的所有整数,i Y 表示能被n i i A A A A A A ,,,,,,,11321 +-整除的所有整数且处于i A 余i B 的所有整数,那么1321/A m M A A A X n ⨯=⨯⨯⨯= , 2312/A m M m A A A X n ⨯=⨯⨯⨯⨯= ,n n n A m M m A A A X /121⨯=⨯⨯⨯⨯=- , 其中m 为任意整数.设i F 满足i X 和i Y , 且令其为i Y 中最小的正整数, 其中n i ≤≤1则 m M F m A A A F Y n ⨯+=⨯⨯⨯⨯+=12111m M F M A A A F Y n n n n ⨯+=⨯⨯⨯⨯+= 21那么m M F F F Y Y Y Y Y n n ⨯++++=++++= 21321.用Y 表示明文, 是所要隐蔽和保护的机要消息. 用n B B B B ,,,,321 表示密文, 要把明文转换成一种隐蔽的形式: n A A A A ,,,,321 和N 为密钥.加密算法的步骤如下:步骤1: 选出n 个n A A A A ,,,,321 作为“密钥”; 步骤2: 求出这n 个素数的乘积M ; 步骤3: 求出n F F F F ,,,,321 ;步骤4: 由m M F F F Y Y Y Y Y n n ⨯++++=++++= 21321得出 ()[]M F F F F Y N n /321++++-= ;步骤5: 用Y 分别除以n A A A A ,,,,321 得余数n B B B B ,,,,321 并把它们作为密文. 解密算法的步骤如下:已知密文n B B B B ,,,,321 和密钥n A A A A ,,,,321 和N 算出n F F F F ,,,,321 . 由m M F F F Y Y Y Y Y n n ⨯++++=++++= 21321得出Y . 这样就实现了从密文和密钥到明文的整个解密过程. 加密和解密举例: 加密:令明文2001=X , 密钥为11,7,5, 密文为10,6,1可求出175,55,231321===F F F , 那么()[]()41175/175552312001=⨯⨯++-=m 为另一密钥.解密:2001411755517522121321=⨯⨯⨯+++=⨯++++=++++=m M F F F Y Y Y Y Y n n .2. 3. 2中国剩余定理在RSA 解密中的应用1978年美国麻省理工学院的三位教授R. L. Rivest, A. Shamir 和M. Adleman 提出了一种基于因子分解的指数函数作为单项陷门函数[3](One-way Trapdoor Function)的公开密钥密码算法(Public-Key Cryptosystems, PKC), 即著名的RSA 算法[4]. RSA 算法是第一个较完善的PKC 算法, 也是非常容易理解和实现的的PKC 算法. 它既可用于传输信息的加密, 也可用于数字签名系统, 是当前民用也商业使用最广泛的公开密钥密码算法之一, 已被国际标准化组织ISO 、JTU 和SWIFT 接受为标准.随机选取两个不同的大素数p 和q (约为150位或更大的十进制数), 计算它们的乘积pq N =与相应的Euler 函数(Euler Totient Function)()()()11--=q p n φ的值, 将N 公开, 而将()n φ, p 和q 保密;显然, 如果不知道N 的素因子p 和q 的前提下, 计算()n φ的值是属于NP 问题, 极难实现.再随机选取一个正整数e , 是e 满足条件: ()N e φ<且()()1,gcd =N e φ(即e 与()N φ的最大共因素是1), 根据扩展Eulicd 算法(Extended Euclidean Algorihm)[5]计算()()N e d φmod 1-=, 即计算满足()()N ed φmod 1=的d . 将e 公开, 而将d 保密, 就确定了RSA 算法的公开密钥()N e PK ,=, 私人密钥()N d SK ,=, 密钥空间:(){}pq N d e q p N K ==,,,,, p 与q 为不同大素数, ()()N ed φmod 1=.相应的, RSA 算法中的单向陷门函数为()()N x x f t mod =(其中K t ∈且N Z x ∈), 称为RSA 函数. 其秘密陷门信息为()N φ及素数p 、q 的值.确定公钥()N e PK ,=和私钥()N d SK ,=之后, RSA 算法的机密运算定义为: ()()N m m E c e pk mod ==, 其中11-≤≤N m 为明文.解密运算定义为: ()()N c c D m d sk mod ==, 其中11-≤≤N c 为密文.RSA 秘密算法的明文m 应为1到1-N 之间的整数, 即[]1,1-∈N m . 如果明文m 太长, 可将其转换成N 进制的形式, 即0111m N m N m N m m s s s s ++++=-- , 于是得到分组后的明文序列 ()s m m m m ,,,10 =, 其中 []1,1-∈N m i , s i ≤≤0. 与之相应的密文序列为()s c c c c ,,,10 =, 其中1c 对应于1m ()s i ≤≤0.中国剩余定理(Chinese Remainder Throrem, CRT)是初等数论中重要的基本定理之一, 它主要是刻画剩余系的结构和求解形如()()s i p d x i i ≤≤≡1mod 的一次同余式方程. 在计算数论中, 计算中国剩余定理唯一解的方法有两种: 单基数转换法(Single-Radex Conversion, SRC)和混合技术转换法(Mixed-Radex Conversion, MRC), 这两种防范都是非常实用的计算方法.算法1 CRT 的单基数转化法(SRC)(1)计算s p p p P 21←和()s i p P P i i ≤≤←1/;(2)计算()()s i p P Q i ≤≤←-1,mod 111;、 (3)计算唯一解()P Q P d Q P d Q P d x s s s mod 222111+++← .利用混合技术转换法(MRC)求CTR 唯一解得方法是H. L. Garner 在1958年首先提出的. 之后D. E. Kunth 将其用于计算数论, 并进行了有益的改进. 经Kunth 改进后的MRC 方法用算法描述如下:算法2 CRT 的混合基数转换法(MRC) (1)计算()i j ji p p B mod ←, ()s i j ≤<≤1; (2)分别计算()i p d v mod 11←; ()()212122mod p B v d v -←;()()()()()()s s s s s s s s s p B B B v p v p v p v d v mod 1211232211---++++-← .(3)计算唯一解112123121v p v p p v p p p v X s s ++++←- .利用中国剩余定理对RSA 密码解密, 首先要将RSA 的解密运算由计算模N 的指数形式转化成求解同余方程组的情形. 为此, 先介绍两个必须的数论定理: 即中国剩余定理的一个推论(定理1)于费马小定理(Fermat's Little Theorem).定理1(CRT 的推论)[6, 7]设s p p p ,,,21 是s 个两两互素的正整数, s p p p P 21=, 则同余式()()P x f mod 0≡与同余式方程组()()()s i p x f i ≤≤≡1mod 0等价.定理2(费马小定理)[6, 7]设p 使一个素数, x 是一个满足()0mod ≠p x 的整数, 则:()p x p mod 11≡-.下面, 将着重分析利用SRC(算法1)和MRC(算法2)实现的RSA 解密算法. 对于RSA 的解密算法()()N c c D m d sk mod ==, 由于用于私钥()N d SK ,=的合法解密者已知pq N =(p 和q 为不同的素数), 因此根据定理1, 可将RSA 的解密由计算模N 的指数运算()()N c c D m d sk mod ==转化为计算模p 和模q 的同余式方程组:()()⎪⎩⎪⎨⎧≡≡q c m p c m d dmod mod 21 (2. 1) 而d 和c 通常是不小于p (或q )的, 因此可利用定理2及同余式的性质, 简化同余式方程组(2. 1)的模p (或q )的指数运算.事实上, 根据定理2及同余式的性质, 同余式()p c m d mod 1=可以如下简化: 令()1mod -=p d r , 则存在k 满足: ()r p k d +-=1. 于是()()()()()()()()p c p c p c c p c p c m r kp r p k r p k d mod mod mod mod mod 1111--+-≡≡≡=()()()()()()p p c p c p c p d p d r k mod mod mod mod 11m od 1m od --≡≡≡同理对于同余式()q c m d mod 2≡有()()()()()()q q c q c q c m q d q d d mod mod mod mod 1m od 1m od 2--≡≡≡最终, 同余式方程组(2. 1)转化为:()()()()⎪⎩⎪⎨⎧≡≡,mod mod mod mod 2121q q c m p p c m d d (2. 2)其中()()1mod ,1mod 21-=-=q d d p d d .于是, RSA 的解密运算转化为解同余式方程组(2. 2). 利用算法1(即SRC)解之, 即得到下面的快速RSA 解密算法.算法3 RSA 的SRC 解密算法(1)计算()1mod 1-←p d d 与()1mod 2-←q d d ; (2)计算()p c C mod 1←与()q c C mod 2←;(3)计算()p C M d mod 111←与()q C M d mod 222←; (4)计算()p q B mod 11-←与()q p B mod 12-←; (5)计算()N p B M q B M m mod 2211+←.同样地, 可利用改进的混合基数计算法(MMRC)(即算法2)解同余式方程组(2. 2). 首先, 构造三角形数值表:222111M M M其中111m M =, 221m M =,()()()()()()q q p m m q q p M M M mod mod mod mod 1121112122---=-=, 再由MMRC(算法2)得到:()()()[]p q q p m m m m *-+=-mod mod 1121 . 这样就得到另一个快速RSA 解密算法. 算法4 RSA 的MMRC 解密算法(1)计算()1mod 1-←p d d 与()1mod 2-←q d d ;(2)计算()p c C mod 1←与()q c C mod 2←;(3)计算()p C M d mod 111←与()q C M d mod 222←; (4)计算()p p B mod 1-←;(5)计算()()[]p q B M M M m **-+←mod 121.由于算法3和算法4的(1)-(3)相同, 因此只需比较它们的后两步. 对于算法3, 需要计算2次逆元、1次加法和1次模余(2k 比特)运算;而对于算法4, 需要计算1次逆元、2次惩罚、1次加法、1次减法和1次模余(k 比特)运算. 显然, 算法4的后两步的计算量比算法3的少一半(加法与减法的计算量相对减少, 忽略不计), 因此明显好于算法3. 利用MMRC 的解密算法(即算法4)使RSA 的解密速度加快大约4倍, 可大大提高用于RSA 的软硬件解密实现.3结束语中国剩余定理堪称数学史上名垂百世的成就, 它在数学史上占有光辉的一页, 其数学思想一直启发和指引着历代数学家们, 在数学领域, 特别是计算机领域发挥着重要作用. 以上只是它应用的一些例子, 可见中国剩余定理的应用之广泛, 地位之高.致谢 本文是在。

文章编号:1001 - 9383 (2003) 03 - 0138 - 06Ξ中国剩余定理在RSA 解密中的应用贺毅朝1 ,刘建芹2 ,陈维海3( 11 石家庄经济管理学院信息工程系,石家庄050000 ;21 石家庄信息工程职业学院,石家庄0500353 . 中国华融资产管理公司石家庄办事处, 石家庄050000)【摘要】在分析RSA 密码算法实现原理的基础上,着重论述了利用单基数转换法( SRC)和混合基数转换法( M R C) 计算中国剩余定理惟一解的方法以及利用这两种方法快速实现RSA 的解密算法。

【关键词】P KC 算法; 中国剩余定理; RSA 算法【中图分类号】T P 311 . 56 ;O156 【文献标识码】 AThe a ppl i cat i on of CRT to R SA decrypt i onHE Y i2chao 1 ,LI U J ian2qin2 ,CHE N Wei2hai3( 1 . Col l ege of I nf or m at i on En g i neeri n g , S hij i a z h u a n g U ni versi t y of Econ nom i cs , S hij i a z h u a n g 050000 , Chi n a ;2 . S hij i a z h u a n g I nf or m at i on En g i neeri n g V ocat i on al Col l ege , S hi j i a z h u a n g 050035 , Chi n a ;3 . S hi j i a z h u a n g Of f ice of Chi n a Hu a r on g A s sets M a n age m ents Corporat i on , S hij i a z h u a n g 050000 , Chi na) Abstract Based o n analysis of t h e p r inciple of RSA implementati o n ,t h e applicati o n issues of Sin2 gle2Radix C o nversi o n ( SRC) and Mixed2Radix C o nversi o n ( M RC) algo rit h ms o n Chinese Rem ain2 der Theo re m ( CR T) and high2speed realizati o n of RSA decryp ti o n using above met ho ds were il lu2 minated em p h atically.K ey w ords P KC algo r it h m ; Chinese Re mainder Theo r e m (CR T) ; RSA algo r it h m1978 年美国麻省理工学院的三位教授R. L . Rivest ,A. Shamir 和M . Ad leman 提出了一种以基于因子分解的指数函数作为单向陷门函数1 (One2way Trap d oor Functio n) 的公开密钥密码算法( Pub lic2Key Cryp to syst em , P KC) ,即著名的RSA 算法2 。

RSA加密算法的研究作者：李莹赵瑞曹宇张天宇刘霏凝来源：《智能计算机与应用》2020年第03期摘要：随着互联网和通信技术的发展，信息安全问题日益受到重视，基于数据加密的信息安全技术得到了迅速的发展。

数据加密就算法而言，分为对称加密和非对称加密两类。

RSA是应用最广泛的非对称算法之一，具有安全性高、易于实现等特点，但运算速度很慢，只能用于一些少量数据。

针对RSA运算效率慢的问题，提出了中國剩余定理和蒙哥马利模乘法相结合的方法来优化模幂，用三素数代替传统的二重素数。

实验结果表明，优化算法具有较高的速度和可行性。

关键词： RSA; 中国剩余定理; 蒙哥马利模乘法【Abstract】 With the development of Internet and communication technology， more and more attention has been paid to information security.In terms of algorithm， data encryption can be divided into symmetric encryption and asymmetric encryption.RSA is one of the most widely used asymmetric algorithms， and has the characteristics of high security， being easy to implement， but the operation speed is very slow， which can only be used for some small amount of data encryption.In order to solve the problem of slow arithmetic efficiency of RSA， a method combining Chinese residual theorem and Montgomery modular multiplication is proposed to optimize modular power and replace traditional double prime number with triple prime number. Experimental results show that the optimization algorithm has high speed and feasibility.【Key words】 ;RSA;Chinese remainder theorem; Montgomery model multiplication0 引言随着计算机技术的不断发展，互联网上共享的数据量有了显著增长。

LUOYANG NORMAL UNIVERSITY 2012届本科毕业论文中国剩余定理的归纳及其应用院（系）名称数学科学学院专业名称数学与应用数学学生姓名任晓燕学号*********指导教师王众杰讲师完成时间2012.5中国剩余定理的归纳及其应用任晓燕数学科学学院 数学与应用数学 学号：080414001指导老师：王众杰摘要：中国剩余定理又称为孙子定理,它的数学思想在近代数学中占有非常重要的地位.本文归纳了中国剩余定理并给出证明,并给出相关的经典例,并在此基础上对其在同余式组,多项式定理、赋值定理、密码学以及生活中的应用进行初步的讨论和分析.关键词：中国剩余定理； 同余式组； 多项式； 密码学 引言中国古代著名数学著作<孙子算经>记载,"今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?"此问题为中国剩余定理的原型.解法和答案用算式表示为70×2+21×3+15×2-105×2=23.即得到适合题意的最小整数是23."物不知其数"开创了一次同余式研究的先河,但真正从完整的计算程序和理论上解决这个问题的事南宋时期的数学家秦九韶,秦九韶在他的《数书九章》中提出了一个数学方法"大衍求一术" .1876年,德国人马蒂生首先指出这一解法与19世纪高斯《算术探究》中关于一次同余式组的解法完全一致.从此,中国古代数学这一创造受到世界学者瞩目,并在西方数学史著中正式称为"中国剩余定理" ..1 中国剩余定理及其证明设122,,,...n n m m m 两两互素的正整数,令121122......,n n n M m m m m M m M m M ====则同余式组()()()1122mod mod ........................mod n n x c m x c m x c m =⎧⎪=⎪⎨⎪⎪=⎩有正整数解()111222...mod n n n x M a c M a c M a c M =++且解唯一；其中i a 是满足()()1mod ,1,2,...i i i M a m i n ≡=的一个整数.下面我们先给出裴蜀恒等式和一个性质,然后证明中国剩余定理.在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。

基于中国剩余定理的秘密共享方案李洁平;韦性佳【摘要】利用中国剩余定理、椭圆曲线离散对数问题(ECDLP)、双线性变换和强RSA假设,提出了一种新的可验证秘密共享方案.该方案具有能够检测出秘密分发者和可信中心的诚实性,检测出系统中参与者的欺诈行为;利用椭圆曲线,结合双线性对技术,不仅降低了系统的计算成本,而且实现了方案的可验证性;利用强RSA假设,实现方案的前向安全性,即使敌手掌握第j个时间段的子秘密,也无法获取之前时间段关于共享秘密的任何信息,增强了系统的安全性.%By utilizing the Chinese remainder theorem, elliptic curve discrete logarithm problem (ECDLP), bilinear transformation and strong RSA hypothesis, a new verifiable secret sharing scheme is proposed. The scheme is capable of detecting the integrity of secret distributors, trusted centers and fraudulent behavior in the system; by using elliptic curve and bilinear pair technology, the computational cost of the system could be reduced and the verification of the scheme realized; by using strong RSA assumption the forward security of the scheme be achieved, even if the opponent grasps the sub-secret of the j-th time period, he can't get any information about the shared secret in the previous time period, thus enhancing the security of the system.【期刊名称】《通信技术》【年(卷),期】2018(051)003【总页数】5页(P671-675)【关键词】秘密共享;中国剩余定理;椭圆曲线;双线性变换;强RSA假设【作者】李洁平;韦性佳【作者单位】青海师范大学数学与统计学院,青海西宁 810008;青海师范大学数学与统计学院,青海西宁 810008【正文语种】中文【中图分类】TP3090 引言秘密共享是密码学的一个重要工具。

一种基于中国剩余定理的加密方案
孙秀娟;宋明娟;陈孝国
【期刊名称】《煤炭技术》
【年(卷),期】2008(27)10
【摘要】密码技术在当今社会经济发展过程中,发挥了越来越大的作用。

随着计算机网络的进一步普及和发展,人们的生活将更依赖于数字化的信息技术,依赖于为其安全提供基础保障的密码学。

而在密码技术的发展进程中,各种数学工具的作用不容小视。

特别是数论同余理论中大量的技巧,使得要设计一个好的密码算法更加困难。

本文在分析论证和推广中国剩余定理的基础上,提出一种新的网络信息加密方案,并用实例说明该方案的合理实用。

【总页数】2页(P146-147)
【关键词】信息安全;密钥算法;中国剩余定理
【作者】孙秀娟;宋明娟;陈孝国
【作者单位】黑龙江科技学院数力系
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于中国剩余定理的广播加密方案 [J], 李树栋;丁媛媛;姜述武
2.基于中国剩余定理的数据广播加密方案 [J], 蔡国扬;苏扬
3.基于中国剩余定理的公钥加密方案同态性 [J], 王会勇;孙爽;冯勇
4.一种基于多项式环上中国剩余定理的(r,n)-门限方案 [J], 刘寅寅;郭楠楠
5.基于中国剩余定理的一种加密算法 [J], 张皓翔
因版权原因，仅展示原文概要，查看原文内容请购买。

一种基于中国剩余定理改进RSA算法的实现方法摘要：RSA加密算法是目前使用较多、安全性高的一种非对称加密算法，但RSA也存在运算代价高，速度较慢等缺点。

本文提出了一种改进的RSA算法，使其运算速度得到了一定地提高，并采用C语言平台得到了比较好的验证。

关键词：非对称加密；RSA算法Abstract: Though RSA encryption algorithm is a popular unsymmetrical encryption with high secure character， The shortcomings of high cost and low efficiency are inherent. This paper introduced an improved RSA algorithm. The computation speed under this algorithm was improved with C programming language．Key words:unsymmetrical encryption ; RSA algorithm引言RSA(Rivest,Shamir and Adleman)是一种国际公认的理想公钥密码体制。

它表达方式简单、保密性强、没有密钥管理的麻烦，并且具有数字签名、认证和鉴别等功能，特别适合于现代保密通信的需要。

但RSA的加密算法速度与对称加密算法相比，其速度非常缓慢的。

因此，研究快速的RSA算法是十分有意义的。

至今，人们在此方面已经作了很多的研究，提出了许多快速的RSA算法。

其中分块模幂算法，幂等价代换的改进及SMM算法等都极大的提高了RSA加密算法的速度。

本文运用中国剩余定理对RSA算法的加密过程做了一定改进。

通过理论分析和试验测试，证明了改进后的算法比改进前的算法速度要快。

1 RSA工作原理RSA工作原理如下[1]：1)任意选取两个不同的大质数P和q，计算乘积年n=P*q；2)任意选取一个大整数e ，e 与(p-1)*(q-1)互质，整数e 用做加密密钥．注意：e 的选取是很容易的，例如所有大于P和q的质数都可用；3)确定解密密钥d，由 d*e=1 mod((p-1)*(q-1))，根据e ，p和q可以容易地计算出d；4)公开整数n和e，但是不公开d；5)将明文M(假设M是一个小于n的整数)加密为密文C，计算方法为C= M e mod n；6)将密文C解密为明文M，计算方法为M=C d mod n。

跨越千年的RSA算法数论，数学中的皇冠，最纯粹的数学。

早在古希腊时代，人们就开始痴迷地研究数字，沉浸于这个几乎没有任何实用价值的思维游戏中。

直到计算机诞生之后，几千年来的数论研究成果突然有了实际的应用，这个过程可以说是最为激动人心的数学话题之一。

最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》，但受篇幅限制，只有一万字左右的内容。

其实，从数论到 RSA 算法，里面的数学之美哪里是一万字能扯完的？在写作的过程中，我查了很多资料，找到了很多漂亮的例子，也积累了很多个人的思考，但最终都因为篇幅原因没有加进《程序员》的文章中。

今天，我想重新梳理一下线索，把所有值得分享的内容一次性地呈现在这篇长文中，希望大家会有所收获。

需要注意的是，本文有意为了照顾可读性而牺牲了严谨性。

很多具体内容都仅作了直观解释，一些“显然如此”的细节实际上是需要证明的。

如果你希望看到有关定理及其证明的严格表述，可以参见任意一本初等数论的书。

把本文作为初等数论的学习读物是非常危险的。

最后，希望大家能够积极指出文章中的缺陷，我会不断地做出修改。

======= 更新记录 =======2012 年 12 月 15 日：发布全文。

2012 年 12 月 18 日：修改了几处表达。

======== 目录 ========（一）可公度线段（二）中国剩余定理（三）扩展的辗转相除（四）Fermat 小定理（五）公钥加密的可能性（六）RSA 算法（一）可公度线段Euclid ，中文译作“欧几里得”，古希腊数学家。

他用公理化系统的方法归纳整理了当时的几何理论，并写成了伟大的数学著作《几何原本》，因而被后人称作“几何学之父”。

有趣的是，《几何原本》一书里并不全讲的几何。

全书共有十三卷，第七卷到第十卷所讨论的实际上是数论问题——只不过是以几何的方式来描述的。

在《几何原本》中，数的大小用线段的长度来表示，越长的线段就表示越大的数。

很多数字与数字之间的简单关系，在《几何原本》中都有对应的几何语言。

基于中国剩余定理的一种加密算法
张皓翔
【期刊名称】《广西科学院学报》
【年(卷),期】2007(23)4
【摘要】在分析论证和推广中国剩余定理的基础上,提出一种新的网络信息加密算法,并用实例说明新算法合理实用.
【总页数】3页(P249-251)
【作者】张皓翔
【作者单位】北京交通大学电子信息工程学院,北京,100044
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于中国剩余定理的快速公钥加密算法 [J], 王保仓;韦永壮;胡予濮
2.基于中国剩余定理的公钥加密算法的破解 [J], 毕经国;韩立东;刘明洁
3.一种基于多项式环上中国剩余定理的(r,n)-门限方案 [J], 刘寅寅;郭楠楠
4.一种基于多项式环上中国剩余定理的（r,n）-门限方案 [J], 刘寅寅;郭楠楠
5.基于中国剩余定理和Logistic映射的彩色图像加密算法 [J], 段雪峰;王瑞
因版权原因，仅展示原文概要，查看原文内容请购买。