rsa.h

一个用RSA算法实现加密通信的聊天程序。

/***************"vlong.h"********************/
#ifndef __VLONG_H__
#define __VLONG_H__ 

#ifndef NULL
#define NULL 0
#endif

#ifndef DWORD
#define DWORD unsigned long
#endif

// Macros for doing double precision multiply
#define BPU ( 8*sizeof(DWORD) )       // 一个字节位 DWORD
#define lo(x) ( ((DWORD)(x)) & (DWORD)((((DWORD)1)<<(BPU/2))-((DWORD)1)) ) // lower half of DWORD
#define hi(x) ( ((DWORD)(x)) >> (BPU/2) )         // 生 1/2
#define lh(x) ( ((DWORD)(x)) << (BPU/2) )         // 实施

// Provides storage allocation and index checking
class flex_unit
{
public:
	DWORD n; // used units (read-only)
	flex_unit();
	~flex_unit();
	void clear(); // set n to zero
	DWORD get( DWORD i ) const;     // 获取 ith DWORD
	void set( DWORD i, DWORD x );   // 设置 ith DWORD
	void reserve( DWORD x );           // storage hint
	
	// Time critical routine
	void fast_mul( flex_unit &x, flex_unit &y, DWORD n );
//private: //lchen modi
	DWORD * a; // array of units
	DWORD z; // units allocated
};

class vlong_value : public flex_unit
{
public:
	DWORD share; // share count, used by vlong to delay physical copying
	long is_zero() const;
	DWORD bit( DWORD i ) const;
	void setbit( DWORD i );
	void clearbit( DWORD i );
	DWORD bits() const;
	long cf( vlong_value& x ) const;
	long product( vlong_value &x ) const;
	void shl();
	long  shr(); // result is carry
	void shr( DWORD n );
	void add( vlong_value& x );
	void xor( vlong_value& x );
	void and( vlong_value& x );
	void subtract( vlong_value& x );
	void init( DWORD x );
	void copy( vlong_value& x );
	DWORD to_unsigned(); // Unsafe conversion to DWORD
	vlong_value();
	void mul( vlong_value& x, vlong_value& y );
	void divide( vlong_value& x, vlong_value& y, vlong_value& rem );
};

class vlong // very long integer - can be used like long
{
public:
	// Standard arithmetic operators
	friend vlong operator +( const vlong& x, const vlong& y );
	friend vlong operator -( const vlong& x, const vlong& y );
	friend vlong operator *( const vlong& x, const vlong& y );
	friend vlong operator /( const vlong& x, const vlong& y );
	friend vlong operator %( const vlong& x, const vlong& y );
	friend vlong operator ^( const vlong& x, const vlong& y );
	friend vlong pow2( DWORD n );
	friend vlong operator &( const vlong& x, const vlong& y );
	
	friend vlong operator <<( const vlong& x, DWORD n );
	
	vlong& operator +=( const vlong& x );
	vlong& operator -=( const vlong& x );
	vlong& operator >>=( DWORD n );
	
	// Standard comparison operators
	friend long operator !=( const vlong& x, const vlong& y );
	friend long operator ==( const vlong& x, const vlong& y );
	friend long operator >=( const vlong& x, const vlong& y );
	friend long operator <=( const vlong& x, const vlong& y );
	friend long operator > ( const vlong& x, const vlong& y );
	friend long operator < ( const vlong& x, const vlong& y );
	
	// Absolute value
	friend vlong abs( const vlong & x );
	
	// Construction and conversion operations
	vlong ( DWORD x=0 );
	vlong ( const vlong& x );
	~vlong();
	friend DWORD to_unsigned( const vlong &x );
	vlong& operator =(const vlong& x);
	
	// Bit operations
	DWORD bits() const;
	DWORD bit(DWORD i) const;
	void setbit(DWORD i);
	void clearbit(DWORD i);
	vlong& operator ^=( const vlong& x );
	vlong& operator &=( const vlong& x );
	vlong& ror( DWORD n ); // single  bit rotate
	vlong& rol( DWORD n ); // single bit rotate
	friend long product( const vlong & x, const vlong & y ); // parity of x&y
	
	void load( DWORD * a, DWORD n ); // 读值, a[0]
	void store( DWORD * a, DWORD n ) const; // low level save, a[0] is lsw
	void load( char * a, DWORD n );	//自己添加
	void store( char * a, DWORD n ) const;	//自己添加


//private:
	class vlong_value * value;
	long negative;
	long cf( const vlong & x ) const;
	void docopy();
	friend class monty;
};

vlong modexp( const vlong & x, const vlong & e, const vlong & m ); // m 必须已添加

vlong gcd( const vlong &X, const vlong &Y ); // greatest common denominator
vlong modinv( const vlong &a, const vlong &m ); // modular inverse

vlong monty_exp( const vlong & x, const vlong & e, const vlong & m );
vlong monty_exp( const vlong & x, const vlong & e, const vlong & m, const vlong &p, const vlong &q );

class rng
{
public:
	virtual vlong next()=0;
};

class vlstr
{
public:
	virtual void put( const vlong & x )=0;
	virtual vlong get()=0;
};

vlong lucas ( vlong P, vlong Z, vlong k, vlong p ); // P^2 - 4Z != 0
vlong sqrt( vlong g, vlong p ); // 平方根的模 p


#endif// __VLONG_H__
/***************"vlong.h"********************/


/***************"rsa.h"********************/

#ifndef __RSA_H__
#define __RSA_H__ 

//#include "vlong.h"
		
#define LEVEL	64	
//当LEVEL=32表示1024位,LEVEL=64表示2048,LEVEL=128表示4096位的RSA

#define VL	LEVEL * 2
/*一次加密的数据块大小应该和m的比特相同，即使比它小就生成的密文都是m的比特
加/解密的数据VL*char字节，它最大长度就是LEVEL的长度，
但是因为它要比m小，所以定LEVEL*DWORD比特既绝对安全又可以使可以构造的plain小于m*/

struct PK	//公开密钥
{
	DWORD m[LEVEL];	//公开密钥中要用大整数用DWORD表示
};
struct SK	//私人密钥
{
	DWORD p[LEVEL / 2];
	DWORD q[LEVEL / 2];
};


struct MessageDollop	//要加密的数据块，先用BPK加密，再用ASK加密。
{
	char	text[LEVEL * 2];	//要加密的消息内容，规定是LEVEL*2字节
	DWORD	digital_ID[4];		//数字签名的标识(可以使他固定，用私钥加密它时必须小于m)，经过散列算法处理后...
	DWORD	messagePackage_ID[4];	//整条消息的标识(随机生成)，可以判断收方是否收到这条消息
	DWORD	messageDollop_ID[4];//这个消息块的ID(由message_ID随机生成)，把整个消息包的个块的messageDollop_ID进行异或后必须等于message_ID
	char	time[20];			//记录这条消息发出的时间，防止别人将我以前的消息发个收件人
	char	disuse[LEVEL * 2 - 22 * 4];	//无用的数据
	char	randCount[16];		//随机数，当requires=false时就要重新进行加密，就用这个数的改变使得它requires=true
	DWORD	nil[1];				//必须为零，这样就可以使得加密的大整数小于m了，但不能保证加密的数用另一个密钥加密就可以小于m了
};
/*如何进行数字签名呢？
《密聊》通过RSA实现的了消息通讯安全功能包括：
1. 身份验证，使收件人确信发件人就是他或她就是公开密钥所所对应的那个人；
2. 机密性，确保只有预期的收件人能够阅读邮件；
3. 完整性，确保消息在传输过程中没有被更改；
4. 消息到达确认，发件人确认收件人收到了消息。
*/

/*
传输协议格式为：
[head(16bit)]:[ID(16bit)]:[n(16bit)]:[data(...)]
其中head为发送的消息类型,ID为消息接收者的标志，n为明文的实际字节数，data为谈话内容。
消息类型包括：建立连接，退出连接，接收加密消息，发送公钥，接受成功的消息回复
ID可以为重要的消息，一般的等等
*/
//head收到的消息类型
#define HEAD_TEXT				1	//收到的是正文
#define	HEAD_REVERT_TEXT		2	//发出的正文就收到的是回复
#define HEAD_DISCONNECTION		4	//收到的是断开提示
#define HEAD_CLAIM_PUBLIC_KEY	8	//对方的请求获得公钥
#define	HEAD_REVERT_PUBLIC_KEY	16	//收到对方发过来的公钥
#define	HEAD_DIGITAL_SIGNATURE	32	//对方的数字签名，看看我这里有没有它的公钥，可以在请求获得它的公钥
#define HEAD_ZAIXIANBIAOJI		64	//在线通知
#define HEAD_VERSION 			128	//收到对方的版本通知，当前版本为1
#define HEAD_SENDFILE 			256	//发送文件给对方
#define HEAD_SYSTEM_MESSAGE		1024 //系统消息

//HEAD_DIGITAL_SIGNATURE的子类型
#define HEAD_DIGITAL_SIGNATURE_YES	1	//合格的数字签名
#define HEAD_DIGITAL_SIGNATURE_NO	2	//不合格的数字签名

//HEAD_SENDFILE的子类型
#define HEAD_SENDFILE_ENQUIRY		1	//询问对方需要文件吗？
#define HEAD_SENDFILE_CONCENT		2	//允许 
#define HEAD_SENDFILE_NO_CONCENT	4	//拒绝
#define HEAD_SENDFILE_CONCENT_RECEIVE 8	//拒绝
#define HEAD_SENDFILE_STOP			16	//中止发送或接收
#define HEAD_SENDFILE_VERSION_UPDATE 32 //文件传送版本处理
#define HEAD_SENDFILE_SUCCEED		64	//发送成功
#define HEAD_SENDFILE_NO_SUCCEED	128	//发送失败

//HEAD_DISCONNECTION的子类型
#define HEAD_DISCONNECTION_INFORM		1	//对方断开连接通知，我也要断开了
#define HEAD_DISCONNECTION_CLOSE		4	//对方关闭密聊

#define DATA_LENGTH				1024 * 4	//正文的最大长度，data是他的两倍
struct MessagePackage			//发送的消息数据包，它由许多消息块和一些其他信息组成
{
	int head;		//发送消息的类型
	int ID;			//类型中的子类的标识
	int n;			//明文的实际字节数
	char data[DATA_LENGTH * 2];//加密后的数据，一次最多发送4K字节，由许多消息块组成
};


class public_key
{
public:
	public_key();	//构造函数为了使得requires为1，派生类private_key也会调用这个基类中的构造函数的
	void	encrypt(MessagePackage &package);//加密消息包，正文的长度为package.n
	void	encrypt(MessageDollop &dollop);	//加密消息块
	//要求plain必须小于m
	vlong	encrypt( const vlong& plain );	// Requires 0 <= plain < m
	void	PK_to_vlong(PK pk);
	void	vlong_to_PK(PK &pk);
		
public:
	void	set_requires(int req);
	int		get_requires();
	int		requires;	//判断加密的数是否小于m
	vlong	m, e;
};

class private_key : public public_key
{/*private_key是从public_key派生出来的类*/
public:	
	void	create();	//生成m, e, p, q; 安全级别是2048位
	void	decrypt(MessagePackage &package);//解密消息包，正文的长度为package.n
	void	decrypt(MessageDollop &dollop);	//解密消息块
	//要求plain必须小于m
	vlong	decrypt( const vlong& cipher );// Requires 0 <= cipher < m
	void	SK_to_vlong(SK sk);
	void	vlong_to_SK(SK &sk);

public:
	vlong	p, q;
	// r1 and r2 should be null terminated random strings
	// each of length around 35 characters (for a 500 bit modulus)
};

#endif
/***************"rsa.h"********************/


/***************"prime.h"********************/
#ifndef __PRIME_H__
#define __PRIME_H__ 

//#include "vlong.h"

class prime_factory
{
  public:
  DWORD np;
  DWORD *pl;
  prime_factory( DWORD MP = 2000 ); // sieve size
  ~prime_factory();
  vlong find_prime( vlong & start );
  long make_prime( vlong & r, vlong &k, const vlong & rmin );
};

long is_probable_prime( const vlong &p );

#endif
/***************"prime.h"********************/