安全聊天系统的设计与实现.doc

安全聊天系统的设计与实现

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

个人收集整理 勿做商业用途
安全聊天系统的设计与实现
学生姓名：xxx 指导老师：xxx
摘 要 随着计算机的不断普及和互联网技术在全球领域的高速发展。越来越多的人使用到了聊天程序。聊天程序给人们带来通信便利的同时也存在着一些安全隐患，传统的聊天程序以明文方式传送聊天内容，这样就给一些用心不良的人大开方便之门。本系统正是基于以上原因而设计的加密聊天程序。聊天程序采用服务器/客户端模式。在Linux环境下采用socket套接口编程，服务器程序以创建线程池的方式为每一个客户服务。聊天内容由服务器转发。在聊天程序中加入了对称加密算法DES和非对称加密算法RSA.其基本实现是由服务器端生成RSA的公钥和私钥，由客户端生成DES对称密钥,服务器端传送公钥至客户端加密DES密钥之后回传服务器,服务器再用本地的私钥解密获得DES密钥。此后双方的通信由DES密钥加密后传送，这样既能高效的加密明文又能在信道上安全的传送密钥使得密钥间的共享成为现实。

关键词 对称加密算法；非对称加密算法;聊天系统

The Design and implementation of safe chat system
Student name: CHEN Fan-xing Advisor：ZHOU Shu-ren
Abstract Along with Computer becoming more and more popular and Internet technology developing rapidly, a lot of People began to use the IM（chat program). Chat program brings people more convenience， but at the same time， security problem existed。 The traditional chat program sends the message by plain text, which open the door for the bad man。 This encrypted chat system is right based on the point. The system is in C/S architecture using socket based on Linux. The server program serves each client in the way of establishing thread and is responsible to transfer message。 The DES algorithm and RSA algorithm are used to encrypt in this program。 The basic principle is that the server generates RSA public key and private key and client generates DES symmetrical secret key。 Firstly， the server sends the public key to client， and then client sends it back after encrypting DES secret key。 Secondly, the Server uses local private key to decode to obtain the DES private key. After then， the message is sent after encrypted by DES secret key. So the plain text can be encrypted effectively and sent in channel in security。个人收集整理，勿做商业用途个人收集整理，勿做商业用途

Key words symmetry encrypting program； unsymmetrical encrypting program；chat system

1 引言
1.1 课题背景
自从TCP/IP协议族成为计算机通信的主要网络协议，基于该协议族开发的网络应用程序数不胜数。聊天程序便是其中之一。聊天程序使人们可以通过互联网及时传送消息，让远在千里之外的人们畅所欲言.传统的聊天程序在给人们带来方便的同时也逐渐暴露出一些安全隐患.前不久网上登出了这样一则新闻:上海某银行的白领丽人,因为聊天程序受监控被同事知道了个人隐私，被迫辞去了月薪三万余元的工作。于是聊天程序的安全性受到了人们的广泛关注。
1.2 国内外研究现状
从国内外对聊天程序的加密情况看，大多数处理方式是在现有的聊天程序基础之上添加相应的加密插件来实现加密。比较典型的例子是Linux平台下的多集成聊天程序Gaim，其中集成了ICQ、MSN、QQ等现今主流国内外聊天程序。普遍的聊天程序没有经过加密而直接传输聊天明文。Gaim通过添加插件程序对未加密的聊天程序进行加密传输，通信双方需要只要同时安装加密插件就可以顺利的对聊天内容进行加密解密。这其中存在一个现而易见的问题：要是一方加入了加密插件而另一方却没有相应的解密程序显然双方不能正确通信。
1.3 本课题研究的意义
聊天程序是否加密关系着用户的切身利用。为了保卫公民隐私权不受到网络黑客的不法侵犯,开发加密传输信息的聊天程序有着重大意义。聊天程序的加密特性对用户应该是透明的.正如前面分析，如果以安装插件的方式加密聊天程序很可能造成通信双方加密不一致的情况。因此将加密算法内嵌入聊天程序可以保证通信双方均能正常通信。
传统的对称加密算法如DES虽然可以快速的加密和解密明文，然而其密钥难以分配和管理。如果让通信双方相互约定密钥显然是不合适的，因此最好的方式是由一方产生密钥然后传送给另一方.基于公钥的非对称加密体制的引入正是用于解决对称加密算法在密钥管理上的不足，但是非对称加密算法如RSA存在运算强度过大、费时较长等问题。如果直接用于加密聊天程序，其生成密钥和加密解密所需时间是人们在通信过程中所不能容忍的,采取将两种加密算法相结合的方式可以很好的解决以上问题，从而达到安全快速的加密数据.

2所采用技术的先进性分析
2.1 DES算法
DES是Data Encryption Standard（数据加密标准)的缩写。它是由IBM公司研制的一种加密算法,美国国家标准局于1977年公布把它作为非机要部门使用的数据加密标准，二十年来,它一直活跃在国际保密通信的舞台上，扮演了十分重要的角色.
DES是一个分组加密算法，它以64位为分组对数据加密。同时DES也是一个对称算法：加密和解密用的是同一个算法。它的密钥长度是56位(因为每个第8位都用作奇偶校验），密钥也可以是任意的56位数，而且可以任意时候改变。其中有极少量的数被认为是弱密钥，但是很容易避开它们。所以保密性依赖于密钥。
2。2 RSA算法
1978年，美国麻省理工学院(MIT)的研究小组成员Ronald L Rivest、Adi Shamir、 Leonard Adleman提出了一种基于公开密钥密码体制的优秀加密算法－－RSA算法。RSA的取名就是来自这三位发明者姓氏的第一个字母。该算法以其较高的保密强度逐渐成为一种广为接受的公钥密码体制算法。RSA算法是一种分组密码体制算法,它的保密强度是建立在具有大素数因子的合数，其因子分解NP(Nondeterministic Polynomial）完全问题这一数学难题的基础上的，因此RSA算法具有很强的保密性.
RSA算法研制的最初目标是解决DES算法秘密密钥利用公开信道传输分发困难的难题，而实际结果不但很好地解决了这个难题；还可利用RSA来完成对消息的数字签名以防对消息的抵赖；同时还可以利用数字签名发现攻击者对消息的非法篡改，以保护数据信息的完整性。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作.RSA是被研究得最广泛的公钥算法,普遍认为是目前最优秀的公钥方案之一。RSA得到了世界上的最广泛的应用，并于1992年ISO国际标准化组织在其颁发的国际标准X。509中,将RSA算法正式纳入国际标准。
2。3 线程池
在传统的UNIX模型中，当一个进程需要另一个实体来完成某事时，它就fork一个子进程并让子进程去执行处理。Unix上的大多数网络服务器程序就是这么编写的，父进程accept一个连接,fork一个子进程,该子进程处理与该连接对端的客户之间的通信.
尽管这种范式多少年来一直良好地服务着,fork调用却存在一些问题:1
fork是昂贵的.fork要把父进程的内存映象拷贝到子进程，并在子进程中复制所有描述字，如此等等。2 fork返回之后父进程之间信息的传递需要进程间通信（IPC)机制.调用fork之前父进程向尚存在的子进程传递信息相当容易。因为子进程将从父进程数据空间及所有描述字的一个拷贝开始运行。然而从子进程往父进程返回信息却比较费力.
线程有助于解决这两个问题。线程有时称为轻权进程(lightweight process)，因为线程比进程“权重轻些".也就是说，线程的创建可能比进程的创建快10~100倍。
线程池是指在服务器启动阶段预先创建一系列线程阻塞于accept调用,每个客户由当前可用线程池中的某个（闲置)线程处理.这种处理方式比通常的客户连接到来时临时创建线程为其服务要快得多.可以获得很好的性能加速。

3系统需求分析
3。1聊天程序功能分析
1 注册功能
通常聊天程序需要用户名和密码才能使用,所以需要实现web注册功能，这样用户可以很方便的通过web网站注册自己的用户名并取得密码，还可以在服务器上存储个人相关信息以便他人查看.
2 登陆功能
用户在聊天之前需要输入用户名和密码进行登陆以便获取自身相关信息和好友相关信息，故登陆过程中服务器需对用户名和密码进行必要的核对.
3 聊天功能
这是聊天程序的主要功能。用户之间的相互通信必须及时快速的由服务器转发.
3。2 加密算法
由于是加密聊天程序，故对聊天明文的加密算法应选取加密速度相对较快的对称加密算法（如：DES)，又由于DES的加密密钥是不能公开的秘密密钥，故对DES的密钥应加密传送,所以应采用非对称的公钥加密算法（如RSA）用以分发DES密钥。
DES加密算法：
作为对称加密算法中的DES加密算法由于其加密过程是固定不变的,故应考虑其密钥的生成。由于弱密钥存在的可能性，还应该考虑如何避免生成弱密钥。因为差分分析法的提出可以快速的破解少于16轮迭代的DES算法，故应保证其迭代次数至少为16轮。
RSA加密算法：
由于RSA是基于大素数因子分解这一数学难题提出的，故RSA中公钥和私钥的产生应重点考虑。又由于RSA的运算强度较大，故还应考虑如何加速其运算速度。

4 系统总体设计和模块划分
4.1 系统总体设计

图4.1系统设计
如图4。1所示,本系统采用C/S模式。
1 用户通过web应用程序注册帐号，然后用注册的帐号登陆聊天程序服务器。
2 客户端产生生成DES密钥，服务器端在启动时初始化产生RSA公钥和私钥。当客户端向服务器发起连接时，服务器送出RSA公钥,客户端用取得的公钥加密产生的DES私钥回传服务器。
3 最后服务器与客户端双方的通信均由DES加密算法加密通信明文.

4。2 模块划分
4.2.1 DES算法模块
1 加密算法3个主要步骤
第一步，初始置换IP

图4.2 初始置换表IP
图4。2为初始置换表IP,64bit输入明文经过该表完成初始置换。

第二步，16轮迭代

图4.3 16轮迭代
图4。3为DES16轮迭代，将经过初始置换的数据分成Li和Ri两部分。将Ri直接交换为Li+1，Li与Ri经过f函数处理后的数据相异或得Ri+1,最后一轮不做交换。
第三步，逆置换

图4.4 逆置换表（IP-1)
图4.4为逆置换表(IP—1），经过16轮迭代后通过该表置换得到输出的密文。
2 子密钥的产生

图4.5 生成子密钥
图4。5为子密钥生成过程，将64bit初始密钥经过PC—1表置换为56bit输入,分为Ci, Di两组分别进行LS循环左移,再经过PC—2表压缩为48bit子密钥.如此循环16轮生成16组子密钥。
4.2.2 RSA算法模块
1 大数的运算
加法运算:
设定相应的进位变量c，按位相加，如ri = ai + bi + c，当ai + bi + c 〉 m （m为权值)，c送1，ri = (ai + bi + c) mod m， 否则c送0。
减法运算：
设定相应的借位变量c，按位相减，如ri = ai – bi + c，当ai < bi时，c送m （m为权值),还要将ai高一位减1，如过高位连续为0则依次置m – 1，一直到第一个非0位并将其减1，否则c送0。
乘法运算：
设定相应的进位变量c，和一个取当前结果位值变量d,双重循环。外层循环依次取运算数A的相应位，内层循环依次取B的相应位。r(i + j) = d + ai * bj + c，当d + ai ＊ bi + c > m （m位权值），c送ri/m （m为权值)，d为从对应的内外循环位之和(i + j)对应的结果位上取得的值。r（i + j）暂时存入对应的结果位。
除法运算：
假设A为被除数，B为除数。当A 〉 B,将B扩大到A相同位数，循环做A = A – Bk (扩充后的B），商位qi = qi + 1，最后A为余数。
取余运算：
依除法运算输出余数A。
乘方运算：
与乘法运算一样设有进位变量c和取当前结果位值变量d。依然分内外两层循环。外层循环中d = r （2 ＊ i)，r（2 * i） = d + ai ＊ ai，在此仅计算相同位ai的乘积存入结果位r（2 ＊ i）中。内层循环d = r (i + j），r(i + j) = d + 2 ＊ ai * aj + c，这里由于乘数A和被乘数B相等，故可以采用2 ＊ ai * aj,这种方式提前运算对应位。可以看出这种预处理方式加快了运算速度。
模幂运算：
将模幂运算转化为乘模运算。定理：（a * b) mod n = (（a mod n） * （b mod n）) mod n。计算A^m mod n:令c = 1，如果m = m % 2 == 0 循环计算 A = （A ＊ A） mod n 否则 m = m – 1，c = （A ＊ c) mod n。最后输出c。
2 选取P,Q
先以生成随机数的方式生成随机奇数A、B.再让A、B依次通过Miller-Rabin素性测试.
Miller-Rabin素性测试：先计算出m、j，使得n—1=m＊2^j，其中m是正奇数，j是非负整数,随机取一个b，2<=b，计算v=b^m mod n，如果v==1，通过测试,返回。令i=1，循环以后步骤,如果v=n-1，通过测试，返回.如果i==j，非素数，结束.v=v^2 mod n，i=i+1。
3 欧几里德算法求a,b最大公因数和逆元
定理：gcd （a, b） = gcd (b， a mod b) （设a 〉 b)
r = a mod b, a = b，b = r 循环以上三步直到r = 0， 则a为所求最小公因数。r = a mod b =〉 x * a + y ＊ b = r。 x称为a的逆元。在每步循环过程中将前一步中的r代入下一步中合并后可求得逆元x。
4.2.3 DES和RSA安全性讨论
1 弱密钥
所谓的弱密钥是指在所有可能的密钥中，有某几个特别的密钥，会降低DES的安全性，所以使用者一定要避免使用这几个弱密钥。而弱密钥产生的原因是由于子密钥产生过程的设计不当所导致的。
由子密钥产生的过程来看，假设有某个初始密钥经过密钥初始置换表置换，使得寄存器C0与D0的内容成为全是“0”或全是“1”的数据。如此一来，不管以后的每一轮中之循环左移函数是如何地变化，Ci与Di的内容并不会有所改变的.换句话说，这样的初始密钥，将会产生16个一摸一样的子密钥。如此一来将大大地降低DES的安全性。
弱密钥有另外一个特性－对弱密钥而言，其加密与解密的过程是完全一样的。我们知道DES的加密与解密过程中，唯一的不同在于子密钥的使用顺序是相反的。然而对弱密钥而言，因为其所衍生的16个子密钥是完全相同的，故子密钥之间也就毫无顺序之分了。
2 半弱密钥
除了上述的弱密钥之外，还有另外一种称之为半弱密钥的初始密钥。其特性是此类初始密钥所产生的子密钥，只有两种可能。而每一种可能的子密钥，刚好各出现8次。
假设现在有两个位串:A＝0101…0101，与B＝1010…1010,那么无论如何对A做循环左移动作，其结果不是A就是B。当然对B做循环左移动作也会得到一样的结果。如果对某个弱密钥而言，它满足以下两个条件,那么它就属于以上所谓的半弱密钥了。
（1)子密钥排列中的C(或D）寄存器只含有0101,…，0101或1010,…,1010这两种形式的数据.
（2）另一个寄存器D（或C)含有0000，…，0000,1111，…,1111，0101，…，0101或1010，…,1010任何一种形式的数据。
3 差分分析法
差分分析法基本上是属于选择明文攻击法。但在某些特定的情形下,也可用于已知明文攻击。这个方法简单地说，就是分析特殊明文配对（Plaintext Pair)的差值相对应的密文配对（Ciphertext Pair）的差值所产生的影响。这里所谓的差值是指两个明文(或密文)之间做异或（XOR）所得到的值。
这个做法的主要概念在于差值的运算会使得DES变得简单许多。我们知道DES可看做一部非常复杂的非线性机器，即使知道某一明文对应的密文，若无法得知密钥,也很难去推导出这一部机内部的数据流。当在差值的概念下，就有机可趁了.
对DES中的某个差值而言，最多的可以有2的64次方个明文（或密文)配对与之对应。差分密码分析法所在乎的是差值本身,而非其所对应的明文（或密文）配对。而某些特殊的差分密码分析法就是选取许多拥有相同特征值的明文配对，加密后得到相对应的密文配对，再借着特征值与这些密文配对推导出一些可能的密钥，并附与可能的概率，最后再选出最有可能者。
B. RSA安全性讨论
不可使用公共的模N
在某些情况下，我们假设有一密钥产生中心（Key Generation Center, KGC），利用RSA系统产生一公共模N = pq.此中心接着产生许多对的加密与解密密钥｛ei,di}，并将解密密钥di秘密传送给使用者i，且公布ei为使用者i的公开密钥。此系统的优点为密钥管理非常简单,因为系统中使用公共的模(N），不会有Reblocking问题产生，且可节省公开密钥的存储空间。不过，RSA系统使用公共的模,却可能招致下列三个主要的问题，使得此系统并不安全.
1 若相同的明文m分送给两个不同的使用者，则此系统可能变得不安全
设预将明文m加密后分送给使用者i及j，则其密文分别为Ci = m^ei mod N及Cj = m^ej mod N。
若使用者i与j的公开密钥ei与ej互素，则由欧几里德算法可求得两整数r及s使得rei + sej = 1。
很明显地，r或s一定有一个为负数，即r = -｜r|。若Ci与N互素（若不是的互,则我们可利用最大公因子方法求出p或q，尽而分解N），则Ci的乘法逆元Ci-1存在，并可被轻易求出。由下式我们可以容易求出明文m:
(Ci-1)^|r｜（Cj)^s = （m^ei）^—|r|(m^ej)^s = m^(rej + sej） = m mod N
因此,若有相同的明文分送给两个不同的使用者,且此二使用者的公开密钥为互素，则此系统并不安全。
2 拥有一对的加密/解密密钥就能因子分解N
Delaurentis提出一种概率算法，使得拥有一对加/解密密钥的人就能因子分解N.其基本概念为找出一整数b使得
(1) b^2 = 1 mod N
(2) b ！= +- 1 mod N
(3) 1 〈 b 〈 N
由基本数论知，若N = pq，满足上述条件的b共有两个。若能找出任一个，则我们即可将N因子分解。因为b^2 -1 = 0 mod N， 则(b + 1)(b - 1) = 0 mod N, 所以(b + 1)（b -1) = kN = kqp， 其中k为整数.
由于1 < b 〈 N,所以不等式0 < b – 1 < b + 1 〈 N = qp成立。因此p及q不能同时整除b – 1或b + 1，也即b – 1与N必有一公因子p或q。利用欧几里德算法,求GCD（b – 1， N），即可求得p或q，因此可以将N因子分解。
3 拥有一对加/解密密钥
能在不必分解N情况下，求出另一对加解密密钥。
设已拥有一对加/解密密钥e及d，则已给出一加密密钥e1(GCD（e1, f（N)） = 1)，即可在不需因子分解N情况下，求出其解密密钥d1，满足e1d1 = 1 mod f(N）。
（1） 利用欧几里德算法求出e1与ed – 1的最大公因子g。
（2） 求出（ed — 1） / g = f。
（3） 利用欧几里德算法，求出两整数r1及d1，使得r1f + d1e1 = 1.
由于g整除ed – 1，因此f必为整数,且f必为f(N)的整数倍,这是由于f（N)整除ed – 1，且g与f（N）互素。当f求出后，第（3）步中，我们求出d1即满足d1e1 = 1 mod f（N)。因为f为f（N）的整数倍。
4.2.4 聊天程序模块
1、数据库设计
用户信息表User_Infor （存储注册用户的信息）
CREATE TABLE User_Info
(
user_id INTEGER AUTO_INCREMENT PRIMARY KEY，
user_name VARCHAR (50） NOT NULL,
user_passwd VARCHAR （10) NOT NULL，
user_sex VARCHAR （10)，
user_age INTEGER，
user_address VARCHAR （100)，
INDEX (user_name）
) ENGINE = InnoDB; #指定存储引擎
好友关系表Friend_Index (记录用户添加的好友)
CREATE TABLE User_Online
（
user_id INTEGER PRIMARY KEY，
ip_address VARCHAR (100） NOT NULL,
conn_socket INTEGER NOT NULL,
FOREIGN KEY （user_id） REFERENCES User_Info （user_id）
) ENGINE = InnoDB;
在线用户记录表User_Online （记录已登陆的在线用户和与服务器建立的套接口)
CREATE TABLE User_Online
(
user_id INTEGER PRIMARY KEY，
conn_socket INTEGER NOT NULL,
des_key VARCHAR (30) NOT NULL,
FOREIGN KEY （user_id） REFERENCES User_Info (user_id）
） ENGINE = InnoDB；
消息记录表Messages （缓存发给离线用户的消息）
CREATE TABLE Messages
（
message_id INTEGER AUTO_INCREMENT PRIMARY KEY，
from_id INTEGER NOT NULL,
to_id INTEGER NOT NULL，
body TEXT NOT NULL,
date_posted TIMESTAMP NOT NULL,
INDEX （to_id），
FOREIGN KEY (from_id） REFERENCES User_Info (user_id）,
FOREIGN KEY （to_id) REFERENCES User_Info （user_id)
） ENGINE = InnoDB；
2、Web注册页面模块
用户管理：用于管理用户的注册和登陆.
添加好友：查询数据库中注册用户，选择要添加的好友插入数据库。
3、聊天程序服务器端
初始化套接口，初始化RSA算法生成公钥和私钥 －〉 创建线程池等待连接 －〉 送出RSA公钥 －> 接收DES密钥 －> 验证登陆信息 －> 服务登陆客户负责消息转发。
4、聊天程序客户端
初始化套接口，生成DES密钥，向服务器发起连接 －> 取得RSA公钥加密DES密钥后回传服务器 －> 发送登陆信息 －> 接收好友信息 －> 创建发送消息线程和接收消息线程与好友通信.
5系统实现
5.1 DES核心代码
l DES类声明
class DES
{
public :
DES （unsigned long long）; //构造函数仅传入密钥
void encrypting (unsigned long long ＆)； //加密函数
void decrypting （unsigned long long ＆）; //解密函数
private :
//明文处理==============================================
bitset<64〉 IP_permute （unsigned long long）； //初始置换
unsigned long long IP_1_permute （bitset<64>）； //逆置换
//加密过程==============================================
bitset<48〉 E_permute （bitset<32>)；//E盒子置换
unsigned long long b1b6 （bitset<48>， int， int）；
unsigned long long b2b3b4b5 （bitset〈48〉, int， int， int， int）;
bitset〈32〉 SBox_Process (bitset〈48〉); //S盒子置换
void P_permute （bitset〈32> ＆）; //P置换
bitset<32> f (bitset〈32〉, bitset〈48〉)； //f函数
//子密钥生成============================================
bitset<56〉 PC_1_permute (unsigned long long）； //PC-1置换
void LSi （bitset〈28> ＆， int）； //循环左移
bitset<48〉 PC_2_permute (bitset<56〉)； //PC—2置换
void create_k （unsigned long long)；
bitset<48〉 k［16]; //子密钥数组
}；
l 子密钥生成
void DES :： create_k （unsigned long long key)
{
bitset〈56〉 CiDi (0）；
CiDi = PC_1_permute （key); //PC—1置换
bitset<28> Ci (0）, Di (0)；
for （int i = 0; i < 56; i++)
｛ //将经过PC—1置换的数据分成左右28比特
if (i < 28）
Ci［i] = CiDi［i];
else
Di[i — 28］ = CiDi［i］;
｝
for （int i = 0； i < 16; i++） //16轮循环
{
LSi (Ci, LSI[i］）; //LS循环左移
LSi （Di, LSI[i］); //LS循环左移
for （int j = 0; j 〈 56； j++） //再将28比特数据合为56比特数据
｛
if （j 〈 28)
CiDi［j］ = Ci[j]；
else
CiDi［j] = Di［j — 28];
}
k[i］ = PC_2_permute (CiDi)； //存入子密钥数组
｝
}
l 加密算法
void DES :: encrypting （unsigned long long ＆msg）
{
bitset<64〉 ip （0）;
bitset〈32> Li （0)， Ri （0)， buf (0）；
ip = IP_permute （msg）; //IP初始置换
for （int i = 0; i 〈 64； i++) //等分成左右32位数据
｛
if （i 〈 32）
Li[i］ = ip[i];
else
Ri［i — 32］ = ip[i］；
｝
for (int i = 0; i 〈 16; i++） //16轮迭代
{
if （i != 15）
｛
buf = Li；
Li = Ri; //Li = Ri—1
Ri = f (Ri， k［i]); //f函数处理Ri-1
Ri ^= buf; //Ri = f (Ri-1， ki） XOR Li-1
｝
else
｛ //最后不再互换
buf = Ri；
Ri = f （Ri, k[i]）；
Li ^= Ri;
Ri = buf；
｝
}
for （int i = 0； i < 64； i++) //将两部分32数据组合回64位数据
{
if (i 〈 32）
ip［i] = Li[i]；
else
ip[i] = Ri[i — 32］；
}
msg = IP_1_permute （ip）; //IP-1 逆置换
return;
}
5。2 RSA核心代码
l 大数类声明
class BigNum
｛
public :
BigNum （char *a = NULL, unsigned long n = 0， Status s = 0）；
～BigNum （） ｛}；
BigNum absadd (BigNum， BigNum); //绝对值相加
BigNum abssub （BigNum， BigNum）； //绝对值相减
BigNum operator + (BigNum）； //加号重载
BigNum operator — （BigNum）; //减号重载
BigNum operator ＊ （BigNum）; //乘号重载
BigNum operator / (BigNum）; //除号重载
BigNum operator ％ （BigNum）； //取余重载
BigNum square （)； //乘方运算
BigNum ＆ operator <<= （unsigned long）; //循环左移
BigNum & operator 〉>= （unsigned long）; //循环右移
friend bool operator 〈 (BigNum， BigNum)； //〈重载为友元
friend bool operator 〉 （BigNum, BigNum）； //>重载为友元
friend bool operator 〉= （BigNum， BigNum）； //>=重载为友元
friend bool operator == (BigNum, BigNum）; //==重载为友元
friend bool operator != (BigNum， BigNum）； //！=重载为友元
void print (）；
unsigned long getsize （) {return （size)；}
char ＊getnum () {return (num);｝
private ：
char num［MAXNUM］；
unsigned long size；
Status symbol; //正数为1,零为0,负数为-1
｝;
l 模幂运算
BigNum modexp （BigNum x, BigNum r, BigNum p）
{ //依据定理 （a * b）mod n = ((a mod n） ＊ (b mod n)） mod n
BigNum a， b, c ("1"， 1， 1), one （"1", 1， 1）， zero (”0”, 1， 0)， two （”2”， 1， 1）;
a = x;
b = r；
while （b ！= zero）
｛
if (b ％ two == zero) //是否为偶数
｛
b = b / two; //降阶
a = a。square () % p； //乘方对p取余
continue;
｝
b = b - one;
c = (a * c） % p; //乘模运算
｝
return （c）；
｝
l 欧几里德计算最大公因数和逆元
BigNum RSA ：: gcd （BigNum &a， BigNum ＆b, BigNum x， BigNum y）
{ //gcd （x, y) = gcd （y, x mod y）, 对式子ax + by = r,
//每一步迭代中ai = ai-2 – q * ai-1, bi = bi-2 – q ＊bi—1
//其中q 为当前这步的商
BigNum zero ("0”, 1， 0);
BigNum q， r， ai_2 (”1”, 1, 1）, ai_1 （"0"， 1, 0）, bi_2 (”0”, 1， 0)， bi_1 （”1"， 1, 1);
if （x < y） //x、y互换
{
Big