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 +]}if 0 {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 matrixes; 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)]}if 0 {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 ;-( }
Category Cryptography | Arts and crafts of Tcl-Tk programming