Cryptography Reference
In-Depth Information
X
−
1
Y
and
then the target ciphertext is decrypted by using the inverse of
A
. Finally, the function
returns the decryption of the target ciphertext, given as a text string.
=
to those of
X
. Since
X
is invertible, the key
A
may be computed as
A
> HillCryptanalysis := proc(knownplaintext, kciphertext, blocklength, ciphertext)
local blt, blc, rd, det, c, z, q, rows, gcd, invq, k, x;
if StringTools:-Length(ciphertext) mod blocklength <> 0 then
error "Erroneous blocksize"
end if;
blt := blocks(knownplaintext, blocklength);
blc := blocks(kciphertext, blocklength);
rd := RowDimension(blt);
gcd := 0;
c := combinat:-choose([$1..rd], blocklength);
for z in c while gcd <> 1 do
q := SubMatrix(blt, z, [$1..blocklength]);
det := Modular:-Determinant(modulus, q);
gcd := igcd(det, modulus);
rows := z;
end do;
if gcd <>1 then
error "There are not enough linearly independent blocks to complete
cryptanalysis"
end if;
invq := Modular:-Inverse(modulus, q, RREF);
x := SubMatrix(blc, rows, [$1..blocklength]);
k := Modular:-Multiply(modulus, invq, x);
HillDec(k, ciphertext);
end proc:
Let us present a specific example of how this procedure works. Let us take as
known plaintext the following string:
> kpt := "this sentence is the known plaintext that we will use in our attempt to
break this block cipher":
Next, we generate the key. In order to make the example nontrivial, we will
use a 10
10 matrix (i.e., we will use 10 as block length) which will not
be explicitly printed here. This way the key space (consisting of all the invert-
ible 10
×
×
10-matrices over
Z
27
) is sufficiently large to ensure that a brute-force
attack is infeasible.
> k := PseudoRandomInvertibleMatrixMod(10):
We compute the ciphertext that corresponds to the above known plaintext:
> kct := HillEnc(k,kpt);
kct := "sqwtwoz h sxoniizxtcmthsuxgasjfloxyryfktcnyptyzpmlhycsubnxyvhakozjunptrc\
bbgtraeunqvkoayzsjzql notgb"
Now, suppose that we have a ciphertext obtained by encrypting an unknown
plaintext with the same key:
> ciphertext := "tt msflnikw vrgzncxftqwzeeebal":
To recover the plaintext without using
k
(which now we assume is unknown to
us), we use the
HillCryptanalysis
function above:
