[理学]密码学报告.doc

中国地质大学 计算机学院 19210301 唐乾 学 号：20101000214 班 级：19210301 学生姓名：唐乾 指导教师：任伟 日 期：2012年12月25日 题 号： 实验一、二、三、RSA1 预期目标在充分理解古典密码加密体制概念和原理的基础上，用Microsoft Visual C+ 6.0实现古典密码加密与解密，演示公钥与密钥的生成及加密与解密的过程。2 系统分析2.1 仿射密码：加法密码和乘法密码结合就构成仿射密码，仿射密码的加密和解密算法是： C= Ek(m)=(k1m+k2) mod n M= Dk(c)=k1(c- k2) mod n 仿射密码具有可逆性的条件是gcd(k, n)=1。当k1=1时，仿射密码变为加法密码，当k2=0时，仿射密码变为乘法密码。 仿射密码中的密钥空间的大小为n(n)，当n为26字母，(n)=12，因此仿射密码的密钥空间为1226 = 312。2.2 Playfair密码：它依据一个5*5的正方形组成的密码表来编写，密码表里排列有25个字母。如果一种语言字母超过25个，可以去掉使用频率最少的一个。如，法语一般去掉w或k，德语则是把i和j合起来当成一个字母看待。英语中z使用最少，可以去掉它。第一步是编制密码表。在这个5*5的密码表中，共有5行5列字母。第一列（或第一行）是密钥,其余按照字母顺序。密钥是一个单词或词组，若有重复字母，可将后面重复的字母去掉。当然也要把使用频率最少的字母去掉。如：密钥是Live and learn,去掉后则为liveandr。如果密钥过长可占用第二列或行。 如密钥crazy dog，可编制成 第二步整理明文。将明文每两个字母组成一对。如果成对后有两个相同字母紧挨或最后一个字母是单个的，就插入一个字母X。如，communist，应成为co,mx,mu,ni,st。最后编写密文。对明文加密规则如下：1 若p1 p2在同一行，对应密文c1 c2分别是紧靠p1 p2 右端的字母。其中第一列被看做是最后一列的右方。如，按照前表，ct对应oc 2 若p1 p2在同一列，对应密文c1 c2分别是紧靠p1 p2 下方的字母。其中第一行被看做是最后一行的下方。3 若p1 p2不在同一行，不在同一列，则c1 c2是由p1 p2确定的矩形的其他两角的字母（至于横向替换还是纵向替换要事先约好，或自行尝试）。如，按照前表，wh对应tk或kt。如，依照上表，明文where there is life,there is hope。可先整理为wh er et he re is li fe th er ei sh op ex 然后密文为：kt yg wo ok gy nl hj of cm yg kg lm mb wf 将密文变成大写，然后几个字母一组排列。 Playfair解密算法首先将密钥填写在一个5*5的矩阵中（去出重复字母和字母z），矩阵中其它未用到的字母按顺序填在矩阵剩余位置中，根据替换矩阵由密文得到明文。对密文解密规则如下：1 若c1 c2在同一行，对应明文p1 p2分别是紧靠c1 c2 左端的字母。其中最后一列被看做是第一列的左方。2 若c1 c2在同一列，对应明文p1 p2分别是紧靠c1 c2 上方的字母。其中最后一行被看做是第一行的上方。3 若c1 c2不在同一行，不在同一列，则p1 p2是由c1 c2确定的矩形的其他两角的字母。2.3 Vigenere密码： 给定一个任意密钥k，其中k=(k1,k2,k3 .Kn)并且kiZ26(1in)；任意明文P=(P1,P2,P3.Pm)，并且PjZ26(1jm)；将加密后得到的密文表示为c=(c1,c2cm)并且cj(1jm)。这样，我们中以定义如下所示的加密操作Eki：Cj=Eki(Pj)(其中Eki(p)jPj+Ki(mod 26)还可以定义如下所示的解密操作：Pj=Dki(cj)(其中Dki(c):cjcj-Ki(mod 26)2.4 希尔密码：每个字母当作26进制数字：A=0, B=1, C=2. 一串字母当成n维向量，跟一个nn的矩阵相乘，再将得出的结果模26。注意用作加密的矩阵（即密匙）在mathbb_n必须是可逆的，否则就不可能译码。只有矩阵的行列式和26互质，才是可逆的。 设d是一正整数，定义。Hill cipher的主要思想是利用线性变换方法，不同的是这种变换是在上运算。例如：设d=2，每个明文单元使用 来表示，同样密文单元用 表示，具体的加密中，将被表示为 的线性组合。如：利用线性代数的知识，可得这个运算在 上进行，即mod26，密钥K一般取一个m*m的矩阵。 希尔密码是基于矩阵的线性变换，希尔密码相对于前面介绍的移位密码以及放射密码而言，其最大的好处就是隐藏了字符的频率信息，使得传统的通过字频来破译密文的方法失效。 线性代数中的逆矩阵：在线性代数中，大家都知道，对于一个n阶矩阵 M，如果存在一个n阶矩阵N，使得 M * N = E（其中：E为n阶单位矩阵），则称矩阵 N 为矩阵 M 的逆矩阵，并记为 M-1.比如 2阶矩阵 M = 3,6，则很容易得知其逆矩阵：2,7M-1 = 7/9,-2/3 -2/9,1/3 。关于这个逆矩阵是如何计算出的，通常的有两种方法：一是使用伴随矩阵，通过计算行列式得到。所用公式为： M-1 = M* / D 。（其中M*为M的伴随矩阵，D为M的行列式的值）二是通过增广矩阵，在M右侧附加一个n阶单位矩阵，再通过初等变换将增广矩阵的左侧变换为一个n阶单位矩阵，这时右侧便是所求的逆矩阵。3 源代码#include Encryption.hHGLOBAL Temp;int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd )DialogBoxParam(hInstance,MAKEINTRESOURCE(IDD_DIALOG1),NULL,DLGPROC (DlgP),LPARAM(hInstance);return 0;BOOL CALLBACK DlgP(HWND hWnd,UINT wMessage,WPARAM wParam,LPARAM lParam)HICON hIcon;HWND hEdit;switch (wMessage)case WM_COMMAND:switch (LOWORD(wParam) )case IDC_OPEN:OpenDlg(hWnd);return TRUE;case ID_M_AFF_EN: /get paramentif (Temp = NULL)return TRUE;elseif(Encryption(hWnd,(TCHAR*)Temp)hEdit = GetDlgItem(hWnd,IDC_EDIT);SetWindowText(hEdit,(TCHAR*)Temp);GlobalFree(Temp);return TRUE;case ID_M_AFF_DE:if (Temp = NULL)return TRUE;elseDecryption(hWnd,(TCHAR*)Temp);hEdit = GetDlgItem(hWnd,IDC_EDIT);SetWindowText(hEdit,(TCHAR*)Temp);GlobalFree(Temp);return TRUE;case ID_M_HILL_EN:if (Temp = NULL)return TRUE;elseif(Hi_Encryption(TCHAR*)Temp,hWnd)hEdit = GetDlgItem(hWnd,IDC_EDIT);SetWindowText(hEdit,(TCHAR*)Temp);GlobalFree(Temp);return TRUE;case ID_M_HILL_DE:if (Temp = NULL)return TRUE;elseHi_Decryption(TCHAR*)Temp,hWnd);GlobalFree(Temp);return TRUE;return TRUE;case ID_M_PLAY_EN:if (Temp = NULL)return TRUE;elsePlay_Encryption(TCHAR*)Temp,hWnd);GlobalFree(Temp);return TRUE;case ID_M_PLAY_DE:if (Temp = NULL)return TRUE;elsePlay_Decryption(TCHAR*)Temp,hWnd);GlobalFree(Temp);return TRUE;case ID_M_VI_EN:if (Temp = NULL)return TRUE;elseif(Vi_Encryption(TCHAR*)Temp,hWnd)hEdit = GetDlgItem(hWnd,IDC_EDIT);SetWindowText(hEdit,(TCHAR*)Temp);GlobalFree(Temp);return TRUE;return TRUE;case ID_M_VI_DE:if (Temp = NULL)return TRUE;elseVi_Decryption(TCHAR*)Temp,hWnd);hEdit = GetDlgItem(hWnd,IDC_EDIT);SetWindowText(hEdit,(TCHAR*)Temp);GlobalFree(Temp);return TRUE;return TRUE;default:return FALSE;case WM_INITDIALOG:hIcon = LoadIcon(HINSTANCE(lParam),MAKEINTRESOURCE(IDI_ICON1);SendMessage(hWnd,WM_SETICON,ICON_BIG,LPARAM(hIcon);return TRUE;case WM_CLOSE:EndDialog(hWnd,NULL);return TRUE;default:return FALSE;void OpenDlg(HWND hWnd)OPENFILENAME openfile;HANDLE hFile;DWORD FileSize;DWORD ByteRead;static TCHAR fileBufMAX_PATH;static TCHAR FileTitleMAX_PATH;static TCHAR FileFilter= TEXT(Text Files(*.txt)0*.txt00);RtlZeroMemory(&openfile,sizeof(OPENFILENAME);openfile.lStructSize = sizeof(OPENFILENAME);openfile.hwndOwner = hWnd;openfile.Flags = OFN_EXPLORER;openfile.lpstrFile = fileBuf;openfile.lpstrFilter =FileFilter;openfile.nMaxFile = MAX_PATH;openfile.nMaxFileTitle = MAX_PATH;openfile.nMaxFileTitle =MAX_PATH;if(GetOpenFileName(&openfile)hFile = CreateFile(openfile.lpstrFile,GENERIC_READ,FILE_SHARE_READ,NULL,OPEN_EXISTING,FILE_ATTRIBUTE_ARCHIVE | FILE_ATTRIBUTE_NORMAL,NULL);FileSize = GetFileSize(hFile,NULL);Temp = GlobalAlloc(GMEM_FIXED | GMEM_ZEROINIT,FileSize+1);if (Temp = NULL)MessageBox(NULL,TEXT(Memory allocate error!),TEXT(oh,no),MB_OK |MB_ICONERROR);return ;if(!ReadFile(hFile,Temp,FileSize,&ByteRead,NULL)MessageBox(NULL,TEXT(Read File Error),TEXT(Sorry),MB_OK |MB_ICONERROR);return;SetWindowText(GetDlgItem(hWnd,IDC_PATH),openfile.lpstrFile);CloseHandle(hFile);elsereturn;4 测试数据及结果运行效果如下图：图11 预期目标在充分理解ELGamal加密、签名体制概念和原理的基础上，用Microsoft Visual C+ 6.0实现ELGamal加密与签名，演示ELGamal加密与签名过程。2 系统分析2.1.1 计算体系参数 随机素数p，用户的私有密钥x，g和x计算得到的整数y，消息m，随机数k。2.1.2 计算密钥 公开密钥（p，g，y），私有密钥x2.1.3 对文件签名 任何一个给定的消息都可以产生多个有效的ELGamal签名。2.1.4 验证签名文件 验证算法能够将上述多个ELGamal签名中的任何一个当作可信的签名接受。2.1.5 密钥对产生办法 首先选择一个素数p，两个随机数, g 和x，g, x p, 计算 y = gx ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。 ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算 a= gk ( mod p ) 再用扩展 Euclidean 算法对下面方程求解b： M = xa + kb ( mod p - 1 ) 签名就是( a, b )。随机数k须丢弃。 验证时要验证下式： ya * ab ( mod p ) = gM ( mod p ) 同时一定要检验是否满足1= a p。否则签名容易伪造。 ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数。因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。 2.2 Elgamal加密和签名方案 在系统中有两个用户A和B，A要发送消息到B，并对发送的消息进行签名。B收到A发送的消息和签名后进行验证。 1系统初始化 选取一个大的素数p，g是GF(p)的本原元。h：GF(p)GF(p)，是一个单向Hash函数。系统将参数p、g和h存放于公用的文件中，在系统中的每一个用户都可以从公开的文件中获得上述参数。 2对发送的消息进行加密、签名的过程 假定用户A要向B发送消息m 1,p-1，并对消息m签字。第一步：用户A选取一个x 1,p-1作为秘密密钥，计算y= (mod p)作为公钥。将公钥y存放于公用的文件中。第二步：随机选取k 1,p-1且gcd(k,(p-1)=1，计算r= (mod p)。对一般的ElGamal型数字签名方案有签名方程（Signature Equation）：ax=bk+c(mod(p-1)。 其中(a，b，c)是(h(m),r,s)数学组合的一个置换。由签名方程可以解出s。那么(m,(r,s)就是A对消息m的数字签名。第三步：A将(m,(r,s)发送到B 3加密、签名的验证过程 当B接收到A发送的消息(m,(r,s)，再从系统公开文件和A的公开文件中获得系统公用参数p，g，h和A的公钥y。由(m,(r,s)计算出(a，b，c)验证等式： = (mod p)是否成立。 2.3 整个程序的流程图在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和成员函数原型声明）。产生一个随机数g输入私钥x计算出公钥y输入m计算出签名（a，b）验证签名产生一个素数p产生素数p由用户选择素数p的范围，来算出p函数定义为 int prime_number_p();由用户输入产生素数的范围n,mP-m判断m是否为素数m=m-1mnYNNY产生随机数gg是一个在1-（p-1）中的一个随机数函数为int random_number_g(int p)p是选择的大素数利用随机函数rand()%p来得g。产生公钥y自定义函数为int PKI_y(int p,int g,int x)P是产生的大素数，g是大素数的生成元，x是私钥计算公式y=gx(mod p)产生m签名（a，b）自定义函数 void elg_sign_develop(int g,int p,int x,int m)g是p的生成元，p是大素数，x是私钥，m是要签名的数据b=i计算a= gk ( mod p )i=1x*a+k*b)%(p-1)=mi=i+1输出a产生一个随机数kK与p-1互质YNYN验证签名自定义函数名void elg_sign_test(int y,int p,int m,int g,char name)y是公钥，p是大素数，m是签名的数据，g是大素数的生成元计算i=(ya)*(ab)%p;计算j=(gm)%p;i=jYN输出签名正确输出不是name的签名3 源代码#include#include #includeint a,b;int prime_number_p();int random(int);int m_develop(int );/*-*/int prime(int p)int i,j;for(i=2;i=n;p-)if(prime(p)=1)return p;/求出n,m之间的最大素数/*-*/int prime_number_p()int p,m,n;cout为一组用户产生一个公钥P(p为素数)endl;cout请输入p所在范围n，m(系统将选择最大的素数P)endl;coutn;coutm;p=prime_number_max(n,m);if(p=0) coutn,m中无素数;p=prime_number_p();return p;/p的产生/*-*/int Random_number_g(int p) int g;srand(int) time (NULL);g=rand()%p;return g;/g的产生int PKI_y(int p,int g,int x)int y;int i;y=1;for(i=0;ib)s0=a;s1=b;elses0=a;s1=b;for(int i=1;im;if (mp)cout无法对输入的m进行签名,请重新输入endl;m=m_develop(p);return m;int prime_k(int p)int k,i;k=rand()%p;i=gcd(k,p-1);if(i!=1)k=prime_k(p);return k;/随即数k的产生/*-*/void elg_sign_develop(int g,int p,int x,int m) int k;int i=1;k=prime_k(p);/产生一个k的随机数,k与p-1互质/a=(gk)%p;for(i=0;ik;i+)a*=g;a%=p;/while(m!=(a*x+k*i)%(p-1)/i+;b=i;for(i=0;ip-1;i+)b=i;if(x*a+k*b)%(p-1)=m) break;k=0;/丢弃随即数Kcoutm的数字签名是（a,b）endl;/产生签名/*/void elg_sign_test(int y,int p,int m,int g,char name)int i,c1,d1,j;c1=d1=j=1;/i=(ya)*(ab)%p;for(i=0;ia;i+)c1*=y;c1%=p;for(i=0;ib;i+)d1*=a;d1%=p;d1*=c1;d1%=p;/j=(gm)%p;for(i=0;im;i+)j*=g;j%=p;if(d1=j)cout是用户name签名的。endl;elsecout不是用户name签名的endl;/验证签名/*/main()int p,g,x,y,m,i;a=b=1;char name;p=prime_number_p();/产生大素数pg=Random_number_g(p);/产生随即数gcout此用户组的公共参数为p=p g=gendl;cout输入用户名name;x=p+1;while(x=p)cout输入用户密码x;if(x=p)cout密码格式错误;endl;y=PKI_y(p,g,x);/公钥y的产生cout用户name公钥y是yendl;cout输入要签名的字符mendl;m=m_develop(p);elg_sign_develop(g,p,x,m);elg_sign_test(y,p,m,g,name);jj:cout结束程序请输入0i; if(i=0) exit(0); else goto jj;4 测试数据及结果大素数p的产生和g的产生用户名以及密钥x，和公钥y的生成签名（a，b）的产生和验证5 调试过程中的问题此程序仅仅局限于int型，int对于文件还有安全性较差。超过int就会出现错误这就出现错误了。 我们可以进行扩充。把int的数用一个数组来表示。大家都扩到128位。密码也按照一定方法扩到128位。对于m则可以使用hash值。这样可以可以对几乎所有的文件进行签名了。 对于g，此处我使用的随机数g，这会使得签名容易破译。g应该为p的生成元在，然后再生成元中随机取一个。 若一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号G=（a）来表示。a叫做G的一个生成元。关于生成元g产生的方法 int getGenerator(int p)int gTableLEN;int len=0;int q=p;for(int i=2;iq;i+)for(int j=2;jq-1;j+)int g=1;for(int l=0;l=40)break;cout素数p的生成元有：endl;for(int s=0;slen;s+)coutgTables ; coutendl;srand(time(NULL);int g_index=rand()%len;return gTableg_index; 对于随机数K的产生，一开始没有注意到要与p-1互质，总是出错。注意到只要进行gcd（k，p-1）就行。求最大公约数的方法则用欧几里得算法。1 预期目标在充分理解Rabin加密体制概念和原理的基础上，用Microsoft Visual C+ 6.0实现Rabin加密与签名，演示Rabin加密与签名的过程。2 系统分析2.1密钥产生 随机选择两个大素数p, q，满足p q 3 mod 4,即这两个 素数形式为4k+3；计算n=p*q。 以n作为公钥，p, q作为密钥2.2 加密 c m2modn m是明文分组，c是对应的密文分组2.3 解密 解密即为求解x2 c m2modn，由中国剩余定理知该方 程等价于解方程组 x2 cmodp x2 cmodq由于p q 3 mod 4，下面将看到，方程组的解可容易求出，其中每个方程都有两个解，即 xm mod p, x-mmod p xm mod q, x-m mod q经过组合可得到4个同余方程组： xm mod p x-mmod p xm mod p x-mmod pxm mod q xm mod q x-m mod q x-m mod q pq3 mod 4，下面将看到，方程组的解可容易求出：一个结论：对x2 cmodp，c是modp的平方剩余的充要条件是c(p-1)/21modp简单推导：x2 cmodpx(p-1) c(p-1)/2modp。因为c是modp的平方剩余，故c不能被p 整除，所以x也不能被p 整除。由Fermat定理可知x(p-1) 1modp，故c(p-1)/21modp，pq3 mod 4，可得：p+1=4k，即(p+1)/4是一个整数。则(c(p+1)/4)2 (c(p+1)/2 c(p-1)/2*ccmodp，故(c(p+1)/4和p-(c(p+1)/4是方程x2 cmodp的两个根。同理，故(c(q+1)/4和q-(c(q+1)/4是方程x2 cmodq的两个根。2.4 总体方案要实现加密与签名的功能，必须先生成两个大素数，且满足p=q=3mod4。方法是先设定随机种子为系统当前时间，然后随即生成两个100以内的随机数，并判断其是否为素数，取出这两个素数。然后通过调用函数进行加密与签名，同时显示出结果到屏幕上。3 源代码#include #includeusing namespace std; typedef long llong; llong b1000,w1000; int mod_exp(int a,int b,int n) int tmp=a%n,ans=1; for(;b0;b=1) if(b&1) ans*=tmp;ans%=n; tmp*=tmp;tmp%=n; return ans; int extended_euclid(int a, int b, int &x, int &y) int d; if(b = 0) x = 1; y = 0; return a; d = extended_euclid(b, a % b, y, x); y -= a / b * x; return d; int chinese_remainder(int len) int i, d, x, y, m, n, ret; ret = 0; n = 1; for(i=0; i len ;i+) n *= wi; for(i=0; i pqM; N = p*q; int C = (M*M)%N; coutC= Cendl; int a1 = mod_exp( (int)C,(p+1)/4), p); int a2 = -(mod_exp( (int)C,(p+1)/4), p); int b1 = mod_exp( (int)C,(q+1)/4) , p); int b2 = -(mod_exp( (int)C,(q+1)/4) , p); b0 = a1; b1 = b1; w0 = p; w1 = q; M1 = chinese_remainder(2); b0 = a1; b1 = b2; w0 = p; w1 = q; M2 = chinese_remainder(2); b0 = a2; b1 = b1; w0 = p; w1 = q; M3 = chinese_remainder(2); b0 = a2; b1 = b2; w0 = p; w1 = q; M4 = chinese_remainder(2); coutThe possible messages are endl; coutM1 M2 M3 M41)是素数，如果p的因子只有1，p。称c是两个整数a、b的最大公因子，如果 c是a的因子也是b 的因子，即c是a、b的公因子。 a和b的任一公因子，也是c的因子。表示为c=gcd(a, b)。由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由任一非0整数能整除0，可得gcd(a,0)=|a|。如果将a，b都表示为素数的乘积，则gcd（a, b）极易确定。一般由c=gcd(a,b)可得： 对每一素数p，cp=min(ap,bp)。由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。如果gcd(a,b)=1，则称a和b互素。2.1.2 模运算设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0rn, 其中x为小于或等于x的最大整数。用a mod n表示余数r如果(a mod n)=(b mod n)，则称两整数a和b模n同余，记为ab mod n。称与a模n同余的数的全体为a的同余类，记为a，称a为这个同余类的表示元素。2.1.3 欧拉函数和欧拉定理欧拉函数：设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)。若n是素数，则显然有(n)=n-1。若n是两个素数p和q的乘积，则(n)=(p)(q)=(p-1)(q-1)。欧拉定理：若a和n互素，则a(n)1 mod n。2.1.4 欧几里德算法欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。1. 求最大公因子：Euclid算法是基于下面一个基本结论： 对任意非负整数a和正整数b，有gcd(a, b)=gcd(b, a mod b)。2. 求乘法逆元：如果gcd(a, b)=1 ，则b在mod a下有乘法逆元（不妨设ba），即存在一x (xa)，使得bx1 mod a。2.1.5 RSA算法中的计算问题1. RSA的加密与解密过程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(ab) mod n=(a mod n)(b mod n) mod n就可减小中间结果再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。2. RSA密钥的产生产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（102002664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。2.1.6公钥密码体制的基本概念在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问