mceliece密码系统.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.09M 资料格式：pdf 举报版权申诉

ligong200803-2312062-4744300845230489358.pdf-第1页.png

第1页 / 共13页

ligong200803-2312062-4744300845230489358.pdf-第2页.png

第2页 / 共13页

ligong200803-2312062-4744300845230489358.pdf-第3页.png

第3页 / 共13页

ligong200803-2312062-4744300845230489358.pdf-第4页.png

第4页 / 共13页

ligong200803-2312062-4744300845230489358.pdf-第5页.png

第5页 / 共13页

ligong200803-2312062-4744300845230489358.pdf-第6页.png

第6页 / 共13页

ligong200803-2312062-4744300845230489358.pdf-第7页.png

第7页 / 共13页

ligong200803-2312062-4744300845230489358.pdf-第8页.png

第8页 / 共13页

文本预览

The McEliece Cryptosystem

Introduction This public key cryptosystem, introduced by McEliece in 1978, is similar to the Merkle-Hellman Knapsack cryptosystem in that it takes an easy case of an NP- problem and disguises it to look like the hard instance of the problem. In this cryptosystem, the problem that is used is drawn from the theory of error-correcting codes.

The Problem Syndrome decoding of linear codes (when considered as a decision problem) is an NP-complete problem if the number of errors is not bounded. However, there are classes of linear codes which have very fast decoding algorithms. The basic idea of the McEliece system is to take one of these linear codes and disguise it so that Oscar, when trying to decrypt a message, is forced to use syndrome decoding, while Bob, who set up the system, can remove the disguise and use the fast decoding algorithm. McEliece suggested using Goppa Codes, which are linear codes with a fast decoding algorithm, in the system, but any linear code with a good decoding algorithm can be used.

The Cryptosystem k invertible matrix (the n permutation matrix (i.e., having a Let C be an [n,k]-linear code with a fast decoding algorithm that can correct t or fewer errors. Let G be a generator matrix for C. To create the disguise, let S be a k · scrambler) and let P be an n · single 1 in each row and column and 0's everywhere else). The matrix, G' = SGP is made public while S, G and P are kept secret by Bob. For Alice to send a message to Bob, she blocks her message into binary vectors of length k. If x is one such block, she randomly constructs a binary n-vector of weight t (that is, she randomly places t 1's in a zero vector of length n), call it e and then sends to Bob the vector y = xG' + e.

The Cryptosystem Oscar, upon intercepting this message, would have to find the nearest codeword to y of the code generated by G'. This would involve calculating the syndrome of y and comparing it to the  n syndromes of all the error vectors of weight t. As there are of these error vectors, good choices of n and t will make this computation infeasible. t Bob, on the other hand, would calculate yP-1 = (xG' + e)P-1 = xSG + eP-1 = xSG + e' where e' is a vector of weight t (since P-1 is also a permutation matrix). Bob now applies the fast decoding algorithm to strip off the error vector e' and get the code word (xS)G.

The Cryptosystem The vector xS can now be obtained by multiplying by G-1 on the right (however, if Bob had been smart, he would have written G in standard form [I positions of xSG and this multiplication would not be needed). Finally, Bob gets x by multiplying xS on the right by S-1. A], and then xS would just be the first k k For McEleice's Goppa Code example, n = 1024 and t = 50 which gives Oscar more than 1080 syndromes to calculate.

An Example For an example we shall use the (7,4) Hamming code which corrects all single errors. A generator matrix for this code is given by (note the clever choice):  G=1 0 0 0 1 1 0  S =1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 and Bob chooses the scrambler matrix

An Example and the permutation matrix P=0 1 0 0 0 0 0  G '=S G P=1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 Bob makes public the generator matrix 

分享到：

赞收藏

资料库

mceliece密码系统.pdf

相关推荐

课程资源

热门标签

最新资料