计算机与信息工程学院
《密码学课程设计》报告
(2013/20##学年 第 二学期)
题 目: Diffie-Hellman密钥交换协议
系 别: 计算机与信息工程学院
专 业: 信息安全
班 级:
学 号:
姓 名:
20##年05月30日
(一)题目Diffie-Hellman密钥交换协议
(二)开发工具与环境:
window7环境下的Visual Studio2010
(三)设计原理: Diffie-Hellman算法的安全性基于求离散对数的困难性。算法的惟一目的是使得两个用户能够安全地交换密钥,得到一个共享的会话密钥,算法本身不能用于加、解密,因此,这里用产生的最终的密钥作为仿射变换加密的密钥来实现对消息的加解密。
Diffie-Hellman的设计原理如下:A和B两方要生成共享密钥Y,则首先选定一个大素数p,以及p的原根g,p,g为双方共享,用户A选择一保密的随机证书Xa,并将Ya=g^Xa modp发送给用户 B,类似,B选择一保密的随机整数Xb,并将Yb=g^Xb modp发送给用户A.之后A和B分别由Y=Yb^Xa modp和Y=Ya^Xb计算出的就是共享密钥。因为Xa,Xb是保密的,敌手只能得到p,a,Ya,Yb,要想得到Y,必须得到Xa,Xb中的一个,这意味着要求离散对数,因此敌手求Y是不可行的,保证了安全。
(四)系统功能描述及软件模块划分
系统需手动输入随机数Xa,Xb,点击确定后可以隐藏输入的随机数。在原文框中输入需要处理的原文,选择加密或者解密按钮,在结果框中会生成对应的解密或者加密的结果。
系统共分为两个模块,一块是Diffie-Hellman模块,用来处理输入的随机数,系统随机生成大素数并找到该大素数的原根,再按照算法思想最终生成共享密钥Y.Mainwindow 模块通过函数接收Diffie-Hellman模块的密钥
(五)设计的核心代码
MainWindow::MainWindow(QWidget *parent) :
QMainWindow(parent),
ui(new Ui::MainWindow)
{ ui->setupUi(this);
label1=findChild<QLabel*>("label1");
label2=findChild<QLabel*>("label2");
label3=findChild<QLabel*>("label3");
label4=findChild<QLabel*>("label4");
text1=findChild<QTextEdit*>("textEdit1");
text2=findChild<QTextEdit*>("textEdit2");
yuanwen=findChild<QTextEdit*>("textEdit3");
jieguo=findChild<QTextBrowser*>("textBrowser1");
queren=findChild<QPushButton*>("pushButton1");
jiami=findChild<QPushButton*>("pushButton2");
jiemi=findChild<QPushButton*>("pushButton3");
fanhui=findChild<QPushButton*>("pushButton4");
init();}
MainWindow::~MainWindow()
{delete ui;}
void MainWindow::on_pushButton1_clicked()
{ unsigned __int64 p,g,Alice_Y,Bob_Y,Alice_key,Bob_key;
DiffieHellman Alice,Bob;
Alice.init();
Bob.init();
Alice.CreatePrimeAndGenerator();
p=Alice.GetPrime();
g=Alice.GetGenerator();
Bob.SetPrimeAndGenerator(p,g);
Alice.CreatePrivateKey(text1->toPlainText().toInt());
Bob.CreatePrivateKey(text2->toPlainText().toInt());
Alice_Y=Alice.GetPublicKey();
Bob_Y=Bob.GetPublicKey();
Alice_key=Alice.GetKey(Bob_Y);
Bob_key=Bob.GetKey(Alice_Y);
this->Setkey(Alice_key);}
void MainWindow::on_pushButton2_clicked()
{eguo->clear();
QString jg,yw;
yw = yuanwen->toPlainText();
for(int i = 0;i < yw.length();++i){
jg.append(this->JiaMi(yw[i])); }
jieguo->append(jg);}
void MainWindow::on_pushButton4_clicked()
{init();}
void MainWindow::on_pushButton3_clicked()
{ jieguo->clear();
QString jg,yw;
yw = yuanwen->toPlainText();
for(int i = 0;i < yw.length();++i){
jg.append(this->JieMi(yw[i])); }
jieguo->append(jg);}
class DiffieHellman{
public:
DiffieHellman(){
p=0; g=0; X=0; Y=0;Key=0; }
void init();
int CreatePrimeAndGenerator();
unsigned __int64 GetPrime();
unsigned __int64 GetGenerator();
unsigned __int64 GetPublicKey();
unsigned __int64 GetKey(unsigned __int64 HisPublieKey);
int SetPrimeAndGenerator(unsigned __int64 Prime,unsigned __int64 Generator);
int CreatePrivateKey(int key);
private:
__int64 GetRandNum( void );
unsigned __int64 GenerateRandomNumber(void);
__int64 XpowYmodN(__int64 x, __int64 y, __int64 N);
bool IsItPrime (__int64 n, __int64 a) ;
bool MillerRabin (__int64 n, __int64 trials);
unsigned __int64 GeneratePrime();
int CreatePublicKey();
int GenerateKey(unsigned __int64 HisPublicKey);
unsigned __int64 p; //素数
unsigned __int64 g; //对应的本原根
unsigned __int64 X; //私钥
unsigned __int64 Y; //公钥
unsigned __int64 Key;//通讯密钥};
void DiffieHellman::init(){
p=0; g=0; X=0; Y=0; Key=0;}
__int64 DiffieHellman::GetRandNum( void )
{
srand((unsigned)time(0));
__int64 tmp = (__int64)rand()*(__int64)rand();
return tmp;}
unsigned __int64 DiffieHellman::GenerateRandomNumber(void)
{ static unsigned long rnd = 0x41594c49;
static unsigned long x = 0x94c49514;
LFSR(x);
rnd^=GetRandNum()^x;
ROT(rnd,7);
return (unsigned __int64)GetRandNum() + rnd;}
__int64 DiffieHellman::XpowYmodN(__int64 x, __int64 y, __int64 N)
{ __int64 tmp = 0;
if (y==1) return (x % N);
if ((y&1)==0)
{ tmp = XpowYmodN(x,y/2,N);
return ((tmp * tmp) % N); }
else
{tmp = XpowYmodN(x,(y-1)/2,N);
tmp = ((tmp * tmp) % N);
tmp = ((tmp * x) % N);
return (tmp) }}
bool DiffieHellman::IsItPrime (__int64 n, __int64 a)
{
__int64 d = XpowYmodN(a, n-1, n);
if (d==1)
return true;
else
return false;
}
bool DiffieHellman::MillerRabin (__int64 n, __int64 trials)
{ __int64 a = 0;
for (__int64 i=0; i<trials; i++)
{
a = (rand() % (n-3))+2;// gets random value in [2..n-1]
if (IsItPrime (n,a)==false)
{ return false; }
} return true; // n probably prime}
unsigned __int64 DiffieHellman::GeneratePrime()
{ unsigned __int64 tmp = 0;
tmp = GenerateRandomNumber() % MAX_PRIME_NUMBER;
//ensure it is an odd number
if ((tmp % 2)==0)
tmp += 1;
if (MillerRabin(tmp,5)==true) return tmp;
do
{ tmp+=2;
} while (MillerRabin(tmp,5)==false);
return tmp;}
int DiffieHellman::CreatePrimeAndGenerator()// 产生素数p,和它的本原根g
{ unsigned __int64 q;
bool f=true;
while(f){
p=GeneratePrime();
q=p*2+1;
if(MillerRabin(q,5)==true)
f=false;}
f=true;
while(f){
g=GenerateRandomNumber() % (p-2);
if(XpowYmodN(g, 2, p)!=1 && XpowYmodN(g, q, p)!=1)
f=false; }
return 0;}
unsigned __int64 DiffieHellman::GetPrime(){
return p;}
unsigned __int64 DiffieHellman::GetGenerator(){
return g;}
int DiffieHellman::CreatePrivateKey(int key){
X=key;
return 0;}
int DiffieHellman::CreatePublicKey(){
Y=XpowYmodN(g, X, p);
return 0;}
unsigned __int64 DiffieHellman::GetPublicKey(){
if(Y==0) CreatePublicKey();
return Y;}
int DiffieHellman::GenerateKey(unsigned __int64 HisPublicKey){
Key=XpowYmodN(HisPublicKey, X, p);
return 0;}
unsigned __int64 DiffieHellman::GetKey(unsigned __int64 HisPublicKey){
if(Key == 0){
Key=XpowYmodN(HisPublicKey, X, p); }
return Key;}
int DiffieHellman::SetPrimeAndGenerator(unsigned __int64 Prime,unsigned __int64 Generator){
p=Prime;
g=Generator;
return 0;}
(六)关键问题及解决方法
(1)用Diffie-Hellman生成的密钥Y可能与仿射变换加密的模数26和10不互素,因此加解密会出现错误。解决方法:把模数改为素数29和11,则无论生成的密钥是多少,必互素。
(2)
七)设计结果及验证
(八)总结
通过这次为期一周的课程设计,我对Diffie-Hellman密钥交换协议有了更深层次的理解,并在课程设计的过程中学会了生成大素数以及大素数的原根,虽然在课程设计过程中遇到很多问题,但是最终都在一次次的尝试下成功了,可能还是有很多不足,比如加密算法比较简单,未实现对汉字的加密解密等等,我依旧从中获益良多,更透彻的了解到密码学对现代信息社会起到的举足轻重的作用,