OTP: Matlab Solution

Matlab isn't the most popular programming language out there (especially given that an individual license will run you over $2,000**), but it's incredibly powerful. For me, it also has a nostalgic appeal, as analyzing fMRI data with Matlab scripts served as my introduction to programming. So when David posed his One Time Pad programming challenge I relished the opportunity to relive some of the magic and mystery of Matlab.

** Check out Octave for a similar-but-open-source, free alternative to Matlab (and prepare for your mind to be blown when you discover that LaTeX—an Octave dependency—is 2.5GB).

One-Line Wonder

In my DIBS days, there was a half-joking mantra that you could accomplish anything with a single line of Matlab. It's no myth that extremely complex problems have historically been solved with extremely simple Matlab programs. Take for example the source separation (aka cocktail party problem) solution famously included in Andrew Ng's introductory Machine Learning slides:

 [W,s,v] = svd((repmat(sum(x.*x,1),size(x,1),1).*x)*x');

Would it be possible to implement a one-line OTP solution?

The Good

Arrays FTW

If Matlab has one strength, it's running computations over arrays and matrices. The fact that Matlab strings are really just arrays of characters, combined with liberal use of arrayfun would get me most of the way to a one-line solution.

Functions for Everything

Part of the power of Matlab is the fact that it has built-in functions for seemingly everything. Using bitxor, dec2hex, hex2dec, and circshift kept complicated code out of the OTP solution, and made the one-line objective more realistic.

The Ugly

1-indexed Arrays

Arrays in Matlab are 1-indexed (something about Matlab being made for Mathematicians, not Computer Scientists). The side effect of this is that it greatly complicates the modular arithmetic necessary to repeat key sequences.

In 0-indexed programming languages, if I have a 3-character key, and need to grab the second key pair, I can simply take the modulus of the key index and the size of the key to wrap around to the beginning of the key when my key is too short for the message. Consider the Ruby implementation:

 key <span class="pl-k">=</span> [<span class="pl-s1"><span class="pl-pds">'</span>a<span class="pl-pds">'</span></span>, <span class="pl-s1"><span class="pl-pds">'</span>b<span class="pl-pds">'</span></span>, <span class="pl-s1"><span class="pl-pds">'</span>c<span class="pl-pds">'</span></span>]
key[<span class="pl-c1">0</span>] <span class="pl-k">+</span> key[<span class="pl-c1">1</span>] <span class="pl-c"># First Keypair (n = 0)</span>
key[<span class="pl-c1">2</span>] <span class="pl-k">+</span> key[<span class="pl-c1">0</span>] <span class="pl-c"># Second Keypair (n = 1)</span>
key[((<span class="pl-c1">2</span> <span class="pl-k">*</span> n) <span class="pl-k">%</span> key.size)] <span class="pl-k">+</span> key[((<span class="pl-c1">2</span> <span class="pl-k">*</span> n) <span class="pl-k">+</span> <span class="pl-c1">1</span> <span class="pl-k">%</span> key.size)] <span class="pl-c"># All Keypairs (</span><span class="pl-c">n ∈ ��</span><span class="pl-c">)</span>

With 1-indexed arrays, this solution completely falls apart. The only reasonable way out of this tricky situation is to fake a 0-indexed array by shifting all the elements over 1 position. (I also used this circshift line to address the edgecase of the use of a single-character key.)

 key = circshift([key key],1, 2) // Goodbye 1-line solution :-(

Command Line Sadness

Matlab likes to run within the comfort of its IDE. You can run it from the command line, but the output is ghastly.

Matlab on the command-line

With great sadness I had to resort writing a shell script to run the Matlab command and sed the output to get the encrypted/decrypted value. Hardly elegant.

 #!/bin/bash
read in2
echo -n $(matlab -nodesktop -nosplash -nojvm -r "try; encrypt('$1','$in2'); end; quit;" | sed -n '/encrypted/{n;n;p;}')

The Result

Ultimately my one-line pursuit was a failure. This was as close as I could get:

Encryption

 key = circshift([key key],1, 2)
encrypted = lower(strjoin(arrayfun(@(c,k)dec2hex(bitxor(int16(c),k)),message,arrayfun(@(i)hex2dec([key(mod((i-1)*2,numel(key))+2),key(mod(i*2,numel(key))+1)]),1:numel(message)),'un',0),''))

Decryption

 key = circshift([key key],1, 2)
decrypted = [char(bitxor(arrayfun(@(i)hex2dec([key(mod((i-1)*2,numel(key))+2),key(mod(i*2,numel(key))+1)]),1:numel(arrayfun(@(i)hex2dec(strcat(message(i*2-1),message(i*2))),1:(numel(message)/2),'un',0))),cell2mat(arrayfun(@(i)hex2dec(strcat(message(i*2-1),message(i*2))),1:(numel(message)/2),'un',0))))]

See the solution complete with supporting files here: https://github.com/vigetlabs/otp/tree/master/languages/Matlab

If you're able to devise a clever one-liner, please show me up in the comments below!

Lawson Kurtz

,
Posted in Article Category: #Code
on