密码学实验第四组实验报告
- 格式：doc
- 大小：118.00 KB
- 文档页数：12
云南大学数学与统计学实验教学中心实验报告
第 1 页 共 12 页 云南大学数学与统计学实验教学中心实验报告
课程名称：密码学实验 学期：2013-2014学年第一学期 成绩：
指导教师： 陆正福 学生姓名：卢富毓 学生学号：20101910072
实验名称：McEliece 实验要求：必做 实验学时：4学时
实验编号： No.5 实验日期：2013/12/14 完成日期：2012/12/20
学院：数学与统计学院 专业 ： 信息与计算科学 年级： 2010级
一、 实验目的：
1.熟悉McEliece码的设计原理；
2.编程实现编码和译码算法；
二、实验内容：
实现McEliece公钥密码体制，并以(7,4)Hamming码为例进行测试。
三、实验环境
Win7 Java
四、实验过程（请学生认真填写）：
1. 预备知识：
McEliece密码体制是是一种基于一个二进制线性码寻找最近码字的困难性的密码体制，McEliece建议采用一个[1024,512,101]Goppa码，但是任何具备良好译码特性的线性编码都是可以使用的。这里由于对Goppa码不熟悉，选择了Hamming码来实现McEliece密码体制。
2. 实验过程
A、原理分析：
具体协议如下：
Bob选择G—(n,k)线性纠错码C的生成矩阵(最大纠错能力为d),S—模2意义下k×k可逆矩阵，P—n×n置换矩阵，计算G1= SGP，公开公钥G1，对私钥（S，G，P）保密。
Alice试图给Bob发送消息x，首先随机产生噪声e (长度为n,重量为t)，再利用公钥对x进行加密：y = xG1+ e，将y发送给Bob
Bob解密消息：计算y1= yP-1,再通过线性纠错码C的校验矩阵来得到y1的最近码字x1。通过计算得到x0,使得x0×G=x1，通常直接取x1前k个Bits做为x0。计算x=x0S-1,解密完成，得到原始消息。
B、具体代码较多，放在最后源代码部分
实验中关于求行列式的值，矩阵乘积，矩阵求逆，Hamming码校验矩阵和生成矩阵相关函数，都
是在以前实验课基础上加以修改后使用的。 云南大学数学与统计学实验教学中心实验报告
第 2 页 共 12 页 实验结果：
分析：由于Hamming码纠错能力有限，只能正确纠正一个比特位置上的错误，所以这次试验只是用来模拟McEliece公钥密码体制的相关过程，不具有实用性。并且查阅资料以后，对McEliece有了更多了解。虽然比较简单容易实现，但也存在不容忽视的弊端，比如1）公钥G1的密钥空间太大。如果使用Goppa码，公钥将有219 个bit密钥空间太大。
2）密文比明文要大得多。这将导致传输中的错误发生的可能性增加。在构造加密体制时应该结合各种差错控制机制以保证加密信息的可靠传输，否则可能无法解密。
五、实验总结 云南大学数学与统计学实验教学中心实验报告
第 3 页 共 12 页 1．遇到的问题、分析并的出方案（列出遇到的问题和解决办法，列出没有解决的问题）：
遇到问题：
如何利用校验矩阵找到最近码字，Hamming码编码和纠错的原理设计
分析并解决：
查阅资料得到解决。
2．体会和收获。
通过学习，编写McEliece公钥密码体制算法，实现其加密和解密过程，更深一步的了解了其设计思路。收获还是比较大的。但是，代码只是在Hamming上测试，没有深入地进行探究，在大数据中运用的话，必然会有秘钥空间较大，效率比较低的问题，这里没有实现，比较遗憾吧。
六、参考文献
GMP_Document
《应用密码学》 林岱岳
《密码学概论》wade trape
七、教师评语：
八、源代码：
/* McEliece的实验
*
*1.熟悉McEliece码的设计原理；
*2.编程实现编码和译码算法；
*/
package HammingCode;
import java.util.Scanner;
import java.util.Random;
/*
* @author 卢富毓
* @see 实现McElice
*/
public class McElice {
static int k, m, n;
Scanner sc;
public static void main(String[] args) {
McElice MC = new McElice();
MC.start(MC);
}
public void start(McElice MC) {
System.out.print("请输入校验位数 k = ");
sc = new Scanner(System.in);
k = sc.nextInt();// 3 云南大学数学与统计学实验教学中心实验报告
第 4 页 共 12 页 n = (int) Math.pow(2, k) - 1;// 7
m = n - k;// 4
HammingCode HMC = new HammingCode();
HMC.Create(HMC);// 得到H,G
Matrix S = new Matrix();
S = S.GenerateS();
Matrix P = new Matrix();
P = P.GenerateP();
Matrix G = new Matrix(k, n);
G.Mt = HMC.G;
Matrix G1 = new Matrix();
G1 = G1.MultipleMatrix(S, G);
G1 = G1.MultipleMatrix(G1, P);
System.out.println("公钥G1:");
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(G1.Mt[i][j] + " ");
}
System.out.println();
}
int send[] = new int[m];
// 输入字符进行编码
System.out.print("请输入需编码的字符（0、1）" + m + "个：");
for (int i = 0; i < m; i++) {
send[i] = sc.nextInt();
}
sc.close();
int receive[] = this.Encrypt(send,HMC, G1);
int send0[] =this.Decrypt(receive, P, S, HMC);
for(int i=0 ; i
if(send0[i]!=send[i]){
System.out.println("解密错误！");
return;
}
}
System.out.println("解密正确");
return;
}
public int[] Encrypt(int send[],HammingCode HMC, Matrix G1) {
int receive[] = new int[n];
int e;
Random rnd = new Random();
e = rnd.nextInt(n); //e:0~n-1
// 编码
receive = HMC.encode(G1.Mt, send);
// 加入噪声
receive[e] = (receive[e] + 1) % 2;
// 打印y=x*G1+e
System.out.print("y=x*G1+e:");
for (int i = 0; i < n; i++) {
System.out.print(receive[i] + " ");
}
System.out.println();
return receive;
} 云南大学数学与统计学实验教学中心实验报告
第 5 页 共 12 页
public int[] Decrypt(int receive[], Matrix P, Matrix S, HammingCode HMC) {
int[] send = new int[m];
int[] y1 = new int[n];
P.Mt = P.Invert(P);
y1 = HMC.encode(P.Mt, receive);// y1=y*p^-1
// 利用校验矩阵H求得y1的最近码字
int e1 = HMC.checkAndDecode(HMC.H, y1);//e1=H*y1
y1[e1] = (y1[e1]+1)%2;
for (int i = 0; i < n; i++) {
//y1[i] = y1[i] ^ P.Mt[i][e1];
if (i < m) {
send[i] = y1[i];//取y1前m位放入send数组中
}
}
S.Mt = S.Invert(S); //S^-1
send = HMC.encode(S.Mt, send);//x0 = send * S^-1
System.out.print("解密出的明文：");
for (int i = 0; i < m; i++) {
System.out.print(send[i]+" ");
}
return send;
}
class HammingCode {
int[][] H;
int[][] G;
/**
* @param start
* Hamming码的具体实现
* @param HMC
* 类的实例
*/
public void Create(HammingCode HMC) {
// Hamming 码的校验矩阵生成
H = HMC.CreateCheckArray();
// Hamming 码的生成矩阵生成
G = HMC.GenerateArray();
}
/**
* @param ToBinary
* 校验矩阵 十进制数转为二进制矩阵
* @return 返回校验矩阵
*/
public int[][] CreateCheckArray() { // 二进制 校验矩阵
int m1 = 1;
int l = 0;
int[][] b = new int[k][n];
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < b[i].length; j++) {
