208
12 Cryptocurrencies
channel becomes zero, if the probability ε for a flipped bit is 1/2 in the encryption
process. At the same time, we need to ensure that the encryption process is invertible,
such that Bob can recover the original message m from the cipertext c.
In the following we will exclusively deal with binary, rather than textual data
such that we can use the binary symmetric channel as an example. Let us assume
that Alice wants to send the letter “A,” which is m = b’01000001 in the ASCII code.
One way to encrypt binary numbers is based on the logical exclusive or, or xor(i, j)
function, which is defined for one bit i, j = 0, 1 to return xor(i, j) = 0 for i = j
and xor(i, j) = 1 for i = j. For multi-bit numbers, such as m = b’01000001, and
the secret key k, we define xor(m, k) to operate on one bit at a time. Using the secret
key k =b’01101100, we find the ciphertext c = xor(m, k) from
m = b’01000001
k = b’01101100
c = b’00101101
whenever m and k have the same bit in a particular position the c contains “0” in
that position; if the bits are different, c contains “1.” It is easy to convince ourselves
that Bob can recover the original message m from the ciphertext c by calculating
m = xor(c, k).
Bob can decode the ciphertext c, but Eve only sees c. Let us therefore calculate
the conditional probabilities p y,x and p zx from (12.8), where Alice sends x i , Bob
receives y i , and Eve observes z i . In the following MATLAB script, we first define
the key k and 2 × 2 arrays to hold the conditional probabilities. Then we loop over
all possible messages m, which implies α = 1/2 in Fig. 12.2 and ensures that the
same number of “1” and “0” are sent. Inside the loop, we first encode m to obtain
the ciphertext c before simulating Bob’s action of decoding c with the same key k.
Then we compare the eight bits in each byte and update the conditional probabilities.
After the loops we normalize the entries in the 2 × 2 matrices for the conditional
probabilities.
k=bin2dec(’01101100’);
% key
pyx=zeros(2,2); pzx=pyx; % cond. probabilities
for m=0:255
% loop over all messages
c=bitxor(m,k);
% Alice encodes to ciphertext
bob=bitxor(c,k);
% Bob decodes with key
for i=1:8
% compare all eight bits
bx=bitget(m,i);
bz=bitget(c,i);
by=bitget(bob,i);
pyx(2-by,2-bx)=pyx(2-by,2-bx)+1; % update probs.
pzx(2-bz,2-bx)=pzx(2-bz,2-bx)+1;
end
end
pyx=pyx/1024
% Alice to Bob, pyx=[1,0;0;1]
pzx=pzx/1024
% Alice to Eve, pzx=[0.5,0.5;0.5,0.5]
12 Cryptocurrencies
channel becomes zero, if the probability ε for a flipped bit is 1/2 in the encryption
process. At the same time, we need to ensure that the encryption process is invertible,
such that Bob can recover the original message m from the cipertext c.
In the following we will exclusively deal with binary, rather than textual data
such that we can use the binary symmetric channel as an example. Let us assume
that Alice wants to send the letter “A,” which is m = b’01000001 in the ASCII code.
One way to encrypt binary numbers is based on the logical exclusive or, or xor(i, j)
function, which is defined for one bit i, j = 0, 1 to return xor(i, j) = 0 for i = j
and xor(i, j) = 1 for i = j. For multi-bit numbers, such as m = b’01000001, and
the secret key k, we define xor(m, k) to operate on one bit at a time. Using the secret
key k =b’01101100, we find the ciphertext c = xor(m, k) from
m = b’01000001
k = b’01101100
c = b’00101101
whenever m and k have the same bit in a particular position the c contains “0” in
that position; if the bits are different, c contains “1.” It is easy to convince ourselves
that Bob can recover the original message m from the ciphertext c by calculating
m = xor(c, k).
Bob can decode the ciphertext c, but Eve only sees c. Let us therefore calculate
the conditional probabilities p y,x and p zx from (12.8), where Alice sends x i , Bob
receives y i , and Eve observes z i . In the following MATLAB script, we first define
the key k and 2 × 2 arrays to hold the conditional probabilities. Then we loop over
all possible messages m, which implies α = 1/2 in Fig. 12.2 and ensures that the
same number of “1” and “0” are sent. Inside the loop, we first encode m to obtain
the ciphertext c before simulating Bob’s action of decoding c with the same key k.
Then we compare the eight bits in each byte and update the conditional probabilities.
After the loops we normalize the entries in the 2 × 2 matrices for the conditional
probabilities.
k=bin2dec(’01101100’);
% key
pyx=zeros(2,2); pzx=pyx; % cond. probabilities
for m=0:255
% loop over all messages
c=bitxor(m,k);
% Alice encodes to ciphertext
bob=bitxor(c,k);
% Bob decodes with key
for i=1:8
% compare all eight bits
bx=bitget(m,i);
bz=bitget(c,i);
by=bitget(bob,i);
pyx(2-by,2-bx)=pyx(2-by,2-bx)+1; % update probs.
pzx(2-bz,2-bx)=pzx(2-bz,2-bx)+1;
end
end
pyx=pyx/1024
% Alice to Bob, pyx=[1,0;0;1]
pzx=pzx/1024
% Alice to Eve, pzx=[0.5,0.5;0.5,0.5]