算法的原理

时间：2022-10-04 百科知识版权反馈

【摘要】：RSA就是典型的非对称密码算法，本节将了解RSA算法的原理及实现方法。它的理论基础是一种特殊的可逆模指数运算，其安全性基于分解大整数n的困难性。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA一定需要作大数分解。目前，RSA的一些变种算法已被证明等价于大数分解。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。下面的案例利用RSA算法对文件进行加密和解密。

任务概述

在传统的对称密钥体制中用于加密的密钥和解密的密钥完全相同，通常加密算法比较简便高效，破译极其困难。但在公开的计算机网络上传送和保管密钥是一个严峻的问题。在非对称密钥密码体制中，加密密钥不同于解密密钥，加密密钥公布于众，谁都可以用，而解密密钥只有解密人自己知道。RSA就是典型的非对称密码算法，本节将了解RSA算法的原理及实现方法。

任务目标

●能够了解RSA算法的描述

●能够理解RSA算法的安全性和速度

●能够理解RSA算法的原理及实现

学习内容

1977年，由Rivest、Shamir、Adleman三人提出了第一个比较完善的公钥密码算法，这就是著名的RSA算法。它的理论基础是一种特殊的可逆模指数运算，其安全性基于分解大整数n的困难性。

一、RSA体制的简单描述

（1）生成两个大素数p和q。

（2）计算这两个素数的乘积n=p×q。

（3）计算小于n并且与n互质的整数的个数，即欧拉函数φ（n） =（p-1）（q-1）。

（4）选择一个随机数b满足1＜b＜φ（n），并且b和φ（n）互质，即gcd（b，φ（n）） =1。

（5）计算ab=1modφ（n）。

（6）保密a、p和q，公开n和b。

二、举例说明

（1）选取两个质数:p=47，q=71

（2）计算:n=pq=3337;φ（n） =（47-1）（71-1） =3220

（3）选取e=79，与φ（n）互质。

（4）计算:ed=1modφ（n） =1mod（3220）;d=1019

将e、n公布，d保密，p、q销毁。

例如，如果有一明文6882326879666683要加密，则先将m分割成多块:m1=688， m2=232，m3=687，m4=966，m5=668，m6=3。

将m1加密后得密文c1=m1e（mod3337） =68879（mod3337） =1570，依次对各块加密后得密文c=15702756271422762423158，对c1解密得m1，m1=c1d（mod3337） =15701019 （mod3337） =668，依次解密得原文m。

三、RSA算法的安全性

RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。

四、RSA算法的速度

由于进行的都是大数计算，使得RSA最快的情况也比DES慢上千倍，无论是软件还是硬件实现。速度一直是RSA的缺陷，一般来说只用于少量数据加密。

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

五、RSA算法的程序实现

根据RSA算法的原理，可以利用C语言实现其加密和解密算法。RSA算法比DES算法复杂，加解密所需要的时间也比较长。

下面的案例利用RSA算法对文件进行加密和解密。算法根据设置自动产生大素数p和q，并根据p和q的值产生模（n）、公钥（e）和密钥（d）。利用VC++6.0实现核心算法，如图2-4所示。

编译执行程序，如图2-5所示。该对话框提供的功能是对未加密的文件进行加密，并可以对已经加密的文件进行解密。

在图2-6中点击按钮“产生RSA密钥对”，在出现的对话框中首先产生素数p和素数q，如果产生100位长度的p和q，大约分别需要10秒，产生的素数如图2-6所示。

图2-4 利用VC++6.0实现核心算法

图2-5 加密系统

图2-6 产生RSA密钥对

利用素数p和q产生密钥对，产生的结果如图2-7所示。