基于RSA的加密算法研究.doc

1、摘要RSA作为一种重要的公开密钥算法，它是继Merkle背包算法出现不久之后，出现的第一个比较完善的公开密钥算法，它既能用于加解密也能用于数字签名。现在主要阐述其基本原理，加解密的实现，以及着重的讨论其安全性，并用C语言来实现。关键词加密算法；RSA；安全性；C语言AbstractRSA algorithm is one of the most important public-key encryption algorithm. It was the first perfect public-key encryption algorithm after the Merkle backpack

2、algorithm had appeared soon. It cans be used for encryption or decryption. Also be used the digital signature. Now, I mainly explain the basic principle of the public-key encryption algorithm, realize the encryption or decryption by C language, and discuss the safety of the public-key encryption alg

3、orithm .Key wordsEncryption algorithm; RSA; Security; C language目录摘要IAbstractII第一章 绪论11.1 RSA的研究背景与意义11.2 RSA的国内外发展趋势11.3 本文做的工作及文章结构2第二章RSA公钥密码32.1 RSA算法简介32.2 加解密算法描述32.2.1 RSA利用了单向陷门函数32.2.2 RSA密钥对生成与加解密42.2.2.1 RSA密钥对的生成42.2.2.2 RSA加解密算法42.2.2.2.1 加密过程42.2.2.2.2 解密过程42.2.3加解密流程52.3 RSA设计流程5第三章RS

4、A的安全性分析63.1 RSA的安全性63.2 RSA的攻击方法63.2.1 因子分解法63.2.2 选择密文攻击73.2.3 共模攻击83.2.4 低加密指数攻击93.2.5 低解密指数攻击93.2.6 计时攻击93.3 使用RSA的一些限制10第四章 RSA的C语言的具体实现114.1 RSA的速度114.1.1 硬件实现114.1.2 软件实现114.2 算法加密结果114.2.1 加密算法的C代码114.2.2 加密所得结果19结论20参考文献21附录23致谢29基于RSA的加密算法研究第一章 绪论1.1 RSA的研究背景与意义随着通信与计算机网络技术的快速发展和公共信息系统商业性应用

5、步伐的加快，人们对网络环境和网络信息资源的依赖程度的日亦加深，这时，网络信息安全的重要性也就从各个方面（电子政务、电子商务、网络金融、网络媒体）体现了出来1。而产生网络信息安全问题的根源可以从三个方面分析：自身缺陷，开放性和人的因素2。首先，网络自身的安全缺陷主要体现在协议和业务的不安全上，而协议的不安全主要原因是：一方面互联网起源的出忠是进行学术交流和信息的沟通，并非商业目的而导致缺乏安全的总体构想和设计。另一方面是协议本身的泄漏。然而业务上的不安全表现在错误信息或业务本身的不完善。其次，网络的开放性体现在业务是基于公开的协议等原因。最后，人的因素才是最主要的因素，表现为三方面：人为的无意失

6、误，黑客攻击，管理不善。随着这些问题不断的出现，网络信息安全的意义也就体现出来了：从大的方面说，网络信息安全关系到国家主权的安全、社会的稳定、民族文化的继承和发扬等。从小的发面说，网络信息安全关系到公私财产和个人隐私的安全。因此，密码学在网络信息安全中发挥的重要性也体现了出来。密码技术是实现网络信息安全的核心技术，是保护数据最重要的工具之一。最常用的技术有：数据加密标准DES、高级加密标准AES、RSA算法、椭圆曲线密码算法ECC、IDEA算法、PGP系统等3。1.2 RSA的国内外发展趋势2012年2月27日到3月2日在美国旧金山举办的RSA信息安全大会上，网络安全，云安全仍然是时下最为热点

7、的话题。而其中云安全仍是2010、2011和2012年度最耀眼的新星，围绕着云安全与网络安全提出了许多问题以及解决的方法，比如：云安全需要急迫解决的安全隐患4；云计算是转变安全交付方式的机会5；云安全将成为2010安全领域趋势6；安全专家看RSA大会焦点：云安全 准备出发7；RSA大会三大主题：网络计犯罪，云计算，IT消费8；安全风向标：品味RSA 2012信息安全大会9；RSA2012主题揭秘：伟大的密码比剑更有力10；新的安全威胁面前 需要新的安全架构11。另外，前人针对RSA所做的一些研究，比如：RSA算法的改进12；基于AES与RSA混合加密策略的硬盘分区加密技术13；一种基于RSA的

8、加密算法14；RSA密码算法的研究与改进实现15；RSA加密算法的研究及应用16等等。1.3 本文做的工作及文章结构本文依旧是对RSA加密算法进行研究以及利用C语言进行实现。主要分为以下四章：第一章绪论部分，对RSA算法的背景意义、国内外的发展趋势进行了大致的介绍。第二章RSA公钥密码，主要介绍其算法简介，算法的原理以及加解密的实现。第三章安全性分析，主要介绍了各种对RSA的攻击方法以及在设计RSA中应该避免的一些问题。第四章RSA的C语言的具体实现，主要介绍一部分用C语言实现RSA的部分代码和加密所得到的结果。 第二章RSA公钥密码2.1 RSA算法简介公开密码算法与其他密码学完全不同，它是

9、基于数学函数而不是基于替换或置换。与使用一个密钥的对称算法不同，公开密钥算法是非对称的，并且它使用的是两个密钥，包括用于加密的公钥和用于解密的私钥。公开密钥算法有RSA、Elgamal等。RSA公钥密码算法是由美国麻省理工学院（MIT）的Rivest，Shamir和Adleman在1978年提出来的，并以他们的名字的有字母命名的。RSA是是第一个安全、实用的公钥密码算法，已经成为公钥密码的国际标准，是目前应用广泛的公钥密码体制。RSA的基础是数论的Euler定理，其安全性基于大整数因子分解问题的困难性，公私钥是一对大素数的函数。并且该算法已经经受住了多年深入的密码分析，虽然密码分析者既不能证明

10、也不能否地RSA的安全性，但这不恰恰说明该算法有其一定的可信度。2.2 加解密算法描述2.2.1 RSA利用了单向陷门函数如下图17所示：私钥公钥图1-1 RSA利用单向陷门函数的原理2.2.2 RSA密钥对生成与加解密2.2.2.1 RSA密钥对的生成首先，选取两个互异的大素数，令其为和（保密），并且为获得最大程度的安全性，要让与相同长度。然后计算乘积（公开）： （1-1） （1-2）其次，随机选取加密密钥，使其与互素，即，然后用扩展的Euclid算法计算密钥 ： （1-3）即 （1-4）注意，和可以公开，两素数与不再需要，可销毁，但不能泄露。2.2.2.2 RSA加解密算法2.2.2.2.

11、1 加密过程首先，将明文比特分组，使其每个分组对应的十进制数小于，即分组长度小于，后对每个明文分组做加密运算，其具体步骤如下：（1） 获得其接收方公钥（e，n）；（2） 把消息M分组为长度L()的消息分组M=；（3） 利用加密算法计算出密文（公式如下）； （1-5）（4） 将密文C发送给对方。2.2.2.2.2 解密过程（1） 接收方收到密文C并把密文按照长度为L分组得；（2） 利用私钥和解密算法计算（公式如下）； （1-6）（3） 得到明文消息。2.2.3加解密流程如下图16所示：发送者加密系统密文明文明文解密系统接收者图1-2 加解密流程图2.3 RSA设计流程如下图18所示：信息输入模块

12、素数产生模块素数测试模块产生密钥模块加密模块解密模块信息输出模块图1-3 RSA设计流程第三章RSA的安全性分析3.1 RSA的安全性从理论上讲RSA的安全性完全依赖于分解大数的难度。但从技术上讲这是不正确的，这只是一种推测。从数学上从未证明需要分解才能从和中计算出。用这种完全不同的方法来对RSA进行密码分析这还只是一种假想。而我并不认为这种新方法能让密码分析者推算出。当然，也可通过猜测（p-1）（q-1）的值来攻击RSA，但这种攻击没有分解容易。对那些仍持极端怀疑态度的人来说，有些RSA的变型已经被证明和大数分解同样困难，可参见19，它给出了从RSA加密的密文中恢复某一位与恢复出整个文本同样

13、困难这一结论。可以看出分解是最显而易见的攻击方法。敌方手中有公开密钥和模数，所以要找到解密密钥，就必须分解。目前，129为十进制数字的模数是能分解的临界数。所以，应该大于这个数。对于密码分析者而言，他有可能尝试每一种可能的，直到获得正确的一个。这种穷举攻击并没有试图分解更有效。随着时间的推移，人们声称已经找到了破译RSA的简单方法，但是直到现在这些宣称还是站不住脚的。举例来说，1993年Willian Payne的论文草案中提到了一种基于费尔马小定理的方法20。很不幸，它的速度仍然比分解模数要慢很多。3.2 RSA的攻击方法3.2.1 因子分解法RSA密码体制安全性主要依赖的是大整数因子分解的

14、问题，那么，试图分解模数的素因子就是攻击RSA最直接的方法。出现的比较早的因子分解分析法是试除法，它的基本思想是：密码分析者完全尝试小于的所有素数，直到找到因子。而根据素数理论，尝试的次数上限是。虽然这种方法非常有效，但是对于超大数，这种方法对资源的消耗在现实之中几乎是不可能实现的。后来也出现了一些比较重要的因子分解分析法，比如：Pollard在1974年提出的因子分解法，Williams提出的因子分解法，二次筛（Quadratic Sieve）因子分解法，椭圆曲线因子分解法，数域筛（Number Field Sieve）因子分解法等常用方法。除了因子分解法的长足发展之外，并行计算和网络上分布

15、式计算也多加快了因子分解的速度，如下表21：表2-1 因子分解位数年度位数（十进制）1984711994129199915520031742005200然而，随着因子分解位数的增加，人们可能会怀疑因子分解是不是计算上的难题。但是由于银子分解的时间复杂性并没有降为多项式时间，因此，因子分解还是计算上的难题，只是需要考虑使用较大的位数，来确保无法在短时间内被攻破。3.2.2 选择密文攻击有一些攻击是专门针对RSA的实现。他们不是攻击基本的算法，而是攻击协议。仅仅会使用RSA是不够的，实现的细节也是非常重要的。实例1：Eve在Alice通信的过程中进行窃听，想办法成功的选取了一个用她的公开密钥加密的

16、密文。Eve想从中读出消息，那么从数学上讲，也就是她想得到，这里： （2-1）为了恢复出完整的，她首先选取了一个随机数，且满足小于。她得到了Alice的公开密钥，然后进行计算： （2-2） （2-3） （2-4）如果成立，那么就成立现在，Eve让Alice用其私人密钥对签名，便于解密（注意，Alice以前从未见过）。则Alice发送给Eve： （2-5）现在Eve计算如下内容: （2-6）Eve就获得了。实例2：Eve想让Alice对签名。她生成两份消息，满足如下要求： （2-7）如果，她也能让Alice对和进行签名，就能计算： （2-8）因此，我们应该谨记，绝对不要对陌生人提交的随机消息进行

17、签名。并且要先利用单向散列函数对消息进行散列运算。ISO9796分组格式可以防止这种攻击。3.2.3 共模攻击有这样一个可能的RSA实现，每个人都具有相同的值，但他们有不同的指数和。然而，不幸的是：这样做是不行的。最显而易见的问题便是：假如同一个消息用两个不同的指数进行加密，并且这两个密钥有互素（一般情况下）。那么不需要任何一个解密指数就可以恢复出明文。假设是明文消息，两个加密密钥为和，共同模数为。则两个密文为： （2-9） （2-10）那么密码分析者就知道n，和，他是如何恢复出的，如下所示：由于和互素，则有扩展Euclid算法就能找出和，满足于： （2-11）假设为负数（或中有一个必须为负）

18、，那么再用Euclid算法可以计算，然后则有下式： （2-12）因此，我们应该谨记不要在一组用户之间共享。3.2.4 低加密指数攻击在对RSA进行加密和数字签名验证中，如所选值较小倒是可以加快速度，但这是不安全的。如果，你采用相同的值以及不同的RSA公开密钥，对个线性相关的消息进行加密，则将存在一种能攻击系统的方法。如果消息较短或消息不相关，将不存在这个问题。如消息相同，那么个消息就足够了。阻止这种攻击最简单的方法就是利用独立随机值填充消息。这也就能保证成立。因此，我们应该谨记在家加密前要用随机值进行消息的填充，用以确保和的大小是一样的3.2.5 低解密指数攻击Michael Wiener给出

19、了另外一种攻击方法，假设达到的1/4大小，并且小于，那么该方法将可以恢复。如果与随即进行选择，则该攻击将很少发生；如果的值很小，则他将不可能发生。因此，我们应该谨记选择大的。3.2.6 计时攻击公钥密码算法的运行时间经常因为输入的不同而表现出细微的差别。而由于攻击者可以高精度的有效的测量公钥密码算法因为输入的不同而表现在运行时间上的差异，并且由于这些差异可能包涵了私钥信息，因而有可能利用这些信息推导出私钥。实施计时攻击的攻击者，就需要对于公钥密码算法具体实现的技术细节具有相当的了解才可以进行这种方法的攻击。3.3 使用RSA的一些限制首先对于所选取的素数对，应该有如下要求22,23：（1）和的

20、长度相差不大（2）和都有大素数因子（3）应该尽可能小（4）与差值不应该太小其次，仅有安全的密码算法是不足够的。整个密码系统必须是安全的，甚至密码协议也必须是安全的。因此，有如下的限制21：（1）如知道对于一个给定模数的加解密密钥指数对，那么攻击者就能分解这个模数。（2）如知道对于一个给定模数的加解密秘钥指数对，那么攻击者无需分解n就可以计算出别的加解密对。（3）在通信网络中，利用RSA实现的协议不应该使用公共模数。（4）消息必须用随机数来填充用以避免对加密指数的攻击。（5）解密指数应该无限大。第四章 RSA的C语言的具体实现4.1 RSA的速度4.1.1 硬件实现在硬件实现时，DES比RSA快

21、大约1000倍。在512位模数的硬件中，最快的是VLSI硬件，其可实现的吞吐量为64位/秒。当然，也有一些可实现1024位的RSA的加密芯片。到1995年，具有512位模数的芯片可达到1M/秒。在智能卡中已经大量实现了RSA，但这些实现大多较慢。4.1.2 软件实现在软件实现时，RSA比DES大约慢100倍。当然这些数字会随着技术的发展而发生相应的变化，但是RSA的速度不会也不可能达到对称算法的速度。下表给出了RSA软件速度的实例21：表3-1 具有8位公开密钥的RSA对于不同长度模数的加密速度512位768位1024位加密0.03秒0.05秒0.08秒解密0.16秒0.48秒0.93秒签名0

22、.16秒0.52秒0.97秒验证0.02秒0.07秒0.08秒4.2 算法加密结果4.2.1 加密算法的C代码（1）小素数的实现#includeint candp(int a,int b,int c) /数据处理函数，实现幂的取余运 int r=1;b=b+1;while(b!=1)r=r*a;r=r%c;b-;printf(%dn,r);return r;int fun(int x,int y) /公钥 e与 t 的互素判断int t;while(y)t=x;x=y;y=t%y;if(x = 1)return 0; /x 与 y互素时返回 0elsereturn 1; /x 与 y不互素时返

23、回 1void main()int p,q,e,d,m,n,t,c,r;printf(请输入两个素数 p,q:);scanf(%d%d,&p,&q);n=p*q;printf(计算得 n 为 %3dn,n);t=(p-1)*(q-1); /求 n 的欧拉数printf(计算得 t 为 %3dn,t);printf(请输入公钥 e: );scanf(%d,&e);if(et|fun(e,t)printf(e 不合要求，请重新输入: ); /et 或 e 与 t 不互素时，重新输入scanf(%d,&e);d=1;while(e*d)%t)!=1) d+; /由公钥 e 求出私钥dprintf(经

24、计算 d 为 %dn,d);printf(加密请输入 1n); /加密或解密选择printf(解密请输入 2n);scanf(%d,&r);switch(r)case 1: printf(请输入明文 m: ); /输入要加密的明文数字scanf(%d,&m);c=candp(m,e,n);printf(密文为 %dn,c);case 2: printf(请输入密文 c: ); /输入要解密的密文数字scanf(%d,&c);m=candp(c,d,n);printf(明文为 %dn,m);（2）函数说明/! MAX是数组的最大个数，LEN为结构体slink的占用内存空间大小 */ #defin

25、e MAX 100 #define LEN sizeof(struct slink) /! #能够进行动态链接库编译的RSA类 /*! see class _declspec(dllexport) RSA 将RSA算法写成动态链接库的形式方便调用，其中有公钥，私钥和明文 就可以进行明文的加密和解密 */ class _declspec(dllexport) RSA public: /! # 新定义的数据结构slink /*! see struct slink 数据结构中，bignum存储的是随机生成的大数，next是指向后面的指针 see int bignumMAX */ typedef st

26、ruct slink int bignumMAX;/*! bignum98用来标记正负号，1正，0负bignum99来标记实际长度*/ struct slink *next; slink; public: /! #RSA 的构造函数 /*! see RSA() 其中应该对RSA类中的一些变量进行相应的初始化 */ RSA(); /! #RSA的析构函数 /*! see RSA() 释放内存 */ RSA(); public: /! #RSA的大数运算函数库 /* 大数比较函数 see int cmp(int, int) */ int cmp(int a1MAX,int a2MAX); /* 大

27、数类型转换函数 see void mov(int aMAX,int *b); */ void mov(int aMAX,int *b); /* 大数乘积函数 see void mul(int a1MAX,int a2MAX,int *c); */ void mul(int a1MAX,int a2MAX,int *c); /* 大数相加函数 see void add(int a1MAX,int a2MAX,int *c); */ void add(int a1MAX,int a2MAX,int *c); /* 大数大数相减函数 see void sub(int a1MAX,int a2MAX,

28、int *c); */ void sub(int a1MAX,int a2MAX,int *c); /*! 大数取模函数 see void mod(int aMAX,int bMAX,int *c); attention /c=a mod b/注意：经检验知道此处A和C的数组都改变了。 */ void mod(int aMAX,int bMAX,int *c); /*! 大数相除函数 see void divt(int tMAX,int bMAX,int *c ,int *w); attention /试商法/调用以后w为a mod b, C为a div b; */ void divt(int

29、 tMAX,int bMAX,int *c ,int *w); /*! 解决 了 m=a*b mod n; /*! see void mulmod(int aMAX ,int bMAX ,int nMAX,int *m); */ void mulmod(int aMAX ,int bMAX ,int nMAX,int *m); /*! 解决 m=ap mod n的函数问题 /*! see void expmod(int aMAX ,int pMAX ,int nMAX,int *m); */ void expmod(int aMAX ,int pMAX ,int nMAX,int *m); /

30、*! 判断是否为素数 see int is_prime_san(int pMAX ); */ int is_prime_san(int pMAX ); /*! 判断两个大数之间是否互质 see int coprime(int eMAX,int sMAX); */ int coprime(int eMAX,int sMAX); /*! 随机产生素数 see void prime_random(int *p,int *q); */ void prime_random(int *p,int *q); /*! 产生素数e see void erand(int eMAX,int mMAX); */ vo

31、id erand(int eMAX,int mMAX); /*! 根据规则产生其他的数 see void rsad(int eMAX,int gMAX,int *d); */ void rsad(int eMAX,int gMAX,int *d); /*! 求解密密钥d的函数(根据Euclid算法) see unsigned long rsa(unsigned long p,unsigned long q,unsigned long e); */ unsigned long rsa(unsigned long p,unsigned long q,unsigned long e); /! #RS

32、A的产生大数的公钥和私钥的函数 /*! see bool RSAKey(); param 没有任何输入， param 随机产生e，d，n的函数，其运行时间比较长，需要等待 returnbool 成功返回true，失败返回false */ bool RSAKey(); /! #RSA的进行文件加密的函数 /*! see string tencrypto(int eMAX, int nMAX, char* text); paramint e，n为随机产生的公钥，利用公钥进行加密 paramchar* text为明文，明文以char*的格式存储 returnstring 返回值为加密成功之后的密文，

33、采用string类型进行存储 */ string tencrypto(int eMAX, int nMAX, char* text); /! #RSA的进行文件解密的函数 /*! see string tdecrypto(int dMAX, int nMAX, string text); paramint d,n为私钥，由函数RSAKey()产生 paramstring text为密文，对应加密函数，密文的格式为string returnstring 解密之后的明文采用string进行存储 */ string tdecrypto(int dMAX, int nMAX, string text)

34、; public: /* brief 定义的全局变量，存储密钥 */ int pMAX,qMAX,nMAX,dMAX,eMAX,mMAX,p1MAX,q1MAX; private: int i; char c; /struct slink *head,*h1,*h2; ; 注意:完整的随机生成素数的C语言实现代码24见附录。4.2.2 加密所得结果图4-1 C语言实现结果结论一方面，本文做了以下几方面的工作：（1）对密码学、信息安全做了些简要的介绍，并且简明扼要的介绍了信息安全的发展趋势，而且阐述了RSA加解密体制的一些现状。（2）介绍了RSA加解密用到的数论的基本思想，研究了RSA公钥密码体

35、制的原理，并着重的讨论、分析了RSA的安全性以及参数的选择问题。（3）对RSA算法的加解密原理进行了深入浅出的细致的研究，同时构建了主要包括：大素数的产生、密钥对的生成、模幂运算实现（见附录），三大模块的RSA算法系统框架。另一方面，由于时间和能力有限，本文还有有待改善的诸多地方，比如：（1）特殊素数的快速生成算法有待进一步的研究实现。如果采用中的剩余定理，将会大大提高加解密速度。（2）争取自己开发一套及数据加密、认证、密钥产生等功能于一体的完整的RSA应用平台。参考文献1 LI Tie-niu，LI Hong-da. Rational Distributed Computation Of T

36、he RSA PrivateKey Over The Shared Euler Totient Function J.计算机工程与科学,2010. 2 HAN Song，WANG Ji. New Provably Secure Signature SchemeN.北京大学学报.2003(5).3 Sun Baolin，Wu Channghai. Research on the RSA Public-Key Cipher Algorithm and Secret Sharing ProblemN.武汉理工大学学报,2002(3)4 赛迪网. RSA 2010：云安全需急迫解决的安全隐患R.旧金山

37、：赛迪网,2010.5 Cent. RSA2010：云计算是转变安全交付方式的机会R. 旧金山：Cent，2010.6 赛迪网. RSA主席认为云安全成2010安全领域趋势R. 旧金山：赛迪网,2010.7 赛迪网. 安全专家看RSA大会焦点：云安全 准备出发R. 旧金山：赛迪网,2010. 8 赛迪网. RSA大会三大主题：网络计犯罪，云计算，IT消费R. 旧金山：赛迪网，2010. 9 魏晨. 安全风向标：品味RSA 2012信息安全大会R. 旧金山：赛迪网,2012. 10 木淼鑫. RSA2012主题揭秘：伟大的密码比剑更有力R. 旧金山：赛迪网,2012. 11 四夕. 新的安全威胁

38、面前 需要新的安全架构R. 旧金山：赛迪网，2012.12 陈磊. RSA算法的改进N.中国软件评测中心,2011.13 董军利，宋福刚，管文强. 基于AES与RSA混合加密策略的硬盘分区加密技术J.微电子学与计算机,2012,29(1):135-137.14 王茜，倪建伟. 一种基于RSA的加密算法J.重庆大学学报,2005,28(1):68-72.15 周升力. RSA密码算法的研究与改进实现J.现代计算机,2008:51-53.16 管占明,邓亚娟. RSA加密算法的研究及应用J.科技广场,2009:98-99.17 胡向东，魏琴芳等. 应用密码学M.北京市：电子工业出版社,2008：1

39、14-119.18 李青，李雄伟，金涛. RSA算法的研究与简单实现J. 网络安全技术与应用,2007:88-91.19 W.Alexi, O.Goldreich, C.P.Schnorr. RSA and Rabin Functions：Certain Parts are as hard as the whole. SIAM Journal on Computing.V.17，n.2，Apr1988:pp.194-209.20 W.H.Payne. Public key cryptography is easy to break. William H.Payne, unpublished m

40、anuscript ,16 Oct 90.21 吴世忠，祝世雄等（译）,Bruce Schneier（著）.应用密码学M.北京市：机械工业出版社，2007：334-340.22 谷利泽，郑世慧，杨义先. 现代密码学教程M.北京邮电大学出版社，2009：218-225.23 卢开澄. 计算机密码学M. 北京市：清华大学出版社，2002：737724 史子荣. 软件加密技术从入门到精通M. 北京市：清华大学出版社，2007：74-77.附录/*/求解密密钥d的函数(根据Euclid算法)96403770511368768000*/ unsigned long RSA:rsa(unsigned long p,unsigned long q,unsigned long e) /*/求解密密钥d的函数(根据Euclid算法)*/ unsigned long g,k,r,n1,n2,t; unsigned long b1=0,b2=1; g=(p-1)*(q-1); n1=g; n2=e; while(1) k=n1/n2; r=n1-k*n2; if(r!=0)