密码学课程设计实验报告
院 系 计算机科学与技术学院
专 业 信息安全
班 级 0703
学 号 xxxxxxxxxx
姓 名 xxxxxx
指导教师 xxxxxxxx
20## 年 3 月 18 日
目录
第一部分
一、实验目的... ４
二、实验环境及工具... ４
三、实验内容... ４
四、实验原理... ４
五、实验过程... 6
5.1设计思路... 6
5.2程序的实现部分... 11
六、程序测试... 12
6.1制定测试方案... 12
6.2测试效果... 12
七、源代码... 13
第二部分
一、实验目的... 14
二、实验环境及工具... 14
三、实验内容... 14
四、实验原理... 14
五、实验过程... 14
5.1设计思路... 14
5.2程序的流程图... 17
六、程序测试... 19
6.1制定测试方案... 19
6.2测试效果... 20
七、源代码... 20
第三部分
实验总结... 21
第一部分三圈DES的差分攻击
一、实验目的
通过课程设计，使学生进一步熟悉密码算法以及算法安全性的基本概念和原理；培养学生将密码理论和技术应用于实际的能力，使学生具备实施数据加/脱密和基本的密码分析的能力。
二、实验环境及工具
操作系统 Microsoft windows XP Home Edition 版本2002 Service Pack3
IDE环境 Microsoft Visual C++ 6.0 （SP6）
硬件环境 Intel（R）Atom? CPU N270 @1.60GHz,0.99GB的内存物理地址扩展
三、实验内容
题目：三圈DES的差分攻击；
要求：设计必需的界面环境，
（1） 输入明文及其对应的密文，产生相应的密钥
（2） 设计有好的窗口显示实验结果
四、实验原理
DES加密算法中的各种置换和扩展对差分没有影响，只有S盒可以阻挡差分；设 △X=X1⊕X2，△Y=Y1⊕Y2,其中X1和X2是S盒的六位输入，Y1和Y2是相应的四位输出即X1->S=Y1,X2->S=Y2；那么我们就可以以△X为行索引，以△Y为列索引建立一个64*16的二维矩阵，矩阵中的元素为可能的X值，我们把这个矩阵称作S盒的差分表，如下表所示：
我们一共可以构造八个差分表，下面我们给出三圈DES的加密过程（省略了IP置换）：
在选择明文攻击的情况下我们很容易保证△R0=0，那么我们就可以得到下列式子：
1)
△A=E（△L3）；
2) △B=P（△R3⊕△L0）
由于△L3、△R3、△L0在选择明文攻击时都是可求的,所以△A、△B也是可求的。
由于A是S盒的输入B是S盒的输出，我们又能求得△A、△B所以我们通过查差分表就可以把A局限在一个较小的范围内（在这个范围内穷举是可行的），又由于K3=A⊕C= A⊕E(L3)，所以子密钥K3也被局限到了一个较小的范围内而DES的主密钥K的穷举时间是K3的256倍,所以穷举K也是可行的。
五、实验过程
5.1设计思路
其实具体的算法已经在实验原理中给出了，我就是按照此原理设计了一个CAttack类用来进行差分攻击，下面是它的头文件：
// Attack.h: interface for the CAttack class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_ATTACK_H__5C3E3C22_41EC_4D03_8249_6A9D80ECFA07__INCLUDED_)
#define AFX_ATTACK_H__5C3E3C22_41EC_4D03_8249_6A9D80ECFA07__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "DES.h"
#define PLAINTEXT0 0
#define PLAINTEXT1 1
#define ENCRYPTOGRAPH0 2
#define ENCRYPTOGRAPH1 3
#define PLAINTEXT2 4
#define PLAINTEXT3 5
#define ENCRYPTOGRAPH2 6
#define ENCRYPTOGRAPH3 7
class CAttack : public CDES
{
public:
CAttack();
virtual ~CAttack();
/**************************************************************************
// 名称：InitAttack
// 功能：初始化8个S盒的差分表
// 参数：
// 返回：
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
void InitAttack();
/**************************************************************************
// 名称：TryAttack
// 功能：进行差分攻击
// 参数：key:[out] 返回破解出来的密钥
// 返回：成功为TURE，否则为FALSE
// 备注：成功为TURE,否则为FALSE
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
BOOL TryAttack(CString &key);
/**************************************************************************
// 名称：SetData
// 功能：设置破解参数
// 参数：nFlag:[in] 参数标志
// str: [in] 参数值
// 返回：成功为TURE,否则为FALSE
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
BOOL SetData(UINT nFlag,CString& str);
protected:
/**************************************************************************
// 名称：CalcDelta
// 功能：计算各个差分值
// 参数：byPlaintext0:[in] 明文串0
// byEncryptograph0: [in] 密文串0
// byPlaintext1:[in] 明文串1
// byEncryptograph1: [in] 密文串1
// 返回：
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
void CalcDelta(BYTE byPlaintext0[],BYTE byEncryptograph0[],BYTE byPlaintext1[],BYTE byEncryptograph1[]);
/**************************************************************************
// 名称：BitToUint
// 功能：二进制位串到整型数据的转换
// 参数：byt:[in] 二进制串
// len: [in] 二进制串的长度
// 返回：转换结果
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
UINT BitToUint(BYTE byt[],UINT len);
/**************************************************************************
// 名称：UintToBit
// 功能：整型数据到二进制位串的转换
// 参数：byt:[out] 二进制串
// len: [in] 二进制串的长度
// n: [in] 整数
// 返回：
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
void UintToBit(BYTE byt[],UINT len,UINT n);
/**************************************************************************
// 名称：CalcSubkey
// 功能：计算所有可能的子密钥K3
// 参数：R:[in] 密文的右半部分
// delX: [in] x的差分
// delY: [in] y的差分
// subkey:[out]可能的子密钥
// 返回：
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
void CalcSubkey(BYTE R[],BYTE delX[],BYTE delY[],CList<BYTE,BYTE> subkey[]);
/**************************************************************************
// 名称：CalcSubkey
// 功能：穷举56位主密钥
// 参数：
// 返回：成功为TURE，否则为FALSE
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
BOOL CalcMainKey();
/**************************************************************************
// 名称：Conjoin
// 功能：求子密钥交集的函数key2=key2交key1
// 参数：key2[in/out]:子密钥key2集合
// key1[in]:子密钥key1集合
// 返回：
// 备注：
// 更新：2010/3/10
// 作者：王凤伟
/**************************************************************************
void Conjoin(CList<BYTE,BYTE> key2[],CList<BYTE,BYTE> key1[]);
protected:
CList<BYTE,BYTE> m_s[8][64][16];// 用于保存差分表
CList<BYTE,BYTE> m_Key1[8]; // 用于保存可能子密钥集合的链表
CList<BYTE,BYTE> m_Key2[8]; // 用于保存可能子密钥集合的链表
BYTE m_byAttackedSubKey[ROUND][48]; // 3圈子密钥
BYTE m_byAttackedDesKey[56]; // 密钥
CString m_strAttackedDesKey; // 密钥串
BYTE m_byEncryptograph0[64]; // 密文0
BYTE m_byPlaintext0[64]; // 明文0
CString m_strPlaintext0; // 明文串0
CString m_strEncryptograph0; // 密文串0
BYTE m_byEncryptograph1[64]; // 密文1
BYTE m_byPlaintext1[64]; // 明文 1
CString m_strPlaintext1; // 明文串1
CString m_strEncryptograph1; // 密文串1
BYTE m_byEncryptograph2[64]; // 密文2
BYTE m_byPlaintext2[64]; // 明文2
CString m_strPlaintext2; // 明文串2
CString m_strEncryptograph2; // 密文串2
BYTE m_byEncryptograph3[64]; // 密文3
BYTE m_byPlaintext3[64]; // 明文3
CString m_strPlaintext3; // 明文串3
CString m_strEncryptograph3; // 密文串3
BYTE m_byDeltaL0[32]; // L0的差分
BYTE m_byDeltaL3[32]; // L3的差分
BYTE m_byDeltaR3_L0[32]; // R3的差分异或L0的差分
BYTE m_byDeltaA[48]; // A的差分（S盒的输入）
BYTE m_byDeltaB[32]; // B的差分（S盒的输出）
};
#endif // !defined(AFX_ATTACK_H__5C3E3C22_41EC_4D03_8249_6A9D80ECFA07__INCLUDED_)
5.2程序的实现部分
既然原理已经很清楚了，那么设计算法就不在困难了，这里我进一步给出算法的流程图，算法的详细内容请参照文件夹DES Attacker中的源程序。
说明：保存subkey时并不是真正的保存subkey的完整部分，而是将subkey
每6位分为一组保存，这样可以大大地减少存储空间（乘法原理）。
六、程序测试
6.1制定测试方案
为了便于测试，我编写了一个简单的三圈DES加密程序（DES 3 Rounds.exe），可以在DES 3 Rounds文件夹中找到，由用户自主选择密钥和满足条件的明密文对，然后把相应的参数输入到三圈DES差分攻击主程序(DES Attacker.exe)中，进行破译，最后与用户的密钥进行比较。
6.2测试效果
6.2.1生成破解参数
运行程序DES 3 Rounds.exe，输入相应的明文和密钥，生成参数
图6.2.1生成破解参数
6.2.1进行破译
运行DES Attacker.exe，并把刚才生成的破解参数复制到相应的编辑框中。
图6.2.1 进行破译
七、源代码
由于该程序的主框架是由MFC的AppWizard生成的，代码量很大，所以就不把源代码放到实验报告里了，若要看源代码请打开当前目录下的DES Attacker文件夹。
一、实验目的
通过课程设计，使学生进一步熟悉密码算法以及算法安全性的基本概念和原理；培养学生将密码理论和技术应用于实际的能力，使学生具备实施数据加/脱密和基本的密码分析的能力。
二、实验环境及工具
操作系统 Microsoft windows XP Home Edition 版本2002 Service Pack3
IDE环境 Microsoft Visual C++ 6.0 （SP6）
硬件环境 Intel（R）Atom? CPU N270 @1.60GHz,0.99GB的内存物理地址扩展
三、实验内容
题目：RSA解密密钥攻击；
要求：设计必需的界面环境，
（1） 加密密钥和解密密钥，求p、q，使n=p*q
（2） 设计有好的窗口显示实验结果
四、实验原理
定理：已知k1，k2求p和q，k1*k2=m* 
（n）+1，若能求x*x=1(mod n)的非平凡根，则可求p和q且p=（x+1,n）,q=(x-1,n)；
算法：（1）k1*K2-1->r;0->s;
（2）i+1->s,n=r/2;
（3）若2|r,则转（2），否则转（4）；（（2）-（3）步骤目的是求K1*K2=r*2^s）
（4）任取w，1<w<n-1;若（w,n）!=1,则p=(w,n);q=n/p,成功返回；否则转（5）；
（5）w^r->V;若V=1，则转（4）；否则转（6）
（6）r/2->r;V^r->tem;若tem=1则转（6）；
若tem=-1,则转（4）
否则p=（tem+1,n）,q=(tem-1,n)，成功
说明：算法的关键是第6步，在判断tem的值时，没有简单的判断tem=1或tem=-1时直接重新计算随机数W，而是对tem=1的情况进行了优化，即在tem=1时，把V的指数除二然后得到新的tem，这种优化是必要的，也是有效的。因为
V^(2^s)是收敛于1的，也就是说在随着s的增大V^(2^s)=1的概率将越来越接近1，而若不把指数缩小很难找到tem!=1的W值，这与利用穷举法分解N的效率相当。我曾经在没有优化的情况下做过实验，当时分解一个20位（16进制）的N，大约需要30分钟，而且都是在（w,n）!=1的条件下返回的（这正是穷举的结果），而经过优化后分解的时间只有几百毫秒的时间，而且都是在第六步返回的。
五、实验过程
5.1设计思路
具体的算法已经在实验原理中给出了，我就是按照此原理设计了一个CAttack类用来进行大数分解，而其中最关键的就是CAttack::Attack()函数，下面给出了源代码：
#define CHECK(x) {if( !(x) ) return false;}
bool CAttack::Attack()
{
static BigInt r,tem,tem1,v,sem,m,rands,rands1;
UINT i=0;
// 利用简单的加解密判断用户输入的参数是否正确
CHECK(m_OBigInt.PowMod(tem,m_OBigInt.Two,m_k1,m_n))
CHECK(m_OBigInt.PowMod(tem1,tem,m_k2,m_n))
CHECK(!m_OBigInt.Cmp(tem1,m_OBigInt.Two))
CHECK(m_OBigInt.Mul(tem,m_k1,m_k2))
CHECK(m_OBigInt.Sub(sem,tem,m_OBigInt.One))
tem=sem;
// 计算k1*k2-1=r*2^s
do
{
r=tem;
CHECK(m_OBigInt.Div(tem,rands,r,m_OBigInt.Two))
} while (!m_OBigInt.Cmp(rands,m_OBigInt.Zero));
// 2^s->m
CHECK(m_OBigInt.Div(m,tem1,sem,r))
// 生成随机数rands1
CHECK(m_OBigInt.RandVal(rands1,m_n.len+1))
do
{
do
{
B:
if (i>CYCLE)
{
i=0;
CHECK(m_OBigInt.RandVal(rands1,m_n.len+1))
}
i++;
// 生成满足条件1<rands<n-1的随机数rands
rands=rands1;
CHECK(m_OBigInt.Div(tem,rands,rands,m_n))
CHECK(m_OBigInt.Add(rands1,rands,m_OBigInt.One))
} while (!rands.len||!m_OBigInt.Cmp(rands,m_OBigInt.One)||!m_OBigInt.Cmp(rands1,m_n));
// 计算(rands,n)
CHECK(m_OBigInt.Glb(m_p,m_n,rands))
// (m_n,rands)=1，破解成功
if (m_OBigInt.Cmp(m_p,m_OBigInt.One))
{
CHECK(m_OBigInt.Div(m_q,tem,m_n,m_p))
CGfL::HalfByteToStr(m_strP,m_p.bit,m_p.len);
CGfL::HalfByteToStr(m_strQ,m_q.bit,m_q.len);
return true;
}
// 计算rands^r->v
CHECK(m_OBigInt.PowMod(v,rands,r,m_n))
CHECK(m_OBigInt.Add(tem,v,m_OBigInt.One))
// 若v=1或v=-1，则重新生成随机数
if (!m_OBigInt.Cmp(v,m_OBigInt.One)||!m_OBigInt.Cmp(tem,m_n))
{
goto B;
}
tem1=m; // 2^s->tem
loop: CHECK(m_OBigInt.Div(tem1,tem,tem1,m_OBigInt.Two)) // 计算tem1/2->tem1
CHECK(m_OBigInt.PowMod(tem,v,tem1,m_n)) // 计算v^tem1->tem
// 如果v^tem1=1，则计算v^(tem1/2)
if(!m_OBigInt.Cmp(tem,m_OBigInt.One))
{
goto loop;
}
CHECK(m_OBigInt.Add(tem1,tem,m_OBigInt.One))
}while(!m_OBigInt.Cmp(tem1,m_n)); // 如果v^tem1=-1则重新生成随机数rands，否则成功
CHECK(m_OBigInt.Add(rands,tem,m_OBigInt.One))
CHECK(m_OBigInt.Sub(rands1,tem,m_OBigInt.One))
CHECK(m_OBigInt.Glb(m_p,rands,m_n))// p=(tem+1,n)
CHECK(m_OBigInt.Glb(m_q,rands1,m_n))// q=(tem-1,n)
CGfL::HalfByteToStr(m_strP,m_p.bit,m_p.len);
CGfL::HalfByteToStr(m_strQ,m_q.bit,m_q.len);
return true;
}
声明：大数的计算我用的是东北大学的开源的算法库CBigInt和通用库CGfL来实现的，在这里我向作者表示感谢。
5.2程序的流程图
六、程序测试
6.1制定测试方案
为了便于测试，我编写了一个简单的RSA参数生成程序（Generate RSA.exe），可以在Generate RSA文件夹中找到，由用户自主选择N的长度，然后把生成相应的参数输入到RSA已知密钥攻击主程序(RSA Attacker.exe)中，进行大数分解，最后与生成参数中的p、q比较。
6.2测试效果
6.2.1生成破解参数
运行程序Generate RSA.exe，输入N的长度，生成参数
图6.2.1生成破解参数
6.2.1进行破译
运行RSA Attacker.exe，并把刚才生成的破解参数复制到相应的编辑框中。
图6.2.1 进行破译
七、源代码
由于该程序的主框架是由MFC的AppWizard生成的，代码量很大，所以就不把源代码放到实验报告里了，若要看源代码请打开当前目录下的RSA Attacker文件夹。
第三部分
实验总结
通过本次课程设计，我对密码学原理有了更深入的理解，特别是通过编程实现三圈DES差分攻击和RSA解密密钥攻击，对DES和RSA密码算法的理解更加深刻，而且对差分攻击技术有了更清晰的认识，对概率算法也有了新的认识。
在编程的过程中也遇到了一些问题，如RSA解密密钥攻击中，开始时只是简单的随机选取W，然后判断V^(2^(s-1))是否为+1或-1，若不成功则重新选择W，最终导致所有的V^(2^(s-1))几乎都为1，使该算法蜕化为一般的穷举算法。经过不断地跟踪和分析，发现指数必须足够小，概率算法才能发挥作用，因此对算法做了改进，果然，改进后的算法效率很高，令我兴奋不已。在三圈DES差分攻击中，由于计算差分△B=P（△R3⊕△L0）时，错误地认为△B=△R3⊕△L0，也给调试制造了很多麻烦。
总之，通过独立完成此次课设，在编程的过程中遇到了很多问题，通过反复地分析与调试，将它们一一解决，锻炼了自己的分析问题和解决问题的能力。同时，通过实际编写密码分析程序，也极大地激发了我对密码学的兴趣，希望在以后的学习中不断地积累和丰富密码学的相关理论与技术。