Richard Suchenwirth 2002-06-01 - After function mapping, here is an application for matrix multiplications: encryption. We use map to transpose the second matrix in multiplication, and again to multiply elementwise:
proc mat* {A B} {
set C {}
set Bt [eval map list $B]
foreach arow $A {
set crow {}
foreach bcol $Bt {
lappend crow [sum [map * $arow $bcol]]
}
lappend C $crow
}
set C
}
proc map {fun args} {
set cmd "foreach "
set fargs {}
for {set i 0} {$i<[llength $args]} {incr i} {
append cmd "$i [string map [list @ $i] {[lindex $args @]}] "
lappend fargs $$i
}
append cmd [string map [list @f $fun @a [join $fargs]] {{
lappend res [@f @a]
}}]
set res {}
eval $cmd
set res
}
proc * {a b} {expr {$a*$b}}
proc sum list {expr [join $list +]}We can do matrix multiplication now - so what? Here's an interesting application in cryptography (from a German math book): given a string to encrypt, e.g.
This is matrix magic
convert each character to a number (e.g. decimal Unicode); group each four characters into a 2x2 matrix; multiply that with a same-sized encryption matrix; transmit the resulting sequence of matrix contents, which in the example look like
-20 208 -10 230 -73 210 83 64 12 194 2 228 -15 240 -77 218 -6 206 6 198
Decoding such a cryptogram goes backwards: group the numbers into 2x2 matrices; multiply with the inverse of the encryption matrix (this is the really secret part); format into the corresponding characters.
This simple encryption has the property that same letters have unequal equivalents, depending on the context - e.g. "i" comes as -10, 210, -15, 6 above; but equal 4-grams of course have the same code:
% matrixEncrypt foolfool => -9 222 3 216 -9 222 3 216
proc matrixEncrypt {s {M {{1 0} {-1 2}}}} {
if {[set ls [string length $s]]%4} {
append s [string repeat " " [expr 4-$ls%4]]
}
set res ""
foreach {a b c d} [map c2i [split $s ""]] {
eval lappend res [mat* "{$a $b} {$c $d}" $M]
}
eval concat $res ;# flatten the list of rows
}
proc matrixDecrypt {numbers {M {{1 0} {.5 .5}}}} {
foreach {a b c d} $numbers {
eval lappend t [mat* "{$a $b} {$c $d}" $M]
}
join [map n2c [eval concat $t]] ""
}
#------------ little helper functions for mapping:
proc c2i c {scan $c %c}
proc n2c n {format %c [expr round($n)]}We can experiment how cryptic the output gets:
% matrixEncrypt a 65 64 0 64 % matrixEncrypt aa 0 194 0 64 % matrixEncrypt aaa 0 194 65 64 % matrixEncrypt aaaa 0 194 0 194 % matrixEncrypt "Hello, world" -29 202 0 216 67 88 -87 238 -3 228 8 200
One might also try larger matrix sizes - but what's always required is that sender and receiver agree on one matrix, and the inverse matrix is used in decoding - just I don't have matrix inversion algorithms handy ;-(
There is little point in treating the message as a 2x2 matrix. The ith row of the left factor will only affect the ith row of the product. You reach essentially the same result by treating pairs of characters in the message as a 1x2 matrix and multiplying that with the cipher key matrix. Encoding pairs of characters is of course only slightly stronger than a single character replacement cipher. Larger matrices should be used, and one should furthermore work with matrices over some finite field (easiest: do all calculations modulo some suitably large prime) since that at least makes the size of the numbers in the ciphertext irrelevant. Unfortunately this encryption method still has the same basic flaw as the Caesar cipher: if you for only one ciphertext matrix know what the corresponding plaintext matrix is, then you can easily figure out they key. An important feature of most "industrial strength" ciphers, such as RSA or DES, is that even if you know corresponding plaintext and ciphertext you still don't get any useful information about the key. -- Lars H