Borrar filtros
Borrar filtros

Using Metropolis-Hastings to decrypt a message

5 visualizaciones (últimos 30 días)
Alex
Alex el 14 de Dic. de 2011
I'm using Metropolis-Hastings to decrypt a coded message. First I downloaded 'War & Peace' and used this to build a transition probability matrix for 53 different symbols (letters, numbers, etc). I assume that I did this correctly. Now I am trying to decrypt this message by starting off with an initial decoding key which is just a random permutation of the symbols. The decoding key maps each symbol to its coded version. Now I decrypt the message with this key and determine the transition probabilities between each successive decrypted symbol using the transition probability matrix found from 'war and peace'. Then I swap two symbols in the key to make a new key and do the same computation with this key. If the product of the transistion probabilities is greater for this new key then I keep it, if not I keep the old key. I keep changing the key to see if it improves for 1000 iterations. The problem is that when I decode the message with the key that the algorithm finds, the result is not comprehensible so I think there is a problem. The following is my code
%set number of iterations of algorithm
numIter=3000;
%import list of symbols
symbols=importdata('symbols.txt',',',53);
%now load message that we want to decrypt
message=fileread('message.txt');
%determine length of message
messageLength=length(message);
%create initial permutation guess. So each symbol in the 'symbols' array is
%mapped to the corresponding symbol in the 'permut' array. i.e. 'permut' is
%the decoding key
permut=symbols(randperm(length(symbols)));
%find most commonly occuring character in message
mostCommon=char(mode(double(message)));
%find its position in the message
commonPos=find(~cellfun(@isempty,strfind(permut,mostCommon)));
%now map this to the space character because this is the most common symbol
%which we know from the probabilities. Space is the second symbol.
swapCommon1=permut(2);
swapCommon2=permut(commonPos);
permut(2)=swapCommon2;
permut(commonPos)=swapCommon1;
%find initial transition probabilities of this key
totTransProb=1;
%totSymbolProb=symbolProb(find(~cellfun(@isempty,strfind(permut,message(1)))));
for i=1:(messageLength-1)
%find symbol that maps to ith symbol of message
X=find(~cellfun(@isempty,strfind(permut,message(i))));
%find symbol that maps to i+1th symbol of message
Y=find(~cellfun(@isempty,strfind(permut,message(i+1))));
%find the transition probabilities between these symbols
totTransProb=totTransProb*transProb(X,Y);
%totSymbolProb=totSymbolProb*symbolProb(Y);
end
%oldCompare=totTransProb*totSymbolProb;
oldCompare=totTransProb;
%begin algorithm
for j=1:numIter
%now swap two random symbols in the decoding key and call this new decoding
%key newPermut
newPermut=permut;
randomized=randperm(53);
swap1=permut(randomized(1));
swap2=permut(randomized(2));
newPermut(randomized(1))=swap2;
newPermut(randomized(2))=swap1;
%now determine the transition probabilities of this new key
newTransProb=1;
%newSymbolProb=symbolProb(find(~cellfun(@isempty,strfind(newPermut,message(1)))));
for i=1:(messageLength-1)
%find symbol that maps to ith symbol of message
X=find(~cellfun(@isempty,strfind(newPermut,message(i))));
%find symbol that maps to i+1th symbol of message
Y=find(~cellfun(@isempty,strfind(newPermut,message(i+1))));
%find the transition probabilities between these symbols
newTransProb=newTransProb*transProb(X,Y);
%newSymbolProb=newSymbolProb*symbolProb(Y);
end
%newCompare=newTransProb*newSymbolProb;
newCompare=newTransProb;
%if this new decoder is better than the old one then keep it otherwise
%discard it.
if newCompare>oldCompare
oldCompare=newCompare;
permut=newPermut;
end
end
%now decoded message with the best key
for k=1:messageLength
X=find(~cellfun(@isempty,strfind(permut,message(k))));
decodedMessage(k)=symbols(X);
end
myMessage=char(decodedMessage);

Respuestas (0)

Categorías

Más información sobre Condensed Matter & Materials Physics en Help Center y File Exchange.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by